BGP — path vector, AS, policy routing: Worked examples

Vocabulary this page needs (built from zero)

Every example below leans on a handful of terms and one piece of maths notation. We define them here, once, before any example uses them.

Definition Gao–Rexford export filtering (who you re-advertise a route to)

After an AS picks its best route to a prefix, it must decide which neighbors to tell. The rule depends on who it learned the route from:

Route learned from	Export to Customer	Export to Peer	Export to Provider
Customer	✅	✅	✅
Peer	✅	❌	❌
Provider	✅	❌	❌

Why: you happily tell paying customers about every route (you earn money carrying it), but you refuse to give peer- or provider-learned routes to anyone except customers — otherwise you'd be handing out free transit.

The full decision ladder (defined once, used everywhere)

Every example below walks down this exact ladder. Compare routes attribute by attribute; the first attribute that differs decides, and you stop. Each rung uses only terms defined above.

Formula BGP best-path selection — all 8 steps (top wins)

Highest LOCAL_PREF — the policy knob defined above; ranks customer > peer > provider (cheapest money first).
Shortest AS_PATH — fewest AS numbers in the path list (a distance-like tie-break, not the primary metric).
Lowest ORIGIN code — IGP $(0) <$ EGP $(1) <$ INCOMPLETE $(2)$ ; prefer the smaller code.
Lowest MED (Multi-Exit Discriminator) — a neighbour's hint about which of its own links to prefer; compared only between routes from the same neighbouring AS.
eBGP over iBGP — a route learned from a different AS beats one learned inside your own AS.
Lowest IGP metric to the egress — the "hot-potato" rule: leave via the nearest exit inside your AS.
Oldest route — the route that has been stable longest wins (favours already-converged, less flappy paths).
Lowest router-ID — a final deterministic tie-break using the neighbour router's 32-bit ID (see the conversion above).

The scenario matrix

Before touching numbers, let's list every distinct situation a BGP route can be in. Think of these as the "quadrants" of BGP — miss one and you'll hit a case you never rehearsed.

Cell	Case class	What makes it tricky
A	Decision by LOCAL_PREF (policy beats distance)	longest path can win
B	LOCAL_PREF tie → AS_PATH breaks it	the "shortest path" intuition, but only as tie-break
C	Tie down through ORIGIN, oldest route, to router-ID	every early attribute equal, degenerate late tie-breaks
D	Loop rejection (own ASN in path)	route silently discarded — a "zero" output
E	Export filtering (Gao–Rexford)	a route exists but is not advertised onward
F	AS_PATH prepending to lose on purpose	making your own path longer deliberately
G	MED compared / MED ignored → step 6 finishes it	only within same neighbor AS — a "sign" trap
H	Degenerate origin: empty / single-element AS_PATH	the base case, path length 0 or 1
I	Real-world word problem	translate business relationships into a decision
J	Exam twist: valley-free violation detection	spot the illegal path shape

Each example below is labelled with the cell(s) it covers. Together they touch every row.

Cell A — Policy beats distance

Worked example Cell A: LOCAL_PREF decides, longest path wins

AS10 hears three routes to prefix P:

R1 from provider AS90, $AS_PATH = [90, 7]$ — 2 hops, LOCAL_PREF $= 100$
R2 from peer AS80, $AS_PATH = [80, 6, 7]$ — 3 hops, LOCAL_PREF $= 200$
R3 from customer AS70, $AS_PATH = [70, 5, 4, 3, 7]$ — 5 hops, LOCAL_PREF $= 300$

Which route does AS10 install?

Forecast: guess before reading — is it the 2-hop R1, or something else?

Compare step 1, LOCAL_PREF (highest wins). Values are $100, 200, 300$ . R3 has $300$ . Why this step? LOCAL_PREF is the first rung of the ladder. Nothing below it is even consulted until there is a tie here — and there is no tie.
Stop. R3 already wins outright; AS_PATH length is never examined. Why this step? AS10 earns money by handing traffic to its paying customer AS70, so its operator configured customer routes with the highest LOCAL_PREF ( $= 300$ , per the default convention). The 5-hop path is the cheapest for AS10's wallet, not the shortest.

