idnits 2.17.1 draft-ietf-rtgwg-ipfrr-notvia-addresses-09.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 521 has weird spacing: '... a Ps a ...' -- 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 (June 9, 2012) is 4338 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-12) exists of draft-ietf-rtgwg-ordered-fib-05 -- Obsolete informational reference (is this intentional?): RFC 5101 (Obsoleted by RFC 7011) Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group S. Bryant 3 Internet-Draft S. Previdi 4 Intended status: Informational Cisco Systems 5 Expires: December 11, 2012 M. Shand 6 Individual Contributor 7 June 9, 2012 9 IP Fast Reroute Using Not-via Addresses 10 draft-ietf-rtgwg-ipfrr-notvia-addresses-09 12 Abstract 14 This draft describes a mechanism that provides fast reroute in an IP 15 network through encapsulation to "not-via" addresses. A single level 16 of encapsulation is used. The mechanism protects unicast, multicast 17 and LDP traffic against link, router and shared risk group failure, 18 regardless of network topology and metrics. 20 Requirements Language 22 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 23 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 24 document are to be interpreted as described in RFC2119 [RFC2119]. 26 Status of this Memo 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF). Note that other groups may also distribute 33 working documents as Internet-Drafts. The list of current Internet- 34 Drafts is at http://datatracker.ietf.org/drafts/current/. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 This Internet-Draft will expire on December 11, 2012. 43 Copyright Notice 45 Copyright (c) 2012 IETF Trust and the persons identified as the 46 document authors. All rights reserved. 48 This document is subject to BCP 78 and the IETF Trust's Legal 49 Provisions Relating to IETF Documents 50 (http://trustee.ietf.org/license-info) in effect on the date of 51 publication of this document. Please review these documents 52 carefully, as they describe your rights and restrictions with respect 53 to this document. Code Components extracted from this document must 54 include Simplified BSD License text as described in Section 4.e of 55 the Trust Legal Provisions and are provided without warranty as 56 described in the Simplified BSD License. 58 Table of Contents 60 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 61 2. Overview of Not-via Repairs . . . . . . . . . . . . . . . . . 4 62 2.1. Use of Equal Cost Multi-Path . . . . . . . . . . . . . . . 5 63 2.2. Use of LFA repairs . . . . . . . . . . . . . . . . . . . . 5 64 3. Not-via Repair Path Computation . . . . . . . . . . . . . . . 6 65 3.1. Computing not-via repairs in distance and path vector 66 routing protocols . . . . . . . . . . . . . . . . . . . . 7 67 4. Operation of Repairs . . . . . . . . . . . . . . . . . . . . . 7 68 4.1. Node Failure . . . . . . . . . . . . . . . . . . . . . . . 8 69 4.2. Link Failure . . . . . . . . . . . . . . . . . . . . . . . 8 70 4.2.1. Loop Prevention Under Node Failure . . . . . . . . . . 8 71 4.3. Multi-homed Prefixes . . . . . . . . . . . . . . . . . . . 9 72 4.4. Installation of Repair Paths . . . . . . . . . . . . . . . 10 73 5. Compound Failures . . . . . . . . . . . . . . . . . . . . . . 11 74 5.1. Shared Risk Link Groups . . . . . . . . . . . . . . . . . 11 75 5.2. Local Area Networks . . . . . . . . . . . . . . . . . . . 16 76 5.2.1. Simple LAN Repair . . . . . . . . . . . . . . . . . . 17 77 5.2.2. LAN Component Repair . . . . . . . . . . . . . . . . . 17 78 5.2.3. LAN Repair Using Diagnostics . . . . . . . . . . . . . 18 79 5.3. Multiple Independent Failures . . . . . . . . . . . . . . 18 80 5.3.1. Looping Repairs . . . . . . . . . . . . . . . . . . . 19 81 5.3.2. Outline Solution . . . . . . . . . . . . . . . . . . . 20 82 5.3.3. Looping Repairs . . . . . . . . . . . . . . . . . . . 21 83 5.3.3.1. Dropping Looping Packets . . . . . . . . . . . . . 21 84 5.3.3.2. Computing non-looping Repairs of Repairs . . . . . 22 85 5.3.4. Mixing LFAs and Not-via . . . . . . . . . . . . . . . 24 86 6. Optimizing not-via computations using LFAs . . . . . . . . . . 25 87 7. Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . 26 88 8. Fast Reroute in an MPLS LDP Network. . . . . . . . . . . . . . 26 89 9. Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . 26 90 10. Routing Extensions . . . . . . . . . . . . . . . . . . . . . . 27 91 11. Incremental Deployment . . . . . . . . . . . . . . . . . . . . 27 92 12. Manageability Considerations . . . . . . . . . . . . . . . . . 27 93 12.1. Pre-failure configuration . . . . . . . . . . . . . . . . 28 94 12.2. Pre-failure Monitoring and operational support . . . . . . 28 95 12.3. Failure action monitoring . . . . . . . . . . . . . . . . 29 96 13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 29 97 14. Security Considerations . . . . . . . . . . . . . . . . . . . 29 98 15. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 30 99 16. References . . . . . . . . . . . . . . . . . . . . . . . . . . 30 100 16.1. Normative References . . . . . . . . . . . . . . . . . . . 30 101 16.2. Informative References . . . . . . . . . . . . . . . . . . 30 102 Appendix A. Q-Space . . . . . . . . . . . . . . . . . . . . . . . 31 103 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 31 105 1. Introduction 107 When a link or a router fails, only the neighbors of the failure are 108 initially aware that the failure has occurred. In a network 109 operating IP fast reroute [RFC5714], the routers that are the 110 neighbors of the failure repair the failure. These repairing routers 111 have to steer packets to their destinations despite the fact that 112 most other routers in the network are unaware of the nature and 113 location of the failure. 115 A common limitation in most IPFRR mechanisms is an inability to 116 indicate the identity of the failure and to explicitly steer the 117 repaired packet round the failure. The extent to which this 118 limitation affects the repair coverage is topology dependent. The 119 mechanism proposed here is to encapsulate the packet to an address 120 that explicitly identifies the network component that the repair must 121 avoid. This produces a repair mechanism, which, provided the network 122 is not partitioned by the failure, will always achieve a repair. 124 2. Overview of Not-via Repairs 126 This section provides a brief overview of the not-via method of 127 IPFRR. Consider the network fragment shown in Figure 1 below, in 128 which S has a packet for some destination D that it would normally 129 send via P and B, and that S suspects that P has failed. 131 A 132 | Bp is the address to use to get 133 | a packet to B not-via P 134 | 135 S----------P----------B. . . . . . . . . .D 136 \ | Bp^ 137 \ | | 138 \ | | 139 \ C | 140 \ | 141 X-------Y-------Z 142 Repair to Bp 144 Figure 1: Not-via repair of router failure 146 In the not-via IPFRR method, S encapsulates the packet to Bp, where 147 Bp is an address on node B that has the property that it is not 148 reachable from node P, i.e. the notation Bp means "an address of node 149 B that is only reachable not via node P. We later show how to install 150 the path from S to Bp such that it is the shortest path from S to B 151 not going via P. If the network contains a path from S to B that does 152 not transit router P, i.e. the network is not partitioned by the 153 failure of P and the path from S to Bp has been installed, then the 154 packet will be successfully delivered to B. In the example we are 155 considering this is the path S-X-Y-Z-B. When the packet addressed to 156 Bp arrives at B, B removes the encapsulation and forwards the 157 repaired packet towards its final destination. 159 Note that if the path from B to the final destination includes one or 160 more nodes that are included in the repair path, a packet MAY back 161 track after the encapsulation is removed. However, because the 162 decapsulating router is always closer to the packet destination than 163 the encapsulating router, the packet will not loop. 165 For complete protection, all of P's neighbors will require a not-via 166 address that allows traffic to be directed to them without traversing 167 P. This is shown in Figure 2. Similarly, P will require a set of 168 not-via address (one for each neighbor) allowing traffic to be 169 directed to P without traversing each of those neighbors. 171 The not-via addresses are advertised in the routing protocol in a way 172 that clearly identifies them as not-via addresses and not 'ordinary' 173 addresses. 175 A 176 |Ap 177 | 178 Sp Pa|Pb 179 S----------P----------B 180 Ps|Pc Bp 181 | 182 Cp| 183 C 185 Figure 2: The set of Not-via P Addresses 187 2.1. Use of Equal Cost Multi-Path 189 A router can use an equal cost multi-path (ECMP) repair in place of a 190 not-via repair. 192 A router computing a not-via repair path MAY subject the repair to 193 ECMP. 195 2.2. Use of LFA repairs 197 The not-via approach provides complete repair coverage and therefore 198 MAY be used as the sole repair mechanism. There are, however, 199 advantages in using not-via in combination with loop free alternates 200 (LFA) and or downstream paths as documented in [RFC5286]. In 201 particular LFAs do not require the assignment and management of 202 additional IP addresses to nodes, they do not require nodes in the 203 network to be upgraded in order to calculate not-via repair paths, 204 and they do not require the use of encapsulation. 206 LFAs are computed on a per destination basis and in general, only a 207 subset of the destinations requiring repair will have a suitable LFA 208 repair. In this case, those destinations which are repairable by 209 LFAs are so repaired and the remainder of the destinations are 210 repaired using the not-via encapsulation. On the other hand, the 211 path taken by an LFA repair may be less optimal than that of the 212 equivalent not-via repair for traffic destined to nodes close to the 213 far end of the failure, but may be more optimal for some other 214 traffic. The description in this document assumes that LFAs will be 215 used where available, but the distribution of repairs between the two 216 mechanisms is a local implementation choice. 218 3. Not-via Repair Path Computation 220 The not-via repair mechanism requires that all routers on the path 221 from S to B (Figure 1) have a route to Bp. They can calculate this 222 by failing node P, running a Shortest Path First Algorithm (SPF), and 223 finding the shortest route to B. 225 A router has no simple way of knowing whether it is on the shortest 226 path for any particular repair. It is therefore necessary for every 227 router to calculate the path it would use in the event of any 228 possible router failure. Each router therefore "fails" every router 229 in the network, one at a time, and calculates its own best route to 230 each of the neighbors of that router. In other words, with reference 231 to Figure 1, routers A, B, C, X, Y, Z and P will consider each router 232 in turn, assume that router has failed, and then calculate its own 233 route to each of the not-via addresses advertised by the neighbors of 234 that router. In other words in the case of a presumed failure of P, 235 ALL routers (in this case S, A, B, C, X, Y and Z) calculate their 236 routes to Sp, Ap, Bp, and Cp, in each case, not via P. 238 To calculate the repair paths a router has to calculate n-1 SPFs 239 where n is the number of routers in the network. This is expensive 240 to compute. However, the problem is amenable to a solution in which 241 each router (X) proceeds as follows. X first calculates the base 242 topology with all routers functional and determines its normal path 243 to all not-via addresses. This can be performed as part of the 244 normal SPF computation. For each router P in the topology, X then 245 performs the following actions:- 246 1. Removes router P from the topology. 248 2. Performs an incremental SPF (iSPF) [ISPF] on the modified 249 topology. The iSPF process involves detaching the sub-tree 250 affected by the removal of router P, and then re-attaching the 251 detached nodes. However, it is not necessary to run the iSPF to 252 completion. It is sufficient to run the iSPF up to the point 253 where all of the nodes advertising not-via P addresses have been 254 re-attached to the SPT, and then terminate it. 256 3. Reverts to the base topology. 258 This algorithm is significantly less expensive than a set of full 259 SPFs. Thus, although a router has to calculate the repair paths for 260 n-1 failures, the computational effort is much less than n-1 SPFs. 262 Experiments on a selection of real world network topologies with 263 between 40 and 400 nodes suggest that the worst-case computational 264 complexity using the above optimizations is equivalent to performing 265 between 5 and 13 full SPFs. Further optimizations are described in 266 section 6. 268 3.1. Computing not-via repairs in distance and path vector routing 269 protocols 271 While this document focuses on link state routing protocols, it is 272 equally possible to compute not-via repairs in distance vector (e.g. 273 RIP) or path vector (e.g. BGP) routing protocols. This can be 274 achieved with very little protocol modification by advertising the 275 not-via address in the normal way, but ensuring that the information 276 about a not-via address Ps is not propagated through the node S. In 277 the case of link protection this simply means that the advertisement 278 from P to S is suppressed, with the result that S and all other nodes 279 compute a route to Ps which doesn't traverse S, as required. 281 In the case of node protection, where P is the protected node, and N 282 is some neighbor, the advertisement of Np MUST be suppressed not only 283 across the link N->P, but also across any link to P. The simplest way 284 of achieving this is for P itself to perform the suppression of any 285 address of the form Xp. 287 4. Operation of Repairs 289 This section explains the basic operation of the not-via repair of 290 node and link failure. 292 4.1. Node Failure 294 When router P fails (Figure 2) S encapsulates any packet that it 295 would send to B via P to Bp, and then sends the encapsulated packet 296 on the shortest path to Bp. S follows the same procedure for routers 297 A and C in Figure 2. The packet is decapsulated at the repair target 298 (A, B or C) and then forwarded normally to its destination. The 299 repair target can be determined as part of the normal SPF by 300 recording the "next-next-hop" for each destination in addition to the 301 normal next-hop. The next-next hop is the router that the next hop 302 router regards as its own next hop to the destination. In Figure 1, 303 B is S's next next hop to D. 305 Notice that with this technique only one level of encapsulation is 306 needed, and that it is possible to repair ANY failure regardless of 307 link metrics and any asymmetry that may be present in the network. 308 The only exception to this is where the failure was a single point of 309 failure that partitioned the network, in which case ANY repair is 310 clearly impossible. 312 4.2. Link Failure 314 The normal mode of operation of the network would be to assume router 315 failure. However, where some destinations are only reachable through 316 the failed router, it is desirable that an attempt be made to repair 317 to those destinations by assuming that only a link failure has 318 occurred. 320 To perform a link repair, S encapsulates to Ps (i.e. it instructs the 321 network to deliver the packet to P not-via S). All of the neighbors 322 of S will have calculated a path to Ps in case S itself had failed. 323 S could therefore give the packet to any of its neighbors (except, of 324 course, P). However, S SHOULD send the encapsulated packet on the 325 shortest available path to P. This path is calculated by running an 326 SPF with the link SP failed. Note that this may again be an 327 incremental calculation, which can terminate when address Ps has been 328 reattached. 330 4.2.1. Loop Prevention Under Node Failure 332 It is necessary to consider the behavior of IPFRR solutions when a 333 link repair is attempted in the presence of node failure. In its 334 simplest form, the not-via IPFRR solution prevents the formation of 335 loops as a result of mutual repair, by never providing a repair path 336 for a not-via address. The repair of packets with not-via addresses 337 is considered in more detail in Section 5.3. Referring to Figure 2, 338 if A was the neighbor of P that was on the link repair path from S to 339 P, and P itself had failed, the repaired packet from S would arrive 340 at A encapsulated to Ps. A would have detected that the AP link had 341 failed and would normally attempt to repair the packet. However, no 342 repair path is provided for any not-via address, and so A would be 343 forced to drop the packet, thus preventing the formation of a loop. 345 4.3. Multi-homed Prefixes 347 A multi-homed Prefix (MHP) is a prefix that is reachable via more 348 than one router in the network. Some of these may be repairable 349 using LFAs as described in [RFC5286]. Only those without such a 350 repair need be considered here. 352 When IPFRR router S (Figure 3) discovers that P has failed, it needs 353 to send packets addressed to the MHP X, which is normally reachable 354 through P, to an alternate router, which is still able to reach X. 356 X X X 357 | | | 358 | | | 359 | Sp |Pb | 360 Z...............S----------P----------B...............Y 361 Ps|Pc Bp 362 | 363 Cp| 364 C 366 Figure 3: Multi-homed Prefixes 368 S SHOULD choose the closest router that can reach X during the 369 failure as the alternate router. S determines which router to use as 370 the alternate while running the SPF with P failed. This is 371 accomplished by the normal process of re-attaching a leaf node to the 372 core topology (this is sometimes known as a "partial SPF"). 374 First, consider the case where the shortest alternate path to X is 375 via Z. S can reach Z without using the failed router P. However, S 376 cannot just send the packet towards Z, because the other routers in 377 the network will not be aware of the failure of P, and may loop the 378 packet back to S. S therefore encapsulates the packet to Z (using a 379 normal address for Z). When Z receives the encapsulated packet it 380 removes the encapsulation and forwards the packet to X. 382 Now consider the case where the shortest alternate path to X is via 383 Y, which S reaches via P and B. To reach Y, S must first repair the 384 packet to B using the normal not-via repair mechanism. To do this S 385 encapsulates the packet for X to Bp. When B receives the packet it 386 removes the encapsulation and discovers that the packet is intended 387 for MHP X. The situation now reverts to the previous case, in which 388 the shortest alternate path does not require traversal of the 389 failure. B therefore follows the algorithm above and encapsulates 390 the packet to Y (using a normal address for Y). Y removes the 391 encapsulation and forwards the packet to X. 393 It may be that the cost of reaching X using local delivery from the 394 alternate router (i.e. Z or Y) is greater than the cost of reaching 395 X via P. Under those circumstances, the alternate router would 396 normally forward to X via P, which would cause the IPFRR repair to 397 loop. To prevent the repair from looping the alternate router MUST 398 locally deliver a packet received via a repair encapsulation. This 399 may be specified by using a special address with the above semantics. 400 Note that only one such address is required per node. Notice that 401 using the not-via approach, only one level of encapsulation was 402 needed to repair MHPs to the alternate router. 404 4.4. Installation of Repair Paths 406 The following algorithm is used by node S (Figure 3) to pre- 407 calculate and install repair paths in the FIB, ready for immediate 408 use in the event of a failure. It is assumed that the not-via repair 409 paths have already been calculated as described above. 411 For each neighbor P, consider all destinations which are reachable 412 via P in the current topology:- 414 1. For all destinations with an ECMP or LFA repair (as described in 415 [RFC5286]) install that repair. 417 2. For each destination (DR) that remains, identify in the current 418 topology the next-next-hop (H) (i.e. the neighbor of P that P 419 will use to send the packet to DR). This can be determined 420 during the normal SPF run by recording the additional 421 information. If S has a path to the not-via address Hp (H not 422 via P), install a not-via repair to Hp for the destination DR. 424 3. Identify all remaining destinations (M) which can still be 425 reached when node P fails. These will be multi-homed prefixes 426 that are not repairable by LFA, for which the normal attachment 427 node is P, or a router for which P is a single point of failure, 428 and have an alternative attachment point that is reachable after 429 P has failed. One way of determining these destinations would be 430 to run an SPF rooted at S with node P removed, but an 431 implementation may record alternative attachment points during 432 the normal SPF run. In either case, the next best point of 433 attachment can also be determined for use in step (4) below. 435 4. For each multi-homed prefix (M) identified in step (3):- 437 A. Identify the new attachment node (as shown in Figure 3). 438 This may be:- 440 a. Y, where the next hop towards Y is P, or 442 b. Z, where the next hop towards Z is not P. 444 If the attachment node is Z, install the repair for M as a 445 tunnel to Z' (where Z' is the address of Z that is used to 446 force local forwarding). 448 B. For the subset of prefixes (M) that remain (having attachment 449 point Y), install the repair path previously installed for 450 destination Y. 452 For each destination (DS) that remains, install a not-via repair 453 to Ps (P not via S). Note, these are destinations for which node 454 P is a single point of failure, and can only be repaired by 455 assuming that the apparent failure of node P was simply a failure 456 of the S-P link. Note that, if available, a downstream path to P 457 MAY be used for such a repair. This cannot generate a persistent 458 loop in the event of the failure of node P, but if one neighbor 459 of P uses a not-via repair and another uses a downstream path, it 460 is possible for a packet sent on the downstream path to be 461 returned to the sending node inside a not-via encapsulation. 462 Since packets destined to not-via addresses are not repaired, the 463 packet will be dropped after executing a single turn loop. 465 5. Compound Failures 467 The following types of failures involve more than one component: 469 1. Shared Risk Link Groups 471 2. Local Area Networks 473 3. Multiple Independent Failures 475 The considerations that apply in each of the above situations are 476 described in the following sections. 478 5.1. Shared Risk Link Groups 480 A Shared Risk Link Group (SRLG) is a set of links whose failure can 481 be caused by a single action such as a conduit cut or line card 482 failure. When repairing the failure of a link that is a member of an 483 SRLG, it MUST be assumed that all the other links that are also 484 members of the SRLG have also failed. Consequently, any repair path 485 MUST be computed to avoid not just the adjacent link, but also all 486 the links which are members of the same SRLG. 488 In Figure 4 below, the links S-P and A-B are both members of SRLG 489 "a". The semantics of the not-via address Ps changes from simply "P 490 not-via the link S-P" to be "P not-via the link S-P or any other link 491 with which S-P shares an SRLG" In Figure 4 this is the links that are 492 members of SRLG "a". I.e. links S-P and A-B. Since the information 493 about SRLG membership of all links is available in the Link State 494 Database, all nodes computing routes to the not-via address Ps can 495 infer these semantics, and perform the computation by failing all the 496 links in the SRLG when running the iSPF. 498 Note that it is not necessary for S to consider repairs to any other 499 nodes attached to members of the SRLG (such as B). It is sufficient 500 for S to repair to the other end of the adjacent link (P in this 501 case). 503 a Ps 504 S----------P---------D 505 | | 506 | a | 507 A----------B 508 | | 509 | | 510 C----------E 512 Figure 4: Shared Risk Link Group 514 In some cases, it may be that the links comprising the SRLG occur in 515 series on the path from S to the destination D, as shown in Figure 5. 516 In this case, multiple consecutive repairs may be necessary. S will 517 first repair to Ps, then P will repair to Dp. In both cases, because 518 the links concerned are members of SRLG "a" the paths are computed to 519 avoid all members of SRLG "a". 521 a Ps a Dp 522 S----------P---------D 523 | | | 524 | a | | 525 A----------B | 526 | | | 527 | | | 528 C----------E---------F 530 Figure 5: Shared Risk Link Group members in series 532 While the use of multiple repairs in series introduces some 533 additional overhead, these semantics avoid the potential 534 combinatorial explosion of not-via addresses that could otherwise 535 occur. 537 Note that although multiple repairs are used, only a single level of 538 encapsulation is required. This is because the first repair packet 539 is decapsulated before the packet is re-encapsulated using the not- 540 via address corresponding to the far side of the next link which is a 541 member of the same SRLG. In some cases the decapsulation and re- 542 encapsulation takes place (at least notionally) at a single node, 543 while in other cases, these functions may be performed by different 544 nodes. This scenario is illustrated in Figure 6 below. 546 a Ps a Dg 547 S----------P---------G--------D 548 | | | | 549 | a | | | 550 A----------B | | 551 | | | | 552 | | | | 553 C----------E---------F--------H 555 Figure 6: Shared Risk Link Group members in series 557 In this case, S first encapsulates to Ps, and node P decapsulates the 558 packet and forwards it "native" to G using its normal FIB entry for 559 destination D. G then repairs the packet to Dg. 561 It can be shown that such multiple repairs can never form a loop 562 because each repair causes the packet to move closer to its 563 destination. 565 It is often the case that a single link may be a member of multiple 566 SRLGs, and those SRLGs may not be isomorphic. This is illustrated in 567 Figure 7 below. 569 ab Ps a Dg 570 S----------P---------G--------D 571 | | | | 572 | a | | | 573 A----------B | | 574 | | | | 575 | b | | b | 576 C----------E---------F--------H 577 | | 578 | | 579 J----------K 581 Figure 7: Multiple Shared Risk Link Groups 583 The link SP is a member of SRLGs "a" and "b". When a failure of the 584 link SP is detected, it MUST be assumed that BOTH SRLGs have failed. 585 Therefore the not-via path to Ps must be computed by failing all 586 links which are members of SRLG "a" or SRLG "b". I.e. the semantics 587 of Ps is now "P not-via any links which are members of any of the 588 SRLGs of which link SP is a member". This is illustrated in Figure 8 589 below. 591 ab Ps a Dg 592 S----/-----P---------G---/----D 593 | | | | 594 | a | | | 595 A----/-----B | | 596 | | | | 597 | b | | b | 598 C----/-----E---------F---/----H 599 | | 600 | | 601 J----------K 603 Figure 8: Topology used for repair computation for link S-P 605 In this case, the repair path to Ps will be S-A-C-J-K-E-B-P. It may 606 appear that there is no path to D because GD is a member of SRLG "a" 607 and FH is a member of SRLG "b". This is true if BOTH SRLGs "a" and 608 "b" have in fact failed, which would be an instance of multiple 609 independent failures. In practice, it is likely that there is only a 610 single failure, i.e. either SRLG "a" or SRLG "b" has failed, but not 611 both. These two possibilities are indistinguishable from the point 612 of view of the repairing router S and so it MUST repair on the 613 assumption that both are unavailable. However, each link repair is 614 considered independently. The repair to Ps delivers the packet to P 615 which then forwards the packet to G. When the packet arrives at G, if 616 SRLG "a" has failed it will be repaired around the path G-F-H-D. 618 This is illustrated in Figure 9 below. If, on the other hand, SRLG 619 "b" has failed, link GD will still be available. In this case the 620 packet will be delivered as normal across the link GD. 622 ab Ps a Dg 623 S----/-----P---------G---/----D 624 | | | | 625 | a | | | 626 A----/-----B | | 627 | | | | 628 | b | | b | 629 C----------E---------F--------H 630 | | 631 | | 632 J----------K 634 Figure 9: Topology used for repair computation for link G-D 636 If both SRLG a and SRLG b had failed, the packet would be repaired as 637 far as P by S, and would be forwarded by P to G. G would encapsulate 638 the packet to D using the not-via address Dg and forward it to F. F 639 would recognise that the its next hop to Dg (H) was unreachable due 640 to the failure of link FH (part of SRLG b) and would drop the packet, 641 because packets addressed to a not-via address are not repaired in 642 basic not-via IPFRR. 644 The repair of multiple independent failures is not provided by the 645 basic not-via IPFRR method described so far in this memo. 647 A repair strategy that assumes the worst-case failure for each link 648 can often result in longer repair paths than necessary. In cases 649 where only a single link fails, rather than the full SRLG, this 650 strategy may occasionally fail to identify a repair even though a 651 viable repair path exists in the network. The use of sub-optimal 652 repair paths is an inevitable consequence of this compromise 653 approach. The failure to identify any repair is a serious 654 deficiency, but is a rare occurrence in a robustly designed network. 655 This problem can be addressed by:- 657 1. Reporting that the link in question is irreparable, so that the 658 network designer can take appropriate action. 660 2. Modifying the design of the network to avoid this possibility. 662 3. Using some form of SRLG diagnostic (for example, by running BFD 663 over alternate repair paths) to determine which SRLG member(s) 664 has actually failed and using this information to select an 665 appropriate pre-computed repair path. However, aside from the 666 complexity of performing the diagnostics, this requires multiple 667 not-via addresses per interface, which has poor scaling 668 properties. 670 4. Using the mechanism described in Section 5.3 672 5.2. Local Area Networks 674 LANs are a special type of SRLG and are solved using the SRLG 675 mechanisms outlined above. With all SRLGs there is a trade-off 676 between the sophistication of the fault detection and the size of the 677 SRLG. Protecting against link failure of the LAN link(s) is 678 relatively straightforward, but as with all fast reroute mechanisms, 679 the problem becomes more complex when it is desired to protect 680 against the possibility of failure of the nodes attached to the LAN 681 as well as the LAN itself. 683 +--------------Q------C 684 | 685 | 686 | 687 A--------S-------(N)-------------P------B 688 | 689 | 690 | 691 +--------------R------D 693 Figure 10: Local Area Networks 695 Consider the LAN shown in Figure 10. For connectivity purposes, we 696 consider that the LAN is represented by the pseudonode (N). To 697 provide IPFRR protection, S MUST run a connectivity check to each of 698 its protected LAN adjacencies P, Q, and R, using, for example BFD 699 [RFC5880]. 701 When S discovers that it has lost connectivity to P, it is unsure 702 whether the failure is: 704 o its own interface to the LAN, 706 o the LAN itself, 708 o the LAN interface of P, 710 o the node P. 712 5.2.1. Simple LAN Repair 714 A simple approach to LAN repair is to consider the LAN and all of its 715 connected routers as a single SRLG. Thus, the address P not via the 716 LAN (Pl) would require P to be reached not-via any router connected 717 to the LAN. This is shown in Figure 11. 719 Ql Cl 720 +-------------Q--------C 721 | Qc 722 | 723 As Sl | Pl Bl 724 A--------S-------(N)------------P--------B 725 Sa | Pb 726 | 727 | Rl Dl 728 +-------------R--------D 729 Rd 731 Figure 11: Local Area Networks - LAN SRLG 733 In this case, when S detected that P had failed it would send traffic 734 reached via P and B to B not-via the LAN or any router attached to 735 the LAN (i.e. to Bl). Any destination only reachable through P would 736 be addressed to P not-via the LAN or any router attached to the LAN 737 (except of course P). 739 Whilst this approach is simple, it assumes that a large portion of 740 the network adjacent to the failure has also failed. This will 741 result in the use of sub-optimal repair paths and in some cases the 742 inability to identify a viable repair. 744 5.2.2. LAN Component Repair 746 In this approach, possible failures are considered at a finer 747 granularity, but without the use of diagnostics to identify the 748 specific component that has failed. Because S is unable to diagnose 749 the failure it MUST repair traffic sent through P and B, to B not- 750 via P,N (i.e. not via P and not via N), on the conservative 751 assumption that both the entire LAN and P have failed. Destinations 752 for which P is a single point of failure MUST as usual be sent to P 753 using an address that avoids the interface by which P is reached from 754 S, i.e. to P not-via N. Similarly for routers Q and R. 756 Notice that each router that is connected to a LAN MUST, as usual, 757 advertise one not-via address for each neighbor. In addition, each 758 router on the LAN MUST advertise an extra address not via the 759 pseudonode (N). 761 Notice also that each neighbor of a router connected to a LAN MUST 762 advertise two not-via addresses, the usual one not via the neighbor 763 and an additional one, not via either the neighbor or the pseudonode. 764 The required set of LAN address assignments is shown in Figure 12 765 below. Each router on the LAN, and each of its neighbors, is 766 advertising exactly one address more than it would otherwise have 767 advertised if this degree of connectivity had been achieved using 768 point-to-point links. 770 Qs Qp Qc Cqn 771 +--------------Q---------C 772 | Qr Qn Cq 773 | 774 Asn Sa Sp Sq | Ps Pq Pb Bpn 775 A--------S-------(N)-------------P---------B 776 As Sr Sn | Pr Pn Bp 777 | 778 | Rs Rp Pd Drn 779 +--------------R---------D 780 Rq Rn Dr 782 Figure 12: Local Area Networks 784 5.2.3. LAN Repair Using Diagnostics 786 A more specific LAN repair can be undertaken by using diagnostics. 787 In order to explicitly diagnose the failed network component, S 788 correlates the connectivity reports from P and one or more of the 789 other routers on the LAN, in this case, Q and R. If it lost 790 connectivity to P alone, it could deduce that the LAN was still 791 functioning and that the fault lay with either P, or the interface 792 connecting P to the LAN. It would then repair to B not via P (and P 793 not-via N for destinations for which P is a single point of failure) 794 in the usual way. If S lost connectivity to more than one router on 795 the LAN, it could conclude that the fault lay only with the LAN, and 796 could repair to P, Q and R not-via N, again in the usual way. 798 5.3. Multiple Independent Failures 800 IPFRR repair of multiple simultaneous failures which are not members 801 of a known SRLG is complicated by the problem that the use of 802 multiple concurrent repairs may result in looping repair paths. As 803 described in Section 4.2.1, the simplest method of preventing such 804 loops, is to ensure that packets addressed to a not-via address are 805 not repaired but instead are dropped. It is possible that a network 806 may experience multiple simultaneous failures. This may be due to 807 simple statistical effects, but the more likely cause is 808 unanticipated SRLGs. When multiple failures which are not part of an 809 anticipated group are detected, repairs are abandoned and the network 810 reverts to normal convergence. Although safe, this approach is 811 somewhat draconian, since there are many circumstances were multiple 812 repairs do not induce loops. 814 This section describes the properties of multiple unrelated failures 815 and proposes some methods that may be used to address this problem. 817 5.3.1. Looping Repairs 819 Let us assume that the repair mechanism is based on solely on not-via 820 repairs. LFA or downstream routes MAY be incorporated, and will be 821 dealt with later. 823 A------//------B------------D 824 / \ 825 / \ 826 F G 827 \ / 828 \ / 829 X------//------Y 831 Figure 13: The General Case of Multiple Failures 833 The essential case is as illustrated in Figure 13. Note that 834 depending on the repair case under consideration, there may be paths 835 present in Figure 13, that are in addition to those shown in the 836 figure. For example there may be paths between A and B, and/or 837 between X and Y. These paths are omitted for graphical clarity. 839 There are three cases to consider: 841 1) Consider the general case of a pair of protected links A-B and 842 X-Y as shown in the network fragment shown Figure 13. If the 843 repair path for A-B does not traverse X-Y and the repair path for 844 X-Y does not traverse A-B, this case is completely safe and will 845 not cause looping or packet loss. 847 A more common variation of this case is shown in Figure 14, which 848 shows two failures in different parts of the network in which a 849 packet from A to D traverses two concatenated repairs. 851 A------//------B------------X------//------Y------D 852 | | | | 853 | | | | 854 M--------------+ N--------------+ 856 Figure 14: Concatenated Repairs 858 2) In Figure 13, the repair for A-B traverses X-Y, but the repair 859 for X-Y does not traverse A-B. This case occurs when the not-via 860 path from A to B traverses link X-Y, but the not-via path from X 861 to Y traverses some path not shown in Figure 13. Without the 862 multi-failure mechanism described in this section the repaired 863 packet for A-B would be dropped when it reached X-Y, since the 864 repair of repaired packets would be forbidden. However, if this 865 packet were allowed to be repaired, the path to D would be 866 complete and no harm would be done, although two levels of 867 encapsulation would be required. 869 3) The repair for A-B traverses X-Y AND the repair for X-Y 870 traverses A-B. In this case unrestricted repair would result in 871 looping packets and increasing levels of encapsulation. 873 The challenge in applying IPFRR to a network that is undergoing 874 multiple failures is, therefore, to identify which of these cases 875 exist in the network and react accordingly. 877 5.3.2. Outline Solution 879 When A is computing the not-via repair path for A-B (i.e. the path 880 for packets addressed to Ba, read as "B not-via A") it is aware of 881 the list of nodes which this path traverses. This can be recorded by 882 a simple addition to the SPF process, and the not-via addresses 883 associated with each forward link can be determined. If the path 884 were A, F, X, Y, G, B, (Figure 13) the list of not-via addresses 885 would be: Fa, Xf, Yx, Gy, Bg. Under standard not-via operation, A 886 would populate its FIB such that all normal addresses normally 887 reachable via A-B would be encapsulated to Ba when A-B fails, but 888 traffic addressed to any not-via address arriving at A would be 889 dropped. The new procedure modifies this such that any traffic for a 890 not-via address normally reachable over A-B is also encapsulated to 891 Ba unless the not-via address is one of those previously identified 892 as being on the path to Ba, for example Yx, in which case the packet 893 is dropped. 895 The above procedure allows cases 1 and 2 above to be repaired, while 896 preventing the loop which would result from case 3. 898 Note that this is accomplished by pre-computing the required FIB 899 entries, and does not require any detailed packet inspection. The 900 same result could be achieved by checking for multiple levels of 901 encapsulation and dropping any attempt to triple encapsulate. 902 However, this would require more detailed inspection of the packet, 903 and causes difficulties when more than 2 "simultaneous" failures are 904 contemplated. 906 So far we have permitted benign repairs to coexist, albeit sometimes 907 requiring multiple encapsulation. Note that in many cases there will 908 be no performance impact since unless both failures are on the same 909 node, the two encapsulations or two decapsulations will be performed 910 at different nodes. There is however the issue of the MTU impact of 911 multiple encapsulations. 913 In the following sub-section we consider the various strategies that 914 may be applied to case 3 - mutual repairs that would loop. 916 5.3.3. Looping Repairs 918 In case 3, the simplest approach is to simply not install repairs for 919 repair paths that might loop. In this case, although the potentially 920 looping traffic is dropped, the traffic is not repaired. If we 921 assume that a hold-down is applied before reconvergence in case the 922 link failure was just a short glitch, and if a loop free convergence 923 mechanism further delays convergence, then the traffic will be 924 dropped for an extended period. In these circumstances it would be 925 better to "abandon all hope" (AAH) [I-D.ietf-rtgwg-ordered-fib] 926 (Appendix A) and immediately invoke normal re-convergence. 928 Note that it is not sufficient to expedite the issuance of an LSP 929 reporting the failure, since this may be treated as a permitted 930 simultaneous failure by the ordered FIB (oFIB) algorithm 931 [I-D.ietf-rtgwg-ordered-fib]. It is therefore necessary to 932 explicitly trigger an oFIB AAH. 934 5.3.3.1. Dropping Looping Packets 936 One approach to case 3 is to allow the repair, and to experimentally 937 discover the incompatibility of the repairs if and when they occur. 938 With this method we permit the repair in case 3 and trigger AAH when 939 a packet drop count on the not-via address has been incremented. 940 Alternatively, it is possible to wait until the LSP describing the 941 change is issued normally (i.e. when X announces the failure of X-Y). 942 When the repairing node A, which has precomputed that X-Y failures 943 are mutually incompatible with its own repairs receives this LSP it 944 can then issue the AAH. This has the disadvantage that it does not 945 overcome the hold-down delay, but it requires no "data-driven" 946 operation, and it still has the required effect of abandoning the 947 oFIB which is probably the longer of the delays (although with 948 signalled oFIB this should be sub-second). 950 Whilst both of the experimental approaches described above are 951 feasible, they tend to induce AAH in the presence of otherwise 952 feasible repairs, and they are contrary to the philosophy of repair 953 pre-determination that has been applied to existing IPFRR solutions. 955 5.3.3.2. Computing non-looping Repairs of Repairs 957 An alternative approach to simply dropping the looping packets, or to 958 detecting the loop after it has occurred, is to use secondary SRLGs. 959 With a link state routing protocol it is possible to precompute the 960 incompatibility of the repairs in advance and to compute an 961 alternative SRLG repair path. Although this does considerably 962 increase the computational complexity it may be possible to compute 963 repair paths that avoid the need to simply drop the offending 964 packets. 966 This approach requires us to identify the mutually incompatible 967 failures, and advertise them as "secondary SRLGs". When computing 968 the repair paths for the affected not-via addresses these links are 969 simultaneously failed. Note that the assumed simultaneous failure 970 and resulting repair path only applies to the repair path computed 971 for the conflicting not-via addresses, and is not used for normal 972 addresses. This implies that although there will be a longer repair 973 path when there is more than one failure, if there is a single 974 failure the repair path length will be "normal". 976 Ideally we would wish to only invoke secondary SRLG computation when 977 we are sure that the repair paths are mutually incompatible. 978 Consider the case of node A in Figure 13. A first identifies that 979 the repair path for A-B is via F-X-Y-G-B. It then explores this path 980 determining the repair path for each link in the path. Thus, for 981 example, it performs a check at X by running an SPF rooted at X with 982 the X-Y link removed to determine whether A-B is indeed on X's repair 983 path for packets addressed to Yx. 985 Some optimizations are possible in this calculation, which appears at 986 first sight to be order hk (where h is the average hop length of 987 repair paths and k is the average number of neighbours of a router). 988 When A is computing its set of repair paths, it does so for all its k 989 neighbours. In each case it identifies a list of node pairs 990 traversed by each repair. These lists may often have one or more 991 node pairs in common, so the actual number of link failures which 992 require investigation is the union of these sets. It is then 993 necessary to run an SPF rooted at the first node of each pair (the 994 first node because the pairings are ordered representing the 995 direction of the path), with the link to the second node removed. 996 This SPF, while not an incremental, can be terminated as soon as the 997 not-via address is reached. For example, when running the SPF rooted 998 at X, with the link X-Y removed, the SPF can be terminated when Yx is 999 reached. Once the path has been found, the path is checked to 1000 determine if it traverses any of A's links in the direction away from 1001 A. Note that, because the node pair XY may exist in the list for more 1002 than one of A's links (i.e. it lies on more than one repair path), it 1003 is necessary to identify the correct list, and hence link which has a 1004 mutually looping repair path. That link of A is then advertised by A 1005 as a secondary SRLG paired with the link X-Y. Also note that X will 1006 be running this algorithm as well, and will identify that XY is 1007 paired with A-B and so advertise it. This could perhaps be used as a 1008 further check. 1010 The ordering of the pairs in the lists is important. i.e. X-Y and 1011 Y-X are dealt with separately. If and only if the repairs are 1012 mutually incompatible, we need to advertise the pair of links as a 1013 secondary SRLG, and then ALL nodes compute repair paths around both 1014 failures using an additional not-via address with the semantics not- 1015 via A-B AND not-via X-Y. 1017 A further possibility is that because we are going to the trouble of 1018 advertising these SRLG sets, we could also advertise the new repair 1019 path and only get the nodes on that path to perform the necessary 1020 computation. Note also that once we have reached Q-space Appendix A 1021 with respect to the two failures we need no longer continue the 1022 computation, so we only need to notify the nodes on the path that are 1023 not in Q-space. 1025 One cause of mutually looping repair paths is the existence of nodes 1026 with only two links, or sections of the network which are only bi- 1027 connected. In these cases, repair is clearly impossible - the 1028 failure of both links partitions the network. It would be 1029 advantageous to be able to identify these cases, and inhibit the 1030 fruitless advertisement of the secondary SRLG information. This 1031 could be achieved by the node detecting the requirement for a 1032 secondary SRLG, first running the not-via computation with both links 1033 removed. If this does not result in a path, it is clear that the 1034 network would be partitioned by such a failure, and so no 1035 advertisement is required. 1037 5.3.4. Mixing LFAs and Not-via 1039 So far in this section we have assumed that all repairs use not-via 1040 tunnels. However, in practise we may wish to use LFAs or downstream 1041 routes where available. This complicates the issue, because their 1042 use results in packets which are being repaired, but NOT addressed to 1043 not-via addresses. If BOTH links are using downstream routes there 1044 is no possibility of looping, since it is impossible to have a pair 1045 of nodes which are both downstream of each other [RFC5286]. 1047 Loops can however occur when LFAs are used. An obvious example is 1048 the well known node repair problem with LFAs [RFC5286]. If one link 1049 is using a downstream route, while the other is using a not-via 1050 tunnel, the potential mechanism described above would work provided 1051 it were possible to determine the nodes on the path of the downstream 1052 route. Some methods of computing downstream routes do not provide 1053 this path information. If the path information is however available, 1054 the link using a downstream route will have a discard FIB entry for 1055 the not-via address of the other link. The consequence is that 1056 potentially looping packets will be discarded when they attempt to 1057 cross this link. 1059 In the case where the mutual repairs are both using not-via repairs, 1060 the loop will be broken when the packet arrives at the second 1061 failure. However packets are unconditionally repaired by means of a 1062 downstream routes, and thus when the mutual pair consists of a 1063 downstream route and a not-via repair, the looping packet will only 1064 be dropped when it gets back to the first failure. i.e. it will 1065 execute a single turn of the loop before being dropped. 1067 There is a further complication with downstream routes, since 1068 although the path may be computed to the far side of the failure, the 1069 packet may "peel off" to its destination before reaching the far side 1070 of the failure. In this case it may traverse some other link which 1071 has failed and was not accounted for on the computed path. If the 1072 A-B repair (Figure 13) is a downstream route and the X-Y repair is a 1073 not-via repair, we can have the situation where the X-Y repair 1074 packets encapsulated to Yx follow a path which attempts to traverse 1075 A-B. If the A-B repair path for "normal" addresses is a downstream 1076 route, it cannot be assumed that the repair path for packets 1077 addressed to Yx can be sent to the same neighbour. This is because 1078 the validity of a downstream route MUST be ascertained in the 1079 topology represented by Yx, i.e. that with the link X-Y failed. This 1080 is not the same topology that was used for the normal downstream 1081 calculation, and use of the normal downstream route for the 1082 encapsulated packets may result in an undetected loop. If it is 1083 computationally feasible to check the downstream route in this 1084 topology (i.e. for any not-via address Qp which traverses A-B we MUST 1085 perform the downstream calculation for that not-via address in the 1086 topology with link Q-P failed.), then the downstream repair for Yx 1087 can safely be used. These packets cannot re-visit X-Y, since by 1088 definition they will avoid that link. Alternatively, the packet 1089 could be always repaired in a not-via tunnel. i.e. even though the 1090 normal repair for traffic traversing A-B would be to use a downstream 1091 route, we could insist that such traffic addressed to a not-via 1092 address MUST use a tunnel to Ba. Such a tunnel would only be 1093 installed for an address Qp if it were established that it did not 1094 traverse Q-P (using the rules described above). 1096 6. Optimizing not-via computations using LFAs 1098 If repairing node S has an LFA to the repair endpoint it is not 1099 necessary for any router to perform the incremental SPF with the link 1100 SP removed in order to compute the route to the not-via address Ps. 1101 This is because the correct routes will already have been computed as 1102 a result of the SPF on the base topology. Node S can signal this 1103 condition to all other routers by including a bit in its LSP or LSA 1104 associated with each LFA protected link. Routers computing not-via 1105 routes can then omit the running of the iSPF for links with this bit 1106 set. 1108 When running the iSPF for a particular link AB, the calculating 1109 router first checks whether the link AB is present in the existing 1110 SPT. If the link is not present in the SPT, no further work is 1111 required. This check is a normal part of the iSPF computation. 1113 If the link is present in the SPT, this optimization introduces a 1114 further check to determine whether the link is marked as protected by 1115 an LFA in the direction in which the link appears in the SPT. If so 1116 the iSPF need not be performed. For example, if the link appears in 1117 the SPT in the direction A->B and A has indicated that the link AB is 1118 protected by an LFA no further action is required for this link. 1120 If the receipt of this information is delayed, the correct operation 1121 of the protocol is not compromised provided that the necessity to 1122 perform a not-via computation is re-evaluated whenever new 1123 information arrives. 1125 This optimization is not particularly beneficial to nodes close to 1126 the repair since, as has been observed above, the computation for 1127 nodes on the LFA path is trivial. However, for nodes upstream of the 1128 link SP for which S-P is in the path to P, there is a significant 1129 reduction in the computation required. 1131 7. Multicast 1133 Multicast traffic can be repaired in a similar way to unicast. The 1134 multicast forwarder is able to use the not-via address to which the 1135 multicast packet was addressed as an indication of the expected 1136 receive interface and hence to correctly run the required RPF check. 1138 In some cases, all the destinations, including the repair endpoint, 1139 are repairable by an LFA. In this case, all unicast traffic may be 1140 repaired without encapsulation. Multicast traffic still requires 1141 encapsulation, but for the nodes on the LFA repair path the 1142 computation of the not-via forwarding entry is unnecessary since, by 1143 definition, their normal path to the repair endpoint is not via the 1144 failure. 1146 A more complete description of multicast operation is for further 1147 study. 1149 8. Fast Reroute in an MPLS LDP Network. 1151 Not-via addresses are IP addresses and LDP [RFC5036] will distribute 1152 labels for them in the usual way. The not-via repair mechanism may 1153 therefore be used to provide fast re-route in an MPLS network by 1154 first pushing the label which the repair endpoint uses to forward the 1155 packet, and then pushing the label corresponding to the not-via 1156 address needed to effect the repair. Referring once again to 1157 Figure 1, if S has a packet destined for D that it must reach via P 1158 and B, S first pushes B's label for D. S then pushes the label that 1159 its next hop to Bp needs to reach Bp. 1161 Note that in an MPLS LDP network it is necessary for S to have the 1162 repair endpoint's label for the destination. When S is effecting a 1163 link repair it already has this. In the case of a node repair, S 1164 either needs to set up a directed LDP session with each of its 1165 neighbor's neighbors, or it needs to use a method similar to the 1166 next-next hop label distribution mechanism proposed in 1167 [I-D.shen-mpls-ldp-nnhop-label]. 1169 9. Encapsulation 1171 Any IETF specified IP in IP encapsulation may be used to carry a not- 1172 via repair. IP in IP [RFC2003], GRE [RFC1701] and L2TPv3 [RFC3931], 1173 all have the necessary and sufficient properties. The requirement is 1174 that both the encapsulating router and the router to which the 1175 encapsulated packet is addressed have a common ability to process the 1176 chosen encapsulation type. When an MPLS LDP network is being 1177 protected, the encapsulation would normally be an additional MPLS 1178 label. In an MPLS enabled IP network an MPLS label may be used in 1179 place of an IP in IP encapsulation in the case above. 1181 10. Routing Extensions 1183 IPFRR requires routing protocol extensions. Each IPFRR router that 1184 is directly connected to a protected network component MUST advertise 1185 a not-via address for that component. This MUST be advertised in 1186 such a way that the association between the protected component 1187 (link, router or SRLG) and the not-via address can be determined by 1188 the other routers in the network. 1190 It is necessary that not-via capable routers advertise in the IGP 1191 that they will calculate not-via routes. 1193 It is necessary for routers to advertise the type of encapsulation 1194 that they support (MPLS, GRE, L2TPv3 etc). However, the deployment 1195 of mixed IP encapsulation types within a network is discouraged. 1197 If the optimization proposed in Section 6 is to be used the use of 1198 the LFA in place of the not-via repair MUST also be signalled in the 1199 routing protocol. 1201 11. Incremental Deployment 1203 Incremental deployment is supported by excluding routers that are not 1204 calculating not-via routes (as indicated by their capability 1205 information flooded with their link state information) from the base 1206 topology used for the computation of repair paths. In that way 1207 repairs may be steered around islands of routers that are not IPFRR 1208 capable. Routers that are protecting a network component need to 1209 have the capability to encapsulate and decapsulate packets. However, 1210 routers that are on the repair path only need to be capable of 1211 calculating not-via paths and including the not-via addresses in 1212 their FIB i.e. these routers do not need any changes to their 1213 forwarding mechanism. 1215 12. Manageability Considerations 1217 [RFC5714] outlines the general set of manageability consideration 1218 that apply to the general case of IPFRR. We slightly expand this and 1219 add details that are not-via specific. There are three classes 1220 manageability consideration: 1222 1. Pre-failure configuration 1224 2. Pre-failure Monitoring and operational support 1226 3. Failure action verification 1228 12.1. Pre-failure configuration 1230 Pre-failure configuration for not-via includes: 1232 o Enabling/disabling not-via IPFRR support. 1234 o Enabling/disabling protection on a per-link or per-node basis. 1236 o Expressing preferences regarding the links/nodes used for repair 1237 paths. 1239 o Configuration of failure detection mechanisms. 1241 o Setting a preference concerning the use of LFA. 1243 o Configuring not-via address (per interface), or not-via address 1244 set (per node). 1246 o Configuring any SRLG rules or preferences. 1248 Any standard configuration method may be used and the selection of 1249 the method to be used is outside the scope of this document. 1251 12.2. Pre-failure Monitoring and operational support 1253 Pre-failure Monitoring and operational support for not-via includes: 1255 o Notification of links/nodes/destinations that cannot be protected. 1257 o Notification of pre-computed repair paths. 1259 o Notification of repair type to be used (LFA or not-via). 1261 o Notification of not-via address assignment. 1263 o Notification of path or address optimizations used. 1265 o Testing repair paths. Note that not-via addresses look identical 1266 to "ordinary" addresses as far as tools such as trace route and 1267 ping are concerned and thus it is anticipated that these will be 1268 used to verify the established repair path. 1270 Any standard IETF method may be used for the above and the selection 1271 of the method to be used is outside the scope of this document. 1273 12.3. Failure action monitoring 1275 Failure action monitoring for not-via includes: 1277 o Counts of failure detections, protection invocations, and packets 1278 forwarded over repair paths. 1280 o Logging of the events using a sufficiently accurate and precise 1281 timestamp. 1283 o Validation that the packet loss was within specification using a 1284 suitable loss verification tool. 1286 o Capture of the in-flight repair packet flows using a tool such as 1287 IPFIX[RFC5101]. 1289 Note that monitoring the repair in action requires the capture of the 1290 signatures of a short, possibly sub-second network transient which is 1291 not a well developed IETF technology. 1293 13. IANA Considerations 1295 There are no IANA considerations that arise from this draft. 1297 14. Security Considerations 1299 The repair endpoints present vulnerability in that they might be used 1300 as a method of disguising the delivery of a packet to a point in the 1301 network. The primary method of protection SHOULD be through the use 1302 of a private address space for the not-via addresses. These 1303 addresses MUST NOT be advertised outside the area, and SHOULD be 1304 filtered at the network entry points. In addition, a mechanism might 1305 be developed that allowed the use of the mild security available 1306 through the use of a key [RFC1701] [RFC3931]. With the deployment of 1307 such mechanisms, the repair endpoints would not increase the security 1308 risk beyond that of existing IP tunnel mechanisms. An attacker may 1309 attempt to overload a router by addressing an excessive traffic load 1310 to the de-capsulation endpoint. Typically, routers take a 50% 1311 performance penalty in decapsulating a packet. The attacker could 1312 not be certain that the router would be impacted, and the extremely 1313 high volume of traffic needed, would easily be detected as an 1314 anomaly. If an attacker were able to influence the availability of a 1315 link, they could cause the network to invoke the not-via repair 1316 mechanism. A network protected by not-via IPFRR is less vulnerable 1317 to such an attack than a network that undertook a full convergence in 1318 response to a link up/down event. 1320 15. Acknowledgements 1322 The authors would like to acknowledge contributions made by Alia 1323 Atlas and John Harper. 1325 16. References 1327 16.1. Normative References 1329 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1330 Requirement Levels", BCP 14, RFC 2119, March 1997. 1332 16.2. Informative References 1334 [I-D.ietf-rtgwg-ordered-fib] 1335 Shand, M., Bryant, S., Previdi, S., and C. Filsfils, 1336 "Loop-free convergence using oFIB", 1337 draft-ietf-rtgwg-ordered-fib-05 (work in progress), 1338 April 2011. 1340 [I-D.shand-remote-lfa] 1341 Bryant, S., Filsfils, C., Shand, M., and N. So, "Remote 1342 LFA FRR", draft-shand-remote-lfa-01 (work in progress), 1343 June 2012. 1345 [I-D.shen-mpls-ldp-nnhop-label] 1346 Shen, N., "Discovering LDP Next-Nexthop Labels", 1347 draft-shen-mpls-ldp-nnhop-label-02 (work in progress), 1348 May 2005. 1350 [ISPF] McQuillan, J., Richer, I., and E. Rosen, "ARPANET Routing 1351 Algorithm Improvements"", BBN Technical Report 3803, 1978. 1353 [RFC1701] Hanks, S., Li, T., Farinacci, D., and P. Traina, "Generic 1354 Routing Encapsulation (GRE)", RFC 1701, October 1994. 1356 [RFC2003] Perkins, C., "IP Encapsulation within IP", RFC 2003, 1357 October 1996. 1359 [RFC3931] Lau, J., Townsley, M., and I. Goyret, "Layer Two Tunneling 1360 Protocol - Version 3 (L2TPv3)", RFC 3931, March 2005. 1362 [RFC5036] Andersson, L., Minei, I., and B. Thomas, "LDP 1363 Specification", RFC 5036, October 2007. 1365 [RFC5101] Claise, B., "Specification of the IP Flow Information 1366 Export (IPFIX) Protocol for the Exchange of IP Traffic 1367 Flow Information", RFC 5101, January 2008. 1369 [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast 1370 Reroute: Loop-Free Alternates", RFC 5286, September 2008. 1372 [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", 1373 RFC 5714, January 2010. 1375 [RFC5880] Katz, D. and D. Ward, "Bidirectional Forwarding Detection 1376 (BFD)", RFC 5880, June 2010. 1378 Appendix A. Q-Space 1380 Q-space is the set of routers from which a specific router can be 1381 reached without any path (including equal cost path splits) 1382 transiting the protected link (or node). It is fully described in 1383 [I-D.shand-remote-lfa]. 1385 S---E 1386 / \ 1387 A D 1388 \ / 1389 B---C 1391 Figure 15 1393 Consider a repair of link S-E (Figure 15). The set of routers from 1394 which the node E can be reached, by normal forwarding, without 1395 traversing the link S-E is termed the Q-space of E with respect to 1396 the link S-E. The Q-space can be obtained by computing a reverse 1397 shortest path tree (rSPT) rooted at E, with the sub-tree which 1398 traverses the failed link excised (including those which are members 1399 of an ECMP). The rSPT uses the cost towards the root rather than 1400 from it and yields the best paths towards the root from other nodes 1401 in the network. In the case of Figure 15 the Q-space comprises nodes 1402 C and D only. 1404 Authors' Addresses 1406 Stewart Bryant 1407 Cisco Systems 1408 250, Longwater Avenue. 1409 Reading, Berks RG2 6GB 1410 UK 1412 Email: stbryant@cisco.com 1414 Stefano Previdi 1415 Cisco Systems 1416 Via Del Serafico, 200 1417 00142 Rome, 1418 Italy 1420 Email: sprevidi@cisco.com 1422 Mike Shand 1423 Individual Contributor 1425 Email: imc.shand@googlemail.com