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

В телекоммуникационных сетях с пакетной коммутацией пуассоновские модели трафика не являются адекватными. Это привело к необходимости разработки новых моделей трафика, основанных на не пуассоновских распределениях [1]. В их числе были потоки Ньютса [2], марковские входные потоки (Markovian Arival Process, MАP) и их обобщения – групповые марковские потоки (Batch Markovian Arival Process, BMАP) [3–10].

Групповые пуассоновские потоки

Были предложены групповые пуассоновские модели потоков [11]. Групповой пуассоновский поток ‒ это пуассоновский поток независимых событий. Каждое событие заключается в одновременном появлении «пачки» из независимых случайно распределенных чисел пакетов.

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

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

_{q (} ρ ₎ = Â (1 + ν B ² ) ρ - ρ _,

2(1 - ρ )    2

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

Для группового пуассоновского потока с постоянным числом заявок в пачке, равным В:

Âρρ

^^^^^—^^^^^— —— --- .

2(1 - ρ )  2

Нетрудно видеть, что для B = 1 получается классическая формула Поллачека-Хинчина для СМО M/D/1.

Групповые детерминированные потоки

Рассматриваются групповые потоки, характеризующиеся тем, что интервалы между последовательными пачками являются постоянными, то есть имеют детерминированный характер [12]. Нами показано, что в рассматриваемом частном случае с постоянными размерами пачек B, выражение для средних значений очередей оказывается весьма простым:

q Ä ( ρ ) = ^Â ₂ ρ - ρ ₂. (2)

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

Зависимости средних размеров очередей q ( ρ ) от коэффициента загрузки ρ в случае групповых потоков с размером пачки B = 10 представлены на рисунке 1.

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

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

В качестве моделей пачечного трафика предлагается использовать групповой смешанный поток. Данный поток является смесью независимых детерминированных и пуассоновских групповых потоков. Средние кривые на рисунке 1 от раж ают зависимости средних размеров очередей q ( ρ ) от коэффициента загрузки ρ для таких смешанных групповых потоков. Средние значения очередей, которые получаются при раздельной генерации групповых детерминированных и групповых пуассоновских потоков, обозначим как q д ( p ) и q_n ( p ) . Примем, что у данных потоков одинаковые и постоянные размеры пачек равные B. С вероятностью P генерируются интервалы группового детерменированного потока, в свою очередь с вероятностью (1–P) генерируются интервалы группового пуассоновского потока.

Суммируя средние значения очередей данных потоков при условии последовательной генерации, получаем:

q ( р ) = q д ⁽ р ) р + q п ( р )(i - ^P );

«д=Apfi-pP) - р        (3)

2(1 - р )    2

0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9

Рисунок 2. Сравнение зависимости средней очереди от загрузки прибора, полученной в результате имитационного моделирования с вычислениями согласно формуле (3)

Соотношение (3) достаточно точно отражает характеристики средних значений очередей для смешанных групповых пуассоновских и детерминированных потоков (рисунок 2).

Групповые квазипуассоновские потоки с одинаковыми паузами

На основе модели группового пуассоновского потока, нами предложено ее расширение – групповой квазипуассоновский поток с одинаковыми паузами.

Особенностью рассматриваемого группового потока является то, что каждый последующий интервал между пачками возрастает на одинаковую величину T . Заявки в рассматриваемом потоке поступают пачками, причем количество заявок в каждой пачке представляет собой независимые одинаково распределенные дискретные случайные величины B _k . Сумма интервалов времени имеющих экспоненциальное распределение с параметром λ и постоянного интервала времени T образует интервал времени между моментами прибытия последовательных пачек. Поскольку основной интерес представляет зависимость средней длины очереди в приборе обслуживания от его загрузки, а временной масштаб не важен, рассматриваемый квазипуассоновский поток можно описать двумя параметрами: B – постоянный размер пачки, α = λ T – отношение детерминированной паузы к среднему значению экспоненциального интервала.

