Алгоритм Дикстры

Рис. 4.2.11.2.1 Иллюстрация работы алгоритма Дикстры

Ниже дается формальное описание алгоритма. Сначала вводим некоторые определения.

Пусть D(v) равно сумме весов связей для данного пути.
Пусть c(i,j) равно весу связи между узлами с номерами i и j.

Далее следует последовательность шагов, реализующих алгоритм.

1. Устанавливаем множество узлов N = {1}.
2. Для каждого узла v не из множества n устанавливаем D(v)= c(1,v).
3. Для каждого шага находим узел w не из множества N, для которого D(w) минимально, и добавляем узел w в множество N.
4. Актуализируем D(v) для всех узлов не из множества N
   D(v)=min{D(v), D(v)+c(w,v)}.
5. Повторяем шаги 2-4, пока все узлы не окажутся в множестве N.

Топология маршрутов для узла a приведена на нижней части рис. 4.2.11.2.1. В скобках записаны числа, характеризующие метрику отобранного маршрута согласно критерию пункта 3.

Таблица 4.2.11.2.1. Реализация алгоритма

Таблица 4.2.11.2.1 может иметь совершенно иное содержимое для какого-то другого вида сервиса, выбранные пути при этом могут иметь другую топологию. Качество сервиса (QoS) может характеризоваться следующими параметрами:

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

Базовые особенности учета состояния канала

Определяющими являются три характеристики: задержка, пропускная способность и надежность. Для транспортных целей OSPF использует IP непосредственно, т.е. не привлекает протоколы UDP или TCP. OSPF имеет свой код (89) в протокольном поле IP-заголовка. Код TOS (type of service) в IP-пакетах, содержащих OSPF-сообщения, равен нулю, значение TOS здесь задается в самих пакетах OSPF. Маршрутизация в этом протоколе определяется IP-адресом и типом сервиса. Так как протокол не требует инкапсуляции пакетов, сильно облегчается управление сетями с большим количеством бриджей и сложной топологией (исключается циркуляция пакетов, сокращается транзитный трафик). Автономная система может быть поделена на отдельные области, каждая из которых становится объектом маршрутизации, а внутренняя структура снаружи не видна (узлы на рис. 4.2.11.2.1 могут представлять собой как отдельные ЭВМ или маршрутизаторы, так и целые сети). Этот прием позволяет значительно сократить необходимый объем маршрутной базы данных. В OSPF используется термин опорной сети (backbone) для коммуникаций между выделенными областями. Протокол работает лишь в пределах автономной системы. В пределах выделенной области может работать свой протокол маршрутизации.

Выделенные области маршрутизации OSPF

Рис. 4.2.11.2.2 Пример выделения областей при OSPF маршрутизации в автономной системе (М - маршрутизаторы; c - сети).

На рис 4.2.11.2.2 (см. также рис. 4.2.11.2.1) приведен пример выделения областей маршрутизации при OSPF-маршрутизации в пределах автономной системы. На рис. 4.2.11.2.2 маршрутизаторы М4 и М2 выполняют функция опорной сети для других областей. В выделенных областях может быть любое число маршрутизаторов. Более толстыми линиями выделены связи с другими автономными системами.

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

Зарезервированные мультикаст-адреса

Любое сообщение OSPF начинается с 24-октетного заголовка:

Форматы заголовков сообщений OSPF

Рис. 4.2.11.2.3 Формат заголовка сообщений для протокола маршрутизации OSPF

Поле версия определяет версию протокола (= 2). Поле тип идентифицирует функцию сообщения согласно таблице 4.2.11.2.2:

Таблица 4.2.11.2.2. Коды поля тип

