Mathematical model of delay based on a system with gamma distribution

Full Text

Введение

Настоящая статья посвящена анализу системы массового обслуживания (СМО), образованной двумя потоками с функциями плотности распределения Эрланга второго порядка, для которого в открытом доступе не обнаружены результаты по средней задержке требований в очереди, являющегося главной характеристикой для любых СМО. В исследовании систем G/G/1 важную роль играет метод спектрального разложения решения интегрального уравнения Линдли (ИУЛ) и большинство результатов в теории массового обслуживания получены именно с помощью данного метода. Используемый в работе метод спектрального разложения решения интегрального уравнения Линдли впервые подробно представлен в классике теории массового обслуживания [1], а впоследствии применялся во многих работах, включая [2–4]. Другой подход к решению ИУЛ использован в [5]. Здесь вместо термина «спектральное разложение» использована факторизация, а вместо функций ${\psi }_{+}\left(s\right)$ и ${\psi }_{-}\left(s\right)$ – компоненты факторизации ${\omega }_{+}\left(z,t\right)$ и ${\omega }_{-}\left(z,t\right)$ функции $1-z\chi \left(t\right).$

Такой подход для получения конечных результатов для рассматриваемых систем менее удобен, чем подход, описанный в [1] и проиллюстрированный многочисленными примерами для лучшего понимания. Метод спектрального разложения решения ИУЛ также применен для исследования систем с гиперэкспоненциальными входными распределениями в работах [6–8]. Результаты современных исследований по системам массового обслуживания приведены в работах [12–15].

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

$f\left(t\right)=\left\{\begin{array}{l}\frac{{\beta }^{-\alpha }{t}^{\alpha -1}{e}^{-t/\beta }}{\Gamma \left(\alpha \right)},t\ge 0;\\ \mathrm{0,}t<\mathrm{0,}\end{array}\right.$

где Г(α) – гамма-функция, равная $\Gamma \left(z\right)=\underset{0}{\overset{\infty }{\int }}{t}^{z-1}{e}^{-t}dt$ для любого вещественного числа z > 0, α > 0, β > 0. Преобразование Лапласа функции f(t) имеет вид:

$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)}\underset{0}{\overset{+\infty }{\int }}{t}^{\alpha -1}{e}^{-(s+1/\beta )t}dt=$

$=\left|\begin{array}{l}(s+1/\beta )t=x\\ t=\frac{\beta }{\beta s+1}x\\ dt=\frac{\beta }{\beta s+1}dx\end{array}\right|=$

$=\frac{{\beta }^{-\alpha }}{\Gamma \left(\alpha \right)}{\left(\frac{\beta }{\beta s+1}\right)}^{\alpha }\underset{0}{\overset{+\infty }{\int }}{x}^{\alpha -1}{e}^{-x}dx=$

$=\frac{{\beta }^{-\alpha }}{\Gamma \left(\alpha \right)}{\left(\frac{\beta }{\beta s+1}\right)}^{\alpha }\Gamma \left(\alpha \right)=\frac{1}{{(\beta s+1)}^{\alpha }}.$

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

С целью дальнейшего построения дробно-рациональной функции для спектрального разложения в последнем выражении сделаем замену переменной $\lambda =1/\beta$ для функции плотности распределения интервалов входного потока, $\mu =1/\beta$ для функции плотности распределения времени обслуживания и ограничимся случаем α=2.

Таким образом, в случае целочисленных $\alpha \ge 2$ данное распределение превращается в обычное распределение Эрланга порядка α. Например, при замене $\lambda =1/\beta ,$ $k=\alpha$   получим обычное распределение Эрланга порядка k: $f_{\lambda }\left(t\right)=\frac{{\lambda }^k{t}^{k-1}{e}^{-\lambda t}}{(k-1)!}.$ Ограничимся распределением Эрланга второго порядка при k = 2 $f_{\lambda }\left(t\right)={\lambda }^{2}t{e}^{-\lambda t}.$ Это распределение отличается от рассмотренного в [11], а также в других работах автора нормированного распределения Эрлага $f_{\lambda }\left(t\right)=4{\lambda }^{2}t{e}^{-2\lambda t},$ обозначенного ранее E₂.

Разница между ними заключается в том, что у нормированного распределения Эрланга математическое ожидание не зависит от порядка распределения k, следовательно, они еще отличаются и числовыми характеристиками [3]. Из-за такой разницы между распределениями, СМО, образованную двумя потоками с функциями плотности обычного распределения Эрланга второго порядка, полученного из гамма распределения обозначим Г₂/Г₂/1. Это будет различать СМО E₂/E₂/1, образованную нормированными распределениями Эрланга.

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

В статье ставится задача получения решения в замкнутой форме для основной характеристики системы - средней задержки в очереди для указанной СМО с помощью метода спектрального разложения решения ИУЛ. Вначале проясним различие между двумя законами распределения Г₂ и E₂. Для этого в табл. 1 и 2 приведем их числовые характеристики: первый начальный момент ${\overline{\tau }}_{\lambda },$ второй начальный момент $\overline{{\tau }_{\lambda }^2},$ квадрат коэффициента вариации  а также параметр распределений λ.

Таблица 1. Числовые характеристики распределений

Table 1. Numerical characteristics of distributions

Таблица 2. Параметр распределения, полученный методом моментов

Table 2. Distribution parameter obtained by the method of moments

Таким образом, указанные законы распределения отличаются как параметром, так и числовыми характеристиками, кроме коэффициента вариации.

При кратком изложении метода спектрального разложения решения ИУЛ будем придерживаться подхода и символики автора классики теории массового обслуживания [1]. Суть решения ИУЛ методом спектрального разложения состоит в нахождении для выражения $F_{\lambda }^{*}\left(-s\right)\cdot B*\left(s\right)-1$ представления в виде произведения двух множителей, которое давало бы рациональную функцию от s. Следовательно, для нахождения закона распределения времени ожидания необходимо следующее спектральное разложение: $F_{\lambda }^{*}\left(-s\right)F_{\mu }^{*}\left(s\right)-1={\psi }_{+}\left(s\right)/{\psi }_{-}\left(s\right),$ где ${\text{ψ}}_{+}\left(s\right)$ и ${\text{ψ}}_{-}\left(s\right)$ некоторые рациональные функции от s, которые можно разложить на множители. Функции ${\psi }_{+}\left(s\right)$ и ${\psi }_{-}\left(s\right)$ должны удовлетворять следующим условиям согласно [1]:

– для $\text{Re}\left(\text{s}\right)>\text{0}$ функция ${\psi }_{+}\left(s\right)$ является аналитической без нулей в этой полуплоскости;

– для $\text{Re}\left(\text{s}\right)<D$ функция ${\psi }_{-}\left(s\right)$ является аналитической без нулей в этой полуплоскости, где D – некоторая положительная константа, определяемая из условия: $\underset{t\to \infty }{\text{lim}}\frac{a\left(t\right)}{e^{-Dt}}<\infty .$   (1)

Кроме того, функции ${\psi }_{+}\left(s\right)$ и ${\psi }_{-}\left(s\right)$ должны удовлетворять следующим условиям:

$\begin{array}{l}\underset{\left|s\right|\to \infty ,\mathrm{Re}\left(s\right)>0}{\lim }\frac{{\psi }_{+}\left(s\right)}{s}=1;\\ \underset{\left|s\right|\to \infty ,\mathrm{Re}\left(s\right)<D}{\lim }\frac{{\psi }_{-}\left(s\right)}{s}=-1.\end{array}$   (2)

Для решения поставленной задачи необходимо вначале построить для рассматриваемой системы спектральное разложение вида $F_{\lambda }^{*}\left(-s\right)F_{\mu }^{*}\left(s\right)-1={\psi }_{+}\left(s\right)/{\psi }_{-}\left(s\right)$с учетом условий (1), (2). Тогда для системы Г₂/Г₂/1 законы распределения интервалов входного потока и времени обслуживания задаются функциями плотности вида:

$f_{\lambda }\left(t\right)={\lambda }^{2}t{e}^{-\lambda t},$    (3)

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

Преобразования Лапласа функций (3) и (4) будут соответственно:

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

