автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Исследование однолинейной системы массового обслуживания конечной ёмкости с фоновыми заявками

ВВЕДЕНИЕ

1 АНАЛИЗ СИСТЕМЫ С МАРКОВСКИМ ПОТОКОМ И МАРКОВСКИМ ОБСЛУЖИВАНИЕМ В НЕПРЕРЫВНОМ ВРЕМЕНИ

§ 1. Описание системы.

§ 2. Стохастическая модель системы.

§ 3. Система уравнений равновесия.

§ 4. Решение уравнений равновесия.

§ 5. Основные показатели производительности системы

§ 6. Стационарные вероятности состояний системы по моментам поступления основных заявок и выхода обслуженных заявок.

§ 7. Стационарное распределение времени ожидания основных заявок.

§ 8. Результаты имитационного моделирования и численных исследований.

Выводы.

2 АНАЛИЗ СИСТЕМЫ С МАРКОВСКИМ ПОТОКОМ И МАРКОВСКИМ ОБСЛУЖИВАНИЕМ В ДИСКРЕТНОМ ВРЕМЕНИ

§ 1. Описание системы.

§ 2. Стохастическая модель системы.

§ 3. Система уравнений равновесия.

§ 4. Решение уравнений равновесия.

§ 5. Стационарные вероятности состояний системы по моментам поступления основных заявок.

Выводы.

3 АНАЛИЗ СИСТЕМЫ С МАРКОВСКИМ ПОТОКОМ И ПРОИЗВОЛЬНЫМ ВРЕМЕНЕМ ОБСЛУЖИВАНИЯ

ОСНОВНЫХ И ФОНОВЫХ ЗАЯВОК

§ 1. Описание системы.

§ 2. Стохастическая модель

§ 3. Решение уравнений равновесия.

§ 4. Некоторые соотношения для показателей производительности

§ 5. Стационарные вероятности по моментам поступления основных заявок

§ 6. Стационарное распределение времени ожидания основных заявок при дисциплине РСРБ.

Выводы.

