RFC 8405

Shortest Path First (SPF) Back-Off Delay Algorithm for Link-State IGPs

📅 published June 2018, from ietf

Okay bestie, the title block is giving Standards Track 👑 so this is the real deal. It's from the IETF, dated June 2018, ISSN 2070-1721. The authors are B. Decraene and S. Litkowski (Orange and Orange Business Service), H. Gredler (RtBrick Inc.), A. Lindem (Cisco Systems), P. Francois (no affiliation shown in this block), and C. Bowers (Juniper Networks, Inc.). It doesn't obsolete or update any other RFC 🎀.

Abstract ✨

This document defines a standard algorithm that temporarily postpones, or "backs off," link-state IGP Shortest Path First (SPF) computations 🦋. The point is to cut down on computational load and churn on IGP nodes when several network events happen close together and each one would otherwise trigger its own SPF computation.

Having one standard algorithm is the glow-up for interoperability 💅. It lowers the probability and/or duration of transient forwarding loops during IGP convergence when the IGP reacts to multiple IGP events that are close in time.

Status of This Memo 🌸

This is an Internet Standards Track document.

It's a product of the Internet Engineering Task Force (IETF), so it reflects the consensus of the IETF community. It got public review and was approved for publication by the Internet Engineering Steering Group (IESG). For more on Internet Standards, check Section 2 of RFC 7841.

For the current status, any errata, and how to send feedback, go to https://www.rfc-editor.org/info/rfc8405.

Copyright (c) 2018 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) in effect on the date of publication. Read these carefully, 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, and they come without warranty as described in the Simplified BSD License.

Table of Contents 🍓

1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
  1.1.  Requirements Language . . . . . . . . . . . . . . . . . .   3
2.  High-Level Goals  . . . . . . . . . . . . . . . . . . . . . .   3
3.  Definitions and Parameters  . . . . . . . . . . . . . . . . .   4
4.  Principles of the SPF Delay Algorithm . . . . . . . . . . . .   5
5.  Specification of the SPF Delay State Machine  . . . . . . . .   6
  5.1.  State Machine . . . . . . . . . . . . . . . . . . . . . .   6
  5.2.  States  . . . . . . . . . . . . . . . . . . . . . . . . .   7
  5.3.  Timers  . . . . . . . . . . . . . . . . . . . . . . . . .   7
  5.4.  FSM Events  . . . . . . . . . . . . . . . . . . . . . . .   7
6.  Parameters  . . . . . . . . . . . . . . . . . . . . . . . . .   9
7.  Partial Deployment  . . . . . . . . . . . . . . . . . . . . .  10
8.  Impact on Micro-loops . . . . . . . . . . . . . . . . . . . .  11
9.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  11
10. Security Considerations . . . . . . . . . . . . . . . . . . .  11
11. References  . . . . . . . . . . . . . . . . . . . . . . . . .  11
  11.1.  Normative References . . . . . . . . . . . . . . . . . .  11
  11.2.  Informative References . . . . . . . . . . . . . . . . .  11
Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . .  13
Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  13

1. Introduction 💅

Okay so link-state IGPs like IS-IS [ISO10589], OSPF [RFC2328], and OSPFv3 [RFC5340] do distributed route computation on every router in the area/level 🌈. For routing tables to be consistent across the network, every router needs the same version of the topology (the Link-State Database (LSDB)) and has to do its computation more or less at the same time. That's the vibe.

When the network is stable, everyone wants a new SPF computation the instant a failure is detected, so traffic can route around it fast ⚡. But if the network is hit with several failures in a short window, there's a conflicting desire to limit how often SPF runs. That saves control plane resources for the IGP and for everything else reacting to the route change, like LDP [RFC5036], RSVP-TE [RFC3209], BGP [RFC4271], Fast Reroute computations (e.g., Loop-Free Alternates (LFAs) [RFC5286]), FIB updates, and so on. It also cuts down on network churn and, in particular, on side effects like micro-loops [RFC5715] that show up during IGP convergence 🙈.

