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

 

1.6. Маршруты по умолчанию

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

 

 

Рис.1.3. Алгоритм Дикстры

 

Если сеть включает в  себя субсети, то для каждой записи в маршрутной таблице производится побитная операция <И> для ID и маски  субсети. Если результат этой операции совпадет с содержимым адресного  поля сети, дейтограмма посылается серверу субсети. На практике при наличии субсетей в маршрутную таблицу добавляются соответствующие записи с масками и адресами сетей.

1.7. Опорные сети и автономные системы

Одна из базовых идей маршрутизации заключается в  том, чтобы сконцентрировать маршрутную информацию в ограниченном числе (в идеале в одном) узловых маршрутизаторов-диспетчеров. Эта замечательная идея ведет к заметному увеличению числа шагов при пересылке пакетов. Оптимизировать решение позволяет backbone (опорная сеть), к которой подключаются узловые маршрутизаторы. Любая AS подключается к backbone через узловой маршрутизатор.

"Прозрачные" backbone не работают  с адресами класса С (все  объекты такой сети должны  иметь один адрес, а для c-класса  число объектов слишком ограничено). "Прозрачные" мосты трудно диагностировать, так как они не следуют протоколу ICMP (команда ping не работает, в последнее время такие объекты снабжаются snmp-поддержкой). За то они позволяют перераспределять нагрузку через несколько маршрутизаторов, что невозможно для большинства протоколов.

 

 

Рис. 1.4. Маршрутизация между двумя  сетями

 

В примере, приведенном  на рис. 1.4, задача маршрутизации достаточно сложна. ЭВМ1,2 и ЭВМ6,1 можно связать  многими путями: ЭВМ1,2 - GW1 - ЭВМ6,1; ЭВМ1,2 - GW2 - ЭВМ6,1; ЭВМ1,2 - GW3 - ЭВМ6,1; ЭВМ1,2 - GW4 - ЭВМ6,1; ЭВМ1,2 - GW1 - GW2 - GW3 - ЭВМ6,1; и т.д. Трафик между двумя географически близкими узлами должен направляться кратчайшим путем, вне зависимости от направления глобальных потоков. Так ЭВМ1,2 и ЭВМ1,1 должны соединяться через GW1. Маршрутизация через опорные сети (backbone) требует индивидуального подхода для каждого узла. Администраторы опорных сетей должны согласовывать свои принципы маршрутизации. Ситуация, когда узел не владеет исчерпывающей маршрутной информацией, в сочетании с использованием маршрутов по умолчанию может привести к зацикливанию пакетов (см. рис. 1.5). Например, если маршрут по умолчанию в GW1 указывает на GW2, а в GW2 на GW1, то пакет с несуществующим адресом будет циркулировать между GW1 и GW2 пока не истечет ttl (время жизни пакета), полностью блокируя канал. По этой причине желательно иметь полную таблицу маршрутизации, и, если не вынуждают обстоятельства, избегать использования маршрутов по умолчанию.

 

 

Рис. 1.5. Зацикливание пакетов

 

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

Динамические протоколы (обычно используются именно они, наиболее известным разработчиком является компания CISCO):

В маршрутизаторе с динамическим протоколом (например, BGP-4) резидентно загруженная  программа-драйвер изменяет таблицы  маршрутизации на основе информации, полученной от соседних маршрутизаторов. В ЭВМ, работающей под UNIX и выполняющей функции маршрутизатора, эту задачу часто решает резидентная программа gated или routed (демон). Последняя - поддерживает только внутренние протоколы маршрутизации.

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

1.8. Внешние и внутренние протоколы маршрутизации

Может возникнуть вопрос, откуда возникло ограничение на число внешних и внутренних протоколов маршрутизации? Главная причина - согласование метрик сетевых каналов. С внешними протоколами все относительно просто. Во-первых, их мало, во-вторых, практически все они используют для оценки каналов вектор расстояния, что потенциально может вообще снять рассматриваемое ограничение. А как быть с внутренней маршрутизацией? Ведь существуют протоколы, базирующиеся на векторе расстояния (RIP), и на состоянии канала (OSPF или IGRP). Предположим, что в одной зоне сети работает RIP, где канал оценивается числом шагов до цели, а в другой - OSPF с оценкой состояния канала, выполненной администратором сети. Если маршрут содержит фрагменты пути, пролегающие через обе указанные зоны, возникает проблема оценки такого пути. Как сложить метрики этих участков, ведь они несовместимы? В принципе задача имеет решение, для этого на границах зон с разными протоколами маршрутизации размещаются специальные маршрутизаторы, которые оптимизируют пути для каждого из протоколов (и зон) независимо. Но и в этом случае возможны трудно разрешимые ситуации. Один из таких вариантов показан на рис. 1.6.

 

 

Рис. 1.6. Применение различных  протоколов маршрутизации

 

Пусть на рисунке 1.6. в  сетевых зонах, обозначенных кругами  используется протокол RIP, а в остальном пространстве - OSPF. ЭВМ обозначены пятиугольниками, внутренние маршрутизаторы прямоугольниками, а окрашенные прямоугольники отмечают пограничные маршрутизаторы зон. Любые маршруты из зоны А в зону Б проблем не вызовут, так как внутри зоны маршруты оптимизируются RIP, а между зонами - протоколом OSPF. Рассмотрим прокладку маршрута из зоны Б в зону В. Здесь следует рассмотреть варианты пути через зоны Г и Д. Важно то, что при выборе оптимального пути придется как-то учитывать метрики как OSPF-части пути, так и фрагменты транзитного пути внутри зон. При этом надо принять решение, с какими весами складывать метрики разных протоколов. Эта проблема снимается, если каждая зона имеет только один пограничный маршрутизатор. Маршрут прокладывается между пограничными маршрутизаторами, а различие маршрутов внутри зон игнорируется. Кстати именно эта логика лежит в основе рекомендации для автономной системы иметь только один пограничный маршрутизатор. Поясним это на примере, показанном на рис. 1.7.

 

 

