MAP- and BMAP-Flows in Traffic Models of Telecommunication Systems

Full Text

Успешное применение результатов анализа систем массового обслуживания (СМО) для оценивания очередей и задержек в реальных системах требует предварительного осуществления операции аппроксимации характеристик реального потока, типичного для данной системы. И от того, какие характеристики аппроксимируются и какие математические модели применены для их аппроксимации, существенно зависит возможность получения адекватного результата анализа. Наиболее ранние математические модели процессов обработки информационных потоков в телекоммуникационных сетях основывались на представлении потоков заявок пуассоновскими потоками. Потоки определялись как стационарные, ординарные с отсутствием последействия. Такие потоки имели экспоненциальное распределение интервалов времени между соседними заявками, а сами интервалы времени были взаимно независимы. Кроме того, предполагалось, что и время обслуживания заявок имеет экспоненциальное распределение и не зависит от моментов поступления заявок. Потоки запросов на соединения в телефонной станции представляли суперпозицию большого числа потоков заявок малой интенсивности от отдельных пользователей, которые, как известно, сходятся к пуассоновскому потоку. В силу этого модель стационарного пуассоновского потока хорошо согласовывалась с реальными потоками в телефонных сетях. Появление сетей передачи данных с коммутацией пакетов показало, что пуассоновские модели потоков не являются адекватными, и потребовало разработки новых моделей, основанных на непуассоновских распределениях. Исследуются потоки с распределениями Вейбулла и Эрланга, гамма-распределением, распределением Парето и др. Все интервалы времени, представляемые данными распределениями вероятностей, попрежнему считались взаимно независимыми. Это позволяло применить хорошо разработанный аппарат теории очередей для анализа сетей с пакетной коммутацией. Однако с появлением мультисервисных телекоммуникационных сетей, в которых единый ресурс использовался для передачи весьма разнородных информационных потоков, оказалось, что модели с независимыми заявками не отражают поведения реальных потоков пакетов. Реальные потоки имеют высокую степень корреляции, и пренебрегать корреляционными свойствами потоков уже нельзя. Например, нами показано, что для потока видеотрафика доля корреляционной составляющей в образуемых очередях в десятки раз превышает долю дисперсионной составляющей [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-потока Заключение Рассмотренные примеры показывают, что даже такие неравномерные потоки, как потоки пакетов видеотрафика, достаточно адекватно отображаются МАР-моделями, которые по своей структуре намного проще моделей самоподобных процессов, что открывает широкие перспективы для аналитического исследования трафика мультисервисных телекоммуникационных сетей.

About the authors

B. Ya Likhttsinder

Povolzhskiy State University of Telecommunications and Informatics

Email: lixt@psuti.ru
Samara, Russian Federation

V. I Moiseev

Povolzhskiy State University of Telecommunications and Informatics

Email: lixt@psuti.ru
Samara, Russian Federation

References

Supplementary files