OPTIMISING H2/M/1 SYSTEM CHARACTERISTICS CALCULATION

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

Supplementary files