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

На правах рукописи

Зарядов Иван Сергеевич

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

обновления

05.13.17 — теоретические основы информатики

Автореферат

диссертации на соискание учёной степени кандидата физико-математических наук

1 8 НОЯ 2010

Москва — 2010

004613382

Работа выполнена на кафедре теории вероятностей и математической статистики Российского университета дружбы народов

Научный руководитель:

доктор физико-математических наук, профессор Александр Владимирович Печинкин

Официальные оппоненты:

доктор физико-математических наук, профессор Владимир Георгиевич Ушаков

кандидат физико-математических наук, доцент Пётр Викторович Шнурков

Ведущая организация:

Учреждение Российской академии наук Институт проблем управления им. В. А. Трапезникова РАН

Защита состоится «26» ноября 2010 г. в 16 ч. 30 мин. на заседании диссертационного совета Д 212.203.28 при Российском университете дружбы народов по адресу: г. Москва, ул. Орджоникидзе д. 3, ауд. 110.

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

Автореферат разослан «. 22. » октября 2010 г.

Учёный секретарь ( диссертационного совета

М. Б. Фомин

Общая характеристика работы

Актуальность работы

Информационные технологии — один из основных признаков и ресурсов развития современного общества. Для развития и повсеместного внедрения сетей передачи и обработки дапных требуется создание аналитических моделей, адекватно представляющих реальные системы и учитывающих как их характерные особенности, так и возможные из-за воздействия ряда факторов (выход из строя сервера, воздействие вирусов и пр.) потери передаваемых или обрабатываемых данных. Математические методы теории массового обслуживания (ТМО) (значительный вклад в развитие ТМО и теории телетрафика внесли и продолжают вносить Л.Я. Хинчин, Б.В. Гнеденко,.A.A. Боровков, Д. Кендалл, Д. Литтл, Д. Кокс, В. Смит, JL Клейнрок, Б.А. Севастьянов, JI. Такач, Ф. Поллачек, П.П. Бочаров, Г.П. Башарип, В.М. Вишневский, А.Н. Дудип, В.А. Ивтщкий, И.Н. Коваленко, В. А. Наумов, A.B. Печинкин, К.Е. Самуилов и др.) позволяют создавать стохастические модели протоколов сетей передачи данных, обеспечивают возможность решения многочисленных задач по расчёту характеристик качества обслуживания (Quality of Service, QoS) и функционирования различных компонент сетей, включая оценку вероятностно-временных характеристик узлов коммутации и маршрутизации, анализ производительности сетей, управления потоками данных, расчёт потерь и загрузки цифровых линий связи при передаче данных, голоса и видеоинформации.

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

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

По данной проблематике написано много работ как теоретического, так и прикладного характера. Одна из таких работ, авторами которой являются Towsley D. и Tripathi S.K1, посвящена разработке вероятностной модели протоколов, обеспечивающих функционирование помехоустойчивых систем. Другая — работа А.Я. Крейнина2, рассматривала модель функционирования системы, в которую поступают потоки команд (заявок) нескольких типов (в том числе поток исполняемых команд) и в которой возможен переход от исполняемой команды к иной команде с потерей промежуточных команд. В дальнейшем3 А. Я. Крей-нин, введя понятие обновления (полного обновления), предложил обобщающую теоретическую модель для вычисления показателей функционирования систем, подверженных потере поступающих данных.

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

— расчёт показателей качества обслуживания протокола управления потоковой передачей (Stream Control Transmission Protocol — SCTP), a именно: общей задержки передачи сообщения, среднего числа переданных пакетов, среднего количества порций данных, входящих в пакет;

— расчёт вероятности сброса поступающего пакета, числа сброшенных пакетов, распределения времени пребывания в системе сброшенного или переданного пакета при реализации механизмов активного управления очередью (Active Queue Management, AQM) — управления числом заявок в системе путём их «случайного» удаления. Удаление пакетов осуществляется в зависимости от значений ряда параметров алгоритма управления. Наиболее распространены алгоритмы типа RED (Random Early Détection), классификацию которых на

1D. Towsley, S. K. Tnjialki A single server priority queue with server failure and queue flushing. Oper. Res. Lett., 1991;10:353-362.

2Kieinm, 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 Math. Stochast. Analysis, 1997, vol. 10, ■V' 4, pp. 431-413.

русском языке можно посмотреть в работе1, алгоритм Drop Tail, алгоритм Blue — сброс пакетов агрегированного потока. При построении аналитической модели можно использовать частный случай обобщённого обновления;

- оптимизация работы как IP-сети2 (активное управление очередями — Active Queue Management (AQM), — во избежание как перегрузок каналов передачи данных, маршрутизаторов, так и во избежание пх простоя), так, к примеру, и сетей третьего поколения (3G)'1;

- анализ компьютерных систем, подверженных воздействию вирусов, приводящих к потере данных (возможная потеря сообщений в результате обработки инфицированного сообщения4);

- исследование систем с ненадёжными приборами (моментальное восстановление прибора);

- анализ узлов G-сетей (обобщённое обновление можно рассматривать как 1) результат поступления в систему потока триггеров (сигналов) — заявок, которые могут с некоторой вероятностью становиться отрицательными и, тем самым, привести к потери иных («нормальных») заявок5; 2) результат появления заявок типа «reset»0, сокращающих размер накопителя в СМО);

- управление временем ожидания обслуживания, динамическое распределение ресурсов системы7;

- обеспечение необходимого качества услуг (Quality of Service — QoS) в компьютерных сетях8;

1 Каролькова А. В., Кулхбов Д. С., Черпоиьанаа А. И. К вопросу о классификации алгоритмов RED // Вестник РУДН. Серия «Математика. Информатика. Физика.» Л'« 3. 2009. С. 34—46

2см, например, иерьую работу по дайной тематике — Floyd. S., Jacohson. 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

4Krishna Kumar В., Ariuudainambi D., Krishnamoortfiy A. Some results on a generalized M/G/l feedback queue witll negative customers // Aim Oper Res (2006) 143: 277-296

5 Gelenbe E. G-Xetworks with triggered customer movement // Journal of Applied Probability, Vol. 30, Xo. 3, pp 742-748, 1993.

6 Gelenbe E, Fov.mea.xi JM G-networks with resets // 2002, Performance Evaluation 49, 179-192.

7Semenova O.V., Dndin A.N. M/M/N queueing system with controlled service mode and disaster. //

Automat. Control Comput. Sci. 2007. V. 41. No. 6. P. 350-357.

sErol Gelenbe, AHuro Nunez Self-Aware Networks and Quality of Service // O. Kaynak et al. (Eds.): ICANX/ICONfP 2003, LNCS 2714, pp. 901-908, 2003.

— моделирование и оптимизация работы call-центров1 и центров обслуживания sins-сообщений2 (потеря ожидающих обслуживание клиентов). Задача диссертации — оценка эффективности телекоммуникационных систем, а именно: построение аналитических моделей расчёта показателей функционирования (задержка обслуживания, потеря пакетов) телекоммуникационных систем с помощью СМО с обобщённым обновлением. Анализ различных вариантов дисциплин обслуживания и обобщённого обновления в построенной аналитической модели позволяет выбрать оптимальный вариант касательно задержки, т.е. вариант с наименьшим значением задержки — среднего времени пребывания в системе. Эта задача является актуальной и имеет практическую ценность. Кроме того, изучение систем с обобщённым обновлением имеет и теоретическую ценность, так как данные системы являются обобщением ряда СМО.

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

1. Построение аналитических моделей вычисления таких показателей функционирования телекоммуникационных систем как задержка передачи сообщения, колебание задержки, вероятность потери поступившего пакета, число потерянных пакетов с помощью марковских систем с полным обновлением (с дообслу-живанием и без) на основе уже существующих методов, а также с помощью системы GI/M/n/r (г < сю) с обобщённым обновлением;

