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

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

НСАНГУ Мушили Мама

РАЗРАБОТКА ВЕРОЯТНОСТНЫХ МОДЕЛЕЙ ДЛЯ АНАЛИЗА ПОКАЗАТЕЛЕЙ ЭФФЕКТИВНОСТИ УСТАНОВЛЕНИЯ СЕССИЙ В МУЛЬТИСЕРВИСНОЙ СЕТИ

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

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

2 ОЕЗ Ш 005008964

Москва-2012

005008964

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

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

профессор

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

Официальные оппоненты: доктор физико-математических наук,

профессор

Печинкин Александр Владимирович

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

Лузгачев Михаил Васильевич

Ведущая организация: Московский технический университет

связи и информатики (МТУСИ)

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

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

Автореферат разослан «23» января 2012 г.

Ученый секретарь

диссертационного совета 0 М.Б. Фомин

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

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

На настоящем этапе развития инфокоммуникаций широко внедряются новые телекоммуникационные технологии, такие как передача видео данных и услуга присутствия пользователей в сети (англ. Presence Service). Сервер присутствия обеспечивает прием, хранение и распределение информации о присутствии пользователей в сети и оказывает положительное влияние не только на показатели эффективности поставщиков услуг, но и на эффективность работы самих пользователей за счет повышения их коммуникационной активности. Для стандартизованной на международном уровне мультимедийной подсистемы IMS (IP Multimedia Subsystem), используемой при построении мультисервисных сетей, основным протоколом сигнализации является протокол установления сессий SIP (Session Initiation Protocol), который используется для установления, модификации и разъединения сессий пользователей. Задача оценки объема сигнальной нагрузки и времени установления соединения в подсистеме остается мало исследованным, так как для протокола SIP до настоящего времени не стандартизованы методики, позволяющие проводить анализ параметров его производительности. Для анализа характеристик, влияющих на качество обслуживания трафика, применяются различные модели, при построении и анализе которых используются методы и модели математической теории телетрафика и теории массового обслуживания. Вклад в развитие этих моделей и методов их анализа внесли российские и зарубежные ученые - Г.П. Башарин, A.B. Печинкин, Б.С. Гольдштейн, А.П. Пшеничников, К.Е. Самуйлов, С.Н. Степанов, В. М. Вишневский, С.Я. Шоргин, И.И. Цитович, Henning Schulzrinne, Medhi J. E., Templeton J. G. С., V. B. Iversen, V. Hilt, F. Kelly, J. Rosenberg, K. Ross и др.

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

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

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

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

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

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

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

3. Для модели сервера присутствия в виде системы массового обслуживания (СМО) М|я I М 111 °° IBS с отключением и с разогревом прибора, когда сервер либо работает

(и.т) (p.q)

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

распределения вероятностей и предложен метод расчета вероятностных характеристик системы.

Практическая ценность работы. Исследованные модели позволяют оценить показатели эффективности предоставления услуг при установлении соединения в сетях последующих поколений. С помощью разработанных алгоритмов может быть проведен численный анализ реальных систем с нормируемыми международными стандартами показателями эффективности их функционирования. Математические модели сервера присутствия построены при весьма общих предположениях о поступающей нагрузке сообщений протокола SIP. Поэтому, модели применимы для достаточно широкого класса реальных систем, что позволит поставщику телекоммуникационных услуг достичь приемлемого качества предоставления услуги присутствия. Результаты работы использованы в рамках исследований по гранту РФФИ № 10-07-00487-а «Задача управления доступом в широкополосной сети и анализ марковской модели с мультипликативным распределением вероятностей состояний» и в НИР 020612-1-173 «Разработка математических моделей и анализ информационно-телекоммуникационных сетей».

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

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

- на отраслевых научно-технических конференциях - форум «Технологии информационного общества», МТУ СИ (Москва, 2009, 2010);

- на научных семинарах кафедры систем телекоммуникаций РУДН (Москва, 2010 и 2011);

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

- на российской научно-технической конференции общества радиотехники, электроники и связи имени A.C. Попова (Москва, 2009);

- на международной научной конференции «Information and Networking Technologies» -DCCN (Russia, 2010);

- на международной научно-практической конференции «Перспективные разработки науки и техники». (Польша, Przemys, 2011).

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

