# Abstract

This article presents the results of deriving the formula for the average waiting time for the queuing system E2/HE2/1 with second-order Erlang and hyper-Erlang input distributions. By the definition of Kendall, this system belongs to the class G/G/1 with arbitrary laws of distribution of intervals of the input stream and service time. In queuing theory, studies of such systems are particularly relevant because it is impossible to find a solution for the average waiting time in the queue in the final form for the general case. For the system under consideration, such a solution can be obtained in closed form based on the classical method of spectral decomposition of the solution of the Lindley integral equation for systems of type G/G/1. Using higher-order Erlang and hyper-Erlang distributions is difficult to derive a solution for the average latency due to increasing computational complexity. The article presents the obtained spectral decomposition of the solution of the Lindley integral equation for the system under consideration and the calculation formula for the average waiting time in the queue. The adequacy of the results is confirmed by the correct use of the classical method of spectral decomposition and the results of numerical simulation. The E2/HE2/1 system is applicable when the coefficient of variation of the intervals of receipt is equal to 1/ 2 and the coefficient of variation of the service time is greater 1/ 2. For practical application of the results obtained, the probability method moments method is used. The results of numerical modeling in the Mathcad package unambiguously confirm the fact of the queuing theory that the average waiting time is related to the coefficients of variation of the intervals of arrival and service time by a quadratic dependence

# Full Text

Статья посвящена анализу системы массового обслуживания (СМО) E2/HE2/1 с эрланговским (E2) и с гиперэрланговским (HE2) входными распределениями. В открытом доступе авторам не удалось обнаружить результаты для среднего времени ожидания требований в очереди для такой СМО. Как известно из теории массового обслуживания, среднее время ожидания является главной характеристикой для любых СМО. По этой характеристике, например, оценивают задержки пакетов в сетях пакетной коммутации при их моделировании с помощью СМО. Рассматриваемая СМО относится к типу G/G/1. В теории массового обслуживания исследования систем G/G/1 актуальны в связи с тем, что они активно используются в современной теории телетрафика, к тому же нельзя получить решения для таких систем в конечном виде для общего случая. Законы распределений Вейбулла или Гамма наиболее общего вида, которые обеспечивают диапазон изменения коэффициентов вариаций от 0 до ∞ в зависимости от величины их параметров, не позволяют их использовать в теории массового обслуживания. Поэтому остается применять другие частные законы распределений. В исследовании систем G/G/1 важную роль играет метод спектрального разложения решения интегрального уравнения Линдли и большинство результатов в теории массового обслуживания получены именно с помощью данного метода. Метод спектрального разложения решения интегрального уравнения Линдли (ИУЛ) составляет важную часть теории систем G/G/1. Для за- G/G/1. Для за- /G/1. Для за- G/1. Для за- /1. Для записи ИУЛ введем следующие обозначения [1]: ( ) Wy - функция распределения вероятностей (ФРВ) времени ожидания требования в очереди; ( ) () Cu Pu u = <  - ФРВ случайной величины ; u xt = -   x  - случайное время обслуживания требования; t  - интервал времени между поступлениями требований. Тогда одна из форм уравнения Линдли выглядит так [1]: ( ) ( ) ( ) d, 0 0, 0 y W y u Cu y Wy y -∞  -≥  =   <  ∫ . При кратком изложении метода спектрального разложения решения ИУЛ будем придерживаться подхода [1]. Для этого через () As ∗ и () Bs ∗ обозначим преобразования Лапласа функций плотности распределения интервалов между поступлениями и времени обслуживания соответственно. Суть решения ИУЛ методом спектрального разложения состоит в нахождении для выражения ( ) ( ) * *1 A sB s -⋅ - представления в виде произведения двух множителей, которое давало бы рациональную функцию от s. Следовательно, для нахождения закона распределения времени ожидания необходимо следующее спектральное разложение: ( ) ( ) ( ) ( ) * *1 / , A sB s s s +- - ⋅ -=ψ ψ где ( ) s + ψ и ( ) s - ψ - некоторые дробно-рациональные функции от s. Функции ( ) s + ψ и ( ) s - ψ должны удовлетворять следующим условиям согласно [1]: - для ( ) Re s 0 > функция ( ) s + ψ является аналитической без нулей в этой полуплоскости; - для ( ) Re s D < функция ( ) s - ψ - аналитическая без нулей в этой полуплоскости, где D - некоторая положительная константа, определяемая из условия ( ) / lim Dt t at e - →∞ <∞. Кроме того, функции ( ) s + ψ и ( ) s - ψ должны обладать следующими свойствами: ( ) ( ) ,Re 0 lim 1; ss s s + →∞ > ψ = (1) ( ) ( ) ,Re lim 1. s sD s s - →∞ < ψ = - (2) Теперь остается применить метод спектрального разложения к рассматриваемой системе. Постановка задачи В статье ставится задача вывода формулы для среднего времени ожидания для рассматриваемой системы E2/HE2/1 и подтверждения адекватности построенной математической модели путем численного моделирования в пакете Mathcad. Вывод решения для среднего времени ожидания проводится классическим методом спектрального разложения решения ИУЛ, как это показано в [3-6; 13]. Аналогичные подходы к аппроксимации законов распределений использованы в [2; 7-10; 12]. Решение для системы E2/HE2/ 1 В системе E2/HE2/1 интервалы времени между поступлениями требований заданы функцией плотности ( ) 22 , 4 t a t te -λ = λ (3) преобразование Лапласа которой выглядит как: ( ) 2 * 2 . 2 As s λ  =  +λ  (4) Время обслуживания распределено с функцией плотности ( ) ( ) 12 22 22 12 4 41 , tt b t q te q te -µ -µ =µ + -µ (5) а ее преобразование Лапласа имеет вид ( ) ( ) 22 12 12 22 * 1. 22 Bs q q ss   µµ = +-   +µ +µ   (6) Тогда спектральное разложение решения ИУЛ для системы E2/HE2/1 ( ) ( ) * *1 A sB s - ⋅ -= ( ) ( ) / ss +- =ψψ примет вид: ( ) ( ) ( ) 2 22 12 12 2 2 22 1 1. 22 s ss qq ss + - ψ λ  = ×  ψ λ-     µµ × +- -    µ+ µ+     (7) Выражение в квадратных скобках (7) примет вид: ( ) ( ) ( ) ( ) ( ) ( ) 1 2 12 2 22 12 2 01 2 22 12 1 16 16 4 22 , 22 q ss ss b bs bs ss - µµ + µµ + µ += µ+ µ+ ++ = µ+ µ+ где промежуточные параметры 22 0 12 16 , b = µµ ( ) 1 12 1 2 16 [ 1 ], b qq = µµ µ + - µ ( ) 22 21 2 4[ 1 ]. bq q = µ+ - µ Продолжая разложение (7), получим: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 22 01 2 22 2 12 22 2 12 22 2 12 5432 4 3 2 10 22 2 12 12345 22 2 12 4( ) (2 ) 2 2 (2 ) 2 2 (2 ) 2 2 () (2 ) 2 2 ( )( )( )( )( ) . (2 ) 2 2 s b bs bs s ss s ss s ss s ss ds ds ds ds d ss s ssssss ss s + - ψ λ ++ = - ψ λ- µ + µ + λ- µ + µ + -= λ- µ + µ + ------ = = λ- µ + µ + - +σ +σ +σ +σ -σ = λ- µ + µ + Окончательно спектральное разложение решения ИУЛ для системы HE2/E2/1 имеет вид ( ) ( ) ( ) ( ) 12345 22 2 12 ( )( )( )( )( ) . (2 ) 2 2 s s ssssss ss s + - ψ = ψ - +σ +σ +σ +σ -σ = λ- µ + µ + (8) Исследование многочлена в числителе разложения (8) и определение его корней являются основным моментом метода спектрального разложения решения ИУЛ. Поэтому выпишем многочлен пятой степени в числителе разложения (8): 5432 4 3 2 10. s ds ds ds ds d ----- (9) Его коэффициенты, сформированные с помощью символьных операций Mathcad, равны: 2 0 12 12 1 2 1 64 [ ( ) 4 ]; db = λµµ µµ -λµ +µ + λ 1 12 1 2 2 22 12 1 2 2 16{4 ( ) [2 ( ) ] 4 }; d b = λµ µ µ +µ - -λ µµ + µ +µ + λ 2 2 1 2 12 2 1 2 12 16 [( ) 2 ] 16( )( ); d = λ µ +µ + µµ - - µ +µ λ +µµ 222 3 1 2 1 2 12 4[ 4 ( ) 4 ]; d =- λ +µ +µ - λ µ +µ + µµ 4 12 4( ), = λ-µ -µ d и выражаются через параметры распределений (3) и (5), которые предстоит еще определить. Многочлен (9) имеет четыре действительных отрицательных корня 1, -σ 2 , -σ 3, -σ 4 -σ (либо два действительных отрицательных корня и два комплексно сопряженных с отрицательными действительными частями) и один положительный корень 5. σ Исследование знака младшего коэффициента 0 d показывает, что 0 0 d > всегда в случае стабильной системы, когда 0 1. <ρ< С учетом знака минус перед 0 d в многочлене (6) это также подтверждает предположение о наличии таких корней многочлена. C учетом условий [1] строим рациональные функции ( ) s + ψ и ( ): s - ψ 1234 22 12 ( )( )( )( ) () , (2 ) (2 ) ss s s s s ss + +σ +σ +σ +σ ψ= µ+ µ+ так как нули многочлена (9) 0, s = 1, s = -σ 2 , s = -σ 3, s = -σ 4 s = -σ и двукратные полюсы 1 2 s =-µ и 2 2 s =-µ лежат в области ) , ( 0 Re s ≤ ( ) 2 5 2 () , () s s s - λ- ψ=- -σ так как ее нули и полюсы лежат в области ( ) , Re s D > определенной условием [1]. Теперь выполнение обоих условий метода спектрального разложения для построенных функций ( ) s + ψ и ( ) s - ψ очевидно. Далее по методике спектрального разложения найдем константу K: ( ) ( ) ( ) ( ) ( ) 0 1234 22 0 12 1234 22 12 lim () () lim 22 , 16 s s s K s ssss ss + → → ψ = = +σ +σ +σ +σ = = +µ +µ σσσσ = µµ где 1, σ 2 , σ 3, σ 4 σ - абсолютные значения отрицательных корней 1, -σ 2 , -σ 3, -σ 4. -σ Постоянная K определяет вероятность того, что поступающее в систему требование застает ее свободной. Для нахождения преобразования Лапласа ФРВ времени ожидания построим функцию ( ) ( ) ( ) ( ) ( ) ( ) 1234 22 12 22 12 1234 16 22 . () () K s ss ss ssss + + σσσσ Φ= = × ψ µµ +µ +µ × +σ +σ +σ +σ Отсюда преобразование Лапласа ФРВ времени ожидания ( ) * () Ws s s + = ⋅Φ будет равно ( ) ( ) ( ) ( ) ( ) * 22 1234 1 2 22 12 1 2 3 4 22 . 16 () () Ws ss ssss = σσσσ +µ +µ = µµ +σ +σ +σ +σ (10) Для нахождения среднего времени ожидания вычислим производную от функции ( ) * W s со знаком минус в точке 0: s = ( ) * 12 412 0 3 111111 . s dW s ds = -= σσ +++-- σ σµµ Окончательно среднее время ожидания для системы E2/HE2/1: 12 4 2 3 1 111111 . W +++-- µ σ σ σµ = σ (11) Из выражения (10) при необходимости также можно определить моменты высших порядков времени ожидания, например, вторая производная от преобразования (10) в точке 0 s = дает второй начальный момент времени ожидания, что позво- ляет определить дисперсию времени ожидания. Учитывая определение джиттера в телекоммуникациях как разброс времени ожидания вокруг его среднего значения [10], тем самым получим возможность определения джиттера через дисперсию. Это является важным результатом для анализа трафика, чувствительного к задержкам. Для практического применения формулы (11) необходимо определить числовые характеристики распределений (3) E2 и (5) HE2, а через них - неизвестные параметры этих распределений. Для распределения Е2 среднее значение 1 , - λ τ=λ ко- эффициент вариации 1/ 2. cλ = Для нахождения числовых характеристик до второго порядка для распределения (5) воспользуемся свойством преобразования Лапласа * () Bs воспроизведения моментов и запишем начальные моменты: ( ) 12 1 , q q µ - τ= + µµ ( ) 2 22 12 1 3 . 2 q q µ -  τ= +  µµ  (12) Рассматривая равенства (12) как запись метода моментов, найдем неизвестные параметры распределения (5) 1, µ 2 , µ . q Система двух уравнений (12) при этом является недоопределенной, поэтому к ней добавим выражение для квадрата коэффициента вариации: 22 2 2 () , () c µµ µ µ τ-τ = τ (13) как связующее условие между (12). Кроме того, коэффициент вариации будем использовать в расчетах в качестве входного параметра системы. Исходя из вида первого уравнения (12), положим 1 2/ , q µ µ= τ 2 2(1 ) / q µ µ= - τ (14) и потребуем выполнения условия (13) [2; 3]. Подставив выражения (12) и (14) в (13), получим уравнение четвертой степени относительно неизвестного параметра q: 22 2 (1 )[8(1 ) 8(1 ) 3] 0. q q cq cq µµ - + - + += Отбросив тривиальные решения 0 q = и 1, q = получим квадратное уравнение 22 8(1 ) cq µ +- 2 8(1 ) 3 0, µ - + += cq решив его, выберем для однозначности больший корень: 2 2 2(1 ) 3 1 . 2 8(1 ) c q c µ µ +- = + + (15) Отсюда следует, что коэффициент вариации 1/ 2. cµ ≥ Теперь, подставив (15) в (14), определяем все три неизвестных параметра распределе- ния (5). Аналогичную аппроксимацию законов распределений с использованием начальных моментов можно увидеть в [3-5; 13]. Таблица. Исходные данные и результаты вычислительного эксперимента для СМО E2/HE2/1 Входные параметры Среднее время ожидания ρ cµ для системы E2/HE2/1 для системы E2/H2/1 0,1 0,71 0,018 - 2 0,160 0,160 4 0,796 0,795 8 3,452 3,448 0,5 0,71 0,395 - 2 2,102 2,094 4 8,092 8,082 8 32,089 32,079 0,9 0,71 4,380 2 20,082 20,072 4 74,075 74,065 8 290,074 290,063 Результаты численного моделирования В таблице приведены данные расчетов для системы E2/HE2/1 для случаев малой, средней и высокой нагрузки 0,1; ρ= 0,5; 0,9. Заметим, что эта система определена для 1/ 2 cλ = и 1/ 2. cµ ≥ Данные расчетов для системы E2/HE2/1 сравниваются с результатами близкой системы E2/H2/1, где H2 - гиперэкспоненциальный закон распределения второго порядка. Прочерки в таблице означают, что при данных параметрах система E2/H2/1 неприменима. Коэффициент загрузки ρ определяется отношения средних интервалов /. µλ ρ=τ τ Результаты, приведенные в таблице, получены для нормированного времени обслуживания 1. µ τ= Данные таблицы свидетельствуют о незначительном различии сравниваемых систем, так как сами распределения HE2 и H2 мало отличаются друг от друга. Результаты для системы E2/HE2/1 хорошо согласуются с данными [10] в той области изменения параметров, при которых применима данная система, что свидетельствует об адекватности разработанной модели. Заключение В работе получено спектральное разложение решения интегрального уравнения Линдли для системы E2/HE2/1 и через него выведена расчетная формула для среднего времени ожидания в очереди в такой системе. Это расчетное выражение дополняет известную незавершенную формулу для среднего времени ожидания для систем типа G/G/1. Среднее время ожидания в очереди - это основная характеристика для систем массового обслуживания, так как все остальные характеристики: время задержки, средняя длина очереди,количество требований в системе и др. - являются производными от основной характеристики. Адекватность полученных результатов обеспечена корректным использованием классического метода спектрального разложения, а проведенные вычислительные эксперименты только подтверждают данный факт.

### V. N Tarasov

Povolzhskiy State University of Telecommunications and Informatics

Email: tarasov-vn@psuti.ru
Samara, Russia Federation

### N. F Bakhareva

Povolzhskiy State University of Telecommunications and Informatics

Email: tarasov-vn@psuti.ru
Samara, Russia Federation

Povolzhskiy State University of Telecommunications and Informatics

Email: tarasov-vn@psuti.ru
Samara, Russia Federation

# References

1. Клейнрок Л. Теория массового обслуживания / пер. с англ. М.: Машиностроение, 1979. 432 с.
2. Brannstrom N. A Queueing Theory analysis of wireless radio systems. Appllied to HS-DSCH. Lulea University of Technology, 2004. 79 p.
3. Тарасов В.Н., Бахарева Н.Ф., Липилина Л.В. Математическая модель телетрафика на основе системы G/M/1 и результаты вычислительных экспериментов // Информационные технологии. 2016. Т. 22. No 2. С. 121-126.
4. Тарасов В.Н., Карташевский И.В. Способы аппроксимации входных распределений для системы G/G/1 и анализ полученных результатов // Системы управления и информацион-ные технологии. 2015. No 3. С. 182-185.
5. Тарасов В.Н., Горелов Г.А., Ушаков Ю.А. Восстановление моментных характеристик распределения интервалов между пакетами входящего трафика // Инфокоммуникационные технологии. 2014. Т. 12. No 2. С. 40-44.
6. Тарасов В.Н. Вероятностное компьютерное моделирование сложных систем. Самара: СНЦ РАН, 2002. 194 с.
7. Myskja A. An improved heuristic approximation for the GI/GI/1 queue with bursty arrivals // Teletraffic and datatraffic in a Period of Change, ITC-13. 1991. P. 683-688.
8. Whitt W. Approximating a point process by a renewal process: two basic methods // Operation Research. 1982. Vol. 30. No 1. P. 125-147.
9. Алиев Т.И. Основы моделирования дискретных систем. СПб.: СПбГУ ИТМО, 2009. 363 с.
10. Алиев Т.И. Аппроксимация вероятностных распределений в моделях массового обслуживания // Научно-технический вестник информационных технологий, механики и оптики. 2013. No 2 (84). С. 88-93.
11. RFC 3393 IP Packet Delay Variation Metric for IP Performance Metrics (IPPM). URL: https://tools.ietf.org/html/rfc3393 (дата обращения: 26.02.2016).
12. Тарасов В.Н., Бахаpева Н.Ф. Обобщенная двумеpная диффузионная модель массового обслуживания типа GI/G/1 // Телекоммуникации. 2009. No 7. С. 2-8.
13. Тарасов В.Н., Малахов С.В., Карташевский И.В. Теоретическое и экспериментальное - исследование задержки в программно-конфигурируемых сетях // Инфокоммуникационные технологии. 2015. Т. 13. No 4. С. 409-413.

# Statistics

#### Views

Abstract - 17

PDF (Russian) - 4