idnits 2.17.1 draft-ietf-rtgwg-mrt-frr-algorithm-08.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 28 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 (January 10, 2016) is 3022 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 1926, but not defined == Missing Reference: 'F' is mentioned on line 628, but not defined == Missing Reference: 'C' is mentioned on line 1926, but not defined == Missing Reference: 'G' is mentioned on line 1926, but not defined == Missing Reference: 'E' is mentioned on line 281, but not defined == Missing Reference: 'D' is mentioned on line 628, but not defined == Missing Reference: 'J' is mentioned on line 183, but not defined == Missing Reference: 'A' is mentioned on line 281, but not defined == Missing Reference: 'B' is mentioned on line 189, but not defined == Missing Reference: 'H' is mentioned on line 1334, but not defined == Missing Reference: 'K' is mentioned on line 628, but not defined == Missing Reference: 'N' is mentioned on line 628, but not defined == Missing Reference: 'X' is mentioned on line 1334, but not defined == Missing Reference: 'Y' is mentioned on line 1334, but not defined == Missing Reference: 'R-small' is mentioned on line 1293, but not defined == Missing Reference: 'R-great' is mentioned on line 1309, but not defined == Missing Reference: 'I' is mentioned on line 1926, but not defined == Unused Reference: 'RFC5120' is defined on line 3065, but no explicit reference was found in the text == Unused Reference: 'RFC7490' is defined on line 3071, but no explicit reference was found in the text == Outdated reference: A later version (-10) exists of draft-ietf-rtgwg-mrt-frr-architecture-07 Summary: 0 errors (**), 0 flaws (~~), 23 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: July 13, 2016 A. Atlas 6 C. Bowers 7 Juniper Networks 8 A. Gopalan 9 University of Arizona 10 January 10, 2016 12 An Algorithm for Computing Maximally Redundant Trees for IP/LDP Fast- 13 Reroute 14 draft-ietf-rtgwg-mrt-frr-algorithm-08 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 July 13, 2016. 42 Copyright Notice 44 Copyright (c) 2016 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 . . . . . . . . . . . . . . . . . . . 6 63 4.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 7 64 4.2. Finding an Ear and the Correct Direction . . . . . . . . 8 65 4.3. Low-Point Values and Their Uses . . . . . . . . . . . . . 11 66 4.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 14 67 4.5. Determining Local-Root and Assigning Block-ID . . . . . . 16 68 5. MRT Lowpoint Algorithm Specification . . . . . . . . . . . . 18 69 5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 18 70 5.2. MRT Island Identification . . . . . . . . . . . . . . . . 21 71 5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21 72 5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 22 73 5.5. Constructing the GADAG using lowpoint inheritance . . . . 23 74 5.6. Augmenting the GADAG by directing all links . . . . . . . 25 75 5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 29 76 5.7.1. MRT next-hops to all nodes ordered with respect to 77 the computing node . . . . . . . . . . . . . . . . . 29 78 5.7.2. MRT next-hops to all nodes not ordered with respect 79 to the computing node . . . . . . . . . . . . . . . . 30 80 5.7.3. Computing Redundant Tree next-hops in a 2-connected 81 Graph . . . . . . . . . . . . . . . . . . . . . . . . 31 82 5.7.4. Generalizing for a graph that isn't 2-connected . . . 33 83 5.7.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 34 84 5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 36 85 5.9. Named Proxy-Nodes . . . . . . . . . . . . . . . . . . . . 43 86 5.9.1. Determining Proxy-Node Attachment Routers . . . . . . 43 87 5.9.2. Computing if an Island Neighbor (IN) is loop-free . . 44 88 5.9.3. Computing MRT Next-Hops for Proxy-Nodes . . . . . . . 46 89 5.9.4. Computing MRT Alternates for Proxy-Nodes . . . . . . 52 90 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 60 91 7. Broadcast interfaces . . . . . . . . . . . . . . . . . . . . 60 92 7.1. Computing MRT next-hops on broadcast networks . . . . . . 61 93 7.2. Using MRT next-hops as alternates in the event of 94 failures on broadcast networks . . . . . . . . . . . . . 62 95 8. Evaluation of Alternative Methods for Constructing GADAGs . . 63 96 9. Implementation Status . . . . . . . . . . . . . . . . . . . . 64 97 10. Operational Considerations . . . . . . . . . . . . . . . . . 65 98 10.1. GADAG Root Selection . . . . . . . . . . . . . . . . . . 65 99 10.2. Destination-rooted GADAGs . . . . . . . . . . . . . . . 65 100 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 66 101 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 66 102 13. Security Considerations . . . . . . . . . . . . . . . . . . . 66 103 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 66 104 14.1. Normative References . . . . . . . . . . . . . . . . . . 66 105 14.2. Informative References . . . . . . . . . . . . . . . . . 66 106 Appendix A. Python Implementation of MRT Lowpoint Algorithm . . 67 107 Appendix B. Constructing a GADAG using SPFs . . . . . . . . . . 108 108 Appendix C. Constructing a GADAG using a hybrid method . . . . . 113 109 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 115 111 1. Introduction 113 MRT Fast-Reroute requires that packets can be forwarded not only on 114 the shortest-path tree, but also on two Maximally Redundant Trees 115 (MRTs), referred to as the MRT-Blue and the MRT-Red. A router which 116 experiences a local failure must also have pre-determined which 117 alternate to use. This document defines how to compute these three 118 things for use in MRT-FRR and describes the algorithm design 119 decisions and rationale. The algorithm is based on those presented 120 in [MRTLinear] and expanded in [EnyediThesis]. The MRT Lowpoint 121 algorithm is required for implementation when the Default MRT profile 122 is implemented. 124 Just as packets routed on a hop-by-hop basis require that each router 125 compute a shortest-path tree which is consistent, it is necessary for 126 each router to compute the MRT-Blue next-hops and MRT-Red next-hops 127 in a consistent fashion. This document defines the MRT Lowpoint 128 algorithm to be used as a standard in the default MRT profile for 129 MRT-FRR. 131 As now, a router's FIB will contain primary next-hops for the current 132 shortest-path tree for forwarding traffic. In addition, a router's 133 FIB will contain primary next-hops for the MRT-Blue for forwarding 134 received traffic on the MRT-Blue and primary next-hops for the MRT- 135 Red for forwarding received traffic on the MRT-Red. 137 What alternate next-hops a point-of-local-repair (PLR) selects need 138 not be consistent - but loops must be prevented. To reduce 139 congestion, it is possible for multiple alternate next-hops to be 140 selected; in the context of MRT alternates, each of those alternate 141 next-hops would be equal-cost paths. 143 This document defines an algorithm for selecting an appropriate MRT 144 alternate for consideration. Other alternates, e.g. LFAs that are 145 downstream paths, may be preferred when available. See the 146 Operational Considerations section of 147 [I-D.ietf-rtgwg-mrt-frr-architecture] for a more detailed discussion 148 of combining MRT alternates with those produced by other FRR 149 technologies. 151 [E]---[D]---| [E]<--[D]<--| [E]-->[D] 152 | | | | ^ | | 153 | | | V | | V 154 [R] [F] [C] [R] [F] [C] [R] [F] [C] 155 | | | ^ ^ | | 156 | | | | | V | 157 [A]---[B]---| [A]-->[B] [A]---[B]<--| 159 (a) (b) (c) 160 a 2-connected graph MRT-Blue towards R MRT-Red towards R 162 Figure 1 164 The MRT Lowpoint algorithm can handle arbitrary network topologies 165 where the whole network graph is not 2-connected, as in Figure 2, as 166 well as the easier case where the network graph is 2-connected 167 (Figure 1). Each MRT is a spanning tree. The pair of MRTs provide 168 two paths from every node X to the root of the MRTs. Those paths 169 share the minimum number of nodes and the minimum number of links. 170 Each such shared node is a cut-vertex. Any shared links are cut- 171 links. 173 [E]---[D]---| |---[J] 174 | | | | | 175 | | | | | 176 [R] [F] [C]---[G] | 177 | | | | | 178 | | | | | 179 [A]---[B]---| |---[H] 181 (a) a graph that isn't 2-connected 183 [E]<--[D]<--| [J] [E]-->[D]---| |---[J] 184 | ^ | | | | | ^ 185 V | | | V V V | 186 [R] [F] [C]<--[G] | [R] [F] [C]<--[G] | 187 ^ ^ ^ | ^ | | | 188 | | | V | V | | 189 [A]-->[B]---| |---[H] [A]<--[B]<--| [H] 191 (b) MRT-Blue towards R (c) MRT-Red towards R 193 Figure 2 195 2. Requirements Language 197 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 198 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 199 document are to be interpreted as described in [RFC2119]. 201 3. Terminology and Definitions 203 Please see the Terminology section of 204 [I-D.ietf-rtgwg-mrt-frr-architecture] for a complete list of 205 terminology relevant to this draft. The list below does not repeat 206 terminology introduced in that draft. 208 spanning tree: A tree containing links that connects all nodes in 209 the network graph. 211 back-edge: In the context of a spanning tree computed via a depth- 212 first search, a back-edge is a link that connects a descendant of 213 a node x with an ancestor of x. 215 partial ADAG: A subset of an ADAG that doesn't yet contain all the 216 nodes in the block. A partial ADAG is created during the MRT 217 algorithm and then expanded until all nodes in the block are 218 included and it is an ADAG. 220 DFS: Depth-First Search 221 DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS- 222 tree path from the DFS root to x. 224 DFS descendant: A node n is a DFS descendant of x if x is on the 225 DFS-tree path from the DFS root to n. 227 ear: A path along not-yet-included-in-the-GADAG nodes that starts 228 at a node that is already-included-in-the-GADAG and that ends at a 229 node that is already-included-in-the-GADAG. The starting and 230 ending nodes may be the same node if it is a cut-vertex. 232 X >> Y or Y << X: Indicates the relationship between X and Y in a 233 partial order, such as found in a GADAG. X >> Y means that X is 234 higher in the partial order than Y. Y << X means that Y is lower 235 in the partial order than X. 237 X > Y or Y < X: Indicates the relationship between X and Y in the 238 total order, such as found via a topological sort. X > Y means 239 that X is higher in the total order than Y. Y < X means that Y is 240 lower in the total order than X. 242 X ?? Y: Indicates that X is unordered with respect to Y in the 243 partial order. 245 UNDIRECTED: In the GADAG, each link is marked as OUTGOING, INCOMING 246 or both. Until the directionality of the link is determined, the 247 link is marked as UNDIRECTED to indicate that its direction hasn't 248 been determined. 250 OUTGOING: A link marked as OUTGOING has direction in the GADAG from 251 the interface's router to the remote end. 253 INCOMING: A link marked as INCOMING has direction in the GADAG from 254 the remote end to the interface's router. 256 4. Algorithm Key Concepts 258 There are five key concepts that are critical for understanding the 259 MRT Lowpoint algorithm. The first is the idea of partially ordering 260 the nodes in a network graph with regard to each other and to the 261 GADAG root. The second is the idea of finding an ear of nodes and 262 adding them in the correct direction. The third is the idea of a 263 Low-Point value and how it can be used to identify cut-vertices and 264 to find a second path towards the root. The fourth is the idea that 265 a non-2-connected graph is made up of blocks, where a block is a 266 2-connected cluster, a cut-link or an isolated node. The fifth is 267 the idea of a local-root for each node; this is used to compute ADAGs 268 in each block. 270 4.1. Partial Ordering for Disjoint Paths 272 Given any two nodes X and Y in a graph, a particular total order 273 means that either X < Y or X > Y in that total order. An example 274 would be a graph where the nodes are ranked based upon their unique 275 IP loopback addresses. In a partial order, there may be some nodes 276 for which it can't be determined whether X << Y or X >> Y. A partial 277 order can be captured in a directed graph, as shown in Figure 3. In 278 a graphical representation, a link directed from X to Y indicates 279 that X is a neighbor of Y in the network graph and X << Y. 281 [A]<---[R] [E] R << A << B << C << D << E 282 | ^ R << A << B << F << G << H << D << E 283 | | 284 V | Unspecified Relationships: 285 [B]--->[C]--->[D] C and F 286 | ^ C and G 287 | | C and H 288 V | 289 [F]--->[G]--->[H] 291 Figure 3: Directed Graph showing a Partial Order 293 To compute MRTs, the root of the MRTs is at both the very bottom and 294 the very top of the partial ordering. This means that from any node 295 X, one can pick nodes higher in the order until the root is reached. 296 Similarly, from any node X, one can pick nodes lower in the order 297 until the root is reached. For instance, in Figure 4, from G the 298 higher nodes picked can be traced by following the directed links and 299 are H, D, E and R. Similarly, from G the lower nodes picked can be 300 traced by reversing the directed links and are F, B, A, and R. A 301 graph that represents this modified partial order is no longer a DAG; 302 it is termed an Almost DAG (ADAG) because if the links directed to 303 the root were removed, it would be a DAG. 305 [A]<---[R]<---[E] R << A << B << C << R 306 | ^ ^ R << A << B << C << D << E << R 307 | | | R << A << B << F << G << H << D << E << R 308 V | | 309 [B]--->[C]--->[D] Unspecified Relationships: 310 | ^ C and F 311 | | C and G 312 V | C and H 313 [F]--->[G]--->[H] 315 Figure 4: ADAG showing a Partial Order with R lowest and highest 317 Most importantly, if a node Y >> X, then Y can only appear on the 318 increasing path from X to the root and never on the decreasing path. 319 Similarly, if a node Z << X, then Z can only appear on the decreasing 320 path from X to the root and never on the inceasing path. 322 When following the increasing paths, it is possible to pick multiple 323 higher nodes and still have the certainty that those paths will be 324 disjoint from the decreasing paths. E.g. in the previous example 325 node B has multiple possibilities to forward packets along an 326 increasing path: it can either forward packets to C or F. 328 4.2. Finding an Ear and the Correct Direction 330 For simplicity, the basic idea of creating a GADAG by adding ears is 331 described assuming that the network graph is a single 2-connected 332 cluster so that an ADAG is sufficient. Generalizing to multiple 333 blocks is done by considering the block-roots instead of the GADAG 334 root - and the actual algorithm is given in Section 5.5. 336 In order to understand the basic idea of finding an ADAG, first 337 suppose that we have already a partial ADAG, which doesn't contain 338 all the nodes in the block yet, and we want to extend it to cover all 339 the nodes. Suppose that we find a path from a node X to Y such that 340 X and Y are already contained by our partial ADAG, but all the 341 remaining nodes along the path are not added to the ADAG yet. We 342 refer to such a path as an ear. 344 Recall that our ADAG is closely related to a partial order. More 345 precisely, if we remove root R, the remaining DAG describes a partial 346 order of the nodes. If we suppose that neither X nor Y is the root, 347 we may be able to compare them. If one of them is definitely lesser 348 with respect to our partial order (say X<B---| A-->B---| 360 (a) (b) (c) 362 (a) A 2-connected graph 363 (b) Partial ADAG (C is not included) 364 (c) Resulting ADAG after adding path (or ear) B-C-D 366 Figure 5 368 In this partial ADAG, node C is not yet included. However, we can 369 find path B-C-D, where both endpoints are contained by this partial 370 ADAG (we say those nodes are "ready" in the following text), and the 371 remaining node (node C) is not contained yet. If we remove R, the 372 remaining DAG defines a partial order, and with respect to this 373 partial order we can say that B<C and C->D are added). If 375 B >> D, we would add the same path in reverse direction. 377 If in the partial order where an ear's two ends are X and Y, X << Y, 378 then there must already be a directed path from X to Y in the ADAG. 379 The ear must be added in a direction such that it doesn't create a 380 cycle; therefore the ear must go from X to Y. 382 In the case, when X and Y are not ordered with each other, we can 383 select either direction for the ear. We have no restriction since 384 neither of the directions can result in a cycle. In the corner case 385 when one of the endpoints of an ear, say X, is the root (recall that 386 the two endpoints must be different), we could use both directions 387 again for the ear because the root can be considered both as smaller 388 and as greater than Y. However, we strictly pick that direction in 389 which the root is lower than Y. The logic for this decision is 390 explained in Section 5.7 392 A partial ADAG is started by finding a cycle from the root R back to 393 itself. This can be done by selecting a non-ready neighbor N of R 394 and then finding a path from N to R that doesn't use any links 395 between R and N. The direction of the cycle can be assigned either 396 way since it is starting the ordering. 398 Once a partial ADAG is already present, it will always have a node 399 that is not the root R in it. As a brief proof that a partial ADAG 400 can always have ears added to it: just select a non-ready neighbor N 401 of a ready node Q, such that Q is not the root R, find a path from N 402 to the root R in the graph with Q removed. This path is an ear where 403 the first node of the ear is Q, the next is N, then the path until 404 the first ready node the path reached (that ready node is the other 405 endpoint of the path). Since the graph is 2-connected, there must be 406 a path from N to R without Q. 408 It is always possible to select a non-ready neighbor N of a ready 409 node Q so that Q is not the root R. Because the network is 410 2-connected, N must be connected to two different nodes and only one 411 can be R. Because the initial cycle has already been added to the 412 ADAG, there are ready nodes that are not R. Since the graph is 413 2-connected, while there are non-ready nodes, there must be a non- 414 ready neighbor N of a ready node that is not R. 416 Generic_Find_Ears_ADAG(root) 417 Create an empty ADAG. Add root to the ADAG. 418 Mark root as IN_GADAG. 419 Select an arbitrary cycle containing root. 420 Add the arbitrary cycle to the ADAG. 421 Mark cycle's nodes as IN_GADAG. 422 Add cycle's non-root nodes to process_list. 423 while there exists connected nodes in graph that are not IN_GADAG 424 Select a new ear. Let its endpoints be X and Y. 425 if Y is root or (Y << X) 426 add the ear towards X to the ADAG 427 else // (a) X is root or (b)X << Y or (c) X, Y not ordered 428 Add the ear towards Y to the ADAG 430 Figure 6: Generic Algorithm to find ears and their direction in 431 2-connected graph 433 The algorithm in Figure 6 merely requires that a cycle or ear be 434 selected without specifying how. Regardless of the method for 435 selecting the path, we will get an ADAG. The method used for finding 436 and selecting the ears is important; shorter ears result in shorter 437 paths along the MRTs. The MRT Lowpoint algorithm uses the Low-Point 438 Inheritance method for constructing an ADAG (and ultimately a GADAG). 439 This method is defined in Section 5.5. Other methods for 440 constructing GADAGs are described in Appendix B and Appendix C. An 441 evaluation of these different methods is given in Section 8 443 As an example, consider Figure 5 again. First, we select the 444 shortest cycle containing R, which can be R-A-B-F-D-E (uniform link 445 costs were assumed), so we get to the situation depicted in Figure 5 446 (b). Finally, we find a node next to a ready node; that must be node 447 C and assume we reached it from ready node B. We search a path from 448 C to R without B in the original graph. The first ready node along 449 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 451 this point. 453 4.3. Low-Point Values and Their Uses 455 A basic way of computing a spanning tree on a network graph is to run 456 a depth-first-search, such as given in Figure 7. This tree has the 457 important property that if there is a link (x, n), then either n is a 458 DFS ancestor of x or n is a DFS descendant of x. In other words, 459 either n is on the path from the root to x or x is on the path from 460 the root to n. 462 global_variable: dfs_number 464 DFS_Visit(node x, node parent) 465 D(x) = dfs_number 466 dfs_number += 1 467 x.dfs_parent = parent 468 for each link (x, w) 469 if D(w) is not set 470 DFS_Visit(w, x) 472 Run_DFS(node gadag_root) 473 dfs_number = 0 474 DFS_Visit(gadag_root, NONE) 476 Figure 7: Basic Depth-First Search algorithm 478 Given a node x, one can compute the minimal DFS number of the 479 neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the 480 earliest attachment point neighbouring x. What is interesting, 481 though, is what is the earliest attachment point from x and x's 482 descendants. This is what is determined by computing the Low-Point 483 value. 485 In order to compute the low point value, the network is traversed 486 using DFS and the vertices are numbered based on the DFS walk. Let 487 this number be represented as DFS(x). All the edges that lead to 488 already visited nodes during DFS walk are back-edges. The back-edges 489 are important because they give information about reachability of a 490 node via another path. 492 The low point number is calculated by finding: 494 Low(x) = Minimum of ( (DFS(x), 495 Lowest DFS(n, x->n is a back-edge), 496 Lowest Low(n, x->n is tree edge in DFS walk) ). 498 A detailed algorithm for computing the low-point value is given in 499 Figure 8. Figure 9 illustrates how the lowpoint algorithm applies to 500 a example graph. 502 global_variable: dfs_number 504 Lowpoint_Visit(node x, node parent, interface p_to_x) 505 D(x) = dfs_number 506 L(x) = D(x) 507 dfs_number += 1 508 x.dfs_parent = parent 509 x.dfs_parent_intf = p_to_x.remote_intf 510 x.lowpoint_parent = NONE 511 for each ordered_interface intf of x 512 if D(intf.remote_node) is not set 513 Lowpoint_Visit(intf.remote_node, x, intf) 514 if L(intf.remote_node) < L(x) 515 L(x) = L(intf.remote_node) 516 x.lowpoint_parent = intf.remote_node 517 x.lowpoint_parent_intf = intf 518 else if intf.remote_node is not parent 519 if D(intf.remote_node) < L(x) 520 L(x) = D(intf.remote_node) 521 x.lowpoint_parent = intf.remote_node 522 x.lowpoint_parent_intf = intf 524 Run_Lowpoint(node gadag_root) 525 dfs_number = 0 526 Lowpoint_Visit(gadag_root, NONE, NONE) 528 Figure 8: Computing Low-Point value 530 [E]---| [J]-------[I] [P]---[O] 531 | | | | | | 532 | | | | | | 533 [R] [D]---[C]--[F] [H]---[K] [N] 534 | | | | | | 535 | | | | | | 536 [A]--------[B] [G]---| [L]---[M] 538 (a) a non-2-connected graph 540 [E]----| [J]---------[I] [P]------[O] 541 (5, ) | (10, ) (9, ) (16, ) (15, ) 542 | | | | | | 543 | | | | | | 544 [R] [D]---[C]---[F] [H]----[K] [N] 545 (0, ) (4, ) (3, ) (6, ) (8, ) (11, ) (14, ) 546 | | | | | | 547 | | | | | | 548 [A]---------[B] [G]----| [L]------[M] 549 (1, ) (2, ) (7, ) (12, ) (13, ) 551 (b) with DFS values assigned (D(x), L(x)) 553 [E]----| [J]---------[I] [P]------[O] 554 (5,0) | (10,3) (9,3) (16,11) (15,11) 555 | | | | | | 556 | | | | | | 557 [R] [D]---[C]---[F] [H]----[K] [N] 558 (0,0) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11) 559 | | | | | | 560 | | | | | | 561 [A]---------[B] [G]----| [L]------[M] 562 (1,0) (2,0) (7,3) (12,11) (13,11) 564 (c) with low-point values assigned (D(x), L(x)) 566 Figure 9: Example lowpoint value computation 568 From the low-point value and lowpoint parent, there are three very 569 useful things which motivate our computation. 571 First, if there is a child c of x such that L(c) >= D(x), then there 572 are no paths in the network graph that go from c or its descendants 573 to an ancestor of x - and therefore x is a cut-vertex. In Figure 9, 574 this can be seen by looking at the DFS children of C. C has two 575 children - D and F and L(F) = 3 = D(C) so it is clear that C is a 576 cut-vertex and F is in a block where C is the block's root. L(D) = 0 577 < 3 = D(C) so D has a path to the ancestors of C; in this case, D can 578 go via E to reach R. Comparing the low-point values of all a node's 579 DFS-children with the node's DFS-value is very useful because it 580 allows identification of the cut-vertices and thus the blocks. 582 Second, by repeatedly following the path given by lowpoint_parent, 583 there is a path from x back to an ancestor of x that does not use the 584 link [x, x.dfs_parent] in either direction. The full path need not 585 be taken, but this gives a way of finding an initial cycle and then 586 ears. 588 Third, as seen in Figure 9, even if L(x) < D(x), there may be a block 589 that contains both the root and a DFS-child of a node while other 590 DFS-children might be in different blocks. In this example, C's 591 child D is in the same block as R while F is not. It is important to 592 realize that the root of a block may also be the root of another 593 block. 595 4.4. Blocks in a Graph 597 A key idea for the MRT Lowpoint algorithm is that any non-2-connected 598 graph is made up by blocks (e.g. 2-connected clusters, cut-links, 599 and/or isolated nodes). To compute GADAGs and thus MRTs, computation 600 is done in each block to compute ADAGs or Redundant Trees and then 601 those ADAGs or Redundant Trees are combined into a GADAG or MRT. 603 [E]---| [J]-------[I] [P]---[O] 604 | | | | | | 605 | | | | | | 606 [R] [D]---[C]--[F] [H]---[K] [N] 607 | | | | | | 608 | | | | | | 609 [A]--------[B] [G]---| [L]---[M] 611 (a) A graph with four blocks that are: 612 three 2-connected clusters 613 and one cut-link 615 [E]<--| [J]<------[I] [P]<--[O] 616 | | | ^ | ^ 617 V | V | V | 618 [R] [D]<--[C] [F] [H]<---[K] [N] 619 ^ | ^ ^ 620 | V | | 621 [A]------->[B] [G]---| [L]-->[M] 623 (b) MRT-Blue for destination R 625 [E]---| [J]-------->[I] [P]-->[O] 626 | | | 627 V V V 628 [R] [D]-->[C]<---[F] [H]<---[K] [N] 629 ^ | ^ | ^ | 630 | V | | | V 631 [A]<-------[B] [G]<--| [L]<--[M] 633 (c) MRT-Red for destination R 635 Figure 10 637 Consider the example depicted in Figure 10 (a). In this figure, a 638 special graph is presented, showing us all the ways 2-connected 639 clusters can be connected. It has four blocks: block 1 contains R, 640 A, B, C, D, E, block 2 contains C, F, G, H, I, J, block 3 contains K, 641 L, M, N, O, P, and block 4 is a cut-link containing H and K. As can 642 be observed, the first two blocks have one common node (node C) and 643 blocks 2 and 3 do not have any common node, but they are connected 644 through a cut-link that is block 4. No two blocks can have more than 645 one common node, since two blocks with at least two common nodes 646 would qualify as a single 2-connected cluster. 648 Moreover, observe that if we want to get from one block to another, 649 we must use a cut-vertex (the cut-vertices in this graph are C, H, 650 K), regardless of the path selected, so we can say that all the paths 651 from block 3 along the MRTs rooted at R will cross K first. This 652 observation means that if we want to find a pair of MRTs rooted at R, 653 then we need to build up a pair of RTs in block 3 with K as a root. 654 Similarly, we need to find another pair of RTs in block 2 with C as a 655 root, and finally, we need the last pair of RTs in block 1 with R as 656 a root. When all the trees are selected, we can simply combine them; 657 when a block is a cut-link (as in block 4), that cut-link is added in 658 the same direction to both of the trees. The resulting trees are 659 depicted in Figure 10 (b) and (c). 661 Similarly, to create a GADAG it is sufficient to compute ADAGs in 662 each block and connect them. 664 It is necessary, therefore, to identify the cut-vertices, the blocks 665 and identify the appropriate local-root to use for each block. 667 4.5. Determining Local-Root and Assigning Block-ID 669 Each node in a network graph has a local-root, which is the cut- 670 vertex (or root) in the same block that is closest to the root. The 671 local-root is used to determine whether two nodes share a common 672 block. 674 Compute_Localroot(node x, node localroot) 675 x.localroot = localroot 676 for each DFS child node c of x 677 if L(c) < D(x) //x is not a cut-vertex 678 Compute_Localroot(c, x.localroot) 679 else 680 mark x as cut-vertex 681 Compute_Localroot(c, x) 683 Compute_Localroot(gadag_root, gadag_root) 685 Figure 11: A method for computing local-roots 687 There are two different ways of computing the local-root for each 688 node. The stand-alone method is given in Figure 11 and better 689 illustrates the concept; it is used by the GADAG construction methods 690 given in Appendix B and Appendix C. The MRT Lowpoint algorithm 691 computes the local-root for a block as part of computing the GADAG 692 using lowpoint inheritance; the essence of this computation is given 693 in Figure 12. Both methods for computing the local-root produce the 694 same results. 696 Get the current node, s. 697 Compute an ear(either through lowpoint inheritance 698 or by following dfs parents) from s to a ready node e. 699 (Thus, s is not e, if there is such ear.) 700 if s is e 701 for each node x in the ear that is not s 702 x.localroot = s 703 else 704 for each node x in the ear that is not s or e 705 x.localroot = e.localroot 707 Figure 12: Ear-based method for computing local-roots 709 Once the local-roots are known, two nodes X and Y are in a common 710 block if and only if one of the following three conditions apply. 712 o Y's local-root is X's local-root : They are in the same block and 713 neither is the cut-vertex closest to the root. 715 o Y's local-root is X: X is the cut-vertex closest to the root for 716 Y's block 718 o Y is X's local-root: Y is the cut-vertex closest to the root for 719 X's block 721 Once we have computed the local-root for each node in the network 722 graph, we can assign for each node, a block id that represents the 723 block in which the node is present. This computation is shown in 724 Figure 13. 726 global_var: max_block_id 728 Assign_Block_ID(x, cur_block_id) 729 x.block_id = cur_block_id 730 foreach DFS child c of x 731 if (c.local_root is x) 732 max_block_id += 1 733 Assign_Block_ID(c, max_block_id) 734 else 735 Assign_Block_ID(c, cur_block_id) 737 max_block_id = 0 738 Assign_Block_ID(gadag_root, max_block_id) 740 Figure 13: Assigning block id to identify blocks 742 5. MRT Lowpoint Algorithm Specification 744 The MRT Lowpoint algorithm computes one GADAG that is then used by a 745 router to determine its MRT-Blue and MRT-Red next-hops to all 746 destinations. Finally, based upon that information, alternates are 747 selected for each next-hop to each destination. The different parts 748 of this algorithm are described below. 750 o Order the interfaces in the network graph. [See Section 5.1] 752 o Compute the local MRT Island for the particular MRT Profile. [See 753 Section 5.2] 755 o Select the root to use for the GADAG. [See Section 5.3] 757 o Initialize all interfaces to UNDIRECTED. [See Section 5.4] 759 o Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See 760 Figure 8] 762 o Construct the GADAG. [See Section 5.5] 764 o Assign directions to all interfaces that are still UNDIRECTED. 765 [See Section 5.6] 767 o From the computing router x, compute the next-hops for the MRT- 768 Blue and MRT-Red. [See Section 5.7] 770 o Identify alternates for each next-hop to each destination by 771 determining which one of the blue MRT and the red MRT the 772 computing router x should select. [See Section 5.8] 774 A Python implementation of this algorithm is given in Appendix A. 776 5.1. Interface Ordering 778 To ensure consistency in computation, all routers MUST order 779 interfaces identically down to the set of links with the same metric 780 to the same neighboring node. This is necessary for the DFS in 781 Lowpoint_Visit in Section 4.3, where the selection order of the 782 interfaces to explore results in different trees. Consistent 783 interface ordering is also necessary for computing the GADAG, where 784 the selection order of the interfaces to use to form ears can result 785 in different GADAGs. It is also necessary for the topological sort 786 described in Section 5.8, where different topological sort orderings 787 can result in undirected links being added to the GADAG in different 788 directions. 790 The required ordering between two interfaces from the same router x 791 is given in Figure 14. 793 Interface_Compare(interface a, interface b) 794 if a.metric < b.metric 795 return A_LESS_THAN_B 796 if b.metric < a.metric 797 return B_LESS_THAN_A 798 if a.neighbor.mrt_node_id < b.neighbor.mrt_node_id 799 return A_LESS_THAN_B 800 if b.neighbor.mrt_node_id < a.neighbor.mrt_node_id 801 return B_LESS_THAN_A 802 // Same metric to same node, so the order doesn't matter for 803 // interoperability. 804 return A_EQUAL_TO_B 806 Figure 14: Rules for ranking multiple interfaces. Order is from low 807 to high. 809 In Figure 14, if two interfaces on a router connect to the same 810 remote router with the same metric, the Interface_Compare function 811 returns A_EQUAL_TO_B. This is because the order in which those 812 interfaces are initially explored does not affect the final GADAG 813 produced by the algorithm described here. While only one of the 814 links will be added to the GADAG in the initial traversal, the other 815 parallel links will be added to the GADAG with the same direction 816 assigned during the procedure for assigning direction to UNDIRECTED 817 links described in Section 5.6. An implementation is free to apply 818 some additional criteria to break ties in interface ordering in this 819 situation, but that criteria is not specified here since it will not 820 affect the final GADAG produced by the algorithm. 822 The Interface_Compare function in Figure 14 relies on the 823 interface.metric and the interface.neighbor.mrt_node_id values to 824 order interfaces. The exact source of these values for different 825 IGPs and applications is specified in Figure 15. The metric and 826 mrt_node_id values for OSPFv2, OSPFv3, and IS-IS provided here is 827 normative. The metric and mrt_node_id values for ISIS-PCR in this 828 table should be considered informational. The normative values are 829 specified in [IEEE8021Qca] . 831 +--------------+-----------------------+-----------------------------+ 832 | IGP/flooding | mrt_node_id | metric of | 833 | protocol | of neighbor | interface | 834 | and | on interface | | 835 | application | | | 836 +--------------+-----------------------+-----------------------------+ 837 | OSPFv2 for | 4 octet Neighbor | 2 octet Metric field | 838 | IP/LDP FRR | Router ID in | for corresponding | 839 | | Link ID field for | point-to-point link | 840 | | corresponding | in Router-LSA | 841 | | point-to-point link | | 842 | | in Router-LSA | | 843 +--------------+-----------------------+-----------------------------+ 844 | OSPFv3 for | 4 octet Neighbor | 2 octet Metric field | 845 | IP/LDP FRR | Router ID field | for corresponding | 846 | | for corresponding | point-to-point link | 847 | | point-to-point link | in Router-LSA | 848 | | in Router-LSA | | 849 +--------------+-----------------------+-----------------------------+ 850 | IS-IS for | 7 octet neighbor | 3 octet metric field | 851 | IP/LDP FRR | system ID and | in Extended IS | 852 | | pseudonode number | Reachability TLV #22 | 853 | | in Extended IS | or Multi-Topology | 854 | | Reachability TLV #22 | IS Neighbor TLV #222 | 855 | | or Multi-Topology | | 856 | | IS Neighbor TLV #222 | | 857 +--------------+-----------------------+-----------------------------+ 858 | ISIS-PCR for | 8 octet Bridge ID | 3 octet SPB-LINK-METRIC in | 859 | protection | created from 2 octet | SPB-Metric sub-TLV (type 29)| 860 | of traffic | Bridge Priority in | in Extended IS Reachability | 861 | in bridged | SPB Instance sub-TLV | TLV #22 or Multi-Topology | 862 | networks | (type 1) carried in | Intermediate Systems | 863 | | MT-Capability TLV | TLV #222. In the case | 864 | | #144 and 6 octet | of asymmetric link metrics, | 865 | | neighbor system ID in | the larger link metric | 866 | | Extended IS | is used for both link | 867 | | Reachability TLV #22 | directions. | 868 | | or Multi-Topology | (informational) | 869 | | Intermediate Systems | | 870 | | TLV #222 | | 871 | | (informational) | | 872 +--------------+-----------------------+-----------------------------+ 874 Figure 15: value of interface.neighbor.mrt_node_id and 875 interface.metric to be used for ranking interfaces, for different 876 flooding protocols and applications 878 The metrics are unsigned integers and MUST be compared as unsigned 879 integers. The results of mrt_node_id comparisons MUST be the same as 880 would be obtained by converting the mrt_node_ids to unsigned integers 881 using network byte order and performing the comparison as unsigned 882 integers. In the case of IS-IS for IP/LDP FRR with point-to-point 883 links, the pseudonode number (the 7th octet) is zero. Broadcast 884 interfaces will be discussed in Section 7. 886 5.2. MRT Island Identification 888 The local MRT Island for a particular MRT profile can be determined 889 by starting from the computing router in the network graph and doing 890 a breadth-first-search (BFS). The BFS explores only links that are 891 in the same area/level, are not IGP-excluded, and are not MRT- 892 ineligible. The BFS explores only nodes that are are not IGP- 893 excluded, and that support the particular MRT profile. See section 7 894 of [I-D.ietf-rtgwg-mrt-frr-architecture] for more precise definitions 895 of these criteria. 897 MRT_Island_Identification(topology, computing_rtr, profile_id, area) 898 for all routers in topology 899 rtr.IN_MRT_ISLAND = FALSE 900 computing_rtr.IN_MRT_ISLAND = TRUE 901 explore_list = { computing_rtr } 902 while (explore_list is not empty) 903 next_rtr = remove_head(explore_list) 904 for each intf in next_rtr 905 if (not intf.MRT-ineligible 906 and not intf.remote_intf.MRT-ineligible 907 and not intf.IGP-excluded and (intf in area) 908 and (intf.remote_node supports profile_id) ) 909 intf.IN_MRT_ISLAND = TRUE 910 intf.remote_node.IN_MRT_ISLAND = TRUE 911 if (not intf.remote_node.IN_MRT_ISLAND)) 912 intf.remote_node.IN_MRT_ISLAND = TRUE 913 add_to_tail(explore_list, intf.remote_node) 915 Figure 16: MRT Island Identification 917 5.3. GADAG Root Selection 919 In Section 8.3 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG 920 Root Selection Policy is described for the MRT default profile. This 921 selection policy allows routers to consistently select a common GADAG 922 Root inside the local MRT Island, based on advertised priority 923 values. The MRT Lowpoint algorithm simply requires that all routers 924 in the MRT Island MUST select the same GADAG Root; the mechanism can 925 vary based upon the MRT profile description. Before beginning 926 computation, the network graph is reduced to contain only the set of 927 routers that support the specific MRT profile whose MRTs are being 928 computed. 930 As noted in Section 7, pseudonodes MUST NOT be considered for GADAG 931 root selection. 933 It is expected that an operator will designate a set of routers as 934 good choices for selection as GADAG root by setting the GADAG Root 935 Selection Priority for that set of routers to lower (more preferred) 936 numerical values. For guidance on setting the GADAG Root Selection 937 Priority values, refer to Section 10.1. 939 5.4. Initialization 941 Before running the algorithm, there is the standard type of 942 initialization to be done, such as clearing any computed DFS-values, 943 lowpoint-values, DFS-parents, lowpoint-parents, any MRT-computed 944 next-hops, and flags associated with algorithm. 946 It is assumed that a regular SPF computation has been run so that the 947 primary next-hops from the computing router to each destination are 948 known. This is required for determining alternates at the last step. 950 Initially, all interfaces MUST be initialized to UNDIRECTED. Whether 951 they are OUTGOING, INCOMING or both is determined when the GADAG is 952 constructed and augmented. 954 It is possible that some links and nodes will be marked using 955 standard IGP mechanisms to discourage or prevent transit traffic. 956 Section 7.3.1 of [I-D.ietf-rtgwg-mrt-frr-architecture] describes how 957 those links and nodes are excluded from MRT Island formation. 959 MRT-FRR also has the ability to advertise links MRT-Ineligible, as 960 described in Section 7.3.2 of [I-D.ietf-rtgwg-mrt-frr-architecture]. 961 These links are excluded from the MRT Island and the GADAG. 962 Computation of MRT next-hops will therefore not use any MRT- 963 ineligible links. The MRT algorithm does still need to consider MRT- 964 ineligible links when computing FRR alternates, because an MRT- 965 ineligible link can still be the shortest-path next-hop to reach a 966 destination. 968 When a broadcast interface is advertised as MRT-ineligible, then the 969 pseudo-node representing the entire broadcast network MUST NOT be 970 included in the MRT Island. This is equivalent to excluding all of 971 the broadcast interfaces on that broadcast network from the MRT 972 Island. 974 5.5. Constructing the GADAG using lowpoint inheritance 976 As discussed in Section 4.2, it is necessary to find ears from a node 977 x that is already in the GADAG (known as IN_GADAG). Two different 978 methods are used to find ears in the algorithm. The first is by 979 going to a not IN_GADAG DFS-child and then following the chain of 980 low-point parents until an IN_GADAG node is found. The second is by 981 going to a not IN_GADAG neighbor and then following the chain of DFS 982 parents until an IN_GADAG node is found. As an ear is found, the 983 associated interfaces are marked based on the direction taken. The 984 nodes in the ear are marked as IN_GADAG. In the algorithm, first the 985 ears via DFS-children are found and then the ears via DFS-neighbors 986 are found. 988 By adding both types of ears when an IN_GADAG node is processed, all 989 ears that connect to that node are found. The order in which the 990 IN_GADAG nodes is processed is, of course, key to the algorithm. The 991 order is a stack of ears so the most recent ear is found at the top 992 of the stack. Of course, the stack stores nodes and not ears, so an 993 ordered list of nodes, from the first node in the ear to the last 994 node in the ear, is created as the ear is explored and then that list 995 is pushed onto the stack. 997 Each ear represents a partial order (see Figure 4) and processing the 998 nodes in order along each ear ensures that all ears connecting to a 999 node are found before a node higher in the partial order has its ears 1000 explored. This means that the direction of the links in the ear is 1001 always from the node x being processed towards the other end of the 1002 ear. Additionally, by using a stack of ears, this means that any 1003 unprocessed nodes in previous ears can only be ordered higher than 1004 nodes in the ears below it on the stack. 1006 In this algorithm that depends upon Low-Point inheritance, it is 1007 necessary that every node have a low-point parent that is not itself. 1008 If a node is a cut-vertex, that may not yet be the case. Therefore, 1009 any nodes without a low-point parent will have their low-point parent 1010 set to their DFS parent and their low-point value set to the DFS- 1011 value of their parent. This assignment also properly allows an ear 1012 between two cut-vertices. 1014 Finally, the algorithm simultaneously computes each node's local- 1015 root, as described in Figure 12. This is further elaborated as 1016 follows. The local-root can be inherited from the node at the end of 1017 the ear unless the end of the ear is x itself, in which case the 1018 local-root for all the nodes in the ear would be x. This is because 1019 whenever the first cycle is found in a block, or an ear involving a 1020 bridge is computed, the cut-vertex closest to the root would be x 1021 itself. In all other scenarios, the properties of lowpoint/dfs 1022 parents ensure that the end of the ear will be in the same block, and 1023 thus inheriting its local-root would be the correct local-root for 1024 all newly added nodes. 1026 The pseudo-code for the GADAG algorithm (assuming that the adjustment 1027 of lowpoint for cut-vertices has been made) is shown in Figure 17. 1029 Construct_Ear(x, Stack, intf, ear_type) 1030 ear_list = empty 1031 cur_node = intf.remote_node 1032 cur_intf = intf 1033 not_done = true 1035 while not_done 1036 cur_intf.UNDIRECTED = false 1037 cur_intf.OUTGOING = true 1038 cur_intf.remote_intf.UNDIRECTED = false 1039 cur_intf.remote_intf.INCOMING = true 1041 if cur_node.IN_GADAG is false 1042 cur_node.IN_GADAG = true 1043 add_to_list_end(ear_list, cur_node) 1044 if ear_type is CHILD 1045 cur_intf = cur_node.lowpoint_parent_intf 1046 cur_node = cur_node.lowpoint_parent 1047 else // ear_type must be NEIGHBOR 1048 cur_intf = cur_node.dfs_parent_intf 1049 cur_node = cur_node.dfs_parent 1050 else 1051 not_done = false 1053 if (ear_type is CHILD) and (cur_node is x) 1054 // x is a cut-vertex and the local root for 1055 // the block in which the ear is computed 1056 x.IS_CUT_VERTEX = true 1057 localroot = x 1058 else 1059 // Inherit local-root from the end of the ear 1060 localroot = cur_node.localroot 1061 while ear_list is not empty 1062 y = remove_end_item_from_list(ear_list) 1063 y.localroot = localroot 1064 push(Stack, y) 1066 Construct_GADAG_via_Lowpoint(topology, gadag_root) 1067 gadag_root.IN_GADAG = true 1068 gadag_root.localroot = None 1069 Initialize Stack to empty 1070 push gadag_root onto Stack 1071 while (Stack is not empty) 1072 x = pop(Stack) 1073 foreach ordered_interface intf of x 1074 if ((intf.remote_node.IN_GADAG == false) and 1075 (intf.remote_node.dfs_parent is x)) 1076 Construct_Ear(x, Stack, intf, CHILD) 1077 foreach ordered_interface intf of x 1078 if ((intf.remote_node.IN_GADAG == false) and 1079 (intf.remote_node.dfs_parent is not x)) 1080 Construct_Ear(x, Stack, intf, NEIGHBOR) 1082 Construct_GADAG_via_Lowpoint(topology, gadag_root) 1084 Figure 17: Low-point Inheritance GADAG algorithm 1086 5.6. Augmenting the GADAG by directing all links 1088 The GADAG, regardless of the method used to construct it, at this 1089 point could be used to find MRTs, but the topology does not include 1090 all links in the network graph. That has two impacts. First, there 1091 might be shorter paths that respect the GADAG partial ordering and so 1092 the alternate paths would not be as short as possible. Second, there 1093 may be additional paths between a router x and the root that are not 1094 included in the GADAG. Including those provides potentially more 1095 bandwidth to traffic flowing on the alternates and may reduce 1096 congestion compared to just using the GADAG as currently constructed. 1098 The goal is thus to assign direction to every remaining link marked 1099 as UNDIRECTED to improve the paths and number of paths found when the 1100 MRTs are computed. 1102 To do this, we need to establish a total order that respects the 1103 partial order described by the GADAG. This can be done using Kahn's 1104 topological sort[Kahn_1962_topo_sort] which essentially assigns a 1105 number to a node x only after all nodes before it (e.g. with a link 1106 incoming to x) have had their numbers assigned. The only issue with 1107 the topological sort is that it works on DAGs and not ADAGs or 1108 GADAGs. 1110 To convert a GADAG to a DAG, it is necessary to remove all links that 1111 point to a root of block from within that block. That provides the 1112 necessary conversion to a DAG and then a topological sort can be 1113 done. When adding undirected links to the GADAG, links connecting 1114 the block root to other nodes in that block need special handling 1115 because the topological order will not always give the right answer 1116 for those links. There are three cases to consider. If the 1117 undirected link in question has another parallel link between the 1118 same two nodes that is already directed, then the direction of the 1119 undirected link can be inherited from the previously directed link. 1120 In the case of parallel cut links, we set all of the parallel links 1121 to both INCOMING and OUTGOING. Otherwise, the undirected link in 1122 question is set to OUTGOING from the block root node. A cut-link can 1123 then be identified by the fact that it will be directed both INCOMING 1124 and OUTGOING in the GADAG. The exact details of this whole process 1125 are captured in Figure 18 1127 Add_Undirected_Block_Root_Links(topo, gadag_root) 1128 foreach node x in topo 1129 if x.IS_CUT_VERTEX or x is gadag_root 1130 foreach interface i of x 1131 if (i.remote_node.localroot is not x 1132 or i.PROCESSED ) 1133 continue 1134 Initialize bundle_list to empty 1135 bundle.UNDIRECTED = true 1136 bundle.OUTGOING = false 1137 bundle.INCOMING = false 1138 foreach interface i2 in x 1139 if i2.remote_node is i.remote_node 1140 add_to_list_end(bundle_list, i2) 1141 if not i2.UNDIRECTED: 1142 bundle.UNDIRECTED = false 1143 if i2.INCOMING: 1144 bundle.INCOMING = true 1145 if i2.OUTGOING: 1146 bundle.OUTGOING = true 1147 if bundle.UNDIRECTED 1148 foreach interface i3 in bundle_list 1149 i3.UNDIRECTED = false 1150 i3.remote_intf.UNDIRECTED = false 1151 i3.PROCESSED = true 1152 i3.remote_intf.PROCESSED = true 1153 i3.OUTGOING = true 1154 i3.remote_intf.INCOMING = true 1155 else 1156 if (bundle.OUTGOING and bundle.INCOMING) 1157 foreach interface i3 in bundle_list 1158 i3.UNDIRECTED = false 1159 i3.remote_intf.UNDIRECTED = false 1160 i3.PROCESSED = true 1161 i3.remote_intf.PROCESSED = true 1162 i3.OUTGOING = true 1163 i3.INCOMING = true 1164 i3.remote_intf.INCOMING = true 1165 i3.remote_intf.OUTGOING = true 1167 else if bundle.OUTGOING 1168 foreach interface i3 in bundle_list 1169 i3.UNDIRECTED = false 1170 i3.remote_intf.UNDIRECTED = false 1171 i3.PROCESSED = true 1172 i3.remote_intf.PROCESSED = true 1173 i3.OUTGOING = true 1174 i3.remote_intf.INCOMING = true 1175 else if bundle.INCOMING 1176 foreach interface i3 in bundle_list 1177 i3.UNDIRECTED = false 1178 i3.remote_intf.UNDIRECTED = false 1179 i3.PROCESSED = true 1180 i3.remote_intf.PROCESSED = true 1181 i3.INCOMING = true 1182 i3.remote_intf.OUTGOING = true 1184 Modify_Block_Root_Incoming_Links(topo, gadag_root) 1185 foreach node x in topo 1186 if x.IS_CUT_VERTEX or x is gadag_root 1187 foreach interface i of x 1188 if i.remote_node.localroot is x 1189 if i.INCOMING: 1190 i.INCOMING = false 1191 i.INCOMING_STORED = true 1192 i.remote_intf.OUTGOING = false 1193 i.remote_intf.OUTGOING_STORED = true 1195 Revert_Block_Root_Incoming_Links(topo, gadag_root) 1196 foreach node x in topo 1197 if x.IS_CUT_VERTEX or x is gadag_root 1198 foreach interface i of x 1199 if i.remote_node.localroot is x 1200 if i.INCOMING_STORED 1201 i.INCOMING = true 1202 i.remote_intf.OUTGOING = true 1203 i.INCOMING_STORED = false 1204 i.remote_intf.OUTGOING_STORED = false 1206 Run_Topological_Sort_GADAG(topo, gadag_root) 1207 Modify_Block_Root_Incoming_Links(topo, gadag_root) 1208 foreach node x in topo 1209 node.unvisited = 0 1210 foreach interface i of x 1211 if (i.INCOMING) 1212 node.unvisited += 1 1213 Initialize working_list to empty 1214 Initialize topo_order_list to empty 1215 add_to_list_end(working_list, gadag_root) 1216 while working_list is not empty 1217 y = remove_start_item_from_list(working_list) 1218 add_to_list_end(topo_order_list, y) 1219 foreach ordered_interface i of y 1220 if intf.OUTGOING 1221 i.remote_node.unvisited -= 1 1222 if i.remote_node.unvisited is 0 1223 add_to_list_end(working_list, i.remote_node) 1224 next_topo_order = 1 1225 while topo_order_list is not empty 1226 y = remove_start_item_from_list(topo_order_list) 1227 y.topo_order = next_topo_order 1228 next_topo_order += 1 1229 Revert_Block_Root_Incoming_Links(topo, gadag_root) 1231 def Set_Other_Undirected_Links_Based_On_Topo_Order(topo) 1232 foreach node x in topo 1233 foreach interface i of x 1234 if i.UNDIRECTED: 1235 if x.topo_order < i.remote_node.topo_order 1236 i.OUTGOING = true 1237 i.UNDIRECTED = false 1238 i.remote_intf.INCOMING = true 1239 i.remote_intf.UNDIRECTED = false 1240 else 1241 i.INCOMING = true 1242 i.UNDIRECTED = false 1243 i.remote_intf.OUTGOING = true 1244 i.remote_intf.UNDIRECTED = false 1246 Add_Undirected_Links(topo, gadag_root) 1247 Add_Undirected_Block_Root_Links(topo, gadag_root) 1248 Run_Topological_Sort_GADAG(topo, gadag_root) 1249 Set_Other_Undirected_Links_Based_On_Topo_Order(topo) 1251 Add_Undirected_Links(topo, gadag_root) 1253 Figure 18: Assigning direction to UNDIRECTED links 1255 Proxy-nodes do not need to be added to the network graph. They 1256 cannot be transited and do not affect the MRTs that are computed. 1257 The details of how the MRT-Blue and MRT-Red next-hops are computed 1258 for proxy-nodes and how the appropriate alternate next-hops are 1259 selected is given in Section 5.9. 1261 5.7. Compute MRT next-hops 1263 As was discussed in Section 4.1, once a ADAG is found, it is 1264 straightforward to find the next-hops from any node X to the ADAG 1265 root. However, in this algorithm, we will reuse the common GADAG and 1266 find not only the one pair of MRTs rooted at the GADAG root with it, 1267 but find a pair rooted at each node. This is useful since it is 1268 significantly faster to compute. 1270 The method for computing differently rooted MRTs from the common 1271 GADAG is based on two ideas. First, if two nodes X and Y are ordered 1272 with respect to each other in the partial order, then an SPF along 1273 OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a 1274 decreasing-SPF) can be used to find the increasing and decreasing 1275 paths. Second, if two nodes X and Y aren't ordered with respect to 1276 each other in the partial order, then intermediary nodes can be used 1277 to create the paths by increasing/decreasing to the intermediary and 1278 then decreasing/increasing to reach Y. 1280 As usual, the two basic ideas will be discussed assuming the network 1281 is two-connected. The generalization to multiple blocks is discussed 1282 in Section 5.7.4. The full algorithm is given in Section 5.7.5. 1284 5.7.1. MRT next-hops to all nodes ordered with respect to the computing 1285 node 1287 To find two node-disjoint paths from the computing router X to any 1288 node Y, depends upon whether Y >> X or Y << X. As shown in 1289 Figure 19, if Y >> X, then there is an increasing path that goes from 1290 X to Y without crossing R; this contains nodes in the interval [X,Y]. 1291 There is also a decreasing path that decreases towards R and then 1292 decreases from R to Y; this contains nodes in the interval 1293 [X,R-small] or [R-great,Y]. The two paths cannot have common nodes 1294 other than X and Y. 1296 [Y]<---(Cloud 2)<--- [X] 1297 | ^ 1298 | | 1299 V | 1300 (Cloud 3)--->[R]--->(Cloud 1) 1302 MRT-Blue path: X->Cloud 2->Y 1303 MRT-Red path: X->Cloud 1->R->Cloud 3->Y 1305 Figure 19: Y >> X 1307 Similar logic applies if Y << X, as shown in Figure 20. In this 1308 case, the increasing path from X increases to R and then increases 1309 from R to Y to use nodes in the intervals [X,R-great] and [R-small, 1310 Y]. The decreasing path from X reaches Y without crossing R and uses 1311 nodes in the interval [Y,X]. 1313 [X]<---(Cloud 2)<--- [Y] 1314 | ^ 1315 | | 1316 V | 1317 (Cloud 3)--->[R]--->(Cloud 1) 1319 MRT-Blue path: X->Cloud 3->R->Cloud 1->Y 1320 MRT-Red path: X->Cloud 2->Y 1322 Figure 20: Y << X 1324 5.7.2. MRT next-hops to all nodes not ordered with respect to the 1325 computing node 1327 When X and Y are not ordered, the first path should increase until we 1328 get to a node G, where G >> Y. At G, we need to decrease to Y. The 1329 other path should be just the opposite: we must decrease until we get 1330 to a node H, where H << Y, and then increase. Since R is smaller and 1331 greater than Y, such G and H must exist. It is also easy to see that 1332 these two paths must be node disjoint: the first path contains nodes 1333 in interval [X,G] and [Y,G], while the second path contains nodes in 1334 interval [H,X] and [H,Y]. This is illustrated in Figure 21. It is 1335 necessary to decrease and then increase for the MRT-Blue and increase 1336 and then decrease for the MRT-Red; if one simply increased for one 1337 and decreased for the other, then both paths would go through the 1338 root R. 1340 (Cloud 6)<---[Y]<---(Cloud 5)<------------| 1341 | | 1342 | | 1343 V | 1344 [G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H] 1345 ^ | 1346 | | 1347 | | 1348 (Cloud 3)<---[X]<---(Cloud 2)<-----------| 1350 MRT-Blue path: decrease to H and increase to Y 1351 X->Cloud 2->H->Cloud 5->Y 1352 MRT-Red path: increase to G and decrease to Y 1353 X->Cloud 3->G->Cloud 6->Y 1355 Figure 21: X and Y unordered 1357 This gives disjoint paths as long as G and H are not the same node. 1358 Since G >> Y and H << Y, if G and H could be the same node, that 1359 would have to be the root R. This is not possible because there is 1360 only one incoming interface to the root R which is created when the 1361 initial cycle is found. Recall from Figure 6 that whenever an ear 1362 was found to have an end that was the root R, the ear was directed 1363 from R so that the associated interface on R is outgoing and not 1364 incoming. Therefore, there must be exactly one node M which is the 1365 largest one before R, so the MRT-Red path will never reach R; it will 1366 turn at M and decrease to Y. 1368 5.7.3. Computing Redundant Tree next-hops in a 2-connected Graph 1370 The basic ideas for computing RT next-hops in a 2-connected graph 1371 were given in Section 5.7.1 and Section 5.7.2. Given these two 1372 ideas, how can we find the trees? 1374 If some node X only wants to find the next-hops (which is usually the 1375 case for IP networks), it is enough to find which nodes are greater 1376 and less than X, and which are not ordered; this can be done by 1377 running an increasing-SPF and a decreasing-SPF rooted at X and not 1378 exploring any links from the ADAG root. 1380 In principle, an traversal method other than SPF could be used to 1381 traverse the GADAG in the process of determining blue and red next- 1382 hops that result in maximally redundant trees. This will be the case 1383 as long as one traversal uses the links in the direction specified by 1384 the GADAG and the other traversal uses the links in the direction 1385 opposite of that specified by the GADAG. However, a different 1386 traversal algorithm will generally result in different blue and red 1387 next-hops. Therefore, the algorithm specified here requires the use 1388 of SPF to traverse the GADAG to generate MRT blue and red next-hops, 1389 as described below. 1391 An increasing-SPF rooted at X and not exploring links from the root 1392 will find the increasing next-hops to all Y >> X. Those increasing 1393 next-hops are X's next-hops on the MRT-Blue to reach Y. A 1394 decreasing-SPF rooted at X and not exploring links from the root will 1395 find the decreasing next-hops to all Z << X. Those decreasing next- 1396 hops are X's next-hops on the MRT-Red to reach Z. Since the root R 1397 is both greater than and less than X, after this increasing-SPF and 1398 decreasing-SPF, X's next-hops on the MRT-Blue and on the MRT-Red to 1399 reach R are known. For every node Y >> X, X's next-hops on the MRT- 1400 Red to reach Y are set to those on the MRT-Red to reach R. For every 1401 node Z << X, X's next-hops on the MRT-Blue to reach Z are set to 1402 those on the MRT-Blue to reach R. 1404 For those nodes which were not reached by either the increasing-SPF 1405 or the decreasing-SPF, we can determine the next-hops as well. The 1406 increasing MRT-Blue next-hop for a node which is not ordered with 1407 respect to X is the next-hop along the decreasing MRT-Red towards R, 1408 and the decreasing MRT-Red next-hop is the next-hop along the 1409 increasing MRT-Blue towards R. Naturally, since R is ordered with 1410 respect to all the nodes, there will always be an increasing and a 1411 decreasing path towards it. This algorithm does not provide the 1412 complete specific path taken but just the appropriate next-hops to 1413 use. The identities of G and H are not determined by the computing 1414 node X. 1416 The final case to consider is when the GADAG root R computes its own 1417 next-hops. Since the GADAG root R is << all other nodes, running an 1418 increasing-SPF rooted at R will reach all other nodes; the MRT-Blue 1419 next-hops are those found with this increasing-SPF. Similarly, since 1420 the GADAG root R is >> all other nodes, running a decreasing-SPF 1421 rooted at R will reach all other nodes; the MRT-Red next-hops are 1422 those found with this decreasing-SPF. 1424 E---D---| E<--D<--| 1425 | | | | ^ | 1426 | | | V | | 1427 R F C R F C 1428 | | | | ^ ^ 1429 | | | V | | 1430 A---B---| A-->B---| 1432 (a) (b) 1433 A 2-connected graph A spanning ADAG rooted at R 1435 Figure 22 1437 As an example consider the situation depicted in Figure 22. Node C 1438 runs an increasing-SPF and a decreasing-SPF on the ADAG. The 1439 increasing-SPF reaches D, E and R and the decreasing-SPF reaches B, A 1440 and R. E>>C. So towards E the MRT-Blue next-hop is D, since E was 1441 reached on the increasing path through D. And the MRT-Red next-hop 1442 towards E is B, since R was reached on the decreasing path through B. 1443 Since E>>D, D will similarly compute its MRT-Blue next-hop to be E, 1444 ensuring that a packet on MRT-Blue will use path C-D-E. B, A and R 1445 will similarly compute the MRT-Red next-hops towards E (which is 1446 ordered less than B, A and R), ensuring that a packet on MRT-Red will 1447 use path C-B-A-R-E. 1449 C can determine the next-hops towards F as well. Since F is not 1450 ordered with respect to C, the MRT-Blue next-hop is the decreasing 1451 one towards R (which is B) and the MRT-Red next-hop is the increasing 1452 one towards R (which is D). Since F>>B, for its MRT-Blue next-hop 1453 towards F, B will use the real increasing next-hop towards F. So a 1454 packet forwarded to B on MRT-Blue will get to F on path C-B-F. 1455 Similarly, D will use the real decreasing next-hop towards F as its 1456 MRT-Red next-hop, a packet on MRT-Red will use path C-D-F. 1458 5.7.4. Generalizing for a graph that isn't 2-connected 1460 If a graph isn't 2-connected, then the basic approach given in 1461 Section 5.7.3 needs some extensions to determine the appropriate MRT 1462 next-hops to use for destinations outside the computing router X's 1463 blocks. In order to find a pair of maximally redundant trees in that 1464 graph we need to find a pair of RTs in each of the blocks (the root 1465 of these trees will be discussed later), and combine them. 1467 When computing the MRT next-hops from a router X, there are three 1468 basic differences: 1470 1. Only nodes in a common block with X should be explored in the 1471 increasing-SPF and decreasing-SPF. 1473 2. Instead of using the GADAG root, X's local-root should be used. 1474 This has the following implications: 1476 A. The links from X's local-root should not be explored. 1478 B. If a node is explored in the outgoing SPF so Y >> X, then X's 1479 MRT-Red next-hops to reach Y uses X's MRT-Red next-hops to 1480 reach X's local-root and if Z << X, then X's MRT-Blue next- 1481 hops to reach Z uses X's MRT-Blue next-hops to reach X's 1482 local-root. 1484 C. If a node W in a common block with X was not reached in the 1485 increasing-SPF or decreasing-SPF, then W is unordered with 1486 respect to X. X's MRT-Blue next-hops to W are X's decreasing 1487 (aka MRT-Red) next-hops to X's local-root. X's MRT-Red next- 1488 hops to W are X's increasing (aka MRT-Blue) next-hops to X's 1489 local-root. 1491 3. For nodes in different blocks, the next-hops must be inherited 1492 via the relevant cut-vertex. 1494 These are all captured in the detailed algorithm given in 1495 Section 5.7.5. 1497 5.7.5. Complete Algorithm to Compute MRT Next-Hops 1499 The complete algorithm to compute MRT Next-Hops for a particular 1500 router X is given in Figure 23. In addition to computing the MRT- 1501 Blue next-hops and MRT-Red next-hops used by X to reach each node Y, 1502 the algorithm also stores an "order_proxy", which is the proper cut- 1503 vertex to reach Y if it is outside the block, and which is used later 1504 in deciding whether the MRT-Blue or the MRT-Red can provide an 1505 acceptable alternate for a particular primary next-hop. 1507 In_Common_Block(x, y) 1508 if ( (x.block_id is y.block_id) 1509 or (x is y.localroot) or (y is x.localroot) ) 1510 return true 1511 return false 1513 Store_Results(y, direction) 1514 if direction is FORWARD 1515 y.higher = true 1516 y.blue_next_hops = y.next_hops 1517 if direction is REVERSE 1518 y.lower = true 1519 y.red_next_hops = y.next_hops 1521 SPF_No_Traverse_Block_Root(spf_root, block_root, direction) 1522 Initialize spf_heap to empty 1523 Initialize nodes' spf_metric to infinity and next_hops to empty 1524 spf_root.spf_metric = 0 1525 insert(spf_heap, spf_root) 1526 while (spf_heap is not empty) 1527 min_node = remove_lowest(spf_heap) 1528 Store_Results(min_node, direction) 1529 if ((min_node is spf_root) or (min_node is not block_root)) 1530 foreach interface intf of min_node 1531 if ( ( ((direction is FORWARD) and intf.OUTGOING) or 1532 ((direction is REVERSE) and intf.INCOMING) ) 1533 and In_Common_Block(spf_root, intf.remote_node) ) 1534 path_metric = min_node.spf_metric + intf.metric 1535 if path_metric < intf.remote_node.spf_metric 1536 intf.remote_node.spf_metric = path_metric 1537 if min_node is spf_root 1538 intf.remote_node.next_hops = make_list(intf) 1539 else 1540 intf.remote_node.next_hops = min_node.next_hops 1541 insert_or_update(spf_heap, intf.remote_node) 1542 else if path_metric == intf.remote_node.spf_metric 1543 if min_node is spf_root 1544 add_to_list(intf.remote_node.next_hops, intf) 1545 else 1546 add_list_to_list(intf.remote_node.next_hops, 1547 min_node.next_hops) 1549 SetEdge(y) 1550 if y.blue_next_hops is empty and y.red_next_hops is empty 1551 SetEdge(y.localroot) 1552 y.blue_next_hops = y.localroot.blue_next_hops 1553 y.red_next_hops = y.localroot.red_next_hops 1554 y.order_proxy = y.localroot.order_proxy 1556 Compute_MRT_NextHops(x, gadag_root) 1557 foreach node y 1558 y.higher = y.lower = false 1559 clear y.red_next_hops and y.blue_next_hops 1560 y.order_proxy = y 1561 SPF_No_Traverse_Block_Root(x, x.localroot, FORWARD) 1562 SPF_No_Traverse_Block_Root(x, x.localroot, REVERSE) 1564 // red and blue next-hops are stored to x.localroot as different 1565 // paths are found via the SPF and reverse-SPF. 1566 // Similarly any nodes whose local-root is x will have their 1567 // red_next_hops and blue_next_hops already set. 1569 // Handle nodes in the same block that aren't the local-root 1570 foreach node y 1571 if (y.IN_MRT_ISLAND and (y is not x) and 1572 (y.block_id is x.block_id) ) 1573 if y.higher 1574 y.red_next_hops = x.localroot.red_next_hops 1575 else if y.lower 1576 y.blue_next_hops = x.localroot.blue_next_hops 1577 else 1578 y.blue_next_hops = x.localroot.red_next_hops 1579 y.red_next_hops = x.localroot.blue_next_hops 1581 // Inherit next-hops and order_proxies to other components 1582 if (x is not gadag_root) and (x.localroot is not gadag_root) 1583 gadag_root.blue_next_hops = x.localroot.blue_next_hops 1584 gadag_root.red_next_hops = x.localroot.red_next_hops 1585 gadag_root.order_proxy = x.localroot 1586 foreach node y 1587 if (y is not gadag_root) and (y is not x) and y.IN_MRT_ISLAND 1588 SetEdge(y) 1590 max_block_id = 0 1591 Assign_Block_ID(gadag_root, max_block_id) 1592 Compute_MRT_NextHops(x, gadag_root) 1594 Figure 23 1596 5.8. Identify MRT alternates 1598 At this point, a computing router S knows its MRT-Blue next-hops and 1599 MRT-Red next-hops for each destination in the MRT Island. The 1600 primary next-hops along the SPT are also known. It remains to 1601 determine for each primary next-hop to a destination D, which of the 1602 MRTs avoids the primary next-hop node F. This computation depends 1603 upon data set in Compute_MRT_NextHops such as each node y's 1604 y.blue_next_hops, y.red_next_hops, y.order_proxy, y.higher, y.lower 1605 and topo_orders. Recall that any router knows only which are the 1606 nodes greater and lesser than itself, but it cannot decide the 1607 relation between any two given nodes easily; that is why we need 1608 topological ordering. 1610 For each primary next-hop node F to each destination D, S can call 1611 Select_Alternates(S, D, F, primary_intf) to determine whether to use 1612 the MRT-Blue or MRT-Red next-hops as the alternate next-hop(s) for 1613 that primary next hop. The algorithm is given in Figure 24 and 1614 discussed afterwards. 1616 Select_Alternates_Internal(D, F, primary_intf, 1617 D_lower, D_higher, D_topo_order): 1618 if D_higher and D_lower 1619 if F.HIGHER and F.LOWER 1620 if F.topo_order < D_topo_order 1621 return USE_RED 1622 else 1623 return USE_BLUE 1624 if F.HIGHER 1625 return USE_RED 1626 if F.LOWER 1627 return USE_BLUE 1628 //F unordered wrt S 1629 return USE_RED_OR_BLUE 1631 else if D_higher 1632 if F.HIGHER and F.LOWER 1633 return USE_BLUE 1634 if F.LOWER 1635 return USE_BLUE 1636 if F.HIGHER 1637 if (F.topo_order > D_topo_order) 1638 return USE_BLUE 1639 if (F.topo_order < D_topo_order) 1640 return USE_RED 1641 //F unordered wrt S 1642 return USE_RED_OR_BLUE 1644 else if D_lower 1645 if F.HIGHER and F.LOWER 1646 return USE_RED 1647 if F.HIGHER 1648 return USE_RED 1649 if F.LOWER 1650 if F.topo_order > D_topo_order 1651 return USE_BLUE 1652 if F.topo_order < D_topo_order 1653 return USE_RED 1654 //F unordered wrt S 1655 return USE_RED_OR_BLUE 1657 else //D is unordered wrt S 1658 if F.HIGHER and F.LOWER 1659 if primary_intf.OUTGOING and primary_intf.INCOMING 1660 return USE_RED_OR_BLUE 1661 if primary_intf.OUTGOING 1662 return USE_BLUE 1663 if primary_intf.INCOMING 1664 return USE_RED 1665 //primary_intf not in GADAG 1666 return USE_RED 1667 if F.LOWER 1668 return USE_RED 1669 if F.HIGHER 1670 return USE_BLUE 1671 //F unordered wrt S 1672 if F.topo_order > D_topo_order: 1673 return USE_BLUE 1674 else: 1675 return USE_RED 1677 Select_Alternates(D, F, primary_intf) 1678 if not In_Common_Block(F, S) 1679 return PRIM_NH_IN_DIFFERENT_BLOCK 1680 if (D is F) or (D.order_proxy is F) 1681 return PRIM_NH_IS_D_OR_OP_FOR_D 1682 D_lower = D.order_proxy.LOWER 1683 D_higher = D.order_proxy.HIGHER 1684 D_topo_order = D.order_proxy.topo_order 1685 return Select_Alternates_Internal(D, F, primary_intf, 1686 D_lower, D_higher, D_topo_order) 1688 Figure 24: Select_Alternates() and Select_Alternates_Internal() 1690 It is useful to first handle the case where where F is also D, or F 1691 is the order proxy for D. In this case, only link protection is 1692 possible. The MRT that doesn't use the failed primary next-hop is 1693 used. If both MRTs use the primary next-hop, then the primary next- 1694 hop must be a cut-link, so either MRT could be used but the set of 1695 MRT next-hops must be pruned to avoid the failed primary next-hop 1696 interface. To indicate this case, Select_Alternates returns 1697 PRIM_NH_IS_D_OR_OP_FOR_D. Explicit pseudo-code to handle the three 1698 sub-cases above is not provided. 1700 The logic behind Select_Alternates_Internal is described in 1701 Figure 25. As an example, consider the first case described in the 1702 table, where the D>>S and D<>S and F<D.topo_order, then either F is ordered lower 1715 than D, or F is unordered with respect to D. Therefore, F is either 1716 on an increasing path from S to D, or it is on neither an increasing 1717 nor a decreasing path from S to D. In either case, it is safe to 1718 take a decreasing path from S to D to avoid F. We know that when S 1719 is R, the decreasing path is the red path, so it is safe to use the 1720 red path to avoid F. 1722 If F>>S or F<>S, we deduce that 1725 F is on an increasing path from S to R. So in order to avoid F, we 1726 use a decreasing path from S to R, which is the red path. Instead, 1727 when F<>S | Blue path: | F>>S | additional | F on an | Use Red | 1741 | and | Increasing | only | criteria | increasing | to avoid | 1742 | D<>S | topo(F)>topo(D) | F on a | Use Blue | 1751 | S is | Blue path: | and | implies that | decreasing | to avoid | 1752 | R | Increasing | F<>D or F??D | path from | F | 1753 | | path to D. | F is | | S to D or | | 1754 | | Red path: | R | | neither | | 1755 | | Decreasing | +-----------------+------------+------------+ 1756 | | path to D. | | topo(F)>S | Blue path: | F<>S | topo(F)>topo(D) | F on | Use Blue | 1775 | | Decreasing | only | implies that | decreasing | to avoid | 1776 | | shortest | | F>>D or F??D | path from | F | 1777 | | path from | | | R to D | | 1778 | | S to R, | | | or | | 1779 | | then | | | neither | | 1780 | | decreasing | +-----------------+------------+------------+ 1781 | | shortest | | topo(F)>S | additional | F on Red | Use Blue | 1789 | | | and | criteria | | to avoid | 1790 | | | F<>S | additional | F on | Use Red | 1802 | only | Increasing | only | criteria | increasing | to avoid | 1803 | | shortest | | not needed | path from | F | 1804 | | path from | | | S to R | | 1805 | | S to R, +------+-----------------+------------+------------+ 1806 | | then | F<topo(D) | F on | Use Blue | 1807 | | increasing | only | implies that | decreasing | to avoid | 1808 | | shortest | | F>>D or F??D | path from | F | 1809 | | path from | | | R to D | | 1810 | | R to D. | | | or | | 1811 | | Red path: | | | neither | | 1812 | | Decreasing | +-----------------+------------+------------+ 1813 | | shortest | | topo(F)>S | additional | F on Blue | Use Red | 1821 | | | and | criteria | | to avoid | 1822 | | | F<>S | additional | F on an | Use Blue | 1839 | | Red path: | only | criteria | increasing | to avoid | 1840 | | Incr. from | | not needed | path from | F | 1841 | | S to first | | | S to L | | 1842 | | node L>>D, | | | | | 1843 | | then decr. | | | | | 1844 | | +------+-----------------+------------+------------+ 1845 | | | F??S | F<-->S link is | | | 1846 | | | | MRT_INELIGIBLE | | | 1847 | | | +-----------------+------------+------------+ 1848 | | | | topo(F)>topo(D) | F on decr. | Use Blue | 1849 | | | | implies that | path from | to avoid | 1850 | | | | F>>D or F??D | L to D or | F | 1851 | | | | | neither | | 1852 | | | +-----------------+------------+------------+ 1853 | | | | topo(F)>S | GADAG link | F on an | Use Blue | 1859 | | | and | direction | incr. path | to avoid | 1860 | | | F<F | from S | F | 1861 | | | F is +-----------------+------------+------------+ 1862 | | | R | GADAG link | F on a | Use Red | 1863 | | | | direction | decr. path | to avoid | 1864 | | | | S<-F | from S | F | 1865 | | | +-----------------+------------+------------+ 1866 | | | | GADAG link | Either F is the order | 1867 | | | | direction | proxy for D (case | 1868 | | | | S<-->F | already handled) or D | 1869 | | | | | is in a different block | 1870 | | | | | from F, in which case | 1871 | | | | | Red or Blue avoids F | 1872 | | | +-----------------+-------------------------+ 1873 | | | | S-F link not | Relies on special | 1874 | | | | in GADAG, | construction of GADAG | 1875 | | | | only when | to demonstrate that | 1876 | | | | S-F link is | using Red avoids F | 1877 | | | | MRT_INELIGIBLE | (see text) | 1878 +------+------------+------+-----------------+-------------------------+ 1880 Figure 25: determining MRT next-hops and alternates based on the 1881 partial order and topological sort relationships between the 1882 source(S), destination(D), primary next-hop(F), and block root(R). 1883 topo(N) indicates the topological sort value of node N. X??Y 1884 indicates that node X is unordered with respect to node Y. It is 1885 assumed that the case where F is D, or where F is the order proxy for 1886 D, has already been handled. 1888 The last case in Figure 25 requires additional explanation. The fact 1889 that the red path from S to D in this case avoids F relies on a 1890 special property of the GADAGs that we have constructed in this 1891 algorithm, a property not shared by all GADAGs in general. When D is 1892 unordered with respect to S, and F is the localroot for S, it can 1893 occur that the link between S and F is not in the GADAG only when 1894 that link has been marked MRT_INELIGIBLE. For an arbitrary GADAG, S 1895 doesn't have enough information based on the computed order 1896 relationships to determine if the red path or blue path will hit F 1897 (which is also the localroot) before hitting K or L, and making it 1898 safely to D. However, the GADAGs that we construct using the 1899 algorithm in this document are not arbitrary GADAGs. They have the 1900 additional property that incoming links to a localroot come from only 1901 one other node in the same block. This is a result of the method of 1902 construction. This additional property guarantees that the red path 1903 from S to D will never pass through the localroot of S. (That would 1904 require the localroot to play the role of L, the first node in the 1905 path ordered higher than D, which would in turn require the localroot 1906 to have two incoming links in the GADAG, which cannot happen.) 1907 Therefore it is safe to use the red path to avoid F with these 1908 specially constructed GADAGs. 1910 As an example of how Select_Alternates_Internal() operates, consider 1911 the ADAG depicted in Figure 26 and first suppose that G is the 1912 source, D is the destination and H is the failed next-hop. Since 1913 D>>G, we need to compare H.topo_order and D.topo_order. Since 1914 D.topo_order>H.topo_order, D must be either higher than H or 1915 unordered with respect to H, so we should select the decreasing path 1916 towards the root. If, however, the destination were instead J, we 1917 must find that H.topo_order>J.topo_order, so we must choose the 1918 increasing Blue next-hop to J, which is I. In the case, when instead 1919 the destination is C, we find that we need to first decrease to avoid 1920 using H, so the Blue, first decreasing then increasing, path is 1921 selected. 1923 [E]<-[D]<-[H]<-[J] 1924 | ^ ^ ^ 1925 V | | | 1926 [R] [C] [G]->[I] 1927 | ^ ^ ^ 1928 V | | | 1929 [A]->[B]->[F]---| 1931 (a)ADAG rooted at R for 1932 a 2-connected graph 1934 Figure 26 1936 5.9. Named Proxy-Nodes 1938 As discussed in Section 11.2 of 1939 [I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT- 1940 Blue and MRT-Red next-hops and MRT-FRR alternates for named proxy- 1941 nodes. An example use case is for a router that is not part of that 1942 local MRT Island, when there is only partial MRT support in the 1943 domain. 1945 5.9.1. Determining Proxy-Node Attachment Routers 1947 Section 11.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] discusses 1948 general considerations for determining the two proxy-node attachment 1949 routers for a given proxy-node, corresponding to a prefix. A router 1950 in the MRT Island that advertises the prefix is a candidate for being 1951 a proxy-node attachment router, with the associated named-proxy-cost 1952 equal to the advertised cost to the prefix. 1954 An Island Border Router (IBR) is a router in the MRT Island that is 1955 connected to an Island Neighbor(IN), which is a router not in the MRT 1956 Island but in the same area/level. An (IBR,IN) pair is a candidate 1957 for being a proxy-node attachment router, if the shortest path from 1958 the IN to the prefix does not enter the MRT Island. A method for 1959 identifying such loop-free Island Neighbors(LFINs) is given below. 1960 The named-proxy-cost assigned to each (IBR, IN) pair is cost(IBR, IN) 1961 + D_opt(IN, prefix). 1963 From the set of prefix-advertising routers and the set of IBRs with 1964 at least one LFIN, the two routers with the lowest named-proxy-cost 1965 are selected. Ties are broken based upon the lowest Router ID. For 1966 ease of discussion, the two selected routers will be referred to as 1967 proxy-node attachment routers. 1969 5.9.2. Computing if an Island Neighbor (IN) is loop-free 1971 As discussed above, the Island Neighbor needs to be loop-free with 1972 respect to the whole MRT Island for the destination. This can be 1973 accomplished by running the usual SPF algorithm while keeping track 1974 of which shortest paths have passed through the MRT island. Pseudo- 1975 code for this is shown in Figure 27. The Island_Marking_SPF() is run 1976 for each IN that needs to be evaluated for the loop-free condition, 1977 with the IN as the spf_root. Whether or not an IN is loop-free with 1978 respect to the MRT island can then be determined by evaluating 1979 node.PATH_HITS_ISLAND for each destination of interest. 1981 Island_Marking_SPF(spf_root) 1982 Initialize spf_heap to empty 1983 Initialize nodes' spf_metric to infinity and next_hops to empty 1984 and PATH_HITS_ISLAND to false 1985 spf_root.spf_metric = 0 1986 insert(spf_heap, spf_root) 1987 while (spf_heap is not empty) 1988 min_node = remove_lowest(spf_heap) 1989 foreach interface intf of min_node 1990 path_metric = min_node.spf_metric + intf.metric 1991 if path_metric < intf.remote_node.spf_metric 1992 intf.remote_node.spf_metric = path_metric 1993 if min_node is spf_root 1994 intf.remote_node.next_hops = make_list(intf) 1995 else 1996 intf.remote_node.next_hops = min_node.next_hops 1997 if intf.remote_node.IN_MRT_ISLAND 1998 intf.remote_node.PATH_HITS_ISLAND = true 1999 else 2000 intf.remote_node.PATH_HITS_ISLAND = 2001 min_node.PATH_HITS_ISLAND 2002 insert_or_update(spf_heap, intf.remote_node) 2003 else if path_metric == intf.remote_node.spf_metric 2004 if min_node is spf_root 2005 add_to_list(intf.remote_node.next_hops, intf) 2006 else 2007 add_list_to_list(intf.remote_node.next_hops, 2008 min_node.next_hops) 2009 if intf.remote_node.IN_MRT_ISLAND 2010 intf.remote_node.PATH_HITS_ISLAND = true 2011 else 2012 intf.remote_node.PATH_HITS_ISLAND = 2013 min_node.PATH_HITS_ISLAND 2015 Figure 27: Island_Marking_SPF for determining if an Island Neighbor 2016 is loop-free 2018 It is also possible that a given prefix is originated by a 2019 combination of non-island routers and island routers. The results of 2020 the Island_Marking_SPF computation can be used to determine if the 2021 shortest path from an IN to reach that prefix hits the MRT island. 2022 The shortest path for the IN to reach prefix P is determined by the 2023 total cost to reach prefix P, which is the sum of the cost for the IN 2024 to reach a prefix-advertising node and the cost with which that node 2025 advertises the prefix. The path with the minimum total cost to 2026 prefix P is chosen. If the prefix-advertising node for that minimum 2027 total cost path has PATH_HITS_ISLAND set to True, then the IN is not 2028 loop-free with respect to the MRT Island for reaching prefix P. If 2029 there multiple minimum total cost paths to reach prefix P, then all 2030 of the prefix-advertising routers involved in the minimum total cost 2031 paths MUST have PATH_HITS_ISLAND set to False for the IN to be 2032 considered loop-free to reach P. 2034 Note that there are other computations that could be used to 2035 determine if paths from a given IN _might_ pass through the MRT 2036 Island for a given prefix or destination. For example, a previous 2037 version of this draft specified running the SPF algorithm on modified 2038 topology which treats the MRT island as a single node (with intra- 2039 island links set to zero cost) in order to provide input to 2040 computations to determine if the path from IN to non-island 2041 destination hits the MRT island in this modified topology. This 2042 computation is enough to guarantee that a path will not hit the MRT 2043 island in the original topology. However, it is possible that a path 2044 which is disqualified for hitting the MRT island in the modified 2045 topology will not actually hit the MRT Island in the original 2046 topology. The algorithm described in Island_Marking_SPF() above does 2047 not modify the original topology, and will only disqualify a path if 2048 the actual path does in fact hit the MRT island. 2050 Since all routers need to come to the same conclusion about which 2051 routers qualify as LFINs, this specification requires that all 2052 routers computing LFINs MUST use an algorithm whose result is 2053 identical to that of the Island_Marking_SPF() in Figure 27. 2055 5.9.3. Computing MRT Next-Hops for Proxy-Nodes 2057 Determining the MRT next-hops for a proxy-node in the degenerate case 2058 where the proxy-node is attached to only one node in the GADAG is 2059 trivial, as all needed information can be derived from that proxy 2060 node attachment router. If there are multiple interfaces connecting 2061 the proxy node to the single proxy node attachment router, then some 2062 can be assigned to MRT-Red and others to MRT_Blue. 2064 Now, consider the proxy-node P that is attached to two proxy-node 2065 attachment routers. The pseudo-code for Select_Proxy_Node_NHs(P,S) 2066 in Figure 28 specifies how a computing-router S MUST compute the MRT 2067 red and blue next-hops to reach proxy-node P. The proxy-node 2068 attachment router with the lower value of mrt_node_id (as defined in 2069 Figure 15) is assigned to X, and the other proxy-node attachment 2070 router is assigned to Y. We will be using the relative order of X,Y, 2071 and S in the partial order defined by the GADAG to determine the MRT 2072 red and blue next-hops to reach P, so we also define A and B as the 2073 order proxies for X and Y, respectively, with respect to S. The 2074 order proxies for all nodes with respect to S were already computed 2075 in Compute_MRT_NextHops(). 2077 def Select_Proxy_Node_NHs(P,S): 2078 if P.pnar1.node.node_id < P.pnar2.node.node_id: 2079 X = P.pnar1.node 2080 Y = P.pnar2.node 2081 else: 2082 X = P.pnar2.node 2083 Y = P.pnar1.node 2084 P.pnar_X = X 2085 P.pnar_Y = Y 2086 A = X.order_proxy 2087 B = Y.order_proxy 2088 if (A is S.localroot 2089 and B is S.localroot): 2090 // case 1.0 2091 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2092 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2093 return 2094 if (A is S.localroot 2095 and B is not S.localroot): 2096 // case 2.0 2097 if B.LOWER: 2098 // case 2.1 2099 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2100 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2101 return 2102 if B.HIGHER: 2103 // case 2.2 2104 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2105 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2106 return 2107 else: 2108 // case 2.3 2109 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2110 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2111 return 2112 if (A is not S.localroot 2113 and B is S.localroot): 2114 // case 3.0 2115 if A.LOWER: 2116 // case 3.1 2117 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2118 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2119 return 2120 if A.HIGHER: 2121 // case 3.2 2122 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2123 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2124 return 2126 else: 2127 // case 3.3 2128 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2129 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2130 return 2131 if (A is not S.localroot 2132 and B is not S.localroot): 2133 // case 4.0 2134 if (S is A.localroot or S is B.localroot): 2135 // case 4.05 2136 if A.topo_order < B.topo_order: 2137 // case 4.05.1 2138 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2139 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2140 return 2141 else: 2142 // case 4.05.2 2143 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2144 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2145 return 2146 if A.LOWER: 2147 // case 4.1 2148 if B.HIGHER: 2149 // case 4.1.1 2150 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2151 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2152 return 2153 if B.LOWER: 2154 // case 4.1.2 2155 if A.topo_order < B.topo_order: 2156 // case 4.1.2.1 2157 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2158 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2159 return 2160 else: 2161 // case 4.1.2.2 2162 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2163 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2164 return 2165 else: 2166 // case 4.1.3 2167 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2168 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2169 return 2170 if A.HIGHER: 2171 // case 4.2 2172 if B.HIGHER: 2173 // case 4.2.1 2174 if A.topo_order < B.topo_order: 2175 // case 4.2.1.1 2176 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2177 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2178 return 2179 else: 2180 // case 4.2.1.2 2181 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2182 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2183 return 2184 if B.LOWER: 2185 // case 4.2.2 2186 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2187 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2188 return 2189 else: 2190 // case 4.2.3 2191 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2192 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2193 return 2194 else: 2195 // case 4.3 2196 if B.LOWER: 2197 // case 4.3.1 2198 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 2199 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2200 return 2201 if B.HIGHER: 2202 // case 4.3.2 2203 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2204 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 2205 return 2206 else: 2207 // case 4.3.3 2208 if A.topo_order < B.topo_order: 2209 // case 4.3.3.1 2210 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 2211 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 2212 return 2213 else: 2214 // case 4.3.3.2 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 assert(False) 2220 Figure 28: Select_Proxy_Node_NHs() 2222 It is useful to understand up front that the blue next-hops to reach 2223 proxy-node P produced by Select_Proxy_Node_NHs() will always be the 2224 next-hops that reach proxy-node attachment router X, while the red 2225 next-hops to reach proxy-node P will always be the next-hops that 2226 reach proxy-node attachment router Y. This is different from the red 2227 and blue next-hops produced by Compute_MRT_NextHops() where, for 2228 example, blue next-hops to a destination that is ordered with respect 2229 to the source will always correspond to an INCREASING next-hop on the 2230 GADAG. The exact choice of which next-hops chosen by 2231 Select_Proxy_Node_NHs() as the blue next-hops to reach P (which will 2232 necessarily go through X on its way to P) does depend on the GADAG, 2233 but the relationship is more complex than was the case with 2234 Compute_MRT_NextHops(). 2236 There are twenty-one different relative order relationships between 2237 A, B and S that Select_Proxy_Node_NHs() uses to determine red and 2238 blue next-hops to P. This document does not attempt to provide an 2239 exhaustive description of each case considered in 2240 Select_Proxy_Node_NHs(). Instead we provide a high level overview of 2241 the different cases, and we consider a few cases in detail to give an 2242 example of the reasoning that can be used to understand each case. 2244 At the highest level, Select_Proxy_Node_NHs() distinguishes between 2245 four different cases depending on whether or not A or B is the 2246 localroot for S. For example, for case 4.0, neither A nor B is the 2247 localroot for S. Case 4.05 addresses the case where S is the 2248 localroot for either A or B, while cases 4.1, 4.2, and 4.3 address 2249 the cases where A is ordered lower than S, A is ordered higher than 2250 S, or A is unordered with respect to S on the GADAG. In general, 2251 each of these cases is then further subdivided into whether or not B 2252 is ordered lower than S, B is ordered higher than S, or B is 2253 unordered with respect to S. In some cases we also need a further 2254 level of discrimination, where we use the topological sort order of A 2255 with respect to B. 2257 As a detailed example, let's consider case 4.1 and all of its sub- 2258 cases, and explain why the red and blue next-hops to reach P are 2259 chosen as they are in Select_Proxy_Node_NHs(). In case 4.1, neither 2260 A nor B is the localroot for S, S is not the localroot for A or B, 2261 and A is ordered lower than S on the GADAG. In this situation, we 2262 know that the red path to reach X (as computed in 2263 Compute_MRT_NextHops()) will follow DECREASING next-hops towards A, 2264 while the blue path to reach X will follow INCREASING next-hops to 2265 the localroot, and then INCREASING next-hops to A. 2267 Now consider sub-case 4.1.1 where B is ordered higher than S. In 2268 this situation, we know that the blue path to reach Y will follow 2269 INCREASING next-hops towards B, while the red next-hops to reach Y 2270 will follow DECREASING next-hops to the localroot, and then 2271 DECREASING next-hops to B. So to reach X and Y by two disjoint 2272 paths, we can choose the red next-hops to X and the blue next-hops to 2273 Y. We have chosen the convention that blue next-hops to P are those 2274 that pass through X, and red next-hops to P are those that pass 2275 through Y, so we can see that case 4.1.1 produces the desired result. 2276 Choosing blue to X and red to Y does not produce disjoint paths 2277 because the paths intersect at least at the localroot. 2279 Now consider sub-case 4.1.2 where B is ordered lower than S. In this 2280 situation, we know that the red path to reach Y will follow 2281 DECREASING next-hops towards B, while the BLUE next-hops to reach Y 2282 will follow INCREASING next-hops to the localroot, and then 2283 INCREASING next-hops to A. The choice here is more difficult than in 2284 4.1.1 because A and B are both on the DECREASING path from S towards 2285 the localroot. We want to use the direct DECREASING(red) path to the 2286 one that is nearer to S on the GADAG. We get this extra information 2287 by comparing the topological sort order of A and B. If 2288 A.topo_orderB.topo_order, then we use red to X and blue to Y. 2293 Note that when A is unordered with respect to B, the result of 2294 comparing A.topo_order with B.topo_order could be greater than or 2295 less than. In this case, the result doesn't matter because either 2296 choice (red to Y and blue to X or red to X and blue to Y) would work. 2297 What is required is that all nodes in the network give the same 2298 result when comparing A.topo_order with B.topo_order. This is 2299 guarantee by having all nodes run the same algorithm 2300 (Run_Topological_Sort_GADAG()) to compute the topological sort order. 2302 Finally we consider case 4.1.3, where B is unordered with respect to 2303 S. In this case, the blue path to reach Y will follow the DECREASING 2304 next-hops towards the localroot until it reaches some node (K) which 2305 is ordered less than B, after which it will take INCREASING next-hops 2306 to B. The red path to reach Y will follow the INCREASING next-hops 2307 towards the localroot until it reaches some node (L) which is ordered 2308 greater than B, after which it will take DECREASING next-hops to B. 2309 Both K and A are reached by DECREASING from S, but we don't have 2310 information about whether or not that DECREASING path will hit K or A 2311 first. Instead, we do know that the INCREASING path from S will hit 2312 L before reaching A. Therefore, we use the red path to reach Y and 2313 the red path to reach X. 2315 Similar reasoning can be applied to understand the other seventeen 2316 cases used in Select_Proxy_Node_NHs(). However, cases 2.3 and 3.3 2317 deserve special attention because the correctness of the solution for 2318 these two cases relies on a special property of the GADAGs that we 2319 have constructed in this algorithm, a property not shared by all 2320 GADAGs in general. Focusing on case 2.3, we consider the case where 2321 A is the localroot for S, while B is not, and B is unordered with 2322 respect to S. The red path to X DECREASES from S to the localroot A, 2323 while the blue path to X INCREASES from S to the localroot A. The 2324 blue path to Y DECREASES towards the localroot A until it reaches 2325 some node (K) which is ordered less than B, after which the path 2326 INCREASES to B. The red path to Y INCREASES towards the localroot A 2327 until it reaches some node (L) which is ordered greater than B, after 2328 which the path DECREASES to B. It can be shown that for an arbitrary 2329 GADAG, with only the ordering relationships computed so far, we don't 2330 have enough information to choose a pair of paths to reach X and Y 2331 that are guaranteed to be disjoint. In some topologies, A will play 2332 the role of K, the first node ordered less than B on the blue path to 2333 Y. In other topologies, A will play the role of L, the first node 2334 ordered greater than B on the red path to Y. The basic problem is 2335 that we cannot distinguish between these two cases based on the 2336 ordering relationships. 2338 As discussed Section 5.8, the GADAGs that we construct using the 2339 algorithm in this document are not arbitrary GADAGs. They have the 2340 additional property that incoming links to a localroot come from only 2341 one other node in the same block. This is a result of the method of 2342 construction. This additional property guarantees that localroot A 2343 will never play the role of L in the red path to Y, since L must have 2344 at least two incoming links from different nodes in the same block in 2345 the GADAG. This in turn allows Select_Proxy_Node_NHs() to choose the 2346 red path to Y and the red path to X as the disjoint MRT paths to 2347 reach P. 2349 5.9.4. Computing MRT Alternates for Proxy-Nodes 2351 After finding the red and the blue next-hops for a given proxy-node 2352 P, it is necessary to know which one of these to use in the case of 2353 failure. This can be done by Select_Alternates_Proxy_Node(), as 2354 shown in the pseudo-code in Figure 29. 2356 def Select_Alternates_Proxy_Node(P,F,primary_intf): 2357 S = primary_intf.local_node 2358 X = P.pnar_X 2359 Y = P.pnar_Y 2360 A = X.order_proxy 2361 B = Y.order_proxy 2362 if F is A and F is B: 2363 return 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y' 2364 if F is A: 2365 return 'USE_RED' 2367 if F is B: 2368 return 'USE_BLUE' 2370 if not In_Common_Block(A, B): 2371 if In_Common_Block(F, A): 2372 return 'USE_RED' 2373 elif In_Common_Block(F, B): 2374 return 'USE_BLUE' 2375 else: 2376 return 'USE_RED_OR_BLUE' 2377 if (not In_Common_Block(F, A) 2378 and not In_Common_Block(F, A) ): 2379 return 'USE_RED_OR_BLUE' 2381 alt_to_X = Select_Alternates(X, F, primary_intf) 2382 alt_to_Y = Select_Alternates(Y, F, primary_intf) 2384 if (alt_to_X == 'USE_RED_OR_BLUE' 2385 and alt_to_Y == 'USE_RED_OR_BLUE'): 2386 return 'USE_RED_OR_BLUE' 2387 if alt_to_X == 'USE_RED_OR_BLUE': 2388 return 'USE_BLUE' 2389 if alt_to_Y == 'USE_RED_OR_BLUE': 2390 return 'USE_RED' 2392 if (A is S.localroot 2393 and B is S.localroot): 2394 // case 1.0 2395 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 2396 return 'USE_RED_OR_BLUE' 2397 if alt_to_X == 'USE_BLUE': 2398 return 'USE_BLUE' 2399 if alt_to_Y == 'USE_RED': 2400 return 'USE_RED' 2401 assert(False) 2402 if (A is S.localroot 2403 and B is not S.localroot): 2404 // case 2.0 2405 if B.LOWER: 2406 // case 2.1 2407 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 2408 return 'USE_RED_OR_BLUE' 2409 if alt_to_X == 'USE_BLUE': 2410 return 'USE_BLUE' 2411 if alt_to_Y == 'USE_RED': 2412 return 'USE_RED' 2413 assert(False) 2414 if B.HIGHER: 2416 // case 2.2 2417 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 2418 return 'USE_RED_OR_BLUE' 2419 if alt_to_X == 'USE_RED': 2420 return 'USE_BLUE' 2421 if alt_to_Y == 'USE_BLUE': 2422 return 'USE_RED' 2423 assert(False) 2424 else: 2425 // case 2.3 2426 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'): 2427 return 'USE_RED_OR_BLUE' 2428 if alt_to_X == 'USE_RED': 2429 return 'USE_BLUE' 2430 if alt_to_Y == 'USE_RED': 2431 return 'USE_RED' 2432 assert(False) 2433 if (A is not S.localroot 2434 and B is S.localroot): 2435 // case 3.0 2436 if A.LOWER: 2437 // case 3.1 2438 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 2439 return 'USE_RED_OR_BLUE' 2440 if alt_to_X == 'USE_RED': 2441 return 'USE_BLUE' 2442 if alt_to_Y == 'USE_BLUE': 2443 return 'USE_RED' 2444 assert(False) 2445 if A.HIGHER: 2446 // case 3.2 2447 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 2448 return 'USE_RED_OR_BLUE' 2449 if alt_to_X == 'USE_BLUE': 2450 return 'USE_BLUE' 2451 if alt_to_Y == 'USE_RED': 2452 return 'USE_RED' 2453 assert(False) 2454 else: 2455 // case 3.3 2456 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'): 2457 return 'USE_RED_OR_BLUE' 2458 if alt_to_X == 'USE_RED': 2459 return 'USE_BLUE' 2460 if alt_to_Y == 'USE_RED': 2461 return 'USE_RED' 2462 assert(False) 2463 if (A is not S.localroot 2464 and B is not S.localroot): 2465 // case 4.0 2466 if (S is A.localroot or S is B.localroot): 2467 // case 4.05 2468 if A.topo_order < B.topo_order: 2469 // case 4.05.1 2470 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 2471 return 'USE_RED_OR_BLUE' 2472 if alt_to_X == 'USE_BLUE': 2473 return 'USE_BLUE' 2474 if alt_to_Y == 'USE_RED': 2475 return 'USE_RED' 2476 assert(False) 2477 else: 2478 // case 4.05.2 2479 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 2480 return 'USE_RED_OR_BLUE' 2481 if alt_to_X == 'USE_RED': 2482 return 'USE_BLUE' 2483 if alt_to_Y == 'USE_BLUE': 2484 return 'USE_RED' 2485 assert(False) 2486 if A.LOWER: 2487 // case 4.1 2488 if B.HIGHER: 2489 // case 4.1.1 2490 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 2491 return 'USE_RED_OR_BLUE' 2492 if alt_to_X == 'USE_RED': 2493 return 'USE_BLUE' 2494 if alt_to_Y == 'USE_BLUE': 2495 return 'USE_RED' 2496 assert(False) 2497 if B.LOWER: 2498 // case 4.1.2 2499 if A.topo_order < B.topo_order: 2500 // case 4.1.2.1 2501 if (alt_to_X == 'USE_BLUE' 2502 and alt_to_Y == 'USE_RED'): 2503 return 'USE_RED_OR_BLUE' 2504 if alt_to_X == 'USE_BLUE': 2505 return 'USE_BLUE' 2506 if alt_to_Y == 'USE_RED': 2507 return 'USE_RED' 2508 assert(False) 2509 else: 2510 // case 4.1.2.2 2511 if (alt_to_X == 'USE_RED' 2512 and alt_to_Y == 'USE_BLUE'): 2513 return 'USE_RED_OR_BLUE' 2514 if alt_to_X == 'USE_RED': 2515 return 'USE_BLUE' 2516 if alt_to_Y == 'USE_BLUE': 2517 return 'USE_RED' 2518 assert(False) 2519 else: 2520 // case 4.1.3 2521 if (F.LOWER and not F.HIGHER 2522 and F.topo_order > A.topo_order): 2523 // case 4.1.3.1 2524 return 'USE_RED' 2525 else: 2526 // case 4.1.3.2 2527 return 'USE_BLUE' 2528 if A.HIGHER: 2529 // case 4.2 2530 if B.HIGHER: 2531 // case 4.2.1 2532 if A.topo_order < B.topo_order: 2533 // case 4.2.1.1 2534 if (alt_to_X == 'USE_BLUE' 2535 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.2.1.2 2544 if (alt_to_X == 'USE_RED' 2545 and alt_to_Y == 'USE_BLUE'): 2546 return 'USE_RED_OR_BLUE' 2547 if alt_to_X == 'USE_RED': 2548 return 'USE_BLUE' 2549 if alt_to_Y == 'USE_BLUE': 2550 return 'USE_RED' 2551 assert(False) 2552 if B.LOWER: 2553 // case 4.2.2 2554 if (alt_to_X == 'USE_BLUE' 2555 and alt_to_Y == 'USE_RED'): 2556 return 'USE_RED_OR_BLUE' 2557 if alt_to_X == 'USE_BLUE': 2558 return 'USE_BLUE' 2559 if alt_to_Y == 'USE_RED': 2561 return 'USE_RED' 2562 assert(False) 2563 else: 2564 // case 4.2.3 2565 if (F.HIGHER and not F.LOWER 2566 and F.topo_order < A.topo_order): 2567 return 'USE_RED' 2568 else: 2569 return 'USE_BLUE' 2570 else: 2571 // case 4.3 2572 if B.LOWER: 2573 // case 4.3.1 2574 if (F.LOWER and not F.HIGHER 2575 and F.topo_order > B.topo_order): 2576 return 'USE_BLUE' 2577 else: 2578 return 'USE_RED' 2579 if B.HIGHER: 2580 // case 4.3.2 2581 if (F.HIGHER and not F.LOWER 2582 and F.topo_order < B.topo_order): 2583 return 'USE_BLUE' 2584 else: 2585 return 'USE_RED' 2586 else: 2587 // case 4.3.3 2588 if A.topo_order < B.topo_order: 2589 // case 4.3.3.1 2590 if (alt_to_X == 'USE_BLUE' 2591 and alt_to_Y == 'USE_RED'): 2592 return 'USE_RED_OR_BLUE' 2593 if alt_to_X == 'USE_BLUE': 2594 return 'USE_BLUE' 2595 if alt_to_Y == 'USE_RED': 2596 return 'USE_RED' 2597 assert(False) 2598 else: 2599 // case 4.3.3.2 2600 if (alt_to_X == 'USE_RED' 2601 and alt_to_Y == 'USE_BLUE'): 2602 return 'USE_RED_OR_BLUE' 2603 if alt_to_X == 'USE_RED': 2604 return 'USE_BLUE' 2605 if alt_to_Y == 'USE_BLUE': 2606 return 'USE_RED' 2607 assert(False) 2608 assert(False) 2609 Figure 29: Select_Alternates_Proxy_Node() 2611 Select_Alternates_Proxy_Node(P,F,primary_intf) determines whether it 2612 is safe to use the blue path to P (which goes through X), the red 2613 path to P (which goes through Y), or either, when the primary_intf to 2614 node F (and possibly node F) fails. The basic approach is to run 2615 Select_Alternates(X,F,primary_intf) and 2616 Select_Alternates(Y,F,primary_intf) to determine which of the two MRT 2617 paths to X and which of the two MRT paths to Y is safe to use in the 2618 event of the failure of F. In general, we will find that if it is 2619 safe to use a particular path to X or Y when F fails, and 2620 Select_Proxy_Node_NHs() used that path when constructing the red or 2621 blue path to reach P, then it will also be safe to use that path to 2622 reach P when F fails. This rule has one exception which is covered 2623 below. First, we give a concrete example of how 2624 Select_Alternates_Proxy_Node() works in the common case. 2626 The twenty one ordering relationships used in Select_Proxy_Node_NHs() 2627 are repeated in Select_Alternates_Proxy_Node(). We focus on case 2628 4.1.1 to give give a detailed example of the reasoning used in 2629 Select_Alternates_Proxy_Node(). In Select_Proxy_Node_NHs(), we 2630 determined for case 4.1.1 that the red next-hops to X and the blue 2631 next-hops to Y allow us to reach X and Y by disjoint paths, and are 2632 thus the blue and red next-hops to reach P. Therefore, if we run 2633 Select_Alternates(X, F, primary_intf) and we find that it is safe to 2634 USE_RED to reach X, then we also conclude that it is safe to use the 2635 MRT path through X to reach P (the blue path to P) when F fails. 2636 Similarly, if run Select_Alternates(X, F, primary_intf) and we find 2637 that it is safe to USE_BLUE to reach Y, then we also conclude that it 2638 is safe to use the MRT path through Y to reach P (the red path to P) 2639 when F fails. If both of the paths that were used in 2640 Select_Proxy_Node_NHs() to construct the blue and red paths to P are 2641 found to be safe to use to use to reach X and Y, t then we conclude 2642 that we can use either the red or the blue path to P. 2644 This simple reasoning gives the correct answer in most of the cases. 2645 However, additional logic is needed when either A or B (but not both 2646 A and B) is unordered with respect to S. This applies to cases 2647 4.1.3, 4.2.3, 4.3.1, and 4.3.2. Looking at case 4.1.3 in more 2648 detail, A is ordered less than S, but B is unordered with respect to 2649 S. In the discussion of case 4.1.3 above, we saw that 2650 Select_Proxy_Node_NHs() chose the red path to reach Y and the red 2651 path to reach X. We also saw that the red path to reach Y will 2652 follow the INCREASING next-hops towards the localroot until it 2653 reaches some node (L) which is ordered greater than B, after which it 2654 will take DECREASING next-hops to B. The problem is that the red 2655 path to reach P (the one that goes through Y) won't necessarily be 2656 the same as the red path to reach Y. This is because the next-hop 2657 that node L computes for its red next-hop to reach P may be different 2658 from the next-hop it computes for its red next-hop to reach Y. This 2659 is because B is ordered lower than L, so L applies case 4.1.2 of 2660 Select_Proxy_Node_NHs() in order to determine its next-hops to reach 2661 P. If A.topo_orderB.topo_order (case 4.1.2.2), then L will choose 2665 INCREASING next-hops to reach B, which is different from what L 2666 computes in Compute_MRT_NextHops() to reach Y. So testing the safety 2667 of the path for S to reach Y on failure of F as a surrogate for the 2668 safety of using the red path to reach P is not reliable in this case. 2669 It is possible construct topologies where the red path to P hits F 2670 even though the red path to Y does not hit F. 2672 Fortunately there is enough information in the order relationships 2673 that we have already computed to still figure out which alternate to 2674 choose in these four cases. The basic idea is to always choose the 2675 path involving the ordered node, unless that path would hit F. 2676 Returning to case 4.1.3, we see that since A is ordered lower than S, 2677 the only way for S to hit F using a simple DECREASING path to A is 2678 for F to lie between A and S on the GADAG. This scenario is covered 2679 by requiring that F be lower than S (but not also higher than S) and 2680 that F.topo_order>A.topo_order in case 4.1.3.1. 2682 We just need to confirm that it is safe to use the path involving B 2683 in this scenario. In case 4.1.3.1, either F is between A and S on 2684 the GADAG, or F is unordered with respect to A and lies on the 2685 DECREASING path from S to the localroot. When F is between A and S 2686 on the GADAG, then the path through B chosen to avoid A in 2687 Select_Proxy_Node_NHs() will also avoid F. When F is unordered with 2688 respect to A and lies on the DECREASING path from S to the localroot, 2689 then we consider two cases. Either F.topo_orderB.topo_order. In the first case, since 2691 F.topo_orderA.topo_order, it must be 2692 the case that A.topo_orderB.topo_order, the only way for the path involving B to 2696 hit F is if it DECREASES from L to B through F , ie. it must be that 2697 L>>F>>B. However, since S>>F, this would imply that S>>B. However, 2698 we know that S is unordered with respect to B, so the second case 2699 cannot occur. So we have demonstrated that the red path to P (which 2700 goes via B and Y) is safe to use under the conditions of 4.1.3.1. 2701 Similar reasoning can be applied to the other three special cases 2702 where either A or B is unordered with respect to S. 2704 6. MRT Lowpoint Algorithm: Next-hop conformance 2706 This specification defines the MRT Lowpoint Algorithm, which include 2707 the construction of a common GADAG and the computation of MRT-Red and 2708 MRT-Blue next-hops to each node in the graph. An implementation MAY 2709 select any subset of next-hops for MRT-Red and MRT-Blue that respect 2710 the available nodes that are described in Section 5.7 for each of the 2711 MRT-Red and MRT-Blue and the selected next-hops are further along in 2712 the interval of allowed nodes towards the destination. 2714 For example, the MRT-Blue next-hops used when the destination Y >> X, 2715 the computing router, MUST be one or more nodes, T, whose topo_order 2716 is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y 2717 is T. Similarly, the MRT-Red next-hops MUST be have a topo_order in 2718 the interval [R-small.topo_order, X.topo_order] or [Y.topo_order, 2719 R-big.topo_order]. 2721 Implementations SHOULD implement the Select_Alternates() function to 2722 pick an MRT-FRR alternate. 2724 7. Broadcast interfaces 2726 When broadcast interfaces are used to connect nodes, the broadcast 2727 network MUST be represented as a pseudonode, where each real node 2728 connects to the pseudonode. The interface metric in the direction 2729 from real node to pseudonode is the non-zero interface metric, while 2730 the interface metric in the direction from the pseudonode to the real 2731 node is set to zero. This is consistent with the way that broadcast 2732 interfaces are represented as pseudonodes in IS-IS and OSPF. 2734 Pseudonodes MUST be treated as equivalent to real nodes in the 2735 network graph used in the MRT algorithm with a few exceptions 2736 detailed below. 2738 The pseudonodes MUST be included in the computation of the GADAG. 2739 The neighbors of the pseudonode need to know the mrt_node_id of the 2740 pseudonode in order to consistently order interfaces, which is needed 2741 to compute the GADAG. The mrt_node_id for IS-IS is the 7 octet 2742 neighbor system ID and pseudonode number in TLV #22 or TLV#222. The 2743 mrt_node_id for OSPFv2 is the 4 octet interface address of the 2744 Designated Router found in the Link ID field for the link type 2 2745 (transit network) in the Router-LSA. The mrt_node_id for OSPFv3 is 2746 the 4 octet interface address of the Designated Router found in the 2747 Neighbor Interface ID field for the link type 2 (transit network) in 2748 the Router-LSA. pseudonodes MUST NOT be considered as candidates for 2749 GADAG root selection. Note that this is different from the Neighbor 2750 Router ID field used for the mrt_node_id for point-to-point links in 2751 OSPFv3 Router-LSAs given in Figure 15. 2753 Pseudonodes MUST NOT be considered as candidates for selection as 2754 GADAG root. This rule is intended to result in a more stable 2755 network- wide selection of GADAG root by removing the possibility 2756 that the change of Designated Router or Designated Intermediate 2757 System on a broadcast network can result in a change of GADAG root. 2759 7.1. Computing MRT next-hops on broadcast networks 2761 The pseudonode does not correspond to an real node, so it is not 2762 actually involved in forwarding. A real node on a broadcast network 2763 cannot simply forward traffic to the broadcast network. It must 2764 specify another real node on the broadcast network as the next-hop. 2765 On a network graph where a broadcast network is represented by a 2766 pseudonode, this means that if a real node determines that the next- 2767 hop to reach a given destination is a pseudonode, it must also 2768 determine the next-next-hop for that destination in the network 2769 graph, which corresponds to a real node attached to the broadcast 2770 network. 2772 It is interesting to note that this issue is not unique to the MRT 2773 algorithm, but is also encountered in normal SPF computations for 2774 IGPs. Section 16.1.1 of [RFC2328] describes how this is done for 2775 OSPF. As OSPF runs Dijkstra's algorithm, whenever a shorter path is 2776 found reach a real destination node, and the shorter path is one hop 2777 from the computing routing, and that one hop is a pseudonode, then 2778 the next-hop for that destination is taken from the interface IP 2779 address in the Router-LSA correspond to the link to the real 2780 destination node 2782 For IS-IS, in the example pseudo-code implementation of Dijkstra's 2783 algorithm in Annex C of [ISO10589-Second-Edition] whenever the 2784 algorithm encounters an adjacency from a real node to a pseudonode, 2785 it gets converted to a set of adjacencies from the real node to the 2786 neighbors of the pseudonode. In this way, the computed next-hops 2787 point all the way to the real node, and not the pseudonode. 2789 We could avoid the problem of determining next-hops across 2790 pseudonodes in MRT by converting the pseudonode representation of 2791 broadcast networks to a full mesh of links between real nodes on the 2792 same network. However, if we make that conversion before computing 2793 the GADAG, we lose information about which links actually correspond 2794 to a single physical interface into the broadcast network. This 2795 could result computing red and blue next-hops that use the same 2796 broadcast interface, in which case neither the red nor the blue next- 2797 hop would be usable as an alternate on failure of the broadcast 2798 interface. 2800 Instead, we take the following approach, which maintains the property 2801 that either the red and blue next-hop will avoid the broadcast 2802 network, if topologically allowed. We run the MRT algorithm treating 2803 the pseudonodes as equivalent to real nodes in the network graph, 2804 with the exceptions noted above. In addition to running the MRT 2805 algorithm from the point of view of itself, a computing router 2806 connected to a pseudonode MUST also run the MRT algorithm from the 2807 point of view of each of its pseudonode neighbors. For example, if a 2808 computing router S determines that its MRT red next-hop to reach a 2809 destination D is a pseudonode P, S looks at its MRT algorithm 2810 computation from P's point of view to determine P's red next-hop to 2811 reach D, say interface 1 on node X. S now knows that its real red 2812 next-hop to reach D is interface 1 on node X on the broadcast network 2813 represented by P, and can install the corresponding entry in its FIB. 2815 7.2. Using MRT next-hops as alternates in the event of failures on 2816 broadcast networks 2818 In the previous section, we specified how to compute MRT next-hops 2819 when broadcast networks are involved. In this section, we discuss 2820 how a PLR can use those MRT next-hops in the event of failures 2821 involving broadcast networks. 2823 A PLR attached to a broadcast network running only OSPF or IS-IS with 2824 large Hello intervals has limited ability to quickly detect failures 2825 on a broadcast network. The only failure mode that can be quickly 2826 detected is the failure of the physical interface connecting the PLR 2827 to the broadcast network. For the failure of the interface 2828 connecting the PLR to the broadcast network, the alternate that 2829 avoids the broadcast network can be computed by using the broadcast 2830 network pseudonode as F, the primary next-hop node, in 2831 Select_Alternates(). This will choose an alternate path that avoids 2832 the broadcast network. However, the alternate path will not 2833 necessarily avoid all of the real nodes connected to the broadcast 2834 network. This is because we have used the pseudonode to represent 2835 the broadcast network. And we have enforced the node-protecting 2836 property of MRT on the pseudonode to provide protection against 2837 failure of the broadcast network, not the real next-hop nodes on the 2838 broadcast network. This is the best that we can hope to do if 2839 failure of the broadcast interface is the only failure mode that the 2840 PLR can respond to. 2842 We can improve on this if the PLR also has the ability to quickly 2843 detect a lack of connectivity across the broadcast network to a given 2844 IP-layer node. This can be accomplished by running BFD between all 2845 pairs of IGP neighbors on the broadcast network. Note that in the 2846 case of OSPF, this would require establishing BFD sessions between 2847 all pairs of neighbors in the 2-WAY state. When the PLR can quickly 2848 detect the failure of a particular next-hop across a broadcast 2849 network, then the PLR can be more selective in its choice of 2850 alternates. For example, when the PLR observes that connectivity to 2851 an IP-layer node on a broadcast network has failed, the PLR may 2852 choose to still use the broadcast network to reach other IP-layer 2853 nodes which are still reachable. Or if the PLR observes that 2854 connectivity has failed to several IP-layer nodes on the same 2855 broadcast network, it may choose to treat the entire broadcast 2856 network as failed. The choice of MRT alternates by a PLR for a 2857 particular set of failure conditions is a local decision, since it 2858 does not require coordination with other nodes. 2860 8. Evaluation of Alternative Methods for Constructing GADAGs 2862 This document specifies the MRT Lowpoint algorithm. One component of 2863 the algorithm involves constructing a common GADAG based on the 2864 network topology. The MRT Lowpoint algorithm computes the GADAG 2865 using the method described in Section 5.5. This method aims to 2866 minimize the amount of computation required to compute the GADAG. In 2867 the process of developing the MRT Lowpoint algorithm, two alternative 2868 methods for constructing GADAGs were also considered. These 2869 alternative methods are described in Appendix B and Appendix C. In 2870 general, these other two methods require more computation to compute 2871 the GADAG. The analysis below was performed to determine if the 2872 alternative GADAG construction methods produce shorter MRT alternate 2873 paths in real network topologies, and if so, to what extent. 2875 Figure 30 compares results obtained using the three different methods 2876 for constructing GADAGs on five different service provider network 2877 topologies. MRT_LOWPOINT indicates the method specified in 2878 Section 5.5, while MRT_SPF and MRT_HYBRID indicate the methods 2879 specified in Appendix B and Appendix C, respectively. The columns on 2880 the right present the distribution of alternate path lengths for each 2881 GADAG construction method. Each MRT computation was performed using 2882 a same GADAG root chosen based on centrality. 2884 For three of the topologies analyzed (T201, T206, and T211), the use 2885 of MRT_SPF or MRT_HYBRID methods does not appear to provide a 2886 significantly shorter alternate path lengths compared to the 2887 MRT_LOWPOINT method. However, for two of the topologies (T216 and 2888 T219), the use of the MRT_SPF method resulted in noticeably shorter 2889 alternate path lengths than the use of the MRT_LOWPOINT or MRT_HYBRID 2890 methods. 2892 It was decided to use the MRT_LOWPOINT method to construct the GADAG 2893 in the algorithm specified in this draft, in order to initially offer 2894 an algorithm with lower computational requirements. These results 2895 indicate that in the future it may be useful to evaluate and 2896 potentially specify other MRT algorithm variants that use different 2897 GADAG construction methods. 2899 +-------------------------------------------------------------------+ 2900 | Topology name | percentage of failure scenarios | 2901 | | protected by an alternate N hops | 2902 | GADAG construction | longer than the primary path | 2903 | method +------------------------------------+ 2904 | | | | | | | | | | no | 2905 | | | | | | |10 |12 |14 | alt| 2906 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 2907 +------------------------------+---+---+---+---+---+---+---+---+----+ 2908 | T201(avg primary hops=3.5) | | | | | | | | | | 2909 | MRT_HYBRID | 33| 26| 23| 6| 3| | | | | 2910 | MRT_SPF | 33| 36| 23| 6| 3| | | | | 2911 | MRT_LOWPOINT | 33| 36| 23| 6| 3| | | | | 2912 +------------------------------+---+---+---+---+---+---+---+---+----+ 2913 | T206(avg primary hops=3.7) | | | | | | | | | | 2914 | MRT_HYBRID | 50| 35| 13| 2| | | | | | 2915 | MRT_SPF | 50| 35| 13| 2| | | | | | 2916 | MRT_LOWPOINT | 55| 32| 13| | | | | | | 2917 +------------------------------+---+---+---+---+---+---+---+---+----+ 2918 | T211(avg primary hops=3.3) | | | | | | | | | | 2919 | MRT_HYBRID | 86| 14| | | | | | | | 2920 | MRT_SPF | 86| 14| | | | | | | | 2921 | MRT_LOWPOINT | 85| 15| 1| | | | | | | 2922 +------------------------------+---+---+---+---+---+---+---+---+----+ 2923 | T216(avg primary hops=5.2) | | | | | | | | | | 2924 | MRT_HYBRID | 23| 22| 18| 13| 10| 7| 4| 2| 2| 2925 | MRT_SPF | 35| 32| 19| 9| 3| 1| | | | 2926 | MRT_LOWPOINT | 28| 25| 18| 11| 7| 6| 3| 2| 1| 2927 +------------------------------+---+---+---+---+---+---+---+---+----+ 2928 | T219(avg primary hops=7.7) | | | | | | | | | | 2929 | MRT_HYBRID | 20| 16| 13| 10| 7| 5| 5| 5| 3| 2930 | MRT_SPF | 31| 23| 19| 12| 7| 4| 2| 1| | 2931 | MRT_LOWPOINT | 19| 14| 15| 12| 10| 8| 7| 6| 10| 2932 +------------------------------+---+---+---+---+---+---+---+---+----+ 2934 Figure 30 2936 9. Implementation Status 2938 [RFC Editor: please remove this section prior to publication.] 2940 Please see [I-D.ietf-rtgwg-mrt-frr-architecture] for details on 2941 implementation status. 2943 10. Operational Considerations 2945 This sections discusses operational considerations related to the the 2946 MRT Lowpoint algorithm and other potential MRT algorithm variants. 2947 For a discussion of operational considerations related to MRT-FRR in 2948 general, see the Operational Considerations section of 2949 [I-D.ietf-rtgwg-mrt-frr-architecture]. 2951 10.1. GADAG Root Selection 2953 The Default MRT Profile uses the GADAG Root Selection Priority 2954 advertised by routers as the primary criterion for selecting the 2955 GADAG root. It is RECOMMENDED that an operator designate a set of 2956 routers as good choices for selection as GADAG root by setting the 2957 GADAG Root Selection Priority for that set of routers to lower (more 2958 preferred) numerical values. Criteria for making this designation 2959 are discussed below. 2961 Analysis has shown that the centrality of a router can have a 2962 significant impact on the lengths of the alternate paths computed. 2963 Therefore, it is RECOMMENDED that off-line analysis that considers 2964 the centrality of a router be used to help determine how good a 2965 choice a particular router is for the role of GADAG root. 2967 If the router currently selected as GADAG root becomes unreachable in 2968 the IGP topology, then a new GADAG root will be selected. Changing 2969 the GADAG root can change the overall structure of the GADAG as well 2970 the paths of the red and blue MRT trees built using that GADAG. In 2971 order to minimize change in the associated red and blue MRT 2972 forwarding entries that can result from changing the GADAG root, it 2973 is RECOMMENDED that operators prioritize for selection as GADAG root 2974 those routers that are expected to consistently remain part of the 2975 IGP topology. 2977 10.2. Destination-rooted GADAGs 2979 The MRT Lowpoint algorithm constructs a single GADAG rooted at a 2980 single node selected as the GADAG root. It is also possible to 2981 construct a different GADAG for each destination, with the GADAG 2982 rooted at the destination. A router can compute the MRT-Red and MRT- 2983 Blue next-hops for that destination based on the GADAG rooted at that 2984 destination. Building a different GADAG for each destination is 2985 computationally more expensive, but it may give somewhat shorter 2986 alternate paths. Using destination-rooted GADAGs would require a new 2987 MRT profile to be created with a new MRT algorithm specification, 2988 since all routers in the MRT Island would need to use destination- 2989 rooted GADAGs. 2991 11. Acknowledgements 2993 The authors would like to thank Shraddha Hegde, Eric Wu, Janos 2994 Farkas, and Stewart Bryant for their suggestions and review. We 2995 would also like to thank Anil Kumar SN for his assistance in 2996 clarifying the algorithm description and pseudo-code. 2998 12. IANA Considerations 3000 This document includes no request to IANA. 3002 13. Security Considerations 3004 The algorithm described in this document does not introduce new 3005 security concerns beyond those already discussed in the document 3006 describing the MRT FRR architecture 3007 [I-D.ietf-rtgwg-mrt-frr-architecture]. 3009 14. References 3011 14.1. Normative References 3013 [I-D.ietf-rtgwg-mrt-frr-architecture] 3014 Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar, 3015 A., Tantsura, J., and R. White, "An Architecture for IP/ 3016 LDP Fast-Reroute Using Maximally Redundant Trees", draft- 3017 ietf-rtgwg-mrt-frr-architecture-07 (work in progress), 3018 October 2015. 3020 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 3021 Requirement Levels", BCP 14, RFC 2119, 3022 DOI 10.17487/RFC2119, March 1997, 3023 . 3025 14.2. Informative References 3027 [EnyediThesis] 3028 Enyedi, G., "Novel Algorithms for IP Fast Reroute", 3029 Department of Telecommunications and Media Informatics, 3030 Budapest University of Technology and Economics Ph.D. 3031 Thesis, February 2011, . 3035 [IEEE8021Qca] 3036 IEEE 802.1, "IEEE 802.1Qca Bridges and Bridged Networks - 3037 Amendment: Path Control and Reservation - Draft 2.1", 3038 (work in progress), June 24, 2015, 3039 . 3041 [ISO10589-Second-Edition] 3042 International Organization for Standardization, 3043 "Intermediate system to Intermediate system intra-domain 3044 routeing information exchange protocol for use in 3045 conjunction with the protocol for providing the 3046 connectionless-mode Network Service (ISO 8473)", ISO/ 3047 IEC 10589:2002, Second Edition, Nov. 2002. 3049 [Kahn_1962_topo_sort] 3050 Kahn, A., "Topological sorting of large networks", 3051 Communications of the ACM, Volume 5, Issue 11 , Nov 1962, 3052 . 3054 [MRTLinear] 3055 Enyedi, G., Retvari, G., and A. Csaszar, "On Finding 3056 Maximally Redundant Trees in Strictly Linear Time", IEEE 3057 Symposium on Computers and Comunications (ISCC) , 2009, 3058 . 3061 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, 3062 DOI 10.17487/RFC2328, April 1998, 3063 . 3065 [RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi 3066 Topology (MT) Routing in Intermediate System to 3067 Intermediate Systems (IS-ISs)", RFC 5120, 3068 DOI 10.17487/RFC5120, February 2008, 3069 . 3071 [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. 3072 So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", 3073 RFC 7490, DOI 10.17487/RFC7490, April 2015, 3074 . 3076 Appendix A. Python Implementation of MRT Lowpoint Algorithm 3078 Below is Python code implementing the MRT Lowpoint algorithm 3079 specified in this document. In order to avoid the page breaks in the 3080 .txt version of the draft, one can cut and paste the Python code from 3081 the .xml version. The code is also posted on Github. 3083 While this Python code is believed to correctly implement the pseudo- 3084 code description of the algorithm, in the event of a difference, the 3085 pseudo-code description should be considered normative. 3087 3088 # This program has been tested to run on Python 2.6 and 2.7 3089 # (specifically Python 2.6.6 and 2.7.8 were tested). 3090 # The program has known incompatibilities with Python 3.X. 3092 # When executed, this program will generate a text file describing 3093 # an example topology. It then reads that text file back in as input 3094 # to create the example topology, and runs the MRT algorithm.This 3095 # was done to simplify the inclusion of the program as a single text 3096 # file that can be extracted from the IETF draft. 3098 # The output of the program is four text files containing a description 3099 # of the GADAG, the blue and red MRTs for all destinations, and the 3100 # MRT alternates for all failures. 3102 import random 3103 import os.path 3104 import heapq 3106 # simple Class definitions allow structure-like dot notation for 3107 # variables and a convenient place to initialize those variables. 3108 class Topology: 3109 def __init__(self): 3110 self.gadag_root = None 3111 self.node_list = [] 3112 self.node_dict = {} 3113 self.test_gr = None 3114 self.island_node_list_for_test_gr = [] 3115 self.stored_named_proxy_dict = {} 3116 self.init_new_computing_router() 3117 def init_new_computing_router(self): 3118 self.island_node_list = [] 3119 self.named_proxy_dict = {} 3121 class Node: 3122 def __init__(self): 3123 self.node_id = None 3124 self.intf_list = [] 3125 self.profile_id_list = [0] 3126 self.GR_sel_priority = 128 3127 self.blue_next_hops_dict = {} 3128 self.red_next_hops_dict = {} 3129 self.blue_to_green_nh_dict = {} 3130 self.red_to_green_nh_dict = {} 3131 self.prefix_cost_dict = {} 3132 self.pnh_dict = {} 3133 self.alt_dict = {} 3134 self.init_new_computing_router() 3135 def init_new_computing_router(self): 3136 self.island_intf_list = [] 3137 self.IN_MRT_ISLAND = False 3138 self.IN_GADAG = False 3139 self.dfs_number = None 3140 self.dfs_parent = None 3141 self.dfs_parent_intf = None 3142 self.dfs_child_list = [] 3143 self.lowpoint_number = None 3144 self.lowpoint_parent = None 3145 self.lowpoint_parent_intf = None 3146 self.localroot = None 3147 self.block_id = None 3148 self.IS_CUT_VERTEX = False 3149 self.blue_next_hops = [] 3150 self.red_next_hops = [] 3151 self.primary_next_hops = [] 3152 self.alt_list = [] 3154 class Interface: 3155 def __init__(self): 3156 self.metric = None 3157 self.area = None 3158 self.MRT_INELIGIBLE = False 3159 self.IGP_EXCLUDED = False 3160 self.SIMULATION_OUTGOING = False 3161 self.init_new_computing_router() 3162 def init_new_computing_router(self): 3163 self.UNDIRECTED = True 3164 self.INCOMING = False 3165 self.OUTGOING = False 3166 self.INCOMING_STORED = False 3167 self.OUTGOING_STORED = False 3168 self.IN_MRT_ISLAND = False 3169 self.PROCESSED = False 3171 class Bundle: 3172 def __init__(self): 3173 self.UNDIRECTED = True 3174 self.OUTGOING = False 3175 self.INCOMING = False 3177 class Alternate: 3178 def __init__(self): 3180 self.failed_intf = None 3181 self.red_or_blue = None 3182 self.nh_list = [] 3183 self.fec = 'NO_ALTERNATE' 3184 self.prot = 'NO_PROTECTION' 3185 self.info = 'NONE' 3187 class Proxy_Node_Attachment_Router: 3188 def __init__(self): 3189 self.prefix = None 3190 self.node = None 3191 self.named_proxy_cost = None 3192 self.min_lfin = None 3193 self.nh_intf_list = [] 3195 class Named_Proxy_Node: 3196 def __init__(self): 3197 self.node_id = None #this is the prefix_id 3198 self.node_prefix_cost_list = [] 3199 self.lfin_list = [] 3200 self.pnar1 = None 3201 self.pnar2 = None 3202 self.pnar_X = None 3203 self.pnar_Y = None 3204 self.blue_next_hops = [] 3205 self.red_next_hops = [] 3206 self.primary_next_hops = [] 3207 self.blue_next_hops_dict = {} 3208 self.red_next_hops_dict = {} 3209 self.pnh_dict = {} 3210 self.alt_dict = {} 3212 def Interface_Compare(intf_a, intf_b): 3213 if intf_a.metric < intf_b.metric: 3214 return -1 3215 if intf_b.metric < intf_a.metric: 3216 return 1 3217 if intf_a.remote_node.node_id < intf_b.remote_node.node_id: 3218 return -1 3219 if intf_b.remote_node.node_id < intf_a.remote_node.node_id: 3220 return 1 3221 return 0 3223 def Sort_Interfaces(topo): 3224 for node in topo.island_node_list: 3225 node.island_intf_list.sort(Interface_Compare) 3227 def Reset_Computed_Node_and_Intf_Values(topo): 3229 topo.init_new_computing_router() 3230 for node in topo.node_list: 3231 node.init_new_computing_router() 3232 for intf in node.intf_list: 3233 intf.init_new_computing_router() 3235 # This function takes a file with links represented by 2-digit 3236 # numbers in the format: 3237 # 01,05,10 3238 # 05,02,30 3239 # 02,01,15 3240 # which represents a triangle topology with nodes 01, 05, and 02 3241 # and symmetric metrics of 10, 30, and 15. 3243 # Inclusion of a fourth column makes the metrics for the link 3244 # asymmetric. An entry of: 3245 # 02,07,10,15 3246 # creates a link from node 02 to 07 with metrics 10 and 15. 3247 def Create_Topology_From_File(filename): 3248 topo = Topology() 3249 node_id_set= set() 3250 cols_list = [] 3251 # on first pass just create nodes 3252 with open(filename + '.csv') as topo_file: 3253 for line in topo_file: 3254 line = line.rstrip('\r\n') 3255 cols=line.split(',') 3256 cols_list.append(cols) 3257 nodea_node_id = int(cols[0]) 3258 nodeb_node_id = int(cols[1]) 3259 if (nodea_node_id > 999 or nodeb_node_id > 999): 3260 print("node_id must be between 0 and 999.") 3261 print("exiting.") 3262 exit() 3263 node_id_set.add(nodea_node_id) 3264 node_id_set.add(nodeb_node_id) 3265 for node_id in node_id_set: 3266 node = Node() 3267 node.node_id = node_id 3268 topo.node_list.append(node) 3269 topo.node_dict[node_id] = node 3270 # on second pass create interfaces 3271 for cols in cols_list: 3272 nodea_node_id = int(cols[0]) 3273 nodeb_node_id = int(cols[1]) 3274 metric = int(cols[2]) 3275 reverse_metric = int(cols[2]) 3276 if len(cols) > 3: 3278 reverse_metric=int(cols[3]) 3279 nodea = topo.node_dict[nodea_node_id] 3280 nodeb = topo.node_dict[nodeb_node_id] 3281 nodea_intf = Interface() 3282 nodea_intf.metric = metric 3283 nodea_intf.area = 0 3284 nodeb_intf = Interface() 3285 nodeb_intf.metric = reverse_metric 3286 nodeb_intf.area = 0 3287 nodea_intf.remote_intf = nodeb_intf 3288 nodeb_intf.remote_intf = nodea_intf 3289 nodea_intf.remote_node = nodeb 3290 nodeb_intf.remote_node = nodea 3291 nodea_intf.local_node = nodea 3292 nodeb_intf.local_node = nodeb 3293 nodea_intf.link_data = len(nodea.intf_list) 3294 nodeb_intf.link_data = len(nodeb.intf_list) 3295 nodea.intf_list.append(nodea_intf) 3296 nodeb.intf_list.append(nodeb_intf) 3297 return topo 3299 def MRT_Island_Identification(topo, computing_rtr, profile_id, area): 3300 if profile_id in computing_rtr.profile_id_list: 3301 computing_rtr.IN_MRT_ISLAND = True 3302 explore_list = [computing_rtr] 3303 else: 3304 return 3305 while explore_list != []: 3306 next_rtr = explore_list.pop() 3307 for intf in next_rtr.intf_list: 3308 if ( (not intf.MRT_INELIGIBLE) 3309 and (not intf.remote_intf.MRT_INELIGIBLE) 3310 and (not intf.IGP_EXCLUDED) and intf.area == area 3311 and (profile_id in intf.remote_node.profile_id_list)): 3312 intf.IN_MRT_ISLAND = True 3313 intf.remote_intf.IN_MRT_ISLAND = True 3314 if (not intf.remote_node.IN_MRT_ISLAND): 3315 intf.remote_node.IN_MRT_ISLAND = True 3316 explore_list.append(intf.remote_node) 3318 def Compute_Island_Node_List_For_Test_GR(topo, test_gr): 3319 Reset_Computed_Node_and_Intf_Values(topo) 3320 topo.test_gr = topo.node_dict[test_gr] 3321 MRT_Island_Identification(topo, topo.test_gr, 0, 0) 3322 for node in topo.node_list: 3323 if node.IN_MRT_ISLAND: 3324 topo.island_node_list_for_test_gr.append(node) 3326 def Set_Island_Intf_and_Node_Lists(topo): 3327 for node in topo.node_list: 3328 if node.IN_MRT_ISLAND: 3329 topo.island_node_list.append(node) 3330 for intf in node.intf_list: 3331 if intf.IN_MRT_ISLAND: 3332 node.island_intf_list.append(intf) 3334 global_dfs_number = None 3336 def Lowpoint_Visit(x, parent, intf_p_to_x): 3337 global global_dfs_number 3338 x.dfs_number = global_dfs_number 3339 x.lowpoint_number = x.dfs_number 3340 global_dfs_number += 1 3341 x.dfs_parent = parent 3342 if intf_p_to_x == None: 3343 x.dfs_parent_intf = None 3344 else: 3345 x.dfs_parent_intf = intf_p_to_x.remote_intf 3346 x.lowpoint_parent = None 3347 if parent != None: 3348 parent.dfs_child_list.append(x) 3349 for intf in x.island_intf_list: 3350 if intf.remote_node.dfs_number == None: 3351 Lowpoint_Visit(intf.remote_node, x, intf) 3352 if intf.remote_node.lowpoint_number < x.lowpoint_number: 3353 x.lowpoint_number = intf.remote_node.lowpoint_number 3354 x.lowpoint_parent = intf.remote_node 3355 x.lowpoint_parent_intf = intf 3356 else: 3357 if intf.remote_node is not parent: 3358 if intf.remote_node.dfs_number < x.lowpoint_number: 3359 x.lowpoint_number = intf.remote_node.dfs_number 3360 x.lowpoint_parent = intf.remote_node 3361 x.lowpoint_parent_intf = intf 3363 def Run_Lowpoint(topo): 3364 global global_dfs_number 3365 global_dfs_number = 0 3366 Lowpoint_Visit(topo.gadag_root, None, None) 3368 max_block_id = None 3370 def Assign_Block_ID(x, cur_block_id): 3371 global max_block_id 3372 x.block_id = cur_block_id 3373 for c in x.dfs_child_list: 3375 if (c.localroot is x): 3376 max_block_id += 1 3377 Assign_Block_ID(c, max_block_id) 3378 else: 3379 Assign_Block_ID(c, cur_block_id) 3381 def Run_Assign_Block_ID(topo): 3382 global max_block_id 3383 max_block_id = 0 3384 Assign_Block_ID(topo.gadag_root, max_block_id) 3386 def Construct_Ear(x, stack, intf, ear_type): 3387 ear_list = [] 3388 cur_intf = intf 3389 not_done = True 3390 while not_done: 3391 cur_intf.UNDIRECTED = False 3392 cur_intf.OUTGOING = True 3393 cur_intf.remote_intf.UNDIRECTED = False 3394 cur_intf.remote_intf.INCOMING = True 3395 if cur_intf.remote_node.IN_GADAG == False: 3396 cur_intf.remote_node.IN_GADAG = True 3397 ear_list.append(cur_intf.remote_node) 3398 if ear_type == 'CHILD': 3399 cur_intf = cur_intf.remote_node.lowpoint_parent_intf 3400 else: 3401 assert ear_type == 'NEIGHBOR' 3402 cur_intf = cur_intf.remote_node.dfs_parent_intf 3403 else: 3404 not_done = False 3406 if ear_type == 'CHILD' and cur_intf.remote_node is x: 3407 # x is a cut-vertex and the local root for the block 3408 # in which the ear is computed 3409 x.IS_CUT_VERTEX = True 3410 localroot = x 3411 else: 3412 # inherit local root from the end of the ear 3413 localroot = cur_intf.remote_node.localroot 3415 while ear_list != []: 3416 y = ear_list.pop() 3417 y.localroot = localroot 3418 stack.append(y) 3420 def Construct_GADAG_via_Lowpoint(topo): 3421 gadag_root = topo.gadag_root 3422 gadag_root.IN_GADAG = True 3423 gadag_root.localroot = None 3424 stack = [] 3425 stack.append(gadag_root) 3426 while stack != []: 3427 x = stack.pop() 3428 for intf in x.island_intf_list: 3429 if ( intf.remote_node.IN_GADAG == False 3430 and intf.remote_node.dfs_parent is x ): 3431 Construct_Ear(x, stack, intf, 'CHILD' ) 3432 for intf in x.island_intf_list: 3433 if (intf.remote_node.IN_GADAG == False 3434 and intf.remote_node.dfs_parent is not x): 3435 Construct_Ear(x, stack, intf, 'NEIGHBOR') 3437 def Assign_Remaining_Lowpoint_Parents(topo): 3438 for node in topo.island_node_list: 3439 if ( node is not topo.gadag_root 3440 and node.lowpoint_parent == None ): 3441 node.lowpoint_parent = node.dfs_parent 3442 node.lowpoint_parent_intf = node.dfs_parent_intf 3443 node.lowpoint_number = node.dfs_parent.dfs_number 3445 def Add_Undirected_Block_Root_Links(topo): 3446 for node in topo.island_node_list: 3447 if node.IS_CUT_VERTEX or node is topo.gadag_root: 3448 for intf in node.island_intf_list: 3449 if ( intf.remote_node.localroot is not node 3450 or intf.PROCESSED ): 3451 continue 3452 bundle_list = [] 3453 bundle = Bundle() 3454 for intf2 in node.island_intf_list: 3455 if intf2.remote_node is intf.remote_node: 3456 bundle_list.append(intf2) 3457 if not intf2.UNDIRECTED: 3458 bundle.UNDIRECTED = False 3459 if intf2.INCOMING: 3460 bundle.INCOMING = True 3461 if intf2.OUTGOING: 3462 bundle.OUTGOING = True 3463 if bundle.UNDIRECTED: 3464 for intf3 in bundle_list: 3465 intf3.UNDIRECTED = False 3466 intf3.remote_intf.UNDIRECTED = False 3467 intf3.PROCESSED = True 3468 intf3.remote_intf.PROCESSED = True 3469 intf3.OUTGOING = True 3470 intf3.remote_intf.INCOMING = True 3472 else: 3473 if (bundle.OUTGOING and bundle.INCOMING): 3474 for intf3 in bundle_list: 3475 intf3.UNDIRECTED = False 3476 intf3.remote_intf.UNDIRECTED = False 3477 intf3.PROCESSED = True 3478 intf3.remote_intf.PROCESSED = True 3479 intf3.OUTGOING = True 3480 intf3.INCOMING = True 3481 intf3.remote_intf.INCOMING = True 3482 intf3.remote_intf.OUTGOING = True 3483 elif bundle.OUTGOING: 3484 for intf3 in bundle_list: 3485 intf3.UNDIRECTED = False 3486 intf3.remote_intf.UNDIRECTED = False 3487 intf3.PROCESSED = True 3488 intf3.remote_intf.PROCESSED = True 3489 intf3.OUTGOING = True 3490 intf3.remote_intf.INCOMING = True 3491 elif bundle.INCOMING: 3492 for intf3 in bundle_list: 3493 intf3.UNDIRECTED = False 3494 intf3.remote_intf.UNDIRECTED = False 3495 intf3.PROCESSED = True 3496 intf3.remote_intf.PROCESSED = True 3497 intf3.INCOMING = True 3498 intf3.remote_intf.OUTGOING = True 3500 def Modify_Block_Root_Incoming_Links(topo): 3501 for node in topo.island_node_list: 3502 if ( node.IS_CUT_VERTEX == True or node is topo.gadag_root ): 3503 for intf in node.island_intf_list: 3504 if intf.remote_node.localroot is node: 3505 if intf.INCOMING: 3506 intf.INCOMING = False 3507 intf.INCOMING_STORED = True 3508 intf.remote_intf.OUTGOING = False 3509 intf.remote_intf.OUTGOING_STORED = True 3511 def Revert_Block_Root_Incoming_Links(topo): 3512 for node in topo.island_node_list: 3513 if ( node.IS_CUT_VERTEX == True or node is topo.gadag_root ): 3514 for intf in node.island_intf_list: 3515 if intf.remote_node.localroot is node: 3516 if intf.INCOMING_STORED: 3517 intf.INCOMING = True 3518 intf.remote_intf.OUTGOING = True 3519 intf.INCOMING_STORED = False 3520 intf.remote_intf.OUTGOING_STORED = False 3522 def Run_Topological_Sort_GADAG(topo): 3523 Modify_Block_Root_Incoming_Links(topo) 3524 for node in topo.island_node_list: 3525 node.unvisited = 0 3526 for intf in node.island_intf_list: 3527 if (intf.INCOMING == True): 3528 node.unvisited += 1 3529 working_list = [] 3530 topo_order_list = [] 3531 working_list.append(topo.gadag_root) 3532 while working_list != []: 3533 y = working_list.pop(0) 3534 topo_order_list.append(y) 3535 for intf in y.island_intf_list: 3536 if ( intf.OUTGOING == True): 3537 intf.remote_node.unvisited -= 1 3538 if intf.remote_node.unvisited == 0: 3539 working_list.append(intf.remote_node) 3540 next_topo_order = 1 3541 while topo_order_list != []: 3542 y = topo_order_list.pop(0) 3543 y.topo_order = next_topo_order 3544 next_topo_order += 1 3545 Revert_Block_Root_Incoming_Links(topo) 3547 def Set_Other_Undirected_Links_Based_On_Topo_Order(topo): 3548 for node in topo.island_node_list: 3549 for intf in node.island_intf_list: 3550 if intf.UNDIRECTED: 3551 if node.topo_order < intf.remote_node.topo_order: 3552 intf.OUTGOING = True 3553 intf.UNDIRECTED = False 3554 intf.remote_intf.INCOMING = True 3555 intf.remote_intf.UNDIRECTED = False 3556 else: 3557 intf.INCOMING = True 3558 intf.UNDIRECTED = False 3559 intf.remote_intf.OUTGOING = True 3560 intf.remote_intf.UNDIRECTED = False 3562 def Initialize_Temporary_Interface_Flags(topo): 3563 for node in topo.island_node_list: 3564 for intf in node.island_intf_list: 3565 intf.PROCESSED = False 3566 intf.INCOMING_STORED = False 3567 intf.OUTGOING_STORED = False 3569 def Add_Undirected_Links(topo): 3570 Initialize_Temporary_Interface_Flags(topo) 3571 Add_Undirected_Block_Root_Links(topo) 3572 Run_Topological_Sort_GADAG(topo) 3573 Set_Other_Undirected_Links_Based_On_Topo_Order(topo) 3575 def In_Common_Block(x,y): 3576 if ( (x.block_id == y.block_id) 3577 or ( x is y.localroot) or (y is x.localroot) ): 3578 return True 3579 return False 3581 def Copy_List_Items(target_list, source_list): 3582 del target_list[:] # Python idiom to remove all elements of a list 3583 for element in source_list: 3584 target_list.append(element) 3586 def Add_Item_To_List_If_New(target_list, item): 3587 if item not in target_list: 3588 target_list.append(item) 3590 def Store_Results(y, direction): 3591 if direction == 'INCREASING': 3592 y.HIGHER = True 3593 Copy_List_Items(y.blue_next_hops, y.next_hops) 3594 if direction == 'DECREASING': 3595 y.LOWER = True 3596 Copy_List_Items(y.red_next_hops, y.next_hops) 3597 if direction == 'NORMAL_SPF': 3598 y.primary_spf_metric = y.spf_metric 3599 Copy_List_Items(y.primary_next_hops, y.next_hops) 3600 if direction == 'MRT_ISLAND_SPF': 3601 Copy_List_Items(y.mrt_island_next_hops, y.next_hops) 3602 if direction == 'COLLAPSED_SPF': 3603 y.collapsed_metric = y.spf_metric 3604 Copy_List_Items(y.collapsed_next_hops, y.next_hops) 3606 # Note that the Python heapq fucntion allows for duplicate items, 3607 # so we use the 'spf_visited' property to only consider a node 3608 # as min_node the first time it gets removed from the heap. 3609 def SPF_No_Traverse_Block_Root(topo, spf_root, block_root, direction): 3610 spf_heap = [] 3611 for y in topo.island_node_list: 3612 y.spf_metric = 2147483647 # 2^31-1 3613 y.next_hops = [] 3614 y.spf_visited = False 3615 spf_root.spf_metric = 0 3616 heapq.heappush(spf_heap, 3617 (spf_root.spf_metric, spf_root.node_id, spf_root) ) 3618 while spf_heap != []: 3619 #extract third element of tuple popped from heap 3620 min_node = heapq.heappop(spf_heap)[2] 3621 if min_node.spf_visited: 3622 continue 3623 min_node.spf_visited = True 3624 Store_Results(min_node, direction) 3625 if ( (min_node is spf_root) or (min_node is not block_root) ): 3626 for intf in min_node.island_intf_list: 3627 if ( ( (direction == 'INCREASING' and intf.OUTGOING ) 3628 or (direction == 'DECREASING' and intf.INCOMING ) ) 3629 and In_Common_Block(spf_root, intf.remote_node) ) : 3630 path_metric = min_node.spf_metric + intf.metric 3631 if path_metric < intf.remote_node.spf_metric: 3632 intf.remote_node.spf_metric = path_metric 3633 if min_node is spf_root: 3634 intf.remote_node.next_hops = [intf] 3635 else: 3636 Copy_List_Items(intf.remote_node.next_hops, 3637 min_node.next_hops) 3638 heapq.heappush(spf_heap, 3639 ( intf.remote_node.spf_metric, 3640 intf.remote_node.node_id, 3641 intf.remote_node ) ) 3642 elif path_metric == intf.remote_node.spf_metric: 3643 if min_node is spf_root: 3644 Add_Item_To_List_If_New( 3645 intf.remote_node.next_hops,intf) 3646 else: 3647 for nh_intf in min_node.next_hops: 3648 Add_Item_To_List_If_New( 3649 intf.remote_node.next_hops,nh_intf) 3651 def Normal_SPF(topo, spf_root): 3652 spf_heap = [] 3653 for y in topo.node_list: 3654 y.spf_metric = 2147483647 # 2^31-1 as max metric 3655 y.next_hops = [] 3656 y.primary_spf_metric = 2147483647 3657 y.primary_next_hops = [] 3658 y.spf_visited = False 3659 spf_root.spf_metric = 0 3660 heapq.heappush(spf_heap, 3661 (spf_root.spf_metric,spf_root.node_id,spf_root) ) 3662 while spf_heap != []: 3663 #extract third element of tuple popped from heap 3664 min_node = heapq.heappop(spf_heap)[2] 3665 if min_node.spf_visited: 3666 continue 3667 min_node.spf_visited = True 3668 Store_Results(min_node, 'NORMAL_SPF') 3669 for intf in min_node.intf_list: 3670 path_metric = min_node.spf_metric + intf.metric 3671 if path_metric < intf.remote_node.spf_metric: 3672 intf.remote_node.spf_metric = path_metric 3673 if min_node is spf_root: 3674 intf.remote_node.next_hops = [intf] 3675 else: 3676 Copy_List_Items(intf.remote_node.next_hops, 3677 min_node.next_hops) 3678 heapq.heappush(spf_heap, 3679 ( intf.remote_node.spf_metric, 3680 intf.remote_node.node_id, 3681 intf.remote_node ) ) 3682 elif path_metric == intf.remote_node.spf_metric: 3683 if min_node is spf_root: 3684 Add_Item_To_List_If_New( 3685 intf.remote_node.next_hops,intf) 3686 else: 3687 for nh_intf in min_node.next_hops: 3688 Add_Item_To_List_If_New( 3689 intf.remote_node.next_hops,nh_intf) 3691 def Set_Edge(y): 3692 if (y.blue_next_hops == [] and y.red_next_hops == []): 3693 Set_Edge(y.localroot) 3694 Copy_List_Items(y.blue_next_hops,y.localroot.blue_next_hops) 3695 Copy_List_Items(y.red_next_hops ,y.localroot.red_next_hops) 3696 y.order_proxy = y.localroot.order_proxy 3698 def Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,x): 3699 for y in topo.island_node_list: 3700 y.HIGHER = False 3701 y.LOWER = False 3702 y.red_next_hops = [] 3703 y.blue_next_hops = [] 3704 y.order_proxy = y 3705 SPF_No_Traverse_Block_Root(topo, x, x.localroot, 'INCREASING') 3706 SPF_No_Traverse_Block_Root(topo, x, x.localroot, 'DECREASING') 3707 for y in topo.island_node_list: 3708 if ( y is not x and (y.block_id == x.block_id) ): 3709 assert (not ( y is x.localroot or x is y.localroot) ) 3710 assert(not (y.HIGHER and y.LOWER) ) 3711 if y.HIGHER == True: 3712 Copy_List_Items(y.red_next_hops, 3713 x.localroot.red_next_hops) 3714 elif y.LOWER == True: 3715 Copy_List_Items(y.blue_next_hops, 3716 x.localroot.blue_next_hops) 3717 else: 3718 Copy_List_Items(y.blue_next_hops, 3719 x.localroot.red_next_hops) 3720 Copy_List_Items(y.red_next_hops, 3721 x.localroot.blue_next_hops) 3723 # Inherit x's MRT next-hops to reach the GADAG root 3724 # from x's MRT next-hops to reach its local root, 3725 # but first check if x is the gadag_root (in which case 3726 # x does not have a local root) or if x's local root 3727 # is the gadag root (in which case we already have the 3728 # x's MRT next-hops to reach the gadag root) 3729 if x is not topo.gadag_root and x.localroot is not topo.gadag_root: 3730 Copy_List_Items(topo.gadag_root.blue_next_hops, 3731 x.localroot.blue_next_hops) 3732 Copy_List_Items(topo.gadag_root.red_next_hops, 3733 x.localroot.red_next_hops) 3734 topo.gadag_root.order_proxy = x.localroot 3736 # Inherit next-hops and order_proxies to other blocks 3737 for y in topo.island_node_list: 3738 if (y is not topo.gadag_root and y is not x ): 3739 Set_Edge(y) 3741 def Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,x): 3742 for y in topo.island_node_list: 3743 if y is x: 3744 continue 3745 x.blue_next_hops_dict[y.node_id] = [] 3746 x.red_next_hops_dict[y.node_id] = [] 3747 Copy_List_Items(x.blue_next_hops_dict[y.node_id], 3748 y.blue_next_hops) 3749 Copy_List_Items(x.red_next_hops_dict[y.node_id], 3750 y.red_next_hops) 3752 def Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,x): 3753 for y in topo.island_node_list: 3754 x.pnh_dict[y.node_id] = [] 3755 Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops) 3756 x.alt_dict[y.node_id] = [] 3757 Copy_List_Items(x.alt_dict[y.node_id], y.alt_list) 3759 def Store_Primary_NHs_For_One_Source_To_Nodes(topo,x): 3760 for y in topo.node_list: 3762 x.pnh_dict[y.node_id] = [] 3763 Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops) 3765 def Store_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x): 3766 for prefix in topo.named_proxy_dict: 3767 P = topo.named_proxy_dict[prefix] 3768 x.blue_next_hops_dict[P.node_id] = [] 3769 x.red_next_hops_dict[P.node_id] = [] 3770 Copy_List_Items(x.blue_next_hops_dict[P.node_id], 3771 P.blue_next_hops) 3772 Copy_List_Items(x.red_next_hops_dict[P.node_id], 3773 P.red_next_hops) 3775 def Store_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,x): 3776 for prefix in topo.named_proxy_dict: 3777 P = topo.named_proxy_dict[prefix] 3778 x.alt_dict[P.node_id] = [] 3779 Copy_List_Items(x.alt_dict[P.node_id], 3780 P.alt_list) 3782 def Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x): 3783 for prefix in topo.named_proxy_dict: 3784 P = topo.named_proxy_dict[prefix] 3785 x.pnh_dict[P.node_id] = [] 3786 Copy_List_Items(x.pnh_dict[P.node_id], 3787 P.primary_next_hops) 3789 def Select_Alternates_Internal(D, F, primary_intf, 3790 D_lower, D_higher, D_topo_order): 3791 if D_higher and D_lower: 3792 if F.HIGHER and F.LOWER: 3793 if F.topo_order > D_topo_order: 3794 return 'USE_BLUE' 3795 else: 3796 return 'USE_RED' 3797 if F.HIGHER: 3798 return 'USE_RED' 3799 if F.LOWER: 3800 return 'USE_BLUE' 3801 assert(primary_intf.MRT_INELIGIBLE 3802 or primary_intf.remote_intf.MRT_INELIGIBLE) 3803 return 'USE_RED_OR_BLUE' 3804 if D_higher: 3805 if F.HIGHER and F.LOWER: 3806 return 'USE_BLUE' 3807 if F.LOWER: 3808 return 'USE_BLUE' 3809 if F.HIGHER: 3811 if (F.topo_order > D_topo_order): 3812 return 'USE_BLUE' 3813 if (F.topo_order < D_topo_order): 3814 return 'USE_RED' 3815 assert(False) 3816 assert(primary_intf.MRT_INELIGIBLE 3817 or primary_intf.remote_intf.MRT_INELIGIBLE) 3818 return 'USE_RED_OR_BLUE' 3819 if D_lower: 3820 if F.HIGHER and F.LOWER: 3821 return 'USE_RED' 3822 if F.HIGHER: 3823 return 'USE_RED' 3824 if F.LOWER: 3825 if F.topo_order > D_topo_order: 3826 return 'USE_BLUE' 3827 if F.topo_order < D_topo_order: 3828 return 'USE_RED' 3829 assert(False) 3830 assert(primary_intf.MRT_INELIGIBLE 3831 or primary_intf.remote_intf.MRT_INELIGIBLE) 3832 return 'USE_RED_OR_BLUE' 3833 else: # D is unordered wrt S 3834 if F.HIGHER and F.LOWER: 3835 if primary_intf.OUTGOING and primary_intf.INCOMING: 3836 # This can happen when F and D are in different blocks 3837 return 'USE_RED_OR_BLUE' 3838 if primary_intf.OUTGOING: 3839 return 'USE_BLUE' 3840 if primary_intf.INCOMING: 3841 return 'USE_RED' 3842 #This can occur when primary_intf is MRT_INELIGIBLE. 3843 #This appears to be a case where the special 3844 #construction of the GADAG allows us to choose red, 3845 #whereas with an arbitrary GADAG, neither red nor blue 3846 #is guaranteed to work. 3847 assert(primary_intf.MRT_INELIGIBLE 3848 or primary_intf.remote_intf.MRT_INELIGIBLE) 3849 return 'USE_RED' 3850 if F.LOWER: 3851 return 'USE_RED' 3852 if F.HIGHER: 3853 return 'USE_BLUE' 3854 assert(primary_intf.MRT_INELIGIBLE 3855 or primary_intf.remote_intf.MRT_INELIGIBLE) 3856 if F.topo_order > D_topo_order: 3857 return 'USE_BLUE' 3858 else: 3860 return 'USE_RED' 3862 def Select_Alternates(D, F, primary_intf): 3863 S = primary_intf.local_node 3864 if not In_Common_Block(F, S): 3865 return 'PRIM_NH_IN_DIFFERENT_BLOCK' 3866 if (D is F) or (D.order_proxy is F): 3867 return 'PRIM_NH_IS_D_OR_OP_FOR_D' 3868 D_lower = D.order_proxy.LOWER 3869 D_higher = D.order_proxy.HIGHER 3870 D_topo_order = D.order_proxy.topo_order 3871 return Select_Alternates_Internal(D, F, primary_intf, 3872 D_lower, D_higher, D_topo_order) 3874 def Is_Remote_Node_In_NH_List(node, intf_list): 3875 for intf in intf_list: 3876 if node is intf.remote_node: 3877 return True 3878 return False 3880 def Select_Alts_For_One_Src_To_Island_Dests(topo,x): 3881 Normal_SPF(topo, x) 3882 for D in topo.island_node_list: 3883 D.alt_list = [] 3884 if D is x: 3885 continue 3886 for failed_intf in D.primary_next_hops: 3887 alt = Alternate() 3888 alt.failed_intf = failed_intf 3889 cand_alt_list = [] 3890 F = failed_intf.remote_node 3891 #We need to test if F is in the island, as opposed 3892 #to just testing if failed_intf is in island_intf_list, 3893 #because failed_intf could be marked as MRT_INELIGIBLE. 3894 if F in topo.island_node_list: 3895 alt.info = Select_Alternates(D, F, failed_intf) 3896 else: 3897 #The primary next-hop is not in the MRT Island. 3898 #Either red or blue will avoid the primary next-hop, 3899 #because the primary next-hop is not even in the 3900 #GADAG. 3901 alt.info = 'USE_RED_OR_BLUE' 3903 if (alt.info == 'USE_RED_OR_BLUE'): 3904 alt.red_or_blue = random.choice(['USE_RED','USE_BLUE']) 3905 if (alt.info == 'USE_BLUE' 3906 or alt.red_or_blue == 'USE_BLUE'): 3908 Copy_List_Items(alt.nh_list, D.blue_next_hops) 3909 alt.fec = 'BLUE' 3910 alt.prot = 'NODE_PROTECTION' 3911 if (alt.info == 'USE_RED' or alt.red_or_blue == 'USE_RED'): 3912 Copy_List_Items(alt.nh_list, D.red_next_hops) 3913 alt.fec = 'RED' 3914 alt.prot = 'NODE_PROTECTION' 3915 if (alt.info == 'PRIM_NH_IN_DIFFERENT_BLOCK'): 3916 alt.fec = 'NO_ALTERNATE' 3917 alt.prot = 'NO_PROTECTION' 3918 if (alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D'): 3919 if failed_intf.OUTGOING and failed_intf.INCOMING: 3920 # cut-link: if there are parallel cut links, use 3921 # the link(s) with lowest metric that are not 3922 # primary intf or None 3923 cand_alt_list = [None] 3924 min_metric = 2147483647 3925 for intf in x.island_intf_list: 3926 if ( intf is not failed_intf and 3927 (intf.remote_node is 3928 failed_intf.remote_node)): 3929 if intf.metric < min_metric: 3930 cand_alt_list = [intf] 3931 min_metric = intf.metric 3932 elif intf.metric == min_metric: 3933 cand_alt_list.append(intf) 3934 if cand_alt_list != [None]: 3935 alt.fec = 'GREEN' 3936 alt.prot = 'PARALLEL_CUTLINK' 3937 else: 3938 alt.fec = 'NO_ALTERNATE' 3939 alt.prot = 'NO_PROTECTION' 3940 Copy_List_Items(alt.nh_list, cand_alt_list) 3942 # Is_Remote_Node_In_NH_List() is used, as opposed 3943 # to just checking if failed_intf is in D.red_next_hops, 3944 # because failed_intf could be marked as MRT_INELIGIBLE. 3945 elif Is_Remote_Node_In_NH_List(F, D.red_next_hops): 3946 Copy_List_Items(alt.nh_list, D.blue_next_hops) 3947 alt.fec = 'BLUE' 3948 alt.prot = 'LINK_PROTECTION' 3949 elif Is_Remote_Node_In_NH_List(F, D.blue_next_hops): 3950 Copy_List_Items(alt.nh_list, D.red_next_hops) 3951 alt.fec = 'RED' 3952 alt.prot = 'LINK_PROTECTION' 3953 else: 3954 alt.fec = random.choice(['RED','BLUE']) 3955 alt.prot = 'LINK_PROTECTION' 3957 D.alt_list.append(alt) 3959 def Write_GADAG_To_File(topo, file_prefix): 3960 gadag_edge_list = [] 3961 for node in topo.node_list: 3962 for intf in node.intf_list: 3963 if intf.SIMULATION_OUTGOING: 3964 local_node = "%04d" % (intf.local_node.node_id) 3965 remote_node = "%04d" % (intf.remote_node.node_id) 3966 intf_data = "%03d" % (intf.link_data) 3967 edge_string=(local_node+','+remote_node+','+ 3968 intf_data+'\n') 3969 gadag_edge_list.append(edge_string) 3970 gadag_edge_list.sort(); 3971 filename = file_prefix + '_gadag.csv' 3972 with open(filename, 'w') as gadag_file: 3973 gadag_file.write('local_node,'\ 3974 'remote_node,local_intf_link_data\n') 3975 for edge_string in gadag_edge_list: 3976 gadag_file.write(edge_string); 3978 def Write_MRTs_For_All_Dests_To_File(topo, color, file_prefix): 3979 edge_list = [] 3980 for node in topo.island_node_list_for_test_gr: 3981 if color == 'blue': 3982 node_next_hops_dict = node.blue_next_hops_dict 3983 elif color == 'red': 3984 node_next_hops_dict = node.red_next_hops_dict 3985 for dest_node_id in node_next_hops_dict: 3986 for intf in node_next_hops_dict[dest_node_id]: 3987 gadag_root = "%04d" % (topo.gadag_root.node_id) 3988 dest_node = "%04d" % (dest_node_id) 3989 local_node = "%04d" % (intf.local_node.node_id) 3990 remote_node = "%04d" % (intf.remote_node.node_id) 3991 intf_data = "%03d" % (intf.link_data) 3992 edge_string=(gadag_root+','+dest_node+','+local_node+ 3993 ','+remote_node+','+intf_data+'\n') 3994 edge_list.append(edge_string) 3995 edge_list.sort() 3996 filename = file_prefix + '_' + color + '_to_all.csv' 3997 with open(filename, 'w') as mrt_file: 3998 mrt_file.write('gadag_root,dest,'\ 3999 'local_node,remote_node,link_data\n') 4000 for edge_string in edge_list: 4001 mrt_file.write(edge_string); 4003 def Write_Both_MRTs_For_All_Dests_To_File(topo, file_prefix): 4004 Write_MRTs_For_All_Dests_To_File(topo, 'blue', file_prefix) 4005 Write_MRTs_For_All_Dests_To_File(topo, 'red', file_prefix) 4007 def Write_Alternates_For_All_Dests_To_File(topo, file_prefix): 4008 edge_list = [] 4009 for x in topo.island_node_list_for_test_gr: 4010 for dest_node_id in x.alt_dict: 4011 alt_list = x.alt_dict[dest_node_id] 4012 for alt in alt_list: 4013 for alt_intf in alt.nh_list: 4014 gadag_root = "%04d" % (topo.gadag_root.node_id) 4015 dest_node = "%04d" % (dest_node_id) 4016 prim_local_node = \ 4017 "%04d" % (alt.failed_intf.local_node.node_id) 4018 prim_remote_node = \ 4019 "%04d" % (alt.failed_intf.remote_node.node_id) 4020 prim_intf_data = \ 4021 "%03d" % (alt.failed_intf.link_data) 4022 if alt_intf == None: 4023 alt_local_node = "None" 4024 alt_remote_node = "None" 4025 alt_intf_data = "None" 4026 else: 4027 alt_local_node = \ 4028 "%04d" % (alt_intf.local_node.node_id) 4029 alt_remote_node = \ 4030 "%04d" % (alt_intf.remote_node.node_id) 4031 alt_intf_data = \ 4032 "%03d" % (alt_intf.link_data) 4033 edge_string = (gadag_root+','+dest_node+','+ 4034 prim_local_node+','+prim_remote_node+','+ 4035 prim_intf_data+','+alt_local_node+','+ 4036 alt_remote_node+','+alt_intf_data+','+ 4037 alt.fec +'\n') 4038 edge_list.append(edge_string) 4039 edge_list.sort() 4040 filename = file_prefix + '_alts_to_all.csv' 4041 with open(filename, 'w') as alt_file: 4042 alt_file.write('gadag_root,dest,'\ 4043 'prim_nh.local_node,prim_nh.remote_node,'\ 4044 'prim_nh.link_data,alt_nh.local_node,'\ 4045 'alt_nh.remote_node,alt_nh.link_data,'\ 4046 'alt_nh.fec\n') 4047 for edge_string in edge_list: 4048 alt_file.write(edge_string); 4050 def Raise_GADAG_Root_Selection_Priority(topo,node_id): 4051 node = topo.node_dict[node_id] 4052 node.GR_sel_priority = 255 4054 def Lower_GADAG_Root_Selection_Priority(topo,node_id): 4055 node = topo.node_dict[node_id] 4056 node.GR_sel_priority = 128 4058 def GADAG_Root_Compare(node_a, node_b): 4059 if (node_a.GR_sel_priority > node_b.GR_sel_priority): 4060 return 1 4061 elif (node_a.GR_sel_priority < node_b.GR_sel_priority): 4062 return -1 4063 else: 4064 if node_a.node_id > node_b.node_id: 4065 return 1 4066 elif node_a.node_id < node_b.node_id: 4067 return -1 4069 def Set_GADAG_Root(topo,computing_router): 4070 gadag_root_list = [] 4071 for node in topo.island_node_list: 4072 gadag_root_list.append(node) 4073 gadag_root_list.sort(GADAG_Root_Compare) 4074 topo.gadag_root = gadag_root_list.pop() 4076 def Add_Prefix_Advertisements_From_File(topo, filename): 4077 prefix_filename = filename + '.prefix' 4078 cols_list = [] 4079 if not os.path.exists(prefix_filename): 4080 return 4081 with open(prefix_filename) as prefix_file: 4082 for line in prefix_file: 4083 line = line.rstrip('\r\n') 4084 cols=line.split(',') 4085 cols_list.append(cols) 4086 prefix_id = int(cols[0]) 4087 if prefix_id < 2000 or prefix_id >2999: 4088 print('skipping the following line of prefix file') 4089 print('prefix id should be between 2000 and 2999') 4090 print(line) 4091 continue 4092 prefix_node_id = int(cols[1]) 4093 prefix_cost = int(cols[2]) 4094 advertising_node = topo.node_dict[prefix_node_id] 4095 advertising_node.prefix_cost_dict[prefix_id] = prefix_cost 4097 def Add_Prefixes_for_Non_Island_Nodes(topo): 4098 for node in topo.node_list: 4099 if node.IN_MRT_ISLAND: 4100 continue 4101 prefix_id = node.node_id + 1000 4102 node.prefix_cost_dict[prefix_id] = 0 4104 def Add_Profile_IDs_from_File(topo, filename): 4105 profile_filename = filename + '.profile' 4106 for node in topo.node_list: 4107 node.profile_id_list = [] 4108 cols_list = [] 4109 if os.path.exists(profile_filename): 4110 with open(profile_filename) as profile_file: 4111 for line in profile_file: 4112 line = line.rstrip('\r\n') 4113 cols=line.split(',') 4114 cols_list.append(cols) 4115 node_id = int(cols[0]) 4116 profile_id = int(cols[1]) 4117 this_node = topo.node_dict[node_id] 4118 this_node.profile_id_list.append(profile_id) 4119 else: 4120 for node in topo.node_list: 4121 node.profile_id_list = [0] 4123 def Island_Marking_SPF(topo,spf_root): 4124 spf_root.isl_marking_spf_dict = {} 4125 for y in topo.node_list: 4126 y.spf_metric = 2147483647 # 2^31-1 as max metric 4127 y.PATH_HITS_ISLAND = False 4128 y.next_hops = [] 4129 y.spf_visited = False 4130 spf_root.spf_metric = 0 4131 spf_heap = [] 4132 heapq.heappush(spf_heap, 4133 (spf_root.spf_metric,spf_root.node_id,spf_root) ) 4134 while spf_heap != []: 4135 #extract third element of tuple popped from heap 4136 min_node = heapq.heappop(spf_heap)[2] 4137 if min_node.spf_visited: 4138 continue 4139 min_node.spf_visited = True 4140 spf_root.isl_marking_spf_dict[min_node.node_id] = \ 4141 (min_node.spf_metric, min_node.PATH_HITS_ISLAND) 4142 for intf in min_node.intf_list: 4143 path_metric = min_node.spf_metric + intf.metric 4144 if path_metric < intf.remote_node.spf_metric: 4145 intf.remote_node.spf_metric = path_metric 4146 if min_node is spf_root: 4147 intf.remote_node.next_hops = [intf] 4148 else: 4149 Copy_List_Items(intf.remote_node.next_hops, 4150 min_node.next_hops) 4151 if (intf.remote_node.IN_MRT_ISLAND): 4152 intf.remote_node.PATH_HITS_ISLAND = True 4153 else: 4154 intf.remote_node.PATH_HITS_ISLAND = \ 4155 min_node.PATH_HITS_ISLAND 4156 heapq.heappush(spf_heap, 4157 ( intf.remote_node.spf_metric, 4158 intf.remote_node.node_id, 4159 intf.remote_node ) ) 4160 elif path_metric == intf.remote_node.spf_metric: 4161 if min_node is spf_root: 4162 Add_Item_To_List_If_New( 4163 intf.remote_node.next_hops,intf) 4164 else: 4165 for nh_intf in min_node.next_hops: 4166 Add_Item_To_List_If_New( 4167 intf.remote_node.next_hops,nh_intf) 4168 if (intf.remote_node.IN_MRT_ISLAND): 4169 intf.remote_node.PATH_HITS_ISLAND = True 4170 else: 4171 if (intf.remote_node.PATH_HITS_ISLAND 4172 or min_node.PATH_HITS_ISLAND): 4173 intf.remote_node.PATH_HITS_ISLAND = True 4175 def Create_Basic_Named_Proxy_Nodes(topo): 4176 for node in topo.node_list: 4177 for prefix in node.prefix_cost_dict: 4178 prefix_cost = node.prefix_cost_dict[prefix] 4179 if prefix in topo.named_proxy_dict: 4180 P = topo.named_proxy_dict[prefix] 4181 P.node_prefix_cost_list.append((node,prefix_cost)) 4182 else: 4183 P = Named_Proxy_Node() 4184 topo.named_proxy_dict[prefix] = P 4185 P.node_id = prefix 4186 P.node_prefix_cost_list = [(node,prefix_cost)] 4188 def Compute_Loop_Free_Island_Neighbors_For_Each_Prefix(topo): 4189 topo.island_nbr_set = set() 4190 topo.island_border_set = set() 4191 for node in topo.node_list: 4192 if node.IN_MRT_ISLAND: 4193 continue 4194 for intf in node.intf_list: 4195 if intf.remote_node.IN_MRT_ISLAND: 4196 topo.island_nbr_set.add(node) 4197 topo.island_border_set.add(intf.remote_node) 4199 for island_nbr in topo.island_nbr_set: 4200 Island_Marking_SPF(topo,island_nbr) 4202 for prefix in topo.named_proxy_dict: 4203 P = topo.named_proxy_dict[prefix] 4204 P.lfin_list = [] 4205 for island_nbr in topo.island_nbr_set: 4206 min_isl_nbr_to_pref_cost = 2147483647 4207 for (adv_node, prefix_cost) in P.node_prefix_cost_list: 4208 (adv_node_cost, path_hits_island) = \ 4209 island_nbr.isl_marking_spf_dict[adv_node.node_id] 4210 isl_nbr_to_pref_cost = adv_node_cost + prefix_cost 4211 if isl_nbr_to_pref_cost < min_isl_nbr_to_pref_cost: 4212 min_isl_nbr_to_pref_cost = isl_nbr_to_pref_cost 4213 min_path_hits_island = path_hits_island 4214 elif isl_nbr_to_pref_cost == min_isl_nbr_to_pref_cost: 4215 if min_path_hits_island or path_hits_island: 4216 min_path_hits_island = True 4217 if not min_path_hits_island: 4218 P.lfin_list.append( (island_nbr, 4219 min_isl_nbr_to_pref_cost) ) 4221 def Compute_Island_Border_Router_LFIN_Pairs_For_Each_Prefix(topo): 4222 for ibr in topo.island_border_set: 4223 ibr.prefix_lfin_dict = {} 4224 ibr.min_intf_metric_dict = {} 4225 ibr.min_intf_list_dict = {} 4226 ibr.min_intf_list_dict[None] = None 4227 for intf in ibr.intf_list: 4228 if not intf.remote_node in topo.island_nbr_set: 4229 continue 4230 if not intf.remote_node in ibr.min_intf_metric_dict: 4231 ibr.min_intf_metric_dict[intf.remote_node] = \ 4232 intf.metric 4233 ibr.min_intf_list_dict[intf.remote_node] = [intf] 4234 else: 4235 if (intf.metric 4236 < ibr.min_intf_metric_dict[intf.remote_node]): 4237 ibr.min_intf_metric_dict[intf.remote_node] = \ 4238 intf.metric 4239 ibr.min_intf_list_dict[intf.remote_node] = [intf] 4240 elif (intf.metric 4241 < ibr.min_intf_metric_dict[intf.remote_node]): 4242 ibr.min_intf_list_dict[intf.remote_node].\ 4243 append(intf) 4245 for prefix in topo.named_proxy_dict: 4246 P = topo.named_proxy_dict[prefix] 4247 for ibr in topo.island_border_set: 4248 min_ibr_lfin_pref_cost = 2147483647 4249 min_lfin = None 4250 for (lfin, lfin_to_pref_cost) in P.lfin_list: 4251 if not lfin in ibr.min_intf_metric_dict: 4252 continue 4253 ibr_lfin_pref_cost = \ 4254 ibr.min_intf_metric_dict[lfin] + lfin_to_pref_cost 4255 if ibr_lfin_pref_cost < min_ibr_lfin_pref_cost: 4256 min_ibr_lfin_pref_cost = ibr_lfin_pref_cost 4257 min_lfin = lfin 4258 ibr.prefix_lfin_dict[prefix] = (min_lfin, 4259 min_ibr_lfin_pref_cost, 4260 ibr.min_intf_list_dict[min_lfin]) 4262 def Proxy_Node_Att_Router_Compare(pnar_a, pnar_b): 4263 if pnar_a.named_proxy_cost < pnar_b.named_proxy_cost: 4264 return -1 4265 if pnar_b.named_proxy_cost < pnar_a.named_proxy_cost: 4266 return 1 4267 if pnar_a.node.node_id < pnar_b.node.node_id: 4268 return -1 4269 if pnar_b.node.node_id < pnar_a.node.node_id: 4270 return 1 4271 if pnar_a.min_lfin == None: 4272 return -1 4273 if pnar_b.min_lfin == None: 4274 return 1 4276 def Choose_Proxy_Node_Attachment_Routers(topo): 4277 for prefix in topo.named_proxy_dict: 4278 P = topo.named_proxy_dict[prefix] 4279 pnar_candidate_list = [] 4280 for (node, prefix_cost) in P.node_prefix_cost_list: 4281 if not node.IN_MRT_ISLAND: 4282 continue 4283 pnar = Proxy_Node_Attachment_Router() 4284 pnar.prefix = prefix 4285 pnar.named_proxy_cost = prefix_cost 4286 pnar.node = node 4287 pnar_candidate_list.append(pnar) 4288 for ibr in topo.island_border_set: 4289 (min_lfin, prefix_cost, min_intf_list) = \ 4290 ibr.prefix_lfin_dict[prefix] 4291 if min_lfin == None: 4292 continue 4294 pnar = Proxy_Node_Attachment_Router() 4295 pnar.named_proxy_cost = prefix_cost 4296 pnar.node = ibr 4297 pnar.min_lfin = min_lfin 4298 pnar.nh_intf_list = min_intf_list 4299 pnar_candidate_list.append(pnar) 4300 pnar_candidate_list.sort(cmp=Proxy_Node_Att_Router_Compare) 4301 #pop first element from list 4302 first_pnar = pnar_candidate_list.pop(0) 4303 second_pnar = None 4304 for next_pnar in pnar_candidate_list: 4305 if next_pnar.node is first_pnar.node: 4306 continue 4307 second_pnar = next_pnar 4308 break 4310 P.pnar1 = first_pnar 4311 P.pnar2 = second_pnar 4313 def Attach_Named_Proxy_Nodes(topo): 4314 Compute_Loop_Free_Island_Neighbors_For_Each_Prefix(topo) 4315 Compute_Island_Border_Router_LFIN_Pairs_For_Each_Prefix(topo) 4316 Choose_Proxy_Node_Attachment_Routers(topo) 4318 def Select_Proxy_Node_NHs(P,S): 4319 if P.pnar1.node.node_id < P.pnar2.node.node_id: 4320 X = P.pnar1.node 4321 Y = P.pnar2.node 4322 else: 4323 X = P.pnar2.node 4324 Y = P.pnar1.node 4325 P.pnar_X = X 4326 P.pnar_Y = Y 4327 A = X.order_proxy 4328 B = Y.order_proxy 4329 if (A is S.localroot 4330 and B is S.localroot): 4331 #print("1.0") 4332 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4333 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4334 return 4335 if (A is S.localroot 4336 and B is not S.localroot): 4337 #print("2.0") 4338 if B.LOWER: 4339 #print("2.1") 4340 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4341 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4342 return 4343 if B.HIGHER: 4344 #print("2.2") 4345 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4346 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4347 return 4348 else: 4349 #print("2.3") 4350 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4351 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4352 return 4353 if (A is not S.localroot 4354 and B is S.localroot): 4355 #print("3.0") 4356 if A.LOWER: 4357 #print("3.1") 4358 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4359 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4360 return 4361 if A.HIGHER: 4362 #print("3.2") 4363 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4364 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4365 return 4366 else: 4367 #print("3.3") 4368 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4369 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4370 return 4371 if (A is not S.localroot 4372 and B is not S.localroot): 4373 #print("4.0") 4374 if (S is A.localroot or S is B.localroot): 4375 #print("4.05") 4376 if A.topo_order < B.topo_order: 4377 #print("4.05.1") 4378 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4379 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4380 return 4381 else: 4382 #print("4.05.2") 4383 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4384 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4385 return 4386 if A.LOWER: 4387 #print("4.1") 4388 if B.HIGHER: 4389 #print("4.1.1") 4390 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4391 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4392 return 4393 if B.LOWER: 4394 #print("4.1.2") 4395 if A.topo_order < B.topo_order: 4396 #print("4.1.2.1") 4397 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4398 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4399 return 4400 else: 4401 #print("4.1.2.2") 4402 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4403 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4404 return 4405 else: 4406 #print("4.1.3") 4407 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4408 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4409 return 4410 if A.HIGHER: 4411 #print("4.2") 4412 if B.HIGHER: 4413 #print("4.2.1") 4414 if A.topo_order < B.topo_order: 4415 #print("4.2.1.1") 4416 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4417 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4418 return 4419 else: 4420 #print("4.2.1.2") 4421 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4422 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4423 return 4424 if B.LOWER: 4425 #print("4.2.2") 4426 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4427 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4428 return 4429 else: 4430 #print("4.2.3") 4431 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4432 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4433 return 4434 else: 4435 #print("4.3") 4436 if B.LOWER: 4437 #print("4.3.1") 4438 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4439 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4440 return 4441 if B.HIGHER: 4442 #print("4.3.2") 4443 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4444 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4445 return 4446 else: 4447 #print("4.3.3") 4448 if A.topo_order < B.topo_order: 4449 #print("4.3.3.1") 4450 Copy_List_Items(P.blue_next_hops, X.blue_next_hops) 4451 Copy_List_Items(P.red_next_hops, Y.red_next_hops) 4452 return 4453 else: 4454 #print("4.3.3.2") 4455 Copy_List_Items(P.blue_next_hops, X.red_next_hops) 4456 Copy_List_Items(P.red_next_hops, Y.blue_next_hops) 4457 return 4458 assert(False) 4460 def Compute_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,S): 4461 for prefix in topo.named_proxy_dict: 4462 P = topo.named_proxy_dict[prefix] 4463 if P.pnar2 == None: 4464 if S is P.pnar1.node: 4465 # set the MRT next-hops for the PNAR to 4466 # reach the LFIN and change FEC to green 4467 Copy_List_Items(P.blue_next_hops, 4468 P.pnar1.nh_intf_list) 4469 S.blue_to_green_nh_dict[P.node_id] = True 4470 Copy_List_Items(P.red_next_hops, 4471 P.pnar1.nh_intf_list) 4472 S.red_to_green_nh_dict[P.node_id] = True 4473 else: 4474 # inherit MRT NHs for P from pnar1 4475 Copy_List_Items(P.blue_next_hops, 4476 P.pnar1.node.blue_next_hops) 4477 Copy_List_Items(P.red_next_hops, 4478 P.pnar1.node.red_next_hops) 4479 else: 4480 Select_Proxy_Node_NHs(P,S) 4481 # set the MRT next-hops for the PNAR to reach the LFIN 4482 # and change FEC to green rely on the red or blue 4483 # next-hops being empty to figure out which one needs 4484 # to point to the LFIN. 4485 if S is P.pnar1.node: 4487 this_pnar = P.pnar1 4488 elif S is P.pnar2.node: 4489 this_pnar = P.pnar2 4490 else: 4491 continue 4492 if P.blue_next_hops == []: 4493 Copy_List_Items(P.blue_next_hops, 4494 this_pnar.nh_intf_list) 4495 S.blue_to_green_nh_dict[P.node_id] = True 4496 if P.red_next_hops == []: 4497 Copy_List_Items(P.red_next_hops, 4498 this_pnar.nh_intf_list) 4499 S.red_to_green_nh_dict[P.node_id] = True 4501 def Select_Alternates_Proxy_Node(P,F,primary_intf): 4502 S = primary_intf.local_node 4503 X = P.pnar_X 4504 Y = P.pnar_Y 4505 A = X.order_proxy 4506 B = Y.order_proxy 4507 if F is A and F is B: 4508 return 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y' 4509 if F is A: 4510 return 'USE_RED' 4511 if F is B: 4512 return 'USE_BLUE' 4514 if not In_Common_Block(A, B): 4515 if In_Common_Block(F, A): 4516 return 'USE_RED' 4517 elif In_Common_Block(F, B): 4518 return 'USE_BLUE' 4519 else: 4520 return 'USE_RED_OR_BLUE' 4521 if (not In_Common_Block(F, A) 4522 and not In_Common_Block(F, A) ): 4523 return 'USE_RED_OR_BLUE' 4525 alt_to_X = Select_Alternates(X, F, primary_intf) 4526 alt_to_Y = Select_Alternates(Y, F, primary_intf) 4528 if (alt_to_X == 'USE_RED_OR_BLUE' 4529 and alt_to_Y == 'USE_RED_OR_BLUE'): 4530 return 'USE_RED_OR_BLUE' 4531 if alt_to_X == 'USE_RED_OR_BLUE': 4532 return 'USE_BLUE' 4533 if alt_to_Y == 'USE_RED_OR_BLUE': 4534 return 'USE_RED' 4536 if (A is S.localroot 4537 and B is S.localroot): 4538 #print("1.0") 4539 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 4540 return 'USE_RED_OR_BLUE' 4541 if alt_to_X == 'USE_BLUE': 4542 return 'USE_BLUE' 4543 if alt_to_Y == 'USE_RED': 4544 return 'USE_RED' 4545 assert(False) 4546 if (A is S.localroot 4547 and B is not S.localroot): 4548 #print("2.0") 4549 if B.LOWER: 4550 #print("2.1") 4551 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 4552 return 'USE_RED_OR_BLUE' 4553 if alt_to_X == 'USE_BLUE': 4554 return 'USE_BLUE' 4555 if alt_to_Y == 'USE_RED': 4556 return 'USE_RED' 4557 assert(False) 4558 if B.HIGHER: 4559 #print("2.2") 4560 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 4561 return 'USE_RED_OR_BLUE' 4562 if alt_to_X == 'USE_RED': 4563 return 'USE_BLUE' 4564 if alt_to_Y == 'USE_BLUE': 4565 return 'USE_RED' 4566 assert(False) 4567 else: 4568 #print("2.3") 4569 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'): 4570 return 'USE_RED_OR_BLUE' 4571 if alt_to_X == 'USE_RED': 4572 return 'USE_BLUE' 4573 if alt_to_Y == 'USE_RED': 4574 return 'USE_RED' 4575 assert(False) 4576 if (A is not S.localroot 4577 and B is S.localroot): 4578 #print("3.0") 4579 if A.LOWER: 4580 #print("3.1") 4581 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 4582 return 'USE_RED_OR_BLUE' 4583 if alt_to_X == 'USE_RED': 4585 return 'USE_BLUE' 4586 if alt_to_Y == 'USE_BLUE': 4587 return 'USE_RED' 4588 assert(False) 4589 if A.HIGHER: 4590 #print("3.2") 4591 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 4592 return 'USE_RED_OR_BLUE' 4593 if alt_to_X == 'USE_BLUE': 4594 return 'USE_BLUE' 4595 if alt_to_Y == 'USE_RED': 4596 return 'USE_RED' 4597 assert(False) 4598 else: 4599 #print("3.3") 4600 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'): 4601 return 'USE_RED_OR_BLUE' 4602 if alt_to_X == 'USE_RED': 4603 return 'USE_BLUE' 4604 if alt_to_Y == 'USE_RED': 4605 return 'USE_RED' 4606 assert(False) 4607 if (A is not S.localroot 4608 and B is not S.localroot): 4609 #print("4.0") 4610 if (S is A.localroot or S is B.localroot): 4611 #print("4.05") 4612 if A.topo_order < B.topo_order: 4613 #print("4.05.1") 4614 if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): 4615 return 'USE_RED_OR_BLUE' 4616 if alt_to_X == 'USE_BLUE': 4617 return 'USE_BLUE' 4618 if alt_to_Y == 'USE_RED': 4619 return 'USE_RED' 4620 assert(False) 4621 else: 4622 #print("4.05.2") 4623 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 4624 return 'USE_RED_OR_BLUE' 4625 if alt_to_X == 'USE_RED': 4626 return 'USE_BLUE' 4627 if alt_to_Y == 'USE_BLUE': 4628 return 'USE_RED' 4629 assert(False) 4630 if A.LOWER: 4631 #print("4.1") 4632 if B.HIGHER: 4634 #print("4.1.1") 4635 if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): 4636 return 'USE_RED_OR_BLUE' 4637 if alt_to_X == 'USE_RED': 4638 return 'USE_BLUE' 4639 if alt_to_Y == 'USE_BLUE': 4640 return 'USE_RED' 4641 assert(False) 4642 if B.LOWER: 4643 #print("4.1.2") 4644 if A.topo_order < B.topo_order: 4645 #print("4.1.2.1") 4646 if (alt_to_X == 'USE_BLUE' 4647 and alt_to_Y == 'USE_RED'): 4648 return 'USE_RED_OR_BLUE' 4649 if alt_to_X == 'USE_BLUE': 4650 return 'USE_BLUE' 4651 if alt_to_Y == 'USE_RED': 4652 return 'USE_RED' 4653 assert(False) 4654 else: 4655 #print("4.1.2.2") 4656 if (alt_to_X == 'USE_RED' 4657 and alt_to_Y == 'USE_BLUE'): 4658 return 'USE_RED_OR_BLUE' 4659 if alt_to_X == 'USE_RED': 4660 return 'USE_BLUE' 4661 if alt_to_Y == 'USE_BLUE': 4662 return 'USE_RED' 4663 assert(False) 4664 else: 4665 #print("4.1.3") 4666 if (F.LOWER and not F.HIGHER 4667 and F.topo_order > A.topo_order): 4668 #print("4.1.3.1") 4669 return 'USE_RED' 4670 else: 4671 #print("4.1.3.2") 4672 return 'USE_BLUE' 4673 if A.HIGHER: 4674 #print("4.2") 4675 if B.HIGHER: 4676 #print("4.2.1") 4677 if A.topo_order < B.topo_order: 4678 #print("4.2.1.1") 4679 if (alt_to_X == 'USE_BLUE' 4680 and alt_to_Y == 'USE_RED'): 4681 return 'USE_RED_OR_BLUE' 4683 if alt_to_X == 'USE_BLUE': 4684 return 'USE_BLUE' 4685 if alt_to_Y == 'USE_RED': 4686 return 'USE_RED' 4687 assert(False) 4688 else: 4689 #print("4.2.1.2") 4690 if (alt_to_X == 'USE_RED' 4691 and alt_to_Y == 'USE_BLUE'): 4692 return 'USE_RED_OR_BLUE' 4693 if alt_to_X == 'USE_RED': 4694 return 'USE_BLUE' 4695 if alt_to_Y == 'USE_BLUE': 4696 return 'USE_RED' 4697 assert(False) 4698 if B.LOWER: 4699 #print("4.2.2") 4700 if (alt_to_X == 'USE_BLUE' 4701 and alt_to_Y == 'USE_RED'): 4702 return 'USE_RED_OR_BLUE' 4703 if alt_to_X == 'USE_BLUE': 4704 return 'USE_BLUE' 4705 if alt_to_Y == 'USE_RED': 4706 return 'USE_RED' 4707 assert(False) 4708 else: 4709 #print("4.2.3") 4710 if (F.HIGHER and not F.LOWER 4711 and F.topo_order < A.topo_order): 4712 return 'USE_RED' 4713 else: 4714 return 'USE_BLUE' 4715 else: 4716 #print("4.3") 4717 if B.LOWER: 4718 #print("4.3.1") 4719 if (F.LOWER and not F.HIGHER 4720 and F.topo_order > B.topo_order): 4721 return 'USE_BLUE' 4722 else: 4723 return 'USE_RED' 4724 if B.HIGHER: 4725 #print("4.3.2") 4726 if (F.HIGHER and not F.LOWER 4727 and F.topo_order < B.topo_order): 4728 return 'USE_BLUE' 4729 else: 4730 return 'USE_RED' 4732 else: 4733 #print("4.3.3") 4734 if A.topo_order < B.topo_order: 4735 #print("4.3.3.1") 4736 if (alt_to_X == 'USE_BLUE' 4737 and alt_to_Y == 'USE_RED'): 4738 return 'USE_RED_OR_BLUE' 4739 if alt_to_X == 'USE_BLUE': 4740 return 'USE_BLUE' 4741 if alt_to_Y == 'USE_RED': 4742 return 'USE_RED' 4743 assert(False) 4744 else: 4745 #print("4.3.3.2") 4746 if (alt_to_X == 'USE_RED' 4747 and alt_to_Y == 'USE_BLUE'): 4748 return 'USE_RED_OR_BLUE' 4749 if alt_to_X == 'USE_RED': 4750 return 'USE_BLUE' 4751 if alt_to_Y == 'USE_BLUE': 4752 return 'USE_RED' 4753 assert(False) 4754 assert(False) 4756 def Compute_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src): 4757 for prefix in topo.named_proxy_dict: 4758 P = topo.named_proxy_dict[prefix] 4759 min_total_pref_cost = 2147483647 4760 for (adv_node, prefix_cost) in P.node_prefix_cost_list: 4761 total_pref_cost = (adv_node.primary_spf_metric 4762 + prefix_cost) 4763 if total_pref_cost < min_total_pref_cost: 4764 min_total_pref_cost = total_pref_cost 4765 Copy_List_Items(P.primary_next_hops, 4766 adv_node.primary_next_hops) 4767 elif total_pref_cost == min_total_pref_cost: 4768 for nh_intf in adv_node.primary_next_hops: 4769 Add_Item_To_List_If_New(P.primary_next_hops, 4770 nh_intf) 4772 def Select_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,src): 4773 for prefix in topo.named_proxy_dict: 4774 P = topo.named_proxy_dict[prefix] 4775 P.alt_list = [] 4776 for failed_intf in P.primary_next_hops: 4777 alt = Alternate() 4778 alt.failed_intf = failed_intf 4779 if failed_intf not in src.island_intf_list: 4781 alt.info = 'PRIM_NH_FOR_PROXY_NODE_NOT_IN_ISLAND' 4782 elif P.pnar1 is None: 4783 alt.info = 'NO_PNARs_EXIST_FOR_THIS_PREFIX' 4784 elif src is P.pnar1.node: 4785 alt.info = 'SRC_IS_PNAR' 4786 elif P.pnar2 is not None and src is P.pnar2.node: 4787 alt.info = 'SRC_IS_PNAR' 4788 elif P.pnar2 is None: 4789 #inherit alternates from the only pnar. 4790 alt.info = Select_Alternates(P.pnar1.node, 4791 failed_intf.remote_node, failed_intf) 4792 elif failed_intf in src.island_intf_list: 4793 alt.info = Select_Alternates_Proxy_Node(P, 4794 failed_intf.remote_node, failed_intf) 4796 if alt.info == 'USE_RED_OR_BLUE': 4797 alt.red_or_blue = \ 4798 random.choice(['USE_RED','USE_BLUE']) 4799 if (alt.info == 'USE_BLUE' 4800 or alt.red_or_blue == 'USE_BLUE'): 4801 Copy_List_Items(alt.nh_list, P.blue_next_hops) 4802 alt.fec = 'BLUE' 4803 alt.prot = 'NODE_PROTECTION' 4804 elif (alt.info == 'USE_RED' 4805 or alt.red_or_blue == 'USE_RED'): 4806 Copy_List_Items(alt.nh_list, P.red_next_hops) 4807 alt.fec = 'RED' 4808 alt.prot = 'NODE_PROTECTION' 4809 elif (alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D' 4810 or alt.info == 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y'): 4811 if failed_intf.OUTGOING and failed_intf.INCOMING: 4812 # cut-link: if there are parallel cut links, use 4813 # the link(s) with lowest metric that are not 4814 # primary intf or None 4815 cand_alt_list = [None] 4816 min_metric = 2147483647 4817 for intf in src.island_intf_list: 4818 if ( intf is not failed_intf and 4819 (intf.remote_node is 4820 failed_intf.remote_node)): 4821 if intf.metric < min_metric: 4822 cand_alt_list = [intf] 4823 min_metric = intf.metric 4824 elif intf.metric == min_metric: 4825 cand_alt_list.append(intf) 4826 if cand_alt_list != [None]: 4827 alt.fec = 'GREEN' 4828 alt.prot = 'PARALLEL_CUTLINK' 4830 else: 4831 alt.fec = 'NO_ALTERNATE' 4832 alt.prot = 'NO_PROTECTION' 4833 Copy_List_Items(alt.nh_list, cand_alt_list) 4834 else: 4835 # set Z as the node to inherit blue next-hops from 4836 if alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D': 4837 Z = P.pnar1.node 4838 else: 4839 Z = P 4840 if failed_intf in Z.red_next_hops: 4841 Copy_List_Items(alt.nh_list, Z.blue_next_hops) 4842 alt.fec = 'BLUE' 4843 alt.prot = 'LINK_PROTECTION' 4844 else: 4845 assert(failed_intf in Z.blue_next_hops) 4846 Copy_List_Items(alt.nh_list, Z.red_next_hops) 4847 alt.fec = 'RED' 4848 alt.prot = 'LINK_PROTECTION' 4850 elif alt.info == 'PRIM_NH_FOR_PROXY_NODE_NOT_IN_ISLAND': 4851 if (P.pnar2 == None and src is P.pnar1.node): 4852 #MRT Island is singly connected to non-island dest 4853 alt.fec = 'NO_ALTERNATE' 4854 alt.prot = 'NO_PROTECTION' 4855 elif P.node_id in src.blue_to_green_nh_dict: 4856 # blue to P goes to failed LFIN so use red to P 4857 Copy_List_Items(alt.nh_list, P.red_next_hops) 4858 alt.fec = 'RED' 4859 alt.prot = 'LINK_PROTECTION' 4860 elif P.node_id in src.red_to_green_nh_dict: 4861 # red to P goes to failed LFIN so use blue to P 4862 Copy_List_Items(alt.nh_list, P.blue_next_hops) 4863 alt.fec = 'BLUE' 4864 alt.prot = 'LINK_PROTECTION' 4865 else: 4866 Copy_List_Items(alt.nh_list, P.blue_next_hops) 4867 alt.fec = 'BLUE' 4868 alt.prot = 'LINK_PROTECTION' 4869 elif alt.info == 'TEMP_NO_ALTERNATE': 4870 alt.fec = 'NO_ALTERNATE' 4871 alt.prot = 'NO_PROTECTION' 4873 P.alt_list.append(alt) 4875 def Run_Basic_MRT_for_One_Source(topo, src): 4876 MRT_Island_Identification(topo, src, 0, 0) 4877 Set_Island_Intf_and_Node_Lists(topo) 4878 Set_GADAG_Root(topo,src) 4879 Sort_Interfaces(topo) 4880 Run_Lowpoint(topo) 4881 Assign_Remaining_Lowpoint_Parents(topo) 4882 Construct_GADAG_via_Lowpoint(topo) 4883 Run_Assign_Block_ID(topo) 4884 Add_Undirected_Links(topo) 4885 Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,src) 4886 Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,src) 4887 Select_Alts_For_One_Src_To_Island_Dests(topo,src) 4888 Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,src) 4890 def Store_GADAG_and_Named_Proxies_Once(topo): 4891 for node in topo.node_list: 4892 for intf in node.intf_list: 4893 if intf.OUTGOING: 4894 intf.SIMULATION_OUTGOING = True 4895 else: 4896 intf.SIMULATION_OUTGOING = False 4897 for prefix in topo.named_proxy_dict: 4898 P = topo.named_proxy_dict[prefix] 4899 topo.stored_named_proxy_dict[prefix] = P 4901 def Run_Basic_MRT_for_All_Sources(topo): 4902 for src in topo.node_list: 4903 Reset_Computed_Node_and_Intf_Values(topo) 4904 Run_Basic_MRT_for_One_Source(topo,src) 4905 if src is topo.gadag_root: 4906 Store_GADAG_and_Named_Proxies_Once(topo) 4908 def Run_MRT_for_One_Source(topo, src): 4909 MRT_Island_Identification(topo, src, 0, 0) 4910 Set_Island_Intf_and_Node_Lists(topo) 4911 Set_GADAG_Root(topo,src) 4912 Sort_Interfaces(topo) 4913 Run_Lowpoint(topo) 4914 Assign_Remaining_Lowpoint_Parents(topo) 4915 Construct_GADAG_via_Lowpoint(topo) 4916 Run_Assign_Block_ID(topo) 4917 Add_Undirected_Links(topo) 4918 Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,src) 4919 Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,src) 4920 Select_Alts_For_One_Src_To_Island_Dests(topo,src) 4921 Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,src) 4922 Create_Basic_Named_Proxy_Nodes(topo) 4923 Attach_Named_Proxy_Nodes(topo) 4924 Compute_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4925 Store_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4926 Compute_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4927 Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4928 Select_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4929 Store_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4931 def Run_Prim_SPF_for_One_Source(topo,src): 4932 Normal_SPF(topo, src) 4933 Store_Primary_NHs_For_One_Source_To_Nodes(topo,src) 4934 Create_Basic_Named_Proxy_Nodes(topo) 4935 Compute_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4936 Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src) 4938 def Run_MRT_for_All_Sources(topo): 4939 for src in topo.node_list: 4940 Reset_Computed_Node_and_Intf_Values(topo) 4941 if src in topo.island_node_list_for_test_gr: 4942 # src runs MRT if it is in same MRT island as test_gr 4943 Run_MRT_for_One_Source(topo,src) 4944 if src is topo.gadag_root: 4945 Store_GADAG_and_Named_Proxies_Once(topo) 4946 else: 4947 # src still runs SPF if not in MRT island 4948 Run_Prim_SPF_for_One_Source(topo,src) 4950 def Write_Output_To_Files(topo,file_prefix): 4951 Write_GADAG_To_File(topo,file_prefix) 4952 Write_Both_MRTs_For_All_Dests_To_File(topo,file_prefix) 4953 Write_Alternates_For_All_Dests_To_File(topo,file_prefix) 4955 def Create_Basic_Topology_Input_File(filename): 4956 data = [[01,02,10],[02,03,10],[03,04,11],[04,05,10,20],[05,06,10], 4957 [06,07,10],[06,07,10],[06,07,15],[07,01,10],[07,51,10], 4958 [51,52,10],[52,53,10],[53,03,10],[01,55,10],[55,06,10], 4959 [04,12,10],[12,13,10],[13,14,10],[14,15,10],[15,16,10], 4960 [16,17,10],[17,04,10],[05,76,10],[76,77,10],[77,78,10], 4961 [78,79,10],[79,77,10]] 4962 with open(filename + '.csv', 'w') as topo_file: 4963 for item in data: 4964 if len(item) > 3: 4965 line = (str(item[0])+','+str(item[1])+','+ 4966 str(item[2])+','+str(item[3])+'\n') 4967 else: 4968 line = (str(item[0])+','+str(item[1])+','+ 4969 str(item[2])+'\n') 4970 topo_file.write(line) 4972 def Create_Complex_Topology_Input_File(filename): 4973 data = [[01,02,10],[02,03,10],[03,04,11],[04,05,10,20],[05,06,10], 4975 [06,07,10],[06,07,10],[06,07,15],[07,01,10],[07,51,10], 4976 [51,52,10],[52,53,10],[53,03,10],[01,55,10],[55,06,10], 4977 [04,12,10],[12,13,10],[13,14,10],[14,15,10],[15,16,10], 4978 [16,17,10],[17,04,10],[05,76,10],[76,77,10],[77,78,10], 4979 [78,79,10],[79,77,10]] 4980 with open(filename + '.csv', 'w') as topo_file: 4981 for item in data: 4982 if len(item) > 3: 4983 line = (str(item[0])+','+str(item[1])+','+ 4984 str(item[2])+','+str(item[3])+'\n') 4985 else: 4986 line = (str(item[0])+','+str(item[1])+','+ 4987 str(item[2])+'\n') 4988 topo_file.write(line) 4990 data = [[01,0],[02,0],[03,0],[04,0],[05,0], 4991 [06,0],[07,0], 4992 [51,0],[55,0], 4993 [12,0],[13,0],[14,0],[15,0], 4994 [16,0],[17,0],[76,0],[77,0], 4995 [78,0],[79,0]] 4996 with open(filename + '.profile', 'w') as topo_file: 4997 for item in data: 4998 line = (str(item[0])+','+str(item[1])+'\n') 4999 topo_file.write(line) 5001 data = [[2001,05,100],[2001,07,120],[2001,03,130], 5002 [2002,13,100],[2002,15,110], 5003 [2003,52,100],[2003,78,100]] 5004 with open(filename + '.prefix', 'w') as topo_file: 5005 for item in data: 5006 line = (str(item[0])+','+str(item[1])+','+ 5007 str(item[2])+'\n') 5008 topo_file.write(line) 5010 def Generate_Basic_Topology_and_Run_MRT(): 5011 this_gadag_root = 3 5012 Create_Basic_Topology_Input_File('basic_topo_input') 5013 topo = Create_Topology_From_File('basic_topo_input') 5014 res_file_base = 'basic_topo' 5015 Compute_Island_Node_List_For_Test_GR(topo, this_gadag_root) 5016 Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root) 5017 Run_Basic_MRT_for_All_Sources(topo) 5018 Write_Output_To_Files(topo, res_file_base) 5020 def Generate_Complex_Topology_and_Run_MRT(): 5021 this_gadag_root = 3 5022 Create_Complex_Topology_Input_File('complex_topo_input') 5023 topo = Create_Topology_From_File('complex_topo_input') 5024 Add_Profile_IDs_from_File(topo,'complex_topo_input') 5025 Add_Prefix_Advertisements_From_File(topo,'complex_topo_input') 5026 Compute_Island_Node_List_For_Test_GR(topo, this_gadag_root) 5027 Add_Prefixes_for_Non_Island_Nodes(topo) 5028 res_file_base = 'complex_topo' 5029 Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root) 5030 Run_MRT_for_All_Sources(topo) 5031 Write_Output_To_Files(topo, res_file_base) 5033 Generate_Basic_Topology_and_Run_MRT() 5035 Generate_Complex_Topology_and_Run_MRT() 5037 5039 Appendix B. Constructing a GADAG using SPFs 5041 The basic idea in this method for constructing a GADAG is to use 5042 slightly-modified SPF computations to find ears. In every block, an 5043 SPF computation is first done to find a cycle from the local root and 5044 then SPF computations in that block find ears until there are no more 5045 interfaces to be explored. The used result from the SPF computation 5046 is the path of interfaces indicated by following the previous hops 5047 from the mininized IN_GADAG node back to the SPF root. 5049 To do this, first all cut-vertices must be identified and local-roots 5050 assigned as specified in Figure 12. 5052 The slight modifications to the SPF are as follows. The root of the 5053 block is referred to as the block-root; it is either the GADAG root 5054 or a cut-vertex. 5056 a. The SPF is rooted at a neighbor x of an IN_GADAG node y. All 5057 links between y and x are marked as TEMP_UNUSABLE. They should 5058 not be used during the SPF computation. 5060 b. If y is not the block-root, then it is marked TEMP_UNUSABLE. It 5061 should not be used during the SPF computation. This prevents 5062 ears from starting and ending at the same node and avoids cycles; 5063 the exception is because cycles to/from the block-root are 5064 acceptable and expected. 5066 c. Do not explore links to nodes whose local-root is not the block- 5067 root. This keeps the SPF confined to the particular block. 5069 d. Terminate when the first IN_GADAG node z is minimized. 5071 e. Respect the existing directions (e.g. INCOMING, OUTGOING, 5072 UNDIRECTED) already specified for each interface. 5074 Mod_SPF(spf_root, block_root) 5075 Initialize spf_heap to empty 5076 Initialize nodes' spf_metric to infinity 5077 spf_root.spf_metric = 0 5078 insert(spf_heap, spf_root) 5079 found_in_gadag = false 5080 while (spf_heap is not empty) and (found_in_gadag is false) 5081 min_node = remove_lowest(spf_heap) 5082 if min_node.IN_GADAG 5083 found_in_gadag = true 5084 else 5085 foreach interface intf of min_node 5086 if ((intf.OUTGOING or intf.UNDIRECTED) and 5087 ((intf.remote_node.localroot is block_root) or 5088 (intf.remote_node is block_root)) and 5089 (intf.remote_node is not TEMP_UNUSABLE) and 5090 (intf is not TEMP_UNUSABLE)) 5091 path_metric = min_node.spf_metric + intf.metric 5092 if path_metric < intf.remote_node.spf_metric 5093 intf.remote_node.spf_metric = path_metric 5094 intf.remote_node.spf_prev_intf = intf 5095 insert_or_update(spf_heap, intf.remote_node) 5096 return min_node 5098 SPF_for_Ear(cand_intf.local_node,cand_intf.remote_node, block_root, 5099 method) 5100 Mark all interfaces between cand_intf.remote_node 5101 and cand_intf.local_node as TEMP_UNUSABLE 5102 if cand_intf.local_node is not block_root 5103 Mark cand_intf.local_node as TEMP_UNUSABLE 5104 Initialize ear_list to empty 5105 end_ear = Mod_SPF(spf_root, block_root) 5106 y = end_ear.spf_prev_hop 5107 while y.local_node is not spf_root 5108 add_to_list_start(ear_list, y) 5109 y.local_node.IN_GADAG = true 5110 y = y.local_node.spf_prev_intf 5111 if(method is not hybrid) 5112 Set_Ear_Direction(ear_list, cand_intf.local_node, 5113 end_ear,block_root) 5114 Clear TEMP_UNUSABLE from all interfaces between 5115 cand_intf.remote_node and cand_intf.local_node 5117 Clear TEMP_UNUSABLE from cand_intf.local_node 5118 return end_ear 5120 Figure 31: Modified SPF for GADAG construction 5122 Assume that an ear is found by going from y to x and then running an 5123 SPF that terminates by minimizing z (e.g. y<->x...q<->z). Now it is 5124 necessary to determine the direction of the ear; if y << z, then the 5125 path should be y->x...q->z but if y >> z, then the path should be y<- 5126 x...q<-z. In Section 5.5, the same problem was handled by finding 5127 all ears that started at a node before looking at ears starting at 5128 nodes higher in the partial order. In this GADAG construction 5129 method, using that approach could mean that new ears aren't added in 5130 order of their total cost since all ears connected to a node would 5131 need to be found before additional nodes could be found. 5133 The alternative is to track the order relationship of each node with 5134 respect to every other node. This can be accomplished by maintaining 5135 two sets of nodes at each node. The first set, Higher_Nodes, 5136 contains all nodes that are known to be ordered above the node. The 5137 second set, Lower_Nodes, contains all nodes that are known to be 5138 ordered below the node. This is the approach used in this GADAG 5139 construction method. 5141 Set_Ear_Direction(ear_list, end_a, end_b, block_root) 5142 // Default of A_TO_B for the following cases: 5143 // (a) end_a and end_b are the same (root) 5144 // or (b) end_a is in end_b's Lower Nodes 5145 // or (c) end_a and end_b were unordered with respect to each 5146 // other 5147 direction = A_TO_B 5148 if (end_b is block_root) and (end_a is not end_b) 5149 direction = B_TO_A 5150 else if end_a is in end_b.Higher_Nodes 5151 direction = B_TO_A 5152 if direction is B_TO_A 5153 foreach interface i in ear_list 5154 i.UNDIRECTED = false 5155 i.INCOMING = true 5156 i.remote_intf.UNDIRECTED = false 5157 i.remote_intf.OUTGOING = true 5158 else 5159 foreach interface i in ear_list 5160 i.UNDIRECTED = false 5161 i.OUTGOING = true 5162 i.remote_intf.UNDIRECTED = false 5163 i.remote_intf.INCOMING = true 5164 if end_a is end_b 5165 return 5166 // Next, update all nodes' Lower_Nodes and Higher_Nodes 5167 if (end_a is in end_b.Higher_Nodes) 5168 foreach node x where x.localroot is block_root 5169 if end_a is in x.Lower_Nodes 5170 foreach interface i in ear_list 5171 add i.remote_node to x.Lower_Nodes 5172 if end_b is in x.Higher_Nodes 5173 foreach interface i in ear_list 5174 add i.local_node to x.Higher_Nodes 5175 else 5176 foreach node x where x.localroot is block_root 5177 if end_b is in x.Lower_Nodes 5178 foreach interface i in ear_list 5179 add i.local_node to x.Lower_Nodes 5180 if end_a is in x.Higher_Nodes 5181 foreach interface i in ear_list 5182 add i.remote_node to x.Higher_Nodes 5184 Figure 32: Algorithm to assign links of an ear direction 5186 A goal of this GADAG construction method is to find the shortest 5187 cycles and ears. An ear is started by going to a neighbor x of an 5188 IN_GADAG node y. The path from x to an IN_GADAG node is minimal, 5189 since it is computed via SPF. Since a shortest path is made of 5190 shortest paths, to find the shortest ears requires reaching from the 5191 set of IN_GADAG nodes to the closest node that isn't IN_GADAG. 5192 Therefore, an ordered tree is maintained of interfaces that could be 5193 explored from the IN_GADAG nodes. The interfaces are ordered by 5194 their characteristics of metric, local loopback address, remote 5195 loopback address, and ifindex, based on the Interface_Compare 5196 function defined in Figure 14. 5198 This GADAG construction method ignores interfaces picked from the 5199 ordered list that belong to the block root if the block in which the 5200 interface is present already has an ear that has been computed. This 5201 is necessary since we allow at most one incoming interface to a block 5202 root in each block. This requirement stems from the way next-hops 5203 are computed as was seen in Section 5.7. After any ear gets 5204 computed, we traverse the newly added nodes to the GADAG and insert 5205 interfaces whose far end is not yet on the GADAG to the ordered tree 5206 for later processing. 5208 Finally, cut-links are a special case because there is no point in 5209 doing an SPF on a block of 2 nodes. The algorithm identifies cut- 5210 links simply as links where both ends of the link are cut-vertices. 5211 Cut-links can simply be added to the GADAG with both OUTGOING and 5212 INCOMING specified on their interfaces. 5214 add_eligible_interfaces_of_node(ordered_intfs_tree,node) 5215 for each interface of node 5216 if intf.remote_node.IN_GADAG is false 5217 insert(intf,ordered_intfs_tree) 5219 check_if_block_has_ear(x,block_id) 5220 block_has_ear = false 5221 for all interfaces of x 5222 if ( (intf.remote_node.block_id == block_id) && 5223 intf.remote_node.IN_GADAG ) 5224 block_has_ear = true 5225 return block_has_ear 5227 Construct_GADAG_via_SPF(topology, root) 5228 Compute_Localroot (root,root) 5229 Assign_Block_ID(root,0) 5230 root.IN_GADAG = true 5231 add_eligible_interfaces_of_node(ordered_intfs_tree,root) 5232 while ordered_intfs_tree is not empty 5233 cand_intf = remove_lowest(ordered_intfs_tree) 5234 if cand_intf.remote_node.IN_GADAG is false 5235 if L(cand_intf.remote_node) == D(cand_intf.remote_node) 5236 // Special case for cut-links 5237 cand_intf.UNDIRECTED = false 5238 cand_intf.remote_intf.UNDIRECTED = false 5239 cand_intf.OUTGOING = true 5240 cand_intf.INCOMING = true 5241 cand_intf.remote_intf.OUTGOING = true 5242 cand_intf.remote_intf.INCOMING = true 5243 cand_intf.remote_node.IN_GADAG = true 5244 add_eligible_interfaces_of_node( 5245 ordered_intfs_tree,cand_intf.remote_node) 5246 else 5247 if (cand_intf.remote_node.local_root == 5248 cand_intf.local_node) && 5249 check_if_block_has_ear(cand_intf.local_node, 5250 cand_intf.remote_node.block_id)) 5251 /* Skip the interface since the block root 5252 already has an incoming interface in the 5253 block */ 5254 else 5255 ear_end = SPF_for_Ear(cand_intf.local_node, 5256 cand_intf.remote_node, 5257 cand_intf.remote_node.localroot, 5258 SPF method) 5259 y = ear_end.spf_prev_hop 5260 while y.local_node is not cand_intf.local_node 5261 add_eligible_interfaces_of_node( 5262 ordered_intfs_tree, y.local_node) 5263 y = y.local_node.spf_prev_intf 5265 Figure 33: SPF-based method for GADAG construction 5267 Appendix C. Constructing a GADAG using a hybrid method 5269 The idea of this method is to combine the salient features of the 5270 lowpoint inheritance and SPF methods. To this end, we process nodes 5271 as they get added to the GADAG just like in the lowpoint inheritance 5272 by maintaining a stack of nodes. This ensures that we do not need to 5273 maintain lower and higher sets at each node to ascertain ear 5274 directions since the ears will always be directed from the node being 5275 processed towards the end of the ear. To compute the ear however, we 5276 resort to an SPF to have the possibility of better ears (path 5277 lentghs) thus giving more flexibility than the restricted use of 5278 lowpoint/dfs parents. 5280 Regarding ears involving a block root, unlike the SPF method which 5281 ignored interfaces of the block root after the first ear, in the 5282 hybrid method we would have to process all interfaces of the block 5283 root before moving on to other nodes in the block since the direction 5284 of an ear is pre-determined. Thus, whenever the block already has an 5285 ear computed, and we are processing an interface of the block root, 5286 we mark the block root as unusable before the SPF run that computes 5287 the ear. This ensures that the SPF terminates at some node other 5288 than the block-root. This in turn guarantees that the block-root has 5289 only one incoming interface in each block, which is necessary for 5290 correctly computing the next-hops on the GADAG. 5292 As in the SPF gadag, bridge ears are handled as a special case. 5294 The entire algorithm is shown below in Figure 34 5296 find_spf_stack_ear(stack, x, y, xy_intf, block_root) 5297 if L(y) == D(y) 5298 // Special case for cut-links 5299 xy_intf.UNDIRECTED = false 5300 xy_intf.remote_intf.UNDIRECTED = false 5301 xy_intf.OUTGOING = true 5302 xy_intf.INCOMING = true 5303 xy_intf.remote_intf.OUTGOING = true 5304 xy_intf.remote_intf.INCOMING = true 5305 xy_intf.remote_node.IN_GADAG = true 5306 push y onto stack 5307 return 5308 else 5309 if (y.local_root == x) && 5310 check_if_block_has_ear(x,y.block_id) 5311 //Avoid the block root during the SPF 5312 Mark x as TEMP_UNUSABLE 5313 end_ear = SPF_for_Ear(x,y,block_root,hybrid) 5314 If x was set as TEMP_UNUSABLE, clear it 5315 cur = end_ear 5316 while (cur != y) 5317 intf = cur.spf_prev_hop 5318 prev = intf.local_node 5319 intf.UNDIRECTED = false 5320 intf.remote_intf.UNDIRECTED = false 5321 intf.OUTGOING = true 5322 intf.remote_intf.INCOMING = true 5323 push prev onto stack 5324 cur = prev 5325 xy_intf.UNDIRECTED = false 5326 xy_intf.remote_intf.UNDIRECTED = false 5327 xy_intf.OUTGOING = true 5328 xy_intf.remote_intf.INCOMING = true 5329 return 5331 Construct_GADAG_via_hybrid(topology,root) 5332 Compute_Localroot (root,root) 5333 Assign_Block_ID(root,0) 5334 root.IN_GADAG = true 5335 Initialize Stack to empty 5336 push root onto Stack 5337 while (Stack is not empty) 5338 x = pop(Stack) 5339 for each interface intf of x 5340 y = intf.remote_node 5341 if y.IN_GADAG is false 5342 find_spf_stack_ear(stack, x, y, intf, y.block_root) 5344 Figure 34: Hybrid GADAG construction method 5346 Authors' Addresses 5348 Gabor Sandor Enyedi 5349 Ericsson 5350 Konyves Kalman krt 11 5351 Budapest 1097 5352 Hungary 5354 Email: Gabor.Sandor.Enyedi@ericsson.com 5356 Andras Csaszar 5357 Ericsson 5358 Konyves Kalman krt 11 5359 Budapest 1097 5360 Hungary 5362 Email: Andras.Csaszar@ericsson.com 5364 Alia Atlas 5365 Juniper Networks 5366 10 Technology Park Drive 5367 Westford, MA 01886 5368 USA 5370 Email: akatlas@juniper.net 5371 Chris Bowers 5372 Juniper Networks 5373 1194 N. Mathilda Ave. 5374 Sunnyvale, CA 94089 5375 USA 5377 Email: cbowers@juniper.net 5379 Abishek Gopalan 5380 University of Arizona 5381 1230 E Speedway Blvd. 5382 Tucson, AZ 85721 5383 USA 5385 Email: abishek@ece.arizona.edu