idnits 2.17.00 (12 Aug 2021) /tmp/idnits11222/draft-enyedi-rtgwg-mrt-frr-algorithm-03.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. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 761: '...in computation, all routers MUST order...' RFC 2119 keyword, line 1589: '...node attachments MUST be determined. ...' RFC 2119 keyword, line 1687: '...e in the graph. An implementation MAY...' RFC 2119 keyword, line 1694: '...omputing router, MUST be one or more n...' RFC 2119 keyword, line 1696: '...RT-Red next-hops MUST be have a topo_o...' (1 more instance...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 15, 2013) is 3232 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: Informational ---------------------------------------------------------------------------- == Missing Reference: 'R' is mentioned on line 1557, but not defined == Missing Reference: 'F' is mentioned on line 618, but not defined == Missing Reference: 'C' is mentioned on line 1557, but not defined == Missing Reference: 'G' is mentioned on line 1557, but not defined == Missing Reference: 'E' is mentioned on line 298, but not defined == Missing Reference: 'D' is mentioned on line 618, but not defined == Missing Reference: 'J' is mentioned on line 166, but not defined == Missing Reference: 'A' is mentioned on line 298, but not defined == Missing Reference: 'B' is mentioned on line 172, but not defined == Missing Reference: 'H' is mentioned on line 1141, but not defined == Missing Reference: 'K' is mentioned on line 618, but not defined == Missing Reference: 'N' is mentioned on line 618, but not defined == Missing Reference: 'X' is mentioned on line 1141, but not defined == Missing Reference: 'Y' is mentioned on line 1141, but not defined == Missing Reference: 'R-small' is mentioned on line 1099, but not defined == Missing Reference: 'R-great' is mentioned on line 1116, but not defined == Missing Reference: 'I' is mentioned on line 1557, but not defined == Unused Reference: 'I-D.ietf-rtgwg-ipfrr-notvia-addresses' is defined on line 1955, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-rtgwg-remote-lfa' is defined on line 1967, but no explicit reference was found in the text == Unused Reference: 'LFARevisited' is defined on line 1977, but no explicit reference was found in the text == Unused Reference: 'LightweightNotVia' is defined on line 1983, but no explicit reference was found in the text == Unused Reference: 'RFC5286' is defined on line 2000, but no explicit reference was found in the text == Unused Reference: 'RFC5714' is defined on line 2003, but no explicit reference was found in the text == Unused Reference: 'RFC6571' is defined on line 2006, but no explicit reference was found in the text == Outdated reference: draft-ietf-rtgwg-mrt-frr-architecture has been published as RFC 7812 == Outdated reference: A later version (-03) exists of draft-atlas-ospf-mrt-00 == Outdated reference: draft-ietf-rtgwg-ipfrr-notvia-addresses has been published as RFC 6981 == Outdated reference: draft-ietf-rtgwg-lfa-manageability has been published as RFC 7916 == Outdated reference: draft-ietf-rtgwg-remote-lfa has been published as RFC 7490 -- Obsolete informational reference (is this intentional?): RFC 3137 (Obsoleted by RFC 6987) Summary: 2 errors (**), 0 flaws (~~), 31 warnings (==), 3 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: Informational Ericsson 5 Expires: January 16, 2014 A. Atlas, Ed. 6 C. Bowers 7 Juniper Networks 8 A. Gopalan 9 University of Arizona 10 July 15, 2013 12 Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- 13 Reroute 14 draft-enyedi-rtgwg-mrt-frr-algorithm-03 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 16, 2014. 42 Copyright Notice 44 Copyright (c) 2013 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. Terminology and Definitions . . . . . . . . . . . . . . . . . 4 61 3. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 6 62 3.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 6 63 3.2. Finding an Ear and the Correct Direction . . . . . . . . 8 64 3.3. Low-Point Values and Their Uses . . . . . . . . . . . . . 11 65 3.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 13 66 3.5. Determining Local-Root and Assigning Block-ID . . . . . . 15 67 4. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 16 68 4.1. MRT Island Identification . . . . . . . . . . . . . . . . 17 69 4.2. Root Selection . . . . . . . . . . . . . . . . . . . . . 18 70 4.3. Initialization . . . . . . . . . . . . . . . . . . . . . 18 71 4.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint 72 inheritance . . . . . . . . . . . . . . . . . . . . . . . 19 73 4.5. Augmenting the GADAG by directing all links . . . . . . . 21 74 4.6. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 23 75 4.6.1. MRT next-hops to all nodes partially ordered with 76 respect to the computing node . . . . . . . . . . . . 24 77 4.6.2. MRT next-hops to all nodes not partially ordered with 78 respect to the computing node . . . . . . . . . . . . 24 79 4.6.3. Computing Redundant Tree next-hops in a 2-connected 80 Graph . . . . . . . . . . . . . . . . . . . . . . . . 25 81 4.6.4. Generalizing for graph that isn't 2-connected . . . . 27 82 4.6.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 28 83 4.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 30 84 4.8. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 34 85 5. MRT Lowpoint Algorithm: Complete Specification . . . . . . . 36 86 6. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 37 87 6.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 37 88 7. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 41 89 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 42 90 9. Security Considerations . . . . . . . . . . . . . . . . . . . 42 91 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 42 92 10.1. Normative References . . . . . . . . . . . . . . . . . . 42 93 10.2. Informative References . . . . . . . . . . . . . . . . . 42 94 Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 44 95 Appendix B. Option 3: Computing GADAG using a hybrid method . . 48 96 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 50 98 1. Introduction 100 MRT Fast-Reroute requires that packets can be forwarded not only on 101 the shortest-path tree, but also on two Maximally Redundant Trees 102 (MRTs), referred to as the MRT-Blue and the MRT-Red. A router which 103 experiences a local failure must also have pre-determined which 104 alternate to use. This document defines how to compute these three 105 things for use in MRT-FRR and describes the algorithm design 106 decisions and rationale. The algorithm is based on those presented 107 in [MRTLinear] and expanded in [EnyediThesis]. 109 Just as packets routed on a hop-by-hop basis require that each router 110 compute a shortest-path tree which is consistent, it is necessary for 111 each router to compute the MRT-Blue next-hops and MRT-Red next-hops 112 in a consistent fashion. This document defines the MRT Lowpoint 113 algorithm to be used as a standard in the default MRT profile for 114 MRT-FRR. 116 As now, a router's FIB will contain primary next-hops for the current 117 shortest-path tree for forwarding traffic. In addition, a router's 118 FIB will contain primary next-hops for the MRT-Blue for forwarding 119 received traffic on the MRT-Blue and primary next-hops for the MRT- 120 Red for forwarding received traffic on the MRT-Red. 122 What alternate next-hops a point-of-local-repair (PLR) selects need 123 not be consistent - but loops must be prevented. To reduce 124 congestion, it is possible for multiple alternate next-hops to be 125 selected; in the context of MRT alternates, each of those alternate 126 next-hops would be equal-cost paths. 128 This document defines an algorithm for selecting an appropriate MRT 129 alternate for consideration. Other alternates, e.g. LFAs that are 130 downstream paths, may be prefered when available and that policy- 131 based alternate selection process[I-D.ietf-rtgwg-lfa-manageability] 132 is not captured in this document. 134 [E]---[D]---| [E]<--[D]<--| [E]-->[D] 135 | | | | ^ | | 136 | | | V | | V 137 [R] [F] [C] [R] [F] [C] [R] [F] [C] 138 | | | ^ ^ | | 139 | | | | | V | 140 [A]---[B]---| [A]-->[B] [A]---[B]<--| 142 (a) (b) (c) 143 a 2-connected graph MRT-Blue towards R MRT-Red towards R 145 Figure 1 147 Algorithms for computing MRTs can handle arbitrary network topologies 148 where the whole network graph is not 2-connected, as in Figure 2, as 149 well as the easier case where the network graph is 2-connected 150 (Figure 1). Each MRT is a spanning tree. The pair of MRTs provide 151 two paths from every node X to the root of the MRTs. Those paths 152 share the minimum number of nodes and the minimum number of links. 153 Each such shared node is a cut-vertex. Any shared links are cut- 154 links. 156 [E]---[D]---| |---[J] 157 | | | | | 158 | | | | | 159 [R] [F] [C]---[G] | 160 | | | | | 161 | | | | | 162 [A]---[B]---| |---[H] 164 (a) a graph that isn't 2-connected 166 [E]<--[D]<--| [J] [E]-->[D]---| |---[J] 167 | ^ | | | | | ^ 168 V | | | V V V | 169 [R] [F] [C]<--[G] | [R] [F] [C]<--[G] | 170 ^ ^ ^ | ^ | | | 171 | | | V | V | | 172 [A]-->[B]---| |---[H] [A]<--[B]<--| [H] 174 (b) MRT-Blue towards R (c) MRT-Red towards R 176 Figure 2 178 2. Terminology and Definitions 180 network graph: A graph that reflects the network topology where all 181 links connect exactly two nodes and broadcast links have been 182 transformed into the standard pseudo-node representation. 184 Redundant Trees (RT): A pair of trees where the path from any node X 185 to the root R on the first tree is node-disjoint with the path 186 from the same node X to the root along the second tree. These can 187 be computed in 2-connected graphs. 189 Maximally Redundant Trees (MRT): A pair of trees where the path 190 from any node X to the root R along the first tree and the path 191 from the same node X to the root along the second tree share the 192 minimum number of nodes and the minimum number of links. Each 193 such shared node is a cut-vertex. Any shared links are cut-links. 194 Any RT is an MRT but many MRTs are not RTs. 196 MRT-Red: MRT-Red is used to describe one of the two MRTs; it is 197 used to described the associated forwarding topology and MT-ID. 198 Specifically, MRT-Red is the decreasing MRT where links in the 199 GADAG are taken in the direction from a higher topologically 200 ordered node to a lower one. 202 MRT-Blue: MRT-Blue is used to describe one of the two MRTs; it is 203 used to described the associated forwarding topology and MT-ID. 204 Specifically, MRT-Blue is the increasing MRT where links in the 205 GADAG are taken in the direction from a lower topologically 206 ordered node to a higher one. 208 cut-vertex: A vertex whose removal partitions the network. 210 cut-link: A link whose removal partitions the network. A cut-link 211 by definition must be connected between two cut-vertices. If 212 there are multiple parallel links, then they are referred to as 213 cut-links in this document if removing the set of parallel links 214 would partition the network. 216 2-connected: A graph that has no cut-vertices. This is a graph 217 that requires two nodes to be removed before the network is 218 partitioned. 220 spanning tree: A tree containing links that connects all nodes in 221 the network graph. 223 back-edge: In the context of a spanning tree computed via a depth- 224 first search, a back-edge is a link that connects a descendant of 225 a node x with an ancestor of x. 227 2-connected cluster: A maximal set of nodes that are 2-connected. 228 In a network graph with at least one cut-vertex, there will be 229 multiple 2-connected clusters. 231 block: Either a 2-connected cluster, a cut-edge, or an isolated 232 vertex. 234 DAG: Directed Acyclic Graph - a digraph containing no directed 235 cycle. 237 ADAG: Almost Directed Acyclic Graph - a digraph that can be 238 transformed into a DAG whith removing a single node (the root 239 node). 241 GADAG: Generalized ADAG - a digraph, which has only ADAGs as all of 242 its blocks. The root of such a block is the node closest to the 243 global root (e.g. with uniform link costs). 245 DFS: Depth-First Search 247 DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS- 248 tree path from the DFS root to x. 250 DFS descendant: A node n is a DFS descendant of x if x is on the 251 DFS-tree path from the DFS root to n. 253 ear: A path along not-yet-included-in-the-GADAG nodes that starts 254 at a node that is already-included-in-the-GADAG and that ends at a 255 node that is already-included-in-the-GADAG. The starting and 256 ending nodes may be the same node if it is a cut-vertex. 258 X >> Y or Y << X: Indicates the relationship between X and Y in a 259 partial order, such as found in a GADAG. X >> Y means that X is 260 higher in the partial order than Y. Y << X means that Y is lower 261 in the partial order than X. 263 X > Y or Y < X: Indicates the relationship between X and Y in the 264 total order, such as found via a topological sort. X > Y means 265 that X is higher in the total order than Y. Y < X means that Y is 266 lower in the total order than X. 268 proxy-node: A node added to the network graph to represent a multi- 269 homed prefix or routers outside the local MRT-fast-reroute- 270 supporting island of routers. The key property of proxy-nodes is 271 that traffic cannot transit them. 273 3. Algorithm Key Concepts 275 There are five key concepts that are critical for understanding the 276 MRT Lowpoint algorithm and other algorithms for computing MRTs. The 277 first is the idea of partially ordering the nodes in a network graph 278 with regard to each other and to the GADAG root. The second is the 279 idea of finding an ear of nodes and adding them in the correct 280 direction. The third is the idea of a Low-Point value and how it can 281 be used to identify cut-vertices and to find a second path towards 282 the root. The fourth is the idea that a non-2-connected graph is 283 made up of blocks, where a block is a 2-connected cluster, a cut-edge 284 or an isolated node. The fifth is the idea of a local-root for each 285 node; this is used to compute ADAGs in each block. 287 3.1. Partial Ordering for Disjoint Paths 289 Given any two nodes X and Y in a graph, a particular total order 290 means that either X < Y or X > Y in that total order. An example 291 would be a graph where the nodes are ranked based upon their unique 292 IP loopback addresses. In a partial order, there may be some nodes 293 for which it can't be determined whether X << Y or X >> Y. A partial 294 order can be captured in a directed graph, as shown in Figure 3. In 295 a graphical representation, a link directed from X to Y indicates 296 that X is a neighbor of Y in the network graph and X << Y. 298 [A]<---[R] [E] R << A << B << C << D << E 299 | ^ R << A << B << F << G << H << D << E 300 | | 301 V | Unspecified Relationships: 302 [B]--->[C]--->[D] C and F 303 | ^ C and G 304 | | C and H 305 V | 306 [F]--->[G]--->[H] 308 Figure 3: Directed Graph showing a Partial Order 310 To compute MRTs, the root of the MRTs is at both the very bottom and 311 the very top of the partial ordering. This means that from any node 312 X, one can pick nodes higher in the order until the root is reached. 313 Similarly, from any node X, one can pick nodes lower in the order 314 until the root is reached. For instance, in Figure 4, from G the 315 higher nodes picked can be traced by following the directed links and 316 are H, D, E and R. Similarly, from G the lower nodes picked can be 317 traced by reversing the directed links and are F, B, A, and R. A 318 graph that represents this modified partial order is no longer a DAG; 319 it is termed an Almost DAG (ADAG) because if the links directed to 320 the root were removed, it would be a DAG. 322 [A]<---[R]<---[E] R << A << B << C << R 323 | ^ ^ R << A << B << C << D << E << R 324 | | | R << A << B << F << G << H << D << E << R 325 V | | 326 [B]--->[C]--->[D] Unspecified Relationships: 327 | ^ C and F 328 | | C and G 329 V | C and H 330 [F]--->[G]--->[H] 332 Figure 4: ADAG showing a Partial Order with R lowest and highest 334 Most importantly, if a node Y >> X, then Y can only appear on the 335 increasing path from X to the root and never on the decreasing path. 336 Similarly, if a node Z << X, then Z can only appear on the decreasing 337 path from X to the root and never on the inceasing path. 339 When following the increasing paths, it is possible to pick multiple 340 higher nodes and still have the certainty that those paths will be 341 disjoint from the decreasing paths. E.g. in the previous example 342 node B has multiple possibilities to forward packets along an 343 increasing path: it can either forward packets to C or F. 345 3.2. Finding an Ear and the Correct Direction 347 For simplicity, the basic idea of creating a GADAG by adding ears is 348 described assuming that the network graph is a single 2-connected 349 cluster so that an ADAG is sufficient. Generalizing to multiple 350 blocks is done by considering the block-roots instead of the GADAG 351 root - and the actual algorithm is given in Section 4.4. 353 In order to understand the basic idea of finding an ADAG, first 354 suppose that we have already a partial ADAG, which doesn't contain 355 all the nodes in the block yet, and we want to extend it to cover all 356 the nodes. Suppose that we find a path from a node X to Y such that 357 X and Y are already contained by our partial ADAG, but all the 358 remaining nodes along the path are not added to the ADAG yet. We 359 refer to such a path as an ear. 361 Recall that our ADAG is closely related to a partial order, more 362 precisely, if we remove root R, the remaining DAG describes a partial 363 order of the nodes. If we suppose that neither X nor Y is the root, 364 we may be able to compare them. If one of them is definitely lesser 365 with respect to our partial order (say X<B---| A-->B---| 377 (a) (b) (c) 379 (a) A 2-connected graph 380 (b) Partial ADAG (C is not included) 381 (c) Resulting ADAG after adding path (or ear) B-C-D 382 Figure 5 384 In this partial ADAG, node C is not yet included. However, we can 385 find path B-C-D, where both endpoints are contained by this partial 386 ADAG (we say those nodes are *ready* in the sequel), and the 387 remaining node (node C) is not contained yet. If we remove R, the 388 remaining DAG defines a partial order, and with respect to this 389 partial order we can say that B<C and C->D are added). If 391 B were strictly greater than D, we would add the same path in reverse 392 direction. 394 If in the partial order where an ear's two ends are X and Y, X << Y, 395 then there must already be a directed path from X to Y already in the 396 ADAG. The ear must be added in a direction such that it doesn't 397 create a cycle; therefore the ear must go from X to Y. 399 In the case, when X and Y are not ordered with each other, we can 400 select either direction for the ear. We have no restriction since 401 neither of the directions can result in a cycle. In the corner case 402 when one of the endpoints of an ear, say X, is the root (recall that 403 the two endpoints must be different), we could use both directions 404 again for the ear because the root can be considered both as smaller 405 and as greater than Y. However, we strictly pick that direction in 406 which the root is lower than Y. The logic for this decision is 407 explained in Section 4.6 409 A partial ADAG is started by finding a cycle from the root R back to 410 itself. This can be done by selecting a non-ready neighbor N of R 411 and then finding a path from N to R that doesn't use any links 412 between R and N. The direction of the cycle can be assigned either 413 way since it is starting the ordering. 415 Once a partial ADAG is already present, we can always add ears to it: 416 just select a non-ready neighbor N of a ready node Q, such that Q is 417 not the root, find a path from N to the root in the graph with Q 418 removed. This path is an ear where the first node of the ear is Q, 419 the next is N, then the path until the first ready node the path 420 reached (that second ready node is the other endpoint of the path). 421 Since the graph is 2-connected, there must be a path from N to R 422 without Q. 424 It is always possible to select a non-ready neighbor N of a ready 425 node Q so that Q is not the root R. Because the network is 426 2-connected, N must be connected to two different nodes and only one 427 can be R. Because the initial cycle has already been added to the 428 ADAG, there are ready nodes that are not R. Since the graph is 429 2-connected, while there are non-ready nodes, there must be a non- 430 ready neighbor N of a ready node that is not R. 432 Generic_Find_Ears_ADAG(root) 433 Create an empty ADAG. Add root to the ADAG. 434 Mark root as IN_GADAG. 435 Select an arbitrary cycle containing root. 436 Add the arbitrary cycle to the ADAG. 437 Mark cycle's nodes as IN_GADAG. 438 Add cycle's non-root nodes to process_list. 439 while there exists connected nodes in graph that are not IN_GADAG 440 Select a new ear. Let its endpoints be X and Y. 441 if Y is root or (Y << X) 442 add the ear towards X to the ADAG 443 else // (a) X is root or (b)X << Y or (c) X, Y not ordered 444 Add the ear towards Y to the ADAG 446 Figure 6: Generic Algorithm to find ears and their direction in 447 2-connected graph 449 Algorithm Figure 6 merely requires that a cycle or ear be selected 450 without specifying how. Regardless of the way of selecting the path, 451 we will get an ADAG. The method used for finding and selecting the 452 ears is important; shorter ears result in shorter paths along the 453 MRTs. The MRT Lowpoint algorithm's method using Low-Point 454 Inheritance is defined in Section 4.4. Other methods are described 455 in the Appendices (Appendix A and Appendix B). 457 As an example, consider Figure 5 again. First, we select the 458 shortest cycle containing R, which can be R-A-B-F-D-E (uniform link 459 costs were assumed), so we get to the situation depicted in Figure 5 460 (b). Finally, we find a node next to a ready node; that must be node 461 C and assume we reached it from ready node B. We search a path from C 462 to R without B in the original graph. The first ready node along 463 this is node D, so the open ear is B-C-D. Since B<C 464 and C->D to the ADAG. Since all the nodes are ready, we stop at this 465 point. 467 3.3. Low-Point Values and Their Uses 469 A basic way of computing a spanning tree on a network graph is to run 470 a depth-first-search, such as given in Figure 7. This tree has the 471 important property that if there is a link (x, n), then either n is a 472 DFS ancestor of x or n is a DFS descendant of x. In other words, 473 either n is on the path from the root to x or x is on the path from 474 the root to n. 476 global_variable: dfs_number 478 DFS_Visit(node x, node parent) 479 D(x) = dfs_number 480 dfs_number += 1 481 x.dfs_parent = parent 482 for each link (x, w) 483 if D(w) is not set 484 DFS_Visit(w, x) 486 Run_DFS(node root) 487 dfs_number = 0 488 DFS_Visit(root, NONE) 490 Figure 7: Basic Depth-First Search algorithm 492 Given a node x, one can compute the minimal DFS number of the 493 neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the 494 highest attachment point neighbouring x. What is interesting, 495 though, is what is the highest attachment point from x and x's 496 descendants. This is what is determined by computing the Low-Point 497 value, as given in Algorithm Figure 9 and illustrated on a graph in 498 Figure 8. 500 [E]---| [J]-------[I] [P]---[O] 501 | | | | | | 502 | | | | | | 503 [R] [D]---[C]--[F] [H]---[K] [N] 504 | | | | | | 505 | | | | | | 506 [A]--------[B] [G]---| [L]---[M] 508 (a) a non-2-connected graph 510 [E]----| [J]---------[I] [P]------[O] 511 (5, ) | (10, ) (9, ) (16, ) (15, ) 512 | | | | | | 513 | | | | | | 514 [R] [D]---[C]---[F] [H]----[K] [N] 516 (0, ) (4, ) (3, ) (6, ) (8, ) (11, ) (14, ) 517 | | | | | | 518 | | | | | | 519 [A]---------[B] [G]----| [L]------[M] 520 (1, ) (2, ) (7, ) (12, ) (13, ) 522 (b) with DFS values assigned (D(x), L(x)) 524 [E]----| [J]---------[I] [P]------[O] 525 (5,0) | (10,3) (9,3) (16,11) (15,11) 526 | | | | | | 527 | | | | | | 528 [R] [D]---[C]---[F] [H]----[K] [N] 529 (0, ) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11) 530 | | | | | | 531 | | | | | | 532 [A]---------[B] [G]----| [L]------[M] 533 (1,0) (2,0) (7,3) (12,11) (13,11) 535 (c) with low-point values assigned (D(x), L(x)) 537 Figure 8 539 global_variable: dfs_number 541 Lowpoint_Visit(node x, node parent, interface p_to_x) 542 D(x) = dfs_number 543 L(x) = D(x) 544 dfs_number += 1 545 x.dfs_parent = parent 546 x.dfs_parent_intf = p_to_x 547 x.lowpoint_parent = NONE 548 for each interface intf of x: 549 if D(intf.remote_node) is not set 550 Lowpoint_Visit(intf.remote_node, x, intf) 551 if L(intf.remote_node) < L(x) 552 L(x) = L(intf.remote_node) 553 x.lowpoint_parent = intf.remote_node 554 x.lowpoint_parent_intf = intf 555 else if intf.remote_node is not parent 556 if D(intf.remote_node) < L(x) 557 L(x) = D(intf.remote) 558 x.lowpoint_parent = intf.remote_node 559 x.lowpoint_parent_intf = intf 561 Run_Lowpoint(node root) 562 dfs_number = 0 563 Lowpoint_Visit(root, NONE, NONE) 565 Figure 9: Computing Low-Point value 567 From the low-point value and lowpoint parent, there are two very 568 useful things which motivate our computation. 570 First, if there is a child c of x such that L(c) >= D(x), then there 571 are no paths in the network graph that go from c or its descendants 572 to an ancestor of x - and therefore x is a cut-vertex. This is 573 useful because it allows identification of the cut-vertices and thus 574 the blocks. As seen in Figure 8, even if L(x) < D(x), there may be a 575 block that contains both the root and a DFS-child of a node while 576 other DFS-children might be in different blocks. In this example, 577 C's child D is in the same block as R while F is not. 579 Second, by repeatedly following the path given by lowpoint_parent, 580 there is a path from x back to an ancestor of x that does not use the 581 link [x, x.dfs_parent] in either direction. The full path need not 582 be taken, but this gives a way of finding an initial cycle and then 583 ears. 585 3.4. Blocks in a Graph 587 A key idea for an MRT algorithm is that any non-2-connected graph is 588 made up by blocks (e.g. 2-connected clusters, cut-links, and/or 589 isolated nodes). To compute GADAGs and thus MRTs, computation is 590 done in each block to compute ADAGs or Redundant Trees and then those 591 ADAGs or Redundant Trees are combined into a GADAG or MRT. 593 [E]---| [J]-------[I] [P]---[O] 594 | | | | | | 595 | | | | | | 596 [R] [D]---[C]--[F] [H]---[K] [N] 597 | | | | | | 598 | | | | | | 599 [A]--------[B] [G]---| [L]---[M] 601 (a) A graph with four blocks that are: 602 3 2-connected clusters and a cut-link 604 [E]<--| [J]<------[I] [P]<--[O] 605 | | | ^ | ^ 606 V | V | V | 607 [R] [D]<--[C] [F] [H]<---[K] [N] 608 ^ | ^ ^ 609 | V | | 611 [A]------->[B] [G]---| [L]-->[M] 613 (b) MRT-Blue 615 [E]---| [J]-------->[I] [P]-->[O] 616 | | | 617 V V V 618 [R] [D]-->[C]<---[F] [H]<---[K] [N] 619 ^ | ^ | ^ | 620 | V | | | V 621 [A]<-------[B] [G]<--| [L]<--[M] 623 (c) MRT-Red 625 Figure 10 627 Consider the example depicted in Figure 10 (a). In this figure, a 628 special graph is presented, showing us all the ways 2-connected 629 clusters can be connected. It has four blocks: block 1 contains R, 630 A, B, C, D, E, block 2 contains C, F, G, H, I, J, block 3 contains K, 631 L, M, N, O, P, and block 4 is a cut-edge containing H and K. As can 632 be observed, the first two blocks have one common node (node C) and 633 blocks 2 and 3 do not have any common node, but they are connected 634 through a cut-edge that is block 4. No two blocks can have more than 635 one common node, since two blocks with at least 2 common nodes would 636 qualify as a single 2-connected cluster. 638 Moreover, observe that if we want to get from one block to another, 639 we must use a cut-vertex (the cut-vertices in this graph are C, H, 640 K), regardless of the path selected, so we can say that all the paths 641 from block 3 along the MRTs rooted at R will cross K first. This 642 observation means that if we want to find a pair of MRTs rooted at R, 643 then we need to build up a pair of RTs in block 3 with K as a root. 644 Similarly, we need to find another one in block 2 with C as a root, 645 and finally, we need the last one in block 1 with R as a root. When 646 all the trees are selected, we can simply combine them; when a block 647 is a cut-edge (as in block 4), that cut-edge is added in the same 648 direction to both of the trees. The resulting trees are depicted in 649 Figure 10 (b) and (c). 651 Similarly, to create a GADAG it is sufficient to compute ADAGs in 652 each block and connect them. 654 It is necessary, therefore, to identify the cut-vertices, the blocks 655 and identify the appropriate local-root to use for each block. 657 3.5. Determining Local-Root and Assigning Block-ID 659 Each node in a network graph has a local-root, which is the cut- 660 vertex (or root) in the same block that is closest to the root. The 661 local-root is used to determine whether two nodes share a common 662 block. 664 Compute_Localroot(node x, node localroot) 665 x.localroot = localroot 666 for each DFS child c 667 if L(c) < D(x) //x is not a cut-vertex 668 Compute_Localroot(c, x.localroot) 669 else 670 mark x as cut-vertex 671 Compute_Localroot(c, x) 673 Compute_Localroot(root, root) 675 Figure 11: A method for computing local-roots 677 There are two different ways of computing the local-root for each 678 node. The stand-alone method is given in Figure 11 and better 679 illustrates the concept; it is used by the MRT algorithms given in 680 the Appendices Appendix A and Appendix B. The method for local-root 681 computation is used in the MRT Lowpoint algorithm for computing a 682 GADAG using Low-Point inheritance and the essence of it is given in 683 Figure 12. 685 Get the current node, s. 686 Compute an ear(either through lowpoint inheritance 687 or by following dfs parents) from s to a ready node e. 688 (Thus, s is not e, if there is such ear.) 689 if s is e 690 for each node x in the ear that is not s 691 x.localroot = s 692 else 693 for each node x in the ear that is not s or e 694 x.localroot = e.localroot 696 Figure 12: Ear-based method for computing local-roots 698 Once the local-roots are known, two nodes X and Y are in a common 699 block if and only if one of the following three conditions apply. 701 o Y's local-root is X's local-root : They are in the same block and 702 neither is the cut-vertex closest to the root. 704 o Y's local-root is X: X is the cut-vertex closest to the root for 705 Y's block 707 o Y is X's local-root: Y is the cut-vertex closest to the root for 708 X's block 710 Once we have computed the local-root for each node in the network 711 graph, we can assign for each node, a block id that represents the 712 block in which the node is present. This computation is shown in 713 Figure 13. 715 global_var: max_block_id 717 Assign_Block_ID(x, cur_block_id) 718 x.block_id = cur_block_id 719 foreach DFS child c of x 720 if (c.local_root is x) 721 max_block_id += 1 722 Assign_Block_ID(c, max_block_id) 723 else 724 Assign_Block_ID(c, cur_block_id) 726 max_block_id = 0 727 Assign_Block_ID(root, max_block_id) 729 Figure 13: Assigning block id to identify blocks 731 4. Algorithm Sections 733 This algorithm computes one GADAG that is then used by a router to 734 determine its MRT-Blue and MRT-Red next-hops to all destinations. 735 Finally, based upon that information, alternates are selected for 736 each next-hop to each destination. The different parts of this 737 algorithm are described below. These work on a network graph after, 738 for instance, its interfaces are ordered as per Figure 14. 740 1. Compute the local MRT Island for the particular MRT Profile. 741 [See Section 4.1.] 743 2. Select the root to use for the GADAG. [See Section 4.2.] 745 3. Initialize all interfaces to UNDIRECTED. [See Section 4.3.] 747 4. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See 748 Figure 9.] 750 5. Construct the GADAG. [See Section 4.4] 751 6. Assign directions to all interfaces that are still UNDIRECTED. 752 [See Section 4.5.] 754 7. From the computing router x, compute the next-hops for the MRT- 755 Blue and MRT-Red. [See Section 4.6.] 757 8. Identify alternates for each next-hop to each destination by 758 determining which one of the blue MRT and the red MRT the 759 computing router x should select. [See Section 4.7.] 761 To ensure consistency in computation, all routers MUST order 762 interfaces identically. This is necessary for the DFS, where the 763 selection order of the interfaces to explore results in different 764 trees, and for computing the GADAG, where the selection order of the 765 interfaces to use to form ears can result in different GADAGs. The 766 required ordering between two interfaces from the same router x is 767 given in Figure 14. 769 Interface_Compare(interface a, interface b) 770 if a.metric < b.metric 771 return A_LESS_THAN_B 772 if b.metric < a.metric 773 return B_LESS_THAN_A 774 if a.neighbor.loopback_addr < b.neighbor.loopback_addr 775 return A_LESS_THAN_B 776 if b.neighbor.loopback_addr < a.neighbor.loopback_addr 777 return B_LESS_THAN_A 778 // Same metric to same node, so the order doesn't matter anymore. 779 // To have a unique, consistent total order, 780 // tie-break based on, for example, the link's linkData as 781 // distributed in an OSPF Router-LSA 782 if a.link_data < b.link_data 783 return A_LESS_THAN_B 784 return B_LESS_THAN_A 786 Figure 14: Rules for ranking multiple interfaces. Order is from low 787 to high. 789 4.1. MRT Island Identification 791 The local MRT Island for a particular MRT profile can be determined 792 by starting from the computing router in the network graph and doing 793 a breadth-first-search (BFS), exploring only links that aren't MRT- 794 ineligible. 796 MRT_Island_Identification(topology, computing_rtr, profile_id) 797 for all routers in topology 798 rtr.IN_MRT_ISLAND = FALSE 800 computing_rtr.IN_MRT_ISLAND = TRUE 801 explore_list = { computing_rtr } 802 while (explore_list is not empty) 803 next_rtr = remove_head(explore_list) 804 for each interface in next_rtr 805 if interface is not MRT-ineligible 806 if ((interface.remote_node supports profile_id) and 807 (interface.remote_node.IN_MRT_ISLAND is FALSE)) 808 interface.remote_node.IN_MRT_ISLAND = TRUE 809 add_to_tail(explore_list, interface.remote_node) 811 Figure 15: MRT Island Identification 813 4.2. Root Selection 815 In [I-D.atlas-ospf-mrt], a mechanism is given for routers to 816 advertise the GADAG Root Selection Priority and consistently select a 817 GADAG Root inside the local MRT Island. Before beginning 818 computation, the network graph is reduced to contain only the set of 819 routers that support the specific MRT profile whose MRTs are being 820 computed. 822 Off-line analysis that considers the centrality of a router may help 823 determine how good a choice a particular router is for the role of 824 GADAG root. 826 4.3. Initialization 828 Before running the algorithm, there is the standard type of 829 initialization to be done, such as clearing any computed DFS-values, 830 lowpoint-values, DFS-parents, lowpoint-parents, any MRT-computed 831 next-hops, and flags associated with algorithm. 833 It is assumed that a regular SPF computation has been run so that the 834 primary next-hops from the computing router to each destination are 835 known. This is required for determining alternates at the last step. 837 Initially, all interfaces must be initialized to UNDIRECTED. Whether 838 they are OUTGOING, INCOMING or both is determined when the GADAG is 839 constructed and augmented. 841 It is possible that some links and nodes will be marked as unusable, 842 whether because of configuration, IGP flooding (e.g. MRT-ineligible 843 links in [I-D.atlas-ospf-mrt]), overload, or due to a transient cause 844 such as [RFC3137]. In the algorithm description, it is assumed that 845 such links and nodes will not be explored or used and no more 846 discussion is given of this restriction. 848 4.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance 850 As discussed in Section 3.2, it is necessary to find ears from a node 851 x that is already in the GADAG (known as IN_GADAG). There are two 852 methods to find ears; both are required. The first is by going to a 853 not IN_GADAG DFS-child and then following the chain of low-point 854 parents until an IN_GADAG node is found. The second is by going to a 855 not IN_GADAG neighbor and then following the chain of DFS parents 856 until an IN_GADAG node is found. As an ear is found, the associated 857 interfaces are marked based on the direction taken. The nodes in the 858 ear are marked as IN_GADAG. In the algorithm, first the ears via 859 DFS-children are found and then the ears via DFS-neighbors are found. 861 By adding both types of ears when an IN_GADAG node is processed, all 862 ears that connect to that node are found. The order in which the 863 IN_GADAG nodes is processed is, of course, key to the algorithm. The 864 order is a stack of ears so the most recent ear is found at the top 865 of the stack. Of course, the stack stores nodes and not ears, so an 866 ordered list of nodes, from the first node in the ear to the last 867 node in the ear, is created as the ear is explored and then that list 868 is pushed onto the stack. 870 Each ear represents a partial order (see Figure 4) and processing the 871 nodes in order along each ear ensures that all ears connecting to a 872 node are found before a node higher in the partial order has its ears 873 explored. This means that the direction of the links in the ear is 874 always from the node x being processed towards the other end of the 875 ear. Additionally, by using a stack of ears, this means that any 876 unprocessed nodes in previous ears can only be ordered higher than 877 nodes in the ears below it on the stack. 879 In this algorithm that depends upon Low-Point inheritance, it is 880 necessary that every node have a low-point parent that is not itself. 881 If a node is a cut-vertex, that may not yet be the case. Therefore, 882 any nodes without a low-point parent will have their low-point parent 883 set to their DFS parent and their low-point value set to the DFS- 884 value of their parent. This assignment also properly allows an ear 885 between two cut-vertices. 887 Finally, the algorithm simultaneously computes each node's local- 888 root, as described in Figure 12. This is further elaborated as 889 follows. The local-root can be inherited from the node at the end of 890 the ear unless the end of the ear is x itself, in which case the 891 local-root for all the nodes in the ear would be x. This is because 892 whenever the first cycle is found in a block, or an ear involving a 893 bridge is computed, the cut-vertex closest to the root would be x 894 itself. In all other scenarios, the properties of lowpoint/dfs 895 parents ensure that the end of the ear will be in the same block, and 896 thus inheriting its local-root would be the correct local-root for 897 all newly added nodes. 899 The pseudo-code for the GADAG algorithm (assuming that the adjustment 900 of lowpoint for cut-vertices has been made) is shown in Figure 16. 902 Construct_Ear(x, Stack, intf, type) 903 ear_list = empty 904 cur_node = intf.remote_node 905 cur_intf = intf 906 not_done = true 908 while not_done 909 cur_intf.UNDIRECTED = false 910 cur_intf.OUTGOING = true 911 cur_intf.remote_intf.UNDIRECTED = false 912 cur_intf.remote_intf.INCOMING = true 914 if cur_node.IN_GADAG is false 915 cur_node.IN_GADAG = true 916 add_to_list_end(ear_list, cur_node) 917 if type is CHILD 918 cur_intf = cur_node.lowpoint_parent_intf 919 cur_node = cur_node.lowpoint_parent 920 else type must be NEIGHBOR 921 cur_intf = cur_node.dfs_parent_intf 922 cur_node = cur_node.dfs_parent 923 else 924 not_done = false 926 if (type is CHILD) and (cur_node is x) 927 //x is a cut-vertex and the local root for 928 //the block in which the ear is computed 929 localroot = x 930 else 931 // Inherit local-root from the end of the ear 932 localroot = cur_node.localroot 933 while ear_list is not empty 934 y = remove_end_item_from_list(ear_list) 935 y.localroot = localroot 936 push(Stack, y) 938 Construct_GADAG_via_Lowpoint(topology, root) 939 root.IN_GADAG = true 940 root.localroot = root 941 Initialize Stack to empty 942 push root onto Stack 943 while (Stack is not empty) 944 x = pop(Stack) 945 foreach interface intf of x 946 if ((intf.remote_node.IN_GADAG == false) and 947 (intf.remote_node.dfs_parent is x)) 948 Construct_Ear(x, Stack, intf, CHILD) 949 foreach interface intf of x 950 if ((intf.remote_node.IN_GADAG == false) and 951 (intf.remote_node.dfs_parent is not x)) 952 Construct_Ear(x, Stack, intf, NEIGHBOR) 954 Construct_GADAG_via_Lowpoint(topology, root) 956 Figure 16: Low-point Inheritance GADAG algorithm 958 4.5. Augmenting the GADAG by directing all links 960 The GADAG, regardless of the algorithm used to construct it, at this 961 point could be used to find MRTs but the topology does not include 962 all links in the network graph. That has two impacts. First, there 963 might be shorter paths that respect the GADAG partial ordering and so 964 the alternate paths would not be as short as possible. Second, there 965 may be additional paths between a router x and the root that are not 966 included in the GADAG. Including those provides potentially more 967 bandwidth to traffic flowing on the alternates and may reduce 968 congestion compared to just using the GADAG as currently constructed. 970 The goal is thus to assign direction to every remaining link marked 971 as UNDIRECTED to improve the paths and number of paths found when the 972 MRTs are computed. 974 To do this, we need to establish a total order that respects the 975 partial order described by the GADAG. This can be done using Kahn's 976 topological sort[Kahn_1962_topo_sort] which essentially assigns a 977 number to a node x only after all nodes before it (e.g. with a link 978 incoming to x) have had their numbers assigned. The only issue with 979 the topological sort is that it works on DAGs and not ADAGs or 980 GADAGs. 982 To convert a GADAG to a DAG, it is necessary to remove all links that 983 point to a root of block from within that block. That provides the 984 necessary conversion to a DAG and then a topological sort can be 985 done. Finally, all UNDIRECTED links are assigned a direction based 986 upon the partial ordering. Any UNDIRECTED links that connect to a 987 root of a block from within that block are assigned a direction 988 INCOMING to that root. The exact details of this whole process are 989 captured in Figure 17 990 Set_Block_Root_Incoming_Links(topo, root, mark_or_clear) 991 foreach node x in topo 992 if node x is a cut-vertex or root 993 foreach interface i of x 994 if (i.remote_node.localroot is x) 995 if i.UNDIRECTED 996 i.OUTGOING = true 997 i.remote_intf.INCOMING = true 998 i.UNDIRECTED = false 999 i.remote_intf.UNDIRECTED = false 1000 if i.INCOMING 1001 if mark_or_clear is mark 1002 if i.OUTGOING // a cut-edge 1003 i.STORE_INCOMING = true 1004 i.INCOMING = false 1005 i.remote_intf.STORE_OUTGOING = true 1006 i.remote_intf.OUTGOING = false 1007 i.TEMP_UNUSABLE = true 1008 i.remote_intf.TEMP_UNUSABLE = true 1009 else 1010 i.TEMP_UNUSABLE = false 1011 i.remote_intf.TEMP_UNUSABLE = false 1012 if i.STORE_INCOMING and (mark_or_clear is clear) 1013 i.INCOMING = true 1014 i.STORE_INCOMING = false 1015 i.remote_intf.OUTGOING = true 1016 i.remote_intf.STORE_OUTGOING = false 1018 Run_Topological_Sort_GADAG(topo, root) 1019 Set_Block_Root_Incoming_Links(topo, root, MARK) 1020 foreach node x 1021 set x.unvisited to the count of x's incoming interfaces 1022 that aren't marked TEMP_UNUSABLE 1023 Initialize working_list to empty 1024 Initialize topo_order_list to empty 1025 add_to_list_end(working_list, root) 1026 while working_list is not empty 1027 y = remove_start_item_from_list(working_list) 1028 add_to_list_end(topo_order_list, y) 1029 foreach interface i of y 1030 if (i.OUTGOING) and (not i.TEMP_UNUSABLE) 1031 i.remote_node.unvisited -= 1 1032 if i.remote_node.unvisited is 0 1033 add_to_list_end(working_list, i.remote_node) 1034 next_topo_order = 1 1035 while topo_order_list is not empty 1036 y = remove_start_item_from_list(topo_order_list) 1037 y.topo_order = next_topo_order 1038 next_topo_order += 1 1039 Set_Block_Root_Incoming_Links(topo, root, CLEAR) 1041 Add_Undirected_Links(topo, root) 1042 Run_Topological_Sort_GADAG(topo, root) 1043 foreach node x in topo 1044 foreach interface i of x 1045 if i.UNDIRECTED 1046 if x.topo_order < i.remote_node.topo_order 1047 i.OUTGOING = true 1048 i.UNDIRECTED = false 1049 i.remote_intf.INCOMING = true 1050 i.remote_intf.UNDIRECTED = false 1051 else 1052 i.INCOMING = true 1053 i.UNDIRECTED = false 1054 i.remote_intf.OUTGOING = true 1055 i.remote_intf.UNDIRECTED = false 1057 Add_Undirected_Links(topo, root) 1059 Figure 17: Assigning direction to UNDIRECTED links 1061 Proxy-nodes do not need to be added to the network graph. They 1062 cannot be transited and do not affect the MRTs that are computed. 1063 The details of how the MRT-Blue and MRT-Red next-hops are computed 1064 and how the appropriate alternate next-hops are selected is given in 1065 Section 4.8. 1067 4.6. Compute MRT next-hops 1069 As was discussed in Section 3.1, once a ADAG is found, it is 1070 straightforward to find the next-hops from any node X to the ADAG 1071 root. However, in this algorithm, we want to reuse the common GADAG 1072 and find not only the one pair of MRTs rooted at the GADAG root with 1073 it, but find a pair rooted at each node. This is useful since it is 1074 significantly faster to compute. It may also provide easier 1075 troubleshooting of the MRT-Red and MRT-Blue. 1077 The method for computing differently rooted MRTs from the common 1078 GADAG is based on two ideas. First, if two nodes X and Y are ordered 1079 with respect to each other in the partial order, then an SPF along 1080 OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a 1081 decreasing-SPF) can be used to find the increasing and decreasing 1082 paths. Second, if two nodes X and Y aren't ordered with respect to 1083 each other in the partial order, then intermediary nodes can be used 1084 to create the paths by increasing/decreasing to the intermediary and 1085 then decreasing/increasing to reach Y. 1087 As usual, the two basic ideas will be discussed assuming the network 1088 is two-connected. The generalization to multiple blocks is discussed 1089 in Section 4.6.4. The full algorithm is given in Section 4.6.5. 1091 4.6.1. MRT next-hops to all nodes partially ordered with respect to the 1092 computing node 1094 To find two node-disjoint paths from the computing router X to any 1095 node Y, depends upon whether Y >> X or Y << X. As shown in Figure 1096 18, if Y >> X, then there is an increasing path that goes from X to Y 1097 without crossing R; this contains nodes in the interval [X,Y]. There 1098 is also a decreasing path that decreases towards R and then decreases 1099 from R to Y; this contains nodes in the interval [X,R-small] or 1100 [R-great,Y]. The two paths cannot have common nodes other than X and 1101 Y. 1103 [Y]<---(Cloud 2)<--- [X] 1104 | ^ 1105 | | 1106 V | 1107 (Cloud 3)--->[R]--->(Cloud 1) 1109 MRT-Blue path: X->Cloud 2->Y 1110 MRT-Red path: X->Cloud 1->R->Cloud 3->Y 1112 Figure 18: Y >> X 1114 Similar logic applies if Y << X, as shown in Figure 19. In this 1115 case, the increasing path from X increases to R and then increases 1116 from R to Y to use nodes in the intervals [X,R-great] and [R-small, 1117 Y]. The decreasing path from X reaches Y without crossing R and uses 1118 nodes in the interval [Y,X]. 1120 [X]<---(Cloud 2)<--- [Y] 1121 | ^ 1122 | | 1123 V | 1124 (Cloud 3)--->[R]--->(Cloud 1) 1126 MRT-Blue path: X->Cloud 3->R->Cloud 1->Y 1127 MRT-Red path: X->Cloud 2->Y 1129 Figure 19: Y << X 1131 4.6.2. MRT next-hops to all nodes not partially ordered with respect to 1132 the computing node 1134 When X and Y are not ordered, the first path should increase until we 1135 get to a node G, where G >> Y. At G, we need to decrease to Y. The 1136 other path should be just the opposite: we must decrease until we get 1137 to a node H, where H << Y, and then increase. Since R is smaller and 1138 greater than Y, such G and H must exist. It is also easy to see that 1139 these two paths must be node disjoint: the first path contains nodes 1140 in interval [X,G] and [Y,G], while the second path contains nodes in 1141 interval [H,X] and [H,Y]. This is illustrated in Figure 20. It is 1142 necessary to decrease and then increase for the MRT-Blue and increase 1143 and then decrease for the MRT-Red; if one simply increased for one 1144 and decreased for the other, then both paths would go through the 1145 root R. 1147 (Cloud 6)<---[Y]<---(Cloud 5)<------------| 1148 | | 1149 | | 1150 V | 1151 [G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H] 1152 ^ | 1153 | | 1154 | | 1155 (Cloud 3)<---[X]<---(Cloud 2)<-----------| 1157 MRT-Blue path: decrease to H and increase to Y 1158 X->Cloud 2->H->Cloud 5->Y 1159 MRT-Red path: increase to G and decrease to Y 1160 X->Cloud 3->G->Cloud 6->Y 1162 Figure 20: X and Y unordered 1164 This gives disjoint paths as long as G and H are not the same node. 1165 Since G >> Y and H << Y, if G and H could be the same node, that 1166 would have to be the root R. This is not possible because there is 1167 only one incoming interface to the root R which is created when the 1168 initial cycle is found. Recall from Figure 6 that whenever an ear 1169 was found to have an end that was the root R, the ear was directed 1170 from R so that the associated interface on R is outgoing and not 1171 incoming. Therefore, there must be exactly one node M which is the 1172 largest one before R, so the MRT-Red path will never reach R; it will 1173 turn at M and decrease to Y. 1175 4.6.3. Computing Redundant Tree next-hops in a 2-connected Graph 1177 The basic ideas for computing RT next-hops in a 2-connected graph 1178 were given in Section 4.6.1 and Section 4.6.2. Given these two 1179 ideas, how can we find the trees? 1180 If some node X only wants to find the next-hops (which is usually the 1181 case for IP networks), it is enough to find which nodes are greater 1182 and less than X, and which are not ordered; this can be done by 1183 running an increasing-SPF and a decreasing-SPF rooted at X and not 1184 exploring any links from the ADAG root. ( Traversal algorithms other 1185 than SPF could safely be used instead where one traversal takes the 1186 links in their given directions and the other reverses the links' 1187 directions.) 1189 An increasing-SPF rooted at X and not exploring links from the root 1190 will find the increasing next-hops to all Y >> X. Those increasing 1191 next-hops are X's next-hops on the MRT-Blue to reach Y. An 1192 decreasing-SPF rooted at X and not exploring links from the root will 1193 find the decreasing next-hops to all Z << X. Those decreasing next- 1194 hops are X's next-hops on the MRT-Red to reach Z. Since the root R 1195 is both greater than and less than X, after this increasing-SPF and 1196 decreasing-SPF, X's next-hops on the MRT-Blue and on the MRT-Red to 1197 reach R are known. For every node Y >> X, X's next-hops on the MRT- 1198 Red to reach Y are set to those on the MRT-Red to reach R. For every 1199 node Z << X, X's next-hops on the MRT-Blue to reach Z are set to 1200 those on the MRT-Blue to reach R. 1202 For those nodes, which were not reached, we have the next-hops as 1203 well. The increasing MRT-Blue next-hop for a node, which is not 1204 ordered, is the next-hop along the decreasing MRT-Red towards R and 1205 the decreasing MRT-Red next-hop is the next-hop along the increasing 1206 MRT-Blue towards R. Naturally, since R is ordered with respect to all 1207 the nodes, there will always be an increasing and a decreasing path 1208 towards it. This algorithm does not provide the complete specific 1209 path taken but just the appropriate next-hops to use. The identity 1210 of G and H is not determined. 1212 The final case to considered is when the root R computes its own 1213 next-hops. Since the root R is << all other nodes, running an 1214 increasing-SPF rooted at R will reach all other nodes; the MRT-Blue 1215 next-hops are those found with this increasing-SPF. Similarly, since 1216 the root R is >> all other nodes, running a decreasing-SPF rooted at 1217 R will reach all other nodes; the MRT-Red next-hops are those found 1218 with this decreasing-SPF. 1220 E---D---| E<--D<--| 1221 | | | | ^ | 1222 | | | V | | 1223 R F C R F C 1224 | | | | ^ ^ 1225 | | | V | | 1226 A---B---| A-->B---| 1227 (a) (b) 1228 A 2-connected graph A spanning ADAG rooted at R 1230 Figure 21 1232 As an example consider the situation depicted in Figure 21. There 1233 node C runs an increasing-SPF and a decreasing-SPF The increasing-SPF 1234 reaches D, E and R and the decreasing-SPF reaches B, A and R. So 1235 towards E the increasing next-hop is D (it was reached though D), and 1236 the decreasing next-hop is B (since R was reached though B). Since 1237 both D and B, A and R will compute the next hops similarly, the 1238 packets will reach E. 1240 We have the next-hops towards F as well: since F is not ordered with 1241 respect to C, the MRT-Blue next-hop is the decreasing one towards R 1242 (which is B) and the MRT-Red next-hop is the increasing one towards R 1243 (which is D). Since B is ordered with F, it will find, for its MRT- 1244 Blue, a real increasing next-hop, so packet forwarded to B will get 1245 to F on path C-B-F. Similarly, D will have, for its MRT-Red, a real 1246 decreasing next-hop, and the packet will use path C-D-F. 1248 4.6.4. Generalizing for graph that isn't 2-connected 1250 If a graph isn't 2-connected, then the basic approach given in 1251 Section 4.6.3 needs some extensions to determine the appropriate MRT 1252 next-hops to use for destinations outside the computing router X's 1253 blocks. In order to find a pair of maximally redundant trees in that 1254 graph we need to find a pair of RTs in each of the blocks (the root 1255 of these trees will be discussed later), and combine them. 1257 When computing the MRT next-hops from a router X, there are three 1258 basic differences: 1260 1. Only nodes in a common block with X should be explored in the 1261 increasing-SPF and decreasing-SPF. 1263 2. Instead of using the GADAG root, X's local-root should be used. 1264 This has the following implications: 1266 a. The links from X's local-root should not be explored. 1268 b. If a node is explored in the outgoing SPF so Y >> X, then X's 1269 MRT-Red next-hops to reach Y uses X's MRT-Red next-hops to 1270 reach X's local-root and if Z << X, then X's MRT-Blue next- 1271 hops to reach Z uses X's MRT-Blue next-hops to reach X's 1272 local-root. 1274 c. If a node W in a common block with X was not reached in the 1275 increasing-SPF or decreasing-SPF, then W is unordered with 1276 respect to X. X's MRT-Blue next-hops to W are X's decreasing 1277 aka MRT-Red next-hops to X's local-root. X's MRT-Red next- 1278 hops to W are X's increasing aka Blue MRT next-hops to X's 1279 local-root. 1281 3. For nodes in different blocks, the next-hops must be inherited 1282 via the relevant cut-vertex. 1284 These are all captured in the detailed algorithm given in 1285 Section 4.6.5. 1287 4.6.5. Complete Algorithm to Compute MRT Next-Hops 1289 The complete algorithm to compute MRT Next-Hops for a particular 1290 router X is given in Figure 22. In addition to computing the MRT- 1291 Blue next-hops and MRT-Red next-hops used by X to reach each node Y, 1292 the algorithm also stores an "order_proxy", which is the proper cut- 1293 vertex to reach Y if it is outside the block, and which is used later 1294 in deciding whether the MRT-Blue or the MRT-Red can provide an 1295 acceptable alternate for a particular primary next-hop. 1297 In_Common_Block(x, y) 1298 if (((x.localroot is y.localroot) and (x.block_id is y.block_id)) 1299 or (x is y.localroot) or (y is x.localroot)) 1300 return true 1301 return false 1303 Store_Results(y, direction, spf_root, store_nhs) 1304 if direction is FORWARD 1305 y.higher = true 1306 if store_nhs 1307 y.blue_next_hops = y.next_hops 1308 if direction is REVERSE 1309 y.lower = true 1310 if store_nhs 1311 y.red_next_hops = y.next_hops 1313 SPF_No_Traverse_Root(spf_root, block_root, direction, store_nhs) 1314 Initialize spf_heap to empty 1315 Initialize nodes' spf_metric to infinity and next_hops to empty 1316 spf_root.spf_metric = 0 1317 insert(spf_heap, spf_root) 1318 while (spf_heap is not empty) 1319 min_node = remove_lowest(spf_heap) 1320 Store_Results(min_node, direction, spf_root, store_nhs) 1321 if ((min_node is spf_root) or (min_node is not block_root)) 1322 foreach interface intf of min_node 1323 if (((direction is FORWARD) and intf.OUTGOING) or 1324 ((direction is REVERSE) and intf.INCOMING) and 1325 In_Common_Block(spf_root, intf.remote_node)) 1326 path_metric = min_node.spf_metric + intf.metric 1327 if path_metric < intf.remote_node.spf_metric 1328 intf.remote_node.spf_metric = path_metric 1329 if min_node is spf_root 1330 intf.remote_node.next_hops = make_list(intf) 1331 else 1332 intf.remote_node.next_hops = min_node.next_hops 1333 insert_or_update(spf_heap, intf.remote_node) 1334 else if path_metric is intf.remote_node.spf_metric 1335 if min_node is spf_root 1336 add_to_list(intf.remote_node.next_hops, intf) 1337 else 1338 add_list_to_list(intf.remote_node.next_hops, 1339 min_node.next_hops) 1341 SetEdge(y) 1342 if y.blue_next_hops is empty and y.red_next_hops is empty 1343 if (y.local_root != y) { 1344 SetEdge(y.localroot) 1345 } 1346 y.blue_next_hops = y.localroot.blue_next_hops 1347 y.red_next_hops = y.localroot.red_next_hops 1348 y.order_proxy = y.localroot.order_proxy 1350 Compute_MRT_NextHops(x, root) 1351 foreach node y 1352 y.higher = y.lower = false 1353 clear y.red_next_hops and y.blue_next_hops 1354 y.order_proxy = y 1355 SPF_No_Traverse_Root(x, x.localroot, FORWARD, TRUE) 1356 SPF_No_Traverse_Root(x, x.localroot, REVERSE, TRUE) 1358 // red and blue next-hops are stored to x.localroot as different 1359 // paths are found via the SPF and reverse-SPF. 1360 // Similarly any nodes whose local-root is x will have their 1361 // red_next_hops and blue_next_hops already set. 1363 // Handle nodes in the same block that aren't the local-root 1364 foreach node y 1365 if (y.IN_MRT_ISLAND and (y is not x) and 1366 (y.localroot is x.localroot) and 1367 ((y is x.localroot) or (x is y.localroot) or 1368 (y.block_id is x.block_id))) 1369 if y.higher 1370 y.red_next_hops = x.localroot.red_next_hops 1371 else if y.lower 1372 y.blue_next_hops = x.localroot.blue_next_hops 1373 else 1374 y.blue_next_hops = x.localroot.red_next_hops 1375 y.red_next_hops = x.localroot.blue_next_hops 1377 // Inherit next-hops and order_proxies to other components 1378 if x is not root 1379 root.blue_next_hops = x.localroot.blue_next_hops 1380 root.red_next_hops = x.localroot.red_next_hops 1381 root.order_proxy = x.localroot 1382 foreach node y 1383 if (y is not root) and (y is not x) and y.IN_MRT_ISLAND 1384 SetEdge(y) 1386 max_block_id = 0 1387 Assign_Block_ID(root, max_block_id) 1388 Compute_MRT_NextHops(x, root) 1390 Figure 22 1392 4.7. Identify MRT alternates 1394 At this point, a computing router S knows its MRT-Blue next-hops and 1395 MRT-Red next-hops for each destination in the MRT Island. The 1396 primary next-hops along the SPT are also known. It remains to 1397 determine for each primary next-hop to a destination D, which of the 1398 MRTs avoids the primary next-hop node F. This computation depends 1399 upon data set in Compute_MRT_NextHops such as each node y's 1400 y.blue_next_hops, y.red_next_hops, y.order_proxy, y.higher, y.lower 1401 and topo_orders. Recall that any router knows only which are the 1402 nodes greater and lesser than itself, but it cannot decide the 1403 relation between any two given nodes easily; that is why we need 1404 topological ordering. 1406 For each primary next-hop node F to each destination D, S can call 1407 Select_Alternates(S, D, F, primary_intf) to determine whether to use 1408 the MRT-Blue next-hops as the alternate next-hop(s) for that primary 1409 next hop or to use the MRT-Red next-hops. The algorithm is given in 1410 Figure 23 and discussed afterwards. 1412 Select_Alternates_Internal(S, D, F, primary_intf, 1413 D_lower, D_higher, D_topo_order) 1415 //When D==F, we can do only link protection 1416 if ((D is F) or (D.order_proxy is F)) 1417 if an MRT doesn't use primary_intf 1418 indicate alternate is not node-protecting 1419 return that MRT color 1420 else // parallel links are cut-edge 1421 return AVOID_LINK_ON_BLUE 1423 if (D_lower and D_higher and F.lower and F.higher) 1424 if F.topo_order < D_topo_order 1425 return USE_RED 1426 else 1427 return USE_BLUE 1429 if (D_lower and D_higher) 1430 if F.higher 1431 return USE_RED 1432 else 1433 return USE_BLUE 1435 if (F.lower and F.higher) 1436 if D_lower 1437 return USE_RED 1438 else if D_higher 1439 return USE_BLUE 1440 else 1441 if primary_intf.OUTGOING and primary_intf.INCOMING 1442 return AVOID_LINK_ON_BLUE 1443 if primary_intf.OUTGOING is true 1444 return USE_BLUE 1445 if primary_intf.INCOMING is true 1446 return USE_RED 1448 if D_higher 1449 if F.higher 1450 if F.topo_order < D_topo_order 1451 return USE_RED 1452 else 1453 return USE_BLUE 1454 else if F.lower 1455 return USE_BLUE 1456 else 1457 // F and S are neighbors so either F << S or F >> S 1458 else if D_lower 1459 if F.higher 1460 return USE_RED 1461 else if F.lower 1462 if F.topo_order < D_topo_order 1463 return USE_RED 1464 else 1465 return USE_BLUE 1466 else 1467 // F and S are neighbors so either F << S or F >> S 1468 else // D and S not ordered 1469 if F.lower 1470 return USE_RED 1471 else if F.higher 1472 return USE_BLUE 1473 else 1474 // F and S are neighbors so either F << S or F >> S 1476 Select_Alternates(S, D, F, primary_intf) 1477 if D.order_proxy is not D 1478 D_lower = D.order_proxy.lower 1479 D_higher = D.order_proxy.higher 1480 D_topo_order = D.order_proxy.topo_order 1481 else 1482 D_lower = D.lower 1483 D_higher = D.higher 1484 D_topo_order = D.topo_order 1485 return Select_Alternates_Internal(S, D, F, primary_intf, 1486 D_lower, D_higher, D_topo_order) 1488 Figure 23 1490 If either D>>S>>F or D<>D (ii) F<D.topo_order, either case (i) or 1501 case (iii) holds true, which means that selecting the Blue next-hop 1502 is safe. Similarly, if F.topo_order>S, we 1512 should use the Blue next-hop. 1514 Additionally, the cases where either F or D is ordered both higher 1515 and lower must be considered; this can happen when one is a block- 1516 root or its order_proxy is. If D is both higher and lower than S, 1517 then the MRT to use is the one that avoids F so if F is higher, then 1518 the MRT-Red should be used and if F is lower, then the MRT-Blue 1519 should be used; F and S must be ordered because they are neighbors. 1520 If F is both higher and lower, then if D is lower, using the MRT-Red 1521 to decrease reaches D and if D is higher, using the Blue MRT to 1522 increase reaches D; if D is unordered compared to S, then the 1523 situation is a bit more complicated. 1525 In the case where F< F, then use the MRT-Blue (decrease to avoid 1528 that link and then increase). If the link is directed S <- F, then 1529 use the MRT-Red (increase to avoid that link and then decrease). If 1530 the link is S <--> F, then the link must be a cut-link and there is 1531 no node-protecting alternate. If there are multiple links between S 1532 and F, then they can protect against each other; of course, in this 1533 situation, they are probably already ECMP. 1535 Finally, there is the case where D is also F. In this case, only link 1536 protection is possible. The MRT that doesn't use the indicated 1537 primary next-hop is used. If both MRTs use the primary next-hop, 1538 then the primary next-hop must be a cut-edge so either MRT could be 1539 used but the set of MRT next-hops must be pruned to avoid that 1540 primary next-hop. To indicate this case, Select_Alternates returns 1541 AVOID_LINK_ON_BLUE. 1543 As an example, consider the ADAG depicted in Figure 24 and first 1544 suppose that G is the source, D is the destination and H is the 1545 failed next-hop. Since D>>G, we need to compare H.topo_order and 1546 D.topo_order. Since D.topo_order>H.topo_order, D must be not smaller 1547 than H, so we should select the decreasing path towards the root. 1548 If, however, the destination were instead J, we must find that 1549 H.topo_order>J.topo_order, so we must choose the increasing Blue 1550 next-hop to J, which is I. In the case, when instead the destination 1551 is C, we find that we need to first decrease to avoid using H, so the 1552 Blue, first decreasing then increasing, path is selected. 1554 [E]<-[D]<-[H]<-[J] 1555 | ^ ^ ^ 1556 V | | | 1557 [R] [C] [G]->[I] 1558 | ^ ^ ^ 1559 V | | | 1560 [A]->[B]->[F]---| 1562 (a) 1563 a 2-connected graph 1565 Figure 24 1567 4.8. Finding FRR Next-Hops for Proxy-Nodes 1569 As discussed in Section 10.2 of 1570 [I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT- 1571 Blue and MRT-Red next-hops and MRT-FRR alternates for a named proxy- 1572 nodes. An example case is for a router that is not part of that 1573 local MRT Island, when there is only partial MRT support in the 1574 domain. 1576 A first incorrect and naive approach to handling proxy-nodes, which 1577 cannot be transited, is to simply add these proxy-nodes to the graph 1578 of the network and connect it to the routers through which the new 1579 proxy-node can be reached. Unfortunately, this can introduce some 1580 new ordering between the border routers connected to the new node 1581 which could result in routing MRT paths through the proxy-node. 1582 Thus, this naive approach would need to recompute GADAGs and redo 1583 SPTs for each proxy-node. 1585 Instead of adding the proxy-node to the original network graph, each 1586 individual proxy-node can be individually added to the GADAG. The 1587 proxy-node is connected to at most two nodes in the GADAG. 1588 Section 10.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] defines how the 1589 proxy-node attachments MUST be determined. The degenerate case where 1590 the proxy-node is attached to only one node in the GADAG is trivial 1591 as all needed information can be derived from that attachment node; 1592 if there are different interfaces, then some can be assigned to MRT- 1593 Red and others to MRT_Blue. 1595 Now, consider the proxy-node that is attached to exactly two nodes in 1596 the GADAG. Let the order_proxies of these nodes be A and B. Let the 1597 current node, where next-hop is just being calculated, be S. If one 1598 of these two nodes A and B is the local root of S, let A=S.local_root 1599 and the other one be B. Otherwise, let A.topo_order < B.topo_order. 1601 A valid GADAG was constructed. Instead doing an increasing-SPF and a 1602 decreasing-SPF to find ordering for the proxy-nodes, the following 1603 simple rules, providing the same result, can be used independently 1604 for each different proxy-node. For the following rules, let 1605 X=A.local_root, and if A is the local root, let that be strictly 1606 lower than any other node. Always take the first rule that matches. 1608 Rule Condition Blue NH Red NH Notes 1609 1 S=X Blue to A Red to B 1610 2 S<>B Blue to R Red to B 1612 4 A<> S, 1694 the computing router, MUST be one or more nodes, T, whose topo_order 1695 is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y 1696 is T. Similarly, the MRT-Red next-hops MUST be have a topo_order in 1697 the interval [R-small.topo_order, X.topo_order] or [Y.topo_order, 1698 R-big.topo_order]. 1700 Implementations SHOULD implement the Select_Alternates() function to 1701 pick an MRT-FRR alternate. 1703 In a future version, this section will include pseudo-code describing 1704 the full code path through the pseudo-code given earlier in the 1705 draft. 1707 6. Algorithm Alternatives and Evaluation 1709 This specification defines the MRT Lowpoint Algorithm, which is one 1710 option among several possible MRT algorithms. Other alternatives are 1711 described in the appendices. 1713 In addition, it is possible to calculate Destination-Rooted GADAG, 1714 where for each destination, a GADAG rooted at that destination is 1715 computed. Then a router can compute the blue MRT and red MRT next- 1716 hops to that destination. Building GADAGs per destination is 1717 computationally more expensive, but may give somewhat shorter 1718 alternate paths. It may be useful for live-live multicast along 1719 MRTs. 1721 6.1. Algorithm Evaluation 1723 This section compares MRT and remote LFA for IP Fast Reroute in 16 1724 service provider network topologies, focusing on coverage and 1725 alternate path length. Figure 26 shows the coverage provided by MRT 1726 and RLFA for protection against different failure modes in these 1727 topologies. The coverage values are calculated as the percentage of 1728 source-destination pairs protected by the given IPFRR method relative 1729 to source-destination pairs protected by optimal routing, against the 1730 same failure modes. For example, the second column is the percentage 1731 of source-destination pairs protected by MRT against next-hop node 1732 failure and against next-hop link failure relative to source- 1733 destination pairs protected by optimal routing against the same 1734 failure modes. The particular variants of MRT and RLFA used for this 1735 analysis are described at the end of this section. 1737 When the requirement is to provide IPFRR protection against a single 1738 link or node failure, MRT is able to provide protection for any 1739 source-destination pair for which some path still exists after the 1740 failure. For the topologies analyzed here, RLFA provides protection 1741 against a single link or node failure for 41% to 98% of the source- 1742 destination pairs, with an average of 73% coverage. 1744 +------------+------------------+-----------------------------------+ 1745 | Topology | link and node | link-only | 1746 | | failure coverage | failure coverage | 1747 | |------------------+-----------------------------------+ 1748 | | MRT | RLFA | MRT | RLFA | RLFA | 1749 | | | | |no possible| possible | 1750 | | | | | loops | loops | 1751 +------------+---------+--------+--------+---------- +--------------+ 1752 | T101 | 100.0% | 89.0% | 100.0% | 97.1% | 99.4% | 1753 | T102 | 100.0% | 41.0% | 100.0% | 96.5% | 100.0% | 1754 | T103 | 100.0% | 81.7% | 100.0% | 94.9% | 99.6% | 1755 | T104 | 100.0% | 65.4% | 100.0% | 86.2% | 100.0% | 1756 | T105 | 100.0% | 69.0% | 100.0% | 85.7% | 93.8% | 1757 | T106 | 100.0% | 80.3% | 100.0% | 91.2% | 100.0% | 1758 | T107 | 100.0% | 79.6% | 100.0% | 82.1% | 93.7% | 1759 | T108 | 100.0% | 60.4% | 100.0% | 54.9% | 66.9% | 1760 | T109 | 100.0% | 50.7% | 100.0% | 52.9% | 67.0% | 1761 | T110 | 100.0% | 80.5% | 100.0% | 75.4% | 100.0% | 1762 | T111 | 100.0% | 85.1% | 100.0% | 89.5% | 99.9% | 1763 | T112 | 100.0% | 89.1% | 100.0% | 76.9% | 100.0% | 1764 | T113 | 100.0% | 66.7% | 100.0% | 93.7% | 100.0% | 1765 | T114 | 100.0% | 73.6% | 100.0% | 96.0% | 100.0% | 1766 | T115 | 100.0% | 97.7% | 100.0% | 96.2% | 100.0% | 1767 | T116 | 100.0% | 65.0% | 100.0% | 95.7% | 99.9% | 1768 | Average | 100.0% | 73.4% | 100.0% | 85.3% | 95.0% | 1769 | Median | 100.0% | 76.6% | 100.0% | 90.4% | 100.0% | 1770 +------------+---------+--------+--------+-----------+--------------+ 1772 Figure 26 1774 When the requirement is to provide protection against a single link 1775 failure, MRT is able to provide 100% coverage. The coverage provided 1776 by RLFA against a single link failure depends on whether or not one 1777 restricts RLFA repairs to those that are guaranteed not to cause 1778 loops in the event of a node failure occurs. When RLFAs are chosen 1779 to exclude the possiblity of such loops, coverage for these 1780 topologies ranges from 52% to 97%, with an average of 85%. If one 1781 allows for the possibility of loops being created by the use of an 1782 RLFA, then the coverage increases to range from 67% to 100%, with an 1783 average of 95%. 1785 Note that for most of the topologies, the calculated RLFA coverage 1786 increases when reducing the protection requirements from link and 1787 node failure coverage to link-only failure coverage. However, for 1788 several of the topologies, the calculated RLFA coverage decreases 1789 when going from link and node failure coverage to link-only failure 1790 coverage. While the absolute number of source-destination pairs 1791 protected by RLFA increases for all of the topologies when the 1792 protection requirements are reduced, for some topologies the absolute 1793 number of source-destination pairs that protectable by optimal 1794 routing increases even more, resulting in a decrease in the relative 1795 RLFA coverage. 1797 +----------+--------------------------------------------------+ 1798 | Topology | average alternate path length | 1799 | | (relative to optimal) | 1800 | +--------------------------------------------------+ 1801 | | MRT | RLFA | Next-Next-Hop | 1802 +----------+----------------+----------------+----------------+ 1803 | T101 | 1.28 | 1.01 | 1.04 | 1804 | T102 | 1.22 | 1.01 | 1.02 | 1805 | T103 | 1.13 | 1.01 | 1.02 | 1806 | T104 | 1.01 | 1.00 | 1.00 | 1807 | T105 | 2.97 | 1.42 | 1.16 | 1808 | T106 | 1.16 | 1.06 | 1.07 | 1809 | T107 | 86.87 | 99.51 | 1.04 | 1810 | T108 | 1.07 | 1.01 | 1.03 | 1811 | T109 | 1.09 | 1.02 | 1.05 | 1812 | T110 | 1.06 | 1.03 | 1.25 | 1813 | T111 | 1.25 | 1.02 | 1.10 | 1814 | T112 | 1.11 | 1.05 | 1.32 | 1815 | T113 | 1.03 | 1.00 | 1.02 | 1816 | T114 | 1.77 | 1.00 | 1.06 | 1817 | T115 | 1.01 | 1.00 | 1.04 | 1818 | T116 | 1.31 | 1.01 | 1.04 | 1819 | Median | 1.14 | 1.01 | 1.04 | 1820 +----------+----------------+----------------+----------------+ 1822 Figure 27 1824 The first three columns of Figure 27 compare the lengths of the 1825 alternate paths used by MRT and RLFA across the 16 topologies 1826 (measured as the sum of IGP costs). The alternate path lengths for 1827 the FRR methods are computed relative to the optimal alternate path 1828 length, which is computed by removing the failed node and running an 1829 SPF to find the shortest path from the PLR to the destination. The 1830 alternate path lengths are averaged over all source-destination pairs 1831 for which RLFA provides a node-protecting alternate or a link- 1832 protecting alternate that cannot loop in the event of a node failure. 1833 The fourth column of Figure 27 presents results for Next-Next-Hop 1834 alternate paths. The calculated Next-Next-Hop alternate lengths 1835 would apply to the Not-Via IPFRR method as well as RSVP-TE based FRR 1836 using next-next-hop bypass tunnels. 1838 Before drawing any general conclusions from this data, it is useful 1839 understand the origin of the large values of average relative 1840 alternate path length calculated for topology T107, with a value of 1841 87 for MRT, and 99 for RLFA. The network topology represented by 1842 T107 uses values of 10, 100, and 1000 as IGP costs, so small 1843 deviations from the optimal alternate path can result in large 1844 differences in relative path length. The fact that the Next-Next-Hop 1845 average relative alternate path length for T107 is 1.04 (much closer 1846 to optimal than either MRT or RLFA is reasonable. The next-next-hop 1847 alternate path length is computed by removing the failed node and 1848 finding the shortest path from the source to the next-next-hop node, 1849 and adding that to the shortest path from the next-next-hop node to 1850 the destination. Both of the paths that make up the Next-Next-Hop 1851 alternate path follow shortest paths, so the resulting alternate path 1852 from source to destination will only use a link with a cost of 1000 1853 if absolutely necessary. Instead, the other two methods allow for at 1854 least one hop in the alterate path to be chosen independent of the 1855 cost of the link, often resulting in the use of a link with cost 1856 1000. 1858 For most of the topologies analyzed, the average RLFA alternate paths 1859 are within a few percent of optimal with a median value of 1.01. 1860 Most of the average MRT alternate path lengths are within 30% of 1861 optimal with a median value of 1.14. In general, it appears that the 1862 100% coverage provided by MRT comes at the expense of a modest 1863 increase in alternate path length. This may be a desirable trade-off 1864 if one considers that the alternate path length for a source- 1865 destination pair without an RLFA alternate is effectively infinite. 1866 The results for Next-Next-Hop alternate path lengths tend to fall in 1867 between MRT and RLFA with a median of 1.04. However, for some 1868 topologies the Next-Next-Hop results are higher than the MRT results. 1870 The analysis presented here uses the MRT Lowpoint Algorithm defined 1871 in this specification with a common GADAG root. The particular 1872 choice of a common GADAG root is expected to affect the quality of 1873 the MRT alternate paths, with a more central common GADAG root 1874 resulting in shorter MRT alternate path lengths. For this analysis, 1875 a single GADAG root was chosen for each topology by calculating the 1876 sum of costs of all shortest paths to and from a given node. The 1877 node with the lowest sum was chosen as the common GADAG root. In 1878 actual deployments, the common GADAG root would be chosen based on 1879 the GADAG Root Selection Priority advertised by each router, the 1880 values of which would be determined off-line. 1882 Both MRT and remote LFA have the option of using a local LFA in the 1883 alternate selection process. The details of the alternate selection 1884 processes used in this analysis are provided below. 1886 For the MRT analysis, for each source, destination, and primary next- 1887 hop, each alternate was chosen with the following priorty: 1889 1. node-protecting downstream local LFA 1891 2. node-protecting MRT alternate 1893 3. link-protecting downstream local LFA 1895 4. MRT alternate 1897 For the RLFA analysis, each alternate was chosen with the following 1898 priority: 1900 1. node-protecting local LFA 1902 2. link-protecting remote LFA providing node-protection 1904 3. link-protecting downstream local LFA 1906 4. link-protecting downstream remote LFA 1908 5. link-protecting local LFA 1910 6. link-protecting remote LFA 1912 7. Algorithm Work to Be Done 1914 Broadcast Interfaces: The algorithm assumes that broadcast 1915 interfaces are already represented as pseudo-nodes in the network 1916 graph. Given maximal redundancy, one of the MRT will try to avoid 1917 both the pseudo-node and the next hop. The exact rules need to be 1918 fully specified. 1920 8. IANA Considerations 1922 This doument includes no request to IANA. 1924 9. Security Considerations 1926 This architecture is not currently believed to introduce new security 1927 concerns. 1929 10. References 1931 10.1. Normative References 1933 [I-D.ietf-rtgwg-mrt-frr-architecture] 1934 Atlas, A., Kebler, R., Envedi, G., Csaszar, A., Tantsura, 1935 J., Konstantynowicz, M., and R. White, "An Architecture 1936 for IP/LDP Fast-Reroute Using Maximally Redundant Trees", 1937 draft-ietf-rtgwg-mrt-frr-architecture-03 (work in 1938 progress), July 2013. 1940 10.2. Informative References 1942 [EnyediThesis] 1943 Enyedi, G., "Novel Algorithms for IP Fast Reroute", 1944 Department of Telecommunications and Media Informatics, 1945 Budapest University of Technology and Economics Ph.D. 1946 Thesis, February 2011, . 1950 [I-D.atlas-ospf-mrt] 1951 Atlas, A., Hegde, S., Chris, C., and J. Tantsura, "OSPF 1952 Extensions to Support Maximally Redundant Trees", draft- 1953 atlas-ospf-mrt-00 (work in progress), July 2013. 1955 [I-D.ietf-rtgwg-ipfrr-notvia-addresses] 1956 Bryant, S., Previdi, S., and M. Shand, "A Framework for IP 1957 and MPLS Fast Reroute Using Not-via Addresses", draft- 1958 ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress), 1959 May 2013. 1961 [I-D.ietf-rtgwg-lfa-manageability] 1962 Litkowski, S., Decraene, B., Filsfils, C., and K. Raza, 1963 "Operational management of Loop Free Alternates", draft- 1964 ietf-rtgwg-lfa-manageability-00 (work in progress), May 1965 2013. 1967 [I-D.ietf-rtgwg-remote-lfa] 1968 Bryant, S., Filsfils, C., Previdi, S., Shand, M., and S. 1969 Ning, "Remote LFA FRR", draft-ietf-rtgwg-remote-lfa-02 1970 (work in progress), May 2013. 1972 [Kahn_1962_topo_sort] 1973 Kahn, A., "Topological sorting of large networks", 1974 Communications of the ACM, Volume 5, Issue 11 , Nov 1962, 1975 . 1977 [LFARevisited] 1978 Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP 1979 Fast ReRoute: Loop Free Alternates Revisited", Proceedings 1980 of IEEE INFOCOM , 2011, . 1983 [LightweightNotVia] 1984 Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP 1985 Fast ReRoute: Lightweight Not-Via without Additional 1986 Addresses", Proceedings of IEEE INFOCOM , 2009, 1987 . 1989 [MRTLinear] 1990 Enyedi, G., Retvari, G., and A. Csaszar, "On Finding 1991 Maximally Redundant Trees in Strictly Linear Time", IEEE 1992 Symposium on Computers and Comunications (ISCC) , 2009, 1993 . 1996 [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. 1997 McPherson, "OSPF Stub Router Advertisement", RFC 3137, 1998 June 2001. 2000 [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast 2001 Reroute: Loop-Free Alternates", RFC 5286, September 2008. 2003 [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC 2004 5714, January 2010. 2006 [RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., 2007 Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free 2008 Alternate (LFA) Applicability in Service Provider (SP) 2009 Networks", RFC 6571, June 2012. 2011 Appendix A. Option 2: Computing GADAG using SPFs 2013 The basic idea in this option is to use slightly-modified SPF 2014 computations to find ears. In every block, an SPF computation is 2015 first done to find a cycle from the local root and then SPF 2016 computations in that block find ears until there are no more 2017 interfaces to be explored. The used result from the SPF computation 2018 is the path of interfaces indicated by following the previous hops 2019 from the mininized IN_GADAG node back to the SPF root. 2021 To do this, first all cut-vertices must be identified and local-roots 2022 assigned as specified in Figure 12. 2024 The slight modifications to the SPF are as follows. The root of the 2025 block is referred to as the block-root; it is either the GADAG root 2026 or a cut-vertex. 2028 a. The SPF is rooted at a neighbor x of an IN_GADAG node y. All 2029 links between y and x are marked as TEMP_UNUSABLE. They should 2030 not be used during the SPF computation. 2032 b. If y is not the block-root, then it is marked TEMP_UNUSABLE. It 2033 should not be used during the SPF computation. This prevents 2034 ears from starting and ending at the same node and avoids cycles; 2035 the exception is because cycles to/from the block-root are 2036 acceptable and expected. 2038 c. Do not explore links to nodes whose local-root is not the block- 2039 root. This keeps the SPF confined to the particular block. 2041 d. Terminate when the first IN_GADAG node z is minimized. 2043 e. Respect the existing directions (e.g. INCOMING, OUTGOING, 2044 UNDIRECTED) already specified for each interface. 2046 Mod_SPF(spf_root, block_root) 2047 Initialize spf_heap to empty 2048 Initialize nodes' spf_metric to infinity 2049 spf_root.spf_metric = 0 2050 insert(spf_heap, spf_root) 2051 found_in_gadag = false 2052 while (spf_heap is not empty) and (found_in_gadag is false) 2053 min_node = remove_lowest(spf_heap) 2054 if min_node.IN_GADAG is true 2055 found_in_gadag = true 2056 else 2057 foreach interface intf of min_node 2058 if ((intf.OUTGOING or intf.UNDIRECTED) and 2059 ((intf.remote_node.localroot is block_root) or 2060 (intf.remote_node is block_root)) and 2061 (intf.remote_node is not TEMP_UNUSABLE) and 2062 (intf is not TEMP_UNUSABLE)) 2063 path_metric = min_node.spf_metric + intf.metric 2064 if path_metric < intf.remote_node.spf_metric 2065 intf.remote_node.spf_metric = path_metric 2066 intf.remote_node.spf_prev_intf = intf 2067 insert_or_update(spf_heap, intf.remote_node) 2068 return min_node 2070 SPF_for_Ear(cand_intf.local_node,cand_intf.remote_node, block_root, 2071 method) 2072 Mark all interfaces between cand_intf.remote_node 2073 and cand_intf.local_node as TEMP_UNUSABLE 2074 if cand_intf.local_node is not block_root 2075 Mark cand_intf.local_node as TEMP_UNUSABLE 2076 Initialize ear_list to empty 2077 end_ear = Mod_SPF(spf_root, block_root) 2078 y = end_ear.spf_prev_hop 2079 while y.local_node is not spf_root 2080 add_to_list_start(ear_list, y) 2081 y.local_node.IN_GADAG = true 2082 y = y.local_node.spf_prev_intf 2083 if(method is not hybrid) 2084 Set_Ear_Direction(ear_list, cand_intf.local_node, 2085 end_ear,block_root) 2086 Clear TEMP_UNUSABLE from all interfaces between 2087 cand_intf.remote_node and cand_intf.local_node 2088 Clear TEMP_UNUSABLE from cand_intf.local_node 2089 return end_ear 2091 Figure 28: Modified SPF for GADAG computation 2093 Assume that an ear is found by going from y to x and then running an 2094 SPF that terminates by minimizing z (e.g. y<->x...q<->z). Now it is 2095 necessary to determine the direction of the ear; if y << z, then the 2096 path should be y->x...q->z but if y >> z, then the path should be 2097 y<-x...q<-z. In Section 4.4, the same problem was handled by finding 2098 all ears that started at a node before looking at ears starting at 2099 nodes higher in the partial order. In this algorithm, using that 2100 approach could mean that new ears aren't added in order of their 2101 total cost since all ears connected to a node would need to be found 2102 before additional nodes could be found. 2104 The alternative is to track the order relationship of each node with 2105 respect to every other node. This can be accomplished by maintaining 2106 two sets of nodes at each node. The first set, Higher_Nodes, 2107 contains all nodes that are known to be ordered above the node. The 2108 second set, Lower_Nodes, contains all nodes that are known to be 2109 ordered below the node. This is the approach used in this algorithm. 2111 Set_Ear_Direction(ear_list, end_a, end_b, block_root) 2112 // Default of A_TO_B for the following cases: 2113 // (a) end_a and end_b are the same (root) 2114 // or (b) end_a is in end_b's Lower Nodes 2115 // or (c) end_a and end_b were unordered with respect to each 2116 // other 2117 direction = A_TO_B 2118 if (end_b is block_root) and (end_a is not end_b) 2119 direction = B_TO_A 2120 else if end_a is in end_b.Higher_Nodes 2121 direction = B_TO_A 2122 if direction is B_TO_A 2123 foreach interface i in ear_list 2124 i.UNDIRECTED = false 2125 i.INCOMING = true 2126 i.remote_intf.UNDIRECTED = false 2127 i.remote_intf.OUTGOING = true 2128 else 2129 foreach interface i in ear_list 2130 i.UNDIRECTED = false 2131 i.OUTGOING = true 2132 i.remote_intf.UNDIRECTED = false 2133 i.remote_intf.INCOMING = true 2134 if end_a is end_b 2135 return 2136 // Next, update all nodes' Lower_Nodes and Higher_Nodes 2137 if (end_a is in end_b.Higher_Nodes) 2138 foreach node x where x.localroot is block_root 2139 if end_a is in x.Lower_Nodes 2140 foreach interface i in ear_list 2141 add i.remote_node to x.Lower_Nodes 2142 if end_b is in x.Higher_Nodes 2143 foreach interface i in ear_list 2144 add i.local_node to x.Higher_Nodes 2145 else 2146 foreach node x where x.localroot is block_root 2147 if end_b is in x.Lower_Nodes 2148 foreach interface i in ear_list 2149 add i.local_node to x.Lower_Nodes 2150 if end_a is in x.Higher_Nodes 2151 foreach interface i in ear_list 2152 add i.remote_node to x.Higher_Nodes 2154 Figure 29: Algorithm to assign links of an ear direction 2156 A goal of the algorithm is to find the shortest cycles and ears. An 2157 ear is started by going to a neighbor x of an IN_GADAG node y. The 2158 path from x to an IN_GADAG node is minimal, since it is computed via 2159 SPF. Since a shortest path is made of shortest paths, to find the 2160 shortest ears requires reaching from the set of IN_GADAG nodes to the 2161 closest node that isn't IN_GADAG. Therefore, an ordered tree is 2162 maintained of interfaces that could be explored from the IN_GADAG 2163 nodes. The interfaces are ordered by their characteristics of 2164 metric, local loopback address, remote loopback address, and ifindex, 2165 as in the algorithm previously described in Figure 14. 2167 The algorithm ignores interfaces picked from the ordered tree that 2168 belong to the block root if the block in which the interface is 2169 present already has an ear that has been computed. This is necessary 2170 since we allow at most one incoming interface to a block root in each 2171 block. This requirement stems from the way next-hops are computed as 2172 will be seen in Section 4.6. After any ear gets computed, we 2173 traverse the newly added nodes to the GADAG and insert interfaces 2174 whose far end is not yet on the GADAG to the ordered tree for later 2175 processing. 2177 Finally, cut-edges are a special case because there is no point in 2178 doing an SPF on a block of 2 nodes. The algorithm identifies cut- 2179 edges simply as links where both ends of the link are cut-vertices. 2180 Cut-edges can simply be added to the GADAG with both OUTGOING and 2181 INCOMING specified on their interfaces. 2183 add_eligible_interfaces_of_node(ordered_intfs_tree,node) 2184 for each interface of node 2185 if intf.remote_node.IN_GADAG is false 2186 insert(intf,ordered_intfs_tree) 2188 check_if_block_has_ear(x,block_id) 2189 block_has_ear = false 2190 for all interfaces of x 2191 if (intf.remote_node.block_id == block_id) && 2192 (intf.remote_node.IN_GADAG is true) 2193 block_has_ear = true 2194 return block_has_ear 2196 Construct_GADAG_via_SPF(topology, root) 2197 Compute_Localroot (root,root) 2198 Assign_Block_ID(root,0) 2199 root.IN_GADAG = true 2200 add_eligible_interfaces_of_node(ordered_intfs_tree,root) 2201 while ordered_intfs_tree is not empty 2202 cand_intf = remove_lowest(ordered_intfs_tree) 2203 if cand_intf.remote_node.IN_GADAG is false 2204 if L(cand_intf.remote_node) == D(cand_intf.remote_node) 2205 // Special case for cut-edges 2206 cand_intf.UNDIRECTED = false 2207 cand_intf.remote_intf.UNDIRECTED = false 2208 cand_intf.OUTGOING = true 2209 cand_intf.INCOMING = true 2210 cand_intf.remote_intf.OUTGOING = true 2211 cand_intf.remote_intf.INCOMING = true 2212 cand_intf.remote_node.IN_GADAG = true 2213 add_eligible_interfaces_of_node( 2214 ordered_intfs_tree,cand_intf.remote_node) 2215 else 2216 if (cand_intf.remote_node.local_root == 2217 cand_intf.local_node) && 2218 check_if_block_has_ear 2219 (cand_intf.local_node, 2220 cand_intf.remote_node.block_id)) 2221 /* Skip the interface since the block root 2222 already has an incoming interface in the 2223 block */ 2224 else 2225 ear_end = SPF_for_Ear(cand_intf.local_node, 2226 cand_intf.remote_node, 2227 cand_intf.remote_node.localroot, 2228 SPF method) 2229 y = ear_end.spf_prev_hop 2230 while y.local_node is not cand_intf.local_node 2231 add_eligible_interfaces_of_node( 2232 ordered_intfs_tree, 2233 y.local_node) 2234 y = y.local_node.spf_prev_intf 2236 Figure 30: SPF-based GADAG algorithm 2238 Appendix B. Option 3: Computing GADAG using a hybrid method 2240 In this option, the idea is to combine the salient features of the 2241 above two options. To this end, we process nodes as they get added 2242 to the GADAG just like in the lowpoint inheritance by maintaining a 2243 stack of nodes. This ensures that we do not need to maintain lower 2244 and higher sets at each node to ascertain ear directions since the 2245 ears will always be directed from the node being processed towards 2246 the end of the ear. To compute the ear however, we resort to an SPF 2247 to have the possibility of better ears (path lentghs) thus giving 2248 more flexibility than the restricted use of lowpoint/dfs parents. 2250 Regarding ears involving a block root, unlike the SPF method which 2251 ignored interfaces of the block root after the first ear, in the 2252 hybrid method we would have to process all interfaces of the block 2253 root before moving on to other nodes in the block since the direction 2254 of an ear is pre-determined. Thus, whenever the block already has an 2255 ear computed, and we are processing an interface of the block root, 2256 we mark the block root as unusable before the SPF run that computes 2257 the ear. This ensures that the SPF terminates at some node other 2258 than the block-root. This in turn guarantees that the block-root has 2259 only one incoming interface in each block, which is necessary for 2260 correctly computing the next-hops on the GADAG. 2262 As in the SPF gadag, bridge ears are handled as a special case. 2264 The entire algorithm is shown below in Figure 31 2266 find_spf_stack_ear(stack, x, y, xy_intf, block_root) 2267 if L(y) == D(y) 2268 // Special case for cut-edges 2269 xy_intf.UNDIRECTED = false 2270 xy_intf.remote_intf.UNDIRECTED = false 2271 xy_intf.OUTGOING = true 2272 xy_intf.INCOMING = true 2273 xy_intf.remote_intf.OUTGOING = true 2274 xy_intf.remote_intf.INCOMING = true 2275 xy_intf.remote_node.IN_GADAG = true 2276 push y onto stack 2277 return 2278 else 2279 if (y.local_root == x) && 2280 check_if_block_has_ear(x,y.block_id) 2281 //Avoid the block root during the SPF 2282 Mark x as TEMP_UNUSABLE 2283 end_ear = SPF_for_Ear(x,y,block_root,hybrid) 2284 If x was set as TEMP_UNUSABLE, clear it 2285 cur = end_ear 2286 while (cur != y) 2287 intf = cur.spf_prev_hop 2288 prev = intf.local_node 2289 intf.UNDIRECTED = false 2290 intf.remote_intf.UNDIRECTED = false 2291 intf.OUTGOING = true 2292 intf.remote_intf.INCOMING = true 2293 push prev onto stack 2295 cur = prev 2296 xy_intf.UNDIRECTED = false 2297 xy_intf.remote_intf.UNDIRECTED = false 2298 xy_intf.OUTGOING = true 2299 xy_intf.remote_intf.INCOMING = true 2300 return 2302 Construct_GADAG_via_hybrid(topology,root) 2303 Compute_Localroot (root,root) 2304 Assign_Block_ID(root,0) 2305 root.IN_GADAG = true 2306 Initialize Stack to empty 2307 push root onto Stack 2308 while (Stack is not empty) 2309 x = pop(Stack) 2310 for each interface intf of x 2311 y = intf.remote_node 2312 if y.IN_GADAG is false 2313 find_spf_stack_ear(stack, x, y, intf, y.block_root) 2315 Figure 31: Hybrid GADAG algorithm 2317 Authors' Addresses 2319 Gabor Sandor Enyedi (editor) 2320 Ericsson 2321 Konyves Kalman krt 11 2322 Budapest 1097 2323 Hungary 2325 Email: Gabor.Sandor.Enyedi@ericsson.com 2327 Andras Csaszar 2328 Ericsson 2329 Konyves Kalman krt 11 2330 Budapest 1097 2331 Hungary 2333 Email: Andras.Csaszar@ericsson.com 2334 Alia Atlas (editor) 2335 Juniper Networks 2336 10 Technology Park Drive 2337 Westford, MA 01886 2338 USA 2340 Email: akatlas@juniper.net 2342 Chris Bowers 2343 Juniper Networks 2344 1194 N. Mathilda Ave. 2345 Sunnyvale, CA 94089 2346 USA 2348 Email: cbowers@juniper.net 2350 Abishek Gopalan 2351 University of Arizona 2352 1230 E Speedway Blvd. 2353 Tucson, AZ 85721 2354 USA 2356 Email: abishek@ece.arizona.edu