idnits 2.17.00 (12 Aug 2021) /tmp/idnits45152/draft-thubert-rtgwg-arc-vs-mrt-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 : ---------------------------------------------------------------------------- ** There are 10 instances of too long lines in the document, the longest one being 8 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 570 has weird spacing: '...eversal sta...' == Line 633 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 21, 2013) is 3407 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RFC5921' is defined on line 710, but no explicit reference was found in the text == Outdated reference: A later version (-04) exists of draft-enyedi-rtgwg-mrt-frr-algorithm-02 == 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-00 Summary: 1 error (**), 0 flaws (~~), 8 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 Systems 4 Intended status: Informational G. Enyedi 5 Expires: July 25, 2013 Ericsson 6 S. Ramasubramanian 7 UA 8 January 21, 2013 10 Available Routing Constructs 11 draft-thubert-rtgwg-arc-vs-mrt-00 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 25, 2013. 43 Copyright Notice 45 Copyright (c) 2013 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 . . . . . . . . . . . . . . . . . . . . . . . 3 61 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 62 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 63 4. Reference Topology . . . . . . . . . . . . . . . . . . . . . . 5 64 5. Normal Operation . . . . . . . . . . . . . . . . . . . . . . . 6 65 6. One breakage . . . . . . . . . . . . . . . . . . . . . . . . . 7 66 7. Second breakage . . . . . . . . . . . . . . . . . . . . . . . 8 67 8. Summary of differences . . . . . . . . . . . . . . . . . . . . 9 68 8.1. Differences between ARCs and MRT . . . . . . . . . . . . . 10 69 8.2. Similarities between ARC and MRT . . . . . . . . . . . . . 13 70 9. ARC specific properties . . . . . . . . . . . . . . . . . . . 13 71 9.1. Multiple related breakages . . . . . . . . . . . . . . . . 13 72 9.2. Multiple Destination and Load Balancing . . . . . . . . . 14 73 9.3. Hierarchical Routing . . . . . . . . . . . . . . . . . . . 15 74 9.4. Recovery from Node Failures . . . . . . . . . . . . . . . 16 75 10. Manageability . . . . . . . . . . . . . . . . . . . . . . . . 16 76 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16 77 12. Security Considerations . . . . . . . . . . . . . . . . . . . 16 78 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 16 79 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 16 80 14.1. Normative References . . . . . . . . . . . . . . . . . . . 16 81 14.2. Informative References . . . . . . . . . . . . . . . . . . 17 82 14.3. References . . . . . . . . . . . . . . . . . . . . . . . . 17 83 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 18 85 1. Important Notice 87 This document compares MRT and ARCs based on 88 [I-D.enyedi-rtgwg-mrt-frr-algorithm], 89 [I-D.ietf-rtgwg-mrt-frr-architecture] and [I-D.thubert-rtgwg-arc] as 90 they are on 10/12/2012. Both solutions are about to change, which 91 may make this document outdated. 93 2. Introduction 95 Traditional routing and forwarding uses the concept of path as the 96 basic routing paradigm to get a packet from a source to a 97 destination. A path is represented as an ordered sequence of nodes. 98 This paradigm is greedy in that it requires that the next node 99 represent a progress towards the destination. Greediness is 100 maximized by Shortest Path First (SPF) techniques which optimize for 101 a cost that relates to the amount of forwarding effort and latency, 102 at the expense of network capacity and reliability. In particular, a 103 path is broken as soon as a single link or a single node fails, and 104 getting around a breakage can require path recomputation, network 105 reconvergence, and incur delays and/or microloops till service is 106 restored. 108 Maximally Redundant Trees [I-D.ietf-rtgwg-mrt-frr-architecture] 109 [I-D.enyedi-rtgwg-mrt-frr-algorithm] (MRT), on the other hand, favors 110 reliability over shorter path. MRT provides two spanning trees 111 rooted at a destination, referred to as red and blue trees. The 112 trees have the property that the red and blue paths from any node to 113 the destination (root of the tree) are maximally-disjoint. The red 114 and blue paths may not be the shortest path. Thus, a node may employ 115 shortest path tree for forwarding under normal circumstances. Thus, 116 every node may have up to three FIB entries for a destination, one 117 for red tree, one for blue tree, and a third for the shortest path 118 tree. Under normal circumstances, the idea is to forward the packets 119 along the shortest path until the packet encounters a failure. If 120 the failed link is red (blue), then the packet is forwarded along the 121 blue (red) path. Once a packet is rerouted along the red or blue 122 tree, it continues to be forwarded along the chosen tree until it 123 reaches the destination. If the packet encounters another failure, 124 then it is dropped. Thus, MRT is guaranteed to recovery from only 125 only failure. 127 The maximally redundant trees are constructed using a technique 128 called path augmentation. The approach works as follows: (1) For a 129 given destination node, a cycle traversing the node and two other 130 nodes are computed. (2) One direction of the cycle is termed as red, 131 while the other direction is termed as blue. (3) A cycle or path is 132 computed that starts and ends at a node that has been already added 133 to the trees. On this cycle/path, one direction is treated as red 134 and the other direction is treated as blue. The direction of the red 135 and blue trees is computed based on a partial order, which ensures 136 that the red and blue assignments would result in disjoint paths 137 along the red and blue trees. The last step is repeated until all 138 the nodes in the network are considered. For a more detailed 139 description of the construction, refer to 140 [Jayavelu.2009.Maintaining]. 142 MRT constructs trees that are maximally-disjoint. Thus, if the 143 network provided two node-disjoint paths between a node and 144 destination, MRT would provide node-disjoint paths as well. If the 145 network does not provide node-disjoint paths, but provides link- 146 disjoint paths between a node and destination, then MRT would provide 147 link-disjoint paths as well. 149 Available Routing Construct [I-D.thubert-rtgwg-arc] (ARC) defines a 150 routing construct made of a bidirectional sequence of nodes and links 151 with 2 outgoing edges, so that, upon a single breakage, each lively 152 node in along ARC can still reach one of the outgoing edges. The bi- 153 directional sequence of nodes and links are similar to the paths/ 154 cycles used in the path augmentation technique in constructing MRT. 155 The routing graph to reach a certain destination is expressed as a 156 cascade of ARCs, each ARC providing its own independent domain of 157 fault isolation and recovery. Unicast traffic may enter an ARC via 158 any node but it may only leave the ARC through one of its two edges. 159 One node along the ARC is designated as the cursor. In normal 160 unicast operations, the traffic inside an ARC flows away from the 161 cursor towards an edge. Upon a failure, packets may bounce on the 162 breakage point and flow the other way along the ARC to take the other 163 exit. [I-D.thubert-rtgwg-arc] calculates ARCs within the shortest 164 path computation, and both sides of an ARC as delineated by the 165 cursor actually represent the shortest path to the destination. 167 This drafts compares the properties of the ARC an MRT techniques in a 168 number of example situations that are crafted to highlight their 169 particular behaviors with an educational purpose in mind, as opposed 170 to represent the most classical real-world cases. It must be noted 171 that though the draft focuses on differences, ARCs and MRT have a lot 172 in common, in particular both provide maximally redundant solutions, 173 and represent roughly the same amount of labels and states in the 174 packets. 176 3. Terminology 178 The draft uses terminology from [I-D.enyedi-rtgwg-mrt-frr-algorithm] 179 and [I-D.thubert-rtgwg-arc]. 181 4. Reference Topology 183 This draft uses a simple reference topology, made of eight nodes A to 184 H and ten links with costs of either 1 or 2 as represented below: 186 A--- 2 ---E A E 187 | | v 188 1 1 v 189 | | v 190 B--- 1 ---F B >>>>>>> F 191 | | v v 192 1 1 v v 193 | | v v 194 C--- 1 ---G C >>>>>>> G 195 | | v 196 1 1 v 197 | | v 198 D--- 1 ---H D H 200 Topology SPF A to H 202 Figure 1: Reference Topology 204 In the following examples we will be interested in traffic flowing 205 from A to H. The shortest path for that flow is via B, then through 206 an equal cost multipath via F or C, and then G to finally reach H. 208 The oLAF algorithm forms three ARCs and MRT forms two trees: 210 A=========E 5 ------> 4 A E 211 | | ^ | r b 212 | | | | r b 213 | | | V v v 214 B=========F 6 ------> 3 B F 215 | | ^ | r b 216 | | | | r b 217 | | | V v v 218 C=========G 7 ------> 2 C G 219 || | ^ | r ^ b 220 || | | | r b b 221 || | | V v b v 222 D---------H 8 <------ 1 D rrrrrr> H D H 223 MRT MRT MRT 224 ARC set GADAG graph Red Tree BLUE Tree 226 Figure 2: ARC set and MRT Trees 228 Bidirectional links along the ARCs are represented as doubled lines. 229 The cursors end up on A, B and C for their respective ARCs. 231 5. Normal Operation 233 In normal operations MRT trees are not used so the MRT case is 234 identical to the SPF case. For ARCs, the cursors A B and C may send 235 traffic on either side but favor shortest. For A that means sending 236 to B and for C sending to G. B sees an equal cost so it may 237 distribute its traffic. 239 A E A E A E 240 v v v 241 v v v 242 v v v 243 B >>>>>>> F B >>>>>>> F B >>>>>>> F 244 v v v v v v 245 v v v v v v 246 v v v v v v 247 C >>>>>>> G C >>>>>>> G C >>>>>>> G 248 v v v 249 v v v 250 v v v 251 D H D H D H 253 ARC SPF MRT 254 Figure 3: Normal Operation 256 All in all, the three approaches end up with an identical result. 258 6. One breakage 260 Upon a first breakage, SPF cannot make a greedy progress so a packet 261 that follows the broken path is dropped. MRT converts to the packet 262 to blue or red, and then packet is placed in the associated tree till 263 the destination. Because blue and red have to be non-congruent to 264 the end, the detour that MRT generates tends to route the packet away 265 from shortest path. ARCs returns the packet along the current ARC so 266 it exits on the other edge. As soon as the cursor in the current ARC 267 is passed, the packet is again on shortest path. 269 A E A E A E 270 v v v 271 v v v 272 v v v 273 B >>>>>>> F B >>>>>>> F B >>>>>>> F 274 v <<<<<<< v v r >>>>>> G C G C G 278 v r 279 v r 280 v v 281 D H D H D rrrrrr> H 283 ARC SPF MRT 285 Figure 4: ARC closer to shortest path 287 Both MRT and ARCs enable fast reroute. MRT will generally incur a 288 larger detour. In the example above, the ARC path after B is 289 shortest, whereas the red path selected by MRT is not. 291 Because the blue and red paths of MRT are link-disjoint from any node 292 to the destination, the recovery path does not visit a broken link 293 again. ARCs achieve a shorter path by being more greedy. It results 294 that in some situations, a broken node might be visited twice, once 295 from the above, that is from an incoming ARC, and then from the side, 296 that is from inside its own ARC. This is illustrated below though it 297 would take an intermediate node between C and broken G to actually 298 create the undesired bouncing that is discussed here. 300 A E A E A E 301 v v v 302 v v v 303 v v v 304 B >>>>>>> F B >>>>>>> F B >>>>>>> F 305 v <<<<<<< v v r >>>>>> \/ C \/ C \/ 309 v <<<<<<< /\ /\ r /\ 310 v r 311 v v 312 D >>>>>>> H D H D rrrrrr> H 314 ARC SPF MRT 316 Figure 5: ARCs may revisit broken node 318 Note: In the particular case where a broken node is visited twice, 319 the end to end path that ARC uses may still be shorter than the blue 320 or red path that MRT computes, though it is not the case in the 321 particular example above. 323 MRT recovers from node failure similar to that of link failure. Note 324 that the paths provided by MRT are maximally disjoint. Thus at a 325 node, if a link is unavailable (whether due to a link failure or node 326 failure), the recovery path is taken. As the paths are maximally 327 disjoint, MRT guarantees that a failed node would never be visited 328 again. 330 7. Second breakage 332 Upon a first breakage, SPF cannot make a greedy progress so a packet 333 that follows the broken path is dropped. Upon a first breakage, MRT 334 selects either blue or red. If that selected path is broken down the 335 road, the packet is dropped. In the data plane, ARCs protect against 336 one breakage per ARC. Once a packet leaves an ARC to cascade in the 337 next, stigmata from a previous breakage are removed. So a break on 338 the next ARC can be resolved as well. 340 A >>>>>>> E A E A bbbbbb> E 341 v v v v b 342 \/ v \/ \/ b 343 /\ v /\ /\ v 344 B <<<<<<< F B F B F 345 v v v 346 v \/ \/ 347 v /\ /\ 348 C >>>>>>> G C G C G 349 v 350 v 351 v 352 D H D H D H 354 ARC SPF MRT 356 Figure 6: Each ARC its own recovery domain 358 It can be noted that if C to G,G or G to H is broken, ARCs will find 359 the C, D, H path and thus fix a third breakage as well. 361 8. Summary of differences 363 In sumary: 365 MRT ARC 367 1. Limited complexity - can be even O(e) Complexity inherited from SPF 369 2. Detour, unrelated to Shortest Path Short detour then Shortest Path 370 again 372 3. Smaller chance to avoid unrelated Higher chance to avoid unrelated 373 failures failures 374 -> may address SRLG cases 376 4. Single failure: reroute at most Single failure may incur double 377 once reroute 379 5. Load balancing with traditional Non-equal Cost Load Balancing 380 ECMP capabilities 382 6. Unrelated "topologies" exists Detours are strongly bound to 383 -> reconfiguration after the default paths 384 failure is simple -> reconfiguration techniques are 385 difficult 387 7. Non-Congruent bicasting is not Shorter Path bicasting with 388 addressed collision avoidance 390 8. Source-centric computation Destination-centric computation 391 -> easier to distribute -> allows for complex destinations 393 Figure 7: Comparison summary 395 8.1. Differences between ARCs and MRT 397 In this section, we elaborate on the differences listed above. 399 1. 401 ARC is a destination based technology, i.e. it compute a set of ARCs 402 to all the destinations in the network. Constructing one such set 403 needs several shortest path computations. This may cause a minor 404 problem: since detours and default paths are bound, computing the new 405 default paths after a failure may be delayed due to this slower 406 computation. 408 In contrast, MRT used the traditional shortest paths in a failure- 409 free state, thus detours can be computed separately, when all the 410 shortest paths are up and running. Moreover, although MRT offers 411 multiple ways to construct detours (keep in mind that MRT is only for 412 detours, default paths are computed with SPF), even the slowest one 413 is as fast as computing one set of ARCs for a single destination; the 414 fastest algorithm takes only O(e) time, so it is linear with the 415 number of links in the network. 417 2. 419 In MRT, the paths from any node to the destination on the red and 420 blue trees are link-disjoint, while in ARC, it is not. Thus, in MRT, 421 neither the red nor the blue tree is guaranteed to provide shortest 422 path for a node. However, in ARC, packet is forwarded along the 423 shortest path after a short detour. Naturally, when there is no 424 failure, both algorithms use the shortest paths, thus this difference 425 can only be observed after a failure. 427 3. 429 MRT uses separated default paths and detours. As a consequence, one 430 needs to have three FIB entries one for shortest path forwarding 431 (default), one for red tree forwarding, and one for blue tree 432 forwarding. When a failure happens, MRT puts the packet onto a 433 detour, which is not removed until it reaches the destination (egress 434 router, area border router, etc..). Thus, packet is bound to either 435 the red path, or the blue path. When the packet encounters a second 436 failure, the packet is dropped. 438 Although the MRT draft [I-D.ietf-rtgwg-mrt-frr-architecture] does not 439 discuss about recovering from multiple failures, the MRT framework 440 allows the network to recover from multiple link failures, as long as 441 no more than one failure is seen on a path/cycle that's used for 442 augmentation. Thus, when a packet is forwarded from one path/cycle 443 to another, the packet can handle one more link failure. This 444 technique has been shown in [Erlebach.2009.Path-Splicing]. 446 In contrast, ARC partitions the network in delimited protection 447 areas, i.e. it puts packets back to shortest path when they leave the 448 current ARC. Putting packets back to the shortest path as soon as 449 they leave the ARC makes it possible to reroute again at another 450 failure. Moreover, theoretically ARC needs only two labels/addresses 451 per destination, one describing the shortest path, and the other 452 describing the other direction in the ARC. However, this approach 453 would result loops, if there are more than one failure in the same 454 ARC, thus current version of ARC use at least three labels/addresses 455 per destination. 457 ARC can protect against multiple link failures as long as the only 458 one link failure occurs on an ARC. 460 Since there is always a reconfiguration after a failure, and FRR is 461 in charge only for a short amount of time while this reconfiguration 462 takes place, one may think that preparing for more than one failure 463 is not important. However, there are the "Shared Risk Link Groups" 464 (SRLG), groups of links sharing the same fate due to some hidden 465 common property (e.g. they are using the same optical cable), which 466 may cause multiple failures at the same time. Even if both MRT and 467 ARC can deal with the most common types of SRLGs (failure of links of 468 the same linecard, and the failure of some ethernet network under the 469 level of IP; namely the "LAN failure"), it is better to protect as 470 many resources as possible. 472 4. 474 For the price of having only one reroute, MRT can guarantee that the 475 same failure will never be visited again. In contrast, since the 476 same node can be an exit point for multiple ARCs, and since ARC puts 477 packets back to shortest path after a failure, it is possible that a 478 single failed node will be visited multiple times. It is very 479 important that ARCs will properly handle this case with multiple 480 rerouting, so sooner or later the destination will be reached. 481 Moreover, the probability of such situation seems to be low. 483 5. 485 ARC can provide load balancing for the traffic with the "cursor 486 node", since ARC gives not only a backup, but a new way for default 487 routing as well. In contrast, since MRT only provide the detours, 488 load balancing is not in the focus of MRT, but it is done with 489 traditional ECMP. However, it is possible that a node have multiple 490 blue or red next-hops with MRT, and in this case load balancing is 491 possible even for packets on detours. 493 6. 495 IPFRR techniques are for designed for protection, i.e. they are used 496 immediately after a failure happens. Typically after a failure, 497 traditional routing protocols like OSPF reexplore the topology and 498 reconfigure the forwarding entries based on the new topology. 499 Packets start using the new shortest paths, and the network prepares 500 to protect against a new failure. Normally, the reconfiguration 501 after a failure may cause transient forwarding anomalies like micro- 502 loops, but these are not acceptable for IPFRR. 504 Thus, several loop-preventing techniques were proposed in [RFC5715]. 505 Since MRT provides two independent routing, i.e. the default shortest 506 paths and the detours, it can use even Farside tunnels, which does 507 not need protocol extension (basically, MRT can use one routing, 508 while it reconfigures the other). Although, ARC is capable for 509 loopfree convergence with centralized loop routing, it is not clear, 510 which technique ARC could use in a distributed environment. 512 7. 514 Since MRT is an FRR technique, bicasting is out of its scope. 515 However, bicasting is theoretically possible, if we use the blue and 516 the red next-hops; naturally, these paths will be node- and link- 517 disjoint. In contrast, ARC was designed for not only FRR but 518 bicasting, even if it cannot automatically provide disjoint paths. 519 The advantage is that those paths can be shorter. For further 520 details consult [I-D.thubert-rtgwg-arc]. 522 8.2. Similarities between ARC and MRT 524 MRT uses a helper graph called GADAG, and detour computation is based 525 on that graph. This helper graph is basically a set of ARCs with 526 some extra direction information for the GADAG root as a destination. 527 Thanks to this common point, computation algorithm and detours are 528 very similar. 530 9. ARC specific properties 532 ARC is not only for FRR, but a complex forwarding technique, which 533 can help in load balancing and speed up reconfiguration. Since MRT 534 is an only for IPFRR, it cannot change routing in any way in a 535 failure-free state, and the following properties do not exist. 537 However, it is important to note that for the advantages below we 538 need to introduce the "cursor" node. Using the concept of a cursor 539 needs some protocol extension, and it replaces traditional shortest 540 path routing in some sense. 542 9.1. Multiple related breakages 544 In control plane, ARCs can find an exit if one exists and in 545 principle, can be used to solve the Shared Risk Link Group (SRLG) 546 problem. An ARC set is a Directed Acyclic Graph of ARCs, thus link 547 reversal techniques can be applied to recover from complex breakages. 548 Upon a second breakage in a same ARC, a segment is isolated. In 549 control plane, it is possible to return all the incoming links in 550 that segment. This may recurse if incoming ARCs become isolated as 551 well. If the process recurses, a link may be returned a number of 552 times and this must be stopped by some infinity count. Once the 553 local recovery settles, the exit path stands out. 555 A E A E A >>>>>>> E 556 v ^ v 557 v | v 558 v | v 559 B >>\/ F B \/ F B \/ F 560 v /\ /\ /\ v 561 \/ \/ \/ v 562 /\ /\ /\ v 563 C G C G C G 564 v 565 v 566 v 567 D H D H D H 569 Double Control plane Exit path 570 breakage Link reversal stands out 572 Figure 8: SRLG case 574 This example illustrates that the ARC segment around B is no more 575 isolated by returning the A -> B edge into a B-> A link. 577 Recovery from multiple failures may also be performed using a variant 578 of redundant trees, called independent directed acyclic graphs, which 579 aims to utilize all the links in the network 580 [Cho.2012.Independent-DAG]. With this approach, every node has one 581 or more forwarding edges in the red/blue trees. Upon failure of all 582 the red forwarding edges, the packet is transferred to the blue tree. 584 9.2. Multiple Destination and Load Balancing 586 The MRT and ARC techniques may be used for routing to redundant 587 destination nodes. Given two nodes R1 and R2, MRT can construct two 588 trees, tree T1 rooted at R1 and tree T2 rooted at R2. The path from 589 any node to R1 on T1 and to R2 on T2 are still maximally-disjoint 590 [Jayavelu.2009.Maintaining]. Similarly, the oLAF algorithm used for 591 constructing ARCs is destination-oriented, in that it forms ARCs from 592 the standpoint of the destination. This makes ARCs more complex to 593 compute in a distributed fashion, but on the other hand enables to 594 group a set of nodes. 596 One example of employing multiple destinations is to employ multiple 597 border routers between one area and another. Thus, the routing in 598 one area may exit to the other area through one of the border 599 routers. 601 With multiple destinations, it is possible not only to allow high 602 availability but also to dynamically load balance between the member 603 nodes. In an ARC, the node that has the logical responsibility of 604 cursor is the only node that may send packets towards both edges in 605 normal conditions. It is possible to create a control loop between a 606 congestion point on one side and the cursor, in order to balance more 607 traffic towards the other edge. If the cursor sends all its traffic 608 towards the other edge, then the cursor responsibility may be 609 transferred to the next node towards the congested edge to balance 610 more traffic. If both edges are congested, then the congestion 611 indication can be recursively injected in incoming ARCs. 613 An ARC based control loop does not need to involve metric changes or 614 other routing advertisements, so it can be kept separate from the 615 routing protocol. A simple control loop protocol can be used, that 616 can be kept from oscillating with appropriate periods and adaptive 617 filters. 619 A<==cur==>E A<==cur==>E A<==cur==>E 620 | | | | | | 621 | | | | | | 622 v v v v v v 623 B<==cur==>F B<==cur==>F B<==cur F 624 | | | | | | 625 | | | | | con 626 v v v v v gest 627 C<==cur==>G C<==cur G C<=======cur 628 | | | | | | 629 | | | con | con 630 v v v gest v gest 631 D OMEGA H D OMEGA H D OMEGA H 633 Destination is control loop recursing 634 both A and H to cursor control loop 636 Figure 9: Complex Destination and Load Balancing 638 9.3. Hierarchical Routing 640 In a hierarchical network, routing happens within cells and then 641 between cells. The collection of border routers between this cell 642 and the next cell forms a complex destination for which an ARC set 643 can be formed within this cell. This can be done as soon as the 644 cells are formed, before any end-to-end route between cell is 645 computed and whatever the routing protocol between cells is. This 646 model applies in particular for such cells as areas, autonomous 647 systems and optical rings. 649 9.4. Recovery from Node Failures 651 ARCS may be used to achieve fast recovery from node failures as well. 652 The construction of ARC is similar to the construction of backup 653 forwarding arcs forwarding arcs, as discussed in 654 [Xi.2007.Fast-Reroute]. The placement of cursors may still be 655 performed once the backup paths (forwarding edges) are computed after 656 failing each node. 658 10. Manageability 660 This specification describes a generic model. Protocols and 661 management will come later 663 11. IANA Considerations 665 This specification does not require IANA action. 667 12. Security Considerations 669 This specification is not found to introduce new security threat. 671 13. Acknowledgements 673 The authors wishes to thank Alia Atlas, Patrice Bellagamba, Stewart 674 Bryant, Robert Kebler, and Andras Csaszar for their participation to 675 this particular work, and Dirk Anteunis, IJsbrand Wijnands, George 676 Swallow, Eric Osborne, Clarence Filsfils and Eric Levy-Abegnoli for 677 their continuous support to components of the work presented here. 679 14. References 681 14.1. Normative References 683 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 684 Requirement Levels", BCP 14, RFC 2119, March 1997. 686 [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free 687 Convergence", RFC 5715, January 2010. 689 14.2. Informative References 691 [I-D.enyedi-rtgwg-mrt-frr-algorithm] 692 Atlas, A., Envedi, G., Csaszar, A., and A. Gopalan, 693 "Algorithms for computing Maximally Redundant Trees for 694 IP/LDP Fast- Reroute", 695 draft-enyedi-rtgwg-mrt-frr-algorithm-02 (work in 696 progress), October 2012. 698 [I-D.ietf-rtgwg-mrt-frr-architecture] 699 Atlas, A., Kebler, R., Envedi, G., Csaszar, A., 700 Konstantynowicz, M., White, R., and M. Shand, "An 701 Architecture for IP/LDP Fast-Reroute Using Maximally 702 Redundant Trees", draft-ietf-rtgwg-mrt-frr-architecture-01 703 (work in progress), March 2012. 705 [I-D.thubert-rtgwg-arc] 706 Thubert, P. and P. Bellagamba, "Available Routing 707 Constructs", draft-thubert-rtgwg-arc-00 (work in 708 progress), October 2012. 710 [RFC5921] Bocci, M., Bryant, S., Frost, D., Levrau, L., and L. 711 Berger, "A Framework for MPLS in Transport Networks", 712 RFC 5921, July 2010. 714 14.3. References 716 [Cho.2012.Independent-DAG] 717 Cho, S., Elhourani, T., and S. Ramasubramanian, 718 "Independent Directed Acyclic Graphs for Resilient 719 Multipath Routing", IEEE/ACM Transactions on Networking, 720 vol. 20, no. 1 , February 2012, 721 . 723 [Erlebach.2009.Path-Splicing] 724 Erlebach, T. and A. Mereu, "Path splicing with guaranteed 725 fault tolerance", Proceedings of IEEE GLOBECOM , November- 726 December 2009, 727 . 729 [Jayavelu.2009.Maintaining] 730 Jayavelu, G., Ramasubramanian, S., and O. Younis, 731 "Maintaining colored trees for disjoint multipath routing 732 under node failures", IEEE/ACM Transactions on Networking, 733 vol. 17, no. 1 , February 2009, 734 . 736 [Xi.2007.Fast-Reroute] 737 Xi, K. and H. Chao, "IP fast rerouting for single-link/ 738 node failure recovery", Proceedings of IEEE BROADNETS , 739 September 2007, . 742 Authors' Addresses 744 Pascal Thubert (editor) 745 Cisco Systems 746 Village d'Entreprises Green Side 747 400, Avenue de Roumanille 748 Batiment T3 749 Biot - Sophia Antipolis 06410 750 FRANCE 752 Phone: +33 497 23 26 34 753 Email: pthubert@cisco.com 755 Gabor Sandor Enyedi 756 Ericsson 758 Srinivasan Ramasubramanian 759 University of Arizona 760 1230 E. Speedway Blvd. 761 Tucson, AZ 85721 762 USA 764 Phone: +1 520 621 4521 765 Email: srini@ece.arizona.edu