2. Разработка программно ориентированных алгоритмов расчёта вероятностно-временных характеристик — стационарных распределений числа заявок в системе (по моментам поступления заявок в систему и в произвольные моменты времени) и вывод функций стационарных распределений времён пребывания в накопителе «убитой», обслуженной и произвольной заявок (либо в терминах преобразований Ланласа-Стилтьеса и производящих функций, либо в явном виде) для следующих вариантов обобщённого обновления и дисциплины обслуживания: прямой порядок обобщённого обновления (заявки «убиваются» в накопителе в порядке поступления) при дисциплине обслуживания в порядке поступления (FIFO), инверсионный порядок обобщённого обновления (заявки «убиваются» в накопителе в порядке, обратном поступлению) при дисциплине

* YanijWtm Shin Multi-server retrial queue with negative customers and disasters // Queueing Syst (2007) 55: 223-237

2 Jolai, F. and AxadzadrM, 5. M. and Taqhizadf.h, M. R. Performance estimation of an email contact center 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, — с последующим выбором комбинации дисциплин обслуживания и обновления, оптимальной согласно одному из параметров качества функционирования телекоммуникационных систем — времени задержки.

Результаты, выносимые на защиту

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

2. Для телекоммуникационных систем (с возможным сбросом данных для улучшения функционирования или из-за воздействия ряда факторов, например, таких как выход из строя сервера) па основе СМО G/M/n/r, г < оо с обобщенным обновлением разработаны аналитические алгоритмы расчёта вероятностно-временных характеристик: стационарных распределений числа заявок, функций распределения времён пребывания в накопителе (системе) «убитой», обслуженной и произвольной заявок для различных вариантов обобщённого обновления и дисциплин обслуживания.

Доказано, что для произвольной заявки вне зависимости от вариантов обслуживания и обобщённого обновления время пребывания в накопителе имеет одно и тоже распределение. Кроме того, показано, что, меняя дисциплины обслуживания и обобщённого обновления при неизмеппых начальных условиях, можно уменьшать (увеличивать) время пребывания в накопителе (системе) обслуженной («убитой») заявки, т.е. изменять значения задержки — одного из параметров AQM.

Научная новизна

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

строению аналитических моделей апализа качества функционирования систем с НЕБ-подобными алгоритмами. Кроме того, аналитическая модель с обобщённым обновлением пригодна для расчёта показателей качества обслуживания протокола управления потоковой передачей (БСТР), а именно: общей задержки передачи сообщения, среднего числа переданных пакетов, среднего количества порций данных, входящих в пакет; причём эта модель отлична от изученных ранее другими авторами. Кроме того, в диссертации рассмотрено несколько вариантов комбинаций дисциплин обслуживания поступающих заявок и обобщённого обновления с целью выбрать оптимальную по значениям среднего времени ожидания обслуживания (пребывания в системе), т.е. с наименьшими значениями задержки.

Методы исследования

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

Обоснованность и достоверность результатов

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

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

Теоретическая и практическая ценность

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

Созданные на основе полученных теоретических результатов программы позволяют производить расчёт таких систем при их проектировании.

Исследования проводились в рамках грантов Российского фонда фундаментальных исследований (РФФИ) № 06-07-89056-а «Математические модели, методы, алгоритмы и программное обеспечение, основанное на веб-технологиях, для проведения фундаментальных исследований в области анализа производительности сетевых систем» и № 09-07-12032-офи_м «Разработка математические методов, вычислительных алгоритмов и программных средств для решения задач моделирования информационно-вычислительных и телекоммуникационных систем».

Реализация результатов работы

Результаты диссертации использовались в научно-исследовательских работах (НИР), проводимых Институтом проблем информатики Российской академии наук:

1. Разработка общих базовых математических методов расчёта систем массового обслуживания, функционирующих в дискретном времени.

2. Исследование систем и сетей массового обслуживания специального вида и информационно-управляющих систем с новыми видами обратной связи.

3. Исследование систем и сетей массового обслуживания специального вида с ненадёжными приборами и отрицательными заявками.

Результаты исследований вошли в программу «WEB-ориентировагшый программный комплекс удалённого расчёта стационарных характеристик систем массового обслуживания», дата регистрации РОСПАТЕНТом 11. 01. 2010г., номер свидетельства о регистрации № 2010610026.

Апробация работы

Результаты, полученные в ходе выполнения работы, были представлены на:

- XLII-XLVI Всероссийских конференциях по проблемам математики, информатики, физики и химии. Москва, Российский университет дружбы народов (РУДН), 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 из них опубликованы в ведущих рецензируемых научных журналах и изданиях, определённых Высшей аттестационной комиссией), основные из которых приведены в конце автореферата, а с полным списком можно ознакомиться в диссертации. Основные результаты представлены в работах, опубликованных в изданиях, рекомендованных ВАК, и получены лично соискателем. В работах, опубликованных в соавторстве, личный вклад соискателя состоит в построении аналитических моделей, получении, обосновании и интерпретации полученных результатов.

Структура и объем диссертации

Диссертация состоит из введения, трёх глав, разделённых на пункты, заключения, приложения и списка литературы. Основной текст изложен па 127 страницах, в приложении приведено 36 рисунков. Список литературы содержит 117 наименований.

Во Введении обоснована актуальность работы, сформулирована её цель и определены научная новизна и практическая ценность работы. Кратко изложены основные результаты выполненной работы.

Глава 1 диссертации посвящена расчёту показателей функционирования телекоммуникационных систем с потерями данных (катастрофами) из-за выхода из строя прибора с моментальным восстановлением или из-за воздействия вирусов. Аналитическая модель этих систем реализуется СМО с обновлением (полным обновлением) и продолжает работы А.Я. Крейнина в этой области. Отличие о предыдущих исследований состоит в том, что в качестве модели рассматриваются многолинейные СМО с полным обновлением и введено дообслуживание —

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

В моделях первого типа (СМО без дообслуживания) заявка, окончившая обслуживание на приборе, с вероятностью q убивает все заявки в накопителе и покидает СМО, а с дополнительной вероятностью р = 1 — д просто покидает систему. Вероятность д называется вероятностью обновления. Для систем такого типа ин-финитезимальная матрица однородного неприводимого марковского процесса с непрерывным временем и конечным множеством состояшш представима в виде:

Л'о Л 0 0 0 0 0 0

Мг N1 Л 0 0 0 . 0 0

0 м2 N2 Л . 0 0 0 0

0 0 Мз ЛГ3 • 0 0 . 0 0

0 0 0 0 Л 0 . 0 0

0 0 0 0 . Л 0 0

0 0 0 0 . мп N 0 0

0 0 0 0 м м . 0 0

0 0 0 0 м 0 . Л 0

0 0 0 0 м 0 N Л

0 0 0 0 м 0 м

где Мп — Мп + М.

Тогда если существуют матрицы Я и 3 такие что: А + RN + В?М = Он в2к + БЫ + М = 0, кроме того, не вырождена матрица 5Л + N + КМ. В этом случае вектор р = (ро,р\,... ,Рп+т)т удовлетворяет СУР ртС} 1 = 0Т с матрицей вида тогда и только тогда, когда для некоторых векторов / и д справедливы равенства:

-Т ТТ пк-п+1 . -*Т /-1П+7— к , —-, .

рк=/ Я +д в , к = п — 1,п + г,

vl-2^ + Г (Nn-i + RMn) + gTSr (sNn-i + M„) +

/ n+r \ / n+r \

+ /T £ Ri"n+1 )m + 9t{ ¿ Sn+r-i\M = 5T,

Vj=n+1 / Vj=n+1 /

fTRr (RNn+r + A)+gT (Nn+r + SA) = 0T.

