Ильницкий С.В.

Последние исследования различных типов сетевого трафика убедительно доказывают, что сетевой трафик является самоподобным (self-similar) или фрактальным (fractal) по своей природе, т.е. в нем присутствуют так называемые вспышки или пачки (burst) пакетов, наблюдаемые в различных временных интервалах (от милисекунд до минут или даже часов), а также корреляция между пакетами. Из этого следует, что широко используемые в настоящее время методы моделирования и расчета сетевых систем, основанные на традиционных предположениях, не дают адекватной картины происходящего в сети. Было бы логично предполагать, что рабочие параметры сетевых систем с самоподобным трафиком отличаются по своим значениям от систем с простейшим (Пуассоновским) потоком на входе.

В данной публикации проведено cравнение рабочих параметров сетевых систем, представленных моделью M/M/1 (с Пуассоновским входным потоком (Poison input flow)) и моделью G/M/1 с самоподобным входным потоком, а также анализ средней длины очереди, среднего времени ожидания в очереди и определение максимальной длины очереди в случае различных входных потоков.

КОМПЬЮТЕРНЫЕ СЕТИ, ТРАФИК, МОДЕЛИРОВАНИЕ, МЕТОДЫ РАСЧЕТА, САМОПОДОБНОСТЬ.

Keywords: network traffic, self-similar traffic, traffic analysis.

1. Введение

Последние исследования различных типов сетевого трафика убедительно доказывают, что сетевой трафик является самоподобным (self-similar) или фрактальным (fractal) по своей природе, т.е. в нем присутствуют так называемые вспышки или пачки (burst) пакетов, наблюдаемые в различных временных интервалах (от милисекунд до минут или даже часов). Из этого следует, что широко используемые в настоящее время методы моделирования и расчета сетевых систем, основанные на традиционных предположениях, не дают адекватной картины происходящего в сети. Было бы логично предполагать, что рабочие параметры систем с самоподобным трафиком отличаются по своим значениям от традиционных, рассчитанных для систем с простейшим (Пуассоновским) потоком на входе. Сравнение удобно провести на моделях систем массового обслуживания. Для этого проанализируем поведение моделей M/M/1 (с Пуассоновским входным потоком (Poison input flow)) и G/M/1 с самоподобным входным потоком, а также сделаем анализ средней длины очереди, среднего времени ожидания в очереди и определение максимальной длины очереди в случае различных входных потоков.

2. Сравнение рабочих параметров для систем М/М/1 и С/М/1 с самоподобным входным потоком

Проанализируем основные характеристики (среднее время ожидания, среднюю длину очереди и максимальную длину очереди) для системы G/M/1. В качестве входного потока будем использовать поток, сгенерированный с помощью модели, описанной в работе [7]. Время ожидания измеряется встроенной подсистемой GPSS в зависимости от загрузки системы:

где

X - средняя интенсивность входного потока, р - средняя интенсивность обслуживания.

Время обслуживания транзакции имеет экспоненциальный закон распределения.

В начале выполнения программы происходит инициализация параметров. Количество ON-OFF источников выбрано согласно топологии исследуемой сети [7] и подразумевает следующее: каждая рабочая станция в сети является источником запросов к серверу. Общее количество рабочих станций в сети равно 350. В 1-м блоке программы происходит прозрачное включение 350 ON-OFF источников.

Во 2-м блоке, в зависимости от количества включенных источников, генерируется поток транзакций, который затем будет передан в 3-й блок программы.

В 3-м блоке транзакции поступают на обслуживающий прибор GPSS, названный PRIB, и задерживаются в нем на время, которое распределено по экспоненциальному закону и имеющим среднее значение TM2. Когда устройство обслуживания занято, транзакции поступают в очередь и ожидают там до тех пор, пока обслуживающее устройство не будет свободным. Длина очереди в нашем случае бесконечна, а приоритеты не используются.

В 4-м блоке программы определяется время моделирования.

Для получения точных результатов необходимо повторять эксперименты много раз, изменяя только случайные последовательности, инициализируя генератор и вычисляя средние значения результатов. Исходные коды программы находятся у автора данной статьи.

Для сравнения результатов с классической системой с экспоненциальным временем распределения необходимо провести дополнительные расчеты, сохраняя без изменения время моделирования и другие параметры. Входной поток имеет экспоненциальное время распределения со средним значением а процесс обслуживания происходит в том же самом блоке программы, что и в случае самоподобного входного трафика в предыдущем эксперименте.

