--- 1/draft-ietf-rtgwg-mrt-frr-algorithm-06.txt 2015-12-21 07:15:26.000772724 -0800 +++ 2/draft-ietf-rtgwg-mrt-frr-algorithm-07.txt 2015-12-21 07:15:26.252778820 -0800 @@ -1,50 +1,50 @@ -Routing Area Working Group G. Enyedi, Ed. +Routing Area Working Group G. Enyedi Internet-Draft A. Csaszar Intended status: Standards Track Ericsson -Expires: April 17, 2016 A. Atlas, Ed. +Expires: June 23, 2016 A. Atlas C. Bowers Juniper Networks A. Gopalan University of Arizona - October 15, 2015 + December 21, 2015 Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- Reroute - draft-ietf-rtgwg-mrt-frr-algorithm-06 + draft-ietf-rtgwg-mrt-frr-algorithm-07 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. + A solution for IP and LDP Fast-Reroute using Maximally Redundant + Trees is presented in draft-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. Status of This Memo 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 April 17, 2016. + This Internet-Draft will expire on June 23, 2016. Copyright Notice 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 @@ -76,39 +76,43 @@ 5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 30 5.7.1. MRT next-hops to all nodes ordered with respect to the computing node . . . . . . . . . . . . . . . . . 30 5.7.2. MRT next-hops to all nodes not ordered with respect to the computing node . . . . . . . . . . . . . . . . 31 5.7.3. Computing Redundant Tree next-hops in a 2-connected Graph . . . . . . . . . . . . . . . . . . . . . . . . 32 5.7.4. Generalizing for a graph that isn't 2-connected . . . 34 5.7.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 35 5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 37 - 5.9. Finding MRT Next-Hops for Proxy-Nodes . . . . . . . . . . 44 - 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 58 - 7. Broadcast interfaces . . . . . . . . . . . . . . . . . . . . 58 - 7.1. Computing MRT next-hops on broadcast networks . . . . . . 59 + 5.9. Named Proxy-Nodes . . . . . . . . . . . . . . . . . . . . 44 + 5.9.1. Determining Proxy-Node Attachment Routers . . . . . . 44 + 5.9.2. Computing if an Island Neighbor (IN) is loop-free . . 45 + 5.9.3. Computing MRT Next-Hops for Proxy-Nodes . . . . . . . 47 + 5.9.4. Computing MRT Alternates for Proxy-Nodes . . . . . . 53 + 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 61 + 7. Broadcast interfaces . . . . . . . . . . . . . . . . . . . . 61 + 7.1. Computing MRT next-hops on broadcast networks . . . . . . 62 7.2. Using MRT next-hops as alternates in the event of - failures on broadcast networks . . . . . . . . . . . . . 60 - 8. Python Implementation of MRT Lowpoint Algorithm . . . . . . . 61 - 9. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 102 - 9.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 102 - 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 112 - 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 112 - 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 112 - 13. Security Considerations . . . . . . . . . . . . . . . . . . . 112 - 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 112 - 14.1. Normative References . . . . . . . . . . . . . . . . . . 112 - 14.2. Informative References . . . . . . . . . . . . . . . . . 112 - Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 115 - Appendix B. Option 3: Computing GADAG using a hybrid method . . 120 - Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 122 + failures on broadcast networks . . . . . . . . . . . . . 63 + 8. Python Implementation of MRT Lowpoint Algorithm . . . . . . . 64 + 9. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 104 + 9.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 105 + 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 115 + 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 115 + 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 115 + 13. Security Considerations . . . . . . . . . . . . . . . . . . . 115 + 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 115 + 14.1. Normative References . . . . . . . . . . . . . . . . . . 115 + 14.2. Informative References . . . . . . . . . . . . . . . . . 115 + Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 117 + Appendix B. Option 3: Computing GADAG using a hybrid method . . 122 + Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 124 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 alternate to use. This document defines how to compute these three things for use in MRT-FRR and describes the algorithm design decisions and rationale. The algorithm is based on those presented @@ -130,21 +134,21 @@ Red for forwarding received traffic on the MRT-Red. What alternate next-hops a point-of-local-repair (PLR) selects need not be consistent - but loops must be prevented. To reduce congestion, it is possible for multiple alternate next-hops to be selected; in the context of MRT alternates, each of those alternate next-hops would be equal-cost paths. This document defines an algorithm for selecting an appropriate MRT alternate for consideration. Other alternates, e.g. LFAs that are - downstream paths, may be prefered when available and that policy- + downstream paths, may be preferred when available and that policy- based alternate selection process[I-D.ietf-rtgwg-lfa-manageability] is not captured in this document. [E]---[D]---| [E]<--[D]<--| [E]-->[D] | | | | ^ | | | | | V | | V [R] [F] [C] [R] [F] [C] [R] [F] [C] | | | ^ ^ | | | | | | | V | [A]---[B]---| [A]-->[B] [A]---[B]<--| @@ -182,21 +186,21 @@ [A]-->[B]---| |---[H] [A]<--[B]<--| [H] (b) MRT-Blue towards R (c) MRT-Red towards R Figure 2 2. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this - document are to be interpreted as described in [RFC2119] + document are to be interpreted as described in [RFC2119]. 3. Terminology and Definitions network graph: A graph that reflects the network topology where all links connect exactly two nodes and broadcast links have been transformed into a pseudonode representation (e.g. in OSPF, viewing a Network LSA as representing a pseudonode). Redundant Trees (RT): A pair of trees where the path from any node X to the root R on the first tree is node-disjoint with the path @@ -1961,23 +1965,23 @@ additional property that incoming links to a localroot come from only one other node in the same block. This is a result of the method of construction. This additional property guarantees that the red path from S to D will never pass through the localroot of S. (That would require the localroot to play the role of L, the first node in the path ordered higher than D, which would in turn require the localroot to have two incoming links in the GADAG, which cannot happen.) Therefore it is safe to use the red path to avoid F with these specially constructed GADAGs. - As an example of how to Select_Alternates_Internal() operates, - consider the ADAG depicted in Figure 26 and first suppose that G is - the source, D is the destination and H is the failed next-hop. Since + As an example of how Select_Alternates_Internal() operates, consider + the ADAG depicted in Figure 26 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 either higher than H or unordered with respect to H, so we should select the decreasing path towards the root. If, however, the destination were instead J, we must find that H.topo_order>J.topo_order, so we must choose the increasing Blue next-hop to J, which is I. In the case, when instead the destination is C, we find that we need to first decrease to avoid using H, so the Blue, first decreasing then increasing, path is selected. @@ -1987,41 +1991,151 @@ [R] [C] [G]->[I] | ^ ^ ^ V | | | [A]->[B]->[F]---| (a)ADAG rooted at R for a 2-connected graph Figure 26 -5.9. Finding MRT Next-Hops for Proxy-Nodes +5.9. Named Proxy-Nodes As discussed in Section 11.2 of [I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT- - Blue and MRT-Red next-hops and MRT-FRR alternates for a named proxy- + Blue and MRT-Red next-hops and MRT-FRR alternates for named proxy- nodes. An example use case is for a router that is not part of that local MRT Island, when there is only partial MRT support in the domain. - The proxy-node is connected to at most two nodes in the GADAG. - Section 11.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] defines how the - proxy-node attachment routers MUST be determined. The degenerate - case where the proxy-node is attached to only one node in the GADAG - is trivial as all needed information can be derived from that proxy +5.9.1. Determining Proxy-Node Attachment Routers + + Section 11.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] discusses + general considerations for determining the two proxy-node attachment + routers for a given proxy-node, corresponding to a prefix. A router + in the MRT Island that advertises the prefix is a candidate for being + a proxy-node attachment router, with the associated named-proxy-cost + equal to the advertised cost to the prefix. + + An Island Border Router (IBR) is a router in the MRT Island that is + connected to an Island Neighbor(IN), which is a router not in the MRT + Island but in the same area/level. An (IBR,IN) pair is a candidate + for being a proxy-node attachment router, if the shortest path from + the IN to the prefix does not enter the MRT Island. A method for + identifying such loop-free Island Neighbors(LFINs) is given below. + The named-proxy-cost assigned to each (IBR, IN) pair is cost(IBR, IN) + + D_opt(IN, prefix). + + From the set of prefix-advertising routers and the set of IBRs with + at least one LFIN, the two routers with the lowest named-proxy-cost + are selected. Ties are broken based upon the lowest Router ID. For + ease of discussion, the two selected routers will be referred to as + proxy-node attachment routers. + +5.9.2. Computing if an Island Neighbor (IN) is loop-free + + As discussed above, the Island Neighbor needs to be loop-free with + respect to the whole MRT Island for the destination. This can be + accomplished by running the usual SPF algorithm while keeping track + of which shortest paths have passed through the MRT island. Pseudo- + code for this is shown in Figure 27. The Island_Marking_SPF() is run + for each IN that needs to be evaluated for the loop-free condition, + with the IN as the spf_root. Whether or not an IN is loop-free with + respect to the MRT island can then be determined by evaluating + node.PATH_HITS_ISLAND for each destination of interest. + + Island_Marking_SPF(spf_root) + Initialize spf_heap to empty + Initialize nodes' spf_metric to infinity and next_hops to empty + and PATH_HITS_ISLAND to false + spf_root.spf_metric = 0 + insert(spf_heap, spf_root) + while (spf_heap is not empty) + min_node = remove_lowest(spf_heap) + foreach interface intf of min_node + path_metric = min_node.spf_metric + intf.metric + if path_metric < intf.remote_node.spf_metric + intf.remote_node.spf_metric = path_metric + if min_node is spf_root + intf.remote_node.next_hops = make_list(intf) + else + intf.remote_node.next_hops = min_node.next_hops + if intf.remote_node.IN_MRT_ISLAND + intf.remote_node.PATH_HITS_ISLAND = true + else + intf.remote_node.PATH_HITS_ISLAND = + min_node.PATH_HITS_ISLAND + insert_or_update(spf_heap, intf.remote_node) + else if path_metric == intf.remote_node.spf_metric + if min_node is spf_root + add_to_list(intf.remote_node.next_hops, intf) + else + add_list_to_list(intf.remote_node.next_hops, + min_node.next_hops) + if intf.remote_node.IN_MRT_ISLAND + intf.remote_node.PATH_HITS_ISLAND = true + else + intf.remote_node.PATH_HITS_ISLAND = + min_node.PATH_HITS_ISLAND + + Figure 27: Island_Marking_SPF for determining if an Island Neighbor + is loop-free + + It is also possible that a given prefix is originated by a + combination of non-island routers and island routers. The results of + the Island_Marking_SPF computation can be used to determine if the + shortest path from an IN to reach that prefix hits the MRT island. + The shortest path for the IN to reach prefix P is determined by the + total cost to reach prefix P, which is the sum of the cost for the IN + to reach a prefix-advertising node and the cost with which that node + advertises the prefix. The path with the minimum total cost to + prefix P is chosen. If the prefix-advertising node for that minimum + total cost path has PATH_HITS_ISLAND set to True, then the IN is not + loop-free with respect to the MRT Island for reaching prefix P. If + there multiple minimum total cost paths to reach prefix P, then all + of the prefix-advertising routers involved in the minimum total cost + paths MUST have PATH_HITS_ISLAND set to False for the IN to be + considered loop-free to reach P. + + Note that there are other computations that could be used to + determine if paths from a given IN _might_ pass through the MRT + Island for a given prefix or destination. For example, a previous + version of this draft specified running the SPF algorithm on modified + topology which treats the MRT island as a single node (with intra- + island links set to zero cost) in order to provide input to + computations to determine if the path from IN to non-island + destination hits the MRT island in this modified topology. This + computation is enough to guarantee that a path will not hit the MRT + island in the original topology. However, it is possible that a path + which is disqualified for hitting the MRT island in the modified + topology will not actually hit the MRT Island in the original + topology. The algorithm described in Island_Marking_SPF() above does + not modify the original topology, and will only disqualify a path if + the actual path does in fact hit the MRT island. + + Since all routers need to come to the same conclusion about which + routers qualify as LFINs, this specification requires that all + routers computing LFINs MUST use an algorithm whose result is + identical to that of the Island_Marking_SPF() in Figure 27. + +5.9.3. Computing MRT Next-Hops for Proxy-Nodes + + Determining the MRT next-hops for a proxy-node in the degenerate case + where the proxy-node is attached to only one node in the GADAG is + trivial, as all needed information can be derived from that proxy node attachment router. If there are multiple interfaces connecting the proxy node to the single proxy node attachment router, then some canbe assigned to MRT-Red and others to MRT_Blue. Now, consider the proxy-node P that is attached to two proxy-node attachment routers. The pseudo-code for Select_Proxy_Node_NHs(P,S) - in Figure 27 specifies how a computing-router S MUST compute the MRT + in Figure 28 specifies how a computing-router S MUST compute the MRT red and blue next-hops to reach proxy-node P. The proxy-node attachment router with the lower value of mrt_node_id (as defined in Figure 15) is assigned to X, and the other proxy-node attachment router is assigned to Y. We will be using the relative order of X,Y, and S in the partial order defined by the GADAG to determine the MRT red and blue next-hops to reach P, so we also define A and B as the order proxies for X and Y, respectively, with respect to S. The order proxies for all nodes with respect to S were already computed in Compute_MRT_NextHops(). @@ -2031,150 +2145,151 @@ Y = P.pnar2.node else: X = P.pnar2.node Y = P.pnar1.node P.pnar_X = X P.pnar_Y = Y A = X.order_proxy B = Y.order_proxy if (A is S.localroot and B is S.localroot): - #print("1.0") + // case 1.0 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops) return if (A is S.localroot and B is not S.localroot): - #print("2.0") + // case 2.0 if B.LOWER: - #print("2.1") + // case 2.1 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops) return if B.HIGHER: - #print("2.2") + // case 2.2 Copy_List_Items(P.blue_next_hops, X.red_next_hops) Copy_List_Items(P.red_next_hops, Y.blue_next_hops) return else: - #print("2.3") + // case 2.3 Copy_List_Items(P.blue_next_hops, X.red_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops) return if (A is not S.localroot and B is S.localroot): - #print("3.0") + // case 3.0 if A.LOWER: - #print("3.1") + // case 3.1 Copy_List_Items(P.blue_next_hops, X.red_next_hops) Copy_List_Items(P.red_next_hops, Y.blue_next_hops) return if A.HIGHER: - #print("3.2") + // case 3.2 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops) return + else: - #print("3.3") + // case 3.3 Copy_List_Items(P.blue_next_hops, X.red_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops) return if (A is not S.localroot and B is not S.localroot): - #print("4.0") + // case 4.0 if (S is A.localroot or S is B.localroot): - #print("4.05") + // case 4.05 if A.topo_order < B.topo_order: - #print("4.05.1") + // case 4.05.1 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops) return else: - #print("4.05.2") + // case 4.05.2 Copy_List_Items(P.blue_next_hops, X.red_next_hops) Copy_List_Items(P.red_next_hops, Y.blue_next_hops) return if A.LOWER: - #print("4.1") + // case 4.1 if B.HIGHER: - #print("4.1.1") + // case 4.1.1 Copy_List_Items(P.blue_next_hops, X.red_next_hops) Copy_List_Items(P.red_next_hops, Y.blue_next_hops) return if B.LOWER: - #print("4.1.2") + // case 4.1.2 if A.topo_order < B.topo_order: - #print("4.1.2.1") + // case 4.1.2.1 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops) return else: - #print("4.1.2.2") + // case 4.1.2.2 Copy_List_Items(P.blue_next_hops, X.red_next_hops) Copy_List_Items(P.red_next_hops, Y.blue_next_hops) return else: - #print("4.1.3") + // case 4.1.3 Copy_List_Items(P.blue_next_hops, X.red_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops) return if A.HIGHER: - - #print("4.2") + // case 4.2 if B.HIGHER: - #print("4.2.1") + // case 4.2.1 if A.topo_order < B.topo_order: - #print("4.2.1.1") + // case 4.2.1.1 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops) return else: - #print("4.2.1.2") + // case 4.2.1.2 Copy_List_Items(P.blue_next_hops, X.red_next_hops) Copy_List_Items(P.red_next_hops, Y.blue_next_hops) return if B.LOWER: - #print("4.2.2") + // case 4.2.2 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops) return else: - #print("4.2.3") + // case 4.2.3 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) Copy_List_Items(P.red_next_hops, Y.blue_next_hops) return else: - #print("4.3") + // case 4.3 if B.LOWER: - #print("4.3.1") + // case 4.3.1 Copy_List_Items(P.blue_next_hops, X.red_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops) return if B.HIGHER: - #print("4.3.2") + // case 4.3.2 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) Copy_List_Items(P.red_next_hops, Y.blue_next_hops) return else: - #print("4.3.3") + // case 4.3.3 if A.topo_order < B.topo_order: - #print("4.3.3.1") + // case 4.3.3.1 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops) return else: - #print("4.3.3.2") + // case 4.3.3.2 Copy_List_Items(P.blue_next_hops, X.red_next_hops) Copy_List_Items(P.red_next_hops, Y.blue_next_hops) return assert(False) - Figure 27: Select_Proxy_Node_NHs() + + Figure 28: Select_Proxy_Node_NHs() It is useful to understand up front that the blue next-hops to reach proxy-node P produced by Select_Proxy_Node_NHs() will always be the next-hops that reach proxy-node attachment router X, while the red next-hops to reach proxy-node P will always be the next-hops that reach proxy-node attachment router Y. This is different from the red and blue next-hops produced by Compute_MRT_NextHops() where, for example, blue next-hops to a destination that is ordered with respect to the source will always correspond to an INCREASING next-hop on the GADAG. The exact choice of which next-hops chosen by @@ -2289,24 +2404,26 @@ algorithm in this document are not arbitrary GADAGs. They have the additional property that incoming links to a localroot come from only one other node in the same block. This is a result of the method of construction. This additional property guarantees that localroot A will never play the role of L in the red path to Y, since L must have at least two incoming links from different nodes in the same block in the GADAG. This in turn allows Select_Proxy_Node_NHs() to choose the red path to Y and the red path to X as the disjoint MRT paths to reach P. +5.9.4. Computing MRT Alternates for Proxy-Nodes + After finding the red and the blue next-hops for a given proxy-node P, it is necessary to know which one of these to use in the case of failure. This can be done by Select_Alternates_Proxy_Node(), as - shown in the pseudo-code in Figure 28. + shown in the pseudo-code in Figure 29. def Select_Alternates_Proxy_Node(P,F,primary_intf): S = primary_intf.local_node X = P.pnar_X Y = P.pnar_Y A = X.order_proxy B = Y.order_proxy if F is A and F is B: return 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y' if F is A: @@ -2332,239 +2449,236 @@ if (alt_to_X == 'USE_RED_OR_BLUE' and alt_to_Y == 'USE_RED_OR_BLUE'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_RED_OR_BLUE': return 'USE_BLUE' if alt_to_Y == 'USE_RED_OR_BLUE': return 'USE_RED' if (A is S.localroot and B is S.localroot): - #print("1.0") + // case 1.0 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_BLUE': return 'USE_BLUE' if alt_to_Y == 'USE_RED': return 'USE_RED' assert(False) if (A is S.localroot and B is not S.localroot): - #print("2.0") + // case 2.0 if B.LOWER: - #print("2.1") + // case 2.1 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_BLUE': return 'USE_BLUE' if alt_to_Y == 'USE_RED': return 'USE_RED' assert(False) - if B.HIGHER: - #print("2.2") + + // case 2.2 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_RED': return 'USE_BLUE' if alt_to_Y == 'USE_BLUE': return 'USE_RED' assert(False) else: - #print("2.3") + // case 2.3 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_RED': return 'USE_BLUE' if alt_to_Y == 'USE_RED': return 'USE_RED' assert(False) if (A is not S.localroot and B is S.localroot): - #print("3.0") + // case 3.0 if A.LOWER: - #print("3.1") + // case 3.1 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_RED': return 'USE_BLUE' if alt_to_Y == 'USE_BLUE': return 'USE_RED' assert(False) if A.HIGHER: - #print("3.2") + // case 3.2 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_BLUE': return 'USE_BLUE' if alt_to_Y == 'USE_RED': return 'USE_RED' assert(False) else: - #print("3.3") + // case 3.3 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_RED': return 'USE_BLUE' if alt_to_Y == 'USE_RED': return 'USE_RED' assert(False) - if (A is not S.localroot and B is not S.localroot): - #print("4.0") + // case 4.0 if (S is A.localroot or S is B.localroot): - #print("4.05") + // case 4.05 if A.topo_order < B.topo_order: - #print("4.05.1") + // case 4.05.1 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_BLUE': return 'USE_BLUE' if alt_to_Y == 'USE_RED': return 'USE_RED' assert(False) else: - #print("4.05.2") + // case 4.05.2 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_RED': return 'USE_BLUE' if alt_to_Y == 'USE_BLUE': return 'USE_RED' assert(False) if A.LOWER: - #print("4.1") + // case 4.1 if B.HIGHER: - #print("4.1.1") + // case 4.1.1 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_RED': return 'USE_BLUE' if alt_to_Y == 'USE_BLUE': return 'USE_RED' assert(False) if B.LOWER: - #print("4.1.2") + // case 4.1.2 if A.topo_order < B.topo_order: - #print("4.1.2.1") + // case 4.1.2.1 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_BLUE': return 'USE_BLUE' if alt_to_Y == 'USE_RED': return 'USE_RED' assert(False) else: - #print("4.1.2.2") + // case 4.1.2.2 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_RED': return 'USE_BLUE' if alt_to_Y == 'USE_BLUE': return 'USE_RED' assert(False) else: - #print("4.1.3") + // case 4.1.3 if (F.LOWER and not F.HIGHER and F.topo_order > A.topo_order): - #print("4.1.3.1") + // case 4.1.3.1 return 'USE_RED' else: - #print("4.1.3.2") + // case 4.1.3.2 return 'USE_BLUE' if A.HIGHER: - #print("4.2") + // case 4.2 if B.HIGHER: - #print("4.2.1") + // case 4.2.1 if A.topo_order < B.topo_order: - #print("4.2.1.1") + // case 4.2.1.1 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_BLUE': return 'USE_BLUE' if alt_to_Y == 'USE_RED': return 'USE_RED' assert(False) else: - #print("4.2.1.2") + // case 4.2.1.2 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_RED': return 'USE_BLUE' if alt_to_Y == 'USE_BLUE': return 'USE_RED' assert(False) if B.LOWER: - #print("4.2.2") + // case 4.2.2 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_BLUE': return 'USE_BLUE' - if alt_to_Y == 'USE_RED': + return 'USE_RED' assert(False) else: - #print("4.2.3") + // case 4.2.3 if (F.HIGHER and not F.LOWER and F.topo_order < A.topo_order): return 'USE_RED' else: return 'USE_BLUE' else: - #print("4.3") + // case 4.3 if B.LOWER: - #print("4.3.1") + // case 4.3.1 if (F.LOWER and not F.HIGHER and F.topo_order > B.topo_order): return 'USE_BLUE' else: return 'USE_RED' if B.HIGHER: - #print("4.3.2") + // case 4.3.2 if (F.HIGHER and not F.LOWER and F.topo_order < B.topo_order): return 'USE_BLUE' else: return 'USE_RED' else: - #print("4.3.3") + // case 4.3.3 if A.topo_order < B.topo_order: - #print("4.3.3.1") + // case 4.3.3.1 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_BLUE': return 'USE_BLUE' if alt_to_Y == 'USE_RED': return 'USE_RED' assert(False) else: - #print("4.3.3.2") + // case 4.3.3.2 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): return 'USE_RED_OR_BLUE' if alt_to_X == 'USE_RED': return 'USE_BLUE' if alt_to_Y == 'USE_BLUE': return 'USE_RED' assert(False) - assert(False) - - Figure 28: Select_Alternates_Proxy_Node() + Figure 29: Select_Alternates_Proxy_Node() Select_Alternates_Proxy_Node(P,F,primary_intf) determines whether it is safe to use the blue path to P (which goes through X), the red path to P (which goes through Y), or either, when the primary_intf to node F (and possibly node F) fails. The basic approach is to run Select_Alternates(X,F,primary_intf) and Select_Alternates(Y,F,primary_intf) to determine which of the two MRT paths to X and which of the two MRT paths to Y is safe to use in the event of the failure of F. In general, we will find that if it is safe to use a particular path to X or Y when F fails, and @@ -2715,21 +2829,21 @@ specify another real node on the broadcast network as the next-hop. On a network graph where a broadcast network is represented by a pseudonode, this means that if a real node determines that the next- hop to reach a given destination is a pseudonode, it must also determine the next-next-hop for that destination in the network graph, which corresponds to a real node attached to the broadcast network. It is interesting to note that this issue is not unique to the MRT algorithm, but is also encountered in normal SPF computations for - IGPs. Section 16.1.1 of [RFC2327] describes how this is done for + IGPs. Section 16.1.1 of [RFC2328] describes how this is done for OSPF. As OSPF runs Dijkstra's algorithm, whenever a shorter path is found reach a real destination node, and the shorter path is one hop from the computing routing, and that one hop is a pseudonode, then the next-hop for that destination is taken from the interface IP address in the Router-LSA correspond to the link to the real destination node For IS-IS, in the example pseudo-code implementation of Dijkstra's algorithm in Annex C of [ISO10589-Second-Edition] whenever the algorithm encounters an adjacency from a real node to a pseudonode, @@ -2808,20 +2922,24 @@ particular set of failure conditions is a local decision, since it does not require coordination with other nodes. 8. Python Implementation of MRT Lowpoint Algorithm Below is Python code implementing the MRT Lowpoint algorithm specified in this document. In order to avoid the page breaks in the .txt version of the draft, one can cut and paste the Python code from the .xml version. The code is also posted on Github. + While this Python code is believed to correctly implement the pseudo- + code description of the algorithm, in the event of a difference, the + pseudo-code description should be considered normative. + # This program has been tested to run on Python 2.6 and 2.7 # (specifically Python 2.6.6 and 2.7.8 were tested). # The program has known incompatibilities with Python 3.X. # When executed, this program will generate a text file describing # an example topology. It then reads that text file back in as input # to create the example topology, and runs the MRT algorithm.This # was done to simplify the inclusion of the program as a single text # file that can be extracted from the IETF draft. @@ -3029,23 +3146,22 @@ if profile_id in computing_rtr.profile_id_list: computing_rtr.IN_MRT_ISLAND = True explore_list = [computing_rtr] else: return while explore_list != []: next_rtr = explore_list.pop() for intf in next_rtr.intf_list: if ( (not intf.MRT_INELIGIBLE) and (not intf.remote_intf.MRT_INELIGIBLE) - and (not intf.IGP_EXCLUDED) and intf.area == area ): - - if (profile_id in intf.remote_node.profile_id_list): + and (not intf.IGP_EXCLUDED) and intf.area == area + and (profile_id in intf.remote_node.profile_id_list)): intf.IN_MRT_ISLAND = True intf.remote_intf.IN_MRT_ISLAND = True if (not intf.remote_node.IN_MRT_ISLAND): intf.remote_node.IN_MRT_ISLAND = True explore_list.append(intf.remote_node) def Compute_Island_Node_List_For_Test_GR(topo, test_gr): Reset_Computed_Node_and_Intf_Values(topo) topo.test_gr = topo.node_dict[test_gr] MRT_Island_Identification(topo, topo.test_gr, 0, 0) @@ -3557,29 +3674,27 @@ return 'USE_BLUE' if F.topo_order < D_topo_order: return 'USE_RED' assert(False) assert(primary_intf.MRT_INELIGIBLE or primary_intf.remote_intf.MRT_INELIGIBLE) return 'USE_RED_OR_BLUE' else: # D is unordered wrt S if F.HIGHER and F.LOWER: if primary_intf.OUTGOING and primary_intf.INCOMING: - # This can happen when the primary next hop goes - # to a node in a different block and D is - # unordered wrt S. + # This can happen when F and D are in different blocks return 'USE_RED_OR_BLUE' if primary_intf.OUTGOING: + return 'USE_BLUE' if primary_intf.INCOMING: return 'USE_RED' - #This can occur when primary_intf is MRT_INELIGIBLE. #This appears to be a case where the special #construction of the GADAG allows us to choose red, #whereas with an arbitrary GADAG, neither red nor blue #is guaranteed to work. assert(primary_intf.MRT_INELIGIBLE or primary_intf.remote_intf.MRT_INELIGIBLE) return 'USE_RED' if F.LOWER: return 'USE_RED' @@ -3664,44 +3780,35 @@ elif intf.metric == min_metric: cand_alt_list.append(intf) if cand_alt_list != [None]: alt.fec = 'GREEN' alt.prot = 'PARALLEL_CUTLINK' else: alt.fec = 'NO_ALTERNATE' alt.prot = 'NO_PROTECTION' Copy_List_Items(alt.nh_list, cand_alt_list) - # Use Is_Remote_Node_In_NH_List() is used, as opposed + # Is_Remote_Node_In_NH_List() is used, as opposed # to just checking if failed_intf is in D.red_next_hops, # because failed_intf could be marked as MRT_INELIGIBLE. elif Is_Remote_Node_In_NH_List(F, D.red_next_hops): Copy_List_Items(alt.nh_list, D.blue_next_hops) alt.fec = 'BLUE' alt.prot = 'LINK_PROTECTION' - else: - if not Is_Remote_Node_In_NH_List(F, D.blue_next_hops): - print("WEIRD behavior") + elif Is_Remote_Node_In_NH_List(F, D.blue_next_hops): Copy_List_Items(alt.nh_list, D.red_next_hops) alt.fec = 'RED' alt.prot = 'LINK_PROTECTION' + else: + alt.fec = random.choice(['RED','BLUE']) + alt.prot = 'LINK_PROTECTION' - # working version but has issue with MRT_INELIGIBLE link being - # primary_NH -# elif failed_intf in D.red_next_hops: -# Copy_List_Items(alt.nh_list, D.blue_next_hops) -# alt.fec = 'BLUE' -# alt.prot = 'LINK_PROTECTION' -# else: -# Copy_List_Items(alt.nh_list, D.red_next_hops) -# alt.fec = 'RED' -# alt.prot = 'LINK_PROTECTION' D.alt_list.append(alt) def Write_GADAG_To_File(topo, file_prefix): gadag_edge_list = [] for node in topo.node_list: for intf in node.intf_list: if intf.SIMULATION_OUTGOING: local_node = "%04d" % (intf.local_node.node_id) remote_node = "%04d" % (intf.remote_node.node_id) intf_data = "%03d" % (intf.link_data) @@ -4805,21 +4909,21 @@ they did not provide significant differences in the path lenghts for the alternatives. This section does not focus on that analysis or the decision to use the MRT Lowpoint algorithm as the default MRT algorithm; it has the lowest computational and storage requirements and gave comparable results. Since this document defines the MRT Lowpoint algorithm for use in fast-reroute applications, it is useful to compare MRT and Remote LFA [RFC7490]. This section compares MRT and remote LFA for IP Fast Reroute in 19 service provider network topologies, focusing on - coverage and alternate path length. Figure 29 shows the node- + coverage and alternate path length. Figure 30 shows the node- protecting coverage provided by local LFA (LLFA), remote LFA (RLFA), and MRT against different failure scenarios in these topologies. The coverage values are calculated as the percentage of source- destination pairs protected by the given IPFRR method relative to those protectable by optimal routing, against the same failure modes. More details on alternate selection policies used for this analysis are described later in this section. +------------+-----------------------------+ | Topology | percentage of failure | @@ -4842,38 +4946,38 @@ | T212 | 59 | 63 | 100 | | T213 | 84 | 84 | 100 | | T214 | 68 | 78 | 100 | | T215 | 84 | 88 | 100 | | T216 | 43 | 59 | 100 | | T217 | 78 | 88 | 100 | | T218 | 72 | 75 | 100 | | T219 | 78 | 84 | 100 | +------------+---------+---------+---------+ - Figure 29 + Figure 30 For the topologies analyzed here, LLFA is able to provide node- protecting coverage ranging from 37% to 95% of the source-destination pairs, as seen in the column labeled NP_LLFA. The use of RLFA in addition to LLFA is generally able to increase the node-protecting coverage. The percentage of node-protecting coverage with RLFA is provided in the column labeled NP_RLFA, ranges from 59% to 98% for these topologies. The node-protecting coverage provided by MRT is 100% since MRT is able to provide protection for any source- destination pair for which a path still exists after the failure. We would also like to measure the quality of the alternate paths produced by these different IPFRR methods. An obvious approach is to take an average of the alternate path costs over all source- destination pairs and failure modes. However, this presents a problem, which we will illustrate by presenting an example of results - for one topology using this approach ( Figure 30). In this table, + for one topology using this approach ( Figure 31). In this table, the average relative path length is the alternate path length for the IPFRR method divided by the optimal alternate path length, averaged over all source-destination pairs and failure modes. The first three columns of data in the table give the path length calculated from the sum of IGP metrics of the links in the path. The results for topology T208 show that the metric-based path lengths for NP_LLFA and NP_RLFA alternates are on average 78 and 66 times longer than the path lengths for optimal alternates. The metric-based path lengths for MRT alternates are on average 14 times longer than for optimal alternates. @@ -4881,45 +4985,45 @@ +--------+------------------------------------------------+ | | average relative alternate path length | | |-----------------------+------------------------+ |Topology| IGP metric | hopcount | | |-----------------------+------------------------+ | |NP_LLFA |NP_RLFA | MRT |NP_LLFA |NP_RLFA | MRT | +--------+--------+--------+-----+--------+--------+------+ | T208 | 78.2 | 66.0 | 13.6| 0.99 | 1.01 | 1.32 | +--------+--------+--------+-----+--------+--------+------+ - Figure 30 + Figure 31 The network topology represented by T208 uses values of 10, 100, and 1000 as IGP costs, so small deviations from the optimal alternate path can result in large differences in relative path length. LLFA, RLFA, and MRT all allow for at least one hop in the alterate path to be chosen independent of the cost of the link. This can easily result in an alternate using a link with cost 1000, which introduces noise into the path length measurement. In the case of T208, the adverse effects of using metric-based path lengths is obvious. However, we have observed that the metric-based path length introduces noise into alternate path length measurements in several other topologies as well. For this reason, we have opted to measure the alternate path length using hopcount. While IGP metrics may be adjusted by the network operator for a number of reasons (e.g. traffic engineering), the hopcount is a fairly stable measurement of - path length. As shown in the last three columns of Figure 30, the + path length. As shown in the last three columns of Figure 31, the hopcount-based alternate path lengths for topology T208 are fairly well-behaved. - Figure 31, Figure 32, Figure 33, and Figure 34 present the hopcount- + Figure 32, Figure 33, Figure 34, and Figure 35 present the hopcount- based path length results for the 19 topologies examined. The topologies in the four tables are grouped based on the size of the - topologies, as measured by the number of nodes, with Figure 31 having - the smallest topologies and Figure 34 having the largest topologies. + topologies, as measured by the number of nodes, with Figure 32 having + the smallest topologies and Figure 35 having the largest topologies. Instead of trying to represent the path lengths of a large set of alternates with a single number, we have chosen to present a histogram of the path lengths for each IPFRR method and alternate selection policy studied. The first eight colums of data represent the percentage of failure scenarios protected by an alternate N hops longer than the primary path, with the first column representing an alternate 0 or 1 hops longer than the primary path, all the way up through the eighth column respresenting an alternate 14 or 15 hops longer than the primary path. The last column in the table gives the percentage of failure scenarios for which there is no alternate less @@ -4994,21 +5098,21 @@ | MRT_LOWPOINT_ONLY | 58| 27| 11| 3| 1| | | | | +------------------------------+---+---+---+---+---+---+---+---+----+ | T205(avg primary hops=3.4) | | | | | | | | | | | OPTIMAL | 92| 8| | | | | | | | | NP_LLFA | 89| 3| | | | | | | 8| | NP_LLFA_THEN_NP_RLFA | 90| 4| | | | | | | 7| | NP_LLFA_THEN_MRT_LOWPOINT | 91| 9| | | | | | | | | MRT_LOWPOINT_ONLY | 62| 33| 5| 1| | | | | | +------------------------------+---+---+---+---+---+---+---+---+----+ - Figure 31 + Figure 32 +-------------------------------------------------------------------+ | | percentage of failure scenarios | | Topology name | protected by an alternate N hops | | and | longer than the primary path | | alternate selection +------------------------------------+ | policy evaluated | | | | | | | | | no | | | | | | | |10 |12 |14 | alt| | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| +------------------------------+---+---+---+---+---+---+---+---+----+ @@ -5041,21 +5145,21 @@ | MRT_LOWPOINT_ONLY | 63| 29| 8| | | | | | | +------------------------------+---+---+---+---+---+---+---+---+----+ | T210(avg primary hops=2.5) | | | | | | | | | | | OPTIMAL | 95| 4| 1| | | | | | | | NP_LLFA | 94| 1| | | | | | | 5| | NP_LLFA_THEN_NP_RLFA | 94| 3| 1| | | | | | 2| | NP_LLFA_THEN_MRT_LOWPOINT | 95| 4| 1| | | | | | | | MRT_LOWPOINT_ONLY | 91| 6| 2| | | | | | | +------------------------------+---+---+---+---+---+---+---+---+----+ - Figure 32 + Figure 33 +-------------------------------------------------------------------+ | | percentage of failure scenarios | | Topology name | protected by an alternate N hops | | and | longer than the primary path | | alternate selection +------------------------------------+ | policy evaluated | | | | | | | | | no | | | | | | | |10 |12 |14 | alt| | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| +------------------------------+---+---+---+---+---+---+---+---+----+ @@ -5088,21 +5192,21 @@ | MRT_LOWPOINT_ONLY | 30| 20| 18| 12| 8| 4| 3| 2| 3| +------------------------------+---+---+---+---+---+---+---+---+----+ | T215(avg primary hops=4.8) | | | | | | | | | | | OPTIMAL | 73| 27| | | | | | | | | NP_LLFA | 73| 11| | | | | | | 16| | NP_LLFA_THEN_NP_RLFA | 73| 13| 2| | | | | | 12| | NP_LLFA_THEN_MRT_LOWPOINT | 74| 19| 3| 2| 1| 1| 1| | | | MRT_LOWPOINT_ONLY | 32| 31| 16| 12| 4| 3| 1| | | +------------------------------+---+---+---+---+---+---+---+---+----+ - Figure 33 + Figure 34 +-------------------------------------------------------------------+ | | percentage of failure scenarios | | Topology name | protected by an alternate N hops | | and | longer than the primary path | | alternate selection +------------------------------------+ | policy evaluated | | | | | | | | | no | | | | | | | |10 |12 |14 | alt| | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| +------------------------------+---+---+---+---+---+---+---+---+----+ @@ -5128,21 +5232,21 @@ | MRT_LOWPOINT_ONLY | 37| 29| 21| 10| 3| 1| | | | +------------------------------+---+---+---+---+---+---+---+---+----+ | T219(avg primary hops=7.7) | | | | | | | | | | | OPTIMAL | 77| 15| 5| 1| 1| | | | | | NP_LLFA | 72| 5| | | | | | | 22| | NP_LLFA_THEN_NP_RLFA | 73| 8| 2| | | | | | 16| | NP_LLFA_THEN_MRT_LOWPOINT | 74| 8| 3| 3| 2| 2| 2| 2| 4| | MRT_LOWPOINT_ONLY | 19| 14| 15| 12| 10| 8| 7| 6| 10| +------------------------------+---+---+---+---+---+---+---+---+----+ - Figure 34 + Figure 35 In the preceding analysis, the following procedure for selecting an RLFA was used. Nodes were ordered with respect to distance from the source and checked for membership in Q and P-space. The first node to satisfy this condition was selected as the RLFA. More sophisticated methods to select node-protecting RLFAs is an area of active research. The analysis presented above uses the MRT Lowpoint Algorithm defined in this specification with a common GADAG root. The particular @@ -5156,21 +5260,21 @@ chosen based on the GADAG Root Selection Priority advertised by each router, the values of which would be determined off-line. In order to measure how sensitive the MRT alternate path lengths are to the choice of common GADAG root, we performed the same analysis using different choices of GADAG root. All of the nodes in the network were ordered with respect to the node centrality as computed above. Nodes were chosen at the 0th, 25th, and 50th percentile with respect to the centrality ordering, with 0th percentile being the most central node. The distribution of alternate path lengths for - those three choices of GADAG root are shown in Figure 35 for a subset + those three choices of GADAG root are shown in Figure 36 for a subset of the 19 topologies (chosen arbitrarily). The third row for each topology (labeled MRT_LOWPOINT ( 0 percentile) ) reproduces the results presented above for MRT_LOWPOINT_ONLY. The fourth and fifth rows show the alternate path length distibution for the 25th and 50th percentile choice for GADAG root. One can see some impact on the path length distribution with the less central choice of GADAG root resulting in longer path lenghths. We also looked at the impact of MRT algorithm variant on the alternate path lengths. The first two rows for each topology present @@ -5226,168 +5330,126 @@ | MRT_LOWPOINT (50 percentile) | 19| 14| 13| 10| 8| 6| 5| 5| 10| +------------------------------+---+---+---+---+---+---+---+---+----+ | 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 35 + Figure 36 10. 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. 11. Acknowledgements - The authors would like to thank Shraddha Hegde for her suggestions - and review. We would also like to thank Anil Kumar SN for his - assistance in clarifying the algorithm description and pseudo-code. + The authors would like to thank Shraddha Hegde, Eric Wu, and Janos + Farkas for their suggestions and review. We would also like to thank + Anil Kumar SN for his assistance in clarifying the algorithm + description and pseudo-code. 12. IANA Considerations This document includes no request to IANA. 13. Security Considerations - This architecture is not currently believed to introduce new security - concerns. + The algorithm described in this document does not introduce new + security concerns beyond those already discussed in the document + describing the MRT FRR architecture + [I-D.ietf-rtgwg-mrt-frr-architecture]. 14. References 14.1. Normative References [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", draft- - ietf-rtgwg-mrt-frr-architecture-05 (work in progress), - January 2015. + ietf-rtgwg-mrt-frr-architecture-07 (work in progress), + October 2015. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . 14.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.ietf-isis-mrt] - Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J. + Li, Z., Wu, N., <>, Q., Atlas, A., Bowers, C., and J. Tantsura, "Intermediate System to Intermediate System (IS- IS) Extensions for Maximally Redundant Trees (MRT)", - draft-ietf-isis-mrt-00 (work in progress), February 2015. + draft-ietf-isis-mrt-01 (work in progress), October 2015. [I-D.ietf-isis-pcr] Farkas, J., Bragg, N., Unbehagen, P., Parsons, G., Ashwood-Smith, P., and C. Bowers, "IS-IS Path Computation - and Reservation", draft-ietf-isis-pcr-00 (work in - progress), April 2015. - - [I-D.ietf-mpls-ldp-mrt] - Atlas, A., Tiruveedhula, K., Bowers, C., Tantsura, J., and - I. Wijnands, "LDP Extensions to Support Maximally - Redundant Trees", draft-ietf-mpls-ldp-mrt-00 (work in - progress), January 2015. + and Reservation", draft-ietf-isis-pcr-04 (work in + progress), December 2015. [I-D.ietf-ospf-mrt] Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li, "OSPF Extensions to Support Maximally Redundant Trees", - draft-ietf-ospf-mrt-00 (work in progress), January 2015. - - [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. + draft-ietf-ospf-mrt-01 (work in progress), October 2015. [I-D.ietf-rtgwg-lfa-manageability] Litkowski, S., Decraene, B., Filsfils, C., Raza, K., Horneffer, M., and P. Sarkar, "Operational management of Loop Free Alternates", draft-ietf-rtgwg-lfa- manageability-11 (work in progress), June 2015. [ISO10589-Second-Edition] International Organization for Standardization, "Intermediate system to Intermediate system intra-domain routeing information exchange protocol for use in conjunction with the protocol for providing the connectionless-mode Network Service (ISO 8473)", ISO/ IEC 10589:2002, Second Edition, Nov. 2002. [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, - . - - [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 Symposium on Computers and Comunications (ISCC) , 2009, . - [RFC2327] Handley, M. and V. Jacobson, "SDP: Session Description - Protocol", RFC 2327, DOI 10.17487/RFC2327, April 1998, - . - - [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. - McPherson, "OSPF Stub Router Advertisement", RFC 3137, - DOI 10.17487/RFC3137, June 2001, - . + [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, + DOI 10.17487/RFC2328, April 1998, + . [RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi Topology (MT) Routing in Intermediate System to Intermediate Systems (IS-ISs)", RFC 5120, DOI 10.17487/RFC5120, February 2008, . - [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for - IP Fast Reroute: Loop-Free Alternates", RFC 5286, - DOI 10.17487/RFC5286, September 2008, - . - - [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", - RFC 5714, DOI 10.17487/RFC5714, January 2010, - . - - [RFC6571] Filsfils, C., Ed., Francois, P., Ed., Shand, M., Decraene, - B., Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free - Alternate (LFA) Applicability in Service Provider (SP) - Networks", RFC 6571, DOI 10.17487/RFC6571, June 2012, - . - [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", RFC 7490, DOI 10.17487/RFC7490, April 2015, . Appendix A. Option 2: Computing GADAG using SPFs The basic idea in this option is to use slightly-modified SPF computations to find ears. In every block, an SPF computation is first done to find a cycle from the local root and then SPF @@ -5451,29 +5513,30 @@ and cand_intf.local_node as TEMP_UNUSABLE if cand_intf.local_node is not block_root Mark cand_intf.local_node as TEMP_UNUSABLE Initialize ear_list to empty end_ear = Mod_SPF(spf_root, block_root) y = end_ear.spf_prev_hop while y.local_node is not spf_root add_to_list_start(ear_list, y) y.local_node.IN_GADAG = true y = y.local_node.spf_prev_intf + if(method is not hybrid) Set_Ear_Direction(ear_list, cand_intf.local_node, end_ear,block_root) 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 36: Modified SPF for GADAG computation + Figure 37: 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.5, 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 @@ -5522,21 +5585,21 @@ add i.local_node to x.Higher_Nodes else foreach node x where x.localroot is block_root if end_b is in x.Lower_Nodes foreach interface i in ear_list add i.local_node to x.Lower_Nodes if end_a is in x.Higher_Nodes foreach interface i in ear_list add i.remote_node to x.Higher_Nodes - Figure 37: Algorithm to assign links of an ear direction + Figure 38: Algorithm to assign links of an ear direction A goal of the algorithm is to find the shortest cycles and ears. An ear is started by going to a neighbor x of an IN_GADAG node y. The path from x to an IN_GADAG node is minimal, since it is computed via SPF. Since a shortest path is made of shortest paths, to find the shortest ears requires reaching from the set of IN_GADAG nodes to the closest node that isn't IN_GADAG. Therefore, an ordered tree is 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, @@ -5601,21 +5664,21 @@ ear_end = SPF_for_Ear(cand_intf.local_node, cand_intf.remote_node, cand_intf.remote_node.localroot, SPF method) y = ear_end.spf_prev_hop while y.local_node is not cand_intf.local_node add_eligible_interfaces_of_node( ordered_intfs_tree, y.local_node) y = y.local_node.spf_prev_intf - Figure 38: SPF-based GADAG algorithm + Figure 39: 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 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 @@ -5630,21 +5693,21 @@ 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 only one incoming interface in each block, which is necessary for correctly computing the next-hops on the GADAG. As in the SPF gadag, bridge ears are handled as a special case. - The entire algorithm is shown below in Figure 39 + The entire algorithm is shown below in Figure 40 find_spf_stack_ear(stack, x, y, xy_intf, block_root) if L(y) == D(y) // Special case for cut-links xy_intf.UNDIRECTED = false xy_intf.remote_intf.UNDIRECTED = false xy_intf.OUTGOING = true xy_intf.INCOMING = true xy_intf.remote_intf.OUTGOING = true xy_intf.remote_intf.INCOMING = true @@ -5680,41 +5743,41 @@ root.IN_GADAG = true Initialize Stack to empty push root onto Stack while (Stack is not empty) x = pop(Stack) for each interface intf of x y = intf.remote_node if y.IN_GADAG is false find_spf_stack_ear(stack, x, y, intf, y.block_root) - Figure 39: Hybrid GADAG algorithm + Figure 40: Hybrid GADAG algorithm Authors' Addresses - Gabor Sandor Enyedi (editor) + Gabor Sandor Enyedi Ericsson Konyves Kalman krt 11 Budapest 1097 Hungary Email: Gabor.Sandor.Enyedi@ericsson.com Andras Csaszar Ericsson Konyves Kalman krt 11 Budapest 1097 Hungary Email: Andras.Csaszar@ericsson.com - Alia Atlas (editor) + Alia Atlas Juniper Networks 10 Technology Park Drive Westford, MA 01886 USA Email: akatlas@juniper.net Chris Bowers Juniper Networks 1194 N. Mathilda Ave.