Анализ однолинейных систем массового обслуживания конечной емкости с зависимым обслуживанием

Последние годы характеризуются стремительным развитием разнообразных вычислительных средств и создаваемых на их базе информационно-вычислительных сетей, цифровых сетей с интеграцией служб и др. Основное назначение сетевых систем такого типа—это передача и обработка потоков информационных сообщений, которые по своей природе носят стохастический характер. В силу этого, как на этапе создания сетевых систем, так и в процессе их функционирования приходится решать ряд математичских задач, связанных с оценкой производительности сетевых систем и их компонентов. Известно, что одним из основных математических инструментов, позволяющих строить адекватные вероятностные модели для получения количественных оценок показателей функционирования сетевых систем и осуществлять анализ этих моделй, является аппарат теории массового обслуживания (ТМО) [13, 20, 32, 40−42, 46, 47, 51, 56, 64, 65, 68, 69, 79−81, 87]. Эффективность использования систем массового обслуживания (СМО) и сетей массового обслуживания (СеМО) для аналитического моделирования различного рода сетевых систем и их компонентов нашла свое обоснование в большом числе книг и обзоров [5, 9, 13, 14, 16, 44, 45, 40, 48, 50, 54, 59, 60].

Однако, при построении моделей ТМО для оценки производительности современных цифровых сетей [19, 44, 59, 60] в ряде случаев оказывается, что известные классические потоки—пуассоновский, эрланговский и, в общем случае, рекуррентный потоки—не вполне корректно моделируют реальные потоки пакетов, циркулирующих в сетях. Это в основном связано с тем, что рекуррентные потоки отражают только ситуации, когда интервалы между событиями потоков независимы между собой, что не всегда присуще реальным потокам. Этот недостаток рекуррентного потока в определенной степени был устранен с появлением марковского потока заявок (Markov arrival process—MAP) ([78]), который позволяет учитывать зависимости интервалов между смежными событиями потока, и в этом смысле является более общим по сравнению с рекуррентным потоком. В последние годы исследованию СМО с марковскими потоками заявок посвящено большое число публикаций. В частности, в работах [61, 70, 73, 74, 88, 89] отражены результаты исследования СМО с марковскими потоками, являющихся моделями различных компонентов цифровых сетей с одновременной передачей данных, речи и видеосигналов.

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

Другим видом специальных требований, накладываемых на процесс обслуживания в реальных сетевых системах, часто бывает приоритетный механизм обслуживания. В этих случаях процессы очередей более адекватно описываются приоритетными СМО. Например, приоритетный механизм обслуживания часто используется в цифровых сетях с интеграцией служб, в которых одновременно могут передаваться различные виды сигналов: данные, речь, видеосигналы, и др. В частности, принцип обслуживания с относительным приоритетом (без прерывания обслуживания) ([15]) используется при аналитическом моделировании системы сигнализации N 7 ([82]), которая является необходимой составляющей ряда современных цифровых сетей—телефонных сетей общего пользования, мобильных сетей, при реализации концепции интеллектуальных сетей [55] и т. д.

Еще одним важным практическим требованием, которое нельзя игнорировать при аналитическом моделировании процессов очередей, является ограничение на объемы буферных накопителей в реальных сетевых системах. СМО с накопителями конечной емкости являются более сложным объектом для аналитического изучения. Это связано с невозможностью применения для моделей с конечными очередями метода производящих функций и других традиционных методов ТМО. Поэтому значительная часть публикаций, связанных с оценкой производительности сетевых систем, посвящена анализу СМО с неограниченными накопителями. В некоторых случаях приближения такого рода дают вполне удовлетворительные результаты при решении реальных задач. Но это далеко не всегда так. Как показано в [13], глава 5, характер поступающего потока заявок также, как и распределение длительности обслуживания, может внести существенные коррективы в количественные оценки показателей производительности сетевых систем. Примером этого может служить резко выраженная зависимость вероятности потерь в однолинейной СМО с ограниченным накопителем от значения коэффициентов вариации интервалов между поступлениями заявок и длительностей их обслуживания. Неучет этого фактора при замене ограниченного накопителя на неограниченный может привести к совершенно неприемлемым результатом, так как вероятность потерь при одной и той же нагрузке, но различных значениях соответствующих коэффициентов вариации может различаться на несколько порядков.

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

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

