Содержание к диссертации
Введение
ГЛАВА 1. Однолинейная система конечной емкости с марковским потоком и марковским обслуживанием в дискретном времени 18
1, Марковский поток заявок и марковское обслуживание 18
в дискретном времени
2. Описание системы 24
3. Система уравнений равновесия 26
4. Матрично-рекуррентное решение системы уравнений равновесия 31
5. Связь с непрерывным временем 35
6. Стационарные вероятности состояний в моменты поступления или выхода заявок 37
7. Стационарное распределение времени ожидания 43
8. Численный анализ 47
ВЫВОДЫ 50
ГЛАВА 2. Однолинейная система конечной емкости с марковским потоком и марковским обслуживание отрицательными заявками в дискретном времени 51
1. Описание системы 51
2. Система уравнений равновесия 53
3. Алгоритм решения системы уравнений равновесия 59
4. Стационарные вероятности потери заявок 61
5. Численный анализ 67
ВЫВОДЫ 71
ГЛАВА 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. систем передачи пакетов
.9
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-го такта рассматривается полуинтервал [{п — 1)/г,п/г), а события на этом такте происходят в следующем порядке: в момент nh — 0 покидает систему заявка, обслуживание которой завершилось на такте п; в момент nh из очереди выбирается заявка на обслуживание и сразу поступает на прибор; в момент nh + 0 в систему поступает и помещается в очередь заявка, генерация которой завершилась на такте, п.
Выбор заявок на обслуживание производится в порядке их поступления, т.е. в соответствии с дисциплиной FCFS. Заявки, заставшие в момент их поступления в систему все места в накопителе занятыми, теряются, при этом потерянные заявки более не возобновляются и не оказывают никакого влияния на систему и входящий поток.
В 1 формализовано понятие дискретного марковского потока и введено понятие дискретного марковского обслуживания.
Формальное описание рассматриваемой СМО дано в 2,
где также введена цепь Маркова (ЦМ), описывающая ее функционирование.
В 3 получена система уравнений равновесия (СУР) для стационарных вероятностей состояний системы в произвольные дискретные моменты времени.
В 4 выведен матричный алгоритм для решения СУР.
В 5 показана взаимосвязь между системами с марковским потоком и марковским обслулшванием в дискретном и непрерывном времени.
В 6 получены выражения для стационарного распределения вероятностей состояний системы, рассматриваемой в моменты непосредственно перед и сразу после поступления заявок или окончания их обслуживания,
В 7 получены основные характеристики производительности системы: стационарная вероятность потерь и среднее время ожидания начала обслуживания.
В S проведем численный анализ основных характеристик производительности системы.
Во второй главе рассматривается однолинейная система массового обслуживания конечной емкости с отрицательными заявками. Входящий поток обычных (положительных) заявок является дискретным марковским, отрицательные заявки поступают в систему в соответствии с геометрическим распределением, обслуживание также марковское и определяется идентично тому, как это было сделано в главе 1.
Поступившая за такт отрицательная заявка вытесняет из СМО последнюю ожидающую в накопителе положительную заявку и покидает систему, не получая никакого обслуживания; если в накопителе отсутствуют заявки, то отрицательная заявка уничтожает положительную' заявку, находящуюся на приборе, и
также покидает систему.
В 1 дано формальное описание рассматриваемой СМО, установлен порядок осуществления событий за такт, определена цепь Маркова, описывающая функционирование СМО.
В 2 выведена СУР для стационарных вероятностей цепи Маркова в произвольные дискретные моменты времени.
В 3 получено матрично-рекуррентное решение СУР.
В 4 получены выражения для стационарного распределения вероятностей состояний системы, рассматриваемой в моменты непосредственно перед и сразу после поступления отрицательных и обычных заявок в систему или окончания их обслуживания; выведены выражения для вероятностей потерь заявок из-за переполнения буфера и из-за поступления отрицательных заявок,
В 5 проведен численный анализ основных характеристик производительности системы.
В третьей и четвертой главах проводится анализ двухфазных систем массового обслуживания с марковским потоком и марковским обслуживанием, на каждой фазе в системах функционирует один прибор и имеется буферный накопитель конечной емкости. Отличие между СМО состоит в наличие потока Бернулли отрицательных заявок в системе, рассматриваемой в главе 4. Если прибор и все места в буферном накопителе на первой фазе заняты, то вновь сгенерированная заявка теряется. Аналогично, если на второй фазе прибор и все места в буферном накопителе заняты к моменту завершения обслуживания заявки на первой фазе, то обслуженная на первой фазе заявка теряется.
В 1 дано формальное описание рассматриваемой СМО и установлен порядок осуществления событий за такт,
В 2 получена СУР для стационарных вероятностей ЦМ, описывающей функционирование системы, в произвольные
дискретные моменты времени.
В 3 разработан алгоритм решения СУР.
В 4 получены выражения для стационарного распределения вероятностей состояний системы, рассматриваемой в моменты непосредственно перед и сразу после поступления заявок на фазы системы или окончания их обслуживания. В главе 4 получены выражения для вероятностей потери заявок на первой и второй фазах из-за переполнения буферных накопителей, а также в результате поступления отрицательных заявок.
В 5 главы 3 выведены выражения для вероятностей потери заявок на первой и второй фазах, а также суммарной вероятности потери в системе из-за переполнения буферных накопителей.
В б главы 3 проведен численный анализ основных вероятностных характеристик системы.
Матрично-рекуррентное решение системы уравнений равновесия
Для решения СУР (1.7) — (1-Ю) применим метод урезания11, состоящий в последовательном отбрасывании множеств Ад, XR-I: ... J Х\ и ТсклеиванииТостающихся траекторий соответствующих ЦМ. Для лучшего понимания сущности получаемого при таком подходе алгоритма дадим его краткий вывод. Суть данного подхода заключается в последовательном преобразовании матрицы Р. Сначала преобразуются блочные элементы матрицы Р = Р 1:
Из структуры матрицы F видно, что ЦМ {7 , п 0} за один шаг может попасть из любого состояния подмножества Ля — i jjR), І — 1,/, jf = 1,77} только в одно из СОСТОЯНИЙ Хл или Xr — {(г, j, г), г — 1,/, j = l,m}. Поэтому матрица Р ., элементом (і) которой является вероятность р)/. Pw, ., ч того, что в момент выхода из состояния (i3ij, Л) Є - ЦМ {jni n 0} первый раз попадет в состояние (i lfjv) Є rfr имеет вид Р&} = Ряг + Р Рд. + (42 + ..- = (/- 4)-1 - Р Ра Рассмотрим теперь новую ЦМ {% \ п 0} с множеством состояний порожденную моментами попадания первоначальной ЦМ {7п, п 0} в состояния множества X l\
Следует отметить, что для всех состояний (i}j}k)} г = 17, ЦМ {77. j n 0} переходит из состояния (iyj7k) в состояние (i jfjk ) тогда и только тогда, когда ЦМ { уПі п 0} совершает (і) такой же переход. Следовательно, матрицы Р п к — 0,г, к1 = 03 г — 1, для ЦМ {7п І п 0} совпадают с соответствующими матрицами для ЦМ {jni п 0}.
Далее рассмотрим случай, когда ЦМ {7 , п 0} переходит из состояний (i}j7r) и (i j r — 1) в состояние (i\f7r). Тогда ЦМ {7п тс 0} может либо на первом шаге перейти из состояний (iyj7r) и (i7j)V — 1) сразу в состояние {і 7з\т) с вероятностями ptir)(i j\r) и rJCi j .r-i) соответственно, либо сначала перейти из состояния (i j /r) в состояние (f\f\R), а затем в момент первого выхода из множества состояний , попасть в состояние (і ,/, г) с вероятностью p\i» f щш jf г)ш результате, учитывая, что вероятность перехода из состояния (i} j, г — 1) в состояние (17, j", К] равна нулю, получим р(1) _ р , р(0)р{1) р(1) _ р Кроме того заметим, что ЦМ { jn , ть 0} также неприводима и непериодична. Далее введем матрицу оо J oi U . PlO Pll Pl2 0 P2i Р22 ( Рт Рт 0 ... О 0 0 О О О pi1) = 0 0 \ 0 0 0 Очевидно, что ее главный минор /Роо Рої 0 Pj.0 Pll Р±2 о о р(1) = 0 Рої Р О о о V р(1) р(0) M",f-1 Р Р(1) представляет собой матрицу переходных вероятностей ЦМ ь п ) п 0} и имеет такую же структуру, как и матрица Р = Р . Аналогичная процедура преобразования главных миноров, получаемых на каждом шаге матриц Р \ Р и т.д., продолжается до тех пор, пока не придем к матрице P R\ которая является матрицей переходов ЦМ {уп \ п 0} с множеством состояний Согласно леьше 1.4.1 из [44, с. 23] стационарные вероятности 0. Р? для всех цепей Маркова {7?t , я- 0}7 А: — 0, Я, совпадают с точностью до постоянного множителя. Поэтому сначала можно найти решение ОУР для ЦМ {jn \ п 0} (с точностью до нормировочной константы): (1.12) где матрица .г00 находится с помощью рекуррентного матричного алгоритма: p(r-k+i) _ jf р(г-Щ-і p(r-k+l) _ „(r-A+lJp 1 k,k Vі i fc,A J i fc,fc-i — fc.fc М-1 p(r-fc+l) _ p p(r-ft) p[r-k+l) p(r-k+l) _ p Po--fe+i) _ p -ft+D _ 0j A = Q- _ Затем последовательно (также с точностью до нормировочной константы) вычисляются рк, к = 1,й, из последнего уравнения СУР для ЦМ {7 тг } , 0} (здесь исходная ЦМ соответствует {in \ п 0}) по формуле РЬ(ЕЙГ УГ+11 (Lis) Наконец, на последнем этапе производится нормировка полученных вероятностей в соответствии с условием нормировки (1.10).
Алгоритм решения системы уравнений равновесия
Для решения СУР (2.2)-(2.6) используется метод "урезания11 множества состояний с последующим склеиванием оставшейся траектории исходной ЦМ, который был детально описан в главе 1.
Согласно методу, изложенному в предыдущей главе, сначала с точностью до нормировочной константы находится решение СУР PS = PP№, (2.7) где матрица 1QQ находится с помощью рекуррентного матричного алгоритма: р(г-Ч--1) _ (т р(г-А)ч-1 р(г-Л+1) _ p(r-fc+l)p J U - Iі J М J ) А, :-! — J кк J fc, -b p(r-fcH-l) _ р pC -fe) p(r-AH-l) p(r-fc+l) _. p p(r-k+l) = pfr-ft+l) 0 fc = g- Затем последовательно (также с точностью до нормировочной константы) вычисляются остальные векторы рк по формуле РГ=(ЕР "Ч) Г"), к = ТЛ. (2.8) 5=0 Наконец, на последнем этапе в соответствии с условием (2.6) производится нормировка полученных вероятностей .
В системах с отрицательными заявками и накопителем ограниченной емкости заявки могут теряться по двум причинам: в результате переполнения накопителя и за счет поступления в непустую систему отрицательном заявки. Обозначим через тг стационарную вероятность потери в результате переполнения накопителя, а через 7Г стационарную вероятность потери, вызванную поступлением отрицательной заявки. Далее найдем эти вероятности,
Вероятность потери заявки за счет переполнения накопителя. Для расчета стационарной вероятности потери заявки н результате переполнения накопителя найдем стационарные вероятности состояний СМО в моменты непосредственно перед завершением генерации положительных заявок и их поступлением в систему.
Рассмотрим ЦМ {j A+7n 0} = {(п-о,?М-о3 ьЪ-о)3 п 0}, вложенную по моментам непосредственно перед поступлением положительных заявок в систему, исключая те моменты, когда за рассматриваемый такт произойдет окончание обслуживания заявки на приборе или поступит отрицательная заявка. Множество А + состояний ЦМ {7 -и п 0} является подмножеством X и определяется следующим образом;
Здесь индексы г, j и fc обозначают соответственно фазу генерации, фазу обслуживания и число заявок в системе непосредственно перед поступлением положительной заявки в систему.
Обозначим через V &+-, стационарную вероятность состояния х е /1+- Далее определим вероятность a[stq) поступления положительной заявки в систему за такт при незавершенном обслуживании и непоступлении отрицательной заявки на этом такте; для режима 1 н o-(s,q) = pq {ai 1) + 5 Pfe g (ai ьо) (2-9) k=i для режима 2 к Найдем теперь стационарные вероятности состояний СМО в моменты непосредственно перед поступлением заявки в систему при незавершенном обслуживании и непоступлении отрицательной заявки на данном такте, задаваемые векторами Р] + — [PllkiA+iPlZhtAPlm/ A+ lfc.A-b — iP2mktA+i "- РШс,А+ - ш ,А+) где к — О, R для режима 1 и к = 1, І2 для режима 2, и дополнительно для режима 2 - вектором pj"+ = СРГОИ+ = %А+)"
Заметим, что поступающая в СМО заявка, генерация которой завершилась на. n-м такте, застанет в ней в момент непосредственно перед поступлением в СМО к других заявок, если па п-ы такте в СМО находилось к заявок и за n-й такт не закончилось обслуживание заявки на приборе и не поступила отрицательная заявка. Кроме того, заметим, что стационарная вероятность РЇікА представляет собой условную вероятность состояния (i jjk) системы при условии, что в данный момент поступит новая заявка и на предыдущем такте не завершится обслуживание заявки, находящейся на приборе, и не поступит отрицательная заявка. С учетом этого, а также, принимая во внимание (2.9) и (2.9 ), полупим для режима 1
Зная стационарное распределение состояний вложенной ЦМ по моментам непосредственно перед поступлением положительных заявок в систему, определим вероятность тг потери заявки в результате переполнения накопителя.
Рассмотрим механизм потери заявки. Если в момент nh + 0 СМО находится в одном из состояний множества Х то поступившая на (п+ 1)-м такте заявка потеряется лишь при условии, что находящаяся на приборе на этом такте заявка не обслужится, т.е. она не покинет систему в момент (п -\- l)h — 0 и не поступит отрицательная заявка.
. Алгоритм решения системы уравнений равновесия
С целью вычисления стационарных вероятностей потерь заявок на первой и второй фазах системы и общей вероятности потери заявки в этом разделе будут получены стационарные вероятности состояний системы в моменты нсгюсредствеппо перед поступлением заявки в систему и непосредственно перед завершением ее обслуживания на первой фазе и перехода на вторую фазу системы.
Необходимо заметить, что в случае дискретного времени за один такт могут произойти два и более активных событий, приводящих к изменению состояния системы. В нашем случае одновременно (в течение одного такта) могут произойти три следующих события: завершение обслуживания заявки на второй фазе, завершение обслуживания заявки на первой фазе и поступление новой заявки. Если за такт происходят все три перечисленные события, то потеря заявки, в силу установленного к 1 порядка наступления событий, ни на одной из фаз невозможна. Таким образом, для вычисления вероятностей потери заявки следует рассматривать лишь такие комбинации событий, которые могут привести к потери на одной из фаз системы, что возможно в следующих случаях: если за такт сгенерируется новая заявка, 1-і а первой фазе заявка не обслужится, на второй фазе заявка может как обслужится, так и нет; либо, если на такт не закончится обслуживание заявки на второй фазе, завершится обслуживание заявки на первой фазе, а новая заявка, может как сгеиерироваться, так и пет.
Далее рассмотрим ЦМ {%л , п 0}, построенную по моментам nh—О непосредственно перед поступлением заявки в систему при условии, что обслуживание на первой фазе за такт с номером [n — l)h не завершилось- ІУІножество состояний Хд цепи Маркова {%А 0} является подмножеством множества X и имеет следующий вид: ХМ= U Иі ifci=0 где
Здесь индексы (z,.?ijj2j fci; 2) обозначают соответственно фазу генерации заявки, фазу обслуживания на первом приборе и фазу обслуживание на втором приборе, число заявок на первой фазе системы и на второй фазе системы, непосредственно перед поступлением заявки в систему.
Будем полагать, что предельные вероятности р Ai = ]ш1п„ соР{7 = ffi}, хі Є ХХ1 существуют.
Далее определим вероятность a j поступления заявки в систему при незавершенном обслуживании на первой фазе системы: a(h) = Y POM і і) + Y, Т рїикЛаі Ьо і)- (3-3) где a-i = Ail, 6 = SQI, 1 — единичный вектор, соответствующей контексту размерности.
Найдем теперь стационарные вероятности того, что система находится в одном из состояний множества хі Є Х в моменты nh — 0 непосредственно перед поступлением заявки в систему при незавершенном обслуживании на первой фазе. Такие вероятности будем задавать векторами где fci = 0, J?i, АГ2 = 0,.
Исходя из простых вероятностных рассуждений и принимая во внимание (3,3), получаем РОДА, = [PoUAi -О (3.4) "(si) Ркф,Аг = №( 1 В0 J) + +Pfttil(i4iB0iBj) /сі = 1,Лі; [3.5) P M = Wk IBl) (З.б) +1/.( - к2)р0тк.2+1(Лі #?)] &2 - ГЖ; Р Иі - Л ( і Во В20)+ (3.7)
Далее рассмотрим ЦМ {I D , га 0}, построенную по моментам непосредственно перед завершением обслуживания заявки на первой фазе при условии, что на второй фазе системы обслуживание не закончилось при наличие на пей заявок. Множество состояний Xfi для ЦМ {%lD , п 0} является подмножеством множества X и имеет вид: ХЬ, = U XkuD ГДС = (( 1 2 1, І=1:1, ji = 1,7711, J2 = 1 т2, fc2 = 0;fi2J,fci = 1,Яі Здесь индексы (i.ji,J2 ki.k-i) обозначают соответственно фазу генерации, фа;-ш обслуживания на верной и второй фазах системы, число заявок на первой и второй фазах системы в моменты непосредственно перед завершением обслуживания заявки на первой фазе.
Алгоритм решения системы уравнений равновесия
Теорема 8. Вероятность 7Гі потери заявки на первой фазе двухфазной марковской системы в результате переполнения буферного накопителя определяется формз лой Да А;2-0 ГҐІ — где вероятность рс, .+. ,к2 — 0. состояния ЦМ, построенной по моментам непосредственно перед поступлением заявки в систему при незавершенном обслуживании на первой фазе и не поступлении на нее отрицательной заявки, находится из (4.27) — (4.30).
Далее рассмотрим механизм потери заявок на второй фазе системы. Если в момент nh + 0 на второй фазе имеется 7 заявок, т.е система находится в одном из состояний {hJuJ2ih,R2)} г= V, Зі = l,mi, j2 = l7m2i fci = 0,Іїі, тогда заявка, обслуживание которой завершилось на первой фазе системы к моменту (п + l)h — 0, потеряется лишь при условии, если заявка, которая обслуживалась на приборе второй фазы в течении п-го такта, не покинет прибор (т.е. ее обслуживание не будет завершено) к моменту (п -\- l)h — 0 и па вторую фазу не поступит отрицательная заявка. Имеет место
Теорема 9. Вероятность щ потери заявки на второй фазе двухфазггой марковской системы в результате переполнения буферного накопителя определяется формулой - Е ЛаЛ - л—7 ХХлЛ1 Ь! &o)QT: (4-35) где вероятность Ь(й 3) завершения обслуживания заявки на первой фазе системы при незавершенном обслуживании на второй фазе системы и не поступлении отрицательной заявки на вторую фазу находится из (4.31).
Далее с учетом выражений (4.34) и (4.35) приходим к соотношению, отражающему взаимосвязь между вероятностями потери заявки на каждой фазе системы и суммарной верояностью 7г потери заявки в системе из-за переполнения буферного накопителя: 1 — 7Г = (l-7Ti)(l-7rS). (4.36) Из (4.36) получаем выражение для расчета суммарной ВерОЯТНОСТИ НОТерИ ЗаЯВКИ В СИСТеме 7Ї\ IL 4.2. Стационарная вероятность потери положительной заявки за счет поступления отрицательной заявки. Как было отмечено в главе 2 отрицательная заявка оказывает на систему свое ff разрушительное "воздействие лишь в том случае, когда система не пуста. Поэтому для нахождения вероятности потери положительной заявки за счет поступления отри і ідтельной заявки на каждой фазе системы необходимо определить вероятность того, что непосредственно перед поступлением на каждую из фаз системы отрицательной заявки на приборе или в накопителе находились заявки.
Рассмотрим сначала систему в моменты непосредственно перед поступлением отрицательных заявок на первую фазу системы. Заявка на первой фазе системы потеряется в случае наступления следующей совокупности событий: за такт па первую фазу системы поступит отрицательная заявка, к моменту ее поступления обслуживание положительной заявки на приборе первой фазы не завершится или завершится, но тогда в накопителе будет ожидать обслуживания хотя бы еще одна заявка; остальные события, связанные с поступлением или обслуживанием заявок на второй фазе могут как происходить, так и нет.
Заметим, что поступающая на n-м такте на первую фазу системы отрицательная заявка застанет в ней в момент непосредственно перед своим поступлением и оказанием Гразрушительного1 воздействия ki других заявок, если на п-и такте на фазе находилось к\ заявок и не завершилось обслуживание заявки на приборе.
В случае завершения обслуживания заявки за n-ый такт, поступающая на фазу на этом такте отрицательная заявка застанет на ней к\ обычных заявок в момент непосредственно перед своим поступлением и оказанием воздействия на СМО, если на п-и такте на фазе находилась к -I- 1 заявка. Этот факт обясняется установленным в 1 порядком наступления событий, произошедших в СМО за такт; сначала обслуженная на п-и такте заявка покидает первую фазу, и только затем отрицательная заявка, поступившая за этот такт, оказывает воздействие на СМО,
Опять же в силу установленного в 1 порядка наступления событий за такт (сначала отрицательная заявка оказывает воздействие на СМО, а затем в очередь помещается положительная заявка, генерация которой завершилась за рассматриваемый такт), вероятность поступления или не поступления новой положительной заявки не учитывается при расчете вероятности потери из-за поступления отрицательной заявки, также не учитываются события, происходящие на второй фазе системы.
