idnits 2.17.1 draft-ietf-rtgwg-mrt-frr-algorithm-07.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 : ---------------------------------------------------------------------------- == There are 95 instances of lines with non-RFC2606-compliant FQDNs in the document. == There are 20 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (December 21, 2015) is 3048 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 1991, but not defined == Missing Reference: 'F' is mentioned on line 683, but not defined == Missing Reference: 'C' is mentioned on line 1991, but not defined == Missing Reference: 'G' is mentioned on line 1991, but not defined == Missing Reference: 'E' is mentioned on line 338, but not defined == Missing Reference: 'D' is mentioned on line 683, but not defined == Missing Reference: 'J' is mentioned on line 180, but not defined == Missing Reference: 'A' is mentioned on line 338, but not defined == Missing Reference: 'B' is mentioned on line 186, but not defined == Missing Reference: 'H' is mentioned on line 1399, but not defined == Missing Reference: 'K' is mentioned on line 683, but not defined == Missing Reference: 'N' is mentioned on line 683, but not defined == Missing Reference: 'X' is mentioned on line 1399, but not defined == Missing Reference: 'Y' is mentioned on line 1399, but not defined == Missing Reference: 'R-small' is mentioned on line 1358, but not defined == Missing Reference: 'R-great' is mentioned on line 1374, but not defined == Missing Reference: 'I' is mentioned on line 1991, but not defined == Outdated reference: A later version (-10) exists of draft-ietf-rtgwg-mrt-frr-architecture-07 == Outdated reference: A later version (-03) exists of draft-ietf-isis-mrt-01 == Outdated reference: A later version (-05) exists of draft-ietf-isis-pcr-04 == Outdated reference: A later version (-03) exists of draft-ietf-ospf-mrt-01 Summary: 0 errors (**), 0 flaws (~~), 24 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Routing Area Working Group G. Enyedi 3 Internet-Draft A. Csaszar 4 Intended status: Standards Track Ericsson 5 Expires: June 23, 2016 A. Atlas 6 C. Bowers 7 Juniper Networks 8 A. Gopalan 9 University of Arizona 10 December 21, 2015 12 Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- 13 Reroute 14 draft-ietf-rtgwg-mrt-frr-algorithm-07 16 Abstract 18 A solution for IP and LDP Fast-Reroute using Maximally Redundant 19 Trees is presented in draft-ietf-rtgwg-mrt-frr-architecture. This 20 document defines the associated MRT Lowpoint algorithm that is used 21 in the default MRT profile to compute both the necessary Maximally 22 Redundant Trees with their associated next-hops and the alternates to 23 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 June 23, 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 ordered with respect to 78 the computing node . . . . . . . . . . . . . . . . . 30 79 5.7.2. MRT next-hops to all nodes not ordered with respect 80 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. Named Proxy-Nodes . . . . . . . . . . . . . . . . . . . . 44 87 5.9.1. Determining Proxy-Node Attachment Routers . . . . . . 44 88 5.9.2. Computing if an Island Neighbor (IN) is loop-free . . 45 89 5.9.3. Computing MRT Next-Hops for Proxy-Nodes . . . . . . . 47 90 5.9.4. Computing MRT Alternates for Proxy-Nodes . . . . . . 53 91 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 61 92 7. Broadcast interfaces . . . . . . . . . . . . . . . . . . . . 61 93 7.1. Computing MRT next-hops on broadcast networks . . . . . . 62 94 7.2. Using MRT next-hops as alternates in the event of 95 failures on broadcast networks . . . . . . . . . . . . . 63 96 8. Python Implementation of MRT Lowpoint Algorithm . . . . . . . 64 97 9. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 104 98 9.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 105 99 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 115 100 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 115 101 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 115 102 13. Security Considerations . . . . . . . . . . . . . . . . . . . 115 103 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 115 104 14.1. Normative References . . . . . . . . . . . . . . . . . . 115 105 14.2. Informative References . . . . . . . . . . . . . . . . . 115 106 Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 117 107 Appendix B. Option 3: Computing GADAG using a hybrid method . . 122 108 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 124 110 1. Introduction 112 MRT Fast-Reroute requires that packets can be forwarded not only on 113 the shortest-path tree, but also on two Maximally Redundant Trees 114 (MRTs), referred to as the MRT-Blue and the MRT-Red. A router which 115 experiences a local failure must also have pre-determined which 116 alternate to use. This document defines how to compute these three 117 things for use in MRT-FRR and describes the algorithm design 118 decisions and rationale. The algorithm is based on those presented 119 in [MRTLinear] and expanded in [EnyediThesis]. The MRT Lowpoint 120 algorithm is required for implementation when the default MRT profile 121 is implemented. 123 Just as packets routed on a hop-by-hop basis require that each router 124 compute a shortest-path tree which is consistent, it is necessary for 125 each router to compute the MRT-Blue next-hops and MRT-Red next-hops 126 in a consistent fashion. This document defines the MRT Lowpoint 127 algorithm to be used as a standard in the default MRT profile for 128 MRT-FRR. 130 As now, a router's FIB will contain primary next-hops for the current 131 shortest-path tree for forwarding traffic. In addition, a router's 132 FIB will contain primary next-hops for the MRT-Blue for forwarding 133 received traffic on the MRT-Blue and primary next-hops for the MRT- 134 Red for forwarding received traffic on the MRT-Red. 136 What alternate next-hops a point-of-local-repair (PLR) selects need 137 not be consistent - but loops must be prevented. To reduce 138 congestion, it is possible for multiple alternate next-hops to be 139 selected; in the context of MRT alternates, each of those alternate 140 next-hops would be equal-cost paths. 142 This document defines an algorithm for selecting an appropriate MRT 143 alternate for consideration. Other alternates, e.g. LFAs that are 144 downstream paths, may be preferred when available and that policy- 145 based alternate selection process [I-D.ietf-rtgwg-lfa-manageability] 146 is not captured in this document. 148 [E]---[D]---| [E]<--[D]<--| [E]-->[D] 149 | | | | ^ | | 150 | | | V | | V 151 [R] [F] [C] [R] [F] [C] [R] [F] [C] 152 | | | ^ ^ | | 153 | | | | | V | 154 [A]---[B]---| [A]-->[B] [A]---[B]<--| 156 (a) (b) (c) 157 a 2-connected graph MRT-Blue towards R MRT-Red towards R 159 Figure 1 161 Algorithms for computing MRTs can handle arbitrary network topologies 162 where the whole network graph is not 2-connected, as in Figure 2, as 163 well as the easier case where the network graph is 2-connected 164 (Figure 1). Each MRT is a spanning tree. The pair of MRTs provide 165 two paths from every node X to the root of the MRTs. Those paths 166 share the minimum number of nodes and the minimum number of links. 167 Each such shared node is a cut-vertex. Any shared links are cut- 168 links. 170 [E]---[D]---| |---[J] 171 | | | | | 172 | | | | | 173 [R] [F] [C]---[G] | 174 | | | | | 175 | | | | | 176 [A]---[B]---| |---[H] 178 (a) a graph that isn't 2-connected 180 [E]<--[D]<--| [J] [E]-->[D]---| |---[J] 181 | ^ | | | | | ^ 182 V | | | V V V | 183 [R] [F] [C]<--[G] | [R] [F] [C]<--[G] | 184 ^ ^ ^ | ^ | | | 185 | | | V | V | | 186 [A]-->[B]---| |---[H] [A]<--[B]<--| [H] 188 (b) MRT-Blue towards R (c) MRT-Red towards R 190 Figure 2 192 2. Requirements Language 194 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 195 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 196 document are to be interpreted as described in [RFC2119]. 198 3. Terminology and Definitions 200 network graph: A graph that reflects the network topology where all 201 links connect exactly two nodes and broadcast links have been 202 transformed into a pseudonode representation (e.g. in OSPF, 203 viewing a Network LSA as representing a pseudonode). 205 Redundant Trees (RT): A pair of trees where the path from any node X 206 to the root R on the first tree is node-disjoint with the path 207 from the same node X to the root along the second tree. These can 208 be computed in 2-connected graphs. 210 Maximally Redundant Trees (MRT): A pair of trees where the path 211 from any node X to the root R along the first tree and the path 212 from the same node X to the root along the second tree share the 213 minimum number of nodes and the minimum number of links. Each 214 such shared node is a cut-vertex. Any shared links are cut-links. 215 Any RT is an MRT but many MRTs are not RTs. 217 MRT Island: From the computing router, the set of routers that 218 support a particular MRT profile and are connected. 220 MRT-Red: MRT-Red is used to describe one of the two MRTs; it is 221 used to describe the associated forwarding topology and MT-ID. 222 Specifically, MRT-Red is the decreasing MRT where links in the 223 GADAG are taken in the direction from a higher topologically 224 ordered node to a lower one. 226 MRT-Blue: MRT-Blue is used to describe one of the two MRTs; it is 227 used to describe the associated forwarding topology and MT-ID. 228 Specifically, MRT-Blue is the increasing MRT where links in the 229 GADAG are taken in the direction from a lower topologically 230 ordered node to a higher one. 232 cut-vertex: A vertex whose removal partitions the network. 234 cut-link: A link whose removal partitions the network. A cut-link 235 by definition must be connected between two cut-vertices. If 236 there are multiple parallel links, then they are referred to as 237 cut-links in this document if removing the set of parallel links 238 would partition the network. 240 2-connected: A graph that has no cut-vertices. This is a graph 241 that requires two nodes to be removed before the network is 242 partitioned. 244 spanning tree: A tree containing links that connects all nodes in 245 the network graph. 247 back-edge: In the context of a spanning tree computed via a depth- 248 first search, a back-edge is a link that connects a descendant of 249 a node x with an ancestor of x. 251 2-connected cluster: A maximal set of nodes that are 2-connected. 252 In a network graph with at least one cut-vertex, there will be 253 multiple 2-connected clusters. 255 block: Either a 2-connected cluster, a cut-link, or an isolated 256 vertex. 258 DAG: Directed Acyclic Graph - a digraph containing no directed 259 cycle. 261 ADAG: Almost Directed Acyclic Graph - a digraph that can be 262 transformed into a DAG with removing a single node (the root 263 node). 265 partial ADAG: A subset of an ADAG that doesn't yet contain all the 266 nodes in the block. A partial ADAG is created during the MRT 267 algorithm and then expanded until all nodes in the block are 268 included and it is an ADAG. 270 GADAG: Generalized ADAG - a digraph, which has only ADAGs as all of 271 its blocks. The root of such a block is the node closest to the 272 global root (e.g. with uniform link costs). 274 DFS: Depth-First Search 276 DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS- 277 tree path from the DFS root to x. 279 DFS descendant: A node n is a DFS descendant of x if x is on the 280 DFS-tree path from the DFS root to n. 282 ear: A path along not-yet-included-in-the-GADAG nodes that starts 283 at a node that is already-included-in-the-GADAG and that ends at a 284 node that is already-included-in-the-GADAG. The starting and 285 ending nodes may be the same node if it is a cut-vertex. 287 X >> Y or Y << X: Indicates the relationship between X and Y in a 288 partial order, such as found in a GADAG. X >> Y means that X is 289 higher in the partial order than Y. Y << X means that Y is lower 290 in the partial order than X. 292 X > Y or Y < X: Indicates the relationship between X and Y in the 293 total order, such as found via a topological sort. X > Y means 294 that X is higher in the total order than Y. Y < X means that Y is 295 lower in the total order than X. 297 proxy-node: A node added to the network graph to represent a multi- 298 homed prefix or routers outside the local MRT-fast-reroute- 299 supporting island of routers. The key property of proxy-nodes is 300 that traffic cannot transit them. 302 UNDIRECTED: In the GADAG, each link is marked as OUTGOING, INCOMING 303 or both. Until the directionality of the link is determined, the 304 link is marked as UNDIRECTED to indicate that its direction hasn't 305 been determined. 307 OUTGOING: A link marked as OUTGOING has direction in the GADAG from 308 the interface's router to the remote end. 310 INCOMING: A link marked as INCOMING has direction in the GADAG from 311 the remote end to the interface's router. 313 4. Algorithm Key Concepts 315 There are five key concepts that are critical for understanding the 316 MRT Lowpoint algorithm and other algorithms for computing MRTs. The 317 first is the idea of partially ordering the nodes in a network graph 318 with regard to each other and to the GADAG root. The second is the 319 idea of finding an ear of nodes and adding them in the correct 320 direction. The third is the idea of a Low-Point value and how it can 321 be used to identify cut-vertices and to find a second path towards 322 the root. The fourth is the idea that a non-2-connected graph is 323 made up of blocks, where a block is a 2-connected cluster, a cut-link 324 or an isolated node. The fifth is the idea of a local-root for each 325 node; this is used to compute ADAGs in each block. 327 4.1. Partial Ordering for Disjoint Paths 329 Given any two nodes X and Y in a graph, a particular total order 330 means that either X < Y or X > Y in that total order. An example 331 would be a graph where the nodes are ranked based upon their unique 332 IP loopback addresses. In a partial order, there may be some nodes 333 for which it can't be determined whether X << Y or X >> Y. A partial 334 order can be captured in a directed graph, as shown in Figure 3. In 335 a graphical representation, a link directed from X to Y indicates 336 that X is a neighbor of Y in the network graph and X << Y. 338 [A]<---[R] [E] R << A << B << C << D << E 339 | ^ R << A << B << F << G << H << D << E 340 | | 341 V | Unspecified Relationships: 342 [B]--->[C]--->[D] C and F 343 | ^ C and G 344 | | C and H 345 V | 346 [F]--->[G]--->[H] 348 Figure 3: Directed Graph showing a Partial Order 350 To compute MRTs, the root of the MRTs is at both the very bottom and 351 the very top of the partial ordering. This means that from any node 352 X, one can pick nodes higher in the order until the root is reached. 353 Similarly, from any node X, one can pick nodes lower in the order 354 until the root is reached. For instance, in Figure 4, from G the 355 higher nodes picked can be traced by following the directed links and 356 are H, D, E and R. Similarly, from G the lower nodes picked can be 357 traced by reversing the directed links and are F, B, A, and R. A 358 graph that represents this modified partial order is no longer a DAG; 359 it is termed an Almost DAG (ADAG) because if the links directed to 360 the root were removed, it would be a DAG. 362 [A]<---[R]<---[E] R << A << B << C << R 363 | ^ ^ R << A << B << C << D << E << R 364 | | | R << A << B << F << G << H << D << E << R 365 V | | 366 [B]--->[C]--->[D] Unspecified Relationships: 367 | ^ C and F 368 | | C and G 369 V | C and H 370 [F]--->[G]--->[H] 372 Figure 4: ADAG showing a Partial Order with R lowest and highest 374 Most importantly, if a node Y >> X, then Y can only appear on the 375 increasing path from X to the root and never on the decreasing path. 376 Similarly, if a node Z << X, then Z can only appear on the decreasing 377 path from X to the root and never on the inceasing path. 379 When following the increasing paths, it is possible to pick multiple 380 higher nodes and still have the certainty that those paths will be 381 disjoint from the decreasing paths. E.g. in the previous example 382 node B has multiple possibilities to forward packets along an 383 increasing path: it can either forward packets to C or F. 385 4.2. Finding an Ear and the Correct Direction 387 For simplicity, the basic idea of creating a GADAG by adding ears is 388 described assuming that the network graph is a single 2-connected 389 cluster so that an ADAG is sufficient. Generalizing to multiple 390 blocks is done by considering the block-roots instead of the GADAG 391 root - and the actual algorithm is given in Section 5.5. 393 In order to understand the basic idea of finding an ADAG, first 394 suppose that we have already a partial ADAG, which doesn't contain 395 all the nodes in the block yet, and we want to extend it to cover all 396 the nodes. Suppose that we find a path from a node X to Y such that 397 X and Y are already contained by our partial ADAG, but all the 398 remaining nodes along the path are not added to the ADAG yet. We 399 refer to such a path as an ear. 401 Recall that our ADAG is closely related to a partial order. More 402 precisely, if we remove root R, the remaining DAG describes a partial 403 order of the nodes. If we suppose that neither X nor Y is the root, 404 we may be able to compare them. If one of them is definitely lesser 405 with respect to our partial order (say X<B---| A-->B---| 417 (a) (b) (c) 419 (a) A 2-connected graph 420 (b) Partial ADAG (C is not included) 421 (c) Resulting ADAG after adding path (or ear) B-C-D 423 Figure 5 425 In this partial ADAG, node C is not yet included. However, we can 426 find path B-C-D, where both endpoints are contained by this partial 427 ADAG (we say those nodes are "ready" in the following text), and the 428 remaining node (node C) is not contained yet. If we remove R, the 429 remaining DAG defines a partial order, and with respect to this 430 partial order we can say that B<C and C->D are added). If 432 B >> D, we would add the same path in reverse direction. 434 If in the partial order where an ear's two ends are X and Y, X << Y, 435 then there must already be a directed path from X to Y in the ADAG. 436 The ear must be added in a direction such that it doesn't create a 437 cycle; therefore the ear must go from X to Y. 439 In the case, when X and Y are not ordered with each other, we can 440 select either direction for the ear. We have no restriction since 441 neither of the directions can result in a cycle. In the corner case 442 when one of the endpoints of an ear, say X, is the root (recall that 443 the two endpoints must be different), we could use both directions 444 again for the ear because the root can be considered both as smaller 445 and as greater than Y. However, we strictly pick that direction in 446 which the root is lower than Y. The logic for this decision is 447 explained in Section 5.7 449 A partial ADAG is started by finding a cycle from the root R back to 450 itself. This can be done by selecting a non-ready neighbor N of R 451 and then finding a path from N to R that doesn't use any links 452 between R and N. The direction of the cycle can be assigned either 453 way since it is starting the ordering. 455 Once a partial ADAG is already present, it will always have a node 456 that is not the root R in it. As a brief proof that a partial ADAG 457 can always have ears added to it: just select a non-ready neighbor N 458 of a ready node Q, such that Q is not the root R, find a path from N 459 to the root R in the graph with Q removed. This path is an ear where 460 the first node of the ear is Q, the next is N, then the path until 461 the first ready node the path reached (that ready node is the other 462 endpoint of the path). Since the graph is 2-connected, there must be 463 a path from N to R without Q. 465 It is always possible to select a non-ready neighbor N of a ready 466 node Q so that Q is not the root R. Because the network is 467 2-connected, N must be connected to two different nodes and only one 468 can be R. Because the initial cycle has already been added to the 469 ADAG, there are ready nodes that are not R. Since the graph is 470 2-connected, while there are non-ready nodes, there must be a non- 471 ready neighbor N of a ready node that is not R. 473 Generic_Find_Ears_ADAG(root) 474 Create an empty ADAG. Add root to the ADAG. 475 Mark root as IN_GADAG. 476 Select an arbitrary cycle containing root. 477 Add the arbitrary cycle to the ADAG. 478 Mark cycle's nodes as IN_GADAG. 479 Add cycle's non-root nodes to process_list. 480 while there exists connected nodes in graph that are not IN_GADAG 481 Select a new ear. Let its endpoints be X and Y. 482 if Y is root or (Y << X) 483 add the ear towards X to the ADAG 484 else // (a) X is root or (b)X << Y or (c) X, Y not ordered 485 Add the ear towards Y to the ADAG 487 Figure 6: Generic Algorithm to find ears and their direction in 488 2-connected graph 490 Algorithm Figure 6 merely requires that a cycle or ear be selected 491 without specifying how. Regardless of the way of selecting the path, 492 we will get an ADAG. The method used for finding and selecting the 493 ears is important; shorter ears result in shorter paths along the 494 MRTs. The MRT Lowpoint algorithm's method using Low-Point 495 Inheritance is defined in Section 5.5. Other methods are described 496 in the Appendices (Appendix A and Appendix B). 498 As an example, consider Figure 5 again. First, we select the 499 shortest cycle containing R, which can be R-A-B-F-D-E (uniform link 500 costs were assumed), so we get to the situation depicted in Figure 5 501 (b). Finally, we find a node next to a ready node; that must be node 502 C and assume we reached it from ready node B. We search a path from 503 C to R without B in the original graph. The first ready node along 504 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 506 this point. 508 4.3. Low-Point Values and Their Uses 510 A basic way of computing a spanning tree on a network graph is to run 511 a depth-first-search, such as given in Figure 7. This tree has the 512 important property that if there is a link (x, n), then either n is a 513 DFS ancestor of x or n is a DFS descendant of x. In other words, 514 either n is on the path from the root to x or x is on the path from 515 the root to n. 517 global_variable: dfs_number 519 DFS_Visit(node x, node parent) 520 D(x) = dfs_number 521 dfs_number += 1 522 x.dfs_parent = parent 523 for each link (x, w) 524 if D(w) is not set 525 DFS_Visit(w, x) 527 Run_DFS(node gadag_root) 528 dfs_number = 0 529 DFS_Visit(gadag_root, NONE) 531 Figure 7: Basic Depth-First Search algorithm 533 Given a node x, one can compute the minimal DFS number of the 534 neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the 535 earliest attachment point neighbouring x. What is interesting, 536 though, is what is the earliest attachment point from x and x's 537 descendants. This is what is determined by computing the Low-Point 538 value. 540 In order to compute the low point value, the network is traversed 541 using DFS and the vertices are numbered based on the DFS walk. Let 542 this number be represented as DFS(x). All the edges that lead to 543 already visited nodes during DFS walk are back-edges. The back-edges 544 are important because they give information about reachability of a 545 node via another path. 547 The low point number is calculated by finding: 549 Low(x) = Minimum of ( (DFS(x), 550 Lowest DFS(n, x->n is a back-edge), 551 Lowest Low(n, x->n is tree edge in DFS walk) ). 553 A detailed algorithm for computing the low-point value is given in 554 Figure 8. Figure 9 illustrates how the lowpoint algorithm applies to 555 a example graph. 557 global_variable: dfs_number 559 Lowpoint_Visit(node x, node parent, interface p_to_x) 560 D(x) = dfs_number 561 L(x) = D(x) 562 dfs_number += 1 563 x.dfs_parent = parent 564 x.dfs_parent_intf = p_to_x.remote_intf 565 x.lowpoint_parent = NONE 566 for each ordered_interface intf of x 567 if D(intf.remote_node) is not set 568 Lowpoint_Visit(intf.remote_node, x, intf) 569 if L(intf.remote_node) < L(x) 570 L(x) = L(intf.remote_node) 571 x.lowpoint_parent = intf.remote_node 572 x.lowpoint_parent_intf = intf 573 else if intf.remote_node is not parent 574 if D(intf.remote_node) < L(x) 575 L(x) = D(intf.remote_node) 576 x.lowpoint_parent = intf.remote_node 577 x.lowpoint_parent_intf = intf 579 Run_Lowpoint(node gadag_root) 580 dfs_number = 0 581 Lowpoint_Visit(gadag_root, NONE, NONE) 583 Figure 8: Computing Low-Point value 585 [E]---| [J]-------[I] [P]---[O] 586 | | | | | | 587 | | | | | | 588 [R] [D]---[C]--[F] [H]---[K] [N] 589 | | | | | | 590 | | | | | | 591 [A]--------[B] [G]---| [L]---[M] 593 (a) a non-2-connected graph 595 [E]----| [J]---------[I] [P]------[O] 596 (5, ) | (10, ) (9, ) (16, ) (15, ) 597 | | | | | | 598 | | | | | | 599 [R] [D]---[C]---[F] [H]----[K] [N] 600 (0, ) (4, ) (3, ) (6, ) (8, ) (11, ) (14, ) 601 | | | | | | 602 | | | | | | 603 [A]---------[B] [G]----| [L]------[M] 604 (1, ) (2, ) (7, ) (12, ) (13, ) 606 (b) with DFS values assigned (D(x), L(x)) 608 [E]----| [J]---------[I] [P]------[O] 609 (5,0) | (10,3) (9,3) (16,11) (15,11) 610 | | | | | | 611 | | | | | | 612 [R] [D]---[C]---[F] [H]----[K] [N] 613 (0,0) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11) 614 | | | | | | 615 | | | | | | 616 [A]---------[B] [G]----| [L]------[M] 617 (1,0) (2,0) (7,3) (12,11) (13,11) 619 (c) with low-point values assigned (D(x), L(x)) 621 Figure 9: Example lowpoint value computation 623 From the low-point value and lowpoint parent, there are three very 624 useful things which motivate our computation. 626 First, if there is a child c of x such that L(c) >= D(x), then there 627 are no paths in the network graph that go from c or its descendants 628 to an ancestor of x - and therefore x is a cut-vertex. In Figure 9, 629 this can be seen by looking at the DFS children of C. C has two 630 children - D and F and L(F) = 3 = D(C) so it is clear that C is a 631 cut-vertex and F is in a block where C is the block's root. L(D) = 0 632 < 3 = D(C) so D has a path to the ancestors of C; in this case, D can 633 go via E to reach R. Comparing the low-point values of all a node's 634 DFS-children with the node's DFS-value is very useful because it 635 allows identification of the cut-vertices and thus the blocks. 637 Second, by repeatedly following the path given by lowpoint_parent, 638 there is a path from x back to an ancestor of x that does not use the 639 link [x, x.dfs_parent] in either direction. The full path need not 640 be taken, but this gives a way of finding an initial cycle and then 641 ears. 643 Third, as seen in Figure 9, even if L(x) < D(x), there may be a block 644 that contains both the root and a DFS-child of a node while other 645 DFS-children might be in different blocks. In this example, C's 646 child D is in the same block as R while F is not. It is important to 647 realize that the root of a block may also be the root of another 648 block. 650 4.4. Blocks in a Graph 652 A key idea for an MRT algorithm is that any non-2-connected graph is 653 made up by blocks (e.g. 2-connected clusters, cut-links, and/or 654 isolated nodes). To compute GADAGs and thus MRTs, computation is 655 done in each block to compute ADAGs or Redundant Trees and then those 656 ADAGs or Redundant Trees are combined into a GADAG or MRT. 658 [E]---| [J]-------[I] [P]---[O] 659 | | | | | | 660 | | | | | | 661 [R] [D]---[C]--[F] [H]---[K] [N] 662 | | | | | | 663 | | | | | | 664 [A]--------[B] [G]---| [L]---[M] 666 (a) A graph with four blocks that are: 667 three 2-connected clusters 668 and one cut-link 670 [E]<--| [J]<------[I] [P]<--[O] 671 | | | ^ | ^ 672 V | V | V | 673 [R] [D]<--[C] [F] [H]<---[K] [N] 674 ^ | ^ ^ 675 | V | | 676 [A]------->[B] [G]---| [L]-->[M] 678 (b) MRT-Blue for destination R 680 [E]---| [J]-------->[I] [P]-->[O] 681 | | | 682 V V V 683 [R] [D]-->[C]<---[F] [H]<---[K] [N] 684 ^ | ^ | ^ | 685 | V | | | V 686 [A]<-------[B] [G]<--| [L]<--[M] 688 (c) MRT-Red for destionation R 690 Figure 10 692 Consider the example depicted in Figure 10 (a). In this figure, a 693 special graph is presented, showing us all the ways 2-connected 694 clusters can be connected. It has four blocks: block 1 contains R, 695 A, B, C, D, E, block 2 contains C, F, G, H, I, J, block 3 contains K, 696 L, M, N, O, P, and block 4 is a cut-link containing H and K. As can 697 be observed, the first two blocks have one common node (node C) and 698 blocks 2 and 3 do not have any common node, but they are connected 699 through a cut-link that is block 4. No two blocks can have more than 700 one common node, since two blocks with at least two common nodes 701 would qualify as a single 2-connected cluster. 703 Moreover, observe that if we want to get from one block to another, 704 we must use a cut-vertex (the cut-vertices in this graph are C, H, 705 K), regardless of the path selected, so we can say that all the paths 706 from block 3 along the MRTs rooted at R will cross K first. This 707 observation means that if we want to find a pair of MRTs rooted at R, 708 then we need to build up a pair of RTs in block 3 with K as a root. 709 Similarly, we need to find another pair of RTs in block 2 with C as a 710 root, and finally, we need the last pair of RTs in block 1 with R as 711 a root. When all the trees are selected, we can simply combine them; 712 when a block is a cut-link (as in block 4), that cut-link is added in 713 the same direction to both of the trees. The resulting trees are 714 depicted in Figure 10 (b) and (c). 716 Similarly, to create a GADAG it is sufficient to compute ADAGs in 717 each block and connect them. 719 It is necessary, therefore, to identify the cut-vertices, the blocks 720 and identify the appropriate local-root to use for each block. 722 4.5. Determining Local-Root and Assigning Block-ID 724 Each node in a network graph has a local-root, which is the cut- 725 vertex (or root) in the same block that is closest to the root. The 726 local-root is used to determine whether two nodes share a common 727 block. 729 Compute_Localroot(node x, node localroot) 730 x.localroot = localroot 731 for each DFS child node c of x 732 if L(c) < D(x) //x is not a cut-vertex 733 Compute_Localroot(c, x.localroot) 734 else 735 mark x as cut-vertex 736 Compute_Localroot(c, x) 738 Compute_Localroot(gadag_root, gadag_root) 740 Figure 11: A method for computing local-roots 742 There are two different ways of computing the local-root for each 743 node. The stand-alone method is given in Figure 11 and better 744 illustrates the concept; it is used by the MRT algorithms given in 745 the Appendices Appendix A and Appendix B. The MRT Lowpoint algorithm 746 computes the local-root for a block as part of computing the GADAG 747 using lowpoint inheritance; the essence of this computation is given 748 in Figure 12. Both methods for computing the local-root produce the 749 same results. 751 Get the current node, s. 752 Compute an ear(either through lowpoint inheritance 753 or by following dfs parents) from s to a ready node e. 754 (Thus, s is not e, if there is such ear.) 755 if s is e 756 for each node x in the ear that is not s 757 x.localroot = s 758 else 759 for each node x in the ear that is not s or e 760 x.localroot = e.localroot 762 Figure 12: Ear-based method for computing local-roots 764 Once the local-roots are known, two nodes X and Y are in a common 765 block if and only if one of the following three conditions apply. 767 o Y's local-root is X's local-root : They are in the same block and 768 neither is the cut-vertex closest to the root. 770 o Y's local-root is X: X is the cut-vertex closest to the root for 771 Y's block 773 o Y is X's local-root: Y is the cut-vertex closest to the root for 774 X's block 776 Once we have computed the local-root for each node in the network 777 graph, we can assign for each node, a block id that represents the 778 block in which the node is present. This computation is shown in 779 Figure 13. 781 global_var: max_block_id 783 Assign_Block_ID(x, cur_block_id) 784 x.block_id = cur_block_id 785 foreach DFS child c of x 786 if (c.local_root is x) 787 max_block_id += 1 788 Assign_Block_ID(c, max_block_id) 789 else 790 Assign_Block_ID(c, cur_block_id) 792 max_block_id = 0 793 Assign_Block_ID(gadag_root, max_block_id) 795 Figure 13: Assigning block id to identify blocks 797 5. Algorithm Sections 799 This algorithm computes one GADAG that is then used by a router to 800 determine its MRT-Blue and MRT-Red next-hops to all destinations. 801 Finally, based upon that information, alternates are selected for 802 each next-hop to each destination. The different parts of this 803 algorithm are described below. These work on a network graph after 804 its interfaces have been ordered as per Figure 14. 806 1. Compute the local MRT Island for the particular MRT Profile. 807 [See Section 5.2.] 809 2. Select the root to use for the GADAG. [See Section 5.3.] 811 3. Initialize all interfaces to UNDIRECTED. [See Section 5.4.] 813 4. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See 814 Figure 8.] 816 5. Construct the GADAG. [See Section 5.5] 818 6. Assign directions to all interfaces that are still UNDIRECTED. 819 [See Section 5.6.] 821 7. From the computing router x, compute the next-hops for the MRT- 822 Blue and MRT-Red. [See Section 5.7.] 824 8. Identify alternates for each next-hop to each destination by 825 determining which one of the blue MRT and the red MRT the 826 computing router x should select. [See Section 5.8.] 828 5.1. Interface Ordering 830 To ensure consistency in computation, all routers MUST order 831 interfaces identically down to the set of links with the same metric 832 to the same neighboring node. This is necessary for the DFS in 833 Lowpoint_Visit in Section 4.3, where the selection order of the 834 interfaces to explore results in different trees. Consistent 835 interface ordering is also necessary for computing the GADAG, where 836 the selection order of the interfaces to use to form ears can result 837 in different GADAGs. It is also necessary for the topological sort 838 described in Section 5.8, where different topological sort orderings 839 can result in undirected links being added to the GADAG in different 840 directions. 842 The required ordering between two interfaces from the same router x 843 is given in Figure 14. 845 Interface_Compare(interface a, interface b) 846 if a.metric < b.metric 847 return A_LESS_THAN_B 848 if b.metric < a.metric 849 return B_LESS_THAN_A 850 if a.neighbor.mrt_node_id < b.neighbor.mrt_node_id 851 return A_LESS_THAN_B 852 if b.neighbor.mrt_node_id < a.neighbor.mrt_node_id 853 return B_LESS_THAN_A 854 // Same metric to same node, so the order doesn't matter for 855 // interoperability. 856 return A_EQUAL_TO_B 858 Figure 14: Rules for ranking multiple interfaces. Order is from low 859 to high. 861 In Figure 14, if two interfaces on a router connect to the same 862 remote router with the same metric, the Interface_Compare function 863 returns A_EQUAL_TO_B. This is because the order in which those 864 interfaces are initially explored does not affect the final GADAG 865 produced by the algorithm described here. While only one of the 866 links will be added to the GADAG in the initial traversal, the other 867 parallel links will be added to the GADAG with the same direction 868 assigned during the procedure for assigning direction to UNDIRECTED 869 links described in Section 5.6. An implementation is free to apply 870 some additional criteria to break ties in interface ordering in this 871 situation, but that criteria is not specified here since it will not 872 affect the final GADAG produced by the algorithm. 874 The Interface_Compare function in Figure 14 relies on the 875 interface.metric and the interface.neighbor.mrt_node_id values to 876 order interfaces. The exact source of these values for different 877 IGPs (or flooding protocol in the case of ISIS-PCR 878 [I-D.ietf-isis-pcr]) and applications is specified in Figure 15. The 879 metric and mrt_node_id values for OSPFv2, OSPFv3, and IS-IS provided 880 here is normative. The metric and mrt_node_id values for ISIS-PCR 881 should be considered informational. 883 +--------------+-----------------------+-----------------------------+ 884 | IGP/flooding | mrt_node_id | metric of | 885 | protocol | of neighbor | interface | 886 | and | on interface | | 887 | application | | | 888 +--------------+-----------------------+-----------------------------+ 889 | OSPFv2 for | 4 octet Neighbor | 2 octet Metric field | 890 | IP/LDP FRR | Router ID in | for corresponding | 891 | | Link ID field for | point-to-point link | 892 | | corresponding | in Router-LSA | 893 | | point-to-point link | | 894 | | in Router-LSA | | 895 +--------------+-----------------------+-----------------------------+ 896 | OSPFv3 for | 4 octet Neighbor | 2 octet Metric field | 897 | IP/LDP FRR | Router ID field | for corresponding | 898 | | for corresponding | point-to-point link | 899 | | point-to-point link | in Router-LSA | 900 | | in Router-LSA | | 901 +--------------+-----------------------+-----------------------------+ 902 | IS-IS for | 7 octet neighbor | 3 octet metric field | 903 | IP/LDP FRR | system ID and | in Extended IS | 904 | | pseudonode number | Reachability TLV #22 | 905 | | in Extended IS | or Multi-Topology | 906 | | Reachability TLV #22 | IS Neighbor TLV #222 | 907 | | or Multi-Topology | | 908 | | IS Neighbor TLV #222 | | 909 +--------------+-----------------------+-----------------------------+ 910 | ISIS-PCR for | 8 octet Bridge ID | 3 octet SPB-LINK-METRIC in | 911 | protection | created from 2 octet | SPB-Metric sub-TLV (type 29)| 912 | of traffic | Bridge Priority in | in Extended IS Reachability | 913 | in bridged | SPB Instance sub-TLV | TLV #22 or Multi-Topology | 914 | networks | (type 1) carried in | Intermediate Systems | 915 | | MT-Capability TLV | TLV #222. In the case | 916 | | #144 and 6 octet | of asymmetric link metrics, | 917 | | neighbor system ID in | the larger link metric | 918 | | Extended IS | is used for both link | 919 | | Reachability TLV #22 | directions. | 920 | | or Multi-Topology | (informational) | 921 | | Intermediate Systems | | 922 | | TLV #222 | | 923 | | (informational) | | 924 +--------------+-----------------------+-----------------------------+ 926 Figure 15: value of interface.neighbor.mrt_node_id and 927 interface.metric to be used for ranking interfaces, for different 928 flooding protocols and applications 930 The metrics are unsigned integers and MUST be compared as unsigned 931 integers. The results of mrt_node_id comparisons MUST be the same as 932 would be obtained by converting the mrt_node_ids to unsigned integers 933 using network byte order and performing the comparison as unsigned 934 integers. In the case of IS-IS for IP/LDP FRR with point-to-point 935 links, the pseudonode number (the 7th octet) is zero. Broadcast 936 interfaces will be discussed in Section 7. 938 In the case of IS-IS for IP/LDP FRR, this specification allows for 939 the use of Multi-Topology routing. [RFC5120] requires that 940 information related to the standard/default topology (MT-ID = 0) be 941 carried in the Extended IS Reachability TLV #22, while it requires 942 that the Multi-Topology IS Neighbor TLV #222 only be used to carry 943 topology information related to non-default topologies (with non-zero 944 MT-IDs). [RFC5120] enforces this by requiring an implementation to 945 ignore TLV#222 with MT-ID = 0. The current document also requires 946 that TLV#222 with MT-ID = 0 MUST be ignored. 948 5.2. MRT Island Identification 950 The local MRT Island for a particular MRT profile can be determined 951 by starting from the computing router in the network graph and doing 952 a breadth-first-search (BFS). The BFS explores only links that are 953 in the same area/level, are not IGP-excluded, and are not MRT- 954 ineligible. The BFS explores only nodes that are are not IGP- 955 excluded, and that support the particular MRT profile. See section 7 956 of [I-D.ietf-rtgwg-mrt-frr-architecture] for more precise definitions 957 of these criteria. 959 MRT_Island_Identification(topology, computing_rtr, profile_id, area) 960 for all routers in topology 961 rtr.IN_MRT_ISLAND = FALSE 962 computing_rtr.IN_MRT_ISLAND = TRUE 963 explore_list = { computing_rtr } 964 while (explore_list is not empty) 965 next_rtr = remove_head(explore_list) 966 for each intf in next_rtr 967 if (not intf.MRT-ineligible 968 and not intf.remote_intf.MRT-ineligible 969 and not intf.IGP-excluded and (intf in area) 970 and (intf.remote_node supports profile_id) ) 971 intf.IN_MRT_ISLAND = TRUE 972 intf.remote_node.IN_MRT_ISLAND = TRUE 973 if (not intf.remote_node.IN_MRT_ISLAND)) 974 intf.remote_node.IN_MRT_ISLAND = TRUE 975 add_to_tail(explore_list, intf.remote_node) 977 Figure 16: MRT Island Identification 979 5.3. GADAG Root Selection 981 In Section 8.3 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG 982 Root Selection Policy is described for the MRT default profile. In 983 [I-D.ietf-ospf-mrt] and [I-D.ietf-isis-mrt], a mechanism is given for 984 routers to advertise the GADAG Root Selection Priority and 985 consistently select a GADAG Root inside the local MRT Island. The 986 MRT Lowpoint algorithm simply requires that all routers in the MRT 987 Island MUST select the same GADAG Root; the mechanism can vary based 988 upon the MRT profile description. Before beginning computation, the 989 network graph is reduced to contain only the set of routers that 990 support the specific MRT profile whose MRTs are being computed. 992 As noted in Section 7, pseudonodes MUST NOT be considered for GADAG 993 root selection. 995 Analysis has shown that the centrality of a router can have a 996 significant impact on the lengths of the alternate paths computed. 997 Therefore, it is RECOMMENDED that off-line analysis that considers 998 the centrality of a router be used to help determine how good a 999 choice a particular router is for the role of GADAG root. 1001 5.4. Initialization 1003 Before running the algorithm, there is the standard type of 1004 initialization to be done, such as clearing any computed DFS-values, 1005 lowpoint-values, DFS-parents, lowpoint-parents, any MRT-computed 1006 next-hops, and flags associated with algorithm. 1008 It is assumed that a regular SPF computation has been run so that the 1009 primary next-hops from the computing router to each destination are 1010 known. This is required for determining alternates at the last step. 1012 Initially, all interfaces MUST be initialized to UNDIRECTED. Whether 1013 they are OUTGOING, INCOMING or both is determined when the GADAG is 1014 constructed and augmented. 1016 It is possible that some links and nodes will be marked as unusable 1017 using standard IGP mechanisms (see section 7 of 1018 [I-D.ietf-rtgwg-mrt-frr-architecture]). Due to FRR manageability 1019 considerations [I-D.ietf-rtgwg-lfa-manageability], it may also be 1020 desirable to administratively configure some interfaces as ineligible 1021 to carry MRT FRR traffic. This constraint MUST be consistently 1022 flooded via the IGP [I-D.ietf-ospf-mrt] [I-D.ietf-isis-mrt] by the 1023 owner of the interface, so that links are known to be MRT-ineligible 1024 and not explored or used in the MRT algorithm. When a either 1025 interface on a link is advertised as MRT-ineligible, the link MUST 1026 NOT be included in the MRT Island, and will thus be excluded from the 1027 GADAG. Computation of MRT next-hops will therefore not use any MRT- 1028 ineligible links. The MRT algorithm does still need to consider MRT- 1029 ineligible links when computing FRR alternates, because an MRT- 1030 ineligible link can still be the shortest-path next-hop to reach a 1031 destination. 1033 When a broadcast interface is advertised as MRT-ineligible, then the 1034 pseudo-node representing the entire broadcast network MUST NOT be 1035 included in the MRT Island. This is equivalent to excluding all of 1036 the broadcast interfaces on that broadcast network from the MRT 1037 Island. 1039 5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance 1041 As discussed in Section 4.2, it is necessary to find ears from a node 1042 x that is already in the GADAG (known as IN_GADAG). Two different 1043 methods are used to find ears in the algorithm. The first is by 1044 going to a not IN_GADAG DFS-child and then following the chain of 1045 low-point parents until an IN_GADAG node is found. The second is by 1046 going to a not IN_GADAG neighbor and then following the chain of DFS 1047 parents until an IN_GADAG node is found. As an ear is found, the 1048 associated interfaces are marked based on the direction taken. The 1049 nodes in the ear are marked as IN_GADAG. In the algorithm, first the 1050 ears via DFS-children are found and then the ears via DFS-neighbors 1051 are found. 1053 By adding both types of ears when an IN_GADAG node is processed, all 1054 ears that connect to that node are found. The order in which the 1055 IN_GADAG nodes is processed is, of course, key to the algorithm. The 1056 order is a stack of ears so the most recent ear is found at the top 1057 of the stack. Of course, the stack stores nodes and not ears, so an 1058 ordered list of nodes, from the first node in the ear to the last 1059 node in the ear, is created as the ear is explored and then that list 1060 is pushed onto the stack. 1062 Each ear represents a partial order (see Figure 4) and processing the 1063 nodes in order along each ear ensures that all ears connecting to a 1064 node are found before a node higher in the partial order has its ears 1065 explored. This means that the direction of the links in the ear is 1066 always from the node x being processed towards the other end of the 1067 ear. Additionally, by using a stack of ears, this means that any 1068 unprocessed nodes in previous ears can only be ordered higher than 1069 nodes in the ears below it on the stack. 1071 In this algorithm that depends upon Low-Point inheritance, it is 1072 necessary that every node have a low-point parent that is not itself. 1073 If a node is a cut-vertex, that may not yet be the case. Therefore, 1074 any nodes without a low-point parent will have their low-point parent 1075 set to their DFS parent and their low-point value set to the DFS- 1076 value of their parent. This assignment also properly allows an ear 1077 between two cut-vertices. 1079 Finally, the algorithm simultaneously computes each node's local- 1080 root, as described in Figure 12. This is further elaborated as 1081 follows. The local-root can be inherited from the node at the end of 1082 the ear unless the end of the ear is x itself, in which case the 1083 local-root for all the nodes in the ear would be x. This is because 1084 whenever the first cycle is found in a block, or an ear involving a 1085 bridge is computed, the cut-vertex closest to the root would be x 1086 itself. In all other scenarios, the properties of lowpoint/dfs 1087 parents ensure that the end of the ear will be in the same block, and 1088 thus inheriting its local-root would be the correct local-root for 1089 all newly added nodes. 1091 The pseudo-code for the GADAG algorithm (assuming that the adjustment 1092 of lowpoint for cut-vertices has been made) is shown in Figure 17. 1094 Construct_Ear(x, Stack, intf, ear_type) 1095 ear_list = empty 1096 cur_node = intf.remote_node 1097 cur_intf = intf 1098 not_done = true 1100 while not_done 1101 cur_intf.UNDIRECTED = false 1102 cur_intf.OUTGOING = true 1103 cur_intf.remote_intf.UNDIRECTED = false 1104 cur_intf.remote_intf.INCOMING = true 1106 if cur_node.IN_GADAG is false 1107 cur_node.IN_GADAG = true 1108 add_to_list_end(ear_list, cur_node) 1109 if ear_type is CHILD 1110 cur_intf = cur_node.lowpoint_parent_intf 1111 cur_node = cur_node.lowpoint_parent 1112 else // ear_type must be NEIGHBOR 1113 cur_intf = cur_node.dfs_parent_intf 1114 cur_node = cur_node.dfs_parent 1115 else 1116 not_done = false 1118 if (ear_type is CHILD) and (cur_node is x) 1119 // x is a cut-vertex and the local root for 1120 // the block in which the ear is computed 1121 x.IS_CUT_VERTEX = true 1122 localroot = x 1124 else 1125 // Inherit local-root from the end of the ear 1126 localroot = cur_node.localroot 1127 while ear_list is not empty 1128 y = remove_end_item_from_list(ear_list) 1129 y.localroot = localroot 1130 push(Stack, y) 1132 Construct_GADAG_via_Lowpoint(topology, gadag_root) 1133 gadag_root.IN_GADAG = true 1134 gadag_root.localroot = None 1135 Initialize Stack to empty 1136 push gadag_root onto Stack 1137 while (Stack is not empty) 1138 x = pop(Stack) 1139 foreach ordered_interface intf of x 1140 if ((intf.remote_node.IN_GADAG == false) and 1141 (intf.remote_node.dfs_parent is x)) 1142 Construct_Ear(x, Stack, intf, CHILD) 1143 foreach ordered_interface intf of x 1144 if ((intf.remote_node.IN_GADAG == false) and 1145 (intf.remote_node.dfs_parent is not x)) 1146 Construct_Ear(x, Stack, intf, NEIGHBOR) 1148 Construct_GADAG_via_Lowpoint(topology, gadag_root) 1150 Figure 17: Low-point Inheritance GADAG algorithm 1152 5.6. Augmenting the GADAG by directing all links 1154 The GADAG, regardless of the algorithm used to construct it, at this 1155 point could be used to find MRTs, but the topology does not include 1156 all links in the network graph. That has two impacts. First, there 1157 might be shorter paths that respect the GADAG partial ordering and so 1158 the alternate paths would not be as short as possible. Second, there 1159 may be additional paths between a router x and the root that are not 1160 included in the GADAG. Including those provides potentially more 1161 bandwidth to traffic flowing on the alternates and may reduce 1162 congestion compared to just using the GADAG as currently constructed. 1164 The goal is thus to assign direction to every remaining link marked 1165 as UNDIRECTED to improve the paths and number of paths found when the 1166 MRTs are computed. 1168 To do this, we need to establish a total order that respects the 1169 partial order described by the GADAG. This can be done using Kahn's 1170 topological sort[Kahn_1962_topo_sort] which essentially assigns a 1171 number to a node x only after all nodes before it (e.g. with a link 1172 incoming to x) have had their numbers assigned. The only issue with 1173 the topological sort is that it works on DAGs and not ADAGs or 1174 GADAGs. 1176 To convert a GADAG to a DAG, it is necessary to remove all links that 1177 point to a root of block from within that block. That provides the 1178 necessary conversion to a DAG and then a topological sort can be 1179 done. When adding undirected links to the GADAG, links connecting 1180 the block root to other nodes in that block need special handling 1181 because the topological order will not always give the right answer 1182 for those links. There are three cases to consider. If the 1183 undirected link in question has another parallel link between the 1184 same two nodes that is already directed, then the direction of the 1185 undirected link can be inherited from the previously directed link. 1186 In the case of parallel cut links, we set all of the parallel links 1187 to both INCOMING and OUTGOING. Otherwise, the undirected link in 1188 question is set to OUTGOING from the block root node. A cut-link can 1189 then be identified by the fact that it will be directed both INCOMING 1190 and OUTGOING in the GADAG. The exact details of this whole process 1191 are captured in Figure 18 1193 Add_Undirected_Block_Root_Links(topo, gadag_root) 1194 foreach node x in topo 1195 if x.IS_CUT_VERTEX or x is gadag_root 1196 foreach interface i of x 1197 if (i.remote_node.localroot is not x 1198 or i.PROCESSED ) 1199 continue 1200 Initialize bundle_list to empty 1201 bundle.UNDIRECTED = true 1202 bundle.OUTGOING = false 1203 bundle.INCOMING = false 1204 foreach interface i2 in x 1205 if i2.remote_node is i.remote_node 1206 add_to_list_end(bundle_list, i2) 1207 if not i2.UNDIRECTED: 1208 bundle.UNDIRECTED = false 1209 if i2.INCOMING: 1210 bundle.INCOMING = true 1211 if i2.OUTGOING: 1212 bundle.OUTGOING = true 1213 if bundle.UNDIRECTED 1214 foreach interface i3 in bundle_list 1215 i3.UNDIRECTED = false 1216 i3.remote_intf.UNDIRECTED = false 1217 i3.PROCESSED = true 1218 i3.remote_intf.PROCESSED = true 1219 i3.OUTGOING = true 1220 i3.remote_intf.INCOMING = true 1221 else 1222 if (bundle.OUTGOING and bundle.INCOMING) 1223 foreach interface i3 in bundle_list 1224 i3.UNDIRECTED = false 1225 i3.remote_intf.UNDIRECTED = false 1226 i3.PROCESSED = true 1227 i3.remote_intf.PROCESSED = true 1228 i3.OUTGOING = true 1229 i3.INCOMING = true 1230 i3.remote_intf.INCOMING = true 1231 i3.remote_intf.OUTGOING = true 1232 else if bundle.OUTGOING 1233 foreach interface i3 in bundle_list 1234 i3.UNDIRECTED = false 1235 i3.remote_intf.UNDIRECTED = false 1236 i3.PROCESSED = true 1237 i3.remote_intf.PROCESSED = true 1238 i3.OUTGOING = true 1239 i3.remote_intf.INCOMING = true 1240 else if bundle.INCOMING 1241 foreach interface i3 in bundle_list 1242 i3.UNDIRECTED = false 1243 i3.remote_intf.UNDIRECTED = false 1244 i3.PROCESSED = true 1245 i3.remote_intf.PROCESSED = true 1246 i3.INCOMING = true 1247 i3.remote_intf.OUTGOING = true 1249 Modify_Block_Root_Incoming_Links(topo, gadag_root) 1250 foreach node x in topo 1251 if x.IS_CUT_VERTEX or x is gadag_root 1252 foreach interface i of x 1253 if i.remote_node.localroot is x 1254 if i.INCOMING: 1255 i.INCOMING = false 1256 i.INCOMING_STORED = true 1257 i.remote_intf.OUTGOING = false 1258 i.remote_intf.OUTGOING_STORED = true 1260 Revert_Block_Root_Incoming_Links(topo, gadag_root) 1261 foreach node x in topo 1262 if x.IS_CUT_VERTEX or x is gadag_root 1263 foreach interface i of x 1264 if i.remote_node.localroot is x 1265 if i.INCOMING_STORED 1266 i.INCOMING = true 1267 i.remote_intf.OUTGOING = true 1268 i.INCOMING_STORED = false 1269 i.remote_intf.OUTGOING_STORED = false 1271 Run_Topological_Sort_GADAG(topo, gadag_root) 1272 Modify_Block_Root_Incoming_Links(topo, gadag_root) 1273 foreach node x in topo 1274 node.unvisited = 0 1275 foreach interface i of x 1276 if (i.INCOMING) 1277 node.unvisited += 1 1278 Initialize working_list to empty 1279 Initialize topo_order_list to empty 1280 add_to_list_end(working_list, gadag_root) 1281 while working_list is not empty 1282 y = remove_start_item_from_list(working_list) 1283 add_to_list_end(topo_order_list, y) 1284 foreach ordered_interface i of y 1285 if intf.OUTGOING 1286 i.remote_node.unvisited -= 1 1287 if i.remote_node.unvisited is 0 1288 add_to_list_end(working_list, i.remote_node) 1289 next_topo_order = 1 1290 while topo_order_list is not empty 1291 y = remove_start_item_from_list(topo_order_list) 1292 y.topo_order = next_topo_order 1293 next_topo_order += 1 1294 Revert_Block_Root_Incoming_Links(topo, gadag_root) 1296 def Set_Other_Undirected_Links_Based_On_Topo_Order(topo) 1297 foreach node x in topo 1298 foreach interface i of x 1299 if i.UNDIRECTED: 1300 if x.topo_order < i.remote_node.topo_order 1301 i.OUTGOING = true 1302 i.UNDIRECTED = false 1303 i.remote_intf.INCOMING = true 1304 i.remote_intf.UNDIRECTED = false 1305 else 1306 i.INCOMING = true 1307 i.UNDIRECTED = false 1308 i.remote_intf.OUTGOING = true 1309 i.remote_intf.UNDIRECTED = false 1311 Add_Undirected_Links(topo, gadag_root) 1312 Add_Undirected_Block_Root_Links(topo, gadag_root) 1313 Run_Topological_Sort_GADAG(topo, gadag_root) 1314 Set_Other_Undirected_Links_Based_On_Topo_Order(topo) 1316 Add_Undirected_Links(topo, gadag_root) 1318 Figure 18: Assigning direction to UNDIRECTED links 1320 Proxy-nodes do not need to be added to the network graph. They 1321 cannot be transited and do not affect the MRTs that are computed. 1322 The details of how the MRT-Blue and MRT-Red next-hops are computed 1323 for proxy-nodes and how the appropriate alternate next-hops are 1324 selected is given in Section 5.9. 1326 5.7. Compute MRT next-hops 1328 As was discussed in Section 4.1, once a ADAG is found, it is 1329 straightforward to find the next-hops from any node X to the ADAG 1330 root. However, in this algorithm, we will reuse the common GADAG and 1331 find not only the one pair of MRTs rooted at the GADAG root with it, 1332 but find a pair rooted at each node. This is useful since it is 1333 significantly faster to compute. 1335 The method for computing differently rooted MRTs from the common 1336 GADAG is based on two ideas. First, if two nodes X and Y are ordered 1337 with respect to each other in the partial order, then an SPF along 1338 OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a 1339 decreasing-SPF) can be used to find the increasing and decreasing 1340 paths. Second, if two nodes X and Y aren't ordered with respect to 1341 each other in the partial order, then intermediary nodes can be used 1342 to create the paths by increasing/decreasing to the intermediary and 1343 then decreasing/increasing to reach Y. 1345 As usual, the two basic ideas will be discussed assuming the network 1346 is two-connected. The generalization to multiple blocks is discussed 1347 in Section 5.7.4. The full algorithm is given in Section 5.7.5. 1349 5.7.1. MRT next-hops to all nodes ordered with respect to the computing 1350 node 1352 To find two node-disjoint paths from the computing router X to any 1353 node Y, depends upon whether Y >> X or Y << X. As shown in 1354 Figure 19, if Y >> X, then there is an increasing path that goes from 1355 X to Y without crossing R; this contains nodes in the interval [X,Y]. 1356 There is also a decreasing path that decreases towards R and then 1357 decreases from R to Y; this contains nodes in the interval 1358 [X,R-small] or [R-great,Y]. The two paths cannot have common nodes 1359 other than X and Y. 1361 [Y]<---(Cloud 2)<--- [X] 1362 | ^ 1363 | | 1364 V | 1365 (Cloud 3)--->[R]--->(Cloud 1) 1367 MRT-Blue path: X->Cloud 2->Y 1368 MRT-Red path: X->Cloud 1->R->Cloud 3->Y 1370 Figure 19: Y >> X 1372 Similar logic applies if Y << X, as shown in Figure 20. In this 1373 case, the increasing path from X increases to R and then increases 1374 from R to Y to use nodes in the intervals [X,R-great] and [R-small, 1375 Y]. The decreasing path from X reaches Y without crossing R and uses 1376 nodes in the interval [Y,X]. 1378 [X]<---(Cloud 2)<--- [Y] 1379 | ^ 1380 | | 1381 V | 1382 (Cloud 3)--->[R]--->(Cloud 1) 1384 MRT-Blue path: X->Cloud 3->R->Cloud 1->Y 1385 MRT-Red path: X->Cloud 2->Y 1387 Figure 20: Y << X 1389 5.7.2. MRT next-hops to all nodes not ordered with respect to the 1390 computing node 1392 When X and Y are not ordered, the first path should increase until we 1393 get to a node G, where G >> Y. At G, we need to decrease to Y. The 1394 other path should be just the opposite: we must decrease until we get 1395 to a node H, where H << Y, and then increase. Since R is smaller and 1396 greater than Y, such G and H must exist. It is also easy to see that 1397 these two paths must be node disjoint: the first path contains nodes 1398 in interval [X,G] and [Y,G], while the second path contains nodes in 1399 interval [H,X] and [H,Y]. This is illustrated in Figure 21. It is 1400 necessary to decrease and then increase for the MRT-Blue and increase 1401 and then decrease for the MRT-Red; if one simply increased for one 1402 and decreased for the other, then both paths would go through the 1403 root R. 1405 (Cloud 6)<---[Y]<---(Cloud 5)<------------| 1406 | | 1407 | | 1408 V | 1409 [G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H] 1410 ^ | 1411 | | 1412 | | 1413 (Cloud 3)<---[X]<---(Cloud 2)<-----------| 1415 MRT-Blue path: decrease to H and increase to Y 1416 X->Cloud 2->H->Cloud 5->Y 1417 MRT-Red path: increase to G and decrease to Y 1418 X->Cloud 3->G->Cloud 6->Y 1420 Figure 21: X and Y unordered 1422 This gives disjoint paths as long as G and H are not the same node. 1423 Since G >> Y and H << Y, if G and H could be the same node, that 1424 would have to be the root R. This is not possible because there is 1425 only one incoming interface to the root R which is created when the 1426 initial cycle is found. Recall from Figure 6 that whenever an ear 1427 was found to have an end that was the root R, the ear was directed 1428 from R so that the associated interface on R is outgoing and not 1429 incoming. Therefore, there must be exactly one node M which is the 1430 largest one before R, so the MRT-Red path will never reach R; it will 1431 turn at M and decrease to Y. 1433 5.7.3. Computing Redundant Tree next-hops in a 2-connected Graph 1435 The basic ideas for computing RT next-hops in a 2-connected graph 1436 were given in Section 5.7.1 and Section 5.7.2. Given these two 1437 ideas, how can we find the trees? 1439 If some node X only wants to find the next-hops (which is usually the 1440 case for IP networks), it is enough to find which nodes are greater 1441 and less than X, and which are not ordered; this can be done by 1442 running an increasing-SPF and a decreasing-SPF rooted at X and not 1443 exploring any links from the ADAG root. 1445 In principle, an traversal method other than SPF could be used to 1446 traverse the GADAG in the process of determining blue and red next- 1447 hops that result in maximally redundant trees. This will be the case 1448 as long as one traversal uses the links in the direction specified by 1449 the GADAG and the other traversal uses the links in the direction 1450 opposite of that specified by the GADAG. However, a different 1451 traversal algorithm will generally result in different blue and red 1452 next-hops. Therefore, the algorithm specified here requires the use 1453 of SPF to traverse the GADAG to generate MRT blue and red next-hops, 1454 as described below. 1456 An increasing-SPF rooted at X and not exploring links from the root 1457 will find the increasing next-hops to all Y >> X. Those increasing 1458 next-hops are X's next-hops on the MRT-Blue to reach Y. A 1459 decreasing-SPF rooted at X and not exploring links from the root will 1460 find the decreasing next-hops to all Z << X. Those decreasing next- 1461 hops are X's next-hops on the MRT-Red to reach Z. Since the root R 1462 is both greater than and less than X, after this increasing-SPF and 1463 decreasing-SPF, X's next-hops on the MRT-Blue and on the MRT-Red to 1464 reach R are known. For every node Y >> X, X's next-hops on the MRT- 1465 Red to reach Y are set to those on the MRT-Red to reach R. For every 1466 node Z << X, X's next-hops on the MRT-Blue to reach Z are set to 1467 those on the MRT-Blue to reach R. 1469 For those nodes which were not reached by either the increasing-SPF 1470 or the decreasing-SPF, we can determine the next-hops as well. The 1471 increasing MRT-Blue next-hop for a node which is not ordered with 1472 respect to X is the next-hop along the decreasing MRT-Red towards R, 1473 and the decreasing MRT-Red next-hop is the next-hop along the 1474 increasing MRT-Blue towards R. Naturally, since R is ordered with 1475 respect to all the nodes, there will always be an increasing and a 1476 decreasing path towards it. This algorithm does not provide the 1477 complete specific path taken but just the appropriate next-hops to 1478 use. The identities of G and H are not determined by the computing 1479 node X. 1481 The final case to consider is when the GADAG root R computes its own 1482 next-hops. Since the GADAG root R is << all other nodes, running an 1483 increasing-SPF rooted at R will reach all other nodes; the MRT-Blue 1484 next-hops are those found with this increasing-SPF. Similarly, since 1485 the GADAG root R is >> all other nodes, running a decreasing-SPF 1486 rooted at R will reach all other nodes; the MRT-Red next-hops are 1487 those found with this decreasing-SPF. 1489 E---D---| E<--D<--| 1490 | | | | ^ | 1491 | | | V | | 1492 R F C R F C 1493 | | | | ^ ^ 1494 | | | V | | 1495 A---B---| A-->B---| 1497 (a) (b) 1498 A 2-connected graph A spanning ADAG rooted at R 1500 Figure 22 1502 As an example consider the situation depicted in Figure 22. Node C 1503 runs an increasing-SPF and a decreasing-SPF on the ADAG. The 1504 increasing-SPF reaches D, E and R and the decreasing-SPF reaches B, A 1505 and R. E>>C. So towards E the MRT-Blue next-hop is D, since E was 1506 reached on the increasing path through D. And the MRT-Red next-hop 1507 towards E is B, since R was reached on the decreasing path through B. 1508 Since E>>D, D will similarly compute its MRT-Blue next-hop to be E, 1509 ensuring that a packet on MRT-Blue will use path C-D-E. B, A and R 1510 will similarly compute the MRT-Red next-hops towards E (which is 1511 ordered less than B, A and R), ensuring that a packet on MRT-Red will 1512 use path C-B-A-R-E. 1514 C can determine the next-hops towards F as well. Since F is not 1515 ordered with respect to C, the MRT-Blue next-hop is the decreasing 1516 one towards R (which is B) and the MRT-Red next-hop is the increasing 1517 one towards R (which is D). Since F>>B, for its MRT-Blue next-hop 1518 towards F, B will use the real increasing next-hop towards F. So a 1519 packet forwarded to B on MRT-Blue will get to F on path C-B-F. 1520 Similarly, D will use the real decreasing next-hop towards F as its 1521 MRT-Red next-hop, a packet on MRT-Red will use path C-D-F. 1523 5.7.4. Generalizing for a graph that isn't 2-connected 1525 If a graph isn't 2-connected, then the basic approach given in 1526 Section 5.7.3 needs some extensions to determine the appropriate MRT 1527 next-hops to use for destinations outside the computing router X's 1528 blocks. In order to find a pair of maximally redundant trees in that 1529 graph we need to find a pair of RTs in each of the blocks (the root 1530 of these trees will be discussed later), and combine them. 1532 When computing the MRT next-hops from a router X, there are three 1533 basic differences: 1535 1. Only nodes in a common block with X should be explored in the 1536 increasing-SPF and decreasing-SPF. 1538 2. Instead of using the GADAG root, X's local-root should be used. 1539 This has the following implications: 1541 A. The links from X's local-root should not be explored. 1543 B. If a node is explored in the outgoing SPF so Y >> X, then X's 1544 MRT-Red next-hops to reach Y uses X's MRT-Red next-hops to 1545 reach X's local-root and if Z << X, then X's MRT-Blue next- 1546 hops to reach Z uses X's MRT-Blue next-hops to reach X's 1547 local-root. 1549 C. If a node W in a common block with X was not reached in the 1550 increasing-SPF or decreasing-SPF, then W is unordered with 1551 respect to X. X's MRT-Blue next-hops to W are X's decreasing 1552 (aka MRT-Red) next-hops to X's local-root. X's MRT-Red next- 1553 hops to W are X's increasing (aka MRT-Blue) next-hops to X's 1554 local-root. 1556 3. For nodes in different blocks, the next-hops must be inherited 1557 via the relevant cut-vertex. 1559 These are all captured in the detailed algorithm given in 1560 Section 5.7.5. 1562 5.7.5. Complete Algorithm to Compute MRT Next-Hops 1564 The complete algorithm to compute MRT Next-Hops for a particular 1565 router X is given in Figure 23. In addition to computing the MRT- 1566 Blue next-hops and MRT-Red next-hops used by X to reach each node Y, 1567 the algorithm also stores an "order_proxy", which is the proper cut- 1568 vertex to reach Y if it is outside the block, and which is used later 1569 in deciding whether the MRT-Blue or the MRT-Red can provide an 1570 acceptable alternate for a particular primary next-hop. 1572 In_Common_Block(x, y) 1573 if ( (x.block_id is y.block_id) 1574 or (x is y.localroot) or (y is x.localroot) ) 1575 return true 1576 return false 1578 Store_Results(y, direction) 1579 if direction is FORWARD 1580 y.higher = true 1581 y.blue_next_hops = y.next_hops 1582 if direction is REVERSE 1583 y.lower = true 1584 y.red_next_hops = y.next_hops 1586 SPF_No_Traverse_Block_Root(spf_root, block_root, direction) 1587 Initialize spf_heap to empty 1588 Initialize nodes' spf_metric to infinity and next_hops to empty 1589 spf_root.spf_metric = 0 1590 insert(spf_heap, spf_root) 1591 while (spf_heap is not empty) 1592 min_node = remove_lowest(spf_heap) 1593 Store_Results(min_node, direction) 1594 if ((min_node is spf_root) or (min_node is not block_root)) 1595 foreach interface intf of min_node 1596 if ( ( ((direction is FORWARD) and intf.OUTGOING) or 1597 ((direction is REVERSE) and intf.INCOMING) ) 1598 and In_Common_Block(spf_root, intf.remote_node) ) 1599 path_metric = min_node.spf_metric + intf.metric 1600 if path_metric < intf.remote_node.spf_metric 1601 intf.remote_node.spf_metric = path_metric 1602 if min_node is spf_root 1603 intf.remote_node.next_hops = make_list(intf) 1604 else 1605 intf.remote_node.next_hops = min_node.next_hops 1606 insert_or_update(spf_heap, intf.remote_node) 1607 else if path_metric == intf.remote_node.spf_metric 1608 if min_node is spf_root 1609 add_to_list(intf.remote_node.next_hops, intf) 1610 else 1611 add_list_to_list(intf.remote_node.next_hops, 1612 min_node.next_hops) 1614 SetEdge(y) 1615 if y.blue_next_hops is empty and y.red_next_hops is empty 1616 SetEdge(y.localroot) 1617 y.blue_next_hops = y.localroot.blue_next_hops 1618 y.red_next_hops = y.localroot.red_next_hops 1619 y.order_proxy = y.localroot.order_proxy 1621 Compute_MRT_NextHops(x, gadag_root) 1622 foreach node y 1623 y.higher = y.lower = false 1624 clear y.red_next_hops and y.blue_next_hops 1625 y.order_proxy = y 1626 SPF_No_Traverse_Block_Root(x, x.localroot, FORWARD) 1627 SPF_No_Traverse_Block_Root(x, x.localroot, REVERSE) 1629 // red and blue next-hops are stored to x.localroot as different 1630 // paths are found via the SPF and reverse-SPF. 1631 // Similarly any nodes whose local-root is x will have their 1632 // red_next_hops and blue_next_hops already set. 1634 // Handle nodes in the same block that aren't the local-root 1635 foreach node y 1636 if (y.IN_MRT_ISLAND and (y is not x) and 1637 (y.block_id is x.block_id) ) 1638 if y.higher 1639 y.red_next_hops = x.localroot.red_next_hops 1640 else if y.lower 1641 y.blue_next_hops = x.localroot.blue_next_hops 1642 else 1643 y.blue_next_hops = x.localroot.red_next_hops 1644 y.red_next_hops = x.localroot.blue_next_hops 1646 // Inherit next-hops and order_proxies to other components 1647 if (x is not gadag_root) and (x.localroot is not gadag_root) 1648 gadag_root.blue_next_hops = x.localroot.blue_next_hops 1649 gadag_root.red_next_hops = x.localroot.red_next_hops 1650 gadag_root.order_proxy = x.localroot 1651 foreach node y 1652 if (y is not gadag_root) and (y is not x) and y.IN_MRT_ISLAND 1653 SetEdge(y) 1655 max_block_id = 0 1656 Assign_Block_ID(gadag_root, max_block_id) 1657 Compute_MRT_NextHops(x, gadag_root) 1659 Figure 23 1661 5.8. Identify MRT alternates 1663 At this point, a computing router S knows its MRT-Blue next-hops and 1664 MRT-Red next-hops for each destination in the MRT Island. The 1665 primary next-hops along the SPT are also known. It remains to 1666 determine for each primary next-hop to a destination D, which of the 1667 MRTs avoids the primary next-hop node F. This computation depends 1668 upon data set in Compute_MRT_NextHops such as each node y's 1669 y.blue_next_hops, y.red_next_hops, y.order_proxy, y.higher, y.lower 1670 and topo_orders. Recall that any router knows only which are the 1671 nodes greater and lesser than itself, but it cannot decide the 1672 relation between any two given nodes easily; that is why we need 1673 topological ordering. 1675 For each primary next-hop node F to each destination D, S can call 1676 Select_Alternates(S, D, F, primary_intf) to determine whether to use 1677 the MRT-Blue or MRT-Red next-hops as the alternate next-hop(s) for 1678 that primary next hop. The algorithm is given in Figure 24 and 1679 discussed afterwards. 1681 Select_Alternates_Internal(D, F, primary_intf, 1682 D_lower, D_higher, D_topo_order): 1683 if D_higher and D_lower 1684 if F.HIGHER and F.LOWER 1685 if F.topo_order < D_topo_order 1686 return USE_RED 1687 else 1688 return USE_BLUE 1689 if F.HIGHER 1690 return USE_RED 1691 if F.LOWER 1692 return USE_BLUE 1693 //F unordered wrt S 1694 return USE_RED_OR_BLUE 1696 else if D_higher 1697 if F.HIGHER and F.LOWER 1698 return USE_BLUE 1699 if F.LOWER 1700 return USE_BLUE 1701 if F.HIGHER 1702 if (F.topo_order > D_topo_order) 1703 return USE_BLUE 1704 if (F.topo_order < D_topo_order) 1705 return USE_RED 1706 //F unordered wrt S 1707 return USE_RED_OR_BLUE 1709 else if D_lower 1710 if F.HIGHER and F.LOWER 1711 return USE_RED 1712 if F.HIGHER 1713 return USE_RED 1714 if F.LOWER 1715 if F.topo_order > D_topo_order 1716 return USE_BLUE 1717 if F.topo_order < D_topo_order 1718 return USE_RED 1719 //F unordered wrt S 1720 return USE_RED_OR_BLUE 1722 else //D is unordered wrt S 1723 if F.HIGHER and F.LOWER 1724 if primary_intf.OUTGOING and primary_intf.INCOMING 1725 return USE_RED_OR_BLUE 1726 if primary_intf.OUTGOING 1727 return USE_BLUE 1728 if primary_intf.INCOMING 1729 return USE_RED 1730 //primary_intf not in GADAG 1731 return USE_RED 1732 if F.LOWER 1733 return USE_RED 1734 if F.HIGHER 1735 return USE_BLUE 1736 //F unordered wrt S 1737 if F.topo_order > D_topo_order: 1738 return USE_BLUE 1739 else: 1740 return USE_RED 1742 Select_Alternates(D, F, primary_intf) 1743 if not In_Common_Block(F, S) 1744 return PRIM_NH_IN_DIFFERENT_BLOCK 1745 if (D is F) or (D.order_proxy is F) 1746 return PRIM_NH_IS_D_OR_OP_FOR_D 1747 D_lower = D.order_proxy.LOWER 1748 D_higher = D.order_proxy.HIGHER 1749 D_topo_order = D.order_proxy.topo_order 1750 return Select_Alternates_Internal(D, F, primary_intf, 1751 D_lower, D_higher, D_topo_order) 1753 Figure 24: Select_Alternates() and Select_Alternates_Internal() 1755 It is useful to first handle the case where where F is also D, or F 1756 is the order proxy for D. In this case, only link protection is 1757 possible. The MRT that doesn't use the failed primary next-hop is 1758 used. If both MRTs use the primary next-hop, then the primary next- 1759 hop must be a cut-link, so either MRT could be used but the set of 1760 MRT next-hops must be pruned to avoid the failed primary next-hop 1761 interface. To indicate this case, Select_Alternates returns 1762 PRIM_NH_IS_D_OR_OP_FOR_D. Explicit pseudo-code to handle the three 1763 sub-cases above is not provided. 1765 The logic behind Select_Alternates_Internal is described in 1766 Figure 25. As an example, consider the first case described in the 1767 table, where the D>>S and D<>S and F<D.topo_order, then either F is ordered lower 1780 than D, or F is unordered with respect to D. Therefore, F is either 1781 on an increasing path from S to D, or it is on neither an increasing 1782 nor a decreasing path from S to D. In either case, it is safe to 1783 take a decreasing path from S to D to avoid F. We know that when S 1784 is R, the decreasing path is the red path, so it is safe to use the 1785 red path to avoid F. 1787 If F>>S or F<>S, we deduce that 1790 F is on an increasing path from S to R. So in order to avoid F, we 1791 use a decreasing path from S to R, which is the red path. Instead, 1792 when F<>S | Blue path: | F>>S | additional | F on an | Use Red | 1806 | and | Increasing | only | criteria | increasing | to avoid | 1807 | D<>S | topo(F)>topo(D) | F on a | Use Blue | 1816 | S is | Blue path: | and | implies that | decreasing | to avoid | 1817 | R | Increasing | F<>D or F??D | path from | F | 1818 | | path to D. | F is | | S to D or | | 1819 | | Red path: | R | | neither | | 1820 | | Decreasing | +-----------------+------------+------------+ 1821 | | path to D. | | topo(F)>S | Blue path: | F<>S | topo(F)>topo(D) | F on | Use Blue | 1840 | | Decreasing | only | implies that | decreasing | to avoid | 1841 | | shortest | | F>>D or F??D | path from | F | 1842 | | path from | | | R to D | | 1843 | | S to R, | | | or | | 1844 | | then | | | neither | | 1845 | | decreasing | +-----------------+------------+------------+ 1846 | | shortest | | topo(F)>S | additional | F on Red | Use Blue | 1854 | | | and | criteria | | to avoid | 1855 | | | F<>S | additional | F on | Use Red | 1867 | only | Increasing | only | criteria | increasing | to avoid | 1868 | | shortest | | not needed | path from | F | 1869 | | path from | | | S to R | | 1870 | | S to R, +------+-----------------+------------+------------+ 1871 | | then | F<topo(D) | F on | Use Blue | 1872 | | increasing | only | implies that | decreasing | to avoid | 1873 | | shortest | | F>>D or F??D | path from | F | 1874 | | path from | | | R to D | | 1875 | | R to D. | | | or | | 1876 | | Red path: | | | neither | | 1877 | | Decreasing | +-----------------+------------+------------+ 1878 | | shortest | | topo(F)>S | additional | F on Blue | Use Red | 1886 | | | and | criteria | | to avoid | 1887 | | | F<>S | additional | F on an | Use Blue | 1904 | | Red path: | only | criteria | increasing | to avoid | 1905 | | Incr. from | | not needed | path from | F | 1906 | | S to first | | | S to L | | 1907 | | node L>>D, | | | | | 1908 | | then decr. | | | | | 1909 | | +------+-----------------+------------+------------+ 1910 | | | F??S | F<-->S link is | | | 1911 | | | | MRT_INELIGIBLE | | | 1912 | | | +-----------------+------------+------------+ 1913 | | | | topo(F)>topo(D) | F on decr. | Use Blue | 1914 | | | | implies that | path from | to avoid | 1915 | | | | F>>D or F??D | L to D or | F | 1916 | | | | | neither | | 1917 | | | +-----------------+------------+------------+ 1918 | | | | topo(F)>S | GADAG link | F on an | Use Blue | 1924 | | | and | direction | incr. path | to avoid | 1925 | | | F<F | from S | F | 1926 | | | F is +-----------------+------------+------------+ 1927 | | | R | GADAG link | F on a | Use Red | 1928 | | | | direction | decr. path | to avoid | 1929 | | | | S<-F | from S | F | 1930 | | | +-----------------+------------+------------+ 1931 | | | | GADAG link | Either F is the order | 1932 | | | | direction | proxy for D (case | 1933 | | | | S<-->F | already handled) or D | 1934 | | | | | is in a different block | 1935 | | | | | from F, in which case | 1936 | | | | | Red or Blue avoids F | 1937 | | | +-----------------+-------------------------+ 1938 | | | | S-F link not | Relies on special | 1939 | | | | in GADAG, | construction of GADAG | 1940 | | | | only when | to demonstrate that | 1941 | | | | S-F link is | using Red avoids F | 1942 | | | | MRT_INELIGIBLE | (see text) | 1943 +------+------------+------+-----------------+-------------------------+ 1945 Figure 25: determining MRT next-hops and alternates based on the 1946 partial order and topological sort relationships between the 1947 source(S), destination(D), primary next-hop(F), and block root(R). 1948 topo(N) indicates the topological sort value of node N. X??Y 1949 indicates that node X is unordered with respect to node Y. It is 1950 assumed that the case where F is D, or where F is the order proxy for 1951 D, has already been handled. 1953 The last case in Figure 25 requires additional explanation. The fact 1954 that the red path from S to D in this case avoids F relies on a 1955 special property of the GADAGs that we have constructed in this 1956 algorithm, a property not shared by all GADAGs in general. When D is 1957 unordered with respect to S, and F is the localroot for S, it can 1958 occur that the link between S and F is not in the GADAG only when 1959 that link has been marked MRT_INELIGIBLE. For an arbitrary GADAG, S 1960 doesn't have enough information based on the computed order 1961 relationships to determine if the red path or blue path will hit F 1962 (which is also the localroot) before hitting K or L, and making it 1963 safely to D. However, the GADAGs that we construct using the 1964 algorithm in this document are not arbitrary GADAGs. They have the 1965 additional property that incoming links to a localroot come from only 1966 one other node in the same block. This is a result of the method of 1967 construction. This additional property guarantees that the red path 1968 from S to D will never pass through the localroot of S. (That would 1969 require the localroot to play the role of L, the first node in the 1970 path ordered higher than D, which would in turn require the localroot 1971 to have two incoming links in the GADAG, which cannot happen.) 1972 Therefore it is safe to use the red path to avoid F with these 1973 specially constructed GADAGs. 1975 As an example of how Select_Alternates_Internal() operates, consider 1976 the ADAG depicted in Figure 26 and first suppose that G is the 1977 source, D is the destination and H is the failed next-hop. Since 1978 D>>G, we need to compare H.topo_order and D.topo_order. Since 1979 D.topo_order>H.topo_order, D must be either higher than H or 1980 unordered with respect to H, so we should select the decreasing path 1981 towards the root. If, however, the destination were instead J, we 1982 must find that H.topo_order>J.topo_order, so we must choose the 1983 increasing Blue next-hop to J, which is I. In the case, when instead 1984 the destination is C, we find that we need to first decrease to avoid 1985 using H, so the Blue, first decreasing then increasing, path is 1986 selected. 1988 [E]<-[D]<-[H]<-[J] 1989 | ^ ^ ^ 1990 V | | | 1991 [R] [C] [G]->[I] 1992 | ^ ^ ^ 1993 V | | | 1994 [A]->[B]->[F]---| 1996 (a)ADAG rooted at R for 1997 a 2-connected graph 1999 Figure 26 2001 5.9. Named Proxy-Nodes 2003 As discussed in Section 11.2 of 2004 [I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT- 2005 Blue and MRT-Red next-hops and MRT-FRR alternates for named proxy- 2006 nodes. An example use case is for a router that is not part of that 2007 local MRT Island, when there is only partial MRT support in the 2008 domain. 2010 5.9.1. Determining Proxy-Node Attachment Routers 2012 Section 11.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] discusses 2013 general considerations for determining the two proxy-node attachment 2014 routers for a given proxy-node, corresponding to a prefix. A router 2015 in the MRT Island that advertises the prefix is a candidate for being 2016 a proxy-node attachment router, with the associated named-proxy-cost 2017 equal to the advertised cost to the prefix. 2019 An Island Border Router (IBR) is a router in the MRT Island that is 2020 connected to an Island Neighbor(IN), which is a router not in the MRT 2021 Island but in the same area/level. An (IBR,IN) pair is a candidate 2022 for being a proxy-node attachment router, if the shortest path from 2023 the IN to the prefix does not enter the MRT Island. A method for 2024 identifying such loop-free Island Neighbors(LFINs) is given below. 2025 The named-proxy-cost assigned to each (IBR, IN) pair is cost(IBR, IN) 2026 + D_opt(IN, prefix). 2028 From the set of prefix-advertising routers and the set of IBRs with 2029 at least one LFIN, the two routers with the lowest named-proxy-cost 2030 are selected. Ties are broken based upon the lowest Router ID. For 2031 ease of discussion, the two selected routers will be referred to as 2032 proxy-node attachment routers. 2034 5.9.2. Computing if an Island Neighbor (IN) is loop-free 2036 As discussed above, the Island Neighbor needs to be loop-free with 2037 respect to the whole MRT Island for the destination. This can be 2038 accomplished by running the usual SPF algorithm while keeping track 2039 of which shortest paths have passed through the MRT island. Pseudo- 2040 code for this is shown in Figure 27. The Island_Marking_SPF() is run 2041 for each IN that needs to be evaluated for the loop-free condition, 2042 with the IN as the spf_root. Whether or not an IN is loop-free with 2043 respect to the MRT island can then be determined by evaluating 2044 node.PATH_HITS_ISLAND for each destination of interest. 2046 Island_Marking_SPF(spf_root) 2047 Initialize spf_heap to empty 2048 Initialize nodes' spf_metric to infinity and next_hops to empty 2049 and PATH_HITS_ISLAND to false 2050 spf_root.spf_metric = 0 2051 insert(spf_heap, spf_root) 2052 while (spf_heap is not empty) 2053 min_node = remove_lowest(spf_heap) 2054 foreach interface intf of min_node 2055 path_metric = min_node.spf_metric + intf.metric 2056 if path_metric < intf.remote_node.spf_metric 2057 intf.remote_node.spf_metric = path_metric 2058 if min_node is spf_root 2059 intf.remote_node.next_hops = make_list(intf) 2060 else 2061 intf.remote_node.next_hops = min_node.next_hops 2062 if intf.remote_node.IN_MRT_ISLAND 2063 intf.remote_node.PATH_HITS_ISLAND = true 2064 else 2065 intf.remote_node.PATH_HITS_ISLAND = 2066 min_node.PATH_HITS_ISLAND 2067 insert_or_update(spf_heap, intf.remote_node) 2068 else if path_metric == intf.remote_node.spf_metric 2069 if min_node is spf_root 2070 add_to_list(intf.remote_node.next_hops, intf) 2071 else 2072 add_list_to_list(intf.remote_node.next_hops, 2073 min_node.next_hops) 2074 if intf.remote_node.IN_MRT_ISLAND 2075 intf.remote_node.PATH_HITS_ISLAND = true 2076 else 2077 intf.remote_node.PATH_HITS_ISLAND = 2078 min_node.PATH_HITS_ISLAND 2080 Figure 27: Island_Marking_SPF for determining if an Island Neighbor 2081 is loop-free 2083 It is also possible that a given prefix is originated by a 2084 combination of non-island routers and island routers. The results of 2085 the Island_Marking_SPF computation can be used to determine if the 2086 shortest path from an IN to reach that prefix hits the MRT island. 2087 The shortest path for the IN to reach prefix P is determined by the 2088 total cost to reach prefix P, which is the sum of the cost for the IN 2089 to reach a prefix-advertising node and the cost with which that node 2090 advertises the prefix. The path with the minimum total cost to 2091 prefix P is chosen. If the prefix-advertising node for that minimum 2092 total cost path has PATH_HITS_ISLAND set to True, then the IN is not 2093 loop-free with respect to the MRT Island for reaching prefix P. If 2094 there multiple minimum total cost paths to reach prefix P, then all 2095 of the prefix-advertising routers involved in the minimum total cost 2096 paths MUST have PATH_HITS_ISLAND set to False for the IN to be 2097 considered loop-free to reach P. 2099 Note that there are other computations that could be used to 2100 determine if paths from a given IN _might_ pass through the MRT 2101 Island for a given prefix or destination. For example, a previous 2102 version of this draft specified running the SPF algorithm on modified 2103 topology which treats the MRT island as a single node (with intra- 2104 island links set to zero cost) in order to provide input to 2105 computations to determine if the path from IN to non-island 2106 destination hits the MRT island in this modified topology. This 2107 computation is enough to guarantee that a path will not hit the MRT 2108 island in the original topology. However, it is possible that a path 2109 which is disqualified for hitting the MRT island in the modified 2110 topology will not actually hit the MRT Island in the original 2111 topology. The algorithm described in Island_Marking_SPF() above does 2112 not modify the original topology, and will only disqualify a path if 2113 the actual path does in fact hit the MRT island. 2115 Since all routers need to come to the same conclusion about which 2116 routers qualify as LFINs, this specification requires that all 2117 routers computing LFINs MUST use an algorithm whose result is 2118 identical to that of the Island_Marking_SPF() in Figure 27. 2120 5.9.3. Computing MRT Next-Hops for Proxy-Nodes 2122 Determining the MRT next-hops for a proxy-node in the degenerate case 2123 where the proxy-node is attached to only one node in the GADAG is 2124 trivial, as all needed information can be derived from that proxy 2125 node attachment router. If there are multiple interfaces connecting 2126 the proxy node to the single proxy node attachment router, then some 2127 can be assigned to MRT-Red and others to MRT_Blue. 2129 Now, consider the proxy-node P that is attached to two proxy-node 2130 attachment routers. The pseudo-code for Select_Proxy_Node_NHs(P,S) 2131 in Figure 28 specifies how a computing-router S MUST compute the MRT 2132 red and blue next-hops to reach proxy-node P. The proxy-node 2133 attachment router with the lower value of mrt_node_id (as defined in 2134 Figure 15) is assigned to X, and the other proxy-node attachment 2135 router is assigned to Y. We will be using the relative order of X,Y, 2136 and S in the partial order defined by the GADAG to determine the MRT 2137 red and blue next-hops to reach P, so we also define A and B as the 2138 order proxies for X and Y, respectively, with respect to S. The 2139 order proxies for all nodes with respect to S were already computed 2140 in Compute_MRT_NextHops(). 2142 def Select_Proxy_Node_NHs(P,S): 2143 if P.pnar1.node.node_id < P.pnar2.node.node_id: 2144 X = P.pnar1.node 2145 Y = P.pnar2.node 2146 else: 2147 X = P.pnar2.node 2148 Y = P.pnar1.node 2149 P.pnar_X = X 2150 P.pnar_Y = Y 2151 A = X.order_proxy 2152 B = Y.order_proxy 2153 if (A is S.localroot 2154 and B is S.localroot): 2155 // case 1.0 2156 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2157 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2158 return 2159 if (A is S.localroot 2160 and B is not S.localroot): 2161 // case 2.0 2162 if B.LOWER: 2163 // case 2.1 2164 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2165 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2166 return 2167 if B.HIGHER: 2168 // case 2.2 2169 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2170 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2171 return 2172 else: 2173 // case 2.3 2174 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2175 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2176 return 2177 if (A is not S.localroot 2178 and B is S.localroot): 2179 // case 3.0 2180 if A.LOWER: 2181 // case 3.1 2182 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2183 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2184 return 2185 if A.HIGHER: 2186 // case 3.2 2187 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2188 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2189 return 2191 else: 2192 // case 3.3 2193 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2194 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2195 return 2196 if (A is not S.localroot 2197 and B is not S.localroot): 2198 // case 4.0 2199 if (S is A.localroot or S is B.localroot): 2200 // case 4.05 2201 if A.topo_order < B.topo_order: 2202 // case 4.05.1 2203 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2204 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2205 return 2206 else: 2207 // case 4.05.2 2208 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2209 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2210 return 2211 if A.LOWER: 2212 // case 4.1 2213 if B.HIGHER: 2214 // case 4.1.1 2215 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2216 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2217 return 2218 if B.LOWER: 2219 // case 4.1.2 2220 if A.topo_order < B.topo_order: 2221 // case 4.1.2.1 2222 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2223 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2224 return 2225 else: 2226 // case 4.1.2.2 2227 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2228 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2229 return 2230 else: 2231 // case 4.1.3 2232 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2233 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2234 return 2235 if A.HIGHER: 2236 // case 4.2 2237 if B.HIGHER: 2238 // case 4.2.1 2239 if A.topo_order < B.topo_order: 2240 // case 4.2.1.1 2241 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2242 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2243 return 2244 else: 2245 // case 4.2.1.2 2246 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2247 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2248 return 2249 if B.LOWER: 2250 // case 4.2.2 2251 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2252 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2253 return 2254 else: 2255 // case 4.2.3 2256 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2257 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2258 return 2259 else: 2260 // case 4.3 2261 if B.LOWER: 2262 // case 4.3.1 2263 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2264 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2265 return 2266 if B.HIGHER: 2267 // case 4.3.2 2268 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2269 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2270 return 2271 else: 2272 // case 4.3.3 2273 if A.topo_order < B.topo_order: 2274 // case 4.3.3.1 2275 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2276 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2277 return 2278 else: 2279 // case 4.3.3.2 2280 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2281 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2282 return 2283 assert(False) 2285 Figure 28: Select_Proxy_Node_NHs() 2287 It is useful to understand up front that the blue next-hops to reach 2288 proxy-node P produced by Select_Proxy_Node_NHs() will always be the 2289 next-hops that reach proxy-node attachment router X, while the red 2290 next-hops to reach proxy-node P will always be the next-hops that 2291 reach proxy-node attachment router Y. This is different from the red 2292 and blue next-hops produced by Compute_MRT_NextHops() where, for 2293 example, blue next-hops to a destination that is ordered with respect 2294 to the source will always correspond to an INCREASING next-hop on the 2295 GADAG. The exact choice of which next-hops chosen by 2296 Select_Proxy_Node_NHs() as the blue next-hops to reach P (which will 2297 necessarily go through X on its way to P) does depend on the GADAG, 2298 but the relationship is more complex than was the case with 2299 Compute_MRT_NextHops(). 2301 There are twenty-one different relative order relationships between 2302 A, B and S that Select_Proxy_Node_NHs() uses to determine red and 2303 blue next-hops to P. This document does not attempt to provide an 2304 exhaustive description of each case considered in 2305 Select_Proxy_Node_NHs(). Instead we provide a high level overview of 2306 the different cases, and we consider a few cases in detail to give an 2307 example of the reasoning that can be used to understand each case. 2309 At the highest level, Select_Proxy_Node_NHs() distinguishes between 2310 four different cases depending on whether or not A or B is the 2311 localroot for S. For example, for case 4.0, neither A nor B is the 2312 localroot for S. Case 4.05 addresses the case where S is the 2313 localroot for either A or B, while cases 4.1, 4.2, and 4.3 address 2314 the cases where A is ordered lower than S, A is ordered higher than 2315 S, or A is unordered with respect to S on the GADAG. In general, 2316 each of these cases is then further subdivided into whether or not B 2317 is ordered lower than S, B is ordered higher than S, or B is 2318 unordered with respect to S. In some cases we also need a further 2319 level of discrimination, where we use the topological sort order of A 2320 with respect to B. 2322 As a detailed example, let's consider case 4.1 and all of its sub- 2323 cases, and explain why the red and blue next-hops to reach P are 2324 chosen as they are in Select_Proxy_Node_NHs(). In case 4.1, neither 2325 A nor B is the localroot for S, S is not the localroot for A or B, 2326 and A is ordered lower than S on the GADAG. In this situation, we 2327 know that the red path to reach X (as computed in 2328 Compute_MRT_NextHops()) will follow DECREASING next-hops towards A, 2329 while the blue path to reach X will follow INCREASING next-hops to 2330 the localroot, and then INCREASING next-hops to A. 2332 Now consider sub-case 4.1.1 where B is ordered higher than S. In 2333 this situation, we know that the blue path to reach Y will follow 2334 INCREASING next-hops towards B, while the red next-hops to reach Y 2335 will follow DECREASING next-hops to the localroot, and then 2336 DECREASING next-hops to B. So to reach X and Y by two disjoint 2337 paths, we can choose the red next-hops to X and the blue next-hops to 2338 Y. We have chosen the convention that blue next-hops to P are those 2339 that pass through X, and red next-hops to P are those that pass 2340 through Y, so we can see that case 4.1.1 produces the desired result. 2341 Choosing blue to X and red to Y does not produce disjoint paths 2342 because the paths intersect at least at the localroot. 2344 Now consider sub-case 4.1.2 where B is ordered lower than S. In this 2345 situation, we know that the red path to reach Y will follow 2346 DECREASING next-hops towards B, while the BLUE next-hops to reach Y 2347 will follow INCREASING next-hops to the localroot, and then 2348 INCREASING next-hops to A. The choice here is more difficult than in 2349 4.1.1 because A and B are both on the DECREASING path from S towards 2350 the localroot. We want to use the direct DECREASING(red) path to the 2351 one that is nearer to S on the GADAG. We get this extra information 2352 by comparing the topological sort order of A and B. If 2353 A.topo_orderB.topo_order, then we use red to X and blue to Y. 2358 Note that when A is unordered with respect to B, the result of 2359 comparing A.topo_order with B.topo_order could be greater than or 2360 less than. In this case, the result doesn't matter because either 2361 choice (red to Y and blue to X or red to X and blue to Y) would work. 2362 What is required is that all nodes in the network give the same 2363 result when comparing A.topo_order with B.topo_order. This is 2364 guarantee by having all nodes run the same algorithm 2365 (Run_Topological_Sort_GADAG()) to compute the topological sort order. 2367 Finally we consider case 4.1.3, where B is unordered with respect to 2368 S. In this case, the blue path to reach Y will follow the DECREASING 2369 next-hops towards the localroot until it reaches some node (K) which 2370 is ordered less than B, after which it will take INCREASING next-hops 2371 to B. The red path to reach Y will follow the INCREASING next-hops 2372 towards the localroot until it reaches some node (L) which is ordered 2373 greater than B, after which it will take DECREASING next-hops to B. 2374 Both K and A are reached by DECREASING from S, but we don't have 2375 information about whether or not that DECREASING path will hit K or A 2376 first. Instead, we do know that the INCREASING path from S will hit 2377 L before reaching A. Therefore, we use the red path to reach Y and 2378 the red path to reach X. 2380 Similar reasoning can be applied to understand the other seventeen 2381 cases used in Select_Proxy_Node_NHs(). However, cases 2.3 and 3.3 2382 deserve special attention because the correctness of the solution for 2383 these two cases relies on a special property of the GADAGs that we 2384 have constructed in this algorithm, a property not shared by all 2385 GADAGs in general. Focusing on case 2.3, we consider the case where 2386 A is the localroot for S, while B is not, and B is unordered with 2387 respect to S. The red path to X DECREASES from S to the localroot A, 2388 while the blue path to X INCREASES from S to the localroot A. The 2389 blue path to Y DECREASES towards the localroot A until it reaches 2390 some node (K) which is ordered less than B, after which the path 2391 INCREASES to B. The red path to Y INCREASES towards the localroot A 2392 until it reaches some node (L) which is ordered greater than B, after 2393 which the path DECREASES to B. It can be shown that for an arbitrary 2394 GADAG, with only the ordering relationships computed so far, we don't 2395 have enough information to choose a pair of paths to reach X and Y 2396 that are guaranteed to be disjoint. In some topologies, A will play 2397 the role of K, the first node ordered less than B on the blue path to 2398 Y. In other topologies, A will play the role of L, the first node 2399 ordered greater than B on the red path to Y. The basic problem is 2400 that we cannot distinguish between these two cases based on the 2401 ordering relationships. 2403 As discussed Section 5.8, the GADAGs that we construct using the 2404 algorithm in this document are not arbitrary GADAGs. They have the 2405 additional property that incoming links to a localroot come from only 2406 one other node in the same block. This is a result of the method of 2407 construction. This additional property guarantees that localroot A 2408 will never play the role of L in the red path to Y, since L must have 2409 at least two incoming links from different nodes in the same block in 2410 the GADAG. This in turn allows Select_Proxy_Node_NHs() to choose the 2411 red path to Y and the red path to X as the disjoint MRT paths to 2412 reach P. 2414 5.9.4. Computing MRT Alternates for Proxy-Nodes 2416 After finding the red and the blue next-hops for a given proxy-node 2417 P, it is necessary to know which one of these to use in the case of 2418 failure. This can be done by Select_Alternates_Proxy_Node(), as 2419 shown in the pseudo-code in Figure 29. 2421 def Select_Alternates_Proxy_Node(P,F,primary_intf): 2422 S = primary_intf.local_node 2423 X = P.pnar_X 2424 Y = P.pnar_Y 2425 A = X.order_proxy 2426 B = Y.order_proxy 2427 if F is A and F is B: 2428 return 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y' 2429 if F is A: 2430 return 'USE_RED' 2432 if F is B: 2433 return 'USE_BLUE' 2435 if not In_Common_Block(A, B): 2436 if In_Common_Block(F, A): 2437 return 'USE_RED' 2438 elif In_Common_Block(F, B): 2439 return 'USE_BLUE' 2440 else: 2441 return 'USE_RED_OR_BLUE' 2442 if (not In_Common_Block(F, A) 2443 and not In_Common_Block(F, A) ): 2444 return 'USE_RED_OR_BLUE' 2446 alt_to_X = Select_Alternates(X, F, primary_intf) 2447 alt_to_Y = Select_Alternates(Y, F, primary_intf) 2449 if (alt_to_X == 'USE_RED_OR_BLUE' 2450 and alt_to_Y == 'USE_RED_OR_BLUE'): 2451 return 'USE_RED_OR_BLUE' 2452 if alt_to_X == 'USE_RED_OR_BLUE': 2453 return 'USE_BLUE' 2454 if alt_to_Y == 'USE_RED_OR_BLUE': 2455 return 'USE_RED' 2457 if (A is S.localroot 2458 and B is S.localroot): 2459 // case 1.0 2460 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 2461 return 'USE_RED_OR_BLUE' 2462 if alt_to_X == 'USE_BLUE': 2463 return 'USE_BLUE' 2464 if alt_to_Y == 'USE_RED': 2465 return 'USE_RED' 2466 assert(False) 2467 if (A is S.localroot 2468 and B is not S.localroot): 2469 // case 2.0 2470 if B.LOWER: 2471 // case 2.1 2472 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 2473 return 'USE_RED_OR_BLUE' 2474 if alt_to_X == 'USE_BLUE': 2475 return 'USE_BLUE' 2476 if alt_to_Y == 'USE_RED': 2477 return 'USE_RED' 2478 assert(False) 2479 if B.HIGHER: 2481 // case 2.2 2482 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 2483 return 'USE_RED_OR_BLUE' 2484 if alt_to_X == 'USE_RED': 2485 return 'USE_BLUE' 2486 if alt_to_Y == 'USE_BLUE': 2487 return 'USE_RED' 2488 assert(False) 2489 else: 2490 // case 2.3 2491 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'): 2492 return 'USE_RED_OR_BLUE' 2493 if alt_to_X == 'USE_RED': 2494 return 'USE_BLUE' 2495 if alt_to_Y == 'USE_RED': 2496 return 'USE_RED' 2497 assert(False) 2498 if (A is not S.localroot 2499 and B is S.localroot): 2500 // case 3.0 2501 if A.LOWER: 2502 // case 3.1 2503 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 2504 return 'USE_RED_OR_BLUE' 2505 if alt_to_X == 'USE_RED': 2506 return 'USE_BLUE' 2507 if alt_to_Y == 'USE_BLUE': 2508 return 'USE_RED' 2509 assert(False) 2510 if A.HIGHER: 2511 // case 3.2 2512 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 2513 return 'USE_RED_OR_BLUE' 2514 if alt_to_X == 'USE_BLUE': 2515 return 'USE_BLUE' 2516 if alt_to_Y == 'USE_RED': 2517 return 'USE_RED' 2518 assert(False) 2519 else: 2520 // case 3.3 2521 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'): 2522 return 'USE_RED_OR_BLUE' 2523 if alt_to_X == 'USE_RED': 2524 return 'USE_BLUE' 2525 if alt_to_Y == 'USE_RED': 2526 return 'USE_RED' 2527 assert(False) 2528 if (A is not S.localroot 2529 and B is not S.localroot): 2530 // case 4.0 2531 if (S is A.localroot or S is B.localroot): 2532 // case 4.05 2533 if A.topo_order < B.topo_order: 2534 // case 4.05.1 2535 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 2536 return 'USE_RED_OR_BLUE' 2537 if alt_to_X == 'USE_BLUE': 2538 return 'USE_BLUE' 2539 if alt_to_Y == 'USE_RED': 2540 return 'USE_RED' 2541 assert(False) 2542 else: 2543 // case 4.05.2 2544 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 2545 return 'USE_RED_OR_BLUE' 2546 if alt_to_X == 'USE_RED': 2547 return 'USE_BLUE' 2548 if alt_to_Y == 'USE_BLUE': 2549 return 'USE_RED' 2550 assert(False) 2551 if A.LOWER: 2552 // case 4.1 2553 if B.HIGHER: 2554 // case 4.1.1 2555 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 2556 return 'USE_RED_OR_BLUE' 2557 if alt_to_X == 'USE_RED': 2558 return 'USE_BLUE' 2559 if alt_to_Y == 'USE_BLUE': 2560 return 'USE_RED' 2561 assert(False) 2562 if B.LOWER: 2563 // case 4.1.2 2564 if A.topo_order < B.topo_order: 2565 // case 4.1.2.1 2566 if (alt_to_X == 'USE_BLUE' 2567 and alt_to_Y == 'USE_RED'): 2568 return 'USE_RED_OR_BLUE' 2569 if alt_to_X == 'USE_BLUE': 2570 return 'USE_BLUE' 2571 if alt_to_Y == 'USE_RED': 2572 return 'USE_RED' 2573 assert(False) 2574 else: 2575 // case 4.1.2.2 2576 if (alt_to_X == 'USE_RED' 2577 and alt_to_Y == 'USE_BLUE'): 2578 return 'USE_RED_OR_BLUE' 2579 if alt_to_X == 'USE_RED': 2580 return 'USE_BLUE' 2581 if alt_to_Y == 'USE_BLUE': 2582 return 'USE_RED' 2583 assert(False) 2584 else: 2585 // case 4.1.3 2586 if (F.LOWER and not F.HIGHER 2587 and F.topo_order > A.topo_order): 2588 // case 4.1.3.1 2589 return 'USE_RED' 2590 else: 2591 // case 4.1.3.2 2592 return 'USE_BLUE' 2593 if A.HIGHER: 2594 // case 4.2 2595 if B.HIGHER: 2596 // case 4.2.1 2597 if A.topo_order < B.topo_order: 2598 // case 4.2.1.1 2599 if (alt_to_X == 'USE_BLUE' 2600 and alt_to_Y == 'USE_RED'): 2601 return 'USE_RED_OR_BLUE' 2602 if alt_to_X == 'USE_BLUE': 2603 return 'USE_BLUE' 2604 if alt_to_Y == 'USE_RED': 2605 return 'USE_RED' 2606 assert(False) 2607 else: 2608 // case 4.2.1.2 2609 if (alt_to_X == 'USE_RED' 2610 and alt_to_Y == 'USE_BLUE'): 2611 return 'USE_RED_OR_BLUE' 2612 if alt_to_X == 'USE_RED': 2613 return 'USE_BLUE' 2614 if alt_to_Y == 'USE_BLUE': 2615 return 'USE_RED' 2616 assert(False) 2617 if B.LOWER: 2618 // case 4.2.2 2619 if (alt_to_X == 'USE_BLUE' 2620 and alt_to_Y == 'USE_RED'): 2621 return 'USE_RED_OR_BLUE' 2622 if alt_to_X == 'USE_BLUE': 2623 return 'USE_BLUE' 2624 if alt_to_Y == 'USE_RED': 2626 return 'USE_RED' 2627 assert(False) 2628 else: 2629 // case 4.2.3 2630 if (F.HIGHER and not F.LOWER 2631 and F.topo_order < A.topo_order): 2632 return 'USE_RED' 2633 else: 2634 return 'USE_BLUE' 2635 else: 2636 // case 4.3 2637 if B.LOWER: 2638 // case 4.3.1 2639 if (F.LOWER and not F.HIGHER 2640 and F.topo_order > B.topo_order): 2641 return 'USE_BLUE' 2642 else: 2643 return 'USE_RED' 2644 if B.HIGHER: 2645 // case 4.3.2 2646 if (F.HIGHER and not F.LOWER 2647 and F.topo_order < B.topo_order): 2648 return 'USE_BLUE' 2649 else: 2650 return 'USE_RED' 2651 else: 2652 // case 4.3.3 2653 if A.topo_order < B.topo_order: 2654 // case 4.3.3.1 2655 if (alt_to_X == 'USE_BLUE' 2656 and alt_to_Y == 'USE_RED'): 2657 return 'USE_RED_OR_BLUE' 2658 if alt_to_X == 'USE_BLUE': 2659 return 'USE_BLUE' 2660 if alt_to_Y == 'USE_RED': 2661 return 'USE_RED' 2662 assert(False) 2663 else: 2664 // case 4.3.3.2 2665 if (alt_to_X == 'USE_RED' 2666 and alt_to_Y == 'USE_BLUE'): 2667 return 'USE_RED_OR_BLUE' 2668 if alt_to_X == 'USE_RED': 2669 return 'USE_BLUE' 2670 if alt_to_Y == 'USE_BLUE': 2671 return 'USE_RED' 2672 assert(False) 2673 assert(False) 2674 Figure 29: Select_Alternates_Proxy_Node() 2676 Select_Alternates_Proxy_Node(P,F,primary_intf) determines whether it 2677 is safe to use the blue path to P (which goes through X), the red 2678 path to P (which goes through Y), or either, when the primary_intf to 2679 node F (and possibly node F) fails. The basic approach is to run 2680 Select_Alternates(X,F,primary_intf) and 2681 Select_Alternates(Y,F,primary_intf) to determine which of the two MRT 2682 paths to X and which of the two MRT paths to Y is safe to use in the 2683 event of the failure of F. In general, we will find that if it is 2684 safe to use a particular path to X or Y when F fails, and 2685 Select_Proxy_Node_NHs() used that path when constructing the red or 2686 blue path to reach P, then it will also be safe to use that path to 2687 reach P when F fails. This rule has one exception which is covered 2688 below. First, we give a concrete example of how 2689 Select_Alternates_Proxy_Node() works in the common case. 2691 The twenty one ordering relationships used in Select_Proxy_Node_NHs() 2692 are repeated in Select_Alternates_Proxy_Node(). We focus on case 2693 4.1.1 to give give a detailed example of the reasoning used in 2694 Select_Alternates_Proxy_Node(). In Select_Proxy_Node_NHs(), we 2695 determined for case 4.1.1 that the red next-hops to X and the blue 2696 next-hops to Y allow us to reach X and Y by disjoint paths, and are 2697 thus the blue and red next-hops to reach P. Therefore, if we run 2698 Select_Alternates(X, F, primary_intf) and we find that it is safe to 2699 USE_RED to reach X, then we also conclude that it is safe to use the 2700 MRT path through X to reach P (the blue path to P) when F fails. 2701 Similarly, if run Select_Alternates(X, F, primary_intf) and we find 2702 that it is safe to USE_BLUE to reach Y, then we also conclude that it 2703 is safe to use the MRT path through Y to reach P (the red path to P) 2704 when F fails. If both of the paths that were used in 2705 Select_Proxy_Node_NHs() to construct the blue and red paths to P are 2706 found to be safe to use to use to reach X and Y, t then we conclude 2707 that we can use either the red or the blue path to P. 2709 This simple reasoning gives the correct answer in most of the cases. 2710 However, additional logic is needed when either A or B (but not both 2711 A and B) is unordered with respect to S. This applies to cases 2712 4.1.3, 4.2.3, 4.3.1, and 4.3.2. Looking at case 4.1.3 in more 2713 detail, A is ordered less than S, but B is unordered with respect to 2714 S. In the discussion of case 4.1.3 above, we saw that 2715 Select_Proxy_Node_NHs() chose the red path to reach Y and the red 2716 path to reach X. We also saw that the red path to reach Y will 2717 follow the INCREASING next-hops towards the localroot until it 2718 reaches some node (L) which is ordered greater than B, after which it 2719 will take DECREASING next-hops to B. The problem is that the red 2720 path to reach P (the one that goes through Y) won't necessarily be 2721 the same as the red path to reach Y. This is because the next-hop 2722 that node L computes for its red next-hop to reach P may be different 2723 from the next-hop it computes for its red next-hop to reach Y. This 2724 is because B is ordered lower than L, so L applies case 4.1.2 of 2725 Select_Proxy_Node_NHs() in order to determine its next-hops to reach 2726 P. If A.topo_orderB.topo_order (case 4.1.2.2), then L will choose 2730 INCREASING next-hops to reach B, which is different from what L 2731 computes in Compute_MRT_NextHops() to reach Y. So testing the safety 2732 of the path for S to reach Y on failure of F as a surrogate for the 2733 safety of using the red path to reach P is not reliable in this case. 2734 It is possible construct topologies where the red path to P hits F 2735 even though the red path to Y does not hit F. 2737 Fortunately there is enough information in the order relationships 2738 that we have already computed to still figure out which alternate to 2739 choose in these four cases. The basic idea is to always choose the 2740 path involving the ordered node, unless that path would hit F. 2741 Returning to case 4.1.3, we see that since A is ordered lower than S, 2742 the only way for S to hit F using a simple DECREASING path to A is 2743 for F to lie between A and S on the GADAG. This scenario is covered 2744 by requiring that F be lower than S (but not also higher than S) and 2745 that F.topo_order>A.topo_order in case 4.1.3.1. 2747 We just need to confirm that it is safe to use the path involving B 2748 in this scenario. In case 4.1.3.1, either F is between A and S on 2749 the GADAG, or F is unordered with respect to A and lies on the 2750 DECREASING path from S to the localroot. When F is between A and S 2751 on the GADAG, then the path through B chosen to avoid A in 2752 Select_Proxy_Node_NHs() will also avoid F. When F is unordered with 2753 respect to A and lies on the DECREASING path from S to the localroot, 2754 then we consider two cases. Either F.topo_orderB.topo_order. In the first case, since 2756 F.topo_orderA.topo_order, it must be 2757 the case that A.topo_orderB.topo_order, the only way for the path involving B to 2761 hit F is if it DECREASES from L to B through F , ie. it must be that 2762 L>>F>>B. However, since S>>F, this would imply that S>>B. However, 2763 we know that S is unordered with respect to B, so the second case 2764 cannot occur. So we have demonstrated that the red path to P (which 2765 goes via B and Y) is safe to use under the conditions of 4.1.3.1. 2766 Similar reasoning can be applied to the other three special cases 2767 where either A or B is unordered with respect to S. 2769 6. MRT Lowpoint Algorithm: Next-hop conformance 2771 This specification defines the MRT Lowpoint Algorithm, which include 2772 the construction of a common GADAG and the computation of MRT-Red and 2773 MRT-Blue next-hops to each node in the graph. An implementation MAY 2774 select any subset of next-hops for MRT-Red and MRT-Blue that respect 2775 the available nodes that are described in Section 5.7 for each of the 2776 MRT-Red and MRT-Blue and the selected next-hops are further along in 2777 the interval of allowed nodes towards the destination. 2779 For example, the MRT-Blue next-hops used when the destination Y >> X, 2780 the computing router, MUST be one or more nodes, T, whose topo_order 2781 is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y 2782 is T. Similarly, the MRT-Red next-hops MUST be have a topo_order in 2783 the interval [R-small.topo_order, X.topo_order] or [Y.topo_order, 2784 R-big.topo_order]. 2786 Implementations SHOULD implement the Select_Alternates() function to 2787 pick an MRT-FRR alternate. 2789 7. Broadcast interfaces 2791 When broadcast interfaces are used to connect nodes, the broadcast 2792 network MUST be represented as a pseudonode, where each real node 2793 connects to the pseudonode. The interface metric in the direction 2794 from real node to pseudonode is the non-zero interface metric, while 2795 the interface metric in the direction from the pseudonode to the real 2796 node is set to zero. This is consistent with the way that broadcast 2797 interfaces are represented as pseudonodes in IS-IS and OSPF. 2799 Pseudonodes MUST be treated as equivalent to real nodes in the 2800 network graph used in the MRT algorithm with a few exceptions 2801 detailed below. 2803 The pseudonodes MUST be included in the computation of the GADAG. 2804 The neighbors of the pseudonode need to know the mrt_node_id of the 2805 pseudonode in order to consistently order interfaces, which is needed 2806 to compute the GADAG. The mrt_node_id for IS-IS is the 7 octet 2807 neighbor system ID and pseudonode number in TLV #22 or TLV#222. The 2808 mrt_node_id for OSPFv2 is the 4 octet interface address of the 2809 Designated Router found in the Link ID field for the link type 2 2810 (transit network) in the Router-LSA. The mrt_node_id for OSPFv3 is 2811 the 4 octet interface address of the Designated Router found in the 2812 Neighbor Interface ID field for the link type 2 (transit network) in 2813 the Router-LSA. pseudonodes MUST NOT be considered as candidates for 2814 GADAG root selection. Note that this is different from the Neighbor 2815 Router ID field used for the mrt_node_id for point-to-point links in 2816 OSPFv3 Router-LSAs given in Figure 15. 2818 Pseudonodes MUST NOT be considered as candidates for selection as 2819 GADAG root. This rule is intended to result in a more stable 2820 network- wide selection of GADAG root by removing the possibility 2821 that the change of Designated Router or Designated Intermediate 2822 System on a broadcast network can result in a change of GADAG root. 2824 7.1. Computing MRT next-hops on broadcast networks 2826 The pseudonode does not correspond to an real node, so it is not 2827 actually involved in forwarding. A real node on a broadcast network 2828 cannot simply forward traffic to the broadcast network. It must 2829 specify another real node on the broadcast network as the next-hop. 2830 On a network graph where a broadcast network is represented by a 2831 pseudonode, this means that if a real node determines that the next- 2832 hop to reach a given destination is a pseudonode, it must also 2833 determine the next-next-hop for that destination in the network 2834 graph, which corresponds to a real node attached to the broadcast 2835 network. 2837 It is interesting to note that this issue is not unique to the MRT 2838 algorithm, but is also encountered in normal SPF computations for 2839 IGPs. Section 16.1.1 of [RFC2328] describes how this is done for 2840 OSPF. As OSPF runs Dijkstra's algorithm, whenever a shorter path is 2841 found reach a real destination node, and the shorter path is one hop 2842 from the computing routing, and that one hop is a pseudonode, then 2843 the next-hop for that destination is taken from the interface IP 2844 address in the Router-LSA correspond to the link to the real 2845 destination node 2847 For IS-IS, in the example pseudo-code implementation of Dijkstra's 2848 algorithm in Annex C of [ISO10589-Second-Edition] whenever the 2849 algorithm encounters an adjacency from a real node to a pseudonode, 2850 it gets converted to a set of adjacencies from the real node to the 2851 neighbors of the pseudonode. In this way, the computed next-hops 2852 point all the way to the real node, and not the pseudonode. 2854 We could avoid the problem of determining next-hops across 2855 pseudonodes in MRT by converting the pseudonode representation of 2856 broadcast networks to a full mesh of links between real nodes on the 2857 same network. However, if we make that conversion before computing 2858 the GADAG, we lose information about which links actually correspond 2859 to a single physical interface into the broadcast network. This 2860 could result computing red and blue next-hops that use the same 2861 broadcast interface, in which case neither the red nor the blue next- 2862 hop would be usable as an alternate on failure of the broadcast 2863 interface. 2865 Instead, we take the following approach, which maintains the property 2866 that either the red and blue next-hop will avoid the broadcast 2867 network, if topologically allowed. We run the MRT algorithm treating 2868 the pseudonodes as equivalent to real nodes in the network graph, 2869 with the exceptions noted above. In addition to running the MRT 2870 algorithm from the point of view of itself, a computing router 2871 connected to a pseudonode MUST also run the MRT algorithm from the 2872 point of view of each of its pseudonode neighbors. For example, if a 2873 computing router S determines that its MRT red next-hop to reach a 2874 destination D is a pseudonode P, S looks at its MRT algorithm 2875 computation from P's point of view to determine P's red next-hop to 2876 reach D, say interface 1 on node X. S now knows that its real red 2877 next-hop to reach D is interface 1 on node X on the broadcast network 2878 represented by P, and can install the corresponding entry in its FIB. 2880 7.2. Using MRT next-hops as alternates in the event of failures on 2881 broadcast networks 2883 In the previous section, we specified how to compute MRT next-hops 2884 when broadcast networks are involved. In this section, we discuss 2885 how a PLR can use those MRT next-hops in the event of failures 2886 involving broadcast networks. 2888 A PLR attached to a broadcast network running only OSPF or IS-IS with 2889 large Hello intervals has limited ability to quickly detect failures 2890 on a broadcast network. The only failure mode that can be quickly 2891 detected is the failure of the physical interface connecting the PLR 2892 to the broadcast network. For the failure of the interface 2893 connecting the PLR to the broadcast network, the alternate that 2894 avoids the broadcast network can be computed by using the broadcast 2895 network pseudonode as F, the primary next-hop node, in 2896 Select_Alternates(). This will choose an alternate path that avoids 2897 the broadcast network. However, the alternate path will not 2898 necessarily avoid all of the real nodes connected to the broadcast 2899 network. This is because we have used the pseudonode to represent 2900 the broadcast network. And we have enforced the node-protecting 2901 property of MRT on the pseudonode to provide protection against 2902 failure of the broadcast network, not the real next-hop nodes on the 2903 broadcast network. This is the best that we can hope to do if 2904 failure of the broadcast interface is the only failure mode that the 2905 PLR can respond to. 2907 We can improve on this if the PLR also has the ability to quickly 2908 detect a lack of connectivity across the broadcast network to a given 2909 IP-layer node. This can be accomplished by running BFD between all 2910 pairs of IGP neighbors on the broadcast network. Note that in the 2911 case of OSPF, this would require establishing BFD sessions between 2912 all pairs of neighbors in the 2-WAY state. When the PLR can quickly 2913 detect the failure of a particular next-hop across a broadcast 2914 network, then the PLR can be more selective in its choice of 2915 alternates. For example, when the PLR observes that connectivity to 2916 an IP-layer node on a broadcast network has failed, the PLR may 2917 choose to still use the broadcast network to reach other IP-layer 2918 nodes which are still reachable. Or if the PLR observes that 2919 connectivity has failed to several IP-layer nodes on the same 2920 broadcast network, it may choose to treat the entire broadcast 2921 network as failed. The choice of MRT alternates by a PLR for a 2922 particular set of failure conditions is a local decision, since it 2923 does not require coordination with other nodes. 2925 8. Python Implementation of MRT Lowpoint Algorithm 2927 Below is Python code implementing the MRT Lowpoint algorithm 2928 specified in this document. In order to avoid the page breaks in the 2929 .txt version of the draft, one can cut and paste the Python code from 2930 the .xml version. The code is also posted on Github. 2932 While this Python code is believed to correctly implement the pseudo- 2933 code description of the algorithm, in the event of a difference, the 2934 pseudo-code description should be considered normative. 2936 2937 # This program has been tested to run on Python 2.6 and 2.7 2938 # (specifically Python 2.6.6 and 2.7.8 were tested). 2939 # The program has known incompatibilities with Python 3.X. 2941 # When executed, this program will generate a text file describing 2942 # an example topology. It then reads that text file back in as input 2943 # to create the example topology, and runs the MRT algorithm.This 2944 # was done to simplify the inclusion of the program as a single text 2945 # file that can be extracted from the IETF draft. 2947 # The output of the program is four text files containing a description 2948 # of the GADAG, the blue and red MRTs for all destinations, and the 2949 # MRT alternates for all failures. 2951 import random 2952 import os.path 2953 import heapq 2955 # simple Class definitions allow structure-like dot notation for 2956 # variables and a convenient place to initialize those variables. 2957 class Topology: 2958 def __init__(self): 2959 self.gadag_root = None 2960 self.node_list = [] 2961 self.node_dict = {} 2962 self.test_gr = None 2963 self.island_node_list_for_test_gr = [] 2964 self.stored_named_proxy_dict = {} 2965 self.init_new_computing_router() 2966 def init_new_computing_router(self): 2967 self.island_node_list = [] 2968 self.named_proxy_dict = {} 2970 class Node: 2971 def __init__(self): 2972 self.node_id = None 2973 self.intf_list = [] 2974 self.profile_id_list = [0] 2975 self.GR_sel_priority = 128 2976 self.blue_next_hops_dict = {} 2977 self.red_next_hops_dict = {} 2978 self.blue_to_green_nh_dict = {} 2979 self.red_to_green_nh_dict = {} 2980 self.prefix_cost_dict = {} 2981 self.pnh_dict = {} 2982 self.alt_dict = {} 2983 self.init_new_computing_router() 2984 def init_new_computing_router(self): 2985 self.island_intf_list = [] 2986 self.IN_MRT_ISLAND = False 2987 self.IN_GADAG = False 2988 self.dfs_number = None 2989 self.dfs_parent = None 2990 self.dfs_parent_intf = None 2991 self.dfs_child_list = [] 2992 self.lowpoint_number = None 2993 self.lowpoint_parent = None 2994 self.lowpoint_parent_intf = None 2995 self.localroot = None 2996 self.block_id = None 2997 self.IS_CUT_VERTEX = False 2998 self.blue_next_hops = [] 2999 self.red_next_hops = [] 3000 self.primary_next_hops = [] 3001 self.alt_list = [] 3003 class Interface: 3004 def __init__(self): 3005 self.metric = None 3006 self.area = None 3007 self.MRT_INELIGIBLE = False 3008 self.IGP_EXCLUDED = False 3009 self.SIMULATION_OUTGOING = False 3010 self.init_new_computing_router() 3011 def init_new_computing_router(self): 3012 self.UNDIRECTED = True 3013 self.INCOMING = False 3014 self.OUTGOING = False 3015 self.INCOMING_STORED = False 3016 self.OUTGOING_STORED = False 3017 self.IN_MRT_ISLAND = False 3018 self.PROCESSED = False 3020 class Bundle: 3021 def __init__(self): 3022 self.UNDIRECTED = True 3023 self.OUTGOING = False 3024 self.INCOMING = False 3026 class Alternate: 3027 def __init__(self): 3028 self.failed_intf = None 3029 self.red_or_blue = None 3030 self.nh_list = [] 3031 self.fec = 'NO_ALTERNATE' 3032 self.prot = 'NO_PROTECTION' 3033 self.info = 'NONE' 3035 class Proxy_Node_Attachment_Router: 3036 def __init__(self): 3037 self.prefix = None 3038 self.node = None 3039 self.named_proxy_cost = None 3040 self.min_lfin = None 3041 self.nh_intf_list = [] 3043 class Named_Proxy_Node: 3044 def __init__(self): 3045 self.node_id = None #this is the prefix_id 3046 self.node_prefix_cost_list = [] 3047 self.lfin_list = [] 3048 self.pnar1 = None 3049 self.pnar2 = None 3050 self.pnar_X = None 3051 self.pnar_Y = None 3052 self.blue_next_hops = [] 3053 self.red_next_hops = [] 3054 self.primary_next_hops = [] 3055 self.blue_next_hops_dict = {} 3056 self.red_next_hops_dict = {} 3057 self.pnh_dict = {} 3058 self.alt_dict = {} 3060 def Interface_Compare(intf_a, intf_b): 3061 if intf_a.metric < intf_b.metric: 3062 return -1 3063 if intf_b.metric < intf_a.metric: 3064 return 1 3065 if intf_a.remote_node.node_id < intf_b.remote_node.node_id: 3066 return -1 3067 if intf_b.remote_node.node_id < intf_a.remote_node.node_id: 3068 return 1 3069 return 0 3071 def Sort_Interfaces(topo): 3072 for node in topo.island_node_list: 3073 node.island_intf_list.sort(Interface_Compare) 3075 def Reset_Computed_Node_and_Intf_Values(topo): 3076 topo.init_new_computing_router() 3077 for node in topo.node_list: 3078 node.init_new_computing_router() 3079 for intf in node.intf_list: 3080 intf.init_new_computing_router() 3082 # This function takes a file with links represented by 2-digit 3083 # numbers in the format: 3084 # 01,05,10 3085 # 05,02,30 3086 # 02,01,15 3087 # which represents a triangle topology with nodes 01, 05, and 02 3088 # and symmetric metrics of 10, 30, and 15. 3090 # Inclusion of a fourth column makes the metrics for the link 3091 # asymmetric. An entry of: 3092 # 02,07,10,15 3093 # creates a link from node 02 to 07 with metrics 10 and 15. 3094 def Create_Topology_From_File(filename): 3095 topo = Topology() 3096 node_id_set= set() 3097 cols_list = [] 3098 # on first pass just create nodes 3099 with open(filename + '.csv') as topo_file: 3100 for line in topo_file: 3101 line = line.rstrip('\r\n') 3102 cols=line.split(',') 3103 cols_list.append(cols) 3104 nodea_node_id = int(cols[0]) 3105 nodeb_node_id = int(cols[1]) 3106 if (nodea_node_id > 999 or nodeb_node_id > 999): 3107 print("node_id must be between 0 and 999.") 3108 print("exiting.") 3109 exit() 3110 node_id_set.add(nodea_node_id) 3111 node_id_set.add(nodeb_node_id) 3112 for node_id in node_id_set: 3113 node = Node() 3114 node.node_id = node_id 3115 topo.node_list.append(node) 3116 topo.node_dict[node_id] = node 3117 # on second pass create interfaces 3118 for cols in cols_list: 3119 nodea_node_id = int(cols[0]) 3120 nodeb_node_id = int(cols[1]) 3121 metric = int(cols[2]) 3122 reverse_metric = int(cols[2]) 3123 if len(cols) > 3: 3124 reverse_metric=int(cols[3]) 3125 nodea = topo.node_dict[nodea_node_id] 3126 nodeb = topo.node_dict[nodeb_node_id] 3127 nodea_intf = Interface() 3128 nodea_intf.metric = metric 3129 nodea_intf.area = 0 3130 nodeb_intf = Interface() 3131 nodeb_intf.metric = reverse_metric 3132 nodeb_intf.area = 0 3133 nodea_intf.remote_intf = nodeb_intf 3134 nodeb_intf.remote_intf = nodea_intf 3135 nodea_intf.remote_node = nodeb 3136 nodeb_intf.remote_node = nodea 3137 nodea_intf.local_node = nodea 3138 nodeb_intf.local_node = nodeb 3139 nodea_intf.link_data = len(nodea.intf_list) 3140 nodeb_intf.link_data = len(nodeb.intf_list) 3141 nodea.intf_list.append(nodea_intf) 3142 nodeb.intf_list.append(nodeb_intf) 3143 return topo 3145 def MRT_Island_Identification(topo, computing_rtr, profile_id, area): 3146 if profile_id in computing_rtr.profile_id_list: 3147 computing_rtr.IN_MRT_ISLAND = True 3148 explore_list = [computing_rtr] 3149 else: 3150 return 3151 while explore_list != []: 3152 next_rtr = explore_list.pop() 3153 for intf in next_rtr.intf_list: 3154 if ( (not intf.MRT_INELIGIBLE) 3155 and (not intf.remote_intf.MRT_INELIGIBLE) 3156 and (not intf.IGP_EXCLUDED) and intf.area == area 3157 and (profile_id in intf.remote_node.profile_id_list)): 3158 intf.IN_MRT_ISLAND = True 3159 intf.remote_intf.IN_MRT_ISLAND = True 3160 if (not intf.remote_node.IN_MRT_ISLAND): 3161 intf.remote_node.IN_MRT_ISLAND = True 3162 explore_list.append(intf.remote_node) 3164 def Compute_Island_Node_List_For_Test_GR(topo, test_gr): 3165 Reset_Computed_Node_and_Intf_Values(topo) 3166 topo.test_gr = topo.node_dict[test_gr] 3167 MRT_Island_Identification(topo, topo.test_gr, 0, 0) 3168 for node in topo.node_list: 3169 if node.IN_MRT_ISLAND: 3170 topo.island_node_list_for_test_gr.append(node) 3172 def Set_Island_Intf_and_Node_Lists(topo): 3173 for node in topo.node_list: 3174 if node.IN_MRT_ISLAND: 3175 topo.island_node_list.append(node) 3176 for intf in node.intf_list: 3177 if intf.IN_MRT_ISLAND: 3178 node.island_intf_list.append(intf) 3180 global_dfs_number = None 3182 def Lowpoint_Visit(x, parent, intf_p_to_x): 3183 global global_dfs_number 3184 x.dfs_number = global_dfs_number 3185 x.lowpoint_number = x.dfs_number 3186 global_dfs_number += 1 3187 x.dfs_parent = parent 3188 if intf_p_to_x == None: 3189 x.dfs_parent_intf = None 3190 else: 3191 x.dfs_parent_intf = intf_p_to_x.remote_intf 3192 x.lowpoint_parent = None 3193 if parent != None: 3194 parent.dfs_child_list.append(x) 3195 for intf in x.island_intf_list: 3196 if intf.remote_node.dfs_number == None: 3197 Lowpoint_Visit(intf.remote_node, x, intf) 3198 if intf.remote_node.lowpoint_number < x.lowpoint_number: 3199 x.lowpoint_number = intf.remote_node.lowpoint_number 3200 x.lowpoint_parent = intf.remote_node 3201 x.lowpoint_parent_intf = intf 3202 else: 3203 if intf.remote_node is not parent: 3204 if intf.remote_node.dfs_number < x.lowpoint_number: 3205 x.lowpoint_number = intf.remote_node.dfs_number 3206 x.lowpoint_parent = intf.remote_node 3207 x.lowpoint_parent_intf = intf 3209 def Run_Lowpoint(topo): 3210 global global_dfs_number 3211 global_dfs_number = 0 3212 Lowpoint_Visit(topo.gadag_root, None, None) 3214 max_block_id = None 3216 def Assign_Block_ID(x, cur_block_id): 3217 global max_block_id 3218 x.block_id = cur_block_id 3219 for c in x.dfs_child_list: 3220 if (c.localroot is x): 3221 max_block_id += 1 3222 Assign_Block_ID(c, max_block_id) 3223 else: 3224 Assign_Block_ID(c, cur_block_id) 3226 def Run_Assign_Block_ID(topo): 3227 global max_block_id 3228 max_block_id = 0 3229 Assign_Block_ID(topo.gadag_root, max_block_id) 3231 def Construct_Ear(x, stack, intf, ear_type): 3232 ear_list = [] 3233 cur_intf = intf 3234 not_done = True 3235 while not_done: 3236 cur_intf.UNDIRECTED = False 3237 cur_intf.OUTGOING = True 3238 cur_intf.remote_intf.UNDIRECTED = False 3239 cur_intf.remote_intf.INCOMING = True 3240 if cur_intf.remote_node.IN_GADAG == False: 3241 cur_intf.remote_node.IN_GADAG = True 3242 ear_list.append(cur_intf.remote_node) 3243 if ear_type == 'CHILD': 3244 cur_intf = cur_intf.remote_node.lowpoint_parent_intf 3245 else: 3246 assert ear_type == 'NEIGHBOR' 3247 cur_intf = cur_intf.remote_node.dfs_parent_intf 3248 else: 3250 not_done = False 3252 if ear_type == 'CHILD' and cur_intf.remote_node is x: 3253 # x is a cut-vertex and the local root for the block 3254 # in which the ear is computed 3255 x.IS_CUT_VERTEX = True 3256 localroot = x 3257 else: 3258 # inherit local root from the end of the ear 3259 localroot = cur_intf.remote_node.localroot 3261 while ear_list != []: 3262 y = ear_list.pop() 3263 y.localroot = localroot 3264 stack.append(y) 3266 def Construct_GADAG_via_Lowpoint(topo): 3267 gadag_root = topo.gadag_root 3268 gadag_root.IN_GADAG = True 3269 gadag_root.localroot = None 3270 stack = [] 3271 stack.append(gadag_root) 3272 while stack != []: 3273 x = stack.pop() 3274 for intf in x.island_intf_list: 3275 if ( intf.remote_node.IN_GADAG == False 3276 and intf.remote_node.dfs_parent is x ): 3277 Construct_Ear(x, stack, intf, 'CHILD' ) 3278 for intf in x.island_intf_list: 3279 if (intf.remote_node.IN_GADAG == False 3280 and intf.remote_node.dfs_parent is not x): 3281 Construct_Ear(x, stack, intf, 'NEIGHBOR') 3283 def Assign_Remaining_Lowpoint_Parents(topo): 3284 for node in topo.island_node_list: 3285 if ( node is not topo.gadag_root 3286 and node.lowpoint_parent == None ): 3287 node.lowpoint_parent = node.dfs_parent 3288 node.lowpoint_parent_intf = node.dfs_parent_intf 3289 node.lowpoint_number = node.dfs_parent.dfs_number 3291 def Add_Undirected_Block_Root_Links(topo): 3292 for node in topo.island_node_list: 3293 if node.IS_CUT_VERTEX or node is topo.gadag_root: 3294 for intf in node.island_intf_list: 3295 if ( intf.remote_node.localroot is not node 3296 or intf.PROCESSED ): 3297 continue 3299 bundle_list = [] 3300 bundle = Bundle() 3301 for intf2 in node.island_intf_list: 3302 if intf2.remote_node is intf.remote_node: 3303 bundle_list.append(intf2) 3304 if not intf2.UNDIRECTED: 3305 bundle.UNDIRECTED = False 3306 if intf2.INCOMING: 3307 bundle.INCOMING = True 3308 if intf2.OUTGOING: 3309 bundle.OUTGOING = True 3310 if bundle.UNDIRECTED: 3311 for intf3 in bundle_list: 3312 intf3.UNDIRECTED = False 3313 intf3.remote_intf.UNDIRECTED = False 3314 intf3.PROCESSED = True 3315 intf3.remote_intf.PROCESSED = True 3316 intf3.OUTGOING = True 3317 intf3.remote_intf.INCOMING = True 3318 else: 3319 if (bundle.OUTGOING and bundle.INCOMING): 3320 for intf3 in bundle_list: 3321 intf3.UNDIRECTED = False 3322 intf3.remote_intf.UNDIRECTED = False 3323 intf3.PROCESSED = True 3324 intf3.remote_intf.PROCESSED = True 3325 intf3.OUTGOING = True 3326 intf3.INCOMING = True 3327 intf3.remote_intf.INCOMING = True 3328 intf3.remote_intf.OUTGOING = True 3329 elif bundle.OUTGOING: 3330 for intf3 in bundle_list: 3331 intf3.UNDIRECTED = False 3332 intf3.remote_intf.UNDIRECTED = False 3333 intf3.PROCESSED = True 3334 intf3.remote_intf.PROCESSED = True 3335 intf3.OUTGOING = True 3336 intf3.remote_intf.INCOMING = True 3337 elif bundle.INCOMING: 3338 for intf3 in bundle_list: 3339 intf3.UNDIRECTED = False 3340 intf3.remote_intf.UNDIRECTED = False 3341 intf3.PROCESSED = True 3342 intf3.remote_intf.PROCESSED = True 3343 intf3.INCOMING = True 3344 intf3.remote_intf.OUTGOING = True 3346 def Modify_Block_Root_Incoming_Links(topo): 3348 for node in topo.island_node_list: 3349 if ( node.IS_CUT_VERTEX == True or node is topo.gadag_root ): 3350 for intf in node.island_intf_list: 3351 if intf.remote_node.localroot is node: 3352 if intf.INCOMING: 3353 intf.INCOMING = False 3354 intf.INCOMING_STORED = True 3355 intf.remote_intf.OUTGOING = False 3356 intf.remote_intf.OUTGOING_STORED = True 3358 def Revert_Block_Root_Incoming_Links(topo): 3359 for node in topo.island_node_list: 3360 if ( node.IS_CUT_VERTEX == True or node is topo.gadag_root ): 3361 for intf in node.island_intf_list: 3362 if intf.remote_node.localroot is node: 3363 if intf.INCOMING_STORED: 3364 intf.INCOMING = True 3365 intf.remote_intf.OUTGOING = True 3366 intf.INCOMING_STORED = False 3367 intf.remote_intf.OUTGOING_STORED = False 3369 def Run_Topological_Sort_GADAG(topo): 3370 Modify_Block_Root_Incoming_Links(topo) 3371 for node in topo.island_node_list: 3372 node.unvisited = 0 3373 for intf in node.island_intf_list: 3374 if (intf.INCOMING == True): 3375 node.unvisited += 1 3376 working_list = [] 3377 topo_order_list = [] 3378 working_list.append(topo.gadag_root) 3379 while working_list != []: 3380 y = working_list.pop(0) 3381 topo_order_list.append(y) 3382 for intf in y.island_intf_list: 3383 if ( intf.OUTGOING == True): 3384 intf.remote_node.unvisited -= 1 3385 if intf.remote_node.unvisited == 0: 3386 working_list.append(intf.remote_node) 3387 next_topo_order = 1 3388 while topo_order_list != []: 3389 y = topo_order_list.pop(0) 3390 y.topo_order = next_topo_order 3391 next_topo_order += 1 3392 Revert_Block_Root_Incoming_Links(topo) 3394 def Set_Other_Undirected_Links_Based_On_Topo_Order(topo): 3395 for node in topo.island_node_list: 3397 for intf in node.island_intf_list: 3398 if intf.UNDIRECTED: 3399 if node.topo_order < intf.remote_node.topo_order: 3400 intf.OUTGOING = True 3401 intf.UNDIRECTED = False 3402 intf.remote_intf.INCOMING = True 3403 intf.remote_intf.UNDIRECTED = False 3404 else: 3405 intf.INCOMING = True 3406 intf.UNDIRECTED = False 3407 intf.remote_intf.OUTGOING = True 3408 intf.remote_intf.UNDIRECTED = False 3410 def Initialize_Temporary_Interface_Flags(topo): 3411 for node in topo.island_node_list: 3412 for intf in node.island_intf_list: 3413 intf.PROCESSED = False 3414 intf.INCOMING_STORED = False 3415 intf.OUTGOING_STORED = False 3417 def Add_Undirected_Links(topo): 3418 Initialize_Temporary_Interface_Flags(topo) 3419 Add_Undirected_Block_Root_Links(topo) 3420 Run_Topological_Sort_GADAG(topo) 3421 Set_Other_Undirected_Links_Based_On_Topo_Order(topo) 3423 def In_Common_Block(x,y): 3424 if ( (x.block_id == y.block_id) 3425 or ( x is y.localroot) or (y is x.localroot) ): 3426 return True 3427 return False 3429 def Copy_List_Items(target_list, source_list): 3430 del target_list[:] # Python idiom to remove all elements of a list 3431 for element in source_list: 3432 target_list.append(element) 3434 def Add_Item_To_List_If_New(target_list, item): 3435 if item not in target_list: 3436 target_list.append(item) 3438 def Store_Results(y, direction): 3439 if direction == 'INCREASING': 3440 y.HIGHER = True 3441 Copy_List_Items(y.blue_next_hops, y.next_hops) 3442 if direction == 'DECREASING': 3443 y.LOWER = True 3444 Copy_List_Items(y.red_next_hops, y.next_hops) 3446 if direction == 'NORMAL_SPF': 3447 y.primary_spf_metric = y.spf_metric 3448 Copy_List_Items(y.primary_next_hops, y.next_hops) 3449 if direction == 'MRT_ISLAND_SPF': 3450 Copy_List_Items(y.mrt_island_next_hops, y.next_hops) 3451 if direction == 'COLLAPSED_SPF': 3452 y.collapsed_metric = y.spf_metric 3453 Copy_List_Items(y.collapsed_next_hops, y.next_hops) 3455 # Note that the Python heapq fucntion allows for duplicate items, 3456 # so we use the 'spf_visited' property to only consider a node 3457 # as min_node the first time it gets removed from the heap. 3458 def SPF_No_Traverse_Block_Root(topo, spf_root, block_root, direction): 3459 spf_heap = [] 3460 for y in topo.island_node_list: 3461 y.spf_metric = 2147483647 # 2^31-1 3462 y.next_hops = [] 3463 y.spf_visited = False 3464 spf_root.spf_metric = 0 3465 heapq.heappush(spf_heap, 3466 (spf_root.spf_metric, spf_root.node_id, spf_root) ) 3467 while spf_heap != []: 3468 #extract third element of tuple popped from heap 3469 min_node = heapq.heappop(spf_heap)[2] 3470 if min_node.spf_visited: 3471 continue 3472 min_node.spf_visited = True 3473 Store_Results(min_node, direction) 3474 if ( (min_node is spf_root) or (min_node is not block_root) ): 3475 for intf in min_node.island_intf_list: 3476 if ( ( (direction == 'INCREASING' and intf.OUTGOING ) 3477 or (direction == 'DECREASING' and intf.INCOMING ) ) 3478 and In_Common_Block(spf_root, intf.remote_node) ) : 3479 path_metric = min_node.spf_metric + intf.metric 3480 if path_metric < intf.remote_node.spf_metric: 3481 intf.remote_node.spf_metric = path_metric 3482 if min_node is spf_root: 3483 intf.remote_node.next_hops = [intf] 3484 else: 3485 Copy_List_Items(intf.remote_node.next_hops, 3486 min_node.next_hops) 3487 heapq.heappush(spf_heap, 3488 ( intf.remote_node.spf_metric, 3489 intf.remote_node.node_id, 3490 intf.remote_node ) ) 3491 elif path_metric == intf.remote_node.spf_metric: 3492 if min_node is spf_root: 3493 Add_Item_To_List_If_New( 3494 intf.remote_node.next_hops,intf) 3495 else: 3496 for nh_intf in min_node.next_hops: 3497 Add_Item_To_List_If_New( 3498 intf.remote_node.next_hops,nh_intf) 3500 def Normal_SPF(topo, spf_root): 3501 spf_heap = [] 3502 for y in topo.node_list: 3503 y.spf_metric = 2147483647 # 2^31-1 as max metric 3504 y.next_hops = [] 3505 y.primary_spf_metric = 2147483647 3506 y.primary_next_hops = [] 3507 y.spf_visited = False 3508 spf_root.spf_metric = 0 3509 heapq.heappush(spf_heap, 3510 (spf_root.spf_metric,spf_root.node_id,spf_root) ) 3511 while spf_heap != []: 3512 #extract third element of tuple popped from heap 3513 min_node = heapq.heappop(spf_heap)[2] 3514 if min_node.spf_visited: 3515 continue 3516 min_node.spf_visited = True 3517 Store_Results(min_node, 'NORMAL_SPF') 3518 for intf in min_node.intf_list: 3519 path_metric = min_node.spf_metric + intf.metric 3520 if path_metric < intf.remote_node.spf_metric: 3521 intf.remote_node.spf_metric = path_metric 3522 if min_node is spf_root: 3523 intf.remote_node.next_hops = [intf] 3524 else: 3525 Copy_List_Items(intf.remote_node.next_hops, 3526 min_node.next_hops) 3527 heapq.heappush(spf_heap, 3528 ( intf.remote_node.spf_metric, 3529 intf.remote_node.node_id, 3530 intf.remote_node ) ) 3531 elif path_metric == intf.remote_node.spf_metric: 3532 if min_node is spf_root: 3533 Add_Item_To_List_If_New( 3534 intf.remote_node.next_hops,intf) 3535 else: 3536 for nh_intf in min_node.next_hops: 3537 Add_Item_To_List_If_New( 3538 intf.remote_node.next_hops,nh_intf) 3540 def Set_Edge(y): 3541 if (y.blue_next_hops == [] and y.red_next_hops == []): 3543 Set_Edge(y.localroot) 3544 Copy_List_Items(y.blue_next_hops,y.localroot.blue_next_hops) 3545 Copy_List_Items(y.red_next_hops ,y.localroot.red_next_hops) 3546 y.order_proxy = y.localroot.order_proxy 3548 def Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,x): 3549 for y in topo.island_node_list: 3550 y.HIGHER = False 3551 y.LOWER = False 3552 y.red_next_hops = [] 3553 y.blue_next_hops = [] 3554 y.order_proxy = y 3555 SPF_No_Traverse_Block_Root(topo, x, x.localroot, 'INCREASING') 3556 SPF_No_Traverse_Block_Root(topo, x, x.localroot, 'DECREASING') 3557 for y in topo.island_node_list: 3558 if ( y is not x and (y.block_id == x.block_id) ): 3559 assert (not ( y is x.localroot or x is y.localroot) ) 3560 assert(not (y.HIGHER and y.LOWER) ) 3561 if y.HIGHER == True: 3562 Copy_List_Items(y.red_next_hops, 3563 x.localroot.red_next_hops) 3564 elif y.LOWER == True: 3565 Copy_List_Items(y.blue_next_hops, 3566 x.localroot.blue_next_hops) 3567 else: 3568 Copy_List_Items(y.blue_next_hops, 3569 x.localroot.red_next_hops) 3570 Copy_List_Items(y.red_next_hops, 3571 x.localroot.blue_next_hops) 3573 # Inherit x's MRT next-hops to reach the GADAG root 3574 # from x's MRT next-hops to reach its local root, 3575 # but first check if x is the gadag_root (in which case 3576 # x does not have a local root) or if x's local root 3577 # is the gadag root (in which case we already have the 3578 # x's MRT next-hops to reach the gadag root) 3579 if x is not topo.gadag_root and x.localroot is not topo.gadag_root: 3580 Copy_List_Items(topo.gadag_root.blue_next_hops, 3581 x.localroot.blue_next_hops) 3582 Copy_List_Items(topo.gadag_root.red_next_hops, 3583 x.localroot.red_next_hops) 3584 topo.gadag_root.order_proxy = x.localroot 3586 # Inherit next-hops and order_proxies to other blocks 3587 for y in topo.island_node_list: 3588 if (y is not topo.gadag_root and y is not x ): 3589 Set_Edge(y) 3591 def Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,x): 3592 for y in topo.island_node_list: 3593 if y is x: 3594 continue 3595 x.blue_next_hops_dict[y.node_id] = [] 3596 x.red_next_hops_dict[y.node_id] = [] 3597 Copy_List_Items(x.blue_next_hops_dict[y.node_id], 3598 y.blue_next_hops) 3599 Copy_List_Items(x.red_next_hops_dict[y.node_id], 3600 y.red_next_hops) 3602 def Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,x): 3603 for y in topo.island_node_list: 3604 x.pnh_dict[y.node_id] = [] 3605 Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops) 3606 x.alt_dict[y.node_id] = [] 3607 Copy_List_Items(x.alt_dict[y.node_id], y.alt_list) 3609 def Store_Primary_NHs_For_One_Source_To_Nodes(topo,x): 3610 for y in topo.node_list: 3611 x.pnh_dict[y.node_id] = [] 3612 Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops) 3614 def Store_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x): 3615 for prefix in topo.named_proxy_dict: 3616 P = topo.named_proxy_dict[prefix] 3617 x.blue_next_hops_dict[P.node_id] = [] 3618 x.red_next_hops_dict[P.node_id] = [] 3619 Copy_List_Items(x.blue_next_hops_dict[P.node_id], 3620 P.blue_next_hops) 3621 Copy_List_Items(x.red_next_hops_dict[P.node_id], 3622 P.red_next_hops) 3624 def Store_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,x): 3625 for prefix in topo.named_proxy_dict: 3626 P = topo.named_proxy_dict[prefix] 3627 x.alt_dict[P.node_id] = [] 3628 Copy_List_Items(x.alt_dict[P.node_id], 3629 P.alt_list) 3631 def Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x): 3632 for prefix in topo.named_proxy_dict: 3633 P = topo.named_proxy_dict[prefix] 3634 x.pnh_dict[P.node_id] = [] 3635 Copy_List_Items(x.pnh_dict[P.node_id], 3636 P.primary_next_hops) 3638 def Select_Alternates_Internal(D, F, primary_intf, 3639 D_lower, D_higher, D_topo_order): 3640 if D_higher and D_lower: 3641 if F.HIGHER and F.LOWER: 3642 if F.topo_order > D_topo_order: 3643 return 'USE_BLUE' 3644 else: 3645 return 'USE_RED' 3646 if F.HIGHER: 3647 return 'USE_RED' 3648 if F.LOWER: 3649 return 'USE_BLUE' 3650 assert(primary_intf.MRT_INELIGIBLE 3651 or primary_intf.remote_intf.MRT_INELIGIBLE) 3652 return 'USE_RED_OR_BLUE' 3653 if D_higher: 3654 if F.HIGHER and F.LOWER: 3655 return 'USE_BLUE' 3656 if F.LOWER: 3657 return 'USE_BLUE' 3658 if F.HIGHER: 3659 if (F.topo_order > D_topo_order): 3660 return 'USE_BLUE' 3661 if (F.topo_order < D_topo_order): 3662 return 'USE_RED' 3663 assert(False) 3664 assert(primary_intf.MRT_INELIGIBLE 3665 or primary_intf.remote_intf.MRT_INELIGIBLE) 3666 return 'USE_RED_OR_BLUE' 3667 if D_lower: 3668 if F.HIGHER and F.LOWER: 3669 return 'USE_RED' 3670 if F.HIGHER: 3671 return 'USE_RED' 3672 if F.LOWER: 3673 if F.topo_order > D_topo_order: 3674 return 'USE_BLUE' 3675 if F.topo_order < D_topo_order: 3676 return 'USE_RED' 3677 assert(False) 3678 assert(primary_intf.MRT_INELIGIBLE 3679 or primary_intf.remote_intf.MRT_INELIGIBLE) 3680 return 'USE_RED_OR_BLUE' 3681 else: # D is unordered wrt S 3682 if F.HIGHER and F.LOWER: 3683 if primary_intf.OUTGOING and primary_intf.INCOMING: 3684 # This can happen when F and D are in different blocks 3685 return 'USE_RED_OR_BLUE' 3686 if primary_intf.OUTGOING: 3688 return 'USE_BLUE' 3689 if primary_intf.INCOMING: 3690 return 'USE_RED' 3691 #This can occur when primary_intf is MRT_INELIGIBLE. 3692 #This appears to be a case where the special 3693 #construction of the GADAG allows us to choose red, 3694 #whereas with an arbitrary GADAG, neither red nor blue 3695 #is guaranteed to work. 3696 assert(primary_intf.MRT_INELIGIBLE 3697 or primary_intf.remote_intf.MRT_INELIGIBLE) 3698 return 'USE_RED' 3699 if F.LOWER: 3700 return 'USE_RED' 3701 if F.HIGHER: 3702 return 'USE_BLUE' 3703 assert(primary_intf.MRT_INELIGIBLE 3704 or primary_intf.remote_intf.MRT_INELIGIBLE) 3705 if F.topo_order > D_topo_order: 3706 return 'USE_BLUE' 3707 else: 3708 return 'USE_RED' 3710 def Select_Alternates(D, F, primary_intf): 3711 S = primary_intf.local_node 3712 if not In_Common_Block(F, S): 3713 return 'PRIM_NH_IN_DIFFERENT_BLOCK' 3714 if (D is F) or (D.order_proxy is F): 3715 return 'PRIM_NH_IS_D_OR_OP_FOR_D' 3716 D_lower = D.order_proxy.LOWER 3717 D_higher = D.order_proxy.HIGHER 3718 D_topo_order = D.order_proxy.topo_order 3719 return Select_Alternates_Internal(D, F, primary_intf, 3720 D_lower, D_higher, D_topo_order) 3722 def Is_Remote_Node_In_NH_List(node, intf_list): 3723 for intf in intf_list: 3724 if node is intf.remote_node: 3725 return True 3726 return False 3728 def Select_Alts_For_One_Src_To_Island_Dests(topo,x): 3729 Normal_SPF(topo, x) 3730 for D in topo.island_node_list: 3731 D.alt_list = [] 3732 if D is x: 3733 continue 3734 for failed_intf in D.primary_next_hops: 3736 alt = Alternate() 3737 alt.failed_intf = failed_intf 3738 cand_alt_list = [] 3739 F = failed_intf.remote_node 3740 #We need to test if F is in the island, as opposed 3741 #to just testing if failed_intf is in island_intf_list, 3742 #because failed_intf could be marked as MRT_INELIGIBLE. 3743 if F in topo.island_node_list: 3744 alt.info = Select_Alternates(D, F, failed_intf) 3745 else: 3746 #The primary next-hop is not in the MRT Island. 3747 #Either red or blue will avoid the primary next-hop, 3748 #because the primary next-hop is not even in the 3749 #GADAG. 3750 alt.info = 'USE_RED_OR_BLUE' 3752 if (alt.info == 'USE_RED_OR_BLUE'): 3753 alt.red_or_blue = random.choice(['USE_RED','USE_BLUE']) 3754 if (alt.info == 'USE_BLUE' 3755 or alt.red_or_blue == 'USE_BLUE'): 3756 Copy_List_Items(alt.nh_list, D.blue_next_hops) 3757 alt.fec = 'BLUE' 3758 alt.prot = 'NODE_PROTECTION' 3759 if (alt.info == 'USE_RED' or alt.red_or_blue == 'USE_RED'): 3760 Copy_List_Items(alt.nh_list, D.red_next_hops) 3761 alt.fec = 'RED' 3762 alt.prot = 'NODE_PROTECTION' 3763 if (alt.info == 'PRIM_NH_IN_DIFFERENT_BLOCK'): 3764 alt.fec = 'NO_ALTERNATE' 3765 alt.prot = 'NO_PROTECTION' 3766 if (alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D'): 3767 if failed_intf.OUTGOING and failed_intf.INCOMING: 3768 # cut-link: if there are parallel cut links, use 3769 # the link(s) with lowest metric that are not 3770 # primary intf or None 3771 cand_alt_list = [None] 3772 min_metric = 2147483647 3773 for intf in x.island_intf_list: 3774 if ( intf is not failed_intf and 3775 (intf.remote_node is 3776 failed_intf.remote_node)): 3777 if intf.metric < min_metric: 3778 cand_alt_list = [intf] 3779 min_metric = intf.metric 3780 elif intf.metric == min_metric: 3781 cand_alt_list.append(intf) 3782 if cand_alt_list != [None]: 3783 alt.fec = 'GREEN' 3784 alt.prot = 'PARALLEL_CUTLINK' 3785 else: 3786 alt.fec = 'NO_ALTERNATE' 3787 alt.prot = 'NO_PROTECTION' 3788 Copy_List_Items(alt.nh_list, cand_alt_list) 3790 # Is_Remote_Node_In_NH_List() is used, as opposed 3791 # to just checking if failed_intf is in D.red_next_hops, 3792 # because failed_intf could be marked as MRT_INELIGIBLE. 3793 elif Is_Remote_Node_In_NH_List(F, D.red_next_hops): 3794 Copy_List_Items(alt.nh_list, D.blue_next_hops) 3795 alt.fec = 'BLUE' 3796 alt.prot = 'LINK_PROTECTION' 3797 elif Is_Remote_Node_In_NH_List(F, D.blue_next_hops): 3798 Copy_List_Items(alt.nh_list, D.red_next_hops) 3799 alt.fec = 'RED' 3800 alt.prot = 'LINK_PROTECTION' 3801 else: 3802 alt.fec = random.choice(['RED','BLUE']) 3803 alt.prot = 'LINK_PROTECTION' 3805 D.alt_list.append(alt) 3807 def Write_GADAG_To_File(topo, file_prefix): 3808 gadag_edge_list = [] 3809 for node in topo.node_list: 3810 for intf in node.intf_list: 3811 if intf.SIMULATION_OUTGOING: 3812 local_node = "%04d" % (intf.local_node.node_id) 3813 remote_node = "%04d" % (intf.remote_node.node_id) 3814 intf_data = "%03d" % (intf.link_data) 3815 edge_string=(local_node+','+remote_node+','+ 3816 intf_data+'\n') 3817 gadag_edge_list.append(edge_string) 3818 gadag_edge_list.sort(); 3819 filename = file_prefix + '_gadag.csv' 3820 with open(filename, 'w') as gadag_file: 3821 gadag_file.write('local_node,'\ 3822 'remote_node,local_intf_link_data\n') 3823 for edge_string in gadag_edge_list: 3824 gadag_file.write(edge_string); 3826 def Write_MRTs_For_All_Dests_To_File(topo, color, file_prefix): 3827 edge_list = [] 3828 for node in topo.island_node_list_for_test_gr: 3829 if color == 'blue': 3830 node_next_hops_dict = node.blue_next_hops_dict 3831 elif color == 'red': 3833 node_next_hops_dict = node.red_next_hops_dict 3834 for dest_node_id in node_next_hops_dict: 3835 for intf in node_next_hops_dict[dest_node_id]: 3836 gadag_root = "%04d" % (topo.gadag_root.node_id) 3837 dest_node = "%04d" % (dest_node_id) 3838 local_node = "%04d" % (intf.local_node.node_id) 3839 remote_node = "%04d" % (intf.remote_node.node_id) 3840 intf_data = "%03d" % (intf.link_data) 3841 edge_string=(gadag_root+','+dest_node+','+local_node+ 3842 ','+remote_node+','+intf_data+'\n') 3843 edge_list.append(edge_string) 3844 edge_list.sort() 3845 filename = file_prefix + '_' + color + '_to_all.csv' 3846 with open(filename, 'w') as mrt_file: 3847 mrt_file.write('gadag_root,dest,'\ 3848 'local_node,remote_node,link_data\n') 3849 for edge_string in edge_list: 3850 mrt_file.write(edge_string); 3852 def Write_Both_MRTs_For_All_Dests_To_File(topo, file_prefix): 3853 Write_MRTs_For_All_Dests_To_File(topo, 'blue', file_prefix) 3854 Write_MRTs_For_All_Dests_To_File(topo, 'red', file_prefix) 3856 def Write_Alternates_For_All_Dests_To_File(topo, file_prefix): 3857 edge_list = [] 3858 for x in topo.island_node_list_for_test_gr: 3859 for dest_node_id in x.alt_dict: 3860 alt_list = x.alt_dict[dest_node_id] 3861 for alt in alt_list: 3862 for alt_intf in alt.nh_list: 3863 gadag_root = "%04d" % (topo.gadag_root.node_id) 3864 dest_node = "%04d" % (dest_node_id) 3865 prim_local_node = \ 3866 "%04d" % (alt.failed_intf.local_node.node_id) 3867 prim_remote_node = \ 3868 "%04d" % (alt.failed_intf.remote_node.node_id) 3869 prim_intf_data = \ 3870 "%03d" % (alt.failed_intf.link_data) 3871 if alt_intf == None: 3872 alt_local_node = "None" 3873 alt_remote_node = "None" 3874 alt_intf_data = "None" 3875 else: 3876 alt_local_node = \ 3877 "%04d" % (alt_intf.local_node.node_id) 3878 alt_remote_node = \ 3879 "%04d" % (alt_intf.remote_node.node_id) 3880 alt_intf_data = \ 3881 "%03d" % (alt_intf.link_data) 3882 edge_string = (gadag_root+','+dest_node+','+ 3883 prim_local_node+','+prim_remote_node+','+ 3884 prim_intf_data+','+alt_local_node+','+ 3885 alt_remote_node+','+alt_intf_data+','+ 3886 alt.fec +'\n') 3887 edge_list.append(edge_string) 3888 edge_list.sort() 3889 filename = file_prefix + '_alts_to_all.csv' 3890 with open(filename, 'w') as alt_file: 3891 alt_file.write('gadag_root,dest,'\ 3892 'prim_nh.local_node,prim_nh.remote_node,'\ 3893 'prim_nh.link_data,alt_nh.local_node,'\ 3894 'alt_nh.remote_node,alt_nh.link_data,'\ 3895 'alt_nh.fec\n') 3896 for edge_string in edge_list: 3897 alt_file.write(edge_string); 3899 def Raise_GADAG_Root_Selection_Priority(topo,node_id): 3900 node = topo.node_dict[node_id] 3901 node.GR_sel_priority = 255 3903 def Lower_GADAG_Root_Selection_Priority(topo,node_id): 3904 node = topo.node_dict[node_id] 3905 node.GR_sel_priority = 128 3907 def GADAG_Root_Compare(node_a, node_b): 3908 if (node_a.GR_sel_priority > node_b.GR_sel_priority): 3909 return 1 3910 elif (node_a.GR_sel_priority < node_b.GR_sel_priority): 3911 return -1 3912 else: 3913 if node_a.node_id > node_b.node_id: 3914 return 1 3915 elif node_a.node_id < node_b.node_id: 3916 return -1 3918 def Set_GADAG_Root(topo,computing_router): 3919 gadag_root_list = [] 3920 for node in topo.island_node_list: 3921 gadag_root_list.append(node) 3922 gadag_root_list.sort(GADAG_Root_Compare) 3923 topo.gadag_root = gadag_root_list.pop() 3925 def Add_Prefix_Advertisements_From_File(topo, filename): 3926 prefix_filename = filename + '.prefix' 3927 cols_list = [] 3928 if not os.path.exists(prefix_filename): 3930 return 3931 with open(prefix_filename) as prefix_file: 3932 for line in prefix_file: 3933 line = line.rstrip('\r\n') 3934 cols=line.split(',') 3935 cols_list.append(cols) 3936 prefix_id = int(cols[0]) 3937 if prefix_id < 2000 or prefix_id >2999: 3938 print('skipping the following line of prefix file') 3939 print('prefix id should be between 2000 and 2999') 3940 print(line) 3941 continue 3942 prefix_node_id = int(cols[1]) 3943 prefix_cost = int(cols[2]) 3944 advertising_node = topo.node_dict[prefix_node_id] 3945 advertising_node.prefix_cost_dict[prefix_id] = prefix_cost 3947 def Add_Prefixes_for_Non_Island_Nodes(topo): 3948 for node in topo.node_list: 3949 if node.IN_MRT_ISLAND: 3950 continue 3951 prefix_id = node.node_id + 1000 3952 node.prefix_cost_dict[prefix_id] = 0 3954 def Add_Profile_IDs_from_File(topo, filename): 3955 profile_filename = filename + '.profile' 3956 for node in topo.node_list: 3957 node.profile_id_list = [] 3958 cols_list = [] 3959 if os.path.exists(profile_filename): 3960 with open(profile_filename) as profile_file: 3961 for line in profile_file: 3962 line = line.rstrip('\r\n') 3963 cols=line.split(',') 3964 cols_list.append(cols) 3965 node_id = int(cols[0]) 3966 profile_id = int(cols[1]) 3967 this_node = topo.node_dict[node_id] 3968 this_node.profile_id_list.append(profile_id) 3969 else: 3970 for node in topo.node_list: 3971 node.profile_id_list = [0] 3973 def Island_Marking_SPF(topo,spf_root): 3974 spf_root.isl_marking_spf_dict = {} 3975 for y in topo.node_list: 3976 y.spf_metric = 2147483647 # 2^31-1 as max metric 3977 y.PATH_HITS_ISLAND = False 3978 y.next_hops = [] 3979 y.spf_visited = False 3980 spf_root.spf_metric = 0 3981 spf_heap = [] 3982 heapq.heappush(spf_heap, 3983 (spf_root.spf_metric,spf_root.node_id,spf_root) ) 3984 while spf_heap != []: 3985 #extract third element of tuple popped from heap 3986 min_node = heapq.heappop(spf_heap)[2] 3987 if min_node.spf_visited: 3988 continue 3989 min_node.spf_visited = True 3990 spf_root.isl_marking_spf_dict[min_node.node_id] = \ 3991 (min_node.spf_metric, min_node.PATH_HITS_ISLAND) 3992 for intf in min_node.intf_list: 3993 path_metric = min_node.spf_metric + intf.metric 3994 if path_metric < intf.remote_node.spf_metric: 3995 intf.remote_node.spf_metric = path_metric 3996 if min_node is spf_root: 3997 intf.remote_node.next_hops = [intf] 3998 else: 3999 Copy_List_Items(intf.remote_node.next_hops, 4000 min_node.next_hops) 4001 if (intf.remote_node.IN_MRT_ISLAND): 4002 intf.remote_node.PATH_HITS_ISLAND = True 4003 else: 4004 intf.remote_node.PATH_HITS_ISLAND = \ 4005 min_node.PATH_HITS_ISLAND 4006 heapq.heappush(spf_heap, 4007 ( intf.remote_node.spf_metric, 4008 intf.remote_node.node_id, 4009 intf.remote_node ) ) 4010 elif path_metric == intf.remote_node.spf_metric: 4011 if min_node is spf_root: 4012 Add_Item_To_List_If_New( 4013 intf.remote_node.next_hops,intf) 4014 else: 4015 for nh_intf in min_node.next_hops: 4016 Add_Item_To_List_If_New( 4017 intf.remote_node.next_hops,nh_intf) 4018 if (intf.remote_node.IN_MRT_ISLAND): 4019 intf.remote_node.PATH_HITS_ISLAND = True 4020 else: 4021 if (intf.remote_node.PATH_HITS_ISLAND 4022 or min_node.PATH_HITS_ISLAND): 4023 intf.remote_node.PATH_HITS_ISLAND = True 4025 def Create_Basic_Named_Proxy_Nodes(topo): 4026 for node in topo.node_list: 4027 for prefix in node.prefix_cost_dict: 4028 prefix_cost = node.prefix_cost_dict[prefix] 4029 if prefix in topo.named_proxy_dict: 4030 P = topo.named_proxy_dict[prefix] 4031 P.node_prefix_cost_list.append((node,prefix_cost)) 4032 else: 4033 P = Named_Proxy_Node() 4034 topo.named_proxy_dict[prefix] = P 4035 P.node_id = prefix 4036 P.node_prefix_cost_list = [(node,prefix_cost)] 4038 def Compute_Loop_Free_Island_Neighbors_For_Each_Prefix(topo): 4039 topo.island_nbr_set = set() 4040 topo.island_border_set = set() 4041 for node in topo.node_list: 4042 if node.IN_MRT_ISLAND: 4043 continue 4044 for intf in node.intf_list: 4045 if intf.remote_node.IN_MRT_ISLAND: 4046 topo.island_nbr_set.add(node) 4047 topo.island_border_set.add(intf.remote_node) 4049 for island_nbr in topo.island_nbr_set: 4050 Island_Marking_SPF(topo,island_nbr) 4052 for prefix in topo.named_proxy_dict: 4053 P = topo.named_proxy_dict[prefix] 4054 P.lfin_list = [] 4055 for island_nbr in topo.island_nbr_set: 4056 min_isl_nbr_to_pref_cost = 2147483647 4057 for (adv_node, prefix_cost) in P.node_prefix_cost_list: 4058 (adv_node_cost, path_hits_island) = \ 4059 island_nbr.isl_marking_spf_dict[adv_node.node_id] 4060 isl_nbr_to_pref_cost = adv_node_cost + prefix_cost 4061 if isl_nbr_to_pref_cost < min_isl_nbr_to_pref_cost: 4062 min_isl_nbr_to_pref_cost = isl_nbr_to_pref_cost 4063 min_path_hits_island = path_hits_island 4064 elif isl_nbr_to_pref_cost == min_isl_nbr_to_pref_cost: 4065 if min_path_hits_island or path_hits_island: 4066 min_path_hits_island = True 4067 if not min_path_hits_island: 4068 P.lfin_list.append( (island_nbr, 4069 min_isl_nbr_to_pref_cost) ) 4071 def Compute_Island_Border_Router_LFIN_Pairs_For_Each_Prefix(topo): 4073 for ibr in topo.island_border_set: 4074 ibr.prefix_lfin_dict = {} 4075 ibr.min_intf_metric_dict = {} 4076 ibr.min_intf_list_dict = {} 4077 ibr.min_intf_list_dict[None] = None 4078 for intf in ibr.intf_list: 4079 if not intf.remote_node in topo.island_nbr_set: 4080 continue 4081 if not intf.remote_node in ibr.min_intf_metric_dict: 4082 ibr.min_intf_metric_dict[intf.remote_node] = \ 4083 intf.metric 4084 ibr.min_intf_list_dict[intf.remote_node] = [intf] 4085 else: 4086 if (intf.metric 4087 < ibr.min_intf_metric_dict[intf.remote_node]): 4088 ibr.min_intf_metric_dict[intf.remote_node] = \ 4089 intf.metric 4090 ibr.min_intf_list_dict[intf.remote_node] = [intf] 4091 elif (intf.metric 4092 < ibr.min_intf_metric_dict[intf.remote_node]): 4093 ibr.min_intf_list_dict[intf.remote_node].\ 4094 append(intf) 4096 for prefix in topo.named_proxy_dict: 4097 P = topo.named_proxy_dict[prefix] 4098 for ibr in topo.island_border_set: 4099 min_ibr_lfin_pref_cost = 2147483647 4100 min_lfin = None 4101 for (lfin, lfin_to_pref_cost) in P.lfin_list: 4102 if not lfin in ibr.min_intf_metric_dict: 4103 continue 4104 ibr_lfin_pref_cost = \ 4105 ibr.min_intf_metric_dict[lfin] + lfin_to_pref_cost 4106 if ibr_lfin_pref_cost < min_ibr_lfin_pref_cost: 4107 min_ibr_lfin_pref_cost = ibr_lfin_pref_cost 4108 min_lfin = lfin 4109 ibr.prefix_lfin_dict[prefix] = (min_lfin, 4110 min_ibr_lfin_pref_cost, 4111 ibr.min_intf_list_dict[min_lfin]) 4113 def Proxy_Node_Att_Router_Compare(pnar_a, pnar_b): 4114 if pnar_a.named_proxy_cost < pnar_b.named_proxy_cost: 4115 return -1 4116 if pnar_b.named_proxy_cost < pnar_a.named_proxy_cost: 4117 return 1 4118 if pnar_a.node.node_id < pnar_b.node.node_id: 4119 return -1 4120 if pnar_b.node.node_id < pnar_a.node.node_id: 4122 return 1 4123 if pnar_a.min_lfin == None: 4124 return -1 4125 if pnar_b.min_lfin == None: 4126 return 1 4128 def Choose_Proxy_Node_Attachment_Routers(topo): 4129 for prefix in topo.named_proxy_dict: 4130 P = topo.named_proxy_dict[prefix] 4131 pnar_candidate_list = [] 4132 for (node, prefix_cost) in P.node_prefix_cost_list: 4133 if not node.IN_MRT_ISLAND: 4134 continue 4135 pnar = Proxy_Node_Attachment_Router() 4136 pnar.prefix = prefix 4137 pnar.named_proxy_cost = prefix_cost 4138 pnar.node = node 4139 pnar_candidate_list.append(pnar) 4140 for ibr in topo.island_border_set: 4141 (min_lfin, prefix_cost, min_intf_list) = \ 4142 ibr.prefix_lfin_dict[prefix] 4143 if min_lfin == None: 4144 continue 4145 pnar = Proxy_Node_Attachment_Router() 4146 pnar.named_proxy_cost = prefix_cost 4147 pnar.node = ibr 4148 pnar.min_lfin = min_lfin 4149 pnar.nh_intf_list = min_intf_list 4150 pnar_candidate_list.append(pnar) 4151 pnar_candidate_list.sort(cmp=Proxy_Node_Att_Router_Compare) 4152 #pop first element from list 4153 first_pnar = pnar_candidate_list.pop(0) 4154 second_pnar = None 4155 for next_pnar in pnar_candidate_list: 4156 if next_pnar.node is first_pnar.node: 4157 continue 4158 second_pnar = next_pnar 4159 break 4161 P.pnar1 = first_pnar 4162 P.pnar2 = second_pnar 4164 def Attach_Named_Proxy_Nodes(topo): 4165 Compute_Loop_Free_Island_Neighbors_For_Each_Prefix(topo) 4166 Compute_Island_Border_Router_LFIN_Pairs_For_Each_Prefix(topo) 4167 Choose_Proxy_Node_Attachment_Routers(topo) 4169 def Select_Proxy_Node_NHs(P,S): 4171 if P.pnar1.node.node_id < P.pnar2.node.node_id: 4172 X = P.pnar1.node 4173 Y = P.pnar2.node 4174 else: 4175 X = P.pnar2.node 4176 Y = P.pnar1.node 4177 P.pnar_X = X 4178 P.pnar_Y = Y 4179 A = X.order_proxy 4180 B = Y.order_proxy 4181 if (A is S.localroot 4182 and B is S.localroot): 4183 #print("1.0") 4184 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4185 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4186 return 4187 if (A is S.localroot 4188 and B is not S.localroot): 4189 #print("2.0") 4190 if B.LOWER: 4191 #print("2.1") 4192 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4193 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4194 return 4195 if B.HIGHER: 4196 #print("2.2") 4197 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4198 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4199 return 4200 else: 4201 #print("2.3") 4202 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4203 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4204 return 4205 if (A is not S.localroot 4206 and B is S.localroot): 4207 #print("3.0") 4208 if A.LOWER: 4209 #print("3.1") 4210 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4211 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4212 return 4213 if A.HIGHER: 4214 #print("3.2") 4215 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4216 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4217 return 4218 else: 4220 #print("3.3") 4221 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4222 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4223 return 4224 if (A is not S.localroot 4225 and B is not S.localroot): 4226 #print("4.0") 4227 if (S is A.localroot or S is B.localroot): 4228 #print("4.05") 4229 if A.topo_order < B.topo_order: 4230 #print("4.05.1") 4231 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4232 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4233 return 4234 else: 4235 #print("4.05.2") 4236 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4237 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4238 return 4239 if A.LOWER: 4240 #print("4.1") 4241 if B.HIGHER: 4242 #print("4.1.1") 4243 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4244 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4245 return 4246 if B.LOWER: 4247 #print("4.1.2") 4248 if A.topo_order < B.topo_order: 4249 #print("4.1.2.1") 4250 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4251 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4252 return 4253 else: 4254 #print("4.1.2.2") 4255 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4256 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4257 return 4258 else: 4259 #print("4.1.3") 4260 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4261 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4262 return 4263 if A.HIGHER: 4264 #print("4.2") 4265 if B.HIGHER: 4266 #print("4.2.1") 4267 if A.topo_order < B.topo_order: 4269 #print("4.2.1.1") 4270 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4271 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4272 return 4273 else: 4274 #print("4.2.1.2") 4275 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4276 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4277 return 4278 if B.LOWER: 4279 #print("4.2.2") 4280 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4281 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4282 return 4283 else: 4284 #print("4.2.3") 4285 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4286 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4287 return 4288 else: 4289 #print("4.3") 4290 if B.LOWER: 4291 #print("4.3.1") 4292 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4293 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4294 return 4295 if B.HIGHER: 4296 #print("4.3.2") 4297 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4298 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4299 return 4300 else: 4301 #print("4.3.3") 4302 if A.topo_order < B.topo_order: 4303 #print("4.3.3.1") 4304 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4305 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4306 return 4307 else: 4308 #print("4.3.3.2") 4309 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4310 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4311 return 4312 assert(False) 4314 def Compute_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,S): 4315 for prefix in topo.named_proxy_dict: 4316 P = topo.named_proxy_dict[prefix] 4317 if P.pnar2 == None: 4318 if S is P.pnar1.node: 4319 # set the MRT next-hops for the PNAR to 4320 # reach the LFIN and change FEC to green 4321 Copy_List_Items(P.blue_next_hops, 4322 P.pnar1.nh_intf_list) 4323 S.blue_to_green_nh_dict[P.node_id] = True 4324 Copy_List_Items(P.red_next_hops, 4325 P.pnar1.nh_intf_list) 4326 S.red_to_green_nh_dict[P.node_id] = True 4327 else: 4328 # inherit MRT NHs for P from pnar1 4329 Copy_List_Items(P.blue_next_hops, 4330 P.pnar1.node.blue_next_hops) 4331 Copy_List_Items(P.red_next_hops, 4332 P.pnar1.node.red_next_hops) 4333 else: 4334 Select_Proxy_Node_NHs(P,S) 4335 # set the MRT next-hops for the PNAR to reach the LFIN 4336 # and change FEC to green rely on the red or blue 4337 # next-hops being empty to figure out which one needs 4338 # to point to the LFIN. 4339 if S is P.pnar1.node: 4340 this_pnar = P.pnar1 4341 elif S is P.pnar2.node: 4342 this_pnar = P.pnar2 4343 else: 4344 continue 4345 if P.blue_next_hops == []: 4346 Copy_List_Items(P.blue_next_hops, 4347 this_pnar.nh_intf_list) 4348 S.blue_to_green_nh_dict[P.node_id] = True 4349 if P.red_next_hops == []: 4350 Copy_List_Items(P.red_next_hops, 4351 this_pnar.nh_intf_list) 4352 S.red_to_green_nh_dict[P.node_id] = True 4354 def Select_Alternates_Proxy_Node(P,F,primary_intf): 4355 S = primary_intf.local_node 4356 X = P.pnar_X 4357 Y = P.pnar_Y 4358 A = X.order_proxy 4359 B = Y.order_proxy 4360 if F is A and F is B: 4361 return 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y' 4362 if F is A: 4363 return 'USE_RED' 4364 if F is B: 4366 return 'USE_BLUE' 4368 if not In_Common_Block(A, B): 4369 if In_Common_Block(F, A): 4370 return 'USE_RED' 4371 elif In_Common_Block(F, B): 4372 return 'USE_BLUE' 4373 else: 4374 return 'USE_RED_OR_BLUE' 4375 if (not In_Common_Block(F, A) 4376 and not In_Common_Block(F, A) ): 4377 return 'USE_RED_OR_BLUE' 4379 alt_to_X = Select_Alternates(X, F, primary_intf) 4380 alt_to_Y = Select_Alternates(Y, F, primary_intf) 4382 if (alt_to_X == 'USE_RED_OR_BLUE' 4383 and alt_to_Y == 'USE_RED_OR_BLUE'): 4384 return 'USE_RED_OR_BLUE' 4385 if alt_to_X == 'USE_RED_OR_BLUE': 4386 return 'USE_BLUE' 4387 if alt_to_Y == 'USE_RED_OR_BLUE': 4388 return 'USE_RED' 4390 if (A is S.localroot 4391 and B is S.localroot): 4392 #print("1.0") 4393 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 4394 return 'USE_RED_OR_BLUE' 4395 if alt_to_X == 'USE_BLUE': 4396 return 'USE_BLUE' 4397 if alt_to_Y == 'USE_RED': 4398 return 'USE_RED' 4399 assert(False) 4400 if (A is S.localroot 4401 and B is not S.localroot): 4402 #print("2.0") 4403 if B.LOWER: 4404 #print("2.1") 4405 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 4406 return 'USE_RED_OR_BLUE' 4407 if alt_to_X == 'USE_BLUE': 4408 return 'USE_BLUE' 4409 if alt_to_Y == 'USE_RED': 4410 return 'USE_RED' 4411 assert(False) 4412 if B.HIGHER: 4413 #print("2.2") 4414 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 4415 return 'USE_RED_OR_BLUE' 4416 if alt_to_X == 'USE_RED': 4417 return 'USE_BLUE' 4418 if alt_to_Y == 'USE_BLUE': 4419 return 'USE_RED' 4420 assert(False) 4421 else: 4422 #print("2.3") 4423 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'): 4424 return 'USE_RED_OR_BLUE' 4425 if alt_to_X == 'USE_RED': 4426 return 'USE_BLUE' 4427 if alt_to_Y == 'USE_RED': 4428 return 'USE_RED' 4429 assert(False) 4430 if (A is not S.localroot 4431 and B is S.localroot): 4432 #print("3.0") 4433 if A.LOWER: 4434 #print("3.1") 4435 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 4436 return 'USE_RED_OR_BLUE' 4437 if alt_to_X == 'USE_RED': 4438 return 'USE_BLUE' 4439 if alt_to_Y == 'USE_BLUE': 4440 return 'USE_RED' 4441 assert(False) 4442 if A.HIGHER: 4443 #print("3.2") 4444 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 4445 return 'USE_RED_OR_BLUE' 4446 if alt_to_X == 'USE_BLUE': 4447 return 'USE_BLUE' 4448 if alt_to_Y == 'USE_RED': 4449 return 'USE_RED' 4450 assert(False) 4451 else: 4452 #print("3.3") 4453 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'): 4454 return 'USE_RED_OR_BLUE' 4455 if alt_to_X == 'USE_RED': 4456 return 'USE_BLUE' 4457 if alt_to_Y == 'USE_RED': 4458 return 'USE_RED' 4459 assert(False) 4460 if (A is not S.localroot 4461 and B is not S.localroot): 4463 #print("4.0") 4464 if (S is A.localroot or S is B.localroot): 4465 #print("4.05") 4466 if A.topo_order < B.topo_order: 4467 #print("4.05.1") 4468 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 4469 return 'USE_RED_OR_BLUE' 4470 if alt_to_X == 'USE_BLUE': 4471 return 'USE_BLUE' 4472 if alt_to_Y == 'USE_RED': 4473 return 'USE_RED' 4474 assert(False) 4475 else: 4476 #print("4.05.2") 4477 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 4478 return 'USE_RED_OR_BLUE' 4479 if alt_to_X == 'USE_RED': 4480 return 'USE_BLUE' 4481 if alt_to_Y == 'USE_BLUE': 4482 return 'USE_RED' 4483 assert(False) 4484 if A.LOWER: 4485 #print("4.1") 4486 if B.HIGHER: 4487 #print("4.1.1") 4488 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 4489 return 'USE_RED_OR_BLUE' 4490 if alt_to_X == 'USE_RED': 4491 return 'USE_BLUE' 4492 if alt_to_Y == 'USE_BLUE': 4493 return 'USE_RED' 4494 assert(False) 4495 if B.LOWER: 4496 #print("4.1.2") 4497 if A.topo_order < B.topo_order: 4498 #print("4.1.2.1") 4499 if (alt_to_X == 'USE_BLUE' 4500 and alt_to_Y == 'USE_RED'): 4501 return 'USE_RED_OR_BLUE' 4502 if alt_to_X == 'USE_BLUE': 4503 return 'USE_BLUE' 4504 if alt_to_Y == 'USE_RED': 4505 return 'USE_RED' 4506 assert(False) 4507 else: 4508 #print("4.1.2.2") 4509 if (alt_to_X == 'USE_RED' 4510 and alt_to_Y == 'USE_BLUE'): 4512 return 'USE_RED_OR_BLUE' 4513 if alt_to_X == 'USE_RED': 4514 return 'USE_BLUE' 4515 if alt_to_Y == 'USE_BLUE': 4516 return 'USE_RED' 4517 assert(False) 4518 else: 4519 #print("4.1.3") 4520 if (F.LOWER and not F.HIGHER 4521 and F.topo_order > A.topo_order): 4522 #print("4.1.3.1") 4523 return 'USE_RED' 4524 else: 4525 #print("4.1.3.2") 4526 return 'USE_BLUE' 4527 if A.HIGHER: 4528 #print("4.2") 4529 if B.HIGHER: 4530 #print("4.2.1") 4531 if A.topo_order < B.topo_order: 4532 #print("4.2.1.1") 4533 if (alt_to_X == 'USE_BLUE' 4534 and alt_to_Y == 'USE_RED'): 4535 return 'USE_RED_OR_BLUE' 4536 if alt_to_X == 'USE_BLUE': 4537 return 'USE_BLUE' 4538 if alt_to_Y == 'USE_RED': 4539 return 'USE_RED' 4540 assert(False) 4541 else: 4542 #print("4.2.1.2") 4543 if (alt_to_X == 'USE_RED' 4544 and alt_to_Y == 'USE_BLUE'): 4545 return 'USE_RED_OR_BLUE' 4546 if alt_to_X == 'USE_RED': 4547 return 'USE_BLUE' 4548 if alt_to_Y == 'USE_BLUE': 4549 return 'USE_RED' 4550 assert(False) 4551 if B.LOWER: 4552 #print("4.2.2") 4553 if (alt_to_X == 'USE_BLUE' 4554 and alt_to_Y == 'USE_RED'): 4555 return 'USE_RED_OR_BLUE' 4556 if alt_to_X == 'USE_BLUE': 4557 return 'USE_BLUE' 4558 if alt_to_Y == 'USE_RED': 4559 return 'USE_RED' 4561 assert(False) 4562 else: 4563 #print("4.2.3") 4564 if (F.HIGHER and not F.LOWER 4565 and F.topo_order < A.topo_order): 4566 return 'USE_RED' 4567 else: 4568 return 'USE_BLUE' 4569 else: 4570 #print("4.3") 4571 if B.LOWER: 4572 #print("4.3.1") 4573 if (F.LOWER and not F.HIGHER 4574 and F.topo_order > B.topo_order): 4575 return 'USE_BLUE' 4576 else: 4577 return 'USE_RED' 4578 if B.HIGHER: 4579 #print("4.3.2") 4580 if (F.HIGHER and not F.LOWER 4581 and F.topo_order < B.topo_order): 4582 return 'USE_BLUE' 4583 else: 4584 return 'USE_RED' 4585 else: 4586 #print("4.3.3") 4587 if A.topo_order < B.topo_order: 4588 #print("4.3.3.1") 4589 if (alt_to_X == 'USE_BLUE' 4590 and alt_to_Y == 'USE_RED'): 4591 return 'USE_RED_OR_BLUE' 4592 if alt_to_X == 'USE_BLUE': 4593 return 'USE_BLUE' 4594 if alt_to_Y == 'USE_RED': 4595 return 'USE_RED' 4596 assert(False) 4597 else: 4598 #print("4.3.3.2") 4599 if (alt_to_X == 'USE_RED' 4600 and alt_to_Y == 'USE_BLUE'): 4601 return 'USE_RED_OR_BLUE' 4602 if alt_to_X == 'USE_RED': 4603 return 'USE_BLUE' 4604 if alt_to_Y == 'USE_BLUE': 4605 return 'USE_RED' 4606 assert(False) 4607 assert(False) 4609 def Compute_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src): 4610 for prefix in topo.named_proxy_dict: 4611 P = topo.named_proxy_dict[prefix] 4612 min_total_pref_cost = 2147483647 4613 for (adv_node, prefix_cost) in P.node_prefix_cost_list: 4614 total_pref_cost = (adv_node.primary_spf_metric 4615 + prefix_cost) 4616 if total_pref_cost < min_total_pref_cost: 4617 min_total_pref_cost = total_pref_cost 4618 Copy_List_Items(P.primary_next_hops, 4619 adv_node.primary_next_hops) 4620 elif total_pref_cost == min_total_pref_cost: 4621 for nh_intf in adv_node.primary_next_hops: 4622 Add_Item_To_List_If_New(P.primary_next_hops, 4623 nh_intf) 4625 def Select_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,src): 4626 for prefix in topo.named_proxy_dict: 4627 P = topo.named_proxy_dict[prefix] 4628 P.alt_list = [] 4629 for failed_intf in P.primary_next_hops: 4630 alt = Alternate() 4631 alt.failed_intf = failed_intf 4632 if failed_intf not in src.island_intf_list: 4633 alt.info = 'PRIM_NH_FOR_PROXY_NODE_NOT_IN_ISLAND' 4634 elif P.pnar1 is None: 4635 alt.info = 'NO_PNARs_EXIST_FOR_THIS_PREFIX' 4636 elif src is P.pnar1.node: 4637 alt.info = 'SRC_IS_PNAR' 4638 elif P.pnar2 is not None and src is P.pnar2.node: 4639 alt.info = 'SRC_IS_PNAR' 4640 elif P.pnar2 is None: 4641 #inherit alternates from the only pnar. 4642 alt.info = Select_Alternates(P.pnar1.node, 4643 failed_intf.remote_node, failed_intf) 4644 elif failed_intf in src.island_intf_list: 4645 alt.info = Select_Alternates_Proxy_Node(P, 4646 failed_intf.remote_node, failed_intf) 4648 if alt.info == 'USE_RED_OR_BLUE': 4649 alt.red_or_blue = \ 4650 random.choice(['USE_RED','USE_BLUE']) 4651 if (alt.info == 'USE_BLUE' 4652 or alt.red_or_blue == 'USE_BLUE'): 4653 Copy_List_Items(alt.nh_list, P.blue_next_hops) 4654 alt.fec = 'BLUE' 4655 alt.prot = 'NODE_PROTECTION' 4656 elif (alt.info == 'USE_RED' 4657 or alt.red_or_blue == 'USE_RED'): 4658 Copy_List_Items(alt.nh_list, P.red_next_hops) 4659 alt.fec = 'RED' 4660 alt.prot = 'NODE_PROTECTION' 4661 elif (alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D' 4662 or alt.info == 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y'): 4663 if failed_intf.OUTGOING and failed_intf.INCOMING: 4664 # cut-link: if there are parallel cut links, use 4665 # the link(s) with lowest metric that are not 4666 # primary intf or None 4667 cand_alt_list = [None] 4668 min_metric = 2147483647 4669 for intf in src.island_intf_list: 4670 if ( intf is not failed_intf and 4671 (intf.remote_node is 4672 failed_intf.remote_node)): 4673 if intf.metric < min_metric: 4674 cand_alt_list = [intf] 4675 min_metric = intf.metric 4676 elif intf.metric == min_metric: 4677 cand_alt_list.append(intf) 4678 if cand_alt_list != [None]: 4679 alt.fec = 'GREEN' 4680 alt.prot = 'PARALLEL_CUTLINK' 4681 else: 4682 alt.fec = 'NO_ALTERNATE' 4683 alt.prot = 'NO_PROTECTION' 4684 Copy_List_Items(alt.nh_list, cand_alt_list) 4685 else: 4686 # set Z as the node to inherit blue next-hops from 4687 if alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D': 4688 Z = P.pnar1.node 4689 else: 4690 Z = P 4691 if failed_intf in Z.red_next_hops: 4692 Copy_List_Items(alt.nh_list, Z.blue_next_hops) 4693 alt.fec = 'BLUE' 4694 alt.prot = 'LINK_PROTECTION' 4695 else: 4696 assert(failed_intf in Z.blue_next_hops) 4697 Copy_List_Items(alt.nh_list, Z.red_next_hops) 4698 alt.fec = 'RED' 4699 alt.prot = 'LINK_PROTECTION' 4701 elif alt.info == 'PRIM_NH_FOR_PROXY_NODE_NOT_IN_ISLAND': 4702 if (P.pnar2 == None and src is P.pnar1.node): 4703 #MRT Island is singly connected to non-island dest 4704 alt.fec = 'NO_ALTERNATE' 4705 alt.prot = 'NO_PROTECTION' 4706 elif P.node_id in src.blue_to_green_nh_dict: 4707 # blue to P goes to failed LFIN so use red to P 4708 Copy_List_Items(alt.nh_list, P.red_next_hops) 4709 alt.fec = 'RED' 4710 alt.prot = 'LINK_PROTECTION' 4711 elif P.node_id in src.red_to_green_nh_dict: 4712 # red to P goes to failed LFIN so use blue to P 4713 Copy_List_Items(alt.nh_list, P.blue_next_hops) 4714 alt.fec = 'BLUE' 4715 alt.prot = 'LINK_PROTECTION' 4716 else: 4717 Copy_List_Items(alt.nh_list, P.blue_next_hops) 4718 alt.fec = 'BLUE' 4719 alt.prot = 'LINK_PROTECTION' 4720 elif alt.info == 'TEMP_NO_ALTERNATE': 4721 alt.fec = 'NO_ALTERNATE' 4722 alt.prot = 'NO_PROTECTION' 4724 P.alt_list.append(alt) 4726 def Run_Basic_MRT_for_One_Source(topo, src): 4727 MRT_Island_Identification(topo, src, 0, 0) 4728 Set_Island_Intf_and_Node_Lists(topo) 4729 Set_GADAG_Root(topo,src) 4730 Sort_Interfaces(topo) 4731 Run_Lowpoint(topo) 4732 Assign_Remaining_Lowpoint_Parents(topo) 4733 Construct_GADAG_via_Lowpoint(topo) 4734 Run_Assign_Block_ID(topo) 4735 Add_Undirected_Links(topo) 4736 Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,src) 4737 Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,src) 4738 Select_Alts_For_One_Src_To_Island_Dests(topo,src) 4739 Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,src) 4741 def Store_GADAG_and_Named_Proxies_Once(topo): 4742 for node in topo.node_list: 4743 for intf in node.intf_list: 4744 if intf.OUTGOING: 4745 intf.SIMULATION_OUTGOING = True 4746 else: 4747 intf.SIMULATION_OUTGOING = False 4748 for prefix in topo.named_proxy_dict: 4749 P = topo.named_proxy_dict[prefix] 4750 topo.stored_named_proxy_dict[prefix] = P 4752 def Run_Basic_MRT_for_All_Sources(topo): 4754 for src in topo.node_list: 4755 Reset_Computed_Node_and_Intf_Values(topo) 4756 Run_Basic_MRT_for_One_Source(topo,src) 4757 if src is topo.gadag_root: 4758 Store_GADAG_and_Named_Proxies_Once(topo) 4760 def Run_MRT_for_One_Source(topo, src): 4761 MRT_Island_Identification(topo, src, 0, 0) 4762 Set_Island_Intf_and_Node_Lists(topo) 4763 Set_GADAG_Root(topo,src) 4764 Sort_Interfaces(topo) 4765 Run_Lowpoint(topo) 4766 Assign_Remaining_Lowpoint_Parents(topo) 4767 Construct_GADAG_via_Lowpoint(topo) 4768 Run_Assign_Block_ID(topo) 4769 Add_Undirected_Links(topo) 4770 Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,src) 4771 Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,src) 4772 Select_Alts_For_One_Src_To_Island_Dests(topo,src) 4773 Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,src) 4774 Create_Basic_Named_Proxy_Nodes(topo) 4775 Attach_Named_Proxy_Nodes(topo) 4776 Compute_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4777 Store_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4778 Compute_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4779 Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4780 Select_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4781 Store_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4783 def Run_Prim_SPF_for_One_Source(topo,src): 4784 Normal_SPF(topo, src) 4785 Store_Primary_NHs_For_One_Source_To_Nodes(topo,src) 4786 Create_Basic_Named_Proxy_Nodes(topo) 4787 Compute_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4788 Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4790 def Run_MRT_for_All_Sources(topo): 4791 for src in topo.node_list: 4792 Reset_Computed_Node_and_Intf_Values(topo) 4793 if src in topo.island_node_list_for_test_gr: 4794 # src runs MRT if it is in same MRT island as test_gr 4795 Run_MRT_for_One_Source(topo,src) 4796 if src is topo.gadag_root: 4797 Store_GADAG_and_Named_Proxies_Once(topo) 4798 else: 4799 # src still runs SPF if not in MRT island 4800 Run_Prim_SPF_for_One_Source(topo,src) 4802 def Write_Output_To_Files(topo,file_prefix): 4803 Write_GADAG_To_File(topo,file_prefix) 4804 Write_Both_MRTs_For_All_Dests_To_File(topo,file_prefix) 4805 Write_Alternates_For_All_Dests_To_File(topo,file_prefix) 4807 def Create_Basic_Topology_Input_File(filename): 4808 data = [[01,02,10],[02,03,10],[03,04,11],[04,05,10,20],[05,06,10], 4809 [06,07,10],[06,07,10],[06,07,15],[07,01,10],[07,51,10], 4810 [51,52,10],[52,53,10],[53,03,10],[01,55,10],[55,06,10], 4811 [04,12,10],[12,13,10],[13,14,10],[14,15,10],[15,16,10], 4812 [16,17,10],[17,04,10],[05,76,10],[76,77,10],[77,78,10], 4813 [78,79,10],[79,77,10]] 4814 with open(filename + '.csv', 'w') as topo_file: 4815 for item in data: 4816 if len(item) > 3: 4817 line = (str(item[0])+','+str(item[1])+','+ 4818 str(item[2])+','+str(item[3])+'\n') 4819 else: 4820 line = (str(item[0])+','+str(item[1])+','+ 4821 str(item[2])+'\n') 4822 topo_file.write(line) 4824 def Create_Complex_Topology_Input_File(filename): 4825 data = [[01,02,10],[02,03,10],[03,04,11],[04,05,10,20],[05,06,10], 4826 [06,07,10],[06,07,10],[06,07,15],[07,01,10],[07,51,10], 4827 [51,52,10],[52,53,10],[53,03,10],[01,55,10],[55,06,10], 4828 [04,12,10],[12,13,10],[13,14,10],[14,15,10],[15,16,10], 4829 [16,17,10],[17,04,10],[05,76,10],[76,77,10],[77,78,10], 4830 [78,79,10],[79,77,10]] 4831 with open(filename + '.csv', 'w') as topo_file: 4832 for item in data: 4833 if len(item) > 3: 4834 line = (str(item[0])+','+str(item[1])+','+ 4835 str(item[2])+','+str(item[3])+'\n') 4836 else: 4837 line = (str(item[0])+','+str(item[1])+','+ 4838 str(item[2])+'\n') 4839 topo_file.write(line) 4841 data = [[01,0],[02,0],[03,0],[04,0],[05,0], 4842 [06,0],[07,0], 4843 [51,0],[55,0], 4844 [12,0],[13,0],[14,0],[15,0], 4845 [16,0],[17,0],[76,0],[77,0], 4846 [78,0],[79,0]] 4847 with open(filename + '.profile', 'w') as topo_file: 4848 for item in data: 4849 line = (str(item[0])+','+str(item[1])+'\n') 4850 topo_file.write(line) 4852 data = [[2001,05,100],[2001,07,120],[2001,03,130], 4853 [2002,13,100],[2002,15,110], 4854 [2003,52,100],[2003,78,100]] 4855 with open(filename + '.prefix', 'w') as topo_file: 4856 for item in data: 4857 line = (str(item[0])+','+str(item[1])+','+ 4858 str(item[2])+'\n') 4859 topo_file.write(line) 4861 def Generate_Basic_Topology_and_Run_MRT(): 4862 this_gadag_root = 3 4863 Create_Basic_Topology_Input_File('basic_topo_input') 4864 topo = Create_Topology_From_File('basic_topo_input') 4865 res_file_base = 'basic_topo' 4866 Compute_Island_Node_List_For_Test_GR(topo, this_gadag_root) 4867 Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root) 4868 Run_Basic_MRT_for_All_Sources(topo) 4869 Write_Output_To_Files(topo, res_file_base) 4871 def Generate_Complex_Topology_and_Run_MRT(): 4872 this_gadag_root = 3 4873 Create_Complex_Topology_Input_File('complex_topo_input') 4874 topo = Create_Topology_From_File('complex_topo_input') 4875 Add_Profile_IDs_from_File(topo,'complex_topo_input') 4876 Add_Prefix_Advertisements_From_File(topo,'complex_topo_input') 4877 Compute_Island_Node_List_For_Test_GR(topo, this_gadag_root) 4878 Add_Prefixes_for_Non_Island_Nodes(topo) 4879 res_file_base = 'complex_topo' 4880 Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root) 4881 Run_MRT_for_All_Sources(topo) 4882 Write_Output_To_Files(topo, res_file_base) 4884 Generate_Basic_Topology_and_Run_MRT() 4886 Generate_Complex_Topology_and_Run_MRT() 4888 4890 9. Algorithm Alternatives and Evaluation 4892 This specification defines the MRT Lowpoint Algorithm, which is one 4893 option among several possible MRT algorithms. Other alternatives are 4894 described in the appendices. 4896 In addition, it is possible to calculate Destination-Rooted GADAG, 4897 where for each destination, a GADAG rooted at that destination is 4898 computed. Then a router can compute the blue MRT and red MRT next- 4899 hops to that destination. Building GADAGs per destination is 4900 computationally more expensive, but may give somewhat shorter 4901 alternate paths. It may be useful for live-live multicast along 4902 MRTs. 4904 9.1. Algorithm Evaluation 4906 The MRT Lowpoint algorithm is the lowest computation of the MRT 4907 algorithms. Two other MRT algorithms are provided in Appendix A and 4908 Appendix B. When analyzed on service provider network topologies, 4909 they did not provide significant differences in the path lenghts for 4910 the alternatives. This section does not focus on that analysis or 4911 the decision to use the MRT Lowpoint algorithm as the default MRT 4912 algorithm; it has the lowest computational and storage requirements 4913 and gave comparable results. 4915 Since this document defines the MRT Lowpoint algorithm for use in 4916 fast-reroute applications, it is useful to compare MRT and Remote LFA 4917 [RFC7490]. This section compares MRT and remote LFA for IP Fast 4918 Reroute in 19 service provider network topologies, focusing on 4919 coverage and alternate path length. Figure 30 shows the node- 4920 protecting coverage provided by local LFA (LLFA), remote LFA (RLFA), 4921 and MRT against different failure scenarios in these topologies. The 4922 coverage values are calculated as the percentage of source- 4923 destination pairs protected by the given IPFRR method relative to 4924 those protectable by optimal routing, against the same failure modes. 4925 More details on alternate selection policies used for this analysis 4926 are described later in this section. 4928 +------------+-----------------------------+ 4929 | Topology | percentage of failure | 4930 | | scenarios covered by | 4931 | | IPFRR method | 4932 | |-----------------------------+ 4933 | | NP_LLFA | NP_RLFA | MRT | 4934 +------------+---------+---------+---------+ 4935 | T201 | 37 | 90 | 100 | 4936 | T202 | 73 | 83 | 100 | 4937 | T203 | 51 | 80 | 100 | 4938 | T204 | 55 | 81 | 100 | 4939 | T205 | 92 | 93 | 100 | 4940 | T206 | 71 | 74 | 100 | 4941 | T207 | 57 | 74 | 100 | 4942 | T208 | 66 | 81 | 100 | 4943 | T209 | 79 | 79 | 100 | 4944 | T210 | 95 | 98 | 100 | 4945 | T211 | 68 | 71 | 100 | 4946 | T212 | 59 | 63 | 100 | 4947 | T213 | 84 | 84 | 100 | 4948 | T214 | 68 | 78 | 100 | 4949 | T215 | 84 | 88 | 100 | 4950 | T216 | 43 | 59 | 100 | 4951 | T217 | 78 | 88 | 100 | 4952 | T218 | 72 | 75 | 100 | 4953 | T219 | 78 | 84 | 100 | 4954 +------------+---------+---------+---------+ 4956 Figure 30 4958 For the topologies analyzed here, LLFA is able to provide node- 4959 protecting coverage ranging from 37% to 95% of the source-destination 4960 pairs, as seen in the column labeled NP_LLFA. The use of RLFA in 4961 addition to LLFA is generally able to increase the node-protecting 4962 coverage. The percentage of node-protecting coverage with RLFA is 4963 provided in the column labeled NP_RLFA, ranges from 59% to 98% for 4964 these topologies. The node-protecting coverage provided by MRT is 4965 100% since MRT is able to provide protection for any source- 4966 destination pair for which a path still exists after the failure. 4968 We would also like to measure the quality of the alternate paths 4969 produced by these different IPFRR methods. An obvious approach is to 4970 take an average of the alternate path costs over all source- 4971 destination pairs and failure modes. However, this presents a 4972 problem, which we will illustrate by presenting an example of results 4973 for one topology using this approach ( Figure 31). In this table, 4974 the average relative path length is the alternate path length for the 4975 IPFRR method divided by the optimal alternate path length, averaged 4976 over all source-destination pairs and failure modes. The first three 4977 columns of data in the table give the path length calculated from the 4978 sum of IGP metrics of the links in the path. The results for 4979 topology T208 show that the metric-based path lengths for NP_LLFA and 4980 NP_RLFA alternates are on average 78 and 66 times longer than the 4981 path lengths for optimal alternates. The metric-based path lengths 4982 for MRT alternates are on average 14 times longer than for optimal 4983 alternates. 4985 +--------+------------------------------------------------+ 4986 | | average relative alternate path length | 4987 | |-----------------------+------------------------+ 4988 |Topology| IGP metric | hopcount | 4989 | |-----------------------+------------------------+ 4990 | |NP_LLFA |NP_RLFA | MRT |NP_LLFA |NP_RLFA | MRT | 4991 +--------+--------+--------+-----+--------+--------+------+ 4992 | T208 | 78.2 | 66.0 | 13.6| 0.99 | 1.01 | 1.32 | 4993 +--------+--------+--------+-----+--------+--------+------+ 4995 Figure 31 4997 The network topology represented by T208 uses values of 10, 100, and 4998 1000 as IGP costs, so small deviations from the optimal alternate 4999 path can result in large differences in relative path length. LLFA, 5000 RLFA, and MRT all allow for at least one hop in the alterate path to 5001 be chosen independent of the cost of the link. This can easily 5002 result in an alternate using a link with cost 1000, which introduces 5003 noise into the path length measurement. In the case of T208, the 5004 adverse effects of using metric-based path lengths is obvious. 5005 However, we have observed that the metric-based path length 5006 introduces noise into alternate path length measurements in several 5007 other topologies as well. For this reason, we have opted to measure 5008 the alternate path length using hopcount. While IGP metrics may be 5009 adjusted by the network operator for a number of reasons (e.g. 5010 traffic engineering), the hopcount is a fairly stable measurement of 5011 path length. As shown in the last three columns of Figure 31, the 5012 hopcount-based alternate path lengths for topology T208 are fairly 5013 well-behaved. 5015 Figure 32, Figure 33, Figure 34, and Figure 35 present the hopcount- 5016 based path length results for the 19 topologies examined. The 5017 topologies in the four tables are grouped based on the size of the 5018 topologies, as measured by the number of nodes, with Figure 32 having 5019 the smallest topologies and Figure 35 having the largest topologies. 5020 Instead of trying to represent the path lengths of a large set of 5021 alternates with a single number, we have chosen to present a 5022 histogram of the path lengths for each IPFRR method and alternate 5023 selection policy studied. The first eight colums of data represent 5024 the percentage of failure scenarios protected by an alternate N hops 5025 longer than the primary path, with the first column representing an 5026 alternate 0 or 1 hops longer than the primary path, all the way up 5027 through the eighth column respresenting an alternate 14 or 15 hops 5028 longer than the primary path. The last column in the table gives the 5029 percentage of failure scenarios for which there is no alternate less 5030 than 16 hops longer than the primary path. In the case of LLFA and 5031 RLFA, this category includes failure scenarios for which no alternate 5032 was found. 5034 For each topology, the first row (labeled OPTIMAL) is the 5035 distribution of the number of hops in excess of the primary path 5036 hopcount for optimally routed alternates. (The optimal routing was 5037 done with respect to IGP metrics, as opposed to hopcount.) The 5038 second row(labeled NP_LLFA) is the distribution of the extra hops for 5039 node-protecting LLFA. The third row (labeled NP_LLFA_THEN_NP_RLFA) 5040 is the hopcount distribution when one adds node-protecting RLFA to 5041 increase the coverage. The alternate selection policy used here 5042 first tries to find a node-protecting LLFA. If that does not exist, 5043 then it tries to find an RLFA, and checks if it is node-protecting. 5044 Comparing the hopcount distribution for RLFA and LLFA across these 5045 topologies, one can see how the coverage is increased at the expense 5046 of using longer alternates. It is also worth noting that while 5047 superficially LLFA and RLFA appear to have better hopcount 5048 distributions than OPTIMAL, the presence of entries in the last 5049 column (no alternate < 16) mainly represent failure scenarios that 5050 are not protected, for which the hopcount is effectively infinite. 5052 The fourth and fifth rows of each topology show the hopcount 5053 distributions for two alternate selection policies using MRT 5054 alternates. The policy represented by the label 5055 NP_LLFA_THEN_MRT_LOWPOINT will first use a node-protecting LLFA. If 5056 a node-protecting LLFA does not exist, then it will use an MRT 5057 alternate. The policy represented by the label MRT_LOWPOINT instead 5058 will use the MRT alternate even if a node-protecting LLFA exists. 5059 One can see from the data that combining node-protecting LLFA with 5060 MRT results in a significant shortening of the alternate hopcount 5061 distribution. 5063 +-------------------------------------------------------------------+ 5064 | | percentage of failure scenarios | 5065 | Topology name | protected by an alternate N hops | 5066 | and | longer than the primary path | 5067 | alternate selection +------------------------------------+ 5068 | policy evaluated | | | | | | | | | no | 5069 | | | | | | |10 |12 |14 | alt| 5070 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 5071 +------------------------------+---+---+---+---+---+---+---+---+----+ 5072 | T201(avg primary hops=3.5) | | | | | | | | | | 5073 | OPTIMAL | 37| 37| 20| 3| 3| | | | | 5074 | NP_LLFA | 37| | | | | | | | 63| 5075 | NP_LLFA_THEN_NP_RLFA | 37| 34| 19| | | | | | 10| 5076 | NP_LLFA_THEN_MRT_LOWPOINT | 37| 33| 21| 6| 3| | | | | 5077 | MRT_LOWPOINT | 33| 36| 23| 6| 3| | | | | 5078 +------------------------------+---+---+---+---+---+---+---+---+----+ 5079 | T202(avg primary hops=4.8) | | | | | | | | | | 5080 | OPTIMAL | 90| 9| | | | | | | | 5081 | NP_LLFA | 71| 2| | | | | | | 27| 5082 | NP_LLFA_THEN_NP_RLFA | 78| 5| | | | | | | 17| 5083 | NP_LLFA_THEN_MRT_LOWPOINT | 80| 12| 5| 2| 1| | | | | 5084 | MRT_LOWPOINT_ONLY | 48| 29| 13| 7| 2| 1| | | | 5085 +------------------------------+---+---+---+---+---+---+---+---+----+ 5086 | T203(avg primary hops=4.1) | | | | | | | | | | 5087 | OPTIMAL | 36| 37| 21| 4| 2| | | | | 5088 | NP_LLFA | 34| 15| 3| | | | | | 49| 5089 | NP_LLFA_THEN_NP_RLFA | 35| 19| 22| 4| | | | | 20| 5090 | NP_LLFA_THEN_MRT_LOWPOINT | 36| 35| 22| 5| 2| | | | | 5091 | MRT_LOWPOINT_ONLY | 31| 35| 26| 7| 2| | | | | 5092 +------------------------------+---+---+---+---+---+---+---+---+----+ 5093 | T204(avg primary hops=3.7) | | | | | | | | | | 5094 | OPTIMAL | 76| 20| 3| 1| | | | | | 5095 | NP_LLFA | 54| 1| | | | | | | 45| 5096 | NP_LLFA_THEN_NP_RLFA | 67| 10| 4| | | | | | 19| 5097 | NP_LLFA_THEN_MRT_LOWPOINT | 70| 18| 8| 3| 1| | | | | 5098 | MRT_LOWPOINT_ONLY | 58| 27| 11| 3| 1| | | | | 5099 +------------------------------+---+---+---+---+---+---+---+---+----+ 5100 | T205(avg primary hops=3.4) | | | | | | | | | | 5101 | OPTIMAL | 92| 8| | | | | | | | 5102 | NP_LLFA | 89| 3| | | | | | | 8| 5103 | NP_LLFA_THEN_NP_RLFA | 90| 4| | | | | | | 7| 5104 | NP_LLFA_THEN_MRT_LOWPOINT | 91| 9| | | | | | | | 5105 | MRT_LOWPOINT_ONLY | 62| 33| 5| 1| | | | | | 5106 +------------------------------+---+---+---+---+---+---+---+---+----+ 5108 Figure 32 5110 +-------------------------------------------------------------------+ 5111 | | percentage of failure scenarios | 5112 | Topology name | protected by an alternate N hops | 5113 | and | longer than the primary path | 5114 | alternate selection +------------------------------------+ 5115 | policy evaluated | | | | | | | | | no | 5116 | | | | | | |10 |12 |14 | alt| 5117 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 5118 +------------------------------+---+---+---+---+---+---+---+---+----+ 5119 | T206(avg primary hops=3.7) | | | | | | | | | | 5120 | OPTIMAL | 63| 30| 7| | | | | | | 5121 | NP_LLFA | 60| 9| 1| | | | | | 29| 5122 | NP_LLFA_THEN_NP_RLFA | 60| 13| 1| | | | | | 26| 5123 | NP_LLFA_THEN_MRT_LOWPOINT | 64| 29| 7| | | | | | | 5124 | MRT_LOWPOINT | 55| 32| 13| | | | | | | 5125 +------------------------------+---+---+---+---+---+---+---+---+----+ 5126 | T207(avg primary hops=3.9) | | | | | | | | | | 5127 | OPTIMAL | 71| 24| 5| 1| | | | | | 5128 | NP_LLFA | 55| 2| | | | | | | 43| 5129 | NP_LLFA_THEN_NP_RLFA | 63| 10| | | | | | | 26| 5130 | NP_LLFA_THEN_MRT_LOWPOINT | 70| 20| 7| 2| 1| | | | | 5131 | MRT_LOWPOINT_ONLY | 57| 29| 11| 3| 1| | | | | 5132 +------------------------------+---+---+---+---+---+---+---+---+----+ 5133 | T208(avg primary hops=4.6) | | | | | | | | | | 5134 | OPTIMAL | 58| 28| 12| 2| 1| | | | | 5135 | NP_LLFA | 53| 11| 3| | | | | | 34| 5136 | NP_LLFA_THEN_NP_RLFA | 56| 17| 7| 1| | | | | 19| 5137 | NP_LLFA_THEN_MRT_LOWPOINT | 58| 19| 10| 7| 3| 1| | | | 5138 | MRT_LOWPOINT_ONLY | 34| 24| 21| 13| 6| 2| 1| | | 5139 +------------------------------+---+---+---+---+---+---+---+---+----+ 5140 | T209(avg primary hops=3.6) | | | | | | | | | | 5141 | OPTIMAL | 85| 14| 1| | | | | | | 5142 | NP_LLFA | 79| | | | | | | | 21| 5143 | NP_LLFA_THEN_NP_RLFA | 79| | | | | | | | 21| 5144 | NP_LLFA_THEN_MRT_LOWPOINT | 82| 15| 2| | | | | | | 5145 | MRT_LOWPOINT_ONLY | 63| 29| 8| | | | | | | 5146 +------------------------------+---+---+---+---+---+---+---+---+----+ 5147 | T210(avg primary hops=2.5) | | | | | | | | | | 5148 | OPTIMAL | 95| 4| 1| | | | | | | 5149 | NP_LLFA | 94| 1| | | | | | | 5| 5150 | NP_LLFA_THEN_NP_RLFA | 94| 3| 1| | | | | | 2| 5151 | NP_LLFA_THEN_MRT_LOWPOINT | 95| 4| 1| | | | | | | 5152 | MRT_LOWPOINT_ONLY | 91| 6| 2| | | | | | | 5153 +------------------------------+---+---+---+---+---+---+---+---+----+ 5155 Figure 33 5157 +-------------------------------------------------------------------+ 5158 | | percentage of failure scenarios | 5159 | Topology name | protected by an alternate N hops | 5160 | and | longer than the primary path | 5161 | alternate selection +------------------------------------+ 5162 | policy evaluated | | | | | | | | | no | 5163 | | | | | | |10 |12 |14 | alt| 5164 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 5165 +------------------------------+---+---+---+---+---+---+---+---+----+ 5166 | T211(avg primary hops=3.3) | | | | | | | | | | 5167 | OPTIMAL | 88| 11| | | | | | | | 5168 | NP_LLFA | 66| 1| | | | | | | 32| 5169 | NP_LLFA_THEN_NP_RLFA | 68| 3| | | | | | | 29| 5170 | NP_LLFA_THEN_MRT_LOWPOINT | 88| 12| | | | | | | | 5171 | MRT_LOWPOINT | 85| 15| 1| | | | | | | 5172 +------------------------------+---+---+---+---+---+---+---+---+----+ 5173 | T212(avg primary hops=3.5) | | | | | | | | | | 5174 | OPTIMAL | 76| 23| 1| | | | | | | 5175 | NP_LLFA | 59| | | | | | | | 41| 5176 | NP_LLFA_THEN_NP_RLFA | 61| 1| 1| | | | | | 37| 5177 | NP_LLFA_THEN_MRT_LOWPOINT | 75| 24| 1| | | | | | | 5178 | MRT_LOWPOINT_ONLY | 66| 31| 3| | | | | | | 5179 +------------------------------+---+---+---+---+---+---+---+---+----+ 5180 | T213(avg primary hops=4.3) | | | | | | | | | | 5181 | OPTIMAL | 91| 9| | | | | | | | 5182 | NP_LLFA | 84| | | | | | | | 16| 5183 | NP_LLFA_THEN_NP_RLFA | 84| | | | | | | | 16| 5184 | NP_LLFA_THEN_MRT_LOWPOINT | 89| 10| 1| | | | | | | 5185 | MRT_LOWPOINT_ONLY | 75| 24| 1| | | | | | | 5186 +------------------------------+---+---+---+---+---+---+---+---+----+ 5187 | T214(avg primary hops=5.8) | | | | | | | | | | 5188 | OPTIMAL | 71| 22| 5| 2| | | | | | 5189 | NP_LLFA | 58| 8| 1| 1| | | | | 32| 5190 | NP_LLFA_THEN_NP_RLFA | 61| 13| 3| 1| | | | | 22| 5191 | NP_LLFA_THEN_MRT_LOWPOINT | 66| 14| 7| 5| 3| 2| 1| 1| 1| 5192 | MRT_LOWPOINT_ONLY | 30| 20| 18| 12| 8| 4| 3| 2| 3| 5193 +------------------------------+---+---+---+---+---+---+---+---+----+ 5194 | T215(avg primary hops=4.8) | | | | | | | | | | 5195 | OPTIMAL | 73| 27| | | | | | | | 5196 | NP_LLFA | 73| 11| | | | | | | 16| 5197 | NP_LLFA_THEN_NP_RLFA | 73| 13| 2| | | | | | 12| 5198 | NP_LLFA_THEN_MRT_LOWPOINT | 74| 19| 3| 2| 1| 1| 1| | | 5199 | MRT_LOWPOINT_ONLY | 32| 31| 16| 12| 4| 3| 1| | | 5200 +------------------------------+---+---+---+---+---+---+---+---+----+ 5202 Figure 34 5204 +-------------------------------------------------------------------+ 5205 | | percentage of failure scenarios | 5206 | Topology name | protected by an alternate N hops | 5207 | and | longer than the primary path | 5208 | alternate selection +------------------------------------+ 5209 | policy evaluated | | | | | | | | | no | 5210 | | | | | | |10 |12 |14 | alt| 5211 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 5212 +------------------------------+---+---+---+---+---+---+---+---+----+ 5213 | T216(avg primary hops=5.2) | | | | | | | | | | 5214 | OPTIMAL | 60| 32| 7| 1| | | | | | 5215 | NP_LLFA | 39| 4| | | | | | | 57| 5216 | NP_LLFA_THEN_NP_RLFA | 46| 12| 2| | | | | | 41| 5217 | NP_LLFA_THEN_MRT_LOWPOINT | 48| 20| 12| 7| 5| 4| 2| 1| 1| 5218 | MRT_LOWPOINT | 28| 25| 18| 11| 7| 6| 3| 2| 1| 5219 +------------------------------+---+---+---+---+---+---+---+---+----+ 5220 | T217(avg primary hops=8.0) | | | | | | | | | | 5221 | OPTIMAL | 81| 13| 5| 1| | | | | | 5222 | NP_LLFA | 74| 3| 1| | | | | | 22| 5223 | NP_LLFA_THEN_NP_RLFA | 76| 8| 3| 1| | | | | 12| 5224 | NP_LLFA_THEN_MRT_LOWPOINT | 77| 7| 5| 4| 3| 2| 1| 1| | 5225 | MRT_LOWPOINT_ONLY | 25| 18| 18| 16| 12| 6| 3| 1| | 5226 +------------------------------+---+---+---+---+---+---+---+---+----+ 5227 | T218(avg primary hops=5.5) | | | | | | | | | | 5228 | OPTIMAL | 85| 14| 1| | | | | | | 5229 | NP_LLFA | 68| 3| | | | | | | 28| 5230 | NP_LLFA_THEN_NP_RLFA | 71| 4| | | | | | | 25| 5231 | NP_LLFA_THEN_MRT_LOWPOINT | 77| 12| 7| 4| 1| | | | | 5232 | MRT_LOWPOINT_ONLY | 37| 29| 21| 10| 3| 1| | | | 5233 +------------------------------+---+---+---+---+---+---+---+---+----+ 5234 | T219(avg primary hops=7.7) | | | | | | | | | | 5235 | OPTIMAL | 77| 15| 5| 1| 1| | | | | 5236 | NP_LLFA | 72| 5| | | | | | | 22| 5237 | NP_LLFA_THEN_NP_RLFA | 73| 8| 2| | | | | | 16| 5238 | NP_LLFA_THEN_MRT_LOWPOINT | 74| 8| 3| 3| 2| 2| 2| 2| 4| 5239 | MRT_LOWPOINT_ONLY | 19| 14| 15| 12| 10| 8| 7| 6| 10| 5240 +------------------------------+---+---+---+---+---+---+---+---+----+ 5242 Figure 35 5244 In the preceding analysis, the following procedure for selecting an 5245 RLFA was used. Nodes were ordered with respect to distance from the 5246 source and checked for membership in Q and P-space. The first node 5247 to satisfy this condition was selected as the RLFA. More 5248 sophisticated methods to select node-protecting RLFAs is an area of 5249 active research. 5251 The analysis presented above uses the MRT Lowpoint Algorithm defined 5252 in this specification with a common GADAG root. The particular 5253 choice of a common GADAG root is expected to affect the quality of 5254 the MRT alternate paths, with a more central common GADAG root 5255 resulting in shorter MRT alternate path lengths. For the analysis 5256 above, the GADAG root was chosen for each topology by calculating 5257 node centrality as the sum of costs of all shortest paths to and from 5258 a given node. The node with the lowest sum was chosen as the common 5259 GADAG root. In actual deployments, the common GADAG root would be 5260 chosen based on the GADAG Root Selection Priority advertised by each 5261 router, the values of which would be determined off-line. 5263 In order to measure how sensitive the MRT alternate path lengths are 5264 to the choice of common GADAG root, we performed the same analysis 5265 using different choices of GADAG root. All of the nodes in the 5266 network were ordered with respect to the node centrality as computed 5267 above. Nodes were chosen at the 0th, 25th, and 50th percentile with 5268 respect to the centrality ordering, with 0th percentile being the 5269 most central node. The distribution of alternate path lengths for 5270 those three choices of GADAG root are shown in Figure 36 for a subset 5271 of the 19 topologies (chosen arbitrarily). The third row for each 5272 topology (labeled MRT_LOWPOINT ( 0 percentile) ) reproduces the 5273 results presented above for MRT_LOWPOINT_ONLY. The fourth and fifth 5274 rows show the alternate path length distibution for the 25th and 50th 5275 percentile choice for GADAG root. One can see some impact on the 5276 path length distribution with the less central choice of GADAG root 5277 resulting in longer path lenghths. 5279 We also looked at the impact of MRT algorithm variant on the 5280 alternate path lengths. The first two rows for each topology present 5281 results of the same alternate path length distribution analysis for 5282 the SPF and Hybrid methods for computing the GADAG. These two 5283 methods are described in Appendix A and Appendix B. For three of the 5284 topologies in this subset (T201, T206, and T211), the use of SPF or 5285 Hybrid methods does not appear to provide a significant advantage 5286 over the Lowpoint method with respect to path length. Instead, the 5287 choice of GADAG root appears to have more impact on the path length. 5288 However, for two of the topologies in this subset(T216 and T219) and 5289 for this particular choice of GAGAG root, the use of the SPF method 5290 results in noticeably shorter alternate path lengths than the use of 5291 the Lowpoint or Hybrid methods. It remains to be determined if this 5292 effect applies generally across more topologies or is sensitive to 5293 choice of GADAG root. 5295 +-------------------------------------------------------------------+ 5296 | Topology name | percentage of failure scenarios | 5297 | | protected by an alternate N hops | 5298 | MRT algorithm variant | longer than the primary path | 5299 | +------------------------------------+ 5300 | (GADAG root | | | | | | | | | no | 5301 | centrality percentile) | | | | | |10 |12 |14 | alt| 5302 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 5303 +------------------------------+---+---+---+---+---+---+---+---+----+ 5304 | T201(avg primary hops=3.5) | | | | | | | | | | 5305 | MRT_HYBRID ( 0 percentile) | 33| 26| 23| 6| 3| | | | | 5306 | MRT_SPF ( 0 percentile) | 33| 36| 23| 6| 3| | | | | 5307 | MRT_LOWPOINT ( 0 percentile) | 33| 36| 23| 6| 3| | | | | 5308 | MRT_LOWPOINT (25 percentile) | 27| 29| 23| 11| 10| | | | | 5309 | MRT_LOWPOINT (50 percentile) | 27| 29| 23| 11| 10| | | | | 5310 +------------------------------+---+---+---+---+---+---+---+---+----+ 5311 | T206(avg primary hops=3.7) | | | | | | | | | | 5312 | MRT_HYBRID ( 0 percentile) | 50| 35| 13| 2| | | | | | 5313 | MRT_SPF ( 0 percentile) | 50| 35| 13| 2| | | | | | 5314 | MRT_LOWPOINT ( 0 percentile) | 55| 32| 13| | | | | | | 5315 | MRT_LOWPOINT (25 percentile) | 47| 25| 22| 6| | | | | | 5316 | MRT_LOWPOINT (50 percentile) | 38| 38| 14| 11| | | | | | 5317 +------------------------------+---+---+---+---+---+---+---+---+----+ 5318 | T211(avg primary hops=3.3) | | | | | | | | | | 5319 | MRT_HYBRID ( 0 percentile) | 86| 14| | | | | | | | 5320 | MRT_SPF ( 0 percentile) | 86| 14| | | | | | | | 5321 | MRT_LOWPOINT ( 0 percentile) | 85| 15| 1| | | | | | | 5322 | MRT_LOWPOINT (25 percentile) | 70| 25| 5| 1| | | | | | 5323 | MRT_LOWPOINT (50 percentile) | 80| 18| 2| | | | | | | 5324 +------------------------------+---+---+---+---+---+---+---+---+----+ 5325 | T216(avg primary hops=5.2) | | | | | | | | | | 5326 | MRT_HYBRID ( 0 percentile) | 23| 22| 18| 13| 10| 7| 4| 2| 2| 5327 | MRT_SPF ( 0 percentile) | 35| 32| 19| 9| 3| 1| | | | 5328 | MRT_LOWPOINT ( 0 percentile) | 28| 25| 18| 11| 7| 6| 3| 2| 1| 5329 | MRT_LOWPOINT (25 percentile) | 24| 20| 19| 16| 10| 6| 3| 1| | 5330 | MRT_LOWPOINT (50 percentile) | 19| 14| 13| 10| 8| 6| 5| 5| 10| 5331 +------------------------------+---+---+---+---+---+---+---+---+----+ 5332 | T219(avg primary hops=7.7) | | | | | | | | | | 5333 | MRT_HYBRID ( 0 percentile) | 20| 16| 13| 10| 7| 5| 5| 5| 3| 5334 | MRT_SPF ( 0 percentile) | 31| 23| 19| 12| 7| 4| 2| 1| | 5335 | MRT_LOWPOINT ( 0 percentile) | 19| 14| 15| 12| 10| 8| 7| 6| 10| 5336 | MRT_LOWPOINT (25 percentile) | 19| 14| 15| 13| 12| 10| 6| 5| 7| 5337 | MRT_LOWPOINT (50 percentile) | 19| 14| 14| 12| 11| 8| 6| 6| 10| 5338 +------------------------------+---+---+---+---+---+---+---+---+----+ 5340 Figure 36 5342 10. Implementation Status 5344 [RFC Editor: please remove this section prior to publication.] 5346 Please see [I-D.ietf-rtgwg-mrt-frr-architecture] for details on 5347 implementation status. 5349 11. Acknowledgements 5351 The authors would like to thank Shraddha Hegde, Eric Wu, and Janos 5352 Farkas for their suggestions and review. We would also like to thank 5353 Anil Kumar SN for his assistance in clarifying the algorithm 5354 description and pseudo-code. 5356 12. IANA Considerations 5358 This document includes no request to IANA. 5360 13. Security Considerations 5362 The algorithm described in this document does not introduce new 5363 security concerns beyond those already discussed in the document 5364 describing the MRT FRR architecture 5365 [I-D.ietf-rtgwg-mrt-frr-architecture]. 5367 14. References 5369 14.1. Normative References 5371 [I-D.ietf-rtgwg-mrt-frr-architecture] 5372 Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar, 5373 A., Tantsura, J., and R. White, "An Architecture for IP/ 5374 LDP Fast-Reroute Using Maximally Redundant Trees", draft- 5375 ietf-rtgwg-mrt-frr-architecture-07 (work in progress), 5376 October 2015. 5378 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 5379 Requirement Levels", BCP 14, RFC 2119, 5380 DOI 10.17487/RFC2119, March 1997, 5381 . 5383 14.2. Informative References 5385 [EnyediThesis] 5386 Enyedi, G., "Novel Algorithms for IP Fast Reroute", 5387 Department of Telecommunications and Media Informatics, 5388 Budapest University of Technology and Economics Ph.D. 5389 Thesis, February 2011, . 5393 [I-D.ietf-isis-mrt] 5394 Li, Z., Wu, N., <>, Q., Atlas, A., Bowers, C., and J. 5395 Tantsura, "Intermediate System to Intermediate System (IS- 5396 IS) Extensions for Maximally Redundant Trees (MRT)", 5397 draft-ietf-isis-mrt-01 (work in progress), October 2015. 5399 [I-D.ietf-isis-pcr] 5400 Farkas, J., Bragg, N., Unbehagen, P., Parsons, G., 5401 Ashwood-Smith, P., and C. Bowers, "IS-IS Path Computation 5402 and Reservation", draft-ietf-isis-pcr-04 (work in 5403 progress), December 2015. 5405 [I-D.ietf-ospf-mrt] 5406 Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li, 5407 "OSPF Extensions to Support Maximally Redundant Trees", 5408 draft-ietf-ospf-mrt-01 (work in progress), October 2015. 5410 [I-D.ietf-rtgwg-lfa-manageability] 5411 Litkowski, S., Decraene, B., Filsfils, C., Raza, K., 5412 Horneffer, M., and P. Sarkar, "Operational management of 5413 Loop Free Alternates", draft-ietf-rtgwg-lfa- 5414 manageability-11 (work in progress), June 2015. 5416 [ISO10589-Second-Edition] 5417 International Organization for Standardization, 5418 "Intermediate system to Intermediate system intra-domain 5419 routeing information exchange protocol for use in 5420 conjunction with the protocol for providing the 5421 connectionless-mode Network Service (ISO 8473)", ISO/ 5422 IEC 10589:2002, Second Edition, Nov. 2002. 5424 [Kahn_1962_topo_sort] 5425 Kahn, A., "Topological sorting of large networks", 5426 Communications of the ACM, Volume 5, Issue 11 , Nov 1962, 5427 . 5429 [MRTLinear] 5430 Enyedi, G., Retvari, G., and A. Csaszar, "On Finding 5431 Maximally Redundant Trees in Strictly Linear Time", IEEE 5432 Symposium on Computers and Comunications (ISCC) , 2009, 5433 . 5436 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, 5437 DOI 10.17487/RFC2328, April 1998, 5438 . 5440 [RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi 5441 Topology (MT) Routing in Intermediate System to 5442 Intermediate Systems (IS-ISs)", RFC 5120, 5443 DOI 10.17487/RFC5120, February 2008, 5444 . 5446 [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. 5447 So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", 5448 RFC 7490, DOI 10.17487/RFC7490, April 2015, 5449 . 5451 Appendix A. Option 2: Computing GADAG using SPFs 5453 The basic idea in this option is to use slightly-modified SPF 5454 computations to find ears. In every block, an SPF computation is 5455 first done to find a cycle from the local root and then SPF 5456 computations in that block find ears until there are no more 5457 interfaces to be explored. The used result from the SPF computation 5458 is the path of interfaces indicated by following the previous hops 5459 from the mininized IN_GADAG node back to the SPF root. 5461 To do this, first all cut-vertices must be identified and local-roots 5462 assigned as specified in Figure 12. 5464 The slight modifications to the SPF are as follows. The root of the 5465 block is referred to as the block-root; it is either the GADAG root 5466 or a cut-vertex. 5468 a. The SPF is rooted at a neighbor x of an IN_GADAG node y. All 5469 links between y and x are marked as TEMP_UNUSABLE. They should 5470 not be used during the SPF computation. 5472 b. If y is not the block-root, then it is marked TEMP_UNUSABLE. It 5473 should not be used during the SPF computation. This prevents 5474 ears from starting and ending at the same node and avoids cycles; 5475 the exception is because cycles to/from the block-root are 5476 acceptable and expected. 5478 c. Do not explore links to nodes whose local-root is not the block- 5479 root. This keeps the SPF confined to the particular block. 5481 d. Terminate when the first IN_GADAG node z is minimized. 5483 e. Respect the existing directions (e.g. INCOMING, OUTGOING, 5484 UNDIRECTED) already specified for each interface. 5486 Mod_SPF(spf_root, block_root) 5487 Initialize spf_heap to empty 5488 Initialize nodes' spf_metric to infinity 5489 spf_root.spf_metric = 0 5490 insert(spf_heap, spf_root) 5491 found_in_gadag = false 5492 while (spf_heap is not empty) and (found_in_gadag is false) 5493 min_node = remove_lowest(spf_heap) 5494 if min_node.IN_GADAG 5495 found_in_gadag = true 5496 else 5497 foreach interface intf of min_node 5498 if ((intf.OUTGOING or intf.UNDIRECTED) and 5499 ((intf.remote_node.localroot is block_root) or 5500 (intf.remote_node is block_root)) and 5501 (intf.remote_node is not TEMP_UNUSABLE) and 5502 (intf is not TEMP_UNUSABLE)) 5503 path_metric = min_node.spf_metric + intf.metric 5504 if path_metric < intf.remote_node.spf_metric 5505 intf.remote_node.spf_metric = path_metric 5506 intf.remote_node.spf_prev_intf = intf 5507 insert_or_update(spf_heap, intf.remote_node) 5508 return min_node 5510 SPF_for_Ear(cand_intf.local_node,cand_intf.remote_node, block_root, 5511 method) 5512 Mark all interfaces between cand_intf.remote_node 5513 and cand_intf.local_node as TEMP_UNUSABLE 5514 if cand_intf.local_node is not block_root 5515 Mark cand_intf.local_node as TEMP_UNUSABLE 5516 Initialize ear_list to empty 5517 end_ear = Mod_SPF(spf_root, block_root) 5518 y = end_ear.spf_prev_hop 5519 while y.local_node is not spf_root 5520 add_to_list_start(ear_list, y) 5521 y.local_node.IN_GADAG = true 5522 y = y.local_node.spf_prev_intf 5524 if(method is not hybrid) 5525 Set_Ear_Direction(ear_list, cand_intf.local_node, 5526 end_ear,block_root) 5527 Clear TEMP_UNUSABLE from all interfaces between 5528 cand_intf.remote_node and cand_intf.local_node 5529 Clear TEMP_UNUSABLE from cand_intf.local_node 5530 return end_ear 5532 Figure 37: Modified SPF for GADAG computation 5534 Assume that an ear is found by going from y to x and then running an 5535 SPF that terminates by minimizing z (e.g. y<->x...q<->z). Now it is 5536 necessary to determine the direction of the ear; if y << z, then the 5537 path should be y->x...q->z but if y >> z, then the path should be y<- 5538 x...q<-z. In Section 5.5, the same problem was handled by finding 5539 all ears that started at a node before looking at ears starting at 5540 nodes higher in the partial order. In this algorithm, using that 5541 approach could mean that new ears aren't added in order of their 5542 total cost since all ears connected to a node would need to be found 5543 before additional nodes could be found. 5545 The alternative is to track the order relationship of each node with 5546 respect to every other node. This can be accomplished by maintaining 5547 two sets of nodes at each node. The first set, Higher_Nodes, 5548 contains all nodes that are known to be ordered above the node. The 5549 second set, Lower_Nodes, contains all nodes that are known to be 5550 ordered below the node. This is the approach used in this algorithm. 5552 Set_Ear_Direction(ear_list, end_a, end_b, block_root) 5553 // Default of A_TO_B for the following cases: 5554 // (a) end_a and end_b are the same (root) 5555 // or (b) end_a is in end_b's Lower Nodes 5556 // or (c) end_a and end_b were unordered with respect to each 5557 // other 5558 direction = A_TO_B 5559 if (end_b is block_root) and (end_a is not end_b) 5560 direction = B_TO_A 5561 else if end_a is in end_b.Higher_Nodes 5562 direction = B_TO_A 5563 if direction is B_TO_A 5564 foreach interface i in ear_list 5565 i.UNDIRECTED = false 5566 i.INCOMING = true 5567 i.remote_intf.UNDIRECTED = false 5568 i.remote_intf.OUTGOING = true 5569 else 5570 foreach interface i in ear_list 5571 i.UNDIRECTED = false 5572 i.OUTGOING = true 5573 i.remote_intf.UNDIRECTED = false 5574 i.remote_intf.INCOMING = true 5575 if end_a is end_b 5576 return 5577 // Next, update all nodes' Lower_Nodes and Higher_Nodes 5578 if (end_a is in end_b.Higher_Nodes) 5579 foreach node x where x.localroot is block_root 5580 if end_a is in x.Lower_Nodes 5581 foreach interface i in ear_list 5582 add i.remote_node to x.Lower_Nodes 5583 if end_b is in x.Higher_Nodes 5584 foreach interface i in ear_list 5585 add i.local_node to x.Higher_Nodes 5586 else 5587 foreach node x where x.localroot is block_root 5588 if end_b is in x.Lower_Nodes 5589 foreach interface i in ear_list 5590 add i.local_node to x.Lower_Nodes 5591 if end_a is in x.Higher_Nodes 5592 foreach interface i in ear_list 5593 add i.remote_node to x.Higher_Nodes 5595 Figure 38: Algorithm to assign links of an ear direction 5597 A goal of the algorithm is to find the shortest cycles and ears. An 5598 ear is started by going to a neighbor x of an IN_GADAG node y. The 5599 path from x to an IN_GADAG node is minimal, since it is computed via 5600 SPF. Since a shortest path is made of shortest paths, to find the 5601 shortest ears requires reaching from the set of IN_GADAG nodes to the 5602 closest node that isn't IN_GADAG. Therefore, an ordered tree is 5603 maintained of interfaces that could be explored from the IN_GADAG 5604 nodes. The interfaces are ordered by their characteristics of 5605 metric, local loopback address, remote loopback address, and ifindex, 5606 as in the algorithm previously described in Figure 14. 5608 The algorithm ignores interfaces picked from the ordered tree that 5609 belong to the block root if the block in which the interface is 5610 present already has an ear that has been computed. This is necessary 5611 since we allow at most one incoming interface to a block root in each 5612 block. This requirement stems from the way next-hops are computed as 5613 was seen in Section 5.7. After any ear gets computed, we traverse 5614 the newly added nodes to the GADAG and insert interfaces whose far 5615 end is not yet on the GADAG to the ordered tree for later processing. 5617 Finally, cut-links are a special case because there is no point in 5618 doing an SPF on a block of 2 nodes. The algorithm identifies cut- 5619 links simply as links where both ends of the link are cut-vertices. 5620 Cut-links can simply be added to the GADAG with both OUTGOING and 5621 INCOMING specified on their interfaces. 5623 add_eligible_interfaces_of_node(ordered_intfs_tree,node) 5624 for each interface of node 5625 if intf.remote_node.IN_GADAG is false 5626 insert(intf,ordered_intfs_tree) 5628 check_if_block_has_ear(x,block_id) 5629 block_has_ear = false 5630 for all interfaces of x 5631 if ( (intf.remote_node.block_id == block_id) && 5632 intf.remote_node.IN_GADAG ) 5633 block_has_ear = true 5634 return block_has_ear 5636 Construct_GADAG_via_SPF(topology, root) 5637 Compute_Localroot (root,root) 5638 Assign_Block_ID(root,0) 5639 root.IN_GADAG = true 5640 add_eligible_interfaces_of_node(ordered_intfs_tree,root) 5641 while ordered_intfs_tree is not empty 5642 cand_intf = remove_lowest(ordered_intfs_tree) 5643 if cand_intf.remote_node.IN_GADAG is false 5644 if L(cand_intf.remote_node) == D(cand_intf.remote_node) 5645 // Special case for cut-links 5646 cand_intf.UNDIRECTED = false 5647 cand_intf.remote_intf.UNDIRECTED = false 5648 cand_intf.OUTGOING = true 5649 cand_intf.INCOMING = true 5650 cand_intf.remote_intf.OUTGOING = true 5651 cand_intf.remote_intf.INCOMING = true 5652 cand_intf.remote_node.IN_GADAG = true 5653 add_eligible_interfaces_of_node( 5654 ordered_intfs_tree,cand_intf.remote_node) 5655 else 5656 if (cand_intf.remote_node.local_root == 5657 cand_intf.local_node) && 5658 check_if_block_has_ear(cand_intf.local_node, 5659 cand_intf.remote_node.block_id)) 5660 /* Skip the interface since the block root 5661 already has an incoming interface in the 5662 block */ 5663 else 5664 ear_end = SPF_for_Ear(cand_intf.local_node, 5665 cand_intf.remote_node, 5666 cand_intf.remote_node.localroot, 5667 SPF method) 5668 y = ear_end.spf_prev_hop 5669 while y.local_node is not cand_intf.local_node 5670 add_eligible_interfaces_of_node( 5671 ordered_intfs_tree, y.local_node) 5672 y = y.local_node.spf_prev_intf 5674 Figure 39: SPF-based GADAG algorithm 5676 Appendix B. Option 3: Computing GADAG using a hybrid method 5678 In this option, the idea is to combine the salient features of the 5679 lowpoint inheritance and SPF methods. To this end, we process nodes 5680 as they get added to the GADAG just like in the lowpoint inheritance 5681 by maintaining a stack of nodes. This ensures that we do not need to 5682 maintain lower and higher sets at each node to ascertain ear 5683 directions since the ears will always be directed from the node being 5684 processed towards the end of the ear. To compute the ear however, we 5685 resort to an SPF to have the possibility of better ears (path 5686 lentghs) thus giving more flexibility than the restricted use of 5687 lowpoint/dfs parents. 5689 Regarding ears involving a block root, unlike the SPF method which 5690 ignored interfaces of the block root after the first ear, in the 5691 hybrid method we would have to process all interfaces of the block 5692 root before moving on to other nodes in the block since the direction 5693 of an ear is pre-determined. Thus, whenever the block already has an 5694 ear computed, and we are processing an interface of the block root, 5695 we mark the block root as unusable before the SPF run that computes 5696 the ear. This ensures that the SPF terminates at some node other 5697 than the block-root. This in turn guarantees that the block-root has 5698 only one incoming interface in each block, which is necessary for 5699 correctly computing the next-hops on the GADAG. 5701 As in the SPF gadag, bridge ears are handled as a special case. 5703 The entire algorithm is shown below in Figure 40 5705 find_spf_stack_ear(stack, x, y, xy_intf, block_root) 5706 if L(y) == D(y) 5707 // Special case for cut-links 5708 xy_intf.UNDIRECTED = false 5709 xy_intf.remote_intf.UNDIRECTED = false 5710 xy_intf.OUTGOING = true 5711 xy_intf.INCOMING = true 5712 xy_intf.remote_intf.OUTGOING = true 5713 xy_intf.remote_intf.INCOMING = true 5714 xy_intf.remote_node.IN_GADAG = true 5715 push y onto stack 5716 return 5717 else 5718 if (y.local_root == x) && 5719 check_if_block_has_ear(x,y.block_id) 5720 //Avoid the block root during the SPF 5721 Mark x as TEMP_UNUSABLE 5722 end_ear = SPF_for_Ear(x,y,block_root,hybrid) 5723 If x was set as TEMP_UNUSABLE, clear it 5724 cur = end_ear 5725 while (cur != y) 5726 intf = cur.spf_prev_hop 5727 prev = intf.local_node 5728 intf.UNDIRECTED = false 5729 intf.remote_intf.UNDIRECTED = false 5730 intf.OUTGOING = true 5731 intf.remote_intf.INCOMING = true 5732 push prev onto stack 5733 cur = prev 5734 xy_intf.UNDIRECTED = false 5735 xy_intf.remote_intf.UNDIRECTED = false 5736 xy_intf.OUTGOING = true 5737 xy_intf.remote_intf.INCOMING = true 5738 return 5740 Construct_GADAG_via_hybrid(topology,root) 5741 Compute_Localroot (root,root) 5742 Assign_Block_ID(root,0) 5743 root.IN_GADAG = true 5744 Initialize Stack to empty 5745 push root onto Stack 5746 while (Stack is not empty) 5747 x = pop(Stack) 5748 for each interface intf of x 5749 y = intf.remote_node 5750 if y.IN_GADAG is false 5751 find_spf_stack_ear(stack, x, y, intf, y.block_root) 5753 Figure 40: Hybrid GADAG algorithm 5755 Authors' Addresses 5757 Gabor Sandor Enyedi 5758 Ericsson 5759 Konyves Kalman krt 11 5760 Budapest 1097 5761 Hungary 5763 Email: Gabor.Sandor.Enyedi@ericsson.com 5765 Andras Csaszar 5766 Ericsson 5767 Konyves Kalman krt 11 5768 Budapest 1097 5769 Hungary 5771 Email: Andras.Csaszar@ericsson.com 5773 Alia Atlas 5774 Juniper Networks 5775 10 Technology Park Drive 5776 Westford, MA 01886 5777 USA 5779 Email: akatlas@juniper.net 5781 Chris Bowers 5782 Juniper Networks 5783 1194 N. Mathilda Ave. 5784 Sunnyvale, CA 94089 5785 USA 5787 Email: cbowers@juniper.net 5788 Abishek Gopalan 5789 University of Arizona 5790 1230 E Speedway Blvd. 5791 Tucson, AZ 85721 5792 USA 5794 Email: abishek@ece.arizona.edu