idnits 2.17.1 draft-enyedi-rtgwg-mrt-frr-algorithm-01.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 25 instances of lines with non-RFC2606-compliant FQDNs in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 12, 2012) is 4421 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'R' is mentioned on line 1802, but not defined == Missing Reference: 'F' is mentioned on line 1789, but not defined == Missing Reference: 'C' is mentioned on line 1789, but not defined == Missing Reference: 'G' is mentioned on line 1647, but not defined == Missing Reference: 'E' is mentioned on line 274, but not defined == Missing Reference: 'D' is mentioned on line 1802, but not defined == Missing Reference: 'J' is mentioned on line 1642, but not defined == Missing Reference: 'A' is mentioned on line 274, but not defined == Missing Reference: 'B' is mentioned on line 160, but not defined == Missing Reference: 'H' is mentioned on line 1789, but not defined == Missing Reference: 'K' is mentioned on line 1789, but not defined == Missing Reference: 'N' is mentioned on line 1802, but not defined == Missing Reference: 'X' is mentioned on line 1272, but not defined == Missing Reference: 'Y' is mentioned on line 1272, but not defined == Missing Reference: 'R-small' is mentioned on line 1230, but not defined == Missing Reference: 'R-great' is mentioned on line 1247, but not defined == Missing Reference: 'I' is mentioned on line 1647, but not defined == Missing Reference: 'C2' is mentioned on line 1802, but not defined == Missing Reference: 'H2' is mentioned on line 1802, but not defined == Missing Reference: 'K2' is mentioned on line 1802, but not defined == Unused Reference: 'I-D.ietf-rtgwg-mrt-frr-architecture' is defined on line 1910, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-rtgwg-lfa-applicability' is defined on line 1933, but no explicit reference was found in the text == Unused Reference: 'LFARevisited' is defined on line 1948, but no explicit reference was found in the text == Unused Reference: 'LightweightNotVia' is defined on line 1954, but no explicit reference was found in the text == Outdated reference: A later version (-10) exists of draft-ietf-rtgwg-mrt-frr-architecture-00 == Outdated reference: A later version (-11) exists of draft-ietf-rtgwg-ipfrr-notvia-addresses-08 == Outdated reference: A later version (-01) exists of draft-shand-remote-lfa-00 -- Obsolete informational reference (is this intentional?): RFC 3137 (Obsoleted by RFC 6987) Summary: 1 error (**), 0 flaws (~~), 29 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Routing Area Working Group A. Atlas 3 Internet-Draft Juniper Networks 4 Intended status: Informational G. Enyedi 5 Expires: September 13, 2012 A. Csaszar 6 Ericsson 7 March 12, 2012 9 Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- 10 Reroute 11 draft-enyedi-rtgwg-mrt-frr-algorithm-01 13 Abstract 15 A complete solution for IP and LDP Fast-Reroute using Maximally 16 Redundant Trees is presented in [I-D.ietf-rtgwg-mrt-frr- 17 architecture]. This document describes an algorithm that can be used 18 to compute the necessary Maximally Redundant Trees and the associated 19 next-hops. 21 Status of this Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at http://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on September 13, 2012. 38 Copyright Notice 40 Copyright (c) 2012 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 56 2. Terminology and Definitions . . . . . . . . . . . . . . . . . 4 57 3. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . . 6 58 3.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 6 59 3.2. Finding an Ear and the Correct Direction . . . . . . . . . 8 60 3.3. Low-Point Values and Their Uses . . . . . . . . . . . . . 10 61 3.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 14 62 3.5. Determining Local-Root . . . . . . . . . . . . . . . . . . 15 63 4. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . . 16 64 4.1. Root Selection . . . . . . . . . . . . . . . . . . . . . . 18 65 4.2. Initialization . . . . . . . . . . . . . . . . . . . . . . 18 66 4.3. Option 1: Computing GADAG using lowpoint inheritance . . . 18 67 4.4. Option 2: Computing GADAG using SPFs . . . . . . . . . . . 21 68 4.5. Augmenting the GADAG by directing all links . . . . . . . 27 69 4.6. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 29 70 4.6.1. MRT next-hops to all nodes partially ordered with 71 respect to the computing node . . . . . . . . . . . . 30 72 4.6.2. MRT next-hops to all nodes not partially ordered 73 with respect to the computing node . . . . . . . . . . 30 74 4.6.3. Computing Redundant Tree next-hops in a 75 2-connected Graph . . . . . . . . . . . . . . . . . . 31 76 4.6.4. Generalizing for graph that isn't 2-connected . . . . 33 77 4.6.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 34 78 4.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 36 79 5. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 42 80 5.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . . 43 81 6. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 44 82 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 44 83 8. Security Considerations . . . . . . . . . . . . . . . . . . . 44 84 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 44 85 9.1. Normative References . . . . . . . . . . . . . . . . . . . 44 86 9.2. Informative References . . . . . . . . . . . . . . . . . . 44 87 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 46 89 1. Introduction 91 MRT Fast-Reroute requires that packets can be forwarded not only on 92 the shortest-path tree, but also on two Maximally Redundant Trees 93 (MRTs), referred to as the Blue MRT and the Red MRT. A router which 94 experiences a local failure must also have pre-determined which 95 alternate to use. This document describes how to compute these three 96 things and the algorithm design decisions and rationale. The 97 algorithms are based on those presented in [MRTLinear] and expanded 98 in [EnyediThesis]. 100 Just as packets routed on a hop-by-hop basis require that each router 101 compute a shortest-path tree which is consistent, it is necessary for 102 each router to compute the Blue MRT and Red MRT in a consistent 103 fashion. This is the motivation for the detail in this document. 105 As now, a router's FIB will contain primary next-hops for the current 106 shortest-path tree for forwarding traffic. In addition, a router's 107 FIB will contain primary next-hops for the Blue MRT for forwarding 108 received traffic on the Blue MRT and primary next-hops for the Red 109 MRT for forwarding received traffic on the Red MRT. 111 What alternate next-hops a point-of-local-repair (PLR) selects need 112 not be consistent - but loops must be prevented. To reduce 113 congestion, it is possible for multiple alternate next-hops to be 114 selected; in the context of MRT alternates, each of those alternate 115 next-hops would be equal-cost paths. 117 This document provides an algorithm for selecting an appropriate MRT 118 alternate for consideration. Other alternates, e.g. LFAs that are 119 downstream paths, may be prefered when available and that decision- 120 making is not captured in this document. 122 [E]---[D]---| [E]<--[D]<--| [E]-->[D] 123 | | | | ^ | | 124 | | | V | | V 125 [R] [F] [C] [R] [F] [C] [R] [F] [C] 126 | | | ^ ^ | | 127 | | | | | V | 128 [A]---[B]---| [A]-->[B] [A]---[B]<--| 130 (a) (b) (c) 131 a 2-connected graph Blue MRT towards R Red MRT towards R 133 Figure 1 135 Algorithms for computing MRTs can handle arbitrary network topologies 136 where the whole network graph is not 2-connected, as in Figure 2, as 137 well as the easier case where the network graph is 2-connected 138 (Figure 1). Each MRT is a spanning tree. The pair of MRTs provide 139 two paths from every node X to the root of the MRTs. Those paths 140 share the minimum number of nodes and the minimum number of links. 141 Each such shared node is a cut-vertex. Any shared links are cut- 142 links. 144 [E]---[D]---| |---[J] 145 | | | | | 146 | | | | | 147 [R] [F] [C]---[G] | 148 | | | | | 149 | | | | | 150 [A]---[B]---| |---[H] 152 (a) a graph that isn't 2-connected 154 [E]<--[D]<--| |---[J] [E]-->[D] [J] 155 | ^ | | ^ | | 156 V | | V | V | 157 [R] [F] [C]<--[G] | [R] [F] [C]<--[G] | 158 ^ | ^ | | ^ | 159 | | | V | | V 160 [A]-->[B] [H] [A]<--[B]<--| |---[H] 162 (b) Blue MRT towards R (c) Red MRT towards R 164 Figure 2 166 2. Terminology and Definitions 168 Redundant Trees (RT): A pair of trees where the path from any node X 169 to the root R on the first tree is node-disjoint with the path 170 from the same node X to the root along the second tree. These can 171 be computed in 2-connected graphs. 173 Maximally Redundant Trees (MRT): A pair of trees where the path 174 from any node X to the root R along the first tree and the path 175 from the same node X to the root along the second tree share the 176 minimum number of nodes and the minimum number of links. Each 177 such shared node is a cut-vertex. Any shared links are cut-links. 178 Any RT is an MRT but many MRTs are not RTs. 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 cut-vertex: A vertex whose removal partitions the network. 186 cut-link: A link whose removal partitions the network. A cut-link 187 by definition must be connected between two cut-vertices. If 188 there are multiple parallel links, then they are referred to as 189 cut-links in this document if removing the set of parallel links 190 would partition the network. 192 2-connected: A graph that has no cut-vertices. This is a graph 193 that requires two nodes to be removed before the network is 194 partitioned. 196 spanning tree: A tree containing links that connects all nodes in 197 the network graph. 199 back-edge: In the context of a spanning tree computed via a depth- 200 first search, a back-edge is a link that connects a descendant of 201 a node x with an ancestor of x. 203 2-connected cluster: A maximal set of nodes that are 2-connected. 204 In a network graph with at least one cut-vertex, there will be 205 multiple 2-connected clusters. 207 block: Either a 2-connected cluster, a cut-edge, or an isolated 208 vertex. 210 DAG: Directed Acyclic Graph - a digraph containing no directed 211 cycle. 213 ADAG: Almost Directed Acyclic Graph - a digraph that can be 214 transformed into a DAG whith removing a single node (the root 215 node). 217 GADAG: Generalized ADAG - a digraph, which has only ADAGs as all of 218 its blocks. The root of such a block is the node closest to the 219 global root (e.g. with uniform link costs). 221 DFS: Depth-First Search 223 DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS- 224 tree path from the DFS root to x. 226 DFS descendant: A node n is a DFS descendant of x if x is on the 227 DFS-tree path from the DFS root to n. 229 ear: A path along not-yet-included-in-the-GADAG nodes that starts 230 at a node that is already-included-in-the-GADAG and that ends at a 231 node that is already-included-in-the-GADAG. The starting and 232 ending nodes may be the same node if it is a cut-vertex. 234 X >> Y or Y << X: Indicates the relationship between X and Y in a 235 partial order, such as found in a GADAG. X >> Y means that X is 236 higher in the partial order than Y. Y << X means that Y is lower 237 in the partial order than X. 239 X > Y or Y < X: Indicates the relationship between X and Y in the 240 total order, such as found via a topological sort. X > Y means 241 that X is higher in the total order than Y. Y < X means that Y is 242 lower in the total order than X. 244 proxy-node: A node added to the network graph to represent a multi- 245 homed prefix or routers outside the local MRT-fast-reroute- 246 supporting island of routers. The key property of proxy-nodes is 247 that traffic cannot transit them. 249 3. Algorithm Key Concepts 251 There are five key concepts that are critical for understanding the 252 algorithms for computing MRTs. The first is the idea of partially 253 ordering the nodes in a network graph with regard to each other and 254 to the GADAG root. The second is the idea of finding an ear of nodes 255 and adding them in the correct direction. The third is the idea of a 256 Low-Point value and how it can be used to identify cut-vertices and 257 to find a second path towards the root. The fourth is the idea that 258 a non-2-connected graph is made up of blocks, where a block is a 259 2-connected cluster, a cut-edge or an isolated node. The fifth is 260 the idea of a local-root for each node; this is used to compute ADAGs 261 in each block. 263 3.1. Partial Ordering for Disjoint Paths 265 Given any two nodes X and Y in a graph, a particular total order 266 means that either X < Y or X > Y in that total order. An example 267 would be a graph where the nodes are ranked based upon their IP 268 loopback addresses. In a partial order, there may be some nodes for 269 which it can't be determined whether X << Y or X >> Y. A partial 270 order can be captured in a directed graph, as shown in Figure 3. In 271 a graphical representation, a link directed from X to Y indicates 272 that X is a neighbor of Y in the network graph and X << Y. 274 [A]<---[R] [E] R << A << B << C << D << E 275 | ^ R << A << B << F << G << H << D << E 276 | | 277 V | Unspecified Relationships: 278 [B]--->[C]--->[D] C and F 279 | ^ C and G 280 | | C and H 281 V | 282 [F]--->[G]--->[H] 284 Figure 3: Directed Graph showing a Partial Order 286 To compute MRTs, it is very useful to have the root of the MRTs be at 287 the very bottom and the very top of the partial ordering. This means 288 that from any node X, one can pick nodes higher in the order until 289 the root is reached. Similarly, from any node X, one can pick nodes 290 lower in the order until the root is reached. For instance, in 291 Figure 4, from G the higher nodes picked can be traced by following 292 the directed links and are H, D, E and R. Similarly, from G the lower 293 nodes picked can be traced by reversing the directed links and are F, 294 B, A, and R. A graph that represents this modified partial order is 295 no longer a DAG; it is termed an Almost DAG (ADAG) because if the 296 links directed to the root were removed, it would be a DAG. 298 [A]<---[R]<---[E] R << A << B << C << R 299 | ^ ^ R << A << B << C << D << E << R 300 | | | R << A << B << F << G << H << D << E << R 301 V | | 302 [B]--->[C]--->[D] Unspecified Relationships: 303 | ^ C and F 304 | | C and G 305 V | C and H 306 [F]--->[G]--->[H] 308 Figure 4: ADAG showing a Partial Order with R lowest and highest 310 Most importantly, if a node Y >> X, then Y can only appear on the 311 increasing path from X to the root and never on the decreasing path. 312 Similarly, if a node Z << X, then Z can only appear on the decreasing 313 path from X to the root and never on the inceasing path. 315 Additionally, when following the increasing paths, it is possible to 316 pick multiple higher nodes and still have the certainty that those 317 paths will be disjoint from the decreasing paths. E.g. in the 318 previous example node B has multiple possibilities to forward packets 319 along an increasing path: it can either forward packets to C or F. 321 3.2. Finding an Ear and the Correct Direction 323 For simplicity, the basic idea of creating a GADAG by adding ears is 324 described assuming that the network graph is a single 2-connected 325 cluster so that an ADAG is sufficient. Generalizing to multiple 326 blocks is done by considering the block-roots instead of the GADAG 327 root - and the actual algorithms given in Section 4.3 and 328 Section 4.4. 330 In order to understand the basic idea of finding an ADAG, first 331 suppose that we have already a partial ADAG, which doesn't contain 332 all the nodes in the block yet, and we want to extend it to cover all 333 the nodes. Suppose that we find a path from a node X to Y such that 334 X and Y are already contained by our partial ADAG, but all the 335 remaining nodes along the path are not added to the ADAG yet. We 336 refer to such a path as an ear. 338 Recall that our ADAG is closely related to a partial order, more 339 precisely, if we remove root R, the remaining DAG describes a partial 340 order of the nodes. If we suppose that neither X nor Y is the root, 341 we may be able to compare them. If one of them is definitely lesser 342 with respect to our partial order (say X<B---| A-->B---| 354 (a) (b) (c) 356 (a) A 2-connected graph 357 (b) Partial ADAG (C is not included) 358 (c) Resulting ADAG after adding path (or ear) B-C-D 360 Figure 5 362 In this partial ADAG, node C is not yet included. However, we can 363 find path B-C-D, where both endpoints are contained by this partial 364 ADAG (we say those nodes are *ready* in the sequel), and the 365 remaining node (node C) is not contained yet. If we remove R, the 366 remaining DAG defines a partial order, and with respect to this 367 partial order we can say that B<C and C->D are added). If 369 B were strictly greater than D, we would add the same path in reverse 370 direction. 372 If in the partial order where an ear's two ends are X and Y, X << Y, 373 then there must already be a directed path from X to Y already in the 374 ADAG. The ear must be added in a direction such that it doesn't 375 create a cycle; therefore the ear must go from X to Y. 377 In the case, when X and Y are not ordered with each other, we can 378 select either direction for the ear. We have no restriction since 379 neither of the directions can result in a cycle. In the corner case 380 when one of the endpoints of an ear, say X, is the root (recall that 381 the two endpoints must be different), we could use both directions 382 again for the ear because the root can be considered both as smaller 383 and as greater than Y. However, we strictly pick that direction in 384 which the root is lower than Y. The logic for this decision is 385 explained in Section 4.6 387 A partial ADAG is started by finding a cycle from the root R back to 388 itself. This can be done by selecting a non-ready neighbor N of R 389 and then finding a path from N to R that doesn't use any links 390 between R and N. The direction of the cycle can be assigned either 391 way since it is starting the ordering. 393 Once a partial ADAG is already present, we can always add ears to it: 394 just select a non-ready neighbor N of a ready node Q, such that Q is 395 not the root, find a path from N to the root in the graph with Q 396 removed. This path is an ear where the first node of the ear is Q, 397 the next is N, then the path until the first ready node the path 398 reached (that second ready node is the other endpoint of the path). 399 Since the graph is 2-connected, there must be a path from N to R 400 without Q. 402 It is always possible to select a non-ready neighbor N of a ready 403 node Q so that Q is not the root R. Because the network is 404 2-connected, N must be connected to two different nodes and only one 405 can be R. Because the initial cycle has already been added to the 406 ADAG, there are ready nodes that are not R. Since the graph is 407 2-connected, while there are non-ready nodes, there must be a non- 408 ready neighbor N of a ready node that is not R. 410 Generic_Find_Ears_ADAG(root) 411 Create an empty ADAG. Add root to the ADAG. 412 Mark root as IN_GADAG. 413 Select the shortest cycle containing root. 414 Add the shortest cycle to the ADAG. 415 Mark cycle's nodes as IN_GADAG. 416 Add cycle's non-root nodes to process_list. 417 while there exists connected nodes in graph that are not IN_GADAG 418 Select a new ear. Let its endpoints be X and Y. 419 if Y is root or (Y << X) 420 add the ear towards X to the ADAG 421 else // (a) X is root or (b)X << Y or (c) X, Y not ordered 422 Add the ear towards Y to the ADAG 424 Figure 6: Generic Algorithm to find ears and their direction in 425 2-connected graph 427 Algorithm Figure 6 merely requires that a cycle or ear be selected 428 without specifying how. Regardless of the way of selecting the path, 429 we will get an ADAG. The method used for finding and selecting the 430 ears is important; shorter ears result in shorter paths along the 431 MRTs. There are two options being considered. The Low-Point 432 Inheritance option is described in Section 4.3. The SPF-based option 433 is described in Section 4.4. 435 As an example, consider Figure 5 again. First, we select the 436 shortest cycle containing R, which can be R-A-B-F-D-E (uniform link 437 costs were assumed), so we get to the situation depicted in Figure 5 438 (b). Finally, we find a node next to a ready node; that must be node 439 C and assume we reached it from ready node B. We search a path from C 440 to R without B in the original graph. The first ready node along 441 this is node D, so the open ear is B-C-D. Since B<C and C->D to the ADAG. Since all the nodes are ready, we stop at 443 this point. 445 3.3. Low-Point Values and Their Uses 447 A basic way of computing a spanning tree on a network graph is to run 448 a depth-first-search, such as given in Figure 7. This tree has the 449 important property that if there is a link (x, n), then either n is a 450 DFS ancestor of x or n is a DFS descendant of x. In other words, 451 either n is on the path from the root to x or x is on the path from 452 the root to n. 454 global_variable: dfs_number 456 DFS_Visit(node x, node parent) 457 D(x) = dfs_number 458 dfs_number += 1 459 x.dfs_parent = parent 460 for each link (x, w) 461 if D(w) is not set 462 DFS_Visit(w, x) 464 Run_DFS(node root) 465 dfs_number = 0 466 DFS_Visit(root, NONE) 468 Figure 7: Basic Depth-First Search algorithm 470 Given a node x, one can compute the minimal DFS number of the 471 neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the 472 highest attachment point neighbouring x. What is interesting, 473 though, is what is the highest attachment point from x and x's 474 descendants. This is what is determined by computing the Low-Point 475 value, as given in Algorithm Figure 9 and illustrated on a graph in 476 Figure 8. 478 [E]---| [J]-------[I] [P]---[O] 479 | | | | | | 480 | | | | | | 481 [R] [D]---[C]--[F] [H]---[K] [N] 482 | | | | | | 483 | | | | | | 484 [A]--------[B] [G]---| [L]---[M] 486 (a) a non-2-connected graph 488 [E]----| [J]---------[I] [P]------[O] 489 (5, ) | (10, ) (9, ) (16, ) (15, ) 490 | | | | | | 491 | | | | | | 492 [R] [D]---[C]---[F] [H]----[K] [N] 493 (0, ) (4, ) (3, ) (6, ) (8, ) (11, ) (14, ) 494 | | | | | | 495 | | | | | | 496 [A]---------[B] [G]----| [L]------[M] 497 (1, ) (2, ) (7, ) (12, ) (13, ) 499 (b) with DFS values assigned (D(x), L(x)) 501 [E]----| [J]---------[I] [P]------[O] 502 (5,0) | (10,3) (9,3) (16,11) (15,11) 503 | | | | | | 504 | | | | | | 505 [R] [D]---[C]---[F] [H]----[K] [N] 506 (0, ) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11) 507 | | | | | | 508 | | | | | | 509 [A]---------[B] [G]----| [L]------[M] 510 (1,0) (2,0) (7,3) (12,11) (13,11) 512 (c) with low-point values assigned (D(x), L(x)) 514 Figure 8 516 global_variable: dfs_number 518 Lowpoint_Visit(node x, node parent, interface p_to_x) 519 D(x) = dfs_number 520 L(x) = D(x) 521 dfs_number += 1 522 x.dfs_parent = parent 523 x.dfs_parent_intf = p_to_x 524 x.lowpoint_parent = NONE 525 for each interface intf of x: 526 if D(intf.remote_node) is not set 527 Lowpoint_Visit(intf.remote_node, x, intf) 528 if L(intf.remote_node) < L(x) 529 L(x) = L(intf.remote_node) 530 x.lowpoint_parent = intf.remote_node 531 x.lowpoint_parent_intf = intf 532 else if intf.remote_node is not parent 533 if D(intf.remote_node) < L(x) 534 L(x) = D(intf.remote) 535 x.lowpoint_parent = intf.remote_node 536 x.lowpoint_parent_intf = intf 538 Run_Lowpoint(node root) 539 dfs_number = 0 540 Lowpoint_Visit(root, NONE, NONE) 542 Figure 9: Computing Low-Point value 544 From the low-point value and lowpoint parent, there are two very 545 useful things which motivate our computation. 547 First, if there is a child c of x such that L(c) >= D(x), then there 548 are no paths in the network graph that go from c or its descendants 549 to an ancestor of x - and therefore x is a cut-vertex. This is 550 useful because it allows identification of the cut-vertices and thus 551 the blocks. As seen in Figure 8, even if L(x) < D(x), there may be a 552 block that contains both the root and a DFS-child of a node while 553 other DFS-children might be in different blocks. In this example, 554 C's child D is in the same block as R while F is not. 556 Second, by repeatedly following the path given by lowpoint_parent, 557 there is a path from x back to an ancestor of x that does not use the 558 link [x, x.dfs_parent] in either direction. The full path need not 559 be taken, but this gives a way of finding an initial cycle and then 560 ears. 562 3.4. Blocks in a Graph 564 A key idea for the MRT algorithm is that any non-2-connected graph is 565 made up by blocks (e.g. 2-connected clusters, cut-links, and/or 566 isolated nodes). To compute GADAGs and thus MRTs, computation is 567 done in each block to compute ADAGs or Redundant Trees and then those 568 ADAGs or Redundant Trees are combined into a GADAG or MRT. 570 [E]---| [J]-------[I] [P]---[O] 571 | | | | | | 572 | | | | | | 573 [R] [D]---[C]--[F] [H]---[K] [N] 574 | | | | | | 575 | | | | | | 576 [A]--------[B] [G]---| [L]---[M] 578 (a) A graph with four blocks that are: 579 3 2-connected clusters and a cut-link 581 [E]<--| [J]<------[I] [P]<--[O] 582 | | | ^ | ^ 583 V | V | V | 584 [R] [D]<--[C] [F] [H]<---[K] [N] 585 ^ | ^ ^ 586 | V | | 587 [A]------->[B] [G]---| [L]-->[M] 589 (b) Blue MRT 591 [E]---| [J]-------->[I] [P]-->[O] 592 | | | 593 V V V 594 [R] [D]-->[C]<---[F] [H]<---[K] [N] 595 ^ | ^ | ^ | 596 | V | | | V 597 [A]<-------[B] [G]<--| [L]<--[M] 599 (c) Red MRT 601 Figure 10 603 Consider the example depicted in Figure 10 (a). In this figure, a 604 special graph is presented, showing us all the ways 2-connected 605 clusters can be connected. It has four blocks: block 1 contains R, 606 A, B, C, D, E, block 2 contains C, F, G, H, I, J, block 3 contains K, 607 L, M, N, O, P, and block 4 is a cut-edge containing H and K. As can 608 be observed, the first two blocks have one common node (node C) and 609 blocks 2 and 3 do not have any common node, but they are connected 610 through a cut-edge that is block 4. No two blocks can have more than 611 one common node, since two blocks with at least 2 common nodes would 612 qualify as a single 2-connected cluster. 614 Moreover, observe that if we want to get from one block to another, 615 we must use a cut-vertex (the cut-vertices in this graph are C, H, 616 K), regardless of the path selected, so we can say that all the paths 617 from block 3 along the MRTs rooted at R will cross K first. This 618 observation means that if we want to find a pair of MRTs rooted at R, 619 then we need to build up a pair of RTs in block 3 with K as a root. 620 Similarly, we need to find another one in block 2 with C as a root, 621 and finally, we need the last one in block 1 with R as a root. When 622 all the trees are selected, we can simply combine them; when a block 623 is a cut-edge (as in block 4), that cut-edge is added in the same 624 direction to both of the trees. The resulting trees are depicted in 625 Figure 10 (b) and (c). 627 Similarly, to create a GADAG it is sufficient to compute ADAGs in 628 each block and connect them. 630 It is necessary, therefore, to identify the cut-vertices, the blocks 631 and identify the appropriate local-root to use for each block. 633 3.5. Determining Local-Root 635 Each node in a network graph has a local-root, which is the cut- 636 vertex (or root) in the same block that is closest to the root. The 637 local-root is used to determine whether two nodes share a common 638 block. 640 Compute_Localroot(node x, node localroot) 641 x.localroot = localroot 642 for each DFS child c 643 if L(c) < D(x) //x is not a cut-vertex 644 Compute_Localroot(c, x.localroot) 645 else 646 mark x as cut-vertex 647 Compute_Localroot(c, x) 649 Compute_Localroot(root, root) 651 Figure 11: A method for computing local-roots 653 There are two different ways of computing the local-root for each 654 node. The stand-alone method is given in Figure 11 and better 655 illustrates the concept. It is used in the second option for 656 computing a GADAG using SPFs. The other method is used in the first 657 option for computing a GADAG using Low-Point inheritance and the 658 essence of it is given in Figure 12. 660 Get the current node, s. 661 Compute an ear from s to a child c 662 and then via lowpoint inheritance, e.g. 663 ( n = c 664 while n is not ready: 665 n = n.lowpoint_parent 666 e = n 667 ) 668 to a ready node e. 669 if s is e 670 s is a cut-vertex 671 x.localroot = s 672 else 673 for each node x in the ear that is not s or e 674 x.localroot = s.localroot 676 Figure 12: Ear-based method for computing local-roots 678 Once the local-roots are known, two nodes X and Y are in a common 679 block if and only if one of the following three conditions apply. 681 o Y's local-root is X's local-root : They are in the same block and 682 neither is the cut-vertex closest to the root. 684 o Y's local-root is X: X is the cut-vertex closest to the root for 685 Y's block 687 o Y is X's local-root: Y is the cut-vertex closest to the root for 688 X's block 690 4. Algorithm Sections 692 This algorithm computes one GADAG that is then used by a router to 693 determine its blue MRT and red MRT next-hops to all destinations. 694 Finally, based upon that information, alternates are selected for 695 each next-hop to each destination. The different parts of this 696 algorithm are described below. These work on a network graph after, 697 for instance, its interfaces are ordered as per Figure 13. 699 1. Select the root to use for the GADAG. [See Section 4.1.] 700 2. Initialize all interfaces to UNDIRECTED. [See Section 4.2.] 702 3. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See 703 Figure 9.] 705 4. Construct the GADAG. [See Section 4.3 for Option 1 using 706 Lowpoint Inheritance and Section 4.4 for Option 2 using SPFs.] 708 5. Assign directions to all interfaces that are still UNDIRECTED. 709 [See Section 4.5.] 711 6. From the computing router x, compute the next-hops for the blue 712 MRT and red MRT. [See Section 4.6.] 714 7. Identify alternates for each next-hop to each destination by 715 determining which one of the blue MRT and the red MRT the 716 computing router x should select. [See Section 4.7.] 718 To ensure consistency in computation, it is necessary that all 719 routers order interfaces identically. This is necessary for the DFS, 720 where the selection order of the interfaces to explore results in 721 different trees, and for computing the GADAG, where the selection 722 order of the interfaces to use to form ears can result in different 723 GADAGs. The recommended ordering between two interfaces from the 724 same router x is given in Figure 13. 726 Interface_Compare(interface a, interface b) 727 if a.metric < b.metric 728 return A_LESS_THAN_B 729 if b.metric < a.metric 730 return B_LESS_THAN_A 731 if a.neighbor.loopback_addr < b.neighbor.loopback_addr 732 return A_LESS_THAN_B 733 if b.neighbor.loopback_addr < a.neighbor.loopback_addr 734 return B_LESS_THAN_A 735 // Same metric to same node, so the order doesn't matter anymore. 736 // To have a unique, consistent total order, 737 // tie-break based on ifindex. 738 if a.ifindex < b.ifindex 739 return A_LESS_THAN_B 740 return B_LESS_THAN_A 742 Figure 13: Rules for ranking multiple interfaces. Order is from low 743 to high. 745 4.1. Root Selection 747 The precise mechanism by which routers advertise a priority for the 748 GADAG root is not described in this document. Nor is the algorithm 749 for selecting routers based upon priority described in this document. 751 A network may be partitioned or there may be islands of routers that 752 support MRT fast-reroute. Therefore, the root selected for use in a 753 GADAG must be consistent only across each connected island of MRT 754 fast-reroute support. Before beginning computation, the network 755 graph is reduced to contain only the set of routers that support a 756 compatible MRT fast-reroute. 758 The selection of a GADAG root is done among only those routers in the 759 same MRT fast-reroute island as the computing router x. 760 Additionally, only routers that are not marked as unusable or 761 overloaded (e.g. ISIS overload or [RFC3137]) are eligible for 762 selection as root. 764 4.2. Initialization 766 Before running the algorithm, there is the standard type of 767 initialization to be done, such as clearing any computed DFS-values, 768 lowpoint-values, DFS-parents, lowpoint-parents, any MRT-computed 769 next-hops, and flags associated with algorithm. 771 It is assumed that a regular SPF computation has been run so that the 772 primary next-hops from the computing router to each destination are 773 known. This is required for determining alternates at the last step. 775 Initially, all interfaces must be initialized to UNDIRECTED. Whether 776 they are OUTGOING, INCOMING or both is determined when the GADAG is 777 constructed and augmented. 779 It is possible that some links and nodes will be marked as unusable, 780 whether because of configuration, overload, or due to a transient 781 cause such as [RFC3137]. In the algorithm description, it is assumed 782 that such links and nodes will not be explored or used and no more 783 disussion is given of this restriction. 785 4.3. Option 1: Computing GADAG using lowpoint inheritance 787 The basic idea of this is to find ears from a node x that is already 788 in the GADAG (known as IN_GADAG). There are two methods to find 789 ears; both are required. The first is by going to a not IN_GADAG 790 DFS-child and then following the chain of low-point parents until an 791 IN_GADAG node is found. The second is by going to a not IN_GADAG 792 neighbor and then following the chain of DFS parents until an 793 IN_GADAG node is found. As an ear is found, the associated 794 interfaces are marked based on the direction taken. The nodes in the 795 ear are marked as IN_GADAG. In the algorithm, first the ears via 796 DFS-children are found and then the ears via DFS-neighbors are found. 798 By adding both types of ears when an IN_GADAG node is processed, all 799 ears that connect to that node are found. The order in which the 800 IN_GADAG nodes is processed is, of course, key to the algorithm. The 801 order is a stack of ears so the most recent ear is found at the top 802 of the stack. Of course, the stack stores nodes and not ears, so an 803 ordered list of nodes, from the first node in the ear to the last 804 node in the ear, is created as the ear is explored and then that list 805 is pushed onto the stack. 807 Each ear represents a partial order (see Figure 4) and processing the 808 nodes in order along each ear ensures that all ears connecting to a 809 node are found before a node higher in the partial order has its ears 810 explored. This means that the direction of the links in the ear is 811 always from the node x being processed towards the other end of the 812 ear. Additionally, by using a stack of ears, this means that any 813 unprocessed nodes in previous ears can only be ordered higher than 814 nodes in the ears below it on the stack. 816 In this algorithm that depends upon Low-Point inheritance, it is 817 necessary that every node have a low-point parent that is not itself. 818 If a node is a cut-vertex, that will not yet be the case. Therefore, 819 any nodes without a low-point parent will have their low-point parent 820 set to their DFS parent and their low-point value set to the DFS- 821 value of their parent. This assignment also properly allows an ear 822 to a cut-vertex to start and end at the same node. 824 Finally, the algorithm simultaneously computes each node's local- 825 root, as described in Figure 12. The local-root can be inherited 826 from the node x being processed to the nodes in the ear unless the 827 child of x is a cut-vertex in which case the rest of the nodes in the 828 ear are in a different block than x and have the child of x as their 829 local-root. 831 Construct_GADAG_via_Lowpoint(topology, root) 832 root.IN_GADAG = true 833 Initialize Stack to empty 834 push root onto Stack 835 while (Stack is not empty) 836 x = pop(Stack) 837 foreach interface intf of x 838 if ((intf.remote_node.IN_GADAG == false) and 839 (intf.remote_node.dfs_parent is x)) 840 Construct_Ear(x, Stack, intf, CHILD) 841 foreach interface intf of x 842 if ((intf.remote_node.IN_GADAG == false) and 843 (intf.remote_node.dfs_parent is not x)) 844 Construct_Ear(x, Stack, intf, NEIGHBOR) 846 Construct_Ear(x, Stack, intf, type) 847 ear_list = empty 848 cur_node = intf.remote_node 849 cur_intf = intf 850 not_done = true 852 while not_done 853 cur_intf.UNDIRECTED = false 854 cur_intf.OUTGOING = true 855 cur_intf.remote_intf.UNDIRECTED = false 856 cur_intf.remote_intf.INCOMING = true 858 if cur_node.IN_GADAG is false 859 cur_node.IN_GADAG = true 860 add_to_list_end(ear_list, cur_node) 861 if type is CHILD 862 cur_intf = cur_node.lowpoint_parent_intf 863 else type must be NEIGHBOR 864 cur_intf = cur_node.dfs_parent_intf 865 cur_node = cur_intf.remote_node 866 else 867 not_done = false 869 if (type is CHILD) and (cur_node is x) 870 localroot = x 871 else 872 localroot = x.localroot 873 while ear_list is not empty 874 y = remove_end_item_from_list(ear_list) 875 push(Stack, y) 877 Construct_GADAG_via_Lowpoint(topology, root) 878 Figure 14: Low-point Inheritance GADAG algorithm 880 4.4. Option 2: Computing GADAG using SPFs 882 The basic idea in this option is to use slightly-modified SPF 883 computations to find ADAGs in each block. In each block, an SPF 884 computation is first done to find a cycle from the local root and 885 then SPF computations find ears until there are no more interfaces to 886 be explored. The used result from the SPF computation is the path of 887 interfaces indicated by following the previous hops from the 888 mininized IN_GADAG node back to the SPF root. 890 To do this, first all cut-vertices must be identified and local-roots 891 assigned as specified in Figure 11 893 The slight modifications to the SPF are as follows. The root of the 894 block is referred to as the block-root; it is either the GADAG root 895 or a cut-vertex. 897 a. The SPF is rooted at a neighbor x of an IN_GADAG node y. All 898 links between y and x are marked as TEMP_UNUSABLE. They should 899 not be used during the SPF computation. 901 b. If y is not the block-root, then it is marked TEMP_UNUSABLE. It 902 should not be used during the SPF computation. This prevents 903 ears from starting and ending at the same node and avoids cycles; 904 the exception is because cycles to/from the block-root are 905 acceptable and expected. 907 c. Do not explore links to nodes whose local-root is not the block- 908 root. This keeps the SPF confined to the particular block. 910 d. Terminate when the first IN_GADAG node z is minimized. 912 e. Respect the existing directions (e.g. INCOMING, OUTGOING, 913 UNDIRECTED) already specified for each interface. 915 Mod_SPF(spf_root, block_root) 916 Initialize spf_heap to empty 917 Initialize nodes' spf_metric to infinity 918 spf_root.spf_metric = 0 919 insert(spf_heap, spf_root) 920 found_in_gadag = false 921 while (spf_heap is not empty) and (found_in_gadag is false) 922 min_node = remove_lowest(spf_heap) 923 if min_node.IN_GADAG is true 924 found_in_gadag = true 925 else 926 foreach interface intf of min_node 927 if ((intf.OUTGOING or intf.UNDIRECTED) and 928 ((intf.remote_node.localroot is block_root) or 929 (intf.remote_node is block_root)) and 930 (intf.remote_node is not TEMP_UNUSABLE) and 931 (intf is not TEMP_UNUSABLE)) 932 path_metric = min_node.spf_metric + intf.metric 933 if path_metric < intf.remote_node.spf_metric 934 intf.remote_node.spf_metric = path_metric 935 intf.remote_node.spf_prev_intf = intf 936 insert_or_update(spf_heap, intf.remote_node) 937 return min_node 939 SPF_for_Ear(spf_root, block_root, ear_list, cut_vertex_list) 940 end_ear = Mod_SPF(spf_root, block_root) 941 y = end_ear.spf_prev_hop 942 while y.local_node is not spf_root 943 add_to_list_start(ear_list, y) 944 if y.local_node is a cut-vertex 945 add_to_list_end(cut_vertex_list, y.local_node) 946 y = y.local_node.spf_prev_intf 948 Figure 15: Modified SPF for GADAG computation 950 In Figure 15, while the path is determined, any non-end node in the 951 path that is a cut-vertex is added to the list of cut-vertices. This 952 ensures that there is a path from the GADAG root to that cut-vertex 953 before adding it to the list of nodes. All such cut-vertices will be 954 treated as the root of a block and the ADAG in that block will be 955 computed. 957 Assume that an ear is found by going from y to x and then running an 958 SPF that terminates by minimizing z (e.g. y<->x...q<->z). Now it is 959 necessary to determine the direction of the ear; if y << z, then the 960 path should be y->x...q->z but if y >> z, then the path should be 961 y<-x...q<-z. In Section 4.3, the same problem was handled by finding 962 all ears that started at a node before looking at ears starting at 963 nodes higher in the partial order. In this algorithm, using that 964 approach could mean that new ears aren't added in order of their 965 total cost since all ears connected to a node would need to be found 966 before additional nodes could be found. 968 The alternative is to track the order relationship of each node with 969 respect to every other node. This can be accomplished by maintaining 970 two sets of nodes at each node. The first set, Higher_Nodes, 971 contains all nodes that are known to be ordered above the node. The 972 second set, Lower_Nodes, contains all nodes that are known to be 973 ordered below the node. This is the approach used in this algorithm. 975 Set_Ear_Direction(ear_list, end_a, end_b, block_root) 976 // Default of A_TO_B for the following cases: 977 // (a) end_a and end_b are the same (root) 978 // or (b) end_a is in end_b's Lower Nodes 979 // or (c) end_a and end_b were unordered with respect to each 980 // other 981 direction = A_TO_B 982 if (end_b is block_root) and (end_a is not end_b) 983 direction = B_TO_A 984 else if end_a is in end_b.Higher_Nodes 985 direction = B_TO_A 986 if direction is B_TO_A 987 foreach interface i in ear_list 988 i.UNDIRECTED = false 989 i.INCOMING = true 990 i.remote_intf.UNDIRECTED = false 991 i.remote_intf.OUTGOING = true 992 else 993 foreach interface i in ear_list 994 i.UNDIRECTED = false 995 i.OUTGOING = true 996 i.remote_intf.UNDIRECTED = false 997 i.remote_intf.INCOMING = true 998 if end_a is end_b 999 return 1000 // Next, update all nodes' Lower_Nodes and Higher_Nodes 1001 if (end_a is in end_b.Higher_Nodes) 1002 foreach node x where x.localroot is block_root 1003 if end_a is in x.Lower_Nodes 1004 foreach interface i in ear_list 1005 add i.remote_node to x.Lower_Nodes 1006 if end_b is in x.Higher_Nodes 1007 foreach interface i in ear_list 1008 add i.local_node to x.Higher_Nodes 1009 else 1010 foreach node x where x.localroot is block_root 1011 if end_b is in x.Lower_Nodes 1012 foreach interface i in ear_list 1013 add i.local_node to x.Lower_Nodes 1014 if end_a is in x.Higher_Nodes 1015 foreach interface i in ear_list 1016 add i.remote_node to x.Higher_Nodes 1018 Figure 16: Algorithm to assign links of an ear direction 1020 A goal of the algorithm is to find the shortest cycles and ears. An 1021 ear is started by going to a neighbor x of an IN_GADAG node y. The 1022 path from x to an IN_GADAG node is minimal, since it is computed via 1023 SPF. Since a shortest path is made of shortest paths, to find the 1024 shortest ears requires reaching from the set of IN_GADAG nodes to the 1025 closest node that isn't IN_GADAG. Therefore, an ordered tree is 1026 maintained of interfaces that could be explored from the IN_GADAG 1027 nodes. The interfaces are ordered by their characteristics of 1028 metric, local loopback address, remote loopback address, and ifindex, 1029 as in the algorithm previously described in Figure 13. 1031 Finally, cut-edges are a special case because there is no point in 1032 doing an SPF on a block of 2 nodes. The algorithm identifies cut- 1033 edges simply as links where both ends of the link are cut-vertices. 1034 Cut-edges can simply be added to the GADAG with both OUTGOING and 1035 INCOMING specified on their interfaces. 1037 Construct_GADAG_via_SPF(topology, root) 1038 Compute_Localroot(root, root) 1039 if root has multiple DFS-children 1040 mark root as a cut-vertex 1041 Initialize cut_vertex_list to empty 1042 Initialize ordered_intfs_tree to empty 1043 add_to_list_end(cut_vertex_list, root) 1044 while cut_vertex_list is not empty 1045 v = remove_start_item_from_list(cut_vertex_list) 1046 foreach interface intf of v 1047 if L(intf.remote_node) == D(intf.remote_node) 1048 // Special case for cut-edges 1049 intf.UNDIRECTED = false 1050 intf.remote_intf.UNDIRECTED = false 1051 intf.OUTGOING = true 1052 intf.INCOMING = true 1053 intf.remote_intf.OUTGOING = true 1054 intf.remote_intf.INCOMING = true 1055 if intf.remote_node.IN_GADAG == false 1056 if intf.remote_node is a cut-vertex 1057 add_to_list_end(cut_vertex_list, intf.remote_node) 1058 intf.remote_node.IN_GADAG = true 1059 else if intf.remote_node.localroot is v 1060 insert(ordered_intfs_tree, intf) 1061 v.IN_GADAG = true 1062 while ordered_intfs_trees is not empty 1063 cand_intf = remove_lowest(ordered_intfs_tree) 1064 if cand_intf.remote_node.IN_GADAG is false 1065 Mark all interfaces between cand_intf.remote_node 1066 and cand_intf.local_node as TEMP_UNUSABLE 1067 if cand_intf.local_node is not v 1068 Mark cand_intf.local_node as TEMP_UNUSABLE 1069 Initialize ear_list to empty 1070 ear_end = SPF_for_Ear(cand_intf.remote_node, v, ear_list, 1071 cut_vertex_list) 1072 add_to_list_start(ear_list, cand_intf) 1073 Set_Ear_Direction(ear_list, cand_intf.remote, ear_end, v) 1074 Clear TEMP_UNUSABLE from all interfaces between 1075 cand_intf.remote_node and cand_intf.local_node 1076 Clear TEMP_UNUSABLE from cand_intf.local_node 1078 Figure 17: SPF-based GADAG algorithm 1080 4.5. Augmenting the GADAG by directing all links 1082 The GADAG, whether constructed via Low-Point Inheritance or with 1083 SPFs, at this point could be used to find MRTs but the topology does 1084 not include all links in the network graph. That has two impacts. 1085 First, there might be shorter paths that respect the GADAG partial 1086 ordering and so the alternate paths would not be as short as 1087 possible. Second, there may be additional paths between a router x 1088 and the root that are not included in the GADAG. Including those 1089 provides potentially more bandwidth to traffic flowing on the 1090 alternates and may reduce congestion compared to just using the GADAG 1091 as currently constructed. 1093 The goal is thus to assign direction to every remaining link marked 1094 as UNDIRECTED to improve the paths and number of paths found when the 1095 MRTs are computed. 1097 To do this, we need to establish a total order that respects the 1098 partial order described by the GADAG. This can be done using Kahn's 1099 topological sort[Kahn_1962_topo_sort] which essentially assigns a 1100 number to a node x only after all nodes before it (e.g. with a link 1101 incoming to x) have had their numbers assigned. The only issue with 1102 the topological sort is that it works on DAGs and not ADAGs or 1103 GADAGs. 1105 To convert a GADAG to a DAG, it is necessary to remove all links that 1106 point to a root of block from within that block. That provides the 1107 necessary conversion to a DAG and then a topological sort can be 1108 done. Finally, all UNDIRECTED links are assigned a direction based 1109 upon the partial ordering. Any UNDIRECTED links that connect to a 1110 root of a block from within that block are assigned a direction 1111 INCOMING to that root. The exact details of this whole process are 1112 captured in Figure 18 1114 Set_Block_Root_Incoming_Links(topo, root, mark_or_clear) 1115 foreach node x in topo 1116 if node x is a cut-vertex or root 1117 foreach interface i of x 1118 if (i.remote_node.localroot is x) 1119 if i.UNDIRECTED 1120 i.OUTGOING = true 1121 i.remote_intf.INCOMING = true 1122 i.UNDIRECTED = false 1123 i.remote_intf.UNDIRECTED = false 1124 if i.INCOMING 1125 if mark_or_clear is mark 1126 if i.OUTGOING // a cut-edge 1127 i.STORE_INCOMING = true 1128 i.INCOMING = false 1129 i.remote_intf.STORE_OUTGOING = true 1130 i.remote_intf.OUTGOING = false 1131 i.TEMP_UNUSABLE = true 1132 i.remote_intf.TEMP_UNUSABLE = true 1133 else 1134 i.TEMP_UNUSABLE = false 1135 i.remote_intf.TEMP_UNUSABLE = false 1136 if i.STORE_INCOMING and (mark_or_clear is clear) 1137 i.INCOMING = true 1138 i.STORE_INCOMING = false 1139 i.remote_intf.OUTGOING = true 1140 i.remote_intf.STORE_OUTGOING = false 1142 Run_Topological_Sort_GADAG(topo, root) 1143 Set_Block_Root_Incoming_Links(topo, root, MARK) 1144 foreach node x 1145 set x.unvisited to the count of x's incoming interfaces 1146 that aren't marked TEMP_UNUSABLE 1147 Initialize working_list to empty 1148 Initialize topo_order_list to empty 1149 add_to_list_end(working_list, root) 1150 while working_list is not empty 1151 y = remove_start_item_from_list(working_list) 1152 add_to_list_end(topo_order_list, y) 1153 foreach interface i of y 1154 if (i.OUTGOING) and (not i.TEMP_UNUSABLE) 1155 i.remote_node.unvisited -= 1 1156 if i.remote_node.unvisited is 0 1157 add_to_list_end(working_list, i.remote_node) 1158 next_topo_order = 1 1159 while topo_order_list is not empty 1160 y = remove_start_item_from_list(topo_order_list) 1161 y.topo_order = next_topo_order 1162 next_topo_order += 1 1163 Set_Block_Root_Incoming_Links(topo, root, CLEAR) 1165 Add_Undirected_Links(topo, root) 1166 Run_Topological_Sort_GADAG(topo, root) 1167 foreach node x in topo 1168 foreach interface i of x 1169 if i.UNDIRECTED 1170 if x.topo_order < i.remote_node.topo_order 1171 i.OUTGOING = true 1172 i.UNDIRECTED = false 1173 i.remote_intf.INCOMING = true 1174 i.remote_intf.UNDIRECTED = false 1176 else 1177 i.INCOMING = true 1178 i.UNDIRECTED = false 1179 i.remote_intf.OUTGOING = true 1180 i.remote_intf.UNDIRECTED = false 1182 Add_Undirected_Links(topo, root) 1184 Figure 18: Assigning direction to UNDIRECTED links 1186 Proxy-nodes are used to represent multi-homed prefixes and routers 1187 that do not support MRT Fast-Reroute. Until now, the network graph 1188 has not included proxy-nodes because the computation for a GADAG 1189 assumes that the nodes can be transited. 1191 To handle destinations that can only be reached via proxy-nodes, each 1192 proxy-node should be added into the network graph after 1193 Add_Directed_Links() has beeen run once. A proxy-node P is connected 1194 to two routers, X and Y, which have been found to offer the best 1195 cost. If X.topo_order < Y.topo_order, then the proxy-node P is added 1196 along with a link X->P and a link P->Y. Once all the proxy-nodes have 1197 been added in this fashion, Run_Topological_Sort_GADAG() should be 1198 rerun so that the topological order includes the proxy-nodes as well. 1199 This is needed for determining which MRT can offer alternates, as is 1200 explained in Section 4.7. 1202 4.6. Compute MRT next-hops 1204 As was discussed in Section 3.1, once a ADAG is found, it is 1205 straightforward to find the next-hops from any node X to the ADAG 1206 root. However, in this algorithm, we want to reuse the common GADAG 1207 and find not only one pair of redundant trees with it, but a pair 1208 rooted at each node. This is ideal, since it is faster and it 1209 results packet forwarding easier to trace and/or debug. The method 1210 for doing that is based on two basic ideas. First, if two nodes X 1211 and Y are ordered with respect to each other in the partial order, 1212 then the same SPF and reverse-SPF can be used to find the increasing 1213 and decreasing paths. Second, if two nodes X and Y aren't ordered 1214 with respect to each other in the partial order, then intermediary 1215 nodes can be used to create the paths by increasing/decreasing to the 1216 intermediary and then decreasing/increasing to reach Y. 1218 As usual, the two basic ideas will be discussed assuming the network 1219 is two-connected. The generalization to multiple blocks is discussed 1220 in Section 4.6.4. The full algorithm is given in Section 4.6.5. 1222 4.6.1. MRT next-hops to all nodes partially ordered with respect to the 1223 computing node 1225 To find two node-disjoint paths from the computing router X to any 1226 node Y, depends upon whether Y >> X or Y << X. As shown in Figure 19, 1227 if Y >> X, then there is an increasing path that goes from X to Y 1228 without crossing R; this contains nodes in the interval [X,Y]. There 1229 is also a decreasing path that decreases towards R and then decreases 1230 from R to Y; this contains nodes in the interval [X,R-small] or 1231 [R-great,Y]. The two paths cannot have common nodes other than X and 1232 Y. 1234 [Y]<---(Cloud 2)<--- [X] 1235 | ^ 1236 | | 1237 V | 1238 (Cloud 3)--->[R]--->(Cloud 1) 1240 Blue MRT path: X->Cloud 2->Y 1241 Red MRT path: X->Cloud 1->R->Cloud 3->Y 1243 Figure 19: Y >> X 1245 Similar logic applies if Y << X, as shown in Figure 20. In this 1246 case, the increasing path from X increases to R and then increases 1247 from R to Y to use nodes in the intervals [X,R-great] and [R-small, 1248 Y]. The decreasing path from X reaches Y without crossing R and uses 1249 nodes in the interval [Y,X]. 1251 [X]<---(Cloud 2)<--- [Y] 1252 | ^ 1253 | | 1254 V | 1255 (Cloud 3)--->[R]--->(Cloud 1) 1257 Blue MRT path: X->Cloud 3->R->Cloud 1->Y 1258 Red MRT path: X->Cloud 2->Y 1260 Figure 20: Y << X 1262 4.6.2. MRT next-hops to all nodes not partially ordered with respect to 1263 the computing node 1265 When X and Y are not ordered, the first path should increase until we 1266 get to a node G, where G >> Y. At G, we need to decrease to Y. The 1267 other path should be just the opposite: we must decrease until we get 1268 to a node H, where H << Y, and then increase. Since R is smaller and 1269 greater than Y, such G and H must exist. It is also easy to see that 1270 these two paths must be node disjoint: the first path contains nodes 1271 in interval [X,G] and [Y,G], while the second path contains nodes in 1272 interval [H,X] and [H,Y]. This is illustrated in Figure 21. It is 1273 necessary to decrease and then increase for the Blue MRT and increase 1274 and then decrease for the Red MRT; if one simply increased for one 1275 and decreased for the other, then both paths would go through the 1276 root R. 1278 (Cloud 6)<---[Y]<---(Cloud 5)<------------| 1279 | | 1280 | | 1281 V | 1282 [G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H] 1283 ^ | 1284 | | 1285 | | 1286 (Cloud 3)<---[X]<---(Cloud 2)<-----------| 1288 Blue MRT path: decrease to H and increase to Y 1289 X->Cloud 2->H->Cloud 5->Y 1290 Red MRT path: increase to G and decrease to Y 1291 X->Cloud 3->G->Cloud 6->Y 1293 Figure 21: X and Y unordered 1295 This gives disjoint paths as long as G and H are not the same node. 1296 Since G >> Y and H << Y, if G and H could be the same node, that 1297 would have to be the root R. This is not possible because there is 1298 only one incoming interface to the root R which is created when the 1299 initial cycle is found. Recall from Figure 6 that whenever an ear 1300 was found to have an end that was the root R, the ear was directed 1301 from R so that the associated interface on R is outgoing and not 1302 incoming. Therefore, there must be exactly one node M which is the 1303 largest one before R, so the Red MRT path will never reach R; it will 1304 turn at M and decrease to Y. 1306 4.6.3. Computing Redundant Tree next-hops in a 2-connected Graph 1308 The basic ideas for computing RT next-hops in a 2-connected graph 1309 were given in Section 4.6.1 and Section 4.6.2. Given these two 1310 ideas, how can we find the trees? 1312 If some node X only wants to find the next-hops (which is usually the 1313 case for IP networks), it is enough to find which nodes are greater 1314 and less than X, and which are not ordered; this can be done by 1315 running an SPF and a reverse-SPF rooted at X and not exploring any 1316 links from the ADAG root. ( Other traversal algorithms could safely 1317 be used instead where one traversal takes the links in their given 1318 directions and the other reverses the links' directions.) 1320 An SPF rooted at X and not exploring links from the root will find 1321 the increasing next-hops to all Y >> X. Those increasing next-hops 1322 are X's next-hops on the Blue MRT to reach Y. A reverse-SPF rooted at 1323 X and not exploring links from the root will find the decreasing 1324 next-hops to all Z << X. Those decreasing next-hops are X's next-hops 1325 on the Red MRT to reach Z. Since the root R is both greater than and 1326 less than X, after this SPF and reverse-SPF, X's next-hops on the 1327 Blue MRT and on the Red MRT to reach R are known. For every node Y 1328 >> X, X's next-hops on the Red MRT to reach Y are set to those on the 1329 Red MRT to reach R. For every node Z << X, X's next-hops on the Blue 1330 MRT to reach Z are set to those on the Blue MRT to reach R. 1332 For those nodes, which were not reached, we have the next-hops as 1333 well. The increasing Blue MRT next-hop for a node, which is not 1334 ordered, is the next-hop along the decreasing Red MRT towards R and 1335 the decreasing Red MRT next-hop is the next-hop along the increasing 1336 Blue MRT towards R. Naturally, since R is ordered with respect to all 1337 the nodes, there will always be an increasing and a decreasing path 1338 towards it. This algorithm does not provide the specific path taken 1339 but only the appropriate next-hops to use. The identity of G and H 1340 is not determined. 1342 The final case to considered is when the root R computes its own 1343 next-hops. Since the root R is << all other nodes, running an SPF 1344 rooted at R will reach all other nodes; the Blue MRT next-hops are 1345 those found with this SPF. Similarly, since the root R is >> all 1346 other nodes, running a reverse-SPF rooted at R will reach all other 1347 nodes; the Red MRT next-hops are those found with this reverse-SPF. 1349 E---D---| E<--D<--| 1350 | | | | ^ | 1351 | | | V | | 1352 R F C R F C 1353 | | | | ^ ^ 1354 | | | V | | 1355 A---B---| A-->B---| 1357 (a) (b) 1358 A 2-connected graph A spanning ADAG rooted at R 1360 Figure 22 1362 As an example consider the situation depicted in Figure 22. There 1363 node C runs an SPF and a reverse-SPF The SPF reaches D, E and R and 1364 the reverse SPF reaches B, A and R. So we immediately get that e.g. 1365 towards E the increasing next-hop is D (it was reached though D), and 1366 the decreasing next-hop is B (since R was reached though B). Since 1367 both D and B, A and R will compute the next hops similarly, the 1368 packets will reach E. 1370 We have the next-hops towards F as well: since F is not ordered with 1371 respect to C, the increasing next-hop is the decreasing one towards R 1372 (which is B) and the decreasing next-hop is the increasing one 1373 towards R (which is D). Since B is ordered with F, it will find a 1374 real increasing next-hop, so packet forwarded to B will get to F on 1375 path C-B-F. Similarly, D will have a real decreasing next-hop, and 1376 packet will use path C-D-F. 1378 4.6.4. Generalizing for graph that isn't 2-connected 1380 If a graph isn't 2-connected, then the basic approach given in 1381 Section 4.6.3 needs some extensions to determine the appropriate MRT 1382 next-hops to use for destinations outside the computing router X's 1383 blocks. In order to find a pair of maximally redundant trees in that 1384 graph we need to find a pair of RTs in each of the blocks (the root 1385 of these trees will be discussed later), and combine them. 1387 When computing the MRT next-hops from a router X, there are three 1388 basic differences: 1390 1. Only nodes in a common block with X should be explored in the SPF 1391 and reverse-SPF. 1393 2. Instead of using the GADAG root, X's local-root should be used. 1394 This has the following implications: 1396 A. The links from X's local-root should not be explored. 1398 B. If a node is explored in the increasing SPF so Y >> X, then 1399 X's Red MRT next-hops to reach Y uses X's Red MRT next-hops 1400 to reach X's local-root and if Z <<, then X's Blue MRT next- 1401 hops to reach Z uses X's Blue MRT next-hops to reach X's 1402 local-root. 1404 C. If a node W in a common block with X was not reached in the 1405 SPF or reverse-SPF, then W is unordered with respect to X. 1406 X's Blue MRT next-hops to W are X's decreasing aka Red MRT 1407 next-hops to X's local-root. X's Red MRT next-hops to W are 1408 X's increasing aka Blue MRT next-hops to X's local-root. 1410 3. For nodes in different blocks, the next-hops must be inherited 1411 via the relevant cut-vertex. 1413 These are all captured in the detailed algorithm given in 1414 Section 4.6.5. 1416 4.6.5. Complete Algorithm to Compute MRT Next-Hops 1418 The complete algorithm to compute MRT Next-Hops for a particular 1419 router X is given in Figure 23. In addition to computing the Blue 1420 MRT next-hops and Red MRT next-hops used by X to reach each node Y, 1421 the algorithm also stores an "order_proxy", which is the proper cut- 1422 vertex to reach Y if it is outside the block, and which is used later 1423 in deciding whether the Blue MRT or the Red MRT can provide an 1424 acceptable alternate for a particular primary next-hop. 1426 global_var: max_block_id 1428 Assign_Block_ID(x, cur_block_id) 1429 x.block_id = cur_block_id 1430 foreach DFS child c of x 1431 if (c.local_root is x) 1432 max_block_id += 1 1433 Assign_Block_ID(c, max_block_id) 1434 else 1435 Assign_Block_ID(c, cur_block_id) 1437 In_Common_Block(x, y) 1438 if ((x.localroot is y.localroot) or (x is y.localroot) or 1439 (y is x.localroot)) 1440 return true 1441 return false 1443 Store_Results(y, direction, spf_root, store_nhs) 1444 if direction is FORWARD 1445 y.higher = true 1446 if store_nhs 1447 y.blue_next_hops = y.next_hops 1448 if direction is REVERSE 1449 y.lower = true 1450 if store_nhs 1451 y.red_next_hops = y.next_hops 1453 SPF_No_Traverse_Root(spf_root, block_root, direction, store_nhs) 1454 Initialize spf_heap to empty 1455 Initialize nodes' spf_metric to infinity and next_hops to empty 1456 spf_root.spf_metric = 0 1457 insert(spf_heap, spf_root) 1458 while (spf_heap is not empty) 1459 min_node = remove_lowest(spf_heap) 1460 Store_Results(min_node, direction, spf_root, store_nhs) 1461 if ((min_node is spf_root) or 1462 ((min_node is not block_root) and 1463 (min_node is not a proxy_node))) 1464 foreach interface intf of min_node 1465 if (((direction is FORWARD) and intf.OUTGOING) or 1466 ((direction is REVERSE) and intf.INCOMING) and 1467 In_Common_Block(spf_root, intf.remote_node)) 1468 if direction is FORWARD 1469 path_metric = min_node.spf_metric + intf.metric 1470 else 1471 path_metric = min_node.spf_metric + 1472 intf.remote_intf.metric 1473 if path_metric < intf.remote_node.spf_metric 1474 intf.remote_node.spf_metric = path_metric 1475 if min_node is spf_root 1476 intf.remote_node.next_hops = make_list(intf) 1477 else 1478 intf.remote_node.next_hops = min_node.next_hops 1479 insert_or_update(spf_heap, intf.remote_node) 1480 else if path_metric is intf.remote_node.spf_metric 1481 if min_node is spf_root 1482 add_to_list(intf.remote_node.next_hops, intf) 1483 else 1484 add_list_to_list(intf.remote_node.next_hops, 1485 min_node.next_hops) 1487 SetEdge(y) 1488 if y.blue_next_hops is empty and y.red_next_hops is empty 1489 SetEdge(y.localroot) 1490 y.blue_next_hops = y.localroot.blue_next_hops 1491 y.red_next_hops = y.localroot.red_next_hops 1492 y.order_proxy = y.localroot.order_proxy 1494 Compute_MRT_NextHops(x, root) 1495 foreach node y 1496 y.higher = y.lower = false 1497 clear y.red_next_hops and y.blue_next_hops 1498 y.order_proxy = y 1499 SPF_No_Traverse_Root(x, x.localroot, FORWARD, TRUE) 1500 SPF_No_Traverse_Root(x, x.localroot, REVERSE, TRUE) 1502 // red and blue next-hops are stored to x.localroot as different 1503 // paths are found via the SPF and reverse-SPF. 1504 // Similarly any nodes whose local-root is x will have their 1505 // red_next_hops and blue_next_hops already set. 1507 // Handle nodes in the same block that aren't the local-root 1508 foreach node y 1509 if ((y is not x) and (y.localroot is x.localroot) and 1510 ((y is x.localroot) or (y.block_id is x.block_id)) 1511 if y.higher 1512 y.red_next_hops = x.localroot.red_next_hops 1513 else if y.lower 1514 y.blue_next_hops = x.localroot.blue_next_hops 1515 else 1516 y.blue_next_hops = x.localroot.red_next_hops 1517 y.red_next_hops = x.localroot.blue_next_hops 1519 // Inherit next-hops and order_proxies to other components 1520 if x is not root 1521 root.blue_next_hops = x.localroot.blue_next_hops 1522 root.red_next_hops = x.localroot.red_next_hops 1523 root.order_proxy = x.localroot 1524 foreach node y 1525 if (y is not root) and (y is not x) 1526 SetEdge(y) 1528 max_block_id = 0 1529 Assign_Block_ID(root, max_block_id) 1530 Compute_MRT_NextHops(x, root) 1532 Figure 23 1534 4.7. Identify MRT alternates 1536 At this point, we have that a computing router S knows its Blue MRT 1537 next-hops and Red MRT next-hops for each destination. However, we 1538 usually needed to find out which one among these two should be used 1539 in order to avoid a potentially failed node. Usually, the node needs 1540 only to avoid the default next-hop (which has just failed), which is 1541 a neighbor. However, there is a much complex use case for multicast 1542 forwarding, when an alternate area border router must be avoided. 1543 Thus, first we provide a simple algorithm for finding the correct 1544 trees to avoid a given neighbor, and later this algorithm is modified 1545 for a node far away. 1547 For each primary next-hop node F to each destination D, S can call 1548 Select_Alternates(S, D, F) to determine whether to use the Blue MRT 1549 next-hops as the alternate next-hops for that primary next-hop or to 1550 use the Red MRT next-hops. The algorithm is given in Figure 24 and 1551 discussed afterwards. Note that we suppose that each link was 1552 already added to the GADAG in some direction, thus S and F must be 1553 ordered, and there must be a block of the GADAG, which contains both 1554 S and F. Moreover, we also suppose that if there are parallel links 1555 between S and F, and only one of them fails, the connection with F is 1556 not lost, and IPFRR is not activated (instead this event is handled 1557 by some other protection). Finally, if F is the primary next-hop 1558 along a shortest path towards D, D (or D.order_proxy) must be in the 1559 same block. If this final assumption were not true, we would have to 1560 put an extra condition into the algorithm for checking if F and 1561 D.order_proxy are not in the same block, and if they were in 1562 different blocks, both trees could be used. 1564 Select_Alternates_For_NH(S, D, F) 1565 if D.order_proxy is not D 1566 D_lower = D.order_proxy.lower 1567 D_higher = D.order_proxy.higher 1568 D_topo_order = D.order_proxy.topo_order 1569 else 1570 D_lower = D.lower 1571 D_higher = D.higher 1572 D_topo_order = D.topo_order 1574 ///When D==F, we can do only link protection 1575 if ((D == F) or (D.order_proxy == F)) 1576 if (D_lower) 1577 return USE_BLUE 1578 else 1579 return USE_RED 1581 //There are three corner cases when S, F or D is the local root 1582 if (S == F.local_root && S == D.local_root) 1583 if (F.topo_order < D.topo_order) 1584 return USE_RED 1585 else 1586 return USE_BLUE 1588 if (F == S.local_root && F == D.local_root) 1589 if (D_lower) 1590 return USE_RED 1591 else 1592 return USE_BLUE 1594 if (D == S.local_root && D == F.local_root) 1595 if (F.lower) 1596 return USE_BLUE 1597 else 1598 return USE_RED 1600 //This is the main part. Recall that S and F must be ordered 1601 if (D_lower) 1602 if (F.lower && F.topo_order > D_topo_order) 1603 return USE_BLUE 1604 else 1605 return USE_RED 1606 else if (D_higher) 1607 if (F.higher && F.topo_order < D_topo_order) 1608 return USE_RED 1609 else 1610 return USE_BLUE 1611 else //S and D are not ordered 1612 if (F.lower) 1613 return USE_RED 1614 else 1615 return USE_BLUE 1617 Figure 24 1619 The algorithm first handles some corner cases, when either of S, D 1620 and F is the local root. When D is in a different block, the cut- 1621 vertex leading to D's block is used instead as D's order-proxy. If 1622 that is not true, there must be a block, which contains all the three 1623 of them. If S>>D.order_proxy, we can use the red path (decreasing 1624 path), unless F is in interval [D.order_proxy,S] - that is checked in 1625 the second if branch. Similarly, when S<>S, we need to use the blue path. 1631 As an example, consider the ADAG depicted in Figure 25 and first 1632 suppose that G is the source, D is the destination and H is the 1633 failed next-hop. Since D>>G, we need to check if H can be in 1634 interval [G,D]. Since H>>G and D.topo_order>H.topo_order, this may 1635 be possible (actually, in this example that is not only possible but 1636 true), so we select the decreasing path towards the root (red path). 1637 Observe, that we are not sure that H is really in [G,D], but we are 1638 sure that it is not in interval [R, G] and not in interval [R, D] (R 1639 is the smallest and the greatest node), so the decreasing path will 1640 always be usable. If, however, the destination was instead J, we 1641 would find that H.topo_order>J.topo_order, so we can be sure that H 1642 is not in [G, J], so using the increasing (blue) path is safe. 1644 [E]<-[D]<-[H]<-[J] 1645 | ^ ^ ^ 1646 V | | | 1647 [R] [C] [G]->[I] 1648 | ^ ^ ^ 1649 V | | | 1650 [A]->[B]->[F]---| 1652 (a) 1653 a 2-connected graph 1655 Figure 25 1657 For ADAGs, the previous algorithm can easily be extended to compute 1658 the right next-hops for a failed node F. One needs only to find out 1659 what to do, when S is ordered with neither F nor D. In that 1660 situation, the first part of the path (the decreasing part for the 1661 blue path or the increasing part of the red path) is ordered with S, 1662 so that do not contain F. Thus, we can use the blue path if F>D and 1663 the red path if F D_topo_order) 1703 return USE_BLUE 1704 else 1705 return USE_RED 1706 else if (D.higher) 1707 if (F.higher && F.topo_order < D_topo_order) 1708 return USE_RED 1709 else 1710 return USE_BLUE 1711 else //S and D are not ordered 1712 if (F.lower) 1713 return USE_RED 1714 else 1715 return USE_BLUE 1716 else //THIS IS DIFFERENT: S is not ordered with both F and D 1717 if (F.topo_order > D_topo_order) 1718 return USE_BLUE 1719 else 1720 return USE_RED 1722 Figure 26 1724 Select_Alternates_For_ADAG is valid, only when S, F, and D are in the 1725 same block; if this is not the case, we do not even have order 1726 between the nodes. Therefore, if we have a GADAG, where S and F are 1727 not in the same block, we need to convert it into an ADAG. 1729 The transformation is straightforward. Suppose that there is a node 1730 X along the path from S to D. We need to split that into two nodes, 1731 let them be X1 and X2, and add an X1->X2 arc between them. For that 1732 block where X was not the local root, all the arcs going into X must 1733 be added to X1 and all the arcs going out from X must be added to X2. 1734 Moreover, for all the blocks, where X was the local root, do the 1735 opposite, i.e. add arcs going out from X to X1, and those going into 1736 X should be added to X2. It can be seen that the blue and the red 1737 paths will be the same after the transformation, except that where 1738 previously they both crossed X, the red now crosses X1 and the blue 1739 now crosses X2. It is straightforward to see that in this way the 1740 blocks separated by X are opened up into a single block. Naturally, 1741 if the blue or the red path could avoid using a given node F in the 1742 resulting ADAG, path with the same color will avoid F in the original 1743 GADAG. Below is the pseudo code of the generalized algorithm. 1745 Convert_GADAG_to_ADAG(GADAG, ADAG) 1746 ADAG = GADAG 1747 for_each local_root X in GADAG 1748 remove X from ADAG 1749 add X1 to ADAG 1750 add X2 to ADAG 1751 add X1->X2 to ADAG 1752 for_each arc Y->X in GADAG { 1753 if (Y.local_root != X) 1754 add Y->X1 to ADAG 1755 else 1756 add Y->X2 to ADAG 1757 } 1758 for_each arc X->Y in GADAG { 1759 if (Y.local_root != X) 1760 add X2->Y to ADAG 1761 else 1762 add X1->Y to ADAG 1763 } 1765 Select_Alternates_For_GADAG(S, D, F) 1766 if (ADAG == NULL) //Need this once, not once for each F and D 1767 Convert_GADAG_to_ADAG(GADAG, ADAG) 1768 // Now determine the orderings via an SPF and rSPF on ADAG 1769 SPF_No_Traverse_Root(S, S.localroot, FORWARD, FALSE) 1770 SPF_No_Traverse_Root(S, S.localroot, REVERSE, FALSE) 1772 return Select_Alternates_For_ADAG(S, D, F) 1774 Figure 27 1776 As an example consider the GADAG depicted in Figure 28. In that 1777 GADAG, three cut-vertices can be found: C, H and K; we need to split 1778 them all. First, split C, now we have C1 and C2 and a C1->C2 arc 1779 between them. We have arcs B->C and J->C going into C. Since B does 1780 not have C as local root, we add B->C1 to ADAG. However, 1781 J.local_root is C, so J->C2 is added. Similarly we add C2->D and 1782 C1->F. The resulting ADAG is depicted in Figure 29. Now that the 1783 GADAG is converted to an ADAG, it is straightforward to use 1784 Select_Alternates_For_ADAG for this ADAG. 1786 [E]<--| [J]<------[I] [P]<--[O] 1787 | | | ^ | ^ 1788 V | V | V | 1789 [R] [D]<--[C]->[F] [H]<--[K] [N] 1790 | ^ | [ ]-->[ ] ^ 1791 | | | ^ | | 1792 V | V | V | 1793 [A]------->[B] [G]---| [L]-->[M] 1795 A GADAG with multiple blocks 1797 Figure 28 1799 [E]<--| [J]<-----------[I] [P]<--[O] 1800 | | | ^ | ^ 1801 V | V | V | 1802 [R] [D]<----[C2] [H2]<--[K2] [N] 1803 | ^ ^ ^ ^ 1804 | | | | | 1805 | [C1]----->[F] [H1]-->[K1] | 1806 | ^ | ^ | | 1807 V | V | V | 1808 [A]---------->[B] [G]----| [L]-->[M] 1810 The ADAG after conversion 1812 Figure 29 1814 5. Algorithm Alternatives and Evaluation 1816 This description of the algorithm assumes a particular approach that 1817 is believed to be a reasonable compromise between complexity and 1818 computation. There are two options given for constructing the GADAG 1819 as both are reasonable and promising. 1821 SPF-based GADAG Compute the common GADAG using Option 2 of SPF-based 1822 inheritance. This considers metrics when constructing the GADAG, 1823 which is important for path length and operational control. It 1824 has higher computational complexity than the Low-Point Inheritance 1825 GADAG. 1827 Low-Point Inheritance GADAG Compute the common GADAG using Option 1 1828 of Low-Point Inheritance. This ignores metrics when constructing 1829 the GADAG, but its computational complexity is O(links) which is 1830 attractive. It is possible that augmenting the GADAG by assigning 1831 directions to all links in the network graph and adding them to 1832 the GADAG will make the difference between this and the SPF-based 1833 GADAG minimal. 1835 In addition, it is possible to calculate Destination-Rooted GADAG, 1836 where for each destination, a GADAG rooted at that destination is 1837 computed. The GADAG can be computed using either Low-Point 1838 Inheritance or SPF-based. Then a router would need to compute the 1839 blue MRT and red MRT next-hops to that destination. Building GADAGs 1840 per destination is computationally more expensive, but may give 1841 somewhat shorter alternate paths. It may be useful for live-live 1842 multicast along MRTs. 1844 5.1. Algorithm Evaluation 1846 When evaluating different algorithms and methods for IP Fast Reroute 1847 [RFC5714], there are three critical points to consider. 1849 o Coverage: For every Point of Local Repair (PLR) and local failure, 1850 is there an alternate to reach every destination? Those 1851 destinations include not only routers in the IGP area, but also 1852 prefixes outside the IGP area. 1854 o Alternate Length: What is the length of the alternate path offered 1855 compared to the optimal alternate route in the network? This is 1856 computed as the total length of the alternate path divided by the 1857 length of an optimal alternate path. The optimal alternate path 1858 is computed by removing the failed node and running an SPF to find 1859 the shortest path from the PLR to the destination. 1861 o Alternate Bandwidth: What percentage of the traffic sent to the 1862 failed point can be sent on the alternates? This is computed as 1863 the sum of the bandwidths along the alternate paths divided by the 1864 bandwidth of the primary paths that go through the failure point. 1866 Simulation and modeling to evalute the MRT algorithms is underway. 1867 The algorithms being compared are: 1869 o SPF-based GADAG 1871 o Low-Point Inheritance GADAG 1873 o Destination-Rooted SPF-based GADAG 1875 o Destination-Rooted Low-Point Inheritance GADAG 1877 o Not-Via to Next-Next Hop[I-D.ietf-rtgwg-ipfrr-notvia-addresses] 1878 o Loop-Free Alternates[RFC5286] 1880 o Remote LFAs[I-D.shand-remote-lfa] 1882 6. Algorithm Work to Be Done 1884 Broadcast Interfaces: The algorithm assumes that broadcast 1885 interfaces are already represented as pseudo-nodes in the network 1886 graph. The exact rules for extending the set of next-hops and 1887 ensuring that the neighboring node is avoided need to be fully 1888 specified. 1890 Local SRLG Protection: The algorithmic extensions to handle local 1891 SRLGs, where each member of the SRLG shares a common router end, 1892 need to be fully specified. 1894 General SRLG Protection: Creating MRTs that consider general SRLGs 1895 is still a challenging open research problem. 1897 7. IANA Considerations 1899 This doument includes no request to IANA. 1901 8. Security Considerations 1903 This architecture is not currently believed to introduce new security 1904 concerns. 1906 9. References 1908 9.1. Normative References 1910 [I-D.ietf-rtgwg-mrt-frr-architecture] 1911 Atlas, A., Kebler, R., Konstantynowicz, M., Csaszar, A., 1912 White, R., and M. Shand, "An Architecture for IP/LDP Fast- 1913 Reroute Using Maximally Redundant Trees", 1914 draft-ietf-rtgwg-mrt-frr-architecture-00 (work in 1915 progress), January 2012. 1917 9.2. Informative References 1919 [EnyediThesis] 1920 Enyedi, G., "Novel Algorithms for IP Fast Reroute", 1921 Department of Telecommunications and Media Informatics, 1922 Budapest University of Technology and Economics Ph.D. 1923 Thesis, February 2011, . 1927 [I-D.ietf-rtgwg-ipfrr-notvia-addresses] 1928 Bryant, S., Previdi, S., and M. Shand, "IP Fast Reroute 1929 Using Not-via Addresses", 1930 draft-ietf-rtgwg-ipfrr-notvia-addresses-08 (work in 1931 progress), December 2011. 1933 [I-D.ietf-rtgwg-lfa-applicability] 1934 Filsfils, C. and P. Francois, "LFA applicability in SP 1935 networks", draft-ietf-rtgwg-lfa-applicability-06 (work in 1936 progress), January 2012. 1938 [I-D.shand-remote-lfa] 1939 Bryant, S., Filsfils, C., Shand, M., and N. So, "Remote 1940 LFA FRR", draft-shand-remote-lfa-00 (work in progress), 1941 October 2011. 1943 [Kahn_1962_topo_sort] 1944 Kahn, A., "Topological sorting of large networks", 1945 Communications of the ACM, Volume 5, Issue 11 , Nov 1962, 1946 . 1948 [LFARevisited] 1949 Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP 1950 Fast ReRoute: Loop Free Alternates Revisited", Proceedings 1951 of IEEE INFOCOM , 2011, . 1954 [LightweightNotVia] 1955 Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP 1956 Fast ReRoute: Lightweight Not-Via without Additional 1957 Addresses", Proceedings of IEEE INFOCOM , 2009, 1958 . 1960 [MRTLinear] 1961 Enyedi, G., Retvari, G., and A. Csaszar, "On Finding 1962 Maximally Redundant Trees in Strictly Linear Time", IEEE 1963 Symposium on Computers and Comunications (ISCC) , 2009, 1964 . 1967 [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. 1968 McPherson, "OSPF Stub Router Advertisement", RFC 3137, 1969 June 2001. 1971 [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast 1972 Reroute: Loop-Free Alternates", RFC 5286, September 2008. 1974 [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", 1975 RFC 5714, January 2010. 1977 Authors' Addresses 1979 Alia Atlas 1980 Juniper Networks 1981 10 Technology Park Drive 1982 Westford, MA 01886 1983 USA 1985 Email: akatlas@juniper.net 1987 Gabor Sandor Enyedi 1988 Ericsson 1989 Konyves Kalman krt 11 1990 Budapest 1097 1991 Hungary 1993 Email: Gabor.Sandor.Enyedi@ericsson.com 1995 Andras Csaszar 1996 Ericsson 1997 Konyves Kalman krt 11 1998 Budapest 1097 1999 Hungary 2001 Email: Andras.Csaszar@ericsson.com