Содержание к диссертации
Введение
Глава 1. Аналитическая модель телекоммуникационных систем с потерей всех принятых данных 23
1.1. Постановка задачи 23
1.2. Аналитическая модель системы с полной потерей данных. Стационарные характеристики 24
1.3. Частный случай модели: система M/MR/n/r с обновлением без дообслуживания 32
1.4. Частный случай модели: система M/MRR/n/r с обновлением и дообслуживанием 36
1.5. Заключение 39
Глава 2. Аналитическая модель телекоммуникационных систем с частичной потерей данных на основе СМО G/M/n/r (г со) с обобщённым обновлением 40
2.1. Построение аналитической модели 41
2.2. Стационарные вероятности состояний 42
2.3. Времена пребывания в накопителе заявок в случае прямых порядков обслуживания и обобщённого обновления
2.4. Прямое обслуживание заявок с инверсионным обобщённым обновлением 54
2.5. Инверсионное обслуживание и прямое обобщённое обновление 64
2.6. Инверсионное обслуживание с инверсионным механизмом обобщённого обновления 71
2.7. Средние стационарные времена пребывания в накопителе «убитой» и обслуженной заявок 79
2.8. Выводы 81
Глава 3. Аналитическая модель расчёта показателей качества функционирования телекоммуникационных систем с частичной потерей данных с помощью СМО GI/M/n/oo с обобщённым обновлением 83
3.1. Описание модели 84
3.2. Стационарные вероятности состояний 85
3.3. Распределения времён пребывания в накопителе потерянной и обслуженной заявок для прямых порядков обобщённого обновления и обслуживания 94
3.4. Прямой порядок обслуживания заявок с инверсионным обобщённым обновлением 99
3.5. Инверсионный порядок обслуживания при прямом порядке обобщённого обновления 108
3.6. Инверсионный порядок обслуживания с инверсионным порядком обобщённого обновления 115
3.7. Выводы 120
Заключение 124
Приложение А. Зависимость среднего времени пребывания заявки в накопителе от дисциплин обслуживания и обобщённого обновления 128
А.1. Пуассоновский входящий поток 129
А.2. Эрланговский входящий поток 135
А.З. Гамма распределение интервалов между поступлением заявок 140
Список иллюстраций 145
Список источников
- Частный случай модели: система M/MR/n/r с обновлением без дообслуживания
- Времена пребывания в накопителе заявок в случае прямых порядков обслуживания и обобщённого обновления
- Распределения времён пребывания в накопителе потерянной и обслуженной заявок для прямых порядков обобщённого обновления и обслуживания
- Инверсионный порядок обслуживания с инверсионным порядком обобщённого обновления
Введение к работе
Актуальность работы
Информационные технологии — один из основных признаков и ресурсов развития совремеиного общества. Для развития и повсеместного внедрения сетей передачи и обработки дапных требуется создание аналитических моделей, адекватно представляющих реальные системы и учитывающих как их характерные особенности, так и возможные из-за воздействия ряда факторов (выход из строя сервера, воздействие вирусов и пр.) потери передаваемых или обрабатываемых дапных. Математические методы теории массового обслуживания (ТМО) (значительный вклад в развитие ТМО и теории телетрафика внесли и продолжают вносить Л.Я. Хинчин, Б.В. Гнеденко,.А.А. Боровков, Д. Кендалл, Д. Литтл, Д. Кокс, В. Смит, Л. Клейнрок, Б.А. Севастьянов, Л. Такач, Ф. Поллачек, П.ІІ. Бочаров, Г.П. Башарип, В.М. Вишневский, А.Н. Дудип, В.А. Ивтщкий, И.Н. Коваленко, В. А. Наумов, А.В. Печинкин, К.Е. Самуилов и др.) позволяют создавать стохастические модели протоколов сетей передачи данных, обеспечивают возможность решения многочисленных задач по расчёту характеристик качества обслуживания (Quality of Service, QoS) и функционирования различных компонент сетей, включая оценку вероятностно-временных характеристик узлов коммутации и маршрутизации, анализ производительности сетей, управления потоками данных, расчёт потерь и загрузки цифровых линий связи при передаче данных, голоса и видеоинформации.
В моделях сетей передачи данных важную роль играют потери заявок по каким-либо внешним или внутренним причинам (поломка прибора, поступление в систему заявок особого вида — отрицательные заявки или поток катастроф, сброс заявок для оптимизации работы системы, нетерпеливость клиентов и пр.) и колебания задержки (разброс максимального и минимального времени прохождения заявки относительно среднего значения). Анализ этих параметров требует построения адекватных аналитических моделей, в частности, на основе систем массового обслуживания (СМО) с обобщённым обновлением. Так, например, задержке соответствует среднее стационарное время пребывания заявки в системе, а колебашда задержки — среднее квадратичное отклонение стационарного времени
пребывания заявки в системе. С помощью обобщённого обновления, введённого и рассмотренного в диссертации, можно вычислить вероятность потери поступившего пакета, среднее число сброшенных пакетов и среднее время пребывания такого пакета в системе.
По данной проблематике написано много работ как теоретического, так и прикладного характера. Одна из таких работ, авторами которой являются Towsley D. и Tripathi S.K1, посвящена разработке вероятностной модели протоколов, обеспечивающих функционирование помехоустойчивых систем. Другая — работа А.Я. Крейнина2, рассматривала модель функционирования системы, в которую поступают потоки команд (заявок) нескольких типов (в том числе поток исполняемых команд) и в которой возможен переход от исполняемой команды к иной команде с потерей промежуточных команд. В дальнейшем3 Л. Я. Крей-нин, введя понятие обновления (полного обновления), предложил обобщающую теоретическую модель для вычисления показателей функционирования систем, подверженных потере поступающих данных.
Диссертация продолжает работы Крейнина и Towsley. В ней расширено понятие обновления — введено понятие обобщённого обновления, что позволяет создавать аналитические модели, применимые для следующих целей:
расчёт показателей качества обслуживания протокола управления потоковой передачей (Stream Control Transmission Protocol — SCTP), а именно: общей задержки передачи сообщения, среднего числа переданных пакетов, среднего количества порций данных, входящих в пакет;
расчёт вероятности сброса поступающего пакета, числа сброшенных пакетов, распределения времени пребывания в системе сброшенного или переданного пакета при реализации механизмов активного управления очередью (Active Queue Management, AQM) — управления числом заявок в системе путём их «случайного» удаления. Удаление пакетов осуществляется в зависимости от значений ряда параметров алгоритма управления. Наиболее распространены алгоритмы типа RED (Random Early Detection), классификацию которых на
lD. Towsley, S. К. TYipalhi A single server priority queue with server failure and queue Hushing. Oper. Res. Lett, 1991;10:353-362.
"Kieinin, A. Queueing system with dumping: Computation and bounds for stability, Fifth International Vilnius Conf. on Prob. Conf. on Prob. and Math. Stats. Abstract of Commun. 3 (1989), 327-328.
3Kreinin A. Queueing Systems with Renovation. .Journal of Applied Moth. Stochast. Analysis, 1997, vol. 10, .V' 4, pp. 431-4«.
русском языке можно посмотреть в работе , алгоритм Drop Tail, алгоритм Blue — сброс пакетов агрегированного потока. При построении аналитической модели можно использовать частный случай обобщённого обновления;
оптимизация работы как IP-сети2 (активное управление очередями — Active Queue Management (AQM), — во избежание как перегрузок каналов передачи данных, маршрутизаторов, так и во избежание пх простоя), так, к примеру, и сетей третьего поколения (3G)3;
анализ компьютерных систем, подверженных воздействию вирусов, приводящих к потере данных (возможная потеря сообщений в результате обработки инфицированного сообщения );
исследование систем с ненадёжными приборами (моментальное восстановление прибора);
анализ узлов G-сетей (обобщённое обновление можно рассматривать как 1) результат поступления в систему потока триггеров (сигналов) — заявок, которые могут с некоторой вероятностью становиться отрицательными и, тем самым, привести к потери иных («нормальных») заявок0; 2) результат появления заявок типа «reset»0, сокращающих размер накопителя в СМО);
управление временем ожидания обслуживания, динамическое распределение ресурсов системы7;
обеспечение необходимого качества услуг (Quality of Service — QoS) в компьютерных сетях8;
Королькова А. В., Куллбив Д. С, Черноишноа А. И. К вопросу о классификации алгоритмов RED // Вестник РУДН. Серия «Математика. Информатика. Физика.» Л"« 3. 2009. С. 34—46
2см, например, нераую работу но дайной тематике — Floyd, S., Jacobson. V., Random Early Detection gateways for Congestion Avoidance, IEEE/ACM Transactions on Networking, V.l N.4, August 1993, P. 397-413.
3M. Sagfors, R. Ludwig, M. Meyer, and J. Peisa, Queue management for TCP Traffic over 3G Links, Wireless Communications and Networking, 2003. WCNC 2003
*Krishna Kumar В., Arivudainanihi D., Krishnamoortfiy A, Some results on a generalized M/G/l feedback queue with negative customers // Aim Oper Res (2006) 143: 277-29S
5 Gelenbe E. G-Xetworks with triggered customer movement // Journal of Applied Probability, Vol. 30, Xo.
3, pp 742-748, 1993.
6 Gelenbe E, Foumeau M G-networks with resets // 2002, Performance Evaluation 49, 179-192.
7Semmova O.V., Dndin A.N. M/M/N queuemjr system with controlled service mode and disaster. // Automat. Control Comput. Sci. 2007. V. 41. No. 6. P. 350-357.
lEral Gelenbe, AHura Nunez Self-Aware Networks and Quality of Service // O. Kaynak et al. (Eds.): ICANX/ICONfP 2003, LNCS 2714, pp. 901-908, 2003.
— моделирование и оптимизация работы call-центров и центров обслуживания sins-сообщений (потеря ожидающих обслуживание клиентов). Задача диссертации — оценка эффективности телекоммуникационных систем, а именно: построение аналитических моделей расчёта показателей функционирования (задержка обслуживания, потеря пакетов) телекоммуникационных систем с помощью СМО с обобщённым обновлением. Анализ различных вариантов дисциплин обслуживаїшя и обобщённого обновления в построенной аналитической модели позволяет выбрать оптимальный вариант касательно задержки, т.е. вариант с наименьшим значением задержки — среднего времени пребывания в системе. Эта задача является актуальной и имеет практическую ценность. Кроме того, изучение систем с обобщённым обновлением имеет и теоретическую ценность, так как данные системы являются обобщением ряда СМО.
Цель диссертационной работы
-
Построение аналитических моделей вычисления таких показателей функционирования телекоммуникационных систем как задержка передачи сообщения, колебание задержки, вероятность потери поступившего пакета, число потерянных пакетов с помощью марковских систем с полным обновлением (с дообслу-живанием и без) на основе уже существующих методов, а также с помощью системы GI/M/n/r (г < со) с обобщённым обновлением;
-
Разработка программно ориентированных алгоритмов расчёта вероятностно-временных характеристик — стационарных распределений числа заявок в системе (по моментам поступления заявок в систему и в произвольные моменты времени) и вывод функций стационарных распределений времён пребывания в накопителе «убитой», обслуженной и произвольной заявок (либо в терминах преобразований Ланласа-Стилтьеса и производящих функций, либо в явном виде) для следующих вариантов обобщённого обновления и дисциплины обслуживания: прямой порядок обобщённого обновления (заявки «убиваются» в накопителе в порядке поступления) при дисциплине обслуживания в порядке поступления (FIFO), инверсионный порядок обобщённого обновления (заявки «убиваются» в накопителе в порядке, обратном поступлению) при дисциплине
YanijWno Shin Multi-server retrial queue with negative customers and disasters // Queueing Syst (2007) 55: 223-237
Jolai, F. and Aaadzadch, 5. M. and Tatjhizade.h, M. R. Performance estimation of an email contact renter by a finite source discrete time Geo/Geo/1 queue with disasters // Comput. Ind. Eng. (2008) V. 55. No 3:543-556
обслуживания FIFO, прямой порядок обобщённого обновления при инверсионном порядке обслуживания (LIFO), инверсионный порядок обобщённого обновления при дисциплине обслуживания LIFO, — с последующим выбором комбинации дисциплин обслуживания и обновления, оптимальной согласно одному из параметров качества функционирования телекоммуникационных систем — времени задержки.
Результаты, выносимые на защиту
-
Предложен аналитический метод нахождения показателей функционирования (стационарного распределения числа заявок) инфокоммуиикационных систем, моделируемых с помощью марковских СМО с обновлением на основе обобщённого процесса размножения и гибели.
-
Для телекоммуникационных систем (с возможным сбросом данных для улучшения функционирования или из-за воздействия ряда факторов, например, таких как выход из строя сервера) па основе СМО G/M/n/r, г < со с обобщеппым обновлением разработаны аналитические алгоритмы расчёта вероятностно-временных характеристик: стационарных распределений числа заявок, функций распределения времён пребывания в накопителе (системе) «убитой», обслуженной и произвольной заявок для различных вариантов обобщённого обповления и дисциплин обслуживания.
Доказано, что для произвольной заявки вне зависимости от вариантов обслуживания и обобщённого обновления время пребывания в накопителе имеет одно и тоже распределение. Кроме того, показано, что, меняя дисциплины обслуживания и обобщённого обновления при неизмешгых начальных условиях, можно уменьшать (увеличивать) время пребывания в накопителе (системе) обслуженной («убитой») заявки, т.е. изменять значения задержки — одного из параметров AQM.
Научная новизна
Все основные результаты диссертации являются новыми. Отличие от предыдущих работ по системам с (полным) обновлением — введено обобщённое обновление, модели строятся при помощи многолинейных СМО. На основе рассмотренных в диссертации СМО предложен отличный от классического подход к по-
строению аналитических моделей апализа качества функционирования систем с RED-подобными алгоритмами. Кроме того, аналитическая модель с обобщённым обновлением пригодна для расчёта показателей качества обслуживания протокола управления потоковой передачей (SCTP), а именно: общей задержки передачи сообщения, среднего числа переданных пакетов, среднего количества порций данных, входящих в пакет; причём эта модель отлична от изученных ранее другими авторами. Кроме того, в диссертации рассмотрено несколько вариантов комбинаций дисциплин обслуживания поступающих заявок и обобщённого обновления с целью выбрать оптимальную по значениям среднего времени ожидания обслуживания (пребывания в системе), т.е. с наименьшими значениями задержки.
Методы исследования
В работе используются методы теории вероятностей, теории случайных процессов, теории массового обслуживания и численные методы.
Обоснованность и достоверность результатов
Обоснованность полученных результатов следует из того, что на всех этапах построения аналитических моделей расчёта показателей качества функционирования телекоммуникационных систем, а также для аналитического и численного анализа полученных решений использовались строгие и проверенные методы.
Достоверность теоретических результатов диссертации подтверждена численными расчётами на основе программных модулей для анализа моделей СМО GI/M/n/r и GI/M/ti/oq с обобщённым обновлением и их частных случаев, которые допускают расчёт по упрощённым алгоритмам.
Теоретическая и практическая ценность
Математические методы и вычислительные алгоритмы, разработанные в диссертации, могут применяться для расчёта и анализа характеристик: качества обслуживания протокола управления потоковой передачей, компьютерных систем, подверженных воздействия вирусов, систем с выходом из строя обслуживающего прибора (сервера) с последующим моментальным восстановлением; и ориентированы на применение в различных сетях и автоматизированных системах.
Созданные на основе полученных теоретических результатов программы позволяют производить расчёт таких систем при их проектировании.
Исследования проводились в рамках грантов Российского фонда фундаментальных исследований (РФФИ) № 06-07-89056-а «Математические модели, методы, алгоритмы и программное обеспечение, основанное на веб-технологиях, для проведения фундаментальных исследований в области анализа производительности сетевых систем» и № 09-07-12032-офи_м «Разработка математические методов, вычислительных алгоритмов и программных средств для решения задач моделирования информационно-вычислительных и телекоммуникационных систем».
Реализация результатов работы
Результаты диссертации использовались в научно-исследовательских работах (НИР), проводимых Институтом проблем информатики Российской академии наук:
-
Разработка общих базовых математических методов расчёта систем массового обслуживания, функционирующих в дискретном времени.
-
Исследование систем и сетей массового обслуживания специального вида и информационно-управляющих систем с новыми видами обратной связи.
-
Исследование систем и сетей массового обслуживания специального вида с ненадёжными приборами и отрицательными заявками.
Результаты исследований вошли в программу «WEB-ориентировагшый программный комплекс удалённого расчёта стационарных характеристик систем массового обслуживания», дата регистрации РОСПАТЕНТом 11. 01. 2010г., номер свидетельства о регистрации № 2010610026.
Апробация работы
Результаты, полученные в ходе выполнения работы, были представлены на:
XLII-XLV1 Всероссийских конференциях по проблемам математики, информатики, физики и химии. Москва, Российский университет дружбы народов (РУДН), 2006-2010 гг.;
международной конференции «Mathematical Methods in Reliability. Theory. Methods. Applications.» - MMR2009 (22-29 июня 2009, Москва);
международной конференции «International Conference on Ultra Modern Telecommunications» - ICUMT 2009 (12-14 October 2009, St.-Petersburg, Russia);
международной конференции «International Conference on Ultra Modern Telecommunications» - ICUMT 2010 (18-20 October 2010, Moscow, Russia);
научных семинарах кафедры теории вероятностей и математической статистики РУДН (Москва 2006-2010).
Публикации
По теме диссертации опубликовано 14 работ (из них 7 — тезисы докладов на всероссийских и международных конференциях, 7 — статьи, причём 4 из них опубликованы в ведущих рецензируемых научных журналах и изданиях, определённых Высшей аттестационной комиссией), основные из которых приведены в конце автореферата, а с полным списком можно ознакомиться в диссертации. Основные результаты представлены в работах, опубликованных в изданиях, рекомендованных ВАК, и подучены лично соискателем. В работах, опубликованных в соавторстве, личный вклад соискателя состоит в построении аналитических моделей, получении, обосновании и интерпретации полученных результатов.
Структура и объем диссертации
Частный случай модели: система M/MR/n/r с обновлением без дообслуживания
Глава посвящена дальнейшему развитию идеи обновления (полного обновления), расмотренного в предыдущей главе и работах [28,29,93-96], в построении аналитических моделей различных телекоммуникационных систем. В отличие от предыдущих работ по данной тематике и от первой главы здесь рассматривается обобщённое обновление. Полученные выражения можно применять, в частности, для нахождения оценки показателей качества обслуживания протокола управления потоковой передачей (SCTP) [30-32], а именно: общей задержки передачи сообщения (среднее время пребывания в системе обслуженной заявки), среднего числа переданных пакетов (среднее число обслуженных заявок), среднего количества порций данных, входящих в пакет (среднее число «убитых» заявок плюс один), построенная таким образом аналитическая модель будет отлична от рассматривавшихся ранее, к примеру в работах Н.В. Першакова и К.Е. Самуйлова [33-35,108] либо для оценки некоторых алгоритмов управления трафиком (алгоритмы типа RED [36,37,39], Drop Tail). 2.1. Построение аналитической модели
Рассмотрим n-линейную систему массового обслуживания (СМО) G/M/n/r с конечным накопителем ёмкости г и обобщённым обновлением.
Входящий в систему поток является рекуррентным, причём время между соседними поступлениями заявок имеет произвольную функцию распре оо деления Л(х). Будем предполагать, что среднее время а = J xdA(x) между поступлениями заявок конечно. Кроме того, там, где речь пойдёт о стационарных вероятностях по времени, будем предполагать, что время между поступлениями заявок не может принимать только значения am, где а О, am — целое число.
Времена обслуживания заявок на приборах являются независимыми одинаково распределёнными по экспоненциальному с параметром ц закону случайными величинами. Заявки обслуживаются в порядке поступления. Заявка, заставшая в момент поступления в системе п заявок на приборах и г заявок в накопителе, теряется.
Обобщённое обновление определяется следующим образом. Находящаяся па приборе заявка в момент окончания обслуживания одновременно с уходом из системы либо с вероятностью q(l) «убивает» в накопителе ровно I заявок, если в нем находится более I заявок, либо с вероятностью Q(l) = 2 q(k) полностью опустошает накопитель, если в нем было не бо к=1 лее I заявок. Вероятности q(l) при / 0 будем называть вероятностями г обновления. Очевидно, что Q(0) — 5Z?(0 = 15 а р = д(0) представляет собой вероятность того, что закончившая обслуживание на приборе заявка покидает систему, не выбивая заявок из накопителя.
Отметим, что при р=1 рассматриваемая система превращается в стандартную систему G/M/n/r, а при q(r) = 1 получаем систему с обновлением, рассмотренную в предыдущей главе и работах [27-29].
В этой части в терминах преобразований Лапласа-Стилтьеса (ПЛС) получим стационарные распределения времён пребывания в накопителе «убитой» и обслуженной заявок для следующих случаев: — заявки обслуживаются и «убиваются» в порядке поступления {FIFO /First); — инверсионное обобщённое обновление при обслуживании в порядке поступления (FIFO /Last)] — инверсионное обслуживание заявок при прямом порядке обобщённого обновления (LIFO/First); — инверсионные порядки обслуживания и обновления (LOFO/Last).
Исследование данной системы проведём с помощью вложенной цепи Маркова (см., например, [15,16,109]), образованной числами (тп+0) заявок в системе в моменты времени тп + 0, где тп — момент поступления п-й заявки. Множество состояний имеет вид А = {1,...,п + г}.
Выпишем матрицу переходных вероятностей вложенной цепи Маркова. Для этого введём обозначения: — ттт(к) — вероятность того, что за время х систему покинет ровно к за явок, при условии, что за это время обслужится ровно т, к т, заявок и новые заявки в систему не поступят; — Щп{к) — вероятность того, что в конце временного интервала х в системе останется п — 1 заявок, при условии, что в начальный момент было п + к — 1 заявок, а за время х обслужится ровно m, т /с, заявок и новые заявки в систему не поступят. Для тгт(к) и 7гт(к) справедливы следующие рекуррентные соотношения: 7ri(A0 = g(fc-l), : = T7F (2.1) fc-i я"т(&) = XI m-i n k-i), ra = 2,r, k = rn/r, (2.2) i=m—1 7ri(fc) = Q(fc-l) fc = l,r + l, (2.3) fc-i їїт{к) = X 7ггп_і(г)-л:1(А; - г), m = 2,r + l, A; = m,r + 1. (2.4) i=m— 1 Далее, пусть: F} (x) — условная вероятность того, что за время х систему покинет ровно А; заявок, при условии, что в начальный момент в системе было не менее п + к, к = 0, г, заявок и за время х в систему не поступили новые заявки; Fk,w(%) — условная вероятность того, что за время х систему покинет к — w заявок, при условии, что в начальный момент в системе было к, /с = 1,п + г, и; = 0, п — 1, заявок и за время х в систему не поступили новые заявки; Ак — вероятность того, что между поступлениями заявок систему покинет ровно к заявок, при условии, что в начальный момент их было не менее п + к, к = 0, г; Ak,w — вероятность того, что между поступлениями заявок систему покинет ровно к — w заявок, при условии, что в начальный момент их было к, k = l,n j-r, w — Q,n — l). Функции Fk(x) и Fk,w(x) с учётом (2.1)-(2.4) представимы в виде
Времена пребывания в накопителе заявок в случае прямых порядков обслуживания и обобщённого обновления
Покажем, как получены (2.32)-(2.36), на примере (2.34) и (2.35). Пусть перед некоторой (выделенной) заявкой в накопителе находится г, і = 1, г — 2, а после неё ещё j, j = 0, г — г — 2, заявок. Эта заявка может быть «убита» в момент х ещё до поступления новой заявки в систему, если в момент х обслужится последняя, 7тг-я, т = 1,г + 1, из т обслуженных за время х заявок, до ее ухода в накопителе будет «убито» менее j + 1 заявок, а после ухода — не менее j + 1 заявок (с плотностью вероятностей й-1 umj+i(x)), а новая заявка не поступит до момента х (с вероятностью т=\ Л(х)). Такой случай отражён первым слагаемым (2.34). Если же новая заявка поступит в систему в момент у х (с плотностью вероятностей а(у)), то за время до поступления новой заявки могут обслужиться m, т = 1,г, заявок и в накопителе может быть «убито» к, к — 0,j, заявок (с г j вероятностью 2 ит,к(у))- Тогда после прихода в систему новой заявки т-0 к-0 перед выделенной заявкой в очереди на обслуживание будет находиться уже і — т, а после неё j — к + 1 заявок, и выделенная заявка будет «убита» в момент х с плотностью вероятностей w\ ._к+і{х — у). Суммируя по всем промежуточным моментам у, получаем второе слагаемое (2.34). Наконец, если до момента у поступления новой заявки в систему ни на одном из приборов не закончится обслуживание, то число заявок, стоящих после выделенной, увеличится на одну, что даёт нам третье слагаемое (2.34). Пусть теперь система заполнена полностью, т.е. перед выделенной заяв кой находится г, і — 1, г — 2, а после неё г —г —1 заявок. От рассмотренного выше этот случай отличается только тем, что, если за время у ни на одном из приборов не закончится обслуживание, то поступающая в систему заявка будет потеряна и перед выделенной заявкой в накопителе по-прежнему будут находиться г, а после неё г — г — 1 заявок. Эти рассуждения приводят к выражению (2.35). m=l rn=l Решение данной системы можно найти следующим образом. ПЛС wo-i(s) непосредственно определяется из уравнения (2.38). Затем из уравнения (2.37) при j — г — 2 ПЛС о-2(5) выражается через or-i(s) из этого же уравнения при j = г — 3 ПЛС WQ г з(в) выражается через ш sl2(s) и т.д. Таким образом, каждое ПЛС щss (s), j = 0, г — 2, однозначно определяется через о;о!!{. Аналогичным образом из соотношений (2.40), (2.39) последовательно по г = l,i— 2 вычисляются через WQ!!{ ПЛС w\ (re), а из соотношения (2.41) — ПЛС OJ Q(S).
Для вычисления в терминах ПЛС cu oss\s) стационарного распределение времени пребывания в накопителе «убитой» заявки осталось воспользоваться формулой (2.21).
Снова рассмотрим некоторую (выделенную) заявку, перед которой в очереди на обслуживание находится г, г = l,r — 2, а после неё — ещё j, j — 0,r — і — 2, заявок. Эта заявка может начать обслуживаться на приборе в момент времени х ещё до поступления новой заявки в систему, если за время х обслужатся і + 1 заявок и при этом она не будет «убита», то есть из накопителя будет выбито не более j стоящих после неё заявок з (с плотностью вероятностей Y2 иі+іЛх))і а новая заявка не поступит до момента х (с вероятностью Л(х)). Этот случай соответствует первому слагаемому (2.44). Если же новая заявка поступит в систему в момент времени у х (с вероятностью dA(y)), то за время до поступления новой заявки могут обслужиться т, т = 0, г, заявок и из накопителя может быть потеряно к, к = 0,j, заявок (с вероятностью Y1 т,к(у))- При этом га=0 к=0 после прихода новой заявки перед выделенной заявкой в накопителе будет уже находиться г — т заявок, а после неё — j — к + 1 заявок, и она сможет начать обслуживаться в момент времени х с плотностью вероятностей Щ-т j-k+i(x У)- Суммируя по всем промежуточным моментам у, получим второе слагаемое (2.44). Наконец, третье слагаемое в (2.44) соответствует случаю, когда до момента у поступления новой заявки в систему ни на одном из приборов не закончится обслуживание и число заявок, стоящих после выделенной, увеличится на единицу.
Пусть теперь система заполнена полностью, т.е. перед выделенной заявкой находится і, і — 1, г — 2, а после неё г—г — 1 заявок. От рассмотренного выше этот случай отличается только тем, что, если за время у до прихода новой заявки ни на одном из приборов не закончится обслуживание, то поступающая в систему заявка будет потеряна и перед выделенной заявкой в накопителе по-прежнему будут находиться г, а после неё г — г — 1 заявок.
Распределения времён пребывания в накопителе потерянной и обслуженной заявок для прямых порядков обобщённого обновления и обслуживания
Однако в формуле (3.17) осталась неизвестной функция ipo(z,s). Для её нахождения рассмотрим уравнение а это означает, что функция f(u) — f(u, z, s) на интервале (0,1) является выпуклой вверх при всех 0 -г 1 и s 0. Учитывая (3.19), получаем, что на отрезке [0,1] уравнение (3.18) имеет ровно одно решение, которое обозначим через u(z,s).
Заметим теперь, что во всех точках (z,u,s), 0 z, u 1 и s 0, в том числе и в точках (z,u(z, s), s), функция ip(z,u, s) является непрерывной. Но тогда, поскольку в точках (z,u(z,s),s) знаменатель (3.17) обращается в нуль, то в нуль должен обращаться и числитель этой формулы, т.е.
Отметим, что в окончательное выражение (3.21) для ПЛС стационарного распределения времени ожидания начала обслуживания принятой к обслуживанию заявки входит только функция ipo(g,s). Тройное преобразование ip(z,u,s) использовалось лишь для нахождения этой функции.
Дифференцируя выражения (3.20) и (3.21) по s в точке (z = д, 5 = 0), можно вычислить моменты любого порядка стационарного распределения времени пребывания в накопителе обслуженной заявки. В частности, производя элементарные преобразования и учитывая равенство (3.2), получаем, что стационарное среднее время пребывания в накопителе обслуженной заявки определяется формулой
Поскольку время пребывания в системе обслуженной заявки состоит из времени ожидания начала обслуживания и собственно времени обслуживания на приборе, то ПЛС {Kserv)(s) стационарного распределения времени ожидания начала обслуживания обслуженной заявки имеет вид
По аналогии с подразделом 3.4.1 обозначим через И (ж), I 0, к 0, вероятность того, что заявка, перед которой в начальный момент 0 в очереди находилось I других заявок, а после неё — к заявок, будет «убита», причём до момента х, при условии, что начальный момент 0 совпал с мо (loss) / \ /TIr(loss) / \\/ ментом поступления заявки в систему, и положим wl к [х) = [Wik [X)) . Для вывода уравнений, которым удовлетворяют w\k(x), I 0, к О, как и раньше, предположим, что перед выделенной заявкой в накопителе находится I, I 0, заявок, а после неё — ещё к, к 0, других заявок. В момент х выделенная заявка будет «убита» в одном из двух случаев: 1) либо если в этот момент окончится обслуживание (га + 1)-й заявки, га = 0, /, и до её ухода будет «убито» не более к заявок, а после её ухода с учётом ранее выбитых будет «убито» более к заявок (с плотностью вероятностей (nfi)m+1xme linx J2 m+i{k + l)/m\), и новая заявка до момента х в систему j=o _ не поступит (с вероятностью Л(х)); 2) либо в некоторый промежуточный момент у, 0 у х, поступит новая заявка (с плотностью вероятностей а(у)), до её поступления обслужится г, г = 0,1, заявок и будет «уби к
Приведем также выражение для стационарного среднего времени пребывания в системе «убитой» заявки: Стационарное распределение времени пребывания в накопителе произвольной заявки имеет ПЛС (1 - g)[s + nfi - пцдіт(и(д, s))] Дифференцируя последнюю формулу по 5 в точке s = 0, получаем следующее выражение для стационарного среднего времени пребывания в накопителе произвольной заявки: W = -W (0) = —у Г Рп-1- (3-24)
Это выражение совпадает с аналогичным выражением для той же системы, но при прямых порядках об 108 новления и выбора из очереди на обслуживание (см.3.13). Однако моменты более высоких порядков, в частности дисперсия, будут, вообще говоря, различными.
Обозначим, как и ранее, через w\s (ж), I 0, к 0, плотность вероятностей того, что в момент х выделенная заявка поступит на прибор, при условии, что в начальный момент времени перед этой заявкой в накопителе находилось I других заявок, после неё — к заявок и начальный момент совпал с моментом поступления заявки в систему (поступившая заявка будет либо выделенной, если к = 0, либо последней в очереди, если к 1).
Инверсионный порядок обслуживания с инверсионным порядком обобщённого обновления
Для системы с бесконечным накопителем, конечным числом приборов (п = 5), с экспоненциальным обслуживанием заявок на приборах (интенсивность обслуживания р), пуассоновским входящим потоком заданной интенсивности Л и вероятностями q(k), к 0} обобщённого обновления, имеющими геометрическое распределение с параметром q, q(k) = (1 — q)qk, к 0, на рис. А.1-А.З показана зависимость средних времён пребывания в накопителе обслуженной u/serv) и «убитой» w(loss) заявок от вероятности q. Рассматриваются три варианта загрузки р системы: малая — р = 0.2, средняя — р = 0.5 и большая -р«1. Также на рис. А.1-А.З представлена зависимость вероятностей «убийства» или обслуживания поступившей в систему заявки (p(/oss) и p(serw) соответственно) от параметра q геометрического распределения.
На рис. А.4-А.6 представлены графики поведения средних времён пребывания в накопителе «убитой» {w loss ) и обслуженной (w serv ) заявок для дисциплин FIFO/First, LIFO/First и LIFO/Last обслуживания и обобщённого обновления относительно дисциплины FIFO/Last (стандартная для
Поведение дисциплин обслуживания и обновления относительно друг друга при средней загрузке системы алгоритмов семейства RED). Задержка (среднее стационарное время w serv пребывания в накопителе обслуженной заявки) для дисциплины FIFO /Last является максимальной. Минимальные значения w serv принимает для случая LIFO/First. Значения w serv в случае прямых (FIFO/First) и инверсионных (LIFO/Last) порядков обслуживания и обобщённого обновления малоразличимы.
На рис. А.7-А.9 представлены графики поведения p(loss\ p(serv)! w(loss) и w(sery} при предположении о пуассоновском распределение вероятно-стей обобщённого обновления (q(k) Зависимость p(loss\ p(serv) w(loss) и w(serv) от параметра Ao пуассоновского распределения вероятностей обобщённого обновления при малой загрузке системы но поведение средних времён пребывания в накопителе «убитой» (ги 05 ) и обслуженной ( u/se)) заявок для дисциплин FIFO/First, LIFO/First и LIFO/Last обслуживания и обобщённого обновления относительно дисциплины FIFO/Last.
Минимальные значения w serv принимает для случая LIFO/First, максимальные — для FIFO/Last при малой загрузке. При среднихи больших значениях загрузки системы наибольшие значения w serv принимает для варианта LIFO/Last, минимальные — при LIFO/First. Pk» Р-П-
Все параметры системы аналогичны предыдущим за одним исключением — входящий поток заявок является эрланговским с параметром т = 2. На рис. А.13-А.15 представлены графики зависимости вероятностей p oss) и p(serv\ а также средних времён w loss и w serv от значений параметра q геометрического распределения вероятностей обобщенного обновления. На рис. А.16-А.18 представлено поведение w loss и w serv для дисциплин FIFO/First, LIFO/First и LIFO/Last обслуживания и обобщённого обновления относительно дисциплины FIFO/Last.
Рис. А.19-А.24 представляют поведение p(loss\ (5егг,)) w(loss) и w(serv) ПрИ пуассоновском распределении вероятностей обобщённого обновления.
Поведение K/ZOSS) и w/se) в случае геометрического распределения вероятностей обобщённого обновления аналогично случаю пуассоновского входящего потока, для пуассоновского распределения вероятностей обобщённого обновления картина иная — w serv максимально для дисциплины
В заключение рассмотрим еще один вариант входящего потока заявок, когда времена между поступлением заявок имеют гамма распределение с параметрами А и 7 = 0-8. В случае геометрического распределения вероятностей q(l), I 0 обобщённого обновления (рис. А.25-А.30) ситуация аналогична рассмотренным ранее случаям (рис. А.1-А.6 и рис. А.13-А.18). В случае пуассоновского распределения вероятностей q(l), I 0 — рис. А.31-А.36, ситуация иная. Максимальные значения среднее время пребывания в накопителе обслуженной заявки w serv принимает для дисциплины LIFO/Last (при любых значениях параметра пуассоновского распределения для средней и большой загрузке системы) и лишь при значениях параметра Ло пуассоновского распределения, больших 2.7, w(se) при дисциплине FIFO/Last принимает наибольшие (относительно других вариантов обслуживания и обновления) значения. Но во всех случаях при дисциплине LIFO/First среднее время ожидания обслуживания uMerv имеет минимальные значения.
