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

Это динамическая маршрутизация.

Идея этого алгоритма - у каждого маршрутизатора в подсети есть таблица расстояний до каждого маршрутизатора в подсети. Периодически маршрутизатор обменивается информацией со своими соседями и обновляет информацию в таблице. Каждый элемент таблицы состоит из двух полей: первое - номер линии, по которой надо отправлять пакеты, чтобы достичь нужного места, второе - величина задержки до места назначения. Эта величина задержки может быть измерена в разных единицах: скачках, миллисекундах, длине очереди на линии и т.д.

Каждые Т секунд маршрутизатор шлет своим соседям свой вектор задержек до всех маршрутизаторов в подсети. В свою очередь он получает такие же вектора от своих соседей. Кроме этого, он постоянно замеряет задержки до своих соседей. Поэтому, имея вектора расстояний от соседей и зная расстояние до соседей, маршрутизатор всегда может вычислить кратчайший маршрут.

На рис.5-10(а) показана подсеть. На рис.5-10(в) показаны вектора, которые J маршрутизатор получил от своих соседий и его замеры задержек до соседей. Там же показана итоговая таблица маршрутизации, которую J маршрутизатор вычислит на основании этой информации.

Рассмотрим как J маршрутизатор с помощью этой таблицы вычислит маршрут до G.

Проблема бесконечного счетчика

Алгоритм маршрутизации по вектору расстояния теоретически работает хорошо, но у него есть один недостаток: он очень медленно сходится к правильному значению. Информация о появлении хорошего маршрута в подсети распространяется более или менее быстро, а вот данные о потере, разрушении какого маршрута распространяются не столь быстро.

Рассмотрим пример на рис.5-11. Там дана линейная подсеть. Пусть изначально маршрутизатор А не работал. Поэтому у всех маршрутизаторов в подсети для него стояла ╔. Пусть в какой-то момент времени А был включен. По истечении определенного времени маршрутизаторы начнут обмениваться векторами и В узнает об А. Еще через один обмен векторами об А узнает С и т.д. Таким образом, информация о новом маршруте будеи распространяться линейно шаг за шагом за каждый обмен векторами. Если самый длинный маршрут в подсети имеет длину N, то потребуется N обменов векторами пока информация о новом маршруте дойдет до самого удаленного узла в подсети.

Теперь рассмотрим обратную ситуацию на рис.5-11(в). Здесь изначально все маршрутизаторы и линии были работоспособны. Пусть в какой-то момент времени линия между А и В разрушена. В перестает видеть А, но С говорит В: "Не беспокойся у меня есть маршрут до А." При этом В не подозревает, что маршрут от С до А идет через него же. При этом марутизаторы D и Е своих таблиц не меняют. Их расстояния до А на единицу больше чем у С. Плохая весть будет распространяться медленно пока счетчики задержек не примут значения бесконечности для данной сети. Только после этого станет ясно что А не достижимо ни через С, ни через D, ни через Е. Сколько времени на это потребуется, зависит от конкретного значения бесконечности в данной подсети.

Разделение направлений

Одним из решений этой проблемы является следующий прием. Алгоритм работает как было описано, но при передаче вектора по линии, по которой достижим маршрутизатор Х, расстояние до Х указывается как бесконечность. Если теперь рассмотреть как будет работать подсеть на рис.5-11(в), то там проблем возникать не будет.

Однако, рассмотрим подсеть на рис.5-12. Если линия между С и D будет разрушена, то С сообщит об этом А и В. Однако, А знает что у В есть маршрут до D, а В знает что такой маршрут есть и у А. И опять мы сваливаемся в проблему бесконечного счетчика.