LAN/ЖУРНАЛ СЕТЕВЫХ РЕШЕНИЙ #12/98
Несмотря на кажущуюся сложность и многообразие, протоколы маршрутизации базируются всего на двух простых алгоритмах, известных уже несколько десятилетий.
Алексей Савельев
Для выполнения своей основной функции - переключения трафика - каждый маршрутизатор использует таблицу, в которой отражена топология сети на данный момент времени. В самом общем случае таблица маршрутизации содержит адрес сети назначения, адрес следующего узла на пути к этой сети и метрику (стоимость) пути. Создание и последующее обновление таблицы маршрутизации при изменении топологии сети осуществляется с помощью протоколов маршрутизации. Наибольшей популярностью пользуются протоколы динамической маршрутизации.
Алгоритм Беллмана-Форда (также известный как алгоритм Форда-Фулкерсона) был положен в основу первого протокола маршрутизации, созданного для сети 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 | 1 | 0 | 0 | 0 |
| FTP: | ||||
| Команды | 1 | 0 | 0 | 0 |
| Данные | 0 | 1 | 0 | 0 |
| SMTP: | ||||
| Команды | 1 | 0 | 0 | 0 |
| Данные | 0 | 1 | 0 | 0 |
| DNS: | ||||
| Запрос TCP | 0 | 0 | 0 | 0 |
| Запрос UDP | 1 | 0 | 0 | 0 |
Как видим, с введением правила расщепления горизонта плохая новость распространяется в нашей сети так же быстро, как и хорошая. При этом никаких петель не возникает. К сожалению, даже при минимальном усложнении топологии правило расщепления горизонта перестает действовать.
Рисунок 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 )
Самый "пожилой" и заслуженный представитель семейства протоколов вектора расстояний, вне всякого сомнения, - протокол RIP. Он настолько прост и удобен в небольших сетях, что ему прощают даже откровенные проявления старческого маразма (как известно, RIP может запросто направить трафик через "полуживое" модемное соединение при наличии свободного волоконно-оптического канала - главное, чтобы транзитных узлов было поменьше).
Все дело в том, что во времена создания RIP линии связи имели максимальную пропускную способность 56 Кбит/с, и протоколу маршрутизации незачем было учитывать скорость канала. Поэтому единственный способ заставить RIP при определении маршрута отдавать предпочтение быстрым каналам - это назначить медленным линиям большую метрику вручную.
Появившийся сравнительно недавно протокол IGRP учитывает многие характеристики каналов связи. И RIP, и IGRP используют функцию временного отказа от приема сообщений для обеспечения большей стабильности работы в условиях изменяющейся топологии. Цена за такую стабильность - увеличение времени определения новых маршрутов, так как, блокировав изменение некоторого маршрута вследствие отказа какого-либо узла из опасения "дезинформации" со стороны соседей, маршрутизатор отбрасывает и корректные объявления.
Многие реализации протоколов позволяют функцию отказа от приема сообщений отключить. В этом случае, из-за распространения ложной информации, петли будут возникать чаще, но эффективность работы сети может и повыситься. При наличии механизма корректировки (т. е., например, если используется IGRP) и при отсутствии механизма отказа "дисциплину" в сети следует ужесточить и заставить маршрутизаторы ликвидировать маршруты даже при увеличении метрики на единицу.
В принципе, механизмов принудительных объявлений и отказа от приема достаточно для стабильной работы сети, однако пренебрегать, например, правилом расщепления горизонта конечно же не стоит. Расщепление горизонта позволяет по меньшей мере снизить объем рассылаемых сообщений.
На этом рассмотрение протоколов вектора расстояний можно закончить и перейти к другой, не менее интересной, группе протоколов маршрутизации - к протоколам состояния канала.
Развитие Internet привело к необходимости создания более гибкого и эффективного протокола маршрутизации для обслуживания крупных сетей. По замыслу создателей, протоколы состояния канала должны были решить характерные для протоколов вектора расстояний проблемы. Однако, в отличие от протоколов вектора расстояния, протоколы состояния канала сложны и требовательны к ресурсам маршрутизаторов. Основу протоколов состояния канала составляет алгоритм предпочтения кратчайшего пути, созданный в 1978 году.
Формальное описание протоколов состояния канала достаточно запутанно и может занять не один десяток страниц. В упрощенной форме принципы работы маршрутизаторов в соответствии с этим протоколом можно сформулировать в виде пяти несложных правил. Итак, каждый маршрутизатор в сети должен:
Другими словами, маршрутизатору необходимо узнать всю информацию о топологии сети, измерить метрики каналов, соединяющих собственные физические интерфейсы с соседями и далее, вычислить с помощью алгоритма Дейкстры, кратчайшие пути ко всем остальным узлам и внести полученные результаты в таблицу маршрутизации.
Рассмотрим каждый из пяти пунктов подробнее.
При подключении сети, маршрутизатор первым делом должен "познакомиться" со своими соседями. Для этого он рассылает через все свои физические интерфейсы специальные пакеты с приветствием HELLO. Получив такой пакет, соседний узел должен ответить, сообщив данные о себе.
Узнав данные о соседях, маршрутизатор принимается за второй пункт программы - тестирование каналов связи с целью выяснения метрики каждого канала. Под метрикой может пониматься пропускная способность, время задержки, надежность (количество ошибок на единицу переданной информации), загрузка канала.
Задержку канала можно определить, послав специальный ECHO-пакет, который принимающая сторона должна немедленно отправить обратно. Разделив время отклика пополам, маршрутизатор вычисляет приблизительную величину задержки канала.
Загрузку канала также несложно измерить. Однако ответ на вопрос о том, как использовать показатель загруженности канала при вычислении метрики, отнюдь не однозначен. Рассмотрим небольшой пример. При наличии нескольких альтернативных путей до точки назначения маршрутизатор, оценив загруженность каждого из них, переключает трафик на канал с меньшей загрузкой. Тем самым он максимально использует свободный канал, что вполне логично. Во время следующего измерения метрик предпочтение может быть отдано уже другому каналу, через который трафик уже не идет и который, следовательно, теперь менее загружен. В результате трафик будет переключен на него. Это приводит к тому, что трафик постоянно переводится с одного канала на другой, что, естественно, не способствует стабильности в работе сети.
Хороший протокол должен уметь распределять нагрузку по нескольким каналам. Современные протоколы маршрутизации успешно справляются с этой задачей.
Рисунок 4. Обмен пакетами с объявлениями о состоянии каналов.
Шаг номер три в программе маршрутизатора состоит в сообщении полученных знаний остальным. Информация о каналах должна быть разослана соседям. Однако пакеты с объявлениями о состоянии каналов (Link State Advertisement, LSA) могут затеряться при транспортировке или прибыть в ином порядке. Для того чтобы получатель мог разобраться в пришедшей информации, каждый пакет с объявлением о состоянии каналов снабжается полями source (адрес отправителя), sequence number (номер пакета в последовательности отправленных сообщений) и age (возраст) (см. Рисунок 4).
В процессе работы маршрутизатора пакеты с объявлениями маршрутов рассылаются обычно лишь в случае каких-либо изменений в сети. В остальное же время протоколы состояния канала молчат и не загружают каналы служебной информацией, лишь изредка обмениваясь небольшими HELLO-пакетами.
Обмен информацией осуществляется с помощью веерной рассылки (flooding), т. е., получив пакет, маршрутизатор LSA сохраняет копию в своей базе данных и посылает пакет дальше всем остальным соседям. В итоге пакет, отправленный одним из узлов сети, обязательно получат все остальные маршрутизаторы. В этом ключевое отличие данного алгоритма от алгоритма вектора расстояния, в котором каждый узел мог общаться только с непосредственно подключенными к нему маршрутизаторами, что часто приводит к эффекту "испорченного телефона", когда, сам не разобравшись в топологии, маршрутизатор сбивает с толку соседей.
Протокол состояния канала дает возможность каждому узлу самостоятельно обменяться информацией со всеми маршрутизаторами и получить представление о топологии сети. Именно поэтому данному алгоритму не свойственны проблемы возрастания до бесконечности, а жесткие ограничения на диаметр сети отсутствуют.
Узким местом такого подхода является необходимость обязательной синхронизации баз данных всех маршрутизаторов в пределах автономной системы. Если разные узлы будут по-разному представлять себе топологию сети, с которой они работают, то это приведет к образованию петель и к другим проблемам.
Получив пакет LSA, маршрутизатор проверяет пару (source, sequence), что позволяет отбросить устаревшие и дублированные объявления. Поле age задает время, по истечении которого не приславший новых объявлений узел считается недоступным.
В конкретных протоколах данные поля могут носить другие названия, в протоколе OSPF, например, поля age и sequence носят названия DeadInt и DD Sequence, а протокол IS-IS даже использует специальный тип пакета - порядковый пакет. Однако, независимо от протокола, наличие подобной информации обязательно для надежной работы алгоритма предпочтения кратчайшего пути.
После получения информации от всех узлов маршрутизатор может построить "карту" сети. Для этого он создает ориентированный граф, отражающий топологию сети. Соединение "точка-точка" между узлами представляется на графе парой дуг (по одной в каждом направлении), причем стоимости этих дуг могут отличаться друг от друга. Сети с множественным доступом (например, локальные сети) отображаются вершинами для каждого узла сети и дополнительной вершиной - "центром" этой сети. Дуги графа от "центра" до узлов сети не отображаются (см. Рисунок 5).
Имея в памяти такой граф, маршрутизатор применяет алгоритм Дейкстры для выбора пути с наименьшей суммарной стоимостью до каждой из вершин графа (т. е. до каждого узла сети). По результатам этих вычислений и строится таблица маршрутизации, используемая далее при переключении трафика.
Рисунок 5. Сеть и ее предствление в виде графа.
Наиболее популярные протоколы состояния канала - это IS-IS и OSPF. Протокол IS-IS изначально создавался для сетей OSI, но впоследствии был адаптирован и к другим протоколам сетевого уровня, в частности к IP. Например, сеть NSFNet широко использует IS-IS в своей работе. К основным достоинствам IS-IS принято относить его "врожденную" способность взаимодействовать с самыми различными протоколами сетевого уровня, что делает его особенно полезным в крупных многопротокольных сетях. В сетях TCP/IP, все же, более популярен протокол OSPF. Протоколы IS-IS и OSPF имеют очень много общего (OSPF, по сути, является улучшенной версией IS-IS). Все сказанное ранее о протоколах состояния канала в равной степе-ни справедливо и для IS-IS, и для OSPF.
Протоколом OSPF предусмотрена полезная возможность вычисления отдельного набора маршрутов для каждого значения поля "тип сервиса" (Type-Of-Service, TOS) в заголовке протокола IP. До создания OSPF ни один протокол не использовал значение этого поля.
Поле "тип сервиса" позволяет запрашивать для трафика определенный уровень сервиса. Длина поля - четыре бита, из которых значимым может быть только один. Таким образом, мы имеем всего четыре возможных варианта: минимальная задержка, максимальная пропускная способность, максимальная надежность, минимальная стоимость (в смысле оплаты). Каждое приложение по-разному устанавливает значение поля TOS. Значения битов данного поля для некоторых приложений приведены ниже (см. Таблица 1).
Как видно из таблицы, протоколам FTP и SMTP требуется передавать команды с минимальной задержкой, а для передачи данных им необходима большая пропускная способность. Если запрос DNS передается по протоколу UDP, то очевидно, что программа-resolver, пославшая этот запрос, желает получить ответ как можно скорее, так как дейтаграммы UDP не требуют посылки подтверждений. Настроив протокол OSPF для определения маршрутов либо с минимальной задержкой, либо с максимальной пропускной способностью, в зависимости от TOS, мы можем еще больше ускорить работу DNS, так же как FTP и SMTP.
Однако не стоит забывать, что протоколы состояния канала очень требовательны к памяти. Злоупотребление богатыми возможностями OSPF быстро приведет к переполнению памяти маршрутизатора и сбоям при вычислениях маршрутов. В итоге весь трафик окажется в состоянии хаоса, и никакого заявленного типа сервиса он не получит.
Необходимо помнить, что абсолютно надежных протоколов маршрутизации не существует. При чрезмерной нагрузке отказать может любой протокол. Каких-то общепринятых стандартов настройки протоколов состояния канала нет. Однако обычно их настройка производится с учетом следующих соображений.
Протоколам маршрутизации традиционно не нравятся "облака" сетей X.25 и frame relay. Большое число медленных каналов, соответственно, требующих рассылки большого числа объявлений LSA, затрудняет работу. Рассылка объявлений производится по "веерному" методу, поэтому полносвязная (fully-meshed) топология сети нежелательна. Сети с частично связной (partial-meshed) топологией здесь более предпочтительны.
Несмотря на отсутствие строгого ограничения на максимальное количество узлов в сети, возможности протоколов все же не безграничны. Эксперименты с протоколом OSPF показали, что 50 маршрутизаторов на зону (area) - это верхний предел, превышение которого чревато неприятными "сюрпризами" со стороны сети. При большем количестве узлов лучший выход состоит в создании новой зоны.
Самой серьезной проблемой может стать нехватка памяти. Для системы из n узлов, каждый из которых имеет k соседей, необходимый объем памяти пропорционален k*n. Обычно подобные проблемы проявляются в больших сетях, с очень большим количеством внешних маршрутов. Определение одного маршрутизатора (шлюза) по умолчанию для всех внешних путей может значительно сэкономить память. Вообще, тщательное предварительное планирование сети способно значительно облегчить "жизнь" протоколам состояния канала.
C Алексеем Савельевым можно связаться по тел.: (095) 705-9229, 929-9500, или адресу: a.saveljev@usa.net.