Use of group poisson flow in simulation modeling of modern video traffic

Full Text

Введение

В настоящее время математическими моделями, наиболее адекватно описывающими трафик современных сетей телекоммуникаций, считаются модели самоподобного трафика [1–6; 9; 10]. Действительно, с помощью таких моделей можно одновременно приблизить сразу несколько важных статистических характеристик трафика как первого, так и более высоких порядков [3]. Однако главным недостатком этих моделей является весьма высокая сложность, затрудняющая использование их на практике.

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

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

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

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

Приближение с использованием аналитических выражений

Рассматривается Пуассоновский поток с параметром λ независимых событий, i-тое (i = 1,2…) из которых есть одновременное прибытие B_i пакетов для передачи, где B_i – независимые одинаково распределенные случайные величины. Все пакеты одинакового размера, они поступают в буфер и передаются оттуда по каналу постоянной битовой скорости. Таким образом, мы рассматриваем систему массового обслуживания (СМО) типа G/D/1 с групповым Пуассоновским потоком на входе.

В работе [7] с помощью интервального метода [8] для системы G/D/1 были получены формулы для математического ожидания очереди (обобщение формулы Поллачека–Хинчина) и для вторых моментов очереди, а именно:

$\overline{q}=\frac{D\left(m\right)+2R(q_{t-1},m_t)}{2(1-\rho )}-\frac{\rho }{2}$,

$\begin{array}{c}\overline{q^2}=\frac{\overline{q}}{1-\rho }\left(D\right(m)+{\left(1-\rho \right)}^2)+\\ +\frac{\overline{m^3}-3\overline{m^2}+2\rho }{3(1-\rho )}\end{array}$,

$D\left(q\right)=\overline{q^2}-{\left(\overline{q}\right)}^2$.

где m – случайная величина, равная количеству заявок, приходящих в систему в течении случайно выбранного интервала обслуживания одной заявки, ρ – коэффициент загрузки прибора (канала связи), D(m) – ее дисперсия, R(q_t-1 m_t,) – корреляция между величиной очереди перед началом некоторого интервала обслуживания заявки и количеством заявок, поступивших во время этого обслуживания, q – очередь, D(q) – дисперсия очереди.

Там же для группового пуассоновского потока получено, что:

$\overline{m}=\rho =\lambda \tau \overline{B}$,

$\overline{m^2}=\lambda \tau \overline{B^2}+{\left(\lambda \tau \overline{B}\right)}^2$,

$\overline{m^3}=\lambda \tau \overline{B^3}+3\left(\lambda \tau \right)\overline{B}\overline{B^2}+{\left(\lambda \tau \overline{B}\right)}^3$,

$D\left(m\right)=\lambda \tau \overline{B^2},{\mu }_3\left(m\right)=\lambda \tau \overline{B^3}$.

где τ – время обслуживания заявки, μ₃(m) –третий центральный момент m, B – размер пачки заявок.

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

$\overline{q}\left(\rho \right)=\frac{\rho (\overline{B^2}-\overline{B}(1-\rho \left)\right)}{2\overline{B}(1-\rho )}$, (1)

$\begin{array}{c}\overline{q^2}\left(\rho \right)=\frac{\rho (\overline{B^2}-\overline{B}(1-\rho \left)\right)}{2\overline{B}(1-\rho )}\times \\ \times \left(\rho \frac{\overline{B^2}}{\overline{B}}+{(1-\rho )}^2\right)+\\ +\frac{{\rho }^3-3{\rho }^2+2\rho }{3(1-\rho )}+\frac{\rho \overline{B^3}-3\rho \overline{B^2}(1-\rho )}{3\overline{B}(1-\rho )}\end{array}$, (2)

$D\left(q\right(\rho \left)\right)=\overline{q^2\left(\rho \right)}-{\left(\overline{q}\right(\rho \left)\right)}^2$. (3)

Далее для используемых трасс реального видеотрафика методом имитационного моделирования, когда данная трасса является входным потоком в систему G/D/1, были найдены эмпирические оценки средней очереди и дисперсии очереди для ряда значений ρ:

