Алгоритмы адаптивной маршрутизации.

Самыми распространенными являются алгоритмы адаптивной (динамической) маршрутизации. Эти алгоритмы обеспечивают автоматическое обновление таблиц маршрутизации после изменения конфигурации составной сети. Протоколы, построенные на основе адаптивных алгоритмов, позволяют всем маршрутизаторам собирать информацию по топологии связей в сети, оперативно обрабатывать все изменения конфигурации этих связей. В таблицах маршрутизации в случае адаптивной маршрутизации имеется информация об интервале времени, в течение которого данный маршрут будет действителен. Это время называют временем жизни маршрута (Time To Live, TTL).

Адаптивные алгоритмы должны отвечать следующим требованиям:

1. Обеспечивать рациональность маршрута (в данном случае речь не идет об оптимальности).

2. Они не должны требовать слишком большого объема вычислений и порождать интенсивный служебный трафик.

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

Протоколы, построенные на основе адаптивных алгоритмов, делятся на две группы:

1. Дистанционно-векторные алгоритмы (Distance Vector Algorithms, DVA).

2. Алгоритмы состояния связей (Link State Algorithms, LSA).

В алгоритмах дистанционно-векторного типа каждый маршрутизатор периодически и широковещательно рассылает по сети вектор, компонентами которого являются расстояния от данного маршрутизатора до всех известных ему сетей. Здесь под расстоянием понимается число хопов. Возможна и другая метрика: учитывается наряду с числом промежуточных хопов время прохождения пакетов по сети между соседними маршрутизаторами. При получении вектора от соседа, маршрутизатор наращивает расстояние до указанных в векторе сетей на расстояние до данного соседа. Получив вектор от соседнего маршрутизатора, каждый маршрутизатор добавляет к нему информацию об известных ему других сетях, о которых он узнал непосредственно (если они подключены к его портам) или из аналогичных объявлений других маршрутизаторов, а затем снова рассылает новое значение вектора по сети. В конце концов, каждый маршрутизатор узнает информацию обо всех имеющихся в интерсети сетях и о расстоянии до них через соседние маршрутизаторы.

Дистанционно-векторные алгоритмы хорошо работают только в небольших сетях. В больших сетях они засоряют линии связи широковещательным трафиком. Работа маршрутизатора в соответствии с дистанционно-векторным протоколом напоминает работу моста, так как точной топологической картины сети такой маршрутизатор не имеет. Наиболее распространенным протоколом, основанным на дистанционно-векторном алгоритме, является протокол RIP, который распространен в двух версиях - RIP IP, работающий с протоколом IP, и RIP IPX, работающий с протоколом IPX. Примечание: Протокол RIP использует в качестве транспорта либо протокол IP либо стека TCP/IP, либо протокол IPX стека IPX/SPX.

Алгоритмы состояния связей обеспечивают каждый маршрутизатор информацией, достаточной для построения точного графа связей составной сети. Все маршрутизаторы работают на основании одинаковых графов, что делает процесс маршрутизации более устойчивым к изменениям конфигурации. Вершинами графа являются как маршрутизаторы, так и объединяемыми ими сети. Распространяемая по сети информации состоит из описания связей типов: маршрутизатор – маршрутизатор, маршрутизатор – сеть. Чтобы понять, в каком состоянии находятся линии связей, подключенные к его портам, маршрутизатор периодически обменивается короткими пакетами HELLO со своими ближайшими соседями. Этот служебный трафик также засоряет сеть, но не в такой степени как RIP-пакеты, поскольку пакеты HELLO имеют намного меньший объем. Примером протокола, работа которого основана на алгоритме состояния связей, является второй протокол OSPF стека TCP/IP.