idnits 2.17.1 draft-enyedi-rtgwg-mrt-frr-algorithm-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The abstract seems to contain references ([I-D.ietf-rtgwg-mrt-frr-architecture]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. == There are 19 instances of lines with non-RFC2606-compliant FQDNs in the document. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 761: '...in computation, all routers MUST order...' RFC 2119 keyword, line 1589: '...node attachments MUST be determined. ...' RFC 2119 keyword, line 1687: '...e in the graph. An implementation MAY...' RFC 2119 keyword, line 1694: '...omputing router, MUST be one or more n...' RFC 2119 keyword, line 1696: '...RT-Red next-hops MUST be have a topo_o...' (1 more instance...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 21, 2013) is 3833 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: Informational ---------------------------------------------------------------------------- == Missing Reference: 'R' is mentioned on line 1557, but not defined == Missing Reference: 'F' is mentioned on line 618, but not defined == Missing Reference: 'C' is mentioned on line 1557, but not defined == Missing Reference: 'G' is mentioned on line 1557, but not defined == Missing Reference: 'E' is mentioned on line 298, but not defined == Missing Reference: 'D' is mentioned on line 618, but not defined == Missing Reference: 'J' is mentioned on line 166, but not defined == Missing Reference: 'A' is mentioned on line 298, but not defined == Missing Reference: 'B' is mentioned on line 172, but not defined == Missing Reference: 'H' is mentioned on line 1141, but not defined == Missing Reference: 'K' is mentioned on line 618, but not defined == Missing Reference: 'N' is mentioned on line 618, but not defined == Missing Reference: 'X' is mentioned on line 1141, but not defined == Missing Reference: 'Y' is mentioned on line 1141, but not defined == Missing Reference: 'R-small' is mentioned on line 1099, but not defined == Missing Reference: 'R-great' is mentioned on line 1116, but not defined == Missing Reference: 'I' is mentioned on line 1557, but not defined == Unused Reference: 'I-D.ietf-rtgwg-ipfrr-notvia-addresses' is defined on line 2191, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-rtgwg-remote-lfa' is defined on line 2203, but no explicit reference was found in the text == Unused Reference: 'LFARevisited' is defined on line 2213, but no explicit reference was found in the text == Unused Reference: 'LightweightNotVia' is defined on line 2219, but no explicit reference was found in the text == Unused Reference: 'RFC5286' is defined on line 2236, but no explicit reference was found in the text == Unused Reference: 'RFC5714' is defined on line 2239, but no explicit reference was found in the text == Unused Reference: 'RFC6571' is defined on line 2242, but no explicit reference was found in the text == Outdated reference: A later version (-10) exists of draft-ietf-rtgwg-mrt-frr-architecture-03 == Outdated reference: A later version (-03) exists of draft-atlas-ospf-mrt-00 == Outdated reference: A later version (-11) exists of draft-ietf-rtgwg-lfa-manageability-00 == Outdated reference: A later version (-11) exists of draft-ietf-rtgwg-remote-lfa-02 -- Obsolete informational reference (is this intentional?): RFC 3137 (Obsoleted by RFC 6987) Summary: 2 errors (**), 0 flaws (~~), 30 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Routing Area Working Group G. Enyedi, Ed. 3 Internet-Draft A. Csaszar 4 Intended status: Informational Ericsson 5 Expires: April 24, 2014 A. Atlas, Ed. 6 C. Bowers 7 Juniper Networks 8 A. Gopalan 9 University of Arizona 10 October 21, 2013 12 Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- 13 Reroute 14 draft-enyedi-rtgwg-mrt-frr-algorithm-04 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 24, 2014. 42 Copyright Notice 44 Copyright (c) 2013 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. Terminology and Definitions . . . . . . . . . . . . . . . . . 4 61 3. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 6 62 3.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 6 63 3.2. Finding an Ear and the Correct Direction . . . . . . . . 8 64 3.3. Low-Point Values and Their Uses . . . . . . . . . . . . . 11 65 3.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 13 66 3.5. Determining Local-Root and Assigning Block-ID . . . . . . 15 67 4. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 16 68 4.1. MRT Island Identification . . . . . . . . . . . . . . . . 17 69 4.2. Root Selection . . . . . . . . . . . . . . . . . . . . . 18 70 4.3. Initialization . . . . . . . . . . . . . . . . . . . . . 18 71 4.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint 72 inheritance . . . . . . . . . . . . . . . . . . . . . . . 19 73 4.5. Augmenting the GADAG by directing all links . . . . . . . 21 74 4.6. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 23 75 4.6.1. MRT next-hops to all nodes partially ordered with 76 respect to the computing node . . . . . . . . . . . . 24 77 4.6.2. MRT next-hops to all nodes not partially ordered with 78 respect to the computing node . . . . . . . . . . . . 24 79 4.6.3. Computing Redundant Tree next-hops in a 2-connected 80 Graph . . . . . . . . . . . . . . . . . . . . . . . . 25 81 4.6.4. Generalizing for graph that isn't 2-connected . . . . 27 82 4.6.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 28 83 4.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 30 84 4.8. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 34 85 5. MRT Lowpoint Algorithm: Complete Specification . . . . . . . 36 86 6. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 37 87 6.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 37 88 7. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 47 89 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 47 90 9. Security Considerations . . . . . . . . . . . . . . . . . . . 47 91 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 47 92 10.1. Normative References . . . . . . . . . . . . . . . . . . 47 93 10.2. Informative References . . . . . . . . . . . . . . . . . 47 94 Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 49 95 Appendix B. Option 3: Computing GADAG using a hybrid method . . 53 96 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 55 98 1. Introduction 100 MRT Fast-Reroute requires that packets can be forwarded not only on 101 the shortest-path tree, but also on two Maximally Redundant Trees 102 (MRTs), referred to as the MRT-Blue and the MRT-Red. A router which 103 experiences a local failure must also have pre-determined which 104 alternate to use. This document defines how to compute these three 105 things for use in MRT-FRR and describes the algorithm design 106 decisions and rationale. The algorithm is based on those presented 107 in [MRTLinear] and expanded in [EnyediThesis]. 109 Just as packets routed on a hop-by-hop basis require that each router 110 compute a shortest-path tree which is consistent, it is necessary for 111 each router to compute the MRT-Blue next-hops and MRT-Red next-hops 112 in a consistent fashion. This document defines the MRT Lowpoint 113 algorithm to be used as a standard in the default MRT profile for 114 MRT-FRR. 116 As now, a router's FIB will contain primary next-hops for the current 117 shortest-path tree for forwarding traffic. In addition, a router's 118 FIB will contain primary next-hops for the MRT-Blue for forwarding 119 received traffic on the MRT-Blue and primary next-hops for the MRT- 120 Red for forwarding received traffic on the MRT-Red. 122 What alternate next-hops a point-of-local-repair (PLR) selects need 123 not be consistent - but loops must be prevented. To reduce 124 congestion, it is possible for multiple alternate next-hops to be 125 selected; in the context of MRT alternates, each of those alternate 126 next-hops would be equal-cost paths. 128 This document defines an algorithm for selecting an appropriate MRT 129 alternate for consideration. Other alternates, e.g. LFAs that are 130 downstream paths, may be prefered when available and that policy- 131 based alternate selection process[I-D.ietf-rtgwg-lfa-manageability] 132 is not captured in this document. 134 [E]---[D]---| [E]<--[D]<--| [E]-->[D] 135 | | | | ^ | | 136 | | | V | | V 137 [R] [F] [C] [R] [F] [C] [R] [F] [C] 138 | | | ^ ^ | | 139 | | | | | V | 140 [A]---[B]---| [A]-->[B] [A]---[B]<--| 142 (a) (b) (c) 143 a 2-connected graph MRT-Blue towards R MRT-Red towards R 145 Figure 1 147 Algorithms for computing MRTs can handle arbitrary network topologies 148 where the whole network graph is not 2-connected, as in Figure 2, as 149 well as the easier case where the network graph is 2-connected 150 (Figure 1). Each MRT is a spanning tree. The pair of MRTs provide 151 two paths from every node X to the root of the MRTs. Those paths 152 share the minimum number of nodes and the minimum number of links. 153 Each such shared node is a cut-vertex. Any shared links are cut- 154 links. 156 [E]---[D]---| |---[J] 157 | | | | | 158 | | | | | 159 [R] [F] [C]---[G] | 160 | | | | | 161 | | | | | 162 [A]---[B]---| |---[H] 164 (a) a graph that isn't 2-connected 166 [E]<--[D]<--| [J] [E]-->[D]---| |---[J] 167 | ^ | | | | | ^ 168 V | | | V V V | 169 [R] [F] [C]<--[G] | [R] [F] [C]<--[G] | 170 ^ ^ ^ | ^ | | | 171 | | | V | V | | 172 [A]-->[B]---| |---[H] [A]<--[B]<--| [H] 174 (b) MRT-Blue towards R (c) MRT-Red towards R 176 Figure 2 178 2. Terminology and Definitions 180 network graph: A graph that reflects the network topology where all 181 links connect exactly two nodes and broadcast links have been 182 transformed into the standard pseudo-node representation. 184 Redundant Trees (RT): A pair of trees where the path from any node X 185 to the root R on the first tree is node-disjoint with the path 186 from the same node X to the root along the second tree. These can 187 be computed in 2-connected graphs. 189 Maximally Redundant Trees (MRT): A pair of trees where the path 190 from any node X to the root R along the first tree and the path 191 from the same node X to the root along the second tree share the 192 minimum number of nodes and the minimum number of links. Each 193 such shared node is a cut-vertex. Any shared links are cut-links. 194 Any RT is an MRT but many MRTs are not RTs. 196 MRT-Red: MRT-Red is used to describe one of the two MRTs; it is 197 used to described the associated forwarding topology and MT-ID. 198 Specifically, MRT-Red is the decreasing MRT where links in the 199 GADAG are taken in the direction from a higher topologically 200 ordered node to a lower one. 202 MRT-Blue: MRT-Blue is used to describe one of the two MRTs; it is 203 used to described the associated forwarding topology and MT-ID. 204 Specifically, MRT-Blue is the increasing MRT where links in the 205 GADAG are taken in the direction from a lower topologically 206 ordered node to a higher one. 208 cut-vertex: A vertex whose removal partitions the network. 210 cut-link: A link whose removal partitions the network. A cut-link 211 by definition must be connected between two cut-vertices. If 212 there are multiple parallel links, then they are referred to as 213 cut-links in this document if removing the set of parallel links 214 would partition the network. 216 2-connected: A graph that has no cut-vertices. This is a graph 217 that requires two nodes to be removed before the network is 218 partitioned. 220 spanning tree: A tree containing links that connects all nodes in 221 the network graph. 223 back-edge: In the context of a spanning tree computed via a depth- 224 first search, a back-edge is a link that connects a descendant of 225 a node x with an ancestor of x. 227 2-connected cluster: A maximal set of nodes that are 2-connected. 228 In a network graph with at least one cut-vertex, there will be 229 multiple 2-connected clusters. 231 block: Either a 2-connected cluster, a cut-edge, or an isolated 232 vertex. 234 DAG: Directed Acyclic Graph - a digraph containing no directed 235 cycle. 237 ADAG: Almost Directed Acyclic Graph - a digraph that can be 238 transformed into a DAG whith removing a single node (the root 239 node). 241 GADAG: Generalized ADAG - a digraph, which has only ADAGs as all of 242 its blocks. The root of such a block is the node closest to the 243 global root (e.g. with uniform link costs). 245 DFS: Depth-First Search 247 DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS- 248 tree path from the DFS root to x. 250 DFS descendant: A node n is a DFS descendant of x if x is on the 251 DFS-tree path from the DFS root to n. 253 ear: A path along not-yet-included-in-the-GADAG nodes that starts 254 at a node that is already-included-in-the-GADAG and that ends at a 255 node that is already-included-in-the-GADAG. The starting and 256 ending nodes may be the same node if it is a cut-vertex. 258 X >> Y or Y << X: Indicates the relationship between X and Y in a 259 partial order, such as found in a GADAG. X >> Y means that X is 260 higher in the partial order than Y. Y << X means that Y is lower 261 in the partial order than X. 263 X > Y or Y < X: Indicates the relationship between X and Y in the 264 total order, such as found via a topological sort. X > Y means 265 that X is higher in the total order than Y. Y < X means that Y is 266 lower in the total order than X. 268 proxy-node: A node added to the network graph to represent a multi- 269 homed prefix or routers outside the local MRT-fast-reroute- 270 supporting island of routers. The key property of proxy-nodes is 271 that traffic cannot transit them. 273 3. Algorithm Key Concepts 275 There are five key concepts that are critical for understanding the 276 MRT Lowpoint algorithm and other algorithms for computing MRTs. The 277 first is the idea of partially ordering the nodes in a network graph 278 with regard to each other and to the GADAG root. The second is the 279 idea of finding an ear of nodes and adding them in the correct 280 direction. The third is the idea of a Low-Point value and how it can 281 be used to identify cut-vertices and to find a second path towards 282 the root. The fourth is the idea that a non-2-connected graph is 283 made up of blocks, where a block is a 2-connected cluster, a cut-edge 284 or an isolated node. The fifth is the idea of a local-root for each 285 node; this is used to compute ADAGs in each block. 287 3.1. Partial Ordering for Disjoint Paths 289 Given any two nodes X and Y in a graph, a particular total order 290 means that either X < Y or X > Y in that total order. An example 291 would be a graph where the nodes are ranked based upon their unique 292 IP loopback addresses. In a partial order, there may be some nodes 293 for which it can't be determined whether X << Y or X >> Y. A partial 294 order can be captured in a directed graph, as shown in Figure 3. In 295 a graphical representation, a link directed from X to Y indicates 296 that X is a neighbor of Y in the network graph and X << Y. 298 [A]<---[R] [E] R << A << B << C << D << E 299 | ^ R << A << B << F << G << H << D << E 300 | | 301 V | Unspecified Relationships: 302 [B]--->[C]--->[D] C and F 303 | ^ C and G 304 | | C and H 305 V | 306 [F]--->[G]--->[H] 308 Figure 3: Directed Graph showing a Partial Order 310 To compute MRTs, the root of the MRTs is at both the very bottom and 311 the very top of the partial ordering. This means that from any node 312 X, one can pick nodes higher in the order until the root is reached. 313 Similarly, from any node X, one can pick nodes lower in the order 314 until the root is reached. For instance, in Figure 4, from G the 315 higher nodes picked can be traced by following the directed links and 316 are H, D, E and R. Similarly, from G the lower nodes picked can be 317 traced by reversing the directed links and are F, B, A, and R. A 318 graph that represents this modified partial order is no longer a DAG; 319 it is termed an Almost DAG (ADAG) because if the links directed to 320 the root were removed, it would be a DAG. 322 [A]<---[R]<---[E] R << A << B << C << R 323 | ^ ^ R << A << B << C << D << E << R 324 | | | R << A << B << F << G << H << D << E << R 325 V | | 326 [B]--->[C]--->[D] Unspecified Relationships: 327 | ^ C and F 328 | | C and G 329 V | C and H 330 [F]--->[G]--->[H] 332 Figure 4: ADAG showing a Partial Order with R lowest and highest 334 Most importantly, if a node Y >> X, then Y can only appear on the 335 increasing path from X to the root and never on the decreasing path. 336 Similarly, if a node Z << X, then Z can only appear on the decreasing 337 path from X to the root and never on the inceasing path. 339 When following the increasing paths, it is possible to pick multiple 340 higher nodes and still have the certainty that those paths will be 341 disjoint from the decreasing paths. E.g. in the previous example 342 node B has multiple possibilities to forward packets along an 343 increasing path: it can either forward packets to C or F. 345 3.2. Finding an Ear and the Correct Direction 347 For simplicity, the basic idea of creating a GADAG by adding ears is 348 described assuming that the network graph is a single 2-connected 349 cluster so that an ADAG is sufficient. Generalizing to multiple 350 blocks is done by considering the block-roots instead of the GADAG 351 root - and the actual algorithm is given in Section 4.4. 353 In order to understand the basic idea of finding an ADAG, first 354 suppose that we have already a partial ADAG, which doesn't contain 355 all the nodes in the block yet, and we want to extend it to cover all 356 the nodes. Suppose that we find a path from a node X to Y such that 357 X and Y are already contained by our partial ADAG, but all the 358 remaining nodes along the path are not added to the ADAG yet. We 359 refer to such a path as an ear. 361 Recall that our ADAG is closely related to a partial order, more 362 precisely, if we remove root R, the remaining DAG describes a partial 363 order of the nodes. If we suppose that neither X nor Y is the root, 364 we may be able to compare them. If one of them is definitely lesser 365 with respect to our partial order (say X<B---| A-->B---| 377 (a) (b) (c) 379 (a) A 2-connected graph 380 (b) Partial ADAG (C is not included) 381 (c) Resulting ADAG after adding path (or ear) B-C-D 382 Figure 5 384 In this partial ADAG, node C is not yet included. However, we can 385 find path B-C-D, where both endpoints are contained by this partial 386 ADAG (we say those nodes are *ready* in the sequel), and the 387 remaining node (node C) is not contained yet. If we remove R, the 388 remaining DAG defines a partial order, and with respect to this 389 partial order we can say that B<C and C->D are added). If 391 B were strictly greater than D, we would add the same path in reverse 392 direction. 394 If in the partial order where an ear's two ends are X and Y, X << Y, 395 then there must already be a directed path from X to Y already in the 396 ADAG. The ear must be added in a direction such that it doesn't 397 create a cycle; therefore the ear must go from X to Y. 399 In the case, when X and Y are not ordered with each other, we can 400 select either direction for the ear. We have no restriction since 401 neither of the directions can result in a cycle. In the corner case 402 when one of the endpoints of an ear, say X, is the root (recall that 403 the two endpoints must be different), we could use both directions 404 again for the ear because the root can be considered both as smaller 405 and as greater than Y. However, we strictly pick that direction in 406 which the root is lower than Y. The logic for this decision is 407 explained in Section 4.6 409 A partial ADAG is started by finding a cycle from the root R back to 410 itself. This can be done by selecting a non-ready neighbor N of R 411 and then finding a path from N to R that doesn't use any links 412 between R and N. The direction of the cycle can be assigned either 413 way since it is starting the ordering. 415 Once a partial ADAG is already present, we can always add ears to it: 416 just select a non-ready neighbor N of a ready node Q, such that Q is 417 not the root, find a path from N to the root in the graph with Q 418 removed. This path is an ear where the first node of the ear is Q, 419 the next is N, then the path until the first ready node the path 420 reached (that second ready node is the other endpoint of the path). 421 Since the graph is 2-connected, there must be a path from N to R 422 without Q. 424 It is always possible to select a non-ready neighbor N of a ready 425 node Q so that Q is not the root R. Because the network is 426 2-connected, N must be connected to two different nodes and only one 427 can be R. Because the initial cycle has already been added to the 428 ADAG, there are ready nodes that are not R. Since the graph is 429 2-connected, while there are non-ready nodes, there must be a non- 430 ready neighbor N of a ready node that is not R. 432 Generic_Find_Ears_ADAG(root) 433 Create an empty ADAG. Add root to the ADAG. 434 Mark root as IN_GADAG. 435 Select an arbitrary cycle containing root. 436 Add the arbitrary cycle to the ADAG. 437 Mark cycle's nodes as IN_GADAG. 438 Add cycle's non-root nodes to process_list. 439 while there exists connected nodes in graph that are not IN_GADAG 440 Select a new ear. Let its endpoints be X and Y. 441 if Y is root or (Y << X) 442 add the ear towards X to the ADAG 443 else // (a) X is root or (b)X << Y or (c) X, Y not ordered 444 Add the ear towards Y to the ADAG 446 Figure 6: Generic Algorithm to find ears and their direction in 447 2-connected graph 449 Algorithm Figure 6 merely requires that a cycle or ear be selected 450 without specifying how. Regardless of the way of selecting the path, 451 we will get an ADAG. The method used for finding and selecting the 452 ears is important; shorter ears result in shorter paths along the 453 MRTs. The MRT Lowpoint algorithm's method using Low-Point 454 Inheritance is defined in Section 4.4. Other methods are described 455 in the Appendices (Appendix A and Appendix B). 457 As an example, consider Figure 5 again. First, we select the 458 shortest cycle containing R, which can be R-A-B-F-D-E (uniform link 459 costs were assumed), so we get to the situation depicted in Figure 5 460 (b). Finally, we find a node next to a ready node; that must be node 461 C and assume we reached it from ready node B. We search a path from C 462 to R without B in the original graph. The first ready node along 463 this is node D, so the open ear is B-C-D. Since B<C 464 and C->D to the ADAG. Since all the nodes are ready, we stop at this 465 point. 467 3.3. Low-Point Values and Their Uses 469 A basic way of computing a spanning tree on a network graph is to run 470 a depth-first-search, such as given in Figure 7. This tree has the 471 important property that if there is a link (x, n), then either n is a 472 DFS ancestor of x or n is a DFS descendant of x. In other words, 473 either n is on the path from the root to x or x is on the path from 474 the root to n. 476 global_variable: dfs_number 478 DFS_Visit(node x, node parent) 479 D(x) = dfs_number 480 dfs_number += 1 481 x.dfs_parent = parent 482 for each link (x, w) 483 if D(w) is not set 484 DFS_Visit(w, x) 486 Run_DFS(node root) 487 dfs_number = 0 488 DFS_Visit(root, NONE) 490 Figure 7: Basic Depth-First Search algorithm 492 Given a node x, one can compute the minimal DFS number of the 493 neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the 494 highest attachment point neighbouring x. What is interesting, 495 though, is what is the highest attachment point from x and x's 496 descendants. This is what is determined by computing the Low-Point 497 value, as given in Algorithm Figure 9 and illustrated on a graph in 498 Figure 8. 500 [E]---| [J]-------[I] [P]---[O] 501 | | | | | | 502 | | | | | | 503 [R] [D]---[C]--[F] [H]---[K] [N] 504 | | | | | | 505 | | | | | | 506 [A]--------[B] [G]---| [L]---[M] 508 (a) a non-2-connected graph 510 [E]----| [J]---------[I] [P]------[O] 511 (5, ) | (10, ) (9, ) (16, ) (15, ) 512 | | | | | | 513 | | | | | | 514 [R] [D]---[C]---[F] [H]----[K] [N] 516 (0, ) (4, ) (3, ) (6, ) (8, ) (11, ) (14, ) 517 | | | | | | 518 | | | | | | 519 [A]---------[B] [G]----| [L]------[M] 520 (1, ) (2, ) (7, ) (12, ) (13, ) 522 (b) with DFS values assigned (D(x), L(x)) 524 [E]----| [J]---------[I] [P]------[O] 525 (5,0) | (10,3) (9,3) (16,11) (15,11) 526 | | | | | | 527 | | | | | | 528 [R] [D]---[C]---[F] [H]----[K] [N] 529 (0, ) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11) 530 | | | | | | 531 | | | | | | 532 [A]---------[B] [G]----| [L]------[M] 533 (1,0) (2,0) (7,3) (12,11) (13,11) 535 (c) with low-point values assigned (D(x), L(x)) 537 Figure 8 539 global_variable: dfs_number 541 Lowpoint_Visit(node x, node parent, interface p_to_x) 542 D(x) = dfs_number 543 L(x) = D(x) 544 dfs_number += 1 545 x.dfs_parent = parent 546 x.dfs_parent_intf = p_to_x 547 x.lowpoint_parent = NONE 548 for each interface intf of x: 549 if D(intf.remote_node) is not set 550 Lowpoint_Visit(intf.remote_node, x, intf) 551 if L(intf.remote_node) < L(x) 552 L(x) = L(intf.remote_node) 553 x.lowpoint_parent = intf.remote_node 554 x.lowpoint_parent_intf = intf 555 else if intf.remote_node is not parent 556 if D(intf.remote_node) < L(x) 557 L(x) = D(intf.remote) 558 x.lowpoint_parent = intf.remote_node 559 x.lowpoint_parent_intf = intf 561 Run_Lowpoint(node root) 562 dfs_number = 0 563 Lowpoint_Visit(root, NONE, NONE) 565 Figure 9: Computing Low-Point value 567 From the low-point value and lowpoint parent, there are two very 568 useful things which motivate our computation. 570 First, if there is a child c of x such that L(c) >= D(x), then there 571 are no paths in the network graph that go from c or its descendants 572 to an ancestor of x - and therefore x is a cut-vertex. This is 573 useful because it allows identification of the cut-vertices and thus 574 the blocks. As seen in Figure 8, even if L(x) < D(x), there may be a 575 block that contains both the root and a DFS-child of a node while 576 other DFS-children might be in different blocks. In this example, 577 C's child D is in the same block as R while F is not. 579 Second, by repeatedly following the path given by lowpoint_parent, 580 there is a path from x back to an ancestor of x that does not use the 581 link [x, x.dfs_parent] in either direction. The full path need not 582 be taken, but this gives a way of finding an initial cycle and then 583 ears. 585 3.4. Blocks in a Graph 587 A key idea for an MRT algorithm is that any non-2-connected graph is 588 made up by blocks (e.g. 2-connected clusters, cut-links, and/or 589 isolated nodes). To compute GADAGs and thus MRTs, computation is 590 done in each block to compute ADAGs or Redundant Trees and then those 591 ADAGs or Redundant Trees are combined into a GADAG or MRT. 593 [E]---| [J]-------[I] [P]---[O] 594 | | | | | | 595 | | | | | | 596 [R] [D]---[C]--[F] [H]---[K] [N] 597 | | | | | | 598 | | | | | | 599 [A]--------[B] [G]---| [L]---[M] 601 (a) A graph with four blocks that are: 602 3 2-connected clusters and a cut-link 604 [E]<--| [J]<------[I] [P]<--[O] 605 | | | ^ | ^ 606 V | V | V | 607 [R] [D]<--[C] [F] [H]<---[K] [N] 608 ^ | ^ ^ 609 | V | | 611 [A]------->[B] [G]---| [L]-->[M] 613 (b) MRT-Blue 615 [E]---| [J]-------->[I] [P]-->[O] 616 | | | 617 V V V 618 [R] [D]-->[C]<---[F] [H]<---[K] [N] 619 ^ | ^ | ^ | 620 | V | | | V 621 [A]<-------[B] [G]<--| [L]<--[M] 623 (c) MRT-Red 625 Figure 10 627 Consider the example depicted in Figure 10 (a). In this figure, a 628 special graph is presented, showing us all the ways 2-connected 629 clusters can be connected. It has four blocks: block 1 contains R, 630 A, B, C, D, E, block 2 contains C, F, G, H, I, J, block 3 contains K, 631 L, M, N, O, P, and block 4 is a cut-edge containing H and K. As can 632 be observed, the first two blocks have one common node (node C) and 633 blocks 2 and 3 do not have any common node, but they are connected 634 through a cut-edge that is block 4. No two blocks can have more than 635 one common node, since two blocks with at least 2 common nodes would 636 qualify as a single 2-connected cluster. 638 Moreover, observe that if we want to get from one block to another, 639 we must use a cut-vertex (the cut-vertices in this graph are C, H, 640 K), regardless of the path selected, so we can say that all the paths 641 from block 3 along the MRTs rooted at R will cross K first. This 642 observation means that if we want to find a pair of MRTs rooted at R, 643 then we need to build up a pair of RTs in block 3 with K as a root. 644 Similarly, we need to find another one in block 2 with C as a root, 645 and finally, we need the last one in block 1 with R as a root. When 646 all the trees are selected, we can simply combine them; when a block 647 is a cut-edge (as in block 4), that cut-edge is added in the same 648 direction to both of the trees. The resulting trees are depicted in 649 Figure 10 (b) and (c). 651 Similarly, to create a GADAG it is sufficient to compute ADAGs in 652 each block and connect them. 654 It is necessary, therefore, to identify the cut-vertices, the blocks 655 and identify the appropriate local-root to use for each block. 657 3.5. Determining Local-Root and Assigning Block-ID 659 Each node in a network graph has a local-root, which is the cut- 660 vertex (or root) in the same block that is closest to the root. The 661 local-root is used to determine whether two nodes share a common 662 block. 664 Compute_Localroot(node x, node localroot) 665 x.localroot = localroot 666 for each DFS child c 667 if L(c) < D(x) //x is not a cut-vertex 668 Compute_Localroot(c, x.localroot) 669 else 670 mark x as cut-vertex 671 Compute_Localroot(c, x) 673 Compute_Localroot(root, root) 675 Figure 11: A method for computing local-roots 677 There are two different ways of computing the local-root for each 678 node. The stand-alone method is given in Figure 11 and better 679 illustrates the concept; it is used by the MRT algorithms given in 680 the Appendices Appendix A and Appendix B. The method for local-root 681 computation is used in the MRT Lowpoint algorithm for computing a 682 GADAG using Low-Point inheritance and the essence of it is given in 683 Figure 12. 685 Get the current node, s. 686 Compute an ear(either through lowpoint inheritance 687 or by following dfs parents) from s to a ready node e. 688 (Thus, s is not e, if there is such ear.) 689 if s is e 690 for each node x in the ear that is not s 691 x.localroot = s 692 else 693 for each node x in the ear that is not s or e 694 x.localroot = e.localroot 696 Figure 12: Ear-based method for computing local-roots 698 Once the local-roots are known, two nodes X and Y are in a common 699 block if and only if one of the following three conditions apply. 701 o Y's local-root is X's local-root : They are in the same block and 702 neither is the cut-vertex closest to the root. 704 o Y's local-root is X: X is the cut-vertex closest to the root for 705 Y's block 707 o Y is X's local-root: Y is the cut-vertex closest to the root for 708 X's block 710 Once we have computed the local-root for each node in the network 711 graph, we can assign for each node, a block id that represents the 712 block in which the node is present. This computation is shown in 713 Figure 13. 715 global_var: max_block_id 717 Assign_Block_ID(x, cur_block_id) 718 x.block_id = cur_block_id 719 foreach DFS child c of x 720 if (c.local_root is x) 721 max_block_id += 1 722 Assign_Block_ID(c, max_block_id) 723 else 724 Assign_Block_ID(c, cur_block_id) 726 max_block_id = 0 727 Assign_Block_ID(root, max_block_id) 729 Figure 13: Assigning block id to identify blocks 731 4. Algorithm Sections 733 This algorithm computes one GADAG that is then used by a router to 734 determine its MRT-Blue and MRT-Red next-hops to all destinations. 735 Finally, based upon that information, alternates are selected for 736 each next-hop to each destination. The different parts of this 737 algorithm are described below. These work on a network graph after, 738 for instance, its interfaces are ordered as per Figure 14. 740 1. Compute the local MRT Island for the particular MRT Profile. 741 [See Section 4.1.] 743 2. Select the root to use for the GADAG. [See Section 4.2.] 745 3. Initialize all interfaces to UNDIRECTED. [See Section 4.3.] 747 4. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See 748 Figure 9.] 750 5. Construct the GADAG. [See Section 4.4] 751 6. Assign directions to all interfaces that are still UNDIRECTED. 752 [See Section 4.5.] 754 7. From the computing router x, compute the next-hops for the MRT- 755 Blue and MRT-Red. [See Section 4.6.] 757 8. Identify alternates for each next-hop to each destination by 758 determining which one of the blue MRT and the red MRT the 759 computing router x should select. [See Section 4.7.] 761 To ensure consistency in computation, all routers MUST order 762 interfaces identically. This is necessary for the DFS, where the 763 selection order of the interfaces to explore results in different 764 trees, and for computing the GADAG, where the selection order of the 765 interfaces to use to form ears can result in different GADAGs. The 766 required ordering between two interfaces from the same router x is 767 given in Figure 14. 769 Interface_Compare(interface a, interface b) 770 if a.metric < b.metric 771 return A_LESS_THAN_B 772 if b.metric < a.metric 773 return B_LESS_THAN_A 774 if a.neighbor.loopback_addr < b.neighbor.loopback_addr 775 return A_LESS_THAN_B 776 if b.neighbor.loopback_addr < a.neighbor.loopback_addr 777 return B_LESS_THAN_A 778 // Same metric to same node, so the order doesn't matter anymore. 779 // To have a unique, consistent total order, 780 // tie-break based on, for example, the link's linkData as 781 // distributed in an OSPF Router-LSA 782 if a.link_data < b.link_data 783 return A_LESS_THAN_B 784 return B_LESS_THAN_A 786 Figure 14: Rules for ranking multiple interfaces. Order is from low 787 to high. 789 4.1. MRT Island Identification 791 The local MRT Island for a particular MRT profile can be determined 792 by starting from the computing router in the network graph and doing 793 a breadth-first-search (BFS), exploring only links that aren't MRT- 794 ineligible. 796 MRT_Island_Identification(topology, computing_rtr, profile_id) 797 for all routers in topology 798 rtr.IN_MRT_ISLAND = FALSE 800 computing_rtr.IN_MRT_ISLAND = TRUE 801 explore_list = { computing_rtr } 802 while (explore_list is not empty) 803 next_rtr = remove_head(explore_list) 804 for each interface in next_rtr 805 if interface is not MRT-ineligible 806 if ((interface.remote_node supports profile_id) and 807 (interface.remote_node.IN_MRT_ISLAND is FALSE)) 808 interface.remote_node.IN_MRT_ISLAND = TRUE 809 add_to_tail(explore_list, interface.remote_node) 811 Figure 15: MRT Island Identification 813 4.2. Root Selection 815 In [I-D.atlas-ospf-mrt], a mechanism is given for routers to 816 advertise the GADAG Root Selection Priority and consistently select a 817 GADAG Root inside the local MRT Island. Before beginning 818 computation, the network graph is reduced to contain only the set of 819 routers that support the specific MRT profile whose MRTs are being 820 computed. 822 Off-line analysis that considers the centrality of a router may help 823 determine how good a choice a particular router is for the role of 824 GADAG root. 826 4.3. Initialization 828 Before running the algorithm, there is the standard type of 829 initialization to be done, such as clearing any computed DFS-values, 830 lowpoint-values, DFS-parents, lowpoint-parents, any MRT-computed 831 next-hops, and flags associated with algorithm. 833 It is assumed that a regular SPF computation has been run so that the 834 primary next-hops from the computing router to each destination are 835 known. This is required for determining alternates at the last step. 837 Initially, all interfaces must be initialized to UNDIRECTED. Whether 838 they are OUTGOING, INCOMING or both is determined when the GADAG is 839 constructed and augmented. 841 It is possible that some links and nodes will be marked as unusable, 842 whether because of configuration, IGP flooding (e.g. MRT-ineligible 843 links in [I-D.atlas-ospf-mrt]), overload, or due to a transient cause 844 such as [RFC3137]. In the algorithm description, it is assumed that 845 such links and nodes will not be explored or used and no more 846 discussion is given of this restriction. 848 4.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance 850 As discussed in Section 3.2, it is necessary to find ears from a node 851 x that is already in the GADAG (known as IN_GADAG). There are two 852 methods to find ears; both are required. The first is by going to a 853 not IN_GADAG DFS-child and then following the chain of low-point 854 parents until an IN_GADAG node is found. The second is by going to a 855 not IN_GADAG neighbor and then following the chain of DFS parents 856 until an IN_GADAG node is found. As an ear is found, the associated 857 interfaces are marked based on the direction taken. The nodes in the 858 ear are marked as IN_GADAG. In the algorithm, first the ears via 859 DFS-children are found and then the ears via DFS-neighbors are found. 861 By adding both types of ears when an IN_GADAG node is processed, all 862 ears that connect to that node are found. The order in which the 863 IN_GADAG nodes is processed is, of course, key to the algorithm. The 864 order is a stack of ears so the most recent ear is found at the top 865 of the stack. Of course, the stack stores nodes and not ears, so an 866 ordered list of nodes, from the first node in the ear to the last 867 node in the ear, is created as the ear is explored and then that list 868 is pushed onto the stack. 870 Each ear represents a partial order (see Figure 4) and processing the 871 nodes in order along each ear ensures that all ears connecting to a 872 node are found before a node higher in the partial order has its ears 873 explored. This means that the direction of the links in the ear is 874 always from the node x being processed towards the other end of the 875 ear. Additionally, by using a stack of ears, this means that any 876 unprocessed nodes in previous ears can only be ordered higher than 877 nodes in the ears below it on the stack. 879 In this algorithm that depends upon Low-Point inheritance, it is 880 necessary that every node have a low-point parent that is not itself. 881 If a node is a cut-vertex, that may not yet be the case. Therefore, 882 any nodes without a low-point parent will have their low-point parent 883 set to their DFS parent and their low-point value set to the DFS- 884 value of their parent. This assignment also properly allows an ear 885 between two cut-vertices. 887 Finally, the algorithm simultaneously computes each node's local- 888 root, as described in Figure 12. This is further elaborated as 889 follows. The local-root can be inherited from the node at the end of 890 the ear unless the end of the ear is x itself, in which case the 891 local-root for all the nodes in the ear would be x. This is because 892 whenever the first cycle is found in a block, or an ear involving a 893 bridge is computed, the cut-vertex closest to the root would be x 894 itself. In all other scenarios, the properties of lowpoint/dfs 895 parents ensure that the end of the ear will be in the same block, and 896 thus inheriting its local-root would be the correct local-root for 897 all newly added nodes. 899 The pseudo-code for the GADAG algorithm (assuming that the adjustment 900 of lowpoint for cut-vertices has been made) is shown in Figure 16. 902 Construct_Ear(x, Stack, intf, type) 903 ear_list = empty 904 cur_node = intf.remote_node 905 cur_intf = intf 906 not_done = true 908 while not_done 909 cur_intf.UNDIRECTED = false 910 cur_intf.OUTGOING = true 911 cur_intf.remote_intf.UNDIRECTED = false 912 cur_intf.remote_intf.INCOMING = true 914 if cur_node.IN_GADAG is false 915 cur_node.IN_GADAG = true 916 add_to_list_end(ear_list, cur_node) 917 if type is CHILD 918 cur_intf = cur_node.lowpoint_parent_intf 919 cur_node = cur_node.lowpoint_parent 920 else type must be NEIGHBOR 921 cur_intf = cur_node.dfs_parent_intf 922 cur_node = cur_node.dfs_parent 923 else 924 not_done = false 926 if (type is CHILD) and (cur_node is x) 927 //x is a cut-vertex and the local root for 928 //the block in which the ear is computed 929 localroot = x 930 else 931 // Inherit local-root from the end of the ear 932 localroot = cur_node.localroot 933 while ear_list is not empty 934 y = remove_end_item_from_list(ear_list) 935 y.localroot = localroot 936 push(Stack, y) 938 Construct_GADAG_via_Lowpoint(topology, root) 939 root.IN_GADAG = true 940 root.localroot = root 941 Initialize Stack to empty 942 push root onto Stack 943 while (Stack is not empty) 944 x = pop(Stack) 945 foreach interface intf of x 946 if ((intf.remote_node.IN_GADAG == false) and 947 (intf.remote_node.dfs_parent is x)) 948 Construct_Ear(x, Stack, intf, CHILD) 949 foreach interface intf of x 950 if ((intf.remote_node.IN_GADAG == false) and 951 (intf.remote_node.dfs_parent is not x)) 952 Construct_Ear(x, Stack, intf, NEIGHBOR) 954 Construct_GADAG_via_Lowpoint(topology, root) 956 Figure 16: Low-point Inheritance GADAG algorithm 958 4.5. Augmenting the GADAG by directing all links 960 The GADAG, regardless of the algorithm used to construct it, at this 961 point could be used to find MRTs but the topology does not include 962 all links in the network graph. That has two impacts. First, there 963 might be shorter paths that respect the GADAG partial ordering and so 964 the alternate paths would not be as short as possible. Second, there 965 may be additional paths between a router x and the root that are not 966 included in the GADAG. Including those provides potentially more 967 bandwidth to traffic flowing on the alternates and may reduce 968 congestion compared to just using the GADAG as currently constructed. 970 The goal is thus to assign direction to every remaining link marked 971 as UNDIRECTED to improve the paths and number of paths found when the 972 MRTs are computed. 974 To do this, we need to establish a total order that respects the 975 partial order described by the GADAG. This can be done using Kahn's 976 topological sort[Kahn_1962_topo_sort] which essentially assigns a 977 number to a node x only after all nodes before it (e.g. with a link 978 incoming to x) have had their numbers assigned. The only issue with 979 the topological sort is that it works on DAGs and not ADAGs or 980 GADAGs. 982 To convert a GADAG to a DAG, it is necessary to remove all links that 983 point to a root of block from within that block. That provides the 984 necessary conversion to a DAG and then a topological sort can be 985 done. Finally, all UNDIRECTED links are assigned a direction based 986 upon the partial ordering. Any UNDIRECTED links that connect to a 987 root of a block from within that block are assigned a direction 988 INCOMING to that root. The exact details of this whole process are 989 captured in Figure 17 990 Set_Block_Root_Incoming_Links(topo, root, mark_or_clear) 991 foreach node x in topo 992 if node x is a cut-vertex or root 993 foreach interface i of x 994 if (i.remote_node.localroot is x) 995 if i.UNDIRECTED 996 i.OUTGOING = true 997 i.remote_intf.INCOMING = true 998 i.UNDIRECTED = false 999 i.remote_intf.UNDIRECTED = false 1000 if i.INCOMING 1001 if mark_or_clear is mark 1002 if i.OUTGOING // a cut-edge 1003 i.STORE_INCOMING = true 1004 i.INCOMING = false 1005 i.remote_intf.STORE_OUTGOING = true 1006 i.remote_intf.OUTGOING = false 1007 i.TEMP_UNUSABLE = true 1008 i.remote_intf.TEMP_UNUSABLE = true 1009 else 1010 i.TEMP_UNUSABLE = false 1011 i.remote_intf.TEMP_UNUSABLE = false 1012 if i.STORE_INCOMING and (mark_or_clear is clear) 1013 i.INCOMING = true 1014 i.STORE_INCOMING = false 1015 i.remote_intf.OUTGOING = true 1016 i.remote_intf.STORE_OUTGOING = false 1018 Run_Topological_Sort_GADAG(topo, root) 1019 Set_Block_Root_Incoming_Links(topo, root, MARK) 1020 foreach node x 1021 set x.unvisited to the count of x's incoming interfaces 1022 that aren't marked TEMP_UNUSABLE 1023 Initialize working_list to empty 1024 Initialize topo_order_list to empty 1025 add_to_list_end(working_list, root) 1026 while working_list is not empty 1027 y = remove_start_item_from_list(working_list) 1028 add_to_list_end(topo_order_list, y) 1029 foreach interface i of y 1030 if (i.OUTGOING) and (not i.TEMP_UNUSABLE) 1031 i.remote_node.unvisited -= 1 1032 if i.remote_node.unvisited is 0 1033 add_to_list_end(working_list, i.remote_node) 1034 next_topo_order = 1 1035 while topo_order_list is not empty 1036 y = remove_start_item_from_list(topo_order_list) 1037 y.topo_order = next_topo_order 1038 next_topo_order += 1 1039 Set_Block_Root_Incoming_Links(topo, root, CLEAR) 1041 Add_Undirected_Links(topo, root) 1042 Run_Topological_Sort_GADAG(topo, root) 1043 foreach node x in topo 1044 foreach interface i of x 1045 if i.UNDIRECTED 1046 if x.topo_order < i.remote_node.topo_order 1047 i.OUTGOING = true 1048 i.UNDIRECTED = false 1049 i.remote_intf.INCOMING = true 1050 i.remote_intf.UNDIRECTED = false 1051 else 1052 i.INCOMING = true 1053 i.UNDIRECTED = false 1054 i.remote_intf.OUTGOING = true 1055 i.remote_intf.UNDIRECTED = false 1057 Add_Undirected_Links(topo, root) 1059 Figure 17: Assigning direction to UNDIRECTED links 1061 Proxy-nodes do not need to be added to the network graph. They 1062 cannot be transited and do not affect the MRTs that are computed. 1063 The details of how the MRT-Blue and MRT-Red next-hops are computed 1064 and how the appropriate alternate next-hops are selected is given in 1065 Section 4.8. 1067 4.6. Compute MRT next-hops 1069 As was discussed in Section 3.1, once a ADAG is found, it is 1070 straightforward to find the next-hops from any node X to the ADAG 1071 root. However, in this algorithm, we want to reuse the common GADAG 1072 and find not only the one pair of MRTs rooted at the GADAG root with 1073 it, but find a pair rooted at each node. This is useful since it is 1074 significantly faster to compute. It may also provide easier 1075 troubleshooting of the MRT-Red and MRT-Blue. 1077 The method for computing differently rooted MRTs from the common 1078 GADAG is based on two ideas. First, if two nodes X and Y are ordered 1079 with respect to each other in the partial order, then an SPF along 1080 OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a 1081 decreasing-SPF) can be used to find the increasing and decreasing 1082 paths. Second, if two nodes X and Y aren't ordered with respect to 1083 each other in the partial order, then intermediary nodes can be used 1084 to create the paths by increasing/decreasing to the intermediary and 1085 then decreasing/increasing to reach Y. 1087 As usual, the two basic ideas will be discussed assuming the network 1088 is two-connected. The generalization to multiple blocks is discussed 1089 in Section 4.6.4. The full algorithm is given in Section 4.6.5. 1091 4.6.1. MRT next-hops to all nodes partially ordered with respect to the 1092 computing node 1094 To find two node-disjoint paths from the computing router X to any 1095 node Y, depends upon whether Y >> X or Y << X. As shown in Figure 1096 18, if Y >> X, then there is an increasing path that goes from X to Y 1097 without crossing R; this contains nodes in the interval [X,Y]. There 1098 is also a decreasing path that decreases towards R and then decreases 1099 from R to Y; this contains nodes in the interval [X,R-small] or 1100 [R-great,Y]. The two paths cannot have common nodes other than X and 1101 Y. 1103 [Y]<---(Cloud 2)<--- [X] 1104 | ^ 1105 | | 1106 V | 1107 (Cloud 3)--->[R]--->(Cloud 1) 1109 MRT-Blue path: X->Cloud 2->Y 1110 MRT-Red path: X->Cloud 1->R->Cloud 3->Y 1112 Figure 18: Y >> X 1114 Similar logic applies if Y << X, as shown in Figure 19. In this 1115 case, the increasing path from X increases to R and then increases 1116 from R to Y to use nodes in the intervals [X,R-great] and [R-small, 1117 Y]. The decreasing path from X reaches Y without crossing R and uses 1118 nodes in the interval [Y,X]. 1120 [X]<---(Cloud 2)<--- [Y] 1121 | ^ 1122 | | 1123 V | 1124 (Cloud 3)--->[R]--->(Cloud 1) 1126 MRT-Blue path: X->Cloud 3->R->Cloud 1->Y 1127 MRT-Red path: X->Cloud 2->Y 1129 Figure 19: Y << X 1131 4.6.2. MRT next-hops to all nodes not partially ordered with respect to 1132 the computing node 1134 When X and Y are not ordered, the first path should increase until we 1135 get to a node G, where G >> Y. At G, we need to decrease to Y. The 1136 other path should be just the opposite: we must decrease until we get 1137 to a node H, where H << Y, and then increase. Since R is smaller and 1138 greater than Y, such G and H must exist. It is also easy to see that 1139 these two paths must be node disjoint: the first path contains nodes 1140 in interval [X,G] and [Y,G], while the second path contains nodes in 1141 interval [H,X] and [H,Y]. This is illustrated in Figure 20. It is 1142 necessary to decrease and then increase for the MRT-Blue and increase 1143 and then decrease for the MRT-Red; if one simply increased for one 1144 and decreased for the other, then both paths would go through the 1145 root R. 1147 (Cloud 6)<---[Y]<---(Cloud 5)<------------| 1148 | | 1149 | | 1150 V | 1151 [G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H] 1152 ^ | 1153 | | 1154 | | 1155 (Cloud 3)<---[X]<---(Cloud 2)<-----------| 1157 MRT-Blue path: decrease to H and increase to Y 1158 X->Cloud 2->H->Cloud 5->Y 1159 MRT-Red path: increase to G and decrease to Y 1160 X->Cloud 3->G->Cloud 6->Y 1162 Figure 20: X and Y unordered 1164 This gives disjoint paths as long as G and H are not the same node. 1165 Since G >> Y and H << Y, if G and H could be the same node, that 1166 would have to be the root R. This is not possible because there is 1167 only one incoming interface to the root R which is created when the 1168 initial cycle is found. Recall from Figure 6 that whenever an ear 1169 was found to have an end that was the root R, the ear was directed 1170 from R so that the associated interface on R is outgoing and not 1171 incoming. Therefore, there must be exactly one node M which is the 1172 largest one before R, so the MRT-Red path will never reach R; it will 1173 turn at M and decrease to Y. 1175 4.6.3. Computing Redundant Tree next-hops in a 2-connected Graph 1177 The basic ideas for computing RT next-hops in a 2-connected graph 1178 were given in Section 4.6.1 and Section 4.6.2. Given these two 1179 ideas, how can we find the trees? 1180 If some node X only wants to find the next-hops (which is usually the 1181 case for IP networks), it is enough to find which nodes are greater 1182 and less than X, and which are not ordered; this can be done by 1183 running an increasing-SPF and a decreasing-SPF rooted at X and not 1184 exploring any links from the ADAG root. ( Traversal algorithms other 1185 than SPF could safely be used instead where one traversal takes the 1186 links in their given directions and the other reverses the links' 1187 directions.) 1189 An increasing-SPF rooted at X and not exploring links from the root 1190 will find the increasing next-hops to all Y >> X. Those increasing 1191 next-hops are X's next-hops on the MRT-Blue to reach Y. An 1192 decreasing-SPF rooted at X and not exploring links from the root will 1193 find the decreasing next-hops to all Z << X. Those decreasing next- 1194 hops are X's next-hops on the MRT-Red to reach Z. Since the root R 1195 is both greater than and less than X, after this increasing-SPF and 1196 decreasing-SPF, X's next-hops on the MRT-Blue and on the MRT-Red to 1197 reach R are known. For every node Y >> X, X's next-hops on the MRT- 1198 Red to reach Y are set to those on the MRT-Red to reach R. For every 1199 node Z << X, X's next-hops on the MRT-Blue to reach Z are set to 1200 those on the MRT-Blue to reach R. 1202 For those nodes, which were not reached, we have the next-hops as 1203 well. The increasing MRT-Blue next-hop for a node, which is not 1204 ordered, is the next-hop along the decreasing MRT-Red towards R and 1205 the decreasing MRT-Red next-hop is the next-hop along the increasing 1206 MRT-Blue towards R. Naturally, since R is ordered with respect to all 1207 the nodes, there will always be an increasing and a decreasing path 1208 towards it. This algorithm does not provide the complete specific 1209 path taken but just the appropriate next-hops to use. The identity 1210 of G and H is not determined. 1212 The final case to considered is when the root R computes its own 1213 next-hops. Since the root R is << all other nodes, running an 1214 increasing-SPF rooted at R will reach all other nodes; the MRT-Blue 1215 next-hops are those found with this increasing-SPF. Similarly, since 1216 the root R is >> all other nodes, running a decreasing-SPF rooted at 1217 R will reach all other nodes; the MRT-Red next-hops are those found 1218 with this decreasing-SPF. 1220 E---D---| E<--D<--| 1221 | | | | ^ | 1222 | | | V | | 1223 R F C R F C 1224 | | | | ^ ^ 1225 | | | V | | 1226 A---B---| A-->B---| 1227 (a) (b) 1228 A 2-connected graph A spanning ADAG rooted at R 1230 Figure 21 1232 As an example consider the situation depicted in Figure 21. There 1233 node C runs an increasing-SPF and a decreasing-SPF The increasing-SPF 1234 reaches D, E and R and the decreasing-SPF reaches B, A and R. So 1235 towards E the increasing next-hop is D (it was reached though D), and 1236 the decreasing next-hop is B (since R was reached though B). Since 1237 both D and B, A and R will compute the next hops similarly, the 1238 packets will reach E. 1240 We have the next-hops towards F as well: since F is not ordered with 1241 respect to C, the MRT-Blue next-hop is the decreasing one towards R 1242 (which is B) and the MRT-Red next-hop is the increasing one towards R 1243 (which is D). Since B is ordered with F, it will find, for its MRT- 1244 Blue, a real increasing next-hop, so packet forwarded to B will get 1245 to F on path C-B-F. Similarly, D will have, for its MRT-Red, a real 1246 decreasing next-hop, and the packet will use path C-D-F. 1248 4.6.4. Generalizing for graph that isn't 2-connected 1250 If a graph isn't 2-connected, then the basic approach given in 1251 Section 4.6.3 needs some extensions to determine the appropriate MRT 1252 next-hops to use for destinations outside the computing router X's 1253 blocks. In order to find a pair of maximally redundant trees in that 1254 graph we need to find a pair of RTs in each of the blocks (the root 1255 of these trees will be discussed later), and combine them. 1257 When computing the MRT next-hops from a router X, there are three 1258 basic differences: 1260 1. Only nodes in a common block with X should be explored in the 1261 increasing-SPF and decreasing-SPF. 1263 2. Instead of using the GADAG root, X's local-root should be used. 1264 This has the following implications: 1266 a. The links from X's local-root should not be explored. 1268 b. If a node is explored in the outgoing SPF so Y >> X, then X's 1269 MRT-Red next-hops to reach Y uses X's MRT-Red next-hops to 1270 reach X's local-root and if Z << X, then X's MRT-Blue next- 1271 hops to reach Z uses X's MRT-Blue next-hops to reach X's 1272 local-root. 1274 c. If a node W in a common block with X was not reached in the 1275 increasing-SPF or decreasing-SPF, then W is unordered with 1276 respect to X. X's MRT-Blue next-hops to W are X's decreasing 1277 aka MRT-Red next-hops to X's local-root. X's MRT-Red next- 1278 hops to W are X's increasing aka Blue MRT next-hops to X's 1279 local-root. 1281 3. For nodes in different blocks, the next-hops must be inherited 1282 via the relevant cut-vertex. 1284 These are all captured in the detailed algorithm given in 1285 Section 4.6.5. 1287 4.6.5. Complete Algorithm to Compute MRT Next-Hops 1289 The complete algorithm to compute MRT Next-Hops for a particular 1290 router X is given in Figure 22. In addition to computing the MRT- 1291 Blue next-hops and MRT-Red next-hops used by X to reach each node Y, 1292 the algorithm also stores an "order_proxy", which is the proper cut- 1293 vertex to reach Y if it is outside the block, and which is used later 1294 in deciding whether the MRT-Blue or the MRT-Red can provide an 1295 acceptable alternate for a particular primary next-hop. 1297 In_Common_Block(x, y) 1298 if (((x.localroot is y.localroot) and (x.block_id is y.block_id)) 1299 or (x is y.localroot) or (y is x.localroot)) 1300 return true 1301 return false 1303 Store_Results(y, direction, spf_root, store_nhs) 1304 if direction is FORWARD 1305 y.higher = true 1306 if store_nhs 1307 y.blue_next_hops = y.next_hops 1308 if direction is REVERSE 1309 y.lower = true 1310 if store_nhs 1311 y.red_next_hops = y.next_hops 1313 SPF_No_Traverse_Root(spf_root, block_root, direction, store_nhs) 1314 Initialize spf_heap to empty 1315 Initialize nodes' spf_metric to infinity and next_hops to empty 1316 spf_root.spf_metric = 0 1317 insert(spf_heap, spf_root) 1318 while (spf_heap is not empty) 1319 min_node = remove_lowest(spf_heap) 1320 Store_Results(min_node, direction, spf_root, store_nhs) 1321 if ((min_node is spf_root) or (min_node is not block_root)) 1322 foreach interface intf of min_node 1323 if (((direction is FORWARD) and intf.OUTGOING) or 1324 ((direction is REVERSE) and intf.INCOMING) and 1325 In_Common_Block(spf_root, intf.remote_node)) 1326 path_metric = min_node.spf_metric + intf.metric 1327 if path_metric < intf.remote_node.spf_metric 1328 intf.remote_node.spf_metric = path_metric 1329 if min_node is spf_root 1330 intf.remote_node.next_hops = make_list(intf) 1331 else 1332 intf.remote_node.next_hops = min_node.next_hops 1333 insert_or_update(spf_heap, intf.remote_node) 1334 else if path_metric is intf.remote_node.spf_metric 1335 if min_node is spf_root 1336 add_to_list(intf.remote_node.next_hops, intf) 1337 else 1338 add_list_to_list(intf.remote_node.next_hops, 1339 min_node.next_hops) 1341 SetEdge(y) 1342 if y.blue_next_hops is empty and y.red_next_hops is empty 1343 if (y.local_root != y) { 1344 SetEdge(y.localroot) 1345 } 1346 y.blue_next_hops = y.localroot.blue_next_hops 1347 y.red_next_hops = y.localroot.red_next_hops 1348 y.order_proxy = y.localroot.order_proxy 1350 Compute_MRT_NextHops(x, root) 1351 foreach node y 1352 y.higher = y.lower = false 1353 clear y.red_next_hops and y.blue_next_hops 1354 y.order_proxy = y 1355 SPF_No_Traverse_Root(x, x.localroot, FORWARD, TRUE) 1356 SPF_No_Traverse_Root(x, x.localroot, REVERSE, TRUE) 1358 // red and blue next-hops are stored to x.localroot as different 1359 // paths are found via the SPF and reverse-SPF. 1360 // Similarly any nodes whose local-root is x will have their 1361 // red_next_hops and blue_next_hops already set. 1363 // Handle nodes in the same block that aren't the local-root 1364 foreach node y 1365 if (y.IN_MRT_ISLAND and (y is not x) and 1366 (y.localroot is x.localroot) and 1367 ((y is x.localroot) or (x is y.localroot) or 1368 (y.block_id is x.block_id))) 1369 if y.higher 1370 y.red_next_hops = x.localroot.red_next_hops 1371 else if y.lower 1372 y.blue_next_hops = x.localroot.blue_next_hops 1373 else 1374 y.blue_next_hops = x.localroot.red_next_hops 1375 y.red_next_hops = x.localroot.blue_next_hops 1377 // Inherit next-hops and order_proxies to other components 1378 if x is not root 1379 root.blue_next_hops = x.localroot.blue_next_hops 1380 root.red_next_hops = x.localroot.red_next_hops 1381 root.order_proxy = x.localroot 1382 foreach node y 1383 if (y is not root) and (y is not x) and y.IN_MRT_ISLAND 1384 SetEdge(y) 1386 max_block_id = 0 1387 Assign_Block_ID(root, max_block_id) 1388 Compute_MRT_NextHops(x, root) 1390 Figure 22 1392 4.7. Identify MRT alternates 1394 At this point, a computing router S knows its MRT-Blue next-hops and 1395 MRT-Red next-hops for each destination in the MRT Island. The 1396 primary next-hops along the SPT are also known. It remains to 1397 determine for each primary next-hop to a destination D, which of the 1398 MRTs avoids the primary next-hop node F. This computation depends 1399 upon data set in Compute_MRT_NextHops such as each node y's 1400 y.blue_next_hops, y.red_next_hops, y.order_proxy, y.higher, y.lower 1401 and topo_orders. Recall that any router knows only which are the 1402 nodes greater and lesser than itself, but it cannot decide the 1403 relation between any two given nodes easily; that is why we need 1404 topological ordering. 1406 For each primary next-hop node F to each destination D, S can call 1407 Select_Alternates(S, D, F, primary_intf) to determine whether to use 1408 the MRT-Blue next-hops as the alternate next-hop(s) for that primary 1409 next hop or to use the MRT-Red next-hops. The algorithm is given in 1410 Figure 23 and discussed afterwards. 1412 Select_Alternates_Internal(S, D, F, primary_intf, 1413 D_lower, D_higher, D_topo_order) 1415 //When D==F, we can do only link protection 1416 if ((D is F) or (D.order_proxy is F)) 1417 if an MRT doesn't use primary_intf 1418 indicate alternate is not node-protecting 1419 return that MRT color 1420 else // parallel links are cut-edge 1421 return AVOID_LINK_ON_BLUE 1423 if (D_lower and D_higher and F.lower and F.higher) 1424 if F.topo_order < D_topo_order 1425 return USE_RED 1426 else 1427 return USE_BLUE 1429 if (D_lower and D_higher) 1430 if F.higher 1431 return USE_RED 1432 else 1433 return USE_BLUE 1435 if (F.lower and F.higher) 1436 if D_lower 1437 return USE_RED 1438 else if D_higher 1439 return USE_BLUE 1440 else 1441 if primary_intf.OUTGOING and primary_intf.INCOMING 1442 return AVOID_LINK_ON_BLUE 1443 if primary_intf.OUTGOING is true 1444 return USE_BLUE 1445 if primary_intf.INCOMING is true 1446 return USE_RED 1448 if D_higher 1449 if F.higher 1450 if F.topo_order < D_topo_order 1451 return USE_RED 1452 else 1453 return USE_BLUE 1454 else if F.lower 1455 return USE_BLUE 1456 else 1457 // F and S are neighbors so either F << S or F >> S 1458 else if D_lower 1459 if F.higher 1460 return USE_RED 1461 else if F.lower 1462 if F.topo_order < D_topo_order 1463 return USE_RED 1464 else 1465 return USE_BLUE 1466 else 1467 // F and S are neighbors so either F << S or F >> S 1468 else // D and S not ordered 1469 if F.lower 1470 return USE_RED 1471 else if F.higher 1472 return USE_BLUE 1473 else 1474 // F and S are neighbors so either F << S or F >> S 1476 Select_Alternates(S, D, F, primary_intf) 1477 if D.order_proxy is not D 1478 D_lower = D.order_proxy.lower 1479 D_higher = D.order_proxy.higher 1480 D_topo_order = D.order_proxy.topo_order 1481 else 1482 D_lower = D.lower 1483 D_higher = D.higher 1484 D_topo_order = D.topo_order 1485 return Select_Alternates_Internal(S, D, F, primary_intf, 1486 D_lower, D_higher, D_topo_order) 1488 Figure 23 1490 If either D>>S>>F or D<>D (ii) F<D.topo_order, either case (i) or 1501 case (iii) holds true, which means that selecting the Blue next-hop 1502 is safe. Similarly, if F.topo_order>S, we 1512 should use the Blue next-hop. 1514 Additionally, the cases where either F or D is ordered both higher 1515 and lower must be considered; this can happen when one is a block- 1516 root or its order_proxy is. If D is both higher and lower than S, 1517 then the MRT to use is the one that avoids F so if F is higher, then 1518 the MRT-Red should be used and if F is lower, then the MRT-Blue 1519 should be used; F and S must be ordered because they are neighbors. 1520 If F is both higher and lower, then if D is lower, using the MRT-Red 1521 to decrease reaches D and if D is higher, using the Blue MRT to 1522 increase reaches D; if D is unordered compared to S, then the 1523 situation is a bit more complicated. 1525 In the case where F< F, then use the MRT-Blue (decrease to avoid 1528 that link and then increase). If the link is directed S <- F, then 1529 use the MRT-Red (increase to avoid that link and then decrease). If 1530 the link is S <--> F, then the link must be a cut-link and there is 1531 no node-protecting alternate. If there are multiple links between S 1532 and F, then they can protect against each other; of course, in this 1533 situation, they are probably already ECMP. 1535 Finally, there is the case where D is also F. In this case, only link 1536 protection is possible. The MRT that doesn't use the indicated 1537 primary next-hop is used. If both MRTs use the primary next-hop, 1538 then the primary next-hop must be a cut-edge so either MRT could be 1539 used but the set of MRT next-hops must be pruned to avoid that 1540 primary next-hop. To indicate this case, Select_Alternates returns 1541 AVOID_LINK_ON_BLUE. 1543 As an example, consider the ADAG depicted in Figure 24 and first 1544 suppose that G is the source, D is the destination and H is the 1545 failed next-hop. Since D>>G, we need to compare H.topo_order and 1546 D.topo_order. Since D.topo_order>H.topo_order, D must be not smaller 1547 than H, so we should select the decreasing path towards the root. 1548 If, however, the destination were instead J, we must find that 1549 H.topo_order>J.topo_order, so we must choose the increasing Blue 1550 next-hop to J, which is I. In the case, when instead the destination 1551 is C, we find that we need to first decrease to avoid using H, so the 1552 Blue, first decreasing then increasing, path is selected. 1554 [E]<-[D]<-[H]<-[J] 1555 | ^ ^ ^ 1556 V | | | 1557 [R] [C] [G]->[I] 1558 | ^ ^ ^ 1559 V | | | 1560 [A]->[B]->[F]---| 1562 (a) 1563 a 2-connected graph 1565 Figure 24 1567 4.8. Finding FRR Next-Hops for Proxy-Nodes 1569 As discussed in Section 10.2 of 1570 [I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT- 1571 Blue and MRT-Red next-hops and MRT-FRR alternates for a named proxy- 1572 nodes. An example case is for a router that is not part of that 1573 local MRT Island, when there is only partial MRT support in the 1574 domain. 1576 A first incorrect and naive approach to handling proxy-nodes, which 1577 cannot be transited, is to simply add these proxy-nodes to the graph 1578 of the network and connect it to the routers through which the new 1579 proxy-node can be reached. Unfortunately, this can introduce some 1580 new ordering between the border routers connected to the new node 1581 which could result in routing MRT paths through the proxy-node. 1582 Thus, this naive approach would need to recompute GADAGs and redo 1583 SPTs for each proxy-node. 1585 Instead of adding the proxy-node to the original network graph, each 1586 individual proxy-node can be individually added to the GADAG. The 1587 proxy-node is connected to at most two nodes in the GADAG. 1588 Section 10.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] defines how the 1589 proxy-node attachments MUST be determined. The degenerate case where 1590 the proxy-node is attached to only one node in the GADAG is trivial 1591 as all needed information can be derived from that attachment node; 1592 if there are different interfaces, then some can be assigned to MRT- 1593 Red and others to MRT_Blue. 1595 Now, consider the proxy-node that is attached to exactly two nodes in 1596 the GADAG. Let the order_proxies of these nodes be A and B. Let the 1597 current node, where next-hop is just being calculated, be S. If one 1598 of these two nodes A and B is the local root of S, let A=S.local_root 1599 and the other one be B. Otherwise, let A.topo_order < B.topo_order. 1601 A valid GADAG was constructed. Instead doing an increasing-SPF and a 1602 decreasing-SPF to find ordering for the proxy-nodes, the following 1603 simple rules, providing the same result, can be used independently 1604 for each different proxy-node. For the following rules, let 1605 X=A.local_root, and if A is the local root, let that be strictly 1606 lower than any other node. Always take the first rule that matches. 1608 Rule Condition Blue NH Red NH Notes 1609 1 S=X Blue to A Red to B 1610 2 S<>B Blue to R Red to B 1612 4 A<> S, 1694 the computing router, MUST be one or more nodes, T, whose topo_order 1695 is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y 1696 is T. Similarly, the MRT-Red next-hops MUST be have a topo_order in 1697 the interval [R-small.topo_order, X.topo_order] or [Y.topo_order, 1698 R-big.topo_order]. 1700 Implementations SHOULD implement the Select_Alternates() function to 1701 pick an MRT-FRR alternate. 1703 In a future version, this section will include pseudo-code describing 1704 the full code path through the pseudo-code given earlier in the 1705 draft. 1707 6. Algorithm Alternatives and Evaluation 1709 This specification defines the MRT Lowpoint Algorithm, which is one 1710 option among several possible MRT algorithms. Other alternatives are 1711 described in the appendices. 1713 In addition, it is possible to calculate Destination-Rooted GADAG, 1714 where for each destination, a GADAG rooted at that destination is 1715 computed. Then a router can compute the blue MRT and red MRT next- 1716 hops to that destination. Building GADAGs per destination is 1717 computationally more expensive, but may give somewhat shorter 1718 alternate paths. It may be useful for live-live multicast along 1719 MRTs. 1721 6.1. Algorithm Evaluation 1723 This section compares MRT and remote LFA for IP Fast Reroute in 19 1724 service provider network topologies, focusing on coverage and 1725 alternate path length. Figure 26 shows the node-protecting coverage 1726 provided by local LFA (LLFA), remote LFA (RLFA), and MRT against 1727 different failure scenarios in these topologies. The coverage values 1728 are calculated as the percentage of source-destination pairs 1729 protected by the given IPFRR method relative to those protectable by 1730 optimal routing, against the same failure modes. More details on 1731 alternate selection policies used for this analysis are described 1732 later in this section. 1734 +------------+-----------------------------+ 1735 | Topology | percentage of failure | 1736 | | scenarios covered by | 1737 | | IPFRR method | 1738 | |-----------------------------+ 1739 | | NP_LLFA | NP_RLFA | MRT | 1740 +------------+---------+---------+---------+ 1741 | T201 | 37 | 90 | 100 | 1742 | T202 | 73 | 83 | 100 | 1743 | T203 | 51 | 80 | 100 | 1744 | T204 | 55 | 81 | 100 | 1745 | T205 | 92 | 93 | 100 | 1746 | T206 | 71 | 74 | 100 | 1747 | T207 | 57 | 74 | 100 | 1748 | T208 | 66 | 81 | 100 | 1749 | T209 | 79 | 79 | 100 | 1750 | T210 | 95 | 98 | 100 | 1751 | T211 | 68 | 71 | 100 | 1752 | T212 | 59 | 63 | 100 | 1753 | T213 | 84 | 84 | 100 | 1754 | T214 | 68 | 78 | 100 | 1755 | T215 | 84 | 88 | 100 | 1756 | T216 | 43 | 59 | 100 | 1757 | T217 | 78 | 88 | 100 | 1758 | T218 | 72 | 75 | 100 | 1759 | T219 | 78 | 84 | 100 | 1760 +------------+---------+---------+---------+ 1762 Figure 26 1764 For the topologies analyzed here, LLFA is able to provide node- 1765 protecting coverage ranging from 37% to 95% of the source-destination 1766 pairs, as seen in the column labeled NP_LLFA. The use of RLFA in 1767 addition to LLFA is generally able to increase the node-protecting 1768 coverage. The percentage of node-protecting coverage with RLFA is 1769 provided in the column labeled NP_RLFA, ranges from 59% to 98% for 1770 these topologies. The node-protecting coverage provided by MRT is 1771 100% since MRT is able to provide protection for any source- 1772 destination pair for which a path still exists after the failure. 1774 We would also like to measure the quality of the alternate paths 1775 produced by these different IPFRR methods. An obvious approach is to 1776 take an average of the alternate path costs over all source- 1777 destination pairs and failure modes. However, this presents a 1778 problem, which we will illustrate by presenting an example of results 1779 for one topology using this approach ( Figure 27). In this table, 1780 the average relative path length is the alternate path length for the 1781 IPFRR method divided by the optimal alternate path length, averaged 1782 over all source-destination pairs and failure modes. The first three 1783 columns of data in the table give the path length calculated from the 1784 sum of IGP metrics of the links in the path. The results for 1785 topology T208 show that the metric-based path lengths for NP_LLFA and 1786 NP_RLFA alternates are on average 78 and 66 times longer than the 1787 path lengths for optimal alternates. The metric-based path lengths 1788 for MRT alternates are on average 14 times longer than for optimal 1789 alternates. 1791 +--------+------------------------------------------------+ 1792 | | average relative alternate path length | 1793 | |-----------------------+------------------------+ 1794 |Topology| IGP metric | hopcount | 1795 | |-----------------------+------------------------+ 1796 | |NP_LLFA |NP_RLFA | MRT |NP_LLFA |NP_RLFA | MRT | 1797 +--------+--------+--------+-----+--------+--------+------+ 1798 | T208 | 78.2 | 66.0 | 13.6| 0.99 | 1.01 | 1.32 | 1799 +--------+--------+--------+-----+--------+--------+------+ 1801 Figure 27 1803 The network topology represented by T208 uses values of 10, 100, and 1804 1000 as IGP costs, so small deviations from the optimal alternate 1805 path can result in large differences in relative path length. LLFA, 1806 RLFA, and MRT all allow for at least one hop in the alterate path to 1807 be chosen independent of the cost of the link. This can easily 1808 result in an alternate using a link with cost 1000, which introduces 1809 noise into the path length measurement. In the case of T208, the 1810 adverse effects of using metric-based path lengths is obvious. 1811 However, we have observed that the metric-based path length 1812 introduces noise into alternate path length measurements in several 1813 other topologies as well. For this reason, we have opted to measure 1814 the alternate path length using hopcount. While IGP metrics may be 1815 adjusted by the network operator for a number of reasons (e.g. 1816 traffic engineering), the hopcount is a fairly stable measurement of 1817 path length. As shown in the last three columns of Figure 27, the 1818 hopcount-based alternate path lengths for topology T208 are fairly 1819 well-behaved. 1821 Figure 28, Figure 29, Figure 30, and Figure 31 present the hopcount- 1822 based path length results for the 19 topologies examined. The 1823 topologies in the four tables are grouped based on the size of the 1824 topologies, as measured by the number of nodes, with Figure 28 having 1825 the smallest topologies and Figure 31 having the largest topologies. 1826 Instead of trying to represent the path lengths of a large set of 1827 alternates with a single number, we have chosen to present a 1828 histogram of the path lengths for each IPFRR method and alternate 1829 selection policy studied. The first eight colums of data represent 1830 the percentage of failure scenarios protected by an alternate N hops 1831 longer than the primary path, with the first column representing an 1832 alternate 0 or 1 hops longer than the primary path, all the way up 1833 through the eighth column respresenting an alternate 14 or 15 hops 1834 longer than the primary path. The last column in the table gives the 1835 percentage of failure scenarios for which there is no alternate less 1836 than 16 hops longer than the primary path. In the case of LLFA and 1837 RLFA, this category includes failure scenarios for which no alternate 1838 was found. 1840 For each topology, the first row (labeled OPTIMAL) is the 1841 distribution of the number of hops in excess of the primary path 1842 hopcount for optimally routed alternates. (The optimal routing was 1843 done with respect to IGP metrics, as opposed to hopcount.) The 1844 second row(labeled NP_LLFA) is the distribution of the extra hops for 1845 node-protecting LLFA. The third row (labeled NP_LLFA_THEN_NP_RLFA) 1846 is the hopcount distribution when one adds node-protecting RLFA to 1847 increase the coverage. The alternate selection policy used here 1848 first tries to find a node-protecting LLFA. If that does not exist, 1849 then it tries to find an RLFA, and checks if it is node-protecting. 1850 Comparing the hopcount distribution for RLFA and LLFA across these 1851 topologies, one can see how the coverage is increased at the expense 1852 of using longer alternates. It is also worth noting that while 1853 superficially LLFA and RLFA appear to have better hopcount 1854 distributions than OPTIMAL, the presence of entries in the last 1855 column (no alternate < 16) mainly represent failure scenarios that 1856 are not protected, for which the hopcount is effectively infinite. 1858 The fourth and fifth rows of each topology show the hopcount 1859 distributions for two alternate selection policies using MRT 1860 alternates. The policy represented by the label 1861 NP_LLFA_THEN_MRT_LOWPOINT will first use a node-protecting LLFA. If 1862 a node-protecting LLFA does not exist, then it will use an MRT 1863 alternate. The policy represented by the label MRT_LOWPOINT instead 1864 will use the MRT alternate even if a node-protecting LLFA exists. 1865 One can see from the data that combining node-protecting LLFA with 1866 MRT results in a significant shortening of the alternate hopcount 1867 distribution. 1869 +-------------------------------------------------------------------+ 1870 | | percentage of failure scenarios | 1871 | Topology name | protected by an alternate N hops | 1872 | and | longer than the primary path | 1873 | alternate selection +------------------------------------+ 1874 | policy evaluated | | | | | | | | | no | 1875 | | | | | | |10 |12 |14 | alt| 1876 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 1877 +------------------------------+---+---+---+---+---+---+---+---+----+ 1878 | T201(avg primary hops=3.5) | | | | | | | | | | 1879 | OPTIMAL | 37| 37| 20| 3| 3| | | | | 1880 | NP_LLFA | 37| | | | | | | | 63| 1881 | NP_LLFA_THEN_NP_RLFA | 37| 34| 19| | | | | | 10| 1882 | NP_LLFA_THEN_MRT_LOWPOINT | 37| 33| 21| 6| 3| | | | | 1883 | MRT_LOWPOINT | 33| 36| 23| 6| 3| | | | | 1884 +------------------------------+---+---+---+---+---+---+---+---+----+ 1885 | T202(avg primary hops=4.8) | | | | | | | | | | 1886 | OPTIMAL | 90| 9| | | | | | | | 1887 | NP_LLFA | 71| 2| | | | | | | 27| 1888 | NP_LLFA_THEN_NP_RLFA | 78| 5| | | | | | | 17| 1889 | NP_LLFA_THEN_MRT_LOWPOINT | 80| 12| 5| 2| 1| | | | | 1890 | MRT_LOWPOINT_ONLY | 48| 29| 13| 7| 2| 1| | | | 1891 +------------------------------+---+---+---+---+---+---+---+---+----+ 1892 | T203(avg primary hops=4.1) | | | | | | | | | | 1893 | OPTIMAL | 36| 37| 21| 4| 2| | | | | 1894 | NP_LLFA | 34| 15| 3| | | | | | 49| 1895 | NP_LLFA_THEN_NP_RLFA | 35| 19| 22| 4| | | | | 20| 1896 | NP_LLFA_THEN_MRT_LOWPOINT | 36| 35| 22| 5| 2| | | | | 1897 | MRT_LOWPOINT_ONLY | 31| 35| 26| 7| 2| | | | | 1898 +------------------------------+---+---+---+---+---+---+---+---+----+ 1899 | T204(avg primary hops=3.7) | | | | | | | | | | 1900 | OPTIMAL | 76| 20| 3| 1| | | | | | 1901 | NP_LLFA | 54| 1| | | | | | | 45| 1902 | NP_LLFA_THEN_NP_RLFA | 67| 10| 4| | | | | | 19| 1903 | NP_LLFA_THEN_MRT_LOWPOINT | 70| 18| 8| 3| 1| | | | | 1904 | MRT_LOWPOINT_ONLY | 58| 27| 11| 3| 1| | | | | 1905 +------------------------------+---+---+---+---+---+---+---+---+----+ 1906 | T205(avg primary hops=3.4) | | | | | | | | | | 1907 | OPTIMAL | 92| 8| | | | | | | | 1908 | NP_LLFA | 89| 3| | | | | | | 8| 1909 | NP_LLFA_THEN_NP_RLFA | 90| 4| | | | | | | 7| 1910 | NP_LLFA_THEN_MRT_LOWPOINT | 91| 9| | | | | | | | 1911 | MRT_LOWPOINT_ONLY | 62| 33| 5| 1| | | | | | 1912 +------------------------------+---+---+---+---+---+---+---+---+----+ 1914 Figure 28 1916 +-------------------------------------------------------------------+ 1917 | | percentage of failure scenarios | 1918 | Topology name | protected by an alternate N hops | 1919 | and | longer than the primary path | 1920 | alternate selection +------------------------------------+ 1921 | policy evaluated | | | | | | | | | no | 1922 | | | | | | |10 |12 |14 | alt| 1923 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 1924 +------------------------------+---+---+---+---+---+---+---+---+----+ 1925 | T206(avg primary hops=3.7) | | | | | | | | | | 1926 | OPTIMAL | 63| 30| 7| | | | | | | 1927 | NP_LLFA | 60| 9| 1| | | | | | 29| 1928 | NP_LLFA_THEN_NP_RLFA | 60| 13| 1| | | | | | 26| 1929 | NP_LLFA_THEN_MRT_LOWPOINT | 64| 29| 7| | | | | | | 1930 | MRT_LOWPOINT | 55| 32| 13| | | | | | | 1931 +------------------------------+---+---+---+---+---+---+---+---+----+ 1932 | T207(avg primary hops=3.9) | | | | | | | | | | 1933 | OPTIMAL | 71| 24| 5| 1| | | | | | 1934 | NP_LLFA | 55| 2| | | | | | | 43| 1935 | NP_LLFA_THEN_NP_RLFA | 63| 10| | | | | | | 26| 1936 | NP_LLFA_THEN_MRT_LOWPOINT | 70| 20| 7| 2| 1| | | | | 1937 | MRT_LOWPOINT_ONLY | 57| 29| 11| 3| 1| | | | | 1938 +------------------------------+---+---+---+---+---+---+---+---+----+ 1939 | T208(avg primary hops=4.6) | | | | | | | | | | 1940 | OPTIMAL | 58| 28| 12| 2| 1| | | | | 1941 | NP_LLFA | 53| 11| 3| | | | | | 34| 1942 | NP_LLFA_THEN_NP_RLFA | 56| 17| 7| 1| | | | | 19| 1943 | NP_LLFA_THEN_MRT_LOWPOINT | 58| 19| 10| 7| 3| 1| | | | 1944 | MRT_LOWPOINT_ONLY | 34| 24| 21| 13| 6| 2| 1| | | 1945 +------------------------------+---+---+---+---+---+---+---+---+----+ 1946 | T209(avg primary hops=3.6) | | | | | | | | | | 1947 | OPTIMAL | 85| 14| 1| | | | | | | 1948 | NP_LLFA | 79| | | | | | | | 21| 1949 | NP_LLFA_THEN_NP_RLFA | 79| | | | | | | | 21| 1950 | NP_LLFA_THEN_MRT_LOWPOINT | 82| 15| 2| | | | | | | 1951 | MRT_LOWPOINT_ONLY | 63| 29| 8| | | | | | | 1952 +------------------------------+---+---+---+---+---+---+---+---+----+ 1953 | T210(avg primary hops=2.5) | | | | | | | | | | 1954 | OPTIMAL | 95| 4| 1| | | | | | | 1955 | NP_LLFA | 94| 1| | | | | | | 5| 1956 | NP_LLFA_THEN_NP_RLFA | 94| 3| 1| | | | | | 2| 1957 | NP_LLFA_THEN_MRT_LOWPOINT | 95| 4| 1| | | | | | | 1958 | MRT_LOWPOINT_ONLY | 91| 6| 2| | | | | | | 1959 +------------------------------+---+---+---+---+---+---+---+---+----+ 1961 Figure 29 1963 +-------------------------------------------------------------------+ 1964 | | percentage of failure scenarios | 1965 | Topology name | protected by an alternate N hops | 1966 | and | longer than the primary path | 1967 | alternate selection +------------------------------------+ 1968 | policy evaluated | | | | | | | | | no | 1969 | | | | | | |10 |12 |14 | alt| 1970 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 1971 +------------------------------+---+---+---+---+---+---+---+---+----+ 1972 | T211(avg primary hops=3.3) | | | | | | | | | | 1973 | OPTIMAL | 88| 11| | | | | | | | 1974 | NP_LLFA | 66| 1| | | | | | | 32| 1975 | NP_LLFA_THEN_NP_RLFA | 68| 3| | | | | | | 29| 1976 | NP_LLFA_THEN_MRT_LOWPOINT | 88| 12| | | | | | | | 1977 | MRT_LOWPOINT | 85| 15| 1| | | | | | | 1978 +------------------------------+---+---+---+---+---+---+---+---+----+ 1979 | T212(avg primary hops=3.5) | | | | | | | | | | 1980 | OPTIMAL | 76| 23| 1| | | | | | | 1981 | NP_LLFA | 59| | | | | | | | 41| 1982 | NP_LLFA_THEN_NP_RLFA | 61| 1| 1| | | | | | 37| 1983 | NP_LLFA_THEN_MRT_LOWPOINT | 75| 24| 1| | | | | | | 1984 | MRT_LOWPOINT_ONLY | 66| 31| 3| | | | | | | 1985 +------------------------------+---+---+---+---+---+---+---+---+----+ 1986 | T213(avg primary hops=4.3) | | | | | | | | | | 1987 | OPTIMAL | 91| 9| | | | | | | | 1988 | NP_LLFA | 84| | | | | | | | 16| 1989 | NP_LLFA_THEN_NP_RLFA | 84| | | | | | | | 16| 1990 | NP_LLFA_THEN_MRT_LOWPOINT | 89| 10| 1| | | | | | | 1991 | MRT_LOWPOINT_ONLY | 75| 24| 1| | | | | | | 1992 +------------------------------+---+---+---+---+---+---+---+---+----+ 1993 | T214(avg primary hops=5.8) | | | | | | | | | | 1994 | OPTIMAL | 71| 22| 5| 2| | | | | | 1995 | NP_LLFA | 58| 8| 1| 1| | | | | 32| 1996 | NP_LLFA_THEN_NP_RLFA | 61| 13| 3| 1| | | | | 22| 1997 | NP_LLFA_THEN_MRT_LOWPOINT | 66| 14| 7| 5| 3| 2| 1| 1| 1| 1998 | MRT_LOWPOINT_ONLY | 30| 20| 18| 12| 8| 4| 3| 2| 3| 1999 +------------------------------+---+---+---+---+---+---+---+---+----+ 2000 | T215(avg primary hops=4.8) | | | | | | | | | | 2001 | OPTIMAL | 73| 27| | | | | | | | 2002 | NP_LLFA | 73| 11| | | | | | | 16| 2003 | NP_LLFA_THEN_NP_RLFA | 73| 13| 2| | | | | | 12| 2004 | NP_LLFA_THEN_MRT_LOWPOINT | 74| 19| 3| 2| 1| 1| 1| | | 2005 | MRT_LOWPOINT_ONLY | 32| 31| 16| 12| 4| 3| 1| | | 2006 +------------------------------+---+---+---+---+---+---+---+---+----+ 2008 Figure 30 2010 +-------------------------------------------------------------------+ 2011 | | percentage of failure scenarios | 2012 | Topology name | protected by an alternate N hops | 2013 | and | longer than the primary path | 2014 | alternate selection +------------------------------------+ 2015 | policy evaluated | | | | | | | | | no | 2016 | | | | | | |10 |12 |14 | alt| 2017 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 2018 +------------------------------+---+---+---+---+---+---+---+---+----+ 2019 | T216(avg primary hops=5.2) | | | | | | | | | | 2020 | OPTIMAL | 60| 32| 7| 1| | | | | | 2021 | NP_LLFA | 39| 4| | | | | | | 57| 2022 | NP_LLFA_THEN_NP_RLFA | 46| 12| 2| | | | | | 41| 2023 | NP_LLFA_THEN_MRT_LOWPOINT | 48| 20| 12| 7| 5| 4| 2| 1| 1| 2024 | MRT_LOWPOINT | 28| 25| 18| 11| 7| 6| 3| 2| 1| 2025 +------------------------------+---+---+---+---+---+---+---+---+----+ 2026 | T217(avg primary hops=8.0) | | | | | | | | | | 2027 | OPTIMAL | 81| 13| 5| 1| | | | | | 2028 | NP_LLFA | 74| 3| 1| | | | | | 22| 2029 | NP_LLFA_THEN_NP_RLFA | 76| 8| 3| 1| | | | | 12| 2030 | NP_LLFA_THEN_MRT_LOWPOINT | 77| 7| 5| 4| 3| 2| 1| 1| | 2031 | MRT_LOWPOINT_ONLY | 25| 18| 18| 16| 12| 6| 3| 1| | 2032 +------------------------------+---+---+---+---+---+---+---+---+----+ 2033 | T218(avg primary hops=5.5) | | | | | | | | | | 2034 | OPTIMAL | 85| 14| 1| | | | | | | 2035 | NP_LLFA | 68| 3| | | | | | | 28| 2036 | NP_LLFA_THEN_NP_RLFA | 71| 4| | | | | | | 25| 2037 | NP_LLFA_THEN_MRT_LOWPOINT | 77| 12| 7| 4| 1| | | | | 2038 | MRT_LOWPOINT_ONLY | 37| 29| 21| 10| 3| 1| | | | 2039 +------------------------------+---+---+---+---+---+---+---+---+----+ 2040 | T219(avg primary hops=7.7) | | | | | | | | | | 2041 | OPTIMAL | 77| 15| 5| 1| 1| | | | | 2042 | NP_LLFA | 72| 5| | | | | | | 22| 2043 | NP_LLFA_THEN_NP_RLFA | 73| 8| 2| | | | | | 16| 2044 | NP_LLFA_THEN_MRT_LOWPOINT | 74| 8| 3| 3| 2| 2| 2| 2| 4| 2045 | MRT_LOWPOINT_ONLY | 19| 14| 15| 12| 10| 8| 7| 6| 10| 2046 +------------------------------+---+---+---+---+---+---+---+---+----+ 2048 Figure 31 2050 In the preceding analysis, the following procedure for selecting an 2051 RLFA was used. Nodes were ordered with respect to distance from the 2052 source and checked for membership in Q and P-space. The first node 2053 to satisfy this condition was selected as the RLFA. More 2054 sophisticated methods to select node-protecting RLFAs is an area of 2055 active research. 2057 The analysis presented above uses the MRT Lowpoint Algorithm defined 2058 in this specification with a common GADAG root. The particular 2059 choice of a common GADAG root is expected to affect the quality of 2060 the MRT alternate paths, with a more central common GADAG root 2061 resulting in shorter MRT alternate path lengths. For the analysis 2062 above, the GADAG root was chosen for each topology by calculating 2063 node centrality as the sum of costs of all shortest paths to and from 2064 a given node. The node with the lowest sum was chosen as the common 2065 GADAG root. In actual deployments, the common GADAG root would be 2066 chosen based on the GADAG Root Selection Priority advertised by each 2067 router, the values of which would be determined off-line. 2069 In order to measure how sensitive the MRT alternate path lengths are 2070 to the choice of common GADAG root, we performed the same analysis 2071 using different choices of GADAG root. All of the nodes in the 2072 network were ordered with respect to the node centrality as computed 2073 above. Nodes were chosen at the 0th, 25th, and 50th percentile with 2074 respect to the centrality ordering, with 0th percentile being the 2075 most central node. The distribution of alternate path lengths for 2076 those three choices of GADAG root are shown in Figure 32 for a subset 2077 of the 19 topologies (chosen arbitrarily). The third row for each 2078 topology (labeled MRT_LOWPOINT ( 0 percentile) ) reproduces the 2079 results presented above for MRT_LOWPOINT_ONLY. The fourth and fifth 2080 rows show the alternate path length distibution for the 25th and 50th 2081 percentile choice for GADAG root. One can see some impact on the 2082 path length distribution with the less central choice of GADAG root 2083 resulting in longer path lenghths. 2085 We also looked at the impact of MRT algorithm variant on the 2086 alternate path lengths. The first two rows for each topology present 2087 results of the same alternate path length distribution analysis for 2088 the SPF and Hybrid methods for computing the GADAG. These two 2089 methods are described in Appendix A and Appendix B. For three of the 2090 topologies in this subset (T201, T206, and T211), the use of SPF or 2091 Hybrid methods does not appear to provide a significant advantage 2092 over the Lowpoint method with respect to path length. Instead, the 2093 choice of GADAG root appears to have more impact on the path length. 2094 However, for two of the topologies in this subset(T216 and T219) and 2095 for this particular choice of GAGAG root, the use of the SPF method 2096 results in noticeably shorter alternate path lengths than the use of 2097 the Lowpoint or Hybrid methods. It remains to be determined if this 2098 effect applies generally across more topologies or is sensitive to 2099 choice of GADAG root. 2101 +-------------------------------------------------------------------+ 2102 | Topology name | percentage of failure scenarios | 2103 | | protected by an alternate N hops | 2104 | MRT algorithm variant | longer than the primary path | 2105 | +------------------------------------+ 2106 | (GADAG root | | | | | | | | | no | 2107 | centrality percentile) | | | | | |10 |12 |14 | alt| 2108 | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| 2109 +------------------------------+---+---+---+---+---+---+---+---+----+ 2110 | T201(avg primary hops=3.5) | | | | | | | | | | 2111 | MRT_HYBRID ( 0 percentile) | 33| 26| 23| 6| 3| | | | | 2112 | MRT_SPF ( 0 percentile) | 33| 36| 23| 6| 3| | | | | 2113 | MRT_LOWPOINT ( 0 percentile) | 33| 36| 23| 6| 3| | | | | 2114 | MRT_LOWPOINT (25 percentile) | 27| 29| 23| 11| 10| | | | | 2115 | MRT_LOWPOINT (50 percentile) | 27| 29| 23| 11| 10| | | | | 2116 +------------------------------+---+---+---+---+---+---+---+---+----+ 2117 | T206(avg primary hops=3.7) | | | | | | | | | | 2118 | MRT_HYBRID ( 0 percentile) | 50| 35| 13| 2| | | | | | 2119 | MRT_SPF ( 0 percentile) | 50| 35| 13| 2| | | | | | 2120 | MRT_LOWPOINT ( 0 percentile) | 55| 32| 13| | | | | | | 2121 | MRT_LOWPOINT (25 percentile) | 47| 25| 22| 6| | | | | | 2122 | MRT_LOWPOINT (50 percentile) | 38| 38| 14| 11| | | | | | 2123 +------------------------------+---+---+---+---+---+---+---+---+----+ 2124 | T211(avg primary hops=3.3) | | | | | | | | | | 2125 | MRT_HYBRID ( 0 percentile) | 86| 14| | | | | | | | 2126 | MRT_SPF ( 0 percentile) | 86| 14| | | | | | | | 2127 | MRT_LOWPOINT ( 0 percentile) | 85| 15| 1| | | | | | | 2128 | MRT_LOWPOINT (25 percentile) | 70| 25| 5| 1| | | | | | 2129 | MRT_LOWPOINT (50 percentile) | 80| 18| 2| | | | | | | 2130 +------------------------------+---+---+---+---+---+---+---+---+----+ 2131 | T216(avg primary hops=5.2) | | | | | | | | | | 2132 | MRT_HYBRID ( 0 percentile) | 23| 22| 18| 13| 10| 7| 4| 2| 2| 2133 | MRT_SPF ( 0 percentile) | 35| 32| 19| 9| 3| 1| | | | 2134 | MRT_LOWPOINT ( 0 percentile) | 28| 25| 18| 11| 7| 6| 3| 2| 1| 2135 | MRT_LOWPOINT (25 percentile) | 24| 20| 19| 16| 10| 6| 3| 1| | 2136 | MRT_LOWPOINT (50 percentile) | 19| 14| 13| 10| 8| 6| 5| 5| 10| 2137 +------------------------------+---+---+---+---+---+---+---+---+----+ 2138 | T219(avg primary hops=7.7) | | | | | | | | | | 2139 | MRT_HYBRID ( 0 percentile) | 20| 16| 13| 10| 7| 5| 5| 5| 3| 2140 | MRT_SPF ( 0 percentile) | 31| 23| 19| 12| 7| 4| 2| 1| | 2141 | MRT_LOWPOINT ( 0 percentile) | 19| 14| 15| 12| 10| 8| 7| 6| 10| 2142 | MRT_LOWPOINT (25 percentile) | 19| 14| 15| 13| 12| 10| 6| 5| 7| 2143 | MRT_LOWPOINT (50 percentile) | 19| 14| 14| 12| 11| 8| 6| 6| 10| 2144 +------------------------------+---+---+---+---+---+---+---+---+----+ 2146 Figure 32 2148 7. Algorithm Work to Be Done 2150 Broadcast Interfaces: The algorithm assumes that broadcast 2151 interfaces are already represented as pseudo-nodes in the network 2152 graph. Given maximal redundancy, one of the MRT will try to avoid 2153 both the pseudo-node and the next hop. The exact rules need to be 2154 fully specified. 2156 8. IANA Considerations 2158 This doument includes no request to IANA. 2160 9. Security Considerations 2162 This architecture is not currently believed to introduce new security 2163 concerns. 2165 10. References 2167 10.1. Normative References 2169 [I-D.ietf-rtgwg-mrt-frr-architecture] 2170 Atlas, A., Kebler, R., Envedi, G., Csaszar, A., Tantsura, 2171 J., Konstantynowicz, M., and R. White, "An Architecture 2172 for IP/LDP Fast-Reroute Using Maximally Redundant Trees", 2173 draft-ietf-rtgwg-mrt-frr-architecture-03 (work in 2174 progress), July 2013. 2176 10.2. Informative References 2178 [EnyediThesis] 2179 Enyedi, G., "Novel Algorithms for IP Fast Reroute", 2180 Department of Telecommunications and Media Informatics, 2181 Budapest University of Technology and Economics Ph.D. 2182 Thesis, February 2011, . 2186 [I-D.atlas-ospf-mrt] 2187 Atlas, A., Hegde, S., Chris, C., and J. Tantsura, "OSPF 2188 Extensions to Support Maximally Redundant Trees", draft- 2189 atlas-ospf-mrt-00 (work in progress), July 2013. 2191 [I-D.ietf-rtgwg-ipfrr-notvia-addresses] 2192 Bryant, S., Previdi, S., and M. Shand, "A Framework for IP 2193 and MPLS Fast Reroute Using Not-via Addresses", draft- 2194 ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress), 2195 May 2013. 2197 [I-D.ietf-rtgwg-lfa-manageability] 2198 Litkowski, S., Decraene, B., Filsfils, C., and K. Raza, 2199 "Operational management of Loop Free Alternates", draft- 2200 ietf-rtgwg-lfa-manageability-00 (work in progress), May 2201 2013. 2203 [I-D.ietf-rtgwg-remote-lfa] 2204 Bryant, S., Filsfils, C., Previdi, S., Shand, M., and S. 2205 Ning, "Remote LFA FRR", draft-ietf-rtgwg-remote-lfa-02 2206 (work in progress), May 2013. 2208 [Kahn_1962_topo_sort] 2209 Kahn, A., "Topological sorting of large networks", 2210 Communications of the ACM, Volume 5, Issue 11 , Nov 1962, 2211 . 2213 [LFARevisited] 2214 Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP 2215 Fast ReRoute: Loop Free Alternates Revisited", Proceedings 2216 of IEEE INFOCOM , 2011, . 2219 [LightweightNotVia] 2220 Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP 2221 Fast ReRoute: Lightweight Not-Via without Additional 2222 Addresses", Proceedings of IEEE INFOCOM , 2009, 2223 . 2225 [MRTLinear] 2226 Enyedi, G., Retvari, G., and A. Csaszar, "On Finding 2227 Maximally Redundant Trees in Strictly Linear Time", IEEE 2228 Symposium on Computers and Comunications (ISCC) , 2009, 2229 . 2232 [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. 2233 McPherson, "OSPF Stub Router Advertisement", RFC 3137, 2234 June 2001. 2236 [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast 2237 Reroute: Loop-Free Alternates", RFC 5286, September 2008. 2239 [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC 2240 5714, January 2010. 2242 [RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., 2243 Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free 2244 Alternate (LFA) Applicability in Service Provider (SP) 2245 Networks", RFC 6571, June 2012. 2247 Appendix A. Option 2: Computing GADAG using SPFs 2249 The basic idea in this option is to use slightly-modified SPF 2250 computations to find ears. In every block, an SPF computation is 2251 first done to find a cycle from the local root and then SPF 2252 computations in that block find ears until there are no more 2253 interfaces to be explored. The used result from the SPF computation 2254 is the path of interfaces indicated by following the previous hops 2255 from the mininized IN_GADAG node back to the SPF root. 2257 To do this, first all cut-vertices must be identified and local-roots 2258 assigned as specified in Figure 12. 2260 The slight modifications to the SPF are as follows. The root of the 2261 block is referred to as the block-root; it is either the GADAG root 2262 or a cut-vertex. 2264 a. The SPF is rooted at a neighbor x of an IN_GADAG node y. All 2265 links between y and x are marked as TEMP_UNUSABLE. They should 2266 not be used during the SPF computation. 2268 b. If y is not the block-root, then it is marked TEMP_UNUSABLE. It 2269 should not be used during the SPF computation. This prevents 2270 ears from starting and ending at the same node and avoids cycles; 2271 the exception is because cycles to/from the block-root are 2272 acceptable and expected. 2274 c. Do not explore links to nodes whose local-root is not the block- 2275 root. This keeps the SPF confined to the particular block. 2277 d. Terminate when the first IN_GADAG node z is minimized. 2279 e. Respect the existing directions (e.g. INCOMING, OUTGOING, 2280 UNDIRECTED) already specified for each interface. 2282 Mod_SPF(spf_root, block_root) 2283 Initialize spf_heap to empty 2284 Initialize nodes' spf_metric to infinity 2285 spf_root.spf_metric = 0 2286 insert(spf_heap, spf_root) 2287 found_in_gadag = false 2288 while (spf_heap is not empty) and (found_in_gadag is false) 2289 min_node = remove_lowest(spf_heap) 2290 if min_node.IN_GADAG is true 2291 found_in_gadag = true 2292 else 2293 foreach interface intf of min_node 2294 if ((intf.OUTGOING or intf.UNDIRECTED) and 2295 ((intf.remote_node.localroot is block_root) or 2296 (intf.remote_node is block_root)) and 2297 (intf.remote_node is not TEMP_UNUSABLE) and 2298 (intf is not TEMP_UNUSABLE)) 2299 path_metric = min_node.spf_metric + intf.metric 2300 if path_metric < intf.remote_node.spf_metric 2301 intf.remote_node.spf_metric = path_metric 2302 intf.remote_node.spf_prev_intf = intf 2303 insert_or_update(spf_heap, intf.remote_node) 2304 return min_node 2306 SPF_for_Ear(cand_intf.local_node,cand_intf.remote_node, block_root, 2307 method) 2308 Mark all interfaces between cand_intf.remote_node 2309 and cand_intf.local_node as TEMP_UNUSABLE 2310 if cand_intf.local_node is not block_root 2311 Mark cand_intf.local_node as TEMP_UNUSABLE 2312 Initialize ear_list to empty 2313 end_ear = Mod_SPF(spf_root, block_root) 2314 y = end_ear.spf_prev_hop 2315 while y.local_node is not spf_root 2316 add_to_list_start(ear_list, y) 2317 y.local_node.IN_GADAG = true 2318 y = y.local_node.spf_prev_intf 2319 if(method is not hybrid) 2320 Set_Ear_Direction(ear_list, cand_intf.local_node, 2321 end_ear,block_root) 2322 Clear TEMP_UNUSABLE from all interfaces between 2323 cand_intf.remote_node and cand_intf.local_node 2324 Clear TEMP_UNUSABLE from cand_intf.local_node 2325 return end_ear 2327 Figure 33: Modified SPF for GADAG computation 2329 Assume that an ear is found by going from y to x and then running an 2330 SPF that terminates by minimizing z (e.g. y<->x...q<->z). Now it is 2331 necessary to determine the direction of the ear; if y << z, then the 2332 path should be y->x...q->z but if y >> z, then the path should be 2333 y<-x...q<-z. In Section 4.4, the same problem was handled by finding 2334 all ears that started at a node before looking at ears starting at 2335 nodes higher in the partial order. In this algorithm, using that 2336 approach could mean that new ears aren't added in order of their 2337 total cost since all ears connected to a node would need to be found 2338 before additional nodes could be found. 2340 The alternative is to track the order relationship of each node with 2341 respect to every other node. This can be accomplished by maintaining 2342 two sets of nodes at each node. The first set, Higher_Nodes, 2343 contains all nodes that are known to be ordered above the node. The 2344 second set, Lower_Nodes, contains all nodes that are known to be 2345 ordered below the node. This is the approach used in this algorithm. 2347 Set_Ear_Direction(ear_list, end_a, end_b, block_root) 2348 // Default of A_TO_B for the following cases: 2349 // (a) end_a and end_b are the same (root) 2350 // or (b) end_a is in end_b's Lower Nodes 2351 // or (c) end_a and end_b were unordered with respect to each 2352 // other 2353 direction = A_TO_B 2354 if (end_b is block_root) and (end_a is not end_b) 2355 direction = B_TO_A 2356 else if end_a is in end_b.Higher_Nodes 2357 direction = B_TO_A 2358 if direction is B_TO_A 2359 foreach interface i in ear_list 2360 i.UNDIRECTED = false 2361 i.INCOMING = true 2362 i.remote_intf.UNDIRECTED = false 2363 i.remote_intf.OUTGOING = true 2364 else 2365 foreach interface i in ear_list 2366 i.UNDIRECTED = false 2367 i.OUTGOING = true 2368 i.remote_intf.UNDIRECTED = false 2369 i.remote_intf.INCOMING = true 2370 if end_a is end_b 2371 return 2372 // Next, update all nodes' Lower_Nodes and Higher_Nodes 2373 if (end_a is in end_b.Higher_Nodes) 2374 foreach node x where x.localroot is block_root 2375 if end_a is in x.Lower_Nodes 2376 foreach interface i in ear_list 2377 add i.remote_node to x.Lower_Nodes 2378 if end_b is in x.Higher_Nodes 2379 foreach interface i in ear_list 2380 add i.local_node to x.Higher_Nodes 2382 else 2383 foreach node x where x.localroot is block_root 2384 if end_b is in x.Lower_Nodes 2385 foreach interface i in ear_list 2386 add i.local_node to x.Lower_Nodes 2387 if end_a is in x.Higher_Nodes 2388 foreach interface i in ear_list 2389 add i.remote_node to x.Higher_Nodes 2391 Figure 34: Algorithm to assign links of an ear direction 2393 A goal of the algorithm is to find the shortest cycles and ears. An 2394 ear is started by going to a neighbor x of an IN_GADAG node y. The 2395 path from x to an IN_GADAG node is minimal, since it is computed via 2396 SPF. Since a shortest path is made of shortest paths, to find the 2397 shortest ears requires reaching from the set of IN_GADAG nodes to the 2398 closest node that isn't IN_GADAG. Therefore, an ordered tree is 2399 maintained of interfaces that could be explored from the IN_GADAG 2400 nodes. The interfaces are ordered by their characteristics of 2401 metric, local loopback address, remote loopback address, and ifindex, 2402 as in the algorithm previously described in Figure 14. 2404 The algorithm ignores interfaces picked from the ordered tree that 2405 belong to the block root if the block in which the interface is 2406 present already has an ear that has been computed. This is necessary 2407 since we allow at most one incoming interface to a block root in each 2408 block. This requirement stems from the way next-hops are computed as 2409 will be seen in Section 4.6. After any ear gets computed, we 2410 traverse the newly added nodes to the GADAG and insert interfaces 2411 whose far end is not yet on the GADAG to the ordered tree for later 2412 processing. 2414 Finally, cut-edges are a special case because there is no point in 2415 doing an SPF on a block of 2 nodes. The algorithm identifies cut- 2416 edges simply as links where both ends of the link are cut-vertices. 2417 Cut-edges can simply be added to the GADAG with both OUTGOING and 2418 INCOMING specified on their interfaces. 2420 add_eligible_interfaces_of_node(ordered_intfs_tree,node) 2421 for each interface of node 2422 if intf.remote_node.IN_GADAG is false 2423 insert(intf,ordered_intfs_tree) 2425 check_if_block_has_ear(x,block_id) 2426 block_has_ear = false 2427 for all interfaces of x 2428 if (intf.remote_node.block_id == block_id) && 2429 (intf.remote_node.IN_GADAG is true) 2430 block_has_ear = true 2431 return block_has_ear 2433 Construct_GADAG_via_SPF(topology, root) 2434 Compute_Localroot (root,root) 2435 Assign_Block_ID(root,0) 2436 root.IN_GADAG = true 2437 add_eligible_interfaces_of_node(ordered_intfs_tree,root) 2438 while ordered_intfs_tree is not empty 2439 cand_intf = remove_lowest(ordered_intfs_tree) 2440 if cand_intf.remote_node.IN_GADAG is false 2441 if L(cand_intf.remote_node) == D(cand_intf.remote_node) 2442 // Special case for cut-edges 2443 cand_intf.UNDIRECTED = false 2444 cand_intf.remote_intf.UNDIRECTED = false 2445 cand_intf.OUTGOING = true 2446 cand_intf.INCOMING = true 2447 cand_intf.remote_intf.OUTGOING = true 2448 cand_intf.remote_intf.INCOMING = true 2449 cand_intf.remote_node.IN_GADAG = true 2450 add_eligible_interfaces_of_node( 2451 ordered_intfs_tree,cand_intf.remote_node) 2452 else 2453 if (cand_intf.remote_node.local_root == 2454 cand_intf.local_node) && 2455 check_if_block_has_ear 2456 (cand_intf.local_node, 2457 cand_intf.remote_node.block_id)) 2458 /* Skip the interface since the block root 2459 already has an incoming interface in the 2460 block */ 2461 else 2462 ear_end = SPF_for_Ear(cand_intf.local_node, 2463 cand_intf.remote_node, 2464 cand_intf.remote_node.localroot, 2465 SPF method) 2466 y = ear_end.spf_prev_hop 2467 while y.local_node is not cand_intf.local_node 2468 add_eligible_interfaces_of_node( 2469 ordered_intfs_tree, 2470 y.local_node) 2471 y = y.local_node.spf_prev_intf 2473 Figure 35: SPF-based GADAG algorithm 2475 Appendix B. Option 3: Computing GADAG using a hybrid method 2476 In this option, the idea is to combine the salient features of the 2477 above two options. To this end, we process nodes as they get added 2478 to the GADAG just like in the lowpoint inheritance by maintaining a 2479 stack of nodes. This ensures that we do not need to maintain lower 2480 and higher sets at each node to ascertain ear directions since the 2481 ears will always be directed from the node being processed towards 2482 the end of the ear. To compute the ear however, we resort to an SPF 2483 to have the possibility of better ears (path lentghs) thus giving 2484 more flexibility than the restricted use of lowpoint/dfs parents. 2486 Regarding ears involving a block root, unlike the SPF method which 2487 ignored interfaces of the block root after the first ear, in the 2488 hybrid method we would have to process all interfaces of the block 2489 root before moving on to other nodes in the block since the direction 2490 of an ear is pre-determined. Thus, whenever the block already has an 2491 ear computed, and we are processing an interface of the block root, 2492 we mark the block root as unusable before the SPF run that computes 2493 the ear. This ensures that the SPF terminates at some node other 2494 than the block-root. This in turn guarantees that the block-root has 2495 only one incoming interface in each block, which is necessary for 2496 correctly computing the next-hops on the GADAG. 2498 As in the SPF gadag, bridge ears are handled as a special case. 2500 The entire algorithm is shown below in Figure 36 2502 find_spf_stack_ear(stack, x, y, xy_intf, block_root) 2503 if L(y) == D(y) 2504 // Special case for cut-edges 2505 xy_intf.UNDIRECTED = false 2506 xy_intf.remote_intf.UNDIRECTED = false 2507 xy_intf.OUTGOING = true 2508 xy_intf.INCOMING = true 2509 xy_intf.remote_intf.OUTGOING = true 2510 xy_intf.remote_intf.INCOMING = true 2511 xy_intf.remote_node.IN_GADAG = true 2512 push y onto stack 2513 return 2514 else 2515 if (y.local_root == x) && 2516 check_if_block_has_ear(x,y.block_id) 2517 //Avoid the block root during the SPF 2518 Mark x as TEMP_UNUSABLE 2519 end_ear = SPF_for_Ear(x,y,block_root,hybrid) 2520 If x was set as TEMP_UNUSABLE, clear it 2521 cur = end_ear 2522 while (cur != y) 2523 intf = cur.spf_prev_hop 2524 prev = intf.local_node 2525 intf.UNDIRECTED = false 2526 intf.remote_intf.UNDIRECTED = false 2527 intf.OUTGOING = true 2528 intf.remote_intf.INCOMING = true 2529 push prev onto stack 2530 cur = prev 2531 xy_intf.UNDIRECTED = false 2532 xy_intf.remote_intf.UNDIRECTED = false 2533 xy_intf.OUTGOING = true 2534 xy_intf.remote_intf.INCOMING = true 2535 return 2537 Construct_GADAG_via_hybrid(topology,root) 2538 Compute_Localroot (root,root) 2539 Assign_Block_ID(root,0) 2540 root.IN_GADAG = true 2541 Initialize Stack to empty 2542 push root onto Stack 2543 while (Stack is not empty) 2544 x = pop(Stack) 2545 for each interface intf of x 2546 y = intf.remote_node 2547 if y.IN_GADAG is false 2548 find_spf_stack_ear(stack, x, y, intf, y.block_root) 2550 Figure 36: Hybrid GADAG algorithm 2552 Authors' Addresses 2554 Gabor Sandor Enyedi (editor) 2555 Ericsson 2556 Konyves Kalman krt 11 2557 Budapest 1097 2558 Hungary 2560 Email: Gabor.Sandor.Enyedi@ericsson.com 2562 Andras Csaszar 2563 Ericsson 2564 Konyves Kalman krt 11 2565 Budapest 1097 2566 Hungary 2568 Email: Andras.Csaszar@ericsson.com 2569 Alia Atlas (editor) 2570 Juniper Networks 2571 10 Technology Park Drive 2572 Westford, MA 01886 2573 USA 2575 Email: akatlas@juniper.net 2577 Chris Bowers 2578 Juniper Networks 2579 1194 N. Mathilda Ave. 2580 Sunnyvale, CA 94089 2581 USA 2583 Email: cbowers@juniper.net 2585 Abishek Gopalan 2586 University of Arizona 2587 1230 E Speedway Blvd. 2588 Tucson, AZ 85721 2589 USA 2591 Email: abishek@ece.arizona.edu