Для того, чтобы определить параметры предлагаемой модели было использовано обобщение формулы Поллачека-Хинчина для системы СМО G/D/1, полученное с помощью интервального метода [13]. Результатом является оценочная формула средний очереди в СМО G/D/1 от загрузки прибора. Данная формула хорошо согласуется с результатами имитационного моделирования:

м= _P B-p^-p)

если p < p₀ ;

q (p) = ^(2- ^°)(£ B _£(L_£) ) ₊

' ' P P 2

p * B --р(1-рУ 2(1-P)

если p p p ₀ .

средняя очередь

а) ⁰

Моделирование, α = 0, Моделирование, α = 1, Моделирование, α = 2, Оценка, α = 0,5 B = 20 Оценка, α = 1,0 B = 20 Оценка, α = 2,0 B = 20

,5 B = 20

,0 B = 20

,0 B =

загрузка прибора

0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9

средняя очередь

б) ⁰

Моделирование, α = 1 B = 10

Моделирование, α = 1 B = 50

Моделирование, α = 1 B = 100

Оценка, α = 1 B = 10

Оценка, α = 1 B = 50

Оценка, α = 1 B = 100

загрузка прибора

0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9

Рисунок 3. Сравнение зависимости средней очереди от загрузки прибора, полученной в результате имитационного моделирования, с вычислениями согласно формуле (4): a) для всех потоков B = 20;

б) для всех потоков α = 1

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

Полученное приближение показывает высокую степень соответствия.

Тандемные квазипуассоновские модели потоков с одинаковыми паузами

Групповые неординарные потоки, в определенной степени, представляют абстракцию реальных потоков пакетов или кадров. Пакеты имеют продолжительность по времени и могут располагаться относительно друг друга, с учетом наличия минимальных межкадровых интервалов (обычно 12 байт). Группы таких пакетов, объединенные в тандемы, образуют пачки, имеющие продолжительность по времени. Наличие тандемных групп пакетов в реальном трафике приводит к существенному уменьшению наклона графика зависимости средних значений очереди при малых значениях коэффициента загрузки. На рисунке 4 показана зависимость средних значений очередей от коэффициента загрузки для пачек пакетов, образуемых в канале UTUB 100 000-4.

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

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

16648,360

13675,440

10702,520

7729,598

4756,675

1783,753

Рисунок 4. Зависимость средних значений очередей от коэффициента загрузки для пачек пакетов, образуемых в канале UTUB 100 000-4 [11]

0,818      0,818      0,818      0,818      0,818      0,818      0,818

распределенной случайной величины с параметром Л , а каждое событие - это начало прибытия

B 2

тандема пачек заявок, то есть, последовательное прибытие фиксированного числа K пачек заявок, размер каждой из которых фиксирован, и интервалы следования между k -той и k +1-ой пачками

B 1

B 1

Первая пачка из тандема всегда прибывает точно в момент события потока. В каждом тандеме соответствующие параметры B _k , к = 1... K и t_k , к = 1... K — 1 являются одинаковыми.

Нетрудно видеть, что групповой квазипуассо-новский поток с постоянным размером пачки B является частным случаем тандемного при K = 1.

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

.____1А т+1/К

t

q ( Р ) =

рВ^р(±^р) 2 K

если р <  р ₀;

q ( р ) = ^(1 + 1 - ^Х ^P B Р ^{(1 Р} ) )

р K р 2

р B * - /(1 - р ) * 2(1 - р')

если р >  р ₀.

При K = 1 эта формула превращается в формулу (4) для группового квазипуассоновского потока.

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

Определим «парный групповой квазипуассо-новский поток» как разновидность группового пуассоновского потока, в котором каждый интервал времени между соседними пачками увеличивается на постоянную величину T , причем по истечении этого промежутка времени формируется вторая пачка заявок. Таким образом, в пределах одного интервала происходит прибытие двух пачек размером B ₁ и B ₂ , при этом используются следующие обозначения:

B 1 = 0 B , B 2 = ( 1 — в ) B ,

B 1 + B ₂ = B , в е [ 0,1 ] .

На рисунке 5 схематически отображен один цикл данной модели.

При этом размер постоянного интервала T не превышает среднего размера экспоненциального интервала:

а = ЛТ .

Выражая данное неравенство через параметр а = Л Т получим:

а < 1.

Рисунок 5. Схематичное отображение интервалов парного группового пуассоновского потока

Данная модель отражает характерное поведение сетевого трафика, при котором крупные пачки пакетов разбиваются на несколько меньших подпачек. Такое разбиение снижает пиковую нагрузку и позволяет более адекватно описывать временную протяженность передачи пакетов в сети. Рассматриваемый поток является модификацией группового квазипуассоновского потока с одинаковыми паузами, в связи с чем имеется возможность использовать схожие предположения при построении аналитической модели, модифицируя уже существующие результаты. На рисунке 6 схематично показаны изменения размеров очереди по времени для рассматриваемой модели. Площадь A S отражает изменение формы треугольника, используемого для расчета поправочного коэффициента в модифицируемой модели. Пересчет поправочного коэффициента позволяет повторно использовать аналитические расчеты для случаев 2 и 3, ввиду того, что их можно свести к частному случаю модели с одинаковыми паузами.

В зависимости от нагрузки аналитическая модель разделяется на несколько случаев. В частности, в зависимости от того, успевает ли обработаться пачка B до окончания промежутка T , а также успевают ли обработаться пачки B ₁ и B ₂ до окончания стационарного промежутка T и экспоненциального промежутка со средним значением 1/ λ соо тветственно. В случае 4, когда обе пачки B 1 и B ₂ не были обработаны за выделенные промежутки, очередь растет бесконечно, и рассматривать аналитические расчеты средней очереди не имеет практического смысла. Это связано с тем, что заявки поступают быстрее, чем обрабатываются, поэтому очередь неограниченно растет, а канал оказывается полностью загруженным. Усредненный размер очереди перестает отображать реальное состояние системы.

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

а)                                          в)

б)                                          г)

Рисунок 6. Изменение числа заявок в системе для различных случаев обработки пачек B ₁ и B ₂ :

а) Пачка B = B 1 + B 2 успевает обработаться за промежуток T ; б) Пачка B = B 1 + B 2 не успевает обработаться за промежуток T , при этом пачка B 1 не успевает обрабатываться за промежуток T ; в) Пачка B = B 1 + B 2 не успевает обработаться за промежуток T , при этом пачка B ₁ успевает обрабатываться за промежуток T ;

г) Пачка B = B 1 + B 2 не успевает обработаться за промежуток T , при этом пачки B 1 и B ₂ не успевают обработаться за соответствующие промежутки T и 1/ λ

В т <  T ;

В 1 т <  T ;

b * =

B, т < - .

² Л

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

т = р

T +1 Л

B ;

* * _ Р ^- p 0

^р =1       ^;

¹ — ^Р 0

a T

Р о =     =----т^;

a +1 т । 1

Л

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

a

Р <---- (a +1);

a

Р <------

Ma + 1)^;

Р<---------

(1 - e )( a + 1)

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

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

t+ -=4 л л

Коэффициент нагрузки при этом можно рассчитать, как:

p = л В т .               (12)

к = S *

1 new

-A S

S

( B + B * ) T -----В— + TB, 2²

TB ²

2 (B - B ’)

Исходя из этого, размер очереди для первого случая рассчитывается следующим образом:

q ( р ) = ( S b 1 + S b ₂ ) Л‘ =

( B Т + B² 2 r ) .*

=--------Л =

( в в ²т + (1 - в ) B 2 т ) ,*

