Перейти к содержанию

RPL (протокол маршрутизации для сетей с потерями)

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

Обновлено Редакция GAW

Содержание

RPL (IPv6 Routing Protocol for Low-Power and Lossy Networks, протокол маршрутизации для сетей с низким энергопотреблением и потерями) — протокол RFC 6550 для сетей LLN: узлы с ограниченными процессором, памятью и батареей связаны каналами с низкой скоростью и частыми потерями, а трафик течёт в основном от многих датчиков к одному шлюзу (разд. 1). Типичный нижний слой — 6LoWPAN поверх IEEE 802.15.4, где радиус радио меньше размера сети и пакет к шлюзу идёт через несколько узлов.

Дерево DODAG

Топология RPL — ориентированный ациклический граф, разбитый на DODAG (Destination-Oriented DAG): по одному дереву на каждый сток, обычно пограничный маршрутизатор (разд. 3.1.1). Четыре идентификатора задают положение узла (разд. 3.1.2):

ИдентификаторЧто обозначает
RPLInstanceIDэкземпляр RPL со своей целевой функцией; в сети их может быть несколько
DODAGIDконкретное дерево внутри экземпляра
DODAGVersionNumberверсия дерева; корень увеличивает её для глобальной перестройки (разд. 3.2.2)
Rankположение узла относительно корня

Ранг строго убывает по направлению к корню; это не стоимость пути и не метрика с единицей измерения, а абстрактное число, которое Objective Function выводит из метрик — энергии, задержки, качества канала (разд. 3.2.1, 3.5). У корня ранг равен MinHopRankIncrease (по умолчанию 256, так что целая часть ранга — 8 бит), значение 0xFFFF (INFINITE_RANK) означает «не в дереве» (разд. 17). Благодаря монотонности ранга узел не может выбрать родителем своего потомка, и петли исключаются.

Сообщения

Все управляющие сообщения RPL — один тип ICMPv6, 155, различающийся кодом (разд. 6):

  • DIS (0x00) — запрос информации о DODAG, аналог Router Solicitation из Neighbor Discovery (разд. 6.2);
  • DIO (0x01) — объявление дерева сверху вниз: параметры экземпляра, ранг отправителя; по нему узлы выбирают родителей и строят маршруты вверх (разд. 3.2, 6.3);
  • DAO (0x02) — объявление достижимых адресов снизу вверх, для маршрутов вниз (разд. 3.3, 6.4);
  • DAO-ACK (0x03) — подтверждение DAO по запросу (разд. 6.5).

Источник — link-local адрес, назначение — групповой адрес всех узлов RPL ff02::1a или link-local unicast; исключение — DAO в режиме Non-Storing, которые идут к корню через несколько переходов с глобальных адресов (разд. 6). DIO рассылаются по таймеру Trickle (RFC 6206): с минимального интервала 8 мс (DEFAULT_DIO_INTERVAL_MIN = 3) интервал удваивается до 20 раз, то есть до 2,3 ч (разд. 8.3.1, 17) — в стабильной сети служебный трафик почти исчезает. 8 мс × 2^20 ≈ 8400 с ≈ 2,3 ч (наш расчёт). Внутри интервала узел передаёт DIO в случайный момент из второй его половины и только если за интервал услышал меньше k = 10 согласованных DIO соседей (DEFAULT_DIO_REDUNDANCY_CONSTANT); при несогласованности — например, когда узел присоединился к новой версии DODAG — интервал сбрасывается к минимуму (RFC 6206 разд. 4.2, RFC 6550 разд. 8.3).

Маршруты вниз: storing и non-storing

Маршруты к корню есть всегда; маршруты от корня к узлам — только если включены DAO. Поле MOP в DIO задаёт режим (разд. 6.3.1): 0 — без маршрутов вниз, 1 — Non-Storing, 2 — Storing без multicast, 3 — Storing с multicast. В режиме Storing каждый узел хранит таблицу потомков, и пакет между двумя узлами разворачивается вниз у ближайшего общего предка. В Non-Storing таблицы хранит только корень, пакет сначала поднимается до него и спускается с маршрутом от источника в заголовке (разд. 3.3). Первый режим требует памяти на каждом узле, второй — нагружает корень и удлиняет путь; RFC отмечает, что реализации обычно поддерживают только один из них. Для прошивки датчика важно и то, что Hop Limit пакета расходуется на каждом переходе дерева. Сравнение радиотехнологий для таких сетей — в обзоре беспроводных интерфейсов.

Частые вопросы

Что такое DODAG в RPL?

Destination-Oriented Directed Acyclic Graph — ориентированный ациклический граф с одним стоком: корнем, обычно шлюзом сети. RFC 6550 (разд. 3.1.1) разбивает топологию на DODAG, по одному на каждый сток. Узел выбирает родителей среди соседей с меньшим рангом, и у каждого пакета «вверх» есть путь к корню. DODAG однозначно задаётся парой RPLInstanceID и DODAGID, а каждая перестройка от корня получает новый DODAGVersionNumber (разд. 3.1.2, 3.2.2).

