Дибров М.В. Маршрутизаторы

Подождите немного. Документ загружается.

R1 R6R4

СП1

СП2 СП3

СП4

СП7

СП5СП6

18 7

Рисунок 9.2 – Представление топологии сети алгоритмом DUAL

алгоритмом маршрутизации по состоянию канала связи

Как видно, кроме кратчайшего пути к сети получателю СП4, лежащего

через маршрутизатор R2, маршрутизатор R1 смог также обнаружить альтер-

нативный маршрут, лежащий через маршрутизатор R4. Метрика кратчайшего

маршрута равна 22 (10 + 12), тогда как метрика альтернативного – 26 (10 +

16). Несмотря на более высокую метрику, маршрутизатор R1 все же рассмат-

ривает маршрут через маршрутизатор R4 как альтернативу, поскольку метри-

ка собственного маршрута маршрутизатора R4 к СП4 равна всего 16, т.е.

меньшему значению, чем метрика кратчайшего маршрута маршрутизатора

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

чем маршрутизатор R1, а значит, маршрутизатор R1 может мгновенно

переключиться на маршрут через R4, если характеристики маршрута через R2

ухудшатся или он станет недоступен.

R6R4

СП1

СП2 СП3

СП4

СП7

СП5СП6

104

Рисунок 9.3 – Представление топологии сети

алгоритмом маршрутизации по состоянию канала связи

161

На рисунке 9.3 показано представление топологии сети передачи дан-

ных маршрутизатором R1 с использованием протокола маршрутизации по со-

стоянию канала. Здесь маршрутизатор R1 знает полную топологию сети пере-

дачи данных. Следовательно, он знает не только об альтернативном маршруте

к сети получателю СП4 через маршрутизатор R4, но также и об альтернатив-

ных маршрутах к СП6 и СП5 через маршрутизатор R2.

Протоколы маршрутизации по состоянию канала имеют два главных

преимущества над дистанционно-векторными протоколами маршрутизации.

Первое преимущество заключается в том, что каждый маршрутизатор в доме-

не маршрутизации имеет точную информацию о топологии сети передачи

данных, следовательно, он может гарантировать, что в таблицу маршрутиза-

ции будут внесены истинные и оптимальные маршруты до сетей получателей.

Второе преимущество следует из первого. Оно заключается в том, что

если маршрутизатор имеет точную информацию о топологии сети передачи

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

механизму рассылки запросов соседним маршрутизаторам, о возможных аль-

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

того как, он обнаружил недоступность того или иного маршрута. Следова-

тельно, время сходимости протоколов маршрутизации по состоянию канала,

значительно меньше, чем у дистанционно-векторных протоколов маршрути-

зации использующих алгоритм Беллмана-Форда.

Однако превосходство протоколов маршрутизации по состоянию кана-

ла имеет свою цену. Такие протоколы обычно значительно сложнее реализо-

вать, чем дистанционно-векторные протоколы Беллмана-Форда и протоколы

на основе алгоритма DUAL. Вычисление маршрутов, исходя из топологиче-

ской информации, обычно требует больше усилий по обработке, чем необхо-

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

бы обеспечить идентичность топологических сведений на всех маршрутиза-

торах, требуется более интенсивный обмен данными между маршрутизатора-

ми.

Если протоколы маршрутизации по состоянию канала сходятся бы-

стрее, чем протоколы Беллмана-Форда, этого нельзя сказать при сравнении

этих протоколов с протоколами на основе алгоритма DUAL. Эксперименталь-

ные данные указывают на то, что в большинстве случаев протоколы маршру-

тизации на основе DUAL сходятся, по меньшей мере настолько же быстро,

как и протоколы маршрутизации по состоянию канала.

И все же алгоритм маршрутизации по состоянию канала популярен

благодаря широко распространенному протоколу маршрутизации OSPF, а сам

протокол обязан своей популярностью открытости своей спецификации.

Эта открытость позволила множеству различных производителей,

включая Cisco, успешно реализовать протокол OSPF в своем оборудовании и

программном обеспечении. Хотя протоколы маршрутизации, основанные на

162

конкурирующем алгоритме DUAL, работают быстро, практически единствен-

ный популярный экземпляр таких протоколов – это протокол EIGRP, являю-

щийся фирменным протоколом корпорации Cisco.

Протокол OSPF оказался способен поддерживать очень крупные сети

передачи данных, состоящие зачастую из тысяч маршрутизаторов. Даже в та-

ких крупных сетях протокол OSPF быстро обрабатывает происходящие изме-

нения, и время его сходимости редко превышает доли минуты.

В основе протокола OSPF, как и любого другого протокола маршрути-

зации по состоянию канала, лежит алгоритм кратчайшего пути Дейкстры

(Dijkstra), используемый для создания маршрутов на основе топологической

информации. Учитывая центральное место алгоритма Дейкстры в работе про-

токолов маршрутизации по состоянию канала, необходимо сначала рассмот-

реть сам алгоритм и получить понятие о работе ядра протокола маршрутиза-

ции по состоянию канала. И только после этого обратиться к подробному

рассмотрению протокола OSPF.

9.1 Алгоритм «кратчайшего пути» Дейкстры

Алгоритм кратчайшего пути – shortest path algorithm (SPF) Дейкстры ра-

ботает с графами, состоящими из вершин, соединенных ребрами. Каждое ре-

бро соединяет ровно две вершины в одном направлении. Каждое ребро имеет

стоимость, связанную с ним. Каждая вершина может быть связана с любым

числом ребер.

Вершины можно представлять как точки, а ребра – как перемещение

между этими точками. Перемещение обеспечивается лишь в одном направле-

нии и за определенную стоимость – в направлении ребра и за стоимость ре-

бра. Например, если ребро соединяет вершину A с вершиной B, это означает,

в сущности, что имеется возможность за стоимость этого ребра переместить-

ся из вершины A в вершину B. Это ребро, однако, не позволяет переместиться

обратно из вершины B в вершину A. Такое перемещение требует наличия

другого ребра – из вершины B в вершину A.

E F

8 5

Рисунок 9.4 – Пример графа

163

На рисунке 9.4 приводится пример графа. Этот граф содержит шесть

вершин, помеченных буквами от A до F. Ребра обозначаются линиями со

стрелками, которые соединяют вершины, а стоимость ребер указана в виде

чисел, изображенных поверх ребер.

Говорится, что вершина X является смежной с вершиной Y, если имеет-

ся ребро, ведущее от вершины X к вершине Y. Например, на рисунке 9.4 вер-

шина B является смежной с вершиной A. Необходимо обратить внимание,

что обратное может быть неверно, например, вершина A не является смежной

с вершиной B, поскольку ребра, ведущего от вершины A к вершине B, не су-

ществует.

Граф с большим количеством вершин может иметь множество путей

между двумя вершинами. Среди этих путей лучший путь определяется как

путь, совокупная стоимость которого, рассчитана как минимальная сумма

стоимостей составляющих путь ребер. Например, кратчайший путь от верши-

ны D к вершине A лежит через вершину B, его стоимость равна 4. Обратный

путь, от вершины A к вершине D, имеет большую длину, он лежит через вер-

шины C и B и имеет стоимость 15.

В приведенном примере задача нахождения кратчайшего пути относи-

тельно проста, но если граф становится больше, количество вычислений рас-

тет экспоненциально. И даже самый быстрый компьютер будет затрачивать

слишком много времени на перебор всех возможных путей и расчет их стои-

мости.

Алгоритм SFP решает задачу быстрого нахождения кратчайшего пути

между любыми двумя вершинами в графе с произвольными связями.

Для работы алгоритм использует две вспомогательные структуры дан-

ных: базу данных вершин, для которых ищется кратчайший путь, и базу дан-

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

Обозначим эти базы как «Найденные» и «Кандидаты». Обе базы данных име-

ют идентичную структуру: они содержат два поля, содержащие ссылку на

вершину и совокупную стоимость пути от начальной вершины к указанной.

Чтобы продемонстрировать работу алгоритма по шагам воспользуемся

графом, изображенным на рисунке 9.4.

Работа алгоритма начинается с помещения начальной вершины в базу

«Найденные» с совокупной стоимостью 0, а всех ее смежных вершин - в базу

«Кандидаты» с совокупной стоимостью, равной стоимости соответствующих

ребер. После этого алгоритм циклически проходит через следующие рекур-