Предметом нашего исследования являются однофазные СМО, которые кодируются в виде А/В ?с/г. Здесь символ, А обозначает тип потока заявок, входящего в СМО, символ В—тип обслуживания заявок, с—число обслуживающих приборов и, наконец, г—емкость буферного накопителя. Наиболее часто в ТМО для обозначения типов потоков и обслуживания используются следующие коды: М— пуассоновский поток или экпоненциальное обслуживание, D—детерминированный поток или обслуживание, Н—гиперэкспоненциальный поток или обслуживание, Е—эрланговкий поток или обслуживание, РН—поток или обслуживание фазового типа, MAP—марковский поток, GI—произвольный рекуррентный поток, G—произвольное рекуррентное обслуживание. При этом данные коды могут иметь нижние индексы, которые обозначают число входящих потоков и соответственно видов обслуживания такого типа. Например, символ М2 на первом месте означает, что в систему поступают два пуассонов-ских потока, а на втором месте,—что заявки обоих типов имеют экспоненциальные распределения с различными параметрами. Соответствующий символ, сопровождаемый обозначением (к), например РН (к), обозначает зависимость соответствующего потока или обслуживания от числа к заявок, находящихся в системе.

В некоторых случаях дополнительно на последнем месте в кодированном обозначении указывается дисциплина обслуживания, т. е. порядок выбора заявок из накопителя на приборы. В частности, это важно для приоритетных СМО, для которых иногда требуется даже указать приоритет заявок при поступлении в переполненную систему. В этом случае возможен один из случаев: либо поступающая заявка независимо от ее типа теряется и вновь не возвращается в систему, либо, если это приоритетная заявка, то она вытесняет из накопителя одну из неприоритетных заявок, которая при этом теряется. Для обозначения приоритетных дисциплин обслуживания будем пользоваться символом /] ([12]), где верхний индекс г обозначает дисциплину постановки заявок в очередь, а нижний 3—дисциплину выбора заявок: если г = 0, то заявка любого типа, поступающая на переполненную СМО, теряется, а при % = 2—поступившая приоритетная заявка вытесняет из накопителя одну из неприоритетных заявокпри 3 = 1 приоритетные заявки имеют относительный приоритет (без прерывания обслуживания), а при 3 = 2—абсолютный приоритет (с прерыванием обслуживания).

Однолинейные СМО с временем обслуживания заявок, зависящим от состояния системы, исследовались в работах [1−4, 25, 43, 66, 67, 71, 84−86], где были изучены разные типы зависимости времен обслуживания от состояния системы. При этом в этих работах результаты получены лишь для случая одного потока. Монография [1] и работы [2−4] посвящены в основном предельным результатам для систем с неограниченными накопителями и зависимым обслуживанием. В работе [25] рассматривалась СМО РН/РН/1/г с входящим потоком и обслуживанием фазового типа, зависящими от состояния очереди, а также с учетом обратной связи на входе и выходе системы. В этой работе был получен матричный алгоритм для вычисления стационарных вероятностей состояний СМО и выведены соотношения для вычисления ряда показателей ее производительности. В работе.

43] рассматривалась задача выбора оптимальной пороговой стратегии переключения скорости обслуживания заявок в двухскоростной ненадежной СМО М/G/l неограниченной емкости, в которой ФР времени обслуживания для первой скорости является экспоненциальной, а для второй скорости имеет произвольный вид. В [66] подобная задача решалась для аналогичной СМО с групповым пуассоновским потоком. В [67] изучалась СМО MMPP/M/1/r конечной емкости с гистерезисным управлением механизмом обслуживания. В отличие от других работ для исследуемой в [67] системе ФР времени обслуживания для конкретной заявки может меняться до завершения ее обслуживания. В [71] изучалась СМО М/G/l бесконечной емкости, имеющая функцию распределения (ФР) времени обслуживания Bk (t) для случая, когда число заявок в системе в момент начала обслуживания равно к < if, и B (t) для случая, когда к > К. Ряд результатов для СМО М/G/l бесконечной емкости для случая, когда ФР времени обслуживания зависит от длины очереди, получен в работах [84−86]. В [89] для СМО MAPJGJ1 бесконечной емкости рассматривался другой тип зависимости, когда время обслуживания зависит от состояния управляющего марковского процесса. В работе [39], основные результаты которой получены автором, анализировалась СМО MAP/G (k)/l/r с функциями распределения времени обслуживания, зависящими от числа заявок, находящихся в системе в момент выбора очередной заявки на обслуживание, для которой были получены матричные рекуррентные формулы для расчета стационарного распределения вероятностей состояний системы. Полученные в [39] результаты обобщают выводы для СМО MAP/G/1/r для случая, когда времена обслуживания заявок не зависят от состояния системы, изученной в [34−37].

