Алгоритм SPF в IP-сетях

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

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

При представлении СПД в виде направленного графа вершинами графа назначаются маршрутизаторы и сети-получатели, настроенные на них. Все вершины графа делятся на три группы:

Рис. 10.5. Итерации алгоритма SPF.

• — маршрутизаторы (Routers);
• — тупиковые сети (Stub Network);
• — транзитные сети (Transit Network).

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

• — Точка-Точка (Point-to-Point);
• — транзит (Network Link);
• — виртуальная связь (Virtual Link).

Три представленных типа ребер графа способны описать все многообразие каналов связи СПД. Каналы «Точка-Точка» представляются соответствующим типом ребер. Многоточечные каналы связи, распространенные в технологиях NBMA, преобразуются в набор ребер «Точка-Точка».

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

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

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

Сеть передачи данных состоит:

• — из семи маршрутизаторов Rl —R7;
• — шести каналов связи «Точка-Точка», например между маршрутизаторами R1 и R2;
• — трех широковещательных каналов связи, например, между маршрутизаторами R2 и R3;
• — двадцати двух тупиковых сетей. К тупиковым сетям относятся не только сети управления и пользовательские сети, но и сети, настроенные на каналах «Точка-Точка»;
• — трех транзитных сетей, описывающих сети-получатели, настроенные на широковещательных каналах связи. Необходимо отметить, что транзитной сеть делает только факт установки соседских отношений с маршрутизатором по широковещательному каналу связи.

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

Рис. 10.6. Пример сети передачи данных

Стоимости ребер можно рассчитать относительно стоимости каналов связи интерфейсов маршрутизаторов.

По представленным данным можно произвести преобразование реальной СПД в направленный граф, представленный на рис. 10.7.

Рис. 10.7. Представление реальной СПД в виде направленного графа.

Количество вершин тупиковых сетей в полученном графе превышает количество существующих в СПД сетей-получателей. Это связано с тем, что сети-получатели, настроенные на каналах «Точка-Точка», описываются как тупиковые сети для обоих маршрутизаторов, между которыми проходит канал связи.

После построения графа при помощи алгоритма SPF необходимо произвести расчет дерева SPT для выбранного маршрутизатора. Расчет дерева SPT происходит в два этапа.

На первом этапе (рис. 10.8) строится каркас дерева, состоящий из следующих компонентов топологической информации:

• — маршрутизаторы;
• — Точка-Точка;
• — транзитная сеть;
• — виртуальная связь.

Рис. 10.8. Каркас дерева SPT для R1

со о.

•С*.

Рис. 10.9. Дерево SPT для R1.

Необходимо отметить, что в каркас дерева для маршрутизатора R1 не войдут связи «Транзитная сеть», поскольку они не будут являться частью кратчайших путей в графе SPF.

На втором этапе в полученный каркас дерева в соответствии с правилами алгоритма SPF добавляется маршрутная информация о сетях-получателях (рис. 10.9):

• — тупиковые сети;
• — транзит.

Проведя обход дерева SPT, можно заполнить таблицу маршрутизации.

Контрольные вопросы

• 1. Назовите главное отличие алгоритма SPF от рассмотренных ранее.
• 2. Для какого типа графа разработан алгоритм SPF?
• 3. Каким образом удалось представить СПД в виде графа?
• 4. Какую информацию могут содержать ребра графа?
• 5. Из каких этапов состоит построение дерева SPT?