Mathematical delay model based on QS with hyperexponential and Erlang distributions

Full Text

Введение

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

$\begin{array}{l}{F}^{*}\left(s\right)=\frac{{\beta }^{-\alpha }}{\Gamma \left(\alpha \right)}\underset{0}{\overset{+\infty }{\int }}{e}^{-st}{t}^{\alpha -1}{e}^{-t/\beta }dt=\\ =\frac{{\beta }^{-\alpha }}{\Gamma \left(\alpha \right)}{\left(\frac{\beta }{\beta s+1}\right)}^{\alpha -1}\Gamma \left(\alpha \right)=\frac{1}{{(\beta s+1)}^{\alpha -1}}\end{array}$

и этот закон распределения в теории массового обслуживания можно использовать только в частных случаях при целочисленных значениях $\alpha \ge 2.$ В конечном итоге это приводит нас к известному распределению Эрланга.

В качестве основного метода решения задачи использован метод спектрального разложения решения интегрального уравнения Линдли [5; 6], а вспомогательного – приемы аппроксимации законов распределений методом моментов теории вероятностей [7–9]. Вычислительные эксперименты по полученным в работе аналитическим результатам подтверждаются данными имитации [10–12]. Схожие результаты современных исследований по системам массового обслуживания приведены в работах [13–16].

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

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

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

$a\left(t\right)=p{\lambda }_1{e}^{-{\lambda }_{1}t}+\left(1-p\right){\lambda }_2{e}^{-{\lambda }_{2}t},$ (1)

$b\left(t\right)=4{\mu }^{2}t{e}^{-2\mu t}.$ (2)

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

$A^{*}\left(s\right)=p\frac{{\lambda }_1}{s+{\lambda }_1}+\left(1-p\right)\frac{{\lambda }_2}{s+{\lambda }_2},$

$B^{*}\left(s\right)={\left(\frac{2\mu }{2\mu +s}\right)}^2.$

Тогда выражение $A^{*}\left(-s\right)B^{*}\left(s\right)-1=$${\psi }_{+}\left(s\right)/{\psi }_{-}\left(s\right),$ где $A^{*}\left(s\right),$ $B^{*}\left(s\right)$ – преобразования Лапласа функций плотности (1), (2), а ${\phi }_{+}\left(s\right),$ ${\phi }_{-}\left(s\right)$ – некоторые дробно-рациональные функции s, для спектрального разложения решения интегрального уравнения Линдли для системы H₂/E₂/1 примет вид:

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

т. к. многочлен 4-й степени в числителе этого выражения можно представить в виде разложения $-s(s^3+c_2{s}^2+$$c_{1}s+c_0)$ с коэффициентами $c_2=4\mu -$${\lambda }_1-{\lambda }_2,$ $c_1=4\mu (\mu -$${\lambda }_1-{\lambda }_2)+{\lambda }_1{\lambda }_2,$ $c_0=4\mu [{\lambda }_1{\lambda }_2+$$\mu ({\lambda }_{1}p-{\lambda }_1-{\lambda }_{2}p)].$ В свою очередь кубический многочлен $s^3+c_2{s}^2+$ $c_{1}s+c_0$ с такими коэффициентами в стационарном режиме функционирования СМО при загрузке $\rho ={\overline{\tau }}_{\mu }/{\overline{\tau }}_{\lambda }<1$ имеет два действительных отрицательных корня $-s_1,$ $-s_2$ и один положительный корень $s_3.$

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

$\frac{{\psi }_{+}\left(s\right)}{{\psi }_{-}\left(s\right)}=\frac{-s(s+s_1)(s+s_2)(s-s_3)}{({\lambda }_1-s)({\lambda }_2-s){(2\mu +s)}^2}.$ (3)

Поэтому с учетом специальных условий [5] за функцию ${\psi }_{+}\left(s\right)$ примем

