python

Where a route lives: the three RIBs, as code

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. The whole series lives in one repo: github.com/pathvector-studio/protocol-in-code. If you're newer to this and want to build and poke protocols by hand first, start with the companion Protocol Lab series, then come back here to read the internals.

Today's module is BGP, Session 06. Earlier sessions treated a BGP UPDATE as state mutation (Session 02) and worked through best-path selection (Session 03). This one connects those two: it answers where the data actually sits between arriving on the wire and going back out.

The question

Here's the question to keep turning over as you read:

Where does a route live inside the router before selection, after selection, and right before advertisement?

That "before / after / right before" phrasing is not decoration. A single prefix — say 10.0.0.0/24 — can exist in three different places inside the same router at the same time, in three different shapes, owned by three different pieces of logic. The names for those places are Adj-RIB-In, Loc-RIB, and Adj-RIB-Out. Configuration guides tell you these exist. Reading the code tells you why they can't be the same store.

The source file is src/protocol_in_code/bgp/ribs.py. It's small enough to hold in your head all at once, which is the point.

Three stores, three shapes

Start with the data structures, because the whole argument is already visible in their type signatures.

@dataclass
class AdjRIBIn:
    paths_by_peer: dict[str, dict[str, PathAttributes]] = field(default_factory=dict)


@dataclass
class LocRIB:
    best_paths: dict[str, PathCandidate] = field(default_factory=dict)


@dataclass
class AdjRIBOut:
    advertisements_by_peer: dict[str, dict[str, PathCandidate]] = field(default_factory=dict)

Read those three lines slowly and notice how the shapes disagree on purpose.

AdjRIBIn is keyed by peer first, then by prefix — dict[peer_id][prefix] — and it holds PathAttributes, the raw thing that arrived in an UPDATE. That nesting is the whole reason Adj-RIB-In can hold several paths for one prefix: each peer gets its own sub-table, so two peers advertising 10.0.0.0/24 land in two different buckets and neither overwrites the other.

LocRIB is keyed by prefix only, and it holds a PathCandidate, not a PathAttributes. There's no peer dimension at all. One prefix, one winner. This toy model installs exactly one best path per prefix — the selection has already happened by the time anything lands here.

AdjRIBOut looks structurally like Adj-RIB-In — keyed by peer then prefix — but it stores PathCandidate and it means something completely different: what we intend to send to each peer. It is not a copy of Loc-RIB. We'll get to why.

Note: The type of the value is doing as much work as the key here. PathAttributes is "what a neighbor told us." PathCandidate is "an input to the best-path comparison." The RIBs literally hold different types because they're at different stages of the pipeline.

Reading it as a pipeline

The module gives a five-line sketch of the full flow, and every line is a real function in the file:

store_received_path(adj_rib_in, peer_id, prefix, attributes)
candidates = build_candidates(adj_rib_in, prefix)
best = select_best_path(candidates)
install_best_path(loc_rib, best)
stage_advertisement(adj_rib_out, peer_id, best)

Received → candidates → selected → installed → staged. Walk each step against the source.

Storing what a peer said

def store_received_path(
    adj_rib_in: AdjRIBIn,
    peer_id: str,
    prefix: str,
    attributes: PathAttributes,
) -> None:
    adj_rib_in.paths_by_peer.setdefault(peer_id, {})[prefix] = attributes

setdefault(peer_id, {}) creates the per-peer sub-table if this is the first thing we've heard from that peer, then stores the attributes under the prefix. Because the outer key is the peer, storing peer A's route for a prefix never touches peer B's route for the same prefix. That single setdefault is why Adj-RIB-In can hold multiple paths for one prefix — it's per-peer received state, and nothing here is deduplicating or comparing.

Collecting the candidates

When it's time to decide, we pull every peer's version of a prefix back out:

def received_attributes_for_prefix(
    adj_rib_in: AdjRIBIn,
    prefix: str,
) -> list[tuple[str, PathAttributes]]:
    received: list[tuple[str, PathAttributes]] = []
    for peer_id, attributes_by_prefix in adj_rib_in.paths_by_peer.items():
        attributes = attributes_by_prefix.get(prefix)
        if attributes is None:
            continue
        received.append((peer_id, attributes))
    return received

It iterates over every peer, asks each one's sub-table for this prefix, and skips the peers that never advertised it. The return type keeps the peer_id attached — list[tuple[str, PathAttributes]] — because at this point we still know who told us what.

Then build_candidates converts those into the objects best-path selection actually consumes:

def build_candidates(adj_rib_in: AdjRIBIn, prefix: str) -> list[PathCandidate]:
    candidates: list[PathCandidate] = []
    for _, attributes in received_attributes_for_prefix(adj_rib_in, prefix):
        candidates.append(candidate_from_attributes(prefix, attributes))
    return candidates

Look at the for _, attributes in ... line. The peer_id is deliberately thrown away — bound to _ and never used. This is the bridge between Session 02's world (PathAttributes off the wire) and Session 03's world (PathCandidate, the thing you compare), and it is intentionally lossy. It keeps only the fields a pure best-path comparison needs and drops peer ownership entirely. That simplification is fine here, but hold onto it — later sessions have to restore peer ownership once validation state and policy actions become part of the decision, and they can't, because this step forgot who the peer was.

The conversion itself is where one specific transformation happens:

