Протоколы вектора расстояния

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

Достоинство этого элегантного алгоритма - быстрая реакция на хорошие новости (появление в сети нового маршрутизатора), а недостаток - очень медленная реакция на плохие известия (исчезновение одного из соседей).

Рассмотрим правильную работу протокола на примере:

Пусть маршрутизатор В временно отключен. То есть путь, отмеченный красным цветом, недоступен. Тогда у маршрутизатора А в таблице появится запись о пути к маршрутизатору D по зеленому пути. Этот путь имеет длину 3 (три пролета). При включении маршрутизатора В А получит от него таблицу, в которой указан путь до D длиной 1, посчитает длину пути от себя (2). А изменит запись в таблице маршрутизации на минимальный путь, то есть через В длиной 2.

В качестве примера распространения информации о включении и о выключении маршрутизатора мы рассмотрим сеть (см. Рисунок 1) из нескольких последовательно соединенных маршрутизаторов, где метрикой является число транзитных узлов на пути к точке назначения (как в протоколе RIP).

Рисунок 1. Распространение "хорошей" новости в сети.

Пусть в начальный момент времени маршрутизатор A не был доступен, т. е. расстояние до него во всех таблицах - бесконечность. При включении А пошлет сообщение своему соседу - узлу B. Все остальные маршрутизаторы узнают об этом через последовательный обмен сообщениями (для простоты будем считать, что обмен между всеми соседними узлами происходит синхронно каждые несколько секунд).

Во время первого обмена узел B узнает, что A заработал и вносит в свою таблицу маршрутизации "1" как расстояние до A; все остальные узлы в этот момент по-прежнему считают A недоступным. При следующем обмене, спустя несколько секунд, узел C также узнает о появлении маршрутизатора A. В результате последовательности таких обменов информация достигнет и узла E, для которого стоимость маршрута до А будет "4".

Таким образом, для сети с максимальной длиной маршрута N сообщение о новом маршрутизаторе дойдет до самого удаленного узла в сети через N-1 циклов обмена таблицами маршрутизации. На этом этапе никаких проблем не возникает.

Теперь мы рассмотрим обратный случай (см. Рисунок 2), когда узел А перестает работать вследствие сбоя. При очередном обмене (мы будем считать его первым в этой серии) узел В не получает никакого сообщения от молчащего маршрутизатора А. Это верный сигнал о том, что у А возникли проблемы, и информацию о нем необходимо удалить из таблицы. Однако в то же самое время узел C сообщает, что ему известен путь до А и стоимость этого пути "2". Тот факт, что путь до А, объявленный узлом C, проходит через сам B (т. е. образуется петля), ускользает от внимания маршрутизатора, и он заносит в таблицу путь до неработающего А стоимостью "3".

Рисунок 2. Проблема возрастания до бесконечности.

Во время следующего обмена C замечает, что оба его соседа рекламируют путь до A стоимостью "3", и немедленно делает поправки в своей таблице. Теперь длина пути от С до A - "4". Если этот процесс не остановить, то он может продолжаться до бесконечности, и никто так и не узнает, что маршрутизатор А давно вышел из строя. Соответственно данные к А будут посылаться и дальше.

Эта проблема алгоритма вектора расстояний получила название проблемы возрастания до бесконечности (count-to-infinity problem). Она является основной причиной задания ограничений на максимальную длину пути во всех протоколах вектора расстояния.

Протокол RIP, например, считает маршрут длиной более чем в 15 транзитных узлов бесконечным. Такой путь будет немедленно удален из таблицы маршрутизации. Т. е. в последнем примере узел B поймет, что узел А недоступен, когда получит объявление пути до А со стоимостью "15". К сожалению, такая процедура занимает слишком много времени. Кроме того, появилось ограничение на количество маршрутизаторов в одной так называемой "зоне".