Interval traffic analysis of multichannel queuing systems

Full Text

Введение

Сегодня технология потокового вещания видео все более замещает общепринятую видеотрансляцию, основанную на протоколах RTP/UDP [1–5].

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

При управлении ТСР видеопотоком в отличие от передачи трафика данных возникают дополнительные трудности, связанные с тем, что потребление видеопакетов происходит с определенной постоянной скоростью, называемой «битрейтом». Битрейт определяет разрешающую способность передаваемого видеосообщения. Если пропускная способность канала окажется меньше битрейта, то передача с данным уровнем качества становится невозможной и значение битрейта необходимо уменьшить. Для этого существующие видеокодеки имеют ряд настроек, обеспечивающих ступенчатое изменение битрейта и, следовательно, качества воспроизведения.

Принято считать, что для обеспечения нормальной работы канала, имеющего пропускную способность C и время кругового оборота T, требуется минимальный объем буферной памяти, равный СТ [6]. Из этого следует, например, что для одного канала с пропускной способностью 10 гигабит в секунду, работающего в сети с круговой задержкой 250 миллисекунд, потребуется объем буферной памяти, равный 2,5 гигабайт. Принято также считать, что этот объем увеличивается пропорционально числу каналов. Современные магистральные маршрутизаторы обычно являются многоканальными, и необходимый объем памяти существенно возрастает, при этом предъявляются очень высокие требования к ее быстродействию. При современных технологиях повышение быстродействия памяти сопряжено с увеличением удельной мощности и выделяемой энергии и, следовательно, с увеличением габаритных размеров элементов. Таким образом, снижение объема буферной памяти коммутаторов и маршрутизаторов является одним из важных требований при их проектировании и производстве.

Влияние многоканальности

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

Особенности обработки трафика многоканальными СМО были рассмотрены в [5, 7, 8].

На рис. 1 представлены результаты имитационного моделирования многоканальных СМО с пуассоновскими потоками входных заявок. Показаны зависимости средних размеров очередей $mq\left(\rho \right)=\overline{q\left(\rho \right)}$ одного канала от коэффициента загрузки ρ (скрины получены с помощью разработанной нами системы АМС). Из графиков следует, что при увеличении числа каналов размеры средних очередей существенно уменьшаются. Это явление позволило авторам статьи [6] сделать вывод о возможности существенного сокращения объемов буферной памяти в многоканальных магистральных коммутаторах, предполагая, что входные потоки пакетов являются пуассоновскими.

Однако это далеко не всегда так. Трафик пакетов мультисервисных сетей весьма неравномерен, носит пачечный характер, и увеличение числа каналов СМО часто не приводит к существенному уменьшению среднего размера очередей. На рис. 2 представлены результаты имитационного моделирования многоканальных СМО с входными потоками пакетов видеотрафика (указанные результаты, так же как и результаты, приведенные на рис. 1, были получены с использованием системы АМС). Из графиков следует, что при одинаковой загрузке, приходящейся на каждый канал, увеличение числа каналов не приводит к уменьшению размеров очередей, как это происходит с пуассоновскими потоками (почти все каналы либо одновременно заняты, либо одновременно свободны).

 

Рис. 1. Зависимости $\overline{\mathit{q}\mathbf{\left(}\mathit{p}\mathbf{\right)}}$ пуассоновского потока для систем с различным числом K каналов: K = 1 – верхняя кривая, K = 2 – средняя кривая, K = 1 – нижняя кривая

 

Рис. 2. Зависимости $\overline{\mathit{q}\mathbf{\left(}\mathit{p}\mathbf{\right)}}$ потока видеотрафика для систем с различным числом K каналов: K = 1 – верхняя кривая, K = 50 – средняя кривая, K = 1000 – нижняя кривая

 

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

Интервальный анализ очередей многоканальных СМО

Рассмотрим СМО, имеющую K однотипных каналов обслуживания. Сообщения поступают к любому свободному каналу в соответствии с дисциплиной обслуживания FIFO и образуют единую очередь. Для упрощения будем считать, что времена обслуживания одинаковы и равны τ. Для такой СМО справедливо рекуррентное соотношение, устанавливающее связь между поступающими и обработанными заявками [9]:

