Автор: Костромицкий А. И., Волотка В. С.
Источник: http://314159.ru/...
Костромицкий А. И., Волотка В. С. Подходы к моделированию самоподобного трафика. Произведен обзор научных публикаций по рассматриваемой тематике за последние более чем полтора десятка лет. Проанализировано существующее состояние в области моделирования самоподобного трафика.
В настоящее время бурное развитие высоких технологий привело к появлению и повсеместному распространению сетей с пакетной передачей данных, которые постепенно стали вытеснять системы с коммутацией каналов.
Исследования различных типов сетевого трафика за последние полтора десятка лет доказывают, что сетевой трафик является самоподобным (self–similar) или фрактальным (fractal) по своей природе [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]. Самоподобие
представляет собой свойство процесса сохранять свое поведение и внешние признаки при рассмотрении в разном масштабе. Из этого следует, что используемые методы моделирования и расчета сетевых систем, основанные на использовании пуассоновских потоков, не дают полной и точной картины происходящего в сети.
Кроме того, самоподобный трафик имеет особую структуру, сохраняющуюся при многократном масштабировании. В реализации, как правило, присутствует некоторое количество выбросов при относительно небольшом среднем уровне трафика. Данное явление ухудшает характеристики (увеличивает потери, задержки, джиттер пакетов) при прохождении самоподобного трафика через узлы сети. На практике это проявляется в том, что пакеты, при высокой скорости их движения по сети, поступают на узел не по отдельности, а целой пачкой, что может приводить к их потерям из–за ограниченности буфера, рассчитанного по классическим методикам.
Эти особенности сетевого трафика вызвали лавинообразный рост публикаций и исследований по методам анализа, моделирования и прогнозирования самоподобного трафика.
Среди иностранных ученых, активно занимающихся вопросом самоподобия трафика, необходимо выделить W. Leland, M. Taqqu, W. Wilinger, D. Wilson, V. Paxson, которым принадлежат наиболее фундаментальные труды в этом направлении [1,2,3,4]. Активно работают также K. Park, A. Feldmann, P.M. Robinson, A.C. Gilbert, A. Erramilli и др. Среди российских и украинских исследователей необходимо отметить работы О. И. Шелухина, Б. С. Цыбакова, В. В. Петрова, А. В. Осина, А. Г. Ложковского, Е. В. Добровольского, А. В. Рослякова, А. В. Медных [5,6,7,8,9,10,11,12,13,14,15,16] и многих других авторов.
Несмотря на огромную популярность данной тематики и продолжительность периода (более полутора десятка лет) ее активного изучения, приходится констатировать, что до сих пор остается множество вопросов и нерешенных задач. Так, например, отсутствуют общепринятые универсальные достаточно точные и легкие в применении методы моделирования и прогнозирования поведения самоподобного трафика, методы проектирования мультисерсисных сетей.
Целью данной работы является анализ и классификация используемых современными исследователями моделей самоподобного трафика.
Методы моделирования сетевого трафика, концептуально можно разделить на два класса аналитические и имитационные.
Аналитическая модель — это совокупность математических выражений, формально описывающая моделируемый объект или процесс. Такие модели удобны для проведения теоретических исследований, однако, для большинства источников построение адекватной аналитической модели крайне затруднительно.
Имитационная модель — это набор алгоритмов, генерирующий некую последовательность, которая по своим характеристикам близка к реальной (экспериментально снятой с действующего объекта) последовательности. В качестве такой последовательности, например, может быть сетевой трафик. Использование имитационных моделей является зачастую более предпочтительным и удобным. В тоже время, как правило, имитационные модели имеют узкую специфику, и применение таких моделей требует значительной работы для адаптации модели под новые условия применения.
Возможны также комбинированные модели, сочетающие в себе аналитическую и алгоритмическую части [13].
На сегодняшний день разработано множество моделей, предназначенных для имитации фрактального трафика. Анализ доступных публикаций по моделированию самоподобного трафика позволяет выделить следующие модели.
Фрактальное броуновское движение (Fractional Brown Motion — FBM). В основе модели FBM лежит случайный процесс, начинающийся в начале координат с независимыми бесконечно малыми гауссовскими приращениями. FBM описывается аналитически. Также для генерации FBM широко используются алгоритмы случайного перемещения средней точки (RMD–алгоритм) и алгоритмы последовательного случайного сложения (SLA–алгоритм).
Фрактальный гауссовский шум (Fractional Gaussian Noise — FGN) [8,9]. FGN — стационарный в широком смысле стохастический процесс с определенным параметрами (средним значением, дисперсией, Херста) и автокорреляционной функцией заданного вида. По сравнению с обычным гауссовым шумом, FGN имеет дополнительный параметр Херста, который количественно определяет степень фрактального масштабирования. Основная трудность использования FBM и FGN — подбор наилучших значений параметров для получения генерируемого трафика, близкого по свойствам к экспериментально снятым реализациям трафика.
Хаотические отображения (Chaotic Map — СМАР). Такие модели являются достаточно распространенными и концептуально простыми, они используют меньшее число параметров, чем FGN и FBM, и их выбор имеет более наглядную трактовку.
Модели на основе техники динамического моделирования Маркова
(Dynamic Markov Modelling — DMM). Эти модели представляют собой автоматы с конечным числом состояний, изображаемые орграфами или диаграммами состояний модели. В процессе обучения модели, при получении очередного символа входного потока, происходит переход модели в следующее состояние и модификация частотных счетчиков, соответствующих вероятностям переходов. Выходом модели является набор вероятностей появления символов [10,11].
Модели с использованием нечеткой логики. Построение нечетких моделей, как правило, основано на настройке функций принадлежности по параметрам нечетких множеств, используемых в правилах, весов правил и на настройке операций. В [14] предложено использование нечеткой модели временного ряда нечетких тенденций, позволяющей эффективно моделировать и прогнозировать работу сложной технической системы.
Нейросетевые модели, которые позволяют решить задачу аппроксимации функций нескольких переменных по обучающей выборке путем погружения временного ряда в многомерное пространство.
Авторегрессионные модели (Autoregressive Models — AR) широко применяются для моделирования и предсказания благодаря свойству длительной памяти
самоподобных процессов. В этих моделях текущее значение генерируемой величины рассчитывается как взвешенная сумма N предыдущих отсчетов плюс случайная переменная. Как разновидности таких моделей используются модели ARMA (процесс скользящего среднего), ARIMA (интегральный процесс скользящего среднего) и FARIMA (фрактальный интегральный процесс скользящего среднего). К достоинствам последней необходимо отнести возможность гибкого управления корреляционной структурой (кратковременной и долговременной зависимостями, произвольным распределением).
Фрактальные точечные процессы (Fractal Point Process — FPP) являются очень наглядными для моделирования самоподобного трафика. Простейший точечный процесс представляется на временной оси неубывающей ступенчатой функцией, моменты роста которой являются случайными. Существует много модификаций FPP, которые достаточно экономичны и вычислительно эффективны.
ON/OFF — модели. В этих моделях трафик рассматривается как комбинация источников, которые его генерируют. Каждый источник имеет следующую структуру. Некоторый период времени они могут генерировать пакеты информации (так называемые ON–периоды), при этом внутри одного периода пакеты приходят с одинаковыми интервалами между ними. После ON–периода следует OFF–период, когда источник не генерирует пакеты. Размер ON– и OFF–периодов является случайной величиной, которая, как показано в работе [2], должна иметь конечное математическое ожидание и бесконечную дисперсию. Отметим, что в [6] ON/OFF — процесс классифицирован как чередующийся фрактальный процесс восстановления — одна из разновидностей FPP.
Фрактальное движение Леви движение (Fractional Levi Motion — FLM) относится к так называемым устойчивым процессам. В основе его моделирования лежат симметричные α–устойчивые распределения, характеризуемые кроме показателя Херста, еще и показателем Леви. FLM можно рассматривать как некое обобщение FBM и эффективно использовать для моделирования интенсивности трафика или скорости передачи, имеющих теоретически бесконечную дисперсию.
Мультифрактальные модели (Multifractional — MF) удачно воспроизводят трафик, агрегированный от нескольких существенно отличающихся источников. Мультифрактальность трафика проявляется в изменении статистических свойств реализации трафика при изменении масштаба агрегирования [15]. Для описания таких свойств вводятся дополнительные масштабная функция и моментный коэффициент. В основе MF моделей лежат консервативные бинарные мультипликативные каскады [6].
Вейвлет модели (Wavelet Models) строятся на основе обратного дискретного вейвлет–преобразования, который состоит в формировании с помощью масштабных и Вейвлет–коэффициентов дискретного временного ряда, используя функции детализации различного масштаба на основе прототипа полосовой Вейвлет–функции и низкочастотной скейлинг–функции. Вейвлет–модели могут иметь различное количество параметров (три и более) и достаточно эффективны для моделирования самоподобного трафика. Очень близкие по свойствам к Вейвлет–моделям являются модели на основе преобразования всплесков [16].
Модели на основе классических систем массового обслуживания. Как правило, такие модели удачно описывают трафик с пуассоновскими потоками. Однако, как показано в [3], такая модель как М/G/∞ способна создать приблизительно самоподобный трафик путем управления поведением хвоста
произвольного распределения обслуживания пользователей, создавая тем самым долговременную зависимость.
Практически все рассмотренные модели хорошо подходят для моделирования самоподобного трафика данных в телекоммуникационных сетях с коммутацией пакетов. Все модели обладают такими необходимыми для качественного моделирования свойствами, как долговременная зависимость, маштабируемость, стационарность и т. д. Однако современные исследования экспериментально снятых реализаций трафика показывают, что характеристики трафика могут изменяться в самых широких пределах и зависеть от большого числа параметров и настроек реальных сетей, характеристик протоколов, передаваемой информации и поведения пользователей.
Кроме перечисленных выше, выявлены, например, такие характеристики трафика как наличие кратковременных зависимостей, нестационарность, мультифрактальность.
Общим недостатком, используемых в настоящее время моделей сетевого трафика, является их направленность на какую–либо конкретную разновидность трафика либо сети и отсутствие универсальности, хотя некоторые авторы претендуют на универсальность разработанных моделей. Кроме того, применение их на практике приводит к большому объему исследовательской работы, требуемой для адаптации (обучения) модели к параметрам сетевой конфигурации или параметра трафика. Все это значительно усложняет построение универсальной модели, из–за большого разнообразия, как самих источников, так и сетевых конфигураций, оказывающих влияние на их работу. Отметим также, что поскольку реальный трафик, как правило, не является строго самоподобным, простые модели, такие как, например, FBM, FGN, FPP, FLM и М/G/∞, не всегда могут адекватно описать реальный трафик.
Адекватность описания реального трафика достигается путем усложнения моделей, объединения нескольких моделей, введения дополнительных параметров. Естественно для более сложных моделей требуются большие вычислительные возможности или большее время для генерирования реализаций трафика. Это не является проблемой при проведении единичных экспериментов и исследований, когда время генерации очередного отсчета трафика или всей реализации ограничено терпеливостью
исследователя. Но как только встает проблема применения некой модели для прогнозирования трафика с целью дальнейшего оптимального управления ресурсами сети, фактор реального времени накладывает жесткие ограничения на сложность модели при заданных вычислительных возможностях сетевых узлов и агентов управления.
Прогнозы рынка современных видов услуг и реальные статистические данные операторов свидетельствуют, в ряде случаев, о существенных расхождениях. В отличие от телефонии прогностические оценки трафика данных очень недостоверны. Это свидетельствует о недостаточном развитии теории прогнозирования мультисервисного (самоподобного) трафика. С другой стороны, именно на знании параметров трафика базируется основная часть работ по расчету сети. Поэтому одна из самых актуальных задач на современном этапе развития NGN — разработка новых или улучшение существующих методов моделирования и прогнозирования для трафика NGN.
1. Taqqu M., Willinger W., Sherman R. Proof of a fundamental result in self–similar traffic modeling. Computer Communication Review, 1997, vol. 27, no. 2, pp. 5–23.
2. Leland W., Taqqu M., Willinger W., Wilson D. On the self–similar nature of Ethernet traffic. IEEE/ACM Transactions on Networking, 2(1), pp. 1–15, February, 1994.
3. Paxon V., Floyd S. Wide–area traffic: The failure of Poisson modeling. // IEEE/ACM Transactions on Networking #3, 1995. — pp.226–244.
4. Feldmann A., Gilbert A. C., Willinger W. Data Networks as Cascades: Investigating the multifractal nature of Internet WAN traffic, Proc. 1998 ACM SIGCOM, pp. 42–55.
5. Шелухин О. И., Тенякишев А. М., Осин А. В. Фрактальные процессы в телекоммуникациях. Монография / Под ред. О. И. Шелухина. — М.: Радиотехника, 2003. — 480 с.
6. Шелухин О. И., Осин А. В., Смольский С. М. Самоподобие и фракталы. Телекоммуникационные приложения / Под ред. О. И. Шелухина. — М.: ФИЗМАТЛИТ. 2008. — 368 с.
7. Цыбаков Б. С. Модель телетрафика на основе самоподобного случайного процесса // Радиотехника. — 1999. — Вып. 5. — С. 24–31.
8. Петров В. В. Структура телетрафика и алгоритм обеспечения качества обслуживания при влиянии эффекта самоподобия: Диссертация на соискание ученой степени кандидата технических наук — Москва, 2004. — 199 с.
9. Ложковский A. Г. Модель мультисервисного трафика и метод расчета параметров QoS при его обслуживании // Радиотехника. — 2009. — Вып. 157. — С. 48–52.
10. Добровольский Е. В., Нечипорук О. Л. Имитационное моделирование источников нагрузки в сетях передачи данных с коммутацией пакетов // Наукові праці ОНAЗ ім. О. С. Попова. — 2000. — № 3. — С. 19–23.
11. Добровольский Е. В., Нечипорук О. Л. Моделирование сетевого трафика с использованием контекстных методов // Наукові праці ОНAЗ ім. О. С. Попова. — 2005. — № 1. — С. 24–32.
12. Росляков А. В., Криштофович А. Ю. Математическое описание автомодельного трафика. 4–я Международная конференция DSPA–2002.
13. Медных А. В. Разработка методов моделирования самоподобного сетевого трафика // Зв’язок. — 2007. — № 6. — С. 20–22.
14. Юнусов Т. Р. Моделирование трафика терминал–сервера на основе анализа нечетких тенденция временных рядов. Инфокоммуникационные технологии, том 6, № 1, 2008. — С. 55–64.
15. Шелухин О. И., Осин А. В. Мультифрактальный анализ самоподобного WAN–трафика. Электротехнические и информационные комплексы и системы, № 1, т. 3, 2007. С. 21–27.
16. Заборовский В. С. методы и средства исследования процессов в высокоскоростных компьютерных сетях: Диссертация на соискание ученой степени доктора технических наук — Санкт–Петербург, 1999. — 268 с.