--- 1/draft-ietf-roll-minrank-hysteresis-of-08.txt 2012-04-23 08:14:00.126671441 +0200 +++ 2/draft-ietf-roll-minrank-hysteresis-of-09.txt 2012-04-23 08:14:00.146670882 +0200 @@ -1,19 +1,19 @@ Networking Working Group O. Gnawali Internet-Draft University of Houston Intended status: Standards Track P. Levis -Expires: October 22, 2012 Stanford University - April 20, 2012 +Expires: October 24, 2012 Stanford University + April 22, 2012 The Minimum Rank with Hysteresis Objective Function - draft-ietf-roll-minrank-hysteresis-of-08 + draft-ietf-roll-minrank-hysteresis-of-09 Abstract The Routing Protocol for Low Power and Lossy Networks (RPL) uses objective functions to construct routes that optimize or constrain the routes it selects and uses. This specification describes the Minimum Rank with Hysteresis Objective Function (MRHOF), an objective function that selects routes that minimize a metric, while using hysteresis to reduce churn in response to small metric changes. MRHOF works with metrics that are additive along a route, and the @@ -28,21 +28,21 @@ Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." - This Internet-Draft will expire on October 22, 2012. + This Internet-Draft will expire on October 24, 2012. Copyright Notice 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 @@ -56,48 +56,47 @@ 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 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 . . . . . . . . . . . . 9 + 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 . . . . . . . . . . . . . . . . . . . 11 + 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 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13 1. Introduction An objective function specifies how RPL [RFC6550] selects paths. For example, if an RPL instance uses an objective function that minimizes hop-count, RPL will select paths with minimum hop count. RPL requires that all nodes in a network use a common OF; relaxing this requirement may be a subject of future study. The nodes running RPL might use a number of metrics to describe a - link or a node [I-D.ietf-roll-routing-metrics] and make these metrics - available for route selection. RPL advertises metrics in RPL - Destination Information Object (DIO) messages with a Metric Container - suboption. An objective function can use these metrics to choose - routes. + link or a node [RFC6551] and make these metrics available for route + selection. RPL advertises metrics in RPL Destination Information + Object (DIO) messages with a Metric Container suboption. An + objective function can use these metrics to choose routes. To decouple the details of an individual metric or objective function from forwarding and routing, RPL describes routes through a value called Rank. Rank, roughly speaking, corresponds to the distance associated with a route. RPL defines how nodes decide on paths based on Rank and advertise their Rank. An objective function defines how nodes calculate Rank, based on the Rank of its potential parents, metrics, and other network properties. This specification describes MRHOF, an objective function for RPL. @@ -117,56 +116,54 @@ that are not 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 terminologies used in this document are consistent with the - terminologies described in [I-D.ietf-roll-terminology] and - [I-D.ietf-roll-routing-metrics]. + terminologies described in [I-D.ietf-roll-terminology] and [RFC6551]. The terminologies used in this document are also consistent with the - terminologies described in RFC 6550 [RFC6550], except the term Rank. - In this document, Rank refers to the value of the Rank field, not - DAGRank as in RFC 6550 [RFC6550]. + terminologies described in [RFC6550], except the term Rank. In this + document, Rank refers to the value of the Rank field, not DAGRank as + in [RFC6550]. This document introduces three terms: Selected metric: The metric chosen by the network operator to use for path selection. This metric can be any additive metric - listed in [I-D.ietf-roll-routing-metrics]. + listed in [RFC6551]. Path cost: Path cost quantifies a property of an end-to-end path. Path cost is obtained by summing up the selected metric of the links or nodes along the path. Path cost can be used by RPL 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 The Minimum Rank with Hysteresis Objective Function, MRHOF, is designed to find the paths with the smallest path cost while preventing excessive churn in the network. It does so by finding the minimum cost path and switching to that path only if it is shorter (in terms of path cost) than the current path by at least a given threshold. - MRHOF may be used with any additive metric listed in - [I-D.ietf-roll-routing-metrics] as long the routing objective is to - minimize the given routing metric. Nodes MUST support at least one - of these metrics: node energy, hop count, latency, link quality - level, and ETX. Nodes SHOULD support the ETX metric. MRHOF does not - support non-additive metrics. + MRHOF may be used with any additive metric listed in [RFC6551] as + long the routing objective is to minimize the given routing metric. + Nodes MUST support at least one of these metrics: node energy, hop + count, latency, link quality level, and ETX. Nodes SHOULD support + the ETX metric. MRHOF does not support non-additive metrics. 3.1. Computing the Path cost Root nodes (Grounded or Floating) set the variable cur_min_path_cost to MIN_PATH_COST. If a non-root node does not have metrics to compute the path cost through any of the candidate neighbors, it MUST join one of the candidate neighbors as a RPL Leaf. @@ -442,23 +439,22 @@ candidate parents are still available without triggering a new round of route discovery. ALLOW_FLOATING_ROOT: 0. Do not allow a node to become a floating root. 6. Manageability Section 18 of [RFC6550] depicts the management of RPL. This specification inherits from that section and its subsections, with - the exception that metrics as specified in - [I-D.ietf-roll-routing-metrics] are not used and do not require - management. + the exception that metrics as specified in [RFC6551] are not used and + do not require management. 6.1. Device Configuration An implementation SHOULD allow the following parameters to be configured at installation time: MAX_LINK_METRIC, MAX_PATH_COST, MIN_PATH_COST, PARENT_SWITCH_THRESHOLD, PARENT_SET_SIZE, and ALLOW_FLOATING_ROOT. An implementation MAY allow these parameters to be configured dynamically at run time once a network has been deployed. @@ -480,20 +477,29 @@ Because of the partially-coupled relationship between Rank and metric values, networks using MRHOF require care in setting MinHopRankIncrease. A large MinHopRankIncrease will cause MRHOF to be unable to select paths with different hop counts but similar metric values. If MinHopRankIncrease is large enough that its increment is greater than that caused by link cost, then metrics will be used to select a preferred parent but the advertised Rank will be a simple hopcount. This behavior might be desirable, but it also might be unintended: care is recommended. + RPL's Rank advertisement rules can require a DODAG Root to advertise + a Rank higher than its corresponding ETX value, as a DODAG Root + advertises a Rank of MinHopRankIncrease. Because all DODAG Roots + within a DODAG Version advertise the same Rank, this constant value + typically does not affect route selection. Nevertheless, it means + that if a DODAG Version has a MinHopRankIncrease of M and a path has + an advertised ETX of E, then the actual ETX of the path is likely + closer to a value of E-M than a value of E. + 6.2. Device Monitoring A MRHOF implementation should provide an interface for monitoring its operation. At a minimum, the information provided should include: DAG information as specified in Section 6.3.1 of [RFC6550], and 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. @@ -524,35 +530,32 @@ elements. If those elements were compromised, then an implementation of MRHOF might generate the wrong path for a packet, resulting in it being misrouted. Therefore, deployments are RECOMMENDED to use RPL security mechanisms if there is a risk that routing information might be modified or spoofed. 10. References 10.1. Normative References - [I-D.ietf-roll-routing-metrics] - Barthel, D., Vasseur, J., Pister, K., Kim, M., and N. - Dejean, "Routing Metrics used for Path Calculation in Low - Power and Lossy Networks", - draft-ietf-roll-routing-metrics-19 (work in progress), - March 2011. - [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 [I-D.ietf-roll-security-framework] Tsao, T., Alexander, R., Dohler, M., Daza, V., and A. Lozano, "A Security Framework for Routing over Low Power and Lossy Networks", draft-ietf-roll-security-framework-07 (work in progress), January 2012. [I-D.ietf-roll-terminology] Vasseur, J., "Terminology in Low power And Lossy