Estimate Jitter in the G/M/1 System Based on Hypreexponential Distributions

Full Text

В настоящее время производительность сети является одним из ключевых направлений в исследовании телекоммуникационных сетей. Для анализа производительности сети и повышения качества обслуживания (QoS - Quality of Service) необходима разработка новых методов, основанных на математических моделях реального трафика. Для решения данной задачи, как правило, применяется теория систем массового обслуживания. Однако ввиду отсутствия адекватных моделей современного трафика зачастую для анализа используется пуассоновская модель [1]. Проблемы, связанные с разработкой моделей трафика и сетей обработки трафика, обусловлены разнородностью обрабатываемых потоков, статистической структурой современного трафика, необходимостью учитывать конвергенцию инфокоммуникационных технологий, что может реально влиять на оценки производительности разрабатываемых сетей [2]. Анализ качества обслуживания в инфокоммуникационных сетях, как правило, направлен на оценку задержки. При этом не менее важной характеристикой качества функционирования сети является джиттер. Для некоторых приложений джиттер выступает более значимым параметром, чем задержка. Особенно важно это для мультимедийных потоков. Учитывая, что мультимедийный трафик в современных сетях занимает все большую долю, проблема оценки джиттера становится все актуальней. Свидетельство сложности трафика проявляется в таких формах, как наличие корреляционных связей, долговременные зависимости или самоподобие, которые обнаруживаются при статистическом анализе реализаций трафика [2-4]. Данные явления изучаются давно, и существуют достаточно убедительные доказательства их значительного влияния на показатели функционирования сетей [5; 6]. Эффект самоподобия во многом определяется характером поведения пользователей, организацией запросов, особенностью работы протокола TCP. Для характеристик, описывающих интен- . Для характеристик, описывающих интенсивность поступления пакетов, их длительности, более точные оценки показывают статистические модели, основанные на распределениях с тяжелыми хвостами, таких как Парето и Вейбулла. При этом следует учесть тот факт, что конкретный тип распределения, лежащий в основе математической модели, значительно зависит от конкретной реализации трафика и требует тщательного анализа. Другой проблемой, связанной с использованием распределений с тяжелыми хвостами, является сложность их анализа и использования. В том числе необходимо получить преобразования Лапласа этих распределений, при этом нет удобного выражения для преобразований Лапласа распределений Парето и Вейбулла. Самоподобный характер современного трафика необходимо учитывать и при оценке джиттера или изменения задержки пакетов. Как правило, такая оценка базируется, как и при оценке задержки, на основе математического аппарата теории массового обслуживания. Современные системы, обрабатывающие непуассоновский трафик, лучше описываются моделями G/G/1. В работах [7-9] представлены результаты оценки джиттера с использованием аналитического и имитационного моделирования. Реализуемые в этих работах подходы весьма трудоемки. Одним из возможных вариантов использования методов классической теории массового обслуживания при обработке самоподобного трафика является вариант аппроксимации системы G/G/1 системой 22 1, // HH имеющей гиперэкспоненциально распределенное время поступления и обслуживания. Развитием такого подхода стало использование аппроксимации системой 1. // K L HH В [10] было установлено, что применение смеси экспоненциальных распределений является теоретически обоснованным подходом к моделированию IP-трафика. Модель 1 22 // HH может быть использована в различных подходах описания систем. Например, в [2] приведена методика анализа функционирования сети при обработке самоподобного трафика с использованием гиперэкспоненциального распределения, где первая компонента распределения показывает экспоненциальную составляющую, а вторая описывает поведение тяжелого хвоста. Но данный подход также достаточно трудоемкий для оценки сетевых параметров и требует анализа распределений с тяжелыми хвостами. Более удобными являются подходы с применением аппроксимации с суммой двух экспонент [10]. Анализ джиттера IP-сети Под джиттером понимают либо среднюю абсолютную вариацию задержки, либо изменение задержки в потоке от некоторого минимального значения [12]. В соответствии с рекомендацией IETF (Internet Engineering Task Force - Специальная комиссия интернет-разработок) [13] под джиттером понимается случайная переменная , i J определяемая как 11 , i ii J TT ++ = - где i T - время задержки i-го пакета в узле сети, которое определяется в виде , i ii TWQ + = где i W - время ожидания i-го пакета в очереди и i Q - время его обслуживания. Основываясь на [7-9; 14] и на предположении Линдли [1], заключающемся в том, что ( ) 1 i + -й пакет не будет ждать в очереди при выполнении условия, что интервал времени между приходом ( ) 1 i + -го и i-го пакета больше, чем время задержки i-го пакета в узле сети, получим: 1 1 1 0, â äð. ñëó÷àå. ïðè i i i ii VT W WQV + + + ≥  =  +-  Исходя из этого, джиттер определим следующим образом: 11 1 11 , ïðè â äð. ñëó÷àå. ii i i ii QT VT J QV ++ + ++ - ≥ =  -  Если предположить случайные величины , i T i Q и i V независимыми между собой и не коррелированными в структуре каждой последовательности случайной величины, индекс i у соответствующих плотностей вероятностей можно отбросить и ввести обозначения: ( ) T fx - плотность вероятностей случайной величины Т, ( ) V fy - плотность вероятностей случайной величины V и ( ) Q fz - плотность вероятностей случайной величины Q. В [7; 9] показано, что среднее значение джиттера определяется в соответствии со следующим выражением: ( ) ( ) ( ) ( ) ( ) 1 00 0 . ii V Q y TT y J ET T f y f z z x f x dx z y f x dx dzdy ∞∞ + ∞ = -= ×  × - +-    ∫∫ ∫∫ (1) При известных или приближенных функциях плотности вероятностей случайных интервалов времени между поступлениями пакетов, времени обслуживания и времени ожидания пакета в очереди выражение (1) позволяет оценить среднее значение джиттера для системы обслуживания G/G/1. В случае когда плотность распределения вероятностей какой-либо реализации либо практически невозможно, либо весьма затруднительно описать конкретным законом распределения, можно описать ее смесью распределений. Для (1) функции ( ),T fx ( ) V fy и ( ) Q fz можно представить в виде смеси показательных распределений, которые предпочтительней для описания и моделирования трафика IP-сети [10]. Если произвольную плотность вероятностей в системе G/G/1 обозначить как ( ), fx то задача аппроксимации ( ) fx с использованием гиперэкспоненциальных распределений может быть представлена в виде ( ) ( ) ( ) 1 , = = = ∑ N N ii i fx H x phx (2) где ( ) i hx - функция правдоподобия i-й компоненты смеси; ( ) ; i x hx e -α = α 0 p ≥ - вероятность; 1 1. N i i p = = ∑ В случае применения модели 1 22 // HH выражение (2) можно представить в виде ( ) ( ) 12 12 . 1 xx fx pe p e -α -α =α +- α Использование гиперэкспоненциального распределения в качестве примера произвольного распределения G позволяет получить достаточно точные результаты при незначительных вычислительных затратах. При этом необходимо обозначить параметры каждой экспоненциальной составляющей распределения. Интервалы между отсчетами реализации трафика, распределенные по закону ( ), V fy определяются параметром γ: ( ) ( ) 12 12 , 1 xx ax p e p e -γ -γ =γ +- γ время обслуживания - ( ),Q fz определяется параметром µ: ( ) ( ) 12 12 , 1 xx bx q e q e -µ -µ =µ +-µ транзитное время - ( ) , T fx определяется параметром δ: ( ) ( ) 12 12 . 1 xx cx g e g e -δ -δ =δ +- δ В [14] показан подход с использованием гиперэкспоненциальной аппроксимации плотностей ( ) V fy для интервалов времени между поступлениями и ( ) Q fz для интервалов времени обслуживания. При этом было принято, что ( ) W f ⋅ - показательное распределение, имеющее вид ( ) , W fe -δτ τ=δ где параметр δ определяется как ( ) 1 δ=µ -ξ [1]; ξ - корень уравнения ( ) , V ξ = Λ µ - µξ где V Λ - преобразование Лапласа плотности ( ); V f ⋅ µ - средняя интенсивность обработки пакета в системе G/M/1. Следовательно, ( ) c x можно записать в виде ( ) . x cx e -δ = δ Учитывая вышесказанное, можно принять следующее представление для плотностей ( ) V f ⋅ и ( ): Q f ⋅ ( ) ( ) 12 12 1 ; V f pe p e -γ τ -γ τ τ= γ + - γ (3) ( ) ( ) 12 12 1 . Q f qe q e -µ τ -µ τ τ=µ + - µ (4) Так как для времени задержки пакета в системе i T справедливо , i ii TWQ + = то плотность вероятности ( ) T f ⋅ определяется сверткой распределений (при выполнении условия независимости случайных величин W и Q): ( ) ( ) ( ) ( ) 12 0 2 1 12 . 1 T WQ yy f y f u f y u du q q ee ∞ -µ -µ = -= δ- µ δµ = + δ-µ δ-µ ∫ В итоге получены все плотности, входящие в (1), следовательно, можно оценить среднее значение джиттера, учитывая соотношение: ( ) ( ) ( ) ( ) ( ) 00 . y z TT y T z z x f x dx z x f x dx x z f x dx -=- + +- ∫∫ ∫ Окончательный результат выражения для расчета джиттера [14]: 12 12 11 1 1 2 12 22 1 2 2 12 1 11 12 12 2 21 22 21 12 121 12 () (1 ) (1 ) 2 (1 ) 22 2(1 ) (1 ) 22 (1 ) 2 (1 ) J AB Ap p Bp p qA p p qB p p A q Bq pp =α +α + -  γ -γ - +-  µ µ +γ µ +γ   γ -γ - ++  µ µ +γ µ +γ   γ -γ + ++  µ µ +γ µ +γ   - γ -γ + ++  µ µ +γ µ +γ   - + +×  µµ  γ -γ ×+ µ +µ +γ µ +µ 2 ,   +γ  (5) где [ ] 12 1 2 1 12 1 2 ( ) (1 ) , () Bq A q µ-µ µ- - µ α= µµ µ +µ 12 2 12 (1 ) , qq µ - +µ α= µµ ( ) 12 1 ,. q q AB δ- δ = = δ-µ δ-µ Для получения значения джиттера, согласно выражению (5), необходимо знание параметров распределений ( ) V f ⋅ и ( ) Q f ⋅ и ( ) ,W f ⋅ то есть ( ) 12 ,, p γγ и ( ) 12 ,, q µµ и . δ Для определения параметров гиперэкспоненциальных распределений (3) и (4) воспользуемся подходом, показанным в [15; 16], где представлена методика определения параметров по двум моментам (среднее, дисперсия) исходного распределения для независимых случайных величин. В [15; 16] показано, что для получения аналитических выражений начальных моментов гиперэкспоненциальных распределений до второго порядка, основанный на использовании свойства преобразования Лапласа, и для (3): ( ) 12 1 , p p γ - τ= + γγ (6) ( ) 2 22 11 21 2 , p p γ - τ= + γγ (7) где γ τ - среднее значение интервалов между поступлениями пакетов. Учитывая, что для квадрата коэффициента вариации ( ) ( ) 2 2 2 2 . c γγ γ τ-τ = τ (8) Параметры распределений вычисляются как 1 / , 2 p γ γ= τ ( ) 2 21 , / p γ γ= - τ (9) С учетом выражений (6), (7) и (9) в (8) получено для параметра p: 2 2 1 1 1. 21 c p c γ γ  -  = ±  +  (10) Аналогично можно получить значения параметров для выражения (4), но для определения параметров ( ) 12 ,, q µµ необходимо использовать выражения для µ τ - среднее значение времени обслуживания. Для оценки параметра δ воспользуемся известными подходами [15] для системы 1. 22 // HH В работе [15] авторы показали, что для системы 1 22 // HH для функции плотности времени ожидания преобразование Лапласа имеет вид ( ) ( ) ( ) ( ) ( ) * 12 1 2 12 1 2 , ss s s Ws ss ss +µ +µ = µµ + + а среднее время ожидания будет иметь вид 12 1 2 111 1 , T ss =+-- µµ (11) где 1 s - и 2 s - - отрицательные вещественные части корней кубического уравнения 32 2 s cs -- 10 0, cs c - -= для которого коэффициенты: ( ) ( ) ùùùùù , c ab ab a b = - - µ +µ + γ +γ ( ) ( ) ( ) ùùùùù , c ab a b =- - - + γ +γ µ +µ γ +γ 2 1212 , =γ +γ -µ -µ c Рисунок 1. Распределение случайных интервалов времени между пакетами (Weibull) с промежуточными параметрами: 0 12 , a =γγ ( ) 11 2 , 1 ap p = γ+ - γ 0 12 , b =µµ ( ) 11 2. 1 bq q = µ+ - µ В итоге параметр δ в системе G/M/1 можно определить согласно выражению 11 2 2 2 112 112 11 21 2 1 . ss s s ss ss W µµ δ= = µµ µ - µµ +- µ Полученные результаты позволяют оценить параметры, характеризующие реальный мультимедийный трафик. Анализ статистических характеристик мультимедийного трафика Рассмотрим реализацию мультимедийного трафика на уровне доступа пользователя сети, описание которого приведено в [11]. Законы распределения интервалов времени между пакетами и длин пакетов данного трафика можно проанализировать на основании статистического критерия Колмогорова - Смирнова. Анализ распределения случайных интервалов времени между пакетами показал, что наиболее точным является распределение Weibull (Вейбулла) с параметрами: 0,32, α= 167, β= которое имеет вид ( ) 1 exp , xx fx α- α    α = -     ββ β    где α - параметр формы; β - масштабный параметр. На рисунке 1 отражены гистограмма и результат ее аппроксимации. Для длин пакетов получили результат, показанный на рисунке 2, в виде распределения Парето (Pareto) с параметрами: 0, 3; α= 60, β= которое имеет вид ( ) 1 , , 0, åñëè m m R x xx fx x α α+  α≥  =    где m x - масштабный параметр; α - параметр формы. При определении параметров функци- Рисунок 2. Распределение случайных длин пакетов (Pareto)онирования необходимо учитывать наличие зависимостей между случайными величинами трафика или наличие корреляционных связей между отсчетами реализации трафика. Расчет автокорреляционной функции выборочной реализации случайного процесса можно провести по формуле ( ) ( ) ( ) ( ) 1 2 1 1 , 1 Nk i ik i N i i X XX X Nk Rk XX N - + = = -- - = - ∑ ∑ где X - среднее значение; N - объем выборки. Для исследуемых отсчетов рассматриваемого мультимедийного потока были определены зависимости коэффициентов корреляции, показанные на рисунках 3, 4. Анализ графиков зависимостей коэффициентов корреляции ( ) Rk для интервалов времени между пакетами реализации мультимедийного трафика свидетельствует, что корреляции практически отсутствуют. Это позволяет при анализе параметров функционирования сделать предположение о независимости рассматриваемых случайных величин. Следует заметить, что отсутствие корреляции наблюдается для исследуемой реализации трафика, но не является характерной особенностью в целом для современных инфокоммуникационных потоков. Оценка джиттера для мультимедийного трафика Анализируя реализацию рассматриваемого мультимедийного трафика, мы определили значения 20 γ τ = мс, 102 µ τ = мс. Известно, что коэффициент загрузки системы рассчитывается как / , / µγ ρ=γ µ=τ τ учитывая полученные значения для γ τ и , µ τ получим 0,19. ρ= Согласно выражению (8), можно оценить коэффициенты вариации: 7,2 cγ = мс и 0,06 cµ = мс. Для параметров гиперэкспоненциальных распределений по выражениям (9) и (10) было получено: Рисунок 3. График зависимости коэффициентов корреляции ( ) Rk интервалов времени между пакетами - 0, 93, p = 1 800 γ= мс-1, 2 58 γ= мс-1 - для ( ) V f τ согласно (3); - 0,96, q = 1 189 µ= мс-1, 2 6 µ= мс-1 - для ( ) Q f τ согласно (4). Используя для расчета δ полученные значения параметров, имеем 0,002 δ= мс-1. На основании полученных значений параметров и формулы (5) для джиттера определено: 2 8 10 J - = ⋅ мс. Заключение В работе была получена аналитическая оценка джиттера в системе G/M/1 на основе применения системы 1. 22 // HH Оценка джиттера произведена с использованием известных подходов, но данные подходы ранее не были применены совместно. Представленная методика анализа джиттера является основой для моделирования системы G/G/1 с использованием 1. 22 // HH При этом сохраняется проблема учета корреляционных свойств потоков. Рисунок 4. График зависимости коэффициентов корреляции ( ) Rk длин пакетов

About the authors

M. A Buranova

Povolzhskiy State University of Telecommunications and Informatics

Email: mburanova@yandex.ru
Samara, Russian Federation

V. G Kartashevskiy

Povolzhskiy State University of Telecommunications and Informatics

Email: kartashevskiy-vg@psuti.ru
Samara, Russian Federation

R. T Latypov

Povolzhskiy State University of Telecommunications and Informatics

Email: msib@psuti.ru
Samara, Russian Federation

References

Supplementary files