Первое. При подключении сети, маршрутизатор первым делом должен "познакомиться" со своими соседями. Для этого он рассылает через все свои физические интерфейсы специальные пакеты с приветствием HELLO. Получив такой пакет, соседний узел должен ответить, сообщив данные о себе.
Второе. Узнав данные о соседях, маршрутизатор принимается за второй пункт программы - тестирование каналов связи с целью выяснения метрики каждого канала. Под метрикой может пониматься пропускная способность, время задержки, надежность, загрузка канала.
Пропускная способность – аппаратная характеристика (теоретическая скорость).
Надежность - количество ошибок на единицу переданной информации.
Задержку канала можно определить, послав специальный ECHO-пакет, который принимающая сторона должна немедленно отправить обратно. Разделив время отклика пополам, маршрутизатор вычисляет приблизительную величину задержки канала.
Загрузку канала также несложно измерить. Однако ответ на вопрос о том, как использовать показатель загруженности канала при вычислении метрики, отнюдь не однозначен. Рассмотрим небольшой пример. При наличии нескольких альтернативных путей до точки назначения маршрутизатор, оценив загруженность каждого из них, переключает трафик на канал с меньшей загрузкой. Тем самым он максимально использует свободный канал, что вполне логично. Во время следующего измерения метрик предпочтение может быть отдано уже другому каналу, через который трафик уже не идет и который, следовательно, теперь менее загружен. В результате трафик будет переключен на него. Это приводит к тому, что трафик постоянно переводится с одного канала на другой, что, естественно, не способствует стабильности в работе сети.
Хороший протокол должен уметь распределять нагрузку по нескольким каналам. Современные протоколы маршрутизации успешно справляются с этой задачей.
Рисунок 4. Обмен пакетами с объявлениями о состоянии каналов.
Третье. Шаг номер три в программе маршрутизатора состоит в сообщении полученных знаний остальным. Информация о каналах должна быть разослана соседям. Однако пакеты с объявлениями о состоянии каналов (Link State Advertisement, LSA) могут затеряться при транспортировке или прибыть в ином порядке. Для того чтобы получатель мог разобраться в пришедшей информации, каждый пакет с объявлением о состоянии каналов снабжается полями:
1. source (адрес отправителя),
2. sequence number (номер пакета в последовательности отправленных сообщений)
3. age (возраст) (см. Рисунок 4).
Получив пакет LSA, маршрутизатор проверяет пару (source, sequence), что позволяет отбросить устаревшие и дублированные объявления. Поле age задает время, по истечении которого не приславший новых объявлений узел считается недоступным.
В процессе работы маршрутизатора пакеты с объявлениями маршрутов рассылаются обычно лишь в случае каких-либо изменений в сети. В остальное же время протоколы состояния канала молчат и не загружают каналы служебной информацией, лишь изредка обмениваясь небольшими HELLO-пакетами.
Четвертое. Обмен информацией осуществляется с помощью веерной рассылки (flooding), т. е., получив пакет, маршрутизатор сохраняет копию в своей базе данных и посылает пакет дальше всем остальным соседям. В итоге пакет, отправленный одним из узлов сети, обязательно получат все остальные маршрутизаторы. В этом ключевое отличие данного алгоритма от алгоритма вектора расстояния, в котором каждый узел мог общаться только с непосредственно подключенными к нему маршрутизаторами, что часто приводит к эффекту "испорченного телефона", когда, не разобравшись в топологии, маршрутизатор сбивает с толку соседей.
Протокол состояния канала дает возможность каждому узлу самостоятельно обменяться информацией со всеми маршрутизаторами и получить представление о топологии сети. Именно поэтому данному алгоритму не свойственны проблемы возрастания до бесконечности, а жесткие ограничения на диаметр сети отсутствуют.
Узким местом такого подхода является необходимость обязательной синхронизации баз данных всех маршрутизаторов в пределах автономной системы. Если разные узлы будут по-разному представлять себе топологию сети, с которой они работают, то это приведет к образованию петель и к другим проблемам.
В конкретных протоколах данные поля могут носить другие названия, в протоколе OSPF (из стека TCP/IP), например, поля age и sequence носят названия DeadInt и DD Sequence, а протокол IS-IS даже использует специальный тип пакета - порядковый пакет. Однако, независимо от протокола, наличие подобной информации обязательно для надежной работы алгоритма предпочтения кратчайшего пути.
Пятое. После получения информации от всех узлов маршрутизатор может построить "карту" сети. Для этого он создает ориентированный граф, отражающий топологию сети. Соединение "точка-точка" между узлами представляется на графе парой дуг (по одной в каждом направлении), причем стоимости этих дуг могут отличаться друг от друга. Сети с множественным доступом (например, локальные сети) отображаются вершинами для каждого узла сети и дополнительной вершиной - "центром" этой сети. Дуги графа от "центра" до узлов сети не отображаются (см. Рисунок 5).
Имея в памяти такой граф, маршрутизатор применяет алгоритм Дейкстры для выбора пути с наименьшей суммарной стоимостью до каждой из вершин графа (т. е. до каждого узла сети). По результатам этих вычислений и строится таблица маршрутизации, используемая далее при переключении трафика.
