В продолжении статьи об устройстве таблицы маршрутизации и о реализации протокола BGP в Quagga, в этой статье я рассмотрю, как работает протокол OSPF. Я ограничусь случаем одной зоны OSPF без перераспределения маршрутов от других протоколов маршрутизации.
Как обычно, я не буду подробно описывать работу и настройку протокола OSPF, а Я согласен где можно подробнее об этом прочитать.
Ограничусь только самой важной информацией для дальнейшего понимания статьи.
В отличие от протоколов RIP или BGP, которые сравнивают входящие маршруты от разных соседей и выбирают лучшие из них по некоторым критериям, протокол OSPF строит топологическую карту сети и использует ее для прокладки кратчайших маршрутов к соответствующим IP-сетям.
Для сбора информации о топологии сети маршрутизаторы обмениваются друг с другом фрагментами информации о напрямую подключенных сетях и их соседях по OSPF. Эти кусочки топологической информации называются LSA (Link State Advertisement) и из них, как из пазла, можно собрать полную топологическую карту сети.
Как устроены LSA, мы рассмотрим чуть позже, а сейчас перейдем к алгоритму поиска кратчайшего пути.
Алгоритм поиска кратчайшего пути Для поиска кратчайшего пути используется алгоритм Дейкстры, работа которого будет рассмотрена в следующем примере.
У нас есть пять маршрутизаторов, соединенных друг с другом ссылками, как показано на рисунке: 
R1 — это корневой маршрутизатор, который запускает алгоритм кратчайшего пути.
Цифры на ссылках показывают стоимость данной ссылки.
Задача состоит в том, чтобы найти кратчайший путь от маршрутизатора R1 до каждого из остальных маршрутизаторов, т.е.
путь, для которого суммарная стоимость каналов минимальна.
В результате для каждого роутера нам приходится рассчитывать две вещи:
- Стоимость пути от R1 до этого маршрутизатора.
- Какой следующий переход использует R1 для доступа к этому маршрутизатору.
Внутри каждого роутера мы укажем текущую стоимость для него.
Рядом с ним мы укажем текущий next-hop, который R1 использует для достижения этого маршрутизатора.
Зелёным цветом отметим маршрутизаторы, до которых рассчитан кратчайший путь.
Таким образом, на начальном этапе мы имеем кратчайший путь только до самого маршрутизатора R1, равный 0. До остальных маршрутизаторов затраты равны бесконечности, а next-hop неизвестен.
Теперь мы предпримем ряд шагов, каждый из которых улучшит стоимость путей к маршрутизаторам, и в конечном итоге мы рассчитаем кратчайшие пути ко всем из них.
Шаг 1. Посмотрите соседей корневого роутера.
Соседями корневого маршрутизатора R1 являются маршрутизаторы R2 и R3. Для каждого из них задаем стоимость пути, равную стоимости соответствующего канала, а next-hop, равную самому маршрутизатору R2 или R3, как показано на рисунке: 
Шаг 2. Выберите лучшее из оставшихся.
На этом шаге мы смотрим все оставшиеся маршрутизаторы, т.е.
маршрутизаторы, к которым еще не найден кратчайший путь (белые) и выбираем из них маршрутизатор с наименьшей стоимостью пути до него.
В нашем случае это роутер R2 стоимостью 1. Этот роутер мы можем смело перекрасить в зеленый цвет; для него нет более короткого пути.
На картинке он окрашен в тёмно-зелёный цвет, потому что этот роутер нам пригодится на шаге 3.
Шаг 3. Посмотрите соседей выбранного роутера.
Этот шаг аналогичен шагу 1, но вместо маршрутизатора R1 мы смотрим на соседей темно-зеленого маршрутизатора, выбранного на предыдущем шаге.
Для каждого соседа рассчитываем стоимость пути через выбранный маршрутизатор.
Если стоимость такого пути окажется меньше текущей стоимости, то мы присваиваем соседу новую стоимость и просто копируем next-hop с выбранного маршрутизатора.
Получается такая картина: 
Теперь повторяйте шаги 2 и 3, пока все маршрутизаторы не станут зелеными.
На этапе 2 один роутер обязательно станет зеленым, поэтому этот процесс рано или поздно завершится.
Итак, выбираем лучшие из оставшихся и перекрашиваем их в зеленый цвет (маршрутизатор R5): 
Смотрим соседей выбранного роутера, улучшаем затраты, копируем next-hop: 
Видно, что R3 изменился на next-hop, который был скопирован с R5. Выбираем лучшее: 
Смотрим на оставшегося соседа: 
И получаем окончательный результат: 
Теперь у нас есть стоимость путей к каждому из маршрутизаторов, а также какой следующий переход использовать на корневом маршрутизаторе для их достижения.
Те.
Мы почти готовы создать таблицу маршрутизации.
Однако для прямого применения в сетях рассмотренный выше алгоритм требует некоторой модернизации.
Модернизация алгоритма поиска кратчайшего пути Приведенный выше алгоритм работает только с каналами «точка-точка», когда каждый канал соединяет два маршрутизатора.
Настоящие маршрутизаторы могут соединяться друг с другом через сеть Ethernet, что позволяет подключать к одному сегменту более 2 маршрутизаторов, как показано на рисунке.
В протоколе OSPF такая сеть называется транзитной сетью.
Чтобы решить эту проблему, OSPF представляет каждую транзитную сеть как отдельный узел графа.
Те.
При расчете кратчайшего пути топология будет выглядеть так: 
Узел N1 просто обозначает транзитную сеть.
Теперь каждое звено соединяет только два узла и мы можем применить алгоритм поиска кратчайшего пути.
При расчете стоимости пути учитывается только стоимость канала от маршрутизатора до транзитной сети, а от транзитной сети до маршрутизатора она считается равной 0. Поскольку транзитная сеть является логическим объектом, один из маршрутизаторов должен взять на себя ответственность за создание необходимой топологической информации, описывающей транзитную сеть.
Для этого в OSPF в каждой транзитной сети выбирается Designated Router (DR), который помимо информации о себе также несет ответственность за рекламирование информации о транзитной сети.
Кроме того, таблица маршрутизации содержит маршруты не к маршрутизаторам, а к IP-сетям.
Вопрос с транзитными сетями легко решается.
Поскольку транзитные сети представлены в графе вершинами, стоимость маршрутов до транзитных сетей рассчитывается в ходе работы алгоритма кратчайшего пути.
Другие сети, например те, к которым подключен только один маршрутизатор OSPF, считаются тупиковыми сетями и объявляются маршрутизаторами, к которым они подключены.
Зная стоимость кратчайшего пути до каждого маршрутизатора, можно легко рассчитать стоимость маршрута до всех подключенных к нему конечных сетей.
Объявление о состоянии канала (LSA) Как я уже говорил, чтобы каждый маршрутизатор мог создать топологию сети и применить к ней алгоритм кратчайшего пути, маршрутизаторы обмениваются между собой небольшими порциями информации, называемыми Link State Advertisement LSA. LSA бывают разных типов и передают разную информацию.
Для нашего однозонного случая важны два типа LSA — LSA типа 1 и LSA типа 2. Каждый LSA типа 1 описывает маршрутизатор.
LSA типа 2 описывает транзитную сеть.
Если опустить различную служебную информацию, то схематически эти LSA можно представить следующим образом: 
Ниже приведено краткое описание полей LSA.
LSA типа 1 (LSA маршрутизатора).
В заголовке LSA для нас важны три поля:
- Тип.
Указывает тип LSA. В нашем случае это тип 1, или Router LSA.
- ЛСИД.
Идентификатор LSA. В нашем случае LSID равен идентификатору маршрутизатора, создающего LSA.
- Рекламный маршрутизатор.
Идентификатор маршрутизатора, создавшего LSA. В нашем случае он также равен Router ID роутера, создающего LSA, т.е.
соответствует LSID.
Передаваемая информация о ссылке зависит от типа ссылки.
Маршрутизатор может иметь три различных типа каналов: Транзитная сеть.
По ссылке такого типа передается следующая информация:
- Link ID — IP-адрес интерфейса назначенного маршрутизатора, подключенного к транзитной сети.
- Link Data — IP-адрес интерфейса маршрутизатора, подключенного к транзитной сети.
- Метрика — стоимость ссылки.
Для соединения «точка-точка» передается следующее:
- Link ID — IP-адрес интерфейса соседа.
- Link Data — IP-адрес самого интерфейса роутера.
- Метрика — стоимость ссылки.
Для нее передается:
- Link ID — фактический IP-адрес сети.
- Link Data – маска сети.
- Метрика — стоимость ссылки.
LSA типа 2 (сетевой LSA)
LSA типа 2 передает информацию о транзитной сети и объявляется назначенным маршрутизатором, специально выбранным для каждой транзитной сети.В заголовке LSA есть четыре важных поля:
- Тип.
В нашем случае это тип 2, или Network LSA.
- ЛСИД.
Идентификатор LSA. В нашем случае LSID равен IP-адресу интерфейса назначенного маршрутизатора, подключенного к транзитной сети;
- Рекламный маршрутизатор.
Идентификатор маршрутизатора, создавшего LSA. В нашем случае он равен назначенному идентификатору маршрутизатора.
- Маска.
Сетевая маска.
Для каждого такого роутера указывается его Router ID. Каждый LSA соответствует узлу графа и, в зависимости от его типа, представляет собой либо маршрутизатор, либо транзитную сеть.
Имея все LSA, теперь легко создать топологию сети.
Для этого достаточно отметить, что Link ID транзитного канала маршрутизатора соответствует LSID транзитной сети, и наоборот, Attached Router ID транзитной сети соответствует LSID подключенного к транзитная сеть.
В качестве примера на рисунке показана небольшая сеть: 
соответствующие LSA: 
и топология: 
Все созданные и принятые LSA хранятся в базе данных LSDB (база данных LSA).
Главное, что вам нужно от этой базы данных — это возможность добавлять в нее LSA, перебирать все LSA определенного типа и искать LSA по ключевым полям из заголовка LSA. Просмотреть список всех LSA в LSDB и их полей можно с помощью команд показать базу данных IP OSPF (печатает заголовки всех LSA), показать маршрут к базе данных ip ospf (отображает полную информацию о маршрутизаторе типа LSA) и показать IP сети базы данных OSPF (отображает полную информацию о сети типа LSA).
Реализация в Квагге
В Quagga вся база данных хранения LSA (LSDB) разделена на несколько баз данных, отдельных для каждого типа LSA, как показано на рисунке: 
Каждая база данных для хранения LSA отдельного типа структурирована идентично и хранит содержащиеся в ней LSA в виде, описанном в предыдущей.
статья префиксное дерево.
Префикс представляет собой комбинацию LSID и Adv Router. Комбинация этих полей уникальна для каждого LSA определенного типа внутри зоны.
При получении нового LSA он добавляется в LSDB и инициируется процесс расчета кратчайшего маршрута.
Процесс начинается с LSA, соответствующего самому маршрутизатору.
На основе содержащейся в нем информации в памяти создается новый узел, соответствующий корневому узлу топологии.
Далее из LSDB последовательно извлекаются LSA, соответствующие соседним узлам топологии, создаются новые узлы и рассчитываются кратчайшие пути и следующие переходы к ним, как описано в алгоритме кратчайшего пути.
Параллельно для обрабатываемых узлов в таблицу маршрутизации OSPF добавляются маршруты к транзитным сетям.
После построения топологии и расчета кратчайших путей просматриваются все узлы, соответствующие маршрутизаторам, и все их тупиковые сети добавляются в таблицу маршрутизации OSPF. Маршруты к транзитным сетям уже были добавлены в таблицу маршрутизации ранее.
Последний шаг — удалить все узлы топологии из памяти и передать маршруты из таблицы маршрутизации OSPF демону zebra. Схема этого процесса представлена на рисунке.
Теги: #Сетевые технологии #ospf #Дийкстра #quagga
-
Рейтинг Страницы Google Обновлен.
19 Oct, 24 -
Российские Программисты Не Сдаются-3
19 Oct, 24 -
Стив Джобс Не Разработал Ни Одного Проекта
19 Oct, 24 -
Как Привлечь Инвестиции Венчурного Фонда?
19 Oct, 24 -
Слава И Бедность Больших Данных
19 Oct, 24 -
Эффективный Перевод
19 Oct, 24