Доказательство этого утверждения основано на теореме для ОПРГ и приведено в первой главе диссертации.

Аналогичные результаты получены и для моделей второго типа (СМО с дооб-служиванием), где с вероятностью q обслужившаяся заявка остаётся в системе, убивая все заявки в накопителе, и с вероятностью р = 1 — q покидает систему. Здесь вероятность q также называется вероятностью обновления.

В качестве примеров приведены алгоритмы расчётов показателей функционирования для экспоненциальных систем с обновлением — системы М/М/n/r без дообслуживания и системы М/М/n/r с дообслуживапием.

Глава 2 посвящена дальнейшему развитию идеи обновления (полного обновления) в построении аналитических моделей различных телекоммуникационных систем. В отличие от предыдущих работ по данной тематике и от первой главы здесь рассматривается обобщённое обновление. Полученные выражения можно применять, в частности, для нахождения оценки показателей качества обслуживания протокола управления потоковой передачей (SCTP), а именно: общей задержки передачи сообщения (среднее время пребывания в системе обслуженной заявки), среднего числа переданных пакетов (среднее число обслуженных заявок), среднего количества порций данных, входящих в пакет (среднее число «убитых» заявок плюс один) либо для оценки некоторых алгоритмов управления трафиком (алгоритмы типа RED, Drop Tail).

Обобщённое обновление определяется следующим образом. Находящаяся на приборе заявка в момент окончания обслуживания одновременно с уходом из системы либо с вероятностью q(l) «убивает» в накопителе ровно I заявок, если в

г

нем находится более I заявок, либо с вероятностью Q(l) = Y1(r ~ ёмкость

к-1

накопителя (г < оо)) полностью опустошает накопитель, если в нем было не более I заявок. Вероятности q(l) при Í > 0 будем называть вероятностями обновления.

г

Очевидно, что Q(0) = X) — 1, а р = q(0) представляет собой вероятность 1=0

того, что закончившая обслуживание на приборе заявка покидает систему, не вы-

бивая заявок из накопителя. При д(г) = д -ф- 0 и д(г) = 0, г = 1,г — 1, получаем иолпое обновление (р = д(0) = 1 — д), рассмотренное в первой главе диссертации.

В главе 2 с помощью СМО а/М/п/г с накопителем конечной ёмкости, с рекур-

рентным входящим потоком с конечным средним временем а = f xdA(x) между

поступлениями заявок, экспоненциальным с параметром ц обслуживанием заявок и обобщённым обновлением вычисляются вероятностно-временные характеристики: стационарные распределения числа заявок в системе по вложенной цепи Маркова но моментам поступления в систему и по времени, вероятности обслуживания и потери из-за введённого обобщённого накопления принятой в систему заявки, распределение времени ожидания обслуживания (задержки обслуживания). Рекуррентный поток взят потому, что он наиболее приемлем для построения аналитических моделей телекоммуникационных систем (это показано в работах Пыотса (Marccl F. Newts)).

Для системы GI/M/n/r рассмотрены следующие варианты дисциплин обслуживания и обобщённого обновления:

1) прямой порядок обобщённого обновления при дисциплине обслуживания в порядке поступления (FIFO);

2) инверсионный порядок обобщённого обновления при дисциплине обслуживания в порядке поступления (FIFO);

3) прямой порядок обобщённого обновления при инверсионном порядке обслуживания (LIFO)-,

4) инверсионный порядок обобщённого обновления при дисциплине обслуживания LIFO.

Для прямого порядка обобщёхпюго обновления при дисциплине обслуживания в порядке поступления (FIFO) в явном виде получены стационарные функции распределения времени пребывания в накопителе принятой к обслужи-

ванию заявки, принятой в систему и убитой заявки — W'loss'(x):

оо

О

п+г-1

п+г-1

где

i-n+l

£ irm(i — n + l)Hm(x), i = n,n + r-l,

m= 1 i-n+l

ИЛ<1№)(х)= Km(i-n+l)Hm(x), г=П,П + Г- 1.

m= 1

Здесь Hm(x) — функция распределения Эрланга с параметрами т и n/x, pi05, и Pserv — вероятности того, что принятая в систему заявка либо будет убита, либо перейдёт на обслуживание, irm(fc), т — \,к, к = 1, г, — вероятность того, что систему покинет ровно к заявок, при условии, что за это время обслужится ровно m заявок и новые заявки в систему не поступят, и 7гш(к), тп — 1,к, i — 1,г, — вероятность того, что заявка, находящаяся в начальный момент в очереди па fc-м месте, будет «убита» m-й обслужившейся заявкой.

Для остальных вариантов обобщённого обновления и дисциплин обслуживания получены соотношения, позволяющие в терминах преобразований Лапласа-Стилтьеса (ПЛС) вычислить функции распределения времён пребывания в накопителе и системе обслуженной, «убитой» и произвольной заявок.

Также получены аналитические выражения (для прямых порядков обновления и обслуживания) и соотношения для средних времён пребывания в накопителе (системе) обслуженной, «убитой» и произвольной заявок (для всех других предложенных вариантов обновления и обслуживания).

В главе 3 продолжено построение аналитической модели расчёта и анализа различных показателей качества, особое внимание уделено задержке передачи сообщения, вероятности потери принятого сообщения и-за воздействия ряда факторов и т.д. В отличии от главы 2 модель строится на базе СМО GI/M/n/r с обобщённым обновлением, но уже для случая накопителя бесконечной ёмкости (г = оо), что во-первых позволяет получить в явном виде аналитические выражения для вероятностных и временных характеристик, а во-вторых, модели с бесконечным накопителем более подходят для описания современных существующих телекоммуникационных систем.

Как и в предыдущей главе диссертации найдены стационарные распределения числа заявок в системе по моментам поступления и в произвольные моменты времени, получены аналитические выражения для вероятности обслуживания, а также вероятности потери заявки из-за обобщённого обновления.

В терминах ПЛС и производящей функции (ЛФ) найдены функции распредс-легшя (ФР) времени ожидания начала обслуживания «убитой» (х), обслу-

женной W(scrv,(x) и произвольной заявок W(x) для следующих вариантов дисциплин обслуживания и обобщённого обновления:

1. прямой порядок обобщённого обновления при дисциплине обслуживания в порядке поступления (FIFO)-,

2. инверсионный порядок обобщённого обновления при дисциплине обслуживания в порядке поступления (FIFO)\

3. прямой порядок обобщённого обновления при инверсионном порядке обслуживания (LIFO);

4. инверсионный порядок обобщённого обновления при дисциплине обслуживания LIFO.

Для варианта прямых порядков обобщённого обновления и дисциплины обслуживания ФР найдены в явном виде, причём эти ФР имеют экспоненциальное распределение (за вычетом скачка в нулевой момент времени):

(О, х < О,

W(scrv)(z) =

О,

I зЦд) Л -n/id-s- ]

ж > о,

Z<0,

9

-Рп-1 + Г£~(1~ е-п"(1-зШ)*) Рп-1, X > 0. ? 1 - о \ >

1~д

Здесь Дом и Pscrv — вероятности того, что принятая в систему заявка либо будет убита, либо перейдёт па обслужи панне:

Moss) _ fl(l - Цд)) -

Р ~ (1~д)(1-дЦд))Рп-и

Р<~> = i _ Ploss=gpr+

^ 1 - дп(д)

д — (единственное) решение уравнения д = a(f/.n — fingn(g)) лежащее на интср-

оо

вале (0; 1), n(z) = z'q(i), рЦ, к < 0 — стационарное распределение состояний ¡=о

вложенной цепи Маркова по моментам непосредственно перед поступлением заявки в систему.

Также показано, что независимо от вариантов обновления и обслуживания ФР времени пребывания в накопителе произвольной заявки одно и тоже.

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

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

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

