idnits 2.17.00 (12 Aug 2021) /tmp/idnits47780/draft-thubert-rtgwg-arc-02.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 (July 2, 2014) is 2880 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) No issues found here. Summary: 0 errors (**), 0 flaws (~~), 2 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 Cisco 4 Intended status: Standards Track P. Bellagamba 5 Expires: January 3, 2015 Cisco Systems 6 July 2, 2014 8 Available Routing Constructs 9 draft-thubert-rtgwg-arc-02 11 Abstract 13 This draft introduces the concept of ARC, a two-edged routing 14 construct that forms its own fault isolation and recovery domain. 15 The new paradigm can be leveraged to improve the network utilization 16 and resiliency for unicast and multicast traffic in multiple 17 environments. 19 Requirements Language 21 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 22 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 23 "OPTIONAL" in this document are to be interpreted as described in RFC 24 2119 [RFC2119]. 26 Status of This Memo 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF). Note that other groups may also distribute 33 working documents as Internet-Drafts. The list of current Internet- 34 Drafts is at http://datatracker.ietf.org/drafts/current/. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 This Internet-Draft will expire on January 3, 2015. 43 Copyright Notice 45 Copyright (c) 2014 IETF Trust and the persons identified as the 46 document authors. All rights reserved. 48 This document is subject to BCP 78 and the IETF Trust's Legal 49 Provisions Relating to IETF Documents 50 (http://trustee.ietf.org/license-info) in effect on the date of 51 publication of this document. Please review these documents 52 carefully, as they describe your rights and restrictions with respect 53 to this document. Code Components extracted from this document must 54 include Simplified BSD License text as described in Section 4.e of 55 the Trust Legal Provisions and are provided without warranty as 56 described in the Simplified BSD License. 58 Table of Contents 60 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 61 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 62 3. ARC Set representations . . . . . . . . . . . . . . . . . . . 7 63 4. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 9 64 4.1. Load Balancing . . . . . . . . . . . . . . . . . . . . . 9 65 4.1.1. Routing Hierarchies . . . . . . . . . . . . . . . . . 10 66 5. Lowest ARC First . . . . . . . . . . . . . . . . . . . . . . 10 67 5.1. Init . . . . . . . . . . . . . . . . . . . . . . . . . . 10 68 5.2. Growing Trees . . . . . . . . . . . . . . . . . . . . . . 11 69 5.3. Being Safe . . . . . . . . . . . . . . . . . . . . . . . 11 70 5.4. Bending An ARC . . . . . . . . . . . . . . . . . . . . . 12 71 5.5. Orienting Links . . . . . . . . . . . . . . . . . . . . . 13 72 5.6. Looping or recursing . . . . . . . . . . . . . . . . . . 13 73 6. Forwarding Along An ARC Set . . . . . . . . . . . . . . . . . 14 74 6.1. Control Plane Recovery . . . . . . . . . . . . . . . . . 14 75 6.2. Data Plane Recovery . . . . . . . . . . . . . . . . . . . 15 76 7. Manageability . . . . . . . . . . . . . . . . . . . . . . . . 16 77 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16 78 9. Security Considerations . . . . . . . . . . . . . . . . . . . 16 79 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 16 80 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 16 81 11.1. Normative References . . . . . . . . . . . . . . . . . . 16 82 11.2. Informative References . . . . . . . . . . . . . . . . . 17 83 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 17 85 1. Introduction 87 Traditional routing and forwarding uses the concept of path as the 88 basic routing paradigm to get a packet from a source to a destination 89 by following an ordered sequence of arrows between intermediate 90 nodes. In this serial design, a path is broken as soon as a single 91 arrow is, and getting around a breakage can require path 92 recomputation, network reconvergence, and incur delays to till 93 service is restored. 95 Multiple paths can be bound together for instance to form a Directed 96 Acyclic Graph (DAG) to a destination, but that technique can be 97 difficult to balance and cannot provide a full path redundancy even 98 in the case of a biconnected graph. For instance, if the node that 99 is closest to the DAG destination has only one link to that 100 destination, then it does not have a alternate path to get to that 101 destination. 103 It is also possible to compute an alternate routing topology for fast 104 rerouting to a given destination, in which case some signalling, 105 tagging or labelling can be put in place to indicate whether a packet 106 follows the normal path or was rerouted over an alternate topology. 107 Once a packet is rerouted, it is bound to the alternate topology so 108 only one breakage can be handled with looplessness guarantees in most 109 practical situations. 111 This draft introduces the concept of an Available Routing Construct 112 (ARC) as a routing construct made of a bidirectional sequence of 113 nodes and links with 2 outgoing edges, so that, upon a single 114 breakage, each lively node in along ARC can still reach one of the 115 outgoing edges. 117 The routing graph to reach a certain destination is expressed as a 118 cascade of ARCs, each ARC providing its own independent domain of 119 fault isolation and recovery. Unicast traffic may enter an ARC via 120 any node but it may only leave the ARC through one of its two edges. 121 One node along the ARC is designated as the Cursor. In normal 122 unicast operations, the traffic inside an ARC flows away from the 123 Cursor towards an edge. Upon a failure, packets may bounce on the 124 breakage point and flow the other way along the ARC to take the other 125 exit. 127 Aa a result an ARC is resilient to any single failure, and the 128 recovery can be driven either from the data plane or the control 129 plane. A second failure occurring within a same ARC will isolate an 130 ARC segment. This can be further corrected from the control plane by 131 reversing all the incoming Edges in a process that might recurse till 132 an exit is found. When ARC reversal is applied, an ARC topology is 133 resilient to some cases of Shared Risk Link Group (SRLG) failures. 135 This draft presents the concept and provides an intuition of how ARCs 136 can simplify the operation and improve the network utilization and 137 resiliency for all sorts of traffic in multiple environments, but 138 defers to further documents to elaborate on the algorithms and 139 optimizations in the different application domains. 141 For instance, ARCs can also be used in datacenters for the purpose of 142 fast-reroute, or within a service provider network to simplify load 143 balancing operations or leverage optimally the ring topologies 144 [RFC5921]. An ARC topology can be flooded over itself and serve as a 145 backbone for bicasted [I-D.thubert-rtgwg-arc-bicast] and reliable 146 multicasted operations. 148 2. Terminology 150 The definition of the constituent parts of the "OAM" term is found in 151 [RFC6291]. 153 The draft uses the following terminology: 155 ARC: Available Routing Construct. An ARC is a loopless ordered set 156 of nodes and links whereby traffic may enter via any node in the 157 ARC but may only leave the ARC through either one of the ARC 158 edges. 160 Comb: An ARC generalization: a Comb is a n-edged loopless set of 161 nodes and links with n >= 2; traffic may enter via any node in the 162 Comb but may only exit the Comb through one of its n edges. A 163 Comb comes with a walk operation that enables to attempt to exit 164 via every edge and to discover when all have been tried. 166 Cursor: A virtual point along an ARC that can be located on a node 167 or on a link between 2 nodes. In normal operations, the traffic 168 along the ARC flows away from its Cursor. If the Cursor is a 169 node, then traffic can be distributed on both sides. The Cursor 170 may be moved to change the way traffic is load balanced along an 171 ARC. It may also be placed at the location of a failure to direct 172 traffic away from that point. 174 ARC Node: A Node that belongs to an ARC. 176 Edge ARC Node: An ARC Node at an edge of its ARC. An Edge ARC Node 177 is a node via wich traffic can exit the ARC. 179 Edge Link: A directed link outgoing from an Edge ARC Node. Traffic 180 can only exit from an ARC via an Edge Link. An Edge Link does not 181 accept traffic into an ARC. 183 Intermediate ARC Node: A node that is not at an edge of an ARC. A 184 Intermediate ARC Node node that can receive traffic and forward 185 traffic between its adjacent nodes. 187 Intermediate Link: A link between two Intermediate ARC Nodes. An 188 Intermediate Link is reversible, meaning that traffic is allowed 189 in both directions though an individual packet is constrained in 190 the way its direction is reversed. For stable links such as wired 191 links, the typical constraint is that the direction of a packet 192 may be reversed at most once along a given ARC. 194 Collapsed ARC: An ARC that is formed of a single node. This node is 195 altogether the Cursor and both Edge Nodes. This implies that the 196 node has at least 2 outgoing links to 2 different Safe Nodes. 198 | 199 | 200 V 201 C+EAN 202 /|\ 203 / | \ 204 | V | 205 V V 207 E: Edge ARC Node -| collapsed in a single node 208 C: Cursor -| 210 Figure 1: Collapsed ARC 212 Infrastructure ARC: An ARC that is formed of more than one node, 213 which also means that the Edge Nodes are different nodes. 215 | \ | | 216 | \ | | | 217 V V V | 218 _->IAN<---->IAN<---->IAN<---->IAN<-_ | 219 / + C \ | 220 / \| 221 V V 222 EAN EAN 223 | /|\ 224 | / | \ 225 | | V | 226 V V V 228 IAN: Intermediate ARC Node -| 229 EAN: Edge ARC Node |- All are Safe Nodes 230 C: Cursor -| 232 Figure 2: Infrastructure ARC 234 DAG: Directed Acyclic Graph. 236 ARC Set (or Cascade): A DAG with ARCs as vertices. In the DAG, an 237 edge between ARC A and ARC B corresponds to a link from an Edge 238 ARC Node in ARC A and an arbitrary ARC Node in ARC B. Note that 239 by definition, an ARC has at least 2 outgoing Edge Links, one per 240 Edge Node, and maybe more if an Edge Node has multiple outgoing 241 Edge Links. All vertices in the DAG have 2 forwarding solutions, 242 even the ARC closest to the destination. 244 Omega: the abstract destination (== root) of an ARC Set. 246 ARC Height: An arbitrary distance from Omega that is associated to 247 an ARC. The Height of an ARC must be more than the Height of any 248 of the ARCs it terminates into. The order of ARC formation by a 249 given algorithm can be used as a Height whereby an ARC is always 250 strictly higher or lower than another. 252 Buttressing ARC: A split ARC that is merged into another ARC at one 253 edge. An ARC and one or more Buttressing ARCs form a Comb 254 construct that is resilient to additional breakages. A 255 Buttressing ARC may be applied to an ARC or a Comb iff traffic 256 outgoing the Buttressing ARC Edge always reaches in an ARC that is 257 lower than this ARC, or Omega. 259 | \ | | 260 | \ | | | 261 V V V | 262 _->IAN<---->IAN<---->IAN<---->IAN<-_----->IAN<-_ 263 / + C \ | \ 264 / \| \ 265 V V V 266 EAN EAN EAN 267 | /|\ | 268 | / | \ | 269 | | V | | 270 V V V V 272 Figure 3: Comb with Buttressing ARC 274 Safe Node: A node is Safe if there is no single point of failure - 275 apart from the node itself - on its way to Omega. From this 276 definition, a node is Safe if it has at least two non-congruent 277 paths to two different other Safe Nodes. It results that a Safe 278 node that is not Omega has at least two completely disjunct paths 279 to Omega. When an ARC has been successfully constructed, all its 280 nodes become safe with respect to the Omega for which the ARC was 281 constructed. By extension for a collapsed path Omega is deemed to 282 be Safe, that is any node that pertains in Omega is a Safe Node. 284 ?-S: A node N is deemed dependent on a node S or S-dependent 285 (denoted as ?-S) if S is the last single point of failure along 286 N's shortest path to Omega. 288 3. ARC Set representations 290 An ARC Set can be represented in a number of fashions: 292 Graph View: 294 H2<==>H<==>H1<---I--->J1<==>J--->K1<===>K 295 | | | | | 296 | | | | | 297 V V V V V 298 D1<==>D<==>D3 E1<==>E F1<==>F<==>F2 G 299 | | | | | | / \ 300 | | | | | | / \ 301 V V V V V V V V 302 B1<==>B2<==>B3<==>B--->A<==>A1<------C2<==>C<==>C4 303 | | | | 304 | | | | 305 | V V | 306 +--------------------> Omega <-------------------+ 308 Figure 4: Routing Graph View 310 This representation is similar to a classical routing graph with 311 the pecularity that some Links are marked reversible. An ARC is 312 represented as a sequence of reversible links. The node that 313 holds the Cursor is also indicated somehow. 315 ARC View: 317 +========I========+ 318 | | 319 | +====J====+ 320 | | | 321 +====H====+ | +=====K=====+ 322 | | | | | 323 +====D====+ +====E====+ +====F====+ +====G====+ 324 | | | | | | | | 325 +=========B=========+ | | +=========C=========+ 326 | | | | | | 327 | +======A=======+ | 328 | | | | 329 ------------------------------------------------------------------Omega 331 Figure 5: ARC Representation 333 This representation is similar to a classical routing graph with 334 the pecularity that some Links are marked reversible. An ARC is 335 represented as a sequence of reversible links. 337 Collapsed DAG view: 339 +====+ +====+ +====+ +====+ 340 | H | <--- | I | ---> | J | ---> | K | 341 | \__ | ___/ | 342 | \ | / | 343 V _| V |_ V 344 +====+ +====+ +====+ +====+ 345 | D | | E | | F | <--- | G | 346 \ \ __/ \__ __/ \__ / / 347 \ \ / \ / \ / / 348 _| _| |_ _| |_ _| |_ |_ 349 +====+ +====+ +====+ 350 | B | ---> | A | <--- | C | 351 | | | | 352 V V V V 353 ------------------------------------------------------------------Omega 355 Figure 6: ARC DAG 357 A DAG representation whereby an ARC is abstracted as a vertice and 358 links between ARCs are shown as directed edges. This way, the 359 reversible links are omitted and the graph is simplified. It can 360 be noted that even the vertice closest to Omega has 2 non- 361 congruent forwarding solutions, that is Heir Links to Omega. 363 4. Applicability 365 This section has to be refined. ARCs probably apply to both unicast 366 and multicast and the authors expect further documents to explain how 367 that is done. The examples below are provided as an indication but 368 is not limiting the field of applications. 370 4.1. Load Balancing 372 In normal conditions, only the Cursor may distribute its traffic 373 between the two Edge Nodes. If an Edge Node is still congested after 374 the Cursor forwards all its traffic towards the other Edge Node, then 375 the Cursor can be moved towards the congested Edge in order to derive 376 even more traffic towards the other Edge. If both Edges are 377 congested, then a back-pressure can be applied on the incoming ARCs 378 so that they move their own traffic towards their own alternate Edge. 379 The process may recurse. 381 It is expected that control frames similar to those defined for MPLS 382 Fault Management Operations, Administration, and Maintenance (OAM) 383 [RFC6291] will echo from Edge Node to Edge Node provide information 384 such as liveliness and load. In order to establish a control loop 385 between the Edge Nodes and the Cursor, the OAM frame would carry at 386 least a logical information whether: 388 The Edge Node is capable of forwarding data down to the next ARC 390 the load may be increased (e.g. rate below threshold including 391 hysteresis) 393 the load should be decreased (e.g. congestion observed as 394 increased latency or buffer bloat) 396 If the load should be decreased towards of congested Edge Node and 397 the load may be increased towards the other then the Cursor may 398 adjust its balancing of the load, or move Cursor ownership towards 399 the congested Edge if it is already redirecting all the traffic 400 towards the non-congested Edge. 402 If the Cursor is balancing traffic away from the default position due 403 to a past congestion notification and the Edge that was congested now 404 reports that the load may be increased, then the reverse operation 405 can happen and the Cursor may rebalance the load back to the original 406 position taking the reverse steps as above. 408 If the OAM can not be forwarded due to a link or a node failure, then 409 the last node towards the broken Edge becomes Cursor and echoes the 410 OAM frames advertising that it is an Edge node that is blocked, not 411 capable of forwarding data down to the next ARC. 413 If both Edges are experiencing a congestion then the condition should 414 be reported to the Edge Nodes of all incoming ARCs. Same goes when 415 both Edges are blocked. 417 4.1.1. Routing Hierarchies 419 The ARC methods may be used to build and/or leverage routing 420 hierarchies, allowing high availability at multiple hierarchical 421 levels. In one hand, the view of an ARC Set can be simplified by 422 abstracting an ARC as a node in a DAG. The view of the routing 423 topology is thus simplified, as illustrated in Figure 6. In the 424 other hand, ARCs may be used inside a sub-topology, such as a ring, 425 to enable forwarding inside a ring towards a next ring. Then, 426 abstracting a full ring as a node, ARCs can be applied to a graph of 427 rings, providing another level of redundancy and an abstract end to 428 end path computation that is represented as a cascade of ARCs of 429 rings. 431 5. Lowest ARC First 433 The open Lowest ARC First(oLAF) algorithm is presented below in such 434 a way as to help the reader figure how an ARC Set can be obtained but 435 not in a computer-optimized fashion that is left to be determined. 436 oLAF is based on Dijkstra's algorithm for Shortest Path First (SPF) 437 computation, and is designed in such a fashion that the reverse SPF 438 tree towards a destination is conserved and preferred for forwarding 439 along the resulting ARC Set. 441 We make the computation on behalf of Omega, that is an abstraction, 442 but could represent the node or the set of nodes that we want to 443 reach with an ARC Set. If Omega is instantiated as an actual 444 destination node, then that node may be a fine location for an ARC 445 Computing Engine. 447 5.1. Init 449 So we start with an proverbial Initial Set of Nodes that are 450 interconnected by Links, and Omega that is the destination that we 451 want to reach with an ARC Set. 453 If there is no Heir, we're done. If there is a single Heir then the 454 graph is monoconnected, so we restart the computation taking that 455 Heir off the Set of Nodes and making it Omega. 457 Else, if Omega is a single Node, or if Omega is composed of multiple 458 nodes but we are willing to accept that both ends of an ARC terminate 459 in a same node in Omega, then we create virtual Omega nodes, a 460 minimum of two and at most one per Heir, and we make them the new 461 Omega. Note: we need at least two destinations because both ends of 462 an ARC cannot terminate in a same node. 464 Now we can start building an ARC Set towards the resulting Omega. 466 In this process, we create so-called Dependent Sets of nodes, each 467 owned by a Safe Node S, DSet(S). DSet(S) contains nodes that are not 468 determined to be Safe at the current stage of the computation and for 469 which S, the owner Safe Node, is the last single point of failure on 470 the shortest path tree to Omega. It results that a given node can be 471 at most in one DSet, and that a Safe Node belongs to its own DSet. 473 For each node S in Omega we create a DSet(S) in which we place S. 475 5.2. Growing Trees 477 And then the process goes like this: 479 We select the node in the Set of Nodes that is closest to Omega using 480 the cost towards Omega as if we were building a traditional reverse 481 SPF tree and we place the selected node in the same Dependent Set as 482 its parent in the reverse SPF tree. Note that for a Heir, the parent 483 might be a real node in Omega, or a virtual Omega node. 485 If we kept it at that, we would be building subtrees that are hanging 486 off a Safe Node and together would represent the reverse shortest 487 path tree towards Omega, each subtree being grown separately inside 488 DSet(S) where S is the (virtual) Safe node that is the root of the 489 subtree. 491 5.3. Being Safe 493 But once we have placed the selected node in a DSet, we consider its 494 neighbors one by one. If at least one of the neighbors is already in 495 a different DSet than this node, we select the neighbor that provides 496 the shortest alternate path to Omega for the selected node. 498 Doing so, we have isolated two paths: 500 o one along its own shortest path that is contained within its own 501 Dependent Set and that leads to the owner Safe Node of this set. 503 o and one via the selected neighbor, along its own shortest path 504 within the selected neighbor's Dependent Set and that leads to the 505 owner Safe Node of that other set. 507 Because the two sets are different and have no intersection, these 508 paths are non-congruent. And because the two non-congruent paths 509 lead to two different Safe Nodes, this node is Safe. 511 It might happen that: 513 o the selected node's parent is already a Safe Node, in which case 514 the selected node is the Edge AN on its shortest path side. 516 o It might also happen that the selected neighbor is already a Safe 517 Node, in which case selected node is the Edge AN on its alternate 518 side. 520 If both conditions are met for a same AN, then that AN forms a 521 collapsed ARC by itself. 523 5.4. Bending An ARC 525 Now we form an ARC as follows: 527 o A height is attributed to this ARC that must be strictly more than 528 that of the ARCs it terminates into, if any. The order in which 529 the ARCs are built may be used in some cases. 531 o The ARC terminates in the two Safe Nodes that are the owners of 532 the two DSets. The normal behaviour is to make a Edge Link the 533 link to the Safe Node. 535 o If the Safe Node at one end forms a collapsed ARC by itself, it 536 may be absorbed in the ARC in order to build a multi-edged ARC. 538 o If one of the two Safe Nodes pertains in a ARC or a Comb construct 539 that is higher than the other end, then this ARC may be merged at 540 the Safe Node with its original ARC, in order to form a Comb 541 construct whereby this ARC is a Buttressing ARC of the Comb. The 542 resulting Comb conserves the height on the original ARC or Comb 543 that it extends. 545 o The ARC is built by adjoining the two non-congruent paths that we 546 isolated for the selected node. 548 o The selected node is the node farthest from Omega in the resulting 549 ARC, so we make it the Cursor. 551 o The link between the selected node and the selected neighbor would 552 not have been used in a classical reverse SPF tree. Here, we have 553 determined that this link is in fact critical to connect 2 zones 554 of the network (the DSets) that can act as a back up for one 555 another in case of the failure of their respective single points 556 of failure (the Safe Nodes). 558 o Because the ARC can be used in both directions, each AN along the 559 ARC has two non-congruent paths to the Safe Nodes that the ARC 560 terminates into. So it is a Safe Node. We create individual 561 DSets for each AN and we move the AN to its own DSet. 563 5.5. Orienting Links 565 For each ARC Node along the ARC: 567 o any link (there can be zero for a collapsed ARC, one for an Edge 568 AN or two of them for a Intermediate AN) between this AN and a 569 next AN along this ARC is made an Intermediate Link, that is, 570 reversible. The normal direction, away from the Cursor, preserves 571 the shortest path. 573 o If this AN is an Edge AN for this ARC, than all links off this 574 node that terminate in a Safe Node are made Edge Links, that is, 575 outgoing but not reversible. 577 o All the other links left undertermined. 579 The nodes left in the Dependent Sets but the owner Safe Node are 580 still not Safe. They are moved back to the original Set of Nodes to 581 enable forming additional ARCs which might depend on this ARC in the 582 ARC Set. 584 5.6. Looping or recursing 586 We are done processing the particular node we had picked in the 587 original Set of Nodes. If the Set of Nodes as it stands now is not 588 empty, we continue from Section 5.2. 590 If the Set of Nodes went empty, we are done with this pass and we 591 consider the Dependent Sets that we have put together. In a 592 biconnected graph, there should be one set per node and one node per 593 set, denoting that every node is a Safe Node. 595 If some portion of the graph is monoconnected, then each 596 monoconnected portion forms the Dependent Set of the Safe Node that 597 is its single point of failure. In order to be maximally redundant, 598 we need to form the ARCs again, within the Dependent Set. 600 To do so, we remove the Safe Node from the Dependent set and make it 601 Omega. We make the resulting DSet our Set of Nodes and run the 602 algorithm again. 604 This may recurse a number of times if the graph has monoconnected 605 zones within others. 607 6. Forwarding Along An ARC Set 609 Under normal conditions, the traffic flows away from the Cursor of 610 the current ARC and cascades into the next ARC on that side of the 611 Cursor, with the Height of the current ARC decreasing monotonically 612 from ARC to ARC till Omega is reached. 614 The same goes for a generic Comb construct. When Buttressing ARCs 615 are applied on a main ARC or other Buttressing ARCs, the final 616 construct assumes the shape of a tree. The tree may be walked in 617 different manners but the shortest path requires to start going down 618 the current ARC or Buttressing ARC to its Edge. 620 In case of Label forwarding, the same recursivity is applied and a 621 multiple ARC label path is constructed. Each ARC has is own set of 622 label path per Omega, each ARC Set label path being merged into the 623 lower ARC label set, thus at the interconnection point. At minimum, 624 ARC label path should be built from the Cursor toward each edge, but 625 this would require label path recompilation upon Cursor move, the 626 proposed approach is then to build for the normal flow to an Omega 627 one pair of label path from edge to edge. 629 As this label construct maps the ARC topology with local significant 630 label, the Label Distribution Protocol (LDP) could be reused to 631 announce label association to neighbors on the ARC. 633 Upon a breakage inside an ARC, until a corrective action takes place, 634 some traffic will be lost. The corrective action might be either 635 operated at the control plane or the data plane, if immediate action 636 and near-zero packet loss is required. 638 6.1. Control Plane Recovery 640 Upon a first breakage in an ARC, the Cursor is moved to the breakage 641 point, either a node or a link, so that traffic flows away from the 642 Cursor again. 644 Upon a second breakage within a same ARC, a segment of the ARC is now 645 isolated. Both breakage points become sinks till an additional 646 corrective action, such as modifying the ARC Set, takes place. All 647 incoming links in the isolated segment are blocked , causing the 648 traffic to exit at the other end of the incoming ARCs. 650 Blocking an Edge Link in the incoming ARC may create an isolated 651 segment in the incoming ARC as well if it is a second breakage there 652 too, or if both edges of the incoming ARC tterminate in the broken 653 segment. In that case the process recurses and the broken zone can 654 be determined as the collection of the isolated segments. 656 If a segment of an ARC is getting isolated by a dual failure but that 657 ARC segment has incoming Edges then the ARC can be reversed. This 658 reversal is done by reversing of all the incoming Edges, which become 659 outgoing. The segment that was isolated now benefits from multiple 660 exits in a loop free fashion. This process might in turn isolate a 661 segment of an ARC that was incoming and the process recurses and some 662 links flap. If a real exit exits the process will stabilize, but a 663 count to infinity must be put in place to avoid a permanent flapping 664 when a whole ARC Subset is physically isolated. One may consider 665 that this process is in fact the classical link reversal technique, 666 as applied to the DAG of ARCs. 668 6.2. Data Plane Recovery 670 Upon a breakage inside an ARC, it is possible in the data plane to 671 reverse the direction of -to turn- a given packet once along the ARC 672 so the packets exits over the other Edge Link. But in order to avoid 673 loops, it is undesirable to reverse the direction of a given packet a 674 second time. 676 Note that once a given packet leaves an ARC to enter the next, it is 677 free to bounce again in the next ARC. In other Words, the domain 678 that is impacted by a turn is limited to the current ARC itself; the 679 ARC forms the event horizon wherein the notion that a turn happened 680 may cause a loop. 682 So a local strategy must be put in place inside an ARC to allow a 683 given packet to bounce once upon a breakage, and get dropped upon a 684 second breakage. 686 In the case of IP packet forwarding, a packet can be tagged when it 687 bounces inside an ARC, or when it passes the Cursor, for instance by 688 reserving a TOS bit for that purpose. When the packet bounces, the 689 bit is set and when the packet leaves the ARC, the bit is reset and 690 may be used again in the next ARC. In the generic case of a Comb, a 691 strategy must be put in place to walk the structure and drop a packet 692 that tries all the Edges. it attempts to pass the Cursor twice in a 693 same direction, meaning that more than a full walk was already 694 accomplished. 696 In the case of MPLS forwarding, the same result can be achieved with 697 either 3 or 4 Labels Switched Paths (LSPs) along the ARC. 699 3-Labels method: In this case we lay a primary LSP from the cursoo 700 to the Edge in each direction, and a backup LSP Edge to Edge in 701 each direction. So a node along the way has three labels, one 702 primary and two backup, one in each direction. Should the primary 703 path fail, the packet can be placed along the backup LSP in the 704 other direction. We'll note that this method contrains the 705 location of the Cursor. Should the Cursor move, The primary LSPs 706 have to be recomputed, at a minimum between the old and the new 707 location of the Cursor where the direction is reversed. 709 4-Labels method: In this case we have two primary and two backup 710 LSPs Edge to Edge in each direction. The labels are independent 711 of the location of the Cursor, so the Cursor can be moved in 712 control plane with no impact on labels. 714 7. Manageability 716 This specification describes a generic model. Protocols and 717 management will come later 719 8. IANA Considerations 721 This specification does not require IANA action. 723 9. Security Considerations 725 This specification is not found to introduce new security threat. 727 10. Acknowledgements 729 The authors wishes to thank Dirk Anteunis, Stewart Bryant, IJsbrand 730 Wijnands, George Swallow, Eric Osborne, Clarence Filsfils and Eric 731 Levy-Abegnoli for their participation and continuous support to the 732 work presented here. 734 11. References 736 11.1. Normative References 738 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 739 Requirement Levels", BCP 14, RFC 2119, March 1997. 741 [RFC6291] Andersson, L., van Helvoort, H., Bonica, R., Romascanu, 742 D., and S. Mansfield, "Guidelines for the Use of the "OAM" 743 Acronym in the IETF", BCP 161, RFC 6291, June 2011. 745 11.2. Informative References 747 [I-D.thubert-rtgwg-arc-bicast] 748 Thubert, P. and I. Wijnands, "Applying Available Routing 749 Constructs to bicasting", draft-thubert-rtgwg-arc- 750 bicast-01 (work in progress), October 2013. 752 [RFC5921] Bocci, M., Bryant, S., Frost, D., Levrau, L., and L. 753 Berger, "A Framework for MPLS in Transport Networks", RFC 754 5921, July 2010. 756 Authors' Addresses 758 Pascal Thubert (editor) 759 Cisco Systems, Inc 760 Building D 761 45 Allee des Ormes - BP1200 762 MOUGINS - Sophia Antipolis 06254 763 FRANCE 765 Phone: +33 497 23 26 34 766 Email: pthubert@cisco.com 768 Patrice Bellagamba 769 Cisco Systems 770 214 Avenue des fleurs 771 Saint-Raphael 83700 772 FRANCE 774 Phone: +33.6.1998.4346 775 Email: pbellaga@cisco.com