idnits 2.17.1 draft-atlas-ip-local-protect-uturn-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 14. -- Found old boilerplate from RFC 3978, Section 5.5 on line 1306. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1283. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1290. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1296. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** 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 separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** 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 212: '... N_i MUST only send U-turn packets t...' RFC 2119 keyword, line 379: '...is specification MUST support one of t...' RFC 2119 keyword, line 401: '... identification MUST be used....' RFC 2119 keyword, line 406: '... IGP area, it still MUST be considered...' RFC 2119 keyword, line 409: '... packet identification SHOULD be used....' (36 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == 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: The U-turn alternate next-hop MUST use a link which has been advertised as implicit or explicit marked U-turn Recipient capable by the intended neighbor. If router S is only capable of sending unmarked U-turn packets, then router S MUST not use links which are not advertised as implicit U-turn Recipient capable to reach a U-turn alternate next-hop. Similarly, if router S is only capable of sending marked U-turn packets, then router S MUST not use links which are not advertised as explicit marked U-turn Recipient capable to reach a U-turn alternate next-hop. == 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: If a link is advertised only as explicit marked U-turn Recipient capable and it is selected to reach the U-turn alternate next-hop, then router S MUST apply the marking, as described in the explicit marked U-turn packet identification method, to each packet sent into the U-turn alternate. If the link is advertised only as implicit U-turn Recipient capable and it is selected to reach the U-turn alternate next-hop, then router S MUST not apply any additional marking. If the link is advertised as both implicit U-turn Recipient capable and explicit marked U-turn Recipient capable, then router S may make a local decision as to whether to apply the additional marking. -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (February 2006) is 6638 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'I-D.ietf-isis-link-attr' is defined on line 1168, but no explicit reference was found in the text == Unused Reference: 'RFC1195' is defined on line 1197, but no explicit reference was found in the text == Unused Reference: 'RFC2328' is defined on line 1200, but no explicit reference was found in the text == Unused Reference: 'RFC2370' is defined on line 1202, but no explicit reference was found in the text == Unused Reference: 'RFC2966' is defined on line 1205, but no explicit reference was found in the text == Unused Reference: 'RFC3036' is defined on line 1209, but no explicit reference was found in the text == Unused Reference: 'RFC3137' is defined on line 1212, but no explicit reference was found in the text == Unused Reference: 'RFC3209' is defined on line 1216, but no explicit reference was found in the text == Unused Reference: 'RFC3277' is defined on line 1220, but no explicit reference was found in the text == Outdated reference: A later version (-03) exists of draft-ietf-isis-link-attr-01 == Outdated reference: A later version (-13) exists of draft-ietf-rtgwg-ipfrr-framework-05 ** Downref: Normative reference to an Informational draft: draft-ietf-rtgwg-ipfrr-framework (ref. 'I-D.ietf-rtgwg-ipfrr-framework') == Outdated reference: A later version (-12) exists of draft-ietf-rtgwg-ipfrr-spec-base-05 -- Possible downref: Normative reference to a draft: ref. 'ISIS-LOCAL-PROTECT' -- Possible downref: Normative reference to a draft: ref. 'OSPF-LOCAL-PROTECT' ** Obsolete normative reference: RFC 2370 (Obsoleted by RFC 5250) ** Obsolete normative reference: RFC 2966 (Obsoleted by RFC 5302) ** Obsolete normative reference: RFC 3036 (Obsoleted by RFC 5036) ** Obsolete normative reference: RFC 3137 (Obsoleted by RFC 6987) ** Downref: Normative reference to an Informational RFC: RFC 3277 Summary: 12 errors (**), 0 flaws (~~), 16 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A. Atlas, Ed. 3 Internet-Draft Google, Inc. 4 Expires: August 5, 2006 February 2006 6 U-turn Alternates for IP/LDP Fast-Reroute 7 draft-atlas-ip-local-protect-uturn-03 9 Status of this Memo 11 By submitting this Internet-Draft, each author represents that any 12 applicable patent or other IPR claims of which he or she is aware 13 have been or will be disclosed, and any of which he or she becomes 14 aware will be disclosed, in accordance with Section 6 of BCP 79. 16 Internet-Drafts are working documents of the Internet Engineering 17 Task Force (IETF), its areas, and its working groups. Note that 18 other groups may also distribute working documents as Internet- 19 Drafts. 21 Internet-Drafts are draft documents valid for a maximum of six months 22 and may be updated, replaced, or obsoleted by other documents at any 23 time. It is inappropriate to use Internet-Drafts as reference 24 material or to cite them other than as "work in progress." 26 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/ietf/1id-abstracts.txt. 29 The list of Internet-Draft Shadow Directories can be accessed at 30 http://www.ietf.org/shadow.html. 32 This Internet-Draft will expire on August 5, 2006. 34 Copyright Notice 36 Copyright (C) The Internet Society (2006). 38 Abstract 40 This document defines and describes the use of U-turn alternates to 41 provide local protection for IP unicast and/or LDP traffic in the 42 event of a single failure, whether link, node or shared risk link 43 group (SRLG). When a topology change occurs, a router S pre-computes 44 for each prefix an alternate next-hop that can be used if the primary 45 next-hop fails. An acceptable alternate can be either a loop-free 46 alternate or a U-turn alternate. A U-turn alternate uses a neighbor, 47 whose primary next-hop to the prefix is router S itself and which has 48 itself a loop-free node-protecting alternate, which thus does not go 49 through router S to reach the destination prefix. 51 Table of Contents 53 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 54 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 55 2. U-turn Alternates . . . . . . . . . . . . . . . . . . . . . . 5 56 2.1 ECMP U-turn Neighbors . . . . . . . . . . . . . . . . . . 7 57 2.2 U-turn Neighbor's Alternate . . . . . . . . . . . . . . . 8 58 2.3 Identifying U-turn Traffic . . . . . . . . . . . . . . . . 9 59 2.3.1 Implicit U-turn Packet Identification . . . . . . . . 9 60 2.3.1.1 Broadcast and NBMA Interfaces . . . . . . . . . . 9 61 2.3.2 Explicitly Marked U-turn Packet Identification . . . . 10 62 3. Example Algorithm for finding U-turn Alternates . . . . . . . 12 63 3.1 SRLG Protection . . . . . . . . . . . . . . . . . . . . . 16 64 4. Alternate Next-Hop Calculation . . . . . . . . . . . . . . . . 16 65 4.1 IP/LDP Fast-Reroute Alternate Capability . . . . . . . . . 16 66 4.2 U-turn Recipient Capabilities . . . . . . . . . . . . . . 17 67 4.3 Link-Protecting U-turn Alternate . . . . . . . . . . . . . 18 68 4.4 U-turn Node-Protecting Alternate . . . . . . . . . . . . . 19 69 4.5 Selection Procedure . . . . . . . . . . . . . . . . . . . 19 70 4.5.1 Selection Between Multiple Loop-Free 71 Node-Protecting Alternate . . . . . . . . . . . . . . 21 72 5. Using an Alternate . . . . . . . . . . . . . . . . . . . . . . 22 73 5.1 Alternate Use On Failure . . . . . . . . . . . . . . . . . 22 74 5.2 U-turn Packets Forwarding . . . . . . . . . . . . . . . . 24 75 6. LDP Interactions and Routing Aspects . . . . . . . . . . . . . 24 76 6.1 LDP Interactions . . . . . . . . . . . . . . . . . . . . . 24 77 6.2 Multi-Homed Prefixes . . . . . . . . . . . . . . . . . . . 24 78 6.3 OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 79 6.4 U-turn Alternates Interactions with Tunnels . . . . . . . 24 80 7. Security Considerations . . . . . . . . . . . . . . . . . . . 25 81 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 25 82 9. Intellectual Property Considerations . . . . . . . . . . . . . 25 83 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 25 84 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 27 85 Intellectual Property and Copyright Statements . . . . . . . . 29 87 1. Introduction 89 This document extends IP Fast-Reroute, as defined in [I-D.ietf-rtgwg- 90 ipfrr-spec-base] and [I-D.ietf-rtgwg-ipfrr-framework], which allows a 91 router whose local interface or next-hop has failed to forward 92 traffic to a pre-computed alternate until the router installs the new 93 primary next-hops based upon the changed network topology. 95 The existence of suitable loop-free alternate next-hops is topology 96 dependent. This document defines a second type of alternate next- 97 hop, known as a U-turn alternate, and provides the common behavior 98 and selection method necessary to allow U-turn alternates to 99 function. 101 The topology in Figure 1 is an example where there is no loop-free 102 alternate from S to D, but there is a U-turn alternate. 104 @@@> 105 <--- +-----+ 106 +----------| N_1 | 107 | 5 +-----+ 108 | | 109 +---+-+ | 110 | S | @ |10 111 +-----+ @ | 112 | V | 113 | |5 | 114 V | | 115 | | 116 +-----+ | 117 | E | +-----+ 118 +-----+ | R_1 | 119 | +-----+ 120 | |5 | 121 | | 10 | | 122 V | | | 123 +-----+ | V 124 | D |---------+ 125 +-----+ 127 Figure 1: Topology with U-turn Alternate 129 In Figure 1, there is no loop-free alternate for S to use to reach D. 130 This is because the costs are such that N_1 uses S as its primary 131 neighbor; therefore if S were to send the traffic to N_1, it would 132 loop back to S. If both S and N_1 support the mechanisms defined in 133 this document, then S could use N_1 as a U-turn alternate. Traffic 134 destined to D that was sent by S to N_1 would be forwarded by N_1 to 135 R_1, N_1's loop-free node-protecting alternate. 137 In examining realistic networks, it was seen that loop-free 138 alternates did not provide adequate coverage for the traffic between 139 all the source-destination pairs. As with loop-free alternates, the 140 existence of suitable U-turn alternates is topology dependent; it is 141 seen to substantially extend the coverage on realistic topology above 142 that seen with just loop-free alternates. 144 This document describes the case where a loop-free node-protecting 145 alternate must be available at a neighbor's neighbor. It is possible 146 to extend the length of the U-turn to provide better coverage at the 147 cost of additional local computation. 149 1.1 Terminology 151 This document uses the terminology defined in [I-D.ietf-rtgwg-ipfrr- 152 framework] and the additional terms defined below. 154 Distance_opt(A, B) or D_opt(A,B): The distance of a shortest path 155 from A to B. 157 Distance_!S(A, B) or D_!S(A,B): The distance of a shortest path from 158 A to B that does not traverse S. 160 Reverse Distance of a node X: --- This is the Distance_opt(X, S). 162 U-Turn Alternate: This is an alternate next-hop of S that goes to a 163 neighbor N_i, whose primary next-hop is S, and whose alternate 164 neighbor does not go back trough the router S, which may therefore 165 use the link to N_i as an alternate. 167 Link(A->B): A link connecting router A to router B. 169 ---> An arrow indicating the primary next-hop towards D. 171 @@@> An arrow indicating the alternate next-hop towards D. 173 U-Turn Neighbor: A neighbor N_i is a U-Turn neighbor of router S with 174 respect to a given destination D if and only if S is a primary 175 neighbor of N_i to reach the destination D for all optimal paths 176 which go through S to reach D. 178 ECMP U-Turn Neighbor: A neighbor N_i that is a U-Turn neighbor and 179 that has at least one equal cost path to reach D that does not go 180 through S as well as at least one equal cost path that does go 181 through S to reach D. 183 Looping Neighbor: A neighbor N_i is a looping neighbor of router S 184 with respect to a given destination D if and only if S is not the 185 primary next-hop of N_i on at least one optimal path from N_i to D 186 that also goes through S. 188 2. U-turn Alternates 190 As with primary next-hops, an alternate next-hop is discussed in 191 relation to a particular destination router D. As described in 192 [I-D.ietf-rtgwg-ipfrr-spec-base], a neighbor can provide a loop-free 193 alternate if Equation 1 is true. 195 D_opt(N_i, D) < D_opt(N_i, S) + D_opt(S, D) 197 Equation 1: Criteria for a Loop-Free Alternate 199 When there are no loop-free alternates, this means that all of S's 200 remaining non-primary neighbors will send traffic for D back to S, 201 either directly or indirectly. It is probable that one of S's non- 202 primary neighbors will have a loop-free node-protecting alternate 203 that could be utilized if the neighbor N_i is able to identify a 204 packet as a U-turn packet. 206 N_i can indicate its ability to correctly identify incoming U-turn 207 packets on each layer-3 interface; such an interface is U-turn 208 Recipient capable[ISIS-LOCAL-PROTECT][OSPF-LOCAL-PROTECT]. U-turn 209 packets are identified implicitly or explicitly as described in 210 Section 2.3. 212 N_i MUST only send U-turn packets to N_i's loop-free node-protecting 213 alternate if the packet is received from a primary neighbor for that 214 destination. This motivates the definitions below of a Looping 215 Neighbor and a U-turn Neighbor. These examples are illustrated in 216 Figure 2. 218 Looping Neighbor: A neighbor N_i is a looping neighbor of router S 219 with respect to a given destination D if any of N_i's shortest 220 paths to D goes through S but S is not the primary next-hop of 221 N_i for all those paths through S. 223 U-Turn Neighbor: A neighbor N_i is a U-Turn Neighbor of router S with 224 respect to a given destination D if and only if S is a primary 225 next-hop of N_i to reach the destination D for all optimal paths 226 that go through S to reach D. 228 +-----+ --> 229 | N_4 |------ <--- +-----+ 230 +-----+ | |-----| R_3 | 231 | 15 | | 5 +-----+ 232 |50 | | | 233 +-----+ ---> | +-----+ | 70 234 | N_2 |------ | | N_3 | | 235 +-----+ | | +-----+ | 236 | 15 | | | 30 | 237 | 10 | +-----+ <--- | | 238 @ | ----| S |--------| | 239 @ | <@@@ +-----+ | 240 V | | | | 241 | 10 | | | 242 +-----+ | V | 243 | R_2 | +-----+ | 244 +-----+ | E | | 245 | | +-----+ | 246 | | 40 | | | 247 V | 10 | | | 248 | +-----+ | V | 249 -----| R_1 |-----| | 250 +-----+ | 251 | ---> +-----+ | 252 |------------------| D |--------- 253 10 +-----+ 255 E is primary next-hop of S 256 N_2 and N_3 are U-Turn Neighbors of S 257 N_4 is a Looping Neighbor of S 259 Figure 2: Terminology of Looping Neighbors and Example U-Turn 260 Alternate 262 Mathematically, for a neighbor N_i to be a U-Turn neighbor, it is 263 necessary that Equation 1 be false. If D_opt(N_i,D) = D_opt(N_i,S) + 264 D_opt(S,D), then there may be multiple optimal paths, at least one of 265 which goes through S and one does not. If the shortest distance path 266 from N_i to D that doesn't traverse S (D_!S(N_i, D)) is equal to 267 D_opt(N_i, S) + D_opt(S, D, then there are multiple optimal paths 268 where at least one traverses S and one does not. Such a neighbor may 269 be an ECMP U-Turn neighbor or may be a looping neighbor. 271 Additionally, all optimal paths to reach D that go via S must be via 272 a direct link between N_i and S. If a neighbor N_i does not satisfy 273 Equation 1 and all optimal paths to reach D that go via S are via a 274 direct link between N_i and S, then it is a U-turn neighbor. 276 2.1 ECMP U-turn Neighbors 278 The above definition for U-Turn Neighbor allows a neighbor, which has 279 equal cost paths (an ECMP set) where at least one of those paths goes 280 directly to S and others may or may not, to be a U-Turn Neighbor. 281 Consider the topology shown in Figure 3. In this figure, N_1 has 282 three equal-cost paths to reach D which are N_1 - S - E - D, N_1 - 283 R_1 - D, and N_1 - R_2 - D. Because the only path that goes through S 284 goes directly through S, N_1 is a U-Turn neighbor of S. A neighbor is 285 an ECMP U-turn neighbor if an optimal path from N_i to D traverses S 286 and there are multiple optimal paths from N_i to D. 288 +-----+------------- 289 ---------| N_1 | | 5 290 | | +-----+--------- | +-----+ 291 | | 10 | 15 | |----| R_3 | 292 V | | | | +-----+ 293 +-----+ | | 10 | | 15 | 294 | S | V | | | | | 295 +-----+ | V | | | 296 | +-----+ | | V 297 10 | | ---| R_1 | | | 298 | | | +-----+ | | 299 | V | | +-----+ | 300 | | | 20 | R_2 | | 301 +-----+ V | +-----+ +-----+ 302 | E | | | | X | 303 +-----+ | 15 | | +-----+ 304 | | |---------| | | 305 | | 10 | | V | 306 | | +-----+ <--- | 307 V |--------| D |---------------------| 15 308 +-----+ 310 Figure 3: ECMP U-Turn Neighbor 312 S does not know whether a neighbor N_i supports ECMP or how that 313 neighbor selects among the equal cost paths. Recall that a node will 314 only direct U-turn packets to the alternate if those packets are 315 received from that node's primary neighbors. 317 Consider the topology in Figure 4, where N_2 has three equal cost 318 primary neighbors which are S, N_1 and R_1. If N_2 were to select 319 only N_1 as its primary neighbor, then N_2 would break U-Turns only 320 on traffic received from N_1 and not on traffic received from S. 321 Therefore, S cannot consider N_2 as an ECMP U-Turn neighbor because S 322 cannot rely upon N_2 to break U-turns for traffic destined to D which 323 is received from S. 325 <--- 10 +-----+ ---> 326 --------------------| N_2 |----- 327 | +-----+ | 328 | 5 | | | 329 | +-----+ | | | 330 | | N_1 |----| V | 5 331 +-----+ +-----+ +-----+ 332 | S | <-- | 5 | R_1 | 333 +-----+---------- +-----+ 334 5 | | | 15 335 +-----+ | | | | 336 | E |----| V | | 337 +-----+ V | 338 5 | ---> +-----+ | 339 |------------------| D |------------- 340 +-----+ 342 Figure 4: ECMP Neighbor Which is Not an ECMP U-Turn Neighbor 344 If N_2 has multiple paths to reach D that traverse S and not all such 345 paths have S as the next-hop, then S cannot use N_2 as a U-Turn 346 neighbor. 348 2.2 U-turn Neighbor's Alternate 350 For router S to use a U-turn neighbor N_i for a U-turn alternate, N_i 351 requires a loop-free node-protecting alternate[I-D.ietf-rtgwg-ipfrr- 352 spec-base]. If R_i_j provides a loop-free node-protecting alternate 353 for N_i and S is N_i's primary neighbor, then the path from R_i_j to 354 D will not traverse S. The requirement for an R_i_j to provide a 355 suitable alternate is: 357 D_opt(R_i_j, D) < D_opt(R_i_j, S) + D_opt(S, D) 359 Equation 2: Loop-Free Node-Protecting Neighbor's Neighbor 361 Because N_i is a U-turn neighbor, N_i's shortest path to D traverse 362 S; therefore Equation 2 means that the shortest paths from R_i_j to D 363 also do not traverse N_i. 365 Each router independently computes the alternate that it will select 366 for a given destination D. For the U-turn alternate to provide 367 broadcast link protection, or node or SRLG protection, the router N_i 368 must consistently select a suitable alternate, if available, such 369 that N_i's primary neighbor S can determine what R_i_j is providing 370 that alternate. 372 2.3 Identifying U-turn Traffic 374 There are two methods for identifying a packet as a U-turn packet. 375 The methods are implicit U-turn packet identification and explicit 376 U-turn packet identification. These methods are described in 377 Section 2.3.1 and Section 2.3.2. 379 A router supporting this specification MUST support one of these two 380 methods for identifying U-turn packets. A 382 2.3.1 Implicit U-turn Packet Identification 384 The first method requires no modification to the packets sent into 385 the U-turn alternate. In this method, when, on an Implicit U-turn 386 Recipient Capable interface or sub-interface, a packet for a 387 destination D is received from the primary neighbor to which the 388 router would forward the packet, then the router locally identifies 389 the packet as a U-turn packet and forwards on the loop-free 390 alternate. In essence, this breaks the single hop micro-forwarding 391 loop. 393 2.3.1.1 Broadcast and NBMA Interfaces 395 NBMA and broadcast interfaces can be treated identically for IP/LDP 396 Fast-Reroute; both involve the case of possibly receiving traffic 397 from multiple neighbors. With broadcast links (i.e. Gigabit 398 Ethernet), there can be multiple neighbors connected to the same 399 link. If all the neighbors are not in the same IGP area or there are 400 hosts with default routes on the link, then explicit U-turn packet 401 identification MUST be used. 403 If implicit U-turn packet identification were used, traffic could be 404 incorrectly sent to the alternate. It is extremely desirable to have 405 at most one forwarding table per interface or sub-interface. If all 406 the neighbors are in the same IGP area, it still MUST be considered 407 whether all traffic received on an interface can be treated 408 identically, regardless of the neighbor sourcing the traffic on that 409 interface; otherwise explicit packet identification SHOULD be used. 411 The cost for any node on the broadcast link to reach S or its primary 412 neighbor E will be identical. Because all link costs are positive, 413 no neighbor on the broadcast link will ever send traffic to S along 414 that interface in order to reach E. Therefore, S can assume that any 415 traffic received from the broadcast link that goes to a destination 416 via a primary next-hop neighbor that is also on the broadcast link is 417 in fact sent by that primary next-hop neighbor and should be 418 redirected to break the U-Turn. 420 Thus, if router S has a primary next-hop neighbor for a given prefix 421 on the broadcast link, S should redirect all traffic received 422 destined to that prefix on the broadcast link to S's alternate next- 423 hop. 425 +-----------+-----------+------------+----------+ 426 | | | | | 427 | | /E\ | /E\ | /E\ | /E\ 428 | 2 3| | 3| | 4| | 5| | 429 | | | | | 430 +-----+ +-----+ +-----+ +-----+ +-----+ 431 | E | | S | | N_1 | | N_2 | | N_3 | 432 +-----+ +-----+ +-----+ +-----+ +-----+ 433 | | 434 | | 10 @ | 10 435 | | @ | 436 V | V | 437 | +-----+ 438 | | N_4 | 439 | +-----+ 440 +-----+ 10 | 441 | D |----------| 442 +-----+ <--- 444 Figure 5: Topology With Broadcast Link 446 If it were acceptable to have one forwarding table per neighbor on 447 the link, then the restriction that all neighbors on a broadcast link 448 be in the same IGP region and not be hosts with default routes could 449 be removed. 451 2.3.2 Explicitly Marked U-turn Packet Identification 453 The second method requires that U-turn packets be explicitly marked 454 as such by the router that is directing the packet into the U-turn 455 alternate. This method is motivated by the following benefits: 457 a. For certain existing hardware platforms, it may be difficult to 458 implicitly detect packets as coming from a primary neighbor and 459 forward those packets differently. An explicit marking permits 460 straightforward U-turn handling. 462 b. For broadcast and NBMA links, if packets in the U-turn alternate 463 are not explicitly marked, there are restrictions on the 464 neighbors and hosts (see Section 2.3.1.1). This could limit 465 realistic deployment scenarios where hosts may exist on the same 466 broadcast link as routers. When U-turn packets are explicitly 467 marked, the router can treat some packets received on the 468 interface as U-turn packets and some as normal packets. This 469 permits routers and hosts on a link to send normal traffic while 470 the primary neighbor can send explicitly marked U-turn packets. 472 c. If a router were to request penultimate-hop popping (PHP) for an 473 LSP egressing on interface that the router had also advertised as 474 U-turn Recipient capable, then it would be possible for traffic 475 exiting that LSP to be mis-identified using the implicit 476 identification. If U-turn packets are explicitly marked, then 477 this confusion would not occur and the router could both request 478 PHP for LSPs egressing an interface and supported explicit U-turn 479 packet identification. 481 Explicitly marking U-turn traffic has the following disadvantages, 482 which could be viewed as advantages for the implicit U-turn traffic: 484 a. A marking method must be selected. This marking will need to be 485 below Layer 3; there are certainly no available bits for this 486 purpose in the IPv4 header. 488 b. In some cases implicit U-turn marking will mitigate loops that 489 form by detecting the loop and forwarding to a loop-free node- 490 protecting alternate. This capability is lost when packets are 491 explicitly marked. 493 There are a number of different ways in which U-turn packets could be 494 explicitly marked. For example, this could be done at Layer 2 by 495 using different PPP types, Ethernet types, etc. The simplest 496 mechanism that can apply regardless of the Layer 2 technology is to 497 use a well-known MPLS label (referred to as a U-turn Label). By 498 requiring that routers supporting this specification use the same 499 well-known MPLS label, there is no need to communicate the label. 501 There are already different PPP types, Ethernet types, etc. for MPLS. 502 If a router does not support any other MPLS mechanism, then a packet 503 received with the U-turn label can be clearly identified from the 504 layer-2 information indicating that the packet is MPLS. The MPLS 505 label on the packet SHOULD be checked to verify that the label is the 506 U-turn label. 508 Unlike the common use of MPLS labels, the U-turn label does not 509 indicate specifically where the packet should be switched. The 510 U-turn label indicates that the packet should be tentatively 511 identified as a U-turn packet. The label is always popped on the 512 receiving node. 514 If the explicitly marked packet was received from a primary neighbor, 515 then the packet is a U-turn packet; the U-turn label MUST be popped 516 and the decision on where to forward the packet is based on the 517 packet's identification as a U-turn packet and the packet's 518 destination IP address or the new top MPLS label (after the U-turn 519 label has been popped). 521 If the explicitly marked packet was not received from a primary 522 neighbor, then the packet is not a U-turn packet, the U-turn label 523 must be popped, and the packet MUST be forwarded as a normal packet 524 based upon its destination IP address or the top MPLS label (after 525 the U-turn label has been popped). This scenario could occur if a 526 failure happened during another topology change where the sending 527 router will be or was the receiving router's primary neighbor. 529 It is always necessary to check whether a U-turn marked packet was 530 received from a primary neighbor and to determine from which primary 531 neighbor to properly handle cases where the receiving router has 532 equal-cost paths to the destination. For example, in Figure 3 N_1 533 has three equal-cost paths via S, R_1 and R_2. Assume that N_1 has 534 selected S and R_1 as its primary next-hops. When N_1 receives a 535 U-turn marked packet from S, then that packet can be sent to R_1. 536 When N_1 received a U-turn marked packet from R_1, then that packet 537 can be sent to S. When N_1 receives a U-turn marked packet from R_2, 538 N_1 determines it didn't come from a primary neighbor and will send 539 it to either S or R_1. The need to determine which primary neighbor 540 a U-turn marked packet came from can be seen even more clearly if, 541 for this example, N_1 had selected only S as its primary next-hop and 542 selected R_1 as the loop-free node-protecting alternate next-hop. 543 N_1 might receive U-turn marked packets from S, R_1 or R_2; N_1 must 544 not forward the packets received from R_1 back to R_1. 546 The QoS characteristics associated with a packet with a U-turn label 547 SHOULD be based on the IP packet or the MPLS packet after the U-turn 548 label has been removed. 550 3. Example Algorithm for finding U-turn Alternates 552 This section describes an algorithm that allows the identification of 553 U-turn alternates with a single reverse-SPF computation rooted at S 554 and at most one additional SPF computation per neighbor that could be 555 used as a U-turn alternate. These are required in addition to those 556 required to locate loop-free alternates. 558 The computational complexity of locating alternates is extremely 559 important. There are several factors which potentially influence 560 this. 562 N: Number of neighbors of S 564 A: Number of neighbors that could be used as alternates 566 U: Number of neighbors that could be used as U-turn alternates 568 Clearly, any path computation mechanisms will depend upon the cost of 569 SPF calculations, which depend upon the number of links and nodes and 570 pseudo-nodes in the network and the parameter above. However, 571 different approaches can lead to very different numbers of SPF 572 calculations, ranging from a number of computations proportional to N 573 (or A and U) up to a number proportional to the number of nodes in 574 the network, the number of local links, the number of neighbors' 575 neighbors, or even the number of differently homed prefixes. 576 Clearly, the latter are undesirable. 578 A single SPF is done to find the primary next-hops; this yields 579 D_opt(S, D) for all D. The additional computation required for loop- 580 free alternates is at worst an SPF rooted at each neighbor N_i that 581 can be used as an alternate. This gives a worst-case of an 582 additional A SPF computations to find loop-free alternates. The 583 information obtained is D_opt(D, S) and D_opt(N_i, D) for all N_i and 584 D. 586 It is important to understand the minimum computation required for 587 U-turn alternates beyond that needed for loop-free alternates. The 588 first information required is the distance from any neighbor's 589 neighbor R_i_j back to S; this is known via a single reverse SPF 590 rooted at S. The minimum information that must be determined is 591 whether a particular neighbor N_i has a loop-free node-protecting 592 alternate. This can be determined for a neighbor N_i by running a 593 single U-turn SPF. To explain the rationale behind the mechanisms in 594 a U-turn SPF, consider the following. 596 An SPF algorithm is performing a minimization across the potential 597 paths. A regular SPF is started by exploring each link connected to 598 the root N_i and using the metric associated with that link as the 599 cost. Therefore, at each destination D, it determines D_opt(N_i, D). 601 If instead each link from the root N_i is explored with a cost of 0, 602 then, if there are J neighbors of N_i, the distance associated with 603 the path at each destination D would be 604 min_forall j in J (D_!N_i(R_i_j, D)) 605 where D_!N_i indicates the shortest path from the particular R_i_j to 606 D that does not traverse N_i. 608 Now, if one considers the loop-free test from Equation 2 and groups 609 all the R_i_j terms onto one side, one obtains the following 610 equation: 612 D_opt(R_i_j, D) - D_opt(R_i_j, S) < D_opt(S, D). 614 If an SPF could be modified to minimize the left-hand side of the 615 above equation for all R_i_j neighboring N_i, then the resulting 616 value could be compared to D_opt(S,D) to determine if N_i had a loop- 617 free node-protecting alternate. Mathematically, if there are 1 to J 618 different neighbors of N_i, the desired result at each destination D 619 would be: 620 min_forall j in J (D_opt(R_i,j, D) - D_opt(R_i_j, S)). 622 It is sufficient to determine at each destination D: 624 min_forall j in J (D_!N_i(R_i,j, D) - D_opt(R_i_j, S)). 626 Equation 4: Path Minimization for U-turn Alternate Check 628 To visualize this, consider the following 2 different cases where 629 N_i's primary neighbor is S. 631 A shortest path from R_i_j to D is via N_i and thus S. Therefore, 632 D_!N_i(R_i_j, D) >= D_opt(R_i_j, D). 634 A shortest path from R_i_j to D is not via N_i. Therefore, 635 D_!N_i(R_i_j, D) = D_opt(R_i_j, D). 637 Now that the rationale behind a U-turn SPF is clearer, here is the 638 description of a U-turn SPF. If this procedure is followed, then the 639 stored path distance at each destination D will be Equation 3. 641 A U-turn SPF is a regular SPF where the initial exploration of links 642 from the root N_i uses different costs depending upon the node at the 643 other end of the link. Links from N_i to a node R_i_j are explored 644 with a cost of -D_opt(R_i_j, S). If a link goes from N_i to a 645 pseudo-node, then the pseudo-node's links are also explored as part 646 of this step. The pseudo-node itself is not given a non-infinite 647 path distance in this step. In this step, each link from a pseudo- 648 node neighboring N_i to a node R_i_j is explored with a cost of 649 -D_opt(R_i_j, S). At the end of this step, each R_i_j will be on the 650 candidate-list. From this point, the normal mechanics of the 651 Dijkstra algorithm apply; when a node is removed from the candidate- 652 list, its links will be explored with the cost that of the link 653 metric. 655 Links from N_i will not be explored if those links are not available 656 to provide alternate protection. First, if a point-to-point link is 657 connected to S, it is not explored. Second, a link to a pseudo-node, 658 where that pseudo-node is also connected to S, with the cost of 659 D_opt(N_i, S) will not be explored; it is possible that an alternate 660 found via that link would not provide link-protection for N_i's 661 primary next-hop. Third, a link that is configured to not be used as 662 an alternate will not be explored. Fourth, a link whose forward or 663 reverse cost is at the maximum will not be explored; such a cost 664 indicates that it desired for the link not to be used to tranist 665 traffic. 667 To support ECMP U-turn alternates, it is necessary to know the path 668 traversal without going through S. Therefore, in the U-turn SPF 669 computation, S is never placed onto the candidate list; its links are 670 never explored. 672 From the above description of a U-turn SPF and the rationale behind 673 it, it can be seen that at most one U-turn SPF is needed per neighbor 674 that could be used as a U-turn alternate. The computational 675 complexity of a U-turn SPF is roughly the same as a regular SPF. The 676 additional computational complexity is U U-turn SPF computations, 677 where U is the number of neighbors that could be considered as U-turn 678 alternates. 680 The above gives the ability to determine if a neighbor N_i has a 681 loop-free node-protecting alternate and can therefore provide a 682 U-turn alternate. It does not provide a method to determine if that 683 U-turn alternate is node-protecting. Because D_opt(R_i_j, E) is not 684 known as a result of the previous SPFs, a simple distance comparison 685 is not possible without additional SPFs. To obtain D_opt(R_i_j, E) 686 would require R SPF computations and replace the U U-turn SPF 687 computations. In a network the number of neigbhors is generally much 688 less then the number of neighbors' neighbors. Therefore, another 689 method of determining node protection for U-turn alternates is 690 desirable. 692 During the U-turn SPF, it is possible to track those neighbors of S 693 that were visited along the stored path. If this is done and N_i 694 always selects the R_i_j corresponding to that path as an alternate, 695 then S can determine whether that stored path traverses E, S's 696 primary next-hop. This allows S to determine node-protection at the 697 cost of a bit of additional book-keeping. A similar method is 698 required to determine link protection for broadcast links; the 699 neighboring pseudo-nodes must be tracked. 701 This discussion of an algorithm to compute U-turn alternates is 702 intended to provide explanatory background for the selection 703 procedure defined in Section 4.5.1. 705 3.1 SRLG Protection 707 It may be desirable to obtain an alternate that provides SRLG 708 protection. If SRLGs are being considered, then this would need to 709 be signaled to neighboring routers; an extension to the router 710 capability would provide the mechanism. 712 It can be determined if a U-turn alternate provides SRLG-protection 713 by tracking the SRLGs traversed. This may miss a possible U-turn 714 alternate; to locate all possible U-turn alternates and determine 715 SRLG protection may need an SPF computation per neighbors' neighbor. 716 Intelligent pruning of the R_i_j considered based upon first link 717 SRLGs may improve the completeness of the algorithm while not 718 requiring an SPF computation per neighbors' neighbor. 720 4. Alternate Next-Hop Calculation 722 A router S must select an appropriate alternate next-hop. A common 723 selection method is required to support U-turn alternates. At a 724 minimum, a router must select a loop-free node-protecting alternate. 725 It is necessary for router S to know the path taken by the R_i_j that 726 will be selected by N_i; if multiple R_i_j might be used, then the 727 paths are combined. 729 The same set of failure scenarios that can be protected against with 730 a loop-free alternate is of interest with a U-turn alternate. Just 731 as downstream paths solve concerns with micro-forwarding loops via 732 alternates in the event of unplanned for failures, the same concerns 733 can be solved for U-turn alternates by ensuring that the selected 734 neighbor's neighbor is a downstream path with respect to S 735 (D_opt(R_i_j, D) < D_opt(S, D)). 737 There is also the same interaction with maximum costed links and 738 broadcast interfaces as described in [I-D.ietf-rtgwg-ipfrr-spec- 739 base]. In addition, if all links from a neighbor N_i to a neighbor's 740 neighbor R_i_j have a cost or reverse maximum cost (LSInfinity for 741 OSPF), then router S cannot consider that N_i could provide a U-turn 742 alternate via R_i_j. The rationales for these restrictions are the 743 same as given in [I-D.ietf-rtgwg-ipfrr-spec-base]. 745 4.1 IP/LDP Fast-Reroute Alternate Capability 747 There are a number of different reasons why an operator may not wish 748 for a particular interface to be used as an alternate. For instance, 749 the interface may go to an edge router or the interface may not have 750 sufficient bandwidth to contain the traffic which would be put on it 751 in the event of failure. 753 If an interface should not be used as an alternate, then the router 754 MUST signal this appropriately (e.g. as specified in [I-D.ietf-isis- 755 link-attr] and in [OSPF-LOCAL-PROTECT]) to indicate "link excluded 756 from local protection path". The neighbor routers must not consider 757 that such links might be capable of providing a loop-free node- 758 protecting alternate. Therefore, this "link excluded from local 759 protection path" capability is flooded as part of the link 760 capabilities information. Links that are not capable of being 761 alternates are not explored in the first step of the U-turn SPF. 763 Because a router's neighbors may desire to use that router to provide 764 a U-turn alternate, a router must flood to its neighbors which 765 interfaces are not capable of providing alternates. This information 766 allows a router's neighbors to accurately determine whether or not 767 the router has a loop-free node-protecting alternate. 769 4.2 U-turn Recipient Capabilities 771 A router S can only use a neighbor as a U-turn alternate next-hop if 772 that neighbor has advertised its ability to identify U-turn 773 alternates on a link to S. The implicit U-turn recipient capability 774 and/or the explicit marked U-turn recipient capability must be 775 signaled by a neighbor for a link in order for S to determine that it 776 is allowed to use that neighbor as a potential U-turn alternate. By 777 default, S MUST assume that a neighbor cannot provide a U-Turn 778 alternate unless that neighbor indicates the implicit or the explicit 779 marked U-Turn recipient capability on the link to be used by S to 780 reach that neighbor. 782 The U-turn alternate next-hop MUST use a link which has been 783 advertised as implicit or explicit marked U-turn Recipient capable by 784 the intended neighbor. If router S is only capable of sending 785 unmarked U-turn packets, then router S MUST not use links which are 786 not advertised as implicit U-turn Recipient capable to reach a U-turn 787 alternate next-hop. Similarly, if router S is only capable of 788 sending marked U-turn packets, then router S MUST not use links which 789 are not advertised as explicit marked U-turn Recipient capable to 790 reach a U-turn alternate next-hop. 792 If a link is advertised only as explicit marked U-turn Recipient 793 capable and it is selected to reach the U-turn alternate next-hop, 794 then router S MUST apply the marking, as described in the explicit 795 marked U-turn packet identification method, to each packet sent into 796 the U-turn alternate. If the link is advertised only as implicit 797 U-turn Recipient capable and it is selected to reach the U-turn 798 alternate next-hop, then router S MUST not apply any additional 799 marking. If the link is advertised as both implicit U-turn Recipient 800 capable and explicit marked U-turn Recipient capable, then router S 801 may make a local decision as to whether to apply the additional 802 marking. 804 The extensions to signal the U-turn recipient capability and the 805 Marked U-turn recipient capability are described in [OSPF-LOCAL- 806 PROTECT] and [ISIS-LOCAL-PROTECT]. 808 4.3 Link-Protecting U-turn Alternate 810 For a neighbor N_i to be useable by a router S as a U-turn alternate 811 next-hop to reach a destination D to protect against a link between S 812 and a primary next-hop E, the following topology-based conditions 813 MUST be true. 815 1. D_opt(N_i, D) >= D_opt(N_i, S) + D_opt(S, D) 817 2. N_i is either a U-turn neighbor or an ECMP U-turn neighbor. In 818 other words, S is always the primary next-hop on all shortest 819 paths from N_i to D that traverse S. 821 3. N_i has a loop-free link-protecting node-protecting alternate (as 822 computed in the U-turn SPF): 823 min_forall j in J (D_!N_i(R_i,j, D) - D_opt(R_i_j, S)) < D_opt(S, 824 D) 826 4. The path traversed in the U-turn SPF at N_i didn't traverse the 827 pseudo-node form S to E 829 5. N_i can be reached via a candidate alternate next-hop that 830 doesn't traverse the link from S to E or any pseudo-node along 831 that link. 833 6. If N_i is an ECMP U-turn neighbor, then all other equal-cost 834 paths must be loop-free with respect to link from S to E: 835 D_!S(N_i, D) < D_!S(N_i, pseudo_S_E) + D_opt(pseudo_S_E, D) 837 If N_i is an ECMP U-turn neighbor, S cannot determine whether N_i has 838 selected S as a primary neighbor. Therefore, N_i must both pass the 839 tests for a U-turn neighbor while ignoring the equal-cost paths from 840 N_i that don't go through S and the tests for a loop-free neighbor 841 while ignoring the equal-cost paths from N_i that do go through S. 842 More specifically, the loop-free conditions are verified using D_!S 843 instead of D_opt; the U-turn conditions are verified by looking at 844 the path traversal. 846 The non-topology based conditions are dependent upon the signaled 847 link capabilities as described earlier. 849 4.4 U-turn Node-Protecting Alternate 851 For a U-turn alternate next-hop to protect against node failure, S 852 must be able to determine the set of R_i_j that might be used to 853 provide the loop-free node-protecting alternate to N_i. All optimal 854 paths from each of those R_i_j to the destination D MUST avoid S's 855 primary neighbor E. This is expressed by the following topology-based 856 conditions that MUST be true. 858 1. D_opt(N_i, D) >= D_opt(N_i, S) + D_opt(S, D) 860 2. N_i is either a U-turn neighbor or an ECMP U-turn neighbor. In 861 other words, S is always the primary next-hop on all shortest 862 paths from N_i to D that traverse S. 864 3. N_i has a loop-free link-protecting node-protecting alternate 865 (as computed in the U-turn SPF): 866 min_forall j in J (D_!N_i(R_i,j, D) - D_opt(R_i_j, S)) < D_opt(S, 867 D) 869 4. The path traversed in the U-turn SPF at N_i didn't traverse E 871 5. If N_i is an ECMP U-turn neighbor, then all other equal-cost 872 paths must be loop-free with respect to E: 873 D_!S(N_i, D) < D_!S(N_i, E) + D_opt(E, D) 875 For a U-turn alternate to be both link-protecting and node- 876 protecting, it must meet the requirements in this section and in 877 Section 4.3. 879 4.5 Selection Procedure 881 A router supporting this specification SHOULD select a loop-free 882 alternate next-hop or a U-turn alternate next-hop for each primary 883 next-hop used for a given prefix. If a router advertised either the 884 explicit or implicit U-turn recipient capability on any link, then 885 the router MUST select a loop-free node-protecting link-protecting 886 alternate next-hop for each primary next-hop used for a given prefix, 887 if such an alternate is available. A router MAY decide to not use an 888 available loop-free or U-turn alternate next-hop. The selection 889 should maximize the failure cases that can be protected against. 891 A router MAY use different alternate(s) for forwarding U-turn packets 892 and for forwarding traffic when a primary next-hop fails. The 893 alternate(s) used when a primary next-hop fails are a router-local 894 decision. 896 A router S can only be used as a U-turn alternate next-hop by its 897 primary neighbor E if S selects a loop-free link-protecting node- 898 protecting alternate next-hop. Therefore a router MUST select a 899 loop-free link-protecting node-protecting alternate if one is 900 available. Otherwise, a router MAY select any other type of 901 available alternate. 903 A candidate alternate next-hop may be connected to a primary 904 neighbor, a loop-free neighor, a U-turn neighbor, and ECMP U-turn 905 neighbor or a looping neighbor. The heirarchy among the alternate 906 next-hops is as follows, with the first listed the most preferred. 908 1. Next-hop to a primary neighbor with link and node protection. 910 2. Next-hop to a primary neighbor with at least link protection. 912 3. Next-hop to a loop-free neighbor with link and node protection. 914 4. Next-hop that offers some level of protection. 916 The protection provided by a next-hop that connects to a primary 917 neighbor can be determined in the same way as the protection provided 918 by a next-hop that connects to a loop-free neighbor. These 919 conditions are given in [I-D.ietf-rtgwg-ipfrr-spec-base], but for 920 clarity are briefly repeated below. 922 a. Loop-free for S: 923 D_opt(N_i, D) < D_opt(N_i, S) + D_opt(S, D) 925 b. Path Loop-free for link from S to E: 926 D_opt(N_i, D) < D_opt(N_i, pseudo_S_E) + D_opt(pseudo_S_E, D) 928 c. Candidate next-hop doesn't use the pseudo-node from S to E, if 929 any. 931 d. Loop-free for E: 932 D_opt(N_i, D) < D_opt(N_i, E) + D_opt(E, D) 934 The following describes the alternate selection for a particular 935 primary next-hop to a destination. Initially no alternate next-hop 936 is selected. Each candidate alternate next-hop is considered in turn 937 and either replaces the alternate next-hop or is removed from 938 consideration. This description assumes that a single alternate 939 next-hop is selected; it is possible to have a set of alternate next- 940 hops. In that case, all members MUST be from a set where it is a 941 router-local decision on how to decide among them. 943 If the candidate connects to a primary neighbor and provides link and 944 node protection, then the candidate MUST replace any alternate next- 945 hop lower in the heirarchy. How to handle ties is a router-local 946 decision. If the candidate connects to a primary neighbor and 947 provides only link protection, then the candidate MAY replace any 948 alternate next-hop lower in the heirarchy. 950 If the candidate connects to a loop-free neighbor and provides link 951 protection and node protection, then if the alternate next-hop is not 952 higher on the heirarchy, a decision as to whether to replace the 953 alternate next-hop with the candidate MUST be made as described in 954 Section 4.5.1. 956 Any other type of candidate alternate next-hop MUST NOT replace an 957 alternate next-hop that is higher in the heirarchy. Beyond this 958 restriction, the decision among such candidates is router-local. 960 4.5.1 Selection Between Multiple Loop-Free Node-Protecting Alternate 962 The specific selection policy described in this section is motivated 963 by the ability to reduce the computational complexity associated with 964 identifying U-turn alternates. This mechanism is explained in 965 Section 3. 967 D_opt(R_i_j, D) - D_opt(R_i_j, S) 969 Equation 5: Shortest Reverse-Path-Discounted Distance from R_i_j to D 971 A consequence of this mechanism is that the only path traced during 972 the U-turn SPF is that of the shortest reverse-path-discounted path. 973 A second consequence is that the optimal distance between a 974 neighbor's neighbor and S's primary neighbor E ( D_opt(R_i_j, E) ) is 975 not always known. 977 By constraining the loop-free node-protecting alternate selection as 978 specified below, it is sufficient to know only the path of the 979 shortest reverse-path-discounted path via any of N_i's neighbors. 981 The selection by a router among loop-free link-protecting node- 982 protecting alternates MUST be as follows. 984 Each loop-free node-protecting alternate next-hop is a specific R_i_k 985 where there are K members. The selected R_i_m must be provide the 986 shortest reverse-path-discounted path among all the R_i_j. 988 D_opt(R_i_m, D) - D_opt(R_i_m, S) = 989 min_forall k in K (D_opt(R_i_k, D) - D_opt(R_i_k, S) 991 If there are multiple such R_i_m and one provides the destination, 992 then that one SHOULD be selected. Otherwise, if there are multiple 993 such R_i_m, the router SHOULD make a consistent selection. 995 A consequence of this selection algorithm is that, all else being 996 equal, a more expensive link from an R_i_j will be preferred. This 997 should be considered when determining appropriate metrics for IP 998 traffic-engineering. 1000 5. Using an Alternate 1002 If an alternate is available, it may be used in two circumstances. 1003 The first is when a local failure is detected; the behavior on a 1004 local failure is that specified in [I-D.ietf-rtgwg-ipfrr-spec-base]. 1005 The second is when U-turn packets are received and the alternate is 1006 loop-free and node-protecting. 1008 5.1 Alternate Use On Failure 1010 If an alternate next-hop is available, the router SHOULD redirect 1011 traffic to the alternate next-hop when the primary interface has 1012 failed. If the alternate next-hop provides node protection, the 1013 router SHOULD redirect traffic to the alternate next-hop when the 1014 primary next-hop has failed and the detection of that failure has 1015 occurred within an appropriately short period. The mechanisms 1016 available for failure detection are discussed in [I-D.ietf-rtgwg- 1017 ipfrr-framework] and are outside the scope of this specification. 1019 The alternate next-hop MUST be used only for traffic types which are 1020 routed according to the shortest path. Multicast traffic is 1021 specifically out of scope for this specification. 1023 The details in [I-D.ietf-rtgwg-ipfrr-spec-base] on terminating the 1024 use of the alternate apply equally to U-turn alternates. 1026 Although extremely unlikely in examined topologies, it is 1027 theoretically possible that the convergence on the part of the U-turn 1028 neighbor N_i could cause a short micro-forwarding loop as in the 1029 following topology. 1031 In this example, N provides a U-turn alternate to S via the loop-free 1032 node-protecting alternate A. After the link from S to E fails, N's 1033 alternate continues to function. When N converges, the new primary 1034 next-hop is B; if B has not already converged, then a micro-loop 1035 between N and B could form. 1037 1 +---+ 1 1038 -------| B |------ 1039 | +---+ | 1040 | | 1041 +---+ 1 +---+ 10 +---+ | 1042 | S |----| N |----| A | | 1043 +---+ +---+ +---+ | 1044 1 | 5 | | 1045 +---+ +---+ +---+ 1046 | E | | C | | F | 1047 +---+ +---+ +---+ 1048 | 5 | | 1049 1 | +---+ | 4 1050 |---------------| D |----| 1051 +---+ 1053 Figure 6: Micro-loop Affecting U-turn Alternate 1055 To avoid such an unlikely circumstance, a router SHOULD delay 1056 installation of the new primary and alternate next-hops for a 1057 destination if the failed link is connected to a primary neighbor and 1058 there is a loop-free node-protecting alternate to protect that 1059 primary neighbor and that alternate was not a shortest path to D 1060 (before the failure). 1062 This installation delay SHOULD terminate 1064 a. if the new primary next-hop was loop-free prior to the topology 1065 change, or 1067 b. if a configured hold-down, which represents a worst-case bound on 1068 the length of the network convergence transition, has expired, or 1070 c. if notification of an unrelated topological change in the network 1071 is received. 1073 This delay is required only due to the possibility that the U-turn 1074 alternate next-hop may have a new primary neighbor that was not loop- 1075 free prior to the failure. The loop-free node-protecting alternate 1076 of N_i which goes via R_i,j will not be affected by the failure, 1077 because it was independent of the affected elements. If N_i's new 1078 primary neighbor remains S, then the traffic will continue to be 1079 directed towards the appropriate R_i,j. If N_i converges to a path 1080 that does not include S to reach D, then traffic received from S for 1081 D will be sent along the new path and a micro-forwarding loop is 1082 theoretically possible. 1084 5.2 U-turn Packets Forwarding 1086 If a packet is received from a primary neighbor and is successfully 1087 identified as a U-turn packet (see Section 2.3), then a router which 1088 supports this specification MUST send the packet to the loop-free 1089 node-protecting alternate, selected according to the rules in this 1090 specification, that is associated with the primary next-hop to that 1091 neighbor. If, on a U-turn Recipient capable interface, a packet is 1092 received from a non-primary neighbor (who believes that it is a 1093 primary neighbor) and the packet is marked to indicate that it is a 1094 U-turn packet, then a router which supports this specification MUST 1095 send the packet to a primary next-hop. 1097 6. LDP Interactions and Routing Aspects 1099 6.1 LDP Interactions 1101 U-turn alternates do not impose any additional sessions or signaling 1102 on LDP. LDP can use the U-turn alternates to protect LDP traffic if 1103 the requirements specified in [I-D.ietf-rtgwg-ipfrr-spec-base] are 1104 met. 1106 6.2 Multi-Homed Prefixes 1108 The treatment of multi-homed prefixes is the same as with loop-free 1109 alternates [I-D.ietf-rtgwg-ipfrr-spec-base]. A multi-homed prefix p 1110 can be treated in the SPF computations as a node with uni-directional 1111 links to it from those routers that have advertised the prefix. 1113 If a router is advertising the ability of at least one link to be 1114 implicit or explicit U-turn recipient capable, then a router MUST 1115 compute the alternate next-hop for an IGP multi-homed prefix by 1116 considering alternate paths via all routers that have announced that 1117 prefix. 1119 6.3 OSPF 1121 There are some applicability restrictions for OSPF in regard to loop- 1122 free alternates. Similar ones will apply for U-turn alternates. 1123 Additional restrictions may apply and more details will be available 1124 in the next revision. 1126 6.4 U-turn Alternates Interactions with Tunnels 1128 IP Fast-Reroute treats IGP tunnels the same as any other link. If 1129 router S is not the endpoint of the tunnel, then the alternate path 1130 is computed as normal. If router S is the ingress into the tunnel, 1131 then all destinations, which have the tunnel as a primary next-hop, 1132 may be protected either via a protection scheme associated with the 1133 tunnel or via IP FRR. 1135 One issue with MPLS RSVP-TE tunnels is that an LSP may be created 1136 where the router uses penultimate-hop popping (PHP). If the implicit 1137 U-turn packet identification method is used, then traffic received 1138 via that tunnel is undistinguishable from traffic received over the 1139 interface. If some packets received via the LSP are destined back to 1140 the penultimate hop, then the egress router would consider that those 1141 were U-turn packets and redirect that traffic to its alternate, if 1142 available. To avoid such a scenario, a router can simply not request 1143 PHP for those LSPs which are entering via an interface upon which the 1144 router has advertised that it can break U-Turns. Alternately, a 1145 router could use the explicit U-turn packet identification method. 1146 If that is not supported and the router must do PHP, then the router 1147 can stop advertising the link as U-turn recipient capable. 1149 7. Security Considerations 1151 This document does not introduce any new security issues. The 1152 mechanisms described in this document depend upon the network 1153 topology distributed via an IGP, such as OSPF or ISIS. It is 1154 dependent upon the security associated with those protocols. 1156 8. Acknowledgements 1158 The authors would like to thank Joel Halpern for his helpful review 1159 and comments, particularly as pertains to Section 3. 1161 9. Intellectual Property Considerations 1163 Avici Systems has intellectual property rights claimed in regard to 1164 the specification contained in this document. 1166 10. References 1168 [I-D.ietf-isis-link-attr] 1169 Vasseur, J. and S. Previdi, "Definition of an IS-IS Link 1170 Attribute sub-TLV", draft-ietf-isis-link-attr-01 (work in 1171 progress), May 2005. 1173 [I-D.ietf-rtgwg-ipfrr-framework] 1174 Shand, M. and S. Bryant, "IP Fast Reroute Framework", 1175 draft-ietf-rtgwg-ipfrr-framework-05 (work in progress), 1176 March 2006. 1178 [I-D.ietf-rtgwg-ipfrr-spec-base] 1179 Atlas, A. and A. Zinin, Ed., "Basic Specification for IP 1180 Fast-Reroute: Loop-free Alternates", 1181 draft-ietf-rtgwg-ipfrr-spec-base-05.txt (work in 1182 progress), February 2006. 1184 [ISIS-LOCAL-PROTECT] 1185 Atlas, A., Torvi, R., and C. Martin, "ISIS Extensions to 1186 support U-turn Alternates for IP/LDP Fast-Reroute", 1187 draft-martin-isis-local-protect-cap-02.txt (work in 1188 progress), February 2006. 1190 [OSPF-LOCAL-PROTECT] 1191 Atlas, A., Torvi, R., Choudhury, G., Martin, C., Imhoff, 1192 B., and D. Fedyk, "OSPFv2 Extensions for Link Capabilities 1193 to support U-turn Alternates for IP/LDP Fast-Reroute", 1194 draft-atlas-ospf-local-protect-cap-02.txt (work in 1195 progress), February 2006. 1197 [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and 1198 dual environments", RFC 1195, December 1990. 1200 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 1202 [RFC2370] Coltun, R., "The OSPF Opaque LSA Option", RFC 2370, 1203 July 1998. 1205 [RFC2966] Li, T., Przygienda, T., and H. Smit, "Domain-wide Prefix 1206 Distribution with Two-Level IS-IS", RFC 2966, 1207 October 2000. 1209 [RFC3036] Andersson, L., Doolan, P., Feldman, N., Fredette, A., and 1210 B. Thomas, "LDP Specification", RFC 3036, January 2001. 1212 [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. 1213 McPherson, "OSPF Stub Router Advertisement", RFC 3137, 1214 June 2001. 1216 [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., 1217 and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP 1218 Tunnels", RFC 3209, December 2001. 1220 [RFC3277] McPherson, D., "Intermediate System to Intermediate System 1221 (IS-IS) Transient Blackhole Avoidance", RFC 3277, 1222 April 2002. 1224 Authors' Addresses 1226 Alia K. Atlas (editor) 1227 Google, Inc. 1228 1600 Amphitheatre Parkway 1229 Mountain View, CA 94043 1230 USA 1232 Email: akatlas@alum.mit.edu 1234 Raveendra Torvi 1235 Avici Systems, Inc. 1236 101 Billerica Avenue 1237 N. Billerica, MA 01862 1238 USA 1240 Phone: +1 978 964 2026 1241 Email: rtorvi@avici.com 1243 Gagan Choudhury 1244 AT&T 1245 200 Laurel Avenue, Room D5-3C21 1246 Middletown, NJ 07748 1247 USA 1249 Phone: +1 732 420-3721 1250 Email: gchoudhury@att.com 1252 Christian Martin 1253 iPath Technologies 1255 Email: chris@ipath.net 1257 Brent Imhoff 1258 Juniper Networks 1259 1194 North Mathilda 1260 Sunnyvale, CA 94089 1261 USA 1263 Phone: +1 314 378 2571 1264 Email: bimhoff@planetspork.com 1265 Don Fedyk 1266 Nortel Networks 1267 600 Technology Park 1268 Billerica, MA 01821 1269 USA 1271 Phone: +1 978 288 3041 1272 Email: dwfedyk@nortelnetworks.com 1274 Intellectual Property Statement 1276 The IETF takes no position regarding the validity or scope of any 1277 Intellectual Property Rights or other rights that might be claimed to 1278 pertain to the implementation or use of the technology described in 1279 this document or the extent to which any license under such rights 1280 might or might not be available; nor does it represent that it has 1281 made any independent effort to identify any such rights. Information 1282 on the procedures with respect to rights in RFC documents can be 1283 found in BCP 78 and BCP 79. 1285 Copies of IPR disclosures made to the IETF Secretariat and any 1286 assurances of licenses to be made available, or the result of an 1287 attempt made to obtain a general license or permission for the use of 1288 such proprietary rights by implementers or users of this 1289 specification can be obtained from the IETF on-line IPR repository at 1290 http://www.ietf.org/ipr. 1292 The IETF invites any interested party to bring to its attention any 1293 copyrights, patents or patent applications, or other proprietary 1294 rights that may cover technology that may be required to implement 1295 this standard. Please address the information to the IETF at 1296 ietf-ipr@ietf.org. 1298 Disclaimer of Validity 1300 This document and the information contained herein are provided on an 1301 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1302 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 1303 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 1304 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 1305 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1306 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1308 Copyright Statement 1310 Copyright (C) The Internet Society (2006). This document is subject 1311 to the rights, licenses and restrictions contained in BCP 78, and 1312 except as set forth therein, the authors retain all their rights. 1314 Acknowledgment 1316 Funding for the RFC Editor function is currently provided by the 1317 Internet Society.