idnits 2.17.1 draft-ietf-rtgwg-remote-lfa-04.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 22, 2013) is 3801 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-02 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 26, 2014 Cisco Systems 6 M. Shand 7 Independent Contributor 8 N. So 9 Tata Communications 10 November 22, 2013 12 Remote LFA FRR 13 draft-ietf-rtgwg-remote-lfa-04 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 26, 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. Selecting Repair Paths . . . . . . . . . . . . . . . 9 72 4.3. A Cost Based RLFA Algorithm . . . . . . . . . . . . . . . 10 73 5. Example Application of Remote LFAs . . . . . . . . . . . . . 14 74 6. Node Failures . . . . . . . . . . . . . . . . . . . . . . . . 15 75 7. Operation in an LDP environment . . . . . . . . . . . . . . . 16 76 8. Analysis of Real World Topologies . . . . . . . . . . . . . . 17 77 8.1. Topology Details . . . . . . . . . . . . . . . . . . . . 17 78 8.2. LFA only . . . . . . . . . . . . . . . . . . . . . . . . 18 79 8.3. RLFA . . . . . . . . . . . . . . . . . . . . . . . . . . 18 80 8.4. Comparison of LFA an RLFA results . . . . . . . . . . . . 20 81 9. Management Considerations . . . . . . . . . . . . . . . . . . 21 82 10. Historical Note . . . . . . . . . . . . . . . . . . . . . . . 21 83 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 84 12. Security Considerations . . . . . . . . . . . . . . . . . . . 21 85 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 22 86 14. Informative References . . . . . . . . . . . . . . . . . . . 22 87 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 24 89 1. Terminology 91 This draft uses the terms defined in [RFC5714]. This section defines 92 additional terms used in this draft. 94 Extended P-space 95 The union of the P-space of the neighbours of a 96 specific router with respect to the protected link 97 (see Section 4.2.1.2). 99 P-space P-space is the set of routers reachable from a 100 specific router without any path (including equal cost 101 path splits) transiting the protected link. 103 For example, the P-space of S, is the set of routers 104 that S can reach without using the protected link S-E. 106 PQ node A node which is a member of both the (extended) 107 P-space and the Q-space. In remote LFA this is used 108 as the repair tunnel endpoint. 110 Q-space Q-space is the set of routers from which a specific 111 router can be reached without any path (including 112 equal cost path splits) transiting the protected link. 114 Repair tunnel A tunnel established for the purpose of providing a 115 virtual neighbor which is a Loop Free Alternate. 117 Remote LFA (RLFA) The use of a PQ node rather than a neighbour of 118 the repairing node as the next hop in an LFA repair. 120 In this document we use the notation X-Y to mean the path from X to Y 121 over the link directly connecting X and Y, whilst the notation X->Y 122 refers to the shortest path from X to Y via some set of unspecified 123 nodes including the null set (i.e. including over a link directly 124 connecting X and Y). 126 2. Introduction 128 RFC 5714 [RFC5714] describes a framework for IP Fast Re-route and 129 provides a summary of various proposed IPFRR solutions. A basic 130 mechanism using loop-free alternates (LFAs) is described in [RFC5286] 131 that provides good repair coverage in many topologies[RFC6571], 132 especially those that are highly meshed. However, some topologies, 133 notably ring based topologies are not well protected by LFAs alone. 134 This is illustrated in Figure 1 below. 136 S---E 137 / \ 138 A D 139 \ / 140 B---C 142 Figure 1: A simple ring topology 144 If all link costs are equal, the link S-E cannot be fully protected 145 by LFAs. The destination C is an ECMP from S, and so can be 146 protected when S-E fails, but D and E are not protectable using LFAs 148 This draft describes extensions to the basic repair mechanism in 149 which tunnels are used to provide additional logical links which can 150 then be used as loop free alternates where none exist in the original 151 topology. For example if a tunnel is provided between S and C as 152 shown in Figure 2 then C, now being a direct neighbor of S would 153 become an LFA for D and E. The non-failure traffic distribution is 154 not disrupted by the provision of such a tunnel since it is only used 155 for repair traffic and MUST NOT be used for normal traffic. 157 S---E 158 / \ \ 159 A \ D 160 \ \ / 161 B---C 163 Figure 2: The addition of a tunnel 165 The use of this technique is not restricted to ring based topologies, 166 but is a general mechanism which can be used to enhance the 167 protection provided by LFAs. A study of the protection achieved 168 using remote LFA in typical service provider core networks is 169 provided in Section 8, and a side by side comparison between LFA and 170 remote LFA is provided in Section 8.4. 172 Remote LFA is suitable for incremental deployment within a network, 173 including a network that is already deploying LFA. Computation of 174 the repair path is relatively simple, and takes place exclusively on 175 the repairing node. In MPLS networks the targeted LDP protocol 176 needed to learn the label binding at the repair tunnel endpoint is a 177 well understood and widely deployed technology. 179 This technique describes in this document is directed at providing 180 repairs in the case of link failures. Considerations regarding node 181 failures are discussed in Section 6. 183 3. Repair Paths 185 As with LFA FRR, when a router detects an adjacent link failure, it 186 uses one or more repair paths in place of the failed link. Repair 187 paths are pre-computed in anticipation of later failures so they can 188 be promptly activated when a failure is detected. 190 A tunneled repair path tunnels traffic to some staging point in the 191 network from which it is assumed that, in the absence of multiple 192 failures, it will travel to its destination using normal forwarding 193 without looping back. This is equivalent to providing a virtual 194 loop-free alternate to supplement the physical loop-free alternates. 195 Hence the name "Remote LFA FRR". In its simplest form, when a link 196 cannot be entirely protected with local LFA neighbors, the protecting 197 router seeks the help of a remote LFA staging point. Network 198 manageability considerations may lead to a repair strategy that uses 199 a remote LFA more frequently [I-D.ietf-rtgwg-lfa-manageability].] 201 3.1. Tunnels as Repair Paths 203 Consider an arbitrary protected link S-E. In LFA FRR, if a path to 204 the destination from a neighbor N of S does not cause a packet to 205 loop back over the link S-E (i.e. N is a loop-free alternate), then S 206 can send the packet to N and the packet will be delivered to the 207 destination using the pre-failure forwarding information. If there 208 is no such LFA neighbor, then S may be able to create a virtual LFA 209 by using a tunnel to carry the packet to a point in the network which 210 is not a direct neighbor of S from which the packet will be delivered 211 to the destination without looping back to S. In this document such a 212 tunnel is termed a repair tunnel. The tail-end of this tunnel (the 213 repair tunnel endpoint) is a "PQ node" and the repair mechanism is a 214 "remote LFA". 216 Note that the repair tunnel terminates at some intermediate router 217 between S and E, and not E itself. This is clearly the case, since 218 if it were possible to construct a tunnel from S to E then a 219 conventional LFA would have been sufficient to effect the repair. 221 3.2. Tunnel Requirements 223 There are a number of IP in IP tunnel mechanisms that may be used to 224 fulfil the requirements of this design, such as IP-in-IP [RFC1853] 225 and GRE[RFC1701] . 227 In an MPLS enabled network using LDP[RFC5036], a simple label 228 stack[RFC3032] may be used to provide the required repair tunnel. In 229 this case the outer label is S's neighbor's label for the repair 230 tunnel end point, and the inner label is the repair tunnel end 231 point's label for the packet destination. In order for S to obtain 232 the correct inner label it is necessary to establish a directed LDP 233 session[RFC5036] to the tunnel end point. 235 The selection of the specific tunnelling mechanism (and any necessary 236 enhancements) used to provide a repair path is outside the scope of 237 this document. The deployment in an MPLS/LDP environment is 238 relatively simple in the data plane as an LDP LSP from S to the 239 repair tunnel endpoint (the selected PQ node) is readily available, 240 and hence does not require any new protocol extension or design 241 change. This LSP is automatically established as a basic property of 242 LDP behavior. The performance of the encapsulation and decapsulation 243 is efficient as encapsulation is just a push of one label (like 244 conventional MPLS TE FRR) and the decapsulation occurs naturally at 245 the penultimate hop before the repair tunnel endpoint. In the 246 control plane, a targeted LDP (TLDP) session is needed between the 247 repairing node and the repair tunnel endpoint, which will need to be 248 established and the labels processed before the tunnel can be used. 249 The time to establish the TLDP session and acquire labels will limit 250 the speed at which a new tunnel can be put into service, but this 251 will not be a problem in normal operation. 253 When a failure is detected, it is necessary to immediately redirect 254 traffic to the repair path. Consequently, the repair tunnel used 255 must be provisioned beforehand in anticipation of the failure. Since 256 the location of the repair tunnels is dynamically determined it is 257 necessary to automatically establish the repair tunnels. Multiple 258 repairs may share a tunnel end point 260 4. Construction of Repair Paths 262 4.1. Identifying Required Tunneled Repair Paths 264 Not all links will require protection using a tunneled repair path. 265 Referring to Figure 1, if E can already be protected via an LFA, S-E 266 does not need to be protected using a repair tunnel, since all 267 destinations normally reachable through E must therefore also be 268 protectable by an LFA. Such an LFA is frequently termed a "link 269 LFA". Tunneled repair paths are only required for links which do not 270 have a link LFA. 272 It should be noted that using the Q-space of E as a proxy for the 273 Q-space of each destination can result in failing to identify valid 274 remote LFAs. The extent to which this reduces the effective 275 protection coverage is topology dependent. 277 4.2. Determining Tunnel End Points 278 The repair tunnel endpoint needs to be a node in the network 279 reachable from S without traversing S-E. In addition, the repair 280 tunnel end point needs to be a node from which packets will normally 281 flow towards their destination without being attracted back to the 282 failed link S-E. 284 Note that once released from the tunnel, the packet will be 285 forwarded, as normal, on the shortest path from the release point to 286 its destination. This may result in the packet traversing the router 287 E at the far end of the protected link S-E., but this is obviously 288 not required. 290 The properties that are required of repair tunnel end points are 291 therefore: 293 o The repair tunneled point MUST be reachable from the tunnel source 294 without traversing the failed link; and 296 o When released, tunneled packets MUST proceed towards their 297 destination without being attracted back over the failed link. 299 Provided both these requirements are met, packets forwarded over the 300 repair tunnel will reach their destination and will not loop. 302 In some topologies it will not be possible to find a repair tunnel 303 endpoint that exhibits both the required properties. For example if 304 the ring topology illustrated in Figure 1 had a cost of 4 for the 305 link B-C, while the remaining links were cost 1, then it would not be 306 possible to establish a tunnel from S to C (without resorting to some 307 form of source routing). 309 4.2.1. Computing Repair Paths 311 To compute the repair path for link S-E we need to determine the set 312 of routers which can be reached from S without traversing S-E, and 313 match this with the set of routers from which the node E can be 314 reached, by normal forwarding, without traversing the link S-E. 316 We will proceed as follows: we will describe how to compute the set 317 of routers which can be reached from S without traversing S-E. We 318 call this the S's P-space with respect to the failure of link S-E. We 319 will then note that S is able to use P-Space of its neighbours since 320 S can determine which neighbour it will use as the next hop for the 321 repair. We call this the S's Extended P-Space with respect to the 322 failure of link S-E. The use of extended P-Space allows greater 323 repair coverage and is the preferred approach. Finally we will show 324 how to compute the set of routers from which the node E can be 325 reached, by normal forwarding, without traversing the link S-E. This 326 is called the Q-space of E with respect to the link S-E. The 327 selection of the preferred node from the set of nodes that an in both 328 Extended P-Space and Q-Space is described in Section 4.2.2. 330 A suitable cost based algorithm to compute the set of nodes common to 331 both extended P-space and Q-space is provide in Section 4.3. 333 4.2.1.1. P-space 335 The set of routers which can be reached from S without traversing S-E 336 is termed the P-space of S with respect to the link S-E. The P-space 337 can be obtained by computing a shortest path tree (SPT) rooted at S 338 and excising the sub-tree reached via the link S-E (including those 339 which are members of an ECMP). In the case of Figure 1 the P-space 340 comprises nodes A and B only. Expressed in cost terms the set of 341 routers {P} are those for which the shortest path cost S->P is 342 strictly less than the shortest path cost S->E->P. 344 4.2.1.2. Extended P-space 346 The description in Section 4.2.1.1 calculated router S's P-space 347 rooted at S itself. However, since router S will only use a repair 348 path when it has detected the failure of the link S-E, the initial 349 hop of the repair path need not be subject to S's normal forwarding 350 decision process. Thus we introduce the concept of extended P-space. 351 Router S's extended P-space is the union of the P-spaces of each of 352 S's neighbours (N). This may be calculated by computing an SPT at 353 each of S's neighbors (excluding E) and excising the subtree reached 354 via the path N->S->E. The use of extended P-space may allow router S 355 to reach potential repair tunnel end points that were otherwise 356 unreachable. In cost terms a router (P) is in extended P-space if 357 the shortest path cost N->P is strictly less than the shortest path 358 cost N->S->E->P. In other words, once the packet it forced to N by S, 359 it is lower cost for it to continue on to P by any path except one 360 that takes it back to S and then across the S->E link. 362 Since in the case of Figure 1 node A is a per-prefix LFA for the 363 destination node C, the set of extended P-space nodes comprises nodes 364 A, B and C. Since node C is also in E's Q-space, there is now a node 365 common to both extended P-space and Q-space which can be used as a 366 repair tunnel end-point to protect the link S-E. 368 4.2.1.3. Q-space 370 The set of routers from which the node E can be reached, by normal 371 forwarding, without traversing the link S-E is termed the Q-space of 372 E with respect to the link S-E. The Q-space can be obtained by 373 computing a reverse shortest path tree (rSPT) rooted at E, with the 374 sub-tree which traverses the failed link excised (including those 375 which are members of an ECMP). The rSPT uses the cost towards the 376 root rather than from it and yields the best paths towards the root 377 from other nodes in the network. In the case of Figure 1 the Q-space 378 comprises nodes C and D only. Expressed in cost terms the set of 379 routers {Q} are those for which the shortest path cost Q->E is 380 strictly less than the shortest path cost Q->S->E. In Figure 1 the 381 intersection of the E's Q-space with S's P-space defines the set of 382 viable repair tunnel end-points, known as "PQ nodes". As can be 383 seen, for the case of Figure 1 there is no common node and hence no 384 viable repair tunnel end-point. 386 Note that the Q-space calculation could be conducted for each 387 individual destination and a per-destination repair tunnel end point 388 determined. However this would, in the worst case, require an SPF 389 computation per destination which is not currently considered to be 390 scalable. We therefore use the Q-space of E as a proxy for the 391 Q-space of each destination. This approximation is obviously correct 392 since the repair is only used for the set of destinations which were, 393 prior to the failure, routed through node E. This is analogous to the 394 use of link-LFAs rather than per-prefix LFAs. 396 4.2.2. Selecting Repair Paths 398 The mechanisms described above will identify all the possible repair 399 tunnel end points that can be used to protect a particular link. In 400 a well-connected network there are likely to be multiple possible 401 release points for each protected link. All will deliver the packets 402 correctly so, arguably, it does not matter which is chosen. However, 403 one repair tunnel end point may be preferred over the others on the 404 basis of path cost or some other selection criteria. 406 There is no technical requirement for the selection criteria to be 407 consistent across all routers, but such consistency may be desirable 408 from an operational point of view. In general there are advantages 409 in choosing the repair tunnel end point closest (shortest metric) to 410 S. Choosing the closest maximises the opportunity for the traffic to 411 be load balanced once it has been released from the tunnel. For 412 consistency in behavior, is RECOMMENDED that member of the set of 413 routers {PQ} with the lowest cost S->P be the default choice for P. 414 In the event of a tie the router with the lowest node identifier 415 SHOULD be selected. 417 It is a local matter whether the repair path selection policy used by 418 the router favours LFA repairs over RLFA repairs. An LFA repair has 419 the advantage of not requiring the use of tunnel, however network 420 manageability considerations may lead to a repair strategy that uses 421 a remote LFA more frequently [I-D.ietf-rtgwg-lfa-manageability]. 423 As described in [RFC5286], always selecting a PQ node that is 424 downstream with respect to the repairing node, prevents the formation 425 of loops when the failure is worse than expected. The use of 426 downstream nodes reduces the repair coverage, and operators are 427 advised to determine whether adequate coverage is achieved before 428 enabling this selection feature. 430 4.3. A Cost Based RLFA Algorithm 432 The preceding text has mostly described the computation of the remote 433 LFA repair target (PQ) in terms of the intersection of two 434 reachability graphs computed using SPFs. This section describes a 435 method of computing the remote LFA repair target using a cost based 436 algorithm. The pseudo-code provides in this section avoids 437 unnecessary SPF computations, but for the sake of readability, it 438 does not otherwise try to optimize the code. In this description 439 D_opt(a,b) is the shortest distance from node a to node b as computed 440 by the SPF. 442 The following notation is used: 444 o D_opt(a,b) is the shortest distance from node a to node b as 445 computed by the SPF. 447 o dest is the packet destination 449 o fail_intf is the failed interface (S-E in the example) 451 o fail_intf.remote_node is the node reachable over interface 452 fail_intf (node E in the example) 454 o intf.remote_node is the node reachable over interface intf 456 o root is the root of the SPF calculation 458 o self is the node carrying out the computation 460 o y is the node in the network under consideration 462 ////////////////////////////////////////////////////////////////// 463 // 464 // Main Function 466 ////////////////////////////////////////////////////////////////// 467 // 468 // We have already computed the forward SPF from self to all nodes 469 // y in network and thus we know D_opt (self, y). This is needed 470 // for normal forwarding. 471 // However for completeness. 473 Compute_and_Store_Forward_SPF(self) 475 // To extend P-space we compute the SPF at each neighbour except 476 // the neighbour that is reached via the link being protected. 477 // We will also need D_opt(fail_intf.remote_node,y) so compute 478 // that at the same time. 480 Compute_Neighbor_SPFs() 482 // Compute the set of nodes {P} reachable other than via the 483 // failed link 485 Compute_Extended_P_Space(fail_intf) 487 // Compute the set of nodes that can reach the node on the far 488 // side of the failed link without traversing the failed link. 490 Compute_Q_Space(fail_intf) 492 // Compute the set of candidate RLFA tunnel endpoints 494 Intersect_Extended_P_and_Q_Space() 496 // Make sure that we cannot get looping repairs when the 497 // failure is worse than expected. 499 if (guarantee_no_looping_on_worse_than_protected_failure) 500 Apply_Downstream_Constraint() 502 // 503 // End of Main Function 504 // 505 ////////////////////////////////////////////////////////////////// 507 ////////////////////////////////////////////////////////////////// 508 // 509 // Procedures 510 // 512 ///////////////////////////////////////////////////////////////// 513 // 514 // This computes the SPF from root, and stores the optimum 515 // distance from root to each node y 516 Compute_and_Store_Forward_SPF(root) 517 Compute_Forward_SPF(root) 518 foreach node y in network 519 store D_opt(root,y) 521 ///////////////////////////////////////////////////////////////// 522 // 523 // This computes the optimum distance from each neighbour (other 524 // than the neighbour reachable through the failed link) and 525 // every other node in the network 527 Compute_Neighbor_SPFs() 528 foreach interface intf in self 529 Compute_and_Store_Forward_SPF(intf.remote_node) 531 ///////////////////////////////////////////////////////////////// 532 // 533 // The reverse SPF computes the cost from each remote node to 534 // root. This is achieved by running the normal SPF algorithm, 535 // but using the link cost in the direction from the next hop 536 // back towards root in place of the link cost in the direction 537 // away from root towards the next hop. 539 Compute_and_Store_Reverse_SPF(root) 540 Compute_Reverse_SPF(root) 541 foreach node y in network 542 store D_opt(y,root) 544 ///////////////////////////////////////////////////////////////// 545 // 546 // Calculate extended P-space 547 // 548 // Note the strictly less than operator is needed to 549 // avoid ECMP issues. 551 Compute_Extended_P_Space(fail_intf) 552 foreach node y in network 553 y.in_extended_P_space = false 554 // Extend P-space to the P-spaces of all reachable 555 // neighbours 556 foreach interface intf in self 557 if (intf.remote_node != fail_intf.remote_node) 558 if ( D_opt(intf.remote_node, y) < 559 D_opt(intf.remote_node, self) + 560 D_opt(self,fail_intf.remote_node) + 561 D_opt(fail_intf.remote_node,y) ) 562 y.in_extended_P_space = true 564 ///////////////////////////////////////////////////////////////// 565 // 566 // Compute the nodes in Q-space 567 // 569 Compute_Q_Space(fail_intf) 570 // Compute the cost from every node the network to the 571 // node normally reachable across the failed link 572 Compute_and_Store_Reverse_SPF(fail_intf.remote_node) 574 // Compute the cost from every node the network to self 575 Compute_and_Store_Reverse_SPF(self) 577 foreach node y in network 578 if ( D_opt(y,fail_intf.remote_node) < D_opt(y,self) + 579 D_opt(self,fail_intf.remote_node) ) 580 y.in_Q_space = true 581 else 582 y.in_Q_space = false 584 ///////////////////////////////////////////////////////////////// 585 // 586 // Compute set of nodes in both extended P-space and in Q-space 588 Intersect_Extended_P_and_Q_Space() 589 foreach node y in network 590 if ( y.in_extended_P_space && y.in_Q_space ) 591 y.valid_tunnel_endpoint = true 592 else 593 y.valid_tunnel_endpoint = false 595 ///////////////////////////////////////////////////////////////// 596 // 597 // A downstream route is one where the next hop is strictly 598 // closer to the destination. By sending the packet to a 599 // PQ node that is downstream, we know that if the PQ node 600 // detects a failure, it will not loop the packet back to self. 601 // This is useful when there are two failures, or a node has 602 // failed rather than a link. 604 Apply_Downstream_Constraint() 605 foreach node y in network 606 if (y.valid_tunnel_endpoint) 607 Compute_and_Store_Forward_SPF(y) 608 if ((D_opt(y,dest) < D_opt(self,dest)) 609 y.valid_tunnel_endpoint = true 610 else 611 y.valid_tunnel_endpoint = false 613 // 614 ///////////////////////////////////////////////////////////////// 616 5. Example Application of Remote LFAs 618 An example of a commonly deployed topology which is not fully 619 protected by LFAs alone is shown in Figure 3. PE1 and PE2 are 620 connected in the same site. P1 and P2 may be geographically 621 separated (inter-site). In order to guarantee the lowest latency 622 path from/to all other remote PEs, normally the shortest path follows 623 the geographical distance of the site locations. Therefore, to 624 ensure this, a lower IGP metric (5) is assigned between PE1 and PE2. 625 A high metric (1000) is set on the P-PE links to prevent the PEs 626 being used for transit traffic. The PEs are not individually dual- 627 homed in order to reduce costs. 629 This is a common topology in SP networks. 631 When a failure occurs on the link between PE1 and P2, PE1 does not 632 have an LFA for traffic reachable via P1. Similarly, by symmetry, if 633 the link between PE2 and P1 fails, PE2 does not have an LFA for 634 traffic reachable via P2. 636 Increasing the metric between PE1 and PE2 to allow the LFA would 637 impact the normal traffic performance by potentially increasing the 638 latency. 640 | 100 | 641 -P2---------P1- 642 \ / 643 1000 \ / 1000 644 PE1---PE2 645 5 647 Figure 3: Example SP topology 649 Clearly, full protection can be provided, using the techniques 650 described in this draft, by PE1 choosing P1 as the remote LFA repair 651 target node, and PE2 choosing P2 as the remote LFA repair target. 653 6. Node Failures 655 When the failure is a node failure rather than a link failure there 656 is a danger that the RLFA repair will loop. This is discussed in 657 detail in [I-D.bryant-ipfrr-tunnels]. In summary problem is that two 658 of more of E's neighbors each with E as the next hop to some 659 destination D may attempt to repair a packet addressed to destination 660 D via the other neighbor and then E, thus causing a loop to form. As 661 will be noted from [I-D.bryant-ipfrr-tunnels], this can rapidly 662 become a complex problem to address. 664 There are a number of ways to minimize the probability of a loop 665 forming when a node failure occurs and there exists the possibility 666 that two of E's neighbors may form a mutual repair. 668 1. Detect when a packet has arrived on some interface I that is also 669 the interface used to reach the first hop on the RLFA path to the 670 remote LFA repair target, and drop the packet. This is useful in 671 the case of a ring topology. 673 2. Require that the path from the remote LFA repair target to 674 destination D never passes through E (including in the ECMP 675 case), i.e. only use node protecting paths in which the cost from 676 the remote LFA repair target to D is strictly less than the cost 677 from the remote LFA repair target to E plus the cost E to D. 679 3. Require that where the packet may pass through another neighbor 680 of E, that node is down stream (i.e. strictly closer to D than 681 the repairing node). This means that some neighbor of E (X) can 682 repair via some other neighbor of E (Y), but Y cannot repair via 683 X. 685 Case 1 accepts that loops may form and suppresses them by dropping 686 packets. Dropping packets may be considered less detrimental than 687 looping packets. This approach may also lead to dropping some 688 legitimate packets. Cases 2 and 3 above prevent the formation of a 689 loop, but at the expense of a reduced repair coverage and at the cost 690 of additional complexity in the algorithm to compute the repair path. 692 The probability of a node failure and the consequences of node 693 failure in any particular topology will depend on the node design, 694 the particular topology in use, and node failure strategy (including 695 the null strategy). It is recommended that a network operator 696 perform an analysis of the consequences and probability of node 697 failure in their network, and determine whether the incidence and 698 consequence of occurrence are acceptable. 700 This topic is further discussed in 701 [I-D.psarkar-rtgwg-rlfa-node-protection]. 703 7. Operation in an LDP environment 705 Where this technique is used in an MPLS network using LDP [RFC5036], 706 and S is a transit node, S will need to swap the top label in the 707 stack for the emote LFA repair target's (PQ's) label to the 708 destination, and to then push its own label for the remote LFA repair 709 target. 711 In the example Section 2 S already has the first hop (A) label for 712 the remote LFA repair target (C) as a result of the ordinary 713 operation of LDP. To get the remote LFA repair target's label (C's 714 label) for the destination (D), S needs to establish a targeted LDP 715 session with C. The label stack for normal operation and RLFA 716 operation is shown below in Figure 4. 718 +-----------------+ +-----------------+ +-----------------+ 719 | datalink | | datalink | | datalink | 720 +-----------------+ +-----------------+ +-----------------+ 721 | S's label for D | | E's label for D | | A's label for C | 722 +-----------------+ +-----------------+ +-----------------+ 723 | Payload | | Payload | | C's label for D | 724 +-----------------+ +-----------------+ +-----------------+ 725 X Y | Payload | 726 +-----------------+ 727 Z 729 X = Normal label stack packet arriving at S 730 Y = Normal label stack packet leaving S 731 Z = RLFA label stack to D via C as the remote LFA repair target. 733 Figure 4 735 To establish an targeted LDP session with a candidate remote LFA 736 repair target node the repairing node (S) needs to know what IP 737 address that the remote LFA repair target is willing to use for 738 targeted LDP sessions. Ideally this is provided by the remote LFA 739 repair target advertising this address in the IGP in use. Which 740 address is used, how this is advertised in the IGP, and whether this 741 is a special IP address or an IP address also used for some other 742 purpose is out of scope for this document and must be specified in an 743 IGP specific RFC. 745 In the absence of a protocol to learn the preferred IP address for 746 targeted LDP, an LSR should attempt a targeted LDP session with the 747 Router ID [RFC2328] [RFC5305] [RFC5340], unless it is configured 748 otherwise. 750 No protection is available until the TLDP session has been 751 established and a label for the destination has been learned from the 752 remote LFA repair target. If for any reason the TLDP session cannot 753 not be established, an implementation SHOULD advise the operator 754 about the protection setup issue using any well known mechanism such 755 as Syslog [RFC5424] or SNMP [RFC3411]. 757 8. Analysis of Real World Topologies 759 This section gives the results of analysing a number of real world 760 service provider topologies collected between October 2012 and the 761 date of this draft. 763 8.1. Topology Details 765 The figure below characterises each topology (topo) studied in terms 766 of : 768 o The number of nodes (# nodes) excluding pseudonodes. 770 o The number of bidirectional links ( # links) including parallel 771 links and links to and from pseudonodes. 773 o The number of node pairs that are connected by one or more links 774 (# pairs). 776 o The number of node pairs that are connected by more than one (i.e. 777 parallel) link ( # para). 779 o The number of links (excluding pseudonode links, which are by 780 definition asymmetric) that have asymmetric metrics (#asym). 782 +------+---------+---------+---------+--------+--------+ 783 | topo | # nodes | # links | # pairs | # para | # asym | 784 +------+---------+---------+---------+--------+--------+ 785 | 1 | 315 | 570 | 560 | 10 | 3 | 786 | 2 | 158 | 373 | 312 | 33 | 0 | 787 | 3 | 655 | 1768 | 1314 | 275 | 1195 | 788 | 4 | 1281 | 2326 | 2248 | 70 | 10 | 789 | 5 | 364 | 811 | 659 | 80 | 86 | 790 | 6 | 114 | 318 | 197 | 101 | 4 | 791 | 7 | 55 | 237 | 159 | 67 | 2 | 792 | 8 | 779 | 1848 | 1441 | 199 | 437 | 793 | 9 | 263 | 482 | 413 | 41 | 12 | 794 | 10 | 86 | 375 | 145 | 64 | 22 | 795 | 11 | 162 | 1083 | 351 | 201 | 49 | 796 | 12 | 380 | 1174 | 763 | 231 | 0 | 797 | 13 | 1051 | 2087 | 2037 | 48 | 64 | 798 | 14 | 92 | 291 | 204 | 64 | 2 | 799 +------+---------+---------+---------+--------+--------+ 801 8.2. LFA only 803 The figure below shows the percentage of protected destinations (% 804 prot) and percentage of guaranteed node protected destinations ( % 805 gtd N) for the set of topologies characterized in Section 8.1 806 achieved using only LFA repairs. 808 +------+--------+---------+ 809 | topo | % prot | % gtd N | 810 +------+--------+---------+ 811 | 1 | 78.5 | 36.9 | 812 | 2 | 97.3 | 52.4 | 813 | 3 | 99.3 | 58 | 814 | 4 | 83.1 | 63.1 | 815 | 5 | 99 | 59.1 | 816 | 6 | 86.4 | 21.4 | 817 | 7 | 93.9 | 35.4 | 818 | 8 | 95.3 | 48.1 | 819 | 9 | 82.2 | 49.5 | 820 | 10 | 98.5 | 14.9 | 821 | 11 | 99.6 | 24.8 | 822 | 12 | 99.5 | 62.4 | 823 | 13 | 92.4 | 51.6 | 824 | 14 | 99.3 | 48.6 | 825 +------+--------+---------+ 827 8.3. RLFA 828 The figure below shows the percentage of protected destinations (% 829 prot) and % guaranteed node protected destinations ( % gtd N) for 830 RLFA protection in the topologies studies. In addition, it show the 831 percentage of destinations using an RLFA repair (% PQ) together with 832 the total number of unidirectional RLFA targeted LDP session 833 established (# PQ), the number of PQ sessions which would be required 834 for complete protection, but which could not be established (no PQ). 835 It also shows the 50 (p50), 90 (p90) and 100 (p100) percentiles for 836 the number of individual LDP sessions terminating at an individual 837 node (whether used for TX, RX or both). 839 For example, if there were LDP sessions required A->B, A->C, C->A, 840 C->D, these would be counted as 2, 1, 2, 1 at nodes A,B,C and D 841 respectively because:- 843 A has two sessions (to nodes B and C) 845 B has one session (to node A) 847 C has two sessions (to nodes A and D) 849 D has one session (to node D) 851 In this study, remote LFA is only used when necessary. i.e. when 852 there is at least one destination which is not reparable by a per 853 destination LFA, and a single remote LFA tunnel is used (if 854 available) to repair traffic to all such destinations. The remote 855 LFA repair target points are computed using extended P space and 856 choosing the PQ node which has the lowest metric cost from the 857 repairing node. 859 +------+--------+--------+------+------+-------+-----+-----+------+ 860 | topo | % prot |% gtd N | % PQ | # PQ | no PQ | p50 | p90 | p100 | 861 +------+--------+--------+------+------+-------+-----+-----+------+ 862 | 1 | 99.7 | 53.3 | 21.2 | 295 | 3 | 1 | 5 | 14 | 863 | 2 | 97.5 | 52.4 | 0.2 | 7 | 40 | 0 | 0 | 2 | 864 | 3 | 99.999 | 58.4 | 0.7 | 63 | 5 | 0 | 1 | 5 | 865 | 4 | 99 | 74.8 | 16 | 1424 | 54 | 1 | 3 | 23 | 866 | 5 | 99.5 | 59.5 | 0.5 | 151 | 7 | 0 | 2 | 7 | 867 | 6 | 100 | 34.9 | 13.6 | 63 | 0 | 1 | 2 | 6 | 868 | 7 | 99.999 | 40.6 | 6.1 | 16 | 2 | 0 | 2 | 4 | 869 | 8 | 99.5 | 50.2 | 4.3 | 350 | 39 | 0 | 2 | 15 | 870 | 9 | 99.5 | 55 | 17.3 | 428 | 5 | 1 | 2 | 67 | 871 | 10 | 99.6 | 14.1 | 1 | 49 | 7 | 1 | 2 | 5 | 872 | 11 | 99.9 | 24.9 | 0.3 | 85 | 1 | 0 | 2 | 8 | 873 | 12 | 99.999 | 62.8 | 0.5 | 512 | 4 | 0 | 0 | 3 | 874 | 13 | 97.5 | 54.6 | 5.1 | 1188 | 95 | 0 | 2 | 27 | 875 | 14 | 100 | 48.6 | 0.7 | 79 | 0 | 0 | 2 | 4 | 876 +------+--------+--------+------+------+-------+-----+-----+------+ 878 Another study[ISOCORE2010] confirms the significant coverage increase 879 provided by Remote LFAs. 881 8.4. Comparison of LFA an RLFA results 883 The table below provides a side by side comparison the LFA and the 884 remote LFA results. This shows a significant improvement in the 885 percentage of protected destinations and normally a modest 886 improvement in the percentage of guaranteed node protected 887 destinations. 889 +------+--------+--------+---------+---------+ 890 | topo | LFA | RLFA | LFA | RLFA | 891 | | % prot | %prot | % gtd N | % gtd N | 892 +------+--------+--------+---------+---------+ 893 | 1 | 78.5 | 99.7 | 36.9 | 53.3 | 894 | 2 | 97.3 | 97.5 | 52.4 | 52.4 | 895 | 3 | 99.3 | 99.999 | 58 | 58.4 | 896 | 4 | 83.1 | 99 | 63.1 | 74.8 | 897 | 5 | 99 | 99.5 | 59.1 | 59.5 | 898 | 6 | 86.4 |100 | 21.4 | 34.9 | 899 | 7 | 93.9 | 99.999 | 35.4 | 40.6 | 900 | 8 | 95.3 | 99.5 | 48.1 | 50.2 | 901 | 9 | 82.2 | 99.5 | 49.5 | 55 | 902 | 10 | 98.5 | 99.6 | 14.9 | 14.1 | 903 | 11 | 99.6 | 99.9 | 24.8 | 24.9 | 904 | 12 | 99.5 | 99.999 | 62.4 | 62.8 | 905 | 13 | 92.4 | 97.5 | 51.6 | 54.6 | 906 | 14 | 99.3 |100 | 48.6 | 48.6 | 907 +------+--------+--------+---------+---------+ 909 As shown in the table, remote LFA provides close to 100% prefix 910 protection against link failure in 11 of the 14 topologies studied, 911 and provides a significant improvement in two of the remaining three 912 cases. In an MPLS network, this is achieved without any saleability 913 impact, as the tunnels to the PQ nodes are always present as a 914 property of an LDP-based deployment. In the very few cases where P 915 and Q spaces have an empty intersection, one could select the closest 916 node in the Q space and signal an explicitly-routed RSVP TE LSP to 917 that Q node. A directed LDP session is then established with the 918 selected Q node and the rest of the solution is identical to that 919 described elsewhere in this document. Alternatively the segment 920 routing technology being defined in the IETF may be used to carry the 921 traffic between non-collocated P and Q nodes 922 [I-D.filsfils-rtgwg-segment-routing-use-cases], 923 [I-D.filsfils-rtgwg-segment-routing], 924 [I-D.gredler-rtgwg-igp-label-advertisement]. 926 9. Management Considerations 928 The management of LFA and remote LFA is the subject of ongoing work 929 withing the IETF[I-D.ietf-rtgwg-lfa-manageability] to which the 930 reader is referred. Management considerations may lead to a 931 preference for the use of a remote LFA over an available LFA. This 932 preference is a matter for the network operator, and not a matter of 933 protocol correctness. 935 10. Historical Note 937 The basic concepts behind Remote LFA were invented in 2002 and were 938 later included in [I-D.bryant-ipfrr-tunnels], submitted in 2004. 940 [I-D.bryant-ipfrr-tunnels], targeted a 100% protection coverage and 941 hence included additional mechanisms on top of the Remote LFA 942 concept. The addition of these mechanisms made the proposal very 943 complex and computationally intensive and it was therefore not 944 pursued as a working group item. 946 As explained in [RFC6571], the purpose of the LFA FRR technology is 947 not to provide coverage at any cost. A solution for this already 948 exists with MPLS TE FRR. MPLS TE FRR is a mature technology which is 949 able to provide protection in any topology thanks to the explicit 950 routing capability of MPLS TE. 952 The purpose of LFA FRR technology is to provide for a simple FRR 953 solution when such a solution is possible. The first step along this 954 simplicity approach was "local" LFA [RFC5286]. We propose "Remote 955 LFA" as a natural second step. The following section motivates its 956 benefits in terms of simplicity, incremental deployment and 957 significant coverage increase. 959 11. IANA Considerations 961 There are no IANA considerations that arise from this architectural 962 description of IPFRR. The RFC Editor may remove this section on 963 publication. 965 12. Security Considerations 966 The security considerations of RFC 5286 also apply. 968 To prevent their use as an attack vector the repair tunnel endpoints 969 SHOULD be assigned from a set of addresses that are not reachable 970 from outside the routing domain. 972 13. Acknowledgments 974 The authors wish to thank Levente Csikor and Chris Bowers for their 975 contribution to the cost based algorithm text. We thank Stephane 976 Litkowski for his review of this work. 978 14. Informative References 980 [I-D.bryant-ipfrr-tunnels] 981 Bryant, S., Filsfils, C., Previdi, S., and M. Shand, "IP 982 Fast Reroute using tunnels", draft-bryant-ipfrr-tunnels-03 983 (work in progress), November 2007. 985 [I-D.filsfils-rtgwg-segment-routing-use-cases] 986 Filsfils, C., Francois, P., Previdi, S., Decraene, B., 987 Litkowski, S., Horneffer, M., Milojevic, I., Shakir, R., 988 Ytti, S., Henderickx, W., Tantsura, J., Kini, S., and E. 989 Crabbe, "Segment Routing Use Cases", draft-filsfils-rtgwg- 990 segment-routing-use-cases-02 (work in progress), October 991 2013. 993 [I-D.filsfils-rtgwg-segment-routing] 994 Filsfils, C., Previdi, S., Bashandy, A., Decraene, B., 995 Litkowski, S., Horneffer, M., Milojevic, I., Shakir, R., 996 Ytti, S., Henderickx, W., Tantsura, J., and E. Crabbe, 997 "Segment Routing Architecture", draft-filsfils-rtgwg- 998 segment-routing-01 (work in progress), October 2013. 1000 [I-D.gredler-rtgwg-igp-label-advertisement] 1001 Gredler, H., Amante, S., Scholl, T., and L. Jalil, 1002 "Advertising MPLS labels in IGPs", draft-gredler-rtgwg- 1003 igp-label-advertisement-05 (work in progress), May 2013. 1005 [I-D.ietf-rtgwg-lfa-manageability] 1006 Litkowski, S., Decraene, B., Filsfils, C., and K. Raza, 1007 "Operational management of Loop Free Alternates", draft- 1008 ietf-rtgwg-lfa-manageability-00 (work in progress), May 1009 2013. 1011 [I-D.psarkar-rtgwg-rlfa-node-protection] 1012 psarkar@juniper.net, p., Gredler, H., Hegde, S., 1013 Raghuveer, H., cbowers@juniper.net, c., and S. Litkowski, 1014 "Remote-LFA Node Protection and Manageability", draft- 1015 psarkar-rtgwg-rlfa-node-protection-02 (work in progress), 1016 November 2013. 1018 [ISOCORE2010] 1019 So, N., Lin, T., and C. Chen, "LFA (Loop Free Alternates) 1020 Case Studies in Verizon's LDP Network", 2010. 1022 [RFC1701] Hanks, S., Li, T., Farinacci, D., and P. Traina, "Generic 1023 Routing Encapsulation (GRE)", RFC 1701, October 1994. 1025 [RFC1853] Simpson, W., "IP in IP Tunneling", RFC 1853, October 1995. 1027 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1028 Requirement Levels", BCP 14, RFC 2119, March 1997. 1030 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 1032 [RFC3032] Rosen, E., Tappan, D., Fedorkow, G., Rekhter, Y., 1033 Farinacci, D., Li, T., and A. Conta, "MPLS Label Stack 1034 Encoding", RFC 3032, January 2001. 1036 [RFC3411] Harrington, D., Presuhn, R., and B. Wijnen, "An 1037 Architecture for Describing Simple Network Management 1038 Protocol (SNMP) Management Frameworks", STD 62, RFC 3411, 1039 December 2002. 1041 [RFC5036] Andersson, L., Minei, I., and B. Thomas, "LDP 1042 Specification", RFC 5036, October 2007. 1044 [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast 1045 Reroute: Loop-Free Alternates", RFC 5286, September 2008. 1047 [RFC5305] Li, T. and H. Smit, "IS-IS Extensions for Traffic 1048 Engineering", RFC 5305, October 2008. 1050 [RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF 1051 for IPv6", RFC 5340, July 2008. 1053 [RFC5424] Gerhards, R., "The Syslog Protocol", RFC 5424, March 2009. 1055 [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC 1056 5714, January 2010. 1058 [RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., 1059 Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free 1060 Alternate (LFA) Applicability in Service Provider (SP) 1061 Networks", RFC 6571, June 2012. 1063 Authors' Addresses 1065 Stewart Bryant 1066 Cisco Systems 1067 250, Longwater, Green Park, 1068 Reading RG2 6GB, UK 1069 UK 1071 Email: stbryant@cisco.com 1073 Clarence Filsfils 1074 Cisco Systems 1075 De Kleetlaan 6a 1076 1831 Diegem 1077 Belgium 1079 Email: cfilsfil@cisco.com 1081 Stefano Previdi 1082 Cisco Systems 1084 Email: sprevidi@cisco.com 1086 Mike Shand 1087 Independent Contributor 1089 Email: imc.shand@gmail.com 1091 Ning So 1092 Tata Communications 1093 Mobile Broadband Services 1095 Email: Ning.So@tatacommunications.com