idnits 2.17.00 (12 Aug 2021) /tmp/idnits8707/draft-ietf-rtgwg-rlfa-node-protection-02.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 ([I-D.ietf-rtgwg-remote-lfa]), 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 == 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 D1, if we choose R3 as the R-LFA nexthop, it does not provide node-protection for R3 and D1 anymore. If S chooses R3 as the R-LFA nexthop, in the event of the node-failure on primary nexthop E, the alternate path from S to R-LFA nexthop 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 (June 15, 2015) is 2531 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) == Outdated reference: draft-ietf-rtgwg-lfa-manageability has been published as RFC 7916 == Outdated reference: draft-ietf-rtgwg-remote-lfa has been published as RFC 7490 Summary: 1 error (**), 0 flaws (~~), 5 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 H. Gredler 4 Intended status: Standards Track S. Hegde 5 Expires: December 17, 2015 C. Bowers 6 Juniper Networks, Inc. 7 S. Litkowski 8 Orange 9 H. Raghuveer 10 June 15, 2015 12 Remote-LFA Node Protection and Manageability 13 draft-ietf-rtgwg-rlfa-node-protection-02 15 Abstract 17 The loop-free alternates computed following the current Remote-LFA 18 [I-D.ietf-rtgwg-remote-lfa] specification gaurantees only link- 19 protection. The resulting Remote-LFA nexthops (also called PQ- 20 nodes), may not gaurantee node-protection for all destinations being 21 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 December 17, 2015. 54 Copyright Notice 56 Copyright (c) 2015 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. Few Additional Definitions . . . . . . . . . . . . . . . 5 75 2.2.1. Link-Protecting Extended P-Space . . . . . . . . . . 5 76 2.2.2. Node-Protecting Extended P-Space . . . . . . . . . . 6 77 2.2.3. Q-Space . . . . . . . . . . . . . . . . . . . . . . . 7 78 2.2.4. Link-Protecting PQ Space . . . . . . . . . . . . . . 8 79 2.2.5. Candidate Node-Protecting PQ Space . . . . . . . . . 8 80 2.3. Computing Node-protecting R-LFA Path . . . . . . . . . . 8 81 2.3.1. Computing Candidate Node-protecting PQ-Nodes for 82 Primary nexthops . . . . . . . . . . . . . . . . . . 8 83 2.3.2. Computing node-protecting paths from PQ-nodes to 84 destinations . . . . . . . . . . . . . . . . . . . . 10 85 2.3.3. Limiting extra computational overhead . . . . . . . . 12 86 3. Manageabilty of Remote-LFA Alternate Paths . . . . . . . . . 13 87 3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 13 88 3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 14 89 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14 90 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 91 6. Security Considerations . . . . . . . . . . . . . . . . . . . 14 92 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 14 93 7.1. Normative References . . . . . . . . . . . . . . . . . . 15 94 7.2. Informative References . . . . . . . . . . . . . . . . . 15 95 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 15 97 1. Introduction 99 The Remote-LFA [I-D.ietf-rtgwg-remote-lfa] specification provides 100 loop-free alternates that gaurantees only link-protection. The 101 resulting Remote-LFA alternate nexthops (also referred to as the PQ- 102 nodes) may not provide node-protection for all destinations covered 103 by the same, in case of failure of the primary nexthop node. Neither 104 does the specification provide a means to determine the same. 106 Also, the LFA Manageability [I-D.ietf-rtgwg-lfa-manageability] 107 document, requires a computing router to find all possible (including 108 all possible Remote-LFA) alternate nexthops, collect the complete set 109 of path characteristics for each alternate path, run a alternate- 110 selection policy (configured by the operator), and find the best 111 alternate path. This will require the Remote-LFA implementation to 112 gather all the required path characteristics along each link on the 113 entire Remote-LFA alternate path. 115 With current LFA [RFC5286] and Remote-LFA implementations, the 116 forward SPF (and reverse SPF) is run on the computing router and its 117 immediate 1-hop routers as the roots. While that enables computation 118 of path attributes (e.g. SRLG, Admin-groups) for first alternate 119 path segment from the computing router to the PQ-node, there is no 120 means for the computing router to gather any path attributes for the 121 path segment from the PQ-node to destination. Consecutively any 122 policy-based selection of alternate paths will consider only the path 123 attributes from the computing router up until the PQ-node. 125 This document describes a procedure for determining node-protection 126 with Remote-LFA. The same procedure are also extended for collection 127 of complete set of path attributes, enabling more accurate policy- 128 based selection for alternate paths obtained with Remote-LFA. 130 2. Node Protection with Remote-LFA 132 Node-protection is required to provide protection of traffic on a 133 given forwarding node, against the failure of the first-hop node on 134 the primary forwarding path. Such protection becomes more critical 135 in the absence of mechanisms like non-stop-routing in the network. 136 Certain operators refrains from deploying non-stop-routing in their 137 network, due to the significant additional performance complexities 138 it comes along with. In such cases node-protection is a must to 139 gaurantee un-interrupted flow of traffic, even in the case of an 140 entire forwarding node going down. 142 The following sections discusses the node-protection problem in the 143 context of Remote-LFA and proposes a solution for solving the same. 145 2.1. The Problem 147 To better illustrate the problem and the solution proposed in this 148 document the following topology diagram from the Remote-LFA 149 [I-D.ietf-rtgwg-remote-lfa] draft is being re-used with slight 150 modification. 152 D1 153 / 154 S-x-E 155 / \ 156 N R3--D2 157 \ / 158 R1---R2 160 Figure 1: Topology 1 162 In the above topology, for all (non-ECMP) destinations reachable via 163 the S-E link there is no standard LFA alternate. As per the Remote- 164 LFA [I-D.ietf-rtgwg-remote-lfa] alternate specifications node R2 165 being the only PQ-node for the S-E link provides nexthop for all the 166 above destinations. Table 1 below, shows all possible primary and 167 Remote-LFA alternate paths for each destination. 169 +-------------+--------------+---------+-------------------------+ 170 | Destination | Primary Path | PQ-node | Remote-LFA Backup Path | 171 +-------------+--------------+---------+-------------------------+ 172 | R3 | S->E->R3 | R2 | S=>N=>R1=>R2->R3 | 173 | E | S->E | R2 | S=>N=>R1=>R2->R3->E | 174 | D1 | S->E->D1 | R2 | S=>N=>R1=>R2->R3->E->D1 | 175 | D2 | S->E->R3->D2 | R2 | S=>N=>R1=>R2->R3->D2 | 176 +-------------+--------------+---------+-------------------------+ 178 Table 1: Remote-LFA backup paths via PQ-node R2 180 A closer look at Table 1 shows that, while the PQ-node R2 provides 181 link-protection for all the destinations, it does not provide node- 182 protection for destinations E and D1. In the event of the node- 183 failure on primary nexthop E, the alternate path from Remote-LFA 184 nexthop R2 to E and D1 also becomes unavailable. So for a Remote-LFA 185 nexthop to provide node-protection for a given destination, it is 186 mandatory that, the shortest path from the given PQ-node to the given 187 destination MUST not traverse the primary nexthop. 189 In another extension of the topology in Figure 1 let us consider an 190 additional link between N and E. 192 D1 193 / 194 S-x-E 195 / / \ 196 N---+ R3--D2 197 \ / 198 R1---R2 200 Figure 2: Topology 2 202 In the above topology, the S-E link is no more on any of the shortest 203 paths from N to R3. Hence R3 is also included in both the Extended-P 204 space and PQ space of E (w.r.t S-E link). Table 2 below, shows all 205 possible primary and R-LFA alternate paths via PQ-node R3, for each 206 destination reachable through the S-E link in the above topology. 207 The R-LFA alternate paths via PQ-node R2 remains same as in Table 1. 209 +-------------+--------------+---------+------------------------+ 210 | Destination | Primary Path | PQ-node | Remote-LFA Backup Path | 211 +-------------+--------------+---------+------------------------+ 212 | R3 | S->E->R3 | R3 | S=>N=>E=>R3 | 213 | E | S->E | R3 | S=>N=>E=>R3->E | 214 | D1 | S->E->D1 | R3 | S=>N=>E=>R3->E->D1 | 215 | D2 | S->E->R3->D2 | R3 | S=>N=>E=>R3->D2 | 216 +-------------+--------------+---------+------------------------+ 218 Table 2: Remote-LFA backup paths via PQ-node R3 220 Again a closer look at Table 2 shows that, unlike Table 1, where the 221 single PQ-node R2 provided node-protection, for destinations R3 and 222 D1, if we choose R3 as the R-LFA nexthop, it does not provide node- 223 protection for R3 and D1 anymore. If S chooses R3 as the R-LFA 224 nexthop, in the event of the node-failure on primary nexthop E, the 225 alternate path from S to R-LFA nexthop R3 also becomes unavailable. 226 So for a Remote-LFA nexthop to provide node-protection for a given 227 destination, it is also mandatory that, the shortest path from S to 228 the chosen PQ-node MUST not traverse the primary nexthop node. 230 2.2. Few Additional Definitions 232 This document adds and enhances the following definitions extending 233 the ones mentioned in Remote-LFA [I-D.ietf-rtgwg-remote-lfa] draft. 235 2.2.1. Link-Protecting Extended P-Space 237 The Remote-LFA [I-D.ietf-rtgwg-remote-lfa] draft already defines 238 this. The link-protecting extended P-space for a link S-E being 239 protected is the set of routers that are reachable from one or more 240 direct neighbors of S, except primary node E, without traversing the 241 S-E link on any of the shortest path from the direct neighbor to the 242 router. This MUST exclude any direct neighbor for which there is 243 atleast one ECMP path from the direct neighbor traversing the 244 link(S-E) being protected. 246 A node Y is in link-protecting extended P-space w.r.t to the link 247 (S-E) being protected, if and only if, there exists atleast one 248 direct neighbor of S, Ni, other than primary nexthop E, that 249 satisfies the following condition. 251 D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y) 253 Where, 254 D_opt(A,B) : Distance on most optimum path from A to B. 255 Ni : A direct neighbor of S other than primary 256 nexthop E. 257 Y : The node being evaluated for link-protecting 258 extended P-Space. 260 Figure 3: Link-Protecting Ext-P-Space Condition 262 2.2.2. Node-Protecting Extended P-Space 264 The node-protecting extended P-space for a primary nexthop node E 265 being protected, is the set of routers that are reachable from one or 266 more direct neighbors of S, except primary node E, without traversing 267 the node E. This MUST exclude any direct neighbors for which there 268 is atleast one ECMP path from the direct neighbor traversing the node 269 E being protected. 271 A node Y is in node-protecting extended P-space w.r.t to the node E 272 being protected, if and only if, there exists atleast one direct 273 neighbor of S, Ni, other than primary nexthop E, that satisfies the 274 following condition. 276 D_opt(Ni,Y) < D_opt(Ni,E) + D_opt(E,Y) 278 Where, 279 D_opt(A,B) : Distance on most optimum path from A to B. 280 E : The primary nexthop on shortest path from S 281 to destination. 282 Ni : A direct neighbor of S other than primary 283 nexthop E. 284 Y : The node being evaluated for node-protecting 285 extended P-Space. 287 Figure 4: Node-Protecting Ext-P-Space Condition 289 It must be noted that a node Y satisfying the condition in Figure 4 290 above only guarantees that the R-LFA alternate path segment from S 291 via direct neighbor Ni to the node Y is not affected in the event of 292 a node failure of E. It does not yet guarantee that the path segment 293 from node Y to the destination is also unaffected by the same failure 294 event. 296 2.2.3. Q-Space 298 The Remote-LFA [I-D.ietf-rtgwg-remote-lfa] draft already defines 299 this. The Q-space for a link S-E being protected is the set of 300 routers that can reach primary node E, without traversing the S-E 301 link on any of the shortest path from the node Y to primary nexthop 302 E. This MUST exclude any destination for which there is atleast one 303 ECMP path from the node Y to the primary nexthop E traversing the 304 link(S-E) being protected. 306 A node Y is in Q-space w.r.t to the link (S-E) being protected, if 307 and only if, the following condition is satisfied. 309 D_opt(Y,E) < D_opt(S,E) + D_opt(Y,S) 311 Where, 312 D_opt(A,B) : Distance on most optimum path from A to B. 313 E : The primary nexthop on shortest path from S 314 to destination. 315 Y : The node being evaluated for Q-Space. 317 Figure 5: Q-Space Condition 319 2.2.4. Link-Protecting PQ Space 321 A node Y is in link-protecting PQ space w.r.t to the link (S-E) being 322 protected, if and only if, Y is present in both link-protecting 323 extended P-space and the Q-space for the link being protected. 325 2.2.5. Candidate Node-Protecting PQ Space 327 A node Y is in candidate node-protecting PQ space w.r.t to the node 328 (E) being protected, if and only if, Y is present in both node- 329 protecting extended P-space and the Q-space for the link being 330 protected. 332 Again it must be noted that a node Y being in candidate node- 333 protecting PQ-space does not guarantee that the R-LFA alternate path 334 via the same, in entirety, is unaffected in the event of a node 335 failure of primary nexthop node E. It only guarantees that the path 336 segment from S to PQ-node Y is unaffected by the same failure event. 337 The PQ-nodes in the candidate node-protecting PQ space may provide 338 node protection for only a subset of destinations that are reachable 339 through the corresponding primary link. 341 2.3. Computing Node-protecting R-LFA Path 343 The R-LFA alternate path through a given PQ-node to a given 344 destination comprises of two path segments as follows. 346 1. Path segment from the computing router to the PQ-node (Remote-LFA 347 alternate nexthop), and 349 2. Path segment from the PQ-node to the destination being protected. 351 So to ensure a R-LFA alternate path for a given destination provides 352 node-protection we need to ensure that none of the above path 353 segments are unaffected in the event of failure of the primary 354 nexthop node. Sections Section 2.3.1 and Section 2.3.2 shows how 355 this can be ensured. 357 2.3.1. Computing Candidate Node-protecting PQ-Nodes for Primary 358 nexthops 360 To choose a node-protecting R-LFA nexthop for a destination R3, 361 router S needs to consider a PQ-node from the candidate node- 362 protecting PQ-space for the primary nexthop E on shortest path from S 363 to R3. As mentioned in Section 2.2.2, to consider a PQ-node as 364 candidate node-protecting PQ-node, there must be atleast one direct 365 neighbor Ni of S, such that all shortest paths from Ni to the PQ-node 366 does not traverse primary nexthop node E. 368 Implementations should run the inequality in Section 2.2.2 Figure 4 369 for all direct neighbor, other than primary nexthop node E, to 370 determine whether a node Y is a candidate node-protecting PQ-node. 371 All of the metrics needed by this inequality would have been already 372 collected from the forward SPFs rooted at each of direct neighbor S, 373 computed as part of standard LFA [RFC5286] implementation. With 374 reference to the topology in Figure 2, Table 3 below shows how the 375 above condition can be used to determine the candidate node- 376 protecting PQ-space for S-E link (primary nexthop E) 378 +------------+----------+----------+----------+---------+-----------+ 379 | Candidate | Direct | D_opt | D_opt | D_opt | Condition | 380 | PQ-node | Nbr (Ni) | (Ni,Y) | (Ni,E) | (E,Y) | Met | 381 | (Y) | | | | | | 382 +------------+----------+----------+----------+---------+-----------+ 383 | R2 | N | 2 (N,R2) | 1 (N,E) | 2 | Yes | 384 | | | | | (E,R2) | | 385 | R3 | N | 2 (N,R3) | 1 (N,E) | 1 | No | 386 | | | | | (E,R3) | | 387 +------------+----------+----------+----------+---------+-----------+ 389 Table 3: Node-protection evaluation for R-LFA repair tunnel to PQ- 390 node 392 As seen in the above Table 3 , R3 does not meet the node-protecting 393 extended-p-space inequality And so, while R2 is in candidate node- 394 protecting PQ space, R3 is not. 396 Some SPF implementations may also produce a list of links and nodes 397 traversed on the shortest path(s) from a given root to others. In 398 such implementations, router S may have executed a forward SPF with 399 each of it's direct neighbors as the SPF root, executed as part of 400 the standard LFA [RFC5286] computations. So S may re-use the list of 401 links and nodes collected from the same SPF computations, to decide 402 whether a node Y is a candidate node-protecting PQ-node or not. A 403 node Y shall be considered as a node-protecting PQ-node, if and only 404 if, there is atleast one direct neighbor of S, other than the primary 405 nexthop E, for which, the primary nexthop node E does not exist on 406 the list of nodes traversed on any of the shortest path(s) from the 407 direct neighbor to the PQ-node. Table 4 below is an illustration of 408 the mechanism with the topology in Figure 2. 410 +-----------+-------------------+-----------------+-----------------+ 411 | Candidate | Repair Tunnel | Link-Protection | Node-Protection | 412 | PQ-node | Path(Repairing | | | 413 | | router to PQ- | | | 414 | | node) | | | 415 +-----------+-------------------+-----------------+-----------------+ 416 | R2 | S->N->R1->R2 | Yes | Yes | 417 | R2 | S->E->R3->R2 | No | No | 418 | R3 | S->N->E->R3 | Yes | No | 419 +-----------+-------------------+-----------------+-----------------+ 421 Table 4: Protection of Remote-LFA tunnel to the PQ-node 423 As seen in the above Table 4 while R2 is candidate node-protecting 424 Remote-LFA nexthop for R3 and D2, it is not so for E and D1, since 425 the primary nexthop E is in the shortest path from R2 to E and F. 427 2.3.2. Computing node-protecting paths from PQ-nodes to destinations 429 Once a computing router finds all the candidate node-protecting PQ- 430 nodes for a given directly attached primary link, it shall follow the 431 procedure in proposed in this section, to choose one or more node- 432 protecting R-LFA paths, for destinations reachable through the same 433 primary link in the primary SPF graph. 435 To find a node-protecting R-LFA path for a given destination, the 436 computing router needs to pick a subset of PQ-nodes from the 437 candidate node-protecting PQ-space for the corresponding primary 438 nexthop, such that all the path(s) from the PQ-node(s) to the given 439 destination remain unaffected in the event of a node failure of 440 primary nexthop node. To ensure this, the computing router will need 441 to ensure that, the primary nexthop node should not be on any of the 442 shortest paths from the PQ-node to the given destination. 444 This document proposes an additional forward SPF computation for each 445 of the PQ-nodes, to discover all shortest paths from the PQ-nodes to 446 the destination. The additional forward SPF computation for each PQ- 447 node, shall help determine, if a given primary nexthop node is on the 448 shortest paths from the PQ-node to the given destination or not. To 449 determine if a given candidate node-protecting PQ-node provides node- 450 protecting alternate for a given destination, the primary nexthop 451 node should not be on any of the shortest paths from the PQ-node to 452 the given destination. On running the forward SPF on a candidate 453 node-protecting PQ-node the computing router shall run the inequality 454 in Figure 6 below. PQ-nodes that does not qualify the condition for 455 a given destination, does not gaurantee node-protection for the path 456 segment from the PQ-node to the given destination. 458 D_opt(Y,D) < D_opt(Y,E) + Distance_opt(E,D) 460 Where, 461 D_opt(A,B) : Distance on most optimum path from A to B. 462 D : The destination node. 463 E : The primary nexthop on shortest path from S 464 to destination. 465 Y : The node-protecting PQ-node being evaluated 467 Figure 6: Node-Protecting Condition for PQ-node to Destination 469 All of the above metric costs except D_opt(Y, D), can be obtained 470 with forward and reverse SPFs with E(the primary nexthop) as the 471 root, run as part of the regular LFA and Remote-LFA implementation. 472 The Distance_opt(Y, D) metric can only be determined by the 473 additional forward SPF run with PQ-node Y as the root. With 474 reference to the topology in Figure 2, Table 5 below shows how the 475 above condition can be used to determine node-protection with node- 476 protecting PQ-node R2. 478 +-------------+------------+---------+--------+---------+-----------+ 479 | Destination | Primary-NH | D_opt | D_opt | D_opt | Condition | 480 | (D) | (E) | (Y, D) | (Y, E) | (E, D) | Met | 481 +-------------+------------+---------+--------+---------+-----------+ 482 | R3 | E | 1 | 2 | 1 | Yes | 483 | | | (R2,R3) | (R2,E) | (E,R3) | | 484 | E | E | 2 | 2 | 0 (E,E) | No | 485 | | | (R2,E) | (R2,E) | | | 486 | D1 | E | 3 | 2 | 1 | No | 487 | | | (R2,D1) | (R2,E) | (E,D1) | | 488 | D2 | E | 2 | 2 | 1 | Yes | 489 | | | (R2,D2) | (R2,E) | (E,D2) | | 490 +-------------+------------+---------+--------+---------+-----------+ 492 Table 5: Node-protection evaluation for R-LFA path segment between 493 PQ-node and destination 495 As seen in the above example above, R2 does not meet the node- 496 protecting inequality for destination E, and F. And so, once again, 497 while R2 is a node-protecting Remote-LFA nexthop for R3 and G, it is 498 not so for E and F. 500 In SPF implementations that also produce a list of links and nodes 501 traversed on the shortest path(s) from a given root to others, to 502 determine whether a PQ-node provides node-protection for a given 503 destination or not, the list of nodes computed from forward SPF run 504 on the PQ-node, for the given destination, should be inspected. In 505 case the list contains the primary nexthop node, the PQ-node does not 506 provide node-protection. Else, the PQ-node guarantees node- 507 protecting alternate for the given destination. Below is an 508 illustration of the mechanism with candidate node-protecting PQ-node 509 R2 in the topology in Figure 2. 511 +-------------+-----------------+-----------------+-----------------+ 512 | Destination | Shortest Path | Link-Protection | Node-Protection | 513 | | (Repairing | | | 514 | | router to PQ- | | | 515 | | node) | | | 516 +-------------+-----------------+-----------------+-----------------+ 517 | R3 | R2->R3 | Yes | Yes | 518 | E | R2->R3->E | Yes | No | 519 | D1 | R2->R3->E->D1 | Yes | No | 520 | D2 | R2->R3->D2 | Yes | Yes | 521 +-------------+-----------------+-----------------+-----------------+ 523 Table 6: Protection of Remote-LFA path between PQ-node and 524 destination 526 As seen in the above example while R2 is candidate node-protecting 527 R-LFA nexthop for R3 and G, it is not so for E and F, since the 528 primary nexthop E is in the shortest path from R2 to E and F. 530 The procedure described in this document helps no more than to 531 determine whether a given Remote-LFA alternate provides node- 532 protection for a given destination or not. It does not find out any 533 new Remote-LFA alternate nexthops, outside the ones already computed 534 by standard Remote-LFA procedure. However, in case of availability 535 of more than one PQ-node (Remote-LFA alternates) for a destination, 536 and node-protection is required for the given primary nexthop, this 537 procedure will eliminate the PQ-nodes that do not provide node- 538 protection and choose only the ones that does. 540 2.3.3. Limiting extra computational overhead 542 In addition to the extra reverse SPF computation, one per directly 543 connected neighbor, suggested by the Remote-LFA 544 [I-D.ietf-rtgwg-remote-lfa] draft, this document proposes a forward 545 SPF per PQ-node discovered in the network. Since the average number 546 of PQ-nodes found in any network is considerably more than the number 547 of direct neighbors of the computing router, the proposal of running 548 one forward SPF per PQ-node may add considerably to the overall SPF 549 computation time. 551 To limit the computational overhead of the approach proposed, this 552 document proposes that implementations MUST choose a subset from the 553 entire set of PQ-nodes computed in the network, with a finite limit 554 on the number of PQ-nodes in the subset. Implementations MUST choose 555 a default value for this limit and may provide user with a 556 configuration knob to override the default limit. Implementations 557 MUST also evaluate some default preference criteria while considering 558 a PQ-node in this subset. Finally, implementations MAY also allow 559 user to override the default preference criteria, by providing a 560 policy configuration for the same. 562 This document proposes that implementations SHOULD use a default 563 preference criteria for PQ-node selection which will put a score on 564 each PQ-node, proportional to the number of primary interfaces for 565 which it provides coverage, its distance from the computing router, 566 and its router-id (or system-id in case of IS-IS). PQ-nodes that 567 cover more primary interfaces SHOULD be preferred over PQ-nodes that 568 cover fewer primary interfaces. When two or more PQ-nodes cover the 569 same number of primary interfaces, PQ-nodes which are closer (based 570 on metric) to the computing router SHOULD be preferred over PQ-nodes 571 farther away from it. For PQ-nodes that cover the same number of 572 primary interfaces and are the same distance from the the computing 573 router, the PQ-node with smaller router-id (or system-id in case of 574 IS-IS) SHOULD be preferred. 576 Once a subset of PQ-nodes is found, computing router shall run a 577 forward SPF on each of the PQ-nodes in the subset to continue with 578 procedures proposed in section Section 2.3.2. 580 3. Manageabilty of Remote-LFA Alternate Paths 582 3.1. The Problem 584 With the regular Remote-LFA [I-D.ietf-rtgwg-remote-lfa] functionality 585 the computing router may compute more than one PQ-node as usable 586 Remote-LFA alternate nexthops. Additionally an alternate selection 587 policy may be configured to enable the network operator to choose one 588 of them as the most appropriate Remote-LFA alternate. For such 589 policy-based alternate selection to run, all the relevant path 590 characteristics for each the alternate paths (one through each of the 591 PQ-nodes), needs to be collected. As mentioned befor in section 592 Section 2.3 the R-LFA alternate path through a given PQ-node to a 593 given destination comprises of two path segments. 595 The first path segment (i.e. from the computing router to the PQ- 596 node) can be calculated from the regular forward SPF done as part of 597 standard and remote LFA computations. However without the mechanism 598 proposed in section Section 2.3.2 of this document, there is no way 599 to determine the path characteristics for the second path segment 600 (i.e from the PQ-node to the destination). In the absence of the 601 path characteristics for the second path segment, two Remote-LFA 602 alternate path may be equally preferred based on the first path 603 segments characteristics only, although the second path segment 604 attributes may be different. 606 3.2. The Solution 608 The additional forward SPF computation proposed in section 609 Section 2.3.2 document shall also collect links, nodes and path 610 characteristics along the second path segment. This shall enable 611 collection of complete path characteristics for a given Remote-LFA 612 alternate path to a given destination. The complete alternate path 613 characteristics shall then facilitate more accurate alternate path 614 selection while running the alternate selection policy. 616 Like specified in Section 2.3.3 to limit the computational overhead 617 of the approach proposed, forward SPF computations MUST be run on a 618 selected subset from the entire set of PQ-nodes computed in the 619 network, with a finite limit on the number of PQ-nodes in the subset. 620 The detailed suggestion on how to select this subset is specified in 621 the same section. While this limits the number of possible alternate 622 paths provided to the alternate-selection policy, this is needed keep 623 the computational complexity within affordable limits. However if 624 the alternate-selection policy is very restrictive this may leave few 625 destinations in the entire toplogy without protection. Yet this 626 limitation provides a necessary tradeoff between extensive coverage 627 and immense computational overhead. 629 4. Acknowledgements 631 Many thanks to Bruno Decraene for providing his useful comments. We 632 would also like to thank Uma Chunduri for reviewing this document and 633 providing valuable feedback. 635 5. IANA Considerations 637 N/A. - No protocol changes are proposed in this document. 639 6. Security Considerations 641 This document does not introduce any change in any of the protocol 642 specifications. It simply proposes to run an extra SPF rooted on 643 each PQ-node discovered in the whole network. 645 7. References 646 7.1. Normative References 648 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 649 Requirement Levels", BCP 14, RFC 2119, March 1997. 651 7.2. Informative References 653 [I-D.ietf-rtgwg-lfa-manageability] 654 Litkowski, S., Decraene, B., Filsfils, C., Raza, K., 655 Horneffer, M., and p. psarkar@juniper.net, "Operational 656 management of Loop Free Alternates", draft-ietf-rtgwg-lfa- 657 manageability-03 (work in progress), February 2014. 659 [I-D.ietf-rtgwg-remote-lfa] 660 Bryant, S., Filsfils, C., Previdi, S., Shand, M., and S. 661 Ning, "Remote LFA FRR", draft-ietf-rtgwg-remote-lfa-06 662 (work in progress), May 2014. 664 [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast 665 Reroute: Loop-Free Alternates", RFC 5286, September 2008. 667 Authors' Addresses 669 Pushpasis Sarkar (editor) 670 Juniper Networks, Inc. 671 Electra, Exora Business Park 672 Bangalore, KA 560103 673 India 675 Email: psarkar@juniper.net 677 Hannes Gredler 678 Juniper Networks, Inc. 679 1194 N. Mathilda Ave. 680 Sunnyvale, CA 94089 681 US 683 Email: hannes@juniper.net 685 Shraddha Hegde 686 Juniper Networks, Inc. 687 Electra, Exora Business Park 688 Bangalore, KA 560103 689 India 691 Email: shraddha@juniper.net 692 Chris Bowers 693 Juniper Networks, Inc. 694 1194 N. Mathilda Ave. 695 Sunnyvale, CA 94089 696 US 698 Email: cbowers@juniper.net 700 Stephane Litkowski 701 Orange 703 Email: stephane.litkowski@orange.com 705 Harish Raghuveer 707 Email: harish.r.prabhu@gmail.com