$\begin{array}{l}{q}_i\left(\tau \right)=q_{i-1}\left(\tau \right)+m_i\left(\tau \right)-K_i\left(\tau \right) \left(1\right)\\ K_i\left(\tau \right)=\left\{\begin{array}{l}K,\text{\hspace{0.33em}\hspace{0.33em}если\hspace{0.33em}\hspace{0.17em}}{q}_{i-1}\left(\tau \right)+m_i\left(\tau \right)-K\ge 0;\\ q_{i-1}\left(\tau \right)+m_i\left(\tau \right)-\text{\hspace{0.33em}в\hspace{0.33em}противном\hspace{0.33em}случае.}\end{array}\right.\\ \end{array}$

Здесь K_i(τ) – число каналов обслуживания, задействованных на i-м промежутке времени τ.. Случайная величина K_i(τ) может принимать K + 1 различных целых значений (включая нулевое). Если считать $\overline{m_i\left(\tau \right)}=\lambda \tau$, то загрузка одного канала определится соотношением

$\rho =\frac{\overline{m_i\left(\tau \right)}}{K}=\frac{\lambda \tau }{K}$.

Математическое ожидание

$\overline{K_i\left(\tau \right)}=\overline{m_i\left(\tau \right)}=K\rho$.

Из выражения (1) следует, что

$q_i\left(\tau \right)=q_{i-1}\left(\tau \right)+m_i\left(\tau \right)-K,\text{\hspace{0.17em}\hspace{0.17em}если\hspace{0.17em}\hspace{0.17em}}{q}_{i-1}\left(\tau \right)+m_i\left(\tau \right)>K$;

$q_i\left(\tau \right)=\mathrm{0,}\text{\hspace{0.17em}\hspace{0.17em}если\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}}{q}_{i-1}\left(\tau \right)+m_i\left(\tau \right)\le K$.

Возведем первое равенство (1) в квадрат:

$\begin{array}{l}{q}_i^2\left(\tau \right)=q_{i-1}^2\left(\tau \right)+2q_{i-1}\left(\tau \right)\left[m_i\left(\tau \right)-K_i\left(\tau \right)\right]+{\left[m_i\left(\tau \right)-K_i\left(\tau \right)\right]}^2=\\ =q_{i-1}^2\left(\tau \right)+2q_{i-1}\left(\tau \right)m_i\left(\tau \right)-2q_{i-1}\left(\tau \right)K_i\left(\tau \right)+m_i^2\left(\tau \right)-2m_i\left(\tau \right)K_i\left(\tau \right)+K_i^2\left(\tau \right)=\\ =q_{i-1}^2\left(\tau \right)+2q_{i-1}\left(\tau \right)m_i\left(\tau \right)-2K_i\left(\tau \right)\left[q_{i-1}\left(\tau \right)+m_i\left(\tau \right)-K_i\left(\tau \right)\right]+m_i^2\left(\tau \right)-K_i^2\left(\tau \right).\end{array}$     (2)

Нетрудно заметить, что при рассмотренных выше ограничениях K_i(τ) ≤ K выполняется равенство

$K_i\left(\tau \right)\left[q_{i-1}\left(\tau \right)+m_i\left(\tau \right)-K_i\left(\tau \right)\right]=K\left(\tau \right)\left[q_{i-1}\left(\tau \right)+m_i\left(\tau \right)-K_i\left(\tau \right)\right]$.

Действительно, если K_i(τ) ≤ K, то равенство выполняется автоматически. Если K_i(τ) ≤ K, то выражения в квадратных скобках равны нулю и равенство также выполняется. Подставляя в (2), получим:

