ANALYSIS OF THE CORRELATED QUEUE IN THE G/G/1 SYSTEM

Full Text

Введение При проектировании инфокоммуникацион- ных сетей одной из актуальных задач является точное прогнозирование параметров их функцио- нирования, таких как оценка параметров качества обслуживания QoS (Quality of Service): задержка, изменение задержки передачи пакетов (джиттер), вероятность потерь пакетов. При решении дан- ных задач возникают проблемы, обусловленные особенностями обрабатываемых в инфокомму- никационных сетях потоков, отличие потоков от пуассоновского, наличие свойств самоподобия, корреляционные связи внутри последователь- ностей обслуживаемых пакетов. Большинство работ по анализу инфокоммуникационных сетей и оценке параметров их функционирования ос- нованы на предположении о независимости по- токов [1-4], в то время как многочисленные ис- следования доказывают обратное [5-8]. Для моделирования систем обработки потоков в инфокоммуникационных сетях традиционно используют системы массового обслуживания, для аналитического описания которых необходи- мо определить последовательности интервалов времени между пакетами и времен обработки пакетов. Следует отметить, что современные ин- фокоммуникационные сети лучше описываются моделью очереди G/G/1. Имеются подтвержде- ния о наличии зависимостей внутри данных по- следовательностей [3; 9; 10] и между ними [5-8]. Следует обратить внимание, что предположения о независимости могут привести к неоправданно оптимистичным прогнозам оценки параметров работы сетей. Анализ данных проблем можно найти в [6; 7] и ссылках на них. В [6] авторы рассмотрели систему с пуассоновскими поступлениями, в ко- Есть и другие работы [1; 8], основанные на моделях с учетом корреляций. Однако, как пока- зано в [6], данные модели слабо учитывают осо- бенности процессов прибытия и обслуживания и, следовательно, приводят к неточности в прогно- зировании производительности системы. И их нельзя использовать для получения фактического времени ожидания. Одна из самых ранних работ по системати- ческому исследованию вопроса о корреляции между временем обслуживания пакетов и време- нем между пакетами - это работа [1], в которой Л. Клейнрок изучал влияние коррелированных длин сообщений и времен между прибытиями в контексте модели сети очередей для сетей связи. Там же он показал сложность этой проблемы. В [5] были показаны некоторые подходы к ана- лизу функционирования сетей при наличии кор- реляций внутри последовательностей интерва- лов времени между пакетами и времен обработки пакетов, при этом корреляции между данными последовательностями учитываются только для оценки задержки, а для оценки такого важного параметра качества обслуживания в инфокомму- никационных сетях, как изменение задержки при передаче пакетов (джиттер, вариация задержки), не показан. Более общие корреляции были рассмотрены в [11] с использованием двумерного экспонен- циального распределения для характеристики корреляции между временем прибытия и обслу- живанием. Впоследствии эта работа была расши- рена в нескольких статьях. В [12] было показано, что плотность задержки имеет гиперэкспонен- циальное распределение, а в [13] изучалась чув- ствительность этого распределения к величине коэффициента корреляции. Период занятости исторой время обслуживания Bn n-го пакета проследовался в [14], а система с бесконечным чиспорционально времени An между прибытиями лом серверов рассматривалась в [15]. (n - 1)-го и n-го пакетов, то есть Bn  An , где Аналогично подходу в [5] рассмотрим канал  - положительная постоянная. Было получено преобразование Лапласа распределения времени пребывания в системе, которое состоит из време- ни ожидания в очереди плюс время обработки па- кета путем решения линейного функционального уравнения [7], полученного из уравнения эволю- ции системного времени. Однако они рассматри- вают только случай   1 из-за технических труд- ностей, связанных с решением функционального уравнения. связи с конечной пропускной способностью, соединяющий два узла - узел 1 и узел 2 (см. ри- сунок 1). Пакеты передаются от узла 1 к узлу 2. В такой системе время между прибытиями со- ставляет два последовательных пакета в узле 2 - это сумма времени передачи (время обслужива- ния в узле 1) первого пакета и времени между двумя пакетами. Здесь время между появлением пакетов опре- деляется периодом времени между периодом Рисунок 1. Корреляционная модель очереди окончания передачи первого пакета и периодом начала передачи второго пакета (см. рисунок 1). Поскольку канал, соединяющий два узла, имеет конечную пропускную способность, скажем τ, канал не может отправлять количество пакетов от узла 1 к узлу 2 превышает τ T, и, следовательно, для больших пакетов требуется более длительное время передачи в обоих узлах. Следовательно, время между прибытиями в узле 2 сильно кор- релирует со временем обслуживания в узле 2. Определение задержки и изменения задержки при передаче пакетов по сети на основе данной модели представляется достаточно перспектив- ным. Модель коррелированной очереди Анализируемая модель представляет собой систему очередей в узле 2, в которой хранятся пакеты, поступающие по входному каналу с ко- нечной пропускной способностью к выходному каналу, имеющему одинаковую со входным каобслуживания которого является таким же, как и ON-период, который следует за ним. Кроме того, можно допустить длительность периода OFF равной нулю, так как в случае, если у узла 1 имеются пакеты для передачи или имеется пач- ка пакетов, он может непрерывно передавать их узлу 2. При анализе данной модели воспользуемся подходом, показанным в [5] для аналогичного случая, где введено предположение, что количе- ство последовательных периодов ON между дву- мя периодами OFF положительной длительности имеет некоторое произвольное распределение, а периоды OFF положительной длины распре- делены экспоненциально. Каждый период ON аппроксимируется гиперэкспоненциальным рас- пределением. Данная модель разработана для оценки сред- ней задержки пакетов в сети. Изменение задерж- ки может быть определено как вариация задержки пакета [10]. Вариация задержки пакета в потоке налом пропускную способность. Процесс поступления пакетов в очередь моделируется чередую-  X   D  X , где D  X  - дисперсия задержщимся процессом, имеющим два типа периодов: ки пакетов. Если ввести обозначение fT  x  - ON-периоды передачи (наличия пакетов) и OFF- периоды между передачей пакетов. С точки зрения теории очередей можно пред- ставить последовательности ON-периода как последовательность времен обработки пакетов, плотность вероятностей случайной величины T (время ожидания пакета в сети) и с учетом, что задержка пакета определяется случайной вели- чиной T, дисперсию задержки можно определить согласно выражению последовательности OFF-периодов как последовательностей интервалов времени между па- D  X        2  x - M x  fT 0  x dx   (1) кетами. Периоды OFF фиксируют время между  T   x2 f  x dx -  x fT 2  x dx . появлением последовательных пакетов в узле 1, а периоды ON фиксируют время передачи паке- тов в узле 1, так что время между поступлениями двух последовательных пакетов в очереди состо- ит из периода OFF и ON. Поскольку очередь в узле 2 может передавать пакет через свой выходной канал только после того, как получит последний бит пакета, при анализе можно предположить, что в конце каж- дого периода ON есть прибывший пакет, время 0 0 Чтобы исследовать влияние корреляций на производительность системы, необходимо рас- смотреть и проанализировать аналогичную оче- редь GI/G/1. Рассмотрим коррелированную очередь узла в сети, где процесс ввода в очередь управляется че- редующимися процессами ON и OFF, а пропуск- ная способность входного и выходного каналов одинакова. Как упоминалось в разделе 1, периоды ON фиксируют время между появлением па- кетов, а периоды OFF фиксируют время передачи ет экспоненциальному распределению с параме- тром i . пакетов на предыдущем узле в сети. Поскольку Пусть n s - преобразование Лапласа Wn предполагается, что система очередей может обслуживать пакет только после того, как получит весь пакет, очевидно, что всегда будет новый падля R(s) ≥ 0. Тогда, приняв, что Sn1  i, получим n1 s  кет в конце каждого периода ON. Так как пропускная способность входного M -1   i 0 i PWn  0 E[e( - s[ I( n1) - J( n1) ] ) S ( n1)  i  канала и выходного канала одинакова, время об- служивания пакетов равно периодам ON, за кото- рыми они следуют. В конце каждого периода ON M -1  i i 0    0 dWn ()  (3) начинается либо период OFF, либо другой период  {   e( -i x ) E e( - s (- J( n1) )  dx  ON, так как допускаются периоды ON с нулевой длиной. Следует обратить внимание, что после- довательные периоды ON захватывают последо- вательные передачи пакетов в предыдущем узле сети. Важно, что после каждого периода OFF всегда начинается новый период ON. i   x 0      e( -i x ) E[e( - s ( x - J( n1) ) ) ]dx}. i x  Наблюдая за тем, что каждый следующий пе- риод ON наступает после периода ON n  1 с ве- При анализе предполагается, что периоды ON роятностью p (в этом случае мы имеем J n1  0) генерируются в соответствии с гиперэкспонени что период OFF наступает после периода ON циальным распределением, имеющим M экспоn  1 с вероятностью q  1 - n (в этом случае длиненциальных составляющих, то есть функция на J n1 соответствует экспоненциальному распреплотности f(x) периодов ON определяется выражением делению с параметром ), получаем, что  l -1 M -1  k -1  M -1 f  x    e-i x , M -1   1,   0.  s  i a k  s  ij  c, (4)  i i  i i l 0 k 0 ik 0  j 0  i 0 i 0 где ñ - константа (с учетом, что все задействован- В конце каждого периода ON либо период ные параметры заданы), определяемая по формуле OFF начинается с вероятностью q  1 - p, либо M -1  другой период ON начинается с вероятностью p. Тогда общее число периодов ON между двумя ñ    - i i 0 i    i  ; последовательными периодами OFF, длина кото- рых больше, чем ноль, имеет распределение, отai s    - ps . i i q    личное от экспоненциального. Предполагается, что периоды OFF положительной длины генери- руются в соответствии с экспоненциальным рас- пределением с параметром β. Предполагая, что используется k экспонент в гиперэкспоненциальном распределении,  - па- раметр распределения, получим Пусть In и Jn n  1 обозначают длительl -1 M -1  a s k -1  c. ность n-го периодов ON и OFF соответственно.  ik  k 0 i 0  ij  j 0 k   Пусть начальные периоды ON - вложенные точки и пусть Wn обозначает незавершенную работу системы, определяемую количеством работы в В итоге из (4) следует окончательное выраже- ние для  s системе в n-й вложенной точке n  0. Время 0 -     l -1 M -1 a  s  k -1  l  k  0 j i  i j  i это нулевая вложенная точка, и мы предполага-  s  . 0 0 k 0 k (5) ем, что первый период ON начинается в момент k 0i 0a k s   j 0 i j  l -1 M -1 i k k -1  времени 0. Тогда Wn уравнению: удовлетворяет следующему Среднее время ожидания пакета в очереди можно определить как первую производную W0  0,  Wn1   (2)  s при условии s  0     Wn - In1   In1 - Jn1  , n  0,  l -1 l -1 M -1  n-1  M -1 i  pi    ain k k  ij   k где A  max A, 0. Пусть Sn1 обозначает тип l 1 k 0 k 0, in 0 n k  j 0  ik 0 qij экспоненциального распределения, которое при- E W   j 0 .(6)  l -1 M -1 k -1 нимает In1. Тогда Sn1  i с вероятностью i ,  aik  j  ij  0  i  M -1, и, следовательно, In1 соответству- 0 l 0 k 0 ik 0 Учитывая, что общую сетевую задержку в со-  S - T , åñëè R T , ответствии с моделью коррелированной очереди J   i 1 i i 1 i рисунок 1 и согласно выражению (2) можно заi 1   Si 1 - Ri 1 . писать как Z  W - I   I , Определим функции плотности вероятно- стей рассматриваемых случайных величин: где I - это общая случайная величина для In , fR  y  - функция плотности вероятности для можно получить преобразование Лапласа для Z, времени между поступлениями; fS  z  - функаналогично подходу для  s в виде ция плотности вероятности для времени обслуживания; fT  x  функция плотности вероятно-  s  E e- s (Wn - I )  I    сти для времени ожидания в сети.      Законы распределения случайных величин S   - s  - ps  s  sq c,  - ps и R можно определить, анализируя реализацию случайного процесса, определяя законы рас- E Z   E W   q 1 - c ,  (7) пределения для времени обслуживания и для времени между поступлениями. Распределение случайной величины Т - непростая задача, а для где q - вероятность, с которой в конце каждого периода ON начинается период OFF. Данный подход показывает возможные пути случая зависимых случайных величин требует особого подхода. Заметим, что определения параметров качества обслуживания T  S  R. (8) в системе с наличием корреляции. При этом оче- видно, что выражения (7) и (8) довольно слож- Тогда плотность распределения случайной величины T [17] ны при использовании для численной оценки      задержки в очереди и в системе в целом. Кроме того, данный подход не позволяет определить та- кой важный параметр, как изменение задержки, Или fT x   fS , R y, x - y dy. 0  (9) который очень важен при оценке качества функционирования современных инфокоммуникациfT  x    fS , R  x - z, z dz. 0 (10) онных сетей. Поэтому рассмотрим более оптимальный подход (с точки зрения удобства применения), основанный на показанном в [16] определении двумерных плотностей вероятностей с исполь- зованием копул. Как было показано выше, при определении времени ожидания пакета в сети и вариации задержки в сети фактически задача Определить двумерную плотность вероятно- стей можно с использованием копул на основе результатов теоремы Склара [18], методика при- менения такого подхода представлена в [16]. Согласно показанному в [17; 19] получим fS , R  y, z   c FR  y , FS  z  fR  y  fS  z , (11) где сводится к определению плотности вероятностей fT  x . c u, v   2C u, v  uv В [2-4] показано, что если учесть предпо- - плотность (производная) копулы, для нашего ложение Линдли [1], заключающееся в том, что случая u  FR  y , v  FS  z  функции распре- i  1 -й пакет не будет ждать в очереди при выполнении условия, что интервал времени между приходом i  1 -го и i-го пакета больше, чем вре- мя задержки i -го пакета в узле сети, и если приделения случайных величин. Из работ, посвященных теории копул, следу- ет, что для различных классов (типов распреде- лений) следует использовать различные копулы. нять, что Ti - время задержки i-го пакета в узле Анализ имеющихся подходов [16] показал, что сети, которое определяется в виде Ti  Si  Ri , наиболее удобной для использования в нашем где Ri время между поступлениями пакетов и случае является копула Фарли - Гумбеля - Мор- Si - время обслуживания пакета, то время ожи- дания пакета в очереди равняется W  0, åñëè Ri 1 Ti ,  генштерна (Farlie-Gumbel-Morgenstern copula), имея достаточно простую функциональную фор- му, она позволяет моделировать умеренные зави- симости. i 1 W  S - R .  i i i 1 Джиттер при этом определяется как Копулу Фарли - Гумбеля - Моргенштерна [17-21] можно представить в виде: Рисунок 2. Гистограмма измерений интервалов времени между поступлениями пакетов. Распределение Weibull, параметры: a = 0,005; b = 1 Рисунок 3. Гистограмма измерений длин пакетов. Распределение Weibull (3P),   C u, v   uv 1  1 - u p 1 - v p  , (12) параметры: a = 94; b = 1; c = -4 пакетами и длины пакетов (времена обработки где  - параметр копулы   R, циент корреляции, R - коэффипакетов). Для аналитической оценки проанализируем Учтем, что параметр  должен удовлетворять следующим условиям: статистические характеристики собранного тра- фика. Статистический критерий согласия Кол- -max 1, p2  2 1   , p могорова - Смирнова - это один из наиболее распространенных и удобных инструментов для где p - целое число  p  2,3. Параметр  определяется согласно выражению 2  u, v   3 p  , s    p  2  где s u, v  - коэффициент корреляции Спирмена. проверки гипотезы о предполагаемом законе распределения некоторой выборки случайных величин. Для данного исследования необходимо определить законы распределения случайных величин: интервалов времени между пакетами и длин пакетов (времен обработки пакетов). С помощью Easyfit Professional проанализиру- При p  2 из (11) получим fS , R  y, z   1  1 - 2u 1 - 2v  fR  y  fS  z . (13) ем классы распределений процессов поступления интервалов времени между пакетами и длитель- ности пакетов. При аппроксимации снятых пара- метров трафика в программе Easyfit Professional При известном значении fT  x  достаточно получаем законы распределения на рисунках 2 и 3. просто определить среднее время обработки (задержку) пакетов в сети и вариацию задержки па- кетов в сети. Анализ статистических характеристик видеотрафика В качестве анализируемого трафика можно использовать видеотрафик, зарегистрированный Следовательно, интервалы времени между па- кетами подчиняются закону Вейбулла с параме- трами a = 0,005; b = 1 (см. рисунок 2), а длины па- кетов - Вейбулла (Weibull, 3P) с параметрами a = = 94; b = 1; c = -4 (см. рисунок 3). Функция распределения и плотность распре- деления Вейбулла имеет вид b   x   на уровне пользователя, как один из наиболее F  x   1 - exp -   , (14) характерных для обработки в современных ин- фокоммуникационных сетях. Для регистрации  b-1     a    b    потока наиболее подходящим является анализаf  x    b  x  x exp -  . (15) тор пакетов Wireshark. Все пакеты собираются в  a  a    a   режиме реального времени и предоставляются в удобном для чтения формате. Программа поддер- живает очень мощную систему фильтрации. Файл трассировки Wireshark (trace file) содер- Аналогично для трехпараметрического рас- пределения Вейбулла (Weibull) функция распре- деления и плотность распределения имеют вид b жит необходимые для анализа работы сети харак-   x - c   F  x   1 - exp - , (16)     теристики трафика: интервалы времени между   a   Рисунок 4. График зависимости коэффициентов взаимной корреляции временных интервалов времен обработки пакетов и времен между поступлениями пакетов (ON- и OFF-периодов)  b  x - c b-1 b   x - c   работки пакетов и интервалами времен между f  x      exp -   , (17) поступлениями пакетов. Это позволяет сделать  a  a    a   предположение о зависимости данных случайгде a - параметр масштаба, характеризующий степень растянутости кривой распределения вдоль оси x и связанный со средним значением случайной величины; b - параметр формы; ñ - параметр сдвига, являющийся минимальным воз- можным значением случайной величины x. Анализ законов распределений для интерва- лов времени между пакетами и времен обработки пакетов показал принадлежность к классу расных величин. Из чего следует обоснованность применения методики оценки задержки в систе- ме с коррелированной очередью. Но для оцен- ки параметра  из выражения (12) необходимо определить коэффициент корреляции Спирмена. Метод ранговой корреляции Спирмена позво- ляет определить силу и направление корреляци- онной связи между двумя признаками или двумя профилями признаков как пределений с тяжелыми хвостами, это позволя- ет сделать вывод о том, что для моделирования s  1 - 6  di , n n2 -1 (20) системы обработки данного потока наиболее точгде для случайных величин  и  d   - , ной является модель G/G/1. При определении параметров функциониро- вания необходимо учитывать наличие зависимо- стей между временными интервалами, между па- кетами и временами обработки пакетов. Анализ взаимной корреляции интервалов вре- мени между пакетами и времен обработки паке- тов определяется согласно выражению для оцен- ки корреляции двух случайных величин  и  по формуле: R ,   E  - E  E    i i i n - объем выборки. Для рассматриваемого пото- ка коэффициент корреляции Спирмена s  0, 46. Определение совместной плотности распределений интервалов времени между пакетами и длин пакетов видеотрафика Зная законы распределения случайных вели- чин R и S, учитывая (11) и (13), можно определить совместную плотность распределения данных случайных величин с учетом, что они являются зависимыми E  - E E - E  (19) f  y, z   1  1 - 2u 1 - 2v   ,  S , R   fR  y  fS  z . (21) где E , E  математическое ожидание Основываясь на том, что fR  y  функция случайной величины  и  соответственно; плотности вероятности для времени между по-  ,  - среднеквадратическое отклонение слуступлениями, fS  z  - функция плотности вечайных величин  и . Из анализа графика зависимости коэффици- ентов взаимной корреляции (рисунок 4) можно сделать вывод о наличии достаточно сильной корреляции между интервалами временем оброятности для времени обслуживания, а R и S - случайные величины, для которых необхо- димо определить совместную плотность распре- деления, в (21) будем использовать функцию рас- пределения (14), (16) вместо u и v и плотности распределения (15) и (17) вместо fR  y  и fS  z  a a3  c  из выражения (13). Тогда можем получить следу- ющее выражение: 2  3 -1 1 2 a2 - a1  a exp -    2  2    b    1     1  2  1  a1a2   2a c  exp 1  1  1 - 2 1 - exp - y      a a  a - 2a   2a   aa       a1      2 1 2 1  2 1   1 2          a a   ac  fS , R  y, z    b     2 1  1 2  exp 1 .     x - y  - c  2    2a - a   a   aa 1 - 21 - exp -     2 1  1   1 2      a2    Вариацию задержки можно определить со-    гласно (1) как b -1    1 b    1  b y   1   y exp -     X   D  X    a1  a1    a1   2      b   x - y  - c b2 -1 b    x - y  - c  2  T  x2 f  x dx -  x fT  x dx  .   2   exp -  . 0  0   a2  a2    a2   Введем вспомогательную величину А соглас- Задача, которую необходимо решить в рамках данного исследования, - определение суммы но следующим обозначениям:  двух случайных величин: интервалов времени между пакетами и времен обработки пакетов, со- гласно (9)-(10) при условии b1  b2  1: T A  x2 f 0 2a a4  x dx   c    3 -1 a 1 2 a 2 exp -    a  fT  x    fS , R  y, x - y dy  0  2 1  2 3  1  4  1  a1a2   2a c  exp 1               y  1  1 - 2 1 - exp -    a2 - a1  a2 - 2a1   2a1   a1a2   0     a1   3     1  a a   ac  1 2 1      x - y  - c    4 2a - a   a   exp aa .  1 - 21 - exp -    2 1  1   1 2     a2       Тогда вариация задержки примет окончатель- 2  1    y  ный вид:  X   A - E T  .   exp -    a1    a1  Численные результаты  1     x - y  - c  Учитывая полученные в результате статисти-  a exp -  dy  a ческого анализа законы распределения интер-  2   3 -1   a1a2 2  exp - x - c   валов времени между пакетами и длин пакетов, принимая во внимание параметры данных рас- a - a 2  a  пределений, получим: 2 1  2  - для интервалов времени между пакетами  1 1   2a1  x - c  a = 0,005; b = 1;  2   exp -    a2 - a1  a2 - 2a1    a1a2  - для длин пакетов: a = 94; b = 1; c = -4. При ñ s  0, 46 получим следующие выраже-   2 1    exp - a1  x - c  . ния для оценки времени ожидания пакетов в сети  2a2 - a1    a1a2  E T   104 мс; Для вариации задержки получим Полученное выражение для fT  x  позволяет  X   84 мс. оценить как среднее время ожидания пакета в сети или среднюю задержку пакета в сети, так и вариацию задержки пакета в сети. Среднее значе- ние задержки представляет собой  E T   xfT  x dx  0 Выводы В работе проанализированы методики оцен- ки параметров качества обслуживания пакетов в сети при наличии корреляций в очереди между интервалами времени между пакетами и длинами пакетов. Определено, что при наличии корреляции достаточно эффективным является подход, основанный на использовании копул. При анализе корреляционных свойств ин- тервалов времени между пакетами и длин паке- тов, характеризующих обрабатываемый трафик, определено наличие сильных корреляций. Полу- чены оценки средней задержки в сети и вариации задержки в сети при наличии корреляций между интервалами времени между пакетами и длинами пакетов.

About the authors

M. A Buranova

Povolzhskiy State University of Telecommunications and Informatics

Email: buranova-ma@psuti.ru
Samara, Russian Federation

M. I Rezyapkina

Povolzhskiy State University of Telecommunications and Informatics

Email: rez8pkina@mail.ru
Samara, Russian Federation

References

Supplementary files