Протоколы маршрутизации по состоянию канала — это один из двух основных классов протоколов маршрутизации, используемых в сетях коммутации пакетов для компьютерной связи , остальные — протоколы маршрутизации на основе вектора расстояния . Примеры протоколов маршрутизации по состоянию канала включают в себя Open Shortest Path First (OSPF) и Intermediate System to Intermediate System (IS-IS).
Протокол состояния канала выполняется каждым коммутационным узлом в сети (т. е. узлами, которые готовы пересылать пакеты; в Интернете они называются маршрутизаторами ). Основная концепция маршрутизации по состоянию канала заключается в том, что каждый узел создает карту подключения к сети в виде графа , показывающего, какие узлы к каким другим узлам подключены. Затем каждый узел независимо вычисляет следующий лучший логический путь от него ко всем возможным пунктам назначения в сети. Каждая коллекция лучших путей затем сформирует таблицу маршрутизации каждого узла .
Это контрастирует с протоколами маршрутизации с вектором расстояния, которые работают, когда каждый узел использует свою таблицу маршрутизации совместно со своими соседями. В протоколе состояния канала единственная информация, передаваемая между узлами, связана с подключением . Алгоритмы состояния канала иногда неформально характеризуются как каждый маршрутизатор, «рассказывающий миру о своих соседях».
В протоколах маршрутизации по состоянию канала каждый маршрутизатор обладает информацией о полной топологии сети. Затем каждый маршрутизатор независимо вычисляет лучший следующий переход от него для каждого возможного пункта назначения в сети, используя локальную информацию о топологии. Коллекция лучших следующих переходов формирует таблицу маршрутизации.
Это контрастирует с протоколами маршрутизации на основе вектора расстояния, которые работают, заставляя каждый узел делиться своей таблицей маршрутизации со своими соседями. В протоколе состояния канала единственная информация, передаваемая между узлами, — это информация, используемая для построения карт связности.
Примеры протоколов маршрутизации по состоянию канала:
То, что считается первой компьютерной сетью адаптивной маршрутизации, в основе которой лежит маршрутизация по состоянию канала, было спроектировано и реализовано в 1976–1977 годах командой Plessey Radar под руководством Бернарда Дж. Харриса; проект предназначался для «Вейвелла» — системы компьютерного управления и контроля для британской армии. [ нужна цитата ]
Первая концепция маршрутизации по состоянию канала была опубликована в 1979 году Джоном М. Маккуилланом (тогда в Bolt, Beranek and Newman ) как механизм, который позволял быстрее рассчитывать маршруты при изменении условий сети и, таким образом, приводил к более стабильной маршрутизации. [1] [2] [3] Более поздняя работа в BBN Technologies показала, как использовать технику состояния канала в иерархической системе (т. е. такой, в которой сеть была разделена на области), чтобы каждому коммутационному узлу не требовалась карта. из всей сети только та область(и), в которую она включена. [ нужна цитата ]
Позже этот метод был адаптирован для использования в современных протоколах маршрутизации по состоянию канала IS-IS и OSPF. В литературе Cisco Enhanced Internal Gateway Routing Protocol (EIGRP) называется «гибридным» протоколом, [4] несмотря на то, что он распределяет таблицы маршрутизации вместо карт топологии. Однако он синхронизирует таблицы маршрутизации при запуске, как это делает OSPF, и отправляет определенные обновления только при возникновении изменений топологии.
В 2004 году Радия Перлман предложила использовать маршрутизацию по состоянию канала для пересылки кадров уровня 2 с помощью устройств, называемых мостами маршрутизации или Rbridges. Для достижения этой цели Рабочая группа по проектированию Интернета стандартизировала протокол прозрачного межсоединения множества каналов (TRILL). [5]
Совсем недавно этот иерархический метод был применен к беспроводным ячеистым сетям с использованием протокола маршрутизации с оптимизированным состоянием канала (OLSR). Если соединение может иметь различное качество, качество соединения можно использовать для выбора лучшего соединения. Это используется в некоторых протоколах специальной маршрутизации , использующих радиочастотную передачу.
Это описание охватывает только простейшую конфигурацию; т.е. один без областей, так что все узлы имеют карту всей сети. Иерархический случай несколько сложнее; см. различные спецификации протокола.
Как упоминалось ранее, первым основным этапом алгоритма состояния канала является предоставление карты сети каждому узлу. Это делается с помощью нескольких вспомогательных шагов.
Во-первых, каждому узлу необходимо определить, к каким еще портам он подключен по полностью рабочим каналам; он делает это, используя протокол достижимости , который запускается периодически и отдельно с каждым из своих напрямую подключенных соседей.
Далее каждый узел периодически (и в случае изменения подключения) отправляет короткое сообщение, объявление о состоянии канала , которое:
Это сообщение отправляется всем узлам сети. В качестве необходимого предшественника каждый узел в сети запоминает для каждого из своих соседей порядковый номер последнего сообщения о состоянии канала, которое он получил от этого узла. Когда на узле получено объявление о состоянии канала, узел ищет сохраненный им порядковый номер источника этого сообщения о состоянии канала: если это сообщение новее (т. е. имеет более высокий порядковый номер), оно сохраняется. , порядковый номер обновляется, и копия по очереди отправляется каждому из соседей этого узла. Эта процедура быстро передает копию последней версии объявления о состоянии канала каждого узла каждому узлу в сети.
Сети, в которых используются алгоритмы состояния каналов, также могут быть сегментированы на иерархии, которые ограничивают объем изменений маршрутов. Эти функции означают, что алгоритмы состояния канала лучше масштабируются для более крупных сетей.
Наконец, имея на руках полный набор объявлений о состоянии канала (по одному от каждого узла сети), каждый узел создает граф для карты сети. Алгоритм перебирает коллекцию объявлений о состоянии канала; для каждого из них он создает ссылки на карте сети от узла, отправившего это сообщение, ко всем узлам, которые, как указано в этом сообщении, являются соседями отправляющего узла.
Ни одна ссылка не считается переданной правильно, если обе стороны не пришли к согласию; т.е. если один узел сообщает, что он подключен к другому, но другой узел не сообщает, что он подключен к первому, существует проблема, и ссылка не включается на карту.
Сообщение о состоянии канала, дающее информацию о соседях, пересчитывается, а затем рассылается по сети всякий раз, когда происходит изменение соединения между узлом и его соседями; например, когда ссылка терпит неудачу. Любое такое изменение будет обнаружено протоколом достижимости, который каждый узел использует со своими соседями.
Как упоминалось ранее, вторым основным этапом алгоритма состояния канала является создание таблиц маршрутизации путем проверки карт. Это снова делается в несколько шагов.
Каждый узел независимо запускает алгоритм на карте, чтобы определить кратчайший путь от себя к любому другому узлу в сети; обычно используется какой-то вариант алгоритма Дейкстры . Это основано на стоимости канала по каждому пути, которая, среди прочего, включает доступную пропускную способность.
Узел поддерживает две структуры данных: дерево , содержащее «готовые» узлы, и список кандидатов . Алгоритм начинается с пустых обеих структур; затем он добавляет к первому сам узел. Вариант жадного алгоритма затем неоднократно выполняет следующее:
Два вышеуказанных шага повторяются до тех пор, пока в списке кандидатов остаются какие-либо узлы. (Если их нет, все узлы сети будут добавлены в дерево.) Эта процедура заканчивается тем, что дерево содержит все узлы сети, а узел, на котором выполняется алгоритм, является корнем дерева . . Кратчайший путь от этого узла к любому другому узлу обозначается списком узлов, которые нужно пройти, чтобы добраться от корня дерева до нужного узла в дереве.
Имея под рукой кратчайшие пути, следующим шагом будет заполнение таблицы маршрутизации. Для любого заданного узла назначения лучшим путем для этого пункта назначения является узел, который является первым шагом от корневого узла вниз по ветви дерева кратчайшего пути, ведущей к желаемому узлу назначения. Чтобы создать таблицу маршрутизации, необходимо только пройтись по дереву, запоминая идентификатор узла во главе каждой ветви и заполняя запись таблицы маршрутизации для каждого узла, с которым встречается этот идентификатор.
Описанный выше алгоритм был сделан максимально простым, чтобы облегчить понимание. На практике используется ряд оптимизаций.
Всякий раз, когда происходит изменение в карте связности, необходимо заново вычислить дерево кратчайших путей, а затем заново создать таблицу маршрутизации. Работа BBN Technologies [ нужна ссылка ] обнаружила, как пересчитывать только ту часть дерева, на которую могло повлиять данное изменение карты. Кроме того, таблица маршрутизации обычно заполняется при вычислении дерева кратчайшего пути, вместо того, чтобы делать это отдельной операцией.
В некоторых случаях разумно уменьшить количество узлов, генерирующих сообщения LSA. Например, узлу, имеющему только одно подключение к сетевому графу, не нужно отправлять сообщения LSA, поскольку информация о его существовании уже может быть включена в сообщение LSA его единственного соседа. По этой причине может быть применена стратегия сокращения топологии, при которой только подмножество сетевых узлов генерирует сообщения LSA. Два широко изученных подхода к уменьшению топологии:
При использовании маршрутизации состояния «рыбий глаз» (FSR) LSA отправляются с разными значениями времени жизни, чтобы ограничить их распространение и ограничить накладные расходы из-за управляющих сообщений. Та же концепция используется и в протоколе маршрутизации состояния канала Hazy Sighted Link .
Если все узлы не работают с одной и той же картой, могут образоваться петли маршрутизации . Это ситуации, в которых, в простейшей форме, каждый из двух соседних узлов считает, что другой — лучший путь к заданному пункту назначения. Любой пакет, направляющийся в этот пункт назначения, прибывающий в любой из узлов, будет зацикливаться между ними, отсюда и название. Также возможны петли маршрутизации, включающие более двух узлов.
Это может произойти, поскольку каждый узел вычисляет свое дерево кратчайшего пути и таблицу маршрутизации, не взаимодействуя каким-либо образом с другими узлами. Если два узла начинаются с разных карт, возможны сценарии, в которых создаются петли маршрутизации. В определенных обстоятельствах дифференциальные контуры могут быть включены в мультиоблачной среде. Переменные узлы доступа по протоколу интерфейса также могут обойти проблему одновременного доступа к узлам. [8]
Оптимизированный протокол маршрутизации по состоянию канала (OLSR) — это протокол маршрутизации по состоянию канала, оптимизированный для мобильных одноранговых сетей (который также можно использовать в других беспроводных одноранговых сетях ). [9] OLSR действует упреждающе и использует сообщения приветствия и управления топологией (TC) для обнаружения и распространения информации о состоянии канала в мобильную одноранговую сеть. Используя сообщения приветствия, каждый узел обнаруживает информацию о соседях с двумя переходами и выбирает набор многоточечных ретрансляторов (MPR). MPR отличает OLSR от других протоколов маршрутизации по состоянию канала. Отдельные узлы используют информацию о топологии для расчета путей следующего перехода относительно всех узлов в сети, используя пути пересылки кратчайшего перехода.
{{cite news}}: CS1 maint: несколько имен: список авторов ( ссылка ){{citation}}: CS1 maint: числовые имена: список авторов ( ссылка ){{cite journal}}: Требуется цитировать журнал |journal=( помощь ){{cite journal}}: Требуется цитировать журнал |journal=( помощь )