=------------------- л .

= K -

2TB ₂ ( B - B * )

TB ²

Подставим выражение (8) в формулу выше, представив его в виде:

( в - в * ) = А

в р

В

результате получаем:

Если учесть (6) или (12), результирующим выражением средней очереди для случая, когда B успевает обработаться за промежуток T , является: р в ( 1 - 2 в + 2 в ²) .

к - 2 (1 - в)

I р )

Если условия (9) и (11) выполняются, но условие (10) не выполняется:

Случаи (2) и (3) можно рассчитать, скорректировав формулу модифицируемой модели. Поправочный коэффициент определяется как:

K = Р о ( ₂ - Р 4 S * , Р I Р ) S

S ^*

^K 2 new

^^^^^^в

S

( в + в * ) T

A S _    2   + B2 Вт

= TB²

= к -

2 ( B - B * ) 2 B 1 B₂ т ( B - B * )

TB ²

где S * – площадь трапеции, включающая в себя

площадь A S , а S - площадь треугольника, равная

S = TB в

2 (B - B *)

„ 2в(1 - вт(B - B‘) = к--

T

.

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

к = Т.

При этом в зависимости от условий (9), (10) и (11) величина A S будет иметь различные значения.

Р>

TB 2 , Р >

AS = (

Р <

а .

( а + 1)^;

а .

в ( а + 1) ’

(1 - в )( а + 1).

B ₂ В 1 т ,

а р >--------;

в ( а + 1)

а р <       .

( а + 1)

Таким образом, можно пересчитать коэффициент для случая, когда условия (9) и (10) не выполняются:

При учете выражений (6), (7) и (8) результирующей формулой для данного случая является:

к - 2в(1 - в).

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

На рисунке 7 приведено сравнение результатов расчета средней длины очереди по формуле (13) с результатами имитационного эксперимента прохождения парного группового квазипуассонов-ского потока через СМО типа G/D/1. На рисунке 7а приведены примеры для фиксированного суммарного значения B и фиксированного значения а при различных значениях коэффициента 0 . Коэффициент в определяет соотношение B 1 и B ₂ . В предельных случаях, при в = 0 , в = 1 парный групповой квазипуассоновский поток сводится к модифицируемому групповому квазипуассонов-скому потоку с одинаковыми паузами, а соответствующее аналитическое выражение становится аналогичным ранее полученному. На рисунке 7б приведены примеры для фиксированного суммарного значения B и фиксированного значения в при

q ⁽ p ) = -

pB (1 - 2в + 2в2)

I a

, ]p< ------;

Г (a + 1)

*

P >

a

^p 0

P

^p 0

P

-

-

^p 0

P

^p 0

P

-

2 (1 - в)

-

p011 PB - P(1 - P) + P B

2в(1 - в)

*

*

P

*

pB - p(1 - p) + p B

а)

Рисунок 7. Сравнение зависимости средней очереди от загрузки прибора, полученной в имитационном эксперименте и вычисленной по формуле (13): а) Для потоков β = 0,5; б) Для потоков α = 0,5

*

( a + 1)

J4 I (1 - ^p ) ^, I

-

*

P

p >

P <

a

в ( а + 1)

; (13)

(1 — в )( а + 1)

a

P>

M (1 -p)

-

P

( a + 1)

.

P <

a

в ( а + 1)

б)

различных значениях коэффициента a . Приближение получается весьма удовлетворительным.

Выводы

В работе предложены и разобраны модели для пачечного телекоммуникационного трафика – групповые пуассоновские потоки, а также их модификации, включающие групповые детерминированные потоки, смешанные групповые потоки, групповые квазипуассоновские потоки с одинаковыми паузами и их тандемные и парные обобщения. Для всех рассмотренных моделей получены аналитические выражения для оценки средней длины очереди в системе массового обслуживания типа G/D/1, подтвержденные результатами имитационного моделирования.

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