OPTIMISING H2/M/1 SYSTEM CHARACTERISTICS CALCULATION

Abstract


Currently, there are no analytical methods for precisely determining the characteristics of queuing systems G/M/1 or G/M/m, and this lowers the degree of adequacy of stochastic network models to real computer and telecommunications networks and the quality of design decisions. This article shows the comparative results presented in various publications devoted to the calculation of the average waiting time in queuing systems G/M/1, in particular queuing system with hyper-exponential arrival rate. The results under consideration were obtained by completely different approaches, but the final calculated results are completely identical. These approaches have certain advantages to each other. Using of the analogues simplifies calculation of the characteristics for the system considered, and the author’s approach expands the possibilities of calculating characteristics in terms of determining higher-order moments for the waiting time, which allows extracting information needed to calculate a jitter, for example. Considering the definition of jitter in telecommunications as the spread of the waiting time from its average value, knowledge of higher order moments for the waiting time makes it possible to obtain the jitter value via calculating the variance, i.e. second moment of random waiting time.

Full Text

Введение В настоящее время не существует аналитических методов для точного определения характеристик СМО G/M/1 или G/M/m, и как следствие, это отражается на степени адекватности стохастических сетевых моделей реальным компьютерным и телекоммуникационным сетям и на качестве принимаемых проектных решений. Перспективным на взгляд авторов является такой подход к анализу систем G/M/1 или G/M/m, когда в качестве входного распределения G будет использована вероятностная смесь двух экспоненциальных распределений, то есть гиперэкспоненциальное распределение Н2. При этом СМО с гиперэкспоненциальными входными распределениями в отличие от систем с более сложными с распределениями, позволяет получить решение задачи в аналитическом виде. Тот факт, что такие распределения имеют место на практике, подтвержден в работах [1-4], где приведены результаты анализа интервалов между пакетами входящего трафика на сервер ВУЗа, полученные с помощью программы - дополнения к анализатору Wireshark. Также в работах [1-4] авторами приведены полученные результаты для времени ожидания в системе Н2/M/1 и их практическое применение, а в работе [5] - для системы Н2/Н2/1. Так же приведено преобразование Лапласа-Стильтеса для функции плотности времени ожидания для системы Н2/M/1, полученное через решение интегрального уравнения Линдли методом спектрального разложения [6]. В зарубежной литературе [7] известны эвристические формулы для систем G/M/1 и G/G/1: в частности, для системы Н2/M/1 приведено выражение для среднего времени ожидания: , (1) где промежуточные параметры: , , , а , , - начальные моменты до третьего порядка интервалов между поступлениями требований в систему. Выражение (1) получено с помощью преобразования Лапласа-Стилтьеса функции распределения, и это преобразование приведено также в [6]. Постановка задачи В статье ставится задача качественного сравнения авторских результатов с результатами из зарубежных источников. Решение (1) в работе [7] получено с использованием результата [6]: , (2) где 0 < σ < 1 - корень уравнения (3) где F* - преобразование Лапласа-Стильтеса для функции гиперэкспоненциального распределения Далее в [6] найден нужный корень уравнения (3) в виде где µ - интенсивность обслуживания экспоненциального закона M, а p, λ1, λ2 - параметры гиперэкспоненциального распределения, которые должны быть определены методом моментов из системы уравнений: . (3) В [1-4] значения p, λ1, λ2 для широкого диапазона изменения параметров трафика определялись с использованием пакета Mathcad. В [7] вместо использования пакета удалось параметры гиперэкспоненциального распределения p, λ1, λ2 выразить через начальные моменты интервалов между поступлениями требований в систему , , до третьего порядка включительно. Окончательно корень уравнения (3) имеет вид: (4) После подстановки (4) для σ в (2) получается окончательный результат (1) для среднего времени ожидания в системе Н2/M/1. В этом случае указанные начальные моменты будут входными параметрами для расчета характеристик системы. Заметим, что данные результаты получены с помощью преобразования Лапласа-Стилтьеса функции гиперэкспоненциального распределения. Решение задачи В [1; 8] приведен подробный вывод решения для времени ожидания в системе Н2/M/1. Получено преобразование Лапласа-Стилтьеса функции плотности времени ожидания для системы Н2/M/1 путем решения интегрального уравнения Линдли методом спектрального разложения: , (5) где - значение отрицательного корня со знаком минус квадратного уравнения (6) с коэффициентами , . Величины являются параметрами гиперэкспоненциального закона распределения с функцией плотности . (7) для системы Н2/M/1. Окончательно для среднего времени ожидания получен результат: . (8) В отличие от результата (1) в [7], выражение (4) в авторской работе позволяет определить и моменты высших порядков для времени ожидания. Это будет преимуществом перед результатом [7]. Например, начальный момент второго порядка времени ожидания равен значению второй производной от преобразования (5) в точке и будет иметь вид . (9) В свою очередь, начальный момент второго порядка позволяет определить дисперсию времени ожидания: . Учитывая определение джиттера в телекоммуникациях как разброс времени ожидания от его среднего значения [10], тем самым получим возможность определения джиттера через дисперсию. Это является важным результатом для анализа трафика, чувствительного к задержкам. Теперь установим связь между величинами σ из (2)-(3) и из выражений (5) и (8). Для этого вспомним, что величина σ получена из преобразования Лапласа-Стилтьеса функции распределения F(t), а - из преобразования Лапласа-Стилтьеса функции плотности a(t). Следовательно, по свойству преобразования для функции плотности , преобразование Лапласа будет иметь вид , где преобразование Лапласа функции распределения F(t). Из этого факта после проведения не сложных преобразований над и получим: или . Таким образом, подставив выражение для в (8) получим рабочую формулу для определения среднего времени ожидания для системы Н2/M/1: (10) где параметр σ определяется выражением . Здесь промежуточные параметры:, , , а , , - начальные моменты до третьего порядка интервалов между поступлениями требований в систему, через которые выражаются параметры q и r. Использование выражения (10) не предполагает решения системы (3) в математических пакетах и значительно упрощает расчет среднего времени ожидания для системы Н2/M/1. Как было отмечено выше, начальные моменты: , , являются входными параметрами для определения среднего времени ожидания для системы Н2/M/1. Отсюда возникает естественный вопрос: любые ли значения начальных моментов , , позволяют аппроксимировать произвольные распределения гиперэкспоненциальным законом вида ? Данный вопрос может быть переформулирован иначе: при любых ли значениях начальных моментов: , , система (3) имеет решение относительно параметров p, λ1, λ2 гиперэкспоненциального закона распределения? Эти вопросы исследованы в [9] и ответ получен в виде следующего ограничения: . (11) Следовательно, при аппроксимации произвольных законов распределений гиперэкспоненциальным законом, необходимо придерживаться ограничения (11). Проверим корректность выражения (10) на примере. Для системы Н2/M/1 возьмем следующие входные параметры: ; ; . При нормированном времени обслуживания µ = 1 выбранное значение даст коэффициент загрузки ρ = 9/10, а моменты высщих порядков соответствуют коэффициенту вариации, равному 2 и асимметрии, равной 4. Значения промежуточных параметров для вычисления корня σ в этом случае: q = 7,5; r = 2,5. Тогда значение корня σ ≈ 0,959 и следовательно, значение среднего времени ожидания из выражения (10) W ≈ 23,453. Точно такой же результат дает и формула (1) или (2). Таким образом, авторский результат (10) полностью идентичен результатам (1) и (2). Особенности моментной аппроксимации гиперэкспоненциального закона В [1-4] отмечена особенность гиперэкспоненциального распределения, заключающаяся в возможности его аппроксимации как на уровне двух первых моментов, так и на уровне трех моментов. При этом в первом случае результаты по задержке получаются заниженными, то есть более оптимистичными, по сравнению со вторым случаем. При аппроксимации на уровне двух первых моментов результаты по задержке хорошо согласуются с результатами [10], где также использован метод двухмоментной аппроксимации. Для объяснения данного факта рассмотрим характерный пример [8]. Пусть коэффициент загрузки СМО , где и средние значения интервалов между поступлениями и времени обслуживания. Рассмотрим случай нормированного обслуживания, когда выбранная ед. времени. Тогда средний интервал между поступлениями (ед. времени). Пусть коэффициент вариации случайной величины - интервала времени между поступлениями . Аппроксимация на уровне двух первых моментов дает: , , . Среднее время ожидания в этом случае равно ед. времени. Теперь к имеющимся двум моментам добавим третий в виде коэффициента асимметрии . При тех же значениях входных параметров СМО начальные моменты второго и третьего порядков для распределения (8) соответственно будут: , . Подставив эти данные в систему (3) и решив ее, получим ; ; . Среднее время ожидания ед. времени, что и подтверждает сказанное выше насчет задержки. Таким образом, получили две совершенно различные аппроксимации гиперэкспоненциального распределения. На рис.1 приведены графики функции плотности для двух этих случаев. Рис. 1. Графики функции плотности (7): 1 - аппроксимация закона распределения H2 на уровне двух моментов; 2 - на уровне трех моментов Заключение Проведенный сравнительный анализ авторских результатов с результатами из зарубежных источников показал их полную идентичность несмотря на разницу в подходах их получения. Кроме того, такой анализ позволил авторам оптимизировать расчет характеристик для системы Н2/M/1 в смысле упрощения расчетов. После этого стали возможны расчеты без применения математических пакетов. Такой подход может также упростить расчеты характеристик для более сложной системы Н2/ Н2/1, рассмотренной авторами в работах [1; 5].

