RFC 6552

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

📅 published March 2012, from ietf

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

RFC 6552 💖 by P. Thubert, Ed. from Cisco Systems, published March 2012 as a Standards Track document (ISSN 2070-1721). It's written under the Internet Engineering Task Force (IETF). The title block doesn't list anything it obsoletes or updates, so it's a fresh standard. 🎀

Abstract ✨

okay so RPL is a generic Distance Vector protocol, and it gets adapted to all kinds of network types through Objective Functions (OFs) 🌈. An OF describes the outcome a RPL node is going for when it picks and optimizes routes inside a RPL Instance, based on the Information Objects it has available. An OF is not an algorithm, bestie 💅

This document specifies a basic Objective Function that only relies on the objects already defined in RPL. It doesn't need any protocol extensions. Simple, clean, iconic 👑

Status of This Memo 📜

This is an Internet Standards Track document.

This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It went through public review and got approved for publication by the Internet Engineering Steering Group (IESG). More info on Internet Standards is in Section 2 of RFC 5741.

If you want the current status, any errata, or a way to send feedback, check http://www.rfc-editor.org/info/rfc6552.

Copyright (c) 2012 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as they stand on the publication date. Please read these carefully, because they spell out your rights and restrictions for this document. Any Code Components pulled out of this document must include Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come without warranty, as the Simplified BSD License describes.

Table of Contents 🗺️

1. Introduction ....................................................2
2. Terminology .....................................................4
3. Objective Function Zero Overview ................................4
4. OF0 Operations ..................................................5
   4.1. Computing Rank .............................................5
   4.2. Parent Selection ...........................................7
        4.2.1. Selection of the Preferred Parent ...................7
        4.2.2. Selection of the Backup Feasible Successor ..........8
5. Abstract Interface to OF0 .......................................9
6. OF0 Operands ....................................................9
   6.1. Variables ..................................................9
   6.2. Configurable Parameters ...................................10
   6.3. Constants .................................................10
7. Manageability Considerations ...................................10
   7.1. Device Configuration ......................................11
   7.2. Device Monitoring .........................................11
8. IANA Considerations ............................................12
9. Security Considerations ........................................12
10. Acknowledgements ..............................................12
11. References ....................................................13
   11.1. Normative References .....................................13
   11.2. Informative References ...................................13

1. Introduction 🌸

RPL is defined in [RFC6550], and it's a generic Distance Vector protocol. It gets adapted to a bunch of Low-Power and Lossy Network (LLN) types through specific Objective Functions (OFs) ✨

A RPL OF describes the outcome a RPL node is aiming for when it picks and optimizes routes within a RPL Instance, based on the Information Objects it has. As a general idea, an OF is not an algorithm. Outside of RPL, for example, "shortest path first" is an OF, where the least cost path between two points is the result. There are plenty of algorithms that can satisfy that OF, and the well-known Dijkstra algorithm is one of them 🧚

Keeping OFs separate from the core protocol spec is the whole point. It lets RPL fit the different optimization criteria that come with all the deployments, applications, and network designs out there. Main character energy 💅

RPL builds Directed Acyclic Graphs (DAGs) as collections of Destination-Oriented DAGs (DODAGs) inside protocol instances. Each instance is tied to a specialized Objective Function. A DODAG gets periodically rebuilt as a new DODAG Version, which lets the whole graph be globally reoptimized 🔥

A RPL instance on a device uses an Objective Function to figure out which DODAG, and which Version of that DODAG, it should join. The OF also helps the RPL Instance pick a number of routers within the current and subsequent DODAG Versions to act as parents or feasible successors 🦋

The RPL Instance uses the OF to compute a Rank for the device. The Rank is an abstract distance to the root of the DODAG within the DODAG Version. Nodes swap Ranks through RPL, and that lets them avoid loops and check that traffic is moving forward toward the destination, as [RFC6550] specifies. No matter which OF a node uses, Rank will always increase, so once things converge, loop-free paths are always formed 💜

The Objective Function Zero (OF0) works with parameters that come from provisioning, the RPL DODAG Configuration option, and the RPL DODAG Information Object (DIO) base container [RFC6550] 🎀

