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

В результате освоения главы б студент должен: знать

• • ограничения алгоритма Веллмана — Форда;
• • принцип работы алгоритма DUAL; уметь
• • проводить моделирование событий сети передачи данных алгоритмом DUAL; владеть
• • терминологией алгоритма DUAL.

Слабые стороны алгоритма Веллмана — Форда

Протоколы маршрутизации на основе дистанционно-векторного алгоритма Веллмана — Форда имеют две фундаментальные проблемы:

• — маршрутные петли;
• — счет до бесконечности.

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

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

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

Возникает вопрос: что ценного в полученной от смежного маршрутизатора метрике?

На рис. 6.1 изображена топология сети, в которой у маршрутизатора R1 имеется маршрут к сети-получателю (СП) через маршрутизатор R2.

Маршрутизатор R1 изначально выбрал маршрутизатор R2 в качестве следующего маршрутизатора к СП, поскольку объявленная метрика маршрутизатора R2 (100) в сумме со стоимостью канала связи до него (5) дала наименьшее значение (100 + 5 = 105).

Рис. 6.1. Обработка топологии сети алгоритмом Веллмана — Форда.

Расположение маршрутизаторов R4 и R5 таково, что, независимо от того, какой путь они изберут для передачи трафика, направленного до СП, этот путь пролегает через маршрутизатор R1. Как показано на рис. 6.1, метрика пути по альтернативному маршруту меньше, чем метрика прямого маршрута через маршрутизатор R1, следовательно, маршрутизатор R5 выбирает альтернативный маршрут. Несмотря на то, что объявляемая маршрутизатором R1 метрика (105) меньше, маршрутизатор R5 выбирает маршрут через другого соседа, поскольку объявляемая соседом метрика (135) в сумме со стоимостью сегмента дает меньшее значение (135 + 5 = 140), чем метрика маршрута через маршрутизатор R1 (105 + 40 = 145).

На рис. 6.2 показана информация о стоимости маршрутов до сети СП после обнаружения маршрутизатором R1 отказа канала связи с маршрутизатором R2. Стоимость маршрутов получена сложением стоимости маршрута через предоставивший информацию маршрутизатор и стоимости канала связи до этого маршрутизатора. При этом R1 не запоминает информацию, предоставленную смежными маршрутизаторами, а сразу после вычисления собственной метрики ее забывает.

Маршрутизатор R1 не может сразу использовать полученную от смежных маршрутизаторов информацию, поскольку это может привести к возникновению маршрутной петли.

Действительно, если в качестве маршрута до сети СП R1 будет использовать маршрут через маршрутизатор R5, такая петля возникнет. Поэтому маршрутизатору R1 перед принятием решения о переключении на альтернативный маршрут необходимо подождать, пока R5 не обновит свой маршрут до сети СП и не перестанет объявлять его R4.

Рис. 6.2. Поиск альтернативного маршрута алгоритмом Веллмана — Форда.

После этого маршрутизатор R4 перестанет объявлять R1 о достижимости сети СП. И только теперь маршрутизатор R1 сможет использовать единственный оставшийся маршрут до сети СП через маршрутизатор R3.

На рис. 6.3 маршрутизатор R1 запомнил метрики маршрутов до сети СП, объявленные всеми смежными маршрутизаторами. Поэтому при обнаружении отказа R2 маршрутизатор R1 способен сразу определить, что он не может положиться на лучшую метрику маршрутизатора R5, поскольку его объявленная метрика (140) больше, чем собственная метрика маршрутизатора R1 (105) через отказавший R2. Это значит, что R5 изначально находился дальше от сети СП, чем маршрутизатор R1.

Рис. 6.3. Запоминание переданной метрики.

При этом метрика, переданная маршрутизатором R3, равна 100, что меньше, чем 105, а значит, R3 был изначально ближе к сети СП. Следовательно, маршрутизатор R1 может использовать маршрут через R3 как альтернативный маршрут до сети СП, при этом ему нет необходимости ожидать реакции маршрутизаторов R4 и R5 на произошедшие в сети изменения.

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