idnits 2.17.1 draft-ietf-rtgwg-ipfrr-notvia-addresses-00.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 19. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 926. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 898. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 905. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 911. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 456 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 (Dec 2006) is 6342 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) == Unused Reference: 'MPLS-TE' is defined on line 971, but no explicit reference was found in the text == Outdated reference: A later version (-11) exists of draft-ietf-bfd-base-05 -- Obsolete informational reference (is this intentional?): RFC 3036 (ref. 'LDP') (Obsoleted by RFC 5036) Summary: 2 errors (**), 0 flaws (~~), 5 warnings (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET DRAFT IP Fast Reroute Using Not-via Addresses Dec 2006 4 Network Working Group S. Bryant 5 Internet Draft M. Shand 6 Expiration Date: June 2007 S. Previdi 7 Cisco Systems 9 Dec 2006 11 IP Fast Reroute Using Not-via Addresses 12 14 Status of this Memo 16 By submitting this Internet-Draft, each author represents that any 17 applicable patent or other IPR claims of which he or she is aware 18 have been or will be disclosed, and any of which he or she becomes 19 aware will be disclosed, in accordance with Section 6 of BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF), its areas, and its working groups. Note that 23 other groups may also distribute working documents as 24 Internet-Drafts. 26 Internet-Drafts are draft documents valid for a maximum of six 27 months and may be updated, replaced, or obsoleted by other documents 28 at any time. It is inappropriate to use Internet-Drafts as 29 reference material or to cite them other than as "work in progress". 31 The list of current Internet-Drafts can be accessed at 32 http://www.ietf.org/1id-abstracts.html 34 The list of Internet-Draft Shadow Directories can be accessed at 35 http://www.ietf.org/shadow.html 37 Abstract 38 This draft describes a mechanism that provides fast reroute in an IP 39 network through encapsulation to "not-via" addresses. A single level 40 of encapsulation is used. The mechanism protects unicast, multicast 41 and LDP traffic against link, router and shared risk group failure, 42 regardless of network topology and metrics. 44 Conventions used in this document 46 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 47 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 48 document are to be interpreted as described in RFC 2119 [RFC2119]. 50 Table of Contents 51 1. Overview of Not-via Repairs.........................................3 52 1.1 Use of Equal Cost Multi-Path......................................5 53 1.2 Use of LFA repairs................................................5 54 2. Not-via Repair Path Computation.....................................5 56 3. Operation of Repairs................................................6 57 3.1 Node Failure......................................................6 58 3.2 Link Failure......................................................7 59 3.3 Multi-homed Prefix................................................7 60 3.4 Installation of Repair Paths......................................9 61 4. Compound failures..................................................10 62 4.1 Shared Risk Link Groups..........................................10 63 4.1.1 Use of LFAs with SRLGs.......................................14 64 4.2 Local Area Networks..............................................14 65 4.2.1 Simple LAN Repair............................................15 66 4.2.2 LAN Component Repair.........................................15 67 4.2.3 LAN Repair Using Diagnostics.................................16 68 5. Multiple Simultaneous Failures.....................................17 70 6. Optimizing not-via computations using LFAs.........................17 72 7. Multicast..........................................................18 74 8. Fast Reroute in an MPLS LDP Network................................18 76 9. Encapsulation......................................................18 78 10. Routing Extensions................................................19 80 11. Incremental Deployment............................................19 82 12. IANA considerations...............................................19 84 13. Security Considerations...........................................19 85 Introduction 87 When a link or a router fails, only the neighbors of the failure are 88 initially aware that the failure has occurred. In a network 89 operating IP fast reroute [IPFRR], the routers that are the 90 neighbors of the failure repair the failure. These repairing routers 91 have to steer packets to their destinations despite the fact that 92 most other routers in the network are unaware of the nature and 93 location of the failure. 95 A common limitation in most IPFRR mechanisms is an inability to 96 steer the repaired packet round an identified failure. The extent to 97 which this limitation affects the repair coverage is topology 98 dependent. The mechanism proposed here is to encapsulate the packet 99 to an address that explicitly identifies the network component that 100 the repair must avoid. This produces a repair mechanism, which, 101 provided the network is not partitioned by the failure, will always 102 achieve a repair. 104 1. Overview of Not-via Repairs 106 The purpose of a repair is to deliver packets to their destination 107 without traversing a known failure in the network, i.e. to deliver 108 the packet not via the failure. A special address is assigned to 109 each protected component. This address is called the not-via 110 address. The semantics of a not-via address are that a packet 111 addressed to a not-via address must be delivered to the router 112 advertising that address, not via the protected component (link, 113 node, SRLG etc.) with which that address is associated. 115 A simple example would be node repair in which an additional address 116 is assigned to each interface in the network. To repair a failure, 117 the repairing router encapsulates the packet to the not-via address 118 of the router interface on the far side of the failure. The routers 119 on the repair path then know to which router they must deliver the 120 packet, and which network component they must avoid. The network 121 fragment shown in Figure 1 illustrates a not-via repair for the case 122 of a router failure. 124 A 125 | Bp is the address to use to get 126 | a packet to B not-via P 127 | 128 S----------P----------B. . . . . . . . . .D 129 \ | Bp^ 130 \ | | 131 \ | | 132 \ C | 133 \ | 134 ----------------+ 135 Repair to Bp 137 Figure 1: Not-via repair of router failure 139 Assume that S has a packet for some destination D that it would 140 normally send via P and B, and that S suspects that P has failed. S 141 encapsulates the packet to Bp. The path from S to Bp is the shortest 142 path from S to B not going via P. If the network contains a path 143 from S to B that does not transit router P, i.e. the network is not 144 partitioned by the failure of P, then the packet will be 145 successfully delivered to B. When the packet addressed to Bp arrives 146 at B, B removes the encapsulation and forwards the repaired packet 147 towards its final destination. 149 Note that if the path from B to the final destination includes one 150 or more nodes that are included in the repair path, a packet may 151 back track after the encapsulation is removed. However, because the 152 decapsulating router is always closer to the packet destination than 153 the encapsulating router, the packet will not loop. 155 For complete protection, all of P's neighbors will require a not-via 156 address that allows traffic to be directed to them without 157 traversing P. This is shown in Figure 2. 159 A 160 |Ap 161 | 162 Sp Pa|Pb 163 S----------P----------B 164 Ps|Pc Bp 165 | 166 Cp| 167 C 169 Figure 2: The set of Not-via P Addresses 171 1.1 Use of Equal Cost Multi-Path 173 A router can use an equal cost multi-path (ECMP) repair in place of 174 a not-via repair. 176 A router computing a not-via repair path MAY subject the repair to 177 ECMP. 179 1.2 Use of LFA repairs 181 The not-via approach provides complete repair coverage and therefore 182 may be used as the sole repair mechanism. There are, however, 183 advantages in using not-via in combination with loop free alternates 184 (LFA) as documented in [LFA]. 186 LFAs are computed on a per destination basis and in general, only a 187 subset of the destinations requiring repair will have a suitable LFA 188 repair. In this case, those destinations which are repairable by 189 LFAs are so repaired and the remainder of the destinations are 190 repaired using the not-via encapsulation. This has the advantage of 191 reducing the volume of traffic that requires encapsulation. On the 192 other hand, the path taken by an LFA repair may be less optimal than 193 that of the equivalent not-via repair. The description in this 194 document assumes that LFAs will be used where available, but the 195 distribution of repairs between the two mechanisms is a local 196 implementation choice. 198 2. Not-via Repair Path Computation 200 The not-via repair mechanism requires that all routers on the path 201 from S to B (Figure 1) have a route to Bp. They can calculate this 202 by failing node P, running an SPF, and finding the shortest route to 203 B. 205 A router has no simple way of knowing whether it is on the shortest 206 path for any particular repair. It is therefore necessary for every 207 router to calculate the path it would use in the event of any 208 possible router failure. Each router therefore "fails" every router 209 in the network, one at a time, and calculates its own best route to 210 each of the neighbors of that router. In other words, with reference 211 to Figure 2, some router X will consider each router in turn to be 212 P, fail P, and then calculate its own route to each of the not-via P 213 addresses advertised by the neighbors of P. i.e. X calculates its 214 route to Sp, Ap, Bp, and Cp, in each case, not via P. 216 To calculate the repair paths a router has to calculate n-1 SPFs 217 where n is the number of routers in the network. This is expensive 218 to compute. However, the problem is amenable to a solution in which 219 each router (X) proceeds as follows. X first calculates the base 220 topology with all routers functional and determines its normal path 221 to all not-via addresses. This can be performed as part of the 222 normal SPF computation. For each router P in the topology, X then 223 performs the following actions:- 225 1. Removes router P from the topology. 227 2. Performs an incremental SPF [ISPF] on the modified topology. 228 The iSPF process involves detaching the sub-tree affected by 229 the removal of router P, and then re-attaching the detached 230 nodes. However, it is not necessary to run the iSPF to 231 completion. It is sufficient to run the iSPF up to the point 232 where all of the nodes advertising not-via P addresses have 233 been re-attached to the SPT, and then terminate it. 235 3. Reverts to the base topology. 237 This algorithm is significantly less expensive than a set of full 238 SPFs. Thus, although a router has to calculate the repair paths for 239 n-1 failures, the computational effort is much less than n-1 SPFs. 241 Experiments on a selection of real world network topologies with 242 between 40 and 400 nodes suggest that the worst-case computational 243 complexity using the above optimizations is equivalent to performing 244 between 5 and 13 full SPFs. Further optimizations are described in 245 section 6. 247 3. Operation of Repairs 249 This section explains the basic operation of the not-via repair of 250 node and link failure. 252 3.1 Node Failure 254 When router P fails (Figure 2) S encapsulates any packet that it 255 would send to B via P to Bp, and then sends the encapsulated packet 256 on the shortest path to Bp. S follows the same procedure for routers 257 A and C in Figure 2. The packet is decapsulated at the repair target 258 (A, B or C) and then forwarded normally to its destination. The 259 repair target can be determined as part of the normal SPF by 260 recording the "next-next-hop" for each destination in addition to 261 the normal next-hop. 263 Notice that with this technique only one level of encapsulation is 264 needed, and that it is possible to repair ANY failure regardless of 265 link metrics and any asymmetry that may be present in the network. 266 The only exception to this is where the failure was a single point 267 of failure that partitioned the network, in which case ANY repair is 268 clearly impossible. 270 3.2 Link Failure 272 The normal mode of operation of the network would be to assume 273 router failure. However, where some destinations are only reachable 274 through the failed router, it is desirable that an attempt be made 275 to repair to those destinations by assuming that only a link failure 276 has occurred. 278 To perform a link repair, S encapsulates to Ps (i.e. it instructs 279 the network to deliver the packet to P not-via S). All of the 280 neighbors of S will have calculated a path to Ps in case S itself 281 had failed. S could therefore give the packet to any of its 282 neighbors (except, of course, P). However, S should preferably send 283 the encapsulated packet on the shortest available path to P. This 284 path is calculated by running an SPF with the link SP failed. Note 285 that this may again be an incremental calculation, which can 286 terminate when address Ps has been reattached. 288 It is necessary to consider the behavior of IPFRR solutions when a 289 link repair is attempted in the presence of node failure. In its 290 simplest form the not-via IPFRR solution prevents the formation of 291 loops forming as a result of mutual repair, by never providing a 292 repair path for a not-via address. Referring to Figure 2, if A was 293 the neighbor of P that was on the link repair path from S to P, and 294 P itself had failed, the repaired packet from S would arrive at A 295 encapsulated to Ps. A would have detected that the AP link had 296 failed and would normally attempt to repair the packet. However, no 297 repair path is provided for any not-via address, and so A would be 298 forced to drop the packet, thus preventing the formation of loop. 300 3.3 Multi-homed Prefix 302 A multi-homed Prefix (MHP) is a prefix that is reachable via more 303 than one router in the network. Some of these may be repairable 304 using LFAs as described in [LFA]. Only those without such a repair 305 need be considered here. 307 When IPFRR router S (Figure 3) discovers that P has failed, it needs 308 to send packets addressed to the MHP X, which is normally reachable 309 through P, to an alternate router, which is still able to reach X. 311 X X X 312 | | | 313 | | | 314 | Sp |Pb | 315 Z...............S----------P----------B...............Y 316 Ps|Pc Bp 317 | 318 Cp| 319 C 321 Figure 3: Multi-homed Prefixes 323 S should choose the closest router that can reach X during the 324 failure as the alternate router. S determines which router to use as 325 the alternate while running the SPF with P failed. This is 326 accomplished by the normal process of re-attaching a leaf node to 327 the core topology (this is sometimes known as a "partial SPF"). 329 First, consider the case where the shortest alternate path to X is 330 via Z. S can reach Z without using the failed router P. However, S 331 cannot just send the packet towards Z, because the other routers in 332 the network will not be aware of the failure of P, and may loop the 333 packet back to S. S therefore encapsulates the packet to Z (using a 334 normal address for Z). When Z receives the encapsulated packet it 335 removes the encapsulation and forwards the packet to X. 337 Now consider the case where the shortest alternate path to X is via 338 Y, which S reaches via P and B. To reach Y, S must first repair the 339 packet to B using the normal not-via repair mechanism. To do this S 340 encapsulates the packet for X to Bp. When B receives the packet it 341 removes the encapsulation and discovers that the packet is intended 342 for MHP X. The situation now reverts to the previous case, in which 343 the shortest alternate path does not require traversal of the 344 failure. B therefore follows the algorithm above and encapsulates 345 the packet to Y (using a normal address for Y). Y removes the 346 encapsulation and forwards the packet to X. 348 It may be that the cost of reaching X using local delivery from the 349 alternate router (i.e. Z or Y) is greater than the cost of reaching 350 X via P. Under those circumstances, the alternate router would 351 normally forward to X via P, which would cause the IPFRR repair to 352 loop. To prevent the repair from looping the alternate router must 353 locally deliver a packet received via a repair encapsulation. This 354 may be specified by using a special address with the above 355 semantics. Note that only one such address is required per node. 357 Notice that using the not-via approach, only one level of 358 encapsulation was needed to repair MHPs to the alternate router. 360 3.4 Installation of Repair Paths 362 The following algorithm is used by node S (Figure 3) to pre- 363 calculate and install repair paths in the FIB, ready for immediate 364 use in the event of a failure. 366 For each neighbor P, consider all destinations which are reachable 367 via P in the current topology:- 369 1. For all destinations with an ECMP or LFA repair (as described 370 in [LFA] ) install that repair. 372 2. For each destination (DR) that remains, identify in the current 373 topology the next-next-hop (H) (i.e. the neighbor of P that P 374 will use to send the packet to DR). 376 3. For each next-next-hop node H for which S has a path to the 377 not-via address Hp (H not via P), identify each destination 378 with current next-next-hop H and install a not-via repair to Hp 379 for that destination. 381 4. Identify all remaining destinations (M) which can still be 382 reached when node P fails. These will be multi-homed prefixes 383 that are not repairable by LFA, for which the normal attachment 384 node is P, or a router for which P is a single point of 385 failure, and have an attachment point that is reachable after P 386 has failed. 388 5. For each multi-homed prefix (M) identified in step (4):- 390 a. Identify the new attachment node (as shown in Figure 3). 391 This may be:- 393 i. Y, where the next hop towards Y is P, or 395 ii. Z, where the next hop towards Z is not P. 397 b. If the attachment node is Z, install the repair for M as a 398 tunnel to Z' (where Z' is the address of Z that is used to 399 force local forwarding). 401 c. For the subset of prefixes (M) that remain (having 402 attachment point Y), install the repair path previously 403 installed for destination Y. 405 6. For each destination (DS) that remains, install a not-via 406 repair to Ps (P not via S). Note, these are destinations for 407 which node P is a single point of failure, and can only be 408 repaired by assuming that the apparent failure of node P was 409 simply a failure of the S-P link. 411 4. Compound failures 413 4.1 Shared Risk Link Groups 415 A Shared Risk Link Group (SRLG) is a set of links whose failure can 416 be caused by a single action such as a conduit cut or line card 417 failure. When repairing the failure of a link that is a member of an 418 SRLG, it must be assumed that all the other links that are also 419 members of the SRLG have also failed. Consequently, any repair path 420 must be computed to avoid not just the adjacent link, but also all 421 the links which are members of the same SRLG. 423 In Figure 4 below, the links S-P and A-B are both members of 424 SRLG "a". The semantics of the not-via address Ps changes from 425 simply "P not-via the link S-P" to be "P not-via the link S-P or any 426 other link with which S-P shares an SRLG" In Figure 4 this is the 427 links that are members of SRLG "a". I.e. links S-P and A-B. Since 428 the information about SRLG membership of all links is available in 429 the Link State Database, all nodes computing routes to the not-via 430 address Ps can infer these semantics, and perform the computation by 431 failing all the links in the SRLG when running the iSPF. 433 Note that it is not necessary for S to consider repairs to any other 434 nodes attached to members of the SRLG (such as B). It is sufficient 435 for S to repair to the other end of the adjacent link (P in this 436 case). 438 a Ps 439 S----------P---------D 440 | | 441 | a | 442 A----------B 443 | | 444 | | 445 C----------E 447 Figure 4: Shared Risk Link Group 449 In some cases, it may be that the links comprising the SRLG occur in 450 series on the path from S to the destination D, as shown in Figure 451 5. In this case, multiple consecutive repairs may be necessary. S 452 will first repair to Ps, then P will repair to Dp. In both cases, 453 because the links concerned are members of SRLG "a" the paths are 454 computed to avoid all members of SRLG "a". 456 a Ps a Dp 457 S----------P---------D 458 | | | 459 | a | | 460 A----------B | 461 | | | 462 | | | 463 C----------E---------F 465 Figure 5: Shared Risk Link Group members in series 467 While the use of multiple repairs in series introduces some 468 additional overhead, these semantics avoid the potential 469 combinatorial explosion of not-via addresses that could otherwise 470 occur. 472 Note that although multiple repairs are used, only a single level of 473 encapsulation is required. This is because the first repair packet 474 is de-capsulated before the packet is re-encapsulated using the not- 475 via address corresponding to the far side of the next link which is 476 a member of the same SRLG. In some cases the de-capsulation and re- 477 encapsulation takes place (at least notionally) at a single node, 478 while in other cases, these functions may be performed by different 479 nodes. This scenario is illustrated in Figure 6 below. 481 a Ps a Dg 482 S----------P---------G--------D 483 | | | | 484 | a | | | 485 A----------B | | 486 | | | | 487 | | | | 488 C----------E---------F--------H 490 Figure 6: Shared Risk Link Group members in series 492 In this case, S first encapsulates to Ps, and node P decapsulates 493 the packet and forwards it "native" to G using its normal FIB entry 494 for destination D. G then repairs the packet to Dg. 496 It can be shown that such multiple repairs can never form a loop 497 because each repair causes the packet to move closer to its 498 destination. 500 It is often the case that a single link may be a member of multiple 501 SRLGs, and those SRLG may not be isomorphic. This is illustrated in 502 Figure 7 below. 504 ab Ps a Dg 505 S----------P---------G--------D 506 | | | | 507 | a | | | 508 A----------B | | 509 | | | | 510 | b | | b | 511 C----------E---------F--------H 512 | | 513 | | 514 J----------K 516 Figure 7: Multiple Shared Risk Link Groups 518 The link SP is a member of SRLGs "a" and "b". When a failure of the 519 link SP is detected, it must be assumed that BOTH SRLGs have failed. 520 Therefore the not-via path to Ps must be computed by failing all 521 links which are members of SRLG "a" or SRLG "b". I.e. the semantics 522 of Ps is now "P not-via any links which are members of any of the 523 SRLGs of which link SP is a member". This is illustrated in Figure 8 524 below. 526 ab Ps a Dg 527 S----/-----P---------G---/----D 528 | | | | 529 | a | | | 530 A----/-----B | | 531 | | | | 532 | b | | b | 533 C----/-----E---------F---/----H 534 | | 535 | | 536 J----------K 538 Figure 8: Topology used for repair computation for link S-P 540 In this case, the repair path to Ps will be S-A-C-J-K-E-B-P. It may 541 appear that there is no path to D because GD is a member of SRLG "a" 542 and FH is a member of SRLG "b". This is true if BOTH SRLGs "a" and 543 "b" have in fact failed. But that would be an instance of multiple 544 uncorrelated failures which are out of scope for this design. In 545 practice it is likely that there is only a single failure, i.e. 546 either SRLG "a" or SRLG "b" has failed, but not both. These two 547 possibilities are indistinguishable from the point of view of the 548 repairing router S and so it must repair on the assumption that both 549 are unavailable. However, each link repair is considered 550 independently. The repair to Ps delivers the packet to P which then 551 forwards the packet to G. When the packet arrives at G, if SRLG "a" 552 has failed it will be repaired around the path G-F-H-D. This is 553 illustrated in Figure 9 below. If, on the other hand, SRLG "b" has 554 failed, link GD will still be available. In this case the packet 555 will be delivered as normal across the link GD. 557 ab Ps a Dg 558 S----/-----P---------G---/----D 559 | | | | 560 | a | | | 561 A----/-----B | | 562 | | | | 563 | b | | b | 564 C----------E---------F--------H 565 | | 566 | | 567 J----------K 569 Figure 9: Topology used for repair computation for link G-D 571 A repair strategy that assumes the worst-case failure for each link 572 can often result in longer repair paths than necessary. In cases 573 where only a single link fails, rather than the full SRLG, this 574 strategy may occasionally fail to identify a repair even though a 575 viable repair path exists in the network. The use of sub-optimal 576 repair paths is an inevitable consequence of this compromise 577 approach. The failure to identify any repair is a serious 578 deficiency, but is a rare occurrence in a robustly designed network. 579 This problem can be addressed by:- 581 1. Reporting that the link in question is irreparable, so that the 582 network designer can take appropriate action. 584 2. Modifying the design of the network to avoid this possibility. 586 3. Using some form of SRLG diagnostic (for example, by running BFD 587 over alternate repair paths) to determine which SRLG member(s) 588 has actually failed and using this information to select an 589 appropriate pre-computed repair path. However, aside from the 590 complexity of performing the diagnostics, this requires 591 multiple not-via addresses per interface, which has poor 592 scaling properties. 594 4.1.1 Use of LFAs with SRLGs 596 Section 4.1 above describes the repair of links which are members of 597 one or more SRLGs. LFAs can be used for the repair of such links 598 provided that any other link with which S-P shares an SRLG is 599 avoided when computing the LFA. This is described for the simple 600 case of "local-SRLGs" in [LFA]. 602 4.2 Local Area Networks 604 LANs are a special type of SRLG and are solved using the SRLG 605 mechanisms outlined above. With all SRLGs there is a trade-off 606 between the sophistication of the fault detection and the size of 607 the SRLG. Protecting against link failure of the LAN link(s) is 608 relatively straightforward, but as with all fast reroute mechanisms, 609 the problem becomes more complex when it is desired to protect 610 against the possibility of failure of the nodes attached to the LAN 611 as well as the LAN itself. 613 +--------------Q------C 614 | 615 | 616 | 617 A--------S-------(N)-------------P------B 618 | 619 | 620 | 621 +--------------R------D 623 Figure 10: Local Area Networks 625 Consider the LAN shown in Figure 10. For connectivity purposes, we 626 consider that the LAN is represented by the pseudonode (N). To 627 provide IPFRR protection, S must run a connectivity check to each of 628 its protected LAN adjacencies P, Q, and R, using, for example BFD 629 [BFD]. 631 When S discovers that it has lost connectivity to P, it is unsure 632 whether the failure is: 634 . its own interface to the LAN, 636 . the LAN itself, 638 . the LAN interface of P, 640 . the node P. 642 4.2.1 Simple LAN Repair 644 A simple approach to LAN repair is to consider the LAN and all of 645 its connected routers as a single SRLG. Thus, the address P not via 646 the LAN (Pl) would require P to be reached not-via any router 647 connected to the LAN. This is shown in Figure 11. 649 Ql Cl 650 +-------------Q--------C 651 | Qc 652 | 653 As Sl | Pl Bl 654 A--------S-------(N)------------P--------B 655 Sa | Pb 656 | 657 | Rl Dl 658 +-------------R--------D 659 Rd 661 Figure 11: Local Area Networks - LAN SRLG 663 In this case, when S detected that P had failed it would send 664 traffic reached via P and B to B not-via the LAN or any router 665 attached to the LAN (i.e. to Bl). Any destination only reachable 666 through P would be addressed to P not-via the LAN or any router 667 attached to the LAN (except of course P). 669 Whilst this approach is simple, it assumes that a large portion of 670 the network adjacent to the failure has also failed. This will 671 result in the use of sub-optimal repair paths and in some cases the 672 inability to identify a viable repair. 674 4.2.2 LAN Component Repair 676 In this approach, possible failures are considered at a finer 677 granularity, but without the use of diagnostics to identify the 678 specific component that has failed. Because S is unable to diagnose 679 the failure it must repair traffic sent through P and B, to B not- 680 via P,N (i.e. not via P and not via N), on the conservative 681 assumption that both the entire LAN and P have failed. Destinations 682 for which P is a single point of failure must as usual be sent to P 683 using an address that avoids the interface by which P is reached 684 from S, i.e. to P not-via N. Similarly for routers Q and R. 686 Notice that each router that is connected to a LAN must, as usual, 687 advertise one not-via address for each neighbor. In addition, each 688 router on the LAN must advertise an extra address not via the 689 pseudonode (N). 691 Notice also that each neighbor of a router connected to a LAN must 692 advertise two not-via addresses, the usual one not via the neighbor 693 and an additional one, not via either the neighbor or the 694 pseudonode. The required set of LAN address assignments is shown in 695 Figure 12 below. Each router on the LAN, and each of its neighbors, 696 is advertising exactly one address more than it would otherwise have 697 advertised if this degree of connectivity had been achieved using 698 point-to-point links. 700 Qs Qp Qc Cqn 701 +--------------Q---------C 702 | Qr Qn Cq 703 | 704 Asn Sa Sp Sq | Ps Pq Pb Bpn 705 A--------S-------(N)-------------P---------B 706 As Sr Sn | Pr Pn Bp 707 | 708 | Rs Rp Pd Drn 709 +--------------R---------D 710 Rq Rn Dr 712 Figure 12: Local Area Networks 714 4.2.3 LAN Repair Using Diagnostics 716 A more specific LAN repair can be undertaken by using diagnostics. 717 In order to explicitly diagnose the failed network component, S 718 correlates the connectivity reports from P and one or more of the 719 other routers on the LAN, in this case, Q and R. If it lost 720 connectivity to P alone, it could deduce that the LAN was still 721 functioning and that the fault lay with either P, or the interface 722 connecting P to the LAN. It would then repair to B not via P (and P 723 not-via N for destinations for which P is a single point of failure) 724 in the usual way. If S lost connectivity to more than one router on 725 the LAN, it could conclude that the fault lay only with the LAN, and 726 could repair to P, Q and R not-via N, again in the usual way. 728 5. Multiple Simultaneous Failures 730 The failure of a node or an SRLG can result in multiple correlated 731 failures, which may be repaired using the mechanisms described in 732 this design. This design will not correctly repair a set of 733 unanticipated multiple failures. Such failures are out of scope of 734 this design and are for further study. 736 It is important that the routers in the network are able to 737 discriminate between these two classes of failure, and take 738 appropriate action. 740 6. Optimizing not-via computations using LFAs 742 If repairing node S has an LFA to the repair endpoint it is not 743 necessary for any router to perform the incremental SPF with the 744 link SP removed in order to compute the route to the not-via address 745 Ps. This is because the correct routes will already have been 746 computed as a result of the SPF on the base topology. Node S can 747 signal this condition to all other routers by including a bit in its 748 LSP or LSA associated with each LFA protected link. Routers 749 computing not-via routes can then omit the running of the iSPF for 750 links with this bit set. 752 When running the iSPF for a particular link AB, the calculating 753 router first checks whether the link AB is present in the existing 754 SPT. If the link is not present in the SPT, no further work is 755 required. This check is a normal part of the iSPF computation. 757 If the link is present in the SPT, this optimization introduces a 758 further check to determine whether the link is marked as protected 759 by an LFA in the direction in which the link appears in the SPT. If 760 so the iSPF need not be performed. For example, if the link appears 761 in the SPT in the direction A->B and A has indicated that the link 762 AB is protected by an LFA no further action is required for this 763 link. 765 If the receipt of this information is delayed, the correct operation 766 of the protocol is not compromised provided that the necessity to 767 perform a not-via computation is re-evaluated whenever new 768 information arrives. 770 This optimization is not particularly beneficial to nodes close to 771 the repair since, as has been observed above, the computation for 772 nodes on the LFA path is trivial. However, for nodes upstream of the 773 link SP for which S-P is in the path to P, there is a significant 774 reduction in the computation required. 776 7. Multicast 778 Multicast traffic can be repaired in a similar way to unicast. The 779 multicast forwarder is able to use the not-via address to which the 780 multicast packet was addressed as an indication of the expected 781 receive interface and hence to correctly run the required RPF check. 783 In some cases, all the destinations, including the repair endpoint, 784 are repairable by an LFA. In this case, all unicast traffic may be 785 repaired without encapsulation. Multicast traffic still requires 786 encapsulation, but for the nodes on the LFA repair path the 787 computation of the not-via forwarding entry is unnecessary since, by 788 definition, their normal path to the repair endpoint is not via the 789 failure. 791 A more complete description of multicast operation will be provided 792 in a future version of this draft. 794 8. Fast Reroute in an MPLS LDP Network. 796 Not-via addresses are IP addresses and LDP [LDP] will distribute 797 labels for them in the usual way. The not-via repair mechanism may 798 therefore be used to provide fast re-route in an MPLS network by 799 first pushing the label which the repair endpoint uses to forward 800 the packet, and then pushing the label corresponding to the not-via 801 address needed to effect the repair. Referring once again to Figure 802 1, if S has a packet destined for D that it must reach via P and B, 803 S first pushes B's label for D. S then pushes the label that its 804 next hop to Bp needs to reach Bp. 806 Note that in an MPLS LDP network it is necessary for S to have the 807 repair endpoint's label for the destination. When S is effecting a 808 link repair it already has this. In the case of a node repair, S 809 either needs to set up a directed LDP session with each of its 810 neighbor's neighbors, or it needs to use the next-next hop label 811 distribution mechanism proposed in [NNHL]. 813 9. Encapsulation 815 Any IETF specified IP in IP encapsulation may be used to carry a 816 not-via repair. IP in IP [IPIP], GRE [GRE] and L2TPv3 [L2TPv3], all 817 have the necessary and sufficient properties. The requirement is 818 that both the encapsulating router and the router to which the 819 encapsulated packet is addressed have a common ability to process 820 the chosen encapsulation type. 822 When an MPLS LDP network is being protected, the encapsulation would 823 normally be an additional MPLS label. In an MPLS enabled IP network 824 an MPLS label may be used in place of an IP in IP encapsulation in 825 the case above. 827 10. Routing Extensions 829 IPFRR requires IGP extensions. Each IPFRR router that is directly 830 connected to a protected network component must advertise a not-via 831 address for that component. This must be advertised in such a way 832 that the association between the protected component (link, router 833 or SRLG) and the not-via address can be determined by the other 834 routers in the network. 836 It is necessary that not-via capable routers advertise in the IGP 837 that they will calculate not-via routes. 839 It is necessary for routers to advertise the type of encapsulation 840 that they support (MPLS, GRE [GRE], L2TPv3 etc). However, the 841 deployment of mixed IP encapsulation types within a network is 842 discouraged. 844 11. Incremental Deployment 846 Incremental deployment is supported by excluding routers that are 847 not calculating not-via routes (as indicated by their capability 848 information flooded with their link state information) from the base 849 topology used for the computation of repair paths. In that way 850 repairs may be steered around islands of routers that are not IPFRR 851 capable. 853 Routers that are protecting a network component need to have the 854 capability to encapsulate and de-capsulate packets. However, routers 855 that are on the repair path only need to be capable of calculating 856 not-via paths and including the not-via addresses in their FIB i.e. 857 these routers do not need any changes to their forwarding mechanism. 859 12. IANA considerations 861 There are no IANA considerations that arise from this draft. 863 13. Security Considerations 865 The repair endpoints present vulnerability in that they might be 866 used as a method of disguising the delivery of a packet to a point 867 in the network. The primary method of protection should be through 868 the use of a private address space for the not-via addresses. These 869 addresses MUST NOT be advertised outside the area, and SHOULD be 870 filtered at the network entry points. In addition, a mechanism might 871 be developed that allowed the use of the mild security available 872 through the use of a key [GRE] [L2TPv3]. With the deployment of such 873 mechanisms, the repair endpoints would not increase the security 874 risk beyond that of existing IP tunnel mechanisms. 876 An attacker may attempt to overload a router by addressing an 877 excessive traffic load to the de-capsulation endpoint. Typically, 878 routers take a 50% performance penalty in decapsulating a packet. 879 The attacker could not be certain that the router would be impacted, 880 and the extremely high volume of traffic needed, would easily be 881 detected as an anomaly. 883 If an attacker were able to influence the availability of a link, 884 they could cause the network to invoke the not-via repair mechanism. 885 A network protected by not-via IPFRR is less vulnerable to such an 886 attack than a network that undertook a full convergence in response 887 to a link up/down event. 889 Intellectual Property Statement 891 The IETF takes no position regarding the validity or scope of any 892 Intellectual Property Rights or other rights that might be claimed 893 to pertain to the implementation or use of the technology described 894 in this document or the extent to which any license under such 895 rights might or might not be available; nor does it represent that 896 it has made any independent effort to identify any such rights. 897 Information on the procedures with respect to rights in RFC 898 documents can be found in BCP 78 and BCP 79. 900 Copies of IPR disclosures made to the IETF Secretariat and any 901 assurances of licenses to be made available, or the result of an 902 attempt made to obtain a general license or permission for the use 903 of such proprietary rights by implementers or users of this 904 specification can be obtained from the IETF on-line IPR repository 905 at http://www.ietf.org/ipr. 907 The IETF invites any interested party to bring to its attention any 908 copyrights, patents or patent applications, or other proprietary 909 rights that may cover technology that may be required to implement 910 this standard. Please address the information to the IETF at ietf- 911 ipr@ietf.org. 913 Full copyright statement 915 Copyright (C) The Internet Society (2006). This document is subject 916 to the rights, licenses and restrictions contained in BCP 78, and 917 except as set forth therein, the authors retain all their rights. 919 This document and the information contained herein are provided on 920 an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE 921 REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE 922 IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL 923 WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY 924 WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE 925 ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS 926 FOR A PARTICULAR PURPOSE. 928 Normative References 930 There are no normative references. 932 Informative References 934 Internet-drafts are works in progress available from 935 937 [BFD] Katz, D., Ward, D., "Bidirectional Forwarding 938 Detection", < draft-ietf-bfd-base-05.txt>, 939 June 2006, (work in progress). 941 [GRE] S. Hanks, T. Li, D. Farinacci, P. Traina. 942 "Generic Routing Encapsulation (GRE)", 943 RFC 1701,. October 1994. 945 [IPFRR] Shand, M., Bryant, S., "IP Fast-reroute 946 Framework", 947 , 948 October 2006, (work in progress). 950 [IPIP] Perkins, C., "IP encapsulation within IP", RFC 951 2003, October 1996 953 [ISPF] McQuillan, J., I. Richer and E. Rosen, "ARPANET 954 Routing Algorithm Improvements", BBN Technical 955 Report 3803, April 1978. 957 [L2TPv3] J. Lau, Ed., et al., "Layer Two Tunneling 958 Protocol - Version 3 (L2TPv3)", RFC 3931, 959 March 2005. 961 [LDP] Andersson, L., Doolan, P., Feldman, N., 962 Fredette, A. and B. Thomas, 963 "LDP Specification", RFC 3036, January 2001. 965 [LFA] A. Atlas, Ed, A. Zinin, Ed, "Basic 966 Specification for IP Fast-Reroute: Loop-free 967 Alternates", 968 , 969 Feb 2006, (work in progress). 971 [MPLS-TE] Ping Pan, et al, "Fast Reroute Extensions to 972 RSVP-TE for LSP Tunnels", RFC 4090, May 2005. 974 [NNHL] Shen, N., et al "Discovering LDP Next-Nexthop 975 Labels", 976 , 977 May 2005, (work in progress) 979 [RFC2119] Bradner, S., "Key words for use in RFCs to 980 Indicate Requirement Levels", RFC 2119 981 (BCP 14), March 1997 983 Acknowledgements 985 The authors acknowledge the contributions of the following people to 986 this work:- Alia Atlas, John Harper. 988 Authors' Addresses 990 Stewart Bryant 991 Cisco Systems, 992 250, Longwater Avenue, 993 Green Park, 994 Reading, RG2 6GB, 995 United Kingdom. Email: stbryant@cisco.com 997 Stefano Previdi 998 Cisco Systems 999 Via Del Serafico, 200 1000 00142 Rome, 1001 Italy Email: sprevidi@cisco.com 1003 Mike Shand 1004 Cisco Systems, 1005 250, Longwater Avenue, 1006 Green Park, 1007 Reading, RG2 6GB, 1008 United Kingdom. Email: mshand@cisco.com