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