Анализ систем массового обслуживания с марковским потоком и марковским обслуживанием в дискретном времени Вискова Елена Валерьевна

Вискова Елена Валерьевна. Анализ систем массового обслуживания с марковским потоком и марковским обслуживанием в дискретном времени : Дис. . канд. физ.-мат. наук : 05.13.17 Москва, 2005 122 с. РГБ ОД, 61:06-1/219

Содержание к диссертации

ГЛАВА 1. Однолинейная система конечной емкости с марковским потоком и марковским обслуживанием в дискретном времени 18

1, Марковский поток заявок и марковское обслуживание 18

в дискретном времени

2. Описание системы 24

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

4. Матрично-рекуррентное решение системы уравнений равновесия 31

5. Связь с непрерывным временем 35

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

7. Стационарное распределение времени ожидания 43

8. Численный анализ 47

ГЛАВА 2. Однолинейная система конечной емкости с марковским потоком и марковским обслуживание отрицательными заявками в дискретном времени 51

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

2. Система уравнений равновесия 53

3. Алгоритм решения системы уравнений равновесия 59

4. Стационарные вероятности потери заявок 61

5. Численный анализ 67

ГЛАВА 3. Двухфазная система конечной емкости с марковским потоком и марковским обслуживанием в дискретном времени

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

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

3 . Алгоритм решения системы уравнений равновесия

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

5. Стационарные вероятности потери заявок

б. Численный анализ

ГЛАВА 4. Марковская двухфазная система конечной емкости с отрицательными заявками в дискретном времени

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

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

3. Алгоритм решения системы уравнений равновесия

4. Стационарные вероятности потери заявок

Заключение список источников

Введение к работе

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

Проектирование, управление и расчет этой тончайшей инфокоммуникационной системы представляют собой интереснейшие задачи для математиков, инженеров и экономистов всего мира. Мощный инструментарий для аналитического моделирования сетевых систем создан на основе теории массового обслуживания (ТМО). Возможности применения систем массового обслуживания (СМО) в качестве моделей сетевых систем и их компонентов отражены, например, в [1, 4-6, 22, 24, 26, 27, 30, 34-36]. В связи с этим большое внимание в литературе уделяется собственно анализу СМО (см., например, [1, 7, 16, 23, 28, 29]).

В качестве стандартных моделей в ТМО принято рассматривать системы, функционирующие в непрерывном времени [16, 23, 29]. Тем не менее, дискретные модели также находят

широкое применение, призерами здесь служат хорошо известные методы исследования непрерывных СМО с помощью построения дискретных цепей Маркова по моментам поступления или ухода заявок из системы [10, 44. 70, 71], а также методы аппроксимации непрерывных систем дискретными посредством квантизации времени [2, 3. 12. 71].

Кроме указанных классических примеров использования дискретных моделей существуют и другие приложения аппарата дискретных СМО для анализа производительности реальных систем. В качестве примера, можно привести хорошо известны вычислительный системы с разделением времени (time-sharing), обладающие врожденной дискретной природой - временем, разделенным на слоты. Появление и развитие таких систем относится к середине 60-х годов, в это время и появляются первые исследования в области СМО с дискретным временем, см., например, работы [72, 73], В этих работах шаг дискретизации временной шкалы соответствует размеру временного слота, который выделен для осуществления процессором определенного количества работы — алгоритм кругового обслуживания (round-robin algorithm). Следует отметить, что, несмотря на то, что технических сложностей, возникающих при работе с дискретными СМО. значительно больше, чем при работе со СМО в непрерывным временем, сам математический аппарат является более элементарным по сравнению с непрерывным временем. Под техническими трудностями понимаготся комбинаторные сложности, возникающие при выводе системы уравнений равновесия, что связано с возможностью осуществления большого количества событий за один временной слот, в отличие от непрерывного времени, когда за такт может произойти всего одно событие, приводящее к изменению состояния рассматриваемой СМО.

Впервые эти особенности были рассмотрены в работах: Клейнрока [72, 73]. Из-за сложностей работы с дискретным временем для оценки характеристик производительности систем, обладающих дискретной природой, были разработаны методы приближенного анализа с помощью непрерывных СМО, например, системы с разделением времени можно аппроксимировать моделями с разделением процессора (processor sharing>, как это было впервые предложено в работе [93] и расширено в работе [71, гл. 4].

Из-за сложности работы с системами в дискретном времени публикаций в этой области значительно меньше по сравнению с их количеством в области непрерывных СМО. Однако, начиная с середины 60-х годов, теория дискретных систем массового обслуживания постепенно развивалась, в 1983 году вышло несколько монографий Хюнтера [67, 68]. в которых рассматривались в основном однолинейные СМО неограниченной емкости. Также следует отметить появление в это время базового курса лекций по дискретным СМО у Кобаянш [74], в котором рассматривались их приложения к анализу систем временного мультиплексирования. Постепенно развивалась теория для дискретных многофазных СМО и сетей массового обслуживания (СеМО) с дискретными узлами неограниченной емкости, однако к концу 80-х годов количество работ в этой области очень незначительно [60 ,66, 84, 94, 100].

Новый всплеск исследований в области дискретных СМО связан с развитием сетей на базе технологии асинхронного режима передачи (Asynchronous Transfer Mode, ATM) и приходится на середину 90-х годов [см., например, 53, 69, 87, 88. 92, 101]. Характерной особенностью сетей ATM является фиксированный размер ячейки, в которой передается информация различного типа. Например, коммутаторы ATM, как правило, моделируются с помощью дискретных СМО, поскольку их синхронизация

осуществляется посредством мельчайших временных квантов. В 90-е годы выходят несколько монографий [53, 95. 99] и большое число статей, посвященных исключительно моделям в дискретном времени, наиболее известные среди которых публикации [51, 52, 58, 59, 62-65, 77, 83? 89]. В работах [53, 95, 99] сделан исчерпывающий обзор литературы по моделям в дискретном времени, детально рассмотрены всевозможные дискретные СМО неограниченной емкости с потоками и обслуживанием различных типов (детерминированный, геометрический, фазовый и др.).

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

Впервые понятие марковского потока было введено Ныотсом в 1979 году [79], а затем во время нового всплеска исследований, связанных с потоками фазового типа, уточнено Лукантони [75, 76]т С тех пор в литературе по теории очередей большое внимание уделяется собственно анализу СМО с марковским потоком [8, 9. 16, 37, 47, 57]. Как известно, марковский поток заявок устроен более сложно, чем поток фазового типа, и в определенном смысле является его обобщением [15, 57]. Поток фазового типа в свою очередь характеризуется некоторым РН-распределением, включающем в себя, как частные случаи, экспоненциалы-юе, эрланговское, гиперэкспоненциальное и другие распределения. Имеются два основных фактора, объединяющих поток фазового

типа и марковский поток: первый — это свойство марковости процессов, управляющих генерацией заявок; второй — оба потока являются фазового типа, т.е. pi марковский поток устроен так, что процесс генерации заявок представляется как случайное блуждание по конечному множеству фа,н, длительность прохождения которых имеет экспоненциальное распределение. Однако между этими потоками есть существенное различие: марковский поток не является рекуррентным. Именно последнее свойство марковского потока объясняет его широкое использование для моделирования реальных телекоммуникационных систем с очередями [40. 41, 42. 53, 54, 69,85,87,88, 92, 101].

Для получения стационарного распределения очереди для СМО с марковским входящим потоком, а также для СМО с распределением времени обслуживания фазового типа в работах Бочарова и Печинкина [15, 17, 18] было предложено использовать алгоритмический метод, основанный на использованном в [16, 31] методе последовательного исключени5і состояний вложенной цепи Маркова. Впервые алгоритмические методы анализа СМО были разработаны Ныотсом [80-82] и использовались для анализа системы G/PH/1/co, Развитию алгоритмических методов анализа СМО посвящены также публикации [46, 55, 56, 78, 86, 98].

Появление понятия дискретного марковского потока в начале 90-х было обусловлено необходимостью решения ряда конкретных практических задач. Впервые системы с дискретным марковским потоком исследуются в работах Блондия [42, 43], в которых DM АР применяется для моделирования ATM трафика, а с помощью системы конечной емкости с групповым марковским потоком и рекуррентным обслуживанием в дрхскретном времени анализируются характеристики производительности сетевых коммутационных устройств. В [92] дискретный марковский

поток применяется для анализа производительности процесса мультиплексирования на уровне адаптации ATM. Дальнейшим развитием исследований систем с входящим марковским потоком заявок стало изучение СМО с различными распределениями времени обслуживания и дисциплинами обслуживания, а также с учетом повторных заявок. Этой тематике был посвящен ряд работ [19, 38, 39, 61, 87, 96, 97]. В работах [90, 91] с помощью методов имитационного моделирования исследуется устойчивость параметрических оценок марковского потока.

Цикл работ [11-14, 20, 21, 32, 33, 45, 48, 49]> опубликованных в последние годы, связан с исследованием систем не только с марковским потоком, но и с марковским обслуживанием.

По аналогии с марковским потоком естественно рассмотреть модель обслуживания заявок в виде некоторого марковского процесса, допускающего разбиение обслуживания . на фазы с экспоненциальным распределением, при этом длительности обслуживания заявок могут быть зависимы между собой. Впервые марковское обслуживание было формально определено в работе [10], а понятие марковского обслуживания в дискретном времени введено в работе [12].

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

Актуальность работы. Системы массового обслуживания (СМО) в дискретном времени играют важную роль в оценке производительности реальных систем и сетей связи> поскольку позволяют учитывать как дискретный характер передаваемых единиц информации, так и дискретность процесса функционирования современных телекоммуникационных систем (например, мультиплексоров ATM. систем передачи пакетов

IP (Internet Protocol) поверх WDM (Wavelength Division Multiplexing)).

Появление понятия дискретного марковского потока в начале 90-х было обусловлено необходимостью решения ряда конкретных практических задач, G помощью дискретного марковского потока и его частных случаев (поток Вернул ли; поток Берпулли, управляемый цепью Маркова; дискретный поток фазового типа) достаточно хорошо моделируются процессы поступления единиц информации фиксированной длины в системах и сетях связи, по отношению к которым применяются различные механизмы мультиплексирования, как например в сетях ATM,

Исследования в области дискретных СМО, в том числе с марковским потоком заявок, зародившись в середине 60-х годов, интенсивно развивались. На сегодняшний день изучены всевозможные системы с марковским потоком и различными дисциплинами обслуживания; обобщающие СМО с геометрическим, фазовым и другими потоками; работы в основном направлены на анализ систем неограниченной емкости. Результаты исследований в области дискретных СМО опубликованы в десятках работ. Такой интерес к этой проблематике со стороны ученых показывает практическую необходимость в дальнейшем развитии теории

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

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

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

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

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

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

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

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

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

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

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

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

Реализация результатов работы. Исследование систем конечной емкости с марковским потоком заявок, марковским обслуживанием и отрицательными заявками проводилось в рамках НИР п Разработка теоретических основ анализа очередей в информационно-вычислительных и телекоммуникационных сетях: алгоритмический подход 11 (государственный регистрационный номер 01.2,00 105246), выполняемой в соответствии с тематическим планом РУДН на 2001-2005 гг., а также в рамках гранта Российского фонда фундаментальных исследований № 02-07-90147 ![ Математические методы и программное

обеспечение моделирования информационных, вычислительных и телекоммуникационных систем 11 .

Апробация работы. Материалы диссертации докладывались на международных конференциях: "Современные математические методы анализа и оптимизации телекоммуникационных сетей 4 (Беларусь, Минскj 2005 г.); Fifth Workshop on Simulation (Russia, St. Petersburg, 2005 г.); 17* ;i IMACS World Congress Scientific Computation, Applied Mathematics and Simulation (France, Paris, 2005 i\); XXIV International Seminar on Stability Problems for Stochastic Models (Latvia, Jurmala, 2004 г.); на XL и XLI Всероссийских научных конференциях по проблемам математики, информатики, физики и химии (Москва, РУДН, 2004, 2005 гг.); на научном семинаре по теории массового обслуживания кафедры теории вероятностей и математической статистики РУДН.

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, разделенных на параграфы, заключения и списка литературы. Каждая глава состоит из параграфов; формулы нумеруются внутри каждой главы. При ссылке на формулы из другой главы указывается также номер главы. Текст изложен на 122 страницах, включая 2 рисунка и 7 таблиц. Список литературы содержит 101 источник.

В первой главе исследуется однолинейная система массового обслуживания конечной емкости с марковским потоком и марковским обслуживанием в дискретном времени, которое измеряется в фиксированных интервалах (квантах, тактах). Величина такта устанавливается равной h единиц времени, h > 0 , предполагается, что все возможные изменения в системе происходят в моменты времени n/i, п — 1,2. , В качестве n-го такта рассматривается полуинтервал [

📎📎📎📎📎📎📎📎📎📎