О стационарном распределении вероятностей состояний модели мультисервисной сети с тройной услугой

УДК 621.39

О стационарном распределении вероятностей состояний модели мультисервисной сети с тройной услугой

И. А. Гудкова

Кафедра систем телекоммуникаций Российский университет дружбы народов ул. Миклухо-Маклая, д. 6, Москва, 117198, Россия

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

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

1. Введение

В настоящее время происходит процесс конвергенции сетей, а инфокоммуни-кационные компании разрабатывают новые стратегии для успешного предоставления новых услуг в сетях следующих поколений. Процесс такой конвергенции связан с коммерческой концепцией «тройная услуга» («triple play») [1], подразумевающей предоставление в одной сети одним провайдером услуг, которые можно разделить на три крупные категории — «голос», «видео» и «данные». Каждая категория фактически является пакетной услугой: «голос» — IP-телефония, Skype, SIP-телефония; «видео» — IPTV, видео по запросу, потоковое видео поверх одноранговых сетей P2P; «данные» — передача файлов, электронная почта, обмен мгновенными сообщениями.

Трафик, генерируемый столь разнообразными услугами, пользующимися различной степени популярностью, различается не только по объёму, но и чувствительностью к потерям пакетов, побитовой скоростью, временем передачи и пр. Потоковый трафик — это трафик реального времени с фиксированным временем передачи, тогда как для эластичного трафика важна передача блоков данных заданного объёма, причём время передачи может варьироваться в зависимости от загрузки сети. В табл. 1 показаны типы трафика, основные режимы передачи и примеры соответствующих услуг. Используя табл. 1, можно говорить о трёх типах трафика — «одноадресный потоковый трафик», «многоадресный потоковый трафик» и «эластичный трафик», причём эластичный трафик может использовать оба режима передачи, но в статье рассматривается только одноадресный режим.

С точки зрения анализа математических моделей, теория телетрафика развивается последовательно, шаг за шагом. Изначально специалисты предлагали модели только с одним типом трафика, например, как в [2-4]. Отметим, что модели только с эластичным трафиком описываются в терминах систем массового обслуживания (СМО) с дисциплиной разделения процессора (Processor Sharing, PS), а в обзоре С.Ф. Яшкова [5] даётся подробный анализ большинства из этих

Статья поступила в редакцию 27 июля 2011 г.

Работа выполнена при поддержке РФФИ (грант 10-07-00487-а).

Автор выражает благодарность д.т.н., профессору, заведующему кафедрой систем телекоммуникаций РУДН К.Е. Самуйлову за постановку задачи, полезные советы в процессе исследований и неоценимую помощь при подготовке статьи.

СМО. Позднее проводился анализ попарных комбинаций трафика — одноадресного и многоадресного [2,6,7], одноадресного и эластичного [8-10]. Для моделей с однородным трафиком были найдены аналитические решения и разработаны рекуррентные алгоритмы, чего нельзя сказать о моделях совместного обслуживания одноадресного и эластичного трафика, для которых пока известны лишь приближенные методы. Модель, учитывающая все три типа трафика, впервые была построена в [11], но точные алгоритмы там также предложены не были. В данной статье разработаны как приближенный метод (раздел 3), так и точный алгоритм (раздел 4) для анализа и расчёта модели звена сети с тремя типами трафика.

Таблица 1

Типы трафика и режимы передачи «тройной услуги»

Трафик Одноадресный режим «точка - точка» Многоадресный режим «точка - много точек»

Потоковый Видео по требованию, IP-телефония, голосовая почта, онлайн прослушивание аудио-файлов, индивидуальные и групповые игры, обмен информацией бизнес-приложений с хранилищем данных Вещательное телевидение IPTV, вещательное телевидение высокого качества HDTV, телевидение с оплатой за просмотр (pay per view), видеоконференции, широковещательное и потоковое радио

Эластичный Поиск каналов IPTV, предварительная загрузка аудиофайлов для МР3-плееров, факс-приложения, оповещения службы мониторинга, передача гипертекста в формате HTML, обмен сообщениями SMS Групповые игры с предоплатой лимита времени, приложения электронной коммерции, удалённое управление и мониторинг в домашней сети, обмен мгновенными сообщениями, рассылка электронной почты

2. Построение модели для отдельного звена сети с

тройной услугой

Аналогично мультисервисным моделям, построенным в [2-4, 6, 7], рассматривается звено сети c С условными единицами канального ресурса (ЕКР), например, ЕКР = 1 бит/с. Также как и в [11], по звену передаётся одноадресный (u := unicast), многоадресный (m := multicast) и эластичный (e := elastic) трафик. Нагрузочные параметры модели определены в табл. 2. Предполагается, что входящие потоки являются пуассоновскими с интенсивностями А&, а длительности обслуживания распределены по экспоненциальному закону со средними ft-1, причём запросы каждого типа трафика требуют bk ЕКР, к £ {u, m, e}. В случае одноадресного и многоадресного трафика число выделяемых для каждого соединения ЕКР не меняется, тогда как блоки эластичных данных всегда занимают всю оставшуюся ёмкость звена. В исследуемой нами модели каждый блок требует как минимум be ЕКР, в противном случае запрос на передачу блока данных будет потерян. Основное отличие между тремя типами трафика заключается в дисциплине их обслуживания. Запросы на установление одноадресных соединений обрабатываются по дисциплине FCFS (First Come — First Served). Запросы на

установление многоадресного соединения обслуживаются по принципу «прозрачных заявок» [7], т.е. bm ЕКР занимаются единожды при установлении соединения на все его время, пока хотя бы один запрос продолжает обслуживаться. Наконец, блоки эластичных данных разделяют все свободные ЕКР звена с дисциплиной EPS (Egalitarian PS) [5].

Таблица 2

Нагрузочные параметры модели

Параметр

Тип трафика

Описание

Afc

к = u к = m к = e

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

^fc1

к = u к = m к = e

Среднее время занятия одноадресного соединения [с]

Среднее время занятия многоадресного соединения [с]

Средняя длина блока эластичных данных [бит]

Рк := Afc

1

к = u к = m к = e

Предложенная нагрузка одноадресного трафика [Эрланг]

Предложенная нагрузка многоадресного трафика [Эрланг]

Предложенная нагрузка эластичного трафика [ЕКР]

Ьк

к = u к = m к = e

Требование к ЕКР одноадресного соединения Требование к ЕКР многоадресного соединения Требование к ЕКР блока эластичных данных

Пк

к = u

к = m

к = e

Число установленных одноадресных

С

соединений nu Е { 0,

Состояние многоадресного соединения: пт = 1 обслуживание запроса(ов), пт = 0 в противном случае Число передаваемых блоков эластичных С

данных ne Е \ 0

Ье

u _

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

^ := <

^ &б{и, т, е} ^

Функционирование рассматриваемой системы описывает марковский процесс над пространством состояний X, и, учитывая [11], можно получить систему уравнений равновесия (СУР) в виде

Р (Пи,Пш,Пе) I ^ ^ ^ 1 {(«и,Пш,Пв)£ Б&} +

\fceju, е}

+ Аш • 1 {(Пи,Пш,Пе) </ Бш л Пт = 0} + Пи^и + Аш (еРт - 1)-1 • 1 {Пш = 1} + + С (Пи, Пш) ^е • 1 {«е > 0} = р («и - 1, Пш, Пе) • Аи • 1 {«и > 0} +

+ р (Пи, 0, Пе) • Аш • 1 {«ш = 1} + Р (Пи, Пш, «е - 1) • Ае • 1 {«е > 0} + + р (Пи + 1,Пш,Пе) • (Пи + 1) ^и • 1 {(Пи,Пш,Пе) / Би} +

+ р (Пи, 1,Пе) • Аш (еРт - 1) 1 • 1 {(Пи,Пш,Пе)</ Бш Л Пш = 0} +

+ Р

Здесь величина с (пи,пш) := С - пиЬи - пшЬш является числом ЕКР, не занятых потоковым трафиком и Б&, к £ {и, т, е} множества блокировок, определяемые формулами:

Бк (ии,Пш,Пе) : Ь^ + Ък >с\, к £ {и, е} ,

^ ш, е}

ш

(^и,Пш,Пе) : пзЬз + >С Л Пш = 0 I.

ш, е} ^

Заметим, что в отличие от классических моделей [2], решение СУР (2) не является мультипликативным, что связано с зависимостью интенсивности •с (пи, пш) передачи блоков эластичных данных от состояния системы. Следовательно требуется разработка приближенных и точных методов расчёта стационарного распределения вероятностей состояний модели, что и сделано в следующих двух разделах статьи.

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

Введём Р {пе = ге | пи,пш} условную вероятность того, что в некоторый момент времени по звену сети передаются ге блоков эластичных данных при условии,

что установлено пи £ |0,..., | одноадресных и пш £ {0, 1} многоадресных

соединений. Обозначим Рш (пи) вероятность того, что многоадресное соединение может быть установлено при условии, что установлено пи одноадресных соединений, и пусть Ри (пи, пш) — вероятность того, что одноадресное соединение может быть установлено при условии, что установлено пи одноадресных и пш £ {0, 1} многоадресных соединений. Сформулированные ниже без доказательства леммы определяют формулы для распределения вероятностей р (пи,пш,пе) состояний модели с тремя типами трафика.

Лемма 1. Условное распределение числа блоков эластичных данных вычисляется по формуле

Р {«е = «е | Пи,«ш} =

(-*— У

ус (Пи, Пш) /

¿е = 0,...,

С

с

I ,пт) I С

С (Пи,Пш^^ - ,1 ^^ '

Ье

, Пи = 0, . . .

С - ПшЬ„

, Пш = 0, 1.

е

Ь

и

Лемма 2. Маргинальное распределение состояний одноадресных и многоадресного соединений вычисляется приближённо по формуле

- £ ]

Р {Пи = Ъи, Пт = Ът} : = Е Р

¿е=0

С

-1

(Ут - 1Гт ртт ы) (

¿„ — 1

ртт (ги)) ^ п ри (ш

3=0

ги = 0,...

С — ЪтЬп

гт = о, 1,

Ь

и

где

I-£J ¡„ «и-1

I. \

° := £ тгП ри и, о)+ £

«и!

¿„=0 j=0

¿„=0

($ П р. <,ч),

I] I С(п„,1) I

Р Ы ) := V Р {п = i \ п 0\= С

гт (^и) := Р = ¿е 1 п., 0} = : , С(„„,1) | +

¿е=0

