COMPARISON OF DIFFERENT APPROACHES FOR ESTIMATING THE AVERAGE WAITING TIME IN THE QUEUE FOR QUEUING SYSTEM Н2/Н2/1

Abstract


The article discusses two different approaches for estimating the average waiting time of a request in a queue for queuing systems with second order hyperexponential distribution of interarrival and service time. The first approach involves solving the Lindley integral equation using the spectral method and reduces to finding an expression for the spectral decomposition as a composition of two multipliers that would give a rational function of an argument. The second approach is based on the assumption of ergodicity of the initial sequence of waiting time for a request in a queue considering the rational form of the Laplace transform from the exponent. The key point of this approach is the usage of the characteristic function defined by the Laplace transform for the probability density function of the sum of the random variables. To calculate the average delay time in the queue, the parameters of hyperexponential distributions are determined with the approximation of random variables defining the interarrival and service time at the level of three moment characteristics. This approach is designed to improve the adequacy and reliability of queuing models. In addition, only for the input distributions of the queuing system described by the hyperexponential distribution of the second order we can get an analytical solution for average waiting time.

Full Text

Введение Для анализа и моделирования трафика современных компьютерных сетей и сетей телекоммуникаций широко используется класс субэкспоненциальных распределений, куда входят в частности распределения Вейбулла, гамма, логнормальное и гиперэкспоненциальное, имеющие коэффициенты вариации большие единицы и относящиеся к распределениям с «тяжелым хвостом». На рисунке 1 приведены фрагменты хвостов функций плотности этих распределений, а для сравнения приведено классическое экспоненциальное распределение. Слева от классического экспоненциального распределения приведен хвост сдвинутого экспоненциального распределения с коэффициентом вариации , (так называемый «легкий хвост»). Для всех приведенных распределений средние значения равны , а дисперсии для распределений с «тяжелым хвостом» равны , что дает коэффициент вариации интервала времени (далее оба ключевых термина употребляются без кавычек). Из теории массового обслуживания известно, что среднее время ожидания требований в системе при распределениях с тяжелым хвостом намного больше, чем у классической системы M/M/1. В настоящее время не существует аналитических методов для точного определения характеристик СМО G/G/1 или G/G/m, и как следствие, это отражается на степени адекватности стохастических сетевых моделей реальным компьютерным сетям и на качестве принимаемых проектных решений. Вместе с тем анализ характеристик любого сетевого устройства можно провести именно на основе модели системы массового обслуживания типа G/G/1, предполагая, что выполняются условия независимости интервалов времени между заявками и интервалов обслуживания в последовательности заявок [9]. Рисунок 1. Фрагменты хвостов функций плотности из класса экспоненциальных распределений Упрощения анализа можно достичь, аппроксимируя распределения с тяжелыми хвостами, входящие в систему G/G/1, гиперэкспоненциальными распределениями, представляющими собой распределение смеси пуассоновских потоков [8]. При этом система G/G/1 заменяется системой , где определяет плотность вероятности случайных интервалов времени между заявками в виде [10] , . (1) Аналогично, для плотности интервалов времени обслуживания заявок можно записать , . (2) Для сравнения, гиперэкспоненциальное распределение второго порядка Н2 (см. рисунок 1) из класса субэкспоненциальных распределений содержит три неизвестных параметра, в то время как остальные распределения с тяжелым хвостом (Вейбулла, гамма, логнормальное) содержат по два неизвестных параметра. Это позволяет аппроксимировать произвольные входные распределения с тяжелым хвостом на уровне трех моментов. Такой подход призван повысить адекватность и достоверность моделей массового обслуживания. Кроме того, только для входных распределений системы массового обслуживания, описываемых гиперэкспоненциальным распределением 2-го порядка Н2 можно получить решение для среднего времени ожидания аналитически [5]. Рассмотрим методы определения среднего времени ожидания в очереди для системы Н2/Н2/1. Подход на основе решения уравнения Линдли спектральным методом Исходя из (1) в системе Н2/Н2/1 интервалы между соседними требованиями входного потока распределены по закону . (3) Аналогично из (2) время обслуживания . (4) Основные характеристики системы G/G/1, как следует из [1], описываются известными из теории случайных процессов интегральными уравнениями типа Винера-Хопфа. Одно из этих уравнений в [1] выведено в форме интегрального уравнения Линдли: где - функция распределения вероятностей (ФРВ) времени ожидания требования в очереди, - ФРВ предельной случайной величины , где в свою очередь - время обслуживания n-го требования , - интервал времени между поступлением требований и . Первый подход подразумевает решение уравнения Линдли спектральным методом и сводится к тому, чтобы для выражения найти представление в виде произведения двух множителей, которое давало бы рациональную функцию от s [1]. То есть для нахождения распределения времени ожидания необходимо следующее спектральное разложение , где - преобразования Лапласа плотности распределения интервалов времени поступления и обслуживания соответственно, и некоторые рациональные функции от s, которые можно разложить на множители. В [2] показано, что среднее время ожидания в очереди может быть определено как , (5) где - и - отрицательные корни кубического уравнения , где , . Далее рассмотрим пример [6-7]. Пусть коэффициент загрузки СМО , где и средние значения интервалов между поступлениями и времени обслуживания. Рассмотрим для удобства случай нормированного обслуживания . Тогда средний интервал между поступлениями . Пусть коэффициенты вариаций интервалов между поступлениями и времени обслуживания , коэффициенты асимметрий . При этих значениях входных параметров СМО начальные моменты 2-го и 3-го порядков для обоих распределений соответственно будут: , , , . Как известно, для пуассоновского потока параметры , . При таких исходных данных, для определения неизвестных параметров входного распределений (3) и (4): , , p, , , q получим следующие системы уравнений: , (6) (7) решив которые найдем эти параметры. Решение системы (6) дает следующие результаты: , , , а системы (7) - , , . Тогда коэффициенты кубического уравнения будут равны: ; ; . Решение кубического уравнения тем же методом дает следующие корни: , , , и соответственно, среднее время ожидания (5) равно ед. времени. Подход на основе использования характеристической функции Второй подход основан на предположении эргодичности последовательности интервалов времени ожидания заявки в очереди с учетом рациональной формы преобразования Лапласа от экспоненты [3]. В частности, для плотности вида (1) преобразование Лапласа имеет вид . (8) Ключевым моментом этого подхода является использование характеристической функции, определяемой преобразованием Лапласа для плотности вероятностей суммы случайных величин , . Распределение суммы двух случайных величин в предположении их независимости определяется сверткой распределений слагаемых. Тогда в предположении эргодичности последовательности поведение ее плотности вероятностей может быть описано выражением , , где дельта-функция характеризует значение плотности при , а - k-мерная свертка плотностей вероятности величин . Теперь характеристическая функция последовательности независимых величин на основе свойства независимости слагаемых при вычислении характеристической функции суммы слагаемых определится в виде , где . С учетом формул (8), (1) и (2) для можно записать. . Последний результат принципиально упрощает факторизацию характеристической функции , что объясняется наличием только вещественных корней у полиномов числителя и знаменателя . Для системы определение необходимых корней требует решения кубического уравнения, которое задается следующим образом [3]: , (9) где , а коэффициенты определяются как . Среднее время ожидания определяется как где - отрицательные корни кубического уравнения (9). Если подставить полученные ранее значения , , , , , в (9), то получим кубическое уравнение , корнями уравнения будут являться ; подставив которые в выражение для среднего времени ожидания, получим среднее время ожидания . Заключение Выше рассмотрены два различных подхода к определению среднего времени ожидания в системе массового обслуживания Н2/Н2/1. Первый подход, основанный на спектральном методе решения интегрального уравнения Линдли, дал среднее время ожидания . Второй подход, основанный на предположении эргодичности последовательности интервалов времени ожидания заявки в очереди и учитывающий рациональную форму преобразования Лапласа от экспоненты дал результат . Сравнивая два полученных значения можно заметить их хорошее совпадение (разница составляет примерно 7%). Недостатком первого подхода является то, что аналитическое решение, основанное на вычислении моментов, легко получается только при использовании аппроксимации реальной системы G/G/1 системой Н2/Н2/1, что связано с решением систем уравнений (6) и (7) лишь для трех моментов используемых распределений. При использовании аппроксимации , что могло бы потенциально повысить точность расчетов среднего времени ожидания, потребуется вычисление большего числа моментов (соответственно порядка K+1 и L+1), что существенно усложнит задачу решения систем уравнений типа (6) и (7). При втором подходе переход к аппроксимации приведет только к повышению порядка линейного уравнения типа (9), что, однако, не снимает проблемы вычисления параметров, аппроксимирующих гиперэкспоненциальных распределений. Возможный вариант вычисления этих параметров рассмотрен в [4]. Кроме того, при втором подходе можно относительно просто показать, что распределение искомого времени ожидания заявки в очереди также удовлетворяет гиперэкспоненциальному распределению.

About the authors

Igor Viacheslavovich Kartashevskiy

Povolzhsky State University of Telecommunications and Informatics

Email: ivk@psuti.ru

Sergey Valerievich Malakhov

Povolzhsky State University of Telecommunications and Informatics

Email: malakhov-sv@psuti.ru

Ekaterina Mikhaylovna Mezentseva

Povolzhsky State University of Telecommunications and Informatics

Email: katya-mem@psuti.ru

References

  1. Клейнрок Л. Теория массового обслуживания. Пер. с англ. М.: Машиностроение. 1979. - С. 80-86.
  2. Тарасов В.Н., Карташевский И.В. Определение среднего времени ожидания требований в управляемой системе массового обслуживания Н2/Н2/1 // Системы управления и информационные технологии. - 2014. - Т. 57. - № 3. - С. 92-96.
  3. Карташевский И.В. Модель трафика для программно-конфигурируемых радиосетей // Радиотехника. - 2016. - № 6. - С. 124-129.
  4. Keilson J., Machihara F. Hyperexponential waiting time structure in hyperexponential system // Journal of the Operation Society of Japan. - 1985. - Vol. 28. - No. 3. - P. 242-250. doi: 10.15807/jorsj.28.242.
  5. Тарасов В.Н. Исследование систем массового обслуживания с гиперэкспоненциальными входными распределениями // Проблемы передачи информации. - 2016. - №1. - С. 16-26.
  6. Тарасов В.Н., Бахарева Н.Ф., Горелов Г.А., Малахов С.В. Анализ входящего трафика на уровне трех моментов распределений временных интервалов // Информационные технологии. - 2014. - №9. - С. 54-59.
  7. Тарасов В.Н., Карташевский И.В. Способы аппроксимации входных распределений для системы G/G/1 и анализ полученных результатов // Системы управления и информационные технологии. - 2015. - № 3. - С. 182-185.
  8. Feldmann A, Whitt W. Fitting mixtures of exponentials to long-tail distributions to analyze network performance models // Performance Evoluation 31. - 1998. - P. 245-279. doi: 10.1016/S0166-5316(97)00003-5.
  9. Jagerman D.L., Balcioglu B., Altiok T., Melamed B. Mean Waiting Time Approximations in the G/G/1 Queue // Queueing Systems. - 2004. - No.46. - P. 481-506. doi: 10.1023/B:QUES.0000027996.28824.89.
  10. Карташевский И.В., Сапрыкин А.В. Обработка коррелированного трафика в узле сети типа G/G/1 // Радиотехника. - 2017. - №10. - С. 119-125.

Statistics

Views

Abstract - 19

PDF (Russian) - 4

Cited-By


Article Metrics

Metrics Loading ...

PlumX

Dimensions


Copyright (c) 2019 Kartashevskiy I.V., Malakhov S.V., Mezentseva E.M.

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