Вопрос 13) Протоколы маршрутизации

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

Алгоритм Беллмана-Форда (также известный как алгоритм Форда-Фулкерсона) был положен в основу первого протокола маршрутизации, созданного для сети ARPANET. Так называемые протоколы вектора расстояния (distance vector protocols), такие, как RIP, IGRP, BGP, используют те же принципы. В 1979 году на смену протоколу вектора расстояний пришел протокол состояния канала (link state protocol), ставший основным в ARPANET. Современные протоколы состояния канала включают OSPF, IS-IS, NLSP и др.

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

Желающие ознакомиться с деталями реализации конкретных протоколов могут обратиться к ресурсам Internet (http://www.lanmag.ru, http://www.citforum.ru), мы же сосредоточимся на общих принципах, легших сегодня в основу протоколов маршрутизации.

В порядке старшинства мы начнем с протоколов вектора расстояний.

ПОРОЧНЫЙ КРУГ

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

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

В качестве примера мы рассмотрим сеть (см. Рисунок 1) из нескольких последовательно соединенных маршрутизаторов, где метрикой является число транзитных узлов на пути к точке назначения (как в протоколе RIP).

Рисунок 1. Распространение "хорошей" новости в сети.

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

Во время первого обмена узел B узнает, что A заработал и вносит в свою таблицу маршрутизации "1" как расстояние до A; все остальные узлы в этот момент по-прежнему считают A недоступным. При следующем обмене, спустя несколько секунд, узел C также узнает о появлении маршрутизатора A. В результате последовательности таких обменов информация достигнет и узла E, для которого стоимость маршрута до А будет "4".

Таким образом, для сети с максимальной длиной маршрута N сообщение о новом маршрутизаторе дойдет до самого удаленного узла в сети через N-1 циклов обмена таблицами маршрутизации. На этом этапе никаких проблем не возникает.

Теперь мы рассмотрим обратный случай (см. Рисунок 2), когда узел А перестает работать вследствие сбоя. При очередном обмене (мы будем считать его первым в этой серии) узел В не получает никакого сообщения от молчащего маршрутизатора А. Это верный сигнал о том, что у А возникли проблемы, и информацию о нем необходимо удалить из таблицы. Однако в то же самое время узел C сообщает, что ему известен путь до А и стоимость этого пути "2". Тот факт, что путь до А, объявленный узлом C, проходит через сам B (т. е. образуется петля), ускользает от внимания маршрутизатора, и он заносит в таблицу путь до неработающего А стоимостью "3".

Рисунок 2. Проблема возрастания до бесконечности.

Во время следующего обмена C замечает, что оба его соседа рекламируют путь до A стоимостью "3", и немедленно делает поправки в своей таблице. Теперь длина пути от С до A - "4". Если этот процесс не остановить, то он может продолжаться до бесконечности, и никто так и не узнает, что маршрутизатор А давно вышел из строя. Соответственно данные к А будут посылаться и дальше.

Эта проблема алгоритма вектора расстояний получила название проблемы возрастания до бесконечности (count-to-infinity problem). Она является основной причиной задания ограничений на максимальную длину пути во всех протоколах вектора расстояния.

Протокол RIP, например, считает маршрут длиной более чем в 15 транзитных узлов бесконечным. Такой путь будет немедленно удален из таблицы маршрутизации. Т. е. в последнем примере узел B поймет, что узел А недоступен, когда получит объявление пути до А со стоимостью "15". К сожалению, такая процедура занимает слишком много времени.

ЧТО ТАМ, ЗА ГОРИЗОНТОМ?

Для предотвращения образования ложных маршрутов используется несколько методов, один из них - метод расщепления горизонта (split-horizon). Данное правило не так сложно, как может показаться из названия: "Если известно, что путь до узла X лежит через соседний узел Y, то узлу Y не надо посылать объявления маршрута до X".

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

Таблица 1. Значения поля TOS для различных приложений

Приложение	Минимальная задержка	Максимальная полоса	Максимальная надежность	Минимальная стоимость
Telnet/Rlogin
FTP:
Команды
Данные
SMTP:
Команды
Данные
DNS:
Запрос TCP
Запрос UDP

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

Рисунок 3. Пример ситуации, когда правило расщепления горизонта не действует.

Рассмотрим пример сети с избыточной топологией (см. Рисунок 3). В начальный момент времени А и B знают, что расстояние до узла D равно "2". После выхода D из строя маршрутизатор C, не получив от D сообщения, определяет, что узел D недоступен. А и В продолжают считать D доступным, но правило расщепления горизонта запрещает им сообщать эту ложную информацию маршрутизатору С. При следующем обмене C уведомляет A и B о недоступности D. Но одновременно с этим узел А получает от В сообщение о пути до D стоимостью "2", а узел В получает аналогичное сообщение от А.

Информация об аварии на D не будет услышана. Проблема возрастания до бесконечности возникла вновь.

ДОВЕРЯЙ, НО ПРОВЕРЯЙ

В рассмотренном выше примере маршрутизаторы A и B не смогли корректно определить отказ узла D. Не помогло и правило расщепления горизонта. Подобную проблему помогает решить метод временного отказа от приема сообщений (hold-down), используемый современными протоколами вектора расстояний.

Правило отказа от приема запрещает маршрутизатору, получившему сообщение об отказе узла, принимать объявления маршрута до этого узла в течение некоторого времени. Получив от C уведомление о недоступности D, маршрутизатор А не должен доверять сообщению узла B, так как в момент обмена тот не имел достоверной информации о D. Лишь спустя некоторое время, когда можно быть уверенным, что информация об отказе D распространилась по всей сети, маршрутизатор A может вновь начинать принимать объявления о путях до D. (За это время и А и B сотрут информацию о маршруте до D, так как оно превышает время хранения записи в таблице маршрутизации.)

ЦЕПНАЯ РЕАКЦИЯ

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

Зловещий призрак count-to-infinity продолжает бродить по сетям, использующим в своей работе протоколы вектора расстояний. Если зацикливание в сети все же произошло, то образовавшаяся петля будет разорвана, когда метрика маршрута превысит максимально допустимую. Этот процесс может быть ускорен с помощью механизма принудительных объявлений (triggered updates).

Правило принудительных объявлений звучит следующим образом: "Узнав об изменении метрики маршрута, маршрутизатор обязан немедленно сообщить об этом соседям". Узнав об отказе маршрутизатора А (см. Рисунок 2), узел B не будет ждать следующего обмена, а тут же сообщит об отказе узлу C. Узел C, в свою очередь, немедленно проинформирует D. Выход из строя узла A вызывает быстро распространяющуюся по сети волну объявлений. В результате адаптация сети к изменившейся топологии произойдет значительно быстрее.

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

МАЛЕНЬКИЕ ХИТРОСТИ

Современные протоколы вектора расстояний IGRP и EIGRP поддерживаются, например, маршрутизаторами Cisco. Они имеют такую полезную функцию, как метод корректировки отмены маршрута (route-poisoning).

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

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

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

По сообщению компании Cisco, ее специалистам удалось ликвидировать данный недостаток. По скорости восстановления после аварии протокол EIGRP не уступает протоколам состояния канала. Этим он прежде всего обязан алгоритму диффузионного обновления DUAL (Distibuted Update Algorithm).

Маршрутизатор, работающий по алгоритму DUAL, хранит в таблице маршрутизации не только адрес следующего узла на пути к сети назначения, но и список соседей, знающих такую же короткую дорогу (feasible successors). В случае сбоев в сети это позволяет, не пересчитывая маршрута и не посылая объявлений по сети, переключать трафик на путь с такой же стоимостью. Пересчитывание таблиц маршрутизации происходит только при отсутствии равнозначного пути. Объявления маршрутов посылаются только узлам, которых изменение в топологии касается непосредственно. (О деталях работы EIGRP см. http://www.cisco.com/warp/public/103/1.html)