В современных компьютерных сетях обычно используются динамические алгоритмы выбора маршрута. Наиболее популярными являются два динамических алгоритма: дистанционно–векторная маршрутизация и маршрутизация состояния канала.
Каждый маршрутизатор содержит таблицу, в которой перечисляются кратчайшие известные пути к каждому получателю. Для обновления данных этих таблиц производится обмен информацией с соседними маршрутизаторами.
Таблицы, с которыми работают маршрутизаторы, содержат записи о каждом маршрутизаторе подсети. Каждая запись состоит из двух частей: номера оптимальной линии для данного получателя и оценки расстояния или времени прохождения пакета до этого получателя. Предполагается, что маршрутизаторам известно расстояние до каждого из соседей.
Отказаться от алгоритма пришлось из-за двух основных проблем. Во-первых, старый алгоритм не учитывал пропускную способность линий. Во вторых - алгоритм слишком долго приходил к устойчивому состоянию, несмотря на применение трюков типа расколотого горизонта. Поэтому он был полностью заменен новым алгоритмом, называющимся маршрутизацией с учетом состояния линий.
|
|
Маршрутизация с учетом состояний линий.
В основе этого алгоритма лежит простая идея, ее можно изложить в пяти требованиях к маршрутизатору. Каждый маршрутизатор должен:
· Обнаруживать своих соседей и узнавать их сетевые адреса.
· Измерять задержку или стоимость связи с каждым из своих соседей.
· Создавать пакет, содержащий всю собранную информацию.
· Посылать этот пакет всем остальным маршрутизаторам.
· Вычислить кратчайший путь ко всем остальным маршрутизаторам.
В результате каждому маршрутизатору высылается полная топология и все измеренные значения задержек. После этого для обнаружения кратчайшего пути к каждому маршрутизатору может применяться алгоритм Дийкстра. Рассмотрим его работу:
Знакомство с соседями.
Когда маршрутизатор загружается, его первая задача состоит в получении информации о его соседях. Он достигает этой цели, посылая специальный пакет HELLO по всем двухточечным линиям. При этом маршрутизатор на другом конце линии должен послать ответ, сообщая о себе. Имена маршрутизаторов должны быть глобально уникальными.