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

Идея — выполнение следующих требований:

1. Каждый маршрутизатор должен обнаруживать своих соседей и определять сетевые адреса. Получение информации о соседях осуществляется после загрузки маршрутизатора посылкой пакета HELLO по всем направлениям. Адреса маршрутизаторов уникальны и каждый в ответ посылает свой адрес.
2. Каждый маршрутизатор должен уметь опросить состояние, чтобы измерить задержку или стоимость связи с каждым из своих соседей. Наиболее общий способ измерения — пакет ECHO.
3. Каждый маршрутизатор должен уметь создавать пакет, содержащий всю информацию о соседях. Пакет состоит из идентификатора маршрутизатора, порядкового номера, возраста и списка соседей.
4. Каждый маршрутизатор должен уметь посылать этот пакет всем маршрутизаторам. Основная идея передачи пакетов – алгоритм заливки.
5. Порядковый номер увеличивается для каждого следующего пакета. Когда приходит пакет состояния, маршрутизатор ищет адрес отправителя и порядковый номер пакета в своем списке. Если это новый пакет он рассылается по всем линиям по методу заливки. Если дубликат — он удаляется. Если порядковый номер меньше чем в списке он также удаляется как устаревший. Т.е. в сети идет постоянный обмен информацией между маршрутизаторами. При этом маршрутизаторы постоянно обновляют пакеты (каждый обновляет свой пакет).
6. Если маршрутизатор вышел из строя, то пакет маршрутизатора будет изменен в соответствии с состоянием сети. Эти изменения прочувствуют все маршрутизаторы. Недостатки: последовательный номер пакета может достичь максимально возможного и обнулиться, тогда возникнет путаница. Одним из решений увеличения до 32 разрядов порядковых номеров пакетов (если обмен каждую секунду происходит, то 32х разрядов хватит на 100 лет). Другим недостатком является то, что при выключении одного из маршрутизаторов и потом включении порядковые номера его пакетов будут начинаться с нуля и будут игнорироваться в сети как устаревшие. Решение — использование возраста пакета. Возраст пакета уменьшается на 1 каждую секунду (как правило). Когда возраст становится равным нулю, он удаляется. Как правило, обмен пакетами в сети осуществляется раз в 10 секунд. Когда маршрутизатор выключится, т.е. больше 10 секунд поле возраста пакета будет уменьшено на единицу все равно и при загрузке и последующем распространении пакета он не удалится, т.к. возраст не ноль, т.е. будет сохранен во всех узлах сети.
7. После того как информация о сети распространена между маршрутизаторами, маршрутизатор должен уметь вычислять кратчайший путь. Как правило, применяется алгоритм Дейкстры для статической маршрутизации или строится новая таблица маршрутов, т.е. динамически получили информацию, она превратилась в статический вид… Через 10 секунд опять…

Наиболее известные протоколы, использующие маршрутизаторы с учетом состояния линии (канала) — OSPF (в Интернете) и IS-IS (DecNet, часть Интернета).