${\psi }_{+}\left(s\right)=s(s+s_1)(s+s_2)/{(s+2\mu )}^2,$

т. к. нули кубического многочлена $s=\mathrm{0,}$ $s=-s_1,$ $s=-s_2$ и полюс $s=-2\text{\hspace{0.17em}μ}$ лежат в области $\text{Re}\left(s\right)\le \mathrm{0,}$ а за функцию

${\psi }_{-}\left(s\right)=-({\lambda }_1-s)({\lambda }_2-s)/(s-s_3).$

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

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

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

Далее по методике спектрального разложения найдем константу K:

$K=\underset{\left|s\right|\to 0}{\lim }\frac{{\psi }_{+}\left(s\right)}{s}=\underset{\left|s\right|\to 0}{\lim }\frac{(s+s_1)(s+s_2)}{{(s+2\text{μ)}}^2}=\frac{s_1{s}_2}{{\text{4μ}}^2}.$

Построим функцию ${\Phi }_{+}\left(s\right)=K/{\psi }_{+}\left(s\right),$ через которую найдем преобразование Лапласа функции плотности задержки:

$W^{*}\left(s\right)=s{\Phi }_{+}\left(s\right)=\frac{s_1{s}_2{\left(s+2\text{μ}\right)}^2}{{\text{4μ}}^2(s+s_1)(s+s_2)}.$

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

$W^{*}\left(s\right)=\frac{s_1{s}_2{\left(s+2\text{μ}\right)}^2}{{\text{4μ}}^2(s+s_1)(s+s_2)}.$ (4)

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

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

Тогда средняя задержка в очереди для системы H₂/E₂/1 будет равна:

$\overline{W}=\frac{1}{s_1}+\frac{1}{s_2}-\frac{1}{\text{μ}},$ (5)

где $s_1,$ $s_2$ абсолютные значения отрицательных корней $-s_1$ и $-s_2$ кубического многочлена $s^3+c_2{s}^2+$$c_{1}s+c_0$ с приведенными выше коэффициентами. Таким образом, средняя задержка для системы H₂/E₂/1 однозначно определена в виде замкнутой формы (5).

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

Для практического применения расчетной формулы (5) необходимо определить числовые характеристики распределений (1) H₂ и (2) E₂. Для этого воспользуемся свойством преобразования Лапласа воспроизведения моментов и запишем начальные моменты до третьего порядка для распределения (1):

$\begin{array}{l}{\overline{\tau }}_{\lambda }=\frac{p}{{\lambda }_1}+\frac{\left(1-p\right)}{{\lambda }_2},\overline{{\tau }_{\lambda }^2}=\frac{2p}{{\lambda }_1^2}+\frac{2\left(1-p\right)}{{\lambda }_2^2},\\ \overline{{\tau }_{\lambda }^3}=\frac{6p}{{\lambda }_1^3}+\frac{6\left(1-p\right)}{{\lambda }_2^3}.\end{array}$ (6)

При аппроксимации с использованием первых двух моментов неизвестные параметры распределения (1) ${\lambda }_1, {\lambda }_2, p$   определяются с помощью следующих выражений [10]:

$\begin{array}{l}{\lambda }_1=2p/{\overline{\tau }}_{\lambda },{\lambda }_2=2(1-p)/{\overline{\tau }}_{\lambda },\\ p=\frac{1}{2}[1\pm \sqrt{(c_{\lambda }^2-1)/(c_{\lambda }^2+1)}].\end{array}$(7)

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

Для распределения (2) имеем:

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

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

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

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

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

Table. Results of experiments for QS H₂/E₂/1 in comparison with H₂/M/1

Заключение

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

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

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

About the authors

Veniamin N. Tarasov

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

professor, head of the Department of Software and Management in Technical Systems

References

Supplementary files

Supplementary Files

Action

1. JATS XML

Download

2. Рис. Нули и полюсы функции для системы H2/E2/1

Download (22KB)

Indexing metadata