Рис. 1.7. Автономные системы  и пограничные маршрутизаторы

 

Рассмотрим процедуру  выбора пути от ЭВМ-1 к ЭВМ-2 из автономной системы AS1 в автономную систему AS2. Имеются метрики, характеризующие  путь до маршрутизаторов GW1 и GW2 (M1 и M2). Существует метрика пути от GW1 и GW2 до автономной системы AS2 М3 и М4 (они совсем необязательно равны между собой). В результате мы имеем характеристики двух путей между означенными машинами М1, М3 и М2, М4). Если внутренним протоколом маршрутизации является OSPF или IGMP, то складывать М1 и М4 (соответственно М2 и М4) нельзя, так как в одном случае (М1, М2) это характеристики состояния каналов (администратор назначил их, например, равными 35 и 55), а во втором (М3,М4) - это число шагов до автономной системы AS2 (пусть они равны, например, 6 и 4). Задача сопоставления метрик в этом простом случае может оказаться не по плечу даже суперЭВМ.

Если бы у AS1 был только один пограничный шлюз (например, GW1), то задача решалась бы автоматически. Другим подходом может быть деление всего Интернет на две части, одна делается доступной только через GW1, а вторая - через GW2.

Любая автономная система (AS, система маршрутизаторов, ЭВМ  или сетей, имеющая единую политику маршрутизации) может выбрать свой собственный протокол маршрутизации.

Деликатной процедурой алгоритмов маршрутизации является рассылка маршрутной информации. Если предположить, что один маршрутизатор  получил пакет с новыми данными, а другой нет (потерялся или еще  не дошел), то эти два прибора будут  использовать разное представление о топологии сети, что может привести к циклам пакетов, осцилляции маршрутов и другим неприятностям. Первое, что приходит в голову для синхронизации маршрутной картины сети - это широковещательная рассылка маршрутных данных. При этом каждому пакету можно присваивать порядковый номер. Анализ этого номера позволяет маршрутизатору избавляться от пакетов дубликатов и от кадров с устаревшей информацией. Получив новый пакет, маршрутизатор переадресует его на все свои интерфейсы кроме того, через который он пришел. Такой алгоритм может встать в тупик в случае переполнения номера пакета. Допустим, после номера N придет пакет с номером 1. В этом случае он будет отброшен как дубликат ранее пришедшего или как кадр, несущий устаревшие данные. Если использовать 32-разрядные номера пакетов, при частоте рассылки один пакет в секунду переполнение счетчика произойдет более чем через 136 лет. Такая угроза вряд ли кого-то напугает.

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

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

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

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

Внутренний протокол маршрутизации IGP (Interior Gateway Protocol) определяет маршруты внутри автономной системы. Наиболее популярный IGP - RIP (Routing Information Protocol, RFC-1058), разработан Фордом, Фулкерсоном и Белманом (фирма XEROX) разработан в 1957-62 годах и использует в качестве метрики вектор расстояния. Протокол был базовым в рамках проекта ARPANET. В качестве метрики может выбираться время доступа, число пакетов в очереди, но обычно - это число шагов до места назначения. Если до цели имеется один промежуточный маршрутизатор, то число шагов считается равным 2. Расстояние до любого из соседей равно одному шагу. В этом протоколе всегда выбирается путь с наименьшим числом шагов до цели (наименьшее значение метрики). Маршрутизация на основе вектора расстояния в принципе позволяет получить положительный результат в любой ситуации, но она имеет одну особенность - процесс сходится быстро при обнаружении нового более короткого пути и работает крайне медленно при исчезновении пути.

Алгоритм вектора расстояния неявно предполагает, что все каналы имеют равную пропускную способность.

Существует более новый  протокол OSPF (Open Shortest Pass First, RFC-1131, -1245, -1247, -1253, -1584, -1850, -2328, -2740). базирующийся на оценках состояний каналов. Как во всех маршрутных протоколах, использующих состояние канала, многое зависит от того, как вычисляется метрика. Если определяющим фактором выбрать полосу пропускания канала, то при определенных обстоятельствах могут возникнуть трудно преодолимые проблемы. Рассмотрим топологию сети, показанную на рисунке 1.8.

 

 

Рис. 1.8. Пример топологии  сети, допускающей осцилляцию маршрутов

 

Здесь две субсети  А и Б соединены двумя каналами 1 и 2. Кружочками обозначены маршрутизаторы. Если в исходный момент времени основной поток между сетями протекает по каналу 2, он может оказаться перегружен, в то время как канал 1 получит меньшее значение метрики из-за отсутствия загрузки. При очередной оценке каналов будет принято решение переключить поток между сетями на канал 1. После этого будет перегружен канал 1 и так может повторяться до бесконечности. Такая ситуация называется осцилляцией маршрутов и ее желательно избегать. Маршрутные таблицы в маршрутизаторах актуализуются вдоль пути с заметными задержками и отнюдь не синхронно. Такие осцилляции могут в разы понизить пропускную способность сети, что необходимо учитывать, выбирая параметры протоколов маршрутизации.

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