$\begin{array}{l}{q}_i^2\left(\tau \right)=q_{i-1}^2\left(\tau \right)+2q_{i-1}\left(\tau \right)m_i\left(\tau \right)-2K\left[q_{i-1}\left(\tau \right)+m_i\left(\tau \right)-K_i\left(\tau \right)\right]+m_i^2\left(\tau \right)-K_i^2\left(\tau \right)=\\ =q_{i-1}^2\left(\tau \right)+2q_{i-1}\left(\tau \right)m_i\left(\tau \right)-2K{q}_{i-1}\left(\tau \right)+2K{m}_i\left(\tau \right)-2K{K}_i\left(\tau \right)+m_i^2\left(\tau \right)-K_i^2\left(\tau \right).\end{array}$

Производя усреднение, получим:

$\begin{array}{l}0=2\overline{q_{i-1}\left(\tau \right)m_i\left(\tau \right)}-2K\overline{q_{i-1}\left(\tau \right)}+2K\overline{m_i\left(\tau \right)}-2K\overline{K_i\left(\tau \right)}+\overline{m_i^2\left(\tau \right)}-\overline{K_i^2\left(\tau \right)}\\ 2\overline{q\left(\tau \right)}\left[K-\overline{m_i\left(\tau \right)}\right]=2K\left[\overline{m_i\left(\tau \right)}-\overline{K_i\left(\tau \right)}\right]+\overline{m_i^2\left(\tau \right)}-\overline{K_i^2\left(\tau \right)}+2\text{Cov}\left[q_{i-1}\left(\tau \right);m_i\left(\tau \right)\right]\end{array}$

Учитывая, что $\overline{K_i\left(\tau \right)}=\overline{m_i\left(\tau \right)}$, получим:

$\overline{q\left(\tau \right)}=\frac{\overline{m_i^2\left(\tau \right)}-\overline{K_i^2\left(\tau \right)}+2\text{Cov}\left[q_{i-1}\left(\tau \right);m_i\left(\tau \right)\right]}{2\left[K-\overline{m_i\left(\tau \right)}\right]}$.

Обозначим $D_m\left(\tau \right)=\overline{m_i^2\left(\tau \right)}-{\overline{m_i\left(\tau \right)}}^2$, $D_K\left(\tau \right)=\overline{K_i^2\left(\tau \right)}-{\overline{K_i\left(\tau \right)}}^2$, получим:

$\overline{q\left(\tau \right)}=\frac{D_m\left(\tau \right)-D_K\left(\tau \right)+2\text{Cov}\left[q_{i-1}\left(\tau \right);m_i\left(\tau \right)\right]}{2\left[K-\overline{m_i\left(\tau \right)}\right]}$.                                             (3)

Введем обозначения:

$\begin{array}{c}\\ \\ \end{array}$$\begin{array}{c}{D}_{1m}\left(\rho \right)=\frac{D_m\left(\tau \right)}{K^2};\\ D_{1k}\left(\rho \right)=\frac{D_k\left(\tau \right)}{K^2};\\ m_{1i}\left(\rho \right)=\frac{m_i\left(\tau \right)}{K}.\end{array}$

тогда

$\overline{q_{1K}\left(\rho \right)}=\frac{D_{1m}\left(\rho \right)+2\text{Cov}\left[q_{1K;i-1}\left(\rho \right);m_{1i}\left(\rho \right)\right]-D_{1K}\left(\rho \right)}{2\left(1-\rho \right)}$.                          (4)

Здесь $q_{1K;i-1}\left(\rho \right)=\frac{q_{i-1}\left(\rho \right)}{K}$, а $\overline{q_{1K}\left(\rho \right)}=\frac{\overline{q\left(\rho \right)}}{K}$ – среднее значение очереди, приходящееся на один канал многоканальной СМО, каждый из каналов которой загружен с коэффициентом загрузки ρ. Обозначим:

$J\left(\rho \right)=1+\frac{2\text{Cov}\left[q_{1K;i-1}\left(\rho \right);m_{1i}\left(\rho \right)\right]}{D_{1m}\left(\rho \right)}$.

Этот коэффициент называют «индекс дисперсии». Произведение D_1m(ρ)J(ρ) = D_1E(ρ). назовем эквивалентной дисперсией входного потока заявок. Получим:

