Selfl ike traffi c of multiservice communication networks: myths and reality

Full Text

Для исследования и оптимизации сетей связи широко применяются модели систем массового обслуживания (СМО). Основным объектом исследования СМО является взаимодействие двух компонентов: это некоторый ресурс и множество заявок на удовлетворение потребности в указанным ресурсе. Ограниченность ресурса и случайный характер поступления заявок приводят к возникновению задержек или отказов в удовлетворении ресурсом. На начальном этапе проектирования сетей связи, когда широко использовалась технология коммутации каналов, в качестве модели потока заявок, поступающих в узел связи, рассматривалась модель пуассоновского потока с экспоненциальным законом распределения длительностей временных интервалов между поступлениями соседних заявок. Аналогичное распределение предполагалось и для интервалов времени обслуживания заявок. Все поступающие заявки считались взаимно независимыми, так же, как и интервалы времени их обработки. Потоки заявок на телефонные соединения (заявок на канальный ресурс) являлись суперпозицией множества независимых потоков, поступающих от отдельных пользователей. Известно [1], что подобная суперпозиция при большом числе независимых потоков сходится к стационарному пуассоновскому потоку. Поэтому пуассоновская модель трафика была вполне оправданной. При переходе к телекоммуникационным сетям, основанным на технологиях пакетной коммутации, на начальных этапах также использовались предположения о пуассоновском характере потоков заявок и экспоненциальном характере распределения времени их обработки. Однако практика показала, что такие предположения совершенно не согласуются с действительностью и в некоторых случаях приводят к возникновению ошибок, превышающих тысячи процентов [3]. Особенно проявляются указанные несоответствия в телекоммуникационных сетях доступа, в которых программно-аппаратные средства используются для совместной передачи сравнительно небольшого количества совершенно разнородных потоков речевой, мультимедийной информации и передачи данных. В силу большой разнородности, потоки в таких сетях имеют существенно неравномерный характер и сильно коррелированы. Предположение о взаимной независимости поступающих потоков не выполняется, а взаимная зависимость пакетов сохраняется даже для далеко расположенных друг от друга интервалов времени. Учет корреляции Вся классическая теория СМО основана на предположении о взаимной независимости поступающих заявок. Даже известная классификация Кендалла [8] не предусматривает возможности учета корреляционных свойств исследуемых потоков, а учитывает лишь законы распределения соответствующих вероятностей. Существует ряд работ, рассматривающих различные законы распределения вероятностей интервалов между соседними заявками, непуассоновские распределения вероятностей чисел заявок на некотором временном интервале и ряд других. Однако все они предполагают взаимную независимость поступающих заявок. Если же указанные заявки взаимно коррелированы, то даже при экспоненциальном распределении интервалов времени между соседними заявками очереди таких заявок в СМО могут во много раз превышать очереди, создаваемые пуассоновским потоком, при одинаковых интенсивностях поступления заявок и одинаковых коэффициентах загрузки. В качестве примера рассмотрим реализацию простейшего стационарного потока заявок с экспоненциальным распределением интервалов времени между соседними заявками на длительном промежутке времени T [4]. Сгруппируем интерT [4]. Сгруппируем интерT валы заявок таким образом, чтобы наиболее короткие интервалы оказались в начальной части промежутка времени Т, а наиболее длинные окаТ, а наиболее длинные окаТ зались в его конечной части. Естественно, что распределение временных интервалов между заявками во вновь полученном потоке не изменится и останется экспоненциальным. Однако новый поток уже не будет пуассоновский, поскольку мы искусственно ввели в него дополнительную корреляционную зависимость. Средний размер очереди для такого потока будет во много раз превышать значения, полученные по формуле Хинчина - Полачека для пуассоновского потока. На рисунке 1 отображены зависимости средних размеров очередей для пуассоновского потока и того же потока с корректированными интервалами между заявками. Этот пример показывает, что при заданном времени обслуживания знание закона распределения вероятностей, далеко не полностью определяет размер очередей, получающихся при обработке заявок в СМО. Большое (а часто определяющее) влияние на размеры очередей оказывают корреляционные свойства потоков. Наиболее ранними исследованиями корреляционных свойств потоков заявок в СМО, повидимому, можно считать работы [5; 6], в которых рассматривается так называемый индекс дисперсии, учитывающий либо корреляционные свойства входных потоков, либо корреляционные свойства интервалов обработки заявок и не учитывающий их взаимную корреляцию. В последние годы появляются работы [7; 8], где также не учитываются взаимные корреляционные свойства. Однако, поскольку интервалы времени обработки заявок могут сильно зависеть от заявок входного потока, пренебрегать их взаимной корреляцией нельзя. Почти одновременно с [5; 6] была опубликована работа [9] автора этой статьи, где приводится соотношение, обобщающее формулу Хинчина - Полачека и учитывающее взаимные корреляционные свойства стационарных потоков заявок общего вида. Интервальный метод анализа Одним из перспективных, на наш взгляд, направлений изучения пакетного трафика является интервальный метод [4], позволяющий заменить анализ интервалов времени между соседними за Рисунок 1. Зависимости средних размеров очередей для пуассоновского потока (нижний график) и того же потока с коррелированными интервалами между заявками (верхний график)явками и интервалов времени обработки заявок анализом одной случайной величины - числом заявок, поступающих в течение последовательных интервалов времени обработки заявок. В [10; 11] показано, что дисперсия и корреляционные свойства указанной случайной величины при заданной загрузке полностью характеризуют средний размер очереди в системах СМО. Рассмотрим стационарный и ординарный входной поток заявок. Заявки поступают в моменты времени . it Разместим на оси времени последовательные интервалы , iτ соответствующие интервалам времени обработки каждой из заявок. Числа заявок, поступающих в течение каждого из интервалов времени i τ представляют собою анализируемую случайную переменную ( ). im τ Обозначим () m τ - математическое ожидание, () mD τ - дисперсию указанной случайной величины. Если λ - это средняя интенсивность потока заявок, а τ - математическое ожидание времени обслуживания, то ρ=λτ - это коэффициент загрузки одноканальной СМО. Нетрудно показать, что для любого потока заявок справедливо равенство ( ) .m τ =ρ Процесс образования очередей в указанной СМО определялся уравнением баланса 1 ( ) ( ) ( ) ( ), i i i i qqm - τ = τ + τ -δ τ (1) где ( ) 0 ,i δτ= если 1( ) ( ) 0, - τ = τ = ii mq ( ) 1 δτ= i в противном случае. Здесь () iq τ - размер очереди на интервале . iτ Значения ( ) 0 i δτ= возникают на тех интервалах времени, когда на текущем интервале заявки не поступают, а на предыдущем интервале отсутствует очередь. В течение интервалов, когда ( ) 0, i δτ= обработка заявок в процессоре не происходит и система простаивает. Случайная величина () i δτ имеет математическое ожидание, равное коэффициенту загрузки : ρ ( ) ( ) . ii m δ τ = τ =ρ (2) Следовательно, величина ( ) ( ) iim τ -δ τ является центрированной. На основании (1) для среднего числа заявок, находящихся в очереди ( ), ρq нами было получено соотношение, обобщаю щее известную формулу Хинчина - Полачека и справедливое для стационарных потоков общего вида, в том числе и для самоподобного потока: 1 ( ) 2 ( ) ( , )] () 2(1 ) 2 . i m m m k D D r k q ∞ -δ = ρ + ρ ρ ρ ρ= - -ρ ∑ (3) Здесь (,) im rk -δ ρ - нормированная корреляционная функция потока заявок ( ) ( ) iim ρ -δ ρ при заданном значении коэффициента загрузки ρ и сдвиге на k интервалов, а k интервалов, а k () mD ρ - дисперсия указанного потока. На рисунке 2 показана зависимость дисперсии от коэффициента загрузки для видеотрафика (нижний график) и зависимость числителя формулы (3), обусловленная наличием корреляционных связей в потоке видеотрафика (верхний график). Разница впечатляет. Эксперименты показали, что для большинства видов трафика мультисервисных сетей доступа значения второго члена числителя в формуле (3), обусловленного наличием корреляционных связей в потоке, существенно превышают значения дисперсии, и пренебрегать ими нельзя. Самоподобный трафик Измерения на реальных компьютерных сетях и измерения потоков в пакетных сетях передачи данных показали, что передаваемый в них трафик имеет свойства самоподобного случайного процесса. Анализу самоподобных процессов телетрафика посвящено множество публикаций. На качественном уровне самоподобие проявляется в том, что имеется медленно убывающая зависимость между величинами трафика в разные моменты времени, а также в том, что трафик носит пачечный характер. Эти пачки выглядят статистически подобными в различных масштабах интервалов времени [14]. Одной из фундаментальных отечественных работ в указанном направлении является работа [12], определения которой мы рассмотрим Рисунок 2. Зависимость дисперсии и числителя формулы (3) от коэффициента загрузки для видеотрафика применительно к анализируемому нами случайному процессу. Рассматриваемый процесс () im τ 0,iN = является стационарным и дискретным по времен и , τ которое необходимо для обработки одной заявки. Обозначим через () ikm - τ элемент, сдвинутый на k интервалов τ по отношению к ( ). im τ Значение корреляционной функции (корреляционный коэффициент) при сдвиге на k интервалов τ обозначим через ( , ) [ ( ) ( )][ ( ) ( )].m i ik k m m m m - µ τ = τ - τ τ - τ Очевидно, что дисперсия ( ) (0, ) mmD τ =µ τ - это корреляционный коэффициент при нулевом сдвиге () 0.k = Нормированная корреляционная функция: (,) ( , ) . () m m m krk D µρ ρ= ρ Согласно определениям, принятым в литературе [13], статистический процесс () im τ называется самоподобным, с параметром самоподобия H, (где H, (где H ,5 1) 0, H << если ему соответствует корреляционная функция 2 2 2 ( , ) [( 1) 2 ( 1) ]. H H H m r k k k k τ = + - + - (4) Процесс с указанной корреляционной функцией демонстрирует долговременную зависимость, если коэффициент H, называемый параметром Херста, удовлетворяет условию 0,5 1. H << В этом случае 2(1 ) lim ( , ) lim ( , ) , ïðèmm H r k r k Ck kk -β ττ = → →∞ (5) где 21() - Hβ= - коэффициент, меняющийся в пределах 0 1, <β< а С - некоторая медленно меС - некоторая медленно меС няющаяся функция. Нетрудно показать, что при отсутствии корреляции 0,5, =H и нормированная корреляционная функция убывает пропорционально первой степени увеличения коэффициента сдвига k. Для самоподобных процессов убывание корреляционной функции происходит намного медленнее. Поскольку (,) m k µτ является корреляционной функцией центрированного процесса, значения медленно меняющейся функции С близки к нулю. Если выполняется соотношение 0,5 1, H << то самоподобный процесс обладает свойством долговременной зависимости. Из (5) следует, что величина (,) m rk τ убывает по степенному закону. Это означает, что корреляционная функция является не суммируемой, и ряд, образованный ее последовательными значениями, расходится: 1 ( , ).m k rk ∞ = ρ∑ (6) Но в формуле (3) сумма корреляционных коэффициентов в числителе является конечной, и, следовательно, поток заявок, образующих очередь, не может считаться самоподобным. В чем же здесь противоречие? В принятых выше рассуждениях считалось, что случайная величина, образующая самоподобный поток, центрируется с помощью вычитания ее математического ожидания. В действительности, разностная переменная ( ) ( ) iim τ δ τ - центрируется путем вычитания из () im τ случайной величины ( ). i δτ При этом реальная случайная величина ( ), im τ представляющая числа заявок, поступающих в течение интервалов обслуживания одной заявки, имеет математическое ожидание ()im τ = () 1. i δτ=ρ< Поскольку величина () i δτ может принимать только единичные или нулевые значения, на интервалах, где ( ) 0, δτ= i заявки и очереди в системе полностью отсутствуют, и ее дальнейшее поведение не зависит от предыдущих значений ( ).im τ Таким образом, с целью анализа очередей, создаваемых в СМО самоподобными процессами, необходимо учитывать, что корреляционные свойства процесса, с точки зрения образования очередей, определяются разностной переменной ( ) ( ), iim τ δ τ - которая не удовлетворяет свойствам самоподобия. Долговременная корреляционная зависимость () im τ компенсируется корреляционной зависимостью величины ( ). i δτ Процесс, соответствующий указанной переменной, имеет временные интервалы, на которых () im τ = ( ) 0,i = δ τ = прерывающие корреляционную связь между предыдущими и последующими частями очереди. Следовательно, ни о какой долговременной зависимости здесь говорить не приходится. Она компенсируется и длится лишь в течение активной части каждого цикла образования очереди. Это еще раз подтверждает, что самоподобный трафик, имеющий долговременную корреляционную зависимость, при обработке в СМО указанную зависимость теряет, соотношение (6) не выполняется, и сумма сходится к некоторой постоянной величине С: 1 ( , ) .im k r k C -δ = ρ=∑ Именно значения указанной величины с учетом того, что , λτ=ρ определяют средний размер очереди по обобщенной формуле (1). На свойства разностной величины, аналогичной [ ( ) ( )], iim τ δ τ - обращал внимание еще Л. Клейнрок в [2], указывая, что эта случайная величина полностью определяет характер очередей в СМО. Итак, суммарный поток заявок, образующих очередь в СМО, учитывающий заявки, покидающие очередь, не удовлетворяет требованиям самоподобия даже в тех случаях, когда поток входных заявок этим требованиям удовлетворяет. Именно указанное отличие является одной из причин недостаточной эффективности применения модели самоподобного трафика при анализе очередей и задержек в СМО. Сложность модели самоподобного трафика Второй причиной недостаточной эффективности применения модели самоподобного трафика является ее сложность. В середине прошлого столетия появилось множество работ, посвященных анализу самоподобных процессов. Однако в указанных работах такие процессы рассматривались в отрыве от их анализа в составе СМО и не привели к существенным практическим результатам. Причины этого факта изложены в прекрасном обзоре [13]. Главный недостаток модели самоподобных потоков с точки зрения их использования при аналитическом моделировании процессов передачи информации в телекоммуникационных сетях состоит в том, что самоподобный поток сам по себе является достаточно сложным объектом. «Поэтому аналитическое исследование не только самого потока, но и СМО, в которую он поступает, является мало реальным» [13]. С этим выводом трудно не согласиться. Заключение Отсутствие весомых практических результатов подтверждает малую реальность аналитического исследования СМО с самоподобными входными потоками и ставит под сомнение миф о преимуществах модели самоподобных процессов при анализе трафика телекоммуникационных сетей.

About the authors

B. Ya Likhttcinder

References

Supplementary files