1) Средние времена пребывания в накопителе убитой и обслуженной заявок в случае обновления и обслуживания в порядке поступления, а также в инверсионном порядке (обновление и обслуживание) практически совпадают для геометрического распределения вероятностей обобщённого обновления и различаются для пуассоновского распределения.

2) Если вероятности обобщенного обновления подчиняются геометрическому распределению, то наименьшие значения u/loss' принимает при обслуживании в порядке поступления и обновлении в инверсионном порядке, наибольшие значения — при обслуживании в инверсионном порядке и при обновлении в порядке поступления. Для среднего времени пребывания в накопителе обслуженной заявки и/Я!Ч') ситуация противоположная. Наименьшие значения — при обслуживании в инверсионном порядке и при обновлении в порядке поступления, а наибольшие — при обслуживании в порядке поступления и обновлении в инверсионном порядке.

3) Если вероятности обобщённого обновления имеют пуассоновское распределение, то картина чуть иная. Наименьшие значения задержка (среднее время ожидания обслуживания) принимает при инверсионном обновлении и прямом порядке обслуживания, а максимальные — либо в случае обслуживания в порядке поступления и обновления в инверсионном порядке (пуассонов-ский или эрланговский входящий поток), либо при обслуживании и обновлении в инверсионных порядках (гамма распределение интервалов между поступлением заявок).

Представлены графики зависимости средних времён пребывания в накопителе «убитой» и обслуженной заявок от вероятностей обобщённого обновления для всех рассмотренных в диссертации вариантов обслуживания и обновления.

По материалам диссертации опубликованы следующие работы:

1. Бочаров П. П., Зарядов И. С. Стационарное распределение вероятностей в системах массового обслуживания с обновлением // Вестник РУДН, Серия «Математика. Информатика. Физика». — 2007. — № 1-2. — С. 15-25.

2. Зарядов И. С. Стационарные характеристики обслуживания в системе G/M/n/r с обобщённым обновлением // Вестник РУДН. Серия «Математика. Информатика. Физика». - 2008. - № 2. — С. 3-10.

3. Зарядов И. С., Печинкин А. В. Стационарные временные характеристики системы GI/M/п/оо с некоторыми вариантами дисциплины обобщённого обновления // Автоматика и телемеханика. — 2009. — № 12. — С. 161-174.

4. Зарядов И. С. Система массового обслуживания GI/M/п/оо с обобщённым обновлением // Автоматика и телемеханика. — 2010. — № 4. — С. 130-139.

5. Зарядов И. С. О системах массового обслуживания с обновлением // Тезисы докладов. XLII Всероссийская конференция по проблемам математики, ин-

форматики, физики и химии. Секция «Прикладная теория вероятностей и теоретическая информатика» / РУДН. — Москва: 2006.

6. Зарядов И. С. Многолинейные системы массового обслуживания с обновлением с дообслуживанием и без // Тезисы докладов. XLIII Всероссийская конференция но проблемам математики, информатики, физики и химия. Секция «Прикладная теория вероятностей и теоретическая информатика» / РУДН. — Москва: 2007. - С. 32.

7. Зарядов И. С. Система массового обслуживания РН/РН/1/г с обновлением // Тезисы докладов. XLIII Всероссийская конференция по проблемам математики, информатики, физики и химии. Секция «Прикладная теория вероятностей и теоретическая информатика» / РУДН. — Москва: 2007. — С. 33.

8. Зарядов И. С. Система массового обслуживания G/MSP/n/r с обобщённым обновлением // Тезисы докладов. XLIV Всероссийская конференция по проблемам математики, информатики, физики и химии. Секция «Прикладная теория вероятностей и теоретическая информатика» / РУДН. — Москва:

2008. - С. 42-43.

9. Зарядов И. С. Стационарные характеристики обслуживания системы G/M/n/r с некоторыми вариантами дисциплины обобщённого обновления // Информационные процессы. — 2008. — Т. 8, № 2. — С. 108-124.

10. Зарядов И. С. Временные характеристики системы с различными вариантами обобщённого обновления // Тезисы докладов. XLV Всероссийская конференция по проблемам математики, информатики, физики и химии. Секция «Прикладная теория вероятностей и теоретическая информатика» / РУДН- — Москва: 2009. - С. 109-110.

11. Зарядов И. С. Ненадёжные системы с различными вариантами обновления // Труды конференции «MMR 2009 — математические методы в теории надёжности. Теория. Методы. Приложения.» / Университет нефти и газа им. Губ-кипа. — Москва: 2009. — С. 573-575.

12. Zaryadov I. S. Queueing Systems with General Renovation // ICUMT 2009 — International Conference on Ultra Modern Telecommunications. — St.-Petersburg:

2009. — Pp. 1-6.

13. Зарядов И. С. Сравнение временных характеристик системы с различными вариантами дисциплин обобщённого обновления и обслуживания // Тезисы докладов. XLV Всероссийская конференция по проблемам математики, информатики, физики и химии. Секция «Прикладная теория вероятностей и теоретическая ипформатика» / РУДН. — Москва: 2010. — С. 38-39.

14. Korolkova А. V., Zaryadov I. S. The Mathematical Model of the Traffic Transfer Process with a Rate Adjustable by RED // ICUMT 2010 — Interna^ tional Conference on Ultra Modern Telecommunications. — Moscow: 2010. — Pp. 1-5.

Зарядов Иван Сергеевич (Россия)

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

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

Доказано, что для произвольной заявки вне зависимости от вариантов обслуживания и обобщённого обновления время пребывания в накопителе имеет одно и то же распределение. Кроме того, показано, что, меняя дисциплины обслуживания и обобщённого обновления при неизменных начальных условиях, можно уменьшать (увеличивать) время пребывания в накопителе (системе) обслуженной («убитой») заявки.

Zaryadov Ivan Sergeevich (Russia) Computation of quality performance parameters for telecommunication and data processing systems using general renovation

In this thesis consideration is given to the development of analytical model for the computation of quality performance parameters for telecommunication systems with losses (discard or dropping of data) using queueing system with general renovation. Different methods were developed and improved for the analysis of such systems in cases of recurrent incoming flow of customers, exponential service time distribution, finite and infinite buffers for customers. There were obtained analytic expressions for the following stationary characteristics: distribution of number of customers, waiting and sojourn time distributions of the «killed», serviced and arbitrary customers for different combinations of renovation and service disciplines.

It is proved that for an arbitrary customer its waiting time in the buffer has the same distribution regardless generalized renovation and service disciplines. Moreover, it is shown that changing service and general renovation disciplines one can decrease (increase) waiting and sojourn times of «killed» and serviced customers.

Подписано в печать: 21.10.2010

Заказ № 4347 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Введение.

Глава 1. Аналитическая модель телекоммуникационных систем с потерей всех принятых данных.

1.1. Постановка задачи.

1.2. Аналитическая модель системы с полной потерей данных. Стационарные характеристики.

1.3. Частный случай модели: система M/MR/n/r с обновлением без дообслуживания.

1.4. Частный случай модели: система M/MRR/n/r с обновлением и дообслуживанием.

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

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

Математические методы теории массового обслуживания (ТМО) позволяют создавать стохастические модели протоколов сетей передачи данных, обеспечивают возможность решения многочисленных задач по расчёту характеристик качества обслуживания (Quality of Service, QoS) и функционирования различных компонент сетей, включая оценку вероятностновременных характеристик узлов коммутации и маршрутизации, анализ производительности сетей, управления потоками данных, расчёт потерь и загрузки цифровых линий связи при передаче данных, голоса и видеоинформации.

