Алгоритм поиска кратчайшего пути

Если какая-либо сеть становится недостижимой, все соседние маршрутизаторы установят метрику для этой сети равной 16. В следующем цикле посылки сообщений об обновлении маршрутизаторы будут передавать этот маршрут каждому из своих соседей с числом переходов, равным 16. Маршрутизаторы, расположенные на расстоянии одного перехода от маршрутизаторов, соседних с вышедшим из строя устройством, будут иметь количество переходов, равное 17. Любые записи в таблице маршрутизации, имеющие число переходов более 16, уменьшат это число до 16. В таблицах маршрутизации всех маршрутизаторов в сети количество переходов в недостижимую сеть будет сводиться к значению 16.

Сходимость — это состояние, в котором все маршрутизаторы используют одинаковое понимание маршрутизаторами текущей сетевой топологии. Сходимость в сети нарушается только временно, когда выходит из строя либо маршрутизатор, либо канал связи. Если сходимость нарушена, необходимо определенное время, после прохождения, которого все маршрутизаторы в сети обменяются информацией для восстановления сходимости в новой сетевой топологии.

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

Существует несколько технологий, с помощью которых протокол RIP IP может повысить производительность в динамических средах и которые могут помочь в повышении скорости сходимости. К ним относятся:

• Расщепление горизонта (Split — Horizon);
• Обратное исправление (Poison Reverse);
• Мгновенное изменение (Triggered Update);
• Временный отказ от приема информации (Hold -    Down 
  и Garbage — Collection).

Рис. 2.4.1 показывает логическую петлю, образованную между двумя маршрутизаторами.

Маршрутизатор М2 может достигнуть целевой сети через маршрутизатор Ml с количеством переходов, равным 1. Маршрутизатор МЗ получает эту информацию из периодических сообщений об обновлении от маршрутизатора М2, который говорит, что МЗ может

Рис. 2.4.1. Пример образования петель маршрутизации

достигнуть целевую сеть, используя маршрутизатор М2 с количеством переходов, равным 2. В следующем цикле посылки сообщений об обновлении маршрутизатор МЗ известит маршрутизатор М2 о его достижимости целевой сети с количеством переходов, равным 3. В результате маршрутизатор М2 будет иметь два маршрута в целевую сеть: первый маршрут с использованием маршрутизатора Ml и количеством переходов, равным 1, и второй -- с использованием маршрутизатора МЗ с количеством переходов, равным 3. Маршрутизатор М2 выберет маршрут с использованием маршрутизатора Ml, так как он имеет наименьшую метрику.

В случае если канал связи между маршрутизаторами Ml и М2 выйдет из строя, М2 не получит сообщение об обновлении в требуемый интервал времени и удалит из своей таблицы запись с маршрутом в целевую сеть, использующим маршрутизатор Ml. Однако маршрутизатор М2 имеет альтернативный маршрут в целевую сеть с использованием маршрутизатора МЗ и с количеством переходов, равным 3. Следовательно, МЗ будет передавать весь трафик обратно маршрутизатору М2, что вызовет создание петли маршрутизации. Обмен пакетами между маршрутизаторами будет продолжаться до тех пор, пока поле TTL в заголовке IP-дейтаграммы не достигнет нуля, и она не будет удалена одним из маршрутизаторов.

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

На рис. 2.4.2 показано, каким образом технология Split — Horizon будет устранять образовавшуюся ранее петлю.

Рис. 2.4.2. Пример использования технологии расщепления горизонта

Процедура обмена сообщениями об обновлении маршрутной информации между маршрутизаторами остается такой же, как и на рис. 2.4.1, за исключением того, что маршрутизатор МЗ не будет посылать информацию о маршруте в целевую сеть маршрутизатору М2. В результате маршрутизатор М2 имеет только один маршрут в целевую сеть, и если произойдет обрыв канала связи между маршрутизаторами Ml и М2, то он удалит из своей таблицы маршрутизации маршрут в Целевую сеть, избегая таким образом образования петли.

Технология Poison Reverse решает те же задачи, что и технология Split — Horizon, однако немного другими способами. Маршрутизаторы будут распространять маршруты через порты, которые явились их источниками. Но эти маршруты будут идентифицироваться как недостижимые, что достигается установкой количества переходов равным 16 (см. рис. 2.4.3).

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

Рис. 2.4.3. Пример работы технологии Poison Reverse

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

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

Совместное использование технологий Split -- Horizont и Poison Reverse необходимо для предотвращения образования петель маршрутизации, которые включают только два маршрутизатора. Однако могут существовать ситуации, когда три или более маршрутизатора включены в процесс «взаимного обмана». Например, какой-либо маршрутизатор Ml полагает, что он имеет маршрут через маршрутизатор М2, маршрутизатор М2 через МЗ, МЗ через М4, а М4 через Ml. Для ускорения сходимости в подобных ситуациях служит технология Triggered Update.

