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

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

СОПИН Эдуард Сергеевич

Модели систем ограниченной емкости с групповым входящим потоком и их применение к анализу

показателей эффективности серверов протокола установления сессий

05.13.17 - «Теоретические основы информатики»

Автореферат

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

1 7 0К"Г 2013

Москва-2013

005535232

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

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

профессор

Самуйлов Константин Евгеньевич

Официальные оппоненты: Печинкин Александр Владимирович, доктор

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

Зарядов Иван Сергеевич, кандидат физико-математических наук, старший преподаватель кафедры теории вероятностей и математической статистики Российского университета дружбы народов

Ведущая организация: Институт проблем передачи информации

Российской Академии наук (ИППИ РАН)

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

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

Автореферат разослан «/¿/» октября 2013 г.

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

Л

М.Б. Фомин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы В настоящее время телекоммуникационные компании разрабатывают и внедряют все больше новых мультимедийных услуг. Базой для их внедрения является мультимедийная IP-подсистема (IP Multimedia Subsystem, IMS), позволяющая предоставлять поверх протокола IP на основе единой сети как традиционные услуги связи, так и новые услуги сетей последующих поколений (Next Generation Networks, NGN). В связи с большой популярностью этих услуг сети телекоммуникаций на базе IMS, работающие на основе протокола установления сессий (Session Initiation Protocol, SIP), работают в условиях перегрузки. Кроме того, мультимедийные услуги существенно меняют характер трафика установления сессий (сигнального трафика). В частности, услуга присутствия (presence service) подразумевает отправку сообщений уведомления одновременно большому числу пользователей.

Для анализа вероятностно временных характеристик (ВВХ) SIP-серверов таких как вероятность потерь, среднее время ожидания, время возврата в состояние нормальной нагрузки и др., применяются модели однолинейных систем массового обслуживания (СМО). При построении и анализе таких моделей используется аппарат теории вероятностей, теории случайных процессов, теории массового обслуживания и теории телетрафика. Существенный вклад в развитие данной области внесли российские и зарубежные ученые: Л.Г. Афанасьева, Г.П. Башарин, Е.В. Булинская, В.М. Вишневский, Б.С. Гольдштейн, В.А. Наумов, A.B. Печинкин, А.П. Пшеничников, К.Е. Самуйлов, Б.А. Севастьянов, С.Н. Степанов, А.Д. Харкевич, И.И. Цитович, С.А. Шоргин, А.Е. Кучерявый, V.B.Iversen, F.P. Kelly, P.V. Mieghem, J.W. Roberts, K.W. Ross, J. Virtamo, M. Roughan и др.

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

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

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

