Протокол маршрутизации OSPF. Динамическая маршрутизация на базе протокола OSPF OSPF Hello и Dead интервалы

А сейчас вкратце пробежимся по теории.

OSPF (Open Shortest Path First ) - протокол динамической маршрутизации, основанный на технологии отслеживания состояния канала (link-state technology) и использующий для нахождения кратчайшего пути Алгоритм Дейкстры (Dijkstra’s algorithm).

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

OSPF предлагает решение следующих задач:

Увеличение скорости сходимости;
Поддержка сетевых масок переменной длины (VLSM);
Достижимость сети;
Использование пропускной способности;
Метод выбора пути.

Теория

Терминология протокола OSPF

Объявление о состоянии канала (link-state advertisement, LSA) - объявление описывает все каналы маршрутизатора, все интерфейсы и состояние каналов.
Состояние канала (link state) - состояние канала между двумя маршрутизаторами; обновления происходят при помощи пакетов LSA.
Метрика (metric) - условный показатель «стоимости» пересылки данных по каналу;
Автономная система (autonomous system) - группа маршрутизаторов, обменивающаяся маршрутизирующей информацией с помощью одного протокола маршрутизации.
Зона (area) - совокупность сетей и маршрутизаторов, имеющих один и тот же идентификатор зоны.
Соседи (neighbours) - два маршрутизатора, имеющие интерфейсы в общей сети.
Состояние соседства (adjacency) - взаимосвязь между определенными соседними маршрутизаторами установленная с целью обмена информацией маршрутизации.
Hello-пакеты (hello packets) - используются для поддержания соседских отношений.
База данных соседей (neighbours database) - список всех соседей.
База данных состояния каналов (link state database, LSDB) - список всех записей о состоянии каналов. Встречается также термин топологическая база данных (topological database), употребляется как синоним базы данных состояния каналов.
Идентификатор маршрутизатора (router ID, RID) - уникальное 32-битовое число, которое уникально идентифицирует маршрутизатор в пределах одной автономной системы.
Выделенный маршрутизатор (designated router, DR) - управляет процессом рассылки LSA в сети. Каждый маршрутизатор сети устанавливает отношения соседства с DR. Информация об изменениях в сети отправляется DR, маршрутизатором обнаружившим это изменение, а DR отвечает за то, чтобы эта информация была отправлена остальным маршрутизаторам сети.Недостатком в схеме работы с DR маршрутизатором является то, что при выходе его из строя должен быть выбран новый DR. Новые отношения соседства должны быть сформированы и, пока базы данных маршрутизаторов не синхронизируются с базой данных нового DR, сеть будет недоступна для пересылки пакетов. Для устранения этого недостатка выбирается BDR.
Резервный выделенный маршрутизатор (backup designated router, BDR) . Каждый маршрутизатор сети устанавливает отношения соседства не только с DR, но и BDR. DR и BDR также устанавливают отношения соседства и между собой. При выходе из строя DR, BDR становится DR и выполняет все его функции. Так как маршрутизаторы сети установили отношения соседства с BDR, то время недоступности сети минимизируется.

Краткое описание работы протокола

Маршрутизаторы обмениваются hello-пакетами через все интерфейсы на которых активирован OSPF . Маршрутизаторы разделяющие общий канал передачи данных становятся соседями, когда они приходят к договоренности об определенных параметрах указанных в их hello-пакетах.
На следующем этапе работы протокола маршрутизаторы будут пытаться перейти в состояние соседства со своими соседями. Переход в состояние соседства определяется типом маршрутизаторов обменивающихся hello-пакетами и типом сети по которой передаются hello-пакеты. OSPF определяет несколько типов сетей и несколько типов маршрутизаторов. Пара маршрутизаторов, находящихся в состоянии соседства синхронизирует между собой базу данных состояния каналов.
Каждый маршрутизатор посылает объявление о состоянии канала маршрутизаторам с которыми он находится в состоянии соседства.
Каждый маршрутизатор получивший объявление от соседа записывает информацию передаваемую в нем в базу данных состояния каналов маршрутизатора и рассылает копию объявления всем другим своим соседям.
Рассылая объявления через зону, все маршрутизаторы строят идентичную базу данных состояния каналов маршрутизатора.
Когда база данных построена, каждый маршрутизатор использует алгоритм кратчайший путь первым для вычисления графа без петель, который будет описывать кратчайший путь к каждому известному пункту назначения с собой в качестве корня. Этот граф это дерево кратчайшего пути.
Каждый маршрутизатор строит таблицу маршрутизации из своего дерева кратчайшего пути.

В сетях со множественным доступом отношения соседства должны быть установлены между всеми маршрутизаторами. Это приводит к тому, что рассылается большое количество копий LSA. Если, к примеру, количество маршрутизаторов в сети со множественным доступом равно n , то будет установлено n(n-1)/2 отношений соседства. Каждый маршрутизатор будет рассылать n-1 LSA своим соседям, плюс одно LSA для сети, в результате сеть сгенерирует n? LSA.

Маршрутизатор, выбранный DR или BDR в одной присоединенной к нему сети со множественным доступом, может не быть DR (BDR) в другой присоединенной сети. Роль DR (BDR) является свойством интерфейса, а не свойством всего маршрутизатора.

Таймеры протокола

