Алгоритм DUAL. 
Компьютерные сети и телекоммуникации. 
Маршрутизация в ip-сетях

Запоминание переданных смежными маршрутизаторами метрик маршрутов является основой другого дистанционно-векторного алгоритма — алгоритма диффузионного обновления DUAL.

По сравнению с алгоритмом DUAL дистанционно-векторный алгоритм Веллмана — Форда кажется несколько близоруким. Алгоритм DUAL заключается в более глубоком рассмотрении окружения и позволяет получить знания о топологии, которых часто оказывается достаточно для принятия быстрых решений о маршрутизации, что очень важно для ускорения сходимости сети.

Алгоритм DUAL ведет свое начало от работы Эдсгера Дейкстры и К. С. Шольтена (Edsger Dijkstra, С. 5. Sholten) «Termination Detection for Diffusing Computations», изданной в 1980 г. Алгоритм DUAL подкреплен многими математическими работами, основной из которых является «LoopFree Routing Using Diffusing Computations», написанная X. X. Гарсия-ЛунаАсевесом (J.J. Garcia-Luna-Aceves).

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

• — Статус маршрута. Различают два основных статуса: пассивные маршруты (Passive, Р), под которыми понимаются устойчивые и готовые к использованию маршруты, и активные (Active, /1), в отношении которых алгоритм DUAL не закончил процесс расчета маршрута.
• — Соседи (Neighbor, N) — смежные маршрутизаторы, подключенные в одну подсеть, знающие о существовании друг друга и обменивающиеся маршрутной информацией.
• — Переданное расстояние (Reported Distance, RD) — метрика маршрута до сети-получателя, полученная от соседа.
• — Выполнимое расстояние (Feasible Distance, FD) — сумма переданного расстояния, полученного от соседа, и расстояния до соседа.

Пример переданного и выполнимого расстояния до сети-получателя для маршрутизатора R1 приводится на рис. 6.4.

Из рис. 6.4 видно, что переданное маршрутизатору R1 от R2 расстояние до СП будет равно 50, а выполнимое расстояние — 150.

— Таблица топологии (base topology) — таблица, в которую алгоритм DUAL заносит все сети-получатели со всеми смежными маршрутизаторами, через которые они доступны.

Преемник (Successor, S) — сосед с наименьшим выполнимым расстоянием, который используется для достижения сети — получателя. Маршруты через преемников передаются в таблицу маршрутизации.

— Вероятный преемник (Feasible Successor, FS) — сосед, который может быть использован для достижения сети-получателя, если маршрут через преемника станет недоступен.

Рис. 6.4. Заявленное и выполнимое расстояние

Для назначения соседям особых статусов «Преемник» и «Вероятный преемник» необходимо выполнение следующих условий.

Для назначения соседа «Преемником» необходимо выполнения условия из формулы (6.1).

S = min (FD). (6.1).

Для назначения соседа «Вероятным преемником» необходимо выполнения условия из формулы (6.2).

FS = RD (FS) < FD (S). (6.2).

Принцип назначения маршрутизатором R1 своим соседям статусов «Преемник» и «Вероятный преемник» для сети-получателя СП приводится на рис. 6.5.

Рис. 6.5. Назначение «Преемника» и «Вероятного преемника»

Маршрут через R2 для достижения СП имеет наименьшее выполнимое расстояние (30), следовательно, но формуле (6.1) R2 назначается преемником для этой сети.

Переданное маршрутизатором R3 расстояние (25) до сети СП будет меньше выполнимого расстояния через преемника, следовательно, по формуле (6.2) R3 может быть назначен вероятным преемником для сети СП. Маршрут через R3 будет назначен резервным маршрутом до сети СГ1.

Маршрутизатор R4 не будет иметь никаких особых статусов, поскольку ни выполнимое, ни переданное расстояние через него не удовлетворяет формулам (6.1) и (6.2). Маршрутизатор R4 для R1 будет оставаться просто соседом.