Маршрутизация по вектору расстояния
Маршрутизация, базирующаяся на векторе расстояния, применяется в протоколе маршрутной информации, который используется в для маршрутизации в сети 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. Как работает алгоритм Дейкстры?