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

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

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

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

Москва 2010

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

Научный консультант:

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

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

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

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

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

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

г. Москва, ул. Орджоникидзе д. 3, ауд. 110.

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

(Отзывы на автореферат просьба направлять по указанному адресу.) Автореферат разослан « » октября 2010 г.

Учёный секретарь диссертационного совета М. Б. Фомин

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

Актуальность работы Информационные технологии один из основных признаков и ресурсов раз вития современного общества. Для развития и повсеместного внедрения сетей передачи и обработки данных требуется создание аналитических моделей, адек ватно представляющих реальные системы и учитывающих как их характерные особенности, так и возможные из-за воздействия ряда факторов (выход из строя сервера, воздействие вирусов и пр.) потери передаваемых или обрабатываемых данных. Математические методы теории массового обслуживания (ТМО) (зна чительный вклад в развитие ТМО и теории телетрафика внесли и продолжа ют вносить А.Я. Хинчин, Б.В. Гнеденко, А.А. Боровков, Д. Кендалл, Д. Литтл, Д. Кокс, В. Смит, Л. Клейнрок, Б.А. Севастьянов, Л. Такач, Ф. Поллачек, П.П. Бочаров, Г.П. Башарин, В.М. Вишневский, А.Н. Дудин, В.А. Ивницкий, И.Н. Коваленко, В.А. Наумов, А.В. Печинкин, К.Е. Самуйлов и др.) позволя ют создавать стохастические модели протоколов сетей передачи данных, обеспе чивают возможность решения многочисленных задач по расчёту характеристик качества обслуживания (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), классификацию которых на D. Towsley, S. K. Tripathi A single server priority queue with server failure and queue ushing. Oper. Res.

Lett., 1991;

10:353-362.

Kreinin, 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.

Kreinin A. Queueing Systems with Renovation. Journal of Applied Math. Stochast. Analysis, 1997, vol. 10, № 4, pp. 431–443.

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

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

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

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

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

2) результат появления за явок типа «reset»6, сокращающих размер накопителя в СМО);

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

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

Королькова А. В., Кулябов Д. С., Черноиванов А. И. К вопросу о классификации алгоритмов RED // Вестник РУДН. Серия Математика. Информатика. Физика. № 3. 2009. С. 34–- см, например, первую работу по данной тематике — Floyd, S., Jacobson, V., Random Early Detection gateways for Congestion Avoidance, IEEE/ACM Transactions on Networking, V.1 N.4, August 1993, P. 397-413.

M. Sagfors, R. Ludwig, M. Meyer, and J. Peisa, Queue management for TCP Trac over 3G Links, Wireless Communications and Networking, 2003. WCNC Krishna Kumar B., Arivudainambi D., Krishnamoorthy A. Some results on a generalized M/G/1 feedback queue with negative customers // Ann Oper Res (2006) 143: 277– Gelenbe E. G-Networks with triggered customer movement // Journal of Applied Probability, Vol. 30, No.

3, pp 742–748, 1993.

Gelenbe E, Fourneau JM G-networks with resets // 2002, Performance Evaluation 49, 179-192.

Semenova O.V., Dudin 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.

Erol Gelenbe, Arturo Nunez Self-Aware Networks and Quality of Service // O. Kaynak et al. (Eds.):

ICANN/ICONIP 2003, LNCS 2714, pp. 901–908, 2003.

– моделирование и оптимизация работы call-центров1 и центров обслуживания sms-сообщений2 (потеря ожидающих обслуживание клиентов).

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

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

2. Разработка программно ориентированных алгоритмов расчёта вероятностно временных характеристик стационарных распределений числа заявок в си стеме (по моментам поступления заявок в систему и в произвольные моменты времени) и вывод функций стационарных распределений времён пребывания в накопителе «убитой», обслуженной и произвольной заявок (либо в терминах преобразований Лапласа-Стилтьеса и производящих функций, либо в явном виде) для следующих вариантов обобщённого обновления и дисциплины об служивания: прямой порядок обобщённого обновления (заявки «убиваются» в накопителе в порядке поступления) при дисциплине обслуживания в порядке поступления (FIFO), инверсионный порядок обобщённого обновления (заявки «убиваются» в накопителе в порядке, обратном поступлению) при дисциплине YangWoo Shin Multi-server retrial queue with negative customers and disasters // Queueing Syst (2007) 55: 223– Jolai, F. and Asadzadeh, S. M. and Taghizadeh, M. R. Performance estimation of an email contact center by a nite source discrete time Geo/Geo/1 queue with disasters // Comput. Ind. Eng. (2008) V. 55. No 3:543– обслуживания FIFO, прямой порядок обобщённого обновления при инверсион ном порядке обслуживания (LIFO), инверсионный порядок обобщённого обнов ления при дисциплине обслуживания LIFO, с последующим выбором комби нации дисциплин обслуживания и обновления, оптимальной согласно одному из параметров качества функционирования телекоммуникационных систем времени задержки.

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

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

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

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

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

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

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

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

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

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

и ориентиро ваны на применение в различных сетях и автоматизированных системах.

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

Исследования проводились в рамках грантов Российского фонда фундамен тальных исследований (РФФИ) № 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 рисунков. Список литературы содержит наименований.

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

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

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

Вероятность q называется вероятностью обновления. Для систем такого типа ин финитезимальная матрица Q однородного неприводимого марковского процесса с непрерывным временем и конечным множеством состояний представима в виде:

N0 0 0... 0 0... 0 M1 N1 0... 0 0... 0 M2 N2... 0 0... 0 0 M3 N3... 0 0...........................................................

.

0 0 0 0... 0... 0 Q1 = 0 0, 0 0 0... Nn1... 0 0 0 0... Mn N... 0 0 0 0... M M...........................................................

.