Приоритетные СМО являются одним из важнейших типов систем, исследуемых в ТМО. Результаты для приоритетных СМО с неограниченными накопителями отражены в монографиях [40, 42, 87], а также в справочнике по ТМО [69].

Приоритетные системы конечной емкости, представляющие собой отдельный объект исследования. Начало исследования таких систем было положено Г. П. Башариным в работе [10], где для анализа многолинейной СМО М2/М/с/г//У с общим ограниченным накопителем был впервые предложен матрично-алгоритмический подход, позволивший получить рекуррентный алгоритм для вычисления стационарного двумерного распределения длин очередей в данной СМО. Матрично-алгоритмический подход позже был развит в целом ряде других публикаций ([13, 14, 29, 32, 53, 80, 81] и др.). В [10] также было получено выражение для преобразования Лапласа-Стилтьеса (ПЛС) времени ожидания приоритетных заявок и, кроме того, рассмотрен случай раздельных конечных накопителей. В работе [49] выводы [10] были обобщены на случай произвольного числа потоков. СМО Мк/М/с/г//1 с к входящими потоками исследовалась в работе [91], где были выведены явные выражения для распределений длин очередей каждого типа. Аналогичная СМО для случая произвольного обслуживания изучалась в [52].

Анализу однолинейных СМО конечной емкости с относительным приоритетом при общей очереди в литературе посвящен ряд работ [21−23, 30, 33]. В этих работах анализировались СМО с пуас-соновскими входящими потоками: в [30] рассматривалась система М2/М2/1/Г/Д0, в [21]—система М2/Я2/1/г//?, в [22]—система М2/С*2/ 1/г//1 и в [23]—система М2/С?2/1/г//°. Основными результатами этих работ являются рекуррентные формулы и рекуррентно-матричные алгоритмы для расчета совместного стационарного распределения длин очередей. В [33] было выведено условие существования равновесного режима СМО М2/С/1 с относительным приоритетом с двумя накопителями—конечным для приоритетного потока и бесконечным для неприоритетного потока. Получен также алгоритм для вычисления распределения очереди приоритетных заявок и факториальных моментов длины очереди неприоритетных заявок. Анализ СМО с потоками фазового типа и относительным приоритетом проводился в работах [6−8]. Исследуемая в этих работах СМО РЯ2/РЯ2/1/г1,Г2//10 с потоками и временами обслуживания, характеризуемыми распределениями фазового типа (РН~распределениями), имеет раздельные накопители для каждого типа заявок.

Исследованию однолинейных СМО с общим ограниченным накопителем и абсолютным приоритетом посвящены работы [6, 11, 28]. В работе [11] исследовалась СМО М2/М2/1/г//2, для которой были получены рекуррентные формулы для вычисления стационарного двумерного распределения длин очередей. В работах [6, 28] анализировалась СМО РН2/РН2/1 /г//2 с распределениями фазового типа, для которых был получен матрично-рекуррентный алгоритм для вычисления стационарного распределения вероятностей состояний соответствующего марковского процесса.

В работе [24] был разработан унифицированный алгоритм для нахождения стационарного распределения вероятностей состояний линейчатого марковского процесса, описывающего функционирование СМО М2/Су2/1 Для совокупности приоритетных дисциплин обслуживания {/?, Д2, /|}.

