Дистанционно–векторная маршрутизация

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

Каждый маршрутизатор содержит таблицу, в которой перечисляются кратчайшие известные пути к каждому получателю. Для обновления данных этих таблиц производится обмен информацией с соседними маршрутизаторами.

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

Отказаться от алгоритма пришлось из-за двух основных проблем. Во-первых, старый алгоритм не учитывал пропускную способность линий. Во вторых - алгоритм слишком долго приходил к устойчивому состоянию, несмотря на применение трюков типа расколотого горизонта. Поэтому он был полностью заменен новым алгоритмом, называющимся маршрутизацией с учетом состояния линий.

Маршрутизация с учетом состояний линий.

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

· Обнаруживать своих соседей и узнавать их сетевые адреса.

· Измерять задержку или стоимость связи с каждым из своих соседей.

· Создавать пакет, содержащий всю собранную информацию.

· Посылать этот пакет всем остальным маршрутизаторам.

· Вычислить кратчайший путь ко всем остальным маршрутизаторам.

В результате каждому маршрутизатору высылается полная топология и все измеренные значения задержек. После этого для обнаружения кратчайшего пути к каждому маршрутизатору может применяться алгоритм Дийкстра. Рассмотрим его работу:

Знакомство с соседями.

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