В работах, выполненных в соавторстве, соискателю принадлежит, кроме алгоритмов и численного анализа: в [1,3,4,6] - модель для анализа вероятностно-временных характеристик процесса установления соединения; в [2,5], модели и методы анализа как группового, так и ординарного поступлений заявок в СМО; в [8], рекуррентный алгоритм расчета стационарных вероятностей и вероятности блокировки сообщений оповещения статуса пользователей. Все результаты, выносимые на защиту, получены автором лично.

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

СОДЕРЖАНИЕ РАБОТЫ

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

Глава 1 посвящена исследованию процессов обмена сигнальными сообщениями протокола SIP при установлении соединения и уведомлении пользователей в сетях NGN и применения к их анализу систем с групповым поступлением заявок. В разделе 1.1 исследованы особенности процесса обмена сигнальными сообщениями, в части вероятностно-временных характеристик проанализирована процедура установления VoIP-соединения (англ. Voice over IP, передача речи по сети протокола IP). Выведена формула для вычисления среднего времени установления VoIP-соединения с учетом временных задержек ожидания и обработки заявок в узлах сети. Для этого определены задержки на каждом участке подсистемы прокси-серверов в зависимости от функций управления сеансами связи. Принимая во внимание особенности транспортного протокола, учтена задержка сигнальных передач из-за их повторных передач. В разделе 1.2, для исследуемых типов серверов в сетях последующих поколений, проведен аналитический обзор известных результатов для различных моделей систем

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

Раздел 1.3 посвящен анализу простейшей СМО типа м'к' IM 111 R, R < , в которой, для случая с надежным прибором и бесконечной емкостью накопителя (R = °°), поступление заявок производится группами фиксированной длины К, а для случая системы с прогулками прибора, исследуется процесс уведомления пользователей сообщениями NOTIFY с ординарным входящим потоком и с ограниченной емкостью накопителя (R<°° ). Найдены стационарное распределения числа заявок в СМО, а также другие важные вероятностно-временные характеристики системы. Рис. 1 показывает, как среднее время ожидания обслуживания заявок зависит от нагрузки, поступающей на сервер, и от размера поступающей группы заявок.

Рис. 1. Среднее время ожидания обслуживания в СМО м'к' IМ111К. Получены стационарные вероятности состояний СМО М!к}1М111 Я, а также ее

важнейшие характеристики, такие как среднее значение числа заявок Ыг в очереди, представленное в виде (1):

1 02 I

