Измерение стоимости линии

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

Создание пакетов состояния линий.

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

Создать пакеты состояния линий несложно. Самая сложная часть заключается в выборе момента времени их создания. Их можно создавать периодически через равные интервалы времени. Другой вариант заключается в создании пакетов, когда происходит какое–ни будь значительное событие, например, линия или соседний маршрутизатор выходят из строя или, наоборот, снова появляются в сети, либо существенно изменяют свои свойства.

Вычисление новых маршрутов.

Собрав полный комплект пакетов состояния линий, маршрутизатор может построить полный граф подсети, т.к. он располагает данными обо всех линиях. На самом деле, каждая линия представлена даже дважды, по одному значению для каждого направления. Эти два значения могут быть усреднены или использоваться по отдельности.

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

Маршрутизация с учетом состояния линий широко применяется в современных сетях. Одним из использовавших этот алгоритм является протокол – OSPF, все чаще применяемый в Интернет.