сивные шаги:

Шаг 1. Найти в базе «Кандидаты» вершину с наименьшей совокупной

стоимостью. Переместить вершину в базу «Найденные».

Шаг 2. Определить вершины, с которыми перемещенная вершина яв-

ляется смежной.

Шаг 3. Отбросить смежные вершины данной вершины, которые уже

были перемещены в базу «Найденные».

164

Шаг 4. Для каждой из смежных вершин перемещенной вершины, кото-

рая уже была помещена в базу «Кандидаты», установить записанную сово-

купную стоимость равной меньшей из величин предыдущей записанной сово-

купной стоимости и суммы совокупной стоимости перемещенной вершины

плюс стоимость ребра, ведущего от перемещенной вершины к смежной, фор-

мула (9.1).

смеж. нов.

= min(C

смеж. стар.

, C

перемещ.

+ C

ребра

) (9.1)

где C

смеж. нов.

и C

смеж. стар.

– соответственно новая и старая записанные совокуп-

ные стоимости смежной вершины,

перемещ.

– записанная совокупная стоимость перемещенной вершины,

ребра

– стоимость ребра от перемещенной вершины к смежной.

Шаг 5. Поместить каждую смежную вершину, не содержащуюся ни в

базе «Найденные», ни в базе «Кандидаты», в базу «Кандидаты». Установить

ее совокупную стоимость равной сумме совокупной стоимости перемещен-

ной вершины и стоимости ребра, ведущего от перемещенной вершины к

смежной, формула (9.2).

смеж.

= C

перемещ.

+ C

ребра

(9.2)

где C

смеж.

– совокупная стоимость смежной вершины.

Шаг 6. Если база «Кандидаты» пуста, завершить работу. В противном

случае вернуться к Шагу 1 и повторить действия.

На рисунке 9.5 каждый из шести шагов помещен отдельно и помечен

своим номером. Вершины, которые были помещены в базу «Найденные», от-

мечены жирной границей, а вершины с тонкой границей попали только в базу

«Кандидаты». Числа на ребрах указывают совокупную стоимость пути от на-

чальной вершины к вершине, к которой ребро ведет, тогда как на рисунке 9.4,

числа обозначали стоимость ребер. Если на ребре находится вопросительный

знак, это означает, что вершина, к которой ведет ребро, уже находится в базе

«Найденные», и, поэтому совокупная стоимость для нее не рассчитывается.

Кроме того, для каждой итерации приведено содержимое баз «Найден-

ные» и «Кандидаты». Вершина, которая только что была помещена в базу

«Найденные», помечена звездочкой. Вершины, которые либо были помещены

в базу «Кандидаты» либо имеют обновленные существующие записи в этой

базе, помечены знаком «>». Если совокупная стоимость заменена меньшей

величиной, в соответствующей записи базы «Кандидаты» показано старое

значение, «>», а затем новое значение.

Как видно из схемы, алгоритм определил длины кратчайших путей к

каждой вершине методично и достаточно простым способом.

165

Простота и скорость алгоритма определили для него центральное место

в алгоритмах маршрутизации по состоянию канала, строящих маршруты ис-

ходя из информации о топологии сети.

Кандидаты

С E

4 4

Найденные

А 0

Шаг 1

C 4>

E 4>

Кандидаты

С E

4 4

Найденные

А 0

Шаг 2

C 4

E 4

B 12

Кандидаты

С E

4 4

Найденные

А 0

Шаг 3

C 4

E 4

B 12

FCA

F 8

Кандидаты

С E

4 4

Найденные

А 0

Шаг 4

C 4

E 4

B 12

D 16

F 8

Кандидаты

С E

4 4

Найденные

А 0

Шаг 5

C 4

E 4

DCA

1615

→

Кандидаты

С E

4 4

Найденные

А 0

Шаг 6

C 4

E 4

<Пусто >

FEB

? ?

Рисунок 9.5 – Итерации алгоритма SPF

166

10 Протокол OSPF

Протокол маршрутизации по состоянию каналов OSPF (Open Shortest

Path First) описан в документе RFC 2328. Протокол OSPF использует алго-

ритм SPF и поэтому может осуществлять более интеллектуальный выбор

маршрута по сравнению с дистанционно-векторными протоколами маршру-

тизации. Существует несколько версий протокола OSPF, в настоящее время

широкое распространение получила вторая версия протокола – OSPF v2.

Все маршрутизаторы поддерживающие OSPF, сети и подсети логически

объединены в зоны. Сети передачи данных, в которых применяется протокол

OSPF, могут составлять одну зону или включать множество зон, организован-

ных по иерархическому признаку. Объединенная сеть передачи данных, ис-

пользующая протокол OSPF, независимо от того, состоит ли она из одной

зоны или включает множество зон, представляет собой один домен маршру-

тизации, или другими словами одну автономную систему. Такая иерархиче-

ская структура позволяет локализовать изменения маршрутов и трафик марш-

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

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

тизации и пересчетом этих таблиц в случае изменения маршрутов.

10.1 Характеристики протокола OSPF

Протокол OSPF обладает следующими свойствами:

– Групповая рассылка обновлений. В протоколе OSPF рассылка тополо-

гической информации о состоянии каналов связи осуществляется по группо-

вому адресу 224.0.0.5 для всех маршрутизаторов OSPF и по адресу 224.0.0.6

для назначенного и резервного назначенного маршрутизатора.

– Бесклассовая маршрутизация. Протоколом OSPF поддерживается тех-

нология VLSM.

– Аутентификация. Маршрутизаторы OSPF имеют возможность ис-

пользовать несколько методов аутентификации, таких как аутентификация по

паролю или с помощью MD5.

– Быстрота распространения изменений в топологии. Благодаря отсут-

ствию периодической рассылки обновлений маршрутной информации марш-

рутизатор, обнаруживший изменения в топологии сети, незамедлительно опо-

вещает об этом все соседние маршрутизаторы

– Экономия пропускной способности каналов связи. Протокол OSPF

производит периодическую рассылку информации базы данных топологии

сети передачи данных через длительные промежутки времени, 30 минут.

– Иерархическое разделение сети передачи данных. Протокол OSPF

позволяет произвести иерархическое разделение сети передачи данных на

167

несколько зон, с целью уменьшения нагрузки на маршрутизаторы внутри

каждой зоны.

10.1.1 Групповая рассылка обновлений состояния каналов

Для распространения обновлений о состоянии каналов передачи дан-

ных OSPF маршрутизаторы не используют широковещательные рассылки.

Вместо этого они применяют групповую рассылку по зарезервированным для

протокола OSPF групповым IP адресам.

Протокол OSPF поддерживает два основных групповых адреса:

224.0.0.5 – для всех маршрутизаторов OSPF и 224.0.0.6 - адрес для назначен-

ного и резервного назначенного маршрутизатора. Маршрутизатор, на кото-

ром активизирован протокол OSPF, автоматически становится членом группы

многоадресной рассылки с адресом 224.0.0.5 и начинает рассылать и получать

групповые сообщения OSPF.

В широковещательных сетях выбирается назначенный маршрутизатор

(Designated Router) – DR и резервный назначенный маршрутизатор (Backup

Designated Router) – BDR. Оба эти маршрутизатора с момента принятия на

себя таких функций становятся членами группы многоадресной рассылки с

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

на этот адрес всеми остальными маршрутизаторами OSPF принадлежащими

тому же широковещательному домену.

10.1.2 Аутентификация

Протокол OSPF обеспечивает аутентификацию соседних маршрутиза-

торов при передаче обновлений о состоянии каналов передачи данных.

Аутентификация маршрутизаторов может осуществляться как при помощи

передачи пароля в виде открытого текста, так и при помощи MD5.

10.1.3 Быстрота распространения изменения в топологии

Протокол OSPF производит рассылку обновлений о состоянии канала

связи сразу после обнаружения изменений в его состоянии. Маршрутизатор

отслеживает каждое изменение и рассылает сообщение о состоянии канала –

(Link State Advertisement) – LSA.

Сообщения LSA рассылаются всем соседним маршрутизаторам, в свою

очередь каждый маршрутизатор получивший LSA производит обновление

своей базы данных топологии сети и производит дальнейшую рассылку LSA

всем своим соседям. Такая рассылка называется лавинной, и она информиру-

ет все маршрутизаторы о произошедших изменениях в топологии сети, а так

же о возможной необходимости внесения изменений в таблицу маршрутиза-

ции с целью отражения в ней новой топологии сети.

168

10.1.4 Иерархическое разделение сети передачи данных

В небольших сетях количество каналов связи межу маршрутизаторами

не столь велико и расчет маршрутов для каждой сети получателя не столь

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

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

маршрутов велико, применение алгоритма SPF требует достаточного большо-

го промежутка времени и значительных вычислительных возможностей

маршрутизатора. Протокол OSPF для уменьшения числа расчетов применяют

разделение сети передачи данных на зоны. Число маршрутизаторов в каждой

зоне, а так же число LSA в пределах зоны не велико, следовательно, база дан-

ных состояния каналов в пределах зоны значительно меньше. Поэтому расчет

маршрутов становиться легче и занимает меньше времени. Различается два

основных типа зон:

– Транзитная зона. Главная задача транзитной зоны быстрое и эффектив-

ное продвижение IP пакетов в другие зоны. В транзитной зоне не рекомендует-

ся размещать пользовательские сети, хотя это не запрещено в спецификации.

В протоколе OSPF в качестве транзитной зоны применяется Зона 0, также

именуемая базовой (backbone area).

– Регулярные зоны. В протоколе OSPF зоны, чья основная задача под-

ключение пользователей называются регулярными. Регулярные зоны устанав-

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

умолчанию регулярные зоны не пропускают трафик из других зон. Весь тра-

фик из других зон проходит через транзитную зону.

Применение протокола OSPF вынуждает применять жесткую двух

уровневую иерархию сети передачи данных (Рисунок 10.1). Все регулярные

зоны должны иметь соединение с базовой зоной.

Зона 1 Зона 2 Зона 3

Зона 0 (Backbone )

Рисунок 10.1 – Зональное разделение в протоколе OSPF

169

10.2 База данных протокола OSPF

Все маршрутизаторы OSPF создают и поддерживают в своей базе дан-

ных две основные таблицы:

– Таблица соседства. Все маршрутизаторы OSPF ведут таблицу сосед-

ства, в которой хранится список и вся необходимая информация о соседних

OSPF маршрутизаторах.

– Таблица топологии. Каждый маршрутизатор OSPF ведет таблицу то-

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

тей, подсетей и маршрутизаторов в пределах зоны OSPF. Если маршрутиза-

тор OSPF имеет подключение к двум и более зонам, то он ведет отдельную

таблицу топологии для каждой из зон OSPF, к которой он подключен.

10.2.1 Таблица соседства

Чтобы начать обмен топологической информацией, маршрутизаторы

OSPF, находящиеся в одном и том же сегменте сети в пределах одной зоны

OSPF, должны сформировать соседские взаимоотношения. Маршрутизаторы

становятся соседями после того, как они обменяются приветственными паке-

тами. Когда маршрутизатор OSPF находится в процессе инициализации, он

должен распознать все соседние OSPF маршрутизаторы и установить с ними

соседские взаимоотношения. Этот процесс называется процессом обнаруже-

ния соседей. Каждый маршрутизатор в результате обмена приветственными

сообщениями создает локальную таблицу соседей, в дальнейшем отслеживая

всех своих соседей и их состояния. В примере 10.1 приводится таблица сосед-

ства маршрутизатора OSPF.

Пример 10.1 – Таблица соседства маршрутизатора OSPF

Neighbor ID Pri State Dead Time Address Interface

10.95.72.27 1 2WAY/DROTHER 00:00:37 10.93.72.41 Vlan325

10.95.72.29 1 2WAY/DROTHER 00:00:32 10.93.72.42 Vlan325

10.95.120.22 1 FULL/BDR 00:00:35 10.93.72.34 Vlan325

10.95.120.23 1 FULL/DR 00:00:38 10.93.72.35 Vlan325

10.95.12.10 1 FULL/- 00:00:18 10.93.18.10 Serial0/0

Ниже описаны поля, содержащиеся в таблице соседства:

– Идентификатор соседа (Neighbor ID). Уникальное число идентифици-

рующее соседний маршрутизатор.

– Приоритет маршрутизатора (Pri). Приоритет соседнего маршрутизато-

ра.

– Состояние (State). Состояние соседских отношений.

170