(l-^-e (Я + 8 )(I

N' = «r' +

Рол'

(1)

^(r-lfc-^J + l

где, Лг = ргЛ + рг0 является вероятностью блокировки и вероятность р0, вычисляется по формуле:

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

Глава 2 посвящена разработке математической модели для анализа показателей качества функционирования протокола SIP в процессе установления соединения, с учетом ретрансляций сообщений из-за ошибочных передач. Определены основные задачи исследования, показана их актуальность, а также необходимость исследования математических моделей, описывающих работу протокола установления сессий. В разделе 2.1 сформулированы требования к функциональной модели, разработанной на основе принципов работы протокола SIP учитывая механизм обеспечения передачи для случая, когда сообщения могут быть потеряны или искажены. В случае возникновения различных сбоев протоколом SIP запускается механизм повторной передачи сообщения. Отметим, что ретрансляция предусмотрена только для сообщений INVITE, 200-ÛK и АСК. Механизм передачи сообщений 100-TRYING и 180-RINGING надежен, поэтому при построении модели предполагается, что они передаются без ошибок. Б разделе 2.2 построена математическая модель в виде цепи Маркова (ЦМ) для анализа вероятностных характеристик процесса установления соединения. В соответствии с этой моделью предполагается, что успешная передача SIP-терминалом сообщений INVITE, 2ОО-ОК или АСК происходит по истечению таймеров T"\T£'соответственно, где величины и,, я, и и3, 1 < n,,«,,«, < N, являются номерами успешных попыток повторной

Рол ~

передачи. Построенная модель позволяет получить вероятности перехода по цепи для заданного числа шагов. Предполагается, что успешная передача происходит с вероятностью (l - g) для INVITE и АСК и с вероятностью (l-/) для 200-СЖ. Таким образом, сбой передачи происходит с вероятностью g для INVITE и АСК и с вероятностью / для 200-СЖ, т.е. в этом случае происходит ретрансляция (повторная передача) сообщения.

При анализе математической модели для вычисления характеристик качества обслуживания, необходимо определить число п шагов ЦМ до первого попадания в состояние ЗЛ^ + 4 («Setup») из состояния 1 («INVITE»), n = 3,---,3N + 3. Это счисло шагов определяет время установления соединения с учетом ретрансляций из за ошибочных передач сообщений. Диаграмма переходов состояний модели ЦМ показана на рис. 2., а соответствие номеров состояний ЦМ состояниям протокола SIP приведено в таблице 1.

В соответствии с этой моделью, проанализирована цепь Маркова, и получены условные вероятности перехода по цепи при заданном числе шагов. Показано, что вероятность P{f,g) успешного установления сессии по протоколу SIP с учетом вероятностей повторных передач может быть вычислена по формуле

Рис. 2. Диаграмма переходов состояний ЦМ

п=Э (^.nj.njieNin)

L,3N+4

(2)

где /i.âii+V" =ag"'+"J/"!H множитель a = (l-g)!(l-/) равен вероятности успешной передачи всех трех сообщений - INVITE, 20Q-OK и АСК.

Таблица 1. Соответствие состояний ЦМ состояниям протокола SIP

Номер состояния ЦМ Состояние SIP Описание

0/3JV + 5 «старт»/«финиш » ожидание запроса из внешней среды / транзакция заблокирована

1 Передача сообщения INVITE

1, 1<п, <N «Г,"1 » -ая повторная передача сообщения INVITE, 1 < n, < N

N + 2 «200» Передача сообщения 200-СЖ

n2 + N + 2, 1 <n2<N «I2-» П2 -ая повторная передача сообщения 200-OK,\<n2<N

IN + Ъ «ACK» Передача сообщения АС К

n,+2N + 2, «7Г» гц -ая повторная передача сообщения АСК, 1 < пъ < N

ЪN+A «setup» Сессия установлена

Получена формула для вычисления вероятности успешного установления и вероятности прерывания соединения по протоколу SIP. Лемма 1.

P(f,g) = \-P(f,g) = l-{l-f"*1b-g™iu (4)

Для случая равенства вероятностей ошибочной передачи сообщений f = g и равенства значений таймеров 7", = Т2 = Г3 = Т, в аналитическом виде получена формула для расчета среднего времени ретрансляции сообщений протокола SIP:

Я

,ЗГГ &-,) (l-(2g)»«) Л

1(1-«™) О-2g) JJ' (5)

Численный анализ, проведенный в разделе 2.3, показал достоверность полученных формул. Для случая §<10"' и Г = 0.5 с на рис. 3, показан график среднего времени ретрансляции сообщений протокола БГР.

0.05

0.15

Dsip, 0.2

0.1

0

6

N

Рис. 3. Среднее время ретрансляции SIP-сообщений в зависимости от числа ретрансляций N и вероятности ошибочной передачи g .

Глава 3 посвящена анализу вероятностно-временных характеристик процесса передачи информации по протоколу sip в сетях NGN и моделей функционирования сервера присутствия. Услуга оповещения о статусе пользователей в сетях подвижной связи 3-ого (3G) и 4-ого (4G) поколений является одной из самых востребованных. В диссертации кратко охарактеризована концепция предоставления этой услуги и в терминах теории массового обслуживания поставлена задача анализа показателей эффективности функционирования сервера присутствия подсистемы ims. В разделе 3.1 проводится анализ модели сервера присутствия как системы с групповым поступлением заявок и прогулками обслуживающего прибора. Учитывая, что сервер выполняет и другие работы по обслуживания очередей, целесообразно исследовать модель в виде СМО типа m'x'|GI1I°o с групповым поступлением заявок и прогулками прибора на периодах простоя системы. Для описания процесса обработки очереди в сервере присутствия исследована модель типа m|X'|GI1 с неограниченной емкостью накопителя. Введены случайные процессы (СП): числа заявок в СМО и £ "'(/)

длина очереди в СМО в момент времени (> 0. С помощью метода вложенных цепи Маркова получены формулы для ПФ для числа заявок в системе и в очереди соответственно.

Пусть t„,n>0 - моменты окончания обслуживания заявок, либо окончания прогулки прибора, тогда состояния случайного процесса образуют вложенную цепь

Маркова. Обозначим

и

Обозначим также (3^ = |е~ --<1В{х), ^Р,. =1, где р^ можно интерпретировать

О ^! к=0

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

величина фк, к> 0. Кроме этого, введем следующие обозначения: р = ХЬ''\ р = /('®р ,

СХ = А,/''' , а = /'''(X , где /"' - среднее число заявок в группе. Моменты распределений будем обозначать соответствующими малыми латинскими буквами с указанием порядка

момента, например: ¿>(2' = I х2(/(В(х)) . ПФ рассматриваемых

¡=1 о

распределений будем обозначать большими латинскими буквами - = ^Г р.х1,

м

Q(z) = г ¿(г) = У/. Обозначим I- вероятность того, что к групп содержат г

>-0 ¡=о

заявок. Очевидно, что это есть к-кратная свертка распределения I, и тогда можно установить следующую связь соответствующих ПФ: [ук (г) = = (¿(г))*,

;=о

Утверждение I. При р<1, /'" < <*> ПФ распределения ({1 имеет вид

лМ 1-р Р(А.-№.(г))-гф(Ь-М,(г))

21г/ =--г-т-тт-- и ПФ распределения р. имеет вид

1-р+о 1

П1} ос (1-1(г)ХР(Х-^(г))-г)И

Найдено среднее время ожидания заявки в очереди в следующем виде

лР>

2 ^(2)

В разделе 3.2 с учетом группового поступления заявок решена задача о расчете задержек обслуживания сообщений NOTIFY на основании модели, представленной в виде СМО

типа М[Х]/ М /1/oo/BS с прогулками прибора на периодах простоя и разогрева -

(м) (p.q)

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

Введем случайный процесс (СП) >о}, где описывает число заявок в СМО в

момент времени г и ^ <2'(г),/>о}, £<2|(') характеризует номер состояния, на котором находится прибор в момент времени 1, очевидно, что множество состояний {к(?),?>0} СП К(г) = ,2)(г)).' ^ О} имеет вид К = {(0,0), (0,1)11 (/, ]\/ >1,7= 0,1,2}.

Обозначим я1,=Нш/'{^г>(О = 1,?(2)(0 = 1}, п,0 =НшР{^(2)(0 = (2) (0 = 0} и

Я1.2=ИтР|^2'(0 = ',С'г'(') = 2}, > -1, стационарные вероятности системы соответственно в состояниях прогулки, разогрева и обслуживания. Тогда

соответствующие этим распределениям ПФ будут иметь вид Я, (г) = ,

|'=0

Я0(г) = 2^ТГ,0г' и Я2(г) = ^ЗГ1.2г1 соответственно. ¡=0 (=1

Утверждение 2. При любых р < 1 и у < |1, ПФ распределения л ^ имеет вид:

7 = 1; *00 -97*10

г+е V

x(i-z.(z))+9.T0"

1-— fy +9„

г,

7=0;

+1 —+ р-Яоо

v ^ J м-

(7)

i-p4

- 7 = 2

В рассматриваемой модели, находясь в состоянии разогрева, пока завершается

обслуживание заявки, сервер может его прерывать и с вероятностью 1 —q, возвращаться в

состояние полной занятости или, берет дополнительную прогулку с вероятностью q. Для

упрощения задачи предположено что q = 0, что более адекватно отражает процесс

обработки очереди сообщений уведомления NOTIFY сервером присутствия.

Следовательно, рассматривается модель сервера присутствия в виде СМО

М[Х1/ М /1/oo/BS с групповым поступлением заявок. (и.у) (р,0)

Утверждение 3. При любых р < 1 и у < ц, ПФ распределения л,у определяются следующими формулами:

х+е V Л.(1-гХг))+в ^Г0 (я.+г+е„)

7=1;

Х(1-Мг))+у+в„ -Хг(1-^(г)Хж.(г)+я,(г))+у(1-гХяо(г)-яа,)

Хг(1-Дг))-ц(1-г)

где я0], Яда являются вероятностями простоя сервера и имеют вид

7 = 2.

Я ос = (1 — Р )р

^01 = р(1-р

_ л X

р + р\

—У»-1'

0,+тЛ и.

я + (1-/,)у+е,, я+у+е„

е(я+е„ +у)

е(я+у+в„)

Показано, что ПФ я (г) числа заявок в системе имеет вид,

я г =

(г-1)

Яг(1-4г))+ц(г-1)

+7

и(х+е)

■""Ча-^у+в'

(9)

Теперь, имея ПФ X (г), можно найти среднее число заявок в системе по формуле

ЛГ_[яу(Я+/'")| Ох-уХх+у+е,) [2ц2(1-р)г (т+в,Х1-р)

2ц2(1-р) (у+е.)

и(я+е

|(1-Р)

2М-Ч1-Р) в

(10)

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

Утверждение 4. При ограниченной емкости накопителя /? < <» и у < ц , распределение

|я } е {0,1,2} модели М,/ М /1/Л <°°/В8 может быть вычислено по следующему

(м) (м)

алгоритму.

Шаг 1. Вычисление параметра уг по формуле

(Я +8„ +у)-А/(Х+Э1. +у)2 -АКсп

2сп

Шаг 2. Вычисление вспомогательных величин т„ тгр ,тгк и т-у ,

по формулам

IР Р-К) Р~к„

Шаг 3. Вычисление параметра аг =

-,где

к0 + к, + к2 у:-у,

рг''-Р... к;1-к,

к, =т,. + ——т„., к, =т„ +т,, + ■!-—>и,„

¿',„-1 Р-1

Уг -Уг у г

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

[аДш2рр -тик-' -т^у- ),} = 2

^•у Г

*<Г> =

0,. +у

а„] = 0

^ 1 г-1 »1

ф" т 'П01«г'/ = 1

е.. 0 I • ,

ртг_,о Н--т 0 н—т , кх,,у = 2

" ц ц

Одна из важных вероятностных характеристик является вероятностью потерь заявок из-за ограничения емкости накопителя, которая найдена в следующем виде:

(г! ( Г^-УГ1 1 9,- 0

■я; 1 = (шг0 +тл1 + т,2)а, = ——Ъ"ткт т01 + рт,_,г +—тг0 + тг1 Ь . (11)

в ИР)

Имея ПФ распределения длины очереди, можно найти среднее число заявок в СМО в

следующем виде:

£<2,Г) = <2(г)'(г)1г„=а>г +г{т,0 +т„ +тг2))+агд^г).

кттт-тп т1р =(г-1)^; + рГ)+2(ц/г + + р)

о;

(р-1)2' -^Г'+С1 + ргЧ)-^'+^ + р2)

Продолжительность простоя из-за отсутствия заявок в системе, можно найти в виде:

(12)

Далее в главе 3, представлены результаты численного анализа вероятностных характеристик для разработанных моделей функционирования сервера присутствия Среднее время прогулки /(1'= 1/9 мс, было получено исходя из соображений, что оно равно среднему времени обслуживания группы сообщений. На рис. 4 показана зависимость среднего времени ожидания обслуживания от поступающей на СМО нагрузки,

р, эрл.

Рис. 4. Среднее время ожидания заявок в очереди.

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

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

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

3. В виде СМО MIX,IGI1 с прогулками прибора и виде СМО М|х|/ М /l/R < WBS с

(м) (p,q)

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

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

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

1. Нсангу Мушили Мама, Плаксина О.Н. Анализ характеристик процедуры установления SIP-соединения поверх протокола ТСР. Тезисы докладов секции математики и информатики XLIV Всероссийской Конференции по проблемам МИФиХ, РУДН, 2008. - С. 91.

2. Нсангу Мушили Мама, Сопин Э. С. Анализ трафика и моделирование производительности сервера присутствия подсистемы IMS. Тезисы докладов секции математики и информатики XLIV Всероссийской Конференции по проблемам МИФиХ, РУДН, 2009. - С. 188-189.

3. Нсангу Мушили Мама. Марковская модель установления соединения по протоколу SIP с учётом повторных передач. Труды секции телетрафика LXIV конференции РНТОРЭС имени А. С. Попова, МТУСИ, 2009. - С. 367-369.

4. Нсангу Мушили Мама, Самуилов К.Е., Серебренникова Н.В. Модель установления соединения сессии по протоколу SIP с учётом повторных передач. Вестник Российского университета дружбы народов. Серия «Математика, информатика и Физика». 2009. - № 1. - С. 59-66.

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

6. Нсангу Мушили Мама, Самуилов К.Е., Чукарин А.В. Построение и анализ Марковской модели установления соединения по протоколу SIP с учетом повторных передач. T. comm. Телекоммуникации и транспорт, 2010. - №7. - С. 139-141.

7. Нсангу Мушили Мама. Управление прогулкой очереди М/М/1 сервера присутствия с возможным прерыванием. Тезисы докладов секции математики и информатики XLVI Всероссийской Конференции по проблемам МИФиХ, РУДН, 2010. -С. 82.

8. Нсангу Мушили Мама, Самуилов К.Е. Анализ модели сервера присутствия в сети NGN. Research and Development company «Information and Networking Technologies» (Russia). International Conférence DCCN. Theory and Application. Moscow, 2010. - P. 124-129.

9. Нсапгу Мушши Мама. Модель 51Р-сервера в виде системы с прогулками и разогревом прибора. Тезисы докладов Конференции с международным участием ИТТММ, РУДН, 2011.-С. 106-108.

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

В диссертации решается задача разработки и анализа вероятностных моделей установления сессии пользователей в сетях последующих поколений по протоколу установления сессий (SIP, Session Initiation Protocol), а также моделей для анализа показателей эффективности обработки сообщений оповещения на сервере присутствия.

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

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

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

Nsangou Mouchili Mama (Cameroon)

Development of models for the analysis of session initiation efficiency parameters in a multiservice network

The goal of this thesis deals with the development and analysis of SIP (session initiation Protocol) session establishment models in multiservice networks, as well as analysis methods of users status transmission control through the presence servers. In terms of Markov chain, the call establishment mathematical model is developed, probabilistic characteristics are analyzed and both SIP messages retransmission and processing delays calculation's method is proposed. We provided the numerical analysis using the real values.

For the presence server performance analysis, fairly general assumptions, a batch inflows model is built taking into account the multiservice delivery due to the diversity of requirements; the probability generating function and the average number of costumers in the system are found.

Managing the notify messages queue, we built an exponential queuing system in terms of single-linear model with ordinary and working vacations for either batch or singular incoming flows. The sojourn time was found as well as the system probabilistic characteristics. For the model with limited capacity, the losing probability is found.

Using the values closer to reality, like some proposed by British Telecom, the adequacy of results has been assessed.

Подписано в печать 21.01.2012г. Заказ № 07537 Тираж: 120экз. Копицентр «ЧЕРТЕЖ.ру» ИНН 7701723201 107023, Москва, ул.Б.Семеновская 11, стр.12 (495) 542-7389 www.chertez.ru

61 12-1/456

РОССИЙСКИЙ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ

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

Нсангу Мушили Мама

РАЗРАБОТКА ВЕРОЯТНОСТНЫХ МОДЕЛЕЙ ДЛЯ АНАЛИЗА ПОКАЗАТЕЛЕЙ ЭФФЕКТИВНОСТИ УСТАНОВЛЕНИЯ СЕССИЙ В МУЛЬТИСЕРВИСНОЙ

СЕТИ

Специальность 05.13.17 - теоретические основы информатики

Диссертация

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

Научный руководитель доктор технических наук, профессор Самуйлов Константин Евгеньевич

Москва-2012

ОГЛАВЛЕНИЕ

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

Глава 1. Сервер мультисервисной сети как система с групповым поступлением сообщений

1.1. Базовая модель установления соединения в мультисервисной сети

1.2. Сервер присутствия как система массового обслуживания

1.3. Анализ простейшей модели сервера присутствия с групповым поступлением

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

ГЛАВА 2. Построение и анализ математической модели установления соединения с учетом повторных передач

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

2.2. Марковская модель установления соединения

2.3. Пример численного анализа

Глава 3. Анализ показателей эффективности сервера присутствия в мультисервисной сети

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

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

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

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

Заключение Библиоерафия

5 13

13

19

25

33 36

37

40 48 51

53

58

71

88

95 97

СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ

Л - интенсивность потока пачек заявок

К - объем накопителя заявок,

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

N - среднее число заявок в СМО

м - среднее время ожидания в очереди

- интенсивность обслуживания при полной занятости прибора

- вероятность того, что группа состоит из I заявок

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

заявок

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

обслуживания заявки

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

F(л:) - ФР длительности прогулки прибора

/{к} - к-й начальный момент длительности прогулки

прибора

Ж) ~ производящая функция (ПФ) распределения I

