Протоколы маршрутизации на основе состояния канала - это один из двух основных классов протоколов маршрутизации, используемых в сетях с коммутацией пакетов для компьютерной связи , другой - протоколы маршрутизации с вектором расстояния . Примеры протоколов маршрутизации на основе состояния канала включают в себя сначала открытый кратчайший путь (OSPF) и от промежуточной системы к промежуточной системе (IS-IS).
Протокол состояния канала выполняется каждым коммутационным узлом в сети (т. Е. Узлами, которые готовы пересылать пакеты; в Интернете они называются маршрутизаторами ). Основная концепция маршрутизации на основе состояния канала заключается в том, что каждый узел строит карту подключения к сети в форме графика , показывающего, какие узлы связаны с какими другими узлами. Затем каждый узел независимо вычисляет следующий лучший логический путь от него до каждого возможного пункта назначения в сети. Каждый набор лучших путей затем сформирует таблицу маршрутизации каждого узла .
Это контрастирует с протоколами маршрутизации по вектору расстояния , которые работают, когда каждый узел разделяет свою таблицу маршрутизации со своими соседями, в протоколе состояния канала единственной информацией, передаваемой между узлами, является связность . Алгоритмы состояния канала иногда неформально характеризуют как каждый маршрутизатор, «рассказывающий миру о своих соседях».
История [ править ]
То, что считается первой компьютерной сетью с адаптивной маршрутизацией, в основе которой лежит маршрутизация по состоянию канала, было разработано и реализовано в 1976-77 годах командой из Plessey Radar под руководством Бернарда Дж. Харриса; Проект был разработан для "Wavell" - системы компьютерного управления и контроля для британской армии. [ необходима цитата ]
Первая концепция маршрутизации на основе состояния канала была опубликована в 1979 году Джоном М. МакКилланом (затем в Bolt, Beranek и Newman ) как механизм, который быстрее вычислял маршруты при изменении сетевых условий и, таким образом, приводил к более стабильной маршрутизации. [1] [2]
Более поздняя работа в BBN Technologies показала, как использовать технику состояния канала в иерархической системе (т. Е. Такой, в которой сеть была разделена на области), так что каждому коммутационному узлу не нужна карта всей сети, только область ( s) в которую он включен. [ необходима цитата ]
Позже этот метод был адаптирован для использования в современных протоколах маршрутизации состояния канала IS-IS и OSPF. Cisco литература относится к протоколу маршрутизации расширения внутреннего шлюза (EIGRP) в качестве протокола «гибридного», [ править ] , несмотря на то , что распределяет таблицы маршрутизации вместо карты топологии. Однако он синхронизирует таблицы маршрутизации при запуске, как это делает OSPF, и отправляет определенные обновления только при изменении топологии.
В 2004 году Радиа Перлман предложил использовать маршрутизацию по состоянию канала для пересылки кадров уровня 2 с помощью устройств, называемых мостами маршрутизации или Rbridges. Engineering Task Force Интернет унифицировал прозрачную взаимосвязь много ссылок (трель) протокола для достижения этой цели . [3]
Совсем недавно этот иерархический метод был применен к беспроводным ячеистым сетям с использованием протокола маршрутизации оптимизированного состояния канала (OLSR). Если соединение может иметь разное качество, качество соединения можно использовать для выбора лучшего соединения. Это используется в некоторых протоколах маршрутизации , использующих радиочастотную передачу.
В 2012 году IEEE завершил и утвердил стандартизацию использования IS-IS для управления пересылкой Ethernet с помощью моста кратчайшего пути (SPB) IEEE 802.1aq .
Распространение карт [ править ]
Это описание охватывает только простейшую конфигурацию; т.е. узел без областей, так что все узлы имеют карту всей сети. Иерархический случай несколько сложнее; см. различные спецификации протокола.
Как упоминалось ранее, первый основной этап в алгоритме состояния канала - предоставить карту сети каждому узлу. Это делается с помощью нескольких дополнительных шагов.
Определение соседей каждого узла [ править ]
Во-первых, каждому узлу необходимо определить, к каким еще портам он подключен по полностью работающим каналам; он делает это, используя протокол достижимости, который он периодически и отдельно запускает с каждым из своих напрямую подключенных соседей.
Распространение информации для карты [ править ]
 | Эта статья может сбивать с толку или непонятна читателям . В частности, из приведенного описания неясно, как работают порядковые номера: 1) как они генерируются, 2) как они «обновляются», когда узел получает сообщение, 3) как именно они предотвращают отправку сообщения в цикл. ( Ноябрь 2020 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Затем каждый узел периодически (и в случае изменения подключения) отправляет короткое сообщение, объявление о состоянии канала , которое:
- Обозначает узел, который его производит.
- Определяет все остальные узлы (маршрутизаторы или сети), к которым он напрямую подключен.
- Включает «порядковый номер», который увеличивается каждый раз, когда исходный узел создает новую версию сообщения .
Это сообщение отправляется всем узлам в сети. В качестве необходимого предшественника каждый узел в сети запоминает для каждого из своих соседей порядковый номер последнего сообщения о состоянии канала, которое он получил от этого узла. Когда в узле получено объявление о состоянии канала, узел ищет сохраненный им порядковый номер для источника этого сообщения о состоянии канала: если это сообщение более новое (т. Е. Имеет более высокий порядковый номер), оно сохраняется. , порядковый номер обновляется, и копия отправляется по очереди каждому из соседей этого узла. Эта процедура быстро получает копию последней версии объявления о состоянии канала каждого узла на каждый узел в сети.
Сети, в которых работают алгоритмы состояния каналов, также можно сегментировать по иерархиям, которые ограничивают объем изменений маршрута. Эти функции означают, что алгоритмы состояния канала лучше масштабируются для более крупных сетей.
Создание карты [ править ]
Наконец, имея полный набор объявлений о состоянии канала (по одному от каждого узла в сети), каждый узел создает граф для карты сети. Алгоритм выполняет итерацию по сбору рекламных объявлений о состоянии ссылок; для каждого из них он устанавливает связи на карте сети от узла, отправившего это сообщение, ко всем узлам, которые в этом сообщении указывают, являются соседями отправляющего узла.
Считается, что ни одна ссылка не была сообщена правильно, если обе стороны не пришли к соглашению; то есть, если один узел сообщает, что он подключен к другому, но другой узел не сообщает, что он подключен к первому, существует проблема, и ссылка не включена в карту.
Примечания об этом этапе [ править ]
Сообщение о состоянии канала, дающее информацию о соседях, пересчитывается, а затем рассылается по сети всякий раз, когда происходит изменение связи между узлом и его соседями; например, когда ссылка не работает. Любое такое изменение будет обнаружено протоколом достижимости, который каждый узел выполняет со своими соседями.
Расчет таблицы маршрутизации [ править ]
Как упоминалось ранее, второй основной этап в алгоритме состояния канала - создание таблиц маршрутизации путем проверки карт. Это снова делается в несколько шагов.
Расчет кратчайших путей [ править ]
Каждый узел независимо запускает алгоритм по карте, чтобы определить кратчайший путь от самого себя до каждого другого узла в сети; обычно используется какой-то вариант алгоритма Дейкстры . Это основано на стоимости соединения по каждому пути, которая, помимо прочего, включает доступную полосу пропускания.
Узел поддерживает две структуры данных: дерево, содержащее узлы, которые "выполнены", и список кандидатов . Алгоритм начинается с пустыми обеими структурами; затем он добавляет к первому саму вершину. Затем вариант жадного алгоритма многократно выполняет следующие действия:
- Все соседние узлы, которые напрямую подключены к узлу, просто добавляются в дерево (за исключением любых узлов, которые уже есть в дереве или списке кандидатов). Остальные добавляются во второй (кандидатский) список.
- Каждый узел в списке кандидатов сравнивается с каждым из узлов уже в дереве. Узел-кандидат, ближайший к любому из узлов уже в дереве, сам перемещается в дерево и присоединяется к соответствующему соседнему узлу. Когда узел перемещается из списка кандидатов в дерево, он удаляется из списка кандидатов и не учитывается в последующих итерациях алгоритма.
Вышеупомянутые два шага повторяются до тех пор, пока в списке кандидатов остаются какие-либо узлы. (Если их нет, все узлы в сети будут добавлены в дерево.) Эта процедура заканчивается деревом, содержащим все узлы в сети, с узлом, на котором алгоритм работает, как корнем дерева. . Кратчайший путь от этого узла к любому другому узлу обозначается списком узлов, которые нужно пройти, чтобы добраться от корня дерева к желаемому узлу в дереве ..!
Заполнение таблицы маршрутизации [ править ]
Имея на руках кратчайшие пути, следующим шагом будет заполнение таблицы маршрутизации. Для любого заданного узла назначения наилучшим путем для этого узла назначения является узел, который является первым шагом от корневого узла вниз по ветви в дереве кратчайших путей, ведущей к желаемому узлу назначения. Чтобы создать таблицу маршрутизации, необходимо только пройтись по дереву, запомнив идентификатор узла в начале каждой ветви и заполнив запись в таблице маршрутизации для каждого встречного узла с этим идентификатором.
Оптимизация алгоритма [ править ]
Описанный выше алгоритм был сделан максимально простым, чтобы облегчить понимание. На практике используется ряд оптимизаций.
Частичный пересчет [ править ]
Каждый раз, когда происходит изменение в карте связности, необходимо повторно вычислять дерево кратчайшего пути, а затем заново создавать таблицу маршрутизации. Работа BBN Technologies [ необходима цитата ] обнаружила, как пересчитывать только ту часть дерева, на которую могло повлиять данное изменение карты. Кроме того, таблица маршрутизации обычно заполняется по мере вычисления дерева кратчайшего пути вместо того, чтобы делать это отдельной операцией.
Уменьшение топологии [ править ]
В некоторых случаях целесообразно уменьшить количество узлов, генерирующих сообщения LSA. Например, узел, который имеет только одно соединение с сетевым графом, не должен отправлять сообщения LSA, поскольку информация о его существовании может быть уже включена в сообщение LSA его единственного соседа. По этой причине может применяться стратегия сокращения топологии, при которой только подмножество сетевых узлов генерирует сообщения LSA. Два широко изучаемых подхода к уменьшению топологии:
- Многоточечные реле, которые лежат в основе протокола OLSR , но также были предложены для OSPF [4]
- Связанные доминирующие множества, которые снова были предложены для OSPF [5]
Маршрутизация по состоянию "рыбий глаз" [ править ]
С FSR LSA отправляются с разными значениями TTL, чтобы ограничить их распространение и ограничить накладные расходы из-за управляющих сообщений. Та же самая концепция используется также в протоколе маршрутизации с нечетким видением состояния канала .
Режимы отказа [ править ]
Если все узлы не работают с точно той же карты, петли маршрутизации могут формировать. Это ситуации, в которых в простейшей форме два соседних узла думают, что другой - лучший путь к заданному месту назначения. Любой пакет, направленный в этот пункт назначения, поступающий на любой узел, будет зацикливаться между ними, отсюда и название. Также возможны петли маршрутизации, включающие более двух узлов.
Это может произойти, поскольку каждый узел вычисляет свое дерево кратчайших путей и свою таблицу маршрутизации без какого-либо взаимодействия с другими узлами. Если два узла начинаются с разных карт, возможны сценарии, в которых создаются петли маршрутизации. В определенных обстоятельствах дифференциальные петли могут быть включены в многооблачной среде. Узлы переменного доступа через протокол интерфейса также могут обойти проблему одновременного доступа к узлам. [6]
Оптимизированный протокол маршрутизации состояния канала для мобильных одноранговых сетей [ править ]
Optimized Link State Routing Protocol (OLSR) представляет собой ссылку состояние протокола маршрутизации , оптимизированный для мобильных одноранговых сетей (которые также могут быть использованы на других беспроводных одноранговых сетях ). [7] OLSR является проактивным, он использует сообщения Hello и Topology Control (TC) для обнаружения и распространения информации о состоянии канала в специальной мобильной сети . Используя сообщения Hello, каждый узел обнаруживает информацию о двухсегментном соседе и выбирает набор многоточечных ретрансляторов (MPR). MPR делает OLSR уникальным по сравнению с другими протоколами маршрутизации состояния канала. Отдельные узлы используют информацию о топологии для вычисления путей следующего перехода по отношению ко всем узлам в сети с использованием кратчайших путей пересылки.
См. Также [ править ]
- Мост по кратчайшему пути 802.1aq
Ссылки [ править ]
- ^ Джон М. Маккуиллан , Исаак Ричер и Эрик К. Розен, Улучшения алгоритма маршрутизации ARPANet , Отчет BBN № 3803, Кембридж, апрель 1978 г.
- ^ Джон М. Маккуиллан , Исаак Ричер и Эрик К. Розен, Новый алгоритм маршрутизации для ARPANet , IEEE Trans. on Comm., 28 (5), pp. 711–719, 1980 г.
- ^ Прозрачное соединение множества ссылок (TRILL) Использование IS-IS , RFC 7176
- ^ https://tools.ietf.org/html/rfc5449
- ^ https://tools.ietf.org/html/rfc5614
- ^ Вуйчик R (2016). «Обзор методов обеспечения междоменной многолучевой передачи». Компьютерные сети . 108 .
- ^ RFC 3626
 | Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . ( Сентябрь 2010 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
- Джош Сигер и Атул Ханна, Снижение накладных расходов на маршрутизацию в растущем DDN , MILCOMM '86, IEEE, 1986
- Радия Перлман «R-мосты: прозрачная маршрутизация» , Инфоком, 2004.
Дальнейшее чтение [ править ]
- Раздел «Состояние канала по сравнению с вектором расстояния» в главе «Основы маршрутизации» в «Руководстве по межсетевым технологиям Cisco »
