Помощь студентам в учебе
Разработка протокола маршрутизации на основе алгоритма роевого интеллекта
|
ВВЕДЕНИЕ 3
1 Роевой интеллект 6
2 Ant алгоритм 12
2.1 Описание 12
2.1.1 Решение при помощи алгоритма роевого интеллекта 12
2.1.2 Идея мобильных агентов 17
2.2 Протокол 18
2.3 Граф работы протокола 21
3 Реализация AntNet 23
3.1 Обзор среды OMNeT++ 23
3.2 OMNeT++ модель 24
3.3 Алгоритм протокола 27
3.3.1 Алгоритм работы протокола AntNet 27
3.3.2 Инициализация сети 28
3.3.3 Поддержание оптимальных маршрутов 32
3.3.4 Обработка сбоев 36
3.4 Структуры пакетов 39
4 Моделирование 42
4.1 Результаты эксперимента 42
ЗАКЛЮЧЕНИЕ 46
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1 Роевой интеллект 6
2 Ant алгоритм 12
2.1 Описание 12
2.1.1 Решение при помощи алгоритма роевого интеллекта 12
2.1.2 Идея мобильных агентов 17
2.2 Протокол 18
2.3 Граф работы протокола 21
3 Реализация AntNet 23
3.1 Обзор среды OMNeT++ 23
3.2 OMNeT++ модель 24
3.3 Алгоритм протокола 27
3.3.1 Алгоритм работы протокола AntNet 27
3.3.2 Инициализация сети 28
3.3.3 Поддержание оптимальных маршрутов 32
3.3.4 Обработка сбоев 36
3.4 Структуры пакетов 39
4 Моделирование 42
4.1 Результаты эксперимента 42
ЗАКЛЮЧЕНИЕ 46
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Маршрутизация - это процесс определения на основе данных из таблицы маршрутизации оптимального пути от узла-источника к узлу-получателю в условиях избыточных связей.
В процессе построения маршрутизации выделяют две части: определение дальнейшего пути пакета и непосредственно его пересылка по этому путь.
В соответствии с этими частями, процесс маршрутизации можно разделить на два иерархически связанных уровня:
- уровень маршрутизации. На этом уровне происходит работа с таблицей маршрутизации. Таблица маршрутизации служит для определения сетевого адреса следующего маршрутизатора, на который будет передан пакет, или непосредственно получателя пакета. После определения адреса передачи выбирается определенный выходной физический порт маршрутизатора для передачи сетевого пакета. Этот процесс называется определением маршрута перемещения пакета. Настройка таблицы маршрутизации ведется протоколами маршрутизации. На этом же уровне определяется перечень необходимых предоставляемых сервисов;
- уровень передачи пакетов. Перед тем как передать пакет, необходимо проверить контрольную сумму заголовка пакета, определить адрес (канального уровня) получателя пакета и произвести непосредственно отправку пакета с учетом очередности, фрагментации, фильтрации и прочих действий. Эти действия выполняются на основании команд, поступающих с уровня маршрутизации.
Маршрутизация является одной из наиболее важных процедур передачи данных. Процедура маршрутизации гарантирует, что данные перемещаются из одной сети в другую с оптимальной скоростью и минимальной задержкой. Целостность передаваемых данных в процессе построения маршрутизации гарантирована.
Алгоритм маршрутизации - часть программного обеспечения сетевого уровня, и отвечает за определение по какой линии отправлять пакет дальше. В независимости от того выбирается ли маршрут для сессии или для каждого пакета алгоритм маршрутизации должен обладать рядом свойств: корректностью, простотой, устойчивостью, стабильностью, справедливостью и оптимальностью.
Не адаптивные алгоритмы не принимают в расчет текущую загрузку сети и состояние топологии. Все возможные маршруты вычисляются заранее и загружаются в маршрутизаторы при загрузке сети. Такая маршрутизация называется статической маршрутизацией.
Адаптивные алгоритмы маршрутизации, наоборот, определяют маршрут исходя из текущей загрузки сети и топологии. Адаптивные алгоритмы различаются тем, где и как они получают информацию (локально от соседних маршрутизаторов или глобально ото всех), когда они меняют маршрут ( каждые АТ секунд, когда меняется нагрузка, когда меняется топология), какая метрика используется при оптимизации (расстояние, число скачков, ожидаемое время передачи).
Маршрутизация по вектору расстояния - это алгоритм маршрутизации, идея которого в том, что у каждого маршрутизатора в подсети есть таблица расстояний до каждого маршрутизатора в подсети. Периодически маршрутизатор обменивается информацией со своими соседями и обновляет информацию в таблице. Каждый элемент таблицы состоит из двух полей: первое - номер линии, по которой надо отправлять пакеты, чтобы достичь нужного места, второе - величина задержки до места назначения. Эта величина задержки может быть измерена в разных единицах: скачках, миллисекундах, длине очереди на линии и т.д.
Алгоритм AntNet является адаптивным алгоритмом маршрутизации, метод поиска путей которого основан на поведении муравьев в природе. В нем предусмотрено исследование состояния сети с использованием агентов (муравьев), которые в классическом представлении данного алгоритма, используют вероятностные правила выбора маршрутов. Для маршрутизации пакетов данных используются вероятностные таблицы маршрутизации.
Процедура поиска кратчайших путей в алгоритме AntNet использует те же принципы, что и колония муравьев при поиске пищи . Муравей на своем пути оставляет след из активных веществ - феромонов. Феромоновый след во внешней среде существует некоторое время, и муравьи, которые будут идти следом, с больше вероятностью предпочтут то направление, по которому до них прошли другие муравьи. Эта вероятность будет тем больше, чем большее количество муравьев прошло по этому пути. Таким образом, через некоторое время большая часть муравьев будет использовать один, наиболее близкий к оптимальному, маршрут.
Роль муравьев в протоколе AntNet выполняют активные агенты. Активный агент в протоколе AntNet - это специальный пакет, который несет с собой статистику о состоянии пройденных сетевых каналов.
В произвольные моменты времени роутер сети, настроенной с помощью AntNet, генерирует сообщения, которые отсылаются до определенного принимающего узла, но каждое сообщение следует по своему маршруту. С помощью такого алгоритма замеряется время следования сообщения на каждом маршруте, и затем путь с меньшим временем следования сменяет прежний маршрут и становится новым маршрутом по умолчанию до данного узла назначения.
В процессе построения маршрутизации выделяют две части: определение дальнейшего пути пакета и непосредственно его пересылка по этому путь.
В соответствии с этими частями, процесс маршрутизации можно разделить на два иерархически связанных уровня:
- уровень маршрутизации. На этом уровне происходит работа с таблицей маршрутизации. Таблица маршрутизации служит для определения сетевого адреса следующего маршрутизатора, на который будет передан пакет, или непосредственно получателя пакета. После определения адреса передачи выбирается определенный выходной физический порт маршрутизатора для передачи сетевого пакета. Этот процесс называется определением маршрута перемещения пакета. Настройка таблицы маршрутизации ведется протоколами маршрутизации. На этом же уровне определяется перечень необходимых предоставляемых сервисов;
- уровень передачи пакетов. Перед тем как передать пакет, необходимо проверить контрольную сумму заголовка пакета, определить адрес (канального уровня) получателя пакета и произвести непосредственно отправку пакета с учетом очередности, фрагментации, фильтрации и прочих действий. Эти действия выполняются на основании команд, поступающих с уровня маршрутизации.
Маршрутизация является одной из наиболее важных процедур передачи данных. Процедура маршрутизации гарантирует, что данные перемещаются из одной сети в другую с оптимальной скоростью и минимальной задержкой. Целостность передаваемых данных в процессе построения маршрутизации гарантирована.
Алгоритм маршрутизации - часть программного обеспечения сетевого уровня, и отвечает за определение по какой линии отправлять пакет дальше. В независимости от того выбирается ли маршрут для сессии или для каждого пакета алгоритм маршрутизации должен обладать рядом свойств: корректностью, простотой, устойчивостью, стабильностью, справедливостью и оптимальностью.
Не адаптивные алгоритмы не принимают в расчет текущую загрузку сети и состояние топологии. Все возможные маршруты вычисляются заранее и загружаются в маршрутизаторы при загрузке сети. Такая маршрутизация называется статической маршрутизацией.
Адаптивные алгоритмы маршрутизации, наоборот, определяют маршрут исходя из текущей загрузки сети и топологии. Адаптивные алгоритмы различаются тем, где и как они получают информацию (локально от соседних маршрутизаторов или глобально ото всех), когда они меняют маршрут ( каждые АТ секунд, когда меняется нагрузка, когда меняется топология), какая метрика используется при оптимизации (расстояние, число скачков, ожидаемое время передачи).
Маршрутизация по вектору расстояния - это алгоритм маршрутизации, идея которого в том, что у каждого маршрутизатора в подсети есть таблица расстояний до каждого маршрутизатора в подсети. Периодически маршрутизатор обменивается информацией со своими соседями и обновляет информацию в таблице. Каждый элемент таблицы состоит из двух полей: первое - номер линии, по которой надо отправлять пакеты, чтобы достичь нужного места, второе - величина задержки до места назначения. Эта величина задержки может быть измерена в разных единицах: скачках, миллисекундах, длине очереди на линии и т.д.
Алгоритм AntNet является адаптивным алгоритмом маршрутизации, метод поиска путей которого основан на поведении муравьев в природе. В нем предусмотрено исследование состояния сети с использованием агентов (муравьев), которые в классическом представлении данного алгоритма, используют вероятностные правила выбора маршрутов. Для маршрутизации пакетов данных используются вероятностные таблицы маршрутизации.
Процедура поиска кратчайших путей в алгоритме AntNet использует те же принципы, что и колония муравьев при поиске пищи . Муравей на своем пути оставляет след из активных веществ - феромонов. Феромоновый след во внешней среде существует некоторое время, и муравьи, которые будут идти следом, с больше вероятностью предпочтут то направление, по которому до них прошли другие муравьи. Эта вероятность будет тем больше, чем большее количество муравьев прошло по этому пути. Таким образом, через некоторое время большая часть муравьев будет использовать один, наиболее близкий к оптимальному, маршрут.
Роль муравьев в протоколе AntNet выполняют активные агенты. Активный агент в протоколе AntNet - это специальный пакет, который несет с собой статистику о состоянии пройденных сетевых каналов.
В произвольные моменты времени роутер сети, настроенной с помощью AntNet, генерирует сообщения, которые отсылаются до определенного принимающего узла, но каждое сообщение следует по своему маршруту. С помощью такого алгоритма замеряется время следования сообщения на каждом маршруте, и затем путь с меньшим временем следования сменяет прежний маршрут и становится новым маршрутом по умолчанию до данного узла назначения.
В данной работе был разработан протокол маршрутизации на основе алгоритма роевого интеллекта - протокол AntNet. Для данного протокола был сформулирован алгоритм работы протокола. На основе алгоритма работы был сформирован граф работы протокола. Описаны структуры пакетов. Данный протокол был промоделирован в среде моделирования OMNeT++. Основанием разработки данного протокола послужила проблема того, что современные протоколы маршрутизации неспособны эффективно решать проблему отслеживания загруженности каналов связи и производить последующую перестройку таблицы маршрутизации.
С помощью библиотеки INET Framework для OMNeT++ был реализован модуль, обеспечивающий работу протокола AntNet.
Моделирование протокола роевого интеллекта было выполнено на разработанной для этого тестовой сети. На основании полученных результатов были сделаны выводы, что протокол AntNet в определенный момент времени отследил, что на используемом маршруте передачи данных время следования пакетов больше чем на другом маршруте. Таким образом, протокол отследил использование неоптимального маршрута передачи данных. После чего таблица маршрутизации была перестроена, и данные стали передаваться по другому маршруту.
В процессе моделирования AntNet были сделаны выводы, что протокол может быть использован в исследованиях по повышению производительности сети при больших нагрузках за счет использования алгоритмов, с помощью которых замеряется время следования пакетов по сети и происходит перенаправление трафика по маршруту с меньшим показателем RTT.
В результате выполнения данной работы был разработан протокол маршрутизации на основе алгоритма роевого интеллекта. Для достижения эффективности в работе протокола AntNet требуются дополнительные исследования.
С помощью библиотеки INET Framework для OMNeT++ был реализован модуль, обеспечивающий работу протокола AntNet.
Моделирование протокола роевого интеллекта было выполнено на разработанной для этого тестовой сети. На основании полученных результатов были сделаны выводы, что протокол AntNet в определенный момент времени отследил, что на используемом маршруте передачи данных время следования пакетов больше чем на другом маршруте. Таким образом, протокол отследил использование неоптимального маршрута передачи данных. После чего таблица маршрутизации была перестроена, и данные стали передаваться по другому маршруту.
В процессе моделирования AntNet были сделаны выводы, что протокол может быть использован в исследованиях по повышению производительности сети при больших нагрузках за счет использования алгоритмов, с помощью которых замеряется время следования пакетов по сети и происходит перенаправление трафика по маршруту с меньшим показателем RTT.
В результате выполнения данной работы был разработан протокол маршрутизации на основе алгоритма роевого интеллекта. Для достижения эффективности в работе протокола AntNet требуются дополнительные исследования.