Queue dispersion in queue systems with group poisson flows

Full Text

Введение

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

Модели «самоподобного» трафика, учитывающие корреляционные свойства, оказались слишком сложными, неэффективными. На смену им пришел целый класс моделей потоков с коммутируемой цепью Маркова – ВМАР-потоки [1– 3; 6–13]. Среди указанных потоков можно выделить групповые пуассоновские потоки [5]. Это неординарные потоки событий, каждое из которых соответствует одновременному появлению нескольких заявок. События возникают независимо друг от друга и имеют экспоненциальное распределение интервалов между соседними событиями. Следовательно, поток событий является пуассоновским.

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

$\overline{m\left(\tau \right)}=\lambda \tau =\rho$.

$D_m\left(\rho \right)=\lambda \tau \overline{k^2}=\rho \overline{k}(1+{\nu }_k^2)={Е}_m\rho$.

Здесь, ${\nu }_k^2=\frac{D_k}{{\left(\overline{k}\right)}^2}$ – квадрат коэффициента вариации, а $\overline{k}$ – среднее число заявок в «пачке».

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

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

$\overline{q\left(\rho \right)}=\frac{D_m\left(\rho \right)}{2(1-\rho )}-\frac{\rho }{2}=\frac{E_m\rho }{2(1-\rho )}-\frac{\rho }{2}$ (1)

В частном случае ординарного пуассоновского потока: $k_i=1,\overline{k}=1,{\nu }_k^2=0$, $E=1$ – при этом справедлива известная формула:

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

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

Для таких потоков отличаться будут лишь значения дисперсий $D_q\left(\rho \right)$ размеров очередей.

Второй начальный момент

Второй начальный момент размера очереди $\overline{q^2\left(\rho \right)}$ определим из соотношения баланса [4].

$\begin{array}{c}{q}_i\left(\rho \right)=q_{i-1}\left(\rho \right)+m_i\left(\rho \right)-{\delta }_i\left(\rho \right);\\ {\delta }_i\left(\rho \right)=\mathrm{0,}еслиq_{i-1}\left(\rho \right)=m_i\left(\rho \right)=0;\\ {\delta }_i\left(\rho \right)=\mathrm{1,}впротивномслучае.\end{array}$ (2)

где $q_i\left(\rho \right)$ – значение очереди, $m_i\left(\rho \right)$ – число поступивших заявок, а ${\delta }_i\left(\rho \right)$ – обработанных число заявок, в течение интервала времени $\tau$.

Ограничения имеют следующий вид:

$\begin{array}{l}{{\delta }_i}^k\left(\rho \right)={\delta }_i\left(\rho \right),m_i\left(\rho \right){\delta }_i\left(\rho \right)=m_i\left(\rho \right),\\ q_{i-1}\left(\rho \right){\delta }_i\left(\rho \right)=q_{i-1}\left(\rho \right),\overline{{\delta }_i\left(\rho \right)}=\overline{m_i\left(\rho \right)}\end{array}$. (3)

При возведении в третью степень уравнения (2), коэффициент загрузки для ρ краткости будем опускать:

${q^3}_i={q^3}_{i-1}+3{q^2}_{i-1}(m_i-{\delta }_i)+3{q^{}}_{i-1}{(m_i-{\delta }_i)}^2+{(m_i-{\delta }_i)}^3$.

После соответствующих преобразований, с учетом принятых ограничений получим:

$\begin{array}{c}{q^3}_i={q^3}_{i-1}+3{q^2}_{i-1}{m}_i-3{q^2}_{i-1}+3q_{i-1}({m_i}^2-2m_i+1)+\\ +({m_i}^3-3{m_i}^2+3m_i-{\delta }_i)\end{array}$.

Произведем усреднение обеих частей:

$\begin{array}{c}3\overline{{q^2}_{i-1}}\left(1-\overline{m_i}\right)=3\overline{q_{i-1}}(\overline{{m_i}^2}-2\overline{m_i}+1)+\\ +(\overline{{m_i}^3}-3\overline{{m_i}^2}+2\overline{m_i})\end{array}$.

$\begin{array}{c}3\overline{{q^2}_{i-1}}\left(1-\overline{m_i}\right)=3\overline{q_{i-1}}(\overline{D_m}+{\overline{m_i}}^2-2\overline{m_i}+1)+\\ +(\overline{{m_i}^3}-3\overline{{m_i}^2}+2\overline{m_i})\end{array}$.

