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

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

Для автоматического построения таблиц маршрутизации маршрутизаторы об­мениваются информацией о топологии составной сети в соответствии со специаль­ным служебным протоколом. Протоколы этого типа называются протоколами маршрутизации (или маршрутизирующими протоколами). Протоколы маршрути­зации (например, RIP, OSPF, NLSP) следует отличать от собственно сетевых про­токолов (например, IP, IPX). И те и другие выполняют функции сетевого уровня модели OSI — участвуют в доставке пакетов адресату через разнородную состав­ную сеть. Но в то время как первые собирают и передают по сети чисто служебную информацию, вторые предназначены для передачи пользовательских данных, как это делают протоколы канального уровня. Протоколы маршрутизации используют сетевые протоколы как транспортное средство. При обмене маршрутной информа­цией пакеты протокола маршрутизации помещаются в поле данных пакетов сете­вого уровня или даже транспортного уровня, поэтому с точки зрения вложенности пакетов протоколы маршрутизации формально следовало бы отнести к более вы­сокому уровню, чем сетевой.

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

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

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

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

Существует и прямо противоположный, многошаговый подход — маршрутиза­ция от источника (Source Routing). В соответствии с ним узел-источник задает в отправляемом в сеть пакете полный маршрут его следования через все промежу­точные маршрутизаторы. При использовании многошаговой маршрутизации нет необходимости строить и анализировать таблицы маршрутизации. Это ускоряет прохождение пакета по сети, разгружает маршрутизаторы, но при этом большая нагрузка ложится на конечные узлы. Эта схема в вычислительных сетях применя­ется сегодня гораздо реже, чем схема распределенной одношаговой маршрутиза­ции. Однако в новой версии протокола IP наряду с классической одношаговой маршрутизацией будет разрешена и маршрутизация от источника.

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

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

• алгоритмы простой маршрутизации;

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

В алгоритмах фиксированной маршрутизации все записи в таблице маршрути­зации являются статическими. Администратор сети сам решает, на какие маршру­тизаторы надо передавать пакеты с теми или иными адресами, и вручную (например, с помощью утилиты route ОС Unix или Windows NT) заносит соответствующие записи в таблицу маршрутизации. Таблица, как правило, создается в процессе за­грузки, в дальнейшем она используется без изменений до тех пор, пока ее содержи­мое не будет отредактировано вручную. Такие исправления могут понадобиться, например, если в сети отказывает какой-либо маршрутизатор и его функции воз­лагаются на другой маршрутизатор. Различают одномаршрутные таблицы, в которых для каждого адресата задан один путь, и многомаршрутные таблицы, определяю­щие несколько альтернативных путей для каждого адресата. В многомаршрутных таблицах должно быть задано правило выбора одного из маршрутов. Чаще всего один путь является основным, а остальные — резервными. Понятно, что алгоритм фиксированной маршрутизации с его ручным способом формирования таблиц маршрутизации приемлем только в небольших сетях с простой топологией. Одна­ко этот алгоритм может быть эффективно использован и для работы на магистра­лях крупных сетей, так как сама магистраль может иметь простую структуру с очевидными наилучшими путями следования пакетов в подсети, присоединенные к магистрали.

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

• случайная маршрутизация, когда прибывший пакет посылается в первом по­павшем случайном направлении, кроме исходного;

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

• маршрутизация по предыдущему опыту, когда выбор маршрута осуществляется

по таблице, но таблица строится по принципу моста путем анализа адресных

полей пакетов, появляющихся на входных портах.

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

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

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

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

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

• дистанционно-векторные алгоритмы (Distance Vector Algorithms, DVA);

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

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

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

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

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

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

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