Path Vectors, Policy, and Why BGP Does Not Minimize Anything

An interior routing protocol computes a shortest path because a single organisation wants one policy: deliver the packet by the cheapest route, where cheap is defined by a metric the operator sets. An exterior routing protocol cannot work that way, because the parties involved do not share a definition of cheap. One network wants to minimize the load on its own backbone; another wants to send traffic to a peer rather than a customer because the peer charges nothing; a third wants to avoid a transit provider whose contract penalises a particular kind of traffic. There is no scalar that orders these preferences, and the protocol does not pretend to find one.

BGP is the protocol that carries the disagreement. Its central mechanism is not a distance but a path: each announcement lists the sequence of autonomous systems a packet would traverse, and each router chooses among candidates by applying a ranked list of criteria that begins with locally configured policy and ends with a tie-breaker on address. The result is a routing system that converges on something consistent without being optimal for anyone.

The path as both loop check and evidence

A distance-vector protocol advertises a metric to a destination and trusts the neighbour’s report. A path-vector protocol advertises the whole route, so a router can check the announcement for its own identifier before accepting it. If an autonomous system sees itself anywhere in the AS_PATH of a route, the route is a loop and is rejected. The check is exact and requires no coordination, which is what makes a routing system spanning independent operators possible without a global authority computing paths.

The path also carries information the receiver can use. Its length is a coarse measure of distance, but its content is more useful: a receiver can see whether a route passes through a customer, a peer, or a provider, because those relationships are visible in the sequence. The convention that an autonomous system should announce to a provider only routes for its own customers and itself, and should announce to a peer only routes for its own customers and itself, is what keeps the global topology free of transit paths that were never paid for. A route whose path violates that convention is an economic anomaly, and operators detect them by inspecting AS_PATH rather than by measuring anything.

The next hop is carried separately. The NEXT_HOP attribute names the address on the shared link, or on a shared multi-access segment, to which packets for the prefix should be sent, and it is not necessarily the address of the router that sent the announcement. On a shared segment, one router can advertise a route whose next hop is a third router’s address, and the receiving routers resolve that address through the interior protocol or through the segment itself. This is how a route reflector distributes routes without becoming a forwarding hop: the next hop is preserved from the original announcement, and the reflector is invisible to the data path.

The decision process is a lexicographic order

A router that has several routes to the same prefix selects one by walking a fixed sequence of comparisons. The order matters more than any individual step, because the first step that distinguishes two candidates decides between them and no later step is consulted.

1. Highest local preference        (iBGP attribute, set by local policy)
2. Shortest AS_PATH                (only among routes with equal preference)
3. Lowest origin type              (IGP < EGP < incomplete)
4. Lowest MED                      (compared only within one neighbour AS)
5. eBGP over iBGP
6. Lowest IGP cost to NEXT_HOP
7. Lowest router ID, then lowest peer address

Only steps 2 and 6 involve anything resembling a metric. Step 1 is pure policy: an operator marks a route as preferred and the protocol does not ask why. Step 4 is a hint from a neighbouring operator, compared only among routes learned from that same neighbour, which is why a MED is not a global preference and why it can be ignored across AS boundaries. Step 6, the interior cost to the next hop, is where the interior protocol finally enters, and it is deliberately late: it decides among routes that are already equal on every external criterion.

The consequence of placing step 6 late is that a router will often accept a route whose exit point is farther away inside its own network, because the external criteria dominated. The operator who wants the opposite configures local preference to override the path length, which is the standard way to implement hot-potato and cold-potato routing without changing the protocol.

Why the ranking is not a metric

A metric induces a total order that is transitive: if A is better than B and B better than C, then A is better than C. The BGP decision process does not have that property when local preference is involved, because local preference is per-router policy rather than a property of the route. Two routers in the same autonomous system can rank the same two routes differently, and the resulting system can have no stable assignment of routes at all.

The canonical example is a pair of autonomous systems, each of which prefers a route through the other to a route through its own customer, arranged so that each withdraws the route the other depends on. Neither operator has done anything irrational, and the combination oscillates. Gao and Rexford showed that the standard business relationships, if every participant follows the rule of preferring customers over peers over providers, produce a stable and uniquely determined outcome. The stability is a property of the policy constraints, not of the protocol.

The protocol’s own response to instability is route flap damping, which penalises a prefix that withdraws and re-announces repeatedly by suppressing it for a period that grows with the number of flaps. The mechanism trades reachability for stability, and its parameters were tuned for a network whose failure modes differed from the ones that later appeared, which is why the recommended settings were revised and why some operators disabled damping entirely.

Convergence is proportional to the path, not the hop count

When a route is withdrawn, the announcement propagates one autonomous system per message, and each hop must recompute its decision before it can advertise anything. The propagation is not a flood in the sense of link-state routing; it is a wavefront along the path the route used, and its speed is limited by the session processing and the timer settings at each border.

The delay has three components. The first is the interior convergence inside each autonomous system: a border router learns a new route and must distribute it to the other border routers through iBGP, and iBGP is a full mesh or a set of reflectors, so the distribution is a second routing problem nested inside the first. The second is the eBGP advertisement itself, which is a TCP message and subject to the session’s timers. The third is the decision at each receiver, which must compare the new candidate against the existing best and possibly withdraw its own advertisement downstream.

The aggregate effect is that a change deep in one provider’s network can take tens of seconds to reach a distant part of the internet, and during that interval some routers forward on a path that no longer exists. A router that has lost its route but has not yet told its neighbours is a black hole for the duration, which is why the withdrawal of a route is propagated eagerly rather than waiting for a hold timer to expire.

def select_route(candidates):
    """Lexicographic best-path selection over the decisive fields.
    Each candidate is a dict; the key sorts ascending, so preferences
    that should rank higher are negated or inverted."""
    def key(r):
        return (
            -r["local_pref"],        # highest preference first
            r["as_path_len"],        # shortest AS path next
            r["origin"],             # IGP(0) < EGP(1) < incomplete(2)
            r["med"],                # comparable only within one neighbour AS
            not r["ebgp"],           # eBGP before iBGP
            r["igp_cost"],           # interior cost to the next hop
            r["router_id"],          # final tie-breaker
        )
    return min(candidates, key=key)

The comparison above is only valid when every candidate comes from the same neighbouring autonomous system, because the MED step must otherwise be skipped rather than compared across neighbours. That conditional makes the selection a function of the candidate set rather than of each candidate independently, which is one reason a correct implementation cannot be a simple sort.

What the protocol does not carry

BGP does not carry a metric of available bandwidth, a measure of delay, or any statement about load. A route is reachable or it is not, and the attributes describe policy and topology rather than performance. An operator who wants traffic to follow a particular path because the alternative is congested has to express that through local preference or through a community value agreed with a neighbour, and the expression is static: it does not change when the congestion appears.

This is the boundary between the routing system and the transport. The forwarding path chosen by BGP is fixed until a route changes, and the adaptation to load happens inside the connections that use it, as described in AIMD Congestion Control and the Collapse It Prevented. The two systems operate on different timescales and with different information, and neither can substitute for the other.

The address space that BGP announces is itself a policy artefact. A prefix is announced by the autonomous system that holds it, and the aggregation that keeps the table small depends on the assignment following the topology. That dependency was created by the move away from classful addressing, described in Classful Addressing, Subnets, and the Move to CIDR, and the table’s growth is the price of every organisation that insists on keeping its prefix portable.

The last boundary is trust. A session between two border routers authenticates the peer weakly or not at all, and the content of an announcement is believed because the peer is configured as a neighbour. A misconfigured router that announces a prefix it does not hold attracts traffic for that prefix from every network that prefers the more specific route, and the traffic is delivered to the wrong place until the announcement is withdrawn. The protocol has no mechanism to prove that an announcement is authorised; the mechanisms that later appeared attach a signed attestation to the route and let the receiver check it, which adds a verification step without changing the path-vector mechanism itself.