Поле длина пакета определяет длину блока в октетах, включая заголовок. Идентификатор области - 32-битный код, идентифицирующий область, которой данный пакет принадлежит. Все OSPF-пакеты ассоциируются с той или иной областью. Большинство из них не преодолевает более одного шага. Пакеты, путешествующие по виртуальным каналам, помечаются идентификатором опорной области (backbone) 0.0.0.0. Поле контрольная сумма содержит контрольную сумму IP-пакета, включая поле типа идентификации. Контрольное суммирование производится по модулю 1. Поле тип идентификации может принимать значения 0 при отсутствии контроля доступа, и 1 при наличии контроля. В дальнейшем функции поля будут расширены. Важную функцию в OSPF-сообщениях выполняет одно-октетное поле опции, оно присутствует в сообщениях типа Hello, объявление состояния канала и описание базы данных. Особую роль в этом поле играют младшие биты E и Т:

Бит E характеризует возможность внешней маршрутизации и имеет значение только в сообщениях типа Hello, в остальных сообщениях этот бит должен быть обнулен. Если E=0, то данный маршрутизатор не будет посылать или принимать маршрутную информацию от внешних автономных систем. Бит T определяет сервисные возможности маршрутизатора (TOS). Если T=0, это означает, что маршрутизатор поддерживает только один вид услуг (TOS=0) и он не пригоден для маршрутизации с учетом вида услуг. Такие маршрутизаторы, как правило, не используются для транзитного трафика.

Протокол OSPF использует сообщение типа Hello для взаимообмена данными между соседними маршрутизаторами. Структура пакетов этого типа показана на рис. 4.2.11.2.4.

Рис. 4.2.11.2.4 Формат сообщения Hello в протоколе OSPF

Поле сетевая маска соответствует маске субсети данного интерфейса. Например, если интерфейс принадлежит сети класса B и третий байт служит для выделения нужной субсети, то сетевая маска будет иметь вид 0xFFFFFF00.

Поле время между Hello содержит значение времени в секундах, между сообщениями Hello. Поле опции характеризует возможности, которые предоставляет данный маршрутизатор. Поле приоритет характеризует уровень приоритета маршрутизатора (целое положительное число), используется при выборе резервного (backup) маршрутизатора. Если приоритет равен нулю, данный маршрутизатор никогда не будет использован в качестве резервного. Поле время отключения маршрутизатора определяет временной интервал в секундах, по истечении которого "молчащий" маршрутизатор считается вышедшим из строя. IP-адреса маршрутизаторов, записанные в последующих полях, указывают место, куда следует послать данное сообщение. Поля IP-адрес соседа k образуют список адресов соседних маршрутизаторов, откуда за последнее время были получены сообщения Hello.

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

Сообщения о маршрутах

Рис. 4.2.11.2.5 Формат OSPF-сообщений о маршрутах

Поля, начиная с тип канала, повторяются для каждого описания канала. Так как размер базы данных может быть велик, ее содержимое может пересылаться по частям. Для реализации этого используются биты I и М. Бит I устанавливается в 1 в стартовом сообщении, а бит M принимает единичное состояние для сообщения, которые являются продолжением. Бит S определяет то, кем послано сообщение (S=1 для сервера, S=0 для клиента, этот бит иногда имеет имя MS). Поле номер сообщения по порядку служит для контроля пропущенных блоков. Первое сообщение содержит в этом поле случайное целое число M, последующие M+1, M+2,...M+L. Поле тип канала может принимать следующие значения:

Коды типов состояния каналов

Таблица 4.2.11.2.3. Коды типов состояния каналов (LS)

Поле идентификатор канала определяет его характер, в зависимости от этого идентификатором может быть IP-адрес маршрутизатора или сети. Маршрутизатор, рекламирующий канал определяет адрес этого маршрутизатора. Поле порядковый номер канала позволяет маршрутизатору контролировать порядок прихода сообщений и их потерю. Поле возраст канала определяет время в секундах с момента установления связи. После обмена сообщениями с соседями маршрутизатор может выяснить, что часть данных в его базе устарела. Он может послать своим соседям запрос с целью получения свежей маршрутной информации о каком-то конкретном канале связи. Сосед, получивший запрос, высылает необходимую информацию. Запрос посылается в соответствии с форматом, показанном ниже (рис. 4.2.11.2.6):

