Назад в библиотеку

---

Моделирование самоподобного входного трафика сетевых процессоров в системе NS-2

Автор: Д.Д. Моргайлов, Ю.В. Ладыженский, М. Юнис

Источник: Информатика и компьютерные технологии – 2012 (ИКТ – 2012) / Материалы VIII международной научно-технической конференции студентов, аспирантов и молодых ученых – 18-19 сентября 2012 – Донецк, ДонНТУ – 2012, c. 232-239.

Аннотация

Д.Д. Моргайлов, Ю.В. Ладыженский, М. Юнис. Моделирование самоподобного входного трафика сетевых процессоров в системе NS-2. Рассмотрены основные свойства самоподобного трафика. Приведена методика оценки степени самоподобия сетевого трафика. Рассмотрены средства  симулятора NS-2 для генерации самоподобного трафика. Описаны параметры распределения Парето. Выполнено моделирование самоподобного трафика в системе NS-2 и исследованы его свойства.

Введение

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

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

Свойство масштабной инвариантности сетевого трафика позволяет разработать алгоритмы прогнозирования, которые смогут посредством анализа трафика на относительно небольшом отрезке времени предсказать его поведение на более длительных интервалах [1].

Самоподобие трафика

Многочисленные современные исследования Интернет трафика свидетельствуют о том, что он обладает свойством самоподобия [2].

Под самоподобием подразумевается повторяемость распределения нагрузки во времени при различных масштабах [3]. Если набор значений самоподобной функции (т.е. проявляющей признаки самокорреляции) разделить на равные группы, а затем просуммировать значения внутри групп, то набор сумм будет подчиняться той же самой корреляционной функции, что и исходные данные [3].

В отличие от пуассоновских самоподобные процессы характеризуются наличием последействия: вероятность наступления очередного события зависит не только от времени, но и от предыдущих событий (предыстории) [2]. Это означает, что число текущих событий может зависеть от числа предыдущих событий в отдаленные промежутки времени [2]. Поэтому одним из основных свойств самоподобного процесса является медленно убывающая зависимость между объемами трафика в разные моменты времени.

Самоподобный процесс часто носит взрывной (burst) характер, что проявляется в наличии выбросов при относительно низкой скорости потока событий [2]. Эти локализованные во времени скопления (congestions) вызывают значительные потери пакетов, даже когда суммарная потребность в обслуживании всех потоков далека от максимально допустимых значений [3], поскольку расчеты требуемых характеристик современных сетей используют лишь усредненные свойства трафика. В частности, для самоподобного потока пакетов при увеличении размера буфера на входе сетевого процессора вероятность потерь падает значительно медленнее, чем для экспоненциального закона, используемого в классических моделям телетрафика [4]. Алгоритмы обработки трафика сетевым процессором, предназначенные для работы с простейшим потоком, неэффективны для самоподобных потоков.

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

Важнейшим параметром, характеризующим степень самоподобия, является параметр Херста H, определяемый для временного ряда x(t_i), t_i – дискретные моменты времени, . Параметр Херста описывается эмпирическим соотношением

где a – константа, R – размах отклонения значений ряда x, S – стандартное отклонение x. Пусть – среднее значение случайной величины

Стандартное отклонение x определяется из формулы

Обозначим через

                                                   

накопившееся отклонение значений случайной величины x(t) от ее среднего значения за время t.

Разность между максимальным и минимальным значениями называется размахом

 

где

Генерация самоподобного трафика в системе NS-2

NS (Network Simulator – сетевой симулятор) – инструмент для моделирования процессов в компьютерных сетях [5]. Он позволяет описать для моделируемой сети топологию, конфигурацию источников и приемников трафика, параметры соединений (полосу пропускания, задержку, вероятность потери пакетов) и другие параметры. При моделировании имеется возможность управлять параметрами буферов, проводить мониторинг принятых, отправленных и потерянных пакетов, осуществлять сбор статистики и др. С помощью генерации выходных trace-файлов может быть получена информация о динамике трафика, состоянии соединений и объектов сети, а также работе протоколов [5].

Для генерации трафика в системе NS-2 предназначены объекты типа Traffic. Они создаются методами Traffic/type, где type – Expoo, Pareto или Trace [5].

Объект Traffic/Pareto – ON/OFF генератор трафика согласно распределению Парето.

Простая ON/OFF модель предполагает, что источники переключаются между двумя состояниями: ON-состояние, в котором источники генерируют трафик с постоянной скоростью,  OFF-состояние, в котором они молчат [6].

На рисунке 1 показан пример создания генератора трафика Парето.

Созданный объект генерирует  пакеты размером 128 байт с постоянной битовой скоростью 20000 бит/с в течение ON периода со средней продолжительностью в 500 мс. Средняя длительность OFF периода составляет 1,5 с, параметр формы (характеризует, будет ли распределение иметь конечное или бесконечное среднее и дисперсию) равен 1,2 (типичное значение).

При постоянном размере пакетов ON и OFF периоды распределены по закону Парето.

Распределение Парето имеет функцию распределения

 

