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

Протоколы маршрутизации по состоянию канала — это один из двух основных классов протоколов маршрутизации, используемых в коммутации пакетов сетях для компьютерной связи , остальные — протоколы маршрутизации на основе вектора расстояния . ^{[ 1 ]} Примеры протоколов маршрутизации по состоянию канала включают в себя Open Shortest Path First (OSPF) и Intermediate System to Intermediate System (IS-IS). ^{[ 2 ]}

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

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

Обзор

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

Это контрастирует с протоколами маршрутизации на основе вектора расстояния , которые работают, заставляя каждый узел делиться своей таблицей маршрутизации со своими соседями. В протоколе состояния канала единственная информация, передаваемая между узлами, — это информация, используемая для построения карт связности.

История

То, что считается первой компьютерной сетью адаптивной маршрутизации, использующей маршрутизацию по состоянию канала, было спроектировано и реализовано в 1976–1977 годах командой Plessey Radar под руководством Бернарда Дж. Харриса; проект предназначался для «Вейвелла» — системы компьютерного управления и контроля для британской армии . ^{[ нужна ссылка ]} Первая концепция маршрутизации по состоянию канала была опубликована в 1979 году Джоном М. Маккуилланом (тогда в Bolt, Beranek and Newman ) как механизм, который позволял быстрее рассчитывать маршруты при изменении условий сети и, таким образом, приводил к более стабильной маршрутизации. ^{[ 9 ]}^{[ 10 ]}^{[ 11 ]}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сокращение топологии

В некоторых случаях разумно уменьшить количество узлов, генерирующих сообщения LSA. По этой причине можно применить стратегию сокращения топологии, при которой только подмножество сетевых узлов генерирует сообщения LSA. Два широко изученных подхода к уменьшению топологии — это многоточечные ретрансляторы , которые лежат в основе протокола маршрутизации с оптимизированным состоянием канала (OLSR), но также были предложены для OSPF. ^{[ 14 ]} и связанные доминирующие наборы , которые снова были предложены для OSPF. ^{[ 15 ]}

Государственная маршрутизация «рыбий глаз»

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

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

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

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

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

Оптимизированный протокол маршрутизации по состоянию канала (OLSR) — это протокол маршрутизации по состоянию канала, оптимизированный для мобильных одноранговых сетей (который также можно использовать в других беспроводных одноранговых сетях ). ^{[ 17 ]} OLSR действует упреждающе и использует сообщения приветствия и управления топологией для распространения информации о состоянии канала в мобильную одноранговую сеть. Используя сообщения приветствия, каждый узел обнаруживает информацию о соседях с двумя переходами и выбирает набор многоточечных ретрансляторов (MPR). MPR отличает OLSR от других протоколов маршрутизации по состоянию канала. Отдельные узлы используют информацию о топологии для расчета путей следующего перехода относительно всех узлов в сети, используя пути пересылки кратчайшего перехода.

См. также

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

Ссылки

^ «Одноадресная маршрутизация — маршрутизация по состоянию канала» . Гики для Гиков . 18 мая 2018 г. Проверено 9 мая 2024 г.
^ lec10-lsrouting.pdf (princeton.edu) https://www.cs.princeton.edu/courses/archive/spring23/cos461/lectures/lec10-lsrouting.pdf
^ лекции6.pptx (umich.edu) https://www.eecs.umich.edu/courses/eecs489/w10/winter10/lectures/lecture6_2.pdf
^ 123sp15-lec14.pdf (ucsd.edu) https://cseweb.ucsd.edu/classes/sp15/cse123-a/lectures/123sp15-lec14.pdf
^ ссылка на протокол состояния.pdf (fauser.edu) http://nuovolabs.fauser.edu/~valeria/materiale-didattico/sistemi-quinta/link%20state%20protocol.pdf
^ «9.6: Алгоритм маршрутизации и обновления состояния канала» . Инженерные библиотеки LibreTexts . 12 августа 2019 г. Проверено 9 мая 2024 г.
^ 5-routing-part2.pdf (washington.edu) https://courses.cs.washington.edu/courses/cse461/22sp/slides/5-routing-part2.pdf
^ Библиотека, широкополосный доступ (31 августа 2018 г.). «Более внимательный взгляд на маршрутизацию |» . Проверено 9 мая 2024 г.
^ Джон М. Маккуиллан , Исаак Ричер и Эрик К. Розен, Усовершенствования алгоритма маршрутизации ARPANet , Отчет BBN № 3803, Кембридж, апрель 1978 г.
^ Джон М. Маккуиллан , Исаак Ричер и Эрик К. Розен, Новый алгоритм маршрутизации для ARPANet , IEEE Trans. по сообщению, 28 (5), стр. 711–719, 1980 г.
^ Болат, Доррис М. «Route4Me» . Проверено 12 декабря 2021 г.
^ «Руководство по настройке Cisco Firepower Threat Defense для Firepower Device Manager, версия 7.1 — расширенный протокол маршрутизации внутреннего шлюза (EIGRP) [Cisco Secure Firewall Threat Defense]» . Циско . Проверено 18 января 2024 г.
^ Истлейк 3-й, Дональд Э.; Сеневиратне, Тисса; Ганвани, Ануп; Датт, Динеш; Банерджи, Аян (май 2014 г.), Прозрачное соединение множества ссылок (TRILL) Использование IS-IS , doi : 10.17487/RFC7176 , RFC 7176 {{citation}}: CS1 maint: числовые имена: список авторов ( ссылка )
^ Нгуен, Данг-Куан; Клаузен, Томас Х.; Жаке, Филипп; Бачелли, Эммануэль (февраль 2009 г.). «Расширение многоточечной ретрансляции OSPF (MPR) для одноранговых сетей» . дои : 10.17487/RFC5449 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Ожье, Ришар; Спаньоло, Фил (август 2009 г.). «Расширение OSPF для мобильной одноранговой сети (MANET) с использованием рассылки подключенного доминирующего набора (CDS)» . дои : 10.17487/RFC5614 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Войчик, Р. (2016). «Обзор методов обеспечения междоменной многолучевой передачи». Компьютерные сети . 108 : 233–259. дои : 10.1016/j.comnet.2016.08.028 .
^ RFC 3626

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

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

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

[1] «Одноадресная маршрутизация — маршрутизация по состоянию канала» . Гики для Гиков . 18 мая 2018 г. Проверено 9 мая 2024 г.

[2] 10-lsrouting.pdf (princeton.edu) https://www.cs.princeton.edu/courses/archive/spring23/cos461/lectures/lec10-lsrouting.pdf

[3] лекции6.pptx (umich.edu) https://www.eecs.umich.edu/courses/eecs489/w10/winter10/lectures/lecture6_2.pdf

[4] 123sp15-lec14.pdf (ucsd.edu) https://cseweb.ucsd.edu/classes/sp15/cse123-a/lectures/123sp15-lec14.pdf

[5] ссылка на протокол состояния.pdf (fauser.edu) http://nuovolabs.fauser.edu/~valeria/materiale-didattico/sistemi-quinta/link%20state%20protocol.pdf

[6] «9.6: Алгоритм маршрутизации и обновления состояния канала» . Инженерные библиотеки LibreTexts . 12 августа 2019 г. Проверено 9 мая 2024 г.

[7] 5-routing-part2.pdf (washington.edu) https://courses.cs.washington.edu/courses/cse461/22sp/slides/5-routing-part2.pdf

[8] Библиотека, широкополосный доступ (31 августа 2018 г.). «Более внимательный взгляд на маршрутизацию |» . Проверено 9 мая 2024 г.

[9] Джон М. Маккуиллан , Исаак Ричер и Эрик К. Розен, Усовершенствования алгоритма маршрутизации ARPANet , Отчет BBN № 3803, Кембридж, апрель 1978 г.

[10] Джон М. Маккуиллан , Исаак Ричер и Эрик К. Розен, Новый алгоритм маршрутизации для ARPANet , IEEE Trans. по сообщению, 28 (5), стр. 711–719, 1980 г.

[11] Болат, Доррис М. «Route4Me» . Проверено 12 декабря 2021 г.

[12] «Руководство по настройке Cisco Firepower Threat Defense для Firepower Device Manager, версия 7.1 — расширенный протокол маршрутизации внутреннего шлюза (EIGRP) [Cisco Secure Firewall Threat Defense]» . Циско . Проверено 18 января 2024 г.

[13] Истлейк 3-й, Дональд Э.; Сеневиратне, Тисса; Ганвани, Ануп; Датт, Динеш; Банерджи, Аян (май 2014 г.), Прозрачное соединение множества ссылок (TRILL) Использование IS-IS , doi : 10.17487/RFC7176 , RFC 7176 {{citation}}: CS1 maint: числовые имена: список авторов ( ссылка )

[14] Нгуен, Данг-Куан; Клаузен, Томас Х.; Жаке, Филипп; Бачелли, Эммануэль (февраль 2009 г.). «Расширение многоточечной ретрансляции OSPF (MPR) для одноранговых сетей» . дои : 10.17487/RFC5449 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[15] Ожье, Ришар; Спаньоло, Фил (август 2009 г.). «Расширение OSPF для мобильной одноранговой сети (MANET) с использованием рассылки подключенного доминирующего набора (CDS)» . дои : 10.17487/RFC5614 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[16] Войчик, Р. (2016). «Обзор методов обеспечения междоменной многолучевой передачи». Компьютерные сети . 108 : 233–259. дои : 10.1016/j.comnet.2016.08.028 .

[17] RFC 3626

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]