Эта технология требует, чтобы маршрутизатор немедленно посылал сообщения об обновлении своим соседям, если он обнаружил изменение в метрике маршрута. Сообщения должны быть посланы, даже если не пришло время для регулярных сообщений.

Технология Triggered Update может вызвать чрезмерную загрузку сети с ограниченной пропускной способностью, например коммутируемых телефонных каналов связи или сети с множеством маршрутизаторов. Все реализации протокола RIP должны включать заготовленный лимит частоты немедленной посылки сообщений об обновлении, чтобы не загружать сеть. Простым решением данной проблемы является установка таймера на случайное число между одной и пятью секундами, после чего посылается сообщение об обновлении. Если произошли другие изменения, которые должны вызвать немедленную посылку дополнительных сообщений, маршрутизатор должен выждать, пока таймер не обнулится, а затем послать новое сообщение. Таймер после этого устанавливается в другое случайное число в заданном интервале.

Например, маршрутизатор М будет устанавливать тайм-аут для своего маршрута в целевую сеть. Это заставит сформировать сообщения об обновлении и посылать их через порты маршрутизатора. Сообщения будут распространяться через все пути, обновляя метрику для целевой сети до бесконечности. Такой каскад сообщений об обновлении останавливается тогда, когда они достигают маршрутизатора, который использует путь для достижения целевой сети, который не проходит через маршрутизатор М.

Маршруты, получаемые с помощью протокола RIP, могут проходить серию стадий в таблице маршрутизации. Например, для маршрутизаторов фирмы 3Com маршруты проходят следующие стадии:

1)UP —  маршрут может находиться в  данной стадии, если он достижим  с определенной (меньше 16) метрикой. Маршрут остается в данном  состоянии в течение шестикратного  интервала времени между периодичной  посылкой сообщений об обновлении. Это значение известно как таймер маршрута. Данный таймер сбрасывается каждый раз, когда поступает новое сообщение об обновлении для этого маршрута. По истечении этого таймера маршрут более не рассматривается как корректный и переводится в стадию Garbare — Collection;

2)Hold — Down — маршрут, находящийся в стадии UP, переходит в данную стадию, если маршрутизатор получил сообщение  об обновлении маршрута с метрикой, равной бесконечности, от маршрутизатора, который явился источником информации  об этом маршруте. Маршрут будет  оставаться в данной стадии  весь период времени, равный четырехкратному  интервалу посылки сообщений  об обновлении. Это значение известно  как Hold -Down Timer. В этой стадии маршрутизатор  будет игнорировать информацию  о сети на промежутке времени, следующем за получением сообщения, информирующего о том, что и  эта сеть недостижима. Когда таймер Hold -- Down обнулится, маршрутизатор перейдет  в стадию Garbage — Collection. Если сообщение, содержащее информацию об этом  маршруте с метрикой меньше 16, получено от исходного маршрутизатора  до обнуления таймера, этот маршрут  перейдет в стадию UP. Цель этого  состояния — в позволении всем  другим маршрутизаторам в автономной  системе получать информацию  о том, что маршрут не функционирует. Это препятствует маршрутизатору  в этом состоянии ошибочно  принимать сообщение, содержимое  которого устарело; 

3)Garbare — Collection. Когда таймер маршрута, который был в стадии UP, обнулился, он переходит в стадию Garbage Collection. Маршрут может оставаться в  этой стадии на время, равное  четырехкратному интервалу обновлений. Это значение времени называется Garbage — Collection Timer. В этой стадии  соседи могут извещать маршрутизатор, что сеть более недостижима. В  течение этой стадии маршрут  с метрикой, равной 16, включается  во все сообщения об обновлении, посылаемые этим маршрутизатором. Это вызывает удаление маршрута  из списка возможных. Если не  получено сообщений об обновлении  до  обнуления таймера Garbage — Collection, маршрут удаляется  изтаблицы  маршрутизации. Если соседний маршрутизатор  информирует об этом маршруте  с метрикой меньше 16 до обнуления  таймера, новый маршрут будет  заменять маршрут, подготовленный  для удаления. В этом случае  таймер обнуляется.

2.4.2. Отключение тупиковой  сети

При отключении тупиковой сети, о ее недоступности в первый момент времени будет знать только один маршрутизатор. Изменения в маршрутных таблицах в других маршрутизаторах будут происходить только после рассылки таблицы вторым маршрутизатором.

В результате в установившемся значении во всех маршрутизаторах 20я сеть будет иметь максимальную дистанцию 16.