python

When a BGP peer disappears, one session loss becomes many route decisions

Kaoru Nagashima

— 7 min read

This post is part of Protocol in Code, a free series that reads network protocols as logic — inputs, state, and branches — rather than as configuration examples. Every module points at one small Python file and asks you to read it the way you'd read any other piece of code. The source lives at github.com/pathvector-studio/protocol-in-code.

Note: If you're earlier on the path and want hands-on packet-level exercises before diving into implementation logic, start with the companion Protocol Lab series instead.

The question

What happens to Loc-RIB when one peer disappears and the best path came from that peer?

Hold onto that while you read. It sounds like a single question, but it hides at least four: how many routes are affected, which store changes first, what replaces the lost path, and what happens when nothing can.

The operational answer everyone knows is "the routes go away." That's true and useless. It doesn't tell you why some prefixes survive a peer loss with a brief reconvergence and others vanish entirely, or why a peer that advertised 500 prefixes generates 500 independent decisions rather than one.

The code answer is more precise, and it's about thirty lines long.

Where this sits

Session 06 introduced per-peer received state — the idea that Adj-RIB-In isn't one flat table but a mapping keyed by peer, with each peer's advertisements kept separately. That structure is what makes this session possible. If you'd stored all received paths in a single undifferentiated table, "which routes came from this peer?" would be a scan; with per-peer state it's a key lookup.

The file we're reading is src/protocol_in_code/bgp/recompute.py. Read it in this order:

  1. recompute_best_path_for_prefix() — the single-prefix decision
  2. handle_peer_loss() — the loop that applies it
  3. How lost prefixes are collected from one peer
  4. How each affected prefix is recomputed independently

Read it like code

Start with the smaller function, because the bigger one is just a loop around it:

def recompute_best_path_for_prefix(
    adj_rib_in: AdjRIBIn,
    loc_rib: LocRIB,
    prefix: str,
) -> PathCandidate | None:
    candidates = build_candidates(adj_rib_in, prefix)
    if not candidates:
        remove_best_path(loc_rib, prefix)
        return None

    best = select_best_path(candidates)
    install_best_path(loc_rib, best)
    return best

Four lines of logic and one branch. That branch is the whole story.

build_candidates(adj_rib_in, prefix) reads the current contents of Adj-RIB-In and assembles every path anyone is still advertising for this prefix. Note the tense: current. This function has no memory of what used to be there and no notion of "the peer that just went down." It sees state, not events.

Then the branch. If the candidate set is empty, there is nothing to install, so remove_best_path() deletes the Loc-RIB entry and the function returns None. If the set is non-empty, select_best_path() runs the decision process over the survivors and install_best_path() writes the winner into Loc-RIB.

Read that carefully and notice what isn't there: the function never asks "was the previous best path from the dead peer?" It doesn't compare old and new. It doesn't need to. It recomputes from scratch and overwrites. This is the difference between an event-driven and a state-driven design, and BGP implementations lean state-driven for exactly this reason — recomputing from current state is much harder to get wrong than incrementally patching a decision.

The loop that makes it plural

Now the outer function:

def handle_peer_loss(
    adj_rib_in: AdjRIBIn,
    loc_rib: LocRIB,
    peer_id: str,
) -> dict[str, PathCandidate | None]:
    lost_prefixes = tuple(adj_rib_in.paths_by_peer.get(peer_id, {}).keys())
    adj_rib_in.paths_by_peer.pop(peer_id, None)

    results: dict[str, PathCandidate | None] = {}
    for prefix in lost_prefixes:
        results[prefix] = recompute_best_path_for_prefix(adj_rib_in, loc_rib, prefix)
    return results

Three things happen, strictly in order, and the ordering is not incidental.

First, snapshot. lost_prefixes is materialized as a tuple before anything is mutated. That tuple(...) isn't stylistic — it copies the keys out of the dict so the subsequent pop doesn't invalidate what we're about to iterate over. This is the list of prefixes that were affected, captured at the moment of loss.

Second, delete. adj_rib_in.paths_by_peer.pop(peer_id, None) removes the entire per-peer subtree. Every path that peer ever advertised is gone from received state in one operation. The None default means calling this for an unknown peer is a no-op rather than a KeyError — losing a peer you weren't tracking should be harmless.

Third, recompute. Only after the deletion does the loop run. This ordering answers one of the questions you should be holding: Adj-RIB-In changes first, Loc-RIB second. It has to. recompute_best_path_for_prefix() calls build_candidates(), which reads Adj-RIB-In — if the dead peer's paths were still in there, build_candidates() would happily hand them back and the peer's paths could get reinstalled as best. The deletion isn't cleanup after the decision; it's the input to it.

The for loop is where "one session loss" becomes "many route decisions." One peer, N prefixes, N independent invocations of the decision process. There is no batching, no shared state between iterations, no notion of "the peer went down" inside the per-prefix function at all. Each prefix asks the same question in isolation: given who's still advertising, what's best now?

