idnits 2.17.1 draft-ietf-rtgwg-ipfrr-notvia-addresses-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 16. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 1008. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1019. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1026. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1032. 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 Copyright Line does not match the current year == Line 492 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 (February 25, 2008) is 5897 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-bfd-base-07 == Outdated reference: A later version (-13) exists of draft-ietf-rtgwg-ipfrr-framework-07 == Outdated reference: A later version (-12) exists of draft-ietf-rtgwg-ipfrr-spec-base-10 Summary: 1 error (**), 0 flaws (~~), 5 warnings (==), 7 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: Standards Track S. Previdi 5 Expires: August 28, 2008 Cisco Systems 6 February 25, 2008 8 IP Fast Reroute Using Not-via Addresses 9 draft-ietf-rtgwg-ipfrr-notvia-addresses-02.txt 11 Status of this Memo 13 By submitting this Internet-Draft, each author represents that any 14 applicable patent or other IPR claims of which he or she is aware 15 have been or will be disclosed, and any of which he or she becomes 16 aware will be disclosed, in accordance with Section 6 of BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt. 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 This Internet-Draft will expire on August 28, 2008. 36 Copyright Notice 38 Copyright (C) The IETF Trust (2008). 40 Abstract 42 This draft describes a mechanism that provides fast reroute in an IP 43 network through encapsulation to "not-via" addresses. A single level 44 of encapsulation is used. The mechanism protects unicast, multicast 45 and LDP traffic against link, router and shared risk group failure, 46 regardless of network topology and metrics. 48 Table of Contents 50 1. Conventions used in this document . . . . . . . . . . . . . . 3 51 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 52 3. Overview of Not-via Repairs . . . . . . . . . . . . . . . . . 3 53 3.1. Use of Equal Cost Multi-Path . . . . . . . . . . . . . . . 5 54 3.2. Use of LFA repairs . . . . . . . . . . . . . . . . . . . . 5 55 4. Not-via Repair Path Computation . . . . . . . . . . . . . . . 5 56 4.1. Computing not-via repairs in routing vector protocols . . 6 57 5. Operation of Repairs . . . . . . . . . . . . . . . . . . . . . 7 58 5.1. Node Failure . . . . . . . . . . . . . . . . . . . . . . . 7 59 5.2. Link Failure . . . . . . . . . . . . . . . . . . . . . . . 7 60 5.3. Multi-homed Prefixes . . . . . . . . . . . . . . . . . . . 8 61 5.4. Installation of Repair Paths . . . . . . . . . . . . . . . 9 62 6. Compound Failures . . . . . . . . . . . . . . . . . . . . . . 10 63 6.1. Shared Risk Link Groups . . . . . . . . . . . . . . . . . 11 64 6.1.1. Use of LFAs with SRLGs . . . . . . . . . . . . . . . . 14 65 6.2. Local Area Networks . . . . . . . . . . . . . . . . . . . 15 66 6.2.1. Simple LAN Repair . . . . . . . . . . . . . . . . . . 15 67 6.2.2. LAN Component Repair . . . . . . . . . . . . . . . . . 16 68 6.2.3. LAN Repair Using Diagnostics . . . . . . . . . . . . . 17 69 7. Multiple Simultaneous Failures . . . . . . . . . . . . . . . . 17 70 8. Optimizing not-via computations using LFAs . . . . . . . . . . 17 71 9. Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . 18 72 10. Fast Reroute in an MPLS LDP Network. . . . . . . . . . . . . . 19 73 11. Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . 19 74 12. Routing Extensions . . . . . . . . . . . . . . . . . . . . . . 19 75 13. Incremental Deployment . . . . . . . . . . . . . . . . . . . . 20 76 14. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 77 15. Security Considerations . . . . . . . . . . . . . . . . . . . 20 78 16. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 21 79 17. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 80 17.1. Normative References . . . . . . . . . . . . . . . . . . . 21 81 17.2. Informative References . . . . . . . . . . . . . . . . . . 21 82 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22 83 Intellectual Property and Copyright Statements . . . . . . . . . . 23 85 1. Conventions used in this document 87 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 88 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 89 document are to be interpreted as described in RFC 2119 [RFC2119]. 91 2. Introduction 93 When a link or a router fails, only the neighbors of the failure are 94 initially aware that the failure has occurred. In a network 95 operating IP fast reroute [I-D.ietf-rtgwg-ipfrr-framework], the 96 routers that are the neighbors of the failure repair the failure. 97 These repairing routers have to steer packets to their destinations 98 despite the fact that most other routers in the network are unaware 99 of the nature and location of the failure. 101 A common limitation in most IPFRR mechanisms is an inability to 102 indicate the identity of the failure and to explicitly steer the 103 repaired packet round the failure. The extent to which this 104 limitation affects the repair coverage is topology dependent. The 105 mechanism proposed here is to encapsulate the packet to an address 106 that explicitly identifies the network component that the repair must 107 avoid. This produces a repair mechanism, which, provided the network 108 is not partitioned by the failure, will always achieve a repair. 110 3. Overview of Not-via Repairs 112 When a link or a router fails, only the neighbors of the failure are 113 initially aware that the failure has occurred. In a network 114 operating IP fast reroute [I-D.ietf-rtgwg-ipfrr-framework], the 115 routers that are the neighbors of the failure repair the failure. 116 These repairing routers have to steer packets to their destinations 117 despite the fact that most other routers in the network are unaware 118 of the nature and location of the failure. 120 A common limitation in most IPFRR mechanisms is an inability to 121 indicate the identity of the failure and to explicitly steer the 122 repaired packet round the failure. The extent to which this 123 limitation affects the repair coverage is topology dependent. The 124 mechanism proposed here is to encapsulate the packet to an address 125 that explicitly identifies the network component that the repair must 126 avoid. This produces a repair mechanism, which, provided the network 127 is not partitioned by the failure, will always achieve a repair. 129 A 130 | Bp is the address to use to get 131 | a packet to B not-via P 132 | 133 S----------P----------B. . . . . . . . . .D 134 \ | Bp^ 135 \ | | 136 \ | | 137 \ C | 138 \ | 139 ----------------+ 140 Repair to Bp 142 Figure 1: Not-via repair of router failure 144 Assume that S has a packet for some destination D that it would 145 normally send via P and B, and that S suspects that P has failed. S 146 encapsulates the packet to Bp. The path from S to Bp is the shortest 147 path from S to B not going via P. If the network contains a path from 148 S to B that does not transit router P, i.e. the network is not 149 partitioned by the failure of P, then the packet will be successfully 150 delivered to B. When the packet addressed to Bp arrives at B, B 151 removes the encapsulation and forwards the repaired packet towards 152 its final destination. 154 Note that if the path from B to the final destination includes one or 155 more nodes that are included in the repair path, a packet may back 156 track after the encapsulation is removed. However, because the 157 decapsulating router is always closer to the packet destination than 158 the encapsulating router, the packet will not loop. 160 For complete protection, all of P's neighbors will require a not-via 161 address that allows traffic to be directed to them without traversing 162 P. This is shown in Figure 2. 164 A 165 |Ap 166 | 167 Sp Pa|Pb 168 S----------P----------B 169 Ps|Pc Bp 170 | 171 Cp| 172 C 174 Figure 2: The set of Not-via P Addresses 176 3.1. Use of Equal Cost Multi-Path 178 A router can use an equal cost multi-path (ECMP) repair in place of a 179 not-via repair. 181 A router computing a not-via repair path MAY subject the repair to 182 ECMP. 184 3.2. Use of LFA repairs 186 The not-via approach provides complete repair coverage and therefore 187 may be used as the sole repair mechanism. There are, however, 188 advantages in using not-via in combination with loop free alternates 189 (LFA) and or downstream paths as documented in 190 [I-D.ietf-rtgwg-ipfrr-spec-base]. 192 LFAs are computed on a per destination basis and in general, only a 193 subset of the destinations requiring repair will have a suitable LFA 194 repair. In this case, those destinations which are repairable by 195 LFAs are so repaired and the remainder of the destinations are 196 repaired using the not-via encapsulation. This has the advantage of 197 reducing the volume of traffic that requires encapsulation. On the 198 other hand, the path taken by an LFA repair may be less optimal than 199 that of the equivalent not-via repair for traffic destined to nodes 200 close to the far end of the failure, but may be more optimal for some 201 other traffic. The description in this document assumes that LFAs 202 will be used where available, but the distribution of repairs between 203 the two mechanisms is a local implementation choice. 205 4. Not-via Repair Path Computation 207 The not-via repair mechanism requires that all routers on the path 208 from S to B (Figure 1) have a route to Bp. They can calculate this 209 by failing node P, running an SPF, and finding the shortest route to 210 B. 212 A router has no simple way of knowing whether it is on the shortest 213 path for any particular repair. It is therefore necessary for every 214 router to calculate the path it would use in the event of any 215 possible router failure. Each router therefore "fails" every router 216 in the network, one at a time, and calculates its own best route to 217 each of the neighbors of that router. In other words, with reference 218 to Figure 1, some router X will consider each router in turn to be P, 219 fail P, and then calculate its own route to each of the not-via P 220 addresses advertised by the neighbors of P. i.e. X calculates its 221 route to Sp, Ap, Bp, and Cp, in each case, not via P. 223 To calculate the repair paths a router has to calculate n-1 SPFs 224 where n is the number of routers in the network. This is expensive 225 to compute. However, the problem is amenable to a solution in which 226 each router (X) proceeds as follows. X first calculates the base 227 topology with all routers functional and determines its normal path 228 to all not-via addresses. This can be performed as part of the 229 normal SPF computation. For each router P in the topology, X then 230 performs the following actions:- 232 1. Removes router P from the topology. 234 2. Performs an incremental SPF [ISPF] on the modified topology. The 235 iSPF process involves detaching the sub-tree affected by the 236 removal of router P, and then re-attaching the detached nodes. 237 However, it is not necessary to run the iSPF to completion. It 238 is sufficient to run the iSPF up to the point where all of the 239 nodes advertising not-via P addresses have been re-attached to 240 the SPT, and then terminate it. 242 3. Reverts to the base topology. 244 This algorithm is significantly less expensive than a set of full 245 SPFs. Thus, although a router has to calculate the repair paths for 246 n-1 failures, the computational effort is much less than n-1 SPFs. 248 Experiments on a selection of real world network topologies with 249 between 40 and 400 nodes suggest that the worst-case computational 250 complexity using the above optimizations is equivalent to performing 251 between 5 and 13 full SPFs. Further optimizations are described in 252 section 6. 254 4.1. Computing not-via repairs in routing vector protocols 256 While this document focuses on link state routing protocols, it is 257 equally possible to compute not-via repairs in distance vector (e.g. 258 RIP) or path vector (e.g. BGP) routing protocols. This can be 259 achieved with very little protocol modification by advertising the 260 not-via address in the normal way, but ensuring that the information 261 about a not-via address Ps is not propagated through the node S. In 262 the case of link protection this simply means that the advertisement 263 from P to S is suppressed, with the result that S and all other nodes 264 compute a route to Ps which doesn't traverse S, as required. 266 In the case of node protection, where P is the protected node, and N 267 is some neighbor, the advertisement of Np must be suppressed not only 268 across the link N->P, but also across any link to P. The simplest way 269 of achieving this is for P itself to perform the suppression of any 270 address of the form Xp. 272 5. Operation of Repairs 274 This section explains the basic operation of the not-via repair of 275 node and link failure. 277 5.1. Node Failure 279 When router P fails (Figure 2) S encapsulates any packet that it 280 would send to B via P to Bp, and then sends the encapsulated packet 281 on the shortest path to Bp. S follows the same procedure for routers 282 A and C in Figure 2. The packet is decapsulated at the repair target 283 (A, B or C) and then forwarded normally to its destination. The 284 repair target can be determined as part of the normal SPF by 285 recording the "next-next-hop" for each destination in addition to the 286 normal next-hop. 288 Notice that with this technique only one level of encapsulation is 289 needed, and that it is possible to repair ANY failure regardless of 290 link metrics and any asymmetry that may be present in the network. 291 The only exception to this is where the failure was a single point of 292 failure that partitioned the network, in which case ANY repair is 293 clearly impossible. 295 5.2. Link Failure 297 The normal mode of operation of the network would be to assume router 298 failure. However, where some destinations are only reachable through 299 the failed router, it is desirable that an attempt be made to repair 300 to those destinations by assuming that only a link failure has 301 occurred. 303 To perform a link repair, S encapsulates to Ps (i.e. it instructs the 304 network to deliver the packet to P not-via S). All of the neighbors 305 of S will have calculated a path to Ps in case S itself had failed. 306 S could therefore give the packet to any of its neighbors (except, of 307 course, P). However, S should preferably send the encapsulated 308 packet on the shortest available path to P. This path is calculated 309 by running an SPF with the link SP failed. Note that this may again 310 be an incremental calculation, which can terminate when address Ps 311 has been reattached. 313 It is necessary to consider the behavior of IPFRR solutions when a 314 link repair is attempted in the presence of node failure. In its 315 simplest form the not-via IPFRR solution prevents the formation of 316 loops forming as a result of mutual repair, by never providing a 317 repair path for a not-via address. Referring to Figure 2, if A was 318 the neighbor of P that was on the link repair path from S to P, and P 319 itself had failed, the repaired packet from S would arrive at A 320 encapsulated to Ps. A would have detected that the AP link had 321 failed and would normally attempt to repair the packet. However, no 322 repair path is provided for any not-via address, and so A would be 323 forced to drop the packet, thus preventing the formation of loop. 325 5.3. Multi-homed Prefixes 327 A multi-homed Prefix (MHP) is a prefix that is reachable via more 328 than one router in the network. Some of these may be repairable 329 using LFAs as described in [I-D.ietf-rtgwg-ipfrr-spec-base]. Only 330 those without such a repair need be considered here. 332 When IPFRR router S (Figure 3) discovers that P has failed, it needs 333 to send packets addressed to the MHP X, which is normally reachable 334 through P, to an alternate router, which is still able to reach X. 336 X X X 337 | | | 338 | | | 339 | Sp |Pb | 340 Z...............S----------P----------B...............Y 341 Ps|Pc Bp 342 | 343 Cp| 344 C 346 Figure 3: Multi-homed Prefixes 348 S should choose the closest router that can reach X during the 349 failure as the alternate router. S determines which router to use as 350 the alternate while running the SPF with P failed. This is 351 accomplished by the normal process of re-attaching a leaf node to the 352 core topology (this is sometimes known as a "partial SPF"). 354 First, consider the case where the shortest alternate path to X is 355 via Z. S can reach Z without using the failed router P. However, S 356 cannot just send the packet towards Z, because the other routers in 357 the network will not be aware of the failure of P, and may loop the 358 packet back to S. S therefore encapsulates the packet to Z (using a 359 normal address for Z). When Z receives the encapsulated packet it 360 removes the encapsulation and forwards the packet to X. 362 Now consider the case where the shortest alternate path to X is via 363 Y, which S reaches via P and B. To reach Y, S must first repair the 364 packet to B using the normal not-via repair mechanism. To do this S 365 encapsulates the packet for X to Bp. When B receives the packet it 366 removes the encapsulation and discovers that the packet is intended 367 for MHP X. The situation now reverts to the previous case, in which 368 the shortest alternate path does not require traversal of the 369 failure. B therefore follows the algorithm above and encapsulates 370 the packet to Y (using a normal address for Y). Y removes the 371 encapsulation and forwards the packet to X. 373 It may be that the cost of reaching X using local delivery from the 374 alternate router (i.e. Z or Y) is greater than the cost of reaching 375 X via P. Under those circumstances, the alternate router would 376 normally forward to X via P, which would cause the IPFRR repair to 377 loop. To prevent the repair from looping the alternate router must 378 locally deliver a packet received via a repair encapsulation. This 379 may be specified by using a special address with the above semantics. 380 Note that only one such address is required per node. Notice that 381 using the not-via approach, only one level of encapsulation was 382 needed to repair MHPs to the alternate router. 384 5.4. Installation of Repair Paths 386 The following algorithm is used by node S (Figure 3) to pre- 387 calculate and install repair paths in the FIB, ready for immediate 388 use in the event of a failure. It is assumed that the not-via repair 389 paths have already been calculated as described above. 391 For each neighbor P, consider all destinations which are reachable 392 via P in the current topology:- 394 1. For all destinations with an ECMP or LFA repair (as described in 395 [I-D.ietf-rtgwg-ipfrr-spec-base]) install that repair. 397 2. For each destination (DR) that remains, identify in the current 398 topology the next-next-hop (H) (i.e. the neighbor of P that P 399 will use to send the packet to DR). This can be determined 400 during the normal SPF run by recording the additional 401 information. If S has a path to the not-via address Hp (H not 402 via P), install a not-via repair to Hp for the destination DR. 404 3. Identify all remaining destinations (M) which can still be 405 reached when node P fails. These will be multi-homed prefixes 406 that are not repairable by LFA, for which the normal attachment 407 node is P, or a router for which P is a single point of failure, 408 and have an alternative attachment point that is reachable after 409 P has failed. One way of determining these destinations would be 410 to run an SPF rooted at S with node P removed, but an 411 implementation may record alternative attachment points during 412 the normal SPF run. In either case, the next best point of 413 attachment can also be determined for use in step (4) below. 415 4. For each multi-homed prefix (M) identified in step (3):- 417 A. Identify the new attachment node (as shown in Figure 3). 418 This may be:- 420 a. Y, where the next hop towards Y is P, or 422 b. Z, where the next hop towards Z is not P. 424 If the attachment node is Z, install the repair for M as a 425 tunnel to Z' (where Z' is the address of Z that is used to 426 force local forwarding). 428 B. For the subset of prefixes (M) that remain (having attachment 429 point Y), install the repair path previously installed for 430 destination Y. 432 For each destination (DS) that remains, install a not-via repair 433 to Ps (P not via S). Note, these are destinations for which node 434 P is a single point of failure, and can only be repaired by 435 assuming that the apparent failure of node P was simply a failure 436 of the S-P link. Note that, if available, a downstream path to P 437 may be used for such a repair. This cannot generate a persistent 438 loop in the event of the failure of node P, but if one neighbor 439 of P uses a not-via repair and another uses a downstream path, it 440 is possible for a packet sent on the downstream path to be 441 returned to the sending node inside a not-via encapsulation. 442 Since packets destined to not-via addresses are not repaired, the 443 packet will be dropped after executing a single turn loop. 445 6. Compound Failures 447 The following types of failures involve more tha one component. 449 6.1. Shared Risk Link Groups 451 A Shared Risk Link Group (SRLG) is a set of links whose failure can 452 be caused by a single action such as a conduit cut or line card 453 failure. When repairing the failure of a link that is a member of an 454 SRLG, it must be assumed that all the other links that are also 455 members of the SRLG have also failed. Consequently, any repair path 456 must be computed to avoid not just the adjacent link, but also all 457 the links which are members of the same SRLG. 459 In Figure 4 below, the links S-P and A-B are both members of SRLG 460 "a". The semantics of the not-via address Ps changes from simply "P 461 not-via the link S-P" to be "P not-via the link S-P or any other link 462 with which S-P shares an SRLG" In Figure 4 this is the links that are 463 members of SRLG "a". I.e. links S-P and A-B. Since the information 464 about SRLG membership of all links is available in the Link State 465 Database, all nodes computing routes to the not-via address Ps can 466 infer these semantics, and perform the computation by failing all the 467 links in the SRLG when running the iSPF. 469 Note that it is not necessary for S to consider repairs to any other 470 nodes attached to members of the SRLG (such as B). It is sufficient 471 for S to repair to the other end of the adjacent link (P in this 472 case). 474 a Ps 475 S----------P---------D 476 | | 477 | a | 478 A----------B 479 | | 480 | | 481 C----------E 483 Figure 4: Shared Risk Link Group 485 In some cases, it may be that the links comprising the SRLG occur in 486 series on the path from S to the destination D, as shown in Figure 5. 487 In this case, multiple consecutive repairs may be necessary. S will 488 first repair to Ps, then P will repair to Dp. In both cases, because 489 the links concerned are members of SRLG "a" the paths are computed to 490 avoid all members of SRLG "a". 492 a Ps a Dp 493 S----------P---------D 494 | | | 495 | a | | 496 A----------B | 497 | | | 498 | | | 499 C----------E---------F 501 Figure 5: Shared Risk Link Group members in series 503 While the use of multiple repairs in series introduces some 504 additional overhead, these semantics avoid the potential 505 combinatorial explosion of not-via addresses that could otherwise 506 occur. 508 Note that although multiple repairs are used, only a single level of 509 encapsulation is required. This is because the first repair packet 510 is de-capsulated before the packet is re-encapsulated using the not- 511 via address corresponding to the far side of the next link which is a 512 member of the same SRLG. In some cases the de-capsulation and re- 513 encapsulation takes place (at least notionally) at a single node, 514 while in other cases, these functions may be performed by different 515 nodes. This scenario is illustrated in Figure 6 below. 517 a Ps a Dg 518 S----------P---------G--------D 519 | | | | 520 | a | | | 521 A----------B | | 522 | | | | 523 | | | | 524 C----------E---------F--------H 526 Figure 6: Shared Risk Link Group members in series 528 In this case, S first encapsulates to Ps, and node P decapsulates the 529 packet and forwards it "native" to G using its normal FIB entry for 530 destination D. G then repairs the packet to Dg. 532 It can be shown that such multiple repairs can never form a loop 533 because each repair causes the packet to move closer to its 534 destination. 536 It is often the case that a single link may be a member of multiple 537 SRLGs, and those SRLG may not be isomorphic. This is illustrated in 538 Figure 7 below. 540 ab Ps a Dg 541 S----------P---------G--------D 542 | | | | 543 | a | | | 544 A----------B | | 545 | | | | 546 | b | | b | 547 C----------E---------F--------H 548 | | 549 | | 550 J----------K 552 Figure 7: Multiple Shared Risk Link Groups 554 The link SP is a member of SRLGs "a" and "b". When a failure of the 555 link SP is detected, it must be assumed that BOTH SRLGs have failed. 556 Therefore the not-via path to Ps must be computed by failing all 557 links which are members of SRLG "a" or SRLG "b". I.e. the semantics 558 of Ps is now "P not-via any links which are members of any of the 559 SRLGs of which link SP is a member". This is illustrated in Figure 8 560 below. 562 ab Ps a Dg 563 S----/-----P---------G---/----D 564 | | | | 565 | a | | | 566 A----/-----B | | 567 | | | | 568 | b | | b | 569 C----/-----E---------F---/----H 570 | | 571 | | 572 J----------K 574 Figure 8: Topology used for repair computation for link S-P 576 In this case, the repair path to Ps will be S-A-C-J-K-E-B-P. It may 577 appear that there is no path to D because GD is a member of SRLG "a" 578 and FH is a member of SRLG "b". This is true if BOTH SRLGs "a" and 579 "b" have in fact failed. But that would be an instance of multiple 580 uncorrelated failures which are out of scope for this design. In 581 practice it is likely that there is only a single failure, i.e. 582 either SRLG "a" or SRLG "b" has failed, but not both. These two 583 possibilities are indistinguishable from the point of view of the 584 repairing router S and so it must repair on the assumption that both 585 are unavailable. However, each link repair is considered 586 independently. The repair to Ps delivers the packet to P which then 587 forwards the packet to G. When the packet arrives at G, if SRLG "a" 588 has failed it will be repaired around the path G-F-H-D. This is 589 illustrated in Figure 9 below. If, on the other hand, SRLG "b" has 590 failed, link GD will still be available. In this case the packet 591 will be delivered as normal across the link GD. 593 ab Ps a Dg 594 S----/-----P---------G---/----D 595 | | | | 596 | a | | | 597 A----/-----B | | 598 | | | | 599 | b | | b | 600 C----------E---------F--------H 601 | | 602 | | 603 J----------K 605 Figure 9: Topology used for repair computation for link G-D 607 A repair strategy that assumes the worst-case failure for each link 608 can often result in longer repair paths than necessary. In cases 609 where only a single link fails, rather than the full SRLG, this 610 strategy may occasionally fail to identify a repair even though a 611 viable repair path exists in the network. The use of sub-optimal 612 repair paths is an inevitable consequence of this compromise 613 approach. The failure to identify any repair is a serious 614 deficiency, but is a rare occurrence in a robustly designed network. 615 This problem can be addressed by:- 617 1. Reporting that the link in question is irreparable, so that the 618 network designer can take appropriate action. 620 2. Modifying the design of the network to avoid this possibility. 622 3. Using some form of SRLG diagnostic (for example, by running BFD 623 over alternate repair paths) to determine which SRLG member(s) 624 has actually failed and using this information to select an 625 appropriate pre-computed repair path. However, aside from the 626 complexity of performing the diagnostics, this requires multiple 627 not-via addresses per interface, which has poor scaling 628 properties. 630 6.1.1. Use of LFAs with SRLGs 632 Section 4.1 above describes the repair of links which are members of 633 one or more SRLGs. LFAs can be used for the repair of such links 634 provided that any other link with which S-P shares an SRLG is avoided 635 when computing the LFA. This is described for the simple case of 636 "local-SRLGs" in [I-D.ietf-rtgwg-ipfrr-spec-base]. 638 6.2. Local Area Networks 640 LANs are a special type of SRLG and are solved using the SRLG 641 mechanisms outlined above. With all SRLGs there is a trade-off 642 between the sophistication of the fault detection and the size of the 643 SRLG. Protecting against link failure of the LAN link(s) is 644 relatively straightforward, but as with all fast reroute mechanisms, 645 the problem becomes more complex when it is desired to protect 646 against the possibility of failure of the nodes attached to the LAN 647 as well as the LAN itself. 649 +--------------Q------C 650 | 651 | 652 | 653 A--------S-------(N)-------------P------B 654 | 655 | 656 | 657 +--------------R------D 659 Figure 10: Local Area Networks 661 Consider the LAN shown in Figure 10. For connectivity purposes, we 662 consider that the LAN is represented by the pseudonode (N). To 663 provide IPFRR protection, S must run a connectivity check to each of 664 its protected LAN adjacencies P, Q, and R, using, for example BFD 665 [I-D.ietf-bfd-base]. 667 When S discovers that it has lost connectivity to P, it is unsure 668 whether the failure is: 670 o its own interface to the LAN, 672 o the LAN itself, 674 o the LAN interface of P, 676 o the node P. 678 6.2.1. Simple LAN Repair 680 A simple approach to LAN repair is to consider the LAN and all of its 681 connected routers as a single SRLG. Thus, the address P not via the 682 LAN (Pl) would require P to be reached not-via any router connected 683 to the LAN. This is shown in Figure 11. 685 Ql Cl 686 +-------------Q--------C 687 | Qc 688 | 689 As Sl | Pl Bl 690 A--------S-------(N)------------P--------B 691 Sa | Pb 692 | 693 | Rl Dl 694 +-------------R--------D 695 Rd 697 Figure 11: Local Area Networks - LAN SRLG 699 In this case, when S detected that P had failed it would send traffic 700 reached via P and B to B not-via the LAN or any router attached to 701 the LAN (i.e. to Bl). Any destination only reachable through P would 702 be addressed to P not-via the LAN or any router attached to the LAN 703 (except of course P). 705 Whilst this approach is simple, it assumes that a large portion of 706 the network adjacent to the failure has also failed. This will 707 result in the use of sub-optimal repair paths and in some cases the 708 inability to identify a viable repair. 710 6.2.2. LAN Component Repair 712 In this approach, possible failures are considered at a finer 713 granularity, but without the use of diagnostics to identify the 714 specific component that has failed. Because S is unable to diagnose 715 the failure it must repair traffic sent through P and B, to B not- 716 via P,N (i.e. not via P and not via N), on the conservative 717 assumption that both the entire LAN and P have failed. Destinations 718 for which P is a single point of failure must as usual be sent to P 719 using an address that avoids the interface by which P is reached from 720 S, i.e. to P not-via N. Similarly for routers Q and R. 722 Notice that each router that is connected to a LAN must, as usual, 723 advertise one not-via address for each neighbor. In addition, each 724 router on the LAN must advertise an extra address not via the 725 pseudonode (N). 727 Notice also that each neighbor of a router connected to a LAN must 728 advertise two not-via addresses, the usual one not via the neighbor 729 and an additional one, not via either the neighbor or the pseudonode. 730 The required set of LAN address assignments is shown in Figure 12 731 below. Each router on the LAN, and each of its neighbors, is 732 advertising exactly one address more than it would otherwise have 733 advertised if this degree of connectivity had been achieved using 734 point-to-point links. 736 Qs Qp Qc Cqn 737 +--------------Q---------C 738 | Qr Qn Cq 739 | 740 Asn Sa Sp Sq | Ps Pq Pb Bpn 741 A--------S-------(N)-------------P---------B 742 As Sr Sn | Pr Pn Bp 743 | 744 | Rs Rp Pd Drn 745 +--------------R---------D 746 Rq Rn Dr 748 Figure 12: Local Area Networks 750 6.2.3. LAN Repair Using Diagnostics 752 A more specific LAN repair can be undertaken by using diagnostics. 753 In order to explicitly diagnose the failed network component, S 754 correlates the connectivity reports from P and one or more of the 755 other routers on the LAN, in this case, Q and R. If it lost 756 connectivity to P alone, it could deduce that the LAN was still 757 functioning and that the fault lay with either P, or the interface 758 connecting P to the LAN. It would then repair to B not via P (and P 759 not-via N for destinations for which P is a single point of failure) 760 in the usual way. If S lost connectivity to more than one router on 761 the LAN, it could conclude that the fault lay only with the LAN, and 762 could repair to P, Q and R not-via N, again in the usual way. 764 7. Multiple Simultaneous Failures 766 The failure of a node or an SRLG can result in multiple correlated 767 failures, which may be repaired using the mechanisms described in 768 this design. This design will not correctly repair a set of 769 unanticipated multiple failures. Such failures are out of scope of 770 this design and are for further study. 772 It is important that the routers in the network are able to 773 discriminate between these two classes of failure, and take 774 appropriate action. 776 8. Optimizing not-via computations using LFAs 778 If repairing node S has an LFA to the repair endpoint it is not 779 necessary for any router to perform the incremental SPF with the link 780 SP removed in order to compute the route to the not-via address Ps. 781 This is because the correct routes will already have been computed as 782 a result of the SPF on the base topology. Node S can signal this 783 condition to all other routers by including a bit in its LSP or LSA 784 associated with each LFA protected link. Routers computing not-via 785 routes can then omit the running of the iSPF for links with this bit 786 set. 788 When running the iSPF for a particular link AB, the calculating 789 router first checks whether the link AB is present in the existing 790 SPT. If the link is not present in the SPT, no further work is 791 required. This check is a normal part of the iSPF computation. 793 If the link is present in the SPT, this optimization introduces a 794 further check to determine whether the link is marked as protected by 795 an LFA in the direction in which the link appears in the SPT. If so 796 the iSPF need not be performed. For example, if the link appears in 797 the SPT in the direction A->B and A has indicated that the link AB is 798 protected by an LFA no further action is required for this link. 800 If the receipt of this information is delayed, the correct operation 801 of the protocol is not compromised provided that the necessity to 802 perform a not-via computation is re-evaluated whenever new 803 information arrives. 805 This optimization is not particularly beneficial to nodes close to 806 the repair since, as has been observed above, the computation for 807 nodes on the LFA path is trivial. However, for nodes upstream of the 808 link SP for which S-P is in the path to P, there is a significant 809 reduction in the computation required. 811 9. Multicast 813 Multicast traffic can be repaired in a similar way to unicast. The 814 multicast forwarder is able to use the not-via address to which the 815 multicast packet was addressed as an indication of the expected 816 receive interface and hence to correctly run the required RPF check. 818 In some cases, all the destinations, including the repair endpoint, 819 are repairable by an LFA. In this case, all unicast traffic may be 820 repaired without encapsulation. Multicast traffic still requires 821 encapsulation, but for the nodes on the LFA repair path the 822 computation of the not-via forwarding entry is unnecessary since, by 823 definition, their normal path to the repair endpoint is not via the 824 failure. 826 A more complete description of multicast operation will be provided 827 in a future version of this draft. 829 10. Fast Reroute in an MPLS LDP Network. 831 Not-via addresses are IP addresses and LDP [RFC5036] will distribute 832 labels for them in the usual way. The not-via repair mechanism may 833 therefore be used to provide fast re-route in an MPLS network by 834 first pushing the label which the repair endpoint uses to forward the 835 packet, and then pushing the label corresponding to the not-via 836 address needed to effect the repair. Referring once again to 837 Figure 1, if S has a packet destined for D that it must reach via P 838 and B, S first pushes B's label for D. S then pushes the label that 839 its next hop to Bp needs to reach Bp. 841 Note that in an MPLS LDP network it is necessary for S to have the 842 repair endpoint's label for the destination. When S is effecting a 843 link repair it already has this. In the case of a node repair, S 844 either needs to set up a directed LDP session with each of its 845 neighbor's neighbors, or it needs to use the next-next hop label 846 distribution mechanism proposed in [I-D.shen-mpls-ldp-nnhop-label]. 848 11. Encapsulation 850 Any IETF specified IP in IP encapsulation may be used to carry a not- 851 via repair. IP in IP [RFC2003], GRE [RFC1701] and L2TPv3 [RFC3931], 852 all have the necessary and sufficient properties. The requirement is 853 that both the encapsulating router and the router to which the 854 encapsulated packet is addressed have a common ability to process the 855 chosen encapsulation type. When an MPLS LDP network is being 856 protected, the encapsulation would normally be an additional MPLS 857 label. In an MPLS enabled IP network an MPLS label may be used in 858 place of an IP in IP encapsulation in the case above. 860 12. Routing Extensions 862 IPFRR requires IGP extensions. Each IPFRR router that is directly 863 connected to a protected network component must advertise a not-via 864 address for that component. This must be advertised in such a way 865 that the association between the protected component (link, router or 866 SRLG) and the not-via address can be determined by the other routers 867 in the network. 869 It is necessary that not-via capable routers advertise in the IGP 870 that they will calculate not-via routes. 872 It is necessary for routers to advertise the type of encapsulation 873 that they support (MPLS, GRE, L2TPv3 etc). However, the deployment 874 of mixed IP encapsulation types within a network is discouraged. 876 13. Incremental Deployment 878 Incremental deployment is supported by excluding routers that are not 879 calculating not-via routes (as indicated by their capability 880 information flooded with their link state information) from the base 881 topology used for the computation of repair paths. In that way 882 repairs may be steered around islands of routers that are not IPFRR 883 capable. Routers that are protecting a network component need to 884 have the capability to encapsulate and de-capsulate packets. 885 However, routers that are on the repair path only need to be capable 886 of calculating not-via paths and including the not-via addresses in 887 their FIB i.e. these routers do not need any changes to their 888 forwarding mechanism. 890 14. IANA Considerations 892 There are no IANA considerations that arise from this draft. 894 15. Security Considerations 896 The repair endpoints present vulnerability in that they might be used 897 as a method of disguising the delivery of a packet to a point in the 898 network. The primary method of protection should be through the use 899 of a private address space for the not-via addresses. These 900 addresses MUST NOT be advertised outside the area, and SHOULD be 901 filtered at the network entry points. In addition, a mechanism might 902 be developed that allowed the use of the mild security available 903 through the use of a key [RFC1701] [RFC3931]. With the deployment of 904 such mechanisms, the repair endpoints would not increase the security 905 risk beyond that of existing IP tunnel mechanisms. An attacker may 906 attempt to overload a router by addressing an excessive traffic load 907 to the de-capsulation endpoint. Typically, routers take a 50% 908 performance penalty in decapsulating a packet. The attacker could 909 not be certain that the router would be impacted, and the extremely 910 high volume of traffic needed, would easily be detected as an 911 anomaly. If an attacker were able to influence the availability of a 912 link, they could cause the network to invoke the not-via repair 913 mechanism. A network protected by not-via IPFRR is less vulnerable 914 to such an attack than a network that undertook a full convergence in 915 response to a link up/down event. 917 16. Acknowledgements 919 The authors would like to acknowledge contributions made by Alia 920 Atlas and John Harper. 922 17. References 924 17.1. Normative References 926 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 927 Requirement Levels", BCP 14, RFC 2119, March 1997. 929 17.2. Informative References 931 [I-D.ietf-bfd-base] 932 Katz, D. and D. Ward, "Bidirectional Forwarding 933 Detection", draft-ietf-bfd-base-07 (work in progress), 934 January 2008. 936 [I-D.ietf-rtgwg-ipfrr-framework] 937 Shand, M. and S. Bryant, "IP Fast Reroute Framework", 938 draft-ietf-rtgwg-ipfrr-framework-07 (work in progress), 939 July 2007. 941 [I-D.ietf-rtgwg-ipfrr-spec-base] 942 Atlas, A., Zinin, A., Torvi, R., Choudhury, G., Martin, 943 C., Imhoff, B., and D. Fedyk, "Basic Specification for IP 944 Fast-Reroute: Loop-free Alternates", 945 draft-ietf-rtgwg-ipfrr-spec-base-10 (work in progress), 946 November 2007. 948 [I-D.shen-mpls-ldp-nnhop-label] 949 Shen, N., "Discovering LDP Next-Nexthop Labels", 950 draft-shen-mpls-ldp-nnhop-label-02 (work in progress), 951 May 2005. 953 [ISPF] McQuillan, J., Richer, I., and E. Rosen, "ARPANET Routing 954 Algorithm Improvements"", BBN Technical Report 3803, 1978. 956 [RFC1701] Hanks, S., Li, T., Farinacci, D., and P. Traina, "Generic 957 Routing Encapsulation (GRE)", RFC 1701, October 1994. 959 [RFC2003] Perkins, C., "IP Encapsulation within IP", RFC 2003, 960 October 1996. 962 [RFC3931] Lau, J., Townsley, M., and I. Goyret, "Layer Two Tunneling 963 Protocol - Version 3 (L2TPv3)", RFC 3931, March 2005. 965 [RFC5036] Andersson, L., Minei, I., and B. Thomas, "LDP 966 Specification", RFC 5036, October 2007. 968 Authors' Addresses 970 Mike Shand 971 Cisco Systems 972 250, Longwater Avenue. 973 Reading, Berks RG2 6GB 974 UK 976 Email: mshand@cisco.com 978 Stewart Bryant 979 Cisco Systems 980 250, Longwater Avenue. 981 Reading, Berks RG2 6GB 982 UK 984 Email: stbryant@cisco.com 986 Stefano Previdi 987 Cisco Systems 988 Via Del Serafico, 200 989 00142 Rome, 990 Italy 992 Email: sprevidi@cisco.com 994 Full Copyright Statement 996 Copyright (C) The IETF Trust (2008). 998 This document is subject to the rights, licenses and restrictions 999 contained in BCP 78, and except as set forth therein, the authors 1000 retain all their rights. 1002 This document and the information contained herein are provided on an 1003 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1004 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1005 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1006 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1007 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1008 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1010 Intellectual Property 1012 The IETF takes no position regarding the validity or scope of any 1013 Intellectual Property Rights or other rights that might be claimed to 1014 pertain to the implementation or use of the technology described in 1015 this document or the extent to which any license under such rights 1016 might or might not be available; nor does it represent that it has 1017 made any independent effort to identify any such rights. Information 1018 on the procedures with respect to rights in RFC documents can be 1019 found in BCP 78 and BCP 79. 1021 Copies of IPR disclosures made to the IETF Secretariat and any 1022 assurances of licenses to be made available, or the result of an 1023 attempt made to obtain a general license or permission for the use of 1024 such proprietary rights by implementers or users of this 1025 specification can be obtained from the IETF on-line IPR repository at 1026 http://www.ietf.org/ipr. 1028 The IETF invites any interested party to bring to its attention any 1029 copyrights, patents or patent applications, or other proprietary 1030 rights that may cover technology that may be required to implement 1031 this standard. Please address the information to the IETF at 1032 ietf-ipr@ietf.org. 1034 Acknowledgment 1036 Funding for the RFC Editor function is provided by the IETF 1037 Administrative Support Activity (IASA).