idnits 2.17.1 draft-ietf-rtgwg-mrt-frr-algorithm-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The abstract seems to contain references ([I-D.ietf-rtgwg-mrt-frr-architecture]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. == There are 19 instances of lines with non-RFC2606-compliant FQDNs in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords -- however, there's a paragraph with a matching beginning. Boilerplate error? (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- The document date (July 4, 2014) is 3556 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'R' is mentioned on line 1645, but not defined == Missing Reference: 'F' is mentioned on line 677, but not defined == Missing Reference: 'C' is mentioned on line 1645, but not defined == Missing Reference: 'G' is mentioned on line 1645, but not defined == Missing Reference: 'E' is mentioned on line 332, but not defined == Missing Reference: 'D' is mentioned on line 677, but not defined == Missing Reference: 'J' is mentioned on line 172, but not defined == Missing Reference: 'A' is mentioned on line 332, but not defined == Missing Reference: 'B' is mentioned on line 178, but not defined == Missing Reference: 'H' is mentioned on line 1219, but not defined == Missing Reference: 'K' is mentioned on line 677, but not defined == Missing Reference: 'N' is mentioned on line 677, but not defined == Missing Reference: 'X' is mentioned on line 1219, but not defined == Missing Reference: 'Y' is mentioned on line 1219, but not defined == Missing Reference: 'R-small' is mentioned on line 1178, but not defined == Missing Reference: 'R-great' is mentioned on line 1194, but not defined == Missing Reference: 'I' is mentioned on line 1645, but not defined == Unused Reference: 'I-D.atlas-mpls-ldp-mrt' is defined on line 2297, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-rtgwg-ipfrr-notvia-addresses' is defined on line 2308, but no explicit reference was found in the text == Unused Reference: 'LFARevisited' is defined on line 2336, but no explicit reference was found in the text == Unused Reference: 'LightweightNotVia' is defined on line 2343, but no explicit reference was found in the text == Unused Reference: 'RFC3137' is defined on line 2356, but no explicit reference was found in the text == Unused Reference: 'RFC5286' is defined on line 2360, but no explicit reference was found in the text == Unused Reference: 'RFC5714' is defined on line 2363, but no explicit reference was found in the text == Unused Reference: 'RFC6571' is defined on line 2366, but no explicit reference was found in the text -- No information found for draft-rtgwg-mrt-frr-architecture - is the name correct? -- Possible downref: Normative reference to a draft: ref. 'I-D.ietf-rtgwg-mrt-frr-architecture' == Outdated reference: A later version (-03) exists of draft-atlas-mpls-ldp-mrt-01 == Outdated reference: A later version (-03) exists of draft-atlas-ospf-mrt-02 == Outdated reference: A later version (-11) exists of draft-ietf-rtgwg-lfa-manageability-03 == Outdated reference: A later version (-11) exists of draft-ietf-rtgwg-remote-lfa-06 == Outdated reference: A later version (-02) exists of draft-li-isis-mrt-01 -- Obsolete informational reference (is this intentional?): RFC 3137 (Obsoleted by RFC 6987) Summary: 1 error (**), 0 flaws (~~), 33 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Routing Area Working Group G. Enyedi, Ed. 3 Internet-Draft A. Csaszar 4 Intended status: Standards Track Ericsson 5 Expires: January 5, 2015 A. Atlas, Ed. 6 C. Bowers 7 Juniper Networks 8 A. Gopalan 9 University of Arizona 10 July 4, 2014 12 Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- 13 Reroute 14 draft-ietf-rtgwg-mrt-frr-algorithm-01 16 Abstract 18 A complete solution for IP and LDP Fast-Reroute using Maximally 19 Redundant Trees is presented in [I-D.ietf-rtgwg-mrt-frr- 20 architecture]. This document defines the associated MRT Lowpoint 21 algorithm that is used in the default MRT profile to compute both the 22 necessary Maximally Redundant Trees with their associated next-hops 23 and the alternates to select for MRT-FRR. 25 Status of This Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at http://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on January 5, 2015. 42 Copyright Notice 44 Copyright (c) 2014 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (http://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 Table of Contents 59 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 60 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 5 61 3. Terminology and Definitions . . . . . . . . . . . . . . . . . 5 62 4. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 7 63 4.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 7 64 4.2. Finding an Ear and the Correct Direction . . . . . . . . 9 65 4.3. Low-Point Values and Their Uses . . . . . . . . . . . . . 11 66 4.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 15 67 4.5. Determining Local-Root and Assigning Block-ID . . . . . . 17 68 5. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 19 69 5.1. MRT Island Identification . . . . . . . . . . . . . . . . 20 70 5.2. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21 71 5.3. Initialization . . . . . . . . . . . . . . . . . . . . . 21 72 5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint 73 inheritance . . . . . . . . . . . . . . . . . . . . . . . 22 74 5.5. Augmenting the GADAG by directing all links . . . . . . . 24 75 5.6. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 26 76 5.6.1. MRT next-hops to all nodes partially ordered with 77 respect to the computing node . . . . . . . . . . . . 27 78 5.6.2. MRT next-hops to all nodes not partially ordered with 79 respect to the computing node . . . . . . . . . . . . 28 80 5.6.3. Computing Redundant Tree next-hops in a 2-connected 81 Graph . . . . . . . . . . . . . . . . . . . . . . . . 29 82 5.6.4. Generalizing for a graph that isn't 2-connected . . . 30 83 5.6.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 31 84 5.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 33 85 5.8. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 37 86 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 40 87 7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 40 88 7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 41 89 8. Implementation Status . . . . . . . . . . . . . . . . . . . . 51 90 9. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 51 91 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 51 92 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 51 93 12. Security Considerations . . . . . . . . . . . . . . . . . . . 51 94 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 51 95 13.1. Normative References . . . . . . . . . . . . . . . . . . 51 96 13.2. Informative References . . . . . . . . . . . . . . . . . 51 98 Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 53 99 Appendix B. Option 3: Computing GADAG using a hybrid method . . 58 100 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 60 102 1. Introduction 104 MRT Fast-Reroute requires that packets can be forwarded not only on 105 the shortest-path tree, but also on two Maximally Redundant Trees 106 (MRTs), referred to as the MRT-Blue and the MRT-Red. A router which 107 experiences a local failure must also have pre-determined which 108 alternate to use. This document defines how to compute these three 109 things for use in MRT-FRR and describes the algorithm design 110 decisions and rationale. The algorithm is based on those presented 111 in [MRTLinear] and expanded in [EnyediThesis]. The MRT Lowpoint 112 algorithm is required for implementation when the default MRT profile 113 is implemented. 115 Just as packets routed on a hop-by-hop basis require that each router 116 compute a shortest-path tree which is consistent, it is necessary for 117 each router to compute the MRT-Blue next-hops and MRT-Red next-hops 118 in a consistent fashion. This document defines the MRT Lowpoint 119 algorithm to be used as a standard in the default MRT profile for 120 MRT-FRR. 122 As now, a router's FIB will contain primary next-hops for the current 123 shortest-path tree for forwarding traffic. In addition, a router's 124 FIB will contain primary next-hops for the MRT-Blue for forwarding 125 received traffic on the MRT-Blue and primary next-hops for the MRT- 126 Red for forwarding received traffic on the MRT-Red. 128 What alternate next-hops a point-of-local-repair (PLR) selects need 129 not be consistent - but loops must be prevented. To reduce 130 congestion, it is possible for multiple alternate next-hops to be 131 selected; in the context of MRT alternates, each of those alternate 132 next-hops would be equal-cost paths. 134 This document defines an algorithm for selecting an appropriate MRT 135 alternate for consideration. Other alternates, e.g. LFAs that are 136 downstream paths, may be prefered when available and that policy- 137 based alternate selection process[I-D.ietf-rtgwg-lfa-manageability] 138 is not captured in this document. 140 [E]---[D]---| [E]<--[D]<--| [E]-->[D] 141 | | | | ^ | | 142 | | | V | | V 143 [R] [F] [C] [R] [F] [C] [R] [F] [C] 144 | | | ^ ^ | | 145 | | | | | V | 146 [A]---[B]---| [A]-->[B] [A]---[B]<--| 148 (a) (b) (c) 149 a 2-connected graph MRT-Blue towards R MRT-Red towards R 151 Figure 1 153 Algorithms for computing MRTs can handle arbitrary network topologies 154 where the whole network graph is not 2-connected, as in Figure 2, as 155 well as the easier case where the network graph is 2-connected 156 (Figure 1). Each MRT is a spanning tree. The pair of MRTs provide 157 two paths from every node X to the root of the MRTs. Those paths 158 share the minimum number of nodes and the minimum number of links. 159 Each such shared node is a cut-vertex. Any shared links are cut- 160 links. 162 [E]---[D]---| |---[J] 163 | | | | | 164 | | | | | 165 [R] [F] [C]---[G] | 166 | | | | | 167 | | | | | 168 [A]---[B]---| |---[H] 170 (a) a graph that isn't 2-connected 172 [E]<--[D]<--| [J] [E]-->[D]---| |---[J] 173 | ^ | | | | | ^ 174 V | | | V V V | 175 [R] [F] [C]<--[G] | [R] [F] [C]<--[G] | 176 ^ ^ ^ | ^ | | | 177 | | | V | V | | 178 [A]-->[B]---| |---[H] [A]<--[B]<--| [H] 180 (b) MRT-Blue towards R (c) MRT-Red towards R 182 Figure 2 184 2. Requirements Language 186 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 187 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 188 document are to be interpreted as described in [RFC2119] 190 3. Terminology and Definitions 192 network graph: A graph that reflects the network topology where all 193 links connect exactly two nodes and broadcast links have been 194 transformed into a pseudo-node representation (e.g. in OSPF, 195 viewing a Network LSA as representing a pseudo-noe). 197 Redundant Trees (RT): A pair of trees where the path from any node X 198 to the root R on the first tree is node-disjoint with the path 199 from the same node X to the root along the second tree. These can 200 be computed in 2-connected graphs. 202 Maximally Redundant Trees (MRT): A pair of trees where the path 203 from any node X to the root R along the first tree and the path 204 from the same node X to the root along the second tree share the 205 minimum number of nodes and the minimum number of links. Each 206 such shared node is a cut-vertex. Any shared links are cut-links. 207 Any RT is an MRT but many MRTs are not RTs. 209 MRT Island: From the computing router, the set of routers that 210 support a particular MRT profile and are connected. 212 MRT-Red: MRT-Red is used to describe one of the two MRTs; it is 213 used to describe the associated forwarding topology and MT-ID. 214 Specifically, MRT-Red is the decreasing MRT where links in the 215 GADAG are taken in the direction from a higher topologically 216 ordered node to a lower one. 218 MRT-Blue: MRT-Blue is used to describe one of the two MRTs; it is 219 used to describe the associated forwarding topology and MT-ID. 220 Specifically, MRT-Blue is the increasing MRT where links in the 221 GADAG are taken in the direction from a lower topologically 222 ordered node to a higher one. 224 cut-vertex: A vertex whose removal partitions the network. 226 cut-link: A link whose removal partitions the network. A cut-link 227 by definition must be connected between two cut-vertices. If 228 there are multiple parallel links, then they are referred to as 229 cut-links in this document if removing the set of parallel links 230 would partition the network. 232 2-connected: A graph that has no cut-vertices. This is a graph 233 that requires two nodes to be removed before the network is 234 partitioned. 236 spanning tree: A tree containing links that connects all nodes in 237 the network graph. 239 back-edge: In the context of a spanning tree computed via a depth- 240 first search, a back-edge is a link that connects a descendant of 241 a node x with an ancestor of x. 243 2-connected cluster: A maximal set of nodes that are 2-connected. 244 In a network graph with at least one cut-vertex, there will be 245 multiple 2-connected clusters. 247 block: Either a 2-connected cluster, a cut-link, or an isolated 248 vertex. 250 DAG: Directed Acyclic Graph - a digraph containing no directed 251 cycle. 253 ADAG: Almost Directed Acyclic Graph - a digraph that can be 254 transformed into a DAG with removing a single node (the root 255 node). 257 partial ADAG: A subset of an ADAG that doesn't yet contain all the 258 nodes in the block. A partial ADAG is created during the MRT 259 algorithm and then expanded until all nodes in the block are 260 included and it is an ADAG. 262 GADAG: Generalized ADAG - a digraph, which has only ADAGs as all of 263 its blocks. The root of such a block is the node closest to the 264 global root (e.g. with uniform link costs). 266 DFS: Depth-First Search 268 DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS- 269 tree path from the DFS root to x. 271 DFS descendant: A node n is a DFS descendant of x if x is on the 272 DFS-tree path from the DFS root to n. 274 ear: A path along not-yet-included-in-the-GADAG nodes that starts 275 at a node that is already-included-in-the-GADAG and that ends at a 276 node that is already-included-in-the-GADAG. The starting and 277 ending nodes may be the same node if it is a cut-vertex. 279 X >> Y or Y << X: Indicates the relationship between X and Y in a 280 partial order, such as found in a GADAG. X >> Y means that X is 281 higher in the partial order than Y. Y << X means that Y is lower 282 in the partial order than X. 284 X > Y or Y < X: Indicates the relationship between X and Y in the 285 total order, such as found via a topological sort. X > Y means 286 that X is higher in the total order than Y. Y < X means that Y is 287 lower in the total order than X. 289 proxy-node: A node added to the network graph to represent a multi- 290 homed prefix or routers outside the local MRT-fast-reroute- 291 supporting island of routers. The key property of proxy-nodes is 292 that traffic cannot transit them. 294 UNDIRECTED: In the GADAG, each link is marked as OUTGOING, INCOMING 295 or both. Until the directionality of the link is determined, the 296 link is marked as UNDIRECTED to indicate that its direction hasn't 297 been determined. 299 OUTGOING: In the GADAG, each link is marked as OUTGOING, INCOMING 300 or both. A link marked as OUTGOING has direction from the 301 interface's router to the remote end. 303 INCOMING: In the GADAG, each link is marked as OUTGOING, INCOMING 304 or both. A link marked as INCOMING has direction from the remote 305 end to the interface's router. 307 4. Algorithm Key Concepts 309 There are five key concepts that are critical for understanding the 310 MRT Lowpoint algorithm and other algorithms for computing MRTs. The 311 first is the idea of partially ordering the nodes in a network graph 312 with regard to each other and to the GADAG root. The second is the 313 idea of finding an ear of nodes and adding them in the correct 314 direction. The third is the idea of a Low-Point value and how it can 315 be used to identify cut-vertices and to find a second path towards 316 the root. The fourth is the idea that a non-2-connected graph is 317 made up of blocks, where a block is a 2-connected cluster, a cut-link 318 or an isolated node. The fifth is the idea of a local-root for each 319 node; this is used to compute ADAGs in each block. 321 4.1. Partial Ordering for Disjoint Paths 323 Given any two nodes X and Y in a graph, a particular total order 324 means that either X < Y or X > Y in that total order. An example 325 would be a graph where the nodes are ranked based upon their unique 326 IP loopback addresses. In a partial order, there may be some nodes 327 for which it can't be determined whether X << Y or X >> Y. A partial 328 order can be captured in a directed graph, as shown in Figure 3. In 329 a graphical representation, a link directed from X to Y indicates 330 that X is a neighbor of Y in the network graph and X << Y. 332 [A]<---[R] [E] R << A << B << C << D << E 333 | ^ R << A << B << F << G << H << D << E 334 | | 335 V | Unspecified Relationships: 336 [B]--->[C]--->[D] C and F 337 | ^ C and G 338 | | C and H 339 V | 340 [F]--->[G]--->[H] 342 Figure 3: Directed Graph showing a Partial Order 344 To compute MRTs, the root of the MRTs is at both the very bottom and 345 the very top of the partial ordering. This means that from any node 346 X, one can pick nodes higher in the order until the root is reached. 347 Similarly, from any node X, one can pick nodes lower in the order 348 until the root is reached. For instance, in Figure 4, from G the 349 higher nodes picked can be traced by following the directed links and 350 are H, D, E and R. Similarly, from G the lower nodes picked can be 351 traced by reversing the directed links and are F, B, A, and R. A 352 graph that represents this modified partial order is no longer a DAG; 353 it is termed an Almost DAG (ADAG) because if the links directed to 354 the root were removed, it would be a DAG. 356 [A]<---[R]<---[E] R << A << B << C << R 357 | ^ ^ R << A << B << C << D << E << R 358 | | | R << A << B << F << G << H << D << E << R 359 V | | 360 [B]--->[C]--->[D] Unspecified Relationships: 361 | ^ C and F 362 | | C and G 363 V | C and H 364 [F]--->[G]--->[H] 366 Figure 4: ADAG showing a Partial Order with R lowest and highest 368 Most importantly, if a node Y >> X, then Y can only appear on the 369 increasing path from X to the root and never on the decreasing path. 371 Similarly, if a node Z << X, then Z can only appear on the decreasing 372 path from X to the root and never on the inceasing path. 374 When following the increasing paths, it is possible to pick multiple 375 higher nodes and still have the certainty that those paths will be 376 disjoint from the decreasing paths. E.g. in the previous example 377 node B has multiple possibilities to forward packets along an 378 increasing path: it can either forward packets to C or F. 380 4.2. Finding an Ear and the Correct Direction 382 For simplicity, the basic idea of creating a GADAG by adding ears is 383 described assuming that the network graph is a single 2-connected 384 cluster so that an ADAG is sufficient. Generalizing to multiple 385 blocks is done by considering the block-roots instead of the GADAG 386 root - and the actual algorithm is given in Section 5.4. 388 In order to understand the basic idea of finding an ADAG, first 389 suppose that we have already a partial ADAG, which doesn't contain 390 all the nodes in the block yet, and we want to extend it to cover all 391 the nodes. Suppose that we find a path from a node X to Y such that 392 X and Y are already contained by our partial ADAG, but all the 393 remaining nodes along the path are not added to the ADAG yet. We 394 refer to such a path as an ear. 396 Recall that our ADAG is closely related to a partial order. More 397 precisely, if we remove root R, the remaining DAG describes a partial 398 order of the nodes. If we suppose that neither X nor Y is the root, 399 we may be able to compare them. If one of them is definitely lesser 400 with respect to our partial order (say X<B---| A-->B---| 412 (a) (b) (c) 414 (a) A 2-connected graph 415 (b) Partial ADAG (C is not included) 416 (c) Resulting ADAG after adding path (or ear) B-C-D 418 Figure 5 420 In this partial ADAG, node C is not yet included. However, we can 421 find path B-C-D, where both endpoints are contained by this partial 422 ADAG (we say those nodes are "ready" in the following text), and the 423 remaining node (node C) is not contained yet. If we remove R, the 424 remaining DAG defines a partial order, and with respect to this 425 partial order we can say that B<C and C->D are added). If 427 B >> D, we would add the same path in reverse direction. 429 If in the partial order where an ear's two ends are X and Y, X << Y, 430 then there must already be a directed path from X to Y in the ADAG. 431 The ear must be added in a direction such that it doesn't create a 432 cycle; therefore the ear must go from X to Y. 434 In the case, when X and Y are not ordered with each other, we can 435 select either direction for the ear. We have no restriction since 436 neither of the directions can result in a cycle. In the corner case 437 when one of the endpoints of an ear, say X, is the root (recall that 438 the two endpoints must be different), we could use both directions 439 again for the ear because the root can be considered both as smaller 440 and as greater than Y. However, we strictly pick that direction in 441 which the root is lower than Y. The logic for this decision is 442 explained in Section 5.6 444 A partial ADAG is started by finding a cycle from the root R back to 445 itself. This can be done by selecting a non-ready neighbor N of R 446 and then finding a path from N to R that doesn't use any links 447 between R and N. The direction of the cycle can be assigned either 448 way since it is starting the ordering. 450 Once a partial ADAG is already present, it will always have a node 451 that is not the root R in it. As a brief proof that a partial ADAG 452 can always have ears added to it: just select a non-ready neighbor N 453 of a ready node Q, such that Q is not the root R, find a path from N 454 to the root R in the graph with Q removed. This path is an ear where 455 the first node of the ear is Q, the next is N, then the path until 456 the first ready node the path reached (that ready node is the other 457 endpoint of the path). Since the graph is 2-connected, there must be 458 a path from N to R without Q. 460 It is always possible to select a non-ready neighbor N of a ready 461 node Q so that Q is not the root R. Because the network is 462 2-connected, N must be connected to two different nodes and only one 463 can be R. Because the initial cycle has already been added to the 464 ADAG, there are ready nodes that are not R. Since the graph is 465 2-connected, while there are non-ready nodes, there must be a non- 466 ready neighbor N of a ready node that is not R. 468 Generic_Find_Ears_ADAG(root) 469 Create an empty ADAG. Add root to the ADAG. 470 Mark root as IN_GADAG. 471 Select an arbitrary cycle containing root. 472 Add the arbitrary cycle to the ADAG. 473 Mark cycle's nodes as IN_GADAG. 474 Add cycle's non-root nodes to process_list. 475 while there exists connected nodes in graph that are not IN_GADAG 476 Select a new ear. Let its endpoints be X and Y. 477 if Y is root or (Y << X) 478 add the ear towards X to the ADAG 479 else // (a) X is root or (b)X << Y or (c) X, Y not ordered 480 Add the ear towards Y to the ADAG 482 Figure 6: Generic Algorithm to find ears and their direction in 483 2-connected graph 485 Algorithm Figure 6 merely requires that a cycle or ear be selected 486 without specifying how. Regardless of the way of selecting the path, 487 we will get an ADAG. The method used for finding and selecting the 488 ears is important; shorter ears result in shorter paths along the 489 MRTs. The MRT Lowpoint algorithm's method using Low-Point 490 Inheritance is defined in Section 5.4. Other methods are described 491 in the Appendices (Appendix A and Appendix B). 493 As an example, consider Figure 5 again. First, we select the 494 shortest cycle containing R, which can be R-A-B-F-D-E (uniform link 495 costs were assumed), so we get to the situation depicted in Figure 5 496 (b). Finally, we find a node next to a ready node; that must be node 497 C and assume we reached it from ready node B. We search a path from 498 C to R without B in the original graph. The first ready node along 499 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 501 this point. 503 4.3. Low-Point Values and Their Uses 505 A basic way of computing a spanning tree on a network graph is to run 506 a depth-first-search, such as given in Figure 7. This tree has the 507 important property that if there is a link (x, n), then either n is a 508 DFS ancestor of x or n is a DFS descendant of x. In other words, 509 either n is on the path from the root to x or x is on the path from 510 the root to n. 512 global_variable: dfs_number 514 DFS_Visit(node x, node parent) 515 D(x) = dfs_number 516 dfs_number += 1 517 x.dfs_parent = parent 518 for each link (x, w) 519 if D(w) is not set 520 DFS_Visit(w, x) 522 Run_DFS(node root) 523 dfs_number = 0 524 DFS_Visit(root, NONE) 526 Figure 7: Basic Depth-First Search algorithm 528 Given a node x, one can compute the minimal DFS number of the 529 neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the 530 earliest attachment point neighbouring x. What is interesting, 531 though, is what is the earliest attachment point from x and x's 532 descendants. This is what is determined by computing the Low-Point 533 value. 535 In order to compute the low point value, the network is traversed 536 using DFS and the vertices are numbered based on the DFS walk. Let 537 this number be represented as DFS(x). All the edges that lead to 538 already visited nodes during DFS walk are back-edges. The back-edges 539 are important because they give information about reachability of a 540 node via another path. 542 The low point number is calculated by finding: 544 Low(x) = Minimum of ( (DFS(x), 545 Lowest DFS(n, x->n is a back-edge), 546 Lowest Low(n, x->n is tree edge in DFS walk) ). 548 A detailed algorithm for computing the low-point value is given in 549 Figure 8. Figure 9 illustrates how the lowpoint algorithm applies to 550 a example graph. 552 global_variable: dfs_number 554 Lowpoint_Visit(node x, node parent, interface p_to_x) 555 D(x) = dfs_number 556 L(x) = D(x) 557 dfs_number += 1 558 x.dfs_parent = parent 559 x.dfs_parent_intf = p_to_x 560 x.lowpoint_parent = NONE 561 for each interface intf of x 562 if D(intf.remote_node) is not set 563 Lowpoint_Visit(intf.remote_node, x, intf) 564 if L(intf.remote_node) < L(x) 565 L(x) = L(intf.remote_node) 566 x.lowpoint_parent = intf.remote_node 567 x.lowpoint_parent_intf = intf 568 else if intf.remote_node is not parent 569 if D(intf.remote_node) < L(x) 570 L(x) = D(intf.remote_node) 571 x.lowpoint_parent = intf.remote_node 572 x.lowpoint_parent_intf = intf 574 Run_Lowpoint(node root) 575 dfs_number = 0 576 Lowpoint_Visit(root, NONE, NONE) 578 Figure 8: Computing Low-Point value 580 [E]---| [J]-------[I] [P]---[O] 581 | | | | | | 582 | | | | | | 583 [R] [D]---[C]--[F] [H]---[K] [N] 584 | | | | | | 585 | | | | | | 586 [A]--------[B] [G]---| [L]---[M] 588 (a) a non-2-connected graph 590 [E]----| [J]---------[I] [P]------[O] 591 (5, ) | (10, ) (9, ) (16, ) (15, ) 592 | | | | | | 593 | | | | | | 594 [R] [D]---[C]---[F] [H]----[K] [N] 595 (0, ) (4, ) (3, ) (6, ) (8, ) (11, ) (14, ) 596 | | | | | | 597 | | | | | | 598 [A]---------[B] [G]----| [L]------[M] 599 (1, ) (2, ) (7, ) (12, ) (13, ) 601 (b) with DFS values assigned (D(x), L(x)) 603 [E]----| [J]---------[I] [P]------[O] 604 (5,0) | (10,3) (9,3) (16,11) (15,11) 605 | | | | | | 606 | | | | | | 607 [R] [D]---[C]---[F] [H]----[K] [N] 608 (0, ) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11) 609 | | | | | | 610 | | | | | | 611 [A]---------[B] [G]----| [L]------[M] 612 (1,0) (2,0) (7,3) (12,11) (13,11) 614 (c) with low-point values assigned (D(x), L(x)) 616 Figure 9: Example lowpoint value computation 618 From the low-point value and lowpoint parent, there are three very 619 useful things which motivate our computation. 621 First, if there is a child c of x such that L(c) >= D(x), then there 622 are no paths in the network graph that go from c or its descendants 623 to an ancestor of x - and therefore x is a cut-vertex. In Figure 9, 624 this can be seen by looking at the DFS children of C. C has two 625 children - D and F and L(F) = 3 = D(C) so it is clear that C is a 626 cut-vertex and F is in a block where C is the block's root. L(D) = 0 627 > 3 = D(C) so D has a path to the ancestors of C; in this case, D can 628 go via E to reach R. Comparing the low-point values of all a node's 629 DFS-children with the node's DFS-value is very useful because it 630 allows identification of the cut-vertices and thus the blocks. 632 Second, by repeatedly following the path given by lowpoint_parent, 633 there is a path from x back to an ancestor of x that does not use the 634 link [x, x.dfs_parent] in either direction. The full path need not 635 be taken, but this gives a way of finding an initial cycle and then 636 ears. 638 Third, as seen in Figure 9, even if L(x) < D(x), there may be a block 639 that contains both the root and a DFS-child of a node while other 640 DFS-children might be in different blocks. In this example, C's 641 child D is in the same block as R while F is not. It is important to 642 realize that the root of a block may also be the root of another 643 block. 645 4.4. Blocks in a Graph 647 A key idea for an MRT algorithm is that any non-2-connected graph is 648 made up by blocks (e.g. 2-connected clusters, cut-links, and/or 649 isolated nodes). To compute GADAGs and thus MRTs, computation is 650 done in each block to compute ADAGs or Redundant Trees and then those 651 ADAGs or Redundant Trees are combined into a GADAG or MRT. 653 [E]---| [J]-------[I] [P]---[O] 654 | | | | | | 655 | | | | | | 656 [R] [D]---[C]--[F] [H]---[K] [N] 657 | | | | | | 658 | | | | | | 659 [A]--------[B] [G]---| [L]---[M] 661 (a) A graph with four blocks that are: 662 3 2-connected clusters and a cut-link 664 [E]<--| [J]<------[I] [P]<--[O] 665 | | | ^ | ^ 666 V | V | V | 667 [R] [D]<--[C] [F] [H]<---[K] [N] 668 ^ | ^ ^ 669 | V | | 670 [A]------->[B] [G]---| [L]-->[M] 672 (b) MRT-Blue 674 [E]---| [J]-------->[I] [P]-->[O] 675 | | | 676 V V V 677 [R] [D]-->[C]<---[F] [H]<---[K] [N] 678 ^ | ^ | ^ | 679 | V | | | V 680 [A]<-------[B] [G]<--| [L]<--[M] 682 (c) MRT-Red 684 Figure 10 686 Consider the example depicted in Figure 10 (a). In this figure, a 687 special graph is presented, showing us all the ways 2-connected 688 clusters can be connected. It has four blocks: block 1 contains R, 689 A, B, C, D, E, block 2 contains C, F, G, H, I, J, block 3 contains K, 690 L, M, N, O, P, and block 4 is a cut-link containing H and K. As can 691 be observed, the first two blocks have one common node (node C) and 692 blocks 2 and 3 do not have any common node, but they are connected 693 through a cut-link that is block 4. No two blocks can have more than 694 one common node, since two blocks with at least 2 common nodes would 695 qualify as a single 2-connected cluster. 697 Moreover, observe that if we want to get from one block to another, 698 we must use a cut-vertex (the cut-vertices in this graph are C, H, 699 K), regardless of the path selected, so we can say that all the paths 700 from block 3 along the MRTs rooted at R will cross K first. This 701 observation means that if we want to find a pair of MRTs rooted at R, 702 then we need to build up a pair of RTs in block 3 with K as a root. 703 Similarly, we need to find another pair of RTs in block 2 with C as a 704 root, and finally, we need the last pair of RTs in block 1 with R as 705 a root. When all the trees are selected, we can simply combine them; 706 when a block is a cut-link (as in block 4), that cut-link is added in 707 the same direction to both of the trees. The resulting trees are 708 depicted in Figure 10 (b) and (c). 710 Similarly, to create a GADAG it is sufficient to compute ADAGs in 711 each block and connect them. 713 It is necessary, therefore, to identify the cut-vertices, the blocks 714 and identify the appropriate local-root to use for each block. 716 4.5. Determining Local-Root and Assigning Block-ID 718 Each node in a network graph has a local-root, which is the cut- 719 vertex (or root) in the same block that is closest to the root. The 720 local-root is used to determine whether two nodes share a common 721 block. 723 Compute_Localroot(node x, node localroot) 724 x.localroot = localroot 725 for each DFS child c 726 if L(c) < D(x) //x is not a cut-vertex 727 Compute_Localroot(c, x.localroot) 728 else 729 mark x as cut-vertex 730 Compute_Localroot(c, x) 732 Compute_Localroot(root, root) 734 Figure 11: A method for computing local-roots 736 There are two different ways of computing the local-root for each 737 node. The stand-alone method is given in Figure 11 and better 738 illustrates the concept; it is used by the MRT algorithms given in 739 the Appendices Appendix A and Appendix B. The MRT Lowpoint algorithm 740 computes the local-root for a block as part of computing the GADAG 741 using lowpoint inheritance; the essence of this computation is given 742 in Figure 12. 744 Get the current node, s. 745 Compute an ear(either through lowpoint inheritance 746 or by following dfs parents) from s to a ready node e. 747 (Thus, s is not e, if there is such ear.) 748 if s is e 749 for each node x in the ear that is not s 750 x.localroot = s 751 else 752 for each node x in the ear that is not s or e 753 x.localroot = e.localroot 755 Figure 12: Ear-based method for computing local-roots 757 Once the local-roots are known, two nodes X and Y are in a common 758 block if and only if one of the following three conditions apply. 760 o Y's local-root is X's local-root : They are in the same block and 761 neither is the cut-vertex closest to the root. 763 o Y's local-root is X: X is the cut-vertex closest to the root for 764 Y's block 766 o Y is X's local-root: Y is the cut-vertex closest to the root for 767 X's block 769 Once we have computed the local-root for each node in the network 770 graph, we can assign for each node, a block id that represents the 771 block in which the node is present. This computation is shown in 772 Figure 13. 774 global_var: max_block_id 776 Assign_Block_ID(x, cur_block_id) 777 x.block_id = cur_block_id 778 foreach DFS child c of x 779 if (c.local_root is x) 780 max_block_id += 1 781 Assign_Block_ID(c, max_block_id) 782 else 783 Assign_Block_ID(c, cur_block_id) 785 max_block_id = 0 786 Assign_Block_ID(root, max_block_id) 788 Figure 13: Assigning block id to identify blocks 790 5. Algorithm Sections 792 This algorithm computes one GADAG that is then used by a router to 793 determine its MRT-Blue and MRT-Red next-hops to all destinations. 794 Finally, based upon that information, alternates are selected for 795 each next-hop to each destination. The different parts of this 796 algorithm are described below. These work on a network graph after 797 its interfaces have been ordered as per Figure 14. 799 1. Compute the local MRT Island for the particular MRT Profile. 800 [See Section 5.1.] 802 2. Select the root to use for the GADAG. [See Section 5.2.] 804 3. Initialize all interfaces to UNDIRECTED. [See Section 5.3.] 806 4. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See 807 Figure 8.] 809 5. Construct the GADAG. [See Section 5.4] 811 6. Assign directions to all interfaces that are still UNDIRECTED. 812 [See Section 5.5.] 814 7. From the computing router x, compute the next-hops for the MRT- 815 Blue and MRT-Red. [See Section 5.6.] 817 8. Identify alternates for each next-hop to each destination by 818 determining which one of the blue MRT and the red MRT the 819 computing router x should select. [See Section 5.7.] 821 To ensure consistency in computation, all routers MUST order 822 interfaces identically down to the set of links with the same metric 823 to the same neighboring node. This is necessary for the DFS, where 824 the selection order of the interfaces to explore results in different 825 trees, and for computing the GADAG, where the selection order of the 826 interfaces to use to form ears can result in different GADAGs. The 827 required ordering between two interfaces from the same router x is 828 given in Figure 14. 830 Interface_Compare(interface a, interface b) 831 if a.metric < b.metric 832 return A_LESS_THAN_B 833 if b.metric < a.metric 834 return B_LESS_THAN_A 835 if a.neighbor.loopback_addr < b.neighbor.loopback_addr 836 return A_LESS_THAN_B 837 if b.neighbor.loopback_addr < a.neighbor.loopback_addr 838 return B_LESS_THAN_A 839 // Same metric to same node, so the order doesn't matter anymore for 840 // interoperability. 841 // To have a unique, consistent total order, 842 // tie-break in OSPF based on the link's linkData as 843 // distributed in an OSPF Router-LSA 844 if a.link_data < b.link_data 845 return A_LESS_THAN_B 846 return B_LESS_THAN_A 848 Figure 14: Rules for ranking multiple interfaces. Order is from low 849 to high. 851 5.1. MRT Island Identification 853 The local MRT Island for a particular MRT profile can be determined 854 by starting from the computing router in the network graph and doing 855 a breadth-first-search (BFS). The BFS explores only links that are 856 in the same area/level, are not IGP-excluded, and are not MRT- 857 ineligible. The BFS explores only nodes that are are not IGP- 858 excluded, and that support the particular MRT profile. See section 7 859 of [I-D.ietf-rtgwg-mrt-frr-architecture] for more precise definitions 860 of these criteria. 862 MRT_Island_Identification(topology, computing_rtr, profile_id, area) 863 for all routers in topology 864 rtr.IN_MRT_ISLAND = FALSE 865 computing_rtr.IN_MRT_ISLAND = TRUE 866 explore_list = { computing_rtr } 867 while (explore_list is not empty) 868 next_rtr = remove_head(explore_list) 869 for each interface in next_rtr 870 if interface is (not MRT-ineligible and not IGP-excluded 871 and in area) 872 if ((interface.remote_node supports profile_id) and 873 (interface.remote_node.IN_MRT_ISLAND is FALSE)) 874 interface.remote_node.IN_MRT_ISLAND = TRUE 875 add_to_tail(explore_list, interface.remote_node) 877 Figure 15: MRT Island Identification 879 5.2. GADAG Root Selection 881 In Section 8.3 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG 882 Root Selection Policy is described for the MRT default profile. In 883 [I-D.atlas-ospf-mrt] and [I-D.li-isis-mrt], a mechanism is given for 884 routers to advertise the GADAG Root Selection Priority and 885 consistently select a GADAG Root inside the local MRT Island. The 886 MRT Lowpoint algorithm simply requires that all routers in the MRT 887 Island MUST select the same GADAG Root; the mechanism can vary based 888 upon the MRT profile description. Before beginning computation, the 889 network graph is reduced to contain only the set of routers that 890 support the specific MRT profile whose MRTs are being computed. 892 Analysis has shown that the centrality of a router can have a 893 significant impact on the lengths of the alternate paths computed. 894 Therefore, it is RECOMMENDED that off-line analysis that considers 895 the centrality of a router be used to help determine how good a 896 choice a particular router is for the role of GADAG root. 898 5.3. Initialization 900 Before running the algorithm, there is the standard type of 901 initialization to be done, such as clearing any computed DFS-values, 902 lowpoint-values, DFS-parents, lowpoint-parents, any MRT-computed 903 next-hops, and flags associated with algorithm. 905 It is assumed that a regular SPF computation has been run so that the 906 primary next-hops from the computing router to each destination are 907 known. This is required for determining alternates at the last step. 909 Initially, all interfaces MUST be initialized to UNDIRECTED. Whether 910 they are OUTGOING, INCOMING or both is determined when the GADAG is 911 constructed and augmented. 913 It is possible that some links and nodes will be marked as unusable 914 using standard IGP mechanisms (see section 7 of 915 [I-D.ietf-rtgwg-mrt-frr-architecture]). Due to FRR manageability 916 considerations [I-D.ietf-rtgwg-lfa-manageability], it may also be 917 desirable to administratively configure some interfaces as ineligible 918 to carry MRT FRR traffic. This constraint MUST be consistently 919 flooded via the IGP [I-D.atlas-ospf-mrt] [I-D.li-isis-mrt] by the 920 owner of the interface, so that links are clearly known to be MRT- 921 ineligible and not explored or used in the MRT algorithm. In the 922 algorithm description, it is assumed that such links and nodes will 923 not be explored or used, and no more discussion is given of this 924 restriction. 926 5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance 928 As discussed in Section 4.2, it is necessary to find ears from a node 929 x that is already in the GADAG (known as IN_GADAG). Two different 930 methods are used to find ears in the algorithm. The first is by 931 going to a not IN_GADAG DFS-child and then following the chain of 932 low-point parents until an IN_GADAG node is found. The second is by 933 going to a not IN_GADAG neighbor and then following the chain of DFS 934 parents until an IN_GADAG node is found. As an ear is found, the 935 associated interfaces are marked based on the direction taken. The 936 nodes in the ear are marked as IN_GADAG. In the algorithm, first the 937 ears via DFS-children are found and then the ears via DFS-neighbors 938 are found. 940 By adding both types of ears when an IN_GADAG node is processed, all 941 ears that connect to that node are found. The order in which the 942 IN_GADAG nodes is processed is, of course, key to the algorithm. The 943 order is a stack of ears so the most recent ear is found at the top 944 of the stack. Of course, the stack stores nodes and not ears, so an 945 ordered list of nodes, from the first node in the ear to the last 946 node in the ear, is created as the ear is explored and then that list 947 is pushed onto the stack. 949 Each ear represents a partial order (see Figure 4) and processing the 950 nodes in order along each ear ensures that all ears connecting to a 951 node are found before a node higher in the partial order has its ears 952 explored. This means that the direction of the links in the ear is 953 always from the node x being processed towards the other end of the 954 ear. Additionally, by using a stack of ears, this means that any 955 unprocessed nodes in previous ears can only be ordered higher than 956 nodes in the ears below it on the stack. 958 In this algorithm that depends upon Low-Point inheritance, it is 959 necessary that every node have a low-point parent that is not itself. 960 If a node is a cut-vertex, that may not yet be the case. Therefore, 961 any nodes without a low-point parent will have their low-point parent 962 set to their DFS parent and their low-point value set to the DFS- 963 value of their parent. This assignment also properly allows an ear 964 between two cut-vertices. 966 Finally, the algorithm simultaneously computes each node's local- 967 root, as described in Figure 12. This is further elaborated as 968 follows. The local-root can be inherited from the node at the end of 969 the ear unless the end of the ear is x itself, in which case the 970 local-root for all the nodes in the ear would be x. This is because 971 whenever the first cycle is found in a block, or an ear involving a 972 bridge is computed, the cut-vertex closest to the root would be x 973 itself. In all other scenarios, the properties of lowpoint/dfs 974 parents ensure that the end of the ear will be in the same block, and 975 thus inheriting its local-root would be the correct local-root for 976 all newly added nodes. 978 The pseudo-code for the GADAG algorithm (assuming that the adjustment 979 of lowpoint for cut-vertices has been made) is shown in Figure 16. 981 Construct_Ear(x, Stack, intf, type) 982 ear_list = empty 983 cur_node = intf.remote_node 984 cur_intf = intf 985 not_done = true 987 while not_done 988 cur_intf.UNDIRECTED = false 989 cur_intf.OUTGOING = true 990 cur_intf.remote_intf.UNDIRECTED = false 991 cur_intf.remote_intf.INCOMING = true 993 if cur_node.IN_GADAG is false 994 cur_node.IN_GADAG = true 995 add_to_list_end(ear_list, cur_node) 996 if type is CHILD 997 cur_intf = cur_node.lowpoint_parent_intf 998 cur_node = cur_node.lowpoint_parent 999 else type must be NEIGHBOR 1000 cur_intf = cur_node.dfs_parent_intf 1001 cur_node = cur_node.dfs_parent 1002 else 1003 not_done = false 1005 if (type is CHILD) and (cur_node is x) 1006 //x is a cut-vertex and the local root for 1007 //the block in which the ear is computed 1008 localroot = x 1009 else 1010 // Inherit local-root from the end of the ear 1011 localroot = cur_node.localroot 1012 while ear_list is not empty 1013 y = remove_end_item_from_list(ear_list) 1014 y.localroot = localroot 1015 push(Stack, y) 1017 Construct_GADAG_via_Lowpoint(topology, root) 1018 root.IN_GADAG = true 1019 root.localroot = root 1020 Initialize Stack to empty 1021 push root onto Stack 1022 while (Stack is not empty) 1023 x = pop(Stack) 1024 foreach interface intf of x 1025 if ((intf.remote_node.IN_GADAG == false) and 1026 (intf.remote_node.dfs_parent is x)) 1027 Construct_Ear(x, Stack, intf, CHILD) 1028 foreach interface intf of x 1029 if ((intf.remote_node.IN_GADAG == false) and 1030 (intf.remote_node.dfs_parent is not x)) 1031 Construct_Ear(x, Stack, intf, NEIGHBOR) 1033 Construct_GADAG_via_Lowpoint(topology, root) 1035 Figure 16: Low-point Inheritance GADAG algorithm 1037 5.5. Augmenting the GADAG by directing all links 1039 The GADAG, regardless of the algorithm used to construct it, at this 1040 point could be used to find MRTs but the topology does not include 1041 all links in the network graph. That has two impacts. First, there 1042 might be shorter paths that respect the GADAG partial ordering and so 1043 the alternate paths would not be as short as possible. Second, there 1044 may be additional paths between a router x and the root that are not 1045 included in the GADAG. Including those provides potentially more 1046 bandwidth to traffic flowing on the alternates and may reduce 1047 congestion compared to just using the GADAG as currently constructed. 1049 The goal is thus to assign direction to every remaining link marked 1050 as UNDIRECTED to improve the paths and number of paths found when the 1051 MRTs are computed. 1053 To do this, we need to establish a total order that respects the 1054 partial order described by the GADAG. This can be done using Kahn's 1055 topological sort[Kahn_1962_topo_sort] which essentially assigns a 1056 number to a node x only after all nodes before it (e.g. with a link 1057 incoming to x) have had their numbers assigned. The only issue with 1058 the topological sort is that it works on DAGs and not ADAGs or 1059 GADAGs. 1061 To convert a GADAG to a DAG, it is necessary to remove all links that 1062 point to a root of block from within that block. That provides the 1063 necessary conversion to a DAG and then a topological sort can be 1064 done. Finally, all UNDIRECTED links are assigned a direction based 1065 upon the total ordering. Any UNDIRECTED links that connect to a root 1066 of a block from within that block are assigned a direction INCOMING 1067 to that root. The exact details of this whole process are captured 1068 in Figure 17 1069 Set_Block_Root_Incoming_Links(topo, root, mark_or_clear) 1070 foreach node x in topo 1071 if node x is a cut-vertex or root 1072 foreach interface i of x 1073 if (i.remote_node.localroot is x) 1074 if i.UNDIRECTED 1075 i.OUTGOING = true 1076 i.remote_intf.INCOMING = true 1077 i.UNDIRECTED = false 1078 i.remote_intf.UNDIRECTED = false 1079 if i.INCOMING 1080 if mark_or_clear is MARK 1081 if i.OUTGOING // a cut-link 1082 i.STORE_INCOMING = true 1083 i.INCOMING = false 1084 i.remote_intf.STORE_OUTGOING = true 1085 i.remote_intf.OUTGOING = false 1086 i.TEMP_UNUSABLE = true 1087 i.remote_intf.TEMP_UNUSABLE = true 1088 else 1089 i.TEMP_UNUSABLE = false 1090 i.remote_intf.TEMP_UNUSABLE = false 1091 if i.STORE_INCOMING and (mark_or_clear is CLEAR) 1092 i.INCOMING = true 1093 i.STORE_INCOMING = false 1094 i.remote_intf.OUTGOING = true 1095 i.remote_intf.STORE_OUTGOING = false 1097 Run_Topological_Sort_GADAG(topo, root) 1098 Set_Block_Root_Incoming_Links(topo, root, MARK) 1099 foreach node x 1100 set x.unvisited to the count of x's incoming interfaces 1101 that aren't marked TEMP_UNUSABLE 1102 Initialize working_list to empty 1103 Initialize topo_order_list to empty 1104 add_to_list_end(working_list, root) 1105 while working_list is not empty 1106 y = remove_start_item_from_list(working_list) 1107 add_to_list_end(topo_order_list, y) 1108 foreach interface i of y 1109 if (i.OUTGOING) and (not i.TEMP_UNUSABLE) 1110 i.remote_node.unvisited -= 1 1111 if i.remote_node.unvisited is 0 1112 add_to_list_end(working_list, i.remote_node) 1113 next_topo_order = 1 1114 while topo_order_list is not empty 1115 y = remove_start_item_from_list(topo_order_list) 1116 y.topo_order = next_topo_order 1117 next_topo_order += 1 1118 Set_Block_Root_Incoming_Links(topo, root, CLEAR) 1120 Add_Undirected_Links(topo, root) 1121 Run_Topological_Sort_GADAG(topo, root) 1122 foreach node x in topo 1123 foreach interface i of x 1124 if i.UNDIRECTED 1125 if x.topo_order < i.remote_node.topo_order 1126 i.OUTGOING = true 1127 i.UNDIRECTED = false 1128 i.remote_intf.INCOMING = true 1129 i.remote_intf.UNDIRECTED = false 1130 else 1131 i.INCOMING = true 1132 i.UNDIRECTED = false 1133 i.remote_intf.OUTGOING = true 1134 i.remote_intf.UNDIRECTED = false 1136 Add_Undirected_Links(topo, root) 1138 Figure 17: Assigning direction to UNDIRECTED links 1140 Proxy-nodes do not need to be added to the network graph. They 1141 cannot be transited and do not affect the MRTs that are computed. 1142 The details of how the MRT-Blue and MRT-Red next-hops are computed 1143 for proxy-nodes and how the appropriate alternate next-hops are 1144 selected is given in Section 5.8. 1146 5.6. Compute MRT next-hops 1148 As was discussed in Section 4.1, once a ADAG is found, it is 1149 straightforward to find the next-hops from any node X to the ADAG 1150 root. However, in this algorithm, we will reuse the common GADAG and 1151 find not only the one pair of MRTs rooted at the GADAG root with it, 1152 but find a pair rooted at each node. This is useful since it is 1153 significantly faster to compute. 1155 The method for computing differently rooted MRTs from the common 1156 GADAG is based on two ideas. First, if two nodes X and Y are ordered 1157 with respect to each other in the partial order, then an SPF along 1158 OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a 1159 decreasing-SPF) can be used to find the increasing and decreasing 1160 paths. Second, if two nodes X and Y aren't ordered with respect to 1161 each other in the partial order, then intermediary nodes can be used 1162 to create the paths by increasing/decreasing to the intermediary and 1163 then decreasing/increasing to reach Y. 1165 As usual, the two basic ideas will be discussed assuming the network 1166 is two-connected. The generalization to multiple blocks is discussed 1167 in Section 5.6.4. The full algorithm is given in Section 5.6.5. 1169 5.6.1. MRT next-hops to all nodes partially ordered with respect to the 1170 computing node 1172 To find two node-disjoint paths from the computing router X to any 1173 node Y, depends upon whether Y >> X or Y << X. As shown in 1174 Figure 18, if Y >> X, then there is an increasing path that goes from 1175 X to Y without crossing R; this contains nodes in the interval [X,Y]. 1176 There is also a decreasing path that decreases towards R and then 1177 decreases from R to Y; this contains nodes in the interval 1178 [X,R-small] or [R-great,Y]. The two paths cannot have common nodes 1179 other than X and Y. 1181 [Y]<---(Cloud 2)<--- [X] 1182 | ^ 1183 | | 1184 V | 1185 (Cloud 3)--->[R]--->(Cloud 1) 1187 MRT-Blue path: X->Cloud 2->Y 1188 MRT-Red path: X->Cloud 1->R->Cloud 3->Y 1190 Figure 18: Y >> X 1192 Similar logic applies if Y << X, as shown in Figure 19. In this 1193 case, the increasing path from X increases to R and then increases 1194 from R to Y to use nodes in the intervals [X,R-great] and [R-small, 1195 Y]. The decreasing path from X reaches Y without crossing R and uses 1196 nodes in the interval [Y,X]. 1198 [X]<---(Cloud 2)<--- [Y] 1199 | ^ 1200 | | 1201 V | 1202 (Cloud 3)--->[R]--->(Cloud 1) 1204 MRT-Blue path: X->Cloud 3->R->Cloud 1->Y 1205 MRT-Red path: X->Cloud 2->Y 1207 Figure 19: Y << X 1209 5.6.2. MRT next-hops to all nodes not partially ordered with respect to 1210 the computing node 1212 When X and Y are not ordered, the first path should increase until we 1213 get to a node G, where G >> Y. At G, we need to decrease to Y. The 1214 other path should be just the opposite: we must decrease until we get 1215 to a node H, where H << Y, and then increase. Since R is smaller and 1216 greater than Y, such G and H must exist. It is also easy to see that 1217 these two paths must be node disjoint: the first path contains nodes 1218 in interval [X,G] and [Y,G], while the second path contains nodes in 1219 interval [H,X] and [H,Y]. This is illustrated in Figure 20. It is 1220 necessary to decrease and then increase for the MRT-Blue and increase 1221 and then decrease for the MRT-Red; if one simply increased for one 1222 and decreased for the other, then both paths would go through the 1223 root R. 1225 (Cloud 6)<---[Y]<---(Cloud 5)<------------| 1226 | | 1227 | | 1228 V | 1229 [G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H] 1230 ^ | 1231 | | 1232 | | 1233 (Cloud 3)<---[X]<---(Cloud 2)<-----------| 1235 MRT-Blue path: decrease to H and increase to Y 1236 X->Cloud 2->H->Cloud 5->Y 1237 MRT-Red path: increase to G and decrease to Y 1238 X->Cloud 3->G->Cloud 6->Y 1240 Figure 20: X and Y unordered 1242 This gives disjoint paths as long as G and H are not the same node. 1243 Since G >> Y and H << Y, if G and H could be the same node, that 1244 would have to be the root R. This is not possible because there is 1245 only one incoming interface to the root R which is created when the 1246 initial cycle is found. Recall from Figure 6 that whenever an ear 1247 was found to have an end that was the root R, the ear was directed 1248 from R so that the associated interface on R is outgoing and not 1249 incoming. Therefore, there must be exactly one node M which is the 1250 largest one before R, so the MRT-Red path will never reach R; it will 1251 turn at M and decrease to Y. 1253 5.6.3. Computing Redundant Tree next-hops in a 2-connected Graph 1255 The basic ideas for computing RT next-hops in a 2-connected graph 1256 were given in Section 5.6.1 and Section 5.6.2. Given these two 1257 ideas, how can we find the trees? 1259 If some node X only wants to find the next-hops (which is usually the 1260 case for IP networks), it is enough to find which nodes are greater 1261 and less than X, and which are not ordered; this can be done by 1262 running an increasing-SPF and a decreasing-SPF rooted at X and not 1263 exploring any links from the ADAG root. ( Traversal algorithms other 1264 than SPF could safely be used instead where one traversal takes the 1265 links in their given directions and the other reverses the links' 1266 directions.) 1268 An increasing-SPF rooted at X and not exploring links from the root 1269 will find the increasing next-hops to all Y >> X. Those increasing 1270 next-hops are X's next-hops on the MRT-Blue to reach Y. A 1271 decreasing-SPF rooted at X and not exploring links from the root will 1272 find the decreasing next-hops to all Z << X. Those decreasing next- 1273 hops are X's next-hops on the MRT-Red to reach Z. Since the root R 1274 is both greater than and less than X, after this increasing-SPF and 1275 decreasing-SPF, X's next-hops on the MRT-Blue and on the MRT-Red to 1276 reach R are known. For every node Y >> X, X's next-hops on the MRT- 1277 Red to reach Y are set to those on the MRT-Red to reach R. For every 1278 node Z << X, X's next-hops on the MRT-Blue to reach Z are set to 1279 those on the MRT-Blue to reach R. 1281 For those nodes which were not reached by either the increasing-SPF 1282 or the decreasing-SPF, we can determine the next-hops as well. The 1283 increasing MRT-Blue next-hop for a node which is not ordered with 1284 respect to X is the next-hop along the decreasing MRT-Red towards R, 1285 and the decreasing MRT-Red next-hop is the next-hop along the 1286 increasing MRT-Blue towards R. Naturally, since R is ordered with 1287 respect to all the nodes, there will always be an increasing and a 1288 decreasing path towards it. This algorithm does not provide the 1289 complete specific path taken but just the appropriate next-hops to 1290 use. The identities of G and H are not determined by the computing 1291 node X. 1293 The final case to considered is when the root R computes its own 1294 next-hops. Since the root R is << all other nodes, running an 1295 increasing-SPF rooted at R will reach all other nodes; the MRT-Blue 1296 next-hops are those found with this increasing-SPF. Similarly, since 1297 the root R is >> all other nodes, running a decreasing-SPF rooted at 1298 R will reach all other nodes; the MRT-Red next-hops are those found 1299 with this decreasing-SPF. 1301 E---D---| E<--D<--| 1302 | | | | ^ | 1303 | | | V | | 1304 R F C R F C 1305 | | | | ^ ^ 1306 | | | V | | 1307 A---B---| A-->B---| 1309 (a) (b) 1310 A 2-connected graph A spanning ADAG rooted at R 1312 Figure 21 1314 As an example consider the situation depicted in Figure 21. Node C 1315 runs an increasing-SPF and a decreasing-SPF on the ADAG. The 1316 increasing-SPF reaches D, E and R and the decreasing-SPF reaches B, A 1317 and R. E>>C. So towards E the MRT-Blue next-hop is D, since E was 1318 reached on the increasing path through D. And the MRT-Red next-hop 1319 towards E is B, since R was reached on the decreasing path through B. 1320 Since E>>D, D will similarly compute its MRT-Blue next-hop to be E, 1321 ensuring that a packet on MRT-Blue will use path C-D-E. B, A and R 1322 will similarly compute the MRT-Red next-hops towards E (which is 1323 ordered less than B, A and R), ensuring that a packet on MRT-Red will 1324 use path C-B-A-R-E. 1326 C can determine the next-hops towards F as well. Since F is not 1327 ordered with respect to C, the MRT-Blue next-hop is the decreasing 1328 one towards R (which is B) and the MRT-Red next-hop is the increasing 1329 one towards R (which is D). Since F>>B, for its MRT-Blue next-hop 1330 towards F, B will use the real increasing next-hop towards F. So a 1331 packet forwarded to B on MRT-Blue will get to F on path C-B-F. 1332 Similarly, D will use the real decreasing next-hop towards F as its 1333 MRT-Red next-hop, an packet on MRT-Red will use path C-D-F. 1335 5.6.4. Generalizing for a graph that isn't 2-connected 1337 If a graph isn't 2-connected, then the basic approach given in 1338 Section 5.6.3 needs some extensions to determine the appropriate MRT 1339 next-hops to use for destinations outside the computing router X's 1340 blocks. In order to find a pair of maximally redundant trees in that 1341 graph we need to find a pair of RTs in each of the blocks (the root 1342 of these trees will be discussed later), and combine them. 1344 When computing the MRT next-hops from a router X, there are three 1345 basic differences: 1347 1. Only nodes in a common block with X should be explored in the 1348 increasing-SPF and decreasing-SPF. 1350 2. Instead of using the GADAG root, X's local-root should be used. 1351 This has the following implications: 1353 A. The links from X's local-root should not be explored. 1355 B. If a node is explored in the outgoing SPF so Y >> X, then X's 1356 MRT-Red next-hops to reach Y uses X's MRT-Red next-hops to 1357 reach X's local-root and if Z << X, then X's MRT-Blue next- 1358 hops to reach Z uses X's MRT-Blue next-hops to reach X's 1359 local-root. 1361 C. If a node W in a common block with X was not reached in the 1362 increasing-SPF or decreasing-SPF, then W is unordered with 1363 respect to X. X's MRT-Blue next-hops to W are X's decreasing 1364 (aka MRT-Red) next-hops to X's local-root. X's MRT-Red next- 1365 hops to W are X's increasing (aka MRT-Blue) next-hops to X's 1366 local-root. 1368 3. For nodes in different blocks, the next-hops must be inherited 1369 via the relevant cut-vertex. 1371 These are all captured in the detailed algorithm given in 1372 Section 5.6.5. 1374 5.6.5. Complete Algorithm to Compute MRT Next-Hops 1376 The complete algorithm to compute MRT Next-Hops for a particular 1377 router X is given in Figure 22. In addition to computing the MRT- 1378 Blue next-hops and MRT-Red next-hops used by X to reach each node Y, 1379 the algorithm also stores an "order_proxy", which is the proper cut- 1380 vertex to reach Y if it is outside the block, and which is used later 1381 in deciding whether the MRT-Blue or the MRT-Red can provide an 1382 acceptable alternate for a particular primary next-hop. 1384 In_Common_Block(x, y) 1385 if (((x.localroot is y.localroot) and (x.block_id is y.block_id)) 1386 or (x is y.localroot) or (y is x.localroot)) 1387 return true 1388 return false 1390 Store_Results(y, direction, spf_root, store_nhs) 1391 if direction is FORWARD 1392 y.higher = true 1393 if store_nhs 1394 y.blue_next_hops = y.next_hops 1395 if direction is REVERSE 1396 y.lower = true 1397 if store_nhs 1398 y.red_next_hops = y.next_hops 1400 SPF_No_Traverse_Root(spf_root, block_root, direction, store_nhs) 1401 Initialize spf_heap to empty 1402 Initialize nodes' spf_metric to infinity and next_hops to empty 1403 spf_root.spf_metric = 0 1404 insert(spf_heap, spf_root) 1405 while (spf_heap is not empty) 1406 min_node = remove_lowest(spf_heap) 1407 Store_Results(min_node, direction, spf_root, store_nhs) 1408 if ((min_node is spf_root) or (min_node is not block_root)) 1409 foreach interface intf of min_node 1410 if (((direction is FORWARD) and intf.OUTGOING) or 1411 ((direction is REVERSE) and intf.INCOMING) and 1412 In_Common_Block(spf_root, intf.remote_node)) 1413 path_metric = min_node.spf_metric + intf.metric 1414 if path_metric < intf.remote_node.spf_metric 1415 intf.remote_node.spf_metric = path_metric 1416 if min_node is spf_root 1417 intf.remote_node.next_hops = make_list(intf) 1418 else 1419 intf.remote_node.next_hops = min_node.next_hops 1420 insert_or_update(spf_heap, intf.remote_node) 1421 else if path_metric is intf.remote_node.spf_metric 1422 if min_node is spf_root 1423 add_to_list(intf.remote_node.next_hops, intf) 1424 else 1425 add_list_to_list(intf.remote_node.next_hops, 1426 min_node.next_hops) 1428 SetEdge(y) 1429 if y.blue_next_hops is empty and y.red_next_hops is empty 1430 if (y.local_root != y) { 1431 SetEdge(y.localroot) 1432 } 1433 y.blue_next_hops = y.localroot.blue_next_hops 1434 y.red_next_hops = y.localroot.red_next_hops 1435 y.order_proxy = y.localroot.order_proxy 1437 Compute_MRT_NextHops(x, root) 1438 foreach node y 1439 y.higher = y.lower = false 1440 clear y.red_next_hops and y.blue_next_hops 1441 y.order_proxy = y 1442 SPF_No_Traverse_Root(x, x.localroot, FORWARD, TRUE) 1443 SPF_No_Traverse_Root(x, x.localroot, REVERSE, TRUE) 1445 // red and blue next-hops are stored to x.localroot as different 1446 // paths are found via the SPF and reverse-SPF. 1447 // Similarly any nodes whose local-root is x will have their 1448 // red_next_hops and blue_next_hops already set. 1450 // Handle nodes in the same block that aren't the local-root 1451 foreach node y 1452 if (y.IN_MRT_ISLAND and (y is not x) and 1453 (y.localroot is x.localroot) and 1454 ((y is x.localroot) or (x is y.localroot) or 1455 (y.block_id is x.block_id))) 1456 if y.higher 1457 y.red_next_hops = x.localroot.red_next_hops 1458 else if y.lower 1459 y.blue_next_hops = x.localroot.blue_next_hops 1460 else 1461 y.blue_next_hops = x.localroot.red_next_hops 1462 y.red_next_hops = x.localroot.blue_next_hops 1464 // Inherit next-hops and order_proxies to other components 1465 if x is not root 1466 root.blue_next_hops = x.localroot.blue_next_hops 1467 root.red_next_hops = x.localroot.red_next_hops 1468 root.order_proxy = x.localroot 1469 foreach node y 1470 if (y is not root) and (y is not x) and y.IN_MRT_ISLAND 1471 SetEdge(y) 1473 max_block_id = 0 1474 Assign_Block_ID(root, max_block_id) 1475 Compute_MRT_NextHops(x, root) 1477 Figure 22 1479 5.7. Identify MRT alternates 1481 At this point, a computing router S knows its MRT-Blue next-hops and 1482 MRT-Red next-hops for each destination in the MRT Island. The 1483 primary next-hops along the SPT are also known. It remains to 1484 determine for each primary next-hop to a destination D, which of the 1485 MRTs avoids the primary next-hop node F. This computation depends 1486 upon data set in Compute_MRT_NextHops such as each node y's 1487 y.blue_next_hops, y.red_next_hops, y.order_proxy, y.higher, y.lower 1488 and topo_orders. Recall that any router knows only which are the 1489 nodes greater and lesser than itself, but it cannot decide the 1490 relation between any two given nodes easily; that is why we need 1491 topological ordering. 1493 For each primary next-hop node F to each destination D, S can call 1494 Select_Alternates(S, D, F, primary_intf) to determine whether to use 1495 the MRT-Blue next-hops as the alternate next-hop(s) for that primary 1496 next hop or to use the MRT-Red next-hops. The algorithm is given in 1497 Figure 23 and discussed afterwards. 1499 Select_Alternates_Internal(S, D, F, primary_intf, 1500 D_lower, D_higher, D_topo_order) 1502 //When D==F, we can do only link protection 1503 if ((D is F) or (D.order_proxy is F)) 1504 if an MRT doesn't use primary_intf 1505 indicate alternate is not node-protecting 1506 return that MRT color 1507 else // parallel links are cut-links 1508 return AVOID_LINK_ON_BLUE 1510 if (D_lower and D_higher and F.lower and F.higher) 1511 if F.topo_order < D_topo_order 1512 return USE_RED 1513 else 1514 return USE_BLUE 1516 if (D_lower and D_higher) 1517 if F.higher 1518 return USE_RED 1519 else 1520 return USE_BLUE 1522 if (F.lower and F.higher) 1523 if D_lower 1524 return USE_RED 1525 else if D_higher 1526 return USE_BLUE 1527 else 1528 if primary_intf.OUTGOING and primary_intf.INCOMING 1529 return AVOID_LINK_ON_BLUE 1530 if primary_intf.OUTGOING is true 1531 return USE_BLUE 1532 if primary_intf.INCOMING is true 1533 return USE_RED 1535 if D_higher 1536 if F.higher 1537 if F.topo_order < D_topo_order 1538 return USE_RED 1539 else 1540 return USE_BLUE 1541 else if F.lower 1542 return USE_BLUE 1543 else 1544 // F and S are neighbors so either F << S or F >> S 1545 else if D_lower 1546 if F.higher 1547 return USE_RED 1548 else if F.lower 1549 if F.topo_order < D_topo_order 1550 return USE_RED 1551 else 1552 return USE_BLUE 1553 else 1554 // F and S are neighbors so either F << S or F >> S 1555 else // D and S not ordered 1556 if F.lower 1557 return USE_RED 1558 else if F.higher 1559 return USE_BLUE 1560 else 1561 // F and S are neighbors so either F << S or F >> S 1563 Select_Alternates(S, D, F, primary_intf) 1564 if D.order_proxy is not D 1565 D_lower = D.order_proxy.lower 1566 D_higher = D.order_proxy.higher 1567 D_topo_order = D.order_proxy.topo_order 1568 else 1569 D_lower = D.lower 1570 D_higher = D.higher 1571 D_topo_order = D.topo_order 1572 return Select_Alternates_Internal(S, D, F, primary_intf, 1573 D_lower, D_higher, D_topo_order) 1575 Figure 23 1577 If either D>>S>>F or D<>D (ii) F<D.topo_order, either case (i) or 1588 case (iii) holds true, which means that selecting the Blue next-hop 1589 is safe. Similarly, if F.topo_order>S, 1599 we should use the Blue next-hop. 1601 Additionally, the cases where either F or D is ordered both higher 1602 and lower must be considered; this can happen when one is a block- 1603 root or its order_proxy is. If D is both higher and lower than S, 1604 then the MRT to use is the one that avoids F so if F is higher, then 1605 the MRT-Red should be used and if F is lower, then the MRT-Blue 1606 should be used; F and S must be ordered because they are neighbors. 1607 If F is both higher and lower, then if D is lower, using the MRT-Red 1608 to decrease reaches D and if D is higher, using the Blue MRT to 1609 increase reaches D; if D is unordered compared to S, then the 1610 situation is a bit more complicated. 1612 In the case where F< F, then use the MRT-Blue (decrease to avoid 1615 that link and then increase). If the link is directed S <- F, then 1616 use the MRT-Red (increase to avoid that link and then decrease). If 1617 the link is S <--> F, then the link must be a cut-link and there is 1618 no node-protecting alternate. If there are multiple links between S 1619 and F, then they can protect against each other; of course, in this 1620 situation, they are probably already ECMP. 1622 Finally, there is the case where D is also F. In this case, only 1623 link protection is possible. The MRT that doesn't use the indicated 1624 primary next-hop is used. If both MRTs use the primary next-hop, 1625 then the primary next-hop must be a cut-link so either MRT could be 1626 used but the set of MRT next-hops must be pruned to avoid that 1627 primary next-hop. To indicate this case, Select_Alternates returns 1628 AVOID_LINK_ON_BLUE. 1630 As an example, consider the ADAG depicted in Figure 24 and first 1631 suppose that G is the source, D is the destination and H is the 1632 failed next-hop. Since D>>G, we need to compare H.topo_order and 1633 D.topo_order. Since D.topo_order>H.topo_order, D must be not smaller 1634 than H, so we should select the decreasing path towards the root. 1636 If, however, the destination were instead J, we must find that 1637 H.topo_order>J.topo_order, so we must choose the increasing Blue 1638 next-hop to J, which is I. In the case, when instead the destination 1639 is C, we find that we need to first decrease to avoid using H, so the 1640 Blue, first decreasing then increasing, path is selected. 1642 [E]<-[D]<-[H]<-[J] 1643 | ^ ^ ^ 1644 V | | | 1645 [R] [C] [G]->[I] 1646 | ^ ^ ^ 1647 V | | | 1648 [A]->[B]->[F]---| 1650 (a) 1651 a 2-connected graph 1653 Figure 24 1655 5.8. Finding FRR Next-Hops for Proxy-Nodes 1657 As discussed in Section 10.2 of 1658 [I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT- 1659 Blue and MRT-Red next-hops and MRT-FRR alternates for a named proxy- 1660 nodes. An example case is for a router that is not part of that 1661 local MRT Island, when there is only partial MRT support in the 1662 domain. 1664 A first incorrect and naive approach to handling proxy-nodes, which 1665 cannot be transited, is to simply add these proxy-nodes to the graph 1666 of the network and connect it to the routers through which the new 1667 proxy-node can be reached. Unfortunately, this can introduce some 1668 new ordering between the border routers connected to the new node 1669 which could result in routing MRT paths through the proxy-node. 1670 Thus, this naive approach would need to recompute GADAGs and redo 1671 SPTs for each proxy-node. 1673 Instead of adding the proxy-node to the original network graph, each 1674 individual proxy-node can be individually added to the GADAG. The 1675 proxy-node is connected to at most two nodes in the GADAG. 1676 Section 10.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] defines how the 1677 proxy-node attachments MUST be determined. The degenerate case where 1678 the proxy-node is attached to only one node in the GADAG is trivial 1679 as all needed information can be derived from that attachment node; 1680 if there are different interfaces, then some can be assigned to MRT- 1681 Red and others to MRT_Blue. 1683 Now, consider the proxy-node that is attached to exactly two nodes in 1684 the GADAG. Let the order_proxies of these nodes be A and B. Let the 1685 current node, where next-hop is just being calculated, be S. If one 1686 of these two nodes A and B is the local root of S, let A=S.local_root 1687 and the other one be B. Otherwise, let A.topo_order < B.topo_order. 1689 A valid GADAG was constructed. Instead doing an increasing-SPF and a 1690 decreasing-SPF to find ordering for the proxy-nodes, the following 1691 simple rules, providing the same result, can be used independently 1692 for each different proxy-node. For the following rules, let 1693 X=A.local_root, and if A is the local root, let that be strictly 1694 lower than any other node. Always take the first rule that matches. 1696 Rule Condition Blue NH Red NH Notes 1697 1 S=X Blue to A Red to B 1698 2 S<>B Blue to R Red to B 1700 4 A<> X, 1783 the computing router, MUST be one or more nodes, T, whose topo_order 1784 is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y 1785 is T. Similarly, the MRT-Red next-hops MUST be have a topo_order in 1786 the interval [R-small.topo_order, X.topo_order] or [Y.topo_order, 1787 R-big.topo_order]. 1789 Implementations SHOULD implement the Select_Alternates() function to 1790 pick an MRT-FRR alternate. 1792 7. Algorithm Alternatives and Evaluation 1794 This specification defines the MRT Lowpoint Algorithm, which is one 1795 option among several possible MRT algorithms. Other alternatives are 1796 described in the appendices. 1798 In addition, it is possible to calculate Destination-Rooted GADAG, 1799 where for each destination, a GADAG rooted at that destination is 1800 computed. Then a router can compute the blue MRT and red MRT next- 1801 hops to that destination. Building GADAGs per destination is 1802 computationally more expensive, but may give somewhat shorter 1803 alternate paths. It may be useful for live-live multicast along 1804 MRTs. 1806 7.1. Algorithm Evaluation 1808 The MRT Lowpoint algorithm is the lowest computation of the MRT 1809 algorithms. Two other MRT algorithms are provided in Appendix A and 1810 Appendix B. When analyzed on service provider network topologies, 1811 they did not provide significant differences in the path lenghts for 1812 the alternatives. This section does not focus on that analysis or 1813 the decision to use the MRT Lowpoint algorithm as the default MRT 1814 algorithm; it has the lowest computational and storage requirements 1815 and gave comparable results. 1817 Since this document defines the MRT Lowpoint algorithm for use in 1818 fast-reroute applications, it is useful to compare MRT and Remote LFA 1819 [I-D.ietf-rtgwg-remote-lfa]. This section compares MRT and remote 1820 LFA for IP Fast Reroute in 19 service provider network topologies, 1821 focusing on coverage and alternate path length. Figure 26 shows the 1822 node-protecting coverage provided by local LFA (LLFA), remote LFA 1823 (RLFA), and MRT against different failure scenarios in these 1824 topologies. The coverage values are calculated as the percentage of 1825 source-destination pairs protected by the given IPFRR method relative 1826 to those protectable by optimal routing, against the same failure 1827 modes. More details on alternate selection policies used for this 1828 analysis are described later in this section. 1830 +------------+-----------------------------+ 1831 | Topology | percentage of failure | 1832 | | scenarios covered by | 1833 | | IPFRR method | 1834 | |-----------------------------+ 1835 | | NP_LLFA | NP_RLFA | MRT | 1836 +------------+---------+---------+---------+ 1837 | T201 | 37 | 90 | 100 | 1838 | T202 | 73 | 83 | 100 | 1839 | T203 | 51 | 80 | 100 | 1840 | T204 | 55 | 81 | 100 | 1841 | T205 | 92 | 93 | 100 | 1842 | T206 | 71 | 74 | 100 | 1843 | T207 | 57 | 74 | 100 | 1844 | T208 | 66 | 81 | 100 | 1845 | T209 | 79 | 79 | 100 | 1846 | T210 | 95 | 98 | 100 | 1847 | T211 | 68 | 71 | 100 | 1848 | T212 | 59 | 63 | 100 | 1849 | T213 | 84 | 84 | 100 | 1850 | T214 | 68 | 78 | 100 | 1851 | T215 | 84 | 88 | 100 | 1852 | T216 | 43 | 59 | 100 | 1853 | T217 | 78 | 88 | 100 | 1854 | T218 | 72 | 75 | 100 | 1855 | T219 | 78 | 84 | 100 | 1856 +------------+---------+---------+---------+ 1858 Figure 26 1860 For the topologies analyzed here, LLFA is able to provide node- 1861 protecting coverage ranging from 37% to 95% of the source-destination 1862 pairs, as seen in the column labeled NP_LLFA. The use of RLFA in 1863 addition to LLFA is generally able to increase the node-protecting 1864 coverage. The percentage of node-protecting coverage with RLFA is 1865 provided in the column labeled NP_RLFA, ranges from 59% to 98% for 1866 these topologies. The node-protecting coverage provided by MRT is 1867 100% since MRT is able to provide protection for any source- 1868 destination pair for which a path still exists after the failure. 1870 We would also like to measure the quality of the alternate paths 1871 produced by these different IPFRR methods. An obvious approach is to 1872 take an average of the alternate path costs over all source- 1873 destination pairs and failure modes. However, this presents a 1874 problem, which we will illustrate by presenting an example of results 1875 for one topology using this approach ( Figure 27). In this table, 1876 the average relative path length is the alternate path length for the 1877 IPFRR method divided by the optimal alternate path length, averaged 1878 over all source-destination pairs and failure modes. The first three 1879 columns of data in the table give the path length calculated from the 1880 sum of IGP metrics of the links in the path. The results for 1881 topology T208 show that the metric-based path lengths for NP_LLFA and 1882 NP_RLFA alternates are on average 78 and 66 times longer than the 1883 path lengths for optimal alternates. The metric-based path lengths 1884 for MRT alternates are on average 14 times longer than for optimal 1885 alternates. 1887 +--------+------------------------------------------------+ 1888 | | average relative alternate path length | 1889 | |-----------------------+------------------------+ 1890 |Topology| IGP metric | hopcount | 1891 | |-----------------------+------------------------+ 1892 | |NP_LLFA |NP_RLFA | MRT |NP_LLFA |NP_RLFA | MRT | 1893 +--------+--------+--------+-----+--------+--------+------+ 1894 | T208 | 78.2 | 66.0 | 13.6| 0.99 | 1.01 | 1.32 | 1895 +--------+--------+--------+-----+--------+--------+------+ 1897 Figure 27 1899 The network topology represented by T208 uses values of 10, 100, and 1900 1000 as IGP costs, so small deviations from the optimal alternate 1901 path can result in large differences in relative path length. LLFA, 1902 RLFA, and MRT all allow for at least one hop in the alterate path to 1903 be chosen independent of the cost of the link. This can easily 1904 result in an alternate using a link with cost 1000, which introduces 1905 noise into the path length measurement. In the case of T208, the 1906 adverse effects of using metric-based path lengths is obvious. 1907 However, we have observed that the metric-based path length 1908 introduces noise into alternate path length measurements in several 1909 other topologies as well. For this reason, we have opted to measure 1910 the alternate path length using hopcount. While IGP metrics may be 1911 adjusted by the network operator for a number of reasons (e.g. 1912 traffic engineering), the hopcount is a fairly stable measurement of 1913 path length. As shown in the last three columns of Figure 27, the 1914 hopcount-based alternate path lengths for topology T208 are fairly 1915 well-behaved. 1917 Figure 28, Figure 29, Figure 30, and Figure 31 present the hopcount- 1918 based path length results for the 19 topologies examined. The 1919 topologies in the four tables are grouped based on the size of the 1920 topologies, as measured by the number of nodes, with Figure 28 having 1921 the smallest topologies and Figure 31 having the largest topologies. 1922 Instead of trying to represent the path lengths of a large set of 1923 alternates with a single number, we have chosen to present a 1924 histogram of the path lengths for each IPFRR method and alternate 1925 selection policy studied. The first eight colums of data represent 1926 the percentage of failure scenarios protected by an alternate N hops 1927 longer than the primary path, with the first column representing an 1928 alternate 0 or 1 hops longer than the primary path, all the way up 1929 through the eighth column respresenting an alternate 14 or 15 hops 1930 longer than the primary path. The last column in the table gives the 1931 percentage of failure scenarios for which there is no alternate less 1932 than 16 hops longer than the primary path. In the case of LLFA and 1933 RLFA, this category includes failure scenarios for which no alternate 1934 was found. 1936 For each topology, the first row (labeled OPTIMAL) is the 1937 distribution of the number of hops in excess of the primary path 1938 hopcount for optimally routed alternates. (The optimal routing was 1939 done with respect to IGP metrics, as opposed to hopcount.) The 1940 second row(labeled NP_LLFA) is the distribution of the extra hops for 1941 node-protecting LLFA. The third row (labeled NP_LLFA_THEN_NP_RLFA) 1942 is the hopcount distribution when one adds node-protecting RLFA to 1943 increase the coverage. The alternate selection policy used here 1944 first tries to find a node-protecting LLFA. If that does not exist, 1945 then it tries to find an RLFA, and checks if it is node-protecting. 1946 Comparing the hopcount distribution for RLFA and LLFA across these 1947 topologies, one can see how the coverage is increased at the expense 1948 of using longer alternates. It is also worth noting that while 1949 superficially LLFA and RLFA appear to have better hopcount 1950 distributions than OPTIMAL, the presence of entries in the last 1951 column (no alternate < 16) mainly represent failure scenarios that 1952 are not protected, for which the hopcount is effectively infinite. 1954 The fourth and fifth rows of each topology show the hopcount 1955 distributions for two alternate selection policies using MRT 1956 alternates. The policy represented by the label 1957 NP_LLFA_THEN_MRT_LOWPOINT will first use a node-protecting LLFA. If 1958 a node-protecting LLFA does not exist, then it will use an MRT 1959 alternate. The policy represented by the label MRT_LOWPOINT instead 1960 will use the MRT alternate even if a node-protecting LLFA exists. 1961 One can see from the data that combining node-protecting LLFA with 1962 MRT results in a significant shortening of the alternate hopcount 1963 distribution. 1965 +-------------------------------------------------------------------+ 1966 | | percentage of failure scenarios | 1967 | Topology name | protected by an alternate N hops | 1968 | and | longer than the primary path | 1969 | alternate selection +------------------------------------+ 1970 | policy evaluated | | | | | | | | | no | 1971 | | | | | | |10 |12 |14 | alt| 1972 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 1973 +------------------------------+---+---+---+---+---+---+---+---+----+ 1974 | T201(avg primary hops=3.5) | | | | | | | | | | 1975 | OPTIMAL | 37| 37| 20| 3| 3| | | | | 1976 | NP_LLFA | 37| | | | | | | | 63| 1977 | NP_LLFA_THEN_NP_RLFA | 37| 34| 19| | | | | | 10| 1978 | NP_LLFA_THEN_MRT_LOWPOINT | 37| 33| 21| 6| 3| | | | | 1979 | MRT_LOWPOINT | 33| 36| 23| 6| 3| | | | | 1980 +------------------------------+---+---+---+---+---+---+---+---+----+ 1981 | T202(avg primary hops=4.8) | | | | | | | | | | 1982 | OPTIMAL | 90| 9| | | | | | | | 1983 | NP_LLFA | 71| 2| | | | | | | 27| 1984 | NP_LLFA_THEN_NP_RLFA | 78| 5| | | | | | | 17| 1985 | NP_LLFA_THEN_MRT_LOWPOINT | 80| 12| 5| 2| 1| | | | | 1986 | MRT_LOWPOINT_ONLY | 48| 29| 13| 7| 2| 1| | | | 1987 +------------------------------+---+---+---+---+---+---+---+---+----+ 1988 | T203(avg primary hops=4.1) | | | | | | | | | | 1989 | OPTIMAL | 36| 37| 21| 4| 2| | | | | 1990 | NP_LLFA | 34| 15| 3| | | | | | 49| 1991 | NP_LLFA_THEN_NP_RLFA | 35| 19| 22| 4| | | | | 20| 1992 | NP_LLFA_THEN_MRT_LOWPOINT | 36| 35| 22| 5| 2| | | | | 1993 | MRT_LOWPOINT_ONLY | 31| 35| 26| 7| 2| | | | | 1994 +------------------------------+---+---+---+---+---+---+---+---+----+ 1995 | T204(avg primary hops=3.7) | | | | | | | | | | 1996 | OPTIMAL | 76| 20| 3| 1| | | | | | 1997 | NP_LLFA | 54| 1| | | | | | | 45| 1998 | NP_LLFA_THEN_NP_RLFA | 67| 10| 4| | | | | | 19| 1999 | NP_LLFA_THEN_MRT_LOWPOINT | 70| 18| 8| 3| 1| | | | | 2000 | MRT_LOWPOINT_ONLY | 58| 27| 11| 3| 1| | | | | 2001 +------------------------------+---+---+---+---+---+---+---+---+----+ 2002 | T205(avg primary hops=3.4) | | | | | | | | | | 2003 | OPTIMAL | 92| 8| | | | | | | | 2004 | NP_LLFA | 89| 3| | | | | | | 8| 2005 | NP_LLFA_THEN_NP_RLFA | 90| 4| | | | | | | 7| 2006 | NP_LLFA_THEN_MRT_LOWPOINT | 91| 9| | | | | | | | 2007 | MRT_LOWPOINT_ONLY | 62| 33| 5| 1| | | | | | 2008 +------------------------------+---+---+---+---+---+---+---+---+----+ 2010 Figure 28 2012 +-------------------------------------------------------------------+ 2013 | | percentage of failure scenarios | 2014 | Topology name | protected by an alternate N hops | 2015 | and | longer than the primary path | 2016 | alternate selection +------------------------------------+ 2017 | policy evaluated | | | | | | | | | no | 2018 | | | | | | |10 |12 |14 | alt| 2019 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 2020 +------------------------------+---+---+---+---+---+---+---+---+----+ 2021 | T206(avg primary hops=3.7) | | | | | | | | | | 2022 | OPTIMAL | 63| 30| 7| | | | | | | 2023 | NP_LLFA | 60| 9| 1| | | | | | 29| 2024 | NP_LLFA_THEN_NP_RLFA | 60| 13| 1| | | | | | 26| 2025 | NP_LLFA_THEN_MRT_LOWPOINT | 64| 29| 7| | | | | | | 2026 | MRT_LOWPOINT | 55| 32| 13| | | | | | | 2027 +------------------------------+---+---+---+---+---+---+---+---+----+ 2028 | T207(avg primary hops=3.9) | | | | | | | | | | 2029 | OPTIMAL | 71| 24| 5| 1| | | | | | 2030 | NP_LLFA | 55| 2| | | | | | | 43| 2031 | NP_LLFA_THEN_NP_RLFA | 63| 10| | | | | | | 26| 2032 | NP_LLFA_THEN_MRT_LOWPOINT | 70| 20| 7| 2| 1| | | | | 2033 | MRT_LOWPOINT_ONLY | 57| 29| 11| 3| 1| | | | | 2034 +------------------------------+---+---+---+---+---+---+---+---+----+ 2035 | T208(avg primary hops=4.6) | | | | | | | | | | 2036 | OPTIMAL | 58| 28| 12| 2| 1| | | | | 2037 | NP_LLFA | 53| 11| 3| | | | | | 34| 2038 | NP_LLFA_THEN_NP_RLFA | 56| 17| 7| 1| | | | | 19| 2039 | NP_LLFA_THEN_MRT_LOWPOINT | 58| 19| 10| 7| 3| 1| | | | 2040 | MRT_LOWPOINT_ONLY | 34| 24| 21| 13| 6| 2| 1| | | 2041 +------------------------------+---+---+---+---+---+---+---+---+----+ 2042 | T209(avg primary hops=3.6) | | | | | | | | | | 2043 | OPTIMAL | 85| 14| 1| | | | | | | 2044 | NP_LLFA | 79| | | | | | | | 21| 2045 | NP_LLFA_THEN_NP_RLFA | 79| | | | | | | | 21| 2046 | NP_LLFA_THEN_MRT_LOWPOINT | 82| 15| 2| | | | | | | 2047 | MRT_LOWPOINT_ONLY | 63| 29| 8| | | | | | | 2048 +------------------------------+---+---+---+---+---+---+---+---+----+ 2049 | T210(avg primary hops=2.5) | | | | | | | | | | 2050 | OPTIMAL | 95| 4| 1| | | | | | | 2051 | NP_LLFA | 94| 1| | | | | | | 5| 2052 | NP_LLFA_THEN_NP_RLFA | 94| 3| 1| | | | | | 2| 2053 | NP_LLFA_THEN_MRT_LOWPOINT | 95| 4| 1| | | | | | | 2054 | MRT_LOWPOINT_ONLY | 91| 6| 2| | | | | | | 2055 +------------------------------+---+---+---+---+---+---+---+---+----+ 2057 Figure 29 2059 +-------------------------------------------------------------------+ 2060 | | percentage of failure scenarios | 2061 | Topology name | protected by an alternate N hops | 2062 | and | longer than the primary path | 2063 | alternate selection +------------------------------------+ 2064 | policy evaluated | | | | | | | | | no | 2065 | | | | | | |10 |12 |14 | alt| 2066 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 2067 +------------------------------+---+---+---+---+---+---+---+---+----+ 2068 | T211(avg primary hops=3.3) | | | | | | | | | | 2069 | OPTIMAL | 88| 11| | | | | | | | 2070 | NP_LLFA | 66| 1| | | | | | | 32| 2071 | NP_LLFA_THEN_NP_RLFA | 68| 3| | | | | | | 29| 2072 | NP_LLFA_THEN_MRT_LOWPOINT | 88| 12| | | | | | | | 2073 | MRT_LOWPOINT | 85| 15| 1| | | | | | | 2074 +------------------------------+---+---+---+---+---+---+---+---+----+ 2075 | T212(avg primary hops=3.5) | | | | | | | | | | 2076 | OPTIMAL | 76| 23| 1| | | | | | | 2077 | NP_LLFA | 59| | | | | | | | 41| 2078 | NP_LLFA_THEN_NP_RLFA | 61| 1| 1| | | | | | 37| 2079 | NP_LLFA_THEN_MRT_LOWPOINT | 75| 24| 1| | | | | | | 2080 | MRT_LOWPOINT_ONLY | 66| 31| 3| | | | | | | 2081 +------------------------------+---+---+---+---+---+---+---+---+----+ 2082 | T213(avg primary hops=4.3) | | | | | | | | | | 2083 | OPTIMAL | 91| 9| | | | | | | | 2084 | NP_LLFA | 84| | | | | | | | 16| 2085 | NP_LLFA_THEN_NP_RLFA | 84| | | | | | | | 16| 2086 | NP_LLFA_THEN_MRT_LOWPOINT | 89| 10| 1| | | | | | | 2087 | MRT_LOWPOINT_ONLY | 75| 24| 1| | | | | | | 2088 +------------------------------+---+---+---+---+---+---+---+---+----+ 2089 | T214(avg primary hops=5.8) | | | | | | | | | | 2090 | OPTIMAL | 71| 22| 5| 2| | | | | | 2091 | NP_LLFA | 58| 8| 1| 1| | | | | 32| 2092 | NP_LLFA_THEN_NP_RLFA | 61| 13| 3| 1| | | | | 22| 2093 | NP_LLFA_THEN_MRT_LOWPOINT | 66| 14| 7| 5| 3| 2| 1| 1| 1| 2094 | MRT_LOWPOINT_ONLY | 30| 20| 18| 12| 8| 4| 3| 2| 3| 2095 +------------------------------+---+---+---+---+---+---+---+---+----+ 2096 | T215(avg primary hops=4.8) | | | | | | | | | | 2097 | OPTIMAL | 73| 27| | | | | | | | 2098 | NP_LLFA | 73| 11| | | | | | | 16| 2099 | NP_LLFA_THEN_NP_RLFA | 73| 13| 2| | | | | | 12| 2100 | NP_LLFA_THEN_MRT_LOWPOINT | 74| 19| 3| 2| 1| 1| 1| | | 2101 | MRT_LOWPOINT_ONLY | 32| 31| 16| 12| 4| 3| 1| | | 2102 +------------------------------+---+---+---+---+---+---+---+---+----+ 2104 Figure 30 2106 +-------------------------------------------------------------------+ 2107 | | percentage of failure scenarios | 2108 | Topology name | protected by an alternate N hops | 2109 | and | longer than the primary path | 2110 | alternate selection +------------------------------------+ 2111 | policy evaluated | | | | | | | | | no | 2112 | | | | | | |10 |12 |14 | alt| 2113 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 2114 +------------------------------+---+---+---+---+---+---+---+---+----+ 2115 | T216(avg primary hops=5.2) | | | | | | | | | | 2116 | OPTIMAL | 60| 32| 7| 1| | | | | | 2117 | NP_LLFA | 39| 4| | | | | | | 57| 2118 | NP_LLFA_THEN_NP_RLFA | 46| 12| 2| | | | | | 41| 2119 | NP_LLFA_THEN_MRT_LOWPOINT | 48| 20| 12| 7| 5| 4| 2| 1| 1| 2120 | MRT_LOWPOINT | 28| 25| 18| 11| 7| 6| 3| 2| 1| 2121 +------------------------------+---+---+---+---+---+---+---+---+----+ 2122 | T217(avg primary hops=8.0) | | | | | | | | | | 2123 | OPTIMAL | 81| 13| 5| 1| | | | | | 2124 | NP_LLFA | 74| 3| 1| | | | | | 22| 2125 | NP_LLFA_THEN_NP_RLFA | 76| 8| 3| 1| | | | | 12| 2126 | NP_LLFA_THEN_MRT_LOWPOINT | 77| 7| 5| 4| 3| 2| 1| 1| | 2127 | MRT_LOWPOINT_ONLY | 25| 18| 18| 16| 12| 6| 3| 1| | 2128 +------------------------------+---+---+---+---+---+---+---+---+----+ 2129 | T218(avg primary hops=5.5) | | | | | | | | | | 2130 | OPTIMAL | 85| 14| 1| | | | | | | 2131 | NP_LLFA | 68| 3| | | | | | | 28| 2132 | NP_LLFA_THEN_NP_RLFA | 71| 4| | | | | | | 25| 2133 | NP_LLFA_THEN_MRT_LOWPOINT | 77| 12| 7| 4| 1| | | | | 2134 | MRT_LOWPOINT_ONLY | 37| 29| 21| 10| 3| 1| | | | 2135 +------------------------------+---+---+---+---+---+---+---+---+----+ 2136 | T219(avg primary hops=7.7) | | | | | | | | | | 2137 | OPTIMAL | 77| 15| 5| 1| 1| | | | | 2138 | NP_LLFA | 72| 5| | | | | | | 22| 2139 | NP_LLFA_THEN_NP_RLFA | 73| 8| 2| | | | | | 16| 2140 | NP_LLFA_THEN_MRT_LOWPOINT | 74| 8| 3| 3| 2| 2| 2| 2| 4| 2141 | MRT_LOWPOINT_ONLY | 19| 14| 15| 12| 10| 8| 7| 6| 10| 2142 +------------------------------+---+---+---+---+---+---+---+---+----+ 2144 Figure 31 2146 In the preceding analysis, the following procedure for selecting an 2147 RLFA was used. Nodes were ordered with respect to distance from the 2148 source and checked for membership in Q and P-space. The first node 2149 to satisfy this condition was selected as the RLFA. More 2150 sophisticated methods to select node-protecting RLFAs is an area of 2151 active research. 2153 The analysis presented above uses the MRT Lowpoint Algorithm defined 2154 in this specification with a common GADAG root. The particular 2155 choice of a common GADAG root is expected to affect the quality of 2156 the MRT alternate paths, with a more central common GADAG root 2157 resulting in shorter MRT alternate path lengths. For the analysis 2158 above, the GADAG root was chosen for each topology by calculating 2159 node centrality as the sum of costs of all shortest paths to and from 2160 a given node. The node with the lowest sum was chosen as the common 2161 GADAG root. In actual deployments, the common GADAG root would be 2162 chosen based on the GADAG Root Selection Priority advertised by each 2163 router, the values of which would be determined off-line. 2165 In order to measure how sensitive the MRT alternate path lengths are 2166 to the choice of common GADAG root, we performed the same analysis 2167 using different choices of GADAG root. All of the nodes in the 2168 network were ordered with respect to the node centrality as computed 2169 above. Nodes were chosen at the 0th, 25th, and 50th percentile with 2170 respect to the centrality ordering, with 0th percentile being the 2171 most central node. The distribution of alternate path lengths for 2172 those three choices of GADAG root are shown in Figure 32 for a subset 2173 of the 19 topologies (chosen arbitrarily). The third row for each 2174 topology (labeled MRT_LOWPOINT ( 0 percentile) ) reproduces the 2175 results presented above for MRT_LOWPOINT_ONLY. The fourth and fifth 2176 rows show the alternate path length distibution for the 25th and 50th 2177 percentile choice for GADAG root. One can see some impact on the 2178 path length distribution with the less central choice of GADAG root 2179 resulting in longer path lenghths. 2181 We also looked at the impact of MRT algorithm variant on the 2182 alternate path lengths. The first two rows for each topology present 2183 results of the same alternate path length distribution analysis for 2184 the SPF and Hybrid methods for computing the GADAG. These two 2185 methods are described in Appendix A and Appendix B. For three of the 2186 topologies in this subset (T201, T206, and T211), the use of SPF or 2187 Hybrid methods does not appear to provide a significant advantage 2188 over the Lowpoint method with respect to path length. Instead, the 2189 choice of GADAG root appears to have more impact on the path length. 2190 However, for two of the topologies in this subset(T216 and T219) and 2191 for this particular choice of GAGAG root, the use of the SPF method 2192 results in noticeably shorter alternate path lengths than the use of 2193 the Lowpoint or Hybrid methods. It remains to be determined if this 2194 effect applies generally across more topologies or is sensitive to 2195 choice of GADAG root. 2197 +-------------------------------------------------------------------+ 2198 | Topology name | percentage of failure scenarios | 2199 | | protected by an alternate N hops | 2200 | MRT algorithm variant | longer than the primary path | 2201 | +------------------------------------+ 2202 | (GADAG root | | | | | | | | | no | 2203 | centrality percentile) | | | | | |10 |12 |14 | alt| 2204 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 2205 +------------------------------+---+---+---+---+---+---+---+---+----+ 2206 | T201(avg primary hops=3.5) | | | | | | | | | | 2207 | MRT_HYBRID ( 0 percentile) | 33| 26| 23| 6| 3| | | | | 2208 | MRT_SPF ( 0 percentile) | 33| 36| 23| 6| 3| | | | | 2209 | MRT_LOWPOINT ( 0 percentile) | 33| 36| 23| 6| 3| | | | | 2210 | MRT_LOWPOINT (25 percentile) | 27| 29| 23| 11| 10| | | | | 2211 | MRT_LOWPOINT (50 percentile) | 27| 29| 23| 11| 10| | | | | 2212 +------------------------------+---+---+---+---+---+---+---+---+----+ 2213 | T206(avg primary hops=3.7) | | | | | | | | | | 2214 | MRT_HYBRID ( 0 percentile) | 50| 35| 13| 2| | | | | | 2215 | MRT_SPF ( 0 percentile) | 50| 35| 13| 2| | | | | | 2216 | MRT_LOWPOINT ( 0 percentile) | 55| 32| 13| | | | | | | 2217 | MRT_LOWPOINT (25 percentile) | 47| 25| 22| 6| | | | | | 2218 | MRT_LOWPOINT (50 percentile) | 38| 38| 14| 11| | | | | | 2219 +------------------------------+---+---+---+---+---+---+---+---+----+ 2220 | T211(avg primary hops=3.3) | | | | | | | | | | 2221 | MRT_HYBRID ( 0 percentile) | 86| 14| | | | | | | | 2222 | MRT_SPF ( 0 percentile) | 86| 14| | | | | | | | 2223 | MRT_LOWPOINT ( 0 percentile) | 85| 15| 1| | | | | | | 2224 | MRT_LOWPOINT (25 percentile) | 70| 25| 5| 1| | | | | | 2225 | MRT_LOWPOINT (50 percentile) | 80| 18| 2| | | | | | | 2226 +------------------------------+---+---+---+---+---+---+---+---+----+ 2227 | T216(avg primary hops=5.2) | | | | | | | | | | 2228 | MRT_HYBRID ( 0 percentile) | 23| 22| 18| 13| 10| 7| 4| 2| 2| 2229 | MRT_SPF ( 0 percentile) | 35| 32| 19| 9| 3| 1| | | | 2230 | MRT_LOWPOINT ( 0 percentile) | 28| 25| 18| 11| 7| 6| 3| 2| 1| 2231 | MRT_LOWPOINT (25 percentile) | 24| 20| 19| 16| 10| 6| 3| 1| | 2232 | MRT_LOWPOINT (50 percentile) | 19| 14| 13| 10| 8| 6| 5| 5| 10| 2233 +------------------------------+---+---+---+---+---+---+---+---+----+ 2234 | T219(avg primary hops=7.7) | | | | | | | | | | 2235 | MRT_HYBRID ( 0 percentile) | 20| 16| 13| 10| 7| 5| 5| 5| 3| 2236 | MRT_SPF ( 0 percentile) | 31| 23| 19| 12| 7| 4| 2| 1| | 2237 | MRT_LOWPOINT ( 0 percentile) | 19| 14| 15| 12| 10| 8| 7| 6| 10| 2238 | MRT_LOWPOINT (25 percentile) | 19| 14| 15| 13| 12| 10| 6| 5| 7| 2239 | MRT_LOWPOINT (50 percentile) | 19| 14| 14| 12| 11| 8| 6| 6| 10| 2240 +------------------------------+---+---+---+---+---+---+---+---+----+ 2242 Figure 32 2244 8. Implementation Status 2246 [RFC Editor: please remove this section prior to publication.] 2248 Please see [I-D.ietf-rtgwg-mrt-frr-architecture] for details on 2249 implementation status. 2251 9. Algorithm Work to Be Done 2253 Broadcast Interfaces: The algorithm assumes that broadcast 2254 interfaces are already represented as pseudo-nodes in the network 2255 graph. Given maximal redundancy, one of the MRT will try to avoid 2256 both the pseudo-node and the next hop. The exact rules need to be 2257 fully specified. 2259 10. Acknowledgements 2261 The authors would like to thank Shraddha Hegde for her suggestions 2262 and review. 2264 11. IANA Considerations 2266 This document includes no request to IANA. 2268 12. Security Considerations 2270 This architecture is not currently believed to introduce new security 2271 concerns. 2273 13. References 2275 13.1. Normative References 2277 [I-D.ietf-rtgwg-mrt-frr-architecture] 2278 Atlas, A., Kebler, R., Bowers, C., Enyedi, G., Csaszar, 2279 A., Tantsura, J., Konstantynowicz, M., and R. White, "An 2280 Architecture for IP/LDP Fast-Reroute Using Maximally 2281 Redundant Trees", draft-rtgwg-mrt-frr-architecture-04 2282 (work in progress), July 2014. 2284 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2285 Requirement Levels", BCP 14, RFC 2119, March 1997. 2287 13.2. Informative References 2289 [EnyediThesis] 2290 Enyedi, G., "Novel Algorithms for IP Fast Reroute", 2291 Department of Telecommunications and Media Informatics, 2292 Budapest University of Technology and Economics Ph.D. 2293 Thesis, February 2011, . 2297 [I-D.atlas-mpls-ldp-mrt] 2298 Atlas, A., Tiruveedhula, K., Tantsura, J., and IJ. 2299 Wijnands, "LDP Extensions to Support Maximally Redundant 2300 Trees", draft-atlas-mpls-ldp-mrt-01 (work in progress), 2301 July 2014. 2303 [I-D.atlas-ospf-mrt] 2304 Atlas, A., Hegde, S., Bowers, C., and J. Tantsura, "OSPF 2305 Extensions to Support Maximally Redundant Trees", draft- 2306 atlas-ospf-mrt-02 (work in progress), July 2014. 2308 [I-D.ietf-rtgwg-ipfrr-notvia-addresses] 2309 Bryant, S., Previdi, S., and M. Shand, "A Framework for IP 2310 and MPLS Fast Reroute Using Not-via Addresses", draft- 2311 ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress), 2312 May 2013. 2314 [I-D.ietf-rtgwg-lfa-manageability] 2315 Litkowski, S., Decraene, B., Filsfils, C., Raza, K., 2316 Horneffer, M., and p. psarkar@juniper.net, "Operational 2317 management of Loop Free Alternates", draft-ietf-rtgwg-lfa- 2318 manageability-03 (work in progress), February 2014. 2320 [I-D.ietf-rtgwg-remote-lfa] 2321 Bryant, S., Filsfils, C., Previdi, S., Shand, M., and S. 2322 Ning, "Remote LFA FRR", draft-ietf-rtgwg-remote-lfa-06 2323 (work in progress), May 2014. 2325 [I-D.li-isis-mrt] 2326 Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J. 2327 Tantsura, "Intermediate System to Intermediate System (IS- 2328 IS) Extensions for Maximally Redundant Trees(MRT)", draft- 2329 li-isis-mrt-01 (work in progress), July 2014. 2331 [Kahn_1962_topo_sort] 2332 Kahn, A., "Topological sorting of large networks", 2333 Communications of the ACM, Volume 5, Issue 11 , Nov 1962, 2334 . 2336 [LFARevisited] 2337 Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP 2338 Fast ReRoute: Loop Free Alternates Revisited", Proceedings 2339 of IEEE INFOCOM , 2011, 2340 . 2343 [LightweightNotVia] 2344 Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP 2345 Fast ReRoute: Lightweight Not-Via without Additional 2346 Addresses", Proceedings of IEEE INFOCOM , 2009, 2347 . 2349 [MRTLinear] 2350 Enyedi, G., Retvari, G., and A. Csaszar, "On Finding 2351 Maximally Redundant Trees in Strictly Linear Time", IEEE 2352 Symposium on Computers and Comunications (ISCC) , 2009, 2353 . 2356 [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. 2357 McPherson, "OSPF Stub Router Advertisement", RFC 3137, 2358 June 2001. 2360 [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast 2361 Reroute: Loop-Free Alternates", RFC 5286, September 2008. 2363 [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC 2364 5714, January 2010. 2366 [RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., 2367 Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free 2368 Alternate (LFA) Applicability in Service Provider (SP) 2369 Networks", RFC 6571, June 2012. 2371 Appendix A. Option 2: Computing GADAG using SPFs 2373 The basic idea in this option is to use slightly-modified SPF 2374 computations to find ears. In every block, an SPF computation is 2375 first done to find a cycle from the local root and then SPF 2376 computations in that block find ears until there are no more 2377 interfaces to be explored. The used result from the SPF computation 2378 is the path of interfaces indicated by following the previous hops 2379 from the mininized IN_GADAG node back to the SPF root. 2381 To do this, first all cut-vertices must be identified and local-roots 2382 assigned as specified in Figure 12. 2384 The slight modifications to the SPF are as follows. The root of the 2385 block is referred to as the block-root; it is either the GADAG root 2386 or a cut-vertex. 2388 a. The SPF is rooted at a neighbor x of an IN_GADAG node y. All 2389 links between y and x are marked as TEMP_UNUSABLE. They should 2390 not be used during the SPF computation. 2392 b. If y is not the block-root, then it is marked TEMP_UNUSABLE. It 2393 should not be used during the SPF computation. This prevents 2394 ears from starting and ending at the same node and avoids cycles; 2395 the exception is because cycles to/from the block-root are 2396 acceptable and expected. 2398 c. Do not explore links to nodes whose local-root is not the block- 2399 root. This keeps the SPF confined to the particular block. 2401 d. Terminate when the first IN_GADAG node z is minimized. 2403 e. Respect the existing directions (e.g. INCOMING, OUTGOING, 2404 UNDIRECTED) already specified for each interface. 2406 Mod_SPF(spf_root, block_root) 2407 Initialize spf_heap to empty 2408 Initialize nodes' spf_metric to infinity 2409 spf_root.spf_metric = 0 2410 insert(spf_heap, spf_root) 2411 found_in_gadag = false 2412 while (spf_heap is not empty) and (found_in_gadag is false) 2413 min_node = remove_lowest(spf_heap) 2414 if min_node.IN_GADAG is true 2415 found_in_gadag = true 2416 else 2417 foreach interface intf of min_node 2418 if ((intf.OUTGOING or intf.UNDIRECTED) and 2419 ((intf.remote_node.localroot is block_root) or 2420 (intf.remote_node is block_root)) and 2421 (intf.remote_node is not TEMP_UNUSABLE) and 2422 (intf is not TEMP_UNUSABLE)) 2423 path_metric = min_node.spf_metric + intf.metric 2424 if path_metric < intf.remote_node.spf_metric 2425 intf.remote_node.spf_metric = path_metric 2426 intf.remote_node.spf_prev_intf = intf 2427 insert_or_update(spf_heap, intf.remote_node) 2428 return min_node 2430 SPF_for_Ear(cand_intf.local_node,cand_intf.remote_node, block_root, 2431 method) 2432 Mark all interfaces between cand_intf.remote_node 2433 and cand_intf.local_node as TEMP_UNUSABLE 2434 if cand_intf.local_node is not block_root 2435 Mark cand_intf.local_node as TEMP_UNUSABLE 2436 Initialize ear_list to empty 2437 end_ear = Mod_SPF(spf_root, block_root) 2438 y = end_ear.spf_prev_hop 2439 while y.local_node is not spf_root 2440 add_to_list_start(ear_list, y) 2441 y.local_node.IN_GADAG = true 2442 y = y.local_node.spf_prev_intf 2443 if(method is not hybrid) 2444 Set_Ear_Direction(ear_list, cand_intf.local_node, 2445 end_ear,block_root) 2446 Clear TEMP_UNUSABLE from all interfaces between 2447 cand_intf.remote_node and cand_intf.local_node 2448 Clear TEMP_UNUSABLE from cand_intf.local_node 2449 return end_ear 2451 Figure 33: Modified SPF for GADAG computation 2453 Assume that an ear is found by going from y to x and then running an 2454 SPF that terminates by minimizing z (e.g. y<->x...q<->z). Now it is 2455 necessary to determine the direction of the ear; if y << z, then the 2456 path should be y->x...q->z but if y >> z, then the path should be y<- 2457 x...q<-z. In Section 5.4, the same problem was handled by finding 2458 all ears that started at a node before looking at ears starting at 2459 nodes higher in the partial order. In this algorithm, using that 2460 approach could mean that new ears aren't added in order of their 2461 total cost since all ears connected to a node would need to be found 2462 before additional nodes could be found. 2464 The alternative is to track the order relationship of each node with 2465 respect to every other node. This can be accomplished by maintaining 2466 two sets of nodes at each node. The first set, Higher_Nodes, 2467 contains all nodes that are known to be ordered above the node. The 2468 second set, Lower_Nodes, contains all nodes that are known to be 2469 ordered below the node. This is the approach used in this algorithm. 2471 Set_Ear_Direction(ear_list, end_a, end_b, block_root) 2472 // Default of A_TO_B for the following cases: 2473 // (a) end_a and end_b are the same (root) 2474 // or (b) end_a is in end_b's Lower Nodes 2475 // or (c) end_a and end_b were unordered with respect to each 2476 // other 2477 direction = A_TO_B 2478 if (end_b is block_root) and (end_a is not end_b) 2479 direction = B_TO_A 2480 else if end_a is in end_b.Higher_Nodes 2481 direction = B_TO_A 2482 if direction is B_TO_A 2483 foreach interface i in ear_list 2484 i.UNDIRECTED = false 2485 i.INCOMING = true 2486 i.remote_intf.UNDIRECTED = false 2487 i.remote_intf.OUTGOING = true 2488 else 2489 foreach interface i in ear_list 2490 i.UNDIRECTED = false 2491 i.OUTGOING = true 2492 i.remote_intf.UNDIRECTED = false 2493 i.remote_intf.INCOMING = true 2494 if end_a is end_b 2495 return 2496 // Next, update all nodes' Lower_Nodes and Higher_Nodes 2497 if (end_a is in end_b.Higher_Nodes) 2498 foreach node x where x.localroot is block_root 2499 if end_a is in x.Lower_Nodes 2500 foreach interface i in ear_list 2501 add i.remote_node to x.Lower_Nodes 2502 if end_b is in x.Higher_Nodes 2503 foreach interface i in ear_list 2504 add i.local_node to x.Higher_Nodes 2505 else 2506 foreach node x where x.localroot is block_root 2507 if end_b is in x.Lower_Nodes 2508 foreach interface i in ear_list 2509 add i.local_node to x.Lower_Nodes 2510 if end_a is in x.Higher_Nodes 2511 foreach interface i in ear_list 2512 add i.remote_node to x.Higher_Nodes 2514 Figure 34: Algorithm to assign links of an ear direction 2516 A goal of the algorithm is to find the shortest cycles and ears. An 2517 ear is started by going to a neighbor x of an IN_GADAG node y. The 2518 path from x to an IN_GADAG node is minimal, since it is computed via 2519 SPF. Since a shortest path is made of shortest paths, to find the 2520 shortest ears requires reaching from the set of IN_GADAG nodes to the 2521 closest node that isn't IN_GADAG. Therefore, an ordered tree is 2522 maintained of interfaces that could be explored from the IN_GADAG 2523 nodes. The interfaces are ordered by their characteristics of 2524 metric, local loopback address, remote loopback address, and ifindex, 2525 as in the algorithm previously described in Figure 14. 2527 The algorithm ignores interfaces picked from the ordered tree that 2528 belong to the block root if the block in which the interface is 2529 present already has an ear that has been computed. This is necessary 2530 since we allow at most one incoming interface to a block root in each 2531 block. This requirement stems from the way next-hops are computed as 2532 was seen in Section 5.6. After any ear gets computed, we traverse 2533 the newly added nodes to the GADAG and insert interfaces whose far 2534 end is not yet on the GADAG to the ordered tree for later processing. 2536 Finally, cut-links are a special case because there is no point in 2537 doing an SPF on a block of 2 nodes. The algorithm identifies cut- 2538 links simply as links where both ends of the link are cut-vertices. 2539 Cut-links can simply be added to the GADAG with both OUTGOING and 2540 INCOMING specified on their interfaces. 2542 add_eligible_interfaces_of_node(ordered_intfs_tree,node) 2543 for each interface of node 2544 if intf.remote_node.IN_GADAG is false 2545 insert(intf,ordered_intfs_tree) 2547 check_if_block_has_ear(x,block_id) 2548 block_has_ear = false 2549 for all interfaces of x 2550 if (intf.remote_node.block_id == block_id) && 2551 (intf.remote_node.IN_GADAG is true) 2552 block_has_ear = true 2553 return block_has_ear 2555 Construct_GADAG_via_SPF(topology, root) 2556 Compute_Localroot (root,root) 2557 Assign_Block_ID(root,0) 2558 root.IN_GADAG = true 2559 add_eligible_interfaces_of_node(ordered_intfs_tree,root) 2560 while ordered_intfs_tree is not empty 2561 cand_intf = remove_lowest(ordered_intfs_tree) 2562 if cand_intf.remote_node.IN_GADAG is false 2563 if L(cand_intf.remote_node) == D(cand_intf.remote_node) 2564 // Special case for cut-links 2565 cand_intf.UNDIRECTED = false 2566 cand_intf.remote_intf.UNDIRECTED = false 2567 cand_intf.OUTGOING = true 2568 cand_intf.INCOMING = true 2569 cand_intf.remote_intf.OUTGOING = true 2570 cand_intf.remote_intf.INCOMING = true 2571 cand_intf.remote_node.IN_GADAG = true 2572 add_eligible_interfaces_of_node( 2573 ordered_intfs_tree,cand_intf.remote_node) 2574 else 2575 if (cand_intf.remote_node.local_root == 2576 cand_intf.local_node) && 2577 check_if_block_has_ear 2578 (cand_intf.local_node, 2579 cand_intf.remote_node.block_id)) 2580 /* Skip the interface since the block root 2581 already has an incoming interface in the 2582 block */ 2583 else 2584 ear_end = SPF_for_Ear(cand_intf.local_node, 2585 cand_intf.remote_node, 2586 cand_intf.remote_node.localroot, 2587 SPF method) 2588 y = ear_end.spf_prev_hop 2589 while y.local_node is not cand_intf.local_node 2590 add_eligible_interfaces_of_node( 2591 ordered_intfs_tree, 2592 y.local_node) 2593 y = y.local_node.spf_prev_intf 2595 Figure 35: SPF-based GADAG algorithm 2597 Appendix B. Option 3: Computing GADAG using a hybrid method 2599 In this option, the idea is to combine the salient features of the 2600 lowpoint inheritance and SPF methods. To this end, we process nodes 2601 as they get added to the GADAG just like in the lowpoint inheritance 2602 by maintaining a stack of nodes. This ensures that we do not need to 2603 maintain lower and higher sets at each node to ascertain ear 2604 directions since the ears will always be directed from the node being 2605 processed towards the end of the ear. To compute the ear however, we 2606 resort to an SPF to have the possibility of better ears (path 2607 lentghs) thus giving more flexibility than the restricted use of 2608 lowpoint/dfs parents. 2610 Regarding ears involving a block root, unlike the SPF method which 2611 ignored interfaces of the block root after the first ear, in the 2612 hybrid method we would have to process all interfaces of the block 2613 root before moving on to other nodes in the block since the direction 2614 of an ear is pre-determined. Thus, whenever the block already has an 2615 ear computed, and we are processing an interface of the block root, 2616 we mark the block root as unusable before the SPF run that computes 2617 the ear. This ensures that the SPF terminates at some node other 2618 than the block-root. This in turn guarantees that the block-root has 2619 only one incoming interface in each block, which is necessary for 2620 correctly computing the next-hops on the GADAG. 2622 As in the SPF gadag, bridge ears are handled as a special case. 2624 The entire algorithm is shown below in Figure 36 2626 find_spf_stack_ear(stack, x, y, xy_intf, block_root) 2627 if L(y) == D(y) 2628 // Special case for cut-links 2629 xy_intf.UNDIRECTED = false 2630 xy_intf.remote_intf.UNDIRECTED = false 2631 xy_intf.OUTGOING = true 2632 xy_intf.INCOMING = true 2633 xy_intf.remote_intf.OUTGOING = true 2634 xy_intf.remote_intf.INCOMING = true 2635 xy_intf.remote_node.IN_GADAG = true 2636 push y onto stack 2637 return 2638 else 2639 if (y.local_root == x) && 2640 check_if_block_has_ear(x,y.block_id) 2641 //Avoid the block root during the SPF 2642 Mark x as TEMP_UNUSABLE 2643 end_ear = SPF_for_Ear(x,y,block_root,hybrid) 2644 If x was set as TEMP_UNUSABLE, clear it 2645 cur = end_ear 2646 while (cur != y) 2647 intf = cur.spf_prev_hop 2648 prev = intf.local_node 2649 intf.UNDIRECTED = false 2650 intf.remote_intf.UNDIRECTED = false 2651 intf.OUTGOING = true 2652 intf.remote_intf.INCOMING = true 2653 push prev onto stack 2654 cur = prev 2655 xy_intf.UNDIRECTED = false 2656 xy_intf.remote_intf.UNDIRECTED = false 2657 xy_intf.OUTGOING = true 2658 xy_intf.remote_intf.INCOMING = true 2659 return 2661 Construct_GADAG_via_hybrid(topology,root) 2662 Compute_Localroot (root,root) 2663 Assign_Block_ID(root,0) 2664 root.IN_GADAG = true 2665 Initialize Stack to empty 2666 push root onto Stack 2667 while (Stack is not empty) 2668 x = pop(Stack) 2669 for each interface intf of x 2670 y = intf.remote_node 2671 if y.IN_GADAG is false 2672 find_spf_stack_ear(stack, x, y, intf, y.block_root) 2674 Figure 36: Hybrid GADAG algorithm 2676 Authors' Addresses 2678 Gabor Sandor Enyedi (editor) 2679 Ericsson 2680 Konyves Kalman krt 11 2681 Budapest 1097 2682 Hungary 2684 Email: Gabor.Sandor.Enyedi@ericsson.com 2686 Andras Csaszar 2687 Ericsson 2688 Konyves Kalman krt 11 2689 Budapest 1097 2690 Hungary 2692 Email: Andras.Csaszar@ericsson.com 2694 Alia Atlas (editor) 2695 Juniper Networks 2696 10 Technology Park Drive 2697 Westford, MA 01886 2698 USA 2700 Email: akatlas@juniper.net 2701 Chris Bowers 2702 Juniper Networks 2703 1194 N. Mathilda Ave. 2704 Sunnyvale, CA 94089 2705 USA 2707 Email: cbowers@juniper.net 2709 Abishek Gopalan 2710 University of Arizona 2711 1230 E Speedway Blvd. 2712 Tucson, AZ 85721 2713 USA 2715 Email: abishek@ece.arizona.edu