idnits 2.17.1 draft-ietf-rtgwg-rlfa-node-protection-05.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 == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: A closer look at Table 1 shows that, while the PQ-node R2 provides link-protection for all the destinations, it does not provide node-protection for destinations E and D1. In the event of the node-failure on primary nexthop E, the alternate path from Remote-LFA nexthop R2 to E and D1 also becomes unavailable. So for a Remote-LFA nexthop to provide node-protection for a given destination, it is mandatory that, the shortest path from the given PQ-node to the given destination MUST not traverse the primary nexthop. == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: Again a closer look at Table 2 shows that, unlike Table 1, where the single PQ-node R2 provided node-protection for destinations R3 and D2, if we choose R3 as the R-LFA nexthop, it does not provide node-protection for R3 and D2 anymore. If S chooses R3 as the R-LFA nexthop, in the event of the node-failure on primary nexthop E, on the alternate path from S to R-LFA nexthop R3, one of parallel ECMP path between N and R3 also becomes unavailable. So for a Remote-LFA nexthop to provide node-protection for a given destination, it is also mandatory that, the shortest path from S to the chosen PQ-node MUST not traverse the primary nexthop node. -- The document date (December 10, 2015) is 3060 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 (~~), 3 warnings (==), 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 S. Hegde 4 Intended status: Standards Track C. Bowers 5 Expires: June 12, 2016 Juniper Networks, Inc. 6 H. Gredler 7 Unaffiliated 8 S. Litkowski 9 Orange 10 December 10, 2015 12 Remote-LFA Node Protection and Manageability 13 draft-ietf-rtgwg-rlfa-node-protection-05 15 Abstract 17 The loop-free alternates computed following the current Remote-LFA 18 specification guarantees only link-protection. The resulting Remote- 19 LFA nexthops (also called PQ-nodes), may not guarantee node- 20 protection for all destinations being protected by it. 22 This document describes procedures for determining if a given PQ-node 23 provides node-protection for a specific destination or not. The 24 document also shows how the same procedure can be utilised for 25 collection of complete characteristics for alternate paths. 26 Knowledge about the characteristics of all alternate path is 27 precursory to apply operator defined policy for eliminating paths not 28 fitting constraints. 30 Requirements Language 32 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 33 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 34 document are to be interpreted as described in RFC2119 [RFC2119]. 36 Status of This Memo 38 This Internet-Draft is submitted in full conformance with the 39 provisions of BCP 78 and BCP 79. 41 Internet-Drafts are working documents of the Internet Engineering 42 Task Force (IETF). Note that other groups may also distribute 43 working documents as Internet-Drafts. The list of current Internet- 44 Drafts is at http://datatracker.ietf.org/drafts/current/. 46 Internet-Drafts are draft documents valid for a maximum of six months 47 and may be updated, replaced, or obsoleted by other documents at any 48 time. It is inappropriate to use Internet-Drafts as reference 49 material or to cite them other than as "work in progress." 51 This Internet-Draft will expire on June 12, 2016. 53 Copyright Notice 55 Copyright (c) 2015 IETF Trust and the persons identified as the 56 document authors. All rights reserved. 58 This document is subject to BCP 78 and the IETF Trust's Legal 59 Provisions Relating to IETF Documents 60 (http://trustee.ietf.org/license-info) in effect on the date of 61 publication of this document. Please review these documents 62 carefully, as they describe your rights and restrictions with respect 63 to this document. Code Components extracted from this document must 64 include Simplified BSD License text as described in Section 4.e of 65 the Trust Legal Provisions and are provided without warranty as 66 described in the Simplified BSD License. 68 Table of Contents 70 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 71 2. Node Protection with Remote-LFA . . . . . . . . . . . . . . . 3 72 2.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 4 73 2.2. Additional Definitions . . . . . . . . . . . . . . . . . 6 74 2.2.1. Link-Protecting Extended P-Space . . . . . . . . . . 6 75 2.2.2. Node-Protecting Extended P-Space . . . . . . . . . . 6 76 2.2.3. Q-Space . . . . . . . . . . . . . . . . . . . . . . . 6 77 2.2.4. Link-Protecting PQ Space . . . . . . . . . . . . . . 6 78 2.2.5. Candidate Node-Protecting PQ Space . . . . . . . . . 7 79 2.2.6. Cost-Based Definitions . . . . . . . . . . . . . . . 7 80 2.2.6.1. Link-Protecting Extended P-Space . . . . . . . . 7 81 2.2.6.2. Node-Protecting Extended P-Space . . . . . . . . 7 82 2.2.6.3. Q-Space . . . . . . . . . . . . . . . . . . . . . 8 83 2.3. Computing Node-protecting R-LFA Path . . . . . . . . . . 9 84 2.3.1. Computing Candidate Node-protecting PQ-Nodes for 85 Primary nexthops . . . . . . . . . . . . . . . . . . 9 86 2.3.2. Computing node-protecting paths from PQ-nodes to 87 destinations . . . . . . . . . . . . . . . . . . . . 11 88 2.3.3. Limiting extra computational overhead . . . . . . . . 13 89 3. Manageabilty of Remote-LFA Alternate Paths . . . . . . . . . 14 90 3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 14 91 3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 15 92 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 15 93 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 94 6. Security Considerations . . . . . . . . . . . . . . . . . . . 15 95 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 96 7.1. Normative References . . . . . . . . . . . . . . . . . . 15 97 7.2. Informative References . . . . . . . . . . . . . . . . . 16 98 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 16 100 1. Introduction 102 The Remote-LFA [RFC7490] specification provides loop-free alternates 103 that guarantee only link-protection. The resulting Remote-LFA 104 alternate nexthops (also referred to as the PQ-nodes) may not provide 105 node-protection for all destinations covered by the same, in case of 106 failure of the primary nexthop node. Neither does the specification 107 provide a means to determine the same. 109 Also, the LFA Manageability [I-D.ietf-rtgwg-lfa-manageability] 110 document, requires a computing router to find all possible (including 111 all possible Remote-LFA) alternate nexthops, collect the complete set 112 of path characteristics for each alternate path, run a alternate- 113 selection policy (configured by the operator), and find the best 114 alternate path. This will require the Remote-LFA implementation to 115 gather all the required path characteristics along each link on the 116 entire Remote-LFA alternate path. 118 With current LFA [RFC5286] and Remote-LFA implementations, the 119 forward SPF (and reverse SPF) is run on the computing router and its 120 immediate 1-hop routers as the roots. While that enables computation 121 of path attributes (e.g. SRLG, Admin-groups) for first alternate 122 path segment from the computing router to the PQ-node, there is no 123 means for the computing router to gather any path attributes for the 124 path segment from the PQ-node to destination. Consequently any 125 policy-based selection of alternate paths will consider only the path 126 attributes from the computing router up until the PQ-node. 128 This document describes a procedure for determining node-protection 129 with Remote-LFA. The same procedure is also extended for collection 130 of a complete set of path attributes, enabling more accurate policy- 131 based selection for alternate paths obtained with Remote-LFA. 133 2. Node Protection with Remote-LFA 135 Node-protection is required to provide protection of traffic on a 136 given forwarding node, against the failure of the first-hop node on 137 the primary forwarding path. Such protection becomes more critical 138 in the absence of mechanisms like non-stop-routing in the network. 139 Certain operators refrain from deploying non-stop-routing in their 140 network, due to the significant additional performance complexities 141 it introduces. In such cases node-protection is essential to 142 guarantee un-interrupted flow of traffic, even in the case of an 143 entire forwarding node going down. 145 The following sections discuss the node-protection problem in the 146 context of Remote-LFA and propose a solution. 148 2.1. The Problem 150 To better illustrate the problem and the solution proposed in this 151 document the following topology diagram from the Remote-LFA [RFC7490] 152 draft is being re-used with slight modification. 154 D1 155 / 156 S-x-E 157 / \ 158 N R3--D2 159 \ / 160 R1---R2 162 Figure 1: Topology 1 164 In the above topology, for all (non-ECMP) destinations reachable via 165 the S-E link there is no standard LFA alternate. As per the Remote- 166 LFA [RFC7490] alternate specifications node R2 being the only PQ-node 167 for the S-E link provides nexthop for all the above destinations. 168 Table 1 below, shows all possible primary and Remote-LFA alternate 169 paths for each destination. 171 +-------------+--------------+---------+-------------------------+ 172 | Destination | Primary Path | PQ-node | Remote-LFA Backup Path | 173 +-------------+--------------+---------+-------------------------+ 174 | R3 | S->E->R3 | R2 | S=>N=>R1=>R2->R3 | 175 | E | S->E | R2 | S=>N=>R1=>R2->R3->E | 176 | D1 | S->E->D1 | R2 | S=>N=>R1=>R2->R3->E->D1 | 177 | D2 | S->E->R3->D2 | R2 | S=>N=>R1=>R2->R3->D2 | 178 +-------------+--------------+---------+-------------------------+ 180 Table 1: Remote-LFA backup paths via PQ-node R2 182 A closer look at Table 1 shows that, while the PQ-node R2 provides 183 link-protection for all the destinations, it does not provide node- 184 protection for destinations E and D1. In the event of the node- 185 failure on primary nexthop E, the alternate path from Remote-LFA 186 nexthop R2 to E and D1 also becomes unavailable. So for a Remote-LFA 187 nexthop to provide node-protection for a given destination, it is 188 mandatory that, the shortest path from the given PQ-node to the given 189 destination MUST not traverse the primary nexthop. 191 In another extension of the topology in Figure 1 let us consider an 192 additional link between N and E with the same cost as the other 193 links. 195 D1 196 / 197 S-x-E 198 / / \ 199 N---+ R3--D2 200 \ / 201 R1---R2 203 Figure 2: Topology 2 205 In the above topology, the S-E link is no more on any of the shortest 206 paths from N to R3, E and D1. Hence R3, E and D1 are also included 207 in both the Extended-P space and Q space of E (w.r.t S-E link). 208 Table 2 below, shows all possible primary and R-LFA alternate paths 209 via PQ-node R3, for each destination reachable through the S-E link 210 in the above topology. The R-LFA alternate paths via PQ-node R2 211 remains same as in Table 1. 213 +-------------+--------------+---------+------------------------+ 214 | Destination | Primary Path | PQ-node | Remote-LFA Backup Path | 215 +-------------+--------------+---------+------------------------+ 216 | R3 | S->E->R3 | R3 | S=>N=>E=>R3 | 217 | E | S->E | R3 | S=>N=>E=>R3->E | 218 | D1 | S->E->D1 | R3 | S=>N=>E=>R3->E->D1 | 219 | D2 | S->E->R3->D2 | R3 | S=>N=>E=>R3->D2 | 220 +-------------+--------------+---------+------------------------+ 222 Table 2: Remote-LFA backup paths via PQ-node R3 224 Again a closer look at Table 2 shows that, unlike Table 1, where the 225 single PQ-node R2 provided node-protection for destinations R3 and 226 D2, if we choose R3 as the R-LFA nexthop, it does not provide node- 227 protection for R3 and D2 anymore. If S chooses R3 as the R-LFA 228 nexthop, in the event of the node-failure on primary nexthop E, on 229 the alternate path from S to R-LFA nexthop R3, one of parallel ECMP 230 path between N and R3 also becomes unavailable. So for a Remote-LFA 231 nexthop to provide node-protection for a given destination, it is 232 also mandatory that, the shortest path from S to the chosen PQ-node 233 MUST not traverse the primary nexthop node. 235 2.2. Additional Definitions 237 This document adds and enhances the following definitions extending 238 the ones mentioned in Remote-LFA [RFC7490] specification. 240 2.2.1. Link-Protecting Extended P-Space 242 The Remote-LFA [RFC7490] specification already defines this. The 243 link-protecting extended P-space for a link S-E being protected is 244 the set of routers that are reachable from one or more direct 245 neighbors of S, except primary node E, without traversing the S-E 246 link on any of the shortest path from the direct neighbor to the 247 router. This MUST exclude any direct neighbor for which there is at 248 least one ECMP path from the direct neighbor traversing the link(S-E) 249 being protected. 251 For a cost-based definition for Link-protecting Extended P-Space 252 refer to Section 2.2.6.1. 254 2.2.2. Node-Protecting Extended P-Space 256 The node-protecting extended P-space for a primary nexthop node E 257 being protected, is the set of routers that are reachable from one or 258 more direct neighbors of S, except primary node E, without traversing 259 the node E. This MUST exclude any direct neighbors for which there 260 is at least one ECMP path from the direct neighbor traversing the 261 node E being protected. 263 For a cost-based definition for Node-protecting Extended P-Space 264 refer to Section 2.2.6.2. 266 2.2.3. Q-Space 268 The Remote-LFA [RFC7490] draft already defines this. The Q-space for 269 a link S-E being protected is the set of routers that can reach 270 primary node E, without traversing the S-E link on any of the 271 shortest path from the node Y to primary nexthop E. This MUST 272 exclude any destination for which there is at least one ECMP path 273 from the node Y to the primary nexthop E traversing the link(S-E) 274 being protected. 276 For a cost-based definition for Q-Space refer to Section 2.2.6.3. 278 2.2.4. Link-Protecting PQ Space 280 A node Y is in link-protecting PQ space w.r.t to the link (S-E) being 281 protected, if and only if, Y is present in both link-protecting 282 extended P-space and the Q-space for the link being protected. 284 2.2.5. Candidate Node-Protecting PQ Space 286 A node Y is in candidate node-protecting PQ space w.r.t to the node 287 (E) being protected, if and only if, Y is present in both node- 288 protecting extended P-space and the Q-space for the link being 289 protected. 291 It must be noted, that a node Y being in candidate node-protecting 292 PQ-space, does not guarantee that the R-LFA alternate path via the 293 same, in entirety, is unaffected in the event of a node failure of 294 primary nexthop node E. It only guarantees that the path segment 295 from S to PQ-node Y is unaffected by the same failure event. The PQ- 296 nodes in the candidate node-protecting PQ space may provide node 297 protection for only a subset of destinations that are reachable 298 through the corresponding primary link. 300 2.2.6. Cost-Based Definitions 302 This section provides cost-based definitions for some of the terms 303 introduced in Section 2.2 of this document. 305 2.2.6.1. Link-Protecting Extended P-Space 307 Please refer to Section 2.2.1 for a formal definition for Link- 308 protecting Extended P-Space. 310 A node Y is in link-protecting extended P-space w.r.t to the link 311 (S-E) being protected, if and only if, there exists at least one 312 direct neighbor of S, Ni, other than primary nexthop E, that 313 satisfies the following condition. 315 D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y) 317 Where, 318 D_opt(A,B) : Distance on most optimum path from A to B. 319 Ni : A direct neighbor of S other than primary 320 nexthop E. 321 Y : The node being evaluated for link-protecting 322 extended P-Space. 324 Figure 3: Link-Protecting Ext-P-Space Condition 326 2.2.6.2. Node-Protecting Extended P-Space 328 Please refer to Section 2.2.2 for a formal definition for Node- 329 protecting Extended P-Space. 331 A node Y is in node-protecting extended P-space w.r.t to the node E 332 being protected, if and only if, there exists at least one direct 333 neighbor of S, Ni, other than primary nexthop E, that satisfies the 334 following condition. 336 D_opt(Ni,Y) < D_opt(Ni,E) + D_opt(E,Y) 338 Where, 339 D_opt(A,B) : Distance on most optimum path from A to B. 340 E : The primary nexthop on shortest path from S 341 to destination. 342 Ni : A direct neighbor of S other than primary 343 nexthop E. 344 Y : The node being evaluated for node-protecting 345 extended P-Space. 347 Figure 4: Node-Protecting Ext-P-Space Condition 349 It must be noted that a node Y satisfying the condition in Figure 4 350 above only guarantees that the R-LFA alternate path segment from S 351 via direct neighbor Ni to the node Y is not affected in the event of 352 a node failure of E. It does not yet guarantee that the path segment 353 from node Y to the destination is also unaffected by the same failure 354 event. 356 2.2.6.3. Q-Space 358 Please refer to Section 2.2.3 for a formal definition for Q-Space. 360 A node Y is in Q-space w.r.t to the link (S-E) being protected, if 361 and only if, the following condition is satisfied. 363 D_opt(Y,E) < D_opt(S,E) + D_opt(Y,S) 365 Where, 366 D_opt(A,B) : Distance on most optimum path from A to B. 367 E : The primary nexthop on shortest path from S 368 to destination. 369 Y : The node being evaluated for Q-Space. 371 Figure 5: Q-Space Condition 373 2.3. Computing Node-protecting R-LFA Path 375 The R-LFA alternate path through a given PQ-node to a given 376 destination is comprised of two path segments as follows. 378 1. Path segment from the computing router to the PQ-node (Remote-LFA 379 alternate nexthop), and 381 2. Path segment from the PQ-node to the destination being protected. 383 So to ensure a R-LFA alternate path for a given destination provides 384 node-protection we need to ensure that none of the above path 385 segments are affected in the event of failure of the primary nexthop 386 node. Sections Section 2.3.1 and Section 2.3.2 shows how this can be 387 ensured. 389 2.3.1. Computing Candidate Node-protecting PQ-Nodes for Primary 390 nexthops 392 To choose a node-protecting R-LFA nexthop for a destination R3, 393 router S needs to consider a PQ-node from the candidate node- 394 protecting PQ-space for the primary nexthop E on shortest path from S 395 to R3. As mentioned in Section 2.2.2, to consider a PQ-node as 396 candidate node-protecting PQ-node, there must be at least one direct 397 neighbor Ni of S, such that all shortest paths from Ni to the PQ-node 398 does not traverse primary nexthop node E. 400 Implementations should run the inequality in Section 2.2.2 Figure 4 401 for all direct neighbor, other than primary nexthop node E, to 402 determine whether a node Y is a candidate node-protecting PQ-node. 403 All of the metrics needed by this inequality would have been already 404 collected from the forward SPFs rooted at each of direct neighbor S, 405 computed as part of standard LFA [RFC5286] implementation. With 406 reference to the topology in Figure 2, Table 3 below shows how the 407 above condition can be used to determine the candidate node- 408 protecting PQ-space for S-E link (primary nexthop E) 409 +------------+----------+----------+----------+---------+-----------+ 410 | Candidate | Direct | D_opt | D_opt | D_opt | Condition | 411 | PQ-node | Nbr (Ni) | (Ni,Y) | (Ni,E) | (E,Y) | Met | 412 | (Y) | | | | | | 413 +------------+----------+----------+----------+---------+-----------+ 414 | R2 | N | 2 (N,R2) | 1 (N,E) | 2 | Yes | 415 | | | | | (E,R2) | | 416 | R3 | N | 2 (N,R3) | 1 (N,E) | 1 | No | 417 | | | | | (E,R3) | | 418 +------------+----------+----------+----------+---------+-----------+ 420 Table 3: Node-protection evaluation for R-LFA repair tunnel to PQ- 421 node 423 As seen in the above Table 3 , R3 does not meet the node-protecting 424 extended-p-space inequality and so, while R2 is in candidate node- 425 protecting PQ space, R3 is not. 427 Some SPF implementations may also produce a list of links and nodes 428 traversed on the shortest path(s) from a given root to others. In 429 such implementations, router S may have executed a forward SPF with 430 each of its direct neighbors as the SPF root, executed as part of the 431 standard LFA [RFC5286] computations. So S may re-use the list of 432 links and nodes collected from the same SPF computations, to decide 433 whether a node Y is a candidate node-protecting PQ-node or not. A 434 node Y shall be considered as a node-protecting PQ-node, if and only 435 if, there is at least one direct neighbor of S, other than the 436 primary nexthop E, for which, the primary nexthop node E does not 437 exist on the list of nodes traversed on any of the shortest path(s) 438 from the direct neighbor to the PQ-node. Table 4 below is an 439 illustration of the mechanism with the topology in Figure 2. 441 +-----------+-------------------+-----------------+-----------------+ 442 | Candidate | Repair Tunnel | Link-Protection | Node-Protection | 443 | PQ-node | Path(Repairing | | | 444 | | router to PQ- | | | 445 | | node) | | | 446 +-----------+-------------------+-----------------+-----------------+ 447 | R2 | S->N->R1->R2 | Yes | Yes | 448 | R2 | S->E->R3->R2 | No | No | 449 | R3 | S->N->E->R3 | Yes | No | 450 +-----------+-------------------+-----------------+-----------------+ 452 Table 4: Protection of Remote-LFA tunnel to the PQ-node 454 As seen in the above Table 4 while R2 is candidate node-protecting 455 Remote-LFA nexthop for R3 and D2, it is not so for E and D1, since 456 the primary nexthop E is in the shortest path from R2 to E and D1. 458 2.3.2. Computing node-protecting paths from PQ-nodes to destinations 460 Once a computing router finds all the candidate node-protecting PQ- 461 nodes for a given directly attached primary link, it shall follow the 462 procedure as proposed in this section, to choose one or more node- 463 protecting R-LFA paths, for destinations reachable through the same 464 primary link in the primary SPF graph. 466 To find a node-protecting R-LFA path for a given destination, the 467 computing router needs to pick a subset of PQ-nodes from the 468 candidate node-protecting PQ-space for the corresponding primary 469 nexthop, such that all the path(s) from the PQ-node(s) to the given 470 destination remain unaffected in the event of a node failure of the 471 primary nexthop node. To ensure this, the computing router will need 472 to ensure that, the primary nexthop node should not be on any of the 473 shortest paths from the PQ-node to the given destination. 475 This document proposes an additional forward SPF computation for each 476 of the PQ-nodes, to discover all shortest paths from the PQ-nodes to 477 the destination. The additional forward SPF computation for each PQ- 478 node, shall help determine, if a given primary nexthop node is on the 479 shortest paths from the PQ-node to the given destination or not. To 480 determine if a given candidate node-protecting PQ-node provides node- 481 protecting alternate for a given destination, the primary nexthop 482 node should not be on any of the shortest paths from the PQ-node to 483 the given destination. On running the forward SPF on a candidate 484 node-protecting PQ-node the computing router shall run the inequality 485 in Figure 6 below. A PQ-node that does not qualify the condition for 486 a given destination, does not guarantee node-protection for the path 487 segment from the PQ-node to the given destination. 489 D_opt(Y,D) < D_opt(Y,E) + Distance_opt(E,D) 491 Where, 492 D_opt(A,B) : Distance on most optimum path from A to B. 493 D : The destination node. 494 E : The primary nexthop on shortest path from S 495 to destination. 496 Y : The node-protecting PQ-node being evaluated 498 Figure 6: Node-Protecting Condition for PQ-node to Destination 500 All of the above metric costs except D_opt(Y, D), can be obtained 501 with forward and reverse SPFs with E(the primary nexthop) as the 502 root, run as part of the regular LFA and Remote-LFA implementation. 503 The Distance_opt(Y, D) metric can only be determined by the 504 additional forward SPF run with PQ-node Y as the root. With 505 reference to the topology in Figure 2, Table 5 below shows how the 506 above condition can be used to determine node-protection with node- 507 protecting PQ-node R2. 509 +-------------+------------+---------+--------+---------+-----------+ 510 | Destination | Primary-NH | D_opt | D_opt | D_opt | Condition | 511 | (D) | (E) | (Y, D) | (Y, E) | (E, D) | Met | 512 +-------------+------------+---------+--------+---------+-----------+ 513 | R3 | E | 1 | 2 | 1 | Yes | 514 | | | (R2,R3) | (R2,E) | (E,R3) | | 515 | E | E | 2 | 2 | 0 (E,E) | No | 516 | | | (R2,E) | (R2,E) | | | 517 | D1 | E | 3 | 2 | 1 | No | 518 | | | (R2,D1) | (R2,E) | (E,D1) | | 519 | D2 | E | 2 | 2 | 1 | Yes | 520 | | | (R2,D2) | (R2,E) | (E,D2) | | 521 +-------------+------------+---------+--------+---------+-----------+ 523 Table 5: Node-protection evaluation for R-LFA path segment between 524 PQ-node and destination 526 As seen in the above example above, R2 does not meet the node- 527 protecting inequality for destination E, and D1. And so, once again, 528 while R2 is a node-protecting Remote-LFA nexthop for R3 and D2, it is 529 not so for E and D1. 531 In SPF implementations that also produce a list of links and nodes 532 traversed on the shortest path(s) from a given root to others, to 533 determine whether a PQ-node provides node-protection for a given 534 destination or not, the list of nodes computed from forward SPF run 535 on the PQ-node, for the given destination, should be inspected. In 536 case the list contains the primary nexthop node, the PQ-node does not 537 provide node-protection. Else, the PQ-node guarantees node- 538 protecting alternate for the given destination. Below is an 539 illustration of the mechanism with candidate node-protecting PQ-node 540 R2 in the topology in Figure 2. 542 +-------------+-----------------+-----------------+-----------------+ 543 | Destination | Shortest Path | Link-Protection | Node-Protection | 544 | | (Repairing | | | 545 | | router to PQ- | | | 546 | | node) | | | 547 +-------------+-----------------+-----------------+-----------------+ 548 | R3 | R2->R3 | Yes | Yes | 549 | E | R2->R3->E | Yes | No | 550 | D1 | R2->R3->E->D1 | Yes | No | 551 | D2 | R2->R3->D2 | Yes | Yes | 552 +-------------+-----------------+-----------------+-----------------+ 554 Table 6: Protection of Remote-LFA path between PQ-node and 555 destination 557 As seen in the above example while R2 is candidate node-protecting 558 R-LFA nexthop for R3 and D2, it is not so for E and D1, since the 559 primary nexthop E is in the shortest path from R2 to E and D1. 561 The procedure described in this document helps no more than to 562 determine whether a given Remote-LFA alternate provides node- 563 protection for a given destination or not. It does not find out any 564 new Remote-LFA alternate nexthops, outside the ones already computed 565 by standard Remote-LFA procedure. However, in case of availability 566 of more than one PQ-node (Remote-LFA alternates) for a destination, 567 and node-protection is required for the given primary nexthop, this 568 procedure will eliminate the PQ-nodes that do not provide node- 569 protection and choose only the ones that does. 571 2.3.3. Limiting extra computational overhead 573 In addition to the extra reverse SPF computation, one per directly 574 connected neighbor, suggested by the Remote-LFA [RFC7490] draft, this 575 document proposes a forward SPF per PQ-node discovered in the 576 network. Since the average number of PQ-nodes found in any network 577 is considerably more than the number of direct neighbors of the 578 computing router, the proposal of running one forward SPF per PQ-node 579 may add considerably to the overall SPF computation time. 581 To limit the computational overhead of the approach proposed, this 582 document proposes that implementations MUST choose a subset from the 583 entire set of PQ-nodes computed in the network, with a finite limit 584 on the number of PQ-nodes in the subset. Implementations MUST choose 585 a default value for this limit and may provide user with a 586 configuration knob to override the default limit. Implementations 587 MUST also evaluate some default preference criteria while considering 588 a PQ-node in this subset. Finally, implementations MAY also allow 589 user to override the default preference criteria, by providing a 590 policy configuration for the same. 592 This document proposes that implementations SHOULD use a default 593 preference criteria for PQ-node selection which will put a score on 594 each PQ-node, proportional to the number of primary interfaces for 595 which it provides coverage, its distance from the computing router, 596 and its router-id (or system-id in case of IS-IS). PQ-nodes that 597 cover more primary interfaces SHOULD be preferred over PQ-nodes that 598 cover fewer primary interfaces. When two or more PQ-nodes cover the 599 same number of primary interfaces, PQ-nodes which are closer (based 600 on metric) to the computing router SHOULD be preferred over PQ-nodes 601 farther away from it. For PQ-nodes that cover the same number of 602 primary interfaces and are the same distance from the the computing 603 router, the PQ-node with smaller router-id (or system-id in case of 604 IS-IS) SHOULD be preferred. 606 Once a subset of PQ-nodes is found, computing router shall run a 607 forward SPF on each of the PQ-nodes in the subset to continue with 608 procedures proposed in section Section 2.3.2. 610 3. Manageabilty of Remote-LFA Alternate Paths 612 3.1. The Problem 614 With the regular Remote-LFA [RFC7490] functionality the computing 615 router may compute more than one PQ-node as usable Remote-LFA 616 alternate nexthops. Additionally an alternate selection policy may 617 be configured to enable the network operator to choose one of them as 618 the most appropriate Remote-LFA alternate. For such policy-based 619 alternate selection to run, all the relevant path characteristics for 620 each the alternate paths (one through each of the PQ-nodes), needs to 621 be collected. As mentioned before in section Section 2.3 the R-LFA 622 alternate path through a given PQ-node to a given destination is 623 comprised of two path segments. 625 The first path segment (i.e. from the computing router to the PQ- 626 node) can be calculated from the regular forward SPF done as part of 627 standard and remote LFA computations. However without the mechanism 628 proposed in section Section 2.3.2 of this document, there is no way 629 to determine the path characteristics for the second path segment 630 (i.e from the PQ-node to the destination). In the absence of the 631 path characteristics for the second path segment, two Remote-LFA 632 alternate path may be equally preferred based on the first path 633 segments characteristics only, although the second path segment 634 attributes may be different. 636 3.2. The Solution 638 The additional forward SPF computation proposed in section 639 Section 2.3.2 document shall also collect links, nodes and path 640 characteristics along the second path segment. This shall enable 641 collection of complete path characteristics for a given Remote-LFA 642 alternate path to a given destination. The complete alternate path 643 characteristics shall then facilitate more accurate alternate path 644 selection while running the alternate selection policy. 646 Like specified in Section 2.3.3 to limit the computational overhead 647 of the approach proposed, forward SPF computations MUST be run on a 648 selected subset from the entire set of PQ-nodes computed in the 649 network, with a finite limit on the number of PQ-nodes in the subset. 650 The detailed suggestion on how to select this subset is specified in 651 the same section. While this limits the number of possible alternate 652 paths provided to the alternate-selection policy, this is needed keep 653 the computational complexity within affordable limits. However if 654 the alternate-selection policy is very restrictive this may leave few 655 destinations in the entire toplogy without protection. Yet this 656 limitation provides a necessary tradeoff between extensive coverage 657 and immense computational overhead. 659 4. Acknowledgements 661 Many thanks to Bruno Decraene for providing his useful comments. We 662 would also like to thank Uma Chunduri for reviewing this document and 663 providing valuable feedback. Also, many thanks to Harish Raghuveer 664 for his review and comments on the initial versions of this document. 666 5. IANA Considerations 668 N/A. - No protocol changes are proposed in this document. 670 6. Security Considerations 672 This document does not introduce any change in any of the protocol 673 specifications. It simply proposes to run an extra SPF rooted on 674 each PQ-node discovered in the whole network. 676 7. References 678 7.1. Normative References 680 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 681 Requirement Levels", BCP 14, RFC 2119, 682 DOI 10.17487/RFC2119, March 1997, 683 . 685 7.2. Informative References 687 [I-D.ietf-rtgwg-lfa-manageability] 688 Litkowski, S., Decraene, B., Filsfils, C., Raza, K., 689 Horneffer, M., and P. Sarkar, "Operational management of 690 Loop Free Alternates", draft-ietf-rtgwg-lfa- 691 manageability-11 (work in progress), June 2015. 693 [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for 694 IP Fast Reroute: Loop-Free Alternates", RFC 5286, 695 DOI 10.17487/RFC5286, September 2008, 696 . 698 [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. 699 So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", 700 RFC 7490, DOI 10.17487/RFC7490, April 2015, 701 . 703 Authors' Addresses 705 Pushpasis Sarkar (editor) 706 Juniper Networks, Inc. 707 Electra, Exora Business Park 708 Bangalore, KA 560103 709 India 711 Email: pushpasis.ietf@gmail.com; psarkar@juniper.net 713 Shraddha Hegde 714 Juniper Networks, Inc. 715 Electra, Exora Business Park 716 Bangalore, KA 560103 717 India 719 Email: shraddha@juniper.net 721 Chris Bowers 722 Juniper Networks, Inc. 723 1194 N. Mathilda Ave. 724 Sunnyvale, CA 94089 725 US 727 Email: cbowers@juniper.net 728 Hannes Gredler 729 Unaffiliated 731 Email: hannes@gredler.at 733 Stephane Litkowski 734 Orange 736 Email: stephane.litkowski@orange.com