vault

Border Gateway Protocol

18 min read

Border Gateway Protocol

The Border Gateway Protocol (BGP) is the single protocol that stitches the ~77,900 Autonomous Systems of the Internet into one reachable whole — deservedly called “the glue of the Internet.” Standardized as BGP version 4 in RFC 4271 (January 2006, obsoleting RFC 1771), it is “an inter-Autonomous System routing protocol” whose job is to exchange “network reachability information … including the list of Autonomous Systems (ASes) that reachability information traverses” (RFC 4271 §1). BGP is a path-vector protocol: rather than a metric, each advertised route carries the full sequence of ASes it crossed (its AS_PATH), which is used both to prevent loops and to feed policy. It runs over a plain TCP connection on port 179, chosen by neighbors that are usually manually configured — BGP does not auto-discover peers. Crucially, BGP does not pick the shortest path; it picks the path its operator’s policy prefers, which is why BGP is really a distributed policy system as much as a routing one, and why its worst failures — hijacks and leaks — are policy failures, not algorithmic ones. This note covers the protocol as specified; the Linux forwarding mechanism that ultimately consumes BGP’s chosen routes lives in The Routing Subsystem and FIB and IP Routing Decision and Forwarding.

Mental Model — Path-Vector over a Graph of Distrust

Think of BGP as gossip about reachability, annotated with provenance. When AS X can reach prefix P, it tells its neighbors “I can reach P, and the path is [X].” A neighbor Y that accepts this re-announces “I can reach P via [Y, X]” — prepending its own AS number. The route accumulates a breadcrumb trail of every AS it passed through. That trail is the whole trick:

  1. Loop prevention without a metric. If AS Z ever receives a route whose AS_PATH already contains Z, it rejects it — the route has clearly looped. No hop counts, no count-to-infinity, no shared metric needed; the path is the loop detector.
  2. Policy input. The AS_PATH tells you who you’d be routing through, so you can prefer or avoid particular ASes for business or trust reasons.

The graph BGP operates on is one of mutual distrust and commercial relationships. Unlike an IGP, where all routers cooperate and share a metric, every eBGP neighbor is a potential adversary or fool: it might advertise prefixes it doesn’t own, or leak routes it shouldn’t. BGP’s core protocol has essentially no built-in defense against a peer lying — that gap is what RPKI and BGPsec were bolted on to close.

flowchart LR
  ORIG["AS 64500<br/>originates 203.0.113.0/24<br/>AS_PATH = [64500]"]
  T1["AS 64510<br/>re-advertises<br/>AS_PATH = [64510, 64500]"]
  T2["AS 64520<br/>re-advertises<br/>AS_PATH = [64520, 64510, 64500]"]
  RX["AS 64530<br/>receives; sees itself?<br/>NO → accept + apply policy"]
  LOOP["AS 64510 receives a route<br/>with 64510 already in AS_PATH<br/>→ REJECT (loop)"]
  ORIG --> T1 --> T2 --> RX
  T2 -. "if fed back" .-> LOOP

Path-vector propagation and loop prevention. What it shows: a prefix originated by AS 64500 gathers one AS number per hop as it propagates; each AS prepends itself, so the AS_PATH records the exact chain of administrations traversed. The insight to take: loop prevention is structural, not numeric — an AS drops any route whose AS_PATH already lists its own number (RFC 4271 §5.1.2), so BGP needs neither a distance metric nor a hop limit to stay loop-free across a graph it never sees in full.

Sessions, Messages, and the Finite State Machine

Two BGP routers form a peering session (a “BGP session” or “adjacency”) over TCP port 179. Because it rides TCP, BGP inherits reliable, ordered delivery for free and never re-implements retransmission. A session progresses through a finite state machine of six states (RFC 4271 §8): Idle (start), Connect (TCP handshake in progress), Active (retrying / listening), OpenSent (our OPEN sent, awaiting theirs), OpenConfirm (OPENs exchanged, awaiting a confirming KEEPALIVE), and Established — the working state in which UPDATEs flow. A session flapping between Active and Idle is the classic symptom of a peering that won’t come up (wrong ASN, ACL blocking port 179, or a mismatched configuration).

Four message types carry everything (RFC 4271 §4):

  • OPEN (type 1) — the first message each side sends after TCP connects, announcing its AS number, BGP Identifier (a router ID), and a proposed Hold Time. The negotiated Hold Time is “the smaller of its configured Hold Time and the Hold Time received,” and if no KEEPALIVE/UPDATE/NOTIFICATION arrives within it, the session is torn down with a “Hold Timer Expired” error (RFC 4271 §4.2, §6.5).
  • UPDATE (type 2) — the workhorse. One UPDATE can withdraw routes (a list of prefixes no longer reachable), advertise one set of prefixes (the NLRI — Network Layer Reachability Information) that all share a common bundle of path attributes, or both (RFC 4271 §4.3). A withdrawal is how BGP says “forget that route” — and, as the Facebook outage below shows, withdrawing your own routes can erase you from the Internet.
  • KEEPALIVE (type 3, header only) — heartbeat; sent often enough to hold the session, “a reasonable maximum … would be one third of the Hold Time” and never more than one per second (RFC 4271 §4.4).
  • NOTIFICATION (type 3) — an error report; “the BGP connection is closed immediately after it is sent” (RFC 4271 §4.5).

BGP is incremental and stateful: after the initial full-table exchange, only changes (new advertisements and withdrawals) are sent. There is no periodic re-flood as in RIP — steady state is quiet, which is why BGP scales to a million-plus prefixes.

Path Attributes: How a Route Describes Itself

Every advertised route carries path attributes — the metadata that drives selection and policy. Each is encoded as a type-length-value triple with flags (Optional/Well-known, Transitive, Partial, Extended-Length) (RFC 4271 §4.3). The load-bearing ones:

  • ORIGIN (type 1, well-known mandatory) — how the prefix entered BGP: IGP (0), EGP (1), or INCOMPLETE (2, e.g. redistributed from a static route) (RFC 4271 §5.1.1).
  • AS_PATH (type 2, well-known mandatory) — “a sequence of AS path segments,” the ordered list of ASes traversed (RFC 4271 §5.1.2). Segments are usually AS_SEQUENCE (ordered); aggregation can introduce an unordered AS_SET. This is the loop detector and the shortest-path tie-breaker.
  • NEXT_HOP (type 3, well-known mandatory) — “the IP address of the router that SHOULD be used as the next hop to the destinations” (RFC 4271 §5.1.3). Reaching that next-hop across your own AS is an IGP problem — the next-hop resolution mentioned in the sibling note.
  • MULTI_EXIT_DISC / MED (type 4, optional non-transitive) — a hint to a neighboring AS about which of several links between you it should prefer for inbound traffic: “the exit point with the lower metric SHOULD be preferred” (RFC 4271 §5.1.4). Non-transitive: it does not propagate beyond the neighbor AS.
  • LOCAL_PREF (type 5, well-known) — the dominant policy knob, “the advertising speaker’s degree of preference for an advertised route” (RFC 4271 §5.1.5). It is iBGP-only — shared among your own routers, never sent to an external peer — and higher is better. This is where “prefer my customer’s route over my peer’s route over my provider’s route” is encoded.
  • ATOMIC_AGGREGATE (type 6) and AGGREGATOR (type 7) — bookkeeping for route aggregation: which AS/router summarized a set of more-specifics into one prefix (RFC 4271 §5.1.6–5.1.7).

Not in RFC 4271 but universally deployed is the BGP Communities attribute (RFC 1997) — opaque 32-bit tags (ASN:value) that operators attach to routes to signal policy intent between and within ASes (e.g. “don’t export this,” “prepend twice in region X”). Three well-known communities — NO_EXPORT, NO_ADVERTISE, and NO_EXPORT_SUBCONFED — instruct receivers to limit propagation.

eBGP versus iBGP, and the Full-Mesh Problem

BGP is spoken in two modes distinguished only by whether the two ends share an AS (RFC 4271 §1.1):

  • External BGP (eBGP) — between routers in different ASes. This is where routes cross administrative boundaries. On eBGP advertisement a speaker prepends its own AS to the AS_PATH and typically resets NEXT_HOP to itself.
  • Internal BGP (iBGP) — between routers in the same AS, used to carry externally-learned routes across the network so every border router knows the full external picture. On iBGP advertisement the speaker “SHALL NOT modify the AS_PATH” (RFC 4271 §5.1.2) — the path is unchanged because no AS boundary was crossed.

