МАР- и ВМАР-потоки в моделях трафика телекоммуникационных систем

Полный текст

Успешное применение результатов анализа систем массового обслуживания (СМО) для оценивания очередей и задержек в реальных системах требует предварительного осуществления операции аппроксимации характеристик реального потока, типичного для данной системы. И от того, какие характеристики аппроксимируются и какие математические модели применены для их аппроксимации, существенно зависит возможность получения адекватного результата анализа. Наиболее ранние математические модели процессов обработки информационных потоков в телекоммуникационных сетях основывались на представлении потоков заявок пуассоновскими потоками. Потоки определялись как стационарные, ординарные с отсутствием последействия. Такие потоки имели экспоненциальное распределение интервалов времени между соседними заявками, а сами интервалы времени были взаимно независимы. Кроме того, предполагалось, что и время обслуживания заявок имеет экспоненциальное распределение и не зависит от моментов поступления заявок. Потоки запросов на соединения в телефонной станции представляли суперпозицию большого числа потоков заявок малой интенсивности от отдельных пользователей, которые, как известно, сходятся к пуассоновскому потоку. В силу этого модель стационарного пуассоновского потока хорошо согласовывалась с реальными потоками в телефонных сетях. Появление сетей передачи данных с коммутацией пакетов показало, что пуассоновские модели потоков не являются адекватными, и потребовало разработки новых моделей, основанных на непуассоновских распределениях. Исследуются потоки с распределениями Вейбулла и Эрланга, гамма-распределением, распределением Парето и др. Все интервалы времени, представляемые данными распределениями вероятностей, попрежнему считались взаимно независимыми. Это позволяло применить хорошо разработанный аппарат теории очередей для анализа сетей с пакетной коммутацией. Однако с появлением мультисервисных телекоммуникационных сетей, в которых единый ресурс использовался для передачи весьма разнородных информационных потоков, оказалось, что модели с независимыми заявками не отражают поведения реальных потоков пакетов. Реальные потоки имеют высокую степень корреляции, и пренебрегать корреляционными свойствами потоков уже нельзя. Например, нами показано, что для потока видеотрафика доля корреляционной составляющей в образуемых очередях в десятки раз превышает долю дисперсионной составляющей [1]. Описание сложных коррелированных потоков в современных телекоммуникационных сетях часто производилось с использованием «фрактальных» процессов. Работы посвящены анализу «самоподобного» трафика, однако ощутимых практических результатов указанные исследования не принесли. Причины этого, изложенные в [2], а также рассмотренные в [3], сводятся к следующему. Самоподобный входной поток нельзя рассматривать в отрыве от системы, где происходит его обработка. Размеры очередей определяются совокупностью двух потоков заявок: входного и потока обработанных заявок, покидающих очередь. Оба эти потока имеют высокую степень взаимной корреляции. Очереди в таких системах имеют циклический характер, и участки, на которых происходит обработка поступивших заявок, чередуются с участками, где заявки отсутствуют и процессор «простаивает». В [4] показано, что корреляционные зависимости очередей ограничиваются размерами циклов очередей, а корреляционные связи между значениями очередей различных циклов отсутствуют. В итоге результирующий поток, образующий очередь, свойства долговременной зависимости «самоподобных» потоков теряет. Недостаточная эффективность представления трафика моделями «самоподобных» процессов привела к созданию класса моделей потоков, управляемых цепью Маркова. Этапы развития указанных моделей представлены в обзоре [2]. В нашей стране они были названы МС-потоками, а в США эволюционировали от «разносторонних (versatile) потоков», через «N-потоки (потоки Ньютса) [5] до марковских входных потоков (MАP - Markovian Arival Process) и их обобщений - групповых марковских входных потоков (BMАP - Batch Markovian Arival Process) [8-10]. На ранних стадиях указанных моделей интервалы поступления стационарного пуассоновского потока чередовались с интервалами, имеющими показательное распределение, где этот поток отсутствовал (IPP-потоки). Затем перешли к рассмотрению SPP-потоков, где чередовались между собою интервалы поступления нескольких стационарных пуассоновских потоков различной интенсивности. Следует отметить, что подобные потоки получили также название «гиперэкспоненциальные», а их обобщения - «гиперэрланговские» и «гипер-Г-потоки» [1]. На базе указанных потоков еще в 70-х годах прошлого века были получены формулы для средних значений размеров очередей [6]. Однако работы с их применением появляются и поныне [7]. Стимулом к развитию BMАPмоделей явились их матричные представления, предложенные в работах М. Ньютса. Переход к матричным представлениям вероятностных характеристик BMАP-потоков позволил эффективно осуществлять описание их работы и открыл широкий простор для аналитических исследований. Однако определение характеристик входного потока заявок по-прежнему осуществлялось отдельно от характеристик обрабатывающей его системы. Вместе с тем такая характеристика, как время обработки пакета в телекоммуникацион ных системах, не только зависит от пропускной способности системы, но и тесно связано с размером пакета, который является одной из характеристик входного потока. Интервальный метод Одним из перспективных, на наш взгляд, направлений изучения пакетного трафика является разрабатываемый нами интервальный метод [1], позволяющий заменить анализ интервалов времени между соседними заявками и интервалов времени обработки заявок анализом одной случайной величины - числом заявок, поступающих в течение последовательных интервалов времени обработки каждой из заявок. Нами показано, что дисперсия и корреляционные свойства указанной случайной величины при заданной загрузке полностью характеризуют средний размер очереди в системах массового обслуживания [1]. Для одноканальных СМО нами было получено соотношение (1), обобщающее известную формулу Хинчина - Поллачека для среднего значения очереди () ρq и справедливое для любых стационарных потоков заявок при заданном коэффициенте загрузки . ρ 1 2 21 2 ( ) Cov[ ( ); ( )]() . () - ρ + ρ ρ ρ ρ= - -ρ m i i D q mq (1) Анализ числителя (1) показывает, что среднее значение очереди для потоков любого вида зависит от двух составляющих: первой является дисперсия () ρmD числа заявок (пакетов) ( ), ρim поступающих в течение интервала времени обработки одной заявки; вторая обусловлена наличием корреляционных связей в указанном потоке. Корреляционные связи учитываются ковариацией 1 Cov[ ( ); ( )] - ρρ ii qm между значениями () ρim и значениями очереди 1() - ρiq на предыдущем интервале анализа. Для пуассоновского потока в частном случае указанная составляющая равна нулю, а дисперсия ( ) . ρ =ρmD При этом обобщенная формула (1) приобретает обычный вид: 2 21 () () ρ ρ= -ρ q . Анализ видеотрафика В мультисервисных сетях связи (МСС) с пакетной коммутацией поток пакетов существенно отличается от пуассоновского и носит явно выраженный пачечный характер. На рисунке 1 представлена реализация видеотрафика (узкие пачки) на фоне равномерного пуассоновского потока одинаковой с ним интенсивности (серый фон). На рисунке 2 показан фрагмент указанной реализации в увеличенном масштабе времени. Каждая тонкая вертикальная полоска соответствует числу пакетов, поступающих в течение интервала времени обработки одного пакета. Из графиков следует, что для видеопотока имеются интервалы, в течение которых поступают десятки пакетов, в то время как пуассоновский поток содержит на указанных интервалах один или два пакета. Это и объясняет наличие больших очередей при передаче потоков видеотрафика. Пачечный характер видеотрафика объясняется тем, что декодер приемника периодически запрашивает у сервера «порции» видеоинформации объемом порядка одной секунды видеопередачи. Указанная информация хранится в ячейках буферной памяти и равномерно потребляется из нее в процессе воспроизведения. Перед началом передачи в буферную память заносится некоторый начальный объем информации (приблизительно на 10 с видеовоспроизведения), который в процессе воспроизведения стараются поддерживать постоянным. Для пачечного потока видеотрафика составляющая, обусловленная дисперсией ρ ( ),mD оказывается существенно меньше, чем составляющая, обусловленная наличием корреляционных связей. На рисунке 3 для рассматриваемого видеотрафика показаны зависимости дисперсии (нижняя кривая) и средних размеров очереди (верхняя кривая) при различных значениях коэффициента загрузки , ρ полученные в результате имитационного моделирования. Значение дисперсии 0 5 8 8 ( , ) , , =mD в то время как средний размер очереди 05 (,)q превышает 150 пакетов. Корреляционная составляющая потока видеотрафика очень велика. Рисунок 1. Поток видеотрафика и пуассоновский поток Рисунок 2. Поток видеотрафика и пуассоновский поток в увеличенном масштабе времени Рисунок 3. Зависимости дисперсии и средних размеров очередей видеотрафика при различных значениях коэффициента загрузки ρ MАP-модели Развитие МАР- и BMАP-моделей открыло широкое поле для аналитических исследований пачечных потоков в СМО. Основными строительными элементами указанных моделей являются фрагменты простейших потоков, которые коммутируются цепью Маркова. Поскольку заявки в простейших потоках взаимно независимы и корреляционные связи между ними отсутствуют, казалось бы, что вероятность появления корреляционных связей в результирующем потоке должна быть мала. Однако это далеко не так: путем изменения параметров MАP-потока можно получить модели, интервальные характеристики которых весьма близки к соответствующим характеристикам потоков реального видеотрафика. В качестве примера рассмотрим поток реального видеотрафика, представленный на рисунках 1, 2. Поток образуется пачками пакетов, циклически повторяющимися через достаточно большие интервалы времени. Пакеты в пачках следуют один за другим с весьма высокой интенсивностью, которую в модели обозначим через 1. l Примем, что интервалы между соседними пакетами в пачке имеют экспоненциальное распределение вероятностей. Примем также, что интервалы времени между пачками также имеют экспоненциальное распределение вероятностей с параметром интенсивности 2, l много меньшим, чем 1. l Таким образом, нами рассматривается двухфазная модель. Обозначим через 12 P и 21 P вероятности того, что при поступлении очередного пакета система перейдет из одной фазы в другую. Вероятности в процессе остаются неизменными. Рассмотрим модель, имеющую следующие исходные параметры: 12 0 005 ,;=P 21 0 995 ,;=P 1 10000; l= 2 10 ,.l= Объем выборки 100000. =N На рисунке 4 представлена реализация реального потока видеотрафика, полученного от сервера U-TUBE, при коэффициенте загрузки канала 05 ,.ρ= Поток носит пачечный характер, и интервалы обработки одного пакета, содержащие более 30 поступивших пакетов, чередуются с интервалами, где пакеты отсутствуют. На рисунке 5 представлена реализация сгенерированного MАP-потока с указанными выше параметрами. Естественно, что моделирующий поток более равномерный, чем реальный, однако оба они имеют пачечную структуру, и интервалы обработки одного пакета, содержащие более 30 поступивших пакетов, также чередуются с интервалами, где пакеты отсутствуют. На рисунке 6 показаны зависимости средних размеров очередей (верхние графики) и дисперсий (нижние графики) для реализаций MАPпотока и рассматриваемого потока видеотрафика, графики зависимостей очередей имеют вполне достаточное для практических целей совпадение. Нижние графики дисперсий показывают, что, в соответствии с (1), дисперсионные составляющие, в отличие от ковариационных, в обоих случаях оказывают незначительное влияние на размеры очередей. На рисунках 7, 8 представлены нормированные ковариационные функции (;) (;) () µρ ρ= ρ m m krk D чисел заявок ρ ()im при коэффициенте загрузки 05ρ= , для рассматриваемого потока видеотрафика и MАP-потока соответственно. Обе ковариационные функции имеют похожий вид и весьма медленное затухание, они знакопеременны, причем все значения корреляционных коэффициентов малы по сравнению с дисперсией. Однако их сумма при сдвиге в пределах цикла очередей все же намного превосходит значение дисперсии. Рисунок 4. Реализация потока видеотрафика, полученного от сервера U-TUBE Рисунок 5. Реализация MАP-потока, полученного от сервера U-TUBE Рисунок 6. Зависимости средних размеров очередей и дисперсий для реализаций MАP-потока и потока видеотрафика Рисунок 7. Нормированная ковариационная функция чисел заявок 05 ( , ) ρ=im для потока видеотрафика Рисунок 8. Нормированная ковариационная функция чисел заявок 05 ( , ) ρ=im для MАP-потока Заключение Рассмотренные примеры показывают, что даже такие неравномерные потоки, как потоки пакетов видеотрафика, достаточно адекватно отображаются МАР-моделями, которые по своей структуре намного проще моделей самоподобных процессов, что открывает широкие перспективы для аналитического исследования трафика мультисервисных телекоммуникационных сетей.

Об авторах

Б. Я Лихтциндер

Поволжский государственный университет телекоммуникаций и информатики

Email: lixt@psuti.ru
Cамара, РФ

В. И Моисеев

Поволжский государственный университет телекоммуникаций и информатики

Email: lixt@psuti.ru
Cамара, РФ

Список литературы

Дополнительные файлы