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

Компьютерные и информационные науки

УДК 621.39

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

мультивещания

И. А. Гудкова, Е. В. Маркова

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

Сети мобильной связи четвёртого поколения на базе технологии LTE (Long Term Evolution) в настоящее время стали одним из важнейших направлений в модернизации телекоммуникационных систем. Согласно международным стандартам в сетях LTE выделяют девять типов услуг, каждый из которых, в первую очередь, характеризуется гарантированной или негарантированной скоростью передачи данных и приоритетом в обслуживании. В зависимости от значения скорости передачи данных устанавливается соответствие между услугой и типом генерируемого ей трафика — потоковым одноадресным, потоковым многоадресным или эластичным. В зависимости от значения приоритета в обслуживании для услуги могут быть реализованы различные сценарии доступа к ресурсам сети, основанные, как правило, на следующих механизмах: снижение скорости передачи информации, прерывание обслуживания, резервирование, пороговое и вероятностное управление. В статье построена модель схемы доступа к ресурсам соты сети LTE с прерыванием передачи менее приоритетного потокового одноадресного трафика и двумя дисциплинами обслуживания более приоритетного потокового многоадресного трафика. Получен алгоритм для расчёта стационарного распределения вероятностей состояний модели, предложены формулы расчёта основных характеристик модели — вероятностей блокировки и прерывания обслуживания запросов на передачу одноадресного трафика.

Ключевые слова: LTE, управление доступом, одноадресный трафик, многоадресный трафик, прерывание, рекуррентный алгоритм.

1. Введение

Развитие современных инфокоммуникационных сетей и систем направлено на переход к мобильным сетям связи четвёртого поколения (4G, 4th generation), а именно сетям на базе технологии LTE (Long Term Evolution) [1], которая позволяет повысить скорость, эффективность передачи данных, снизить затраты операторов, расширить спектр и улучшить качество предоставляемых мультимедийных услуг. В зависимости от скорости передачи данных в сетях LTE выделяют два типа услуг (стандарт TS 23.203 консорциума 3rd Generation Partnership Project) — услуги, предоставляемые пользователям с гарантированной скоростью передачи данных (Guaranteed Bit Rate, GBR), и услуги, предоставляемые не с гарантированной, а с переменной скоростью передачи (non-GBR). Трафик, генерируемый услугами реального времени с гарантированной скоростью, принято называть потоковым [2], а услугами без гарантированной скорости — эластичным [3].

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

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

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 13-07-00953.

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

Отметим, что далее в статье рассматривается только вторая группа механизмов, а именно механизм прерывания обслуживания пользователей. В зависимости от комбинаций различных по приоритету услуг возможны более 200 схем доступа [4-6,8,9], учитывающих все возможные попарные влияния услуг друг на друга. В связи с этим возникает задача исследования эффективности схем доступа в мультисервисных сетях с учётом алгоритмов приоритетного обслуживания различных типов трафика — потокового одноадресного и многоадресного, эластичного.

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

2. Построение математической модели схемы доступа

Рассмотрим соту сети LTE с пиковой пропускной способностью С (например, Мбит/с). Пользователям соты предоставляются три услуги, две из которых генерируют многоадресный трафик, например, игры в режиме реального времени с приоритетом 3 и видеоконференция с приоритетом 4, а одна — одноадресный, например, видео по запросу с приоритетом 5 (3GPP TS 23.203, более приоритетная услуга имеет меньшее значение приоритета). Для многоадресного трафика рассматриваются две дисциплины обслуживания: П1, при которой сессия муль-тивещания завершается с окончанием обслуживания первого пользователя, инициировавшего эту сессию, и дисциплина П2, при которой сессия мультивещания завершается с окончанием обслуживания последнего получающего услугу пользователя. Все услуги предоставляются пользователям с гарантированной скоростью (GBR). Далее для упрощения изложения будем описывать услуги в терминах многоадресных и одноадресных соединений соответственно, а также использовать термин «единица канального ресурса» (ЕКР), например, ЕКР = 1 Мбит/с.

Предполагается, что входящие потоки являются пуассоновскими с интенсив-ностями V, Л, Л, а времена занятия соединения одним запросом распределены по экспоненциальному закону со средними к-1, /л-1, M-1, тогда интенсивность предложенной нагрузки, создаваемой одноадресным и многоадресным трафиком с дисциплинами П1 и П2, определяется соответственно как а = v/к, р = Х/р и R = Л/М . Для установления одноадресного соединения требуется d ЕКР, многоадресного соединения с дисциплиной обслуживания П1 - b i ЕКР, с дисциплиной П2 - Ь2 ЕКР, Ь2 > Ь1. Без ограничения общности будем считать d = 1. Обозначим число установленных одноадресных соединений п, m — состояние многоадресного соединения с дисциплиной обслуживания П1, I - с дисциплиной П2, где m = 1

или I = 1 обозначает обслуживание П1 или П2 запроса(ов), а т = 0 или I = 0 -противный случай.

С учётом выше изложенного пространство состояний модели имеет вид

X = {

Управление доступом к ресурсам сети основано на реализации механизма прерывания передачи одноадресного трафика. При этом запросы на установление многоадресного соединения П1 или П2 никогда не будут заблокированы. Если ресурсов недостаточно, то будут прерваны одноадресные соединения в количестве, необходимом для установления многоадресного соединения. Таким образом, функции доступа для каждого типа трафика имеют вид:

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

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

f 1, С - bim - b2l - dn > d,

3. } (l,m,n) = < 0 с - bim - b2l - dn < d — функция доступа для запроса

на установление одноадресного соединения, а число прерываемых при поступлении запроса на установление многоадресного соединения П1 или П2 одноадресных соединений определено формулами:

( bi — (С — b2l — dn), m = 0, С — b2l — dn < bi,

Ni (i,m,n) = \ 0, m = 1 V (m = 0, С — Ы — dn > bi),

ЛТ. f b2 — (C — bim — dn), l = 0, С — bim — dn < b2,

N2 (l,™,n) = {0i i = 1 V (l = 0, С — bim — dn > b2).

По причине прерывания обслуживания стационарное распределение вероятностей p (l,m,n), (l,m,n) е X состояний системы не представимо в аналитическом виде. В следующем разделе предложен рекуррентный алгоритм расчёта р (I, т, п).

3. Алгоритм расчёта стационарного распределения вероятностей состояний модели

Рекуррентный алгоритм расчёта ненормированных вероятностей q (1, т, п) состояний модели сформулирован в лемме 1.

Лемма 1. Ненормированные вероятности q (1,т,п) имеют вид

q

В формуле (2) коэффициенты aimn, ßimn, limn, Simn вычисляются по рекуррентным соотношениям

1. (а) аооо = 0, ßooo = 0, ^000 = 0, Ö000 = 1,

/м 'J' R M^R—iTl п л Л + Л + ^

(b) «ooi = —, Р001 =--, 7001 = 0, Ö001 =-,

к к к

(c) п = 2,...,С — Ъ2 + 1

п • а00п = (¿001 + П — 1) • &00,п-1 + «001 • &01,п-1 + ß00i • «10,п-1 Oj • tt00,n—2,

п • ß00n = (^001 + П — 1) • ß00,n-i + «001 • ß0i,n-i + ß00i • ßl0,п-1 — а • ß00,n-2 i

n • 700n = (¿001 + n — 1) • 700,n-i + 00i • 70i,n-i + ß00i • ъ0,n-i — а • j00,n-2,

n • Ö00n = (¿001 + n — 1) • Ö00,n-1 + «001 • Ö0i,n-i + ß00i • ¿10,n-i — а • Ö00,n-2,

(d) п = С - &2 + 2,..., С - bi + 1

п  аооп = (¿001 + п - 1)  aoo,„-i + «ooi  «oi,n-i - а  «oo,n-2,

п  Poon = (¿ooi + П - 1)  Poo,n-1 + «ooi  Poi,n-i - a  Po0,n-2, n  7oon = (¿ooi + n - 1)  7oo,n-i + «ooi  7oi,n-i - a  joo,n-2,

n  5oon = (^ooi + n - 1)  doo,n-1 + «ooi  ^0i,n-i - a  $00,n-2,

(e) n = С - bi + 2,..., С

n  aoon = (fooi + П - 1)  aoo,n-i - a  aoo,n-2,

n  Poon = (¿ooi + n - 1)  ftoo,n-1 - a  fioo,n-2, n  7oon = (¿ooi + n - 1)  7oo,n-i - a  joo,n-2,

n  5oon = (^ooi + n - 1)  ¿oo,n-i - a  $00,n-2,

2. (a) aioo = 0, fiWo = 1, 7ioo = 0, ¿ioo = 0,

/м n я Л (eR - 1)-i + Л + ^ n Л

(b) aioi = 0, Pioi =-, 7ioi =--, Oioi =--,

к к к

(c) n = 2,...,С - bi - b2 + 1

n  aion = (Pioi + n - 1)  aio,n-i + ¿ioi  «oo,n-i + 7ioi  «ii,n-i - a  aw,n-2,

n  Pi0n = (Pi0i + n - 1)  ^io,n-i + ^i0i  P00,n-i + 7ioi  ^ii,n-i - a  Pl0,n-2, n  7ion = (Pioi + n - 1)  7io,n-i + ¿ioi  7oo,n-i + 7ioi  7ii,n-i - a  ^w,n-2, n  5ion = (Pioi + n — 1)  5io,n-i + ^ioi  ^oo,n-i + 7ioi  ^ii,n-i - a  5lo,n-2,

(d) n = С - bi - b2 + 2,..., С - b2

n  «ion = (Pioi - х/к + n - 1)  aio,n-i + ¿ioi  aoo,n-i - a  aw,n-2,

n  Pion = (Pioi - X/K + n - 1)  ^io,n-i + ^ioi  Poo,n-i - a  Pl0,n-2, n  7i0n = (Pioi - х/к + n - 1)  7i0,n-i + ¿ioi  7oo,n-i - a  7io,n-2, n  5Wn = (Pioi - х/к + n - 1)  ¿io,n-i + ¿i0i  ^oo,n-i - a  Sw,n-2,

3. (a) aoio = 1, Poio = 0, 7oio = 0, ¿oio = 0,

Л + n + ^ д п Л (eR - Л

(b) aoii =-, Poii = 0, 7oii =--, Ooii = —,

к к к

(c) n = 2,...,С - bi - b2 + 1

n  aoin = (aoii + n - 1)  «oi,n-i + 7oii  «ii,n-i + ¿oii  «oo,n-i - a  aoi,n-2,

n  Poin = («0ii + n - 1)  ^0i,n-i + 70ii  Pii,n-i + ^oii  P00,n-i - a  Pol,n-2, n  7oin = (aoii + n - 1)  7oi,n-i + 7oii  7ii,n-i + ¿on  7oo,n-i - a  7oi,n-2, n  5oin = (aoii + (n - 1))  foi,n-i + 7oii  $ii,n-i + ¿oii  5oo,n-i - a  6oi,n-2,

(d) n = С - bi - b2 + 2,..., С - bi

n  aoin = ((n + v) /к + n - 1)  &oi,n-i + ^oii  «oo,n-i - a  aoi,n-2, n  Poin = ((n + v) /к + n - 1)  Poi,n-i + ¿on  Poo,n-i - a  Poi,n-2,

П  = ((ß + V) /к + П - 1)  ~io\,n-l + ¿011 ' l00,n—1 - а  701,п-2,

п  5oin = ((ß + v) /к + п - 1)  5о1,п-1 + ¿011  ¿00,п-1 - а  öoi,n-2, 4. (a) а.110 = 0, ß110 = 0, ^110 = 1, ¿110 = 0,

/м Л Л Л (eR - 1)-1 + ß + и

(b) am =--, ßm = —, ^111 =-, dm = 0,

к к к

(c) п = 2,..., С - b1 - Ь2

п  ацп = (7111 + п - 1)  ап,п-1 + am  а01,п—1 + ßm  aw,n-1 - а  ац,п—2,

п  ßun = (7111 + п - 1)  ßu,n-1 + аш  ß01,n-1 + ßm  ßw,n-1 - а  ßu,n—2,

п  7ип = (7111 + п - 1)  7и,п-1 + аш  701,п-1 + ßm  Ъ0,п-1 - а  7и,п—2, П  0Пп = (7111 + п - 1)  Ö11,n-1 + а.111  Ö01,n-1 + ßm  5w,n-1 - а  Ö11,n-2. Величины х, у, z являются решением системы линейных уравнений

((С к + Л + X) 0,00с - va,00C-1)  х + ((С к + Л + X) ß00C - vß00C-1)  У+

+ ((Ск + Л + X) 700с - V700C-1)  z = - (Ск + Л + X) S00C + VÖ00C-1,

I ((С - Ь1) к + ß) а01,с-ъг - va01,c-bt-1 - А ^ а00п\  х+

V n=C—bi )

+ ((С - Ь1) К + ц) ß01,C-bt - vß01,C — 61 — 1

-х £

ß00  У+

V п=С—Ъ1 )

+ I ((с - Ъ\) к + у) l01,c—bi - v^01,c—bi — 1 - А ^ 700n I  ^ =

V n=C—bi )

С

= - ((с - h) к + ц) Ö01,c—bi + vÖ01,c—bi — 1 + А ^ 000п,

n=C—b1

ИЛ (eR - 1) 1 + (С - Ь2) kJ aw,c—b2 - vaw,c—b2—1 - Л ^ «00™)  х+

V п=С—В )

ЦЛ (eR - 1)~1 + (С - Ъ2) ^jßw,c—b2 - vßw,c—b2—1 - Л ^ ß00u\  У+

V п=С—Ъ2 )

^ (л (eR - 1) 1 + (С - Ь2) —Ъ2 - V^10,c—b2—1 - Л ^ 700«  ^ =

V п=С—Ь2 /

С

= - (Л (eR - 1 + (С - Ь2) K^Ö10,c—b2 + v510,c—b2—1 + Л ^ ¿00п.

п=С—Ъ2

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

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

В = р

TT Л Ь2 — С + п

п= > 1-:---- Р (0, 0, П) +

tri лЛ + \ + V + пк п

П=С — 02 + 1

х-1 Л bi — С + п п .

+ > 1-;---1--Р (0, 0, п) +

f-f Л + Л + V + пк п

п=С — Ь1 +1

+

где

/с-ь2 с

р (I, т,п) = д (I, т,п)  ^^ д (1,0, п) + ^^ д (0, 0, п) +

\ п=0 п=0

С-Ьг С'-Ъ1-Ъ2 \ -1

+ ^ д

п=0 п=0 /

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

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

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

Литература

1. Modelling and Dimensioning of Mobile Wireless Networks: from GSM to LTE / M. Stasiak, M. Glabowski, A. Wisniewski, P. Zwierzykowski. — Willey, 2010. — P. 340.

2. Basharin G. P., Gaidamaka Y. V., Samouylov K. E. Mathematical Theory of Teletraffic and its Application to the Analysis of Multiservice Communication of Next Generation Networks. — Germany, Heidelberg: Springer-Verlag, 2013. — Vol. 47. — Pp. 62-69.

3. Approximating Performance Measures of Radio Admission Control Model for Non Real-Time Services with Maximum Bit Rates in LTE / S. Y. Shorgin, K. E. Samouylov, I. A. Gudkova et al. // AIP Conference Proceedings. — Vol. 1648. — USA: AIP Publishing, 2015. — Pp. 1-4.

4. Gudkova I. A., Samouylov K. E. Modelling a Radio Admission Control Scheme for Video Telephony Service in Wireless Networks / Ed. by S. Balandin, R. Dunaytsev, Y. Koucheryavy. — Germany, Heidelberg: Springer-Verlag, 2012. — Vol. 7469. — Pp. 208-215.

5. Ghaderi M., Boutaba R. Call Admission Control in Mobile Cellular Networks: a Comprehensive Survey. — Johns Wiley & Sons Ltd., 2006. — Vol. 6. — Pp. 6993.

6. Liao H., Wang X, Chen H. H. Adaptive Call Admission Control for Multi-Class Services in Wireless Networks // Proc. of the IEEE International Conference on Communications ICC-08. — Beijing, China: 2008. — Pp. 2840-2844.

7. Modelling and Performance Analysis of Pre-Emption Based Radio Admission Control Scheme for Video Conferencing over LTE / V. Y. Borodakiy, I. A. Gudkova, K. E. Samouylov, E. V. Markova // Proc. of the 6th International Conference ITU Kaleidoscope: Living in a converged world - impossible without standards? K-LCW-2014. — St. Petersburg, Russia: 2014. — Pp. 53-59.

8. Khabazian M., Kubbar O., Hassanein H. S. A Fairness-Based Pre-Emption Algorithm for LTE-Advanced // Proc. of the 10th IEEE Global Telecommunications Conference GL0BEC0M-2012. — Anaheim, California, USA: 2012. — Pp. 53205325.

9. On Pre-Emption and Congestion Control for LTE Systems / R. Kwan, R. Arnott, R. Trivisonno, M. Kubota // Proc. of the 72nd Vehicular Technology Conference VTC2010-Fall. — Ottawa, Canada: 2010. — Pp. 6-9.

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

UDC 621.39

Recursive Algorithm for Calculating Stationary Probability Distribution of Model with Interruption of Unicast Traffic by

Multicast Traffic

I. A. Gudkova, E. V. Markova

Department of Applied Probability and Informatics

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

LTE fourth generation networks become one of the most important trends in the modernization of telecommunications systems. According to international standards, LTE networks specify nine types of services, that differ in terms of the bit-rate (guaranteed or non-guaranteed) and priority level. Depending on the bit rate overall traffic generated during the service providing is divided into three types: unicast streaming, streaming multicast, and elastic. The priority level can be realized with use of different mechanisms - bit rate degradation, service interruption, reservation, threshold and probabilistic management - that form the foundations of the radio admission control schemes. In the paper, a model of RAC scheme is proposed with service interruption of unicast traffic and two service disciplines for multicast traffic. The recursive algorithm is proposed for calculating main performance measures of model — blocking and pre-emption probabilities for unicast traffic.

Key words and phrases: LTE, radio admission control, unicast traffic, multicast traffic, interruption, recursive algorithm.

References

1. M. Stasiak, M. Glabowski, A. Wisniewski, P. Zwierzykowski, Modelling and Dimensioning of Mobile Wireless Networks: from GSM to LTE, Willey, 2010.

2. G. P. Basharin, Y. V. Gaidamaka, K. E. Samouylov, Mathematical Theory of Teletraffic and its Application to the Analysis of Multiservice Communication of Next Generation Networks, Vol. 47, Springer-Verlag, Germany, Heidelberg, 2013, pp. 62-69.

3. S. Y. Shorgin, K. E. Samouylov, I. A. Gudkova, E. V. Markova, E. S. Sopin, Approximating Performance Measures of Radio Admission Control Model for Non Real-Time Services with Maximum Bit Rates in LTE, in: AIP Conference Proceedings, Vol. 1648, AIP Publishing, USA, 2015, pp. 1-4.

4. I. A. Gudkova, K. E. Samouylov, Modelling a Radio Admission Control Scheme for Video Telephony Service in Wireless Networks, Vol. 7469, Springer-Verlag, Germany, Heidelberg, 2012, pp. 208-215.

5. M. Ghaderi, R. Boutaba, Call Admission Control in Mobile Cellular Networks: a Comprehensive Survey, Vol. 6, Johns Wiley & Sons Ltd., 2006, pp. 69-93.

6. H. Liao, X. Wang, H. H. Chen, Adaptive Call Admission Control for Multi-Class Services in Wireless Networks, in: Proc. of the IEEE International Conference on Communications ICC-08, Beijing, China, 2008, pp. 2840-2844.

7. V. Y. Borodakiy, I. A. Gudkova, K. E. Samouylov, E. V. Markova, Modelling and Performance Analysis of Pre-Emption Based Radio Admission Control Scheme for Video Conferencing over LTE, in: Proc. of the 6th International Conference ITU Kaleidoscope: Living in a converged world - impossible without standards? K-LCW-2014, St. Petersburg, Russia, 2014, pp. 53-59.

8. M. Khabazian, O. Kubbar, H. S. Hassanein, A Fairness-Based PreEmption Algorithm for LTE-Advanced, in: Proc. of the 10th IEEE Global Telecommunications Conference GL0BEC0M-2012, Anaheim, California, USA, 2012, pp. 5320-5325.

9. R. Kwan, R. Arnott, R. Trivisonno, M. Kubota, On Pre-Emption and Congestion Control for LTE Systems, in: Proc. of the 72nd Vehicular Technology Conference VTC2010-Fall, Ottawa, Canada, 2010, pp. 6-9.

10. I. A. Gudkova, O. N. Plaksina, Performance Measures Computation for a Single Link Loss Network with Unicast and Multicast Traffics, Vol. 6294, Springer-Verlag, Germany, Heidelberg, 2010, pp. 256-265.