1. Простейшая модель 81Р-сервера в виде СМО типа М|М[1|г<оо с прогулками прибора. В аналитическом виде получена формула для расчета вероятности потерь заяовк.

2. Модель 81Р-сервера в виде СМО типа Ми|0|1|г<ю с прогулками прибора на периодах простоя системы и групповым входящим потоком.

3. Метод анализа ВВХ СМО М[х1|С|1|г<оо с прогулками прибора. Уравнения, связывающие вероятности состояний системы по времени с вероятностями состояний системы по вложенной цепи Маркова.

4. Модель управления перегрузками 81Р-сервера в виде СМО А/141 \С\1\{Ь,Н)\(Н,Я) с гистерезисным пороговым управлением нагрузкой и групповым входящим потоком.

5. Метод анализа ВВХ СМО М1*111|(£,#)|(Я,Я). Уравнения, связывающие вероятности состояний системы по времени с вероятностями по вложенной цепи Маркова. Формулы для расчета ВВХ порогового управления нагрузкой: вероятность и среднее время пребывания системы в множестве состояний перегрузки, средняя длительность цикла управления. Численный анализ характеристик гистерезисного управления нагрузкой.

Научная новизна диссертации состоит в следующем

- Для модели функционирования ЙТР-сервера в виде СМО Ми|0|1|г<со с прогулками прибора доказано соотношение, связывающее производящие функции распределения длины очереди систем конечной и неограниченной емкости, найдена производящая функция стационарного распределения вероятностей состояний системы конечной емкости.

— Получена формула для расчета вероятности потерь заявок. Для СМО типа М[х]|0|1|г<оо формула определяет соотношение, связывающее интенсивности предложенной и обслуженной нагрузки.

- Построена модель функционирования SIP-сервера в виде СМО

с гистерезисным пороговым управлением нагрузкой, которая, в отличие от ранее известных моделей, учитывает групповой характер входящего потока.

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

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

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

Теоретическая и практическая ценность Разработанные модели и формулы для вычисления их вероятностно-временных характеристик, полученные в диссертационной работе, предназначены для расчета показателей эффективности функционирования SIP-серверов в сетях последующих поколений (NGN) и могут быть применены проектными организациями и операторами сетей связи при планировании сетевых ресурсов, требуемых для обеспечения необходимого качества обслуживания пользователей. Результаты работы использованы в рамках исследований по грантам РФФИ № 10-07-00487-а «Задача управления доступом в широкополосной сети и анализ марковской модели с мультипликативным распределением вероятностей состояний» и № 12-07-00108-а "Информационная технология и программные средства моделирования и анализа механизмов управления перегрузками прокси-серверов в сети связи следующего поколения".

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

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

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

Кроме того, результаты диссертации были внедрены в учебный процесс, дисциплины «Прикладные задачи теории массового обслуживания» и «Математическая теория телетрафика», читаемые студентам направлений подготовки «Прикладная математика и информатика» и «Математика. Компьютерные науки» в РУДН, и использовались в выпускных работах бакалавров и магистерских диссертациях.

Апробация работы. Основные результаты, изложенные в диссертации, докладывались на следующих научных конференциях и семинарах:

- XLV Всероссийской конференции по проблемам математики, информатики, физики и химии РУДН (Москва, 2009);

- IV и V и VI Отраслевой научно-технической конференции-форуме «Технологии информационного общества» (Москва, 2010,2011 и 2012);

- XXIX и XXX Международной конференции «International Seminar on Stability Problems for Stochastic Models» ISSPSM (Светлогорск, 2011, 2012);

- VTI Международной научно-практической конференции «Современные информационные технологии и ИТ-образование» (Москва, 2012);

- Научном межвузовском семинаре «Современные телекоммуникации и математическая теория телетрафика» (Москва, 2013 г.)

Публикации По теме диссертации опубликовано 9 работ, из которых [2,3,4,6,8] — в ведущих рецензируемых научных журналах и содержат выносимые на защиту результаты, а [5,7,8] - в рецензируемых трудах международных конференций.

В работах, выполненных в соавторстве, соискателю принадлежит: в [1] -экспоненциальная модель функционирования сервера присутствия с прогулками прибора и анализ ее ВВХ; в [2] - модель сигнального трафика IMS и численный анализ сигнальной нагрузки и среднего времени установления соединения; в [3] - модель сервера присутствия в виде СМО типа M\G\l\co с групповым поступлением и прогулками прибора и анализ ее ВВХ; в [4] -построение и анализ СМО типа M\G\\\r с групповым поступлением и прогулками прибора, а также формулы для нахождения вероятности потери заявки и производящей функции числа заявок в очереди; в [6] - модель SIP-

сервера с гистерезисным управлением нагрузкой на основе двух порогов длины очереди и анализ ее ВВХ; в [7] - модель SIP-сервера с гистерезисным управлением нагрузкой и тремя порогами, а также формулы для вычисления основных параметров эффективности порогового управления.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и библиографии из 111 наименований. Диссертация изложена на 83 страницах текста, содержит 22 рисунков.

Содержание работы

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

В главе 1 исследованы принципы управления нагрузкой в сетях сигнализации на базе протокола SIP, ставится задача исследований.

В разделе 1.1 исследуются принципы функционирования мультимедийной IP подсистемы — функциональной сетевой архитектуры, позволяющей операторам связи внедрять новые мультимедийные услуги и использующей SIP в качестве протокола сигнализации. В основе многих мультимедийных услуг лежит услуга присутствия, позволяющая абонентам получать информацию об изменении статуса присутствия друг друга в режиме онлайн. Анализ механизма предоставления услуги присутствия позволяет говорить о возникновении групп SIP-сообщений в сети сигнализации.

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

Раздел 1.3 посвящен исследованию механизмов контроля перегрузок SIP-серверов. Представлены типовые примеры обнаружения перегрузок, требования к механизмам контроля, согласно документам IETF (Internet

Engineering Task Force), и их классификация. Исследован пороговый механизм контроля перегрузок SIP-серверов — т.н. гистсрезисное управление нагрузкой1.

В разделе 1.4 ставится задача исследований диссертационной работы.

В главе 2 построена модель функционирования SIP-сервера в виде СМО типа Afix] | G111 г с прогулками прибора и проведен анализ ее ВВХ.

В разделе 2.1 разработана математическая модель в виде однолинейной СМО с групповым входным потоком и прогулками прибора. Заявки поступают на систему группами, поток групп заявок является пуассоновским с интенсивностью Я. В каждой группе поступает случайное число заявок с вероятностью I, того, что поступит ровно I заявок. Заявка, заставшая прибор свободным, немедленно начинает обслуживаться, в противном случае занимает место в накопителе емкостью г<°о. Если поступающая группа заявок не помещается полностью в накопитель, то часть заявок заполняет очередь, а оставшиеся теряются. Длительность обслуживания является случайной величиной (СВ) с функцией распределения (ФР) В(х) и математическим ожиданием < <х>. Если в некоторый момент времени прибор освободился от обслуживания заявок, он уходит на прогулку, длительность которой есть СВ с ФР F(x) и математическим ожиданием /(|)<оо.

Введем случайные процессы (СП) £(/) — число заявок в СМО в момент времени t, и £(t) — длина очереди в СМО в момент времени t. Пусть tn,n>0 — моменты окончания обслуживания заявок, либо окончания прогулки прибора, и, тогда состояния случайного процесса £(/„ +0) образуют вложенную цепь Маркова (ЦМ). Обозначим q, =limP{£(f„ +0) = j), р,=ИтР{£(1) = j}, j>0,

] и-ко 3 J 1-Ю

°° (Ax)* °°

P = IV -——dB(x), У\Рк =1, где Pt есть вероятность поступления в СМО к Ъ к\ кл

групп заявок за случайное время наблюдения, распределенное в соответствие с ФР В(х). Аналогично определяются вероятности фк, к> 0 для ФР F(x). Кроме того, будем использовать следующие обозначения: р = Л-Ьт, р = 1тр, а = Л-/0>, а=1та, где /(" - средняя число заявок в группе. Пусть также /' -

1А6аев П.О., Гайдамака Ю.В., Самуйяов К.Е. Гистерезиснос управление нагрузкой в сетях сигнализации // «Вестник РУДН. Серия «Математика. Информатика. Физика».» - М.: Изд-во РУДН.-2011. -№4. - С. 55-73.

вероятность того, что к пачек содержат ровно / заявок. Эти вероятности вычисляются по рекуррентной формуле

к> 1.

CD

В разделе 2.2 проведен анализ построенной модели для случая бесконечной очереди (г = оо). Вьшишем систему уравнений равновесия для вложенной ЦМ + 0), я > 0 в виде

У* 0. (2)

о л=о

что позволяет найти производящую функцию (ПФ) распределения при любых р <1, /(1) <оо в следующим виде:

Q{z) = -

1 -р p{X-XL{z))-z<p(l-XL{z))

(3)

1-р + а Р(Л-ЛЦг))-г где /?(•) и - преобразования Лапласа-Стильтьеса (ПЛС) функций В(х) и F(x) соответственно, a L(:) - ПФ распределения {/.}.

