6.8 Протоколы маршрутизации

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

1. Фиксированная маршрутизация;

2. Простая маршрутизация;

3. Адаптивная маршрутизация.

Результатом работы алгоритмов маршрутизации является таблица маршрутов, которая говорит о том, какому маршрутизатору, непосредственно связанному с данным, нужно передать пакет, чтобы достичь адрес сети назначения. Таблица маршрутов, использующей IP-адреса сетей, как правило, имеет три следующих поля:

1. Адрес сети назначения;

2. Номер выходного порта;

3. Расстояние до конечной сети.

Таблица используется при принятии решения о передаче пакета. Если в ней имеется несколько строк для одной и той же сети, то выбирается та, в которой расстояние до конечной сети меньше. Под расстоянием понимается любая метрика, используемая в соответствии с заданным в сетевом пакете классом сервиса. Это может быть время прохождения пакета по линиям связи, надежность линий связи, загруженность линий связи в данный момент времени и любая другая величина, определенная в сетевом протоколе.

В каждом маршрутизаторе существует порт, на который пакеты передаются по умолчанию, если адрес сети назначения не присутствует в явном виде в таблице. Обычно порт по умолчанию связан с магистралью сети, так что пакеты, поступив на магистраль, попадают в маршрутизатор, знающий их сеть назначения.

В сетях с простой топологией связей применяется алгоритм фиксированной маршрутизации, который основан на ручном составлении таблицы маршрутизации администратором сети. Алгоритм эффективно работает также для магистралей крупных сетей, так как сама магистраль может иметь простую структуру с очевидными наилучшими путями следования пакетов в подсети, присоединенные к магистрали.

Алгоритмы простой маршрутизации, разделяются на три типа:

1. Случайная маршрутизация - пакеты передаются в любом, случайном направлении, кроме исходного;

2. Лавинная маршрутизация - пакеты передаются во всех направлениях, кроме исходного;

3. Маршрутизация по опыту - таблицы маршрутизации составляются на основании анализа пакетов, проходящих через маршрутизатор.

Основным видом маршрутизации в сетях со сложной топологией является алгоритм адаптивной маршрутизации, который основан на периодическом обмене маршрутизаторами специальной топологической информацией о сегментах сети, а также о связях между маршрутизаторами. Такие протоколы позволяют маршрутизаторам собирать информацию о топологии связей в сети, адаптивно отрабатывая все изменения конфигурации. Особенность состоит в том, что в сети отсутствует выделенный маршрутизатор, который собирает и обобщает топологическую информацию, эта работа распределена между всеми маршрутизаторами. Протоколы адаптивной маршрутизации, основаны на двух группах алгоритмов - дистанционно-векторных алгоритмах (Distance Vector Algorithms, DVA) и алгоритмах состояния связей (Link State Algorithms, LSA).

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

Алгоритмы состояния связей обеспечивают каждый маршрутизатор информацией, достаточной для построения точного графа связей сети. Все маршрутизаторы работают на основании одинаковых графов, что делает процесс маршрутизации более устойчивым к изменениям конфигурации. Широковещательная рассылка используется здесь только при изменениях состояния связей. Для того чтобы понять, в каком состоянии находятся линии связи, подключенные к его портам, маршрутизатор периодически обменивается короткими пакетами со своими ближайшими соседями. Этот трафик также широковещательный, но он циркулирует только между соседями и не так засоряет сеть.