RFC 6552 Objective Function Zero for the Routing Protocol for Low-Power and Lossy Networks (RPL)

Опубликовано 07.03.2012 автором Nikolai Malykh 
Internet Engineering Task Force (IETF)                   P. Thubert, Ed.
Request for Comments: 6552                                 Cisco Systems
Category: Standards Track                                     March 2012
ISSN: 2070-1721

Objective Function Zero for the Routing Protocol for Low-Power and Lossy Networks (RPL)

Базовая предметная функция OF для протокола маршрутизации RPL

PDF

Аннотация

Спецификация протокола RPL1 определяет базовый протокол на основе вектора удалённости (Distance Vector), адаптированный для разных типов сетей и приложений за счёт применения специализированных предметных функций (Objective Function или OF). OF определяет результат процесса, применяемого узлом RPL для выбора и оптимизации маршрутов в рамках экземпляра RPL на основе информационных объектов. OF не является алгоритмом.

Документ задаёт базовую функцию OF, основанную на объектах, определённых в RPL, и не использующую расширений протокола.

Статус документа

Этот документ содержит проект стандарта Internet (Internet Standards Track).

Документ является результатом работы IETF и выражает согласованное мнение сообщества IETF. Документ был представлен на публичное рассмотрение и одобрен для публикации IESG. Дополнительная информация о стандартах Internet доступна в разделе 2 RFC 5741.

Информацию о текущем статусе документа, обнаруженных ошибках и способах обратной связи можно получить, воспользовавшись ссылкой http://www.rfc-editor.org/info/rfc6552.

Авторские права

Авторские права ((c) 2012) принадлежат IETF Trust и лицам, указанным в числе авторов документа. Все права защищены.

К документу применимы права и ограничения, указанные в BCP 78 и IETF Trust Legal Provisions и относящиеся к документам IETF (http://trustee.ietf.org/license-info), на момент публикации данного документа. Прочтите упомянутые документы внимательно. Фрагменты программного кода, включённые в этот документ, распространяются в соответствии с упрощённой лицензией BSD, как указано в параграфе 4.e документа IETF Trust Legal Provisions, без каких-либо гарантий (как указано в Simplified BSD License).

1. Введение

Спецификация протокола RPL [RFC6550] определяет базовый протокол на основе вектора удалённости, адаптируемый для разных типов сетей LLN2 путём использования конкретных предметных функций (OF).

RPL OF задаёт выход процесса, используемого узлом RPL для выбора и оптимизации маршрутов в экземпляре RPL на основе доступных информационных объектов. Как правило, OF не является алгоритмом. Например, за пределами RPL SPF3 является функцией OF, возвращающей путь с наименьшей стоимостью между парой точек. При этом имеется множество алгоритмов для реализации OF, например, широко известный алгоритм Dijkstra.

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

RPL создаёт ациклические направленные графы (Directed Acyclic Graph или DAG) как наборы ориентированных на адресатов DAG (Destination-Oriented DAG или DODAG) в экземплярах протокола, с каждым из которых связана предметная функция OF. Графы DODAG периодически создаются заново с новой версией DODAG для повторения глобальной оптимизации графа.

Экземпляр RPL на устройстве применяет OF для определения DODAG и версии DODAG, к которым следует присоединиться. OF также применяется экземпляром RPL для выбора числа маршрутизаторов в текущей и последующих версиях DODAG, служащих родителями или предпочтительными преемниками.

RPL Instance использует OF для расчёта ранга устройства, представляющего абстрактное расстояние от корня DODAG в DODAG Version. Значения Rank передаются между узлами, использующими RPL и позволяют другим узлам RPL избегать потерь и проверять выполнение пересылки в направлении адресата, как указано в [RFC6550]. Независимо от применяемой узлом функции OF значение Rank будет всегда возрастать и таким образом после схождения всегда формируется путь без петель.

Базовая целевая функция (Objective Function Zero или OF0) работает с параметрами, получаемыми при инициализации, в опции RPL DODAG Configuration и базовом контейнере RPL DODAG Information Object (DIO) [RFC6550].

Ранг узла получается сложением строго положительного, косвенно нормализованного скаляра rank_increase (параграф 6.1) со значением Rank выбранного предпочтительного родителя. Значение rank_increase основано на нормализованном скаляре step_of_rank (параграф 6.1), который может меняться от 1 (отлично) до 9 (наименее приемлемо) для представления свойств канала. Значение step_of_rank может умножаться на настраиваемый коэффициент rank_factor (параграф 6.2), увеличивающий rank_increase для отражения относительной предпочтительности разных типов каналов, применяемых в одном RPL Instance. Дополнительная адаптация rank_increase рассмотрена в параграфе 4.1. По умолчанию OF0 позволяет представить значения Rank от 28 (наименее приемлемо) до 255 (отлично) интервалов пересылки.

Спецификация RPL [RFC6550] требует использования всеми узлами сети одной функции OF. Вопрос использования нескольких OF требует дальнейшего изучения.

В спецификацию RPL [RFC6550] определение конкретной функции OF не включено и оставлено для других документов, относящихся к конкретному развёртыванию с прикладной среде. Поскольку в базовой спецификации RPL не задано принятой по умолчанию функции OF или контейнера метрики, может случиться так, что две реализации, не следующие общим рекомендациям для конкретной задачи или среды, не будут поддерживать общую функцию OF, которая позволила бы им взаимодействовать.

Функция OF0 разработана в качестве применяемой по умолчанию OF, позволяющей взаимодействовать реализациям в разных вариантах применения. Поэтому OF0 не задаёт преобразование свойств канала в rank_increase и оставляет решение этой задачи за реализацией. OF0 принудительно устанавливает значения rank_increase путём нормализации step_of_rank для обычного канала и задания допустимого диапазона вместо указания деталей расчёта step_of_rank. По этой же причине OF0 игнорирует контейнеры метрики.

2. Терминология

Используемая в документе терминология соответствует документу «Terminology in Low power And Lossy Networks» [ROLL-TERMS] и [RFC6550].

Термин «возможный преемник» (feasible successor) обозначает соседа, который может служить следующим интервалом пересылки для восходящего трафика в соответствии с правилами пересылки и предотвращения петель, реализуемыми узлом и заданными спецификацией RPL [RFC6550].

Ключевые слова необходимо (MUST), недопустимо (MUST NOT), требуется (REQUIRED), нужно (SHALL), не нужно (SHALL NOT), следует (SHOULD), не следует (SHOULD NOT), рекомендуется (RECOMMENDED), возможно (MAY), необязательно (OPTIONAL) в данном документе должны интерпретироваться в соответствии с RFC 2119 [RFC2119].

3. Обзор функции OF0

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

Цель OF0 состоит в присоединении узла версии DODAG, предоставляющей достаточно хорошую связность с конкретным набором узлов или более крупной инфраструктурой маршрутизации, хотя нет гарантии, что путь будет оптимизирован в соответствии с конкретной метрикой. Процесс проверки связности зависит от реализации и типа канала и выходит за рамки документа. Проверка включает применение параграфа 3.2.3 и раздела 13 [RFC6550] в зависимости от ситуации и может включать специфические для реализации правила. Таким образом, для целей OF0 приземленность корня DODAG [RFC6550] означает, что он обеспечивает такую связность. Однако утверждение и поддержка этой связности выходят за рамки документа.

Функция OF0 предназначена для поиска ближайшего приземлённого корня. Этого можно достичь, если Rank узла очень близок к абстрактной функции его удалённости от корня. Эта потребность уравновешивается необходимостью поддержки некоторого разнообразия путей, что можно обеспечить повышением ранга. При отсутствии приземлённого корня связность внутри LLN по-прежнему желательна и формируются плавающие DAG с корнями в узлах с наивысшим административным предпочтением.

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

Узел RPL отслеживает каналы к ряду соседних узлов и может применять OF0 для назначения каждому каналу значения rank_increase. Хотя точный метод расчёта rank_increase зависит от реализации, должны выполняться правила, указанные в параграфе 4.1. Расчёт ранга.

4. Операции OF0

4.1. Расчёт ранга

Реализация OF0 сначала рассчитывает переменную step_of_rank (параграф 6.1), связанную с данным родителем, по соответствующим свойствам и метрике канала. Значение step_of_rank применяется для расчёта приращения ранга на конкретном канале, как описано ниже.

Расчёт step_of_rank на основе статической метике, такой как административная стоимость, предполагает, что реализация OF0 учитывает лишь родителей с достаточно хорошей связью, и даёт в результате значение Rank аналогичное hop-count. В большинстве сетей LLN это отдаёт предпочтение путям с меньшим числом более длинных интервалов пересылки в случаях плохой связи. Таким образом, рекомендуется основывать расчёт step_of_rank на динамических свойствах каналов, таких как ожидаемое число передач (ETX), введённое в [DeCouto03] и рассмотренное в [RFC6551]. В работе «Minimum Rank Objective Function with Hysteresis» [HYSTERESIS] даны рекомендации по расчёту стоимости каналов и повышению стабильности ранга за счёт гистерезиса.

OF0 позволяет реализации «растянуть» step_of_rank для обеспечения возможности выбора хотя бы одного возможного преемника и, таким образом, поддержки разнесения путей. Растягивание step_of_rank не рекомендуется, поскольку оно увеличивает видимое расстояние от узла до корня, искажает граф DODAG и может вызывать нестабильность из-за «жадности» узлов увеличивающих в цикле свой ранг для использования каждого другого узла как родителя. Тем не менее, реализация может «растягивать» step_of_rank с помощью настраиваемого параметра stretch_of_rank (параграф 6.2), принимающего значение от 0 (без растягивания) до константы MAXIMUM_RANK_STRETCH (параграф 6.3).

Реализация должна поддерживать растяжение step_of_rank в диапазоне от MINIMUM_STEP_OF_RANK до MAXIMUM_STEP_OF_RANK (параграф 6.3), что позволяет учесть широкий диапазон качества каналов.

Интервал MINIMUM_STEP_OF_RANK – MAXIMUM_RANK_STRETCH может оказаться недостаточным для всех случаев при сильно различающихся каналах разных типов и категорий, чтобы предпочесть, например, каналы с питанием от сеть по отношению к батарейным или высокоскоростные (кабельные) каналы по отношению к низкоскоростным (беспроводным) в одном DAG. реализации следует разрешать оператору настройку коэффициента rank_factor (параграф 6.2) и применять его для всех каналов и партнёров с целью усиления влияния растянутого step_of_rank при расчёте rank_increase, как описано ниже.

В дополнение реализация может распознавать категории партнёров и каналов, такие как разные типы каналов, и в этом случае следует обеспечивать возможность дополнительной настройки коэффициента rank_factor для таких категорий. Значение rank_factor должно лежать в диапазоне MINIMUM_RANK_FACTOR – MAXIMUM_RANK_FACTOR (параграф 6.3).

Переменная rank_increase указывается в единицах, заданных переменной MinHopRankIncrease, которая по умолчанию имеет значение DEFAULT_MIN_HOP_RANK_INCREASE ([RFC6550]), при такой установке младший октет поля RPL Rank в DIO Base Object не используется.

Значение step_of_rank Sp, рассчитанное для данного канала, умножается на rank_factor Rf и может растягиваться в Sr раз (не более stretch_of_rank). Полученное значение rank_increase добавляется к рангу предпочтительного родителя R(P) для получения ранга данного узла, при этом rank_increase рассчитывается как

   rank_increase = (Rf*Sp + Sr) * MinHopRankIncrease

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

4.2. Выбор родителей

4.2.1. Выбор предпочтительного родителя

При сканировании кандидатов в соседи OF0 сохраняет родителей, которые являются лучшими в соответствии с приведёнными ниже критериями (по порядку).

  1. В разделе 8 [RFC6550] указаны общие правила для узлов при повторном выборе родителя и, в частности, границы роста Rank в рамках DODAG Version. Кандидатов, не соответствующих этим правилам, рассматривать недопустимо.

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

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

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

  4. Если задано административное предпочтение корня для замены цели присоединения к Grounded DODAG, следует предпочитать маршрутизатор подключение к более предпочтительному корню.

  5. Следует предпочитать маршрутизатор, предлагающий соединение с приземлённой версией DODAG.

  6. Следует предпочитать маршрутизатор, предлагающий соединение с более предпочтительным корнем.

  7. При сравнении двух родителей из одного DODAG следует предпочитать маршрутизатор, обеспечивающий связь с более новой версией DODAG.

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

  9. Следует предпочитать версию DODAG, для которой имеется дополнительный родитель. Эта проверка необязательна и выполняется путём вычисления резервного возможного преемника в предположении, что используемый в настоящее время маршрутизатор окончательно выбран предпочтительным родителем.

  10. Следует предпочитать родителя, который уже был предпочтительным.

  11. Следует предпочитать маршрутизатор, анонсировавший более свежее сообщение DIO.

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

4.2.2. Выбор резервного преемника

При выборе резервного возможного преемника OF выполняет проверки в указанном ниже порядке.

  1. Резервному преемнику недопустимо быть предпочтительным родителем.

  2. Резервный преемник должен быть в той же или последующей версии DODAG, что и данный узел.

  3. Наряду с правилами RPL недопустимо выбирать маршрутизатор с той же версией DODAG, как у данного узла, и рангом выше Rank, рассчитанного для данного узла.

  4. Следует предпочитать маршрутизатор с меньшим рангом.

  5. Следует предпочитать маршрутизатор, проверенный на пригодность зависимым от реализации процессом.

  6. При доступности нескольких интерфейсов предпочтительней выбирать маршрутизатор с интерфейсом, имеющим более высокий приоритет.

  7. Следует предпочитать резервный преемник, который уже был предпочтительным.

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

5. Абстрактный интерфейс OF0

Функция OF0 взаимодействует с операциями и системой управления, как показано ниже.

Обработка DIO

При получении нового сообщения DIO функция OF, соответствующая коду цели (Objective Code Point или OCP) в the DIO вызывается с содержимым DIO. OF0 идентифицируется OCP 0 (8. Взаимодействие с IANA).

Предоставление информации DAG

Поддержка OF0 обеспечивает интерфейс, возвращающий информацию о данном экземпляре. Это включает сведения из базового заголовка DIO, роль (маршрутизатор, лист) и Rank данного узла.

Предоставление списка родителей

Поддержка OF0 обеспечивает интерфейс, возвращающий упорядоченный список родителей и возможных преемников для данного экземпляра ядру RPL. Это включает сведения из опции TIO для каждой записи.

Триггерные обновления

Поддержка OF0 обеспечивает события для информирования об изменении в DAG information или Parent List. Это может быть вызвано взаимодействием с другими компонентами системы, такими как настройка конфигурации, таймеры, драйверы устройств, и эти изменения могут приводить к созданию ядром RPL нового сообщения DIO или сбросу таймеров Trickle.

6. Операнды OF0

В дополнение к переменным и константам [RFC6550] данная спецификация определяет ряд переменных и констант.

6.1. Переменные

step_of_rank

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

rank_increase (strictly positive integer)

Положительное целочисленное значение приращения ранга относительно предпочтительного родителя.

6.2. Настраиваемые параметры

OF0 может использовать приведённые ниже настраиваемые значения в качестве параметров расчёта rank_increase.

stretch_of_rank

Целое число без знака, задающее максимальное увеличение step_of_rank для предпочтительного родителя, чтобы обеспечить возможность выбора дополнительного вероятного преемника. По умолчанию step_of_rank не растягивается.

rank_factor

Положительное целое число (настраиваемое), используемое для умножения свойств канала при расчёте rank_increase. По умолчанию используется rank_factor = 1.

6.3. Константы

В разделе 17 [RFC6550] определены константы RPL. OF0 использует несколько дополнительных констант:

DEFAULT_STEP_OF_RANK = 3;

MINIMUM_STEP_OF_RANK = 1;

MAXIMUM_STEP_OF_RANK = 9;

DEFAULT_RANK_STRETCH = 0;

MAXIMUM_RANK_STRETCH = 5;

DEFAULT_RANK_FACTOR = 1;

MINIMUM_RANK_FACTOR = 1;

MAXIMUM_RANK_FACTOR = 4.

7. Вопросы управляемости

В разделе 18 [RFC6550] описано управление протоколом. Данная спецификация наследует этот раздел за исключением того, что заданная в [RFC6551] метрика не применяется и не требует управления.

7.1. Конфигурация устройства

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

Реализация может разрешать настройку максимального значения stretch_of_rank, которое должно быть не больше MAXIMUM_RANK_STRETCH, как отмечено в параграфе 4.1. По умолчанию принято значение 0 и step_of_rank не растягивается.

Реализации OF0 следует поддерживать опцию DODAG Configuration, как описано в параграфе 6.7.6 [RFC6550] и применять содержащиеся в опции параметры. Как отмечено в разделе 16 [RFC6550], это требование может быть переопределено дополнительными рекомендациями для некоторых вариантов развёртывания. При использовании опции параметры настраиваются для узлов, которые могут стать корнями DODAG, а узлы настраиваются на распространение информации с использованием опции DODAG Configuration. В частности, в этой опции может распространяться значение MinHopRankIncrease для переопределения заданной в разделе 17 [RFC6550] константы DEFAULT_MIN_HOP_RANK_INCREASE = 256.

На момент выпуска с производства следует использовать принятые по молчанию значения констант:

  • rank_factor = DEFAULT_RANK_FACTOR (параграф 6.3).

  • максимальное значение stretch_of_rank = DEFAULT_RANK_STRETCH (параграф 6.3).

  • MinHopRankIncrease = DEFAULT_MIN_HOP_RANK_INCREASE ([RFC6550]).

Значения могут быть переопределены в любой момент и применены в следующей версии DODAG. Как указано в разделе 16 [RFC6550], это требование может быть изменено дополнительными рекомендациями для конкретного развёртывания.

7.2. Мониторинг устройств

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

  • Информация DAG, указанная в параграфе 6.3.1 [RFC6550] и включающая DODAGID, RPLInstanceID, MOP, Rank данного узла, текущее значение Version Number и значение флага Grounded.

  • Список соседей с указанием предпочтительного родителя и возможного преемника (при наличии). Для каждого соседа следует указывать Rank, текущее значение Version Number и значение флага Grounded.

8. Взаимодействие с IANA

В соответствии с этой спецификацией выделен код OCP (Objective Code Point) для функции OF0 в реестре Objective Code Point, как указано в параграфе 20.5 [RFC6550].

Код OCP

0

Описание

Базовая предметная функция OF, основанная лишь на объектах, определённых в [RFC6550].

RFC с определением

RFC 6552

9. Вопросы безопасности

Эта спецификация добавляет простые расширения RPL, поэтому для неё сохраняются уязвимости и проблемы безопасности, описанные в [RFC6550] и [ROLL-SECURITY]. Этот документ не добавляет потоков или сообщений, поэтому не требуется дополнительного смягчения угроз.

OF0 зависит от обмена информацией в протокольных элементах Rank и OCP. Если эти элементы скомпрометированы, реализация OF0 может генерировать ложные пути для пакетов, приводящие к ошибочной маршрутизации. Поэтому реализациям рекомендуется применять механизмы защиты RPL при наличии риска изменения или подделки маршрутной информации.

10. Благодарности

Спасибо Philip Levis и Phoebus Chen за помощь в доработке документа.

Большое спасибо также Adrian Farrel, Tim Winter, JP. Vasseur, Julien Abeille, Mathilde Durvy, Teco Boot, Navneet Agarwal, Meral Shirazipour, Henning Rogge за глубокий анализ и отзывы от разработчиков.

11. Литература

11.1. Нормативные документы

[RFC2119] Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels”, BCP 14, RFC 2119, March 1997.

[RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, JP., and R. Alexander, “RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks”, RFC 6550, March 2012.

11.2. Дополнительная литература

[DeCouto03] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, “A High-Throughput Path Metric for Multi-Hop Wireless Routing”, MobiCom ’03, The 9th ACM International Conference on Mobile Computing and Networking, San Diego, California, 2003, <http://pdos.csail.mit.edu/papers/grid:mobicom03/paper.pdf>.

[HYSTERESIS] Gnawali, O. and P. Levis, “The Minimum Rank Objective Function with Hysteresis”, Work in Progress4, May 2011.

[RFC6551] Vasseur, J., Ed., Kim, M., Ed., Pister, K., Dejean, N., and D. Barthel, “Routing Metrics Used for Path Calculation in Low-Power and Lossy Networks”, RFC 6551, March 2012.

[ROLL-SECURITY] Tsao, T., Alexander, R., Dohler, M., Daza, V., and A. Lozano, “A Security Framework for Routing over Low Power and Lossy Networks”, Work in Progress5, March 2012.

[ROLL-TERMS] Vasseur, JP., “Terminology in Low power And Lossy Networks”, Work in Progress6, September 2011.

Адрес автора

Pascal Thubert (editor)

Cisco Systems

Village d’Entreprises Green Side

400, Avenue de Roumanille

Batiment T3

Biot – Sophia Antipolis 06410

FRANCE

Phone: +33 497 23 26 34

EMail: pthubert@cisco.com



Перевод на русский язык


Николай Малых


nmalykh@protokols.ru




1Routing Protocol for Low-Power and Lossy Networks – протокол маршрутизации для сетей с низким питанием и потерями.






2Low-Power and Lossy Network – сеть с ограниченным питанием и потерями.






3Shortest path first – сначала кратчайший путь.






4Работа опубликована в RFC 6719. Прим. перев.






5Работа опубликована в RFC 7416. Прим. перев.






6Работа опубликована в RFC 7102. Прим. перев.



 											


		
						

							Запись опубликована в рубрике RFC. Добавьте в закладки постоянную ссылку.													

					


					

					
			




	

		
Добавить комментарий