Обзор подходов к моделированию модуля управления трафиком

Тип работы:
Реферат
Предмет:
Кибернетика


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Обзор подходов к моделированию модуля управления трафиком
В каждой области знаний исторически существует тята к достаточно узкому кругу известных методов и математических моделей, что приводит к стагнации процесса исследований. Возможны два варианта работы с математическими моделями: нахождение задачи, подходящей к используемой теории (теоретико-ориентированный подход) и подбор метода решения под существующую задачу (проблемно-ориентированный подход). Второй подход представляется авторам более предпочтительным, так как он имеет практическую направленность. При этом возникает задача выбора подходящего метода построения модели.
В данной работе предложено в качестве первого шага исследования рассмотреть научные области, наиболее близкие к изучаемому объекту. Например, для задач моделирования сетевого трафика наиболее близкой и развитой является задача моделирования транспортных потоков. Другой пример -использование эволюционных моделей для решения задач в области биологии.
Для моделирования модуля управления трафиком предложено использовать подходы и методы, разработанные в различных естественно-научных и технических областях. Сделан обзор возможных подходов к моделированию подобных систем. Представлены конкретные методы математического моделирования с обоснованием области их применения. Выделены несколько групп методов, описывающих какдинамическое поведение системы, так и прогноз-ное поведение подсистемы в рамках основной системы. Обсуждается применимость к рассматриваемой задаче макроскопических (например, гидродинамических, газодинамических) и микроскопических моделей (например, клеточные автоматы, теория массового обслуживания).
Ключевые слова: система активного управления, гидродинамические модели, газодинамические модели, клеточные автоматы, теория автоматического управления.
Кулябов Д. С. ,
к.ф. -м.н., доцент кафедры систем телекоммуникаций РУДН, dskulyabov@gmail. com
Королькова А. В. ,
к.ф. -м.н., доцент кафедры систем телекоммуникаций РУДН, akorolkova@sci. pfu. edu. ru, avkorolkova@gmail. com
Зарядов И. С. ,
к.ф. -м.н., старший преподаватель кафедры теории вероятностей и математической статистики РУДН, izaiyadov@gmail. com
Введение
Математическое моделирование имеет очень широкое применение в целях изучения как естественнонаучных, так и технических явлений. Оно позволяет не только предсказать поведение изучаемого предмета, но и понять его сущность. При этом следует иметь в виду, что с практической точки зрения математическое моделирование не всегда востребовано. Например, если сеть передачи данных требует для своего функционирования определенного минимального значения пропускной способности, то зачастую более выгодно просто построить сеть с запасом пропускной способности (из-за дешевизны оборудования), нежели исследовать и оптимизировать данную характеристику.
Модель сети передачи данных представляет собой совокупность следующих основных сущностей: сетевой трафик- прибор (модуль управления), трансформирующий некоторым образом трафик- процесс взаимодействия трафика с прибором (модулем управнения).
Обычно исследователи сосредотачивают своё внимание только на части сущностей, априорно вводя остальные. При дальнейшем рассмотрении априорность предположений зачастую теряется из виду, что приводит к искажению области применения модели. Выбирая определённый метод моделирования, следует ясно представлять его область применения, понимать, что конкретно он моделирует. Кроме того, представляется оправданным переход от монопарадигменных к мультипарадиг-менным моделям. Использование для каждого элемента модели наиболее подходящего подхода и рассмотрение их в совокупности позволит отказаться от априорных предположений и построить замкнутую модель.
При моделировании сетей передачи данных обычно прибегаю! к методам теории массового обслуживания или методам теории автоматического управления. При всей мощности данных методов они не универсальны, имеют свои области применения. Например, одним из недостатков теории массового обслуживания можно назвать ее плохую масштабируемость, поэтому основной областью ее применения является описание небольшой подсистемы, а не системы в целом. Кроме того, для описания трафика для простоты предпочитают использовать распределение Пуассона, поскольку подобные модели хорошо изучены. В тоже время есть работы, в которых предлагается использовать для описание пакетного трафика гиперболические распределения [ 1 ], которые по мнению авторов более реалистичны. Методы теории автоматического управления, в свою очередь, описывают процесс взаимодействия прибора с трафиком, однако описание трафика и прибора приходится вводить априорно.
Можно воспользоваться так называемым «моделированием по аналогии», в основе которого лежит сравнение свойств, признаков или отношений у различных в целом объектов или явлений. Обычно моделирование по аналогии применяют, когда можно подобрать
хорошо изученный процесс из другой области науки и приспособить готовую модель к изучаемому объекту. В случае сетевого трафика — это методы, предложенные в рамках исследования дорожного движения [2].
Классификация моделей
Рассмотрим кратко классификацию моделей на примере возможных подходов к моделированию сетей передачи данных.
Стандартный подход к классификации — классификация моделей по формальным признакам: линейные или нелинейные- сосредоточенные или распределённые системы- детерминированные или стохастические'-, статические или динамические'-, дискретные или непрерывные.
Выбор детерминированной или стохастической модели зависит от того, определяет ли начальное состояние дальнейшее поведение системы.
В статических моделях считается, что моделируемый процесс вышел на стационарный режим, все переходные процессы завершены. Динамические же модели работают в реальном масштабе времени.
Непрерывность и дискретность модели следует рассматривать отдельно для пространственных параметров и времени (хотя зачастую они взаимосвязаны).
Рассмотрим еще один подход к разделению моделей. Можно моделировать поведение каждого пакет в системе. Тогда мы имеем микроскопическую модель. Если же вместо изучения поведения каждого отдельного пакета изучаются характеристики всего потока, то имеем макроскопическую модель.
По функциональной роли (то есть по решаемой задаче) модели можно разделить (см., например [2]) на прогнозные, имитационные и оптимизационные.
Прогнозные модели выполняют задачу нахождения усреднённых параметров потоков данных по начальному расположению источников и приёмников данных (например, объём трафика, среднесуточные колебания трафика и т. д.), а также по топологии сети (связи между узлами сети, характеристики связей).
Имитационные модели ставят своей целью воспроизведение всех деталей процесса передачи данных, его развитие во времени. Входными данными служат собственно потоки донных и их усреднённые параметры. Таким образом, имитационные модели дополняют прогнозные модели.
Прогнозные и имитационные модели предназначены для адекватного воспроизведения передаваемых по сети потоков данных. Оптимизационные модели в свою очередь используются при анализе и поиске оптимальных значений различных характеристик телекоммуникационных систем.
В следующих двух разделах остановимся более подробно на прогнозных и имитационных моделях в рамках исследования сетей передачи данных.
Прогнозные модели
Прогнозные модели предназначены для анализа топологии сети и основных усреднённых характеристик трафика. Они позволяют получить, например, загруженность разных участков сети, отследить, как она будет меняться при изменении топологии сети, места распо-
ложения активного оборудования, потребителей и генераторов трафика.
Сеть разбивается на области (домены, районы). Строится так называемая «матрица корреспонденций», элементами которой являются объёмы трафика между парами доменов. Весь трафик может быть разбит на группы по критериям: по различию в целях, по типу трафика, по различию в маршруте. Для каждой группы выписывается своя матрица корреспонденций. Оценка трафика связана с взаимным размещение источников и потребителей трафика.
Для моделирования используется несколько типов моделей. Одной из простейших моделей оценки междоменных корреспонденций является гравитационная модель [3]. Она основана на предположении, что корреспонденция из одного домена в другой пропорциональна общему объёму исходящего трафика из первого домена, общему объёму входящего трафика во второй домен и некоторой функции (функции тяготения), зависящей от некоторого транспортного расстояния между этими доменами1.
Следующий тип — термодинамические модели. Наиболее известная — энтропийная модель [4]. Она исходит из вероятностного описания сетевого трафика. Все пакеты случайным образом распределяются по некоторому набору возможных состояний. Независимый и случайный выбор состояний приводит к тем или иным макроскопическим состояниям системы. В энтропийной модели считается, что состояние, реализуемое в реальности, есть состояние с наибольшим статистическим весом (статистические веса состояний отражают сравнительные вероятности реализации различных состояний в системе). Использование статистического веса состояний вместо распределения вероятностей тех или иных состояний объясняется тем, что в энтропийных моделях может не существовать конечного и нормированного распределения вероятностей. Для простоты состояния с наибольшим статистическим весом часто называют наиболее вероятными состояниями. При определённых ограничениях энтропийная модель приводит к гравитационной.
Отдельно можно выделить класс моделей с переменным количеством источников и получателей трафика, описываемых с помощью как детерминистических, так и стохастических популяционных моделей [5]. Пример -одноранговые сети [6].
Таким образом, в прогнозных моделях исходная система рассматривается как единое целое, на первый план выходит участок передачи данных, модуль управления лишь меняет параметры его функционирования. Поэтому в этом подходе нет необходимости выделять модуль управления в отдельную сущность.
Имитационные модели
Здесь следует выделить два типа моделей: микроскопические и макроскопические.
К макроскопическим в первую очередь относятся гидродинамические модели [7]. В них поток пакетов представляется как поток сжимаемой жидкости. Отдельные пакеты в рамках данных моделей не рассматриваются. Рассматриваются только макроскопические
I В рамках теории телетрафика — предложенная и обслуженная нагрузка.
характеристики потока, а именно плотность, поток, средняя скорость. Фактически данные модели строятся на основе одномерного уравнения Навье-Стокса.
Собственно гидродинамические модели представляют собой динамическую систему в пространстве полей скоростей обобщённой жидкости, описывающую эволюцию начального поля скоростей частиц жидкости под влиянием их взаимодействия (давления и вязкости), а также под возможным влиянием внешних сил. Под действием этой эволюции динамическая система может прийти к равновесному (стационарному) состоянию, когда скорость потока в каждой точке области течения не меняется со временем (хотя каждая частица движется и меняет со временем свою скорость).
На основе статистической физики строятся кинетические (газодинамические) [8] модели. Хотя их относят к макроскопическим моделям, но, строго говоря, они являются промежуточными между макроскопическими и микроскопическими моделями. Поток разбивается на отдельные пакеты (подобно микроскопическим моделям), но рассматривается не каждый пакет отдельно, а ансамбль пакетов. При изучении используется фазовая плотность потока. В результате получаются макроскопические уравнения движения (подобно макроскопическим моделям). При согласованности гидродинамических и газодинамических моделей получаются одни и те же макропоказатели, что впрочем и не удивительно.
В микроскопических моделях рассматривается эволюция каждого отдельного пакета. При этом явно выделяются детерминистические и стохастические модели.
К стохастическим методам моделирования следует в первую очередь отнести методы теории массового обслуживания. При этом наибольшее применение получили дискретные модели теории массового обслуживания.
В последнее время стали популярными модели, базирующиеся на клеточных автоматах, в которых динамика отдельных пакетов описывается стохастически и дискретно (отметим, что сама процедура дискретизации неоднозначна и нетривиальна). Преимуществами данных моделей является их высокая эффективность с вычислительной точки зрения.
Модели, базирующиеся на клеточных автоматах, используют следующие принципы построения:
— дискретизация пространства на идентичные ячейки-
— конечное число возможных состояний-
— периодическое обновление состояния с элементарным временным шагом-
— обновления захватывают короткие дистанции (непосредственно примыкающих соседей). Всё это позволяет использовать параллельные вычисления.
В рамках имитационного подхода в системе явно выделяются отдельные сущности: поток трафика, модуль управления, взаимодействие потока трафика с модулем управления. Рассмотренные модели описывают систему как единое целое, учитывая все эти сущности, что отличает их от более классических подходов (теории массового обслуживания, теории автоматического управления), ориентированных на какой-либо отдельный аспект.
Предлагаемые подходы к моделированию модуля управления трафиком
В работах [9, 10] была построена и исследована модель модуля управления трафиком на базе алгоритма
RED (Random Early Detection). При построении модели были выделены три сущности: сетевой трафик, модуль управления трафиком RED, взаимодействие трафика и модуля управления. Согласно стандартам была записана система дифференциальных уравнений для модуля RED, а также описан трафик типа TCP Tahoe и TCP Reno. Всё это было объединено в систему обыкновенных дифференциальных уравнений с учётом взаимодействия трафика с модулем управления. В качестве метода исследования была выбрана качественная теория дифференциальных уравнений. Возможно также применение теории автоматического управления как на этапе построения модели, так и на этапе исследования. Данная работа выявила следующий недостаток используемого подхода: полученная модель оказалась нерасширяемой — в рамках модели не удалось ввести другие типы трафика либо другие типы модуля управления (DropTail, BLUE). 11оэтому внимание авторов переключилось на более универсальные способы построения моделей в надежде описагь более широкий класс систем, используя единый подход.
На данный момент предполагается использовать следующие подходы для построения модели. Во-первых, использовать гидродинамический (уравнение Навье-Стокса) и газодинамический (уравнения статфизики) подходы для описание полной системы из сетевого трафика и модуля управления, который рассматривается как внешнее воздействие, меняющее характер трафика. Во-вторых, использовать метод клеточных автоматов для компьютерного моделирования процесса взаимодействия пакетного трафика и модуля управления. В результате авторы надеются получить математическую модель, в рамках которой можно будет описать произвольный пакетный трафик и произвольный модуль управления трафиком. Полученные макромодели планируется исследовать в рамках качественной теории дифференциальных уравнений. Макроскопическая и микроскопическая модели должны верифицировать друг друга.
Заключение
В работе сделан краткий обзор основных методов, которые можно применить для моделирования участка сети с модулем управления трафиком или набора таких участков. Выбор класса модели диктуется, в первую очередь, результатами, которые необходимо получить. Для исследования работы модуля управления предложено использовать рассмотренные имитационные модели.
Литература
1. Shcluhin 0.1., Smolskiy S.М., Osin A.V. Self Similar Processes in Telecommunications. -John Wiley and Sons, 2007.
2. Швецов В. И. Математическое моделирование транспортных потоков // Автоматика и Телемеханика, 2003. № 11. С. 3−46.
3. Voorhees A.M. A general theory of traffic movement. ITE, 1955.
4. Wilson A.G. A statistical theory of spatial distribution models//Transpn. Res. — 1967. V E — Pp. 253−270.
5. Базыкин А. Д. Нелинейная динамика взаимодействующих популяций. — Москва- Ижевск: Институт компьютерных исследований, 2003. 368 с.
6. Veciana G. de, Yang X. Fairness, incentives and performance in peer-to-peer networks // Forty-first Annual Allerton

ПоказатьСвернуть
Заполнить форму текущей работой