idnits 2.17.00 (12 Aug 2021) /tmp/idnits18877/draft-ietf-rtgwg-rlfa-node-protection-09.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 ([RFC7490]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (December 23, 2016) is 1974 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: 1 error (**), 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: June 26, 2017 C. Bowers 6 Juniper Networks, Inc. 7 H. Gredler 8 RtBrick, Inc. 9 S. Litkowski 10 Orange 11 December 23, 2016 13 Remote-LFA Node Protection and Manageability 14 draft-ietf-rtgwg-rlfa-node-protection-09 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 described in [RFC7490], that describes 25 procedures for determining if a given PQ-node provides node- 26 protection for a specific destination or not. The document also 27 shows how the same procedure can be utilised for collection of 28 complete characteristics for alternate paths. Knowledge about the 29 characteristics of all alternate path is precursory to apply operator 30 defined policy for eliminating paths not 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 June 26, 2017. 55 Copyright Notice 57 Copyright (c) 2016 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 2. Node Protection with Remote-LFA . . . . . . . . . . . . . . . 3 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 . . . . . . . . . . . . . . . . . . . . . . . 6 79 2.2.4. Link-Protecting PQ Space . . . . . . . . . . . . . . 6 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 . . . . . . . . 7 84 2.2.6.3. Q-Space . . . . . . . . . . . . . . . . . . . . . 8 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. Manageabilty of Remote-LFA Alternate Paths . . . . . . . . . 18 94 3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 18 95 3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 18 97 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 19 98 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 99 6. Security Considerations . . . . . . . . . . . . . . . . . . . 19 100 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 101 7.1. Normative References . . . . . . . . . . . . . . . . . . 19 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, in case of 111 failure of the primary nexthop node. Neither does the specification 112 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 2. Node Protection with Remote-LFA 141 Node-protection is required to provide protection of traffic on a 142 given forwarding node, against the failure of the first-hop node on 143 the primary forwarding path. Such protection becomes more critical 144 in the absence of mechanisms like non-stop-routing in the network. 146 Certain operators refrain from deploying non-stop-routing in their 147 network, due to the required complex state synchronization between 148 redundant control plane hardwares it requires, and the significant 149 additional performance complexities it hence introduces. In such 150 cases node-protection is essential to guarantee un-interrupted flow 151 of traffic, even in the case of an entire forwarding node going down. 153 The following sections discuss the node-protection problem in the 154 context of Remote-LFA and propose a solution. 156 2.1. The Problem 158 To better illustrate the problem and the solution proposed in this 159 document the following topology diagram from the Remote-LFA [RFC7490] 160 draft is being re-used with slight modification. 162 D1 163 / 164 S-x-E 165 / \ 166 N R3--D2 167 \ / 168 R1---R2 170 Figure 1: Topology 1 172 In the above topology, for all (non-ECMP) destinations reachable via 173 the S-E link there is no standard LFA alternate. As per the Remote- 174 LFA [RFC7490] alternate specifications node R2 being the only PQ-node 175 for the S-E link provides nexthop for all the above destinations. 176 Table 1 below, shows all possible primary and Remote-LFA alternate 177 paths for each destination. 179 +-------------+--------------+---------+-------------------------+ 180 | Destination | Primary Path | PQ-node | Remote-LFA Backup Path | 181 +-------------+--------------+---------+-------------------------+ 182 | R3 | S->E->R3 | R2 | S=>N=>R1=>R2->R3 | 183 | E | S->E | R2 | S=>N=>R1=>R2->R3->E | 184 | D1 | S->E->D1 | R2 | S=>N=>R1=>R2->R3->E->D1 | 185 | D2 | S->E->R3->D2 | R2 | S=>N=>R1=>R2->R3->D2 | 186 +-------------+--------------+---------+-------------------------+ 188 Table 1: Remote-LFA backup paths via PQ-node R2 190 A closer look at Table 1 shows that, while the PQ-node R2 provides 191 link-protection for all the destinations, it does not provide node- 192 protection for destinations E and D1. In the event of the node- 193 failure on primary nexthop E, the alternate path from Remote-LFA 194 nexthop R2 to E and D1 also becomes unavailable. So for a Remote-LFA 195 nexthop to provide node-protection for a given destination, it is 196 mandatory that, the shortest path from the given PQ-node to the given 197 destination MUST NOT traverse the primary nexthop. 199 In another extension of the topology in Figure 1 let us consider an 200 additional link between N and E with the same cost as the other 201 links. 203 D1 204 / 205 S-x-E 206 / / \ 207 N---+ R3--D2 208 \ / 209 R1---R2 211 Figure 2: Topology 2 213 In the above topology, the S-E link is no more on any of the shortest 214 paths from N to R3, E and D1. Hence R3, E and D1 are also included 215 in both the Extended-P space and Q space of E (w.r.t S-E link). 216 Table 2 below, shows all possible primary and R-LFA alternate paths 217 via PQ-node R3, for each destination reachable through the S-E link 218 in the above topology. The R-LFA alternate paths via PQ-node R2 219 remains same as in Table 1. 221 +-------------+--------------+---------+------------------------+ 222 | Destination | Primary Path | PQ-node | Remote-LFA Backup Path | 223 +-------------+--------------+---------+------------------------+ 224 | R3 | S->E->R3 | R3 | S=>N=>E=>R3 | 225 | E | S->E | R3 | S=>N=>E=>R3->E | 226 | D1 | S->E->D1 | R3 | S=>N=>E=>R3->E->D1 | 227 | D2 | S->E->R3->D2 | R3 | S=>N=>E=>R3->D2 | 228 +-------------+--------------+---------+------------------------+ 230 Table 2: Remote-LFA backup paths via PQ-node R3 232 Again a closer look at Table 2 shows that, unlike Table 1, where the 233 single PQ-node R2 provided node-protection for destinations R3 and 234 D2, if we choose R3 as the R-LFA nexthop, it does not provide node- 235 protection for R3 and D2 anymore. If S chooses R3 as the R-LFA 236 nexthop, in the event of the node-failure on primary nexthop E, on 237 the alternate path from S to R-LFA nexthop R3, one of parallel ECMP 238 path between N and R3 also becomes unavailable. So for a Remote-LFA 239 nexthop to provide node-protection for a given destination, it is 240 also mandatory that, the shortest path from S to the chosen PQ-node 241 MUST NOT traverse the primary nexthop node. 243 2.2. Additional Definitions 245 This document adds and enhances the following definitions extending 246 the ones mentioned in Remote-LFA [RFC7490] specification. 248 2.2.1. Link-Protecting Extended P-Space 250 The Remote-LFA [RFC7490] specification already defines this. The 251 link-protecting extended P-space for a link S-E being protected is 252 the set of routers that are reachable from one or more direct 253 neighbors of S, except primary node E, without traversing the S-E 254 link on any of the shortest path from the direct neighbor to the 255 router. This MUST exclude any direct neighbor for which there is at 256 least one ECMP path from the direct neighbor traversing the link(S-E) 257 being protected. 259 For a cost-based definition for Link-protecting Extended P-Space 260 refer to Section 2.2.6.1. 262 2.2.2. Node-Protecting Extended P-Space 264 The node-protecting extended P-space for a primary nexthop node E 265 being protected, is the set of routers that are reachable from one or 266 more direct neighbors of S, except primary node E, without traversing 267 the node E. This MUST exclude any direct neighbors for which there 268 is at least one ECMP path from the direct neighbor traversing the 269 node E being protected. 271 For a cost-based definition for Node-protecting Extended P-Space 272 refer to Section 2.2.6.2. 274 2.2.3. Q-Space 276 The Remote-LFA [RFC7490] draft already defines this. The Q-space for 277 a link S-E being protected is the set of routers that can reach 278 primary node E, without traversing the S-E link on any of the 279 shortest path from the node Y to primary nexthop E. This MUST 280 exclude any destination for which there is at least one ECMP path 281 from the node Y to the primary nexthop E traversing the link(S-E) 282 being protected. 284 For a cost-based definition for Q-Space refer to Section 2.2.6.3. 286 2.2.4. Link-Protecting PQ Space 288 A node Y is in link-protecting PQ space w.r.t to the link (S-E) being 289 protected, if and only if, Y is present in both link-protecting 290 extended P-space and the Q-space for the link being protected. 292 2.2.5. Candidate Node-Protecting PQ Space 294 A node Y is in candidate node-protecting PQ space w.r.t to the node 295 (E) being protected, if and only if, Y is present in both node- 296 protecting extended P-space and the Q-space for the link being 297 protected. 299 Please note, that a node Y being in candidate node-protecting PQ- 300 space, does not guarantee that the R-LFA alternate path via the same, 301 in entirety, is unaffected in the event of a node failure of primary 302 nexthop node E. It only guarantees that the path segment from S to 303 PQ-node Y is unaffected by the same failure event. The PQ-nodes in 304 the candidate node-protecting PQ space may provide node protection 305 for only a subset of destinations that are reachable through the 306 corresponding primary link. 308 2.2.6. Cost-Based Definitions 310 This section provides cost-based definitions for some of the terms 311 introduced in Section 2.2 of this document. 313 2.2.6.1. Link-Protecting Extended P-Space 315 Please refer to Section 2.2.1 for a formal definition for Link- 316 protecting Extended P-Space. 318 A node Y is in link-protecting extended P-space w.r.t to the link 319 (S-E) being protected, if and only if, there exists at least one 320 direct neighbor of S, Ni, other than primary nexthop E, that 321 satisfies the following condition. 323 D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y) 325 Where, 326 D_opt(A,B) : Distance on most optimum path from A to B. 327 Ni : A direct neighbor of S other than primary 328 nexthop E. 329 Y : The node being evaluated for link-protecting 330 extended P-Space. 332 Figure 3: Link-Protecting Ext-P-Space Condition 334 2.2.6.2. Node-Protecting Extended P-Space 336 Please refer to Section 2.2.2 for a formal definition for Node- 337 protecting Extended P-Space. 339 A node Y is in node-protecting extended P-space w.r.t to the node E 340 being protected, if and only if, there exists at least one direct 341 neighbor of S, Ni, other than primary nexthop E, that satisfies the 342 following condition. 344 D_opt(Ni,Y) < D_opt(Ni,E) + D_opt(E,Y) 346 Where, 347 D_opt(A,B) : Distance on most optimum path from A to B. 348 E : The primary nexthop on shortest path from S 349 to destination. 350 Ni : A direct neighbor of S other than primary 351 nexthop E. 352 Y : The node being evaluated for node-protecting 353 extended P-Space. 355 Figure 4: Node-Protecting Ext-P-Space Condition 357 Please note, that a node Y satisfying the condition in Figure 4 above 358 only guarantees that the R-LFA alternate path segment from S via 359 direct neighbor Ni to the node Y is not affected in the event of a 360 node failure of E. It does not yet guarantee that the path segment 361 from node Y to the destination is also unaffected by the same failure 362 event. 364 2.2.6.3. Q-Space 366 Please refer to Section 2.2.3 for a formal definition for Q-Space. 368 A node Y is in Q-space w.r.t to the link (S-E) being protected, if 369 and only if, the following condition is satisfied. 371 D_opt(Y,E) < D_opt(S,E) + D_opt(Y,S) 373 Where, 374 D_opt(A,B) : Distance on most optimum path from A to B. 375 E : The primary nexthop on shortest path from S 376 to destination. 377 Y : The node being evaluated for Q-Space. 379 Figure 5: Q-Space Condition 381 2.3. Computing Node-protecting R-LFA Path 383 The R-LFA alternate path through a given PQ-node to a given 384 destination is comprised of two path segments as follows. 386 1. Path segment from the computing router to the PQ-node (Remote-LFA 387 alternate nexthop), and 389 2. Path segment from the PQ-node to the destination being protected. 391 So to ensure a R-LFA alternate path for a given destination provides 392 node-protection we need to ensure that none of the above path 393 segments are affected in the event of failure of the primary nexthop 394 node. Sections Section 2.3.1 and Section 2.3.2 shows how this can be 395 ensured. 397 2.3.1. Computing Candidate Node-protecting PQ-Nodes for Primary 398 nexthops 400 To choose a node-protecting R-LFA nexthop for a destination R3, 401 router S needs to consider a PQ-node from the candidate node- 402 protecting PQ-space for the primary nexthop E on shortest path from S 403 to R3. As mentioned in Section 2.2.2, to consider a PQ-node as 404 candidate node-protecting PQ-node, there must be at least one direct 405 neighbor Ni of S, such that all shortest paths from Ni to the PQ-node 406 does not traverse primary nexthop node E. 408 Implementations SHOULD run the inequality in Section 2.2.2 Figure 4 409 for all direct neighbors, other than primary nexthop node E, to 410 determine whether a node Y is a candidate node-protecting PQ-node. 411 All of the metrics needed by this inequality would have been already 412 collected from the forward SPFs rooted at each of direct neighbor S, 413 computed as part of standard LFA [RFC5286] implementation. With 414 reference to the topology in Figure 2, Table 3 below shows how the 415 above condition can be used to determine the candidate node- 416 protecting PQ-space for S-E link (primary nexthop E). 418 +------------+----------+----------+----------+---------+-----------+ 419 | Candidate | Direct | D_opt | D_opt | D_opt | Condition | 420 | PQ-node | Nbr (Ni) | (Ni,Y) | (Ni,E) | (E,Y) | Met | 421 | (Y) | | | | | | 422 +------------+----------+----------+----------+---------+-----------+ 423 | R2 | N | 2 (N,R2) | 1 (N,E) | 2 | Yes | 424 | | | | | (E,R2) | | 425 | R3 | N | 2 (N,R3) | 1 (N,E) | 1 | No | 426 | | | | | (E,R3) | | 427 +------------+----------+----------+----------+---------+-----------+ 429 Table 3: Node-protection evaluation for R-LFA repair tunnel to PQ- 430 node 432 As seen in the above Table 3, R3 does not meet the node-protecting 433 extended-p-space inequality and so, while R2 is in candidate node- 434 protecting PQ space, R3 is not. 436 Some SPF implementations may also produce a list of links and nodes 437 traversed on the shortest path(s) from a given root to others. In 438 such implementations, router S may have executed a forward SPF with 439 each of its direct neighbors as the SPF root, executed as part of the 440 standard LFA [RFC5286] computations. So S may re-use the list of 441 links and nodes collected from the same SPF computations, to decide 442 whether a node Y is a candidate node-protecting PQ-node or not. A 443 node Y shall be considered as a node-protecting PQ-node, if and only 444 if, there is at least one direct neighbor of S, other than the 445 primary nexthop E, for which, the primary nexthop node E does not 446 exist on the list of nodes traversed on any of the shortest path(s) 447 from the direct neighbor to the PQ-node. Table 4 below is an 448 illustration of the mechanism with the topology in Figure 2. 450 +-----------+-------------------+-----------------+-----------------+ 451 | Candidate | Repair Tunnel | Link-Protection | Node-Protection | 452 | PQ-node | Path(Repairing | | | 453 | | router to PQ- | | | 454 | | node) | | | 455 +-----------+-------------------+-----------------+-----------------+ 456 | R2 | S->N->R1->R2 | Yes | Yes | 457 | R2 | S->E->R3->R2 | No | No | 458 | R3 | S->N->E->R3 | Yes | No | 459 +-----------+-------------------+-----------------+-----------------+ 461 Table 4: Protection of Remote-LFA tunnel to the PQ-node 463 As seen in the above Table 4 while R2 is candidate node-protecting 464 Remote-LFA nexthop for R3 and D2, it is not so for E and D1, since 465 the primary nexthop E is in the shortest path from R2 to E and D1. 467 2.3.2. Computing node-protecting paths from PQ-nodes to destinations 469 Once a computing router finds all the candidate node-protecting PQ- 470 nodes for a given directly attached primary link, it shall follow the 471 procedure as proposed in this section, to choose one or more node- 472 protecting R-LFA paths, for destinations reachable through the same 473 primary link in the primary SPF graph. 475 To find a node-protecting R-LFA path for a given destination, the 476 computing router needs to pick a subset of PQ-nodes from the 477 candidate node-protecting PQ-space for the corresponding primary 478 nexthop, such that all the path(s) from the PQ-node(s) to the given 479 destination remain unaffected in the event of a node failure of the 480 primary nexthop node. To determine wether a given PQ-node belongs to 481 such a subset of PQ-nodes, the computing router MUST ensure that none 482 of the primary nexthop node are found on any of the shortest paths 483 from the PQ-node to the given destination. 485 This document proposes an additional forward SPF computation for each 486 of the PQ-nodes, to discover all shortest paths from the PQ-nodes to 487 the destination. This will help determine, if a given primary 488 nexthop node is on the shortest paths from the PQ-node to the given 489 destination or not. To determine if a given candidate node- 490 protecting PQ-node provides node-protecting alternate for a given 491 destination, or not, all the shortest paths from the PQ-node to the 492 given destination has to be inspected, to check if the primary 493 nexthop node is found on any of these shortest paths. To compute all 494 the shortest paths from a candidate node-protecting PQ-node to one 495 (or more) destination, the computing router MUST run the forward SPF 496 on the candidate node-protecting PQ-node. Soon after running the 497 forward SPF, the computer router SHOULD run the inequality in 498 Figure 6 below, once for each destination. A PQ-node that does not 499 qualify the condition for a given destination, does not guarantee 500 node-protection for the path segment from the PQ-node to the specific 501 destination. 503 D_opt(Y,D) < D_opt(Y,E) + Distance_opt(E,D) 505 Where, 506 D_opt(A,B) : Distance on most optimum path from A to B. 507 D : The destination node. 508 E : The primary nexthop on shortest path from S 509 to destination. 510 Y : The node-protecting PQ-node being evaluated 512 Figure 6: Node-Protecting Condition for PQ-node to Destination 514 All of the above metric costs except D_opt(Y, D), can be obtained 515 with forward and reverse SPFs with E(the primary nexthop) as the 516 root, run as part of the regular LFA and Remote-LFA implementation. 517 The Distance_opt(Y, D) metric can only be determined by the 518 additional forward SPF run with PQ-node Y as the root. With 519 reference to the topology in Figure 2, Table 5 below shows how the 520 above condition can be used to determine node-protection with node- 521 protecting PQ-node R2. 523 +-------------+------------+---------+--------+---------+-----------+ 524 | Destination | Primary-NH | D_opt | D_opt | D_opt | Condition | 525 | (D) | (E) | (Y, D) | (Y, E) | (E, D) | Met | 526 +-------------+------------+---------+--------+---------+-----------+ 527 | R3 | E | 1 | 2 | 1 | Yes | 528 | | | (R2,R3) | (R2,E) | (E,R3) | | 529 | E | E | 2 | 2 | 0 (E,E) | No | 530 | | | (R2,E) | (R2,E) | | | 531 | D1 | E | 3 | 2 | 1 | No | 532 | | | (R2,D1) | (R2,E) | (E,D1) | | 533 | D2 | E | 2 | 2 | 1 | Yes | 534 | | | (R2,D2) | (R2,E) | (E,D2) | | 535 +-------------+------------+---------+--------+---------+-----------+ 537 Table 5: Node-protection evaluation for R-LFA path segment between 538 PQ-node and destination 540 As seen in the above example above, R2 does not meet the node- 541 protecting inequality for destination E, and D1. And so, once again, 542 while R2 is a node-protecting Remote-LFA nexthop for R3 and D2, it is 543 not so for E and D1. 545 In SPF implementations that also produce a list of links and nodes 546 traversed on the shortest path(s) from a given root to others, the 547 inequality in Figure 6 above need not be evaluated. Instead, to 548 determine whether a PQ-node provides node-protection for a given 549 destination or not, the list of nodes computed from forward SPF run 550 on the PQ-node, for the given destination, SHOULD be inspected. In 551 case the list contains the primary nexthop node, the PQ-node does not 552 provide node-protection. Else, the PQ-node guarantees node- 553 protecting alternate for the given destination. Below is an 554 illustration of the mechanism with candidate node-protecting PQ-node 555 R2 in the topology in Figure 2. 557 +-------------+-----------------+-----------------+-----------------+ 558 | Destination | Shortest Path | Link-Protection | Node-Protection | 559 | | (Repairing | | | 560 | | router to PQ- | | | 561 | | node) | | | 562 +-------------+-----------------+-----------------+-----------------+ 563 | R3 | R2->R3 | Yes | Yes | 564 | E | R2->R3->E | Yes | No | 565 | D1 | R2->R3->E->D1 | Yes | No | 566 | D2 | R2->R3->D2 | Yes | Yes | 567 +-------------+-----------------+-----------------+-----------------+ 569 Table 6: Protection of Remote-LFA path between PQ-node and 570 destination 572 As seen in the above example while R2 is candidate node-protecting 573 R-LFA nexthop for R3 and D2, it is not so for E and D1, since the 574 primary nexthop E is in the shortest path from R2 to E and D1. 576 The procedure described in this document helps no more than to 577 determine whether a given Remote-LFA alternate provides node- 578 protection for a given destination or not. It does not find out any 579 new Remote-LFA alternate nexthops, outside the ones already computed 580 by standard Remote-LFA procedure. However, in case of availability 581 of more than one PQ-node (Remote-LFA alternates) for a destination, 582 and node-protection is required for the given primary nexthop, this 583 procedure will eliminate the PQ-nodes that do not provide node- 584 protection and choose only the ones that does. 586 2.3.3. Computing Node-Protecting R-LFA Paths for Destinations with ECMP 587 primary nexthop nodes 589 In certain scenarios, when one or more destinations maybe reachable 590 via multiple ECMP (equal-cost-multi-path) nexthop nodes, and only 591 link-protection is required, there is no need to compute any 592 alternate paths for such destinations. In the event of failure of 593 one of the nexthop links, the remaining primary nexthops shall always 594 provide link-protection. However, if node-protection is required, 595 the rest of the primary nexthops may not gaurantee node-protection. 596 Figure 7 below shows one such example topology. 598 D1 599 2 / 600 S---x---E1 601 / \ / \ 602 / x / \ 603 / \ / \ 604 N-------E2 R3--D2 605 \ 2 / 606 \ / 607 \ / 608 R1-------R2 609 2 611 Primary Nexthops: 612 Destination D1 = [{ S-E1, E1}, {S-E2, E2}] 613 Destination D2 = [{ S-E1, E1}, {S-E2, E2}] 615 Figure 7: Toplogy with multiple ECMP primary nexthops 617 In the above example topology, costs of all links are 1, except the 618 following links: 620 Link: S-E1, Cost: 2 622 Link: N-E2: Cost: 2 624 Link: R1-R2: Cost: 2 626 In the above topology, on computing router S, destinations D1 and D2 627 are reachable via two ECMP nexthop nodes E1 and E2. However the 628 primary paths via nexthop node E2 also traverses via the nexthop node 629 E1. So in the event of node failure of nexthop node E1, both primary 630 paths (via E1 and E2) becomes unavailable. Hence if node-protection 631 is desired for destinations D1 and D2, alternate paths that does not 632 traverse any of the primary nexthop nodes E1 and E2, need to be 633 computed. In the above topology the only alternate neighbor N does 634 not provide such a LFA alternate path. Hence one (or more) R-LFA 635 node-proecting alternate paths for destinations D1 and D2, needs to 636 be computed. 638 In the above topology, following are the link-protecting PQ-nodes. 640 Primary Nexthop: E1, Link-Protecting PQ-Node: { R2 } 642 Primary Nexthop: E2, Link-Protecting PQ-Node: { R2 } 644 To find one (or more) node-protecting R-LFA paths for destinations D1 645 and D2, one (or more) node-protecting PQ-node(s) needs to be 646 determined first. Inequalities specified in Section 2.2.6.2 and 647 Section 2.2.6.3 can be evaluated to compute the node-protecting PQ- 648 space for each of the nexthop nodes E1 and E2, as shown in Table 7 649 below. To select a PQ-node as node-protecting PQ-node for a 650 destination with multiple primary nexthop nodes, the PQ-node MUST 651 satisfy the inequality for all primary nexthop nodes. Any PQ-node 652 which is NOT node-protecting PQ-node for all the primary nexthop 653 nodes, MUST NOT be chosen as the node-protecting PQ-node for 654 destination. 656 +--------+----------+-------+--------+--------+---------+-----------+ 657 | Primar | Candidat | Direc | D_opt | D_opt | D_opt | Condition | 658 | y Next | e PQ- | t Nbr | (Ni,Y) | (Ni,E) | (E,Y) | Met | 659 | hop | node (Y) | (Ni) | | | | | 660 | (E) | | | | | | | 661 +--------+----------+-------+--------+--------+---------+-----------+ 662 | E1 | R2 | N | 3 | 3 | 2 | Yes | 663 | | | | (N,R2) | (N,E1) | (E1,R2) | | 664 | E2 | R2 | N | 3 | 2 | 3 | Yes | 665 | | | | (N,R2) | (N,E2) | (E2,R2) | | 666 +--------+----------+-------+--------+--------+---------+-----------+ 668 Table 7: Computing Node-protected PQ-nodes for nexthop E1 and E2 670 In SPF implementations that also produce a list of links and nodes 671 traversed on the shortest path(s) from a given root to others, the 672 tunnel-repair paths from the computing router to candidate PQ-node 673 can be examined to ensure that none of the primary nexthop nodes is 674 traversed. PQ-nodes that provide one (or more) Tunnel-repair 675 paths(s) that does not traverse any of the primary nexthop nodes, are 676 to be considered as node-protecting PQ-nodes. Table 8 below shows 677 the possible tunnel-repair paths tp PQ-node R2. 679 +--------------+------------+-------------------+-------------------+ 680 | Primary-NH | PQ-Node | Tunnel-Repair | Exclude All | 681 | (E) | (Y) | Paths | Primary-NH | 682 +--------------+------------+-------------------+-------------------+ 683 | E1, E2 | R2 | S==>N==>R1==>R2 | Yes | 684 +--------------+------------+-------------------+-------------------+ 686 Table 8: Tunnel-Repair paths to PQ-node R2 688 From Table 7 and Table 8, in the above example, R2 being node- 689 protecting PQ-node for both primary nexthops E1 and E2, should be 690 chosen as the node-protecting PQ-node for destinations D1 and D2 that 691 are both reachable via primary nexthop nodes E1 and E2. 693 Next, to find a node-protecting R-LFA path from node-protecting PQ- 694 node to destinations D1 and D2, inequalities specified in Figure 6 695 should be evaluated, to ensure if R2 provides a node-protecting R-LFA 696 path for each of these destinations, as shown below in Table 9. For 697 a R-LFA path to qualify as node-protecting R-LFA path for a 698 destination with multiple ECMP primary nexthop nodes, the R-LFA path 699 from the PQ-node to the destination MUST satisfy the inequality for 700 all primary nexthop nodes. 702 +----------+----------+-------+--------+--------+--------+----------+ 703 | Destinat | Primary- | PQ- | D_opt | D_opt | D_opt | Conditio | 704 | ion (D) | NH (E) | Node | (Y, D) | (Y, E) | (E, D) | n Met | 705 | | | (Y) | | | | | 706 +----------+----------+-------+--------+--------+--------+----------+ 707 | D1 | E1 | R2 | 3 (R2, | 2 (R2, | 1 (E1, | No | 708 | | | | D1) | E1) | D1) | | 709 | D1 | E2 | R2 | 3 (R2, | 3 (R2, | 2 (E2, | Yes | 710 | | | | D1) | E2) | D1) | | 711 | D2 | E1 | R2 | 2 (R2, | 2 (R2, | 2 (E1, | Yes | 712 | | | | D2) | E1) | D2) | | 713 | D2 | E2 | R2 | 2 (R2, | 2 (R2, | 3 (E2, | Yes | 714 | | | | D2) | E2) | D2) | | 715 +----------+----------+-------+--------+--------+--------+----------+ 717 Table 9: Finding node-protecting R-LFA path for destinations D1 and 718 D2 720 In SPF implementations that also produce a list of links and nodes 721 traversed on the shortest path(s) from a given root to others, the 722 R-LFA paths via node-protecting PQ-node to final destination can be 723 examined to ensure that none of the primary nexthop nodes is 724 traversed. R-LFA path(s) that does not traverse any of the primary 725 nexthop nodes, gaurantees node-protection in the event of failure of 726 any of the primary nexthop nodes. Table 10 below shows the possible 727 R-LFA-paths for destinations D1 and D2 via the node-protecting PQ- 728 node R2. 730 +-------------+------------+---------+-----------------+------------+ 731 | Destination | Primary-NH | PQ-Node | R-LFA Paths | Exclude | 732 | (D) | (E) | (Y) | | All | 733 | | | | | Primary-NH | 734 +-------------+------------+---------+-----------------+------------+ 735 | D1 | E1, E2 | R2 | S==>N==>R1==>R2 | No | 736 | | | | -->R3-->E1-->D1 | | 737 | | | | | | 738 | D2 | E1, E2 | R2 | S==>N==>R1==>R2 | Yes | 739 | | | | -->R3-->D2 | | 740 +-------------+------------+---------+-----------------+------------+ 742 Table 10: R-LFA paths for destinations D1 and D2 744 From Table 9 and Table 10, in the above example above, the R-LFA path 745 from R2 does not meet the node-protecting inequality for destination 746 D1, while it does meet the same inequality for destination D2. And 747 so, while R2 provides node-protecting R-LFA alternate for D2, it 748 fails to provide node-protection for destination D1. Finally, while 749 it is possible to get a node-protecting R-LFA path for D2, no such 750 node-protecting R-LFA path can be found for D1. 752 2.3.4. Limiting extra computational overhead 754 In addition to the extra reverse SPF computations suggested by the 755 Remote-LFA [RFC7490] draft (one reverse SPF for each of the directly 756 connected neighbors), this document proposes a forward SPF 757 computations for each PQ-node discovered in the network. Since the 758 average number of PQ-nodes found in any network is considerably more 759 than the number of direct neighbors of the computing router, the 760 proposal of running one forward SPF per PQ-node may add considerably 761 to the overall SPF computation time. 763 To limit the computational overhead of the approach proposed, this 764 document proposes that implementations MUST choose a subset from the 765 entire set of PQ-nodes computed in the network, with a finite limit 766 on the number of PQ-nodes in the subset. Implementations MUST choose 767 a default value for this limit and may provide user with a 768 configuration knob to override the default limit. Implementations 769 MUST also evaluate some default preference criteria while considering 770 a PQ-node in this subset. Finally, implementations MAY also allow 771 user to override the default preference criteria, by providing a 772 policy configuration for the same. 774 This document proposes that implementations SHOULD use a default 775 preference criteria for PQ-node selection which will put a score on 776 each PQ-node, proportional to the number of primary interfaces for 777 which it provides coverage, its distance from the computing router, 778 and its router-id (or system-id in case of IS-IS). PQ-nodes that 779 cover more primary interfaces SHOULD be preferred over PQ-nodes that 780 cover fewer primary interfaces. When two or more PQ-nodes cover the 781 same number of primary interfaces, PQ-nodes which are closer (based 782 on metric) to the computing router SHOULD be preferred over PQ-nodes 783 farther away from it. For PQ-nodes that cover the same number of 784 primary interfaces and are the same distance from the the computing 785 router, the PQ-node with smaller router-id (or system-id in case of 786 IS-IS) SHOULD be preferred. 788 Once a subset of PQ-nodes is found, computing router shall run a 789 forward SPF on each of the PQ-nodes in the subset to continue with 790 procedures proposed in section Section 2.3.2. 792 3. Manageabilty of Remote-LFA Alternate Paths 794 3.1. The Problem 796 With the regular Remote-LFA [RFC7490] functionality the computing 797 router may compute more than one PQ-node as usable Remote-LFA 798 alternate nexthops. Additionally an alternate selection policy may 799 be configured to enable the network operator to choose one of them as 800 the most appropriate Remote-LFA alternate. For such policy-based 801 alternate selection to run, all the relevant path characteristics for 802 each the alternate paths (one through each of the PQ-nodes), needs to 803 be collected. As mentioned before in section Section 2.3 the R-LFA 804 alternate path through a given PQ-node to a given destination is 805 comprised of two path segments. 807 The first path segment (i.e. from the computing router to the PQ- 808 node) can be calculated from the regular forward SPF done as part of 809 standard and remote LFA computations. However without the mechanism 810 proposed in section Section 2.3.2 of this document, there is no way 811 to determine the path characteristics for the second path segment 812 (i.e from the PQ-node to the destination). In the absence of the 813 path characteristics for the second path segment, two Remote-LFA 814 alternate path may be equally preferred based on the first path 815 segments characteristics only, although the second path segment 816 attributes may be different. 818 3.2. The Solution 820 The additional forward SPF computation proposed in Section 2.3.2 821 document shall also collect links, nodes and path characteristics 822 along the second path segment. This shall enable collection of 823 complete path characteristics for a given Remote-LFA alternate path 824 to a given destination. The complete alternate path characteristics 825 shall then facilitate more accurate alternate path selection while 826 running the alternate selection policy. 828 As already specified in Section 2.3.4 to limit the computational 829 overhead of the approach proposed, forward SPF computations MUST be 830 run on a selected subset from the entire set of PQ-nodes computed in 831 the network, with a finite limit on the number of PQ-nodes in the 832 subset. The detailed suggestion on how to select this subset is 833 specified in the same section. While this limits the number of 834 possible alternate paths provided to the alternate-selection policy, 835 this is needed keep the computational complexity within affordable 836 limits. However if the alternate-selection policy is very 837 restrictive this may leave few destinations in the entire toplogy 838 without protection. Yet this limitation provides a necessary 839 tradeoff between extensive coverage and immense computational 840 overhead. 842 4. Acknowledgements 844 Many thanks to Bruno Decraene for providing his useful comments. We 845 would also like to thank Uma Chunduri for reviewing this document and 846 providing valuable feedback. Also, many thanks to Harish Raghuveer 847 for his review and comments on the initial versions of this document. 849 5. IANA Considerations 851 N/A. - No protocol changes are proposed in this document. 853 6. Security Considerations 855 This document does not introduce any change in any of the protocol 856 specifications. It simply proposes to run an extra SPF rooted on 857 each PQ-node discovered in the whole network. 859 7. References 861 7.1. Normative References 863 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 864 Requirement Levels", BCP 14, RFC 2119, 865 DOI 10.17487/RFC2119, March 1997, 866 . 868 [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for 869 IP Fast Reroute: Loop-Free Alternates", RFC 5286, 870 DOI 10.17487/RFC5286, September 2008, 871 . 873 [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. 874 So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", 875 RFC 7490, DOI 10.17487/RFC7490, April 2015, 876 . 878 7.2. Informative References 880 [RFC7916] Litkowski, S., Ed., Decraene, B., Filsfils, C., Raza, K., 881 Horneffer, M., and P. Sarkar, "Operational Management of 882 Loop-Free Alternates", RFC 7916, DOI 10.17487/RFC7916, 883 July 2016, . 885 Authors' Addresses 887 Pushpasis Sarkar (editor) 888 Individual Contributor 890 Email: pushpasis.ietf@gmail.com 892 Shraddha Hegde 893 Juniper Networks, Inc. 894 Electra, Exora Business Park 895 Bangalore, KA 560103 896 India 898 Email: shraddha@juniper.net 900 Chris Bowers 901 Juniper Networks, Inc. 902 1194 N. Mathilda Ave. 903 Sunnyvale, CA 94089 904 US 906 Email: cbowers@juniper.net 908 Hannes Gredler 909 RtBrick, Inc. 911 Email: hannes@rtbrick.com 913 Stephane Litkowski 914 Orange 916 Email: stephane.litkowski@orange.com