OSPF — это открытый протокол маршрутизации, базирующийся на алгоритме поиска наикратчайшего пути (Open Shortest Path First — OSPF). OSPF имеет две основные характеристики: протокол является открытым, т. е. его спецификация является общественным достоянием, он базируется на алгоритме SPF. Алгоритм SPF иногда называют алгоритмом Dijkstra по имени его автора.

OSPF является иерархическим протоколом маршрутизации с объявлением состояния о канале соединения (link-state). Он был спроектирован как протокол работы внутри сетевой области — AS (Autonomous System), которая представляет собой группу маршрутизаторов и сетей, объединенных по иерархическому принципу и находящихся под единым управлением и совместно использующих общую стратегию маршрутизации. В качестве транспортного протокола для маршрутизации внутри AS OSPF использует IP-протокол.

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

Для различных типов IP-сервиса (видов услуг высшего уровня, которые определяются значением поля TOS IP-пакета), OSPF может рассчитывать свои оптимальные маршруты на основании параметров, наиболее критичных для данного вида сервиса. Например, какая-нибудь прикладная программа может включить требование о том, что определенная информация является срочной. Если OSPF имеет в своем распоряжении каналы с высоким приоритетом, то они могут быть использованы для транспортировки срочных дейтаграмм.

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

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

Алгоритм маршрутизации SPF является основой для операций OSPF. В каждой области работает отдельная копия алгоритма маршрутизации. Маршрутизаторы, которые имеют интерфейсы к нескольким областям, работают с несколькими копиями алгоритма SPF.

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

После получения подтверждения о работоспособности своих интерфейсов, роутер использует приветственный протокол (hello protocol) OSPF, чтобы приобрести соседей (neighbor). Соседи — это объекты сети с интерфейсами, предназначенными для работы в общей с данным маршрутизатором сети. Описываемый маршрутизатор отправляет своим соседям приветственные пакеты и получает от них такие же пакеты. Помимо оказания помощи в приобретении соседей, приветственные пакеты также действуют как подтверждение дееспособности, позволяя другим роутерам узнавать о том, что другие роутеры функционируют.

Каждый роутер периодически, в зависимости от настройки системы, отправляет сообщение о состоянии канала (LSA — messages). Эти сообщения содержат информацию о состоянии интерфейса маршрутизатора данного маршрутизатора и смежных с ним объектов сети. Каждое такое сообщение рассылается маршрутизаторам всей области. Из LSA-сообщений всех объектов формируется топологическая база данных (дерево маршрутов). Сообщения LSA также отправляются в том случае, когда изменяется состояние какого-нибудь роутера.

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

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

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

Пример маршрутизации по алгоритму OSPF

Представим себе один день из жизни транзитной локальной сети. Пусть у нас имеется сеть Ethernet, в которой есть три маршрутизатора - Джон, Фред и Роб (имена членов рабочей группы Internet, разработавшей протокол OSPF). Эти маршрутизаторы связаны с сетями в других городах с помощью выделенных линий.

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

Гипотетическая сеть с OSPF маршрутизаторами

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

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

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

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

Посмотрим теперь, как Робин вычисляет маршрут через сеть. Две из связей, присоединенных к его портам, представляют линии T-1, а одна - линию 56 Кб/c. Робин сначала обнаруживает двух соседей - Роба с метрикой 65 и Мило с метрикой 1785. Из объявления о связях Роба Робин обнаружил наилучший путь к Мило со стоимостью 130, поэтому он отверг непосредственный путь к Мило, поскольку он связан с большей задержкой, так как проходит через линии с меньшей пропускной способностью. Робин также обнаруживает транзитную локальную сеть с выделенным маршрутизатором Джоном. Из объявлений о связях Джона Робин узнает о пути к Фреду и, наконец, узнает о пути к маршрутизаторам Келли и Джеффу и к их тупиковым сетям.

После того, как маршрутизаторы полностью входят в рабочий режим, интенсивность обмена сообщениями резко падает. Обычно они посылают сообщение HELLO по своим подсетям каждые 10 секунд и делают объявления о состоянии связей каждые 30 минут (если обнаруживаются изменения в состоянии связей, то объявление передается, естественно, немедленно). Обновленные объявления о связях служат гарантией того, что маршрутизатор работает в сети. Старые объявления удаляются из базы через определенное время.

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

Существует пять типов OSPF-пакетов. Все OSPF-пакеты начинаются со стандартного 24-баитного заголовка.

Version (1 байт). Поле означает номер версии OSPF-пакета протокола, использующего данный пакет.

Type (1 байт). В зависимости от типа, пакет выполняет те или иные функции:

Type = 1 — Hello

Type =2 — Database Description

Type =3 — Link-State Request

Type =4 — Link-State Update

Type =5 — Link-Sate Acknowledgement