python

One prefix stops being one route: reading BGP's decision set 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 code we read here lives in pathvector-studio/protocol-in-code. If you're earlier in your journey and want to do things with protocols before dissecting them, start with the hands-on Protocol Lab series instead — it builds the muscle memory this series assumes.

The question

How do multiple received paths for one prefix become a policy-aware set of installable candidates?

That question sounds small until you notice what it costs. Session 03 of this track taught pure best-path selection: hand it a list of candidates, get back the winner. It's a clean, total function. But best-path selection is only correct when every candidate handed to it is a legitimate thing to install. The moment you introduce RPKI validation and routing policy, that assumption evaporates. Some candidates shouldn't be installed at all. Others should be installed but with rewritten attributes that change who wins.

So the shape of the problem changes. One prefix is no longer one route. One prefix is a decision per peer, and the decisions have to be made before comparison can mean anything.

The file that does this is src/protocol_in_code/bgp/decision_process.py, with src/protocol_in_code/bgp/pipeline.py as its companion. It's short enough to read in one sitting, which is the point — the entire argument fits in two functions.

Read the record before you read the loop

Start at the dataclass, not the function. What a piece of code chooses to keep tells you what it thinks a decision is:

@dataclass(frozen=True)
class CandidateDecision:
    peer_id: str
    validation_state: ValidationState
    action: PolicyAction
    installed_candidate: PathCandidate | None

Four fields, and every one of them is load-bearing.

validation_state and action are deliberately separate. Sessions 04 and 05 spent their time on exactly this split: what RPKI says about a route (ValidationState) is not the same thing as what your router does about it (PolicyAction). An INVALID state doesn't mechanically mean "drop." It means an input to a policy that you wrote, and that policy might drop, might deprioritize, might log and accept. Collapsing the two into a single "verdict" field is the most common modelling mistake in this area, and it's the one this dataclass refuses to make. The state and the action ride together, both visible, neither derived from the other after the fact.

installed_candidate is PathCandidate | None, and the None is the whole story. A decision that produced no installable candidate is still a decision — it's a record that this peer offered this prefix and policy said no. You keep the row. You don't silently drop it from the list.

And then peer_id, which is the sneaky one.

Note: PathCandidate intentionally doesn't carry peer_id. Pure best-path comparison doesn't need to know where a route came from — it compares LOCAL_PREF, AS_PATH length, origin, and so on, and none of those depend on peer identity. So earlier sessions dropped it. Here the course puts it back, because policy-aware decision making is inherently about who told you. This is a real design tension in protocol modelling: the minimal type for one operation is the wrong type for the next one.

The loop that turns a prefix into a set

Here's the function the whole session points at:

def evaluate_prefix_candidates(
    adj_rib_in: AdjRIBIn,
    prefix: str,
    vrps: list[VRP],
    policies: PipelinePolicies,
) -> list[CandidateDecision]:
    decisions: list[CandidateDecision] = []
    for peer_id, attributes in received_attributes_for_prefix(adj_rib_in, prefix):
        validation_state, action, installed = evaluate_candidate(prefix, attributes, vrps, policies)
        decisions.append(
            CandidateDecision(
                peer_id=peer_id,
                validation_state=validation_state,
                action=action,
                installed_candidate=installed,
            )
        )
    return decisions

Read the signature first. It takes one prefix and the entire Adj-RIB-In — the table of what every neighbor sent you, before any local processing. It returns a list. That type signature is the session's thesis: one prefix in, many decisions out.

The loop body is a single call. received_attributes_for_prefix(adj_rib_in, prefix) yields (peer_id, attributes) pairs — every peer that currently advertises this prefix. Then evaluate_candidate() — the per-route pipeline that Session 10 assembled — runs unchanged for each one. Session 10 did validation-then-policy for one incoming route. This session does nothing new to that logic; it just runs it across the fan-in.

That's worth sitting with. The interesting code here isn't clever. It's a for loop and an append. The intelligence is in the shape — in deciding that "evaluate one route" and "evaluate a prefix" are different operations with different return types, and that the second is a fan-out over the first rather than a bigger version of it.

Note also what the loop preserves: decisions where installed came back None still get appended. evaluate_prefix_candidates() is a reporting function. It tells you what happened to every path, including the ones that died. If you want to know why traffic for a prefix is going somewhere surprising, this list is the answer, and it would be useless if it only contained survivors.

Selection happens last, and only on survivors

def select_best_installable_for_prefix(
    adj_rib_in: AdjRIBIn,
    prefix: str,
    vrps: list[VRP],
    policies: PipelinePolicies,
) -> PathCandidate | None:
    decisions = evaluate_prefix_candidates(adj_rib_in, prefix, vrps, policies)
    installable = [decision.installed_candidate for decision in decisions if decision.installed_candidate is not None]
    if not installable:
        return None
    return select_best_path(installable)

Four statements, and the ordering of them is the answer to the session's question.

Evaluate everything. Filter to what survived. Bail if nothing did. Then compare.