Значительный вклад в разработку и анализ классических моделей ТМО внесли А.Я. Хинчин [2], Б.В. Гнеденко [3], A.A. Боровков [4,5], Д. Кендалл [6], Д. Литтл, Д. Кокс [7], В. Смит [7], J1. Клейнрок [8], Б.А. Севастьянов [9], Л. Такач [10], Ф. Поллачек.

Среди современных авторов по ТМО и приложениям в области телекоммуникаций можно выделить Г.П. Башарина [11-14], П.П. Бочарова [15,16], В.М. Вишневского [17], А.Н. Дудина [18-20], В.А. Наумова [21], A.B. Печинкина, К.Е. Самуйлова [22-25] и др.

Пуассоновский входящий поток заявок, в отличие от экспоненциального времени обслуживания, долгое время вполне удовлетворял исследователей. Однако, по мере развития телекоммуникационных технологий появились системы, для которых использование моделей с пуассоновским, и даже с обобщающим его марковским входящим потоком является неприемлемым (что показано в работах Ньютса (Marcel F. Newts) [26]). Это привело к изучению модели СМО G/M/n/r с рекуррентным входящим потоком и экспоненциальным обслуживанием.

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

По данной проблематике написано много работ как теоретического, так и прикладного характера. Одна из таких работ [27], авторами которой являются гКжв1еу Б. и ТпраШ Б.К, посвящена разработке вероятностной модели протоколов, обеспечивающих функционирование помехоустойчивых систем. Другая — работа А.Я. Крейнина [28], рассматривала модель функционирования системы, в которую поступают потоки команд (заявок) нескольких типов (в том числе поток исполняемых команд) и в которой возможен переход от исполняемой команды к иной команде с потерей промежуточных команд. В дальнейшем [29] А. Я. Крейнин, введя понятие обновления (полного обновления), предложил обобщающую теоретическую модель для вычисления показателей функционирования систем, подверженных потере поступающих данных.

Диссертация продолжает работы Крейнина и Тошз1еу. В ней расширено понятие обновления — введено понятие обобщённого обновления, что позволяет создавать аналитические модели, применимые для следующих целей: расчёт показателей качества обслуживания протокола управления потоковой передачей (Stream Control Transmission Protocol — SCTP), a именно: общей задержки передачи сообщения, среднего числа переданных пакетов, среднего количества порций данных, входящих в пакет [30-35]; расчёт вероятности сброса поступающего пакета, числа сброшенных пакетов, распределения времени пребывания в системе сброшенного или переданного пакета при реализации механизмов активного управления очередью (Active Queue Management, AQM) — управления числом заявок в системе путём их «случайного» удаления. Удаление пакетов осуществляется в зависимости от значений ряда параметров алгоритма управления. Наиболее распространены алгоритмы типа RED (Random Early Détection), о которых на русском языке можно посмотреть в работах [36-38] (там же приведена библиография по алгоритмам семейства RED), алгоритм Drop Tail, алгоритм Blue — сброс пакетов агрегированного потока. При построении аналитической модели можно использовать частный случай обобщённого обновления; оптимизация работы как 1Р-сети [39-41], (активное управление очередями — Active Queue Management (AQM), — во избежание как перегрузок каналов передачи данных, маршрутизаторов, так и во избежание их простоя), так, к примеру, и сетей третьего поколения (3G) [42]; анализ узлов G-сетей (обобщённое обновление можно рассматривать как 1) результат поступления в систему потока триггеров (сигналов) — заявок, которые могут с некоторой вероятностью становиться отрицательными и, тем самым, привести к потери иных («нормальных») заявок [43]; 2) результат появления заявок типа «reset» [44,45], сокращающих размер накопителя в СМО); анализ компьютерных систем, подверженных воздействию вирусов, приводящих к потере данных (возможная потеря сообщений в результате обработки инфицированного [46] ); исследование систем с ненадёжными приборами (моментальное восстановление) [47-50]; исследование систем с выбиванием поступающих заявок [51] управление временем ожидания обслуживания, динамическое распределение ресурсов системы (по аналогии с [20]) обеспечение необходимого качества услуг (Quality of Service — QoS) в компьютерных сетях [52]; моделирование поведения ценных бумаг на рынке (аналогично предложенному в [29] подходу); моделирование работы call-центров (потеря ожидающих обслуживание клиентов [53]).

Как было сказано выше обобщенное обновление связано с катастрофами и отрицательными заявками, поэтому вкратце остановимся на этих понятиях.

Идея катастроф заключается в следующем — 1) либо поступающая в систему заявка убивает все иные находящиеся в системе заявки; 2) либо происходит сбой прибора, также приводящий к потере всех данных в системе. Среди работ по системам с катастрофами можно выделить работы А.Н. Дудина [18-20] или [54-59]).

Модели СМО с отрицательными заявками тесно связаны с G-сетями [17, 60-68] и являются предметом интенсивных исследований. Поступающая в систему отрицательная заявка выбивает одну (или несколько) обычных заявок. СМО с отрицательными заявками использовались для моделирования нейронных, компьютерных, телекоммуникационных и производственных сетей [62]. Отрицательную заявку, в частности, можно рассматривать либо как вирус (компьютерные сети) [46], либо как команду, удаляющая записи из базы данных.

Первая работа, в которой была исследована однолинейная СМО с неограниченным накопителем с отрицательными заявками, принадлежит Е. Геленбе с соавторами [61]. В дальнейшем системы с отрицательными заявками рассматривались в работах [69-79].

Среди недавних работ по СМО с отрицательными заявками можно упомянуть (помимо тех, что приведены выше) [46,48,53,80-86]. В работе [53] показано, что системы с отрицательными заявками и катастрофами также могут применяться и в телефонии для моделирования работы call-центров.

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

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

Кратко остановимся на содержании диссертации.

3.7. Выводы

В этой главе диссертации построена математическая модель телекоммуникационной системы с потерей данных (ПЕБ-подобные алгоритмы, к примеру) на базе многолинейной системы массового обслуживания с обобщённым обновлением, рекуррентным входящим потоком, экспоненциальным обслуживанием и накопителем бесконечной ёмкости и следующими вариантами дисциплин обслуживания и обобщённого случайного обновления: прямые порядки обобщённого обновления и обслуживания заявок, гу(в) = р^гу^егу)^ + рОоз^Оозз)^ = Рп-1 + 9Рп-1

1 — + пц — пцг(з)к{г{з))}

Пр[ 1 — ^^(¿(я))] инверсионным порядком обновления при прямом порядке обслуживания заявок, прямым и инверсионным порядком обновления при инверсионном порядке обслуживания. Данная модель может применяться и к анализу показателей функционирования протокола управления потоковой передачей данных (SCTP).

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

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

Также отметим следующее интересное обстоятельство. Стационарные средние времена пребывания в системе произвольной (т.е. независимо от того, обслужена ли заявка до конца или «убита») заявки для всех рассмотренных дисциплин одинаковы, что ещё раз подтверждает справедливость формулы Литтла. В то же время аналогичные характеристики для обслуженных и «убитых» заявок, вообще говоря, различны в зависимости от применяемых дисциплин.

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

Заключение

В диссертационной работе решены следующие задачи:

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

2. Во второй главе диссертации введено понятие обобщённого обновления, позволяющее строить аналитические модели широкого класса телекоммуникационных систем. Полученные выражения можно применять, в частности, для нахождения оценки следующих показателей качества обслуживания: общей задержки передачи сообщения (среднее время пребывания в системе обслуженной заявки), среднего числа переданных пакетов (среднее число обслуженных заявок), вероятности потери принятого сообщения из-за воздействия ряда факторов. В качестве аналитической модели рассмотрена система GI/М/п/г — многолинейная система массового обслуживания с обобщённым обновлением, рекуррентным входящим потоком и экспоненциальным обслуживанием. Решены следующие задачи:

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