A node's Rank comes from adding a strictly positive, indirectly normalized scalar, rank_increase (Section 6.1), to the Rank of its selected preferred parent. The rank_increase is based on a step_of_rank (Section 6.1) normalized scalar, which can vary with a ratio from 1 (excellent) to 9 (worst acceptable) to represent the link properties. The step_of_rank can get multiplied by a configurable factor called rank_factor (Section 6.2), which amplifies the rank_increase so it reflects the relative preferences between different link types used in the same RPL Instance. The rank_increase can be further adapted as detailed in Section 4.1. By default, OF0 encodes the 2-octet Rank in units of 256. The default settings allow encoding a minimum of 28 (worst acceptable) hops and a maximum of 255 (excellent) hops 🌈

The RPL specification [RFC6550] requires every node in a network to use a common OF. Using multiple OFs in a single network is for further study ⭐

The RPL specification [RFC6550] doesn't include any OF definitions. Those are left to other documents that focus on specific deployments and application environments. Since the main RPL spec has no default OF or metric container, two implementations could end up with no common OF to interoperate on, unless they follow the same guidance for a specific problem or environment 🙈

OF0 is designed to be the default OF, so implementations can interoperate across a wide spectrum of use cases. That's why OF0 doesn't say how link properties get turned into a rank_increase. It leaves that to the implementation. Instead, OF0 enforces the rank_increase values by normalizing the step_of_rank for a normal link and its acceptable range, rather than spelling out the details of how the step_of_rank gets computed. This is also why OF0 ignores metric containers 💖

2. Terminology 📖

The terminology in this document lines up with, and builds on, what's in "Terminology in Low power And Lossy Networks" [ROLL-TERMS] and [RFC6550] 🫶

The term "feasible successor" refers to a neighbor that could possibly be used as a next hop for Upward traffic. It follows the loop avoidance and forwarding rules that nodes implement, which are defined in the RPL specification [RFC6550] ✨

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119] 🔥

3. Objective Function Zero Overview 🧚‍♀️

The RPL specification describes constraints on how nodes pick potential parents, called a parent set, from their neighbors. Every parent is a feasible successor for upward traffic (toward the root). RPL also lets parents from a subsequent Version of the same DODAG count as feasible successors. In that case, this node acts as a leaf in the subsequent DODAG Version 🌸

The Goal of OF0 is for a node to join a DODAG Version that offers good enough connectivity to a specific set of nodes, or to a larger routing infrastructure. There's no guarantee the path will be optimized for any specific metric, though. How connectivity gets validated depends on the implementation and the link type, and it's out of scope. The validation involves, but isn't limited to, applying [RFC6550], Sections 3.2.3 and 13, as appropriate. It may also involve deployment-specific policies 🎀

So for OF0, the term "Grounded" [RFC6550] means the DODAG root provides that connectivity. How the connectivity gets asserted and maintained is out of scope 🌈

Objective Function Zero is designed to find the nearest Grounded root. That works when a node's Rank is very close to an abstract function of its distance to the root. That need gets balanced against maintaining some path diversity, which can be achieved by increasing the Rank. Without a Grounded root, inner connectivity within the LLN is still desirable, and floating DAGs form, rooted at the nodes with the highest administrative preference 🦋

OF0 selects a preferred parent, plus a backup feasible successor when one is available. Normally, all upward traffic goes through the preferred parent, with no attempt at load balancing. When link conditions stop an upward packet from getting through the preferred parent, the packet is passed to the backup feasible successor 💜

A RPL node monitors links to a number of neighbor nodes, and it can use OF0 to assign a rank_increase to each link. The exact method for computing the rank_increase depends on the implementation. Still, the computation must follow the rules specified in Section 4.1 💅

4.1. Computing Rank ✨

okay so first things first 💅 every OF0 node has to work out a variable called step_of_rank (see Section 6.1) for each parent it's looking at. It uses the relevant link properties and metrics to do it. That step_of_rank decides how much the Rank goes up along a particular link, and we'll get to the exact math in a sec 🦋

