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

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

Supplementary files