[ « ]+1 -р[ ^ +1

с

I °("„,0) I

с

I с(п„,0) |+1 I °(",„,0) 1+1

с(пП'0^+1 -ре Ье ]+

п. = 0,...

X

X

и

I с(гс„ + 1,Пт) I - Ье J

Ри (Пи,Пт):= £ Р {Пе = ^ I Пи,Пт} =

¿е = 0

I с(^„ + 1,Пт) I I с(п„ ,пт) I

с

Пи = 0,...

С - птЪт

, Пт = 0, 1.

и

Теперь стационарное распределение состояний модели звена сети с тройной услугой может быть вычислено по формуле:

Р (^u, Ъе) Р ^е 1 ^и ^и, ^т ^т} • Р {^и ^и, ^т ^т} ,

Заметим, что приближенное решение СУР (2) может быть найдено несколькими способами (см., например, [8-10]), но проведённые автором данной статьи численные исследования показали, что только распределение, вычисленное по формулам (3)-(8), подходит для расчёта основной характеристики модели — среднего времени передачи блока эластичных данных, при этом относительная погрешность вычислений составляет менее 1%.

4. Точный алгоритм для снижения размерности решаемой задачи

В данном разделе получен точный алгоритм для расчёта ненормированных вероятностей д (пи, пш, пе) состояний модели звена сети с тремя типами трафика. Алгоритм, сформулированный в лемме 3, выписан в предположениях 6е < 6и и &е < &ш, которые основаны на реальных исходных данных для сетей с тройной услугой (см. книгу [1]).

Лемма 3. Ненормированные вероятности состояний модели звена сети с тройной услугой вычисляются по формулам

д (0, 0, 0) = 1,

(Пи, 0, 0) = ХПц,о, Пи = 1,... д («и, 1, 0) = ХПц,1, Пи = 0,...

С_

ьии

С - Ьш

и

I £ \

<? (Пи, Пш, Пе) = «00 (Пи, Пш, Пе) + ^ («и, Пш, Пе) • +

¿=1

I. \

+ X]

¿=0

В формуле (12) коэффициенты ац (пи,пш,пе) вычисляются по рекуррентным соотношениям:

{ощ (Пи,Пш,Пе) , Пе > 0, |Ии - Ъ - 3 | < Пе, 1, Пе = 0, г = Пи, 3 = Пш,

0, в противном случае,

(Пи,Пш,Пе) {

1

- с

+ Аш • и Пш = 0 Л 1

(Ли^

С - ПшЬш - (Пе - 1) Ье

> пЛ +

С - Пи Ьи - (Пе - 1) Ье

> 0^ = и+ Ае +

+ Пи^и + Аш (еРт - 1) 1 -1 {Пш = 1} + С (Пи, Пш) ^е -1 {^ > 2} j -О^ (Пи, Пш, Пе - 1) -- Аи • 1 {Пи > 0} • а^ (Пи - 1, Пш, Пе - 1) - Аш • 1 {Пш = 1} • ац (Пи, 0, Пе - 1) -

- Ае • 1 {Ие > 2} • ац (Пи, Пш, Пе - 2) - (Пи + 1) ^и X

1

С - ПшЬш - (Пе - 1) Ье

> пЛ • О^ (Пи + 1, Пш, Пе - 1) - Аш (еРт - 1) 1 X

хч Пш = 0 Л 1

С - ПиЬи - (Пе - 1) Ье

>} = 1}

> 0^ = П • агу

В формулах (10)-(12) величины Хц являются решением системы линейных уравнений:

и

ш

и

ш

Ш L J

ft 00 (Пи ,Пт) + Z fti0 (Пи, Пт) ' ХЮ + ^ (Пи, Пт) ' ^¿1 = 0,

¿=1

¿=0

Пи = 1, . . .

Л пт = 0, пи = 0,...,

С- bm

Л Пт = 1,

ftij (Пи,Пт) = ( Пи^и + Ат (ePm - 1) 1  1 {Пт = 1} + С (Пи,Пщ) Ре X

1

с( Пи,Пт ) Ье

X ац Пи - 1,ПГ

> 0

с

с(Пи, Пт) Ье

- Лт  1 («т = 1}  «ij «и, 0

- Ли  1 (Пи > 0} X

с

-Ае -1

С(Пи, Пт) Ье

> 0 ^  aij Пи,Пт,

с(Пи, Пт) Ье

- 1 .

После нормировки величин д (п.,пт,пе) получаем искомое стационарное распределение р (пи ,пт,пе) вероятностей состояний модели.

Следствие 5. Алгоритм леммы 3 снижает размерность задачи (2) со значе-

ния

1*1 =

L £ J

Z

пц=0

С - ПиЪи

+

до значения

+

С- Ьт

L J

z

nu=0

+ 1.

С - ПиЬи - bm

С С - Ьт

+ А. + Ьи _

+ 2

Например, для близких к реальным исходных данных из [1] размерность исходной системы составляет порядка 107, а число уравнений в получаемой после применения алгоритма СУР — всего около 102. Заметим, что для частного случая модели звена сети с тройной услугой — модели с многоадресным и эластичным трафиком — система линейных уравнений (13)-(14) вырождается в одно уравнение, решение которого, следовательно, получается в явном виде.

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

Таким образом, в статье построена модель звена мультисервисной сети с тройной услугой — тремя дисциплинами обслуживания одноадресного, многоадресного и эластичного трафика. Предложены два метода расчёта стационарного распределения вероятностей состояний модели. Первый метод (раздел 3) основан на приближенном вычислении маргинального распределения числа одноадресных и многоадресных соединений. Метод, предложенный в разделе 4 статьи, позволяет значительно снизить размерность задачи и представить её решение в виде линейной неоднородной комбинации вероятностей с рекуррентно рассчитываемыми коэффициентами.

и

и

е

е

е

и

и

Литература

1. Hens F. J., Caballero J. M. Triple Play: Building the Converged Network for IP, VoIP and IPTV. — Johns Wiley & Sons Ltd., 2008. — P. 416.

2. Новый этап развития математической теории телетрафика / Г. П. Башарин, К. Е. Самуйлов, Н. В. Яркина, И. А. Гудкова. — Москва: Академиздатцентр

«Наука» РАН, 2009. — С. 16-28. [Novihyj ehtap razvitiya matematicheskoyj teorii teletrafika / G. P. Basharin, K. E. Samuyjlov, N. V. Yarkina, I. A. Gudkova. — Moskva: Akademizdatcentr «Nauka» RAN, 2009. — S. 16-28. ]

3. Gaidamaka Y, Samouylov K. Analytical Model of Multicast Network and Single Link Performance Analysis // Proc. of the 6-th International Conference on Telecommunications ConTEL-2001. — Zagreb, Croatia: 2001. — Pp. 169-175.

4. Samouylov K. E., Gudkova I. A. Recursive Computation for a Multi-Rate Model with Elastic Traffic and Minimum Rate Guarantees // Proc. of the International Congress on Ultra Modern Telecommunications and Control Systems ICUMT-2010. — Moscow, Russia: 2010. — Pp. 1065-1072.

5. Яшков С. Ф. Математические вопросы теории систем обслуживания с разделением процессора. — Москва: ВИНИТИ, 1990. — Т. 29. — С. 382. [Yashkov S. F. Matematicheskie voprosih teorii sistem obsluzhivaniya s razdeleniem processora. — Moskva: VINITI, 1990. — T. 29. — S. 3-82. ]

6. Samouylov K., Yarkina N. Blocking Probabilities in Multiservice Networks with Unicast and Multicast Connections // Proc. of the 7-th International Conference on Telecommunications ConTEL-2005. — Zagreb, Croatia: 2005. — Pp. 423-429.

7. Gudkova I. A., Plaksina O. N. Performance Measures Computation for a Single Link Loss Network with Unicast and Multicast Traffics / Ed. by S. Balandin, R. Dunaytsev, Y. Koucheryavy. — Germany, Heidelberg: Springer-Verlag, 2010. — Vol. 6294. — Pp. 256-265.

8. Bonald T., Proutière A. On Performance Bounds for the Integration of Elastic and Adaptive Streaming Flows // Proc. of the Joint International Conference on Measurement and Modeling of Computer Systems Sigmetrics-Performance-2004. — Vol. 32, No 1. — New York, USA: 2004. — Pp. 235-245.

9. Admission Control for Differentiated Services in Future Generation CDMA Networks / H.-P. Tan, R. Nunez Queija, A. F. Gabor, O. J. Boxma. — Elsevier Science, 2009. — Vol. 66, No 9-10. — Pp. 488-504.

10. Karray M. K. Analytical Evaluation of QoS in the Downlink of OFDMA Wireless Cellular Networks Serving Streaming and Elastic Traffic. — 2010. — Vol. 9, No 5. — Pp. 1799-1807.

11. Gudkova I. A., Samouylov K. E. Approximating Performance Measures of a Triple Play Loss Network Model / Ed. by S. Balandin, R. Dunaytsev, Y. Koucheryavy. — Germany, Heidelberg: Springer-Verlag, 2011. — Vol. 6869. — Pp. 360-369.

UDC 621.39

On the Stationary Probability Distribution for a Multi-Service Model of the Triple Play Network

I. A. Gudkova

Telecommunication Systems Department Peoples' Friendship University of Russia Miklukho-Maklaya str., 6, Moscow, 117198, Russia

Modern multi-service networks are inseparably linked with the commercial concept "triple play" that implies simultaneous provisioning of telephony, television and data transmission over a single broadband connection. These services generate traffics of three types — unicast streaming, multicast streaming and elastic traffics. In this paper, we propose a multi-service model of a triple play single-link network; we obtained an approximate formula for the stationary probability for the model; and finally, we find an exact algorithm for calculating performance measures by reducing the dimension of the problem.

Key words and phrases: triple play, single-link, streaming traffic, unicast traffic, multicast traffic, elastic traffic, stationary probability distribution, approximation, exact algorithm.