Построение маршрута
В 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. И так далее. Таким образом, поиск, начавшийся в какой-то локальной области, все больше расширяет свой охват.
Обслуживание маршрута
Поскольку узлы могут перемещаться и выключаться, топология сети может изменяться совершенно спонтанно. Например, если на рис. 5.18 узел G выключится, А не поймет, что путь к I (ADGI) больше не может быть реализован. Алгоритму нужно как-то с этим бороться. Периодически все узлы рассылают сообщение приветствия Hello. Ожидается, что все узлы, будучи истинными джентльменами, ответят на него. Если ответ не приходит, значит, сосед вышел из зоны действия или вышел из строя и больше не связан с данным узлом. Аналогичным образом, если он пытается послать пакет соседу, который не отвечает, он узнает, что связь с ним недоступна.
Эта информация используется для удаления нерабочих путей. Для каждого из возможных адресатов каждый узел N хранит историю о том, какие активные соседи снабжали узел пакетами для данных адресатов в течение последних AT секунд.
Когда какой-либо из соседей узла N становится недоступным, узел N проверяет свою таблицу маршрутизации — ведь теперь нужно понять, к каким адресатам лежал путь через ушедший узел. Всем оставшимся активным соседям сообщается, что такие пути больше нельзя использовать и их следует удалить из таблиц маршрутизации. В нашем примере D удаляет из своей таблицы маршрутизации записи для G и I и сообщает об этом A, который в свою очередь удаляет I. В общем случае активные соседи передают эти новости своим активным соседям и т. д., пока все пути, зависевшие от ушедшего узла, не будут удалены из всех таблиц.
Теперь, когда неправильные маршруты удалены из сети, отправители могут вычислить новые действующие маршруты в соответствии с методом, описанным выше. Однако здесь есть одна сложность. Если вы помните, при изменении топологии сети протоколы векторов расстояний сталкиваются с проблемами медленной конвергенции и счета до бесконечности, в результате чего они могут перепутать старые неправильные маршруты и новые действующие маршруты.
Чтобы обеспечить быструю конвергенцию, маршрутам присваиваются порядковые номера, контролируемые получателем. Порядковый номер получателя — своего рода логические часы. Получатель увеличивает этот номер каждый раз при отправке нового пакета ROUTE REPLY. Чтобы запросить новый маршрут, отправитель добавляет в пакет ROUTE REQUEST порядковый номер получателя для последнего использовавшегося маршрута: это может быть или порядковый номер только что удаленного маршрута, или 0, то есть исходное значение. Запрос будет передаваться широковещательным способом до тех пор, пока не будет найден маршрут с большим порядковым номером. Промежуточные узлы сохраняют маршруты, имеющие больший порядковый номер или меньшее число промежуточных узлов для текущего порядкового номера.
Подобно тому, как это происходит в протоколе «по требованию», узлы хранят информацию только о тех маршрутах, которые используются в настоящий момент. Остальные маршруты хранятся лишь в течение определенного времени, после чего удаляются. Вычисление и хранение только действующих в настоящий момент маршрутов позволяет более эффективно использовать полосу пропускания и увеличивает время работы от элементов питания (в отличие от стандартного протокола векторов расстояний, который время от времени рассылает обновления).
