OSPF

OSPF
OSPF
Название	Open Shortest Path First
Уровень (по модели OSI)	Сетевой
Семейство	TCP/IP
Создан в	1988
Порт/ID	89
Назначение протокола	Протокол динамической маршрутизации
Спецификация	RFC 2328
Основные реализации (клиенты)	OpenOSPFD, GNU Zebra, Quagga, Cisco IOS, Mikrotik RouterOS
Основные реализации (серверы)	OpenOSPFD, GNU Zebra, Quagga, Cisco IOS, Mikrotik RouterOS, HP Comware
	Медиафайлы на Викискладе

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

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

OSPF имеет следующие преимущества:

Высокая скорость сходимости по сравнению с дистанционно-векторными протоколами маршрутизации;
Поддержка сетевых масок переменной длины (VLSM);
Оптимальное использование пропускной способности с построением дерева кратчайших путей.

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

Интерфейс (interface) — соединение маршрутизатора и одной из подключенных к нему сетей. При обсуждении OSPF термины интерфейс и канал (link) часто употребляются как синонимы.
Объявление о состоянии канала (link-state advertisement, LSA) — объявление описывает все каналы маршрутизатора, все интерфейсы и состояние каналов.
Состояние канала (link state) — состояние канала между двумя маршрутизаторами; обновления происходят при помощи пакетов LSA.
Метрика (metric) — условный показатель «стоимости» пересылки данных по каналу.
Автономная система (autonomous system) — это совокупность сетей под единым административным управлением, обеспечивающим общую для всех входящих в автономную систему маршрутизаторов политику маршрутизации. Обычно автономной системой управляет один поставщик услуг Интернет. Автономная система использует внутренние шлюзовые протоколы IGP (RIP, OSPF и IS-IS).
Зона (area) — совокупность сетей и маршрутизаторов, имеющих один и тот же идентификатор зоны.
Соседи (neighbors) — маршрутизаторы, имеющие интерфейсы в общей сети (зоне).
Состояние смежности (adjacency) — взаимосвязь между определёнными соседними маршрутизаторами, установленная с целью обмена информацией маршрутизации.
Hello-протокол (hello protocol) — используется для поддержания соседских отношений.
База данных соседей (neighbors database) — список всех соседей.
База данных состояния каналов (link state database, LSDB) — список всех записей о состоянии каналов. Встречается также термин топологическая база данных (topological database), употребляется как синоним базы данных состояния каналов.
Идентификатор маршрутизатора (router ID, RID) — уникальное 32-битовое число, которое уникально идентифицирует маршрутизатор в пределах одной автономной системы.

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

Принцип работы заключается в следующем:

После включения маршрутизаторов протокол ищет непосредственно подключенных соседей и устанавливает с ними «дружеские» отношения.
Затем они обмениваются друг с другом информацией о подключенных и доступных им сетях. То есть они строят карту сети (топологию сети). Данная карта одинакова на всех маршрутизаторах.
На основе полученной информации запускается алгоритм SPF (Shortest Path First, «выбор наилучшего пути»), который рассчитывает оптимальный маршрут к каждой сети. Данный процесс похож на построение дерева, корнем которого является сам маршрутизатор, а ветвями — пути к доступным сетям. Данный процесс, то есть конвергенция, происходит очень быстро.

Типы сетей, поддерживаемые протоколом OSPF

Широковещательные сети со множественным доступом (Ethernet, Token Ring)
Точка-точка (T1, E1, коммутируемый доступ)
Не широковещательные сети со множественным доступом (NBMA) (Frame relay)

Выделенный маршрутизатор (DR) и резервный выделенный маршрутизатор ( BDR)

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

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

Выделенный маршрутизатор (designated router, DR) — управляет процессом рассылки LSA в сети. Каждый маршрутизатор сети устанавливает отношения смежности с DR. Информация об изменениях в сети отправляется маршрутизатором, обнаружившим это изменение, на выделенный маршрутизатор, а тот, в свою очередь, отвечает за то, чтобы эта информация была отправлена остальным маршрутизаторам сегмента множественного доступа.

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

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

Маршрутизатор, выбранный DR или BDR в одной присоединённой к нему сети множественного доступа, может не быть DR (BDR) в другой присоединённой сети множественного доступа. Роль DR (BDR) является свойством интерфейса, а не свойством всего маршрутизатора. Иными словами, в каждом сегменте множественного доступа (например, коммутационном сегменте Ethernet), в котором общаются два или более OSPF-маршрутизатора, процесс выбора и распределение ролей 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) — это маршрутизатор, один из портов которого находится в домене OSPF протокола, а другой в домене любого из внутренних шлюзовых протоколов (например RIP или EIGRP). Пограничный маршрутизатор автономной системы может находиться в любом месте автономной системы и быть пограничным или магистральным маршрутизатором.

Типы объявлений о состоянии канала (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 6 LSA — Multicast OSPF LSA — специализированный LSA, который используют мультикаст OSPF приложения (не осуществлено Cisco).

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

Type 8 LSA — Link LSA — анонсирует link-local адрес и префикс(ы) маршрутизатора всем маршрутизаторам разделяющим канал (link). Отправляется только если на канале присутствует более чем один маршрутизатор. Распространяются только в пределах канала (link).

Type 9 LSA — Intra-Area-Prefix LSA ставит в соответствие: список префиксов IPv6 и маршрутизатор, указывая на Router LSA, список префиксов IPv6 и транзитную сеть, указывая на Network LSA. Распространяются только в пределах одной зоны.

Типы зон

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

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

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

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

Существует несколько типов зон:

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

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

Стандартная зона (standard area)

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

Тупиковая зона (stub area)

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

Totally stubby area

Totally stubby area не принимает информацию о внешних маршрутах для автономной системы и маршруты из других зон. Если маршрутизаторам необходимо передавать информацию за пределы зоны, то они используют маршрут по умолчанию. Cisco-proprietary тип зоны.

Not-so-stubby area (NSSA)

Зона NSSA определяет дополнительный тип LSA — LSA type 7. В NSSA зоне может находиться ASBR.

Формат OSPF-пакетов

OSPF-пакет инкапсулируется непосредственно в поле данных IP-пакета. Значение поля «протокол верхнего уровня» в заголовке IP-дейтаграммы для OSPF равно 89.

Заголовок пакета

Октет	0	8	16
0—3	Version	Type	Packet length
4—7	Router ID
8—11	Area ID
12—15	Checksum		Authentication type
16—19	Authentication
20—23	Authentication

Version — номер версии протокола OSPF, текущая версия OSPF для сетей IPv4 — 2;
Type — тип OSPF-пакета;
Packet length — длина пакета, включая заголовок;
Router ID — идентификатор маршрутизатора, уникальное 32-битное число, идентифицирующее маршрутизатор в пределах автономной системы;
Area ID — 32-битный идентификатор зоны;
Checksum — поле контрольной суммы, подсчитывается для всего пакета, включая заголовок;
Authentication type — тип используемой схемы аутентификации, возможные значения:
- 0 — аутентификация не используется
- 1 — аутентификация открытым текстом
- 2 — MD5-аутентификация
Authentication — поле данных аутентификации.

Hello-пакет

Hello-пакет предназначен для установления и поддержания отношений с соседями. Пакет периодически посылается на все интерфейсы маршрутизатора.

Октет	0	8	16	24
0—3	Version	Type = 1	Packet length
4—7	Router ID
8—11	Area ID
12—15	Checksum		Authentication type
16—19	Authentication
20—23	Authentication
24—27	Network mask
28—31	Hello interval		Options	Router priority
32—35	Router dead interval
36—39	Designated router
40—43	Backup designated router
44—47	Neighbor ID
…	…

Network mask — сетевая маска интерфейса, через который отправляется hello-пакет;
Hello interval — интервал задающий частоту рассылки приветственных сообщений для обнаружения соседей в автономной системе, для LAN значение по умолчанию равно 10 секундам;
Options — 8-битное поле опций, описывает возможности маршрутизатора;
Router priority — приоритет маршрутизатора, 8-битное число, символизирующее приоритет маршрутизатора при выборе DR (англ. Designated router) и BDR (англ. Backup designated router);
Router dead interval — период времени, в течение которого маршрутизатор ожидает ответа соседей;
Designated router (DR) — IP-адрес DR;
Backup designated router (BDR) — IP-адрес BDR;
Neighbor ID — идентификатор соседа. Список составляется из идентификаторов соседей, от которых маршрутизатор получил hello-пакеты в течение времени, заданного в поле router dead interval;

Database Description

Пакет Database Description описывает содержание базы данных состояния канала. Обмен пакетами производится при установлении состояния смежности.

Октет	0	8	16	24	25	26	27	28	29	30	31
0—3	Version	Type = 2	Packet length
4—7	Router ID
8—11	Area ID
12—15	Checksum		Authentication type
16—19	Authentication
20—23	Authentication
24—27	Interface MTU		Options	0	0	0	0	0	I	M	MS
28—31	DD sequence number
...	An LSA header

Interface MTU — размер в байтах наибольшей IP дейтаграммы, которая может быть послана через данный интерфейс без фрагментации;
I-бит — устанавливается для первого пакета в последовательности;
M-бит — указывает наличие последующих дополнительных пакетов;
MS-бит — устанавливается для ведущего, сбрасывается для ведомого;
DD sequence number — в начальном пакете устанавливается на уникальное значение, при передаче каждого последующего пакета увеличивается на единицу, пока не будет передана вся база данных;
LSA headers — массив заголовков базы данных состояния каналов.

Link State Request

Пакет Link State Request предназначен для запроса части базы данных соседнего маршрутизатора.

Октет	0	8	16
0—3	Version	Type = 3	Packet length
4—7	Router ID
8—11	Area ID
12—15	Checksum		Authentication type
16—19	Authentication
20—23	Authentication
24—27	LS Type
28—31	Link State ID
32—35	Advertising Router
…	…

LS Type — тип объявления о состоянии канала;
Link State ID — идентификатор домена маршрутизации;
Advertising Router — идентификатор маршрутизатора, создавшего объявление о состоянии канала.

Link State Update

Пакет Link State Update предназначен для рассылки объявлений о состоянии канала. Пакет посылается по групповому адресу на один транзитный участок.

Октет	0	8	16
0—3	Version	Type = 4	Packet length
4—7	Router ID
8—11	Area ID
12—15	Checksum		Authentication type
16—19	Authentication
20—23	Authentication
24—27	Number of LSA
	LSA

Number of LSA — количество объявлений в пакете.

Link State Acknowledgment

Подтверждает получение пакета Link State Update.

Октет	0	8	16
0—3	Version	Type = 5	Packet length
4—7	Router ID
8—11	Area ID
12—15	Checksum		Authentication type
16—19	Authentication
20—23	Authentication
	LSA headers

Версии протокола OSPF

OSPF версия 1
OSPF версия 2 поддерживает версию протокола IPv4
OSPF версия 3 поддерживает версию протокола IPv6

Критика

Считается, что благодаря использованию алгоритма Дейкстры специфического критерия качества распределения входного потока информации, он абсолютно не защищает IP-сеть от перегрузок, что требует реализации дополнительных методов по снижению вероятности перегрузки. Например, предлагается использовать в критерии распределения остаточную пропускную способность канала^[2].

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

См. также

Протокол маршрутизации промежуточных систем (IS-IS)
Shortest Path Bridging (SPB)

Примечания

↑ https://www.iana.org/assignments/protocol-numbers/protocol-numbers.xhtml
↑ Н. А. Кузнецов, В. Н. Фетисов, Системы массового обслуживания, «Алгоритм Дейкстры с улучшенной робастностью для управления маршрутизацией в IP-сетях» ([1] Архивная копия от 8 марта 2016 на Wayback Machine), PACS 02.10.Ox, Автоматика и телемеханика, № 2, 2008.

Литература

Том М. Томас II. Структура и реализация сетей на основе протокола OSPF. Руководство Cisco = OSPF Network Design Solutions. — 2-е изд. — М.: «Вильямс», 2004. — С. 816. — ISBN 1-58705-032-3.

Ссылки

Правила чтения таблиц, описывающих структуру заголовков сетевых протоколов

[_c426810b5789f629-1] ttps://www.iana.org/assignments/protocol-numbers/protocol-numbers.xhtml

[AiT-2-2008-2] Н. А. Кузнецов, В. Н. Фетисов, Системы массового обслуживания, «Алгоритм Дейкстры с улучшенной робастностью для управления маршрутизацией в IP-сетях» ([1] Архивная копия от 8 марта 2016 на Wayback Machine), PACS 02.10.Ox, Автоматика и телемеханика, № 2, 2008.

[1]

[2]