idnits 2.17.1 draft-ietf-rtgwg-rlfa-node-protection-01.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 (December 15, 2014) is 3413 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: A later version (-11) exists of draft-ietf-rtgwg-lfa-manageability-03 == Outdated reference: A later version (-11) exists of draft-ietf-rtgwg-remote-lfa-06 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: June 18, 2015 C. Bowers 6 Juniper Networks, Inc. 7 S. Litkowski 8 Orange 9 H. Raghuveer 11 December 15, 2014 13 Remote-LFA Node Protection and Manageability 14 draft-ietf-rtgwg-rlfa-node-protection-01 16 Abstract 18 The loop-free alternates computed following the current Remote-LFA 19 [I-D.ietf-rtgwg-remote-lfa] specification gaurantees only link- 20 protection. The resulting Remote-LFA nexthops (also called PQ- 21 nodes), may not gaurantee node-protection for all destinations being 22 protected by it. 24 This document describes procedures for determining if a given PQ-node 25 provides node-protection for a specific destination or not. The 26 document also shows how the same procedure can be utilised for 27 collection of complete characteristics for alternate paths. 28 Knowledge about the characteristics of all alternate path is 29 precursory to apply operator defined policy for eliminating paths not 30 fitting constraints. 32 Requirements Language 34 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 35 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 36 document are to be interpreted as described in RFC2119 [RFC2119]. 38 Status of This Memo 40 This Internet-Draft is submitted in full conformance with the 41 provisions of BCP 78 and BCP 79. 43 Internet-Drafts are working documents of the Internet Engineering 44 Task Force (IETF). Note that other groups may also distribute 45 working documents as Internet-Drafts. The list of current Internet- 46 Drafts is at http://datatracker.ietf.org/drafts/current/. 48 Internet-Drafts are draft documents valid for a maximum of six months 49 and may be updated, replaced, or obsoleted by other documents at any 50 time. It is inappropriate to use Internet-Drafts as reference 51 material or to cite them other than as "work in progress." 53 This Internet-Draft will expire on June 18, 2015. 55 Copyright Notice 57 Copyright (c) 2014 IETF Trust and the persons identified as the 58 document authors. All rights reserved. 60 This document is subject to BCP 78 and the IETF Trust's Legal 61 Provisions Relating to IETF Documents 62 (http://trustee.ietf.org/license-info) in effect on the date of 63 publication of this document. Please review these documents 64 carefully, as they describe your rights and restrictions with respect 65 to this document. Code Components extracted from this document must 66 include Simplified BSD License text as described in Section 4.e of 67 the Trust Legal Provisions and are provided without warranty as 68 described in the Simplified BSD License. 70 Table of Contents 72 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 73 2. Node Protection with Remote-LFA . . . . . . . . . . . . . . . 3 74 2.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 4 75 2.2. Few Additional Definitions . . . . . . . . . . . . . . . 5 76 2.2.1. Link-Protecting Extended P-Space . . . . . . . . . . 6 77 2.2.2. Node-Protecting Extended P-Space . . . . . . . . . . 6 78 2.2.3. Q-Space . . . . . . . . . . . . . . . . . . . . . . . 7 79 2.2.4. Link-Protecting PQ Space . . . . . . . . . . . . . . 8 80 2.2.5. Candidate Node-Protecting PQ Space . . . . . . . . . 8 81 2.3. Computing Node-protecting R-LFA Path . . . . . . . . . . 8 82 2.3.1. Computing Candidate Node-protecting PQ-Nodes for 83 Primary nexthops . . . . . . . . . . . . . . . . . . 8 84 2.3.2. Computing node-protecting paths from PQ-nodes to 85 destinations . . . . . . . . . . . . . . . . . . . . 10 86 2.3.3. Limiting extra computational overhead . . . . . . . . 12 87 3. Manageabilty of Remote-LFA Alternate Paths . . . . . . . . . 13 88 3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 13 89 3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 14 90 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14 91 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 92 6. Security Considerations . . . . . . . . . . . . . . . . . . . 14 93 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 14 94 7.1. Normative References . . . . . . . . . . . . . . . . . . 15 95 7.2. Informative References . . . . . . . . . . . . . . . . . 15 97 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 15 99 1. Introduction 101 The Remote-LFA [I-D.ietf-rtgwg-remote-lfa] specification provides 102 loop-free alternates that gaurantees only link-protection. The 103 resulting Remote-LFA alternate nexthops (also referred to as the PQ- 104 nodes) may not provide node-protection for all destinations covered 105 by the same, in case of failure of the primary nexthop node. Neither 106 does the specification provide a means to determine the same. 108 Also, the LFA Manageability [I-D.ietf-rtgwg-lfa-manageability] 109 document, requires a computing router to find all possible (including 110 all possible Remote-LFA) alternate nexthops, collect the complete set 111 of path characteristics for each alternate path, run a alternate- 112 selection policy (configured by the operator), and find the best 113 alternate path. This will require the Remote-LFA implementation to 114 gather all the required path characteristics along each link on the 115 entire Remote-LFA alternate path. 117 With current LFA [RFC5286] and Remote-LFA implementations, the 118 forward SPF (and reverse SPF) is run on the computing router and its 119 immediate 1-hop routers as the roots. While that enables computation 120 of path attributes (e.g. SRLG, Admin-groups) for first alternate 121 path segment from the computing router to the PQ-node, there is no 122 means for the computing router to gather any path attributes for the 123 path segment from the PQ-node to destination. Consecutively any 124 policy-based selection of alternate paths will consider only the path 125 attributes from the computing router up until the PQ-node. 127 This document describes a procedure for determining node-protection 128 with Remote-LFA. The same procedure are also extended for collection 129 of complete set of path attributes, enabling more accurate policy- 130 based selection for alternate paths obtained with Remote-LFA. 132 2. Node Protection with Remote-LFA 134 Node-protection is required to provide protection of traffic on a 135 given forwarding node, against the failure of the first-hop node on 136 the primary forwarding path. Such protection becomes more critical 137 in the absence of mechanisms like non-stop-routing in the network. 138 Certain operators refrains from deploying non-stop-routing in their 139 network, due to the significant additional performance complexities 140 it comes along with. In such cases node-protection is a must to 141 gaurantee un-interrupted flow of traffic, even in the case of an 142 entire forwarding node going down. 144 The following sections discusses the node-protection problem in the 145 context of Remote-LFA and proposes a solution for solving the same. 147 2.1. The Problem 149 To better illustrate the problem and the solution proposed in this 150 document the following topology diagram from the Remote-LFA 151 [I-D.ietf-rtgwg-remote-lfa] draft is being re-used with slight 152 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 [I-D.ietf-rtgwg-remote-lfa] alternate specifications node R2 167 being the only PQ-node for the S-E link provides nexthop for all the 168 above destinations. Table 1 below, shows all possible primary and 169 Remote-LFA alternate 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. 194 D1 195 / 196 S-x-E 197 / / \ 198 N---+ R3--D2 199 \ / 200 R1---R2 202 Figure 2: Topology 2 204 In the above topology, the S-E link is no more on any of the shortest 205 paths from N to R3. Hence R3 is also included in both the Extended-P 206 space and PQ space of E (w.r.t S-E link). Table 2 below, shows all 207 possible primary and R-LFA alternate paths via PQ-node R3, for each 208 destination reachable through the S-E link in the above topology. 209 The R-LFA alternate paths via PQ-node R2 remains same as in Table 1. 211 +-------------+--------------+---------+------------------------+ 212 | Destination | Primary Path | PQ-node | Remote-LFA Backup Path | 213 +-------------+--------------+---------+------------------------+ 214 | R3 | S->E->R3 | R3 | S=>N=>E=>R3 | 215 | E | S->E | R3 | S=>N=>E=>R3->E | 216 | D1 | S->E->D1 | R3 | S=>N=>E=>R3->E->D1 | 217 | D2 | S->E->R3->D2 | R3 | S=>N=>E=>R3->D2 | 218 +-------------+--------------+---------+------------------------+ 220 Table 2: Remote-LFA backup paths via PQ-node R3 222 Again a closer look at Table 2 shows that, unlike Table 1, where the 223 single PQ-node R2 provided node-protection, for destinations R3 and 224 D1, if we choose R3 as the R-LFA nexthop, it does not provide node- 225 protection for R3 and D1 anymore. If S chooses R3 as the R-LFA 226 nexthop, in the event of the node-failure on primary nexthop E, the 227 alternate path from S to R-LFA nexthop R3 also becomes unavailable. 228 So for a Remote-LFA nexthop to provide node-protection for a given 229 destination, it is also mandatory that, the shortest path from S to 230 the chosen PQ-node MUST not traverse the primary nexthop node. 232 2.2. Few Additional Definitions 234 This document adds and enhances the following definitions extending 235 the ones mentioned in Remote-LFA [I-D.ietf-rtgwg-remote-lfa] draft. 237 2.2.1. Link-Protecting Extended P-Space 239 The Remote-LFA [I-D.ietf-rtgwg-remote-lfa] draft already defines 240 this. The link-protecting extended P-space for a link S-E being 241 protected is the set of routers that are reachable from one or more 242 direct neighbors of S, except primary node E, without traversing the 243 S-E link on any of the shortest path from the direct neighbor to the 244 router. This MUST exclude any direct neighbor for which there is 245 atleast one ECMP path from the direct neighbor traversing the 246 link(S-E) being protected. 248 A node Y is in link-protecting extended P-space w.r.t to the link 249 (S-E) being protected, if and only if, there exists atleast one 250 direct neighbor of S, Ni, other than primary nexthop E, that 251 satisfies the following condition. 253 D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y) 255 Where, 256 D_opt(A,B) : Distance on most optimum path from A to B. 257 Ni : A direct neighbor of S other than primary 258 nexthop E. 259 Y : The node being evaluated for link-protecting 260 extended P-Space. 262 Figure 3: Link-Protecting Ext-P-Space Condition 264 2.2.2. Node-Protecting Extended P-Space 266 The node-protecting extended P-space for a primary nexthop node E 267 being protected, is the set of routers that are reachable from one or 268 more direct neighbors of S, except primary node E, without traversing 269 the node E. This MUST exclude any direct neighbors for which there 270 is atleast one ECMP path from the direct neighbor traversing the node 271 E being protected. 273 A node Y is in node-protecting extended P-space w.r.t to the node E 274 being protected, if and only if, there exists atleast one direct 275 neighbor of S, Ni, other than primary nexthop E, that satisfies the 276 following condition. 278 D_opt(Ni,Y) < D_opt(Ni,E) + D_opt(E,Y) 280 Where, 281 D_opt(A,B) : Distance on most optimum path from A to B. 282 E : The primary nexthop on shortest path from S 283 to destination. 284 Ni : A direct neighbor of S other than primary 285 nexthop E. 286 Y : The node being evaluated for node-protecting 287 extended P-Space. 289 Figure 4: Node-Protecting Ext-P-Space Condition 291 It must be noted that a node Y satisfying the condition in Figure 4 292 above only guarantees that the R-LFA alternate path segment from S 293 via direct neighbor Ni to the node Y is not affected in the event of 294 a node failure of E. It does not yet guarantee that the path segment 295 from node Y to the destination is also unaffected by the same failure 296 event. 298 2.2.3. Q-Space 300 The Remote-LFA [I-D.ietf-rtgwg-remote-lfa] draft already defines 301 this. The Q-space for a link S-E being protected is the set of 302 routers that can reach primary node E, without traversing the S-E 303 link on any of the shortest path from the node Y to primary nexthop 304 E. This MUST exclude any destination for which there is atleast one 305 ECMP path from the node Y to the primary nexthop E traversing the 306 link(S-E) being protected. 308 A node Y is in Q-space w.r.t to the link (S-E) being protected, if 309 and only if, the following condition is satisfied. 311 D_opt(Y,E) < D_opt(S,E) + D_opt(Y,S) 313 Where, 314 D_opt(A,B) : Distance on most optimum path from A to B. 315 E : The primary nexthop on shortest path from S 316 to destination. 317 Y : The node being evaluated for Q-Space. 319 Figure 5: Q-Space Condition 321 2.2.4. Link-Protecting PQ Space 323 A node Y is in link-protecting PQ space w.r.t to the link (S-E) being 324 protected, if and only if, Y is present in both link-protecting 325 extended P-space and the Q-space for the link being protected. 327 2.2.5. Candidate Node-Protecting PQ Space 329 A node Y is in candidate node-protecting PQ space w.r.t to the node 330 (E) being protected, if and only if, Y is present in both node- 331 protecting extended P-space and the Q-space for the link being 332 protected. 334 Again it must be noted that a node Y being in candidate node- 335 protecting PQ-space does not guarantee that the R-LFA alternate path 336 via the same, in entirety, is unaffected in the event of a node 337 failure of primary nexthop node E. It only guarantees that the path 338 segment from S to PQ-node Y is unaffected by the same failure event. 339 The PQ-nodes in the candidate node-protecting PQ space may provide 340 node protection for only a subset of destinations that are reachable 341 through the corresponding primary link. 343 2.3. Computing Node-protecting R-LFA Path 345 The R-LFA alternate path through a given PQ-node to a given 346 destination comprises of two path segments as follows. 348 1. Path segment from the computing router to the PQ-node (Remote-LFA 349 alternate nexthop), and 351 2. Path segment from the PQ-node to the destination being protected. 353 So to ensure a R-LFA alternate path for a given destination provides 354 node-protection we need to ensure that none of the above path 355 segments are unaffected in the event of failure of the primary 356 nexthop node. Sections Section 2.3.1 and Section 2.3.2 shows how 357 this can be ensured. 359 2.3.1. Computing Candidate Node-protecting PQ-Nodes for Primary 360 nexthops 362 To choose a node-protecting R-LFA nexthop for a destination R3, 363 router S needs to consider a PQ-node from the candidate node- 364 protecting PQ-space for the primary nexthop E on shortest path from S 365 to R3. As mentioned in Section 2.2.2, to consider a PQ-node as 366 candidate node-protecting PQ-node, there must be atleast one direct 367 neighbor Ni of S, such that all shortest paths from Ni to the PQ-node 368 does not traverse primary nexthop node E. 370 Implementations should run the inequality in Section 2.2.2 Figure 4 371 for all direct neighbor, other than primary nexthop node E, to 372 determine whether a node Y is a candidate node-protecting PQ-node. 373 All of the metrics needed by this inequality would have been already 374 collected from the forward SPFs rooted at each of direct neighbor S, 375 computed as part of standard LFA [RFC5286] implementation. With 376 reference to the topology in Figure 2, Table 3 below shows how the 377 above condition can be used to determine the candidate node- 378 protecting PQ-space for S-E link (primary nexthop E) 380 +------------+----------+----------+----------+---------+-----------+ 381 | Candidate | Direct | D_opt | D_opt | D_opt | Condition | 382 | PQ-node | Nbr (Ni) | (Ni,Y) | (Ni,E) | (E,Y) | Met | 383 | (Y) | | | | | | 384 +------------+----------+----------+----------+---------+-----------+ 385 | R2 | N | 2 (N,R2) | 1 (N,E) | 2 | Yes | 386 | | | | | (E,R2) | | 387 | R3 | N | 2 (N,R3) | 1 (N,E) | 1 | No | 388 | | | | | (E,R3) | | 389 +------------+----------+----------+----------+---------+-----------+ 391 Table 3: Node-protection evaluation for R-LFA repair tunnel to PQ- 392 node 394 As seen in the above Table 3 , R3 does not meet the node-protecting 395 extended-p-space inequality And so, while R2 is in candidate node- 396 protecting PQ space, R3 is not. 398 Some SPF implementations may also produce a list of links and nodes 399 traversed on the shortest path(s) from a given root to others. In 400 such implementations, router S may have executed a forward SPF with 401 each of it's direct neighbors as the SPF root, executed as part of 402 the standard LFA [RFC5286] computations. So S may re-use the list of 403 links and nodes collected from the same SPF computations, to decide 404 whether a node Y is a candidate node-protecting PQ-node or not. A 405 node Y shall be considered as a node-protecting PQ-node, if and only 406 if, there is atleast one direct neighbor of S, other than the primary 407 nexthop E, for which, the primary nexthop node E does not exist on 408 the list of nodes traversed on any of the shortest path(s) from the 409 direct neighbor to the PQ-node. Table 4 below is an illustration of 410 the mechanism with the topology in Figure 2. 412 +-----------+-------------------+-----------------+-----------------+ 413 | Candidate | Repair Tunnel | Link-Protection | Node-Protection | 414 | PQ-node | Path(Repairing | | | 415 | | router to PQ- | | | 416 | | node) | | | 417 +-----------+-------------------+-----------------+-----------------+ 418 | R2 | S->N->R1->R2 | Yes | Yes | 419 | R2 | S->E->R3->R2 | No | No | 420 | R3 | S->N->E->R3 | Yes | No | 421 +-----------+-------------------+-----------------+-----------------+ 423 Table 4: Protection of Remote-LFA tunnel to the PQ-node 425 As seen in the above Table 4 while R2 is candidate node-protecting 426 Remote-LFA nexthop for R3 and D2, it is not so for E and D1, since 427 the primary nexthop E is in the shortest path from R2 to E and F. 429 2.3.2. Computing node-protecting paths from PQ-nodes to destinations 431 Once a computing router finds all the candidate node-protecting PQ- 432 nodes for a given directly attached primary link, it shall follow the 433 procedure in proposed in this section, to choose one or more node- 434 protecting R-LFA paths, for destinations reachable through the same 435 primary link in the primary SPF graph. 437 To find a node-protecting R-LFA path for a given destination, the 438 computing router needs to pick a subset of PQ-nodes from the 439 candidate node-protecting PQ-space for the corresponding primary 440 nexthop, such that all the path(s) from the PQ-node(s) to the given 441 destination remain unaffected in the event of a node failure of 442 primary nexthop node. To ensure this, the computing router will need 443 to ensure that, the primary nexthop node should not be on any of the 444 shortest paths from the PQ-node to the given destination. 446 This document proposes an additional forward SPF computation for each 447 of the PQ-nodes, to discover all shortest paths from the PQ-nodes to 448 the destination. The additional forward SPF computation for each PQ- 449 node, shall help determine, if a given primary nexthop node is on the 450 shortest paths from the PQ-node to the given destination or not. To 451 determine if a given candidate node-protecting PQ-node provides node- 452 protecting alternate for a given destination, the primary nexthop 453 node should not be on any of the shortest paths from the PQ-node to 454 the given destination. On running the forward SPF on a candidate 455 node-protecting PQ-node the computing router shall run the inequality 456 in Figure 6 below. PQ-nodes that does not qualify the condition for 457 a given destination, does not gaurantee node-protection for the path 458 segment from the PQ-node to the given destination. 460 D_opt(Y,D) < D_opt(Y,E) + Distance_opt(E,D) 462 Where, 463 D_opt(A,B) : Distance on most optimum path from A to B. 464 D : The destination node. 465 E : The primary nexthop on shortest path from S 466 to destination. 467 Y : The node-protecting PQ-node being evaluated 469 Figure 6: Node-Protecting Condition for PQ-node to Destination 471 All of the above metric costs except D_opt(Y, D), can be obtained 472 with forward and reverse SPFs with E(the primary nexthop) as the 473 root, run as part of the regular LFA and Remote-LFA implementation. 474 The Distance_opt(Y, D) metric can only be determined by the 475 additional forward SPF run with PQ-node Y as the root. With 476 reference to the topology in Figure 2, Table 5 below shows how the 477 above condition can be used to determine node-protection with node- 478 protecting PQ-node R2. 480 +-------------+------------+---------+--------+---------+-----------+ 481 | Destination | Primary-NH | D_opt | D_opt | D_opt | Condition | 482 | (D) | (E) | (Y, D) | (Y, E) | (E, D) | Met | 483 +-------------+------------+---------+--------+---------+-----------+ 484 | R3 | E | 1 | 2 | 1 | Yes | 485 | | | (R2,R3) | (R2,E) | (E,R3) | | 486 | E | E | 2 | 2 | 0 (E,E) | No | 487 | | | (R2,E) | (R2,E) | | | 488 | D1 | E | 3 | 2 | 1 | No | 489 | | | (R2,D1) | (R2,E) | (E,D1) | | 490 | D2 | E | 2 | 2 | 1 | Yes | 491 | | | (R2,D2) | (R2,E) | (E,D2) | | 492 +-------------+------------+---------+--------+---------+-----------+ 494 Table 5: Node-protection evaluation for R-LFA path segment between 495 PQ-node and destination 497 As seen in the above example above, R2 does not meet the node- 498 protecting inequality for destination E, and F. And so, once again, 499 while R2 is a node-protecting Remote-LFA nexthop for R3 and G, it is 500 not so for E and F. 502 In SPF implementations that also produce a list of links and nodes 503 traversed on the shortest path(s) from a given root to others, to 504 determine whether a PQ-node provides node-protection for a given 505 destination or not, the list of nodes computed from forward SPF run 506 on the PQ-node, for the given destination, should be inspected. In 507 case the list contains the primary nexthop node, the PQ-node does not 508 provide node-protection. Else, the PQ-node guarantees node- 509 protecting alternate for the given destination. Below is an 510 illustration of the mechanism with candidate node-protecting PQ-node 511 R2 in the topology in Figure 2. 513 +-------------+-----------------+-----------------+-----------------+ 514 | Destination | Shortest Path | Link-Protection | Node-Protection | 515 | | (Repairing | | | 516 | | router to PQ- | | | 517 | | node) | | | 518 +-------------+-----------------+-----------------+-----------------+ 519 | R3 | R2->R3 | Yes | Yes | 520 | E | R2->R3->E | Yes | No | 521 | D1 | R2->R3->E->D1 | Yes | No | 522 | D2 | R2->R3->D2 | Yes | Yes | 523 +-------------+-----------------+-----------------+-----------------+ 525 Table 6: Protection of Remote-LFA path between PQ-node and 526 destination 528 As seen in the above example while R2 is candidate node-protecting 529 R-LFA nexthop for R3 and G, it is not so for E and F, since the 530 primary nexthop E is in the shortest path from R2 to E and F. 532 The procedure described in this document helps no more than to 533 determine whether a given Remote-LFA alternate provides node- 534 protection for a given destination or not. It does not find out any 535 new Remote-LFA alternate nexthops, outside the ones already computed 536 by standard Remote-LFA procedure. However, in case of availability 537 of more than one PQ-node (Remote-LFA alternates) for a destination, 538 and node-protection is required for the given primary nexthop, this 539 procedure will eliminate the PQ-nodes that do not provide node- 540 protection and choose only the ones that does. 542 2.3.3. Limiting extra computational overhead 544 In addition to the extra reverse SPF computation, one per directly 545 connected neighbor, suggested by the Remote-LFA 546 [I-D.ietf-rtgwg-remote-lfa] draft, this document proposes a forward 547 SPF per PQ-node discovered in the network. Since the average number 548 of PQ-nodes found in any network is considerably more than the number 549 of direct neighbors of the computing router, the proposal of running 550 one forward SPF per PQ-node may add considerably to the overall SPF 551 computation time. 553 To limit the computational overhead of the approach proposed, this 554 document proposes that implementations MUST choose a subset from the 555 entire set of PQ-nodes computed in the network, with a finite limit 556 on the number of PQ-nodes in the subset. Implementations MUST choose 557 a default value for this limit and may provide user with a 558 configuration knob to override the default limit. Implementations 559 MUST also evaluate some default preference criteria while considering 560 a PQ-node in this subset. Finally, implementations MAY also allow 561 user to override the default preference criteria, by providing a 562 policy configuration for the same. 564 This document proposes that implementations SHOULD use a default 565 preference criteria for PQ-node selection which will put a score on 566 each PQ-node, proportional to the number of primary interfaces for 567 which it provides coverage, its distance from the computing router, 568 and its router-id (or system-id in case of IS-IS). PQ-nodes that 569 cover more primary interfaces SHOULD be preferred over PQ-nodes that 570 cover fewer primary interfaces. When two or more PQ-nodes cover the 571 same number of primary interfaces, PQ-nodes which are closer (based 572 on metric) to the computing router SHOULD be preferred over PQ-nodes 573 farther away from it. For PQ-nodes that cover the same number of 574 primary interfaces and are the same distance from the the computing 575 router, the PQ-node with smaller router-id (or system-id in case of 576 IS-IS) SHOULD be preferred. 578 Once a subset of PQ-nodes is found, computing router shall run a 579 forward SPF on each of the PQ-nodes in the subset to continue with 580 procedures proposed in section Section 2.3.2. 582 3. Manageabilty of Remote-LFA Alternate Paths 584 3.1. The Problem 586 With the regular Remote-LFA [I-D.ietf-rtgwg-remote-lfa] functionality 587 the computing router may compute more than one PQ-node as usable 588 Remote-LFA alternate nexthops. Additionally an alternate selection 589 policy may be configured to enable the network operator to choose one 590 of them as the most appropriate Remote-LFA alternate. For such 591 policy-based alternate selection to run, all the relevant path 592 characteristics for each the alternate paths (one through each of the 593 PQ-nodes), needs to be collected. As mentioned befor in section 594 Section 2.3 the R-LFA alternate path through a given PQ-node to a 595 given destination comprises of two path segments. 597 The first path segment (i.e. from the computing router to the PQ- 598 node) can be calculated from the regular forward SPF done as part of 599 standard and remote LFA computations. However without the mechanism 600 proposed in section Section 2.3.2 of this document, there is no way 601 to determine the path characteristics for the second path segment 602 (i.e from the PQ-node to the destination). In the absence of the 603 path characteristics for the second path segment, two Remote-LFA 604 alternate path may be equally preferred based on the first path 605 segments characteristics only, although the second path segment 606 attributes may be different. 608 3.2. The Solution 610 The additional forward SPF computation proposed in section 611 Section 2.3.2 document shall also collect links, nodes and path 612 characteristics along the second path segment. This shall enable 613 collection of complete path characteristics for a given Remote-LFA 614 alternate path to a given destination. The complete alternate path 615 characteristics shall then facilitate more accurate alternate path 616 selection while running the alternate selection policy. 618 Like specified in Section 2.3.3 to limit the computational overhead 619 of the approach proposed, forward SPF computations MUST be run on a 620 selected subset from the entire set of PQ-nodes computed in the 621 network, with a finite limit on the number of PQ-nodes in the subset. 622 The detailed suggestion on how to select this subset is specified in 623 the same section. While this limits the number of possible alternate 624 paths provided to the alternate-selection policy, this is needed keep 625 the computational complexity within affordable limits. However if 626 the alternate-selection policy is very restrictive this may leave few 627 destinations in the entire toplogy without protection. Yet this 628 limitation provides a necessary tradeoff between extensive coverage 629 and immense computational overhead. 631 4. Acknowledgements 633 Many thanks to Bruno Decraene for providing his useful comments. We 634 would also like to thank Uma Chunduri for reviewing this document and 635 providing valuable feedback. 637 5. IANA Considerations 639 N/A. - No protocol changes are proposed in this document. 641 6. Security Considerations 643 This document does not introduce any change in any of the protocol 644 specifications. It simply proposes to run an extra SPF rooted on 645 each PQ-node discovered in the whole network. 647 7. References 648 7.1. Normative References 650 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 651 Requirement Levels", BCP 14, RFC 2119, March 1997. 653 7.2. Informative References 655 [I-D.ietf-rtgwg-lfa-manageability] 656 Litkowski, S., Decraene, B., Filsfils, C., Raza, K., 657 Horneffer, M., and p. psarkar@juniper.net, "Operational 658 management of Loop Free Alternates", draft-ietf-rtgwg-lfa- 659 manageability-03 (work in progress), February 2014. 661 [I-D.ietf-rtgwg-remote-lfa] 662 Bryant, S., Filsfils, C., Previdi, S., Shand, M., and S. 663 Ning, "Remote LFA FRR", draft-ietf-rtgwg-remote-lfa-06 664 (work in progress), May 2014. 666 [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast 667 Reroute: Loop-Free Alternates", RFC 5286, September 2008. 669 Authors' Addresses 671 Pushpasis Sarkar (editor) 672 Juniper Networks, Inc. 673 Electra, Exora Business Park 674 Bangalore, KA 560103 675 India 677 Email: psarkar@juniper.net 679 Hannes Gredler 680 Juniper Networks, Inc. 681 1194 N. Mathilda Ave. 682 Sunnyvale, CA 94089 683 US 685 Email: hannes@juniper.net 687 Shraddha Hegde 688 Juniper Networks, Inc. 689 Electra, Exora Business Park 690 Bangalore, KA 560103 691 India 693 Email: shraddha@juniper.net 694 Chris Bowers 695 Juniper Networks, Inc. 696 1194 N. Mathilda Ave. 697 Sunnyvale, CA 94089 698 US 700 Email: cbowers@juniper.net 702 Stephane Litkowski 703 Orange 705 Email: stephane.litkowski@orange.com 707 Harish Raghuveer 709 Email: harish.r.prabhu@gmail.com