idnits 2.17.1 draft-ietf-rtgwg-ipfrr-spec-base-08.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 1310. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1321. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1328. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1334. 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 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 278: '... paths, a router SHOULD select a link ...' RFC 2119 keyword, line 428: '... specification MUST conform to at le...' RFC 2119 keyword, line 453: '...on to use it. Therefore, it SHOULD be...' RFC 2119 keyword, line 490: '... SHOULD be loop-free with respect to...' RFC 2119 keyword, line 578: '...ernate, a router MUST NOT use an alter...' (23 more instances...) 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 (Sept 6, 2007) is 6350 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) == Missing Reference: 'E1' is mentioned on line 546, but not defined == Missing Reference: 'E2' is mentioned on line 546, but not defined == Missing Reference: 'A' is mentioned on line 549, but not defined == Missing Reference: 'B' is mentioned on line 549, but not defined == Missing Reference: 'FRAMEWORK' is mentioned on line 838, but not defined ** Obsolete normative reference: RFC 2740 (Obsoleted by RFC 5340) ** Obsolete normative reference: RFC 2966 (Obsoleted by RFC 5302) ** Obsolete normative reference: RFC 3036 (Obsoleted by RFC 5036) == Outdated reference: A later version (-12) exists of draft-ietf-isis-wg-multi-topology-11 == Outdated reference: A later version (-23) exists of draft-ietf-ospf-ospfv3-update-17 == Outdated reference: A later version (-13) exists of draft-ietf-rtgwg-ipfrr-framework-07 -- 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: 5 errors (**), 0 flaws (~~), 10 warnings (==), 10 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: March 9, 2008 A. Zinin, Ed. 5 Alcatel 6 Sept 6, 2007 8 Basic Specification for IP Fast-Reroute: Loop-free Alternates 9 draft-ietf-rtgwg-ipfrr-spec-base-08 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 March 9, 2008. 36 Copyright Notice 38 Copyright (C) The IETF Trust (2007). 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 micro-looping and packet loss that happens while routers converge 47 after a topology change due to a failure. Rapid failure repair is 48 achieved through use of precalculated backup next-hops that are loop- 49 free and safe to use until the distributed network convergence 50 process completes. 52 Table of Contents 54 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 55 1.1. Failure Scenarios . . . . . . . . . . . . . . . . . . . . 5 56 2. Applicability of Described Mechanisms . . . . . . . . . . . . 8 57 3. Alternate Next-Hop Calculation . . . . . . . . . . . . . . . . 8 58 3.1. Basic Loop-free Condition . . . . . . . . . . . . . . . . 10 59 3.2. Node-Protecting Alternate Next-Hops . . . . . . . . . . . 10 60 3.3. Broadcast and NBMA Links . . . . . . . . . . . . . . . . . 10 61 3.4. ECMP and Alternates . . . . . . . . . . . . . . . . . . . 12 62 3.5. Interactions with ISIS Overload, RFC 3137 and Costed 63 Out Links . . . . . . . . . . . . . . . . . . . . . . . . 13 64 3.5.1. Interactions with ISIS Link Attributes . . . . . . . . 14 65 3.6. Selection Procedure . . . . . . . . . . . . . . . . . . . 14 66 3.7. A Simplification: Per-Next-Hop LFAs . . . . . . . . . . . 18 67 4. Using an Alternate . . . . . . . . . . . . . . . . . . . . . . 18 68 4.1. Terminating Use of Alternate . . . . . . . . . . . . . . . 19 69 5. Requirements on LDP Mode . . . . . . . . . . . . . . . . . . . 21 70 6. Routing Aspects . . . . . . . . . . . . . . . . . . . . . . . 21 71 6.1. Multi-Homed Prefixes . . . . . . . . . . . . . . . . . . . 21 72 6.2. ISIS . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 73 6.3. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 74 6.3.1. OSPF External Routing . . . . . . . . . . . . . . . . 23 75 6.3.2. OSPF Multi-Topology . . . . . . . . . . . . . . . . . 23 76 6.4. BGP Next-Hop Synchronization . . . . . . . . . . . . . . . 24 77 6.5. Multicast Considerations . . . . . . . . . . . . . . . . . 24 78 7. Security Considerations . . . . . . . . . . . . . . . . . . . 24 79 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 80 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 25 81 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 25 82 10.1. Normative References . . . . . . . . . . . . . . . . . . . 25 83 10.2. Informative References . . . . . . . . . . . . . . . . . . 25 84 Appendix A. OSPF Example Where LFA Based on Local Area 85 Topology is Insufficient . . . . . . . . . . . . . . 26 86 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 27 87 Intellectual Property and Copyright Statements . . . . . . . . . . 30 89 1. Introduction 91 Applications for interactive multimedia services such as VoIP and 92 pseudo-wires can be very sensitive to traffic loss, such as occurs 93 when a link or router in the network fails. A router's convergence 94 time is generally on the order of hundreds of milliseconds; the 95 application traffic may be sensitive to losses greater than tens of 96 milliseconds. 98 As discussed in [I-D.ietf-rtgwg-ipfrr-framework], minimizing traffic 99 loss requires a mechanism for the router adjacent to a failure to 100 rapidly invoke a repair path, which is minimally affected by any 101 subsequent re-convergence. This specification describes such a 102 mechanism which allows a router whose local link has failed to 103 forward traffic to a pre-computed alternate until the router installs 104 the new primary next-hops based upon the changed network topology. 105 The terminology used in this specification is given in 106 [I-D.ietf-rtgwg-ipfrr-framework]. The described mechanism assumes 107 that routing in the network is performed using a link-state routing 108 protocol-- OSPF [RFC2328] [RFC2740] [I-D.ietf-ospf-ospfv3-update] or 109 ISIS [RFC1195] [RFC2966] (for IPv4 or IPv6). The mechanism also 110 assumes that both the primary path and the alternate path are in the 111 same routing area. 113 When a local link fails, a router currently must signal the event to 114 its neighbors via the IGP, recompute new primary next-hops for all 115 affected prefixes, and only then install those new primary next-hops 116 into the forwarding plane. Until the new primary next-hops are 117 installed, traffic directed towards the affected prefixes is 118 discarded. This process can take hundreds of milliseconds. 120 <-- 121 +-----+ 122 /------| S |--\ 123 / +-----+ \ 124 / 5 8 \ 125 / \ 126 +-----+ +-----+ 127 | E | | N_1 | 128 +-----+ +-----+ 129 \ / 130 \ \ 4 3 / / 131 \| \ / |/ 132 -+ \ +-----+ / +- 133 \---| D |---/ 134 +-----+ 136 Figure 1: Basic Topology 138 The goal of IP Fast-Reroute is to reduce failure reaction time to 10s 139 of milliseconds by using a pre-computed alternate next-hop, in the 140 event that the currently selected primary next-hop fails, so that the 141 alternate can be rapidly used when the failure is detected. A 142 network with this feature experiences less traffic loss and less 143 micro-looping of packets than a network without IPFRR. There are 144 cases where micro-looping is still a possibility since IPFRR coverage 145 varies but in the worst possible situation a network with IPFRR is 146 equivalent with respect to traffic convergence to a network without 147 IPFRR. 149 To clarify the behavior of IP Fast-Reroute, consider the simple 150 topology in Figure 1. When router S computes its shortest path to 151 router D, router S determines to use the link to router E as its 152 primary next-hop. Without IP Fast-Reroute, that link is the only 153 next-hop that router S computes to reach D. With IP Fast-Reroute, S 154 also looks for an alternate next-hop to use. In this example, S 155 would determine that it could send traffic destined to D by using the 156 link to router N_1 and therefore S would install the link to N_1 as 157 its alternate next-hop. At some later time, the link between router 158 S and router E could fail. When that link fails, S and E will be the 159 first to detect it. On detecting the failure, S will stop sending 160 traffic destined for D towards E via the failed link, and instead 161 send the traffic to S's pre-computed alternate next-hop, which is the 162 link to N_1, until a new SPF is run and its results are installed. 163 As with the primary next-hop, an alternate next-hop is computed for 164 each destination. The process of computing an alternate next-hop 165 does not alter the primary next-hop computed via a standard SPF. 167 If in the example of Figure 1, the link cost from N_1 to D increased 168 to 30 from 3, then N_1 would not be a loop-free alternate, because 169 the cost of the path from N_1 to D via S would be 17 while the cost 170 from N_1 directly to D would be 30. In real networks, we may often 171 face this situation. The existence of a suitable loop-free alternate 172 next-hop is dependent on the topology and the nature of the failure 173 the alternate is calculated for. 175 This specification uses the terminology introduced in 176 [I-D.ietf-rtgwg-ipfrr-framework]. In particular, it uses 177 Distance_opt(X,Y), abbreviated to D_opt(X,Y), to indicate the 178 shortest distance from X to Y. S is used to indicate the calculating 179 router. N_i is a neighbor of S; N is used as an abbreviation when 180 only one neighbor is being discussed. D is the destination under 181 consideration. 183 A neighbor N can provide a loop-free alternate (LFA) if and only if 184 Distance_opt(N, D) < Distance_opt(N, S) + Distance_opt(S, D) 186 Inequality 1: Loop-Free Criterion 188 A sub-set of loop-free alternate are downstream paths which must meet 189 a more restrictive condition that is applicable to more complex 190 failure scenarios: 192 Distance_opt(N, D) < Distance_opt(S, D) 194 Inequality 2: Downstream Path Criterion 196 1.1. Failure Scenarios 198 The alternate next-hop can protect against a single link failure, a 199 single node failure, one or more shared risk link group failures, or 200 a combination of these. Whenever a failure occurs that is more 201 extensive than what the alternate was intended to protect, there is 202 the possibility of temporarily looping traffic (note again, that such 203 a loop would only last until the next complete SPF calculation). The 204 example where a node fails when the alternate provided only link 205 protection is illustrated below. If unexpected simultaneous failures 206 occur, then micro-looping may occur since the alternates are not pre- 207 computed to avoid the set of failed links. 209 If only link protection is provided and the node fails, it is 210 possible for traffic using the alternates to experience micro- 211 looping. This issue is illustrated in Figure 2. If Link(S->E) 212 fails, then the link-protecting alternate via N will work correctly. 213 However, if router E fails, then both S and N will detect a failure 214 and switch to their alternates. In this example, that would cause S 215 to redirect the traffic to N and N to redirect the traffic to S and 216 thus causing a forwarding loop. Such a scenario can arise because 217 the key assumption, that all other routers in the network are 218 forwarding based upon the shortest path, is violated because of a 219 second simultaneous correlated failure - another link connected to 220 the same primary neighbor. If there are not other protection 221 mechanisms a node failure is still a concern when only using link 222 protection. 224 <@@@ 225 @@@> 226 +-----+ +-----+ 227 | S |-------| N | 228 +-+---+ 5 +-----+ 229 | | 230 | 5 4 | | 231 | | | \|/ 232 \|/ | | 233 | +-----+ | 234 +----| E |---+ 235 +--+--+ 236 | 237 | 238 | 10 239 | 240 +--+--+ 241 | D | 242 +-----+ 244 Figure 2: Link-Protecting Alternates Causing Loop on Node Failure 246 Micro-looping of traffic via the alternates caused when a more 247 extensive failure than planned for occurs can be prevented via 248 selection of only downstream paths as alternates. In Figure 2, S 249 would be able to use N as an alternate, but N could not use S; 250 therefore N would have no alternate and would discard the traffic, 251 thus avoiding the micro-loop. A micro-loop due to the use of 252 alternates can be avoided by using downstream paths because each 253 succeeding router in the path to the destination must be closer to 254 the destination than its predecessor (according to the topology prior 255 to the failures). Although use of downstream paths ensures that the 256 micro-looping via alternates does not occur, such a restriction can 257 severely limit the coverage of alternates. 259 As shown above, the use of either a node protecting LFA or a 260 downstream path provides protection against micro-looping in the 261 event of node failure. There are topologies where there may be 262 either a node portecting LFA, a downstream path, both or neither. A 263 node may select either a node protecting LFA or a downstream path 264 without risk of causing micro-loops in the event of node failure. 265 While a link-and-node-protecting LFA guarantees protection against 266 either link or node failure, a downstream path provides protection 267 only against a link failure and may or may not provide protection 268 against a node failure depending on the protection available at the 269 downstream node, but it cannot cause a micro-loop. For example in 270 Figure 2, if S uses N as a downstream path, although no looping can 271 occur, the traffic will not be protected in the event of the failure 272 of node E because N has no viable repair path, and it will simply 273 discard the packet. However, if N had a link and node protecting LFA 274 or downstream path via some other path (not shown), then the repair 275 may succeed. 277 Since the functionality of link and node protecting LFAs is greater 278 than that of downstream paths, a router SHOULD select a link and node 279 protecting LFA over a downstream path. If there are any destinations 280 for which a link and node protecting LFA is not available, then by 281 definition the path to all of those destinations from any neighbor of 282 the computing router (S) must be through the node (E) being protected 283 (otherwise there would be a node protecting LFA for that 284 destination). Consequently, if there exists a downstream path to the 285 protected node as destination, then that downstream path may be used 286 for all those destinations for which a link and node protecting LFA 287 is not available; the existence of a downstream path can be 288 determined by a single check of the condition Distance_opt(N, E) < 289 Distance_opt(S, E). 291 It may be desirable to find an alternate that can protect against 292 other correlated failures (of which node failure is a specific 293 instance). In the general case, these are handled by shared risk 294 link groups (SRLGs) where any links in the network can belong to the 295 SRLG. General SRLGs may add unacceptably to the computational 296 complexity of finding a loop-free alternate. 298 However, a sub-category of SRLGs is of interest and can be applied 299 only during the selection of an acceptable alternate. This sub- 300 category is to express correlated failures of links that are 301 connected to the same router. For example, if there are multiple 302 logical sub-interfaces on the same physical interface, such as VLANs 303 on an Ethernet interface, if multiple interfaces use the same 304 physical port because of channelization, or if multiple interfaces 305 share a correlated failure because they are on the same line-card. 306 This sub-category of SRLGs will be referred to as local-SRLGs. A 307 local-SRLG has all of its member links with one end connected to the 308 same router. Thus, router S could select a loop-free alternate which 309 does not use a link in the same local-SRLG as the primary next-hop. 310 The local-SRLGs belonging to E can be protected against via node- 311 protection; i.e. picking a loop-free node-protecting alternate. 313 Where SRLG protection is provided, it is in the context of the 314 particular OSPF or ISIS area, whose topology is used in the SPF 315 computations to compute the loop-free alternates. If an SRLG 316 contains links in multiple areas, then separate SRLG-protecting 317 alternates would be required in each area that is traversed by the 318 affected traffic. 320 2. Applicability of Described Mechanisms 322 IP Fast Reroute mechanisms described in this memo cover intra-domain 323 routing only, with OSPF[RFC2328] or ISIS [RFC1195] [RFC2966] as the 324 IGP. Specifically, Fast Reroute for BGP inter-domain routing is not 325 part of this specification. 327 Certain aspects of OSPF inter-area routing behavior explained in 328 Section 6.3 and Appendix A impact the ability of the router 329 calculating the backup next-hops to assess traffic trajectories. In 330 order to avoid micro-looping and ensure required coverage, certain 331 constraints are applied to multi-area OSPF networks: 333 a. Loop-free alternates should not be used in the backbone area if 334 there are any virtual links configured unless, for each transit 335 area, there is a full mesh of virtual links between all ABRs in 336 that area. Loop-free alternates may be used in non-backbone 337 areas regardless of whether there are virtual links configured. 339 b. Loop-free alternates should not be used for inter-area routes in 340 an area that contains more than one alternate ABR. [RFC3509] 342 c. Loop-free alternates should not be used for AS External routes or 343 ASBR routes in a non-backbone area of a network where there 344 exists an ABR that is announced as an ASBR in multiple non- 345 backbone areas and there exists another ABR that is in at least 346 two of the same non-backbone areas. 348 d. Loop-free alternates should not be used in a non-backbone area of 349 a network for AS External routes where an AS External prefix is 350 advertised with the same type of external metric by multiple 351 ASBRs, which are in different non-backbone areas, with a 352 forwarding address of 0.0.0.0 or by one or more ASBRs with 353 forwarding addresses in multiple non-backbone areas when an ABR 354 exists simultaneously in two or more of those non-backbone areas. 356 3. Alternate Next-Hop Calculation 358 In addition to the set of primary next-hops obtained through a 359 shortest path tree (SPT) computation that is part of standard link- 360 state routing functionality, routers supporting IP Fast Reroute also 361 calculate a set of backup next hops that are engaged when a local 362 failure occurs. These backup next hops are calculated to provide the 363 required type of protection (i.e. link-protecting and/or node- 364 protecting) and to guarantee that when the expected failure occurs, 365 forwarding traffic through them will not result in a loop. Such next 366 hops are called loop-free alternates or LFAs throughout this 367 specification. 369 In general, to be able to calculate the set of LFAs for a specific 370 destination D, a router needs to know the following basic pieces of 371 information: 373 o Shortest-path distance from the calculating router to the 374 destination (Distance_opt(S, D)) 376 o Shortest-path distance from the router's IGP neighbors to the 377 destination (Distance_opt(N, D)) 379 o Shortest path distance from the router's IGP neighbors to itself 380 (Distance_opt(N, S)) 382 o Distance_opt(S, D) is normally available from the regular SPF 383 calculation performed by the link-state routing protocols. 384 Distance_opt(N, D) and Distance_opt(N, S) can be obtained by 385 performing additional SPF calculations from the perspective of 386 each IGP neighbor (i.e. considering the neighbor's vertex as the 387 root of the SPT--called SPT(N) hereafter--rather than the 388 calculating router's one, called SPT(S)). 390 This specification defines a form of SRLG protection limited to those 391 SRLGs that include a link that the calculating router is directly 392 connected to. Only that set of SRLGs could cause a local failure; 393 the calculating router only computes alternates to handle a local 394 failure. Information about local link SRLG membership is manually 395 configured. Information about remote link SRLG membership may be 396 dynamically obtained using [RFC4205] or [RFC4203]. Define 397 SRLG_local(S) to be the set of SRLGs that include a link that the 398 calculating router S is directly connected to. Only SRLG_local(S) is 399 of interest during the calculation, but the calculating router must 400 correctly handle changes to SRLG_local(S) triggered by local link 401 SRLG membership changes. 403 In order to choose among all available LFAs that provide required 404 SRLG protection for a given destination, the calculating router needs 405 to track the set of SRLGs in SRLG_local(S) that the path through a 406 specific IGP neighbor involves. To do so, each node D in the network 407 topology is associated with SRLG_set(N, D), which is the set of SRLGs 408 that would be crossed if traffic to D was forwarded through N. To 409 calculate this set, the router initializes SRLG_set(N, N) for each of 410 its IGP neighbors to be empty. During the SPT(N) calculation, when a 411 new vertex V is added to the SPT, its SRLG_set(N, V) is set to the 412 union of SRLG sets associated with its parents, and the SRLG sets in 413 SRLG_local(S) that are associated with the links from V's parents to 414 V. The union of the set of SRLG associated with a candidate alternate 415 next-hop and the SRLG_set(N, D) for the neighbor reached via that 416 candidate next-hop is used to determine SRLG protection. 418 The following sections provide information required for calculation 419 of LFAs. Sections Section 3.1 through Section 3.4 define different 420 types of LFA conditions. Section 3.5 describes constraints imposed 421 by the IS-IS overload and OSPF stub router functionality. 422 Section 3.6 defines the summarized algorithm for LFA calculation 423 using the definitions in the previous sections. 425 3.1. Basic Loop-free Condition 427 Alternate next hops used by implementations following this 428 specification MUST conform to at least the loop-freeness condition 429 stated above in Inequality 1. This condition guarantees that 430 forwarding traffic to an LFA will not result in a loop after a link 431 failure. 433 Further conditions may be applied when determining link-protecting 434 and/or node-protecting alternate next-hops as described in Sections 435 Section 3.2 and Section 3.3. 437 3.2. Node-Protecting Alternate Next-Hops 439 For an alternate next-hop N to protect against node failure of a 440 primary neighbor E for destination D, N must be loop-free with 441 respect to both E and D. In other words, N's path to D must not go 442 through E. This is the case if Inequality 3 is true, where N is the 443 neighbor providing a loop-free alternate. 445 Distance_opt(N, D) < Distance_opt(N, E) + Distance_opt(E, D) 447 Inequality 3: Criteria for a Node-Protecting Loop-Free Alternate 449 If Distance_opt(N,D) = Distance_opt(N, E) + Distance_opt(E, D), it is 450 possible that N has equal-cost paths and one of those could provide 451 protection against E's node failure. However, it is equally possible 452 that one of N's paths goes through E, and the calculating router has 453 no way to influence N's decision to use it. Therefore, it SHOULD be 454 assumed that an alternate next-hop does not offer node protection if 455 Inequality 3 is not met. 457 3.3. Broadcast and NBMA Links 459 Verification of the link-protection property of a next hop in the 460 case of a broadcast link is more elaborate than for a point-to-point 461 link. This is because a broadcast link is represented as a pseudo- 462 node with zero-cost links connecting it to other nodes. 464 Because failure of an interface attached to a broadcast segment may 465 mean loss of connectivity of the whole segment, the condition 466 described for broadcast link protection is pessimistic and requires 467 that the alternate is loop-free with regard to the pseudo-node. 468 Consider the example in Figure 3. 470 +-----+ 15 471 | S |-------- 472 +-----+ | 473 | 5 | 474 | | 475 | 0 | 476 /----\ 0 5 +-----+ 477 | PN |-----| N | 478 \----/ +-----+ 479 | 0 | 480 | | 8 481 | 5 | 482 +-----+ 5 +-----+ 483 | E |----| D | 484 +-----+ +-----+ 486 Figure 3: Loop-Free Alternate that is Link-Protecting 488 In Figure 3, N offers a loop-free alternate which is link-protecting. 489 If the primary next-hop uses a broadcast link, then an alternate 490 SHOULD be loop-free with respect to that link's pseudo-node to 491 provide link protection. This requirement is described in 492 Inequality 4 below. 494 D_opt(N, D) < D_opt(N, pseudo) + D_opt(pseudo, D) 496 Inequality 4: Loop-Free Link-Protecting Criterion for Broadcast Links 498 Because the shortest path from the pseudo-node goes through E, if a 499 loop-free alternate from a neighbor N is node-protecting, the 500 alternate will also be link-protecting unless the router S can only 501 reach the alternate neighbor N via the same pseudo-node. Because S 502 can direct the traffic away from the shortest path to use the 503 alternate N, traffic might pass through the same broadcast link as it 504 would when S sent the traffic to the primary E. Thus, an LFA from N 505 that is node-protecting is not automatically link-protecting. 507 To obtain link protection, it is necessary both that the path from 508 the selected alternate next-hop does not traverse the link of 509 interest and that the link used from S to reach that alternate next- 510 hop is not the link of interest. The latter can only occur with non- 511 point-to-point links. Therefore, if the primary next-hop is across a 512 broadcast or NBMA interface, it is necessary to consider link 513 protection during the alternate selection. To clarify, consider the 514 topology in Figure 3. For N to provide link-protection, it is first 515 necessary that N's shortest path to D does not traverse the pseudo- 516 node PN. Second, it is necessary that the alternate next-hop 517 selected by S does not traverse PN. In this example, S's shortest 518 path to N is via the pseudo-node. Thus, to obtain link-protection, S 519 must find a next-hop to N (the point-to-point link from S to N in 520 this example) that avoids the pseudo-node PN. 522 Similar consideration of the link from S to the selected alternate 523 next-hop as well as the path from the selected alternate next-hop is 524 also necessary for SRLG protection. S's shortest path to the 525 selected neighbor N may not be acceptable as an alternate next-hop to 526 provide SRLG protection, even if the path from N to D can provide 527 SRLG protection. 529 3.4. ECMP and Alternates 531 With equal-cost multi-path, a prefix may have multiple primary next- 532 hops that are used to forward traffic. When a particular primary 533 next-hop fails, alternate next-hops should be used to preserve the 534 traffic. These alternate next-hops may themselves also be primary 535 next-hops, but need not be. Other primary next-hops are not 536 guaranteed to provide protection against the failure scenarios of 537 concern. 539 20 L1 L3 3 540 [N]-----[ S ]--------[E3] 541 | | | 542 | 5 | L2 | 543 20 | | | 544 | --------- | 2 545 | 5 | | 5 | 546 | [E1] [E2]------| 547 | | | 548 | 10 | 10 | 549 |---[A] [B] 550 | | 551 2 |--[D]--| 2 553 Figure 4: ECMP where Primary Next-Hops Provide Limited Protection 555 In Figure 4 S has three primary next-hops to reach D; these are L2 to 556 E1, L2 to E2 and L3 to E3. The primary next-hop L2 to E1 can obtain 557 link and node protection from L3 to E3, which is one of the other 558 primary next-hops; L2 to E1 cannot obtain link protection from the 559 other primary next-hop L2 to E2. Similarly, the primary next-hop L2 560 to E2 can only get node protection from L2 to E1 and can only get 561 link protection from L3 to E3. The third primary next-hop L3 to E3 562 can obtain link and node protection from L2 to E1 and from L2 to E2. 563 It is possible for both the primary next-hop L2 to E2 and the primary 564 next-hop L2 to E1 to obtain an alternate next-hop that provides both 565 link and node protection by using L1. 567 Alternate next-hops are determined for each primary next-hop 568 separately. As with alternate selection in the non-ECMP case, these 569 alternate next-hops should maximize the coverage of the failure 570 cases. 572 3.5. Interactions with ISIS Overload, RFC 3137 and Costed Out Links 574 As described in [RFC3137], there are cases where it is desirable not 575 to have a router used as a transit node. For those cases, it is also 576 desirable not to have the router used on an alternate path. 578 For computing an alternate, a router MUST NOT use an alternate next- 579 hop that is along a link whose cost or reverse cost is LSInfinity 580 (for OSPF) or the maximum cost (for ISIS) or which has the overload 581 bit set (for ISIS). For a broadcast link, the reverse cost 582 associated with a potential alternate next-hop is the cost towards 583 the pseudo-node advertised by the next-hop router. For point-to- 584 point links, if a specific link from the next-hop router cannot be 585 associated with a particular link, then the reverse cost considered 586 is that of the minimum cost link from the next-hop router back to S. 588 In the case of OSPF, if all links from router S to a neighbor N_i 589 have a reverse cost of LSInfinity, then router S MUST NOT use N_i as 590 an alternate. 592 Similarly in the case of ISIS, if N_i has the overload bit set, then 593 S MUST NOT consider using N_i as an alternate. 595 This preserves the desired behavior of diverting traffic away from a 596 router which is following [RFC3137] and it also preserves the desired 597 behavior when an operator sets the cost of a link to LSInfinity for 598 maintenance which is not permitting traffic across that link unless 599 there is no other path. 601 If a link or router which is costed out was the only possible 602 alternate to protect traffic from a particular router S to a 603 particular destination, then there should be no alternate provided 604 for protection. 606 3.5.1. Interactions with ISIS Link Attributes 608 [I-D.ietf-isis-link-attr] describes several flags whose interactions 609 with LFAs needs to be defined. A router SHOULD NOT specify the 610 "local protection available" flag as a result of having LFAs. A 611 router SHOULD NOT use an alternate next-hop that is along a link for 612 which the link has been advertised with the attribute "link excluded 613 from local protection path" or with the attribute "local maintenance 614 required". 616 3.6. Selection Procedure 618 A router supporting this specification SHOULD attempt to select at 619 least one loop-free alternate next-hop for each primary next-hop used 620 for a given prefix. A router MAY decide to not use an available 621 loop-free alternate next-hop. A reason for such a decision might be 622 that the loop-free alternate next-hop does not provide protection for 623 the failure scenario of interest. 625 The alternate selection should maximize the coverage of the failure 626 cases. 628 When calculating alternate next-hops, the calculating router S 629 applies the following rules. 631 1. S SHOULD select a loop-free node-protecting alternate next-hop, 632 if one is available. If no loop-free node-protecting alternate 633 is available, then S MAY select a loop-free link-protecting 634 alternate. 636 2. If S has a choice between a loop-free link-protecting node- 637 protecting alternate and a loop-free node-protecting alternate 638 which is not link-protecting, S SHOULD select a loop-free node- 639 protecting alternate which is also link-protecting. This can 640 occur as explained in Section 3.3. 642 3. If S has multiple primary next-hops, then S SHOULD select as a 643 loop-free alternate either one of the other primary next-hops or 644 a loop-free node-protecting alternate if available. If no loop- 645 free node-protecting alternate is available and no other primary 646 next-hop can provide link-protection, then S SHOULD select a 647 loop-free link-protecting alternate. 649 4. Implementations SHOULD support a mode where other primary next- 650 hops satisfying the basic loop-free condition and providing at 651 least link or node protection are preferred over any non-primary 652 alternates. This mode is provided to allow the administrator to 653 preserve traffic patterns based on regular ECMP behavior. 655 5. Implementations considering SRLGs MAY use SRLG-protection to 656 determine that a node-protecting or link-protecting alternate is 657 not available for use. 659 Following the above rules maximizes the level of protection and use 660 of primary (ECMP) next-hops. 662 Each next-hop is associated with a set of non-mutually-exclusive 663 characteristics based on whether it is used as a primary next-hop to 664 a particular destination D, and the type of protection it can provide 665 relative to a specific primary next-hop E: 667 Primary Path - The next-hop is used by S as primary. 669 Loop-Free Node-Protecting Alternate - This next-hop satisfies 670 Inequality 1 and Inequality 3. The path avoids S, S's primary 671 neighbor E, and the link from S to E. 673 Loop-Free Link-Protecting Alternate - This next-hop satisfies 674 Inequality 1 but not Inequality 3. If the primary next-hop uses a 675 broadcast link, then this next-hop satisfies Inequality 4. 677 An alternate path may also provide none, some or complete SRLG 678 protection as well as node and link or link protection. For 679 instance, a link may belong to two SRLGs G1 and G2. The alternate 680 path might avoid other links in G1 but not G2, in which case the 681 alternate would only provide partial SRLG protection. 683 Below is an algorithm that can be used to calculate loop-free 684 alternate next-hops. The algorithm is given for informational 685 purposes and implementations are free to use any other algorithm as 686 long as it satisfies the rules described above. 688 The following procedure describes how to select an alternate next- 689 hop. The procedure is described to determine alternate next-hops to 690 use to reach each router in the topology. Prefixes that are 691 advertised by a single router can use the alternate next-hop computed 692 for the router to which they are attached. The same procedure can be 693 used to reach a prefix that is advertised by more than one router 694 when the logical topological transformation described in Section 6.1 695 is used. 697 S is the computing router and has candidate next-hops H_1 through 698 H_k. N_i and N_j are used to refer to neighbors of S. For a next-hop 699 to be a candidate, the next-hop must be associated with a bi- 700 directional link, as is determined by the IGP. For a particular 701 destination router D, let S have already computed D_opt(S, D), and 702 for each neighbor N_i, D_opt(N_i, D), D_opt(N_i, S), and D_opt(N_i, 703 N_j), the distance from N_i to each other neighbor N_j, and the set 704 of SRLGs traversed by the path D_opt(N_i, D). S should follow the 705 below procedure for every primary next-hop selected to reach D. This 706 set of primary next-hops is represented P_1 to P_p. This procedure 707 finds the alternate next-hop(s) for P_i. 709 First, initialize the alternate information for P_i as follows: 711 P_i.alt_next_hops = {} 712 P_i.alt_type = NONE 713 P_i.alt_link-protect = FALSE 714 P_i.alt_node-protect = FALSE 715 P_i.alt_srlg-protect = {} 717 For each candidate next-hop H_h, 719 1. Initialize variables as follows: 721 cand_type = NONE 722 cand_link-protect = FALSE 723 cand_node-protect = FALSE 724 cand_srlg-protect = {} 726 2. If H_h is P_i, skip it and continue to the next candidate next- 727 hop. 729 3. If H_h.link is administratively allowed to be used as an 730 alternate, 732 and the cost of H_h.link is less than the maximum, 733 and the reverse cost of H_h is less than the maximum, 734 and H_h.neighbor is not overloaded (for ISIS), 735 and H_h.link is bi-directional, 737 then H_h can be considered as an alternate. Otherwise, skip it 738 and continue to the next candidate next-hop. 740 4. If D_opt( H_h.neighbor, D) >= D_opt( H_h.neighbor, S) + D_opt(S, 741 D), then H_h is not loop-free. Skip it and continue to the next 742 candidate next-hop. 744 5. cand_type = LOOP-FREE. 746 6. If H_h is a primary next-hop, set cand_type to PRIMARY. 748 7. If H_h.link is not P_i.link, set cand_link-protect to TRUE. 750 8. If D_opt(H_h.neighbor, D) < D_opt(H_h.neighbor, P_i.neighbor) + 751 D_opt(P_i.neighbor, D), set cand_node-protect to TRUE. 753 9. If the router considers SRLGs, then set the cand_srlg-protect to 754 the set of SRLGs traversed on the path from S via P_i to 755 P_i.neighbor. Remove the set of SRLGs to which H_h belongs from 756 cand_srlg-protect. Remove from cand_srlg-protect the set of 757 SRLGs traversed on the path from H_h.neighbor to D. Now 758 cand_srlg-protect holds the set of SRLGs to which P_i belongs 759 and that are not traversed on the path from S via H_h to D. 761 10. If cand_type is PRIMARY, the router prefers other primary next- 762 hops for use as the alternate, and the P_i.alt_type is not 763 PRIMARY, goto Step 19. 765 11. If cand_node-protect is TRUE and P_i.alt_node-protect is FALSE, 766 goto Paragraph 19. 768 12. If cand_link-protect is TRUE and P_i.alt_link-protect is FALSE, 769 goto Step 19. 771 13. If cand_srlg-protect has a better set of SRLGs than 772 P_i.alt_srlg-protect, goto Step 19. 774 14. If cand_srlg-protect is different from P_i.alt_srlg-protect, 775 then select between H_h and P_i.alt_next_hops based upon 776 distance, IP addresses, or any router-local tie-breaker. If H_h 777 is preferred, then goto Step 19. Otherwise, skip H_h and 778 continue to the next candidate next-hop. 780 15. If D_opt(H_h.neighbor, D) < D_opt(P_i.neighbor, D) and 781 D_opt(P_i.alt_next_hops, D) >= D_opt(P_i.neighbor, D), then H_h 782 is a downstream alternate and P_i.alt_next_hops is simply an 783 LFA. Prefer H_h and goto Step 19. 785 16. Based upon the alternate types, the alternate distances, IP 786 addresses, or other tie-breakers, decide if H_h is preferred to 787 P_i.alt_next_hops. If so, goto Step 19. 789 17. Decide if P_i.alt_next_hops is preferred to H_h. If so, then 790 skip H_h and continue to the next candidate next-hop. 792 18. Add H_h into P_i.alt_next_hops. Set P_i.alt_type to the better 793 type of H_h.alt_type and P_i.alt_type. Continue to the next 794 candidate next-hop. 796 19. Replace the P_i alternate next-hop set with H_h as follows: 798 P_i.alt_next_hops = {H_h} 799 P_i.alt_type = cand_type 800 P_i.alt_link-protect = cand_link-protect 801 P_i.alt_node-protect = cand_node-protect 802 P_i.alt_srlg-protect = cand_srlg-protect 804 Continue to the next candidate next-hop. 806 3.7. A Simplification: Per-Next-Hop LFAs 808 It is possible to simplify the computation and use of LFAs when 809 solely link protection is desired by considering and computing only 810 one link-protecting LFA for each next-hop connected to the router. 811 All prefixes that use that next-hop as a primary will use the LFA 812 computed for that next-hop as its LFA. 814 Even a prefix with multiple primary next-hops will have each primary 815 next-hop protected individually by the primary next-hop's associated 816 LFA. That associated LFA might or might not be another of the 817 primary next-hops of the prefix. 819 This simplification may reduce coverage in a network. In addition to 820 limiting protection for multi-homed prefixes (see Section 6.1), the 821 computation per next-hop may also not find an LFA when one could be 822 found for some of the prefixes that use that next-hop. 824 For example, consider Figure 4 where S has 3 ECMP next-hops, E1, E2, 825 and E3 to reach D. For the prefix D, E3 can give link protection for 826 the next-hops E1 and E2; E1 and E2 can give link protection for the 827 next-hops E3. However, if one uses this simplification to compute 828 LFAs for E1, E2 and E3 individually, there is no link-protecting LFA 829 for E1. E3 and E2 can protect each other. 831 4. Using an Alternate 833 If an alternate next-hop is available, the router redirects traffic 834 to the alternate next-hop in case of a primary next-hop failure as 835 follows. 837 When a next-hop failure is detected via a local interface failure or 838 other failure detection mechanisms (see [FRAMEWORK]), the router 839 SHOULD: 841 1. Remove the primary next-hop associated with the failure. 843 2. Install the loop-free alternate calculated for the failed next- 844 hop if it is not already installed (e.g. the alternate is also a 845 primary next-hop). 847 Note that the router MAY remove other next-hops if it believes (via 848 SRLG analysis) that they may have been affected by the same failure, 849 even if it is not visible at the time of failure detection. 851 The alternate next-hop MUST be used only for traffic types which are 852 routed according to the shortest path. Multicast traffic is 853 specifically out of scope for this specification. 855 4.1. Terminating Use of Alternate 857 A router MUST limit the amount of time an alternate next-hop is used 858 after the primary next-hop has become unavailable. This ensures that 859 the router will start using the new primary next-hops. It ensures 860 that all possible transient conditions are removed and the network 861 converges according to the deployed routing protocol. 863 A router that implements [I-D.ietf-rtgwg-microloop-analysis] SHOULD 864 follow the rules given there for terminating the use of an alternate. 866 A router that implements [I-D.francois-ordered-fib] SHOULD follow the 867 rules given there for terminating the use of an alternate. 869 It is desirable to avoid micro-forwarding loops involving S. An 870 example illustrating the problem is given in Figure 5. If the link 871 from S to E fails, S will use N1 as an alternate and S will compute 872 N2 as the new primary next-hop to reach D. If S starts using N2 as 873 soon as S can compute and install its new primary, it is probable 874 that N2 will not have yet installed its new primary next-hop. This 875 would cause traffic to loop and be dropped until N2 has installed the 876 new topology. This can be avoided by S delaying its installation and 877 leaving traffic on the alternate next-hop. 879 +-----+ 880 | N2 |-------- | 881 +-----+ 1 | \|/ 882 | | 883 | +-----+ @@> +-----+ 884 | | S |---------| N1 | 885 10 | +-----+ 10 +-----+ 886 | | | 887 | 1 | | | 888 | | \|/ 10 | 889 | +-----+ | | 890 | | E | | \|/ 891 | +-----+ | 892 | | | 893 | 1 | | | 894 | | \|/ | 895 | +-----+ | 896 |----| D |-------------- 897 +-----+ 899 Figure 5: Example where Continued Use of Alternate is Desirable 901 This is an example of a case where the new primary is not a loop-free 902 alternate before the failure and therefore may have been forwarding 903 traffic through S. This will occur when the path via a previously 904 upstream node is shorter than the the path via a loop-free alternate 905 neighbor. In these cases, it is useful to give sufficient time to 906 ensure that the new primary neighbor and other nodes on the new 907 primary path have switched to the new route. 909 If the newly selected primary was loop-free before the failure, then 910 it is safe to switch to that new primary immediately; the new primary 911 wasn't dependent on the failure and therefore its path will not have 912 changed. 914 Given that there is an alternate providing appropriate protection and 915 while the assumption of a single failure holds, it is safe to delay 916 the installation of the new primaries; this will not create 917 forwarding loops because the alternate's path to the destination is 918 known to not go via S or the failed element and will therefore not be 919 affected by the failure. 921 An implementation SHOULD continue to use the alternate next-hops for 922 packet forwarding even after the new routing information is available 923 based on the new network topology. The use of the alternate next- 924 hops for packet forwarding SHOULD terminate: 926 a. if the new primary next-hop was loop-free prior to the topology 927 change, or 929 b. if a configured hold-down, which represents a worst-case bound on 930 the length of the network convergence transition, has expired, or 932 c. if notification of an unrelated topological change in the network 933 is received. 935 5. Requirements on LDP Mode 937 Since LDP [RFC3036] traffic will follow the path specified by the 938 IGP, it is also possible for the LDP traffic to follow the loop-free 939 alternates indicated by the IGP. To do so, it is necessary for LDP 940 to have the appropriate labels available for the alternate so that 941 the appropriate out-segments can be installed in the forwarding plane 942 before the failure occurs. 944 This means that a Label Switched Router (LSR) running LDP must 945 distribute its labels for the FECs it can provide to all its 946 neighbors, regardless of whether or not they are upstream. 947 Additionally, LDP must be acting in liberal label retention mode so 948 that the labels which correspond to neighbors that aren't currently 949 the primary neighbor are stored. Similarly, LDP should be in 950 downstream unsolicited mode, so that the labels for the FEC are 951 distributed other than along the SPT. 953 If these requirements are met, then LDP can use the loop-free 954 alternates without requiring any targeted sessions or signaling 955 extensions for this purpose. 957 6. Routing Aspects 959 6.1. Multi-Homed Prefixes 961 An SPF-like computation is run for each topology, which corresponds 962 to a particular OSPF area or ISIS level. The IGP needs to determine 963 loop-free alternates to multi-homed routes. Multi-homed routes occur 964 for routes obtained from outside the routing domain by multiple 965 routers, for subnets on links where the subnet is announced from 966 multiple ends of the link, and for routes advertised by multiple 967 routers to provide resiliency. 969 Figure 6 demonstrates such a topology. In this example, the shortest 970 path to reach the prefix p is via E. The prefix p will have the link 971 to E as its primary next-hop. If the alternate next-hop for the 972 prefix p is simply inherited from the router advertising it on the 973 shortest path to p, then the prefix p's alternate next-hop would be 974 the link to C. This would provide link protection, but not the node 975 protection that is possible via A. 977 5 +---+ 4 +---+ 5 +---+ 978 ------| S |------| A |-----| B | 979 | +---+ +---+ +---+ 980 | | | 981 | 5 | 5 | 982 | | | 983 +---+ 5 +---+ 5 7 +---+ 984 | C |---| E |------ p -------| F | 985 +---+ +---+ +---+ 987 Figure 6: Multi-homed prefix 989 To determine the best protection possible, the prefix p can be 990 treated in the SPF computations as a node with uni-directional links 991 to it from those routers that have advertised the prefix. Such a 992 node need never have its links explored, as it has no out-going 993 links. 995 If there exist multiple multi-homed prefixes that share the same 996 connectivity and the difference in metrics to those routers, then a 997 single node can be used to represent the set. For instance, if in 998 Figure 6 there were another prefix X that was connected to E with a 999 metric of 1 and to F with a metric of 3, then that prefix X could use 1000 the same alternate next-hop as was computed for prefix p. 1002 A router SHOULD compute the alternate next-hop for an IGP multi-homed 1003 prefix by considering alternate paths via all routers that have 1004 announced that prefix. 1006 6.2. ISIS 1008 The applicability and interactions of LFAs with multi-topology ISIS 1009 [I-D.ietf-isis-wg-multi-topology] is out of scope for this 1010 specification. 1012 6.3. OSPF 1014 OSPF introduces certain complications because it is possible for the 1015 traffic path to exit an area and then re-enter that area. This can 1016 occur whenever a router considers the same route from multiple areas. 1017 There are several cases where issues such as this can occur. They 1018 happen when another area permits a shorter path to connect two ABRs 1019 than is available in the area where the LFA has been computed. To 1020 clarify, an example topology is given in Appendix A. 1022 a. Virtual Links: These allow paths to leave the backbone area and 1023 traverse the transit area. The path provided via the transit 1024 area can exit via any ABR. The path taken is not the shortest 1025 path determined by doing an SPF in the backbone area. 1027 b. Alternate ABR[RFC3509]: When an ABR is not connected to the 1028 backbone, it considers the inter-area summaries from multiple 1029 areas. The ABR A may determine to use area 2 but that path could 1030 traverse another alternate ABR B that determines to use area 1. 1031 This can lead to scenarios similar to that illustrated in 1032 Figure 7. 1034 c. ASBR Summaries: An ASBR may itself be an ABR and can be announced 1035 into multiple areas. This presents other ABRs with a decision as 1036 to which area to use. This is the example illustrated in 1037 Figure 7. 1039 d. AS External Prefixes: A prefix may be advertised by multiple 1040 ASBRs in different areas and/or with multiple forwarding 1041 addresses that are in different areas, which are connected via at 1042 least one common ABR. This presents such ABRs with a decision as 1043 to which area to use to reach the prefix. 1045 Loop-free alternates should not be used in an area where one of the 1046 above issues affects that area. 1048 6.3.1. OSPF External Routing 1050 When a forwarding address is set in an OSPF AS-external LSA, all 1051 routers in the network calculate their next-hops for the external 1052 prefix by doing a lookup for the forwarding address in the routing 1053 table, rather than using the next-hops calculated for the ASBR. In 1054 this case, the alternate next-hops SHOULD be computed by selecting 1055 among the alternate paths to the forwarding link(s) instead of among 1056 alternate paths to the ASBR. 1058 6.3.2. OSPF Multi-Topology 1060 The applicabilty and interactions of LFAs with multi-topology OSPF 1061 [I-D.ietf-ospf-mt] [I-D.ietf-ospf-mt-ospfv3] is out of scope for this 1062 specification. 1064 6.4. BGP Next-Hop Synchronization 1066 Typically BGP prefixes are advertised with AS exit routers router-id 1067 as the BGP next-hop, and AS exit routers are reached by means of IGP 1068 routes. BGP resolves its advertised next-hop to the immediate next- 1069 hop by potential recursive lookups in the routing database. IP Fast- 1070 Reroute computes the alternate next-hops to all IGP destinations, 1071 which include alternate next-hops to the AS exit router's router-id. 1072 BGP simply inherits the alternate next-hop from IGP. The BGP 1073 decision process is unaltered; BGP continues to use the IGP optimal 1074 distance to find the nearest exit router. MBGP routes do not need to 1075 copy the alternate next hops. 1077 It is possible to provide ASBR protection if BGP selected a set of 1078 BGP next-hops and allowed the IGP to determine the primary and 1079 alternate next-hops as if the BGP route were a multi-homed prefix. 1080 This is for future study. 1082 6.5. Multicast Considerations 1084 Multicast traffic is out of scope for this specification of IP Fast- 1085 Reroute. The alternate next-hops SHOULD NOT be used for multicast 1086 RPF checks. 1088 7. Security Considerations 1090 The mechanism described in this document does not modify any routing 1091 protocol messages, and hence no new threats related to packet 1092 modifications or replay attacks are introduced. Traffic to certain 1093 destinations can be temporarily routed via next-hop routers that 1094 would not be used with the same topology change if this mechanism 1095 wasn't employed. However, these next-hop routers can be used anyway 1096 when a different topological change occurs, and hence this can't be 1097 viewed as a new security threat. 1099 In LDP, the wider distribution of FEC label information is still to 1100 neighbors with whom a trusted LDP session has been established. This 1101 wider distribution and the recommendation of using liberal label 1102 retention mode are believed to have no significant security impact. 1104 8. IANA Considerations 1106 This document requires no IANA considerations. 1108 9. Acknowledgements 1110 The authors would like to thank Joel Halpern, Mike Shand, Stewart 1111 Bryant, and Stefano Previdi for their assistance and useful review. 1113 10. References 1115 10.1. Normative References 1117 [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and 1118 dual environments", RFC 1195, December 1990. 1120 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 1122 [RFC2740] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6", 1123 RFC 2740, December 1999. 1125 [RFC2966] Li, T., Przygienda, T., and H. Smit, "Domain-wide Prefix 1126 Distribution with Two-Level IS-IS", RFC 2966, 1127 October 2000. 1129 [RFC3036] Andersson, L., Doolan, P., Feldman, N., Fredette, A., and 1130 B. Thomas, "LDP Specification", RFC 3036, January 2001. 1132 10.2. Informative References 1134 [I-D.francois-ordered-fib] 1135 Francois, P., "Loop-free convergence using oFIB", 1136 draft-francois-ordered-fib-02 (work in progress), 1137 October 2006. 1139 [I-D.ietf-isis-link-attr] 1140 Vasseur, J. and S. Previdi, "Definition of an IS-IS Link 1141 Attribute sub-TLV", draft-ietf-isis-link-attr-03 (work in 1142 progress), February 2007. 1144 [I-D.ietf-isis-wg-multi-topology] 1145 Przygienda, T., "M-ISIS: Multi Topology (MT) Routing in 1146 IS-IS", draft-ietf-isis-wg-multi-topology-11 (work in 1147 progress), October 2005. 1149 [I-D.ietf-ospf-mt] 1150 Psenak, P., "Multi-Topology (MT) Routing in OSPF", 1151 draft-ietf-ospf-mt-09 (work in progress), June 2007. 1153 [I-D.ietf-ospf-mt-ospfv3] 1154 Mirtorabi, S. and A. Roy, "Multi-topology routing in 1155 OSPFv3 (MT-OSPFv3)", draft-ietf-ospf-mt-ospfv3-03 (work in 1156 progress), July 2007. 1158 [I-D.ietf-ospf-ospfv3-update] 1159 Ferguson, D., "OSPF for IPv6", 1160 draft-ietf-ospf-ospfv3-update-17 (work in progress), 1161 August 2007. 1163 [I-D.ietf-rtgwg-ipfrr-framework] 1164 Shand, M. and S. Bryant, "IP Fast Reroute Framework", 1165 draft-ietf-rtgwg-ipfrr-framework-07 (work in progress), 1166 July 2007. 1168 [I-D.ietf-rtgwg-microloop-analysis] 1169 Zinin, A., "Analysis and Minimization of Microloops in 1170 Link-state Routing Protocols", 1171 draft-ietf-rtgwg-microloop-analysis-01 (work in progress), 1172 October 2005. 1174 [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. 1175 McPherson, "OSPF Stub Router Advertisement", RFC 3137, 1176 June 2001. 1178 [RFC3509] Zinin, A., Lindem, A., and D. Yeung, "Alternative 1179 Implementations of OSPF Area Border Routers", RFC 3509, 1180 April 2003. 1182 [RFC4203] Kompella, K. and Y. Rekhter, "OSPF Extensions in Support 1183 of Generalized Multi-Protocol Label Switching (GMPLS)", 1184 RFC 4203, October 2005. 1186 [RFC4205] Kompella, K. and Y. Rekhter, "Intermediate System to 1187 Intermediate System (IS-IS) Extensions in Support of 1188 Generalized Multi-Protocol Label Switching (GMPLS)", 1189 RFC 4205, October 2005. 1191 Appendix A. OSPF Example Where LFA Based on Local Area Topology is 1192 Insufficient 1194 This appendix provides an example scenario where the local area 1195 topology does not suffice to determine that an LFA is available. As 1196 described in Section 6.3, one problem scenario is for ASBR summaries 1197 where the ASBR is available in two areas via intra-area routes and 1198 there is at least one ABR or alternate ABR that is in both areas. 1199 The following Figure 7 illustrates this case. 1201 5 1202 [ F ]-----------[ C ] 1203 | | 1204 | | 5 1205 20 | 5 | 1 1206 | [ N ]-----[ A ]*****[ F ] 1207 | | # * 1208 | 40 | # 50 * 2 1209 | | 5 # 2 * 1210 | [ S ]-----[ B ]*****[ G ] 1211 | | * 1212 | 5 | * 15 1213 | | * 1214 | [ E ] [ H ] 1215 | | * 1216 | 5 | * 10** 1217 | | * 1218 |---[ X ]-----[ASBR] 1219 5 1221 ---- Link in Area 1 1222 **** Link in Area 2 1223 #### Link in Backbone Area 0 1225 Figure 7: Topology with Multi-area ASBR Causing Area Transiting 1227 In Figure 7, the ASBR is also an ABR and is announced into both area 1228 1 and area 2. A and B are both ABRs that are also connected to the 1229 backbone area. S determines that N can provide a loop-free alternate 1230 to reach the ASBR. N's path goes via A. A also sees an intra-area 1231 route to ASBR via Area 2; the cost of the path in area 2 is 30, which 1232 is less than 35, the cost of the path in area 1. Therefore, A uses 1233 the path from area 2 and directs traffic to F. The path from F in 1234 area 2 goes to B. B is also an ABR and learns the ASBR from both 1235 areas 1 and area 2; B's path via area 1 is shorter (cost 20) than B's 1236 path via area 2 (cost 25). Therefore, B uses the path from area 1 1237 that connects to S. 1239 Authors' Addresses 1241 Alia K. Atlas (editor) 1242 Google, Inc. 1243 One Broadway, 7th Floor 1244 Cambridge, MA 02142 1245 USA 1247 Email: akatlas@google.com 1249 Alex Zinin (editor) 1250 Alcatel 1251 701 E Middlefield Rd. 1252 Mountain View, CA 94043 1253 USA 1255 Email: alex.zinin@alcatel.com 1257 Raveendra Torvi 1258 FutureWei Technologies Inc. 1259 1700 Alma Dr. Suite 100 1260 Plano, TX 75075 1261 USA 1263 Email: traveendra@huawei.com 1265 Gagan Choudhury 1266 AT&T 1267 200 Laurel Avenue, Room D5-3C21 1268 Middletown, NJ 07748 1269 USA 1271 Phone: +1 732 420-3721 1272 Email: gchoudhury@att.com 1274 Christian Martin 1275 iPath Technologies 1277 Email: chris@ipath.net 1278 Brent Imhoff 1279 Juniper Networks 1280 1194 North Mathilda 1281 Sunnyvale, CA 94089 1282 USA 1284 Phone: +1 314 378 2571 1285 Email: bimhoff@planetspork.com 1287 Don Fedyk 1288 Nortel Networks 1289 600 Technology Park 1290 Billerica, MA 01821 1291 USA 1293 Phone: +1 978 288 3041 1294 Email: dwfedyk@nortelnetworks.com 1296 Full Copyright Statement 1298 Copyright (C) The IETF Trust (2007). 1300 This document is subject to the rights, licenses and restrictions 1301 contained in BCP 78, and except as set forth therein, the authors 1302 retain all their rights. 1304 This document and the information contained herein are provided on an 1305 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1306 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1307 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1308 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1309 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1310 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1312 Intellectual Property 1314 The IETF takes no position regarding the validity or scope of any 1315 Intellectual Property Rights or other rights that might be claimed to 1316 pertain to the implementation or use of the technology described in 1317 this document or the extent to which any license under such rights 1318 might or might not be available; nor does it represent that it has 1319 made any independent effort to identify any such rights. Information 1320 on the procedures with respect to rights in RFC documents can be 1321 found in BCP 78 and BCP 79. 1323 Copies of IPR disclosures made to the IETF Secretariat and any 1324 assurances of licenses to be made available, or the result of an 1325 attempt made to obtain a general license or permission for the use of 1326 such proprietary rights by implementers or users of this 1327 specification can be obtained from the IETF on-line IPR repository at 1328 http://www.ietf.org/ipr. 1330 The IETF invites any interested party to bring to its attention any 1331 copyrights, patents or patent applications, or other proprietary 1332 rights that may cover technology that may be required to implement 1333 this standard. Please address the information to the IETF at 1334 ietf-ipr@ietf.org. 1336 Acknowledgment 1338 Funding for the RFC Editor function is provided by the IETF 1339 Administrative Support Activity (IASA).