3. Оценка результатов экспериментов

Результаты моделирования систем G/M/1 и M/M/1показаны в

Таблице 1 и 2.

Таблица 1. Основные параметры для системы G/M/1.

Таблица 2. Основные параметры для системы M/M/1.

Покажем отличия в значениях рабочих параметров для случая классического входного потока (система M/M/1) и самоподобного входного потока (система G/M/1). Для этого построим графики средних значений длины очереди, максимальной длины очереди и среднего времени ожидания в очереди в зависимости от загруженности системы.

4. Средняя длина очереди

Используя данные из Таблицы 1 и 2, строим графики средней длины очереди в зависимости от загруженности системы.

Рисунок 1. Средняя длина очереди для систем G/M/1 и M/M/1.

Так как результаты для различных р отличаются в тысячи раз, разделим график на две части: диапазоны значений 0.2< р<0.8 и 0.8 < р< 1.0, затем проанализируем их независимо.

На Рисунке 2 изображен график для диапазона 0.2< р<0.8. Как видно из графика, в случае самоподобного входного трафика средняя длина очереди намного больше по сравнению с простешим (Пуассоновским) входным трафиком. Разница составляет 2-6 раза даже в случае, когда система не была нагружена. Очередь растет даже тогда, когда интенсивность на входе намного меньше интенсивности обслуживания. Это может быть объяснено особой структурой пакетов самоподобного трафика (в нем присутствуют так называемые вспышки или пачки (burst) пакетов).

Рисунок 2. Средняя длина очереди для О/М/1 и М/М/1 систем при 0.2< р<0.8.

На Рисунке 3 показан график для случая 0.8< р<1.0. нагрузка на систему возросла и разница между значениями средней длины очереди для различных законов распределения тоже возросла. В начале диапазона (р=0.8) разница между двумя графиками составляет 6 раз. Когда р=0.95среднее значение длины очереди для систем О/М/1 в 17 раз больше, чем для систем М/М/1.

Рисунок 3. Средняя длина очереди для С/М/1 и М/М/1 систем при 0.8 < р<1.0

5. Максимальная длина очереди

С помощью полученных в ходе экспериментов данных [7] (Таблица 1 и 2) строим график максимальной длины очереди в зависимости от нагрузки на систему (Рисунок 4).

Рисунок 4. Максимальная длина очереди для систем О/М/1 и М/М/1

Так как результаты для различных р отличаются в тысячи раз, разделим график на две части: диапазоны значений 0.2< р<0.8 и 0.8 < р< 1.0, затем проанализируем их независимо.

На Рисунке 5 изображен график для диапазона 0.2< р<0.8. Как видно из графика, в случае самоподобного входного трафика максимальная длина очереди больше по сравнению со случаем простейшего входного потока. В начале диапазона (р=0.2) разница между двумя графиками составляет 5 раз. Когда р возрастает до значения 0.5, разница сокращается до 2-х раз, но в дальнейшем, когда р продолжает расти, разница между значениями для О/М/1 и М/М/1 системами вновь возрастает и в момент, когда р=0.8 отличие составляет уже 3 раза.

Данные различия на графике можно объяснить характерной для самоподобного трафика структурой пакетов. (Структура пакетов в этом случае характеризуется наличием множественных коллизий даже если средняя интенсивность входного трафика меньше интенсивности обслуживания.) В результате получаем, что для малых значений р разница максимальной длины очереди для систем О/М/1 и М/М/1 выражена больше, чем для средних значений р.

Рисунок 5. Максимальная длина очереди для О/М/1 и М/М/1 систем, 0.2< р<0.8

6. Среднее время ожидания

С помощью полученных в ходе экспериментов данных [7] (Таблица 1 и 2) строим график максимальной длины очереди в зависимости от нагрузки на систему (Рисунок 6).

По аналогии с предыдущими разделами, так как результаты для различных р отличаются в тысячи раз, разделим график на две части: диапазоны значений 0.2< р<0.8 и 0.8 < р< 1.0, затем проанализируем их независимо.

Рисунок 6. Среднее время ожидания для систем О/М/1 и М/М/1.

