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