idnits 2.17.1 draft-ietf-roll-of0-06.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 (March 13, 2011) is 4791 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 (-09) exists of draft-ietf-roll-building-routing-reqs-07 == Outdated reference: A later version (-11) exists of draft-ietf-roll-home-routing-reqs-08 == Outdated reference: A later version (-19) exists of draft-ietf-roll-rpl-18 == Outdated reference: A later version (-13) exists of draft-ietf-roll-terminology-04 Summary: 0 errors (**), 0 flaws (~~), 5 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 March 13, 2011 5 Expires: September 14, 2011 7 RPL Objective Function 0 8 draft-ietf-roll-of0-06 10 Abstract 12 The Routing Protocol for Low Power and Lossy Networks (RPL) defines a 13 generic Distance Vector protocol for Low Power and Lossy Networks 14 (LLNs). RPL is instantiated to honor a particular routing objective/ 15 constraint by the adding a specific Objective Function (OF) that is 16 designed to solve that problem. This specification defines a basic 17 OF, OF0, that uses only the abstract properties exposed in RPL 18 messages with no metric container. 20 Requirements Language 22 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 23 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 24 document are to be interpreted as described in RFC 2119 [RFC2119]. 26 Status of this Memo 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF). Note that other groups may also distribute 33 working documents as Internet-Drafts. The list of current Internet- 34 Drafts is at http://datatracker.ietf.org/drafts/current/. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 This Internet-Draft will expire on September 14, 2011. 43 Copyright Notice 45 Copyright (c) 2011 IETF Trust and the persons identified as the 46 document authors. All rights reserved. 48 This document is subject to BCP 78 and the IETF Trust's Legal 49 Provisions Relating to IETF Documents 50 (http://trustee.ietf.org/license-info) in effect on the date of 51 publication of this document. Please review these documents 52 carefully, as they describe your rights and restrictions with respect 53 to this document. Code Components extracted from this document must 54 include Simplified BSD License text as described in Section 4.e of 55 the Trust Legal Provisions and are provided without warranty as 56 described in the Simplified BSD License. 58 Table of Contents 60 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 61 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 62 3. Goal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 63 4. Selection of the Preferred Parent . . . . . . . . . . . . . . 6 64 5. Selection of the Backup next_hop . . . . . . . . . . . . . . . 7 65 6. Abstract Interface with RPL core . . . . . . . . . . . . . . . 7 66 7. OF0 Constants and Variables . . . . . . . . . . . . . . . . . 8 67 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 68 9. Security Considerations . . . . . . . . . . . . . . . . . . . 9 69 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9 70 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9 71 11.1. Normative References . . . . . . . . . . . . . . . . . . 9 72 11.2. Informative References . . . . . . . . . . . . . . . . . 9 73 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 10 75 1. Introduction 77 The IETF ROLL Working Group has defined application-specific routing 78 requirements for a Low Power and Lossy Network (LLN) routing 79 protocol, specified in [I-D.ietf-roll-building-routing-reqs], 80 [I-D.ietf-roll-home-routing-reqs], [RFC5673], and [RFC5548]. 82 Considering the wide variety of use cases, link types and metrics, 83 the Routing Protocol for Low Power and Lossy Networks 84 [I-D.ietf-roll-rpl] was designed as a generic core that is agnostic 85 to metrics and instantiated using Objective Functions. 87 RPL forms Destination Oriented Directed Acyclic Graphs (DODAGs) 88 within instances of the protocol, each instance being set up to honor 89 a particular routing objective/constraint of a given deployment. 90 This instantiation is achieved by plugging into the RPL core a 91 specific Objective Function (OF) that is designed to solve that 92 problem to be addressed by that instance. 94 An Objective Function selects the DODAG version that a device joins, 95 and a number of neighbor routers within that version as parents and 96 siblings. The OF is also responsible for computing the Rank of the 97 device, that abstracts a relative position within the DODAG and is 98 used by the RPL core to enable a degree of loop avoidance and verify 99 forward progression towards a destination, as specified in 100 [I-D.ietf-roll-rpl]. 102 Since there is no default OF or metric container in the RPL main 103 specification, it might happen that, unless given two implementations 104 follow a same guidance for a specific problem or environment, those 105 implementations will not support a common OF with which they could 106 interoperate. This specification fills the need for an Objective 107 Function that can be used as a common denominator between all generic 108 implementations. This is why OF0 is very abstract as to how the link 109 properties are transformed into a Rank, giving only normalized values 110 for what a normal link and what the acceptable range is for a step of 111 Rank are, as opposed to formulating the details of the step of Rank 112 computation. 114 Indeed, it is the general design in RPL that the metrics are passed 115 from parent to children in a specific container and that the OF will 116 derive the Rank from the natural metric. The separation of Rank and 117 metrics avoids a loss of information as the various metrics are 118 propagated down the DAG. This specification can be used when the 119 link properties that are considered are such that they can be turned 120 in a scalar step of Rank in a reversible fashion and the resulting 121 step of rank is additive over multiple hops. 123 The Objective Function 0 (OF0) corresponds to the Objective Code 124 Point 0 (OCP0). OF0 does not leverage metric containers such as 125 described in the metrics draft [I-D.ietf-roll-routing-metrics]. OF0 126 does not require information in the RPL messages but the abstract 127 information from the DIO base container, such as Rank and an 128 administrative preference, that is transported in DIOs as 129 DODAGPreference in [I-D.ietf-roll-rpl]. The Rank of a node is 130 obtained by adding a step of Rank multiplied by a Rank Factor to the 131 Rank of a selected preferred parent. OF0 uses a MinHopRankIncrease 132 of 0x100 so that Rank value can be stored in one octet. This allows 133 up to at least 28 hops even when each hop has the worst step of Rank 134 of 9 and a Rank Factor of 1. How the link properties are transformed 135 into a step of Rank for a given hop depends on the link type and on 136 the implementation. It can be as simple as an administrative cost, 137 but might also derive from a statistical metric with some hysteresis. 139 2. Terminology 141 The terminology used in this document is consistent with and 142 incorporates that described in `Terminology in Low power And Lossy 143 Networks' [I-D.ietf-roll-terminology] and [I-D.ietf-roll-rpl]. 145 3. Goal 147 The Goal of the OF0 is to join a DODAG version that offers 148 connectivity to a specific set of nodes or to a larger routing 149 infrastructure. For the purpose of OF0, Grounded thus means that the 150 root provides such connectivity. How that connectivity is asserted 151 and maintained is out of scope. 153 Objective Function 0 is designed to find the nearest Grounded root. 154 In the absence of a Grounded root, LLN inner connectivity is still 155 desirable and floating DAGs will form, rooted at the nodes with the 156 highest administrative preference. 158 The metric used in OF0 can be an administratively defined scalar cost 159 that is trivially added up along a path to compute the RPL Rank, as 160 defined in [I-D.ietf-roll-rpl]. Depending on how the step of Rank is 161 computed by an implementation, the Rank of a node might be analogous 162 to a weighted hop count of the path to the root. Using a metric that 163 in essence is similar to hop count implies that the quality of the 164 connectivity should be asserted so that only neighbors with a good 165 enough connectivity are presented to the OF. How that connectivity 166 is asserted and maintained is not covered by this specification. 168 In wireless networks, Hop Count will tend to favor paths with long 169 distance links and non optimal connectivity properties. In some 170 situations, this might end up partitioning the network. As a result, 171 the link selection must be very conservative, and the available link 172 set is thus constrained. For those reasons, though it can be used on 173 wired links and wired link emulations such as WIFI infrastructure 174 mode, a metric derived from hop count is generally not recommended 175 for wireless networks. Instead, careful thinking should be applied 176 to determine how the step of Rank is computed from the link 177 properties and attention should be paid to maintain a certain 178 stability in the resulting Rank. 180 The default step of Rank is DEFAULT_RANK_INCREMENT for each hop. An 181 implementation MAY allow a step between MINIMUM_RANK_INCREMENT and 182 MAXIMUM_RANK_INCREMENT to reflect a large variation of link quality 183 by units of MINIMUM_RANK_INCREMENT. In other words, the least 184 significant octet in the Rank is not used. 186 A node MAY stretch its step of Rank by up to MAXIMUM_RANK_STRETCH in 187 order to enable the selection of a sibling when only one parent is 188 available. For instance, say that a node computes a step of Rank of 189 4 units of MINIMUM_RANK_INCREMENT from a preferred parent with a Rank 190 of 6 units resulting in a Rank of 10 units for this node. Say that 191 with that Rank of 10 units, this node would end up with only one 192 parent and no sibling, though there is a neighbor with a Rank of 12 193 units. In that case, the node is entitled to stretch its step of 194 Rank by a value of 2 units, thus using a step of Rank of 6 units so 195 as to reach a Rank of 12 units and find a sibling. But the node is 196 not entitled to use a step of Rank larger than 6 units since that 197 would be a greedy behavior that would deprive the neighbor of this 198 node of a successor. Also, if the neighbor had exposed a Rank of 16 199 units, the stretch of Rank from 10 to 16 units would have exceeded 200 MAXIMUM_RANK_STRETCH of 5 units and thus the neighbor would not have 201 been selectable even as a sibling. 203 The gap between MINIMUM_RANK_INCREMENT and MAXIMUM_RANK_STRETCH may 204 not be sufficient in every case to strongly distinguish links of 205 different types or categories in order to favor, say, powered over 206 battery-operated or wired over wireless, within a same DAG. An 207 implementation SHOULD allow a configurable factor called Rank Factor 208 and to apply the factor on all links and peers. An implementation 209 MAY recognizes sub-categories of peers and links, such as different 210 MAC types, in which case it SHOULD be able to configure a more 211 specific Rank Factor to those categories. The Rank Factor SHOULD be 212 set between MINIMUM_RANK_FACTOR and MAXIMUM_RANK_FACTOR. Once a step 213 of Rank is computed along the rules specified in this document, the 214 result of the computation is multipled by the Rank Factor and the 215 result is what gets added to the Rank of preferred parent in order to 216 obtain the Rank of this node. 218 Optionally, the administrative preference of a root MAY be configured 219 to supercede the goal to reach Grounded root. In that case, nodes 220 will associate to the root with the highest preference available, 221 regardless of whether that root is Grounded or not. Compared to a 222 deployment with a multitude of Grounded roots that would result in a 223 same multitude of DODAGs, such a configuration may result in possibly 224 less but larger DODAGs, as many as roots configured with the highest 225 priority in the reachable vincinity. 227 OF0 selects a preferred parent and a backup next_hop if one is 228 available. The backup next_hop might be a parent or a sibling. All 229 the traffic is routed via the preferred parent. When the link 230 conditions do not let a packet through the preferred parent, the 231 packet is passed to the backup next_hop. 233 4. Selection of the Preferred Parent 235 As it scans all the candidate neighbors, OF0 keeps the parent that is 236 the best for the following criteria (in order): 238 1. [I-D.ietf-roll-rpl] spells out the generic rules for a node to 239 reparent and in particular the boundaries to augment its Rank 240 within a DODAG version. A candidate that would not satisfy 241 those rules MUST NOT be considered. 243 2. An implementation should validate a router prior to selecting it 244 as preferred. This validation process is implementation and 245 link type dependent, and is out of scope. A router that has 246 been validated is preferrable. 248 3. When multiple interfaces are available, a policy might be 249 locally configured to prioritize them and that policy applies 250 first; that is a router on a higher order interface is 251 preferable. 253 4. In the absence of a Grounded DODAG version, the router with a 254 higher administrative preference SHOULD be preferred. 255 Optionally, this selection applies regardless of whether the 256 DODAG is Grounded or not. 258 5. A router that offers connectivity to a grounded DODAG version 259 SHOULD be preferred over one that does not. 261 6. When comparing 2 routers that belong to the same DODAG, a router 262 that offers connectivity to the freshest sequence SHOULD be 263 preferred. 265 7. When computing a resulting Rank for this node from a parent Rank 266 and a Step of Rank from that parent, the parent that causes the 267 lesser resulting Rank SHOULD be preferred. 269 8. A DODAG version for which there is an alternate parent SHOULD be 270 preferred. This check is optional. It is performed by 271 computing the backup next_hop while assuming that the router 272 that is currently examined is finally selected as preferred 273 parent. 275 9. The DODAG version that was in use already SHOULD be preferred. 277 10. The preferred parent that was in use already SHOULD be 278 preferred. 280 11. A router that has announced a DIO message more recently SHOULD 281 be preferred. 283 5. Selection of the Backup next_hop 285 o When multiple interfaces are available, a router on a higher order 286 interface is preferable. 288 o The backup next_hop MUST NOT be the preferred parent. 290 o The backup next_hop MUST be either in the same DODAG version as 291 the preferred parent or in an subsequent version. 293 o A Router with a Rank that is higher than the Rank computed for 294 this node out of the preferred parent SHOULD NOT be selected as 295 parent, to avoid greedy behaviors. It MAY still be selected as 296 sibling if no better Back-up next hop is found. 298 o A router with a lesser Rank SHOULD be preferred. 300 o A router that has been validated as usable by an implementation 301 dependant validation process SHOULD be preferred. 303 o The backup next_hop that was in use already SHOULD be preferred. 305 6. Abstract Interface with RPL core 307 Objective Function 0 interacts with the core RPL in the following 308 ways: 310 Processing DIO: This core RPL triggers the OF when a new DIO was 311 received. OF0 analyses the information in the DIO and may 312 select the source as a parent or sibling. 314 Providing DAG information The OF0 support can be required to provide 315 the DAG information for a given instance to the RPL core. 316 This includes the material that is contained in a DIO base 317 header. 319 Providing a Parent List The OF0 support can be required to provide 320 the list of the parents for a given instance to the RPL 321 core. This includes the material that is contained in the 322 transit option for that parent. 324 Trigger The OF0 support may trigger the RPL core to inform it that 325 a change occurred. This can be used to indicate whether 326 the change requires a new DIO to be fired or whether 327 trickle timers need to be reset. 329 7. OF0 Constants and Variables 331 OF0 uses the following constants: 333 MinHopRankIncrease: 256 335 DEFAULT_RANK_INCREMENT: 3 * MinHopRankIncrease 337 MINIMUM_RANK_INCREMENT: 1 * MinHopRankIncrease 339 MAXIMUM_RANK_INCREMENT: 9 * MinHopRankIncrease 341 MAXIMUM_RANK_STRETCH: 5 * MinHopRankIncrease 343 DEFAULT_RANK_FACTOR: 1 345 MINIMUM_RANK_FACTOR: 1 347 MAXIMUM_RANK_FACTOR: 4 349 8. IANA Considerations 351 IThis specification requires the assignment of an OCP for OF0. The 352 value of 0 is suggested. 354 9. Security Considerations 356 Security Considerations for OCP/OF are to be developed in accordance 357 with recommendations laid out in, for example, 358 [I-D.tsao-roll-security-framework]. 360 10. Acknowledgements 362 Most specific thanks to Philip Levis for his help in finalizing this 363 document, in particular WRT wireless links, to Tim Winter, JP 364 Vasseur, Julien Abeille, Mathilde Durvy, Teco Boot, Navneet Agarwal 365 and Henning Rogge for in-depth review and first hand implementer's 366 feedback. 368 11. References 370 11.1. Normative References 372 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 373 Requirement Levels", BCP 14, RFC 2119, March 1997. 375 11.2. Informative References 377 [I-D.ietf-roll-building-routing-reqs] 378 Martocci, J., Riou, N., Mil, P., and W. Vermeylen, 379 "Building Automation Routing Requirements in Low Power and 380 Lossy Networks", draft-ietf-roll-building-routing-reqs-07 381 (work in progress), September 2009. 383 [I-D.ietf-roll-home-routing-reqs] 384 Brandt, A., Buron, J., and G. Porcu, "Home Automation 385 Routing Requirements in Low Power and Lossy Networks", 386 draft-ietf-roll-home-routing-reqs-08 (work in progress), 387 September 2009. 389 [I-D.ietf-roll-routing-metrics] 390 Vasseur, J., Kim, M., Pister, K., Dejean, N., and D. 391 Barthel, "Routing Metrics used for Path Calculation in Low 392 Power and Lossy Networks", 393 draft-ietf-roll-routing-metrics-19 (work in progress), 394 March 2011. 396 [I-D.ietf-roll-rpl] 397 Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., 398 Kelsey, R., Levis, P., Pister, K., Struik, R., and J. 399 Vasseur, "RPL: IPv6 Routing Protocol for Low power and 400 Lossy Networks", draft-ietf-roll-rpl-18 (work in 401 progress), February 2011. 403 [I-D.ietf-roll-terminology] 404 Vasseur, J., "Terminology in Low power And Lossy 405 Networks", draft-ietf-roll-terminology-04 (work in 406 progress), September 2010. 408 [I-D.tsao-roll-security-framework] 409 Tsao, T., Alexander, R., Daza, V., and A. Lozano, "A 410 Security Framework for Routing over Low Power and Lossy 411 Networks", draft-tsao-roll-security-framework-02 (work in 412 progress), March 2010. 414 [RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel, 415 "Routing Requirements for Urban Low-Power and Lossy 416 Networks", RFC 5548, May 2009. 418 [RFC5673] Pister, K., Thubert, P., Dwars, S., and T. Phinney, 419 "Industrial Routing Requirements in Low-Power and Lossy 420 Networks", RFC 5673, October 2009. 422 Author's Address 424 Pascal Thubert (editor) 425 Cisco Systems 426 Village d'Entreprises Green Side 427 400, Avenue de Roumanille 428 Batiment T3 429 Biot - Sophia Antipolis 06410 430 FRANCE 432 Phone: +33 497 23 26 34 433 Email: pthubert@cisco.com