Адаптивные (динамические) алгоритмы маршрутизации по вектору расстояния

Имеется несколько типов алгоритмов. Они функционируют на основе таблиц хранящихся у маршрутизатора. Таблицы определенным образом хранят кратчайшие пути (направления) к каждому адресату. Таблицы маршрутизаторов регулярно обновляются путем обмена информацией между соседями.

Примером алгоритма такого типа является алгоритм RIP. В этом случае таблица маршрутизатора содержит записи о каждом маршрутизаторе сети. При этом каждая запись состоит из двух частей: линия для данного адресата и продолжительность времени прохождения пакета или расстояние. Предполагается что маршрутизаторам известно расстояние до каждого из соседей (имеется ввиду весовой коэффициент). Если в качестве расстояния используется время задержки, то оно может быть измерено с помощью пакета ECHO (источник передает пакет, получатель отправляет пакет обратно с установкой времени получения; таким образом можно узнать время прохождения соседа с соседом).

В ходе выполнения алгоритма маршрутизаторы через определенные интервалы времени посылают соседям список с приблизительной задержкой для каждого получателя. Если одна из таблиц пришла к маршрутизатору Y от соседа X и в таблице указано, что время распространения от X до i — X_i, а от X до Y — m, то от Y до X_i — X_i +m. Выполнив такие расчеты для всех маршрутизаторов соседних с Y, можно выбрать наилучший путь до адресата. Обработка этих данных в результате дает новую таблицу кратчайших путей.

Пример:

Рассматриваем маршрутизатор J.

1. Маршрутизатор измерил задержки до своих соседей, выдав им пакет ECHO, и получил следующие данные: JA=8, JI=10,JH=12,JK=6

2. Маршрутизатор получил от своих соседей таблицы со следующими значениями:

Вывод если приходит пакет на маршрутизатор D то J включает линию H. Если на маршрутизатор F, то включает линию I. Каждый маршрутизатор в узле строит такую таблицу, куда посылать пакеты в соответствии с адресатом. Недостаток: расчет требует много ресурсов (времени).