IGPs usually have an SPF Back-Off Delay algorithm to postpone or back off the SPF computation 🦋. The problem is that different implementations picked different algorithms. So in a multi-vendor network, you can't guarantee that every router triggers its SPF after the same delay 😭. That makes the average and maximum differential delay between routers finishing their SPF computations bigger. It also makes it more likely that different routers compute their FIBs from different LSDB versions. Both of those raise the probability and/or duration of micro-loops, which Section 8 digs into.

This document specifies a standard algorithm so multi-vendor networks can have all routers delay their SPF computations for the same duration 🫶.

1.1. Requirements Language 🎀

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.

2. High-Level Goals 🎯

The goals for this algorithm, bestie, are these:

  • very fast convergence for a single event (e.g., link failure),
  • paced fast convergence for multiple temporally close IGP events while IGP stability is considered acceptable,
  • delayed convergence when IGP stability is problematic (this lets the IGP and related processes conserve resources during the period of instability), and
  • avoidance of having different SPF_DELAY timer values (Section 3) across different routers in the area/level. This needs special thought, because different routers may receive IGP messages at different intervals, or even in different orders, due to differences both in the distance from the originator of the IGP event and in flooding implementations 🌸.

3. Definitions and Parameters 📖

Here are the key terms, iykyk 🧚.

IGP event: The reception or origination of an IGP LSDB change that requires a new routing table computation. Some examples are a topology change, a prefix change, and a metric change on a link or prefix. Note that locally triggering a routing table computation doesn't count as an IGP event, since other IGP routers don't know it happened 🙈.

Routing table computation, in this document, is scoped to the IGP. So it's the computation of the IGP RIB, done by the IGP, using the IGP LSDB. No distinction is made between types of computation, e.g., full SPF, incremental SPF, or Partial Route Computation (PRC). The type of computation is a local consideration. This document may interchangeably use the terms "routing table computation" and "SPF computation" 💜.

SPF_DELAY: The delay between the first IGP event that triggers a new routing table computation and the start of that computation. It can take the following values:

  • INITIAL_SPF_DELAY: A very small delay to quickly handle a single isolated link failure, e.g., 0 milliseconds.
  • SHORT_SPF_DELAY: A small delay to provide fast convergence when a single component failure (such as a node failure or Shared Risk Link Group (SRLG) failure) leads to multiple IGP events, e.g., 50-100 milliseconds.
  • LONG_SPF_DELAY: A long delay when the IGP is unstable, e.g., 2 seconds. Note that this lets the IGP network stabilize 😌.

TIME_TO_LEARN_INTERVAL: This is the maximum duration typically needed to learn all the IGP events related to a single component failure (such as router failure or SRLG failure), e.g., 1 second. It mostly depends on the variation in failure detection time across all routers adjacent to the failure. It may also depend on the different IGP implementations and parameters across the network and how they relate to the origination and flooding of link state advertisements 🍓.

HOLDDOWN_INTERVAL: The time required with no received IGP event before the IGP is considered stable again and SPF_DELAY is allowed to be restored to INITIAL_SPF_DELAY, e.g., a HOLDDOWN_INTERVAL of 3 seconds. The HOLDDOWN_INTERVAL MUST be defaulted or configured to be longer than the TIME_TO_LEARN_INTERVAL 🔥.

4. Principles of the SPF Delay Algorithm ✨

Okay so for the first IGP event, we're assuming there was ONE simple change in the network, like a link failure or a prefix metric change, that a single routing computation can handle 🦋. So we optimize for super fast convergence by holding off the initial routing computation for a tiny interval, INITIAL_SPF_DELAY. Waiting wouldn't buy you anything in this case, and it's the most common kind of IGP event in a typical network, so it's giving "optimize this first" 💅.

