idnits 2.17.1 draft-atlas-ip-local-protect-loopfree-00.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 3667, Section 5.1 on line 16. ** Found boilerplate matching RFC 3978, Section 5.4, paragraph 1 (on line 752), which is fine, but *also* found old RFC 2026, Section 10.4C, paragraph 1 text on line 752. ** The document claims conformance with section 10 of RFC 2026, but uses some RFC 3978/3979 boilerplate. As RFC 3978/3979 replaces section 10 of RFC 2026, you should not claim conformance with it if you have changed to using RFC 3978/3979 boilerplate. ** The document seems to lack an RFC 3978 Section 5.1 IPR Disclosure Acknowledgement -- however, there's a paragraph with a matching beginning. Boilerplate error? ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** The document seems to lack an RFC 3978 Section 5.4 Reference to BCP 78. ** The document seems to lack an RFC 3978 Section 5.5 (updated by RFC 4748) Disclaimer -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack an RFC 3979 Section 5, para. 1 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 2 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 3 IPR Disclosure Invitation. ** The document uses RFC 3667 boilerplate or RFC 3978-like boilerplate instead of verbatim RFC 3978 boilerplate. After 6 May 2005, submission of drafts without verbatim RFC 3978 boilerplate is not accepted. The following non-3978 patterns matched text found in the document. That text should be removed or replaced: By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, or will be disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack an Authors' Addresses Section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 6 instances of too long lines in the document, the longest one being 11 characters in excess of 72. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 416: '...ernate, a router MUST not consider div...' RFC 2119 keyword, line 474: '...neighbor, then S SHOULD select a loop-...' RFC 2119 keyword, line 476: '...vailable, then S MAY select a loop-fre...' RFC 2119 keyword, line 659: '...itance procedure SHOULD select a loop-...' RFC 2119 keyword, line 741: '...ernate next-hops SHOULD not used for m...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 217 has weird spacing: '...ier and illus...' == Line 762 has weird spacing: '...for the purpo...' == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: For computing an alternate, a router MUST not consider diverting from the SPF tree along a link whose reverse cost is LSInfinity (for OSPF) or whose router has the overload bit set (for ISIS). == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'SHOULD not' in this paragraph: IP/LDP Local Protection does not apply to multicast traffic. The alternate next-hops SHOULD not used for multi-cast RPF checks. -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'LDP' is defined on line 783, but no explicit reference was found in the text == Unused Reference: 'RSVP-TE' is defined on line 786, but no explicit reference was found in the text == Unused Reference: 'RSVP-TE FRR' is defined on line 790, but no explicit reference was found in the text == Unused Reference: 'RFC3137' is defined on line 795, but no explicit reference was found in the text == Unused Reference: 'RFC3277' is defined on line 798, but no explicit reference was found in the text == Unused Reference: 'ISIS' is defined on line 801, but no explicit reference was found in the text == Unused Reference: 'RFC2966' is defined on line 804, but no explicit reference was found in the text == Unused Reference: 'OSPF' is defined on line 807, but no explicit reference was found in the text == Unused Reference: 'RFC2370' is defined on line 809, but no explicit reference was found in the text == Outdated reference: A later version (-13) exists of draft-ietf-rtgwg-ipfrr-framework-01 ** Downref: Normative reference to an Informational draft: draft-ietf-rtgwg-ipfrr-framework (ref. 'FRAMEWORK') ** Obsolete normative reference: RFC 3036 (ref. 'LDP') (Obsoleted by RFC 5036) == Outdated reference: A later version (-07) exists of draft-ietf-mpls-rsvp-lsp-fastreroute-06 ** Obsolete normative reference: RFC 3137 (Obsoleted by RFC 6987) ** Downref: Normative reference to an Informational RFC: RFC 3277 ** Obsolete normative reference: RFC 2966 (Obsoleted by RFC 5302) ** Obsolete normative reference: RFC 2370 (Obsoleted by RFC 5250) Summary: 23 errors (**), 0 flaws (~~), 17 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Draft Alia Atlas, Ed (Avici Systems) 2 Expires: November 2004 4 Loop-Free Alternates for IP/LDP Local Protection 6 draft-atlas-ip-local-protect-loopfree-00.txt 8 Status of this Memo 10 This document is an Internet-Draft and is in full conformance with 11 all provisions of Section 10 of RFC2026. 13 By submitting this Internet-Draft, I certify that any applicable 14 patent or other IPR claims of which I am aware have been disclosed, 15 or will be disclosed, and any of which I become aware will be 16 disclosed, in accordance with RFC 3668. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as ``work in progress.'' 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 Abstract 36 This document defines an architecture and selection process for 37 providing local protection for IP unicast and/or LDP traffic in the 38 event of a single link or node failure until the router has 39 converged. When computing the primary next-hop for a prefix, a 40 router S also determines an alternate next-hop which can be used if 41 the primary next-hop fails. The alternate next-hop is said to be a 42 loop-free alternate, which goes to a neighbor whose shortest path to 43 the prefix does not go back through the router S. 45 Contents 47 1 Introduction ................................................. 2 48 2 Terminology .................................................. 4 49 3 Finding an Alternate ......................................... 5 50 3.1 Loop-Free Alternates ....................................... 6 51 3.2 Selection of an Alternate .................................. 7 52 3.2.1 Failure Scenarios ........................................ 7 53 3.2.2 Broadcast and NBMA Interfaces ............................ 9 54 3.2.3 Interactions wtih ISIS Overload, RFC 3137 55 and Costed Out Links ..................................... 9 56 3.2.4 Characterization of Neighbors ............................ 10 57 3.2.5 Selection Procedure ...................................... 10 58 4 Using an Alternate ........................................... 11 59 5 Requirements on LDP Mode ..................................... 11 60 6 Routing Aspects .............................................. 12 61 6.1 Multiple-Region Routing .................................... 12 62 6.1.1 Inheriting Alternate Next-Hops with One Primary Neighbor . 14 63 6.1.2 OSPF Inter-Area Routes ................................... 15 64 6.1.3 OSPF Inter-Area Routes ................................... 15 65 6.1.4 ISIS Multi-Level Routing ................................. 15 66 6.2 OSPF Virtual Links ......................................... 15 67 6.3 BGP Next-Hop Synchronization ............................... 16 68 6.4 Multicast Considerations ................................... 16 69 7 Security Considerations ...................................... 16 70 8 Full Copyright Statement ..................................... 17 71 9 References ................................................... 17 72 10 Authors Information .......................................... 18 73 11 Editor's Information ......................................... 19 74 Appendix A Loop-Free Alternate Proofs .......................... 19 75 Appendix A.1 Loop-Free Node-Protecting Alternate Proofs ........ 21 77 1. Introduction 79 Applications for interactive multimedia services such as VoIP and 80 pseudo-wires can be very sensitive to traffic loss, such as occurs 81 when a link or router in the network fails. A router's convergence 82 time is generally on the order of seconds; the application traffic 83 may be sensitive to losses greater than 10s of milliseconds. 85 As discussed in [FRAMEWORK], minimizing traffic loss requires a 86 mechanism for the router adjacent to a failure rapidly invoke a 87 repair path, which is minimally affected by any subsequent re- 88 convergence. This document describes such a mechanism which allows a 89 router whose local link has failed to forward traffic to a pre- 90 computed alternate until the router installs the new primary next- 91 hops based upon the changed network topology. 93 When a local link fails, a router currently must signal the event to 94 its neighbors via the IGP, recompute new primary next-hops for all 95 affected prefixes, and only then install those new primary next-hops 96 into the forwarding plane. Until the new primary next-hops are 97 installed, traffic directed towards the affected prefixes is 98 discarded. This process can take seconds. 100 /__ 101 \ +-----+ 102 /------| S |--\ 103 / +-----+ \ 104 / 5 8 \ 105 / \ 106 +-----+ +-----+ 107 | P | | N_1 | 108 +-----+ +-----+ 109 \ / 110 \ \ 4 3 / / 111 \| \ / |/ 112 -+ \ +-----+ / +- 113 \---| D |---/ 114 +-----+ 116 Figure 1: Basic Topology 118 The goal of IP/LDP Local Protection is to reduce that traffic 119 convergence time to 10s of milliseconds by using a pre-computed 120 alternate interface, in the event that the currently selected primary 121 interface fails, so that the alternate can be rapidly used when the 122 failure is detected. 124 To clarify the behavior of IP/LDP Local Protection, consider the 125 simple topology in Figure 1. When router S computes its shortest 126 path to router D, router S determines to use the interface to router 127 P as its primary next-hop. Without IP/LDP Local Protection, that 128 interface is the only next-hop that router S computes to reach D. 129 With IP/LDP Local Protection, S also looks for an alternate next-hop 130 interface to use. In this example, S would determine that it could 131 send traffic destined to D by using the interface to router N_1 and 132 therefore S would install the interface to N_1 as its alternate 133 next-hop. At some later time, the link between router S and router P 134 could fail. When that link fails, S (and most likely P) will be the 135 first to detect it. On detecting the failure, S will stop sending 136 traffic destined for D towards P via the failed link, and instead 137 send the traffic to S's pre-computed alternate next-hop, which is the 138 interface to N_1, until a new SPF is run and its results are 139 installed. As with the primary next-hop, an alternate next-hop is 140 computed for each destination. The process of computing an alternate 141 next-hop does not alter the primary next-hop computed via a standard 142 SPF. The alternate next-hop can protect against a single link or 143 node failure. 145 If in the example of Figure 1, the link cost from N_1 to D increased 146 to 30 from 3, then N_1 would not be a loop-free alternate, because 147 the cost of the path from N_1 to D via S would be 17 while the cost 148 from N_1 directly to D would be 30. In real networks, we may often 149 face this situation. The existence of a suitable loop-free alternate 150 next-hop is topology dependent. 152 2. Terminology 154 SPT --- Shortest Path Tree 156 D --- The destination router under discussion. 158 S --- The source router under discussion. It is the viewpoint from 159 which IP/LDP Local Protection is described. 161 P --- The router which is the primary next-hop neighbor to get from S 162 to D. Where there is an ECMP set for the shortest path from S 163 to D, these will be referred to as P_1, P_2, etc. 165 N_i --- The ith neighbor of S 167 R_i_j --- The jth neighbor of N_i, the ith neighbor of S. 169 Distance_!S(N_i, D) --- The distance of the shortest path from N_i to 170 D which does not go through router S. 172 Distance_opt(A, B) --- The distance of the shortest path from A to B. 174 Reverse Distance of a node X --- This is the Distance_opt(X, S). 176 Loop-Free Alternate --- This is a next-hop that is not a primary 177 next-hop whose shortest path to the destination from the 178 alternate neighbor does not go back through the router S. 179 This is also known as a downstream path or a feasible 180 alternate. 182 Downstream Path --- This is a loop-free alternate. 184 Link(A->B) --- A link connecting router A to router B. 186 ____\ This is an arrow indicating the primary next-hop towards D. 187 / 189 @@@@\ This is an arrow indicating the alternate next-hop towards D 190 / 192 Primary Neighbor --- One or more of the primary next-hops for S to 193 reach the destination D goes directly to this neighbor. 195 Loop-Free Neighbor --- A Neighbor N_i which is not the primary 196 neighbor and whose shortest path to D does not go through S. 198 Loop-Free Node-Protecting Alternate --- This is a path via a Loop- 199 Free Neighbor N_i which does not go through the particular 200 primary neighbor of S which is being protected to reach the 201 destination D. 203 Loop-Free Link-Protecting Alternate --- This is a path via a Loop- 204 Free Neighbor N_i which does go through the particular primary 205 neighbor of S which is being protected to reach the destination 206 D. 208 Upstream Forwarding Loop --- This is a forwarding loop which involves 209 a set of routers, none of which are directly connected to the 210 link which has caused the topology change that triggered a new 211 SPF in any of the routers. 213 3. Finding an Alternate 215 As with primary next-hops, an alternate next-hop is discussed in 216 relation to a particular destination router D. For this discussion, 217 the following terminology, as described earlier and illustrated in 218 Figure 2, will be used. 220 In IP routing, a router S can join the shortest path tree (SPT) at 221 exactly one point -- itself. A loop-free alternate next-hop allows 222 traffic from S to D to deviate from the SPT and then rejoin it. For 223 instance, if S were to send traffic destined for D to N_1 instead of 224 P, thereby deviating from the SPT, then when N_1 received it, N_1 225 would send that traffic along its shortest path to D. 227 +-----+ 228 \ / _| R_2 | 229 +-----+__ \| |/ / +-----+ 230 | N_3 | \ -+ +- __/ \ 231 +-----+ \____ / \ 232 \ \ / \ 233 \ +-----+ \ 234 \ _| N_2 | \ 235 | __/ +-----+ \ 236 \ / \ | 237 \ / / \_ | 238 +-----+ |/ \ | 239 | S | +- \ +-----+ | 240 +-----+ \_| R_1 | | 241 / / \ +-----+ | 242 |/ / \ / | 243 +- / \ / | 244 / +-----+ / / | 245 +-----+/ | N_1 | / |/ | 246 | P | +-----+ / +- | 247 +-----+ \ / / 248 \ \ \__ / / 249 \ \ \| \ / / 250 \| \ -+ +-----+ / 251 -+ \_________________| D |---------/ 252 +-----+ 254 Figure 2: Topology for Terminology 256 3.1. Loop-Free Alternates 258 With loop-free alternates, the goal is to expand the set of points at 259 which S can cause its traffic to join the SPT. To illustrate this 260 let's first consider S's neighbors. Router S has the ability to send 261 traffic to any one of its neighbors N_i; this is the easiest possible 262 deviation from the SPT that S can cause to happen. Thus, all of 263 router S's neighbors are candidate alternates at which S could cause 264 traffic to rejoin the SPT. However, it is not useful for router S to 265 use a next-hop which results in traffic rejoining the SPT upstream of 266 S, such that the traffic will transit S again. This would cause a 267 loop. Avoiding a loop is thus the first constraint imposed on the 268 alternate next-hop. In Figure 2, S's neighbors N_2 and N_3 are not 269 loop-free alternate neighbors. 271 A next-hop which goes to a neighbor that does not have a loop back to 272 S and is not the primary next-hop may be selected as an alternate 273 next-hop. In Figure 2, that is the case for S's neighbor N_1. N_1 274 is referred to as a loop-free alternate with respect to traffic 275 flowing from S to D because there is no loop caused by forwarding 276 traffic for D to N_1. 278 An algorithm run on router S must be able to determine which 279 neighbors provide loop-free alternates. By running an SPF 280 computation from S's perspective, router S can determine the distance 281 from a neighbor N_i to the destination D for the optimal path that 282 does not go through S. This is referred to as Distance_!S(N_i, D). 283 If a neighbor N_i is a loop-free alternate, then it must be cheaper 284 (a lower metric) to get to the destination D without returning to S. 285 This gives the following requirement, where Distance_opt(A, B) gives 286 the distance of the optimal path from A to B. 288 Distance_!S(N_i, D) < Distance_opt(N_i, S) + Distance_opt(S, D) 290 Equation 1: Criteria for a Loop-Free Alternate 292 To check this equation, we can consider the other conditions where 293 this is not true. Recall that a router will take the shortest path 294 to a destination that it can see. Thus, if Distance_!S(N_i, D) > 295 Distance_opt(N_i, S) + Distance_opt(S, D), then router N_i will, 296 based on its own shortest path computations, determine to send 297 traffic destined for D to S. Similarly, if Distance_!S(N_i, D) = 298 Distance_opt(N_i, S) + Distance_opt(S, D), then router N_i has equal 299 cost paths to the destination D where one or more of those paths go 300 through S. In such a case where a router N_i has an ECMP set to 301 reach the destination and one or more paths go through S, then the 302 router N_i cannot provide a loop-free alternate because some traffic 303 destined to D may be sent back to S by N_i. 305 3.2. Selection of an Alternate 307 The selection of the alternate to use depends upon the failure 308 scenario for which the protection is intended. As with other 309 protection mechanisms, the alternate selected will protect against 310 only a single failure. It is possible to protect against a node 311 failure, which appears as correlated link failures, by explicitly 312 selecting a loop-free alternate which does not use that node. 314 3.2.1 Failure Scenarios 316 The simplest case is to locate an alternate which protects against a 317 link failure. 319 A loop-free link-protecting alternate may cause traffic looping in 320 the event of a node failure. This issue is illustrated in Figure 3. 321 If Link(S->P) fails, then the link-protecting alternate via N will 322 work correctly. However, if router P fails, then both S and N will 323 detect a failure and switch to their alternates. In this example, 324 that would cause S to redirect the traffic to N and N to redirect the 325 traffic to S and thus causing a forwarding loop. Such a scenario can 326 arise because the key assumption, that all other routers in the 327 network are forwarding based upon the shortest path, is violated 328 because of a second simultaneous correlated failure - another link 329 connected to the same primary neighbor. 331 / 332 \ @@@ 333 @@@ \ 334 +-----+ / +-----+ 335 | S |-------| N | 336 +-+---+ 5 +-----+ 337 | | 338 | 5 5 | | 339 | | | \|/ 340 \|/ | | 341 | +-----+ | 342 +----| P |---+ 343 +--+--+ 344 | 345 | 346 | 10 347 | 348 +--+--+ 349 | D | 350 +-----+ 351 Figure 3: Link-Protecting Alternates Causing Loop on Node Failure 353 Such a scenario may be a concern if node failure is not otherwise 354 protected against. 356 One way to solve such an issue is to add a constraint that the loop- 357 free alternate is loop-free with respect to P and the destination. 358 This gives a loop-free node-protecting alternate. An alternate will 359 be node-protecting if it doesn't go through the same primary neighbor 360 as the primary next-hop. This is the case if Equation 2 is true, 361 where N is the neighbor providing a loop-free alternate. 363 Distance_opt(N, D) < Distance_opt(N, P) + Distance_opt(P, D) 365 However unlike Equation 1, where if the equation did not hold, the neighbor 366 wasn't loop-free, if Equation 2 does not hold, the neighbor may still 367 provide a loop-free alternate that is not node-protecting. In the 368 case of ECMP, the neighbor may even provide a node-protecting loop- 369 free alternate, but S cannot determine this. 371 It may also be desirable to find an alternate which can protect 372 against other correlated failures. In the general case, these are 373 handled by shared risk link groups (SRLGs) where any links in the 374 network can belong to the SRLG. General SRLGs may add unacceptably 375 to the computational complexity of finding a loop-free alternate. 377 However, a sub-category of SRLGs is of interest and can be applied 378 only during the selection of an acceptable alternate. This sub- 379 category is to express correlated failures of links which are 380 connected to the same router. For example, if there are multiple 381 logical sub-interfaces on the same physical interface, such as VLANs 382 on an Ethernet interface, if multiple interfaces use the same 383 physical port because of channelization, or if multiple interfaces 384 share a correlated failure because they are on the same line-card. 385 This sub-category of SRLGs will be referred to as local-SRLGs. A 386 local-SRLG has all of its member links with one end connected to the 387 same router. Thus, router S could select a loop-free alternate which 388 does not use a link in the same local-SRLG as the primary next-hop. 389 The local-SRLGs belonging to P can be protected against via node- 390 protection; i.e. picking a loop-free node-protecting alternate. 392 3.2.2 Broadcast and NBMA Interfaces 394 The computation for node-protection and link-protection is a bit more 395 complicated for broadcast interfaces. In an SPF computation, a 396 broadcast interface is represented as a pseudo-node with links of 0 397 cost exiting the pseudo-node. For an alternate to be considered 398 link-protecting, it must avoid the pseudo-node. Thus, a potential 399 alternate which doesn't avoid the next node on the primary path 400 cannot be used as an alternate if the next node on the path is a 401 pseudo-node because the potential alternate would use the link that 402 may fail. Additionally, an alternate which would normally be termed 403 node-protecting because it avoided the next node on the primary path 404 may be only link-protecting. If the alternate avoids the pseudo-node 405 but goes through the next node on the path (i.e. the real neighbor of 406 S), then the alternate is link-protecting; if the alternate avoids 407 not only the pseudo-node but the following node on the primary path, 408 then the alternate is node-protecting. 410 3.2.3 Interactions with ISIS Overload, RFC 3137 and Costed Out Links 412 As described in RFC 3137, there are cases where it is desirable not 413 to have a router used as a transit node. For those cases, it is also 414 desirable not to have the router used on an alternate path. 416 For computing an alternate, a router MUST not consider diverting from 417 the SPF tree along a link whose reverse cost is LSInfinity (for OSPF) 418 or whose router has the overload bit set (for ISIS). 420 In the case of OSPF, if all links from router S to a neighbor N_i 421 have a reverse cost of LSInfinity, then router S cannot consider 422 using N_i as an alternate. 424 Similarly in the case of ISIS, if N_i has the overload bit set, then 425 S cannot consider using N_i as an alternate. 427 This preserves the desired behavior of diverting traffic away from a 428 router which is following RFC 3137 and it also preserves the desired 429 behavior when an operator sets the cost of a link to LSInfinity for 430 maintenance, of not permitting traffic across that link unless there 431 is no other path. 433 If a link or router which is costed out was the only possible 434 alternate to protect traffic from a particular router S to a 435 particular destination, then there will be no alternate provided for 436 protection. 438 3.2.4 Characterization of Neighbors 440 Each neighbor N_i can be categorized as to the type of path it can 441 provide to a particular destination D. Once the primary paths paths 442 have been determined and removed from consideration, each neighbor 443 can be characterized as providing a path in one of the following 444 categories for a particular destination D. It is possible for a 445 neighbor to provide both the primary path and a loop-free link- 446 protecting alternate. The path through the neighbor N_i is either a: 448 Loop-Free Node-Protecting Alternate - not a primary path and the 449 path avoids both S, one of S's primary neighbors on the path to 450 D and the interface connecting S to that primary neighbor. 452 Loop-Free Link-Protecting Alternate - not a primary path and the 453 path avoids S and an interface connecting S to one of S's 454 primary neighbors, but goes through that primary neighbor on the 455 path to D. Note that some neighbors of this type may have ECMP 456 paths to reach the destination, where some of those paths are 457 independent of the primary neighbor. 459 Unavailable - because the path goes through S to reach D, 460 because the interface to reach the neighbor is costed out, etc. 462 3.2.5 Selection Procedure 464 Once the neighbors have been categorized, a selection can be made. 465 The selection should maximize the failure cases which can be 466 protected against. 468 The selection procedure depends on whether S has a single primary 469 neighbor or multiple primary neighbors. A node S is defined to have 470 a single primary neighbor only if there are no equal cost paths that 471 go through any other neighbor; i.e., a node S cannot be considered to 472 have a single primary neighbor just because S does not support ECMP. 474 If S has a single primary neighbor, then S SHOULD select a loop-free 475 node-protecting alternate, if one is available. If none is 476 available, then S MAY select a loop-free link-protecting alternate. 478 If S has multiple primary neighbors, then S should select an 479 alternate to protect against the failure of each of the primary 480 next-hops. The loop-free alternate selected should be either one of 481 the other primary next-hops or should provide node-protection. 483 4. Using an Alternate 485 If an alternate is available, it is used to redirect traffic when the 486 primary next-hop has failed. 488 When a local interface failure is detected, traffic that was destined 489 to go out the failed interface must be redirected to the appropriate 490 alternate next-hops. The alternate next-hop is pre-computed to be 491 the most appropriate as mentioned in the selection criteria in the 492 event of the failure scenario being protected against (i.e. link or 493 node failure). 495 IP/LDP Local Protection does not require any mechanisms for the 496 detection of the failure. The same mechanisms that enable RSVP-TE 497 Fast-Reroute can work here. Because the alternate next-hop is pre- 498 computed, it should be extremely fast to switch traffic to use it, 499 exactly as is the case with RSVP-TE Fast-Reroute. 501 5. Requirements on LDP Mode 503 Since LDP traffic will follow the path specified by the IGP, it is 504 also possible for the LDP traffic to follow the loop-free alternates 505 indicated by the IGP. To do so, it is necessary for LDP to have the 506 appropriate labels available for the alternate so that the 507 appropriate out-segments can be installed in the forwarding plane 508 before the failure occurs. 510 This means that a Label Switched Router (LSR) running LDP must 511 distribute its labels for the FECs it can provide to all its 512 neighbors, regardless of whether or not they are upstream. 513 Additionally, LDP must be acting in liberal label retention mode so 514 that the labels which correspond to interfaces that aren't currently 515 the primary next-hop are stored. Similarly, LDP should be in 516 downstream unsolicited mode, so that the labels for the FEC are 517 distributed other than along the SPT. 519 If these requirements are met, then LDP can use the loop-free 520 alternates without requiring any targeted sessions or signaling 521 extensions for this purpose. 523 6. Routing Aspects 525 An SPF-like computation is run for each topology, which corresponds 526 to a particular OSPF area or ISIS level. The IGP needs to determine 527 the inheritance of loop-free alternates, as determined for singly 528 advertised routes, to multiply advertised routes, for protocols such 529 as BGP and LDP and for inter-area or inter-level routes. These 530 alternates are provided to LDP and BGP for forwarding purposes only; 531 the alternates are not redistributed in any fashion into other 532 protocols. 534 The alternate next-hop inheritance is described in the context of 535 inter-area routes, but applies equally well to BGP routes and to 536 routes which are advertised by multiple routers in the IGP area. 538 6.1 Multiple-Region Routing 540 Routes in different regions inherit their primary next-hops from the 541 border routers (area border routers (ABRs) or level boundary routers) 542 which offer the shortest path to the destination(s) announcing the 543 route. Similarly, routes must inherit their alternate next-hop and 544 will do so from the same border routers. The shortest path to an 545 inter-region route may be learned from a single border router. In 546 that case, both the primary and the alternate next-hops can be 547 inherited from that border router. Figure 4 illustrates this case 548 where D is reached via ABR1; the primary next-hop for ABR1 is P and 549 the loop-free node-protecting alternate is A1. 551 The shortest path to an inter-region route may be learned from 552 multiple border routers with at least 2 different primary neighbors, 553 as is illustrated in Figure 5. D is reached via ABR1 and ABR2 with 554 equal cost from S. The primary neighbor to reach ABR1 is P1 and the 555 alternate is A1. The primary neighbor to reach ABR2 is P2 and the 556 alternate is A2. In this case, there are equal-cost primary next- 557 hops to reach D and they can protect each other. In this example, 558 the primary next-hops would be to P1 and P2; if the link to P2 559 failed, then P1 could be used as an alternate and vice-versa. Thus 560 the alternates can be obtained from the primary next-hops. 562 ............. 563 ...... ...... 564 ... ... 565 .. .. 566 .. 10 +-----+ 5 +-----+ 5 .. 567 . +------| A1 +---------| R1 |-----+ . 568 .. | +-----+ +-----+ | . 569 . | +-----+ 10 570 . | +--------------| ABR1|---------+ 571 . | | 5 +-----+ | 572 . +-----+ 5 +---+-+ . | 573 . | S |-----------| P |------------+ . +-----+ 574 . +-----+ +-----+ 10 | . | D | 575 . | | . +-----+ 576 . | | . | 577 .. | +-----+ +-----+ 20 | 578 . +-----| A2 |------------------| ABR2|------------+ 579 . 10 +-----+ 5 +-----+ 580 ... ... 581 ... ... 582 ...... ...... 583 ............. 585 Figure 4: Inter-Region Destination via One Border Router 587 .......... 588 ...... ...... 589 ... ... 590 .. .. 591 .. 10 +-----+ 5 +-----+ .. 592 . +------| A1 +---------| R1 |-----+ 593 .. | +-----+ +-----+ |. 594 . | +-----+ +-----+ 10 595 . | +-----------| P1 |------------| ABR1|---------+ 596 . | | 5 +-----+ 5 +-----+ | 597 . +-----+ . | 598 . | S |---+ 5 +-----+ 10 . +-----+ 599 . +-----+ +-------| P2 |------------+ . | D | 600 . | +-----+ | . +-----+ 601 . | | . | 602 .. | +-----+ +-----+ 20 | 603 . +-----| A2 |------------------| ABR2|------------+ 604 . 10 +-----+ 5 +-----+ 605 ... ... 606 ... ... 607 ...... ...... 608 .......... 610 Figure 5: Inter-Region Destination via 611 Multiple Border Routers and Multiple Primary Neighbors 613 In the third case, the shortest path to an inter-region route 614 may be learned from multiple border routers but with a single 615 primary neighbor. This is shown in Figure 6, where D can be 616 equally reached from S via ABR1 and ABR2. The alternate next- 617 hop to reach ABR1 is A1 while the alternate to reach ABR2 is A2. 618 It is necessary to select one of the alternates to be inherited. 620 ............. 621 ...... ...... 622 ... ... 623 .. .. 624 .. 5 +-----+ 15 +-----+ 20 .. 625 . +------| A1 +---------| R1 |-----+ . 626 .. | +-----+ +-----+ | . 627 . | +-----+ 10 628 . | +--------------| ABR1|---------+ 629 . | | 15 +-----+ | 630 . +-----+ 5 +---+-+ . | 631 . | S |-----------| P |------------+ . +-----+ 632 . +-----+ +-----+ 5 | . | D | 633 . | | . +-----+ 634 . | | . | 635 .. | +-----+ +-----+ 20 | 636 . +-----| A2 |------------------| ABR2|------------+ 637 . 10 +-----+ 15 +-----+ 638 ... ... 639 ... ... 640 ...... ...... 641 ............. 643 Figure 6: Inter-Region Destination via 644 Multiple Border Routers but One Primary Neighbor 646 6.1.1 Inheriting Alternate Next-Hops with One Primary Neighbor 648 The main question when deciding whether an alternate can be inherited 649 is whether or not that alternate will continue to provide the 650 necessary protection. I.e., will the alternate continue to be usable 651 as an alternate and provide the same link or node protection with 652 respect to the destination that was provided with respect to the 653 border router. The relationships shown in Figure 6 will be used for 654 illustrative purposes, although the topology connecting them may be 655 more general than that shown. The proofs and explanations are 656 provided in Appendix A, but the answer is that the alternate will be 657 usable as an alternate and provide at least the same link or node 658 protection that was provided with respect to the border router. The 659 alternate next-hop inheritance procedure SHOULD select a loop-free 660 node-protecting alternate, if one is available. 662 6.1.2 OSPF Inter-Area Routes 664 In OSPF, each area's links are summarized into a summary LSA, which 665 is announced into an area by an Area Border Router. ABRs announce 666 summary LSAs into the backbone area and inject summary LSAs of the 667 backbone area into other non-backbone areas. A route can be learned 668 via summary LSA from one or more ABRs; such a route will be referred 669 to as a summary route. 671 The alternate next-hop inheritance for summary routes is as described 672 in Section 6.1.1 674 6.1.3 OSPF External Routing 676 Rules of inheritance of alternate next-hops for external routes is 677 the same as for inter-area destinations. The additional complication 678 comes from forwarding addresses, where an ASBR uses a forwarding 679 address to indicate to all routers in the Autonomous System to use 680 the specified address instead of going through the ASBR. When a 681 forwarding address has been indicated, all routers in the topology 682 calculate the shortest path to the link specified in the external 683 LSA. In this case, the alternate next-hop of the forwarding link 684 should be used, in conjunction with the primary next-hop of the 685 forwarding link, instead of those associated with the ASBR. 687 6.1.4 ISIS Multi-Level Routing 689 ISIS maintains separate databases for each level with which it is 690 dealing. Nodes in one level do not have any information about state 691 of nodes and edges of the other level. ISIS level boundary points , 692 also known as ISIS level boundary routers, are attached to both 693 levels. ISIS level boundary routers summarize the destinations in 694 each, level. ISIS inter-level route computation is very similar to 695 OSPF inter area routing. Rules for alternate next-hop inheritance is 696 the same as described in Section 6.1.1 698 6.2 OSPF Virtual Links 700 OSPF virtual links are used to connect two disjoint backbone areas 701 using a transit area. A virtual link is configured at the border 702 routers of the disjoint area. There are two scenarios, depending 703 upon the position of the root, router S. 705 If router S is itself an ABR or one of the endpoints of the disjoint 706 area, then router S must resolve its paths to the destination on the 707 other side of the disjoint area by using the summary links in the 708 transit area and using the closest ABR summarizing them into the 709 transit area. This means that the data path may diverge from the 710 virtual neighbor's control path. An ABR's primary and alternate 711 next-hops are calculated by RAPID on the transit area. 713 The primary next-hops to use are determined based upon the closest 714 set of equidistant ABRs; the same rules described in Section 6.1.1 715 for inter-area destinations must be followed for OSPF virtual links 716 to determine the alternate next-hop. The same ECMP cases apply. 718 If router S is not an ABR, then all the destinations on the other 719 side of the disjoint area will inherit the virtual link's endpoint, 720 the transit ABR. The same OSPF inter-area rules described in Section 721 6.1.1 must be followed here as well. 723 A virtual link cannot be used as an alternate next-hop. 725 6.3 BGP Next-Hop Synchronization 727 Typically BGP prefixes are advertised with AS exit routers router-id, 728 and AS exit routers are reached by means of IGP routes. BGP resolves 729 its advertised next-hop to the immediate next-hop by potential 730 recursive lookups in the routing database. IP/LDP Local Protection 731 computes the alternate next-hops to the all the IGP destinations, 732 which includes alternate next-hops to the AS exit router's router-id. 733 BGP simply inherits the alternate next-hop from IGP. The BGP 734 decision process is unaltered; BGP continue to use the IGP optimal 735 distance to find the nearest exit router. MBGP routes do not need to 736 copy the alternate next hops. 738 6.4 Multicast Considerations 740 IP/LDP Local Protection does not apply to multicast traffic. The 741 alternate next-hops SHOULD not used for multi-cast RPF checks. 743 7. Security Considerations 745 This document does not introduce any new security issues. The 746 mechanisms described in this document depend upon the network 747 topology distributed via an IGP, such as OSPF or ISIS. It is 748 dependent upon the security associated with those protocols. 750 8. Full Copyright Statement 752 Copyright (C) The Internet Society (2004). All Rights Reserved. 754 This document and translations of it may be copied and furnished to 755 others, and derivative works that comment on or otherwise explain it 756 or assist in its implementation may be prepared, copied, published 757 and distributed, in whole or in part, without restriction of any 758 kind, provided that the above copyright notice and this paragraph are 759 included on all such copies and derivative works. However, this 760 document itself may not be modified in any way, such as by removing 761 the copyright notice or references to the Internet Society or other 762 Internet organizations, except as needed for the purpose of 763 developing Internet standards in which case the procedures for 764 copyrights defined in the Internet Standards process must be 765 followed, or as required to translate it into languages other than 766 English. 768 The limited permissions granted above are perpetual and will not be 769 revoked by the Internet Society or its successors or assigns. 771 This document and the information contained herein is provided on an 772 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 773 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 774 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 775 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 776 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 778 9. References 780 [FRAMEWORK] M. Shand, "IP Fast Reroute Framework", draft-ietf-rtgwg- 781 ipfrr-framework-01.txt, June 2004 783 [LDP] L. Anderson, P. Doolan, N. Feldman, A. Fredette, B. Thomas, 784 "LDP Specification", RFC 3036, January 2001 786 [RSVP-TE] D. Awduche, L. Berger, D. Gan, T. Li, V Srinivasan, G. 787 Swallow, "RSVP-TE: Extensions to RSVP for LSP Tunnels", RFC 3209, 788 December 2001 790 [RSVP-TE FRR] P. Pan, D. Gan, G. Swallow, JP Vasseur, D. Cooper, A. 791 Atlas, and M. Jork, "Fast Reroute Extensions to RSVP-TE for LSP 792 Tunnels", work-in-progress draft-ietf-mpls-rsvp-lsp-fastreroute- 793 06.txt, June 2004 795 [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and 796 McPherson, D., "OSPF Stub Router Advertisement", RFC 3137, June 2001 798 [RFC3277] D. McPherson, "Intermediate System to Intermediate System 799 (IS-IS) Transient Blackhole Avoidance", RFC 3277, April 2002 801 [ISIS] R. Callon, "Use of OSI IS-IS for Routing in TCP/IP and Dual 802 Environments", RFC 1195, December 1990 804 [RFC2966] T. Li, T. Przygienda, H. Smit, "Domain-wide Prefix 805 Distribution with Two-Level IS-IS", RFC 2966, October 2000 807 [OSPF] J. Moy, "OSPF Version 2", RFC 2328, April 1998 809 [RFC2370] R. Coltun, "The OSPF Opaque LSA Option", RFC 2370, July 810 1998 812 10. Authors Information 814 Raveendra Torvi 815 Avici Systems 816 101 Billerica Avenue 817 N. Billerica, MA 01862 818 USA 819 email: rtorvi@avici.com 820 phone: +1 978 964 2026 822 Gagan Choudhury 823 AT&T 824 Room D5-3C21 825 200 Laurel Avenue 826 Middletown, NJ 07748 827 USA 828 email: gchoudhury@att.com 829 phone: +1 732 420-3721 831 Christian Martin 832 Verizon 833 1880 Campus Commons Drive 834 Reston, VA 20191 835 email: cmartin@verizon.com 837 Brent Imhoff 838 WilTel Communications 839 3180 Rider Trail South 840 Bridgeton, MO 63045 841 USA 842 email: brent.imhoff@wcg.com 843 phone: +1 314 595 6853 845 Don Fedyk 846 Nortel Networks 847 600 Technology Park 848 Billerica, MA 01821 849 email: dwfedyk@nortelnetworks.com 850 phone: +1 978 288 3041 852 11. Editor's Information 854 Alia Atlas 855 Avici Systems 856 101 Billerica Avenue 857 N. Billerica, MA 01862 858 USA 859 email: aatlas@avici.com 860 phone: +1 978 964 2070 862 Appendix A: Loop-Free Alternate Proofs 864 Consider where A2 is a loop-free alternate with respect to S and ABR2. Will A2 865 be a loop-free alternate with respect to S and D? Let there be three ABRs which 866 must be considered. Each ABR can represent a group of ABRs with the same 867 characteristics. 869 ............. 870 ...... ...... 871 ... ... 872 .. .. 873 .. 5 +-----+ 15 +-----+ 20 .. 874 . +------| A1 +---------| R1 |-----+ . 875 .. | +-----+ +-----+ | . 876 . | +-----+ 10 877 . | +--------------| ABR1|---------+ 878 . | | 15 +-----+ | 879 . +-----+ 5 +---+-+ . | 880 . | S |-----------| P |------------+ . +-----+ 881 . +-----+ +-----+ 5 | . | D | 882 . | | . +-----+ 883 . | | . | | 884 .. | +-----+ +-----+ 20 | | 885 . +-----| A2 |------------------| ABR2|------------+ | 886 . 10 +-----+ 15 +-----+ | 887 ... | ... | 888 ... +---------------+ ... | 889 ...... 10 +--+--+. 20 | 890 ...........| ABRt|-----------------------+ 891 +-----+ 893 Figure 7: Inter-Region Destination via 894 Multiple Border Routers but One Primary Neighbor 896 ABR1 is from the set of ABRs where D_opt(A2, ABR1) = D_opt(A2, 897 S) + D_opt(S, ABR1). In other words, A2 is not loop-free with 898 regards to S and ABR1. Additionally, D_opt(S, D) = D_opt(S, 899 ABR1) + D_opt(ABR1, D) so ABR1 is on a shortest path from S to 900 D. 902 ABR2 is from the set of ABRs where D_opt(A2, ABR2) < D_opt(A2, 903 S) + D_opt(S, ABR2). In other words, A2 is loop-free with 904 regards to S and ABR2. Additionally, D_opt(S, D) = D_opt(S, 905 ABR2) + D_opt(ABR2, D) so ABR2 is on a shortest path from S to 906 D. 908 ABRt is from a set of ABRs where D_opt(S, D) < D_opt(S, ABRt) + 909 D_opt(ABRt, D). In other words, ABRt is not on a shortest path 910 from S to D. 912 First, we will prove that D_opt(A2, D) < D_opt(A2, ABR1) + 913 D_opt(ABR1, D). In other words, the shortest path from A2 to D 914 does not go through ABR1. 916 The shortest path from A2 to D via ABR1 also goes via S. A 917 shortest path from S to D goes via ABR1. 918 Step i: D_opt(A2, ABR1) + D_opt(ABR1, D) = 919 D_opt(A2, S) + D_opt(S, ABR1) + D_opt(ABR1, D) 921 The shortest path from A2 to D via ABR2 does not go through S. 922 ABR2 is on a shortest path from S to D. 923 Step ii: D_opt(A2, ABR2) + D_opt(ABR2, D) < 924 D_opt(A2, S) + D_opt(S, ABR2) + D_opt(ABR2, D) 926 From previous and given that ABR1 and ABR2 provide equal-cost 927 paths from S to D: 928 Step iii: D_opt(A2, ABR2) + D_opt(ABR2, D) < 929 D_opt(A2, S) + D_opt(S, ABR1) + D_opt(ABR1, D) 931 From previous and Step i: 932 Step iv: D_opt(A2, ABR2) + D_opt(ABR2, D) < 933 D_opt(A2, ABR1) + D_opt(ABR1, D) 935 Step v: D_opt(A2, D) <= D_opt(A2, ABR2) + D_opt(ABR2, D) < 936 D_opt(A2, ABR1) + D_opt(ABR1, D) 937 Thus, the optimal path from A2 to D cannot go through ABR1. 939 Next, we will prove that if D_opt(A2, D) = D_opt(A2, ABRt) + 940 D_opt(ABRt, D), then A2 is still loop-free with respect to S and D. 941 In other words, even if A2's shortest path to D goes through an ABRt 942 which isn't on a shortest path from S to D, the path from A2 to D is 943 still loop-free with respect to S and D. This is proved via 944 contradiction. 946 Assume that D_opt(A2, D) goes through ABRt. 948 Step i: D_opt(A2, ABRt) + D_opt(ABRt, D) <= 949 D_opt(A2, ABR2) + D_opt(ABR2, D) 951 Because A2 is loop-free with respect to S and ABR2 952 Step ii: D_opt(A2, ABR2) + D_opt(ABR2, D) < 953 D_opt(A2, S) + D_opt(S, ABR2) + D_opt(ABR2, D) 955 Because ABR2 is on a shortest path from S to D and ABRt is not 956 Step iii: D_opt(S, ABR2) + D_opt(ABR2,D) < 957 D_opt(S, ABRt) + D_opt(ABRt, D) 959 From previous by adding Dopt(A2, S) to both sides 960 Step iv: D_opt(A2, S) + D_opt(S, ABR2) + D_opt(ABR2,D) < 961 D_opt(A2, S) + D_opt(S, ABRt) + D_opt(ABRt, D) 963 From Steps i and ii: 964 Step v: D_opt(A2, ABRt) + D_opt(ABRt, D) < 965 D_opt(A2, S) + D_opt(S, ABR2) + D_opt(ABR2, D) 967 From Steps iv and v: 968 Step vi: D_opt(A2, ABRt) + D_opt(ABRt, D) < 969 D_opt(A2, S) + D_opt(S, ABRt) + D_opt(ABRt, D) 971 Therefore, if D_opt(A2, D) is via ABRt, it does not go through 972 S. 974 These two proofs show that if A2 is loop-free with respect to S and 975 ABR2, then A2 is loop-free with respect to S and D. 977 Appendix A.1 Loop-Free Node-Protecting Alternate Proofs 979 It must also be shown that if A2 is loop-free and node-protecting 980 with respect to S and ABR2, then A2 will still be node-protecting 981 with respect to S and D. In other words, that A2 will be loop-free 982 with respect to P and D. 984 This is shown where D_opt(S, D) = D_opt(S, P) + D_opt(P, D), so that 985 D_opt(P, ABR1) + D_opt(ABR1, D) = D_opt(P, ABR2) + D_opt(ABR2, D). 987 First, it has already been proven that an ABR offering equal-cost 988 from S to D which is also loop-free with respect to S and D will be 989 selected by A2 over an ABR offering equal-cost from S to D which is 990 not loop-free with respect to S and D. Since the alternate 991 inheritance is of interest only where all the ABRs offering equal- 992 cost paths to D have the same primary next-hop P, if A2 is loop-free 993 and node-protecting for one ABR offering equal-cost paths to D, then 994 A2 is node-protecting for all those ABRs. 996 Next, given that A2's optimal path to ABR2 does not go through P, is 997 to prove that if A2's optimal path to D goes via some ABRt, that that 998 path does not go through P. This can be shown using variable 999 replacement of the second proof given as follows: 1001 Assume that D_opt(A2, D) goes through ABRt. 1002 Step i: D_opt(A2, ABRt) + D_opt(ABRt, D) <= 1003 D_opt(A2, ABR2) + D_opt(ABR2, D) 1005 Step ii: D_opt(A2, ABR2) + D_opt(ABR2, D) < 1006 D_opt(A2, P) + D_opt(P, ABR2) + D_opt(ABR2, D) 1008 Step iii: D_opt(P, ABR2) + D_opt(ABR2,D) < 1009 D_opt(P, ABRt) + D_opt(ABRt, D) 1011 From previous by adding Dopt(A2, P) to both sides 1012 Step iv: D_opt(A2, P) + D_opt(P, ABR2) + D_opt(ABR2,D) < 1013 D_opt(A2, P) + D_opt(P, ABRt) + D_opt(ABRt, D) 1015 From Steps i and ii: 1016 Step v: D_opt(A2, ABRt) + D_opt(ABRt, D) < 1017 D_opt(A2, P) + D_opt(P, ABR2) + D_opt(ABR2, D) 1019 From Steps iv and v: 1020 Step vi: D_opt(A2, ABRt) + D_opt(ABRt, D) < 1021 D_opt(A2, P) + D_opt(S, ABRt) + D_opt(ABRt, D) 1023 Therefore, if Dopt(A2, D) is via ABRt, it does not go through P. 1025 This proves that if A2 provides a loop-free node-protecting alternate 1026 for S to reach ABR2, then A2 will also provide a loop-free node- 1027 protecting alternate for S to reach D.