Протокол Hazy-Sighted Link State Routing Protocol ( HSLS ) - это протокол маршрутизации беспроводной ячеистой сети , разработанный CUWiN Foundation. Это алгоритм, позволяющий компьютерам, обменивающимся данными по цифровому радио в ячеистой сети, пересылать сообщения компьютерам, которые находятся вне досягаемости прямого радиоконтакта. Его сетевые накладные расходы теоретически оптимальны [1] с использованием как упреждающего, так и реактивного состояния канала.маршрутизация для ограничения обновлений сети в пространстве и времени. Его изобретатели считают, что это более эффективный протокол для маршрутизации проводных сетей. HSLS был изобретен исследователями BBN Technologies .
Эффективность
HSLS хорошо масштабируется для сетей из более чем тысячи узлов, а в более крупных сетях начинает превосходить эффективность других алгоритмов маршрутизации. Это достигается за счет использования тщательно продуманного баланса частоты обновления и степени обновления для оптимального распространения информации о состоянии канала. В отличие от традиционных методов, HSLS не наводняет сеть информацией о состоянии канала, чтобы попытаться справиться с движущимися узлами, которые меняют соединения с остальной частью сети. Кроме того, HSLS не требует, чтобы каждый узел имел одинаковое представление о сети.
Почему протокол состояния канала?
Алгоритмы состояния канала теоретически привлекательны, потому что они находят оптимальные маршруты, уменьшая потери пропускной способности. Изобретатели HSLS утверждают [ необходима цитата ], что протоколы маршрутизации делятся на три принципиально разные схемы: проактивные (такие как OLSR ), реактивные (такие как AODV ) и алгоритмы, которые принимают неоптимальную маршрутизацию. Если их построить в виде графика, они станут менее эффективными, поскольку представляют собой более чисто любую отдельную стратегию, и сеть станет больше. Лучшие алгоритмы, кажется, находятся посередине.
Информация о маршрутизации называется «обновлением состояния канала». Расстояние, на которое копируется состояние связи, является « временем жизни » и представляет собой количество раз, когда оно может быть скопировано с одного узла на другой.
Говорят, что HSLS оптимально балансирует функции упреждающего, реактивного и субоптимального подходов к маршрутизации. Эти стратегии сочетаются путем ограничения обновлений состояния ссылок во времени и пространстве. Ограничивая время жизни, уменьшается пропускная способность. Ограничивая время передачи упреждающего обновления маршрутизации, можно собирать и передавать сразу несколько обновлений, что также экономит пропускную способность.
- По определению, алгоритм состояния канала использует доступную информацию для создания наилучшего маршрута, поэтому маршрутизация является максимально оптимальной с учетом доступной информации.
- Неоптимальная маршрутизация происходит естественным образом, потому что удаленные узлы реже получают информацию.
- Сведение к минимуму проактивных обновлений - сложная часть. Схема адаптирована из двух алгоритмов маршрутизации с ограниченным состоянием канала. Один, «близорукая маршрутизация состояния канала», ограничен пространством, количеством узловых переходов, на которые может быть передана информация маршрутизации. Другой алгоритм маршрутизации, «дискретная маршрутизация по состоянию канала», ограничивает время, в течение которого информация маршрутизации может быть передана. Поскольку оптимальное затухание обновления как в пространстве, так и во времени составляет около двух, результатом является периодическое упреждающее обновление с фрактальной мощностью двух узловых расстояний перехода для данных (например, расстояния перехода 1, 2, 1, 4, 1, 2, 1, 8 ...).
- Реактивная маршрутизация происходит из-за того, что неудачная попытка использовать соседний канал приводит к истечению следующего таймера, вероятно, с использованием информации для поиска альтернативного маршрута. При каждом последующем сбое повторная попытка усиливает реакцию на более широкую аудиторию узлов сети.
Как это работает
Разработчики начали настройку этих элементов с определения меры потерь глобальной сети. Сюда входят потери из-за передачи обновлений маршрута, а также из-за неэффективных путей передачи. Их точное определение: «Общие накладные расходы определяются как количество полосы пропускания, используемой сверх минимального количества полосы пропускания, требуемого для пересылки пакетов на кратчайшее расстояние (в количестве переходов), при условии, что узлы имеют мгновенную информацию о полной топологии. "
Затем они сделали некоторые разумные предположения и использовали математическую оптимизацию, чтобы найти время для передачи обновлений состояния канала, а также широту узлов, которые должны охватывать обновления состояния канала.
По сути, оба значения должны возрастать до степени двойки с увеличением времени. Теоретическое оптимальное число очень близко к двум с ошибкой всего 0,7%. Это значительно меньше вероятных ошибок, исходящих из предположений, поэтому два - вполне разумное число.
Обновление локальной маршрутизации принудительно происходит при потере соединения. Это реактивная часть алгоритма. Обновление локальной маршрутизации ведет себя так же, как истечение таймера.
В противном случае каждый раз, когда задержка с момента последнего обновления удваивается, узел передает информацию о маршруте, которая удваивается по количеству учитываемых им сетевых переходов. Это продолжается до некоторого верхнего предела. Верхний предел дает сети глобальный размер и гарантирует фиксированное максимальное время отклика для сети без каких-либо движущихся узлов.
Алгоритм имеет несколько специальных функций, которые позволяют справиться со случаями, которые распространены в радиосетях, такими как однонаправленные каналы и циклическая передача, вызванная устаревшими таблицами маршрутизации . В частности, он перенаправляет все передачи к ближайшим узлам всякий раз, когда теряет ссылку на соседний узел. Когда это происходит, он также повторно передает свою смежность. Это полезно именно потому, что наиболее ценные междугородные линии связи являются наименее надежными в радиосети.
Преимущества
Сеть устанавливает довольно хорошие маршруты в режиме реального времени и значительно сокращает количество и размер сообщений, отправляемых для поддержания связи в сети, по сравнению со многими другими протоколами. Многие из более простых протоколов маршрутизации ячеистой сети просто наводняют всю сеть маршрутной информацией при каждом изменении канала.
Фактический алгоритм довольно прост.
Информация о маршрутизации и передача данных децентрализованы и поэтому должны иметь хорошую надежность и производительность без локальных горячих точек.
Системе требуются функциональные узлы с большим объемом памяти для поддержки таблиц маршрутизации. К счастью, они все время становятся дешевле.
Система дает очень быстрое и относительно точное предположение о том, находится ли узел в сети, поскольку полная, хотя и устаревшая информация о маршрутизации присутствует на каждом узле. Однако это не то же самое, что знать, находится ли узел в сети. Это предположение может быть адекватным для большинства тарифных сетей, таких как телефония, но может не подходить для военных или авионики, связанных с безопасностью .
HSLS имеет хорошие свойства масштабируемости. Асимптотическая масштабируемость общего объема накладных расходов по сравнению со стандартным состоянием ссылки, которое масштабируется как , где N - количество узлов в сети.
Критика
Поскольку HSLS отправляет удаленные обновления нечасто, узлы не имеют свежей информации о том, присутствует ли еще удаленный узел. Эта проблема в некоторой степени присутствует во всех протоколах состояния каналов, поскольку база данных состояний каналов все еще может содержать объявление от отказавшего узла. Однако протоколы, такие как OSPF, будут распространять обновление состояния канала от соседей отказавших узлов, и, таким образом, все узлы быстро узнают о выходе из строя (или отключении) отказавшего узла. С помощью HSLS нельзя однозначно определить между узлом, который все еще находится на расстоянии 10 переходов, и отказавшим узлом до тех пор, пока бывшие соседи не отправят междугородние объявления. Таким образом, HSLS может дать сбой в некоторых обстоятельствах, требующих высокой надежности.
В то время как документы, описывающие HSLS, не фокусируются на безопасности, такие методы, как цифровые подписи при обновлении маршрутизации, могут использоваться с HSLS (аналогично OSPF с цифровыми подписями ), а BBN реализовала HSLS с цифровыми подписями в сообщениях об обнаружении соседей и обновлениях состояния каналов. Такие схемы сложны на практике, потому что в специальной среде невозможно гарантировать доступность серверов инфраструктуры открытых ключей . Как почти все протоколы маршрутизации, HSLS не включает механизмов защиты трафика данных. (См. IPsec и TLS .)
Смотрите также
Рекомендации
- ^ «Маршрутизация нечеткого состояния канала (HSLS): масштабируемый алгоритм состояния канала» (PDF) . BBN Technologies. Архивировано из оригинального (PDF) 06.07.2008 . Проверено 20 февраля 2008 . Цитировать журнал требует
|journal=
( помощь )
Внешние ссылки
- OLSR fisheye - OLSR от olsr.org реализовал алгоритм «рыбий глаз», который эквивалентен HSLS.
- Прототип NRLOLSR - расширенный OLSR для обеспечения дополнительной возможности HSLS