iBGP has a critical rule that creates a scaling headache: a route learned via iBGP is not re-advertised to other iBGP peers. This “split-horizon for iBGP” prevents loops inside the AS (there is no AS_PATH growth to detect them with), but it means every iBGP speaker must hear directly from every other — a full mesh of n*(n-1)/2 sessions for n routers (RFC 4456 §1). At 100 routers that is 4,950 sessions; it does not scale. Two standardized escapes exist:

  • Route Reflection (RFC 4456) relaxes the rule for designated route reflectors (RRs), which are permitted to reflect iBGP-learned routes to their clients. Loops are prevented by two new attributes: ORIGINATOR_ID (the route’s original iBGP source — a router ignores a route bearing its own ID) and CLUSTER_LIST (the reflection clusters traversed — an RR drops a route already carrying its cluster ID) (RFC 4456 §8). Clients peer only with the RRs, collapsing the mesh into a hub-and-spoke.
  • Confederations (RFC 5065) split one AS into several sub-ASes that run eBGP-like sessions among themselves while appearing as a single AS to the outside world.

The Decision Process: How BGP Picks One Best Path

For a given prefix a router may hold many candidate routes (in its Adj-RIB-In, the per-peer received routes). The Decision Process selects exactly one to install and re-advertise, moving it into the Loc-RIB (locally chosen) and then per-peer Adj-RIB-Out (what gets advertised onward) (RFC 4271 §3.2). RFC 4271 defines three phases: Phase 1 computes each route’s degree of preference (driven by LOCAL_PREF and policy, §9.1.1); Phase 2 picks the best route per prefix (§9.1.2); Phase 3 decides what to advertise onward (§9.1.3).

In practice, vendors implement a canonical ordered best-path selection, the first steps of which are standardized by RFC 4271 (§9.1.2.2) and the later tie-breakers of which are near-universal convention:

  1. Highest LOCAL_PREF — policy wins first. (This is why a shorter path can lose.)
  2. Shortest AS_PATH — fewer AS hops.
  3. Lowest ORIGIN — IGP < EGP < INCOMPLETE.
  4. Lowest MED — among routes from the same neighbor AS.
  5. eBGP over iBGP — prefer an externally-learned route.
  6. Lowest IGP metric to the NEXT_HOP — “hot-potato routing”: hand traffic off at the nearest exit.
  7. Lowest BGP Identifier / router ID — final deterministic tie-break (RFC 4271 §9.1.2.2).

Uncertain

Verify: the exact ordering and inclusion of steps 5–7 (eBGP-over-iBGP, IGP-metric-to-next-hop, router-ID). Reason: RFC 4271 §9.1.2.2 standardizes the MED / interior-cost / BGP-identifier tie-breakers, but the widely-taught “13-step” ordering (including eBGP-over-iBGP, oldest-route, lowest-router-ID) is largely Cisco/vendor convention layered on top of the RFC and differs in detail across implementations (Juniper, BIRD, FRR). To resolve: for a specific platform, consult its BGP best-path documentation; the RFC only mandates the earlier steps. #uncertain

The takeaway is the ordering of concerns: policy (LOCAL_PREF) beats topology (AS_PATH) beats efficiency (MED, IGP cost). That inversion — money before math — is the essence of inter-domain routing.

Policy Routing: Gao–Rexford and the Valley-Free Rule

Why do operators set LOCAL_PREF the way they do? Because of commercial relationships. Every eBGP link is one of three types: a customer (pays you for transit), a provider (you pay them), or a peer (you exchange traffic for free, usually only each other’s customer routes). The economically rational policy — formalized by Gao and Rexford and codified operationally in RFC 7908 — is:

  • Prefer customer routes (they earn money) over peer routes (free) over provider routes (cost money). This is exactly a LOCAL_PREF ordering.
  • Export rules (valley-free): advertise your customers’ routes to everyone (you’re paid to carry them), but advertise routes learned from peers and providers only to your customers — never to other peers or providers. Doing otherwise means paying to carry traffic you earn nothing on.

The “valley-free” name comes from viewing a path as going up provider links and down customer links: a legitimate path goes up then over (one peer link) then down — it never dips back up after coming down, which would form a “valley.” A path that violates this is a route leak, and it is one of BGP’s two great failure modes.

Configuration Example

A minimal, realistic eBGP setup toward a transit provider, shown in Cisco IOS syntax with commentary:

router bgp 64500                         ! our AS number (BGP process)
 bgp router-id 192.0.2.1                 ! stable ID, used as the final tie-breaker
 neighbor 198.51.100.1 remote-as 64510   ! the provider's router + its ASN → this is eBGP
 neighbor 198.51.100.1 password S3cr3t   ! TCP-MD5 auth on the session (defense vs spoofing)
 neighbor 198.51.100.1 maximum-prefix 1200000 90  ! HARD CAP: tear down if peer sends >1.2M
                                                   ! prefixes (warn at 90%) — leak circuit-breaker
 neighbor 198.51.100.1 prefix-list OUR-BLOCKS out ! ONLY advertise prefixes we actually own
 address-family ipv4
  network 203.0.113.0 mask 255.255.255.0  ! originate our own /24 into BGP
!
ip prefix-list OUR-BLOCKS permit 203.0.113.0/24  ! the allowlist referenced above

The two most important lines are defensive, not functional. maximum-prefix is the leak circuit-breaker — if the provider suddenly floods you with a full table’s worth of extra more-specifics (the 2019 Verizon scenario below), the session drops instead of your router melting. The outbound prefix-list enforces that you advertise only what you own — the single most effective thing an edge network can do to avoid becoming the origin of a hijack. In BIRD (a common software BGP daemon) the same discipline is expressed with an export filter that rejects any route whose prefix is not in your own address set.

Failure Modes: Hijacks, Leaks, and Self-Withdrawal

BGP’s trust-by-default design means its failures are usually someone advertising something they shouldn’t — or withdrawing something they should have kept.

Prefix hijack — the 2008 Pakistan/YouTube incident. On 24 February 2008 at 18:47 UTC, Pakistan Telecom (AS17557), acting on a government order to block YouTube domestically, announced 208.65.153.0/24 — a more specific of YouTube’s own 208.65.152.0/22 (RIPE NCC RIS case study). Because forwarding uses longest-prefix match, the /24 beat YouTube’s /22 everywhere the announcement reached. The blunder was that the route escaped Pakistan: upstream PCCW Global (AS3491) propagated it to the whole Internet, black-holing YouTube worldwide. YouTube (AS36561) fought back with the same weapon — at 20:07 UTC it began announcing the /24 itself, then at 20:18 UTC announced two /25s (208.65.153.0/25 and 208.65.153.128/25) that were more specific still and thus won back the traffic. PCCW withdrew Pakistan’s routes at 21:01 UTC; total outage ≈ 2 hours 14 minutes. The lesson: a single unfiltered more-specific from one small AS can hijack a global service, and the only immediate self-defense is to out-specific the attacker.

Route leak — the 2019 Verizon / BGP-optimizer incident. On 24 June 2019, a “BGP optimizer” at DQE Communications (AS33154) de-aggregated received prefixes into thousands of more-specifics (meant only for internal traffic steering). DQE’s customer Allegheny (AS396531) passed them to its transit provider Verizon (AS701), “who proceeded to tell the entire Internet” (Cloudflare). The leak should have stopped at Verizon — a giant that had no business accepting a full-table’s worth of more-specifics from a small customer — but “Verizon’s lack of filtering turned this into a major incident.” The more-specifics overrode legitimate routes globally, degrading Cloudflare, Amazon, and others. This is a textbook Type-1/Type-6 leak in RFC 7908’s taxonomy, and the fix is unglamorous: prefix filters, maximum-prefix limits, and RPKI.

Self-withdrawal — the 2021 Facebook outage. BGP failures are not always someone else’s fault. On 4 October 2021, a maintenance command “unintentionally took down all the connections in our backbone network” (Meta engineering). Facebook’s authoritative DNS servers are designed to “disable those BGP advertisements if they themselves can not speak to our data centers” as a health check — so when the backbone vanished, the DNS servers dutifully withdrew their own BGP routes, and “our DNS servers became unreachable even though they were still operational.” A correct-by-design withdrawal, triggered by a broken health signal, erased Facebook from the Internet’s routing table and simultaneously destroyed the DNS the recovery tools depended on. The lesson: a BGP withdrawal is as powerful as an advertisement, and coupling route withdrawal to an automated health check can turn a partial fault into a total, hard-to-recover outage.

Mitigations: RPKI, Route Origin Validation, and BGPsec

The defenses layer from cheap-and-deployed to expensive-and-rare.

RPKI + ROA (origin authorization). The Resource Public Key Infrastructure (RFC 6480) lets “a legitimate holder of IP address space … explicitly and verifiably authorize one or more ASes to originate routes to that address space.” It reuses the existing allocation hierarchy — IANA → RIRs → ISPs — as a certificate chain (resource certificates carrying RFC 3779 IP/ASN extensions). The address holder publishes a Route Origination Authorization (ROA), a signed object containing “(1) an AS number; (2) a list of IP address prefixes; and, optionally, (3) for each prefix, the maximum length” of more-specifics that AS may announce (RFC 6480 §3.2). Note the scope: RPKI validates origin only — who is allowed to originate this prefix — and deliberately “does not secure the AS_PATH itself” (RFC 6480 §1).

Route Origin Validation (ROV, RFC 6811). A router (fed ROA data by an RPKI cache via the RPKI-to-Router protocol, RFC 6810/8210) classifies each received route into one of three states: Valid — “at least one VRP [Validated ROA Payload] Matches the Route Prefix” (origin AS matches and the prefix length is within the ROA’s max length); Invalid — “at least one VRP Covers the Route Prefix, but no VRP Matches it” (someone announced it, but not from an authorized AS or too specific); NotFound — “no VRP Covers the Route Prefix” (no ROA exists) (RFC 6811 §2). Operators typically drop Invalid and accept the rest. ROV would have stopped the 2008 hijack cold: Pakistan Telecom’s origination of YouTube’s space would have been Invalid. Importantly the RFC says routers “MUST NOT exclude a route … as a side effect of its validation state, unless explicitly configured to do so” — the state can instead just lower LOCAL_PREF (RFC 6811 §5).

BGPsec (path validation, RFC 8205). BGPsec closes the gap RPKI leaves by cryptographically protecting the path: it replaces AS_PATH with a BGPsec_PATH attribute in which “every Autonomous System … on the path … has explicitly authorized the advertisement of the route to the subsequent AS,” via chained signatures — each AS signs over the prior path plus the target AS (RFC 8205 §3–4), using a router certificate issued under RPKI. Its fatal deployment problem is that it is not usefully incremental: “if an AS in the path doesn’t support BGPsec, then BGP goes back to traditional mode” (RFC 8205 §7.9) — one unsigned hop voids the guarantee for the whole path — and per-update signature verification is costly. Consequently BGPsec is essentially not deployed at Internet scale as of 2026; the practical security frontier is RPKI ROV plus prefix filtering and the operational hygiene of MANRS (Mutually Agreed Norms for Routing Security).

Uncertain

Verify: current RPKI ROV deployment breadth — what fraction of announced prefixes are covered by valid ROAs, and how many large networks drop Invalids. Reason: this figure moves continuously and I did not pin it to a primary measurement in this pass (the APNIC “BGP in 2025” retrospective did not include RPKI coverage; NIST’s RPKI Monitor tracks it live). To resolve: consult the NIST RPKI Monitor or an RIR/NRO RPKI statistics dashboard at read time. Likewise, BGPsec’s “essentially not deployed” status is a dated (2026) observation. #uncertain

Production Notes

BGP’s scale is the context that makes everything above matter. As of January 2026 the IPv4 default-free zone carried about 1,050,000 prefixes — of which ~52% (544,000) are more-specifics rather than root aggregates — plus ~241,800 IPv6 prefixes, and the whole system spanned ~77,900 ASes (Huston, BGP in 2025, APNIC). That “more than half the table is more-specifics” figure is exactly why leaks and hijacks are so potent: the routing system is already saturated with longest-prefix-match overrides, so one more malicious /24 blends in. It is also why CIDR aggregation and prefix filtering are perennial operational concerns — an un-aggregated Internet would have long since overflowed router forwarding hardware (the FIB in The Routing Subsystem and FIB).

The 4-octet ASN transition (RFC 6793) is largely complete: the 2-octet pool (0–65535) is exhausted, and new allocations are 32-bit numbers like AS4200000000. Legacy interop still leans on the AS_TRANS (23456) placeholder and the parallel AS4_PATH/AS4_AGGREGATOR attributes when a modern speaker talks to an old one. And because BGP peers are manually configured over TCP 179, sessions are also a security surface in their own right — TCP-MD5 or the newer TCP-AO authentication, and Generalized TTL Security (GTSH), guard the session itself against off-path spoofing, orthogonally to the RPKI/ROV protections on the routes it carries.

See Also

Graph View

Backlinks