idnits 2.17.00 (12 Aug 2021) /tmp/idnits19813/draft-thubert-rtgwg-arc-vs-mrt-01.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 == Line 600 has weird spacing: '...eversal sta...' == Line 663 has weird spacing: '...tion is con...' == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (January 22, 2015) is 2669 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RFC5921' is defined on line 763, but no explicit reference was found in the text == Outdated reference: draft-ietf-rtgwg-mrt-frr-architecture has been published as RFC 7812 == Outdated reference: A later version (-03) exists of draft-thubert-rtgwg-arc-02 Summary: 0 errors (**), 0 flaws (~~), 7 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: Informational G. Enyedi 5 Expires: July 26, 2015 Ericsson 6 S. Ramasubramanian 7 UA 8 January 22, 2015 10 ARC vs. MRT 11 draft-thubert-rtgwg-arc-vs-mrt-01 13 Abstract 15 This draft compares the capabilities offered by the Available Routing 16 Construct (ARC) and the Maximally Redundant Trees (MRT) techniques in 17 order to support applicability statements. 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 July 26, 2015. 43 Copyright Notice 45 Copyright (c) 2015 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. Important Notice . . . . . . . . . . . . . . . . . . . . . . 2 61 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 62 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 63 4. Reference Topology . . . . . . . . . . . . . . . . . . . . . 5 64 5. Normal Operation . . . . . . . . . . . . . . . . . . . . . . 6 65 6. One breakage . . . . . . . . . . . . . . . . . . . . . . . . 7 66 7. Second breakage . . . . . . . . . . . . . . . . . . . . . . . 9 67 8. Summary of differences . . . . . . . . . . . . . . . . . . . 10 68 8.1. Differences between ARCs and MRT . . . . . . . . . . . . 11 69 8.2. Similarities between ARC and MRT . . . . . . . . . . . . 14 70 9. ARC specific properties . . . . . . . . . . . . . . . . . . . 14 71 9.1. Multiple related breakages . . . . . . . . . . . . . . . 14 72 9.2. Multiple Destination and Load Balancing . . . . . . . . . 15 73 9.3. Hierarchical Routing . . . . . . . . . . . . . . . . . . 16 74 9.4. Recovery from Node Failures . . . . . . . . . . . . . . . 17 75 9.5. Applied to bicasting (livelive) . . . . . . . . . . . . . 17 76 10. Manageability . . . . . . . . . . . . . . . . . . . . . . . . 17 77 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 78 12. Security Considerations . . . . . . . . . . . . . . . . . . . 17 79 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 18 80 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 18 81 14.1. Normative References . . . . . . . . . . . . . . . . . . 18 82 14.2. Informative References . . . . . . . . . . . . . . . . . 18 83 14.3. References . . . . . . . . . . . . . . . . . . . . . . . 19 84 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 19 86 1. Important Notice 88 This document compares MRT and ARCs based on 89 [I-D.enyedi-rtgwg-mrt-frr-algorithm], 90 [I-D.ietf-rtgwg-mrt-frr-architecture] , [I-D.thubert-rtgwg-arc] and 91 [I-D.thubert-rtgwg-arc-bicast] as they were on 10/12/2012. Both 92 solutions may have changed or may change in the future, which would 93 make this document somewhat outdated. 95 2. Introduction 97 Traditional routing and forwarding uses the concept of path as the 98 basic routing paradigm to get a packet from a source to a 99 destination. A path is represented as an ordered sequence of nodes. 100 This paradigm is greedy in that it requires that the next node 101 represent a progress towards the destination. Greediness is 102 maximized by Shortest Path First (SPF) techniques which optimize for 103 a cost that relates to the amount of forwarding effort and latency, 104 at the expense of network capacity and reliability. In particular, a 105 path is broken as soon as a single link or a single node fails, and 106 getting around a breakage can require path recomputation, network 107 reconvergence, and incur delays and/or microloops till service is 108 restored. 110 Maximally Redundant Trees [I-D.ietf-rtgwg-mrt-frr-architecture] 111 [I-D.enyedi-rtgwg-mrt-frr-algorithm] (MRT), on the other hand, favors 112 reliability over shorter path. MRT provides two spanning trees 113 rooted at a destination, referred to as red and blue trees. The 114 trees have the property that the red and blue paths from any node to 115 the destination (root of the tree) are maximally-disjoint. The red 116 and blue paths may not be the shortest path. Thus, a node may employ 117 shortest path tree for forwarding under normal circumstances. Thus, 118 every node may have up to three FIB entries for a destination, one 119 for red tree, one for blue tree, and a third for the shortest path 120 tree. Under normal circumstances, the idea is to forward the packets 121 along the shortest path until the packet encounters a failure. If 122 the failed link is red (blue), then the packet is forwarded along the 123 blue (red) path. Once a packet is rerouted along the red or blue 124 tree, it continues to be forwarded along the chosen tree until it 125 reaches the destination. If the packet encounters another failure, 126 then it is dropped. Thus, MRT is guaranteed to recovery from only 127 only failure. 129 The maximally redundant trees are constructed using a technique 130 called path augmentation. The approach works as follows: (1) For a 131 given destination node, a cycle traversing the node and two other 132 nodes are computed. (2) One direction of the cycle is termed as red, 133 while the other direction is termed as blue. (3) A cycle or path is 134 computed that starts and ends at a node that has been already added 135 to the trees. On this cycle/path, one direction is treated as red 136 and the other direction is treated as blue. The direction of the red 137 and blue trees is computed based on a partial order, which ensures 138 that the red and blue assignments would result in disjoint paths 139 along the red and blue trees. The last step is repeated until all 140 the nodes in the network are considered. For a more detailed 141 description of the construction, refer to 142 [Jayavelu.2009.Maintaining]. 144 MRT constructs trees that are maximally-disjoint. Thus, if the 145 network provided two node-disjoint paths between a node and 146 destination, MRT would provide node-disjoint paths as well. If the 147 network does not provide node-disjoint paths, but provides link- 148 disjoint paths between a node and destination, then MRT would provide 149 link-disjoint paths as well. 151 Available Routing Construct [I-D.thubert-rtgwg-arc] (ARC) defines a 152 routing construct made of a bidirectional sequence of nodes and links 153 with 2 outgoing edges, so that, upon a single breakage, each lively 154 node in along ARC can still reach one of the outgoing edges. The bi- 155 directional sequence of nodes and links are similar to the paths/ 156 cycles used in the path augmentation technique in constructing MRT. 157 The routing graph to reach a certain destination is expressed as a 158 cascade of ARCs, each ARC providing its own independent domain of 159 fault isolation and recovery. Unicast traffic may enter an ARC via 160 any node but it may only leave the ARC through one of its two edges. 161 One node along the ARC is designated as the cursor. In normal 162 unicast operations, the traffic inside an ARC flows away from the 163 cursor towards an edge. Upon a failure, packets may bounce on the 164 breakage point and flow the other way along the ARC to take the other 165 exit. [I-D.thubert-rtgwg-arc] calculates ARCs within the shortest 166 path computation, and both sides of an ARC as delineated by the 167 cursor actually represent the shortest path to the destination. 169 Applying Available Routing Constructs to bicasting 170 [I-D.thubert-rtgwg-arc-bicast] provides additional information on how 171 an ARC fabric can be used for bicasting applications such as 172 livelive. In this class of applications, at least two disjoint paths 173 must be established between a source and a point of consumption. 174 Ideally, the source is diverse, for instance a distributed Content 175 Delivery Network (CDN), but it does not have to be that way. An ARC 176 fabric can be set up for an Omega that is a multiple destination in 177 the exact same fashion as if Omega is a unique node. 178 [I-D.thubert-rtgwg-arc-bicast] then shows how an ARC set can be 179 painted in two colors, an half of each ARC with one color and the 180 secong half of the other color in such a fashion that in most cases, 181 an edge of a certain color ends in the half of the next ARC that is 182 of the same color. A colored packet has the constraint to exit each 183 ARC along its path via the edge of its own color. If the edge and 184 the next half ARC are of the same color, the packet follows the 185 shortest path towards Omega. It results that ARC biscasting 186 agressively pursues the goal that both colored paths are close to 187 shortest even though disjoint. The quality of that closeness depends 188 on the way the ARC set was painted, which itself depends, in the 189 bicasting algorithm, on the starting points in Omega. A centralized 190 computation can probably improve the result that the simple technique 191 in [I-D.thubert-rtgwg-arc-bicast] obtains. 193 This drafts compares the properties of the ARC an MRT techniques in a 194 number of example situations that are crafted to highlight their 195 particular behaviors with an educational purpose in mind, as opposed 196 to represent the most classical real-world cases. It must be noted 197 that though the draft focuses on differences, ARCs and MRT have a lot 198 in common, in particular both provide maximally redundant solutions, 199 and represent roughly the same amount of labels and states in the 200 packets. 202 3. Terminology 204 The draft uses terminology from [I-D.enyedi-rtgwg-mrt-frr-algorithm] 205 and [I-D.thubert-rtgwg-arc]. 207 4. Reference Topology 209 This draft uses a simple reference topology, made of eight nodes A to 210 H and ten links with costs of either 1 or 2 as represented below: 212 A--- 2 ---E A E 213 | | v 214 1 1 v 215 | | v 216 B--- 1 ---F B >>>>>>> F 217 | | v v 218 1 1 v v 219 | | v v 220 C--- 1 ---G C >>>>>>> G 221 | | v 222 1 1 v 223 | | v 224 D--- 1 ---H D H 226 Topology SPF A to H 228 Figure 1: Reference Topology 230 In the following examples we will be interested in traffic flowing 231 from A to H. The shortest path for that flow is via B, then through 232 an equal cost multipath via F or C, and then G to finally reach H. 234 The oLAF algorithm forms three ARCs and MRT forms two trees: 236 A=========E 5 ------> 4 A E 237 | | ^ | r b 238 | | | | r b 239 | | | V v v 240 B=========F 6 ------> 3 B F 241 | | ^ | r b 242 | | | | r b 243 | | | V v v 244 C=========G 7 ------> 2 C G 245 || | ^ | r ^ b 246 || | | | r b b 247 || | | V v b v 248 D---------H 8 <------ 1 D rrrrrr> H D H 249 MRT MRT MRT 250 ARC set GADAG graph Red Tree BLUE Tree 252 Figure 2: ARC set and MRT Trees 254 Bidirectional links along the ARCs are represented as doubled lines. 255 The cursors end up on A, B and C for their respective ARCs. 257 5. Normal Operation 259 In normal operations MRT trees are not used so the MRT case is 260 identical to the SPF case. For ARCs, the cursors A B and C may send 261 traffic on either side but favor shortest. For A that means sending 262 to B and for C sending to G. B sees an equal cost so it may 263 distribute its traffic. 265 A E A E A E 266 v v v 267 v v v 268 v v v 269 B >>>>>>> F B >>>>>>> F B >>>>>>> F 270 v v v v v v 271 v v v v v v 272 v v v v v v 273 C >>>>>>> G C >>>>>>> G C >>>>>>> G 274 v v v 275 v v v 276 v v v 277 D H D H D H 279 ARC SPF MRT 281 Figure 3: Normal Operation 283 All in all, the three approaches end up with an identical result. 285 6. One breakage 287 Upon a first breakage, SPF cannot make a greedy progress so a packet 288 that follows the broken path is dropped. MRT converts to the packet 289 to blue or red, and then packet is placed in the associated tree till 290 the destination. Because blue and red have to be non-congruent to 291 the end, the detour that MRT generates tends to route the packet away 292 from shortest path. ARCs returns the packet along the current ARC so 293 it exits on the other edge. As soon as the cursor in the current ARC 294 is passed, the packet is again on shortest path. 296 A E A E A E 297 v v v 298 v v v 299 v v v 300 B >>>>>>> F B >>>>>>> F B >>>>>>> F 301 v <<<<<<< v v r >>>>>> G C G C G 305 v r 306 v r 307 v v 308 D H D H D rrrrrr> H 310 ARC SPF MRT 312 Figure 4: ARC closer to shortest path 314 Both MRT and ARCs enable fast reroute. MRT will generally incur a 315 larger detour. In the example above, the ARC path after B is 316 shortest, whereas the red path selected by MRT is not. 318 Because the blue and red paths of MRT are link-disjoint from any node 319 to the destination, the recovery path does not visit a broken link 320 again. ARCs achieve a shorter path by being more greedy. It results 321 that in some situations, a broken node might be visited twice, once 322 from the above, that is from an incoming ARC, and then from the side, 323 that is from inside its own ARC. This is illustrated below though it 324 would take an intermediate node between C and broken G to actually 325 create the undesired bouncing that is discussed here. 327 A E A E A E 328 v v v 329 v v v 330 v v v 331 B >>>>>>> F B >>>>>>> F B >>>>>>> F 332 v <<<<<<< v v r >>>>>> \/ C \/ C \/ 336 v <<<<<<< /\ /\ r /\ 337 v r 338 v v 339 D >>>>>>> H D H D rrrrrr> H 341 ARC SPF MRT 343 Figure 5: ARCs may revisit broken node 345 Note: In the particular case where a broken node is visited twice, 346 the end to end path that ARC uses may still be shorter than the blue 347 or red path that MRT computes, though it is not the case in the 348 particular example above. 350 MRT recovers from node failure similar to that of link failure. Note 351 that the paths provided by MRT are maximally disjoint. Thus at a 352 node, if a link is unavailable (whether due to a link failure or node 353 failure), the recovery path is taken. As the paths are maximally 354 disjoint, MRT guarantees that a failed node would never be visited 355 again. 357 7. Second breakage 359 Upon a first breakage, SPF cannot make a greedy progress so a packet 360 that follows the broken path is dropped. Upon a first breakage, MRT 361 selects either blue or red. If that selected path is broken down the 362 road, the packet is dropped. In the data plane, ARCs protect against 363 one breakage per ARC. Once a packet leaves an ARC to cascade in the 364 next, stigmata from a previous breakage are removed. So a break on 365 the next ARC can be resolved as well. 367 A >>>>>>> E A E A bbbbbb> E 368 v v v v b 369 \/ v \/ \/ b 370 /\ v /\ /\ v 371 B <<<<<<< F B F B F 372 v v v 373 v \/ \/ 374 v /\ /\ 375 C >>>>>>> G C G C G 376 v 377 v 378 v 379 D H D H D H 381 ARC SPF MRT 383 Figure 6: Each ARC its own recovery domain 385 It can be noted that if C to G,G or G to H is broken, ARCs will find 386 the C, D, H path and thus fix a third breakage as well. 388 8. Summary of differences 390 In sumary: 392 MRT ARC 394 1. Limited complexity - Complexity inherited from SPF 395 can be even O(e) 397 2. Detour, Short detour then Shortest Path 398 unrelated to Shortest Path again 400 3. Smaller chance to avoid unrelated Higher chance to avoid unrelated 401 failures failures 402 => may address SRLG cases 404 4. Single failure: reroute at most Single failure may incur double 405 once reroute 407 5. Load balancing with traditional Non-equal Cost Load Balancing 408 ECMP capabilities 410 6. Unrelated "topologies" exists Detours are strongly bound to 411 -> reconfiguration after the default paths 412 failure is simple => reconfiguration techniques 413 are difficult 415 7. Non-Congruent bicasting is not Shorter Path bicasting with 416 addressed collision avoidance 418 8. Source-centric computation Destination-centric computation 419 -> easier to distribute => enables complex destinations 420 (multiple equivalent ARC set 421 terminations 423 Figure 7: Comparison summary 425 8.1. Differences between ARCs and MRT 427 In this section, we elaborate on the differences listed above. 429 1. 431 ARC is a destination based technology, i.e. it compute a set of ARCs 432 to all the destinations in the network. Constructing one such set 433 needs several shortest path computations. This may cause a minor 434 problem: since detours and default paths are bound, computing the new 435 default paths after a failure may be delayed due to this slower 436 computation. 438 In contrast, MRT used the traditional shortest paths in a failure- 439 free state, thus detours can be computed separately, when all the 440 shortest paths are up and running. Moreover, although MRT offers 441 multiple ways to construct detours (keep in mind that MRT is only for 442 detours, default paths are computed with SPF), even the slowest one 443 is as fast as computing one set of ARCs for a single destination; the 444 fastest algorithm takes only O(e) time, so it is linear with the 445 number of links in the network. 447 2. 449 In MRT, the paths from any node to the destination on the red and 450 blue trees are link-disjoint, while in ARC, it is not. Thus, in MRT, 451 neither the red nor the blue tree is guaranteed to provide shortest 452 path for a node. However, in ARC, packet is forwarded along the 453 shortest path after a short detour. Naturally, when there is no 454 failure, both algorithms use the shortest paths, thus this difference 455 can only be observed after a failure. 457 3. 459 MRT uses separated default paths and detours. As a consequence, one 460 needs to have three FIB entries one for shortest path forwarding 461 (default), one for red tree forwarding, and one for blue tree 462 forwarding. When a failure happens, MRT puts the packet onto a 463 detour, which is not removed until it reaches the destination (egress 464 router, area border router, etc..). Thus, packet is bound to either 465 the red path, or the blue path. When the packet encounters a second 466 failure, the packet is dropped. 468 Although the MRT draft [I-D.ietf-rtgwg-mrt-frr-architecture] does not 469 discuss about recovering from multiple failures, the MRT framework 470 allows the network to recover from multiple link failures, as long as 471 no more than one failure is seen on a path/cycle that's used for 472 augmentation. Thus, when a packet is forwarded from one path/cycle 473 to another, the packet can handle one more link failure. This 474 technique has been shown in [Erlebach.2009.Path-Splicing]. 476 In contrast, ARC partitions the network in delimited protection 477 areas, i.e. it puts packets back to shortest path when they leave the 478 current ARC. Putting packets back to the shortest path as soon as 479 they leave the ARC makes it possible to reroute again at another 480 failure. Moreover, theoretically ARC needs only two labels/addresses 481 per destination, one describing the shortest path, and the other 482 describing the other direction in the ARC. However, this approach 483 would result loops, if there are more than one failure in the same 484 ARC, thus current version of ARC use at least three labels/addresses 485 per destination. 487 ARC can protect against multiple link failures as long as the only 488 one link failure occurs on an ARC. 490 Since there is always a reconfiguration after a failure, and FRR is 491 in charge only for a short amount of time while this reconfiguration 492 takes place, one may think that preparing for more than one failure 493 is not important. However, there are the "Shared Risk Link Groups" 494 (SRLG), groups of links sharing the same fate due to some hidden 495 common property (e.g. they are using the same optical cable), which 496 may cause multiple failures at the same time. Even if both MRT and 497 ARC can deal with the most common types of SRLGs (failure of links of 498 the same linecard, and the failure of some ethernet network under the 499 level of IP; namely the "LAN failure"), it is better to protect as 500 many resources as possible. 502 4. 504 For the price of having only one reroute, MRT can guarantee that the 505 same failure will never be visited again. In contrast, since the 506 same node can be an exit point for multiple ARCs, and since ARC puts 507 packets back to shortest path after a failure, it is possible that a 508 single failed node will be visited multiple times. It is very 509 important that ARCs will properly handle this case with multiple 510 rerouting, so sooner or later the destination will be reached. 511 Moreover, the probability of such situation seems to be low. 513 5. 515 ARC can provide load balancing for the traffic with the "cursor 516 node", since ARC gives not only a backup, but a new way for default 517 routing as well. In contrast, since MRT only provide the detours, 518 load balancing is not in the focus of MRT, but it is done with 519 traditional ECMP. However, it is possible that a node have multiple 520 blue or red next-hops with MRT, and in this case load balancing is 521 possible even for packets on detours. 523 6. 525 IPFRR techniques are for designed for protection, i.e. they are used 526 immediately after a failure happens. Typically after a failure, 527 traditional routing protocols like OSPF reexplore the topology and 528 reconfigure the forwarding entries based on the new topology. 529 Packets start using the new shortest paths, and the network prepares 530 to protect against a new failure. Normally, the reconfiguration 531 after a failure may cause transient forwarding anomalies like micro- 532 loops, but these are not acceptable for IPFRR. 534 Thus, several loop-preventing techniques were proposed in [RFC5715]. 535 Since MRT provides two independent routing, i.e. the default 536 shortest paths and the detours, it can use even Farside tunnels, 537 which does not need protocol extension (basically, MRT can use one 538 routing, while it reconfigures the other). Although, ARC is capable 539 for loopfree convergence with centralized loop routing, it is not 540 clear, which technique ARC could use in a distributed environment. 542 7. 544 Since MRT is an FRR technique, bicasting is out of its scope. 545 However, bicasting is theoretically possible, if we use the blue and 546 the red next-hops; naturally, these paths will be node- and link- 547 disjoint. In contrast, ARC was designed for not only FRR but 548 bicasting, even if it cannot automatically provide disjoint paths. 549 The advantage is that those paths can be shorter. For further 550 details consult [I-D.thubert-rtgwg-arc]. 552 8.2. Similarities between ARC and MRT 554 MRT uses a helper graph called GADAG, and detour computation is based 555 on that graph. This helper graph is basically a set of ARCs with 556 some extra direction information for the GADAG root as a destination. 557 Thanks to this common point, computation algorithm and detours are 558 very similar. 560 9. ARC specific properties 562 ARC is not only for FRR, but a complex forwarding technique, which 563 can help in load balancing and speed up reconfiguration. Since MRT 564 is an only for IPFRR, it cannot change routing in any way in a 565 failure-free state, and the following properties do not exist. 567 However, it is important to note that for the advantages below we 568 need to introduce the "cursor" node. Using the concept of a cursor 569 needs some protocol extension, and it replaces traditional shortest 570 path routing in some sense. 572 9.1. Multiple related breakages 574 In control plane, ARCs can find an exit if one exists and in 575 principle, can be used to solve the Shared Risk Link Group (SRLG) 576 problem. An ARC set is a Directed Acyclic Graph of ARCs, thus link 577 reversal techniques can be applied to recover from complex breakages. 578 Upon a second breakage in a same ARC, a segment is isolated. In 579 control plane, it is possible to return all the incoming links in 580 that segment. This may recurse if incoming ARCs become isolated as 581 well. If the process recurses, a link may be returned a number of 582 times and this must be stopped by some infinity count. Once the 583 local recovery settles, the exit path stands out. 585 A E A E A >>>>>>> E 586 v ^ v 587 v | v 588 v | v 589 B >>\/ F B \/ F B \/ F 590 v /\ /\ /\ v 591 \/ \/ \/ v 592 /\ /\ /\ v 593 C G C G C G 594 v 595 v 596 v 597 D H D H D H 599 Double Control plane Exit path 600 breakage Link reversal stands out 602 Figure 8: SRLG case 604 This example illustrates that the ARC segment around B is no more 605 isolated by returning the A -> B edge into a B-> A link. 607 Recovery from multiple failures may also be performed using a variant 608 of redundant trees, called independent directed acyclic graphs, which 609 aims to utilize all the links in the network 610 [Cho.2012.Independent-DAG]. With this approach, every node has one 611 or more forwarding edges in the red/blue trees. Upon failure of all 612 the red forwarding edges, the packet is transferred to the blue tree. 614 9.2. Multiple Destination and Load Balancing 616 The MRT and ARC techniques may be used for routing to redundant 617 destination nodes. Given two nodes R1 and R2, MRT can construct two 618 trees, tree T1 rooted at R1 and tree T2 rooted at R2. The path from 619 any node to R1 on T1 and to R2 on T2 are still maximally-disjoint 620 [Jayavelu.2009.Maintaining]. Similarly, the oLAF algorithm used for 621 constructing ARCs is destination-oriented, in that it forms ARCs from 622 the standpoint of the destination. This makes ARCs more complex to 623 compute in a distributed fashion, but on the other hand enables to 624 group a set of nodes. 626 One example of employing multiple destinations is to employ multiple 627 border routers between one area and another. Thus, the routing in 628 one area may exit to the other area through one of the border 629 routers. 631 With multiple destinations, it is possible not only to allow high 632 availability but also to dynamically load balance between the member 633 nodes. In an ARC, the node that has the logical responsibility of 634 cursor is the only node that may send packets towards both edges in 635 normal conditions. It is possible to create a control loop between a 636 congestion point on one side and the cursor, in order to balance more 637 traffic towards the other edge. If the cursor sends all its traffic 638 towards the other edge, then the cursor responsibility may be 639 transferred to the next node towards the congested edge to balance 640 more traffic. If both edges are congested, then the congestion 641 indication can be recursively injected in incoming ARCs. 643 An ARC based control loop does not need to involve metric changes or 644 other routing advertisements, so it can be kept separate from the 645 routing protocol. A simple control loop protocol can be used, that 646 can be kept from oscillating with appropriate periods and adaptive 647 filters. 649 A<==cur==>E A<==cur==>E A<==cur==>E 650 | | | | | | 651 | | | | | | 652 v v v v v v 653 B<==cur==>F B<==cur==>F B<==cur F 654 | | | | | | 655 | | | | | con 656 v v v v v gest 657 C<==cur==>G C<==cur G C<=======cur 658 | | | | | | 659 | | | con | con 660 v v v gest v gest 661 D OMEGA H D OMEGA H D OMEGA H 663 Destination is control loop recursing 664 both A and H to cursor control loop 666 Figure 9: Complex Destination and Load Balancing 668 9.3. Hierarchical Routing 670 In a hierarchical network, routing happens within cells and then 671 between cells. The collection of border routers between this cell 672 and the next cell forms a complex destination for which an ARC set 673 can be formed within this cell. This can be done as soon as the 674 cells are formed, before any end-to-end route between cell is 675 computed and whatever the routing protocol between cells is. This 676 model applies in particular for such cells as areas, autonomous 677 systems and optical rings. 679 9.4. Recovery from Node Failures 681 ARCS may be used to achieve fast recovery from node failures as well. 682 The construction of ARC is similar to the construction of backup 683 forwarding arcs forwarding arcs, as discussed in 684 [Xi.2007.Fast-Reroute]. The placement of cursors may still be 685 performed once the backup paths (forwarding edges) are computed after 686 failing each node. 688 9.5. Applied to bicasting (livelive) 690 MRT is not designed to compute an operational path but rather an 691 alternate fast reroute solution that avoids any potential single 692 breakage in the operational path that is computed otherwise, e.g. 693 using the Shortest Path First algorithm. On the other hand, An ARC 694 fabric joins together branches of a shortest path trees, so that most 695 of the way along an ARC Set is shortest. Coloring the ARC Set for 696 live live forces a colored packet to exit an ARC at an edge that is 697 not always the shortest, but often is. It results that by design, 698 both colored path are close to shortest, making ARCs a potential 699 solution for livelive. Additionally, the support of an Omega that is 700 formed of multiple destinations is a valuable asset for some 701 applications such as video distribution. An ARC Set can be designed 702 so that the lowest ARCs are between CDNs. It results that with a 703 single ARC Set, all nodes in the network would have a pair of path 704 that enable distribution from a relatively close CDN. 706 10. Manageability 708 This specification describes a generic model. Protocols and 709 management will come later 711 11. IANA Considerations 713 This specification does not require IANA action. 715 12. Security Considerations 717 This specification is not found to introduce new security threat. 719 13. Acknowledgements 721 The authors wishes to thank Alia Atlas, Patrice Bellagamba, Stewart 722 Bryant, Robert Kebler, and Andras Csaszar for their participation to 723 this particular work, and Dirk Anteunis, IJsbrand Wijnands, George 724 Swallow, Eric Osborne, Clarence Filsfils and Eric Levy-Abegnoli for 725 their continuous support to components of the work presented here. 727 14. References 729 14.1. Normative References 731 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 732 Requirement Levels", BCP 14, RFC 2119, March 1997. 734 [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free 735 Convergence", RFC 5715, January 2010. 737 14.2. Informative References 739 [I-D.enyedi-rtgwg-mrt-frr-algorithm] 740 Envedi, G., Csaszar, A., Atlas, A., cbowers@juniper.net, 741 c., and A. Gopalan, "Algorithms for computing Maximally 742 Redundant Trees for IP/LDP Fast- Reroute", draft-enyedi- 743 rtgwg-mrt-frr-algorithm-04 (work in progress), October 744 2013. 746 [I-D.ietf-rtgwg-mrt-frr-architecture] 747 Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar, 748 A., Tantsura, J., and R. White, "An Architecture for IP/ 749 LDP Fast-Reroute Using Maximally Redundant Trees", draft- 750 ietf-rtgwg-mrt-frr-architecture-05 (work in progress), 751 January 2015. 753 [I-D.thubert-rtgwg-arc] 754 Thubert, P. and P. Bellagamba, "Available Routing 755 Constructs", draft-thubert-rtgwg-arc-02 (work in 756 progress), July 2014. 758 [I-D.thubert-rtgwg-arc-bicast] 759 Thubert, P. and I. Wijnands, "Applying Available Routing 760 Constructs to bicasting", draft-thubert-rtgwg-arc- 761 bicast-01 (work in progress), October 2013. 763 [RFC5921] Bocci, M., Bryant, S., Frost, D., Levrau, L., and L. 764 Berger, "A Framework for MPLS in Transport Networks", RFC 765 5921, July 2010. 767 14.3. References 769 [Cho.2012.Independent-DAG] 770 Cho, S., Elhourani, T., and S. Ramasubramanian, 771 "Independent Directed Acyclic Graphs for Resilient 772 Multipath Routing", IEEE/ACM Transactions on Networking, 773 vol. 20, no. 1 , February 2012, 774 . 776 [Erlebach.2009.Path-Splicing] 777 Erlebach, T. and A. Mereu, "Path splicing with guaranteed 778 fault tolerance", Proceedings of IEEE GLOBECOM , November- 779 December 2009, 780 . 782 [Jayavelu.2009.Maintaining] 783 Jayavelu, G., Ramasubramanian, S., and O. Younis, 784 "Maintaining colored trees for disjoint multipath routing 785 under node failures", IEEE/ACM Transactions on Networking, 786 vol. 17, no. 1 , February 2009, 787 . 789 [Xi.2007.Fast-Reroute] 790 Xi, K. and H. Chao, "IP fast rerouting for single-link/ 791 node failure recovery", Proceedings of IEEE BROADNETS , 792 September 2007, . 795 Authors' Addresses 797 Pascal Thubert (editor) 798 Cisco Systems, Inc 799 Building D 800 45 Allee des Ormes - BP1200 801 MOUGINS - Sophia Antipolis 06254 802 FRANCE 804 Phone: +33 497 23 26 34 805 Email: pthubert@cisco.com 807 Gabor Sandor Enyedi 808 Ericsson 809 Srinivasan Ramasubramanian 810 University of Arizona 811 1230 E. Speedway Blvd. 812 Tucson, AZ 85721 813 USA 815 Phone: +1 520 621 4521 816 Email: srini@ece.arizona.edu