idnits 2.17.1 draft-ietf-rtgwg-rlfa-node-protection-13.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 2624 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-13 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 an extension to the Remote Loop-Free based IP 24 fast reroute mechanisms, that specifes procedures for determining if 25 a given PQ-node provides node-protection for a specific destination 26 or not. The document also shows how the same procedure can be 27 utilized for collection of complete characteristics for alternate 28 paths. Knowledge about the characteristics of all alternate path is 29 precursory to apply operator defined policy for eliminating paths not 30 fitting constraints. 32 Requirements Language 34 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 35 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 36 document are to be interpreted as described in RFC2119 [RFC2119]. 38 Status of This Memo 40 This Internet-Draft is submitted in full conformance with the 41 provisions of BCP 78 and BCP 79. 43 Internet-Drafts are working documents of the Internet Engineering 44 Task Force (IETF). Note that other groups may also distribute 45 working documents as Internet-Drafts. The list of current Internet- 46 Drafts is at http://datatracker.ietf.org/drafts/current/. 48 Internet-Drafts are draft documents valid for a maximum of six months 49 and may be updated, replaced, or obsoleted by other documents at any 50 time. It is inappropriate to use Internet-Drafts as reference 51 material or to cite them other than as "work in progress." 53 This Internet-Draft will expire on July 24, 2017. 55 Copyright Notice 57 Copyright (c) 2017 IETF Trust and the persons identified as the 58 document authors. All rights reserved. 60 This document is subject to BCP 78 and the IETF Trust's Legal 61 Provisions Relating to IETF Documents 62 (http://trustee.ietf.org/license-info) in effect on the date of 63 publication of this document. Please review these documents 64 carefully, as they describe your rights and restrictions with respect 65 to this document. Code Components extracted from this document must 66 include Simplified BSD License text as described in Section 4.e of 67 the Trust Legal Provisions and are provided without warranty as 68 described in the Simplified BSD License. 70 Table of Contents 72 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 73 1.1. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 3 74 2. Node Protection with Remote-LFA . . . . . . . . . . . . . . . 4 75 2.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 4 76 2.2. Additional Definitions . . . . . . . . . . . . . . . . . 6 77 2.2.1. Link-Protecting Extended P-Space . . . . . . . . . . 6 78 2.2.2. Node-Protecting Extended P-Space . . . . . . . . . . 6 79 2.2.3. Q-Space . . . . . . . . . . . . . . . . . . . . . . . 7 80 2.2.4. Link-Protecting PQ Space . . . . . . . . . . . . . . 7 81 2.2.5. Candidate Node-Protecting PQ Space . . . . . . . . . 7 82 2.2.6. Cost-Based Definitions . . . . . . . . . . . . . . . 7 83 2.2.6.1. Link-Protecting Extended P-Space . . . . . . . . 7 84 2.2.6.2. Node-Protecting Extended P-Space . . . . . . . . 8 85 2.2.6.3. Q-Space . . . . . . . . . . . . . . . . . . . . . 9 86 2.3. Computing Node-protecting R-LFA Path . . . . . . . . . . 9 87 2.3.1. Computing Candidate Node-protecting PQ-Nodes for 88 Primary nexthops . . . . . . . . . . . . . . . . . . 9 89 2.3.2. Computing node-protecting paths from PQ-nodes to 90 destinations . . . . . . . . . . . . . . . . . . . . 11 91 2.3.3. Computing Node-Protecting R-LFA Paths for 92 Destinations with ECMP primary nexthop nodes . . . . 13 93 2.3.4. Limiting extra computational overhead . . . . . . . . 17 94 3. Manageability of Remote-LFA Alternate Paths . . . . . . . . . 18 95 3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 18 96 3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 19 97 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 19 98 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 99 6. Security Considerations . . . . . . . . . . . . . . . . . . . 19 100 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 20 101 7.1. Normative References . . . . . . . . . . . . . . . . . . 20 102 7.2. Informative References . . . . . . . . . . . . . . . . . 20 103 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 105 1. Introduction 107 The Remote-LFA [RFC7490] specification provides loop-free alternates 108 that guarantee only link-protection. The resulting Remote-LFA 109 alternate nexthops (also referred to as the PQ-nodes) may not provide 110 node-protection for all destinations covered by the same Remote-LFA 111 alternate, in case of failure of the primary nexthop node. Neither 112 does the specification provide a means to determine the same. 114 Also, the LFA Manageability [RFC7916] document requires a computing 115 router to find all possible (including all possible Remote-LFA) 116 alternate nexthops, collect the complete set of path characteristics 117 for each alternate path, run an alternate-selection policy 118 (configured by the operator) and find the best alternate path. This 119 will require the Remote-LFA implementation to gather all the required 120 path characteristics along each link on the entire Remote-LFA 121 alternate path. 123 With current LFA [RFC5286] and Remote-LFA implementations, the 124 forward SPF (and reverse SPF) is run with the computing router and 125 its immediate 1-hop routers as the roots. While that enables 126 computation of path attributes (e.g. SRLG, Admin-groups) for first 127 alternate path segment from the computing router to the PQ-node, 128 there is no means for the computing router to gather any path 129 attributes for the path segment from the PQ-node to destination. 130 Consequently any policy-based selection of alternate paths will 131 consider only the path attributes from the computing router up until 132 the PQ-node. 134 This document describes a procedure for determining node-protection 135 with Remote-LFA. The same procedure is also extended for collection 136 of a complete set of path attributes, enabling more accurate policy- 137 based selection for alternate paths obtained with Remote-LFA. 139 1.1. Abbreviations 141 This document uses the following list of abbreviations. 143 LFA - Loop Free Alternates 144 RLFA or R-LFA - Remote Loop Free Alternates 146 ECMP - Equal Cost Multiple Path 148 SPF - Shortest Path First graph computations 150 NH - Next Hop node 152 2. Node Protection with Remote-LFA 154 Node-protection is required to provide protection of traffic on a 155 given forwarding node, against the failure of the first-hop node on 156 the primary forwarding path. Such protection becomes more critical 157 in the absence of mechanisms like non-stop-routing in the network. 158 Certain operators refrain from deploying non-stop-routing in their 159 network, due to the required complex state synchronization between 160 redundant control plane hardwares it requires, and the significant 161 additional performance complexities it hence introduces. In such 162 cases node-protection is essential to guarantee un-interrupted flow 163 of traffic, even in the case of an entire forwarding node going down. 165 The following sections discuss the node-protection problem in the 166 context of Remote-LFA and propose a solution. 168 2.1. The Problem 170 To better illustrate the problem and the solution proposed in this 171 document the following topology diagram from the Remote-LFA [RFC7490] 172 draft is being re-used with slight modification. 174 D1 175 / 176 S-x-E 177 / \ 178 N R3--D2 179 \ / 180 R1---R2 182 Figure 1: Topology 1 184 In the above topology, for all (non-ECMP) destinations reachable via 185 the S-E link there is no standard LFA alternate. As per the Remote- 186 LFA [RFC7490] alternate specifications node R2 being the only PQ-node 187 for the S-E link provides nexthop for all the above destinations. 188 Table 1 below, shows all possible primary and Remote-LFA alternate 189 paths for each destination. 191 +-------------+--------------+---------+-------------------------+ 192 | Destination | Primary Path | PQ-node | Remote-LFA Backup Path | 193 +-------------+--------------+---------+-------------------------+ 194 | R3 | S->E->R3 | R2 | S=>N=>R1=>R2->R3 | 195 | E | S->E | R2 | S=>N=>R1=>R2->R3->E | 196 | D1 | S->E->D1 | R2 | S=>N=>R1=>R2->R3->E->D1 | 197 | D2 | S->E->R3->D2 | R2 | S=>N=>R1=>R2->R3->D2 | 198 +-------------+--------------+---------+-------------------------+ 200 Table 1: Remote-LFA backup paths via PQ-node R2 202 A closer look at Table 1 shows that, while the PQ-node R2 provides 203 link-protection for all the destinations, it does not provide node- 204 protection for destinations E and D1. In the event of the node- 205 failure on primary nexthop E, the alternate path from Remote-LFA 206 nexthop R2 to E and D1 also becomes unavailable. So for a Remote-LFA 207 nexthop to provide node-protection for a given destination, it is 208 mandatory that, the shortest path from the given PQ-node to the given 209 destination MUST NOT traverse the primary nexthop. 211 In another extension of the topology in Figure 1 let us consider an 212 additional link between N and E with the same cost as the other 213 links. 215 D1 216 / 217 S-x-E 218 / / \ 219 N---+ R3--D2 220 \ / 221 R1---R2 223 Figure 2: Topology 2 225 In the above topology, the S-E link is no more on any of the shortest 226 paths from N to R3, E and D1. Hence R3, E and D1 are also included 227 in both the Extended-P space and Q space of E (w.r.t S-E link). 228 Table 2 below, shows all possible primary and R-LFA alternate paths 229 via PQ-node R3, for each destination reachable through the S-E link 230 in the above topology. The R-LFA alternate paths via PQ-node R2 231 remains same as in Table 1. 233 +-------------+--------------+---------+------------------------+ 234 | Destination | Primary Path | PQ-node | Remote-LFA Backup Path | 235 +-------------+--------------+---------+------------------------+ 236 | R3 | S->E->R3 | R3 | S=>N=>E=>R3 | 237 | E | S->E | R3 | S=>N=>E=>R3->E | 238 | D1 | S->E->D1 | R3 | S=>N=>E=>R3->E->D1 | 239 | D2 | S->E->R3->D2 | R3 | S=>N=>E=>R3->D2 | 240 +-------------+--------------+---------+------------------------+ 242 Table 2: Remote-LFA backup paths via PQ-node R3 244 Again a closer look at Table 2 shows that, unlike Table 1, where the 245 single PQ-node R2 provided node-protection for destinations R3 and 246 D2, if we choose R3 as the R-LFA nexthop, it does not provide node- 247 protection for R3 and D2 anymore. If S chooses R3 as the R-LFA 248 nexthop, in the event of the node-failure on primary nexthop E, on 249 the alternate path from S to R-LFA nexthop R3, one of parallel ECMP 250 path between N and R3 also becomes unavailable. So for a Remote-LFA 251 nexthop to provide node-protection for a given destination, it is 252 also mandatory that, the shortest paths from S to the chosen PQ-node 253 MUST NOT traverse the primary nexthop node. 255 2.2. Additional Definitions 257 This document adds and enhances the following definitions extending 258 the ones mentioned in Remote-LFA [RFC7490] specification. 260 2.2.1. Link-Protecting Extended P-Space 262 The Remote-LFA [RFC7490] specification already defines this. The 263 link-protecting extended P-space for a link S-E being protected is 264 the set of routers that are reachable from one or more direct 265 neighbors of S, except primary node E, without traversing the S-E 266 link on any of the shortest paths from the direct neighbor to the 267 router. This MUST exclude any direct neighbor for which there is at 268 least one ECMP path from the direct neighbor traversing the link(S-E) 269 being protected. 271 For a cost-based definition for Link-protecting Extended P-Space 272 refer to Section 2.2.6.1. 274 2.2.2. Node-Protecting Extended P-Space 276 The node-protecting extended P-space for a primary nexthop node E 277 being protected, is the set of routers that are reachable from one or 278 more direct neighbors of S, except primary node E, without traversing 279 the node E. This MUST exclude any direct neighbors for which there 280 is at least one ECMP path from the direct neighbor traversing the 281 node E being protected. 283 For a cost-based definition for Node-protecting Extended P-Space 284 refer to Section 2.2.6.2. 286 2.2.3. Q-Space 288 The Remote-LFA [RFC7490] draft already defines this. The Q-space for 289 a link S-E being protected is the set of nodes that can reach primary 290 node E, without traversing the S-E link on any of the shortest paths 291 from the node itself to primary nexthop E. This MUST exclude any 292 node for which there is at least one ECMP path from the node to the 293 primary nexthop E traversing the link(S-E) being protected. 295 For a cost-based definition for Q-Space refer to Section 2.2.6.3. 297 2.2.4. Link-Protecting PQ Space 299 A node Y is in link-protecting PQ space w.r.t the link (S-E) being 300 protected, if and only if, Y is present in both link-protecting 301 extended P-space and the Q-space for the link being protected. 303 2.2.5. Candidate Node-Protecting PQ Space 305 A node Y is in candidate node-protecting PQ space w.r.t the node (E) 306 being protected, if and only if, Y is present in both node-protecting 307 extended P-space and the Q-space for the link being protected. 309 Please note, that a node Y being in candidate node-protecting PQ- 310 space, does not guarantee that the R-LFA alternate path via the same, 311 in entirety, is unaffected in the event of a node failure of primary 312 nexthop node E. It only guarantees that the path segment from S to 313 PQ-node Y is unaffected by the same failure event. The PQ-nodes in 314 the candidate node-protecting PQ space may provide node protection 315 for only a subset of destinations that are reachable through the 316 corresponding primary link. 318 2.2.6. Cost-Based Definitions 320 This section provides cost-based definitions for some of the terms 321 introduced in Section 2.2 of this document. 323 2.2.6.1. Link-Protecting Extended P-Space 325 Please refer to Section 2.2.1 for a formal definition for Link- 326 protecting Extended P-Space. 328 A node Y is in link-protecting extended P-space w.r.t the link (S-E) 329 being protected, if and only if, there exists at least one direct 330 neighbor of S, Ni, other than primary nexthop E, that satisfies the 331 following condition. 333 D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y) 335 Where, 336 D_opt(A,B) : Distance on most optimum path from A to B. 337 Ni : A direct neighbor of S other than primary 338 nexthop E. 339 Y : The node being evaluated for link-protecting 340 extended P-Space. 342 Figure 3: Link-Protecting Ext-P-Space Condition 344 2.2.6.2. Node-Protecting Extended P-Space 346 Please refer to Section 2.2.2 for a formal definition for Node- 347 protecting Extended P-Space. 349 A node Y is in node-protecting extended P-space w.r.t the node E 350 being protected, if and only if, there exists at least one direct 351 neighbor of S, Ni, other than primary nexthop E, that satisfies the 352 following condition. 354 D_opt(Ni,Y) < D_opt(Ni,E) + D_opt(E,Y) 356 Where, 357 D_opt(A,B) : Distance on most optimum path from A to B. 358 E : The primary nexthop on shortest path from S 359 to destination. 360 Ni : A direct neighbor of S other than primary 361 nexthop E. 362 Y : The node being evaluated for node-protecting 363 extended P-Space. 365 Figure 4: Node-Protecting Ext-P-Space Condition 367 Please note, that a node Y satisfying the condition in Figure 4 above 368 only guarantees that the R-LFA alternate path segment from S via 369 direct neighbor Ni to the node Y is not affected in the event of a 370 node failure of E. It does not yet guarantee that the path segment 371 from node Y to the destination is also unaffected by the same failure 372 event. 374 2.2.6.3. Q-Space 376 Please refer to Section 2.2.3 for a formal definition for Q-Space. 378 A node Y is in Q-space w.r.t the link (S-E) being protected, if and 379 only if, the following condition is satisfied. 381 D_opt(Y,E) < D_opt(S,E) + D_opt(Y,S) 383 Where, 384 D_opt(A,B) : Distance on most optimum path from A to B. 385 E : The primary nexthop on shortest path from S 386 to destination. 387 Y : The node being evaluated for Q-Space. 389 Figure 5: Q-Space Condition 391 2.3. Computing Node-protecting R-LFA Path 393 The R-LFA alternate path through a given PQ-node to a given 394 destination is comprised of two path segments as follows. 396 1. Path segment from the computing router to the PQ-node (Remote-LFA 397 alternate nexthop), and 399 2. Path segment from the PQ-node to the destination being protected. 401 So to ensure a R-LFA alternate path for a given destination provides 402 node-protection we need to ensure that none of the above path 403 segments are affected in the event of failure of the primary nexthop 404 node. Sections Section 2.3.1 and Section 2.3.2 show how this can be 405 ensured. 407 2.3.1. Computing Candidate Node-protecting PQ-Nodes for Primary 408 nexthops 410 To choose a node-protecting R-LFA nexthop for a destination R3, 411 router S needs to consider a PQ-node from the candidate node- 412 protecting PQ-space for the primary nexthop E on shortest path from S 413 to R3. As mentioned in Section 2.2.2, to consider a PQ-node as 414 candidate node-protecting PQ-node, there must be at least one direct 415 neighbor Ni of S, such that all shortest paths from Ni to the PQ-node 416 does not traverse primary nexthop node E. 418 Implementations SHOULD run the inequality in Section 2.2.2 Figure 4 419 for all direct neighbors, other than primary nexthop node E, to 420 determine whether a node Y is a candidate node-protecting PQ-node. 422 All of the metrics needed by this inequality would have been already 423 collected from the forward SPFs rooted at each of direct neighbor S, 424 computed as part of standard LFA [RFC5286] implementation. With 425 reference to the topology in Figure 2, Table 3 below shows how the 426 above condition can be used to determine the candidate node- 427 protecting PQ-space for S-E link (primary nexthop E). 429 +------------+----------+----------+----------+---------+-----------+ 430 | Candidate | Direct | D_opt | D_opt | D_opt | Condition | 431 | PQ-node | Nbr (Ni) | (Ni,Y) | (Ni,E) | (E,Y) | Met | 432 | (Y) | | | | | | 433 +------------+----------+----------+----------+---------+-----------+ 434 | R2 | N | 2 (N,R2) | 1 (N,E) | 2 | Yes | 435 | | | | | (E,R2) | | 436 | R3 | N | 2 (N,R3) | 1 (N,E) | 1 | No | 437 | | | | | (E,R3) | | 438 +------------+----------+----------+----------+---------+-----------+ 440 Table 3: Node-protection evaluation for R-LFA repair tunnel to PQ- 441 node 443 As seen in the above Table 3, R3 does not meet the node-protecting 444 extended-p-space inequality and so, while R2 is in candidate node- 445 protecting PQ space, R3 is not. 447 Some SPF implementations may also produce a list of links and nodes 448 traversed on the shortest path(s) from a given root to others. In 449 such implementations, router S may have executed a forward SPF with 450 each of its direct neighbors as the SPF root, executed as part of the 451 standard LFA [RFC5286] computations. So S may re-use the list of 452 links and nodes collected from the same SPF computations, to decide 453 whether a node Y is a candidate node-protecting PQ-node or not. A 454 node Y shall be considered as a node-protecting PQ-node, if and only 455 if, there is at least one direct neighbor of S, other than the 456 primary nexthop E, for which, the primary nexthop node E does not 457 exist on the list of nodes traversed on any of the shortest paths 458 from the direct neighbor to the PQ-node. Table 4 below is an 459 illustration of the mechanism with the topology in Figure 2. 461 +-----------+-------------------+-----------------+-----------------+ 462 | Candidate | Repair Tunnel | Link-Protection | Node-Protection | 463 | PQ-node | Path(Repairing | | | 464 | | router to PQ- | | | 465 | | node) | | | 466 +-----------+-------------------+-----------------+-----------------+ 467 | R2 | S->N->R1->R2 | Yes | Yes | 468 | R2 | S->E->R3->R2 | No | No | 469 | R3 | S->N->E->R3 | Yes | No | 470 +-----------+-------------------+-----------------+-----------------+ 472 Table 4: Protection of Remote-LFA tunnel to the PQ-node 474 As seen in the above Table 4 while R2 is candidate node-protecting 475 Remote-LFA nexthop for R3 and D2, it is not so for E and D1, since 476 the primary nexthop E is in the shortest path from R2 to E and D1. 478 2.3.2. Computing node-protecting paths from PQ-nodes to destinations 480 Once a computing router finds all the candidate node-protecting PQ- 481 nodes for a given directly attached primary link, it shall follow the 482 procedure as proposed in this section, to choose one or more node- 483 protecting R-LFA paths, for destinations reachable through the same 484 primary link in the primary SPF graph. 486 To find a node-protecting R-LFA path for a given destination, the 487 computing router needs to pick a subset of PQ-nodes from the 488 candidate node-protecting PQ-space for the corresponding primary 489 nexthop, such that all the path(s) from the PQ-node(s) to the given 490 destination remain unaffected in the event of a node failure of the 491 primary nexthop node. To determine whether a given PQ-node belongs 492 to such a subset of PQ-nodes, the computing router MUST ensure that 493 none of the primary nexthop node are found on any of the shortest 494 paths from the PQ-node to the given destination. 496 This document proposes an additional forward SPF computation for each 497 of the PQ-nodes, to discover all shortest paths from the PQ-nodes to 498 the destination. This will help determine, if a given primary 499 nexthop node is on the shortest paths from the PQ-node to the given 500 destination or not. To determine if a given candidate node- 501 protecting PQ-node provides node-protecting alternate for a given 502 destination, or not, all the shortest paths from the PQ-node to the 503 given destination has to be inspected, to check if the primary 504 nexthop node is found on any of these shortest paths. To compute all 505 the shortest paths from a candidate node-protecting PQ-node to one 506 (or more) destination, the computing router MUST run the forward SPF 507 on the candidate node-protecting PQ-node. Soon after running the 508 forward SPF, the computer router SHOULD run the inequality in 509 Figure 6 below, once for each destination. A PQ-node that does not 510 qualify the condition for a given destination, does not guarantee 511 node-protection for the path segment from the PQ-node to the specific 512 destination. 514 D_opt(Y,D) < D_opt(Y,E) + Distance_opt(E,D) 516 Where, 517 D_opt(A,B) : Distance on most optimum path from A to B. 518 D : The destination node. 519 E : The primary nexthop on shortest path from S 520 to destination. 521 Y : The node-protecting PQ-node being evaluated 523 Figure 6: Node-Protecting Condition for PQ-node to Destination 525 All of the above metric costs except D_opt(Y, D), can be obtained 526 with forward and reverse SPFs with E(the primary nexthop) as the 527 root, run as part of the regular LFA and Remote-LFA implementation. 528 The Distance_opt(Y, D) metric can only be determined by the 529 additional forward SPF run with PQ-node Y as the root. With 530 reference to the topology in Figure 2, Table 5 below shows how the 531 above condition can be used to determine node-protection with node- 532 protecting PQ-node R2. 534 +-------------+------------+---------+--------+---------+-----------+ 535 | Destination | Primary-NH | D_opt | D_opt | D_opt | Condition | 536 | (D) | (E) | (Y, D) | (Y, E) | (E, D) | Met | 537 +-------------+------------+---------+--------+---------+-----------+ 538 | R3 | E | 1 | 2 | 1 | Yes | 539 | | | (R2,R3) | (R2,E) | (E,R3) | | 540 | E | E | 2 | 2 | 0 (E,E) | No | 541 | | | (R2,E) | (R2,E) | | | 542 | D1 | E | 3 | 2 | 1 | No | 543 | | | (R2,D1) | (R2,E) | (E,D1) | | 544 | D2 | E | 2 | 2 | 1 | Yes | 545 | | | (R2,D2) | (R2,E) | (E,D2) | | 546 +-------------+------------+---------+--------+---------+-----------+ 548 Table 5: Node-protection evaluation for R-LFA path segment between 549 PQ-node and destination 551 As seen in the above example above, R2 does not meet the node- 552 protecting inequality for destination E, and D1. And so, once again, 553 while R2 is a node-protecting Remote-LFA nexthop for R3 and D2, it is 554 not so for E and D1. 556 In SPF implementations that also produce a list of links and nodes 557 traversed on the shortest path(s) from a given root to others, the 558 inequality in Figure 6 above need not be evaluated. Instead, to 559 determine whether a PQ-node provides node-protection for a given 560 destination or not, the list of nodes computed from forward SPF run 561 on the PQ-node, for the given destination, SHOULD be inspected. In 562 case the list contains the primary nexthop node, the PQ-node does not 563 provide node-protection. Else, the PQ-node guarantees node- 564 protecting alternate for the given destination. Below is an 565 illustration of the mechanism with candidate node-protecting PQ-node 566 R2 in the topology in Figure 2. 568 +-------------+-----------------+-----------------+-----------------+ 569 | Destination | Shortest Path | Link-Protection | Node-Protection | 570 | | (Repairing | | | 571 | | router to PQ- | | | 572 | | node) | | | 573 +-------------+-----------------+-----------------+-----------------+ 574 | R3 | R2->R3 | Yes | Yes | 575 | E | R2->R3->E | Yes | No | 576 | D1 | R2->R3->E->D1 | Yes | No | 577 | D2 | R2->R3->D2 | Yes | Yes | 578 +-------------+-----------------+-----------------+-----------------+ 580 Table 6: Protection of Remote-LFA path between PQ-node and 581 destination 583 As seen in the above example while R2 is candidate node-protecting 584 R-LFA nexthop for R3 and D2, it is not so for E and D1, since the 585 primary nexthop E is in the shortest path from R2 to E and D1. 587 The procedure described in this document helps no more than to 588 determine whether a given Remote-LFA alternate provides node- 589 protection for a given destination or not. It does not find out any 590 new Remote-LFA alternate nexthops, outside the ones already computed 591 by standard Remote-LFA procedure. However, in case of availability 592 of more than one PQ-node (Remote-LFA alternates) for a destination, 593 and node-protection is required for the given primary nexthop, this 594 procedure will eliminate the PQ-nodes that do not provide node- 595 protection and choose only the ones that does. 597 2.3.3. Computing Node-Protecting R-LFA Paths for Destinations with ECMP 598 primary nexthop nodes 600 In certain scenarios, when one or more destinations maybe reachable 601 via multiple ECMP (equal-cost-multi-path) nexthop nodes, and only 602 link-protection is required, there is no need to compute any 603 alternate paths for such destinations. In the event of failure of 604 one of the nexthop links, the remaining primary nexthops shall always 605 provide link-protection. However, if node-protection is required, 606 the rest of the primary nexthops may not guarantee node-protection. 607 Figure 7 below shows one such example topology. 609 D1 610 2 / 611 S---x---E1 612 / \ / \ 613 / x / \ 614 / \ / \ 615 N-------E2 R3--D2 616 \ 2 / 617 \ / 618 \ / 619 R1-------R2 620 2 622 Primary Nexthops: 623 Destination D1 = [{ S-E1, E1}, {S-E2, E2}] 624 Destination D2 = [{ S-E1, E1}, {S-E2, E2}] 626 Figure 7: Topology with multiple ECMP primary nexthops 628 In the above example topology, costs of all links are 1, except the 629 following links: 631 Link: S-E1, Cost: 2 633 Link: N-E2: Cost: 2 635 Link: R1-R2: Cost: 2 637 In the above topology, on computing router S, destinations D1 and D2 638 are reachable via two ECMP nexthop nodes E1 and E2. However the 639 primary paths via nexthop node E2 also traverses via the nexthop node 640 E1. So in the event of node failure of nexthop node E1, both primary 641 paths (via E1 and E2) becomes unavailable. Hence if node-protection 642 is desired for destinations D1 and D2, alternate paths that does not 643 traverse any of the primary nexthop nodes E1 and E2, need to be 644 computed. In the above topology the only alternate neighbor N does 645 not provide such a LFA alternate path. Hence one (or more) R-LFA 646 node-protecting alternate paths for destinations D1 and D2, needs to 647 be computed. 649 In the above topology, following are the link-protecting PQ-nodes. 651 Primary Nexthop: E1, Link-Protecting PQ-Node: { R2 } 653 Primary Nexthop: E2, Link-Protecting PQ-Node: { R2 } 655 To find one (or more) node-protecting R-LFA paths for destinations D1 656 and D2, one (or more) node-protecting PQ-node(s) needs to be 657 determined first. Inequalities specified in Section 2.2.6.2 and 658 Section 2.2.6.3 can be evaluated to compute the node-protecting PQ- 659 space for each of the nexthop nodes E1 and E2, as shown in Table 7 660 below. To select a PQ-node as node-protecting PQ-node for a 661 destination with multiple primary nexthop nodes, the PQ-node MUST 662 satisfy the inequality for all primary nexthop nodes. Any PQ-node 663 which is NOT node-protecting PQ-node for all the primary nexthop 664 nodes, MUST NOT be chosen as the node-protecting PQ-node for 665 destination. 667 +--------+----------+-------+--------+--------+---------+-----------+ 668 | Primar | Candidat | Direc | D_opt | D_opt | D_opt | Condition | 669 | y Next | e PQ- | t Nbr | (Ni,Y) | (Ni,E) | (E,Y) | Met | 670 | hop | node (Y) | (Ni) | | | | | 671 | (E) | | | | | | | 672 +--------+----------+-------+--------+--------+---------+-----------+ 673 | E1 | R2 | N | 3 | 3 | 2 | Yes | 674 | | | | (N,R2) | (N,E1) | (E1,R2) | | 675 | E2 | R2 | N | 3 | 2 | 3 | Yes | 676 | | | | (N,R2) | (N,E2) | (E2,R2) | | 677 +--------+----------+-------+--------+--------+---------+-----------+ 679 Table 7: Computing Node-protected PQ-nodes for nexthop E1 and E2 681 In SPF implementations that also produce a list of links and nodes 682 traversed on the shortest path(s) from a given root to others, the 683 tunnel-repair paths from the computing router to candidate PQ-node 684 can be examined to ensure that none of the primary nexthop nodes is 685 traversed. PQ-nodes that provide one (or more) Tunnel-repair 686 paths(s) that does not traverse any of the primary nexthop nodes, are 687 to be considered as node-protecting PQ-nodes. Table 8 below shows 688 the possible tunnel-repair paths to PQ-node R2. 690 +--------------+------------+-------------------+-------------------+ 691 | Primary-NH | PQ-Node | Tunnel-Repair | Exclude All | 692 | (E) | (Y) | Paths | Primary-NH | 693 +--------------+------------+-------------------+-------------------+ 694 | E1, E2 | R2 | S==>N==>R1==>R2 | Yes | 695 +--------------+------------+-------------------+-------------------+ 697 Table 8: Tunnel-Repair paths to PQ-node R2 699 From Table 7 and Table 8, in the above example, R2 being node- 700 protecting PQ-node for both primary nexthops E1 and E2, should be 701 chosen as the node-protecting PQ-node for destinations D1 and D2 that 702 are both reachable via primary nexthop nodes E1 and E2. 704 Next, to find a node-protecting R-LFA path from node-protecting PQ- 705 node to destinations D1 and D2, inequalities specified in Figure 6 706 should be evaluated, to ensure if R2 provides a node-protecting R-LFA 707 path for each of these destinations, as shown below in Table 9. For 708 a R-LFA path to qualify as node-protecting R-LFA path for a 709 destination with multiple ECMP primary nexthop nodes, the R-LFA path 710 from the PQ-node to the destination MUST satisfy the inequality for 711 all primary nexthop nodes. 713 +----------+----------+-------+--------+--------+--------+----------+ 714 | Destinat | Primary- | PQ- | D_opt | D_opt | D_opt | Conditio | 715 | ion (D) | NH (E) | Node | (Y, D) | (Y, E) | (E, D) | n Met | 716 | | | (Y) | | | | | 717 +----------+----------+-------+--------+--------+--------+----------+ 718 | D1 | E1 | R2 | 3 (R2, | 2 (R2, | 1 (E1, | No | 719 | | | | D1) | E1) | D1) | | 720 | D1 | E2 | R2 | 3 (R2, | 3 (R2, | 2 (E2, | Yes | 721 | | | | D1) | E2) | D1) | | 722 | D2 | E1 | R2 | 2 (R2, | 2 (R2, | 2 (E1, | Yes | 723 | | | | D2) | E1) | D2) | | 724 | D2 | E2 | R2 | 2 (R2, | 2 (R2, | 3 (E2, | Yes | 725 | | | | D2) | E2) | D2) | | 726 +----------+----------+-------+--------+--------+--------+----------+ 728 Table 9: Finding node-protecting R-LFA path for destinations D1 and 729 D2 731 In SPF implementations that also produce a list of links and nodes 732 traversed on the shortest path(s) from a given root to others, the 733 R-LFA paths via node-protecting PQ-node to final destination can be 734 examined to ensure that none of the primary nexthop nodes is 735 traversed. R-LFA path(s) that does not traverse any of the primary 736 nexthop nodes, guarantees node-protection in the event of failure of 737 any of the primary nexthop nodes. Table 10 below shows the possible 738 R-LFA-paths for destinations D1 and D2 via the node-protecting PQ- 739 node R2. 741 +-------------+------------+---------+-----------------+------------+ 742 | Destination | Primary-NH | PQ-Node | R-LFA Paths | Exclude | 743 | (D) | (E) | (Y) | | All | 744 | | | | | Primary-NH | 745 +-------------+------------+---------+-----------------+------------+ 746 | D1 | E1, E2 | R2 | S==>N==>R1==>R2 | No | 747 | | | | -->R3-->E1-->D1 | | 748 | | | | | | 749 | D2 | E1, E2 | R2 | S==>N==>R1==>R2 | Yes | 750 | | | | -->R3-->D2 | | 751 +-------------+------------+---------+-----------------+------------+ 753 Table 10: R-LFA paths for destinations D1 and D2 755 From Table 9 and Table 10, in the example above, the R-LFA path from 756 R2 does not meet the node-protecting inequality for destination D1, 757 while it does meet the same inequality for destination D2. And so, 758 while R2 provides node-protecting R-LFA alternate for D2, it fails to 759 provide node-protection for destination D1. Finally, while it is 760 possible to get a node-protecting R-LFA path for D2, no such node- 761 protecting R-LFA path can be found for D1. 763 2.3.4. Limiting extra computational overhead 765 In addition to the extra reverse SPF computations suggested by the 766 Remote-LFA [RFC7490] draft (one reverse SPF for each of the directly 767 connected neighbors), this document proposes a forward SPF 768 computations for each PQ-node discovered in the network. Since the 769 average number of PQ-nodes found in any network is considerably more 770 than the number of direct neighbors of the computing router, the 771 proposal of running one forward SPF per PQ-node may add considerably 772 to the overall SPF computation time. 774 To limit the computational overhead of the approach proposed, this 775 document specifies that implementations MUST choose a subset from the 776 entire set of PQ-nodes computed in the network, with a finite limit 777 on the number of PQ-nodes in the subset. Implementations MUST choose 778 a default value for this limit and may provide user with a 779 configuration knob to override the default limit. This document 780 suggests 16 as a default value for this limit. Implementations MUST 781 also evaluate some default preference criteria while considering a 782 PQ-node in this subset. The exact default preference criteria to be 783 used is outside the scope of this document, and is a matter of 784 implementation. Finally, implementations MAY also allow the user to 785 override the default preference criteria, by providing a policy 786 configuration for the same. 788 This document proposes that implementations SHOULD use a default 789 preference criteria for PQ-node selection which will put a score on 790 each PQ-node, proportional to the number of primary interfaces for 791 which it provides coverage, its distance from the computing router, 792 and its router-id (or system-id in case of IS-IS). PQ-nodes that 793 cover more primary interfaces SHOULD be preferred over PQ-nodes that 794 cover fewer primary interfaces. When two or more PQ-nodes cover the 795 same number of primary interfaces, PQ-nodes which are closer (based 796 on metric) to the computing router SHOULD be preferred over PQ-nodes 797 farther away from it. For PQ-nodes that cover the same number of 798 primary interfaces and are the same distance from the computing 799 router, the PQ-node with smaller router-id (or system-id in case of 800 IS-IS) SHOULD be preferred. 802 Once a subset of PQ-nodes is found, computing router shall run a 803 forward SPF on each of the PQ-nodes in the subset to continue with 804 procedures proposed in Section 2.3.2. 806 3. Manageability of Remote-LFA Alternate Paths 808 3.1. The Problem 810 With the regular Remote-LFA [RFC7490] functionality the computing 811 router may compute more than one PQ-node as usable Remote-LFA 812 alternate nexthops. Additionally [RFC7916] specifies a LFA (and 813 Remote-LFA) manageability framework, in which an alternate selection 814 policy may be configured to let the network operator choose one of 815 them as the most appropriate Remote-LFA alternate. For such policy- 816 based alternate selection to run, the computing router needs to 817 collect all the relevant path characteristics (as specified in 818 section 6.2.4 of [RFC7916]) for each of the alternate paths (one 819 through each of the PQ-nodes). As mentioned before in Section 2.3 820 the R-LFA alternate path through a given PQ-node to a given 821 destination is comprised of two path segments. Section 6.2.5.4 of 822 [RFC7916] specifies that any kind of alternate selection policy must 823 consider path characteristics for both path segments while evaluating 824 one or more RLFA alternate path(s). 826 The first path segment (i.e. from the computing router to the PQ- 827 node) can be calculated from the regular forward SPF done as part of 828 standard and remote LFA computations. However without the mechanism 829 proposed in Section 2.3.2 of this document, there is no way to 830 determine the path characteristics for the second path segment (i.e. 831 from the PQ-node to the destination). In the absence of the path 832 characteristics for the second path segment, two Remote-LFA alternate 833 paths may be equally preferred based on the first path segments 834 characteristics only, although the second path segment attributes may 835 be different. 837 3.2. The Solution 839 The additional forward SPF computation proposed in Section 2.3.2 840 document shall also collect links, nodes and path characteristics 841 along the second path segment. This shall enable collection of 842 complete path characteristics for a given Remote-LFA alternate path 843 to a given destination. The complete alternate path characteristics 844 shall then facilitate more accurate alternate path selection while 845 running the alternate selection policy. 847 As already specified in Section 2.3.4 to limit the computational 848 overhead of the proposed approach, forward SPF computations must be 849 run on a selected subset from the entire set of PQ-nodes computed in 850 the network, with a finite limit on the number of PQ-nodes in the 851 subset. The detailed suggestion on how to select this subset is 852 specified in the same section. While this limits the number of 853 possible alternate paths provided to the alternate-selection policy, 854 this is needed to keep the computational complexity within affordable 855 limits. However if the alternate-selection policy is very 856 restrictive this may leave few destinations in the entire topology 857 without protection. Yet this limitation provides a necessary 858 tradeoff between extensive coverage and immense computational 859 overhead. 861 The mechanism proposed in this section does not modify or invalidate 862 [RFC7916] or any parts of it. This document specifies a mechanism to 863 meet the requirements specified in section 6.5.2.4 in [RFC7916]. 865 4. Acknowledgements 867 Many thanks to Bruno Decraene for providing his useful comments. We 868 would also like to thank Uma Chunduri for reviewing this document and 869 providing valuable feedback. Also, many thanks to Harish Raghuveer 870 for his review and comments on the initial versions of this document. 872 5. IANA Considerations 874 N/A. - No protocol changes are proposed in this document. 876 6. Security Considerations 878 This document does not introduce any change in any of the protocol 879 specifications. It simply proposes to run an extra SPF rooted on 880 each PQ-node discovered in the whole network. 882 7. References 884 7.1. Normative References 886 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 887 Requirement Levels", BCP 14, RFC 2119, 888 DOI 10.17487/RFC2119, March 1997, 889 . 891 [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for 892 IP Fast Reroute: Loop-Free Alternates", RFC 5286, 893 DOI 10.17487/RFC5286, September 2008, 894 . 896 [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. 897 So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", 898 RFC 7490, DOI 10.17487/RFC7490, April 2015, 899 . 901 7.2. Informative References 903 [RFC7916] Litkowski, S., Ed., Decraene, B., Filsfils, C., Raza, K., 904 Horneffer, M., and P. Sarkar, "Operational Management of 905 Loop-Free Alternates", RFC 7916, DOI 10.17487/RFC7916, 906 July 2016, . 908 Authors' Addresses 910 Pushpasis Sarkar (editor) 911 Individual Contributor 913 Email: pushpasis.ietf@gmail.com 915 Shraddha Hegde 916 Juniper Networks, Inc. 917 Electra, Exora Business Park 918 Bangalore, KA 560103 919 India 921 Email: shraddha@juniper.net 922 Chris Bowers 923 Juniper Networks, Inc. 924 1194 N. Mathilda Ave. 925 Sunnyvale, CA 94089 926 US 928 Email: cbowers@juniper.net 930 Hannes Gredler 931 RtBrick, Inc. 933 Email: hannes@rtbrick.com 935 Stephane Litkowski 936 Orange 938 Email: stephane.litkowski@orange.com