Рис. 4.2.11.2.6 Формат OSPF-запроса маршрутной информации

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

Сообщение об изменении маршрутов

Рис. 4.2.11.2.7 Сообщение об изменении маршрутов

Сообщения об изменениях маршрутов могут быть вызваны следующими причинами:

1. Возраст маршрута достиг предельного значения (lsrefreshtime).
2. Изменилось состояние интерфейса.
3. Произошли изменения в маршрутизаторе сети.
4. Произошло изменение состояния одного из соседних маршрутизаторов.
5. Изменилось состояние одного из внутренних маршрутов (появление нового, исчезновение старого и т.д.)
6. Изменение состояния межзонного маршрута.
7. Появление нового маршрутизатора, подключенного к сети.
8. Вариация виртуального маршрута одним из маршрутизаторов.
9. Возникли изменения одного из внешних маршрутов.
10. Маршрутизатор перестал быть пограничным для данной as (например, перезагрузился).

Каждое сообщение о состоянии канала начинается с заголовка - "объявление состояния канала" (LS- link state). Формат этого типа заголовка приведен ниже (20 октетов):

Рис. 4.2.11.2.8 Формат OSPF-сообщения, описывающего состояние канала

Поле возраст ls информации (рис. 4.2.11.2.8) определяет время в секундах с момента объявления состояния канала. Поле опции содержит значения типов сервиса (TOS), поддерживаемые маршрутизатором, рассылающим маршрутную информацию. Поле тип LS (тип состояния канала) может принимать значения, описанные выше в табл. 4.2.11.2.3. Следует обратить внимание, что код, содержащийся в этом поле, определяет формат сообщения. Поле длина задает размер сообщения в октетах, включая заголовок. В результате получается сообщение с форматом, показанным на рис. 4.2.11.2.9. Зарезервированный октет должен быть обнулен. Идентификатор связи определяет тип маршрутизатора, подключенного к каналу. Действительное значение этого поля зависит от поля тип. В свою очередь информация о канале также зависит от поля тип. Число tos определяет многообразие метрик, соответствующих видам сервиса, для данного канала. Последовательность описания метрик задается величиной кода TOS. Таблица кодов TOS, принятых в OSPF протоколе приведена ниже.

Коды типа сервиса

Таблица 4.2.11.2.4. Коды типа сервиса (TOS)

Рис. 4.2.11.2.9 Формат описания типа канала с LS=1

Если бит V=1 (virtual), маршрутизатор является оконечной точкой активного виртуального канала. Если бит E (external) равен 1, маршрутизатор является пограничным для автономной системы. Бит B=1 (border) указывает на то, что маршрутизатор является пограничным для данной области. Поле тип может принимать значения, приведенные в таблице 4.2.11.2.5.

Коды типов связей

Таблица 4.2.11.2.5. Коды типов связей (см. рис. 4.2.11.2.9)

Поле идентификатор канала характеризует объект, с которым связывается маршрутизатор. Примеры идентификаторов представлены в таблице:

Коды идентификаторов канала

Таблица 4.2.11.2.6. Коды идентификаторов канала

Маршрутизатор, получивший OSPF-пакет, посылает подтверждение его приема. Этот вид пакетов имеет тип=5 и структуру, отображенную на рис. 4.2.11.2.10. Получение нескольких объявлений о состоянии линий может быть подтверждено одним пакетом. Адресом места назначения этого пакета может быть индивидуальный маршрутизатор, группа маршрутизаторов или все маршрутизаторы автономной системы.

Рис. 4.2.11.2.10 Формат сообщения о получении OSPF-пакета

