Research of System with Shifted Hyper-Erlang and Exponential Input Distributions

Abstract

This article presents the results of studies on the HE2/M/1 queuing system with hyper-Erlang and exponential input distributions shifted to the right from the zero point. By Kendall’s definition, the HE2/M/1 system with conventional distributions is of type G/M/1, for which, in general the solution for the average queue waiting time is not known. The same system with shifted distributions is transformed into the G/G/1 system, for which, in the general case, the solution for the average waiting time is also unknown. Considering the fact that, starting with a coefficient of variation equal to four, the distribution of hyper-Erlang has a heavy tail, the system in question can have an active application in the modern theory of teletraffic. Using higher-order hyper-Erlang distributions is difficult to derive a solution for the average waiting time of requests in a queue due to increasing computational complexity. For the hyper-Erlangian distribution law, as well as the hyperexponential law, the spectral decomposition method for solving the Lindley integral equation makes it possible to obtain a final solution. The article presents the results on the spectral decomposition of the solution of the Lindley integral equation for the queuing system HE2/M/1 with shifted distributions, as well as the calculation formula for the average waiting time for claims in the queue. It is shown that the HE2/M/1 system with shifted distributions is a system with a time lag and provides a shorter waiting time compared to a conventional system. The adequacy of the results is confirmed by the correct use of the classical method of spectral decomposition and the results of numerical simulation. To derive the obtained results, as well as for numerical calculations, the well-known method of moments of probability theory is used.

Full Text

Настоящая статья посвящена анализу системы массового обслуживания) СМО HE2/M/1 со сдвинутыми вправо от нулевой точки гиперэрланговским и экспоненциальным входными распределениями. Система HE2/M/1 с обычными распределениями рассмотрена в [1], где для нее представлены спектральное разложение решения интегрального уравнения Линдли и расчетная формула для главной характеристики СМО - среднего времени ожидания требований в очереди. В отличие от обычной системы HE2/M/1, систему со сдвинутыми распределениями обозначим 21.HE /M /--Метод спектрального разложения решения интегрального уравнения Линдли (ИУЛ) в теории систем массового обслуживания G/G/1 занимает важное место. Одна из форм интегрального уравнения Линдли выглядит так [2; 3]: ( )d,0,0,0.yW y u Cu yWyy-∞-≥=<∫Для записи ИУЛ, а также при рассмотрении метода спектрального разложения решения ИУЛ будем использовать стандартные обозначе-ния [2]: через ()As∗ и ()Bs∗ обозначим преобразования Лапласа функций плотности распределения интервалов между поступлениями и времени обслуживания соответственно. Суть решения ИУЛ методом спектрального разложения состоит в нахождении для выражения ( )( )* *1A sB s-⋅ - представления в виде произведения двух множителей, которое давало бы рациональную функцию от s. Следовательно, для нахождения закона распределения времени ожи-дания необходимо следующее спектральное разложение: ( )( )* *1A sB s- ⋅ -=( )( )/,ss+-ψψ где ( )s+ψ и ( )s-ψ - некоторые дробно-рациональные функции от s, удовлетворяющие специальным условиям согласно [2], которые здесь опускаем. Постановка задачиВ статье ставитсязадача вывода формулы для среднего времени ожидания для рассматриваемой системы со сдвинутыми распределениями HE2/M/1, а также подтверждения адекватности построенной математической модели путем чис-ленного моделирования в пакете Mathcad. Вы-Mathcad. Вы-. Вы-вод решения для среднего времени ожидания проводится методом спектрального разложения решения ИУЛ, как это показано в работах [4-7]. Близкие аппроксимативные подходы использова-ны в [8-11].Решение для системы //--2HE M 1В системе 21HE /M /-- интервалы времени между поступлениями требований заданы функ-цией плотности10202( )2102( )220() 4 ( )4(1 ) ( ),ttttat p t t ep tte-λ --λ -=λ-++ -λ-(1)преобразование Лапласа которой имеет вид ( )()0221212*221.22tsAsp pess-= λλ=+- +λ+λ  (2)Время обслуживания распределено с плотно-стью0(- )(),ttbt e-μ= μ(3)а ее преобразование Лапласа вычисляется как: ( )0*.tsBses-μ=+μ(4)В выражениях (1)-(4) 00t> представляет со-бой параметр сдвига распределений. Тогда спектральное разложение решения ИУЛ для системы 21HE /M /--( )( )* *1A sB s- ⋅ -=( )( )/ss+-=ψψпримет вид( )( )()00221212221221.tstssppsssees+--ψ λλ=+-× ψλ-λ- μ×-μ+ (5)В разложении (5) экспоненты с противопо-ложными знаками обнуляются, тогда получаем спектральное разложение:( )( )()221212221221.sppssss+-ψ λλ=+-× ψλ-λ- μ×-μ+ (6)Таким образом, спектральное разложение ре-шения ИУЛ для системы 21HE /M /-- полностью совпадает с таким же разложением для обыч-ной системы HE2/M/1, поэтому мы в дальней-M/1, поэтому мы в дальней-/1, поэтому мы в дальнейшем изложении можем воспользоваться резуль-татами [1].Окончательно спектральное разложение ре-шения ИУЛ для системы HE2/M/1 имеет вид [1]( )( )() ()12342212( )( )( )( ).2 2 ()ssssss ssssss ss+-ψ-+ - - -=ψλ -λ - μ+ (7)Исследование многочлена в числителе разложения (7) и определение его корней являются основным моментом метода спектрального раз-ложения решения ИУЛ. Многочлен четвертой степени в числителе разложения (6)-(7)4323 2 10scscscsc+ + ++(8)с коэффициентами0 112 121 216 [()],ca= μ+ λλ λλ -μλ +λ221112 212 1 2 24 ( 4) 16 (),ca= μ λ + λλ +λ - λλ λ +λ - μ2221 2121 24() 164 (),c= λ +λ + λλ - μ λ +λ3124()c=μ- λ +λв случае стабильной системы имеет один действительный отрицательный корень 1s- и три положительных корня 2,s3,s4s (либо вместо последних один действительный положительный и два комплексно сопряженных с положительной вещественной частью). Эти коэффициенты сформированы с помощью символьных операций Mathcad и выражаются через параметры распре- и выражаются через параметры распре-делений (1) и (3), которые предстоит еще опре-делить.Рациональные функции ( )s+ψ и ( )s-ψ будем строить по правилам метода спектрального раз-ложения: ()s+ψ=1( ) / ( ),ss ss+ μ+ так как нули многочлена (6) 0,s=1ss= - и полюс s= -μ ле-жат в области ) ,( 0Res≤ а функция() ()221223422(),( )( )( )sssss ssss-λ- λ-ψ=----так как ее нули и полюсы лежат в области ( ),Re sD> как того требует метод спектрального разложения.Далее по методике спектрального разложения найдем константу K:( )()()1100limlim,ssssssKss+→→ψ+===+μ μгде 1s - абсолютное значение отрицательного корня 1.s- Постоянная K определяет вероятность того, что поступающее в систему требование за-стает ее свободной. Для нахождения преобразования Лапласа функции плотности времени ожидания построим функцию ( )( )11().()K ssss sss+++μΦ= =ψμ+Отсюда преобразование Лапласа функции плотности времени ожидания ( )*()Ws s s+= ⋅Φбудет ( )()()*11.ssWsss+μ=μ+(9)Для вычисления среднего времени ожидания найдем производную от функции ( )*W s со зна-ком минус в точке 0:s=( )*1011.sdW sdss=-=-μОкончательно среднее время ожидания для системы 21--HE /M / :111//-=μ.Ws(10)Выражение (9) для преобразования Лапласа функции плотности времени ожидания позволяет определить также моменты высших порядков времени ожидания, а именно: вторая производная от преобразования (9) в точке 0s= дает второй начальный момент времени ожидания, что позволяет определить дисперсию времени ожидания. В стандарте [12] джиттер (дрожание задержки)в телекоммуникациях определен как колебание времени ожидания вокруг его среднего значения. Тогда джиттер можно определить через дисперсию времени ожидания. При анализе трафика, чувствительного к задержкам, это будет важным подспорьем.Для использования формулы (10) при расчетах необходимо знать числовые характеристики распределения (1) и (3). Через числовые характеристики будем определять неизвестные параметры распределений (1) и (3) методом моментов. Для этого воспользуемся основным свойством преобразований Лапласа (2) и (4) воспроизведения моментов и запишем первые два первых начальных момента для распределения (1):()01222002212 1 21,(1 ) 3 3(1 )2[].22pptp pp pttλλ-τ= ++λλ--τ= +++ +λλ λ λ (11)Отсюда определим квадрат коэффициента ва-риации интервалов поступления:2221 21212211 2 0122()(12)().2[()]pppcptλλ - λ λ -λ + - λ -λ=λ- λ-λ + λλ (12)Для распределения (3) эти же моменты равны 10.t-μτ=μ +(13)Второй начальный момент времени обслужи-вания выглядит как2200222.ttμτ= + +μμ(14)Отсюда коэффициент вариации времени обслуживания будет равен10(1 ) .ct-μ= +μ(15)Рассматривая равенства (11)-(15) как форму записи метода моментов, найдем неизвестные параметры распределений (1) и (3) 1,λ2,λ,p,μ0.t Теперь, исходя из вида первого уравне-ния (11), положим 102 / (),ptλλ= τ-202(1 ) / ()ptλλ= - τ- (16)и потребуем выполнения условия (12). Подставив (16) в (12), решаем полученное уравнение четвертой степени относительно параметра p с учетом условия 01p<< и выбираем нужное решение:202 2201 13(),2 4 8[()]tptcλλλλτ-=+-τ- + τа затем определяем из (16) параметры 1λ и 2λ. Определим параметры распределения (3) из уравнений моментов (13)-(15). Из (13) получим значение 10t-μ=τ -μ и, подставив его в (15), найдем параметр распределения (3) 1/ .cμμ Таблица. Результаты экспериментов для СМО 21HE /M /-- и НE2/M/1 Параметр сдвига будет связан с параметрами обслуживания условием 0(1 ).tcμμ=τ-(17)Выражение (17) будет определять диапазон изменения параметра сдвига 0(0, 1).t∈Тогда алгоритм расчета среднего времени ожидания в очереди для системы 21HE /M /-- сво-дится к следующим этапам. 1. Задавая значения ,λτ,μτ,cλ,cμ0t в качестве входных параметров системы, определяем методом моментов все неизвестные параметры распределений (1) и (3).2. Находим нужный корень 1s- уравнения (8) и используем расчетную формулу (10). Аналогичную аппроксимацию законов распределений с использованием начальных моментов можно увидеть в [7; 8].Теперь рассмотрим влияние параметра сдвига на коэффициенты вариаций распределений. Для обычного распределения HE2, как следует из выражения (12), при00=:t2221 2121221 122()(12)().2[()]pppcpλλ - λ λ -λ + - λ -λ=λ- λ-λСравнивая последнее выражение с (12), убеждаемся, что параметр сдвига во времени 00t>уменьшает коэффициент вариации интервалов поступлений в 012121[ (1 )]tppλλ+λ - +λ раз. Аналогично для экспоненциального закона времени обслуживания параметр сдвига уменьшает коэффициент вариации времени обслуживания в 01t+μ раз. Учитывая квадратичную зависимость среднего времени ожидания от коэффициентов вариаций интервалов поступлений и времени обслуживания, убеждаемся в том, что введение па-раметра сдвига в законы распределения (1) и (3) уменьшает среднее время ожидания в очереди в СМО. Результаты численного моделированияВ таблице приведены данные расчетов среднего времени ожидания для систем 21HE /M /-- и HE2/M/1 для случаев малой, средней и высокой нагрузки 0,1;ρ= 0,5; 0,9.Коэффициент загрузки ρ определяется отношением средних интервалов /.μλρ=τ τ Результаты, приведенные в таблице, получены для нормированного времени обслуживания 1.μτ= Данные таблицы подтверждают сделанные выше предположения о среднем времени ожидания в системе с запаздыванием. Кроме того, с уменьшением параметра сдвига t0 среднее время ожидания в системе с запаздыванием стремится к значению этого времени в обычной системе, что дополнительно подтверждает адекватность полученных результатов. Результаты расчетов хорошо согласуются с данными [13] в той области изменения параметров, где применимы данные рассматриваемой системы.ЗаключениеВ работе получено спектральное разложение решения ИУЛ для системы 21,HE /M /-- а через нее выведена расчетная формула для среднего времени ожидания требований в очереди для этой системы. Эта формула дополняет известную незавершенную формулу теории массового обслуживания для среднего времени ожидания для систем типа G/G/1.Результаты вычислительных экспериментов подтверждают, что новая система 21HE /M /--обеспечивает намного меньшее время ожида-ния в очереди, чем обычная система HE2/M/1, за счет введения в законы распределения параметра сдвига 0(0, 1).t∈Известно, что среднее время ожидания требований в очереди является главной характеристикой СМО, так как остальные характеристики: средняя задержка, средняя длина очереди, среднее количество требований в системе и др. - определяются через среднее время ожидания. Адекватность полученных результатов обеспечена корректным использованием классического метода спектрального разложения, а проведенные вычислительные эксперименты только подтверждают данный факт.
×

V. N Tarasov

Povolzhskiy State University of Telecommunications and Informatics

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

References

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