Алгоритм диффузионного обновления

Метод корректировки отмены маршрута

Механизм принудительных объявлений

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

Зловещий призрак count-to-infinity продолжает бродить по сетям, использующим в своей работе протоколы вектора расстояний. Если зацикливание в сети все же произошло, то образовавшаяся петля будет разорвана, когда метрика маршрута превысит максимально допустимую. Этот процесс может быть ускорен с помощью механизма принудительных объявлений (triggered updates).

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

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

Современные протоколы вектора расстояний IGRP и EIGRP поддерживаются, например, маршрутизаторами Cisco. Они имеют такую полезную функцию, как метод корректировки отмены маршрута (route-poisoning).

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

В соответствии с правилом корректировки значительно выросшая стоимость маршрута расценивается как признак образования петли. Такой маршрут удаляется из таблицы маршрутизации. Какое изменение стоимости маршрута понимать как "значительное", зависит от администратора.

Слабая сторона алгоритма вектора расстояний, как уже было сказано, - медлительность реакции на негативные изменения в топологии.

По сообщению компании Cisco, ее специалистам удалось ликвидировать данный недостаток. По скорости восстановления после аварии протокол EIGRP не уступает протоколам состояния канала. Этим он прежде всего обязан алгоритму диффузионного обновления DUAL (Distibuted Update Algorithm).

Маршрутизатор, работающий по алгоритму DUAL, хранит в таблице маршрутизации не только адрес следующего узла на пути к сети назначения, но и список соседей, знающих такую же короткую дорогу (feasible successors).

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

(О деталях работы EIGRP см. http://www.cisco.com/warp/public/103/1.html)