Рассмотрены следующие дисциплины обобщённого обновления и обслуживания: прямой порядок обобщённого обновления при прямом порядке обслуживания заявок (FIFO) — FIFO/First; инверсионный порядок обновления при прямом порядке обслуживания заявок — FIFO/Last; прямой порядок обновления при инверсионном порядке обслуживания заявок (LIFO) - LIFO/First; инверсионный порядок обновления при инверсионном порядке обслуживании заявок — LIFO/Last. Для каждого из всех вышеуказанных случаев обобщённого обновления и обслуживания, получены системы уравнений позволяющие найти в терминах ПЛС стационарные распределения времён пребывания в накопителе «убитой» и обслуженной заявок соответственно, указаны способы решения полученных систем уравнений.

3. В третьей главе продолжено построение аналитической модели расчёта и анализа различных показателей качества, особое внимание уделено задержке передачи сообщения, вероятности потери принятого сообщения. В отличии от главы 2 модель строится на базе СМО GI/M/n/r с обобщённым обновлением, но уже для случая накопителя бесконечной ёмкости (г = оо), что во-первых позволяет получить в явном виде аналитические выражения для вероятностных и временных характеристик, а во-вторых, модели с бесконечным накопителем более подходят для описания современных существующих телекоммуникационных систем. Для рассмотренной модели получены математические соотношения для вычисления стационарных распределений основных характеристик рассматриваемой системы — числа заявок в системе по вложенной цепи Маркова и по времени; найдены формулы, позволяющие находить вероятности того, что заявка, поступающая в систему, будет «убита» или попадёт на прибор; получены выражения для расчёта среднего времени пребывания в накопителе (системе) (т.е. задержки) обслуженной или сброшенной из накопителя заявок, а также дисперсии времени пребывания в накопителе (системе) — т.е. колебания задержки, для следующих дисциплин обобщённого обновления и обслуживания: FIFO/First, FIFO/Last, LIFO/First, LIFO/Last. Выбрав один из предложенных вариантов обслуживания-обновления можно уменьшить или увеличить задержку передачи данных. Для варианта FIFO/First в явном виде получены распределения времён пребывания в накопителе «убитой», обслуженной и произвольной заявок. Показано,что время пребывания в накопителе «убитой» подчинено экспоненциальному закону, времена пребывания в накопителе обслуженной и произвольной заявок за вычетом скачка в нулевой момент времени также имеют экспоненциальное распределение. Этот факт позволяет достаточно легко находить различные характеристики, связанные с временем пребывания заявки в системе. Для остальных вариантов распределения времён пребывания в накопителе «убитой», обслуженной и произвольной заявок получены в терминах преобразований Лапласа-Стилтьеса и производящих функций.

1. Erlang А. К. Solution of some problemsin the theory of probabilities of significance in automatic telephone exchanges // The Post Office Electrical Engineers Journal. — 1917. Vol. 10. - Pp. 189-197.

2. Хинчин А. Я. Работы по математической теории массового обслуживания. — М.: Физматгиз, 1963.

3. Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. М.: ЛКИ, 2007.

4. Боровков А. А. Вероятностные процессы в теории массового обслуживания. — М.: Наука, 1972.

5. Боровков А. А. Асимптотические методы в теории массового обслуживания. — М.: Наука, 1980.

6. Kendall D. J. Stochastic processes occurring in the theory of queues and their analysys by the method of the embedded Markov chains // Ann. Math. Stat. 1953. - No 24. - Pp. 338-354.

7. Кокс Д., Смит В. Теория очередей. — М.: Мир, 1966.

8. Kleinrock L. Queueing systems. — Brisbane, Toronto: John Wiley & Sons, 1975.

9. Севастьянов Б. А. Эргодическая теорема для марковских процессов и ее приложение к телефонным линиям с отказами // Теория вероятностей и ее прим. — 1957. — Т. 2, № 1. — С. 106-116.

10. Takacs L. Introduction to the theory of queues. — New York: Oxford University Press, 1962.

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

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

13. Башарин Г. П. Лекции по математической теории телетрафика. — М.: РУДН, 2004.

14. Наумов В. А., Самуйлов К. Е., Яркина Н. В. Теория телетрафика мультисервисных сетей. — Москва: РУДН, 2007.

15. Бочаров П. П., Печинкин А. В. Теория массового обслуживания. — М.: РУДН, 1995.

16. Queueing Theory / P. P. Bocharov, С. D'Apice, A. V. Pechinkin, S. Salerno. Utrecht, Boston: VSP, 2004.

17. Вишневский В. M. Теоретические основы проектирования компьютерных сетей. — М.: Техносфера, 2003.

18. N. D. A., Karolik А. V. BMAP/SM/l queue with Markovian input of disasters and non-instantaneous recovery // Performance Evaluation. — 2001. Vol. 45, No 1. — Pp. 19-32.

19. Дудип A. H., Ким Ч. С., Семенова О. В. Оптимальное многопороговое управление входным потоком для системы обслуживания GI/РН/1 с ВМАР-потоком отрицательных запросов // Автоматика и телемеханика. 2004. - № 9. — С. 71-84.

20. Semenova О. V., Dudin A. N. M/M/N queueing system with controlled service mode and disaster // Automat. Control Comput. Sci. — 2007. — Vol. 41, No 6. Pp. 350-357.

21. Наумов В. А. Численные методы анализа марковских сетей. — М.: Изд-во УДН, 1985.

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

23. Башарин Г. П., Самуйлов К. Е. Современный этап в развитии теории телетрафика // Информационная математика. — 2001. — Т. 1, № 1. — С. 153-166.

24. Neuts М. F. Matrix-geometric solutions in stochastic models. An algorithmic approach. — Baltimore and London: The Johns Hopkins Univ. Press, 1981.

25. Towsley D., Tripathi S. K. A single server priority queue with server failureand queue flushing // Oper. Res. Lett. 1991. - No 10. - Pp. 353-362.

26. Kreinin A. Queueing Systems with Renovation // Journal of Applied Math. Stochast. Analysis. 1997. - Vol. 10, No 4. — Pp. 431-443.

27. Kreinin A. Inhomogeneous Random Walks: Applications in Queueing and Finance // CanQueue / Fields Institute. — Toronto: 2003.

28. Coene L. RFC3257. Stream Control Transmission Protocol Applicability Statement: Techrep / Siemens. — 2002. — http://www.ietf.org/rfc/ rfc3257.txt.

29. Ong L., Yoakum J. RFC3286. An Introduction to the Stream Control Transmission Protocol (SCTP): Techrep / Ciena Corporation, and Nortel Networks. — 2002. — http://tools.ietf.org/html/rfc3286.

30. Самуйлов К. E., Першаков H. В., Чукарин А. В. Разработка модели функционирования протокола управления потоковой передачей // Вестник РУДН, Сер. «Прикладная и компьютерная математика». — 2005. Т. 4, № 1. - С. 40-47.

31. Першаков Н. В., Самуйлов К. Е. Системы M\G\l с групповым обслуживанием и их применение к анализу модели протокола управления потоковой передачей. Часть I // Вестник РУДН, Сер. «Математика. Информатика. Физика». — 2009. — № 1. — С. 34-44.

32. Першаков Н. В., Самуйлов К. Е. Системы M\G\1 с групповым обслуживанием и их применение к анализу модели протокола управления потоковой передачей. Часть II // Вестник РУДН, Сер. «Математика. Информатика. Физика». — 2009. — № 2. — С. 43-53.

33. Королькова А. В., Кулябов Д. С.and Черноиванов А. И. К вопросу о классификации алгоритмов RED // Вестник РУДН. Серия «Математика. Информатика. Физика.». — 2009. — № 3. — С. 34-46.

