Эндрю Уэзеролл - Компьютерные сети. 5-е издание

Построение маршрута

В AODV маршруты к адресу назначения вычисляются «по требованию», то есть только тогда, когда кто-то хочет отправить пакет на этот адрес. Это позволяет избежать выполнения лишней работы: если топология сети изменится, а маршрут еще не использовался, маршрут не придется вычислять дважды. Топология произвольной сети в любой момент может быть описана с помощью графа соединенных друг с другом узлов. Два узла считаются соединенными (то есть между ними проведена дуга), если они могут связываться напрямую посредством радио. Для наших целей вполне подойдет простая, но адекватная модель, в которой каждый узел может связаться со всеми узлами, находящимися в пределах его зоны охвата. На практике сети устроены более сложным образом: соединению могут препятствовать здания, холмы и т. д.; в сети также возможны ситуации, когда узел А соединен с В, но В не соединен с А, поскольку у одного из них может быть более мощный передатчик, чем у другого. Однако для простоты мы будем считать, что все соединения симметричны.

Для описания алгоритма рассмотрим недавно сформированную произвольную сеть, изображенную на рис. 5.18. Предположим, что процессу, запущенному на узле А, необходимо отправить пакет на узел I. Алгоритм AODV на каждом узле ведет таблицу векторов расстояния, доступ к которой осуществляется с помощью поля адреса. Таблица содержит информацию об адресате, в том числе адрес ближайшего соседа, которому необходимо переслать пакет, чтобы он мог достичь пункта назначения. Сначала А просматривает эту таблицу и не находит записи для I. Значит, нужно найти маршрут, ведущий к этому узлу. Итак, алгоритм начинает заниматься поисками маршрутов только тогда, когда они реально требуются. Это и делает его алгоритмом «по требованию».

Рис. 5.18. Произвольная сеть: а — зона широковещания А; б — состояние после получения его узлами В и D; в — состояние после получения его узлами C, F и G; г — состояние после получения его узлами E, H и I. Затененными кружочками обозначены новые получатели. Пунктиром показаны возможные обратные маршруты. Сплошными линиями показан построенный маршрут

Для поиска I узел А генерирует пакет запроса маршрутаROUTE REQUEST и распространяет его по сети методом заливки (см. раздел 5.2.3). На рис. 5.18, а показано, что этот пакет достигает узлов B и D. Далее каждый узел повторно передает запрос, который в результате достигает узлов F , G и C (рис. 5.18, в ) и узлов H, E и I (рис. 5.18, г ). Чтобы избавиться от лишних копий пакета при заливке, используется порядковый номер. Так, например, D не принимает передачу от B (рис. 5.18, в), так как он уже передал запрос. Наконец запрос достигает узла I, который создает пакетROUTE REPLY . Этот пакет пересылается отправителю по тому же пути, по которому он пришел. Чтобы это было возможно, каждый узел должен помнить, какой узел передал ему запрос. Информация об обратном маршруте, хранящаяся в памяти узлов, показана на рис. 5.18, б-г стрелками. При передаче запроса каждый узел также увеличивает значение счетчика транзитных участков. Это позволяет понять, насколько далеко от адреса назначения расположен узел. Ответы сообщают каждому отдельному узлу, какому из соседей следует передавать пакет, предназначенный для данного адреса: тому узлу, от которого пришел ответ. Во время обработки ответа узлы G и D записывают сведения о наилучшем маршруте в таблицы маршрутизации. Когда ответ достигает узла A , появляется новый маршрут — ADGI .

В больших сетях алгоритмом генерируется много широковещательных пакетов даже для адресатов, расположенных достаточно близко друг к другу. Чтобы уменьшить издержки, область широковещания может быть ограничена полем Время жизни ( Time to live ) IP-пакета. Это поле устанавливается отправителем и декрементируется при каждой пересылке. Когда его значение становится равным 0, пакет отвергается, а не распространяется дальше. При этом процесс поиска пути немного изменяется. Для обнаружения адресата отправитель рассылает пакет запроса маршрута со Временем жизни , равным 1. Если в течение разумного времени ответ не приходит, посылается еще один запрос со Временем жизни , равным 2. И так далее. Таким образом, поиск, начавшийся в какой-то локальной области, все больше расширяет свой охват.