idnits 2.17.1 draft-ietf-rtgwg-backoff-algo-09.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year ** The document contains RFC2119-like boilerplate, but doesn't seem to mention RFC 2119. The boilerplate contains a reference [BCP14], but that reference does not seem to mention RFC 2119 either. -- The document date (February 27, 2018) is 2247 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) == Missing Reference: 'BCP14' is mentioned on line 39, but not defined == Outdated reference: A later version (-10) exists of draft-ietf-rtgwg-spf-uloop-pb-statement-06 Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group B. Decraene 3 Internet-Draft Orange 4 Intended status: Standards Track S. Litkowski 5 Expires: August 31, 2018 Orange Business Service 6 H. Gredler 7 RtBrick Inc 8 A. Lindem 9 Cisco Systems 10 P. Francois 12 C. Bowers 13 Juniper Networks, Inc. 14 February 27, 2018 16 SPF Back-off Delay algorithm for link state IGPs 17 draft-ietf-rtgwg-backoff-algo-09 19 Abstract 21 This document defines a standard algorithm to temporarily postpone or 22 'back-off' link-state IGP Shortest Path First (SPF) computations. 23 This reduces the computational load and churn on IGP nodes when 24 multiple temporally close network events trigger multiple SPF 25 computations. 27 Having one standard algorithm improves interoperability by reducing 28 the probability and/or duration of transient forwarding loops during 29 the IGP convergence when the IGP reacts to multiple temporally close 30 IGP events. 32 Requirements Language 34 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 35 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 36 "OPTIONAL" in this document are to be interpreted as described in 37 [BCP14] [RFC2119] [RFC8174] when, and only when, they appear in all 38 capitals, as shown here. 40 Status of This Memo 42 This Internet-Draft is submitted in full conformance with the 43 provisions of BCP 78 and BCP 79. 45 Internet-Drafts are working documents of the Internet Engineering 46 Task Force (IETF). Note that other groups may also distribute 47 working documents as Internet-Drafts. The list of current Internet- 48 Drafts is at https://datatracker.ietf.org/drafts/current/. 50 Internet-Drafts are draft documents valid for a maximum of six months 51 and may be updated, replaced, or obsoleted by other documents at any 52 time. It is inappropriate to use Internet-Drafts as reference 53 material or to cite them other than as "work in progress." 55 This Internet-Draft will expire on August 31, 2018. 57 Copyright Notice 59 Copyright (c) 2018 IETF Trust and the persons identified as the 60 document authors. All rights reserved. 62 This document is subject to BCP 78 and the IETF Trust's Legal 63 Provisions Relating to IETF Documents 64 (https://trustee.ietf.org/license-info) in effect on the date of 65 publication of this document. Please review these documents 66 carefully, as they describe your rights and restrictions with respect 67 to this document. Code Components extracted from this document must 68 include Simplified BSD License text as described in Section 4.e of 69 the Trust Legal Provisions and are provided without warranty as 70 described in the Simplified BSD License. 72 Table of Contents 74 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 75 2. High level goals . . . . . . . . . . . . . . . . . . . . . . 3 76 3. Definitions and parameters . . . . . . . . . . . . . . . . . 4 77 4. Principles of SPF delay algorithm . . . . . . . . . . . . . . 5 78 5. Specification of the SPF delay state machine . . . . . . . . 6 79 5.1. State Machine . . . . . . . . . . . . . . . . . . . . . . 6 80 5.2. State . . . . . . . . . . . . . . . . . . . . . . . . . . 7 81 5.3. Timers . . . . . . . . . . . . . . . . . . . . . . . . . 8 82 5.4. FSM Events . . . . . . . . . . . . . . . . . . . . . . . 8 83 6. Parameters . . . . . . . . . . . . . . . . . . . . . . . . . 10 84 7. Partial Deployment . . . . . . . . . . . . . . . . . . . . . 11 85 8. Impact on micro-loops . . . . . . . . . . . . . . . . . . . . 11 86 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 87 10. Security considerations . . . . . . . . . . . . . . . . . . . 11 88 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 12 89 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 12 90 12.1. Normative References . . . . . . . . . . . . . . . . . . 12 91 12.2. Informative References . . . . . . . . . . . . . . . . . 12 92 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 13 94 1. Introduction 96 Link state IGPs, such as IS-IS [ISO10589-Second-Edition], OSPF 97 [RFC2328] and OSPFv3 [RFC5340], perform distributed route computation 98 on all routers in the area/level. In order to have consistent 99 routing tables across the network, such distributed computation 100 requires that all routers have the same version of the network 101 topology (Link State DataBase (LSDB)) and perform their computation 102 essentially at the same time. 104 In general, when the network is stable, there is a desire to trigger 105 a new Shortest Path First (SPF) computation as soon as a failure is 106 detected in order to quickly route around the failure. However, when 107 the network is experiencing multiple failures over a short period of 108 time, there is a conflicting desire to limit the frequency of SPF 109 computations, which would allow a reduction in control plane 110 resources used by IGPs and all protocols/subsystems reacting on the 111 attendant route change, such as LDP [RFC5036], RSVP-TE [RFC3209], BGP 112 [RFC4271], Fast ReRoute computations (e.g., Loop Free Alternates 113 (LFA) [RFC5286]), FIB updates, etc. This also reduces network churn 114 and, in particular, reduces the side effects such as micro-loops 115 [RFC5715] that ensue during IGP convergence. 117 To allow for this, IGPs usually implement an SPF Back-off Delay 118 algorithm that postpones or backs-off the SPF computation. However, 119 different implementations have chosen different algorithms. Hence, 120 in a multi-vendor network, it's not possible to ensure that all 121 routers trigger their SPF computation after the same delay. This 122 situation increases the average and maximum differential delay 123 between routers completing their SPF computation. It also increases 124 the probability that different routers compute their FIBs based on 125 different LSDB versions. Both factors increase the probability and/ 126 or duration of micro-loops as discussed in Section 8. 128 To allow multi-vendor networks to have all routers delay their SPF 129 computations for the same duration, this document specifies a 130 standard algorithm. 132 2. High level goals 134 The high level goals of this algorithm are the following: 136 o Very fast convergence for a single event (e.g., link failure). 138 o Paced fast convergence for multiple temporally close IGP events 139 while IGP stability is considered acceptable. 141 o Delayed convergence when IGP stability is problematic. This will 142 allow the IGP and related processes to conserve resources during 143 the period of instability. 145 o Always try to avoid different SPF_DELAY Section 3 timer values 146 across different routers in the area/level. This requires 147 specific consideration as different routers may receive IGP 148 messages at different interval or even order, due to differences 149 both in the distance from the originator of the IGP event and in 150 flooding implementations. 152 3. Definitions and parameters 154 IGP events: The reception or origination of an IGP LSDB change 155 requiring a new routing table computation. Examples are a topology 156 change, a prefix change and a metric change on a link or prefix. 157 Note that locally triggering a routing table computation is not 158 considered as an IGP event since other IGP routers are unaware of 159 this occurrence. 161 Routing table computation: Computation of the routing table, by the 162 IGP implementation, using the IGP LSDB. No distinction is made 163 between the type of computation performed. e.g., full SPF, 164 incremental SPF, Partial Route Computation (PRC). The type of 165 computation is a local consideration. This document may 166 interchangeably use the terms routing table computation and SPF 167 computation. 169 SPF_DELAY: The delay between the first IGP event triggering a new 170 routing table computation and the start of that routing table 171 computation. It can take the following values: 173 INITIAL_SPF_DELAY: A very small delay to quickly handle a single 174 isolated link failure, e.g., 0 milliseconds. 176 SHORT_SPF_DELAY: A small delay to provide fast convergence in the 177 case of a single component failure (node, Shared Risk Link Group 178 (SRLG)..) that leads to multiple IGP events, e.g., 50-100 179 milliseconds. 181 LONG_SPF_DELAY: A long delay when the IGP is unstable, e.g., 2 182 seconds. Note that this allows the IGP network to stabilize. 184 TIME_TO_LEARN_INTERVAL: This is the maximum duration typically needed 185 to learn all the IGP events related to a single component failure 186 (e.g., router failure, SRLG failure), e.g., 1 second. It's mostly 187 dependent on failure detection time variation between all routers 188 that are adjacent to the failure. Additionally, it may depend on the 189 different IGP implementations/parameters across the network, related 190 to origination and flooding of their link state advertisements. 192 HOLDDOWN_INTERVAL: The time required with no received IGP events 193 before considering the IGP to be stable again and allowing the 194 SPF_DELAY to be restored to INITIAL_SPF_DELAY. e.g. a 195 HOLDDOWN_INTERVAL of 3 seconds. The HOLDDOWN_INTERVAL MUST be 196 defaulted and configured to be longer than the 197 TIME_TO_LEARN_INTERVAL. 199 4. Principles of SPF delay algorithm 201 For this first IGP event, we assume that there has been a single 202 simple change in the network which can be taken into account using a 203 single routing computation (e.g., link failure, prefix (metric) 204 change) and we optimize for very fast convergence, delaying the 205 routing computation by INITIAL_SPF_DELAY. Under this assumption, 206 there is no benefit in delaying the routing computation. In a 207 typical network, this is the most common type of IGP event. Hence, 208 it makes sense to optimize this case. 210 If subsequent IGP events are received in a short period of time 211 (TIME_TO_LEARN_INTERVAL), we then assume that a single component 212 failed, but that this failure requires the knowledge of multiple IGP 213 events in order for IGP routing to converge. Under this assumption, 214 we want fast convergence since this is a normal network situation. 215 However, there is a benefit in waiting for all IGP events related to 216 this single component failure so that the IGP can compute the post- 217 failure routing table in a single additional route computation. In 218 this situation, we delay the routing computation by SHORT_SPF_DELAY. 220 If IGP events are still received after TIME_TO_LEARN_INTERVAL from 221 the initial IGP event received in QUIET state Section 5.1, then the 222 network is presumably experiencing multiple independent failures. In 223 this case, while waiting for network stability, the computations are 224 delayed for a longer time represented by LONG_SPF_DELAY. This SPF 225 delay is kept until no IGP events are received for HOLDDOWN_INTERVAL. 227 Note that in order to increase the consistency network wide, the 228 algorithm uses a delay (TIME_TO_LEARN_INTERVAL) from the initial IGP 229 event, rather than the number of SPF computation performed. Indeed, 230 as all routers may receive the IGP events at different times, we 231 cannot assume that all routers will perform the same number of SPF 232 computations. For example, assuming that the SPF delay is 50 ms, 233 router R1 may receive 3 IGP events (E1, E2, E3) in those 50 ms and 234 hence will perform a single routing computation. While another 235 router R2 may only receive 2 events (E1, E2) in those 50 ms and hence 236 will schedule another routing computation when receiving E3. 238 5. Specification of the SPF delay state machine 240 This section specifies the finite state machine (FSM) intended to 241 control the timing of the execution of SPF calculations in response 242 to IGP events. 244 5.1. State Machine 246 The FSM is initialized to the QUIET state with all three timers 247 timers (SPF_TIMER, HOLDDOWN_TIMER, LEARN_TIMER) deactivated. 249 The events which may change the FSM states are an IGP event or the 250 expiration of one timer (SPF_TIMER, HOLDDOWN_TIMER, LEARN_TIMER). 252 The following diagram briefly describes the state transitions. 254 +-------------------+ 255 +---->| |<-------------------+ 256 | | QUIET | | 257 +-----| |<---------+ | 258 7: +-------------------+ | | 259 SPF_TIMER | | | 260 expiration | | | 261 | 1: IGP event | | 262 | | | 263 v | | 264 +-------------------+ | | 265 +---->| | | | 266 | | SHORT_WAIT |----->----+ | 267 +-----| | | 268 2: +-------------------+ 6: HOLDDOWN_TIMER | 269 IGP event | expiration | 270 8: SPF_TIMER | | 271 expiration | | 272 | 3: LEARN_TIMER | 273 | expiration | 274 | | 275 v | 276 +-------------------+ | 277 +---->| | | 278 | | LONG_WAIT |------------>-------+ 279 +-----| | 280 4: +-------------------+ 5: HOLDDOWN_TIMER 281 IGP event expiration 282 9: SPF_TIMER expiration 284 Figure 1: State Machine 286 5.2. State 288 The naming and semantics of each state corresponds directly to the 289 SPF delay used for IGP events received in that state. Three states 290 are defined: 292 QUIET: This is the initial state, when no IGP events have occurred 293 for at least HOLDDOWN_INTERVAL since the previous routing table 294 computation. The state is meant to handle link failures very 295 quickly. 297 SHORT_WAIT: State entered when an IGP event has been received in 298 QUIET state. This state is meant to handle single component failure 299 requiring multiple IGP events (e.g., node, SRLG). 301 LONG_WAIT: State reached after TIME_TO_LEARN_INTERVAL. In other 302 words, state reached after TIME_TO_LEARN_INTERVAL in state 303 SHORT_WAIT. This state is meant to handle multiple independent 304 component failures during periods of IGP instability. 306 5.3. Timers 308 SPF_TIMER: The FSM timer that uses the computed SPF delay. Upon 309 expiration, the Route Table Computation (as defined in Section 3) is 310 performed. 312 HOLDDOWN_TIMER: The FSM timer that is (re)started whan an IGP event 313 is received and set to HOLDDOWN_INTERVAL. Upon expiration, the FSM 314 is moved to the QUIET state. 316 LEARN_TIMER: The FSM timer that is started when an IGP event is 317 recevied while the FSM is in the QUIET state. Upon expiration, the 318 FSM is moved to the LONG_WAIT state. 320 5.4. FSM Events 322 This section describes the events and the actions performed in 323 response. 325 Transition 1: IGP event, while in QUIET state. 327 Actions on event 1: 329 o If SPF_TIMER is not already running, start it with value 330 INITIAL_SPF_DELAY. 332 o Start LEARN_TIMER with TIME_TO_LEARN_INTERVAL. 334 o Start HOLDDOWN_TIMER with HOLDDOWN_INTERVAL. 336 o Transition to SHORT_WAIT state. 338 Transition 2: IGP event, while in SHORT_WAIT. 340 Actions on event 2: 342 o Reset HOLDDOWN_TIMER to HOLDDOWN_INTERVAL. 344 o If SPF_TIMER is not already running, start it with value 345 SHORT_SPF_DELAY. 347 o Remain in current state. 349 Transition 3: LEARN_TIMER expiration. 351 Actions on event 3: 353 o Transition to LONG_WAIT state. 355 Transition 4: IGP event, while in LONG_WAIT. 357 Actions on event 4: 359 o Reset HOLDDOWN_TIMER to HOLDDOWN_INTERVAL. 361 o If SPF_TIMER is not already running, start it with value 362 LONG_SPF_DELAY. 364 o Remain in current state. 366 Transition 5: HOLDDOWN_TIMER expiration, while in LONG_WAIT. 368 Actions on event 5: 370 o Transition to QUIET state. 372 Transition 6: HOLDDOWN_TIMER expiration, while in SHORT_WAIT. 374 Actions on event 6: 376 o Deactivate LEARN_TIMER. 378 o Transition to QUIET state. 380 Transition 7: SPF_TIMER expiration, while in QUIET. 382 Actions on event 7: 384 o Compute SPF. 386 o Remain in current state. 388 Transition 8: SPF_TIMER expiration, while in SHORT_WAIT. 390 Actions on event 8: 392 o Compute SPF. 394 o Remain in current state. 396 Transition 9: SPF_TIMER expiration, while in LONG_WAIT. 398 Actions on event 9: 400 o Compute SPF. 402 o Remain in current state. 404 6. Parameters 406 All the parameters MUST be configurable at the protocol instance 407 granularity. They MAY be configurable at the area/level granularity. 408 All the delays (INITIAL_SPF_DELAY, SHORT_SPF_DELAY, LONG_SPF_DELAY, 409 TIME_TO_LEARN_INTERVAL, HOLDDOWN_INTERVAL) SHOULD be configurable at 410 the millisecond granularity. They MUST be configurable at least at 411 the tenth of second granularity. The configurable range for all the 412 parameters SHOULD at least be from 0 milliseconds to 60 seconds. 414 This document does not propose default values for the parameters 415 because these values are expected to be context dependent. 416 Implementations are free to propose their own default values. 417 However the HOLDDOWN_INTERVAL MUST be defaulted or configured to be 418 longer than the TIME_TO_LEARN_INTERVAL. 420 In order to satisfy the goals stated in Section 2, operators are 421 RECOMMENDED to configure delay intervals such that INITIAL_SPF_DELAY 422 <= SHORT_SPF_DELAY and SHORT_SPF_DELAY <= LONG_SPF_DELAY. 424 When setting (default) values, one should consider the customers and 425 their application requirements, the computational power of the 426 routers, the size of the network, and, in particular, the number of 427 IP prefixes advertised in the IGP, the frequency and number of IGP 428 events, the number of protocols reactions/computations triggered by 429 IGP SPF computation (e.g., BGP, PCEP, Traffic Engineering CSPF, Fast 430 ReRoute computations). 432 Note that some or all of these factors may change over the life of 433 the network. In case of doubt, it's RECOMMENDED that timer intervals 434 should be chosen conservatively (i.e., longer timer values). 436 For the standard algorithm to be effective in mitigating micro-loops, 437 it is RECOMMENDED that all routers in the IGP domain, or at least all 438 the routers in the same area/level, have exactly the same configured 439 values. 441 7. Partial Deployment 443 In general, the SPF Back-off Delay algorithm is only effective in 444 mitigating micro-loops if it is deployed, with the same parameters, 445 on all routers in the IGP domain or, at least, all routers in an IGP 446 area/level. The impact of partial deployment is dependent on the 447 particular event, topology, and the algorithm(s) used on other 448 routers in the IGP area/level. In cases where the previous SPF Back- 449 off Delay algorithm was implemented uniformly, partial deployment 450 will increase the frequency and duration of micro-loops. Hence, it 451 is RECOMMENDED that all routers in the IGP domain or at least within 452 the same area/level be migrated to the SPF algorithm described herein 453 at roughly the same time. 455 Note that this is not a new consideration as over times, network 456 operators have changed SPF delay parameters in order to accommodate 457 new customer requirements for fast convergence, as permitted by new 458 software and hardware. They may also have progressively replaced an 459 implementation with a given SPF Back-off Delay algorithm by another 460 implementation with a different one. 462 8. Impact on micro-loops 464 Micro-loops during IGP convergence are due to a non-synchronized or 465 non-ordered update of the forwarding information tables (FIB) 466 [RFC5715] [RFC6976] [I-D.ietf-rtgwg-spf-uloop-pb-statement]. FIBs 467 are installed after multiple steps such as flooding of the IGP event 468 across the network, SPF wait time, SPF computation, FIB distribution 469 across line cards, and FIB update. This document only addresses the 470 contribution from the SPF wait time. This standardized procedure 471 reduces the probability and/or duration of micro-loops when IGPs 472 experience multiple temporally close events. It does not prevent all 473 micro-loops. However, it is beneficial and is less complex and 474 costly to implement when compared to full solutions such as [RFC5715] 475 or [RFC6976]. 477 9. IANA Considerations 479 No IANA actions required. 481 10. Security considerations 483 The algorithm presented in this document does not compromise IGP 484 security. An attacker having the ability to generate IGP events 485 would be able to delay the IGP convergence time. The LONG_SPF_DELAY 486 state may help mitigate the effects of Denial-of-Service (DOS) 487 attacks generating many IGP events. 489 11. Acknowledgements 491 We would like to acknowledge Les Ginsberg, Uma Chunduri, Mike Shand 492 and Alexander Vainshtein for the discussions and comments related to 493 this document. 495 12. References 497 12.1. Normative References 499 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 500 Requirement Levels", BCP 14, RFC 2119, 501 DOI 10.17487/RFC2119, March 1997, 502 . 504 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 505 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 506 May 2017, . 508 12.2. Informative References 510 [I-D.ietf-rtgwg-spf-uloop-pb-statement] 511 Litkowski, S., Decraene, B., and M. Horneffer, "Link State 512 protocols SPF trigger and delay algorithm impact on IGP 513 micro-loops", draft-ietf-rtgwg-spf-uloop-pb-statement-06 514 (work in progress), January 2018. 516 [ISO10589-Second-Edition] 517 International Organization for Standardization, 518 "Intermediate system to Intermediate system intra-domain 519 routeing information exchange protocol for use in 520 conjunction with the protocol for providing the 521 connectionless-mode Network Service (ISO 8473)", ISO/ 522 IEC 10589:2002, Second Edition, Nov 2002. 524 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, 525 DOI 10.17487/RFC2328, April 1998, 526 . 528 [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., 529 and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP 530 Tunnels", RFC 3209, DOI 10.17487/RFC3209, December 2001, 531 . 533 [RFC4271] Rekhter, Y., Ed., Li, T., Ed., and S. Hares, Ed., "A 534 Border Gateway Protocol 4 (BGP-4)", RFC 4271, 535 DOI 10.17487/RFC4271, January 2006, 536 . 538 [RFC5036] Andersson, L., Ed., Minei, I., Ed., and B. Thomas, Ed., 539 "LDP Specification", RFC 5036, DOI 10.17487/RFC5036, 540 October 2007, . 542 [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for 543 IP Fast Reroute: Loop-Free Alternates", RFC 5286, 544 DOI 10.17487/RFC5286, September 2008, 545 . 547 [RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF 548 for IPv6", RFC 5340, DOI 10.17487/RFC5340, July 2008, 549 . 551 [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free 552 Convergence", RFC 5715, DOI 10.17487/RFC5715, January 553 2010, . 555 [RFC6976] Shand, M., Bryant, S., Previdi, S., Filsfils, C., 556 Francois, P., and O. Bonaventure, "Framework for Loop-Free 557 Convergence Using the Ordered Forwarding Information Base 558 (oFIB) Approach", RFC 6976, DOI 10.17487/RFC6976, July 559 2013, . 561 Authors' Addresses 563 Bruno Decraene 564 Orange 566 Email: bruno.decraene@orange.com 568 Stephane Litkowski 569 Orange Business Service 571 Email: stephane.litkowski@orange.com 573 Hannes Gredler 574 RtBrick Inc 576 Email: hannes@rtbrick.com 577 Acee Lindem 578 Cisco Systems 579 301 Midenhall Way 580 Cary, NC 27513 581 USA 583 Email: acee@cisco.com 585 Pierre Francois 587 Email: pfrpfr@gmail.com 589 Chris Bowers 590 Juniper Networks, Inc. 591 1194 N. Mathilda Ave. 592 Sunnyvale, CA 94089 593 US 595 Email: cbowers@juniper.net