Modern global network traffic model for simulation system

Full Text

Введение В течение последних двух десятилетий, начиная от известных статей, таких как [1], анализ и моделирование самоподобного трафика очень актуальная тема для теоретических и прикладных исследований. Представленные коллекции теоретических и практических достижений в этой области за последние двадцать лет можно найти в [2]. В настоящее время влияние самоподобного трафика на различные аспекты телекоммуникаций остается важной темой для исследований [3-6]. Важными проблемами в данной области являются разработка относительно простых в анализе моделей трафика, и оценка их способности генерировать трафик, близкий к реальному. Первой целью данной статьи является представление собственной модификации известной модели самоподобного трафика «M/G/∞ Input», реализованной в системе моделирования OMNeT. Модифицированная модель способна воспроизводить несколько характеристик реального трафика WAN сетей одновременно, включая параметр Херста, одномерное распределение вероятностей величин (ОРВВ) и нормированную автокорреляционную функцию (НАКФ) трафика. Потому вторая цель статьи - сделать параметры модифицированной модели «M/G/∞ Input» более интерпретируемыми с практической точки зрения. Отличие данной работы от хорошо известной статьи [7] в том, что там информационная скорость (ИС) индивидуальных источников (ИИ) предполагалась одинаковой и равной единице. Поэтому ОРВВ трафика, сгенерированного моделью «M/G/∞ Input» (такую модель в данной работе назовем базовой) было пуассоновским, а для последующего приведения к требуемому распределению использовалась преобразовывающая функция. По нашему мнению, недостаток данного подхода в том, что он сталкивается с трудностями трактовки преобразовывающей функции с практической точки зрения. В статье используется другой подход: мы предполагаем, что каждый ИИ может иметь свою собственную ИС, а суперпозиция таких неоднородных ИИ создает соответствующее ОРВВ результирующего трафика. Основные результаты данной работы были представлены на конференции [8]. Статья структурирована следующим образом: во втором разделе произведен обзор базовой модели «M/G/∞ Input» и представлена модификация, которая реализована в программном пакете; в третьем разделе описан программный пакет и предоставлены результаты моделирования трафика, в четвертом разделе подведены итоги и сделаны выводы. Модель «M/G/∞ Input» Для простоты будем рассматривать процесс с дискретным временем. Пусть ось времени делится на одинаковые временные интервалы, и размер каждого такого окна будет единицей времени. Также пусть количество информации измеряется в ячейках, а размер одной ячейки в байтах. Таким образом, трафик и ИС источника измеряется в ячейках в одно временное окно. В модели «M/G/∞ Input» число новых ИИ, появляющихся в системе в каждом временном окне является случайным. Все числа новых ИИ, во всех временных окнах, являются независимыми одинаково распределенными случайными величинами (НОРСВ) с пуассоновским законом распределения с параметром λ. Известно, что самоподобие моделируемого трафика определяется распределением вероятностей времени жизни ИИ - оно должно быть с тяжелым хвостом. Если время жизни для всех ИИ являются НОРСВ с обозначенной общей случайной величиной T и ее распределение вероятностей удовлетворяет , (1) тогда параметр Херста смоделированного трафика по «M/G/∞ Input» равен H. Чтобы сделать АКФ моделируемого трафика похожей на АКФ реального трафика, мы будем использовать следующую функцию распределения вероятностей времени жизни: (2) где x и y параметры для минимизации отклонения, C - нормирующая константа. Как показано в [9-10], в случае такой параметризации, нормированная АКФ моделируемого трафика имеет вид: (3) Имея несколько значений rk, k = 1; 2 … K, АКФ реального трафика, мы можем сделать АКФ (3) более близкой к реальной, производя минимизацию по x и y среднего квадратичного отклонения (4) В каждом временном окне в течение всей жизни каждый индивидуальный источник генерирует трафик (некоторое количество ячеек). Сумма потоков от всех активных источников и есть результирующий трафик модели. В базовой модели «M/G/∞ Input» считалось, что все источники имеют одинаковую скорость генерации трафика (информационную скорость). В стационарном состоянии системы величина результирующего трафика Yt в случайный момент времени t строго пропорциональна числу активных источников Nt в системе в тот же момент, и имеет пуассоновское распределение с параметром , (5) (E - оператор математического ожидания). Поэтому обозначим (6) Предложенная модификация базовой модели - это предположение, что ИС являются НОРСВ с общим обозначением случайной величиной S. Если в какой-то момент t в системе имеется Nt активных источников, то обозначим их скорости как Sk, k = 1; 2 … Nt. Как показано в [9-10], зная распределения вероятностей {Pr{Y = k}}k = 0; 1; 2 … величин трафика Y, мы можем найти распределение вероятностей случайной величины S, которое обеспечивает данное распределение трафика Y. Опишем эту процедуру с некоторыми пояснениями. Для начала допустим, что (7) Это «условие отсутствия фиктивных источников» обеспечивает ситуацию, что Yt = 0 тогда и только тогда, когда Nt = 0, поэтому и (8) . (9) Скорость индивидуального источника S (число ячеек в окно) целочисленная случайная величина, поэтому Yt = 1 тогда и только тогда, когда Nt = 1 и S1 = 1, поэтому , (10) откуда мы получаем Pr{S = 1}. Затем Yt = 2 тогда и только тогда, когда Nt = 1 и S1 = 2 или Nt = 2 и S1 + S2 = 2 (что значит S1 = S2 = 1), получаем ; (11) и, зная Pr{S = 1}, получаем (12) В общем случае имеем , (13) где может быть найдена как m-кратная свертка моментов конечной последовательности где все эти вероятности известны из предыдущих итераций. На практике расчет этих сверток является наиболее трудоемкой частью итерационной процедуры (7) и имеет экспоненциальную сложность, когда растет k. Из (5) мы можем найти . (14) В итоге, в нашей модели получились интерпретируемые параметры: интенсивность появления новых ИИ l, распределение вероятностей времени жизни ИИ и распределение вероятностей ИС ИИ. Моделирование трафика WAN сети Представленный программный пакет на базе OMNeT++ доступен по ссылке [12] и называется SelfSimMGI. Его первое назначение - анализ трафика, так как есть возможность сбора статистики о трафике для последующего расчета статистических характеристик и параметра Херста. Определенный модуль читает трафик из файла с трассой, генерирует OMNeT пакеты согласно записям, в файле и посылает их в исходящий порт. Другой модуль является сборщиком статистики, он собирает необходимую статистику, анализируя проходящие сквозь него OMNeT пакеты, вычисляет ОРВВ трафика, НАКФ и параметр Херста. Результаты записываются в XML файл. Вторая цель - моделирование трафика. В пакете имеется модуль-вычислитель параметров, который читает статистику из вышеупомянутого файла, вычисляет параметры «M/G/∞ Input» модели и записывает их в другой XML файл. Генератор трафика читает эти параметры из файла в начале каждого запуска моделирования и генерирует трафик как поток OMNeT пакетов в соответствии моделью «M/G/∞ Input». Статистические данные смоделированного трафика также собираются вышеупомянутым сборщиком статистики. В данной работе приведены результаты экспериментов на основе трех трасс из коллекции CAIDA [11]. Трассы 1 и 2 - одноминутные, записанные монитором equinix-chicago в двух противоположных направлениях: A и B. Они записаны 19. 12. 2013 г. в 13:00. Трасса 3 той же длительности, но записана монитором equinix-sanjose 20. 11. 2008 г. в 13:00. Обработка этих трасс была сделана с использованием временного окна, равного 15 мкс и размером ячейки, равным 100 байтам. Размер ячейки определяется из требуемой точности представленного трафика, а размер временного окна - из соображений вычисления параметров модели за умеренное время. Наиболее трудоемкая операция - это вычисление сверток в (13). Результаты о способности модельного трафика аппроксимировать реальный трафик представлены в графическом виде - некоторые количественные данные о способности аппроксимации модели см. в [10]. Для всех трасс представлено распределение вероятностей ИС ИИ и интенсивность появления новых ИИ l, а также ОРВВ и НАКФ реального и смоделированного трафиков. Для сравнения также приведены ОРВВ и НАКФ трафика, смоделированного по базовой модели «M/G/∞ Input» (все ИС для ИИ равны единице). Рис. 1. Распределение вероятностей скорости источника для трассы 1 Рис. 2. Распределение вероятностей трафика для трассы 1 Рис. 3. Нормированная АКФ для трассы 1 Интересно, что все распределения вероятностей ИС являются мультимодальными, и это обеспечивает очень хорошую аппроксимацию ОРВВ реального трафика, которое также мультимодальное. На рис. 5 отмечен интересный артефакт в ОРВВ реальной трассы вблизи значения 150-200 (ячеек на слот). Рис. 4. Распределение вероятностей скорости источника для трассы 2 Рис. 5. Распределение вероятностей трафика для трассы 2 Рис. 6. Нормированная АКФ для трассы 2 Принимая во внимание, что вблизи отметки 200 ячеек в окно на оси x (см. рис. 5) величина реального трафика составляет около 10 Гбит/с, то очевидно, что линия связи в этот момент была загружена почти на 100%, и система управления потоком начала ограничивать трафик (см. [6] для описания сетевого оборудования). Наша модель пока не обрабатывает такую ситуацию. Рис. 7. Распределение вероятностей скорости источника для трассы 3 Рис. 8. Распределение вероятностей трафика для трассы 3 Рис. 9. Нормированная АКФ для трассы 3 Как мы видим, мультимодальное поведение распределения вероятностей трафика часто происходит в трафике WAN сетей в течение последних двух десятилетий, однако интенсивность трафика выросла значительно за этот период времени. Значения параметров Херста для всех трасс представлены в таблице 1: видно, что самоподобность и корреляция достаточно хорошо воспроизводятся предложенной моделью «M/G/∞ Input». Таблица 1. Значения параметра Херста Трасса Параметр Херста Реальная трасса Модификация M/G/∞ Базовая M/G/∞ Трасса 1 0,66 0,75 0,74 Трасса 2 0,71 0,73 0,70 Трасса 3 0,70 0,71 0,72 Заключение Представлены совокупность экспериментальных результатов, полученных с помощью программного пакета SelfSimMGI на базе OMNeT для анализа трафика WAN сетей и моделирования. В модели получились хорошо интерпретируемые параметры. Обработка реальных трасс этой программой показывает интересный феномен мультимодального «пилообразного» вида у распределения вероятностей современного трафика WAN сетей. Причина такого поведения требует более глубокого исследования и понимания.

About the authors

Alexander Yurievich Privalov

Samara State Airspace University, Samara

Email: privalov1967@gmail.com

Alexander Aleksandrovich Tsarev

Samara State Airspace University, Samara

Email: al-xandr1@yandex.ru

References

Supplementary files