6.7 Алгоритм DUAL
Алгоритм DUAL представляет собой машину с конечным числом состояний осуществляющую отслеживание всех маршрутов объявляемых соседями. Алгоритм DUAL использует метрики маршрутов для определения лучшего маршрута до сети получателя.
Метрика маршрута до сети получателя (выполнимое расстояние – FD) рассчитывается суммированием метрики заявленной соседом (заявленное расстояние – AD) и метрики маршрута до соседа заявившего этот маршрут.
Маршрутизатор объявивший маршрут с самой низкой метрикой становится преемником, соседом на которого будут передаваться пакеты до сети получателя. Может быть несколько преемников, если они имеют одинаковые FD до сети получателя. Все преемники помещаются в таблицу маршрутизации.
Алгоритм DUAL может вычислить резервный маршрут через вероятного преемника. Маршрутизатор может быть выбран алгоритмом DUAL в качестве вероятного преемника, если заявленное им расстояние до сети получателя меньше чем выполнимое расстояние до сети получателя через маршрутизатор преемник. Вероятные преемники не заносятся в таблицу маршрутизации, а хранятся в таблице топологии. В ней могут присутствовать более одного вероятного преемника.
Если маршрутизатор преемник становится недоступным, а для данного маршрута есть вероятный преемник, то он заносится в таблицу маршрутизации на место преемника, при этом не производятся дополнительные перерасчеты маршрутов.
Если маршрутизатор преемник становится недоступным, а в таблице топологии отсутствуют вероятные преемники, то алгоритму DUAL необходимо произвести выборы нового преемника, если это возможно, что потребует некоторого времени, в течение которого пакеты до сети получателя отправляться не будут.
Для сегмента сети передачи данных изображенной на рисунке 6.8, маршрутизатор R2 объявляет маршрутизатору R3 сеть 10.1.1.0/24 с заявленным расстоянием (AD) 1000. Маршрутизатор R3 заносит в свою таблицу топологии заявленное расстояние маршрутизатором R2 до сети 10.1.1.0/24 и вычисляет выполнимо расстояние (FD) для этой сети через маршрутизатор R2, которое равняется 2000. Маршрутизатор R4 также объявляет маршрутизатору R3 сеть 10.1.1.0/24, но с заявленным расстоянием (AD) 1500. Маршрутизатор R3 также заносит в таблицу топологи AD от маршрутизатора R4 и вычисляет FD через него, равное 3000. Исходя из полученных данных, маршрутизатор R3 назначает преемником для сети 10.1.1.0/24 маршрутизатор R2, так как FD через маршрутизатор R2 до сети 10.1.1.0/24 наименьшее.
117
10.1.1.0/24
R1
1000
|
500 |
|
|
|
|
R2 |
|
R4 |
|
|
|
1000 |
1500 |
|
|
|
|
|
Сеть |
|
FD |
AD |
Topology |
|
10.1.1.0/24 |
2000 |
|
|
|
R3 |
Via R2 |
|
2000 |
1000 |
S |
Via R4 |
|
3000 |
1500 |
FS |
|
|
|
||||
Рисунок 6.8 – Выбор преемника и вероятного преемника
Однако AD заявленное маршрутизатором R4 до сети 10.1.1.0/24 меньше FD преемника, назначенного маршрутизатором R3, следовательно, маршрутизатор R3 имеет право назначить маршрутизатор R4 вероятным преемником для сети 10.1.1.0/24.
10.1.1.0/24
R1
1000
|
500 |
|
|
|
|
R2 |
|
R4 |
|
|
|
|
|
|
|
|
|
1000 |
1500 |
|
|
|
|
|
Сеть |
|
FD |
AD |
Topology |
|
10.1.1.0/24 |
3000 |
|
|
|
R3 |
Via R2 |
|
2000 |
1000 |
|
Via R4 |
|
3000 |
1500 |
S |
|
|
|
||||
Рисунок 6.9 – Действия маршрутизатора при недоступности преемника
118
Если канал связи между маршрутизаторами R2 и R3 выходит из строя (Рисунок 6.9), маршрутизатор R3 вычеркивает из таблицы топологии запись о маршрутизаторе R3, преемником для сети 10.1.1.0/24 становиться маршрутизатор R4 и этот маршрут записывается в таблицу маршрутизации. Других действий маршрутизатор R3 не производит, при этом передача пользовательского трафика не прерывается.
6.7.1 Работа алгоритма DUAL
На рисунке 6.10 изображен сегмент сети, в котором маршрутизатор R4 не может выбрать для сети 10.1.1.0/24 вероятного преемника, так как AD заявленное маршрутизаторами R3 и R5 больше FD через маршрутизатор R2 назначенного маршрутизатором R4 преемником для сети 10.1.1.0/24.
10.1.1.0/24
R1
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Сеть |
FD |
AD |
Topology |
|
|
|
|
|
|
|
10.1.1.0/24 |
2 |
|
|
|
|
|
|
|
1 |
|
Via R 2 |
2 |
1 |
S |
|
|
|
|
R2 |
|
R4 |
Via R 3 |
5 |
3 |
|
|
|
|
|
|
Via R 5 |
5 |
4 |
|
||
|
|
|
|
2 |
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Сеть |
FD |
AD |
Topology |
|
|
|
Сеть |
FD |
AD |
Topology |
10.1.1.0/24 |
3 |
|
|
|
|
|
10.1.1.0/24 |
3 |
|
|
Via R 2 |
3 |
1 |
S |
|
1 |
|
Via R 4 |
3 |
2 |
S |
Via R 4 |
4 |
2 |
FS |
R3 |
|
R5 |
Via R 3 |
4 |
3 |
|
Via R 5 |
4 |
3 |
|
|
|
|
|
|
Рисунок 6.10 – Сегмент сети без вероятного преемника
Что будет происходить в сети, если маршрутизатор R4 обнаружит недоступность маршрутизатора R2 (Рисунок 6.11).
119
10.1.1.0/24
R1
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Сеть |
FD |
AD |
Topology |
|
|
|
|
|
1 |
|
10.1.1.0/24 |
2 |
|
|
|
|
|
|
|
|
Via R 2 |
2 |
1 |
S |
|
|
|
|
|
R2 |
|
R4 |
Via R 3 |
5 |
3 |
|
|
|
|
|
|
Via R 5 |
5 |
4 |
|
||
|
|
|
|
2 |
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Сеть |
FD |
AD |
Topology |
|
|
|
Сеть |
FD |
AD |
Topology |
10.1.1.0/24 |
3 |
|
|
|
|
|
10.1.1.0/24 |
3 |
|
|
Via R 2 |
3 |
1 |
S |
|
1 |
|
Via R 4 |
3 |
2 |
S |
Via R 4 |
4 |
2 |
FS |
R3 |
|
R5 |
Via R 3 |
4 |
3 |
|
Via R 5 |
4 |
3 |
|
|
|
|
|
|
Рисунок 6.11 – Маршрутизатор R2 недостижим
На маршрутизаторе R4 алгоритм DUAL маркирует маршрут до сети 10.1.1.0/24 через R2 как недостижимый и вычеркивает этот маршрут из таблицы топологии и таблицы маршрутизации.
На маршрутизаторе R4 алгоритм DUAL не имеет вероятного преемника для сети и 10.1.1.0/24, поэтому он выставляет метрику маршрута на сеть 10.1.1.0/24 равную -1 (недостижима). Вероятный преемник не может быть найден в таблице топологии и маршрут переводится из пассивного состояния в активное. В активном состоянии маршрутизатор начинает рассылку запросов соседям для определения нового преемника. Маршрутизатор R4 посылает запросы на R3 и R5 для поиска альтернативного маршрута до сети 10.1.1.0/24. В таблице топологии маршрутизатор R4 помечает что, он отправил запрос о сети 10.1.1.0/24 маршрутизаторам R3 и R5. Маршрутизатор R5 получив запрос на сеть 10.1.1.0/24 от маршрутизатора R4, который в его таблице топологии назначен преемником, вычеркивает маршрут до сети 10.1.1.0/24 через маршрутизатор R4 (Рисунок 6.12).
На маршрутизаторе R5 алгоритм DUAL маркирует маршрут до сети 10.1.1.0/24 через R4 как недостижимый и отсылает запрос о наличии маршрута до сети 10.1.1.0/24 маршрутизатору R3.
В это время маршрутизатор R3, получив запрос от R4 о маршруте до сети 10.1.1.0/24, вычеркивает маршрут до сети 10.1.1.0/24 через маршрутизатор R4 из своей таблицы топологии.
120
10.1.1.0/24
R1
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Сеть |
FD |
AD |
Topology |
|
|
|
|
|
|
|
10.1.1.0/24 |
-1 |
|
**ACTIVE ** |
|
|
|
|
|
|
|
Via R 3 |
5 |
3 |
(Q) |
|
|
|
|
R2 |
|
R4 |
Via R 5 |
5 |
4 |
(Q) |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
2 |
2 |
1 |
Q |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
Q |
|
|
|
|
Сеть |
FD |
AD |
Topology |
|
|
|
Сеть |
FD |
AD |
Topology |
10.1.1.0/24 |
3 |
|
|
|
|
|
10.1.1.0/24 |
3 |
|
|
Via R 2 |
3 |
1 |
S |
|
1 |
|
Via R 4 |
3 |
2 |
S |
Via R 4 |
4 |
2 |
FS |
R3 |
|
R5 |
Via R 3 |
4 |
3 |
|
Via R 5 |
4 |
3 |
|
|
|
|
|
|
Рисунок 6.12 – Маршрутизатор R4 рассылает запросы соседям
Однако у маршрутизатора R3 в таблице присутствует маршрут до этой сети через маршрутизатор R2, причем маршрутизатор R2 назначен преемником. Следовательно, маршрутизатор R3 может ответить маршрутизатору R4 на запрос о маршруте до сети 10.1.1.0/24.
10.1.1.0/24
R1
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
Сеть |
FD |
AD |
Topology |
|
|
|
|
|
|
10.1.1.0/24 |
-1 |
|
**ACTIVE ** |
|
|
|
|
|
|
Via R 3 |
5 |
3 |
|
|
|
|
R2 |
|
R4 |
Via R 5 |
5 |
4 |
(Q) |
|
|
|
|
|
|
|
|
||
|
|
|
2 |
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
R |
|
|
|
|
Сеть |
FD |
AD |
Topology |
|
|
Сеть |
FD |
AD |
Topology |
|
|
10.1.1.0/24 |
-1 |
|
**ACTIVE ** |
||||
10.1.1.0/24 |
3 |
|
|
|
|
|
|||
|
|
1 |
|
Via R 3 |
4 |
3 |
(Q) |
||
Via R 2 |
3 |
1 |
S |
|
|||||
Via R 5 |
4 |
3 |
R3 |
Q |
R5 |
|
|
|
|
|
|
|
|
|
|
|
Рисунок 6.13 – Маршрутизатор R4 получает ответ от R3
121
Маршрутизатор R4 принимает ответ от R3 о наличии маршрута до сети 10.1.1.0/24 и снимает маркер запроса со строчки в таблице топологии, однако, сеть 10.1.1.0/24 все еще находится в активном состоянии, так как маршрутизатор R5 еще не ответил на запрос (Рисунок 6.13).
Затем маршрутизатор R5 рассчитывает новое FD маршрута до сети 10.1.1.0/24, устанавливает нового преемника в таблицу топологии, и переводит маршрут из активного состояния в пассивное. Маршрутизатор R4 все еще ожидает ответа от R5 (Рисунок 6.14).
10.1.1.0/24
R1
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
Сеть |
FD |
AD |
Topology |
|
|
|
|
|
|
10.1.1.0/24 |
-1 |
|
**ACTIVE ** |
|
|
|
|
|
|
Via R 3 |
5 |
3 |
|
|
|
|
R2 |
|
R4 |
Via R 5 |
5 |
4 |
(Q) |
|
|
|
|
|
|
|
|
||
|
|
|
2 |
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
||
Сеть |
FD |
AD |
Topology |
|
|
Сеть |
FD |
AD |
Topology |
|
|
10.1.1.0/24 |
4 |
|
|
||||
10.1.1.0/24 |
3 |
|
|
|
|
|
|
||
|
|
1 |
|
Via R 3 |
4 |
3 |
S |
||
Via R 2 |
3 |
1 |
S |
|
|||||
Via R 5 |
4 |
3 |
R3 |
R |
R5 |
|
|
|
|
|
|
|
|
|
|
|
Рисунок 6.14 – Маршрутизатор R5 получает ответ от R3
Маршрутизатор R5 отвечает на запрос о маршруте до сети 10.1.1.0/24 маршрутизатору R4. На маршрутизаторе R4 алгоритм DUAL получает ответ и удаляет флаг запроса с маршрута до сети 10.1.1.0/24 через R5.
Маршрутизатор R4 рассчитывает новые FD до сети 10.1.1.0/24 через маршрутизаторы R3 и R5. Маршруты через R3 и R5 имеют одинаковые FD и оба маркируются как преемники. Маршрут до сети 10.1.1.0/24 переводится из активного состояния в пассивное.
Маршрутизатор R4 устанавливает новых преемников в таблицу маршрутизации (Рисунок 6.15).
122
10.1.1.0/24
R1
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Сеть |
FD |
AD |
Topology |
|
|
|
|
|
|
|
10.1.1.0/24 |
5 |
|
|
|
|
|
|
|
|
|
Via R 3 |
5 |
3 |
S |
|
|
|
|
R2 |
|
R4 |
Via R 5 |
5 |
4 |
S |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
2 |
2 |
1 R |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Сеть |
FD |
AD |
Topology |
|
|
|
Сеть |
FD |
AD |
Topology |
|
|
|
10.1.1.0/24 |
4 |
|
|
||||
10.1.1.0/24 |
3 |
|
|
|
|
|
|
|
||
|
|
|
1 |
|
Via R 3 |
4 |
3 |
S |
||
Via R 2 |
3 |
1 |
S |
|
|
|||||
R3 |
|
R5 |
|
|
|
|
||||
Via R 5 |
4 |
3 |
|
|
|
|
|
|
Рисунок 6.15 – Маршрутизатор R4 получает ответ от R5
Полученная сеть (Рисунок 6.16) является сведенной и стабильной. Маршрутизатор R4 имеет в таблице маршрутизации два маршрута до сети 10.1.1.0/24. По этим двум маршрутам автоматически включается механизм балансировки нагрузки.
10.1.1.0/24
R1
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Сеть |
FD |
AD |
Topology |
|
|
|
|
|
|
|
10.1.1.0/24 |
5 |
|
|
|
|
|
|
|
|
|
Via R 3 |
5 |
3 |
S |
|
|
|
|
R2 |
|
R4 |
Via R 5 |
5 |
4 |
S |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
2 |
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Сеть |
FD |
AD |
Topology |
|
|
|
Сеть |
FD |
AD |
Topology |
|
|
|
10.1.1.0/24 |
4 |
|
|
||||
10.1.1.0/24 |
3 |
|
|
|
|
|
|
|
||
|
|
|
1 |
|
Via R 3 |
4 |
3 |
S |
||
Via R 2 |
3 |
1 |
S |
|
|
|||||
R3 |
|
R5 |
|
|
|
|
||||
Via R 5 |
4 |
3 |
|
|
|
|
|
|
Рисунок 6.16 – Сегмент сети после завершения работы алгоритма DUAL
123