Shortest Path First (SPF) Back-Off Delay Algorithm for Link-State IGPs
Extracted elements (22)
Standardizing a single SPF back-off algorithm across implementations reduces the differential in SPF computation timing between routers, which in turn reduces the probability and duration of transient micro-loops during IGP convergence caused by routers computing FIBs from different LSDB versions.
The algorithm uses elapsed time since the initial IGP event (TIME_TO_LEARN_INTERVAL) rather than a count of SPF computations to drive state transitions. This improves network-wide consistency because different routers may receive the same failure events at different times and thus perform different numbers of SPF computations.
Three delay states (QUIET, SHORT_WAIT, LONG_WAIT) are defined to distinguish a single isolated failure (QUIET→SHORT_WAIT, fast response), a multi-event single-component failure (SHORT_WAIT, moderate delay), and sustained instability (LONG_WAIT, long delay for resource conservation). This tiered approach balances convergence speed with stability.
Partial deployment of this algorithm (where only some routers in an area adopt it) can increase rather than decrease micro-loop frequency and duration, especially if the previous algorithm was deployed uniformly. It is RECOMMENDED to migrate all routers in an IGP area/level to this algorithm at roughly the same time.
The algorithm applies uniformly to all types of IGP routing table computation (full SPF, incremental SPF, Partial Route Computation), treating them identically. The choice of computation type is a local implementation decision and does not affect the back-off state machine.
All delay parameters (INITIAL_SPF_DELAY, SHORT_SPF_DELAY, LONG_SPF_DELAY, TIME_TO_LEARN_INTERVAL, HOLDDOWN_INTERVAL) MUST be configurable at the protocol instance level and MAY be configurable per IGP LSDB (e.g., IS-IS level, OSPF area).
All delay parameters MUST be configurable with a granularity of at least a tenth of a second, and SHOULD be configurable with millisecond granularity. The configurable range SHOULD extend from 0 ms to at least 6000 ms.
For the algorithm to be effective in mitigating micro-loops, it is RECOMMENDED that all routers in the IGP domain, or at least all routers in the same area/level, have exactly the same configured parameter values.
If this algorithm is enabled by default, implementations SHOULD use the specified default values: 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 ensure consistent SPF delays across implementations.
Operators are RECOMMENDED to configure delay intervals such that INITIAL_SPF_DELAY <= SHORT_SPF_DELAY and SHORT_SPF_DELAY <= LONG_SPF_DELAY to satisfy the algorithm's convergence goals.
The HOLDDOWN_INTERVAL MUST be defaulted or configured to be longer than the TIME_TO_LEARN_INTERVAL to ensure the FSM does not return to QUIET before all events of a single failure have been collected.
When IGP events arrive while SPF_TIMER is already running, no new SPF_TIMER is started (only HOLDDOWN_TIMER is reset). The SPF_TIMER started by the first event in a state continues unmodified.
HOLDDOWN_INTERVAL is the period of IGP quiet required before the FSM returns to QUIET state, recommended at 10000 ms (default). It MUST be configured longer than TIME_TO_LEARN_INTERVAL.
HOLDDOWN_TIMER is (re)started on every IGP event and set to HOLDDOWN_INTERVAL. Its expiration moves the FSM to QUIET state from SHORT_WAIT (after deactivating LEARN_TIMER) or from LONG_WAIT.
INITIAL_SPF_DELAY is the SPF delay used in QUIET state for a first IGP event, recommended at 50 ms (default). It is designed to handle single isolated failures with very fast convergence.
LEARN_TIMER is started once when the first IGP event is received in QUIET state and set to TIME_TO_LEARN_INTERVAL. Its expiration transitions the FSM from SHORT_WAIT to LONG_WAIT; it is deactivated if HOLDDOWN_TIMER expires while in SHORT_WAIT.
LONG_SPF_DELAY is the delay used in LONG_WAIT state when the IGP is considered unstable, recommended at 5000 ms (default). It allows the network to stabilize during periods of multiple independent failures.
SHORT_SPF_DELAY is the delay used in SHORT_WAIT state when multiple IGP events arrive within TIME_TO_LEARN_INTERVAL, recommended at 200 ms (default). It handles single-component failures (e.g., node or SRLG failure) that generate multiple IGP events.
SPF_TIMER is the FSM timer set to the computed SPF delay (INITIAL_, SHORT_, or LONG_SPF_DELAY) upon IGP events. Upon expiration in any state, the routing table computation is performed.
TIME_TO_LEARN_INTERVAL is the maximum duration to collect all IGP events related to a single component failure, recommended at 500 ms (default). The FSM uses this as the LEARN_TIMER duration; expiration triggers transition from SHORT_WAIT to LONG_WAIT.
An attacker able to generate IGP events can delay IGP convergence by keeping the FSM in SHORT_WAIT or LONG_WAIT states. The LONG_SPF_DELAY state partially mitigates DoS attacks that generate large numbers of IGP events by throttling SPF computation frequency, but it does not prevent the delay itself.
The SPF Back-Off Delay FSM defines three states — QUIET, SHORT_WAIT, and LONG_WAIT — controlled by three timers (SPF_TIMER, HOLDDOWN_TIMER, LEARN_TIMER). Transitions occur on IGP events or timer expirations: QUIET→SHORT_WAIT on first IGP event, SHORT_WAIT→LONG_WAIT on LEARN_TIMER expiration, and either LONG_WAIT or SHORT_WAIT→QUIET on HOLDDOWN_TIMER expiration.