34. Королькова А. В., Кулябов Д. С. Аналитическая модель для расчёта вероятности сброса пакетов в алгоритме RED // Труды РНТОРЭС им. Попова. Серия: Научная сессия, посвящённая Дню радио. Выпуск: LXII. 2007. - С. 233-234.

35. Королькова А. В. Метод расчёта вероятности сброса паке- тов в алгоритме RED // Вестник Российского университета дружбы народов. Серия «Математика. Информатика. Физика.». — 2007. — № 12. — С. 32-37.

36. Floyd S., Jacobson V. Random Early Detection Gateways for Congestion Avoid- ance // IEEE/ACM Transactions on Networking. — 1993. — No 1(4). Pp. 397-413.

37. Modified RED gateways under bursty traffic / G. Feng, A. K. Agar-wal, A. Jayaraman, С. K. Siew // IEEE Commun. Lett. — 2004. — Vol. 8, No 5. Pp. 323-325.

38. Ryoo I., Yang M. A State Dependent RED: An Enhanced Active Queue Man- agement Scheme for Real-Time Internet Services // IEICE Trans. Commun. 2006. - Vol. E89-B, No 2. — P. 614-617.

39. Queue management for TCP Traffic over 3G Links / M. Sagfors, R. Ludwig, M. Meyer, J. Peisa // Wireless Communications and Networking / WCNC. Vol. 3. - 2003. - Pp. 1663-1668.

40. Gelenbe E. G-Networks with triggered customer movement // Journal of Applied Probability. 1993. - Vol. 30, No 3. - P. 742-748.

41. Gelenbe E., Fourneau J. M. G-networks with resets // Performance Evaluation. 2002. - No 49. - Pp. 179-192.

42. Gelenbe E., Fourneau J. M. Flow equivalence and stochastic equivalence in G-networks // Computational Management Science. — 2004. — Vol. 1, No 2. P. 179-192.

43. Krishna Kumar В., Arivudainambi D., Krishnamoorthy A. Some results on a generalized M/G/l feedback queue with negative customers // Ann. Oper. Res. 2006. - No 143. - Pp. 277-296.

44. Зарядов И. С. Ненадёжные системы с различными вариантами обновления // Труды конференции «MMR 2009 — математические методы в теории надёжности. Теория. Методы. Приложения.» / Университет нефти и газа им. Губкина. — Москва: 2009. — С. 573-575.

45. Соколов И. А., Печинкин А. В., Чаплыгин В. В. Стационарные характеристики многолинейной системы массового обслуживания с ненадежными приборами // Обозрение прикладной и промышленной математики. 2007. — Т. 14, № 5. - С. 27-39.

46. Печинкин А. В., Соколов И. А., Чаплыгин В. В. Многолинейная система массового обслуживания с конечным накопителем и ненадёжными приборами // Информатика и ее применения. — 2007. — Т. 1, № 1. —1. С. 27-39.

47. Псчинкин А. В., Соколов И. А., Чаплыгин В. В. Стационарные характеристики многолинейной системы массового обслуживания с однов-леменными отказами приборов // Информатика и ее применения. — 2007. — Т. 1, № 2. — С. 39-49.

48. Чаплыгин В. В. Многолинейная система массового обслуживания с конечным накопителем, блокировкой полумарковского потока заявок и выбиванием заявок из накопителя // Информатика и ее применения. 2008. - Т. 2, № 3. - С. 34-40.

49. Gelenbe Е., Nunez A. Self-Aware Networks and Quality of Service // ICANN/ICONIP 2003 / Ed. by О. K. et al. 2003. - P. 901-908.

50. YangWoo S. Multi-server retrial queue with negative customers and disasters // Queueing Syst. — 2007. — No 55. — P. 223-237.

51. Semenova О. V. A Queueing System with Two Operation Modes and a Disaster Flow: Its Stationary State Probability Distribution // Automation and Remote Control. — 2002. — No 10. — Pp. 73-86.

52. Semenova О. V. Optimal control for a BMAP/SM/1 queue with MAP-input of disasters and two operation modes // RAIRO Oper. Res. Recherche Operationnelle. — 2004. — Vol. 38, No 2. — Pp. 153-171.

53. Transient analysis of a single server queue with catastrophes, failures and repairs / B. Krishna Kumar, A. Krishnamoorthy, S. Pavai Madheswari, S. Sadiq Basha // Queueing Systems: Theory and Applications. — 2007. — Vol. 56, No 3-4. Pp. 133-141.

54. Yechiali U. Queues with system disasters and impatient customers whensystem is down // Queueing Syst. Theory Appl. — 2007. — Vol. 56, No 34. Pp. 195-202.

55. Boxma O. J., Perry D., Stadje W. Clearing Models for M/G/l Queues // Queueing Systems. 2001. - No 38. - P. 287-306.

56. Yechiali U. Queues with system disasters and impatient customers when system is down // Queueing Systems. — 2007. — Vol. 56, No 3-4. — Pp. 195-202.

57. Gelenbe E. Random neural networks with negative and positive signals and product form solution // Neural Computation. — 1989. — Vol. 1, No 4. P. 502-510.

58. Gelenbe E., Glynn P., Sigman K. Queues with negative arrivals // Journal of Applied Probability. 1991. - Vol. 28. - Pp. 245-250.

59. Gelenbe E. G-networks: an unifying model for neural and queueing networks // Annals of Operations Research. — 1994. — Vol. 48, No 1-4. — P. 433-461.

60. Fourneau J. M., Gelenbe E., Suros R. G-networks with multiple classes of positive and negative customers // Computer Science. — 1996. — Vol. 155. P. 141-156.

61. Gelenbe E. G-Networks: Multiple Classes of Positive Customers, Signals, and Product Form Results // Performance 2002 / Ed. by M. C. Calzarossa, S. Tucci. 2002. - P. 1-16.

62. Бочаров П. П., Вишневский В. М. G-сети: развитие теории мультипликативных сетей // Автоматика и телемеханика. — 2003. № 5. -С. 46-74.

63. Gymez-Corral A., Martos M. E. Marked Markovian Arrivals in a Tandem G-Network with Blocking // Methodol. Comput. Appl. Probab. — 2009. — No 11. Pp. 621-649.

64. Jin-Ting W., Peng Z. A Single-server Discrete-time Retrial G-queue with Server Breakdowns and Repairs // Acta Mathematicae Applicatae Sinica. 2009. - Vol. 25, No 4. - P. 675-684.

65. Chakka R., Harrison P. G. A Markov modulated multi-server queue with negative customers — The MMCPP/GE/c/L G-queue // Acta Infor-matika. 2001. - Vol. 37. - Pp. 881-919.

66. Harrison P. G., Pitel E. ojourn times in single server queues with negative customers // Queueing Systems. — 2002. — No 41. — Pp. 943-963.

67. Harrison P. G., Pitel E. The M/G/l queue with negative customers // Adv. Appl. Prob. 1996. - Vol. 28. - Pp. 540-566.

68. Bayer N., Boxma O. J. Wiener-Hopf analysys of an M/G/l queue with negative customers and of related class of random walk // Queueing Systems. — 1996. No 23. - Pp. 301-316.

69. Atencia I., Aguillera G., Bocharov P. P. On the M/G/1/0 queueing system under LCFS PR discipline with repeated and negative customers with batch arrivals // Proc. Oper. Res. 42 Annual Conf. / Ed. by U. of Swamsea. Wales UK: 2000. - Pp. 30-34.

70. Atencia I., Bocharov P. P. On the M/G/1/0 queueing system under LCFS PR discipline with repeated and negative customers with batch arrivals // Proc. 3-rd Europ. Cong. Math. — Barcelona: 2000. — P. 133.

71. Retrial queueing system with several input flows and negative customersand LCFS PR discipline / I. Atencia, C. D'Apiche, R. Manzo, S. Salerno // Proc. Fourth Int. Workshop on Queueing Networks with Finite Capacity. Ilkley, U. K.: 2000. - Pp. 1-9.

72. Albores J. F., Bocharov P. P., Luybin D. Yu. Two-stage exponential queueing system with internal losses, feedback and negative arrivals // Вестник РУДН. Сер. «Прикладная математика и информатика». — 2003. — № 1. — С. 70-84.

73. Чаплыгин В. В. Система массового обслуживания G/MSP/n/r с потоком отрицательных заявок // Информационные процессы. — 2005. — Т. 5, № 1. С. 1-19.

74. Harrison P. G. The MMCPP/GE/c G-queue: sojourn time distribution // Queueing Sytems. — 2002. — Vol. 41. — Pp. 271-298.

75. Мандзо P. Однолинейная экспоненциальная система массовго обслуживания конечной ёмкости с относительным приоритетом и отрицательными заявками // Вестник РУДН. Сер. «Прикладная математика и информатика». — 2003. — № 1. — С. 100-108.

76. Чаплыгин В. В. Система массового обслуживания G/MSP/n/r с потоком отрицательных заявок // Информационные процессы. — 2005. — Т. 5, № 1. С. 1-19.

77. Анализ многолинейной марковской системы массового обслуживания с неограниченным накопителем и отрицательными заявками / П. П. Бочаров, Ч. Д'Апиче, Р. Мандзо, А. В. Печинкин // Автоматика и телемеханика. — 2007. — № 1. — С. 93—104.

78. Печинкин А. В. Марковская система обслуживания с конечным накопителем и отрицательными заявками, действующими на конец очереди // Информационные процессы. — 2007. — Т. 7. — С. 138—152.

79. Quan-Lin L., Yiqiang Q. Z. A MAP/G/1 Queue with Negative Customers // Queueing Systems. — 2004. — No 47. — Pp. 5-43.

80. Manzo R., Cascone N., Razumchik R. V. Exponential Queuing System with Negative Customers and Bunker for Ousted Customers // Automation and Remote Control. — 2008. — No 9. — P. 103-113.

81. Kim C., Klimenok V. I., Orlovsky D. S. Multi-Server Queueing System with a Batch Markovian Arrival Process and Negative Customers // Automation and Remote Control. — 2006. — No 12. — P. 106-122.

82. Печинкин А. В., В. Разумчикб P. Система массового обслуживания с отрицательными заяками и бункером для вытесненных заявок в дискретном времени // Автоматика и телемеханика. — 2009. — N- 12. — С. 109-120.

83. Bocharov P. P., Naoumov V. A. Matrix-geometric stationary distribution for the PH/PH/l/r queue // Electron. Informationsverarb. Kyb. — 1986. — Vol. 22, No 4. Pp. 179-186.

84. Naoumov V. A. Matrix-multiplicative approach to quasi- birth-and-death processes analysis // Proc. First Internat. Conf. on Matrix- Analytic Methods in Stochastic Models. — Detroit: 1995.

85. Naoumov V. A. Matrix-Multiplicative Approach to Quasi-Birth-and-Death Processes Analysis // Matrix-Analytic Methods in Stochastic Models / Ed. by M. D. Inc. New-York: 1997. - Pp. 87-107.

86. Naoumov V. A. Modified Matrix-Geometric Solution for Finite QBD Processes // Advances in Algorithmic Methods for Stochastic Models. Proc. Third Internat. Conf. on Matrix-Analytic Methods. — Leuven, Belgium:2000. Pp. 257-265.

87. Anisimov V. V., Artalejo J. R. Exponential Analysis of Markov Multiserver Retrial Queues with Negative Arrivals // Queueing Systems. —2001. No 39. - P. 157-182.

88. Artalejo J. R., Gomez-Corrall A. Generalized birth and death processes with applications to queues with repeated attempts and negative arrivals // OR Spektrum. 1998. - No 20. - Pp. 5-14.

89. Бочаров П. П., Зарядов И. С. Стационарное распределение вероятностей в системах массового обслуживания с обновлением // Вестник РУДН. Серия «Математика. Информатика. Физика». — 2007. — № 12. С. 15-25.

90. Зарядов И. С. Стационарные характеристики обслуживания в системе С/М/п/г с обобщённым обновлением // Вестник РУДН. Серия «Математика. Информатика. Физика». — 2008. — № 2. — С. 3-10.

91. Зарядов И. С. Стационарные характеристики обслуживания системы й/М/п/г с некоторыми вариантами дисциплины обобщённого обновления // Информационные процессы. — 2008. — Т. 8, № 2. — С. 108— 124.

92. Зарядов И. С., Печинкин А. В. Стационарные временные характеристики системы Gl/М/п/оо с некоторыми вариантами дисциплины обобщённого обновления // Автоматика и телемеханика. — 2009. — № 12. С. 161-174.

93. Zaryadov I. S. Queueing Systems with General Renovation // ICUMT 2009 — International Conference on Ultra Modern Telecommunications. — St.-Petersburg: 2009. — Pp. 1-6.

94. Зарядов И. С. Система массового обслуживания Gl/М/п/оо с обобщённым обновлением // Автоматика и телемеханика. — 2010. — К2 4. — С. 130-139.

95. Korolkova А. V., Zaryadov I. S. The Mathematical Model of the Traffic Transfer Process with a Rate Adjustable by RED // ICUMT 2010 International Conference on Ultra Modern Telecommunications. — Moscow: 2010. - Pp. 1-5.

96. Наумов В. А. Марковские модели потоков требований // Системы массового обслуживания и информатика. — 1987. — № 1. — С. 67-73.

97. Ramaswami V. Matrix-Analytic Methods: A Tutorial Overview with Some Extensions and New Results // Matrix-Analytic Methods in Stochastic Models / Ed. by M. D. Inc. New-York: 1997. - Pp. 261-296.

98. Першаков H. В. Модели и методы анализа вероятностных характеристик протокола управления потоковой передачей данных: Кандидатская диссертация / РУДН. — Москва, 2007.

99. Печинкин А. В., Чаплыгин В. В. Стационарные характеристики системы массового обслуживания SM/MSP/n/r // Автоматика и телемеханика. 2004. - № 9. - С. 85-100.

100. Печинкин А. В., Чаплыгин В. В. Стационарные характеристики системы массового обслуживания G/MSP/n/r // Вестник РУДН. Сер. «Прикладная математика и информатика». — 2003. — № 1. — С. 119143.

101. Стационарные характеристики системы массового обслуживания G/MSP/1/r / П. П. Бочаров, Ч. Д'Апиче, А. В. Печинкин, С. Са-лерно // Автоматика и телемеханика. — 2003. — № 2. — С. 127-143.

102. ИЗ. Чаплыгин В. В. истема массового обслуживания G/BMSP/1/r // Информационные процессы. — 2003. — Т. 3, № 2. — С. 97-108.

103. Чаплыгин В. В. Система массового обслуживания G/BMSP/1/r Ц

104. Информационные процессы. — 2005. — Т. 3, № 2. — С. 97-108.

105. Huang Y., Tripathi S. К. Resource Allocation for Primary-Site Fault-Tolerant Systems // IEEE Transactions on Software Engineering archive. 1993. — Vol. 19, No 2. - Pp. 108-119.

106. Krishna Kumar В., Arivudainambi D., Krishnamoorthy A. Some results on a generalized M/G/l feedback queue with negative customers // Ann. Oper. Res. 2006. - No 143. - P. 277-296.

107. Jolai F., Asadzadeh S. M., Taghizadeh M. R. Performance estimation of an email contact center by a finite source discrete time Geo/Geo/1 queue with disasters // Comput. Ind. Eng. — 2008. — Vol. 55, No 3. — Pp. 543556.