\1'. - вероятность того, что в к группах содержится I заявок

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

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

Ж) - ПЛС ФР F(x).

Х(1), г > 0 - СП числа заявок в очереди в момент времени г

qj, 7 > 0 - финальное распределение вероятностей состояний вложенной цепи Маркова

б(^) - ПФ распределения

1^(5), 5 > 0 - ПЛС ФР времени ожидания заявок в очереди

/?., _/ > 0 - распределение числа заявок, поступивших за

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

В(х), х > 0 - ФР времени обслуживания группы заявок

Д*), 5 > 0 - ПЛС ФР В(х)

7 - интенсивность обслуживания при разогреве прибора

- вероятность нахождения i заявок в системе, когда прибор находится в состоянии ]

- вероятность нахождения сервера в состоянии ] {?■) ~ ПФ распределения [ж*}

я (г) _ ПФ распределения {л-^]

Е^ - средняя длительность цикла занятости прибора

Е } - средняя длительность периода простоя прибора

2? И- - средняя длительность периода полной занятости

прибора

(7{г) - дисперсия длины очереди

ВВЕДЕНИЕ

Основная технологическая идея сетей последующих поколений (NGN - Next Generation Networks) иллюстрирована разделением транспортных процессов и процессов управления вызовами и сеансами на базе элементов платформы Softswitch. Основной подсистемой, поддерживающей реализацию NGN такого масштаба, является IP мультимедийная подсистема (IMS - IP MultiMedia Subsystem). По существу, концепция IMS возникла в результате эволюции европейского стандарта NGN - системы подвижной связи UMTS (Universal Mobile Telecommunication System), когда функциональность управления мультимедийными вызовами и сеансами на базе протокола установления сессий (SIP - Session Initiation Protocol) добавили к архитектуре сетей 3-го поколения (сети 3G). Среди основных свойств архитектуры IMS можно выделить:

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

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

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

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

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

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

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

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

Услуга присутствия также очень полезна для абонентов, которые теперь всегда знают, доступен ли абонент или нет, желает ли он с кем-либо общаться и.т.д. Услуга является основной для многих популярных приложений таких, как мгновенная передача сообщений (IM - Instant Messaging) и РТТ (Push-To-Talk), которые существенно облегчают коммуникации среди различных сообществ пользователей. Для реализации этой услуги был выбран получавший в то время все большее распространение протокол инициирования сеансов связи или, короче, протокол установления сессий SIP, требовавший, в то же время, расширения функциональности.

Вследствие высокой популярности услуги присутствия большие нагрузки испытывает сервер присутствия, являющийся ключевым элементом инфраструктуры предоставления данной услуги. Поэтому, возникает задача анализа производительности сервера присутствия и параметров эффективности его функционирования. Кроме того, анализ показателей предоставления услуг на базе протокола SIP, необходим для эффективности обеспечения выполнения соглашений об уровне обслуживания (SLA - Service Level Agreement), а также удовлетворения требованиям, установленным международными стандартами.

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

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

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

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

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

3. Для модели сервера присутствия в виде системы массового

обслуживания (СМО) М|Х' I М 111 °о | BS с отключением и с разогревом

(ц.г) (p.q)

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

широкого класса реальных систем, что позволит поставщику телекоммуникационных услуг достичь приемлемого качества предоставления услуги присутствия. Результаты работы использованы в рамках исследований по гранту РФФИ № 10-07-00487-а «Задача управления доступом в широкополосной сети и анализ марковской модели с мультипликативным распределением вероятностей состояний» и в НИР 020612-1-173 «Разработка математических моделей и анализ информационно-телекоммуникационных сетей».

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

Диссертация, состоящая из введения, трех глав, заключения и библиографии из 83 наименований, имеет следующую структуру. На основе аналитического обзора источников указанных в библиографии, глава 1 посвящена исследованию процессов обмена сигнальными сообщениями протокола SIP при установлении соединения и уведомлении пользователей в сетях NGN и применению к их анализу систем с групповым поступлением заявок. В разделе 1.1 исследованы особенности, в части ВВХ проанализирована процедура установления Уо1Р-соединения (англ. Voice over IP, передача речи по сети протокола IP). Выведена формула для вычисления среднего времени установления Уо1Р-соединения с учетом временных задержек ожидания и обработки заявок в узлах сети. Для этого определены задержки на каждом участке системы в зависимости от функций управления сеансами связи. Принимая

во внимание особенности транспортного протокола, учтена задержка передачи сигнальных сообщений из-за их повторных передач. В разделе 1.2, для исследуемых типов серверов в сетях последующих поколений, проведен аналитический обзор известных результатов для различных моделей систем массового обслуживания (СМО), в том числе, приведены некоторые результаты для ПФ числа заявок в системе и характеристик времени простоя обслуживающего прибора. С практической точки зрения исследованы несколько различных математических моделей, описывающих выход прибора из строя и восстановление его работы, а также дисциплины обслуживания заявок, которые при поступлении застают прибор в нерабочем состоянии. Такие системы были исследованы Б. В. Гнеденко и И.Н. Коваленко; а в книге П. П. Бочарова и А. В. Печинкина, предложен метод матрично-мультипликативного решения, где СВ длительности обслуживания задаются распределениями фазового типа (т.н., РН-распределениями). Ряд других авторов исследовали модификации систем такого рода, из них, особо выделяются работы С. Ши с соавторами, а также работа X. Занг и Д. Ши, результаты которых легли в основу постановки задачи исследований в третьей главе диссертационной работы. Раздел 1.3 посвящен анализу простейшей СМО

типа MWIMI1IR < оо в которой для случая с надежным прибором и бесконечной емкостью накопителя (R = ), поступление заявок производится группами фиксированной длины К, а для случая системы с прогулками прибора, исследуется процесс уведомления пользователей сообщениями NOTIFY с ординарным входящим потоком и с ограниченной емкостью накопителя (R<oo). Найдены стационарное распределения числа заявок в СМО, а также другие важные вероятностно-временные характеристики системы.

Глава 2 посвящена разработке математической модели для анализа показателей качества функционирования протокола SIP в процессе установления соединения, с учетом повторных передач. Раздел 2.1 [11, 16, 35, 72] формулирует требования к функциональной модели,

разработанной на основе принципов работы протокола SIP [36, 38, 11, 31, 47], учитывая механизм обеспечения передачи для случая, когда сообщения могут быть потеряны или искажены. Также описан процесс резервирования ресурсов и уточнена роль каждого задействованного в установлении соединения протокола, в разделе 2.2, построена математическая модель в виде цепи Маркова (ЦМ) для анализа вероятностных характеристик. В соответствии с этой моделью, проанализирована ЦМ и получены условные вероятности перехода по цепи при заданном числе шагов. Выведена формула для вероятности успешного установления и вероятности прерывания соединения по протоколу установления сессий; используя общие подходы к вычислению задержки повторных передач голосовых пакетов, получен общий вид суммарной задержки установления соединения. В разделе 2.3, численный анализ вероятности прерывания вызова и общей задержки позволяет проверить адекватность предложенных формул согласно данным из источников [47, 45, 38, 37].

Глава 3 посвящена анализу ВВХ процесса передачи информации по протоколу SIP в сетях следующего поколения и моделей функционирования сервера присутствия. Описана общая концепция предоставления данной услуги и в терминах теории массового обслуживания (ТМО) поставлена задача анализа производительности сервера присутствия с учетом особенностей его функционирования. [42, 80]. В разделе 3.1 проводится анализ модели сервера присутствия как системы с групповым поступлением заявок и прогулками обслуживающего прибора. Учитывая, что сервер выполняет и другие работы по обслуживания очередей, исследована значительно обобщенная модель, в виде системы массового обслуживания типа М^ IG111 с групповым поступлением заявок и прогулками прибора на периодах простоя. С помощью метода вложенной ЦМ, определено рекуррентное соотношение между стационарными вероятностями, и с помощью метода

ПФ, получены формулы для расчета среднего числа заявок в системе и в очереди соответственно.

В разделе 3.2, с учетом группового поступления заявок решена задача расчета задержек обслуживания сообщений NOTIFY в виде системы массового обслуживания типа М[Х]/ М /l/°°/BS с прогулками прибора на

(м) (p,q