idnits 2.17.00 (12 Aug 2021) /tmp/idnits24262/draft-thubert-rtgwg-arc-00.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 doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (October 2, 2012) is 3518 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: 'RFC4291' is defined on line 702, but no explicit reference was found in the text == Unused Reference: 'RFC4861' is defined on line 705, but no explicit reference was found in the text == Unused Reference: 'RFC4862' is defined on line 709, but no explicit reference was found in the text == Unused Reference: 'I-D.phinney-roll-rpl-industrial-applicability' is defined on line 714, but no explicit reference was found in the text == Unused Reference: 'I-D.thubert-lowpan-backbone-router' is defined on line 720, but no explicit reference was found in the text == Unused Reference: 'RFC4191' is defined on line 725, but no explicit reference was found in the text == Unused Reference: 'RFC4541' is defined on line 728, but no explicit reference was found in the text == Unused Reference: 'RFC5213' is defined on line 733, but no explicit reference was found in the text == Unused Reference: 'RFC5415' is defined on line 736, but no explicit reference was found in the text == Unused Reference: 'RFC5865' is defined on line 740, but no explicit reference was found in the text == Unused Reference: 'RFC6275' is defined on line 748, but no explicit reference was found in the text == Unused Reference: 'RFC6550' is defined on line 751, but no explicit reference was found in the text == Outdated reference: A later version (-02) exists of draft-phinney-roll-rpl-industrial-applicability-00 Summary: 0 errors (**), 0 flaws (~~), 15 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 RTGWG P. Thubert, Ed. 3 Internet-Draft P. Bellagamba 4 Intended status: Standards Track Cisco Systems 5 Expires: April 5, 2013 October 2, 2012 7 Available Routing Constructs 8 draft-thubert-rtgwg-arc-00 10 Abstract 12 This draft introduces the concept of ARC, a two-edged routing 13 construct that forms its own fault isolation and recovery domain. 14 The new paradigm can be leveraged to improve the network utilization 15 and resiliency for unicast and multicast traffic in multiple 16 environments. 18 Requirements Language 20 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 21 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 22 "OPTIONAL" in this document are to be interpreted as described in RFC 23 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 April 5, 2013. 42 Copyright Notice 44 Copyright (c) 2012 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. ARC Set representations . . . . . . . . . . . . . . . . . . . 7 62 4. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 11 63 4.1. Load Balancing . . . . . . . . . . . . . . . . . . . . . . 11 64 4.1.1. Routing Hierarchies . . . . . . . . . . . . . . . . . 11 65 5. Lowest ARC First . . . . . . . . . . . . . . . . . . . . . . . 11 66 5.1. Init . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 67 5.2. Growing Trees . . . . . . . . . . . . . . . . . . . . . . 12 68 5.3. Being Safe . . . . . . . . . . . . . . . . . . . . . . . . 12 69 5.4. Bending An ARC . . . . . . . . . . . . . . . . . . . . . . 13 70 5.5. Orienting Links . . . . . . . . . . . . . . . . . . . . . 14 71 5.6. Looping or recursing . . . . . . . . . . . . . . . . . . . 14 72 6. Forwarding Along An ARC Set . . . . . . . . . . . . . . . . . 15 73 6.1. Control Plane Recovery . . . . . . . . . . . . . . . . . . 16 74 6.2. Data Plane Recovery . . . . . . . . . . . . . . . . . . . 16 75 7. Manageability . . . . . . . . . . . . . . . . . . . . . . . . 17 76 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 77 9. Security Considerations . . . . . . . . . . . . . . . . . . . 17 78 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 17 79 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 18 80 11.1. Normative References . . . . . . . . . . . . . . . . . . . 18 81 11.2. Informative References . . . . . . . . . . . . . . . . . . 18 82 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19 84 1. Introduction 86 Traditional routing and forwarding uses the concept of path as the 87 basic routing paradigm to get a packet from a source to a destination 88 by following an ordered sequence of arrows between intermediate 89 nodes. In this serial design, a path is broken as soon as a single 90 arrow is, and getting around a breakage can require path 91 recomputation, network reconvergence, and incur delays to till 92 service is restored. 94 Multiple paths can be bound together for instance to form a Directed 95 Acyclic Graph (DAG) to a destination, but that technique can be 96 difficult to balance and cannot provide a full path redundancy even 97 in the case of a biconnected graph. For instance, if the node that 98 is closest to the DAG destination has only one link to that 99 destination, then it does not have a alternate path to get to that 100 destination. 102 It is also possible to compute an alternate routing topology for fast 103 rerouting to a given destination, in which case some signalling, 104 tagging or labelling can be put in place to indicate whether a packet 105 follows the normal path or was rerouted over an alternate topology. 106 Once a packet is rerouted, it is bound to the alternate topology so 107 only one breakage can be handled with looplessness guarantees in most 108 practical situations. 110 This draft introduces the concept of an Available Routing Construct 111 (ARC) as a routing construct made of a sequence of nodes and links 112 with 2 outgoing edges, so that, upon a single breakage, each lively 113 node in along ARC can still reach one of the outgoing edges. As a 114 result, an ARC is this resilient to one breakage as opposed to an 115 arrow that has only one outgoing edge, and an ARC topology is 116 resilient to one breakage per ARC. 118 The routing graph to reach a certain destination is expressed as a 119 cascade of ARCs, each ARC providing its own independent domain of 120 fault isolation and recovery. Unicast traffic may enter an ARC via 121 any node but it may only leave the ARC through one of its two edges. 122 One node along the ARC is designated as the cursor. In normal 123 unicast operations, the traffic inside an ARC flows away from the 124 cursor towards an edge. Upon a failure, packets may bounce on the 125 breakage point and flow the other way along the ARC to take the other 126 exit. 128 Aa a result an ARC is resilient to any single failure, and the 129 recovery can be driven either from the data plane or the control 130 plane. A second failure occurring within a same ARC will isolate an 131 ARC segment. This can be further corrected from the control plane by 132 reversing all the incoming Edges in a process that might recurse till 133 an exit is found. When ARC reversal is applied, an ARC topology is 134 resilient to some cases of Shared Risk Link Group (SRLG) failures. 136 This draft presents the concept and provides an intuition of how ARCs 137 can simplify the operation and improve the network utilization and 138 resiliency for all sorts of traffic in multiple environments, but 139 defers to further documents to elaborate on the algorithms and 140 optimizations in the different application domains. 142 For instance, ARCs can also be used in datacenters for the purpose of 143 fast-reroute, or within a service provider network to simplify load 144 balancing operations or leverage optimally the ring topologies 145 [RFC5921]. An ARC topology can be flooded over itself and serve as a 146 backbone for reliable multicasting operations. 148 2. Terminology 150 The draft uses the following terminology: 152 ARC: Available Routing Construct. An ARC is a loopless ordered set 153 of nodes and links whereby traffic may enter via any node in the 154 ARC but may only leave the ARC through either one of the ARC 155 edges. 157 Comb: An ARC generalization: a Comb is a n-edged loopless set of 158 nodes and links with n >= 2; traffic may enter via any node in the 159 Comb but may only exit the Comb through one of its n edges. A 160 Comb comes with a walk operation that enables to attempt to exit 161 via every edge and to discover when all have been tried. 163 Cursor: A virtual point along an ARC that can be located on a node 164 or on a link between 2 nodes. In normal operations, the traffic 165 along the ARC flows away from its Cursor. If the cursor is a 166 node, then traffic can be distributed on both sides. The Cursor 167 may be moved to change the way traffic is load balanced along an 168 ARC. It may also be placed at the location of a failure to direct 169 traffic away from that point. 171 ARC Node: A Node that belongs to an ARC. 173 Edge ARC Node: An ARC Node at an edge of its ARC. An Edge ARC Node 174 is a node via wich traffic can exit the ARC. 176 Edge Link: A directed link outgoing from an Edge ARC Node. Traffic 177 can only exit from an ARC via an Edge Link. An Edge Link does not 178 accept traffic into an ARC. 180 Intermediate ARC Node: A node that is not at an edge of an ARC. A 181 Intermediate ARC Node node that can receive traffic and forward 182 traffic between its adjacent nodes. 184 Intermediate Link: A link between two Intermediate ARC Nodes. An 185 Intermediate Link is reversible, meaning that traffic is allowed 186 in both directions though an individual packet is constrained in 187 the way its direction is reversed. For stable links such as wired 188 links, the typical constraint is that the direction of a packet 189 may be reversed at most once along a given ARC. 191 Collapsed ARC: An ARC that is formed of a single node. This node is 192 altogether the cursor and both Edge Nodes. This implies that the 193 node has at least 2 outgoing links to 2 different Safe Nodes. 195 | 196 | 197 V 198 C+EAN 199 /|\ 200 / | \ 201 | V | 202 V V 204 E: Edge ARC Node -| collapsed in a single node 205 C: Cursor -| 207 Figure 1: Collapsed ARC 209 Infrastructure ARC: An ARC that is formed of more than one node, 210 which also means that the Edge Nodes are different nodes. 212 | \ | | 213 | \ | | | 214 V V V | 215 _->IAN<---->IAN<---->IAN<---->IAN<-_ | 216 / + C \ | 217 / \| 218 V V 219 EAN EAN 220 | /|\ 221 | / | \ 222 | | V | 223 V V V 225 IAN: Intermediate ARC Node -| 226 EAN: Edge ARC Node |- All are Safe Nodes 227 C: Cursor -| 229 Figure 2: Infrastructure ARC 231 DAG: Directed Acyclic Graph. 233 ARC Set (or Cascade): A DAG with ARCs as vertices. In the DAG, an 234 edge between ARC A and ARC B corresponds to a link from an Edge 235 ARC Node in ARC A and an arbitrary ARC Node in ARC B. Note that by 236 definition, an ARC has at least 2 outgoing Edge Links, one per 237 Edge Node, and maybe more if an Edge Node has multiple outgoing 238 Edge Links. All vertices in the DAG have 2 forwarding solutions, 239 even the ARC closest to the destination. 241 Omega: the abstract destination (== root) of an ARC Set. 243 ARC Height: An arbitrary distance from Omega that is associated to 244 an ARC. The Height of an ARC must be more than the Height of any 245 of the ARCs it terminates into. The order of ARC formation by a 246 given algorithm can be used as a Height whereby an ARC is always 247 strictly higher or lower than another. 249 Buttressing ARC: A split ARC that is merged into another ARC at one 250 edge. An ARC and one or more Buttressing ARCs form a Comb 251 construct that is resilient to additional breakages. A 252 Buttressing ARC may be applied to an ARC or a Comb iff traffic 253 outgoing the Buttressing ARC Edge always reaches in an ARC that is 254 lower than this ARC, or Omega. 256 | \ | | 257 | \ | | | 258 V V V | 259 _->IAN<---->IAN<---->IAN<---->IAN<-_----->IAN<-_ 260 / + C \ | \ 261 / \| \ 262 V V V 263 EAN EAN EAN 264 | /|\ | 265 | / | \ | 266 | | V | | 267 V V V V 269 Figure 3: Comb with Buttressing ARC 271 Safe Node: A node is Safe if there is no single point of failure - 272 apart from the node itself - on its way to Omega. From this 273 definition, a node is Safe if it has at least two non-congruent 274 paths to two different other Safe Nodes. It results that a Safe 275 node that is not Omega has at least two completely disjunct paths 276 to Omega. When an ARC has been successfully constructed, all its 277 nodes become safe with respect to the Omega for which the ARC was 278 constructed. By extension for a collapsed path Omega is deemed to 279 be Safe, that is any node that pertains in Omega is a Safe Node. 281 ?-S: A node N is deemed dependent on a node S or S-dependent 282 (denoted as ?-S) if S is the last single point of failure along 283 N's shortest path to Omega. 285 3. ARC Set representations 287 An ARC Set can be represented in a number of fashions: 289 Graph View: 291 H2<==>H<==>H1<---I--->J1<==>J--->K1<===>K 292 | | | | | 293 | | | | | 294 V V V V V 295 D1<==>D<==>D3 E1<==>E F1<==>F<==>F2 G 296 | | | | | | / \ 297 | | | | | | / \ 298 V V V V V V V V 299 B1<==>B2<==>B3<==>B--->A<==>A1<------C2<==>C<==>C4 300 | | | | 301 | | | | 302 | V V | 303 +--------------------> Omega <-------------------+ 305 Figure 4: Routing Graph View 307 This representation is similar to a classical routing graph with 308 the pecularity that some Links are marked reversible. An ARC is 309 represented as a sequence of reversible links. The node that 310 holds the cursor is also indicated somehow. 312 ARC View: 314 +========I========+ 315 | | 316 | +====J====+ 317 | | | 318 +====H====+ | +=====K=====+ 319 | | | | | 320 +====D====+ +====E====+ +====F====+ +====G====+ 321 | | | | | | | | 322 +=========B=========+ | | +=========C=========+ 323 | | | | | | 324 | +======A=======+ | 325 | | | | 326 ------------------------------------------------------------------Omega 328 Figure 5: ARC Representation 330 This representation is similar to a classical routing graph with 331 the pecularity that some Links are marked reversible. An ARC is 332 represented as a sequence of reversible links. 334 Collapsed DAG view: 336 +====+ +====+ +====+ +====+ 337 | H | <--- | I | ---> | J | ---> | K | 338 | \__ | ___/ | 339 | \ | / | 340 V _| V |_ V 341 +====+ +====+ +====+ +====+ 342 | D | | E | | F | <--- | G | 343 \ \ __/ \__ __/ \__ / / 344 \ \ / \ / \ / / 345 _| _| |_ _| |_ _| |_ |_ 346 +====+ +====+ +====+ 347 | B | ---> | A | <--- | C | 348 | | | | 349 V V V V 350 ------------------------------------------------------------------Omega 352 Figure 6: ARC DAG 354 A DAG representation whereby an ARC is abstracted as a vertice and 355 links between ARCs are shown as directed edges. This way, the 356 reversible links are omitted and the graph is simplified. It can 357 be noted that even the vertice closest to Omega has 2 non- 358 congruent forwarding solutions, that is Heir Links to Omega. 360 4. Applicability 362 This section has to be refined. ARCs probbaly apply to both unicast 363 and multicast and the authors expect further documents to explain how 364 that is done. The examples below are provided as an indication but 365 is not limiting the field of applications. 367 4.1. Load Balancing 369 In normal conditions, only the cursor may distribute its traffic 370 between the two Edge Nodes. If an Edge Node is still congested after 371 the cursor forwards all its traffic towards the other Edge Node, then 372 the cursor can be moved towards the congested Edge in order to derive 373 even more traffic towards the other Edge. If both Edges are 374 congested, then a backpressure can be applied on the incoming ARCs so 375 that they move their own traffic towards their own alternate Edge. 376 The process may recurse. 378 4.1.1. Routing Hierarchies 380 The ARC methods may be used to build and/or leverage routing 381 hierarchies, allowing high availability at multiple hierarchical 382 levels. In one hand, the view of an ARC Set can be simplified by 383 abstracting an ARC as a node in a DAG. The view of the routing 384 topology is thus simplified, as illustrated in Figure 6. In the 385 other hand, ARCs may be used inside a subtopology, such as a ring, to 386 enable forwarding inside a ring towards a next ring. Then, 387 abstracting a full ring as a node, ARCs can be applied to a graph of 388 rings, providing another level of redundancy and an abstract end to 389 end path computation that is represented as a cascade of ARCs of 390 rings. 392 5. Lowest ARC First 394 The open Lowest ARC First(oLAF) algorithm is presented below in such 395 a way as to help the reader figure how an ARC Set can be obtained but 396 not in a computer-optimized fashion that is left to be determined. 397 oLAF is based on Dijkstra's algorithm for Shortest Path First (SPF) 398 computation, and is designed in such a fashion that the reverse SPF 399 tree towards a destination is conserved and preferred for forwarding 400 along the resulting ARC Set. 402 We make the computation on behalf of Omega, that is an abstraction, 403 but could represent the node or the set of nodes that we want to 404 reach with an ARC Set. If Omega is instantiated as an actual 405 destination node, then that node may be a fine location for an ARC 406 Computing Engine. 408 5.1. Init 410 So we start with an proverbial Initial Set of Nodes that are 411 interconnected by Links, and Omega that is the destination that we 412 want to reach with an ARC Set. 414 If there is no Heir, we're done. If there is a single Heir then the 415 graph is monoconnected, so we restart the computation taking that 416 Heir off the Set of Nodes and making it Omega. 418 Else, if Omega is a single Node, or if Omega is composed of multiple 419 nodes but we are willing to accept that both ends of an ARC terminate 420 in a same node in Omega, then we create virtual Omega nodes, a 421 minimum of two and at most one per Heir, and we make them the new 422 Omega. Note: we need at least two destinations because both ends of 423 an ARC cannot terminate in a same node. 425 Now we can start building an ARC Set towards the resulting Omega. 427 In this process, we create so-called Dependent Sets of nodes, each 428 owned by a Safe Node S, DSet(S). DSet(S) contains nodes that are not 429 determined to be Safe at the current stage of the computation and for 430 which S, the owner Safe Node, is the last single point of failure on 431 the shortest path tree to Omega. It results that a given node can be 432 at most in one DSet, and that a Safe Node belongs to its own DSet. 434 For each node S in Omega we create a DSet(S) in which we place S. 436 5.2. Growing Trees 438 And then the process goes like this: 440 We select the node in the Set of Nodes that is closest to Omega using 441 the cost towards Omega as if we were building a traditional reverse 442 SPF tree and we place the selected node in the same Dependent Set as 443 its parent in the reverse SPF tree. Note that for a Heir, the parent 444 might be a real node in Omega, or a virtual Omega node. 446 If we kept it at that, we would be building subtrees that are hanging 447 off a Safe Node and together would represent the reverse shortest 448 path tree towards Omega, each subtree being grown separately inside 449 DSet(S) where S is the (virtual) Safe node that is the root of the 450 subtree. 452 5.3. Being Safe 454 But once we have placed the selected node in a DSet, we consider its 455 neighbors one by one. If at least one of the neighbors is already in 456 a different DSet than this node, we select the neighbor that provides 457 the shortest alternate path to Omega for the selected node. 459 Doing so, we have isolated two paths: 461 o one along its own shortest path that is contained within its own 462 Dependent Set and that leads to the owner Safe Node of this set. 464 o and one via the selected neighbor, along its own shortest path 465 within the selected neighbor's Dependent Set and that leads to the 466 owner Safe Node of that other set. 468 Because the two sets are different and have no intersection, these 469 paths are non-congruent. And because the two non-congruent paths 470 lead to two different Safe Nodes, this node is Safe. 472 It might happen that: 474 o the selected node's parent is already a Safe Node, in which case 475 the selected node is the Edge AN on its shortest path side. 477 o It might also happen that the selected neighbor is already a Safe 478 Node, in which case selected node is the Edge AN on its alternate 479 side. 481 If both conditions are met for a same AN, then that AN forms a 482 collapsed ARC by itself. 484 5.4. Bending An ARC 486 Now we form an ARC as follows: 488 o A height is attributed to this ARC that must be strictly more than 489 that of the ARCs it terminates into, if any. The order in which 490 the ARCs are built may be used in some cases. 492 o The ARC terminates in the two Safe Nodes that are the owners of 493 the two DSets. The normal behaviour is to make a Edge Link the 494 link to the Safe Node. 496 o If the Safe Node at one end forms a collapsed ARC by itself, it 497 may be absorbed in the ARC in order to build a multi-edged ARC. 499 o If one of the two Safe Nodes pertains in a ARC or a Comb construct 500 that is higher than the other end, then this ARC may be merged at 501 the Safe Node with its original ARC, in order to form a Comb 502 construct whereby this ARC is a Buttressing ARC of the Comb. The 503 resulting Comb conserves the height on the original ARC or Comb 504 that it extends. 506 o The ARC is built by adjoining the two non-congruent paths that we 507 isolated for the selected node. 509 o The selected node is the node farthest from Omega in the resulting 510 ARC, so we make it the cursor. 512 o The link between the selected node and the selected neighbor would 513 not have been used in a classical reverse SPF tree. Here, we have 514 determined that this link is in fact critical to connect 2 zones 515 of the network (the DSets) that can act as a back up for one 516 another in case of the failure of their respective single points 517 of failure (the Safe Nodes). 519 o Because the ARC can be used in both directions, each AN along the 520 ARC has two non-congruent paths to the Safe Nodes that the ARC 521 terminates into. So it is a Safe Node. We create individual 522 DSets for each AN and we move the AN to its own DSet. 524 5.5. Orienting Links 526 For each ARC Node along the ARC: 528 o any link (there can be zero for a collapsed ARC, one for an Edge 529 AN or two of them for a Intermediate AN) between this AN and a 530 next AN along this ARC is made an Intermediate Link, that is, 531 reversible. The normal direction, away from the cursor, preserves 532 the shortest path. 534 o If this AN is an Edge AN for this ARC, than all links off this 535 node that terminate in a Safe Node are made Edge Links, that is, 536 outgoing but not reversible. 538 o All the other links left undertermined. 540 The nodes left in the Dependent Sets but the owner Safe Node are 541 still not Safe. They are moved back to the original Set of Nodes to 542 enable forming additional ARCs which might depend on this ARC in the 543 ARC Set. 545 5.6. Looping or recursing 547 We are done processing the particular node we had picked in the 548 original Set of Nodes. If the Set of Nodes as it stands now is not 549 empty, we continue from Section 5.2. 551 If the Set of Nodes went empty, we are done with this pass and we 552 consider the Dependent Sets that we have put together. In a 553 biconnected graph, there should be one set per node and one node per 554 set, denoting that every node is a Safe Node. 556 If some portion of the graph is monoconnected, then each 557 monoconnected portion forms the Dependent Set of the Safe Node that 558 is its single point of failure. In order to be maximally redundant, 559 we need to form the ARCs again, within the Dependent Set. 561 To do so, we remove the Safe Node from the Dependent set and make it 562 Omega. We make the resulting DSet our Set of Nodes and run the 563 algorithm again. 565 This may recurse a number of times if the graph has monoconnected 566 zones within others. 568 6. Forwarding Along An ARC Set 570 Under normal conditions, the traffic flows away from the cursor of 571 the current ARC and cascades into the next ARC on that side of the 572 cursor, with the Height of the current ARC decreasing monotonically 573 from ARC to ARC till Omega is reached. 575 The same goes for a generic Comb construct. When Buttressing ARCs 576 are applied on a main ARC or other Buttressing ARCs, the final 577 construct assumes the shape of a tree. The tree may be walked in 578 different manners but the shortest path requires to start going down 579 the current ARC or Buttressing ARC to its Edge. 581 In case of Label forwarding, the same recursivity is applied and a 582 multiple ARC label path is constructed. Each ARC has is own set of 583 label path per Omega, each ARC Set label path being merged into the 584 lower ARC label set, thus at the interconnection point. At minimum, 585 ARC label path should be built from the cursor toward each edge, but 586 this would require label path recompilation upon cursor move, the 587 proposed approach is then to build for the normal flow to an Omega 588 one pair of label path from edge to edge. 590 As this label construct maps the ARC topology with local significant 591 label, the Label Distribution Protocol (LDP) could be reused to 592 announce label association to neighbors on the ARC. 594 Upon a breakage inside an ARC, until a corrective action takes place, 595 some traffic will be lost. The corrective action might be either 596 operated at the control plane or the data plane, if immediate action 597 and near-zero packet loss is required. 599 6.1. Control Plane Recovery 601 Upon a first breakage in an ARC, the cursor is moved to the breakage 602 point, either a node or a link, so that traffic flows away from the 603 cursor again. 605 Upon a second breakage within a same ARC, a segment of the ARC is now 606 isolated. Both breakage points become sinks till an additional 607 corrective action, such as modifying the ARC Set, takes place. All 608 incoming links in the isolated segment are blocked , causing the 609 traffic to exit at the other end of the incoming ARCs. 611 Blocking an Edge Link in the incoming ARC may create an isolated 612 segment in the incoming ARC as well if it is a second breakage there 613 too, or if both edges of the incoming ARC tterminate in the broken 614 segment. In that case the process recurses and the broken zone can 615 be determined as the collection of the isolated segments. 617 If a segment of an ARC is getting isolated by a dual failure but that 618 ARC segment has incoming Edges then the ARC can be reversed. This 619 reversal is done by reversing of all the incoming Edges, which become 620 outgoing. The segment that was isolated now benefits from multiple 621 exits in a loop free fashion. This process might in turn isolate a 622 segment of an ARC that was incoming and the process recurses and some 623 links flap. If a real exit exits the process will stabilize, but a 624 count to infinity must be put in place to avoid a permanent flapping 625 when a whole ARC Subset is physically isolated. One may consider 626 that this process is in fact the classical link reversal technique, 627 as applied to the DAG of ARCs. 629 6.2. Data Plane Recovery 631 Upon a breakage inside an ARC, it is possible in the data plane to 632 reverse the direction of -to turn- a given packet once along the ARC 633 so the packets exits over the other Edge Link. But in order to avoid 634 loops, it is undesirable to reverse the direction of a given packet a 635 second time. 637 Note that once a given packet leaves an ARC to enter the next, it is 638 free to bounce again in the next ARC. In other Words, the domain 639 that is impacted by a turn is limited to the current ARC itself; the 640 ARC forms the event horizon wherein the notion that a turn happened 641 may cause a loop. 643 So a local strategy must be put in place inside an ARC to allow a 644 given packet to bounce once upon a breakage, and get dropped upon a 645 second breakage. 647 In the case of IP packet forwarding, a packet can be tagged when it 648 bounces inside an ARC, or when it passes the cursor, for instance by 649 reserving a TOS bit for that purpose. When the packet bounces, the 650 bit is set and when the packet leaves the ARC, the bit is reset and 651 may be used again in the next ARC. In the generic case of a Comb, a 652 strategy must be put in place to walk the structure and drop a packet 653 that tries all the Edges. it attempts to pass the cursor twice in a 654 same direction, meaning that more than a full walk was already 655 accomplished. 657 In the case of MPLS forwarding, the same result can be achieved with 658 either 3 or 4 Labels Switched Paths (LSPs) along the ARC. 660 3-Labels method: In this case we lay a primary LSP from the cursoo 661 to the Edge in each direction, and a backup LSP Edge to Edge in 662 each direction. So a node along the way has three labels, one 663 primary and two backup, one in each direction. Should the primary 664 path fail, the packet can be placed along the backup LSP in the 665 other direction. We'll note that this method contrains the 666 location of the cursor. Should the cursor move, The primary LSPs 667 have to be recomputed, at a minimum between the old and the new 668 location of the cursor where the direction is reversed. 670 4-Labels method: In this case we have two primary and two backup 671 LSPs Edge to Edge in each direction. The labels are independent 672 of the location of the cursor, so the cursor can be moved in 673 control plane with no impact on labels. 675 7. Manageability 677 This specification describes a generic model. Protocols and 678 management will come later 680 8. IANA Considerations 682 This specification does not require IANA action. 684 9. Security Considerations 686 This specification is not found to introduce new security threat. 688 10. Acknowledgements 690 The authors wishes to thank Dirk Anteunis, Stewart Bryant, IJsbrand 691 Wijnands, George Swallow, Eric Osborne, Clarence Filsfils and Eric 692 Levy-Abegnoli for their participation and continuous support to the 693 work presented here. 695 11. References 697 11.1. Normative References 699 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 700 Requirement Levels", BCP 14, RFC 2119, March 1997. 702 [RFC4291] Hinden, R. and S. Deering, "IP Version 6 Addressing 703 Architecture", RFC 4291, February 2006. 705 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 706 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 707 September 2007. 709 [RFC4862] Thomson, S., Narten, T., and T. Jinmei, "IPv6 Stateless 710 Address Autoconfiguration", RFC 4862, September 2007. 712 11.2. Informative References 714 [I-D.phinney-roll-rpl-industrial-applicability] 715 Phinney, T., Thubert, P., and R. Assimiti, "RPL 716 applicability in industrial networks", 717 draft-phinney-roll-rpl-industrial-applicability-00 (work 718 in progress), October 2011. 720 [I-D.thubert-lowpan-backbone-router] 721 Thubert, P., "LoWPAN Backbone Router", 722 draft-thubert-lowpan-backbone-router-00 (work in 723 progress), November 2007. 725 [RFC4191] Draves, R. and D. Thaler, "Default Router Preferences and 726 More-Specific Routes", RFC 4191, November 2005. 728 [RFC4541] Christensen, M., Kimball, K., and F. Solensky, 729 "Considerations for Internet Group Management Protocol 730 (IGMP) and Multicast Listener Discovery (MLD) Snooping 731 Switches", RFC 4541, May 2006. 733 [RFC5213] Gundavelli, S., Leung, K., Devarapalli, V., Chowdhury, K., 734 and B. Patil, "Proxy Mobile IPv6", RFC 5213, August 2008. 736 [RFC5415] Calhoun, P., Montemurro, M., and D. Stanley, "Control And 737 Provisioning of Wireless Access Points (CAPWAP) Protocol 738 Specification", RFC 5415, March 2009. 740 [RFC5865] Baker, F., Polk, J., and M. Dolly, "A Differentiated 741 Services Code Point (DSCP) for Capacity-Admitted Traffic", 742 RFC 5865, May 2010. 744 [RFC5921] Bocci, M., Bryant, S., Frost, D., Levrau, L., and L. 745 Berger, "A Framework for MPLS in Transport Networks", 746 RFC 5921, July 2010. 748 [RFC6275] Perkins, C., Johnson, D., and J. Arkko, "Mobility Support 749 in IPv6", RFC 6275, July 2011. 751 [RFC6550] Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R., 752 Levis, P., Pister, K., Struik, R., Vasseur, JP., and R. 753 Alexander, "RPL: IPv6 Routing Protocol for Low-Power and 754 Lossy Networks", RFC 6550, March 2012. 756 Authors' Addresses 758 Pascal Thubert (editor) 759 Cisco Systems 760 Village d'Entreprises Green Side 761 400, Avenue de Roumanille 762 Batiment T3 763 Biot - Sophia Antipolis 06410 764 FRANCE 766 Phone: +33 497 23 26 34 767 Email: pthubert@cisco.com 769 Patrice Bellagamba 770 Cisco Systems 771 214 Avenue des fleurs 772 Saint-Raphael 83700 773 FRANCE 775 Phone: +33.6.1998.4346 776 Email: pbellaga@cisco.com