Маршрутизация по вектору расстояния

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

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

Рис. 23 Маршрутизация по вектору расстояния

 

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

В примере сети, показанной на рисунке, для узлов B и C требуется 10 и 12 единиц времени (соответственно), чтобы ответить и послать их текущие векторы расстояния узлу A. Теперь узел A может сделать вывод, что для путешествия пакета к узлам B и C требуется 5 и 6 единиц времени соответственно. Оценки 6 и 4 в таблицах узлов B и C игнорируются, поскольку оценки 5 и 6 считаются более свежими. После этого получение для узла A новой таблицы является относительно простой задачей. Рассмотрим случай определения маршрута от узла A к узлу D. Узел A оценивает, что если он направит пакет, предназначенный для D, прямо к узлу B, то потребуется 5(AB) плюс 4(СВ)=9 единиц времени, так что первый выбор – направление через узел B. Процедура повторяется для всех других, несмежных узлов сети. Трафик между AE направляется через узел B с суммарным расстоянием 11 (5+6), а не через узел C с суммарным расстоянием 12 (6+6). Наконец, пакеты, предназначенные для узла F, отправляются не через узел B (маршрут с суммарным расстоянием 18), а через более короткий путь, проходящий через узел C, за 16 временных единиц.

Главный недостаток этой схемы – медленная реакция на «плохие» события типа аварийного отключения узлов, из-за которой схема продолжает использовать непригодные маршруты.

 

Задания

1. На рисунке приведены текущие состояния звеньев сети, состоящей из 6 узлов. Нарисуйте эту сеть и определите таблицу маршрутизации, связанную с узлом A (используйте формальный метод).

 

Узел

A	B(10) D(5) E(20)
B	A(10) C(20) E(10) F(10)
C	B(20) F(20)
D	A(5) E(10)
E	A(20) B(10) D(10) F(10)
F	B(10) C(20) E(10)

Рис. 24 Текущие состояния звеньев 6-узловой сети

 

2. Маршрутизация сети из 6 узлов базируется на векторе расстояния; маршрутизатор A расположен рядом с маршрутизаторами B, D и E. На рис. 25 приведены таблицы с векторами расстояний, связанных с каждым из этих трех маршрутов. Используя указанные таблицы, выведите новую таблицу маршрутизации для узла A. Предположите, что текущее расстояние между узлом A и его соседями точно отражено в этих таблицах.

 

Узел B		Узел D		Узел E
A			A			A
B	-		B			B
C			C			C
D			D	-		D
E			E			E	-
F			F			F

Рис. 25 Таблицы с векторами расстояний для трех узлов сети

 

Контрольные вопросы

1. Дайте определение наикратчайшего пути?

2. Как определяется наикратчайший или оптимальный путь?

3. Как работает алгоритм Дейкстры?