idnits 2.17.1 draft-ietf-rtgwg-mrt-frr-algorithm-05.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 74 instances of lines with non-RFC2606-compliant FQDNs in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords -- however, there's a paragraph with a matching beginning. Boilerplate error? (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- The document date (July 2, 2015) is 3219 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 1884, but not defined == Missing Reference: 'F' is mentioned on line 676, but not defined == Missing Reference: 'C' is mentioned on line 1884, but not defined == Missing Reference: 'G' is mentioned on line 1884, but not defined == Missing Reference: 'E' is mentioned on line 331, but not defined == Missing Reference: 'D' is mentioned on line 676, but not defined == Missing Reference: 'J' is mentioned on line 173, but not defined == Missing Reference: 'A' is mentioned on line 331, but not defined == Missing Reference: 'B' is mentioned on line 179, but not defined == Missing Reference: 'H' is mentioned on line 1376, but not defined == Missing Reference: 'K' is mentioned on line 676, but not defined == Missing Reference: 'N' is mentioned on line 676, but not defined == Missing Reference: 'X' is mentioned on line 1376, but not defined == Missing Reference: 'Y' is mentioned on line 1376, but not defined == Missing Reference: 'R-small' is mentioned on line 1335, but not defined == Missing Reference: 'R-great' is mentioned on line 1351, but not defined == Missing Reference: 'I' is mentioned on line 1884, but not defined == Unused Reference: 'I-D.ietf-mpls-ldp-mrt' is defined on line 3540, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-rtgwg-ipfrr-notvia-addresses' is defined on line 3551, but no explicit reference was found in the text == Unused Reference: 'LFARevisited' is defined on line 3568, but no explicit reference was found in the text == Unused Reference: 'LightweightNotVia' is defined on line 3575, but no explicit reference was found in the text == Unused Reference: 'RFC3137' is defined on line 3588, but no explicit reference was found in the text == Unused Reference: 'RFC5286' is defined on line 3596, but no explicit reference was found in the text == Unused Reference: 'RFC5714' is defined on line 3599, but no explicit reference was found in the text == Unused Reference: 'RFC6571' is defined on line 3602, 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 (-03) exists of draft-ietf-isis-mrt-00 == Outdated reference: A later version (-05) exists of draft-ietf-isis-pcr-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 -- Obsolete informational reference (is this intentional?): RFC 3137 (Obsoleted by RFC 6987) Summary: 1 error (**), 0 flaws (~~), 33 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: January 3, 2016 A. Atlas, Ed. 6 C. Bowers 7 Juniper Networks 8 A. Gopalan 9 University of Arizona 10 July 2, 2015 12 Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- 13 Reroute 14 draft-ietf-rtgwg-mrt-frr-algorithm-05 16 Abstract 18 A complete solution for IP and LDP Fast-Reroute using Maximally 19 Redundant Trees is presented in [I-D.ietf-rtgwg-mrt-frr- 20 architecture]. This document defines the associated MRT Lowpoint 21 algorithm that is used in the default MRT profile to compute both the 22 necessary Maximally Redundant Trees with their associated next-hops 23 and the alternates to select for MRT-FRR. 25 Status of This Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at http://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on January 3, 2016. 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 . . . . . . . . . . . . . . . . . . 30 77 5.7.1. MRT next-hops to all nodes partially ordered with 78 respect to the computing node . . . . . . . . . . . . 30 79 5.7.2. MRT next-hops to all nodes not partially ordered with 80 respect to the computing node . . . . . . . . . . . . 31 81 5.7.3. Computing Redundant Tree next-hops in a 2-connected 82 Graph . . . . . . . . . . . . . . . . . . . . . . . . 32 83 5.7.4. Generalizing for a graph that isn't 2-connected . . . 34 84 5.7.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 35 85 5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 37 86 5.9. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 42 87 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 45 88 7. Python Implementation of MRT Lowpoint Algorithm . . . . . . . 45 89 8. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 66 90 8.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 66 91 9. Implementation Status . . . . . . . . . . . . . . . . . . . . 76 92 10. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 76 93 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 76 94 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 76 95 13. Security Considerations . . . . . . . . . . . . . . . . . . . 76 96 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 76 97 14.1. Normative References . . . . . . . . . . . . . . . . . . 76 98 14.2. Informative References . . . . . . . . . . . . . . . . . 77 99 Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 79 100 Appendix B. Option 3: Computing GADAG using a hybrid method . . 84 101 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 86 103 1. Introduction 105 MRT Fast-Reroute requires that packets can be forwarded not only on 106 the shortest-path tree, but also on two Maximally Redundant Trees 107 (MRTs), referred to as the MRT-Blue and the MRT-Red. A router which 108 experiences a local failure must also have pre-determined which 109 alternate to use. This document defines how to compute these three 110 things for use in MRT-FRR and describes the algorithm design 111 decisions and rationale. The algorithm is based on those presented 112 in [MRTLinear] and expanded in [EnyediThesis]. The MRT Lowpoint 113 algorithm is required for implementation when the default MRT profile 114 is implemented. 116 Just as packets routed on a hop-by-hop basis require that each router 117 compute a shortest-path tree which is consistent, it is necessary for 118 each router to compute the MRT-Blue next-hops and MRT-Red next-hops 119 in a consistent fashion. This document defines the MRT Lowpoint 120 algorithm to be used as a standard in the default MRT profile for 121 MRT-FRR. 123 As now, a router's FIB will contain primary next-hops for the current 124 shortest-path tree for forwarding traffic. In addition, a router's 125 FIB will contain primary next-hops for the MRT-Blue for forwarding 126 received traffic on the MRT-Blue and primary next-hops for the MRT- 127 Red for forwarding received traffic on the MRT-Red. 129 What alternate next-hops a point-of-local-repair (PLR) selects need 130 not be consistent - but loops must be prevented. To reduce 131 congestion, it is possible for multiple alternate next-hops to be 132 selected; in the context of MRT alternates, each of those alternate 133 next-hops would be equal-cost paths. 135 This document defines an algorithm for selecting an appropriate MRT 136 alternate for consideration. Other alternates, e.g. LFAs that are 137 downstream paths, may be prefered when available and that policy- 138 based alternate selection process[I-D.ietf-rtgwg-lfa-manageability] 139 is not captured in this document. 141 [E]---[D]---| [E]<--[D]<--| [E]-->[D] 142 | | | | ^ | | 143 | | | V | | V 144 [R] [F] [C] [R] [F] [C] [R] [F] [C] 145 | | | ^ ^ | | 146 | | | | | V | 147 [A]---[B]---| [A]-->[B] [A]---[B]<--| 149 (a) (b) (c) 150 a 2-connected graph MRT-Blue towards R MRT-Red towards R 152 Figure 1 154 Algorithms for computing MRTs can handle arbitrary network topologies 155 where the whole network graph is not 2-connected, as in Figure 2, as 156 well as the easier case where the network graph is 2-connected 157 (Figure 1). Each MRT is a spanning tree. The pair of MRTs provide 158 two paths from every node X to the root of the MRTs. Those paths 159 share the minimum number of nodes and the minimum number of links. 160 Each such shared node is a cut-vertex. Any shared links are cut- 161 links. 163 [E]---[D]---| |---[J] 164 | | | | | 165 | | | | | 166 [R] [F] [C]---[G] | 167 | | | | | 168 | | | | | 169 [A]---[B]---| |---[H] 171 (a) a graph that isn't 2-connected 173 [E]<--[D]<--| [J] [E]-->[D]---| |---[J] 174 | ^ | | | | | ^ 175 V | | | V V V | 176 [R] [F] [C]<--[G] | [R] [F] [C]<--[G] | 177 ^ ^ ^ | ^ | | | 178 | | | V | V | | 179 [A]-->[B]---| |---[H] [A]<--[B]<--| [H] 181 (b) MRT-Blue towards R (c) MRT-Red towards R 183 Figure 2 185 2. Requirements Language 187 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 188 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 189 document are to be interpreted as described in [RFC2119] 191 3. Terminology and Definitions 193 network graph: A graph that reflects the network topology where all 194 links connect exactly two nodes and broadcast links have been 195 transformed into a pseudo-node representation (e.g. in OSPF, 196 viewing a Network LSA as representing a pseudo-noe). 198 Redundant Trees (RT): A pair of trees where the path from any node X 199 to the root R on the first tree is node-disjoint with the path 200 from the same node X to the root along the second tree. These can 201 be computed in 2-connected graphs. 203 Maximally Redundant Trees (MRT): A pair of trees where the path 204 from any node X to the root R along the first tree and the path 205 from the same node X to the root along the second tree share the 206 minimum number of nodes and the minimum number of links. Each 207 such shared node is a cut-vertex. Any shared links are cut-links. 208 Any RT is an MRT but many MRTs are not RTs. 210 MRT Island: From the computing router, the set of routers that 211 support a particular MRT profile and are connected. 213 MRT-Red: MRT-Red is used to describe one of the two MRTs; it is 214 used to describe the associated forwarding topology and MT-ID. 215 Specifically, MRT-Red is the decreasing MRT where links in the 216 GADAG are taken in the direction from a higher topologically 217 ordered node to a lower one. 219 MRT-Blue: MRT-Blue is used to describe one of the two MRTs; it is 220 used to describe the associated forwarding topology and MT-ID. 221 Specifically, MRT-Blue is the increasing MRT where links in the 222 GADAG are taken in the direction from a lower topologically 223 ordered node to a higher one. 225 cut-vertex: A vertex whose removal partitions the network. 227 cut-link: A link whose removal partitions the network. A cut-link 228 by definition must be connected between two cut-vertices. If 229 there are multiple parallel links, then they are referred to as 230 cut-links in this document if removing the set of parallel links 231 would partition the network. 233 2-connected: A graph that has no cut-vertices. This is a graph 234 that requires two nodes to be removed before the network is 235 partitioned. 237 spanning tree: A tree containing links that connects all nodes in 238 the network graph. 240 back-edge: In the context of a spanning tree computed via a depth- 241 first search, a back-edge is a link that connects a descendant of 242 a node x with an ancestor of x. 244 2-connected cluster: A maximal set of nodes that are 2-connected. 245 In a network graph with at least one cut-vertex, there will be 246 multiple 2-connected clusters. 248 block: Either a 2-connected cluster, a cut-link, or an isolated 249 vertex. 251 DAG: Directed Acyclic Graph - a digraph containing no directed 252 cycle. 254 ADAG: Almost Directed Acyclic Graph - a digraph that can be 255 transformed into a DAG with removing a single node (the root 256 node). 258 partial ADAG: A subset of an ADAG that doesn't yet contain all the 259 nodes in the block. A partial ADAG is created during the MRT 260 algorithm and then expanded until all nodes in the block are 261 included and it is an ADAG. 263 GADAG: Generalized ADAG - a digraph, which has only ADAGs as all of 264 its blocks. The root of such a block is the node closest to the 265 global root (e.g. with uniform link costs). 267 DFS: Depth-First Search 269 DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS- 270 tree path from the DFS root to x. 272 DFS descendant: A node n is a DFS descendant of x if x is on the 273 DFS-tree path from the DFS root to n. 275 ear: A path along not-yet-included-in-the-GADAG nodes that starts 276 at a node that is already-included-in-the-GADAG and that ends at a 277 node that is already-included-in-the-GADAG. The starting and 278 ending nodes may be the same node if it is a cut-vertex. 280 X >> Y or Y << X: Indicates the relationship between X and Y in a 281 partial order, such as found in a GADAG. X >> Y means that X is 282 higher in the partial order than Y. Y << X means that Y is lower 283 in the partial order than X. 285 X > Y or Y < X: Indicates the relationship between X and Y in the 286 total order, such as found via a topological sort. X > Y means 287 that X is higher in the total order than Y. Y < X means that Y is 288 lower in the total order than X. 290 proxy-node: A node added to the network graph to represent a multi- 291 homed prefix or routers outside the local MRT-fast-reroute- 292 supporting island of routers. The key property of proxy-nodes is 293 that traffic cannot transit them. 295 UNDIRECTED: In the GADAG, each link is marked as OUTGOING, INCOMING 296 or both. Until the directionality of the link is determined, the 297 link is marked as UNDIRECTED to indicate that its direction hasn't 298 been determined. 300 OUTGOING: A link marked as OUTGOING has direction in the GADAG from 301 the interface's router to the remote end. 303 INCOMING: A link marked as INCOMING has direction in the GADAG from 304 the remote end to the interface's router. 306 4. Algorithm Key Concepts 308 There are five key concepts that are critical for understanding the 309 MRT Lowpoint algorithm and other algorithms for computing MRTs. The 310 first is the idea of partially ordering the nodes in a network graph 311 with regard to each other and to the GADAG root. The second is the 312 idea of finding an ear of nodes and adding them in the correct 313 direction. The third is the idea of a Low-Point value and how it can 314 be used to identify cut-vertices and to find a second path towards 315 the root. The fourth is the idea that a non-2-connected graph is 316 made up of blocks, where a block is a 2-connected cluster, a cut-link 317 or an isolated node. The fifth is the idea of a local-root for each 318 node; this is used to compute ADAGs in each block. 320 4.1. Partial Ordering for Disjoint Paths 322 Given any two nodes X and Y in a graph, a particular total order 323 means that either X < Y or X > Y in that total order. An example 324 would be a graph where the nodes are ranked based upon their unique 325 IP loopback addresses. In a partial order, there may be some nodes 326 for which it can't be determined whether X << Y or X >> Y. A partial 327 order can be captured in a directed graph, as shown in Figure 3. In 328 a graphical representation, a link directed from X to Y indicates 329 that X is a neighbor of Y in the network graph and X << Y. 331 [A]<---[R] [E] R << A << B << C << D << E 332 | ^ R << A << B << F << G << H << D << E 333 | | 334 V | Unspecified Relationships: 335 [B]--->[C]--->[D] C and F 336 | ^ C and G 337 | | C and H 338 V | 339 [F]--->[G]--->[H] 341 Figure 3: Directed Graph showing a Partial Order 343 To compute MRTs, the root of the MRTs is at both the very bottom and 344 the very top of the partial ordering. This means that from any node 345 X, one can pick nodes higher in the order until the root is reached. 346 Similarly, from any node X, one can pick nodes lower in the order 347 until the root is reached. For instance, in Figure 4, from G the 348 higher nodes picked can be traced by following the directed links and 349 are H, D, E and R. Similarly, from G the lower nodes picked can be 350 traced by reversing the directed links and are F, B, A, and R. A 351 graph that represents this modified partial order is no longer a DAG; 352 it is termed an Almost DAG (ADAG) because if the links directed to 353 the root were removed, it would be a DAG. 355 [A]<---[R]<---[E] R << A << B << C << R 356 | ^ ^ R << A << B << C << D << E << R 357 | | | R << A << B << F << G << H << D << E << R 358 V | | 359 [B]--->[C]--->[D] Unspecified Relationships: 360 | ^ C and F 361 | | C and G 362 V | C and H 363 [F]--->[G]--->[H] 365 Figure 4: ADAG showing a Partial Order with R lowest and highest 367 Most importantly, if a node Y >> X, then Y can only appear on the 368 increasing path from X to the root and never on the decreasing path. 369 Similarly, if a node Z << X, then Z can only appear on the decreasing 370 path from X to the root and never on the inceasing path. 372 When following the increasing paths, it is possible to pick multiple 373 higher nodes and still have the certainty that those paths will be 374 disjoint from the decreasing paths. E.g. in the previous example 375 node B has multiple possibilities to forward packets along an 376 increasing path: it can either forward packets to C or F. 378 4.2. Finding an Ear and the Correct Direction 380 For simplicity, the basic idea of creating a GADAG by adding ears is 381 described assuming that the network graph is a single 2-connected 382 cluster so that an ADAG is sufficient. Generalizing to multiple 383 blocks is done by considering the block-roots instead of the GADAG 384 root - and the actual algorithm is given in Section 5.5. 386 In order to understand the basic idea of finding an ADAG, first 387 suppose that we have already a partial ADAG, which doesn't contain 388 all the nodes in the block yet, and we want to extend it to cover all 389 the nodes. Suppose that we find a path from a node X to Y such that 390 X and Y are already contained by our partial ADAG, but all the 391 remaining nodes along the path are not added to the ADAG yet. We 392 refer to such a path as an ear. 394 Recall that our ADAG is closely related to a partial order. More 395 precisely, if we remove root R, the remaining DAG describes a partial 396 order of the nodes. If we suppose that neither X nor Y is the root, 397 we may be able to compare them. If one of them is definitely lesser 398 with respect to our partial order (say X<B---| A-->B---| 410 (a) (b) (c) 412 (a) A 2-connected graph 413 (b) Partial ADAG (C is not included) 414 (c) Resulting ADAG after adding path (or ear) B-C-D 416 Figure 5 418 In this partial ADAG, node C is not yet included. However, we can 419 find path B-C-D, where both endpoints are contained by this partial 420 ADAG (we say those nodes are "ready" in the following text), and the 421 remaining node (node C) is not contained yet. If we remove R, the 422 remaining DAG defines a partial order, and with respect to this 423 partial order we can say that B<C and C->D are added). If 425 B >> D, we would add the same path in reverse direction. 427 If in the partial order where an ear's two ends are X and Y, X << Y, 428 then there must already be a directed path from X to Y in the ADAG. 429 The ear must be added in a direction such that it doesn't create a 430 cycle; therefore the ear must go from X to Y. 432 In the case, when X and Y are not ordered with each other, we can 433 select either direction for the ear. We have no restriction since 434 neither of the directions can result in a cycle. In the corner case 435 when one of the endpoints of an ear, say X, is the root (recall that 436 the two endpoints must be different), we could use both directions 437 again for the ear because the root can be considered both as smaller 438 and as greater than Y. However, we strictly pick that direction in 439 which the root is lower than Y. The logic for this decision is 440 explained in Section 5.7 442 A partial ADAG is started by finding a cycle from the root R back to 443 itself. This can be done by selecting a non-ready neighbor N of R 444 and then finding a path from N to R that doesn't use any links 445 between R and N. The direction of the cycle can be assigned either 446 way since it is starting the ordering. 448 Once a partial ADAG is already present, it will always have a node 449 that is not the root R in it. As a brief proof that a partial ADAG 450 can always have ears added to it: just select a non-ready neighbor N 451 of a ready node Q, such that Q is not the root R, find a path from N 452 to the root R in the graph with Q removed. This path is an ear where 453 the first node of the ear is Q, the next is N, then the path until 454 the first ready node the path reached (that ready node is the other 455 endpoint of the path). Since the graph is 2-connected, there must be 456 a path from N to R without Q. 458 It is always possible to select a non-ready neighbor N of a ready 459 node Q so that Q is not the root R. Because the network is 460 2-connected, N must be connected to two different nodes and only one 461 can be R. Because the initial cycle has already been added to the 462 ADAG, there are ready nodes that are not R. Since the graph is 463 2-connected, while there are non-ready nodes, there must be a non- 464 ready neighbor N of a ready node that is not R. 466 Generic_Find_Ears_ADAG(root) 467 Create an empty ADAG. Add root to the ADAG. 468 Mark root as IN_GADAG. 469 Select an arbitrary cycle containing root. 470 Add the arbitrary cycle to the ADAG. 471 Mark cycle's nodes as IN_GADAG. 472 Add cycle's non-root nodes to process_list. 473 while there exists connected nodes in graph that are not IN_GADAG 474 Select a new ear. Let its endpoints be X and Y. 475 if Y is root or (Y << X) 476 add the ear towards X to the ADAG 477 else // (a) X is root or (b)X << Y or (c) X, Y not ordered 478 Add the ear towards Y to the ADAG 480 Figure 6: Generic Algorithm to find ears and their direction in 481 2-connected graph 483 Algorithm Figure 6 merely requires that a cycle or ear be selected 484 without specifying how. Regardless of the way of selecting the path, 485 we will get an ADAG. The method used for finding and selecting the 486 ears is important; shorter ears result in shorter paths along the 487 MRTs. The MRT Lowpoint algorithm's method using Low-Point 488 Inheritance is defined in Section 5.5. Other methods are described 489 in the Appendices (Appendix A and Appendix B). 491 As an example, consider Figure 5 again. First, we select the 492 shortest cycle containing R, which can be R-A-B-F-D-E (uniform link 493 costs were assumed), so we get to the situation depicted in Figure 5 494 (b). Finally, we find a node next to a ready node; that must be node 495 C and assume we reached it from ready node B. We search a path from 496 C to R without B in the original graph. The first ready node along 497 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 499 this point. 501 4.3. Low-Point Values and Their Uses 503 A basic way of computing a spanning tree on a network graph is to run 504 a depth-first-search, such as given in Figure 7. This tree has the 505 important property that if there is a link (x, n), then either n is a 506 DFS ancestor of x or n is a DFS descendant of x. In other words, 507 either n is on the path from the root to x or x is on the path from 508 the root to n. 510 global_variable: dfs_number 512 DFS_Visit(node x, node parent) 513 D(x) = dfs_number 514 dfs_number += 1 515 x.dfs_parent = parent 516 for each link (x, w) 517 if D(w) is not set 518 DFS_Visit(w, x) 520 Run_DFS(node gadag_root) 521 dfs_number = 0 522 DFS_Visit(gadag_root, NONE) 524 Figure 7: Basic Depth-First Search algorithm 526 Given a node x, one can compute the minimal DFS number of the 527 neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the 528 earliest attachment point neighbouring x. What is interesting, 529 though, is what is the earliest attachment point from x and x's 530 descendants. This is what is determined by computing the Low-Point 531 value. 533 In order to compute the low point value, the network is traversed 534 using DFS and the vertices are numbered based on the DFS walk. Let 535 this number be represented as DFS(x). All the edges that lead to 536 already visited nodes during DFS walk are back-edges. The back-edges 537 are important because they give information about reachability of a 538 node via another path. 540 The low point number is calculated by finding: 542 Low(x) = Minimum of ( (DFS(x), 543 Lowest DFS(n, x->n is a back-edge), 544 Lowest Low(n, x->n is tree edge in DFS walk) ). 546 A detailed algorithm for computing the low-point value is given in 547 Figure 8. Figure 9 illustrates how the lowpoint algorithm applies to 548 a example graph. 550 global_variable: dfs_number 552 Lowpoint_Visit(node x, node parent, interface p_to_x) 553 D(x) = dfs_number 554 L(x) = D(x) 555 dfs_number += 1 556 x.dfs_parent = parent 557 x.dfs_parent_intf = p_to_x.remote_intf 558 x.lowpoint_parent = NONE 559 for each ordered_interface intf of x 560 if D(intf.remote_node) is not set 561 Lowpoint_Visit(intf.remote_node, x, intf) 562 if L(intf.remote_node) < L(x) 563 L(x) = L(intf.remote_node) 564 x.lowpoint_parent = intf.remote_node 565 x.lowpoint_parent_intf = intf 566 else if intf.remote_node is not parent 567 if D(intf.remote_node) < L(x) 568 L(x) = D(intf.remote_node) 569 x.lowpoint_parent = intf.remote_node 570 x.lowpoint_parent_intf = intf 572 Run_Lowpoint(node gadag_root) 573 dfs_number = 0 574 Lowpoint_Visit(gadag_root, NONE, NONE) 576 Figure 8: Computing Low-Point value 578 [E]---| [J]-------[I] [P]---[O] 579 | | | | | | 580 | | | | | | 581 [R] [D]---[C]--[F] [H]---[K] [N] 582 | | | | | | 583 | | | | | | 584 [A]--------[B] [G]---| [L]---[M] 586 (a) a non-2-connected graph 588 [E]----| [J]---------[I] [P]------[O] 589 (5, ) | (10, ) (9, ) (16, ) (15, ) 590 | | | | | | 591 | | | | | | 592 [R] [D]---[C]---[F] [H]----[K] [N] 593 (0, ) (4, ) (3, ) (6, ) (8, ) (11, ) (14, ) 594 | | | | | | 595 | | | | | | 596 [A]---------[B] [G]----| [L]------[M] 597 (1, ) (2, ) (7, ) (12, ) (13, ) 599 (b) with DFS values assigned (D(x), L(x)) 601 [E]----| [J]---------[I] [P]------[O] 602 (5,0) | (10,3) (9,3) (16,11) (15,11) 603 | | | | | | 604 | | | | | | 605 [R] [D]---[C]---[F] [H]----[K] [N] 606 (0,0) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11) 607 | | | | | | 608 | | | | | | 609 [A]---------[B] [G]----| [L]------[M] 610 (1,0) (2,0) (7,3) (12,11) (13,11) 612 (c) with low-point values assigned (D(x), L(x)) 614 Figure 9: Example lowpoint value computation 616 From the low-point value and lowpoint parent, there are three very 617 useful things which motivate our computation. 619 First, if there is a child c of x such that L(c) >= D(x), then there 620 are no paths in the network graph that go from c or its descendants 621 to an ancestor of x - and therefore x is a cut-vertex. In Figure 9, 622 this can be seen by looking at the DFS children of C. C has two 623 children - D and F and L(F) = 3 = D(C) so it is clear that C is a 624 cut-vertex and F is in a block where C is the block's root. L(D) = 0 625 < 3 = D(C) so D has a path to the ancestors of C; in this case, D can 626 go via E to reach R. Comparing the low-point values of all a node's 627 DFS-children with the node's DFS-value is very useful because it 628 allows identification of the cut-vertices and thus the blocks. 630 Second, by repeatedly following the path given by lowpoint_parent, 631 there is a path from x back to an ancestor of x that does not use the 632 link [x, x.dfs_parent] in either direction. The full path need not 633 be taken, but this gives a way of finding an initial cycle and then 634 ears. 636 Third, as seen in Figure 9, even if L(x) < D(x), there may be a block 637 that contains both the root and a DFS-child of a node while other 638 DFS-children might be in different blocks. In this example, C's 639 child D is in the same block as R while F is not. It is important to 640 realize that the root of a block may also be the root of another 641 block. 643 4.4. Blocks in a Graph 645 A key idea for an MRT algorithm is that any non-2-connected graph is 646 made up by blocks (e.g. 2-connected clusters, cut-links, and/or 647 isolated nodes). To compute GADAGs and thus MRTs, computation is 648 done in each block to compute ADAGs or Redundant Trees and then those 649 ADAGs or Redundant Trees are combined into a GADAG or MRT. 651 [E]---| [J]-------[I] [P]---[O] 652 | | | | | | 653 | | | | | | 654 [R] [D]---[C]--[F] [H]---[K] [N] 655 | | | | | | 656 | | | | | | 657 [A]--------[B] [G]---| [L]---[M] 659 (a) A graph with four blocks that are: 660 three 2-connected clusters 661 and one cut-link 663 [E]<--| [J]<------[I] [P]<--[O] 664 | | | ^ | ^ 665 V | V | V | 666 [R] [D]<--[C] [F] [H]<---[K] [N] 667 ^ | ^ ^ 668 | V | | 669 [A]------->[B] [G]---| [L]-->[M] 671 (b) MRT-Blue for destination R 673 [E]---| [J]-------->[I] [P]-->[O] 674 | | | 675 V V V 676 [R] [D]-->[C]<---[F] [H]<---[K] [N] 677 ^ | ^ | ^ | 678 | V | | | V 679 [A]<-------[B] [G]<--| [L]<--[M] 681 (c) MRT-Red for destionation R 683 Figure 10 685 Consider the example depicted in Figure 10 (a). In this figure, a 686 special graph is presented, showing us all the ways 2-connected 687 clusters can be connected. It has four blocks: block 1 contains R, 688 A, B, C, D, E, block 2 contains C, F, G, H, I, J, block 3 contains K, 689 L, M, N, O, P, and block 4 is a cut-link containing H and K. As can 690 be observed, the first two blocks have one common node (node C) and 691 blocks 2 and 3 do not have any common node, but they are connected 692 through a cut-link that is block 4. No two blocks can have more than 693 one common node, since two blocks with at least two common nodes 694 would qualify as a single 2-connected cluster. 696 Moreover, observe that if we want to get from one block to another, 697 we must use a cut-vertex (the cut-vertices in this graph are C, H, 698 K), regardless of the path selected, so we can say that all the paths 699 from block 3 along the MRTs rooted at R will cross K first. This 700 observation means that if we want to find a pair of MRTs rooted at R, 701 then we need to build up a pair of RTs in block 3 with K as a root. 702 Similarly, we need to find another pair of RTs in block 2 with C as a 703 root, and finally, we need the last pair of RTs in block 1 with R as 704 a root. When all the trees are selected, we can simply combine them; 705 when a block is a cut-link (as in block 4), that cut-link is added in 706 the same direction to both of the trees. The resulting trees are 707 depicted in Figure 10 (b) and (c). 709 Similarly, to create a GADAG it is sufficient to compute ADAGs in 710 each block and connect them. 712 It is necessary, therefore, to identify the cut-vertices, the blocks 713 and identify the appropriate local-root to use for each block. 715 4.5. Determining Local-Root and Assigning Block-ID 717 Each node in a network graph has a local-root, which is the cut- 718 vertex (or root) in the same block that is closest to the root. The 719 local-root is used to determine whether two nodes share a common 720 block. 722 Compute_Localroot(node x, node localroot) 723 x.localroot = localroot 724 for each DFS child node c of x 725 if L(c) < D(x) //x is not a cut-vertex 726 Compute_Localroot(c, x.localroot) 727 else 728 mark x as cut-vertex 729 Compute_Localroot(c, x) 731 Compute_Localroot(gadag_root, gadag_root) 733 Figure 11: A method for computing local-roots 735 There are two different ways of computing the local-root for each 736 node. The stand-alone method is given in Figure 11 and better 737 illustrates the concept; it is used by the MRT algorithms given in 738 the Appendices Appendix A and Appendix B. The MRT Lowpoint algorithm 739 computes the local-root for a block as part of computing the GADAG 740 using lowpoint inheritance; the essence of this computation is given 741 in Figure 12. Both methods for computing the local-root produce the 742 same results. 744 Get the current node, s. 745 Compute an ear(either through lowpoint inheritance 746 or by following dfs parents) from s to a ready node e. 747 (Thus, s is not e, if there is such ear.) 748 if s is e 749 for each node x in the ear that is not s 750 x.localroot = s 751 else 752 for each node x in the ear that is not s or e 753 x.localroot = e.localroot 755 Figure 12: Ear-based method for computing local-roots 757 Once the local-roots are known, two nodes X and Y are in a common 758 block if and only if one of the following three conditions apply. 760 o Y's local-root is X's local-root : They are in the same block and 761 neither is the cut-vertex closest to the root. 763 o Y's local-root is X: X is the cut-vertex closest to the root for 764 Y's block 766 o Y is X's local-root: Y is the cut-vertex closest to the root for 767 X's block 769 Once we have computed the local-root for each node in the network 770 graph, we can assign for each node, a block id that represents the 771 block in which the node is present. This computation is shown in 772 Figure 13. 774 global_var: max_block_id 776 Assign_Block_ID(x, cur_block_id) 777 x.block_id = cur_block_id 778 foreach DFS child c of x 779 if (c.local_root is x) 780 max_block_id += 1 781 Assign_Block_ID(c, max_block_id) 782 else 783 Assign_Block_ID(c, cur_block_id) 785 max_block_id = 0 786 Assign_Block_ID(gadag_root, max_block_id) 788 Figure 13: Assigning block id to identify blocks 790 5. Algorithm Sections 792 This algorithm computes one GADAG that is then used by a router to 793 determine its MRT-Blue and MRT-Red next-hops to all destinations. 794 Finally, based upon that information, alternates are selected for 795 each next-hop to each destination. The different parts of this 796 algorithm are described below. These work on a network graph after 797 its interfaces have been ordered as per Figure 14. 799 1. Compute the local MRT Island for the particular MRT Profile. 800 [See Section 5.2.] 802 2. Select the root to use for the GADAG. [See Section 5.3.] 804 3. Initialize all interfaces to UNDIRECTED. [See Section 5.4.] 806 4. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See 807 Figure 8.] 809 5. Construct the GADAG. [See Section 5.5] 811 6. Assign directions to all interfaces that are still UNDIRECTED. 812 [See Section 5.6.] 814 7. From the computing router x, compute the next-hops for the MRT- 815 Blue and MRT-Red. [See Section 5.7.] 817 8. Identify alternates for each next-hop to each destination by 818 determining which one of the blue MRT and the red MRT the 819 computing router x should select. [See Section 5.8.] 821 5.1. Interface Ordering 823 To ensure consistency in computation, all routers MUST order 824 interfaces identically down to the set of links with the same metric 825 to the same neighboring node. This is necessary for the DFS in 826 Lowpoint_Visit in Section 4.3, where the selection order of the 827 interfaces to explore results in different trees. Consistent 828 interface ordering is also necessary for computing the GADAG, where 829 the selection order of the interfaces to use to form ears can result 830 in different GADAGs. It is also necessary for the topological sort 831 described in Section 5.8, where different topological sort orderings 832 can result in undirected links being added to the GADAG in different 833 directions. 835 The required ordering between two interfaces from the same router x 836 is given in Figure 14. 838 Interface_Compare(interface a, interface b) 839 if a.metric < b.metric 840 return A_LESS_THAN_B 841 if b.metric < a.metric 842 return B_LESS_THAN_A 843 if a.neighbor.mrt_node_id < b.neighbor.mrt_node_id 844 return A_LESS_THAN_B 845 if b.neighbor.mrt_node_id < a.neighbor.mrt_node_id 846 return B_LESS_THAN_A 847 // Same metric to same node, so the order doesn't matter for 848 // interoperability. 849 return A_EQUAL_TO_B 851 Figure 14: Rules for ranking multiple interfaces. Order is from low 852 to high. 854 In Figure 14, if two interfaces on a router connect to the same 855 remote router with the same metric, the Interface_Compare function 856 returns A_EQUAL_TO_B. This is because the order in which those 857 interfaces are initially explored does not affect the final GADAG 858 produced by the algorithm described here. While only one of the 859 links will be added to the GADAG in the initial traversal, the other 860 parallel links will be added to the GADAG with the same direction 861 assigned during the procedure for assigning direction to UNDIRECTED 862 links described in Section 5.6. An implementation is free to apply 863 some additional criteria to break ties in interface ordering in this 864 situation, but that criteria is not specified here since it will not 865 affect the final GADAG produced by the algorithm. 867 The Interface_Compare function in Figure 14 relies on the 868 interface.metric and the interface.neighbor.mrt_node_id values to 869 order interfaces. The exact source of these values for different 870 IGPs (or flooding protocol in the case of ISIS-PCR 871 [I-D.ietf-isis-pcr]) and applications is specified in Figure 15. The 872 metric and mrt_node_id values for OSPFv2, OSPFv3, and IS-IS provided 873 here is normative. The metric and mrt_node_id values for ISIS-PCR 874 should be considered informational. 876 +--------------+-----------------------+-----------------------------+ 877 | IGP/flooding | mrt_node_id | metric of | 878 | protocol | of neighbor | interface | 879 | and | on interface | | 880 | application | | | 881 +--------------+-----------------------+-----------------------------+ 882 | OSPFv2 for | 4 octet Neighbor | 2 octet Metric field | 883 | IP/LDP FRR | Router ID in | for corresponding | 884 | | Link ID field for | point-to-point link | 885 | | corresponding | in Router-LSA | 886 | | point-to-point link | | 887 | | in Router-LSA | | 888 +--------------+-----------------------+-----------------------------+ 889 | OSPFv3 for | 4 octet Neighbor | 2 octet Metric field | 890 | IP/LDP FRR | Router ID field | for corresponding | 891 | | for corresponding | point-to-point link | 892 | | point-to-point link | in Router-LSA | 893 | | in Router-LSA | | 894 +--------------+-----------------------+-----------------------------+ 895 | IS-IS for | 7 octet neighbor | 3 octet metric field | 896 | IP/LDP FRR | system ID and | in Extended IS | 897 | | pseudonode number | Reachability TLV #22 | 898 | | in Extended IS | or Multi-Topology | 899 | | Reachability TLV #22 | IS Neighbor TLV #222 | 900 | | or Multi-Topology | | 901 | | IS Neighbor TLV #222 | | 902 +--------------+-----------------------+-----------------------------+ 903 | ISIS-PCR for | 8 octet Bridge ID | 3 octet SPB-LINK-METRIC in | 904 | protection | created from 2 octet | SPB-Metric sub-TLV (type 29)| 905 | of traffic | Bridge Priority in | in Extended IS Reachability | 906 | in bridged | SPB Instance sub-TLV | TLV #22 or Multi-Topology | 907 | networks | (type 1) carried in | Intermediate Systems | 908 | | MT-Capability TLV | TLV #222. In the case | 909 | | #144 and 6 octet | of asymmetric link metrics, | 910 | | neighbor system ID in | the larger link metric | 911 | | Extended IS | is used for both link | 912 | | Reachability TLV #22 | directions. | 913 | | or Multi-Topology | (informational) | 914 | | Intermediate Systems | | 915 | | TLV #222 | | 916 | | (informational) | | 917 +--------------+-----------------------+-----------------------------+ 919 Figure 15: value of interface.neighbor.mrt_node_id and 920 interface.metric to be used for ranking interfaces, for different 921 flooding protocols and applications 923 The metrics are unsigned integers and MUST be compared as unsigned 924 integers. The results of mrt_node_id comparisons MUST be the same as 925 would be obtained by converting the mrt_node_ids to unsigned integers 926 using network byte order and performing the comparison as unsigned 927 integers. Also note that these values are only specified in the case 928 of point-to-point links. Therefore, in the case of IS-IS for IP/LDP 929 FRR, the pseudonode number (the 7th octet) will always be zero. 931 In the case of IS-IS for IP/LDP FRR, this specification allows for 932 the use of Multi-Topology routing. [RFC5120] requires that 933 information related to the standard/default topology (MT-ID = 0) be 934 carried in the Extended IS Reachability TLV #22, while it requires 935 that the Multi-Topology IS Neighbor TLV #222 only be used to carry 936 topology information related to non-default topologies (with non-zero 937 MT-IDs). [RFC5120] enforces this by requiring an implementation to 938 ignore TLV#222 with MT-ID = 0. The current document also requires 939 that TLV#222 with MT-ID = 0 MUST be ignored. 941 5.2. MRT Island Identification 943 The local MRT Island for a particular MRT profile can be determined 944 by starting from the computing router in the network graph and doing 945 a breadth-first-search (BFS). The BFS explores only links that are 946 in the same area/level, are not IGP-excluded, and are not MRT- 947 ineligible. The BFS explores only nodes that are are not IGP- 948 excluded, and that support the particular MRT profile. See section 7 949 of [I-D.ietf-rtgwg-mrt-frr-architecture] for more precise definitions 950 of these criteria. 952 MRT_Island_Identification(topology, computing_rtr, profile_id, area) 953 for all routers in topology 954 rtr.IN_MRT_ISLAND = FALSE 955 computing_rtr.IN_MRT_ISLAND = TRUE 956 explore_list = { computing_rtr } 957 while (explore_list is not empty) 958 next_rtr = remove_head(explore_list) 959 for each interface in next_rtr 960 if interface is (not MRT-ineligible and not IGP-excluded 961 and in area) 962 if ((interface.remote_node supports profile_id) and 963 (interface.remote_node.IN_MRT_ISLAND is FALSE)) 964 interface.remote_node.IN_MRT_ISLAND = TRUE 965 add_to_tail(explore_list, interface.remote_node) 967 Figure 16: MRT Island Identification 969 5.3. GADAG Root Selection 971 In Section 8.3 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG 972 Root Selection Policy is described for the MRT default profile. In 973 [I-D.ietf-ospf-mrt] and [I-D.ietf-isis-mrt], a mechanism is given for 974 routers to advertise the GADAG Root Selection Priority and 975 consistently select a GADAG Root inside the local MRT Island. The 976 MRT Lowpoint algorithm simply requires that all routers in the MRT 977 Island MUST select the same GADAG Root; the mechanism can vary based 978 upon the MRT profile description. Before beginning computation, the 979 network graph is reduced to contain only the set of routers that 980 support the specific MRT profile whose MRTs are being computed. 982 Analysis has shown that the centrality of a router can have a 983 significant impact on the lengths of the alternate paths computed. 984 Therefore, it is RECOMMENDED that off-line analysis that considers 985 the centrality of a router be used to help determine how good a 986 choice a particular router is for the role of GADAG root. 988 5.4. Initialization 990 Before running the algorithm, there is the standard type of 991 initialization to be done, such as clearing any computed DFS-values, 992 lowpoint-values, DFS-parents, lowpoint-parents, any MRT-computed 993 next-hops, and flags associated with algorithm. 995 It is assumed that a regular SPF computation has been run so that the 996 primary next-hops from the computing router to each destination are 997 known. This is required for determining alternates at the last step. 999 Initially, all interfaces MUST be initialized to UNDIRECTED. Whether 1000 they are OUTGOING, INCOMING or both is determined when the GADAG is 1001 constructed and augmented. 1003 It is possible that some links and nodes will be marked as unusable 1004 using standard IGP mechanisms (see section 7 of 1005 [I-D.ietf-rtgwg-mrt-frr-architecture]). Due to FRR manageability 1006 considerations [I-D.ietf-rtgwg-lfa-manageability], it may also be 1007 desirable to administratively configure some interfaces as ineligible 1008 to carry MRT FRR traffic. This constraint MUST be consistently 1009 flooded via the IGP [I-D.ietf-ospf-mrt] [I-D.ietf-isis-mrt] by the 1010 owner of the interface, so that links are clearly known to be MRT- 1011 ineligible and not explored or used in the MRT algorithm. In the 1012 algorithm description, it is assumed that such links and nodes will 1013 not be explored or used, and no more discussion is given of this 1014 restriction. 1016 5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance 1018 As discussed in Section 4.2, it is necessary to find ears from a node 1019 x that is already in the GADAG (known as IN_GADAG). Two different 1020 methods are used to find ears in the algorithm. The first is by 1021 going to a not IN_GADAG DFS-child and then following the chain of 1022 low-point parents until an IN_GADAG node is found. The second is by 1023 going to a not IN_GADAG neighbor and then following the chain of DFS 1024 parents until an IN_GADAG node is found. As an ear is found, the 1025 associated interfaces are marked based on the direction taken. The 1026 nodes in the ear are marked as IN_GADAG. In the algorithm, first the 1027 ears via DFS-children are found and then the ears via DFS-neighbors 1028 are found. 1030 By adding both types of ears when an IN_GADAG node is processed, all 1031 ears that connect to that node are found. The order in which the 1032 IN_GADAG nodes is processed is, of course, key to the algorithm. The 1033 order is a stack of ears so the most recent ear is found at the top 1034 of the stack. Of course, the stack stores nodes and not ears, so an 1035 ordered list of nodes, from the first node in the ear to the last 1036 node in the ear, is created as the ear is explored and then that list 1037 is pushed onto the stack. 1039 Each ear represents a partial order (see Figure 4) and processing the 1040 nodes in order along each ear ensures that all ears connecting to a 1041 node are found before a node higher in the partial order has its ears 1042 explored. This means that the direction of the links in the ear is 1043 always from the node x being processed towards the other end of the 1044 ear. Additionally, by using a stack of ears, this means that any 1045 unprocessed nodes in previous ears can only be ordered higher than 1046 nodes in the ears below it on the stack. 1048 In this algorithm that depends upon Low-Point inheritance, it is 1049 necessary that every node have a low-point parent that is not itself. 1050 If a node is a cut-vertex, that may not yet be the case. Therefore, 1051 any nodes without a low-point parent will have their low-point parent 1052 set to their DFS parent and their low-point value set to the DFS- 1053 value of their parent. This assignment also properly allows an ear 1054 between two cut-vertices. 1056 Finally, the algorithm simultaneously computes each node's local- 1057 root, as described in Figure 12. This is further elaborated as 1058 follows. The local-root can be inherited from the node at the end of 1059 the ear unless the end of the ear is x itself, in which case the 1060 local-root for all the nodes in the ear would be x. This is because 1061 whenever the first cycle is found in a block, or an ear involving a 1062 bridge is computed, the cut-vertex closest to the root would be x 1063 itself. In all other scenarios, the properties of lowpoint/dfs 1064 parents ensure that the end of the ear will be in the same block, and 1065 thus inheriting its local-root would be the correct local-root for 1066 all newly added nodes. 1068 The pseudo-code for the GADAG algorithm (assuming that the adjustment 1069 of lowpoint for cut-vertices has been made) is shown in Figure 17. 1071 Construct_Ear(x, Stack, intf, ear_type) 1072 ear_list = empty 1073 cur_node = intf.remote_node 1074 cur_intf = intf 1075 not_done = true 1077 while not_done 1078 cur_intf.UNDIRECTED = false 1079 cur_intf.OUTGOING = true 1080 cur_intf.remote_intf.UNDIRECTED = false 1081 cur_intf.remote_intf.INCOMING = true 1083 if cur_node.IN_GADAG is false 1084 cur_node.IN_GADAG = true 1085 add_to_list_end(ear_list, cur_node) 1086 if ear_type is CHILD 1087 cur_intf = cur_node.lowpoint_parent_intf 1088 cur_node = cur_node.lowpoint_parent 1089 else // ear_type must be NEIGHBOR 1090 cur_intf = cur_node.dfs_parent_intf 1091 cur_node = cur_node.dfs_parent 1092 else 1093 not_done = false 1095 if (ear_type is CHILD) and (cur_node is x) 1096 // x is a cut-vertex and the local root for 1097 // the block in which the ear is computed 1098 x.IS_CUT_VERTEX = true 1099 localroot = x 1100 else 1101 // Inherit local-root from the end of the ear 1102 localroot = cur_node.localroot 1103 while ear_list is not empty 1104 y = remove_end_item_from_list(ear_list) 1105 y.localroot = localroot 1106 push(Stack, y) 1108 Construct_GADAG_via_Lowpoint(topology, gadag_root) 1109 gadag_root.IN_GADAG = true 1110 gadag_root.localroot = None 1111 Initialize Stack to empty 1112 push gadag_root onto Stack 1113 while (Stack is not empty) 1114 x = pop(Stack) 1115 foreach ordered_interface intf of x 1116 if ((intf.remote_node.IN_GADAG == false) and 1117 (intf.remote_node.dfs_parent is x)) 1118 Construct_Ear(x, Stack, intf, CHILD) 1119 foreach ordered_interface intf of x 1120 if ((intf.remote_node.IN_GADAG == false) and 1121 (intf.remote_node.dfs_parent is not x)) 1122 Construct_Ear(x, Stack, intf, NEIGHBOR) 1124 Construct_GADAG_via_Lowpoint(topology, gadag_root) 1126 Figure 17: Low-point Inheritance GADAG algorithm 1128 5.6. Augmenting the GADAG by directing all links 1130 The GADAG, regardless of the algorithm used to construct it, at this 1131 point could be used to find MRTs, but the topology does not include 1132 all links in the network graph. That has two impacts. First, there 1133 might be shorter paths that respect the GADAG partial ordering and so 1134 the alternate paths would not be as short as possible. Second, there 1135 may be additional paths between a router x and the root that are not 1136 included in the GADAG. Including those provides potentially more 1137 bandwidth to traffic flowing on the alternates and may reduce 1138 congestion compared to just using the GADAG as currently constructed. 1140 The goal is thus to assign direction to every remaining link marked 1141 as UNDIRECTED to improve the paths and number of paths found when the 1142 MRTs are computed. 1144 To do this, we need to establish a total order that respects the 1145 partial order described by the GADAG. This can be done using Kahn's 1146 topological sort[Kahn_1962_topo_sort] which essentially assigns a 1147 number to a node x only after all nodes before it (e.g. with a link 1148 incoming to x) have had their numbers assigned. The only issue with 1149 the topological sort is that it works on DAGs and not ADAGs or 1150 GADAGs. 1152 To convert a GADAG to a DAG, it is necessary to remove all links that 1153 point to a root of block from within that block. That provides the 1154 necessary conversion to a DAG and then a topological sort can be 1155 done. When adding undirected links to the GADAG, links connecting 1156 the block root to other nodes in that block need special handling 1157 because the topological order will not always give the right answer 1158 for those links. There are three cases to consider. If the 1159 undirected link in question has another parallel link between the 1160 same two nodes that is already directed, then the direction of the 1161 undirected link can be inherited from the previously directed link. 1162 In the case of parallel cut links, we set all of the parallel links 1163 to both INCOMING and OUTGOING. Otherwise, the undirected link in 1164 question is set to OUTGOING from the block root node. A cut-link can 1165 then be identified by the fact that it will be directed both INCOMING 1166 and OUTGOING in the GADAG. The exact details of this whole process 1167 are captured in Figure 18 1169 Add_Undirected_Block_Root_Links(topo, gadag_root): 1170 foreach node x in topo 1171 if x.IS_CUT_VERTEX or x is gadag_root 1172 foreach interface i of x 1173 if (i.remote_node.localroot is not x 1174 or i.PROCESSED ) 1175 continue 1176 Initialize bundle_list to empty 1177 bundle.UNDIRECTED = true 1178 bundle.OUTGOING = false 1179 bundle.INCOMING = false 1180 foreach interface i2 in x 1181 if i2.remote_node is i.remote_node 1182 add_to_list_end(bundle_list, i2) 1183 if not i2.UNDIRECTED: 1184 bundle.UNDIRECTED = false 1185 if i2.INCOMING: 1186 bundle.INCOMING = true 1187 if i2.OUTGOING: 1188 bundle.OUTGOING = true 1189 if bundle.UNDIRECTED 1190 foreach interface i3 in bundle_list 1191 i3.UNDIRECTED = false 1192 i3.remote_intf.UNDIRECTED = false 1193 i3.PROCESSED = true 1194 i3.remote_intf.PROCESSED = true 1195 i3.OUTGOING = true 1196 i3.remote_intf.INCOMING = true 1197 else 1198 if (bundle.OUTGOING and bundle.INCOMING) 1199 foreach interface i3 in bundle_list 1200 i3.UNDIRECTED = false 1201 i3.remote_intf.UNDIRECTED = false 1202 i3.PROCESSED = true 1203 i3.remote_intf.PROCESSED = true 1204 i3.OUTGOING = true 1205 i3.INCOMING = true 1206 i3.remote_intf.INCOMING = true 1207 i3.remote_intf.OUTGOING = true 1209 else if bundle.OUTGOING 1210 foreach interface i3 in bundle_list 1211 i3.UNDIRECTED = false 1212 i3.remote_intf.UNDIRECTED = false 1213 i3.PROCESSED = true 1214 i3.remote_intf.PROCESSED = true 1215 i3.OUTGOING = true 1216 i3.remote_intf.INCOMING = true 1217 else if bundle.INCOMING 1218 foreach interface i3 in bundle_list 1219 i3.UNDIRECTED = false 1220 i3.remote_intf.UNDIRECTED = false 1221 i3.PROCESSED = true 1222 i3.remote_intf.PROCESSED = true 1223 i3.INCOMING = true 1224 i3.remote_intf.OUTGOING = true 1226 Modify_Block_Root_Incoming_Links(topo, gadag_root): 1227 foreach node x in topo 1228 if x.IS_CUT_VERTEX or x is gadag_root 1229 foreach interface i of x 1230 if i.remote_node.localroot is x 1231 if i.INCOMING: 1232 i.INCOMING = false 1233 i.INCOMING_STORED = true 1234 i.remote_intf.OUTGOING = false 1235 i.remote_intf.OUTGOING_STORED = true 1237 Revert_Block_Root_Incoming_Links(topo, gadag_root): 1238 foreach node x in topo 1239 if x.IS_CUT_VERTEX or x is gadag_root 1240 foreach interface i of x 1241 if i.remote_node.localroot is x 1242 if i.INCOMING_STORED: 1243 i.INCOMING = true 1244 i.remote_intf.OUTGOING = true 1245 i.INCOMING_STORED = false 1246 i.remote_intf.OUTGOING_STORED = false 1248 Run_Topological_Sort_GADAG(topo, gadag_root): 1249 Modify_Block_Root_Incoming_Links(topo, gadag_root) 1250 foreach node x in topo: 1251 node.unvisited = 0 1252 foreach interface i of x: 1253 if (i.INCOMING): 1254 node.unvisited += 1 1255 Initialize working_list to empty 1256 Initialize topo_order_list to empty 1257 add_to_list_end(working_list, gadag_root) 1258 while working_list is not empty 1259 y = remove_start_item_from_list(working_list) 1260 add_to_list_end(topo_order_list, y) 1261 foreach ordered_interface i of y 1262 if intf.OUTGOING 1263 i.remote_node.unvisited -= 1 1264 if i.remote_node.unvisited is 0 1265 add_to_list_end(working_list, i.remote_node) 1266 next_topo_order = 1 1267 while topo_order_list is not empty 1268 y = remove_start_item_from_list(topo_order_list) 1269 y.topo_order = next_topo_order 1270 next_topo_order += 1 1271 Revert_Block_Root_Incoming_Links(topo, gadag_root) 1273 def Set_Other_Undirected_Links_Based_On_Topo_Order(topo): 1274 foreach node x in topo 1275 foreach interface i of x 1276 if i.UNDIRECTED: 1277 if x.topo_order < i.remote_node.topo_order 1278 i.OUTGOING = true 1279 i.UNDIRECTED = false 1280 i.remote_intf.INCOMING = true 1281 i.remote_intf.UNDIRECTED = false 1282 else 1283 i.INCOMING = true 1284 i.UNDIRECTED = false 1285 i.remote_intf.OUTGOING = true 1286 i.remote_intf.UNDIRECTED = false 1288 Add_Undirected_Links(topo, gadag_root) 1289 Add_Undirected_Block_Root_Links(topo, gadag_root) 1290 Run_Topological_Sort_GADAG(topo, gadag_root) 1291 Set_Other_Undirected_Links_Based_On_Topo_Order(topo) 1293 Add_Undirected_Links(topo, gadag_root) 1295 Figure 18: Assigning direction to UNDIRECTED links 1297 Proxy-nodes do not need to be added to the network graph. They 1298 cannot be transited and do not affect the MRTs that are computed. 1299 The details of how the MRT-Blue and MRT-Red next-hops are computed 1300 for proxy-nodes and how the appropriate alternate next-hops are 1301 selected is given in Section 5.9. 1303 5.7. Compute MRT next-hops 1305 As was discussed in Section 4.1, once a ADAG is found, it is 1306 straightforward to find the next-hops from any node X to the ADAG 1307 root. However, in this algorithm, we will reuse the common GADAG and 1308 find not only the one pair of MRTs rooted at the GADAG root with it, 1309 but find a pair rooted at each node. This is useful since it is 1310 significantly faster to compute. 1312 The method for computing differently rooted MRTs from the common 1313 GADAG is based on two ideas. First, if two nodes X and Y are ordered 1314 with respect to each other in the partial order, then an SPF along 1315 OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a 1316 decreasing-SPF) can be used to find the increasing and decreasing 1317 paths. Second, if two nodes X and Y aren't ordered with respect to 1318 each other in the partial order, then intermediary nodes can be used 1319 to create the paths by increasing/decreasing to the intermediary and 1320 then decreasing/increasing to reach Y. 1322 As usual, the two basic ideas will be discussed assuming the network 1323 is two-connected. The generalization to multiple blocks is discussed 1324 in Section 5.7.4. The full algorithm is given in Section 5.7.5. 1326 5.7.1. MRT next-hops to all nodes partially ordered with respect to the 1327 computing node 1329 To find two node-disjoint paths from the computing router X to any 1330 node Y, depends upon whether Y >> X or Y << X. As shown in 1331 Figure 19, if Y >> X, then there is an increasing path that goes from 1332 X to Y without crossing R; this contains nodes in the interval [X,Y]. 1333 There is also a decreasing path that decreases towards R and then 1334 decreases from R to Y; this contains nodes in the interval 1335 [X,R-small] or [R-great,Y]. The two paths cannot have common nodes 1336 other than X and Y. 1338 [Y]<---(Cloud 2)<--- [X] 1339 | ^ 1340 | | 1341 V | 1342 (Cloud 3)--->[R]--->(Cloud 1) 1344 MRT-Blue path: X->Cloud 2->Y 1345 MRT-Red path: X->Cloud 1->R->Cloud 3->Y 1347 Figure 19: Y >> X 1349 Similar logic applies if Y << X, as shown in Figure 20. In this 1350 case, the increasing path from X increases to R and then increases 1351 from R to Y to use nodes in the intervals [X,R-great] and [R-small, 1352 Y]. The decreasing path from X reaches Y without crossing R and uses 1353 nodes in the interval [Y,X]. 1355 [X]<---(Cloud 2)<--- [Y] 1356 | ^ 1357 | | 1358 V | 1359 (Cloud 3)--->[R]--->(Cloud 1) 1361 MRT-Blue path: X->Cloud 3->R->Cloud 1->Y 1362 MRT-Red path: X->Cloud 2->Y 1364 Figure 20: Y << X 1366 5.7.2. MRT next-hops to all nodes not partially ordered with respect to 1367 the computing node 1369 When X and Y are not ordered, the first path should increase until we 1370 get to a node G, where G >> Y. At G, we need to decrease to Y. The 1371 other path should be just the opposite: we must decrease until we get 1372 to a node H, where H << Y, and then increase. Since R is smaller and 1373 greater than Y, such G and H must exist. It is also easy to see that 1374 these two paths must be node disjoint: the first path contains nodes 1375 in interval [X,G] and [Y,G], while the second path contains nodes in 1376 interval [H,X] and [H,Y]. This is illustrated in Figure 21. It is 1377 necessary to decrease and then increase for the MRT-Blue and increase 1378 and then decrease for the MRT-Red; if one simply increased for one 1379 and decreased for the other, then both paths would go through the 1380 root R. 1382 (Cloud 6)<---[Y]<---(Cloud 5)<------------| 1383 | | 1384 | | 1385 V | 1386 [G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H] 1387 ^ | 1388 | | 1389 | | 1390 (Cloud 3)<---[X]<---(Cloud 2)<-----------| 1392 MRT-Blue path: decrease to H and increase to Y 1393 X->Cloud 2->H->Cloud 5->Y 1394 MRT-Red path: increase to G and decrease to Y 1395 X->Cloud 3->G->Cloud 6->Y 1397 Figure 21: X and Y unordered 1399 This gives disjoint paths as long as G and H are not the same node. 1400 Since G >> Y and H << Y, if G and H could be the same node, that 1401 would have to be the root R. This is not possible because there is 1402 only one incoming interface to the root R which is created when the 1403 initial cycle is found. Recall from Figure 6 that whenever an ear 1404 was found to have an end that was the root R, the ear was directed 1405 from R so that the associated interface on R is outgoing and not 1406 incoming. Therefore, there must be exactly one node M which is the 1407 largest one before R, so the MRT-Red path will never reach R; it will 1408 turn at M and decrease to Y. 1410 5.7.3. Computing Redundant Tree next-hops in a 2-connected Graph 1412 The basic ideas for computing RT next-hops in a 2-connected graph 1413 were given in Section 5.7.1 and Section 5.7.2. Given these two 1414 ideas, how can we find the trees? 1416 If some node X only wants to find the next-hops (which is usually the 1417 case for IP networks), it is enough to find which nodes are greater 1418 and less than X, and which are not ordered; this can be done by 1419 running an increasing-SPF and a decreasing-SPF rooted at X and not 1420 exploring any links from the ADAG root. 1422 In principle, an traversal method other than SPF could be used to 1423 traverse the GADAG in the process of determining blue and red next- 1424 hops that result in maximally redundant trees. This will be the case 1425 as long as one traversal uses the links in the direction specified by 1426 the GADAG and the other traversal uses the links in the direction 1427 opposite of that specified by the GADAG. However, a different 1428 traversal algorithm will generally result in different blue and red 1429 next-hops. Therefore, the algorithm specified here requires the use 1430 of SPF to traverse the GADAG to generate MRT blue and red next-hops, 1431 as described below. 1433 An increasing-SPF rooted at X and not exploring links from the root 1434 will find the increasing next-hops to all Y >> X. Those increasing 1435 next-hops are X's next-hops on the MRT-Blue to reach Y. A 1436 decreasing-SPF rooted at X and not exploring links from the root will 1437 find the decreasing next-hops to all Z << X. Those decreasing next- 1438 hops are X's next-hops on the MRT-Red to reach Z. Since the root R 1439 is both greater than and less than X, after this increasing-SPF and 1440 decreasing-SPF, X's next-hops on the MRT-Blue and on the MRT-Red to 1441 reach R are known. For every node Y >> X, X's next-hops on the MRT- 1442 Red to reach Y are set to those on the MRT-Red to reach R. For every 1443 node Z << X, X's next-hops on the MRT-Blue to reach Z are set to 1444 those on the MRT-Blue to reach R. 1446 For those nodes which were not reached by either the increasing-SPF 1447 or the decreasing-SPF, we can determine the next-hops as well. The 1448 increasing MRT-Blue next-hop for a node which is not ordered with 1449 respect to X is the next-hop along the decreasing MRT-Red towards R, 1450 and the decreasing MRT-Red next-hop is the next-hop along the 1451 increasing MRT-Blue towards R. Naturally, since R is ordered with 1452 respect to all the nodes, there will always be an increasing and a 1453 decreasing path towards it. This algorithm does not provide the 1454 complete specific path taken but just the appropriate next-hops to 1455 use. The identities of G and H are not determined by the computing 1456 node X. 1458 The final case to considered is when the root R computes its own 1459 next-hops. Since the root R is << all other nodes, running an 1460 increasing-SPF rooted at R will reach all other nodes; the MRT-Blue 1461 next-hops are those found with this increasing-SPF. Similarly, since 1462 the root R is >> all other nodes, running a decreasing-SPF rooted at 1463 R will reach all other nodes; the MRT-Red next-hops are those found 1464 with this decreasing-SPF. 1466 E---D---| E<--D<--| 1467 | | | | ^ | 1468 | | | V | | 1469 R F C R F C 1470 | | | | ^ ^ 1471 | | | V | | 1472 A---B---| A-->B---| 1474 (a) (b) 1475 A 2-connected graph A spanning ADAG rooted at R 1477 Figure 22 1479 As an example consider the situation depicted in Figure 22. Node C 1480 runs an increasing-SPF and a decreasing-SPF on the ADAG. The 1481 increasing-SPF reaches D, E and R and the decreasing-SPF reaches B, A 1482 and R. E>>C. So towards E the MRT-Blue next-hop is D, since E was 1483 reached on the increasing path through D. And the MRT-Red next-hop 1484 towards E is B, since R was reached on the decreasing path through B. 1485 Since E>>D, D will similarly compute its MRT-Blue next-hop to be E, 1486 ensuring that a packet on MRT-Blue will use path C-D-E. B, A and R 1487 will similarly compute the MRT-Red next-hops towards E (which is 1488 ordered less than B, A and R), ensuring that a packet on MRT-Red will 1489 use path C-B-A-R-E. 1491 C can determine the next-hops towards F as well. Since F is not 1492 ordered with respect to C, the MRT-Blue next-hop is the decreasing 1493 one towards R (which is B) and the MRT-Red next-hop is the increasing 1494 one towards R (which is D). Since F>>B, for its MRT-Blue next-hop 1495 towards F, B will use the real increasing next-hop towards F. So a 1496 packet forwarded to B on MRT-Blue will get to F on path C-B-F. 1497 Similarly, D will use the real decreasing next-hop towards F as its 1498 MRT-Red next-hop, a packet on MRT-Red will use path C-D-F. 1500 5.7.4. Generalizing for a graph that isn't 2-connected 1502 If a graph isn't 2-connected, then the basic approach given in 1503 Section 5.7.3 needs some extensions to determine the appropriate MRT 1504 next-hops to use for destinations outside the computing router X's 1505 blocks. In order to find a pair of maximally redundant trees in that 1506 graph we need to find a pair of RTs in each of the blocks (the root 1507 of these trees will be discussed later), and combine them. 1509 When computing the MRT next-hops from a router X, there are three 1510 basic differences: 1512 1. Only nodes in a common block with X should be explored in the 1513 increasing-SPF and decreasing-SPF. 1515 2. Instead of using the GADAG root, X's local-root should be used. 1516 This has the following implications: 1518 A. The links from X's local-root should not be explored. 1520 B. If a node is explored in the outgoing SPF so Y >> X, then X's 1521 MRT-Red next-hops to reach Y uses X's MRT-Red next-hops to 1522 reach X's local-root and if Z << X, then X's MRT-Blue next- 1523 hops to reach Z uses X's MRT-Blue next-hops to reach X's 1524 local-root. 1526 C. If a node W in a common block with X was not reached in the 1527 increasing-SPF or decreasing-SPF, then W is unordered with 1528 respect to X. X's MRT-Blue next-hops to W are X's decreasing 1529 (aka MRT-Red) next-hops to X's local-root. X's MRT-Red next- 1530 hops to W are X's increasing (aka MRT-Blue) next-hops to X's 1531 local-root. 1533 3. For nodes in different blocks, the next-hops must be inherited 1534 via the relevant cut-vertex. 1536 These are all captured in the detailed algorithm given in 1537 Section 5.7.5. 1539 5.7.5. Complete Algorithm to Compute MRT Next-Hops 1541 The complete algorithm to compute MRT Next-Hops for a particular 1542 router X is given in Figure 23. In addition to computing the MRT- 1543 Blue next-hops and MRT-Red next-hops used by X to reach each node Y, 1544 the algorithm also stores an "order_proxy", which is the proper cut- 1545 vertex to reach Y if it is outside the block, and which is used later 1546 in deciding whether the MRT-Blue or the MRT-Red can provide an 1547 acceptable alternate for a particular primary next-hop. 1549 In_Common_Block(x, y) 1550 if ( (x.block_id is y.block_id) 1551 or (x is y.localroot) or (y is x.localroot) ) 1552 return true 1553 return false 1555 Store_Results(y, direction) 1556 if direction is FORWARD 1557 y.higher = true 1558 y.blue_next_hops = y.next_hops 1559 if direction is REVERSE 1560 y.lower = true 1561 y.red_next_hops = y.next_hops 1563 SPF_No_Traverse_Block_Root(spf_root, block_root, direction) 1564 Initialize spf_heap to empty 1565 Initialize nodes' spf_metric to infinity and next_hops to empty 1566 spf_root.spf_metric = 0 1567 insert(spf_heap, spf_root) 1568 while (spf_heap is not empty) 1569 min_node = remove_lowest(spf_heap) 1570 Store_Results(min_node, direction) 1571 if ((min_node is spf_root) or (min_node is not block_root)) 1572 foreach interface intf of min_node 1573 if ( ( ((direction is FORWARD) and intf.OUTGOING) or 1574 ((direction is REVERSE) and intf.INCOMING) ) 1575 and In_Common_Block(spf_root, intf.remote_node) ) 1576 path_metric = min_node.spf_metric + intf.metric 1577 if path_metric < intf.remote_node.spf_metric 1578 intf.remote_node.spf_metric = path_metric 1579 if min_node is spf_root 1580 intf.remote_node.next_hops = make_list(intf) 1581 else 1582 intf.remote_node.next_hops = min_node.next_hops 1583 insert_or_update(spf_heap, intf.remote_node) 1584 else if path_metric is intf.remote_node.spf_metric 1585 if min_node is spf_root 1586 add_to_list(intf.remote_node.next_hops, intf) 1587 else 1588 add_list_to_list(intf.remote_node.next_hops, 1589 min_node.next_hops) 1591 SetEdge(y) 1592 if y.blue_next_hops is empty and y.red_next_hops is empty 1593 SetEdge(y.localroot) 1594 y.blue_next_hops = y.localroot.blue_next_hops 1595 y.red_next_hops = y.localroot.red_next_hops 1596 y.order_proxy = y.localroot.order_proxy 1598 Compute_MRT_NextHops(x, gadag_root) 1599 foreach node y 1600 y.higher = y.lower = false 1601 clear y.red_next_hops and y.blue_next_hops 1602 y.order_proxy = y 1603 SPF_No_Traverse_Block_Root(x, x.localroot, FORWARD) 1604 SPF_No_Traverse_Block_Root(x, x.localroot, REVERSE) 1606 // red and blue next-hops are stored to x.localroot as different 1607 // paths are found via the SPF and reverse-SPF. 1608 // Similarly any nodes whose local-root is x will have their 1609 // red_next_hops and blue_next_hops already set. 1611 // Handle nodes in the same block that aren't the local-root 1612 foreach node y 1613 if (y.IN_MRT_ISLAND and (y is not x) and 1614 (y.block_id is x.block_id) ) 1615 if y.higher 1616 y.red_next_hops = x.localroot.red_next_hops 1617 else if y.lower 1618 y.blue_next_hops = x.localroot.blue_next_hops 1619 else 1620 y.blue_next_hops = x.localroot.red_next_hops 1621 y.red_next_hops = x.localroot.blue_next_hops 1623 // Inherit next-hops and order_proxies to other components 1624 if x is not gadag_root 1625 gadag_root.blue_next_hops = x.localroot.blue_next_hops 1626 gadag_root.red_next_hops = x.localroot.red_next_hops 1627 gadag_root.order_proxy = x.localroot 1628 foreach node y 1629 if (y is not gadag_root) and (y is not x) and y.IN_MRT_ISLAND 1630 SetEdge(y) 1632 max_block_id = 0 1633 Assign_Block_ID(gadag_root, max_block_id) 1634 Compute_MRT_NextHops(x, gadag_root) 1636 Figure 23 1638 5.8. Identify MRT alternates 1640 At this point, a computing router S knows its MRT-Blue next-hops and 1641 MRT-Red next-hops for each destination in the MRT Island. The 1642 primary next-hops along the SPT are also known. It remains to 1643 determine for each primary next-hop to a destination D, which of the 1644 MRTs avoids the primary next-hop node F. This computation depends 1645 upon data set in Compute_MRT_NextHops such as each node y's 1646 y.blue_next_hops, y.red_next_hops, y.order_proxy, y.higher, y.lower 1647 and topo_orders. Recall that any router knows only which are the 1648 nodes greater and lesser than itself, but it cannot decide the 1649 relation between any two given nodes easily; that is why we need 1650 topological ordering. 1652 For each primary next-hop node F to each destination D, S can call 1653 Select_Alternates(S, D, F, primary_intf) to determine whether to use 1654 the MRT-Blue or MRT-Red next-hops as the alternate next-hop(s) for 1655 that primary next hop. The algorithm is given in Figure 24 and 1656 discussed afterwards. 1658 Select_Alternates_Internal(D, F, primary_intf, 1659 D_lower, D_higher, D_topo_order): 1660 if D_higher and D_lower 1661 if F.HIGHER and F.LOWER 1662 if F.topo_order < D_topo_order 1663 return USE_RED 1664 else 1665 return USE_BLUE 1666 if F.HIGHER 1667 return USE_RED 1668 if F.LOWER 1669 return USE_BLUE 1670 else if D_higher 1671 if F.HIGHER and F.LOWER 1672 return USE_BLUE 1673 if F.LOWER 1674 return USE_BLUE 1675 if F.HIGHER 1676 if (F.topo_order > D_topo_order) 1677 return USE_BLUE 1678 if (F.topo_order < D_topo_order) 1679 return USE_RED 1680 else if D_lower 1681 if F.HIGHER and F.LOWER 1682 return USE_RED 1683 if F.HIGHER 1684 return USE_RED 1685 if F.LOWER 1686 if F.topo_order > D_topo_order 1687 return USE_BLUE 1688 if F.topo_order < D_topo_order 1689 return USE_RED 1690 else //D is unordered wrt S 1691 if F.HIGHER and F.LOWER 1692 if primary_intf.OUTGOING and primary_intf.INCOMING 1693 // this case should not occur 1694 if primary_intf.OUTGOING 1695 return USE_BLUE 1696 if primary_intf.INCOMING 1697 return USE_RED 1698 if F.LOWER 1699 return USE_RED 1700 if F.HIGHER 1701 return USE_BLUE 1703 Select_Alternates(D, F, primary_intf) 1704 if (D is F) or (D.order_proxy is F) 1705 return PRIM_NH_IS_D_OR_OP_FOR_D 1706 D_lower = D.order_proxy.LOWER 1707 D_higher = D.order_proxy.HIGHER 1708 D_topo_order = D.order_proxy.topo_order 1709 return Select_Alternates_Internal(D, F, primary_intf, 1710 D_lower, D_higher, D_topo_order) 1712 Figure 24 1714 It is useful to first handle the case where where F is also D, or F 1715 is the order proxy for D. In this case, only link protection is 1716 possible. The MRT that doesn't use the failed primary next-hop is 1717 used. If both MRTs use the primary next-hop, then the primary next- 1718 hop must be a cut-link, so either MRT could be used but the set of 1719 MRT next-hops must be pruned to avoid the failed primary next-hop 1720 interface. To indicate this case, Select_Alternates returns 1721 PRIM_NH_IS_D_OR_OP_FOR_D. Explicit pseudocode to handle the three 1722 sub-cases above is not provided. 1724 The logic behind Select_Alternates_Internal is described in 1725 Figure 25. As an example, consider the first case described in the 1726 table, where the D>>S and D<>S and F<D.topo_order, then either F is ordered lower 1739 than D, or F is unordered with respect to D. Therefore, F is either 1740 on an increasing path from S to D, or it is on neither an increasing 1741 nor a decreasing path from S to D. In either case, it is safe to 1742 take a decreasing path from S to D to avoid F. We know that when S 1743 is R, the decreasing path is the red path, so it is safe to use the 1744 red path to avoid F. 1746 If F>>S or F<>S, we deduce that 1749 F is on an increasing path from S to R. So in order to avoid F, we 1750 use a decreasing path from S to R, which is the red path. Instead, 1751 when F<>S | Blue path: | F>>S | additional | F on an | Use Red | 1765 | and | Increasing | only | criteria | increasing | to avoid | 1766 | D<>S | topo(F)>topo(D) | F on a | Use Blue | 1775 | S is | Blue path: | and | implies that | decreasing | to avoid | 1776 | R | Increasing | F<>D or F??D | path from | F | 1777 | | path to D. | | | S to D or | | 1778 | | Red path: | | | neither | | 1779 | | Decreasing | +-----------------+------------+------------+ 1780 | | path to D. | | topo(F)>S | Blue path: | F<>S | topo(F)>topo(D) | F on | Use Blue | 1792 | | Decreasing | only | implies that | decreasing | to avoid | 1793 | | shortest | | F>>D or F??D | path from | F | 1794 | | path from | | | R to D | | 1795 | | S to R, | | | or | | 1796 | | then | | | neither | | 1797 | | decreasing | +-----------------+------------+------------+ 1798 | | shortest | | topo(F)>S | additional | F on Red | Use Blue | 1806 | | | and | criteria | | to avoid | 1807 | | | F<>S | additional | F on | Use Red | 1812 | only | Increasing | only | criteria | increasing | to avoid | 1813 | | shortest | | not needed | path from | F | 1814 | | path from | | | S to R | | 1815 | | S to R, +------+-----------------+------------+------------+ 1816 | | then | F<topo(D) | F on | Use Blue | 1817 | | increasing | only | implies that | decreasing | to avoid | 1818 | | shortest | | F>>D or F??D | path from | F | 1819 | | path from | | | R to D | | 1820 | | R to D. | | | or | | 1821 | | Red path: | | | neither | | 1822 | | Decreasing | +-----------------+------------+------------+ 1823 | | shortest | | topo(F)>S | additional | F on Blue | Use Red | 1831 | | | and | criteria | | to avoid | 1832 | | | F<>D, | | | S to H. | | 1840 | | then incr. +------+-----------------+------------+------------+ 1841 | | to D. | F>>S | additional | F on an | Use Blue | 1842 | | Red path: | only | criteria | increasing | to avoid | 1843 | | Incr. from | | not needed | path from | F | 1844 | | S to first | | | S to G | | 1845 | | node G<>S | GADAG link | F on an | Use Blue | 1849 | | | and | direction | incr. path | to avoid | 1850 | | | F<F | from S | F | 1851 | | | F is +-----------------+------------+------------+ 1852 | | | R | GADAG link | F on a | Use Red | 1853 | | | | direction | decr. path | to avoid | 1854 | | | | S<-F | from S | F | 1855 | | | +-----------------+------------+------------+ 1856 | | | | GADAG link | Implies F is the order | 1857 | | | | direction | proxy for D, which has | 1858 | | | | S<-->F | already been handled. | 1859 +------+------------+------+-----------------+------------+------------+ 1861 Figure 25: determining MRT next-hops and alternates based on the 1862 partial order and topological sort relationships between the 1864 source(S), destination(D), primary next-hop(F), and block root(R). 1865 topo(N) indicates the topological sort value of node N. X??Y 1866 indicates that node X is unordered with respect to node Y. It is 1867 assumed that the case where F is D, or where F is the order proxy for 1868 D, has already been handled. 1870 As an example, consider the ADAG depicted in Figure 26 and first 1871 suppose that G is the source, D is the destination and H is the 1872 failed next-hop. Since D>>G, we need to compare H.topo_order and 1873 D.topo_order. Since D.topo_order>H.topo_order, D must be not smaller 1874 than H, so we should select the decreasing path towards the root. 1875 If, however, the destination were instead J, we must find that 1876 H.topo_order>J.topo_order, so we must choose the increasing Blue 1877 next-hop to J, which is I. In the case, when instead the destination 1878 is C, we find that we need to first decrease to avoid using H, so the 1879 Blue, first decreasing then increasing, path is selected. 1881 [E]<-[D]<-[H]<-[J] 1882 | ^ ^ ^ 1883 V | | | 1884 [R] [C] [G]->[I] 1885 | ^ ^ ^ 1886 V | | | 1887 [A]->[B]->[F]---| 1889 (a)ADAG rooted at R for 1890 a 2-connected graph 1892 Figure 26 1894 5.9. Finding FRR Next-Hops for Proxy-Nodes 1896 As discussed in Section 10.2 of 1897 [I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT- 1898 Blue and MRT-Red next-hops and MRT-FRR alternates for a named proxy- 1899 nodes. An example case is for a router that is not part of that 1900 local MRT Island, when there is only partial MRT support in the 1901 domain. 1903 A first incorrect and naive approach to handling proxy-nodes, which 1904 cannot be transited, is to simply add these proxy-nodes to the graph 1905 of the network and connect it to the routers through which the new 1906 proxy-node can be reached. Unfortunately, this can introduce some 1907 new ordering between the border routers connected to the new node 1908 which could result in routing MRT paths through the proxy-node. 1909 Thus, this naive approach would need to recompute GADAGs and redo 1910 SPTs for each proxy-node. 1912 Instead of adding the proxy-node to the original network graph, each 1913 individual proxy-node can be individually added to the GADAG. The 1914 proxy-node is connected to at most two nodes in the GADAG. 1915 Section 10.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] defines how the 1916 proxy-node attachments MUST be determined. The degenerate case where 1917 the proxy-node is attached to only one node in the GADAG is trivial 1918 as all needed information can be derived from that attachment node; 1919 if there are different interfaces, then some can be assigned to MRT- 1920 Red and others to MRT_Blue. 1922 Now, consider the proxy-node that is attached to exactly two nodes in 1923 the GADAG. Let the order_proxies of these nodes be A and B. Let the 1924 current node, where next-hop is just being calculated, be S. If one 1925 of these two nodes A and B is the local root of S, let A=S.local_root 1926 and the other one be B. Otherwise, let A.topo_order < B.topo_order. 1928 A valid GADAG was constructed. Instead doing an increasing-SPF and a 1929 decreasing-SPF to find ordering for the proxy-nodes, the following 1930 simple rules, providing the same result, can be used independently 1931 for each different proxy-node. For the following rules, let 1932 X=A.local_root, and if A is the local root, let that be strictly 1933 lower than any other node. Always take the first rule that matches. 1935 Rule Condition Blue NH Red NH Notes 1936 1 S=X Blue to A Red to B 1937 2 S<>B Blue to R Red to B 1939 4 A<> X, 2022 the computing router, MUST be one or more nodes, T, whose topo_order 2023 is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y 2024 is T. Similarly, the MRT-Red next-hops MUST be have a topo_order in 2025 the interval [R-small.topo_order, X.topo_order] or [Y.topo_order, 2026 R-big.topo_order]. 2028 Implementations SHOULD implement the Select_Alternates() function to 2029 pick an MRT-FRR alternate. 2031 7. Python Implementation of MRT Lowpoint Algorithm 2033 Below is Python code implementing the MRT Lowpoint algorithm 2034 specified in this document. In order to avoid the page breaks in the 2035 .txt version of the draft, one can cut and paste the Python code from 2036 the .xml version. The code is also posted on Github. 2038 2039 # This program has been tested to run on Python 2.6 and 2.7 2040 # (specifically Python 2.6.6 and 2.7.8 were tested). 2042 # The program has known incompatibilities with Python 3.X. 2044 # When executed, this program will generate a text file describing 2045 # an example topology. It then reads that text file back in as input 2046 # to create the example topology, and runs the MRT algorithm.This 2047 # was done to simplify the inclusion of the program as a single text 2048 # file that can be extracted from the IETF draft. 2050 # The output of the program is four text files containing a description 2051 # of the GADAG, the blue and red MRTs for all destinations, and the 2052 # MRT alternates for all failures. 2054 import heapq 2056 # simple Class definitions allow structure-like dot notation for 2057 # variables and a convenient place to initialize those variables. 2058 class Topology: 2059 pass 2061 class Node: 2062 pass 2064 class Interface: 2065 pass 2067 class Bundle: 2068 pass 2070 class Alternate: 2071 def __init__(self): 2072 self.failed_intf = None 2073 self.nh_list = [] 2074 self.fec = 'NO_ALTERNATE' 2075 self.prot = 'NO_PROTECTION' 2076 self.info = 'NONE' 2078 def Interface_Compare(intf_a, intf_b): 2079 if intf_a.metric < intf_b.metric: 2080 return -1 2081 if intf_b.metric < intf_a.metric: 2082 return 1 2083 if intf_a.remote_node.node_id < intf_b.remote_node.node_id: 2084 return -1 2085 if intf_b.remote_node.node_id < intf_a.remote_node.node_id: 2086 return 1 2087 return 0 2089 def Sort_Interfaces(topo): 2090 for node in topo.island_node_list: 2091 node.island_intf_list.sort(Interface_Compare) 2093 def Initialize_Node(node): 2094 node.intf_list = [] 2095 node.island_intf_list = [] 2096 node.profile_id_list = [0] 2097 node.GR_sel_priority = 128 2098 node.IN_MRT_ISLAND = False 2099 node.IN_GADAG = False 2100 node.dfs_number = None 2101 node.dfs_parent = None 2102 node.dfs_parent_intf = None 2103 node.dfs_child_list = [] 2104 node.lowpoint_number = None 2105 node.lowpoint_parent = None 2106 node.lowpoint_parent_intf = None 2107 node.localroot = None 2108 node.block_id = None 2109 node.IS_CUT_VERTEX = False 2110 node.blue_next_hops_dict = {} 2111 node.red_next_hops_dict = {} 2112 node.pnh_dict = {} 2113 node.alt_dict = {} 2115 def Initialize_Intf(intf): 2116 intf.metric = None 2117 intf.area = None 2118 intf.MRT_INELIGIBLE = False 2119 intf.IGP_EXCLUDED = False 2120 intf.UNDIRECTED = True 2121 intf.INCOMING = False 2122 intf.OUTGOING = False 2123 intf.INCOMING_STORED = False 2124 intf.OUTGOING_STORED = False 2125 intf.PROCESSED = False 2126 intf.IN_MRT_ISLAND = False 2128 def Reset_Computed_Node_and_Intf_Values(topo): 2129 for node in topo.node_list: 2130 node.IN_MRT_ISLAND = False 2131 node.IN_GADAG = False 2132 node.dfs_number = None 2133 node.dfs_parent = None 2134 node.dfs_parent_intf = None 2135 node.dfs_child_list = [] 2136 node.lowpoint_number = None 2137 node.lowpoint_parent = None 2138 node.lowpoint_parent_intf = None 2139 node.localroot = None 2140 node.block_id = None 2141 node.IS_CUT_VERTEX = False 2142 for intf in node.intf_list: 2143 intf.UNDIRECTED = True 2144 intf.INCOMING = False 2145 intf.OUTGOING = False 2146 intf.INCOMING_STORED = False 2147 intf.OUTGOING_STORED = False 2148 intf.IN_MRT_ISLAND = False 2150 # This function takes a file with links represented by 2-digit 2151 # numbers in the format: 2152 # 01,05,10 2153 # 05,02,30 2154 # 02,01,15 2155 # which represents a triangle topology with nodes 01, 05, and 02 2156 # and symmetric metrics of 10, 30, and 15. 2158 # Inclusion of a fourth column makes the metrics for the link 2159 # asymmetric. An entry of: 2160 # 02,07,10,15 2161 # creates a link from node 02 to 07 with metrics 10 and 15. 2162 def Create_Topology_From_File(filename): 2163 topo = Topology() 2164 topo.gadag_root = None 2165 topo.node_list = [] 2166 topo.node_dict = {} 2167 topo.island_node_list = [] 2168 topo.prefix_list = [] # possibly no longer needed 2169 node_id_set= set() 2170 cols_list = [] 2171 # on first pass just create nodes 2172 with open(filename) as topo_file: 2173 for line in topo_file: 2174 line = line.rstrip('\r\n') 2175 cols=line.split(',') 2176 cols_list.append(cols) 2177 nodea_node_id = int(cols[0]) 2178 nodeb_node_id = int(cols[1]) 2179 if (nodea_node_id > 999 or nodeb_node_id > 999): 2180 print("node_id must be between 0 and 999.") 2181 print("exiting.") 2182 exit() 2183 node_id_set.add(nodea_node_id) 2184 node_id_set.add(nodeb_node_id) 2185 for node_id in node_id_set: 2186 node = Node() 2187 node.node_id = node_id 2188 Initialize_Node(node) 2189 topo.node_list.append(node) 2190 topo.node_dict[node_id] = node 2191 # on second pass create interfaces 2192 for cols in cols_list: 2193 nodea_node_id = int(cols[0]) 2194 nodeb_node_id = int(cols[1]) 2195 metric = int(cols[2]) 2196 reverse_metric = int(cols[2]) 2197 if len(cols) > 3: 2198 reverse_metric=int(cols[3]) 2199 nodea = topo.node_dict[nodea_node_id] 2200 nodeb = topo.node_dict[nodeb_node_id] 2201 nodea_intf = Interface() 2202 Initialize_Intf(nodea_intf) 2203 nodea_intf.metric = metric 2204 nodea_intf.area = 0 2205 nodeb_intf = Interface() 2206 Initialize_Intf(nodeb_intf) 2207 nodeb_intf.metric = reverse_metric 2208 nodeb_intf.area = 0 2209 nodea_intf.remote_intf = nodeb_intf 2210 nodeb_intf.remote_intf = nodea_intf 2211 nodea_intf.remote_node = nodeb 2212 nodeb_intf.remote_node = nodea 2213 nodea_intf.local_node = nodea 2214 nodeb_intf.local_node = nodeb 2215 nodea_intf.link_data = len(nodea.intf_list) 2216 nodeb_intf.link_data = len(nodeb.intf_list) 2217 nodea.intf_list.append(nodea_intf) 2218 nodeb.intf_list.append(nodeb_intf) 2219 return topo 2221 def MRT_Island_Identification(topo, computing_rtr, profile_id, area): 2222 if profile_id in computing_rtr.profile_id_list: 2223 computing_rtr.IN_MRT_ISLAND = True 2224 explore_list = [computing_rtr] 2225 else: 2226 return 2227 while explore_list != []: 2228 next_rtr = explore_list.pop() 2229 for intf in next_rtr.intf_list: 2230 if ( not intf.MRT_INELIGIBLE and not intf.IGP_EXCLUDED 2231 and intf.area == area ): 2233 if (profile_id in intf.remote_node.profile_id_list): 2234 intf.IN_MRT_ISLAND = True 2235 if (not intf.remote_node.IN_MRT_ISLAND): 2236 intf.remote_node.IN_MRT_ISLAND = True 2237 explore_list.append(intf.remote_node) 2239 def Set_Island_Intf_and_Node_Lists(topo): 2240 topo.island_node_list = [] 2241 for node in topo.node_list: 2242 node.island_intf_list = [] 2243 if node.IN_MRT_ISLAND: 2244 topo.island_node_list.append(node) 2245 for intf in node.intf_list: 2246 if intf.IN_MRT_ISLAND: 2247 node.island_intf_list.append(intf) 2249 global_dfs_number = None 2251 def Lowpoint_Visit(x, parent, intf_p_to_x): 2252 global global_dfs_number 2253 x.dfs_number = global_dfs_number 2254 x.lowpoint_number = x.dfs_number 2255 global_dfs_number += 1 2256 x.dfs_parent = parent 2257 if intf_p_to_x == None: 2258 x.dfs_parent_intf = None 2259 else: 2260 x.dfs_parent_intf = intf_p_to_x.remote_intf 2261 x.lowpoint_parent = None 2262 if parent != None: 2263 parent.dfs_child_list.append(x) 2264 for intf in x.island_intf_list: 2265 if intf.remote_node.dfs_number == None: 2266 Lowpoint_Visit(intf.remote_node, x, intf) 2267 if intf.remote_node.lowpoint_number < x.lowpoint_number: 2268 x.lowpoint_number = intf.remote_node.lowpoint_number 2269 x.lowpoint_parent = intf.remote_node 2270 x.lowpoint_parent_intf = intf 2271 else: 2272 if intf.remote_node is not parent: 2273 if intf.remote_node.dfs_number < x.lowpoint_number: 2274 x.lowpoint_number = intf.remote_node.dfs_number 2275 x.lowpoint_parent = intf.remote_node 2276 x.lowpoint_parent_intf = intf 2278 def Run_Lowpoint(topo): 2279 global global_dfs_number 2280 global_dfs_number = 0 2281 Lowpoint_Visit(topo.gadag_root, None, None) 2283 # addresses these cases. 2284 max_block_id = None 2286 def Assign_Block_ID(x, cur_block_id): 2287 global max_block_id 2288 x.block_id = cur_block_id 2289 for c in x.dfs_child_list: 2290 if (c.localroot is x): 2291 max_block_id += 1 2292 Assign_Block_ID(c, max_block_id) 2293 else: 2294 Assign_Block_ID(c, cur_block_id) 2296 def Run_Assign_Block_ID(topo): 2297 global max_block_id 2298 max_block_id = 0 2299 Assign_Block_ID(topo.gadag_root, max_block_id) 2301 def Construct_Ear(x, stack, intf, ear_type): 2302 ear_list = [] 2303 cur_intf = intf 2304 not_done = True 2306 while not_done: 2307 cur_intf.UNDIRECTED = False 2308 cur_intf.OUTGOING = True 2309 cur_intf.remote_intf.UNDIRECTED = False 2310 cur_intf.remote_intf.INCOMING = True 2311 if cur_intf.remote_node.IN_GADAG == False: 2312 cur_intf.remote_node.IN_GADAG = True 2313 ear_list.append(cur_intf.remote_node) 2314 if ear_type == 'CHILD': 2315 cur_intf = cur_intf.remote_node.lowpoint_parent_intf 2316 else: 2317 assert ear_type == 'NEIGHBOR' 2318 cur_intf = cur_intf.remote_node.dfs_parent_intf 2319 else: 2320 not_done = False 2322 if ear_type == 'CHILD' and cur_intf.remote_node is x: 2323 # x is a cut-vertex and the local root for the block 2324 # in which the ear is computed 2325 x.IS_CUT_VERTEX = True 2326 localroot = x 2328 else: 2329 # inherit local root from the end of the ear 2330 localroot = cur_intf.remote_node.localroot 2332 while ear_list != []: 2333 y = ear_list.pop() 2334 y.localroot = localroot 2335 stack.append(y) 2337 def Construct_GADAG_via_Lowpoint(topo): 2338 gadag_root = topo.gadag_root 2339 gadag_root.IN_GADAG = True 2340 gadag_root.localroot = None 2341 stack = [] 2342 stack.append(gadag_root) 2344 while stack != []: 2345 x = stack.pop() 2346 for intf in x.island_intf_list: 2347 if ( intf.remote_node.IN_GADAG == False 2348 and intf.remote_node.dfs_parent is x ): 2349 Construct_Ear(x, stack, intf, 'CHILD' ) 2350 for intf in x.island_intf_list: 2351 if (intf.remote_node.IN_GADAG == False 2352 and intf.remote_node.dfs_parent is not x): 2353 Construct_Ear(x, stack, intf, 'NEIGHBOR') 2355 def Assign_Remaining_Lowpoint_Parents(topo): 2356 for node in topo.island_node_list: 2357 if ( node is not topo.gadag_root 2358 and node.lowpoint_parent == None ): 2359 node.lowpoint_parent = node.dfs_parent 2360 node.lowpoint_parent_intf = node.dfs_parent_intf 2361 node.lowpoint_number = node.dfs_parent.dfs_number 2363 def Add_Undirected_Block_Root_Links(topo): 2364 for node in topo.island_node_list: 2365 if node.IS_CUT_VERTEX or node is topo.gadag_root: 2366 for intf in node.island_intf_list: 2367 if ( intf.remote_node.localroot is not node 2368 or intf.PROCESSED ): 2369 continue 2370 bundle_list = [] 2371 bundle = Bundle() 2372 bundle.UNDIRECTED = True 2373 bundle.OUTGOING = False 2374 bundle.INCOMING = False 2375 for intf2 in node.island_intf_list: 2377 if intf2.remote_node is intf.remote_node: 2378 bundle_list.append(intf2) 2379 if not intf2.UNDIRECTED: 2380 bundle.UNDIRECTED = False 2381 if intf2.INCOMING: 2382 bundle.INCOMING = True 2383 if intf2.OUTGOING: 2384 bundle.OUTGOING = True 2385 if bundle.UNDIRECTED: 2386 for intf3 in bundle_list: 2387 intf3.UNDIRECTED = False 2388 intf3.remote_intf.UNDIRECTED = False 2389 intf3.PROCESSED = True 2390 intf3.remote_intf.PROCESSED = True 2391 intf3.OUTGOING = True 2392 intf3.remote_intf.INCOMING = True 2393 else: 2394 if (bundle.OUTGOING and bundle.INCOMING): 2395 for intf3 in bundle_list: 2396 intf3.UNDIRECTED = False 2397 intf3.remote_intf.UNDIRECTED = False 2398 intf3.PROCESSED = True 2399 intf3.remote_intf.PROCESSED = True 2400 intf3.OUTGOING = True 2401 intf3.INCOMING = True 2402 intf3.remote_intf.INCOMING = True 2403 intf3.remote_intf.OUTGOING = True 2404 elif bundle.OUTGOING: 2405 for intf3 in bundle_list: 2406 intf3.UNDIRECTED = False 2407 intf3.remote_intf.UNDIRECTED = False 2408 intf3.PROCESSED = True 2409 intf3.remote_intf.PROCESSED = True 2410 intf3.OUTGOING = True 2411 intf3.remote_intf.INCOMING = True 2412 elif bundle.INCOMING: 2413 for intf3 in bundle_list: 2414 intf3.UNDIRECTED = False 2415 intf3.remote_intf.UNDIRECTED = False 2416 intf3.PROCESSED = True 2417 intf3.remote_intf.PROCESSED = True 2418 intf3.INCOMING = True 2419 intf3.remote_intf.OUTGOING = True 2421 def Modify_Block_Root_Incoming_Links(topo): 2422 for node in topo.island_node_list: 2423 if ( node.IS_CUT_VERTEX == True or node is topo.gadag_root ): 2424 for intf in node.island_intf_list: 2426 if intf.remote_node.localroot is node: 2427 if intf.INCOMING: 2428 intf.INCOMING = False 2429 intf.INCOMING_STORED = True 2430 intf.remote_intf.OUTGOING = False 2431 intf.remote_intf.OUTGOING_STORED = True 2433 def Revert_Block_Root_Incoming_Links(topo): 2434 for node in topo.island_node_list: 2435 if ( node.IS_CUT_VERTEX == True or node is topo.gadag_root ): 2436 for intf in node.island_intf_list: 2437 if intf.remote_node.localroot is node: 2438 if intf.INCOMING_STORED: 2439 intf.INCOMING = True 2440 intf.remote_intf.OUTGOING = True 2441 intf.INCOMING_STORED = False 2442 intf.remote_intf.OUTGOING_STORED = False 2444 def Run_Topological_Sort_GADAG(topo): 2445 Modify_Block_Root_Incoming_Links(topo) 2446 for node in topo.island_node_list: 2447 node.unvisited = 0 2448 for intf in node.island_intf_list: 2449 if (intf.INCOMING == True): 2450 node.unvisited += 1 2451 working_list = [] 2452 topo_order_list = [] 2453 working_list.append(topo.gadag_root) 2454 while working_list != []: 2455 y = working_list.pop(0) 2456 topo_order_list.append(y) 2457 for intf in y.island_intf_list: 2458 if ( intf.OUTGOING == True): 2459 intf.remote_node.unvisited -= 1 2460 if intf.remote_node.unvisited == 0: 2461 working_list.append(intf.remote_node) 2462 next_topo_order = 1 2463 while topo_order_list != []: 2464 y = topo_order_list.pop(0) 2465 y.topo_order = next_topo_order 2466 next_topo_order += 1 2467 Revert_Block_Root_Incoming_Links(topo) 2469 def Set_Other_Undirected_Links_Based_On_Topo_Order(topo): 2470 for node in topo.island_node_list: 2471 for intf in node.island_intf_list: 2472 if intf.UNDIRECTED: 2473 if node.topo_order < intf.remote_node.topo_order: 2475 intf.OUTGOING = True 2476 intf.UNDIRECTED = False 2477 intf.remote_intf.INCOMING = True 2478 intf.remote_intf.UNDIRECTED = False 2479 else: 2480 intf.INCOMING = True 2481 intf.UNDIRECTED = False 2482 intf.remote_intf.OUTGOING = True 2483 intf.remote_intf.UNDIRECTED = False 2485 def Initialize_Temporary_Interface_Flags(topo): 2486 for node in topo.island_node_list: 2487 for intf in node.island_intf_list: 2488 intf.PROCESSED = False 2489 intf.INCOMING_STORED = False 2490 intf.OUTGOING_STORED = False 2492 def Add_Undirected_Links(topo): 2493 Initialize_Temporary_Interface_Flags(topo) 2494 Add_Undirected_Block_Root_Links(topo) 2495 Run_Topological_Sort_GADAG(topo) 2496 Set_Other_Undirected_Links_Based_On_Topo_Order(topo) 2498 def In_Common_Block(x,y): 2499 if ( (x.block_id == y.block_id) 2500 or ( x is y.localroot) or (y is x.localroot) ): 2501 return True 2502 return False 2504 def Copy_List_Items(target_list, source_list): 2505 del target_list[:] # Python idiom to remove all elements of a list 2506 for element in source_list: 2507 target_list.append(element) 2509 def Add_Item_To_List_If_New(target_list, item): 2510 if item not in target_list: 2511 target_list.append(item) 2513 def Store_Results(y, direction): 2514 if direction == 'INCREASING': 2515 y.HIGHER = True 2516 Copy_List_Items(y.blue_next_hops, y.next_hops) 2517 if direction == 'DECREASING': 2518 y.LOWER = True 2519 Copy_List_Items(y.red_next_hops, y.next_hops) 2520 if direction == 'NORMAL_SPF': 2521 y.primary_spf_metric = y.spf_metric 2522 Copy_List_Items(y.primary_next_hops, y.next_hops) 2524 if direction == 'MRT_ISLAND_SPF': 2525 Copy_List_Items(y.mrt_island_next_hops, y.next_hops) 2526 if direction == 'COLLAPSED_SPF': 2527 y.collapsed_metric = y.spf_metric 2528 Copy_List_Items(y.collapsed_next_hops, y.next_hops) 2530 # Note that the Python heapq fucntion allows for duplicate items, 2531 # so we use the 'spf_visited' property to only consider a node 2532 # as min_node the first time it gets removed from the heap. 2533 def SPF_No_Traverse_Block_Root(topo, spf_root, block_root, direction): 2534 spf_heap = [] 2535 for y in topo.island_node_list: 2536 y.spf_metric = 2147483647 # 2^31-1 2537 y.next_hops = [] 2538 y.spf_visited = False 2539 spf_root.spf_metric = 0 2540 heapq.heappush(spf_heap, 2541 (spf_root.spf_metric, spf_root.node_id, spf_root) ) 2542 while spf_heap != []: 2543 #extract third element of tuple popped from heap 2544 min_node = heapq.heappop(spf_heap)[2] 2545 if min_node.spf_visited: 2546 continue 2547 min_node.spf_visited = True 2548 Store_Results(min_node, direction) 2549 if ( (min_node is spf_root) or (min_node is not block_root) ): 2550 for intf in min_node.island_intf_list: 2551 if ( ( (direction == 'INCREASING' and intf.OUTGOING ) 2552 or (direction == 'DECREASING' and intf.INCOMING ) ) 2553 and In_Common_Block(spf_root, intf.remote_node) ) : 2554 path_metric = min_node.spf_metric + intf.metric 2555 if path_metric < intf.remote_node.spf_metric: 2556 intf.remote_node.spf_metric = path_metric 2557 if min_node is spf_root: 2558 intf.remote_node.next_hops = [intf] 2559 else: 2560 Copy_List_Items(intf.remote_node.next_hops, 2561 min_node.next_hops) 2562 heapq.heappush(spf_heap, 2563 ( intf.remote_node.spf_metric, 2564 intf.remote_node.node_id, 2565 intf.remote_node ) ) 2566 elif path_metric == intf.remote_node.spf_metric: 2567 if min_node is spf_root: 2568 Add_Item_To_List_If_New( 2569 intf.remote_node.next_hops,intf) 2570 else: 2571 for nh_intf in min_node.next_hops: 2573 Add_Item_To_List_If_New( 2574 intf.remote_node.next_hops,nh_intf) 2576 def Normal_SPF(topo, spf_root): 2577 spf_heap = [] 2578 for y in topo.node_list: 2579 y.spf_metric = 2147483647 # 2^31-1 as max metric 2580 y.next_hops = [] 2581 y.primary_spf_metric = 2147483647 2582 y.primary_next_hops = [] 2583 y.spf_visited = False 2584 spf_root.spf_metric = 0 2585 heapq.heappush(spf_heap, 2586 (spf_root.spf_metric,spf_root.node_id,spf_root) ) 2587 while spf_heap != []: 2588 #extract third element of tuple popped from heap 2589 min_node = heapq.heappop(spf_heap)[2] 2590 if min_node.spf_visited: 2591 continue 2592 min_node.spf_visited = True 2593 Store_Results(min_node, 'NORMAL_SPF') 2594 for intf in min_node.intf_list: 2595 path_metric = min_node.spf_metric + intf.metric 2596 if path_metric < intf.remote_node.spf_metric: 2597 intf.remote_node.spf_metric = path_metric 2598 if min_node is spf_root: 2599 intf.remote_node.next_hops = [intf] 2600 else: 2601 Copy_List_Items(intf.remote_node.next_hops, 2602 min_node.next_hops) 2603 heapq.heappush(spf_heap, 2604 ( intf.remote_node.spf_metric, 2605 intf.remote_node.node_id, 2606 intf.remote_node ) ) 2607 elif path_metric == intf.remote_node.spf_metric: 2608 if min_node is spf_root: 2609 Add_Item_To_List_If_New( 2610 intf.remote_node.next_hops,intf) 2611 else: 2612 for nh_intf in min_node.next_hops: 2613 Add_Item_To_List_If_New( 2614 intf.remote_node.next_hops,nh_intf) 2616 def Set_Edge(y): 2617 if (y.blue_next_hops == [] and y.red_next_hops == []): 2618 Set_Edge(y.localroot) 2619 Copy_List_Items(y.blue_next_hops,y.localroot.blue_next_hops) 2620 Copy_List_Items(y.red_next_hops ,y.localroot.red_next_hops) 2621 y.order_proxy = y.localroot.order_proxy 2623 def Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,x): 2624 for y in topo.island_node_list: 2625 y.HIGHER = False 2626 y.LOWER = False 2627 y.red_next_hops = [] 2628 y.blue_next_hops = [] 2629 y.order_proxy = y 2630 SPF_No_Traverse_Block_Root(topo, x, x.localroot, 'INCREASING') 2631 SPF_No_Traverse_Block_Root(topo, x, x.localroot, 'DECREASING') 2632 for y in topo.island_node_list: 2633 if ( y is not x and (y.block_id == x.block_id) ): 2634 assert (not ( y is x.localroot or x is y.localroot) ) 2635 assert(not (y.HIGHER and y.LOWER) ) 2636 if y.HIGHER == True: 2637 Copy_List_Items(y.red_next_hops, 2638 x.localroot.red_next_hops) 2639 elif y.LOWER == True: 2640 Copy_List_Items(y.blue_next_hops, 2641 x.localroot.blue_next_hops) 2642 else: 2643 Copy_List_Items(y.blue_next_hops, 2644 x.localroot.red_next_hops) 2645 Copy_List_Items(y.red_next_hops, 2646 x.localroot.blue_next_hops) 2648 # Inherit x's MRT next-hops to reach the GADAG root 2649 # from x's MRT next-hops to reach its local root, 2650 # but first check if x is the gadag_root (in which case 2651 # x does not have a local root) or if x's local root 2652 # is the gadag root (in which case we already have the 2653 # x's MRT next-hops to reach the gadag root) 2654 if x is not topo.gadag_root and x.localroot is not topo.gadag_root: 2655 Copy_List_Items(topo.gadag_root.blue_next_hops, 2656 x.localroot.blue_next_hops) 2657 Copy_List_Items(topo.gadag_root.red_next_hops, 2658 x.localroot.red_next_hops) 2659 topo.gadag_root.order_proxy = x.localroot 2661 # Inherit next-hops and order_proxies to other blocks 2662 for y in topo.island_node_list: 2663 if (y is not topo.gadag_root and y is not x ): 2664 Set_Edge(y) 2666 def Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,x): 2667 for y in topo.island_node_list: 2669 if y is x: 2670 continue 2671 x.blue_next_hops_dict[y.node_id] = [] 2672 x.red_next_hops_dict[y.node_id] = [] 2673 Copy_List_Items(x.blue_next_hops_dict[y.node_id], 2674 y.blue_next_hops) 2675 Copy_List_Items(x.red_next_hops_dict[y.node_id], 2676 y.red_next_hops) 2678 def Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,x): 2679 for y in topo.island_node_list: 2680 x.pnh_dict[y.node_id] = [] 2681 Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops) 2682 x.alt_dict[y.node_id] = [] 2683 Copy_List_Items(x.alt_dict[y.node_id], y.alt_list) 2685 def Store_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x): 2686 for prefix in topo.named_proxy_dict: 2687 P = topo.named_proxy_dict[prefix] 2688 x.blue_next_hops_dict[P.node_id] = [] 2689 x.red_next_hops_dict[P.node_id] = [] 2690 Copy_List_Items(x.blue_next_hops_dict[P.node_id], 2691 P.blue_next_hops) 2692 Copy_List_Items(x.red_next_hops_dict[P.node_id], 2693 P.red_next_hops) 2694 if P.convert_blue_to_green: 2695 x.blue_to_green_nh_dict[P.node_id] = True 2696 if P.convert_red_to_green: 2697 x.red_to_green_nh_dict[P.node_id] = True 2699 def Store_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,x): 2700 for prefix in topo.named_proxy_dict: 2701 P = topo.named_proxy_dict[prefix] 2702 x.alt_dict[P.node_id] = [] 2703 Copy_List_Items(x.alt_dict[P.node_id], 2704 P.alt_list) 2706 def Store_Primary_NHs_For_One_Source_To_Nodes(topo,x): 2707 for y in topo.node_list: 2708 x.pnh_dict[y.node_id] = [] 2709 Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops) 2711 def Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x): 2712 for prefix in topo.named_proxy_dict: 2713 P = topo.named_proxy_dict[prefix] 2714 x.pnh_dict[P.node_id] = [] 2715 Copy_List_Items(x.pnh_dict[P.node_id], 2716 P.primary_next_hops) 2718 def Select_Alternates_Internal(D, F, primary_intf, 2719 D_lower, D_higher, D_topo_order): 2721 if D_higher and D_lower: 2722 if F.HIGHER and F.LOWER: 2723 if F.topo_order > D_topo_order: 2724 return 'USE_BLUE' 2725 else: 2726 return 'USE_RED' 2727 if F.HIGHER: 2728 return 'USE_RED' 2729 if F.LOWER: 2730 return 'USE_BLUE' 2731 assert(False) 2732 if D_higher: 2733 if F.HIGHER and F.LOWER: 2734 return 'USE_BLUE' 2735 if F.LOWER: 2736 return 'USE_BLUE' 2737 if F.HIGHER: 2738 if (F.topo_order > D_topo_order): 2739 return 'USE_BLUE' 2740 if (F.topo_order < D_topo_order): 2741 return 'USE_RED' 2742 assert(False) 2743 assert(False) 2744 if D_lower: 2745 if F.HIGHER and F.LOWER: 2746 return 'USE_RED' 2747 if F.HIGHER: 2748 return 'USE_RED' 2749 if F.LOWER: 2750 if F.topo_order > D_topo_order: 2751 return 'USE_BLUE' 2752 if F.topo_order < D_topo_order: 2753 return 'USE_RED' 2754 assert(False) 2755 assert(False) 2756 else: # D is unordered wrt S 2757 if F.HIGHER and F.LOWER: 2758 if primary_intf.OUTGOING and primary_intf.INCOMING: 2759 assert(False) 2760 if primary_intf.OUTGOING: 2761 # this case isn't hit it topo-9e 2762 return 'USE_BLUE' 2763 if primary_intf.INCOMING: 2764 return 'USE_RED' 2765 assert(False) 2767 if F.LOWER: 2768 return 'USE_RED' 2769 if F.HIGHER: 2770 return 'USE_BLUE' 2771 assert(False) 2773 def Select_Alternates(D, F, primary_intf): 2774 if (D is F) or (D.order_proxy is F): 2775 return 'PRIM_NH_IS_D_OR_OP_FOR_D' 2776 D_lower = D.order_proxy.LOWER 2777 D_higher = D.order_proxy.HIGHER 2778 D_topo_order = D.order_proxy.topo_order 2779 return Select_Alternates_Internal(D, F, primary_intf, 2780 D_lower, D_higher, D_topo_order) 2782 def Select_Alts_For_One_Src_To_Island_Dests(topo,x): 2783 Normal_SPF(topo, x) 2784 for D in topo.island_node_list: 2785 D.alt_list = [] 2786 if D is x: 2787 continue 2788 for primary_intf in D.primary_next_hops: 2789 alt = Alternate() 2790 alt.failed_intf = primary_intf 2791 if primary_intf in x.island_intf_list: 2792 alt.info = Select_Alternates(D, 2793 primary_intf.remote_node, primary_intf) 2794 else: 2795 alt.info = 'PRIM_NH_NOT_IN_ISLAND' 2796 Copy_List_Items(alt.nh_list, D.blue_next_hops) 2797 alt.fec = 'BLUE' 2798 alt.prot = 'NODE_PROTECTION' 2799 if (alt.info == 'USE_BLUE'): 2800 Copy_List_Items(alt.nh_list, D.blue_next_hops) 2801 alt.fec = 'BLUE' 2802 alt.prot = 'NODE_PROTECTION' 2803 if (alt.info == 'USE_RED'): 2804 Copy_List_Items(alt.nh_list, D.red_next_hops) 2805 alt.fec = 'RED' 2806 alt.prot = 'NODE_PROTECTION' 2807 if (alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D'): 2808 if primary_intf.OUTGOING and primary_intf.INCOMING: 2809 # cut-link: if there are parallel cut links, use 2810 # the link(s) with lowest metric that are not 2811 # primary intf or None 2812 cand_alt_list = [None] 2813 min_metric = 2147483647 2814 for intf in x.island_intf_list: 2816 if ( intf is not primary_intf and 2817 (intf.remote_node is 2818 primary_intf.remote_node)): 2819 if intf.metric < min_metric: 2820 cand_alt_list = [intf] 2821 min_metric = intf.metric 2822 elif intf.metric == min_metric: 2823 cand_alt_list.append(intf) 2824 if cand_alt_list != [None]: 2825 alt.fec = 'GREEN' 2826 alt.prot = 'PARALLEL_CUTLINK' 2827 else: 2828 alt.fec = 'NO_ALTERNATE' 2829 alt.prot = 'NO_PROTECTION' 2830 Copy_List_Items(alt.nh_list, cand_alt_list) 2831 elif primary_intf in D.red_next_hops: 2832 Copy_List_Items(alt.nh_list, D.blue_next_hops) 2833 alt.fec = 'BLUE' 2834 alt.prot = 'LINK_PROTECTION' 2835 else: 2836 Copy_List_Items(alt.nh_list, D.red_next_hops) 2837 alt.fec = 'RED' 2838 alt.prot = 'LINK_PROTECTION' 2839 D.alt_list.append(alt) 2841 def Write_GADAG_To_File(topo, file_prefix): 2842 gadag_edge_list = [] 2843 for node in topo.island_node_list: 2844 for intf in node.island_intf_list: 2845 if intf.OUTGOING: 2846 local_node = "%04d" % (intf.local_node.node_id) 2847 remote_node = "%04d" % (intf.remote_node.node_id) 2848 intf_data = "%03d" % (intf.link_data) 2849 edge_string=(local_node+','+remote_node+','+ 2850 intf_data+'\n') 2851 gadag_edge_list.append(edge_string) 2852 gadag_edge_list.sort(); 2853 filename = file_prefix + '_gadag.csv' 2854 with open(filename, 'w') as gadag_file: 2855 gadag_file.write('local_node,'\ 2856 'remote_node,local_intf_link_data\n') 2857 for edge_string in gadag_edge_list: 2858 gadag_file.write(edge_string); 2860 def Write_MRTs_For_All_Dests_To_File(topo, color, file_prefix): 2861 edge_list = [] 2862 for node in topo.island_node_list: 2863 if color == 'blue': 2865 node_next_hops_dict = node.blue_next_hops_dict 2866 elif color == 'red': 2867 node_next_hops_dict = node.red_next_hops_dict 2868 for dest_node_id in node_next_hops_dict: 2869 for intf in node_next_hops_dict[dest_node_id]: 2870 gadag_root = "%04d" % (topo.gadag_root.node_id) 2871 dest_node = "%04d" % (dest_node_id) 2872 local_node = "%04d" % (intf.local_node.node_id) 2873 remote_node = "%04d" % (intf.remote_node.node_id) 2874 intf_data = "%03d" % (intf.link_data) 2875 edge_string=(gadag_root+','+dest_node+','+local_node+ 2876 ','+remote_node+','+intf_data+'\n') 2877 edge_list.append(edge_string) 2878 edge_list.sort() 2879 filename = file_prefix + '_' + color + '_to_all.csv' 2880 with open(filename, 'w') as mrt_file: 2881 mrt_file.write('gadag_root,dest,'\ 2882 'local_node,remote_node,link_data\n') 2883 for edge_string in edge_list: 2884 mrt_file.write(edge_string); 2886 def Write_Both_MRTs_For_All_Dests_To_File(topo, file_prefix): 2887 Write_MRTs_For_All_Dests_To_File(topo, 'blue', file_prefix) 2888 Write_MRTs_For_All_Dests_To_File(topo, 'red', file_prefix) 2890 def Write_Alternates_For_All_Dests_To_File(topo, file_prefix): 2891 edge_list = [] 2892 for x in topo.island_node_list: 2893 for dest_node_id in x.alt_dict: 2894 alt_list = x.alt_dict[dest_node_id] 2895 for alt in alt_list: 2896 for alt_intf in alt.nh_list: 2897 gadag_root = "%04d" % (topo.gadag_root.node_id) 2898 dest_node = "%04d" % (dest_node_id) 2899 prim_local_node = \ 2900 "%04d" % (alt.failed_intf.local_node.node_id) 2901 prim_remote_node = \ 2902 "%04d" % (alt.failed_intf.remote_node.node_id) 2903 prim_intf_data = \ 2904 "%03d" % (alt.failed_intf.link_data) 2905 if alt_intf == None: 2906 alt_local_node = "None" 2907 alt_remote_node = "None" 2908 alt_intf_data = "None" 2909 else: 2910 alt_local_node = \ 2911 "%04d" % (alt_intf.local_node.node_id) 2912 alt_remote_node = \ 2913 "%04d" % (alt_intf.remote_node.node_id) 2914 alt_intf_data = \ 2915 "%03d" % (alt_intf.link_data) 2916 edge_string = (gadag_root+','+dest_node+','+ 2917 prim_local_node+','+prim_remote_node+','+ 2918 prim_intf_data+','+alt_local_node+','+ 2919 alt_remote_node+','+alt_intf_data+','+ 2920 alt.fec +'\n') 2921 edge_list.append(edge_string) 2922 edge_list.sort() 2923 filename = file_prefix + '_alts_to_all.csv' 2924 with open(filename, 'w') as alt_file: 2925 alt_file.write('gadag_root,dest,'\ 2926 'prim_nh.local_node,prim_nh.remote_node,'\ 2927 'prim_nh.link_data,alt_nh.local_node,'\ 2928 'alt_nh.remote_node,alt_nh.link_data,'\ 2929 'alt_nh.fec\n') 2930 for edge_string in edge_list: 2931 alt_file.write(edge_string); 2933 def Raise_GADAG_Root_Selection_Priority(topo,node_id): 2934 node = topo.node_dict[node_id] 2935 node.GR_sel_priority = 255 2937 def Lower_GADAG_Root_Selection_Priority(topo,node_id): 2938 node = topo.node_dict[node_id] 2939 node.GR_sel_priority = 128 2941 def GADAG_Root_Compare(node_a, node_b): 2942 if (node_a.GR_sel_priority > node_b.GR_sel_priority): 2943 return 1 2944 elif (node_a.GR_sel_priority < node_b.GR_sel_priority): 2945 return -1 2946 else: 2947 if node_a.node_id > node_b.node_id: 2948 return 1 2949 elif node_a.node_id < node_b.node_id: 2950 return -1 2952 def Set_GADAG_Root(topo,computing_router): 2953 gadag_root_list = [] 2954 for node in topo.island_node_list: 2955 gadag_root_list.append(node) 2956 gadag_root_list.sort(GADAG_Root_Compare) 2957 topo.gadag_root = gadag_root_list.pop() 2959 def Run_MRT_for_One_Source(topo, src): 2960 Reset_Computed_Node_and_Intf_Values(topo) 2961 MRT_Island_Identification(topo, src, 0, 0) 2962 Set_Island_Intf_and_Node_Lists(topo) 2963 Set_GADAG_Root(topo,src) 2964 Sort_Interfaces(topo) 2965 Run_Lowpoint(topo) 2966 Assign_Remaining_Lowpoint_Parents(topo) 2967 Construct_GADAG_via_Lowpoint(topo) 2968 Run_Assign_Block_ID(topo) 2969 Add_Undirected_Links(topo) 2970 Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,src) 2971 Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,src) 2972 Select_Alts_For_One_Src_To_Island_Dests(topo,src) 2973 Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,src) 2975 def Run_Prim_SPF_for_One_Source(topo,src): 2976 Normal_SPF(topo, src) 2977 Store_Primary_NHs_For_One_Source_To_Nodes(topo,src) 2979 def Run_MRT_for_All_Sources(topo): 2980 for src in topo.node_list: 2981 if 0 in src.profile_id_list: 2982 # src runs MRT if it has profile_id=0 2983 Run_MRT_for_One_Source(topo,src) 2984 else: 2985 # still run SPF for nodes not running MRT 2986 Run_Prim_SPF_for_One_Source(topo,src) 2988 def Write_Output_To_Files(topo,file_prefix): 2989 Write_GADAG_To_File(topo,file_prefix) 2990 Write_Both_MRTs_For_All_Dests_To_File(topo,file_prefix) 2991 Write_Alternates_For_All_Dests_To_File(topo,file_prefix) 2993 def Create_Example_Topology_Input_File(filename): 2994 data = [[01,02,10],[02,03,10],[03,04,11],[04,05,10,20],[05,06,10], 2995 [06,07,10],[06,07,10],[06,07,15],[07,01,10],[07,51,10], 2996 [51,52,10],[52,53,10],[53,03,10],[01,55,10],[55,06,10], 2997 [04,12,10],[12,13,10],[13,14,10],[14,15,10],[15,16,10], 2998 [16,17,10],[17,04,10],[05,76,10],[76,77,10],[77,78,10], 2999 [78,79,10],[79,77,10]] 3000 with open(filename, 'w') as topo_file: 3001 for item in data: 3002 if len(item) > 3: 3003 line = (str(item[0])+','+str(item[1])+','+ 3004 str(item[2])+','+str(item[3])+'\n') 3005 else: 3006 line = (str(item[0])+','+str(item[1])+','+ 3007 str(item[2])+'\n') 3008 topo_file.write(line) 3010 def Generate_Example_Topology_and_Run_MRT(): 3011 Create_Example_Topology_Input_File('example_topo_input_file.csv') 3012 topo = Create_Topology_From_File('example_topo_input_file.csv') 3013 res_file_base = 'example_topo' 3014 Raise_GADAG_Root_Selection_Priority(topo,3) 3015 Run_MRT_for_All_Sources(topo) 3016 Write_Output_To_Files(topo, res_file_base) 3018 Generate_Example_Topology_and_Run_MRT() 3020 3022 8. Algorithm Alternatives and Evaluation 3024 This specification defines the MRT Lowpoint Algorithm, which is one 3025 option among several possible MRT algorithms. Other alternatives are 3026 described in the appendices. 3028 In addition, it is possible to calculate Destination-Rooted GADAG, 3029 where for each destination, a GADAG rooted at that destination is 3030 computed. Then a router can compute the blue MRT and red MRT next- 3031 hops to that destination. Building GADAGs per destination is 3032 computationally more expensive, but may give somewhat shorter 3033 alternate paths. It may be useful for live-live multicast along 3034 MRTs. 3036 8.1. Algorithm Evaluation 3038 The MRT Lowpoint algorithm is the lowest computation of the MRT 3039 algorithms. Two other MRT algorithms are provided in Appendix A and 3040 Appendix B. When analyzed on service provider network topologies, 3041 they did not provide significant differences in the path lenghts for 3042 the alternatives. This section does not focus on that analysis or 3043 the decision to use the MRT Lowpoint algorithm as the default MRT 3044 algorithm; it has the lowest computational and storage requirements 3045 and gave comparable results. 3047 Since this document defines the MRT Lowpoint algorithm for use in 3048 fast-reroute applications, it is useful to compare MRT and Remote LFA 3049 [RFC7490]. This section compares MRT and remote LFA for IP Fast 3050 Reroute in 19 service provider network topologies, focusing on 3051 coverage and alternate path length. Figure 28 shows the node- 3052 protecting coverage provided by local LFA (LLFA), remote LFA (RLFA), 3053 and MRT against different failure scenarios in these topologies. The 3054 coverage values are calculated as the percentage of source- 3055 destination pairs protected by the given IPFRR method relative to 3056 those protectable by optimal routing, against the same failure modes. 3057 More details on alternate selection policies used for this analysis 3058 are described later in this section. 3060 +------------+-----------------------------+ 3061 | Topology | percentage of failure | 3062 | | scenarios covered by | 3063 | | IPFRR method | 3064 | |-----------------------------+ 3065 | | NP_LLFA | NP_RLFA | MRT | 3066 +------------+---------+---------+---------+ 3067 | T201 | 37 | 90 | 100 | 3068 | T202 | 73 | 83 | 100 | 3069 | T203 | 51 | 80 | 100 | 3070 | T204 | 55 | 81 | 100 | 3071 | T205 | 92 | 93 | 100 | 3072 | T206 | 71 | 74 | 100 | 3073 | T207 | 57 | 74 | 100 | 3074 | T208 | 66 | 81 | 100 | 3075 | T209 | 79 | 79 | 100 | 3076 | T210 | 95 | 98 | 100 | 3077 | T211 | 68 | 71 | 100 | 3078 | T212 | 59 | 63 | 100 | 3079 | T213 | 84 | 84 | 100 | 3080 | T214 | 68 | 78 | 100 | 3081 | T215 | 84 | 88 | 100 | 3082 | T216 | 43 | 59 | 100 | 3083 | T217 | 78 | 88 | 100 | 3084 | T218 | 72 | 75 | 100 | 3085 | T219 | 78 | 84 | 100 | 3086 +------------+---------+---------+---------+ 3088 Figure 28 3090 For the topologies analyzed here, LLFA is able to provide node- 3091 protecting coverage ranging from 37% to 95% of the source-destination 3092 pairs, as seen in the column labeled NP_LLFA. The use of RLFA in 3093 addition to LLFA is generally able to increase the node-protecting 3094 coverage. The percentage of node-protecting coverage with RLFA is 3095 provided in the column labeled NP_RLFA, ranges from 59% to 98% for 3096 these topologies. The node-protecting coverage provided by MRT is 3097 100% since MRT is able to provide protection for any source- 3098 destination pair for which a path still exists after the failure. 3100 We would also like to measure the quality of the alternate paths 3101 produced by these different IPFRR methods. An obvious approach is to 3102 take an average of the alternate path costs over all source- 3103 destination pairs and failure modes. However, this presents a 3104 problem, which we will illustrate by presenting an example of results 3105 for one topology using this approach ( Figure 29). In this table, 3106 the average relative path length is the alternate path length for the 3107 IPFRR method divided by the optimal alternate path length, averaged 3108 over all source-destination pairs and failure modes. The first three 3109 columns of data in the table give the path length calculated from the 3110 sum of IGP metrics of the links in the path. The results for 3111 topology T208 show that the metric-based path lengths for NP_LLFA and 3112 NP_RLFA alternates are on average 78 and 66 times longer than the 3113 path lengths for optimal alternates. The metric-based path lengths 3114 for MRT alternates are on average 14 times longer than for optimal 3115 alternates. 3117 +--------+------------------------------------------------+ 3118 | | average relative alternate path length | 3119 | |-----------------------+------------------------+ 3120 |Topology| IGP metric | hopcount | 3121 | |-----------------------+------------------------+ 3122 | |NP_LLFA |NP_RLFA | MRT |NP_LLFA |NP_RLFA | MRT | 3123 +--------+--------+--------+-----+--------+--------+------+ 3124 | T208 | 78.2 | 66.0 | 13.6| 0.99 | 1.01 | 1.32 | 3125 +--------+--------+--------+-----+--------+--------+------+ 3127 Figure 29 3129 The network topology represented by T208 uses values of 10, 100, and 3130 1000 as IGP costs, so small deviations from the optimal alternate 3131 path can result in large differences in relative path length. LLFA, 3132 RLFA, and MRT all allow for at least one hop in the alterate path to 3133 be chosen independent of the cost of the link. This can easily 3134 result in an alternate using a link with cost 1000, which introduces 3135 noise into the path length measurement. In the case of T208, the 3136 adverse effects of using metric-based path lengths is obvious. 3137 However, we have observed that the metric-based path length 3138 introduces noise into alternate path length measurements in several 3139 other topologies as well. For this reason, we have opted to measure 3140 the alternate path length using hopcount. While IGP metrics may be 3141 adjusted by the network operator for a number of reasons (e.g. 3142 traffic engineering), the hopcount is a fairly stable measurement of 3143 path length. As shown in the last three columns of Figure 29, the 3144 hopcount-based alternate path lengths for topology T208 are fairly 3145 well-behaved. 3147 Figure 30, Figure 31, Figure 32, and Figure 33 present the hopcount- 3148 based path length results for the 19 topologies examined. The 3149 topologies in the four tables are grouped based on the size of the 3150 topologies, as measured by the number of nodes, with Figure 30 having 3151 the smallest topologies and Figure 33 having the largest topologies. 3152 Instead of trying to represent the path lengths of a large set of 3153 alternates with a single number, we have chosen to present a 3154 histogram of the path lengths for each IPFRR method and alternate 3155 selection policy studied. The first eight colums of data represent 3156 the percentage of failure scenarios protected by an alternate N hops 3157 longer than the primary path, with the first column representing an 3158 alternate 0 or 1 hops longer than the primary path, all the way up 3159 through the eighth column respresenting an alternate 14 or 15 hops 3160 longer than the primary path. The last column in the table gives the 3161 percentage of failure scenarios for which there is no alternate less 3162 than 16 hops longer than the primary path. In the case of LLFA and 3163 RLFA, this category includes failure scenarios for which no alternate 3164 was found. 3166 For each topology, the first row (labeled OPTIMAL) is the 3167 distribution of the number of hops in excess of the primary path 3168 hopcount for optimally routed alternates. (The optimal routing was 3169 done with respect to IGP metrics, as opposed to hopcount.) The 3170 second row(labeled NP_LLFA) is the distribution of the extra hops for 3171 node-protecting LLFA. The third row (labeled NP_LLFA_THEN_NP_RLFA) 3172 is the hopcount distribution when one adds node-protecting RLFA to 3173 increase the coverage. The alternate selection policy used here 3174 first tries to find a node-protecting LLFA. If that does not exist, 3175 then it tries to find an RLFA, and checks if it is node-protecting. 3176 Comparing the hopcount distribution for RLFA and LLFA across these 3177 topologies, one can see how the coverage is increased at the expense 3178 of using longer alternates. It is also worth noting that while 3179 superficially LLFA and RLFA appear to have better hopcount 3180 distributions than OPTIMAL, the presence of entries in the last 3181 column (no alternate < 16) mainly represent failure scenarios that 3182 are not protected, for which the hopcount is effectively infinite. 3184 The fourth and fifth rows of each topology show the hopcount 3185 distributions for two alternate selection policies using MRT 3186 alternates. The policy represented by the label 3187 NP_LLFA_THEN_MRT_LOWPOINT will first use a node-protecting LLFA. If 3188 a node-protecting LLFA does not exist, then it will use an MRT 3189 alternate. The policy represented by the label MRT_LOWPOINT instead 3190 will use the MRT alternate even if a node-protecting LLFA exists. 3191 One can see from the data that combining node-protecting LLFA with 3192 MRT results in a significant shortening of the alternate hopcount 3193 distribution. 3195 +-------------------------------------------------------------------+ 3196 | | percentage of failure scenarios | 3197 | Topology name | protected by an alternate N hops | 3198 | and | longer than the primary path | 3199 | alternate selection +------------------------------------+ 3200 | policy evaluated | | | | | | | | | no | 3201 | | | | | | |10 |12 |14 | alt| 3202 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 3203 +------------------------------+---+---+---+---+---+---+---+---+----+ 3204 | T201(avg primary hops=3.5) | | | | | | | | | | 3205 | OPTIMAL | 37| 37| 20| 3| 3| | | | | 3206 | NP_LLFA | 37| | | | | | | | 63| 3207 | NP_LLFA_THEN_NP_RLFA | 37| 34| 19| | | | | | 10| 3208 | NP_LLFA_THEN_MRT_LOWPOINT | 37| 33| 21| 6| 3| | | | | 3209 | MRT_LOWPOINT | 33| 36| 23| 6| 3| | | | | 3210 +------------------------------+---+---+---+---+---+---+---+---+----+ 3211 | T202(avg primary hops=4.8) | | | | | | | | | | 3212 | OPTIMAL | 90| 9| | | | | | | | 3213 | NP_LLFA | 71| 2| | | | | | | 27| 3214 | NP_LLFA_THEN_NP_RLFA | 78| 5| | | | | | | 17| 3215 | NP_LLFA_THEN_MRT_LOWPOINT | 80| 12| 5| 2| 1| | | | | 3216 | MRT_LOWPOINT_ONLY | 48| 29| 13| 7| 2| 1| | | | 3217 +------------------------------+---+---+---+---+---+---+---+---+----+ 3218 | T203(avg primary hops=4.1) | | | | | | | | | | 3219 | OPTIMAL | 36| 37| 21| 4| 2| | | | | 3220 | NP_LLFA | 34| 15| 3| | | | | | 49| 3221 | NP_LLFA_THEN_NP_RLFA | 35| 19| 22| 4| | | | | 20| 3222 | NP_LLFA_THEN_MRT_LOWPOINT | 36| 35| 22| 5| 2| | | | | 3223 | MRT_LOWPOINT_ONLY | 31| 35| 26| 7| 2| | | | | 3224 +------------------------------+---+---+---+---+---+---+---+---+----+ 3225 | T204(avg primary hops=3.7) | | | | | | | | | | 3226 | OPTIMAL | 76| 20| 3| 1| | | | | | 3227 | NP_LLFA | 54| 1| | | | | | | 45| 3228 | NP_LLFA_THEN_NP_RLFA | 67| 10| 4| | | | | | 19| 3229 | NP_LLFA_THEN_MRT_LOWPOINT | 70| 18| 8| 3| 1| | | | | 3230 | MRT_LOWPOINT_ONLY | 58| 27| 11| 3| 1| | | | | 3231 +------------------------------+---+---+---+---+---+---+---+---+----+ 3232 | T205(avg primary hops=3.4) | | | | | | | | | | 3233 | OPTIMAL | 92| 8| | | | | | | | 3234 | NP_LLFA | 89| 3| | | | | | | 8| 3235 | NP_LLFA_THEN_NP_RLFA | 90| 4| | | | | | | 7| 3236 | NP_LLFA_THEN_MRT_LOWPOINT | 91| 9| | | | | | | | 3237 | MRT_LOWPOINT_ONLY | 62| 33| 5| 1| | | | | | 3238 +------------------------------+---+---+---+---+---+---+---+---+----+ 3240 Figure 30 3242 +-------------------------------------------------------------------+ 3243 | | percentage of failure scenarios | 3244 | Topology name | protected by an alternate N hops | 3245 | and | longer than the primary path | 3246 | alternate selection +------------------------------------+ 3247 | policy evaluated | | | | | | | | | no | 3248 | | | | | | |10 |12 |14 | alt| 3249 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 3250 +------------------------------+---+---+---+---+---+---+---+---+----+ 3251 | T206(avg primary hops=3.7) | | | | | | | | | | 3252 | OPTIMAL | 63| 30| 7| | | | | | | 3253 | NP_LLFA | 60| 9| 1| | | | | | 29| 3254 | NP_LLFA_THEN_NP_RLFA | 60| 13| 1| | | | | | 26| 3255 | NP_LLFA_THEN_MRT_LOWPOINT | 64| 29| 7| | | | | | | 3256 | MRT_LOWPOINT | 55| 32| 13| | | | | | | 3257 +------------------------------+---+---+---+---+---+---+---+---+----+ 3258 | T207(avg primary hops=3.9) | | | | | | | | | | 3259 | OPTIMAL | 71| 24| 5| 1| | | | | | 3260 | NP_LLFA | 55| 2| | | | | | | 43| 3261 | NP_LLFA_THEN_NP_RLFA | 63| 10| | | | | | | 26| 3262 | NP_LLFA_THEN_MRT_LOWPOINT | 70| 20| 7| 2| 1| | | | | 3263 | MRT_LOWPOINT_ONLY | 57| 29| 11| 3| 1| | | | | 3264 +------------------------------+---+---+---+---+---+---+---+---+----+ 3265 | T208(avg primary hops=4.6) | | | | | | | | | | 3266 | OPTIMAL | 58| 28| 12| 2| 1| | | | | 3267 | NP_LLFA | 53| 11| 3| | | | | | 34| 3268 | NP_LLFA_THEN_NP_RLFA | 56| 17| 7| 1| | | | | 19| 3269 | NP_LLFA_THEN_MRT_LOWPOINT | 58| 19| 10| 7| 3| 1| | | | 3270 | MRT_LOWPOINT_ONLY | 34| 24| 21| 13| 6| 2| 1| | | 3271 +------------------------------+---+---+---+---+---+---+---+---+----+ 3272 | T209(avg primary hops=3.6) | | | | | | | | | | 3273 | OPTIMAL | 85| 14| 1| | | | | | | 3274 | NP_LLFA | 79| | | | | | | | 21| 3275 | NP_LLFA_THEN_NP_RLFA | 79| | | | | | | | 21| 3276 | NP_LLFA_THEN_MRT_LOWPOINT | 82| 15| 2| | | | | | | 3277 | MRT_LOWPOINT_ONLY | 63| 29| 8| | | | | | | 3278 +------------------------------+---+---+---+---+---+---+---+---+----+ 3279 | T210(avg primary hops=2.5) | | | | | | | | | | 3280 | OPTIMAL | 95| 4| 1| | | | | | | 3281 | NP_LLFA | 94| 1| | | | | | | 5| 3282 | NP_LLFA_THEN_NP_RLFA | 94| 3| 1| | | | | | 2| 3283 | NP_LLFA_THEN_MRT_LOWPOINT | 95| 4| 1| | | | | | | 3284 | MRT_LOWPOINT_ONLY | 91| 6| 2| | | | | | | 3285 +------------------------------+---+---+---+---+---+---+---+---+----+ 3287 Figure 31 3289 +-------------------------------------------------------------------+ 3290 | | percentage of failure scenarios | 3291 | Topology name | protected by an alternate N hops | 3292 | and | longer than the primary path | 3293 | alternate selection +------------------------------------+ 3294 | policy evaluated | | | | | | | | | no | 3295 | | | | | | |10 |12 |14 | alt| 3296 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 3297 +------------------------------+---+---+---+---+---+---+---+---+----+ 3298 | T211(avg primary hops=3.3) | | | | | | | | | | 3299 | OPTIMAL | 88| 11| | | | | | | | 3300 | NP_LLFA | 66| 1| | | | | | | 32| 3301 | NP_LLFA_THEN_NP_RLFA | 68| 3| | | | | | | 29| 3302 | NP_LLFA_THEN_MRT_LOWPOINT | 88| 12| | | | | | | | 3303 | MRT_LOWPOINT | 85| 15| 1| | | | | | | 3304 +------------------------------+---+---+---+---+---+---+---+---+----+ 3305 | T212(avg primary hops=3.5) | | | | | | | | | | 3306 | OPTIMAL | 76| 23| 1| | | | | | | 3307 | NP_LLFA | 59| | | | | | | | 41| 3308 | NP_LLFA_THEN_NP_RLFA | 61| 1| 1| | | | | | 37| 3309 | NP_LLFA_THEN_MRT_LOWPOINT | 75| 24| 1| | | | | | | 3310 | MRT_LOWPOINT_ONLY | 66| 31| 3| | | | | | | 3311 +------------------------------+---+---+---+---+---+---+---+---+----+ 3312 | T213(avg primary hops=4.3) | | | | | | | | | | 3313 | OPTIMAL | 91| 9| | | | | | | | 3314 | NP_LLFA | 84| | | | | | | | 16| 3315 | NP_LLFA_THEN_NP_RLFA | 84| | | | | | | | 16| 3316 | NP_LLFA_THEN_MRT_LOWPOINT | 89| 10| 1| | | | | | | 3317 | MRT_LOWPOINT_ONLY | 75| 24| 1| | | | | | | 3318 +------------------------------+---+---+---+---+---+---+---+---+----+ 3319 | T214(avg primary hops=5.8) | | | | | | | | | | 3320 | OPTIMAL | 71| 22| 5| 2| | | | | | 3321 | NP_LLFA | 58| 8| 1| 1| | | | | 32| 3322 | NP_LLFA_THEN_NP_RLFA | 61| 13| 3| 1| | | | | 22| 3323 | NP_LLFA_THEN_MRT_LOWPOINT | 66| 14| 7| 5| 3| 2| 1| 1| 1| 3324 | MRT_LOWPOINT_ONLY | 30| 20| 18| 12| 8| 4| 3| 2| 3| 3325 +------------------------------+---+---+---+---+---+---+---+---+----+ 3326 | T215(avg primary hops=4.8) | | | | | | | | | | 3327 | OPTIMAL | 73| 27| | | | | | | | 3328 | NP_LLFA | 73| 11| | | | | | | 16| 3329 | NP_LLFA_THEN_NP_RLFA | 73| 13| 2| | | | | | 12| 3330 | NP_LLFA_THEN_MRT_LOWPOINT | 74| 19| 3| 2| 1| 1| 1| | | 3331 | MRT_LOWPOINT_ONLY | 32| 31| 16| 12| 4| 3| 1| | | 3332 +------------------------------+---+---+---+---+---+---+---+---+----+ 3334 Figure 32 3336 +-------------------------------------------------------------------+ 3337 | | percentage of failure scenarios | 3338 | Topology name | protected by an alternate N hops | 3339 | and | longer than the primary path | 3340 | alternate selection +------------------------------------+ 3341 | policy evaluated | | | | | | | | | no | 3342 | | | | | | |10 |12 |14 | alt| 3343 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 3344 +------------------------------+---+---+---+---+---+---+---+---+----+ 3345 | T216(avg primary hops=5.2) | | | | | | | | | | 3346 | OPTIMAL | 60| 32| 7| 1| | | | | | 3347 | NP_LLFA | 39| 4| | | | | | | 57| 3348 | NP_LLFA_THEN_NP_RLFA | 46| 12| 2| | | | | | 41| 3349 | NP_LLFA_THEN_MRT_LOWPOINT | 48| 20| 12| 7| 5| 4| 2| 1| 1| 3350 | MRT_LOWPOINT | 28| 25| 18| 11| 7| 6| 3| 2| 1| 3351 +------------------------------+---+---+---+---+---+---+---+---+----+ 3352 | T217(avg primary hops=8.0) | | | | | | | | | | 3353 | OPTIMAL | 81| 13| 5| 1| | | | | | 3354 | NP_LLFA | 74| 3| 1| | | | | | 22| 3355 | NP_LLFA_THEN_NP_RLFA | 76| 8| 3| 1| | | | | 12| 3356 | NP_LLFA_THEN_MRT_LOWPOINT | 77| 7| 5| 4| 3| 2| 1| 1| | 3357 | MRT_LOWPOINT_ONLY | 25| 18| 18| 16| 12| 6| 3| 1| | 3358 +------------------------------+---+---+---+---+---+---+---+---+----+ 3359 | T218(avg primary hops=5.5) | | | | | | | | | | 3360 | OPTIMAL | 85| 14| 1| | | | | | | 3361 | NP_LLFA | 68| 3| | | | | | | 28| 3362 | NP_LLFA_THEN_NP_RLFA | 71| 4| | | | | | | 25| 3363 | NP_LLFA_THEN_MRT_LOWPOINT | 77| 12| 7| 4| 1| | | | | 3364 | MRT_LOWPOINT_ONLY | 37| 29| 21| 10| 3| 1| | | | 3365 +------------------------------+---+---+---+---+---+---+---+---+----+ 3366 | T219(avg primary hops=7.7) | | | | | | | | | | 3367 | OPTIMAL | 77| 15| 5| 1| 1| | | | | 3368 | NP_LLFA | 72| 5| | | | | | | 22| 3369 | NP_LLFA_THEN_NP_RLFA | 73| 8| 2| | | | | | 16| 3370 | NP_LLFA_THEN_MRT_LOWPOINT | 74| 8| 3| 3| 2| 2| 2| 2| 4| 3371 | MRT_LOWPOINT_ONLY | 19| 14| 15| 12| 10| 8| 7| 6| 10| 3372 +------------------------------+---+---+---+---+---+---+---+---+----+ 3374 Figure 33 3376 In the preceding analysis, the following procedure for selecting an 3377 RLFA was used. Nodes were ordered with respect to distance from the 3378 source and checked for membership in Q and P-space. The first node 3379 to satisfy this condition was selected as the RLFA. More 3380 sophisticated methods to select node-protecting RLFAs is an area of 3381 active research. 3383 The analysis presented above uses the MRT Lowpoint Algorithm defined 3384 in this specification with a common GADAG root. The particular 3385 choice of a common GADAG root is expected to affect the quality of 3386 the MRT alternate paths, with a more central common GADAG root 3387 resulting in shorter MRT alternate path lengths. For the analysis 3388 above, the GADAG root was chosen for each topology by calculating 3389 node centrality as the sum of costs of all shortest paths to and from 3390 a given node. The node with the lowest sum was chosen as the common 3391 GADAG root. In actual deployments, the common GADAG root would be 3392 chosen based on the GADAG Root Selection Priority advertised by each 3393 router, the values of which would be determined off-line. 3395 In order to measure how sensitive the MRT alternate path lengths are 3396 to the choice of common GADAG root, we performed the same analysis 3397 using different choices of GADAG root. All of the nodes in the 3398 network were ordered with respect to the node centrality as computed 3399 above. Nodes were chosen at the 0th, 25th, and 50th percentile with 3400 respect to the centrality ordering, with 0th percentile being the 3401 most central node. The distribution of alternate path lengths for 3402 those three choices of GADAG root are shown in Figure 34 for a subset 3403 of the 19 topologies (chosen arbitrarily). The third row for each 3404 topology (labeled MRT_LOWPOINT ( 0 percentile) ) reproduces the 3405 results presented above for MRT_LOWPOINT_ONLY. The fourth and fifth 3406 rows show the alternate path length distibution for the 25th and 50th 3407 percentile choice for GADAG root. One can see some impact on the 3408 path length distribution with the less central choice of GADAG root 3409 resulting in longer path lenghths. 3411 We also looked at the impact of MRT algorithm variant on the 3412 alternate path lengths. The first two rows for each topology present 3413 results of the same alternate path length distribution analysis for 3414 the SPF and Hybrid methods for computing the GADAG. These two 3415 methods are described in Appendix A and Appendix B. For three of the 3416 topologies in this subset (T201, T206, and T211), the use of SPF or 3417 Hybrid methods does not appear to provide a significant advantage 3418 over the Lowpoint method with respect to path length. Instead, the 3419 choice of GADAG root appears to have more impact on the path length. 3420 However, for two of the topologies in this subset(T216 and T219) and 3421 for this particular choice of GAGAG root, the use of the SPF method 3422 results in noticeably shorter alternate path lengths than the use of 3423 the Lowpoint or Hybrid methods. It remains to be determined if this 3424 effect applies generally across more topologies or is sensitive to 3425 choice of GADAG root. 3427 +-------------------------------------------------------------------+ 3428 | Topology name | percentage of failure scenarios | 3429 | | protected by an alternate N hops | 3430 | MRT algorithm variant | longer than the primary path | 3431 | +------------------------------------+ 3432 | (GADAG root | | | | | | | | | no | 3433 | centrality percentile) | | | | | |10 |12 |14 | alt| 3434 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 3435 +------------------------------+---+---+---+---+---+---+---+---+----+ 3436 | T201(avg primary hops=3.5) | | | | | | | | | | 3437 | MRT_HYBRID ( 0 percentile) | 33| 26| 23| 6| 3| | | | | 3438 | MRT_SPF ( 0 percentile) | 33| 36| 23| 6| 3| | | | | 3439 | MRT_LOWPOINT ( 0 percentile) | 33| 36| 23| 6| 3| | | | | 3440 | MRT_LOWPOINT (25 percentile) | 27| 29| 23| 11| 10| | | | | 3441 | MRT_LOWPOINT (50 percentile) | 27| 29| 23| 11| 10| | | | | 3442 +------------------------------+---+---+---+---+---+---+---+---+----+ 3443 | T206(avg primary hops=3.7) | | | | | | | | | | 3444 | MRT_HYBRID ( 0 percentile) | 50| 35| 13| 2| | | | | | 3445 | MRT_SPF ( 0 percentile) | 50| 35| 13| 2| | | | | | 3446 | MRT_LOWPOINT ( 0 percentile) | 55| 32| 13| | | | | | | 3447 | MRT_LOWPOINT (25 percentile) | 47| 25| 22| 6| | | | | | 3448 | MRT_LOWPOINT (50 percentile) | 38| 38| 14| 11| | | | | | 3449 +------------------------------+---+---+---+---+---+---+---+---+----+ 3450 | T211(avg primary hops=3.3) | | | | | | | | | | 3451 | MRT_HYBRID ( 0 percentile) | 86| 14| | | | | | | | 3452 | MRT_SPF ( 0 percentile) | 86| 14| | | | | | | | 3453 | MRT_LOWPOINT ( 0 percentile) | 85| 15| 1| | | | | | | 3454 | MRT_LOWPOINT (25 percentile) | 70| 25| 5| 1| | | | | | 3455 | MRT_LOWPOINT (50 percentile) | 80| 18| 2| | | | | | | 3456 +------------------------------+---+---+---+---+---+---+---+---+----+ 3457 | T216(avg primary hops=5.2) | | | | | | | | | | 3458 | MRT_HYBRID ( 0 percentile) | 23| 22| 18| 13| 10| 7| 4| 2| 2| 3459 | MRT_SPF ( 0 percentile) | 35| 32| 19| 9| 3| 1| | | | 3460 | MRT_LOWPOINT ( 0 percentile) | 28| 25| 18| 11| 7| 6| 3| 2| 1| 3461 | MRT_LOWPOINT (25 percentile) | 24| 20| 19| 16| 10| 6| 3| 1| | 3462 | MRT_LOWPOINT (50 percentile) | 19| 14| 13| 10| 8| 6| 5| 5| 10| 3463 +------------------------------+---+---+---+---+---+---+---+---+----+ 3464 | T219(avg primary hops=7.7) | | | | | | | | | | 3465 | MRT_HYBRID ( 0 percentile) | 20| 16| 13| 10| 7| 5| 5| 5| 3| 3466 | MRT_SPF ( 0 percentile) | 31| 23| 19| 12| 7| 4| 2| 1| | 3467 | MRT_LOWPOINT ( 0 percentile) | 19| 14| 15| 12| 10| 8| 7| 6| 10| 3468 | MRT_LOWPOINT (25 percentile) | 19| 14| 15| 13| 12| 10| 6| 5| 7| 3469 | MRT_LOWPOINT (50 percentile) | 19| 14| 14| 12| 11| 8| 6| 6| 10| 3470 +------------------------------+---+---+---+---+---+---+---+---+----+ 3472 Figure 34 3474 9. Implementation Status 3476 [RFC Editor: please remove this section prior to publication.] 3478 Please see [I-D.ietf-rtgwg-mrt-frr-architecture] for details on 3479 implementation status. 3481 10. Algorithm Work to Be Done 3483 Broadcast Interfaces: The algorithm assumes that broadcast 3484 interfaces are already represented as pseudo-nodes in the network 3485 graph. Given maximal redundancy, one of the MRT will try to avoid 3486 both the pseudo-node and the next hop. The exact rules need to be 3487 fully specified. 3489 11. Acknowledgements 3491 The authors would like to thank Shraddha Hegde for her suggestions 3492 and review. We would also like to thank Anil Kumar SN for his 3493 assistance in clarifying the algorithm description and pseudocode. 3495 12. IANA Considerations 3497 This document includes no request to IANA. 3499 13. Security Considerations 3501 This architecture is not currently believed to introduce new security 3502 concerns. 3504 14. References 3506 14.1. Normative References 3508 [I-D.ietf-rtgwg-mrt-frr-architecture] 3509 Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar, 3510 A., Tantsura, J., and R. White, "An Architecture for IP/ 3511 LDP Fast-Reroute Using Maximally Redundant Trees", draft- 3512 ietf-rtgwg-mrt-frr-architecture-05 (work in progress), 3513 January 2015. 3515 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 3516 Requirement Levels", BCP 14, RFC 2119, March 1997. 3518 14.2. Informative References 3520 [EnyediThesis] 3521 Enyedi, G., "Novel Algorithms for IP Fast Reroute", 3522 Department of Telecommunications and Media Informatics, 3523 Budapest University of Technology and Economics Ph.D. 3524 Thesis, February 2011, . 3528 [I-D.ietf-isis-mrt] 3529 Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J. 3530 Tantsura, "Intermediate System to Intermediate System (IS- 3531 IS) Extensions for Maximally Redundant Trees (MRT)", 3532 draft-ietf-isis-mrt-00 (work in progress), February 2015. 3534 [I-D.ietf-isis-pcr] 3535 Farkas, J., Bragg, N., Unbehagen, P., Parsons, G., 3536 Ashwood-Smith, P., and C. Bowers, "IS-IS Path Computation 3537 and Reservation", draft-ietf-isis-pcr-00 (work in 3538 progress), April 2015. 3540 [I-D.ietf-mpls-ldp-mrt] 3541 Atlas, A., Tiruveedhula, K., Bowers, C., Tantsura, J., and 3542 I. Wijnands, "LDP Extensions to Support Maximally 3543 Redundant Trees", draft-ietf-mpls-ldp-mrt-00 (work in 3544 progress), January 2015. 3546 [I-D.ietf-ospf-mrt] 3547 Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li, 3548 "OSPF Extensions to Support Maximally Redundant Trees", 3549 draft-ietf-ospf-mrt-00 (work in progress), January 2015. 3551 [I-D.ietf-rtgwg-ipfrr-notvia-addresses] 3552 Bryant, S., Previdi, S., and M. Shand, "A Framework for IP 3553 and MPLS Fast Reroute Using Not-via Addresses", draft- 3554 ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress), 3555 May 2013. 3557 [I-D.ietf-rtgwg-lfa-manageability] 3558 Litkowski, S., Decraene, B., Filsfils, C., Raza, K., 3559 Horneffer, M., and P. Sarkar, "Operational management of 3560 Loop Free Alternates", draft-ietf-rtgwg-lfa- 3561 manageability-11 (work in progress), June 2015. 3563 [Kahn_1962_topo_sort] 3564 Kahn, A., "Topological sorting of large networks", 3565 Communications of the ACM, Volume 5, Issue 11 , Nov 1962, 3566 . 3568 [LFARevisited] 3569 Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP 3570 Fast ReRoute: Loop Free Alternates Revisited", Proceedings 3571 of IEEE INFOCOM , 2011, 3572 . 3575 [LightweightNotVia] 3576 Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP 3577 Fast ReRoute: Lightweight Not-Via without Additional 3578 Addresses", Proceedings of IEEE INFOCOM , 2009, 3579 . 3581 [MRTLinear] 3582 Enyedi, G., Retvari, G., and A. Csaszar, "On Finding 3583 Maximally Redundant Trees in Strictly Linear Time", IEEE 3584 Symposium on Computers and Comunications (ISCC) , 2009, 3585 . 3588 [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. 3589 McPherson, "OSPF Stub Router Advertisement", RFC 3137, 3590 June 2001. 3592 [RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi 3593 Topology (MT) Routing in Intermediate System to 3594 Intermediate Systems (IS-ISs)", RFC 5120, February 2008. 3596 [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast 3597 Reroute: Loop-Free Alternates", RFC 5286, September 2008. 3599 [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC 3600 5714, January 2010. 3602 [RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., 3603 Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free 3604 Alternate (LFA) Applicability in Service Provider (SP) 3605 Networks", RFC 6571, June 2012. 3607 [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. 3608 So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", 3609 RFC 7490, April 2015. 3611 Appendix A. Option 2: Computing GADAG using SPFs 3613 The basic idea in this option is to use slightly-modified SPF 3614 computations to find ears. In every block, an SPF computation is 3615 first done to find a cycle from the local root and then SPF 3616 computations in that block find ears until there are no more 3617 interfaces to be explored. The used result from the SPF computation 3618 is the path of interfaces indicated by following the previous hops 3619 from the mininized IN_GADAG node back to the SPF root. 3621 To do this, first all cut-vertices must be identified and local-roots 3622 assigned as specified in Figure 12. 3624 The slight modifications to the SPF are as follows. The root of the 3625 block is referred to as the block-root; it is either the GADAG root 3626 or a cut-vertex. 3628 a. The SPF is rooted at a neighbor x of an IN_GADAG node y. All 3629 links between y and x are marked as TEMP_UNUSABLE. They should 3630 not be used during the SPF computation. 3632 b. If y is not the block-root, then it is marked TEMP_UNUSABLE. It 3633 should not be used during the SPF computation. This prevents 3634 ears from starting and ending at the same node and avoids cycles; 3635 the exception is because cycles to/from the block-root are 3636 acceptable and expected. 3638 c. Do not explore links to nodes whose local-root is not the block- 3639 root. This keeps the SPF confined to the particular block. 3641 d. Terminate when the first IN_GADAG node z is minimized. 3643 e. Respect the existing directions (e.g. INCOMING, OUTGOING, 3644 UNDIRECTED) already specified for each interface. 3646 Mod_SPF(spf_root, block_root) 3647 Initialize spf_heap to empty 3648 Initialize nodes' spf_metric to infinity 3649 spf_root.spf_metric = 0 3650 insert(spf_heap, spf_root) 3651 found_in_gadag = false 3652 while (spf_heap is not empty) and (found_in_gadag is false) 3653 min_node = remove_lowest(spf_heap) 3654 if min_node.IN_GADAG 3655 found_in_gadag = true 3656 else 3657 foreach interface intf of min_node 3658 if ((intf.OUTGOING or intf.UNDIRECTED) and 3659 ((intf.remote_node.localroot is block_root) or 3660 (intf.remote_node is block_root)) and 3661 (intf.remote_node is not TEMP_UNUSABLE) and 3662 (intf is not TEMP_UNUSABLE)) 3663 path_metric = min_node.spf_metric + intf.metric 3664 if path_metric < intf.remote_node.spf_metric 3665 intf.remote_node.spf_metric = path_metric 3666 intf.remote_node.spf_prev_intf = intf 3667 insert_or_update(spf_heap, intf.remote_node) 3668 return min_node 3670 SPF_for_Ear(cand_intf.local_node,cand_intf.remote_node, block_root, 3671 method) 3672 Mark all interfaces between cand_intf.remote_node 3673 and cand_intf.local_node as TEMP_UNUSABLE 3674 if cand_intf.local_node is not block_root 3675 Mark cand_intf.local_node as TEMP_UNUSABLE 3676 Initialize ear_list to empty 3677 end_ear = Mod_SPF(spf_root, block_root) 3678 y = end_ear.spf_prev_hop 3679 while y.local_node is not spf_root 3680 add_to_list_start(ear_list, y) 3681 y.local_node.IN_GADAG = true 3682 y = y.local_node.spf_prev_intf 3683 if(method is not hybrid) 3684 Set_Ear_Direction(ear_list, cand_intf.local_node, 3685 end_ear,block_root) 3686 Clear TEMP_UNUSABLE from all interfaces between 3687 cand_intf.remote_node and cand_intf.local_node 3688 Clear TEMP_UNUSABLE from cand_intf.local_node 3689 return end_ear 3691 Figure 35: Modified SPF for GADAG computation 3693 Assume that an ear is found by going from y to x and then running an 3694 SPF that terminates by minimizing z (e.g. y<->x...q<->z). Now it is 3695 necessary to determine the direction of the ear; if y << z, then the 3696 path should be y->x...q->z but if y >> z, then the path should be y<- 3697 x...q<-z. In Section 5.5, the same problem was handled by finding 3698 all ears that started at a node before looking at ears starting at 3699 nodes higher in the partial order. In this algorithm, using that 3700 approach could mean that new ears aren't added in order of their 3701 total cost since all ears connected to a node would need to be found 3702 before additional nodes could be found. 3704 The alternative is to track the order relationship of each node with 3705 respect to every other node. This can be accomplished by maintaining 3706 two sets of nodes at each node. The first set, Higher_Nodes, 3707 contains all nodes that are known to be ordered above the node. The 3708 second set, Lower_Nodes, contains all nodes that are known to be 3709 ordered below the node. This is the approach used in this algorithm. 3711 Set_Ear_Direction(ear_list, end_a, end_b, block_root) 3712 // Default of A_TO_B for the following cases: 3713 // (a) end_a and end_b are the same (root) 3714 // or (b) end_a is in end_b's Lower Nodes 3715 // or (c) end_a and end_b were unordered with respect to each 3716 // other 3717 direction = A_TO_B 3718 if (end_b is block_root) and (end_a is not end_b) 3719 direction = B_TO_A 3720 else if end_a is in end_b.Higher_Nodes 3721 direction = B_TO_A 3722 if direction is B_TO_A 3723 foreach interface i in ear_list 3724 i.UNDIRECTED = false 3725 i.INCOMING = true 3726 i.remote_intf.UNDIRECTED = false 3727 i.remote_intf.OUTGOING = true 3728 else 3729 foreach interface i in ear_list 3730 i.UNDIRECTED = false 3731 i.OUTGOING = true 3732 i.remote_intf.UNDIRECTED = false 3733 i.remote_intf.INCOMING = true 3734 if end_a is end_b 3735 return 3736 // Next, update all nodes' Lower_Nodes and Higher_Nodes 3737 if (end_a is in end_b.Higher_Nodes) 3738 foreach node x where x.localroot is block_root 3739 if end_a is in x.Lower_Nodes 3740 foreach interface i in ear_list 3741 add i.remote_node to x.Lower_Nodes 3742 if end_b is in x.Higher_Nodes 3743 foreach interface i in ear_list 3744 add i.local_node to x.Higher_Nodes 3745 else 3746 foreach node x where x.localroot is block_root 3747 if end_b is in x.Lower_Nodes 3748 foreach interface i in ear_list 3749 add i.local_node to x.Lower_Nodes 3750 if end_a is in x.Higher_Nodes 3751 foreach interface i in ear_list 3752 add i.remote_node to x.Higher_Nodes 3754 Figure 36: Algorithm to assign links of an ear direction 3756 A goal of the algorithm is to find the shortest cycles and ears. An 3757 ear is started by going to a neighbor x of an IN_GADAG node y. The 3758 path from x to an IN_GADAG node is minimal, since it is computed via 3759 SPF. Since a shortest path is made of shortest paths, to find the 3760 shortest ears requires reaching from the set of IN_GADAG nodes to the 3761 closest node that isn't IN_GADAG. Therefore, an ordered tree is 3762 maintained of interfaces that could be explored from the IN_GADAG 3763 nodes. The interfaces are ordered by their characteristics of 3764 metric, local loopback address, remote loopback address, and ifindex, 3765 as in the algorithm previously described in Figure 14. 3767 The algorithm ignores interfaces picked from the ordered tree that 3768 belong to the block root if the block in which the interface is 3769 present already has an ear that has been computed. This is necessary 3770 since we allow at most one incoming interface to a block root in each 3771 block. This requirement stems from the way next-hops are computed as 3772 was seen in Section 5.7. After any ear gets computed, we traverse 3773 the newly added nodes to the GADAG and insert interfaces whose far 3774 end is not yet on the GADAG to the ordered tree for later processing. 3776 Finally, cut-links are a special case because there is no point in 3777 doing an SPF on a block of 2 nodes. The algorithm identifies cut- 3778 links simply as links where both ends of the link are cut-vertices. 3779 Cut-links can simply be added to the GADAG with both OUTGOING and 3780 INCOMING specified on their interfaces. 3782 add_eligible_interfaces_of_node(ordered_intfs_tree,node) 3783 for each interface of node 3784 if intf.remote_node.IN_GADAG is false 3785 insert(intf,ordered_intfs_tree) 3787 check_if_block_has_ear(x,block_id) 3788 block_has_ear = false 3789 for all interfaces of x 3790 if ( (intf.remote_node.block_id == block_id) && 3791 intf.remote_node.IN_GADAG ) 3792 block_has_ear = true 3793 return block_has_ear 3795 Construct_GADAG_via_SPF(topology, root) 3796 Compute_Localroot (root,root) 3797 Assign_Block_ID(root,0) 3798 root.IN_GADAG = true 3799 add_eligible_interfaces_of_node(ordered_intfs_tree,root) 3800 while ordered_intfs_tree is not empty 3801 cand_intf = remove_lowest(ordered_intfs_tree) 3802 if cand_intf.remote_node.IN_GADAG is false 3803 if L(cand_intf.remote_node) == D(cand_intf.remote_node) 3804 // Special case for cut-links 3805 cand_intf.UNDIRECTED = false 3806 cand_intf.remote_intf.UNDIRECTED = false 3807 cand_intf.OUTGOING = true 3808 cand_intf.INCOMING = true 3809 cand_intf.remote_intf.OUTGOING = true 3810 cand_intf.remote_intf.INCOMING = true 3811 cand_intf.remote_node.IN_GADAG = true 3812 add_eligible_interfaces_of_node( 3813 ordered_intfs_tree,cand_intf.remote_node) 3814 else 3815 if (cand_intf.remote_node.local_root == 3816 cand_intf.local_node) && 3817 check_if_block_has_ear(cand_intf.local_node, 3818 cand_intf.remote_node.block_id)) 3819 /* Skip the interface since the block root 3820 already has an incoming interface in the 3821 block */ 3822 else 3823 ear_end = SPF_for_Ear(cand_intf.local_node, 3824 cand_intf.remote_node, 3825 cand_intf.remote_node.localroot, 3826 SPF method) 3827 y = ear_end.spf_prev_hop 3828 while y.local_node is not cand_intf.local_node 3829 add_eligible_interfaces_of_node( 3830 ordered_intfs_tree, y.local_node) 3831 y = y.local_node.spf_prev_intf 3833 Figure 37: SPF-based GADAG algorithm 3835 Appendix B. Option 3: Computing GADAG using a hybrid method 3837 In this option, the idea is to combine the salient features of the 3838 lowpoint inheritance and SPF methods. To this end, we process nodes 3839 as they get added to the GADAG just like in the lowpoint inheritance 3840 by maintaining a stack of nodes. This ensures that we do not need to 3841 maintain lower and higher sets at each node to ascertain ear 3842 directions since the ears will always be directed from the node being 3843 processed towards the end of the ear. To compute the ear however, we 3844 resort to an SPF to have the possibility of better ears (path 3845 lentghs) thus giving more flexibility than the restricted use of 3846 lowpoint/dfs parents. 3848 Regarding ears involving a block root, unlike the SPF method which 3849 ignored interfaces of the block root after the first ear, in the 3850 hybrid method we would have to process all interfaces of the block 3851 root before moving on to other nodes in the block since the direction 3852 of an ear is pre-determined. Thus, whenever the block already has an 3853 ear computed, and we are processing an interface of the block root, 3854 we mark the block root as unusable before the SPF run that computes 3855 the ear. This ensures that the SPF terminates at some node other 3856 than the block-root. This in turn guarantees that the block-root has 3857 only one incoming interface in each block, which is necessary for 3858 correctly computing the next-hops on the GADAG. 3860 As in the SPF gadag, bridge ears are handled as a special case. 3862 The entire algorithm is shown below in Figure 38 3864 find_spf_stack_ear(stack, x, y, xy_intf, block_root) 3865 if L(y) == D(y) 3866 // Special case for cut-links 3867 xy_intf.UNDIRECTED = false 3868 xy_intf.remote_intf.UNDIRECTED = false 3869 xy_intf.OUTGOING = true 3870 xy_intf.INCOMING = true 3871 xy_intf.remote_intf.OUTGOING = true 3872 xy_intf.remote_intf.INCOMING = true 3873 xy_intf.remote_node.IN_GADAG = true 3874 push y onto stack 3875 return 3876 else 3877 if (y.local_root == x) && 3878 check_if_block_has_ear(x,y.block_id) 3879 //Avoid the block root during the SPF 3880 Mark x as TEMP_UNUSABLE 3881 end_ear = SPF_for_Ear(x,y,block_root,hybrid) 3882 If x was set as TEMP_UNUSABLE, clear it 3883 cur = end_ear 3884 while (cur != y) 3885 intf = cur.spf_prev_hop 3886 prev = intf.local_node 3887 intf.UNDIRECTED = false 3888 intf.remote_intf.UNDIRECTED = false 3889 intf.OUTGOING = true 3890 intf.remote_intf.INCOMING = true 3891 push prev onto stack 3892 cur = prev 3893 xy_intf.UNDIRECTED = false 3894 xy_intf.remote_intf.UNDIRECTED = false 3895 xy_intf.OUTGOING = true 3896 xy_intf.remote_intf.INCOMING = true 3897 return 3899 Construct_GADAG_via_hybrid(topology,root) 3900 Compute_Localroot (root,root) 3901 Assign_Block_ID(root,0) 3902 root.IN_GADAG = true 3903 Initialize Stack to empty 3904 push root onto Stack 3905 while (Stack is not empty) 3906 x = pop(Stack) 3907 for each interface intf of x 3908 y = intf.remote_node 3909 if y.IN_GADAG is false 3910 find_spf_stack_ear(stack, x, y, intf, y.block_root) 3912 Figure 38: Hybrid GADAG algorithm 3914 Authors' Addresses 3916 Gabor Sandor Enyedi (editor) 3917 Ericsson 3918 Konyves Kalman krt 11 3919 Budapest 1097 3920 Hungary 3922 Email: Gabor.Sandor.Enyedi@ericsson.com 3924 Andras Csaszar 3925 Ericsson 3926 Konyves Kalman krt 11 3927 Budapest 1097 3928 Hungary 3930 Email: Andras.Csaszar@ericsson.com 3932 Alia Atlas (editor) 3933 Juniper Networks 3934 10 Technology Park Drive 3935 Westford, MA 01886 3936 USA 3938 Email: akatlas@juniper.net 3940 Chris Bowers 3941 Juniper Networks 3942 1194 N. Mathilda Ave. 3943 Sunnyvale, CA 94089 3944 USA 3946 Email: cbowers@juniper.net 3947 Abishek Gopalan 3948 University of Arizona 3949 1230 E Speedway Blvd. 3950 Tucson, AZ 85721 3951 USA 3953 Email: abishek@ece.arizona.edu