Введение

Класс маршрутизационных протоколов

Протоколы маршрутизации состояния связи – один из двух основных классов маршрутизационных протоколов, используемых в сетях коммутации пакетов для компьютерных коммуникаций, второй – протоколы маршрутизации на основе вектора расстояния. Примеры протоколов состояния связи включают Open Shortest Path First (OSPF) и Intermediate System to Intermediate System (IS-IS). Протокол состояния связи выполняется каждым коммутирующим узлом в сети (то есть узлами, способными пересылать пакеты; в Интернете они называются маршрутизаторами). Основная концепция маршрутизации состояния связи заключается в том, что каждый узел строит карту связности сети в виде графа, отображающего, какие узлы связаны с какими другими узлами. Затем каждый узел независимо вычисляет наилучший логический путь от себя до каждого возможного пункта назначения в сети. Набор этих наилучших путей формирует таблицу маршрутизации для каждого узла. Это отличается от протоколов маршрутизации на основе вектора расстояния, где каждый узел обменивается своей таблицей маршрутизации с соседями. В протоколе состояния связи между узлами передается только информация о связности. Алгоритмы состояния связи иногда неформально описывают как каждый маршрутизатор, "рассказывающий сети о своих соседях".

История

Первая адаптивная сеть маршрутизации компьютеров, использующая маршрутизацию по состоянию каналов в качестве основы, была разработана и реализована в 1976–1977 годах командой Plessey Radar под руководством Бернарда Дж. Харриса; проект предназначался для системы "Wavell" – системы компьютерного управления и контроля для британской армии. Первая концепция маршрутизации по состоянию каналов была опубликована в 1979 году Джоном М. Маккуилланом (в то время работавшим в Bolt, Beranek and Newman) как механизм, позволяющий быстрее вычислять маршруты при изменении условий сети и, следовательно, обеспечивать более стабильную маршрутизацию. Последующие работы в BBN Technologies показали, как использовать метод состояния каналов в иерархической системе (то есть в сети, разделенной на области), чтобы каждому коммутационному узлу не требовалась карта всей сети, а только области, в которые он включен. Позже эта техника была адаптирована для использования в современных протоколах маршрутизации по состоянию каналов IS-IS и OSPF. В документации Cisco протокол Enhanced Interior Gateway Routing Protocol (EIGRP) обозначается как "гибридный" протокол, несмотря на то, что он распространяет таблицы маршрутизации, а не топологические карты. Однако он синхронизирует таблицы маршрутизации при запуске, как это делает OSPF, и отправляет конкретные обновления только при изменениях топологии. В 2004 году Радия Перлман предложила использовать маршрутизацию по состоянию каналов для пересылки кадров второго уровня с помощью устройств, называемых маршрутизирующими мостами или Rbridges. Для реализации этого Интернет-инженерная группа стандартизировала протокол Transparent Interconnection of Lots of Links (TRILL). В последнее время эта иерархическая техника была применена к беспроводным mesh-сетям с использованием протокола Optimized Link State Routing Protocol (OLSR). Если соединение может иметь различное качество, качество соединения можно использовать для выбора лучших соединений. Это используется в некоторых ad hoc протоколах маршрутизации, использующих радиочастотную передачу.

Распространение карт

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

Определение соседей каждого узла

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

Создание карты

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

Примечания к этому этапу

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

Расчет таблицы маршрутизации

Как было упомянуто ранее, второй основной этап в алгоритме состояний связей — формирование таблиц маршрутизации на основе анализа топологических карт. Это снова выполняется в несколько шагов.

Расчет кратчайших путей

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

Заполнение таблицы маршрутизации

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

Оптимизация алгоритма

Алгоритм, описанный выше, был сделан максимально простым для облегчения понимания. На практике применяется ряд оптимизаций.

Частичный перерасчет

Всякий раз, когда происходит изменение карты связности, необходимо пересчитать дерево кратчайших путей и затем воссоздать таблицу маршрутизации. Исследования, проведенные BBN Technologies, показали, как пересчитывать только ту часть дерева, которая могла быть затронута данным изменением карты. Также, таблица маршрутизации обычно заполняется по мере вычисления дерева кратчайших путей, а не как отдельная операция.

Маршрутизация по штату Fisheye

С Fisheye State Routing (FSR) LSA отправляются с разными значениями времени жизни (TTL), чтобы ограничить их распространение и снизить нагрузку, создаваемую контрольными сообщениями. Та же концепция используется и в протоколе маршрутизации на основе состояний Hazy Sighted Link.

Режимы отказов

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

Протокол маршрутизации состояния оптимальной связи

Оптимизированный протокол маршрутизации на основе состояния каналов связи (OLSR) – это протокол маршрутизации на основе состояния каналов связи, оптимизированный для мобильных самоорганизующихся сетей (который также может использоваться и в других беспроводных самоорганизующихся сетях). OLSR является проактивным и использует приветные сообщения и сообщения контроля топологии (TC) для обнаружения и распространения информации о состоянии каналов связи в мобильной самоорганизующейся сети. С помощью приветных сообщений каждый узел обнаруживает информацию о соседях в пределах двух скачков и выбирает набор многоточечных ретрансляторов (MPR). Многоточечные ретрансляторы (MPR) выделяют OLSR среди других протоколов маршрутизации на основе состояния каналов связи. Отдельные узлы используют топологическую информацию для вычисления маршрутов до всех узлов сети, используя пути с наименьшим числом скачков.