| RTGWG | P. Thubert, Ed. |
| Internet-Draft | Cisco |
| Intended status: Informational | G. Enyedi |
| Expires: July 26, 2015 | Ericsson |
| S. Ramasubramanian | |
| UA | |
| January 22, 2015 |
ARC vs. MRT
draft-thubert-rtgwg-arc-vs-mrt-01
This draft compares the capabilities offered by the Available Routing Construct (ARC) and the Maximally Redundant Trees (MRT) techniques in order to support applicability statements.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."
This Internet-Draft will expire on July 26, 2015.
Copyright (c) 2015 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
This document compares MRT and ARCs based on [I-D.enyedi-rtgwg-mrt-frr-algorithm], [I-D.ietf-rtgwg-mrt-frr-architecture] , [I-D.thubert-rtgwg-arc] and [I-D.thubert-rtgwg-arc-bicast] as they were on 10/12/2012. Both solutions may have changed or may change in the future, which would make this document somewhat outdated.
Traditional routing and forwarding uses the concept of path as the basic routing paradigm to get a packet from a source to a destination. A path is represented as an ordered sequence of nodes. This paradigm is greedy in that it requires that the next node represent a progress towards the destination. Greediness is maximized by Shortest Path First (SPF) techniques which optimize for a cost that relates to the amount of forwarding effort and latency, at the expense of network capacity and reliability. In particular, a path is broken as soon as a single link or a single node fails, and getting around a breakage can require path recomputation, network reconvergence, and incur delays and/or microloops till service is restored.
Maximally Redundant Trees [I-D.ietf-rtgwg-mrt-frr-architecture] [I-D.enyedi-rtgwg-mrt-frr-algorithm] (MRT), on the other hand, favors reliability over shorter path. MRT provides two spanning trees rooted at a destination, referred to as red and blue trees. The trees have the property that the red and blue paths from any node to the destination (root of the tree) are maximally-disjoint. The red and blue paths may not be the shortest path. Thus, a node may employ shortest path tree for forwarding under normal circumstances. Thus, every node may have up to three FIB entries for a destination, one for red tree, one for blue tree, and a third for the shortest path tree. Under normal circumstances, the idea is to forward the packets along the shortest path until the packet encounters a failure. If the failed link is red (blue), then the packet is forwarded along the blue (red) path. Once a packet is rerouted along the red or blue tree, it continues to be forwarded along the chosen tree until it reaches the destination. If the packet encounters another failure, then it is dropped. Thus, MRT is guaranteed to recovery from only only failure.
The maximally redundant trees are constructed using a technique called path augmentation. The approach works as follows: (1) For a given destination node, a cycle traversing the node and two other nodes are computed. (2) One direction of the cycle is termed as red, while the other direction is termed as blue. (3) A cycle or path is computed that starts and ends at a node that has been already added to the trees. On this cycle/path, one direction is treated as red and the other direction is treated as blue. The direction of the red and blue trees is computed based on a partial order, which ensures that the red and blue assignments would result in disjoint paths along the red and blue trees. The last step is repeated until all the nodes in the network are considered. For a more detailed description of the construction, refer to [Jayavelu.2009.Maintaining].
MRT constructs trees that are maximally-disjoint. Thus, if the network provided two node-disjoint paths between a node and destination, MRT would provide node-disjoint paths as well. If the network does not provide node-disjoint paths, but provides link-disjoint paths between a node and destination, then MRT would provide link-disjoint paths as well.
Available Routing Construct [I-D.thubert-rtgwg-arc] (ARC) defines a routing construct made of a bidirectional sequence of nodes and links with 2 outgoing edges, so that, upon a single breakage, each lively node in along ARC can still reach one of the outgoing edges. The bi-directional sequence of nodes and links are similar to the paths/cycles used in the path augmentation technique in constructing MRT. The routing graph to reach a certain destination is expressed as a cascade of ARCs, each ARC providing its own independent domain of fault isolation and recovery. Unicast traffic may enter an ARC via any node but it may only leave the ARC through one of its two edges. One node along the ARC is designated as the cursor. In normal unicast operations, the traffic inside an ARC flows away from the cursor towards an edge. Upon a failure, packets may bounce on the breakage point and flow the other way along the ARC to take the other exit. [I-D.thubert-rtgwg-arc] calculates ARCs within the shortest path computation, and both sides of an ARC as delineated by the cursor actually represent the shortest path to the destination.
Applying Available Routing Constructs to bicasting [I-D.thubert-rtgwg-arc-bicast] provides additional information on how an ARC fabric can be used for bicasting applications such as livelive. In this class of applications, at least two disjoint paths must be established between a source and a point of consumption. Ideally, the source is diverse, for instance a distributed Content Delivery Network (CDN), but it does not have to be that way. An ARC fabric can be set up for an Omega that is a multiple destination in the exact same fashion as if Omega is a unique node. [I-D.thubert-rtgwg-arc-bicast] then shows how an ARC set can be painted in two colors, an half of each ARC with one color and the secong half of the other color in such a fashion that in most cases, an edge of a certain color ends in the half of the next ARC that is of the same color. A colored packet has the constraint to exit each ARC along its path via the edge of its own color. If the edge and the next half ARC are of the same color, the packet follows the shortest path towards Omega. It results that ARC biscasting agressively pursues the goal that both colored paths are close to shortest even though disjoint. The quality of that closeness depends on the way the ARC set was painted, which itself depends, in the bicasting algorithm, on the starting points in Omega. A centralized computation can probably improve the result that the simple technique in [I-D.thubert-rtgwg-arc-bicast] obtains.
This drafts compares the properties of the ARC an MRT techniques in a number of example situations that are crafted to highlight their particular behaviors with an educational purpose in mind, as opposed to represent the most classical real-world cases. It must be noted that though the draft focuses on differences, ARCs and MRT have a lot in common, in particular both provide maximally redundant solutions, and represent roughly the same amount of labels and states in the packets.
The draft uses terminology from [I-D.enyedi-rtgwg-mrt-frr-algorithm] and [I-D.thubert-rtgwg-arc].
A--- 2 ---E A E
| | v
1 1 v
| | v
B--- 1 ---F B >>>>>>> F
| | v v
1 1 v v
| | v v
C--- 1 ---G C >>>>>>> G
| | v
1 1 v
| | v
D--- 1 ---H D H
Topology SPF A to H
Figure 1: Reference Topology
This draft uses a simple reference topology, made of eight nodes A to H and ten links with costs of either 1 or 2 as represented below:
A=========E 5 ------> 4 A <rrrrrr E A bbbbbb> E
| | ^ | r b
| | | | r b
| | | V v v
B=========F 6 ------> 3 B <rrrrrr F B bbbbbb> F
| | ^ | r b
| | | | r b
| | | V v v
C=========G 7 ------> 2 C <rrrrrr G C bbbbbb> G
|| | ^ | r ^ b
|| | | | r b b
|| | | V v b v
D---------H 8 <------ 1 D rrrrrr> H D H
MRT MRT MRT
ARC set GADAG graph Red Tree BLUE Tree
Figure 2: ARC set and MRT Trees
The oLAF algorithm forms three ARCs and MRT forms two trees:
A E A E A E
v v v
v v v
v v v
B >>>>>>> F B >>>>>>> F B >>>>>>> F
v v v v v v
v v v v v v
v v v v v v
C >>>>>>> G C >>>>>>> G C >>>>>>> G
v v v
v v v
v v v
D H D H D H
ARC SPF MRT
Figure 3: Normal Operation
In normal operations MRT trees are not used so the MRT case is identical to the SPF case. For ARCs, the cursors A B and C may send traffic on either side but favor shortest. For A that means sending to B and for C sending to G. B sees an equal cost so it may distribute its traffic.
A E A E A E
v v v
v v v
v v v
B >>>>>>> F B >>>>>>> F B >>>>>>> F
v <<<<<<< v v r <rrrrrr v
v \/ \/ r \/
v /\ /\ v /\
C >>>>>>> G C G C G
v r
v r
v v
D H D H D rrrrrr> H
ARC SPF MRT
Figure 4: ARC closer to shortest path
Upon a first breakage, SPF cannot make a greedy progress so a packet that follows the broken path is dropped. MRT converts to the packet to blue or red, and then packet is placed in the associated tree till the destination. Because blue and red have to be non-congruent to the end, the detour that MRT generates tends to route the packet away from shortest path. ARCs returns the packet along the current ARC so it exits on the other edge. As soon as the cursor in the current ARC is passed, the packet is again on shortest path.
A E A E A E
v v v
v v v
v v v
B >>>>>>> F B >>>>>>> F B >>>>>>> F
v <<<<<<< v v r <rrrrrr v
v v v r v
v v v v v
C >>>>>>> \/ C \/ C \/
v <<<<<<< /\ /\ r /\
v r
v v
D >>>>>>> H D H D rrrrrr> H
ARC SPF MRT
Figure 5: ARCs may revisit broken node
Because the blue and red paths of MRT are link-disjoint from any node to the destination, the recovery path does not visit a broken link again. ARCs achieve a shorter path by being more greedy. It results that in some situations, a broken node might be visited twice, once from the above, that is from an incoming ARC, and then from the side, that is from inside its own ARC. This is illustrated below though it would take an intermediate node between C and broken G to actually create the undesired bouncing that is discussed here.
MRT recovers from node failure similar to that of link failure. Note that the paths provided by MRT are maximally disjoint. Thus at a node, if a link is unavailable (whether due to a link failure or node failure), the recovery path is taken. As the paths are maximally disjoint, MRT guarantees that a failed node would never be visited again.
A >>>>>>> E A E A bbbbbb> E
v v v v b
\/ v \/ \/ b
/\ v /\ /\ v
B <<<<<<< F B F B F
v v v
v \/ \/
v /\ /\
C >>>>>>> G C G C G
v
v
v
D H D H D H
ARC SPF MRT
Figure 6: Each ARC its own recovery domain
Upon a first breakage, SPF cannot make a greedy progress so a packet that follows the broken path is dropped. Upon a first breakage, MRT selects either blue or red. If that selected path is broken down the road, the packet is dropped. In the data plane, ARCs protect against one breakage per ARC. Once a packet leaves an ARC to cascade in the next, stigmata from a previous breakage are removed. So a break on the next ARC can be resolved as well.
MRT ARC
1. Limited complexity - Complexity inherited from SPF
can be even O(e)
2. Detour, Short detour then Shortest Path
unrelated to Shortest Path again
3. Smaller chance to avoid unrelated Higher chance to avoid unrelated
failures failures
=> may address SRLG cases
4. Single failure: reroute at most Single failure may incur double
once reroute
5. Load balancing with traditional Non-equal Cost Load Balancing
ECMP capabilities
6. Unrelated "topologies" exists Detours are strongly bound to
-> reconfiguration after the default paths
failure is simple => reconfiguration techniques
are difficult
7. Non-Congruent bicasting is not Shorter Path bicasting with
addressed collision avoidance
8. Source-centric computation Destination-centric computation
-> easier to distribute => enables complex destinations
(multiple equivalent ARC set
terminations
Figure 7: Comparison summary
In sumary:
In this section, we elaborate on the differences listed above.
1.
ARC is a destination based technology, i.e. it compute a set of ARCs to all the destinations in the network. Constructing one such set needs several shortest path computations. This may cause a minor problem: since detours and default paths are bound, computing the new default paths after a failure may be delayed due to this slower computation.
In contrast, MRT used the traditional shortest paths in a failure-free state, thus detours can be computed separately, when all the shortest paths are up and running. Moreover, although MRT offers multiple ways to construct detours (keep in mind that MRT is only for detours, default paths are computed with SPF), even the slowest one is as fast as computing one set of ARCs for a single destination; the fastest algorithm takes only O(e) time, so it is linear with the number of links in the network.
2.
In MRT, the paths from any node to the destination on the red and blue trees are link-disjoint, while in ARC, it is not. Thus, in MRT, neither the red nor the blue tree is guaranteed to provide shortest path for a node. However, in ARC, packet is forwarded along the shortest path after a short detour. Naturally, when there is no failure, both algorithms use the shortest paths, thus this difference can only be observed after a failure.
3.
MRT uses separated default paths and detours. As a consequence, one needs to have three FIB entries one for shortest path forwarding (default), one for red tree forwarding, and one for blue tree forwarding. When a failure happens, MRT puts the packet onto a detour, which is not removed until it reaches the destination (egress router, area border router, etc..). Thus, packet is bound to either the red path, or the blue path. When the packet encounters a second failure, the packet is dropped.
Although the MRT draft [I-D.ietf-rtgwg-mrt-frr-architecture] does not discuss about recovering from multiple failures, the MRT framework allows the network to recover from multiple link failures, as long as no more than one failure is seen on a path/cycle that's used for augmentation. Thus, when a packet is forwarded from one path/cycle to another, the packet can handle one more link failure. This technique has been shown in [Erlebach.2009.Path-Splicing].
In contrast, ARC partitions the network in delimited protection areas, i.e. it puts packets back to shortest path when they leave the current ARC. Putting packets back to the shortest path as soon as they leave the ARC makes it possible to reroute again at another failure. Moreover, theoretically ARC needs only two labels/addresses per destination, one describing the shortest path, and the other describing the other direction in the ARC. However, this approach would result loops, if there are more than one failure in the same ARC, thus current version of ARC use at least three labels/addresses per destination.
ARC can protect against multiple link failures as long as the only one link failure occurs on an ARC.
Since there is always a reconfiguration after a failure, and FRR is in charge only for a short amount of time while this reconfiguration takes place, one may think that preparing for more than one failure is not important. However, there are the "Shared Risk Link Groups" (SRLG), groups of links sharing the same fate due to some hidden common property (e.g. they are using the same optical cable), which may cause multiple failures at the same time. Even if both MRT and ARC can deal with the most common types of SRLGs (failure of links of the same linecard, and the failure of some ethernet network under the level of IP; namely the "LAN failure"), it is better to protect as many resources as possible.
4.
For the price of having only one reroute, MRT can guarantee that the same failure will never be visited again. In contrast, since the same node can be an exit point for multiple ARCs, and since ARC puts packets back to shortest path after a failure, it is possible that a single failed node will be visited multiple times. It is very important that ARCs will properly handle this case with multiple rerouting, so sooner or later the destination will be reached. Moreover, the probability of such situation seems to be low.
5.
ARC can provide load balancing for the traffic with the "cursor node", since ARC gives not only a backup, but a new way for default routing as well. In contrast, since MRT only provide the detours, load balancing is not in the focus of MRT, but it is done with traditional ECMP. However, it is possible that a node have multiple blue or red next-hops with MRT, and in this case load balancing is possible even for packets on detours.
6.
IPFRR techniques are for designed for protection, i.e. they are used immediately after a failure happens. Typically after a failure, traditional routing protocols like OSPF reexplore the topology and reconfigure the forwarding entries based on the new topology. Packets start using the new shortest paths, and the network prepares to protect against a new failure. Normally, the reconfiguration after a failure may cause transient forwarding anomalies like micro-loops, but these are not acceptable for IPFRR.
Thus, several loop-preventing techniques were proposed in [RFC5715]. Since MRT provides two independent routing, i.e. the default shortest paths and the detours, it can use even Farside tunnels, which does not need protocol extension (basically, MRT can use one routing, while it reconfigures the other). Although, ARC is capable for loopfree convergence with centralized loop routing, it is not clear, which technique ARC could use in a distributed environment.
7.
Since MRT is an FRR technique, bicasting is out of its scope. However, bicasting is theoretically possible, if we use the blue and the red next-hops; naturally, these paths will be node- and link-disjoint. In contrast, ARC was designed for not only FRR but bicasting, even if it cannot automatically provide disjoint paths. The advantage is that those paths can be shorter. For further details consult [I-D.thubert-rtgwg-arc].
MRT uses a helper graph called GADAG, and detour computation is based on that graph. This helper graph is basically a set of ARCs with some extra direction information for the GADAG root as a destination. Thanks to this common point, computation algorithm and detours are very similar.
ARC is not only for FRR, but a complex forwarding technique, which can help in load balancing and speed up reconfiguration. Since MRT is an only for IPFRR, it cannot change routing in any way in a failure-free state, and the following properties do not exist.
However, it is important to note that for the advantages below we need to introduce the "cursor" node. Using the concept of a cursor needs some protocol extension, and it replaces traditional shortest path routing in some sense.
A E A E A >>>>>>> E
v ^ v
v | v
v | v
B >>\/ F B \/ F B \/ F
v /\ /\ /\ v
\/ \/ \/ v
/\ /\ /\ v
C G C G C G
v
v
v
D H D H D H
Double Control plane Exit path
breakage Link reversal stands out
Figure 8: SRLG case
In control plane, ARCs can find an exit if one exists and in principle, can be used to solve the Shared Risk Link Group (SRLG) problem. An ARC set is a Directed Acyclic Graph of ARCs, thus link reversal techniques can be applied to recover from complex breakages. Upon a second breakage in a same ARC, a segment is isolated. In control plane, it is possible to return all the incoming links in that segment. This may recurse if incoming ARCs become isolated as well. If the process recurses, a link may be returned a number of times and this must be stopped by some infinity count. Once the local recovery settles, the exit path stands out.
Recovery from multiple failures may also be performed using a variant of redundant trees, called independent directed acyclic graphs, which aims to utilize all the links in the network [Cho.2012.Independent-DAG]. With this approach, every node has one or more forwarding edges in the red/blue trees. Upon failure of all the red forwarding edges, the packet is transferred to the blue tree.
The MRT and ARC techniques may be used for routing to redundant destination nodes. Given two nodes R1 and R2, MRT can construct two trees, tree T1 rooted at R1 and tree T2 rooted at R2. The path from any node to R1 on T1 and to R2 on T2 are still maximally-disjoint [Jayavelu.2009.Maintaining]. Similarly, the oLAF algorithm used for constructing ARCs is destination-oriented, in that it forms ARCs from the standpoint of the destination. This makes ARCs more complex to compute in a distributed fashion, but on the other hand enables to group a set of nodes.
One example of employing multiple destinations is to employ multiple border routers between one area and another. Thus, the routing in one area may exit to the other area through one of the border routers.
With multiple destinations, it is possible not only to allow high availability but also to dynamically load balance between the member nodes. In an ARC, the node that has the logical responsibility of cursor is the only node that may send packets towards both edges in normal conditions. It is possible to create a control loop between a congestion point on one side and the cursor, in order to balance more traffic towards the other edge. If the cursor sends all its traffic towards the other edge, then the cursor responsibility may be transferred to the next node towards the congested edge to balance more traffic. If both edges are congested, then the congestion indication can be recursively injected in incoming ARCs.
A<==cur==>E A<==cur==>E A<==cur==>E
| | | | | |
| | | | | |
v v v v v v
B<==cur==>F B<==cur==>F B<==cur F
| | | | | |
| | | | | con
v v v v v gest
C<==cur==>G C<==cur G C<=======cur
| | | | | |
| | | con | con
v v v gest v gest
D OMEGA H D OMEGA H D OMEGA H
Destination is control loop recursing
both A and H to cursor control loop
Figure 9: Complex Destination and Load Balancing
An ARC based control loop does not need to involve metric changes or other routing advertisements, so it can be kept separate from the routing protocol. A simple control loop protocol can be used, that can be kept from oscillating with appropriate periods and adaptive filters.
In a hierarchical network, routing happens within cells and then between cells. The collection of border routers between this cell and the next cell forms a complex destination for which an ARC set can be formed within this cell. This can be done as soon as the cells are formed, before any end-to-end route between cell is computed and whatever the routing protocol between cells is. This model applies in particular for such cells as areas, autonomous systems and optical rings.
ARCS may be used to achieve fast recovery from node failures as well. The construction of ARC is similar to the construction of backup forwarding arcs forwarding arcs, as discussed in [Xi.2007.Fast-Reroute]. The placement of cursors may still be performed once the backup paths (forwarding edges) are computed after failing each node.
MRT is not designed to compute an operational path but rather an alternate fast reroute solution that avoids any potential single breakage in the operational path that is computed otherwise, e.g. using the Shortest Path First algorithm. On the other hand, An ARC fabric joins together branches of a shortest path trees, so that most of the way along an ARC Set is shortest. Coloring the ARC Set for live live forces a colored packet to exit an ARC at an edge that is not always the shortest, but often is. It results that by design, both colored path are close to shortest, making ARCs a potential solution for livelive. Additionally, the support of an Omega that is formed of multiple destinations is a valuable asset for some applications such as video distribution. An ARC Set can be designed so that the lowest ARCs are between CDNs. It results that with a single ARC Set, all nodes in the network would have a pair of path that enable distribution from a relatively close CDN.
This specification describes a generic model. Protocols and management will come later
This specification does not require IANA action.
This specification is not found to introduce new security threat.
The authors wishes to thank Alia Atlas, Patrice Bellagamba, Stewart Bryant, Robert Kebler, and Andras Csaszar for their participation to this particular work, and Dirk Anteunis, IJsbrand Wijnands, George Swallow, Eric Osborne, Clarence Filsfils and Eric Levy-Abegnoli for their continuous support to components of the work presented here.
| [RFC2119] | Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. |
| [RFC5715] | Shand, M. and S. Bryant, "A Framework for Loop-Free Convergence", RFC 5715, January 2010. |
| [I-D.enyedi-rtgwg-mrt-frr-algorithm] | Envedi, G., Csaszar, A., Atlas, A., cbowers@juniper.net, c. and A. Gopalan, "Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- Reroute", Internet-Draft draft-enyedi-rtgwg-mrt-frr-algorithm-04, October 2013. |
| [I-D.ietf-rtgwg-mrt-frr-architecture] | Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar, A., Tantsura, J. and R. White, "An Architecture for IP/LDP Fast-Reroute Using Maximally Redundant Trees", Internet-Draft draft-ietf-rtgwg-mrt-frr-architecture-05, January 2015. |
| [I-D.thubert-rtgwg-arc] | Thubert, P. and P. Bellagamba, "Available Routing Constructs", Internet-Draft draft-thubert-rtgwg-arc-02, July 2014. |
| [I-D.thubert-rtgwg-arc-bicast] | Thubert, P. and I. Wijnands, "Applying Available Routing Constructs to bicasting", Internet-Draft draft-thubert-rtgwg-arc-bicast-01, October 2013. |
| [RFC5921] | Bocci, M., Bryant, S., Frost, D., Levrau, L. and L. Berger, "A Framework for MPLS in Transport Networks", RFC 5921, July 2010. |
| [Cho.2012.Independent-DAG] | Cho, S., Elhourani, T. and S. Ramasubramanian, "Independent Directed Acyclic Graphs for Resilient Multipath Routing", IEEE/ACM Transactions on Networking, vol. 20, no. 1 , February 2012. |
| [Erlebach.2009.Path-Splicing] | Erlebach, T. and A. Mereu, "Path splicing with guaranteed fault tolerance", Proceedings of IEEE GLOBECOM , November-December 2009. |
| [Jayavelu.2009.Maintaining] | Jayavelu, G., Ramasubramanian, S. and O. Younis, "Maintaining colored trees for disjoint multipath routing under node failures", IEEE/ACM Transactions on Networking, vol. 17, no. 1 , February 2009. |
| [Xi.2007.Fast-Reroute] | Xi, K. and H. Chao, "IP fast rerouting for single-link/node failure recovery", Proceedings of IEEE BROADNETS , September 2007. |