Развитие человечества всегда было связано с информацией: её накоплением и хранением, обменом и переработкой. Многовековое развитие информационных технологий взаимообусловливало параллельное развитие производства, науки, искусства и образования [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. M. и др. [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, ИЗ], поэтому терминологию для этих систем удобно использовать для классификации систем с отключениями заявок [51,73,105,108]:

• exhaustive (исчерпывающая) схема с отключением прибора после опустошения прибора;

• decrementing (убывающая) схема с отключением прибора после уменьшения количества заявок в системе на одну по отношению к моменту окончания предыдущего отключения;

• gated (вентильная) схема, подразумевающая обслуживание только заявок, находившихся в очереди на момент отключения прибора;

• limited (ограничивающая) схема с отключением прибора после опустошения прибора или после окончания обслуживания некоторого заданного числа заявок;

• ordinary (единичная) схема — частный случай ограничивающей схемы с обслуживанием не более одной заявки перед отключением.

Заметим, что рассматривались также и другие процедуры отключения прибора, например, совмещающие признаки, приведённых выше схем [86,87]. Кроме того, может задаваться различное поведение прибора, если после окончания отключения система оказывается пустой. В этом случае происходит либо повторное отключение прибора, либо прибор остаётся включенным, но простаивает [57]. В [82], например, задаётся поведение системы после n-го повторного отключения прибора функцией распределения длительности следующего отключения, зависящей от п.

Для удобства дальнейшего обзора работ по исследованию систем с прогулками определим следующую модификацию классификации Кен-далла. Будем задавать СМО набором символов А\В\С\Т>\£, где Л указывает тип входящего потока заявок, В — тип обслуживания, С — число приборов, V — емкость накопителя, а дополнительный символ £ указывает схему отключения прибора. В качестве основы для символа S будем использовать первые буквы английских названий соответствующих дисциплин, т.е. Е — исчерпывающая, D — убывающая, G — вентильная, Ln — ограничивающая (N — число заявок, подлежащих обслуживанию до начала следующего отключения прибора), О — единичная. В некоторых случаях дисциплина имеет вероятностную схему окончания циклов повторяющихся отключений, в этом случае будем добавлять к символу, обозначающему тип дисциплины, индекс 9, где 9 (0 < 9 < 1) — вероятность перехода прибора в режим ожидания (простоя).

Наибольшее количество результатов приходится на СМО с исчерпывающей схемой отключения с повторными отключениями (дисциплина Е0). В работах [88,90,104,106,108] для системы M/G/1/oo/Eq получены некоторые результаты для стационарных характеристик очереди, а для системы M/M/1/oo/Eq в [47] — выражения для среднего периода отключения прибора. Много работ посвящено СМО с групповыми поступлениями заявок. Так, системы класса M^/G/1/oo/E рассмотрены в [52,57-59,69,82]. Как уже упоминалось выше, в [82] рассматривается система с повторными отключениями с различными ФР для длительности каждого последующего отключения. Для этой СМО выведены производящая функция (ПФ) распределения длины очереди и преобразование Лапласа-Стилтьеса (ПЛС) времени ожидания. Основным значимым результатом в [57] являются ПЛС периода занятости и времени цикла при 9 — 0,1. Кроме того, в работе [84] при исследовании системы MW/G/1/oo/E было введено расширение исчерпывающей схемы отключений, в которой окончание отключения происходило по достижению или превышению длинной очереди заданного значения. Позже такую схему отключения стали называть пороговой (threshold policy [78] или iV-policy) по аналогии со схожей схемой при отложенном обслуживании.

Рассматривались также системы с групповым обслуживанием [62,98].

В частности в [98] рассматривалось пороговое групповое обслуживание с отключением прибора при длине очереди меньше нижнего порога обслуживания. В [98] для этой СМО найдено стационарное распределение вложенной цепи Маркова, а в [62] эти результаты были уточнены с учётом проблемы первого преодоления порога [46].

Кроме того, проводились исследования систем с несколькими приборами. Так СМО класса М/М/Ы/оо/Е рассматривались в работах [77, 89,97], причём в первых двух было выведено матрично-геометрическое выражение для длины очереди, в третьей — такой же результат для системы с групповым обслуживанием, аналогичным рассмотренному в [98]. Следует также отметить, что в [77] приводятся некоторые результаты для времени ожидания заявок и периода занятости СМО.

Для систем с конечной ёмкостью и исчерпывающей схемой отключения был также получен целый ряд результатов [5,10,15-17,29,53,61,79,83, 96]. Для СМО М/С/1/г/Ео в работе [83] получено стационарное распределение вероятностей состояний для произвольных моментов времени и для вложенной цепи Маркова и связь этих распределений со случаем с бесконечной очередью, а кроме того найдено ПЛС времени ожидания и занятости системы. При этом данные результаты для проведения вычислений требуют дополнительных математических преобразований. В работе [5] за счёт применения для анализа аналогичной СМО линейчатого марковского процесса авторам удалось избавиться от этого недостатка. Для этой же СМО в [29,61] для стационарных характеристик также выведены некоторые результаты, а в [17] рассмотрена аналогичная система с несколькими типами заявок и вероятностным отключением прибора Мк\Ск\1\г\Ед. В работе [96] для системы найдена вероятность потерь заявок при поступлении и произведено сравнение с вероятностью потерь в системе с групповым обслуживанием а/М^/1/г/Е$.

Рассматривались и более сложные с аналитической точки зрения СМО этого класса. Система РН/РН/1/г/с распределением фазового типа длительности отключения рассмотрена в работе [10]. Для этой

СМО выведен матричный алгоритм для вычисления стационарного распределения длины очереди в моменты поступления и обслуживания заявок и в произвольные моменты. Кроме того, получен результат для ПЛС стационарного распределения времени ожидания обслуживания. В работах [15,16] эти результаты были обобщены для случая вероятностного управления повторными отключениями РН/РН/1/г/Ее. СМО МАР/0/1/г/Ео исследовалась в работе В1опсИа [53] с помощью аппарата процессов марковского восстановления. Однако, результаты полученные в [53] для стационарного распределения длины очереди и ПЛС распределения времени ожидания мало пригодны для практических расчётов. В диссертации для анализа данной СМО используется алгоритмический подход с применением аппарата линейчатых марковских процессов. В результате был получен матричный рекуррентный алгоритм для рассчёта стационарного распределения длины очереди и других характеристик системы.

Были также исследованы системы с прогулками, функционирующие в дискретном времени. Так в монографии по СМО с дискретным временем [109] Та1^1 рассмотрел систему Сеох/С/1/оо/Ев, в = 0,1, и получил выражения для распределения вероятностей длины очереди в терминах производящей функции. Эти результаты были обобщены в [67] для систем Сеох/С/1/со с исчерпывающей и ограниченной по времени или количеству обслуживаемых заявок дисциплин отключения прибора. В работе [114] к системе а/Сео/1/оо/был применён матрично-геометрический метод, что позволило получить явные выражения для стационарного распределения длины очереди и времени ожидания. Для СМО ОМАР/в/г/оо/Ео и ВМАР/С/1/г/Е0 в работе [66] были выведены выражения для следующих характеристик выходящего потока: распределение длительности промежутков между моментами окончания обслуживания; совместное распределение длительностей последовательных промежутков между окончаниями обслуживания; распределение продолжительности периода простоя (прогулки).

Опустим здесь подробный обзор работ по СМО со схемами отключения прибора, отличными от исчерпывающей, т.к. они далеки от тематики диссертации.

Актуальность работы. В наше время информация является одним из наиболее важных ресурсов, поэтому решения в области информационных технологий подвергаются тщательному анализу и оптимизации с применением математического моделирования. Для исследования по меньшей мере двух составляющих ИТ — обработки и передачи информации — широко применяется аппарат теории массового обслуживания, предметом изучения которой являются системы массового обслуживания и сети массового обслуживания. При этом для адекватного построения моделей необходимо учитывать специфические свойства исследуемых систем, относящиеся в основном к числу обслуживающих устройств, количеству и объему накопителей, процессу обработки заявок, дисциплине обслуживания и пр.

Одна из важнейших особенностей современных приложений, затрудняющая анализ систем массового обслуживания, связана с широким применением технологий с приоритезацией обслуживания заявок в зависимости от их класса. Приоритезация обслуживания применяется как в системах обработки информации и управления — в основном для обеспечения выполнения отдельных задач в режиме реального времени, либо, наоборот, в периоды простоя системы, так и в телекоммуникационных системах — для обеспечения качества передачи некоторых видов трафика в высокопроизводительных сетях и для передачи отдельных классов сообщений в фоновом режиме (например, сигнального трафика). В частности, интерес представляют системы с фоновыми заявками — заявками, обладающими низшим приоритетом, и запас которых неограничен, т.е. они всегда есть в наличии для поступления на обслуживание.

В последнее время системы с приоритезацией обслуживания подверглись интенсивному исследованию, что демонстрирует практическую необходимость в дальнейшем развитии аналитических решений в этой области. Однако, до сих пор редко и недостаточно полно при их рассмотрении учитывалась другая особенность современных приложений — зависимый входящий поток. В телекоммуникационных сетях это явление связано прежде всего с тем, что по одному каналу связи с помощью пакетного мультиплексирования передаётся информация по соединениям, установленным между несколькими источниками и приёмниками в сети. Кроме того, имеет место явление так называемого взрывного или пульсирующего трафика. Также не рассматривались модели с фоновыми заявками и зависимым обслуживанием.

Исследования СМО ограниченной ёмкости с фоновыми заявками и зависимыми входящим потоком и обслуживанием ранее не проводились в литературе, а результаты для систем с зависимым входящим потоком и независимым обслуживанием получены в виде, для которого затруднена разработка эффективного вычислительного алгоритма, поэтому тема диссертационной работы является актуальной.

Целью диссертационной работы является анализ однолинейной системы массового обслуживания конечной емкости с фоновыми заявками, разработка эффективных алгоритмов для вычисления стационарных вероятностей состояний, а также получение аналитических закономерностей и выражений для основных показателей производительности для следующих типов нагрузки:

• марковского потока основных заявок и марковского обслуживания заявок обоих типов (система (МАР, ЗТ)/(М8Р, М5Р)/1/г);

• дискретного марковского потока основных заявок и дискретного марковского обслуживания основных и фоновых заявок (система (.Б МАР, 5Т)/(£>М5Т, £>М5Р)/1/г);

• марковского потока основных заявок и произвольного обслуживания основных и фоновых заявок (система (MAP, ST)/(G, G)/l/r).

Научная новизна и результаты, выносимые на защиту. Все основные результаты диссертации являются новыми и состоят в следующем:

1. Предложен математический метод анализа процесса очереди в СМО (MAP, ST)/{MSP, MSP)/1/г и разработан алгоритм расчета стационарных вероятностей состояний, а также получены выражения для основных стационарных показателей производительности системы.

2. Разработаны математический метод и алгоритм для вычисления стационарных вероятностей состояний СМО (MAP,ST)/(MSP,MSP)/l/r, функционирующей в дискретном времени, и получены выражения для основных стационарных показателей производительности системы.

3. Предложен алгоритмический подход и разработан алгоритм для вычисления стационарных вероятностей состояний СМО (MAP, ST)/(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. Выведены выражения для основных показателей производительности системы, таких как стационарные интенсивности: принятого в систему, потерянного на входе системы и обслуженного ей потоков основных заявок, а также для стационарной вероятности потери основных заявок.

3. Получены стационарные плотности вероятностей и вероятности состояний системы, рассматриваемой непосредственно перед поступлением 1-заявки.

4. Выведены выражения для ПЛС ФР времени ожидания основной заявкой заявкой начала обслуживания и ПЛС ФР времени пребывания основной заявки в системе.

ЗАКЛЮЧЕНИЕ

В диссертационной работе проведено исследование трёх типов однолинейных СМО с фоновыми заявками и ограниченным накопителем для основных заявок. Рассмотрены как системы, функционирующие в непрерывном времени, так и система, функционирующая в дискретном времени. Входящий поток основных заявок является марковским (дискретным марковским в случае дискретного времени). Процесс обслуживания обоих типов заявок также является марковским. Кроме того, для СМО, функционирующей в непрерывном времени, рассмотрен рекуррентный процесс обслуживания с произвольной ФР длительности обслуживания.

Выполненные исследования позволили получить новые результаты, перечисленные ниже.

1. Для однолинейной СМО (MAP, ST)/(MSP, MSP)/l/r с фоновыми заявками и зависимыми входящим потоком и обслуживанием:

• предложен устойчивый метод решения системы уравнений равновесия и разработан алгоритм расчёта стационарных вероятностей состояний системы;

• получены выражения для интенсивностей потоков основных заявок принятых в систему, потерянных и обслуженных в ней, а также для вероятности потери заявки;

• найдено ПЛС ФР времени ожидания заявки в стационарном режиме.

2. Для однолинейной СМО (DMАР, ST)/(DMSP, DMSP)/l/r, функционирующей в дискретном времени:

• разработан алгоритм расчёта стационарного распределения длины очереди;

• установлена связь стационарного распределения вероятностей состояний СМО в произвольные моменты времени со стационарными вероятностями состояний в моменты непосредственно перед поступлениями основных заявок.

3. Для однолинейной СМО (MAP, ST)/{G, G)/l/r с фоновыми заявками и произвольным распределением времени обслуживания:

• предложен матрично-рекуррентный подход для вычисления стационарного распределения вероятностей состояний системы;

• получено выражение для ПЛС ФР времени ожидания заявки и ряда других стационарных показателей производительности системы.

1. Авен О.И. Турин H.H., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982. С. 464.

2. Артамонов Г.Т., Брехов О.М. Аналитические вероятностные модели функционирования ЭВМ. М.: Энергия, 1978.

3. Башарин Т.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчёта. М.: Наука, 1989.

4. Башарин Т.П., Бочаров П.П., Спесивое С. С. Об алгоритмическом и программном обеспечении методов аналитического моделирования информационно-вычислительных систем и их компонентов. М.: ВИНИТИ, 1983.

5. Башарин Т.П., Самуилов К.Е. Об одной системе массового обслуживания с двумя типами заявок с относительным приоритетом // Изв. АН СССР. Техн. кибернетика. 1983. №3. С. 48-56.

6. Башарин Т.П., Самуилов К.Е. Методы анализа производительности систем сигнализации по общему каналу / Итоги науки и техники. Электросвязь. М.: ВИНИТИ, 1986. С. 102-164.

7. Башарин Г.П., Харкевич А.Д., Шнепс М.А. Массовое обслуживание в телефонии. М.: Наука, 1968.

8. Бертсекас Д., Галлагер Р. Сети передачи данных. М.: Мир, 1989.

9. Бочаров П. П. Об обслуживании двух типов заявок с относительным приоритетом и распределениями фазового типа. // Теория телетрафика в системах информатики. М.: Наука, 1989. С. 45-50.

10. Бочаров П. П. Стационарное распределение конечной очереди с рекуррентным потоком и марковским обслуживанием // АиТ. 1996. т. С. 66-78.

11. Бочаров П.П., Вискова Е.В. Однолинейная система массового обслуживания конечной емкости с марковскими потоком и обслуживанием в дискретном времени. // Автоматика и телемеханика. 2005. №2. С. 73-91.

12. Бочаров П.П., ДАпиче Ч., Печинкин A.B., Салерно С. Система массового обслуживания G/MSP/1/r // Автоматика и телемеханика. 2003. №5. С. 46-74.

13. Бочаров П.П., Печинкин A.B. Теория массового обслуживания. М.: Изд-во РУДН, 1995.

14. Бочаров П.П., Чхитх Ворннаритх. Матрично-геометрическое решение для очереди фазового типа при исчерпывающей дисциплине отключения прибора // Микросистема 92: Материалы Всесоюзнойнаучно-технической конференции. Томск: Изд-во Том. ун-та. 1992. С. 31-33.

15. Бочаров П.П., Чхитх Ворннаритх. Об обслуживании нескольких видов заявок в системе конечной ёмкости с отключением прибора при опустошении системы // Методы массового обслуживания в информатике. М.: Изд-во РУДН. 1992. С. 72-88.

16. Бочаров П.П., Шлумпер Л. О. Однолинейная система массового обслуживания с фоновыми заявками. // Автоматика и телемеханика. 2005. №6. С. 74-88.

17. Бочаров П.П., Шлумпер Л. О. Однолинейная система массового обслуживания с фоновыми заявками в дискретном времени. // Информационные процессы. 2005. Т. 5. №3. С. 236-246.

18. Бочаров П.П., Шлумпер Л.О. Система массового обслуживания МАР/С/1/г с фоновыми заявками // Информационные процессы. 2005. Т. 5. № 5. С. 367-379.

19. Бронштейн О.И., Духовный И.М. Модели приоритетного обслуживания в информационно-вычислительных системах. М.: Наука, 1976.

20. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. М.: РИЦ "Техносфера", 2003.

21. Волковинский М.И., Кабалевский А.Н. Анализ приоритетных систем с учётом времени переключения. М.: Наука, 1976.

22. Гнеденко Б.В., Даниелян Э.А., Димитров Б.Н., Климов Г.П., Матвеев В.Ф. Приоритетные системы обслуживания. М.: Изд-во МГУ, 1973.

23. Джейсуол Н. Очереди с приоритетами. М.: Мир, 1973.

24. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь, 1988.

25. Като Т. Теория возмущений линейных операторов. // М.: Изд-во Мир, 1972.

26. Клейнрок Л. Вычислительные системы с очередями. М: Мир, 1979.

27. Клименок В. И. Модель приёмника транспортной станции локальной вычислительной сети. // Сети связи и сети ЭВМ, как модели массового обслуживания. Минск: Изд-во БГУ. 1991. С. 26-27.

28. Климов Г.П. Стохастические системы обслуживания. М.: Наука, 1966.

29. Климов Г.П., Мишкой Г.К. Приоритетные системы обслуживания с ориентацией. М.: Изд-во МГУ, 1979.

30. Липаев В.В., Колин К.К., Серебровский Л.А. Математическое обеспечение управляющих ЦВМ. М.: Сов. радио, 1972

31. Литвин В.Г., Лысяков П.К. О влиянии реорганизации базы данных на время ответа информационной системы. // Управляющие системы и машины. 1981. №2. С. 105-109.

32. Литвин В.Г., Лысяков П.К. Дискретно-непрерывная модель информационной системы с совместным обслуживанием запросов и реорганизацией баз данных. // Автоматика и телемеханика. 1983. №5. С. 149-158.

33. Развитие определений "информатика" и "информационные технологии". Под редакцией члена-корреспондента АН СССР И.А. Ми-зина. // Препринт. Москва. 1991. УДК 007:519.71.

34. Печинкин A.B., Чаплыгин B.B. Стационарные характеристики си-темы массового обслуживания G/MSP/n/r // Вестник РУДН. Серия: прикладная математика и информатика. 2003. №1. С. 119-133.

35. Математический энциклопедический словарь. Гл. ред. Прохоров Ю.В. М.:Сов. энциклопедия, 1988.

36. Самуилов К.Е. Методы анализа и расчета сетей ОКС 7. М.: Изд-во РУДН, 2002.

37. Сатовский Б. Л. MPLS технология маршрутизации для нового поколения сетей общего пользования. // Сети и системы связи. 2001. № 3. http://www.ccc.ru/magazine/depot/0103/read.html70303.htm

38. Скитович В. П. Элементы теории массового обслуживания. JL: Изд-во ЛГУ, 1976.

39. Тихоненко О.М. Модели массового обслуживания в информационных системах. Учебное пособие, (ГРИФ). М., Технопринт. 2003.

40. Флинт Д. Локальные сети ЭВМ: архитектура, принципы построения, реализации. М.: Финансы и статистика, 1986.

41. Шварц М. Сети связи: протоколы, моделирование и анализ. М.: Наука, 1992.

42. Шлумпер Л. О. Система массового обслуживания MAP/MSP/1/r с фоновыми заявками // XLI Всероссийская конференция по проблемам математики, информатики, физики и химии. Тезисы докладов, 18-22 апреля 2005 г., Москва. М.: Изд-во РУДН, 2005. С. 98-99.

43. Abate J., Choudhury G.L., Whitt W. Asymptotics for steady-state tail probabilities in structured Markov queueing models // Commun. Stat., Stochastic Models. 1994. V. 10. M. P. 99-143.

44. Abolnikov L., Dshalalow J.H. A first passage problem and its applications to the analysis of a class of stochastic models. //J. Appl. Math. Stochastic Anal. 1992. V. 5. №. P. 83-97.

45. Alam S.S., Acharya D., Rao V.P.C. M/M/l Queues with Server's Vacation. // Asia-Pacific Journal of Operational Research. 1986. V. 3. №1. P. 21-26.

46. Albores J.F., Tajonar S.F. The multi-server GI/MSP/c/r queue // Transactions of XXIV International Seminar on Stability Problems for Stochastic Models. Jurmala. Latvia, 2004. P. 110.

47. Albores J.F., Tajonar S.F. Analysis of the GI/MSP/c/r Queueing System // Информационные процессы. 2004. Т. 4. № 1. С. 46-57.

48. ATM Forum Technical Committee. Traffic Management Specification, Version 4.0 // ATM Forum contribution 95-0013R13, 1996.

49. Avi-Itzhak В., Maxwell W.L., Miller L.W. Queueing with alternating priorities. // Operations Research. 1965. V. 13. №2. P. 306-318.

50. Baba Y. On the M^/G/l queue with vacation time. // Oper. Res. Lett. 1986. V. 5. №2. P. 93-98.

51. Blondia C. Finite capacity vacation models with non-renewal input. // J. Appl. Probab. 1991. V. 28. №1. P. 174-197.

52. Bocharov P.P., DApice C, Pechinkin A.V., Salerno S. Queueing Theory. Ultrecht-Boston: VSP, 2004.

53. Bruneel H. Analysis of buffer behaviour for an integrated voice-data system // Electronics Letters, 1983. V. 19. №2. P. 72-74.

54. Chatterjee U., Mukherjee S.P. On some distributions of the M^/G/l queue with server's vacation and exhaustive service discipline. // Asia-Pac. J. Oper. Res. 1990. V. 7. №1. P. 82-91.

55. Choudhury G. An M^/G/l queueing system with a setup period and a vacation period. // Queueing Systems Theory Appl. 2000. V. 36. №1-3. P. 23-38.

56. Choudhury G. A batch arrival queue with a vacation time under single vacation policy. // Computers and Operations Research. 2002. V. 29. №14. P. 1941-1955.

57. Cooper R.B. Queues served in cyclic order: Waiting times.// Bell Syst. Tech. Jr. 1970 V. 49 (3 Mar.). P. 399-413.

58. Courtois P.J. The M/G/l finte capacity queue with delays. // IEEE Trans.on Communications. 1980. V. 28. P. 165-172.

59. Dshalalow J.H., Yellen J. Bulk input queues with quorum and multiple vacations. // Mathematical Problems in Engineering. 1996. V. 2. №2. P. 95-106.

60. Fendick K. W., Saksena V. R., Whitt W. Dependence in packet queues. // IEEE Transactions on Communications. 1989. V. 37. №11. P. 11731183.

61. Ferguson M. J., Aminetzah Y. J. Exact results for nonsymmetric token ring systems// IEEE TVans. on Commun. V. COM-33, 1985. P. 223231.

62. Ferguson M.J. Computation of the variance of the waiting time for token rings// IEEE. J. Sel. Areas Commun. V. 4. №6 1986. P. 775-782.

63. Ferng H. W., Chang J.F. The departure process of discrete-time queue-ing systems with Markovian type inputs // Queueing Systems, 2000. V. 36. P. 201-220.

64. Fiems D. Analysis of discrete-time queueing systems with vacations // PhD thesis, 2004. Brussel: Ghent University. P. 205.

65. Fuhrmann S. W., Cooper R. B. Application of decomposition principle in M/G/l vacation model to two continuum cyclic queueing models — especially token-ring LAN's. // AT&T Tech. J., 1985. V. 64. P. 10911099.

66. Fuhrmann S. W., Cooper R. B. Stochastic decompositions in the M/G/l queue with generalized vacations. // Operations Research. 1985. V. 33. №5. P. 1117-1129.

67. Gelenbe E., Mitrani I. Analysis and synthesis of computer systems // New York and London: Academic Press, 1980.

68. Gelenbe E., Pujolle G. Introduction to queueing networks. N.Y.: John Wiley, 1998.

69. Gun L., Chimento P. Effective bandwidth vector for two-priority ATM traffic // Proceedings of the INFOCOM'94, 1994. P. 1056-1063.

70. Hashida O. Analysis of Multiqueue. // Review of the Electrical Communication Laboratories. 1972. V. 20. №3. P. 189-199.

71. Heindl A., Zhang Q., Smirni E. ETAQA Truncation Models for the MAP/MAP/1 Departure Process // The Quantitative Evaluation of Systems, First International Conference on (QEST'04), 2004. P. 100109.

72. Jelencovic, P. and Melamed, B. Algorithmic modeling of TES processes //IEEE Trans. Autom. Con., 1995. V. 40. №7. P. 1305-1312.

73. Kao E.P.G., Narayanan K.S. Modeling a multiprocessor system with preemptive priorities. // Management Science. 1991. V. 2. P. 185-97.

74. Kao E.P.C., Narayanan K.S. Analyses of an M/M/N queue with servers' vacations. // European Journal of Operational Research. 1991. V. 54. P. 256-266.

75. Kella 0. The threshold policy in the M/G/l queue with server vacations. // Nav. Res. Logist. 1989. V. 36. M. P. 111-123.

76. Kramer M. Computational analysis of a finite capacity queueing system with vacations and nonexhaustive service. // Commun. Stat. 1988. V. Stochastic Models 4. №. P. 151-159.

77. Kuehn P.J. Multiqueue Systems with Non-exhaustive Cyclic Service. // BSTJ, 1979. V. 58. №. P. 671-698.

78. Kulkarni V.G., Gautam N. Admission Control of Multi-Class Traffic with Service Priorities in High-Speed Networks // Technical Report №95-06, Dept of Operations Research, University of North Carolina, 1995.

79. Lee, H. W., Lee, S.S. A Batch Arrival Queue with Different Vacations// Compu. Oper. Res. 1991. V. 18. M. P. 51-58.

80. Lee T. T. M/G/l/N Queue with Vacation Time and Exhaustive Service Discipline. // Opns. Res. 1984. V. 32. P. 774-785.

81. Lee H.S., Srinivasan M.M. Control policies for the Mx/G/1 queueing system. // Management Sci. 1989. V. 35. №6. P. 708-721.

82. Leung K.K. Cyclic-Service Systems with Nonpreemptive, Time-Limited Service. // IEEE Transactions on Communications. 1994. V. 42. №8. P. 2521-2524.

83. Leung K.K., Eisenberg M. A single-server queue with vacations and gated time-limited service. // IEEE Trans. Commun. 1990. V. 38. P. 1454-1462.

84. Leung K.K., Eisenberg M. A single-server queue with vacations and non-gated time-limited service. // Performance Evaluation, 1991. V. 12. №2. P. 115-125.

85. Levy H., Kleinrock L. A queue with starter and a queue with vacations: delay analysis by decomposition. // Operations Research. 1986. V. 34. №3. P. 426-436.

86. Levy Y., Yechiali U. An M/M/c queue with server's vacations. // Informations. 1976. V. 14. P. 153-163.

87. Levy Y., Yechiali U. Utilization of idle time in an M/G/l queueing system// Management Science. 1975. V. 22. №2. P. 202-211.

88. Livni M., Melamed B., and Tsiolis A. K. The impact of autocorrelation on queuing systems //Manage. Sci., 1993. V. 39. №3. P. 322-339.

89. Lucantoni D. M., Mieler-Hellstern K. S., Neuts M. F. A single-server queue with server vacations and a class of nonrenewal arrival processes. // Advances in Applied Probability. 1990. V. 22. №3. P. 676-705.

90. Mandjes M., Uitert M. Sample-path large deviations for tandem and priority queues with Gaussian inputs. // Annals of Applied Probability. 2005. V. 15. №3. P. 1193-1226.

91. McDysan D.E., Spohn D.L. ATM theory and application. New-York: McGraw-Hill. 1995.

92. Melamed, B. TES: A class of methods for generating autocorrelated uni-form variates. // ORSA J. Comput., 1991. V. 3. P. 317-329.

93. Miyazawa M., Shanthikumar J.G. Monotonicity of the loss probability of single server finite queue with respect to convex order of arrival or service processes. // Probability in the Engineering and Informational Sciences. 1991. V. 5. P. 43-53.

94. Nadarajan R., Mohana Dhas D.Audsin. Multiserver General Bulk Service Queue With Vacation. // Asia-Pac. J. Oper. Res. 1990. V. 7. №2. P. 141-154.

95. Nadarajan R., Subramaniam A. A general bulk service queue with server's vacation. // Oper. Res. in Manag. Systems Academic Publications. 1984. №7. P. 127-135.

96. Neuts M.F. A versatile Markovian point process. //J. Appl. Prob. 1979. V. 16. P. 764-779.

97. Neuts M.F. Matrix-geometric solution in stochastic models. Baltimore and London: The John Hopkins Univ. Press. 1981.

98. Queija R.N. Sojourn times in a processor sharing queue with service interruptions // Queueing Systems, 2000. V. 34. P. 351-386

99. Rubin I., De Moraes L.F.M. Message delay analysis for polling and token multiple-access schemes for local communication networks. // IEEE Journal on Selected Areas in Communications. 1983. V. 1. №5. P. 935947.

100. Sadre R., Haverkort B. Characterizing traffic streams in networks of MAP/MAP/1 queues // Proceedings of the 11th GI/ITG Conference on Measuring, Modelling and Evaluation of Computer and Communication Systems, Aachen, Germany, 2001. P. 195-208.

101. Scholl M., Kleinrock L. On an M/G/l Queue with Rest Period and Certain Service Independent Queueing Disciplines. // Operations Research. 1983. V. 31. №. P. 705-719.

102. Servi L.D. Average Delay Approximation of M/G/l Cyclic Service Queues with Bernoulli Schedules. // IEEE Journal on Selected Areas in Communications. 1986. V. 4. №6. P. 813-822.

103. Shanthikumar J. G. On stochastic decomposition in M/G/l type queues with generalized server vacations. // Oper. Res. 1988. V. 36. №4. P. 566569.

104. Soo H.M., Chung J-M. Analysis of Nonpreemptive Priority Queueing of DiffServ Networks with Bulk Arrivals. // International Journal of Electronics and Communications. 2003. V. 57. №6. P. 409-414.

105. Takagi H. Queueing analysis of vacation models, part I: M/G/l and part II: M/G/l with vacations. // TRL Res. Rep. TR87-0032, Tokyo: IBM Tokyo Res. Lab., 1987.

106. Takagi H. Queueing Analysis. A foundation of performance evaluation. Volume 3: Discrete-time systems // Amsterdam: Elsevier Science Publishers, 1993.

107. Takine T. A nonpreemptive priority MAP/G/1 queue with two classes of customers. // Journal of Operations Research Society of Japan. 1996. V.39. №. P. 266-290.

108. Takine T., Hasegawa T. The Workload in the MAP/G/1 Queue with State-dependent Services: Its Application to a Queue with Preemptive Resume Priority. // Stochastic Models. 1994. V. 10. №1. P. 183-204.

109. Takine T., Sengupta B., Hasegawa T. An Analysis of a Discrete-Time Queue for Broadband ISDN with Priorities among Traffic Classes // IEEE Transactions on Communications, 1994. V. 42. №№2-4. P. 18371845.

110. Watson K.S. Performance evaluation of cyclic server strategies-A survey. //in Proc. Performance '84, E. Gelenbe, Ed., Amsterdam, The Netherlands. 1985. P. 521-533.

111. Zhang Z.G., Tian N. Discrete Time GI/Geo/1 Queue with Multiple Vacations // Queueing Systems: Theory and Applications, 2002. V. 40. № 3. P. 283-294.