Spectral decomposition for a QS based delay model with Erlang and hyperexponential distributions

Full Text

Введение

В данной работе использован метод спектрального разложения решения интегрального уравнения Линдли для систем массового обслуживания типа G/G/1 для нахождения среднего времени ожидания требований в очереди. Наиболее доступно для исследователей этот метод продемонстрирован в [1]. Важным моментом данного метода является конструирование спектрального разложения для рассматриваемой системы, а затем – нахождение нулей и полюсов этого разложения.

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

Настоящая статья посвящена анализу СМО E₂/H₂/1 по символике Кендалла с эрланговским и гиперэкспоненциальным входными распределениями второго порядка и является продолжением исследований [3–6]. В теории массового обслуживания исследования систем G/G/1 актуальны в связи с тем, что они активно используются в современной теории телетрафика при моделировании систем передачи данных различного назначения, к тому же нельзя получить решения для таких систем в конечном виде для общего случая.

В работе также использованы приемы и способы аппроксимации законов распределений методом моментов теории вероятностей [7–12]. Схожие результаты современных исследований по системам массового обслуживания приведены в работах [13–15].

Постановка и решение задачи

В работе ставится задача вывода решения по средней задержке требований в очереди в системе E₂/H₂/1 с эрланговским и гиперэкспоненциальным входными распределениями второго порядка как основной характеристики любой СМО.

Для системы E₂/H₂/1 законы распределения интервалов входного потока и времени обслуживания задаются функциями плотности вида:

$a\left(t\right)=4{\lambda }^{2}t{e}^{-2\lambda t},$ (1)

$b\left(t\right)=q{\mu }_1{e}^{-{\mu }_{1}t}+\left(1-q\right){\mu }_2{e}^{-{\mu }_{2}t}.$ (2)

Запишем преобразования Лапласа функций (1) и (2):

$A^{*}\left(s\right)={\left(\frac{2\lambda }{2\lambda +s}\right)}^2,$

$B^{*}\left(s\right)=q\frac{{\mu }_1}{s+{\mu }_1}+\left(1-q\right)\frac{{\mu }_2}{s+{\mu }_2}.$

Выражение для спектрального разложения решения интегрального уравнения Линдли для системы E₂/H₂/1 примет вид:

$A^{*}(-s)\cdot B^{*}\left(s\right)-1= \frac{{\psi }_{+}\left(s\right)}{{\psi }_{-}\left(s\right)}={\left(\frac{2\lambda }{2\lambda -s}\right)}^2\times$ (3)

$\begin{array}{l}\times \left[q\frac{{\mu }_1}{{\mu }_1+s}+\left(1-q\right)\frac{{\mu }_2}{{\mu }_2+s}\right]-1=\\ =\frac{-s(s+s_1)(s+s_2)(s-s_3)}{{(2\lambda -s)}^2(s+{\mu }_1)(s+{\mu }_2)},\end{array}$

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

$-s(s^3-c_2{s}^2-$$c_{1}s-c_0)$ с коэффициентами 

$c_2=4\lambda -{\mu }_1-{\mu }_2,$ $c_1=4\lambda ({\mu }_1+{\mu }_2-\lambda )-{\mu }_1{\mu }_2,$

$c_0=4{\lambda }^{2}q({\mu }_1-{\mu }_2)+4\lambda {\mu }_1({\mu }_2-\lambda )].$

В свою очередь кубический многочлен

$s^3-c_2{s}^2-c_{1}s-c_0$ (4)

с такими коэффициентами имеет два действительных отрицательных корня $-s_1,$ $-s_2$ и один положительный корень $s_3$ в случае стационарного режима, т. е. когда $0<\rho =$ ${\overline{\tau }}_{\mu }\text{/}{\overline{\tau }}_{\lambda }<\text{1,}$ где $\rho \text{,}$ ${\overline{\tau }}_{\lambda },$ ${\overline{\tau }}_{\mu }$ соответственно коэффициент загрузки, средний интервал поступлений и среднее время обслуживания в системе.

Исходя из правил построения функций ${\psi }_{+}\left(s\right)$ и ${\psi }_{-}\left(s\right),$ из выражения (3) за функцию ${\psi }_{+}\left(s\right)$ примем

${\psi }_{+}\left(s\right)=\frac{s\left(s+s_1\right)\left(s+s_2\right)}{\left(s+{\mu }_1\right)(s+{\mu }_2)},$

т. к. нули многочлена (4) $s=\mathrm{0,}$ $-s_1,$ $-s_2$ и полюсы $s=-{\mu }_1,$ $s=-{\mu }_2$ лежат в области $\text{Re}\left(s\right)\le 0.$ За функцию ${\psi }_{-}\left(s\right)$ из выражения (3) примем

${\psi }_{-}\left(s\right)=-\frac{{\text{(2}\lambda -s)}^2}{(s-s_3)},$

т. к. ее нуль $s=2\lambda$ и полюс $s=s_3$ лежат в области $\text{Re}\left(s\right)\ge D.$

На рис. отображены нули и полюса отношения ${\psi }_{+}\left(s\right)/$${\psi }_{-}\left(s\right)$ на комплексной s – плоскости для исключения ошибок построения спектрального разложения. На рис. полюсы отмечены крестиками, а нули – кружками.

 

Рис. Нули и полюсы функции ${\mathit{\psi }}_{\mathbf{+}}\left(s\right)\mathbf{/}{\mathit{\psi }}_{\mathbf{-}}\left(s\right)$ для системы E2/H2/1

Fig. Zeros and poles ${\mathit{\psi }}_{\mathbf{+}}\left(s\right)\mathbf{/}{\mathit{\psi }}_{\mathbf{-}}\left(s\right)$ function for the E₂/H₂/1 system

 

Необходимая для получения решения константа равна 

$К=\underset{s\to 0}{\lim }\frac{{\psi }_{+}\left(s\right)}{s}=\frac{s_1{s}_2}{{\text{μ}}_1{\mu }_2}.$

Далее строим преобразование Лапласа функции распределения вероятностей времени ожидания

${\Phi }_{+}\left(s\right)=\frac{K}{{\psi }_{+}\left(s\right)}=\frac{s_1{s}_2\left(s+{\mu }_1\right)\left(s+{\mu }_2\right)}{s\left(s+s_1\right)\left(s+s_2\right){\mu }_1{\mu }_2}.$

Откуда следует, что преобразование Лапласа функции плотности времени ожидания в системе E₂/H₂/1:

$W^{*}\left(s\right)=s\cdot {\Phi }_{+}\left(s\right)=\frac{s_1{s}_2\left(s+{\mu }_1\right)\left(s+{\mu }_2\right)}{\left(s+s_1\right)\left(s+s_2\right){\mu }_1{\mu }_2}.$ (5)

Производная от функции $W^{*}\left(s\right)$ со знаком минус в т. $s=0$ даст среднее время ожидания:

$\begin{array}{l}-\frac{d{W}^{*}\left(s\right)}{ds}{|}_{s=0}=-\frac{s_1{s}_2\left(s+{\mu }_1\right)\left(s+{\mu }_2\right)}{\left(s+s_1\right)\left(s+s_2\right){\mu }_1{\mu }_2}{|}_{s=0}=\\ =\frac{1}{s_1}+\frac{1}{s_2}-\frac{1}{{\text{μ}}_1}-\frac{1}{{\mu }_2}.\end{array}$

Окончательно среднее время ожидания в системе E₂/H₂/1 может быть определено из выражения

$\overline{W}=\frac{1}{s_1}+\frac{1}{s_2}-\frac{1}{{\text{μ}}_1}-\frac{1}{{\mu }_2},$ (6)

где $s_1,$ $s_2$ абсолютные значения отрицательных корней $-s_1,$ $-s_2$ кубического многочлена (4) с приведенными выше коэффициентами, а ${\mu }_1,$ ${\mu }_2$ – параметры распределения (2). Таким образом, для среднего времени ожидания в СМО E₂/H₂/1 получено решение в замкнутой форме (6). Для того, чтобы им воспользоваться в практических расчетах, необходимо определить неизвестные параметры распределений (1) и (2) через их числовые характеристики.

Для распределения (1) запишем выражения для моментов: среднего интервала поступлений, второго начального момента, а через него для коэффициента вариации

${\overline{\tau }}_{\lambda }=\frac{1}{\lambda },$ $\overline{{\tau }_{\lambda }^2}=\frac{3}{2{\lambda }^2} ,$ $c_{\lambda }=\frac{1}{\sqrt{2}}.$

Для распределения (2) воспользуемся свойством преобразования Лапласа воспроизведения моментов и запишем два начальных момента для распределения (2):