Verify: $max (100, 200, 300) = 300 \Rightarrow$ R3. The chosen route has the most AS hops of the three ( $5 > 3 > 2$ ), which is exactly the "policy first, distance second" behaviour. ✔

Look at Figure s01. AS10 sits at the left as a white circle. Three arrows fan out to the right toward the three route labels R1 (top), R2 (middle), R3 (bottom). Two arrows are black (R1, R2 — the losers) and one arrow is red (R3 — the winner). Only the red arrow's label mentions "LP=300, highest", and a red caption in the top-right explains R3 wins despite being the longest path. The colour coding is: black = considered but rejected, red = the single chosen object. That red-versus-black split is the whole picture — the longest black-hop path won purely because its LOCAL_PREF sat highest on rung 1.

Figure — BGP — path vector, AS, policy routing

Cell B — Tie on policy, AS_PATH breaks it

Worked example Cell B: equal LOCAL_PREF, shortest AS_PATH wins

AS10 hears two routes to prefix Q, both from customers (so both LOCAL_PREF $= 300$ ):

R4 $AS_PATH = [70, 5, 7]$ — 3 hops
R5 $AS_PATH = [71, 7]$ — 2 hops

Forecast: now that policy is tied, does the shorter path win?

Step 1 LOCAL_PREF: $300 = 300$ . Tie. Move down. Why this step? The decision process is a strict ladder — only on an exact tie do we descend to the next rung.
Step 2 AS_PATH length: $∣ R 4∣ = 3$ , $∣ R 5∣ = 2$ . Shortest wins → R5. Why this step? Once money is equal, BGP falls back to a distance-like measure to stay efficient. This is the only place the "shortest path" intuition is correct.

Verify: $min (3, 2) = 2 \Rightarrow$ R5. Note the contrast with Cell A: there the longer path won because policy differed; here the shorter wins because policy is equal. ✔

Cell C — Everything ties, down through ORIGIN and oldest route to router-ID

Worked example Cell C: degenerate all-equal tie

AS10 hears two routes to R, both from customers:

R6 from neighbor router-ID 10.0.0.2, $AS_PATH = [70, 7]$ , ORIGIN $=$ IGP (code 0), MED $= 50$ , both eBGP, IGP cost to egress $= 5$ , learned first
R7 from neighbor router-ID 10.0.0.9, $AS_PATH = [71, 7]$ , ORIGIN $=$ IGP (code 0), MED $= 50$ , both eBGP, IGP cost to egress $= 5$ , learned later

Forecast: if LOCAL_PREF, path length, ORIGIN, MED, eBGP/iBGP, and IGP cost are all equal, is the choice random?

Steps 1–6 all tie: LOCAL_PREF $300 = 300$ ; AS_PATH length $2 = 2$ ; ORIGIN code $0 = 0$ ; MED — not comparable, different neighbor ASes ( $70$ vs $71$ ), so this rung is skipped; both eBGP; IGP cost $5 = 5$ . Why this step? We must walk the whole ladder. A degenerate input is one where every early rung ties, forcing us toward the bottom.
Step 7 oldest route: R6 was learned first, so by the "prefer the longest-stable route" rule R6 would already win here. Why this step? Preferring the older route damps needless churn — if a newly arrived route is otherwise identical, keeping the established one avoids re-computing forwarding for no benefit.
Step 8 lowest router-ID (shown for completeness): even if we ignored age, convert both IDs to integers using $value (a . b . c . d) = a \cdot 25 6^{3} + b \cdot 25 6^{2} + c \cdot 256 + d$ . 10.0.0.2 $\to 167772162$ , 10.0.0.9 $\to 167772169$ ; the first is smaller → R6 again. Why this step? The very last rung guarantees the outcome is deterministic — never random — so two routers evaluating the same routes always agree; we include it to show the tie is resolved either way.

Verify: interpreting the dotted quads as unsigned 32-bit integers, $10.0.0.2 = 167772162$ and $10.0.0.9 = 167772169$ ; $167772162 < 167772169 \Rightarrow$ R6. Both the oldest-route rung and the router-ID rung select R6. ✔

Cell D — Loop rejection (the "zero" output)

Worked example Cell D: own ASN in the path → discard

AS10 receives a route to S with $AS_PATH = [90, 10, 4]$ .

