idnits 2.17.1 draft-gnawali-roll-minrank-hysteresis-of-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Sep 2009 rather than the newer Notice from 28 Dec 2009. (See https://trustee.ietf.org/license-info/) Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (September 21, 2010) is 4959 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Outdated reference: A later version (-19) exists of draft-ietf-roll-routing-metrics-01 == Outdated reference: A later version (-19) exists of draft-ietf-roll-rpl-05 == Outdated reference: A later version (-13) exists of draft-ietf-roll-terminology-01 Summary: 1 error (**), 0 flaws (~~), 4 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Networking Working Group O. Gnawali 3 Internet-Draft P. Levis 4 Intended status: Standards Track Stanford University 5 Expires: March 25, 2011 September 21, 2010 7 The Minimum Rank Objective Function with Hysteresis 8 draft-gnawali-roll-minrank-hysteresis-of-02 10 Abstract 12 Hysteresis delays the effect of changes in link metric on parent 13 selection. Such delay makes the topology stable despite jitters in 14 link metrics. The Routing Protocol for Low Power and Lossy Networks 15 (RPL) allows the use of objective functions to construct routes that 16 optimize or constrain a routing metric on the paths. This 17 specification describes the Minimum Rank Objective Function with 18 Hysteresis (MRHOF), an objective function that minimizes the node 19 rank in terms of a given metric, while using hysteresis to prevent 20 excessive rank churn. The use of MRHOF with RPL results in nodes 21 selecting stable paths that minimize the given routing metric to the 22 roots of a Directed Acyclic Graph (DAG). 24 Status of this Memo 26 This Internet-Draft is submitted to IETF in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF), its areas, and its working groups. Note that 31 other groups may also distribute working documents as Internet- 32 Drafts. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 The list of current Internet-Drafts can be accessed at 40 http://www.ietf.org/ietf/1id-abstracts.txt. 42 The list of Internet-Draft Shadow Directories can be accessed at 43 http://www.ietf.org/shadow.html. 45 This Internet-Draft will expire on March 25, 2011. 47 Copyright Notice 48 Copyright (c) 2010 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (http://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 64 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3 65 3. The Minimum Rank Objective Function with Hysteresis . . . . . . 4 66 3.1. Computing the Path cost . . . . . . . . . . . . . . . . . . 4 67 3.2. Parent Selection . . . . . . . . . . . . . . . . . . . . . 5 68 3.3. Computing Rank . . . . . . . . . . . . . . . . . . . . . . 6 69 3.4. Advertising the path cost . . . . . . . . . . . . . . . . . 6 70 4. MRHOF Variables and Parameters . . . . . . . . . . . . . . . . 6 71 5. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 7 72 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 7 73 7. Security Considerations . . . . . . . . . . . . . . . . . . . . 7 74 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8 75 8.1. Normative References . . . . . . . . . . . . . . . . . . . 8 76 8.2. Informative References . . . . . . . . . . . . . . . . . . 8 77 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 8 79 1. Introduction 81 An objective function allows RPL [I-D.ietf-roll-rpl] to select paths 82 that are best in terms of a given routing metric or select paths that 83 meet certain constraints in terms of the routing metric. RPL 84 achieves this goal by selecting the parent among the alternate 85 parents as dictated by that objective function. For example, if an 86 RPL instance uses an objective function that minimizes hop-count, RPL 87 will select paths with minimum hop count. 89 The nodes running RPL might use a number of metrics to describe a 90 link or a node [I-D.ietf-roll-routing-metrics] and make it available 91 for route selection. A metric can be used by different objective 92 functions to optimize or constrain the metric in different ways. 94 This specification describes MRHOF, an objective function for RPL. 95 MRHOF uses hysteresis while selecting the path with the smallest 96 metric value. The path with the minimum cost has different property 97 depending on the metric used for path selection. For example, the 98 use of MRHOF with the latency metric allows RPL to find stable 99 minimum-latency paths from the nodes to a root in the DAG instance. 100 The use of MRHOF with the ETX metric allows RPL to find the stable 101 minimum-ETX paths from the nodes to a root in the DAG instance. 103 MRHOF can be used with additive metric that must be minimized on the 104 paths selected for routing. Although MRHOF can be used with a number 105 of metrics, this draft is based on experiences with the ETX metric. 107 2. Terminology 109 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 110 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 111 "OPTIONAL" in this document are to be interpreted as described in RFC 112 2119 [RFC2119]. 114 This terminology used in this document is consistent with the 115 terminologies described in [I-D.ietf-roll-terminology], 116 [I-D.ietf-roll-rpl], and [I-D.ietf-roll-routing-metrics]. 118 This document introduces two terms: 120 Selected metric: The metric chosen by the network operator to use 121 for path selection. This metric can be any additive metric 122 listed in [I-D.ietf-roll-routing-metrics] 124 Path cost: Path cost quantifies a property of an end-to-end path. 125 Path cost is composed using the selected metric of the links 126 along the path. Path cost can be used by RPL to compare 127 different paths. 129 3. The Minimum Rank Objective Function with Hysteresis 131 The Minimum Rank Objective Function with Hysteresis, MRHOF, is 132 designed to find the paths with the smallest path cost while 133 preventing excessive churn in the network. It does so by switching 134 to the minimum cost path only if the path cost of the current path is 135 larger than the path cost of the minimum cost path by a given 136 threshold. MRHOF may be used with any additive metric listed in 137 [I-D.ietf-roll-routing-metrics] as long the routing objective is to 138 minimize the given routing metric. MRHOF cannot be used if the 139 routing objective is to maximize the metric. 141 3.1. Computing the Path cost 143 Nodes compute the path cost for each candidate neighbor reachable on 144 all the interfaces. The Path cost represents the cost of the path, 145 in terms of the selected metric, from a node to the root of the DODAG 146 through the neighbor. 148 Root nodes (Grounded or Floating) set the variable cur_min_path_cost 149 to MIN_PATH_COST. 151 A non-root node computes the path cost for a path to the root through 152 each candidate neighbor by adding these two components: 154 1. The selected metric for the link to a candidate neighbor. 156 2. The value of the selected metric in the metric container in the 157 DIO sent by that neighbor. 159 A node SHOULD compute the path cost for the path through each 160 candidate neighbor reachable through all the interfaces. If a node 161 cannot compute the path cost for the path through a candidate 162 neighbor, the node MUST NOT select the candidate neighbor as its 163 preferred parent with one exception. If the node does not have 164 metrics to compute the path cost through any of the candidate 165 neighbors, it SHOULD join one of the candidate neighbors as a leaf 166 node. 168 If the selected metric of the link to a neighbor is not available, 169 the path cost for the path through that neighbor SHOULD be set to 170 MAX_PATH_COST. This cost value will prevent this path from being 171 considered for path selection. 173 The path cost corresponding to a neighbor SHOULD be re-computed each 174 time: 176 1. The selected metric of the link to the candidate neighbor is 177 updated. 179 2. A node receives a new metric advertisement from the candidate 180 neighbor. 182 This computation MAY also be performed periodically. However, long 183 intervals between periodic computation or deferring the computation 184 for too long after new metric advertisements or updates to the 185 selected link metric prevents results in node making parent selection 186 based on stale link and path information. 188 3.2. Parent Selection 190 After computing the path cost for all the candidate neighbors 191 reachable through all the interfaces for the current DODAG iteration, 192 a node selects the preferred parent. This process is called parent 193 selection. 195 A node MUST select a candidate neighbor as its preferred parent if 196 the path cost corresponding to that neighbor is smaller than the path 197 cost corresponding to the rest of the neighbors, except as indicated 198 below: 200 1. If the smallest path cost for paths through the candidate 201 neighbors is smaller than cur_min_path_cost by less than 202 PARENT_SWITCH_THRESHOLD, the node MAY continue to use the current 203 preferred parent. 205 2. If there are multiple paths with the smallest path cost and that 206 the smallest path cost is smaller than cur_min_path_cost by at 207 least PARENT_SWITCH_THRESHOLD, a node MAY use a different 208 objective function to select the preferred parent among the 209 candidates which are first hop on the path with the minimum cost. 211 3. A node MAY declare itself as a Floating root, and hence no 212 preferred parent, depending on the configuration. 214 4. If the selected metric for a link is greater than 215 MAX_LINK_METRIC, the node SHOULD exclude that link from 216 consideration for parent selection. 218 5. If cur_min_path_cost is greater than MAX_PATH_COST, the node MAY 219 declare itself as a Floating root. 221 6. If the configuration disallows a node to be a Floating root and 222 no neighbors are discovered, the node does not have a preferred 223 parent, and MUST set cur_min_path_cost to MAX_PATH_COST. 225 3.3. Computing Rank 227 Once a node selects its preferred parent, it can use the following 228 table to covert its path cost to the DAG root through its preferred 229 parent (written as Cost in the table) to its rank: 231 +--------------------+------------+ 232 | Node/link Metric | Rank | 233 +--------------------+------------+ 234 | Node Energy | 255 - Cost | 235 | Hop-Count | Cost | 236 | Latency | Cost/65536 | 237 | Link Quality Level | Cost | 238 | ETX | Cost | 239 +--------------------+------------+ 241 Table 1: Conversion of metric to rank. 243 Node rank is undefined for these node/link metrics: Node state and 244 attributes, node fanout ratio, throughput, and link color. 246 3.4. Advertising the path cost 248 Once the preferred parent is selected, the node sets its 249 cur_min_path_cost variable to the path cost corresponding to the 250 preferred parent. Thus, cur_min_path_cost is the cost of the minimum 251 cost path from the node to the root. The value of the 252 cur_min_path_cost is carried in the metric container whenever DIO 253 messages are sent. 255 4. MRHOF Variables and Parameters 257 MRHOF uses the following variable: 259 cur_min_path_cost: The cost of the path from a node through its 260 preferred parent to the root computed at the last parent 261 selection. 263 MRHOF uses the following parameters: 265 MAX_LINK_METRIC: Maximum allowed value for the selected link 266 metric for each link on the path. 268 MAX_PATH_COST: Maximum allowed value for the path metric of a 269 selected path. 271 MIN_PATH_COST: The minimum allowed value for the path metric of 272 the selected path. 274 PARENT_SWITCH_THRESHOLD: The difference between metric of the path 275 through the preferred parent and the minimum-metric path to 276 trigger new preferred parent selection. 278 The parameter values are assigned depending on the selected metric. 279 Here is an example parameter assignment for the ETX metric: 281 MAX_LINK_METRIC: 10. Disallow links with greater than 10 expected 282 transmission count on the selected path. 284 MAX_PATH_COST: 100. Disallow paths with greater than 100 expected 285 transmission count. 287 MIN_PATH_COST: 0. At root, the expected transmission count is 0. 289 PARENT_SWITCH_THRESHOLD: 1.0. Switch to a new path only if it is 290 requires at least one fewer transmission than the current path. 292 5. Acknowledgements 294 6. IANA Considerations 296 This specification requires an allocated OCP. A value of 1 is 297 requested. 299 7. Security Considerations 301 Security considerations to be developed in accordance to the output 302 of the WG. 304 8. References 305 8.1. Normative References 307 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 308 Requirement Levels", BCP 14, RFC 2119, March 1997. 310 8.2. Informative References 312 [I-D.ietf-roll-routing-metrics] 313 Vasseur, J. and D. Networks, "Routing Metrics used for 314 Path Calculation in Low Power and Lossy Networks", 315 draft-ietf-roll-routing-metrics-01 (work in progress), 316 October 2009. 318 [I-D.ietf-roll-rpl] 319 Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing 320 Protocol for Low power and Lossy Networks", 321 draft-ietf-roll-rpl-05 (work in progress), December 2009. 323 [I-D.ietf-roll-terminology] 324 Vasseur, J., "Terminology in Low power And Lossy 325 Networks", draft-ietf-roll-terminology-01 (work in 326 progress), May 2009. 328 Authors' Addresses 330 Omprakash Gnawali 331 Stanford University 332 S255 Clark Center, 318 Campus Drive 333 Stanford, CA 94305 334 USA 336 Phone: +1 650 725 6086 337 Email: gnawali@cs.stanford.edu 339 Philip Levis 340 Stanford University 341 358 Gates Hall, Stanford University 342 Stanford, CA 94305 343 USA 345 Email: pal@cs.stanford.edu