Тезисы к докладу, сделанному на региональной студенческой научно-технической конференции "Компьютерный мониторинг и информационные технологии" 31 мая 2005 года в Донецком Национальном Техническом Университете (ДонНТУ)
А. В. Мирецкий, Ю. В. Ладыженский
Донецкий Национальный Технический Университет
В настоящее время разработано множество алгоритмов, которые частично решают проблему оптимальной маршрутизации. Возникает вопрос о том, какой алгоритм является наиболее эффективным. Для того, чтобы определить эффективность алгоритма, необходимо построить модель сети, использующей исследуемый алгоритм маршрутизации. В модели должны происходить процессы, приближенные к реальности.
Разработан дискретно-событийный симулятор для моделирования сети, использующей исследуемый алгоритм маршрутизации. Симулятор использует одну главную структуру - список запланированных событий. Каждое событие - это структура, в которой хранится идентификатор события, время наступления события, обработчик события и дополнительные параметры. Все события в списке отсортированы по времени наступления. Из списка постоянно в процессе моделирования выбирается событие и отправляется к обработчику, который указан в структуре события. Время моделирования постоянно изменяется и устанавливается с помощью текущего запланированного события.
Выделяются два базовых класса объектов: Планировщик событий (Event scheduler) и Обработчик событий (Event Handler). Экземпляры первого класса занимаются планированием событий, а экземпляры второго - их обработкой. В процессе обработки событий сам обработчик может <порождать> новые события, которые отправляются к планировщику.
Моделируемая сеть является нерегулярной, с неориентированной на соединение топологией, с сетевым уровнем IP (в терминах ISO-OSI) и с очень простым транспортным уровнем. Подсети рассматриваются как отдельные узлы-хосты, соединенные с интерфейсными узлами - шлюзами. Шлюзы выполняют довольно сложные задачи сетевого уровня, включая маршрутизацию. Группы шлюзов объединяются в произвольную топологию. Все шлюзы расположены на одном и том же иерархическом уровне и между ними выполняется <плоская> маршрутизация [1].
Модель коммуникационной сети представлена направленным взвешенным графом с N узлами, которые обрабатывают и перенаправляют данные. Все линии связи рассматриваются как каналы передачи битов, характеризующиеся пропускной способностью (бит/сек) и задержкой передачи (сек), доступ к ним осуществляется по мультиплексной схеме. С каждой входящей и выходящей линией связи узла связаны очереди входящих и выходящих пакетов. Таким образом, каждый узел в сети является узлом с промежуточным хранением, т.е. содержит в себе буфер, где хранятся пришедшие и выходящие пакеты. Этот буфер является разделяемым ресурсом для всех очередей. Узлы действуют одновременно и как хосты (конечная точка сессии), и как шлюзы (маршрутизаторы, элементы перенаправления данных). На транспортном уровне нет контроля ошибок, нет средств установления правильной последовательности пакетов-фрагментов, нет подтверждений пересылки, т.е. однажды посланный пакет рассматривается как подтвержденный.
Для каждого входящего пакета компоненты маршрутизации узла используют информацию из локальной маршрутной таблицы для определения выходящей линии связи, по которой будет направлен. Если ресурсы линии связи доступны, то они ре- зервируются, и устанавливается режим передачи данных. Время, необходимое на перемещение пакета из узла в один из соседних узлов, зависит от размера пакета и от характеристик передачи данных линии связи. Если по прибытию пакета в буфере недостаточно места для его размещения, то пакет теряется. Иначе пакет помещается в очередь входящих пакетов для последующего обслуживания и маршрутизации.
Модель рабочей нагрузки объединяет простые механизмы управления потоками. Между парами узлов сети устанавливаются сессии (потоки пакетов данных) с заданной скоростью передачи (пара узлов, а также скорость передачи данных между ними выбираются с использованием определенных вероятностных законов), т.е. из одного узла в другой регулярно отправляются пакеты данных.
В модели сети выделяются следующие классы объектов: Узел сети (Network Node), Линия связи (Link), Таблица маршрутизации (Routing Table), Маршрутизатор (Router), Генератор рабочей нагрузки (Traffic Generator) и Пакет (Packet). Все эти классы, кроме пакета, являются прямыми потомками класса Обработчик событий (Event Handler). Объектная модель сети имеет следующую структуру:
Класс Маршрутизатор - это абстрактный класс. В классах-потомках этого базового класса реализованы конкретные алгоритмы маршрутизации. В настоящее время в симуляторе имеется два класса-потомка, в которых реализованы алгоритмы OSPF [1] и AntNet [2].
Класс Пакет также является базовым. Он представляет обычные пакеты данных. Потомки этого класса представляют агентов - специальные пакеты, которыми обмениваются маршрутизаторы. Агенты - это основа адаптивной маршрутизации. В симуляторе для алгоритмов маршрутизации OSPF и AntNet реализованы: пакет маршрутизации для OSPF и Муравей-агент для AntNet.
В симуляторе имеется специальный класс Монитор (Network Monitor), который управляет всем процессом моделирования, а также позволяет собирать статистику о состоянии сети. Этот класс является прямым потомком класса Планировщик (Event Scheduler).
В модели могут учитываться ситуации, приводящие к временным или постоянным изменениям сетевых топологий или их физических характеристик (выход из строя линии связи, выход из строя узла и т.п.). Моделируются также механизмы отслеживания зацикливаний пакетов.
По окончании моделирования сети, использующей исследуемый алгоритм, определяются следующие характеристики: пропускная способность, вероятностное распределение задержки пакетов, вероятностное распределение потери пакетов.
Для алгоритмов маршрутизации AntNet и OSPF получены экспериментальные зависимости мгновенных значений основных характеристик от времени моделирования.
Литература