Алгоритм маршрутизации. Формат таблицы маршрутизации.

Структура таблицы маршрутизации (ТМ) содержит всю информацию, необходимую для перенаправления IP датаграммы к месту назначения. Каждая запись ТМ описывает набор лучших маршрутов к какому-либо месту назначения. При маршрутизации IP датаграммы выбирается запись ТМ, которая обеспечивает наилучший маршрут. Протокол OSPF обеспечивает также наличие маршрута по умолчанию (Идентификатор места назначения [Destination ID] = DefaultDestination, Маска адреса [Address Mask] = 0x00000000). Каждый маршрутизатор содержит одну ТМ. Каждая запись содержит следующие поля:

• Тип места назначения (Destination Туре)

Это может быть либо «сеть», либо «маршрутизатор». При маршрутизации трафика актуальны только записи с типом «сеть». Записи с типом «маршрутизатор» используются исключительно как промежуточные шаги в процессе построения ТМ и хранятся для граничных маршрутизаторов области (Area Border Router) и граничных маршрутизаторов автономной системы (AS Boundary Routers). Сеть (в терминах протокола OSPF) - диапазон IP адресов, к которым может быть направлен трафик. Данный диапазон может включать IP сети (класса А, В или С), IP подсети, IP суперсети и одиночные IP хосты. Маршрут по умолчанию также попадает в эту категорию.

• Идентификатор места назначения (Destination ID)

Это может быть либо идентификатор, либо имя места назначения. Данный факт зависит от типа места назначения. Для сетей идентификатором является их IP адрес. Для маршрутизаторов идентификатором является идентификатор маршрутизатора протокола OSPF (OSPF Router ID).

• Маска адреса (Address Mask)

Данное поле определено только для сетей. Для подсетей поле содержит маску подсети, для хостов маска - «все единицы» (0xffffffff).

• Опциональные возможности (Optional Capabilities)

Когда местом назначения является маршрутизатор, данное поле указывает опциональные OSPF возможности, поддерживаемые этим маршрутизатором. Единственной опциональной возможностью, определенной в RFC-2328, является возможность обработки сообщений типа AS-external-LSA.

• Область (Area)

Данное поле указывает область, связь с которой ведет к месту назначения.

• Тип маршрута (Path-type)

Существует четыре возможных типа маршрутов, используемых для маршрутизации трафика к месту назначения. Данные типы перечислены в порядке убывания степени их предпочтения: внутриобластной (intra-area), межобластной (inter-area), внешний типа 1 (type 1 external) и внешний типа 2 (type 2 external). Внутриобластные маршруты указывают место назначения, принадлежащее одной из прикрепленных к текущему маршрутизатору областей. Межобластные маршруты - маршруты к местам назначения в других OSPF областях. Они обнаруживаются путем анализа полученных сообщений summary-LSA. Внешние маршруты автономной области указывают место назначения за пределами данной автономной области. Они обнаруживаются путем анализа полученных сообщений AS-external-LSA.

• Стоимость (Cost)

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

• Стоимость внешних маршрутов второго типа (Туре 2 cost)

Для данных маршрутов поле содержит стоимость внешней части пути. Данная стоимость объявляется граничным маршрутизатором автономной области и является наиболее значимой частью общей стоимости пути.

• Источник состояния связей (Link State Origin)

Действительно только для внутриобластных маршрутов. Данное поле содержит LSA (router-LSA или network-LSA), которое напрямую указывает на место назначения. Например, если местом назначения является транзитная сеть, тогда данное поле содержит network-LSA транзитной сети. LSA анализируется во время построения дерева наикратчайшего пути. Значение в данном поле используется протоколом MOSPF (Multicast OSPF).

Когда к месту назначения существует несколько маршрутов одинакового типа и стоимости (называются маршруты "одинаковой стоимости", "equal-cost" paths), тогда они хранятся в одной записи ТМ. Каждый из подобных маршрутов различается следующими полями:

• Следующий хоп (Next hop)

Интерфейс маршрутизатора, который необходимо использовать для перенаправления трафика к месту назначения. В широковещательных, Point-to-MultiPoint и NBMA сетях следующий хоп также включает IP адрес следующего маршрутизатора на пути к месту назначения.

• Объявляющий маршрутизатор (Advertising router)

Поле действительно только для межобластных и внешних маршрутов и содержит идентификатор маршрутизатора, объявляющего сообщения summary-LSA или AS-external-LSA, которые ведут к данному пути.

Формирование таблицы маршрутизации (алгоритм SPF).

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

Процесс построения таблицы маршрутизации может быть разбит на следующие шаги:

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

2. Внутриобластные маршруты вычисляются путем построения дерева наикратчайших путей для каждой присоединенной области. В частности, все записи таблицы маршрутизации, у которых Тип Места Назначения есть "Пограничный Маршрутизатор Области", вычисляются на данном этапе. Данный этап разбивается на две части. В первую очередь, дерево строится только с учетом связей (каналов) между маршрутизаторами и промежуточными сетями. Затем сети «заглушки» (stub networks) включаются в дерево. Во время построения дерева наикратчайших путей области также вычисляется свойство области «Возможность Транзита» для дальнейшего использования в шаге 4

3. Межобластные маршруты вычисляются путем анализа сообщений summary-LSA. Если маршрутизатор подсоединен к множеству областей (например, пограничный маршрутизатор области), то анализируются сообщения summary-LSA только из основной области.

4. В пограничных маршрутизаторах области, подсоединенных к одной или более промежуточной области, анализируются сообщения summary-LSA из промежуточных областей. Цель анализа - выяснить, существуют ли лучшие маршруты через промежуточные области, чем те, которые были найдены на этапах 2 и 3.

5. Маршруты к внешним местам назначения вычисляются путем анализа сообщений AS-external-LSA. Расположение пограничных маршрутизаторов АС (которые генерируют сообщения AS-external-LSA) определяется на этапах 2-4.

Изменения, сделанные в ТМ, могут инициировать OSPF протокол к принятию дополнительных действий Например, изменение в внутриобластном маршруте заставит пограничный маршрутизатор области генерировать новое сообщение summary-LSA.

Алгоритм маршрутизации.

Когда получена IP дейтаграмма, OSPF маршрутизатор должен найти запись в ТМ, которая содержит место назначения, наиболее подходящее для дейтаграммы. Данная запись должна обеспечить исходящий интерфейс и маршрутизатор следующей пересылки. Выбирается запись ТМ, которая отвечает правилу «Longest Match». Предположим, что маршрутизатор переправляет пакет к месту назначения с адресом 192.9.1.1. При этом запись 192.9.1/24 всегда будет предпочтительней записи 192.9/16 вне зависимости от типа маршрута.

Если не найдено подходящей записи ТМ, или наиболее подходящая найденная запись входит в список «отвернутых», то тогда считается, что пакет невозможно доставить к месту назначения. Пакет должен быть сброшен. ICMP-сообщение «Получатель недоступен» должно быть сгенерировано для источника пакета.

6.4. Область применения, достоинства, недостатки

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

• Отсутствие ограничений на размер сети.

• Достаточно большую скорость установления маршрута.

• Процедура установления подлинности источника информации при передаче и получении обновлений маршрутов.

• Иерархическая маршрутизация.

• Может быть несколько маршрутных таблиц, по одной на каждый тип сервиса (TOS).

• При существовании эквивалентных маршрутов OSFP распределяет поток равномерно по этим маршрутам (Load balancing).

• При связи точка-точка не требуется IP-адрес для каждого из концов (экономия адресов).

Недостатки:

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

• Протокол OSPF гораздо сложнее протокола RIP.

6.5. Классификация

Протокол OSPF является:

• динамическим;

• многомаршрутным;

• иерархическим;

• с интеллектом в маршрутизаторе;

• внутридоменным;

• алгоритмом состояний канала.