idnits 2.17.00 (12 Aug 2021) /tmp/idnits36509/draft-thubert-roll-fundamentals-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.ii or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. 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 : ---------------------------------------------------------------------------- ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 317: '... the LLN Routers MUST obey the followi...' RFC 2119 keyword, line 339: '...dy part of a tree MAY move at any time...' RFC 2119 keyword, line 342: '... LLN Router MUST NOT move down th...' RFC 2119 keyword, line 343: '... LLN Routers MUST ignore RAs that ...' RFC 2119 keyword, line 426: '...following values MUST not change durin...' (15 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: The following values MUST not change during the propagation of the TIO down the tree: G, Tree Delay and Tree ID. All other fields are updated at each hop of the propagation. -- The document date (March 31, 2009) is 4799 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) ** Obsolete normative reference: RFC 2460 (Obsoleted by RFC 8200) == Outdated reference: A later version (-26) exists of draft-ietf-manet-dymo-17 == Outdated reference: draft-ietf-roll-building-routing-reqs has been published as RFC 5867 == Outdated reference: draft-ietf-roll-home-routing-reqs has been published as RFC 5826 == Outdated reference: draft-ietf-roll-indus-routing-reqs has been published as RFC 5673 == Outdated reference: draft-ietf-roll-terminology has been published as RFC 7102 == Outdated reference: draft-ietf-roll-urban-routing-reqs has been published as RFC 5548 -- Obsolete informational reference (is this intentional?): RFC 2740 (Obsoleted by RFC 5340) -- Obsolete informational reference (is this intentional?): RFC 3775 (Obsoleted by RFC 6275) Summary: 3 errors (**), 0 flaws (~~), 8 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 ROLL Working Group P. Thubert 3 Internet-Draft Cisco 4 Intended status: Standards Track T. Watteyne 5 Expires: October 2, 2009 UC Berkeley 6 Z. Shelby 7 Sensinode 8 D. Barthel 9 Orange Labs 10 March 31, 2009 12 LLN Routing Fundamentals 13 draft-thubert-roll-fundamentals-00 15 Status of this Memo 17 This Internet-Draft is submitted to IETF in full conformance with the 18 provisions of BCP 78 and BCP 79. 20 Internet-Drafts are working documents of the Internet Engineering 21 Task Force (IETF), its areas, and its working groups. Note that 22 other groups may also distribute working documents as Internet- 23 Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six months 26 and may be updated, replaced, or obsoleted by other documents at any 27 time. It is inappropriate to use Internet-Drafts as reference 28 material or to cite them other than as "work in progress." 30 The list of current Internet-Drafts can be accessed at 31 http://www.ietf.org/ietf/1id-abstracts.txt. 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html. 36 This Internet-Draft will expire on October 2, 2009. 38 Copyright Notice 40 Copyright (c) 2009 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents in effect on the date of 45 publication of this document (http://trustee.ietf.org/license-info). 46 Please review these documents carefully, as they describe your rights 47 and restrictions with respect to this document. 49 Abstract 51 This document describes a basic set of fundamental mechanisms for 52 routing on a Low-power and Lossy Network (LLN). It does not intend 53 to specify a full-blown protocol. It is rather offered as a basis to 54 support the discussion while designing the ROLL protocol. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 59 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 5 60 1.2. Needs . . . . . . . . . . . . . . . . . . . . . . . . . . 6 61 2. Tree Discovery . . . . . . . . . . . . . . . . . . . . . . . . 7 62 2.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 8 63 2.2. Discovery Information . . . . . . . . . . . . . . . . . . 9 64 2.3. Tree Selection . . . . . . . . . . . . . . . . . . . . . . 11 65 2.4. States . . . . . . . . . . . . . . . . . . . . . . . . . . 11 66 2.5. Stability . . . . . . . . . . . . . . . . . . . . . . . . 12 67 3. Route Dissemination . . . . . . . . . . . . . . . . . . . . . 12 68 3.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 12 69 3.2. Disseminated Information . . . . . . . . . . . . . . . . . 14 70 3.3. LLN Router Operation . . . . . . . . . . . . . . . . . . . 15 71 4. Forwarding . . . . . . . . . . . . . . . . . . . . . . . . . . 19 72 4.1. Upstream Forwarding . . . . . . . . . . . . . . . . . . . 19 73 4.2. Downstream Forwarding . . . . . . . . . . . . . . . . . . 21 74 5. Multicast Support . . . . . . . . . . . . . . . . . . . . . . 22 75 5.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 22 76 5.2. Receiver Flow . . . . . . . . . . . . . . . . . . . . . . 22 77 5.3. Source flow . . . . . . . . . . . . . . . . . . . . . . . 23 78 6. Advanced Features . . . . . . . . . . . . . . . . . . . . . . 23 79 6.1. Interaction with other routing protocols . . . . . . . . . 23 80 6.1.1. AODV/DYMO . . . . . . . . . . . . . . . . . . . . . . 23 81 6.1.2. OSPF/OLSR . . . . . . . . . . . . . . . . . . . . . . 24 82 6.1.3. MIP6/NEMO . . . . . . . . . . . . . . . . . . . . . . 25 83 6.2. Route Optimization . . . . . . . . . . . . . . . . . . . . 25 84 6.2.1. Node-to-node routing . . . . . . . . . . . . . . . . . 25 85 6.2.2. Offline Path Computation . . . . . . . . . . . . . . . 25 86 6.2.3. Graph forwarding . . . . . . . . . . . . . . . . . . . 26 87 6.3. Density . . . . . . . . . . . . . . . . . . . . . . . . . 27 88 6.4. Digraph Dissemination . . . . . . . . . . . . . . . . . . 28 89 6.5. Multiple LBRs and Trees . . . . . . . . . . . . . . . . . 28 90 6.6. Aggregation for Route Dissemination . . . . . . . . . . . 28 91 6.7. Advanced Forwarding . . . . . . . . . . . . . . . . . . . 29 92 7. Security Considerations . . . . . . . . . . . . . . . . . . . 29 93 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 30 94 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 30 95 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 30 96 10.1. Normative References . . . . . . . . . . . . . . . . . . . 30 97 10.2. Informative References . . . . . . . . . . . . . . . . . . 30 98 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 32 100 1. Introduction 102 This document describes a basic set of fundamental mechanisms for 103 routing on a Low-power and Lossy Network (LLN) appropriate for 104 scenarios identified by the ROLL working group. It does not intend 105 to specify a full-blown protocol. It is rather offered as a basis to 106 support the discussion while designing the ROLL protocol. The 107 fundamental mechanisms proposed stem from our analysis that current 108 academic, industrial and IETF protocols suitable to ROLL scenarios 109 are reduceable to those basic mechanisms. 111 Those mechanisms provide a core set of functionality that can be 112 complemented by specific extensions to implement the needs expressed 113 in the ROLL routing requirement drafts: 115 o Urban WSNs Routing Requirements in Low Power and Lossy Networks 116 [I-D.ietf-roll-urban-routing-reqs] 118 o Building Automation Routing Requirements in Low Power and Lossy 119 Networks [I-D.ietf-roll-building-routing-reqs] 121 o Home Automation Routing Requirements in Low Power and Lossy 122 Networks [I-D.ietf-roll-home-routing-reqs] 124 o Industrial Routing Requirements in Low Power and Lossy Networks 125 [I-D.ietf-roll-indus-routing-reqs] 127 The constraints expressed in the routing requirement documents (such 128 as on node memory and communication cost) narrow the choice of 129 fundamental mechanisms down to very simple ones. 131 Due to the highly directed flows in LLNs, a tree structure comes 132 naturally to mind as a bare minimum. In a slightly more elaborate 133 mechanism, we propose that each router memorizes a few best neighbor 134 routers (not only among its parents up the tree, but also among its 135 siblings), to choose from (using some routing metric) when routing 136 towards LLN Border Routers (LBR). However, to reduce complexity, we 137 propose that only the best parent be used for routing advertisements 138 up the structure towards the LBRs, giving each of them a simple tree 139 representation to be used to route downstream traffic or to make 140 other global decisions. Since links and nodes are expected to come 141 and go over time, mechanisms for tree reorganization are described. 142 However, on a shorter time scale, transient link failures are bound 143 to happen. In such a case, we recommend that the link-layer passes 144 packets back to the network layer for re-routing along alternate 145 paths. 147 In terms of routing, the basic fundamental methods include uni/ 148 anycast routing up the graph and unicast routing down the tree 149 (either hop-by-hop or source-based). The best neighbor selection 150 mechanism is left to the protocol design phase. We even suggest that 151 it be left as a plug-in for future evolution. However, a set of 152 basic tree discovery and forwarding rules, described here, prevents 153 loops from forming, in most cases, whatever the routing algorithm 154 eventually implemented. 156 More advanced mechanisms which can be built upon the fundamental 157 mechanisms are also described. They include route optimizations, 158 dissemination of a digraph, dissemination and maintenance of multiple 159 overlapping trees, prefix aggregation and advanced forwarding rules. 161 This document is organized as follows: 163 Section 1.1 defines the terminology used in this document. 165 Section 2 concentrates on the basic tree discovery and maintenance 166 mechanism. 168 Section 3 introduces the basic distance-vector route dissemination 169 mechanism. 171 Section 4 describes the upstream and downstream forwarding rules. 173 Section 5 describes multicast support. 175 Section 6 describes advanced mechanisms which can be built upon 176 these fundamentals. 178 1.1. Terminology 180 The terminology used in this document is consistent with and 181 incorporates that described in [I-D.ietf-roll-terminology]. This 182 terminology is extended in this document as follows: 184 Discovery: a mechanism by which a logical representation of the 185 network is built. 187 Router: a network node that is capable of forwarding packets on 188 behalf of other nodes. In ROLL routing requirement documents, it 189 appears that most nodes are expected to be routers. 191 Default Router: the router to turn to when a node has no information 192 on where to forward a packet 194 Route Dissemination: the action of establishing state within the 195 network so that routers know how to route packets related to some 196 source-destination pairs. 198 Graph: a set of vertices and edges to represent a network of nodes 199 and links. A Directed Acyclic Graph (DAG) is a graph with 200 directional edges where no loop is formed. 202 Tree: a simple form of graph in which there is only one possible 203 route from any node to a specific node called the root. An LLN is 204 said to be Grounded if it is connected to a high-capacity backbone 205 or link to a network such as the Internet. By contrast, an LLN is 206 said to be Floating if it is not grounded. 208 Tree Depth: the maximum number of edges that need to be traversed 209 from any tree node to the root. 211 Uniform Path Metric: A scalar measure for the quality of the bi- 212 directional path between the LLN Router and the root. 214 1.2. Needs 216 The ROLL working group has identified typical scenarios and their 217 related requirements for LLN routing. The main requirements on any 218 fundamental mechanisms used for achieving the ROLL protocol can be 219 summarized as follows: 221 o Support for operation in both full IPv6 [RFC2460] and minimal 222 6LoWPAN [RFC4944] networks. 224 o Optimized for traffic directed between nodes and LBRs. 226 o The use of multiple default routers whenever possible. 228 o Support for multiple LBRs out of the LLN. 230 o Minimal network state needed by routers, with a hard bound better 231 than O(D). 233 o Support for complex unicast, anycast and multicast flows. 235 o Localized response upon link failures without requiring global 236 updates. 238 o Minimal control overhead scaling within O(log(L)) of the data 239 rate. 241 o Support for link and node costs along routes. 243 2. Tree Discovery 245 A tree is the simplest and most basic acyclic graph structure. Even 246 if it is not sufficient to ensure by itself the multipath forwarding 247 proposed below, a tree provides the ideal structure for best path 248 routing between source and sink in a convergecast. 250 In many occasions, LLNs do not have a clear and stable physical 251 structure and it becomes necessary to overlay a logical 252 representation to define links and enable IPv6 operations. LLN Tree 253 Discovery is the component of the LLN fundamentals that builds and 254 maintains logical tree structures over the LLN. 256 The nodes in the LLN discovery tree are Routers; the root is an 257 arbitrary elected Router if the network is isolated; it is the LLN 258 Border Router (LBR) if the LLN is connected to the infrastructure via 259 a backhaul link. A federating backbone such as an extended LoWPAN 260 backbone is the virtual root of the federated tree. In that case, 261 the LBRs are attached at a depth of one and are in charge of 262 performing the root operations on behalf of that virtual root. 264 A tree is identified by a Tree ID which can take the form of an IPv6 265 address: in the case of a LoWPAN configuration with a backbone, the 266 LoWPAN prefix is used as the Tree ID. In the case of an isolated 267 network, that will be an address of the root. 269 This section describes 271 1. a minimum extension to IPv6 Neighbor Discovery Router 272 Advertisements in order to ensure that LLN Routers organize in a 273 tree structure, and 275 2. a minimum common algorithmic part that all LLN Routers are 276 required to implement in order to ensure that, whatever their 277 individual routing decisions, routing loops between LLN Routers 278 are avoided and a basic optimization is achieved. 280 LLN Discovery is based on an autonomous decision by each Router with 281 no global state convergence such as traditionally found in IGPs. In 282 order to enable backward compatibility and interoperability, LLN 283 Discovery allows Routers to make different decisions from identical 284 inputs, based on their own configuration and their own algorithms, 285 though it is highly preferable that the decision algorithm be 286 consistent in a given deployment to achieve the specific goals of 287 that deployment. 289 The signalling mechanism that is used to form the trees is an 290 extension to the ICMP Router Advertisement (RA) message, namely the 291 Tree Information Option (TIO). The TIO allows LLN Routers to 292 advertise the tree they belong to, and to select and move to the best 293 location within the available trees. LLN Routers propagate the TIO 294 in RA messages down the tree, updating some metrics such as the Tree 295 Depth, leaving other information such as the Tree ID unchanged, and 296 resending the result in its own RAs. This is compatible with RA 297 period reduction techniques such as the use of Trickle. 299 2.1. Overview 301 LLN Tree Discovery is a form of distance vector protocol for use in 302 wireless meshed networks. Tree Discovery locates the nearest exit 303 and forms Directed Graphs towards that exit, composed of a best path 304 tree and alternate forwarding options. 306 By introducing the concept of routing plug-ins, LLN Tree Discovery 307 enables LLN Routers to implement different policies for selecting 308 their preferred parent in the Tree. Tree Discovery does not specify 309 the plug-in operation, but rather specifies a set of rules to be 310 implemented by all plug-ins to ensure interoperability. 312 The Tree Depth is the underlying criterion that garantees loop-free 313 operations even if plug-ins implement different policies, and even if 314 these policies do not use Depth as a routing metric. 316 In order to organize and maintain a loopfree structure, the parent 317 selection plug-ins in the LLN Routers MUST obey the following rules 318 and definitions: 320 1. An LLN Router that is not attached to a parent Router is the root 321 of its own floating tree. Its depth is zero. An LLN Router that 322 looses its current parent and has no alternate parent that it can 323 attach to also adopts a depth of zero, but remembers the Tree ID 324 and the sequence counter in the TIO of the lost parent for a 325 period of time which covers multiple TIOs. 327 2. An LLN Border Router that is attached to a federating backbone 328 acts as root and advertises a depth of one. An LBR that is not 329 attached to a federating backbone is a root and exposes a depth 330 of zero. 332 3. A router sending an RA without TIO is considered a grounded 333 parent Router at depth 0. 335 4. The root of a tree exposes the tree in the Router Advertisement 336 (RA) Tree Information Option (TIO) and LLN Routers propagate the 337 TIO down. 339 5. An LLN Router that is already part of a tree MAY move at any time 340 and with no delay in order to get closer to the root of its 341 current tree, i.e. in order to reduce its own tree depth. But an 342 LLN Router MUST NOT move down the tree that it is attached to. 343 LLN Routers MUST ignore RAs that are received from other routers 344 located deeper within the same tree. 346 6. A LLN Router may move from its current tree into any different 347 tree at any time and whatever the depth it reaches in the new 348 tree but, before it can do so, it may have to wait for a Tree Hop 349 Timer to elapse. If the router was root of its own floating 350 tree, it may join its previous tree (identified by the last 351 parent Tree ID) only if the sequence number in the TIO was 352 incrememented since the LLN Router left that tree, indicating 353 that the candidate parent was not attached behind this LLN Router 354 and kept getting subsequent TIOs from the same tree. The LLN 355 Router will join that other tree if it is preferable for reasons 356 of connectivity, configured preference, free medium time, size, 357 security, bandwidth, tree depth, or whatever metrics the LLN 358 Router cares to use. 360 7. If an LLN Router has selected a new parent router but has not 361 moved yet (because it is waiting for Tree Hop Timer to elapse), 362 the LLN Router is said to be unstable and it refrains from 363 sending Router Advertisement - Tree Information Options. 365 8. When a LLN Router joins a tree, it moves within its own tree or 366 receives a modified TIO from its current parent router, the LLN 367 Router sends out an unsolicited Router Advertisement message with 368 TIO that propagates the new tree information. 370 9. This allows the new higher parts of the tree to be updated first, 371 eventually dragging their sub-tree with them, and allowing 372 stepped sub-tree reconfigurations, limiting relative movements. 374 2.2. Discovery Information 376 The Tree Information Option carries a number of metrics and other 377 information that allows an LLN Router to discover a tree and select 378 its parent while avoiding loop generation. 380 TIO Base option 381 The Tree Information Option is a container option, which might 382 contain a number of suboptions. The base option regroups the 383 minimum information set that is mandatory to operate the LLN 384 Discovery Algorithm. 386 Grounded (G): The Grounded (G) flag is set when the tree is 387 attached to a fixed network infrastructure (such as the 388 Internet). 390 Sequence Number: An integer that is incremented by the root for 391 each TIO sent on a link. It is propagated unchanged down the 392 tree. 394 Boot Time Random: A random number used to resolve collisions. 395 Its value is computed at boot time and recomputed in case of a 396 collision. Each LLN Router in the propagation chain sets this 397 TIO field to its own value. 399 Tree Depth: If the root is attached to a federating backbone, its 400 Tree Depth is 1, otherwise it is 0. The Tree Depth of an LLN 401 Router is the depth of its parent as received in a TIO, 402 incremented by at least one. All the nodes in the tree 403 advertise their Tree Depth in the Tree Information Options that 404 they append to the RA messages as part of the propagation 405 process. 407 Tree Delay: An unsigned integer set by the root indicating the 408 delay before changing the tree configuration. It is expected 409 to be at least an order of magnitude shorter than the RA 410 interval and at least an order of magnitude larger than the 411 typical propagation delay inside the LLN. 413 Path Digest: An unsigned integer CRC, updated by each Router. 414 This is the result of a computation on a bit string obtained by 415 appending the received value and the Router address used to 416 attach to his parent. LBRs use a 'previous value' of zeroes to 417 initially set the Path Digest. 419 Tree ID: An unsigned integer which uniquely identifies a tree. 420 This value is set by the root to one of its ULA or global 421 addresses or prefixes. 423 Uniform Path Metric: A scalar measure for the quality of the bi- 424 directional path between the LLN Router and the root. 426 The following values MUST not change during the propagation of the 427 TIO down the tree: G, Tree Delay and Tree ID. All other fields 428 are updated at each hop of the propagation. 430 In addition to the minimum set of information required, a number 431 of options can are used, e.g. for bandwidth, stability, preference 432 etc. 434 2.3. Tree Selection 436 The tree selection is implementation and algorithm dependent. In 437 order to limit erratic movements, and all metrics being equal, LLN 438 Routers SHOULD stick to their previous selection. Also, LLN Routers 439 SHOULD provide a means to filter out candidate parent Routers whose 440 availability is detected as fluctuating, at least when more stable 441 choices are available. For instance, the LLN Router MAY place the 442 failed parent Router in a Hold Down mode that prevents the parent 443 Router from being reused for a given period of time. 445 The known trees are associated with the parent Router that advertises 446 them and kept in a list by extending the Default Router List. DRL 447 entries are extended to store the information received from the last 448 TIO. These entries are managed by states and timers described in the 449 next section. 451 When LLN connection to a fixed network is either not possible or not 452 recommended, for security or other reasons, scattered trees should as 453 much as possible be aggregated into larger trees in order to allow 454 inner connectivity. How to balance these trees is implementation 455 dependent, and MAY use a specific visitor-counter suboption in the 456 TIO. 458 An LLN Router SHOULD verify that bidirectional connectivity is 459 available with a candidate parent Router before it attaches to that 460 candidate. Some link-layers such as 802.11 infrastructure mode will 461 provide for this, while others such as 802.15.4 will not. If the 462 link-layer does not guarantee bidirectional connectivity, then the 463 LLN Router needs to make sure that it can reach the LBR. This is 464 achieved using Neighbor Solicitation and refraining from attaching to 465 an LBR for which no neighbor cache exists, or the state is still 466 INCOMPLETE. 468 2.4. States 470 Parent routers in the DRL may or may not be usable for attachment 471 depending on runtime conditions. The following states are defined: 473 Current This parent Router is currently used for attachment 475 Candidate This parent Router can be used for attachment. 477 Held-Up This parent Router can not be used till Tree Hop Timer 478 elapses. 480 Held-Down This parent Router can not be used till Hold Down Timer 481 elapses. At the end of the hold-down period, the router is 482 removed from the DRL. It will be reinserted if it appears again 483 in an RA. 485 Collision This parent Router can not be used until it transmits its 486 next RA. 488 2.5. Stability 490 An LLN Router is instable when it is prepared to move shortly to 491 another parent Router. This happens typically when the LLN Router 492 has selected a more preferred candidate parent Router and has to wait 493 for the Tree Hop Timer to elapse before roaming. Instability may 494 also occur when the current parent Router is lost and the next best 495 is still held up. Instability is resolved when the Tree Hop Timer of 496 all the parent Router(s) causing instability elapse. Such parent 497 Router is changes state to Current or Held- Down. 499 Instability is transient (on the order of Tree Hop Timers). When an 500 LLN Router is unstable, it MUST NOT send RAs with TIO. This avoids 501 loops when LLN Router A wishes to attach to LLN Router B and LLN 502 Router B wishes to attach to LLN Router A. Unless RAs crisscross, a 503 LLN Router receives TIO from stable parent Routers, which do not plan 504 to attach to it, so the LLN Router can safely attach to them. 506 3. Route Dissemination 508 3.1. Overview 510 Route Dissemination is the second component of the LLN fundamental 511 mechanisms. As explained previously, the first component, LLN Tree 512 Discovery, establishes a logical tree structure over the LLN and sets 513 up default routes towards the root. To establish the routing states 514 towards the nodes in the LLN and enable complete reachability along 515 the tree, it suffices for Route Dissemination to advertise up the 516 tree the host, prefix and multicast routes. 518 As a result, the Default Router for an LLN Router is its parent up in 519 the tree (upstream); and the more specific routes are always oriented 520 down the tree (downstream). 522 LLN Tree Discovery does not only provide loop avoidance for the Route 523 Dissemination protocol; LLN Tree Discovery also triggers Route 524 Dissemination each time a topological change occurs. The loopfree 525 structure must be restored before Route Dissemination can operate 526 again and repaint the tree with prefixes, addresses and group 527 membership. 529 Each logical tree that LLN Tree Discovery forms is considered a 530 separate routing topology. If an LLN Router belongs to multiple of 531 such topologies, then it is expected that both the Route 532 Dissemination signaling and the data packets are flagged to follow 533 the topology for which the packet was introduced in the network. 535 The ROLL Route Dissemination protocol design follows a hierarchical 536 model where a whole structure that is reachable via a node of the 537 tree is abstracted as located within that node for the upper level of 538 network abstraction, exposing only the list of reachable prefixes, 539 hosts, and multicast group listeners as opposed to the topological 540 information to get there. 542 This allows an extreme conciseness of the routing information, with 543 no topological knowledge past the first hop. That conciseness 544 enables some degree of movement within the nested structure; in 545 particular, a movement within a subtree is not seen outside of that 546 subtree, so most of the connectivity is maintained at all times while 547 there might never be such a thing as a convergence. 549 The ROLL Route Dissemination protocol defines a new information 550 vector called the Route Information Option (RIO) to disseminate 551 atomic routing information towards the root of the tree. Due to a 552 topological change, a RIO can be received from a sub-tree where the 553 originating router was but is no more, until its parents realize it 554 is gone and stop advertising. By construction of the tree, there can 555 be a single child to reach a given unicast resource, so older unicast 556 routes can be flushed right away if a more recent advertisement comes 557 from a different child. Multicast routes can only be explicitely 558 removed or timed out. 560 A parent maintains a state for each information it learns from Route 561 Dissemination. Advertisements are sequenced and the last sequence 562 number is kept. An out-of-sequence RIO must be disregarded. If the 563 RIO information appears valid, it is forwarded to the parent's parent 564 in the next burst, carried by a RIO, together with the parent's own 565 information. 567 3.2. Disseminated Information 569 Route Dissemination extends RFC4861 and RFC4191 to allow a node to 570 include a new Route Information Option in ND messages such as 571 Neighbor Advertisements (NAs). 573 In order to track the freshness of an advertisement, the RIO includes 574 a sequence counter that is incremented each time the advertisment is 575 reissued. 577 A depth is also added for tracking purposes; the depth is incremented 578 at each hop as the RIO is propagated up the tree. 580 Receiving a Tree Discovery TIO from the parent triggers the sending 581 of a delayed advertisement back, with the collection of all known 582 information. 584 An NA is also sent to the new parent once it has been selected after 585 a movement, or when the list of advertised information has changed. 587 Route Dissemination may advertise positive (prefix is present) or 588 negative (removed) RIOs. A no-RIO is stimulated by the disappearance 589 of a route below. This is discovered by timing out after a request 590 (a Tree Discovery TIO) or by receiving a no-RIO. A no-RIO is a RIO 591 with a RIO Lifetime of 0. 593 The RIO base option carries sequenced route information for unicast 594 and multicast; it contains: 596 Resource type: Prefix, host, or multicast group 598 Prefix Length: Number of valid leading bits in the IPv6 Prefix. 600 RIO Lifetime: The length of time in seconds (relative to the time 601 the packet is sent) that the prefix is valid for route 602 determination. A value of all one bits (0xFFFFFFFF) represents 603 infinity. A value of all zero bits (0x00000000) indicates a loss 604 of reachability. 606 RIO Depth: Set to 0 by the router that owns the resource and issues 607 the RIO. Incremented by all routers that propagate the RIO 608 towards the root. 610 RIO Sequence: Incremented by the router that owns the resource for 611 each new RIO for that prefix. Left unchanged by all routers that 612 propagate the RIO. A lollipop mechanism is used to wrap from 613 0xFFFF directly to 10. 615 Prefix: Variable-length field containing a prefix, an IPv6 address 616 or a multicast group id. The Prefix Length field contains the 617 number of valid leading bits in the prefix in the former case. 618 The bits in the prefix after the prefix length (if any) are 619 reserved and MUST be initialized to zero by the sender and ignored 620 by the receiver. 622 3.3. LLN Router Operation 624 The LLN Router operation is autonomous, based on the information 625 provided by the potential parents in sight. Each router selects a 626 parent in a loopfree and case-optimized fashion, and installs a 627 default route up the tree via the selected parent. The resulting 628 tree may never be globally stable enough to be mapped in a global 629 graph. So the adaptation to local movements must be rapid and 630 localized. 632 Route Dissemination information can be redistributed in another 633 routing protocol, e.g. MANET or IGP. But the MANET or the IGP route 634 information SHOULD NOT be redistributed into Route Dissemination. 635 This creates a hierarchy of routing protocols where Route 636 Dissemination routes stand somewhere between connected and IGP 637 routes. See Section Section 6.1 for more discussion on integration 638 with other routing protocols. 640 As a result: 642 o LLN Discovery establishes a tree using extended Neighbor Discovery 643 RS/RA flows. 645 o A routing algorithm exploits the tree to get optimally out of LLN 646 (default route). 648 o Route Dissemination extends Neighbor Discovery in order to quickly 649 establish hop-by-hop routes down the tree. 651 o Source Routing can be used to provide additional routes towards 652 nodes in the LLN. When there is existing hop-by-hop state in 653 routers, the source routing information can be compressed. 655 Route Dissemination maintains abstract lists of known information. 656 An entry contains the following abstract information: 658 o The state of the entry: ELAPSED, PENDING, or CONFIRMED. 660 o A reference to the adjacency that was created for that prefix. 662 o A reference to the ND entry that was created for the advertiser 663 Neighbor. 665 o The IPv6 address of the advertiser Neighbor. 667 o The logical equivalent of the full Route Dissemination 668 information. 670 o A reference to the interface of the advertiser Neighbor. 672 o A 'reported' Boolean to keep track whether this prefix was 673 reported already to the parent parent. 675 o A counter of retries to count how many TIOs were sent on the 676 interface to the neighbor without reachability confirmation for 677 the prefix. 679 Route Dissemination stores the entries in either one of 3 abstract 680 lists; the Connected, the Reachable and the Unreachable lists. In 681 practice all part of a route table. 683 The Connected list corresponds to the resources owned by the LLN 684 Router. 686 As long as an router keeps receiving RIOs for a given information 687 timely, its entry is listed in the Reachable list. 689 Once scheduled to be destroyed, an entry is moved to the Unreachable 690 list if the router has a parent to which it sends RIOs, otherwise the 691 entry is cleaned up right away. The entry is removed from the 692 Unreachable list when the parent changes or when a no-RIO is sent to 693 the parent indicating the loss of the prefix. 695 Route Dissemination requires 2 timers; the DelayNA timer and the 696 DestroyTimer. 698 o The DelayNA timer is armed upon a stimulation to send a RIO (such 699 as a TIO from the parent). When the timer is armed, all entries 700 in the Reachable list as well as all entries for Connected list 701 are set to not reported yet. 703 o The DelayNA timer has a duration that is DEF_NA_LATENCY divided by 704 2 with the tree depth. 706 o The DestroyTimer is armed when at least one entry has exhausted 707 its retries, which means that a number of TIO were sent over the 708 interface but that the entry was not confirmed with a RIO. When 709 the destroy timer elapses, for all exhausted entries, the 710 associated route is removed, and the entry is scheduled to be 711 destroyed. 713 o The Destroy timer has a duration of min (MAX_DESTROY_INTERVAL, 714 RA_INTERVAL). 716 RIO Processing 718 When ND sends a NA to the parent, Route Dissemination extends the 719 message with RIO options for: 721 * All the entries that are not 'DELETED'. 723 * All the entries in the removed list as no-RIO. 725 * All the pentries in the advertised list that are not reported 726 yet.The entries are then set to reported. 728 When ND receives a NA from a visitor over a given interface, RIOs 729 are processed in a loop. For known information, the sequence 730 counter in the RIO is checked against the last received and the 731 update is used only if the sequence is newer. This filters out 732 obsolete advertisements when a node has moved between 2 subtrees 733 attached to a same node. 735 If an information is advertised as a no-RIO, the associated route 736 is removed, and the entry is transferred to the removed list. 737 Otherwise, the proper routing table is looked up: 739 * If a preferred route to that source from another protocol 740 already exists, the RIO is ignored. 742 * If a new route can be created, a new entry is allocated to 743 track it, as CONFIRMED, but not reported. 745 * If a Route Dissemination route existed already via the same 746 Neighbor, it is CONFIRMED. 748 * If an older unicast route existed via a different Neighbor, 749 this is equivalent to a no-RIO for the previous entry followed 750 by a new RIO for the new entry. So the old entry is scheduled 751 to be destroyed, whereas the new one is installed. 753 Unicast Route Dissemination messages from child to parent 754 When sending Route Dissemination to its parent, a router includes 755 the RIOs about not already reported entries in the Reachable and 756 Connected lists, as well as no-RIOs for all the entries in the 757 Unreachable list. 759 Depending on its policy, the receiving router SHOULD install a 760 route for the resource in the RIO via the link local address of 761 the source router and it SHOULD propagate the information, either 762 as a RIO or by means of redistribution into a routing protocol. 764 The TIO from the root is used to synchronize the whole tree. Its 765 period is expected to range from 500ms to hours, depending on the 766 stability of the configuration and the bandwidth available. 768 When an router receives a TIO over an egress interface from the 769 current parent parent, the DelayNA is armed to force a full 770 update. The router also issues a propagated TIO over all its 771 relevant interfaces, after a small jitter that aims at minimizing 772 collisions of TIO messages over the radio as it is propagated down 773 the tree. 775 The design choice behind this is NOT TO synchronize the parent and 776 children databases, but instead to update them regularly to cover 777 from the loss of packets. The rationale for that choice is 778 movement. If the topology can be expected to change frequently, 779 synchronization might be an excessive goal in terms of exchanges 780 and protocol complexity. This results in a simple protocol with 781 no real peering. 783 When the router sends a TIO over an interface, for all entries on 784 that interface: 786 * If the entry is CONFIRMED, it goes PENDING with the retry count 787 set to 0. 789 * If the entry is PENDING, the retry count is incremented. If it 790 reaches a maximum threshold, the entry goes ELAPSED If at least 791 one entry is ELAPSED at the end of the process: if the Destroy 792 timer is not running then it is armed with a jitter. 794 Since the DelayNA has a duration that decreases with the depth, it 795 is expected to receive all RIOs from all children before the timer 796 elapses and the full update is sent to the parent. 798 Other events 799 Finally, Route Dissemination listens to a series of events, such 800 as: 802 * router stopped or unable to run: Route Dissemination routes are 803 cleaned up. Route Dissemination is inactive. 805 * Route Dissemination operation stopped: All entries in the 806 abstract lists are freed. All the Route Dissemination routes 807 are destroyed. 809 * Interface going down: for all entries in the Reachable list on 810 that interface, the associated route is removed, and the entry 811 is scheduled to be destroyed. 813 * Neighbor being removed from the ND list: if the entry is in the 814 Reachable list the associated route is removed, and the entry 815 is scheduled to be destroyed. 817 * Roaming: All entries in the Reachable list are set to not 818 'reported' and DelayNA is armed. 820 4. Forwarding 822 The fundamental mechanisms described in this draft build a DAG to 823 enable communication from the LLN Router nodes to the LLN Border 824 Routers (upstream); a second mechanism informs LLN Routers about 825 their children in the tree, hence enabling LLN Boarder Router to LLN 826 Router communication (downstream) and node-to-node routing along the 827 tree. While the previous sections focus on how routing information 828 is disseminated throughout the LLN and used for routing, this section 829 focuses on the forwarding policies used by LLN Routers. 831 Reliability can be increased by allowing for secondary next-hop nodes 832 for upstream traffic, while downstream traffic is sent along the tree 833 formed by route dissemination. 835 4.1. Upstream Forwarding 837 Forwarding in a LLN needs to account for requirements that are 838 unusual in the IP world: 840 perfect loop freedom is a non-goal 842 the specification allows the wheel model where a packet circulates 843 a bit around the destination till it finally makes it. 845 transient forwarding failure are commonplace 847 This specification introduces the capability for the layer 2 to 848 give a packet back to layer 3 in order to try another adjacency. 850 Using the LLN Tree Discovery procedure, LLN Routers expose their path 851 metrics using the Uniform Path Metric field in the TIO. Neighbor LLN 852 Routers with a lesser depth in the tree then self are forwarding 853 parents. Neighbor LLN Routers with a same depth in the tree are 854 siblings. Forwarding via parents ensures a loop free operation 855 whereas forwarding via siblings may not be loopfree unless additional 856 measures are taken. 858 The approach taken in this specification is to favor forwarding via 859 parents but enable forwarding via siblings as a backup option. 860 Preferring the parents enables a forwarding gradient towards the LBR 861 that limits the chances of multiple consecutive hops over siblings. 862 This specification also prevents from returning a packet back to the 863 neighbor that just passed it. This simple rule coupled with the 864 forwarding gradient protect against loops for a vast majority of 865 cases, and the specification relies on a appropriate setting of the 866 TTL in a given deployment to protect against meltdowns. 868 In more details: 870 o A LLN router MUST send upstream data to its forwarding parent with 871 smallest metric. Note that, depending on the way the routing 872 protocol determines this metric, and the dynamics of the tree, the 873 best forwarding parent at a given point of time is not necessarily 874 the parent with the smallest depth or the parent in the logical 875 tree defined by the Tree Discovery procedure. 877 o If the transmission of an upstream packet to that preferred parent 878 fails (due to a node or link failure, or mobility), the LLN router 879 MAY attempt to forward the packet again via other parents, as 880 ordered by best metric. 882 o If the transmission to both primary and secondary forwarding 883 parents fails, the LLN Router MAY forward the packet via siblings, 884 as ordered by best metric. 886 o When the transmission fails and the packet is retried via a 887 different neighbor, the router MUST decrease the TTL by one. 889 In order to enable these rules, a LLN router maintains a blacklist 890 per packet being forwarded that contains: 892 o the neighbor that forwarded the packet to self 894 o neighbors to which forwarding of this packet failed 896 These rules are illustrated in the following figure which represents 897 a subset of an LLN. 899 D,1,3 B,1,7 900 | / 901 | / 902 | / 903 C,2,9--- A,2,8 905 An LLN Router is identified by . LLN Router A has 906 three neighbors B,C,D. D is A's primary forwarding parent as it is 907 the neighbor with the smallest Metric amoung neighbors with smaller 908 depth. If transmission to D fails, A sends the packet to B, which is 909 of smaller depth. If transmission to B fails, A transmits to C. 910 Because C is at the same depth as A, a blacklisting policy is used to 911 avoid that C retransmits to A. 913 4.2. Downstream Forwarding 915 Downstream routing using LLN fundamental mechanisms can occur using 916 either hop-by-hop state, source routing or a combination of them 917 (loose source route). By default the LLN Dissemination mechanism 918 builds up hop-by-hop distance-vector routing information in each of 919 the routers along the tree up to the root for each address, prefix or 920 group ID. 922 Source routing can optionally be supported by either requesting a 923 route record header from a node, or by having nodes send periodic 924 route record headers up to the root. Route Dissemination also allows 925 a compression of the Routing header when the routes match the 926 topology as traced by Record Route on a per packet basis. In 927 particular, if a Route Dissemination route exists to the first entry 928 in the Record Route header via the source of the packet, then the 929 router can override the source of the packet with its address without 930 adding the original source to the Record Route. At that point, the 931 routing header operation becomes loose, in other words an hybrid 932 between transparent hop-by-hop (stateful) and source routing. 934 Therefore three different downstream techniques are supported: 936 o Hop-by-hop forwarding. When only partial route dissemination data 937 reaches a LLN Border Router, it only knows the next-hop to a given 938 LLN Router in the network. In this case, each LLN Router relaying 939 downstream data will select the next-hop according to the 940 information it receives during route dissemination. 942 o Full source routing. When all the route dissemination data 943 reaches a LLN Border Router, it one can choose to specify the full 944 list of LLN Routers to be traversed in each downstream data 945 packet. 947 o Loose source routing. When the source route information is 948 compressed because of existing state in the routers along the 949 path. 951 5. Multicast Support 953 5.1. Overview 955 Wherever we mention , one can read MLDv2,3 for IPv6. Doing IGMP 956 over the LLN involves: 958 o LLN Border Router acting as a local Rendez-vous Point (RP) for the 959 LLN and as source towards the Internet for all multicast flows 960 started in the LLN. 962 o transporting in Route Dissemination and recursive 963 coalescence of the multicast requests. 965 5.2. Receiver Flow 967 The LBR is considered as a Rendezvous Point (RP) for all multicast 968 flows issued from inside the LLN. Multicast packets are passed up 969 the tree to the LBR. 971 Nodes talk to their parent router. The parent router forward 972 the registration and inject their own as a special type of RIO for 973 multicast groups, towards the LBR. The LBR MAY participate to 974 multicast in the infrastructure it is connected to and forward all 975 the packets coming from the LLN. 977 Between the parent router and the LBR, requests are transported 978 in the RIO; each hop aggregates the requests in a fashion that is 979 similar to proxy IGMP, but this happens recursively between child 980 node to parent router up to the LBR. On the way, multicast routing 981 states are installed in each router from the receiver to the root, 982 enabling multicast routing down the LLN tree. 984 5.3. Source flow 986 As a Node, the source is unaware of the ROLL protocol, and it uses 987 standard protocols with the router (say in IPv6: Neighbor Discovery, 988 etc...). So when it has a multicast packet to send, the source 989 just forwards it to its default router, which is the expected 990 standard behavior. RRs on the way recursively forward to their 991 parent. At each hop, if a multicast route indicates that a listener 992 is reachable via another child (but that from which the packet was 993 received) then the packet is duplicated and forwarded to that child 994 down the tree. 996 If the LLN Border Router is configured to do so, it will source the 997 packet to a real RP in the Internet. 999 6. Advanced Features 1001 The fundamental mechanisms described in this document are sufficient 1002 to allow for upstream and downstream communication inside the LLN. 1003 They form a common basis upon which future LLN routing protocols can 1004 be designed. This section indicates some possible advanced features 1005 which can be integrated to increase efficiency for a particular 1006 useage scenarios. 1008 6.1. Interaction with other routing protocols 1010 While network design and specific use cases are out of scope for this 1011 document, it must be noted that the ROLL fundamentals mechanisms 1012 described herein might be used in conjunction with other routing 1013 protocols vin order to fulfill the requirements of a particular 1014 deployment. Here follows a non exhaustive series of examples 1015 illustrating such interactions. 1017 6.1.1. AODV/DYMO 1019 In the example of a closed loop between a sensor and a switch, a 1020 constrained optimized route must be installed between the 2 devices. 1022 Defining such a specific route is costly and should be performed on- 1023 demand when the bulk of the traffic is buffered data from source to 1024 sink. 1026 A reactive MANET protocol such as AODV [RFC3561], DSR [RFC4728] or 1027 DYMO [I-D.ietf-manet-dymo] can be deployed to enable such routing, 1028 though the QoS-constrained approach for AODV is stalled as a draft 1029 ([I-D.perkins-manet-aodvqos]). 1031 6.1.2. OSPF/OLSR 1033 A federating backbone is the virtual root of a collection of trees 1034 that forms a single routing topology. If that topology shares a same 1035 prefix, a sensor device can move freely within the topology without 1036 renumbering.The 6LoWPAN backbone link is an example of such a 1037 federating backbone and in that case, the protocol that enables any 1038 to any reachability is simply IPv6 Neighbor Discovery [RFC4861]. 1040 In a generalized case with routing and multiple subnets, a 1041 traditional IGP such as OSPF [RFC2740] or a MANET protocol such as 1042 OLSR [RFC3626] can be deployed within the federating backbone between 1043 the LBR to advertise the routes learnt from the ROLL fundamentals 1044 dissemination protocol through the redistribution of route 1045 information. 1047 In turn, the routed federating backbone is just the instantiation at 1048 Depth 0 of the more general concept of beltlines. A beltline is a 1049 set of routers of a same depth in a same tree that form a subarea 1050 where an IGP is run and route information from the LLN Route 1051 Dissemination protocol is redistributed. This creates routes around 1052 the root and reduces the load that routing along the tree imposes on 1053 the lower depth of the tree. 1055 Note that in turn, beltline routes ARE NOT redistributed into LLN 1056 Route Dissemination information. As a result, the beltlines routes 1057 are orthogonal to the route dissemination routes, and they should 1058 never collide, which optimizes the value of the control plane of the 1059 combination. 1061 Beltline routes should be used with caution in order to maintain 1062 stability and optimize the resulting routes: 1064 o beltline routes should only be used when a certain topological 1065 stability was asserted 1067 o using beltline routes discourages the reorganization of the tree, 1068 mostly when that causes a router to change its depth 1070 o a divide and conquer approach to limit the size of a beltline 1071 enables to manage the cost of the control plane 1073 o a beltline of depth 2 or more should be an arc as opposed to full 1074 circle.In the example of a closed loop between a sensor and a 1075 switch, a constrained optimized route must be installed between 1076 the 2 devices. 1078 6.1.3. MIP6/NEMO 1080 MIP6 [RFC3775]and NEMO [RFC3963] enables a subtree to move away from 1081 the tree and maintain reachability as if the nodes in the subtree 1082 were still located in their topologically correct position. This can 1083 be useful when a RIO aggregation is performed (see Section 6.6) to 1084 enable reachability of a stray device. MIP6 be also be useful to 1085 enable a mobile display device such as a PDA to keep accessing a 1086 sensor network remotely without injecting the sensor network prefix 1087 into the infrastructure for security reasons. 1089 6.2. Route Optimization 1091 Whereas upstream and downstream communication is made possible by the 1092 fundamental mechanisms described in this document, applications may 1093 require more require traffic engineering, which may include: 1095 6.2.1. Node-to-node routing 1097 Node-to-node routing is ensured along the tree by the Route 1098 Dissemination protocol, and the packets flow via he first common 1099 parent. This can be optimized if the LLN Border Router has a clear 1100 view of the topology (see 'Offline Path Computation' section). In 1101 this case, the LLN Border Router can indicate the direct path between 1102 both LLN Routers, calculated offline, to the source, the destination, 1103 or both. This technique induces a trade-off between multi-hop route 1104 efficiency and signaling overhead to setup this direct node-to-node 1105 path for instance as suggested in Section 6.1.1. 1107 6.2.2. Offline Path Computation 1109 Whereas nodes might not have the capacity to store and manage enough 1110 information to perform constrained routing, it is possible for node 1111 to report there neighborhood information to the LLN Border routers. 1112 LLN Border routers can then share their partial topology databases 1113 and get a full picture of the network. 1115 From there, it is possible to get LLN Border routers to compute 1116 shorter or constrained paths and either distribute them (e.g. LDP) 1117 or pass the source route information to the end nodes. 1119 An OSPF example of that goes like this. Nodes run HELLO or similar, 1120 and send their LSA in unicast to their LLN Border routers. The LLN 1121 Border routers act as proxy for the nodes and share those LSAs with 1122 other LLN Border routers over the backbone. At some point they 1123 converge and an LLN Border router will run SPF on behalf of all its 1124 registered nodes, one at a time. The SPF computation should end at a 1125 certain distance from the node for which it makes more sense to go 1126 through the backbone anyway. Then the LLN Border router sends the 1127 set of routes to the node as an new topology that can be used in a 1128 MTR fashion. 1130 6.2.3. Graph forwarding 1132 Distance Vector and Link State routing protocols are traditionally 1133 designed in terms of: 1135 Links -> Metrics -> Routes -> network runtime 1137 Unless traffic engineering kicks in, either the routes are 1138 established over the shortest path and the alternate links are wasted 1139 or the traffic is load balanced in a fashion that represents the 1140 ratio of costs as opposed to the ratio of capacity of the paths. 1142 Also, the runtime of the network is opaque to the forwarding plane, 1143 so the only way to guarantee some end-to-end bandwidth for a class of 1144 traffic is to blindly reserve it, leading to even more waste of 1145 bandwidth when the reservation is not fully utilized. 1147 In order to optimize the network utilization, it would be beneficial 1148 to detect the saturation of the shortest path and load balance the 1149 extra traffic over alternate routes. In the case of ROLL, it is also 1150 critical to be able to make a reroute decision on a per packet basis 1151 when hop by hop retries are exhausted. Arpanet introduced a feedback 1152 loop into the routing protocol by making the metrics dynamic: 1154 Links -> Metrics -> Routes -> network runtime 1155 ^ | 1156 |__________________________________| 1158 But this approach was unsuccessful, causing instabilities and 1159 disrupting the network. With dynamic metrics, the duration of the 1160 convergence time - or frozen time -,increases with the number of 1161 links and the frequency of the metric updates. During that time, the 1162 response of the network is undefined and temporary loops occur. 1164 An approach to solve this problem is having 2 independent sets of 1165 metrics: In one hand, the topological metrics that are rather static 1166 and mostly administratively set; and in the other hand the volatile 1167 metrics that are based on dynamic measurements of the network 1168 characteristics. 1170 The topological metrics are used by the ROLL routing protocol to 1171 initially build the tree as described in this specification. The 1172 volatile metrics are then used by a forwarding protocol to balance 1173 the traffic for that destination over the upstream links, thus 1174 modifying the way the graph is being used in runtime, without 1175 changing its structure. 1177 To get there, the control plane operates in 2 phases, in a lollipop 1178 fashion: 1180 Links->Metrics->Routes->netw. runtime->runtime metrics->forwarding 1181 ^ | 1182 |________________________________| 1183 <--------------------------> <-----------------------------------> 1184 ROLL routing protocol ROLL forwarding protocol 1186 The ROLL fundamentals proposal builds shortest path trees to the 1187 exits but adds the capability to forward over another branch if 1188 sending a packet to a parent fails, either via any alternate parent 1189 or a sibbling. So the paths that we really want to monitor are along 1190 the tree itself and one hop away from the tree. To get there, the 1191 root emits a beacon that is multicasted down the tree and heard one 1192 hop away. That beacon gathers the metrics that will be used for 1193 alternate parents and sibblings selection and nodes keep track of the 1194 beacon they hear for all the parents and sibblings they want to 1195 track. From the beacon, they can infer the quality of the path 1196 through all the alternates and compare them. 1198 6.3. Density 1200 In a dense environment, it is useless that all routers that can 1201 provide backhauling service actually do so; in practice, limiting the 1202 number of routers that accept attached nodes saves memory in the 1203 attached nodes and reduces the cost of signalling. Also, limiting 1204 the number of forwarding LLN Routers in the tree improves the 1205 multicast operations. 1207 Algorithms such a Trickle could be used by a LLN Router to decide to 1208 stop providing its access services for attached nodes if there are a 1209 number of neighboring routers that provide similar services. The 1210 simplest abstraction of such similarity is that a multiple routers 1211 advertising a same depth, though such a simple similarity does not 1212 address the specifics of a router selection in the plugins. In a 1213 more general fashion, a LLN Router can associate the concept of 1214 similarity with the characteristics of its own parent router 1215 selection plug in. 1217 6.4. Digraph Dissemination 1219 The fundamental techniques described in this draft coverlays a tree 1220 for source/sink traffic over the physical topology. This tree could 1221 be converted into a (bi)graph with additional overhead. A LLN Router 1222 would therefore send route dissemination data to both its primary and 1223 secondary forwarding parents, hence informing a LLN Border Router of 1224 disjoint paths. This makes sense in applications where the gains in 1225 increase downstream reliability outweigh the additional signaling 1226 overhead. 1228 6.5. Multiple LBRs and Trees 1230 The ROLL tree discovery technique propagates increasing depths and 1231 metrics throughout the network; upstream messages travel on a 1232 decreasing metric path back to the ROLL border router. When the LLN 1233 features multiple LBRs, the following options appear: 1235 o If the different LBRs share the same TreeID, a LLN Router 1236 implicitly sends its upstream data to the LBR which is closest in 1237 terms of aggregated metric. This should be used whenever LBR play 1238 the same role. 1240 o Different LBRs may choose to use different TreeIDs. In this case, 1241 a LLN Router is part of multiple trees, one for eachTreeID. When 1242 sending an upstream message, a LLN Router chooses on which TreeID 1243 it wishes to send, i.e. to which LBR. 1245 o A hybrid case can exist in which some LBRs share the same TreeID 1246 while others have their dedicated tree ID. 1248 An alternative when having multiple LBR is to construct multiple 1249 trees (e.g. one for each LBR) and choose a default tree for 1250 forwarding data. Using an alternate tree is possible only when 1251 labeling the data packet accordingly; an unlabeled packet is 1252 forwarded on the default tree. 1254 6.6. Aggregation for Route Dissemination 1256 Aggregation of prefixes on a same router 1258 When deploying an router with multiple interfaces, it makes sense 1259 to assign an aggregation prefix (shorter than /64) to the router 1260 and partition it as /64 prefixes over the router interfaces. An 1261 router that owns a contiguous set of prefixes should only report 1262 the aggregation of these prefixes through Route Dissemination. 1264 Aggregation of prefixes by a parent acting as ROLL Home 1266 There are also a number of cases where a ROLL aggregation is 1267 shared within a toon of LLN Routers. For instance, a toon formed 1268 by firefighters and their commander. In that case, it is still 1269 possible to use aggregation techniques with Route Dissemination 1270 and improve its scalability. In that case, the commander is 1271 configured as the Route Dissemination aggregator for the group 1272 prefix. In run time, it absorbs the individual RIO information it 1273 receives from the toon members down its subtree and only reports 1274 the aggregation up the TD tree. This works fine when the whole 1275 toon is attached within the commander's subtree. 1277 But other cases might occur for which additional support is 1278 required: 1280 1. the commander is attached within the subtree of one of its 1281 toon members. 1283 2. A toon member is somewhere else within the TD tree. 1285 3. A toon member is somewhere else in the Internet. 1287 In all those cases, a node situated above the commander in the TD 1288 tree but not above the toon member will see the advertisements for 1289 the aggregation owned by the commander but not that of the 1290 individual toon member prefix. So it will route all the packets 1291 for the toon member towards the commander, but the commander will 1292 have no route to the toon and will fail to forward. 1294 6.7. Advanced Forwarding 1296 A blacklisting policy can be used to avoid routing loops when an 1297 upstream data packet is sent between neighbor LLN Routers of the same 1298 depth. Alternatively, more general techniques can be used to avoid 1299 loops. One is to record the sequence of already traversed nodes in 1300 the data packet as it travels along a multi-hop path. When receiving 1301 a packet, a LLN Router may know whether it has already relayed that 1302 packet; if yes, it can know from which neighbors it had received it 1303 and to which it had sent. A distributed version of depth first 1304 search can then be used to avoid routing loops. This extension 1305 enables upstream packets to be sent to neighbors with a larger depth. 1307 7. Security Considerations 1309 As this draft suggests the use of new options carried in ICMP ND 1310 messages; the same security considerations as in [RFC4861] apply, in 1311 particular with regards to the use of Secure ND [RFC3971] to protect 1312 against address theft. Additionally link-layer security should be 1313 applied in the case of 6LoWPAN where SeND is not typically possible. 1315 8. IANA Considerations 1317 This draft would require two new ICMP options for use with ND: the 1318 Tree Information Option (TIO) and the Route Information Option (RIO). 1320 9. Acknowledgments 1322 The authors would like to thank Robert Assimiti, Kris Pister, Mischa 1323 Dohler, Julien Abeille, Ryuji Wakikawa, Teco Boot, Patrick 1324 Wetterwald, Bryan Mclaughlin and Carlos J. Bernardos for useful 1325 design considerations. 1327 10. References 1329 10.1. Normative References 1331 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 1332 (IPv6) Specification", RFC 2460, December 1998. 1334 [RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, 1335 "Transmission of IPv6 Packets over IEEE 802.15.4 1336 Networks", RFC 4944, September 2007. 1338 10.2. Informative References 1340 [I-D.ietf-manet-dymo] 1341 Chakeres, I. and C. Perkins, "Dynamic MANET On-demand 1342 (DYMO) Routing", draft-ietf-manet-dymo-17 (work in 1343 progress), March 2009. 1345 [I-D.ietf-roll-building-routing-reqs] 1346 Martocci, J., Riou, N., Mil, P., and W. Vermeylen, 1347 "Building Automation Routing Requirements in Low Power and 1348 Lossy Networks", draft-ietf-roll-building-routing-reqs-05 1349 (work in progress), February 2009. 1351 [I-D.ietf-roll-home-routing-reqs] 1352 Porcu, G., "Home Automation Routing Requirements in Low 1353 Power and Lossy Networks", 1354 draft-ietf-roll-home-routing-reqs-06 (work in progress), 1355 November 2008. 1357 [I-D.ietf-roll-indus-routing-reqs] 1358 Networks, D., Thubert, P., Dwars, S., and T. Phinney, 1359 "Industrial Routing Requirements in Low Power and Lossy 1360 Networks", draft-ietf-roll-indus-routing-reqs-04 (work in 1361 progress), January 2009. 1363 [I-D.ietf-roll-terminology] 1364 Vasseur, J., "Terminology in Low power And Lossy 1365 Networks", draft-ietf-roll-terminology-00 (work in 1366 progress), October 2008. 1368 [I-D.ietf-roll-urban-routing-reqs] 1369 Dohler, M., Watteyne, T., Winter, T., Barthel, D., 1370 Jacquenet, C., Madhusudan, G., and G. Chegaray, "Urban 1371 WSNs Routing Requirements in Low Power and Lossy 1372 Networks", draft-ietf-roll-urban-routing-reqs-05 (work in 1373 progress), March 2009. 1375 [I-D.perkins-manet-aodvqos] 1376 Perkins, C. and E. Belding-Royer, "Quality of Service for 1377 Ad hoc On-Demand Distance Vector Routing", 1378 draft-perkins-manet-aodvqos-01 (work in progress), 1379 November 2001. 1381 [RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", 1382 RFC 2740, December 1999. 1384 [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 1385 Demand Distance Vector (AODV) Routing", RFC 3561, 1386 July 2003. 1388 [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing 1389 Protocol (OLSR)", RFC 3626, October 2003. 1391 [RFC3775] Johnson, D., Perkins, C., and J. Arkko, "Mobility Support 1392 in IPv6", RFC 3775, June 2004. 1394 [RFC3963] Devarapalli, V., Wakikawa, R., Petrescu, A., and P. 1395 Thubert, "Network Mobility (NEMO) Basic Support Protocol", 1396 RFC 3963, January 2005. 1398 [RFC3971] Arkko, J., Kempf, J., Zill, B., and P. Nikander, "SEcure 1399 Neighbor Discovery (SEND)", RFC 3971, March 2005. 1401 [RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source 1402 Routing Protocol (DSR) for Mobile Ad Hoc Networks for 1403 IPv4", RFC 4728, February 2007. 1405 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 1406 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 1407 September 2007. 1409 Authors' Addresses 1411 Pascal Thubert 1412 Cisco Systems 1413 Village d'Entreprises Green Side 1414 400, Avenue de Roumanille 1415 Batiment T3 1416 Biot - Sophia Antipolis 06410 1417 FRANCE 1419 Phone: +33 4 97 23 26 34 1420 Email: pthubert@cisco.com 1422 Thomas Watteyne 1423 UC Berkeley 1424 497 Cory Hall #1774 1425 Berkeley Sensor & Actuator Center 1426 Berkeley, California 94720-1774 1427 USA 1429 Phone: +1 (510) 333-4437 1430 Email: watteyne@eecs.berkeley.edu 1432 Zach Shelby 1433 Sensinode 1434 Kidekuja 2 1435 Vuokatti 88600 1436 FINLAND 1438 Phone: +358407796297 1439 Email: zach@sensinode.com 1440 Dominique Barthel 1441 Orange Labs 1442 28 chemin du Vieux Chene, BP98 1443 BP98 1444 Meylan 38243 1445 FRANCE 1447 Phone: +33476764522 1448 Email: dominique.barthel@orange-ftgroup.com