Об обслуживании в системе с входным гамма потоком

Пономарев Д.Ю.

Красноярский государственный технический университет

660074, Красноярск, ул. Киренского, 26

E-mail: kafaes@krasmail.ru

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

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

С развитием высокоскоростных сетей связи все большее влияние на качество обслуживания потоков информации оказывает свойство самоподобия, заключающееся на практике в том, что пакеты, при высокой скорости их движения по сети, поступают на узел не по отдельности, а целой пачкой, что приводит, из-за ограниченности буфера, к отсутствию мест ожидания, и, следовательно, к потерям. Расчет объемов буфера по классическим методикам приводит к существенно заниженному значению. Для того чтобы обеспечить заданное качество обслуживания необходимо определить характеристики самоподобных потоков пакетов в современных сетях связи. Основное проявление свойства самоподобия заключается в большой пачечности (берстности) или большой дисперсии процесса. В [1] отмечается возможность использования гамма распределения в качестве модели потока с «тяжелым» хвостом. Поэтому возникает естественная предпосылка по исследованию характеристик системы массового обслуживания гамма потока.

Из [2] известно, что для системы $G/M/1$ вероятность того, что вновь поступившее требование застанет в системе $n$ требований, определяется, как: $r_n = \left( {1 - \sigma } \right)\sigma ^n$, где $\sigma$ - единственное решение уравнения $h\left(\mu-\mu\sigma\right)=\sigma$ ($h$ - преобразование Лапласа-Стильтьеса функции распределения интервалов между вызовами). Следует отметить, что для системы массового обслуживания (СМО) с пуассоновским входным потоком данная вероятность $r_n$ равна вероятности нахождения в системе $n$ требований: $p_n = r_n $ (будем считать, что и для гамма потока это выполняется), для некоторых других систем вероятность $p_n$ будет определяться, как $p_n=\rho r_{n - 1}=\rho\left({1 - \sigma }\right)\sigma ^n $.


\begin{displaymath}
f(t) = {{k\lambda } \over {\Gamma(k)}}\left( {k\lambda t} \right)^{k - 1} e^{ - k\lambda t} ,
\end{displaymath}

где $\Gamma(k) = \int\limits_0^\infty {t^{k - 1} e^{ - t} dt}$

ПЛС для такого распределения имеет вид: $h\left( s \right) = \left( {\displaystyle{s \over {k\lambda }} + 1} \right)^{ - k}$

Искомое уравнение получим в виде: $h\left( {\mu - \mu \sigma } \right) = \left( {\displaystyle{{\mu - \mu \sigma } \over {k\lambda }} + 1} \right)^{ - k}$. Откуда,  $\left( {\displaystyle{{\mu - \mu \sigma } \over {k\lambda }} + 1} \right)^{ - k} = \sigma $. Следовательно, $\left( {\displaystyle{{1 - \sigma } \over {k\rho }} + 1} \right)^{ - k}=~\sigma$.

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

\begin{displaymath}\left( {\displaystyle{{1 - \sigma + k\rho } \over {k\rho }}} \right)^{ - k} =~\sigma\end{displaymath}

Используя свойство степени, искомое уравнение имеет вид:

\begin{displaymath}\left( {\displaystyle{{k\rho } \over {1 - \sigma + k\rho }}} \right)^k =~\sigma \end{displaymath}

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


$\displaystyle{{k\rho } \over {1 - \sigma + k\rho }} - \sigma ^{{1 \over k}} = 0$ $\left( {\displaystyle{{k\rho } \over {1 - \sigma + k\rho }}} \right)^k - \sigma = 0$
$k\rho - \displaystyle\sigma ^{{1 \over k}} \left( {1 - \sigma + k\rho } \right) = 0$ $\left( {k\rho } \right)^k - \sigma \left( {1 - \sigma + k\rho } \right)^k = 0$


Для порядка распределения $k=2$ (в общем классическое распределение $E_2$) возьмем второе выражение. Составляем уравнение $\left( {2\rho } \right)^2 - \sigma \left( {1 - \sigma + 2\rho } \right)^2 = 0$. Откуда, производя необходимые вычисления, уравнение приобретает вид: $\left( {2\rho } \right)^2 \left( {1 - \sigma } \right) - \sigma \left( {1 - \sigma } \right)\left( {1 - \sigma + 4\rho } \right) = 0$. Следовательно, $\left( {1 - \sigma } \right)\left[ {\left( {2\rho } \right)^2 - \left( {\sigma - \sigma ^2 + 4\sigma \rho } \right)} \right] = 0$. Окончательно, получаем уравнение в виде: $\left( {1 - \sigma } \right)\left[ {\sigma ^2 - \sigma \left( {1 + 4\rho } \right) + \left( {2\rho } \right)^2 } \right] = 0$.

Корни данного уравнения равны:

\begin{displaymath}\sigma = 1,\sigma _{1,2} = \displaystyle{{\left( {1 + 4\rho }...
...{\left( {1 + 4\rho }
\right) \pm \sqrt {1 + 8\rho } } \over 2}\end{displaymath}

В соответствии с [2], первый корень не удовлетворяет условию: $0<\sigma<1$. Для определения соответствия данному условию других корней определим следующее:

для первого корня найдем пределы: $\mathop {\lim }\limits_{\rho \to 1} \sigma _1 = \displaystyle{{5 + \sqrt 9 } \over 2} > 1$ и $\mathop {\lim }\limits_{\rho \to 0} \sigma _1 = 1$, следовательно $\sigma _1 \ge 1$.

для второго корня: $\mathop {\lim }\limits_{\rho \to 1} \sigma _2 = \displaystyle{{5 - \sqrt 9 } \over 2} = 1$ и $\mathop {\lim }\limits_{\rho \to 0} \sigma _2 = 0$, следовательно, пределы изменения корня $0 \le \sigma _2 \le 1$.

Исходя из всего вышесказанного, найденный корень равен

\begin{displaymath}\sigma = \displaystyle{{\left( {1 + 4\rho } \right) - \sqrt {1 + 8\rho } } \over 2}\end{displaymath}

Находим вероятность нахождения в системе k требований:

\begin{displaymath}
p_k = \left( {1 - {{\left( {1 + 4\rho } \right) - \sqrt {1 +...
... + 4\rho } \right) - \sqrt {1 + 8\rho } } \over 2}} \right)^k
\end{displaymath}

Определим, теперь среднее число требований в системе в общем случае:


\begin{displaymath}
\bar N = \sum\limits_{k = 1}^\infty {kp_k } =
\left( {1 - \...
... \right)\sigma \sum\limits_{k = 1}^\infty {k\sigma ^{k - 1} }=
\end{displaymath}


\begin{displaymath}
= \left( {1 - \sigma } \right)\sigma {\partial \over {\parti...
... } \right)\sigma
{1 \over {\left( {1 - \sigma } \right)^2 }}
\end{displaymath}

Откуда, получаем:


\begin{displaymath}
\bar N = {\sigma \over {1 - \sigma }}
\end{displaymath}

Следовательно, для найденного ранее корня уравнения в СМО вида $\Gamma_2/M/1$ средняя очередь будет равна:

\begin{displaymath}
\bar N = {{1 + 4\rho - \sqrt {1 + 8\rho } } \over {2 - \left( {1 + 4\rho - \sqrt {1 + 8\rho } } \right)}}
\end{displaymath}

Проверим возможность использования полученных формул при $k=1$ (СМО $M/M/1, \Gamma_1/M/1, E_1/M/1$). Воспользовавшись второй формой уравнения, получаем:

\begin{displaymath}
\left( {k\rho } \right)^k - \sigma \left( {1 - \sigma + k\rho } \right)^k = 0
\end{displaymath}


\begin{displaymath}
\rho - \sigma \left( {1 - \sigma + k\rho } \right) = 0\end{displaymath}


\begin{displaymath}\rho \left( {1 - \sigma } \right) - \sigma \left( {1 - \sigma } \right) = 0\end{displaymath}


\begin{displaymath}\left( {1 - \sigma } \right)\left( {\rho - \sigma } \right) = 0\end{displaymath}

Первый корень не удовлетворяет условию $0<\sigma<1$. Второй корень $\sigma=\rho$ приводит к классическому выражению $r_k = \left( {1 - \rho } \right)\rho ^k = p_k $. Следовательно, средняя очередь равна: $\bar N = \displaystyle{\rho \over {1 - \rho }}$.

Из этого, можно сделать вывод о возможности использования формул для частных решений для СМО $\Gamma_k/M/1$. Однако, более интересен случай, когда порядок $k$ лежит в пределах $0<k<1$. Например, для $k=0.5$ возьмем первую форму уравнения:


\begin{displaymath}k\rho - \sigma ^{{1 \over k}} \left( {1 - \sigma + k\rho } \right) = 0\end{displaymath}


\begin{displaymath}{\rho \over 2} - \sigma ^2 \left( {1 - \sigma + {\rho \over 2}} \right) = 0\end{displaymath}


\begin{displaymath}{\rho \over 2}\left( {1 - \sigma ^2 } \right) - \sigma ^2 \left( {1 - \sigma } \right) = 0\end{displaymath}


\begin{displaymath}\left( {1 - \sigma } \right)\left( {{\rho \over 2} + {\rho \over 2}\sigma - \sigma ^2 } \right) = 0\end{displaymath}

Решение дает три корня: $\sigma=1$, и два корня уравнения $\sigma ^2 - {\rho \over 2}\sigma - {\rho \over 2} = 0$, которые можно получить в следующем виде:

\begin{displaymath}
\sigma _{1,2} = {{\displaystyle{\rho \over 2} \pm \sqrt {\le...
...\over 4} \pm \sqrt {{{\rho ^2 } \over {16}} + {\rho \over 2}}
\end{displaymath}

При исследовании пределов изменений данных корней:


$\mathop {\lim }\limits_{\rho \to 1} \sigma _1 = \displaystyle{{1 \over 4} + {3 \over 4}} = 1$   $\mathop {\lim }\limits_{\rho \to 1} \sigma _2 = \displaystyle{{1 \over 4} - {3 \over 4}} < 0$
$\mathop {\lim }\limits_{\rho \to 0} \sigma _1 = 0$   $\mathop {\lim }\limits_{\rho \to 0} \sigma _2 = 0$
$0 \le \sigma _1 \le 1$   $\sigma _2 \le 0$


получаем, что всем условиям удовлетворяет корень уравнения:

\begin{displaymath}
\sigma = {\rho \over 4} + \sqrt {{{\rho ^2 } \over {16}} + {\rho \over 2}}
\end{displaymath}

Отсюда, для вероятности нахождения в системе k требований получим:

\begin{displaymath}
p_k = \left( {1 - {\rho \over 4} - \sqrt {{{\rho ^2 } \over ...
... \sqrt {{{\rho ^2 } \over {16}} + {\rho \over 2}} } \right)^k
\end{displaymath}

Среднее число требований в системе можно представить аналогично

\begin{displaymath}
\bar N = \displaystyle{\displaystyle{{\rho \over 4} + \sqrt ...
...\over 4} - \sqrt {{{\rho ^2 } \over {16}} + {\rho \over 2}} }}
\end{displaymath}

На рис. 1-2 представлены результаты расчетов, проведенных по формулам 2-6.

Image 1

а) $\rho=0.3$ б) $\rho=0.9$

Рисунок 1 – Изменение вероятности нахождения в системе n требований при различных значениях загрузки (пунктир – $\Gamma_2/M/1$, сплошная – $\Gamma_{0.5}/M/1$ ).

Image 2

Рисунок 2 – Зависимость средней очереди от загрузки (пунктир – $\Gamma_2/M/1$, сплошная – $\Gamma_{0.5}/M/1$).

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

- общий характер зависимостей не меняется при изменении порядка распределения;

- при обслуживании потока второго порядка вероятность занятия мест с меньшим номером намного больше, чем при обслуживании потока с порядком распределения $k=0.5$, т.е. при изменении порядка в меньшую сторону распределение заявок становится более равномерно, но занимается больше мест ожидания;

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

Продолжим исследование систем с гамма потоком на входе, но с ограниченным буфером, для чего воспользуемся методом, предложенным в [3]. Ограниченность буфера будем учитывать через условие нормировки (N – размер буфера): $\displaystyle{\sum\limits_{k = 0}^{N + 1}} {p_k } = 1$. Cледовательно, можно записать $\displaystyle{\sum\limits_{k = 0}^{N + 1}} {p_k } = \displaystyle{\sum\limits_{k = 0}^{N + 1}} {\left( {1 - \sigma } \right)\sigma ^k K} = 1$. Тогда, коэффициент $K$ можно найти, как:

\begin{displaymath}
K = \left[ {\sum\limits_{k = 0}^{N + 1} {\left( {1 - \sigma ...
...\sigma ^k } } \right]^{ - 1} = {1 \over {1 - \sigma ^{N + 2} }}\end{displaymath}

Тогда, искомые вероятности будут определяться, как:

\begin{displaymath}
p_k = {{1 - \sigma } \over {1 - \sigma ^{N + 2} }}\sigma ^k
\end{displaymath}

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

для $k=2$ : $
p_k = \displaystyle{{2^{N + 1} \left( {1 - 4\rho + \sqrt {1 + 8\rho } } \right...
...ft( {{{\left( {1 + 4\rho } \right) - \sqrt {1 + 8\rho } } \over 2}} \right)^k
$ для $k=1$: $p_k = \displaystyle{{1 - \rho } \over {1 - \rho ^{N + 2} }}\rho ^k $ (классический результат, подтверждается [2,3]);

для $k=0.5$: $
p_k = \displaystyle{{1 - {\rho \over 4} - \sqrt {{{\rho ^2 } \over {16}} + {\r...
...{\rho \over 4} + \sqrt {{{\rho ^2 } \over {16}} + {\rho \over 2}} } \right)^k
$.

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

\begin{displaymath}
\bar N = \sum\limits_{k = 1}^N {kp_k } = \sum\limits_{k = 1}...
...
\over {\partial \sigma }}\sum\limits_{k = 1}^N {\sigma ^k } =
\end{displaymath}


\begin{displaymath}
= {{1 - \sigma } \over {1 - \sigma ^{N + 2} }}\sigma {\parti...
... N\sigma ^{N + 1} }
\over {\left( {1 - \sigma } \right)^2 }}
\end{displaymath}

Окончательно:

\begin{displaymath}
\bar N = {\sigma \over {1 - \sigma ^{N + 2} }}{{1 - \left( {N + 1} \right)\sigma ^N + N\sigma ^{N + 1} } \over {1 - \sigma }}
\end{displaymath}

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

для $k=2$ :

\begin{displaymath}
\bar N = {{\left( {2^{N + 1} - 2\left( {N + 1} \right)\left(...
...}
\over {\left( {1 + 4\rho - \sqrt {1 + 8\rho } } \right)}}}}
\end{displaymath}

для $k=1$:

\begin{displaymath}
\bar N = {\rho \over {1 - \rho ^{N + 2} }}{{1 - \left( {N + 1} \right)\rho ^N + N\rho ^{N + 1} } \over {1 - \rho }}
\end{displaymath}

(известный результат [3]);

для $k=0.5$:

\begin{displaymath}
\bar N = {\displaystyle{{\rho \over 4} + \sqrt {{{\rho ^2 } ...
...\over 4} - \sqrt {{{\rho ^2 } \over {16}} + {\rho \over 2}} }}
\end{displaymath}

Image 3

а) $\rho=0.3$ б) $\rho=0.9$

Рисунок 3 – Изменение вероятности нахождения в системе $n$ требований при различных значениях загрузки (пунктир – $\Gamma_2/M/1/N$, сплошная – $\Gamma_{0.5}/M/1/N$ ).

Image 4

Рисунок 4 – Зависимость средней очереди от загрузки при размере буфера $N=15$ (точками – $M/M/1/N$).

Анализируя графики, представленные на рис. 3-4, можно отметить, что характер зависимостей остался таким же, как и в случае с неограниченным буфером. Однако, изменились количественные параметры, что для буферов малой размерности является достаточно заметным. Кроме того, изменение порядка распределения также проявляется и здесь, но для средней очереди влияние может быть недостаточно проявляющееся в количественном определении. Более интересным становится вопрос о вероятности потерь в СМО с ограниченным буфером. Определять данную характеристику будем согласно [2,3,4], тогда можно записать:

для $k=2$ :

\begin{displaymath}
p_{} = {{2^{N + 1} \left( {1 - 4\rho + \sqrt {1 + 8\rho } } ...
...ho } \right) - \sqrt {1 + 8\rho } } \over 2}} \right)^{N + 1}
\end{displaymath}

для $k=0.5$ :

\begin{displaymath}
p_{} = {\displaystyle{1 - {\rho \over 4} - \sqrt {{{\rho ^2 ...
... {{{\rho ^2 } \over {16}} + {\rho \over 2}} } \right)^{N + 1}
\end{displaymath}

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

Image 5

Рисунок 5 –Зависимость вероятности потерь от загрузки в СМО $\Gamma_k/M/1/15$.