Чем DIO отличается от DAO?

DIO (DODAG Information Object) рассылают сверху вниз: по нему узел узнаёт о существовании DODAG, его параметрах и рангах соседей и выбирает родителей — так строятся маршруты вверх, к корню (разд. 3.2, 6.3). DAO (Destination Advertisement Object) идёт снизу вверх и объявляет, какие адреса достижимы через узел, — так появляются маршруты вниз (разд. 3.3, 6.4). DAO необязательны: при MOP = 0 сеть умеет только собирать данные к корню.

Что такое ранг узла?

Число, выражающее положение узла относительно корня DODAG: у корня ROOT_RANK = MinHopRankIncrease, по мере удаления ранг растёт, 0xFFFF означает «вне графа» (разд. 17). Как именно считать ранг из метрик канала, решает Objective Function (разд. 3.2.1). Ранг — не стоимость пути и не имеет единицы (разд. 3.5); его единственная обязанность — строго убывать по направлению к корню, чтобы в маршрутах не было петель.

Источники

  1. IETF. T. Winter, P. Thubert, A. Brandt, J. Hui, R. Kelsey, P. Levis, K. Pister, R. Struik, JP. Vasseur, R. Alexander. RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks. RFC 6550, March 2012 — разд. 1: LLN — ограниченные узлы (процессор, память, иногда батарея), каналы с потерями и низкой скоростью, трафик в основном «многие к одному» и «один ко многим», до тысяч узлов; разд. 1.1: несколько экземпляров RPL одновременно, цель оптимизации (энергия, задержка) вынесена в Objective Function, нужны двунаправленные каналы и проверка досягаемости перед выбором родителя; разд. 3.1.1: топология — DAG, разбитый на DODAG, по одному на сток; разд. 3.1.2: идентификаторы RPLInstanceID, DODAGID, DODAGVersionNumber, Rank; разд. 3.2: маршруты вверх строятся сообщениями DIO; разд. 3.2.1: OF переводит метрики в Rank — приближённое расстояние до корня — и задаёт выбор родителей; разд. 3.2.2: глобальный ремонт — корень увеличивает DODAGVersionNumber; разд. 3.3: маршруты вниз — сообщения DAO, необязательны; режимы Storing (с таблицами) и Non-Storing (маршрутизация от источника), P2P-пакет идёт вверх до общего предка, в Non-Storing — до корня; разд. 3.5: Rank монотонно убывает к корню, не является стоимостью пути, без физической единицы; разд. 4: три потока — MP2P, P2MP, P2P; разд. 6: управляющее сообщение RPL — ICMPv6 тип 155, коды 0x00 DIS, 0x01 DIO, 0x02 DAO, 0x03 DAO-ACK; источник — link-local адрес, назначение — all-RPL-nodes ff02::1a или link-local unicast, кроме DAO/DAO-ACK в Non-Storing (unicast через несколько переходов с глобальных адресов); разд. 6.2: DIS — аналог Router Solicitation, зондирование соседей на наличие DODAG; разд. 6.3: DIO — обнаружить экземпляр, узнать параметры, выбрать родителей; разд. 6.3.1: MOP 0 — без маршрутов вниз, 1 — Non-Storing, 2 — Storing без multicast, 3 — Storing с multicast; разд. 6.4: DAO unicast родителю (Storing) или корню (Non-Storing), DAO-ACK по запросу; разд. 8.3.1: DIO рассылаются по таймеру Trickle (RFC 6206); разд. 17: ROOT_RANK = MinHopRankIncrease, DEFAULT_MIN_HOP_RANK_INCREASE = 256 (целая часть ранга — 8 бит), INFINITE_RANK = 0xFFFF, DEFAULT_DIO_INTERVAL_MIN = 3 (Imin 8 мс), DEFAULT_DIO_INTERVAL_DOUBLINGS = 20 (максимальный интервал 2,3 ч), DEFAULT_DIO_REDUNDANCY_CONSTANT = 10
  2. IETF. P. Levis, T. Clausen, J. Hui, O. Gnawali, J. Ko. The Trickle Algorithm. RFC 6206, March 2011 — разд. 4.1: три параметра — минимальный интервал Imin в единицах времени, максимальный Imax как число удвоений Imin, константа избыточности k; переменные I, t, c; разд. 4.2: шесть правил — в начале интервала c = 0, t выбирается случайно из [I/2, I); каждое «согласованное» сообщение увеличивает c; в момент t узел передаёт, только если c < k; по истечении интервала I удваивается до предела Imax; при «несогласованности» I сбрасывается к Imin; ответ не мгновенный, а в случайный момент нового интервала — чтобы не было шторма одновременных ответов
Страница помогла?

Нашли ошибку? ·

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