If more IGP events show up within a short window (TIME_TO_LEARN_INTERVAL), we assume a single component failed, but that failure needs several IGP events before routing can converge. That's still a normal situation, so we still want speed 🏃‍♀️. But waiting is worth it here, because if you collect all the events for that one failure, the IGP can compute the post-failure routing table in a single extra route computation 🧩. In this situation, we delay the routing computation by SHORT_SPF_DELAY.

If IGP events are still coming in after TIME_TO_LEARN_INTERVAL has passed since the initial event received in QUIET state (see Section 5.1), it's presumably multiple independent failures 😭. While the network is trying to settle, the computations get delayed for a longer time, LONG_SPF_DELAY. This SPF delay stays in use until no IGP events are received for HOLDDOWN_INTERVAL.

Quick note on consistency 🫶: the algorithm measures a time window (TIME_TO_LEARN_INTERVAL) from the initial IGP event, NOT the number of SPF computations performed. Why? Because routers don't all get the IGP events at the same time, so we can't assume they'll all run the same number of SPF computations.

Here's the example. Say the SPF delay is 50 milliseconds:

  • Router R1 receives three IGP events (E1, E2, E3) within those 50 milliseconds, so it performs a single routing computation.
  • Router R2 only receives two events (E1, E2) within those 50 milliseconds, so it schedules another routing computation when it receives E3.

Two routers, two different counts, same algorithm, and that's the whole point 💖.

5. Specification of the SPF Delay State Machine 🧠

This section specifies the Finite State Machine (FSM) that controls the timing of SPF calculations in response to IGP events. It's the rulebook for the whole vibe. 📋

5.1. State Machine

The FSM starts in the QUIET state with all three timers (SPF_TIMER, HOLDDOWN_TIMER, and LEARN_TIMER) deactivated 🌸.

The events that may change the FSM states are an IGP event or the expiration of one timer (SPF_TIMER, HOLDDOWN_TIMER, or LEARN_TIMER).

Here's a quick picture of the state transitions 👀:

                     +-------------------+
               +---->|                   |<-------------------+
               |     |      QUIET        |                    |
               +-----|                   |<---------+         |
           7:        +-------------------+          |         |
           SPF_TIMER           |                    |         |
           expiration          |                    |         |
                               | 1: IGP event       |         |
                               |                    |         |
                               v                    |         |
                     +-------------------+          |         |
               +---->|                   |          |         |
               |     |    SHORT_WAIT     |----->----+         |
               +-----|                   |                    |
           2:        +-------------------+  6: HOLDDOWN_TIMER |
           IGP event           |               expiration     |
           8: SPF_TIMER        |                              |
              expiration       |                              |
                               | 3: LEARN_TIMER               |
                               |    expiration                |
                               |                              |
                               v                              |
                     +-------------------+                    |
               +---->|                   |                    |
               |     |     LONG_WAIT     |------------>-------+
               +-----|                   |
           4:        +-------------------+  5: HOLDDOWN_TIMER
           IGP event                           expiration
           9: SPF_TIMER expiration

Figure 1: State Machine

5.2. States

The naming and semantics of each state line up directly with the SPF delay used for IGP events received in that state. There are three states 🎀:

  • QUIET: This is the initial state, when no IGP events have occurred for at least HOLDDOWN_INTERVAL since the last routing table computation. It's built to handle link failures super quickly ⚡.
  • SHORT_WAIT: This is the state entered when an IGP event has been received in QUIET state. It's meant to handle a single component failure that needs multiple IGP events (e.g., node, SRLG) 🧩.
  • LONG_WAIT: This is the state reached after TIME_TO_LEARN_INTERVAL in state SHORT_WAIT. It's meant to handle multiple independent component failures during periods of IGP instability 🌪️.

5.3. Timers

  • SPF_TIMER: This is the FSM timer that uses the computed SPF delay. When it expires, the routing table computation (as defined in Section 3) is performed 🏁.
  • HOLDDOWN_TIMER: This is the FSM timer that is (re)started when an IGP event is received and set to HOLDDOWN_INTERVAL. When it expires, the FSM moves to the QUIET state 😌.
  • LEARN_TIMER: This is the FSM timer that starts when an IGP event is received while the FSM is in the QUIET state. When it expires, the FSM moves to the LONG_WAIT state ⏰.

5.4. FSM Events

This section describes the events and the actions taken in response. Let's go through them one by one 💅.

Transition 1: IGP event while in QUIET state

Actions on event 1:

  • If SPF_TIMER is not already running, start it with value INITIAL_SPF_DELAY.
  • Start LEARN_TIMER with TIME_TO_LEARN_INTERVAL.
  • Start HOLDDOWN_TIMER with HOLDDOWN_INTERVAL.
  • Transition to SHORT_WAIT state.

Transition 2: IGP event while in SHORT_WAIT

Actions on event 2:

  • Reset HOLDDOWN_TIMER to HOLDDOWN_INTERVAL.
  • If SPF_TIMER is not already running, start it with value SHORT_SPF_DELAY.
  • Remain in current state.

Transition 3: LEARN_TIMER expiration

Actions on event 3:

  • Transition to LONG_WAIT state.

Transition 4: IGP event while in LONG_WAIT

Actions on event 4:

  • Reset HOLDDOWN_TIMER to HOLDDOWN_INTERVAL.
  • If SPF_TIMER is not already running, start it with value LONG_SPF_DELAY.
  • Remain in current state.

Transition 5: HOLDDOWN_TIMER expiration while in LONG_WAIT

Actions on event 5:

  • Transition to QUIET state.

Transition 6: HOLDDOWN_TIMER expiration while in SHORT_WAIT

Actions on event 6:

  • Deactivate LEARN_TIMER.
  • Transition to QUIET state.

Transition 7: SPF_TIMER expiration while in QUIET

Actions on event 7:

  • Compute SPF.
  • Remain in current state.

Transition 8: SPF_TIMER expiration while in SHORT_WAIT

Actions on event 8:

  • Compute SPF.
  • Remain in current state.

Transition 9: SPF_TIMER expiration while in LONG_WAIT

Actions on event 9:

  • Compute SPF.
  • Remain in current state.

6. Parameters ⚙️

All the parameters MUST be configurable at the protocol instance level 🔧. They MAY be configurable on a per IGP LSDB basis (e.g., IS-IS level, OSPF area, or IS-IS Level 1 area).

All the delays (INITIAL_SPF_DELAY, SHORT_SPF_DELAY, LONG_SPF_DELAY, TIME_TO_LEARN_INTERVAL, and HOLDDOWN_INTERVAL) SHOULD be configurable with a granularity of a millisecond ⏱️. They MUST be configurable with a granularity of at least a tenth of a second. The configurable range for all the parameters SHOULD be from 0 milliseconds to at least 6000 milliseconds. And the HOLDDOWN_INTERVAL MUST be defaulted or configured to be longer than the TIME_TO_LEARN_INTERVAL. Non-negotiable, bestie 🙅‍♀️.

If this SPF Back-Off algorithm is enabled by default, then to get consistent SPF delays between implementations with default configuration, the following default values SHOULD be implemented 🍓:

   INITIAL_SPF_DELAY         50 ms
   SHORT_SPF_DELAY          200 ms
   LONG_SPF_DELAY          5000 ms
   TIME_TO_LEARN_INTERVAL   500 ms
   HOLDDOWN_INTERVAL      10000 ms

To satisfy the goals stated in Section 2, operators are RECOMMENDED to configure delay intervals so that INITIAL_SPF_DELAY <= SHORT_SPF_DELAY and SHORT_SPF_DELAY <= LONG_SPF_DELAY 📈.