$\overline{q^{*}}\left({\rho }_i\right),i=\mathrm{1,...,}NиD^{*}\left({\rho }_j\right),j=\mathrm{1,...,}M$.

Различные значения ρ получены путем изменения скорости обслуживания (скорости передачи данных по каналу).

В качестве распределения размера пачки в групповом пуассоновском потоке был взят простейший случай постоянного размера пачки B = const, и методом взвешенных наименьших квадратов определено значение B, при котором значение целевой функции (4) минимально.

$\begin{array}{c}J\left(B\right)=\sum _{i=1}^N\frac{{\left(\overline{q^{*}}\left({\rho }_i\right)-\overline{q}\left({\rho }_i\right)\right)}^2}{\overline{q^{*}}\left({\rho }_i\right)}+\\ +\sum _{j=1}^M\frac{{\left(D^{*}\left({\rho }_j\right)-D\left({\rho }_j\right)\right)}^2}{D^{*}\left({\rho }_j\right)}\end{array}$ (4)

При вычислении целевой функции используются формулы (1)–(3) при условии B = const.

На рисунках 1 и 2 приведены для средней очереди и дисперсии очереди, точки, полученные из реального трафика, использовавшиеся в функции (4), графики зависимостей (1) и (2) для B, минимизирующего функцию (4) и для сравнения графики для ординарного пуассоновского потока. В этом эксперименте использовался трафик от видеокодека стандарта H264. На рисунках 3 и 4 приведены результаты аналогичного эксперимента с видеотрафиком типа vid.

 

Рисунок 1. Зависимость средней очереди от загрузки прибора, трафик H264

 

Рисунок 2. Зависимость дисперсии очереди от загрузки прибора, трафик H264

 

Рисунок 3. Зависимость средней очереди от загрузки прибора, трафик vid

 

Рисунок 4. Зависимость дисперсии очереди от загрузки прибора, трафик vid

 

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

Отметим, что кроме простейшего случая постоянного размера пачки, мы проводили аналогичные эксперименты для случая, когда размер пачки мог иметь два различных значения: одно с вероятностью p, а другое с вероятностью 1-p, и минимизация целевой функции (4) проводилась по этим двум размерам и вероятности p. Однако значимого улучшения результатов не было получено.

Проверка результатов с помощью имитационного моделирования

Для проверки были сгенерированы групповые пуассоновские потоки с найденными параметрами, и, использовав их в качестве входных в систему G/D/1, получены эмпирические зависимости средней и дисперсии очереди. Результаты приведены на рисунках 5 и 6 для кодека H264 и на рисунках 7 и 8 для видеотрафика vid. Видно, что эмпирические зависимости, найденные по трассам имитационного эксперимента, практически совпадают с теоретическими, вычисленными по формулам (1)–(3).

 

Рисунок 5. Зависимость средней очереди от загрузки прибора, трафик H264

 

Рисунок 6. Зависимость дисперсии очереди от загрузки прибора, трафик H264

 

Рисунок 7. Зависимость средней очереди от загрузки прибора, трафик vid

 

Рисунок 8. Зависимость дисперсии очереди от загрузки прибора, трафик vid

 

Некоторое различие для дисперсии очереди в области больших нагрузок для трафика vid связано с медленным установлением стационарного состояния при размере пачки, равном 245: в экспериментах использовалась трасса, содержащая моменты прихода 160 000 пакетов, и при этом стационарное состояние при больших нагрузках еще не вполне установилось.

Заключение

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

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

About the authors

Boris Y. Likhttsinder

Povolzhskiy State University of Telecommunications and Informatics

Author for correspondence.
Email: lixt@psuti.ru

Professor of Networks and Communication Systems Department, Doctor of Technical Science

Russian Federation, Samara

Alexander Y. Privalov

Samara National Research University

Email: privalov1967@gmail.com

Professor of Applied Mathematics and Physics Department, Doctor of Technical Science

Russian Federation, Samara

References

Supplementary files