Modern global network traffic model for simulation system

Abstract


Currently, the impact of traffic self-similarity on different aspects of telecommunications is still an important research topic. One of the important problems in this field is developing tractable traffic models and evaluating their ability to match closely real traffic behavior. The first purpose of this paper is to present OMNET++ realization of our modification of well-known self-similar traffic model «M/G/∞ Input». Modified model is able to capture several characteristics of real WAN traffic together, including Hurst parameter, probability distribution of traffic value and autocorrelation function (ACF) of traffic value. Another purpose of this paper is to make parameters of modified «M/G/∞ Input» model more tractable from the practical point of view. An OMNET package with an implementation of a useful modification of well-known self-similar traffic model is presented. The package is designed for analysis of real WAN traffic traces, identification of model parameters and generation of a synthetic traffic, which is close to real one by a number of characteristics simultaneously. These characteristics include traffic value probability distribution, normalized autocorrelation function and Hurst parameter. Performance of the package was tested with traffic traces from CAIDA and Internet Traffic Archive collections. An interesting phenomenon of multimodal «saw-like» form of the probability distribution of modern WAN traffic was reviled in these experiments.

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

  1. Leland W., Taqqu M., Willinger W., Wilson D. On the self-similar nature of Ethernet traffic (extended version) // IEEE/ACM Trans. on Networking. Vol. 2, No.1, February 1994. - P. 1-15.
  2. Park K., Willinger W., Wiley Ed. Self-similar Network Traffic and Performance Evaluation // John Wiley & Sons Inc. New-York, 2000. - 556 p.
  3. Xiaolong Jin, Geyong Min. A heuristic flow-decomposition approach for generalized processor sharing under self-similar traffic // J. Comput. Syst. Sci. Vol. 74, No. 6, September 2008. - P. 1055-1066.
  4. Perez C.S., Dominguez L.R., Pacheco Ju-C. R. A simulation scenario for performance studies under self-similar traffic // In Proc. of the 8-th WSEAS Intern. Conf. on Data Networks, Communications, Computers (DNCOCO'09). USA, Wisconsin, Stevens Point, 2009. - P. .
  5. Galkin A.M., Simonina O.A., Yanovsky G.G. Multiservice IP Network QoS Parameters Estimation in Presence of Self-similar Traffic // In Proc. of the 6th International Conf. on Next Generation Teletraffic and Wired/Wireless Advanced Networking (NEW2AN'06). Berlin, Heidelberg Springer-Verlag, 2006. - P. .
  6. Horn G., Kvalbein A., Blomskold J., Nilsen E. An empirical comparison of generators for self similar simulated traffic // Perform. Eval. Vol. 64, No. 2, February 2007. - P. .
  7. Krunz M.M., Makowski A.M. Modeling video traffic using M/G/∞ input processes: a compromise between Markovian and LRD models // IEEE J.Sel. A. Commun. Vol. 16, No. 5, September 2006. - P. .
  8. Privalov A., Tsarev A. Analysis and simulation of WAN traffic by self-similar traffic model with OMNeT // In Proc. of the 10th Intern. Wireless Communications and Mobile Computing Conference (IWCMC'14). Cyprus, Nicosia, August 4-8, 2014. - P. .
  9. Privalov A., Blagov A. Some Models Parameters Calculation for Simulation of Network Traffic Marginal Distribution and Self-similarity // 23rd European Conference of Modeling and Simulation (ECMS). Madrid, 2009. - P.51-60.
  10. Privalov A., Blagov A. Approximative models of data network self-similar traffic // Germany, Lambert Academic Publishing (LAP), 2013. - 120 p.
  11. The Cooperative Association for Internet Data Analysis (CAIDA). URL: http://www.caida.org
  12. Model catalog on OMNET++-community cite URL: http://omnetpp.org/index.php/models/ catalog

Statistics

Views

Abstract - 20

PDF (Russian) - 4

Cited-By


Article Metrics

Metrics Loading ...

Copyright (c) 2015 Privalov A.Y., Tsarev A.A.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies