RFC 8541
Impact of Shortest Path First (SPF) Trigger and Delay Strategies on IGP Micro-loops
RFC 8541 🎀 (part 1 of 4)
Okay so, the title block is giving main character energy 💅:
- Title: Impact of Shortest Path First (SPF) Trigger and Delay Strategies on IGP Micro-loops ✨
- Authors: S. Litkowski (Orange Business Service), B. Decraene (Orange), and M. Horneffer (Deutsche Telekom) 👑
- Category: Informational 🦋 (ISSN: 2070-1721)
- Date: March 2019 🌸
- Obsoletes / Updates: there's no Obsoletes or Updates line in the header, so this one doesn't obsolete or update anything 🧚
Abstract 💖
Bestie, a micro-loop is a packet-forwarding loop that can pop up transiently between two or more routers in a hop-by-hop packet-forwarding setup. Lowkey scary, right? 🙈
This doc looks at how using different link state IGP implementations in one network affects micro-loops. The main focus is the Shortest Path First (SPF) delay algorithm, but it also touches on how SPF trigger strategies play in. 🔥
Status of This Memo 🌈
This document is not an Internet Standards Track specification. It's published for informational purposes, so no standards vibes here, just info 🫶
It's a product of the Internet Engineering Task Force (IETF), and it reflects the consensus of the IETF community. It got public review and was approved for publication by the Internet Engineering Steering Group (IESG). Not every doc the IESG approves is a candidate for any level of Internet Standard. See Section 2 of RFC 7841 for more on that 🍓
If you want the current status, any errata, or a way to send feedback, check https://www.rfc-editor.org/info/rfc8541 ✨
Copyright Notice 💜
Copyright (c) 2019 IETF Trust and the persons identified as the document authors. All rights reserved. 🎀
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info), as in effect on the date of publication. Please actually read these, because they spell out your rights and restrictions for this document 🙏 Code Components pulled out of this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions. They come without warranty, as described in the Simplified BSD License 💅
Table of Contents 🦋
1. Introduction ....................................................3
2. Problem Statement ...............................................4
3. SPF Trigger Strategies ..........................................6
4. SPF Delay Strategies ............................................6
4.1. Two-Step SPF Delay .........................................7
4.2. Exponential Back-Off Delay .................................7
5. Mixing Strategies ...............................................9
6. Benefits of Standardized SPF Delay Behavior ....................13
7. Security Considerations ........................................14
8. IANA Considerations ............................................14
9. References .....................................................14
9.1. Normative References ......................................14
9.2. Informative References ....................................15
Acknowledgements ..................................................15
Authors' Addresses ................................................151. Introduction 🦋
Okay so, link state IGP protocols run on a topology database. The SPF algorithm runs on that database to find a consistent set of non-looping routing paths. That's the whole vibe ✨
Specs like IS-IS [RFC1195] propose some optimizations to the route computation (see Appendix C.1 of [RFC1195]). The catch is that not all implementations follow those non-mandatory optimizations 🙃
In this document, we call the events that lead to a new SPF computation based on the topology "SPF triggers" 💖
Link state IGP protocols, like OSPF [RFC2328] and IS-IS [RFC1195], use multiple timers to control router behavior during churn. Those timers are: SPF delay, Partial Route Computation (PRC) delay, Link State Packet (LSP) generation delay, LSP flooding delay, and LSP retransmission interval 🌸
Some of the values and behaviors of these timers are standardized in protocol specs, and some aren't. The SPF computation-related timers have generally stayed unspecified, which is lowkey wild 👀
Implementations are free to implement non-standardized timers in any way they like. For some standardized timers, implementations may offer dynamically adjusted timers to help control churn, instead of static configurable values 🧚
"SPF delay" refers to the timer in most implementations that specifies the required delay before running an SPF computation after an SPF trigger is received. This is the one we'll be talking about the most 💅
A micro-loop is a packet-forwarding loop that may occur transiently among two or more routers in a hop-by-hop packet-forwarding paradigm. These micro-loops form when two routers don't update their Forwarding Information Bases (FIBs) for a certain prefix at the same time. The micro-loop phenomenon is described in [MICROLOOP-LSRP] 🔁
The IETF has defined two micro-loop mitigation techniques. The mechanism in [RFC6976] hasn't been widely implemented, presumably because the technique is complicated. The mechanism in [RFC8333] has been implemented. However, it doesn't prevent all micro-loops that can occur for a given topology and failure scenario 😭
In multi-vendor networks, using different implementations of a link state protocol may favor micro-loop creation during convergence, because of discrepancies in timers. Service providers already know to use timers with similar values and behaviors across the whole network as a best practice. Sometimes that isn't possible, though, due to implementation limitations 🙈
So this document lays out reasons for service providers to have consistent implementation of link state protocols across vendors. In particular, it analyzes the impact of using different link state IGP implementations in a single network with regard to micro-loops. The analysis focuses on the SPF delay algorithm 🫶
[RFC8405] defines a solution that partially addresses this problem statement, and this document captures the reasoning behind that solution 🌈
2. Problem Statement 💅
S ---- E
| |
10 | | 10
| |
D ---- A
| 2
Px
Figure 1: Network Topology Experiencing Micro-loopsFigure 1 shows a small network made of four routers (S, D, E, and A). Router S mostly uses the SD link to reach the prefixes behind router D (named Px). When the SD link fails, IGP convergence kicks in. If S converges before E, S will forward the traffic to Px through E. But because E hasn't converged yet, E will loop the traffic right back to S, and boom, that's a micro-loop 😱
The micro-loop shows up because the nodes in a network converge asynchronously when an event happens 🌀
A few factors (or a combo of them) can raise the odds of a micro-loop showing up:
- Delay of failure notification: The bigger the time gap between E and S being told about the failure, the greater the chance a micro-loop may appear 📨
- SPF delay: Most implementations support a delay for the SPF computation so they can catch as many events as possible. If S uses an SPF delay timer of x ms, E uses an SPF delay timer of y ms, and x < y, then E would start converging after S, which leads to a potential micro-loop 🕰️
- SPF computation time: This is mostly a matter of CPU power and optimizations like incremental SPF. If S computes its SPF faster than E, there's a chance a micro-loop may appear. Today, CPUs are fast enough to treat SPF computation time as negligible (on the order of milliseconds in a large network) ⚡
- SPF computation ordering: An SPF trigger can be common to multiple IGP areas or levels (e.g., IS-IS Level 1 and Level 2), or to multiple address families with multi-topologies. There's no specified order for SPF computation today, and it's implementation dependent. In those scenarios, if the order of SPF computation done in S and E for each area, level, topology, or SPF algorithm is different, a micro-loop could appear 🔀
- RIB and FIB prefix insertion speed or ordering: This is highly dependent on the implementation 🧩
Even if all of these factors increase the probability of a micro-loop, the SPF delay plays a significant role, especially during churn. As the number of IGP events goes up, the delta between the SPF delay values used by routers becomes significant. In fact, it becomes the dominating factor, especially when one router increases its timer exponentially while another increases it in a smoother way 📈
Another important factor is the time to update the FIB. As of today, the total FIB update time is the major factor for IGP convergence. For micro-loops, though, what matters isn't the total time. It's the difference in installing the same prefix between nodes. The time to update the FIB may be the main part for the first iteration, but not for subsequent IGP events. Also, FIB update time is very implementation specific and difficult or impossible to standardize, while the SPF delay algorithm may be standardized 🧁
So this document focuses on analyzing SPF delay behavior and the associated triggers 💖
3. SPF Trigger Strategies ✨
Depending on the change advertised in the LSP or LSA (Link State Advertisement), the topology may or may not be affected. An implementation may skip running the SPF computation (and may only run an IP reachability computation instead) if the advertised change doesn't affect the topology 🦋
Different strategies can trigger the SPF computation:
- An implementation may always run a full SPF for any type of change.
- An implementation may run a full SPF only when required. For example, if a link fails, a local node will run an SPF for its local LSP update. If the LSP from the neighbor (describing the same failure) is received after SPF has started, the local node can decide that a new full SPF isn't required, since the topology hasn't changed 🧠
- If the topology doesn't change, an implementation may only recompute the IP reachability.
As noted in Section 1, SPF optimizations aren't mandatory in specifications. That's led to the implementation of different strategies, so every vendor is doing its own thing 🌈
4. SPF Delay Strategies 👑
Implementations of link state routing protocols use different strategies to delay SPF computation. The two most common SPF delay behaviors are the following:
- Two-step SPF delay
- Exponential back-off delay
These behaviors are explained in the following sections 🫶
4.1. Two-Step SPF Delay 🎀
okay so the SPF delay is controlled by four parameters, and they're honestly a whole vibe:
- rapid delay: how long to wait before running SPF after the first SPF trigger event 🏃♀️
- rapid runs: how many back-to-back SPF runs can use the rapid delay. Once that number is exceeded, the delay switches over to the slow delay value 💅
- slow delay: how long to wait before running an SPF 🐢
- wait time: how long to go without spotting any SPF trigger events before going back to the rapid delay ✨
Figure 2 shows how the SPF delay timer changes (using the two-step delay algorithm) when a bunch of events roll in. For this one, the parameters are rapid delay (RD) = 50 ms, rapid runs = 3, slow delay (SD) = 1 s, and wait time = 2 s. 🌸
SPF delay time
^
|
|
SD- | x xx x
|
|
|
RD- | x x x x
|
+---------------------------------> Events
| | | | || | |
< wait time >Figure 2: Two-Step SPF Delay Algorithm 🦋
4.2. Exponential Back-Off Delay 🧚
this one has two modes, fast mode and back-off mode, and it's giving "start chill, then get dramatic if things keep happening" 😭 In fast mode, the SPF delay is usually only delayed by a tiny amount of time (fast reaction ⚡). The moment an SPF computation runs in fast mode, the algorithm automatically hops over to back-off mode. (Just so we're clear, a single SPF run is authorized in fast mode 💜.) In back-off mode, the SPF delay grows exponentially with each run 📈. Once the network is stable again, the algorithm goes back to fast mode 🌈. It's managed by four parameters:
- first delay: how long to wait before running SPF. This one is only used when SPF is in fast mode 🏁.
- incremental delay: how long to wait before running SPF. This one is only used when SPF is in back-off mode, and it increases exponentially at each SPF run 🚀.
- maximum delay: the longest amount of time to wait before running SPF 🛑.
- wait time: how long to go without events before going back to fast mode 🫶.
Figure 3 shows how the SPF delay timer changes (using the exponential back-off delay algorithm) when multiple events come through. The parameters for this one are first delay (FD) = 50 ms, incremental delay (ID) = 50 ms, maximum delay (MD) = 1 s, and wait time = 2 s. 🍓
SPF delay time
^
MD- | xx x
|
|
|
|
|
| x
|
|
|
| x
|
FD- | x x x
ID |
+---------------------------------> Events
| | | | || | |
< wait time >
FM->BM -------------------->FMFigure 3: Exponential Back-Off Delay Algorithm 👑
5. Mixing Strategies 🌈
okay so bestie, this section is where we stop looking at each strategy on its own and see what happens when two routers are running different ones. spoiler: it's not pretty 💀
Figure 1 shows a packet flow from S to D. S uses optimized SPF triggering, so full SPF only runs when it's actually needed, plus two-step SPF delay with rapid delay = 150 ms, rapid runs = 3, and slow delay = 1 s. Since S's implementation is optimized, PRC is available to it. For PRC delay, we use the same timers as the SPF delay. E is doing its own thing: it uses an SPF trigger strategy that always computes a full SPF for any change, and it uses the exponential back-off strategy for SPF delay, with first delay = 150 ms, incremental delay = 150 ms, and maximum delay = 1 s. two routers, two vibes 🙈
Let's walk through this sequence of events:
- t0=0 ms: A prefix is declared down in the network. This event happens at time=0.
- 200 ms: The prefix is declared up.
- 400 ms: The prefix is declared down in the network.
- 1000 ms: S-D link fails.
Here's the timeline, step by step:
+---------+-------------------+------------------+------------------+
| Time | Network Event | Router S Events | Router E Events |
+---------+-------------------+------------------+------------------+
| t0=0 | Prefix DOWN | | |
| 10 ms | | Schedule PRC (in | Schedule SPF (in |
| | | 150 ms) | 150 ms) |
| | | | |
| | | | |
| 160 ms | | PRC starts | SPF starts |
| 161 ms | | PRC ends | |
| 162 ms | | RIB/FIB starts | |
| 163 ms | | | SPF ends |
| 164 ms | | | RIB/FIB starts |
| 175 ms | | RIB/FIB ends | |
| 178 ms | | | RIB/FIB ends |
| | | | |
| 200 ms | Prefix UP | | |
| 212 ms | | Schedule PRC (in | |
| | | 150 ms) | |
| 214 ms | | | Schedule SPF (in |
| | | | 150 ms) |
| | | | |
| | | | |
| 370 ms | | PRC starts | |
| 372 ms | | PRC ends | |
| 373 ms | | | SPF starts |
| 373 ms | | RIB/FIB starts | |
| 375 ms | | | SPF ends |
| 376 ms | | | RIB/FIB starts |
| 383 ms | | RIB/FIB ends | |
| 385 ms | | | RIB/FIB ends |
| | | | |
| 400 ms | Prefix DOWN | | |
| 410 ms | | Schedule PRC (in | Schedule SPF (in |
| | | 300 ms) | 300 ms) |
| | | | |
| | | | |
| | | | |
| | | | |
| 710 ms | | PRC starts | SPF starts |
| 711 ms | | PRC ends | |
| 712 ms | | RIB/FIB starts | |
| 713 ms | | | SPF ends |
| 714 ms | | | RIB/FIB starts |
| 716 ms | | RIB/FIB ends | RIB/FIB ends |
| | | | |
| 1000 ms | S-D link DOWN | | |
| 1010 ms | | Schedule SPF (in | Schedule SPF (in |
| | | 150 ms) | 600 ms) |
| | | | |
| | | | |
| 1160 ms | | SPF starts | |
| 1161 ms | | SPF ends | |
| 1162 ms | Micro-loop may | RIB/FIB starts | |
| | start from here | | |
| 1175 ms | | RIB/FIB ends | |
| | | | |
| | | | |
| | | | |
| | | | |
| 1612 ms | | | SPF starts |
| 1615 ms | | | SPF ends |
| 1616 ms | | | RIB/FIB starts |
| 1626 ms | Micro-loop ends | | RIB/FIB ends |
+---------+-------------------+------------------+------------------+
Table 1: Route Computation When S and E Use Different Behaviors and
Multiple Events AppearNow the tea ☕ In Table 1, the two routers' SPF delay values get totally out of sync with each other because of all the different types of events that stack up. That misalignment is what creates the micro-loops. 😭
It's not only a multi-event problem, though. The same issue can show up with just one type of event, as you can see here:
+---------+-------------------+------------------+------------------+
| Time | Network Event | Router S Events | Router E Events |
+---------+-------------------+------------------+------------------+
| t0=0 | Link DOWN | | |
| 10 ms | | Schedule SPF (in | Schedule SPF (in |
| | | 150 ms) | 150 ms) |
| | | | |
| | | | |
| 160 ms | | SPF starts | SPF starts |
| 161 ms | | SPF ends | |
| 162 ms | | RIB/FIB starts | |
| 163 ms | | | SPF ends |
| 164 ms | | | RIB/FIB starts |
| 175 ms | | RIB/FIB ends | |
| 178 ms | | | RIB/FIB ends |
| | | | |
| 200 ms | Link DOWN | | |
| 212 ms | | Schedule SPF (in | |
| | | 150 ms) | |
| 214 ms | | | Schedule SPF (in |
| | | | 150 ms) |
| | | | |
| | | | |
| 370 ms | | SPF starts | |
| 372 ms | | SPF ends | |
| 373 ms | | | SPF starts |
| 373 ms | | RIB/FIB starts | |
| 375 ms | | | SPF ends |
| 376 ms | | | RIB/FIB starts |
| 383 ms | | RIB/FIB ends | |
| 385 ms | | | RIB/FIB ends |
| | | | |
| 400 ms | Link DOWN | | |
| 410 ms | | Schedule SPF (in | Schedule SPF (in |
| | | 150 ms) | 300 ms) |
| | | | |
| | | | |
| 560 ms | | SPF starts | |
| 561 ms | | SPF ends | |
| 562 ms | Micro-loop may | RIB/FIB starts | |
| | start from here | | |
| 568 ms | | RIB/FIB ends | |
| | | | |
| | | | |
| 710 ms | | | SPF starts |
| 713 ms | | | SPF ends |
| 714 ms | | | RIB/FIB starts |
| 716 ms | Micro-loop ends | | RIB/FIB ends |
| | | | |
| 1000 ms | Link DOWN | | |
| 1010 ms | | Schedule SPF (in | Schedule SPF (in |
| | | 1 s) | 600 ms) |
| | | | |
| | | | |
| | | | |
| | | | |
| 1612 ms | | | SPF starts |
| 1615 ms | | | SPF ends |
| 1616 ms | Micro-loop may | | RIB/FIB starts |
| | start from here | | |
| 1626 ms | | | RIB/FIB ends |
| | | | |
| | | | |
| | | | |
| | | | |
| 2012 ms | | SPF starts | |
| 2014 ms | | SPF ends | |
| 2015 ms | | RIB/FIB starts | |
| 2025 ms | Micro-loop ends | RIB/FIB ends | |
| | | | |
| | | | |
+---------+-------------------+------------------+------------------+
Table 2: Route Computation upon Multiple Link Down Events When S and
E Use Different BehaviorsThe big takeaway: even when the events are all the same kind, two routers using different behaviors can drift apart and leave the door open for micro-loops. so mixing strategies is not it, bestie 🫶
6. Benefits of Standardized SPF Delay Behavior ✨
okay so Table 3 runs on the exact same event timeline as Table 1 🎀 (same drama, same cast) and the big takeaway is that a standardized SPF delay should give you fewer and/or shorter micro-loops 💅 ngl that's the whole glow-up.
+---------+-------------------+------------------+------------------+
| Time | Network Event | Router S Events | Router E Events |
+---------+-------------------+------------------+------------------+
| t0=0 | Prefix DOWN | | |
| 10 ms | | Schedule PRC (in | Schedule PRC (in |
| | | 150 ms) | 150 ms) |
| | | | |
| | | | |
| 160 ms | | PRC starts | PRC starts |
| 161 ms | | PRC ends | |
| 162 ms | | RIB/FIB starts | PRC ends |
| 163 ms | | | RIB/FIB starts |
| 175 ms | | RIB/FIB ends | |
| 176 ms | | | RIB/FIB ends |
| | | | |
| 200 ms | Prefix UP | | |
| 212 ms | | Schedule PRC (in | |
| | | 150 ms) | |
| 213 ms | | | Schedule PRC (in |
| | | | 150 ms) |
| | | | |
| | | | |
| 370 ms | | PRC starts | PRC starts |
| 372 ms | | PRC ends | |
| 373 ms | | RIB/FIB starts | PRC ends |
| 374 ms | | | RIB/FIB starts |
| 383 ms | | RIB/FIB ends | |
| 384 ms | | | RIB/FIB ends |
| | | | |
| 400 ms | Prefix DOWN | | |
| 410 ms | | Schedule PRC (in | Schedule PRC (in |
| | | 300 ms) | 300 ms) |
| | | | |
| | | | |
| | | | |
| | | | |
| 710 ms | | PRC starts | PRC starts |
| 711 ms | | PRC ends | PRC ends |
| 712 ms | | RIB/FIB starts | |
| 713 ms | | | RIB/FIB starts |
| 716 ms | | RIB/FIB ends | RIB/FIB ends |
| | | | |
| 1000 ms | S-D link DOWN | | |
| 1010 ms | | Schedule SPF (in | Schedule SPF (in |
| | | 150 ms) | 150 ms) |
| | | | |
| | | | |
| 1160 ms | | SPF starts | |
| 1161 ms | | SPF ends | SPF starts |
| 1162 ms | Micro-loop may | RIB/FIB starts | SPF ends |
| | start from here | | |
| 1163 ms | | | RIB/FIB starts |
| 1175 ms | | RIB/FIB ends | |
| 1177 ms | Micro-loop ends | | RIB/FIB ends |
+---------+-------------------+------------------+------------------+
Table 3: Route Computation When S and E Use the Same Standardized
Behaviorso here's the tea ☕ other stuff can totally affect micro-loops too, like how much computing power a router has and its flooding timers 🧚 (we're not ignoring those, bestie). In every example in this doc that compares router S and router E's SPF timers, router E is a little bit slower than router S 🐢. That means micro-loops can still show up even when both S and E use a shared standardized SPF behavior 😭. Still, the hope is that once implementations of the SPF delay line up, service providers can cut down on how many micro-loops happen and how long they last 🌈✨.
7. Security Considerations 🔒
Okay, the security section is giving empty 💀 because this document does not introduce any security considerations. Nothing new to worry about here, periodt 🫶.
8. IANA Considerations 🦋
No vibes for IANA here: this document has no actions for IANA 🌸.
9. References 📚
9.1. Normative References
[RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and
dual environments", RFC 1195, DOI 10.17487/RFC1195,
December 1990, <https://www.rfc-editor.org/info/rfc1195>.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
DOI 10.17487/RFC2328, April 1998,
<https://www.rfc-editor.org/info/rfc2328>.
[RFC8405] Decraene, B., Litkowski, S., Gredler, H., Lindem, A.,
Francois, P., and C. Bowers, "Shortest Path First (SPF)
Back-Off Delay Algorithm for Link-State IGPs", RFC 8405,
DOI 10.17487/RFC8405, June 2018,
<https://www.rfc-editor.org/info/rfc8405>.9.2. Informative References
[MICROLOOP-LSRP]
Zinin, A., "Analysis and Minimization of Microloops in
Link-state Routing Protocols", Work in Progress,
draft-ietf-rtgwg-microloop-analysis-01, October 2005.
[RFC6976] Shand, M., Bryant, S., Previdi, S., Filsfils, C.,
Francois, P., and O. Bonaventure, "Framework for Loop-Free
Convergence Using the Ordered Forwarding Information Base
(oFIB) Approach", RFC 6976, DOI 10.17487/RFC6976, July
2013, <https://www.rfc-editor.org/info/rfc6976>.
[RFC8333] Litkowski, S., Decraene, B., Filsfils, C., and P.
Francois, "Micro-loop Prevention by Introducing a Local
Convergence Delay", RFC 8333, DOI 10.17487/RFC8333, March
2018, <https://www.rfc-editor.org/info/rfc8333>.Acknowledgements 💜
Huge thanks to Mike Shand and Chris Bowers, who gave the authors useful comments 🙌.
Authors' Addresses 🎀
Stephane Litkowski Orange Business Service
Email: stephane.litkowski@orange.com
Bruno Decraene Orange
Email: bruno.decraene@orange.com
Martin Horneffer Deutsche Telekom
Email: martin.horneffer@telekom.de
📦 where this page comes from
- ietf: rfc8541 2019-03
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms