RFC 6719

The Minimum Rank with Hysteresis Objective Function

📅 published September 2012, from ietf

The Minimum Rank with Hysteresis Objective Function ✨

RFC 6719 🎀 is written by O. Gnawali (University of Houston) and P. Levis (Stanford University). It's a Standards Track doc with ISSN 2070-1721, published September 2012. The title block doesn't list anything it obsoletes or updates, so there's no earlier RFC to chase down here. 💅

Abstract

RPL 🌸 builds routes using Objective Functions, which either optimize the routes it picks or constrain them. This spec introduces the Minimum Rank with Hysteresis Objective Function (MRHOF) 👑, which picks the routes that minimize a metric. It also uses hysteresis so the network doesn't churn every time a metric wiggles a little. 🦋 MRHOF works with additive metrics along a route, and which metrics it uses depends on what the RPL Destination Information Object (DIO) messages advertise.

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). For more on Internet Standards, check Section 2 of RFC 5741. 💜

Info about the current status of this document, any errata, and how to send feedback lives at http://www.rfc-editor.org/info/rfc6719. 🌈

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) in effect on the date of publication of this document. Please review these documents carefully, because they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions, and they're provided without warranty as described in the Simplified BSD License. 📜

Table of Contents

1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  2
2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  3
3.  The Minimum Rank with Hysteresis Objective Function  . . . . .  4
  3.1.  Computing the Path Cost  . . . . . . . . . . . . . . . . .  4
  3.2.  Parent Selection . . . . . . . . . . . . . . . . . . . . .  5
    3.2.1.  When Parent Selection Runs . . . . . . . . . . . . . .  6
    3.2.2.  Parent Selection Algorithm . . . . . . . . . . . . . .  6
  3.3.  Computing Rank . . . . . . . . . . . . . . . . . . . . . .  7
  3.4.  Advertising the Path Cost  . . . . . . . . . . . . . . . .  8
  3.5.  Working without Metric Containers  . . . . . . . . . . . .  8
4.  Using MRHOF for Metric Maximization  . . . . . . . . . . . . .  9
5.  MRHOF Variables and Parameters . . . . . . . . . . . . . . . .  9
6.  Manageability  . . . . . . . . . . . . . . . . . . . . . . . . 10
  6.1.  Device Configuration . . . . . . . . . . . . . . . . . . . 10
  6.2.  Device Monitoring  . . . . . . . . . . . . . . . . . . . . 11
7.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 12
8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 12
9.  Security Considerations  . . . . . . . . . . . . . . . . . . . 12
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12
  10.1. Normative References . . . . . . . . . . . . . . . . . . . 12
  10.2. Informative References . . . . . . . . . . . . . . . . . . 13

1. Introduction 🦋

RPL [RFC6550] is the thing that decides how paths get picked, and an Objective Function is what tells it how. Say an RPL instance uses an Objective Function that minimizes hop count. Then RPL will pick paths with the minimum hop count. 🌸 RPL requires that every node in a network uses the same Objective Function. Relaxing that requirement might be something people study later. 🔮

Nodes running RPL can use a bunch of metrics to describe a link or a node [RFC6551] and make them available for route selection. RPL advertises metrics in DIO messages using a Metric Container suboption, and an Objective Function can use those metrics to choose routes. 💅

To keep the details of a metric or an Objective Function separate from forwarding and routing, RPL describes routes with a value called Rank. Rank roughly stands for how far away a route is. RPL defines how nodes decide on paths based on Rank and how they advertise their Rank. An Objective Function defines how nodes calculate their Rank, using the Rank of their potential parents, the metrics, and other network properties. 🧠

This spec describes MRHOF, an Objective Function for RPL that uses hysteresis while picking the path with the smallest metric value. The metric MRHOF uses comes from the metrics in the DIO Metric Container. For example, MRHOF with the latency metric lets RPL find stable minimum-latency paths from nodes to a root in the Directed Acyclic Graph (DAG) instance [RFC6550]. MRHOF with the Expected Transmission Count (ETX) metric [RFC6551] lets RPL find stable minimum-ETX paths from nodes to a root in the DAG instance. If there's no metric in the DIO Metric Container, or there's no DIO Metric Container at all, MRHOF defaults to using ETX to compute Rank, as described in Section 3.5. 🌈

MRHOF tries to minimize path costs measured by metrics, so it can only be used with additive metrics. MRHOF doesn't support metrics that aren't additive. 🚫

2. Terminology 📖

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]. 💖

The terms used here line up with the ones in [ROLL-TERM] and [RFC6551]. They also line up with the terms in [RFC6550], except for Rank. In this document, Rank means the value of the Rank field, not DAGRank as in [RFC6550]. 🎀

This document introduces three terms: ✨

  • Selected metric: The metric the network operator picks for path selection. MRHOF supports using a single metric for path selection. Choosing a metric other than ETX is shown by that metric being present in the DIO Metric Container. Choosing ETX is shown by the Metric Container being absent, and in that case ETX is advertised as Rank. 📊
  • Path cost: Path cost measures a property of an end-to-end path. Each node gets it by adding the selected link metric to the path cost its parent advertised. RPL can use path cost to compare different paths. 🛣️
  • Worst parent: The node in the parent set with the largest path cost. 💀

3. The Minimum Rank with Hysteresis Objective Function 👑

MRHOF is built to find the paths with the smallest path cost while keeping churn in the network under control. It does this with two mechanisms. The first one finds the minimum cost path, which is the path with the minimum Rank. The second one switches to that minimum Rank path only if it's shorter (in path cost) than the current path by at least a given threshold. That second mechanism is called "hysteresis". 🌸

MRHOF can be used with any additive metric listed in [RFC6551], as long as the routing objective is to minimize that metric. Nodes MUST support at least one of these metrics: hop count, latency, or ETX. Nodes SHOULD support the ETX metric. MRHOF doesn't support non-additive metrics. 🔥

3.1. Computing the Path Cost 🧮

Root nodes (Grounded or Floating) set the variable cur_min_path_cost to the metric value that works out to a Rank of MinHopRankIncrease. 🌱

If a non-root node doesn't have the metrics it needs to compute the path cost through any of its candidate neighbors, it MUST join one of the candidate neighbors as a RPL Leaf. 🍃

Otherwise, nodes compute the path cost for each candidate neighbor reachable on an interface. A neighbor's path cost is the cost of the path from a node to the root of the Destination-Oriented DAG (DODAG) through that neighbor, measured by the selected metric. A non-root node works out a neighbor's path cost by adding two components: ✨

  1. If the selected metric is a link metric, it's the selected metric for the link to the candidate neighbor. If the selected metric is a node metric, it's the selected metric for the node.
  2. It's the value of the selected metric in the Metric Container of the DIO that neighbor sent. If the Metric Container is empty, ETX is the selected metric, so use the Rank that neighbor advertised as the second component. See Section 3.5 for how ETX gets used in MRHOF. 💅

A node SHOULD compute the path cost for the path through each candidate neighbor reachable through an interface. If a node can't compute the path cost for the path through a candidate neighbor, the node MUST NOT select that candidate neighbor as its preferred parent. But if the node can't compute the path cost through any neighbor, it may join a candidate neighbor as a Leaf, as described above. 🙈

If the selected metric is a link metric and the metric of the link to a neighbor isn't available, the path cost for the path through that neighbor SHOULD be set to MAX_PATH_COST. That cost value keeps this path from getting considered for path selection. 🚫

If the selected metric is a node metric and the metric isn't available, the path cost through all the neighbors SHOULD be set to MAX_PATH_COST. 🚫

The path cost for a neighbor SHOULD be recomputed each time any of these conditions is met: 🔁

  1. The selected metric of the link to the candidate neighbor is updated.
  2. The selected metric is a node metric and that metric is updated.
  3. A node receives a new metric advertisement from the candidate neighbor.

This computation SHOULD also be performed periodically. Delaying it up to a minimum Trickle interval [RFC6550] is harmless. But if you wait longer to update the path cost after the metric changes or a new metric advertisement shows up, the info can go stale. ⏰

3.2. Parent Selection 🎯

After computing the path cost for all the candidate neighbors reachable through an interface for the current DODAG iteration [RFC6550], a node picks its preferred parent. This process is called "parent selection". To allow hysteresis, parent selection keeps a variable, cur_min_path_cost, which holds the path cost of the current preferred parent. 🦋

3.2.1. When Parent Selection Runs ✨

okay so an MRHOF implementation SHOULD run Parent Selection each time either of these happens 🫶

  1. The path cost for an existing candidate neighbor changes, and that includes the preferred parent 📈. You can check this right after the path cost gets computed.
  2. A brand new candidate neighbor gets added to the neighbor table 🆕.

If, for whatever reason, you need to put off parent selection until later (like up to the Trickle minimum interval [RFC6550]), just know that waiting can delay the use of better paths in the network 🐢. not ideal bestie 😭

3.2.2. Parent Selection Algorithm 👑

if the selected metric for a link is bigger than MAX_LINK_METRIC, the node SHOULD exclude that link from parent selection 🚫. bye bye link 👋

the node MUST select the candidate neighbor with the lowest path cost as its preferred parent. the exceptions are below 👇:

  1. A node MAY declare itself a Floating root, which means it has no preferred parent. whether it can do this depends on system configuration 🧚
  2. If cur_min_path_cost is greater than MAX_PATH_COST, the node MAY declare itself a Floating root 🌈.
  3. If the smallest path cost through the candidate neighbors is smaller than cur_min_path_cost by less than PARENT_SWITCH_THRESHOLD, the node MAY keep using its current preferred parent 💜. this is the hysteresis part of MRHOF, and it's giving stability 🎀.
  4. If ALLOW_FLOATING_ROOT is 0 and no neighbors are discovered, the node doesn't have a preferred parent and MUST set cur_min_path_cost to MAX_PATH_COST 💀.

if a bunch of neighbors all share the smallest path cost, the node MAY use a different selection criteria to pick which one counts as the lowest cost 🍓.

a node MAY include up to PARENT_SET_SIZE-1 extra candidate neighbors in its parent set 🦋. the cost of the path through any node in the parent set is smaller than or equal to the cost of any path through a node that's NOT in the parent set (okay that's the whole point of a parent set, iconic ✨). and if the cost of the path through the preferred parent and the worst parent is too large, a node MAY keep a smaller parent set than PARENT_SET_SIZE 🌸.

once the preferred parent is picked, the node sets cur_min_path_cost to the path cost of that preferred parent 🎯. the cur_min_path_cost value gets carried in the Metric Container for the selected metric whenever DIO messages are sent 📦.

3.3. Computing Rank 🧮

DAG roots set their Rank to MinHopRankIncrease 👑. easy.

once a non-root node picks its parent set, it can use the table below to turn the path cost of a parent (called Cost in the table) into a Rank value 🔥:

                 +------------------+------------+
                 | Node/link Metric |    Rank    |
                 +------------------+------------+
                 |     Hop-Count    |    Cost    |
                 |      Latency     | Cost/65536 |
                 |        ETX       |    Cost    |
                 +------------------+------------+

               Table 1: Conversion of Metric to Rank

if MRHOF is used with other metrics, the Rank is undefined 🙈. and if the Rank is undefined, the node must join one of its neighbors as an RPL Leaf node according to [RFC6550] 🍃.

MRHOF uses this Rank value to work out the Rank it associates with the path through each member of the parent set. the Rank for a path through a parent set member is the maximum of two values. the first is the Rank from the table above, and the second is that node's advertised Rank plus MinHopRankIncrease 💖.

a node sets its Rank to the maximum of three values 🌈:

  1. The Rank calculated for the path through the preferred parent.
  2. The Rank of the parent set member with the highest advertised Rank, rounded up to the next integral Rank. in other words, MinHopRankIncrease * (1 + floor(Rank/MinHopRankIncrease)) 📐.
  3. The largest calculated Rank among the paths through the parent set, minus MaxRankIncrease 🫧.

the first case is the Rank for the path through the preferred parent. the second case covers requirement 5 of Rank advertisements in Section 8.2.1 of [RFC6550]. the third case makes sure a node doesn't advertise a Rank that would stop it from using the members of its own parent set 🛡️.

heads up, the third case means a node advertises a conservative Rank based on its parent set 🧐. that conservative value can be way higher than the Rank for the path through the preferred parent. so if you pick a parent set with a huge spread of Ranks, routing will likely end up subptimal 😬. nodes might skip good paths because they look much worse than they really are 💀. how the parent set gets picked is an implementation decision 🎀.

3.4. Advertising the Path Cost 📣

once the preferred parent is picked, the node sets cur_min_path_cost to the path cost for that preferred parent 🎯. then it works out the metric it will advertise in its metric container 💅. this value is the path cost of the parent set member with the highest path cost. so while cur_min_path_cost is the cost through the preferred parent, a node advertises the highest cost path from itself to the root through a member of its parent set 🌸. that highest cost value gets carried in the metric container for the selected metric whenever DIO messages are sent 📦.

if ETX is the selected metric, a node MUST NOT advertise it in a metric container 🚫. instead, the node MUST advertise an approximation of its ETX in its advertised Rank value, following the rules in Section 3.3 ✨. and if a node receives a DIO with a Metric Container holding an ETX metric, MRHOF MUST ignore that ETX metric value in its Rank calculations 🙈.

DODAG Roots advertise a metric value that computes to a Rank of MinHopRankIncrease 👑.

3.5. Working without Metric Containers 🫧

if there's no Metric Container, MRHOF uses ETX as its metric 💖. it works out the ETX of its links to neighbors locally, then adds that value to their advertised Rank to get the associated Rank of routes 🧮. once parent selection and Rank computation are done using ETX, the node advertises its Rank and MUST NOT include a metric container in its DIO messages 🚫. while assigning Rank in this case, use the representation of ETX described in [RFC6551], so assign Rank equal to ETX * 128 ✨.

4. Using MRHOF for Metric Maximization 🔄

MRHOF can't be used directly for parent selection with metrics that need paths with a MAXIMUM value of the selected metric, like path reliability 😭. you can convert a metric maximization problem into a metric minimization problem for some metrics and still use MRHOF, but only if:

  • There is a fixed and well-known maximum metric value for the best path. this is the path cost for the DAG root. for example, the logarithm of the best link reliability is 0 🧠.
  • The metrics in the maximization problem are all negative. the logarithm of link reliability is always negative 🫶.

for metrics that meet the conditions above, maximizing the metric value is equivalent to minimizing the modified metric value, like the logarithm of link reliability 💜. MRHOF is not required to work with these metrics 🌈.

5. MRHOF Variables and Parameters 🎀

MRHOF uses this one variable 👇:

  • cur_min_path_cost: The cost of the path from a node through its preferred parent to the root, computed at the last parent selection.

MRHOF uses these parameters 📋:

  • MAX_LINK_METRIC: Maximum allowed value for the selected link metric on each link in the path.
  • MAX_PATH_COST: Maximum allowed value for the path metric of a selected path.
  • PARENT_SWITCH_THRESHOLD: The difference between the cost of the path through the preferred parent and the minimum cost path, needed to trigger selecting a new preferred parent.
  • PARENT_SET_SIZE: The number of candidate parents in the parent set, including the preferred parent.
  • ALLOW_FLOATING_ROOT: If set to 1, lets a node become a floating root.

the parameter values are set depending on the selected metric 🧩. the best values are decided by what the specific RPL deployment needs 🏠. for example, if you use ETX as the selected metric and UDP as the transport protocol, you should use a small MAX_LINK_METRIC (like an ETX of 1.1) so link-layer retransmissions are enough to give a good chance of end-to-end reliability 🔥.

the working group has tons of experience routing with the ETX metric [Hui08b] 🤓. based on that experience, the following values are RECOMMENDED when ETX is the selected metric 💅:

  • MAX_LINK_METRIC: 512. Disallow links with more than 4 expected transmission counts on the selected path 🚫.
  • MAX_PATH_COST: 32768. Disallow paths with more than 256 expected transmission counts 🙅.
  • PARENT_SWITCH_THRESHOLD: 192. Switch to a new path only if it's expected to need at least 1.5 fewer transmissions than the current path 🔄.
  • PARENT_SET_SIZE: 3. If the preferred parent isn't available, two candidate parents are still around without triggering a new round of route discovery 🫶.
  • ALLOW_FLOATING_ROOT: 0. Don't allow a node to become a floating root 🙅‍♀️.

6. Manageability 🧚

Section 18 of [RFC6550] covers the management of RPL 📖. this specification inherits from that section and its subsections, with one exception: the metrics specified in [RFC6551] aren't used and don't need management 🌸.

6.1. Device Configuration 🎀

okay so first up, config time ⚙️ An implementation SHOULD let you set these five at install time: MAX_LINK_METRIC, MAX_PATH_COST, PARENT_SWITCH_THRESHOLD, PARENT_SET_SIZE, and ALLOW_FLOATING_ROOT. It MAY also let you tweak them at run time once the network is live, which is giving flexibility 💜

A MRHOF implementation MUST support the DODAG Configuration option as described in [RFC6550] and apply the parameters it specifies. ✨ Now here's the tea 🫖 care should be taken with how the MRHOF PARENT_SWITCH_THRESHOLD parameter relates to the RPL MaxRankIncrease parameter. For example, if MaxRankIncrease is smaller than PARENT_SWITCH_THRESHOLD, a RPL node using MRHOF could end up in a situation where its current preferred parent pushes the node's Rank up past MaxRankIncrease, but MRHOF doesn't switch parents. 😭 That could make the node drop out of the routing topology, even though other members of the parent set could have kept its Rank within MaxRankIncrease. Not ideal, bestie 💀

Unless you configure otherwise, a MRHOF implementation SHOULD use the default parameters as specified in Section 5. 🌸

Okay, now the vibe check on Rank and metric values 🧐 They're only partially coupled, so networks using MRHOF need care when setting MinHopRankIncrease. A large MinHopRankIncrease means MRHOF can't pick between paths with different hop counts but similar metric values. If MinHopRankIncrease is big enough that its increment is more than what link cost adds, then metrics will pick the preferred parent, but the advertised Rank is just a plain hop count. 🙈 That might be exactly what you want, but it might also be an accident, so care is recommended 🍓

Also, with ETX as the selected metric, RPL's Rank advertisement rules can make a DODAG Root advertise a Rank higher than its ETX value, since a DODAG Root advertises a Rank of MinHopRankIncrease. Every DODAG Root in a DODAG Version advertises the same Rank, so this constant usually doesn't change route selection. 🦋 Still, it means that if a DODAG Version has a MinHopRankIncrease of M and a path has an advertised ETX of E, the actual ETX of that path is probably closer to E-M than to E. Main character math 🧮👑

6.2. Device Monitoring 🔥

A MRHOF implementation should provide an interface for monitoring how it's doing 👀 At a minimum, the info it gives you 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 showing the preferred parent. For each neighbor, the list should show the Rank, the current Version Number, the value of the Grounded flag, and the associated metrics.

7. Acknowledgements 🫶

Huge thank-yous to Antonio Grilo, Nicolas Tsiftes, Matteo Paris, JP Vasseur, and Phoebus Chen for their comments. 💖 Also big love to Barry Leiba, Brian Haberman, Martin Stiemerling, Ralph Droms, Robert Sparks, Russ Housley, Stephen Farrell, Wesley Eddy, Miguel A. Garcia, Mukul Goyal, and Michael Richardson for their feedback during the publication phase. You're all iconic 👑

8. IANA Considerations 📋

Per this document, IANA has allocated value 1 from the "Objective Code Point (OCP)" sub-registry of the "Routing Protocol for Low Power and Lossy Networks (RPL)" registry. ✨ One code point, very much claimed 💅

9. Security Considerations 🚨

Okay, serious moment, but make it cute 🎀 This specification makes simple extensions to RPL, so it's vulnerable to, and also benefits from, the security issues and mechanisms described in [RFC6550] and [ROLL-SEC]. This document does not introduce new flows or new messages, so it doesn't need any specific mitigation for new threats.

MRHOF depends on information exchanged in a number of RPL protocol elements. If those elements get compromised, an implementation of MRHOF might generate the wrong path for a packet, and the packet could end up misrouted. 😱 That's a major risk, so deployments are RECOMMENDED to use RPL security mechanisms whenever there's a risk that routing information might be modified or spoofed. Protect your routing info like it's your group chat password 🔐💀

10. References 📚

10.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., Thubert, P., 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.

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

10.2. Informative References

   [Hui08b]    Hui, J. and D. Culler, "IP is dead, long live IP for
               wireless sensor networks", Proceedings of the 6th ACM
               Conference on Embedded Networked Systems SenSys 2008,
               November 2008,
               <http://portal.acm.org/citation.cfm?id=1460412.1460415>.

   [ROLL-SEC]  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, January 2012.

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

Authors' Addresses 🦋

   Omprakash Gnawali
   University of Houston
   PGH 577, University of Houston
   Houston, TX  77204
   USA

   Phone: +1 713 743 3356
   EMail: gnawali@cs.uh.edu


   Philip Levis
   Stanford University
   412 Gates Hall, Stanford University
   Stanford, CA  94305
   USA

   EMail: pal@cs.stanford.edu
📦 where this page comes from