$\begin{array}{c}3\overline{{q^2}_{i-1}}\left(1-\overline{m_i}\right)=3\overline{q_{i-1}}{D}_m+3\overline{q_{i-1}}+\\ +(\overline{{m_i}^3}-3\overline{{m_i}^2}+2\overline{m_i})\end{array}$

Определим значение $\overline{{q^2}_{i-1}}$:

$\overline{{q^2}_{i-1}}=\frac{\overline{q_{i-1}}{D}_m}{\left(1-\overline{m_i}\right)}+\overline{q_{i-1}\cdot }\left(1-\overline{m_i}\right)+\frac{\overline{{m_i}^3}-3\overline{{m_i}^2}+2\overline{m_i}}{3\left(1-\overline{m_i}\right)}$.

$\overline{{q^2}_{i-1}}=\overline{q_{i-1}}[\frac{D_m}{\left(1-\overline{m_i}\right)}+\left(1-\overline{m_i}\right)+\frac{\overline{{m_i}^3}-3\overline{{m_i}^2}+2\overline{m_i}}{3\left(1-\overline{m_i}\right)}$.

$\overline{{q^2}_{i-1}}=\overline{q_{i-1}}\frac{D_m+{\left(1-\overline{m_i}\right)}^2}{\left(1-\overline{m_i}\right)}+\frac{\overline{{m_i}^3}-3\overline{{m_i}^2}+2\overline{m_i}}{3\left(1-\overline{m_i}\right)}$.

$\begin{array}{l}\\ \overline{{q^2}_{i-1}}=\frac{\overline{q_{i-1}}}{\left(1-\overline{m_i}\right)}[D_m+{\left(1-\overline{m_i}\right)}^2]+\frac{\overline{{m_i}^3}-3\overline{{m_i}^2}+2\overline{m_i}}{3\left(1-\overline{m_i}\right)}\end{array}$.

Выразим третий начальный момент $\overline{{m_i}^3}$ через третий центральный момент ${\mu }_3=\overline{{(m_i-m_i)}^3}$.

$\overline{{m_i}^3}=\overline{{(m_i-m_i)}^3}+3\overline{m_i}{D}_m+{\overline{m_i}}^3={\mu }_3+3\overline{m_i}{D}_m+{\overline{m_i}}^3$.

После подстановки получим:

$\overline{{q^2}_{i-1}}=\overline{q_{i-1}}\left[\frac{D_m+{\left(1-\overline{m_i}\right)}^2}{\left(1-\overline{m_i}\right)}\right]+\frac{3\overline{m_i}{D}_m{\overline{+m_i}}^3-3D_m-3{\overline{m_i}}^2+2\overline{m_i}}{3\left(1-\overline{m_i}\right)}+\frac{{\mu }_3}{3\left(1-\overline{m_i}\right)}$,

$\begin{array}{l}\overline{{q^2}_{i-1}}=\frac{\overline{q_{i-1}}}{\left(1-\overline{m_i}\right)}[D_m+{\left(1-\overline{m_i}\right)}^2]+\\ +\frac{{\overline{m_i}}^3+3\overline{m_i}{D}_m-3\overline{{m_i}^2}+2\overline{m_i}}{3\left(1-\overline{m_i}\right)}+\frac{{\mu }_3}{3\left(1-\overline{m_i}\right)}\end{array}$.

Подставляя $\overline{q_{i-1}}=\overline{q\left(\rho \right)}$ из (1) и учитывая, что $\overline{m\left(\rho \right)}=\lambda \tau =\rho$, получим:

$\begin{array}{l}\overline{q^2\left(\rho \right)}=\frac{D_m\left(\rho \right)-\rho (1-\rho )}{2{\left(1-\rho \right)}^2}\left[D_m\right(\rho )+{\left(1-\rho \right)}^2]+\\ +\frac{{\rho }^3+3\rho D_m\left(\rho \right)-3D_m\left(\rho \right)-3{\rho }^2+2\rho }{3\left(1-\overline{\rho }\right)}+\frac{{\mu }_3\left(\rho \right)}{3\left(1-\rho \right)}\end{array}$.

Приведенное ниже соотношение позволяет определить второй начальный момент размера очереди в СМО с групповыми пуассоновскими потоками.

Для групповых потоков второй момент размера очереди определится соотношением:

$\begin{array}{l}\overline{q^2\left(\rho \right)}=\frac{E_m\rho -\rho +{\rho }^2}{2{\left(1-\rho \right)}^2}[E_m\rho +1-2\rho +{\rho }^2]+\\ +\frac{{\rho }^3+3E_m{\rho }^2-3E_m\rho -3{\rho }^2+2\rho }{3\left(1-\overline{\rho }\right)}+\frac{{\mu }_3\left(\rho \right)}{3\left(1-\rho \right)}\end{array}$.

Для простейшего потока $E_m=\mathrm{1,}{\mu }_3\left(\rho \right)=\rho$ выражение упростится:

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

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

Дисперсия очередей

Дисперсию размеров очередей определим на основании соотношения:

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

Выполним преобразования:

$\overline{D_q\left(\rho \right)}=\frac{D_m\left(\rho \right)-\rho (1-\rho )}{2{\left(1-\rho \right)}^2}\left[D_m\right(\rho )+{\left(1-\rho \right)}^2]+\frac{{\rho }^3+3\rho D_m\left(\rho \right)-3D_m\left(\rho \right)-3{\rho }^2+2\rho }{3\left(1-\overline{\rho }\right)}\frac{{\mu }_3\left(\rho \right)}{3\left(1-\rho \right)}-\frac{{\left[D_m\right(\rho )-\rho (1-\rho \left)\right]}^2}{4{\left(1-\rho \right)}^2}=$

$=\frac{D_m\left(\rho \right)-\rho (1-\rho )}{2{\left(1-\rho \right)}^2}\left[D_m\right(\rho )+{\left(1-\rho \right)}^2-\frac{D_m\left(\rho \right)-\rho (1-\rho )}{2}]+\frac{{\rho }^3+3\rho D_m\left(\rho \right)-3D_m\left(\rho \right)-3{\rho }^2+2\rho }{3\left(1-\overline{\rho }\right)}+\frac{{\mu }_3\left(\rho \right)}{3\left(1-\rho \right)}=$

$=\frac{D_m\left(\rho \right)-\rho (1-\rho )}{4{\left(1-\rho \right)}^2}\left[2D_m\right(\rho )+2{\left(1-\rho \right)}^2-D_m(\rho )+\rho (1-\rho \left)\right]+\frac{{\rho }^3+3\rho D_m\left(\rho \right)-3D_m\left(\rho \right)-3{\rho }^2+2\rho }{3\left(1-\overline{\rho }\right)}+\frac{{\mu }_3\left(\rho \right)}{3\left(1-\rho \right)}=$

$=\frac{D_m\left(\rho \right)-\rho (1-\rho )}{4{\left(1-\rho \right)}^2}\left[D_m\right(\rho )+2-4\rho +2{\rho }^2+\rho -{\rho }^2]+\frac{{\rho }^3+3\rho D_m\left(\rho \right)-3D_m\left(\rho \right)-3{\rho }^2+2\rho }{3\left(1-\overline{\rho }\right)}+\frac{{\mu }_3\left(\rho \right)}{3\left(1-\rho \right)}=$

$=\frac{D_m\left(\rho \right)-\rho (1-\rho )}{4{\left(1-\rho \right)}^2}\left[D_m\right(\rho )+2-3\rho +{\rho }^2]++\frac{{\rho }^3+3\rho D_m\left(\rho \right)-3D_m\left(\rho \right)-3{\rho }^2+2\rho }{3\left(1-\overline{\rho }\right)}+\frac{{\mu }_3\left(\rho \right)}{3\left(1-\rho \right)}$.

Для простейшего пуассоновского потока $E_m=\mathrm{1,}{D}_m\left(\rho \right)={\mu }_3\left(\rho \right)=\rho$,

$\overline{D_q\left(\rho \right)}=\frac{{\rho }^2}{2{\left(1-\rho \right)}^2}(1-\frac{1}{3}\rho -\frac{1}{6}{\rho }^2)$.

Выражение существенно упрощается.

Заключение

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

About the authors

Boris Y. Likhttsinder

Author for correspondence.
Email: lixt@psuti.ru

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

References

Supplementary files