Рекламирование сетевых связей относится к типу 2. Сообщения посылаются для каждой транзитной сети в автономной системе. Транзитной считается сеть, которая имеет более одного маршрутизатора. Сообщение о сетевых связях должно содержать информацию обо всех маршрутизаторах, подключенных к сети, включая тот, который рассылает эту информацию. Расстояние от сети до любого подключенного маршрутизатора равно нулю для всех видов сервиса (TOS), поэтому поля TOS и метрики в этих сообщениях отсутствуют. Формат сообщения о транзитных сетевых связях показан на рис. 4.2.11.2.11.

Следует помнить, что приведенные ниже сообщения должны быть снабжены стандартными 24-октетными OSPF-заголовками (на рис. 4.2.11.2.11 отсутствует).

Рис. 4.2.11.2.11 Формат сообщения о сетевых связях (тип LS=2)

Сетевая маска относится к описываемой сети, а поле подключенный маршрутизатор содержит идентификатор маршрутизатора, работающего в сети. Информация об адресатах в пределах автономной системы передается LS-сообщениями типа 3 и 4. Тип 3 работает для IP-сетей. В этом случае в качестве идентификатора состояния канала используется IP-адрес сети. Если же адресатом является пограничный маршрутизатор данной AS, то используется LS-сообщение типа 4, а в поле идентификатор состояния канала записывается OSPF-идентификатор этого маршрутизатора. Во всех остальных отношениях сообщения 3 и 4 имеют идентичные форматы (рис. 4.2.11.2.12):

Рис. 4.2.11.2.12 Формат сообщений об адресатах в пределах автономной системы

Поля, следующие после заголовка, повторяются в соответствии с числом описываемых объектов. Рекламирование внешних маршрутов относится к пятому типу. Эта информация рассылается пограничными маршрутизаторами. Информация о каждом внешнем адресате, известном маршрутизатору, посылается независимо. Этот вид описания используется и для маршрутов по умолчанию, для которых идентификатор состояния канала устанавливается равным 0.0.0.0 (аналогичное значение принимает при этом и сетевая маска). Формат такого сообщения представлен на рис. 4.2.11.2.13.

Формат описания внешних маршрутов

Рис. 4.2.11.2.13 Формат описания внешних маршрутов

Сетевая маска характеризует место назначения рекламируемого маршрута. Так для сети класса A маска может иметь вид 0xFF000000. Последующий набор полей повторяется для каждого вида TOS. Поля для TOS=0 заполняются всегда, и это описание является первым. Бит E характеризует внешнюю метрику. Если E=0, то она может непосредственно (без преобразования) сравниваться с метриками других каналов. При E=1 метрика считается больше любой метрики. Поле адрес пересылки указывает на место, куда будут пересылаться данные, адресованные рекламируемым маршрутом. Если адрес пересылки равен 0.0.0.0, данные посылаются пограничному маршрутизатору автономной системы - источнику данного сообщения. Метка внешнего маршрута - 32-битовое число, присваиваемое каждому внешнему маршруту. Эта метка самим протоколом OSPF не используется и предназначена для информирования других автономных систем при работе внешних протоколов маршрутизации. Маршрутная таблица OSPF содержит в себе:

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

Преимущества и недостатки OSPF

Преимущества OSPF:

1. Для каждого адреса может быть несколько маршрутных таблиц, по одной на каждый вид IP-операции (TOS).
2. Каждому интерфейсу присваивается безразмерная цена, учитывающая пропускную способность, время транспортировки сообщения. Для каждой IP-операции может быть присвоена своя цена (коэффициент качества).
3. При существовании эквивалентных маршрутов OSFP распределяет поток равномерно по этим маршрутам.
4. Поддерживается адресация субсетей (разные маски для разных маршрутов).
5. При связи точка-точка не требуется IP-адрес для каждого из концов. (Экономия адресов!)
6. Применение мультикастинга вместо широковещательных сообщений снижает загрузку не вовлеченных сегментов.

Недостатки:

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