$\overline{q_{1K}\left(\rho \right)}=\frac{D_{1Е}\left(\rho \right)-D_{1K}\left(\rho \right)}{2\left(1-\rho \right)}$.

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

Наличие многоканальности учитывается дисперсией числа занятых каналов D_1K(ρ).

Интервальный анализ для пуассоновских входных потоков

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

$K=\mathrm{1,} D_{1m}\left(\rho \right)=\rho , \text{Cov}\left[q_{1K;i-1}\left(\rho \right);m_{1i}\left(\rho \right)\right]=0, D_{1Kp}\left(\rho \right)=D_{1p}\left(\rho \right)$,

$\overline{q_{1p}\left(\rho \right)}=$$\frac{\rho -D_{1p}\left(\rho \right)}{2\left(1-\rho \right)}$.                                                                      (5)

Здесь $\overline{{\mathit{q}}_{\mathit{1}\mathit{p}}\left(\mathit{\rho }\right)}$ – среднее значение очереди, приходящееся на один канал многоканальной СМО с пуассоновским потоком, каждый из каналов которой загружен с коэффициентом загрузки ρ; D_1p(ρ) представляет собой дисперсию числа занятых каналов, включая нулевое значение, при пуассоновском входном потоке.

Поскольку канал всего один, поток чисел занятых каналов K_i = 0;1 представляет собой поток единичных и нулевых значений с вероятностями занятости канала, равными ρ, и незанятости канала(1 - ρ). Дисперсия такой случайной величины D_1p(ρ) = ρ(1 - ρ). Подставляя указанные значения в (5), получим формулу Хинчина – Поллачека для одноканальной системы в ее обычном виде:

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

Анализ выражения (1 - ρ) для одноканальной системы показывает, что оно представляет собой вероятность того, что «не все» каналы заняты. Обозначим такую вероятность для многоканальной системы с пуассоновским входным потоком через 1 - B_Kp(ρ). Тогда вероятность того, что все K каналов заняты и вновь пришедшая заявка поступит в очередь, будет равна B_Kp(ρ). Принимая во внимание указанные рассуждения, после подстановки в (5) для многоканальной СМО с пуассоновским входным потоком получим:

$\overline{q_{Kp}\left(\rho \right)}=$$\frac{B_{Kp}\left(\rho \right)\rho }{2\left(1-\rho \right)}$.                                                                            (7)

Подобное выражение было приведено в книге [10] для СМО  M / M / n (n = K) и свидетельствует о справедливости сделанных допущений. Там же приводится формула для определения B_Kp(ρ) в зависимости от числа каналов K для такой СМО:

$B_{Kp}\left(\rho \right)=$ $\left[1-\frac{{\displaystyle \sum _{i=0}^{K-1}\frac{{\left(K\rho \right)}^i}{i!}}}{{\displaystyle \sum _{i=0}^K\frac{{\left(K\rho \right)}^i}{i!}}}\right]\cdot {\left[1-\rho \frac{{\displaystyle \sum _{i=0}^{K-1}\frac{{\left(K\rho \right)}^i}{i!}}}{{\displaystyle \sum _{i=0}^K\frac{{\left(K\rho \right)}^i}{i!}}}\right]}^{-1}$.                                    (8)

Графическое представление этой зависимости показано на рис. 3.

 

Рис. 3. Зависимость вероятности B_1m(ρ) для различных чисел каналов

 

Для M / D / K, которую мы рассмотрели с помощью интервального анализа, аналитической формулы нет, и мы посчитаем B_Kp(ρ) численно, используя численный метод, описанный в [11], для сравнения со значениями, получающимися по формуле (8).

Метод из [11] заключается в составлении бесконечной системы уравнений баланса для вложенной марковской цепи, описывающей количество занятых приборов в системе, и решении ее методом производящих функций. Показано, что состояние системы M / D / n, рассматриваемое в моменты ухода заявок из системы, образует однородную марковскую цепь со счетным числом состояний, и переходная матрица (полубесконечная) этой вложенной марковской цепи имеет вид

