idnits 2.17.1 draft-ietf-rtgwg-rlfa-node-protection-12.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (January 20, 2017) is 2652 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) No issues found here. Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Routing Area Working Group P. Sarkar, Ed. 3 Internet-Draft Individual Contributor 4 Intended status: Standards Track S. Hegde 5 Expires: July 24, 2017 C. Bowers 6 Juniper Networks, Inc. 7 H. Gredler 8 RtBrick, Inc. 9 S. Litkowski 10 Orange 11 January 20, 2017 13 Remote-LFA Node Protection and Manageability 14 draft-ietf-rtgwg-rlfa-node-protection-12 16 Abstract 18 The loop-free alternates computed following the current Remote-LFA 19 specification guarantees only link-protection. The resulting Remote- 20 LFA nexthops (also called PQ-nodes), may not guarantee node- 21 protection for all destinations being protected by it. 23 This document describes procedures for determining if a given PQ-node 24 provides node-protection for a specific destination or not. The 25 document also shows how the same procedure can be utilized for 26 collection of complete characteristics for alternate paths. 27 Knowledge about the characteristics of all alternate path is 28 precursory to apply operator defined policy for eliminating paths not 29 fitting constraints. 31 Requirements Language 33 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 34 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 35 document are to be interpreted as described in RFC2119 [RFC2119]. 37 Status of This Memo 39 This Internet-Draft is submitted in full conformance with the 40 provisions of BCP 78 and BCP 79. 42 Internet-Drafts are working documents of the Internet Engineering 43 Task Force (IETF). Note that other groups may also distribute 44 working documents as Internet-Drafts. The list of current Internet- 45 Drafts is at http://datatracker.ietf.org/drafts/current/. 47 Internet-Drafts are draft documents valid for a maximum of six months 48 and may be updated, replaced, or obsoleted by other documents at any 49 time. It is inappropriate to use Internet-Drafts as reference 50 material or to cite them other than as "work in progress." 52 This Internet-Draft will expire on July 24, 2017. 54 Copyright Notice 56 Copyright (c) 2017 IETF Trust and the persons identified as the 57 document authors. All rights reserved. 59 This document is subject to BCP 78 and the IETF Trust's Legal 60 Provisions Relating to IETF Documents 61 (http://trustee.ietf.org/license-info) in effect on the date of 62 publication of this document. Please review these documents 63 carefully, as they describe your rights and restrictions with respect 64 to this document. Code Components extracted from this document must 65 include Simplified BSD License text as described in Section 4.e of 66 the Trust Legal Provisions and are provided without warranty as 67 described in the Simplified BSD License. 69 Table of Contents 71 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 72 1.1. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 3 73 2. Node Protection with Remote-LFA . . . . . . . . . . . . . . . 4 74 2.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 4 75 2.2. Additional Definitions . . . . . . . . . . . . . . . . . 6 76 2.2.1. Link-Protecting Extended P-Space . . . . . . . . . . 6 77 2.2.2. Node-Protecting Extended P-Space . . . . . . . . . . 6 78 2.2.3. Q-Space . . . . . . . . . . . . . . . . . . . . . . . 7 79 2.2.4. Link-Protecting PQ Space . . . . . . . . . . . . . . 7 80 2.2.5. Candidate Node-Protecting PQ Space . . . . . . . . . 7 81 2.2.6. Cost-Based Definitions . . . . . . . . . . . . . . . 7 82 2.2.6.1. Link-Protecting Extended P-Space . . . . . . . . 7 83 2.2.6.2. Node-Protecting Extended P-Space . . . . . . . . 8 84 2.2.6.3. Q-Space . . . . . . . . . . . . . . . . . . . . . 9 85 2.3. Computing Node-protecting R-LFA Path . . . . . . . . . . 9 86 2.3.1. Computing Candidate Node-protecting PQ-Nodes for 87 Primary nexthops . . . . . . . . . . . . . . . . . . 9 88 2.3.2. Computing node-protecting paths from PQ-nodes to 89 destinations . . . . . . . . . . . . . . . . . . . . 11 90 2.3.3. Computing Node-Protecting R-LFA Paths for 91 Destinations with ECMP primary nexthop nodes . . . . 13 92 2.3.4. Limiting extra computational overhead . . . . . . . . 17 93 3. Manageability of Remote-LFA Alternate Paths . . . . . . . . . 18 94 3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 18 95 3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 19 96 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 19 97 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 98 6. Security Considerations . . . . . . . . . . . . . . . . . . . 19 99 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 20 100 7.1. Normative References . . . . . . . . . . . . . . . . . . 20 101 7.2. Informative References . . . . . . . . . . . . . . . . . 20 102 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 104 1. Introduction 106 The Remote-LFA [RFC7490] specification provides loop-free alternates 107 that guarantee only link-protection. The resulting Remote-LFA 108 alternate nexthops (also referred to as the PQ-nodes) may not provide 109 node-protection for all destinations covered by the same Remote-LFA 110 alternate, in case of failure of the primary nexthop node. Neither 111 does the specification provide a means to determine the same. 113 Also, the LFA Manageability [RFC7916] document requires a computing 114 router to find all possible (including all possible Remote-LFA) 115 alternate nexthops, collect the complete set of path characteristics 116 for each alternate path, run an alternate-selection policy 117 (configured by the operator) and find the best alternate path. This 118 will require the Remote-LFA implementation to gather all the required 119 path characteristics along each link on the entire Remote-LFA 120 alternate path. 122 With current LFA [RFC5286] and Remote-LFA implementations, the 123 forward SPF (and reverse SPF) is run with the computing router and 124 its immediate 1-hop routers as the roots. While that enables 125 computation of path attributes (e.g. SRLG, Admin-groups) for first 126 alternate path segment from the computing router to the PQ-node, 127 there is no means for the computing router to gather any path 128 attributes for the path segment from the PQ-node to destination. 129 Consequently any policy-based selection of alternate paths will 130 consider only the path attributes from the computing router up until 131 the PQ-node. 133 This document describes a procedure for determining node-protection 134 with Remote-LFA. The same procedure is also extended for collection 135 of a complete set of path attributes, enabling more accurate policy- 136 based selection for alternate paths obtained with Remote-LFA. 138 1.1. Abbreviations 140 This document uses the following list of abbreviations. 142 LFA - Loop Free Alternates 144 RLFA or R-LFA - Remote Loop Free Alternates 145 ECMP - Equal Cost Multiple Path 147 SPF - Shortest Path First graph computations 149 NH - Next Hop node 151 2. Node Protection with Remote-LFA 153 Node-protection is required to provide protection of traffic on a 154 given forwarding node, against the failure of the first-hop node on 155 the primary forwarding path. Such protection becomes more critical 156 in the absence of mechanisms like non-stop-routing in the network. 157 Certain operators refrain from deploying non-stop-routing in their 158 network, due to the required complex state synchronization between 159 redundant control plane hardwares it requires, and the significant 160 additional performance complexities it hence introduces. In such 161 cases node-protection is essential to guarantee un-interrupted flow 162 of traffic, even in the case of an entire forwarding node going down. 164 The following sections discuss the node-protection problem in the 165 context of Remote-LFA and propose a solution. 167 2.1. The Problem 169 To better illustrate the problem and the solution proposed in this 170 document the following topology diagram from the Remote-LFA [RFC7490] 171 draft is being re-used with slight modification. 173 D1 174 / 175 S-x-E 176 / \ 177 N R3--D2 178 \ / 179 R1---R2 181 Figure 1: Topology 1 183 In the above topology, for all (non-ECMP) destinations reachable via 184 the S-E link there is no standard LFA alternate. As per the Remote- 185 LFA [RFC7490] alternate specifications node R2 being the only PQ-node 186 for the S-E link provides nexthop for all the above destinations. 187 Table 1 below, shows all possible primary and Remote-LFA alternate 188 paths for each destination. 190 +-------------+--------------+---------+-------------------------+ 191 | Destination | Primary Path | PQ-node | Remote-LFA Backup Path | 192 +-------------+--------------+---------+-------------------------+ 193 | R3 | S->E->R3 | R2 | S=>N=>R1=>R2->R3 | 194 | E | S->E | R2 | S=>N=>R1=>R2->R3->E | 195 | D1 | S->E->D1 | R2 | S=>N=>R1=>R2->R3->E->D1 | 196 | D2 | S->E->R3->D2 | R2 | S=>N=>R1=>R2->R3->D2 | 197 +-------------+--------------+---------+-------------------------+ 199 Table 1: Remote-LFA backup paths via PQ-node R2 201 A closer look at Table 1 shows that, while the PQ-node R2 provides 202 link-protection for all the destinations, it does not provide node- 203 protection for destinations E and D1. In the event of the node- 204 failure on primary nexthop E, the alternate path from Remote-LFA 205 nexthop R2 to E and D1 also becomes unavailable. So for a Remote-LFA 206 nexthop to provide node-protection for a given destination, it is 207 mandatory that, the shortest path from the given PQ-node to the given 208 destination MUST NOT traverse the primary nexthop. 210 In another extension of the topology in Figure 1 let us consider an 211 additional link between N and E with the same cost as the other 212 links. 214 D1 215 / 216 S-x-E 217 / / \ 218 N---+ R3--D2 219 \ / 220 R1---R2 222 Figure 2: Topology 2 224 In the above topology, the S-E link is no more on any of the shortest 225 paths from N to R3, E and D1. Hence R3, E and D1 are also included 226 in both the Extended-P space and Q space of E (w.r.t S-E link). 227 Table 2 below, shows all possible primary and R-LFA alternate paths 228 via PQ-node R3, for each destination reachable through the S-E link 229 in the above topology. The R-LFA alternate paths via PQ-node R2 230 remains same as in Table 1. 232 +-------------+--------------+---------+------------------------+ 233 | Destination | Primary Path | PQ-node | Remote-LFA Backup Path | 234 +-------------+--------------+---------+------------------------+ 235 | R3 | S->E->R3 | R3 | S=>N=>E=>R3 | 236 | E | S->E | R3 | S=>N=>E=>R3->E | 237 | D1 | S->E->D1 | R3 | S=>N=>E=>R3->E->D1 | 238 | D2 | S->E->R3->D2 | R3 | S=>N=>E=>R3->D2 | 239 +-------------+--------------+---------+------------------------+ 241 Table 2: Remote-LFA backup paths via PQ-node R3 243 Again a closer look at Table 2 shows that, unlike Table 1, where the 244 single PQ-node R2 provided node-protection for destinations R3 and 245 D2, if we choose R3 as the R-LFA nexthop, it does not provide node- 246 protection for R3 and D2 anymore. If S chooses R3 as the R-LFA 247 nexthop, in the event of the node-failure on primary nexthop E, on 248 the alternate path from S to R-LFA nexthop R3, one of parallel ECMP 249 path between N and R3 also becomes unavailable. So for a Remote-LFA 250 nexthop to provide node-protection for a given destination, it is 251 also mandatory that, the shortest paths from S to the chosen PQ-node 252 MUST NOT traverse the primary nexthop node. 254 2.2. Additional Definitions 256 This document adds and enhances the following definitions extending 257 the ones mentioned in Remote-LFA [RFC7490] specification. 259 2.2.1. Link-Protecting Extended P-Space 261 The Remote-LFA [RFC7490] specification already defines this. The 262 link-protecting extended P-space for a link S-E being protected is 263 the set of routers that are reachable from one or more direct 264 neighbors of S, except primary node E, without traversing the S-E 265 link on any of the shortest paths from the direct neighbor to the 266 router. This MUST exclude any direct neighbor for which there is at 267 least one ECMP path from the direct neighbor traversing the link(S-E) 268 being protected. 270 For a cost-based definition for Link-protecting Extended P-Space 271 refer to Section 2.2.6.1. 273 2.2.2. Node-Protecting Extended P-Space 275 The node-protecting extended P-space for a primary nexthop node E 276 being protected, is the set of routers that are reachable from one or 277 more direct neighbors of S, except primary node E, without traversing 278 the node E. This MUST exclude any direct neighbors for which there 279 is at least one ECMP path from the direct neighbor traversing the 280 node E being protected. 282 For a cost-based definition for Node-protecting Extended P-Space 283 refer to Section 2.2.6.2. 285 2.2.3. Q-Space 287 The Remote-LFA [RFC7490] draft already defines this. The Q-space for 288 a link S-E being protected is the set of nodes that can reach primary 289 node E, without traversing the S-E link on any of the shortest paths 290 from the node itself to primary nexthop E. This MUST exclude any 291 node for which there is at least one ECMP path from the node to the 292 primary nexthop E traversing the link(S-E) being protected. 294 For a cost-based definition for Q-Space refer to Section 2.2.6.3. 296 2.2.4. Link-Protecting PQ Space 298 A node Y is in link-protecting PQ space w.r.t the link (S-E) being 299 protected, if and only if, Y is present in both link-protecting 300 extended P-space and the Q-space for the link being protected. 302 2.2.5. Candidate Node-Protecting PQ Space 304 A node Y is in candidate node-protecting PQ space w.r.t the node (E) 305 being protected, if and only if, Y is present in both node-protecting 306 extended P-space and the Q-space for the link being protected. 308 Please note, that a node Y being in candidate node-protecting PQ- 309 space, does not guarantee that the R-LFA alternate path via the same, 310 in entirety, is unaffected in the event of a node failure of primary 311 nexthop node E. It only guarantees that the path segment from S to 312 PQ-node Y is unaffected by the same failure event. The PQ-nodes in 313 the candidate node-protecting PQ space may provide node protection 314 for only a subset of destinations that are reachable through the 315 corresponding primary link. 317 2.2.6. Cost-Based Definitions 319 This section provides cost-based definitions for some of the terms 320 introduced in Section 2.2 of this document. 322 2.2.6.1. Link-Protecting Extended P-Space 324 Please refer to Section 2.2.1 for a formal definition for Link- 325 protecting Extended P-Space. 327 A node Y is in link-protecting extended P-space w.r.t the link (S-E) 328 being protected, if and only if, there exists at least one direct 329 neighbor of S, Ni, other than primary nexthop E, that satisfies the 330 following condition. 332 D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y) 334 Where, 335 D_opt(A,B) : Distance on most optimum path from A to B. 336 Ni : A direct neighbor of S other than primary 337 nexthop E. 338 Y : The node being evaluated for link-protecting 339 extended P-Space. 341 Figure 3: Link-Protecting Ext-P-Space Condition 343 2.2.6.2. Node-Protecting Extended P-Space 345 Please refer to Section 2.2.2 for a formal definition for Node- 346 protecting Extended P-Space. 348 A node Y is in node-protecting extended P-space w.r.t the node E 349 being protected, if and only if, there exists at least one direct 350 neighbor of S, Ni, other than primary nexthop E, that satisfies the 351 following condition. 353 D_opt(Ni,Y) < D_opt(Ni,E) + D_opt(E,Y) 355 Where, 356 D_opt(A,B) : Distance on most optimum path from A to B. 357 E : The primary nexthop on shortest path from S 358 to destination. 359 Ni : A direct neighbor of S other than primary 360 nexthop E. 361 Y : The node being evaluated for node-protecting 362 extended P-Space. 364 Figure 4: Node-Protecting Ext-P-Space Condition 366 Please note, that a node Y satisfying the condition in Figure 4 above 367 only guarantees that the R-LFA alternate path segment from S via 368 direct neighbor Ni to the node Y is not affected in the event of a 369 node failure of E. It does not yet guarantee that the path segment 370 from node Y to the destination is also unaffected by the same failure 371 event. 373 2.2.6.3. Q-Space 375 Please refer to Section 2.2.3 for a formal definition for Q-Space. 377 A node Y is in Q-space w.r.t the link (S-E) being protected, if and 378 only if, the following condition is satisfied. 380 D_opt(Y,E) < D_opt(S,E) + D_opt(Y,S) 382 Where, 383 D_opt(A,B) : Distance on most optimum path from A to B. 384 E : The primary nexthop on shortest path from S 385 to destination. 386 Y : The node being evaluated for Q-Space. 388 Figure 5: Q-Space Condition 390 2.3. Computing Node-protecting R-LFA Path 392 The R-LFA alternate path through a given PQ-node to a given 393 destination is comprised of two path segments as follows. 395 1. Path segment from the computing router to the PQ-node (Remote-LFA 396 alternate nexthop), and 398 2. Path segment from the PQ-node to the destination being protected. 400 So to ensure a R-LFA alternate path for a given destination provides 401 node-protection we need to ensure that none of the above path 402 segments are affected in the event of failure of the primary nexthop 403 node. Sections Section 2.3.1 and Section 2.3.2 show how this can be 404 ensured. 406 2.3.1. Computing Candidate Node-protecting PQ-Nodes for Primary 407 nexthops 409 To choose a node-protecting R-LFA nexthop for a destination R3, 410 router S needs to consider a PQ-node from the candidate node- 411 protecting PQ-space for the primary nexthop E on shortest path from S 412 to R3. As mentioned in Section 2.2.2, to consider a PQ-node as 413 candidate node-protecting PQ-node, there must be at least one direct 414 neighbor Ni of S, such that all shortest paths from Ni to the PQ-node 415 does not traverse primary nexthop node E. 417 Implementations SHOULD run the inequality in Section 2.2.2 Figure 4 418 for all direct neighbors, other than primary nexthop node E, to 419 determine whether a node Y is a candidate node-protecting PQ-node. 421 All of the metrics needed by this inequality would have been already 422 collected from the forward SPFs rooted at each of direct neighbor S, 423 computed as part of standard LFA [RFC5286] implementation. With 424 reference to the topology in Figure 2, Table 3 below shows how the 425 above condition can be used to determine the candidate node- 426 protecting PQ-space for S-E link (primary nexthop E). 428 +------------+----------+----------+----------+---------+-----------+ 429 | Candidate | Direct | D_opt | D_opt | D_opt | Condition | 430 | PQ-node | Nbr (Ni) | (Ni,Y) | (Ni,E) | (E,Y) | Met | 431 | (Y) | | | | | | 432 +------------+----------+----------+----------+---------+-----------+ 433 | R2 | N | 2 (N,R2) | 1 (N,E) | 2 | Yes | 434 | | | | | (E,R2) | | 435 | R3 | N | 2 (N,R3) | 1 (N,E) | 1 | No | 436 | | | | | (E,R3) | | 437 +------------+----------+----------+----------+---------+-----------+ 439 Table 3: Node-protection evaluation for R-LFA repair tunnel to PQ- 440 node 442 As seen in the above Table 3, R3 does not meet the node-protecting 443 extended-p-space inequality and so, while R2 is in candidate node- 444 protecting PQ space, R3 is not. 446 Some SPF implementations may also produce a list of links and nodes 447 traversed on the shortest path(s) from a given root to others. In 448 such implementations, router S may have executed a forward SPF with 449 each of its direct neighbors as the SPF root, executed as part of the 450 standard LFA [RFC5286] computations. So S may re-use the list of 451 links and nodes collected from the same SPF computations, to decide 452 whether a node Y is a candidate node-protecting PQ-node or not. A 453 node Y shall be considered as a node-protecting PQ-node, if and only 454 if, there is at least one direct neighbor of S, other than the 455 primary nexthop E, for which, the primary nexthop node E does not 456 exist on the list of nodes traversed on any of the shortest paths 457 from the direct neighbor to the PQ-node. Table 4 below is an 458 illustration of the mechanism with the topology in Figure 2. 460 +-----------+-------------------+-----------------+-----------------+ 461 | Candidate | Repair Tunnel | Link-Protection | Node-Protection | 462 | PQ-node | Path(Repairing | | | 463 | | router to PQ- | | | 464 | | node) | | | 465 +-----------+-------------------+-----------------+-----------------+ 466 | R2 | S->N->R1->R2 | Yes | Yes | 467 | R2 | S->E->R3->R2 | No | No | 468 | R3 | S->N->E->R3 | Yes | No | 469 +-----------+-------------------+-----------------+-----------------+ 471 Table 4: Protection of Remote-LFA tunnel to the PQ-node 473 As seen in the above Table 4 while R2 is candidate node-protecting 474 Remote-LFA nexthop for R3 and D2, it is not so for E and D1, since 475 the primary nexthop E is in the shortest path from R2 to E and D1. 477 2.3.2. Computing node-protecting paths from PQ-nodes to destinations 479 Once a computing router finds all the candidate node-protecting PQ- 480 nodes for a given directly attached primary link, it shall follow the 481 procedure as proposed in this section, to choose one or more node- 482 protecting R-LFA paths, for destinations reachable through the same 483 primary link in the primary SPF graph. 485 To find a node-protecting R-LFA path for a given destination, the 486 computing router needs to pick a subset of PQ-nodes from the 487 candidate node-protecting PQ-space for the corresponding primary 488 nexthop, such that all the path(s) from the PQ-node(s) to the given 489 destination remain unaffected in the event of a node failure of the 490 primary nexthop node. To determine whether a given PQ-node belongs 491 to such a subset of PQ-nodes, the computing router MUST ensure that 492 none of the primary nexthop node are found on any of the shortest 493 paths from the PQ-node to the given destination. 495 This document proposes an additional forward SPF computation for each 496 of the PQ-nodes, to discover all shortest paths from the PQ-nodes to 497 the destination. This will help determine, if a given primary 498 nexthop node is on the shortest paths from the PQ-node to the given 499 destination or not. To determine if a given candidate node- 500 protecting PQ-node provides node-protecting alternate for a given 501 destination, or not, all the shortest paths from the PQ-node to the 502 given destination has to be inspected, to check if the primary 503 nexthop node is found on any of these shortest paths. To compute all 504 the shortest paths from a candidate node-protecting PQ-node to one 505 (or more) destination, the computing router MUST run the forward SPF 506 on the candidate node-protecting PQ-node. Soon after running the 507 forward SPF, the computer router SHOULD run the inequality in 508 Figure 6 below, once for each destination. A PQ-node that does not 509 qualify the condition for a given destination, does not guarantee 510 node-protection for the path segment from the PQ-node to the specific 511 destination. 513 D_opt(Y,D) < D_opt(Y,E) + Distance_opt(E,D) 515 Where, 516 D_opt(A,B) : Distance on most optimum path from A to B. 517 D : The destination node. 518 E : The primary nexthop on shortest path from S 519 to destination. 520 Y : The node-protecting PQ-node being evaluated 522 Figure 6: Node-Protecting Condition for PQ-node to Destination 524 All of the above metric costs except D_opt(Y, D), can be obtained 525 with forward and reverse SPFs with E(the primary nexthop) as the 526 root, run as part of the regular LFA and Remote-LFA implementation. 527 The Distance_opt(Y, D) metric can only be determined by the 528 additional forward SPF run with PQ-node Y as the root. With 529 reference to the topology in Figure 2, Table 5 below shows how the 530 above condition can be used to determine node-protection with node- 531 protecting PQ-node R2. 533 +-------------+------------+---------+--------+---------+-----------+ 534 | Destination | Primary-NH | D_opt | D_opt | D_opt | Condition | 535 | (D) | (E) | (Y, D) | (Y, E) | (E, D) | Met | 536 +-------------+------------+---------+--------+---------+-----------+ 537 | R3 | E | 1 | 2 | 1 | Yes | 538 | | | (R2,R3) | (R2,E) | (E,R3) | | 539 | E | E | 2 | 2 | 0 (E,E) | No | 540 | | | (R2,E) | (R2,E) | | | 541 | D1 | E | 3 | 2 | 1 | No | 542 | | | (R2,D1) | (R2,E) | (E,D1) | | 543 | D2 | E | 2 | 2 | 1 | Yes | 544 | | | (R2,D2) | (R2,E) | (E,D2) | | 545 +-------------+------------+---------+--------+---------+-----------+ 547 Table 5: Node-protection evaluation for R-LFA path segment between 548 PQ-node and destination 550 As seen in the above example above, R2 does not meet the node- 551 protecting inequality for destination E, and D1. And so, once again, 552 while R2 is a node-protecting Remote-LFA nexthop for R3 and D2, it is 553 not so for E and D1. 555 In SPF implementations that also produce a list of links and nodes 556 traversed on the shortest path(s) from a given root to others, the 557 inequality in Figure 6 above need not be evaluated. Instead, to 558 determine whether a PQ-node provides node-protection for a given 559 destination or not, the list of nodes computed from forward SPF run 560 on the PQ-node, for the given destination, SHOULD be inspected. In 561 case the list contains the primary nexthop node, the PQ-node does not 562 provide node-protection. Else, the PQ-node guarantees node- 563 protecting alternate for the given destination. Below is an 564 illustration of the mechanism with candidate node-protecting PQ-node 565 R2 in the topology in Figure 2. 567 +-------------+-----------------+-----------------+-----------------+ 568 | Destination | Shortest Path | Link-Protection | Node-Protection | 569 | | (Repairing | | | 570 | | router to PQ- | | | 571 | | node) | | | 572 +-------------+-----------------+-----------------+-----------------+ 573 | R3 | R2->R3 | Yes | Yes | 574 | E | R2->R3->E | Yes | No | 575 | D1 | R2->R3->E->D1 | Yes | No | 576 | D2 | R2->R3->D2 | Yes | Yes | 577 +-------------+-----------------+-----------------+-----------------+ 579 Table 6: Protection of Remote-LFA path between PQ-node and 580 destination 582 As seen in the above example while R2 is candidate node-protecting 583 R-LFA nexthop for R3 and D2, it is not so for E and D1, since the 584 primary nexthop E is in the shortest path from R2 to E and D1. 586 The procedure described in this document helps no more than to 587 determine whether a given Remote-LFA alternate provides node- 588 protection for a given destination or not. It does not find out any 589 new Remote-LFA alternate nexthops, outside the ones already computed 590 by standard Remote-LFA procedure. However, in case of availability 591 of more than one PQ-node (Remote-LFA alternates) for a destination, 592 and node-protection is required for the given primary nexthop, this 593 procedure will eliminate the PQ-nodes that do not provide node- 594 protection and choose only the ones that does. 596 2.3.3. Computing Node-Protecting R-LFA Paths for Destinations with ECMP 597 primary nexthop nodes 599 In certain scenarios, when one or more destinations maybe reachable 600 via multiple ECMP (equal-cost-multi-path) nexthop nodes, and only 601 link-protection is required, there is no need to compute any 602 alternate paths for such destinations. In the event of failure of 603 one of the nexthop links, the remaining primary nexthops shall always 604 provide link-protection. However, if node-protection is required, 605 the rest of the primary nexthops may not guarantee node-protection. 606 Figure 7 below shows one such example topology. 608 D1 609 2 / 610 S---x---E1 611 / \ / \ 612 / x / \ 613 / \ / \ 614 N-------E2 R3--D2 615 \ 2 / 616 \ / 617 \ / 618 R1-------R2 619 2 621 Primary Nexthops: 622 Destination D1 = [{ S-E1, E1}, {S-E2, E2}] 623 Destination D2 = [{ S-E1, E1}, {S-E2, E2}] 625 Figure 7: Topology with multiple ECMP primary nexthops 627 In the above example topology, costs of all links are 1, except the 628 following links: 630 Link: S-E1, Cost: 2 632 Link: N-E2: Cost: 2 634 Link: R1-R2: Cost: 2 636 In the above topology, on computing router S, destinations D1 and D2 637 are reachable via two ECMP nexthop nodes E1 and E2. However the 638 primary paths via nexthop node E2 also traverses via the nexthop node 639 E1. So in the event of node failure of nexthop node E1, both primary 640 paths (via E1 and E2) becomes unavailable. Hence if node-protection 641 is desired for destinations D1 and D2, alternate paths that does not 642 traverse any of the primary nexthop nodes E1 and E2, need to be 643 computed. In the above topology the only alternate neighbor N does 644 not provide such a LFA alternate path. Hence one (or more) R-LFA 645 node-protecting alternate paths for destinations D1 and D2, needs to 646 be computed. 648 In the above topology, following are the link-protecting PQ-nodes. 650 Primary Nexthop: E1, Link-Protecting PQ-Node: { R2 } 652 Primary Nexthop: E2, Link-Protecting PQ-Node: { R2 } 654 To find one (or more) node-protecting R-LFA paths for destinations D1 655 and D2, one (or more) node-protecting PQ-node(s) needs to be 656 determined first. Inequalities specified in Section 2.2.6.2 and 657 Section 2.2.6.3 can be evaluated to compute the node-protecting PQ- 658 space for each of the nexthop nodes E1 and E2, as shown in Table 7 659 below. To select a PQ-node as node-protecting PQ-node for a 660 destination with multiple primary nexthop nodes, the PQ-node MUST 661 satisfy the inequality for all primary nexthop nodes. Any PQ-node 662 which is NOT node-protecting PQ-node for all the primary nexthop 663 nodes, MUST NOT be chosen as the node-protecting PQ-node for 664 destination. 666 +--------+----------+-------+--------+--------+---------+-----------+ 667 | Primar | Candidat | Direc | D_opt | D_opt | D_opt | Condition | 668 | y Next | e PQ- | t Nbr | (Ni,Y) | (Ni,E) | (E,Y) | Met | 669 | hop | node (Y) | (Ni) | | | | | 670 | (E) | | | | | | | 671 +--------+----------+-------+--------+--------+---------+-----------+ 672 | E1 | R2 | N | 3 | 3 | 2 | Yes | 673 | | | | (N,R2) | (N,E1) | (E1,R2) | | 674 | E2 | R2 | N | 3 | 2 | 3 | Yes | 675 | | | | (N,R2) | (N,E2) | (E2,R2) | | 676 +--------+----------+-------+--------+--------+---------+-----------+ 678 Table 7: Computing Node-protected PQ-nodes for nexthop E1 and E2 680 In SPF implementations that also produce a list of links and nodes 681 traversed on the shortest path(s) from a given root to others, the 682 tunnel-repair paths from the computing router to candidate PQ-node 683 can be examined to ensure that none of the primary nexthop nodes is 684 traversed. PQ-nodes that provide one (or more) Tunnel-repair 685 paths(s) that does not traverse any of the primary nexthop nodes, are 686 to be considered as node-protecting PQ-nodes. Table 8 below shows 687 the possible tunnel-repair paths to PQ-node R2. 689 +--------------+------------+-------------------+-------------------+ 690 | Primary-NH | PQ-Node | Tunnel-Repair | Exclude All | 691 | (E) | (Y) | Paths | Primary-NH | 692 +--------------+------------+-------------------+-------------------+ 693 | E1, E2 | R2 | S==>N==>R1==>R2 | Yes | 694 +--------------+------------+-------------------+-------------------+ 696 Table 8: Tunnel-Repair paths to PQ-node R2 698 From Table 7 and Table 8, in the above example, R2 being node- 699 protecting PQ-node for both primary nexthops E1 and E2, should be 700 chosen as the node-protecting PQ-node for destinations D1 and D2 that 701 are both reachable via primary nexthop nodes E1 and E2. 703 Next, to find a node-protecting R-LFA path from node-protecting PQ- 704 node to destinations D1 and D2, inequalities specified in Figure 6 705 should be evaluated, to ensure if R2 provides a node-protecting R-LFA 706 path for each of these destinations, as shown below in Table 9. For 707 a R-LFA path to qualify as node-protecting R-LFA path for a 708 destination with multiple ECMP primary nexthop nodes, the R-LFA path 709 from the PQ-node to the destination MUST satisfy the inequality for 710 all primary nexthop nodes. 712 +----------+----------+-------+--------+--------+--------+----------+ 713 | Destinat | Primary- | PQ- | D_opt | D_opt | D_opt | Conditio | 714 | ion (D) | NH (E) | Node | (Y, D) | (Y, E) | (E, D) | n Met | 715 | | | (Y) | | | | | 716 +----------+----------+-------+--------+--------+--------+----------+ 717 | D1 | E1 | R2 | 3 (R2, | 2 (R2, | 1 (E1, | No | 718 | | | | D1) | E1) | D1) | | 719 | D1 | E2 | R2 | 3 (R2, | 3 (R2, | 2 (E2, | Yes | 720 | | | | D1) | E2) | D1) | | 721 | D2 | E1 | R2 | 2 (R2, | 2 (R2, | 2 (E1, | Yes | 722 | | | | D2) | E1) | D2) | | 723 | D2 | E2 | R2 | 2 (R2, | 2 (R2, | 3 (E2, | Yes | 724 | | | | D2) | E2) | D2) | | 725 +----------+----------+-------+--------+--------+--------+----------+ 727 Table 9: Finding node-protecting R-LFA path for destinations D1 and 728 D2 730 In SPF implementations that also produce a list of links and nodes 731 traversed on the shortest path(s) from a given root to others, the 732 R-LFA paths via node-protecting PQ-node to final destination can be 733 examined to ensure that none of the primary nexthop nodes is 734 traversed. R-LFA path(s) that does not traverse any of the primary 735 nexthop nodes, guarantees node-protection in the event of failure of 736 any of the primary nexthop nodes. Table 10 below shows the possible 737 R-LFA-paths for destinations D1 and D2 via the node-protecting PQ- 738 node R2. 740 +-------------+------------+---------+-----------------+------------+ 741 | Destination | Primary-NH | PQ-Node | R-LFA Paths | Exclude | 742 | (D) | (E) | (Y) | | All | 743 | | | | | Primary-NH | 744 +-------------+------------+---------+-----------------+------------+ 745 | D1 | E1, E2 | R2 | S==>N==>R1==>R2 | No | 746 | | | | -->R3-->E1-->D1 | | 747 | | | | | | 748 | D2 | E1, E2 | R2 | S==>N==>R1==>R2 | Yes | 749 | | | | -->R3-->D2 | | 750 +-------------+------------+---------+-----------------+------------+ 752 Table 10: R-LFA paths for destinations D1 and D2 754 From Table 9 and Table 10, in the example above, the R-LFA path from 755 R2 does not meet the node-protecting inequality for destination D1, 756 while it does meet the same inequality for destination D2. And so, 757 while R2 provides node-protecting R-LFA alternate for D2, it fails to 758 provide node-protection for destination D1. Finally, while it is 759 possible to get a node-protecting R-LFA path for D2, no such node- 760 protecting R-LFA path can be found for D1. 762 2.3.4. Limiting extra computational overhead 764 In addition to the extra reverse SPF computations suggested by the 765 Remote-LFA [RFC7490] draft (one reverse SPF for each of the directly 766 connected neighbors), this document proposes a forward SPF 767 computations for each PQ-node discovered in the network. Since the 768 average number of PQ-nodes found in any network is considerably more 769 than the number of direct neighbors of the computing router, the 770 proposal of running one forward SPF per PQ-node may add considerably 771 to the overall SPF computation time. 773 To limit the computational overhead of the approach proposed, this 774 document specifies that implementations MUST choose a subset from the 775 entire set of PQ-nodes computed in the network, with a finite limit 776 on the number of PQ-nodes in the subset. Implementations MUST choose 777 a default value for this limit and may provide user with a 778 configuration knob to override the default limit. This document 779 suggests 16 as a default value for this limit. Implementations MUST 780 also evaluate some default preference criteria while considering a 781 PQ-node in this subset. The exact default preference criteria to be 782 used is outside the scope of this document, and is a matter of 783 implementation. Finally, implementations MAY also allow the user to 784 override the default preference criteria, by providing a policy 785 configuration for the same. 787 This document proposes that implementations SHOULD use a default 788 preference criteria for PQ-node selection which will put a score on 789 each PQ-node, proportional to the number of primary interfaces for 790 which it provides coverage, its distance from the computing router, 791 and its router-id (or system-id in case of IS-IS). PQ-nodes that 792 cover more primary interfaces SHOULD be preferred over PQ-nodes that 793 cover fewer primary interfaces. When two or more PQ-nodes cover the 794 same number of primary interfaces, PQ-nodes which are closer (based 795 on metric) to the computing router SHOULD be preferred over PQ-nodes 796 farther away from it. For PQ-nodes that cover the same number of 797 primary interfaces and are the same distance from the computing 798 router, the PQ-node with smaller router-id (or system-id in case of 799 IS-IS) SHOULD be preferred. 801 Once a subset of PQ-nodes is found, computing router shall run a 802 forward SPF on each of the PQ-nodes in the subset to continue with 803 procedures proposed in Section 2.3.2. 805 3. Manageability of Remote-LFA Alternate Paths 807 3.1. The Problem 809 With the regular Remote-LFA [RFC7490] functionality the computing 810 router may compute more than one PQ-node as usable Remote-LFA 811 alternate nexthops. Additionally [RFC7916] specifies a LFA (and 812 Remote-LFA) manageability framework, in which an alternate selection 813 policy may be configured to let the network operator choose one of 814 them as the most appropriate Remote-LFA alternate. For such policy- 815 based alternate selection to run, the computing router needs to 816 collect all the relevant path characteristics (as specified in 817 section 6.2.4 of [RFC7916]) for each of the alternate paths (one 818 through each of the PQ-nodes). As mentioned before in Section 2.3 819 the R-LFA alternate path through a given PQ-node to a given 820 destination is comprised of two path segments. Section 6.2.5.4 of 821 [RFC7916] specifies that any kind of alternate selection policy must 822 consider path characteristics for both path segments while evaluating 823 one or more RLFA alternate path(s). 825 The first path segment (i.e. from the computing router to the PQ- 826 node) can be calculated from the regular forward SPF done as part of 827 standard and remote LFA computations. However without the mechanism 828 proposed in Section 2.3.2 of this document, there is no way to 829 determine the path characteristics for the second path segment (i.e. 830 from the PQ-node to the destination). In the absence of the path 831 characteristics for the second path segment, two Remote-LFA alternate 832 paths may be equally preferred based on the first path segments 833 characteristics only, although the second path segment attributes may 834 be different. 836 3.2. The Solution 838 The additional forward SPF computation proposed in Section 2.3.2 839 document shall also collect links, nodes and path characteristics 840 along the second path segment. This shall enable collection of 841 complete path characteristics for a given Remote-LFA alternate path 842 to a given destination. The complete alternate path characteristics 843 shall then facilitate more accurate alternate path selection while 844 running the alternate selection policy. 846 As already specified in Section 2.3.4 to limit the computational 847 overhead of the proposed approach, forward SPF computations must be 848 run on a selected subset from the entire set of PQ-nodes computed in 849 the network, with a finite limit on the number of PQ-nodes in the 850 subset. The detailed suggestion on how to select this subset is 851 specified in the same section. While this limits the number of 852 possible alternate paths provided to the alternate-selection policy, 853 this is needed to keep the computational complexity within affordable 854 limits. However if the alternate-selection policy is very 855 restrictive this may leave few destinations in the entire topology 856 without protection. Yet this limitation provides a necessary 857 tradeoff between extensive coverage and immense computational 858 overhead. 860 The mechanism proposed in this section does not modify or invalidate 861 [RFC7916] or any parts of it. This document specifies a mechanism to 862 meet the requirements specified in section 6.5.2.4 in [RFC7916]. 864 4. Acknowledgements 866 Many thanks to Bruno Decraene for providing his useful comments. We 867 would also like to thank Uma Chunduri for reviewing this document and 868 providing valuable feedback. Also, many thanks to Harish Raghuveer 869 for his review and comments on the initial versions of this document. 871 5. IANA Considerations 873 N/A. - No protocol changes are proposed in this document. 875 6. Security Considerations 877 This document does not introduce any change in any of the protocol 878 specifications. It simply proposes to run an extra SPF rooted on 879 each PQ-node discovered in the whole network. 881 7. References 883 7.1. Normative References 885 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 886 Requirement Levels", BCP 14, RFC 2119, 887 DOI 10.17487/RFC2119, March 1997, 888 . 890 [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for 891 IP Fast Reroute: Loop-Free Alternates", RFC 5286, 892 DOI 10.17487/RFC5286, September 2008, 893 . 895 [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. 896 So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", 897 RFC 7490, DOI 10.17487/RFC7490, April 2015, 898 . 900 7.2. Informative References 902 [RFC7916] Litkowski, S., Ed., Decraene, B., Filsfils, C., Raza, K., 903 Horneffer, M., and P. Sarkar, "Operational Management of 904 Loop-Free Alternates", RFC 7916, DOI 10.17487/RFC7916, 905 July 2016, . 907 Authors' Addresses 909 Pushpasis Sarkar (editor) 910 Individual Contributor 912 Email: pushpasis.ietf@gmail.com 914 Shraddha Hegde 915 Juniper Networks, Inc. 916 Electra, Exora Business Park 917 Bangalore, KA 560103 918 India 920 Email: shraddha@juniper.net 921 Chris Bowers 922 Juniper Networks, Inc. 923 1194 N. Mathilda Ave. 924 Sunnyvale, CA 94089 925 US 927 Email: cbowers@juniper.net 929 Hannes Gredler 930 RtBrick, Inc. 932 Email: hannes@rtbrick.com 934 Stephane Litkowski 935 Orange 937 Email: stephane.litkowski@orange.com