Приоритетные системы с марковскими входящими потоками изучались в работах [88−90, 34−37]. В работах [88−90] исследовалась СМО МАР2/С2/1 с двумерным марковским потоком и относительным приоритетом при бесконечной емкости накопителей, где ряд результатов для стационарного режима функционирования системы был получен в терминах производящих функций. Система М АР2/^2/1/г//1 с относительным приоритетом была подробно изучена в работах.

34, 35], где выведен матричный алгоритм для расчета стационарного распределения линейчатого марковского процесса, описывающего поведение СМО, а также получены выражения для определения стационарных вероятностей цепей Маркова, вложенных по моментам поступления заявок или окончания их обслуживания. Также в этих работах получено выражение для ПЛС для стационарной ФР времени ожидания приоритетных заявок при обслуживании их согласно дисциплине Аналогичные результаты были получены в работах [36, 37] для подобной системы в предположении, что выбор заявок на обслуживание производится с абсолютным приоритетом. В работах [39, 62], основные результаты которой были получены автором, результаты работ [34−37] были обобщены на случай приоритетных систем МАР2/в2(к)/1/г/Д0 и МАР2/02(к)/1/г/$ с зависимым обслуживанием.

Актуальность работы. Оценка производительности бурно развивающихся в последнее время сетевых систем является одной из важных и актуальных теоретических проблем информатики. Наиболее действенным инструментом аналитического моделирования сетевых систем является теория массового обслуживания.

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

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

Целью диссертационной работы является:

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

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

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

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

2. На базе полученных теоретических результатов разработан комплекс программ на языке Турбо Паскаль для расчета стационарных вероятностно-временных характеристик исследуемых СМО.

Методы исследования. В диссертационной работе в основном используются методы теории вероятностей, теории случайных процессов, теории массового обслуживания, матричной алгебры и численные методы.

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

Практическая ценность работы. Результаты, полученные в диссертации, могут найти свое применение при аналитическом моделировании сетевых систем. Результаты диссертации дают возможность более адекватно моделировать процессы очередей в реально существующих сетевых системах. К результатам диссертации относятся также программы, разработанные для полученных при теоретическом исследовании вычислительных алгоритмов и включенные в программный комплекс для расчета систем и сетей массового обслуживания, разрабатываемый в РУДН. Эти результаты могут быть использованы в учебном процессе для студентов направления «Прикладная математика и информатика» в курсе «Стохастическое моделирование» и при подготовке курсовых и выпускных работ, а также при выполнении магистерских диссертаций по программе «Теория вероятностей и математичекая статистика» .

Реализация результатов работы. Исследование однолинейных систем массового обслуживания конечной емкости с марковскими потоками при произвольном обслуживании, зависящим от состояния очереди, проводилось в рамках НИР «Разработка математических методов и алгоритмов анализа цифровых систем с интеграцией служб (государственный регистрационный номер 01.960.0 9 077), выполняемой в соответствии с координационными планами РУДН, а также по гранту РФФИ № 99−01−34 «Стохастические сети: моделирование, анализ производительности и устойчивости» .

Апробация работы. Материалы диссертации докладывались на ХХХ1У, ХХХУ и ХХХУ1 научных конференциях факультета физико-математических и естественных наук РУДН (Москва, 1998;2000 гг.), а также на научном семинаре кафедры теории вероятностей и математической статистики РУДН (1998;2000 гг.).

Публикации. По материалам диссертации опубликовано 5 работ, из них две в центральной печати.

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

Основные результаты выполненных исследований заключаются в следующем:

1. Для случаев как бесприоритетного, так и приоритетного обслуживания выведены рекуррентные матричные алгоритмы расчета стационарных вероятностей состояний систем в произвольные моменты времени и формулы для вычисления основных показателей их производительности.

2. Для всех изученных систем получены стационарные распределения цепей Маркова, вложенных либо по моментам поступления заявок, либо по моментам окончания их обслуживания.

4. Для системы с одним входящим марковским потоком получено преобразование Лапласа-Стилтьеса стационарной функции распределения интервалов между выходами заявок.

5. На основе разработанных вычислительных алгоритмов составлены программы на языке Турбо Паскаль для расчета стационарных распределений длин очередей и проведен численный анализ ряда показателей производительности исследуемых систем.

ЗАКЛЮЧЕНИЕ

.

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