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