Введение
1 Обзор проблемы 6
1.1 Обзор протокола 6
1.2 Учет метрики в протоколе OSPF 9
1.3 Недостаток протокола OSPF 11
2 Модификация для решения проблемы 14
2.1 Решение при помощи муравьев 14
2.2 Идея мобильных агентов 17
2.3 Протокол AntNet 18
3 Моделирование 22
3.1 Обзор среды моделирования OMNeT++ 22
3.2 Моделирование протокола OSPF 26
3.2.1 Описание исходной модели 26
3.2.2 Эксперимент над исходной моделью 35
3.3 Моделирование протокола AntNet 38
3.3.1 Описание полученной модели 38
3.3.2 Эксперимент над полученной моделью 48
ЗАКЛЮЧЕНИЕ 52
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 53
Маршрутизацию можно описать как процесс передачи пакетов между соединенными сетями. В TCP/IP-сетях маршрутизация является частью протокола IP (Internet Protocol) и используется в сочетании с другими службами сетевых протоколов для обеспечения передачи данных между узлами, расположенными в разных сегментах более крупной TCP/IP-сети [2].
IP - это своего рода «почтовая система» стека TCP/IP, выполняющая сортировку и доставку IP-данных. Каждый входящий или исходящий пакет называется IP-датаграммой. Датаграмма IP содержит два IP-адреса, их трактовка: адрес источника (отправляющего узла) и адрес назначения (принимающего узла). В отличие от аппаратных адресов, IP-адреса в датаграмме в процессе передачи ее по TCP/IP-сети остаются постоянными [2].
Маршрутизация является основной функцией IP. Обмен IP-датаграммами и их обработка на каждом узле выполняются протоколом IP, работающим на межсетевом уровне [2].
Открытый протокол, базирующийся на алгоритме поиска наикратчайшего пути (Open Shortest Path Fisrt - OSPF) является протоколом маршрутизации, разработанным для сетей IP рабочей группой Internet Engineering Task Force (IETF), занимающейся разработкой протоколов для внутрисистемных роутеров (interior gateway protocol - IGP) [3].
OSPF имеет две основных характеристики. Первая из них - это то, что протокол является открытым, т.е. его спецификация является общественным достоянием. Второй его главной характеристикой является то, что он базируется на алгоритме SPF. Алгоритм SPF иногда называют алгоритмом «Дейкстра» по имени автора, который его разработал [3].
Являясь алгоритмом с объявлением состояния канала, OSPF отличается от RIP и IGRP, которые являются протоколами маршрутизации с вектором расстояния. Роутеры, использующие алгоритм вектора расстояния, отправляют всю или часть своей таблицы маршрутизации в сообщения о корректировке маршрутизации, но только своим соседям. А роутеры, использующие алгоритмы маршрутизации по состоянию канала требуют отправки сообщений во все роутеры, которые находятся в пределах одной и той же иерархической области. В объявления о состоянии канала протокол OSPF включает информацию о подключенных интерфейсах, об использованных показателях и о других переменных. По мере накопления роутерами OSPF информации о состоянии канала, они используют алгоритм SPF для расчета наикратчайшего пути к каждому узлу [3].
Протокол OSPF решает большинство проблем, связанных с маршрутизацией настолько эффективно, что его работа кажется идеальной. Но существует серьезная проблема, с которой OSPF не может справиться [4].
Протокол OSPF работает на основании алгоритма Дейкстры, т.е. строя маршрут от адреса отправки пакета до адреса доставки учитывается метрика каналов, в итоге получается самый короткий путь. Однако не исключено, что на одном из каналов, включенных в маршрут следования пакета, могут передаваться большие объемы данных. Это приведет к тому, что пакет, доставленный до этого загруженного канала, будет поставлен в хвост длинной очереди на передачу сначала на одном конце канала, а потом на другом. В сложившейся ситуации маршрут, имеющий большую метрику, но на котором отсутствует какая либо нагрузка (кроме передачи служебных сообщений, в случае с протоколом OSPF), мог бы оказаться более предпочтительным, но протокол OSPF не позволяют обнаружить этот факт.
Существующие алгоритмы оптимизации потоков с учетом перегрузок каналов достаточно сложны, поэтому поиски более простых и эффективных методов решения этой задачи ведутся до сих пор.
В качестве решения проблемы передачи трафика по загруженным каналам был рассмотрен протокол AntNet, основанный на роевом интеллекте. Этот протокол маршрутизации основывается на алгоритмах оптимизации трафика сети с помощью подражания муравьиному алгоритму.
В произвольные моменты времени роутер сети, настроенной с помощью AntNet, генерирует сообщения, которые отсылаются до определенного принимающего узла, но каждое сообщение следует по своему маршруту. С помощью такого алгоритма замеряется время следования сообщения на каждом маршруте, и затем путь с меньшим временем следования сменяет прежний маршрут и становится новым маршрутом по умолчанию до данного узла назначения.
В данной работы был рассмотрен протокол маршрутизации на основе роевого интеллекта - протокол AntNet. Данный протокол был промоделирован в среде моделирования OMNeT++. Основанием для моделирования послужила проблема, выявленная в результате моделирования протокола по состоянию канала связи - OSPF. Результаты показали, что OSPF неспособен эффективно решать проблему отслеживания загруженности каналов связи и производить последующую перестройку таблицы маршрутизации.
В процессе разработки AntNet был создан граф состояний протокола, кратко описывающий алгоритм работы протокола AntNet.
С помощью библиотеки INET Framework для OMNeT++ был реализован модуль, обеспечивающий работу протокола AntNet.
Моделирование нового протокола было выполнено на той же тестовой сети. На основании полученных результатов было увидено, что протокол AntNet в определенный момент времени отследил, что на используемом маршруте передачи данных время следования пакетов больше чем на другом маршруте. Таким образом, протокол отследил большую нагрузку на используемом канале, после чего таблица маршрутизации была перестроена, и данные стали передаваться по другому маршруту.
В процессе моделирования AntNet было увидено, что протокол может быть использован в исследованиях по повышению производительности сети при больших нагрузках за счет использования алгоритмов, с помощью которых замеряется время следования пакетов по сети и происходит перенаправление трафика по маршруту с меньшим показателем RTT.
В результате выполнения данной работы была рассмотрена работоспособность сети, использующей в качестве протокола маршрутизации протокол AntNet. Для достижения эффективности в работе протокола AntNet требуются дополнительные исследования.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
