idnits 2.17.1 draft-ietf-roll-of0-11.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 (May 5, 2011) is 4741 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) == Unused Reference: 'I-D.ietf-roll-routing-metrics' is defined on line 427, but no explicit reference was found in the text == Outdated reference: A later version (-11) exists of draft-ietf-roll-minrank-hysteresis-of-03 == Outdated reference: A later version (-13) exists of draft-ietf-roll-terminology-05 Summary: 0 errors (**), 0 flaws (~~), 4 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 ROLL P. Thubert, Ed. 3 Internet-Draft Cisco Systems 4 Intended status: Standards Track May 5, 2011 5 Expires: November 6, 2011 7 RPL Objective Function 0 8 draft-ietf-roll-of0-11 10 Abstract 12 The Routing Protocol for Low Power and Lossy Networks (RPL) defines a 13 generic Distance Vector protocol that is adapted to such networks. 14 RPL requires a specific Objective Function to establish a desired 15 routing topology. This document specifies a basic Objective Function 16 that relies only on RPL's basic Protocol Data Units; it does not use 17 extensions such as RPL metric containers. 19 Requirements Language 21 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 22 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 23 document are to be interpreted as described in RFC 2119 [RFC2119]. 25 Status of this Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at http://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on November 6, 2011. 42 Copyright Notice 44 Copyright (c) 2011 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (http://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 Table of Contents 59 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 60 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 61 3. Objective Function 0 Overview . . . . . . . . . . . . . . . . 4 62 4. OF0 operations . . . . . . . . . . . . . . . . . . . . . . . . 5 63 4.1. Computing Rank . . . . . . . . . . . . . . . . . . . . . . 5 64 4.2. Feasible successors selection . . . . . . . . . . . . . . 6 65 4.2.1. Selection of the Preferred Parent . . . . . . . . . . 6 66 4.2.2. Selection of the backup feasible successor . . . . . . 7 67 5. Abstract Interface with RPL core . . . . . . . . . . . . . . . 8 68 6. OF0 Operands . . . . . . . . . . . . . . . . . . . . . . . . . 8 69 6.1. Variables . . . . . . . . . . . . . . . . . . . . . . . . 8 70 6.2. Configurable parameters . . . . . . . . . . . . . . . . . 8 71 6.3. Constants . . . . . . . . . . . . . . . . . . . . . . . . 9 72 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 73 8. Security Considerations . . . . . . . . . . . . . . . . . . . 9 74 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9 75 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10 76 10.1. Normative References . . . . . . . . . . . . . . . . . . . 10 77 10.2. Informative References . . . . . . . . . . . . . . . . . . 10 78 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 10 80 1. Introduction 82 The Routing Protocol for Low Power and Lossy Networks 83 [I-D.ietf-roll-rpl] was designed as a generic core that is agnostic 84 to metrics and that is adapted to a given problem using Objective 85 Functions (OF). This separation of Objective Functions from the core 86 protocol specification allows RPL to adapt to meet the different 87 optimization criteria required by the wide range of use cases. 89 RPL forms Destination Oriented Directed Acyclic Graphs (DODAGs) 90 within instances of the protocol. Each instance is associated with a 91 specialized Objective Function. A DODAG is periodically 92 reconstructed in a new Version to enable a global reoptimization of 93 the graph. 95 An Objective Function selects the DODAG Version that a device joins 96 within an instance, and a number of neighbor routers within that 97 DODAG Version as parents or feasible successors. The OF generates 98 the Rank of the device, that represents an abstract distance to the 99 root within the DODAG. In turn, the Rank is used by the generic RPL 100 core to enable a degree of loop avoidance and verify forward 101 progression towards a destination, as specified in 102 [I-D.ietf-roll-rpl]. 104 The Objective Function 0 (OF0) corresponds to the Objective Code 105 Point 0 (OCP0). OF0 only requires the information in the RPL DIO 106 base container, such as Rank and the DODAGPreference field that 107 describes an administrative preference [I-D.ietf-roll-rpl]. The Rank 108 of a node is obtained by adding a normalized scalar, rank_increase, 109 to the Rank of a selected preferred parent. OF0 uses a unit 110 MinHopRankIncrease of rank_increase of 0x100 so that Rank value can 111 be stored in one octet. This allows up to at least 28 hops even when 112 default settings are used and each hop has the worst rank_increase of 113 9. 115 Since there is no default OF or metric container in the RPL main 116 specification, it might happen that, unless two given implementations 117 follow the same guidance for a specific problem or environment, those 118 implementations will not support a common OF with which they could 119 interoperate. OF0 is designed to be common to all implementations 120 that are not specifically designed to apply to a given case for which 121 further guidance is provided. This is why it is very abstract as to 122 how the link properties are transformed into a rank_increase and 123 leaves that responsibility to implementation; rather, OF0 enforces 124 normalized values for the rank_increase of a normal link and its 125 acceptable range, as opposed to formulating the details of its 126 computation. This is also why OF0 ignores metric containers. 128 2. Terminology 130 The terminology used in this document is consistent with and 131 incorporates that described in `Terminology in Low power And Lossy 132 Networks' [I-D.ietf-roll-terminology] and [I-D.ietf-roll-rpl]. 134 The term feasible successor is used to refer to a neighbor that can 135 possibly be used as a next-hop for upwards traffic following the loop 136 avoidance and forwarding rules that the nodes implements and that are 137 defined outside of this specification, in particular in the RPL 138 specification. 140 3. Objective Function 0 Overview 142 The core RPL specification describes constraints on how nodes select 143 potential parents, called a parent set, from their neighbors. All 144 parents are feasible successors for upgoing traffic (towards the 145 root). Additionally, RPL allows the use of parents in a subsequent 146 Version of a same DODAG as feasible successors, in which case this 147 node acts as a leaf in the subsequent DODAG Version. Further 148 specifications might extend the set of feasible successors, for 149 instance to nodes of a same Rank, aka siblings. 151 The Goal of the OF0 is for a node to join a DODAG Version that offers 152 connectivity to a specific set of nodes or to a larger routing 153 infrastructure. For the purpose of OF0, Grounded thus means that the 154 root provides such connectivity. How that connectivity is asserted 155 and maintained is out of scope. 157 Objective Function 0 is designed to find the nearest Grounded root. 158 This can be achieved if the Rank of a node represents closely its 159 distance to the root. This need is balanced with the other need of 160 maintaining some path diversity. In the absence of a Grounded root, 161 LLN inner connectivity is still desirable and floating DAGs will 162 form, rooted at the nodes with the highest administrative preference. 164 OF0 selects a preferred parent and a backup feasible successor if one 165 is available. All the upward traffic is normally routed via the 166 preferred parent. When the link conditions do not let an upward 167 packet through the preferred parent, the packet is passed to the 168 backup feasible successor. 170 OF0 assigns a step_of_rank to each link to another node that it 171 monitors. The exact method for computing the step_of_rank is 172 implementation-dependent. 174 4. OF0 operations 176 4.1. Computing Rank 178 One trivial OF0 implementation might compute the step_of_rank from as 179 a classical administrative cost that is assigned to the link. Using 180 a metric similar to hop count implies that the OF0 implementation 181 only considers neighbors with good enough connectivity, for instance 182 neighbors that are reachable over an Ethernet link, or a WIFI link in 183 infrastructure mode. 185 In most wireless networks, a Rank that is analogous to an unweighted 186 hop count favors paths with long distance links and poor connectivity 187 properties. Other link properties such as the expected transmission 188 count metric (ETX) [DeCouto03] should be used instead to compute the 189 step_of_rank. For instance, the Minimum Rank Objective Function with 190 Hysteresis [I-D.ietf-roll-minrank-hysteresis-of] provides guidance on 191 how link cost can be computed and on how hysteresis can improve Rank 192 stability. 194 An implementation MAY allow to stretch the step_of_rank with a 195 stretch_of_rank up to no more than MAXIMUM_RANK_STRETCH in order to 196 enable the selection of a feasible successor and maintain path 197 diversity. The use of a stretch_of_rank augments the apparent 198 distance from the node to the root and distorts the DODAG; it should 199 be used with care so as to avoid instabilities due to greedy 200 behaviours. 202 The step_of_rank is expressed in units of MINIMUM_STEP_OF_RANK. As a 203 result, the least significant octet in the RPL Rank is not used. The 204 default step_of_rank is DEFAULT_STEP_OF_RANK for each hop. An 205 implementation MUST maintain the stretched step_of_rank between 206 MINIMUM_STEP_OF_RANK and MAXIMUM_STEP_OF_RANK, which allows to 207 reflect a large variation of link quality. 209 The gap between MINIMUM_STEP_OF_RANK and MAXIMUM_RANK_STRETCH may not 210 be sufficient in every case to strongly distinguish links of 211 different types or categories in order to favor, say, powered over 212 battery-operated or wired over wireless, within a same DAG. 214 An implementation SHOULD allow a configurable factor called Rank- 215 factor and to apply the factor on all links and peers. 217 An implementation MAY recognizes sub-categories of peers and links, 218 such as different MAC types, in which case it SHOULD be able to 219 configure a more specific Rank-factor to those categories. The Rank- 220 factor SHOULD be set between MINIMUM_RANK_FACTOR and 221 MAXIMUM_RANK_FACTOR. 223 The step_of_rank Sp that is computed for that link is multiplied by 224 the Rank-factor Rf and then possibly stretched by a stretch_of_rank 225 Sr. The resulting rank_increase Ri is added to the Rank of preferred 226 parent R(P) to obtain that of this node R(N): 228 R(N) = R(P) + Ri where Ri = (Rf*Sp + Sr) * MinHopRankIncrease 230 Optionally, the administrative preference of a root MAY be configured 231 to supersede the goal to join a Grounded DODAG. In that case, nodes 232 will associate to the root with the highest preference available, 233 regardless of whether that root is Grounded or not. Compared to a 234 deployment with a multitude of Grounded roots that would result in a 235 same multitude of DODAGs, such a configuration may result in possibly 236 less but larger DODAGs, as many as roots configured with the highest 237 priority in the reachable vicinity. 239 4.2. Feasible successors selection 241 4.2.1. Selection of the Preferred Parent 243 As it scans all the candidate neighbors, OF0 performs in order the 244 following checks and keeps the parent that is the best for the first 245 criterion that makes a difference: 247 1. [I-D.ietf-roll-rpl] spells out the generic rules for a node to 248 reparent and in particular the boundaries to augment its Rank 249 within a DODAG Version. A candidate that would not satisfy 250 those rules MUST NOT be considered. 252 2. An implementation should validate a router prior to selecting it 253 as preferred. This validation process is implementation and 254 link type dependent, and is out of scope. A router that has 255 been validated is preferable. 257 3. When multiple interfaces are available, a policy might be 258 locally configured to order them and that policy applies first; 259 that is a router on a higher order interface in the policy is 260 preferable. 262 4. If the administrative preference of the root is configured to 263 supersede the goal to join a Grounded DODAG, a router that 264 offers connectivity to a more preferable root SHOULD be 265 preferred. 267 5. A router that offers connectivity to a grounded DODAG Version 268 SHOULD be preferred over one that does not. 270 6. A router that offers connectivity to a more preferable root 271 SHOULD be preferred. 273 7. When comparing 2 routers that belong to the same DODAG, a router 274 that offers connectivity to the freshest DODAG Version SHOULD be 275 preferred. 277 8. The parent that causes the lesser resulting Rank for this node, 278 as specified in Section 4.1, SHOULD be preferred. 280 9. A DODAG Version for which there is an alternate parent SHOULD be 281 preferred. This check is optional. It is performed by 282 computing the backup feasible successor while assuming that the 283 router that is currently examined is finally selected as 284 preferred parent. 286 10. The preferred parent that was in use already SHOULD be 287 preferred. 289 11. A router that has announced a DIO message more recently SHOULD 290 be preferred. 292 4.2.2. Selection of the backup feasible successor 294 When selecting a backup feasible successor, the OF performs in order 295 the following checks: 297 1. When multiple interfaces are available, a router on a higher 298 order interface is preferable. 300 2. The backup feasible successor MUST NOT be the preferred parent. 302 3. The backup feasible successor MUST be either in the same DODAG 303 Version as this node or in an subsequent DODAG Version. 305 4. Along with RPL rules, a Router in the same DODAG Version as this 306 node and with a Rank that is higher than the Rank computed for 307 this node MUST NOT be selected as a feasible successor. 309 5. A router with a lesser Rank SHOULD be preferred. 311 6. A router that has been validated as usable by an implementation 312 dependant validation process SHOULD be preferred. 314 7. The backup feasible successor that was in use already SHOULD be 315 preferred. 317 5. Abstract Interface with RPL core 319 Objective Function 0 interacts with the core RPL in the following 320 ways: 322 Processing DIO: This core RPL triggers the OF when a new DIO was 323 received. OF0 analyses the information in the DIO and may select 324 the source as a parent or sibling. 326 Providing DAG information: The OF is called to provide information 327 about a given instance. This includes material from the DIO base 328 header, the role (router, leaf), and the Rank of this node. 330 Providing a Parent List: The OF0 support can be required to provide 331 the ordered list of the parents and feasible successors for a 332 given instance to the RPL core. This includes the material that 333 is contained in the transit option for each entry. 335 Trigger: The OF0 support may trigger the RPL core to inform it that 336 a change occurred. This can be used to indicate whether the 337 change requires a new DIO to be fired or whether trickle timers 338 need to be reset. 340 6. OF0 Operands 342 6.1. Variables 344 OF0 uses the following variables: 346 step_of_rank (unsigned integer): an intermediate computation based 347 on the link properties with a certain neighbor. 349 rank-increase (unsigned integer): delta between the Rank of the 350 preferred parent and self 352 6.2. Configurable parameters 354 OF0 can use the following optional parameters: 356 stretch_of_rank (unsigned integer): an optional augmentation to the 357 step-of-rank of the preferred parent to allow the selection of 358 additional parents. 360 rank_factor (unsigned integer): A configurable factor that is used 361 to multiply the effect of the link properties in the rank_increase 362 computation. 364 6.3. Constants 366 OF0 fixes the following constants: 368 MinHopRankIncrease: 256 370 DEFAULT_STEP_OF_RANK: 3 372 MINIMUM_STEP_OF_RANK: 1 374 MAXIMUM_STEP_OF_RANK: 9 376 DEFAULT_RANK_STRETCH: 0 378 MAXIMUM_RANK_STRETCH: 5 380 DEFAULT_RANK_FACTOR: 1 382 MINIMUM_RANK_FACTOR: 1 384 MAXIMUM_RANK_FACTOR: 4 386 7. IANA Considerations 388 This specification requires the assignment of an OCP for OF0. The 389 value of 0 is suggested. 391 8. Security Considerations 393 Security Considerations for OCP/OF are to be developed in accordance 394 with recommendations laid out in, for example, 395 [I-D.tsao-roll-security-framework]. 397 9. Acknowledgements 399 Most specific thanks to Philip Levis and Phoebus Chen for their help 400 in finalizing this document. 402 Many thanks also to Tim Winter, JP Vasseur, Julien Abeille, Mathilde 403 Durvy, Teco Boot, Navneet Agarwal and Henning Rogge for in-depth 404 review and first hand implementer's feedback. 406 10. References 407 10.1. Normative References 409 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 410 Requirement Levels", BCP 14, RFC 2119, March 1997. 412 10.2. Informative References 414 [DeCouto03] 415 De Couto, Aguayo, Bicket, and Morris, "A High-Throughput 416 Path Metric for Multi-Hop Wireless Routing", MobiCom 417 '03 The 9th ACM International Conference on Mobile 418 Computing and Networking, San Diego, California,, 2003, . 421 [I-D.ietf-roll-minrank-hysteresis-of] 422 Gnawali, O. and P. Levis, "The Minimum Rank Objective 423 Function with Hysteresis", 424 draft-ietf-roll-minrank-hysteresis-of-03 (work in 425 progress), May 2011. 427 [I-D.ietf-roll-routing-metrics] 428 Vasseur, J., Kim, M., Pister, K., Dejean, N., and D. 429 Barthel, "Routing Metrics used for Path Calculation in Low 430 Power and Lossy Networks", 431 draft-ietf-roll-routing-metrics-19 (work in progress), 432 March 2011. 434 [I-D.ietf-roll-rpl] 435 Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., 436 Kelsey, R., Levis, P., Pister, K., Struik, R., and J. 437 Vasseur, "RPL: IPv6 Routing Protocol for Low power and 438 Lossy Networks", draft-ietf-roll-rpl-19 (work in 439 progress), March 2011. 441 [I-D.ietf-roll-terminology] 442 Vasseur, J., "Terminology in Low power And Lossy 443 Networks", draft-ietf-roll-terminology-05 (work in 444 progress), March 2011. 446 [I-D.tsao-roll-security-framework] 447 Tsao, T., Alexander, R., Daza, V., and A. Lozano, "A 448 Security Framework for Routing over Low Power and Lossy 449 Networks", draft-tsao-roll-security-framework-02 (work in 450 progress), March 2010. 452 Author's Address 454 Pascal Thubert (editor) 455 Cisco Systems 456 Village d'Entreprises Green Side 457 400, Avenue de Roumanille 458 Batiment T3 459 Biot - Sophia Antipolis 06410 460 FRANCE 462 Phone: +33 497 23 26 34 463 Email: pthubert@cisco.com