And each can get a different answer:

Situation Outcome
Another peer also advertises this prefix build_candidates() returns a non-empty set, select_best_path() picks a survivor, Loc-RIB gets a new best path
The dead peer was the only source build_candidates() returns empty, remove_best_path() fires, prefix disappears from Loc-RIB
The dead peer wasn't best for this prefix anyway Recomputation runs regardless and reinstalls the same winner

That third row is worth sitting with. The code doesn't optimize it away. It recomputes prefixes whose best path was never in danger, because checking "was this prefix's best path from the dead peer?" is itself a decision that can be wrong, while recomputing is unconditionally correct. Correctness first; a real implementation would add the optimization later, guarded carefully.

The return value — dict[str, PathCandidate | None] — is the outcome of every one of those decisions. A PathCandidate means a path survived or replaced; None means the prefix is gone. The | None in the type signature is the withdrawal case made explicit in the type system.

Same shape, elsewhere

The pattern here isn't BGP-specific: maintain per-source state, and when a source disappears, delete its contribution and re-derive the aggregate from what's left.

DNS resolvers do this when a nameserver stops responding — the cached RRsets attributed to it become unusable, and resolution falls back to re-deriving an answer from the remaining authoritative servers. Link-state protocols do it when an LSA ages out: remove the contribution, rerun SPF over the surviving topology. Even TCP's congestion state has the shape, one level down — a loss signal doesn't patch cwnd incrementally so much as re-derive it from the current state of the connection.

The alternative design — event-driven incremental patching, where "peer down" tries to surgically fix only the Loc-RIB entries it believes are affected — is faster and much easier to get subtly wrong. Every protocol that has tried it has accumulated a long tail of "stale entry" bugs. The recompute-from-current-state shape trades CPU for the guarantee that the output is always a function of the present input.

Run it

The walkthrough is executable:

PYTHONPATH=src python3 examples/bgp/session_09_walkthrough.py

It installs a best path from one peer, simulates that peer going down, and shows the backup path taking over. Watch the transition specifically: the prefix stays in Loc-RIB but its best path changes identity. Then modify the script to remove the second peer's advertisement and run it again — now the same code path produces a disappearance instead of a substitution. Same function, same branch, different candidate set.

Toy model boundary

This module is a reading aid, not a BGP implementation. Be clear about what it leaves out:

  • No BGP session machinery. handle_peer_loss() is called by you, with a peer_id string. Real peer loss is detected by the FSM — hold timer expiry, TCP reset, NOTIFICATION received, an explicit administrative shutdown — and each of those has different timing characteristics. Hold-timer detection can take tens of seconds; a TCP RST is near-instant. The model has no timers at all.
  • No withdrawal propagation. In the real protocol, changes to Loc-RIB feed Adj-RIB-Out and generate UPDATE messages toward other peers, subject to export policy. Here, the function returns a dict and stops. Everything downstream of the local decision is absent.
  • No route flap damping, no MRAI. Real BGP deliberately slows reconvergence: the MinRouteAdvertisementInterval timer rate-limits how often a prefix's changes go out, and damping penalizes prefixes that flap. This model reconverges instantaneously and without hysteresis, which is precisely the behavior operators spend effort suppressing.
  • No graceful restart. RFC 4724 exists so that a peer going down doesn't immediately trigger this code path — routes are marked stale and retained while the peer restarts. The model has no stale-route concept and no restart signalling; loss is always immediate and total.
  • Delete-then-recompute is not atomic. The pop happens, then the loop runs. In between, Adj-RIB-In and Loc-RIB disagree. A single-threaded toy never observes that window, but real implementations have concurrent readers and need locking or versioning to keep anyone from reading the inconsistent middle state.
  • select_best_path() is simplified. The decision process here is a reduced version of the real tie-break ladder in RFC 4271 §9.1, and the model has no ADD-PATH, no multipath, no RIB failure states.
  • Cost is not modeled. N prefixes means N recomputations. With a full table that's ~1M invocations, and real implementations do a great deal of work — prefix indexing, batched walks, deferred best-path runs — to make peer loss survivable. The model's flat loop makes the logic obvious and the performance question invisible.

Check yourself

Can you answer these just by reading the source? Don't take my word for any of it — go verify against recompute.py.

  1. Which store changes first, Adj-RIB-In or Loc-RIB — and what would break if you swapped the order? Trace what build_candidates() would return if pop ran after the loop instead of before it.
  2. Under exactly what condition does a prefix disappear from Loc-RIB entirely? Find the single expression that decides it, and name the state that has to hold across all remaining peers.
  3. Why is lost_prefixes built with tuple(...) rather than used directly as a dict view? What concretely goes wrong if you drop the tuple() call?

You've got this module when you can say, without notes: peer loss deletes Adj-RIB-In state for that peer first; then each affected prefix is recomputed independently; a backup path can become best; and if no backup exists, the Loc-RIB entry disappears.

Further reading

Read more