AODV

AODV (англ. Ad hoc On-Demand Distance Vector ) — протокол динамической маршрутизации для мобильных ad-hoc сетей (MANET) и других беспроводных сетей. Разработан совместно в исследовательском центре Nokia университета Калифорнии, Санта-Барбары и университете Цинциннати Ч. Перкинсом, Э. Белдинг и С. Дасом[1]. AODV пригоден для маршрутизации как unicast, так и multicast пакетов. Является реактивным протоколом маршрутизации, то есть устанавливает маршрут до адресата по требованию. В отличие от классических протоколов маршрутизации Интернета являющихся превентивными, то есть находящих пути маршрутизации независимо от использования маршрутов. Как следует из названия, для вычисления маршрутов используется дистанционно-векторный алгоритм маршрутизации. В AODV с помощью применения порядковых номеров при обновлениях маршрута исключена возможность возникновения проблемы «счета до бесконечности», присущая другим протоколам, использующим этот алгоритм маршрутизации. Эта методика, ранее реализована в протоколе DSDV. На базе AODV и DSR ведётся разработка протокола DYMO[2].

Поля сообщения RREQ (запроса создания маршрута)

[править | править код]

Поля сообщения RREQ:

  • Тип (8 бит) — «1»
  • Флаг «J» — устанавливается, если RREQ передаётся широковещательно
  • Флаг «R» — устанавливается при восстановлении маршрута
  • Флаг «G» — устанавливается в том случае, если необходимо установить не только маршрут до узла-получателя, но и обратный маршрут от узла-получателя до узла-инициатора.
  • Флаг «D» — устанавливается, если необходимо доставить сообщение RREQ непосредственно до узла-получателя.
  • Флаг «U» — устанавливается в том случае, если порядковый номер узла-получателя неизвестен
  • 11 бит зарезервировано
  • Hop Count (Количество переходов) — 8 бит
  • RREQ ID (идентификационный номер сообщения RREQ)
  • IP-адрес узла-получателя (Destination IP Address)
  • Порядковый номер узла-получателя (Destination Sequence Number)
  • IP-адрес узла-инициатора (Originator IP Address)
  • Порядковый номер узла-инициатора (Originator Sequence Number)

Принципы работы

[править | править код]

В AODV передача маршрутной информации (кроме сообщений Hello) не ведётся, пока нет необходимости в установке или восстановлении маршрута. Когда один из узлов пытается отправить данные в сеть, посылается пакет с запросом на установку маршрута RREQ. Другие узлы сети с AODV пересылают этот пакет в общую среду и делают запись об узле, от которого они приняли запрос, создавая массовую отправку временных маршрутов к запрашивающему узлу. Когда узел получает запрос RREQ и уже имеет маршрут к узлу назначения, то в зависимости от флага «D» сообщения RREQ, он посылает назад сообщение RREP через временный маршрут к узлу требования (узлу-инициатору маршрута) или направляет сообщение RREQ к узлу-получателю, который отправляет сообщение RREP назад узлу-отправителю. Запрашивающий узел в таком случае использует маршрут с наименьшим количеством промежуточных узлов. Неиспользуемые записи в таблицах маршрутизации через некоторое время стираются. Если связь недостаточно надёжная, то предусмотрена возможность дополнительного подтверждения установки маршрута — отправление от узла-инициатора узлу-получателю сообщения RREP-ACK, подтверждающего получение сообщения RREP.

Когда маршрут по каким-либо причинам разрушается, передаётся сообщение об ошибке к передающему узлу и процесс создания маршрута повторяется.

Наибольшая сложность, возникшая при реализации протокола, связана с необходимостью понизить количество сообщений, чтобы не использовать полностью пропускную способность сети. Например, у каждого запроса о маршруте есть порядковый номер. Узлы выбирают этот номер так, чтобы он не повторял номера уже обработанных запросов. Другим методом ограничения распространения паразитного трафика является использование времени жизни, которое ограничивает максимальное количество транзитных узлов. Кроме того, если запрос маршрута по каким-либо причинам не привёл к установке маршрута, другой запрос нельзя послать, пока не проходит вдвое больше времени, потраченного на предыдущий запрос.

Преимущество AODV состоит в том, что он не создаёт дополнительного трафика при передаче данных по установленному маршруту. Кроме того, алгоритм векторной маршрутизации довольно прост и не требует больших объёмов памяти и машинного времени. Однако в AODV в начале коммутации требуется больше времени на установку маршрута, чем во многих других протоколах.

Примечания

[править | править код]
  1. RFC 3561: Ad hoc On-Demand Distance Vector (AODV) Routing
  2. Архивированная копия. Дата обращения: 5 июня 2011. Архивировано 13 июля 2011 года.