select_best_path() — the pure function from Session 03 — is called exactly once, on the last line, against a list that has already been filtered and, crucially, already been rewritten. The candidates in installable are not the attributes that arrived on the wire. They're whatever evaluate_candidate() produced after policy ran. If a policy knocked LOCAL_PREF down on a route from an INVALID-validating peer, the candidate in this list carries the lowered value, and best-path compares against that.

This is why "just run best-path" is not enough once validation and policy exist. Best-path is a comparison over a set; it has no opinion about set membership and no opinion about the values it's comparing. Both of those are decided upstream. Run best-path on raw received attributes and you'll faithfully select a route that policy would have rejected.

The if not installable: return None line deserves a beat too. Every path for this prefix can be filtered out, and that's a legitimate outcome — the prefix simply has no route. It's not an error and it's not an empty-list crash in select_best_path(). The None return type makes "no route for this prefix" a first-class value that callers have to handle.

Same shape, different protocol

Once you've seen this ordering, you start recognizing it elsewhere in the series.

Within BGP itself the lineage is explicit: Session 03 gave pure comparison, Sessions 04 and 05 split validation state from policy action, Session 10 wired them together for a single route, and this session fans that out prefix-wide. Nothing was rewritten along the way — each layer wraps the previous one and adds exactly one concern.

The broader pattern is validate → transform → filter → select, and it isn't BGP-specific. A DNS resolver validating RRSIGs before it will serve an answer from cache is doing the same thing: cryptographic verification produces a state, local policy decides whether that state is fatal, and only then does the resolver pick which record set to hand back. A TLS stack evaluating a certificate chain does it too — the chain either validates or it doesn't, and separately your trust policy decides whether a validation failure aborts the handshake or gets pinned around. Same shape, different protocol. The mistake in all three is the same one: fusing the verification result and the local decision into one boolean, and then having nowhere to put the case where you want to accept something you know is broken.

Run it

The walkthrough is executable:

PYTHONPATH=src python3 examples/bgp/session_14_walkthrough.py

Three things to watch for in the output:

  • One peer whose route is deprioritized by policy — same prefix, still installable, but its attributes came out of the pipeline different from how they went in.
  • One peer whose route stays installable without change — the untouched control case.
  • The final best path being chosen after that rewrite, not before it.

If you can trace the third bullet back to the four-line body of select_best_installable_for_prefix(), you've got the session.

Toy model boundary

This is a teaching model, and it simplifies aggressively. Being specific about where:

Best path here is one function call over a flat list. Real BGP best-path selection is the tie-breaker cascade from RFC 4271 §9.1 — weight, LOCAL_PREF, locally originated, AS_PATH length, origin type, MED (with all its comparison-scope subtleties), eBGP over iBGP, IGP metric to next hop, and router-ID as the final coin flip. It also requires next-hop reachability, which this model never checks at all. A candidate here is installable if policy says so; a real router additionally demands a resolvable next hop.

Everything is recomputed from scratch. select_best_installable_for_prefix() reads the whole Adj-RIB-In for a prefix and re-evaluates every peer's path on every call. Real implementations are incremental and event-driven: an UPDATE arrives, and only the affected prefixes are re-run, usually behind a scheduler with route-refresh handling, timers, and damping. There's no notion of time in this model — no MRAI, no convergence behavior, no churn.

There is exactly one best path. No ECMP, no multipath, no add-path. Real deployments routinely install several next hops for one prefix, and the function's PathCandidate | None return type structurally forbids that.

RPKI is a list of VRPs passed in as an argument. No RTR session, no cache staleness, no partial-coverage semantics beyond whatever ValidationState models. Real ROV has to reason about a validator that may be down, stale, or disagreeing with a peer's.

Adj-RIB-Out and advertisement are absent. This model stops at "which path do I install." What you re-advertise to which neighbors, with what attribute modifications, is a whole separate policy stage that isn't here.

No withdrawals, no state transitions. The Adj-RIB-In is a static snapshot. Nothing in this file handles a peer going down, a path being withdrawn, or the difference between "no route" and "route just disappeared" — which is precisely the distinction that makes real routing hard to debug.

None of these omissions change the argument the session is making. They're the reason it fits in forty lines.

Check yourself

Close the walkthrough output and answer these from the source alone:

  1. A peer's route validates as INVALID but the resulting CandidateDecision still has a non-None installed_candidate. Reading evaluate_prefix_candidates() and CandidateDecision, is that a bug — and which field would you inspect to find out what actually happened?
  2. select_best_installable_for_prefix() returns a PathCandidate whose attributes don't match anything you can find in the Adj-RIB-In for that prefix. Where in the four-statement body did the values change, and why is that the correct place for it?
  3. Every peer advertises the prefix, and the function returns None. Which line produced that, and what does the returned value fail to tell you that evaluate_prefix_candidates() would have?

Don't take my word for any of it — the file is short, and the answers are all in it.

Further reading

Read more