$P={\left(p_{i,j}\right)}_{i,j=\mathrm{0,1,...}}=$ $\left(\begin{array}{cccccc}{\pi }_0& {\pi }_1& {\pi }_2& {\pi }_3& {\pi }_4& \cdots \\ {\pi }_0& {\pi }_1& {\pi }_2& {\pi }_3& {\pi }_4& \cdots \\ ⋮& ⋮& ⋮& ⋮& ⋮& \ddots \\ {\pi }_0& {\pi }_1& {\pi }_2& {\pi }_3& {\pi }_4& \cdots \\ 0& {\pi }_0& {\pi }_1& {\pi }_2& {\pi }_3& \cdots \\ 0& 0& {\pi }_0& {\pi }_1& {\pi }_2& \cdots \\ ⋮& ⋮& ⋮& ⋮& ⋮& \ddots \end{array}\right)$,

где ${\pi }_i=\frac{{\left(\lambda \tau \right)}^i}{i!}\exp \left(-\lambda \tau \right)$, а количество одинаковых строк в начале матрицы равно K – числу обслуживающих приборов в системе. Если нагрузка системы меньше 1, то будет существовать стационарное распределение этой марковской цепи, система уравнений баланса которой, записанная для стационарных вероятностей (обозначим их p_i ), выглядит так:

$p_i={\pi }_i\sum _{k=0}^{K-1}{p}_k+\sum _{k=0}^i{\pi }_k{p}_{K+i-k}$, i ≥ 0.

Зная p_i для i = 0,….,K - 1, из данной системы рекуррентно можно вычислить остальные p_i для i ≥ K, а именно

$\frac{1}{{\pi }_0}{p}_{K+i}=\left(p_i-{\pi }_i\sum _{k=0}^{K-1}{p}_k-\sum _{k=1}^i{\pi }_k{p}_{K+i-k}\right)$, i ≥ 0.

Для определения p_i для i = 0,….,K - 1  ищется решение системы уравнений баланса в терминах производящих функций

$P\left(z\right)=\sum _{i=0}^{\infty }{p}_i{z}^i$.

Умножая i-тое уравнение системы уравнений баланса на zⁱ, суммируя по i и используя свойства пуассоновских вероятностей, можно получить, что

$P\left(z\right)=\exp \left(-\lambda \tau \left(1-z\right)\right)$$\left(\sum _{k=0}^{K-1}{p}_k+\frac{1}{z^K}\left(P\left(z\right)-\sum _{k=0}^{K-1}{p}_k{z}^K\right)\right)$,

откуда

$P\left(z\right)=$$\frac{z^K{\displaystyle \sum _{k=0}^{K-1}{p}_k}-{\displaystyle \sum _{k=0}^{K-1}{p}_k{z}^K}}{z^K\exp \left(-\lambda \tau \left(1-z\right)\right)-1}$.

Далее в [11] с использованием теоремы Руше и аналитичности функции P(z) в единичном круге, включая его границу, показывается, что каждому корню знаменателя в выражении для P(z) должен соответствовать корень числителя этого выражения, то есть для каждого из K корней z_i, i = 0,….,K - 1 уравнения

$z_i^K\exp \left(-\lambda \tau \left(1-z_i^K\right)\right)-1=0$

должно выполняться

$z_i^K\sum _{k=0}^{K-1}{p}_k-\sum _{k=0}^{K-1}{p}_k{z}_i^K$ = 0, i = 0,….,K - 1.

В этот набор уравнений не включено уравнение для z₀ = 1, которое тривиально, и вместо него туда надо включить уравнение из условий нормировки вероятностей p_i, которое выглядит так:

$\frac{1}{K-\lambda }\left(K\sum _{k=0}^{K-1}{p}_k-\sum _{k=0}^{K-1}k{p}_k\right)$ = 0.

Численным решением этой системы и находятся вероятности занятости 0,1,…, K ‒ 1 приборов. К сожалению, данная система для больших K и больших ρ становится сильно обусловленной и стандартными библиотеками численных расчетов (использовалась numpy) не решается. Однако близкие значения B_Kp(ρ), получающиеся из (8) и численных расчетов при небольших значениях K и ρ (см. таблицу), позволяют использовать формулу (8) для M / M / K как хорошее приближение для M / D / K. Причем B_K(ρ) для M / M / K всегда больше, чем для M / D / K, и будут использоваться как верхняя граница для последних.

 

