Research of Two Queuing Systems M/E2/1 with Ordinary and Shifted Input Distributions

Abstract

Teletraffic theory often uses queuing systems like M/G/1 and G/G/1. Studies of the latter are still relevant due to the fact that it is impossible to obtain solutions for the average waiting time in the queue in the final form in the general case. This article presents the results for two queuing systems: for a regular M/E2/1 system with exponential and Erlangian distributions, as well as this system with distributions shifted to the right from the zero point. The operation of shifting the laws of distributions in this case transforms the M/G/1 system into a G/G/1 type system due to a decrease in the coefficient of variation of the intervals of the input flow into the system. As it turned out, for the distribution laws under consideration, the spectral decomposition method used for solving the Lindley integral equation for G/G/1 systems allows us to obtain a solution for the average waiting time in the final form. It is shown that in such a system with a delay in time, the average waiting time for requests in the queue can be many times shorter than in a similar conventional system. This follows from the fact that the time-shift operation of the distribution laws reduces the coefficient of variation of the intervals between arrivals and service time. At the same time, it is known that the average waiting time for requirements in the queue for the system depends directly on the squares of these variation coefficients. The M/E2/1 system is applicable only when the coefficient of variation of the intervals of arrival equal to 1 and the coefficient of variation of the service time is equal to 1/ 2, and the system with delay is applicable when the coefficients of variation of the intervals of arrival in the range (0, 1) and the coefficients of variation of the time of service from the interval (0, 1/ 2), which dramatically expands the scope of these systems. To derive solutions by the average waiting time in the queue, the spectral decomposition method of solving the Lindley integral equation, known in queuing theory, was used.

Full Text

Статья посвящена исследованию двух систем массового обслуживания (СМО) M/E2/1 с обычными и сдвинутыми вправо экспоненциальным и эрланговским входными распределениями. Первая система относится к типу M/G/1, а вто-M/G/1, а вто-/G/1, а вто-G/1, а вто-/1, а вторая - G/G/1. В теории массового обслуживания исследования систем G/G/1 актуальны до сих пор в связи с тем, что нельзя получить решения для среднего времени ожидания в очереди в конечном виде в общем случае. В работе авторов [1] впервые приведены результаты по исследованию системы M/M/1 с запаздыванием во времени со сдвинутыми экспоненциальными входными распределениями. В [1] показано, что среднее время ожидания требования в очереди в системе с запаздыванием во времени меньше, чем в классической системе M/M/1 при одинаковом коэффициенте загрузки за счет того, что коэффициенты вариации времен поступления cλ и обслуживания cμ становятся меньше единицы при параметре запаздывания t> В [2] идеи статьи [1] перенесены на системы H2/H2/1, H2/M/1 и M/H2/1.Результаты работ [1; 2] совместно с классической теорией массового обслуживания [3] позво-ляют расширить теорию метода спектрального разложения (МСР) решения интегрального урав-нения Линдли (ИУЛ) также на сдвинутое распре-деление Эрланга.При решении задачи методом спектрального разложения будем использовать стандартную символику оригинала [3], в которой для преобразований Лапласа функций плотностей распределений интервалов между поступающими в систему требованиями и времени обслуживания введены обозначения ()As∗ и ( ).Bs∗ Метод спектрального разложения состоит в преобразо-вании ключевого выражения ( )( )* *1A sB s-⋅ -к произведению некоторых двух множителей в виде дробно-рациональных функций. Для опре-деленности это произведение представим в виде ( )( )* *1A sB s- ⋅ -=( )( )/,ss+-ψψ где рациональные функции ( )s+ψ и ( )s-ψ являются компонентами метода спектрального разложения. Конструирование этих компонент ( )s+ψ и ( )s-ψ является важной частью МСР, и они должны удовлетворять специальным условиям. Система М/E2/1 и вывод решения для среднего времени ожиданияДля системы М/E2/1 законы распределения интервалов входного потока и времени обслуживания задаются функциями плотности вида,()tat e-λ= λ(1)( )22.4tb tte-μ= μ(2)При таком виде функции (2) решения для среднего времени ожидания для системы М/E2/1 в теории массового обслуживания [3; 4; 8; 9] авторами не найдено, и поэтому это решение находим методом спектрального разложения решения ИУЛ, как это показано в [1; 2; 6; 11-13]. Такой подход позволяет определить не только среднее время ожидания, но и моменты высших порядков времени ожидания. Учитывая тот факт, что понятие «дрожание задержки» в стандарте [7] определено как разброс времени ожидания от его среднего значения W, дрожание задержки можно определить через дисперсию. Преобразования Лапласа функций (1) и (2) соответственно имеют вид( );*Assλ=λ+( )2*2.2Bssμ=μ+В связи с тем что система М/E2/1 относится к классу систем М/G/1, воспользуемся результатом для данной системы. Среднее время ожидания в системе М/G/1 дается формулой Полячека - Хин-G/1 дается формулой Полячека - Хин-/1 дается формулой Полячека - Хин-чина [3]:()2,21Wμλτ=-ρ(3)где λ - интенсивность входного потока; 2μτ - второй начальный момент времени обслужива-ния; ρ - коэффициент загрузки 01.<ρ< Для распределения Эрланга второго порядка E2 ви-торой начальный момент времени обслуживания 223/(),2μτ= μ тогда среднее время ожидания в системе М/E2/1 окончательно равно()3.41Wρ=μ -ρ(4)Результатом (4) мы воспользуемся при иссле-довании системы со сдвинутыми распределения-ми, которую обозначим как2Ì /Å /1.--Система 2//--ME1 и вывод решения для среднего времени ожиданияДля системы 2Ì /Å /1-- функциями плотно-стей распределений интервалов будут сдвинутые вправо от нулевой точки распределения:- для входного потока( )( )0,ttat e-λ -= λ(5)- для времени обслуживания( )()( )0220.4ttbtt t e-μ -=μ-(6)Для вывода решения по среднему времени ожидания для данной системы используем клас-сический метод спектрального разложения реше-ния интегрального уравнения Линдли (ИУЛ).Преобразование Лапласа функции (5) есть функция( )0,*tsAses-λ=λ+а для функции (6):( )0222.*stBses-μ=μ+Тогда спектральное разложение: ( )( )**A sB s-⋅ -( )( )1/ss+--=ψ ψ для рассматриваемой систе-мы примет вид( )( )()()()()002**222211221244.2SsttA s Bseesssssssss Показатели степени у экспонент с противоположными знаками здесь обнуляются, и эффект от операции сдвига исчезает. Квадратный трехчлен в числителе последнего выражения ()24ss+ μ-λ +()24,μ -λμ где ()4μ μ-λ >0 и ()4μ-λ >0 при μ>λ в случае стабильной системы, имеет два действительных отрицательных корня 1,s-2:s-()()()214/2 [ 4/2] 4,s- =- μ-λ + μ-λ- μ μ-λ()()()224/2 [ 4/2] 4.s- =- μ-λ - μ-λ- μ μ-λТогда мы придем к окончательному виду спектрального разложения:( )( )( )( )()()()()122.2* *1s ss s ssB sssAss+-ψ ++=ψλ- μ-+-⋅=Исходя из правил построения функций ( )s+ψи ( ),-ψs строим их в виде( )()()()122,2sss ssss+++ψ=μ+( ).ss-ψ =λ- Далее по методике спектрального разложения на-ходим константу:( )()122204lim1 ,44ssssKs+→ψμ μ-λ== == -ρμμкоторая представляет вероятность того, что очередное поступающее в систему требование застает ее свободной. Теперь построим функцию( )( )()()()()21212,sKss sss ss++-ρ μ+Φ= =ψ ++через которую получим преобразование Лапласа функции плотности времени ожидания в системе 2Ì /Å /1:--( )( )()()()()2*1212*.sWs s sss ss+-ρ μ+=Φ=++ (7)В [3] приведено уравнение Полячека - Хинчина для преобразования Лапласа функции плотности времени ожидания для системы М/G/1:( )()( )**1 ,sWssBs-ρ=-λ+λ(8)где ( )*Bs - преобразование Лапласа функции плотности времени обслуживания. Теперь предстоит доказать тождественность выражений (7) и (8). В нашем случае ( )*Bs=()222/4sμ +μ и после подстановки этой функции в (8) получим:( )()()()()()()()()()*22222121[2 / (2 )]1212,24sWssssssss ssss-ρ==-λ+λ μ μ+-ρ μ+-ρ μ+==++-λ μ + + λμтак как знаменатель раскладывается на множители вида()()()()()()222122444.sssssss ss-λ μ + + λμ ==++Следовательно, равенства (7) и (8) тожде ственны. Далее необходимо определить числовые характеристики сдвинутых распределений (5), (6). Они нужны, в свою очередь, для определения неизвестных параметров распределений (5), (6) по методу моментов. Определение числовых характеристик распределений -M и 2-E. Числовые характеристики сдвинутого экспоненциального распределения M- приведены в [1]. Средний интервал поступлений равен10.t-λτ=λ +(9)Коэффициент вариации интервалов поступлений выглядит как()10.1 tc-λ= +λ(10). Для определения числовых характеристик сдвинутого распределения Эрланга 2E- воспользуемся свойством преобразования Лапласа функ-ции плотности воспроизводить моменты: ()()0002*0022003022821/22.tssttssssdBdedsdssetetsss-==-=μ-μ+μμ=+= μ+μ+= -μ+= Отсюда среднее время обслуживания требований:10.t-μτ=μ +(11)Найдя вторую производную от преобразования Лапласа функции (8) при 0,=s определяем второй начальный момент интервала между поступлениями:2*200220()322.sdstBtds== ++μμ Отсюда определим коэффициент вариации времени обслуживания:()1021.ct-μ=+μ(12) Теперь оценим влияние параметра сдвига 0tна числовые характеристики рассматриваемых распределений. Для интервалов поступлений по закону M- коэффициент вариации cλ уменьшается при сдвиге в ()01t+λ раз по сравнению с коэффициентом 1cλ= для распределения M. Таблица. Результаты экспериментов для СМО М/E2/1 и 2Ì /Å /1-- Коэффициент вариации времени обслужива-ния для распределения 2Å:-cμ уменьшается при сдвиге в ()01t+μ раз по сравнению с коэффициентом 1/ 2cμ= для распределения Е2. Учитывая, что среднее время ожидания в системе G/G/1 связано с коэффициентами вариаций времени между поступлениями требований и времени обслуживания квадратичной зависимостью, в системе с запаздыванием время ожидания будет меньше, чем в обычной системе. Таким образом, для определения среднего времени ожидания мы можем использовать формулу (4) с параметрами / ,μλρ=τ τ где λτ и μτопределены (9) и (11), а μ рассчитываем из (11) при заданных ,μτλτ и параметре сдвига 0.t В качестве входных параметров для расчета системы 2Ì /Å /1-- удобнее брать ,λτ,μτ,cλcμ и 0.t Диапазоны изменения коэффициентов вариаций определяются, соответственно, выражениями (10) и (12): ( ) 0,1 ,cλ∈ а () 0,1/ 2cμ∈ в зависимости от величины параметра сдвига 00.t> В таблице приведены расчеты для системы 2Ì /Å /1-- при малой, средней и высокой нагруз-ках 0,1;ρ= 0,5; 0,9. При этих коэффициентах загрузки значения параметра сдвига 00, 01;t= 0,1; 0,5 и 0,9 обеспечивают определенные значения коэффициентов вариаций входного потока cλ и времени обслуживания cμ согласно равенствам (10) и (12). С уменьшением параметра сдвига 0t среднеевремя ожидания в системе 2Ì /Å /1-- стремится к значению среднего времени ожидания в обычной системе М/E2/1. Как и следовало ожидать, уменьшение коэффициентов вариации cλ и cμ влечет за собой сокращение времени ожидания. Заключение Полученные результаты позволяют сделать следующие выводы.1. Введение операции сдвига во времени в законы распределения, описывающие работу СМО, приводит к увеличению загрузки системы с запаздыванием. Для системы 2Ì /Å /1-- с запаздыванием загрузка увеличивается в 0(1 ) /t+μ0(1 )t+λ раз по сравнению с обычной системой М/E2/1.2. Однако операция сдвига уменьшает коэффициенты вариаций случайного интервала между поступлениями и времени обслуживания требований. В связи с тем что среднее время ожидания в системе G/G/1 зависит от квадратов этих коэффициентов вариаций, среднее время ожидания в очереди к системе с запаздыванием будет меньше, чем в обычной системе при одной и той же загрузке. Например, для системы 2Ì /Å /1--при загрузке 0,9ρ= и параметре сдвига 00,9t=коэффициент вариации интервалов поступления cλ уменьшается с 1 для обычной системы до 0,19 для системы с запаздыванием, коэффициент вариации времени обслуживания cμснижается с 1/ 2 до 0,071, а время ожидания сокращается с 6,75 единицы времени для обычной системы до 0,19 единицы.3. Изложенные результаты справедливы только для одинаковых параметров сдвига t0 для распределения интервалов между поступлениями требований и времени обслуживания.
×

About the authors

V. N Tarasov

Povolzhskiy State University of Telecommunications and Informatics

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

N. F Bakhareva

Povolzhskiy State University of Telecommunications and Informatics

Email: nadin1956_04@inbox.ru
Samara, Russian Federation

E. G Akhmetshina

Povolzhskiy State University of Telecommunications and Informatics

Email: elyamalusha@mail.ru
Samara, Russian Federation

References

  1. Тарасов В.Н., Бахарева Н.Ф., Блатов И.А. Анализ и расчет системы массового обслуживания с запаздыванием // Автоматика и телемеханика. 2015. No 11. С. 51-59. doi: 10.1134/S0005117915110041
  2. Тарасов В.Н. Расширение класса систем массового обслуживания с запаздыванием // Автоматика и телемеханика. 2018. No 12. С. 57-70. doi: 10.1134/S0005117918120056.
  3. Клейнрок Л. Теория массового обслуживания / пер. с англ. М.: Машиностроение, 1979. 432 с.
  4. Brannstrom N. A Queueing Theory analysis of wireless radio systems. Appllied to HS-DSCH. Lulea University of Technology, 2004. 79 p.
  5. RFC 3393 IP Packet Delay Variation Metric for IP Performance Metrics (IPPM). URL: https://tools.ietf.org/html/rfc3393 (дата обращения: 26.02.2016).
  6. Тарасов В.Н., Бахаpева Н.Ф., Липилина Л.В. Математическая модель телетрафика на основе системы G/M/1 и результаты вычислительных экспериментов // Информационные технологии. 2016. Т. 22. No 2. С. 121-126.
  7. Алиев Т.И. Аппроксимация вероятностных распределений в моделях массового обслуживания // Научно-технический вестник информационных технологий, механики и оптики. 2013. No 2 (84). С. 88-93.
  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. Legros B. M/G/1 queue with event-dependent arrival rates // Queueing Systems. 2018. Vol. 89. No 3. P. 269-301.
  11. Тарасов В.Н., Карташевский И.В. Способы аппроксимации входных распределений для системы G/G/1 и анализ полученных результатов // Системы управления и информационные технологии. 2015. No 3. С. 182-185.
  12. Тарасов В.Н., Горелов Г.А., Ушаков Ю.А. Восстановление моментных характеристик распределения интервалов между пакетами входящего трафика // Инфокоммуникационные технологии. 2014. Т. 12. No 2. С. 40-44.
  13. Тарасов В.Н., Малахов С.В., Карташевский И.В. Теоретическое и экспериментальное - исследование задержки в программно-конфигурируемых сетях // Инфокоммуникационные технологии. 2015. Т. 13. No 4. С. 409-413.
  14. Тарасов В.Н. Вероятностное компьютерное моделирование сложных систем. Самара: СНЦ РАН, 2002. 194 с.

Statistics

Views

Abstract: 76

PDF (Russian): 22

Dimensions

Article Metrics

Metrics Loading ...

PlumX


Copyright (c) 2020 Tarasov V.N., Bakhareva N.F., Akhmetshina E.G.

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