Inter-Domain Routing with BGP
Imagine ten thousand independently-run networks — universities, ISPs, cloud providers, content giants. Each refuses to reveal internal details to the others. Yet they need to agree on how to deliver a packet from a laptop in Nairobi to a server in Seoul. No central authority can compute this. No single entity even knows the whole topology. This is the problem that the Border Gateway Protocol (BGP) solves. It does so not by finding the objectively shortest path. Instead, it lets every network enforce its own business relationships. Still, routes almost always converge on a globally usable set. BGP is the glue that makes the Internet a single network of networks. Without it, we would have a shattered archipelago instead. Every route you have ever used to reach a website outside your own ISP's network was chosen by BGP. It runs between routers that trust each other only as far as a contract permits. Unlike interior protocols that optimize a single metric like OSPF's link cost, BGP treats routing as a policy problem first. Shortest-path concerns come a distant second. In the real Internet, who pays whom matters more than who is closer. This article builds BGP from first principles. We cover what an autonomous system is. We explain why path-vector routing avoids the count-to-infinity failures of naive distance-vector routing. We show how eBGP and iBGP sessions differ. We describe how the decision process turns a menu of candidate routes into the single best one. We derive correctness and convergence properties honestly. This includes the famous cases where BGP policy combinations can fail to converge at all. By the end you will be able to trace a real BGP UPDATE message through the decision process. You will be able to read a path-vector table and diagnose a route leak. You will also be able to explain why the Internet's routing table is a patchwork of local decisions. From far enough away, it happens to look like a coherent global map.
- BGP is the exterior gateway protocol that routes between autonomous systems (ASes), each an independently administered network with its own interior routing.
- BGP is a path-vector protocol: routes carry the full AS-path, which lets routers detect and reject loops trivially, unlike plain distance-vector.
- Two flavors exist: eBGP between different ASes (usually adjacent), and iBGP among routers inside one AS, which must be fully meshed or use route reflectors.
- Route selection is not shortest-path; it runs a strict, ordered decision process (local preference, AS-path length, origin, MED, etc.) reflecting commercial relationships.
- Policy is enforced via import/export filters tied to peer, provider, and customer relationships — the "valley-free" routing convention keeps most exchanges economically sane.
- BGP's flexibility is also its danger: misconfigured policy can cause route leaks, hijacks, and — in pathological cases — provable non-convergence (persistent route oscillation).
BGP routes the Internet not by computing shortest paths but by letting each autonomous system apply its own commercial policy to a path-vector, using loop-free AS-paths as the only shared truth.
The idea
An autonomous system (AS) is a network or group of networks under a single administrative authority that presents a common routing policy to the rest of the Internet — an ISP, a university, a cloud provider — each identified by a globally unique 16- or 32-bit AS number. Inside an AS, routers use an interior gateway protocol such as OSPF to agree on paths; between ASes, routers speak BGP, the Internet's sole inter-domain routing protocol. This split is deliberate: intra-domain routing can trust a single administrator's metrics, but inter-domain routing must accommodate tens of thousands of mutually distrustful, commercially competing organizations, so it cannot rely on a single notion of "cost." BGP is classified as a path-vector protocol, a generalization of distance-vector routing. In classic distance-vector (Bellman-Ford), a router advertises only a distance to a destination, and a receiving router has no way to know whether adopting that route would create a loop back through itself — this is exactly why plain distance-vector suffers count-to-infinity. Path-vector fixes this by having each router advertise the entire sequence of AS numbers a route has traversed, called the AS-PATH. A router receiving a route simply checks whether its own AS number already appears in the AS-PATH; if so, it discards the route immediately, because accepting it would create a loop. This single mechanism gives BGP loop-freedom without needing split-horizon heuristics or hold-down timers. BGP sessions come in two kinds. eBGP (external BGP) runs between routers in different ASes — typically directly connected peers at an exchange point or private interconnect — and is how routes actually propagate across the Internet. iBGP (internal BGP) runs between routers inside the same AS so that every border router learns the external routes any other border router has learned, keeping the AS's view of the outside world consistent. Because iBGP routes must not be re-advertised to a third iBGP peer (to prevent internal routing loops without an AS-PATH to catch them), iBGP requires either a full mesh of sessions or a route reflector hierarchy that relays routes on the mesh's behalf. The most important conceptual shift from OSPF is that BGP path selection is policy-driven: an AS chooses among multiple valid, loop-free routes to the same prefix based on business relationships — customer, provider, or peer — encoded in local preference values, not based on hop count or bandwidth.
How it works
BGP runs over a reliable TCP connection (port 179) between two routers called BGP speakers or peers. After the TCP handshake, peers exchange OPEN messages to establish a BGP session, then exchange their full routing tables via UPDATE messages, after which only incremental UPDATEs (and periodic KEEPALIVEs) are sent. Each UPDATE either withdraws previously advertised prefixes or announces new ones, each announcement carrying a set of path attributes: AS-PATH, NEXT-HOP, ORIGIN, LOCAL-PREF, MULTI-EXIT-DISC (MED), and community tags used for policy signaling.
Step-by-step mechanism: 1. Session establishment. Two routers configured as BGP peers open a TCP connection and negotiate capabilities (AS number, hold timer, address families) via OPEN messages. The session moves through the BGP finite-state machine: Idle → Connect → OpenSent → OpenConfirm → Established. 2. Route learning. Once Established, each router sends its entire Adj-RIB-Out (routes it is willing to export) to the peer. The peer stores received routes in its Adj-RIB-In. 3. Import policy. Each incoming route is filtered and possibly modified — dropped, tagged with a local-preference, or have its attributes rewritten — according to the router's configured import policy for that peer. 4. Best-path selection. For every destination prefix, the router runs the BGP decision process, an ordered sequence of tie-breaking rules, over all candidate routes to that prefix (from BGP peers and possibly redistributed from the IGP), to choose exactly one best route, installed in the Loc-RIB and the forwarding table. 5. Export policy. The chosen best route is filtered by export policy per peer (e.g., "do not advertise routes learned from one peer to another peer" — the standard no-transit rule for peer relationships) and re-advertised, with the AS's own AS number prepended to AS-PATH for eBGP announcements. 6. Propagation and reconvergence. When a link fails or a route is withdrawn, the affected router sends WITHDRAW messages, and neighbors recompute their own best paths, potentially triggering further withdrawals or re-announcements — this can take many round trips, a phenomenon called path exploration during convergence.
The decision process (in the order it is actually applied)
``` function SELECT_BEST_ROUTE(candidate_routes):
# candidate_routes: list of routes to the same prefix, each with
# attributes {local_pref, as_path, origin, med, next_hop_igp_cost,
# peer_type, router_id, peer_address} routes = candidate_routes if length(routes) == 1: return routes[0]
# 1. Prefer route with a reachable NEXT_HOP (basic sanity filter) routes = filter(routes, r -> IS_REACHABLE(r.next_hop)) if empty(routes): return NONE
# 2. Highest LOCAL_PREF wins (encodes commercial preference:
# customer routes usually get the highest local-pref) routes = keep_max(routes, key = r -> r.local_pref) if length(routes) == 1: return routes[0]
# 3. Prefer routes originated locally over learned ones
# (e.g. static/aggregate routes injected by this AS) routes = prefer_locally_originated(routes) if length(routes) == 1: return routes[0]
# 4. Shortest AS_PATH length routes = keep_min(routes, key = r -> length(r.as_path)) if length(routes) == 1: return routes[0]
# 5. Lowest ORIGIN code: IGP < EGP < INCOMPLETE routes = keep_min(routes, key = r -> origin_rank(r.origin)) if length(routes) == 1: return routes[0]
# 6. Lowest MULTI_EXIT_DISC (MED), only compared between routes
# from the SAME neighboring AS routes = keep_min_grouped_by_neighbor_as(routes, key = r -> r.med) if length(routes) == 1: return routes[0]
# 7. Prefer eBGP-learned routes over iBGP-learned routes routes = prefer_ebgp_over_ibgp(routes) if length(routes) == 1: return routes[0]
# 8. Lowest IGP cost to the BGP NEXT_HOP ("hot potato" routing:
# hand traffic off to the neighboring AS as early as possible) routes = keep_min(routes, key = r -> r.next_hop_igp_cost) if length(routes) == 1: return routes[0]
# 9. Prefer route from peer with lowest BGP Router ID (tie-break) routes = keep_min(routes, key = r -> r.router_id) if length(routes) == 1: return routes[0]
# 10. Prefer route from peer with lowest peer IP address routes = keep_min(routes, key = r -> r.peer_address) return routes[0] ``` ``` function ON_UPDATE_RECEIVED(peer, update): for prefix in update.withdrawn_routes: remove_route(Adj_RIB_In[peer], prefix) RECOMPUTE_BEST(prefix) for (prefix, attrs) in update.nlri_announcements: if MY_AS in attrs.as_path: discard # loop prevention: the core of path-vector safety continue attrs = APPLY_IMPORT_POLICY(peer, attrs) if attrs == REJECTED: continue Adj_RIB_In[peer][prefix] = attrs RECOMPUTE_BEST(prefix) function RECOMPUTE_BEST(prefix): candidates = collect_all_routes_to(prefix) # across all peers new_best = SELECT_BEST_ROUTE(candidates) if new_best != Loc_RIB[prefix]: Loc_RIB[prefix] = new_best install_in_forwarding_table(prefix, new_best) for peer in bgp_peers: out_attrs = APPLY_EXPORT_POLICY(peer, new_best) if out_attrs != REJECTED: if peer.type == EBGP: out_attrs.as_path = prepend(MY_AS, out_attrs.as_path) send_update(peer, prefix, out_attrs) ```
Complexity & correctness
Per-message and per-router cost. Processing one UPDATE message costs `O(1)` amortized attribute parsing plus `O(k)` for the decision process over `k` candidate routes to the same prefix, where `k` is bounded by the router's number of BGP peers (typically tens to a few hundred, rarely more). Since the Internet's routing table holds roughly `n ≈ 900,000` IPv4 prefixes (2024 figures), a full router must maintain `Adj-RIB-In` tables of size `O(n · p)` where `p` is the number of peers, and a Loc-RIB / forwarding table of size `O(n)`. This is why default-free zone routers need large, fast TCAM-backed forwarding hardware and gigabytes of control-plane memory — it is a real engineering constraint, not an abstraction.
Convergence time. Unlike OSPF, which converges in time proportional to graph diameter times a small constant after a full-topology recomputation, BGP convergence after a failure can take path exploration time proportional to the number of alternate paths a router must try and discard before settling, empirically observed to range from seconds to several minutes for a single prefix withdrawal propagating through the default-free zone. This is because a withdrawal forces every downstream AS to fall back to its next-best route, re-advertise it, watch it get withdrawn too, and repeat — a cascading process bounded by, but not tightly characterized by, `O(AS-path length)` rounds in the worst case.
Loop-freedom (safety invariant). Claim: no router ever installs a route whose forwarding would create a persistent forwarding loop through a cycle of ASes, given a single stable route per prefix. Argument: every route carries the ordered list of AS numbers it has traversed. A router in AS X rejects any route whose AS-PATH already contains X (line `if MY_AS in attrs.as_path`). Since accepting the route and forwarding along it can only ever move traffic through the ASes literally listed in that path, and X cannot re-appear, the resulting AS-level path is a simple path, which cannot contain a cycle. This is strictly stronger protection than plain distance-vector's split-horizon heuristics, which only prevent trivial two-node loops and do not scale to arbitrary topologies.
Loop-freedom does not imply global optimality or even termination. The decision process is a strict total order given complete tie-breaking (it always ends at rule 10, comparing peer IP addresses, which are unique), so any single router, given a fixed set of candidate routes, deterministically picks one best route — this makes local computation well-defined and finite. But because each AS applies independent, uncoordinated policy, the celebrated result of Griffin, Shepherd, and Wilfong (the "BGP wedgies" / SPP framework, 1999–2002) shows that certain combinations of otherwise individually reasonable local-preference policies produce persistent route oscillation — routers keep changing their best path forever, with no stable assignment existing at all. The canonical minimal example uses three ASes each preferring routes through the AS that least prefers routing through it, forming a rock-paper-scissors preference cycle with no stable fixed point. In practice, the Internet avoids this via the Gao–Rexford conditions: routers set local-preference according to a customer > peer > provider hierarchy and observe valley-free routing (never route customer-to-customer traffic through a peer or provider), which together are provably sufficient for both termination and route stability, at the cost of not guaranteeing the shortest possible AS-path is ever chosen.
Tradeoff, stated plainly. BGP trades global path optimality and fast, provable convergence — properties OSPF or plain Bellman-Ford can offer inside a single trusted domain — for policy autonomy and scalability across administratively hostile domains. It is correct in the sense that matters for the Internet (no permanent forwarding loops under standard policy conventions, eventual consistency after transient churn) but is not correct in the sense of guaranteeing shortest paths or bounded convergence time.
Worked example
Consider prefix `203.0.113.0/24`, originated by AS 64512 (a small content network), reaching a router in AS 64500 through two independent paths, via AS 64501 (a Tier-2 transit provider) and via AS 64502 (a private peering partner). The router in AS 64500, call it `R`, receives two eBGP routes for this prefix:
| Attribute | Route A (via AS 64501) | Route B (via AS 64502) |
|---|---|---|
| NEXT_HOP | 192.0.2.1 (reachable) | 192.0.2.9 (reachable) |
| LOCAL_PREF (set on import) | 100 (transit provider) | 100 (peer, same default) |
| AS_PATH | [64501, 64777, 64512] | [64502, 64512] |
| ORIGIN | IGP | IGP |
| MED | 50 | (not comparable — different neighbor AS) |
| IGP cost to NEXT_HOP | 12 | 8 |
Trace through `SELECT_BEST_ROUTE`: 1. Reachability filter — both next hops resolve via the IGP; nothing eliminated. 2. LOCAL_PREF — both routes were tagged 100 by import policy (assume the operator has not yet distinguished peer vs. transit here); tie, continue. 3. Locally originated — neither route originates in AS 64500; tie, continue. 4. AS_PATH length — Route A has length 3 (`[64501, 64777, 64512]`), Route B has length 2 (`[64502, 64512]`). Route B is strictly shorter. The tie breaks at rule 4: Route B wins, even though it costs more in IGP metric (rule 8 never gets reached) and even though Route A traverses a paid transit provider that might, in principle, offer more stable capacity. This is the crux of BGP policy: a shorter AS-PATH through a settlement-free peer beats a longer path through a paid provider whenever LOCAL_PREF does not already distinguish them — which is exactly why real operators do set LOCAL_PREF explicitly (customer routes highest, then peers, then providers) rather than letting AS-PATH length make commercially consequential decisions by accident. Now suppose the operator fixes this: import policy sets `LOCAL_PREF = 200` for anything learned from AS 64502 because it is a settlement-free peering partner with an explicit business preference, versus `LOCAL_PREF = 100` for the AS 64501 transit route. Rule 2 now decides the outcome directly — Route B wins at step 2, and rules 3–10 never execute. This illustrates the design intent of the ordered decision process: LOCAL_PREF is checked first precisely so that human-configured business policy always overrides path-length or metric-derived tie-breaks.
Failure and re-convergence trace. Suppose AS 64502's link to AS 64512 now fails. AS 64502 sends a WITHDRAW for `203.0.113.0/24` to `R`. `RECOMPUTE_BEST` re-runs over the remaining candidate (Route A only), installs it, and `R` sends an UPDATE announcing Route A onward to its own eBGP peers, with AS_PATH now `[64500, 64501, 64777, 64512]` from their perspective. Every downstream AS that had preferred the now-withdrawn shorter path must repeat this same recompute-and-reannounce cycle — this ripple is the path-exploration process responsible for BGP's multi-second-to-minutes convergence delay after failures, in contrast to OSPF's link-state flood which reaches every router in the area almost simultaneously.
Common pitfalls & traps
| Pitfall | Why it happens | Consequence |
|---|---|---|
| Treating BGP as a shortest-path protocol | Confusing AS-PATH-length tie-break (rule 4) with the actual objective | Misconfigured expectations; operators surprised routes don't follow "shortest" path |
| Forgetting the iBGP full-mesh / route-reflector requirement | Assuming iBGP behaves like eBGP and can be re-advertised transitively | Internal routing black holes — a border router never learns a route another border router has |
| Route leaks (re-advertising a peer's or provider's route to another peer/provider) | Missing or incorrect export filters, violating valley-free routing | Traffic transits an AS for free, or globally visible outages (e.g., the 2008 Pakistan Telecom YouTube incident was a hijack, but leaks follow the same filter-failure pattern) |
| MED comparison across different neighbor ASes | Ignoring the rule that MED is only meaningful between routes from the same AS | Silent, incorrect tie-breaking that violates protocol semantics |
| Assuming BGP always converges quickly | Extrapolating from OSPF's bounded reconvergence | Underestimating outage duration; not accounting for path-exploration delay in SLAs |
| Ignoring the possibility of non-convergence (SPP violations) | Assuming any locally-sane policy set is globally safe | Persistent route oscillation ("BGP wedgie"), invisible without formal policy analysis |
Pioneers & history
BGP emerged directly from operational necessity in the early NSFNET era, when the Internet's core needed a successor to the earlier Exterior Gateway Protocol (EGP), which could not express policy or handle non-tree topologies. The now-famous "two napkins" design session gave BGP its folkloric origin story: a simple, extensible protocol sketched quickly to keep the growing Internet from fragmenting into incompatible routing islands.
Origins · 1 minYakov Rekhter and how this was discovered
A network architect at IBM and later Juniper Networks, Rekhter co-authored the original BGP specifications (RFC 1105, RFC 1163, and the enduring RFC 4271) alongside Kirk Lougheed, Tony Li, and others. His work on path-vector routing and address aggregation directly shaped how the modern Internet scales its routing table, and the CIDR aggregation scheme he co-designed remains foundational to how BGP prefixes are summarized today.
Where this matters
Every ISP peering session, every cloud provider's edge network, and every content delivery network's traffic-engineering strategy runs on BGP. Internet Exchange Points (IXPs) exist specifically to let hundreds of ASes exchange BGP routes over shared switching fabric instead of point-to-point circuits. Anycast services — the technique behind most DNS root servers and DDoS-resilient CDNs — rely on BGP's path-vector nature to let the same IP address be announced from many physical locations, with BGP naturally routing each client to a topologically nearby instance. Cloud providers use BGP at the edge of their virtual private clouds to exchange routes with enterprise customers over dedicated interconnects. Network operators diagnosing outages routinely read raw BGP UPDATE streams from public route collectors (RouteViews, RIPE RIS) to reconstruct exactly how a hijack or leak propagated. Understanding BGP is also the necessary bridge to understanding how the transport layer can rely on a stable, if not always optimal, path existing between any two hosts on the global Internet.
Ask the tutor: How would you configure import and export policy on a multi-homed AS to correctly implement valley-free routing between two providers and one peer?
What exactly is an Autonomous System Number (ASN) and why does BGP need it?
An AS number is a globally unique identifier (16-bit historically, now commonly 32-bit) assigned by regional registries to a network operating under one administrative policy. BGP needs it because the protocol's core safety mechanism — loop detection via AS-PATH — only works if every administrative domain along a path is uniquely and unambiguously named. If two unrelated networks shared an identifier, a router could not tell whether a path re-entering "that identifier" was actually a loop through itself or a coincidence involving someone else's network. ASNs also let operators express policy per-neighbor: local-preference, filters, and communities are all keyed to the neighboring AS number, making the AS the fundamental unit of trust and negotiation in inter-domain routing, much as a subnet is the fundamental unit of aggregation in CIDR.
Why doesn't BGP simply pick the path with the fewest AS hops, like OSPF picks the cheapest link cost?
BGP's designers deliberately subordinated path length to commercial policy because the Internet is not one organization optimizing one objective — it is thousands of competing businesses. An ISP has no incentive to carry a competitor's traffic for free just because that path happens to be one AS-hop shorter; doing so would violate its own economics. The decision process therefore checks LOCAL_PREF, a value each operator sets according to business relationships (favor customers, then peers, then providers), before it ever looks at AS-PATH length. AS-PATH length only serves as a tie-breaker among routes an operator has already deemed commercially equivalent. This is precisely why traceroutes across the Internet often look "longer" than physically necessary: the chosen path reflects who is willing to carry the traffic and on what terms, not pure geometry.
What is the difference between eBGP and iBGP beyond just "external" versus "internal"?
eBGP sessions run between routers in different ASes, typically single-hop and directly connected, and every eBGP announcement prepends the sending AS's number onto the AS-PATH — this is what makes loop detection possible across AS boundaries. iBGP sessions run between routers inside one AS to distribute externally learned routes internally, and critically do not prepend an AS number, since all routers share one AS number; this means iBGP alone provides no loop protection, which is why an iBGP route learned from one iBGP peer must never be re-advertised to a different iBGP peer. That restriction forces either a full iBGP mesh, which scales as O(n²) sessions for n border routers, or route reflectors, which relay routes on the mesh's behalf and reduce the session count to roughly linear in n at the cost of some path diversity.
Can BGP guarantee that routing will converge after any change in policy or topology?
No, and this is one of the protocol's most important honest limitations. The Stable Paths Problem framework, developed by Griffin, Shepherd, and Wilfong, proves constructively that certain combinations of individually reasonable, locally-configured route preferences have no stable solution at all — routers can oscillate forever, each continually preferring a route that the last change just invalidated. The Internet avoids this in practice by convention rather than protocol enforcement: operators follow the Gao–Rexford guidelines (customer routes preferred over peer routes, preferred over provider routes, combined with valley-free export policy), which are provably sufficient for stability given realistic commercial topologies. But nothing in the BGP specification itself forbids an operator from configuring a policy set that breaks this guarantee, which is why large-scale policy audits and simulation tools matter in real operational practice.
What is a BGP route hijack, and how is it different from a route leak?
A hijack is the announcement of a prefix an AS does not legitimately own or have permission to originate — either accidentally (a misconfigured origin AS) or maliciously (traffic interception, censorship, or spam origination). A leak, by contrast, involves a legitimately learned route being re-advertised in violation of intended policy, typically breaking the valley-free convention, such as a multi-homed customer accidentally offering itself as transit between two of its own providers. Both exploit the same underlying weakness: BGP has no built-in cryptographic verification of who is authorized to originate or forward a given prefix. RPKI-based Route Origin Validation addresses the hijack case by cryptographically binding prefixes to authorized origin ASes; BGPsec and community-based filtering conventions (like MANRS) target leaks, though adoption of both remains partial across the global routing system.
How does MED (Multi-Exit Discriminator) differ from LOCAL_PREF, and why is it compared only within one neighbor AS?
LOCAL_PREF is set unilaterally by the receiving AS to express its own preference among all candidate routes, regardless of who sent them, and takes priority in the decision process. MED, by contrast, is set by the sending (neighboring) AS to hint which of several entry points into its network it would prefer incoming traffic to use — for example, favoring the exit closest to the destination inside its own topology. Because MED is a neighbor's internal hint rather than the local AS's own judgment, comparing MED values from two different neighboring ASes would be meaningless — AS X's idea of "50" has no defined relationship to AS Y's idea of "50." The decision process therefore restricts MED comparison to routes learned from the same neighboring AS, and even then places it low in priority, since it is advisory rather than authoritative.
Why is BGP described as running "over TCP," and does that create any risk?
BGP delegates reliable, in-order, congestion-controlled delivery entirely to TCP port 179, so the protocol itself never needs retransmission logic, fragmentation handling, or sequencing — a deliberate simplification versus protocols like OSPF that manage their own reliability over raw IP. The risk is that BGP inherits every property and vulnerability of the underlying TCP session: a session reset (deliberate or attacker-induced) forces a full route re-exchange, and TCP-level attacks such as connection resets can be used to destabilize peering sessions. Operators mitigate this with TCP MD5 signatures or TCP-AO authentication on BGP sessions, and with the Generalized TTL Security Mechanism (GTSM), which rejects BGP packets whose TTL indicates they did not originate from a directly connected peer, protecting against off-path spoofing attempts.