Алгоритм SPF

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

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

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

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

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

Формат пакета

Все пакеты OSPF начинаются с 24-байтового заголовка, показанного на рис. 47.2.

Рис. 47.2. Пакет OSPF содержит девять полей Ниже описаны поля заголовка, показанные на рис. 47.2.

•        Версия. Используемая версия OSPF.

•       Тип. Один из описанных ниже типов пакета OSPF.

— Приветствие. Устанавливает и поддерживает соединение между соседними маршрутизаторами.

—      Описание базы данных. Описывает содержимое топологической базы данных. Обмен этими пакетами производится при инициализации отношений смежности.

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

—      Обновление состояния канала. Отвечает на пакеты запроса о состоянии канала. Эти сообщения также используются для регулярного распространения сообщений LSA. В одном пакете обновления состояния канала может содержаться несколько LSA.

—      Подтверждение состояния канала. Подтверждает пакеты обновления состояния канала.

•     Длина пакета. Длина пакета в байтах, включая заголовок OSPF.

•      ID маршрутизатора. Идентифицирует источник пакета.

•          ID зоны. Идентифицирует зону, которой принадлежит пакет. Все пакеты OSPF связаны с определенной зоной.

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

•          Тип аутентификации. Любой обмен данными по протоколу OSPF проводится с аутентификацией. Тип аутентификации определяется для каждой зоны.

•     Аутентификация. Информация аутентификации.

•     Данные. Инкапсулированная информация высшего уровня.

Дополнительные функции протокола OSPF

Дополнительными функциями OSRF являются маршрутизация по нескольким маршрутам по принципу равных оценок (equal cost), и маршрутизация на базе запросов типа обслуживания (Type of Service — ToS) высшего уровня. Маршрутизация на базе ToS поддерживает те протоколы высшего уровня, которые позволяют задать конкретный тип обслуживания. Например, приложение может объявить некоторые данные как срочные. Если в распоряжении OSPF есть каналы с высоким приоритетом, то они могут быть использованы для передачи срочных дейтаграмм.

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

В адрес каждого объявленного получателя включаются маски IP-подсети, что позволяет использовать маски подсети переменной длины. С помощью масок подсети

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

Литература:

Руководство по технологиям объединенных сетей, 4-е издание. : Пер. с англ. — М.: Издательский дом «Вильяме», 2005. — 1040 с.: ил. – Парал. тит. англ.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100