About the authors

Veniamin Nikolayevich Tarasov

Povolzhskiy State University of Telecommunications and Informatics

Email: tarasov-vn@psuti.ru

Nadezhda Fedorovna Bakhareva

Povolzhskiy State University of Telecommunications and Informatics

Email: bakhareva-nf@psuti.ru

Igor Viacheslavovich Kartashevskiy

Povolzhskiy State University of Telecommunications and Informatics

Email: ivk@psuti.ru

Liudmila Vladimirovna Lipilina

Povolzhskiy State University of Telecommunications and Informatics

Email: mila199113@gmail.com

References

  1. Тарасов В.Н. Исследование систем массового обслуживания с гиперэкспоненциальными входными распределениями // Проблемы передачи информации. 2016 - №1. - С.16-26.
  2. Тарасов В.Н., Горелов Г.А., Ушаков Ю.А. Восстановление моментных характеристик распределения интервалов между пакетами входящего трафика // Инфокоммуникационные технологии, 2012. - Т.12. - №2. - С.40-44.
  3. Тарасов В.Н., Бахарева Н.Ф., Горелов Г.А., Малахов С.В. Анализ входящего трафика на уровне трех моментов распределений временных интервалов // Информационные технологии. 2014. - №9. - С.54-59.
  4. Тарасов В.Н., Бахарева Н.Ф., Горелов Г.А. Математическая модель трафика с тяжелохвостным распределением на основе системы массового обслуживания Н2/М/1 // Инфокоммуникационные технологии. 2014. - Т.12. - №3. - С.36-41.
  5. Тарасов В.Н., Карташевский И.В. Определение среднего времени ожидания требований в управляемой системе массового обслуживания Н2/Н2/1 // Системы управления и информационные технологии. 2014. - №3. - С. 92-96.
  6. Клейнрок Л. Теория массового обслуживания. // Пер. с англ. М: Машиностроение, 1979. - 432 с.
  7. 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. Elsevier Science Publishers, 1991. - Р. 683-688.
  8. Тарасов В.Н., Бахарева Н.Ф., Липилина Л.В. Математическая модель телетрафика на основе системы G/M/1 и результаты вычислительных экспериментов // Информационные технологии. 2016. - №2. - С. 121-126.
  9. Whitt W. Approximating a point process by a renewal process: two basic methods // Operation Research, 30. 1982. - №1. - Р. 125-147. doi: 10.1287/opre.30.1.125.
  10. Кругликов В.К., Тарасов В.Н. Анализ и расчет сетей массового обслуживания с использованием двумерной диффузионной аппроксимации // Автоматика и телемеханика. 1983. - №8. - С. 74-83.
  11. Standards Track. RFC 3393 IP Packet Delay Variation Metric for IP Performance Metrics (IPPM) // URL https://tools.ietf.org/html/rfc3393 (д.о. 26.02.2017)

Statistics

Views

Abstract - 25

PDF (Russian) - 3

Cited-By


Article Metrics

Metrics Loading ...

PlumX

Dimensions


Copyright (c) 2017 Tarasov V.N., Bakhareva N.F., Kartashevskiy I.V., Lipilina L.V.

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