ДИНАМИЧЕСКИЙ АЛГОРИТМ МАРШРУТИЗАЦИИ НА ОСНОВЕ АГЕНТНЫХ ТЕХНОЛОГИЙ
Cолдатова В.А.
Кафедра ПМИ ДонНТУ
_sunshine@mail.ru
Abstract
Soldatova V.A. Dynamic agent-based routing algorithm. This work deals with new approach to routing problems. AntNet is a distributed, agent-based routing algorithm which was inspired by recent work on the ant colony metaphor for solving optimization problems. AntNet's agents travel between network nodes to collect information about a network state. Communication between the agents is indirect and asynchronous. A routing simulator was developed to explore a behavior of algorithm AntNet. AntNet was compared with link-state algorithm OSPF. AntNet showed a better performance.
Введение
В настоящее время компьютерные сети продолжают расти и изменяться. Кроме глобальных сетей, существуют локальные, виртуальные, беспроводные и другие виды сетей. Все коммуникационные сети имеют сложную структуру, так как они часто содержат в себе подсети и/или являются частью другой, более большой сети. Для обеспечения качественного обслуживания в сетях необходим механизм, позволяющий быстро и без потерь доставлять данные от одного пользователя к другому. Центральное место в этом механизме отводится маршрутизации. Правильно организованная маршрутизация в совокупности с компонентами управления доступом, потоками и перегрузкой полностью гарантирует качественное обслуживание сети. Однако проведенные исследования свидетельствуют о снижении производительности сетей [1]. В большинстве случаев, производительность падает не из-за поступающего трафика, а из-за маршрутизаторов, не справляющихся с поддержанием таблиц маршрутизации и выбором оптимальных маршрутов для данного класса трафика. Для решения возникшей проблемы следует или модернизировать уже существующие алгоритмы маршрутизации, или найти новые подходы к задаче маршрутизации. Одним из таких подходов является применение к задаче маршрутизации муравьиных алгоритмов [2-5].
1 Муравьиные алгоритмы
Муравьиные алгоритмы или Ant Colony Optimization (ACO) получили свое
распространение в последние два десятилетия. ACO активно используются исследователями для решения оптимизационных задач
(задача о коммивояжере, раскраска графов, нахождение кратчайших путей и др.). Данный тип алгоритмов основывается на поведении
социальных насекомых в природе. К социальным насекомым относятся все виды муравьев, термитов, некоторые виды пчел и ос. Поведение
всех перечисленных насекомых основано на роевом интеллекте (Swarm Intelligence). В поведении социальных насекомых различают два
вида взаимодействия между особями:
2 Обзор существующих работ
AntNet - это адаптивный, распределенный, базирующийся на агентах алгоритм маршрутизации. Впервые этот алгоритм был описан Джанни Ди Каро (Gianni Di Caro) и Марко Дориго (Marco Dorigo) в 1998 году в работе [2]. Однако создание AntNet не было первой попыткой использования муравьиных алгоритмов к задаче маршрутизации. Шондерверд (Schoonderwoerd) и другие в 1996-1997 гг. [3,4] рассмотрели маршрутизацию как возможную область применения муравьиных алгоритмов. Их подход к управлению сетью с помощью муравьев (ABC - ant-based control) используется при маршрутизации данных в телефонных сетях и во многом отличается от алгоритма AntNet. Кроме того, в 1997 году Субраманиан (Subramanian), Друшель (Druschel) и Чен (Chen) предложили свой алгоритм [5], базирующий на поведении колонии муравьев в природе. Данный алгоритм был применен к сетям с коммутацией пакетов и являлся расширением ABC-алгоритма, предложенного Шондервердом.
3 Применение поведения муравьев в природе к задаче маршрутизации
Процедура поиска кратчайших путей с помощью алгоритма маршрутизации данных AntNet состоит в следующем. Представим компьютерную сеть как окрестность, в которой взаимодействуют муравьи, при этом узлы этой сети будут являться источниками пищи для муравьев. Узлы соединены линиями связи, на которых муравьи могут отставлять след феромона. Каждый узел в сети характеризуется двумя структурами данных: локальной моделью трафика и вероятностной таблицей маршрутизации. Муравьев в такой сети будем называть мобильными агентами. Каждый мобильный агент движется от одного узла сети к другому (от муравейника к источнику пищи), при этом собирая информацию о линиях связи, соединяющих эти узлы. Чтобы распространить собранную информацию по сети, агент должен вернуться в узел, отправивший его. Для этого у каждого агента существует память, организованная в виде стека, в которую записан весь маршрут движения агента от узла-источника в узел-приемник. При выборе пути движения от узла-источника в узел-приемник через промежуточные узлы агенты используют вероятностное правило выбора пути. Вероятность выбора пути прямо пропорциональна количеству феромонов на этом пути. То есть, линии связи, содержащие большее количество феромонов, являются наиболее удобными маршрутами для пересылки пакетов в сети. В результате своего движения агенты должны собрать информацию о состоянии трафика и обновить главные структуры данных узла.
4 Результаты исследования
Для исследования алгоритма AntNet разработана программная модель. Получены графики зависимости основных характеристик маршрутизации (пропускной способности и потери пакетов) от времени моделирования. Для проверки значимости результатов моделирования был реализован алгоритм маршрутизации OSPF [1,2], активно использующийся при маршрутизации данных в реальных компьютерных сетях. Моделирование алгоритмов проводилось на сети, состоящей из восьми узлов, пропускная способность линий связи которой составляет 1 Мбит/сек (см. рис. 1). Для создания рабочей нагрузки, между всеми парами узлов сети открываются сессии передачи пакетов данных. Каждая сессия имеет скорость передачи (bit rate) 105 байт/сек. Длина пакетов данных, которыми обмениваются узлы, составляет 512 байт.
Рисунок 1 - Компьютерная сеть, на которой проводилось моделирование поведения алгоритмов AntNet и OSPF
Моделирование поведения алгоритмов длилось 300 виртуальных секунд. На 100-й секунде моделирования происходит резкое изменение скорости передачи данных в сессии между 1-м и 6-м узлами с 105 байт/сек на 1.4*106 байт/сек, то есть 1-й узел сети выступает в роли хот-спота [2]. Выключение хот-спота происходит на 200-ой секунде моделирования.
Для алгоритмов AntNet и OSPF получены графики для пропускной способности сети между 1-м и 6-м узлами и общей потери пакетов в сети.
Рисунок 2 - Пропускная способность (байт/сек) для алгоритмов AntNet (а) и OSPF (б)
Рисунок 3 - Потеря пакетов для алгоритмов AntNet (а) и OSPF(б)
Из рисунков 2 и 3 видно, что до включения хот-спота в узле под номером 1 пропускная способность между 1-м и 6-м узлами для обоих алгоритмов одинакова и составляет 100000 байт/сек. При включении хот-спота пропускная способность и уровень потери пакетов резко возрастают. Для алгоритма OSPF эти характеристики со временем стабилизируются (перестают изменяться), вплоть до момента выключения хот-спота. Алгоритм AntNet, напротив, все время пытается изменить маршрутные таблицы для оптимизации работы сети. Вследствие чего пропускная способность для AntNet постоянно растет, а уровень потери пакетов - снижается.
Планируется также сравнение алгоритма AntNet с другими современными алгоритмами маршрутизации (SPF, BF, Q-R, PQ-R и Daemon) [1,2,6].
Заключение
Маршрутизация играет важную роль в обслуживании коммуникационных сетей. При правильно организованной маршрутизации возможно оптимизировать такие важные показатели производительности сети как пропускная способность и задержка пакетов.
Новым подходом к задаче маршрутизации является алгоритм AntNet. Этот алгоритм базируется на так называемом роевом интеллекте, в частности на поведении социальных насекомых - муравьев.
Полученные результаты свидетельствуют о целесообразности дальнейшего изучения поведения алгоритма AntNet. Это позволит использовать полученные закономерности для эффективного внедрения этого алгоритма в реальные компьютерные сети.
Литература