def candidate_from_attributes(prefix: str, attributes: PathAttributes) -> PathCandidate:
    return PathCandidate(
        prefix=prefix,
        next_hop=attributes.next_hop,
        local_pref=attributes.local_pref,
        as_path=attributes.as_path,
        origin_type=origin_to_origin_type(attributes.origin),
    )

Notice origin (a string, off the wire) becomes origin_type (an integer, for comparison). That mapping lives at the top of the file:

def origin_to_origin_type(origin: str) -> int:
    order = {
        "igp": 0,
        "egp": 1,
        "incomplete": 2,
    }
    return order.get(origin.lower(), 2)

igp beats egp beats incomplete, and lower numbers are preferred — the classic BGP origin ordering, expressed as a lookup table so the selection logic can compare integers instead of strings. Anything unrecognized falls through to 2 (incomplete), the least-preferred value.

Installing the winner

Selection happens elsewhere (that's Session 03's select_best_path), and the result gets installed:

def install_best_path(loc_rib: LocRIB, best_path: PathCandidate) -> None:
    loc_rib.best_paths[best_path.prefix] = best_path

Keyed by prefix, one value. Whatever was there before is replaced. This is the "after selection" answer: Loc-RIB is the selected local result, one best path per prefix.

Staging what goes back out

Finally, advertisement:

def stage_advertisement(
    adj_rib_out: AdjRIBOut,
    peer_id: str,
    path: PathCandidate,
) -> None:
    adj_rib_out.advertisements_by_peer.setdefault(peer_id, {})[path.prefix] = path

This is where the "not just a copy of Loc-RIB" point becomes concrete. stage_advertisement takes a peer_id. Loc-RIB has no concept of peers — it's one winner per prefix. Adj-RIB-Out is back to per-peer keying because what you advertise depends on who you're advertising to. In a real router, outbound policy, route filtering, and next-hop rewriting all mean peer X and peer Y can receive different things for the same locally-installed best path. The store is separate because the decision is separate. Keeping them apart in the data model is what makes that future divergence possible instead of a special case bolted on later.

The withdraw functions (withdraw_received_path, remove_best_path, withdraw_staged_advertisement) mirror the stores, and two of them share a small housekeeping pattern worth noticing — after popping a prefix, they pop the whole peer sub-table if it went empty:

    peer_table.pop(prefix, None)
    if not peer_table:
        adj_rib_in.paths_by_peer.pop(peer_id, None)

That keeps received_attributes_for_prefix's iteration from stepping over dead peers with empty tables.

Run it and watch the three stores fill

The walkthrough is runnable. From the repo root:

PYTHONPATH=src python3 examples/bgp/session_06_walkthrough.py

It stores two received paths for the same prefix (so you can see Adj-RIB-In holding both at once), builds candidates from them, installs a single best path into Loc-RIB, and stages one outbound advertisement into Adj-RIB-Out. Running it makes the "same prefix, three stores, three shapes" claim something you can see in printed state rather than something you have to take on faith.

Toy Model Boundary

This is a teaching model, and it simplifies in ways that matter for real deployments. Be honest with yourself about what's missing:

  • One best path per prefix. Real BGP supports add-paths and multipath, where Loc-RIB can legitimately hold more than one path for a prefix. Here, install_best_path overwrites — one winner, always.
  • No per-peer outbound policy is actually applied. Adj-RIB-Out is structured to differ per peer, but this module stages the same PathCandidate you installed. The real work — export policy, prefix filtering, AS-path prepending, next-hop-self, communities — happens between Loc-RIB and Adj-RIB-Out in a production router and isn't modeled here.
  • build_candidates drops the peer. As noted above, this is a deliberate simplification that later sessions have to walk back. In real BGP the peer identity feeds into selection tie-breakers (like lowest router-ID / peer address) and into validation and policy — you cannot actually forget who advertised a route.
  • PathAttributes is a reduced set. Real path attributes include MED, communities, aggregator, atomic-aggregate, and more. The PathCandidate here carries just the fields best-path comparison needs.
  • No timers, no churn control. Nothing here models RIB-out batching, MRAI timers, or route dampening — advertisement is a synchronous dict write.

None of that makes the model wrong; it makes it readable. But if you carry these RIB shapes into reasoning about a real router, carry the caveats too.

The same shape elsewhere

The three-store split isn't a BGP quirk — it's a recurring pattern: keep received state, selected state, and outbound state in separate stores because different logic owns each one, and they diverge. Once you've seen it here, you'll recognize the same shape whenever a system takes in competing inputs, picks a winner, and then re-derives what to emit — the "what came in," "what I chose," and "what I'll say" are almost never the same object. Reading Adj-RIB-In / Loc-RIB / Adj-RIB-Out as three deliberately different data types is the transferable lesson, not the acronyms.

Check yourself

Don't look at your notes. Can you answer these just by reading ribs.py?

  1. Why can Adj-RIB-In contain multiple paths for one prefix — which exact line makes that possible?
  2. Why does Adj-RIB-Out have to be a separate store from Loc-RIB, rather than a copy of it? What would break if you merged them?
  3. Where, precisely, does the string origin become the integer origin_type, and what happens to a value that isn't igp, egp, or incomplete?

If any of those is fuzzy, the answer is in the source — go find it.

Further reading

Read more