here's the tea 🫖 if you base step_of_rank on a static metric like an administrative cost, the node only really considers parents with good enough connectivity, and the Rank ends up acting kinda like hop-count. in most LLNs that favors paths with fewer but longer hops of poorer connectivity, which is giving not-it energy 😭 so it is RECOMMENDED to base the step_of_rank on dynamic link properties instead, like the expected transmission count (ETX) metric from [DeCouto03] that's discussed in [RFC6551]. "Minimum Rank Objective Function with Hysteresis" [HYSTERESIS] gives guidance on how link cost can be computed and how hysteresis can improve Rank stability ✨

OF0 lets an implementation stretch the step_of_rank so it can still pick at least one feasible successor and keep path diversity 🌈 BUT stretching the step_of_rank is NOT RECOMMENDED 🙈 it makes the node look farther from the root than it really is, it bends the DODAG away from its optimal shape, and it can cause instability. depending nodes start bumping up their Ranks to use each other as parents, and then you get a loop, which is a whole mess 💀 still, an implementation may stretch the step_of_rank, but only by up to a configurable stretch_of_rank (Section 6.2). that can be any value from 0 (no stretch) up to the fixed constant MAXIMUM_RANK_STRETCH (Section 6.3).

An implementation MUST maintain the stretched step_of_rank between the fixed constants MINIMUM_STEP_OF_RANK and MAXIMUM_STEP_OF_RANK (Section 6.3). that range is big enough to reflect a huge variety of link quality 🍓

the gap between MINIMUM_STEP_OF_RANK and MAXIMUM_RANK_STRETCH might not be enough in every case to really separate links of different types or categories. like, you might want powered nodes to beat battery-operated ones, or high-speed wired links to beat slower wireless ones, inside the same DAG 🔋⚡ so an implementation SHOULD let the operator configure a factor called rank_factor (Section 6.2). it gets applied on all links and peers to multiply the effect of the stretched step_of_rank in the rank_increase computation, which we'll look at below 🧚

also, an implementation MAY recognize categories of peers and links, such as different link types. if it does, it SHOULD be able to configure a more specific rank_factor for those categories 💜 the rank_factor MUST be set between the fixed constants MINIMUM_RANK_FACTOR and MAXIMUM_RANK_FACTOR (Section 6.3).

the rank_increase is measured in units given by the variable MinHopRankIncrease. that defaults to the fixed constant DEFAULT_MIN_HOP_RANK_INCREASE ([RFC6550]), and with that setting the least significant octet in the RPL Rank field in the DIO Base Object isn't used 🫶

so the math goes like this 🤓 the step_of_rank Sp computed for a link gets multiplied by the rank_factor Rf, and then it might get stretched by a term Sr that's less than or equal to the configured stretch_of_rank. the result is the rank_increase, and that gets added to the Rank of the preferred parent R(P) to get this node's Rank R(N):

R(N) = R(P) + rank_increase where:

rank_increase = (Rf*Sp + Sr) * MinHopRankIncrease

one more thing 👑 the administrative preference of a root MAY be configured to outrank the goal of joining a Grounded DODAG. if that's set up, nodes will associate with the root that has the highest preference available, even if that root isn't Grounded. compared to a deployment with a bunch of Grounded roots (which would make the same bunch of DODAGs), this can give you possibly fewer but bigger DODAGs, as many as there are roots configured with the highest priority in the reachable area ✨

4.2. Parent Selection

4.2.1. Selection of the Preferred Parent

as it scans all the candidate neighbors, OF0 keeps the parent that's the best for the following criteria, in order 👀

  1. [RFC6550], Section 8, spells out the generic rules for a node to re-parent, and in particular the boundaries for augmenting its Rank within a DODAG Version. a candidate that wouldn't satisfy those rules MUST NOT be considered 🚫
  2. before selecting a router as the preferred parent, an implementation SHOULD validate the connectivity and suitability of the router, as discussed in Section 3. this validation checks the Layer 2 connectivity to the router and the Layer 3 connectivity the router offers, and it may also look at other factors like locally or globally configured policies.

in most cases, a router that doesn't pass the validation process can't be considered any further for selection as preferred parent. either way, a router that did pass the validation SHOULD be preferred over one that didn't 💖

  1. when multiple interfaces are available, a policy might be configured locally to order them, and that policy applies first. so a router on a higher-order interface in the policy is preferable 🎀
  2. if the administrative preference of the root is configured to outrank the goal of joining a Grounded DODAG, a router that offers connectivity to a more preferable root SHOULD be preferred 👑
  3. a router that offers connectivity to a Grounded DODAG Version SHOULD be preferred over one that doesn't 🌸
  4. a router that offers connectivity to a more preferable root SHOULD be preferred 🌟
  5. when comparing two parents that belong to the same DODAG, a router that offers connectivity to the most recent DODAG Version SHOULD be preferred 🆕
  6. the parent that causes the lesser resulting Rank for this node, as specified in Section 4.1, SHOULD be preferred 📉
  7. a DODAG Version that has an alternate parent SHOULD be preferred. this check is OPTIONAL 🦋 it's done by computing the backup feasible successor while assuming the router being examined is finally selected as preferred parent.
  8. the preferred parent that was already in use SHOULD be preferred 🫧
  9. a router that has announced a DIO message more recently SHOULD be preferred 📣

these rules and their order MAY be varied by an implementation according to configured policy 🧩

4.2.2. Selection of the Backup Feasible Successor

when selecting a backup feasible successor, the OF goes through these checks in order 🔍

  1. the backup feasible successor MUST NOT be the preferred parent 🙅
  2. the backup feasible successor MUST be either in the same DODAG Version as this node or in a subsequent DODAG Version 💅
  3. along with RPL rules, a Router in the same DODAG Version as this node that has a Rank higher than the Rank computed for this node MUST NOT be selected as a feasible successor 🚫
  4. a router with a lesser Rank SHOULD be preferred 📉
  5. a router that has been validated as usable by an implementation-dependent validation process SHOULD be preferred ✅
  6. when multiple interfaces are available, a router on a higher order interface is preferable 🎀
  7. the backup feasible successor that was already in use SHOULD be preferred 🫶

these rules and their order MAY be varied by an implementation according to configured policy 🌈

5. Abstract Interface to OF0 🔌

Objective Function Zero interacts with the rest of the system for its management and operations in these ways:

  • Processing DIO: when a new DIO is received, the OF that matches the Objective Code Point (OCP) in the DIO gets triggered with the content of the DIO. OF0 is identified by OCP 0 (see Section 8) 🧚
  • Providing DAG Information: the OF0 support provides an interface that returns information about a given instance. that includes material from the DIO base header, the role (router, leaf), and the Rank of this node 📋
  • Providing a Parent List: the OF0 support provides an interface that returns the ordered list of parents and feasible successors for a given instance to the RPL core. that includes the material contained in the transit option for each entry 💜
  • Triggered Updates: the OF0 support provides events to tell it that a change in DAG information or the Parent List has happened. this can be caused by an interaction with another system component, like configuration, timers, and device drivers, and the change may make the RPL core fire a new DIO or reset Trickle timers ⏰

6. OF0 Operands 🍬

on top of the variables and constants defined in [RFC6550], this specification introduces the following variables and constants 🌸

6.1. Variables

OF0 uses the following variables:

  • step_of_rank (strictly positive integer): an intermediate computation based on the link properties with a certain neighbor 🪜
  • rank_increase (strictly positive integer): the delta between the Rank of the preferred parent and self 📏

6.2. Configurable Parameters

OF0 can use the following optional configurable values as parameters to the rank_increase computation ⚙️

  • stretch_of_rank (unsigned integer): the maximum augmentation to the step_of_rank of a preferred parent that allows the selection of an additional feasible successor. if none is configured on the device, the step_of_rank isn't stretched 🙅‍♀️
  • rank_factor (strictly positive integer): a configurable factor used to multiply the effect of the link properties in the rank_increase computation. if none is configured, a rank_factor of 1 is used ✨

6.3. Constants

Section 17 of [RFC6550] defines RPL constants. OF0 fixes the values of the following constants 🔒

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. Manageability Considerations 🛠️

Section 18 of [RFC6550] depicts the management of the protocol. this specification inherits from that section and its subsections, with one exception: the metrics specified in [RFC6551] are not used and don't require management 💖

7.1. Device Configuration 🎀

Okay bestie, config time 💅 An implementation SHOULD allow configuring at least a global rank_factor that applies to all links ✨ It can also group interfaces, links, and/or neighbors and set a more specific rank_factor for those groups 🧚

An implementation MAY allow configuring a maximum stretch_of_rank that MUST be less than or equal to MAXIMUM_RANK_STRETCH, as discussed in Section 4.1 🌸 If none is configured, a value of 0 is assumed and the step_of_rank is not stretched. Main character restraint 💅

An OF0 implementation SHOULD support the DODAG Configuration option as specified in Section 6.7.6 of [RFC6550] and apply the parameters in it 🦋 As discussed in Section 16 of [RFC6550], this requirement might be overridden by further guidance for certain application scenarios. When the option is used, the parameters get configured on the nodes that may become DODAG roots, and those nodes are configured to redistribute the info using the DODAG Configuration option. Lowkey a clean setup 🫶 The value of MinHopRankIncrease can be distributed with that option, and it overrides the fixed constant DEFAULT_MIN_HOP_RANK_INCREASE defined in Section 17 of [RFC6550] with a fixed value of 256 🔥

Out of the box, which means at initial factory time, the default constant values SHOULD be used, namely:

  • the rank_factor is set to the fixed constant DEFAULT_RANK_FACTOR (Section 6.3).
  • the maximum stretch_of_rank is set to the fixed constant DEFAULT_RANK_STRETCH (Section 6.3).
  • the MinHopRankIncrease is set to the fixed constant DEFAULT_MIN_HOP_RANK_INCREASE ([RFC6550]).

The values can be overridden at any time and apply at the next Version of the DODAG. As discussed in Section 16 of [RFC6550], this requirement might be overridden by further guidance for certain application scenarios. Defaults that you can still change, iconic 👑

7.2. Device Monitoring 🌈

As discussed in Section 5, the OF support must be able to provide information about its operations and trigger events when that information changes. At a minimum, the information should include:

  • DAG information as specified in Section 6.3.1 of [RFC6550], including the DODAGID, the RPLInstanceID, the Mode of Operation, the Rank of this node, the current Version Number, and the value of the Grounded flag.
  • A list of neighbors indicating the preferred parent and an alternate feasible one if available. For each neighbor, the Rank, the current Version Number, and the value of the Grounded flag should be indicated.

Monitoring so you're never blindsided 👀✨

8. IANA Considerations 🦋

Per this specification, an Objective Code Point (OCP) for OF0 has been assigned in the Objective Code Point Registry, as described in Section 20.5 of [RFC6550]. The registry entry looks like this:

OCP code:  0

Description:  A basic Objective Function that relies only on the
              objects that are defined in [RFC6550].

Defining RFC:  RFC 6552

Code 0, the basic one, iykyk 💖

9. Security Considerations 💀

This specification makes simple extensions to RPL, so it is vulnerable to and benefits from the security issues and mechanisms described in [RFC6550] and [ROLL-SECURITY]. This document does not introduce new flows or new messages, so it requires no specific mitigation for new threats. Not a lot of new surface area, but the old stuff still applies 🫶

OF0 depends on information exchanged in the Rank and OCP protocol elements. If those elements were compromised, an implementation of OF0 might generate the wrong path for a packet, and the packet could get misrouted 😭 Therefore, deployments are RECOMMENDED to use RPL security mechanisms if there is a risk that routing information might be modified or spoofed. Please protect your routing info, it's giving high stakes 🚨

10. Acknowledgements 🌸

Specific thanks to Philip Levis and Phoebus Chen for their help in finalizing this document 🧚

Many thanks also to Adrian Farrel, Tim Winter, JP. Vasseur, Julien Abeille, Mathilde Durvy, Teco Boot, Navneet Agarwal, Meral Shirazipour, and Henning Rogge for in-depth review and first-hand implementers' feedback. Honestly the real MVPs 👑💜

11. References 📚

11.1. Normative References

[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. Informative References

[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 Progress, 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 Progress,
                 March 2012.

[ROLL-TERMS]     Vasseur, JP., "Terminology in Low power And Lossy
                 Networks", Work in Progress, September 2011.

Author's Address 🖋️

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

And that's the whole spec, bestie 🌈💅 We did it, no cap ✨

📦 where this page comes from