На Рисунке 7 показан график для среднего времени ожидания в случае 0.2<р<0.8. Как можно видеть на графике, в случае самоподобного трафика среднее время ожидания в очереди больше по сравнению со случаем простейшего входного потока. В начале диапазона (р=0.2) разница между графиками составляет 15 раз. Когда р возрастает до значения 0.5, разница снижается до 10 раз. В дальнейшем, когда р продолжает расти, разница между системами О/М/1 и М/М/1 уменьшается и в момент, когда р=0.8 составляет всего 4.5 раза.

Объяснение этому факту следует искать в особенностях структуры пакетов самоподобного трафика. Даже в случае, когда интенсивность входного потока меньше интенсивности обслуживания, имеются различия между системами с самоподобным и простейшим входными потоками.

Рисунок 7. Среднее время ожидания для систем О/М/1 и М/М/1, 0.2< р<0.8

7. Заключение

После анализа рабочих параметров систем О/М/1 и М/М/1 можем сделать следующие выводы:

• Все основные параметры (средняя длина очереди, максимальная длина очереди а также среднее время ожидания в очереди) для системы О/М/1 имеют большие значения по сравнению с системой М/М/1 с аналогичными параметрами (за исключением типа входного потока)

• Когда система не нагружена (р=0...3), разница составляет 2 раза для средней длины очереди, 5 раз для максимальной длины очереди и 15 раз для среднего времени ожидания в очереди. На это сильно влияет структура пакетов самоподобного трафика, имеющего так называемые вспышки или пачки (burst) пакетов.

• Когда система работает в нормальном режиме (р=0.4...0.7), разница между значениями рабочих параметров для систем G/M/1 и М/М/1 не столь велика, как для небольших значений р, но с повышением нагрузки на систему тоже постепенно возрастает: 6 раз для средней длины очереди, 2-3 раза для максимальной длины очереди и 3 раза для среднего времени ожидания.

• Когда система работает в нагруженном режиме (р=0.75.. .0.99), разница в значениях рабочих параметров между двумя системами продолжает возрастать и когда р превышает значение 0.86, это возрастание становится очень стремительным: 17 раз для средней длины очереди, 10 раз для максимальной длины очереди. (Стремительное возрастание разницы значений параметров для максимальной длины очереди начинается даже раньше, когда р=0.75.)

• Длина очереди в нашем эксперименте была бесконечной и не были использованы приоритеты, но в реальной жизни длина очереди имеет определенное значение и поэтому влияние самоподобного входного потока на производительность системы еще более заметно и иногда приводит к нестабильности в ее работе или большим задержкам.

• Влияние эффекта самопободности необходимо учитывать при проектировании и анализе систем.

Библиография

[1] Leland W.E., Taqqu M.S., Willinger W. and Wilson D.V. On The Self-Similar Nature Of Ethernet Traffic.- Proc. АСМ SIGCOMM'93, San-Fransisco, 1993, p 183-193.

[2] Walter Willinger, Murad S. Taqqu, Robert Sherman and Daniel V. Wilson, "Self-Similarity Through High-Variability: Statistical Analysis of Ethernet LAN Traffic at the Source Level". IEEE/ACM Transactions on Networking, Vol. 5, No. 1, 1997

[3] Adrian Popescu, Traffic Self-Similarity, Department of Telecommunications and Signal Processing, University of Karlskrona/Ronneby

[4] Paxson V., Fast Approximation of Self-Similar Network Traffic, preprint Lawrence Berkely Laboratory and EECS Disvision, University of California, 1996

[5] P.Ulanovs, E.Petersons, Modeling of Self-similar traffic in high-performance Computer Networks, RTU, report collection for 42 International Conference, Riga, 2001

[6] Цыбаков Б.С. Модель телетрафика на основе самоподобного случайного процесса. "Радиотехника", 1999 г., № 5.

[7] S.Ilnickis, Research of the network server in self-similar traffic environment, RTU, Riga, 2003.

Об авторе:

Ильницкий Сергей Васильевич, докторант Рижского Технического Университета, факультет „Транспортная Телематика".

Служ. адрес: Латвия, Рига, Ломоносова l, Рижский Технический Университет. Тел: (+371) 7089984,

Дом. адрес: Латвия, Олайне, LV-2114, ул. Земгалес, 34-48. Моб. тел: (+371) 9441875 E-mail: Sergejs.Ilnickis@dati.lv