где – параметр формы, – минимальное значение случайной величины x.

Плотность распределения Парето задается функцией

 

при x > и > 0,

 

при x ≤.

Среднее значение случайной величины определяется из формулы

 

Параметр  определяет среднее и дисперсию случайной величины:

- если ≤ 1, распределение имеет бесконечное среднее;

- если 1 ≤ ≤ 2, распределение имеет конечное среднее и бесконечную дисперсию;

- если ≤ 2, распределение имеет бесконечную дисперсию.

Существует отношение между параметром  и параметром Херста H

 

Создание и исследование моделей самоподобного трафика в системе NS-2

Моделируемая сеть состоит из узлов-генераторов самоподобного трафика (n(100) – n(199)), шлюза на сетевом процессоре  (1), маршрутизатора на сетевом процессоре (2), а также узла-приемника (3). Топология сети показана на рисунке 2.

Сетевой трафик в моделируемой сети создается сотней независимых отдельных источников, которые передают данные с одинаковой интенсивностью, но с длительностями, распределенными в соответствии с тяжелохвостым распределением [6].

Каждый   источник    генерирует   трафик   с   постоянной   битовой   скоростью  20000 бит/с, размер пакета составляет 128 байт. Длительности ON и OFF периодов являются случайными величинами с распределением Парето и задаются средними значениями 0,5 с и 1,5 с соответственно. Минимальные длительности составляют 0,0833 с для ON периода и 0,25 с для OFF периода. Параметр формы распределения равен 1,2.

На рисунках 3 и 4 приведены графики функций распределения и плотности распределения Парето для ON периода соответственно.

На рисунках 5 и 6 приведены графики функций распределения и плотности распределения Парето для OFF периода соответственно.

Смоделированный трафик был получен при временном разрешении 0,1 с, что обеспечивает высокий уровень усреднения. Это позволяет получать достоверные статистические данные.

Трафик, генерируемый одним источником в течение 10 с, 100 с и 5000 с, приведен на рисунках 7, 8 и 9 соответственно в виде зависимости числа принятых пакетов в единицу времени.

Выполним оценку показателя Херста при помощи методики R/S статистики (нормированного размаха), рассмотренной ранее. Для приведенной модели трафика данный показатель равен 0,86. Поскольку H > 0,5, исследуемый поток пакетов имеет персистентную природу (самоподдерживающийся поток), обладает длительной памятью и является самоподобным.

Профиль сетевого трафика, полученного при мультиплексировании 100 ON/OFF источников на временном промежутке от 0 до 100 с, показан на рисунке 10.

Приведенная зависимость была получена путем измерения числа принятых пакетов на сетевом процессоре-маршрутизаторе в единицу времени (0,1 с).

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

Параметр Херста для полученной модели трафика равен 0,81.

Гистограмма для временного ряда, отражающая плотность распределения числа пакетов в единицу времени, приведена на рисунке 11.

Визуально гистограмма похожа на распределение Пуассона, однако полученное значение показателя Херста опровергает это предположение. Следовательно, распределение трафика близко к пуассоновскому, но им не является. Установленную близость можно объяснить наличием большого числа мультиплексированных потоков пакетов.

Выводы

Разработаны имитационные модели самоподобного трафика пакетов , порождаемого одним источником и мультиплексированного трафика пакетов.

Разработан скрипт в системе NS-2 на языке Tcl, предназначенный для моделирования самоподобного сетевого трафика, генерируемого заданным числом независимых источников.

Разработана программа на языке C#, реализующая расчет показателя Херста на основании результатов моделирования, представленных в виде trace-файла, и выполняющая программное построение гистограммы временного ряда в пакете Excel.

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

Наличие в системе NS-2 интерфейсов расширения позволяет создавать комбинированные имитационные и имитационно-аналитические модели сетевых процессоров с применением объектно-ориентированных языков высокого уровня. Это является одним из направлений дальнейших исследований.

Литература

1. Бельков Д.В. Актуальность исследования фрактального трафика / Д.В. Бельков // Материалы IV международной научно-практической конференции «Постигането на висшето образование – 2008» – Т. 12. – С. 44-46.
2. Статистические свойства интернет трафика [Электронный ресурс]. Режим доступа: http://www.nag.ru/goodies/articles/sst/sst.html
3. «Фрактальная катастрофа» TCP/IP [Электронный ресурс]. Режим доступа: http://itc.ua/articles/_fraktalnaya_katastrofa_tcp_ip_5571/
4. Зюльков И.А. Самоподобные свойства трафика систем с повторными вызовами / И.А. Зюльков // Вестник ВГУ. – 2002. – (Серия «Физика, математика»). – № 1. – С. 20-26.
5. Network Simulator (Сетевой симулятор ns2) [Электронный ресурс]. Режим доступа: http://telematika.stu.neva.ru/FILES/KAFEDRA/STUDENTS/POSOBIE/ns-old-html/ns-old.htm
6. Шелухин О.И. Мультифракталы. Инфокоммуникационные приложения / О.И. Шелухин – М.: Горячая линия – Телеком, 2011. – 576 с.