Нетрудно убедиться, что связь между распределениями {q^ и

выражается системой уравнении

f , ,. st\

dx +

[ о Kl

(4)

dx\, ySO,

где С = ^о/(1) +(1-<70)ЬС1>, что позволяет найти ПФ распределения (ру) при любых р< 1,/(1) <оо в виде

Р, (1-*)(!-^(я-яод))

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

Средняя длина очереди N и среднее время ожидания заявки в очереди IV имеют вид:

2 г 20^ '

(6)

6(1) -—1 + ——т + -т2-

м» =

/(2) А/(1)6(2)

__I___

(7)

2/™ 2(1—р) 2(1—р)

Стоит отметить, что выражение (6) распадается на 3 слагаемых: первое — среднее время остаточной длительности прогулки, второе — среднее время ожидания заявки в очереди, вызванное обслуживанием на приборе-заявок из других групп, а третье - среднее время ожидания заявки в очереди, вызванное обслуживанием заявок из этой же группы. Заметим также, что вследствие формулы (5), стационарное распределение процесса £(() представимо в виде

В разделе 2,3 построенная модель исследована в случае конечной очереди (г<оо), а также проведен численный анализ ее вероятностно-временных характеристик. Введем СП ¿Г (О - число заявок в СМО в момент временя и £г(/) - длина очереди в СМО в момент времени где г — максимальная длина

очереди. Тогда 4, = 1йпР{£г('л + 0) = А у = 0,г и р] = )тР{С(0 =Л. j = 0,r.

определению Ф(г)|г = ^а^'. Тогда справедливо следующее утверждение.

Р, = Р„РР

Введем операцию «усечения ряда»: если

положим по

где дЦ находится из условия 0Г(1) = 1.

Соотношения, связывающие стационарное распределение ЦМ

+0) и стационарное распределение процесса 4*40 имеют вид

в'(

1=0 о I*"» К• .

n=r I)

(M k\

t\

dx +

S'-

i=0 n=r-i о t"0

<Л

lie,

где С'=д5/0)+(1-^)б(1). При выводе соотношений (9) и (10) использованы

методы теории процессов восстановления. Справедливо следующее утверждение о вероятности простоя прибора.

Утверждение 2. Вероятность Р0Г того, что прибор не занят обслуживанием, вычисляется по формуле 9о/(П

(И)

(12)

Из утверждений 1 и 2 вытекает следующая теорема и следствие из нее. Теорема 1.1) Вероятность потери заявки я вычисляется по формуле

г 1е0

я- = 2>;я> где — £ (/с - г+./')/,.

>=0 / А «/■-/+'

2) Для любых значений р<оо и ог<°з имеет место связь между ПФ Р(г) и

Р'(г) для СМО ограниченной и неограниченной емкости

Р'{г) = Р;(Р(г)1х+в2'), (13)

где 0 = (14)

/>г ¡М

Следствие 1. Стационарные распределения случайных процессов £(1) и С'^) связаны следующим образом:

Р,

Ро'Рр j = 0,r-1, РЛ, J = r,

(15)

где р;=\ i + pZPj-рЕрл •

V >О j=о )

Проведен численный анализ ВВХ модели. За основу начальных данных были взяты статистические данные, полученные специалистами компании British Telecom. Рассматривается SIP-сервер с максимальной длиной очереди 200 сообщений и средним временем их обработки 15 мс. Количество сообщений в группе (среднее число сообщений уведомления NOTIFY об

изменении статуса присутствия) распределено по геометрическому закону со средним /(1) =5, средняя длительность прогулки - 75 мс. Рассматривалось три случая: детерминированное распределение времени обслуживания, коэффициент вариации Сь = 0 (М'х> | D), экспоненциальное распределение, Сь= 1 (Мт\М) и распределение Эрланга четвертого порядка, С,, =0.5 {Мт\Е).

График на рисунке 1 показывает, что вероятность потери резко возрастает при увеличении дисперсии распределений. Сплошной линией на графике показана та же самая зависимость вероятности потери от поступающей нагрузки при тех же значениях р, но с уменьшенным средним числом сообщений NOTIFY в группе /0) = 4. Как видно на графике, вероятность потери уменьшается в зависимости от нагрузки в 10-100 раз с уменьшением среднего размера группы на 20%. 10"

1......-.......4- —

юг

10"

о

Е 10"

Ь; О Сц сГ

и

10"

4-

^/

у

/•у

и

_¿.__

-----мт I

---мт\

----Мт.

— Р = 4

D М Е

0.525

0.6

0.675 0,75 р, эрл

0,375 0.45

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

В главе 3 построены модели гистерезисного управления нагрузкой 81Р-сервера и проведен анализ показателей эффективности порогового управления.

В разделе 3.1 разработана математическая модель гистерезисного управления нагрузкой типа М\С\\\Я с тремя порогами: порог обнаружения перегрузки Я, порог снижения перегрузки I и порог сброса нагрузки Я (рисунок 2).

Обозначим Х(г) - СП с множеством состояний £р = 5Р0и5р2и5р3, где ^о = {(Л5)[/ = Р,* = О},9\ = {(_м)|у = ЬЯ,з = 1}, ^ = = Я + 1.Л,5 = 2}. Здесь у - число заявок в системе, а 5 - режим ее функционирования в момент времени 1>0. Заявки поступают на прибор группами, поток групп заявок является пуассоновским с интенсивностью = {0,1,2}, причем ^>¿,,¿¡=0. Как и ранее, в каждой группе поступает случайное число заявок с вероятностью I, того, что поступит ровно ; >0 заявок, а длительность обслуживания является СВ с функцией распределения В(х) и математическим ожиданием Ьт <оо. Если в результате поступления группы заявок длина очереди превышает Я, то все непоместившиеся заявки сбрасываются.

'» 1 \ \

\ I

» ■

\

—г-

в=1

\ \

5=2

1.-1 £.

Н-1 Н Н+1

И-1 Я п

Рисунок 2. Гистерезисное управление нагрузкой Пусть <<..., где — момент окончания обслуживания п -ой заявки. Для упрощения анализа будем считать, что режим функционирования .г может меняться только в моменты /п, и > 0. Тогда состояния случайного процесса

{Х(1„ + 0), и>0} образуют ЦМ с множеством состояний .Ф = У'а где

Системы уравнений для стационарных вероятностей и {/>,,.,}

выписаны в следующем разделе в более общем виде.

В разделе 3.2 проведен анализ модели гистерезисного управления нагрузкой с учетом группового входящего потока. Обозначим pjs =limP{A'(<) = (y',5)} и

qJs = lim Р {AT(i„ + 0) = (у, s)}. Система уравнений равновесия для распределения

{qjj\ вложенной ЦМ{ЛГ(/,, +0), н> 0} имеет вид

/+1 j~t+1 minf/+!,//-2) y-i'+l _

i=l k=Q M Är=0

j4t j'-f'+l Я-2 j-i+1

(«] 4-0 i-1 4-0

min(/+TÄ-2) j-i+1

min(i+Ui-2) (И _

+ X j = H-\,R-2,

i=L k=0 (16)

/+1 fl _

w/, e +evo i: iv. e iw

_____ 1 __ Jl

i-\ fe=0 i=l j=R-i Ы0 j=L /=Ä-i /t«0

Далее выпишем соотношения, связывающие стационарное распределение вложенной ЦМ {Х(г„ + 0), п> 0} и стационарное распределение {р^} процесса [Х(1), г > 0}:

Ро,о ^ з Яо.о' Л

Л) I 1=0 1Ь-0 V п-о У /»I 4=0 V п=0 /) Г ® ) ( к \ н-г =о у / *

/»м-т-ЬмЕ* £ ; (17)

Лц [ /=0 у=.тах(0,Я-О 1*0 V и=0 ) '=1 4=0 V /1=0 ))

Г-\ тшШг-2) Н / к \

"I /=£ 4=0 \ л=0 /

Я-2 °° А. ( * Л А 4=0 V п=0 /

где С = 6(1) +-у-<70 0. Л

j = L,R-l;

В разделе 3.3 проведен анализ ВВХ порогового управления нагрузкой. Отметим, что полученные в данном разделе результаты справедливы для обеих моделей главы 3.

Утверждение 3. Вероятности пребывания системы в множестве состояний перегрузки Р(У\) и множестве состояний сброса нагрузки вычисляются

по формулам

¡Л К

(18)

£ Р^С-'^ (19)

Пусть Р0 - матрица переходных вероятностей ЦМ +0), «>()} на

подмножестве :

> + 1 7-/+1

=

/ = 0,у = 0,Я-2;

¿-О

——— _

£ = - 2,} = / ■- 1, Л - 2;

