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