idnits 2.17.1 draft-ietf-rtgwg-uloop-delay-07.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 10, 2017) is 2389 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) == Outdated reference: A later version (-10) exists of draft-ietf-rtgwg-backoff-algo-05 Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). 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 13, 2018 C. Filsfils 6 Cisco Systems 7 P. Francois 8 Individual 9 October 10, 2017 11 Micro-loop prevention by introducing a local convergence delay 12 draft-ietf-rtgwg-uloop-delay-07 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 13, 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. Current IGP reactions . . . . . . . . . . . . . . . . . . 8 82 5.3. Local events . . . . . . . . . . . . . . . . . . . . . . 9 83 5.4. Local delay for link down . . . . . . . . . . . . . . . . 9 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 . . . . . . . . . . . . . . . . . . . . . 13 91 9.2. Local and remote event . . . . . . . . . . . . . . . . . 17 92 9.3. Aborting local delay . . . . . . . . . . . . . . . . . . 18 93 10. Comparison with other solutions . . . . . . . . . . . . . . . 21 94 10.1. PLSN . . . . . . . . . . . . . . . . . . . . . . . . . . 21 95 10.2. OFIB . . . . . . . . . . . . . . . . . . . . . . . . . . 21 96 11. Existing implementations . . . . . . . . . . . . . . . . . . 22 97 12. Security Considerations . . . . . . . . . . . . . . . . . . . 22 98 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 22 99 14. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 100 15. References . . . . . . . . . . . . . . . . . . . . . . . . . 22 101 15.1. Normative References . . . . . . . . . . . . . . . . . . 23 102 15.2. Informative References . . . . . . . . . . . . . . . . . 23 103 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 23 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. That means that all non-D 146 neighbors of S on the topology will send to S any traffic destined to 147 D if a neighbor did not, then that neighbor would be loop-free. 148 Regardless of the advanced fast-reroute (FRR) technique used, when S 149 converges to the new topology, it will send its traffic to a neighbor 150 that was not loop-free and thus cause a local micro-loop. The 151 deployment of advanced fast-reroute techniques motivates this simple 152 router-local mechanism to solve this targeted problem. This solution 153 can be work with the various techniques described in [RFC5715]. 155 1 156 D ------ C 157 | | 158 1 | | 5 159 | | 160 S ------ B 161 1 162 Figure 1 164 When S-D fails, a transient forwarding loop may appear between S and 165 B if S updates its forwarding entry to D before B. 167 3. Transient forwarding loops side effects 169 Even if they are very limited in duration, transient forwarding loops 170 may cause high damages for a network. 172 3.1. Fast reroute inefficiency 174 D 175 1 | 176 | 1 177 A ------ B 178 | | ^ 179 10 | | 5 | T 180 | | | 181 E--------C 182 | 1 183 1 | 184 S 186 Figure 2 - RSVP-TE FRR case 188 In the Figure 2, we consider an IP/LDP routed network. An RSVP-TE 189 tunnel T, provisioned on C and terminating on B, is used to protect 190 the traffic against C-B link failure (the IGP shortcut feature is 191 activated on C). The primary path of T is C->B and FRR is activated 192 on T providing an FRR bypass or detour using path C->E->A->B. On 193 router C, the next hop to D is the tunnel T thanks to the IGP 194 shortcut. When C-B link fails: 196 1. C detects the failure, and updates the tunnel path using a 197 preprogrammed FRR path. The traffic path from S to D becomes: 198 S->E->C->E->A->B->A->D. 200 2. In parallel, on router C, both the IGP convergence and the TE 201 tunnel convergence (tunnel path recomputation) are occurring: 203 * The Tunnel T path is recomputed and now uses C->E->A->B. 205 * The IGP path to D is recomputed and now uses C->E->A->D. 207 3. On C, the tail-end of the TE tunnel (router B) is no longer on 208 the shortest-path tree (SPT) to D, so C does not continue to 209 encapsulate the traffic to D using the tunnel T and updates its 210 forwarding entry to D using the nexthop E. 212 If C updates its forwarding entry to D before router E, there would 213 be a transient forwarding loop between C and E until E has converged. 215 +-----------+------------+------------------+-----------------------+ 216 | Network | Time | Router C events | Router E events | 217 | condition | | | | 218 +-----------+------------+------------------+-----------------------+ 219 | S->D | | | | 220 | Traffic | | | | 221 | OK | | | | 222 | | | | | 223 | S->D | t0 | Link B-C fails | Link B-C fails | 224 | Traffic | | | | 225 | lost | | | | 226 | | | | | 227 | | t0+20msec | C detects the | | 228 | | | failure | | 229 | | | | | 230 | S->D | t0+40msec | C activates FRR | | 231 | Traffic | | | | 232 | OK | | | | 233 | | | | | 234 | | t0+50msec | C updates its | | 235 | | | local LSP/LSA | | 236 | | | | | 237 | | t0+60msec | C schedules SPF | | 238 | | | (100ms) | | 239 | | | | | 240 | | t0+70msec | C floods its | | 241 | | | local updated | | 242 | | | LSP/LSA | | 243 | | | | | 244 | | t0+87msec | | E receives LSP/LSA | 245 | | | | from C and schedules | 246 | | | | SPF (100ms) | 247 | | | | | 248 | | t0+117msec | | E floods LSP/LSA from | 249 | | | | C | 250 | | | | | 251 | | t0+160msec | C computes SPF | | 252 | | | | | 253 | | t0+165msec | C starts | | 254 | | | updating its | | 255 | | | RIB/FIB | | 256 | | | | | 257 | | t0+193msec | | E computes SPF | 258 | | | | | 259 | | t0+199msec | | E starts updating its | 260 | | | | RIB/FIB | 261 | | | | | 262 | S->D | t0+255msec | C updates its | | 263 | Traffic | | RIB/FIB for D | | 264 | lost | | | | 265 | | | | | 266 | | t0+340msec | C convergence | | 267 | | | ends | | 268 | | | | | 269 | S->D | t0+443msec | | E updates its RIB/FIB | 270 | Traffic | | | for D | 271 | OK | | | | 272 | | | | | 273 | | t0+470msec | | E convergence ends | 274 +-----------+------------+------------------+-----------------------+ 276 Route computation event time scale 278 The issue described here is completely independent of the fast- 279 reroute mechanism involved (TE FRR, LFA/rLFA, MRT ...) when the 280 primary path uses hop-by-hop routing. The protection enabled by 281 fast-reroute is working perfectly, but ensures a protection, by 282 definition, only until the PLR has converged (as soon as the PLR has 283 converged, it replaces its FRR path by a new primary path). When 284 implementing FRR, a service provider wants to guarantee a very 285 limited loss of connectivity time. The previous example shows that 286 the benefit of FRR may be completely lost due to a transient 287 forwarding loop appearing when PLR has converged. Delaying FIB 288 updates after the IGP convergence may allow to keep the fast-reroute 289 path until the neighbors have converged and preserves the customer 290 traffic. 292 3.2. Network congestion 294 1 295 D ------ C 296 | | 297 1 | | 5 298 | | 299 A -- S ------ B 300 / | 1 301 F E 303 Figure 3 305 In the figure above, as presented in Section 2, when the link S-D 306 fails, a transient forwarding loop may appear between S and B for 307 destination D. The traffic on the S-B link will constantly increase 308 due to the looping traffic to D. Depending on the TTL of the 309 packets, the traffic rate destined to D, and the bandwidth of the 310 link, the S-B link may become congested in a few hundreds of 311 milliseconds and will stay congested until the loop is eliminated. 313 The congestion introduced by transient forwarding loops is 314 problematic as it can affect traffic that is not directly affected by 315 the failing network component. In the example, the congestion of the 316 S-B link will impact some customer traffic that is not directly 317 affected by the failure: e.g. A to B, F to B, E to B. Class of 318 service may mitigate the congestion for some traffic. However, some 319 traffic not directly affected by the failure will still be dropped as 320 a router is not able to distinguish the looping traffic from the 321 normally forwarded traffic. 323 4. Overview of the solution 325 This document defines a two-step convergence initiated by the router 326 detecting a failure and advertising the topological changes in the 327 IGP. This introduces a delay between the convergence of the local 328 router and the network wide convergence. 330 The proposed solution is limited to local link down events in order 331 to keep the solution simple. 333 This ordered convergence is similar to the ordered FIB proposed 334 defined in [RFC6976], but it is limited to only a "one hop" distance. 335 As a consequence, it is more simple and becomes a local-only feature 336 that does not require interoperability. This benefit comes at the 337 expense of eliminating transient forwarding loops involving the local 338 router. The proposed mechanism also reuses some concepts described 339 in [I-D.ietf-rtgwg-microloop-analysis]. 341 5. Specification 343 5.1. Definitions 345 This document will refer to the following existing IGP timers: 347 o LSP_GEN_TIMER: The delay used to batch multiple local events in 348 one single local LSP/LSA update. It is often associated with a 349 damping mechanism to slow down reactions by incrementing the timer 350 when multiple consecutive events are detected. 352 o SPF_DELAY: The delay between the first IGP event triggering a new 353 routing table computation and the start of that routing table 354 computation. It is often associated with a damping mechanism to 355 slow down reactions by incrementing the timer when the IGP becomes 356 unstable. As an example, [I-D.ietf-rtgwg-backoff-algo] defines a 357 standard SPF delay algorithm. 359 This document introduces the following new timer: 361 o ULOOP_DELAY_DOWN_TIMER: used to slow down the local node 362 convergence in case of link down events. 364 5.2. Current IGP reactions 366 Upon a change of the status of an adjacency/link, the existing 367 behavior of the router advertising the event is the following: 369 1. The Up/Down event is notified to the IGP. 371 2. The IGP processes the notification and postpones the reaction for 372 LSP_GEN_TIMER msec. 374 3. Upon LSP_GEN_TIMER expiration, the IGP updates its LSP/LSA and 375 floods it. 377 4. The SPF computation is scheduled in SPF_DELAY msec. 379 5. Upon SPF_DELAY timer expiration, the SPF is computed, then the 380 RIB and FIB are updated. 382 5.3. Local events 384 The mechanism described in this document assumes that there has been 385 a single link failure as seen by the IGP area/level. If this 386 assumption is violated (e.g. multiple links or nodes failed), then 387 standard IP convergence MUST be applied (as described in 388 Section 5.2). 390 To determine if the mechanism can be applicable or not, an 391 implementation SHOULD implement logic to correlate the protocol 392 messages (LSP/LSA) received during the SPF scheduling period in order 393 to determine the topology changes that occured. This is necessary as 394 multiple protocol messages may describe the same topology change and 395 a single protocol message may describe multiple topology changes. As 396 a consequence, determining a particular topology change MUST be 397 independent of the order of reception of those protocol messages. 398 How the logic works is left to the implementation. 400 Using this logic, if an implementation determines that the associated 401 topology change is a single local link failure, then the router MAY 402 use the mechanism described in this document, otherwise the standard 403 IP convergence MUST be used. 405 Example: 407 +--- E ----+--------+ 408 | | | 409 A ---- B -------- C ------ D 411 Figure 4 413 Let router B be the computing router when the link B-C fails. B 414 updates its local LSP/LSA describing the link B->C as down, C does 415 the same, and both start flooding their updated LSP/LSAs. During the 416 SPF_DELAY period, B and C learn all the LSPs/LSAs to consider. B 417 sees that C is flooding an advertisement that indicates that a link 418 is down, and B is the other end of that link. B determines that B 419 and C are describing the same single event. Since B receives no 420 other changes, B can determine that this is a local link failure and 421 may decide to activate the mechanism described in this document. 423 5.4. Local delay for link down 425 Upon an adjacency/link down event, this document introduces a change 426 in step 5 (Section 5.2) in order to delay the local convergence 427 compared to the network wide convergence. The new step 5 is 428 described below: 430 5. Upon SPF_DELAY timer expiration, the SPF is computed. If the 431 condition of a single local link-down event has been met, then an 432 update of the RIB and the FIB SHOULD be delayed for 433 ULOOP_DELAY_DOWN_TIMER msecs. Otherwise, the RIB and FIB SHOULD 434 be updated immediately. 436 If a new convergence occurs while ULOOP_DELAY_DOWN_TIMER is running, 437 ULOOP_DELAY_DOWN_TIMER is stopped and the RIB/FIB SHOULD be updated 438 as part of the new convergence event. 440 As a result of this addition, routers local to the failure will 441 converge slower than remote routers. Hence it SHOULD only be done 442 for a non-urgent convergence, such as for administrative de- 443 activation (maintenance) or when the traffic is protected by fast- 444 reroute. 446 6. Applicability 448 As previously stated, this mechanism only avoids the forwarding loops 449 on the links between the node local to the failure and its neighbors. 450 Forwarding loops may still occur on other links. 452 6.1. Applicable case: local loops 454 A ------ B ----- E 455 | / | 456 | / | 457 G---D------------C F All the links have a metric of 1 459 Figure 5 461 Let us consider the traffic from G to F. The primary path is 462 G->D->C->E->F. When link C-E fails, if C updates its forwarding 463 entry for F before D, a transient loop occurs. This is sub-optimal 464 as C has FRR enabled and it breaks the FRR forwarding while all 465 upstream routers are still forwarding the traffic to itself. 467 By implementing the mechanism defined in this document on C, when the 468 C-E link fails, C delays the update of its forwarding entry to F, in 469 order to allow some time for D to converge. FRR on C keeps 470 protecting the traffic during this period. When the timer expires on 471 C, its forwarding entry to F is updated. There is no transient 472 forwarding loop on the link C-D. 474 6.2. Non applicable case: remote loops 476 A ------ B ----- E --- H 477 | | 478 | | 479 G---D--------C ------F --- J ---- K 481 All the links have a metric of 1 except BE=15 483 Figure 6 485 Let us consider the traffic from G to K. The primary path is 486 G->D->C->F->J->K. When the C-F link fails, if C updates its 487 forwarding entry to K before D, a transient loop occurs between C and 488 D. 490 By implementing the mechanism defined in this document on C, when the 491 link C-F fails, C delays the update of its forwarding entry to K, 492 allowing time for D to converge. When the timer expires on C, its 493 forwarding entry to F is updated. There is no transient forwarding 494 loop between C and D. However, a transient forwarding loop may still 495 occur between D and A. In this scenario, this mechanism is not 496 enough to address all the possible forwarding loops. However, it 497 does not create additional traffic loss. Besides, in some cases 498 -such as when the nodes update their FIB in the following order C, A, 499 D, for example because the router A is quicker than D to converge- 500 the mechanism may still avoid the forwarding loop that would have 501 otherwise occurred. 503 7. Simulations 505 Simulations have been run on multiple service provider topologies. 507 +----------+------+ 508 | Topology | Gain | 509 +----------+------+ 510 | T1 | 71% | 511 | T2 | 81% | 512 | T3 | 62% | 513 | T4 | 50% | 514 | T5 | 70% | 515 | T6 | 70% | 516 | T7 | 59% | 517 | T8 | 77% | 518 +----------+------+ 520 Table 1: Number of Repair/Dst that may loop 522 We evaluated the efficiency of the mechanism on eight different 523 service provider topologies (different network size, design). The 524 benefit is displayed in the table above. The benefit is evaluated as 525 follows: 527 o We consider a tuple (link A-B, destination D, PLR S, backup 528 nexthop N) as a loop if upon link A-B failure, the flow from a 529 router S upstream from A (A could be considered as PLR also) to D 530 may loop due to convergence time difference between S and one of 531 his neighbors N. 533 o We evaluate the number of potential loop tuples in normal 534 conditions. 536 o We evaluate the number of potential loop tuples using the same 537 topological input but taking into account that S converges after 538 N. 540 o The gain is how many loops (both remote and local) we succeed to 541 suppress. 543 On topology 1, 71% of the transient forwarding loops created by the 544 failure of any link are prevented by implementing the local delay. 545 The analysis shows that all local loops are prevented and only remote 546 loops remain. 548 8. Deployment considerations 550 Transient forwarding loops have the following drawbacks: 552 o They limit FRR efficiency: even if FRR is activated within 50msec, 553 as soon as PLR has converged, the traffic may be affected by a 554 transient loop. 556 o They may impact traffic not directly affected by the failure (due 557 to link congestion). 559 This local delay proposal is a transient forwarding loop avoidance 560 mechanism (like OFIB). Even if it only addresses local transient 561 loops, the efficiency versus complexity comparison of the mechanism 562 makes it a good solution. It is also incrementally deployable with 563 incremental benefits, which makes it an attractive option both for 564 vendors to implement and service providers to deploy. Delaying the 565 convergence time is not an issue if we consider that the traffic is 566 protected during the convergence. 568 The proposed mechanism is limited to link down events. When a link 569 goes down, it eventually goes back up. As a consequence, with the 570 proposed mechanism deployed, only the link down event will be 571 protected against transient forwarding loops while the link up event 572 will not. If the operator wants to limit the impact of the transient 573 forwarding loops during the link up event, it should take care of 574 using specific procedures to bring the link back online. As 575 examples, the operator can decide to put back the link online out of 576 business hours or it can use some incremental metric changes to 577 prevent loops (as proposed in [RFC5715]). 579 9. Examples 581 We will consider the following figure for the associated examples : 583 D 584 1 | F----X 585 | 1 | 586 A ------ B 587 | | ^ 588 10 | | 5 | T 589 | | | 590 E--------C 591 | 1 592 1 | 593 S 595 Figure 7 597 The network above is considered to have a convergence time about 1 598 second, so ULOOP_DELAY_DOWN_TIMER will be adjusted to this value. We 599 also consider that FRR is running on each node. 601 9.1. Local link down 603 The table below describes the events and associated timing that 604 happens on router C and E when link B-C goes down. As C detects a 605 single local event corresponding to a link down (its LSP + LSP from B 606 received), it decides to apply the local delay down behavior and no 607 microloop is formed. 609 +-----------+-------------+------------------+----------------------+ 610 | Network | Time | Router C events | Router E events | 611 | condition | | | | 612 +-----------+-------------+------------------+----------------------+ 613 | S->D | | | | 614 | Traffic | | | | 615 | OK | | | | 616 | | | | | 617 | S->D | t0 | Link B-C fails | Link B-C fails | 618 | Traffic | | | | 619 | lost | | | | 620 | | | | | 621 | | t0+20msec | C detects the | | 622 | | | failure | | 623 | | | | | 624 | S->D | t0+40msec | C activates FRR | | 625 | Traffic | | | | 626 | OK | | | | 627 | | | | | 628 | | t0+50msec | C updates its | | 629 | | | local LSP/LSA | | 630 | | | | | 631 | | t0+60msec | C schedules SPF | | 632 | | | (100ms) | | 633 | | | | | 634 | | t0+67msec | C receives | | 635 | | | LSP/LSA from B | | 636 | | | | | 637 | | t0+70msec | C floods its | | 638 | | | local updated | | 639 | | | LSP/LSA | | 640 | | | | | 641 | | t0+87msec | | E receives LSP/LSA | 642 | | | | from C and schedules | 643 | | | | SPF (100ms) | 644 | | | | | 645 | | t0+117msec | | E floods LSP/LSA | 646 | | | | from C | 647 | | | | | 648 | | t0+160msec | C computes SPF | | 649 | | | | | 650 | | t0+165msec | C delays its | | 651 | | | RIB/FIB update | | 652 | | | (1 sec) | | 653 | | | | | 654 | | t0+193msec | | E computes SPF | 655 | | | | | 656 | | t0+199msec | | E starts updating | 657 | | | | its RIB/FIB | 658 | | | | | 659 | | t0+443msec | | E updates its | 660 | | | | RIB/FIB for D | 661 | | | | | 662 | | t0+470msec | | E convergence ends | 663 | | | | | 664 | | t0+1165msec | C starts | | 665 | | | updating its | | 666 | | | RIB/FIB | | 667 | | | | | 668 | | t0+1255msec | C updates its | | 669 | | | RIB/FIB for D | | 670 | | | | | 671 | | t0+1340msec | C convergence | | 672 | | | ends | | 673 +-----------+-------------+------------------+----------------------+ 675 Route computation event time scale 677 Similarly, upon B-C link down event, if LSP/LSA from B is received 678 before C detects the link failure, C will apply the route update 679 delay if the local detection is part of the same SPF run. 681 +-----------+-------------+------------------+----------------------+ 682 | Network | Time | Router C events | Router E events | 683 | condition | | | | 684 +-----------+-------------+------------------+----------------------+ 685 | S->D | | | | 686 | Traffic | | | | 687 | OK | | | | 688 | | | | | 689 | S->D | t0 | Link B-C fails | Link B-C fails | 690 | Traffic | | | | 691 | lost | | | | 692 | | | | | 693 | | t0+32msec | C receives | | 694 | | | LSP/LSA from B | | 695 | | | | | 696 | | t0+33msec | C schedules SPF | | 697 | | | (100ms) | | 698 | | | | | 699 | | t0+50msec | C detects the | | 700 | | | failure | | 701 | | | | | 702 | S->D | t0+55msec | C activates FRR | | 703 | Traffic | | | | 704 | OK | | | | 705 | | | | | 706 | | t0+55msec | C updates its | | 707 | | | local LSP/LSA | | 708 | | | | | 709 | | t0+70msec | C floods its | | 710 | | | local updated | | 711 | | | LSP/LSA | | 712 | | | | | 713 | | t0+87msec | | E receives LSP/LSA | 714 | | | | from C and schedules | 715 | | | | SPF (100ms) | 716 | | | | | 717 | | t0+117msec | | E floods LSP/LSA | 718 | | | | from C | 719 | | | | | 720 | | t0+160msec | C computes SPF | | 721 | | | | | 722 | | t0+165msec | C delays its | | 723 | | | RIB/FIB update | | 724 | | | (1 sec) | | 725 | | | | | 726 | | t0+193msec | | E computes SPF | 727 | | | | | 728 | | t0+199msec | | E starts updating | 729 | | | | its RIB/FIB | 730 | | | | | 731 | | t0+443msec | | E updates its | 732 | | | | RIB/FIB for D | 733 | | | | | 734 | | t0+470msec | | E convergence ends | 735 | | | | | 736 | | t0+1165msec | C starts | | 737 | | | updating its | | 738 | | | RIB/FIB | | 739 | | | | | 740 | | t0+1255msec | C updates its | | 741 | | | RIB/FIB for D | | 742 | | | | | 743 | | t0+1340msec | C convergence | | 744 | | | ends | | 745 +-----------+-------------+------------------+----------------------+ 747 Route computation event time scale 749 9.2. Local and remote event 751 The table below describes the events and associating timing that 752 happens on router C and E when link B-C goes down, in addition F-X 753 link will fail in the same time window. C will not apply the local 754 delay because a non local topology change is also received. 756 +-----------+------------+-----------------+------------------------+ 757 | Network | Time | Router C events | Router E events | 758 | condition | | | | 759 +-----------+------------+-----------------+------------------------+ 760 | S->D | | | | 761 | Traffic | | | | 762 | OK | | | | 763 | | | | | 764 | S->D | t0 | Link B-C fails | Link B-C fails | 765 | Traffic | | | | 766 | lost | | | | 767 | | | | | 768 | | t0+20msec | C detects the | | 769 | | | failure | | 770 | | | | | 771 | | t0+36msec | Link F-X fails | Link F-X fails | 772 | | | | | 773 | S->D | t0+40msec | C activates FRR | | 774 | Traffic | | | | 775 | OK | | | | 776 | | | | | 777 | | t0+50msec | C updates its | | 778 | | | local LSP/LSA | | 779 | | | | | 780 | | t0+54msec | C receives | | 781 | | | LSP/LSA from F | | 782 | | | and floods it | | 783 | | | | | 784 | | t0+60msec | C schedules SPF | | 785 | | | (100ms) | | 786 | | | | | 787 | | t0+67msec | C receives | | 788 | | | LSP/LSA from B | | 789 | | | | | 790 | | t0+69msec | | E receives LSP/LSA | 791 | | | | from F, floods it and | 792 | | | | schedules SPF (100ms) | 793 | | | | | 794 | | t0+70msec | C floods its | | 795 | | | local updated | | 796 | | | LSP/LSA | | 797 | | | | | 798 | | t0+87msec | | E receives LSP/LSA | 799 | | | | from C | 800 | | | | | 801 | | t0+117msec | | E floods LSP/LSA from | 802 | | | | C | 803 | | | | | 804 | | t0+160msec | C computes SPF | | 805 | | | | | 806 | | t0+165msec | C starts | | 807 | | | updating its | | 808 | | | RIB/FIB (NO | | 809 | | | DELAY) | | 810 | | | | | 811 | | t0+170msec | | E computes SPF | 812 | | | | | 813 | | t0+173msec | | E starts updating its | 814 | | | | RIB/FIB | 815 | | | | | 816 | S->D | t0+365msec | C updates its | | 817 | Traffic | | RIB/FIB for D | | 818 | lost | | | | 819 | | | | | 820 | S->D | t0+443msec | | E updates its RIB/FIB | 821 | Traffic | | | for D | 822 | OK | | | | 823 | | | | | 824 | | t0+450msec | C convergence | | 825 | | | ends | | 826 | | | | | 827 | | t0+470msec | | E convergence ends | 828 | | | | | 829 +-----------+------------+-----------------+------------------------+ 831 Route computation event time scale 833 9.3. Aborting local delay 835 The table below describes the events and associated timing that 836 happen on router C and E when link B-C goes down. In addition, we 837 consider what happens when F-X link fails during local delay of the 838 FIB update. C will first apply the local delay, but when the new 839 event happens, it will fall back to the standard convergence 840 mechanism without further delaying route insertion. In this example, 841 we consider a ULOOP_DELAY_DOWN_TIMER configured to 2 seconds. 843 +-----------+------------+-------------------+----------------------+ 844 | Network | Time | Router C events | Router E events | 845 | condition | | | | 846 +-----------+------------+-------------------+----------------------+ 847 | S->D | | | | 848 | Traffic | | | | 849 | OK | | | | 850 | | | | | 851 | S->D | t0 | Link B-C fails | Link B-C fails | 852 | Traffic | | | | 853 | lost | | | | 854 | | | | | 855 | | t0+20msec | C detects the | | 856 | | | failure | | 857 | | | | | 858 | S->D | t0+40msec | C activates FRR | | 859 | Traffic | | | | 860 | OK | | | | 861 | | | | | 862 | | t0+50msec | C updates its | | 863 | | | local LSP/LSA | | 864 | | | | | 865 | | t0+60msec | C schedules SPF | | 866 | | | (100ms) | | 867 | | | | | 868 | | t0+67msec | C receives | | 869 | | | LSP/LSA from B | | 870 | | | | | 871 | | t0+70msec | C floods its | | 872 | | | local updated | | 873 | | | LSP/LSA | | 874 | | | | | 875 | | t0+87msec | | E receives LSP/LSA | 876 | | | | from C and schedules | 877 | | | | SPF (100ms) | 878 | | | | | 879 | | t0+117msec | | E floods LSP/LSA | 880 | | | | from C | 881 | | | | | 882 | | t0+160msec | C computes SPF | | 883 | | | | | 884 | | t0+165msec | C delays its | | 885 | | | RIB/FIB update (2 | | 886 | | | sec) | | 887 | | | | | 888 | | t0+193msec | | E computes SPF | 889 | | | | | 890 | | t0+199msec | | E starts updating | 891 | | | | its RIB/FIB | 892 | | | | | 893 | | t0+254msec | Link F-X fails | Link F-X fails | 894 | | | | | 895 | | t0+300msec | C receives | | 896 | | | LSP/LSA from F | | 897 | | | and floods it | | 898 | | | | | 899 | | t0+303msec | C schedules SPF | | 900 | | | (200ms) | | 901 | | | | | 902 | | t0+312msec | E receives | | 903 | | | LSP/LSA from F | | 904 | | | and floods it | | 905 | | | | | 906 | | t0+313msec | E schedules SPF | | 907 | | | (200ms) | | 908 | | | | | 909 | | t0+502msec | C computes SPF | | 910 | | | | | 911 | | t0+505msec | C starts updating | | 912 | | | its RIB/FIB (NO | | 913 | | | DELAY) | | 914 | | | | | 915 | | t0+514msec | | E computes SPF | 916 | | | | | 917 | | t0+519msec | | E starts updating | 918 | | | | its RIB/FIB | 919 | | | | | 920 | S->D | t0+659msec | C updates its | | 921 | Traffic | | RIB/FIB for D | | 922 | lost | | | | 923 | | | | | 924 | S->D | t0+778msec | | E updates its | 925 | Traffic | | | RIB/FIB for D | 926 | OK | | | | 927 | | | | | 928 | | t0+781msec | C convergence | | 929 | | | ends | | 930 | | | | | 931 | | t0+810msec | | E convergence ends | 932 +-----------+------------+-------------------+----------------------+ 934 Route computation event time scale 936 10. Comparison with other solutions 938 As stated in Section 4, the proposed solution reuses some concepts 939 already introduced by other IETF proposals but tries to find a 940 tradeoff between efficiency and simplicity. This section tries to 941 compare behaviors of the solutions. 943 10.1. PLSN 945 PLSN ([I-D.ietf-rtgwg-microloop-analysis]) describes a mechanism 946 where each node in the network tries to avoid transient forwarding 947 loops upon a topology change by always keeping traffic on a loop-free 948 path for a defined duration (locked path to a safe neighbor). The 949 locked path may be the new primary nexthop, another neighbor, or the 950 old primary nexthop depending how the safety condition is satisfied. 952 PLSN does not solve all transient forwarding loops (see 953 [I-D.ietf-rtgwg-microloop-analysis] Section 4 for more details). 955 Our solution reuses some concept of PLSN but in a more simple 956 fashion: 958 o PLSN has three different behaviors: keep using old nexthop, use 959 new primary nexthop if it is safe, or use another safe nexthop, 960 while the proposed solution only has one: keep using the current 961 nexthop (old primary, or already activated FRR path). 963 o PLSN may cause some damage while using a safe nexthop which is not 964 the new primary nexthop in case the new safe nexthop does not 965 provide enough bandwidth (see [RFC7916]). This solution may not 966 experience this issue as the service provider may have control on 967 the FRR path being used preventing network congestion. 969 o PLSN applies to all nodes in a network (remote or local changes), 970 while the proposed mechanism applies only on the nodes connected 971 to the topology change. 973 10.2. OFIB 975 OFIB ([RFC6976]) describes a mechanism where the convergence of the 976 network upon a topology change is ordered in order to prevent 977 transient forwarding loops. Each router in the network must deduce 978 the failure type from the LSA/LSP received and computes/applies a 979 specific FIB update timer based on the failure type and its rank in 980 the network considering the failure point as root. 982 This mechanism allows to solve all the transient forwarding loop in a 983 network at the price of introducing complexity in the convergence 984 process that may require a strong monitoring by the service provider. 986 Our solution reuses the OFIB concept but limits it to the first hop 987 that experiences the topology change. As demonstrated, the mechanism 988 proposed in this document allows to solve all the local transient 989 forwarding loops that represents an high percentage of all the loops. 990 Moreover limiting the mechanism to one hop allows to keep the 991 network-wide convergence behavior. 993 11. Existing implementations 995 At this time, there are three different implementations of this 996 mechanism: CISCO IOS-XR, CISCO IOS-XE and Juniper JUNOS. The three 997 implementations have been tested in labs and demonstrated good 998 behavior in term of local micro-loop avoidance. The feature has also 999 been deployed in some live networks. No side effects have been 1000 found. 1002 12. Security Considerations 1004 This document does not introduce any change in term of IGP security. 1005 The operation is internal to the router. The local delay does not 1006 increase the number of attack vectors as an attacker could only 1007 trigger this mechanism if he already has be ability to disable or 1008 enable an IGP link. The local delay does not increase the negative 1009 consequences. If an attacker has the ability to disable or enable an 1010 IGP link, it can already harm the network by creating instability and 1011 harm the traffic by creating forwarding packet loss and forwarding 1012 loss for the traffic crossing that link. 1014 13. Acknowledgements 1016 We would like to thanks the authors of [RFC6976] for introducing the 1017 concept of ordered convergence: Mike Shand, Stewart Bryant, Stefano 1018 Previdi, and Olivier Bonaventure. 1020 14. IANA Considerations 1022 This document has no actions for IANA. 1024 15. References 1025 15.1. Normative References 1027 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1028 Requirement Levels", BCP 14, RFC 2119, 1029 DOI 10.17487/RFC2119, March 1997, 1030 . 1032 15.2. Informative References 1034 [I-D.ietf-rtgwg-backoff-algo] 1035 Decraene, B., Litkowski, S., Gredler, H., Lindem, A., 1036 Francois, P., and C. Bowers, "SPF Back-off algorithm for 1037 link state IGPs", draft-ietf-rtgwg-backoff-algo-05 (work 1038 in progress), May 2017. 1040 [I-D.ietf-rtgwg-microloop-analysis] 1041 Zinin, A., "Analysis and Minimization of Microloops in 1042 Link-state Routing Protocols", draft-ietf-rtgwg-microloop- 1043 analysis-01 (work in progress), October 2005. 1045 [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free 1046 Convergence", RFC 5715, DOI 10.17487/RFC5715, January 1047 2010, . 1049 [RFC6976] Shand, M., Bryant, S., Previdi, S., Filsfils, C., 1050 Francois, P., and O. Bonaventure, "Framework for Loop-Free 1051 Convergence Using the Ordered Forwarding Information Base 1052 (oFIB) Approach", RFC 6976, DOI 10.17487/RFC6976, July 1053 2013, . 1055 [RFC7916] Litkowski, S., Ed., Decraene, B., Filsfils, C., Raza, K., 1056 Horneffer, M., and P. Sarkar, "Operational Management of 1057 Loop-Free Alternates", RFC 7916, DOI 10.17487/RFC7916, 1058 July 2016, . 1060 Authors' Addresses 1062 Stephane Litkowski 1063 Orange 1065 Email: stephane.litkowski@orange.com 1067 Bruno Decraene 1068 Orange 1070 Email: bruno.decraene@orange.com 1071 Clarence Filsfils 1072 Cisco Systems 1074 Email: cfilsfil@cisco.com 1076 Pierre Francois 1077 Individual 1079 Email: pfrpfr@gmail.com