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