(20)

0, _/</-!.

Обозначим г„ - СВ времени пребывания СП {Х(0, / ^ 0} в подмножестве .%, г,2 - в подмножестве 9\и£Рг, а г = г0+г12 - СВ длительности цикла управления. Доказано следующее утверждение и следствие из него о средних значениях данных СВ.

Утверждение 4. Математическое ожидание Ет0 СВ времени пребывания СП [Хи), < >0} в подмножестве ¿Р0 вычисляется по формуле

г

где еь =

0,...,0,1,0,..,0

I и—с./

Следствие 2. Математическое ожидание Етп СВ времени пребывания системы в множестве состояний и Уг определяется по формуле

тиУг) (22)

Етп - Ет,

а средняя длительность цикла управления Ет —

Ет = Ета + Етп. (23)

Заметим, что формулу (21) можно применять для расчета характеристик порогового управления только в случае р0 := > 1, в противном случае матрица I— Р0 становится слабо обусловленной.

Проведен численный анализ величин Етп и Ет. В примере использовались2 следующие величины порогов: ¿=73, Я= 84, Д=100, - а время обслуживания заявок детерминировано и равно 5 мс. При переходе системы в режим перегрузки входящий поток сообщений уменьшается в два раза, т.е. А,=0,5Д,. Число заявок в группе имеет геометрическое распределение с параметром 0,5. На рисунке 3 представлены графики исследуемых параметров для систем с ординарным и групповым потоком.

