idnits 2.17.1 draft-ietf-rtgwg-ipfrr-spec-base-11.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 16. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 1376. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1387. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1394. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1400. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year -- 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 (Feb 24, 2008) is 5899 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Obsolete normative reference: RFC 2740 (Obsoleted by RFC 5340) ** Obsolete normative reference: RFC 3036 (Obsoleted by RFC 5036) == Outdated reference: A later version (-23) exists of draft-ietf-ospf-ospfv3-update-18 == Outdated reference: A later version (-13) exists of draft-ietf-rtgwg-ipfrr-framework-07 -- Obsolete informational reference (is this intentional?): RFC 2966 (Obsoleted by RFC 5302) -- Obsolete informational reference (is this intentional?): RFC 3137 (Obsoleted by RFC 6987) -- Obsolete informational reference (is this intentional?): RFC 4205 (Obsoleted by RFC 5307) Summary: 3 errors (**), 0 flaws (~~), 3 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Routing Area Working Group A. Atlas, Ed. 3 Internet-Draft BT 4 Intended status: Standards Track A. Zinin, Ed. 5 Expires: August 27, 2008 Alcatel 6 Feb 24, 2008 8 Basic Specification for IP Fast-Reroute: Loop-free Alternates 9 draft-ietf-rtgwg-ipfrr-spec-base-11 11 Status of this Memo 13 By submitting this Internet-Draft, each author represents that any 14 applicable patent or other IPR claims of which he or she is aware 15 have been or will be disclosed, and any of which he or she becomes 16 aware will be disclosed, in accordance with Section 6 of BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as 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 This Internet-Draft will expire on August 27, 2008. 36 Copyright Notice 38 Copyright (C) The IETF Trust (2008). 40 Abstract 42 This document describes the use of loop-free alternates to provide 43 local protection for unicast traffic in pure IP and MPLS/LDP networks 44 in the event of a single failure, whether link, node or shared risk 45 link group (SRLG). The goal of this technology is to reduce the 46 packet loss that happens while routers converge after a topology 47 change due to a failure. Rapid failure repair is achieved through 48 use of precalculated backup next-hops that are loop-free and safe to 49 use until the distributed network convergence process completes. 50 This simple approach does not require any support from other routers. 51 The extent to which this goal can be met by this specification is 52 dependent on the topology of the network. 54 Table of Contents 56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 57 1.1. Failure Scenarios . . . . . . . . . . . . . . . . . . . . 5 58 2. Applicability of Described Mechanisms . . . . . . . . . . . . 8 59 3. Alternate Next-Hop Calculation . . . . . . . . . . . . . . . . 9 60 3.1. Basic Loop-free Condition . . . . . . . . . . . . . . . . 10 61 3.2. Node-Protecting Alternate Next-Hops . . . . . . . . . . . 10 62 3.3. Broadcast and NBMA Links . . . . . . . . . . . . . . . . . 11 63 3.4. ECMP and Alternates . . . . . . . . . . . . . . . . . . . 12 64 3.5. Interactions with ISIS Overload, RFC 3137 and Costed 65 Out Links . . . . . . . . . . . . . . . . . . . . . . . . 13 66 3.5.1. Interactions with ISIS Link Attributes . . . . . . . . 14 67 3.6. Selection Procedure . . . . . . . . . . . . . . . . . . . 14 68 3.7. LFA types and Trade-offs . . . . . . . . . . . . . . . . . 18 69 3.8. A Simplification: Per-Next-Hop LFAs . . . . . . . . . . . 19 70 4. Using an Alternate . . . . . . . . . . . . . . . . . . . . . . 20 71 4.1. Terminating Use of Alternate . . . . . . . . . . . . . . . 20 72 5. Requirements on LDP Mode . . . . . . . . . . . . . . . . . . . 22 73 6. Routing Aspects . . . . . . . . . . . . . . . . . . . . . . . 22 74 6.1. Multi-Homed Prefixes . . . . . . . . . . . . . . . . . . . 22 75 6.2. ISIS . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 76 6.3. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 77 6.3.1. OSPF External Routing . . . . . . . . . . . . . . . . 24 78 6.3.2. OSPF Multi-Topology . . . . . . . . . . . . . . . . . 25 79 6.4. BGP Next-Hop Synchronization . . . . . . . . . . . . . . . 25 80 6.5. Multicast Considerations . . . . . . . . . . . . . . . . . 25 81 7. Security Considerations . . . . . . . . . . . . . . . . . . . 25 82 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 83 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 26 84 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 26 85 10.1. Normative References . . . . . . . . . . . . . . . . . . . 26 86 10.2. Informative References . . . . . . . . . . . . . . . . . . 26 87 Appendix A. OSPF Example Where LFA Based on Local Area 88 Topology is Insufficient . . . . . . . . . . . . . . 27 89 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 28 90 Intellectual Property and Copyright Statements . . . . . . . . . . 31 92 1. Introduction 94 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 95 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 96 document are to be interpreted as described in RFC 2119. [RFC2119] 98 Applications for interactive multimedia services such as VoIP and 99 pseudo-wires can be very sensitive to traffic loss, such as occurs 100 when a link or router in the network fails. A router's convergence 101 time is generally on the order of hundreds of milliseconds; the 102 application traffic may be sensitive to losses greater than tens of 103 milliseconds. 105 As discussed in [I-D.ietf-rtgwg-ipfrr-framework], minimizing traffic 106 loss requires a mechanism for the router adjacent to a failure to 107 rapidly invoke a repair path, which is minimally affected by any 108 subsequent re-convergence. This specification describes such a 109 mechanism which allows a router whose local link has failed to 110 forward traffic to a pre-computed alternate until the router installs 111 the new primary next-hops based upon the changed network topology. 112 The terminology used in this specification is given in 113 [I-D.ietf-rtgwg-ipfrr-framework]. The described mechanism assumes 114 that routing in the network is performed using a link-state routing 115 protocol-- OSPF [RFC2328] [RFC2740] [I-D.ietf-ospf-ospfv3-update] or 116 ISIS [RFC1195] [RFC2966] (for IPv4 or IPv6). The mechanism also 117 assumes that both the primary path and the alternate path are in the 118 same routing area. 120 When a local link fails, a router currently must signal the event to 121 its neighbors via the IGP, recompute new primary next-hops for all 122 affected prefixes, and only then install those new primary next-hops 123 into the forwarding plane. Until the new primary next-hops are 124 installed, traffic directed towards the affected prefixes is 125 discarded. This process can take hundreds of milliseconds. 127 <-- 128 +-----+ 129 /------| S |--\ 130 / +-----+ \ 131 / 5 8 \ 132 / \ 133 +-----+ +-----+ 134 | E | | N_1 | 135 +-----+ +-----+ 136 \ / 137 \ \ 4 3 / / 138 \| \ / |/ 139 -+ \ +-----+ / +- 140 \---| D |---/ 141 +-----+ 143 Figure 1: Basic Topology 145 The goal of IP Fast-Reroute is to reduce failure reaction time to 10s 146 of milliseconds by using a pre-computed alternate next-hop, in the 147 event that the currently selected primary next-hop fails, so that the 148 alternate can be rapidly used when the failure is detected. A 149 network with this feature experiences less traffic loss and less 150 micro-looping of packets than a network without IPFRR. There are 151 cases where traffic loss is still a possibility since IPFRR coverage 152 varies but in the worst possible situation a network with IPFRR is 153 equivalent with respect to traffic convergence to a network without 154 IPFRR. 156 To clarify the behavior of IP Fast-Reroute, consider the simple 157 topology in Figure 1. When router S computes its shortest path to 158 router D, router S determines to use the link to router E as its 159 primary next-hop. Without IP Fast-Reroute, that link is the only 160 next-hop that router S computes to reach D. With IP Fast-Reroute, S 161 also looks for an alternate next-hop to use. In this example, S 162 would determine that it could send traffic destined to D by using the 163 link to router N_1 and therefore S would install the link to N_1 as 164 its alternate next-hop. At some later time, the link between router 165 S and router E could fail. When that link fails, S and E will be the 166 first to detect it. On detecting the failure, S will stop sending 167 traffic destined for D towards E via the failed link, and instead 168 send the traffic to S's pre-computed alternate next-hop, which is the 169 link to N_1, until a new SPF is run and its results are installed. 170 As with the primary next-hop, an alternate next-hop is computed for 171 each destination. The process of computing an alternate next-hop 172 does not alter the primary next-hop computed via a standard SPF. 174 If in the example of Figure 1, the link cost from N_1 to D increased 175 to 30 from 3, then N_1 would not be a loop-free alternate, because 176 the cost of the path from N_1 to D via S would be 17 while the cost 177 from N_1 directly to D would be 30. In real networks, we may often 178 face this situation. The existence of a suitable loop-free alternate 179 next-hop is dependent on the topology and the nature of the failure 180 the alternate is calculated for. 182 This specification uses the terminology introduced in 183 [I-D.ietf-rtgwg-ipfrr-framework]. In particular, it uses 184 Distance_opt(X,Y), abbreviated to D_opt(X,Y), to indicate the 185 shortest distance from X to Y. S is used to indicate the calculating 186 router. N_i is a neighbor of S; N is used as an abbreviation when 187 only one neighbor is being discussed. D is the destination under 188 consideration. 190 A neighbor N can provide a loop-free alternate (LFA) if and only if 192 Distance_opt(N, D) < Distance_opt(N, S) + Distance_opt(S, D) 194 Inequality 1: Loop-Free Criterion 196 A sub-set of loop-free alternate are downstream paths which must meet 197 a more restrictive condition that is applicable to more complex 198 failure scenarios: 200 Distance_opt(N, D) < Distance_opt(S, D) 202 Inequality 2: Downstream Path Criterion 204 1.1. Failure Scenarios 206 The alternate next-hop can protect against a single link failure, a 207 single node failure, failure of one or more links within a shared 208 risk link group failures, or a combination of these. Whenever a 209 failure occurs that is more extensive than what the alternate was 210 intended to protect, there is the possibility of temporarily looping 211 traffic (note again, that such a loop would only last until the next 212 complete SPF calculation). The example where a node fails when the 213 alternate provided only link protection is illustrated below. If 214 unexpected simultaneous failures occur, then micro-looping may occur 215 since the alternates are not pre-computed to avoid the set of failed 216 links. 218 If only link protection is provided and the node fails, it is 219 possible for traffic using the alternates to experience micro- 220 looping. This issue is illustrated in Figure 2. If Link(S->E) 221 fails, then the link-protecting alternate via N will work correctly. 222 However, if router E fails, then both S and N will detect a failure 223 and switch to their alternates. In this example, that would cause S 224 to redirect the traffic to N and N to redirect the traffic to S and 225 thus causing a forwarding loop. Such a scenario can arise because 226 the key assumption, that all other routers in the network are 227 forwarding based upon the shortest path, is violated because of a 228 second simultaneous correlated failure - another link connected to 229 the same primary neighbor. If there are not other protection 230 mechanisms to handle node failure, a node failure is still a concern 231 when only using link protecting LFAs. 233 <@@@ 234 @@@> 235 +-----+ +-----+ 236 | S |-------| N | 237 +-+---+ 5 +-----+ 238 | | 239 | 5 4 | | 240 | | | \|/ 241 \|/ | | 242 | +-----+ | 243 +----| E |---+ 244 +--+--+ 245 | 246 | 247 | 10 248 | 249 +--+--+ 250 | D | 251 +-----+ 253 Figure 2: Link-Protecting Alternates Causing Loop on Node Failure 255 Micro-looping of traffic via the alternates caused when a more 256 extensive failure than planned for occurs can be prevented via 257 selection of only downstream paths as alternates. A micro-loop due 258 to the use of alternates can be avoided by using downstream paths 259 because each succeeding router in the path to the destination must be 260 closer to the destination than its predecessor (according to the 261 topology prior to the failures). Although use of downstream paths 262 ensures that the micro-looping via alternates does not occur, such a 263 restriction can severely limit the coverage of alternates. In 264 Figure 2, S would be able to use N as a downstream alternate, but N 265 could not use S; therefore N would have no alternate and would 266 discard the traffic, thus avoiding the micro-loop. 268 As shown above, the use of either a node protecting LFA (described in 269 Section 3.2) or a downstream path provides protection against micro- 270 looping in the event of node failure. There are topologies where 271 there may be either a node portecting LFA, a downstream path, both or 272 neither. A node may select either a node protecting LFA or a 273 downstream path without risk of causing micro-loops in the event of 274 neighbor node failure. While a link-and-node-protecting LFA 275 guarantees protection against either link or node failure, a 276 downstream path provides protection only against a link failure and 277 may or may not provide protection against a node failure depending on 278 the protection available at the downstream node, but it cannot cause 279 a micro-loop. For example in Figure 2, if S uses N as a downstream 280 path, although no looping can occur, the traffic will not be 281 protected in the event of the failure of node E because N has no 282 viable repair path, and it will simply discard the packet. However, 283 if N had a link and node protecting LFA or downstream path via some 284 other path (not shown), then the repair may succeed. 286 Since the functionality of link and node protecting LFAs is greater 287 than that of link protecting downstream paths, a router SHOULD select 288 a link and node protecting LFA over a link protecting downstream 289 path. If there are any destinations for which a link and node 290 protecting LFA is not available, then by definition the path to all 291 of those destinations from any neighbor of the computing router (S) 292 must be through the node (E) being protected (otherwise there would 293 be a node protecting LFA for that destination). Consequently, if 294 there exists a downstream path to the protected node as destination, 295 then that downstream path may be used for all those destinations for 296 which a link and node protecting LFA is not available; the existence 297 of a downstream path can be determined by a single check of the 298 condition Distance_opt(N, E) < Distance_opt(S, E). 300 It may be desirable to find an alternate that can protect against 301 other correlated failures (of which node failure is a specific 302 instance). In the general case, these are handled by shared risk 303 link groups (SRLGs) where any links in the network can belong to the 304 SRLG. General SRLGs may add unacceptably to the computational 305 complexity of finding a loop-free alternate. 307 However, a sub-category of SRLGs is of interest and can be applied 308 only during the selection of an acceptable alternate. This sub- 309 category is to express correlated failures of links that are 310 connected to the same router. For example, if there are multiple 311 logical sub-interfaces on the same physical interface, such as VLANs 312 on an Ethernet interface, if multiple interfaces use the same 313 physical port because of channelization, or if multiple interfaces 314 share a correlated failure because they are on the same line-card. 315 This sub-category of SRLGs will be referred to as local-SRLGs. A 316 local-SRLG has all of its member links with one end connected to the 317 same router. Thus, router S could select a loop-free alternate which 318 does not use a link in the same local-SRLG as the primary next-hop. 319 The local-SRLGs belonging to E can be protected against via node- 320 protection; i.e. picking a loop-free node-protecting alternate. 322 Where SRLG protection is provided, it is in the context of the 323 particular OSPF or ISIS area, whose topology is used in the SPF 324 computations to compute the loop-free alternates. If an SRLG 325 contains links in multiple areas, then separate SRLG-protecting 326 alternates would be required in each area that is traversed by the 327 affected traffic. 329 2. Applicability of Described Mechanisms 331 IP Fast Reroute mechanisms described in this memo cover intra-domain 332 routing only, with OSPF[RFC2328] or ISIS [RFC1195] [RFC2966] as the 333 IGP. Specifically, Fast Reroute for BGP inter-domain routing is not 334 part of this specification. 336 Certain aspects of OSPF inter-area routing behavior explained in 337 Section 6.3 and Appendix A impact the ability of the router 338 calculating the backup next-hops to assess traffic trajectories. In 339 order to avoid micro-looping and ensure required coverage, certain 340 constraints are applied to multi-area OSPF networks: 342 a. Loop-free alternates should not be used in the backbone area if 343 there are any virtual links configured unless, for each transit 344 area, there is a full mesh of virtual links between all ABRs in 345 that area. Loop-free alternates may be used in non-backbone 346 areas regardless of whether there are virtual links configured. 348 b. Loop-free alternates should not be used for inter-area routes in 349 an area that contains more than one alternate ABR. [RFC3509] 351 c. Loop-free alternates should not be used for AS External routes or 352 ASBR routes in a non-backbone area of a network where there 353 exists an ABR that is announced as an ASBR in multiple non- 354 backbone areas and there exists another ABR that is in at least 355 two of the same non-backbone areas. 357 d. Loop-free alternates should not be used in a non-backbone area of 358 a network for AS External routes where an AS External prefix is 359 advertised with the same type of external metric by multiple 360 ASBRs, which are in different non-backbone areas, with a 361 forwarding address of 0.0.0.0 or by one or more ASBRs with 362 forwarding addresses in multiple non-backbone areas when an ABR 363 exists simultaneously in two or more of those non-backbone areas. 365 3. Alternate Next-Hop Calculation 367 In addition to the set of primary next-hops obtained through a 368 shortest path tree (SPT) computation that is part of standard link- 369 state routing functionality, routers supporting IP Fast Reroute also 370 calculate a set of backup next hops that are engaged when a local 371 failure occurs. These backup next hops are calculated to provide the 372 required type of protection (i.e. link-protecting and/or node- 373 protecting) and to guarantee that when the expected failure occurs, 374 forwarding traffic through them will not result in a loop. Such next 375 hops are called loop-free alternates or LFAs throughout this 376 specification. 378 In general, to be able to calculate the set of LFAs for a specific 379 destination D, a router needs to know the following basic pieces of 380 information: 382 o Shortest-path distance from the calculating router to the 383 destination (Distance_opt(S, D)) 385 o Shortest-path distance from the router's IGP neighbors to the 386 destination (Distance_opt(N, D)) 388 o Shortest path distance from the router's IGP neighbors to itself 389 (Distance_opt(N, S)) 391 o Distance_opt(S, D) is normally available from the regular SPF 392 calculation performed by the link-state routing protocols. 393 Distance_opt(N, D) and Distance_opt(N, S) can be obtained by 394 performing additional SPF calculations from the perspective of 395 each IGP neighbor (i.e. considering the neighbor's vertex as the 396 root of the SPT--called SPT(N) hereafter--rather than the 397 calculating router's one, called SPT(S)). 399 This specification defines a form of SRLG protection limited to those 400 SRLGs that include a link that the calculating router is directly 401 connected to. Only that set of SRLGs could cause a local failure; 402 the calculating router only computes alternates to handle a local 403 failure. Information about local link SRLG membership is manually 404 configured. Information about remote link SRLG membership may be 405 dynamically obtained using [RFC4205] or [RFC4203]. Define 406 SRLG_local(S) to be the set of SRLGs that include a link that the 407 calculating router S is directly connected to. Only SRLG_local(S) is 408 of interest during the calculation, but the calculating router must 409 correctly handle changes to SRLG_local(S) triggered by local link 410 SRLG membership changes. 412 In order to choose among all available LFAs that provide required 413 SRLG protection for a given destination, the calculating router needs 414 to track the set of SRLGs in SRLG_local(S) that the path through a 415 specific IGP neighbor involves. To do so, each node D in the network 416 topology is associated with SRLG_set(N, D), which is the set of SRLGs 417 that would be crossed if traffic to D was forwarded through N. To 418 calculate this set, the router initializes SRLG_set(N, N) for each of 419 its IGP neighbors to be empty. During the SPT(N) calculation, when a 420 new vertex V is added to the SPT, its SRLG_set(N, V) is set to the 421 union of SRLG sets associated with its parents, and the SRLG sets in 422 SRLG_local(S) that are associated with the links from V's parents to 423 V. The union of the set of SRLG associated with a candidate alternate 424 next-hop and the SRLG_set(N, D) for the neighbor reached via that 425 candidate next-hop is used to determine SRLG protection. 427 The following sections provide information required for calculation 428 of LFAs. Sections Section 3.1 through Section 3.4 define different 429 types of LFA conditions. Section 3.5 describes constraints imposed 430 by the IS-IS overload and OSPF stub router functionality. 431 Section 3.6 defines the summarized algorithm for LFA calculation 432 using the definitions in the previous sections. 434 3.1. Basic Loop-free Condition 436 Alternate next hops used by implementations following this 437 specification MUST conform to at least the loop-freeness condition 438 stated above in Inequality 1. This condition guarantees that 439 forwarding traffic to an LFA will not result in a loop after a link 440 failure. 442 Further conditions may be applied when determining link-protecting 443 and/or node-protecting alternate next-hops as described in Sections 444 Section 3.2 and Section 3.3. 446 3.2. Node-Protecting Alternate Next-Hops 448 For an alternate next-hop N to protect against node failure of a 449 primary neighbor E for destination D, N must be loop-free with 450 respect to both E and D. In other words, N's path to D must not go 451 through E. This is the case if Inequality 3 is true, where N is the 452 neighbor providing a loop-free alternate. 454 Distance_opt(N, D) < Distance_opt(N, E) + Distance_opt(E, D) 456 Inequality 3: Criteria for a Node-Protecting Loop-Free Alternate 458 If Distance_opt(N,D) = Distance_opt(N, E) + Distance_opt(E, D), it is 459 possible that N has equal-cost paths and one of those could provide 460 protection against E's node failure. However, it is equally possible 461 that one of N's paths goes through E, and the calculating router has 462 no way to influence N's decision to use it. Therefore, it SHOULD be 463 assumed that an alternate next-hop does not offer node protection if 464 Inequality 3 is not met. 466 3.3. Broadcast and NBMA Links 468 Verification of the link-protection property of a next hop in the 469 case of a broadcast link is more elaborate than for a point-to-point 470 link. This is because a broadcast link is represented as a pseudo- 471 node with zero-cost links connecting it to other nodes. 473 Because failure of an interface attached to a broadcast segment may 474 mean loss of connectivity of the whole segment, the condition 475 described for broadcast link protection is pessimistic and requires 476 that the alternate is loop-free with regard to the pseudo-node. 477 Consider the example in Figure 3. 479 +-----+ 15 480 | S |-------- 481 +-----+ | 482 | 5 | 483 | | 484 | 0 | 485 /----\ 0 5 +-----+ 486 | PN |-----| N | 487 \----/ +-----+ 488 | 0 | 489 | | 8 490 | 5 | 491 +-----+ 5 +-----+ 492 | E |----| D | 493 +-----+ +-----+ 495 Figure 3: Loop-Free Alternate that is Link-Protecting 497 In Figure 3, N offers a loop-free alternate which is link-protecting. 498 If the primary next-hop uses a broadcast link, then an alternate 499 SHOULD be loop-free with respect to that link's pseudo-node (PN) to 500 provide link protection. This requirement is described in 501 Inequality 4 below. 503 D_opt(N, D) < D_opt(N, PN) + D_opt(PN, D) 505 Inequality 4: Loop-Free Link-Protecting Criterion for Broadcast Links 507 Because the shortest path from the pseudo-node goes through E, if a 508 loop-free alternate from a neighbor N is node-protecting, the 509 alternate will also be link-protecting unless the router S can only 510 reach the alternate neighbor N via the same pseudo-node. Since this 511 is the only case for which a node-protecting LFA is not link- 512 protecting, this implies that for point-to-point interfaces, an LFA 513 that is node-protecting is always link-protecting. Because S can 514 direct the traffic away from the shortest path to use the alternate 515 N, traffic might pass through the same broadcast link as it would 516 when S sent the traffic to the primary E. Thus, an LFA from N that is 517 node-protecting is not automatically link-protecting for a broadcast 518 or NBMA link. 520 To obtain link protection, it is necessary both that the path from 521 the selected alternate next-hop does not traverse the link of 522 interest and that the link used from S to reach that alternate next- 523 hop is not the link of interest. The latter can only occur with non- 524 point-to-point links. Therefore, if the primary next-hop is across a 525 broadcast or NBMA interface, it is necessary to consider link 526 protection during the alternate selection. To clarify, consider the 527 topology in Figure 3. For N to provide link-protection, it is first 528 necessary that N's shortest path to D does not traverse the pseudo- 529 node PN. Second, it is necessary that the alternate next-hop 530 selected by S does not traverse PN. In this example, S's shortest 531 path to N is via the pseudo-node. Thus, to obtain link-protection, S 532 must find a next-hop to N (the point-to-point link from S to N in 533 this example) that avoids the pseudo-node PN. 535 Similar consideration of the link from S to the selected alternate 536 next-hop as well as the path from the selected alternate next-hop is 537 also necessary for SRLG protection. S's shortest path to the 538 selected neighbor N may not be acceptable as an alternate next-hop to 539 provide SRLG protection, even if the path from N to D can provide 540 SRLG protection. 542 3.4. ECMP and Alternates 544 With equal-cost multi-path, a prefix may have multiple primary next- 545 hops that are used to forward traffic. When a particular primary 546 next-hop fails, alternate next-hops should be used to preserve the 547 traffic. These alternate next-hops may themselves also be primary 548 next-hops, but need not be. Other primary next-hops are not 549 guaranteed to provide protection against the failure scenarios of 550 concern. 552 20 L1 L3 3 553 [ N ]----[ S ]--------[ E3 ] 554 | | | 555 | 5 | L2 | 556 20 | | | 557 | --------- | 2 558 | 5 | | 5 | 559 | [ E1 ] [ E2 ]-----| 560 | | | 561 | 10 | 10 | 562 |---[ A ] [ B ] 563 | | 564 2 |--[ D ]-| 2 566 Figure 4: ECMP where Primary Next-Hops Provide Limited Protection 568 In Figure 4 S has three primary next-hops to reach D; these are L2 to 569 E1, L2 to E2 and L3 to E3. The primary next-hop L2 to E1 can obtain 570 link and node protection from L3 to E3, which is one of the other 571 primary next-hops; L2 to E1 cannot obtain link protection from the 572 other primary next-hop L2 to E2. Similarly, the primary next-hop L2 573 to E2 can only get node protection from L2 to E1 and can only get 574 link protection from L3 to E3. The third primary next-hop L3 to E3 575 can obtain link and node protection from L2 to E1 and from L2 to E2. 576 It is possible for both the primary next-hop L2 to E2 and the primary 577 next-hop L2 to E1 to obtain an alternate next-hop that provides both 578 link and node protection by using L1. 580 Alternate next-hops are determined for each primary next-hop 581 separately. As with alternate selection in the non-ECMP case, these 582 alternate next-hops should maximize the coverage of the failure 583 cases. 585 3.5. Interactions with ISIS Overload, RFC 3137 and Costed Out Links 587 As described in [RFC3137], there are cases where it is desirable not 588 to have a router used as a transit node. For those cases, it is also 589 desirable not to have the router used on an alternate path. 591 For computing an alternate, a router MUST NOT use an alternate next- 592 hop that is along a link whose cost or reverse cost is LSInfinity 593 (for OSPF) or the maximum cost (for ISIS) or which has the overload 594 bit set (for ISIS). For a broadcast link, the reverse cost 595 associated with a potential alternate next-hop is the cost towards 596 the pseudo-node advertised by the next-hop router. For point-to- 597 point links, if a specific link from the next-hop router cannot be 598 associated with a particular link, then the reverse cost considered 599 is that of the minimum cost link from the next-hop router back to S. 601 In the case of OSPF, if all links from router S to a neighbor N_i 602 have a reverse cost of LSInfinity, then router S MUST NOT use N_i as 603 an alternate. 605 Similarly in the case of ISIS, if N_i has the overload bit set, then 606 S MUST NOT consider using N_i as an alternate. 608 This preserves the desired behavior of diverting traffic away from a 609 router which is following [RFC3137] and it also preserves the desired 610 behavior when an operator sets the cost of a link to LSInfinity for 611 maintenance which is not permitting traffic across that link unless 612 there is no other path. 614 If a link or router which is costed out was the only possible 615 alternate to protect traffic from a particular router S to a 616 particular destination, then there should be no alternate provided 617 for protection. 619 3.5.1. Interactions with ISIS Link Attributes 621 [I-D.ietf-isis-link-attr] describes several flags whose interactions 622 with LFAs needs to be defined. A router SHOULD NOT specify the 623 "local protection available" flag as a result of having LFAs. A 624 router SHOULD NOT use an alternate next-hop that is along a link for 625 which the link has been advertised with the attribute "link excluded 626 from local protection path" or with the attribute "local maintenance 627 required". 629 3.6. Selection Procedure 631 A router supporting this specification SHOULD attempt to select at 632 least one loop-free alternate next-hop for each primary next-hop used 633 for a given prefix. A router MAY decide to not use an available 634 loop-free alternate next-hop. A reason for such a decision might be 635 that the loop-free alternate next-hop does not provide protection for 636 the failure scenario of interest. 638 The alternate selection should maximize the coverage of the failure 639 cases. 641 When calculating alternate next-hops, the calculating router S 642 applies the following rules. 644 1. S SHOULD select a loop-free node-protecting alternate next-hop, 645 if one is available. If no loop-free node-protecting alternate 646 is available, then S MAY select a loop-free link-protecting 647 alternate. 649 2. If S has a choice between a loop-free link-protecting node- 650 protecting alternate and a loop-free node-protecting alternate 651 which is not link-protecting, S SHOULD select a loop-free node- 652 protecting alternate which is also link-protecting. This can 653 occur as explained in Section 3.3. 655 3. If S has multiple primary next-hops, then S SHOULD select as a 656 loop-free alternate either one of the other primary next-hops or 657 a loop-free node-protecting alternate if available. If no loop- 658 free node-protecting alternate is available and no other primary 659 next-hop can provide link-protection, then S SHOULD select a 660 loop-free link-protecting alternate. 662 4. Implementations SHOULD support a mode where other primary next- 663 hops satisfying the basic loop-free condition and providing at 664 least link or node protection are preferred over any non-primary 665 alternates. This mode is provided to allow the administrator to 666 preserve traffic patterns based on regular ECMP behavior. 668 5. Implementations considering SRLGs MAY use SRLG-protection to 669 determine that a node-protecting or link-protecting alternate is 670 not available for use. 672 Following the above rules maximizes the level of protection and use 673 of primary (ECMP) next-hops. 675 Each next-hop is associated with a set of non-mutually-exclusive 676 characteristics based on whether it is used as a primary next-hop to 677 a particular destination D, and the type of protection it can provide 678 relative to a specific primary next-hop E: 680 Primary Path - The next-hop is used by S as primary. 682 Loop-Free Node-Protecting Alternate - This next-hop satisfies 683 Inequality 1 and Inequality 3. The path avoids S, S's primary 684 neighbor E, and the link from S to E. 686 Loop-Free Link-Protecting Alternate - This next-hop satisfies 687 Inequality 1 but not Inequality 3. If the primary next-hop uses a 688 broadcast link, then this next-hop satisfies Inequality 4. 690 An alternate path may also provide none, some or complete SRLG 691 protection as well as node and link or link protection. For 692 instance, a link may belong to two SRLGs G1 and G2. The alternate 693 path might avoid other links in G1 but not G2, in which case the 694 alternate would only provide partial SRLG protection. 696 Below is an algorithm that can be used to calculate loop-free 697 alternate next-hops. The algorithm is given for informational 698 purposes and implementations are free to use any other algorithm as 699 long as it satisfies the rules described above. 701 The following procedure describes how to select an alternate next- 702 hop. The procedure is described to determine alternate next-hops to 703 use to reach each router in the topology. Prefixes that are 704 advertised by a single router can use the alternate next-hop computed 705 for the router to which they are attached. The same procedure can be 706 used to reach a prefix that is advertised by more than one router 707 when the logical topological transformation described in Section 6.1 708 is used. 710 S is the computing router. S has neighbors N_1 to N_j. A candidate 711 next-hop is indicated by (outgoing link, neighbor) and the outgoing 712 link must be bidirectionally connected, as is determined by the IGP. 713 The candidate next-hops of S are enumerated as H_1 through H_k. 714 Recall that S may have multiple next hops over different interfaces 715 to a neighbor. H_i.link refers to the outgoing link of that next-hop 716 and H_i.neighbor refers to the neighbor of that nexthop. 718 For a particular destination router D, let S have already computed 719 D_opt(S, D), and for each neighbor N_i, D_opt(N_i, D), D_opt(N_i, S), 720 and D_opt(N_i, N_j), the distance from N_i to each other neighbor 721 N_j, and the set of SRLGs traversed by the path D_opt(N_i, D). S 722 should follow the below procedure for every primary next-hop selected 723 to reach D. This set of primary next-hops is represented P_1 to P_p. 724 This procedure finds the alternate next-hop(s) for P_i. 726 First, initialize the alternate information for P_i as follows: 728 P_i.alt_next_hops = {} 729 P_i.alt_type = NONE 730 P_i.alt_link-protect = FALSE 731 P_i.alt_node-protect = FALSE 732 P_i.alt_srlg-protect = {} 734 For each candidate next-hop H_h, 736 1. Initialize variables as follows: 738 cand_type = NONE 739 cand_link-protect = FALSE 740 cand_node-protect = FALSE 741 cand_srlg-protect = {} 743 2. If H_h is P_i, skip it and continue to the next candidate next- 744 hop. 746 3. If H_h.link is administratively allowed to be used as an 747 alternate, 749 and the cost of H_h.link is less than the maximum, 750 and the reverse cost of H_h is less than the maximum, 751 and H_h.neighbor is not overloaded (for ISIS), 752 and H_h.link is bi-directional, 754 then H_h can be considered as an alternate. Otherwise, skip it 755 and continue to the next candidate next-hop. 757 4. If D_opt( H_h.neighbor, D) >= D_opt( H_h.neighbor, S) + D_opt(S, 758 D), then H_h is not loop-free. Skip it and continue to the next 759 candidate next-hop. 761 5. cand_type = LOOP-FREE. 763 6. If H_h is a primary next-hop, set cand_type to PRIMARY. 765 7. If H_h.link is not P_i.link, set cand_link-protect to TRUE. 767 8. If D_opt(H_h.neighbor, D) < D_opt(H_h.neighbor, P_i.neighbor) + 768 D_opt(P_i.neighbor, D), set cand_node-protect to TRUE. 770 9. If the router considers SRLGs, then set the cand_srlg-protect to 771 the set of SRLGs traversed on the path from S via P_i.link to 772 P_i.neighbor. Remove the set of SRLGs to which H_h belongs from 773 cand_srlg-protect. Remove from cand_srlg-protect the set of 774 SRLGs traversed on the path from H_h.neighbor to D. Now 775 cand_srlg-protect holds the set of SRLGs to which P_i belongs 776 and that are not traversed on the path from S via H_h to D. 778 10. If cand_type is PRIMARY, the router prefers other primary next- 779 hops for use as the alternate, and the P_i.alt_type is not 780 PRIMARY, goto Step 20. 782 11. If cand_type is not PRIMARY, P_i.alt_type is PRIMARY and the 783 router prefers other primary next-hops for use as the alternate, 784 then continue to the next candidate next-hop 786 12. If cand_node-protect is TRUE and P_i.alt_node-protect is FALSE, 787 goto Paragraph 20. 789 13. If cand_link-protect is TRUE and P_i.alt_link-protect is FALSE, 790 goto Step 20. 792 14. If cand_srlg-protect has a better set of SRLGs than 793 P_i.alt_srlg-protect, goto Step 20. 795 15. If cand_srlg-protect is different from P_i.alt_srlg-protect, 796 then select between H_h and P_i.alt_next_hops based upon 797 distance, IP addresses, or any router-local tie-breaker. If H_h 798 is preferred, then goto Step 20. If P_i.alt_next_hops is 799 preferred, skip H_h and continue to the next candidate next-hop. 801 16. If D_opt(H_h.neighbor, D) < D_opt(P_i.neighbor, D) and 802 D_opt(P_i.alt_next_hops, D) >= D_opt(P_i.neighbor, D), then H_h 803 is a downstream alternate and P_i.alt_next_hops is simply an 804 LFA. Prefer H_h and goto Step 20. 806 17. Based upon the alternate types, the alternate distances, IP 807 addresses, or other tie-breakers, decide if H_h is preferred to 808 P_i.alt_next_hops. If so, goto Step 20. 810 18. Decide if P_i.alt_next_hops is preferred to H_h. If so, then 811 skip H_h and continue to the next candidate next-hop. 813 19. Add H_h into P_i.alt_next_hops. Set P_i.alt_type to the better 814 type of H_h.alt_type and P_i.alt_type. Continue to the next 815 candidate next-hop. 817 20. Replace the P_i alternate next-hop set with H_h as follows: 819 P_i.alt_next_hops = {H_h} 820 P_i.alt_type = cand_type 821 P_i.alt_link-protect = cand_link-protect 822 P_i.alt_node-protect = cand_node-protect 823 P_i.alt_srlg-protect = cand_srlg-protect 825 Continue to the next candidate next-hop. 827 3.7. LFA types and Trade-offs 829 LFAs can provide different amounts of protection and the decision 830 about which type to prefer is dependent upon network topology and 831 other techniques in use in the network. This section describes the 832 different protection levels and the trade-offs associated with each. 834 1. Primary Next-hop: When there are equal-cost primary next-hops, 835 using one as an alternate is guaranteed to not cause micro-loops 836 involving S. Traffic flows across the paths that the network will 837 converge to, but congestion may be experienced on the primary 838 paths since traffic is sent across fewer. All primary next-hops 839 are downstream paths. 841 2. Downstream Paths: A downstream path, unlike an LFA, is guaranteed 842 not to cause a micro-loop involving S regardless of the actual 843 failure detected. However, the expected coverage of such 844 alternates in a network is expected to be poor. All downstream 845 paths are LFAs. 847 3. LFA: An LFA can have good coverage of a network, depending on 848 topology. However, it is possible to get micro-loops involving S 849 if a more severe failure occurs than is protected against. 851 The different types of protection are abbreviated as LP (link- 852 protecting), NP (node-protecting) and SP (SRLG-protecting). 854 a. LP, NP, and SP: If such an alternate exists, it gives protection 855 against all failures. 857 b. LP and NP only: Many networks may handle SRLG failures via 858 another method or may focus on node and link failures as being 859 more common. 861 c. LP only: A network may handle node failures via a high 862 availability technique and be concerned primarily about 863 protecting the more common link failure case. 865 d. NP only: These only exist on interfaces that aren't point-to- 866 point. If link protection is handled in a different layer, then 867 an NP alternate may be acceptable. 869 3.8. A Simplification: Per-Next-Hop LFAs 871 It is possible to simplify the computation and use of LFAs when 872 solely link protection is desired by considering and computing only 873 one link-protecting LFA for each next-hop connected to the router. 874 All prefixes that use that next-hop as a primary will use the LFA 875 computed for that next-hop as its LFA. 877 Even a prefix with multiple primary next-hops will have each primary 878 next-hop protected individually by the primary next-hop's associated 879 LFA. That associated LFA might or might not be another of the 880 primary next-hops of the prefix. 882 This simplification may reduce coverage in a network. In addition to 883 limiting protection for multi-homed prefixes (see Section 6.1), the 884 computation per next-hop may also not find an LFA when one could be 885 found for some of the prefixes that use that next-hop. 887 For example, consider Figure 4 where S has 3 ECMP next-hops, E1, E2, 888 and E3 to reach D. For the prefix D, E3 can give link protection for 889 the next-hops E1 and E2; E1 and E2 can give link protection for the 890 next-hops E3. However, if one uses this simplification to compute 891 LFAs for E1, E2 and E3 individually, there is no link-protecting LFA 892 for E1. E3 and E2 can protect each other. 894 4. Using an Alternate 896 If an alternate next-hop is available, the router redirects traffic 897 to the alternate next-hop in case of a primary next-hop failure as 898 follows. 900 When a next-hop failure is detected via a local interface failure or 901 other failure detection mechanisms (see 902 [I-D.ietf-rtgwg-ipfrr-framework]), the router SHOULD: 904 1. Remove the primary next-hop associated with the failure. 906 2. Install the loop-free alternate calculated for the failed next- 907 hop if it is not already installed (e.g. the alternate is also a 908 primary next-hop). 910 Note that the router MAY remove other next-hops if it believes (via 911 SRLG analysis) that they may have been affected by the same failure, 912 even if it is not visible at the time of failure detection. 914 The alternate next-hop MUST be used only for traffic types which are 915 routed according to the shortest path. Multicast traffic is 916 specifically out of scope for this specification. 918 4.1. Terminating Use of Alternate 920 A router MUST limit the amount of time an alternate next-hop is used 921 after the primary next-hop has become unavailable. This ensures that 922 the router will start using the new primary next-hops. It ensures 923 that all possible transient conditions are removed and the network 924 converges according to the deployed routing protocol. 926 There are techniques available to handle the micro-forwarding loops 927 that can occur in a networking during convergence. 929 A router that implements [I-D.ietf-rtgwg-microloop-analysis] SHOULD 930 follow the rules given there for terminating the use of an alternate. 932 A router that implements [I-D.francois-ordered-fib] SHOULD follow the 933 rules given there for terminating the use of an alternate. 935 It is desirable to avoid micro-forwarding loops involving S. An 936 example illustrating the problem is given in Figure 5. If the link 937 from S to E fails, S will use N1 as an alternate and S will compute 938 N2 as the new primary next-hop to reach D. If S starts using N2 as 939 soon as S can compute and install its new primary, it is probable 940 that N2 will not have yet installed its new primary next-hop. This 941 would cause traffic to loop and be dropped until N2 has installed the 942 new topology. This can be avoided by S delaying its installation and 943 leaving traffic on the alternate next-hop. 945 +-----+ 946 | N2 |-------- | 947 +-----+ 1 | \|/ 948 | | 949 | +-----+ @@> +-----+ 950 | | S |---------| N1 | 951 10 | +-----+ 10 +-----+ 952 | | | 953 | 1 | | | 954 | | \|/ 10 | 955 | +-----+ | | 956 | | E | | \|/ 957 | +-----+ | 958 | | | 959 | 1 | | | 960 | | \|/ | 961 | +-----+ | 962 |----| D |-------------- 963 +-----+ 965 Figure 5: Example where Continued Use of Alternate is Desirable 967 This is an example of a case where the new primary is not a loop-free 968 alternate before the failure and therefore may have been forwarding 969 traffic through S. This will occur when the path via a previously 970 upstream node is shorter than the the path via a loop-free alternate 971 neighbor. In these cases, it is useful to give sufficient time to 972 ensure that the new primary neighbor and other nodes on the new 973 primary path have switched to the new route. 975 If the newly selected primary was loop-free before the failure, then 976 it is safe to switch to that new primary immediately; the new primary 977 wasn't dependent on the failure and therefore its path will not have 978 changed. 980 Given that there is an alternate providing appropriate protection and 981 while the assumption of a single failure holds, it is safe to delay 982 the installation of the new primaries; this will not create 983 forwarding loops because the alternate's path to the destination is 984 known to not go via S or the failed element and will therefore not be 985 affected by the failure. 987 An implementation SHOULD continue to use the alternate next-hops for 988 packet forwarding even after the new routing information is available 989 based on the new network topology. The use of the alternate next- 990 hops for packet forwarding SHOULD terminate: 992 a. if the new primary next-hop was loop-free prior to the topology 993 change, or 995 b. if a configured hold-down, which represents a worst-case bound on 996 the length of the network convergence transition, has expired, or 998 c. if notification of an unrelated topological change in the network 999 is received. 1001 5. Requirements on LDP Mode 1003 Since LDP [RFC3036] traffic will follow the path specified by the 1004 IGP, it is also possible for the LDP traffic to follow the loop-free 1005 alternates indicated by the IGP. To do so, it is necessary for LDP 1006 to have the appropriate labels available for the alternate so that 1007 the appropriate out-segments can be installed in the forwarding plane 1008 before the failure occurs. 1010 This means that a Label Switched Router (LSR) running LDP must 1011 distribute its labels for the FECs it can provide to all its 1012 neighbors, regardless of whether or not they are upstream. 1013 Additionally, LDP must be acting in liberal label retention mode so 1014 that the labels which correspond to neighbors that aren't currently 1015 the primary neighbor are stored. Similarly, LDP should be in 1016 downstream unsolicited mode, so that the labels for the FEC are 1017 distributed other than along the SPT. 1019 If these requirements are met, then LDP can use the loop-free 1020 alternates without requiring any targeted sessions or signaling 1021 extensions for this purpose. 1023 6. Routing Aspects 1025 6.1. Multi-Homed Prefixes 1027 An SPF-like computation is run for each topology, which corresponds 1028 to a particular OSPF area or ISIS level. The IGP needs to determine 1029 loop-free alternates to multi-homed routes. Multi-homed routes occur 1030 for routes obtained from outside the routing domain by multiple 1031 routers, for subnets on links where the subnet is announced from 1032 multiple ends of the link, and for routes advertised by multiple 1033 routers to provide resiliency. 1035 Figure 6 demonstrates such a topology. In this example, the shortest 1036 path to reach the prefix p is via E. The prefix p will have the link 1037 to E as its primary next-hop. If the alternate next-hop for the 1038 prefix p is simply inherited from the router advertising it on the 1039 shortest path to p, then the prefix p's alternate next-hop would be 1040 the link to C. This would provide link protection, but not the node 1041 protection that is possible via A. 1043 5 +---+ 8 +---+ 5 +---+ 1044 ------| S |------| A |-----| B | 1045 | +---+ +---+ +---+ 1046 | | | 1047 | 5 | 5 | 1048 | | | 1049 +---+ 5 +---+ 5 7 +---+ 1050 | C |---| E |------ p -------| F | 1051 +---+ +---+ +---+ 1053 Figure 6: Multi-homed prefix 1055 To determine the best protection possible, the prefix p can be 1056 treated in the SPF computations as a node with uni-directional links 1057 to it from those routers that have advertised the prefix. Such a 1058 node need never have its links explored, as it has no out-going 1059 links. 1061 If there exist multiple multi-homed prefixes that share the same 1062 connectivity and the difference in metrics to those routers, then a 1063 single node can be used to represent the set. For instance, if in 1064 Figure 6 there were another prefix X that was connected to E with a 1065 metric of 1 and to F with a metric of 3, then that prefix X could use 1066 the same alternate next-hop as was computed for prefix p. 1068 A router SHOULD compute the alternate next-hop for an IGP multi-homed 1069 prefix by considering alternate paths via all routers that have 1070 announced that prefix. 1072 6.2. ISIS 1074 The applicability and interactions of LFAs with multi-topology ISIS 1075 [I-D.ietf-isis-wg-multi-topology] is out of scope for this 1076 specification. 1078 6.3. OSPF 1080 OSPF introduces certain complications because it is possible for the 1081 traffic path to exit an area and then re-enter that area. This can 1082 occur whenever a router considers the same route from multiple areas. 1083 There are several cases where issues such as this can occur. They 1084 happen when another area permits a shorter path to connect two ABRs 1085 than is available in the area where the LFA has been computed. To 1086 clarify, an example topology is given in Appendix A. 1088 a. Virtual Links: These allow paths to leave the backbone area and 1089 traverse the transit area. The path provided via the transit 1090 area can exit via any ABR. The path taken is not the shortest 1091 path determined by doing an SPF in the backbone area. 1093 b. Alternate ABR[RFC3509]: When an ABR is not connected to the 1094 backbone, it considers the inter-area summaries from multiple 1095 areas. The ABR A may determine to use area 2 but that path could 1096 traverse another alternate ABR B that determines to use area 1. 1097 This can lead to scenarios similar to that illustrated in 1098 Figure 7. 1100 c. ASBR Summaries: An ASBR may itself be an ABR and can be announced 1101 into multiple areas. This presents other ABRs with a decision as 1102 to which area to use. This is the example illustrated in 1103 Figure 7. 1105 d. AS External Prefixes: A prefix may be advertised by multiple 1106 ASBRs in different areas and/or with multiple forwarding 1107 addresses that are in different areas, which are connected via at 1108 least one common ABR. This presents such ABRs with a decision as 1109 to which area to use to reach the prefix. 1111 Loop-free alternates should not be used in an area where one of the 1112 above issues affects that area. 1114 6.3.1. OSPF External Routing 1116 When a forwarding address is set in an OSPF AS-external LSA, all 1117 routers in the network calculate their next-hops for the external 1118 prefix by doing a lookup for the forwarding address in the routing 1119 table, rather than using the next-hops calculated for the ASBR. In 1120 this case, the alternate next-hops SHOULD be computed by selecting 1121 among the alternate paths to the forwarding link(s) instead of among 1122 alternate paths to the ASBR. 1124 6.3.2. OSPF Multi-Topology 1126 The applicabilty and interactions of LFAs with multi-topology OSPF 1127 [RFC4915] [I-D.ietf-ospf-mt-ospfv3] is out of scope for this 1128 specification. 1130 6.4. BGP Next-Hop Synchronization 1132 Typically BGP prefixes are advertised with AS exit routers router-id 1133 as the BGP next-hop, and AS exit routers are reached by means of IGP 1134 routes. BGP resolves its advertised next-hop to the immediate next- 1135 hop by potential recursive lookups in the routing database. IP Fast- 1136 Reroute computes the alternate next-hops to all IGP destinations, 1137 which include alternate next-hops to the AS exit router's router-id. 1138 BGP simply inherits the alternate next-hop from IGP. The BGP 1139 decision process is unaltered; BGP continues to use the IGP optimal 1140 distance to find the nearest exit router. MBGP routes do not need to 1141 copy the alternate next hops. 1143 It is possible to provide ASBR protection if BGP selected a set of 1144 BGP next-hops and allowed the IGP to determine the primary and 1145 alternate next-hops as if the BGP route were a multi-homed prefix. 1146 This is for future study. 1148 6.5. Multicast Considerations 1150 Multicast traffic is out of scope for this specification of IP Fast- 1151 Reroute. The alternate next-hops SHOULD NOT be used for multicast 1152 RPF checks. 1154 7. Security Considerations 1156 The mechanism described in this document does not modify any routing 1157 protocol messages, and hence no new threats related to packet 1158 modifications or replay attacks are introduced. Traffic to certain 1159 destinations can be temporarily routed via next-hop routers that 1160 would not be used with the same topology change if this mechanism 1161 wasn't employed. However, these next-hop routers can be used anyway 1162 when a different topological change occurs, and hence this can't be 1163 viewed as a new security threat. 1165 In LDP, the wider distribution of FEC label information is still to 1166 neighbors with whom a trusted LDP session has been established. This 1167 wider distribution and the recommendation of using liberal label 1168 retention mode are believed to have no significant security impact. 1170 8. IANA Considerations 1172 This document requires no IANA considerations. 1174 9. Acknowledgements 1176 The authors would like to thank Joel Halpern, Mike Shand, Stewart 1177 Bryant, and Stefano Previdi for their assistance and useful review. 1179 10. References 1181 10.1. Normative References 1183 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1184 Requirement Levels", BCP 14, RFC 2119, March 1997. 1186 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 1188 [RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", 1189 RFC 2740, December 1999. 1191 [RFC3036] Andersson, L., Doolan, P., Feldman, N., Fredette, A., and 1192 B. Thomas, "LDP Specification", RFC 3036, January 2001. 1194 10.2. Informative References 1196 [I-D.francois-ordered-fib] 1197 Francois, P., "Loop-free convergence using oFIB", 1198 draft-francois-ordered-fib-02 (work in progress), 1199 October 2006. 1201 [I-D.ietf-isis-link-attr] 1202 Vasseur, J. and S. Previdi, "Definition of an IS-IS Link 1203 Attribute sub-TLV", draft-ietf-isis-link-attr-03 (work in 1204 progress), February 2007. 1206 [I-D.ietf-isis-wg-multi-topology] 1207 Przygienda, T., "M-ISIS: Multi Topology (MT) Routing in 1208 IS-IS", draft-ietf-isis-wg-multi-topology-12 (work in 1209 progress), November 2007. 1211 [I-D.ietf-ospf-mt-ospfv3] 1212 Mirtorabi, S. and A. Roy, "Multi-topology routing in 1213 OSPFv3 (MT-OSPFv3)", draft-ietf-ospf-mt-ospfv3-03 (work in 1214 progress), July 2007. 1216 [I-D.ietf-ospf-ospfv3-update] 1217 Ferguson, D., "OSPF for IPv6", 1218 draft-ietf-ospf-ospfv3-update-18 (work in progress), 1219 November 2007. 1221 [I-D.ietf-rtgwg-ipfrr-framework] 1222 Shand, M. and S. Bryant, "IP Fast Reroute Framework", 1223 draft-ietf-rtgwg-ipfrr-framework-07 (work in progress), 1224 July 2007. 1226 [I-D.ietf-rtgwg-microloop-analysis] 1227 Zinin, A., "Analysis and Minimization of Microloops in 1228 Link-state Routing Protocols", 1229 draft-ietf-rtgwg-microloop-analysis-01 (work in progress), 1230 October 2005. 1232 [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and 1233 dual environments", RFC 1195, December 1990. 1235 [RFC2966] Li, T., Przygienda, T., and H. Smit, "Domain-wide Prefix 1236 Distribution with Two-Level IS-IS", RFC 2966, 1237 October 2000. 1239 [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. 1240 McPherson, "OSPF Stub Router Advertisement", RFC 3137, 1241 June 2001. 1243 [RFC3509] Zinin, A., Lindem, A., and D. Yeung, "Alternative 1244 Implementations of OSPF Area Border Routers", RFC 3509, 1245 April 2003. 1247 [RFC4203] Kompella, K. and Y. Rekhter, "OSPF Extensions in Support 1248 of Generalized Multi-Protocol Label Switching (GMPLS)", 1249 RFC 4203, October 2005. 1251 [RFC4205] Kompella, K. and Y. Rekhter, "Intermediate System to 1252 Intermediate System (IS-IS) Extensions in Support of 1253 Generalized Multi-Protocol Label Switching (GMPLS)", 1254 RFC 4205, October 2005. 1256 [RFC4915] Psenak, P., Mirtorabi, S., Roy, A., Nguyen, L., and P. 1257 Pillay-Esnault, "Multi-Topology (MT) Routing in OSPF", 1258 RFC 4915, June 2007. 1260 Appendix A. OSPF Example Where LFA Based on Local Area Topology is 1261 Insufficient 1263 This appendix provides an example scenario where the local area 1264 topology does not suffice to determine that an LFA is available. As 1265 described in Section 6.3, one problem scenario is for ASBR summaries 1266 where the ASBR is available in two areas via intra-area routes and 1267 there is at least one ABR or alternate ABR that is in both areas. 1268 The following Figure 7 illustrates this case. 1270 5 1271 [ F ]-----------[ C ] 1272 | | 1273 | | 5 1274 20 | 5 | 1 1275 | [ N ]-----[ A ]*****[ F ] 1276 | | # * 1277 | 40 | # 50 * 2 1278 | | 5 # 2 * 1279 | [ S ]-----[ B ]*****[ G ] 1280 | | * 1281 | 5 | * 15 1282 | | * 1283 | [ E ] [ H ] 1284 | | * 1285 | 5 | * 10** 1286 | | * 1287 |---[ X ]-----[ASBR] 1288 5 1290 ---- Link in Area 1 1291 **** Link in Area 2 1292 #### Link in Backbone Area 0 1294 Figure 7: Topology with Multi-area ASBR Causing Area Transiting 1296 In Figure 7, the ASBR is also an ABR and is announced into both area 1297 1 and area 2. A and B are both ABRs that are also connected to the 1298 backbone area. S determines that N can provide a loop-free alternate 1299 to reach the ASBR. N's path goes via A. A also sees an intra-area 1300 route to ASBR via Area 2; the cost of the path in area 2 is 30, which 1301 is less than 35, the cost of the path in area 1. Therefore, A uses 1302 the path from area 2 and directs traffic to F. The path from F in 1303 area 2 goes to B. B is also an ABR and learns the ASBR from both 1304 areas 1 and area 2; B's path via area 1 is shorter (cost 20) than B's 1305 path via area 2 (cost 25). Therefore, B uses the path from area 1 1306 that connects to S. 1308 Authors' Addresses 1310 Alia K. Atlas (editor) 1311 BT 1313 Email: alia.atlas@bt.com 1315 Alex Zinin (editor) 1316 Alcatel 1317 701 E Middlefield Rd. 1318 Mountain View, CA 94043 1319 USA 1321 Email: alex.zinin@alcatel.com 1323 Raveendra Torvi 1324 FutureWei Technologies Inc. 1325 1700 Alma Dr. Suite 100 1326 Plano, TX 75075 1327 USA 1329 Email: traveendra@huawei.com 1331 Gagan Choudhury 1332 AT&T 1333 200 Laurel Avenue, Room D5-3C21 1334 Middletown, NJ 07748 1335 USA 1337 Phone: +1 732 420-3721 1338 Email: gchoudhury@att.com 1340 Christian Martin 1341 iPath Technologies 1343 Email: chris@ipath.net 1344 Brent Imhoff 1345 Juniper Networks 1346 1194 North Mathilda 1347 Sunnyvale, CA 94089 1348 USA 1350 Phone: +1 314 378 2571 1351 Email: bimhoff@planetspork.com 1353 Don Fedyk 1354 Nortel Networks 1355 600 Technology Park 1356 Billerica, MA 01821 1357 USA 1359 Phone: +1 978 288 3041 1360 Email: dwfedyk@nortelnetworks.com 1362 Full Copyright Statement 1364 Copyright (C) The IETF Trust (2008). 1366 This document is subject to the rights, licenses and restrictions 1367 contained in BCP 78, and except as set forth therein, the authors 1368 retain all their rights. 1370 This document and the information contained herein are provided on an 1371 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1372 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1373 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1374 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1375 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1376 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1378 Intellectual Property 1380 The IETF takes no position regarding the validity or scope of any 1381 Intellectual Property Rights or other rights that might be claimed to 1382 pertain to the implementation or use of the technology described in 1383 this document or the extent to which any license under such rights 1384 might or might not be available; nor does it represent that it has 1385 made any independent effort to identify any such rights. Information 1386 on the procedures with respect to rights in RFC documents can be 1387 found in BCP 78 and BCP 79. 1389 Copies of IPR disclosures made to the IETF Secretariat and any 1390 assurances of licenses to be made available, or the result of an 1391 attempt made to obtain a general license or permission for the use of 1392 such proprietary rights by implementers or users of this 1393 specification can be obtained from the IETF on-line IPR repository at 1394 http://www.ietf.org/ipr. 1396 The IETF invites any interested party to bring to its attention any 1397 copyrights, patents or patent applications, or other proprietary 1398 rights that may cover technology that may be required to implement 1399 this standard. Please address the information to the IETF at 1400 ietf-ipr@ietf.org. 1402 Acknowledgment 1404 Funding for the RFC Editor function is provided by the IETF 1405 Administrative Support Activity (IASA).