WikiDer > Протокол маршрутизации по состоянию канала

Протоколы маршрутизации на основе состояния канала являются одним из двух основных классов протоколы маршрутизации используется в коммутация пакетов сети для компьютерные коммуникации, другое существо протоколы дистанционно-векторной маршрутизации. Примеры протоколов маршрутизации по состоянию канала включают: Сначала откройте кратчайший путь (OSPF) и Промежуточная система к промежуточной системе (IS-IS).

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

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

История

То, что считается первой сетью компьютеров с адаптивной маршрутизацией, в основе которой лежит маршрутизация по состоянию канала, было разработано и реализовано в 1976-77 гг. Плесси Радар во главе с Бернардом Дж. Харрисом; Проект был разработан для «Wavell» - системы компьютерного управления и контроля для британской армии.^{[нужна цитата]}

Первая концепция маршрутизации состояния канала была опубликована в 1979 г. Джон М. Маккуиллан (тогда в Болт, Беранек и Ньюман) как механизм, который будет быстрее вычислять маршруты при изменении сетевых условий и, таким образом, приведет к более стабильной маршрутизации.^[1][2]

Позже работать в BBN Technologies показал, как использовать технику состояния канала в иерархической системе (то есть в системе, в которой сеть была разделена на области), чтобы каждому коммутационному узлу не требовалась карта всей сети, а только область (а), в которой он Включено.^{[нужна цитата]}

Позднее этот метод был адаптирован для использования в современных протоколах маршрутизации состояния канала IS-IS и OSPF. В литературе Cisco упоминается расширенный протокол маршрутизации внутреннего шлюза (EIGRP) как «гибридный» протокол,^{[нужна цитата]} несмотря на то, что он раздает таблицы маршрутизации вместо топологических карт. Однако он синхронизирует таблицы маршрутизации при запуске, как это делает OSPF, и отправляет определенные обновления только при изменении топологии.

В 2004 г. Радиа Перлман предложено использовать маршрутизацию состояния канала для слой 2 пересылка кадров с помощью устройств, называемых разводка мостов или Rbridges. В Инженерная группа Интернета стандартизировал прозрачное соединение множества ссылок (TRILL) для этого.^[3]

Совсем недавно этот иерархический метод был применен к беспроводные ячеистые сети с использованием оптимизированный протокол маршрутизации состояния канала (OLSR). Если соединение может иметь разное качество, качество соединения можно использовать для выбора лучшего соединения. Это используется в некоторых протоколы маршрутизации которые используют радиочастотную передачу.

В 2012 г. IEEE завершена и утверждена стандартизация использования IS-IS для контроля Ethernet пересылка с IEEE 802.1aq мост кратчайшего пути (SPB).

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

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

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

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

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

Распространение информации для карты

эта статья может быть сбивает с толку или неясно читателям. В частности, из приведенного описания неясно, как работают порядковые номера: 1) как они генерируются, 2) как они «обновляются», когда узел получает сообщение, 3) как именно они предотвращают отправку сообщения в цикл. Пожалуйста, помоги нам прояснить статью. Возможно обсуждение этого вопроса на страница обсуждения. (Ноябрь 2020) (Узнайте, как и когда удалить этот шаблон сообщения)

Затем каждый узел периодически (и в случае изменения подключения) отправляет короткое сообщение, реклама состояния ссылок, который:

• Обозначает узел, который его производит.
• Определяет все остальные узлы (маршрутизаторы или сети), к которым он напрямую подключен.
• Включает «порядковый номер», который увеличивается каждый раз, когда исходный узел создает новую версию сообщения..

Это сообщение отправляется на все узлы в сети. В качестве необходимого предшественника каждый узел в сети запоминает для каждого из его соседи - порядковый номер последнего сообщения о состоянии канала, полученного от этого узла. Когда узел получает объявление о состоянии канала, узел ищет сохраненный им порядковый номер для источника этого сообщения о состоянии канала: если это сообщение более новое (т. Е. Имеет более высокий порядковый номер), оно сохраняется. , порядковый номер обновляется, и копия отправляется по очереди каждому из соседей этого узла. Эта процедура быстро получает копию последней версии объявления о состоянии канала каждого узла на каждый узел в сети.

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

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

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

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

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

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

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

Как упоминалось ранее, второй основной этап в алгоритме состояния канала - создание таблиц маршрутизации путем проверки карт. Это снова делается в несколько шагов.

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

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

Узел поддерживает две структуры данных: дерево содержащие узлы, которые "готовы", и список кандидаты. Алгоритм начинается с пустых обеих структур; затем он добавляет к первому сам узел. Вариант Жадный алгоритм затем многократно делает следующее:

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

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

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

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

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

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

Частичная перерасчет

Всякий раз, когда происходит изменение в карте связности, необходимо повторно вычислять дерево кратчайшего пути, а затем заново создавать таблицу маршрутизации. Работа BBN Technologies^{[нужна цитата]} обнаружил, как пересчитывать только ту часть дерева, на которую могло повлиять данное изменение в карте. Кроме того, таблица маршрутизации обычно заполняется по мере вычисления дерева кратчайшего пути, вместо того, чтобы делать это отдельной операцией.

Уменьшение топологии

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

1. Многоточечные реле которые лежат в основе OLSR протокол, но также были предложены для OSPF^[4]
2. Связанные доминирующие множества которые снова были предложены для OSPF^[5]

Маршрутизация состояния "рыбий глаз"

С участием FSR LSA отправляются с разными значениями TTL, чтобы ограничить их распространение и ограничить накладные расходы из-за управляющих сообщений. Та же концепция используется и в Протокол маршрутизации состояния канала с неопределенным зрением.

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

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

Это может произойти, поскольку каждый узел вычисляет свое дерево кратчайших путей и свою таблицу маршрутизации, никак не взаимодействуя с другими узлами. Если два узла начинаются с разных карт, возможны сценарии, в которых создаются петли маршрутизации. В определенных обстоятельствах дифференциальные петли могут быть включены в многооблачной среде. Узлы переменного доступа через протокол интерфейса также могут обойти проблему одновременного доступа к узлам.^[6]

Оптимизированный протокол маршрутизации состояния канала для мобильных одноранговых сетей

В Оптимизированный протокол маршрутизации состояния канала (OLSR) - это протокол маршрутизации по состоянию канала, оптимизированный для мобильные специальные сети (который также можно использовать на других беспроводные сети ad hoc).^[7] OLSR является проактивным, он использует сообщения Hello и Topology Control (TC) для обнаружения и распространения информации о состоянии канала в мобильная специальная сеть. Используя приветственные сообщения, каждый узел обнаруживает информацию о двухсегментном соседе и выбирает набор многоточечные реле (MPR). MPR делает OLSR уникальным по сравнению с другими протоколами маршрутизации состояния канала. Отдельные узлы используют информацию о топологии для вычисления путей следующего перехода по отношению ко всем узлам в сети с использованием кратчайших путей пересылки.

Смотрите также

• Мост по кратчайшему пути 802.1aq

использованная литература

Эта статья включает в себя список общих использованная литература, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшить эта статья введение более точные цитаты. (Сентябрь 2010 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

• Джош Сигер и Атул Кханна, Снижение накладных расходов на маршрутизацию в растущем DDN, MILCOMM '86, IEEE, 1986
• Радиа Перлман «Rbridges: прозрачная маршрутизация», Инфоком 2004.

дальнейшее чтение

• Раздел «Связь состояния в зависимости от вектора расстояния» в главе «Основы маршрутизации» в Cisco «Справочник по межсетевым технологиям»