Содержание к диссертации
Введение
1 Анализ системы с марковским потоком и марковским обслуживанием в непрерывном времени 23
1. Описание системы 23
2. Стохастическая модель системы 26
3, Система уравнений равновесия 27
4. Решение уравнений равновесия 31
5. Основные показатели производительности системы 37
6, Стационарные вероятности состояний системы по моментам поступления основных заявок и выхода обслуженных
заявок 40
7. Стационарное распределение времени ожидания основных заявок 43
8. Результаты имитационного моделирования и численных исследований 45
Выводы 51
2 Анализ системы с марковским потоком и марковским обслуживанием в дискретном времени 53
1. Описание системы 53
2. Стохастическая модель системы 56
3. Система уравнений равновесия 57
4. Решение уравнений равновесия 62
5. Стационарные вероятности состояний системы по моментам поступления основных заявок
Выводы 67
3 Анализ системы с марковским потоком и произвольным временем обслуживания основных и фоновых заявок 68
1. Описание системы 68
2. Стохастическая модель 69
3. Решение уравнений равновесия 71
4. Некоторые соотношения для показателей производительности 79
5. Стационарные вероятности по моментам поступления основных заявок 80
6. Стационарное распределение времени ожидания основных заявок при дисциплине FCFS 82
Выводы 85
Заключение 86
Литература 88
- Стохастическая модель системы
- Стационарное распределение времени ожидания основных заявок
- Стохастическая модель системы
- Некоторые соотношения для показателей производительности
Введение к работе
Развитие человечества всегда было связано с информацией: её накоплением и хранением, обменом и переработкой. Многовековое развитие информационных технологий взаимообусловливало параллельное развитие производства, науки, искусства и образования [35,37]. Чем больше накоплено цивилизацией знаний, тем больше есть альтернативных решений для возникающих перед человечеством проблем, и тем более адекватное и эффективное решение может быть выбрано. Чем быстрее и чем больший объём информации позволяет переработать имеющийся у человека инструментарий, тем более полно можно исследовать проблему и тем более эффективное решение может быть выбрано для неё. Чем быстрее распространяется информация, тем больше людей (или машин) могут одновременно работать над решением одной проблемы и тем быстрее и эффективнее может быть решена проблема. В полной мере проявляется и обратная зависимость: для продвижения прогресса требуется развитие инструментов, решающих три упомянутые выше основные задачи по манипуляции информацией.
Очередным этапом развития информационных технологий стало в середине прошлого века применение компьютеров для автоматической обработки данных, а впоследствии и компьютерных сетей для их передачи. Современное понятие информационных технологий (ИТ) включает в себя "совокупность систематических и массовых способов и приёмов обработки информации во всех видах человеческой деятельности с использованием современных средств связи, полиграфии, вычислительной техники и программного обеспечения" [37].
В наше время информация является одним из наиболее важных ре-
сурсов, поэтому решения в области ИТ подвергаются тщательному анализу и оптимизации с применением математического моделирования. Для исследования по меньшей мере двух составляющих ИТ — обработки и передачи информации — широко применяется аппарат теории массового обслуживания (ТМО) [1-4,7-9,22,26,28,32,40-43,70,71,82,100], предметом изучения которой являются системы массового обслуживания (СМО) и сети массового обслуживания (СеМО).
В современной науке подавляющее большинство открытий и других результатов достигается на стыках различных наук или направлений отдельной науки. Исследования, проведённые в рамках диссертации, также состоят в решении задач, лежащих на пересечении нескольких направлений ТМО, таких как: СМО с ограниченной ёмкостью; системы с при-оритсзацией обслуживания; СМО с отключениями прибора; системы с коррелированными входящим потоком заявок и обслуживанием; СМО, функционирующие в дискретном времени. Поэтому, чтобы описать направление исследования, проводимого в рамках диссертации, и дать обзор современного состояния этого направления, необходимо рассмотреть все перечисленные выше области и направления ТМО.
Вернёмся задаче ТМО, упомянутой выше: моделирование информационных систем с целью оптимизации их работы. Для адекватного построения моделей необходимо учитывать специфические свойства исследуемых систем, относящиеся в основном к числу обслуживающих устройств, количеству и объему накопителей, процессу обработки заявок, дисциплине обслуживания и пр. Одной из особенностей практически существующих систем, не учитываемой в простейших аналитических моделях, является ограниченная ёмкость буферного накопителя. Если в СМО с ограниченным накопителем не учитывается эффект повторных вызовов, то поступившая заявка, которая застаёт накопитель перепоненным, не принимается в систему и считается потерянной. Соответственно для разработчиков систем с конечным накопителем важно достичь низкой вероятности потери заявок. Поэтому в работах по иссле-
дованию таких систем уделяется особое внимание вероятности потери заявок. Следует отметить, что, как правило, для моделей с ограниченным буферным накопителем сложнее получить аналитические результаты.
Другой особенностью современных приложений СМО, усложняющей их анализ, является так называемая коррелированность [63,91] трафика (входящего потока в терминах ТМО) в телекоммуникационных сетях. Это явление связано прежде всего с тем, что по одному каналу связи с помощью пакетного мультиплексирования передаётся информация по соединениям, установленным между несколькими источниками и приёмниками в сети. Кроме того, имеет место явление так называемого взрывного (bursty) или пульсирующего трафика. Одним из наиболее широко и успешно применяемых подходов к аналитическому моделированию зависимых потоков является использование марковского потока заявок (Markovian Arrival Process — MAP), впервые введённого в 1979 году в работе Neuts M.F. [99] и активно используемого после более полного рассмотрения в 1990 году в работе Lucantoni D. М. и др. [92]. Марковский поток покрывает широкий класс зависимых входящих потоков, в частности, пуассоповский поток, управляемый цепью Маркова (Markov Modulated Poisson Process — MMPP) и прерывающийся пуассоновский поток (Interrupted Poisson Process — IPP). При этом основными эксплуатируемыми свойствами марковского потока являются большой набор разработанных аналитических методов для систем с потоком такого типа и возможность аппроксимации реальных потоков с помощью марковского потока (в основном за счёт высокой параметризуемости). Существуют и другие методы моделирования зависимых потоков заявок. Так, например, при исследовании процессов передачи сжатого видео с переменным объёмом данных в кадре Melamed [95] предложил метод TES (Transform Expand Sample), который позволяет построить поток заявок с любой заданной точностью приближенный по функции распределения (ФР) и функции автокорреляции к заданным, например, на основе наблюдений реальным процессам, а позднее [75] был выработан алгоритм
подбора параметров TES-процессов. Однако TES-метод не применим для аналитических исследований и используется лишь в имитационном моделировании, где требуется генерировать случайные потоки заявок, соответствующие по вероятностным свойствам наблюдаемым в реальных системах.
Помимо систем с зависимым входящим потоком в приложениях встречаются и системы с зависимым обслуживанием. Одним из подходов к моделированию таких систем является использование марковского процесса обслуживания (Markovian Service Process — MSP). Учёт зависимости в обслуживании ведет к серьёзному усложнению модели, поэтому результатов в этом направлении на данный момент немного. В работах [11,13] была рассмотрена однолинейная СМО G/MSP/1/r, а в работах [36,48,49] была исследована аналогичная система с несколькими приборами. Кроме того, велись работы [45,74,103] по аппроксимации выходящего потока системы MAP/MSP/1 марковским потоком для последующего использования в моделях СеМО с узлами MAP/MSP/1.
Еще одна важная особенность современных приложений, затрудняющая анализ СМО, и особенно систем с ограниченными накопителями, связана с широким применением моделей очередей с приоритезацией обслуживания заявок в зависимости от их класса. При этом наиболее часто используются абсолютный и относительный приоритеты. В системах с абсолютным приоритетом заявки некоторого класса 1 (1-заявки) имеют перед заявками класса 2 (2-заявками) приоритет, состоящий в том, что если 1-заявка приходит в систему или выбирается из накопителя в качестве следующей для поступления на прибор, когда все приборы заняты и хотя бы один из них обслуживает 2-заявку, то пришедшая 1-заявка вытесняет 2-заявку, становится на ее место, а последняя возвращается в очередь (для дообслуживания с прерванного места или заново). Если 1-заявка приходит в систему в момент, когда все приборы обслуживают 1-заявки, то она ожидает обслуживания в накопителе. В то же время 2-заявка помещается в накопитель, если она приходит в систему в мо-
мент, когда приборы заняты безразлично какими заявками. В отличие от систем с абсолютным приоритетом в системах с относительным приоритетом заявка с более низким приоритетом не вытесняется с прибора, а приоритет проявляется лишь при выборе из накопителя следующей заявки для обслуживания. В этом случае заявки низшего приоритета не выбираются из накопителя на обслуживание до тех пор, пока в нем находятся заявки более высокого приоритета. Часто в системах с приоритетными классами заявок вводят раздельные накопители для заявок различных классов.
Исследованию приоритетных систем посвящено много публикаций, в том числе монографии [14,21,23-25,30,31]. Исследования в этой области продолжаются и в настоящее время и появляются новые публикации, содержащие как аналитические решения для более сложных моделей, так и примеры приложений [93,107,110,111]. Приведём здесь примеры работ по основным направлениям приложения моделей с приоритезацией обслуживания.
В задачах обработки информации понятие приоритезации играет последние 2-3 десятилетия очень важную роль, так как на обработку в вычислительные системы попадают как запросы реального времени (в системах управления) или высокоприоритетные запросы (в бизнес приложениях), так и низкоприоритетные или фоновые запросы. Примерами высокоприоритетных задач в современных операционных системах являются служебные модули и компоненты ядра, а также прерывания от внешних устройств. При этом если прерывания пользовались абсолютным приоритетом со времени их введения в компьютерные системы, то диспетчеризация остальных задач до середины 90х годов производилась, как правило, с относительным приоритетом. Среди работ по аналитическим исследованиям в этом направлении можно отметить, например, работы [32,76].
В связи с приоритезацией обслуживания возникает понятие фоновой заявки, т.е. это такие заявки, которые пользуются низшим при-
оритетом при обслуживании. Кроме того, во многих приложениях это понятие подразумевает насыщенность системы фоновыми заявками, т.е. фоновые заявки поступают в систему всякий раз, когда она оказывается незагружена основными заявками.
СМО с фоновыми заявками используются, как модели автоматизированной информационной системы (АИС) с оперативной реорганизацией баз данных (БД) [33,34]. В этом случае согласно [33,34] в систему управления БД вводятся средства, обеспечивающие совместное обслуживание запросов и реорганизацию БД. При этом основной поток — поток запросов пользуется относительным приоритетом по сравнению с фоновыми заявками — циклами реорганизации. С помощью СМО с фоновыми заявками можно оценить такие показатели призводительности АИС, как среднее время ответа, средняя длина очереди запросов, пропускная способность АИС и др.
В системах передачи информации приоритезация также является важным понятием. Особенно ярким примером введения этого понятия являются системы гарантированного качества передачи (QoS — Quality of Service), активное развитие которых с начала 90х годов было вызвано необходимостью передачи голосовой (звуковой) и видео информации по цифровым телекоммуникационным сетям. Была разработана технология передачи данных ATM (Asynchronous Transfer Mode), основным требованием к которой (помимо высокой производительности) была именно поддержка QoS [50,94]. Однако, повсеместная замена старых технологий (в большей части основанных на TCP/IP — IP-based технологий) на ATM была невозможна с экономической точки зрения, вследствие, в частности, высокой стоимости ATM оборудования. Это привело к возникновению необходимости поддержки QoS в IP-based сетях. Такая поддержка была обеспечена впоследствии технологией MPLS (Multiprotocol Label Switching — многопротокольная коммутация на основе меток) [39]. Можно отметить следующие работы, в которых применён аналитический подход к исследованию систем этого класса [72,81,107,112]. В приложениях
к моделированию телекоммуникационных систем с контролем качества понятие фоновых заявок применимо, в частности, к работе узла такой сети в режиме насыщения заявками низкоприоритетного класса [101]. Фоновые заявки рассматривались также и в контексте других технологий совместной передачи голосового и цифрового трафика [56].
Помимо задач приоритезации основного трафика в телекоммуникационных сетях возникает необходимость передавать служебную информацию по общему с основным трафиком каналу. При этом в различных технологиях служебные данные могут передаваться, как с максимальным приоритетом, так и в фоновом режиме. Так, например, в узле телефонной сети с общим каналом сигнализации (ОКС) система сигнализации №7 предполагает [38], что сигнальный трафик является фоновым по отношению к основному голосовому трафику. В [5, 6] однолинейная СМО с фоновыми заявками при пуассоновском потоке и произвольном распределении времени обслуживания была использована для анализа базового метода защиты от ошибок в системе сигнализации ОКС 7.
Некоторые системы с фоновыми заявками могут также быть отнесены к системам с отключениями прибора для выполнения операций, отличных от обслуживания основного потока заявок. В этом случае обслуживание фоновых заявок можно считать отключением прибора по отношению к обслуживанию заявок других классов [5,10]. Системы с отключением прибора называют также системами с прогулками — от английского термина "vacation", употребляемого в зарубежной литературе по отношению к отключениям прибора.
Одна из первых работ, в которой авторами вводится отключение прибора, была опубликована в 1975 году [90]. Прежде, чем перейти к обзору более поздних работ в этой области, введём классификацию процедур отключения прибора. Помимо отмеченного выше сходства систем с прогулками и систем с приоритезацией обслуживания, следует отметить схожесть этих систем с системами с циклическим обслуживанием [60,64,65,68,80,85,102,113], поэтому терминологию для этих си-
стем удобно использовать для классификации систем с отключениями заявок [51,73,105,108]:
exhaustive (исчерпывающая) схема с отключением прибора после опустошения прибора;
decrementing (убывающая) схема с отключением прибора после уменьшения количества заявок в системе на одну по отношению к моменту окончания предыдущего отключения;
gated (вентильная) схема, подразумевающая обслуживание только заявок, находившихся в очереди на момент отключения прибора;
limited (ограничивающая) схема с отключением прибора после опустошения прибора или после окончания обслуживания некоторого заданного числа заявок;
ordinary (единичная) схема — частный случай ограничивающей схемы с обслуживанием не более одной заявки перед отключением.
Заметим, что рассматривались также и другие процедуры отключения прибора, например, совмещающие признаки, приведённых выше схем [86,87]. Кроме того, может задаваться различное поведение прибора, если после окончания отключения система оказывается пустой. В этом случае происходит либо повторное отключение прибора, либо прибор остаётся включенным, но простаивает [57]. В [82{, например, задаётся поведение системы после п-го повторного отключения прибора функцией распределения длительности следующего отключения, зависящей от п.
Для удобства дальнейшего обзора работ по исследованию систем с прогулками определим следующую модификацию классификации Ксн-далла. Будем задавать СМО набором символов Д|Ї|С|>|, где А указывает тип входящего потока заявок, Б — тип обслуживания, С — число
приборов, V — емкость накопителя, а дополнительный символ указывает схему отключения прибора. В качестве основы для символа будем использовать первые буквы английских названий соответствующих дисциплин, т.е. Е — исчерпывающая, D — убывающая, G — вентильная, LN — ограничивающая (N — число заявок, подлежащих обслуживанию до начала следующего отключения прибора), О — единичная. В некоторых случаях дисциплина имеет вероятностную схему окончания циклов повторяющихся отключений, в этом случае будем добавлять к символу, обозначающему тип дисциплины, индекс в, где в (О < в < 1) — вероятность перехода прибора в режим ожидания (простоя).
Наибольшее количество результатов приходится на СМО с исчерпывающей схемой отключения с повторными отключениями (дисциплина Ео). В работах [88,90,104,106,108] для системы M/G/1/oq/Eq получены некоторые результаты для стационарных характеристик очереди, а для системы М/М/1/оо/Ео в [47] — выражения для среднего периода отключения прибора. Много работ посвящено СМО с групповыми поступлениями заявок. Так, системы класса M^/G/1/oo/E рассмотрены в [52,57-59,69,82]. Как уже упоминалось выше, в [82] рассматривается система с повторными отключениями с различными ФР для длительности каждого последующего отключения. Для этой СМО выведены производящая функция (ПФ) распределения длины очереди и преобразование Лапласа-Стилтьеса (ПЛС) времени ожидания. Основным значимым результатом в [57] являются ПЛС периода занятости и времени цикла при 9 — 0,1. Кроме того, в работе [84] при исследовании системы M^/G/1/oo/E было введено расширение исчерпывающей схемы отключений, в которой окончание отключения происходило по достижению или превышению длинной очереди заданного значения. Позже такую схему отключения стали называть пороговой (threshold policy [78] или /V-policy) по аналогии со схожей схемой при отложенном обслуживании.
Рассматривались также системы с групповым обслуживанием [62,98].
В частности в [98] рассматривалось пороговое групповое обслуживание с отключением прибора при длине очереди меньше нижнего порога обслуживания. В [98] для этой СМО найдено стационарное распределение вложенной цепи Маркова, а в [62] эти результаты были уточнены с учётом проблемы первого преодоления порога [46].
Кроме того, проводились исследования систем с несколькими приборами. Так СМО класса M/M/N/oo/E рассматривались в работах [77, 89,97], причём в первых двух было выведено матрично-геометрическое выражение для длины очереди, в третьей — такой же результат для системы с групповым обслуживанием, аналогичным рассмотренному в [98]. Следует также отметить, что в [77] приводятся некоторые результаты для времени ожидания заявок и периода занятости СМО.
Для систем с конечной ёмкостью и исчерпывающей схемой отключения был также получен целый ряд результатов [5,10,15-17,29,53,61,79,83, 96]. Для СМО M/G/1/r/Eo в работе [83] получено стационарное распределение вероятностей состояний для произвольных моментов времени и для вложенной цепи Маркова и связь этих распределений со случаем с бесконечной очередью, а кроме того найдено ПЛС времени ожидания и занятости системы. При этом данные результаты для проведения вычислений требуют дополнительных математических преобразований. В работе [5] за счёт применения для анализа аналогичной СМО линейчатого марковского процесса авторам удалось избавиться от этого недостатка. Для этой же СМО в [29,61] для стационарных характеристик также выведены некоторые результаты, а в [17] рассмотрена аналогичная система с несколькими типами заявок и вероятностным отключением прибора Mk\Gk\l\r\Ee. В работе [96] для системы M^/G/l/r/E0 найдена вероятность потерь заявок при поступлении и произведено сравнение с вероятностью потерь в системе с групповым обслуживанием GJ/M^/1/r/Eo.
Рассматривались и более сложные с аналитической точки зрения СМО этого класса. Система РН/РН/і/г/Eq с распределением фазового типа длительности отключения рассмотрена в работе [10]. Для этой
СМО выведен матричный алгоритм для вычисления стационарного распределения длины очереди в моменты поступления и обслуживания заявок и в произвольные моменты. Кроме того, получен результат для ПЛС стационарного распределения времени ожидания обслуживания, В работах [15,16] эти результаты были обобщены для случая вероятностного управления повторными отключениями РН/РН/1/г/Е$. СМО МЛР/G/l/r/Eo исследовалась в работе Blondia [53] с помощью аппарата процессов марковского восстановления. Однако, результаты полученные в [53] для стационарного распределения длины очереди и ПЛС распределения времени ожидания мало пригодны для практических расчётов. В диссертации для анализа данной СМО используется алгоритмический подход с применением аппарата линейчатых марковских процессов. В результате был получен матричный рекуррентный алгоритм для рассчёта стационарного распределения длины очереди и других характеристик системы.
Были также исследованы системы с прогулками, функционирующие в дискретном времени. Так в монографии по СМО с дискретным временем [109] Takagi рассмотрел систему Geox/G/1/оо/Ев, в — 0,1, и получил выражения для распределения вероятностей длины очереди в терминах производящей функции. Эти результаты были обобщены в [67] для систем Geox/G/l/oo с исчерпывающей и ограниченной по времени или количеству обслуживаемых заявок дисциплин отключения прибора. В работе [114] к системе GI/Geo/1/oo/EQ был применён матрично-геометрический метод, что позволило получить явные выражения для стационарного распределения длины очереди и времени ожидания. Для СМО DMAP/G/1/oo/Eq и DMAP/G/1/r/Eo в работе [66] были выведены выражения для следующих характеристик выходящего потока: распределение длительности промежутков между моментами окончания обслуживания; совместное распределение длительностей последовательных промежутков между окончаниями обслуживания; распределение продолжительности периода простоя (прогулки).
Опустим здесь подробный обзор работ по СМО со схемами отключения прибора, отличными от исчерпывающей, т.к. они далеки от тематики диссертации.
Актуальность работы. В наше время информация является одним из наиболее важных ресурсов, поэтому решения в области информационных технологий подвергаются тщательному анализу и оптимизации с применением математического моделирования. Для исследования по меньшей мере двух составляющих ИТ — обработки и передачи информации — широко применяется аппарат теории массового обслуживания, предметом изучения которой являются системы массового обслуживания и сети массового обслуживания. При этом для адекватного построения моделей необходимо учитывать специфические свойства исследуемых систем, относящиеся в основном к числу обслуживающих устройств, количеству и объему накопителей, процессу обработки заявок, дисциплине обслуживания и пр.
Одна из важнейших особенностей современных приложений, затрудняющая анализ систем массового обслуживания, связана с широким применением технологий с приоритезацией обслуживания заявок в зависимости от их класса. Приоритезация обслуживания применяется как в системах обработки информации и управления — в основном для обеспечения выполнения отдельных задач в режиме реального времени, либо, наоборот, в периоды простоя системы, так и в телекоммуникационных системах — для обеспечения качества передачи некоторых видов трафика в высокопроизводительных сетях и для передачи отдельных классов сообщений в фоновом режиме (например, сигнального трафика). В частности, интерес представляют системы с фоновыми заявками — заявками, обладающими низшим приоритетом, и запас которых неограничен, т.е. они всегда есть в наличии для поступления на обслуживание.
В последнее время системы с приоритезацией обслуживания подверглись интенсивному исследованию, что демонстрирует практическую
необходимость в дальнейшем развитии аналитических решений в этой области. Однако, до сих пор редко и недостаточно полно при их рассмотрении учитывалась другая особенность современных приложений — зависимый входящий поток. В телекоммуникационных сетях это явление связано прежде всего с тем, что по одному каналу связи с помощью пакетного мультиплексирования передаётся информация по соединениям, установленным между несколькими источниками и приёмниками в сети. Кроме того, имеет место явление так называемого взрывного или пульсирующего трафика. Также не рассматривались модели с фоновыми заявками и зависимым обслуживанием.
Исследования СМО ограниченной ёмкости с фоновыми заявками и зависимыми входящим потоком и обслуживанием ранее не проводились в литературе, а результаты для систем с зависимым входящим потоком и независимым обслуживанием получены в виде, для которого затруднена разработка эффективного вычислительного алгоритма, поэтому тема диссертационной работы является актуальной.
Целью диссертационной работы является анализ однолинейной системы массового обслуживания конечной емкости с фоновыми заявками, разработка эффективных алгоритмов для вычисления стационарных вероятностей состояний, а также получение аналитических закономерностей и выражений для основных показателей производительности для следующих типов нагрузки:
марковского потока основных заявок и марковского обслуживания заявок обоих типов (система (MAP,ST)/(MSP,MSP)/l/r);
дискретного марковского потока основных заявок и дискретного марковского обслуживания основных и фоновых заявок (система (DMАР, ST)/{DMSP, DMSP)/l/r)-
марковского потока основных заявок и произвольного обслужива-
ния основных и фоновых заявок (система (MAP, ST)((G, G)/l/r).
Научная новизна и результаты, выносимые на защиту. Все
основные результаты диссертации являются новыми и состоят в следующем:
Предложен математический метод анализа процесса очереди в СМО (MAP,ST)/(MSP,MSP)/l/r и разработан алгоритм расчета стационарных вероятностей состояний, а также получены выражения для основных стационарных показателей производительности системы.
Разработаны математический метод и алгоритм для вычисления стационарных вероятностей состояний СМО (MAP,ST)/(MSP,MSP)/l/r, функционирующей в дискретном времени, и получены выражения для основных стационарных показателей производительности системы.
Предложен алгоритмический подход и разработан алгоритм для вычисления стационарных вероятностей состояний СМО (MAP, ST)j(G, G)/l/r и выведены выражения для основных стационарных показателей ее производительности.
Методы исследования. В диссертационной работе применяются методы теории вероятностей, теории случайных процессов и теории массового обслуживания.
Обоснованность научных положений. Все полученные в диссертации теоретические результаты обоснованы строгими математическими доказательствами.
Практическая ценность работы. Полученные в диссертации результаты могут быть использованы при аналитическом моделировании
информационно-вычислительных сетей, локальных сетей, телекоммуникационных сетей и, в частности, при моделировании сетей с общим каналом сигнализации на основе системы ОКС 7, систем управления базами данных с оперативной реорганизацией данных и сетей передачи данных с поддержкой качества обслуживания (например, ATM, MPLS). Результаты диссертации, полученные в достаточно общих предположениях относительно характеристик входящего потока и процесса обслуживания основных и фоновых заявок на приборе, позволяют строить более адекватные модели реальных сетевых систем и предоставляют их проектировщикам математический инструментарий, применимый для широкого класса систем.
Реализация результатов работы. Исследование систем массового обслуживания конечной емкости с фоновыми заявками проводилось в рамках гранта Российского фонда фундаментальных исследований № 02-07-90147 "Математические методы и программное обеспечение моделирования информационных, вычислительных и телекоммуникационных систем".
Апробация работы. Материалы диссертации докладывались на международной конференции "12th International Conference on Analytical and Stochastic Modelling Techniques and Applications" (Рига, 2005 г.); на XLI Всероссийской конференции по проблемам математики, информатики, физики и химии (Москва, 2005 г.); на научном семинаре по теории массового обслуживания кафедры теории вероятностей и математической статистики РУДН; на научном семинаре по проблемам передачи информации кафедры телекоммуникационных сетей и систем МФТИ.
Публикации. По материалам диссертации опубликовано 5 работ, из них 3 в центральной печати.
Структура и объем работы. Диссертация состоит из введения, трёх глав, заключения и списка литературы. Каждая глава состоит из параграфов. Формулы нумеруются отдельно внутри каждой главы с указанием её номера. Теоремы, леммы, рисунки и таблицы имеют сквозную нумерацию.
В первой главе рассматривается однолинейная система массового обслуживания с марковским потоком основных заявок (1-заявок) и фоновыми заявками (2-заявками), поступающими из бункера, в котором их запас не ограничен, т.е. поток фоновых заявок является насыщенным. Для основных заявок имеется накопитель ограниченной емкости г. Процессы обслуживания обоих типов заявок являются марковскими. Данная СМО в обозначениях Кендалла классифицируется как (MAP,ST)/(MSP,MSP)/l/r. Для определенности предполагается, что выбор основных заявок из очереди в накопителе осуществляется в соответствии с дисциплиной FCFS.
Дисциплина обслуживания предполагает относительный приоритет 1-заявок по сравнению с 2-заявками. При этом после ухода из прибора некоторой 1-заявки на обслуживание поступает следующая 1-заявка из очереди основных заявок, ожидающих в накопителе. Если накопитель пуст, то из бункера на прибор поступает 2-заявка. При поступлении 1-заявки в систему во время обслуживания 2-заявки вновь пришедшая заявка становится в очередь, не прерывая обслуживания фоновой заявки, и поступает на прибор сразу после ухода ее из системы.
Подробное описание рассматриваемой СМО приводится в 1.
В 2 вводится марковский процесс, моделирующий стохастическое поведение исследуемой СМО.
В 3 составляется СУР относительно вектора стационарных вероятностей состояний СМО.
В 4 формулируется и доказывается теорема о рекуррентном матричном алгоритме решения СУР.
В 5 выводятся основные показатели производительности системы,
наиболее часто используемые в приложениях, таких как стационарные интенсивности: принятого в систему, потерянного на входе системы, и обслуженного ей потоков основных заявок, обслуженного потока фоновых заявок, а также стационарную вероятность потери основных заявок и т.д.
В 6 получены соотношения, связывающие стационарное распределение состояний СМО, наблюдаемой в произвольные моменты времени со стационарными вероятностями состояний системы, рассматриваемой в моменты непосредственно перед поступлениями 1-заявок и сразу после них, а также по моментам окончания обслуживания г-заявок (выхода г-заявок) непосредственно перед выходом и сразу после него.
В 7 формулируется и доказывается теорема относительно ФР времени ожидания основных заявок, поступающих в рассматриваемую систему, функционирующую в стационарном режиме, и обслуживаемых в порядке их поступления.
В 8 приводятся результаты численного исследования СМО с помощью системы имитационного моделирования GPSS и вычислительной программы, использующей аналитические результаты, полученные в первой главе.
В главе 2 проанализирован дискретный аналог СМО (MAP,ST)j (MSP, MSP)/l/r - система (DMАР, ST)/(DMSP, DMSP)/l/r, функционирующая в дискретном времени.
Как и в СМО, рассмотренной в главе 1, источником заявок фонового потока (2-заявок) является так называемый бункер, в котором запас заявок не ограничен. При этом фоновая заявка поступает на прибор лишь в случае, когда после завершения обслуживания заявки система свободна, т.е. накопитель пуст и не закончилась генерация новой основной заявки. Если после окончания обслуживания фоновой заявки система снова будет пуста, то на прибор немедленно поступает следующая фоновая заявка из бункера. Таким образом, процесс обслуживания фоновых заявок продолжается до тех пор, пока по завершению обслуживания очередной
фоновой заявки в СМО не окажется хотя бы одна основная заявка. При этом поступившая основная заявка не прерывает обслуживания фоновой заявки. Другими словами, основные заявки имеют относительный приоритет при обслуживании перед фоновыми заявками.
Рассматриваемая во второй главе система подробно описывается в
Для построения корректной математической модели вводится порядок следования событий, происходящих за один такт. При этом считается, что все события в системе происходят в моменты времени кратные такту, и принимается следующий порядок событий на такте:
в момент непосредственно перед окончанием такта обслуженная на такте заявка покидает систему;
в момент окончания такта, если прибор не занят и очередь не пуста, то основная заявка из накопителя, выбранная в соответствии с дисциплиной FCFS, поступает на прибор;
в момент сразу после окончания такта в систему поступает 1-заявка (если на такте закончилась сё генерация) и помещается в накопитель, если прибор занят, или на прибор, если прибор свободен; если на такте не окончилась генерация новой 1-заявки, и прибор в момент сразу после окончания такта не занят, то на прибор в этот момент поступает фоновая заявка.
В 2 вводится однородная цепь Маркова, моделирующая стохастическое поведение исследуемой СМО.
В 3 записывается СУР относительно вектора стационарных вероятностей состояний СМО и обосновывается её вывод.
В 4 к решению СУР применяется алгоритмический подход, формулируется и доказывается теорема о рекуррентном матричном алгоритме вычисления вектора стационарных вероятностей состояний СМО.
В 6 изучаются стационарные вероятности состояний системы, рассматриваемой в моменты непосредственно перед поступлениями 1-заявок и сразу после них. При этом исключаются из рассмотрения те
1-заявки, непосредственно перед поступлением которых (на одном такте) завершилось обслуживание заявки, находившейся на приборе.
В главе 3 рассматривается однолинейная СМО (MAP, ST)/G2/1/V, аналогичная системе, исследованной в главе 1, за исключением того, что длительности обслуживания обоих типов заявок независимы. При этом времена обслуживания j'-заявки имеют ФР Bj(x), j = 1, 2.
В 1 приводится подробное описание рассматриваемой СМО.
В 2 вводится линейчатый марковский процесс, описывающий стохастическое поведение рассматриваемой СМО, и записывается система дифференциальных уравнений, аналог СУР, для стационарного распределения плотности вероятностей состояний этого процесса.
В 3 формулируется и доказывается несколько теорем относительно решения СУР, описывающие матрично-рекуррентный подход для вычисления стационарного распределения вероятностей состояний системы.
В 4 выводятся основные показатели производительности системы, такие как стационарные интенсивности: принятого в систему, потерянного на входе системы, и обслуженного ей потоков основных заявок, а также стационарную вероятность потери основных заявок.
В 5 исследуются стационарная плотность вероятности состояния и стационарная вероятность состояния системы, рассматриваемой непосредственно перед поступлением 1-заявки.
На основе результатов, полученных в 5, в 6 определяется ПЛС ФР времен ожидания o>i(s) и пребывания <>i(s) 1-заявок в системе при дисциплине обслуживания FCFS.
Стохастическая модель системы
Состояние процесса X(t) = (j, п, А;, г) для некоторого момента t следующим образом соответствует состоянию СМО: в данный момент времени і процесс генерации 1-заявок находится на фазе j} на приборе обслуживается г-заявка, в системе находится к 1-заявок, и процесс обслуживания г-заявок находится на фазе п.
Для пояснения вывода СУР воспользуемся схемой переходов процесса X(t) (см. рисунок) на интервале (t,t + А), где Д — малый промежуток времени. Для этого введём следующие обозначения: для некоторой квадратной матрицы Q — (&;,uj)vu,=rn обозначим Qdg матрицу Qdg = diag(qn, g22, , Япп) и Qdg матрицу QQdg = Q - Qdg, Также для упрощения записи условимся опускать на схеме знак о(А).
Поясним сначала вывод третьего уравнения системы для фиксированного к = 2, г с помощью схемы Рис. 1.3. В подмножество состояний Я4д система может попасть из подмножества Л -ід за счёт поступления 1-заявки. Интенсивность поступления новой 1-заявки определяется матрицей N, при этом матрица N также определяет и фазу, с которой начнётся генерация следующей 1-заявки.
Возможен также переход системы в подмножество состояний Л д из подмножества Xk,2 за счёт окончания обслуживания 2-заявки. Интенсивность обслуживания в данном случае определяется вектором д2, при этом фаза, с которой начнется обслуживание следующей 1-заявки, определяется в соответствии с вектором начальных вероятностей /Зх. Кроме того, система может остаться в подмножестве состояний Л д, что может осуществиться двояким образом. В первом случае за время А не закончится прохождение текущих фаз генерации заявки и обслуживания. Эту возможность отражают элементы главной диагонали матрицы Л ф Mi, взятые с обратным знаком. Во втором случае за данный промежуток времени могут произойти изменения фаз текущих процессов генерации и обслуживания (без окончания генерации и обслуживания соответствен но). Такие изменения могут произойти с интенсивностью, определяемой элементами матрицы Л Мі, не лежащими на главной диагонали.
Аналогичное уравнение для к — R получается согласно схеме Рис. 1.5. При этом отличие от случая к — 2, г заключается в том, что приход новой 1-заявки также оставляет систему в исходном макросостоянии (так как поступившая 1-заявка теряется из-за переполнения накопителя). Кроме того, во время обслуживания 1-заявки в системе не может находиться более R 1-заявок, а во время обслуживания 2-заявки — не более г 1-заявок, поэтому система может перейти в макросостояние Лдд только из макросостояния XTt± за счет поступления новой 1-заявки.
Путём аналогичных рассуждений на основе схем Рис. 1.1 и Рис. 1.2 получаются соответственно первое и второе уравнения системы. В свою очередь, схемы Рис. 1.4 и Рис. 1.6 служат для пояснения вывода четвёртого уравнения системы.
Стационарное распределение времени ожидания основных заявок
Доказательство. Доказательство теоремы 3 проводится по аналогии с доказательством теоремы 2, рассматривая интервал (t,t + Д) и выписывая условную вероятность для СМО, функционирующей в стационарном режиме, находиться в состоянии х Є X при условии поступления 1-заявки за Д с последующим переходом к пределу при Д — 0.
Получим теперь стационарные вероятности состояний рассматриваемой системы по моментам окончания обслуживания г-заявок (выхода г-заявок) непосредственно перед выходом {я Да;), х Є X} и сразу после него {тГрДж), х Є X]. Для записи выражений для этих распределений будем использовать векторы 7Г Д,г), аналогичные по структуре векторам p .
Соотношения (1.26) доказываются с помощью рассуждений, аналогичных тем, которые были проведены при доказательстве теоремы 2 и с учетом соотношений (1.22) и (1.23). Соотношения для (1.27) и (1.28) очевидны.
Будем рассматривать СМО (MAP, ST)/{MSP, MSP)/l/r, функционирующую в стационарном режиме, и изучим время ожидания основных заявок, обслуживаемых в порядке их поступления.
Обозначим через W(t) стационарную функцию распределения (ФР) времени ожидания начала обслуживания произвольной 1-заявки при условии, что она принята в систему, а через W(t\(j,n,k,i)) — условную ФР ожидания начала обслуживания 1-заявки, которая поступила в систему, находящуюся в состоянии (j,n,k,i) Є X. Обозначим через w(s) ПЛС W(t), а через w(t\(j,n, к, і)) — ПЛС W(t\(j,n, к, і)). Введём вектор W&(i) {W(t\\ k,i),...,W{t\l,muKi),...,W{t\UrahKi), а через uJk,i{s) обозначим ПЛС этого вектора. По формуле полной вероятности получаем 2 r+u(2)-l ш{8) = —— J2 Е л"(М)« , М. (1-29) PL i=l fc=u(2-i) Если непосредственно перед поступлением 1-заявки система находится в состоянии (j,n, к,і), то 1-заявка начнет обслуживаться после того, как завершится обслуживание г-заявки, находящейся на приборе, и систему покинут к — и(2 — г) 1-заявок, ожидающих обслуживания в накопителе. Нетрудно видеть, что если на приборе находится 1-заявка, т. е. г = 1, то LJkA )-(himi)(si--Mlr1isi(si-Mlr1]k 1fj,u к = Т . (1.30) Если же на приборе обслуживается фоновая заявка, т. е. г = 2, то ш02(я) - (1/ Im2) (si - M2)-1fi2, ь кМ = (h In ) (si - M2) lіьРК&І - M lS sI - MO"1] "1 , fe = l,r-l. (1.31) На основании проведенных выше рассуждений, объединяя формулы (1.29)-(1.31), приходим к результату, который сформулируем в виде следующей теоремы. Теорема 5. Для СМО (MAP,ST)/(MSP,MSP)/l/r/FCFS ПЛС ФР времени ожидания основной заявки, принятой в систему, имеет вид Ф) = Т —{Е А (Ь і) (її щіизд) -1/ + -(0,2)(1(0/ ) 2+ 7—1 + Е А ( 2) (!i « 7bA»2/3fГі іГ!) "1 }, fc=i где T; = (s/ — Mj)_1, г — 1,2, а вероятности 7Гд(к,і) определяются формулой (1.25). 8. Результаты имитационного моделирования и численных исследований Для численного исследования рассматриваемой СМО были реализованы в виде программ в системе программирования Delphi 6 алгоритмы рассчёта стационарного распределения вероятностей состояний системы, описанные в лемме 1 (алгоритм 1) и в теореме 1 (алгоритм 2). Прежде, чем переходить к описанию результатов исследований проведём сравнение вычислительной эффективности использованных алгоритмов. В таблице 1.1 приведены времена выполнения Т рассчётов по алгоритмам 1 и 2 для системы с различным объёмом накопителя г, поведение которых задано матрицами Л и N порядка I - 3 и матрицами М 5 , г — 1, 2, порядка mi — 4. Кроме того, указана мощность множества состояний марковского процесса {X(t)} t 0} и количество элементов Nmlmory-, j = 1,2 матрицы Р, обрабатываемых при осуществлении вычислений по алгоритму j.
Из таблицы и формул видно, что для алгоритма 2 требуется выделять значительно меньше (в приведённом примере — около 50%) оперативной памяти, чем для алгоритма 1. Соответственно при проведении вычислений на ЭВМ с некоторым объёмом памяти алгоритм 2 позволит получить результаты для более сложных систем. При этом время вычисления также значительно ниже при использовании алгоритма, т.к. в операциях участвует меньшее количество переменных.
Дальнейшие численные исследования будем проводить с помощью алгоритма 2, т.к. это позволит получать результаты для более широкого диапазона параметров.
С учётом специфики рассматриваемой системы интерес представляют следующие исследования. Зависимость стационарных характеристик производительности системы от объёма накопителя при фиксированных нагрузке (входящем потоке) и обслуживании. Влияние зависимости во входящем потоке и процессах обслуживания на стационарные характеристики системы.
Стохастическая модель системы
Рассматривается однолинейная СМО с потерями, функционирующая в дискретном времени с фиксированной величиной такта h, h 0. На систему поступают два потока заявок: основной поток заявок, которые будем называть 1-заявками, и фоновый поток заявок, называемых 2-заявками. 1-заявки ожидают начала обслуживания в накопителе ограниченной емкости г, 1 г со,
Поток 1-заявок является дискретным марковским (Discrete Markov Arrival Process — DMAP) [12], задаваемым матрицами AQ И А І порядка I, элементы {Ай)і. и {А\){- которых задают переходы цепи Маркова (ЦМ), управляющей генерацией 1-заявок (в дальнейшем, для краткости, мы иногда будем говорить просто о процессе генерации 1-заявок), с фазы генерации і на фазу генерации j, не сопровождающиеся и сопровождающиеся поступлением новой заявки, соответственно.
Получив векторы а\ и р , можно вычислить вероятность а поступления заявки за такт: а — р а\. Как и в СМО, рассмотренной в главе 1, источником заявок фонового потока (2-заявок) является так называемый бункер, в котором запас заявок не ограничен. При этом фоновая заявка поступает на прибор лишь в случае, когда после завершения обслуживания заявки система свободна, т.е. накопитель пуст и не закончилась генерация новой основной заявки. Если после окончания обслуживания фоновой заявки система снова будет пуста, то на прибор немедленно поступает следующая фоновая заявка из бункера. Таким образом, процесс обслуживания фоновых заявок продолжается до тех пор, пока по завершению обслуживания очередной фоновой заявки в системе не окажется хотя бы одна основная заявка. При этом поступившая основная заявка не прерывает обслуживания фоновой заявки. Другими словами, основные заявки имеют относительный приоритет при обслуживании перед фоновыми заявками.
Процессы обслуживания г-заявок также, как и процесс поступления основных заявок, являются марковскими (Discrete Markov Service Processes — DMSP) [12] и задаются матрицами BQ И В\г) порядка 77, і = 1,2. Элементы f BQ J и [ В\ I этих матриц задают ве-роятности перехода обрывающихся ЦМ, управляющих процессами обслуживания (основных и фоновых) заявок, с фазы обслуживания j на фазу обслуживания s без завершения обслуживания или с завершением обслуживания заявки на приборе, соответственно. Кроме того, задаются векторы ff — (Ді,..,, Дт.), і = 1,2, элементы которых определяют вероятности выбора фазы обслуживания, с которой начинается процесс обслуживания новой заявки при смене типа заявки на приборе.
В дальнейшем будем предполагать, что матрицы А и В (г) — щ) __ щ\ і — 1,2, неразложимы, а матрицы А\ и В\ , і — 1, 2, отличны от нулевых. Также в дальнейшем будет использоваться следствие этих условий — невырожденность матриц I) — Аі и
Для построения корректной математической модели нам необходимо ввести порядок следования событий, происходящих за один такт. Бу дем считать, что все события в системе происходят в моменты времени nh, п 1,2,..., кратные такту. При этом п-и тактом будем называть промежуток времени ((n — l)h,nh] и примем следующий порядок событий на такте п: в момент nh — О обслуженная на такте п заявка покидает систему; в момент nh, если прибор не занят и очередь не пуста, то основная заявка из накопителя, выбранная в соответствии с дисциплиной FCFS, поступает на прибор; в момент nh + 0 в систему поступает 1-заявка (если на такте п закончилась её генерация) и помещается в накопитель, если прибор занят, или на прибор, если прибор свободен; если на такте п не окончилась генерация новой 1-заявки, и прибор в момент пЛ + 0 не занят, то на прибор в этот момент поступает фоновая заявка.
Описанную СМО в обозначениях Кендалла будем классифицировать как {DMАР, ST)/{DMSP, DMSP)fl(r (символ "ST" - сокращение от английского saturated). Данная система является дискретным аналогом системы (MAP,ST)/(MSP,MSP)/l/r, рассмотренной в предыдущей главе.
Некоторые соотношения для показателей производительности
Обозначим через А интенсивность потока 1-заявок, принятого в систему, через Ах, — потерянного на входе системы и через Адд — обслуженного системой. В силу равенства (3.41) интенсивность А поступающего на систему потока 1-заявок, определяется равенствами А = р гЛ - ртЛ. (3.43) Рассмотрим теперь вектор р. — рг. Заметим, что г-я. компонента этого вектора есть стационарная вероятность того, что процесс генерации 1-заявок находится на фазе г и в накопителе находится по крайней мере одно свободное место, т.е. система доступна для поступающих на неё 1-заявок. Тогда для интенсивности А принятого потока 1-заявок получаем следующее выражение: АЛ - (рТ - РП Л. (3.44) Так как в стационарном режиме А,і — Аді, то из (3,44) следует, что Аид = (рТ - РП Л. (3.45) Основываясь на эргодичности процесса {(), t 0}, можно выписать другое выражение для Адд : где jii — интенсивность обслуживания основных заявок. Далее учитывая, что А — А + А , из (3.43) и (3.44) получаем А = р?А. (3.46) Теперь можно определить вероятность потери 1-заявки 7Г в стационарном режиме функционирования СМО: тг = . (3.47) Выражение (3.47) для вероятности потери с учётом (3.46) можно записать в виде тг - ipSTA. (3.48) Рассмотрим теперь равенства (3.37). Умножая обе части этих равенств справа на А и суммируя их по всем значениям к, получим А-р?А = д.д. (3.49) Отсюда с учётом (3.48) и (3.30) получаем соотношение А(1-тг) = №1, (3.50) отражающее равенство интенсивностей принятого в систему и обслуженного ей потоков 1-заявок. Равенство (3.50) можно использовать для контроля расчётов стационарного распределения вероятностей состояний системы, осуществляемых с помощью полученного выше алгоритма.
В данной главе проанализирована однолинейная СМО с марковским потоком основных заявок и насыщенным потоком фоновых заявок (запас которых не ограничен). Обслуживание обоих типов заявок рекуррентное. Для основных заявок имеется накопитель конечной емкости, и они обслуживаются с относительным приоритетом по сравнению с фоновыми заявками.
В этой главе получены следующие результаты. 1. Разработан матрично-рскуррентный подход для вычисления стационарного распределения вероятностей состояний системы. 2. Выведены выражения для основных показателей производительности системы, таких как стационарные интенсивности: принятого в систему, потерянного на входе системы и обслуженного ей потоков основных заявок, а также для стационарной вероятности потери основных заявок. 3. Получены стационарные плотности вероятностей и вероятности состояний системы, рассматриваемой непосредственно перед поступлением 1-заявки. 4. Выведены выражения для ПЛС ФР времени ожидания основной заявкой заявкой начала обслуживания и ПЛС ФР времени пребывания основной заявки в системе. ЗАКЛЮЧЕНИЕ
В диссертационной работе проведено исследование трёх типов однолинейных СМО с фоновыми заявками и ограниченным накопителем для основных заявок. Рассмотрены как системы, функционирующие в непрерывном времени, так и система, функционирующая в дискретном времени. Входящий поток основных заявок является марковским (дискретным марковским в случае дискретного времени). Процесс обслуживания обоих типов заявок также является марковским. Кроме того, для СМО, функционирующей в непрерывном времени, рассмотрен рекуррентный процесс обслуживания с произвольной ФР длительности обслуживания.
