--- 1/draft-ietf-rtgwg-mrt-frr-algorithm-02.txt 2015-03-09 14:14:41.808909571 -0700 +++ 2/draft-ietf-rtgwg-mrt-frr-algorithm-03.txt 2015-03-09 14:14:41.936912652 -0700 @@ -1,24 +1,24 @@ Routing Area Working Group G. Enyedi, Ed. Internet-Draft A. Csaszar Intended status: Standards Track Ericsson -Expires: July 23, 2015 A. Atlas, Ed. +Expires: September 10, 2015 A. Atlas, Ed. C. Bowers Juniper Networks A. Gopalan University of Arizona - January 19, 2015 + March 9, 2015 Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- Reroute - draft-ietf-rtgwg-mrt-frr-algorithm-02 + draft-ietf-rtgwg-mrt-frr-algorithm-03 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 July 23, 2015. + This Internet-Draft will expire on September 10, 2015. 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 @@ -59,52 +59,52 @@ 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 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. 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 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: Next-hop conformance . . . . . . . . 40 - 7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 40 - 7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 41 - 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 + 5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 19 + 5.2. MRT Island Identification . . . . . . . . . . . . . . . . 22 + 5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 23 + 5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 23 + 5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint + inheritance . . . . . . . . . . . . . . . . . . . . . . . 24 + 5.6. Augmenting the GADAG by directing all links . . . . . . . 26 + 5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 28 + 5.7.1. MRT next-hops to all nodes partially ordered with + respect to the computing node . . . . . . . . . . . . 29 + 5.7.2. MRT next-hops to all nodes not partially ordered with + respect to the computing node . . . . . . . . . . . . 30 + 5.7.3. Computing Redundant Tree next-hops in a 2-connected + Graph . . . . . . . . . . . . . . . . . . . . . . . . 31 + 5.7.4. Generalizing for a graph that isn't 2-connected . . . 32 + 5.7.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 33 + 5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 35 + 5.9. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 39 + 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 42 + 7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 42 + 7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 43 + 8. Implementation Status . . . . . . . . . . . . . . . . . . . . 53 + 9. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 53 + 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 53 + 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 53 + 12. Security Considerations . . . . . . . . . . . . . . . . . . . 53 + 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 53 + 13.1. Normative References . . . . . . . . . . . . . . . . . . 53 + 13.2. Informative References . . . . . . . . . . . . . . . . . 53 + Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 56 + Appendix B. Option 3: Computing GADAG using a hybrid method . . 61 + Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 63 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 @@ -376,21 +376,21 @@ disjoint from the decreasing paths. E.g. in the previous example node B has multiple possibilities to forward packets along an increasing path: it can either forward packets to C or F. 4.2. Finding an Ear and the Correct Direction For simplicity, the basic idea of creating a GADAG by adding ears is described assuming that the network graph is a single 2-connected cluster so that an ADAG is sufficient. Generalizing to multiple blocks is done by considering the block-roots instead of the GADAG - root - and the actual algorithm is given in Section 5.4. + root - and the actual algorithm is given in Section 5.5. 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 @@ -432,21 +432,21 @@ cycle; therefore the ear must go from X to Y. In the case, when X and Y are not ordered with each other, we can select either direction for the ear. We have no restriction since neither of the directions can result in a cycle. In the corner case when one of the endpoints of an ear, say X, is the root (recall that the two endpoints must be different), we could use both directions again for the ear because the root can be considered both as smaller and as greater than Y. However, we strictly pick that direction in which the root is lower than Y. The logic for this decision is - explained in Section 5.6 + explained in Section 5.7 A partial ADAG is started by finding a cycle from the root R back to itself. This can be done by selecting a non-ready neighbor N of R 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 @@ -480,21 +480,21 @@ Add the ear towards Y to the ADAG Figure 6: Generic Algorithm to find ears and their direction in 2-connected graph Algorithm Figure 6 merely requires that a cycle or ear be selected without specifying how. Regardless of the way of selecting the path, 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 + Inheritance is defined in Section 5.5. 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 @@ -549,21 +549,21 @@ 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.dfs_parent_intf = p_to_x.remote_intf 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) @@ -598,40 +598,40 @@ [A]---------[B] [G]----| [L]------[M] (1, ) (2, ) (7, ) (12, ) (13, ) (b) with DFS values assigned (D(x), L(x)) [E]----| [J]---------[I] [P]------[O] (5,0) | (10,3) (9,3) (16,11) (15,11) | | | | | | | | | | | | [R] [D]---[C]---[F] [H]----[K] [N] - (0, ) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11) + (0,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 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 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 + < 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. @@ -652,54 +652,55 @@ [E]---| [J]-------[I] [P]---[O] | | | | | | | | | | | | [R] [D]---[C]--[F] [H]---[K] [N] | | | | | | | | | | | | [A]--------[B] [G]---| [L]---[M] (a) A graph with four blocks that are: - 3 2-connected clusters and a cut-link + three 2-connected clusters + and one cut-link [E]<--| [J]<------[I] [P]<--[O] | | | ^ | ^ V | V | V | [R] [D]<--[C] [F] [H]<---[K] [N] ^ | ^ ^ | V | | [A]------->[B] [G]---| [L]-->[M] - (b) MRT-Blue + (b) MRT-Blue for destination R [E]---| [J]-------->[I] [P]-->[O] | | | V V V [R] [D]-->[C]<---[F] [H]<---[K] [N] ^ | ^ | ^ | | V | | | V [A]<-------[B] [G]<--| [L]<--[M] - (c) MRT-Red + (c) MRT-Red for destionation R Figure 10 Consider the example depicted in Figure 10 (a). In this figure, a special graph is presented, showing us all the ways 2-connected clusters can be connected. It has four blocks: block 1 contains R, A, B, C, D, E, block 2 contains C, F, G, H, I, J, block 3 contains K, L, M, N, O, P, and block 4 is a cut-link containing H and K. As can be observed, the first two blocks have one common node (node C) and blocks 2 and 3 do not have any common node, but they are connected through a cut-link that is block 4. No two blocks can have more than - one common node, since two blocks with at least 2 common nodes would - qualify as a single 2-connected cluster. + one common node, since two blocks with at least two common nodes + would qualify as a single 2-connected cluster. Moreover, observe that if we want to get from one block to another, we must use a cut-vertex (the cut-vertices in this graph are C, H, K), regardless of the path selected, so we can say that all the paths from block 3 along the MRTs rooted at R will cross K first. This observation means that if we want to find a pair of MRTs rooted at R, then we need to build up a pair of RTs in block 3 with K as a root. Similarly, we need to find another pair of RTs in block 2 with C as a root, and finally, we need the last pair of RTs in block 1 with R as a root. When all the trees are selected, we can simply combine them; @@ -715,38 +716,39 @@ 4.5. Determining Local-Root and Assigning Block-ID Each node in a network graph has a local-root, which is the cut- vertex (or root) in the same block that is closest to the root. The local-root is used to determine whether two nodes share a common block. Compute_Localroot(node x, node localroot) x.localroot = localroot - for each DFS child c + for each DFS child node c of x if L(c) < D(x) //x is not a cut-vertex Compute_Localroot(c, x.localroot) else mark x as cut-vertex Compute_Localroot(c, x) Compute_Localroot(root, root) Figure 11: A method for computing local-roots There are two different ways of computing the local-root for each node. The stand-alone method is given in Figure 11 and better illustrates the concept; it is used by the MRT algorithms given in the Appendices Appendix A and Appendix B. The MRT Lowpoint algorithm computes the local-root for a block as part of computing the GADAG using lowpoint inheritance; the essence of this computation is given - in Figure 12. + in Figure 12. Both methods for computing the local-root produce the + same results. Get the current node, s. Compute an ear(either through lowpoint inheritance or by following dfs parents) from s to a ready node e. (Thus, s is not e, if there is such ear.) if s is e for each node x in the ear that is not s x.localroot = s else for each node x in the ear that is not s or e @@ -790,72 +792,156 @@ 5. Algorithm Sections This algorithm computes one GADAG that is then used by a router to determine its MRT-Blue and MRT-Red next-hops to all destinations. Finally, based upon that information, alternates are selected for each next-hop to each destination. The different parts of this algorithm are described below. These work on a network graph after its interfaces have been ordered as per Figure 14. 1. Compute the local MRT Island for the particular MRT Profile. - [See Section 5.1.] + [See Section 5.2.] - 2. Select the root to use for the GADAG. [See Section 5.2.] + 2. Select the root to use for the GADAG. [See Section 5.3.] - 3. Initialize all interfaces to UNDIRECTED. [See Section 5.3.] + 3. Initialize all interfaces to UNDIRECTED. [See Section 5.4.] 4. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See Figure 8.] - 5. Construct the GADAG. [See Section 5.4] + 5. Construct the GADAG. [See Section 5.5] 6. Assign directions to all interfaces that are still UNDIRECTED. - [See Section 5.5.] + [See Section 5.6.] 7. From the computing router x, compute the next-hops for the MRT- - Blue and MRT-Red. [See Section 5.6.] + Blue and MRT-Red. [See Section 5.7.] 8. Identify alternates for each next-hop to each destination by determining which one of the blue MRT and the red MRT the - computing router x should select. [See Section 5.7.] + computing router x should select. [See Section 5.8.] + +5.1. Interface Ordering To ensure consistency in computation, all routers MUST order interfaces identically down to the set of links with the same metric to the same neighboring node. This is necessary for the DFS, where the selection order of the interfaces to explore results in different trees, and for computing the GADAG, where the selection order of the interfaces to use to form ears can result in different GADAGs. The required ordering between two interfaces from the same router x is given in Figure 14. Interface_Compare(interface a, interface b) if a.metric < b.metric return A_LESS_THAN_B if b.metric < a.metric return B_LESS_THAN_A - if a.neighbor.loopback_addr < b.neighbor.loopback_addr + if a.neighbor.mrt_node_id < b.neighbor.mrt_node_id return A_LESS_THAN_B - if b.neighbor.loopback_addr < a.neighbor.loopback_addr + if b.neighbor.mrt_node_id < a.neighbor.mrt_node_id return B_LESS_THAN_A - // Same metric to same node, so the order doesn't matter anymore for + // Same metric to same node, so the order doesn't matter for // interoperability. - // To have a unique, consistent total order, - // tie-break in OSPF based on the link's linkData as - // distributed in an OSPF Router-LSA - if a.link_data < b.link_data - return A_LESS_THAN_B - return B_LESS_THAN_A + return A_EQUAL_TO_B Figure 14: Rules for ranking multiple interfaces. Order is from low to high. -5.1. MRT Island Identification + In Figure 14, if two interfaces on a router connect to the same + remote router with the same metric, the Interface_Compare function + returns A_EQUAL_TO_B. This is because the order in which those + interfaces are initially explored does not affect the final GADAG + produced by the algorithm described here. While only one of the + links will be added to the GADAG in the initial traversal, the other + parallel links will be added to the GADAG with the same direction + assigned during the procedure for assigning direction to UNDIRECTED + links described in Section 5.6. An implementation is free to apply + some additional criteria to break ties in interface ordering in this + situation, but that criteria is not specified here since it will not + affect the final GADAG produced by the algorithm. + + The Interface_Compare function in Figure 14 relies on the + interface.metric and the interface.neighbor.mrt_node_id values to + order interfaces. The exact source of these values for different + IGPs (or flooding protocol in the case of ISIS-PCR + [I-D.farkas-isis-pcr]) and applications is specified in Figure 15. + The metric and mrt_node_id values for OSPFv2, OSPFv3, and IS-IS + provided here is normative. The metric and mrt_node_id values for + ISIS-PCR should be considered informational. + + +--------------+-----------------------+-----------------------------+ + | IGP/flooding | mrt_node_id | metric of | + | protocol | of neighbor | interface | + | and | on interface | | + | application | | | + +--------------+-----------------------+-----------------------------+ + | OSPFv2 for | 4 octet Neighbor | 2 octet Metric field | + | IP/LDP FRR | Router ID in | for corresponding | + | | Link ID field for | point-to-point link | + | | corresponding | in Router-LSA | + | | point-to-point link | | + | | in Router-LSA | | + +--------------+-----------------------+-----------------------------+ + | OSPFv3 for | 4 octet Neighbor | 2 octet Metric field | + | IP/LDP FRR | Router ID field | for corresponding | + | | for corresponding | point-to-point link | + | | point-to-point link | in Router-LSA | + | | in Router-LSA | | + +--------------+-----------------------+-----------------------------+ + | IS-IS for | 7 octet neighbor | 3 octet metric field | + | IP/LDP FRR | system ID and | in Extended IS | + | | pseudonode number | Reachability TLV #22 | + | | in Extended IS | or Multi-Topology | + | | Reachability TLV #22 | IS Neighbor TLV #222 | + | | or Multi-Topology | | + | | IS Neighbor TLV #222 | | + +--------------+-----------------------+-----------------------------+ + | ISIS-PCR for | 8 octet Bridge ID | 3 octet SPB-LINK-METRIC in | + | protection | created from 2 octet | SPB-Metric sub-TLV (type 29)| + | of traffic | Bridge Priority in | in Extended IS Reachability | + | in bridged | SPB Instance sub-TLV | TLV #22 or Multi-Topology | + | networks | (type 1) carried in | Intermediate Systems | + | | MT-Capability TLV | TLV #222. In the case | + | | #144 and 6 octet | of asymmetric link metrics, | + | | neighbor system ID in | the larger link metric | + | | Extended IS | is used for both link | + | | Reachability TLV #22 | directions. | + | | or Multi-Topology | (informational) | + | | Intermediate Systems | | + | | TLV #222 | | + | | (informational) | | + +--------------+-----------------------+-----------------------------+ + + Figure 15: value of interface.neighbor.mrt_node_id and + interface.metric to be used for ranking interfaces, for different + flooding protocols and applications + + The metrics are unsigned integers and MUST be compared as unsigned + integers. The results of mrt_node_id comparisons MUST be the same as + would be obtained by converting the mrt_node_ids to unsigned integers + using network byte order and performing the comparison as unsigned + integers. Also note that these values are only specified in the case + of point-to-point links. Therefore, in the case of IS-IS for IP/LDP + FRR, the pseudonode number (the 7th octet) will always be zero. + + In the case of IS-IS for IP/LDP FRR, this specification allows for + the use of Multi-Topology routing. [RFC5120] requires that + information related to the standard/default topology (MT-ID = 0) be + carried in the Extended IS Reachability TLV #22, while it requires + that the Multi-Topology IS Neighbor TLV #222 only be used to carry + topology information related to non-default topologies (with non-zero + MT-IDs). [RFC5120] enforces this by requiring an implementation to + ignore TLV#222 with MT-ID = 0. The current document also requires + that TLV#222 with MT-ID = 0 MUST be ignored. + +5.2. 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). 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. @@ -867,70 +953,70 @@ while (explore_list is not empty) next_rtr = remove_head(explore_list) for each interface in next_rtr 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 + Figure 16: MRT Island Identification -5.2. GADAG Root Selection +5.3. GADAG Root Selection 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 + [I-D.ietf-ospf-mrt] and [I-D.ietf-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 significant impact on the lengths of the alternate paths computed. Therefore, it is RECOMMENDED that off-line analysis that considers the centrality of a router be used to help determine how good a choice a particular router is for the role of GADAG root. -5.3. Initialization +5.4. Initialization Before running the algorithm, there is the standard type of initialization to be done, such as clearing any computed DFS-values, lowpoint-values, DFS-parents, lowpoint-parents, any MRT-computed 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. 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 + flooded via the IGP [I-D.ietf-ospf-mrt] [I-D.ietf-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 +5.5. 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 associated interfaces are marked based on the direction taken. The nodes in the ear are marked as IN_GADAG. In the algorithm, first the @@ -969,79 +1055,79 @@ the ear unless the end of the ear is x itself, in which case the local-root for all the nodes in the ear would be x. This is because whenever the first cycle is found in a block, or an ear involving a bridge is computed, the cut-vertex closest to the root would be x itself. In all other scenarios, the properties of lowpoint/dfs parents ensure that the end of the ear will be in the same block, and thus inheriting its local-root would be the correct local-root for all newly added nodes. The pseudo-code for the GADAG algorithm (assuming that the adjustment - of lowpoint for cut-vertices has been made) is shown in Figure 16. + of lowpoint for cut-vertices has been made) is shown in Figure 17. - Construct_Ear(x, Stack, intf, type) + Construct_Ear(x, Stack, intf, ear_type) ear_list = empty cur_node = intf.remote_node cur_intf = intf not_done = true while not_done cur_intf.UNDIRECTED = false cur_intf.OUTGOING = true cur_intf.remote_intf.UNDIRECTED = false cur_intf.remote_intf.INCOMING = true if cur_node.IN_GADAG is false cur_node.IN_GADAG = true add_to_list_end(ear_list, cur_node) - if type is CHILD + if ear_type is CHILD cur_intf = cur_node.lowpoint_parent_intf cur_node = cur_node.lowpoint_parent - else type must be NEIGHBOR + else // ear_type must be NEIGHBOR cur_intf = cur_node.dfs_parent_intf cur_node = cur_node.dfs_parent else not_done = false - if (type is CHILD) and (cur_node is x) + if (ear_type is CHILD) and (cur_node is x) //x is a cut-vertex and the local root for //the block in which the ear is computed localroot = x else // Inherit local-root from the end of the ear localroot = cur_node.localroot while ear_list is not empty y = remove_end_item_from_list(ear_list) y.localroot = localroot push(Stack, y) Construct_GADAG_via_Lowpoint(topology, root) root.IN_GADAG = true - root.localroot = root + root.localroot = None Initialize Stack to empty push root onto Stack while (Stack is not empty) x = pop(Stack) foreach interface intf of x if ((intf.remote_node.IN_GADAG == false) and (intf.remote_node.dfs_parent is x)) Construct_Ear(x, Stack, intf, CHILD) foreach interface intf of x if ((intf.remote_node.IN_GADAG == false) and (intf.remote_node.dfs_parent is not x)) Construct_Ear(x, Stack, intf, NEIGHBOR) Construct_GADAG_via_Lowpoint(topology, root) - Figure 16: Low-point Inheritance GADAG algorithm + Figure 17: Low-point Inheritance GADAG algorithm -5.5. Augmenting the GADAG by directing all links +5.6. Augmenting the GADAG by directing all links The GADAG, regardless of the algorithm used to construct it, at this point could be used to find MRTs but the topology does not include all links in the network graph. That has two impacts. First, there might be shorter paths that respect the GADAG partial ordering and so the alternate paths would not be as short as possible. Second, there may be additional paths between a router x and the root that are not included in the GADAG. Including those provides potentially more bandwidth to traffic flowing on the alternates and may reduce congestion compared to just using the GADAG as currently constructed. @@ -1058,21 +1144,21 @@ 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 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 + in Figure 18 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 @@ -1128,149 +1214,157 @@ i.remote_intf.INCOMING = true i.remote_intf.UNDIRECTED = false else i.INCOMING = true i.UNDIRECTED = false i.remote_intf.OUTGOING = true i.remote_intf.UNDIRECTED = false Add_Undirected_Links(topo, root) - Figure 17: Assigning direction to UNDIRECTED links + Figure 18: 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 for proxy-nodes and how the appropriate alternate next-hops are - selected is given in Section 5.8. + selected is given in Section 5.9. -5.6. Compute MRT next-hops +5.7. 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 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. As usual, the two basic ideas will be discussed assuming the network is two-connected. The generalization to multiple blocks is discussed - in Section 5.6.4. The full algorithm is given in Section 5.6.5. + in Section 5.7.4. The full algorithm is given in Section 5.7.5. -5.6.1. MRT next-hops to all nodes partially ordered with respect to the +5.7.1. MRT next-hops to all nodes partially ordered with respect to the computing node To find two node-disjoint paths from the computing router X to any node Y, depends upon whether Y >> X or Y << X. As shown in - Figure 18, if Y >> X, then there is an increasing path that goes from + Figure 19, if Y >> X, then there is an increasing path that goes from X to Y without crossing R; this contains nodes in the interval [X,Y]. There is also a decreasing path that decreases towards R and then decreases from R to Y; this contains nodes in the interval [X,R-small] or [R-great,Y]. The two paths cannot have common nodes other than X and Y. [Y]<---(Cloud 2)<--- [X] | ^ | | V | (Cloud 3)--->[R]--->(Cloud 1) MRT-Blue path: X->Cloud 2->Y MRT-Red path: X->Cloud 1->R->Cloud 3->Y - Figure 18: Y >> X + Figure 19: Y >> X - Similar logic applies if Y << X, as shown in Figure 19. In this + Similar logic applies if Y << X, as shown in Figure 20. In this case, the increasing path from X increases to R and then increases from R to Y to use nodes in the intervals [X,R-great] and [R-small, Y]. The decreasing path from X reaches Y without crossing R and uses nodes in the interval [Y,X]. [X]<---(Cloud 2)<--- [Y] | ^ | | V | (Cloud 3)--->[R]--->(Cloud 1) MRT-Blue path: X->Cloud 3->R->Cloud 1->Y MRT-Red path: X->Cloud 2->Y - Figure 19: Y << X + Figure 20: Y << X -5.6.2. MRT next-hops to all nodes not partially ordered with respect to +5.7.2. MRT next-hops to all nodes not partially ordered with respect to the computing node When X and Y are not ordered, the first path should increase until we get to a node G, where G >> Y. At G, we need to decrease to Y. The other path should be just the opposite: we must decrease until we get to a node H, where H << Y, and then increase. Since R is smaller and greater than Y, such G and H must exist. It is also easy to see that these two paths must be node disjoint: the first path contains nodes in interval [X,G] and [Y,G], while the second path contains nodes in - interval [H,X] and [H,Y]. This is illustrated in Figure 20. It is + interval [H,X] and [H,Y]. This is illustrated in Figure 21. It is necessary to decrease and then increase for the MRT-Blue and increase and then decrease for the MRT-Red; if one simply increased for one and decreased for the other, then both paths would go through the root R. (Cloud 6)<---[Y]<---(Cloud 5)<------------| | | | | V | [G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H] ^ | | | | | (Cloud 3)<---[X]<---(Cloud 2)<-----------| MRT-Blue path: decrease to H and increase to Y X->Cloud 2->H->Cloud 5->Y MRT-Red path: increase to G and decrease to Y X->Cloud 3->G->Cloud 6->Y - Figure 20: X and Y unordered + Figure 21: X and Y unordered This gives disjoint paths as long as G and H are not the same node. Since G >> Y and H << Y, if G and H could be the same node, that would have to be the root R. This is not possible because there is only one incoming interface to the root R which is created when the initial cycle is found. Recall from Figure 6 that whenever an ear was found to have an end that was the root R, the ear was directed from R so that the associated interface on R is outgoing and not incoming. Therefore, there must be exactly one node M which is the largest one before R, so the MRT-Red path will never reach R; it will turn at M and decrease to Y. -5.6.3. Computing Redundant Tree next-hops in a 2-connected Graph +5.7.3. Computing Redundant Tree next-hops in a 2-connected Graph The basic ideas for computing RT next-hops in a 2-connected graph - were given in Section 5.6.1 and Section 5.6.2. Given these two + were given in Section 5.7.1 and Section 5.7.2. Given these two ideas, how can we find the trees? If some node X only wants to find the next-hops (which is usually the 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.) + exploring any links from the ADAG root. + + In principle, an traversal method other than SPF could be used to + traverse the GADAG in the process of determining blue and red next- + hops that result in maximally redundant trees. This will be the case + as long as one traversal uses the links in the direction specified by + the GADAG and the other traversal uses the links in the direction + opposite of that specified by the GADAG. However, a different + traversal algorithm will generally result in different blue and red + next-hops. Therefore, the algorithm specified here requires the use + of SPF to traverse the GADAG to generate MRT blue and red next-hops, + as described below. 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. 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- @@ -1302,47 +1396,47 @@ | | | | ^ | | | | V | | 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 + Figure 22 - As an example consider the situation depicted in Figure 21. Node C + As an example consider the situation depicted in Figure 22. 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. 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. + MRT-Red next-hop, a packet on MRT-Red will use path C-D-F. -5.6.4. Generalizing for a graph that isn't 2-connected +5.7.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 + Section 5.7.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: 1. Only nodes in a common block with X should be explored in the increasing-SPF and decreasing-SPF. @@ -1362,104 +1456,99 @@ 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 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. + Section 5.7.5. -5.6.5. Complete Algorithm to Compute MRT Next-Hops +5.7.5. Complete Algorithm to Compute MRT Next-Hops The complete algorithm to compute MRT Next-Hops for a particular - router X is given in Figure 22. In addition to computing the MRT- + router X is given in Figure 23. In addition to computing the MRT- Blue next-hops and MRT-Red next-hops used by X to reach each node Y, the algorithm also stores an "order_proxy", which is the proper cut- vertex to reach Y if it is outside the block, and which is used later in deciding whether the MRT-Blue or the MRT-Red can provide an acceptable alternate for a particular primary next-hop. In_Common_Block(x, y) - if (((x.localroot is y.localroot) and (x.block_id is y.block_id)) + if ( (x.block_id is y.block_id)) or (x is y.localroot) or (y is x.localroot)) return true return false - Store_Results(y, direction, spf_root, store_nhs) +Store_Results(y, direction) if direction is FORWARD y.higher = true - if store_nhs y.blue_next_hops = y.next_hops if direction is REVERSE y.lower = true - if store_nhs y.red_next_hops = y.next_hops - SPF_No_Traverse_Root(spf_root, block_root, direction, store_nhs) +SPF_No_Traverse_Root(spf_root, block_root, direction) Initialize spf_heap to empty Initialize nodes' spf_metric to infinity and next_hops to empty spf_root.spf_metric = 0 insert(spf_heap, spf_root) while (spf_heap is not empty) min_node = remove_lowest(spf_heap) - Store_Results(min_node, direction, spf_root, store_nhs) + Store_Results(min_node, direction) if ((min_node is spf_root) or (min_node is not block_root)) foreach interface intf of min_node - if (((direction is FORWARD) and intf.OUTGOING) or - ((direction is REVERSE) and intf.INCOMING) and - In_Common_Block(spf_root, intf.remote_node)) + if ( ( ((direction is FORWARD) and intf.OUTGOING) or + ((direction is REVERSE) and intf.INCOMING) ) + and In_Common_Block(spf_root, intf.remote_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 insert_or_update(spf_heap, intf.remote_node) else if path_metric is 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) SetEdge(y) if y.blue_next_hops is empty and y.red_next_hops is empty - if (y.local_root != y) { + if (y.localroot != y) SetEdge(y.localroot) - } y.blue_next_hops = y.localroot.blue_next_hops y.red_next_hops = y.localroot.red_next_hops y.order_proxy = y.localroot.order_proxy Compute_MRT_NextHops(x, root) foreach node y y.higher = y.lower = false clear y.red_next_hops and y.blue_next_hops y.order_proxy = y - SPF_No_Traverse_Root(x, x.localroot, FORWARD, TRUE) - SPF_No_Traverse_Root(x, x.localroot, REVERSE, TRUE) + SPF_No_Traverse_Root(x, x.localroot, FORWARD) + SPF_No_Traverse_Root(x, x.localroot, REVERSE) // red and blue next-hops are stored to x.localroot as different // paths are found via the SPF and reverse-SPF. // Similarly any nodes whose local-root is x will have their // red_next_hops and blue_next_hops already set. // Handle nodes in the same block that aren't the local-root foreach node y if (y.IN_MRT_ISLAND and (y is not x) and - (y.localroot is x.localroot) and - ((y is x.localroot) or (x is y.localroot) or - (y.block_id is x.block_id))) + (y.block_id is x.block_id) ) if y.higher y.red_next_hops = x.localroot.red_next_hops else if y.lower y.blue_next_hops = x.localroot.blue_next_hops else y.blue_next_hops = x.localroot.red_next_hops y.red_next_hops = x.localroot.blue_next_hops // Inherit next-hops and order_proxies to other components if x is not root @@ -1467,41 +1556,41 @@ root.red_next_hops = x.localroot.red_next_hops root.order_proxy = x.localroot foreach node y if (y is not root) and (y is not x) and y.IN_MRT_ISLAND SetEdge(y) max_block_id = 0 Assign_Block_ID(root, max_block_id) Compute_MRT_NextHops(x, root) - Figure 22 + Figure 23 -5.7. Identify MRT alternates +5.8. Identify MRT alternates At this point, a computing router S knows its MRT-Blue next-hops and MRT-Red next-hops for each destination in the MRT Island. The primary next-hops along the SPT are also known. It remains to determine for each primary next-hop to a destination D, which of the MRTs avoids the primary next-hop node F. This computation depends upon data set in Compute_MRT_NextHops such as each node y's y.blue_next_hops, y.red_next_hops, y.order_proxy, y.higher, y.lower and topo_orders. Recall that any router knows only which are the nodes greater and lesser than itself, but it cannot decide the relation between any two given nodes easily; that is why we need topological ordering. For each primary next-hop node F to each destination D, S can call Select_Alternates(S, D, F, primary_intf) to determine whether to use the MRT-Blue next-hops as the alternate next-hop(s) for that primary next hop or to use the MRT-Red next-hops. The algorithm is given in - Figure 23 and discussed afterwards. + Figure 24 and discussed afterwards. Select_Alternates_Internal(S, D, F, primary_intf, D_lower, D_higher, D_topo_order) //When D==F, we can do only link protection if ((D is F) or (D.order_proxy is F)) if an MRT doesn't use primary_intf indicate alternate is not node-protecting return that MRT color else // parallel links are cut-links @@ -1520,23 +1609,23 @@ return USE_BLUE if (F.lower and F.higher) if D_lower return USE_RED else if D_higher return USE_BLUE else if primary_intf.OUTGOING and primary_intf.INCOMING return AVOID_LINK_ON_BLUE - if primary_intf.OUTGOING is true + if primary_intf.OUTGOING return USE_BLUE - if primary_intf.INCOMING is true + if primary_intf.INCOMING return USE_RED if D_higher if F.higher if F.topo_order < D_topo_order return USE_RED else return USE_BLUE else if F.lower return USE_BLUE @@ -1565,21 +1654,21 @@ D_lower = D.order_proxy.lower D_higher = D.order_proxy.higher D_topo_order = D.order_proxy.topo_order else D_lower = D.lower D_higher = D.higher D_topo_order = D.topo_order return Select_Alternates_Internal(S, D, F, primary_intf, D_lower, D_higher, D_topo_order) - Figure 23 + Figure 24 If either D>>S>>F or D<>D (ii) F<>G, we need to compare H.topo_order and D.topo_order. Since D.topo_order>H.topo_order, D must be not smaller than 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. [E]<-[D]<-[H]<-[J] | ^ ^ ^ V | | | [R] [C] [G]->[I] @@ -1640,26 +1728,26 @@ Blue, first decreasing then increasing, path is selected. [E]<-[D]<-[H]<-[J] | ^ ^ ^ V | | | [R] [C] [G]->[I] | ^ ^ ^ V | | | [A]->[B]->[F]---| - (a) + (a)ADAG rooted at R for a 2-connected graph - Figure 24 + Figure 25 -5.8. Finding FRR Next-Hops for Proxy-Nodes +5.9. Finding FRR Next-Hops for Proxy-Nodes As discussed in Section 10.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- nodes. An example case is for a router that is not part of that local MRT Island, when there is only partial MRT support in the domain. A first incorrect and naive approach to handling proxy-nodes, which cannot be transited, is to simply add these proxy-nodes to the graph @@ -1760,29 +1848,29 @@ 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 + Figure 26 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 + the available nodes that are described in Section 5.7 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 >> 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]. @@ -1811,21 +1899,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 [I-D.ietf-rtgwg-remote-lfa]. 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 26 shows the + focusing on coverage and alternate path length. Figure 27 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 | @@ -1848,38 +1936,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 26 + Figure 27 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 27). In this table, + for one topology using this approach ( Figure 28). 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. @@ -1887,45 +1975,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 27 + Figure 28 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 27, the + path length. As shown in the last three columns of Figure 28, the hopcount-based alternate path lengths for topology T208 are fairly well-behaved. - Figure 28, Figure 29, Figure 30, and Figure 31 present the hopcount- + Figure 29, Figure 30, Figure 31, and Figure 32 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 28 having - the smallest topologies and Figure 31 having the largest topologies. + topologies, as measured by the number of nodes, with Figure 29 having + the smallest topologies and Figure 32 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 @@ -2000,21 +2088,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 28 + Figure 29 +-------------------------------------------------------------------+ | | 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| +------------------------------+---+---+---+---+---+---+---+---+----+ @@ -2047,21 +2135,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 29 + Figure 30 +-------------------------------------------------------------------+ | | 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| +------------------------------+---+---+---+---+---+---+---+---+----+ @@ -2094,21 +2182,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 30 + Figure 31 +-------------------------------------------------------------------+ | | 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| +------------------------------+---+---+---+---+---+---+---+---+----+ @@ -2134,21 +2222,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 31 + Figure 32 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 @@ -2162,21 +2250,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 32 for a subset + those three choices of GADAG root are shown in Figure 33 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 @@ -2232,21 +2320,21 @@ | 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 32 + Figure 33 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 @@ -2268,72 +2356,79 @@ 12. Security Considerations This architecture is not currently believed to introduce new security concerns. 13. References 13.1. Normative References [I-D.ietf-rtgwg-mrt-frr-architecture] - 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. + 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. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 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 IJ. - Wijnands, "LDP Extensions to Support Maximally Redundant - Trees", draft-atlas-mpls-ldp-mrt-01 (work in progress), - July 2014. + [I-D.farkas-isis-pcr] + Farkas, J., Bragg, N., Unbehagen, P., Parsons, G., and P. + Ashwood-Smith, "IS-IS Path Computation and Reservation", + draft-farkas-isis-pcr-01 (work in progress), December + 2014. - [I-D.atlas-ospf-mrt] - 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-isis-mrt] + 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-ietf-isis-mrt-00 (work in progress), February 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. + + [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. [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-07 (work in progress), January 2015. + manageability-08 (work in progress), March 2015. [I-D.ietf-rtgwg-remote-lfa] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. - So, "Remote Loop-Free Alternate Fast Re-Route", draft- - ietf-rtgwg-remote-lfa-10 (work in progress), January 2015. - - [I-D.li-isis-mrt] - 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. + So, "Remote Loop-Free Alternate (LFA) Fast Re-Route + (FRR)", draft-ietf-rtgwg-remote-lfa-11 (work in progress), + January 2015. [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, @@ -2350,20 +2445,24 @@ Enyedi, G., Retvari, G., and A. Csaszar, "On Finding Maximally Redundant Trees in Strictly Linear Time", IEEE Symposium on Computers and Comunications (ISCC) , 2009, . [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. McPherson, "OSPF Stub Router Advertisement", RFC 3137, June 2001. + [RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi + Topology (MT) Routing in Intermediate System to + Intermediate Systems (IS-ISs)", RFC 5120, February 2008. + [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast Reroute: Loop-Free Alternates", RFC 5286, September 2008. [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC 5714, January 2010. [RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free Alternate (LFA) Applicability in Service Provider (SP) Networks", RFC 6571, June 2012. @@ -2404,21 +2503,21 @@ UNDIRECTED) already specified for each interface. Mod_SPF(spf_root, block_root) Initialize spf_heap to empty Initialize nodes' spf_metric to infinity spf_root.spf_metric = 0 insert(spf_heap, spf_root) found_in_gadag = false while (spf_heap is not empty) and (found_in_gadag is false) min_node = remove_lowest(spf_heap) - if min_node.IN_GADAG is true + if min_node.IN_GADAG found_in_gadag = true else foreach interface intf of min_node if ((intf.OUTGOING or intf.UNDIRECTED) and ((intf.remote_node.localroot is block_root) or (intf.remote_node is block_root)) and (intf.remote_node is not TEMP_UNUSABLE) and (intf is not TEMP_UNUSABLE)) path_metric = min_node.spf_metric + intf.metric if path_metric < intf.remote_node.spf_metric @@ -2441,27 +2540,27 @@ 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 33: Modified SPF for GADAG computation + Figure 34: 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 + 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 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 @@ -2504,58 +2603,58 @@ 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 34: Algorithm to assign links of an ear direction + Figure 35: 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, 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 - was seen in Section 5.6. After any ear gets computed, we traverse + was seen in Section 5.7. 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 insert(intf,ordered_intfs_tree) check_if_block_has_ear(x,block_id) block_has_ear = false for all interfaces of x - if (intf.remote_node.block_id == block_id) && - (intf.remote_node.IN_GADAG is true) + if ( (intf.remote_node.block_id == block_id) && + intf.remote_node.IN_GADAG ) block_has_ear = true return block_has_ear Construct_GADAG_via_SPF(topology, root) Compute_Localroot (root,root) Assign_Block_ID(root,0) root.IN_GADAG = true add_eligible_interfaces_of_node(ordered_intfs_tree,root) while ordered_intfs_tree is not empty cand_intf = remove_lowest(ordered_intfs_tree) @@ -2585,21 +2684,21 @@ 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 35: SPF-based GADAG algorithm + Figure 36: 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 @@ -2614,21 +2713,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 36 + The entire algorithm is shown below in Figure 37 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 @@ -2664,21 +2763,21 @@ 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 36: Hybrid GADAG algorithm + Figure 37: Hybrid GADAG algorithm Authors' Addresses Gabor Sandor Enyedi (editor) Ericsson Konyves Kalman krt 11 Budapest 1097 Hungary Email: Gabor.Sandor.Enyedi@ericsson.com