idnits 2.17.1 draft-ietf-rtgwg-rlfa-node-protection-08.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 (November 17, 2016) is 2716 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: May 21, 2017 C. Bowers 6 Juniper Networks, Inc. 7 H. Gredler 8 RtBrick, Inc. 9 S. Litkowski 10 Orange 11 November 17, 2016 13 Remote-LFA Node Protection and Manageability 14 draft-ietf-rtgwg-rlfa-node-protection-08 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 May 21, 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. Limiting extra computational overhead . . . . . . . . 13 91 3. Manageabilty of Remote-LFA Alternate Paths . . . . . . . . . 14 92 3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 14 93 3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 15 94 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 15 95 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 96 6. Security Considerations . . . . . . . . . . . . . . . . . . . 15 97 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 98 7.1. Normative References . . . . . . . . . . . . . . . . . . 15 99 7.2. Informative References . . . . . . . . . . . . . . . . . 16 100 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 16 102 1. Introduction 104 The Remote-LFA [RFC7490] specification provides loop-free alternates 105 that guarantee only link-protection. The resulting Remote-LFA 106 alternate nexthops (also referred to as the PQ-nodes) may not provide 107 node-protection for all destinations covered by the same, in case of 108 failure of the primary nexthop node. Neither does the specification 109 provide a means to determine the same. 111 Also, the LFA Manageability [RFC7916] document requires a computing 112 router to find all possible (including all possible Remote-LFA) 113 alternate nexthops, collect the complete set of path characteristics 114 for each alternate path, run an alternate-selection policy 115 (configured by the operator) and find the best alternate path. This 116 will require the Remote-LFA implementation to gather all the required 117 path characteristics along each link on the entire Remote-LFA 118 alternate path. 120 With current LFA [RFC5286] and Remote-LFA implementations, the 121 forward SPF (and reverse SPF) is run with the computing router and 122 its immediate 1-hop routers as the roots. While that enables 123 computation of path attributes (e.g. SRLG, Admin-groups) for first 124 alternate path segment from the computing router to the PQ-node, 125 there is no means for the computing router to gather any path 126 attributes for the path segment from the PQ-node to destination. 127 Consequently any policy-based selection of alternate paths will 128 consider only the path attributes from the computing router up until 129 the PQ-node. 131 This document describes a procedure for determining node-protection 132 with Remote-LFA. The same procedure is also extended for collection 133 of a complete set of path attributes, enabling more accurate policy- 134 based selection for alternate paths obtained with Remote-LFA. 136 2. Node Protection with Remote-LFA 138 Node-protection is required to provide protection of traffic on a 139 given forwarding node, against the failure of the first-hop node on 140 the primary forwarding path. Such protection becomes more critical 141 in the absence of mechanisms like non-stop-routing in the network. 142 Certain operators refrain from deploying non-stop-routing in their 143 network, due to the required complex state synchronization between 144 redundant control plane hardwares it requires, and the significant 145 additional performance complexities it hence introduces. In such 146 cases node-protection is essential to guarantee un-interrupted flow 147 of traffic, even in the case of an entire forwarding node going down. 149 The following sections discuss the node-protection problem in the 150 context of Remote-LFA and propose a solution. 152 2.1. The Problem 154 To better illustrate the problem and the solution proposed in this 155 document the following topology diagram from the Remote-LFA [RFC7490] 156 draft is being re-used with slight modification. 158 D1 159 / 160 S-x-E 161 / \ 162 N R3--D2 163 \ / 164 R1---R2 166 Figure 1: Topology 1 168 In the above topology, for all (non-ECMP) destinations reachable via 169 the S-E link there is no standard LFA alternate. As per the Remote- 170 LFA [RFC7490] alternate specifications node R2 being the only PQ-node 171 for the S-E link provides nexthop for all the above destinations. 172 Table 1 below, shows all possible primary and Remote-LFA alternate 173 paths for each destination. 175 +-------------+--------------+---------+-------------------------+ 176 | Destination | Primary Path | PQ-node | Remote-LFA Backup Path | 177 +-------------+--------------+---------+-------------------------+ 178 | R3 | S->E->R3 | R2 | S=>N=>R1=>R2->R3 | 179 | E | S->E | R2 | S=>N=>R1=>R2->R3->E | 180 | D1 | S->E->D1 | R2 | S=>N=>R1=>R2->R3->E->D1 | 181 | D2 | S->E->R3->D2 | R2 | S=>N=>R1=>R2->R3->D2 | 182 +-------------+--------------+---------+-------------------------+ 184 Table 1: Remote-LFA backup paths via PQ-node R2 186 A closer look at Table 1 shows that, while the PQ-node R2 provides 187 link-protection for all the destinations, it does not provide node- 188 protection for destinations E and D1. In the event of the node- 189 failure on primary nexthop E, the alternate path from Remote-LFA 190 nexthop R2 to E and D1 also becomes unavailable. So for a Remote-LFA 191 nexthop to provide node-protection for a given destination, it is 192 mandatory that, the shortest path from the given PQ-node to the given 193 destination MUST NOT traverse the primary nexthop. 195 In another extension of the topology in Figure 1 let us consider an 196 additional link between N and E with the same cost as the other 197 links. 199 D1 200 / 201 S-x-E 202 / / \ 203 N---+ R3--D2 204 \ / 205 R1---R2 207 Figure 2: Topology 2 209 In the above topology, the S-E link is no more on any of the shortest 210 paths from N to R3, E and D1. Hence R3, E and D1 are also included 211 in both the Extended-P space and Q space of E (w.r.t S-E link). 212 Table 2 below, shows all possible primary and R-LFA alternate paths 213 via PQ-node R3, for each destination reachable through the S-E link 214 in the above topology. The R-LFA alternate paths via PQ-node R2 215 remains same as in Table 1. 217 +-------------+--------------+---------+------------------------+ 218 | Destination | Primary Path | PQ-node | Remote-LFA Backup Path | 219 +-------------+--------------+---------+------------------------+ 220 | R3 | S->E->R3 | R3 | S=>N=>E=>R3 | 221 | E | S->E | R3 | S=>N=>E=>R3->E | 222 | D1 | S->E->D1 | R3 | S=>N=>E=>R3->E->D1 | 223 | D2 | S->E->R3->D2 | R3 | S=>N=>E=>R3->D2 | 224 +-------------+--------------+---------+------------------------+ 226 Table 2: Remote-LFA backup paths via PQ-node R3 228 Again a closer look at Table 2 shows that, unlike Table 1, where the 229 single PQ-node R2 provided node-protection for destinations R3 and 230 D2, if we choose R3 as the R-LFA nexthop, it does not provide node- 231 protection for R3 and D2 anymore. If S chooses R3 as the R-LFA 232 nexthop, in the event of the node-failure on primary nexthop E, on 233 the alternate path from S to R-LFA nexthop R3, one of parallel ECMP 234 path between N and R3 also becomes unavailable. So for a Remote-LFA 235 nexthop to provide node-protection for a given destination, it is 236 also mandatory that, the shortest path from S to the chosen PQ-node 237 MUST NOT traverse the primary nexthop node. 239 2.2. Additional Definitions 241 This document adds and enhances the following definitions extending 242 the ones mentioned in Remote-LFA [RFC7490] specification. 244 2.2.1. Link-Protecting Extended P-Space 246 The Remote-LFA [RFC7490] specification already defines this. The 247 link-protecting extended P-space for a link S-E being protected is 248 the set of routers that are reachable from one or more direct 249 neighbors of S, except primary node E, without traversing the S-E 250 link on any of the shortest path from the direct neighbor to the 251 router. This MUST exclude any direct neighbor for which there is at 252 least one ECMP path from the direct neighbor traversing the link(S-E) 253 being protected. 255 For a cost-based definition for Link-protecting Extended P-Space 256 refer to Section 2.2.6.1. 258 2.2.2. Node-Protecting Extended P-Space 260 The node-protecting extended P-space for a primary nexthop node E 261 being protected, is the set of routers that are reachable from one or 262 more direct neighbors of S, except primary node E, without traversing 263 the node E. This MUST exclude any direct neighbors for which there 264 is at least one ECMP path from the direct neighbor traversing the 265 node E being protected. 267 For a cost-based definition for Node-protecting Extended P-Space 268 refer to Section 2.2.6.2. 270 2.2.3. Q-Space 272 The Remote-LFA [RFC7490] draft already defines this. The Q-space for 273 a link S-E being protected is the set of routers that can reach 274 primary node E, without traversing the S-E link on any of the 275 shortest path from the node Y to primary nexthop E. This MUST 276 exclude any destination for which there is at least one ECMP path 277 from the node Y to the primary nexthop E traversing the link(S-E) 278 being protected. 280 For a cost-based definition for Q-Space refer to Section 2.2.6.3. 282 2.2.4. Link-Protecting PQ Space 284 A node Y is in link-protecting PQ space w.r.t to the link (S-E) being 285 protected, if and only if, Y is present in both link-protecting 286 extended P-space and the Q-space for the link being protected. 288 2.2.5. Candidate Node-Protecting PQ Space 290 A node Y is in candidate node-protecting PQ space w.r.t to the node 291 (E) being protected, if and only if, Y is present in both node- 292 protecting extended P-space and the Q-space for the link being 293 protected. 295 Please note, that a node Y being in candidate node-protecting PQ- 296 space, does not guarantee that the R-LFA alternate path via the same, 297 in entirety, is unaffected in the event of a node failure of primary 298 nexthop node E. It only guarantees that the path segment from S to 299 PQ-node Y is unaffected by the same failure event. The PQ-nodes in 300 the candidate node-protecting PQ space may provide node protection 301 for only a subset of destinations that are reachable through the 302 corresponding primary link. 304 2.2.6. Cost-Based Definitions 306 This section provides cost-based definitions for some of the terms 307 introduced in Section 2.2 of this document. 309 2.2.6.1. Link-Protecting Extended P-Space 311 Please refer to Section 2.2.1 for a formal definition for Link- 312 protecting Extended P-Space. 314 A node Y is in link-protecting extended P-space w.r.t to the link 315 (S-E) being protected, if and only if, there exists at least one 316 direct neighbor of S, Ni, other than primary nexthop E, that 317 satisfies the following condition. 319 D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y) 321 Where, 322 D_opt(A,B) : Distance on most optimum path from A to B. 323 Ni : A direct neighbor of S other than primary 324 nexthop E. 325 Y : The node being evaluated for link-protecting 326 extended P-Space. 328 Figure 3: Link-Protecting Ext-P-Space Condition 330 2.2.6.2. Node-Protecting Extended P-Space 332 Please refer to Section 2.2.2 for a formal definition for Node- 333 protecting Extended P-Space. 335 A node Y is in node-protecting extended P-space w.r.t to the node E 336 being protected, if and only if, there exists at least one direct 337 neighbor of S, Ni, other than primary nexthop E, that satisfies the 338 following condition. 340 D_opt(Ni,Y) < D_opt(Ni,E) + D_opt(E,Y) 342 Where, 343 D_opt(A,B) : Distance on most optimum path from A to B. 344 E : The primary nexthop on shortest path from S 345 to destination. 346 Ni : A direct neighbor of S other than primary 347 nexthop E. 348 Y : The node being evaluated for node-protecting 349 extended P-Space. 351 Figure 4: Node-Protecting Ext-P-Space Condition 353 Please note, that a node Y satisfying the condition in Figure 4 above 354 only guarantees that the R-LFA alternate path segment from S via 355 direct neighbor Ni to the node Y is not affected in the event of a 356 node failure of E. It does not yet guarantee that the path segment 357 from node Y to the destination is also unaffected by the same failure 358 event. 360 2.2.6.3. Q-Space 362 Please refer to Section 2.2.3 for a formal definition for Q-Space. 364 A node Y is in Q-space w.r.t to the link (S-E) being protected, if 365 and only if, the following condition is satisfied. 367 D_opt(Y,E) < D_opt(S,E) + D_opt(Y,S) 369 Where, 370 D_opt(A,B) : Distance on most optimum path from A to B. 371 E : The primary nexthop on shortest path from S 372 to destination. 373 Y : The node being evaluated for Q-Space. 375 Figure 5: Q-Space Condition 377 2.3. Computing Node-protecting R-LFA Path 379 The R-LFA alternate path through a given PQ-node to a given 380 destination is comprised of two path segments as follows. 382 1. Path segment from the computing router to the PQ-node (Remote-LFA 383 alternate nexthop), and 385 2. Path segment from the PQ-node to the destination being protected. 387 So to ensure a R-LFA alternate path for a given destination provides 388 node-protection we need to ensure that none of the above path 389 segments are affected in the event of failure of the primary nexthop 390 node. Sections Section 2.3.1 and Section 2.3.2 shows how this can be 391 ensured. 393 2.3.1. Computing Candidate Node-protecting PQ-Nodes for Primary 394 nexthops 396 To choose a node-protecting R-LFA nexthop for a destination R3, 397 router S needs to consider a PQ-node from the candidate node- 398 protecting PQ-space for the primary nexthop E on shortest path from S 399 to R3. As mentioned in Section 2.2.2, to consider a PQ-node as 400 candidate node-protecting PQ-node, there must be at least one direct 401 neighbor Ni of S, such that all shortest paths from Ni to the PQ-node 402 does not traverse primary nexthop node E. 404 Implementations SHOULD run the inequality in Section 2.2.2 Figure 4 405 for all direct neighbors, other than primary nexthop node E, to 406 determine whether a node Y is a candidate node-protecting PQ-node. 407 All of the metrics needed by this inequality would have been already 408 collected from the forward SPFs rooted at each of direct neighbor S, 409 computed as part of standard LFA [RFC5286] implementation. With 410 reference to the topology in Figure 2, Table 3 below shows how the 411 above condition can be used to determine the candidate node- 412 protecting PQ-space for S-E link (primary nexthop E). 414 +------------+----------+----------+----------+---------+-----------+ 415 | Candidate | Direct | D_opt | D_opt | D_opt | Condition | 416 | PQ-node | Nbr (Ni) | (Ni,Y) | (Ni,E) | (E,Y) | Met | 417 | (Y) | | | | | | 418 +------------+----------+----------+----------+---------+-----------+ 419 | R2 | N | 2 (N,R2) | 1 (N,E) | 2 | Yes | 420 | | | | | (E,R2) | | 421 | R3 | N | 2 (N,R3) | 1 (N,E) | 1 | No | 422 | | | | | (E,R3) | | 423 +------------+----------+----------+----------+---------+-----------+ 425 Table 3: Node-protection evaluation for R-LFA repair tunnel to PQ- 426 node 428 As seen in the above Table 3, R3 does not meet the node-protecting 429 extended-p-space inequality and so, while R2 is in candidate node- 430 protecting PQ space, R3 is not. 432 Some SPF implementations may also produce a list of links and nodes 433 traversed on the shortest path(s) from a given root to others. In 434 such implementations, router S may have executed a forward SPF with 435 each of its direct neighbors as the SPF root, executed as part of the 436 standard LFA [RFC5286] computations. So S may re-use the list of 437 links and nodes collected from the same SPF computations, to decide 438 whether a node Y is a candidate node-protecting PQ-node or not. A 439 node Y shall be considered as a node-protecting PQ-node, if and only 440 if, there is at least one direct neighbor of S, other than the 441 primary nexthop E, for which, the primary nexthop node E does not 442 exist on the list of nodes traversed on any of the shortest path(s) 443 from the direct neighbor to the PQ-node. Table 4 below is an 444 illustration of the mechanism with the topology in Figure 2. 446 +-----------+-------------------+-----------------+-----------------+ 447 | Candidate | Repair Tunnel | Link-Protection | Node-Protection | 448 | PQ-node | Path(Repairing | | | 449 | | router to PQ- | | | 450 | | node) | | | 451 +-----------+-------------------+-----------------+-----------------+ 452 | R2 | S->N->R1->R2 | Yes | Yes | 453 | R2 | S->E->R3->R2 | No | No | 454 | R3 | S->N->E->R3 | Yes | No | 455 +-----------+-------------------+-----------------+-----------------+ 457 Table 4: Protection of Remote-LFA tunnel to the PQ-node 459 As seen in the above Table 4 while R2 is candidate node-protecting 460 Remote-LFA nexthop for R3 and D2, it is not so for E and D1, since 461 the primary nexthop E is in the shortest path from R2 to E and D1. 463 2.3.2. Computing node-protecting paths from PQ-nodes to destinations 465 Once a computing router finds all the candidate node-protecting PQ- 466 nodes for a given directly attached primary link, it shall follow the 467 procedure as proposed in this section, to choose one or more node- 468 protecting R-LFA paths, for destinations reachable through the same 469 primary link in the primary SPF graph. 471 To find a node-protecting R-LFA path for a given destination, the 472 computing router needs to pick a subset of PQ-nodes from the 473 candidate node-protecting PQ-space for the corresponding primary 474 nexthop, such that all the path(s) from the PQ-node(s) to the given 475 destination remain unaffected in the event of a node failure of the 476 primary nexthop node. To determine wether a given PQ-node belongs to 477 such a subset of PQ-nodes, the computing router MUST ensure that none 478 of the primary nexthop node are found on any of the shortest paths 479 from the PQ-node to the given destination. 481 This document proposes an additional forward SPF computation for each 482 of the PQ-nodes, to discover all shortest paths from the PQ-nodes to 483 the destination. This will help determine, if a given primary 484 nexthop node is on the shortest paths from the PQ-node to the given 485 destination or not. To determine if a given candidate node- 486 protecting PQ-node provides node-protecting alternate for a given 487 destination, or not, all the shortest paths from the PQ-node to the 488 given destination has to be inspected, to check if the primary 489 nexthop node is found on any of these shortest paths. To compute all 490 the shortest paths from a candidate node-protecting PQ-node to one 491 (or more) destination, the computing router MUST run the forward SPF 492 on the candidate node-protecting PQ-node. Soon after running the 493 forward SPF, the computer router SHOULD run the inequality in 494 Figure 6 below, once for each destination. A PQ-node that does not 495 qualify the condition for a given destination, does not guarantee 496 node-protection for the path segment from the PQ-node to the specific 497 destination. 499 D_opt(Y,D) < D_opt(Y,E) + Distance_opt(E,D) 501 Where, 502 D_opt(A,B) : Distance on most optimum path from A to B. 503 D : The destination node. 504 E : The primary nexthop on shortest path from S 505 to destination. 506 Y : The node-protecting PQ-node being evaluated 508 Figure 6: Node-Protecting Condition for PQ-node to Destination 510 All of the above metric costs except D_opt(Y, D), can be obtained 511 with forward and reverse SPFs with E(the primary nexthop) as the 512 root, run as part of the regular LFA and Remote-LFA implementation. 513 The Distance_opt(Y, D) metric can only be determined by the 514 additional forward SPF run with PQ-node Y as the root. With 515 reference to the topology in Figure 2, Table 5 below shows how the 516 above condition can be used to determine node-protection with node- 517 protecting PQ-node R2. 519 +-------------+------------+---------+--------+---------+-----------+ 520 | Destination | Primary-NH | D_opt | D_opt | D_opt | Condition | 521 | (D) | (E) | (Y, D) | (Y, E) | (E, D) | Met | 522 +-------------+------------+---------+--------+---------+-----------+ 523 | R3 | E | 1 | 2 | 1 | Yes | 524 | | | (R2,R3) | (R2,E) | (E,R3) | | 525 | E | E | 2 | 2 | 0 (E,E) | No | 526 | | | (R2,E) | (R2,E) | | | 527 | D1 | E | 3 | 2 | 1 | No | 528 | | | (R2,D1) | (R2,E) | (E,D1) | | 529 | D2 | E | 2 | 2 | 1 | Yes | 530 | | | (R2,D2) | (R2,E) | (E,D2) | | 531 +-------------+------------+---------+--------+---------+-----------+ 533 Table 5: Node-protection evaluation for R-LFA path segment between 534 PQ-node and destination 536 As seen in the above example above, R2 does not meet the node- 537 protecting inequality for destination E, and D1. And so, once again, 538 while R2 is a node-protecting Remote-LFA nexthop for R3 and D2, it is 539 not so for E and D1. 541 In SPF implementations that also produce a list of links and nodes 542 traversed on the shortest path(s) from a given root to others, the 543 inequality in Figure 6 above need not be evaluated. Instead, to 544 determine whether a PQ-node provides node-protection for a given 545 destination or not, the list of nodes computed from forward SPF run 546 on the PQ-node, for the given destination, SHOULD be inspected. In 547 case the list contains the primary nexthop node, the PQ-node does not 548 provide node-protection. Else, the PQ-node guarantees node- 549 protecting alternate for the given destination. Below is an 550 illustration of the mechanism with candidate node-protecting PQ-node 551 R2 in the topology in Figure 2. 553 +-------------+-----------------+-----------------+-----------------+ 554 | Destination | Shortest Path | Link-Protection | Node-Protection | 555 | | (Repairing | | | 556 | | router to PQ- | | | 557 | | node) | | | 558 +-------------+-----------------+-----------------+-----------------+ 559 | R3 | R2->R3 | Yes | Yes | 560 | E | R2->R3->E | Yes | No | 561 | D1 | R2->R3->E->D1 | Yes | No | 562 | D2 | R2->R3->D2 | Yes | Yes | 563 +-------------+-----------------+-----------------+-----------------+ 565 Table 6: Protection of Remote-LFA path between PQ-node and 566 destination 568 As seen in the above example while R2 is candidate node-protecting 569 R-LFA nexthop for R3 and D2, it is not so for E and D1, since the 570 primary nexthop E is in the shortest path from R2 to E and D1. 572 The procedure described in this document helps no more than to 573 determine whether a given Remote-LFA alternate provides node- 574 protection for a given destination or not. It does not find out any 575 new Remote-LFA alternate nexthops, outside the ones already computed 576 by standard Remote-LFA procedure. However, in case of availability 577 of more than one PQ-node (Remote-LFA alternates) for a destination, 578 and node-protection is required for the given primary nexthop, this 579 procedure will eliminate the PQ-nodes that do not provide node- 580 protection and choose only the ones that does. 582 2.3.3. Limiting extra computational overhead 584 In addition to the extra reverse SPF computations suggested by the 585 Remote-LFA [RFC7490] draft (one reverse SPF for each of the directly 586 connected neighbors), this document proposes a forward SPF 587 computations for each PQ-node discovered in the network. Since the 588 average number of PQ-nodes found in any network is considerably more 589 than the number of direct neighbors of the computing router, the 590 proposal of running one forward SPF per PQ-node may add considerably 591 to the overall SPF computation time. 593 To limit the computational overhead of the approach proposed, this 594 document proposes that implementations MUST choose a subset from the 595 entire set of PQ-nodes computed in the network, with a finite limit 596 on the number of PQ-nodes in the subset. Implementations MUST choose 597 a default value for this limit and may provide user with a 598 configuration knob to override the default limit. Implementations 599 MUST also evaluate some default preference criteria while considering 600 a PQ-node in this subset. Finally, implementations MAY also allow 601 user to override the default preference criteria, by providing a 602 policy configuration for the same. 604 This document proposes that implementations SHOULD use a default 605 preference criteria for PQ-node selection which will put a score on 606 each PQ-node, proportional to the number of primary interfaces for 607 which it provides coverage, its distance from the computing router, 608 and its router-id (or system-id in case of IS-IS). PQ-nodes that 609 cover more primary interfaces SHOULD be preferred over PQ-nodes that 610 cover fewer primary interfaces. When two or more PQ-nodes cover the 611 same number of primary interfaces, PQ-nodes which are closer (based 612 on metric) to the computing router SHOULD be preferred over PQ-nodes 613 farther away from it. For PQ-nodes that cover the same number of 614 primary interfaces and are the same distance from the the computing 615 router, the PQ-node with smaller router-id (or system-id in case of 616 IS-IS) SHOULD be preferred. 618 Once a subset of PQ-nodes is found, computing router shall run a 619 forward SPF on each of the PQ-nodes in the subset to continue with 620 procedures proposed in section Section 2.3.2. 622 3. Manageabilty of Remote-LFA Alternate Paths 624 3.1. The Problem 626 With the regular Remote-LFA [RFC7490] functionality the computing 627 router may compute more than one PQ-node as usable Remote-LFA 628 alternate nexthops. Additionally an alternate selection policy may 629 be configured to enable the network operator to choose one of them as 630 the most appropriate Remote-LFA alternate. For such policy-based 631 alternate selection to run, all the relevant path characteristics for 632 each the alternate paths (one through each of the PQ-nodes), needs to 633 be collected. As mentioned before in section Section 2.3 the R-LFA 634 alternate path through a given PQ-node to a given destination is 635 comprised of two path segments. 637 The first path segment (i.e. from the computing router to the PQ- 638 node) can be calculated from the regular forward SPF done as part of 639 standard and remote LFA computations. However without the mechanism 640 proposed in section Section 2.3.2 of this document, there is no way 641 to determine the path characteristics for the second path segment 642 (i.e from the PQ-node to the destination). In the absence of the 643 path characteristics for the second path segment, two Remote-LFA 644 alternate path may be equally preferred based on the first path 645 segments characteristics only, although the second path segment 646 attributes may be different. 648 3.2. The Solution 650 The additional forward SPF computation proposed in Section 2.3.2 651 document shall also collect links, nodes and path characteristics 652 along the second path segment. This shall enable collection of 653 complete path characteristics for a given Remote-LFA alternate path 654 to a given destination. The complete alternate path characteristics 655 shall then facilitate more accurate alternate path selection while 656 running the alternate selection policy. 658 As already specified in Section 2.3.3 to limit the computational 659 overhead of the approach proposed, forward SPF computations MUST be 660 run on a selected subset from the entire set of PQ-nodes computed in 661 the network, with a finite limit on the number of PQ-nodes in the 662 subset. The detailed suggestion on how to select this subset is 663 specified in the same section. While this limits the number of 664 possible alternate paths provided to the alternate-selection policy, 665 this is needed keep the computational complexity within affordable 666 limits. However if the alternate-selection policy is very 667 restrictive this may leave few destinations in the entire toplogy 668 without protection. Yet this limitation provides a necessary 669 tradeoff between extensive coverage and immense computational 670 overhead. 672 4. Acknowledgements 674 Many thanks to Bruno Decraene for providing his useful comments. We 675 would also like to thank Uma Chunduri for reviewing this document and 676 providing valuable feedback. Also, many thanks to Harish Raghuveer 677 for his review and comments on the initial versions of this document. 679 5. IANA Considerations 681 N/A. - No protocol changes are proposed in this document. 683 6. Security Considerations 685 This document does not introduce any change in any of the protocol 686 specifications. It simply proposes to run an extra SPF rooted on 687 each PQ-node discovered in the whole network. 689 7. References 691 7.1. Normative References 693 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 694 Requirement Levels", BCP 14, RFC 2119, 695 DOI 10.17487/RFC2119, March 1997, 696 . 698 [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for 699 IP Fast Reroute: Loop-Free Alternates", RFC 5286, 700 DOI 10.17487/RFC5286, September 2008, 701 . 703 [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. 704 So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", 705 RFC 7490, DOI 10.17487/RFC7490, April 2015, 706 . 708 7.2. Informative References 710 [RFC7916] Litkowski, S., Ed., Decraene, B., Filsfils, C., Raza, K., 711 Horneffer, M., and P. Sarkar, "Operational Management of 712 Loop-Free Alternates", RFC 7916, DOI 10.17487/RFC7916, 713 July 2016, . 715 Authors' Addresses 717 Pushpasis Sarkar (editor) 718 Individual Contributor 720 Email: pushpasis.ietf@gmail.com 722 Shraddha Hegde 723 Juniper Networks, Inc. 724 Electra, Exora Business Park 725 Bangalore, KA 560103 726 India 728 Email: shraddha@juniper.net 730 Chris Bowers 731 Juniper Networks, Inc. 732 1194 N. Mathilda Ave. 733 Sunnyvale, CA 94089 734 US 736 Email: cbowers@juniper.net 737 Hannes Gredler 738 RtBrick, Inc. 740 Email: hannes@rtbrick.com 742 Stephane Litkowski 743 Orange 745 Email: stephane.litkowski@orange.com