${\overline{\tau }}_{\mu }=\frac{q}{{\mu }_1}+\frac{\left(1-q\right)}{{\mu }_2},$ $\overline{{\tau }_{\mu }^2}=\frac{2q}{{\mu }_1^2}+\frac{2\left(1-q\right)}{{\mu }_2^2}.$ (7)

При аппроксимации с использованием первых двух моментов неизвестные параметры распределения (2) ${\mu }_{\text{1}},$ ${\mu }_{\text{2}},$ q определяются с помощью следующих выражений [3]:

${\mu }_1=\frac{2q}{{\overline{\tau }}_{\mu }},$ ${\mu }_2=\frac{2(1-q)}{{\overline{\tau }}_{\mu }},$ (8)

$q=\frac{1}{2}\left(1\pm \sqrt{\frac{c_{\mu }^2-1}{c_{\mu }^2+1}}\right),$

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

$c_{\mu }^2=\frac{(1-q^2){\mu }_1^2-2q(1-q){\mu }_1{\mu }_2+q(2-q){\mu }_2^2}{{\left[\right(1-q){\mu }_1+q{\mu }_2]}^2}.$ (9)

Из выражения для вероятности q следует, что коэффициент вариации $c_{\mu }\ge 1.$ При аппроксимации закона распределения с использованием первых трех моментов для нахождения параметров распределения (2) необходимо в пакете Mathcad решить систему трех уравнений, полученных методом моментов. При этом необходимым и достаточным условием существования решения является выполнение условия: $\overline{{\tau }_{\mu }^3}\cdot \overline{{\tau }_{\mu }}\ge \mathrm{1,5}\overline{{\tau }_{\mu }^2}$ [8].

Такой подход к использованию метода спектрального разложения позволяет определить не только среднюю задержку в очереди из (5), но и моменты высших порядков времени ожидания. Вторая производная от функции (5) при $s=0$ дает второй начальный момент времени ожидания. С учетом определения вариации задержки – джиттера в телекоммуникациях как разброс времени ожидания от его среднего значения, тем самым получим возможность определения джиттера через дисперсию времени ожидания.

Таким образом, гиперэкспоненциальный закон распределения второго порядка может определяться полностью двумя первыми моментами и перекрывать весь диапазон изменения коэффициента вариации $[\mathrm{1,}\infty ).$ Величины ${\overline{\tau }}_{\lambda }, {\overline{\tau }}_{\mu }, c_{\lambda }=1/\sqrt{2}, c_{\mu }$ будем считать входными параметрами для расчета pсреднего времени ожидания для системы E₂/H₂$s^3-c_2{s}^2-c_{1}s-c_0$/1 с использованием выражения (6). Тогда алгоритм расчета сведется к последовательному определению параметров распределения (2) из выражений (8) и к нахождению нужных корней многочлена с приведенными выше коэффициентами, а затем к использованию расчетной формулы (6).

Результаты вычислительных экспериментов

Ниже в таблице приведены данные расчетов для системы E₂/H₂/1 для различных случаев нагрузки (малой, средней и высокой) $\rho =\mathrm{0,1};$ 0,5; 0,9 при $c_{\mu }=\mathrm{1,}$ 2, 4, 8. Коэффициент загрузки в данном случае определяется отношением средних интервалов $\rho ={\overline{\tau }}_{\mu }/{\overline{\tau }}_{\lambda }.$ Расчеты, приведенные в таблице проведены для удобства для случая нормированного времени обслуживания ${\overline{\tau }}_{\mu }=1.$

 

Таблица. Результаты экспериментов для СМО E₂/H₂/1

Table. Experimental results for QS E₂/H₂/1

Входные параметры $\rho , c_{\mu }$	Среднее время ожидания для системы E2/H2/1
$\rho$	$c_{\mu }=1$	$c_{\mu }=2$	$c_{\mu }=4$	$c_{\mu }=8$
0,1	0,030	0,160	0,795	3,448
0,5	0,618	2,094	8,082	32,079
0,9	6,588	20,072	74,065	290,063

 

Заключение

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

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

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

About the authors

Veniamin N. Tarasov

Povolzhskiy State University of Telecommunications and Informatics

Author for correspondence.
Email: tarasov-vn@psuti.ru

Doctor of Technical Sciences, Professor, Head of the Department of Software and Management in Technical Systems

Russian Federation, 23, L. Tolstoy Street, Samara, 443010

References

Supplementary files