eng
Выпуск #1/2009
В.Вишневский, Д.Лаконцев, А.Сафонов, С.Шпилев.
Mesh-сети стандарта IEEE 802.11s: протоколы маршрутизации
Mesh-сети стандарта IEEE 802.11s: протоколы маршрутизации
Просмотры: 3989
Мы продолжаем* рассказ о технологии беспроводных mesh-сетей стандарта IEEE 802.11s. В новой статье рассмотрены протоколы маршрутизации в mesh-сетях. Это один из ключевых элементов данной технологии, ему посвящено более 20% текста стандарта IEEE 802.11s. Столь пристальное внимание к маршрутизации связано со сложной топологией, высокой мобильностью, большим числом устройств и прочими особенностями mesh-сетей.
Критерии выбора оптимальных путей в сети
Для выбора оптимальных маршрутов в сети используются различные критерии (метрики). Метрики могут включать в себя такую информацию, как длина пути (количество шагов), надежность, задержка, пропускная способность, загрузка, стоимость передачи трафика и так далее. Наиболее распространенной метрикой является длина пути. Некоторые протоколы маршрутизации позволяют администратору сети присвоить каналу (путь длиной в один шаг) произвольную длину. При этом длина пути – это сумма длин каналов, через которые пролегает путь от источника (отправителя) к адресату (получателю). Другие протоколы определяют число шагов – сколько сетевых устройств (например, маршрутизаторов) должен пройти пакет на своем пути к получателю.
Еще один критерий выбора оптимальных маршрутов – надежность. Под метрикой "надежность" обычно подразумевается доля потерь пакетов в каждом из каналов. Некоторые каналы разрываются чаще, чем другие. Или восстанавливаются проще и быстрее после ошибки в работе сети. Любые факторы надежности могут учитываться при получении численного значения данной метрики.
Другая популярная метрика – задержка, т.е. время, необходимое для доставки пакета от отправителя к получателю. Задержка зависит от многих факторов, включая пропускную способность каналов, очереди в портах устройств на пути пакета, загрузку сети во всех промежуточных каналах, а также физическое расстояние, которое нужно преодолеть. Поскольку задержка зависит от ряда важных факторов, это распространенная и полезная метрика.
Пропускная способность также часто используется как критерий выбора пути. Под ней подразумевается объем данных, который может быть передан по сети в единицу времени.
Метрика, напрямую связанная с пропускной способностью, – это загрузка, которая отражает степень занятости сетевых ресурсов, таких как каналы и маршрутизаторы. Загрузку можно вычислить различными способами, включая загрузку процессора и число обрабатываемых или передаваемых в секунду пакетов. Следует отметить, что постоянный анализ этих показателей сам по себе может потребовать значительных ресурсов сетевого оборудования.
Существенно отличается от перечисленных выше критериев метрика "стоимость". Некоторые компании в целях экономии предпочитают использовать пути через собственные каналы, а не через более высокопроизводительные, но платные, каналы других операторов.
Метрика отдельных каналов может быть статической (задаваемой администратором сети) и динамической. Пример первой – метрика стоимости. Динамическая метрика может измеряться по уровню сигнала, задержке пакетов и множеству других параметров. Причем она может определяться как пассивно, без дополнительных служебных пакетов, так и использовать специальные "пробные" пакеты для сбора статистики по каждому каналу (задержки, потери и пр.).
Стандарт IEEE 802.11s* требует, чтобы все устройства поддерживали метрику времени передачи в канале (Airtime Link Metric). Эта обязательная метрика необходима для совместимости устройств. Она задается формулой
ca = (O + Bt / r) / (1 - ef), где O и Bt – константы, определенные стандартом для различных физических реализаций (802.11a, 802.11b): Bt – число битов в тестовом пакете (8192), O – накладные расходы доступа к каналу, которые включают в себя заголовки пакетов, кадры протоколов доступа и т.д.; r – скорость передачи данных в канале (Мбит/с); ef – вероятность возникновения ошибки (измеряется экспериментально на пакетах длиной Bt). Эта метрика представляет собой оценку времени передачи (в секундах) пробного пакета длиной Bt с учетом возможных ретрансляций при потерях в канале. Способ определения параметров r и ef в стандарте не приводится, однако можно предположить, что для этого должна использоваться периодическая рассылка пробных пакетов длиной Bt = 8192 бит.
В основе метода выбора пути для передачи данных в стандарте IEEE 802.11s лежит механизм профилей. Этот механизм обеспечивает совместимость устройств от разных производителей, которые могут поддерживать как стандартизованные механизмы, так и собственные. Профиль – это запись вида <Идентификатор профиля><Идентификатор протокола маршрутизации><Идентификатор метрики протокола маршрутизации>. Устройство может поддерживать несколько профилей работы, но единовременно лишь один из них может быть активным. Обязательный для реализации профиль использует протокол HWMP и метрику времени передачи Airtime Link Metric.
Производители вольны реализовать собственные алгоритмы маршрутизации и метрики к ним, а также и определять дополнительные проприетарные профили. Поэтому вопрос эффективности механизмов маршрутизации и метрик является одним из важнейших для разработчиков mesh-устройств.
Гибридный беспроводной mesh-протокол маршрутизации (HWMP)
Гибридный протокол маршрутизации HWMP (Hybrid Wireless Mesh Protocol) использует стандартный набор служебных пакетов, правил их создания и обработки, наподобие хорошо известного протокола дистанционно-векторной маршрутизации по запросу (Ad Hoc On Demand Distance Vector, AODV) [3]. Однако HWMP адаптирован для работы с адресами MAC-уровня и метриками путей. Гибридным он назван потому, что объединяет в себе два режима построения путей, которые могут быть использованы как по отдельности, так и одновременно в одной сети:
* реактивный режим – построение маршрутных таблиц в узлах mesh-сети непосредственно перед передачей данных (по запросу);
* проактивный режим – регулярная процедура обновления информации в маршрутных таблицах узлов всей сети. Процедуру инициирует корневой узел, в результате на сети строится граф (дерево) путей с вершиной в корневом узле.
В реактивном режиме HWMP узел отправляет широковещательный PREQ-пакет запроса пути (Path Request). Пути выбираются на основании метрики, для распространения информации о которой служит специальное поле в служебных пакетах запроса пути. Этот пакет распространяется через соседние узлы по всей сети, пока не достигнут узел-адресат. По мере продвижения от узла к узлу модифицируется поле метрики пути от текущего узла до отправителя. В итоге формируется полная метрика пути "получатель-отправитель". Узел-адресат отправляет инициатору пакет подтверждения PREP (Path Reply), содержащий итоговое значение метрики пути "инициатор-получатель". Приняв его, узел-инициатор получает информацию об установленном пути.
Очевидно, что в mesh-сети широковещательные пакеты запроса доходят до получателя по множеству путей через различные узлы. При этом они могут начать передаваться по замкнутым маршрутам (циклам), не единожды проходя через какой-либо узел. Чтобы избежать такой ситуации, используется порядковый номер запроса. В стандарте IEEE 802.11s он именуется порядковым номером назначения (Destination Sequence Number, DSN), что вносит невероятную путаницу. Кроме DSN, стандарт оперирует понятием DSN инициатора (поиска пути) – Originator's DSN (OSN). Именно этот параметр и служит порядковым номером при рассылке пакетов поиска пути. Каждое mesh-устройство имеет собственный DSN. Перед началом процедуры поиска пути DSN инициатора увеличивается на 1 и записывается в поле Originator's DSN пакета запроса PREQ. Кроме того, в пакете содержится адрес инициатора (адрес начала пути). Все узлы mesh-сети хранят информацию о каждом узле mesh-сети, обновляя ее на основании полученных служебных пакетов. Такая информация в данных пакетах передается в полях "адрес отправителя", "метрика пути", "порядковый номер".
Узел, получив пакет PREQ, сравнивает значение OSN с ранее сохраненным значением для этого же отправителя (если таковое имеется). Устройство принимает, обрабатывает и ретранслирует пакет PREQ, только если текущий OSN в пакете больше ранее сохраненного или они равны, но метрика пути ранее полученного пакета хуже, чем у вновь полученного (т.е. повторного приема и ретрансляции одного и того же пакета быть не может). В реактивном режиме пакеты подтверждения PREP может отправлять не только узел назначения, но и все промежуточные узлы, успешно принявшие пакет запроса PREQ (если в пакете установлены соответствующие флаги).
Помимо полей метрики пути, по мере прохождения от узла к узлу в пакете может изменяться значение поля "время жизни" (Time to Live, TTL) – число промежуточных узлов, которые разрешено пройти данному пакету. Если этот параметр используется, он декрементируется в каждом узле следования. Когда TTL = 0, обработка и трансляция пакета прекращается.
Проактивный режим отличается от реактивного тем, что в сети назначается корневой узел (узлы). Этот узел периодически рассылает пакеты PREQ, которые распространяются по всей сети. Все узлы сети, принявшие проактивный PREQ, сохраняют адрес узла-отправителя (через который лежит путь к корневому узлу), широковещательно транслируют PREQ с измененными полями (поля метрики и TTL) и отправляют PREP корневому узлу (либо не отправляют, в зависимости от установок).
Помимо описанных методов выбора пути на основе пакетов PREQ/PREP стандарт предусматривает процедуру на основе пакетов оповещения о корневом узле RANN (Root Announcement). Но этот метод принципиально не отличается от уже рассмотренного.
Возможны ситуации одновременного использования реактивного и проактивного режимов HWMP. Например, в сети штатно используется проактивный режим протокола HWMP, но какой-либо узел использует метод выбора пути по запросу для установления прямого соединения с другим заданным узлом.
Протокол маршрутизации HWMP обязателен для всех устройств стандарта IEEE 802.11s как протокол по умолчанию.
Оптимизированный протокол состояния канала для беспроводной сети (RA-OLSR)
Помимо протокола маршрутизации HWMP ранние версии IEEE 802.11s [4, 5] предполагали использование стандарта RA-OLSR (Radio Aware OLSR) – модификации оптимизированного протокола маршрутизации по состоянию канала OLSR (Optimized Link State Routing). OLSR – это описанный в документе IETF RFC 3626 [6] проактивный протокол маршрутизации для мобильных ad hoc сетей. Он поддерживает маршрутные таблицы в узлах сети при помощи регулярных процедур обновления маршрутной информации в сети. Протокол эффективен для больших и плотных мобильных сетей.
OLSR основан на понятии многоточечной эстафеты MPR (MultiPoint Relay). Каждый узел сети m выбирает несколько узлов из числа своих соседей (т.е. из узлов, с которыми у него установлено соединение). В итоге в сети формируется набор узлов MPR(m). Причем он формируется так, что все узлы, находящиеся в сфере с радиусом 2 шага от узла m (соседи соседей), имеют симметричные каналы с MPR(m). Это означает, что узлы MPR связаны со всеми узлами в сфере с радиусом 2 шага. MPR выбираются каждый раз, когда обнаруживается изменение в сфере с радиусом 1 или 2.
Каждый узел сети хранит свою таблицу маршрутизации, которую формирует на основании информации о топологии сети. Она распространяется по всей сети посредством служебных пакетов выбора маршрута Topology Control (TC). Причем только MPR-узлы участвуют в пересылке ТС-пакетов, остальные узлы принимают и обрабатывают такие пакеты, но не пересылают их дальше.
Для каждого MPR формируется список соседних узлов, выбравших его в качестве MPR, – список MPR Selectors (MPRS). Информация о MPRS передается в специальных HELLO-пакетах, которые передаются только между двумя соседними узлами. В сеть (в ТС-пакетах) передается только информация о состоянии соединений между MPR и его MPRSs. Данный механизм позволяет существенно снизить число передач служебных пакетов по сравнению с лавинной рассылкой [6, 7].
В протоколе OLSR служебные сообщения содержат последовательные номера (аналог DSN в HWMP), которые увеличиваются в последующих сообщениях. Таким образом, получатель контрольного сообщения может при необходимости с легкостью определить, какая информация является более новой, даже если сообщения пришли в обратном порядке.
OLSR разработан как совершенно распределенный протокол, он не зависит от каких-либо корневых узлов. Кроме того, каждый узел шлет контрольные пакеты периодически, поэтому протокол устойчив в случае потери части этих сообщений, что довольно часто случается с широковещательными пакетами в беспроводных сетях.
Протокол RA-OLSR детально описан в [5] и практически совпадает с оригинальным OLSR [6]. По сравнению с протоколом OLSR, модификация RA-OLSR сводится к управлению энергопотреблением. В ней также не фиксируется процедура выбора узлов MPR, ее может задавать производитель устройства. Протокол RA-OLSR присутствовал в ранних вариантах стандарта как опциональный, однако с версии D1.07 [8] от него отказались. Поводом для этого послужил тот факт, что RA-OLSR дублирует функциональность HWMP, являющегося и про- и реактивным протоколом, а стандарт допускает применение любых других протоколов маршрутизации [9]. Кроме того, RA-OLSR вызвал множество замечаний, в основном указывающих на неточности его описания в тексте стандарта. Также чрезмерным оказался размер самого описания этого протокола (48 из 246 страниц документа IEEE 802.11s были посвящены RA-OLSR) [9, 10]. Таким образом, отказ от RA-OLSR не связан с его недостатками [11, 12], рабочая группа просто решила оставить вопрос выбора альтернативного механизма маршрутизации производителям оборудования.
Сравнительный анализ протоколов маршрутизации
Мы провели анализ эффективности протоколов маршрутизации достаточно сложной сети (см. рисунок) посредством компьютерного моделирования на языке GPSS World (General Purpose Simulation System) [13]. Рассматривалась сеть без шумов, работающая по протоколу IEEE 802.11a с дополнением IEEE 802.11s на скорости 54 Мбит/с. Практически все потоки данных в этой модели направляются от конечных узлов (1–20) в Интернет через шлюзы (узлы 41–42), в обратном направлении передается примерно 2% от общего числа пакетов.
Для оценки производительности протоколов маршрутизации сравнивались пропускная способность, средние длины путей (в шагах) от конечных узлов до ближайшего шлюза (табл.1) и другие параметры. На рисунке видны кратчайшие пути от узлов до шлюзов: три шага для узлов 1–20, два шага для узлов 21–34 и один шаг для узлов 35–40.
Видно, что в случае HWMP пути становятся в 1,5 раза длиннее, а это, в свою очередь, сильно сказывается на остальных параметрах сети. Так, пропускная способность сети тоже снижается практически в 1,5 раза по сравнению с RA-OLSR. Число посылок пакетов данных в сети на каждый доставленный пакет возрастает на 10%, а время доставки пакетов – на 20%. Это объясняется тем, что с ростом длины путей увеличивается число коллизий, а с ними – и число повторных посылок.
Однако в приведенном эксперименте, кроме метода маршрутизации, сыграл свою роль и недостаток метода измерения метрики времени передачи, предложенной в стандарте IEEE 802.11s. Для измерения метрики использовалась групповая отправка пробных пакетов, которая увеличивала загрузку сети, а полученная таким образом метрика случайным образом менялась от измерения к измерению, что влекло выбор неоптимальных маршрутов.
Чтобы выяснить характеристики именно метода маршрутизации, аналогичный эксперимент проводился с использованием простейшей метрики – количества шагов до узла (табл.2.). В этом случае алгоритм RA-OLSR выбирает практически идеальные пути, а HWMP, хотя и дает заметно лучшие результаты по сравнению с предыдущим экспериментом, тем не менее остается на 16% хуже по этому параметру. Как и в случае с предложенной в стандарте метрикой, это сильно сказывается на пропускной способности сети. Время доставки пакетов и отношение числа посылок пакетов данных к числу доставленных пакетов в случае HWMP становится даже лучше, чем для RA-OLSR. Но объясняется это лишь тем, что алгоритм RA-OLSR обеспечивает почти в 1,5 раза большую загрузку сети (пропускная способность), что существенно сказывается на данных параметрах.
Возникающие проблемы с HWMP объяснить несложно. Ведь данный протокол предельно прост и хранит минимум информации. Так, ему известен только один путь до каждого из узлов mesh-сети. Каждый вновь прибывший от данного отправителя PREQ-пакет, если его DSN больше предыдущего или метрика лучше, считается пришедшим по единственно верному пути. Если же PREQ-пакет, шедший по более короткому пути, был потерян (а для широковещательных пакетов это явление довольно частое), то путь автоматически становится длиннее, чем он есть на самом деле. В случае с RA-OLSR таких проблем не возникает, так как узлы знают всю (или почти всю) топологию сети, да и путь через узел исчезает только при многократном неполучении информации о нем.
Таким образом, хотя в стандарте и остался только один протокол маршрутизации и одна метрика, они требуют серьезной доработки. В случае, если их недостатки не будут исправлены, производителям устройств придется самим выбирать оптимальные методы маршрутизации и метрики. И очевидным кандидатом на эту роль, как видно из приведенного исследования, выступает протокол маршрутизации RA OLSR.
Реализованные протоколы маршрутизации для mesh-сетей
В связи с тем, что стандарт mesh-сетей находится в стадии доработки, многие ведущие фирмы мира предлагают свои собственные протоколы маршрутизации. Известно довольно много различных разработок, но, к сожалению, в большинстве своем они лишь поверхностно описаны разработчиками.
Так, в беспроводной платформе Cisco Aironet 1520 Series фирмы Cisco Systems используется проприетарный протокол маршрутизации Cisco's Adaptive Wireless Path Protocol (AWPP). Логика протокола скрыта, однако по косвенным данным можно предположить, что он базируются на одной из версий HWMP, работающего в проактивном режиме. Управление и мониторинг сети, т.е. функция корневого узла, реализует специальное устройство – контроллер беспроводной сети Cisco Wireless LAN Controller, компания рекомендует использовать в mesh-сетях контроллеры серии 4400.
Довольно много информации о маршрутизации в своих сетях представила корпорация Microsoft. Компания разработала реактивный протокол маршрутизации, основанный на алгоритме динамической маршрутизации источника DSR (Dynamic Source Routing). Он очередь похож на протокол Ad Hoc On Demand Distance Vector (т.е. на HWMP), с той лишь разницей, что для маршрутизации от источника до адресата используется маршрутная таблица источника, а не промежуточных узлов.
Компания Microsoft предложила и протокол маршрутизации источника по качеству канала (Link Quality Source Routing, LQSR), который является адаптацией DSR на виртуальный второй с половиной уровень эталонной сетевой модели взаимодействия открытых систем OSI. Введение промежуточного уровня предпринято компанией, чтобы сделать протокол прозрачным для более высокого уровня, но при этом обеспечить его корректную работу при переходе между проводной и беспроводной сетями. К предложенному протоколу прилагается пять различных метрик: количество шагов; время на получение ответа (Round Trip Time, RTT); время на посылку пробного пакета от источника до адресата и обратно (Packet Pair); ожидаемое время передачи (Expected Transmission Time, ETT) и взвешенное совокупное ожидаемое время передачи (Weighted Cumulative ETTs, WCETT). Помимо основного протокола LQSR, есть версия многоинтерфейсного LQSR (MR-LQSR – Multi-Radio Link Quality Source Routing), которая, согласно экспериментам, дает существенный прирост производительности сети, узлы которой поддерживают несколько интерфейсов.
Компания Tropos Networks также представила свое решение в области маршрутизации в mesh-сетях. Яркий пример внедрения ее разработок – сеть Google WiFi, объединяющая свыше 400 маршрутизаторов в опорной сети, охватывающая более 12 квадратных миль и 15 тыс. домов для обслуживания 25 тыс. пользователей. Данного результата удалось достичь благодаря разработке и использованию протокола Predictive Wireless Routing Protocol (PWRP), способного работать в больших сетях без потери пропускной способности. PWRP является закрытым проприетарным протоколом, поэтому точных данных о его работе нет. Однако из официальных документов разработчика следует, что данный протокол – полностью распределенный и в первую очередь ориентирован на обеспечение связи клиент-сервер, которая динамически оптимизируется и с легкостью масштабируется при расширении сети. Про метрику, используемую в протоколе, известно лишь то, что она основана на измерении действительной производительности беспроводной сети.
Группа OLPC team (известный проект One Laptop per Child – каждому ребенку по лаптопу) предложила упрощенную версию протокола HWMP. Неоспоримые преимущества этого решения – открытость проекта и исходных кодов и его поддержка крупными компаниями.
Специально для mesh-сетей в Голландском институте беспроводной и мобильной связи (Twente Institute for Wireless and Mobile Communications) разработан протокол Forwarding LAyer for MEshing (FLAME). Он работает на виртуальном втором с половиной уровне модели OSI, аналогично протоколу LQSR. Это наделяет FLAME теми же преимуществами, что и LQSR, т.е. прозрачностью с точки зрения протоколов верхних уровней и независимостью от среды передачи данных. Однако в отличие от LQSR протокол FLAME не использует никаких метрик (первый пришедший от узла пакет считается пришедшим по кратчайшему пути, который и используется в дальнейшем), – любой полученный пакет является основанием для обновления информации о его источнике. При этом в таблицу маршрутизации заносится интерфейс и соседний узел, через которые пролегает путь к источнику пакета. Для этого в сети под управлением FLAME ко всем передаваемым пакетам добавляется FLAME-заголовок.
В отечественном аппаратно-программном комплексе mesh-сетей, разработанном коллективом под руководством профессора В.М.Вишневского на базе серийно выпускаемого комплекса РЭС "Рапира" [14], в качестве базового протокола маршрутизации используется HWMP. Кроме того, в ИППИ РАН разработан оригинальный протокол маршрутизации, обеспечивающий полностью прозрачный переход между проводной сетью и беспроводной mesh-сетью. Разработанный в ИППИ РАН протокол, так же как и протоколы FLAME и LQSR, использует виртуальный "2,5 уровень" модели OSI, однако в остальном его алгоритмы отличаются от FLAME и LQSR. В состав комплекса также входит специальная программа – контроллер сети, – которая занимается мониторингом беспроводной сети, а также обеспечивает удобство конфигурирования сети. Эта программа совмещает в себе функции ряда вспомогательных сервисов, таких как NTP- и DHCP-серверы, а также функции сервера безопасности сети. Разработанный отечественный аппаратно-программный комплекс беспроводных mesh-сетей будет широко использован при построении распределенных беспроводных городских сетей (как альтернатива WiMAX), в промышленных сенсорных сетях и в других областях.
Литература
1. Вишневский В., Лаконцев Д., Сафонов А., Шпилев С. Mesh-сети: в ожидании стандарта IEEE 802.11s. –
ЭЛЕКТРОНИКА: НТБ, 2008, №3, с.98–106.
2. IEEE P802.11s/D1.08. Amendment: Mesh Networking. – IEEE, January 2008.
3. Perkins C., Belding-Royer E., Das S. Ad hoc On-Demand Distance Vector (AODV) Routing. – IETF RFC 3561, July 2003.
4. IEEE P802.11s/D1.00. Amendment: Mesh Networking. – IEEE, November 2006.
5. IEEE P802.11s/ D1.06. Amendment: Mesh Networking. – IEEE, July 2007.
6. Clausen T., Jacquet P. Optimized Link State Routing Protocol (OLSR). – IETF RFC 3626, October 2003.
7. Qayyum, Laouiti A., Viennot L. Multipoint relaying technique for flooding broad-cast messages in mobile wireless networks. – HICSS: Hawai Int. Conference on System Sciences, January 2002.
8. IEEE P802.11s/D1.07. Amendment: Mesh Networking. – IEEE, September 2007.
9. Reconsidering RA-OLSR – IEEE P802.11-07.2547r2, Sept. 2007.
10. September 2007 Mesh Meeting Agenda. –
IEEE P802.11-07.2290r11, September 2007.
11. Vishnevsky V.M., Gorodov P.V., Shpilev S.A. Performance analisys of RA-OLSR in IEEE 802.11s mesh networks. – International Workshop. Proc. Of Distributed Computer and Communication Networks (DCCN-2007), 2007, Vol. 1.
12. Шпилев С.А. Проактивная маршрутизация в IEEE 802.11s mesh-сетях. – Третья всероссийская молодежная научная конференция по проблемам управления (ВМКПУ-2008), 2008.
13. Schriber T.J. Simulation using GPSS. – John Wiley & Sons, 1974.
14. Вишневский В., Гузаков Н., Лаконцев Д. Система "Рапира" – базис для отечественных широкополосных беспроводных сетей. – ЭЛЕКТРОНИКА: НТБ, 2005, № 1, с.30–34.
Для выбора оптимальных маршрутов в сети используются различные критерии (метрики). Метрики могут включать в себя такую информацию, как длина пути (количество шагов), надежность, задержка, пропускная способность, загрузка, стоимость передачи трафика и так далее. Наиболее распространенной метрикой является длина пути. Некоторые протоколы маршрутизации позволяют администратору сети присвоить каналу (путь длиной в один шаг) произвольную длину. При этом длина пути – это сумма длин каналов, через которые пролегает путь от источника (отправителя) к адресату (получателю). Другие протоколы определяют число шагов – сколько сетевых устройств (например, маршрутизаторов) должен пройти пакет на своем пути к получателю.
Еще один критерий выбора оптимальных маршрутов – надежность. Под метрикой "надежность" обычно подразумевается доля потерь пакетов в каждом из каналов. Некоторые каналы разрываются чаще, чем другие. Или восстанавливаются проще и быстрее после ошибки в работе сети. Любые факторы надежности могут учитываться при получении численного значения данной метрики.
Другая популярная метрика – задержка, т.е. время, необходимое для доставки пакета от отправителя к получателю. Задержка зависит от многих факторов, включая пропускную способность каналов, очереди в портах устройств на пути пакета, загрузку сети во всех промежуточных каналах, а также физическое расстояние, которое нужно преодолеть. Поскольку задержка зависит от ряда важных факторов, это распространенная и полезная метрика.
Пропускная способность также часто используется как критерий выбора пути. Под ней подразумевается объем данных, который может быть передан по сети в единицу времени.
Метрика, напрямую связанная с пропускной способностью, – это загрузка, которая отражает степень занятости сетевых ресурсов, таких как каналы и маршрутизаторы. Загрузку можно вычислить различными способами, включая загрузку процессора и число обрабатываемых или передаваемых в секунду пакетов. Следует отметить, что постоянный анализ этих показателей сам по себе может потребовать значительных ресурсов сетевого оборудования.
Существенно отличается от перечисленных выше критериев метрика "стоимость". Некоторые компании в целях экономии предпочитают использовать пути через собственные каналы, а не через более высокопроизводительные, но платные, каналы других операторов.
Метрика отдельных каналов может быть статической (задаваемой администратором сети) и динамической. Пример первой – метрика стоимости. Динамическая метрика может измеряться по уровню сигнала, задержке пакетов и множеству других параметров. Причем она может определяться как пассивно, без дополнительных служебных пакетов, так и использовать специальные "пробные" пакеты для сбора статистики по каждому каналу (задержки, потери и пр.).
Стандарт IEEE 802.11s* требует, чтобы все устройства поддерживали метрику времени передачи в канале (Airtime Link Metric). Эта обязательная метрика необходима для совместимости устройств. Она задается формулой
ca = (O + Bt / r) / (1 - ef), где O и Bt – константы, определенные стандартом для различных физических реализаций (802.11a, 802.11b): Bt – число битов в тестовом пакете (8192), O – накладные расходы доступа к каналу, которые включают в себя заголовки пакетов, кадры протоколов доступа и т.д.; r – скорость передачи данных в канале (Мбит/с); ef – вероятность возникновения ошибки (измеряется экспериментально на пакетах длиной Bt). Эта метрика представляет собой оценку времени передачи (в секундах) пробного пакета длиной Bt с учетом возможных ретрансляций при потерях в канале. Способ определения параметров r и ef в стандарте не приводится, однако можно предположить, что для этого должна использоваться периодическая рассылка пробных пакетов длиной Bt = 8192 бит.
В основе метода выбора пути для передачи данных в стандарте IEEE 802.11s лежит механизм профилей. Этот механизм обеспечивает совместимость устройств от разных производителей, которые могут поддерживать как стандартизованные механизмы, так и собственные. Профиль – это запись вида <Идентификатор профиля><Идентификатор протокола маршрутизации><Идентификатор метрики протокола маршрутизации>. Устройство может поддерживать несколько профилей работы, но единовременно лишь один из них может быть активным. Обязательный для реализации профиль использует протокол HWMP и метрику времени передачи Airtime Link Metric.
Производители вольны реализовать собственные алгоритмы маршрутизации и метрики к ним, а также и определять дополнительные проприетарные профили. Поэтому вопрос эффективности механизмов маршрутизации и метрик является одним из важнейших для разработчиков mesh-устройств.
Гибридный беспроводной mesh-протокол маршрутизации (HWMP)
Гибридный протокол маршрутизации HWMP (Hybrid Wireless Mesh Protocol) использует стандартный набор служебных пакетов, правил их создания и обработки, наподобие хорошо известного протокола дистанционно-векторной маршрутизации по запросу (Ad Hoc On Demand Distance Vector, AODV) [3]. Однако HWMP адаптирован для работы с адресами MAC-уровня и метриками путей. Гибридным он назван потому, что объединяет в себе два режима построения путей, которые могут быть использованы как по отдельности, так и одновременно в одной сети:
* реактивный режим – построение маршрутных таблиц в узлах mesh-сети непосредственно перед передачей данных (по запросу);
* проактивный режим – регулярная процедура обновления информации в маршрутных таблицах узлов всей сети. Процедуру инициирует корневой узел, в результате на сети строится граф (дерево) путей с вершиной в корневом узле.
В реактивном режиме HWMP узел отправляет широковещательный PREQ-пакет запроса пути (Path Request). Пути выбираются на основании метрики, для распространения информации о которой служит специальное поле в служебных пакетах запроса пути. Этот пакет распространяется через соседние узлы по всей сети, пока не достигнут узел-адресат. По мере продвижения от узла к узлу модифицируется поле метрики пути от текущего узла до отправителя. В итоге формируется полная метрика пути "получатель-отправитель". Узел-адресат отправляет инициатору пакет подтверждения PREP (Path Reply), содержащий итоговое значение метрики пути "инициатор-получатель". Приняв его, узел-инициатор получает информацию об установленном пути.
Очевидно, что в mesh-сети широковещательные пакеты запроса доходят до получателя по множеству путей через различные узлы. При этом они могут начать передаваться по замкнутым маршрутам (циклам), не единожды проходя через какой-либо узел. Чтобы избежать такой ситуации, используется порядковый номер запроса. В стандарте IEEE 802.11s он именуется порядковым номером назначения (Destination Sequence Number, DSN), что вносит невероятную путаницу. Кроме DSN, стандарт оперирует понятием DSN инициатора (поиска пути) – Originator's DSN (OSN). Именно этот параметр и служит порядковым номером при рассылке пакетов поиска пути. Каждое mesh-устройство имеет собственный DSN. Перед началом процедуры поиска пути DSN инициатора увеличивается на 1 и записывается в поле Originator's DSN пакета запроса PREQ. Кроме того, в пакете содержится адрес инициатора (адрес начала пути). Все узлы mesh-сети хранят информацию о каждом узле mesh-сети, обновляя ее на основании полученных служебных пакетов. Такая информация в данных пакетах передается в полях "адрес отправителя", "метрика пути", "порядковый номер".
Узел, получив пакет PREQ, сравнивает значение OSN с ранее сохраненным значением для этого же отправителя (если таковое имеется). Устройство принимает, обрабатывает и ретранслирует пакет PREQ, только если текущий OSN в пакете больше ранее сохраненного или они равны, но метрика пути ранее полученного пакета хуже, чем у вновь полученного (т.е. повторного приема и ретрансляции одного и того же пакета быть не может). В реактивном режиме пакеты подтверждения PREP может отправлять не только узел назначения, но и все промежуточные узлы, успешно принявшие пакет запроса PREQ (если в пакете установлены соответствующие флаги).
Помимо полей метрики пути, по мере прохождения от узла к узлу в пакете может изменяться значение поля "время жизни" (Time to Live, TTL) – число промежуточных узлов, которые разрешено пройти данному пакету. Если этот параметр используется, он декрементируется в каждом узле следования. Когда TTL = 0, обработка и трансляция пакета прекращается.
Проактивный режим отличается от реактивного тем, что в сети назначается корневой узел (узлы). Этот узел периодически рассылает пакеты PREQ, которые распространяются по всей сети. Все узлы сети, принявшие проактивный PREQ, сохраняют адрес узла-отправителя (через который лежит путь к корневому узлу), широковещательно транслируют PREQ с измененными полями (поля метрики и TTL) и отправляют PREP корневому узлу (либо не отправляют, в зависимости от установок).
Помимо описанных методов выбора пути на основе пакетов PREQ/PREP стандарт предусматривает процедуру на основе пакетов оповещения о корневом узле RANN (Root Announcement). Но этот метод принципиально не отличается от уже рассмотренного.
Возможны ситуации одновременного использования реактивного и проактивного режимов HWMP. Например, в сети штатно используется проактивный режим протокола HWMP, но какой-либо узел использует метод выбора пути по запросу для установления прямого соединения с другим заданным узлом.
Протокол маршрутизации HWMP обязателен для всех устройств стандарта IEEE 802.11s как протокол по умолчанию.
Оптимизированный протокол состояния канала для беспроводной сети (RA-OLSR)
Помимо протокола маршрутизации HWMP ранние версии IEEE 802.11s [4, 5] предполагали использование стандарта RA-OLSR (Radio Aware OLSR) – модификации оптимизированного протокола маршрутизации по состоянию канала OLSR (Optimized Link State Routing). OLSR – это описанный в документе IETF RFC 3626 [6] проактивный протокол маршрутизации для мобильных ad hoc сетей. Он поддерживает маршрутные таблицы в узлах сети при помощи регулярных процедур обновления маршрутной информации в сети. Протокол эффективен для больших и плотных мобильных сетей.
OLSR основан на понятии многоточечной эстафеты MPR (MultiPoint Relay). Каждый узел сети m выбирает несколько узлов из числа своих соседей (т.е. из узлов, с которыми у него установлено соединение). В итоге в сети формируется набор узлов MPR(m). Причем он формируется так, что все узлы, находящиеся в сфере с радиусом 2 шага от узла m (соседи соседей), имеют симметричные каналы с MPR(m). Это означает, что узлы MPR связаны со всеми узлами в сфере с радиусом 2 шага. MPR выбираются каждый раз, когда обнаруживается изменение в сфере с радиусом 1 или 2.
Каждый узел сети хранит свою таблицу маршрутизации, которую формирует на основании информации о топологии сети. Она распространяется по всей сети посредством служебных пакетов выбора маршрута Topology Control (TC). Причем только MPR-узлы участвуют в пересылке ТС-пакетов, остальные узлы принимают и обрабатывают такие пакеты, но не пересылают их дальше.
Для каждого MPR формируется список соседних узлов, выбравших его в качестве MPR, – список MPR Selectors (MPRS). Информация о MPRS передается в специальных HELLO-пакетах, которые передаются только между двумя соседними узлами. В сеть (в ТС-пакетах) передается только информация о состоянии соединений между MPR и его MPRSs. Данный механизм позволяет существенно снизить число передач служебных пакетов по сравнению с лавинной рассылкой [6, 7].
В протоколе OLSR служебные сообщения содержат последовательные номера (аналог DSN в HWMP), которые увеличиваются в последующих сообщениях. Таким образом, получатель контрольного сообщения может при необходимости с легкостью определить, какая информация является более новой, даже если сообщения пришли в обратном порядке.
OLSR разработан как совершенно распределенный протокол, он не зависит от каких-либо корневых узлов. Кроме того, каждый узел шлет контрольные пакеты периодически, поэтому протокол устойчив в случае потери части этих сообщений, что довольно часто случается с широковещательными пакетами в беспроводных сетях.
Протокол RA-OLSR детально описан в [5] и практически совпадает с оригинальным OLSR [6]. По сравнению с протоколом OLSR, модификация RA-OLSR сводится к управлению энергопотреблением. В ней также не фиксируется процедура выбора узлов MPR, ее может задавать производитель устройства. Протокол RA-OLSR присутствовал в ранних вариантах стандарта как опциональный, однако с версии D1.07 [8] от него отказались. Поводом для этого послужил тот факт, что RA-OLSR дублирует функциональность HWMP, являющегося и про- и реактивным протоколом, а стандарт допускает применение любых других протоколов маршрутизации [9]. Кроме того, RA-OLSR вызвал множество замечаний, в основном указывающих на неточности его описания в тексте стандарта. Также чрезмерным оказался размер самого описания этого протокола (48 из 246 страниц документа IEEE 802.11s были посвящены RA-OLSR) [9, 10]. Таким образом, отказ от RA-OLSR не связан с его недостатками [11, 12], рабочая группа просто решила оставить вопрос выбора альтернативного механизма маршрутизации производителям оборудования.
Сравнительный анализ протоколов маршрутизации
Мы провели анализ эффективности протоколов маршрутизации достаточно сложной сети (см. рисунок) посредством компьютерного моделирования на языке GPSS World (General Purpose Simulation System) [13]. Рассматривалась сеть без шумов, работающая по протоколу IEEE 802.11a с дополнением IEEE 802.11s на скорости 54 Мбит/с. Практически все потоки данных в этой модели направляются от конечных узлов (1–20) в Интернет через шлюзы (узлы 41–42), в обратном направлении передается примерно 2% от общего числа пакетов.
Для оценки производительности протоколов маршрутизации сравнивались пропускная способность, средние длины путей (в шагах) от конечных узлов до ближайшего шлюза (табл.1) и другие параметры. На рисунке видны кратчайшие пути от узлов до шлюзов: три шага для узлов 1–20, два шага для узлов 21–34 и один шаг для узлов 35–40.
Видно, что в случае HWMP пути становятся в 1,5 раза длиннее, а это, в свою очередь, сильно сказывается на остальных параметрах сети. Так, пропускная способность сети тоже снижается практически в 1,5 раза по сравнению с RA-OLSR. Число посылок пакетов данных в сети на каждый доставленный пакет возрастает на 10%, а время доставки пакетов – на 20%. Это объясняется тем, что с ростом длины путей увеличивается число коллизий, а с ними – и число повторных посылок.
Однако в приведенном эксперименте, кроме метода маршрутизации, сыграл свою роль и недостаток метода измерения метрики времени передачи, предложенной в стандарте IEEE 802.11s. Для измерения метрики использовалась групповая отправка пробных пакетов, которая увеличивала загрузку сети, а полученная таким образом метрика случайным образом менялась от измерения к измерению, что влекло выбор неоптимальных маршрутов.
Чтобы выяснить характеристики именно метода маршрутизации, аналогичный эксперимент проводился с использованием простейшей метрики – количества шагов до узла (табл.2.). В этом случае алгоритм RA-OLSR выбирает практически идеальные пути, а HWMP, хотя и дает заметно лучшие результаты по сравнению с предыдущим экспериментом, тем не менее остается на 16% хуже по этому параметру. Как и в случае с предложенной в стандарте метрикой, это сильно сказывается на пропускной способности сети. Время доставки пакетов и отношение числа посылок пакетов данных к числу доставленных пакетов в случае HWMP становится даже лучше, чем для RA-OLSR. Но объясняется это лишь тем, что алгоритм RA-OLSR обеспечивает почти в 1,5 раза большую загрузку сети (пропускная способность), что существенно сказывается на данных параметрах.
Возникающие проблемы с HWMP объяснить несложно. Ведь данный протокол предельно прост и хранит минимум информации. Так, ему известен только один путь до каждого из узлов mesh-сети. Каждый вновь прибывший от данного отправителя PREQ-пакет, если его DSN больше предыдущего или метрика лучше, считается пришедшим по единственно верному пути. Если же PREQ-пакет, шедший по более короткому пути, был потерян (а для широковещательных пакетов это явление довольно частое), то путь автоматически становится длиннее, чем он есть на самом деле. В случае с RA-OLSR таких проблем не возникает, так как узлы знают всю (или почти всю) топологию сети, да и путь через узел исчезает только при многократном неполучении информации о нем.
Таким образом, хотя в стандарте и остался только один протокол маршрутизации и одна метрика, они требуют серьезной доработки. В случае, если их недостатки не будут исправлены, производителям устройств придется самим выбирать оптимальные методы маршрутизации и метрики. И очевидным кандидатом на эту роль, как видно из приведенного исследования, выступает протокол маршрутизации RA OLSR.
Реализованные протоколы маршрутизации для mesh-сетей
В связи с тем, что стандарт mesh-сетей находится в стадии доработки, многие ведущие фирмы мира предлагают свои собственные протоколы маршрутизации. Известно довольно много различных разработок, но, к сожалению, в большинстве своем они лишь поверхностно описаны разработчиками.
Так, в беспроводной платформе Cisco Aironet 1520 Series фирмы Cisco Systems используется проприетарный протокол маршрутизации Cisco's Adaptive Wireless Path Protocol (AWPP). Логика протокола скрыта, однако по косвенным данным можно предположить, что он базируются на одной из версий HWMP, работающего в проактивном режиме. Управление и мониторинг сети, т.е. функция корневого узла, реализует специальное устройство – контроллер беспроводной сети Cisco Wireless LAN Controller, компания рекомендует использовать в mesh-сетях контроллеры серии 4400.
Довольно много информации о маршрутизации в своих сетях представила корпорация Microsoft. Компания разработала реактивный протокол маршрутизации, основанный на алгоритме динамической маршрутизации источника DSR (Dynamic Source Routing). Он очередь похож на протокол Ad Hoc On Demand Distance Vector (т.е. на HWMP), с той лишь разницей, что для маршрутизации от источника до адресата используется маршрутная таблица источника, а не промежуточных узлов.
Компания Microsoft предложила и протокол маршрутизации источника по качеству канала (Link Quality Source Routing, LQSR), который является адаптацией DSR на виртуальный второй с половиной уровень эталонной сетевой модели взаимодействия открытых систем OSI. Введение промежуточного уровня предпринято компанией, чтобы сделать протокол прозрачным для более высокого уровня, но при этом обеспечить его корректную работу при переходе между проводной и беспроводной сетями. К предложенному протоколу прилагается пять различных метрик: количество шагов; время на получение ответа (Round Trip Time, RTT); время на посылку пробного пакета от источника до адресата и обратно (Packet Pair); ожидаемое время передачи (Expected Transmission Time, ETT) и взвешенное совокупное ожидаемое время передачи (Weighted Cumulative ETTs, WCETT). Помимо основного протокола LQSR, есть версия многоинтерфейсного LQSR (MR-LQSR – Multi-Radio Link Quality Source Routing), которая, согласно экспериментам, дает существенный прирост производительности сети, узлы которой поддерживают несколько интерфейсов.
Компания Tropos Networks также представила свое решение в области маршрутизации в mesh-сетях. Яркий пример внедрения ее разработок – сеть Google WiFi, объединяющая свыше 400 маршрутизаторов в опорной сети, охватывающая более 12 квадратных миль и 15 тыс. домов для обслуживания 25 тыс. пользователей. Данного результата удалось достичь благодаря разработке и использованию протокола Predictive Wireless Routing Protocol (PWRP), способного работать в больших сетях без потери пропускной способности. PWRP является закрытым проприетарным протоколом, поэтому точных данных о его работе нет. Однако из официальных документов разработчика следует, что данный протокол – полностью распределенный и в первую очередь ориентирован на обеспечение связи клиент-сервер, которая динамически оптимизируется и с легкостью масштабируется при расширении сети. Про метрику, используемую в протоколе, известно лишь то, что она основана на измерении действительной производительности беспроводной сети.
Группа OLPC team (известный проект One Laptop per Child – каждому ребенку по лаптопу) предложила упрощенную версию протокола HWMP. Неоспоримые преимущества этого решения – открытость проекта и исходных кодов и его поддержка крупными компаниями.
Специально для mesh-сетей в Голландском институте беспроводной и мобильной связи (Twente Institute for Wireless and Mobile Communications) разработан протокол Forwarding LAyer for MEshing (FLAME). Он работает на виртуальном втором с половиной уровне модели OSI, аналогично протоколу LQSR. Это наделяет FLAME теми же преимуществами, что и LQSR, т.е. прозрачностью с точки зрения протоколов верхних уровней и независимостью от среды передачи данных. Однако в отличие от LQSR протокол FLAME не использует никаких метрик (первый пришедший от узла пакет считается пришедшим по кратчайшему пути, который и используется в дальнейшем), – любой полученный пакет является основанием для обновления информации о его источнике. При этом в таблицу маршрутизации заносится интерфейс и соседний узел, через которые пролегает путь к источнику пакета. Для этого в сети под управлением FLAME ко всем передаваемым пакетам добавляется FLAME-заголовок.
В отечественном аппаратно-программном комплексе mesh-сетей, разработанном коллективом под руководством профессора В.М.Вишневского на базе серийно выпускаемого комплекса РЭС "Рапира" [14], в качестве базового протокола маршрутизации используется HWMP. Кроме того, в ИППИ РАН разработан оригинальный протокол маршрутизации, обеспечивающий полностью прозрачный переход между проводной сетью и беспроводной mesh-сетью. Разработанный в ИППИ РАН протокол, так же как и протоколы FLAME и LQSR, использует виртуальный "2,5 уровень" модели OSI, однако в остальном его алгоритмы отличаются от FLAME и LQSR. В состав комплекса также входит специальная программа – контроллер сети, – которая занимается мониторингом беспроводной сети, а также обеспечивает удобство конфигурирования сети. Эта программа совмещает в себе функции ряда вспомогательных сервисов, таких как NTP- и DHCP-серверы, а также функции сервера безопасности сети. Разработанный отечественный аппаратно-программный комплекс беспроводных mesh-сетей будет широко использован при построении распределенных беспроводных городских сетей (как альтернатива WiMAX), в промышленных сенсорных сетях и в других областях.
Литература
1. Вишневский В., Лаконцев Д., Сафонов А., Шпилев С. Mesh-сети: в ожидании стандарта IEEE 802.11s. –
ЭЛЕКТРОНИКА: НТБ, 2008, №3, с.98–106.
2. IEEE P802.11s/D1.08. Amendment: Mesh Networking. – IEEE, January 2008.
3. Perkins C., Belding-Royer E., Das S. Ad hoc On-Demand Distance Vector (AODV) Routing. – IETF RFC 3561, July 2003.
4. IEEE P802.11s/D1.00. Amendment: Mesh Networking. – IEEE, November 2006.
5. IEEE P802.11s/ D1.06. Amendment: Mesh Networking. – IEEE, July 2007.
6. Clausen T., Jacquet P. Optimized Link State Routing Protocol (OLSR). – IETF RFC 3626, October 2003.
7. Qayyum, Laouiti A., Viennot L. Multipoint relaying technique for flooding broad-cast messages in mobile wireless networks. – HICSS: Hawai Int. Conference on System Sciences, January 2002.
8. IEEE P802.11s/D1.07. Amendment: Mesh Networking. – IEEE, September 2007.
9. Reconsidering RA-OLSR – IEEE P802.11-07.2547r2, Sept. 2007.
10. September 2007 Mesh Meeting Agenda. –
IEEE P802.11-07.2290r11, September 2007.
11. Vishnevsky V.M., Gorodov P.V., Shpilev S.A. Performance analisys of RA-OLSR in IEEE 802.11s mesh networks. – International Workshop. Proc. Of Distributed Computer and Communication Networks (DCCN-2007), 2007, Vol. 1.
12. Шпилев С.А. Проактивная маршрутизация в IEEE 802.11s mesh-сетях. – Третья всероссийская молодежная научная конференция по проблемам управления (ВМКПУ-2008), 2008.
13. Schriber T.J. Simulation using GPSS. – John Wiley & Sons, 1974.
14. Вишневский В., Гузаков Н., Лаконцев Д. Система "Рапира" – базис для отечественных широкополосных беспроводных сетей. – ЭЛЕКТРОНИКА: НТБ, 2005, № 1, с.30–34.
Отзывы читателей
