idnits 2.17.1 draft-atlas-ip-local-protect-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack an Authors' Addresses Section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 3 instances of too long lines in the document, the longest one being 9 characters in excess of 72. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 59: '... which MUST be followed. In additio...' RFC 2119 keyword, line 749: '.... By default, S MUST assume that a ne...' RFC 2119 keyword, line 815: '... following rules MUST be followed when...' RFC 2119 keyword, line 818: '...ternates, then S MUST select one of th...' RFC 2119 keyword, line 821: '...ternates, then S MUST select the alter...' (10 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 916 has weird spacing: '...primary alt...' == Line 1292 has weird spacing: '...for the purpo...' == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: For computing an alternate, a router MUST not consider diverting from the SPF tree along a link whose reverse cost is LSInfinity (for OSPF) or whose router has the overload bit set (for ISIS). == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'SHOULD not' in this paragraph: IP/LDP Local Protection does not apply to multicast traffic. The alternate next-hops SHOULD not used for multi-cast RPF checks. -- 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.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'LDP' is defined on line 1319, but no explicit reference was found in the text == Unused Reference: 'RSVP-TE' is defined on line 1322, but no explicit reference was found in the text == Unused Reference: 'RSVP-TE FRR' is defined on line 1326, but no explicit reference was found in the text == Unused Reference: 'RFC3137' is defined on line 1331, but no explicit reference was found in the text == Unused Reference: 'RFC3277' is defined on line 1334, but no explicit reference was found in the text == Unused Reference: 'ISIS' is defined on line 1337, but no explicit reference was found in the text == Unused Reference: 'RFC2966' is defined on line 1340, but no explicit reference was found in the text == Unused Reference: 'OSPF' is defined on line 1343, but no explicit reference was found in the text == Unused Reference: 'RFC2370' is defined on line 1345, but no explicit reference was found in the text == Outdated reference: A later version (-02) exists of draft-atlas-ospf-local-protect-cap-00 -- Possible downref: Normative reference to a draft: ref. 'OSPF-LOCAL-PROTECT' == Outdated reference: A later version (-02) exists of draft-martin-isis-local-protect-cap-00 -- Possible downref: Normative reference to a draft: ref. 'ISIS-LOCAL-PROTECT' ** Obsolete normative reference: RFC 3036 (ref. 'LDP') (Obsoleted by RFC 5036) == Outdated reference: A later version (-07) exists of draft-ietf-mpls-rsvp-lsp-fastreroute-04 ** Obsolete normative reference: RFC 3137 (Obsoleted by RFC 6987) ** Downref: Normative reference to an Informational RFC: RFC 3277 ** Obsolete normative reference: RFC 2966 (Obsoleted by RFC 5302) ** Obsolete normative reference: RFC 2370 (Obsoleted by RFC 5250) Summary: 12 errors (**), 0 flaws (~~), 18 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Draft Alia Atlas (Avici Systems) 3 Expires: August 2004 Raveendra Torvi (Avici Systems) 4 Gagan Choudhury (AT&T) 5 Christian Martin (Verizon) 6 Brent Imhoff (Wiltel) 7 Don Fedyk (Nortel) 9 IP/LDP Local Protection 11 draft-atlas-ip-local-protect-00.txt 13 Status of this Memo 15 This document is an Internet-Draft and is in full conformance with 16 all provisions of Section 10 of RFC2026. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as ``work in progress.'' 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 Abstract 36 This document defines an architecture and selection process for 37 providing local protection for IP unicast and/or LDP traffic in the 38 event of a single link or node failure until the router has 39 converged. When computing the primary next-hop for a prefix, a 40 router S also determines an alternate next-hop which can be used if 41 the primary next-hop fails. The alternate can be either a loop-free 42 alternate, which goes to a neighbor whose shortest path to the prefix 43 does not go back through the router S, or a U-turn alternate, which 44 goes to a neighbor whose primary next-hop to the prefix is the router 45 S, and which has itself a loop-free node-protecting alternate, which 46 thus does not go through router S to reach the destination prefix. 48 A router may indicate the capability to break U-turns on its links; 49 only such links can be used as U-turn alternate next-hops. To signal 50 this capability, a router must be capable of detecting when it 51 receives traffic for a given destination from a primary neighbor for 52 that destination and the router must forward that traffic to the 53 selected alternate next-hop. 55 To support U-Turn alternates and node-protection, a router must know 56 what links its neighbor can consider for alternates, how a neighbor 57 will select an alternate, and upon which interfaces a neighbor can 58 break U-turns. This document defines a common selection criteria 59 which MUST be followed. In addition, it is necessary to signal two 60 capabilities per link. First is whether U-turns can be broken on the 61 link and second is whether the link can be used as an alternate, as 62 determined administratively. 64 Contents 66 1 Introduction ................................................. 3 67 2 Terminology .................................................. 4 68 3 Finding an Alternate ......................................... 6 69 3.1 Types of Alternates ....................................... 6 70 3.1.1 Loop-Free Alternates ................................... 7 71 3.1.2 U-Turn Alternates ..................................... 8 72 3.1.2.1 ECMP U-Turn Neighbors ............................. 11 73 3.1.2.2 U-Turn Neighbor's Alternate ....................... 13 74 3.1.2.2.1 Computing Alternate So Primary Next-Hop Can 75 Use Computing Router for U-Turn Alternate....... 15 76 3.2 Selection of an Alternate ................................. 15 77 3.2.1 IP Local Protection Alternate Capability .............. 16 78 3.2.2 U-Turn Breaking Capability ............................ 16 79 3.2.3 Characterization of Neighbors ......................... 16 80 3.2.4 Selection Procedure ................................... 17 81 3.2.4.1 Alternate Selection With One Primary Neighbor ...... 17 82 3.2.4.2 Alternate Selection With Multiple Potential 83 Primary Neighbors .................................. 19 84 4 Using an Alternate ........................................... 19 85 4.1 Breaking U-Turns .......................................... 19 86 4.1.1 Broadcast and NBMA Interfaces ........................... 21 87 4.2 Responding to a Local Failure ............................. 22 88 5 Requirements on LDP Mechanics ................................ 23 89 6 Routing Interactions .......................................... 23 90 6.1 OSPF Inter-Area Routing ................................... 23 91 6.2 OSPF External Routing ..................................... 25 92 6.3 ISIS Multi-Level Routing .................................. 25 93 6.4 OSPF Virtual Links ........................................ 26 94 6.5 BGP Next-Hop Synchronization .............................. 26 95 6.6 Interactions with ISIS Overload, RFC 3137 96 and Costed Out Links ...................................... 26 97 6.7 Multicast Considerations .................................. 27 98 7 Security Considerations ...................................... 27 99 8 Intellectual Property Considerations ......................... 27 100 9 Full Copyright Statement ..................................... 27 101 10 References ................................................... 28 102 11 Authors Information .......................................... 29 104 1. Introduction 106 Applications such as VoIP and pseudo-wires can be very sensitive to 107 traffic loss, such as occurs when a link or router in the network 108 fails. A router's convergence time is generally on the order of 109 seconds; the application traffic may be sensitive to losses greater 110 than 10s of milliseconds. This document describes a mechanism to 111 allow a router whose local link has failed to forward traffic to a 112 pre-computed alternate until the router installs the new primary 113 next-hops based upon the changed network topology. 115 When a local link fails, a router currently must signal the event to 116 its neighbors via the IGP, recompute new primary next-hops for all 117 affected prefixes, and only then install those new primary next-hops 118 into the forwarding plane. Until the new primary next-hops are 119 installed, traffic directed towards the affected prefixes is 120 discarded. This process can take seconds. 122 /__ 123 \ +-----+ 124 /------| S |--\ 125 / +-----+ \ 126 / 5 8 \ 127 / \ 128 +-----+ +-----+ 129 | P | | N_1 | 130 +-----+ +-----+ 131 \ / 132 \ \ 4 3 / / 133 \| \ / |/ 134 -+ \ +-----+ / +- 135 \---| D |---/ 136 +-----+ 138 Figure 1: Basic Topology 140 The goal of IP/LDP Local Protection is to reduce that traffic 141 convergence time to 10s of milliseconds by using a pre-computed 142 alternate interface, in the event that the currently selected primary 143 interface fails, so that the alternate can be rapidly used when the 144 failure is detected. 146 To clarify the behavior of IP/LDP Local Protection, consider the 147 simple topology in Figure 1. When router S computes its shortest 148 path to router D, router S determines to use the interface to router 149 P as its primary next-hop. Without IP/LDP Local Protection, that is 150 the only next-hop that router S computes to reach D. With IP/LDP 151 Local Protection, S also looks for an alternate next-hop to use. In 152 this example, S would determine that it could send traffic destined 153 to D by using the interface to router N_1 and therefore S would 154 install the interface to N_1 as its alternate next-hop. At some 155 point later, the link between router S and router P could fail. If 156 that link fails, S (and most likely P) will be the first to detect 157 it. On detecting the failure, S will stop sending traffic destined 158 to D towards P via the failed link, and instead send the traffic to 159 S's pre-computed alternate next-hop, which is the interface to N_1, 160 until a new SPF is run and its results are installed. As with the 161 primary next-hop, the alternate next-hop is computed for each 162 destination. The process of computing an alternate next-hop does not 163 alter the primary next-hop computed via a standard SPF. The 164 alternate next-hop can protect against a single link or node failure. 166 If in the example of Figure 1, the link cost from N_1 to D increased 167 to 30 from 3, then N_1 would not be a loop-free alternate, because 168 the cost of the path from N_1 to D via S would be 17 while the cost 169 from N_1 directly to D would be 30. In real networks, we may often 170 face this situation. In the modified example, N_1 has a loop-free 171 node-protecting alternate to reach D; N_1 can reach D directly. If S 172 could use N_1 in such a scenario, then the topologies where there are 173 acceptable alternates could increase. Such an alternate is termed a 174 U-turn alternate; S sends to a neighbor N_1 whose primary neighbor 175 for that traffic is S. N_1 detects this situation and rather than 176 forwarding the traffic back to S, in a U-turn loop, N_1 breaks the 177 U-Turn and forwards the traffic to N_1's alternate. 179 The existence of a suitable alternate next-hop is topology dependent; 180 in real networks, the addition of U-Turn alternates has substantially 181 improved the coverage of alternates for the source/destination pairs 182 in those networks over that available with only loop-free alternates. 184 2. Terminology 186 SPT --- Shortest Path Tree 187 D --- The destination router under discussion. 189 S --- The source router under discussion. It is the viewpoint from 190 which IP/LDP Local Protection is described. 192 P --- The router which is the primary next-hop neighbor to get from S 193 to D. Where there is an ECMP set for the shortest path from S 194 to D, these will be referred to as P_1, P_2, etc. 196 N_i --- The ith neighbor of S 198 R_i_j --- The jth neighbor of N_i, the ith neighbor of S. 200 Distance_!S(N_i, D) --- The distance of the shortest path from N_i to 201 D which does not go through router S. 203 Distance_opt(A, B) --- The distance of the shortest path from A to B. 205 Reverse Distance of a node X --- This is the Distance_opt(X, S). 207 Loop-Free Alternate --- This is a next-hop that is not a primary 208 next-hop whose shortest path to the destination from the 209 alternate neighbor does not go back through the router S. 211 U-Turn Alternate --- This is an alternate next-hop of S that goes to 212 a neighbor N_i, whose primary next-hop is S, and whose 213 alternate is loop-free with respect to S and N_i. In other 214 words, this is an alternate that would normally loop traffic 215 back to the source (S), but which itself has an alternate that 216 does not loop back to the source (S). 218 Link(A->B) --- A link connecting router A to router B. 220 ____\ This is an arrow indicating the primary next-hop towards D. 221 / 223 @@@@\ This is an arrow indicating the alternate next-hop towards D 224 / 226 Primary Neighbor --- One or more of the primary next-hops for S to 227 reach the destination D goes directly to this neighbor. 229 Loop-Free Neighbor --- A Neighbor N_i which is not the primary 230 neighbor and whose shortest path to D does not go through S. 232 U-Turn Neighbor --- A neighbor N_i is a U-Turn neighbor of router S 233 with respect to a given destination D if and only if S is a 234 primary neighbor of N_i to reach the destination D for all 235 primary paths which go through S to reach D. 237 ECMP U-Turn Neighbor --- A neighbor N_i which is a U-Turn neighbor 238 and which has at least one equal cost path to reach D that does 239 not go through S as well as the path(s) which do go through S to 240 reach D. 242 Looping Neighbor --- A neighbor N_i is a looping neighbor of router S 243 with respect to a given destination D if any of N_i's optimal 244 paths to D goes through S, but S is not the primary next-hop of 245 N_i for all those paths through S. 247 Loop-Free Node-Protecting Alternate --- This is a path via a Loop- 248 Free Neighbor N_i which does not go through the particular 249 primary neighbor of S which is being protected to reach the 250 destination D. 252 Loop-Free Link-Protecting Alternate --- This is a path via a Loop- 253 Free Neighbor N_i which does go through the particular primary 254 neighbor of S which is being protected to reach the destination 255 D. 257 U-Turn Node-Protecting Alternate --- This is a path via a U-Turn 258 Neighbor N_i which does not go through S or any of S's primary 259 neighbors to reach the destination D. 261 U-Turn Link-Protecting Alternate --- This is a path via a U-Turn 262 Neighbor N_i which does not go through S but does go through one 263 or more of S's primary neighbors to reach the destination D. 265 Upstream Forwarding Loop --- This is a forwarding loop which involves 266 a set of routers, none of which are directly connected to the 267 link which has caused the topology change that triggered a new 268 SPF in any of the routers. 270 3. Finding an Alternate 272 3.1. Types of Alternates 274 As with primary next-hops, an alternate next-hop is discussed in 275 relation to a particular destination router D. For this discussion, 276 the following terminology, illustrated in Figure 2, will be used. 277 The router on which the search for an alternate is proceeding is S. 278 The primary next-hop neighbor to get from S to D is P. Additionally, 279 S has various neighbors which will be labeled N_1, N_2, etc. Where 280 an arbitrary neighbor of S is intended, N_i will be used. Routers 281 which are neighbors of neighbors will be labeled R_1, R_2, etc. 283 Where an arbitrary neighbor of a neighbor N_i is intended, it will be 284 refered to as R_i_j. 286 In IP routing, a router S can join the shortest path tree (SPT) at 287 exactly one point -- itself. An alternate next-hop allows traffic 288 from S to D to deviate from the SPT and then rejoin it. For 289 instance, if S were to send traffic destined for D to N_1 instead of 290 P, thereby deviating from the SPT, then when N_1 received it, N_1 291 would send that traffic along its shortest path to D. 293 +-----+ 294 \ / _| R_2 | 295 +-----+__ \| |/ / +-----+ 296 | N_3 | \ -+ +- __/ \ 297 +-----+ \____ / \ 298 \ \ / \ 299 \ +-----+ \ 300 \ _| N_2 | \ 301 | __/ +-----+ \ 302 \ / \ | 303 \ / / \_ | 304 +-----+ |/ \ | 305 | S | +- \ +-----+ | 306 +-----+ \_| R_1 | | 307 / / \ +-----+ | 308 |/ / \ / | 309 +- / \ / | 310 / +-----+ / / | 311 +-----+/ | N_1 | / |/ | 312 | P | +-----+ / +- | 313 +-----+ \ / / 314 \ \ \__ / / 315 \ \ \| \ / / 316 \| \ -+ +-----+ / 317 -+ \_________________| D |---------/ 318 +-----+ 320 Figure 2: Topology for Terminology 322 3.1.1. Loop-Free Alternates 324 To expand the set of points at which S can cause its traffic to join 325 the SPT, first consider S's neighbors. Router S has the ability to 326 send traffic to any one of its neighbors N_i; this is the easiest 327 possible deviation from the SPT that S can cause to happen. Thus, 328 all of router S's neighbors are possible points at which S could 329 cause traffic to rejoin the SPT. However, it is not useful for 330 router S to use a next-hop which results in rejoining the SPT 331 upstream of S, such that the traffic will transit S again. This 332 would cause a loop. Avoiding a loop is thus the first constraint 333 imposed on the alternate next-hop. In Figure 2, this is the case 334 for S's neighbors N_2 and N_3. 336 A next-hop which goes to a neighbor that does not have a loop back to 337 S and is not the primary next-hop may be selected as an alternate 338 next-hop. In Figure 2, that is the case for S's neighbor N_1. Such 339 alternates are referred to as loop-free alternates because there is 340 no loop caused by using them. 342 An algorithm run on router S must be able to determine which 343 neighbors provide loop-free alternates. By running an SPF 344 computation from S's perspective, router S can determine the distance 345 from a neighbor N_i to the destination D for the optimal path that 346 does not go through S. This is referred to as Distance_!S(N_i, D). 347 If a neighbor N_i can provide a loop-free alternate, then it is 348 cheaper to get to the destination without going through S than by 349 going through S. This gives the following requirement, where 350 Distance_opt(A, B) gives the distance of the optimal path from A to 351 B. 353 Distance_!S(N_i, D) < Distance_opt(N_i, S) + Distance_opt(S, D) 355 Equation 1: Criteria for a Loop-Free Alternate 357 Recall that a router will take the shortest path to a destination 358 that it can see. Thus, if Distance_!S(N_i, D) > Distance_opt(N_i, S) 359 + Distance_opt(S, D), then router N_i will, based on its own shortest 360 path computations, determine to send traffic destined for D to S. 361 Similarly, if Distance_!S(N_i, D) = Distance_opt(N_i, S) + 362 Distance_opt(S, D), then router N_i has equal cost paths to the 363 destination D where one or more of those paths go through S. In such 364 a case where a router N_i has an ECMP set to reach the destination 365 and one or more paths go through S, then the router N_i cannot 366 provide a loop-free alternate because some traffic destined to D may 367 be sent back to S by N_i. Thus, if N_i is to decide not to send 368 traffic for D back to S, N_i must observe that the shortest path to D 369 does not go through S; Equation 1 gives this requirement in terms 370 which can be determined by router S. 372 3.1.2. U-Turn Alternates 374 In examining realistic networks, it was seen that loop-free 375 alternates did not provide adequate coverage for the traffic between 376 all the source-destination pairs. This means that it is not 377 sufficient to expand the set of points where S can cause its traffic 378 to join the SPT to be only S's neighbors. 380 The next possibility is to see whether S could expand its SPT join 381 points to include router S's neighbors' neighbors. This is only of 382 interest if S had no loop-free node-protecting alternate available 383 for the given destination D. If there are no loop-free alternates, 384 that implies that all of S's non-primary neighbors will send traffic 385 for D back to S. 387 The topology shown in Figure 3 gives an example where router S has no 388 loop-free alternate to reach D. Router S uses P as its primary 389 next-hop (distance of 30). S has three other neighbors, but all of 390 them will send traffic for D back through S. 392 +-----+ \ 393 | N_4 |\ \| / +-----+ 394 +-----+ \ -+ |/ /| R_3 | 395 / \ +- / +-----+ 396 / 15 | _/ | 397 | | 5 / | 398 | 50 \ / | 399 +-----+ | +-----+ | 400 | N_2 | / ______/| N_3 | | 401 +-----+ \ / / +-----+ 70 | 402 | \ \| / / 30 / | 403 10| \ -+ / / |/ | 404 | 15 \ +-----+ +- | 405 @ | \-----| S | | 406 @ | / +-----+ | 407 \@/ | @@@@ | | 408 | \ | |10 / 409 | | | / 410 +-----+ \_/ | / 411 | R_2 | +-----+ / 412 +-----+ | P | / 413 \ +-----+ / 414 \ \ 40 / / 415 \| \ 10 / / / 416 -+ \ / |/ / 417 +-----+ / +- / 418 | R_1 |---/ / 419 +-----+ / 420 \ 10 +-----+ 421 \ \------------------| D | 422 \| +-----+ 423 -+ 425 P is primary next-hop of S 426 N_2 and N_3 are U-Turn Neighbors of S 427 N_4 is a Looping Neighbor of S 429 Figure 3: Terminology of Looping Neighbors and Example U-Turn Alternate 431 In order for S to be able to use a neighbor's neighbor as a point 432 where S's traffic can rejoin the SPT, S must be able to direct 433 traffic to a neighbor N_i and that neighbor N_i must be able to 434 direct traffic to one of its appropriate neighbors R_i_j instead of 435 along the SPT. In deciding to use its alternate, S has the ability 436 to force traffic destined to D to go through the selected alternate 437 neighbor N_i. However, for S to reach the appropriate neighbor's 438 neighbor R_i_j, the selected neighbor N_i must be able to detect 439 that the traffic should not be sent along its shortest path to D, 440 which would lead back to S, and should instead be sent to its 441 appropriate neighbor R_i_j. 443 This detection and forwarding contrary to the SPT by N_i must occur 444 without any communication from S upon the failure which would cause S 445 to redirect the traffic to N_i. There is already communication from 446 S to N_i indicating when a link has failed, but such communication 447 would cause the fail-over of traffic to take longer than the desired 448 10s of milliseconds if N_i depended upon it to decide that it should 449 forward contrary to the SPT. In essence, the assumption being made 450 is that the time budget to recover traffic in the event of a failure 451 is being consumed by router S's detection of the failure and switch- 452 over to its pre-computed alternate. 454 With that assumption, it is clear that N_i's behavior to forward 455 traffic contrary to the SPT on receiving traffic from S must be a 456 default behavior. This default behavior must not change how traffic 457 is forwarded unless a forwarding loop is detected; basic IP 458 forwarding must be preserved in the absence of a failure. Router N_i 459 can detect if it is receiving traffic from a neighbor to whom it 460 would forward that traffic; this detection is done via a reverse 461 forwarding check. Such a reverse forwarding check should consider 462 not only if traffic is received on the same interface as it would be 463 forwarded out, but whether it was received from the same neighbor to 464 whom it would be forwarded. Normally, if traffic fails a reverse 465 forwarding check (i.e. would be forwarded out to the same neighbor as 466 received from), then that traffic is either discarded or forwarded 467 into a loop. In IP/LDP Local Protection, however, traffic that fails 468 a reverse forwarding check is forwarded to the appropriate R_i_j, if 469 available, rather than being discarded. 471 First, this detection can be used by N_i to determine not to forward 472 the traffic according to the SPT (or discard it), but to instead send 473 the traffic to N_i's appropriate neighbor R_i_j. N_i can only detect 474 the traffic to be redirected if S sends it directly to N_i, which is 475 under S's control, and if N_i would send that traffic back to S, 476 according to the SPT. This motivates the definition of a Looping 477 Neighbor and a U-turn Neighbor. 479 Looping Neighbor --- A neighbor N_i is a looping neighbor of 480 router S with respect to a given 481 destination D if any of N_i's shortest 482 paths to D goes through S but S is not the 483 primary next-hop of N_i for all those 484 paths through S. 486 U-Turn Neighbor --- A neighbor N_i is a U-Turn Neighbor of 487 router S with respect to a given destination 488 D if and only if S is a primary next-hop of 489 N_i to reach the destination D for all 490 primary paths which go through S to reach D. 492 A Looping Neighbor cannot provide any type of alternate. A U-Turn 493 neighbor may be able to provide an alternate. In Figure 3, S has two 494 U-Turn Neighbors N_2 and N_3 and one looping neighbor N_4. For 495 neighbor N_4, the path to D is N_3 to S to N_1 to R_1 to D; because 496 there is a node between N4 and S on the path, N_4 is a looping 497 neighbor. 499 Mathematically, for a neighbor N_i to be a U-Turn neighbor, it is 500 necessary that Equation 2, which is the exact opposite of Equation 1, 501 be true. If the equality is true, that means that there are multiple 502 optimal paths, at least one of which goes through S and one does not. 503 Such a neighbor may be an ECMP U-Turn neighbor or may be a looping 504 neighbor. 506 Distance_!S(N_i, D) >= Distance_opt(N_i, S) + Distance_opt(S, D) 508 Equation 2: U-Turn or Looping Neighbor 510 Additionally, all optimal paths to reach D that go via S must be via 511 a direct link between N_i and S. If a neighbor N_i satisfies 512 Equation 2 and all optimal paths to reach D that go via S are via a 513 direct link between N_i and S, then it is a U-turn neighbor. 515 The above clarifies what a U-Turn neighbor is and how such a neighbor 516 can detect traffic from router S and redirect it. It is still 517 necessary to describe where the U-Turn neigbhor N_i redirects the 518 traffic. 520 3.1.2.1. ECMP U-Turn Neighbors 522 The above definition for U-Turn Neighbor allows a neighbor, which has 523 equal cost paths (an ECMP set) where one of those paths goes directly 524 to S and others may not, to be a U-Turn Neighbor. Consider the 525 topology shown in Figure 4. In this figure, N_1 has three equal-cost 526 paths to reach D which are N_1 - S - P - D, N_1 - R_1 - D, and N_1 - 527 R_2 - D. Because the only path that goes through S goes directly 528 through S, N_1 is a U-Turn neighbor of S. 530 +-----+------\ 531 /--| N_1 | 5 \ 532 / / +-----+\ \ +-----+ 533 |/ / 10 \ \ 15 \------| R_3 | 534 +- / 10 \ \ +-----+ 535 / | \ \ | 536 +-----+ | | \ \| | 537 | S | \|/ | \ -+ | | 538 +-----+ | \ | \|/ 539 / +-----+ \ | 540 / / 10 | R_1 | \ 15| 541 |/ / +-----+ \ | 542 +- / / / +-----+ | 543 / |/ / 20 | R_2 | | 544 +-----+ +- / +-----+ | 545 | P | | /__ 15 / | 546 +-----+ | \ / | 547 \ | /-------/ +-----+ 548 \ \ 10 | / | X | 549 \| \ | / /__ +-----+ 550 -+ \ +-----+ \ / 15 551 \------| D |-------------------/ 552 +-----+ 554 Figure 4: ECMP U-Turn Neighbor 556 Distance_!S(N_i, D) = Distance_opt(N_i, S) + Distance_opt(S, D) 558 Equation 3: ECMP Neighbor 560 A neighbor is an ECMP neighbor if Equation 3 is true. The 561 complication comes because S does not know whether a neighbor N_i 562 supports ECMP or how that neighbor selects among the equal cost 563 paths. Recall that a node will only break U-Turns on the interfaces 564 connected to that node's primary neighbors. 566 Consider the topology in Figure 5, where N_2 has three equal cost 567 primary neighbors which are S, N_1 and R_1. If N_2 were to select 568 only N_1 as its primary neighbor, then N_2 would break U-Turns only 569 on traffic received from N_1 and not on traffic received from S. 570 Therefore, S cannot consider N_2 as an ECMP U-Turn neighbor because S 571 cannot rely upon N_2 to break U-turns for traffic destined to D which 572 is received from S. 574 If N_2 has multiple paths to reach D which go through S and not all 575 such paths have a first hop which is a direct link between N_2 and S, 576 then S cannot use N_2 as a U-Turn neighbor. 578 10 +-----+ 579 / /--------------| N_2 |\ \ 580 |/ / +-----+ \ \| 581 +- / /----/ 5 \ -+ 582 / / / \ 583 / 5 +-----+ |/ | 584 / /----| N_1 | +- | 15 585 +-----+ / +-----+ | 586 | S |/ / +-----+ 587 +-----+ |/ | R_1 | 588 / / +- +-----+ 589 |/ / 5 / 590 +- / / 15 591 +-----+ /--------/ 592 | P | / 593 +-----+ / / 594 \ / |/ 595 \ \ 5 +-----+ / +- 596 \| \-------------| D |/ 597 -+ +-----+ 599 Figure 5: ECMP Neighbor Which is Not an ECMP U-Turn Neighbor 601 If all paths from an ECMP neighbor N_i to destination D which go via 602 S have S as the primary neighbor, then S can use N_2 as a ECMP U-Turn 603 neighbor. 605 3.1.2.2. U-Turn Neighbor's Alternate 607 The requirement for the neighbor's neighbor R_i_j to which a U-Turn 608 Neighbor N_i will redirect traffic from S destined to D is that the 609 traffic not come back to S. Equation 4 gives this requirement that 610 R_i_j must have a path to D that does not go through S which is 611 shorter than the path to D going via S. This can be expressed as 612 follows. 614 Distance_!S(R_i_j, D) < Distance_opt(R_i_j, S) + Distance_opt(S, D) 616 Equation 4: Loop-Free Neighbor's Neighbor 618 Equation 4 means that a U-Turn neighbor's alternate cannot be an ECMP 619 set which contains that U-Turn neighbor. 621 If N_i is a U-Turn neighbor, then the optimal path to D from N_i is 622 via S; the path is N_i - S - ... - D. Therefore, if the optimal path 623 from R_i_j goes through N_i, it must also go through S. Thus, if 624 Equation 4 holds for a R_i_j, that implies that the path from R_i_j 625 does not go through N_i. This may be made clearer by considering 626 Figure 6 below. If the shortest path from R_1 to D went through N_1, 627 then it would go through S as well, because the shortest path from 628 N_1 to D is through S. Therefore, if the shortest path from R_1 does 629 not go through S, it cannot have gone through N_1. 631 5 +-----+ @ 632 / /--------------| N_2 |\ @ 633 |/ / +-----+ \ \@/ 634 +- / /@\ \ 635 / @ \ 636 / @ | 637 / | 15 638 +-----+ | 639 | S | +-----+ 640 +-----+ | R_1 | 641 / / +-----+ 642 |/ / 5 / 643 +- / / 5 644 +-----+ /--------/ 645 | P | / 646 +-----+ / / 647 \ / |/ 648 \ \ 5 +-----+ / +- 649 \| \-------------| D |/ 650 -+ +-----+ 652 Figure 6: U-Turn Alternate Example 654 If the optimal path from Ri,j to D goes through N_i, then 655 Distance_!S(R_i_j, D) >= Distance_opt(R_i_j, N_i) + 656 Distance_opt(N_i, D) 657 Because N_i is a U-Turn neighbor, the shortest path to D is via S: 658 Distance_opt(N_i, D) = Distance_opt(N_i, S) + Distance_opt(S, D) 660 The previous two equations can be combined to form the following: 661 Distance_!S(R_i_j , D) >= Distance_opt(R_i_j, N_i) + 662 Distance_opt(N_i, S) + Distance_opt(S, D) 664 Because Distance_opt(R_i_j, S) is the minimum distance of a path to 665 get from R_i_j to S, the path to do so via N_i cannot have a lower 666 distance. 667 Distance_opt(R_i_j, S) <= Distance_opt(R_i_j, N_i) + 668 Distance_opt(N_i, S) 670 This can be combined with the previous equation to yield 671 Distance_!S(R_i_j, D) >= Distance_opt(R_i_j, S) + Distance_opt(S,D) 673 This equation is the opposite of Equation 4. Thus, if Equation 4 674 is true, then the optimal path from R_i_j to D does not go through 675 N_i. 677 Proof 1: Proof that a Loop-Free R_i_j (Neighbor's Neighbor) 678 Implies R_i_j Doesn't Loop to Neighbor N_i 680 The proof given in Proof 1 means that if a U-Turn Neighbor N_i has 681 itself a neighbor R_i_j that satisfies Equation 4, then that router 682 R_i_j is itself a loop-free alternate with respect to N_i. 683 Regrettably, the converse does not apply; just because R_i_j is 684 loop-free with respect to N_i and D does not mean that R_i_j is 685 loop-free with respect to S and D. 687 3.1.2.2.1. Computing Alternate So Primary Next-Hop Can Use Computing 688 Router for U-Turn Alternate 690 Each router independently computes the alternate that it will select. 691 It is necessary to consider what alternate S could select so that S's 692 primary next-hop P could use S as a U-Turn alternate. In other 693 words, consider the computation when S is in the role of a neighbor 694 to the router doing the computation. 696 To describe this using router S as the computing router, S would need 697 to verify that both Equation 1 is true and that S's selected 698 alternate N_i does not have a path that goes through P. 700 This can be described as if N_i were doing the computation as 701 follows. The criteria described in Equation 4 requires that if a U- 702 Turn neighbor N_i is to be used as a U-Turn alternate then N_i must 703 have a loop-free alternate which avoids N_i's primary neighbor S. 704 Such an alternate will be referred to as a loop-free node-protecting 705 alternate. N_i can identify loop-free alternates by checking the 706 validity of Equation 5. Additionally, N_i will need to tell whether 707 the path from a loop-free R_i_j to D goes through N_i's primary 708 next-hop neighbor, S. 710 Distance_!S(R_i_j, D) < Distance_opt(R_i_j, N_i) + 711 Distance_opt(N_i, D) 713 Equation 5: Neighbor's Loop-Free Alternate 715 3.2. Selection of an Alternate 717 All routers that supports breaking U-Turns for IP/LDP Local 718 Protection must follow common alternate selection criteria. For a 719 node S to use a U-Turn neighbor N_u for a U-turn alternate, S must 720 know not only that N_u has an acceptable loop-free node-protecting 721 alternate but that N_u can and will use it. For S to be able to 722 provide node-protection via a U-Turn alternate, S must know how N_u 723 will select among the loop-free node-protecting alternates which are 724 available. 726 3.2.1. IP Local Protectection Alternate Capability 728 There are a number of different reasons why an operator may not wish 729 for a particular interface to be used as an alternate. For instance, 730 the interface may go to an edge router or the interface may not have 731 sufficient bandwidth to contain the traffic which would be put on it 732 in the event of failure. 734 Because a router's neighbors may desire to use that router to provide 735 a U-turn alternate, a router must flood to its neighbors which 736 interfaces are not capable of providing alternates. This information 737 allows a router's neighbors to accurately determine whether or not 738 the router has a loop-free node-protecting alternate. 740 The extensions to signal this local-protection alternate capability 741 are described in [OSPF-LOCAL-PROTECT] and [ISIS-LOCAL-PROTECT]. 743 3.2.2. U-Turn Breaking Capability 745 A router S may only use its neighbor N_u as a U-Turn alternate if N_u 746 indicates that it is capable of breaking U-Turns on a link between S 747 and N_u. The capability to break U-Turns must be signaled for a link 748 in order for S to determine that it can use N_u as a U-Turn 749 alternate. By default, S MUST assume that a neighbor cannot provide 750 a U-Turn alternate unless that neighbor indicates the U-Turn breaking 751 capability on a link between S and N_u. This U-Turn breaking 752 capability need only be flooded to a node's neighbors. 754 The extensions to signal the U-turn breaking capability are also 755 described in [OSPF-LOCAL-PROTECT] and [ISIS-LOCAL-PROTECT]. 757 3.2.3 Characterization of Neighbors 759 Conceptually, each neighbor N_i is categorized as to the type of path 760 which it can provide to a particular destination D. Each neighbor 761 can be characterized as providing a path in one of the following 762 categories for a particular destination D. The path through the 763 neighbor N_i is either a: 765 (A) Primary Path --- one of the shortest paths that is selected 766 as a primary next-hop, 768 (B) Loop-Free Node-Protecting Alternate --- not a primary path 769 and the path avoids both S, the interfaces connecting S to its 770 primary neighbors, and its primary neighbors on the path to D. 772 (C) Loop-Free Link-Protecting Alternate --- not a primary path 773 and the path avoids S and the interfaces connecting S to its 774 primary neighbors, but goes through a primary neighbor on the 775 path to D. 777 (D) U-Turn Node-Protecting Alternate --- the neighbor is a U- 778 Turn neighbor or a ECMP U-Turn neighbor and the alternate that 779 the neighbor has selected does not go through a primary neighbor 780 of S to reach D. 782 (E) U-Turn Link-Protecting Alternate --- the neighbor is a U- 783 Turn neighbor or a ECMP U-Turn neighbor and the alternate that 784 the neighbor has selected goes through a primary neighbor of S 785 to reach D. 787 (F) Unavailable --- because the neighbor is looping or a U-Turn 788 neighbor which didn't itself have a loop-free node-protecting 789 path, or a U-Turn neighbor which couldn't break U-Turns or the 790 links to the neighbor are configured to not be used as 791 alternates. The neighbor may also be disqualified because it is 792 connected to S solely via broadcast interfaces which also have 793 primary next-hops. 795 3.2.4. Selection Procedure 797 Once the neighbors have been categorized, a selection can be made. 798 The selection should maximize the failures which can be protected 799 against. A node S can only be used to break U-turns by its primary 800 neighbors if S has a loop-free node-protecting alternate. 802 The selection procedure depends on whether S has a single potential 803 primary neighbor or multiple potential primary neighbors. A router S 804 is defined to have a single potential primary neighbor only if there 805 are no equal cost paths that go through any other neighbor; i.e., a 806 router S cannot be considered to have a single potential primary 807 neighbor just because S does not support ECMP or just because S 808 selects as primary next-hops links to only one potential primary 809 neighbor. 811 3.2.4.1. Alternate Selection With One Primary Neighbor 813 Because a router S can only be used to break U-Turns by its primary 814 neighbor if S selects a loop-free node-protecting alternate, the 815 following rules MUST be followed when selecting an alternate. 817 1. If a router S has one or more loop-free node protecting 818 alternates, then S MUST select one of those alternates. Let M be 819 the set of neighbors which provide loop-free node-protecting 820 alternates. If S has multiple loop-free node protecting 821 alternates, then S MUST select the alternate through a N_k such 822 that: 824 D_!S(N_k, D) - D_opt(N_k, P) = min_forall m in M 825 (D_!S(m, D) - D_opt(m, P)) 827 Equation 6: Selection Among Multiple Loop-Free 828 Node-Protecting Alternates 830 where P is the primary neighbor of S. 832 To rephrase the above to consider the S is the node looking for 833 a U-Turn alternate, the above way of selecting among loop-free 834 node-protecting alternates ensures that N_i's primary neighbor S 835 can determine which alternate was picked by N_i. For S to know 836 that S's U-Turn neighbor N_i can provide a loop-free node- 837 protecting alternate, S must know if 839 min_forall j in J ( D_!S(R_i_j, D) - D_opt(R_i_j, S) ) 840 < D_opt(S, D) 842 Equation 7: Determination if a U-Turn Neighbor 843 can provide a U-Turn Alternate 845 If a router obeys Equation 6 when selecting among multiple 846 loop-free node-protecting alternates, as it MUST for IP/LDP 847 Local Protection, this allows S to determine exactly which 848 alternate was selected by N_i without needing to know the each 849 D_!S(R_i_j). Equation 7 allows S to determine that N_i has a 850 loop-free node-protecting alternate. Equation 6 allows S to 851 know exactly which alternate will be selected so that S can 852 determine whether that alternate protects against S's primary 853 neighbor as well. If there are multiple neighbors which provide 854 the minimum as expressed in Equation 6, then a router can select 855 among them arbitrarily. 857 2. If a router S has no loop-free node-protecting alternates, 858 then S's alternate selection has no consequences for its 859 neighbors because S cannot provide a U-Turn alternate. 860 Therefore, S can select freely among the loop-free link- 861 protecting alternates, u-turn node-protecting alternates and u- 862 turn link protecting alternates which S has available. Clearly 863 selecting a u-turn node-protecting alternate, if one is 864 available, will provide node-protection, while the other options 865 will not. Selection among these categories is a router-local 866 decision. 868 3. If S has neither loop-free node-protecting alternates, 869 loop-free link-protecting alternates, u-turn node-protecting 870 alternates, nor u-turn link-protecting alternates, then S has no 871 alternate available for traffic to the destination D from the 872 source S. 874 3.2.4.2. Alternate Selection With Multiple Potential Primary Neighbors 876 The selection among multiple equal cost paths is a router-local 877 decision. Therefore, a router N_i cannot know which of the potential 878 primary neighbors that S will choose to use. 880 As described in Section 3.1.2.1, N_i can only select S for its U-Turn 881 alternate if any potential primary neighbor which S might select, 882 except for N_i itself, will not go via N_i to reach the destination 883 D. 885 Since a router S has multiple potential primary neighbors, router S 886 MUST select one or more alternates for breaking U-Turns from among 887 next-hops to its potential primary neighbors. If router S does not 888 have a potential primary neighbor that is node-protecting for a 889 particular primary next-hop, that indicates that the particular 890 primary neighbor will not use S as a U-turn alternate. 892 Router S need not use the same alternate(s) for breaking U-Turns on 893 traffic received from a primary next-hop as for when the primary 894 next-hop fails. The alternate(s) used when a primary next-hop fails 895 are a router-local decision. 897 4. Using an Alternate 899 If an alternate is available, it is used in two circumstances. In 900 the first circumstance, it is used to redirect traffic received from 901 a primary next-hop neighbor. In the second circumstance, it is used 902 to redirect traffic when the primary next-hop has failed. As 903 mentioned in Section 3.2.4.2, for destinations with multiple 904 potential primary neighbors, the alternates used for each purpose 905 need not be the same. 907 4.1. Breaking U-Turns 909 If one ignores potential security redirection, IP forwarding is a 910 purely destination based algorithm. Traffic is forwarded based upon 911 the destination IP address, regardless of the incoming interface. 913 +--------------------------+ 914 | N_1 | 915 | | 916 | primary alternate | 917 | D: S R_1 | 918 | C: R_1 R_2 | 919 | | 920 |--------+--------+--------| 921 | D: R_1 | D: S | D: S | 922 | C: R_1 | C: R_1 | C: R_2 | 923 +--------------------------+ 924 / | \ 925 / L_1 | L_2 \ L_3 926 / | \ 927 / +-----+ \ 928 +-----+ | R_2 | \ 929 | S | +-----+ +-----+ 930 +-----+ / | R_1 | 931 / / +-----+ 932 / / / 933 / / / 934 +-----+ / /--------/ 935 | P | / / 936 +-----+ __ / __ / 937 \ / \ / \ / 938 \ / \/ \ / 939 \------ | | 940 \ CLOUD / 941 _/ | 942 / | 943 \_ ___ / 944 /\_/ \_/ 945 / \ 946 / \ 947 / +-----+ 948 +-----+ | D | 949 | C | +-----+ 950 +-----+ 952 Figure 7: Example Forwarding Table 954 As previously described in Section 3.1.2, IP/LDP Local Protection 955 requires that a U-Turn neighbor be capable of detecting traffic 956 coming from the primary next-hop neighbor and redirecting it to the 957 alternate, if an alternate which is node-protecting is available. 959 This becomes the new default behavior. This behavior is described 960 below. A router which indicates that it is capable of breaking U- 961 Turns on an interface MUST obey the following behavior on that 962 interface. 964 For an IP destination 965 If the packet was received on an interface connected 966 to a primary neighbor 967 then if the interface is U-Turn Breaking Capable 968 then if that primary next-hop has a loop-free 969 node-protecting alternate 970 then forward the packet to that alternate 971 else if interface is point-to-point 972 then discard 973 else if interface is configured for ICMP redirection 974 then forward to primary and 975 send ICMP redirect according to RFC 792 976 else discard 977 else forward to a primary next-hop 978 else forward to a primary next-hop 980 New Forwarding Rule 982 To clarify the above behavior, consider the example below in Figure 983 7. In this case, router N_1 has a primary and an alternate for two 984 destinations D and C. The primary next-hop for destination D is 985 router S and the alternate next-hop is R_1. Similarly, the primary 986 next-hop for destination C is router R_1 and the alternate next-hop 987 is R_2. The three interfaces L_1, L_2, and L_3 shown on router N_1 988 have different forwarding tables as shown in Figure 7; additional 989 interfaces would have the same forwarding table as for interface L_2, 990 which is not a primary next-hop for either destination. 992 4.1.1. Broadcast and NBMA Interfaces 994 With broadcast interfaces (i.e. Gigabit Ethernet) and NBMA 995 interfaces, there can be multiple neighbors connected to the same 996 interface. The NBMA and broadcast interfaces can be treated 997 identically for IP/LDP Local Protection. 999 It is extremely desirable to have at most one forwarding table per 1000 interface. Therefore, it must be considered whether all traffic 1001 received on an interface can be treated identically, regardless of 1002 the neighbor sourcing the traffic on that interface. 1004 The cost for any node on the broadcast interface to reach S or P will 1005 be identical. Because all link costs are positive, no neighbor on 1006 the broadcast interface will ever send traffic to S along that 1007 interface in order to reach P. Therefore, S can assume that any 1008 traffic received on the broadcast interface which goes to a 1009 destination via a primary next-hop neighbor that is also on the 1010 broadcast interface is in fact sent by that primary next-hop neighbor 1011 and should be redirected to break the U-Turn. 1013 +-----------+-----------+------------+----------+ 1014 | | | | | 1015 | | /P\ | /P\ | /P\ | /P\ 1016 | 2 3| | 3| | 4| | 5| | 1017 | | | | | 1018 +-----+ +-----+ +-----+ +-----+ +-----+ 1019 | P | | S | | N_1 | | N_2 | | N_3 | 1020 +-----+ +-----+ +-----+ +-----+ +-----+ 1021 \ \ 10 1022 \ \ 10 @ \________ 1023 \| \ @| \ 1024 -+ \ -+ +-----+ 1025 \ ________| N_4 | 1026 \ / 10 +-----+ 1027 +-----+ / 1028 | D |/ 1029 +-----+ 1031 Figure 8: Topology With Broadcast Interface 1033 Thus, if router S has a primary next-hop neighbor for a given prefix 1034 on the broadcast interface, S should redirect all traffic received 1035 destined to that prefix on the broadcast interface to S's alternate 1036 next-hop. 1038 This does assume that all neighbors on a broadcast interface are 1039 routers or are properly configured hosts. If this assumption is 1040 acceptable for a particular broadcast or NBMA interface, then traffic 1041 received on the interface, which is configured to be U-turn capable, 1042 for which there is no loop-free node-protecting alternate will be 1043 discarded. If this assumption is not acceptable, i.e. if there is a 1044 locally connected host, then traffic received on the interface, which 1045 is configured to be U-turn capable, for which there is no loop-free 1046 node-protecting alternate should be forwarded back out the interface 1047 (i.e. to the primary) and an ICMP Redirect should be sent to the 1048 originating host. 1050 An interface can be either a primary next-hop or the alternate next- 1051 hop, but not both because there would be no protection if the 1052 interface failed. 1054 4.2. Responding to a Local Failure 1055 When a local interface failure is detected, traffic that was destined 1056 to go out the failed interface must be redirected to the appropriate 1057 alternate next-hops. The alternate next-hop is pre-computed to be 1058 reliable in the event of the failure scenario being protected against 1059 (i.e. link or node failure). 1061 IP/LDP Local Protection does not attempt to add anything new to the 1062 detection of the failure. The same mechanisms that enable RSVP-TE 1063 Fast-Reroute can work here. Because the alternate next-hop is pre- 1064 computed, it should be extremely fast to switch traffic to use it, 1065 exactly as is the case with RSVP-TE Fast-Reroute. 1067 5. Requirements on LDP Mechanics 1069 In order for LDP to take advantage of the alternate next-hops 1070 determined, it is necessary for LDP to have the appropriate labels 1071 available for the alternate so that the appropriate out-segments can 1072 be installed in the forwarding plane before the failure occurs. 1074 This means that a Label Switched Router (LSR) running LDP must 1075 distribute its labels for the FECs it can provide to all its 1076 neighbors, regardless of whether or not they are upstream. 1077 Additionally, LDP must be acting in liberal label retention mode so 1078 that the labels which correspond to interfaces that aren't currently 1079 the primary next-hop are stored. Similarly, LDP should be in 1080 downstream unsolicited mode, so that the labels for the FEC are 1081 distributed other than along the SPT. 1083 6. Routing Interactions 1085 Just as a standard SPF is run on a particular area or level to find 1086 the primary next-hops, IP Local Protection determines the alternates 1087 to use for a particular area or level. An IGP must determine how to 1088 use those alternates for routes which are not in the local area. 1089 Additionally, those alternates must be communicated properly to LDP 1090 and BGP for their use. IP Local Protection provides alternate paths 1091 for IGP destinations. The alternates are provided to LDP and BGP for 1092 forwarding purposes only; the alternates are not redistributed in any 1093 fashion into other protocols. 1095 6.1. OSPF Inter-Area Routing 1097 Each area in OSPF has its own link state database and corresponding 1098 topology. IP Local Protection provides the primary next-hops and 1099 alternate next-hop for each Area Border Router. The alternates for 1100 summary routes which can be reached via a particular Area Border 1101 Router (ABR) will be inherited from the ABR, just as the primary 1102 next-hops are currently. 1104 The complexity occurs when there is a set of ABRs which are 1105 equidistant from the router S and those ABRs are summarizing a common 1106 set of inter-area destinations. This is a case where the router S 1107 will select from the primary next-hops to reach each of the ABRs in 1108 the set in order to form an ECMP set to reach the inter-area 1109 destination(s). 1111 Additional alternate inheritance rules are necessary in this case; 1112 the rules to follow depend upon the nature of the candidates for the 1113 ECMP set. There are two scenarios, which will be explained in 1114 reference to Figure 9. 1116 ......... 1117 ..... ..... 1118 ... ... 1119 ... +-----+ ... 1120 . /| A_1 |-------------\ . 1121 . / +-----+ \ . 1122 . / \-+-----+ 5 1123 .. / |ABR 1|--------\ 1124 . / 5 +-----+--------+-----+ \ 1125 . / /--------| N_1 | 5 . \ 1126 . +-----+-/ +-----+ . +-----+ 1127 . | S | . | D | 1128 . +-----+-\ . +-----+ 1129 . \ \ . 5 / 1130 . \ \ +-----+ . /-------/ 1131 . \ \------| N_2 | 5 . / 1132 . \ +-----+-------+-----+ / 1133 . \ |ABR.2|/ 1134 .. +-----+ /-+-----+ 1135 . | A_2 |--------------/ . 1136 . +-----+ . 1137 . . 1138 ... ... 1139 ... area 0 ... 1140 ..... ..... 1141 ......... 1143 Figure 9: Inheriting Alternates for ECMP Inter-Area Destinations 1145 1. ECMP Inter-Area Destination with more than one potential 1146 primary neighbor. 1148 2. ECMP Inter-Area Destination with a single primary neighbor. 1150 In Scenario 1, the paths from S to ABR-1 and ABR-2 are node- 1151 protecting with respect to each other; each neighbor is reached via a 1152 different primary next-hop to reach the destination D. In this case, 1153 the primary next-hop to reach N_1 can be used as the alternate next- 1154 hop for N_2 and vice versa. Finding the alternate next-hops in this 1155 scenario is straightforward, because the paths to ABR-1 and ABR-2 are 1156 disjoint. 1158 In Scenario 2, the primary neighbor to reach ABR-1 and ABR-2 is the 1159 same, so the alternate must protect against both the link to N_1 1160 failing and N_1 itself failing. Let the set of ABRs which can be 1161 used to reach the destination be indexed up to T. A loop-free node- 1162 protecting alternate A_i is a candidate if the following is true. 1164 forall_t in T, 1165 if (D_opt(A_i, D) == D_opt(A_i, ABR_t) + D_opt(ABR_t, D)) 1166 D_!S(A_i, ABR_t) < D_opt(A_i, S) + D_opt(S, ABR_t) 1168 The selection criteria between candidate alternate next-hops 1169 associated with ABRs in an ABR set MUST be as follows, for the same 1170 reason as described in Section 3.2.4.4. 1172 1. If there is one or more loop-free node-protecting alternates 1173 associated with one ABR in the set of ABRs, then router MUST 1174 select one of those alternates. Let M be the set of neighbors 1175 which provide loop-free node-protecting alternates to at least 1176 one ABR in the set of ABRs. If S has multiple loop-free node- 1177 protecting alternates, then S MUST select the alternate through 1178 N_k such that Equation 6 is satisfied. 1180 2. If there are no loop-free node-protecting alternates 1181 associated with an ABR in a set of ABRs, then S can select 1182 freely among the appropriate ABR alternates which are available. 1184 6.2. OSPF External Routing 1186 Rules of inheritance of alternate next-hops for external routes is 1187 the same as for inter-area destinations. The additional complication 1188 comes from forwarding addresses, where an ASBR uses a forwarding 1189 address to indicate to all routers in the Autonomous System to use 1190 the specified address instead of going through the ASBR. When a 1191 forwarding address has been indicated, all routers in the topology 1192 calculate the shortest path to the link specified in the external 1193 LSA. In this case, the alternate next-hop of the forwarding link 1194 should be used, in conjunction with the primary next-hop of the 1195 forwarding link, instead of those associated with the ASBR. 1197 6.3. ISIS Multi-Level Routing 1198 Rules for alternate inheritance between levels in ISIS are the same 1199 as for OSPF inter-area routing. 1201 6.4 OSPF Virtual Links 1203 OSPF virtual links are used to connect two disjoint backbone areas 1204 using a transit area. A virtual link is configured at the border 1205 routers of the disjoint area. There are two scenarios, depending 1206 upon the position of the root, router S. 1208 If router S is itself an ABR or one of the endpoints of the disjoint 1209 area, then router S must resolve its paths to the destination on the 1210 other side of the disjoint area by using the summary links in the 1211 transit area and using the closest ABR summarizing them into the 1212 transit area. This means that the data path may diverge from the 1213 virtual neighbor's control path. An ABR's primary and alternate 1214 next-hops are calculated by IP Local Protection on the transit area. 1215 The primary next-hops to use are determined based upon the closest 1216 set of equidistant ABRs; the same rules described in Section 6.1 for 1217 inter-area destinations MUST be followed for OSPF virtual links to 1218 determine the alternate next-hop. The same ECMP cases apply. 1220 If router S is not an ABR, then all the destinations on the other 1221 side of the disjoint area will inherit the virtual link's endpoint, 1222 the transit ABR. The same OSPF inter-area rules described in Section 1223 6.1 MUST be followed here as well. 1225 6.5 BGP Next-Hop Synchronization 1226 BGP simply inherits the alternate next-hop based upon the IGP 1227 destination which was selected. The BGP decision process is 1228 unaltered. 1230 6.6 Interactions with ISIS Overload, RFC 3137 and Costed Out Links 1232 As described in RFC 3137, there are cases where it is desirable not 1233 to have a router used as a transit node. For those cases, it is also 1234 desirable not to have the router used on an alternate path. 1236 For computing an alternate, a router MUST not consider diverting from 1237 the SPF tree along a link whose reverse cost is LSInfinity (for OSPF) 1238 or whose router has the overload bit set (for ISIS). 1240 In the case of OSPF, if all links from router S to a neighbor N_i 1241 have a reverse cost of LSInfinity, then router S cannot consider 1242 using N_i as an alternate. If all links from a neighbor N_i to a 1243 neighbor's neighbor R_i_j have a reverse cost of LSInfinity, then 1244 router S cannot consider that N_i could provide a U-turn alternate 1245 via R_i_j. 1247 Similarly in the case of ISIS, if N_i has the overload bit set, then 1248 S cannot consider using N_i as an alternate. If a neighbor's 1249 neighbor R_i_j has the overload bit set, then router S cannot 1250 consider that N_i could provide a U-turn alterante via R_i_j. 1252 This preserves the desired behavior of diverting traffic away from a 1253 router which is following RFC 3137 and it also preserves the desired 1254 behavior when an operator sets the cost of a link to LSInfinity for 1255 maintenance, of not permitting traffic across that link unless there 1256 is no other path. 1258 If a link or router which is costed out was the only possible 1259 alternate to protect traffic from a particular router S to a 1260 particular destination, then there will be no alternate provided for 1261 protection. 1263 6.7 Multicast Considerations 1265 IP/LDP Local Protection does not apply to multicast traffic. The 1266 alternate next-hops SHOULD not used for multi-cast RPF checks. 1268 7. Security Considerations 1270 This document does not introduce any new security issues. The 1271 mechanisms described in this document depend upon the network 1272 topology distributed via an IGP, such as OSPF or ISIS. It is 1273 dependent upon the security associated with those protocols. 1275 8. Intellectual Property Considerations 1277 Avici Systems has intellectual property rights claimed in regard to 1278 the specification contained in this document. 1280 9. Full Copyright Statement 1282 Copyright (C) The Internet Society (2002). All Rights Reserved. 1284 This document and translations of it may be copied and furnished to 1285 others, and derivative works that comment on or otherwise explain it 1286 or assist in its implementation may be prepared, copied, published 1287 and distributed, in whole or in part, without restriction of any 1288 kind, provided that the above copyright notice and this paragraph are 1289 included on all such copies and derivative works. However, this 1290 document itself may not be modified in any way, such as by removing 1291 the copyright notice or references to the Internet Society or other 1292 Internet organizations, except as needed for the purpose of 1293 developing Internet standards in which case the procedures for 1294 copyrights defined in the Internet Standards process must be 1295 followed, or as required to translate it into languages other than 1296 English. 1298 The limited permissions granted above are perpetual and will not be 1299 revoked by the Internet Society or its successors or assigns. 1301 This document and the information contained herein is provided on an 1302 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 1303 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 1304 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 1305 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 1306 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1308 10. References 1310 [OSPF-LOCAL-PROTECT] A. Atlas, R. Torvi, G. Choudhury, B. Imhoff, C. 1311 Martin, D. Fedyk, "OSPFv2 Extensions for Link Capabilities and IP/LDP 1312 Local Protection", draft-atlas-ospf-local-protect-cap-00.txt, 1313 February 2004, work-in-progress 1315 [ISIS-LOCAL-PROTECT] A. Atlas, R. Torvi, C. Martin, "ISIS Extensions 1316 for Signaling Local Protection Capabilities", draft-martin-isis- 1317 local-protect-cap-00.txt, February 2004, work-in-progress 1319 [LDP] L. Anderson, P. Doolan, N. Feldman, A. Fredette, B. Thomas, 1320 "LDP Specification", RFC 3036, January 2001 1322 [RSVP-TE] D. Awduche, L. Berger, D. Gan, T. Li, V Srinivasan, G. 1323 Swallow, "RSVP-TE: Extensions to RSVP for LSP Tunnels", RFC 3209, 1324 December 2001 1326 [RSVP-TE FRR] P. Pan, D. Gan, G. Swallow, JP Vasseur, D. Cooper, A. 1327 Atlas, and M. Jork, "Fast Reroute Extensions to RSVP-TE for LSP 1328 Tunnels", work-in-progress draft-ietf-mpls-rsvp-lsp-fastreroute- 1329 04.txt, February 2004 1331 [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and 1332 McPherson, D., "OSPF Stub Router Advertisement", RFC 3137, June 2001 1334 [RFC3277] D. McPherson, "Intermediate System to Intermediate System 1335 (IS-IS) Transient Blackhole Avoidance", RFC 3277, April 2002 1337 [ISIS] R. Callon, "Use of OSI IS-IS for Routing in TCP/IP and Dual 1338 Environments", RFC 1195, December 1990 1340 [RFC2966] T. Li, T. Przygienda, H. Smit, "Domain-wide Prefix 1341 Distribution with Two-Level IS-IS", RFC 2966, October 2000 1343 [OSPF] J. Moy, "OSPF Version 2", RFC 2328, April 1998 1345 [RFC2370] R. Coltun, "The OSPF Opaque LSA Option", RFC 2370, July 1346 1998 1348 11. Authors Information 1350 Alia Atlas 1351 Avici Systems 1352 101 Billerica Avenue 1353 N. Billerica, MA 01862 1354 USA 1355 email: aatlas@avici.com 1356 phone: +1 978 964 2070 1358 Raveendra Torvi 1359 Avici Systems 1360 101 Billerica Avenue 1361 N. Billerica, MA 01862 1362 USA 1363 email: rtorvi@avici.com 1364 phone: +1 978 964 2026 1366 Gagan Choudhury 1367 AT&T 1368 Room D5-3C21 1369 200 Laurel Avenue 1370 Middletown, NJ 07748 1371 USA 1372 email: gchoudhury@att.com 1373 phone: +1 732 420-3721 1375 Christian Martin 1376 Verizon 1377 1880 Campus Commons Drive 1378 Reston, VA 20191 1379 email: cmartin@verizon.com 1381 Brent Imhoff 1382 WilTel Communications 1383 3180 Rider Trail South 1384 Bridgeton, MO 63045 1385 USA 1386 email: brent.imhoff@wcg.com 1387 phone: +1 314 595 6853 1389 Don Fedyk 1390 Nortel Networks 1391 600 Technology Park 1392 Billerica, MA 01450 1393 email: dwfedyk@nortelnetworks.com 1394 phone: +1 978 288 3041