idnits 2.17.1 draft-ietf-roll-minrank-hysteresis-of-04.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 (May 17, 2011) is 4721 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 (-13) exists of draft-ietf-roll-terminology-05 Summary: 1 error (**), 0 flaws (~~), 2 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: November 18, 2011 May 17, 2011 7 The Minimum Rank Objective Function with Hysteresis 8 draft-ietf-roll-minrank-hysteresis-of-04 10 Abstract 12 The Routing Protocol for Low Power and Lossy Networks (RPL) uses 13 objective functions to construct routes that optimize or constrain 14 the routes it selects and uses. This specification describes the 15 Minimum Rank Objective Function with Hysteresis (MRHOF), an objective 16 function that selects routes that minimize a metric, while using 17 hysteresis to reduce churn in response to small metric changes. 18 MRHOF works with metrics that are additive along a route, and the 19 metric it uses is determined by the metrics RPL Destination 20 Information Object (DIO) messages advertise. 22 Status of this Memo 24 This Internet-Draft is submitted to IETF in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF), its areas, and its working groups. Note that 29 other groups may also distribute working documents as Internet- 30 Drafts. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 The list of current Internet-Drafts can be accessed at 38 http://www.ietf.org/ietf/1id-abstracts.txt. 40 The list of Internet-Draft Shadow Directories can be accessed at 41 http://www.ietf.org/shadow.html. 43 This Internet-Draft will expire on November 18, 2011. 45 Copyright Notice 47 Copyright (c) 2011 IETF Trust and the persons identified as the 48 document authors. All rights reserved. 50 This document is subject to BCP 78 and the IETF Trust's Legal 51 Provisions Relating to IETF Documents 52 (http://trustee.ietf.org/license-info) in effect on the date of 53 publication of this document. Please review these documents 54 carefully, as they describe your rights and restrictions with respect 55 to this document. Code Components extracted from this document must 56 include Simplified BSD License text as described in Section 4.e of 57 the Trust Legal Provisions and are provided without warranty as 58 described in the BSD License. 60 Table of Contents 62 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 63 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 64 3. The Minimum Rank Objective Function with Hysteresis . . . . . 4 65 3.1. Computing the Path cost . . . . . . . . . . . . . . . . . 4 66 3.2. Parent Selection . . . . . . . . . . . . . . . . . . . . . 5 67 3.3. Computing Rank . . . . . . . . . . . . . . . . . . . . . . 6 68 3.4. Advertising the Path Cost . . . . . . . . . . . . . . . . 7 69 3.5. Working Without Metric Containers . . . . . . . . . . . . 7 70 4. Using MRHOF for Metric Maximization . . . . . . . . . . . . . 7 71 5. MRHOF Variables and Parameters . . . . . . . . . . . . . . . . 8 72 5.1. Manageability . . . . . . . . . . . . . . . . . . . . . . 9 73 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9 74 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 75 8. Security Considerations . . . . . . . . . . . . . . . . . . . 9 76 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10 77 9.1. Normative References . . . . . . . . . . . . . . . . . . . 10 78 9.2. Informative References . . . . . . . . . . . . . . . . . . 10 79 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10 81 1. Introduction 83 An objective function specifies how RPL [I-D.ietf-roll-rpl] selects 84 paths. Objective functions can choose paths based on routing metrics 85 or constraints. For example, if an RPL instance uses an objective 86 function that minimizes hop-count, RPL will select paths with minimum 87 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. These metrics are advertised in RPL Destination 92 Information Object (DIO) messages using a Metric Container suboption. 93 An objective function can use these metrics to choose routes. The 94 only exception is the ETX metric, which is used without the metric 95 container as described in Section 3.5. 97 To decouple the details of an individual metric or objective function 98 from forwarding and routing, RPL describes routes through a value 99 called Rank. Rank, roughly speaking, corresponds to the distance 100 associated with a route. An objective function is responsible for 101 computing a node's advertised Rank value based on the Rank of its 102 potential parents, metrics, and other network properties. 104 This specification describes MRHOF, an objective function for RPL. 105 MRHOF uses hysteresis while selecting the path with the smallest 106 metric value. The metric that MRHOF uses is determined by the 107 metrics in the DIO Metric Container. For example, the use of MRHOF 108 with the latency metric allows RPL to find stable minimum-latency 109 paths from the nodes to a root in the DAG instance. The use of MRHOF 110 with the ETX metric allows RPL to find the stable minimum-ETX paths 111 from the nodes to a root in the DAG instance. 113 MRHOF can only be used with an additive metric that must be minimized 114 on the paths selected for routing. 116 2. Terminology 118 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 119 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 120 "OPTIONAL" in this document are to be interpreted as described in RFC 121 2119 [RFC2119]. 123 This terminology used in this document is consistent with the 124 terminologies described in [I-D.ietf-roll-terminology], 125 [I-D.ietf-roll-rpl], and [I-D.ietf-roll-routing-metrics]. 127 This document introduces two terms: 129 Selected metric: The metric chosen by the network operator to use 130 for path selection. This metric can be any additive metric 131 listed in [I-D.ietf-roll-routing-metrics]. 133 Path cost: Path cost quantifies a property of an end-to-end path. 134 Path cost is obtained by summing up the selected metric of the 135 links or nodes along the path. Path cost can be used by RPL to 136 compare different paths. 138 Worst parent: The node in the parent set with the largest path cost. 140 3. The Minimum Rank Objective Function with Hysteresis 142 The Minimum Rank Objective Function with Hysteresis, MRHOF, is 143 designed to find the paths with the smallest path cost while 144 preventing excessive churn in the network. It does so by finding the 145 minimum cost path and switching to that path only if it is shorter 146 (in terms of path cost) than the current path by at least a given 147 threshold. MRHOF may be used with any additive metric listed in 148 [I-D.ietf-roll-routing-metrics] as long the routing objective is to 149 minimize the given routing metric. 151 3.1. Computing the Path cost 153 Nodes compute the path cost for each candidate neighbor reachable on 154 an interface. The Path cost represents the cost of the path, in 155 terms of the selected metric, from a node to the root of the DODAG 156 through the neighbor. 158 Root nodes (Grounded or Floating) set the variable cur_min_path_cost 159 to MIN_PATH_COST. 161 A non-root node computes the path cost for a path to the root through 162 each candidate neighbor by adding these two components: 164 1. If the selected metric is a link metric, the selected metric for 165 the link to a candidate neighbor. If the selected metric is a 166 node metric, the selected metric for the node. 168 2. The value of the selected metric in the metric container in the 169 DIO sent by that neighbor. 171 A node SHOULD compute the path cost for the path through each 172 candidate neighbor reachable through an interface. If a node cannot 173 compute the path cost for the path through a candidate neighbor, the 174 node MUST NOT select the candidate neighbor as its preferred parent, 175 with one exception. If the node does not have metrics to compute the 176 path cost through any of the candidate neighbors, it MUST join one of 177 the candidate neighbors as a leaf node. 179 If the selected metric is a link metric and the metric of the link to 180 a neighbor is not available, the path cost for the path through that 181 neighbor SHOULD be set to MAX_PATH_COST. This cost value will 182 prevent this path from being considered for path selection. 184 If the selected metric is a node metric, and the metric is not 185 available, the path cost through all the neighbors SHOULD be set to 186 MAX_PATH_COST. 188 The path cost corresponding to a neighbor SHOULD be re-computed each 189 time: 191 1. The selected metric of the link to the candidate neighbor is 192 updated. 194 2. If the selected metric is a node metric and the metric is 195 updated. 197 3. A node receives a new metric advertisement from the candidate 198 neighbor. 200 This computation MAY also be performed periodically. Too much delay 201 in updating the path cost after the metric is updated or a new metric 202 advertisement is received can lead to stale Rank or parent set. 204 3.2. Parent Selection 206 After computing the path cost for all the candidate neighbors 207 reachable through an interface for the current DODAG iteration, a 208 node selects the preferred parent. This process is called parent 209 selection. Parent Selection SHOULD be performed each time: 211 1. The path cost for an existing candidate neighbor, including the 212 preferred parent, changes. This condition can be checked 213 immediately after the path cost is computed. 215 2. A new candidate neighbor is inserted into the neighbor table. 217 The parent selection MAY be deferred until a later time. Deferring 218 the parent selection can delay the use of better paths available in 219 the network. 221 A node MUST select a candidate neighbor as its preferred parent if 222 the path cost corresponding to that neighbor is smaller than the path 223 cost corresponding to the rest of the neighbors, except as indicated 224 below: 226 1. If the smallest path cost for paths through the candidate 227 neighbors is smaller than cur_min_path_cost by less than 228 PARENT_SWITCH_THRESHOLD, the node MAY continue to use the current 229 preferred parent. 231 2. If there are multiple paths with the smallest path cost and the 232 smallest path cost is smaller than cur_min_path_cost by at least 233 PARENT_SWITCH_THRESHOLD, a node MAY use a different objective 234 function to select the preferred parent among the candidate 235 neighbors on the path with the minimum cost. 237 3. A node MAY declare itself as a Floating root, and hence no 238 preferred parent, depending on the configuration. 240 4. If the selected metric for a link is greater than 241 MAX_LINK_METRIC, the node SHOULD exclude that link from 242 consideration for parent selection. 244 5. If cur_min_path_cost is greater than MAX_PATH_COST, the node MAY 245 declare itself as a Floating root. 247 6. If ALLOW_FLOATING_ROOT is 0 and no neighbors are discovered, the 248 node does not have a preferred parent, and MUST set 249 cur_min_path_cost to MAX_PATH_COST. 251 Except in the cases above, the candidate neighbor on the path with 252 the smallest path cost is the preferred parent. A node MAY include a 253 total of PARENT_SET_SIZE candidate neighbors in the parent set. The 254 cost of path through the nodes in the parent set is smaller than or 255 equal to the cost of the paths through any of the nodes that are not 256 in the parent set. If the cost of the path through the preferred 257 parent and the worst parent is too large, a node MAY keep a smaller 258 parent set. 260 3.3. Computing Rank 262 The DAG roots set their rank to MIN_PATH_COST for the selected 263 metric. 265 Once a non-root node selects its parent set, it can use the following 266 table to covert the path cost of the worst parent (written as Cost in 267 the table) to its rank: 269 +--------------------+------------+ 270 | Node/link Metric | Rank | 271 +--------------------+------------+ 272 | Node Energy | 255 - Cost | 273 | Hop-Count | Cost | 274 | Latency | Cost/65536 | 275 | Link Quality Level | Cost | 276 | ETX | Cost | 277 +--------------------+------------+ 279 Table 1: Conversion of metric to rank. 281 Nodes MUST support at least one of the above metrics. Nodes SHOULD 282 support the ETX metric. 284 Node rank is undefined for these node/link metrics: Node state and 285 attributes, throughput, and link color. If the rank is undefined, 286 the node must join one of the neighbors as a leaf node according to 287 [I-D.ietf-roll-rpl]. 289 3.4. Advertising the Path Cost 291 Once the preferred parent is selected, the node sets its 292 cur_min_path_cost variable to the path cost corresponding to the 293 preferred parent. Thus, cur_min_path_cost is the cost of the minimum 294 cost path from the node to the root. The value of the 295 cur_min_path_cost is carried in the metric container corresponding to 296 the selected metric when DIO messages are sent. 298 If ETX is the selected metric, cur_min_path_cost is directly used as 299 Rank and never advertised in a metric container. 301 3.5. Working Without Metric Containers 303 In the absence of metric container, MRHOF uses ETX as its metric. It 304 locally computes the ETX of links to its neighbors and adds this 305 value to their advertised Rank to compute the associated Rank of 306 routes. Once parent selection and rank computation is performed 307 using the ETX metric, the node advertises a Rank equal to the ETX 308 cost and MUST NOT include a metric container in its DIO messages. 310 4. Using MRHOF for Metric Maximization 312 MRHOF cannot be directly used for parent selection using metrics 313 which require finding paths with maximum value of the selected 314 metric, such as path reliability. It is possible to convert such a 315 metric maximization problem to a metric minimization problem for some 316 metrics and use MRHOF provided: 318 There is a fixed and well-known maximum metric value corresponding 319 to the best path. This is the path cost for the DAG root. For 320 example, the logarithm of the best link reliability has a value of 321 0. 323 The metrics in the maximization problem are all negative. The 324 logarithm of the link reliability is always negative. 326 For metrics meeting the above conditions, the problem of maximizing 327 the metric value is equivalent to minimizing the modified metric 328 value, e.g., logarithm of link reliability. MRHOF is not required to 329 work with these metrics. 331 5. MRHOF Variables and Parameters 333 MRHOF uses the following variable: 335 cur_min_path_cost: The cost of the path from a node through its 336 preferred parent to the root computed at the last parent 337 selection. 339 MRHOF uses the following parameters: 341 MAX_LINK_METRIC: Maximum allowed value for the selected link 342 metric for each link on the path. 344 MAX_PATH_COST: Maximum allowed value for the path metric of a 345 selected path. 347 MIN_PATH_COST: The minimum allowed value for the path metric of 348 the selected path. 350 PARENT_SWITCH_THRESHOLD: The difference between metric of the path 351 through the preferred parent and the minimum-metric path in order 352 to trigger the selection of a new preferred parent. 354 PARENT_SET_SIZE: The number of candidate parents, including the 355 preferred parent, in the parent set. 357 ALLOW_FLOATING_ROOT: If set to 1, allows a node to become a 358 floating root. 360 The parameter values are assigned depending on the selected metric. 361 The best values for these parameters should be experimentally 362 determined. The working group has long experience routing with the 363 ETX metric. Based on those experiences, these values are 364 RECOMMENDED: 366 MAX_LINK_METRIC: 10. Disallow links with greater than 10 expected 367 transmission count on the selected path. 369 MAX_PATH_COST: 100. Disallow paths with greater than 100 expected 370 transmission count. 372 MIN_PATH_COST: 0. At root, the expected transmission count is 0. 374 PARENT_SWITCH_THRESHOLD: 1.5. Switch to a new path only if it is 375 expected to require at least 1.5 fewer transmission than the 376 current path. 378 PARENT_SET_SIZE: 3. If the preferred parent is not available, two 379 candidate parents are still available without triggering a new 380 round of route discovery. 382 ALLOW_FLOATING_ROOT: 0. Do not allow a node to become a floating 383 root. 385 5.1. Manageability 387 The parameters MAX_LINK_METRIC, MAX_PATH_COST, MIN_PATH_COST, 388 PARENT_SWITCH_THRESHOLD, PARENT_SET_SIZE, and ALLOW_FLOATING_ROOT 389 should be configurable. 391 6. Acknowledgements 393 Thanks to Antonio Grilo, Nicolas Tsiftes, Matteo Paris, JP Vasseur, 394 and Phoebus Chen for their comments. 396 7. IANA Considerations 398 This specification requires an allocated OCP. A value of 1 is 399 requested. 401 8. Security Considerations 403 Security considerations to be developed in accordance to the output 404 of the WG. 406 9. References 407 9.1. Normative References 409 [I-D.ietf-roll-routing-metrics] 410 Vasseur, J., Kim, M., Pister, K., Dejean, N., and D. 411 Barthel, "Routing Metrics used for Path Calculation in Low 412 Power and Lossy Networks", 413 draft-ietf-roll-routing-metrics-19 (work in progress), 414 March 2011. 416 [I-D.ietf-roll-rpl] 417 Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., 418 Kelsey, R., Levis, P., Pister, K., Struik, R., and J. 419 Vasseur, "RPL: IPv6 Routing Protocol for Low power and 420 Lossy Networks", draft-ietf-roll-rpl-19 (work in 421 progress), March 2011. 423 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 424 Requirement Levels", BCP 14, RFC 2119, March 1997. 426 9.2. Informative References 428 [I-D.ietf-roll-terminology] 429 Vasseur, J., "Terminology in Low power And Lossy 430 Networks", draft-ietf-roll-terminology-05 (work in 431 progress), March 2011. 433 Authors' Addresses 435 Omprakash Gnawali 436 Stanford University 437 S255 Clark Center, 318 Campus Drive 438 Stanford, CA 94305 439 USA 441 Phone: +1 650 725 6086 442 Email: gnawali@cs.stanford.edu 444 Philip Levis 445 Stanford University 446 358 Gates Hall, Stanford University 447 Stanford, CA 94305 448 USA 450 Email: pal@cs.stanford.edu