Forecast: does AS10 install it, or throw it away?

Run the loop test before the decision process even starts. Rule: accept $⟺ X \in / P$ , where $X = 10$ is AS10's own ASN and $P$ is the received path treated as a collection for this membership check (recall $\in /$ = "is not an element of"). Why this step? Loop detection is a gate: an ineligible route never reaches the decision ladder. The path is the proof of loopiness — no global map needed.
Check membership: is $10 \in [90, 10, 4]$ ? Yes ( $10$ appears in the list). Accepting would send traffic back through AS10 — a loop. Why this step? Path vector's whole reason to exist (over distance vector's count-to-infinity) is exactly this instant, local check.
Output: discard. No route to S is installed via this advertisement — the "degenerate/zero" outcome where the answer is nothing. Why this step? Once the gate rejects a route, there is nothing left to select from this advertisement; producing "no route" is the correct, deliberate result, not an error — AS10 simply waits for a loop-free path to arrive.

Verify: $10 \in {90, 10, 4}$ is True $\Rightarrow$ reject. Contrast: a path like $[90, 4]$ would pass the gate ( $10 \in / {90, 4}$ ). ✔

Look at Figure s02. Three boxes hold the AS numbers of the path [90, 10, 4], drawn left-to-right as AS90 AS10 AS4, with origin AS4 on the right (BGP reads paths right-to-left). Black arrows point leftward between boxes, showing the direction the advertisement travelled. The middle box AS10 is drawn in red — because that number is AS10's own ASN sitting inside the very path AS10 just received. A red caption below spells out "10 is already in the path → REJECT (loop)". Colour coding: black = other ASes, red = the offending own-ASN. Seeing your own number already printed on the path is the whole loop test in one glance.

Cell E — Route exists but must NOT be exported

Worked example Cell E: Gao–Rexford export filtering

AS10 has selected a best route to T that it learned from a peer AS80. Its neighbors are: customer AS70, peer AS81, provider AS90. To whom may AS10 advertise this route?

Forecast: does everyone hear about it?

Identify the learned-from type: peer. Why this step? Gao–Rexford export permission (defined above) depends entirely on who you learned it from.
Apply the peer row of the export table: peer-learned routes export only to customers. Why this step? AS10 earns nothing carrying traffic between a peer and anyone but its own paying customers, so it refuses to give this route to another peer or to its provider — that would be free transit.
Result: advertise to AS70 (customer) ✅; withhold from AS81 (peer) ❌ and AS90 (provider) ❌. Why this step? This selective silence is the enforcement mechanism — by never handing a peer-route to another peer or a provider, AS10 guarantees no one uses it as a free transit shortcut, which is exactly what keeps global paths valley-free.

Verify: exactly $1$ of the $3$ neighbors receives the route. This is the mechanism that produces valley-free paths: peer- and provider-learned routes never climb further up. ✔

Cell F — Prepend to LOSE on purpose

Worked example Cell F: AS_PATH prepending for traffic engineering

AS10 owns prefix U and reaches the world through two providers, AS90 and AS91. It wants inbound traffic to prefer the AS90 link. It cannot set other people's LOCAL_PREF, so it uses the one knob it can influence remotely: AS_PATH length.

Normally both advertisements are $AS_PATH = [10]$ . AS10 instead exports:

to AS90: $[10]$ (length 1)
to AS91: $[10, 10, 10]$ (prepended twice, length 3)

Forecast: which link will most of the internet use to reach U, and why?

Recall who compares AS_PATH length: any distant AS that has a LOCAL_PREF tie between the AS90-route and the AS91-route falls to step 2. Why this step? Prepending only helps once policy is tied for the deciding AS — it is a step-2 lever.
Compare lengths at such an AS: the route carrying $[\dots, 10]$ (via AS90) is shorter than the one carrying $[\dots, 10, 10, 10]$ (via AS91). Why this step? By making its own path artificially longer on the AS91 side, AS10 makes that side look worse, steering inbound traffic to AS90.
Result: inbound traffic favours the AS90 entry. AS10 deliberately degraded one of its paths. Why this step? AS10 has no control over remote operators' LOCAL_PREF, so the only lever it can push from a distance is the length attribute at rung 2 — lengthening the AS91 advertisement is the standard, RFC-legal way to nudge inbound traffic, and repeating its own ASN never trips the loop test in others (they aren't AS10).

Verify: $len ([10]) = 1 < len ([10, 10, 10]) = 3$ , so under a step-2 comparison the AS90 path wins. ✔

Cell G — MED: comparable vs ignored, then step 6 finishes it

Worked example Cell G: MED only within the same neighbor AS, IGP metric breaks the survivors

AS10 hears three routes to V, all customer-learned (LOCAL_PREF $= 300$ ), all AS_PATH length $2$ , all ORIGIN IGP (code 0):

R8 from neighbor AS70, MED $= 30$ , IGP cost to its egress $= 8$
R9 from neighbor AS70, MED $= 10$ , IGP cost to its egress $= 8$
R10 from neighbor AS71, MED $= 5$ , IGP cost to its egress $= 3$

Forecast: does R10 win because it has the smallest MED?

Steps 1–3 tie: LOCAL_PREF, AS_PATH length, and ORIGIN code all equal for all three. Descend to step 4, MED.
Step 4 MED — compare only within the same neighbor AS. R8 and R9 both come from AS70, so compare them: $min (30, 10) = 10 \Rightarrow$ R9 beats R8, and R8 is eliminated. R10 comes from a different AS (AS71), so its MED is not compared against AS70's — R10 survives untouched. Why this step? MED is a downstream hint about which of that same neighbor's links to prefer. Comparing MED across different ASes is meaningless — one AS's "10" and another's "5" are unrelated numbers.
Step 5 eBGP/iBGP: R9 and R10 are both eBGP → still tied. Descend to step 6. Why this step? MED could only prune the AS70-internal contest; it can never rank R10 against R9, so the surviving pair must be split by a lower rung.
Step 6 lowest IGP metric to the egress (hot-potato): R9's egress costs $8$ inside AS10; R10's egress costs $3$ . $min (8, 3) = 3 \Rightarrow$ R10 wins. Why this step? With everything above tied, BGP dumps the traffic out the nearest exit inside AS10 to minimise the distance it carries the packets itself — that is the hot-potato rule, and R10's exit is closer.

Verify: among same-AS routes $min (30, 10) = 10 \Rightarrow$ R9 over R8; R10's MED $= 5$ is never compared against them; then $min (8, 3) = 3 \Rightarrow$ R10 is the final winner. So the naive "smallest MED (5) wins immediately" reasoning reaches the right route for the wrong reason — R10 wins on IGP cost at step 6, not on MED. ✔

Cell H — Degenerate origin (empty / length-1 path)

Worked example Cell H: the base case of the AS_PATH

AS7 originates prefix W (it owns those addresses). What is the AS_PATH it stores locally, and what does its first eBGP neighbor AS8 see?

Forecast: what does an AS_PATH look like at the very moment a prefix is born?

At the origin, locally: AS7 has not received W from anyone; the path is the empty sequence $[]$ , length $0$ . Why this step? This is the base case — no hops have been traversed yet. Every longer path is built from here.
First eBGP export: AS7 prepends its own ASN. $[] \Rightarrow [7]$ , length $1$ . Why this step? Prepend-on-export is universal, including the very first hop. So the shortest possible received path is length 1.
AS8 receives $[7]$ , runs the loop test ( $8 \in / [7]$ ✔), prepends → stores $[8, 7]$ for onward use. Why this step? Showing the second hop confirms the recursion: every AS applies the same two operations (loop-test, then prepend) to whatever length it received, so the base case $[]$ grows one element per AS crossed, and the origin ( $7$ ) forever remains the right-most element.

Verify: length goes $0 \to 1 \to 2$ across the first two hops: $len ([]) = 0$ , $len ([7]) = 1$ , $len ([8, 7]) = 2$ . The origin AS ( $7$ ) is always the right-most element. ✔

Cell I — Real-world word problem

Worked example Cell I: a small ISP's routing choice

"CoffeeNet" (AS500) is a small ISP. To reach Netflix's prefix N it has:

a route via its transit provider BigTelco (AS600), 3 AS hops — BigTelco charges CoffeeNet per gigabyte;
a route via a settlement-free peer LocalIX-member (AS610), 4 AS hops — no charge;
no customer route (CoffeeNet is small, its customers don't reach Netflix).

CoffeeNet's operator wants to minimise cost. Which route should they prefer, and how do they enforce it?

Forecast: cheaper or shorter?

Rank by money: the free peer route costs nothing; the provider route costs per-GB. Cheapest = peer route. Why this step? Real routing decisions are business decisions first. The operator encodes "cheapest first" into LOCAL_PREF.
Set LOCAL_PREF (using the default convention): peer $= 200$ , provider $= 100$ . Now the peer route wins step 1 outright. Why this step? LOCAL_PREF is the operator's direct policy knob and sits at the top of the decision ladder — it overrides the fact that the peer path is one hop longer.
Result: CoffeeNet sends Netflix-bound traffic over the free peer link, even though it is $4$ hops vs $3$ . Why this step? Because LOCAL_PREF is decided on rung 1 and the hop-count comparison lives on rung 2, the money-based preference is guaranteed to override the shorter provider path — so setting LOCAL_PREF is sufficient, no other configuration is needed to realise the cheapest-exit policy.

Verify: $LOCAL_PREF_{peer} = 200 > LOCAL_PREF_{prov} = 100 \Rightarrow$ peer route, despite $4 > 3$ hops. Cost-minimising and "policy over distance" agree. ✔

Cell J — Exam twist: spot the illegal path

Worked example Cell J: is this AS_PATH valley-free?

A valley-free path is one legal on the real internet under Gao–Rexford. Classify each hop as up (customer→provider), peer (peer→peer), or down (provider→customer), reading from the origin outward, and decide which path is legal.

Path 1: origin AS3 → AS2 → AS1, where AS3 is a customer of AS2, and AS1 is a customer of AS2. Hop pattern: up (AS3→AS2), then down (AS2→AS1).
Path 2: origin AS3 → AS2 → AS1 → AS0, where AS3 is a customer of AS2 (up), AS1 is a customer of AS2 (down), and AS0 is a provider of AS1 (up again).

Forecast: which of these two shapes can actually exist on the internet, and which is banned?

Recall the valley-free shape: a legal path is $(up)^{*} (peer)^{?} (down)^{*}$ — zero or more up-hops, then at most one peer hop, then zero or more down-hops. Never up after down. Why this step? "Up after down" means some AS in the middle re-advertised a provider-learned route back up to a provider — Gao–Rexford export (the table above) forbids exactly that, so such a path can never form.
Classify Path 1: up, down. That is one peak and zero valleys → it matches the legal template. Legal. Why this step? A single peak (climb then descend) is the canonical valley-free shape; nothing after the descent tries to climb again.
Classify Path 2: up, down, up. The final up comes after a down → a valley → it violates the template. Illegal. Why this step? For Path 2 to exist, AS1 would have to take the route it learned from its provider AS2 and export it up to its provider AS0 — a forbidden export (provider-learned routes go only to customers). The route would be filtered at AS1 (Cell E), so Path 2 never propagates in reality.

Verify: counting valleys (a down-hop later followed by an up-hop): Path 1 has $0$ valleys $\Rightarrow$ legal; Path 2 has $1$ valley $\Rightarrow$ illegal. The legal shape is exactly $(up)^{*} (peer)^{?} (down)^{*}$ . ✔

Recall

Recall Which decision-ladder rung actually chose each cell's winner?

Cell A router picks by which rung? ::: Rung 1, LOCAL_PREF (policy); path length never consulted. Cell B router picks by which rung? ::: Rung 2, shortest AS_PATH, only because LOCAL_PREF tied. Cell C router picks by which rung? ::: Rung 7 (oldest route), confirmed again by rung 8 (lowest router-ID). Cell D outcome? ::: Route discarded by the loop test before the decision process even runs. Cell G: why does the smallest-MED route (R10) win, really? ::: Not on MED — R10 wins at step 6 on lowest IGP metric; MED only pruned R8 among AS70's routes. What are the three ORIGIN codes, best to worst? ::: IGP (0), then EGP (1), then INCOMPLETE (2); lower wins.

See also the parent BGP topic note, and for contrast Distance Vector and Count-to-Infinity, Hot-potato vs Cold-potato routing, and Route flap damping and BGP convergence.