When setting (default) values, think about your customers and their application requirements, the computational power of the routers, and the size of the network (mainly the number of IP prefixes advertised in the IGP). Also consider how often IGP events happen and how many protocol reactions/computations get triggered by IGP SPF computation, such as BGP, Path Computation Element Communication Protocol (PCEP), Traffic Engineering Constrained SPF (CSPF), and Fast Reroute computations 🧠. Some or all of these factors may change over the life of the network, so keep that in mind. In case of doubt, it's RECOMMENDED that timer intervals be chosen conservatively (i.e., longer timer values). Play it safe, babe 🫠.

For the standard algorithm to be effective in mitigating micro-loops, it is RECOMMENDED that all routers in the IGP domain, or at least all the routers in the same area/level, have exactly the same configured values 🤝.

7. Partial Deployment 🚧

In general, the SPF Back-Off Delay algorithm is only effective in mitigating micro-loops if it's deployed with the same parameters on all routers in the IGP domain or, at least, on all routers in an IGP area/level. The impact of partial deployment depends on the particular event, the topology, and the algorithm(s) used on other routers in the IGP area/level. In cases where the previous SPF Back-Off Delay algorithm was implemented uniformly, partial deployment will increase the frequency and duration of micro-loops 😬. So it is RECOMMENDED that all routers in the IGP domain, or at least within the same area/level, be migrated to the SPF algorithm described herein at roughly the same time.

This isn't a brand-new consideration, though 💅. Over time, network operators have changed SPF delay parameters to meet new customer requirements for fast convergence, as new software and hardware have made possible. They may also have gradually replaced an implementation using one SPF Back-Off Delay algorithm with another implementation using a different one 🦋.

8. Impact on Micro-loops 🔄✨

okay so bestie, micro-loops during IGP convergence happen because FIBs get updated in a non-synchronized or non-ordered way 😭 [RFC5715] [RFC6976] [SPF-MICRO] explain this. a FIB only gets installed after a bunch of steps: the IGP event floods across the network, then there's the SPF wait time, then the SPF computation, then FIB distribution across line cards, and finally the FIB update 💅. this document only talks about the piece that comes from the SPF wait time, so don't come for it for doing everything 🫶

the standardized procedure here reduces the probability and/or duration of micro-loops when IGPs see multiple temporally close events 🌸 it does not prevent all micro-loops, tho 💀. it's still lowkey great because it's less complex and costly to implement than the full solutions: Distributed Tunnels [RFC5715], Synchronized FIB Update [RFC5715], or the ordered FIB approach [RFC6976] 👑

9. IANA Considerations 📋

this document has no IANA actions 🎀

10. Security Considerations 🛡️💀

okay this part is serious bestie, so listen up 👀

the algorithm in this document does not compromise IGP security 🔐 BUT an attacker who can generate IGP events would be able to delay IGP convergence time 😱 that's the scary bit 🙈

the LONG_SPF_DELAY state may help mitigate the effects of Denial-of-Service (DoS) attacks that generate many IGP events 🚨

11. References 📚

11.1. Normative References 💜

11.2. Informative References 🦋

Acknowledgements 🫶

we would like to acknowledge Les Ginsberg, Uma Chunduri, Mike Shand, and Alexander Vainshtein for the discussions and comments related to this document 🌈 thank u besties 💖

Authors' Addresses 📮

  • Bruno Decraene, Orange, Email: bruno.decraene@orange.com
  • Stephane Litkowski, Orange Business Service, Email: stephane.litkowski@orange.com
  • Hannes Gredler, RtBrick Inc., Email: hannes@rtbrick.com
  • Acee Lindem, Cisco Systems, 301 Midenhall Way, Cary, NC 27513, United States of America, Email: acee@cisco.com
  • Pierre Francois, Email: pfrpfr@gmail.com
  • Chris Bowers, Juniper Networks, Inc., 1194 N. Mathilda Ave., Sunnyvale, CA 94089, United States of America, Email: cbowers@juniper.net
📦 where this page comes from