Тогда спектральное разложение решения ИУЛ для рассматриваемой системы $F_{\lambda }^{*}\left(-s\right)F_{\mu }^{*}\left(s\right)-1={\psi }_{+}\left(s\right)/{\psi }_{-}\left(s\right)$ примет вид:

$\frac{{\psi }_{+}\left(s\right)}{{\psi }_{-}\left(s\right)}={\left(\frac{\lambda }{\lambda -s}\right)}^2{\left(\frac{\mu }{\mu +s}\right)}^2-1=$

$=\frac{{\lambda }^2{\mu }^2-{(\lambda -s)}^2{(\mu +s)}^2}{{(\lambda -s)}^2{(\mu +s)}^2}=$

$=\frac{-s(s^3-c_2{s}^2-c_{1}s-c_0)}{{(\lambda -s)}^2{(\mu +s)}^2},$

где коэффициенты кубического многочлена, собранные с помощью символьных операций Mathcad

$c_0=2\lambda \mu (\mu -\lambda ), c_1=-({\lambda }^2-4\lambda \mu +{\mu }^2),$

$c_2=-2(\mu -\lambda ).$

Кубическое уравнение, полученное из числителя разложения $s^3-c_2{s}^2-c_{1}s-c_0=0$ имеет два отрицательных корня и один положительный, т. к. в случае стабильной системы $\lambda <\mu ,$ т. е. $\left(\mu -\lambda \right)>0.$ Обозначим их для удобства через $-s_1, -s_2$ и $s_3\text{:}$

Тогда нули числителя разложения ${\psi }_{+}\left(s\right)/{\psi }_{-}\left(s\right)\text{:}$

$s=\mathrm{0,}-s_1,-s_2,s_3.$

Двукратные полюсы разложения ${\psi }_{+}\left(s\right)/{\psi }_{-}\left(s\right)\text{:}$ $s=\lambda ,$ $s=-\mu$ (см. рисунок). Теперь с учетом условий (1) и (2) построим функции ${\text{ψ}}_{+}\left(s\right)$ и ${\psi }_{-}\left(s\right)\text{:}$

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

Выполнение условий (1) для этих функций очевидно, что подтверждается также рисунком. Остается проверить выполнение условий (2):

$\underset{\left|s\right|\to \infty }{\lim }\frac{{\psi }_{+}\left(s\right)}{s}=1;$

$\underset{\left|s\right|\to \infty }{\lim }\frac{{\psi }_{-}\left(s\right)}{s}=\underset{\left|s\right|\to \infty }{\lim }\frac{2\left(\lambda -s\right)}{2s-s_3}=-1.$

Условия (2) также полностью выполнены.

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

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

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

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

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

где $s_1$ и $s_2$ – абсолютные значения отрицательных корней $-s_1,$ $-s_2.$ Теперь построим промежуточную функцию

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

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

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

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

$-\frac{d{W}^{*}\left(s\right)}{d\left(s\right)}\left|{}_{s=0}\right.=\frac{s_1+s_2}{s_1{s}_2}-\frac{1}{\mu }=\frac{1}{s_1}+\frac{1}{s_2}-\frac{1}{\mu }.$

Окончательно, среднее время ожидания для системы Г₂/Г₂/1

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

где $s_1$ и $s_2$ как корни кубического уравнения выражаются через параметры распределений (3) и (4).

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

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

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

Table 3. Results of experiments for QS Г2/Г2/1 and E2/E2/1

Несмотря на большие различия между распределениями E₂ и Г₂, показанные в табл. 1 и 2, а также различие между преобразованиями Лапласа функции плотности времени ожидания, данные табл. 3 полностью совпадают с соответствующими данными для СМО E₂/E₂/1. Данные табл. 3 хорошо согласуются с результатами метода двух моментной аппроксимации [9], а также с результатами имитации [10].

Заключение

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

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

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

About the authors

Veniamin N. Tarasov

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

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

References

Supplementary files

Supplementary Files

Action

1. JATS XML

Download

2. Fig. Zeros and poles of the function for the system Г2/Г2/1

Download (3KB)

Indexing metadata