HelloInterval - Интервал времени в секундах по истечению которого маршрутизатор отправляет следующий hello-пакет с интерфейса. Для широковещательных сетей и сетей точка-точка значение по умолчанию, как правило, 10 секунд. Для нешироковещательных сетей со множественным доступом значение по умолчанию 30 секунд.
RouterDeadInterval - Интервал времени в секундах по истечению которого сосед будет считаться «мертвым». Этот интервал должен быть кратным значению HelloInterval. Как правило, RouterDeadInterval равен 4 интервалам отправки hello-пакетов, то есть 40 секунд.
Wait Timer - Интервал времени в секундах по истечению которого маршрутизатор выберет DR в сети. Его значение равно значению интервала RouterDeadInterval.
RxmtInterval - Интервал времени в секундах по истечению которого маршрутизатор повторно отправит пакет на который не получил подтверждения о получении (например, Database Description пакет или Link State Request пакеты). Это интервал называется также Retransmit interval. Значение интервала 5 секунд.

Типы маршрутизаторов

Внутренний маршрутизатор (internal router) - маршрутизатор все интерфейсы которого принадлежат одной зоне. У таких маршрутизаторов только одна база данных состояния каналов.

Пограничный маршрутизатор (area border router, ABR) - соединяет одну или больше зон с магистральной зоной и выполняет функции шлюза для межзонального трафика. У пограничного маршрутизатора всегда хотя бы один интерфейс принадлежит магистральной зоне. Для каждой присоединенной зоны маршрутизатор поддерживает отдельную базу данных состояния каналов.

Магистральный маршрутизатор (backbone router) - маршрутизатор у которого всегда хотя бы один интерфейс принадлежит магистральной зоне. Определение похоже на пограничный маршрутизатор, однако магистральный маршрутизатор не всегда является пограничным. Внутренний маршрутизатор интерфейсы которого принадлежат нулевой зоне, также является магистральным.

Пограничный маршрутизатор автономной системы (AS boundary router, ASBR) - обменивается информацией с маршрутизаторами принадлежащими другим автономным системам. Пограничный маршрутизатор автономной системы может находиться в любом месте автономной системы и быть внутренним, пограничным или магистральным маршрутизатором.

Типы объявлений о состоянии канала (LSA)

Type 1 LSA - Router LSA - объявление о состоянии каналов маршрутизатора. Эти LSA распространяются всеми маршрутизаторами. В LSA содержится описание всех каналов маршрутизатора и стоимость (cost) каждого канала. Распространяются только в пределах одной зоны.

Type 2 LSA - Network LSA - объявление о состоянии каналов сети. Распространяется DR в сетях со множественным доступом. В LSA содержится описание всех маршрутизаторов присоединенных к сети, включая DR. Распространяются только в пределах одной зоны.

Type 3 LSA - Network Summary LSA - суммарное объявление о состоянии каналов сети. Объявление распространяется пограничными маршрутизаторами. Объявление описывает только маршруты к сетям вне зоны и не описывает маршруты внутри автономной системы. Пограничный маршрутизатор отправляет отдельное объявление для каждой известной ему сети.

Когда маршрутизатор получает Network Summary LSA от пограничного маршрутизатора он не запускает алгоритм вычисления кратчайшего пути. Маршрутизатор просто добавляет к стоимости маршрута указанного в LSA стоимость маршрута к пограничному маршрутизатору. Затем маршрут к сети через пограничный маршрутизатор помещается в таблицу маршрутизации.

Type 4 LSA - ASBR Summary LSA - суммарное объявление о состоянии каналов пограничного маршрутизатора автономной системы. Объявление распространяется пограничными маршрутизаторами. ASBR Summary LSA отличается от Network Summary LSA тем, что распространяется информация не о сети, а о пограничном маршрутизаторе автономной системы.

Type 5 LSA - AS External LSA - объявления о состоянии внешних каналов автономной системы. Объявление распространяется пограничным маршрутизатором автономной системы в пределах всей автономной системы. Объявление описывает маршруты внешние для автономной системы OSPF или маршруты по умолчанию (default route) внешние для автономной системы OSPF.

Type 7 LSA - AS External LSA for NSSA - объявления о состоянии внешних каналов автономной системы в NSSA зоне. Это объявление может передаваться только в NSSA зоне. На границе зоны пограничный маршрутизатор преобразует type 7 LSA в type 5 LSA.

Типы зон

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

Разделение на зоны позволяет:

Снизить нагрузку на ЦПУ маршрутизаторов за счет уменьшения количества перерасчетов по алгоритму SPF
Уменьшить размер таблиц маршрутизации
Уменьшить количество пакетов обновлений состояния канала

Каждой зоне присваивается идентификатор зоны (area ID). Идентификатор может быть указан в десятичном формате или в формате записи IP-адреса. Однако идентификаторы зон не являются IP-адресами и могут совпадать с любым назначенным IP-адресом.

Магистральная зона (backbone area)

Магистральная зона (известная также как нулевая зона (Area 0) или зона 0.0.0.0) формирует ядро сети OSPF. Все остальные зоны ДОЛЖНЫ быть соединены с ней, и межзональная маршрутизация происходит через маршрутизатор соединенный с магистральной зоной. Магистральная зона ответственна за распространение маршрутизирующей информации между немагистральными зонами. Магистральная зона должна быть смежной с другими зонами, но она не обязательно должна быть физически смежной; соединение с магистральной зоной может быть установлено и с помощью виртуальных каналов (virtual links).

