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

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

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

Эти протоколы делятся на следующие группы:

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

2. С маршрутизацией от источника (Sonra Routing). Это многошаговый подход. Узел-источник задает в отправляемом пакете полный маршрут, через все промежуточные узлы. При таком подходе не нужны таблицы маршрутизации для промежуточных узлов, их работа ускоряется, но возрастает нагрузка на конечные узлы. Этот способ трудно применять в больших сетях.

Одношаговые алгоритмы в зависимости от способа формирования таблиц делятся на три класса:

1. Алгоритмы фиксированной (статической) маршрутизации.

2. Алгоритмы простой маршрутизации.

3. Алгоритмы адаптивной (или динамической) маршрутизации.

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

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

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

2. Лавинная маршрутизация, когда пакет широковещательно посылается по всем возможным направлениям, кроме исходного направления (аналогично обработке мостами кадров с неизвестным адресом);

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

Все описанные алгоритмы не подходят для больших сетей.

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

Адаптивные алгоритмы обычно носят распределенный характер, хотя в последнее время наметилась тенденция использовать так называемые серверы маршрутов. Сервер маршрутов собирает информацию, а затем раздает ее по запросам маршрутизаторам, которые освобождаются в этом случае от функции создания таблиц маршрутизации, либо создают только части этих таблиц. Появились специальные протоколы взаимодействия маршрутизаторов с серверами маршрутов, например, NHRP (Next Hop Resolution Protocol).

Адаптивные протоколы в свою очередь делятся на:

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

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

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

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

Наиболее распространенный протокол описанного типа – RIP, существующий в версиях для протоколов IP и IPX.

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

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

Чтобы понять, в каком состоянии находятся линии связи, подключенные к его портам, маршрутизатор периодически обменивается короткими пакетами HELLO со своими ближайшими соседями. Этот служебный трафик также засоряет сеть, но не в такой степени, как, например, пакеты протокола RIP, так как пакеты HELLO имеют намного меньший объем.

Протоколы, использующие алгоритм состояния сетей – это OSPF (Open Shortest Path First) стека TCP/IP, IS-IS (Intermediate System to Intermediate System) стека OSI, и недавно реализованный протокол NLSP стека Novell.