Teletraffic mathematical model based on Erlang and hypererlang distributions

Full Text

Abstract

This article presents the results of 22 / /1HE E queuing system studies with Hyper-Erlang and Erlang second-order input distributions. By Kendall’s defi nition, these systems belong to G/G/1 class with arbitrary distribution laws of input fl ow intervals and service time. In the queueing theory, the study of such systems is particularly relevant due to the fact that it is still not impossible to fi nd a solution for the average waiting time in a queue in the fi nal form. Higher-order Erlang and hyper-Erlang distributions are diffi cult to consider since they cause an increase in computational complexity when deriving a solution for the average waiting time. For the considered second-order distributions, the classical spectral decomposition method of solving the Lindley integral equation for G/G/1 systems allows obtaining a solution in closed form. The article presents the obtained spectral decomposition of the Lindley integral equation solution for the system in question and the formula for the average waiting time in the queue. The adequacy of the obtained results is confi rmed by the correctness of using the classical spectral decomposition method and the results of numerical simulation. The 22 / /1HE E system is applicable when the arrival intervals variation coeffi cient is greater than or equal to 1/ 2 and the service time variation coeffi cient is equal to 1/ 2. For practical application of the results obtained, the method of moments from probability theory is used. The results of Mathcad numerical simulation unequivocally confi rm that the average waiting time is related to the arrival intervals variation coeffi cient and the service time variation coeffi cient by a quadratic dependence.

Full Text

Статья посвящена анализу систем массового обслуживания (СМО) 22 / /1HE E с гиперэрланговским 2 HE и эрланговским E2 входными распределениями. В открытом доступе авторам не удалось обнаружить результаты для среднего времени ожидания требований в очереди в такой СМО. Из теории СМО известно, что среднее время ожидания является главной характеристикой, по которой, например, оценивают задержки пакетов в сетях пакетной коммутации при их моделировании с помощью СМО. Рассматриваемая СМО относится к типу G/G/1. В теории массового обслуживания исследования систем G/G/1 актуальны в связи с тем, что они активно используются в современной теории телетрафика, к тому же нельзя получить решения для таких систем в конечном виде для общего случая. Законы распределений Вейбулла или гамма наиболее общего вида, которые обеспечивают диапазон изменения коэффициентов вариаций от 0 до ∞ в зависимости от величины их параметров, не позволяют их применять в теории массового обслуживания. Поэтому остается использовать другие частные законы распределений. В исследовании систем G/G/1 важную роль играет метод спектрального разложения решения интегрального уравнения Линдли (ИУЛ) и большинство результатов в теории СМО получены именно с помощью данного метода. Метод спектрального разложения решения ИУЛ составляет важную часть теории систем G/G/1. Для записи ИУЛ введем следующие обозначения [1]: () Wy - функция распределения вероятностей (ФРВ) времени ожидания требования в очереди; ( ) ( ) C u P u u = <  - ФРВ случайной величины . uxt = -  Здесь x  - случайное время обслуживания требования; t  - случайная величина: интервал времени между поступлениями требований. Используемая [1] форма ИУЛ выглядит как ( ) ( ) ( ), 0; y W y W y u dC u y -∞ = - ≥ ∫ ( ) 0, Wy= 0. y< При изложении метода спектрального разложения решения ИУЛ будем придерживаться классического подхода и символики [1]. Для этого через () As ∗ и () Bs ∗ обозначим преобразования Лапласа ФРВ интервалов между поступлениями и времени обслуживания соответственно. Суть решения ИУЛ методом спектрального разложения состоит в нахождении для выражения *( ) *( ) 1 A s B s -- представления в виде произведения двух множителей, которое давало бы рациональную функцию от s. Следовательно, для нахождения закона распределения времени ожидания необходимо следующее спектральное разложение: *( ) *( ) 1 A s B s - - = ( )/ ( ), ss +- ψψ где ψ и () s-ψ - некоторые дробно-рациональные функции от s. Функции () s+ψ и () s-ψ должны удовлетворять следующим условиям [1]: - для Re(s) 0 > функция () s+ψ является аналитической без нулей в этой полуплоскости; - для () Re sD < функция () s-ψ является аналитической без нулей в этой полуплоскости, где D - некоторая положительная константа, определяемая из условия: ( )/ . lim Dt t a t e - →∞ <∞ Кроме того, функции () s+ψ и () s-ψ должны обладать следующими свойствами: () ,0 () 1; s Re lim s s s + →∞ > ψ = (1) , () 1() . Re lim s s D s s - →∞ < ψ = - (2) Теперь остается применить метод спектрального разложения к рассматриваемой системе. Постановка задачи Необходимо вывести формулу для среднего времени ожидания для рассматриваемой системы 22 / /1HE E и подтвердить адекватность построенной математической модели путем численного моделирования в пакете Mathcad. Вывод решения для среднего времени ожидания проводится методом спектрального разложения решения ИУЛ. Решение для системы HE2 / E2 / 1 В системе 22 / /1HE E интервалы времени между поступлениями требований заданы функцией плотности 12 22 22 12 ( ) 4 4(1 ) , tta t p te p te -λ -λ = λ + - λ (3) преобразование Лапласа которой имеет вид: 22 * 12 12 22( ) (1 ) . 22 A s p p ss     λλ = + -     +λ +λ     (4) Время обслуживания распределено с функцией плотности 22 ( ) 4 , tb t te -µ= µ (5) а ее преобразование Лапласа имеет вид: 2 * 2 () 2 .Bs s  µ = +µ  (6) Тогда спектральное разложение решения ИУЛ для системы 22 / /1HE E *( ) *( ) 1 A s B s - - = ( )/ ( ) ss +- =ψ ψ примет вид: ( ) 2 1 1 2 2 2 2 2( 2 ) () 22 1 1. 22 p s p s s s s + -   ψλ = +   ψ λ -     λµ +- -  λ - µ+      (7) Первый сомножитель (7) примет вид: ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) 22 12 12 2 2 2 22 1 2 1 2 1 22 12 2 2 2 2 2 1 2 1 2 2 22 12 2 0 1 2 22 12 22 1 22 16 16 4 22 1 16 16 4 22 , 22 pp ss p s s ss p s s ss a a s a s ss      λλ +- =      λ- λ-       λ λ - λ λ + λ = + λ - λ - - λ λ - λ λ + λ += λ - λ - -+ = λ - λ - где промежуточные параметры ( ) ( ) 22 0 1 2 1 1 2 1 2 22 2 1 2 16 , 16 1 , 41. a a p p a p p = λ λ = λ λ λ + - λ    = λ + - λ  Продолжая разложение (7), получим: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( )( )( )( ) ( ) ( ) ( ) 2 2 2 12 2 2 2 12 5432 4 3 2 1 0 2 2 2 12 12 2 345 2 2 2 12 0 1 2 2 2 2 12 222 ( ) 4 ( ) () 222 222 . 2 (2 ) ( ( 2 2 2 2 ) ) s a a s a s s s s s s s s s c s c s c s s cs c s s s s s s s s s s s s s s s s s s s s + - λ - λ - µ+ -= λ - λ - µ+ - - - - - - = = λ - λ - µ+ - + + - - - = λ - λ - ψ µ - + = - ψ λ - + µ+ λ - µ Окончательно спектральное разложение решения ИУЛ для системы 22 / /1HE E имеет вид: ( )( )( )( )( ) ( ) ( ) ( ) 12345 2 2 2 12 . 222 () () s s s s s s s s s s s s ss ss + - ψ = ψ - + + - - - = λ - λ - µ+ (8) Исследование многочлена в числителе разложения (7) и определение его корней является основным моментом метода спектрального разложения решения ИУЛ. Поэтому выпишем многочлен пятой степени в числителе разложения (8) 5432 4 3 2 1 0 .s c s c s c s cs c - - - - - (9) Его коэффициенты, сформированные с помощью символьных операций Mathcad, равны ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) 2 0 1 1 2 1 2 1 2 2 2 2 2 2 2 1 2 1 2 1 2 1 2 1 2 2 2 2 + λ λ - µλ λ = - λ +λ +µ - µ λ +λ - λ λ = λ +λ -µ ca c c c и выражаются через параметры распределений (3) и (5), которые предстоит еще определить. Многочлен (9) имеет два действительных отрицательных корня 1, s- 2 s- и три положительных корня 3, s 4, s 5 s (либо вместо последних один действительный положительный и два комплексно сопряженных с положительной вещественной частью) в случае стабильной системы, то есть когда / 1. µλ ρ= τ τ < Исследование знака младшего коэффициента 0c показывает, что 0 0 c > всегда в случае стабильной системы, когда 0 1. <ρ< С учетом знака «минус» перед 0 c в многочлене (9) это также подтверждает предположение о наличии таких корней многочлена. Далее, с учетом условий (1) и (2) строим рациональные функции () s+ψ и () :s-ψ 2 12 ( ) ( )( )/(2 ) , s s s s s s s+ ψ = + + µ+ так как нули многочлена (9): 0, s = 1, ss = - 2 ss = - и двукратный полюс 2 s =-µ лежат в области ) ,( 0Re s ≤ ( ) ( ) ( ) ( )( )( ) 22 12 345 22 , ss s s s s s s s- λ - λ - ψ = - --- так как ее нули и полюсы лежат в области ( ) ,Re s D> определенной условием (1). Теперь выполнение условий (1) и (2) метода спектрального разложения для построенных функций () s+ψ и () s-ψ очевидно. Далее по методике спектрального разложения найдем константу K: ( )( ) ( ) 1212 2 200 ( , 42 ) lim lim ss ssss K s ss s s + →→ ++ψ = = = µ+µ где 1, s 2 s - абсолютные значения отрицательных корней 1, s- 2. s- Постоянная K определяет веK определяет веK роятность того, что поступающее в систему требование застает ее свободной. Для нахождения преобразования Лапласа ФРВ времени ожидания построим функцию ( ) ( )( ) 2 12 2 12 2 . 4 () () ss sK ss s s sss+ + +µ Φ = = ψ µ + + Отсюда преобразование Лапласа функции плотности времени ожидания *( ) ( ) Ws ss += Φ будет равно ( ) ( )( ) 2 * 12 2 12 2 .( 4 ) ss s W s s s s s +µ = µ + + (10) Для нахождения среднего времени ожидания найдем производную от функции *() Ws со знаком минус в точке 0 :s = * 120 1 .( 1) 1 s ds s s sdW = - = + - µ Окончательно среднее время ожидания для системы 22 / /1HE E 12 111 .W ss =+- µ (11) Из выражения (10) при необходимости также можно определить моменты высших порядков времени ожидания, например вторая производная от преобразования (10) в точке 0 s = дает второй начальный момент времени ожидания, что позволяет определить дисперсию времени ожидания. Учитывая определение джиттера в телекоммуникациях как разброс времени ожидания вокруг его среднего значения [10], тем самым получим возможность определения джиттера через дисперсию. Это является важным результатом для анализа трафика, чувствительного к задержкам. Для практического применения формулы (11) необходимо определить числовые характеристики распределений (3) 2 HE и (5) 2, E а через них - неизвестные параметры этих распределений. Для этого воспользуемся свойством преобразований Лапласа (4) и (6) воспроизведения моментов и запишем начальные моменты до второго порядка для распределения (3): ( ) 12 1 , pp λ - τ = + λλ ( )2 22 12 13 . 2 pp λ -  τ = +  λλ  (12) Рассматривая равенства (12) как запись метода моментов, найдем неизвестные параметры распределения (3) 1, λ 2, λ . p Система двух уравнений (12) при этом является не доопределенной, поэтому к ней добавим выражение для квадрата коэффициента вариации: 22 2 2 () () λλ λ λ τ-τ = τ c (13) как связующее условие между (12). Кроме того, коэффициент вариации будем использовать в расчетах в качестве входного параметра системы. Исходя из вида первого уравнения (12) положим 1 / , 2p λ λ = τ ( ) 2 2 1 / p λ λ = - τ (14) и потребуем выполнения условия (13) [2-3]. Подставив выражения (12) и (14) в (13), получим уравнение четвертой степени относительно неизвестного параметра p: p p c p c p λλ  - + - + + =  Отбросив тривиальные решения 0 p = и 1, p = получим квадратное уравнение ( )22 81 cp λ +- ( ) 2 8 1 3 0, cp λ - + + = решив которое выберем для однозначности больший корень для параметра p: ( ) ( ) 2 2 2 1 31 . 2 81 c p c λ λ +- = + + (15) Отсюда следует, что коэффициент вариации 1/ 2.c λ ≥ Теперь, подставив (15) в (14), определяем все три неизвестных параметра распределения (3) согласно [2]. Для распределения (4) числовые характеристики равны 1/ , µ τ = µ 1/ 2 µ =c [4]. Аналогичную аппроксимацию законов распределений с использованием начальных моментов можно увидеть в [7; 8]. Результаты численного моделирования В таблице приведены данные расчетов для системы 22 / /1HE E для случаев малой, средней и высокой нагрузки 0,1; ρ= 0,5; 0,9. Заметим, что эта система определена для 1/ 2 cλ ≥ и 1/ 2. cµ = Данные расчетов для системы 22 / /1HE E сравниваются с результатами близкой системы 22 / /1, HE где 2 H - гиперэкспоненциальный закон распределения второго порядка. Прочерки в таблице означают, что при данных параметрах система параметрах система па 22 / /1 HE не применима. Коэффициент загрузки ρ в определяется отношением средних интервалов / . µλ ρ= τ τ Расчеты в таблице проведены для нормированного времени обслуживания 1. µ τ= Данные таблицы свидетельствуют о незначительном различии сравниваемых систем в случае средних и высоких нагрузок и более значительных расхождениях при малых нагрузках. Результаты расчетов для системы 22 / /1HE E хорошо согласуются с данными [10] в той области изменения параметров, при которых применима данная система. Заключение В работе получено спектральное разложение решения ИУЛ для системы 22 / /1HE E и через него выведено расчетное выражение для среднего времени ожидания в очереди в такой системе. Это расчетное выражение дополняет известную незавершенную формулу для среднего времени ожидания для систем типа G/G/1. Среднее время ожидания в очереди - это основная характеристика для СМО, так как все остальные характеристики: время задержки, средняя длина очереди, количество требований в системе - являются производными от основной характеристики. Адекватность полученных результатов обеспечена корректным использованием классического метода спектрального разложения, а проведенные вычислительные эксперименты только подтверждают данный факт. Таблица. Результаты экспериментов для СМО
×

About the authors

V. N Tarasov

Povolzhskiy State University of Telecommunications and Informatics

Samara, Russian Federation

N. F Bakhareva

Povolzhskiy State University of Telecommunications and Informatics

Samara, Russian Federation

O. Kada

Povolzhskiy State University of Telecommunications and Informatics

Samara, Russian Federation

References

  1. Клейнрок Л. Теория массового обслуживания / под ред. В.И. Неймана; пер. с англ. И.И. Глушко. М.: Машиностроение, 1979. 432 с.
  2. Тарасов В.Н. Исследование систем массового обслуживания с гиперэкспоненциальными входными распределениями // Проблемы передачи информации. 2016. № 1. С. 16-26. doi: 10.1134/S0032946016010038.
  3. Тарасов В.Н., Бахарева Н.Ф., Блатов И.А. Анализ и расчет системы массового обслуживания с запаздыванием // Автоматика и телемеханика. 2015. № 11. С. 51-59. DOI: 10.1134/ S0005117915110041.
  4. Кругликов В.К., Тарасов В.Н. Анализ и расчет сетей массового обслуживания с использованием двумерной диффузионной аппроксимации // Автоматика и телемеханика. 1983. № 8. С. 74-83.
  5. Тарасов В.Н., Горелов Г.А., Ушаков Ю.А. Восстановление моментных характеристик распределения интервалов между пакетами входящего трафика // Инфокоммуникационные технологии. 2014. № 2. С. 40-44.
  6. Анализ входящего трафика на уровне трех моментов распределений временных интервалов / В.Н. Тарасов [и др.] // Информационные технологии. 2014. № 9. С. 54-59.
  7. Myskja A. An improved heuristic approximation for the GI/GI/1 queue with bursty arrivals // Teletraffi c and Datatraffi c in a Period of Change, ITC-13. Elsevier Science Publishers, 1991. P. 683-688.
  8. Whitt W. Approximating a point process by a renewal process: two basic methods // Operation Research. 1982. Vol. 30. № 1. P. 125-147.
  9. IP Packet Delay Variation Metric for IP Performance Metrics (IPPM). URL: https:// tools.ietf.org/html/rfc3393 (дата обращения: 26.02.2016).
  10. Тарасов В.Н., Бахаpева Н.Ф. Обобщенная двумеpная диффузионная модель массового обслуживания типа GI/G/1 // Телекоммуникации. 2009. № 7. С. 2-8.
  11. Тарасов В.Н. Расширение класса систем массового обслуживания с запаздыванием // Автоматика и телемеханика. 2018. № 12. С. 57-70. doi: 10.1134/S0005117918120056.

Statistics

Views

Abstract: 177

Dimensions

Article Metrics

Metrics Loading ...

PlumX


Copyright (c) 2019 Tarasov V.N., Bakhareva N.F., Kada O.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies