--- 1/draft-ietf-rtgwg-mrt-frr-algorithm-00.txt 2014-07-04 11:14:32.632193398 -0700 +++ 2/draft-ietf-rtgwg-mrt-frr-algorithm-01.txt 2014-07-04 11:14:32.752196291 -0700 @@ -1,24 +1,24 @@ Routing Area Working Group G. Enyedi, Ed. Internet-Draft A. Csaszar Intended status: Standards Track Ericsson -Expires: August 18, 2014 A. Atlas, Ed. +Expires: January 5, 2015 A. Atlas, Ed. C. Bowers Juniper Networks A. Gopalan University of Arizona - February 14, 2014 + July 4, 2014 Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- Reroute - draft-ietf-rtgwg-mrt-frr-algorithm-00 + draft-ietf-rtgwg-mrt-frr-algorithm-01 Abstract A complete solution for IP and LDP Fast-Reroute using Maximally Redundant Trees is presented in [I-D.ietf-rtgwg-mrt-frr- architecture]. This document defines the associated MRT Lowpoint algorithm that is used in the default MRT profile to compute both the necessary Maximally Redundant Trees with their associated next-hops and the alternates to select for MRT-FRR. @@ -30,21 +30,21 @@ 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 August 18, 2014. + This Internet-Draft will expire on January 5, 2015. Copyright Notice Copyright (c) 2014 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 @@ -60,45 +60,48 @@ 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 5 3. Terminology and Definitions . . . . . . . . . . . . . . . . . 5 4. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 7 4.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 7 4.2. Finding an Ear and the Correct Direction . . . . . . . . 9 4.3. Low-Point Values and Their Uses . . . . . . . . . . . . . 11 4.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 15 4.5. Determining Local-Root and Assigning Block-ID . . . . . . 17 5. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 19 5.1. MRT Island Identification . . . . . . . . . . . . . . . . 20 - 5.2. Root Selection . . . . . . . . . . . . . . . . . . . . . 21 + 5.2. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21 5.3. Initialization . . . . . . . . . . . . . . . . . . . . . 21 5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance . . . . . . . . . . . . . . . . . . . . . . . 22 5.5. Augmenting the GADAG by directing all links . . . . . . . 24 5.6. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 26 5.6.1. MRT next-hops to all nodes partially ordered with respect to the computing node . . . . . . . . . . . . 27 5.6.2. MRT next-hops to all nodes not partially ordered with respect to the computing node . . . . . . . . . . . . 28 5.6.3. Computing Redundant Tree next-hops in a 2-connected Graph . . . . . . . . . . . . . . . . . . . . . . . . 29 - 5.6.4. Generalizing for graph that isn't 2-connected . . . . 30 + 5.6.4. Generalizing for a graph that isn't 2-connected . . . 30 5.6.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 31 5.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 33 5.8. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 37 - 6. MRT Lowpoint Algorithm: Complete Specification . . . . . . . 40 + 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 40 7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 40 7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 41 - 8. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 51 - 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 51 - 10. Security Considerations . . . . . . . . . . . . . . . . . . . 51 - 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 51 - 11.1. Normative References . . . . . . . . . . . . . . . . . . 51 - 11.2. Informative References . . . . . . . . . . . . . . . . . 51 + 8. Implementation Status . . . . . . . . . . . . . . . . . . . . 51 + 9. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 51 + 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 51 + 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 51 + 12. Security Considerations . . . . . . . . . . . . . . . . . . . 51 + 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 51 + 13.1. Normative References . . . . . . . . . . . . . . . . . . 51 + 13.2. Informative References . . . . . . . . . . . . . . . . . 51 + Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 53 Appendix B. Option 3: Computing GADAG using a hybrid method . . 58 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 60 1. Introduction MRT Fast-Reroute requires that packets can be forwarded not only on the shortest-path tree, but also on two Maximally Redundant Trees (MRTs), referred to as the MRT-Blue and the MRT-Red. A router which experiences a local failure must also have pre-determined which @@ -383,21 +386,21 @@ root - and the actual algorithm is given in Section 5.4. In order to understand the basic idea of finding an ADAG, first suppose that we have already a partial ADAG, which doesn't contain all the nodes in the block yet, and we want to extend it to cover all the nodes. Suppose that we find a path from a node X to Y such that X and Y are already contained by our partial ADAG, but all the remaining nodes along the path are not added to the ADAG yet. We refer to such a path as an ear. - Recall that our ADAG is closely related to a partial order, more + Recall that our ADAG is closely related to a partial order. More precisely, if we remove root R, the remaining DAG describes a partial order of the nodes. If we suppose that neither X nor Y is the root, we may be able to compare them. If one of them is definitely lesser with respect to our partial order (say X<C and C->D are added). If B >> D, we would add the same path in reverse direction. If in the partial order where an ear's two ends are X and Y, X << Y, then there must already be a directed path from X to Y in the ADAG. The ear must be added in a direction such that it doesn't create a cycle; therefore the ear must go from X to Y. @@ -443,23 +446,23 @@ and then finding a path from N to R that doesn't use any links between R and N. The direction of the cycle can be assigned either way since it is starting the ordering. Once a partial ADAG is already present, it will always have a node that is not the root R in it. As a brief proof that a partial ADAG can always have ears added to it: just select a non-ready neighbor N of a ready node Q, such that Q is not the root R, find a path from N to the root R in the graph with Q removed. This path is an ear where the first node of the ear is Q, the next is N, then the path until - the first ready node the path reached (that second ready node is the - other endpoint of the path). Since the graph is 2-connected, there - must be a path from N to R without Q. + the first ready node the path reached (that ready node is the other + endpoint of the path). Since the graph is 2-connected, there must be + a path from N to R without Q. It is always possible to select a non-ready neighbor N of a ready node Q so that Q is not the root R. Because the network is 2-connected, N must be connected to two different nodes and only one can be R. Because the initial cycle has already been added to the ADAG, there are ready nodes that are not R. Since the graph is 2-connected, while there are non-ready nodes, there must be a non- ready neighbor N of a ready node that is not R. Generic_Find_Ears_ADAG(root) @@ -484,25 +487,25 @@ we will get an ADAG. The method used for finding and selecting the ears is important; shorter ears result in shorter paths along the MRTs. The MRT Lowpoint algorithm's method using Low-Point Inheritance is defined in Section 5.4. Other methods are described in the Appendices (Appendix A and Appendix B). As an example, consider Figure 5 again. First, we select the shortest cycle containing R, which can be R-A-B-F-D-E (uniform link costs were assumed), so we get to the situation depicted in Figure 5 (b). Finally, we find a node next to a ready node; that must be node - C and assume we reached it from ready node B. We search a path from C - to R without B in the original graph. The first ready node along - this is node D, so the open ear is B-C-D. Since B<C - and C->D to the ADAG. Since all the nodes are ready, we stop at this - point. + C and assume we reached it from ready node B. We search a path from + C to R without B in the original graph. The first ready node along + this is node D, so the open ear is B-C-D. Since B<C and C->D to the ADAG. Since all the nodes are ready, we stop at + this point. 4.3. Low-Point Values and Their Uses A basic way of computing a spanning tree on a network graph is to run a depth-first-search, such as given in Figure 7. This tree has the important property that if there is a link (x, n), then either n is a DFS ancestor of x or n is a DFS descendant of x. In other words, either n is on the path from the root to x or x is on the path from the root to n. @@ -517,25 +520,69 @@ DFS_Visit(w, x) Run_DFS(node root) dfs_number = 0 DFS_Visit(root, NONE) Figure 7: Basic Depth-First Search algorithm Given a node x, one can compute the minimal DFS number of the neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the - highest attachment point neighbouring x. What is interesting, - though, is what is the highest attachment point from x and x's + earliest attachment point neighbouring x. What is interesting, + though, is what is the earliest attachment point from x and x's descendants. This is what is determined by computing the Low-Point - value, as given in Algorithm Figure 9 and illustrated on a graph in - Figure 8. + value. + + In order to compute the low point value, the network is traversed + using DFS and the vertices are numbered based on the DFS walk. Let + this number be represented as DFS(x). All the edges that lead to + already visited nodes during DFS walk are back-edges. The back-edges + are important because they give information about reachability of a + node via another path. + + The low point number is calculated by finding: + + Low(x) = Minimum of ( (DFS(x), + Lowest DFS(n, x->n is a back-edge), + Lowest Low(n, x->n is tree edge in DFS walk) ). + + A detailed algorithm for computing the low-point value is given in + Figure 8. Figure 9 illustrates how the lowpoint algorithm applies to + a example graph. + + global_variable: dfs_number + + Lowpoint_Visit(node x, node parent, interface p_to_x) + D(x) = dfs_number + L(x) = D(x) + dfs_number += 1 + x.dfs_parent = parent + x.dfs_parent_intf = p_to_x + x.lowpoint_parent = NONE + for each interface intf of x + if D(intf.remote_node) is not set + Lowpoint_Visit(intf.remote_node, x, intf) + if L(intf.remote_node) < L(x) + L(x) = L(intf.remote_node) + x.lowpoint_parent = intf.remote_node + x.lowpoint_parent_intf = intf + else if intf.remote_node is not parent + if D(intf.remote_node) < L(x) + L(x) = D(intf.remote_node) + x.lowpoint_parent = intf.remote_node + x.lowpoint_parent_intf = intf + + Run_Lowpoint(node root) + dfs_number = 0 + Lowpoint_Visit(root, NONE, NONE) + + Figure 8: Computing Low-Point value [E]---| [J]-------[I] [P]---[O] | | | | | | | | | | | | [R] [D]---[C]--[F] [H]---[K] [N] | | | | | | | | | | | | [A]--------[B] [G]---| [L]---[M] (a) a non-2-connected graph @@ -559,71 +606,43 @@ | | | | | | [R] [D]---[C]---[F] [H]----[K] [N] (0, ) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11) | | | | | | | | | | | | [A]---------[B] [G]----| [L]------[M] (1,0) (2,0) (7,3) (12,11) (13,11) (c) with low-point values assigned (D(x), L(x)) - Figure 8 - - global_variable: dfs_number - - Lowpoint_Visit(node x, node parent, interface p_to_x) - D(x) = dfs_number - L(x) = D(x) - dfs_number += 1 - x.dfs_parent = parent - x.dfs_parent_intf = p_to_x - x.lowpoint_parent = NONE - for each interface intf of x: - if D(intf.remote_node) is not set - Lowpoint_Visit(intf.remote_node, x, intf) - if L(intf.remote_node) < L(x) - L(x) = L(intf.remote_node) - x.lowpoint_parent = intf.remote_node - x.lowpoint_parent_intf = intf - else if intf.remote_node is not parent - if D(intf.remote_node) < L(x) - L(x) = D(intf.remote) - x.lowpoint_parent = intf.remote_node - x.lowpoint_parent_intf = intf - - Run_Lowpoint(node root) - dfs_number = 0 - Lowpoint_Visit(root, NONE, NONE) - - Figure 9: Computing Low-Point value + Figure 9: Example lowpoint value computation From the low-point value and lowpoint parent, there are three very useful things which motivate our computation. First, if there is a child c of x such that L(c) >= D(x), then there are no paths in the network graph that go from c or its descendants - to an ancestor of x - and therefore x is a cut-vertex. In Figure 8, + to an ancestor of x - and therefore x is a cut-vertex. In Figure 9, this can be seen by looking at the DFS children of C. C has two children - D and F and L(F) = 3 = D(C) so it is clear that C is a cut-vertex and F is in a block where C is the block's root. L(D) = 0 > 3 = D(C) so D has a path to the ancestors of C; in this case, D can go via E to reach R. Comparing the low-point values of all a node's DFS-children with the node's DFS-value is very useful because it allows identification of the cut-vertices and thus the blocks. Second, by repeatedly following the path given by lowpoint_parent, there is a path from x back to an ancestor of x that does not use the link [x, x.dfs_parent] in either direction. The full path need not be taken, but this gives a way of finding an initial cycle and then ears. - Third, as seen in Figure 8, even if L(x) < D(x), there may be a block + Third, as seen in Figure 9, even if L(x) < D(x), there may be a block that contains both the root and a DFS-child of a node while other DFS-children might be in different blocks. In this example, C's child D is in the same block as R while F is not. It is important to realize that the root of a block may also be the root of another block. 4.4. Blocks in a Graph A key idea for an MRT algorithm is that any non-2-connected graph is made up by blocks (e.g. 2-connected clusters, cut-links, and/or @@ -778,21 +797,21 @@ its interfaces have been ordered as per Figure 14. 1. Compute the local MRT Island for the particular MRT Profile. [See Section 5.1.] 2. Select the root to use for the GADAG. [See Section 5.2.] 3. Initialize all interfaces to UNDIRECTED. [See Section 5.3.] 4. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See - Figure 9.] + Figure 8.] 5. Construct the GADAG. [See Section 5.4] 6. Assign directions to all interfaces that are still UNDIRECTED. [See Section 5.5.] 7. From the computing router x, compute the next-hops for the MRT- Blue and MRT-Red. [See Section 5.6.] 8. Identify alternates for each next-hop to each destination by @@ -826,43 +845,48 @@ return A_LESS_THAN_B return B_LESS_THAN_A Figure 14: Rules for ranking multiple interfaces. Order is from low to high. 5.1. MRT Island Identification The local MRT Island for a particular MRT profile can be determined by starting from the computing router in the network graph and doing - a breadth-first-search (BFS), exploring only links that aren't MRT- - ineligible. + a breadth-first-search (BFS). The BFS explores only links that are + in the same area/level, are not IGP-excluded, and are not MRT- + ineligible. The BFS explores only nodes that are are not IGP- + excluded, and that support the particular MRT profile. See section 7 + of [I-D.ietf-rtgwg-mrt-frr-architecture] for more precise definitions + of these criteria. - MRT_Island_Identification(topology, computing_rtr, profile_id) + MRT_Island_Identification(topology, computing_rtr, profile_id, area) for all routers in topology rtr.IN_MRT_ISLAND = FALSE computing_rtr.IN_MRT_ISLAND = TRUE explore_list = { computing_rtr } while (explore_list is not empty) next_rtr = remove_head(explore_list) for each interface in next_rtr - if interface is not MRT-ineligible + if interface is (not MRT-ineligible and not IGP-excluded + and in area) if ((interface.remote_node supports profile_id) and (interface.remote_node.IN_MRT_ISLAND is FALSE)) interface.remote_node.IN_MRT_ISLAND = TRUE add_to_tail(explore_list, interface.remote_node) Figure 15: MRT Island Identification -5.2. Root Selection +5.2. GADAG Root Selection - In Section 7 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG Root - Selection is described for the MRT default profile. In + In Section 8.3 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG + Root Selection Policy is described for the MRT default profile. In [I-D.atlas-ospf-mrt] and [I-D.li-isis-mrt], a mechanism is given for routers to advertise the GADAG Root Selection Priority and consistently select a GADAG Root inside the local MRT Island. The MRT Lowpoint algorithm simply requires that all routers in the MRT Island MUST select the same GADAG Root; the mechanism can vary based upon the MRT profile description. Before beginning computation, the network graph is reduced to contain only the set of routers that support the specific MRT profile whose MRTs are being computed. Analysis has shown that the centrality of a router can have a @@ -879,29 +903,32 @@ next-hops, and flags associated with algorithm. It is assumed that a regular SPF computation has been run so that the primary next-hops from the computing router to each destination are known. This is required for determining alternates at the last step. Initially, all interfaces MUST be initialized to UNDIRECTED. Whether they are OUTGOING, INCOMING or both is determined when the GADAG is constructed and augmented. - Due to manageability consideration - [I-D.ietf-rtgwg-lfa-manageability], overload, or a transient cause - such as [RFC3137], it is possible that some links and nodes will be - marked as unusable. This constraint must be consistently flooded via - the IGP [I-D.atlas-ospf-mrt] [I-D.li-isis-mrt] so that links are - clearly known to be MRT-ineligible and not explored or used in the - MRT algorithm. In the algorithm description, it is assumed that such - links and nodes will not be explored or used and no more discussion - is given of this restriction. + It is possible that some links and nodes will be marked as unusable + using standard IGP mechanisms (see section 7 of + [I-D.ietf-rtgwg-mrt-frr-architecture]). Due to FRR manageability + considerations [I-D.ietf-rtgwg-lfa-manageability], it may also be + desirable to administratively configure some interfaces as ineligible + to carry MRT FRR traffic. This constraint MUST be consistently + flooded via the IGP [I-D.atlas-ospf-mrt] [I-D.li-isis-mrt] by the + owner of the interface, so that links are clearly known to be MRT- + ineligible and not explored or used in the MRT algorithm. In the + algorithm description, it is assumed that such links and nodes will + not be explored or used, and no more discussion is given of this + restriction. 5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance As discussed in Section 4.2, it is necessary to find ears from a node x that is already in the GADAG (known as IN_GADAG). Two different methods are used to find ears in the algorithm. The first is by going to a not IN_GADAG DFS-child and then following the chain of low-point parents until an IN_GADAG node is found. The second is by going to a not IN_GADAG neighbor and then following the chain of DFS parents until an IN_GADAG node is found. As an ear is found, the @@ -1028,47 +1055,47 @@ topological sort[Kahn_1962_topo_sort] which essentially assigns a number to a node x only after all nodes before it (e.g. with a link incoming to x) have had their numbers assigned. The only issue with the topological sort is that it works on DAGs and not ADAGs or GADAGs. To convert a GADAG to a DAG, it is necessary to remove all links that point to a root of block from within that block. That provides the necessary conversion to a DAG and then a topological sort can be done. Finally, all UNDIRECTED links are assigned a direction based - upon the partial ordering. Any UNDIRECTED links that connect to a - root of a block from within that block are assigned a direction - INCOMING to that root. The exact details of this whole process are - captured in Figure 17 + upon the total ordering. Any UNDIRECTED links that connect to a root + of a block from within that block are assigned a direction INCOMING + to that root. The exact details of this whole process are captured + in Figure 17 Set_Block_Root_Incoming_Links(topo, root, mark_or_clear) foreach node x in topo if node x is a cut-vertex or root foreach interface i of x if (i.remote_node.localroot is x) if i.UNDIRECTED i.OUTGOING = true i.remote_intf.INCOMING = true i.UNDIRECTED = false i.remote_intf.UNDIRECTED = false if i.INCOMING - if mark_or_clear is mark + if mark_or_clear is MARK if i.OUTGOING // a cut-link i.STORE_INCOMING = true i.INCOMING = false i.remote_intf.STORE_OUTGOING = true i.remote_intf.OUTGOING = false i.TEMP_UNUSABLE = true i.remote_intf.TEMP_UNUSABLE = true else i.TEMP_UNUSABLE = false i.remote_intf.TEMP_UNUSABLE = false - if i.STORE_INCOMING and (mark_or_clear is clear) + if i.STORE_INCOMING and (mark_or_clear is CLEAR) i.INCOMING = true i.STORE_INCOMING = false i.remote_intf.OUTGOING = true i.remote_intf.STORE_OUTGOING = false Run_Topological_Sort_GADAG(topo, root) Set_Block_Root_Incoming_Links(topo, root, MARK) foreach node x set x.unvisited to the count of x's incoming interfaces that aren't marked TEMP_UNUSABLE @@ -1106,32 +1133,31 @@ i.remote_intf.OUTGOING = true i.remote_intf.UNDIRECTED = false Add_Undirected_Links(topo, root) Figure 17: Assigning direction to UNDIRECTED links Proxy-nodes do not need to be added to the network graph. They cannot be transited and do not affect the MRTs that are computed. The details of how the MRT-Blue and MRT-Red next-hops are computed - and how the appropriate alternate next-hops are selected is given in - Section 5.8. + for proxy-nodes and how the appropriate alternate next-hops are + selected is given in Section 5.8. 5.6. Compute MRT next-hops As was discussed in Section 4.1, once a ADAG is found, it is straightforward to find the next-hops from any node X to the ADAG - root. However, in this algorithm, we want to reuse the common GADAG - and find not only the one pair of MRTs rooted at the GADAG root with - it, but find a pair rooted at each node. This is useful since it is - significantly faster to compute. It may also provide easier - troubleshooting of the MRT-Red and MRT-Blue. + root. However, in this algorithm, we will reuse the common GADAG and + find not only the one pair of MRTs rooted at the GADAG root with it, + but find a pair rooted at each node. This is useful since it is + significantly faster to compute. The method for computing differently rooted MRTs from the common GADAG is based on two ideas. First, if two nodes X and Y are ordered with respect to each other in the partial order, then an SPF along OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a decreasing-SPF) can be used to find the increasing and decreasing paths. Second, if two nodes X and Y aren't ordered with respect to each other in the partial order, then intermediary nodes can be used to create the paths by increasing/decreasing to the intermediary and then decreasing/increasing to reach Y. @@ -1234,40 +1260,42 @@ case for IP networks), it is enough to find which nodes are greater and less than X, and which are not ordered; this can be done by running an increasing-SPF and a decreasing-SPF rooted at X and not exploring any links from the ADAG root. ( Traversal algorithms other than SPF could safely be used instead where one traversal takes the links in their given directions and the other reverses the links' directions.) An increasing-SPF rooted at X and not exploring links from the root will find the increasing next-hops to all Y >> X. Those increasing - next-hops are X's next-hops on the MRT-Blue to reach Y. An + next-hops are X's next-hops on the MRT-Blue to reach Y. A decreasing-SPF rooted at X and not exploring links from the root will find the decreasing next-hops to all Z << X. Those decreasing next- hops are X's next-hops on the MRT-Red to reach Z. Since the root R is both greater than and less than X, after this increasing-SPF and decreasing-SPF, X's next-hops on the MRT-Blue and on the MRT-Red to reach R are known. For every node Y >> X, X's next-hops on the MRT- Red to reach Y are set to those on the MRT-Red to reach R. For every node Z << X, X's next-hops on the MRT-Blue to reach Z are set to those on the MRT-Blue to reach R. - For those nodes, which were not reached, we have the next-hops as - well. The increasing MRT-Blue next-hop for a node, which is not - ordered, is the next-hop along the decreasing MRT-Red towards R and - the decreasing MRT-Red next-hop is the next-hop along the increasing - MRT-Blue towards R. Naturally, since R is ordered with respect to all - the nodes, there will always be an increasing and a decreasing path - towards it. This algorithm does not provide the complete specific - path taken but just the appropriate next-hops to use. The identity - of G and H is not determined. + For those nodes which were not reached by either the increasing-SPF + or the decreasing-SPF, we can determine the next-hops as well. The + increasing MRT-Blue next-hop for a node which is not ordered with + respect to X is the next-hop along the decreasing MRT-Red towards R, + and the decreasing MRT-Red next-hop is the next-hop along the + increasing MRT-Blue towards R. Naturally, since R is ordered with + respect to all the nodes, there will always be an increasing and a + decreasing path towards it. This algorithm does not provide the + complete specific path taken but just the appropriate next-hops to + use. The identities of G and H are not determined by the computing + node X. The final case to considered is when the root R computes its own next-hops. Since the root R is << all other nodes, running an increasing-SPF rooted at R will reach all other nodes; the MRT-Blue next-hops are those found with this increasing-SPF. Similarly, since the root R is >> all other nodes, running a decreasing-SPF rooted at R will reach all other nodes; the MRT-Red next-hops are those found with this decreasing-SPF. E---D---| E<--D<--| @@ -1276,37 +1304,42 @@ R F C R F C | | | | ^ ^ | | | V | | A---B---| A-->B---| (a) (b) A 2-connected graph A spanning ADAG rooted at R Figure 21 - As an example consider the situation depicted in Figure 21. There - node C runs an increasing-SPF and a decreasing-SPF The increasing-SPF - reaches D, E and R and the decreasing-SPF reaches B, A and R. So - towards E the increasing next-hop is D (it was reached though D), and - the decreasing next-hop is B (since R was reached though B). Since - both D and B, A and R will compute the next hops similarly, the - packets will reach E. + As an example consider the situation depicted in Figure 21. Node C + runs an increasing-SPF and a decreasing-SPF on the ADAG. The + increasing-SPF reaches D, E and R and the decreasing-SPF reaches B, A + and R. E>>C. So towards E the MRT-Blue next-hop is D, since E was + reached on the increasing path through D. And the MRT-Red next-hop + towards E is B, since R was reached on the decreasing path through B. + Since E>>D, D will similarly compute its MRT-Blue next-hop to be E, + ensuring that a packet on MRT-Blue will use path C-D-E. B, A and R + will similarly compute the MRT-Red next-hops towards E (which is + ordered less than B, A and R), ensuring that a packet on MRT-Red will + use path C-B-A-R-E. - We have the next-hops towards F as well: since F is not ordered with - respect to C, the MRT-Blue next-hop is the decreasing one towards R - (which is B) and the MRT-Red next-hop is the increasing one towards R - (which is D). Since B is ordered with F, it will find, for its MRT- - Blue, a real increasing next-hop, so packet forwarded to B will get - to F on path C-B-F. Similarly, D will have, for its MRT-Red, a real - decreasing next-hop, and the packet will use path C-D-F. + C can determine the next-hops towards F as well. Since F is not + ordered with respect to C, the MRT-Blue next-hop is the decreasing + one towards R (which is B) and the MRT-Red next-hop is the increasing + one towards R (which is D). Since F>>B, for its MRT-Blue next-hop + towards F, B will use the real increasing next-hop towards F. So a + packet forwarded to B on MRT-Blue will get to F on path C-B-F. + Similarly, D will use the real decreasing next-hop towards F as its + MRT-Red next-hop, an packet on MRT-Red will use path C-D-F. -5.6.4. Generalizing for graph that isn't 2-connected +5.6.4. Generalizing for a graph that isn't 2-connected If a graph isn't 2-connected, then the basic approach given in Section 5.6.3 needs some extensions to determine the appropriate MRT next-hops to use for destinations outside the computing router X's blocks. In order to find a pair of maximally redundant trees in that graph we need to find a pair of RTs in each of the blocks (the root of these trees will be discussed later), and combine them. When computing the MRT next-hops from a router X, there are three basic differences: @@ -1321,22 +1354,22 @@ B. If a node is explored in the outgoing SPF so Y >> X, then X's MRT-Red next-hops to reach Y uses X's MRT-Red next-hops to reach X's local-root and if Z << X, then X's MRT-Blue next- hops to reach Z uses X's MRT-Blue next-hops to reach X's local-root. C. If a node W in a common block with X was not reached in the increasing-SPF or decreasing-SPF, then W is unordered with respect to X. X's MRT-Blue next-hops to W are X's decreasing - aka MRT-Red next-hops to X's local-root. X's MRT-Red next- - hops to W are X's increasing aka Blue MRT next-hops to X's + (aka MRT-Red) next-hops to X's local-root. X's MRT-Red next- + hops to W are X's increasing (aka MRT-Blue) next-hops to X's local-root. 3. For nodes in different blocks, the next-hops must be inherited via the relevant cut-vertex. These are all captured in the detailed algorithm given in Section 5.6.5. 5.6.5. Complete Algorithm to Compute MRT Next-Hops @@ -1555,22 +1588,22 @@ case (iii) holds true, which means that selecting the Blue next-hop is safe. Similarly, if F.topo_order>S, we - should use the Blue next-hop. + then decreasing; this path must avoid using F. Similarly, if F>>S, + we should use the Blue next-hop. Additionally, the cases where either F or D is ordered both higher and lower must be considered; this can happen when one is a block- root or its order_proxy is. If D is both higher and lower than S, then the MRT to use is the one that avoids F so if F is higher, then the MRT-Red should be used and if F is lower, then the MRT-Blue should be used; F and S must be ordered because they are neighbors. If F is both higher and lower, then if D is lower, using the MRT-Red to decrease reaches D and if D is higher, using the Blue MRT to increase reaches D; if D is unordered compared to S, then the @@ -1579,22 +1612,22 @@ In the case where F< F, then use the MRT-Blue (decrease to avoid that link and then increase). If the link is directed S <- F, then use the MRT-Red (increase to avoid that link and then decrease). If the link is S <--> F, then the link must be a cut-link and there is no node-protecting alternate. If there are multiple links between S and F, then they can protect against each other; of course, in this situation, they are probably already ECMP. - Finally, there is the case where D is also F. In this case, only link - protection is possible. The MRT that doesn't use the indicated + Finally, there is the case where D is also F. In this case, only + link protection is possible. The MRT that doesn't use the indicated primary next-hop is used. If both MRTs use the primary next-hop, then the primary next-hop must be a cut-link so either MRT could be used but the set of MRT next-hops must be pruned to avoid that primary next-hop. To indicate this case, Select_Alternates returns AVOID_LINK_ON_BLUE. As an example, consider the ADAG depicted in Figure 24 and first suppose that G is the source, D is the destination and H is the failed next-hop. Since D>>G, we need to compare H.topo_order and D.topo_order. Since D.topo_order>H.topo_order, D must be not smaller @@ -1707,65 +1741,61 @@ return P.blue_next_hops = R.red_next_hops P.red_next_hops = R.blue_next_hops return After finding the the red and the blue next-hops, it is necessary to know which one of these to use in the case of failure. This can be done by Select_Alternates_Inner(). In order to use Select_Alternates_Internal(), we need to know if P is greater, less or unordered with S, and P.topo_order. P.lower = B.lower, P.higher = - A.higher, and any value is OK for P.topo_order, until + A.higher, and any value is OK for P.topo_order, as long as A.topo_order<=P.topo_order<=B.topo_order and P.topo_order is not equal to the topo_order of the failed node. So for simplicity let P.topo_order=A.topo_order when the next-hop is not A, and P.topo_order=B.topo_order otherwise. This gives the following pseudo-code: Select_Alternates_Proxy_Node(S, P, F, primary_intf) if (F is not P.neighbor_A) return Select_Alternates_Internal(S, P, F, primary_intf, P.neighbor_B.lower, P.neighbor_A.higher, P.neighbor_A.topo_order) else return Select_Alternates_Internal(S, P, F, primary_intf, P.neighbor_B.lower, P.neighbor_A.higher, P.neighbor_B.topo_order) Figure 25 -6. MRT Lowpoint Algorithm: Complete Specification +6. MRT Lowpoint Algorithm: Next-hop conformance This specification defines the MRT Lowpoint Algorithm, which include the construction of a common GADAG and the computation of MRT-Red and MRT-Blue next-hops to each node in the graph. An implementation MAY select any subset of next-hops for MRT-Red and MRT-Blue that respect the available nodes that are described in Section 5.6 for each of the MRT-Red and MRT-Blue and the selected next-hops are further along in the interval of allowed nodes towards the destination. - For example, the MRT-Blue next-hops used when the destination Y >> S, + For example, the MRT-Blue next-hops used when the destination Y >> X, the computing router, MUST be one or more nodes, T, whose topo_order is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y is T. Similarly, the MRT-Red next-hops MUST be have a topo_order in the interval [R-small.topo_order, X.topo_order] or [Y.topo_order, R-big.topo_order]. Implementations SHOULD implement the Select_Alternates() function to pick an MRT-FRR alternate. - In a future version, this section will include pseudo-code describing - the full code path through the pseudo-code given earlier in the - draft. - 7. Algorithm Alternatives and Evaluation This specification defines the MRT Lowpoint Algorithm, which is one option among several possible MRT algorithms. Other alternatives are described in the appendices. In addition, it is possible to calculate Destination-Rooted GADAG, where for each destination, a GADAG rooted at that destination is computed. Then a router can compute the blue MRT and red MRT next- hops to that destination. Building GADAGs per destination is @@ -2204,107 +2234,118 @@ | T219(avg primary hops=7.7) | | | | | | | | | | | MRT_HYBRID ( 0 percentile) | 20| 16| 13| 10| 7| 5| 5| 5| 3| | MRT_SPF ( 0 percentile) | 31| 23| 19| 12| 7| 4| 2| 1| | | MRT_LOWPOINT ( 0 percentile) | 19| 14| 15| 12| 10| 8| 7| 6| 10| | MRT_LOWPOINT (25 percentile) | 19| 14| 15| 13| 12| 10| 6| 5| 7| | MRT_LOWPOINT (50 percentile) | 19| 14| 14| 12| 11| 8| 6| 6| 10| +------------------------------+---+---+---+---+---+---+---+---+----+ Figure 32 -8. Algorithm Work to Be Done +8. Implementation Status + + [RFC Editor: please remove this section prior to publication.] + + Please see [I-D.ietf-rtgwg-mrt-frr-architecture] for details on + implementation status. + +9. Algorithm Work to Be Done Broadcast Interfaces: The algorithm assumes that broadcast interfaces are already represented as pseudo-nodes in the network graph. Given maximal redundancy, one of the MRT will try to avoid both the pseudo-node and the next hop. The exact rules need to be fully specified. -9. IANA Considerations +10. Acknowledgements - This doument includes no request to IANA. + The authors would like to thank Shraddha Hegde for her suggestions + and review. -10. Security Considerations +11. IANA Considerations + + This document includes no request to IANA. + +12. Security Considerations This architecture is not currently believed to introduce new security concerns. -11. References +13. References -11.1. Normative References +13.1. Normative References [I-D.ietf-rtgwg-mrt-frr-architecture] - Atlas, A., Kebler, R., Envedi, G., Csaszar, A., Tantsura, - J., Konstantynowicz, M., and R. White, "An Architecture - for IP/LDP Fast-Reroute Using Maximally Redundant Trees", - draft-ietf-rtgwg-mrt-frr-architecture-03 (work in - progress), July 2013. + Atlas, A., Kebler, R., Bowers, C., Enyedi, G., Csaszar, + A., Tantsura, J., Konstantynowicz, M., and R. White, "An + Architecture for IP/LDP Fast-Reroute Using Maximally + Redundant Trees", draft-rtgwg-mrt-frr-architecture-04 + (work in progress), July 2014. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. -11.2. Informative References +13.2. Informative References [EnyediThesis] Enyedi, G., "Novel Algorithms for IP Fast Reroute", Department of Telecommunications and Media Informatics, Budapest University of Technology and Economics Ph.D. - Thesis, February 2011, . [I-D.atlas-mpls-ldp-mrt] - Atlas, A., Tiruveedhula, K., Tantsura, J., and I. + Atlas, A., Tiruveedhula, K., Tantsura, J., and IJ. Wijnands, "LDP Extensions to Support Maximally Redundant - Trees", draft-atlas-mpls-ldp-mrt-00 (work in progress), - July 2013. + Trees", draft-atlas-mpls-ldp-mrt-01 (work in progress), + July 2014. [I-D.atlas-ospf-mrt] - Atlas, A., Hegde, S., cbowers@juniper.net, c., and J. - Tantsura, "OSPF Extensions to Support Maximally Redundant - Trees", draft-atlas-ospf-mrt-01 (work in progress), - October 2013. + Atlas, A., Hegde, S., Bowers, C., and J. Tantsura, "OSPF + Extensions to Support Maximally Redundant Trees", draft- + atlas-ospf-mrt-02 (work in progress), July 2014. [I-D.ietf-rtgwg-ipfrr-notvia-addresses] Bryant, S., Previdi, S., and M. Shand, "A Framework for IP and MPLS Fast Reroute Using Not-via Addresses", draft- ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress), May 2013. [I-D.ietf-rtgwg-lfa-manageability] Litkowski, S., Decraene, B., Filsfils, C., Raza, K., Horneffer, M., and p. psarkar@juniper.net, "Operational management of Loop Free Alternates", draft-ietf-rtgwg-lfa- manageability-03 (work in progress), February 2014. [I-D.ietf-rtgwg-remote-lfa] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and S. - Ning, "Remote LFA FRR", draft-ietf-rtgwg-remote-lfa-04 - (work in progress), November 2013. + Ning, "Remote LFA FRR", draft-ietf-rtgwg-remote-lfa-06 + (work in progress), May 2014. [I-D.li-isis-mrt] - Li, Z., Wu, N., Zhao, Q., Atlas, A., cbowers@juniper.net, - c., and J. Tantsura, "Intermediate System to Intermediate - System (IS-IS) Extensions for Maximally Redundant Trees - (MRT)", draft-li-isis-mrt-00 (work in progress), October - 2013. + Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J. + Tantsura, "Intermediate System to Intermediate System (IS- + IS) Extensions for Maximally Redundant Trees(MRT)", draft- + li-isis-mrt-01 (work in progress), July 2014. [Kahn_1962_topo_sort] Kahn, A., "Topological sorting of large networks", Communications of the ACM, Volume 5, Issue 11 , Nov 1962, . [LFARevisited] Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP Fast ReRoute: Loop Free Alternates Revisited", Proceedings - of IEEE INFOCOM , 2011, . + of IEEE INFOCOM , 2011, + . [LightweightNotVia] Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP Fast ReRoute: Lightweight Not-Via without Additional Addresses", Proceedings of IEEE INFOCOM , 2009, . [MRTLinear] Enyedi, G., Retvari, G., and A. Csaszar, "On Finding Maximally Redundant Trees in Strictly Linear Time", IEEE @@ -2406,22 +2446,22 @@ Clear TEMP_UNUSABLE from all interfaces between cand_intf.remote_node and cand_intf.local_node Clear TEMP_UNUSABLE from cand_intf.local_node return end_ear Figure 33: Modified SPF for GADAG computation Assume that an ear is found by going from y to x and then running an SPF that terminates by minimizing z (e.g. y<->x...q<->z). Now it is necessary to determine the direction of the ear; if y << z, then the - path should be y->x...q->z but if y >> z, then the path should be - y<-x...q<-z. In Section 5.4, the same problem was handled by finding + path should be y->x...q->z but if y >> z, then the path should be y<- + x...q<-z. In Section 5.4, the same problem was handled by finding all ears that started at a node before looking at ears starting at nodes higher in the partial order. In this algorithm, using that approach could mean that new ears aren't added in order of their total cost since all ears connected to a node would need to be found before additional nodes could be found. The alternative is to track the order relationship of each node with respect to every other node. This can be accomplished by maintaining two sets of nodes at each node. The first set, Higher_Nodes, contains all nodes that are known to be ordered above the node. The @@ -2482,24 +2522,23 @@ maintained of interfaces that could be explored from the IN_GADAG nodes. The interfaces are ordered by their characteristics of metric, local loopback address, remote loopback address, and ifindex, as in the algorithm previously described in Figure 14. The algorithm ignores interfaces picked from the ordered tree that belong to the block root if the block in which the interface is present already has an ear that has been computed. This is necessary since we allow at most one incoming interface to a block root in each block. This requirement stems from the way next-hops are computed as - will be seen in Section 5.6. After any ear gets computed, we - traverse the newly added nodes to the GADAG and insert interfaces - whose far end is not yet on the GADAG to the ordered tree for later - processing. + was seen in Section 5.6. After any ear gets computed, we traverse + the newly added nodes to the GADAG and insert interfaces whose far + end is not yet on the GADAG to the ordered tree for later processing. Finally, cut-links are a special case because there is no point in doing an SPF on a block of 2 nodes. The algorithm identifies cut- links simply as links where both ends of the link are cut-vertices. Cut-links can simply be added to the GADAG with both OUTGOING and INCOMING specified on their interfaces. add_eligible_interfaces_of_node(ordered_intfs_tree,node) for each interface of node if intf.remote_node.IN_GADAG is false @@ -2551,28 +2590,29 @@ add_eligible_interfaces_of_node( ordered_intfs_tree, y.local_node) y = y.local_node.spf_prev_intf Figure 35: SPF-based GADAG algorithm Appendix B. Option 3: Computing GADAG using a hybrid method In this option, the idea is to combine the salient features of the - above two options. To this end, we process nodes as they get added - to the GADAG just like in the lowpoint inheritance by maintaining a - stack of nodes. This ensures that we do not need to maintain lower - and higher sets at each node to ascertain ear directions since the - ears will always be directed from the node being processed towards - the end of the ear. To compute the ear however, we resort to an SPF - to have the possibility of better ears (path lentghs) thus giving - more flexibility than the restricted use of lowpoint/dfs parents. + lowpoint inheritance and SPF methods. To this end, we process nodes + as they get added to the GADAG just like in the lowpoint inheritance + by maintaining a stack of nodes. This ensures that we do not need to + maintain lower and higher sets at each node to ascertain ear + directions since the ears will always be directed from the node being + processed towards the end of the ear. To compute the ear however, we + resort to an SPF to have the possibility of better ears (path + lentghs) thus giving more flexibility than the restricted use of + lowpoint/dfs parents. Regarding ears involving a block root, unlike the SPF method which ignored interfaces of the block root after the first ear, in the hybrid method we would have to process all interfaces of the block root before moving on to other nodes in the block since the direction of an ear is pre-determined. Thus, whenever the block already has an ear computed, and we are processing an interface of the block root, we mark the block root as unusable before the SPF run that computes the ear. This ensures that the SPF terminates at some node other than the block-root. This in turn guarantees that the block-root has