Процесс построения таблицы маршрутизации. Алгоритм Shortest Patch First

1. Каждый маршрутизатор на всех интерфейсах изучает своих соседей и заносит их в таблицу «соседей».

Рис1.

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

Канал – это линия связи или интерфейс, соединяющий один маршрутизатор с другим или с сетью. Состояние канала — это описание интерфейса и его связей с соседними маршрутизаторами. Описание интерфейса может включать, например, IР-адрес интерфейса, маску, тип сети, к которой он подключен. Набор всех этих состояний каналов формирует базу данных состояния каналов.

Рис 2.

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

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

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

Рис 3.

4. Затем из этого дерева к сетям назначения выбираются пути с наименьшей стоимостью и помещаются в таблицу маршрутизации. Стоимость или метрика интерфейса — это индикатор усилий, которые необходимы для отправки пакета через этот интерфейс. Стоимость интерфейса обратно пропорциональна полосе пропускания интерфейса, таким образом, большая полоса пропускания соответствует меньшей стоимости.

Рис 4.

5. После первоначального построения таблицы маршрутизации необходимо отслеживать изменения состояния сети и вносить коррективы в таблицу маршрутизации. Для контроля состояния связей и соседних маршрутизаторов они передают специальные короткие сообщения HELLO. Если состояние сети не меняется, то маршрутизаторы корректировкой своих таблиц маршрутизации не занимаются и не посылают соседям объявления о связях. Сообщения HELLO отправляются через каждые 10 секунд, чтобы повысить скорость адаптации маршрутизаторов к изменениям, происходящим в сети. Небольшой объем этих сообщений делает возможной такое частое тестирование состояния соседей и связей с ними.

Рис 5.

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

Рис 6.

В сетях с множественным доступом (сети, которые поддерживают больше двух маршрутизаторов на сегменте), например, сетях Ethernet, hello-протокол выбирает назначенный маршрутизатор (DR) и резервный назначенный маршрутизатор (BDR). В числе прочих задач, назначенный маршрутизатор отвечает за генерацию LSA-пакетов для всей сети с множественным доступом. Назначенные маршрутизаторы позволяют уменьшить трафик при обновлениях маршрутной информации и управляют синхронизацией состояния каналов. DR и BDR выбираются на основании приоритетов OSPF и идентификатора маршрутизатора OSPF. В отсутствии множественного доступа, например, в сетях с последовательными соединениями типа точка-точка, DR или BDR не выбираются.

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

В процессе выбора оптимального маршрута анализируется ориентированный граф сети. Ниже описан алгоритм Дикстры по выбору оптимального пути. На рис приведена схема узлов (A-J) со значениями метрики для каждого из отрезков пути. Анализ графа начинается с узла A (Старт). Пути с наименьшим суммарным значением метрики считаются наилучшими. Именно они оказываются выбранными в результате рассмотрения графа (“кратчайшие пути“).

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

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

Пусть 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 приведена на нижней части рис. В скобках записаны числа, характеризующие метрику отобранного маршрута согласно критерию пункта 3.

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

· пропускной способностью канала;

· задержкой (время распространения пакета);

· числом дейтограмм, стоящих в очереди для передачи;

· загрузкой канала;

· требованиями безопасности;

· типом трафика;

· числом шагов до цели;

· возможностями промежуточных связей (например, многовариантность достижения адресата).

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

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

Поиск по сайту: