Протокол маршрутизации состояния канала с неопределенным зрением - Hazy Sighted Link State Routing Protocol

В Протокол маршрутизации с неопределенным состоянием канала (HSLS) это беспроводная ячеистая сеть протокол маршрутизации разрабатывается CUWiN Фонд. Это алгоритм позволяя компьютеры общение через цифровое радио в ячеистая сеть для пересылки сообщений на компьютеры, недоступные для прямой радиосвязи. Его сетевые накладные расходы теоретически оптимальны,^[1] использование как проактивных, так и реактивных состояние связи маршрутизация для ограничения обновлений сети в пространстве и времени. Его изобретатели считают, что это более эффективный протокол для маршрутизации проводных сетей. HSLS был изобретен исследователями из BBN Technologies.

Эффективность

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

Почему протокол состояния канала?

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

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

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

По определению, алгоритм состояния канала использует доступную информацию для создания наилучшего маршрута, поэтому маршрутизация является максимально оптимальной с учетом доступной информации.
Неоптимальная маршрутизация происходит естественным образом, потому что удаленные узлы реже получают информацию.
Сведение к минимуму проактивных обновлений - сложная часть. Схема адаптирована из двух алгоритмов маршрутизации с ограниченным состоянием канала. Первый, «близорукая маршрутизация состояния канала», ограничен пространством, количеством узловых переходов, на которые может быть передана информация маршрутизации. Другой алгоритм маршрутизации, «дискретная маршрутизация по состоянию канала», ограничивает время, в течение которого информация маршрутизации может быть передана. Поскольку оптимальное затухание обновлений как в пространстве, так и во времени составляет около двух, результатом является периодическое упреждающее обновление с фрактальной мощностью двух узловых расстояний перехода для данных (например, расстояния перехода 1, 2, 1, 4, 1, 2, 1, 8 ...).
Реактивная маршрутизация происходит из-за того, что неудачная попытка использовать соседний канал приводит к истечению следующего таймера, вероятно, втягивая информацию для поиска альтернативного маршрута. При каждом последующем сбое повторная попытка усиливает реакцию на более широкую аудиторию связанных узлов.

Как это устроено

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

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

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

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

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

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

Преимущества

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

Фактический алгоритм довольно прост.

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

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

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

HSLS имеет хорошие свойства масштабируемости. В асимптотический масштабируемость его общих накладных расходов составляет ${ displaystyle O (N ^ {1.5})}$ по сравнению со стандартным состоянием ссылки, которое масштабируется как ${ displaystyle O (N ^ {2})}$ , где N - количество узлов в сети.

Критика

Поскольку HSLS отправляет удаленные обновления нечасто, узлы не имеют свежей информации о том, присутствует ли еще удаленный узел. Эта проблема в некоторой степени присутствует во всех протоколах состояния каналов, поскольку база данных состояний каналов может по-прежнему содержать объявление от отказавшего узла. Однако такие протоколы, как OSPF распространит обновление состояния канала от соседей отказавших узлов, и, таким образом, все узлы быстро узнают о выходе из строя (или отключении) отказавшего узла. С помощью HSLS нельзя однозначно определить между узлом, который все еще находится на расстоянии 10 переходов, и отказавшим узлом до тех пор, пока бывшие соседи не отправят междугородные объявления. Таким образом, HSLS может выйти из строя в некоторых обстоятельствах, требующих высокой надежности.

Хотя документы, описывающие HSLS, не фокусируются на безопасности, такие методы, как цифровые подписи при обновлении маршрутизации можно использовать с HSLS (аналогично OSPF с цифровой подписью ), а BBN реализовала HSLS с цифровыми подписями в сообщениях об обнаружении соседей и обновлениях состояния каналов. Такие схемы сложны на практике, потому что в для этого случая достижимость окружающей среды инфраструктура открытого ключа серверы не могут быть уверены. Как почти все протоколы маршрутизации, HSLS не включает механизмов защиты трафика данных. (Видеть IPsec и TLS.)

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

внешняя ссылка

OLSR рыбий глаз - OLSR от olsr.org реализовал алгоритм "рыбий глаз", который эквивалентен HSLS.
Прототип НРЛОЛСР - расширенный OLSR для обеспечения дополнительной возможности HSLS

[1] «Маршрутизация нечеткого состояния канала (HSLS): масштабируемый алгоритм состояния канала» (PDF). BBN Technologies. Архивировано из оригинал (PDF) на 2008-07-06. Получено 2008-02-20. Цитировать журнал требует | журнал = (помощь)

[1]