idnits 2.17.1 draft-ietf-rtgwg-remote-lfa-03.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 -- The document date (November 04, 2013) is 3826 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-00 == Outdated reference: A later version (-05) exists of draft-psarkar-rtgwg-rlfa-node-protection-01 Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group S. Bryant 3 Internet-Draft C. Filsfils 4 Intended status: Standards Track S. Previdi 5 Expires: May 08, 2014 Cisco Systems 6 M. Shand 7 Independent Contributor 8 N. So 9 Tata Communications 10 November 04, 2013 12 Remote LFA FRR 13 draft-ietf-rtgwg-remote-lfa-03 15 Abstract 17 This draft describes an extension to the basic IP fast re-route 18 mechanism described in RFC5286 that provides additional backup 19 connectivity for link failures when none can be provided by the basic 20 mechanisms. 22 Requirements Language 24 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 25 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 26 document are to be interpreted as described in RFC2119 [RFC2119]. 28 Status of This Memo 30 This Internet-Draft is submitted in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF). Note that other groups may also distribute 35 working documents as Internet-Drafts. The list of current Internet- 36 Drafts is at http://datatracker.ietf.org/drafts/current/. 38 Internet-Drafts are draft documents valid for a maximum of six months 39 and may be updated, replaced, or obsoleted by other documents at any 40 time. It is inappropriate to use Internet-Drafts as reference 41 material or to cite them other than as "work in progress." 43 This Internet-Draft will expire on May 08, 2014. 45 Copyright Notice 47 Copyright (c) 2013 IETF Trust and the persons identified as the 48 document authors. All rights reserved. 50 This document is subject to BCP 78 and the IETF Trust's Legal 51 Provisions Relating to IETF Documents 52 (http://trustee.ietf.org/license-info) in effect on the date of 53 publication of this document. Please review these documents 54 carefully, as they describe your rights and restrictions with respect 55 to this document. Code Components extracted from this document must 56 include Simplified BSD License text as described in Section 4.e of 57 the Trust Legal Provisions and are provided without warranty as 58 described in the Simplified BSD License. 60 Table of Contents 62 1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 2 63 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 64 3. Repair Paths . . . . . . . . . . . . . . . . . . . . . . . . 5 65 3.1. Tunnels as Repair Paths . . . . . . . . . . . . . . . . . 5 66 3.2. Tunnel Requirements . . . . . . . . . . . . . . . . . . . 5 67 4. Construction of Repair Paths . . . . . . . . . . . . . . . . 6 68 4.1. Identifying Required Tunneled Repair Paths . . . . . . . 6 69 4.2. Determining Tunnel End Points . . . . . . . . . . . . . . 6 70 4.2.1. Computing Repair Paths . . . . . . . . . . . . . . . 7 71 4.2.2. Extended P-space . . . . . . . . . . . . . . . . . . 8 72 4.2.3. Selecting Repair Paths . . . . . . . . . . . . . . . 9 73 4.3. A Cost Based RLFA Algorithm . . . . . . . . . . . . . . . 9 74 5. Example Application of Remote LFAs . . . . . . . . . . . . . 13 75 6. Node Failures . . . . . . . . . . . . . . . . . . . . . . . . 14 76 7. Operation in an LDP environment . . . . . . . . . . . . . . . 15 77 8. Analysis of Real World Topologies . . . . . . . . . . . . . . 16 78 8.1. Topology Details . . . . . . . . . . . . . . . . . . . . 16 79 8.2. LFA only . . . . . . . . . . . . . . . . . . . . . . . . 17 80 8.3. RLFA . . . . . . . . . . . . . . . . . . . . . . . . . . 18 81 8.4. Comparison of LFA an RLFA results . . . . . . . . . . . . 19 82 9. Management Considerations . . . . . . . . . . . . . . . . . . 20 83 10. Historical Note . . . . . . . . . . . . . . . . . . . . . . . 20 84 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 85 12. Security Considerations . . . . . . . . . . . . . . . . . . . 21 86 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 21 87 14. Informative References . . . . . . . . . . . . . . . . . . . 21 88 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 23 90 1. Terminology 92 This draft uses the terms defined in [RFC5714]. This section defines 93 additional terms used in this draft. 95 Extended P-space 96 The union of the P-space of the neighbours of a 97 specific router with respect to the protected link 98 (see Section 4.2.2). 100 P-space P-space is the set of routers reachable from a 101 specific router without any path (including equal cost 102 path splits) transiting the protected link. 104 For example, the P-space of S, is the set of routers 105 that S can reach without using the protected link S-E. 107 PQ node A node which is a member of both the (extended) 108 P-space and the Q-space. In remote LFA this is used 109 as the repair tunnel endpoint. 111 Q-space Q-space is the set of routers from which a specific 112 router can be reached without any path (including 113 equal cost path splits) transiting the protected link. 115 Repair tunnel A tunnel established for the purpose of providing a 116 virtual neighbor which is a Loop Free Alternate. 118 Remote LFA The use of a PQ node rather than a neighbour of the 119 repairing node as the next hop in an LFA repair. 121 In this document we use the notation X-Y to mean the path from X to Y 122 over the link directly connecting X and Y, whilst the notation X->Y 123 refers to the shortest path from X to Y via some set of unspecified 124 nodes including the null set (i.e. including over a link directly 125 connecting X and Y). 127 2. Introduction 129 RFC 5714 [RFC5714] describes a framework for IP Fast Re-route and 130 provides a summary of various proposed IPFRR solutions. A basic 131 mechanism using loop-free alternates (LFAs) is described in [RFC5286] 132 that provides good repair coverage in many topologies[RFC6571], 133 especially those that are highly meshed. However, some topologies, 134 notably ring based topologies are not well protected by LFAs alone. 135 This is illustrated in Figure 1 below. 137 S---E 138 / \ 139 A D 140 \ / 141 B---C 143 Figure 1: A simple ring topology 145 If all link costs are equal, the link S-E cannot be fully protected 146 by LFAs. The destination C is an ECMP from S, and so can be 147 protected when S-E fails, but D and E are not protectable using LFAs 149 This draft describes extensions to the basic repair mechanism in 150 which tunnels are used to provide additional logical links which can 151 then be used as loop free alternates where none exist in the original 152 topology. For example if a tunnel is provided between S and C as 153 shown in Figure 2 then C, now being a direct neighbor of S would 154 become an LFA for D and E. The non-failure traffic distribution is 155 not disrupted by the provision of such a tunnel since it is only used 156 for repair traffic and MUST NOT be used for normal traffic. 158 S---E 159 / \ \ 160 A \ D 161 \ \ / 162 B---C 164 Figure 2: The addition of a tunnel 166 The use of this technique is not restricted to ring based topologies, 167 but is a general mechanism which can be used to enhance the 168 protection provided by LFAs. A study of the protection achieved 169 using remote LFA in typical service provider core networks is 170 provided in Section 8, and a side by side comparison between LFA and 171 remote LFA is provided in Section 8.4. 173 Remote LFA is suitable for incremental deployment within a network, 174 including a network that is already deploying LFA. Computation of 175 the repair path is relatively simple, and takes place exclusively on 176 the repairing node. In MPLS networks the targeted LDP protocol 177 needed to learn the label binding at the repair tunnel endpoint is a 178 well understood and widely deployed technology. 180 This technique describes in this document is directed at providing 181 repairs in the case of link failures. Considerations regarding node 182 failures are discussed in Section 6. 184 3. Repair Paths 186 As with LFA FRR, when a router detects an adjacent link failure, it 187 uses one or more repair paths in place of the failed link. Repair 188 paths are pre-computed in anticipation of later failures so they can 189 be promptly activated when a failure is detected. 191 A tunneled repair path tunnels traffic to some staging point in the 192 network from which it is assumed that, in the absence of multiple 193 failures, it will travel to its destination using normal forwarding 194 without looping back. This is equivalent to providing a virtual 195 loop-free alternate to supplement the physical loop-free alternates. 196 Hence the name "Remote LFA FRR". In its simplest form, when a link 197 cannot be entirely protected with local LFA neighbors, the protecting 198 router seeks the help of a remote LFA staging point. Network 199 manageability considerations may lead to a repair strategy that uses 200 a remote LFA more frequently [I-D.ietf-rtgwg-lfa-manageability]. 202 3.1. Tunnels as Repair Paths 204 Consider an arbitrary protected link S-E. In LFA FRR, if a path to 205 the destination from a neighbor N of S does not cause a packet to 206 loop back over the link S-E (i.e. N is a loop-free alternate), then S 207 can send the packet to N and the packet will be delivered to the 208 destination using the pre-failure forwarding information. If there 209 is no such LFA neighbor, then S may be able to create a virtual LFA 210 by using a tunnel to carry the packet to a point in the network which 211 is not a direct neighbor of S from which the packet will be delivered 212 to the destination without looping back to S. In this document such a 213 tunnel is termed a repair tunnel. The tail-end of this tunnel (the 214 repair tunnel endpoint) is a "PQ node" and the repair mechanism is a 215 "remote LFA". 217 Note that the repair tunnel terminates at some intermediate router 218 between S and E, and not E itself. This is clearly the case, since 219 if it were possible to construct a tunnel from S to E then a 220 conventional LFA would have been sufficient to effect the repair. 222 3.2. Tunnel Requirements 224 There are a number of IP in IP tunnel mechanisms that may be used to 225 fulfil the requirements of this design, such as IP-in-IP [RFC1853] 226 and GRE[RFC1701] . 228 In an MPLS enabled network using LDP[RFC5036], a simple label 229 stack[RFC3032] may be used to provide the required repair tunnel. In 230 this case the outer label is S's neighbor's label for the repair 231 tunnel end point, and the inner label is the repair tunnel end 232 point's label for the packet destination. In order for S to obtain 233 the correct inner label it is necessary to establish a directed LDP 234 session[RFC5036] to the tunnel end point. 236 The selection of the specific tunnelling mechanism (and any necessary 237 enhancements) used to provide a repair path is outside the scope of 238 this document. The deployment in an MPLS/LDP environment is 239 relatively simple in the dataplane as an LDP LSP from S to the repair 240 tunnel endpoint (the selected PQ node) is readily available, and 241 hence does not require any new protocol extension or design change. 242 This LSP is automatically established as a basic property of LDP 243 behavior. The performance of the encapsulation and decapsulation is 244 efficient as encapsulation is just a push of one label (like 245 conventional MPLS TE FRR) and the decapsulation occurs naturally at 246 the penultimate hop before the repair tunnel endpoint. In the 247 control plane, a targeted LDP (TLDP) session is needed between the 248 repairing node and the repair tunnel endpoint, which will need to be 249 established and the labels processed before the tunnel can be used. 250 The time to establish the TLDP session and acquire labels will limit 251 the speed at which a new tunnel can be put into service, but this 252 will not be a problem in normal operation. 254 When a failure is detected, it is necessary to immediately redirect 255 traffic to the repair path. Consequently, the repair tunnel used 256 must be provisioned beforehand in anticipation of the failure. Since 257 the location of the repair tunnels is dynamically determined it is 258 necessary to automatically establish the repair tunnels. Multiple 259 repairs may share a tunnel end point 261 4. Construction of Repair Paths 263 4.1. Identifying Required Tunneled Repair Paths 265 Not all links will require protection using a tunneled repair path. 266 Referring to Figure 1, if E can already be protected via an LFA, S-E 267 does not need to be protected using a repair tunnel, since all 268 destinations normally reachable through E must therefore also be 269 protectable by an LFA. Such an LFA is frequently termed a "link 270 LFA". Tunneled repair paths are only required for links which do not 271 have a link LFA. 273 It should be noted that using the Q-space of E as a proxy for the 274 Q-space of each destination can result in failing to identify valid 275 remote LFAs. The extent to which this reduces the effective 276 protection coverage is topology dependent. 278 4.2. Determining Tunnel End Points 279 The repair tunnel endpoint needs to be a node in the network 280 reachable from S without traversing S-E. In addition, the repair 281 tunnel end point needs to be a node from which packets will normally 282 flow towards their destination without being attracted back to the 283 failed link S-E. 285 Note that once released from the tunnel, the packet will be 286 forwarded, as normal, on the shortest path from the release point to 287 its destination. This may result in the packet traversing the router 288 E at the far end of the protected link S-E., but this is obviously 289 not required. 291 The properties that are required of repair tunnel end points are 292 therefore: 294 o The repair tunneled point MUST be reachable from the tunnel source 295 without traversing the failed link; and 297 o When released, tunneled packets MUST proceed towards their 298 destination without being attracted back over the failed link. 300 Provided both these requirements are met, packets forwarded over the 301 repair tunnel will reach their destination and will not loop. 303 In some topologies it will not be possible to find a repair tunnel 304 endpoint that exhibits both the required properties. For example if 305 the ring topology illustrated in Figure 1 had a cost of 4 for the 306 link B-C, while the remaining links were cost 1, then it would not be 307 possible to establish a tunnel from S to C (without resorting to some 308 form of source routing). 310 4.2.1. Computing Repair Paths 312 The set of routers which can be reached from S without traversing S-E 313 is termed the P-space of S with respect to the link S-E. The P-space 314 can be obtained by computing a shortest path tree (SPT) rooted at S 315 and excising the sub-tree reached via the link S-E (including those 316 which are members of an ECMP). In the case of Figure 1 the P-space 317 comprises nodes A and B only. Expressed in cost terms the set of 318 routers {P} are those for which the shortest path cost S->P is 319 strictly less than the shortest path cost S->E->P. 321 The set of routers from which the node E can be reached, by normal 322 forwarding, without traversing the link S-E is termed the Q-space of 323 E with respect to the link S-E. The Q-space can be obtained by 324 computing a reverse shortest path tree (rSPT) rooted at E, with the 325 sub-tree which traverses the failed link excised (including those 326 which are members of an ECMP). The rSPT uses the cost towards the 327 root rather than from it and yields the best paths towards the root 328 from other nodes in the network. In the case of Figure 1 the Q-space 329 comprises nodes C and D only. Expressed in cost terms the set of 330 routers {Q} are those for which the shortest path cost Q->E is 331 strictly less than the shortest path cost Q->S->E. In Figure 1 the 332 intersection of the E's Q-space with S's P-space defines the set of 333 viable repair tunnel end-points, known as "PQ nodes". As can be 334 seen, for the case of Figure 1 there is no common node and hence no 335 viable repair tunnel end-point. 337 Note that the Q-space calculation could be conducted for each 338 individual destination and a per-destination repair tunnel end point 339 determined. However this would, in the worst case, require an SPF 340 computation per destination which is not currently considered to be 341 scalable. We therefore use the Q-space of E as a proxy for the 342 Q-space of each destination. This approximation is obviously correct 343 since the repair is only used for the set of destinations which were, 344 prior to the failure, routed through node E. This is analogous to the 345 use of link-LFAs rather than per-prefix LFAs. 347 4.2.2. Extended P-space 349 The description in Section 4.2.1 calculated router S's P-space rooted 350 at S itself. However, since router S will only use a repair path 351 when it has detected the failure of the link S-E, the initial hop of 352 the repair path need not be subject to S's normal forwarding decision 353 process. Thus we introduce the concept of extended P-space. Router 354 S's extended P-space is the union of the P-spaces of each of S's 355 neighbours (N). This may be calculated by computing an SPT at each 356 of S's neighbors (excluding E) and excising the subtree reached via 357 the path N->S->E. The use of extended P-space may allow router S to 358 reach potential repair tunnel end points that were otherwise 359 unreachable. In cost terms a router (P) is in extended P-space if 360 the shortest path cost N->P is strictly less than the shortest path 361 cost N->S->E->P. In other words, once the packet it forced to N by S, 362 it is lower cost for it to continue on to P by any path except one 363 that takes it back to S and then across the S->E link. 365 Another way to describe extended P-space is that it is the union of ( 366 un-extended ) P-space and the set of destinations for which S has a 367 per-prefix LFA protecting the link S-E. i.e. the repair tunnel end 368 point can be reached either directly or using a per-prefix LFA. 370 Since in the case of Figure 1 node A is a per-prefix LFA for the 371 destination node C, the set of extended P-space nodes comprises nodes 372 A, B and C. Since node C is also in E's Q-space, there is now a node 373 common to both extended P-space and Q-space which can be used as a 374 repair tunnel end-point to protect the link S-E. 376 4.2.3. Selecting Repair Paths 378 The mechanisms described above will identify all the possible repair 379 tunnel end points that can be used to protect a particular link. In 380 a well-connected network there are likely to be multiple possible 381 release points for each protected link. All will deliver the packets 382 correctly so, arguably, it does not matter which is chosen. However, 383 one repair tunnel end point may be preferred over the others on the 384 basis of path cost or some other selection criteria. 386 There is no technical requirement for the selection criteria to be 387 consistent across all routers, but such consistency may be desirable 388 from an operational point of view. In general there are advantages 389 in choosing the repair tunnel end point closest (shortest metric) to 390 S. Choosing the closest maximises the opportunity for the traffic to 391 be load balanced once it has been released from the tunnel. For 392 consistency in behavior, is RECOMMENDED that member of the set of 393 routers {PQ} with the lowest cost S->P be the default choice for P. 394 In the event of a tie the router with the lowest node identifier 395 SHOULD be selected. 397 4.3. A Cost Based RLFA Algorithm 399 The preceding text has mostly described the computation of the remote 400 LFA repair target (PQ) in terms of the intersection of two 401 reachability graphs computed using SPFs. This section describes a 402 method of computing the remote LFA repair target using a cost based 403 algorithm. The pseudo-code provides in this section avoids 404 unnecessary SPF computations, but for the sake of readability, it 405 does not otherwise try to optimize the code. Unconventionally, but 406 for clarity, we provide the main algorithm followed its procedures. 407 In this description D_opt(a,b) is the shortest distance from node a 408 to node b as computed by the SPF. 410 ////////////////////////////////////////////////////////////////// 411 // 412 // Main Function 414 ////////////////////////////////////////////////////////////////// 415 // 416 // We have already computed the forward SPF from self to all nodes 417 // y in network and thus we know D_opt (self, y). This is needed 418 // for normal forwarding. 419 // However for completeness. 421 Compute_and_Store_Forward_SPF(self) 422 // To extend P-space we compute the SPF at each neighbour except 423 // the neighbour that is reached via the link being protected. 424 // We will also need D_opt(fail_intf.remote_node,y) so compute 425 // that at the same time. 427 Compute_Neighbor_SPFs() 429 // Compute the set of nodes {P} reachable other than via the 430 // failed link 432 Compute_Extended_P_Space(fail_intf) 434 // Compute the set of nodes that can reach the node on the far 435 // side of the failed link without traversing the failed link. 437 Compute_Q_Space(fail_intf) 439 // Compute the set of candidate RLFA tunnel endpoints 441 Intersect_Extended_P_and_Q_Space() 443 // Make sure that we cannot get looping repairs when the 444 // failure is worse than expected. 446 if (guarantee_no_looping_on_worse_than_protected_failure) 447 Apply_Downstream_Constraint() 449 // 450 // End of Main Function 451 // 452 ////////////////////////////////////////////////////////////////// 453 ////////////////////////////////////////////////////////////////// 454 // 455 // Proceedures 456 // 458 ///////////////////////////////////////////////////////////////// 459 // 460 // This computes the SPF from root, and stores the optimum 461 // distance from root to each node y 463 Compute_and_Store_Forward_SPF(root) 464 Compute_Forward_SPF(root) 465 foreach node y in network 466 store D_opt(root,y) 468 ///////////////////////////////////////////////////////////////// 469 // 470 // This computes the optimum distance from each neighbour (other 471 // than the neighbour reachable through the failed link) and 472 // every other node in the network 474 Compute_Neighbor_SPFs() 475 foreach interface intf in self 476 Compute_and_Store_Forward_SPF(intf.remote_node) 478 ///////////////////////////////////////////////////////////////// 479 // 480 // The reverse SPF computes the cost from each remote node to 481 // root. This is achieved by running the normal SPF algorithm, 482 // but using the link cost in the direction from the next hop 483 // back towards root in place of the link cost in the direction 484 // away from root towards the next hop. 486 Compute_and_Store_Reverse_SPF(root) 487 Compute_Reverse_SPF(root) 488 foreach node y in network 489 store D_opt(y,root) 491 ///////////////////////////////////////////////////////////////// 492 // 493 // Calculate P space and then extend it by the P-spaces of each 494 // neighbour other than the one reachable via the link being 495 // protected. Note the strictly less than operator is needed to 496 // avoid ECMP issues. 498 Compute_Extended_P_Space(fail_intf) 499 foreach node y in network 500 y.in_extended_P_space = false 501 // Extend P-space to the P-spaces of all reachable 502 // neighbours 503 foreach interface intf in self 504 if (intf.remote_node != fail_intf.remote_node) 505 if ( D_opt(intf.remote_node, y) < 506 D_opt(intf.remote_node, self) + 507 D_opt(self,fail_intf.remote_node) + 508 D_opt(fail_intf.remote_node,y) ) 509 y.in_extended_P_space = true 511 ///////////////////////////////////////////////////////////////// 512 // 514 Compute_Q_Space(fail_intf) 515 // Compute the cost from every node the network to the 516 // node normally reachable across the failed link 517 Compute_and_Store_Reverse_SPF(fail_intf.remote_node) 519 // Compute the cost from every node the network to self 520 Compute_and_Store_Reverse_SPF(self) 522 foreach node y in network 523 if ( D_opt(y,fail_intf.remote_node) < D_opt(y,self) + 524 D_opt(self,fail_intf.remote_node) ) 525 y.in_Q_space = true 526 else 527 y.in_Q_space = false 529 ///////////////////////////////////////////////////////////////// 530 // 531 // Compute set of nodes in both extended P-space and in Q-space 533 Intersect_Extended_P_and_Q_Space() 534 foreach node y in network 535 if ( y.in_extended_P_space && y.in_Q_space ) 536 y.valid_tunnel_endpoint = true 537 else 538 y.valid_tunnel_endpoint = false 540 ///////////////////////////////////////////////////////////////// 541 // 542 // A downstream route is one where the next hop is strictly 543 // closer to the destination. By sending the packet to a 544 // PQ node that is downstream, we know that if the PQ node 545 // detects a failure, it will not loop the packet back to self. 546 // This is useful when there are two failures, or a node has 547 // failed rather than a link. 549 Apply_Downstream_Constraint() 550 foreach node y in network 551 if (y.valid_tunnel_endpoint) 552 Compute_and_Store_Forward_SPF(y) 553 if ((D_opt(y,dest) < D_opt(self,dest)) 554 y.valid_tunnel_endpoint = true 555 else 556 y.valid_tunnel_endpoint = false 558 // 559 ///////////////////////////////////////////////////////////////// 561 5. Example Application of Remote LFAs 563 An example of a commonly deployed topology which is not fully 564 protected by LFAs alone is shown in Figure 3. PE1 and PE2 are 565 connected in the same site. P1 and P2 may be geographically 566 separated (inter-site). In order to guarantee the lowest latency 567 path from/to all other remote PEs, normally the shortest path follows 568 the geographical distance of the site locations. Therefore, to 569 ensure this, a lower IGP metric (5) is assigned between PE1 and PE2. 570 A high metric (1000) is set on the P-PE links to prevent the PEs 571 being used for transit traffic. The PEs are not individually dual- 572 homed in order to reduce costs. 574 This is a common topology in SP networks. 576 When a failure occurs on the link between PE1 and P2, PE1 does not 577 have an LFA for traffic reachable via P1. Similarly, by symmetry, if 578 the link between PE2 and P1 fails, PE2 does not have an LFA for 579 traffic reachable via P2. 581 Increasing the metric between PE1 and PE2 to allow the LFA would 582 impact the normal traffic performance by potentially increasing the 583 latency. 585 | 100 | 586 -P2---------P1- 587 \ / 588 1000 \ / 1000 589 PE1---PE2 590 5 592 Figure 3: Example SP topology 594 Clearly, full protection can be provided, using the techniques 595 described in this draft, by PE1 choosing P1 as the remote LFA repair 596 target node, and PE2 choosing P2 as the remote LFA repair target. 598 6. Node Failures 600 When the failure is a node failure rather than a link failure there 601 is a danger that the RLFA repair will loop. This is discussed in 602 detail in [I-D.bryant-ipfrr-tunnels]. In summary problem is that two 603 of more of E's neighbors each with E as the next hop to some 604 destination D may attempt to repair a packet addressed to destination 605 D via the other neighbor and then E, thus causing a loop to form. As 606 will be noted from [I-D.bryant-ipfrr-tunnels], this can rapidly 607 become a complex problem to address. 609 There are a number of ways to minimize the probability of a loop 610 forming when a node failure occurs and there exists the possibility 611 that two of E's neighbors may form a mutual repair. 613 1. Detect when a packet has arrived on some interface I that is also 614 the interface used to reach the first hop on the RLFA path to the 615 remote LFA repair target, and drop the packet. This is useful in 616 the case of a ring topology. 618 2. Require that the path from the remote LFA repair target to 619 destination D never passes through E (including in the ECMP 620 case), i.e. only use node protecting paths in which the cost from 621 the remote LFA repair target to D is strictly less than the cost 622 from the remote LFA repair target to E plus the cost E to D. 624 3. Require that where the packet may pass through another neighbor 625 of E, that node is down stream (i.e. strictly closer to D than 626 the repairing node). This means that some neighbor of E (X) can 627 repair via some other neighbor of E (Y), but Y cannot repair via 628 X. 630 Case 1 accepts that loops may form and suppresses them by dropping 631 packets. Dropping packets may be considered less detrimental than 632 looping packets. This approach may also lead to dropping some 633 legitimate packets. Cases 2 and 3 above prevent the formation of a 634 loop, but at the expense of a reduced repair coverage and at the cost 635 of additional complexity in the algorithm to compute the repair path. 637 The probability of a node failure and the consequences of node 638 failure in any particular topology will depend on the node design, 639 the particular topology in use, and node failure strategy (including 640 the null strategy). It is recommended that a network operator 641 perform an analysis of the consequences and probability of node 642 failure in their network, and determine whether the incidence and 643 consequence of occurrence are acceptable. 645 This topic is further discussed in 646 [I-D.psarkar-rtgwg-rlfa-node-protection]. 648 7. Operation in an LDP environment 650 Where this technique is used in an MPLS network using LDP [RFC5036], 651 and S is a transit node, S will need to swap the top label in the 652 stack for rthe emote LFA repair target's (PQ's) label to the 653 destination, and to then push its own label for the remote LFA repair 654 target. 656 In the example Section 2 S already has the first hop (A) label for 657 the remote LFA repair target (C) as a result of the ordinary 658 operation of LDP. To get the remote LFA repair target's label (C's 659 label) for the destination (D), S needs to establish a targeted LDP 660 session with C. The label stack for normal operation and RLFA 661 operation is shown below in Figure 4. 663 +-----------------+ +-----------------+ +-----------------+ 664 | datalink | | datalink | | datalink | 665 +-----------------+ +-----------------+ +-----------------+ 666 | S's label for D | | E's label for D | | A's label for C | 667 +-----------------+ +-----------------+ +-----------------+ 668 | Payload | | Payload | | C's label for D | 669 +-----------------+ +-----------------+ +-----------------+ 670 X Y | Payload | 671 +-----------------+ 672 Z 674 X = Normal label stack packet arriving at S 675 Y = Normal label stack packet leaving S 676 Z = RLFA label stack to D via C as the remote LFA repair target. 678 Figure 4 680 To establish an targeted LDP session with a candidate remote LFA 681 repair target node the repairing node (S) needs to know what IP 682 address that the remote LFA repair target is willing to use for 683 targeted LDP sessions. Ideally this is provided by the remote LFA 684 repair target advertising this address in the IGP in use. Which 685 address is used, how this is advertised in the IGP, and whether this 686 is a special IP address or an IP address also used for some other 687 purpose is out of scope for this document and must be specified in an 688 IGP specific RFC. 690 In the absence of a protocol to learn the preferred IP address for 691 targeted LDP, a tie-breaking mechanism is required. Unless otherwise 692 configured, an LSR should attempt a targeted LDP session with the 693 local IP address with the lowest numerical value advertised by the 694 target LSR. To determine the lowest numerical value the address is 695 taken in network byte order and cast to an integer of appropriate 696 size. 698 No protection is available until the TLDP session has been 699 established and a label for the destination has been learned from the 700 remote LFA repair target. If for any reason the TLDP session cannot 701 not be established, an implementation SHOULD advise the operator 702 about the protection setup issue using any well known mechanism such 703 as syslog or SNMP. 705 8. Analysis of Real World Topologies 707 This section gives the results of analysing a number of real world 708 service provider topologies collected between October 2012 and the 709 date of this draft. 711 8.1. Topology Details 713 The figure below characterises each topology (topo) studied in terms 714 of : 716 o The number of nodes (# nodes) excluding pseudonodes. 718 o The number of bidirectional links ( # links) including parallel 719 links and links to and from pseudonodes. 721 o The number of node pairs that are connected by one or more links 722 (# pairs). 724 o The number of node pairs that are connected by more than one (i.e. 725 parallel) link ( # para). 727 o The number of links (excluding pseudonode links, which are by 728 definition asymmetric) that have asymmetric metrics (#asym). 730 +------+---------+---------+---------+--------+--------+ 731 | topo | # nodes | # links | # pairs | # para | # asym | 732 +------+---------+---------+---------+--------+--------+ 733 | 1 | 315 | 570 | 560 | 10 | 3 | 734 | 2 | 158 | 373 | 312 | 33 | 0 | 735 | 3 | 655 | 1768 | 1314 | 275 | 1195 | 736 | 4 | 1281 | 2326 | 2248 | 70 | 10 | 737 | 5 | 364 | 811 | 659 | 80 | 86 | 738 | 6 | 114 | 318 | 197 | 101 | 4 | 739 | 7 | 55 | 237 | 159 | 67 | 2 | 740 | 8 | 779 | 1848 | 1441 | 199 | 437 | 741 | 9 | 263 | 482 | 413 | 41 | 12 | 742 | 10 | 86 | 375 | 145 | 64 | 22 | 743 | 11 | 162 | 1083 | 351 | 201 | 49 | 744 | 12 | 380 | 1174 | 763 | 231 | 0 | 745 | 13 | 1051 | 2087 | 2037 | 48 | 64 | 746 | 14 | 92 | 291 | 204 | 64 | 2 | 747 +------+---------+---------+---------+--------+--------+ 749 8.2. LFA only 751 The figure below shows the percentage of protected destinations (% 752 prot) and percentage of guaranteed node protected destinations ( % 753 gtd N) for the set of topologies characterized in Section 8.1 754 achieved using only LFA repairs. 756 +------+--------+---------+ 757 | topo | % prot | % gtd N | 758 +------+--------+---------+ 759 | 1 | 78.5 | 36.9 | 760 | 2 | 97.3 | 52.4 | 761 | 3 | 99.3 | 58 | 762 | 4 | 83.1 | 63.1 | 763 | 5 | 99 | 59.1 | 764 | 6 | 86.4 | 21.4 | 765 | 7 | 93.9 | 35.4 | 766 | 8 | 95.3 | 48.1 | 767 | 9 | 82.2 | 49.5 | 768 | 10 | 98.5 | 14.9 | 769 | 11 | 99.6 | 24.8 | 770 | 12 | 99.5 | 62.4 | 771 | 13 | 92.4 | 51.6 | 772 | 14 | 99.3 | 48.6 | 773 +------+--------+---------+ 775 8.3. RLFA 777 The figure below shows the percentage of protected destinations (% 778 prot) and % guaranteed node protected destinations ( % gtd N) for 779 RLFA protection in the topologies studies. In addition, it show the 780 percentage of destinations using an RLFA repair (% PQ) together with 781 the total number of unidirectional RLFA targeted LDP session 782 established (# PQ), the number of PQ sessions which would be required 783 for complete protection, but which could not be established (no PQ). 784 It also shows the 50 (p50), 90 (p90) and 100 (p100) percentiles for 785 the number of individual LDP sessions terminating at an individual 786 node (whether used for TX, RX or both). 788 For example, if there were LDP sessions required A->B, A->C, C->A, 789 C->D, these would be counted as 2, 1, 2, 1 at nodes A,B,C and D 790 respectively because:- 792 A has two sessions (to nodes B and C) 794 B has one session (to node A) 796 C has two sessions (to nodes A and D) 798 D has one session (to node D) 800 In this study, remote LFA is only used when necessary. i.e. when 801 there is at least one destination which is not reparable by a per 802 destination LFA, and a single remote LFA tunnel is used (if 803 available) to repair traffic to all such destinations. The remote 804 LFA repair target points are computed using extended P space and 805 choosing the PQ node which has the lowest metric cost from the 806 repairing node. 808 +------+--------+--------+------+------+-------+-----+-----+------+ 809 | topo | % prot |% gtd N | % PQ | # PQ | no PQ | p50 | p90 | p100 | 810 +------+--------+--------+------+------+-------+-----+-----+------+ 811 | 1 | 99.7 | 53.3 | 21.2 | 295 | 3 | 1 | 5 | 14 | 812 | 2 | 97.5 | 52.4 | 0.2 | 7 | 40 | 0 | 0 | 2 | 813 | 3 | 99.999 | 58.4 | 0.7 | 63 | 5 | 0 | 1 | 5 | 814 | 4 | 99 | 74.8 | 16 | 1424 | 54 | 1 | 3 | 23 | 815 | 5 | 99.5 | 59.5 | 0.5 | 151 | 7 | 0 | 2 | 7 | 816 | 6 | 100 | 34.9 | 13.6 | 63 | 0 | 1 | 2 | 6 | 817 | 7 | 99.999 | 40.6 | 6.1 | 16 | 2 | 0 | 2 | 4 | 818 | 8 | 99.5 | 50.2 | 4.3 | 350 | 39 | 0 | 2 | 15 | 819 | 9 | 99.5 | 55 | 17.3 | 428 | 5 | 1 | 2 | 67 | 820 | 10 | 99.6 | 14.1 | 1 | 49 | 7 | 1 | 2 | 5 | 821 | 11 | 99.9 | 24.9 | 0.3 | 85 | 1 | 0 | 2 | 8 | 822 | 12 | 99.999 | 62.8 | 0.5 | 512 | 4 | 0 | 0 | 3 | 823 | 13 | 97.5 | 54.6 | 5.1 | 1188 | 95 | 0 | 2 | 27 | 824 | 14 | 100 | 48.6 | 0.7 | 79 | 0 | 0 | 2 | 4 | 825 +------+--------+--------+------+------+-------+-----+-----+------+ 827 Another study[ISOCORE2010] confirms the significant coverage increase 828 provided by Remote LFAs. 830 8.4. Comparison of LFA an RLFA results 832 The table below provides a side by side comparison the LFA and the 833 remote LFA results. This shows a significant improvement in the 834 percentage of protected destinations and normally a modest 835 improvement in the percentage of guaranteed node protected 836 destinations. 838 +------+--------+--------+---------+---------+ 839 | topo | LFA | RLFA | LFA | RLFA | 840 | | % prot | %prot | % gtd N | % gtd N | 841 +------+--------+--------+---------+---------+ 842 | 1 | 78.5 | 99.7 | 36.9 | 53.3 | 843 | 2 | 97.3 | 97.5 | 52.4 | 52.4 | 844 | 3 | 99.3 | 99.999 | 58 | 58.4 | 845 | 4 | 83.1 | 99 | 63.1 | 74.8 | 846 | 5 | 99 | 99.5 | 59.1 | 59.5 | 847 | 6 | 86.4 |100 | 21.4 | 34.9 | 848 | 7 | 93.9 | 99.999 | 35.4 | 40.6 | 849 | 8 | 95.3 | 99.5 | 48.1 | 50.2 | 850 | 9 | 82.2 | 99.5 | 49.5 | 55 | 851 | 10 | 98.5 | 99.6 | 14.9 | 14.1 | 852 | 11 | 99.6 | 99.9 | 24.8 | 24.9 | 853 | 12 | 99.5 | 99.999 | 62.4 | 62.8 | 854 | 13 | 92.4 | 97.5 | 51.6 | 54.6 | 855 | 14 | 99.3 |100 | 48.6 | 48.6 | 856 +------+--------+--------+---------+---------+ 858 As shown in the table, remote LFA provides close to 100% prefix 859 protection against link failure in 11 of the 14 topologies studied, 860 and provides a significant improvement in two of the remaining three 861 cases. In an MPLS network, this is achieved without any saleability 862 impact, as the tunnels to the PQ nodes are always present as a 863 property of an LDP-based deployment. In the very few cases where P 864 and Q spaces have an empty intersection, one could select the closest 865 node in the Q space and signal an explicitly-routed RSVP TE LSP to 866 that Q node. A directed LDP session is then established with the 867 selected Q node and the rest of the solution is identical to that 868 described elsewhere in this document. Alternatively the segment 869 routing technology being defined in the IETF may be used to carry the 870 traffic between non-collocated P and Q nodes 871 [I-D.filsfils-rtgwg-segment-routing-use-cases], 872 [I-D.filsfils-rtgwg-segment-routing], 873 [I-D.gredler-rtgwg-igp-label-advertisement]. 875 9. Management Considerations 877 The management of LFA and remote LFA is the subject of ongoing work 878 withing the IETF[I-D.ietf-rtgwg-lfa-manageability] to which the 879 reader is referred. Management considerations may lead to a 880 preference for the use of a remote LFA over an avalaible LFA. This 881 preference is a matter for the network operator, and not a matter of 882 protocol correctness. 884 10. Historical Note 886 The basic concepts behind Remote LFA were invented in 2002 and were 887 later included in [I-D.bryant-ipfrr-tunnels], submitted in 2004. 889 [I-D.bryant-ipfrr-tunnels], targeted a 100% protection coverage and 890 hence included additional mechanisms on top of the Remote LFA 891 concept. The addition of these mechanisms made the proposal very 892 complex and computationally intensive and it was therefore not 893 pursued as a working group item. 895 As explained in [RFC6571], the purpose of the LFA FRR technology is 896 not to provide coverage at any cost. A solution for this already 897 exists with MPLS TE FRR. MPLS TE FRR is a mature technology which is 898 able to provide protection in any topology thanks to the explicit 899 routing capability of MPLS TE. 901 The purpose of LFA FRR technology is to provide for a simple FRR 902 solution when such a solution is possible. The first step along this 903 simplicity approach was "local" LFA [RFC5286]. We propose "Remote 904 LFA" as a natural second step. The following section motivates its 905 benefits in terms of simplicity, incremental deployment and 906 significant coverage increase. 908 11. IANA Considerations 910 There are no IANA considerations that arise from this architectural 911 description of IPFRR. The RFC Editor may remove this section on 912 publication. 914 12. Security Considerations 916 The security considerations of RFC 5286 also apply. 918 To prevent their use as an attack vector the repair tunnel endpoints 919 SHOULD be assigned from a set of addresses that are not reachable 920 from outside the routing domain. 922 13. Acknowledgments 924 The authors wish to thank Levente Csikor and Chris Bowers for their 925 contribution to the cost based algorithm text. We thank Stephane 926 Litkowski for his review of this work. 928 14. Informative References 930 [I-D.bryant-ipfrr-tunnels] 931 Bryant, S., Filsfils, C., Previdi, S., and M. Shand, "IP 932 Fast Reroute using tunnels", draft-bryant-ipfrr-tunnels-03 933 (work in progress), November 2007. 935 [I-D.filsfils-rtgwg-segment-routing-use-cases] 936 Filsfils, C., Francois, P., Previdi, S., Decraene, B., 937 Litkowski, S., Horneffer, M., Milojevic, I., Shakir, R., 938 Ytti, S., Henderickx, W., Tantsura, J., Kini, S., and E. 939 Crabbe, "Segment Routing Use Cases", draft-filsfils-rtgwg- 940 segment-routing-use-cases-02 (work in progress), October 941 2013. 943 [I-D.filsfils-rtgwg-segment-routing] 944 Filsfils, C., Previdi, S., Bashandy, A., Decraene, B., 945 Litkowski, S., Horneffer, M., Milojevic, I., Shakir, R., 946 Ytti, S., Henderickx, W., Tantsura, J., and E. Crabbe, 947 "Segment Routing Architecture", draft-filsfils-rtgwg- 948 segment-routing-01 (work in progress), October 2013. 950 [I-D.gredler-rtgwg-igp-label-advertisement] 951 Gredler, H., Amante, S., Scholl, T., and L. Jalil, 952 "Advertising MPLS labels in IGPs", draft-gredler-rtgwg- 953 igp-label-advertisement-05 (work in progress), May 2013. 955 [I-D.ietf-rtgwg-lfa-manageability] 956 Litkowski, S., Decraene, B., Filsfils, C., and K. Raza, 957 "Operational management of Loop Free Alternates", draft- 958 ietf-rtgwg-lfa-manageability-00 (work in progress), May 959 2013. 961 [I-D.psarkar-rtgwg-rlfa-node-protection] 962 psarkar@juniper.net, p., Gredler, H., Hegde, S., and H. 963 Raghuveer, "Node Protecting R-LFA and Manageability", 964 draft-psarkar-rtgwg-rlfa-node-protection-01 (work in 965 progress), July 2013. 967 [ISOCORE2010] 968 So, N., Lin, T., and C. Chen, "LFA (Loop Free Alternates) 969 Case Studies in Verizon's LDP Network", 2010. 971 [RFC1701] Hanks, S., Li, T., Farinacci, D., and P. Traina, "Generic 972 Routing Encapsulation (GRE)", RFC 1701, October 1994. 974 [RFC1853] Simpson, W., "IP in IP Tunneling", RFC 1853, October 1995. 976 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 977 Requirement Levels", BCP 14, RFC 2119, March 1997. 979 [RFC3032] Rosen, E., Tappan, D., Fedorkow, G., Rekhter, Y., 980 Farinacci, D., Li, T., and A. Conta, "MPLS Label Stack 981 Encoding", RFC 3032, January 2001. 983 [RFC5036] Andersson, L., Minei, I., and B. Thomas, "LDP 984 Specification", RFC 5036, October 2007. 986 [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast 987 Reroute: Loop-Free Alternates", RFC 5286, September 2008. 989 [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC 990 5714, January 2010. 992 [RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., 993 Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free 994 Alternate (LFA) Applicability in Service Provider (SP) 995 Networks", RFC 6571, June 2012. 997 Authors' Addresses 999 Stewart Bryant 1000 Cisco Systems 1001 250, Longwater, Green Park, 1002 Reading RG2 6GB, UK 1003 UK 1005 Email: stbryant@cisco.com 1007 Clarence Filsfils 1008 Cisco Systems 1009 De Kleetlaan 6a 1010 1831 Diegem 1011 Belgium 1013 Email: cfilsfil@cisco.com 1015 Stefano Previdi 1016 Cisco Systems 1018 Email: sprevidi@cisco.com 1020 Mike Shand 1021 Independent Contributor 1023 Email: imc.shand@gmail.com 1025 Ning So 1026 Tata Communications 1027 Mobile Broadband Services 1029 Email: Ning.So@tatacommunications.com