idnits 2.17.1 draft-ietf-roll-minrank-hysteresis-of-03.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 03, 2011) is 4739 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: November 4, 2011 May 03, 2011 7 The Minimum Rank Objective Function with Hysteresis 8 draft-ietf-roll-minrank-hysteresis-of-03 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 4, 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 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9 73 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 74 8. Security Considerations . . . . . . . . . . . . . . . . . . . 9 75 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9 76 9.1. Normative References . . . . . . . . . . . . . . . . . . . 9 77 9.2. Informative References . . . . . . . . . . . . . . . . . . 9 78 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10 80 1. Introduction 82 An objective function specifies how RPL [I-D.ietf-roll-rpl] selects 83 paths. Objective functions can choose paths based on routing metrics 84 or constraints. For example, if an RPL instance uses an objective 85 function that minimizes hop-count, RPL will select paths with minimum 86 hop count. 88 The nodes running RPL might use a number of metrics to describe a 89 link or a node [I-D.ietf-roll-routing-metrics] and make it available 90 for route selection. These metrics are advertised in RPL Destination 91 Information Object (DIO) messages using a Metric Container suboption. 92 An 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. An objective function is responsible for 98 computing a node's advertised Rank value based on the Rank of its 99 potential parents, metrics, and other network properties. 101 This specification describes MRHOF, an objective function for RPL. 102 MRHOF uses hysteresis while selecting the path with the smallest 103 metric value. The metric that MRHOF uses is determined by the 104 metrics in the DIO Metric Container. For example, the use of MRHOF 105 with the latency metric allows RPL to find stable minimum-latency 106 paths from the nodes to a root in the DAG instance. The use of MRHOF 107 with the ETX metric allows RPL to find the stable minimum-ETX paths 108 from the nodes to a root in the DAG instance. 110 MRHOF can only be used with an additive metric that must be minimized 111 on the paths selected for routing. 113 2. Terminology 115 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 116 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 117 "OPTIONAL" in this document are to be interpreted as described in RFC 118 2119 [RFC2119]. 120 This terminology used in this document is consistent with the 121 terminologies described in [I-D.ietf-roll-terminology], 122 [I-D.ietf-roll-rpl], and [I-D.ietf-roll-routing-metrics]. 124 This document introduces two terms: 126 Selected metric: The metric chosen by the network operator to use 127 for path selection. This metric can be any additive metric 128 listed in [I-D.ietf-roll-routing-metrics]. 130 Path cost: Path cost quantifies a property of an end-to-end path. 131 Path cost is obtained by summing up the selected metric of the 132 links or nodes along the path. Path cost can be used by RPL to 133 compare different paths. 135 Worst parent: The node in the parent set with the largest path cost. 137 3. The Minimum Rank Objective Function with Hysteresis 139 The Minimum Rank Objective Function with Hysteresis, MRHOF, is 140 designed to find the paths with the smallest path cost while 141 preventing excessive churn in the network. It does so by finding the 142 minimum cost path and switching to that path only if it is shorter 143 (in terms of path cost) than the current path by at least a given 144 threshold. MRHOF may be used with any additive metric listed in 145 [I-D.ietf-roll-routing-metrics] as long the routing objective is to 146 minimize the given routing metric. 148 3.1. Computing the Path cost 150 Nodes compute the path cost for each candidate neighbor reachable on 151 an interface. The Path cost represents the cost of the path, in 152 terms of the selected metric, from a node to the root of the DODAG 153 through the neighbor. 155 Root nodes (Grounded or Floating) set the variable cur_min_path_cost 156 to MIN_PATH_COST. 158 A non-root node computes the path cost for a path to the root through 159 each candidate neighbor by adding these two components: 161 1. If the selected metric is a link metric, the selected metric for 162 the link to a candidate neighbor. If the selected metric is a 163 node metric, the selected metric for the node. 165 2. The value of the selected metric in the metric container in the 166 DIO sent by that neighbor. 168 A node SHOULD compute the path cost for the path through each 169 candidate neighbor reachable through an interface. If a node cannot 170 compute the path cost for the path through a candidate neighbor, the 171 node MUST NOT select the candidate neighbor as its preferred parent, 172 with one exception. If the node does not have metrics to compute the 173 path cost through any of the candidate neighbors, it MUST join one of 174 the candidate neighbors as a leaf node. 176 If the selected metric is a link metric and the metric of the link to 177 a neighbor is not available, the path cost for the path through that 178 neighbor SHOULD be set to MAX_PATH_COST. This cost value will 179 prevent this path from being considered for path selection. 181 If the selected metric is a node metric, and the metric is not 182 available, the path cost through all the neighbors SHOULD be set to 183 MAX_PATH_COST. 185 The path cost corresponding to a neighbor SHOULD be re-computed each 186 time: 188 1. The selected metric of the link to the candidate neighbor is 189 updated. 191 2. If the selected metric is a node metric and the metric is 192 updated. 194 3. A node receives a new metric advertisement from the candidate 195 neighbor. 197 This computation MAY also be performed periodically. Too much delay 198 in updating the path cost after the metric is updated or a new metric 199 advertisement is received can lead to stale Rank or parent set. 201 3.2. Parent Selection 203 After computing the path cost for all the candidate neighbors 204 reachable through an interface for the current DODAG iteration, a 205 node selects the preferred parent. This process is called parent 206 selection. Parent Selection SHOULD be performed each time: 208 1. The path cost for an existing candidate neighbor, including the 209 preferred parent, changes. This condition can be checked 210 immediately after the path cost is computed. 212 2. A new candidate neighbor is inserted into the neighbor table. 214 The parent selection MAY be deferred until a later time. Deferring 215 the parent selection can delay the use of better paths available in 216 the network. 218 A node MUST select a candidate neighbor as its preferred parent if 219 the path cost corresponding to that neighbor is smaller than the path 220 cost corresponding to the rest of the neighbors, except as indicated 221 below: 223 1. If the smallest path cost for paths through the candidate 224 neighbors is smaller than cur_min_path_cost by less than 225 PARENT_SWITCH_THRESHOLD, the node MAY continue to use the current 226 preferred parent. 228 2. If there are multiple paths with the smallest path cost and the 229 smallest path cost is smaller than cur_min_path_cost by at least 230 PARENT_SWITCH_THRESHOLD, a node MAY use a different objective 231 function to select the preferred parent among the candidate 232 neighbors on the path with the minimum cost. 234 3. A node MAY declare itself as a Floating root, and hence no 235 preferred parent, depending on the configuration. 237 4. If the selected metric for a link is greater than 238 MAX_LINK_METRIC, the node SHOULD exclude that link from 239 consideration for parent selection. 241 5. If cur_min_path_cost is greater than MAX_PATH_COST, the node MAY 242 declare itself as a Floating root. 244 6. If the configuration disallows a node to be a Floating root and 245 no neighbors are discovered, the node does not have a preferred 246 parent, and MUST set cur_min_path_cost to MAX_PATH_COST. 248 Except in the cases above, the candidate neighbor on the path with 249 the smallest path cost is the preferred parent. A node MAY include a 250 total of PARENT_SET_SIZE candidate neighbors in the parent set. The 251 cost of path through the nodes in the parent set is smaller than or 252 equal to the cost of the paths through any of the nodes that are not 253 in the parent set. If the cost of the path through the preferred 254 parent and the worst parent is too large, a node MAY keep a smaller 255 parent set. 257 3.3. Computing Rank 259 The DAG roots set their rank to MIN_PATH_COST for the selected 260 metric. 262 Once a non-root node selects its parent set, it can use the following 263 table to covert the the path cost of the worst parent (written as 264 Cost in the table) to its rank: 266 +--------------------+------------+ 267 | Node/link Metric | Rank | 268 +--------------------+------------+ 269 | Node Energy | 255 - Cost | 270 | Hop-Count | Cost | 271 | Latency | Cost/65536 | 272 | Link Quality Level | Cost | 273 | ETX | Cost | 274 +--------------------+------------+ 276 Table 1: Conversion of metric to rank. 278 Nodes MUST support at least one of the above metrics. Nodes SHOULD 279 support the ETX metric. 281 Node rank is undefined for these node/link metrics: Node state and 282 attributes, throughput, and link color. If the rank is undefined, 283 the node MUST join one of the neighbors as a leaf node. 285 3.4. Advertising the Path Cost 287 Once the preferred parent is selected, the node sets its 288 cur_min_path_cost variable to the path cost corresponding to the 289 preferred parent. Thus, cur_min_path_cost is the cost of the minimum 290 cost path from the node to the root. The value of the 291 cur_min_path_cost is carried in the metric container corresponding to 292 the selected metric when DIO messages are sent. 294 3.5. Working Without Metric Containers 296 In the absence of metric container, MRHOF uses ETX as its metric. It 297 locally computes the ETX of links to its neighbors and adds this 298 value to their advertised Rank to compute the associated Rank of 299 routes. Once parent selection and rank computation is performed 300 using the ETX metric, the node advertises a Rank equal to the ETX 301 cost and SHOULD NOT include a metric container in its DIO messages. 303 4. Using MRHOF for Metric Maximization 305 MRHOF cannot be directly used for parent selection using metrics 306 which require finding paths with maximum value of the selected 307 metric, such as path reliability. It is possible to convert such a 308 metric maximization problem to a metric minimization problem and use 309 MRHOF provided: 311 There is a fixed and well-known maximum metric value corresponding 312 to the best path. This is the path cost for the DAG root. 313 Example, the best link reliability has a value of 1. 315 Metrics are all positive. Example, link reliability is always 316 positive. 318 For metrics meeting the above conditions, the problem of maximizing 319 the metric value is equivalent to minimizing the negative of the 320 metric value. MRHOF is not required to work with these metrics. 322 5. MRHOF Variables and Parameters 324 MRHOF uses the following variable: 326 cur_min_path_cost: The cost of the path from a node through its 327 preferred parent to the root computed at the last parent 328 selection. 330 MRHOF uses the following parameters: 332 MAX_LINK_METRIC: Maximum allowed value for the selected link 333 metric for each link on the path. 335 MAX_PATH_COST: Maximum allowed value for the path metric of a 336 selected path. 338 MIN_PATH_COST: The minimum allowed value for the path metric of 339 the selected path. 341 PARENT_SWITCH_THRESHOLD: The difference between metric of the path 342 through the preferred parent and the minimum-metric path in order 343 to trigger the selection of a new preferred parent. 345 PARENT_SET_SIZE: The number of candidate parents, including the 346 preferred parent, in the parent set. 348 The parameter values are assigned depending on the selected metric. 349 The best values for these parameters should be experimentally 350 determined. The working group has long experience routing with the 351 ETX metric. Based on those experiences, these ETX parameters are 352 known to work in many settings: 354 MAX_LINK_METRIC: 10. Disallow links with greater than 10 expected 355 transmission count on the selected path. 357 MAX_PATH_COST: 100. Disallow paths with greater than 100 expected 358 transmission count. 360 MIN_PATH_COST: 0. At root, the expected transmission count is 0. 362 PARENT_SWITCH_THRESHOLD: 1.5. Switch to a new path only if it is 363 expected to require at least 1.5 fewer transmission than the 364 current path. 366 PARENT_SET_SIZE: 3. If the preferred parent is not available, two 367 candidate parents are still available without triggering a new 368 round of route discovery. 370 6. Acknowledgements 372 Thanks to Antonio Grilo, Nicolas Tsiftes, Matteo Paris, JP Vasseur, 373 and Phoebus Chen for their comments. 375 7. IANA Considerations 377 This specification requires an allocated OCP. A value of 1 is 378 requested. 380 8. Security Considerations 382 Security considerations to be developed in accordance to the output 383 of the WG. 385 9. References 387 9.1. Normative References 389 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 390 Requirement Levels", BCP 14, RFC 2119, March 1997. 392 9.2. Informative References 394 [I-D.ietf-roll-routing-metrics] 395 Vasseur, J. and D. Networks, "Routing Metrics used for 396 Path Calculation in Low Power and Lossy Networks", 397 draft-ietf-roll-routing-metrics-01 (work in progress), 398 October 2009. 400 [I-D.ietf-roll-rpl] 401 Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing 402 Protocol for Low power and Lossy Networks", 403 draft-ietf-roll-rpl-05 (work in progress), December 2009. 405 [I-D.ietf-roll-terminology] 406 Vasseur, J., "Terminology in Low power And Lossy 407 Networks", draft-ietf-roll-terminology-01 (work in 408 progress), May 2009. 410 Authors' Addresses 412 Omprakash Gnawali 413 Stanford University 414 S255 Clark Center, 318 Campus Drive 415 Stanford, CA 94305 416 USA 418 Phone: +1 650 725 6086 419 Email: gnawali@cs.stanford.edu 421 Philip Levis 422 Stanford University 423 358 Gates Hall, Stanford University 424 Stanford, CA 94305 425 USA 427 Email: pal@cs.stanford.edu