idnits 2.17.1 draft-ietf-roll-minrank-hysteresis-of-09.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. 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 (April 22, 2012) is 4387 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: 0 errors (**), 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 University of Houston 4 Intended status: Standards Track P. Levis 5 Expires: October 24, 2012 Stanford University 6 April 22, 2012 8 The Minimum Rank with Hysteresis Objective Function 9 draft-ietf-roll-minrank-hysteresis-of-09 11 Abstract 13 The Routing Protocol for Low Power and Lossy Networks (RPL) uses 14 objective functions to construct routes that optimize or constrain 15 the routes it selects and uses. This specification describes the 16 Minimum Rank with Hysteresis Objective Function (MRHOF), an objective 17 function that selects routes that minimize a metric, while using 18 hysteresis to reduce churn in response to small metric changes. 19 MRHOF works with metrics that are additive along a route, and the 20 metric it uses is determined by the metrics RPL Destination 21 Information Object (DIO) messages advertise. 23 Status of this Memo 25 This Internet-Draft is submitted in full conformance with the 26 provisions of BCP 78 and BCP 79. 28 Internet-Drafts are working documents of the Internet Engineering 29 Task Force (IETF). Note that other groups may also distribute 30 working documents as Internet-Drafts. The list of current Internet- 31 Drafts is at http://datatracker.ietf.org/drafts/current/. 33 Internet-Drafts are draft documents valid for a maximum of six months 34 and may be updated, replaced, or obsoleted by other documents at any 35 time. It is inappropriate to use Internet-Drafts as reference 36 material or to cite them other than as "work in progress." 38 This Internet-Draft will expire on October 24, 2012. 40 Copyright Notice 42 Copyright (c) 2012 IETF Trust and the persons identified as the 43 document authors. All rights reserved. 45 This document is subject to BCP 78 and the IETF Trust's Legal 46 Provisions Relating to IETF Documents 47 (http://trustee.ietf.org/license-info) in effect on the date of 48 publication of this document. Please review these documents 49 carefully, as they describe your rights and restrictions with respect 50 to this document. Code Components extracted from this document must 51 include Simplified BSD License text as described in Section 4.e of 52 the Trust Legal Provisions and are provided without warranty as 53 described in the Simplified BSD License. 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 58 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 59 3. The Minimum Rank with Hysteresis Objective Function . . . . . 4 60 3.1. Computing the Path cost . . . . . . . . . . . . . . . . . 4 61 3.2. Parent Selection . . . . . . . . . . . . . . . . . . . . . 5 62 3.2.1. When Parent Selection Runs . . . . . . . . . . . . . . 6 63 3.2.2. Parent Selection Algorithm . . . . . . . . . . . . . . 6 64 3.3. Computing Rank . . . . . . . . . . . . . . . . . . . . . . 7 65 3.4. Advertising the Path Cost . . . . . . . . . . . . . . . . 8 66 3.5. Working Without Metric Containers . . . . . . . . . . . . 8 67 4. Using MRHOF for Metric Maximization . . . . . . . . . . . . . 9 68 5. MRHOF Variables and Parameters . . . . . . . . . . . . . . . . 9 69 6. Manageability . . . . . . . . . . . . . . . . . . . . . . . . 10 70 6.1. Device Configuration . . . . . . . . . . . . . . . . . . . 10 71 6.2. Device Monitoring . . . . . . . . . . . . . . . . . . . . 11 72 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 12 73 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 74 9. Security Considerations . . . . . . . . . . . . . . . . . . . 12 75 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12 76 10.1. Normative References . . . . . . . . . . . . . . . . . . . 12 77 10.2. Informative References . . . . . . . . . . . . . . . . . . 13 78 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13 80 1. Introduction 82 An objective function specifies how RPL [RFC6550] selects paths. For 83 example, if an RPL instance uses an objective function that minimizes 84 hop-count, RPL will select paths with minimum hop count. RPL 85 requires that all nodes in a network use a common OF; relaxing this 86 requirement may be a subject of future study. 88 The nodes running RPL might use a number of metrics to describe a 89 link or a node [RFC6551] and make these metrics available for route 90 selection. RPL advertises metrics in RPL Destination Information 91 Object (DIO) messages with a Metric Container suboption. An 92 objective function can use these metrics to choose routes. 94 To decouple the details of an individual metric or objective function 95 from forwarding and routing, RPL describes routes through a value 96 called Rank. Rank, roughly speaking, corresponds to the distance 97 associated with a route. RPL defines how nodes decide on paths based 98 on Rank and advertise their Rank. An objective function defines how 99 nodes calculate Rank, based on the Rank of its potential parents, 100 metrics, and other network properties. 102 This specification describes MRHOF, an objective function for RPL. 103 MRHOF uses hysteresis while selecting the path with the smallest 104 metric value. The metric that MRHOF uses is determined by the 105 metrics in the DIO Metric Container. For example, the use of MRHOF 106 with the latency metric allows RPL to find stable minimum-latency 107 paths from the nodes to a root in the DAG instance. The use of MRHOF 108 with the ETX metric allows RPL to find the stable minimum-ETX paths 109 from the nodes to a root in the DAG instance. In the absence of a 110 metric in the DIO Metric Container or the lack of a DIO Metric 111 Container, MRHOF defaults to using ETX to compute Rank, as described 112 in Section 3.5. 114 Because MRHOF seeks to minimize path costs as described by metrics, 115 it can only be used with additive metrics. MRHOF ignores metrics 116 that are not additive. 118 2. Terminology 120 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 121 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 122 "OPTIONAL" in this document are to be interpreted as described in RFC 123 2119 [RFC2119]. 125 The terminologies used in this document are consistent with the 126 terminologies described in [I-D.ietf-roll-terminology] and [RFC6551]. 128 The terminologies used in this document are also consistent with the 129 terminologies described in [RFC6550], except the term Rank. In this 130 document, Rank refers to the value of the Rank field, not DAGRank as 131 in [RFC6550]. 133 This document introduces three terms: 135 Selected metric: The metric chosen by the network operator to use 136 for path selection. This metric can be any additive metric 137 listed in [RFC6551]. 139 Path cost: Path cost quantifies a property of an end-to-end path. 140 Path cost is obtained by summing up the selected metric of the 141 links or nodes along the path. Path cost can be used by RPL to 142 compare different paths. 144 Worst parent: The node in the parent set with the largest path cost. 146 3. The Minimum Rank with Hysteresis Objective Function 148 The Minimum Rank with Hysteresis Objective Function, MRHOF, is 149 designed to find the paths with the smallest path cost while 150 preventing excessive churn in the network. It does so by finding the 151 minimum cost path and switching to that path only if it is shorter 152 (in terms of path cost) than the current path by at least a given 153 threshold. 155 MRHOF may be used with any additive metric listed in [RFC6551] as 156 long the routing objective is to minimize the given routing metric. 157 Nodes MUST support at least one of these metrics: node energy, hop 158 count, latency, link quality level, and ETX. Nodes SHOULD support 159 the ETX metric. MRHOF does not support non-additive metrics. 161 3.1. Computing the Path cost 163 Root nodes (Grounded or Floating) set the variable cur_min_path_cost 164 to MIN_PATH_COST. 166 If a non-root node does not have metrics to compute the path cost 167 through any of the candidate neighbors, it MUST join one of the 168 candidate neighbors as a RPL Leaf. 170 Otherwise, nodes compute the path cost for each candidate neighbor 171 reachable on an interface. The path cost of a neighbor represents 172 the cost of the path, in terms of the selected metric, from a node to 173 the root of the DODAG through that neighbor. A non-root node 174 computes a neighbor's path cost by adding two components: 176 1. If the selected metric is a link metric, the selected metric for 177 the link to a candidate neighbor. If the selected metric is a 178 node metric, the selected metric for the node. 180 2. The value of the selected metric in the metric container in the 181 DIO sent by that neighbor. 183 A node SHOULD compute the path cost for the path through each 184 candidate neighbor reachable through an interface. If a node cannot 185 compute the path cost for the path through a candidate neighbor, the 186 node MUST NOT select the candidate neighbor as its preferred parent, 187 except if it cannot compute the path cost through any neighbor, in 188 which case it may join as a leaf as described above. 190 If the selected metric is a link metric and the metric of the link to 191 a neighbor is not available, the path cost for the path through that 192 neighbor SHOULD be set to MAX_PATH_COST. This cost value will 193 prevent this path from being considered for path selection. 195 If the selected metric is a node metric, and the metric is not 196 available, the path cost through all the neighbors SHOULD be set to 197 MAX_PATH_COST. 199 The path cost corresponding to a neighbor SHOULD be re-computed each 200 time: 202 1. The selected metric of the link to the candidate neighbor is 203 updated. 205 2. If the selected metric is a node metric and the metric is 206 updated. 208 3. A node receives a new metric advertisement from the candidate 209 neighbor. 211 This computation MAY also be performed periodically. Too much delay 212 in updating the path cost after the metric is updated or a new metric 213 advertisement is received can lead to stale information. 215 3.2. Parent Selection 217 After computing the path cost for all the candidate neighbors 218 reachable through an interface for the current DODAG iteration, a 219 node selects the preferred parent. This process is called parent 220 selection. To allow hysteresis, parent selection maintains a 221 variable, cur_min_path_cost, which is the path cost of the current 222 preferred parent. 224 3.2.1. When Parent Selection Runs 226 A MRHOF implementation SHOULD perform Parent Selection each time: 228 1. The path cost for an existing candidate neighbor, including the 229 preferred parent, changes. This condition can be checked 230 immediately after the path cost is computed. 232 2. A new candidate neighbor is inserted into the neighbor table. 234 The parent selection MAY be deferred until a later time. Deferring 235 the parent selection can delay the use of better paths available in 236 the network. 238 3.2.2. Parent Selection Algorithm 240 If the selected metric for a link is greater than MAX_LINK_METRIC, 241 the node SHOULD exclude that link from consideration during parent 242 selection. 244 A node MUST select the candidate neighbor with the lowest path cost 245 as its preferred parent, except as indicated below: 247 1. A node MAY declare itself as a Floating root, and hence have no 248 preferred parent, depending on system configuration. 250 2. If cur_min_path_cost is greater than MAX_PATH_COST, the node MAY 251 declare itself as a Floating root. 253 3. If the smallest path cost for paths through the candidate 254 neighbors is smaller than cur_min_path_cost by less than 255 PARENT_SWITCH_THRESHOLD, the node MAY continue to use the current 256 preferred parent. This is the hysteresis component of MRHOF. 258 4. If ALLOW_FLOATING_ROOT is 0 and no neighbors are discovered, the 259 node does not have a preferred parent, and MUST set 260 cur_min_path_cost to MAX_PATH_COST. 262 If there are multiple neighbors which share the smallest path cost, a 263 node MAY use a different objective function to select which of these 264 neighbors should be considered to have the lowest cost. 266 A node MAY include up to PARENT_SET_SIZE-1 additional candidate 267 neighbors in its parent set. The cost of path through the nodes in 268 the parent set is smaller than or equal to the cost of the paths 269 through any of the nodes that are not in the parent set. If the cost 270 of the path through the preferred parent and the worst parent is too 271 large, a node MAY keep a smaller parent set than PARENT_SET_SIZE. 273 Once the preferred parent is selected, the node sets its 274 cur_min_path_cost variable to the path cost corresponding to the 275 preferred parent. The value of the cur_min_path_cost is carried in 276 the metric container corresponding to the selected metric when DIO 277 messages are sent. 279 3.3. Computing Rank 281 DAG roots set their Rank to MinHopRankIncrease. 283 Once a non-root node selects its parent set, it can use the following 284 table to covert the path cost of a parent (written as Cost in the 285 table) to a Rank value: 287 +--------------------+------------+ 288 | Node/link Metric | Rank | 289 +--------------------+------------+ 290 | Node Energy | 255 - Cost | 291 | Hop-Count | Cost | 292 | Latency | Cost/65536 | 293 | Link Quality Level | Cost | 294 | ETX | Cost | 295 +--------------------+------------+ 297 Table 1: Conversion of metric to rank. 299 Rank is undefined for these node/link metrics: node state and 300 attributes, throughput, and link color. If the rank is undefined, 301 the node must join one of the neighbors as a RPL Leaf node according 302 to [RFC6550]. 304 MRHOF uses this Rank value to compute the Rank it associates with the 305 path through each member of the parent set. The Rank associated with 306 a path through a member of the parent set is the maximum of two 307 values. The first is corresponding Rank value calculated with the 308 table above, the second is that node's advertised Rank plus 309 MinHopRankIncrease. 311 A node sets its Rank to the maximum of three values: 313 1. The Rank calculated for the path through the preferred parent 315 2. The Rank of the member of the parent set with the highest 316 advertised Rank, rounded to the next higher integral Rank, ie, to 317 MinHopRankIncrease * (1 + floor(Rank/MinHopRankIncrease)). 319 3. The largest calculated Rank among paths through the parent set, 320 minus MaxRankIncrease 322 The first case is the Rank associated with the path through the 323 preferred parent. The second case covers requirement 5 of Rank 324 advertisements in Section 8.2.1 of [RFC6550]. The third case ensures 325 that a node does not advertise a Rank which then precludes it from 326 using members of its parent set. 328 Note that the third case means that a node advertises a conservative 329 Rank value based on members of its parent set. This conservative 330 value might be significantly higher than the Rank calculated for the 331 path through the preferred parent. Accordingly, picking a parent set 332 whose paths have a large range of Ranks will likely result in sub- 333 optimal routing: nodes might not choose good paths because they are 334 advertised as much worse than they actually are. The exact selection 335 of a parent set is an implementation decision. 337 3.4. Advertising the Path Cost 339 Once the preferred parent is selected, the node sets its 340 cur_min_path_cost variable to the path cost corresponding to its 341 preferred parent. It then calculates the metric it will advertise in 342 its metric container. This value is the path cost of the member of 343 the parent set with the highest path cost. Thus, while 344 cur_min_path_cost is the cost through the preferred parent, a node 345 advertises the highest cost path from the node to the root through a 346 member of the parent set. The value of the highest cost path is 347 carried in the metric container corresponding to the selected metric 348 when DIO messages are sent. 350 If ETX is the selected metric, a node SHOULD NOT advertise it in a 351 metric container. Instead, a node MUST advertise an approximation of 352 its ETX in its advertised Rank value, following the rules described 353 in Section 3.3. If a node receives a DIO with a metric container 354 holding an ETX metric, MRHOF MUST ignore the ETX metric value in its 355 Rank calculations. 357 DODAG Roots advertise a metric value which computes to a cost of 358 MIN_PATH_COST. 360 3.5. Working Without Metric Containers 362 In the absence of metric container, MRHOF uses ETX as its metric. It 363 locally computes the ETX of links to its neighbors and adds this 364 value to their advertised Rank to compute the associated Rank of 365 routes. Once parent selection and rank computation is performed 366 using the ETX metric, the node advertises a Rank equal to the ETX 367 cost and MUST NOT include a metric container in its DIO messages. 369 4. Using MRHOF for Metric Maximization 371 MRHOF cannot be directly used for parent selection using metrics 372 which require finding paths with maximum value of the selected 373 metric, such as path reliability. It is possible to convert such a 374 metric maximization problem to a metric minimization problem for some 375 metrics and use MRHOF provided: 377 There is a fixed and well-known maximum metric value corresponding 378 to the best path. This is the path cost for the DAG root. For 379 example, the logarithm of the best link reliability has a value of 380 0. 382 The metrics in the maximization problem are all negative. The 383 logarithm of the link reliability is always negative. 385 For metrics meeting the above conditions, the problem of maximizing 386 the metric value is equivalent to minimizing the modified metric 387 value, e.g., logarithm of link reliability. MRHOF is not required to 388 work with these metrics. 390 5. MRHOF Variables and Parameters 392 MRHOF uses the following variable: 394 cur_min_path_cost: The cost of the path from a node through its 395 preferred parent to the root computed at the last parent 396 selection. 398 MRHOF uses the following parameters: 400 MAX_LINK_METRIC: Maximum allowed value for the selected link 401 metric for each link on the path. 403 MAX_PATH_COST: Maximum allowed value for the path metric of a 404 selected path. 406 MIN_PATH_COST: The minimum allowed value for the path metric of 407 the selected path. 409 PARENT_SWITCH_THRESHOLD: The difference between the cost of the 410 path through the preferred parent and the minimum cost path in 411 order to trigger the selection of a new preferred parent. 413 PARENT_SET_SIZE: The number of candidate parents, including the 414 preferred parent, in the parent set. 416 ALLOW_FLOATING_ROOT: If set to 1, allows a node to become a 417 floating root. 419 The parameter values are assigned depending on the selected metric. 420 The best values for these parameters should be experimentally 421 determined. The working group has long experience routing with the 422 ETX metric. Based on those experiences, these values are 423 RECOMMENDED: 425 MAX_LINK_METRIC: 10. Disallow links with greater than 10 expected 426 transmission count on the selected path. 428 MAX_PATH_COST: 100. Disallow paths with greater than 100 expected 429 transmission count. 431 MIN_PATH_COST: 0. At root, the expected transmission count is 0. 433 PARENT_SWITCH_THRESHOLD: 172. Switch to a new path only if it is 434 expected to require at least 1.5 fewer transmissions than the 435 current path. As ETX is encoded as number of transmissions times 436 128, this is a threshold of 172. 438 PARENT_SET_SIZE: 3. If the preferred parent is not available, two 439 candidate parents are still available without triggering a new 440 round of route discovery. 442 ALLOW_FLOATING_ROOT: 0. Do not allow a node to become a floating 443 root. 445 6. Manageability 447 Section 18 of [RFC6550] depicts the management of RPL. This 448 specification inherits from that section and its subsections, with 449 the exception that metrics as specified in [RFC6551] are not used and 450 do not require management. 452 6.1. Device Configuration 454 An implementation SHOULD allow the following parameters to be 455 configured at installation time: MAX_LINK_METRIC, MAX_PATH_COST, 456 MIN_PATH_COST, PARENT_SWITCH_THRESHOLD, PARENT_SET_SIZE, and 457 ALLOW_FLOATING_ROOT. An implementation MAY allow these parameters to 458 be configured dynamically at run time once a network has been 459 deployed. 461 A MRHOF implementation SHOULD support the DODAG Configuration option 462 as described in [RFC6550] and apply the parameters it specifies. 464 Care should be taken in the relationship between the MRHOF 465 PARENT_SWITCH_THRESHOLD parameter and the RPL MaxRankIncrease 466 parameter. For example, if MaxRankIncrease is smaller than 467 PARENT_SWITCH_THRESHOLD, a RPL node using MRHOF could enter a 468 situation where its current preferred parent causes the nodes Rank to 469 increase more than MaxRankIncrease but MRHOF does not change 470 preferred parents: this could cause the node to leave the routing 471 topology even though there may be other members of the parent set 472 which would allow the node's Rank to remain within MaxRankIncrease. 474 Unless configured otherwise, a MRHOF implementation SHOULD use the 475 default parameters as specified in Section 5. 477 Because of the partially-coupled relationship between Rank and metric 478 values, networks using MRHOF require care in setting 479 MinHopRankIncrease. A large MinHopRankIncrease will cause MRHOF to 480 be unable to select paths with different hop counts but similar 481 metric values. If MinHopRankIncrease is large enough that its 482 increment is greater than that caused by link cost, then metrics will 483 be used to select a preferred parent but the advertised Rank will be 484 a simple hopcount. This behavior might be desirable, but it also 485 might be unintended: care is recommended. 487 RPL's Rank advertisement rules can require a DODAG Root to advertise 488 a Rank higher than its corresponding ETX value, as a DODAG Root 489 advertises a Rank of MinHopRankIncrease. Because all DODAG Roots 490 within a DODAG Version advertise the same Rank, this constant value 491 typically does not affect route selection. Nevertheless, it means 492 that if a DODAG Version has a MinHopRankIncrease of M and a path has 493 an advertised ETX of E, then the actual ETX of the path is likely 494 closer to a value of E-M than a value of E. 496 6.2. Device Monitoring 498 A MRHOF implementation should provide an interface for monitoring its 499 operation. At a minimum, the information provided should include: 501 DAG information as specified in Section 6.3.1 of [RFC6550], and 502 including the DODAGID, the RPLInstanceID, the Mode of Operation, 503 the Rank of this node, the current Version Number, and the value 504 of the Grounded flag. 506 A list of neighbors indicating the preferred parent. The list 507 should indicate, for each neighbor, the Rank, the current Version 508 Number, the value of the Grounded flag, and associated metrics. 510 7. Acknowledgements 512 Thanks to Antonio Grilo, Nicolas Tsiftes, Matteo Paris, JP Vasseur, 513 and Phoebus Chen for their comments. 515 8. IANA Considerations 517 This specification requires a value allocated from the "Objective 518 Code Point (OCP)" sub-registry of the "Routing Protocol for Low Power 519 and Lossy Networks (RPL)" registry. A value of 1 is suggested. 521 9. Security Considerations 523 This specification makes simple extensions to RPL and so is 524 vulnerable to and benefits from the security issues and mechanisms 525 described in [RFC6550] and [I-D.ietf-roll-security-framework]. This 526 document does not introduce new flows or new messages, thus requires 527 no specific mitigation for new threats. 529 MRHOF depends on information exchanged in a number RPL protocol 530 elements. If those elements were compromised, then an implementation 531 of MRHOF might generate the wrong path for a packet, resulting in it 532 being misrouted. Therefore, deployments are RECOMMENDED to use RPL 533 security mechanisms if there is a risk that routing information might 534 be modified or spoofed. 536 10. References 538 10.1. Normative References 540 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 541 Requirement Levels", BCP 14, RFC 2119, March 1997. 543 [RFC6550] Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R., 544 Levis, P., Pister, K., Struik, R., Vasseur, JP., and R. 545 Alexander, "RPL: IPv6 Routing Protocol for Low-Power and 546 Lossy Networks", RFC 6550, March 2012. 548 [RFC6551] Vasseur, JP., Kim, M., Pister, K., Dejean, N., and D. 549 Barthel, "Routing Metrics Used for Path Calculation in 550 Low-Power and Lossy Networks", RFC 6551, March 2012. 552 10.2. Informative References 554 [I-D.ietf-roll-security-framework] 555 Tsao, T., Alexander, R., Dohler, M., Daza, V., and A. 556 Lozano, "A Security Framework for Routing over Low Power 557 and Lossy Networks", draft-ietf-roll-security-framework-07 558 (work in progress), January 2012. 560 [I-D.ietf-roll-terminology] 561 Vasseur, J., "Terminology in Low power And Lossy 562 Networks", draft-ietf-roll-terminology-05 (work in 563 progress), March 2011. 565 Authors' Addresses 567 Omprakash Gnawali 568 University of Houston 569 PGH 577, University of Houston 570 Houston, TX 77204 571 USA 573 Phone: +1 713 743 3356 574 Email: gnawali@cs.uh.edu 576 Philip Levis 577 Stanford University 578 412 Gates Hall, Stanford University 579 Stanford, CA 94305 580 USA 582 Email: pal@cs.stanford.edu