РАЗДЕЛ 2
ПРИМЕНЕНИЕ КОНТЕКСТНЫХ МЕТОДОВ
ДЛЯ МОДЕЛИРОВАНИЯ ИСТОЧНИКОВ СЕТЕВОЙ НАГРУЗКИ
В диссертационной работе предложено использование приемов динамического контекстного моделирования (КМ) для построения универсальной имитационной модели (УИМ) трафика сетевых приложений.
В основе идеи контекстного моделирования лежит анализ статистик источника сообщений в различных контекстах его реализации с дальнейшим использованием полученной информации для прогнозирования распределения вероятностей последующих сообщений генерируемых источником. Используя в качестве прогноза такой набор вероятностей, при помощи генератора псевдослучайных чисел, возможно создание статистически подобной последовательности, имитирующей поведение моделируемого источника сообщений.
В настоящее время контекстные методы находят применение в качестве методов предсказания источников информации обладающих контекстными зависимостями в таких областях, как сжатие данных [61,62,65,67,71] и распознавание образов. Однако, каких-либо сведений об использовании контекстных методов для моделирования сетевого трафика в литературе обнаружено не было.
Установлено, что последовательности величин интенсивности сетевой нагрузки, создаваемые большинством приложений, также обладают выраженными статистическими контекстными зависимостями, что создает предпосылки применения контекстных методов для моделирования их основных характеристик. Так, используя прогноз распределения вероятностей полученный с помощью КМ, возможно получение имитационных последовательностей подобных регистрируемым последовательностям значений интенсивности сетевого трафика, создаваемого моделируемым источником нагрузки.
На рис. 2.1 изображена диаграмма, сопоставляющая величины последовательных интервалов ti и ti+1 между появлениями кадров в локальной сети Ethernet [34]. Регулярные структуры, которые просматриваются на графике, однозначно говорят о наличии существенной детерминированной компоненты в последовательности интервалов прибытия кадров, что, в свою очередь определяет наличие такой компоненты и в последовательности величин интенсивностей сетевой нагрузки. Наличие подобных регулярных структур указывает также на наличие контекстных зависимостей как минимум 1-го порядка в наблюдаемом трафике (поскольку можно наблюдать статистическую зависимость появления определенных интервалов в зависимости от их предшественников).
Рис. 2.1. Фазовая диаграмма интервалов (ti и ti+1) между последовательными появлениями кадров, наблюдаемыми в сетях Ethernet
Одной из основных сфер, в которых происходило развитие контекстных методов моделирования, является сжатие данных. В процессе совершенствования методов сжатия обозначились два основных класса контекстных моделей: с явным ограничением порядков используемых контекстов (контекстно-ограниченные методы) и без такового.
К первому классу относится группа методов предсказания по частичному совпадению (Prediction by Partial Matching, PPM) [64,66,67]. Как показано далее, методы данной группы могут быть адаптированы для имитации сетевого трафика.
Для воплощения концепции контекстного моделирования в специализированном программном обеспечении, в диссертационной работе использован метод называемый динамическим марковским моделированием (ДММ, Dinamyc Markov Modelling, DMM) [55,56,57,58,63,65,66], который был адаптирован с учетом особенностей, свойственных процессу моделирования сетевого трафика. Данный метод относится ко второму классу контекстных методов, в указанном выше смысле, и более удобен в применении для имитационного моделирования последовательностей величин сетевой нагрузки.
Материал данного раздела концептуально структурирован следующим образом:
1. Рассмотрена общая концепция современных контекстных методов, в разрезе их применения для сжатия данных. Большее внимание (ввиду распространенности и эффективности в данной области) уделено семейству контекстно-ограниченных моделей, использующих предсказание по частичному совпадению.
2. Предлагается адаптация контекстно-ограниченных методов (в частности группы методов предсказания по частичному совпадению) для использования в новой предметной области: имитационном моделировании сетевого трафика.
3. Рассмотрено использование конечных автоматов в методах контекстного моделирования. Приведено подробное описание метода динамического марковского моделирования, а также его обобщенной модификации.
4. Предложена адаптация метода ДММ для имитационного моделирования сетевого трафика (в частности трафика отдельных приложений). Указаны возможные проблемные моменты, возникающие в этой предметной области, а также пути их решения, примененные в разработанной программной реализации метода.
2.1. Контекстные методы моделирования источников информации
Рассмотрим дискретный источник сообщений с памятью, генерирующий сообщения в дискретном времени. Сообщения источника кодируются символами an некоторого алфавита U. В случае моделирования трафика приложений, символами будут являться измеренные значения интенсивности нагрузки, создаваемой приложением. Последовательность символов an (где an - значение интенсивности нагрузки в момент времени n), созданную этим источником (в наше случае приложением, создающим сетевой трафик) за временной промежуток [0,t] (t - текущий момент времени), обозначим как S, где
S = {a0,a1,...at-1 at}.
Текущим контекстом порядка i будем называть строку длины i, являющуюся суффиксом рассматриваемой последовательности (включая текущий символ). Например, текущий контекст первого порядка для S будет состоять из символа at , а текущий контекст третьего порядка для данного случая будет представлен строкой {at-2at-1at}.
2.1.1. Модели с фиксированным контекстом. Наиболее известной сферой применения методов контекстного моделирования является сжатие данных, т.е. устранение избыточности их представления. Современные концепции рассматривают процесс сжатия состоящим из двух частей - моделирован