Вероятности занятости всех приборов в многоканальных СМО

ρ		0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
n = 2	M/M/n	0.0182	0.0667	0.1385	0.2286	0.3333	0.4500	0.5765	0.7111	0.8526
	M/D/n	0.0178	0.0645	0.1336	0.2208	0.3233	0.4387	0.5654	0.7019	0.8471
n = 3	M/M/n	3.7·10-3	0.0247	0.0700	0.1412	0.2368	0.3547	0.4923	0.6472	0.8171
	M/D/n	3.6·10-3	0.0236	0.0665	0.1338	0.2253	0.3398	–	–	–
n = 4	M/M/n	7.9·10-4	9.6·10-3	0.0370	0.0907	0.1739	0.2870	0.4287	0.5964	0.7878
	M/D/n	7.8·10-4	9.2·10-3	0.0349	–	–	–	–	–	–

 

Для одноканальной системы B_1m(ρ) = (ρ) и справедлива формула (6).

Как следует из предыдущего, мы рассматриваем значения средней очереди, приходящиеся на один канал многоканальной системы. Сравним их со значениями очередей в эквивалентной одноканальной системе с аналогичной загрузкой ρ. В одноканальной системе пришедшая заявка поступит в очередь с вероятностью того, что единственный канал занят, равной ρ. В многоканальной системе эта заявка поступит в очередь лишь в случае, если заняты все K каналов. Указанное событие происходит с вероятностью B_K(ρ). Если принять во внимание, что средние значения очередей пропорциональны вероятностям поступающих в них заявок, то должно быть справедливо соотношение

${\eta }_K\left(\rho \right)=$ $\frac{\overline{q_{1K}\left(\rho \right)}}{\overline{q_1\left(\rho \right)}}=\frac{B_{1K}\left(\rho \right)}{B_1\left(\rho \right)}=\frac{B_{1K}\left(\rho \right)}{\rho }$.                                                            (9)

Коэффициент ƞ_K(ρ) показывает степень уменьшения размеров средней очереди, приходящейся на один канал многоканальной СМО с общей очередью, по сравнению с аналогичной одноканальной системой. Семейство кривых  ƞ_Kp(ρ) для пуассоновского потока показано на рис. 4.

 

Рис. 4. Семейство кривых ƞ_Kp(ρ) для пуассоновского потока

 

Из рис. 4 следует, что даже небольшое число каналов при пуассоновском входном потоке обеспечивает существенное уменьшение средней длины очереди по сравнению с одноканальной системой. С увеличением числа каналов (приборов обслуживания) для пуассоновских потоков наблюдается существенное уменьшение размеров очередей.

К сожалению, для потоков общего вида рассмотренная формула определения вероятности B(ρ) того, что в системе заняты все K каналов, неприменима, и утверждение об уменьшении среднего размера очереди с увеличением числа каналов справедливо далеко не всегда.

Анализ для потока с групповым прибытием

В качестве более адекватной модели видеотрафика рассмотрим поток с групповым прибытием, в котором согласно пуассоновскому потоку прибывают не отдельные заявки, а пачки заявок, для простоты одинакового размера M. Групповой поток является частным случаем пачечного потока [12–15], когда все заявки пачки поступают одновременно. Обработка каждой заявки из пачки требует одинакового времени одного из имеющихся идентичных K процессоров коммутатора (каналов обслуживания).

Сначала рассмотрим случай, когда K > M, причкм K / M = n ‒ целое число. Нетрудно видеть, что в такой системе занятие и освобождение каналов происходит только группами по M штук и такая СМО эквивалентна СМО M / D / n, рассмотренной выше. Если же K / M не целое и n₁ < K / M < n₂, где n₁ и n₂ – целые числа, то при эквивалентной нагрузке на один канал ρ точка, соответствующая средней очереди в системе, будет находиться между соответствующими кривыми на рис. 4 с абсциссой ρ и выигрыш в размере очереди по-прежнему будет иметь место.

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

Если же M > K и для простоты пусть M = K = k – целое, то нетрудно видеть, что в данной системе заявки забираются на обслуживание всегда группами по K штук и данная СМО эквивалентна одноканальной СМО с групповым прибытием, где пачки имеют постоянный размер k. Для такой системы уравнение (1) можно записать в виде

$q_i\left(\tau \right)=q_{i-1}\left(\tau \right)+m_i\left(\tau \right)-{\delta }_i\left(\tau \right)$,                                                              (10)

${\delta }_i\left(\tau \right)=\left\{\begin{array}{l}\mathrm{0,}\text{\hspace{0.33em}\hspace{0.33em}если\hspace{0.33em}}{q}_{i-1}\left(\tau \right)=m_i\left(\tau \right)=0;\\ 1\text{\hspace{0.33em}\hspace{0.33em}в\hspace{0.33em}противном\hspace{0.33em}случае.}\end{array}\right.$

Нетрудно увидеть некоторые особенностиδ_i (τ):

δ_i²(τ) = δ_i (τ); δ_i(τ) = m_i(τ); $\overline{{\delta }_i\left(\tau \right)}=\overline{m\left(\tau \right)}$, δ_i (τ)q_i-1(τ) = q_i-1(τ).

Заметим также, что для этой одноканальной системы в стационарном состоянии

$\overline{m_i\left(\tau \right)}=\rho =\lambda \tau k$.                                                                             (11)

Как и ранее, возведем в квадрат обе части (10) и после преобразований, аналогичных преобразованиям при выводе (3) и (4), получим их аналог в виде

$\overline{q\left(\tau \right)}=$$\frac{D_m\left(\tau \right)+2\text{Cov}\left(q_{i-1}\left(\tau \right);m_i\left(\tau \right)\right)-D_1\left(\tau \right)}{2\left(1-\overline{m_i\left(\tau \right)}\right)}$.

Вспомним еще, что в одноканальном случае

$D_1\left(\tau \right)=\overline{m_i\left(\tau \right)}\left(1-\overline{m_i\left(\tau \right)}\right)$,

и предыдущее выражение можно переписать в виде

$\overline{q\left(\tau \right)}=\frac{D_m\left(\tau \right)+2\text{Cov}\left(q_{i-1}\left(\tau \right);m_i\left(\tau \right)\right)}{2\left(1-\overline{m_i\left(\tau \right)}\right)}-\frac{m_i\left(\tau \right)}{2}$.                                             (11)

Это обобщение формулы Поллачека – Хинчина для любой одноканальной СМО со стационарным входным потоком и постоянным временем обслуживания τ [9, 16], а для рассматриваемого потока с пуассоновским приходом пачек постоянного размера k имеем

$\text{Cov}\left(q_{i-1}\left(\tau \right); m_i\left(\tau \right)\right)=0; D_m\left(\tau \right)=\lambda \tau k^2=\rho k$,

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

Никакого уменьшения очереди не наблюдается, при увеличении ρ характер роста очередей одинаков, а рост k еще линейно увеличивает среднюю очередь (при постоянном ρ). Так как эта система эквивалента многоканальной с пачечным прибытием, когда размер пачки превышает количество каналов, то можно заключить, что коль скоро M / K = k > 1, то независимо от количества каналов K уменьшение очереди в расчете на канал не происходит.

Заключение

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

About the authors

Likhttsinder Ya. Likhttsinder

Samara National Research University

Email: lixt@psuti.ru

Dr. Sci. (Techn.), Professor

Russian Federation, 34, Moskovskoe shosse, Samara, 443086

Alexander Yu. Privalov

Volga State University Telecommunications and Informatics

Author for correspondence.
Email: privalov.ayu@ssau.ru

Dr. Sci. (Techn.), Professor

Russian Federation, 23, L. Tolstogo str., Samara, 443100

References

Supplementary files