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

Обслуживание маршрута

Поскольку узлы могут перемещаться и выключаться, топология сети может изменяться совершенно спонтанно. Например, если на рис. 5.18 узел G выключится, А не поймет, что путь к I (ADGI ) больше не может быть реализован. Алгоритму нужно как-то с этим бороться. Периодически все узлы рассылают сообщение приветствия Hello . Ожидается, что все узлы, будучи истинными джентльменами, ответят на него. Если ответ не приходит, значит, сосед вышел из зоны действия или вышел из строя и больше не связан с данным узлом. Аналогичным образом, если он пытается послать пакет соседу, который не отвечает, он узнает, что связь с ним недоступна.

Эта информация используется для удаления нерабочих путей. Для каждого из возможных адресатов каждый узел N хранит историю о том, какие активные соседи снабжали узел пакетами для данных адресатов в течение последних AT секунд.

Когда какой-либо из соседей узла N становится недоступным, узел N проверяет свою таблицу маршрутизации — ведь теперь нужно понять, к каким адресатам лежал путь через ушедший узел. Всем оставшимся активным соседям сообщается, что такие пути больше нельзя использовать и их следует удалить из таблиц маршрутизации. В нашем примере D удаляет из своей таблицы маршрутизации записи для G и I и сообщает об этом A, который в свою очередь удаляет I. В общем случае активные соседи передают эти новости своим активным соседям и т. д., пока все пути, зависевшие от ушедшего узла, не будут удалены из всех таблиц.

Теперь, когда неправильные маршруты удалены из сети, отправители могут вычислить новые действующие маршруты в соответствии с методом, описанным выше. Однако здесь есть одна сложность. Если вы помните, при изменении топологии сети протоколы векторов расстояний сталкиваются с проблемами медленной конвергенции и счета до бесконечности, в результате чего они могут перепутать старые неправильные маршруты и новые действующие маршруты.

Чтобы обеспечить быструю конвергенцию, маршрутам присваиваются порядковые номера, контролируемые получателем. Порядковый номер получателя — своего рода логические часы. Получатель увеличивает этот номер каждый раз при отправке нового пакетаROUTE REPLY . Чтобы запросить новый маршрут, отправитель добавляет в пакетROUTE REQUEST порядковый номер получателя для последнего использовавшегося маршрута: это может быть или порядковый номер только что удаленного маршрута, или 0, то есть исходное значение. Запрос будет передаваться широковещательным способом до тех пор, пока не будет найден маршрут с большим порядковым номером. Промежуточные узлы сохраняют маршруты, имеющие больший порядковый номер или меньшее число промежуточных узлов для текущего порядкового номера.

Подобно тому, как это происходит в протоколе «по требованию», узлы хранят информацию только о тех маршрутах, которые используются в настоящий момент. Остальные маршруты хранятся лишь в течение определенного времени, после чего удаляются. Вычисление и хранение только действующих в настоящий момент маршрутов позволяет более эффективно использовать полосу пропускания и увеличивает время работы от элементов питания (в отличие от стандартного протокола векторов расстояний, который время от времени рассылает обновления).

Пока мы рассмотрели только один маршрут: от A до I. Для большей экономии ресурсов построение и обслуживание пересекающихся маршрутов производится совместно. К примеру, если B тоже захочет отправлять пакеты в I, он выполнит вычисление маршрута. Но в таком случае запрос сначала достигнет узла D, который уже знает о существовании маршрута, ведущего к I. И тогда узел D может отправить B ответ, содержащий нужный маршрут, тем самым избежав лишних вычислений.

Существует множество других схем маршрутизации в произвольных сетях. Еще один известный алгоритм «по требованию» называется DSR (Dynamic Source Routing — динамическая маршрутизация от источника) ( Johnson и др., 2001). Другая стратегия, основанная на географии, используется в GPSR (Greedy Perimeter Stateless Routing — «жадный» протокол маршрутизации по периметру без учета состояний). Если все узлы знают свое географическое местоположение, доставка пакета получателю может происходить без вычисления маршрута: пакет можно каждый раз отправлять в правильном направлении, возвращаясь назад в случае, если иначе путь приведет в тупик. Выбор протокола зависит в первую очередь от характеристик данной произвольной сети.