BGP Route Flap Damping
Extracted elements (30)
A ceiling value on the figure of merit bounds the maximum hold-down time regardless of prior history, ensuring that even a severely flapping route can be readvertised after a defined period of stability.
Computation of exponential decay is deferred until a route event occurs rather than being applied periodically to all routes, drastically reducing CPU load. Reuse lists allow suppressed routes to be batched and reevaluated only when they approach reuse eligibility.
Exponential decay was chosen for the figure of merit because it allows decay over any elapsed time to be computed in a single multiply using precomputed arrays, regardless of the interval length, satisfying the property f(f(x,t1),t2) = f(x, t1+t2).
MED is excluded from the route tuple by default because including large numbers of MED values increases per-route state significantly. When MED is included, it is used only in the tuple comparison, with a single state entry shared regardless of MED value.
Multiple configuration parameter sets per router (tuned to short-term severe flap vs. chronic mild flap, or to routes with vs. without alternate paths) allow more nuanced suppression policies. Parameter selection may be based on BGP LOCAL_PREF, prefix length, or presence of an alternate path.
Route suppression is applied only on EBGP-learned routes because suppressing IBGP routes within an AS creates routing inconsistencies between routers in the same AS, which can cause persistent routing loops.
Separate, slower decay rates while a route is unreachable are recommended so that routes reachable for a larger percentage of the flap cycle recover faster; this avoids penalizing intermittently-reachable routes as heavily as continuously-flapping ones.
In topologies with multiple AS paths, aggressive damping by a distant AS can suppress a stable secondary path when the primary flaps. This can be mitigated by damping near the source of the flap, using consistent parameters, or disabling penalties on AS path changes.
The route flap damping technique described is also applicable to IDRP (ISO/IEC 10747), the inter-domain routing protocol for ISO 8473 PDUs.
A BGP implementation must be prepared for a large volume of routing traffic and cannot rely upon the sender to sufficiently shield it from route instabilities.
An implementation should pack updates efficiently, provide a minimum readvertisement delay, provide bounds on maximum readvertisement delay, and must be computationally efficient in the presence of a very large number of candidates for readvertisement.
Implementations should disallow configuration of route damping on IBGP peers. When IBGP routes within an AS are inconsistent, route loops can easily form; suppressing IBGP learned routes causes such inconsistencies.
Penalties for instability should only be applied when a route is removed or replaced, not when a route is added. Consistent application of this constraint results in a stable secondary path being preferred over a damped unstable primary path.
Providers should publish their damping parameters and be willing to manually clear damping on specific prefixes or AS paths at the request of other providers when the request is accompanied by credible assurance that the problem has been addressed.
Route flap damping MUST be applied only when receiving updates from external peers (EBGP). Applying this technique to IBGP learned routes or to advertisements to IBGP or EBGP peers after route selection can result in routing loops.
The decay half life should be set to a time considerably longer than the period of the route flap it is intended to address. The reuse threshold should be set below the cutoff threshold.
When a route is withdrawn, it should be treated as if an unreachable were received. A route path replacement by a peer should be treated as an unreachable followed by a route advertisement, since both AS paths may be flapping.
Where routes are unstable, use and announcement of the routes should be suppressed rather than suppressing their removal. It is more desirable to suppress the acceptance of a route (and therefore its use in the IGP) rather than suppress only the redistribution.
Configuration parameters for the damping algorithm include: cutoff threshold (cut), reuse threshold (reuse), maximum hold-down time (T-hold), decay half-life while reachable (decay-ok), decay half-life while unreachable (decay-ng), and decay memory limit (Tmax-ok / Tmax-ng).
Decay arrays store precomputed values of the per-tick decay factor raised to the power of the array index, enabling O(1) exponential decay over any elapsed interval via a single array lookup and multiply rather than exponentiation.
Per-route state required for damping includes: figure-of-merit (scaled integer), last time updated, config block pointer (for multiple parameter sets), and reuse list traversal pointers (previous and next for doubly linked list).
Reuse lists are a circular array of doubly-linked list heads, each representing suppressed routes scheduled for reevaluation at a specific future time increment (delta-reuse). Routes are inserted into the list corresponding to their estimated reuse eligibility time.
The reuse index array maps scaled figure-of-merit ratios to reuse list indices without requiring logarithm computation. It is indexed by (figure-of-merit / reuse - 1) * scale-factor, and each entry holds a reuse list index.
The route tuple used for damping state is defined by NLRI (prefix + length) and AS path (included by default), with optional inclusion of next hop and MED. AS sets at the end of a path are excluded from comparison by default.
The stability figure of merit is an accumulated, time-decayed, per-route instability score. It is incremented by 1 on each transition from reachable to unreachable, clipped to a ceiling value, and decayed exponentially at a configurable rate while the route is reachable or unreachable.
The practices described in this document do not further weaken BGP security. Denial of service is possible in an already insecure routing environment; route flap damping contributes to the persistence of such attacks but does not impact the methods of prevention or source determination.
On peer loss: either mark all individual routes advertised by that peer as unstable or mark the peering session itself as unstable (saving per-route memory). Routers beyond the adjacent peer will dispose of damping structures over time as no further updates arrive.
On route advertisement: decay figure-of-merit using decay-array-ng[t-diff]; if not suppressed and figure-of-merit < cut then use route; if suppressed and figure-of-merit < reuse then unsuppress and use; otherwise suppress and insert into reuse list.
On route unreachable: decay existing figure-of-merit using decay-array-ok[t-diff], add penalty of 1, clip to ceiling, remove from any reuse list, withdraw route if not already suppressed, update t-updated, insert into a reuse list.
Reuse timer event (every delta-reuse seconds): save head of zeroth queue, rotate circular array by incrementing offset, then reevaluate each route in the saved queue — decay figure-of-merit and either reuse the route, re-insert into a later reuse list, or recover storage.