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

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

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

Современные протоколы маршрутизации делятся на две группы: протоколы типа «вектор-расстояние» и протоколы типа «состояние канала».

В протоколах типа «вектор-расстояние» каждый маршрутизатор рассылает список адресов доступных ему сетей («векторов»), с каждым из которых связано параметр «расстояния» (например, количество маршрутизаторов до этой сети, значение, основанное на производительности канала и т.п.). Основным представителем протоколов данной группы является протокол RIP (Routing Information Protocol, протокол маршрутной информации).

Протоколы типа «состояние канала» основаны на ином принципе. Маршрутизаторы обмениваются между собой топологической информацией о связях в сети: какие маршрутизаторы с какими сетями связаны. В результате каждый маршрутизатор имеет полное представление о структуре сети (причем это представление будет одинаковым для всех), на основе которого вычисляет собственную оптимальную таблицу маршрутизации. Протоколом этой группы является протокол OSPF (Open Shortest Path First, «открой кратчайший путь первым»).

Протокол RIP.

Протокол RIP (Routing Information Protocol, протокол маршрутной информации) является наиболее простым протоколом динамической маршрутизации. Он относится к протоколам типа «вектор-расстояние».

Под вектором протокол RIP определяет IP-адреса сетей, а расстояние измеряется в переходах («хопах», hope) – количестве маршрутизаторов, которое должен пройти пакет, чтобы достичь указанной сети. Следует отметить, что максимальное значение расстояния для протокола RIP равно 15, значение 16 трактуется особым образом «сеть недостижима». Это определило основной недостаток протокола – он оказывается неприменимым в больших сетях, где Возможны маршруты, превышающие 15 переходов.

Протокол RIP версии 1 имеет ряд существенных для практического использования недостатков. К числу важных проблем относятся следующие:

• Оцен ка расстояния только с учетом числа переходов. Протокол RIP не учитывает реальную производительность каналов связи, что может оказаться неэффективным в гетерогенных сетях, т.е. сетях, объединяющих каналы связи различного устройства, производительности, в которых используются разные сетевые технологии.
• Проблема медленной конвергенции . Маршрутизаторы, спользующие протокол RIP. Рассылают маршрутную информацию каждые 30 с, причем их работа не синхронизирована. В ситуации, когда некоторый маршрутизатор обнаружит, что какая-либо сеть стала недоступной, то в худшем случае (если проблема была выявлена сразу после очередной рассылки) он сообщит об это соседям через 30 с. Для соседних маршрутизаторов все будет происходить также. Это означает, что информация о недоступности какой-либо сети может распространятся маршрутизаторам в достаточно долго, очевидно, что сеть при этом будет находиться в нестабильном состоянии.
• Широковещательная рассылка таблиц маршрутизации . Протокол RIP изначально предполагал, что маршрутизаторы рассылают информацию в широковещательном режиме. Это означает, что отправленный пакет вынуждены получить и проанализировать на канальном, сетевом и транспортном уровне все компьютеры сети, в которую он направлен.

Частично указанные проблемы решаются в версии 2 (RIP2).

Протокол OSPF

Протокол OSPF (Routing (Open Shortest Path First, «открой кратчайший путь первым») является более новым протоколом динамической маршрутизации и относится к протоколам типа «состояние канала».

Функционирование протокола OSPF основано на использовании всеми маршрутизаторами единой базы данных, описывающей, как и с какими сетями связан каждый маршрутизатор. Описывая каждую связь, маршрутизаторы связы
вают с ней метрику – значение, характеризующее «качество» канала. Например, для сетей Ethernet со скоростью обмена 100 Мбит/с используется значение 1, а для коммутируемых соединений 56 Кбит/с – значение 1785. Это позволяет маршрутизаторам OSPF (в отличие от RIP, где все каналы равнозначны) учитывать реальную пропускную способность и выявлять эффективные маршруты. Важной особенностью протокола OSPF является то, что используется групповая, а не широковещательная рассылка.

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

Внутренний протокол маршрутизации RIP Этот протокол маршрутизации предназначен для сравнительно небольших и относительно однородных сетей (алгоритм Белмана - Форда). Протокол разработан в университете Калифорнии (Беркли), базируется на разработках фирмы Ксерокс и реализует те же принципы, что и программа маршрутизации routed, используемая в О C Unix (4BSD)

Протокол RIP должен быть способен обрабатывать три типа ошибок: Циклические маршруты. Так как в протоколе нет механизмов выявления замкнутых маршрутов, необходимо либо слепо верить партнерам, либо принимать меры для блокировки такой возможности. Для подавления нестабильностей RIP должен использовать малое значение максимально возможного числа шагов (

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

Значения кодов поля команда: Зарезервированы для внутренних целей sun microsystem. 5-6 Выключение режима трассировки (устарело);4 Включение режима трассировки (устарело);3 Отклик, содержащий информацию о расстояниях из маршрутной таблицы отправителя; 2 Запрос на получение частичной или полной маршрутной информации; 1 Значение Команд а

НЕДОСТАТКИ RIP: RIP не работает с адресами субсетей. Если нормальный 16-бит идентификатор ЭВМ класса B не равен 0, RIP не может определить является ли не нулевая часть cубсетевым ID, или полным IP- адресом. RIP требует много времени для восстановления связи после сбоя в маршрутизаторе (минуты). В процессе установления режима возможны циклы. Число шагов важный, но не единственный параметр маршрута, да и 15 шагов не предел для современных сетей.

Протокол OSPF (алгоритм Дикстры) Протокол OSPF (Open Shortest Pass First, RFC , RFC , алгоритмы предложены Дикстрой) является альтернативой RIP в качестве внутреннего протокола маршрутизации. OSPF представляет собой протокол состояния маршрута (в качестве метрики используется - коэффициент качества обслуживания). Каждый маршрутизатор обладает полной информацией о состоянии всех интерфейсов всех маршрутизаторов (переключателей) автономной системы. Протокол OSPF реализован в демоне маршрутизации gated, который поддерживает также RIP и внешний протокол маршрутизации BGP.

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

Преимущества OSPF: Для каждого адреса может быть несколько маршрутных таблиц, по одной на каждый вид IP-операции (TOS). Каждому интерфейсу присваивается безразмерная цена, учитывающая пропускную способность, время транспортировки сообщения. Для каждой IP- операции может быть присвоена своя цена (коэффициент качества). При существовании эквивалентных маршрутов OSFP распределяет поток равномерно по этим маршрутам. Поддерживается адресация субсетей (разные маски для разных маршрутов). При связи точка-точка не требуется IP-адрес для каждого из концов. (Экономия адресов!) Применение мультикастинга вместо широковещательных сообщений снижает загрузку не вовлеченных сегментов. Недостатки: Трудно получить информацию о предпочтительности каналов для узлов, поддерживающих другие протоколы, или со статической маршрутизацией. OSPF является лишь внутренним протоколом.

Внешний протокол BGP Протокол BGP (RFC-1267, BGP-3; RFC-1268; RFC-1467, BGP-4; , 1655) разработан компаниями IBM и CISCO. Главная цель BGP - сократить транзитный трафик. Но не всякая ЭВМ, использующая протокол BGP, является маршрутизатором, даже если она обменивается маршрутной информацией с пограничным маршрутизатором соседней автономной системы. BGP- маршрутизаторы обмениваются сообщениями об изменении маршрутов

Формат BGP-сообщений об изменениях маршрутов Поле маркер содержит 16 октетов и его содержимое может легко интерпретироваться получателем. Поле длина имеет два октета и определяет общую длину сообщения в октетах, включая заголовок. Поле тип представляет собой код разновидности сообщения и может принимать следующие значения: (еще жив)KEEPALIVE4 (внимание) NOTIFICATIO N 3 (изменить)UPDATE2 (открыть)OPEN1

Предусмотрены следующие разновидности кодов типа атрибута ORIGIN (код типа = 1) - стандартный обязательный атрибут, который определяет происхождение путевой информации. Генерируется автономной системой, которая является источником маршрутной информации. Значение атрибута в этом случае может принимать следующие значения: Incomplete - информация достижимости сетевого уровня получена каким-то иным способом. 2 EGP - информация достижимости сетевого уровня получена с помощью внешнего протокола маршрутизации; 1 IGP - информация достижимости сетевого уровня является внутренней по отношению к исходной автономной системе; 0 Описание Код атрибута

AS_sequence: уп" title="AS_PATH (код типа = 2) также является стандартным обязательным атрибутом, который составлен из совокупности сегментов пути. Каждый сегмент AS_PATH состоит из трех частей . AS_sequence: уп" class="link_thumb"> 22 AS_PATH (код типа = 2) также является стандартным обязательным атрибутом, который составлен из совокупности сегментов пути. Каждый сегмент AS_PATH состоит из трех частей. AS_sequence: упорядоченный набор маршрутов автономной системы в UPDATE-сообщении. 2 AS_set: неупорядоченный набор маршрутов в update сообщении; 1 Описание Код типа сегмента NEXT_HOP (код типа = 3) - стандартный обязательный атрибут, определяющий IP-адрес пограничного маршрутизатора, который должен рассматриваться как цель следующего шага на пути к точке назначения. MULTI_EXIT_DISC (код типа = 4) представляет собой опционный непереходной атрибут, который занимает 4 октета и является положительным целым числом. Величина этого атрибута может использоваться при выборе одного из нескольких путей к соседней автономной системе. LOCAL_PREF (код типа = 5) является опционным атрибутом, занимающим 4 октета. Он используется BGP-маршрутизатором, чтобы сообщить своим BGP-партнерам в своей собственной автономной системе степень предпочтения объявленного маршрута. ATOMIC_AGGREGATE (код типа = 6) представляет собой стандартный атрибут, который используется для информирования партнеров о выборе маршрута, обеспечивающего доступ к более широкому списку адресов. . AS_sequence: уп"> . AS_sequence: упорядоченный набор маршрутов автономной системы в UPDATE-сообщении. 2 AS_set: неупорядоченный набор маршрутов в update сообщении; 1 Описание Код типа сегмента NEXT_HOP (код типа = 3) - стандартный обязательный атрибут, определяющий IP-адрес пограничного маршрутизатора, который должен рассматриваться как цель следующего шага на пути к точке назначения. MULTI_EXIT_DISC (код типа = 4) представляет собой опционный непереходной атрибут, который занимает 4 октета и является положительным целым числом. Величина этого атрибута может использоваться при выборе одного из нескольких путей к соседней автономной системе. LOCAL_PREF (код типа = 5) является опционным атрибутом, занимающим 4 октета. Он используется BGP-маршрутизатором, чтобы сообщить своим BGP-партнерам в своей собственной автономной системе степень предпочтения объявленного маршрута. ATOMIC_AGGREGATE (код типа = 6) представляет собой стандартный атрибут, который используется для информирования партнеров о выборе маршрута, обеспечивающего доступ к более широкому списку адресов."> . AS_sequence: уп" title="AS_PATH (код типа = 2) также является стандартным обязательным атрибутом, который составлен из совокупности сегментов пути. Каждый сегмент AS_PATH состоит из трех частей. AS_sequence: уп"> title="AS_PATH (код типа = 2) также является стандартным обязательным атрибутом, который составлен из совокупности сегментов пути. Каждый сегмент AS_PATH состоит из трех частей . AS_sequence: уп">

Маршрутная база данных BGP состоит из трех частей: Содержит информацию, которую локальный BGP- маршрутизатор отобрал для рассылки соседям с помощью UPDATE-сообщений. ADJ- RIBS- OUT: 3. Содержит локальную маршрутную информацию, которую BGP-маршрутизатор отобрал, руководствуясь маршрутной политикой, из ADJ-RIBS-IN. LOC-RIB:2. Запоминает маршрутную информацию, которая получена из update-сообщений. Это список маршрутов, из которого можно выбирать. (policy information base - PIB). ADJ- RIBS- IN: 1.

Особенности BGP: BGP отличается от RIP и OSPF тем, что использует TCP в качестве транспортного протокола. ЭВМ, использующая BGP, не обязательно является маршрутизатором. Сообщения обрабатываются только после того, как они полностью получены. BGP является протоколом, ориентирующимся на вектор расстояния. BGP регулярно посылает соседям TCP-сообщения, подтверждающие, что узел жив. Если два BGP-маршрутизатора попытаются установить связь друг с другом одновременно, такая ситуация называется столкновением, одна из связей должна быть ликвидирована. При установлении связи маршрутизаторов сначала делается попытка реализовать высший из протоколов, если один из них не поддерживает эту версию, номер версии понижается.

Маршрутизаторы объединяют сегменты сетей или отдельные локальные сети в составную (распределенную) сеть. Маршрутизаторы функционируют в дейтаграммных сетях с коммутацией пакетов, где все возможные маршруты уже существуют. Поэтому пакету нужно лишь выбрать наилучший путь, на основе метрики протокола маршрутизации. Процесс прокладывания пути производится последовательно от одного маршрутизатора к другому. Этот процесс маршрутизации (routing ) является функцией Уровня 3 модели OSI. При прокладывании пути пакета маршрутизатор анализирует сетевой адрес узла назначения, заданный в заголовке пакета, вычленяет из него адрес сети, чтобы идентифицировать сеть адресата в пределах сети Интернет. Адреса сетей назначения хранятся в таблице маршрутизации. Поэтому маршрутизатор должен создавать и поддерживать таблицы маршрутизации, а также извещать другие маршрутизаторы о всех известных ему изменениях в топологии сети.

Совокупность сетей, представленных набором маршрутизаторов под общим административным управлением, образует автономную систему (рис. 9.1). Автономные системы нумеруются и в некоторых протоколах (IGRP, EIGRP) эти номера используются.

Рис. 9.1. Взаимодействие автономных систем

Маршрутизацию, т.е. прокладывание маршрута внутри автономных систем, осуществляют маршрутизирующие протоколы внутреннего шлюза (Interior Gateway Protocols - IGP s), к которым относятся RIP, RIPv2, IGRP, EIGRP, OSPF, Intermediate System-to-Intermediate System (IS-IS). Маршрутизацию между автономными системами производят протоколы внешнего шлюза (Exterior Gateway Protocols - EGP s). Примером протокола внешнего шлюза является протокол BGP, который работает на граничных маршрутизаторах автономных систем (рис. 9.1).

Маршрутизирующие протоколы, работающие внутри автономных систем, в свою очередь, подразделяются на протоколы вектора расстояния (distance - vector ) и протоколы состояния канала (link - state ). Протоколы distance-vector определяют расстояние и направление, т.е. вектор некоторого соединения в составной сети. Расстояние может быть выражено в количестве маршрутизаторов или переходов (hop count ) в соединении на пути от узла источника к адресату назначения или других значениях метрики. При использовании алгоритма distance-vector маршрутизаторы посылают всю или часть таблицы маршрутизации соседним (смежным) маршрутизаторам через определенные интервалы времени. В таких протоколах как RIP, обмен обновлениями (update ) или модификациями происходит, даже если в сети нет никаких изменений , на что затрачивается довольно большая часть полосы пропускания. Получив обновление маршрутной информации, маршрутизатор может заново вычислить все известные пути и произвести изменения в таблице маршрутизации.

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

Таким образом, маршрутизатор ретранслирует пакет, используя две основных функции:

- функцию определения пути с использованием сетевой части адреса,

- функцию коммутации , принимая пакет на входной интерфейс и продвигая его на выходной интерфейс, который определяется функцией определения пути.

Определение наиболее рационального (оптимального) пути производится маршрутизатором на основе некоторого критерия – метрики . Значение метрики используется при оценке возможных путей. Метрика может включать разные параметры, например:

Полосу пропускания,

Задержку,

Надежность,

Загрузку,

Обобщенную стоимость и другие параметры сетевого соединения.

Маршрутизаторы могут использовать один какой-то параметр или комбинацию параметров метрики при выборе оптимального маршрута.

Маршрутная информация может быть сконфигурирована сетевым администратором – при этом реализуется статическая маршрутизация . Динамическая маршрутизация реализуется протоколами маршрутизации, когда маршрутная информация собирается в ходе динамического процесса обмена обновлениями (модификациями) между маршрутизаторами, который выполняется в сети.

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

RIP (Routing Information Protocol)

IGRP (Interior Gateway Routing Protocol)

EIGRP (Enhanced Interior Gateway Routing Protocol)

OSPF (Open Shortest Path First).

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

Протоколы и устройства Уровня 2 и Уровня 3 модели OSI постоянно взаимодействуют при передаче данных по сети (рис. 9.2).

Рис.9.2. Взаимодействие протоколов и устройств

Это проявляется в виде взаимодействия таблиц ARP (табл.9.1), функционирующих на Уровне 2, и таблиц маршрутизации протоколов Уровня 3 модели OSI. Каждый компьютер и порт маршрутизатора поддерживает таблицы ARP, каждая строка которых содержит пару соответствующих IP- и MAC-адресов и функционируют только в пределах широковещательного домена, т.е. в пределах сети или подсети.

Таблица 9.1

Таблица ARP маршрутизатора А

	МАС адрес

Таблицы маршрутизации позволяют передавать пакеты за пределы широковещательного домена. Строки таблицы маршрутизации (табл.9.2) с меткой С отображают непосредственно присоединенные к маршрутизатору сети, а с меткой R – сети, путь к которым проложен с помощью протокола RIP. В каждой строке также представлены: расстояние до сети назначения, выраженное в количестве переходов между маршрутизаторами (hop); выходной интерфейс маршрутизатора на пути к сети назначения.

Таблица 9.2

Таблица маршрутизации маршрутизатора А

	Адрес сети назначения	Число переходов	Интерфейс

На Уровне 2 модели OSI функционируют коммутаторы, которые соединяют сегменты одной локальной сети или подсети, используя МАС-адреса. Для соединения с хостами вне локальной сети коммутатор продвигает кадр на маршрутизатор. Хост использует МАС-адрес входного интерфейса маршрутизатора как адрес назначения. Неизвестный МАС-адрес хост узнает из таблицы ARP. Маршрутизатор cверяет IP-адрес сети назначения с таблицей маршрутизации и продвигает пакет на выходной порт в соответствие с найденной строкой таблицы маршрутизации.

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

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

Тип протокола , который идентифицирует протокол маршрутизации, который создавал каждый вход (строку) таблицы.

Следующий переход (Next-hop) – указывает адрес входного интерфейса следующего маршрутизатора на пути к адресату назначения.

Метрику , которая различается для разные протоколов.

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

Маршрутизаторы поддерживают таблицы маршрутизации через обмен обновлениями или модификациями (update ). Некоторые протоколы передают обновления периодически, например, протоколы RIP, IGRP. Другие протоколы посылают модификации только когда происходят изменения в сетевой топологии, например, OSPF, EIGRP.

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

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

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

Полоса пропускания (Bandwidth) – способность соединения передавать данные с некоторой скоростью, например, соединения сети Ethernet предпочтительней линии со скоростью 64 кбит/с.

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

Надежность (Reliability) – надежность определяется интенсивностью ошибок на каждом сетевом соединении.

Количество переходов (Hop count) – это количество маршрутизаторов, через которые пакет должен пройти на пути к адресату назначения (число переходов от маршрутизатора к маршрутизатору).

Стоимость (Cost) –это обобщенный параметр затрат на передачу пакета к адресату назначения. Обычно стоимость имеет произвольное значение, назначенное администратором. Часто стоимость базируется на полосе пропускания.

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

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

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

Статические алгоритмы и простая маршрутизация

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

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

В первом случае все записи в таблице маршрутизации статические. Администратор сети сам решает, на какие маршрутизаторы надо передавать пакеты с теми или иными адресами, и заносит соответствующие записи в таблицу маршрутизации вручную (например, с помощью утилиты route ОС UNIX или Windows NT).

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

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

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

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

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

АДАПТИВНАЯ МАРШРУТИЗАЦИЯ

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

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

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

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

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

• дистанционно-векторные алгоритмы (Distance Vector Algorithm, DVA);
• алгоритмы состояния каналов (Link State Algorithm, LSA).

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

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

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

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

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

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

СТРУКТУРА INTERNET

Большинство протоколов маршрутизации, применяемых в современных сетях с коммутацией пакетов, появилось благодаря Internet и его предшественницы - сети ARPANET. Для того чтобы понять их назначение и особенности, полезно познакомится со структурой сети Internet, которая наложила отпечаток на терминологию и типы протоколов.

Internet изначально строился как сеть, объединяющая большое количество независимых систем. С самого начала в его структуре выделяли магистральную сеть (core backbone network), а подключенные к магистрали сети рассматривались как автономные системы (autonomous system). Магистраль и каждая из автономных систем имели свои собственные административное управление и протоколы маршрутизации. Необходимо подчеркнуть, что деление на автономные системы не связано прямо с делением Internet на сети и домены имен. Автономная система объединяет сети, где маршрутизация осуществляется под общим административным руководством одной организации, а домен имен - единый для компьютеров (возможно, принадлежащих разным сетям), в которых назначение уникальных символьных имен происходит под таким же руководством. Естественно, область действия автономной системы и домена имен могут в частном случае совпадать, если одна организация выполняет обе указанные функции.

Маршрутизаторы, применяемые для формирования сетей и подсетей внутри автономной системы, называются внутренними шлюзами (interior gateway), а те, с помощью которых автономные системы подключаются к магистрали сети, - внешними шлюзами (exterior gateway). Магистраль сети также является автономной системой. Все автономные системы имеют уникальный 16-разрядный номер, который присваивается централизованно соответствующим административным органом Internet.

Используемые внутри автономных систем протоколы маршрутизации называются протоколами внутренних шлюзов (Interior Gateway Protocol, IGP), а протоколы обмена маршрутной информацией между внешними шлюзами и шлюзами магистральной сети - протоколами внешних шлюзов (Exterior Gateway Protocol, EGP). Внутри магистральной сети также может функционировать любой собственный внутренний протокол IGP.

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

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

Техника бесклассовой маршрутизации CIDR может значительно сократить объемы маршрутной информации, передаваемой между автономными системами. Так, если все сети внутри некоторой автономной системы начинаются с общего префикса, скажем 194.27.0.0/16, то внешний шлюз автономной системы должен делать объявления только об этом адресе, не сообщая отдельно о существовании внутри данной автономной системы, например сети 194.27.32.0/19 или 194.27.40.0/21, так как эти адреса агрегируются в адресе 194.27.0.0/16.

Приведенная на Рисунке 1 структура Internet с единственной магистралью была таковой достаточно долго, поэтому специально для нее был разработан протокол обмена маршрутной информацией между AS, названный EGP. Однако по мере развития сетей провайдеров услуг структура Internet стала гораздо более сложной, с произвольным характером связей между автономными системами. Поэтому протокол EGP уступил место протоколу BGP, который позволяет распознать наличие петель между автономными системами и исключить их из межсистемных маршрутов. Протоколы EGP и BGP используются провайдерами услуг Internet только на внешних шлюзах автономных систем. На маршрутизаторах корпоративных сетей работают внутренние протоколы маршрутизации, такие, как RIP и OSPF.

RIP и OSPF

Протокол RIP (Routing Information Protocol) - внутренний протокол маршрутизации дистанционно-векторного типа. Это один из наиболее ранних протоколов обмена маршрутной информацией, до сих пор чрезвычайно распространенный ввиду простоты реализации. Кроме варианта RIP для сетей TCP/IP версия RIP имеется и для сетей IPX/SPX компании Novell. Протокол RIP для IP представлен двумя версиями: первой и второй. RIP v.1 не поддерживает маски, т. е. он распространяет между маршрутизаторами только информацию о номерах сетей и расстояниях до них, а информацию о масках этих сетей не рассылает, считая, что все адреса принадлежат к стандартным классам A, B или С. Протокол RIP v.2 передает информацию о масках сетей, поэтому он в большей степени соответствует требованиям сегодняшнего дня.

Протокол OSPF (Open Shortest Path First, открытый протокол «первоочередного выбора кратчайшего пути») принят в 1991 г. Будучи реализацией алгоритма состояния каналов, он разрабатывался в расчете на применение в крупных гетерогенных сетях. Вычислительная сложность протокола OSPF быстро растет с увеличением размерности сети, т. е. увеличением количества сетей, маршрутизаторов и связей между ними. Для решения этой проблемы в протоколе OSPF вводится понятие «область» сети (area) (не следует путать с автономной системой Internet). Маршрутизаторы, принадлежащие некоторой области, строят граф связей только для нее, что сокращает размерность сети. Между областями информация о связях не передается, а пограничные маршрутизаторы обмениваются определенной информацией об адресах сетей, находящихся в каждой из областей, и о расстоянии от пограничного маршрутизатора до каждой сети. При передаче пакетов между областями выбирается один из пограничных маршрутизаторов области, а именно тот, у которого расстояние до нужной сети меньше. При передаче адресов в другую область маршрутизаторы OSPF агрегируют несколько адресов общим префиксом в один.

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

Наталья Олифер - обозреватель LAN. С ней можно связаться по адресу: