Алгоритмы маршрутизации применяются для определения оптимального пути пакетов от источника к приемнику и являются основой любого протокола маршрутизации. Для формулирования алгоритмов маршрутизации сеть рассматривается как граф. При этом маршрутизаторы являются узлами, а физические линии между маршрутизаторами — ребрами соответствующего графа. Каждой грани графа присваивается определенное число — стоимость, зависящяя от физической длины линии, скорости передачи данных по линии или финансовой стоимости линии.
Маршрутизация с проверкой состояния линий связи, в общем, имеет следующий вид.
Во время инициализации маршрутизатор определяет стоимость линии для каждого из своих сетевых интерфейсов. Затем маршрутизатор передает эту информацию всем остальным маршрутизаторам в сети, а не только соседним. Далее маршрутизатор следит за состоянием своих линий связи. При значительном изменении (радикально меняется стоимость линии, создается новая линия, становится недоступной существующая линия), маршрутизатор снова объявляет о стоимости своих линий всем маршрутизаторам конфигурации.
Поскольку каждый маршрутизатор получает информацию о стоимости линий от всех маршрутизаторов, каждый маршрутизатор должен рассчитать топологию всей конфигурации, а затем вычислить кратчайший путь к каждой сети. Выполнив расчет, маршрутизатор может сформировать маршрутную таблицу с данными о первом ретрансляционном участке в направлении каждого потенциального получателя. Поскольку при таком подходе к маршрутизации, маршрутизатор имеет данные обо всей сети, то нет необходимости использовать распределенную версию алгоритма маршрутизации, применяемой, например, в дистанционно-векторных алгоритмах. Вместо этого маршрутизатор может воспользоваться любым алгоритмом определения кратчайшего пути. На практике используют алгоритм Дейкстры [1].
В программе ROUTING_SIMULATOR планируется реализовать такие алгоритмы маршрутизации как OSPF [1,2,7] и SPF [2].
