MATHEMATICAL MODEL OF TRAFFIC WITH HEAVY-TAILED DISTRIBUTIONS BASED QUEUEING H 2/M/1

Full Text

Введение. Известно, что теория массового обслуживания (ТМО) не дает точного ответа при анализе систем с входными потоками, описываемыми «тяжелохвостными» (далее без кавычек) распределениями интервалов между требованиями, то есть систем типа G/M/1/, а тем более систем G/G/1. Весомость хвоста распределения в свою очередь влияет на величину задержки. При этом под хвостом распределения будем понимать функцию Q(x): Q{x) = Р{£ > х) = Q([x, оо)), где £ -некоторая случайная величина. Для описания трафика широко используют класс экспоненциальных распределений, включающий подкласс так называемых субэкспо-ненциальных распределений, куда входят распределения Вейбулла, гамма, логнормальное и гиперэкспоненциальное, имеющие коэффициенты вариации больше единицы (см. рис. 1) и относящиеся к распределениям с тяжелым хвостом (heavy-tailed distributions). На рис. 1 приведены фрагменты хвостов функций плотности этих распределений, а для сравнения приведено классическое экспоненциальное распределение с коэффициентом вариации ст = 1. Слева от классического экспоненциального распределения приведен хвост распределения, сдвинутого от нуля вправо экспоненциального распределения, с коэффициентом вариации сх = 0,5 - «легкого». На рис. 1 для всех приведенных распределений средние значения равны тх - 0,25 ; а дисперсии для распределений с тяжелым хвостом равны Dx = 0,25 ; что дает коэффициент вариации интервала времени ст = 2,0. Как видно из этих графиков, даже при сравнительно небольшом коэффициенте вариации распределения ст = 2,0 заметна тяжесть хвостов затухания приведенных выше функций плотностей по сравнению с экспонентой. Очевидно, что с увеличением параметра сх весомость хвоста распределения только возрастет. Рис. 1. Графики хвостов функций плотности из класса экспоненциальных распределений Таким образом, рассматривая только статистические характеристики второго порядка, можно получить определенное представление об отличии распределения времени между поступлениями трафикового процесса от экспоненциального распределения, соответствующего пуассоновско-му потоку. С учетом статистики третьего порядка это отличие может только усилиться. Из теории телетрафика известно, что задержки при использовании тяжелохвостных распределений в системах массового обслуживания намного выше, чем при пуассоновском потоке. И наоборот - при использовании распределений с легким хвостом задержки ниже, чем при пуассоновском потоке. Распознавание закона распределения интервалов времени для его использования в моделях массового обслуживания вызывает большие проблемы, и к тому же трафик, как случайный процесс, имеет свойство постоянно меняться. Поэтому целесообразнее использование числовых характеристик распределения интервалов между пакетами. Для их определения предлагается использовать программу Wire shark [2], к которой авторами написано приложение, позволяющее определить моментные характеристики интервалов между пакетами входящего трафика. Удобство использования данного анализатора обусловлено тем, что он фиксирует моменты времени поступления пакетов агрегированного трафика на уровне долей миллисекунды. Для того чтобы воспользоваться этими результатами, необходим математический аппарат, представленный ниже. Анализ и расчет среднего времени ожидания для СМО Н2/М/1 Из класса субэкспоненциальных распределений только для гиперэкспоненциального распределения 2-го порядка Н2 можно получить явное решение для среднего времени ожидания требования в очереди в системе. Следующим преимуществом данного закона распределения является возможность аппроксимации произвольных входных распределений с его помощью на уровне трех моментов. Поэтому рассмотрим СМО Н2/М/1, где Н2 (см. рис. 1) - обозначение гиперэкспоненциального распределения 2-го порядка времени поступления требований в систему с функцией плотности a(t) = + (і - р)Л2е~^, (1) а M - обозначение экспоненциального закона обслуживания с функцией плотности b{t) = ре~й. (2) «Инфокоммуникационные технологии» Том 12, № 3, 2014 38 Тарасов В.Н., Бахарева Н.Ф., Горелов Г. А. Преобразование Лапласа функции (1) имеет вид J*(s) = j а функции (2) : B*(s) = Xi s + +(i-P) S + (3) (4) Для исследования системы G/G/1, как известно например из [2], используется интегральное уравнение Линдли: W(y) = У \w(y-u)dC(u)\ у> О, (5) 0; у< о, где W(y) - функция распределения вероятностей (ФРВ) времени ожидания требования в очереди; С(и) - ФРВ предельной случайной величины U = \imUn =хп - tn+l, где в свою очередь Хп Л->°о - время обслуживания n-го требования CB ; tn+l - интервал времени между поступлением требований Сп и Си+1. Суть решения уравнения (5) спектральным методом сводится к тому, чтобы для выражения А В* (5^)-1 (6) найти представление в виде произведения двух множителей, которое давало бы рациональную функцию от s [2]. Таким образом, для нахождения распределения времени ожидания необходимо следующее спектральное разложение см. (7): V- ■W ¥ л Я) -5 ¥ -W (7) где ^+(is) и некоторые рациональные функции от s, которые можно разложить на множители. Функции ^+(ä) h^_(s) должны удовлетворять определенным условиям согласно [3]: - для Re(s)>0 функция ^+(s) является аналитической без нулей в этой полуплоскости; - для Re(>s)<.D функция^ (s) является аналитической без нулей в этой полуплоскости, где D - некоторая положительная константа, определяемая из условия: a{t) lim t-> 00 е -Dt <00. (8) Кроме того, функции ^+(.у) и^_(.у) должны обладать следующими свойствами: для Re(,s) > 0 lim = 1; “ “ .&) (9) для Re(s) < 0 lim ¥- ■ = -1. iSl ->00 Выражение А * (- s) • В * (5) -1 = для распределений (1)-(2) с учетом (3)-(4) имеет вид (10), где коэффициенты «О = ^1^2 ’ ^1 = 1 (і - Р)^2 • В числителе правой части равенства (10) получился многочлен от s третьей степени, и нам остается определить его коэффициенты для разложения многочлена на множители. Коэффициенты многочлена в числителе дроби приведены в таблице 1. Я2 -5 -1 = JU + S \p^(s + Z2)+(].-p)À2(s + \)\-s\à2 -sfoi + s) -s\x2 -s)fai + s) ju(a0 - a.s)- (à, - s\à2 -s\ju + s) {^-s^-sXfit + s) ' 5(52 -C25-Cj) s) (11) (10) ¥+(s) = ¥-{s) {s-^X^2~sXp + s) = + ‘S’i ~ ^2 ) (s-A^fa-sX/i + s)’ где ґ ^2 ^2 \ ” sx = -{л l-Cj ) - отрицательный 4 1 2 корень квадратного уравнения в числителе дро- I 2 ■ + сj - положительный коби, ,2=у + ^( ч рень. На рис. 2 показано расположение нулей ЛА\ . «Инфокоммуникационные технологии» Том 12, № 3, 2014 Тарасов В.Н., Бахарева Н.Ф., Горелов Г. А. 39 (кружочки) и полюсов (крестики) на комплексной s-плоскости для функции (11). Таблица 1. Коэффициенты многочлена в числителе дроби (10) Степени слагаемых в числителе дроби Коэффициенты многочлена s° 0 s1 ц[Я.і(і-^)+А,2^]-Я,іЯ,2 scj s2 ^1 +Х2 -Ц = с2 s3 -1 Исследуем знаки корней Sj и s2, чтобы убедиться в сказанном. Для этого вспомним, что среднее значение интервала между требо- г ( p (i-р) ваниями есть x3i = \ t a\t)at = - + -. о Лг Тогда средняя интенсивность входного потока Я, Я2 т 12 Так как в стацио- * = ТҐ = рЛ2 + (1 - p)A^ нарном режиме загрузка р = - <1, то Я<//. От- Р сюда следует, что A^X2 < р\рл2 + (і - рК ] и коэффициент Cj > 0. Тогда один корень будет отрицательным (-Sj), а второй корень (s2 ) - положительным. -ІЄ S плззъгстъ ЛІ Зі Л] Рис. 2. Нули и полюсы функции (s)/ ^-(5) для системы Н /M/1 С учетом знаков корней и условий (8) строим рациональные функции ^+(s)h \//_{s)\ (д)=д(д+ді), у, ^)=tzAXV^). (12) s + JU - - Vs - s, Функции (11) удовлетворяют также и условиям (9). Следуя [2], определим постоянную * = iimt^£) = lim£±£L s-> 0 с 5->° S + /л /л ^2 ^2 і \ где sl = J- + Cj - -. Тогда функция (5) по зволяет найти преобразование Лапласа для ФРВ времени ожидания wbY ®.М=- К _ Sj(s + //) yr+(j) //s(s + Sj)‘ Заметив, что s<I>+(s) = W * (5) есть преобразование Лапласа для функции плотности времени ожидания, получим у»(,)=Ч(* + Л) //(s + sj (13) Отсюда dw*{s) = siÀsi +s)-sl{s + p)p ds p? (5 + 5j )2 Учитывая свойство преобразования Лапласа, найдем среднее время ожидания: " 1 1 w = _dW(s) ds s=o -sf /л + p2sl 2 2 P *1 Окончательно среднее время ожидания r=F-i Si p p (14) где Si = ^2 ^2 1 0 + Cj -- ; c2=Àl+À2-jU- 4 ‘ 2 Ci = р[ЛІ(і-р)+Л2р]-ЛІЛ2. Практическое применение полученных результатов С помощью авторской программы-приложения к анализатору трафика Wireshark был проанализирован файл с данными о трафике, поступающем на прокси-сервер вуза почти за час съема. Входной файл содержал более 2150000 строк, обработка вручную которых не представляется возможным. Результаты по моментным характеристикам интервалов между пакетами в секундах входящего трафика (см. на рис. 3). Полученные данные свидетельствуют о том, что анализируемый трафик сильно отличается от пуассоновского (коэффициент вариации с = 3,43 вместо единицы), значение коэффициента асимметрии As = 10,25 - это говорит о том, что распределение интервалов между пакетами трафика от- «Инфокоммуникационные технологии» Том 12, № 3, 2014 40 Тарасов В.Н., Бахарева Н.Ф., Горелов Г. А. носится к распределениям с тяжелыми хвостами. Например, у экспоненциального закона As = 2. Файл Справка Начальный момент 1-го порядка : 5,097781е-003 л Начальный момент 2-го порядка : 3,3258376-004 Начальный момент 3-го порядка : 5,505049е-005 Дисперсия : 3,065963е-004 Коэффициент вариации: 3,434807е+000 Асимметрия : 1,025441е+001 Количество пакетов: 628183 V Рис. 3. Результат работы программы-приложения анализа лог-файлов Рассмотрим результат (13) на примере рассматриваемого входного распределения с весомым хвостом (см. рис. 3). С использованием преобразования Лапласа (3) определим начальные моменты распределения (1): = - + Р , (1 ~Р) 4 = 2р і 2^~р). 4 4 ’ = бр б(і-р) 4 4 ' (15) Подставив в систему (15) полученные результаты по начальным моментам распределения интервалов между пакетами (см. рис. 3), для определения неизвестных параметров входного распределения (1): Хх,Х1 и р, получим следующую систему уравнений: = 5,0978е - 003 ; Я, А, 1р 2(1-р) 4 4 вр б(і -р) 4 = 3,3258е-004 ; = 5,5050е-005, (16) решив которые найдем эти параметры. Решение системы (16) в пакете Mathcad дает следующие результаты: /? « 0,950; /^«417,985; Я2 «17,556. Промежуточные параметры: сх « 2,429 ж 103 ; с2 « 174,441 ; я2 « 12,962 ; среднее время ожидания в очереди W « 0,073 с. Определим для сравнения среднее время ожидания для системы М/М/1. В нашем случае загрузка канала составляла /7 = 0,75, соответственно среднее время обслуживания пакетов ти «0,0038; интенсивность обслуживания р « 263.2 . Тогда среднее время ожидания паке- 0,011 с. тов W = ^ 1-/7 Таким образом, модель массового обслуживания с учетом весомости хвоста входного распределения демонстрирует задержку примерно в 6,6 раза большую, чем классическая модель. Заключение Для расчета характеристик реального трафика требуется обновленный математический аппарат. Полученные результаты свидетельствуют о том, насколько оптимистичные результаты дает классическая система М/М/1 по сравнению с рассмотренной системой Н2/М/1 в случае высокой весомости хвоста распределения входного потока. Поэтому данный результат с успехом может быть применен в современной теории телетрафика, где задержки пакетов входящего трафика играют первостепенную роль. Заметим, что распределение (1), содержащее три неизвестных параметра Л1,Я2 ир, позволяет с помощью метода уравнений моментов (14) аппроксимировать неизвестные входные распределения на уровне трех первых моментов.

About the authors

V. N Tarasov

Email: vt@ist.psati.ru

N. F Bakhareva

Email: bahareva-nf@psuti.ru

G. A Gorelov

Email: gleb_fox@bk.ru

References

Supplementary files