Интенсивность предложенной нагрузки р0

Рисунок 3. Временные характеристики СМО с гистерезисным управлением

нагрузкой

На графике видно, что при значениях нагрузки р0 < 1,3 длительность цикла управления в большей степени зависит от времени нахождения системы в

2 Pavel Abaev, Yuliya Gaidamaka, Konstantin Samouylov. Queuing Model for Loss-Based Overload Control in a SIP Server Using a Hysteretic Technique // Lecture Notes in Computer Science. - Germany, Heidelberg, Springer-Verlag. -2012. - Vol. 7469. - P. 371-378.

режиме нормального функционирования, но с ростом нагрузки доля времени в режиме перегрузки значительно возрастает. Стоит отметить также, что при значениях нагрузки р0< 1,6 исследуемые характеристики для систем с групповым и ординарным поступлением заявок практически совпадают, однако при увеличении перегрузки разница становится существенной. Это связано с тем, что система с групповым поступлением за счет большей неоднородности входящего потока имеет возможность быстрее перешагнуть порог, при котором происходит изменение режима функционирования.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1. Разработана новая модель функционирования 81Р-сервера в виде СМО типа <оо с прогулками прибора, доказано соотношение, связывающее производящие функции распределения длины очереди систем конечной (г<оо) и неограниченной (г = оо) емкости, найдена ПФстационарного распределения вероятностей модели конечной емкости.

2. Получена формула расчета вероятности потерь заявок, имеющая явный физический смысл, для моделей с групповым потоком типа М|0|1|г <со.

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

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

Основные результаты диссертации отражены в следующих опубликованных работах:

1. Мушили Н.М., Сопин Э.С. Анализ трафика и моделирование производительности сервера присутствия подсистемы IMS // XLV Всерос. конф. по проблемам матем., информ., физики и химии: Тезисы докладов. -М.:РУДН. - 2009. — С. 188-189.

2. Самуилов КЕ„ Сопин Э.С., Чукарин А.В. Оценка характеристик сигнального трафика в сети связи на базе подсистемы IMS // Т-Сошш -Телекоммуникации и Транспорт. -2010. — № 7.-С. 8-13.

3. Мушили Н.М., Самуилов К.Е., Сопим Э.С. Модель функционирования сервера присутствия в сети NGN // T-Comm - Телекоммуникации и Транспорт. -2010.-№7.-С. 116-118.

4. Самуилов К.Е., Сопин Э.С. К анализу системы Mm|G|l|r с прогулками прибора // Вестник РУДН. Серия «Математика. Информатика. Физика». - 2011. -№1.-С. 91-97.

5. Sopin К Analysis of Mw|G|l|r queue with a resume level // XXIX Int. Seminar on Stability Probl. for Stochastic Models: Book of abstracts. - M.: IPI RAS. - 2011. -P. 53-55.

6. Гайдамака Ю.В., Самуилов K.E, Сопин Э.С. Модель одной системы массового обслуживания типа М/G/l с гистерезисным управлением входящим потоком // T-Comm - Телекоммуникации и Транспорт. - 2012. - № 7. - С. 60-62.

7. Gaidamaka К, Samouylov К., Sopin Е. Analysis of M/G/l queue with hysteretic load control // XXX Int. Seminar on Stability Probl. for Stochastic Models: Book of abstracts. -M.: IPI RAS. - 2012. - P. 87-89.

8. Сопин Э.С. Анализ показателей качества функционирования SIP-сервера с гистерезисным управлением нагрузкой // VII Межд. научно-практ. конф. «Современные информационные технологии и ИТ-образование»: Сб. трудов. -М.: ИНТУИТ.РУ. - 2012. - С. 734-739.

9. Сопин Э.С. Анализ модели M|G|l|r с групповым поступлением и гистерезисным управлением нагрузкой // Вестник РУДН. Серия «Математика. Информатика. Физика». - 2013. - №2. - С. 38-44.

Сопип Эдуард Сергеевич (Россия)

Модели систем ограниченной емкости с групповым входящим потоком и их применение к анализу показателей эффективности серверов протокола

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

Разработана модель функционирования 81Р-сервера в виде СМО типа М[С| 1 |г с учетом группового входящего потока и гистерезисного управления нагрузкой. Получены соотношения для расчета стационарного распределения системы и формулы для вероятностно-временных характеристик порогового управления нагрузкой, таких как вероятность нахождения системы в режиме перегрузки, среднее время пребывания системы в режиме перегрузки и средняя длительность цикла управления.

Finite capacity models with batch arrivals developing and their application to session initiation protocol servers performance measures

SIP-server model in terms of M|G|l|r queuing system with batch arrival and vacations is introduced in the thesis. Generating function for queue length equilibrium distribution is obtained. The relationship between equilibrium distributions of infinite and limited capacity queues is shown as well as formula for loss probability is derived, which binds offered and serviced load intensities.

SIP-server model in terms of M|G|l|r queue with batch arrival and bysteretic load control is introduced. System of equations for steady-state probability distribution is obtained and formulas for basic hysteretic load control performance measures are derived: probability that the system is in overload mode, mean time spent in overload mode and mean control cycle time.

установления сессии

Eduard Sopin (Russia)

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

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

российский университет дружбы народов

04201364003 на правах рукошси

Сопин Эдуард Сергеевич

Модели систем ограниченной емкости с групповым входящим потоком и их

применение к анализу показателей эффективности серверов протокола установления сессий

Специальность 05.13.17 - «Теоретические основы информатики» (по физико-математическим наукам)

Диссертация

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

Научный руководитель доктор технических наук профессор

Самуйлов Константин Евгеньевич

Москва-2013

оглавление

список основных обозначений....................................................................3

Введение............................................................................................................5

ГЛАВА 1 Исследование принципов управления нагрузкой в сетях

сигнализации на базе протокола SIP.......................................11

1.1. Принципы функционирования подсистемы IMS..........................11

1.2. Простейшая модель SIP-сервера с прогулками прибора на

периодах простоя............................................................................15

1.3. Гистерезисное управление нагрузкой............................................22

1.4. Постановка задачи исследований...................................................39

ГЛАВА 2 построение и анализ модели функционирования SIP-

сервера в виде смо с прогулками прибора............................41

2.1. Построение модели..........................................................................41

2.2. Анализ модели с неограниченной очередью.................................43

2.3. Модель с конечной очередью и анализ ее вероятностно-

временных характеристик..............................................................47

ГЛАВА 3 построение и анализ модели гистерезисного управления

нагрузкой SIP-сервера.................................................................62

3.1. Модель SIP-сервера в виде СМО с пороговым управлением

нагрузкой и ординарным входящим потоком..............................62

3.2. СМО с групповым поступлением заявок и пороговым

управлением нагрузкой..................................................................67

3.3. Анализ показателей эффективности порогового управления......72

Заключение.....................................................................................................80

Библиография..................................................................................................81

Список основных обозначений

Я - Интенсивность потока групп заявок.

/( - Вероятность того, что группа состоит из i заявок.

1(к) - &-й начальный момент распределения длины группы

заявок.

В(х) - Функция распределения длительности обслуживания

заявки.

Ь{к) - к-й начальный момент длительности обслуживания

заявки.

F(x) - Функция распределения длительности прогулки

прибора.

у W - к-й начальный момент длительности прогулки прибора.

г - Максимальная длина очереди.

<?r(t) ~ Случайный процесс числа заявок в системе емкости г в

момент времени t.

£r(t) ~ Случайный процесс длины очереди в системе емкости г

в момент времени t.

qr - Стационарные вероятности по вложенной цепи

Маркова процесса

p'j ~ Стационарные вероятности по процессу C,r(t).

С - Нормирующая константа.

Р - Величина предложенной нагрузки на систему.

Pr{z) _ Производящая функция распределения рг}.

Qr(z) ~ Производящая функция распределения q".

L(z) - Производящая функция распределения .

1к - Вероятность того, что в к группах находится из i

заявок.

P(s) - Преобразование Лапласа-Стилтьеса функции

распределения В(х).

cp{s) ~ Преобразование Лапласа-Стилтьеса функции

распределения F(x). Рк - k-Vi экспоненциальный момент функции распределения

В{х).

(рк - к-й экспоненциальный момент функции распределения

F{x).

рг - Вероятность того, что прибор не занят обслуживанием

заявок.

N - Средняя длина очереди.

w - Среднее время ожидания в очереди.

п - Вероятность потери заявки.

L - Порог снижения перегрузки.

Н ~ Порог обнаружения перегрузки.

R - Порог сброса нагрузки.

Xs - Интенсивность поступления групп заявок в режиме

функционирования л\ т0 - Случайная величина времени пребывания системы в

режиме нормального функционирования (5 = 0). г - Случайная величина времени пребывания системы в

режиме перегрузки и сброса нагрузки (^ = 1, 5 = 2). г - Случайная величина длительности цикла управления.

введение

В настоящее время телекоммуникационные компании разрабатывают и внедряют все больше новых мультимедийных услуг. Базой для их внедрения является мультимедийная IP-подсистема (IP Multimedia Subsystem, IMS) [2, 91], позволяющая предоставлять поверх протокола IP на основе единой сети как традиционные услуги связи, так и новые услуги сетей последующих поколений (Next Generation Networks, NGN). В связи с большой популярностью этих услуг сети телекоммуникаций на базе IMS, работающие на основе протокола установления сессий (Session Initiation Protocol, SIP [38, 89]), работают в условиях перегрузки. Кроме того, мультимедийные услуги существенно меняют характер трафика установления сессий (сигнального трафика) [10]. В частности, услуга присутствия [36, 37, 40] (англ. presence service) подразумевает отправку сообщений уведомления одновременно нескольким пользователям.

Для анализа характеристик обслуживания сигнального трафика, таких как вероятность потерь, среднее время ожидания, параметры управления нагрузкой и др., применяются модели однолинейных систем массового обслуживания (СМО). При построении и анализе таких моделей используется аппарат теории вероятностей [119, 120], теории массового обслуживания [20, 63, 83, 88, 92, 93, 95, 96, 97, 105] и теории телетрафика [100, 102, 121]. Существенный вклад в развитие данной области внесли российские и зарубежные ученые: Л.Г. Афанасьева [11, 12, 77], Г.П. Башарин [78, 79, 80, 81, 82], Е.В. Булинская [12, 77], В.М. Вишневский [85, 86, 87], Б.С. Гольдштейн [90], В.А. Наумов [57, 58, 105], А.В. Печинкин [7, 15, 83], А.П.Пшеничников [98, 118], К.Е. Самуилов [57, 58, 106, 107, 108, 109], С.Н.Степанов [94, 116], А.Д. Харкевич [82, 98], И.И. Цитович [13, 116], С.А. Шоргин [7, 113], V.B. Iversen [94], Martikainen О. [57, 58], М. Roughan [69, 70] и др.

Принципиально важным является исследование систем конечной емкости, так как время ожидания установления соединения является

критическим параметром, строго ограниченным как спецификациями протокола SIP [38] и рекомендациями МСЭ (Международный союз электросвязи, ITU) [47, 48], так и реальным поведением абонента. Ввиду изложенного, актуальной является задача разработки моделей и методов для анализа функционирования серверов протокола SIP в условиях перегрузки с учетом группового характера потока поступающих сообщений.

В современных телекоммуникационных сетях новые мультимедийные услуги занимают все большую долю трафика данных и сигнального трафика по сравнению с традиционными. Исследования [10] на подсистеме IMS оператора British Telecom в 2007 году показали, что доля сигнального трафика, генерируемого одной только услугой присутствия, составляет более 50%. Одна из первых постановок задач, в которой было предложено использовать СМО с групповым потоком и ненадежным прибором для анализа производительности SIP-сервера, дана в работе [16]. Большое количество работ посвящено исследованию подобных моделей как с ординарным входящим потоком [11, 12, 14, 23, 49, 53, 95], так и групповым [18, 22, 56, 54, 55]. Отдельно отметим группу публикаций, в которых рассматриваются модели с «разогревом», т.е. режимом функционирования с пониженной интенсивностью обслуживания [19, 27, 29, 34, 35, 50, 51, 55, 59]. Основными исследуемыми параметрами эффективности таких моделей являются среднее время ожидания и его дисперсия, а также вероятность потерь для систем конечной емкости, однако автору не известны публикации, в которых была бы получена формула вероятности потерь в явном виде для систем с групповым потоком и ненадежным прибором типа М[Х] \ G111 г.

Вследствие того, что современные сети используют SIP в качестве протокола сигнализации, на серверах этого протокола нередко возникают перегрузки. Вопрос предотвращения перегрузок в системах сигнализации не является новым [28, 66, 74, 99, 109], однако в случае с SIP проблема усугубляется тем, что в первоначальных спецификациях протокола

вопрос управления нагрузкой не был детально проработан. В связи с этим большое количество публикаций посвящено разработке эффективных механизмов предотвращения перегрузок [9, 25, 26, 31, 32, 33, 52, 60, 61, 62, 64, 65, 75, 76]. Основными параметрами эффективности гистерезисного управления нагрузкой являются среднее время возврата из режимов перегрузки и вероятность пребывания в режимах перегрузки. В статье [8], выполненной на кафедре систем телекоммуникаций РУДН, построена аналитическая модель типа М \ М | 11 (£, Н) | В и проведено имитационное моделирование системы с детерминированным обслуживанием. В работе [73] исследована модель типа М10111 (Ь, Я) с

упрощенным гистерезисным управлением. Модель с двумя петлями анализируется в статьях [17, 69, 70] при помощи аппарата мартингалов. Отдельно отметим работу [7], в которой решается задача оптимизации порогов управления с целью минимизации среднего времени возврата из состояний перегрузки. Модели гистерезисного управления типа М[Х] | С11 с групповым входящим потоком автору неизвестны.

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

Диссертация имеет следующую структуру. В главе 1 исследованы принципы управления нагрузкой в сетях сигнализации на базе протокола 81Р, ставится задача исследований. В разделе 1.1 исследуются принципы функционирования мультимедийной 1Р подсистемы — функциональной сетевой архитектуры, позволяющей операторам связи внедрять новые мультимедийные услуги и использующей 81Р в качестве протокола сигнализации. В разделе 1.2 исследована упрощенная марковская модель функционирования 81Р-сервера с групповым поступлением и прогулками прибора на периодах простоя. Раздел 1.3 посвящен исследованию

механизмов контроля перегрузок SIP-серверов. В разделе приводится классификация типов и причин возникновения перегрузок, а также описываются пять основных механизмов их предотвращения, предложенных рабочими группами IETF (Internet Engineering Task Force): механизм снижения скорости передачи, механизм просеивания потока сообщений, механизм управления размером окна, механизм снижения нагрузки по сигналу и механизм временного запрета передачи. В разделе 1.4 ставится задача исследований диссертационной работы. Разделы 1.1 - 1.4 написаны на основе публикаций [101, 104, 112] с участием автора.

В главе 2 построена модель функционирования SIP-сервера в виде СМО типа М[Х] | G | 11 г с прогулками прибора и проведен анализ ее вероятностно-временных характеристик (ВВХ). В разделе 2.1 разработана математическая модель в виде однолинейной СМО с групповым входным потоком и прогулками прибора. В разделе 2.2 проведен анализ построенной модели для случая бесконечной очереди (г = оо). Отметим, что результаты исследований подобных СМО широко известны, однако в данном разделе был применен отличный от методов других авторов математический аппарат, позволяющий использовать результаты исследований системы бесконечной емкости для расчетов ВВХ конечной системы. В разделе 2.3 построенная модель исследована в случае конечной очереди (г< оо). Доказано соотношение, связывающее производящие функции распределения длины очереди систем конечной и неограниченной емкости, найдена производящая функция стационарного распределения вероятностей состояний системы конечной емкости, а также получена формула для расчета вероятностей потерь. Для СМО типа М[Х] IGI 11 г < оо формула определяет соотношение, связывающее интенсивности предложенной и обслуженной нагрузки. В заключение раздела проведен численный анализ параметров эффективности модели. Разделы 2.1 — 2.2 написаны на основе публикаций [72, 103, 111] с участием автора.

В главе 3 построены модели гистерезисного управления нагрузкой 81Р-сервера и проведен анализ показателей эффективности порогового управления. В разделе 3.1 разработана математическая модель гистерезисного управления нагрузкой типа М\0\\\(Ь,Н) \ (Н, Я.) с тремя

порогами: порог обнаружения перегрузки Н, порог снижения перегрузки Ь и порог сброса нагрузки Я. Получены формулы для расчета стационарного распределения вероятностей системы. В разделе 3.2 разработана модель гистерезисного управления нагрузкой с учетом группового входящего потока и получена системы уравнений для вычисления стационарного распределения вероятностей по вложенной цепи Маркова и по процессу. Кроме того, в разделе показано, что для расчета параметров эффективности порогового управления достаточно вычислить только вероятности по вложенной цепи Маркова. В разделе 3.3 проведен анализ вероятностно-временных характеристик порогового управления нагрузкой, в том числе среднего времени возврата и цикла управления, а также вероятности пребывания в режимах перегрузки и сброса нагрузки. В заключение раздела проведен численный анализ указанных характеристик, который показал, что групповой характер входящего потока существенно влияет на среднее время возврата и цикла управления. Разделы 3.1 - 3.3 написаны на основе публикаций [24, 84, 114, 115] с участием автора.

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

Наиболее значимые, с точки зрения автора, результаты сформулированы в виде утверждений, теорем и следствий из них. Для проведения численного анализа разработано программное средство с использованием пакета прикладных математических программ БсПаЬ с открытым исходным кодом.

Разработанные модели и формулы для вычисления их вероятностно-временных характеристик, полученные в диссертационной работе, предназначены для расчета показателей эффективности

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

Помимо исследований при написании диссертационной работы, автором также проводились сопутствующие исследования, в частности, проведен анализ методов балансировки нагрузки несущей в системах LTE-Advanced [110].

Таким образом, в диссертационной работе решаются перечисленные ниже задачи:

1. Построение и исследование модели SIP-сервера в виде СМО типа M[X]|G|1| г < оо с прогулками прибора на периодах простоя системы с учетом группового входящего потока.

2. Анализ ВВХ СМО M[X]|G|1| r<œ с прогулками прибора, таких как среднее время ожидания и вероятность потерь.

3. Построение и исследование модели управления перегрузками SIP-сервера в виде СМО MlX] \G\1\(L,H}\(H,R) с

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

4. Анализ ВВХ СМО М[Х] \G\\\(L,H)\(H,R), таких как

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

ГЛАВА 1

Исследование принципов управления нагрузкой в сетях

сигнализации на базе протокола SIP

1.1. Принципы функционирования подсистемы IMS

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

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

Многоуровневая архитектура подсистемы IMS впервые была предложена консорциумом 3GPP [2, 5, 6] (3GPP Release 5) и предназначалась изначально для предоставления услуг Интернета через GPRS (General Packet Radio Service). В дальнейшем функциональность IMS была расширена для поддержки других сетей, таких как ТфОП (Телефонная сеть общего пользования), CDMA (Code Division Multiple Access), WLAN (Wireless Local Area Network) [86] и LTE (Long Term Evolution) [117].

Сейчас концепция IMS применяется объединенным техническим комитетом TISPAN (Telecoms & Internet Services & Protocols for Advanced Networks) в качестве ключевого элемента инфраструктуры сетей следующего поколения (NGN - Next Generation Networks).

Среди основных свойств архитектуры IMS можно выделить следующие:

- независимость от среды доступа - позволяет операторам и поставщикам услуг конвергировать фиксированные и мобильные сети;

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

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

- возможность взаимодействия различных видов услуг;

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

CSCF

P-CSCF

S-CSCF

I-CSCF

/Уровень передачи данных

данные сигнализация

Уровень уп