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