idnits 2.17.1 draft-ietf-rtgwg-uloop-delay-08.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 -- The document date (October 12, 2017) is 2385 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. 'ISO10589' == Outdated reference: A later version (-10) exists of draft-ietf-rtgwg-backoff-algo-05 Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Routing Area Working Group S. Litkowski 3 Internet-Draft B. Decraene 4 Intended status: Standards Track Orange 5 Expires: April 15, 2018 C. Filsfils 6 Cisco Systems 7 P. Francois 8 Individual 9 October 12, 2017 11 Micro-loop prevention by introducing a local convergence delay 12 draft-ietf-rtgwg-uloop-delay-08 14 Abstract 16 This document describes a mechanism for link-state routing protocols 17 to prevent local transient forwarding loops in case of link failure. 18 This mechanism proposes a two-step convergence by introducing a delay 19 between the convergence of the node adjacent to the topology change 20 and the network wide convergence. 22 As this mechanism delays the IGP convergence it may only be used for 23 planned maintenance or when fast reroute protects the traffic between 24 the link failure time and the IGP convergence. 26 The proposed mechanism is limited to the link down event in order to 27 keep the mechanism simple. 29 Simulations using real network topologies have been performed and 30 show that local loops are a significant portion (>50%) of the total 31 forwarding loops. 33 Requirements Language 35 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 36 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 37 document are to be interpreted as described in [RFC2119]. 39 Status of This Memo 41 This Internet-Draft is submitted in full conformance with the 42 provisions of BCP 78 and BCP 79. 44 Internet-Drafts are working documents of the Internet Engineering 45 Task Force (IETF). Note that other groups may also distribute 46 working documents as Internet-Drafts. The list of current Internet- 47 Drafts is at https://datatracker.ietf.org/drafts/current/. 49 Internet-Drafts are draft documents valid for a maximum of six months 50 and may be updated, replaced, or obsoleted by other documents at any 51 time. It is inappropriate to use Internet-Drafts as reference 52 material or to cite them other than as "work in progress." 54 This Internet-Draft will expire on April 15, 2018. 56 Copyright Notice 58 Copyright (c) 2017 IETF Trust and the persons identified as the 59 document authors. All rights reserved. 61 This document is subject to BCP 78 and the IETF Trust's Legal 62 Provisions Relating to IETF Documents 63 (https://trustee.ietf.org/license-info) in effect on the date of 64 publication of this document. Please review these documents 65 carefully, as they describe your rights and restrictions with respect 66 to this document. Code Components extracted from this document must 67 include Simplified BSD License text as described in Section 4.e of 68 the Trust Legal Provisions and are provided without warranty as 69 described in the Simplified BSD License. 71 Table of Contents 73 1. Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . 3 74 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 75 3. Transient forwarding loops side effects . . . . . . . . . . . 4 76 3.1. Fast reroute inefficiency . . . . . . . . . . . . . . . . 4 77 3.2. Network congestion . . . . . . . . . . . . . . . . . . . 7 78 4. Overview of the solution . . . . . . . . . . . . . . . . . . 7 79 5. Specification . . . . . . . . . . . . . . . . . . . . . . . . 8 80 5.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 8 81 5.2. Regular IGP reaction . . . . . . . . . . . . . . . . . . 8 82 5.3. Local events . . . . . . . . . . . . . . . . . . . . . . 9 83 5.4. Local delay for link down . . . . . . . . . . . . . . . . 10 84 6. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 10 85 6.1. Applicable case: local loops . . . . . . . . . . . . . . 10 86 6.2. Non applicable case: remote loops . . . . . . . . . . . . 11 87 7. Simulations . . . . . . . . . . . . . . . . . . . . . . . . . 11 88 8. Deployment considerations . . . . . . . . . . . . . . . . . . 12 89 9. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 13 90 9.1. Local link down . . . . . . . . . . . . . . . . . . . . . 14 91 9.2. Local and remote event . . . . . . . . . . . . . . . . . 18 92 9.3. Aborting local delay . . . . . . . . . . . . . . . . . . 19 93 10. Comparison with other solutions . . . . . . . . . . . . . . . 23 94 10.1. PLSN . . . . . . . . . . . . . . . . . . . . . . . . . . 23 95 10.2. OFIB . . . . . . . . . . . . . . . . . . . . . . . . . . 23 96 11. Implementation Status . . . . . . . . . . . . . . . . . . . . 24 97 12. Security Considerations . . . . . . . . . . . . . . . . . . . 25 98 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 25 99 14. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 100 15. References . . . . . . . . . . . . . . . . . . . . . . . . . 26 101 15.1. Normative References . . . . . . . . . . . . . . . . . . 26 102 15.2. Informative References . . . . . . . . . . . . . . . . . 26 103 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 27 105 1. Acronyms 107 FIB: Forwarding Information Base 109 FRR: Fast ReRoute 111 IGP: Interior Gateway Protocol 113 LFA: Loop Free Alternate 115 LSA: Link State Advertisement 117 LSP: Link State Packet 119 MRT: Maximum Redundant Trees 121 OFIB: Ordered FIB 123 PLSN: Path Locking via Safe Neighbor 125 RIB: Routing Information Base 127 RLFA: Remote Loop Free Alternate 129 SPF: Shortest Path First 131 TTL: Time To Live 133 2. Introduction 135 Micro-forwarding loops and some potential solutions are well 136 described in [RFC5715]. This document describes a simple targeted 137 mechanism that prevents micro-loops that are local to the failure. 138 Based on network analysis, local failures make up a significant 139 portion of the micro-forwarding loops. A simple and easily 140 deployable solution for these local micro-loops is critical because 141 these local loops cause some traffic loss after a fast-reroute 142 alternate has been used (see Section 3.1). 144 Consider the case in Figure 1 where S does not have an LFA (Loop Free 145 Alternate) to protect its traffic to D when the S-D link fails. That 146 means that all non-D neighbors of S on the topology will send to S 147 any traffic destined to D; if a neighbor did not, then that neighbor 148 would be loop-free. Regardless of the advanced fast-reroute (FRR) 149 technique used, when S converges to the new topology, it will send 150 its traffic to a neighbor that was not loop-free and thus cause a 151 local micro-loop. The deployment of advanced fast-reroute techniques 152 motivates this simple router-local mechanism to solve this targeted 153 problem. This solution can work with the various techniques 154 described in [RFC5715]. 156 D ------ C 157 | | 158 | | 5 159 | | 160 S ------ B 162 Figure 1 164 In the Figure 1, all links have a metric of 1 except B-C which has a 165 metric of 5. When S-D fails, a transient forwarding loop may appear 166 between S and B if S updates its forwarding entry to D before B does. 168 3. Transient forwarding loops side effects 170 Even if they are very limited in duration, transient forwarding loops 171 may cause significant network damage. 173 3.1. Fast reroute inefficiency 175 D 176 1 | 177 | 1 178 A ------ B 179 | | ^ 180 10 | | 5 | T 181 | | | 182 E--------C 183 | 1 184 1 | 185 S 187 Figure 2 - RSVP-TE FRR case 189 In the Figure 2, we consider an IP/LDP routed network. An RSVP-TE 190 tunnel T, provisioned on C and terminating on B, is used to protect 191 the traffic against C-B link failure (the IGP shortcut feature, 192 defined in [RFC3906], is activated on C ). The primary path of T is 193 C->B and FRR is activated on T providing an FRR bypass or detour 194 using path C->E->A->B. On router C, the next hop to D is the tunnel 195 T thanks to the IGP shortcut. When C-B link fails: 197 1. C detects the failure, and updates the tunnel path using a 198 preprogrammed FRR path. The traffic path from S to D becomes: 199 S->E->C->E->A->B->A->D. 201 2. In parallel, on router C, both the IGP convergence and the TE 202 tunnel convergence (tunnel path recomputation) are occurring: 204 * The Tunnel T path is recomputed and now uses C->E->A->B. 206 * The IGP path to D is recomputed and now uses C->E->A->D. 208 3. On C, the tail-end of the TE tunnel (router B) is no longer on 209 the shortest-path tree (SPT) to D, so C does not continue to 210 encapsulate the traffic to D using the tunnel T and updates its 211 forwarding entry to D using the nexthop E. 213 If C updates its forwarding entry to D before router E, there would 214 be a transient forwarding loop between C and E until E has converged. 216 The table 1 below describes a theoretical sequence of events 217 happening when the B-C link fails. This theoretical sequence of 218 events should only be read as an example. 220 +-----------+------------+------------------+-----------------------+ 221 | Network | Time | Router C events | Router E events | 222 | condition | | | | 223 +-----------+------------+------------------+-----------------------+ 224 | S->D | | | | 225 | Traffic | | | | 226 | OK | | | | 227 | | | | | 228 | S->D | t0 | Link B-C fails | Link B-C fails | 229 | Traffic | | | | 230 | lost | | | | 231 | | | | | 232 | | t0+20msec | C detects the | | 233 | | | failure | | 234 | | | | | 235 | S->D | t0+40msec | C activates FRR | | 236 | Traffic | | | | 237 | OK | | | | 238 | | | | | 239 | | t0+50msec | C updates its | | 240 | | | local LSP/LSA | | 241 | | | | | 242 | | t0+60msec | C schedules SPF | | 243 | | | (100ms) | | 244 | | | | | 245 | | t0+70msec | C floods its | | 246 | | | local updated | | 247 | | | LSP/LSA | | 248 | | | | | 249 | | t0+87msec | | E receives LSP/LSA | 250 | | | | from C and schedules | 251 | | | | SPF (100ms) | 252 | | | | | 253 | | t0+117msec | | E floods LSP/LSA from | 254 | | | | C | 255 | | | | | 256 | | t0+160msec | C computes SPF | | 257 | | | | | 258 | | t0+165msec | C starts | | 259 | | | updating its | | 260 | | | RIB/FIB | | 261 | | | | | 262 | | t0+193msec | | E computes SPF | 263 | | | | | 264 | | t0+199msec | | E starts updating its | 265 | | | | RIB/FIB | 266 | | | | | 267 | S->D | t0+255msec | C updates its | | 268 | Traffic | | RIB/FIB for D | | 269 | lost | | | | 270 | | | | | 271 | | t0+340msec | C convergence | | 272 | | | ends | | 273 | | | | | 274 | S->D | t0+443msec | | E updates its RIB/FIB | 275 | Traffic | | | for D | 276 | OK | | | | 277 | | | | | 278 | | t0+470msec | | E convergence ends | 279 +-----------+------------+------------------+-----------------------+ 281 Table 1 - Route computation event time scale 283 The issue described here is completely independent of the fast- 284 reroute mechanism involved (TE FRR, LFA/rLFA, MRT ...) when the 285 primary path uses hop-by-hop routing. The protection enabled by 286 fast-reroute is working perfectly, but ensures a protection, by 287 definition, only until the PLR has converged (as soon as the PLR has 288 converged, it replaces its FRR path by a new primary path). When 289 implementing FRR, a service provider wants to guarantee a very 290 limited loss of connectivity time. The previous example shows that 291 the benefit of FRR may be completely lost due to a transient 292 forwarding loop appearing when PLR has converged. Delaying FIB 293 updates after the IGP convergence may allow to keep the fast-reroute 294 path until the neighbors have converged and preserves the customer 295 traffic. 297 3.2. Network congestion 299 1 300 D ------ C 301 | | 302 1 | | 5 303 | | 304 A -- S ------ B 305 / | 1 306 F E 308 Figure 3 310 In the figure above, as presented in Section 2, when the link S-D 311 fails, a transient forwarding loop may appear between S and B for 312 destination D. The traffic on the S-B link will constantly increase 313 due to the looping traffic to D. Depending on the TTL of the 314 packets, the traffic rate destined to D, and the bandwidth of the 315 link, the S-B link may become congested in a few hundreds of 316 milliseconds and will stay congested until the loop is eliminated. 318 The congestion introduced by transient forwarding loops is 319 problematic as it can affect traffic that is not directly affected by 320 the failing network component. In the example, the congestion of the 321 S-B link will impact some customer traffic that is not directly 322 affected by the failure: e.g. A to B, F to B, E to B. Class of 323 service may mitigate the congestion for some traffic. However, some 324 traffic not directly affected by the failure will still be dropped as 325 a router is not able to distinguish the looping traffic from the 326 normally forwarded traffic. 328 4. Overview of the solution 330 This document defines a two-step convergence initiated by the router 331 detecting a failure and advertising the topological changes in the 332 IGP. This introduces a delay between network-wide convergence and 333 the convergence of the local router. 335 The proposed solution is limited to local link down events in order 336 to keep the solution simple. 338 This ordered convergence is similar to the ordered FIB proposed 339 defined in [RFC6976], but it is limited to only a "one hop" distance. 340 As a consequence, it is more simple and becomes a local-only feature 341 that does not require interoperability. This benefit comes with the 342 limitation of eliminating transient forwarding loops involving the 343 local router only. The proposed mechanism also reuses some concepts 344 described in [I-D.ietf-rtgwg-microloop-analysis]. 346 5. Specification 348 5.1. Definitions 350 This document will refer to the following existing IGP timers. These 351 timers may be standardized or implemented as a vendor specific local 352 feature. 354 o LSP_GEN_TIMER: The delay used to batch multiple local events in 355 one single local LSP/LSA update. In IS-IS, this timer is defined 356 as minimumLSPGenerationInterval in [ISO10589]. In OSPF version 2, 357 this timer is defined as MinLSInterval in [RFC2328]. It is often 358 associated with a vendor specific damping mechanism to slow down 359 reactions by incrementing the timer when multiple consecutive 360 events are detected. 362 o SPF_DELAY: The delay between the first IGP event triggering a new 363 routing table computation and the start of that routing table 364 computation. It is often associated with a damping mechanism to 365 slow down reactions by incrementing the timer when the IGP becomes 366 unstable. As an example, [I-D.ietf-rtgwg-backoff-algo] defines a 367 standard SPF (Shortest Path First) delay algorithm. 369 This document introduces the following new timer: 371 o ULOOP_DELAY_DOWN_TIMER: used to slow down the local node 372 convergence in case of link down events. 374 5.2. Regular IGP reaction 376 Upon a change of the status of an adjacency/link, the regular IGP 377 convergence behavior of the router advertising the event involves the 378 following main steps: 380 1. IGP is notified of the Up/Down event. 382 2. The IGP processes the notification and postpones the reaction for 383 LSP_GEN_TIMER msec. 385 3. Upon LSP_GEN_TIMER expiration, the IGP updates its LSP/LSA and 386 floods it. 388 4. The SPF computation is scheduled in SPF_DELAY msec. 390 5. Upon SPF_DELAY timer expiration, the SPF is computed, then the 391 RIB and FIB are updated. 393 5.3. Local events 395 The mechanism described in this document assumes that there has been 396 a single link failure as seen by the IGP area/level. If this 397 assumption is violated (e.g. multiple links or nodes failed), then 398 regular IP convergence must be applied (as described in Section 5.2). 400 To determine if the mechanism can be applicable or not, an 401 implementation SHOULD implement logic to correlate the protocol 402 messages (LSP/LSA) received during the SPF scheduling period in order 403 to determine the topology changes that occured. This is necessary as 404 multiple protocol messages may describe the same topology change and 405 a single protocol message may describe multiple topology changes. As 406 a consequence, determining a particular topology change MUST be 407 independent of the order of reception of those protocol messages. 408 How the logic works is left to the implementation. 410 Using this logic, if an implementation determines that the associated 411 topology change is a single local link failure, then the router MAY 412 use the mechanism described in this document, otherwise the regular 413 IP convergence MUST be used. 415 Example: 417 +--- E ----+--------+ 418 | | | 419 A ---- B -------- C ------ D 421 Figure 4 423 Let router B be the computing router when the link B-C fails. B 424 updates its local LSP/LSA describing the link B->C as down, C does 425 the same, and both start flooding their updated LSP/LSAs. During the 426 SPF_DELAY period, B and C learn all the LSPs/LSAs to consider. B 427 sees that C is flooding an advertisement that indicates that a link 428 is down, and B is the other end of that link. B determines that B 429 and C are describing the same single event. Since B receives no 430 other changes, B can determine that this is a local link failure and 431 may decide to activate the mechanism described in this document. 433 5.4. Local delay for link down 435 Upon an adjacency/link down event, this document introduces a change 436 in step 5 (Section 5.2) in order to delay the local convergence 437 compared to the network wide convergence. The new step 5 is 438 described below: 440 5. Upon SPF_DELAY timer expiration, the SPF is computed. If the 441 condition of a single local link-down event has been met, then an 442 update of the RIB and the FIB MUST be delayed for 443 ULOOP_DELAY_DOWN_TIMER msecs. Otherwise, the RIB and FIB SHOULD 444 be updated immediately. 446 If a new convergence occurs while ULOOP_DELAY_DOWN_TIMER is running, 447 ULOOP_DELAY_DOWN_TIMER is stopped and the RIB/FIB SHOULD be updated 448 as part of the new convergence event. 450 As a result of this addition, routers local to the failure will 451 converge slower than remote routers. Hence it SHOULD only be done 452 for a non-urgent convergence, such as for administrative de- 453 activation (maintenance) or when the traffic is protected by fast- 454 reroute. 456 6. Applicability 458 As previously stated, this mechanism only avoids the forwarding loops 459 on the links between the node local to the failure and its neighbors. 460 Forwarding loops may still occur on other links. 462 6.1. Applicable case: local loops 464 A ------ B ----- E 465 | / | 466 | / | 467 G---D------------C F All the links have a metric of 1 469 Figure 5 471 Let us consider the traffic from G to F. The primary path is 472 G->D->C->E->F. When link C-E fails, if C updates its forwarding 473 entry for F before D, a transient loop occurs. This is sub-optimal 474 as C has FRR enabled and it breaks the FRR forwarding while all 475 upstream routers are still forwarding the traffic to itself. 477 By implementing the mechanism defined in this document on C, when the 478 C-E link fails, C delays the update of its forwarding entry to F, in 479 order to allow some time for D to converge. FRR on C keeps 480 protecting the traffic during this period. When the timer expires on 481 C, its forwarding entry to F is updated. There is no transient 482 forwarding loop on the link C-D. 484 6.2. Non applicable case: remote loops 486 A ------ B ----- E --- H 487 | | 488 | | 489 G---D--------C ------F --- J ---- K 491 All the links have a metric of 1 except BE=15 493 Figure 6 495 Let us consider the traffic from G to K. The primary path is 496 G->D->C->F->J->K. When the C-F link fails, if C updates its 497 forwarding entry to K before D, a transient loop occurs between C and 498 D. 500 By implementing the mechanism defined in this document on C, when the 501 link C-F fails, C delays the update of its forwarding entry to K, 502 allowing time for D to converge. When the timer expires on C, its 503 forwarding entry to F is updated. There is no transient forwarding 504 loop between C and D. However, a transient forwarding loop may still 505 occur between D and A. In this scenario, this mechanism is not 506 enough to address all the possible forwarding loops. However, it 507 does not create additional traffic loss. Besides, in some cases 508 -such as when the nodes update their FIB in the following order C, A, 509 D, for example because the router A is quicker than D to converge- 510 the mechanism may still avoid the forwarding loop that would have 511 otherwise occurred. 513 7. Simulations 515 Simulations have been run on multiple service provider topologies. 517 +----------+------+ 518 | Topology | Gain | 519 +----------+------+ 520 | T1 | 71% | 521 | T2 | 81% | 522 | T3 | 62% | 523 | T4 | 50% | 524 | T5 | 70% | 525 | T6 | 70% | 526 | T7 | 59% | 527 | T8 | 77% | 528 +----------+------+ 530 Table 2 - Number of Repair/Dst that may loop 532 We evaluated the efficiency of the mechanism on eight different 533 service provider topologies (different network size, design). The 534 benefit is displayed in the table above. The benefit is evaluated as 535 follows: 537 o We consider a tuple (link A-B, destination D, PLR S, backup 538 nexthop N) as a loop if upon link A-B failure, the flow from a 539 router S upstream from A (A could be considered as PLR also) to D 540 may loop due to convergence time difference between S and one of 541 his neighbors N. 543 o We evaluate the number of potential loop tuples in normal 544 conditions. 546 o We evaluate the number of potential loop tuples using the same 547 topological input but taking into account that S converges after 548 N. 550 o The gain is how many loops (both remote and local) we succeed to 551 suppress. 553 On topology 1, 71% of the transient forwarding loops created by the 554 failure of any link are prevented by implementing the local delay. 555 The analysis shows that all local loops are prevented and only remote 556 loops remain. 558 8. Deployment considerations 560 Transient forwarding loops have the following drawbacks: 562 o They limit FRR efficiency: even if FRR is activated within 50msec, 563 as soon as PLR has converged, the traffic may be affected by a 564 transient loop. 566 o They may impact traffic not directly affected by the failure (due 567 to link congestion). 569 This local delay proposal is a transient forwarding loop avoidance 570 mechanism (like OFIB). Even if it only addresses local transient 571 loops, the efficiency versus complexity comparison of the mechanism 572 makes it a good solution. It is also incrementally deployable with 573 incremental benefits, which makes it an attractive option both for 574 vendors to implement and service providers to deploy. Delaying the 575 convergence time is not an issue if we consider that the traffic is 576 protected during the convergence. 578 The ULOOP_DELAY_DOWN_TIMER value should be set according to the 579 maximum IGP convergence time observed in the network (usually 580 observed in the slowest node). 582 The proposed mechanism is limited to link down events. When a link 583 goes down, it eventually goes back up. As a consequence, with the 584 proposed mechanism deployed, only the link down event will be 585 protected against transient forwarding loops while the link up event 586 will not. If the operator wants to limit the impact of the transient 587 forwarding loops during the link up event, it should take care of 588 using specific procedures to bring the link back online. As 589 examples, the operator can decide to put back the link online out of 590 business hours or it can use some incremental metric changes to 591 prevent loops (as proposed in [RFC5715]). 593 9. Examples 595 We will consider the following figure for the associated examples : 597 D 598 1 | F----X 599 | 1 | 600 A ------ B 601 | | 602 10 | | 5 603 | | 604 E--------C 605 | 1 606 1 | 607 S 609 Figure 7 611 The network above is considered to have a convergence time about 1 612 second, so ULOOP_DELAY_DOWN_TIMER will be adjusted to this value. We 613 also consider that FRR is running on each node. 615 9.1. Local link down 617 The table 3 describes the events and associated timing that happen on 618 router C and E when link B-C goes down. It is based on a theoretical 619 sequence of event that should only been read as an example. As C 620 detects a single local event corresponding to a link down (its LSP + 621 LSP from B received), it applies the local delay down behavior and no 622 microloop is formed. 624 +-----------+-------------+------------------+----------------------+ 625 | Network | Time | Router C events | Router E events | 626 | condition | | | | 627 +-----------+-------------+------------------+----------------------+ 628 | S->D | | | | 629 | Traffic | | | | 630 | OK | | | | 631 | | | | | 632 | S->D | t0 | Link B-C fails | Link B-C fails | 633 | Traffic | | | | 634 | lost | | | | 635 | | | | | 636 | | t0+20msec | C detects the | | 637 | | | failure | | 638 | | | | | 639 | S->D | t0+40msec | C activates FRR | | 640 | Traffic | | | | 641 | OK | | | | 642 | | | | | 643 | | t0+50msec | C updates its | | 644 | | | local LSP/LSA | | 645 | | | | | 646 | | t0+60msec | C schedules SPF | | 647 | | | (100ms) | | 648 | | | | | 649 | | t0+67msec | C receives | | 650 | | | LSP/LSA from B | | 651 | | | | | 652 | | t0+70msec | C floods its | | 653 | | | local updated | | 654 | | | LSP/LSA | | 655 | | | | | 656 | | t0+87msec | | E receives LSP/LSA | 657 | | | | from C and schedules | 658 | | | | SPF (100ms) | 659 | | | | | 660 | | t0+117msec | | E floods LSP/LSA | 661 | | | | from C | 662 | | | | | 663 | | t0+160msec | C computes SPF | | 664 | | | | | 665 | | t0+165msec | C delays its | | 666 | | | RIB/FIB update | | 667 | | | (1 sec) | | 668 | | | | | 669 | | t0+193msec | | E computes SPF | 670 | | | | | 671 | | t0+199msec | | E starts updating | 672 | | | | its RIB/FIB | 673 | | | | | 674 | | t0+443msec | | E updates its | 675 | | | | RIB/FIB for D | 676 | | | | | 677 | | t0+470msec | | E convergence ends | 678 | | | | | 679 | | t0+1165msec | C starts | | 680 | | | updating its | | 681 | | | RIB/FIB | | 682 | | | | | 683 | | t0+1255msec | C updates its | | 684 | | | RIB/FIB for D | | 685 | | | | | 686 | | t0+1340msec | C convergence | | 687 | | | ends | | 688 +-----------+-------------+------------------+----------------------+ 690 Table 3 - Route computation event time scale 692 Similarly, upon B-C link down event, if LSP/LSA from B is received 693 before C detects the link failure, C will apply the route update 694 delay if the local detection is part of the same SPF run. The table 695 4 describes the associated theoretical sequence of events. It should 696 only been read as an example. 698 +-----------+-------------+------------------+----------------------+ 699 | Network | Time | Router C events | Router E events | 700 | condition | | | | 701 +-----------+-------------+------------------+----------------------+ 702 | S->D | | | | 703 | Traffic | | | | 704 | OK | | | | 705 | | | | | 706 | S->D | t0 | Link B-C fails | Link B-C fails | 707 | Traffic | | | | 708 | lost | | | | 709 | | | | | 710 | | t0+32msec | C receives | | 711 | | | LSP/LSA from B | | 712 | | | | | 713 | | t0+33msec | C schedules SPF | | 714 | | | (100ms) | | 715 | | | | | 716 | | t0+50msec | C detects the | | 717 | | | failure | | 718 | | | | | 719 | S->D | t0+55msec | C activates FRR | | 720 | Traffic | | | | 721 | OK | | | | 722 | | | | | 723 | | t0+55msec | C updates its | | 724 | | | local LSP/LSA | | 725 | | | | | 726 | | t0+70msec | C floods its | | 727 | | | local updated | | 728 | | | LSP/LSA | | 729 | | | | | 730 | | t0+87msec | | E receives LSP/LSA | 731 | | | | from C and schedules | 732 | | | | SPF (100ms) | 733 | | | | | 734 | | t0+117msec | | E floods LSP/LSA | 735 | | | | from C | 736 | | | | | 737 | | t0+160msec | C computes SPF | | 738 | | | | | 739 | | t0+165msec | C delays its | | 740 | | | RIB/FIB update | | 741 | | | (1 sec) | | 742 | | | | | 743 | | t0+193msec | | E computes SPF | 744 | | | | | 745 | | t0+199msec | | E starts updating | 746 | | | | its RIB/FIB | 747 | | | | | 748 | | t0+443msec | | E updates its | 749 | | | | RIB/FIB for D | 750 | | | | | 751 | | t0+470msec | | E convergence ends | 752 | | | | | 753 | | t0+1165msec | C starts | | 754 | | | updating its | | 755 | | | RIB/FIB | | 756 | | | | | 757 | | t0+1255msec | C updates its | | 758 | | | RIB/FIB for D | | 759 | | | | | 760 | | t0+1340msec | C convergence | | 761 | | | ends | | 762 +-----------+-------------+------------------+----------------------+ 764 Table 4 - Route computation event time scale 766 9.2. Local and remote event 768 The table 5 describes the events and associated timing that happen on 769 router C and E when link B-C goes down, in addition F-X link will 770 fail in the same time window. C will not apply the local delay 771 because a non local topology change is also received. The table 5 is 772 based on a theoretical sequence of event that should only been read 773 as an example. 775 +-----------+------------+-----------------+------------------------+ 776 | Network | Time | Router C events | Router E events | 777 | condition | | | | 778 +-----------+------------+-----------------+------------------------+ 779 | S->D | | | | 780 | Traffic | | | | 781 | OK | | | | 782 | | | | | 783 | S->D | t0 | Link B-C fails | Link B-C fails | 784 | Traffic | | | | 785 | lost | | | | 786 | | | | | 787 | | t0+20msec | C detects the | | 788 | | | failure | | 789 | | | | | 790 | | t0+36msec | Link F-X fails | Link F-X fails | 791 | | | | | 792 | S->D | t0+40msec | C activates FRR | | 793 | Traffic | | | | 794 | OK | | | | 795 | | | | | 796 | | t0+50msec | C updates its | | 797 | | | local LSP/LSA | | 798 | | | | | 799 | | t0+54msec | C receives | | 800 | | | LSP/LSA from F | | 801 | | | and floods it | | 802 | | | | | 803 | | t0+60msec | C schedules SPF | | 804 | | | (100ms) | | 805 | | | | | 806 | | t0+67msec | C receives | | 807 | | | LSP/LSA from B | | 808 | | | | | 809 | | t0+69msec | | E receives LSP/LSA | 810 | | | | from F, floods it and | 811 | | | | schedules SPF (100ms) | 812 | | | | | 813 | | t0+70msec | C floods its | | 814 | | | local updated | | 815 | | | LSP/LSA | | 816 | | | | | 817 | | t0+87msec | | E receives LSP/LSA | 818 | | | | from C | 819 | | | | | 820 | | t0+117msec | | E floods LSP/LSA from | 821 | | | | C | 822 | | | | | 823 | | t0+160msec | C computes SPF | | 824 | | | | | 825 | | t0+165msec | C starts | | 826 | | | updating its | | 827 | | | RIB/FIB (NO | | 828 | | | DELAY) | | 829 | | | | | 830 | | t0+170msec | | E computes SPF | 831 | | | | | 832 | | t0+173msec | | E starts updating its | 833 | | | | RIB/FIB | 834 | | | | | 835 | S->D | t0+365msec | C updates its | | 836 | Traffic | | RIB/FIB for D | | 837 | lost | | | | 838 | | | | | 839 | S->D | t0+443msec | | E updates its RIB/FIB | 840 | Traffic | | | for D | 841 | OK | | | | 842 | | | | | 843 | | t0+450msec | C convergence | | 844 | | | ends | | 845 | | | | | 846 | | t0+470msec | | E convergence ends | 847 | | | | | 848 +-----------+------------+-----------------+------------------------+ 850 Table 5 - Route computation event time scale 852 9.3. Aborting local delay 854 The table 6 describes the events and associated timing that happen on 855 router C and E when link B-C goes down. In addition, we consider 856 what happens when F-X link fails during local delay of the FIB 857 update. C will first apply the local delay, but when the new event 858 happens, it will fall back to the standard convergence mechanism 859 without further delaying route insertion. In this example, we 860 consider a ULOOP_DELAY_DOWN_TIMER configured to 2 seconds. The table 861 6 is based on a theoretical sequence of event that should only been 862 read as an example. 864 +-----------+------------+-------------------+----------------------+ 865 | Network | Time | Router C events | Router E events | 866 | condition | | | | 867 +-----------+------------+-------------------+----------------------+ 868 | S->D | | | | 869 | Traffic | | | | 870 | OK | | | | 871 | | | | | 872 | S->D | t0 | Link B-C fails | Link B-C fails | 873 | Traffic | | | | 874 | lost | | | | 875 | | | | | 876 | | t0+20msec | C detects the | | 877 | | | failure | | 878 | | | | | 879 | S->D | t0+40msec | C activates FRR | | 880 | Traffic | | | | 881 | OK | | | | 882 | | | | | 883 | | t0+50msec | C updates its | | 884 | | | local LSP/LSA | | 885 | | | | | 886 | | t0+60msec | C schedules SPF | | 887 | | | (100ms) | | 888 | | | | | 889 | | t0+67msec | C receives | | 890 | | | LSP/LSA from B | | 891 | | | | | 892 | | t0+70msec | C floods its | | 893 | | | local updated | | 894 | | | LSP/LSA | | 895 | | | | | 896 | | t0+87msec | | E receives LSP/LSA | 897 | | | | from C and schedules | 898 | | | | SPF (100ms) | 899 | | | | | 900 | | t0+117msec | | E floods LSP/LSA | 901 | | | | from C | 902 | | | | | 903 | | t0+160msec | C computes SPF | | 904 | | | | | 905 | | t0+165msec | C delays its | | 906 | | | RIB/FIB update (2 | | 907 | | | sec) | | 908 | | | | | 909 | | t0+193msec | | E computes SPF | 910 | | | | | 911 | | t0+199msec | | E starts updating | 912 | | | | its RIB/FIB | 913 | | | | | 914 | | t0+254msec | Link F-X fails | Link F-X fails | 915 | | | | | 916 | | t0+300msec | C receives | | 917 | | | LSP/LSA from F | | 918 | | | and floods it | | 919 | | | | | 920 | | t0+303msec | C schedules SPF | | 921 | | | (200ms) | | 922 | | | | | 923 | | t0+312msec | E receives | | 924 | | | LSP/LSA from F | | 925 | | | and floods it | | 926 | | | | | 927 | | t0+313msec | E schedules SPF | | 928 | | | (200ms) | | 929 | | | | | 930 | | t0+502msec | C computes SPF | | 931 | | | | | 932 | | t0+505msec | C starts updating | | 933 | | | its RIB/FIB (NO | | 934 | | | DELAY) | | 935 | | | | | 936 | | t0+514msec | | E computes SPF | 937 | | | | | 938 | | t0+519msec | | E starts updating | 939 | | | | its RIB/FIB | 940 | | | | | 941 | S->D | t0+659msec | C updates its | | 942 | Traffic | | RIB/FIB for D | | 943 | lost | | | | 944 | | | | | 945 | S->D | t0+778msec | | E updates its | 946 | Traffic | | | RIB/FIB for D | 947 | OK | | | | 948 | | | | | 949 | | t0+781msec | C convergence | | 950 | | | ends | | 951 | | | | | 952 | | t0+810msec | | E convergence ends | 953 +-----------+------------+-------------------+----------------------+ 955 Table 6 - Route computation event time scale 957 10. Comparison with other solutions 959 As stated in Section 4, the proposed solution reuses some concepts 960 already introduced by other IETF proposals but tries to find a 961 tradeoff between efficiency and simplicity. This section tries to 962 compare behaviors of the solutions. 964 10.1. PLSN 966 PLSN ([I-D.ietf-rtgwg-microloop-analysis]) describes a mechanism 967 where each node in the network tries to avoid transient forwarding 968 loops upon a topology change by always keeping traffic on a loop-free 969 path for a defined duration (locked path to a safe neighbor). The 970 locked path may be the new primary nexthop, another neighbor, or the 971 old primary nexthop depending how the safety condition is satisfied. 973 PLSN does not solve all transient forwarding loops (see 974 [I-D.ietf-rtgwg-microloop-analysis] Section 4 for more details). 976 Our solution reuses some concept of PLSN but in a more simple 977 fashion: 979 o PLSN has three different behaviors: keep using old nexthop, use 980 new primary nexthop if it is safe, or use another safe nexthop, 981 while the proposed solution only has one: keep using the current 982 nexthop (old primary, or already activated FRR path). 984 o PLSN may cause some damage while using a safe nexthop which is not 985 the new primary nexthop in case the new safe nexthop does not 986 provide enough bandwidth (see [RFC7916]). This solution may not 987 experience this issue as the service provider may have control on 988 the FRR path being used preventing network congestion. 990 o PLSN applies to all nodes in a network (remote or local changes), 991 while the proposed mechanism applies only on the nodes connected 992 to the topology change. 994 10.2. OFIB 996 OFIB ([RFC6976]) describes a mechanism where the convergence of the 997 network upon a topology change is ordered in order to prevent 998 transient forwarding loops. Each router in the network must deduce 999 the failure type from the LSA/LSP received and computes/applies a 1000 specific FIB update timer based on the failure type and its rank in 1001 the network considering the failure point as root. 1003 This mechanism allows to solve all the transient forwarding loop in a 1004 network at the price of introducing complexity in the convergence 1005 process that may require a strong monitoring by the service provider. 1007 Our solution reuses the OFIB concept but limits it to the first hop 1008 that experiences the topology change. As demonstrated, the mechanism 1009 proposed in this document allows to solve all the local transient 1010 forwarding loops that represents an high percentage of all the loops. 1011 Moreover limiting the mechanism to one hop allows to keep the 1012 network-wide convergence behavior. 1014 11. Implementation Status 1016 At this time, there are three different implementations of this 1017 mechanism. 1019 o Implementation 1: 1021 * Organization: Cisco 1023 * Implementation name: Local Microloop Protection 1025 * Operating system: IOS-XE 1027 * Level of maturity: production release 1029 * Coverage: all the specification is implemented 1031 * Protocols supported: ISIS and OSPF 1033 * Implementation experience: tested in lab and works as expected 1035 * Comment: the feature gives the ability to choose to apply the 1036 delay to FRR protected entry only 1038 * Report last update: 10-11-2017 1040 o Implementation 2: 1042 * Organization: Cisco 1044 * Implementation name: Local Microloop Protection 1046 * Operating system: IOS-XR 1048 * Level of maturity: deployed 1050 * Coverage: all the specification is implemented 1051 * Protocols supported: ISIS and OSPF 1053 * Implementation experience: deployed and works as expected 1055 * Comment: the feature gives the ability to choose to apply the 1056 delay to FRR protected entry only 1058 * Report last update: 10-11-2017 1060 o Implementation 3: 1062 * Organization: Juniper Networks 1064 * Implementation name: Microloop avoidance when IS-IS link fails 1066 * Operating system: JUNOS 1068 * Level of maturity: deployed (hidden command) 1070 * Coverage: all the specification is implemented 1072 * Protocols supported: ISIS only 1074 * Implementation experience: deployed and works as expected 1076 * Comment: the feature applies to all the ISIS routes 1078 * Report last update: 10-11-2017 1080 12. Security Considerations 1082 This document does not introduce any change in term of IGP security. 1083 The operation is internal to the router. The local delay does not 1084 increase the number of attack vectors as an attacker could only 1085 trigger this mechanism if he already has be ability to disable or 1086 enable an IGP link. The local delay does not increase the negative 1087 consequences. If an attacker has the ability to disable or enable an 1088 IGP link, it can already harm the network by creating instability and 1089 harm the traffic by creating forwarding packet loss and forwarding 1090 loss for the traffic crossing that link. 1092 13. Acknowledgements 1094 We would like to thanks the authors of [RFC6976] for introducing the 1095 concept of ordered convergence: Mike Shand, Stewart Bryant, Stefano 1096 Previdi, and Olivier Bonaventure. 1098 14. IANA Considerations 1100 This document has no actions for IANA. 1102 15. References 1104 15.1. Normative References 1106 [ISO10589] 1107 "Intermediate System to Intermediate System intra-domain 1108 routeing information exchange protocol for use in 1109 conjunction with the protocol for providing the 1110 connectionless-mode network service (ISO 8473)", 1111 ISO 10589, 2002. 1113 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1114 Requirement Levels", BCP 14, RFC 2119, 1115 DOI 10.17487/RFC2119, March 1997, 1116 . 1118 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, 1119 DOI 10.17487/RFC2328, April 1998, 1120 . 1122 15.2. Informative References 1124 [I-D.ietf-rtgwg-backoff-algo] 1125 Decraene, B., Litkowski, S., Gredler, H., Lindem, A., 1126 Francois, P., and C. Bowers, "SPF Back-off algorithm for 1127 link state IGPs", draft-ietf-rtgwg-backoff-algo-05 (work 1128 in progress), May 2017. 1130 [I-D.ietf-rtgwg-microloop-analysis] 1131 Zinin, A., "Analysis and Minimization of Microloops in 1132 Link-state Routing Protocols", draft-ietf-rtgwg-microloop- 1133 analysis-01 (work in progress), October 2005. 1135 [RFC3906] Shen, N. and H. Smit, "Calculating Interior Gateway 1136 Protocol (IGP) Routes Over Traffic Engineering Tunnels", 1137 RFC 3906, DOI 10.17487/RFC3906, October 2004, 1138 . 1140 [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free 1141 Convergence", RFC 5715, DOI 10.17487/RFC5715, January 1142 2010, . 1144 [RFC6976] Shand, M., Bryant, S., Previdi, S., Filsfils, C., 1145 Francois, P., and O. Bonaventure, "Framework for Loop-Free 1146 Convergence Using the Ordered Forwarding Information Base 1147 (oFIB) Approach", RFC 6976, DOI 10.17487/RFC6976, July 1148 2013, . 1150 [RFC7916] Litkowski, S., Ed., Decraene, B., Filsfils, C., Raza, K., 1151 Horneffer, M., and P. Sarkar, "Operational Management of 1152 Loop-Free Alternates", RFC 7916, DOI 10.17487/RFC7916, 1153 July 2016, . 1155 Authors' Addresses 1157 Stephane Litkowski 1158 Orange 1160 Email: stephane.litkowski@orange.com 1162 Bruno Decraene 1163 Orange 1165 Email: bruno.decraene@orange.com 1167 Clarence Filsfils 1168 Cisco Systems 1170 Email: cfilsfil@cisco.com 1172 Pierre Francois 1173 Individual 1175 Email: pfrpfr@gmail.com