idnits 2.17.1 draft-ietf-rtgwg-ipfrr-notvia-addresses-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Sep 2009 rather than the newer Notice from 28 Dec 2009. (See https://trustee.ietf.org/license-info/) 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 == Line 518 has weird spacing: '... a Ps a ...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (March 5, 2010) is 5164 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- No issues found here. Summary: 1 error (**), 0 flaws (~~), 2 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group M. Shand 3 Internet-Draft S. Bryant 4 Intended status: Experimental S. Previdi 5 Expires: September 6, 2010 Cisco Systems 6 March 5, 2010 8 IP Fast Reroute Using Not-via Addresses 9 draft-ietf-rtgwg-ipfrr-notvia-addresses-05 11 Abstract 13 This draft describes a mechanism that provides fast reroute in an IP 14 network through encapsulation to "not-via" addresses. A single level 15 of encapsulation is used. The mechanism protects unicast, multicast 16 and LDP traffic against link, router and shared risk group failure, 17 regardless of network topology and metrics. 19 Requirements Language 21 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 22 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 23 document are to be interpreted as described in RFC2119 [RFC2119]. 25 Status of this Memo 27 This Internet-Draft is submitted to IETF in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF), its areas, and its working groups. Note that 32 other groups may also distribute working documents as Internet- 33 Drafts. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 The list of current Internet-Drafts can be accessed at 41 http://www.ietf.org/ietf/1id-abstracts.txt. 43 The list of Internet-Draft Shadow Directories can be accessed at 44 http://www.ietf.org/shadow.html. 46 This Internet-Draft will expire on September 6, 2010. 48 Copyright Notice 49 Copyright (c) 2010 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents 54 (http://trustee.ietf.org/license-info) in effect on the date of 55 publication of this document. Please review these documents 56 carefully, as they describe your rights and restrictions with respect 57 to this document. Code Components extracted from this document must 58 include Simplified BSD License text as described in Section 4.e of 59 the Trust Legal Provisions and are provided without warranty as 60 described in the BSD License. 62 Table of Contents 64 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 65 2. Overview of Not-via Repairs . . . . . . . . . . . . . . . . . 4 66 2.1. Use of Equal Cost Multi-Path . . . . . . . . . . . . . . . 6 67 2.2. Use of LFA repairs . . . . . . . . . . . . . . . . . . . . 6 68 3. Not-via Repair Path Computation . . . . . . . . . . . . . . . 6 69 3.1. Computing not-via repairs in routing vector protocols . . 7 70 4. Operation of Repairs . . . . . . . . . . . . . . . . . . . . . 8 71 4.1. Node Failure . . . . . . . . . . . . . . . . . . . . . . . 8 72 4.2. Link Failure . . . . . . . . . . . . . . . . . . . . . . . 8 73 4.2.1. Loop Prevention Under Node Failure . . . . . . . . . . 9 74 4.3. Multi-homed Prefixes . . . . . . . . . . . . . . . . . . . 9 75 4.4. Installation of Repair Paths . . . . . . . . . . . . . . . 10 76 5. Compound Failures . . . . . . . . . . . . . . . . . . . . . . 12 77 5.1. Shared Risk Link Groups . . . . . . . . . . . . . . . . . 12 78 5.1.1. Use of LFAs with SRLGs . . . . . . . . . . . . . . . . 16 79 5.2. Local Area Networks . . . . . . . . . . . . . . . . . . . 16 80 5.2.1. Simple LAN Repair . . . . . . . . . . . . . . . . . . 17 81 5.2.2. LAN Component Repair . . . . . . . . . . . . . . . . . 18 82 5.2.3. LAN Repair Using Diagnostics . . . . . . . . . . . . . 19 83 5.3. Multiple Independent Failures . . . . . . . . . . . . . . 19 84 5.3.1. Looping Repairs . . . . . . . . . . . . . . . . . . . 20 85 5.3.2. Outline Solution . . . . . . . . . . . . . . . . . . . 21 86 5.3.3. Looping Repairs . . . . . . . . . . . . . . . . . . . 22 87 5.3.3.1. Dropping Looping Packets . . . . . . . . . . . . . 22 88 5.3.3.2. Computing non-looping Repairs of Repairs . . . . . 23 89 5.3.3.3. N-level Mutual Loops . . . . . . . . . . . . . . . 25 90 5.3.4. Mixing LFAs and Not-via . . . . . . . . . . . . . . . 25 91 6. Optimizing not-via computations using LFAs . . . . . . . . . . 26 92 7. Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . 27 93 8. Fast Reroute in an MPLS LDP Network. . . . . . . . . . . . . . 27 94 9. Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . 28 95 10. Routing Extensions . . . . . . . . . . . . . . . . . . . . . . 28 96 11. Incremental Deployment . . . . . . . . . . . . . . . . . . . . 28 97 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 29 98 13. Security Considerations . . . . . . . . . . . . . . . . . . . 29 99 14. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 29 100 15. References . . . . . . . . . . . . . . . . . . . . . . . . . . 29 101 15.1. Normative References . . . . . . . . . . . . . . . . . . . 29 102 15.2. Informative References . . . . . . . . . . . . . . . . . . 30 103 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 30 105 1. Introduction 107 When a link or a router fails, only the neighbors of the failure are 108 initially aware that the failure has occurred. In a network 109 operating IP fast reroute [RFC5714], the routers that are the 110 neighbors of the failure repair the failure. These repairing routers 111 have to steer packets to their destinations despite the fact that 112 most other routers in the network are unaware of the nature and 113 location of the failure. 115 A common limitation in most IPFRR mechanisms is an inability to 116 indicate the identity of the failure and to explicitly steer the 117 repaired packet round the failure. The extent to which this 118 limitation affects the repair coverage is topology dependent. The 119 mechanism proposed here is to encapsulate the packet to an address 120 that explicitly identifies the network component that the repair must 121 avoid. This produces a repair mechanism, which, provided the network 122 is not partitioned by the failure, will always achieve a repair. 124 2. Overview of Not-via Repairs 126 When a link or a router fails, only the neighbors of the failure are 127 initially aware that the failure has occurred. In a network 128 operating IP fast reroute [RFC5714], the routers that are the 129 neighbors of the failure repair the failure. These repairing routers 130 have to steer packets to their destinations despite the fact that 131 most other routers in the network are unaware of the nature and 132 location of the failure. 134 A common limitation in most IPFRR mechanisms is an inability to 135 indicate the identity of the failure and to explicitly steer the 136 repaired packet round the failure. The extent to which this 137 limitation affects the repair coverage is topology dependent. The 138 mechanism proposed here is to encapsulate the packet to an address 139 that explicitly identifies the network component that the repair must 140 avoid. This produces a repair mechanism, which, provided the network 141 is not partitioned by the failure, will always achieve a repair. 143 A 144 | Bp is the address to use to get 145 | a packet to B not-via P 146 | 147 S----------P----------B. . . . . . . . . .D 148 \ | Bp^ 149 \ | | 150 \ | | 151 \ C | 152 \ | 153 ----------------+ 154 Repair to Bp 156 Figure 1: Not-via repair of router failure 158 Assume that S has a packet for some destination D that it would 159 normally send via P and B, and that S suspects that P has failed. S 160 encapsulates the packet to Bp. The path from S to Bp is the shortest 161 path from S to B not going via P. If the network contains a path from 162 S to B that does not transit router P, i.e. the network is not 163 partitioned by the failure of P, then the packet will be successfully 164 delivered to B. When the packet addressed to Bp arrives at B, B 165 removes the encapsulation and forwards the repaired packet towards 166 its final destination. 168 Note that if the path from B to the final destination includes one or 169 more nodes that are included in the repair path, a packet may back 170 track after the encapsulation is removed. However, because the 171 decapsulating router is always closer to the packet destination than 172 the encapsulating router, the packet will not loop. 174 For complete protection, all of P's neighbors will require a not-via 175 address that allows traffic to be directed to them without traversing 176 P. This is shown in Figure 2. 178 A 179 |Ap 180 | 181 Sp Pa|Pb 182 S----------P----------B 183 Ps|Pc Bp 184 | 185 Cp| 186 C 188 Figure 2: The set of Not-via P Addresses 190 2.1. Use of Equal Cost Multi-Path 192 A router can use an equal cost multi-path (ECMP) repair in place of a 193 not-via repair. 195 A router computing a not-via repair path MAY subject the repair to 196 ECMP. 198 2.2. Use of LFA repairs 200 The not-via approach provides complete repair coverage and therefore 201 may be used as the sole repair mechanism. There are, however, 202 advantages in using not-via in combination with loop free alternates 203 (LFA) and or downstream paths as documented in [RFC5286]. 205 LFAs are computed on a per destination basis and in general, only a 206 subset of the destinations requiring repair will have a suitable LFA 207 repair. In this case, those destinations which are repairable by 208 LFAs are so repaired and the remainder of the destinations are 209 repaired using the not-via encapsulation. This has the advantage of 210 reducing the volume of traffic that requires encapsulation. On the 211 other hand, the path taken by an LFA repair may be less optimal than 212 that of the equivalent not-via repair for traffic destined to nodes 213 close to the far end of the failure, but may be more optimal for some 214 other traffic. The description in this document assumes that LFAs 215 will be used where available, but the distribution of repairs between 216 the two mechanisms is a local implementation choice. 218 3. Not-via Repair Path Computation 220 The not-via repair mechanism requires that all routers on the path 221 from S to B (Figure 1) have a route to Bp. They can calculate this 222 by failing node P, running an SPF, and finding the shortest route to 223 B. 225 A router has no simple way of knowing whether it is on the shortest 226 path for any particular repair. It is therefore necessary for every 227 router to calculate the path it would use in the event of any 228 possible router failure. Each router therefore "fails" every router 229 in the network, one at a time, and calculates its own best route to 230 each of the neighbors of that router. In other words, with reference 231 to Figure 1, some router X will consider each router in turn to be P, 232 fail P, and then calculate its own route to each of the not-via P 233 addresses advertised by the neighbors of P. i.e. X calculates its 234 route to Sp, Ap, Bp, and Cp, in each case, not via P. 236 To calculate the repair paths a router has to calculate n-1 SPFs 237 where n is the number of routers in the network. This is expensive 238 to compute. However, the problem is amenable to a solution in which 239 each router (X) proceeds as follows. X first calculates the base 240 topology with all routers functional and determines its normal path 241 to all not-via addresses. This can be performed as part of the 242 normal SPF computation. For each router P in the topology, X then 243 performs the following actions:- 245 1. Removes router P from the topology. 247 2. Performs an incremental SPF [ISPF] on the modified topology. The 248 iSPF process involves detaching the sub-tree affected by the 249 removal of router P, and then re-attaching the detached nodes. 250 However, it is not necessary to run the iSPF to completion. It 251 is sufficient to run the iSPF up to the point where all of the 252 nodes advertising not-via P addresses have been re-attached to 253 the SPT, and then terminate it. 255 3. Reverts to the base topology. 257 This algorithm is significantly less expensive than a set of full 258 SPFs. Thus, although a router has to calculate the repair paths for 259 n-1 failures, the computational effort is much less than n-1 SPFs. 261 Experiments on a selection of real world network topologies with 262 between 40 and 400 nodes suggest that the worst-case computational 263 complexity using the above optimizations is equivalent to performing 264 between 5 and 13 full SPFs. Further optimizations are described in 265 section 6. 267 3.1. Computing not-via repairs in routing vector protocols 269 While this document focuses on link state routing protocols, it is 270 equally possible to compute not-via repairs in distance vector (e.g. 271 RIP) or path vector (e.g. BGP) routing protocols. This can be 272 achieved with very little protocol modification by advertising the 273 not-via address in the normal way, but ensuring that the information 274 about a not-via address Ps is not propagated through the node S. In 275 the case of link protection this simply means that the advertisement 276 from P to S is suppressed, with the result that S and all other nodes 277 compute a route to Ps which doesn't traverse S, as required. 279 In the case of node protection, where P is the protected node, and N 280 is some neighbor, the advertisement of Np must be suppressed not only 281 across the link N->P, but also across any link to P. The simplest way 282 of achieving this is for P itself to perform the suppression of any 283 address of the form Xp. 285 4. Operation of Repairs 287 This section explains the basic operation of the not-via repair of 288 node and link failure. 290 4.1. Node Failure 292 When router P fails (Figure 2) S encapsulates any packet that it 293 would send to B via P to Bp, and then sends the encapsulated packet 294 on the shortest path to Bp. S follows the same procedure for routers 295 A and C in Figure 2. The packet is decapsulated at the repair target 296 (A, B or C) and then forwarded normally to its destination. The 297 repair target can be determined as part of the normal SPF by 298 recording the "next-next-hop" for each destination in addition to the 299 normal next-hop. 301 Notice that with this technique only one level of encapsulation is 302 needed, and that it is possible to repair ANY failure regardless of 303 link metrics and any asymmetry that may be present in the network. 304 The only exception to this is where the failure was a single point of 305 failure that partitioned the network, in which case ANY repair is 306 clearly impossible. 308 4.2. Link Failure 310 The normal mode of operation of the network would be to assume router 311 failure. However, where some destinations are only reachable through 312 the failed router, it is desirable that an attempt be made to repair 313 to those destinations by assuming that only a link failure has 314 occurred. 316 To perform a link repair, S encapsulates to Ps (i.e. it instructs the 317 network to deliver the packet to P not-via S). All of the neighbors 318 of S will have calculated a path to Ps in case S itself had failed. 319 S could therefore give the packet to any of its neighbors (except, of 320 course, P). However, S should preferably send the encapsulated 321 packet on the shortest available path to P. This path is calculated 322 by running an SPF with the link SP failed. Note that this may again 323 be an incremental calculation, which can terminate when address Ps 324 has been reattached. 326 4.2.1. Loop Prevention Under Node Failure 328 It is necessary to consider the behavior of IPFRR solutions when a 329 link repair is attempted in the presence of node failure. In its 330 simplest form the not-via IPFRR solution prevents the formation of 331 loops forming as a result of mutual repair, by never providing a 332 repair path for a not-via address. The repair of packets with not- 333 via addresses is considered in more detail in Section 5.3. Referring 334 to Figure 2, if A was the neighbor of P that was on the link repair 335 path from S to P, and P itself had failed, the repaired packet from S 336 would arrive at A encapsulated to Ps. A would have detected that the 337 AP link had failed and would normally attempt to repair the packet. 338 However, no repair path is provided for any not-via address, and so A 339 would be forced to drop the packet, thus preventing the formation of 340 loop. 342 4.3. Multi-homed Prefixes 344 A multi-homed Prefix (MHP) is a prefix that is reachable via more 345 than one router in the network. Some of these may be repairable 346 using LFAs as described in [RFC5286]. Only those without such a 347 repair need be considered here. 349 When IPFRR router S (Figure 3) discovers that P has failed, it needs 350 to send packets addressed to the MHP X, which is normally reachable 351 through P, to an alternate router, which is still able to reach X. 353 X X X 354 | | | 355 | | | 356 | Sp |Pb | 357 Z...............S----------P----------B...............Y 358 Ps|Pc Bp 359 | 360 Cp| 361 C 363 Figure 3: Multi-homed Prefixes 365 S should choose the closest router that can reach X during the 366 failure as the alternate router. S determines which router to use as 367 the alternate while running the SPF with P failed. This is 368 accomplished by the normal process of re-attaching a leaf node to the 369 core topology (this is sometimes known as a "partial SPF"). 371 First, consider the case where the shortest alternate path to X is 372 via Z. S can reach Z without using the failed router P. However, S 373 cannot just send the packet towards Z, because the other routers in 374 the network will not be aware of the failure of P, and may loop the 375 packet back to S. S therefore encapsulates the packet to Z (using a 376 normal address for Z). When Z receives the encapsulated packet it 377 removes the encapsulation and forwards the packet to X. 379 Now consider the case where the shortest alternate path to X is via 380 Y, which S reaches via P and B. To reach Y, S must first repair the 381 packet to B using the normal not-via repair mechanism. To do this S 382 encapsulates the packet for X to Bp. When B receives the packet it 383 removes the encapsulation and discovers that the packet is intended 384 for MHP X. The situation now reverts to the previous case, in which 385 the shortest alternate path does not require traversal of the 386 failure. B therefore follows the algorithm above and encapsulates 387 the packet to Y (using a normal address for Y). Y removes the 388 encapsulation and forwards the packet to X. 390 It may be that the cost of reaching X using local delivery from the 391 alternate router (i.e. Z or Y) is greater than the cost of reaching 392 X via P. Under those circumstances, the alternate router would 393 normally forward to X via P, which would cause the IPFRR repair to 394 loop. To prevent the repair from looping the alternate router must 395 locally deliver a packet received via a repair encapsulation. This 396 may be specified by using a special address with the above semantics. 397 Note that only one such address is required per node. Notice that 398 using the not-via approach, only one level of encapsulation was 399 needed to repair MHPs to the alternate router. 401 4.4. Installation of Repair Paths 403 The following algorithm is used by node S (Figure 3) to pre- 404 calculate and install repair paths in the FIB, ready for immediate 405 use in the event of a failure. It is assumed that the not-via repair 406 paths have already been calculated as described above. 408 For each neighbor P, consider all destinations which are reachable 409 via P in the current topology:- 411 1. For all destinations with an ECMP or LFA repair (as described in 412 [RFC5286]) install that repair. 414 2. For each destination (DR) that remains, identify in the current 415 topology the next-next-hop (H) (i.e. the neighbor of P that P 416 will use to send the packet to DR). This can be determined 417 during the normal SPF run by recording the additional 418 information. If S has a path to the not-via address Hp (H not 419 via P), install a not-via repair to Hp for the destination DR. 421 3. Identify all remaining destinations (M) which can still be 422 reached when node P fails. These will be multi-homed prefixes 423 that are not repairable by LFA, for which the normal attachment 424 node is P, or a router for which P is a single point of failure, 425 and have an alternative attachment point that is reachable after 426 P has failed. One way of determining these destinations would be 427 to run an SPF rooted at S with node P removed, but an 428 implementation may record alternative attachment points during 429 the normal SPF run. In either case, the next best point of 430 attachment can also be determined for use in step (4) below. 432 4. For each multi-homed prefix (M) identified in step (3):- 434 A. Identify the new attachment node (as shown in Figure 3). 435 This may be:- 437 a. Y, where the next hop towards Y is P, or 439 b. Z, where the next hop towards Z is not P. 441 If the attachment node is Z, install the repair for M as a 442 tunnel to Z' (where Z' is the address of Z that is used to 443 force local forwarding). 445 B. For the subset of prefixes (M) that remain (having attachment 446 point Y), install the repair path previously installed for 447 destination Y. 449 For each destination (DS) that remains, install a not-via repair 450 to Ps (P not via S). Note, these are destinations for which node 451 P is a single point of failure, and can only be repaired by 452 assuming that the apparent failure of node P was simply a failure 453 of the S-P link. Note that, if available, a downstream path to P 454 may be used for such a repair. This cannot generate a persistent 455 loop in the event of the failure of node P, but if one neighbor 456 of P uses a not-via repair and another uses a downstream path, it 457 is possible for a packet sent on the downstream path to be 458 returned to the sending node inside a not-via encapsulation. 459 Since packets destined to not-via addresses are not repaired, the 460 packet will be dropped after executing a single turn loop. 462 5. Compound Failures 464 The following types of failures involve more than one component: 466 1. Shared Risk Link Groups 468 2. Local Area Networks 470 3. Multiple Independent Failures 472 The considerations that apply in each of the above situations are 473 described in the following sections. 475 5.1. Shared Risk Link Groups 477 A Shared Risk Link Group (SRLG) is a set of links whose failure can 478 be caused by a single action such as a conduit cut or line card 479 failure. When repairing the failure of a link that is a member of an 480 SRLG, it must be assumed that all the other links that are also 481 members of the SRLG have also failed. Consequently, any repair path 482 must be computed to avoid not just the adjacent link, but also all 483 the links which are members of the same SRLG. 485 In Figure 4 below, the links S-P and A-B are both members of SRLG 486 "a". The semantics of the not-via address Ps changes from simply "P 487 not-via the link S-P" to be "P not-via the link S-P or any other link 488 with which S-P shares an SRLG" In Figure 4 this is the links that are 489 members of SRLG "a". I.e. links S-P and A-B. Since the information 490 about SRLG membership of all links is available in the Link State 491 Database, all nodes computing routes to the not-via address Ps can 492 infer these semantics, and perform the computation by failing all the 493 links in the SRLG when running the iSPF. 495 Note that it is not necessary for S to consider repairs to any other 496 nodes attached to members of the SRLG (such as B). It is sufficient 497 for S to repair to the other end of the adjacent link (P in this 498 case). 500 a Ps 501 S----------P---------D 502 | | 503 | a | 504 A----------B 505 | | 506 | | 507 C----------E 509 Figure 4: Shared Risk Link Group 511 In some cases, it may be that the links comprising the SRLG occur in 512 series on the path from S to the destination D, as shown in Figure 5. 513 In this case, multiple consecutive repairs may be necessary. S will 514 first repair to Ps, then P will repair to Dp. In both cases, because 515 the links concerned are members of SRLG "a" the paths are computed to 516 avoid all members of SRLG "a". 518 a Ps a Dp 519 S----------P---------D 520 | | | 521 | a | | 522 A----------B | 523 | | | 524 | | | 525 C----------E---------F 527 Figure 5: Shared Risk Link Group members in series 529 While the use of multiple repairs in series introduces some 530 additional overhead, these semantics avoid the potential 531 combinatorial explosion of not-via addresses that could otherwise 532 occur. 534 Note that although multiple repairs are used, only a single level of 535 encapsulation is required. This is because the first repair packet 536 is decapsulated before the packet is re-encapsulated using the not- 537 via address corresponding to the far side of the next link which is a 538 member of the same SRLG. In some cases the de-capsulation and re- 539 encapsulation takes place (at least notionally) at a single node, 540 while in other cases, these functions may be performed by different 541 nodes. This scenario is illustrated in Figure 6 below. 543 a Ps a Dg 544 S----------P---------G--------D 545 | | | | 546 | a | | | 547 A----------B | | 548 | | | | 549 | | | | 550 C----------E---------F--------H 552 Figure 6: Shared Risk Link Group members in series 554 In this case, S first encapsulates to Ps, and node P decapsulates the 555 packet and forwards it "native" to G using its normal FIB entry for 556 destination D. G then repairs the packet to Dg. 558 It can be shown that such multiple repairs can never form a loop 559 because each repair causes the packet to move closer to its 560 destination. 562 It is often the case that a single link may be a member of multiple 563 SRLGs, and those SRLGs may not be isomorphic. This is illustrated in 564 Figure 7 below. 566 ab Ps a Dg 567 S----------P---------G--------D 568 | | | | 569 | a | | | 570 A----------B | | 571 | | | | 572 | b | | b | 573 C----------E---------F--------H 574 | | 575 | | 576 J----------K 578 Figure 7: Multiple Shared Risk Link Groups 580 The link SP is a member of SRLGs "a" and "b". When a failure of the 581 link SP is detected, it must be assumed that BOTH SRLGs have failed. 582 Therefore the not-via path to Ps must be computed by failing all 583 links which are members of SRLG "a" or SRLG "b". I.e. the semantics 584 of Ps is now "P not-via any links which are members of any of the 585 SRLGs of which link SP is a member". This is illustrated in Figure 8 586 below. 588 ab Ps a Dg 589 S----/-----P---------G---/----D 590 | | | | 591 | a | | | 592 A----/-----B | | 593 | | | | 594 | b | | b | 595 C----/-----E---------F---/----H 596 | | 597 | | 598 J----------K 600 Figure 8: Topology used for repair computation for link S-P 602 In this case, the repair path to Ps will be S-A-C-J-K-E-B-P. It may 603 appear that there is no path to D because GD is a member of SRLG "a" 604 and FH is a member of SRLG "b". This is true if BOTH SRLGs "a" and 605 "b" have in fact failed. But that would be an instance of multiple 606 uncorrelated failures which are out of scope for this design. In 607 practice it is likely that there is only a single failure, i.e. 608 either SRLG "a" or SRLG "b" has failed, but not both. These two 609 possibilities are indistinguishable from the point of view of the 610 repairing router S and so it must repair on the assumption that both 611 are unavailable. However, each link repair is considered 612 independently. The repair to Ps delivers the packet to P which then 613 forwards the packet to G. When the packet arrives at G, if SRLG "a" 614 has failed it will be repaired around the path G-F-H-D. This is 615 illustrated in Figure 9 below. If, on the other hand, SRLG "b" has 616 failed, link GD will still be available. In this case the packet 617 will be delivered as normal across the link GD. 619 ab Ps a Dg 620 S----/-----P---------G---/----D 621 | | | | 622 | a | | | 623 A----/-----B | | 624 | | | | 625 | b | | b | 626 C----------E---------F--------H 627 | | 628 | | 629 J----------K 631 Figure 9: Topology used for repair computation for link G-D 633 A repair strategy that assumes the worst-case failure for each link 634 can often result in longer repair paths than necessary. In cases 635 where only a single link fails, rather than the full SRLG, this 636 strategy may occasionally fail to identify a repair even though a 637 viable repair path exists in the network. The use of sub-optimal 638 repair paths is an inevitable consequence of this compromise 639 approach. The failure to identify any repair is a serious 640 deficiency, but is a rare occurrence in a robustly designed network. 641 This problem can be addressed by:- 643 1. Reporting that the link in question is irreparable, so that the 644 network designer can take appropriate action. 646 2. Modifying the design of the network to avoid this possibility. 648 3. Using some form of SRLG diagnostic (for example, by running BFD 649 over alternate repair paths) to determine which SRLG member(s) 650 has actually failed and using this information to select an 651 appropriate pre-computed repair path. However, aside from the 652 complexity of performing the diagnostics, this requires multiple 653 not-via addresses per interface, which has poor scaling 654 properties. 656 4. Using the machanism described in Section 5.3 658 5.1.1. Use of LFAs with SRLGs 660 Section 4.1 above describes the repair of links which are members of 661 one or more SRLGs. LFAs can be used for the repair of such links 662 provided that any other link with which S-P shares an SRLG is avoided 663 when computing the LFA. This is described for the simple case of 664 "local-SRLGs" in [RFC5286]. 666 5.2. Local Area Networks 668 LANs are a special type of SRLG and are solved using the SRLG 669 mechanisms outlined above. With all SRLGs there is a trade-off 670 between the sophistication of the fault detection and the size of the 671 SRLG. Protecting against link failure of the LAN link(s) is 672 relatively straightforward, but as with all fast reroute mechanisms, 673 the problem becomes more complex when it is desired to protect 674 against the possibility of failure of the nodes attached to the LAN 675 as well as the LAN itself. 677 +--------------Q------C 678 | 679 | 680 | 681 A--------S-------(N)-------------P------B 682 | 683 | 684 | 685 +--------------R------D 687 Figure 10: Local Area Networks 689 Consider the LAN shown in Figure 10. For connectivity purposes, we 690 consider that the LAN is represented by the pseudonode (N). To 691 provide IPFRR protection, S must run a connectivity check to each of 692 its protected LAN adjacencies P, Q, and R, using, for example BFD 693 [I-D.ietf-bfd-base]. 695 When S discovers that it has lost connectivity to P, it is unsure 696 whether the failure is: 698 o its own interface to the LAN, 700 o the LAN itself, 702 o the LAN interface of P, 704 o the node P. 706 5.2.1. Simple LAN Repair 708 A simple approach to LAN repair is to consider the LAN and all of its 709 connected routers as a single SRLG. Thus, the address P not via the 710 LAN (Pl) would require P to be reached not-via any router connected 711 to the LAN. This is shown in Figure 11. 713 Ql Cl 714 +-------------Q--------C 715 | Qc 716 | 717 As Sl | Pl Bl 718 A--------S-------(N)------------P--------B 719 Sa | Pb 720 | 721 | Rl Dl 722 +-------------R--------D 723 Rd 725 Figure 11: Local Area Networks - LAN SRLG 727 In this case, when S detected that P had failed it would send traffic 728 reached via P and B to B not-via the LAN or any router attached to 729 the LAN (i.e. to Bl). Any destination only reachable through P would 730 be addressed to P not-via the LAN or any router attached to the LAN 731 (except of course P). 733 Whilst this approach is simple, it assumes that a large portion of 734 the network adjacent to the failure has also failed. This will 735 result in the use of sub-optimal repair paths and in some cases the 736 inability to identify a viable repair. 738 5.2.2. LAN Component Repair 740 In this approach, possible failures are considered at a finer 741 granularity, but without the use of diagnostics to identify the 742 specific component that has failed. Because S is unable to diagnose 743 the failure it must repair traffic sent through P and B, to B not- 744 via P,N (i.e. not via P and not via N), on the conservative 745 assumption that both the entire LAN and P have failed. Destinations 746 for which P is a single point of failure must as usual be sent to P 747 using an address that avoids the interface by which P is reached from 748 S, i.e. to P not-via N. Similarly for routers Q and R. 750 Notice that each router that is connected to a LAN must, as usual, 751 advertise one not-via address for each neighbor. In addition, each 752 router on the LAN must advertise an extra address not via the 753 pseudonode (N). 755 Notice also that each neighbor of a router connected to a LAN must 756 advertise two not-via addresses, the usual one not via the neighbor 757 and an additional one, not via either the neighbor or the pseudonode. 758 The required set of LAN address assignments is shown in Figure 12 759 below. Each router on the LAN, and each of its neighbors, is 760 advertising exactly one address more than it would otherwise have 761 advertised if this degree of connectivity had been achieved using 762 point-to-point links. 764 Qs Qp Qc Cqn 765 +--------------Q---------C 766 | Qr Qn Cq 767 | 768 Asn Sa Sp Sq | Ps Pq Pb Bpn 769 A--------S-------(N)-------------P---------B 770 As Sr Sn | Pr Pn Bp 771 | 772 | Rs Rp Pd Drn 773 +--------------R---------D 774 Rq Rn Dr 776 Figure 12: Local Area Networks 778 5.2.3. LAN Repair Using Diagnostics 780 A more specific LAN repair can be undertaken by using diagnostics. 781 In order to explicitly diagnose the failed network component, S 782 correlates the connectivity reports from P and one or more of the 783 other routers on the LAN, in this case, Q and R. If it lost 784 connectivity to P alone, it could deduce that the LAN was still 785 functioning and that the fault lay with either P, or the interface 786 connecting P to the LAN. It would then repair to B not via P (and P 787 not-via N for destinations for which P is a single point of failure) 788 in the usual way. If S lost connectivity to more than one router on 789 the LAN, it could conclude that the fault lay only with the LAN, and 790 could repair to P, Q and R not-via N, again in the usual way. 792 5.3. Multiple Independent Failures 794 IPFRR repair of multiple simultaneous failures which are not members 795 of a known SRLG is complicated by the problem that the use of 796 multiple concurrent repairs may result in looping repair paths. As 797 described in Section 4.2.1, the simplest method of preventing such 798 loops, is to ensure that packets addressed to a not-via address are 799 not repaired but instead are dropped. It is possible that a network 800 may experience multiple simultaneous failures. This may be due to 801 simple statistical effects, but the more likely cause is 802 unanticipated SRLGs. When multiple failures which are not part of an 803 anticipated group are detected, repairs are abandoned and the network 804 reverts to normal convergence. Although safe, this approach is 805 somewhat draconian, since there are many circumstances were multiple 806 repairs do not induce loops. 808 This section describes the properties of multiple unrelated failures 809 and proposes some methods that may be used to address this problem. 811 5.3.1. Looping Repairs 813 Let us assume that the repair mechanism is based on solely on not-via 814 repairs. LFA or downstream routes may be incorporated, and will be 815 dealt with later. 817 A------//------B------------D 818 / \ 819 / \ 820 F G 821 \ / 822 \ / 823 X------//------Y 825 Figure 13: The General Case of Multiple Failures 827 The essential case is as illustrated in Figure 13. Note that 828 depending on the repair case under consideration, there may be paths 829 present in Figure 13, that are in addition to those shown in the 830 figure. For example there may be paths between A and B, and/or 831 between X and Y. These paths are omitted for graphical clarity. 833 There are three cases to consider: 835 1) Consider the general case of a pair of protected links A-B and 836 X-Y as shown in the network fragment shown Figure 13. If the 837 repair path for A-B does not traverse X-Y and the repair path for 838 X-Y does not traverse A-B, this case is completely safe and will 839 not cause looping or packet loss. 841 A more common variation of this case is shown in Figure 14, which 842 shows two failures in different parts of the network in which a 843 packet from A to D traverses two concatenated repairs. 845 A------//------B------------X------//------Y------D 846 | | | | 847 | | | | 848 M--------------+ N--------------+ 850 Figure 14: Concatenated Repairs 852 2) In Figure 13, the repair for A-B traverses X-Y, but the repair 853 for X-Y does not traverse A-B. This case occurs when the not-via 854 path from A to B traverses link X-Y, but the not-via path from X 855 to Y traverses some path not shown in Figure 13. Without the 856 multi-failure mechanism described in this section the repaired 857 packet for A-B would be dropped when it reached X-Y, since the 858 repair of repaired packets would be forbidden. However, if this 859 packet were allowed to be repaired, the path to D would be 860 complete and no harm would be done, although two levels of 861 encapsulation would be required. 863 3) The repair for A-B traverses X-Y AND the repair for X-Y 864 traverses A-B. In this case unrestricted repair would result in 865 looping packets and increasing levels of encapsulation. 867 The challenge in applying IPFRR to a network that is undergoing 868 multiple failures is, therefore, to identify which of these cases 869 exist in the network and react accordingly. 871 5.3.2. Outline Solution 873 When A is computing the not-via repair path for A-B (i.e. the path 874 for packets addressed to Ba, read as "B not-via A") it is aware of 875 the list of nodes which this path traverses. This can be recorded by 876 a simple addition to the SPF process, and the not-via addresses 877 associated with each forward link can be determined. If the path 878 were A, F, X, Y, G, B, (Figure 13) the list of not-via addresses 879 would be: Fa, Xf, Yx, Gy, Bg. Under standard not-via operation, A 880 would populate its FIB such that all normal addresses normally 881 reachable via A-B would be encapsulated to Ba when A-B fails, but 882 traffic addressed to any not-via address arriving at A would be 883 dropped. The new procedure modifies this such that any traffic for a 884 not-via address normally reachable over A-B is also encapsulated to 885 Ba unless the not-via address is one of those previously identified 886 as being on the path to Ba, for example Yx, in which case the packet 887 is dropped. 889 The above procedure allows cases 1 and 2 above to be repaired, while 890 preventing the loop which would result from case 3. 892 Note that this is accomplished by pre-computing the required FIB 893 entries, and does not require any detailed packet inspection. The 894 same result could be achieved by checking for multiple levels of 895 encapsulation and dropping any attempt to triple encapsulate. 896 However, this would require more detailed inspection of the packet, 897 and causes difficulties when more than 2 "simultaneous" failures are 898 contemplated. 900 So far we have permitted benign repairs to coexist, albeit sometimes 901 requiring multiple encapsulation. Note that in many cases there will 902 be no performance impact since unless both failures are on the same 903 node, the two encapsulations or two decapsulations will be performed 904 at different nodes. There is however the issue of the MTU impact of 905 multiple encapsulations. 907 In the following sub-section we consider the various strategies that 908 may be applied to case 3 - mutual repairs that would loop. 910 5.3.3. Looping Repairs 912 In case 3, the simplest approach is to simply not install repairs for 913 repair paths that might loop. In this case, although the potentially 914 looping traffic is dropped, the traffic is not repaired. If we 915 assume that a hold-down is applied before reconvergence in case the 916 link failure was just a short glitch, and if a loop free convergence 917 mechanism further delays convergence, then the traffic will be 918 dropped for an extended period. In these circumstances it would be 919 better to "abandon all hope" (AAH) 920 [] and immediately 921 invoke normal re-convergence. 923 Note that it is not sufficient to expedite the issuance of an LSP 924 reporting the failure, since this may be treated as a permitted 925 simultaneous failure by the oFIB algorithm. It is therefore 926 necessary to explicitly trigger an oFIB AAH. 928 5.3.3.1. Dropping Looping Packets 930 One approach to case 3 is to allow the repair, and to experimentally 931 discover the incompatibility of the repairs if and when they occur. 932 With this method we permit the repair in case 3 and trigger AAH when 933 a packet drop count on the not-via address has been incremented. 934 Alternatively, it is possible to wait until the LSP describing the 935 change is issued normally (i.e. when X announces the failure of X-Y). 936 When the repairing node A, which has precomputed that X-Y failures 937 are mutually incompatible with its own repairs receives this LSP it 938 can then issue the AAH. This has the disadvantage that it doesn't 939 overcome the hold-down delay, but it requires no "data-driven" 940 operation, and it still has the required effect of abandoning the 941 oFIB which is probably the longer of the delays (although with 942 signalled oFIB this should be sub-second). 944 Whilst both of the experimental approaches described above are 945 feasible, they tend to induce AAH in the presence of otherwise 946 feasible repairs, and they are contrary to the philosophy of repair 947 pre-determination that has been applied to existing IPFRR solutions. 949 5.3.3.2. Computing non-looping Repairs of Repairs 951 An alternative approach to simply dropping the looping packets, or to 952 detecting the loop after it has occurred, is to use secondary SRLGs. 953 With a link state routing protocol it is possible to precompute the 954 incompatibility of the repairs in advance and to compute an 955 alternative SRLG repair path. Although this does considerably 956 increase the computational complexity it may be possible to compute 957 repair paths that avoid the need to simply drop the offending 958 packets. 960 This approach requires us to identify the mutually incompatible 961 failures, and advertise them as "secondary SRLGs". When computing 962 the repair paths for the affected not-via addresses these links are 963 simultaneously failed. Note that the assumed simultaneous failure 964 and resulting repair path only applies to the repair path computed 965 for the conflicting not-via addresses, and is not used for normal 966 addresses. This implies that although there will be a longer repair 967 path when there is more than one failure, if there is a single 968 failure the repair path length will be "normal". 970 Ideally we would wish to only invoke secondary SRLG computation when 971 we are sure that the repair paths are mutually incompatible. 972 Consider the case of node A in Figure 13. A first identifies that 973 the repair path for A-B is via F-X-Y-G-B. It then explores this path 974 determining the repair path for each link in the path. Thus, for 975 example, it performs a check at X by running an SPF rooted at X with 976 the X-Y link removed to determine whether A-B is indeed on X's repair 977 path for packets addressed to Yx. 979 Some optimizations are possible in this calculation, which appears at 980 first sight to be order hk (where h is the average hop length of 981 repair paths and k is the average number of neighbours of a router). 982 When A is computing its set of repair paths, it does so for all its k 983 neighbours. In each case it identifies a list of node pairs 984 traversed by each repair. These lists may often have one or more 985 node pairs in common, so the actual number of link failures which 986 require investigation is the union of these sets. It is then 987 necessary to run an SPF rooted at the first node of each pair (the 988 first node because the pairings are ordered representing the 989 direction of the path), with the link to the second node removed. 990 This SPF, while not an incremental, can be terminated as soon as the 991 not-via address is reached. For example, when running the SPF rooted 992 at X, with the link X-Y removed, the SPF can be terminated when Yx is 993 reached. Once the path has been found, the path is checked to 994 determine if it traverses any of A's links in the direction away from 995 A. Note that, because the node pair XY may exist in the list for more 996 than one of A's links (i.e. it lies on more than one repair path), it 997 is necessary to identify the correct list, and hence link which has a 998 mutually looping repair path. That link of A is then advertised by A 999 as a secondary SRLG paired with the link X-Y. Also note that X will 1000 be running this algorithm as well, and will identify that XY is 1001 paired with A-B and so advertise it. This could perhaps be used as a 1002 further check. 1004 The ordering of the pairs in the lists is important. i.e. X-Y and 1005 Y-X are dealt with separately. If and only if the repairs are 1006 mutually incompatible, we need to advertise the pair of links as a 1007 secondary SRLG, and then ALL nodes compute repair paths around both 1008 failures using an additional not-via address with the semantics not- 1009 via A-B AND not-via X-Y. 1011 A further possibility is that because we are going to the trouble of 1012 advertising these SRLG sets, we could also advertise the new repair 1013 path and only get the nodes on that path to perform the necessary 1014 computation. Note also that once we have reached Q space with 1015 respect to the two failures we need no longer continue the 1016 computation, so we only need to notify the nodes on the path that are 1017 not in Q-space. 1019 One cause of mutually looping repair paths is the existence of nodes 1020 with only two links, or sections of the network which are only bi- 1021 connected. In these cases, repair is clearly impossible - the 1022 failure of both links partitions the network. It would be 1023 advantageous to be able to identify these cases, and inhibit the 1024 fruitless advertisement of the secondary SRLG information. This 1025 could be achieved by the node detecting the requirement for a 1026 secondary SRLG, first running the not-via computation with both links 1027 removed. If this does not result in a path, it is clear that the 1028 network would be partitioned by such a failure, and so no 1029 advertisement is required. 1031 5.3.3.3. N-level Mutual Loops 1033 [Editors' Note: This section needs to be reviewed before final 1034 publication] 1036 It is tempting to conclude that the mechanism described above can be 1037 applied to the general case of N failures. If we use the approach of 1038 assuming that repairs are not mutual, and catching the loops and 1039 executing AAH when they occur, then we can attempt repairs in the 1040 case of N failures. 1042 If we use the approach of avoiding potentially mutual repairs and 1043 creating secondary SRLG, then we have to explore N levels of repair, 1044 where N is the number of simultaneous failures we wish to repair. 1046 5.3.4. Mixing LFAs and Not-via 1048 So far in this section we have assumed that all repairs use not-via 1049 tunnels. However, in practise we may wish to use LFAs or downstream 1050 routes where available. This complicates the issue, because their 1051 use results in packets which are being repaired, but NOT addressed to 1052 not-via addresses. If BOTH links are using downstream routes there 1053 is no possibility of looping, since it is impossible to have a pair 1054 of nodes which are both downstream of each other [RFC5286]. 1056 Loops can however occur when LFAs are used. An obvious example is 1057 the well known node repair problem with LFAs [RFC5286]. If one link 1058 is using a downstream route, while the other is using a not-via 1059 tunnel, the potential mechanism described above would work provided 1060 it were possible to determine the nodes on the path of the downstream 1061 route. Some methods of computing downstream routes do not provide 1062 this path information. If the path information is however available, 1063 the link using a downstream route will have a discard FIB entry for 1064 the not-via address of the other link. The consequence is that 1065 potentially looping packets will be discarded when they attempt to 1066 cross this link. 1068 In the case where the mutual repairs are both using not-via repairs, 1069 the loop will be broken when the packet arrives at the second 1070 failure. However packets are unconditionally repaired by means of a 1071 downstream routes, and thus when the mutual pair consists of a 1072 downstream route and a not-via repair, the looping packet will only 1073 be dropped when it gets back to the first failure. i.e. it will 1074 execute a single turn of the loop before being dropped. 1076 There is a further complication with downstream routes, since 1077 although the path may be computed to the far side of the failure, the 1078 packet may "peel off" to its destination before reaching the far side 1079 of the failure. In this case it may traverse some other link which 1080 has failed and was not accounted for on the computed path. If the 1081 A-B repair (Figure 1) is a downstream route and the X-Y repair is a 1082 not-via repair, we can have the situation where the X-Y repair 1083 packets encapsulated to Yx follow a path which attempts to traverse 1084 A-B. If the A-B repair path for "normal" addresses is a downstream 1085 route, it cannot be assumed that the repair path for packets 1086 addressed to Yx can be sent to the same neighbour. This is because 1087 the validity of a downstream route must be ascertained in the 1088 topology represented by Yx, i.e. that with the link X-Y failed. This 1089 is not the same topology that was used for the normal downstream 1090 calculation, and use of the normal downstream route for the 1091 encapsulated packets may result in an undetected loop. If it is 1092 computationally feasible to check the downstream route in this 1093 topology (i.e. for any not-via address Qp which traverses A-B we must 1094 perform the downstream calculation for that not-via address in the 1095 topology with link Q-P failed.), then the downstream repair for Yx 1096 can safely be used. These packets cannot re-visit X-Y, since by 1097 definition they will avoid that link. Alternatively, the packet 1098 could be always repaired in a not-via tunnel. i.e. even though the 1099 normal repair for traffic traversing A-B would be to use a downstream 1100 route, we could insist that such traffic addressed to a not-via 1101 address MUST use a tunnel to Ba. Such a tunnel would only be 1102 installed for an address Qp if it were established that it did not 1103 traverse Q-P (using the rules described above). 1105 6. Optimizing not-via computations using LFAs 1107 If repairing node S has an LFA to the repair endpoint it is not 1108 necessary for any router to perform the incremental SPF with the link 1109 SP removed in order to compute the route to the not-via address Ps. 1110 This is because the correct routes will already have been computed as 1111 a result of the SPF on the base topology. Node S can signal this 1112 condition to all other routers by including a bit in its LSP or LSA 1113 associated with each LFA protected link. Routers computing not-via 1114 routes can then omit the running of the iSPF for links with this bit 1115 set. 1117 When running the iSPF for a particular link AB, the calculating 1118 router first checks whether the link AB is present in the existing 1119 SPT. If the link is not present in the SPT, no further work is 1120 required. This check is a normal part of the iSPF computation. 1122 If the link is present in the SPT, this optimization introduces a 1123 further check to determine whether the link is marked as protected by 1124 an LFA in the direction in which the link appears in the SPT. If so 1125 the iSPF need not be performed. For example, if the link appears in 1126 the SPT in the direction A->B and A has indicated that the link AB is 1127 protected by an LFA no further action is required for this link. 1129 If the receipt of this information is delayed, the correct operation 1130 of the protocol is not compromised provided that the necessity to 1131 perform a not-via computation is re-evaluated whenever new 1132 information arrives. 1134 This optimization is not particularly beneficial to nodes close to 1135 the repair since, as has been observed above, the computation for 1136 nodes on the LFA path is trivial. However, for nodes upstream of the 1137 link SP for which S-P is in the path to P, there is a significant 1138 reduction in the computation required. 1140 7. Multicast 1142 Multicast traffic can be repaired in a similar way to unicast. The 1143 multicast forwarder is able to use the not-via address to which the 1144 multicast packet was addressed as an indication of the expected 1145 receive interface and hence to correctly run the required RPF check. 1147 In some cases, all the destinations, including the repair endpoint, 1148 are repairable by an LFA. In this case, all unicast traffic may be 1149 repaired without encapsulation. Multicast traffic still requires 1150 encapsulation, but for the nodes on the LFA repair path the 1151 computation of the not-via forwarding entry is unnecessary since, by 1152 definition, their normal path to the repair endpoint is not via the 1153 failure. 1155 A more complete description of multicast operation is for further 1156 study. 1158 8. Fast Reroute in an MPLS LDP Network. 1160 Not-via addresses are IP addresses and LDP [RFC5036] will distribute 1161 labels for them in the usual way. The not-via repair mechanism may 1162 therefore be used to provide fast re-route in an MPLS network by 1163 first pushing the label which the repair endpoint uses to forward the 1164 packet, and then pushing the label corresponding to the not-via 1165 address needed to effect the repair. Referring once again to 1166 Figure 1, if S has a packet destined for D that it must reach via P 1167 and B, S first pushes B's label for D. S then pushes the label that 1168 its next hop to Bp needs to reach Bp. 1170 Note that in an MPLS LDP network it is necessary for S to have the 1171 repair endpoint's label for the destination. When S is effecting a 1172 link repair it already has this. In the case of a node repair, S 1173 either needs to set up a directed LDP session with each of its 1174 neighbor's neighbors, or it needs to use the next-next hop label 1175 distribution mechanism proposed in [I-D.shen-mpls-ldp-nnhop-label]. 1177 9. Encapsulation 1179 Any IETF specified IP in IP encapsulation may be used to carry a not- 1180 via repair. IP in IP [RFC2003], GRE [RFC1701] and L2TPv3 [RFC3931], 1181 all have the necessary and sufficient properties. The requirement is 1182 that both the encapsulating router and the router to which the 1183 encapsulated packet is addressed have a common ability to process the 1184 chosen encapsulation type. When an MPLS LDP network is being 1185 protected, the encapsulation would normally be an additional MPLS 1186 label. In an MPLS enabled IP network an MPLS label may be used in 1187 place of an IP in IP encapsulation in the case above. 1189 10. Routing Extensions 1191 IPFRR requires IGP extensions. Each IPFRR router that is directly 1192 connected to a protected network component must advertise a not-via 1193 address for that component. This must be advertised in such a way 1194 that the association between the protected component (link, router or 1195 SRLG) and the not-via address can be determined by the other routers 1196 in the network. 1198 It is necessary that not-via capable routers advertise in the IGP 1199 that they will calculate not-via routes. 1201 It is necessary for routers to advertise the type of encapsulation 1202 that they support (MPLS, GRE, L2TPv3 etc). However, the deployment 1203 of mixed IP encapsulation types within a network is discouraged. 1205 11. Incremental Deployment 1207 Incremental deployment is supported by excluding routers that are not 1208 calculating not-via routes (as indicated by their capability 1209 information flooded with their link state information) from the base 1210 topology used for the computation of repair paths. In that way 1211 repairs may be steered around islands of routers that are not IPFRR 1212 capable. Routers that are protecting a network component need to 1213 have the capability to encapsulate and decapsulate packets. However, 1214 routers that are on the repair path only need to be capable of 1215 calculating not-via paths and including the not-via addresses in 1216 their FIB i.e. these routers do not need any changes to their 1217 forwarding mechanism. 1219 12. IANA Considerations 1221 There are no IANA considerations that arise from this draft. 1223 13. Security Considerations 1225 The repair endpoints present vulnerability in that they might be used 1226 as a method of disguising the delivery of a packet to a point in the 1227 network. The primary method of protection should be through the use 1228 of a private address space for the not-via addresses. These 1229 addresses MUST NOT be advertised outside the area, and SHOULD be 1230 filtered at the network entry points. In addition, a mechanism might 1231 be developed that allowed the use of the mild security available 1232 through the use of a key [RFC1701] [RFC3931]. With the deployment of 1233 such mechanisms, the repair endpoints would not increase the security 1234 risk beyond that of existing IP tunnel mechanisms. An attacker may 1235 attempt to overload a router by addressing an excessive traffic load 1236 to the de-capsulation endpoint. Typically, routers take a 50% 1237 performance penalty in decapsulating a packet. The attacker could 1238 not be certain that the router would be impacted, and the extremely 1239 high volume of traffic needed, would easily be detected as an 1240 anomaly. If an attacker were able to influence the availability of a 1241 link, they could cause the network to invoke the not-via repair 1242 mechanism. A network protected by not-via IPFRR is less vulnerable 1243 to such an attack than a network that undertook a full convergence in 1244 response to a link up/down event. 1246 14. Acknowledgements 1248 The authors would like to acknowledge contributions made by Alia 1249 Atlas and John Harper. 1251 15. References 1253 15.1. Normative References 1255 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1256 Requirement Levels", BCP 14, RFC 2119, March 1997. 1258 15.2. Informative References 1260 [I-D.ietf-bfd-base] 1261 Katz, D. and D. Ward, "Bidirectional Forwarding 1262 Detection", draft-ietf-bfd-base-11 (work in progress), 1263 January 2010. 1265 [I-D.shen-mpls-ldp-nnhop-label] 1266 Shen, N., "Discovering LDP Next-Nexthop Labels", 1267 draft-shen-mpls-ldp-nnhop-label-02 (work in progress), 1268 May 2005. 1270 [ISPF] McQuillan, J., Richer, I., and E. Rosen, "ARPANET Routing 1271 Algorithm Improvements"", BBN Technical Report 3803, 1978. 1273 [RFC1701] Hanks, S., Li, T., Farinacci, D., and P. Traina, "Generic 1274 Routing Encapsulation (GRE)", RFC 1701, October 1994. 1276 [RFC2003] Perkins, C., "IP Encapsulation within IP", RFC 2003, 1277 October 1996. 1279 [RFC3931] Lau, J., Townsley, M., and I. Goyret, "Layer Two Tunneling 1280 Protocol - Version 3 (L2TPv3)", RFC 3931, March 2005. 1282 [RFC5036] Andersson, L., Minei, I., and B. Thomas, "LDP 1283 Specification", RFC 5036, October 2007. 1285 [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast 1286 Reroute: Loop-Free Alternates", RFC 5286, September 2008. 1288 [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", 1289 RFC 5714, January 2010. 1291 Authors' Addresses 1293 Mike Shand 1294 Cisco Systems 1295 250, Longwater Avenue. 1296 Reading, Berks RG2 6GB 1297 UK 1299 Email: mshand@cisco.com 1300 Stewart Bryant 1301 Cisco Systems 1302 250, Longwater Avenue. 1303 Reading, Berks RG2 6GB 1304 UK 1306 Email: stbryant@cisco.com 1308 Stefano Previdi 1309 Cisco Systems 1310 Via Del Serafico, 200 1311 00142 Rome, 1312 Italy 1314 Email: sprevidi@cisco.com