Состояния OSPF соседа

Во время формирования соседских отношений OSPF роутеры (маршрутизаторы) проходят следущие состояния: Down, Attempt, Init, 2-Way, Exstart, Exchange, Loading, и Full.

Down state

Первое состояние OSPF соседа. В данном состоянии обмена Hello пакетами еще не производилось или соседские отношения развалились (состояние Full), по причине истечения RouterDeadInterval . Hello-пакеты в данном состоянии принимаются.

Attempt state

Это состояние проходят вручную прописанные в конфигурацию роутера OSPF работающего в NBMA среде (Nonbroadcast Multiple Access Network (NBMA) – среда не поддерживающая распространение multicast и broadcast трафика). В этом состоянии роутер посылает юникаст (unicast) hello-пакеты со своего unicast адреса на unicast адрес соседа.

Init state

Состояние инициализации, когда роутер получил hello пакет от соседа на один из интерфейсов OSPF, но RID получателя ещё небыл включен (вписан) в hello-пакет. Роутер вставляет RID соседа, от которого был получен hello-пакет, в свой hello-пакет как подтверждение того, что он был получен.

2Way state

В данном состоянии между роутерами установлен двунаправленный обмен, т.к. при разборе пришедшего hello-пакета содержится RID этого роутера, т.е. оба роутера получили hello-пакеты друг от друга. Именно в конце установки этого состояния в broadcast среде проиходят выборы DR и BDR если они ещё отсутствуют в Area в которой находятся интерфейсы роутера на которые были получены hello-пакеты.

В NBMA среде выборов DR и BDR не производится.

Exstart state

После выборов DR и BDR, между роутерами и DR, BDR начинается процесс обмена пакетами DBD (Database Descriptor) c информацией о состоянии каналов. В этом состоянии, роутеры и их DR и BDR устанавливают отношения master-slave . Роутер с самым большим Router ID (RID) становиться master и начинает обмен.

Exchange state

В этом состояни, OSPF роутеры обмениваются пакетами дескрипторами базы данных (DBD). Дескрипторы базы данных содержат только заголовки LSA, которые описывают содержимое всей базы данных о состоянии каналов. Каждый DBD пакет имеет номер, который увеличивается только master роутером и обязатесльно подтверждается slave`вом. Роутеры посылают link-state request пакеты и link-state update пакеты, они содержат всю LSA. Содержимое полученного DPD сравнивается с информацией содержащейся в link-state database роутера, идет поиск, имеются ли новые сведения о состоянии каналов доступных соседу.

Происходит непосредственно обмен информацией о состоянии канала. Основываясь на информации полученной через DBD, роутеры посылают link-state request пакеты о состоянии канала. Затем сосед предоставляет запрошенную link-state информацию в link-state update пакетах. Во время adjacency, если роутер принял устаревшую или отсутствующую LSA, он запрашивает эту LSA, посылая link-state request пакет. Все link-state update пакеты нуждаются в обязательном подтвеждении (acknowledgment).

Full state

В этом состоянии соседские отношения полностью установлены. Роутеры обменялись LSA и база данных, на роутерах, полностью синхронизирована. Состояние Full является нормальным состоянием для OSPF роутера.

Роутер может «застрять» в каком-то из состояний, это указывает на проблему в формировании связности (adjacency). Исключением является состояние 2Way , которое является обычным для соседей в broadcast среде. Состояние Full устанавливается только с DR и BDR. С остальными соседями в этой среде будет установлено состояние 2WAY/DROTHER.

В broadcast среде, все OSPF роутеры общаются через multicast адрес 224.0.0.5, но DR и BDR, для общения между собой, используют multicast адрес 224.0.0.6. Благодаря тому, что в broadcast среде работает multicast, определение и нахождение OSPF соседей происходит автоматически.

OSPF (Open Shortest Path First) – протокол динамической маршрутизации, основанный на технологии отслеживания состояния канала (link-state technology) и использующий для нахождения кратчайшего пути алгоритм Дейкстры.

Последняя версия протокола представлена в RFC 2328. OSPF представляет собой протокол внутреннего шлюза (Interior Gateway Protocol – IGP), распространяет информацию о доступных маршрутах между маршрутизирующими устройствами (маршрутизаторами) одной автономной системы.

OSPF предлагает решение следующих задач:

увеличение скорости сходимости сети (т.е. одинаковое понимание текущей сетевой топологии всеми маршрутизаторами) по сравнению с протоколом RIP;

поддержка сетевых масок переменной длины (VLSM, применяются в бессклассовой IP-адресации);

достижимость сети;

оптимальное использование пропускной способности сети;

определение кратчайшего маршрута.

Терминология протокола OSPF

Объявление о состоянии канала (Link-State Advertisement, LSA) – объявление описывает все каналы маршрутизатора, все интерфейсы и состояние каналов.

Состояние канала (Link state) – состояние канала между двумя маршрутизаторами; обновления происходят при помощи пакетов LSA.

Метрика (metric) – условный показатель "стоимости" пересылки данных по каналу;

Автономная система (Autonomous System, AS) – группа устройств, обменивающаяся маршрутизирующей информацией в соответствии с единой политикой и протоколом маршрутизации.

Зона (area) – совокупность сетей и маршрутизаторов, имеющих один и тот же идентификатор зоны.

Соседи (neighbours) – два маршрутизатора, имеющие интерфейсы в общей сети.

Состояние соседства (adjacency) – взаимосвязь между определенными соседними маршрутизаторами, установленная с целью обмена информацией маршрутизации.

Hello-пакеты (Hello packets) – используются для обмена информации и поддержания соседских отношений.

База данных соседей (Neighbours database) – список всех соседей.

База данных состояния каналов (Link State Database, LSDB) – список всех записей о состоянии каналов. Встречается также термин топологическая база данных (topological database), употребляется как синоним базы данных состояния каналов.

Идентификатор маршрутизатора (Router ID, RID) – уникальное 32-битовое число, которое уникально идентифицирует маршрутизатор в пределах одной автономной системы.

Выделенный маршрутизатор (Designated Router, DR) – управляет процессом рассылки LSA в сети. Каждый маршрутизатор сети устанавливает отношения соседства с DR и отправляет ему информацию об изменениях в сети, а DR отвечает за то, чтобы данная информация была отправлена остальным маршрутизаторам сети. Недостатком в схеме работы с DR маршрутизатором является то, что при выходе его из строя должен быть выбран новый DR. Новые отношения соседства должны быть сформированы и, пока базы данных маршрутизаторов не синхронизируются с базой данных нового DR, сеть будет недоступна для пересылки пакетов. Для устранения этого недостатка выбирается BDR.

Резервный выделенный маршрутизатор (Backup Designated Router, BDR). Каждый маршрутизатор сети устанавливает отношения соседства не только с DR, но и BDR. DR и BDR также устанавливают отношения соседства между собой. При выходе из строя DR, BDR становится выделенным маршрутизатором и выполняет все его функции. Так как маршрутизаторы сети устанавливают отношения соседства с BDR, то время недоступности сети минимизируется.

Краткое описание работы протокола OSPF

Маршрутизаторы обмениваются hello-пакетами через все интерфейсы, на которых активирован OSPF. Устройства, разделяющие общий канал передачи данных, становятся соседями после согласования определенных параметров, указанных в hello-пакетах.

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

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

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

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

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

Учитывая, что в сетях с множественным доступом отношения соседства должны быть установлены между всеми маршрутизаторами, существует проблема рассылки огромного количества копий LSA. Для предотвращения этой проблемы в сетях выбираются выделенный (DR) и резервный выделенный (BDR) маршрутизаторы.

Типы зон

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

Разделение на зоны позволяет:

снизить нагрузку на ЦПУ маршрутизаторов за счет уменьшения количества перерасчетов по алгоритму SPF;

уменьшить размер таблиц маршрутизации;

уменьшить количество пакетов обновлений состояния канала.

Каждой зоне присваивается идентификатор зоны (Area ID) и может быть указан в десятичном формате или в формате записи IP-адреса. Однако идентификаторы зон не являются IP-адресами и могут совпадать с любым назначенным IP-адресом.

В любых OSPF-сетях обязательно должна быть определена магистральная зона (Backbone area), известная также как нулевая зона (Area 0) или зона 0.0.0.0, которая формирует ядро сети OSPF. Все остальные зоны должны быть соединены с ней при помощи маршрутизатора, через который обеспечивается межзональная маршрутизация. Если область не связана физически с магистралью, то необходимо добавить виртуальное соединение.

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

Транзитная зона (Transit area) передает информацию из зон, не связанных непосредственно с магистральной зоной.

Типы маршрутизаторов

Все интерфейсы внутреннего маршрутизатора (Internal Router, IR) принадлежат одной зоне. У таких маршрутизаторов только одна база данных состояния каналов.

Граничный маршрутизатор (Area Border Router, ABR) соединяет одну или больше зон с магистральной зоной и выполняет функции шлюза для межзонального трафика. У граничного маршрутизатора всегда хотя бы один интерфейс принадлежит магистральной зоне. Для каждой присоединенной зоны маршрутизатор поддерживает отдельную базу данных состояния каналов.

Граничный маршрутизатор автономной системы (AS Boundary Router, ASBR) обменивается информацией с маршрутизаторами других автономных систем. ASBR может находиться в любом месте автономной системы и быть внутренним, граничным или магистральным маршрутизатором.

Магистральный маршрутизатор (Backbone Router, BR) используется в магистральной зоне.

Рис. 4.1. Сеть OSPF

OSPF поддерживает следующие методы аутентификации:

0 (в межсетевых экранах NetDefend: No Authentification) – для обмена информацией не требуется аутентификация OSPF;

1 (в межсетевых экранах NetDefend: Passphrase) – для аутентификации OSPF требуется простой пароль;

2 (в межсетевых экранах NetDefend: MD5 Digest) – MD5-аутентификация содержит идентификатор ключа (key ID) и 128-битный ключ. Определенный ключ используется для создания 128-бит MD5-хэша. Но назначение аутентификации не означает, что OSPF-пакеты шифруются. В случае необходимости передачи шифрованного OSPF-трафика, его направляют через VPN-туннель (например, IPSec).

Существует два класса протоколов маршрутизации внутри автономных систем: Distance Vector , к которому относятся RIP, EIGRP и Link State , к которому относятся OSPF и IS-IS. Идеология Link State подразумевает, что каждый маршрутизатор должен не просто знать самые лучшие маршруты во все удалённые сети, но и иметь в памяти полную карту сети со всеми существующими связями между другими маршрутизаторами в том числе. OSPF – наиболее распространённый протокол маршрутизации. Это связанно с тем, что его основной конкурент EIGRP вплоть до 2013 года был закрытым протоколом и мог использоваться только на оборудовании Cisco, в то время, как OSPF – это открытый протокол, и он изначально поддерживался как Cisco, так и другими производителями. Таким образом, OSPF завоевал популярность не смотря на некоторые его недостатки в сравнении с EIGRP: меньшую гибкость, отсутствие четкого описания механизма подсчёта метрики, повышенные требования к ресурсам маршрутизатора. В то же время, у OSPF есть и множество достоинств: иерархический дизайн сети (реализуется с помощью зон), удобство при отладке (так как можно видеть карту сети).

Стандартное значение административной дистанции для протокола OSPF – 110, что означает, что его маршруты считаются более приоритетными чем IS-IS, RIP, External EIGRP, Internal BGP, но менее приоритетными чем IGRP, EIGRP BGP. Такая административная дистанция – скорее преференция со стороны Cisco к своим протоколам. Так как с точки зрения здравого смысла, OSPF, конечно предпочтительнее RIP, в современных сетях, но он так же должен быть и предпочтительнее IGRP, который, в силу своего возраста является классовым протоколом маршрутизации. OSPF является бесклассовым (classless) протоколом маршрутизации, что означает передачу вместе с апдейтами информацию о маске подсети (префиксе), в то время, как старые классовые протоколы маршрутизации, опираются на стандартные классы сетей (A, B, C) и по этой причине в настоящее время малоприменимы.

Принцип работы OSPF

Логика работы протокола OSPF следующая:

Маршрутизаторы обмениваются маленькими HELLO-пакетами
Обменявшись пакетами, они устанавливают соседские отношения, добавляя каждый друг друга в свою локальную таблицу соседей
Маршрутизаторы собирают состояния всех своих линков (связей с соседями), включающие в себя id Маршрутизатора, id соседа, сеть и префикс между ними, тип сети, стоимость линка (метрику) и формируют пакет, называемый LSA (Link State Advertisement).
Маршрутизатор рассылает LSA своим соседям, те распространяют LSA дальше.
Каждый маршрутизатор, получивший LSA добавляет в свою локальную табличку LSDB (Link State Database) информацию из LSA.
В LSDB скапливается информация, обо всех парах соединённых в сети маршрутизаторов, то есть каждая строчка таблицы - это информация вида: «Маршрутизатор A имеет соединение со своим соседом маршрутизатором B, между ними сеть такая-то с такими-то свойствами».
После обмена LSA, каждый маршрутизатор знает про все линки, на основании пар строится полная карта сети, включающая все маршрутизаторы и все связи между ними.
На основании этой карты каждый маршрутизатор индивидуально ищет кратчайшие с точки зрения метрики маршруты во все сети и добавляет их в таблицу маршрутизации.

Как видно из описания алгоритма, он достаточно сложный и ресурсоёмкий. Это объясняет высокие требования OSPF к производительности маршрутизатора и оперативной памяти. Теперь, давайте представим, что происходит, если у одного из маршрутизаторов пропадает связь с соседом:

Он рассылает всем новые LSA
Все заново строят карту сети
Заново считают кратчайшие маршруты во все сети
Обновляют свою таблицу маршрутизации

Понятно, что если у нас в много маршрутизаторов, много разных сетей, то такая ситуация будет происходить достаточно часто, вызывая постоянный пересчёт на всех маршрутизаторах и существенно их нагружая. По этой причине, в больших сетях используется разделение на зоны (area ), в каждой зоне вычисления производятся автономно, а между зонами распространяется только результат этих вычислений, таким образом, использование зон важно в случае больших сетей. Об использовании нескольких зон стоит прочесть , пока же мы будем пользоваться одной корневой зоной с номером 0 – эта нулевая зона обязана присутствовать в конфигурации OSPF, и маленькие сети обычно находятся целиком в ней одной.

OSPF пакет помещается в IP пакет, у которого адрес отправителя – адрес отправившего пакет маршрутизатора, а адрес получателя, как правило, мультикастовый. Пакет помещается в соответствующий мультикастовый фрейм, например, Ethernet. Следует обратить внимание, что OSPF напрямую инкапсулируется в IP, а не в TCP или UDP. Этот момент важен при написание списков контроля доступа.

Виды OSPF сообщений

Всего существует пять типов OSPF сообщений:

Hello – отправляются регулярно для поиска соседей и установки соседских отношений
Database Description DBD – используются для проверки синхронизации LSDB у соседних маршрутизаторов
Link state request LSR – принудительный запрос у некого маршрутизатора его LSA. Может использоваться, например, когда маршрутизатор только включился и ему надо узнать текущие связи в сети, или, когда у маршрутизатора пропала сеть, и он хочет узнать нет ли у других маршрутизаторов альтернативных маршрутов к ней.
Link state update LSU – содержит состояния связей маршрутизатора.
Link State Acknowledgment LSAck – пакет-подтверждение, высылается в ответ на другие типы пакетов. Это связано с тем, что OSPF не использует протокол TCP и для надёжной доставки нужен свой собственный механизм подтверждений.

OSPF Hello и Dead интервалы

Hello пакеты рассылаются маршрутизаторами регулярно. Периодичность можно менять в соответствии с задачами, но по умолчанию они шлются раз в 10 секунд в сетях со множественным доступом (BMA) и сетях точка-точка (point-to-point) и раз в 40 секунд в сетях со множественным доступом без возможности широковещательной рассылки (NBMA). Если маршрутизатор не получает ни одного пакета в течении Dead-интервала, то считается, что сосед пропал и отношения разрываются, что влечёт за собой потерю, линка, отправку LSU, пересчёт топологии и т.д. Dead-интервал по умолчанию равен четырём Hello-интервалам, (40 секунд для BMA и 120 для NBMA).

ID маршрутизатора в OSPF

Так как маршрутизаторы строят карту сети, где в качестве узлов используются другие маршрутизаторы, то очень важно, чтобы все они имели уникальные имена. Это необходимо для того, чтобы глядя на полученные из разных источников LSA, понять, что речь идёт об одних и тех же устройствах. В качестве такого уникального имени в OSPF используется поле «Router ID». Идентификатор маршрутизатора выглядит как ip адрес, то есть, состоит из четырёх октетов, разделённых точками. Причём, даже в OSPF для IPv6 идентификатор выглядит как IPv4 адрес. Идентификатор всегда должен присутствовать. Не так важно, какой он будет, важна уникальность идентификаторов в пределах сети. Его можно задать вручную, либо, если этого не сделать, он будет присвоен автоматически.

В общем случае, алгоритм назначения маршрутизатору идентификатора следующий (в порядке приоритета):

Если ID задан явно с помощью команды router-id, то используется именно он
Если router-id не вводился, то берётся самый большой адрес из всех loopback интерфейсов, настроенных на данном маршрутизаторе
Если loopback интерфейсов нет, то берётся самый большой адрес из всех включенных интерфейсов на данном маршрутизаторе. Причём, интерфейс не обязательно должен входить в OSPF процесс, не обязательно его сеть должна быть перечислена при настройке OSPF, достаточно чтобы был настроен адрес и интерфейс был включен.

Здесь под самым большим адресом подразумевается буквальное сравнение по октетам, то есть, например, 10.10.10.20>10.10.10.10, а 2.0.0.1>1.100.100.100, то есть сравниваем по октетам слева направо, как только увидели разницу, то сразу принимаем решение о том, кто больше и дальше не проверяем.

Работа OSPF в сетях со множественным доступом

Одна из проблем подхода OSPF к построению карты сети – использование его в сетях с множественным доступом. Часто используется топология, когда множество маршрутизаторов не подключаются последовательно друг к другу, а соединены через некоторую общую сеть, например, все имеют отдельный интерфейс в некоторой IP-сети для обмена трафиком друг с другом, все подключены один коммутатор, через который обмениваются, или все имеют интерфейс в некотором общем VLAN. В этом случае, OSPF в теории должен устанавливать соседские отношения по принципу «каждый с каждым» в пределах этой общей сети, что приводит к огромным таблицам соседей, повышенной нагрузке на канал, на память и процессор. Ниже приведена таблица, в которой показана зависимость количества соседских отношений от количества маршрутизаторов в одной сети, общая формула для количества отношений имеет вид n(n-1)/2.

Для того чтобы преодолеть эту проблему в OSPF существует механизм выбора Designated Router (DR) и Backup Designated Router (BDR). DR и BDR – это роли маршрутизаторов. Когда имеется сеть со множественным доступом и в ней более двух маршрутизаторов, то один выбирается на роль DR, а второй – на BDR. Каждый маршрутизатор, который хочет отправить, например, LSA, шлёт его не всем в сети, а на специальный мультикастовый адрес, который слушает только DR и BDR, а DR рассылает LSA всем в сети. Таким образом у нас получается не связь «каждый с каждым», а связь «каждый с DR» + «DR с каждым», что позволяет существенно снизить нагрузку в случае, если маршрутизаторов в таком сегменте много. BDR же ничего никому не шлёт – он только слушает то же что и DR и в случае выхода из строя DR-а, BDR мгновенно занимает его место, а среди оставшихся маршрутизаторов проходят выборы нового BDR.

Метрика в OSPF

Сам по себе открытый протокол OSPF не предъявляет никаких требований к тому, как должна считаться метрика и как должно оцениваться «качество маршрута», в стандарте просто говорится, что у каждого линка есть некая стоимость (cost), если маршрут проходит через несколько линков, то их стоимость суммируется. Самым лучшим считается тот маршрут, у которого стоимость меньше остальных. Понятно, что мы имеем дело с той же метрикой, только без внятного механизма его подсчёта. Разные производители могут по разному считать стоимость, поэтому Cisco предусмотрела два варианта вычисления стоимости:

Стоимость считается как обратная величина от скорости линка, например, 1 – для гигабита, 10 – для ста мегабит, 100 – для десяти мегабит, 1000 – для одного мегабита и т.п. Такой вариант хорош, когда мы строим сеть только на оборудовании cisco и знаем, что все маршрутизаторы считают метрику по такому алгоритму. В этом случае стоимость будет считаться автоматически, что существенно упростит настройку.
Стоимость задаётся администратором вручную для каждого линка исходя из своих представлений о качестве этого линка. Такой вариант может применяться в случае, если качество линка не измеряется одной его скоростью. Например, администратор может искуственно завысить метрику для линка, на котором проводится таррификация трафика, или на котором часто возникают ошибки. Это даёт большую гибкость, но требует ручной настройки. Второй случай, когда приходится исползовать этот метод – присутствие в сети маршрутизаторов разных производителей. В этой ситуации надо обеспечить адекватный одинаковые представления о стоимости на всех маршрутизаторах. Надо изучить, как считается стоимость у других производителей, посчитать её так же и задать вручную на маршрутизаторах Cisco.

При выборе первого способа стоимость считается так: берётся величина в 1 гигабит и делится на скорость интерфейса. Этот подход был придуман в те времена, когда 1 гигабит был максимальной скоростью, которую только можно представить. Если считать метрику таким образом, то стоимость гигабиат будет равна единице, но и стоимость 10 гигабитного канала тоже будет равна единице (так как стоимость – целое положительное число). Для того чтобы изменить то значение, которое делится на скорость линка, есть команда auto-cost reference-bandwidth, после которой указывается скорость в мегабитах. То есть, чтобы 1 Гбит отличался от 10 Гбит по стоимости, надо ввести команду:

Router(config-router)#auto-cost reference-bandwidth 10000 % OSPF: Reference bandwidth is changed. Please ensure reference bandwidth is consistent across all routers.

После этого у 10 Гбит будет стоимость 1, у 1 Гб – стоимость 10, у 100 Мб – стоимость 100 и т.д. Важно ввести одинаковое значение на всех маршрутизаторах, чтобы метрика считалась не противоречиво.

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

Введение

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

Основными отличиями от протоколов семейства distance-vector являются:

Возможность использования шаблонной маски для более тонкой настройки;
Высокая скорость сходимости протокола;
Экономия сетевых ресурсов;
Использование мультикаста вместо широковещательных запросов;
Обновление информации по мере изменения топологии сети;
Использование стоимость (cost) в качестве метрики.

OSPF использует так называемые пакеты Link-State Advertisement (LSA) для обмена данными между ближайшими соседями. К слову, список всех напрямую подключенных соседей каждый маршрутизатор хранит в специальной таблице под названием neighbor table . Благодаря обмену пакетами LSA и информации, полученной от соседей, маршрутизаторы выстраивают таблицу топологии сети topology table и заносят данные в базу Link-State Database (LSDB) . Обмен пактетами LSA происходит до тех пор, пока все маршрутизаторы, находящиеся в одной области , не выстроят идентичные базы LSDB. После этого, каждый из них выстроит таблицу маршрутизации routing table , согласно полученной информации. По сути, таблица топологии сети представляет собой базу данных, в которой отражены все маршрутизаторы области и пути их достижения. Таблица топологии сети отличается от таблицы маршрутизации тем, что в первой, маршрутизатор еще не принял решение, какой использовать оптимальный путь для достижения той или иной сети.

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

1. Произошло изменение в топологии сети (потеря физической связи с соседом, сосед не откликается на hello сообщения);
2. Получен пакет LSA от другого соседа* , который должен быть передан по цепочке следующему, до тех пор, пока все маршрутизаторы не обновят свои таблицы топологии сети;
3. Прошло 30 минут без изменений в сети.

* Если номер последовательности LSA новый, тогда маршрутизатор передаст его всем своим соседям.

* Если номер последовательности LSA совпадает с недавней записью в таблице топологии, то этот пакет игнорируется.

* Если номер последовательности более старый, тогда маршрутизатор сгенерирует и отошлет новую версию LSA обратно тому, от кого были получены устаревшие данные.

Итак, каждый маршрутизатор содержит 3 таблицы:

Таблица соседей (Neighbor table);
Таблица топологии (Topology table);
Таблица маршрутизации (Routing table).

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

От стадии знакомства до момента полного «взаимопонимания», маршрутизаторы преодолевают несколько этапов:

Down – обмен OSPF пакетами не происходит;
Init – обмен hello пакетами;
2Way – связь установлена;
Exstart – выбор DR (главного устройства) и BDR (backup устройства) в сетях с множественным доступом (multi-access networks);
Exchange – обмен Database Descriptor (DBD) пакетами, которые содержат по сути заголовки LSA пакетов и описывают содержание контента базы данных Link-state;
Full - достижение полной взаимосвязи, все базы данных синхронизированны.

Метрику или стоимость одного линка, маршрутизатор рассчитывает по формуле 100.000.000bps(100Mbps)/LinkSpeed . Подсчитав суммарную стоимость линков до удаленной сети, маршрутизатор выберет оптимальный маршрут.

Designated Router и Backup Designated Router

Выше были упомянуты аббревиатуры DR (Designated Router) и BDR (Backup Designated Router) . Это роли, которые могут исполнять маршрутизаторы, если они находятся в одном широковещательном сегменте. Выбор одного устройства, который будет исполнять роль DR существенно снизит нагрузку на сеть. Достигается это тем, что маршрутизаторы, находящиеся в одном сегменте, будут устанавливать взаимосвязи (adjacencies) не друг с другом, а только с DR. Выбор же BDR повысит отказоустойчивость сети, т.к. он мгновенно займет место DR, в случае выхода его из строя.

Выборы DR и BDR проводятся согласно следующим критериям:

Приоритет (Priority) - определяет, какой маршрутизатор займет роль DR. Чем больше значение, тем лучше. По умолчанию приоритет равен 1.
Если приоритеты равны, предпочтение будет отдано маршрутизатору с наибольшим Router ID (обычно равен IP адресу).
Маршрутизатор, занявший второе место после DR, становится BDR.

При отсутствии DR и BDR в multi-access сети, количество взаимосвязей возростало бы в геометрической прогрессии относительно количества маршрутизаторов. Число взаимосвязей исчислялось бы по формуле (n(n-1))/2 , где n – количество маршрутизаторов.

Например:

DR уменьшит количество взаимосвязей до 3-х:

В отказоустойчивой модели, количество связей будет равно 5-ти:

Все маршрутизаторы в сегменте отправляют LSA пакеты на адрес 224.0.0.6 (для DR), в свою очередь, DR извещает маршрутизаторы посредством отсылки LSA на адрес 224.0.0.5 . После чего, каждый маршрутизатор в сети должен отправить подтверждение для DR о получении пакета.

DR не изменит свою роль, даже если в сети появится маршрутизатор с лучшим приоритетом. Если DR перестанет отсылать hello пакеты, его место займет BDR.

Области OSPF

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

Алгоритм SPF используется маршрутизатором для расчета кратчайшего пути до удаленной сети.

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

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

OSPF различает два типа областей: нулевая область и все остальные области. Нулевая область представляет из себя центральную область. Все остальные области должны быть смежны с ней. Маршрутизаторы, которые стоят на границе области, смежной с нулевой, называются Area Border Routers (ABR) . Маршрутизаторы, которые импортируют маршруты из других сетевых протоколов, отличных от OSPF, называются Autonomous System Boundary Routers (ASBR) .

Открытый протокол, базирующийся на алгоритме поиска наикратчайшего пути (Open Shortest Path Fisrt - OSPF) является протоколом маршрутизации, разработанным для сетей IP рабочей группой Internet Engineering Task Force (IETF), занимающейся разработкой протоколов для внутрисистемных роутеров (interior gateway protocol - IGP).

Как видно из его названия, OSPF имеет две основных характеристики. Первая из них-это то, что протокол является открытым, т.е. его спецификация является общественным достоянием. Второй его главной характеристикой является то, что он базируется на алгоритме SPF. Алгоритм SPF иногда называют алгоритмом Dijkstra по имени автора, который его разработал.

Основы технологии

OSPF является протоколом маршрутизации с об"явлением состояния о канале (link-state). Это значит, что он требует отправки об"явлений о состоянии канала (link-state advertisement - LSA) во все роутеры, которые находятся в пределах одной и тойже иерархической области. В oб"явления LSA протокола OSPF включается информация о подключенных интерфейсах, об использованных показателях и о других переменных. По мере накопления роутерами OSPF информации о состоянии канала, они используют алгоритм SPF для расчета наикратчайшего пути к каждому узлу.

Являясь алгоритмом с об"явлением состояния канала, OSPF отличается от RIP и IGRP, которые являются протоколами маршрутизации с вектором расстояния. Роутеры, использующие алгоритм вектора расстояния, отправляют всю или часть своей таблицы маршрутизации в сообщения о корректировке маршрутизации, но только своим соседям.

В отличие от RIP, OSPF может работать в пределах некоторой иерархической системы. Самым крупным об"ектом в этой иерархии является автономная система (Autonomous System - AS) AS является набором сетей, которые находятся под единым управлением и совместно используют общую стратегию маршрутизации. OSPF является протоколом маршрутизации внутри AS, хотя он и способен принимать маршруты из других AS и отправлять маршруты в другие AS.

Любая AS может быть разделена на ряд зон или областей(area). Зона - это группа смежных сетей и подключенных к ним хостов. Роутеры, имеющие несколько интерфейсов, могут участвовать в нескольких зонах. Такие роутеры, которые называются пограничными областными роутерами (area border routers), поддерживают отдельные топологические базы данных для каждой области.

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

Термин "домен" (domain) исользуется для описания части сети, в которой все роутери имеют идентичную топологическую базу данных. Термин "домен" часто используется вместо AS.

Топология области является невидимой для об"ектов, находящихся вне этой области. Путем хранения топологий областей отдельно, OSPF добивается меньшего трафика маршрутизации, чем трафик для случая, когда AS не разделена на области.

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

Магистральная часть OSPF (backbone) отвечает за распределение маршрутной информации между областями. Она включает в себя все роутеры границы области, сети, которые не принадлежат полностью како-либо из областей, и подключенные к ним роутеры. На Рис 1 представлен пример об"единенной сети с несколькими областями.

На этом рисунке роутеры 4, 5, 6, 10, 11 и 12 образуют магистраль. Если хост Н1 Области 3 захочет отправить пакет хосту Н2 Области 2, то пакет отправляется в роутер 13, который продвигает его в роутер 12, который в свою очередь отправляет его в роутер 11. Роутер 11 продвигает пакет вдоль стержня к роутеру 10 границы области, который отправляет пакет через два внутренних роутера этой области (роутеры 9 и 7) до тех пор, пока он не будет продвинут к хосту Н2.

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

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

Граничные роутеры AS, использующие OSPF, узнают о внешних маршрутах через протоколы внешних роутеров (EGPs), таких, как Exterior Gateway Protocol (EGP) или Border Gateway Protocol (BGP), или через конфигурацию.

Windows