0 0 0 0... M 0... 0 0 0 0... M 0... N 0 0 0 0... M 0... M Nr+ где Mn = Mn + M.

Тогда если существуют матрицы R и S такие что: + RN + R2 M = 0 и S 2 + SN + M = 0, кроме того, не вырождена матрица S + N + RM. В этом случае вектор p = (0, p1,..., pn+r )T удовлетворяет СУР p T Q1 = T с матрицей p и справедливы Q1 вида тогда и только тогда, когда для некоторых векторов f g равенства:

p T = f T Rkn+1 + T S n+rk, k = n 1, n + r, k g ( ) ( ) p T + f T Nn1 + RMn + T S r SNn1 + Mn + n2 g ( n+r ) ( n+r ) jn+1 n+rj g +fT M +T M = T, R S j=n+1 j=n+ f T Rr (RNn+r + ) + T (Nn+r + S) = T.

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

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

Здесь вероятность q также называется вероятностью обновления.

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

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

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

r Очевидно, что Q(0) = q(l) = 1, а p = q(0) представляет собой вероятность l= того, что закончившая обслуживание на приборе заявка покидает систему, не вы бивая заявок из накопителя. При q(r) = q = 0 и q(i) = 0, i = 1, r 1, получаем полное обновление (p = q(0) = 1 q), рассмотренное в первой главе диссертации.

В главе 2 с помощью СМО GI/M/n/r с накопителем конечной ёмкости, c рекур рентным входящим потоком с конечным средним временем a = xdA(x) между поступлениями заявок, экспоненциальным с параметром µ обслуживанием заявок и обобщённым обновлением вычисляются вероятностно-временные характеристи ки: стационарные распределения числа заявок в системе по вложенной цепи Мар кова по моментам поступления в систему и по времени, вероятности обслужи вания и потери из-за введённого обобщённого накопления принятой в систему заявки, распределение времени ожидания обслуживания (задержки обслужива ния). Рекуррентный поток взят потому, что он наиболее приемлем для построения аналитических моделей телекоммуникационных систем (это показано в работах Ньютса (Marcel F. Newts)).

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

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

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

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

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

Для прямого порядка обобщённого обновления при дисциплине обслуживания в порядке поступления (F IF O) в явном виде получены стационарные функции распределения времени пребывания в накопителе W (serv) (x) принятой к обслужи ванию заявки, принятой в систему и убитой заявки W (loss) (x):

n+r (x)p, (serv) W (serv) (x) = Wi (1 )pserv i=0 i n+r (x)p, (loss) W (loss) (x) = Wi (1 )ploss i=n i где in+ (serv) m (i n + 1)Hm (x), i = n, n + r 1, Wi (x) = m= in+ (loss) m (i n + 1)Hm (x), i = n, n + r 1.

Wi (x) = m= Здесь Hm (x) функция распределения Эрланга с параметрами m и nµ, ploss и pserv вероятности того, что принятая в систему заявка либо будет убита, либо перейдёт на обслуживание, m (k), m = 1, k, k = 1, r, вероятность того, что систему покинет ровно k заявок, при условии, что за это время обслужится ровно m заявок и новые заявки в систему не поступят, и m (k), m = 1, k, i = 1, r, вероятность того, что заявка, находящаяся в начальный момент в очереди на k-м месте, будет «убита» m-й обслужившейся заявкой.

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

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

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

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

В терминах ПЛС и производящей функции (ПФ) найдены функции распреде ления (ФР) времени ожидания начала обслуживания «убитой» W (loss) (x), обслу женной W (serv) (x) и произвольной заявок W (x) для следующих вариантов дисци плин обслуживания и обобщённого обновления:

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

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

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

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

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

0, x 0, W (loss) (x) = 1 enµ(1g(g))x, x 0, 0, x 0, ( 1 g W (serv) (x) = p(serv 1 1 g pn1 + ) ( ) + g (g) nµ(1g (g))x 1 g (g) 1 e pn1, x 0, 0, x 0, g( ) W (x) = g 1 p + 1 enµ(1g(g))x p, x 0.

1 g n1 1 g n Здесь ploss и pserv вероятности того, что принятая в систему заявка либо будет убита, либо перейдёт на обслуживание:

g(1 (g)) p, p(loss) = (1 g)(1 g (g)) n n g (g) p + p, p(serv) = 1 ploss = 1 g (g) n i i= g (единственное) решение уравнения g = (µn µng (g)) лежащее на интер i z q(i), pk, k 0 стационарное распределение состояний вале (0;

1), (z) = i= вложенной цепи Маркова по моментам непосредственно перед поступлением за явки в систему.

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

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

В заключительном разделе сформулированы результаты работы.

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

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

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

2) Если вероятности обобщённого обновления подчиняются геометрическому рас пределению, то наименьшие значения w(loss) принимает при обслуживании в порядке поступления и обновлении в инверсионном порядке, наибольшие зна чения при обслуживании в инверсионном порядке и при обновлении в поряд ке поступления. Для среднего времени пребывания в накопителе обслуженной заявки w(serv) ситуация противоположная. Наименьшие значения при обслу живании в инверсионном порядке и при обновлении в порядке поступления, а наибольшие при обслуживании в порядке поступления и обновлении в инверсионном порядке.

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

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

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

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

2. Зарядов И. С. Стационарные характеристики обслуживания в системе G/M /n/r с обобщённым обновлением // Вестник РУДН. Cерия «Математика.

Информатика. Физика». 2008. № 2. С. 3–10.

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

С. 161–174.

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

С. 130–139.

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

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

Москва: 2007. С. 32.

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

С. 33.

8. Зарядов И. С. Система массового обслуживания G/M SP /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 A. V., Zaryadov I. S. The Mathematical Model of the Trac Trans fer 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) Сomputation 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.