BGP — path vector, AS, policy routing: Visual walkthrough

We start with a made-up internet of a handful of networks and slowly discover the exact rules real BGP uses.

Step 1 — What is an AS, and what does "reach a prefix" even mean?

WHAT. The internet is not one machine. It is a pile of separately-owned networks. Each such network is called an Autonomous System (AS) and gets a unique number, its ASN — think of it as a country with its own government. Each AS owns some blocks of addresses called prefixes (e.g. 200.0.0.0/24 means "all addresses starting with 200.0.0").

WHY start here. Before we can route between networks we must agree on the two nouns of the whole story: the thing we're trying to reach (a prefix) and the players passing messages (the ASes). Every rule later is about ASes telling each other "I can reach that prefix."

PICTURE. Five circles = five ASes. The green tag 200.0.0.0/24 sits inside AS50 — that AS originates the prefix; it is the home of those addresses. Everyone else must find a way to AS50.

Figure — BGP — path vector, AS, policy routing

Step 2 — The naive idea: just advertise a distance (and why it breaks)

WHAT. The simplest possible protocol: each AS shouts to its neighbours "I can reach 200.0.0.0/24, and it costs me $c$ hops." A neighbour adds 1 and re-shouts $c + 1$ . This is distance vector — the message is just a (prefix, number).

WHY show a broken idea first. You only appreciate the real fix once you feel the pain it solves. The number tells you how far but says nothing about which networks the traffic crosses.

PICTURE. Watch the failure. AS1—AS2—AS3 all know a route to the prefix. Now the link to the origin dies (red X). AS2's real route is gone, but AS3 is still advertising "I can reach it, cost 3!" So AS2 believes AS3, sets cost 4; AS3 then hears 4 and bumps to 5… the number crawls upward forever. This is count-to-infinity: stale beliefs bounce between routers because nobody can see whose path they're trusting.

Step 3 — The fix: carry the whole list of ASes (path vector)

WHAT. Change one thing in the message. Instead of a number, carry the entire ordered list of ASes the route passes through. We call this list the AS_PATH. A route to our prefix now looks like:

$which prefix 200.0.0.0/24 AS_PATH = [last AS to hold it 5, origin 50]$

Read it right-to-left: the prefix is born in AS50, then handed to AS5. The rightmost entry is always the origin.

WHY this exact change. The list is a receipt of everywhere the route has been. That receipt is what kills loops — no global map needed, the proof travels inside the message itself.

PICTURE. Same chain as before, but now each hop's message shows the growing list. When AS5 tells AS2, the message is [5,50]; AS2 makes it [2,5,50]. You can literally see the trail.

Step 4 — Prepend: how the list grows, term by term

WHAT. When an AS $X$ passes a route it learned (with path $P$ ) on to another AS over eBGP, it sticks its own number on the front:

$P^{'} = [X] ∥ P$

Here $∥$ means "glue lists together", $X$ is my own ASN, and $P$ is the path I received. So [5,50] arriving at AS2 becomes [2,5,50] leaving AS2.

WHY prepend, and why the front. Two reasons, both earned:

The next AS must be able to run a "am I already in here?" test — so my identity has to be in the list.
Putting it at the front keeps the list in travel order (newest first, origin last), so the length $∣ P ∣$ is a clean count of AS hops we can use as a tie-breaker later.

PICTURE. A single message flowing left to right; at each router a new coloured box is snapped onto the left end of the list. The origin box (yellow) never moves — it stays pinned on the right.

Step 5 — Loop prevention: the list is the proof

WHAT. When AS $X$ receives a route whose path is $P$ , the decision is one line:

$accept ⟺ X \in / P$

In words: "if I'm already somewhere in this list, taking the route would send traffic through me a second time — a loop — so I refuse it." The symbol $\in /$ means "is not a member of".

WHY this works instantly. Because the receipt from Step 4 records everyone who touched the route, a loop is visible right in the message. No timers, no counting to infinity, no waiting for a number to crawl up — one membership check, done.

PICTURE. AS3 tries to advertise the route back toward AS1. The message reaching AS1 carries [3,2,1,50]. AS1 scans the list, spots its own 1 (red highlight), and drops the route. The would-be loop is severed at the instant it's proposed.

Step 6 — Money enters: not every route is allowed to be told to everyone

WHAT. So far we could reach everything loop-free. But real ASes have business relationships, and they change which routes you're even willing to advertise:

Customer→Provider: the customer pays the provider to carry its traffic everywhere.
Peer↔Peer: two ASes swap their own + their customers' traffic for free — but neither gives the other a free ride to the rest of the internet.
Provider→Customer: the provider hands the customer everything (customer paid for it).

The export rule (Gao–Rexford):

$a route learned from a \underline{customer} \to export to everyone$ $a route learned from a \underline{peer or provider} \to export only to customers$

WHY. You gladly advertise a customer route to the world — you earn money carrying that traffic. But you will not spend your money/links carrying traffic between two parties who don't pay you. So peer- and provider-learned routes are handed only to your paying customers.

PICTURE. Arrows between ASes labelled $ (customer pays up) and free (peer link). A route learned across the free peer link is stamped "customers only" — a red barrier blocks it from being re-exported up to a provider.

Step 7 — The decision: policy first, distance second

WHAT. When several allowed routes reach the same prefix, BGP picks one in strict priority order. The top two are all we need for the flagship result:

$1) highest LOCAL_PREF \Rightarrow 2) shortest AS_PATH \Rightarrow \dots$

LOCAL_PREF is a number you assign to a route based on where it came from — a policy knob. Set customer routes high, provider routes low, so "cheapest for me" wins.
AS_PATH length (the count from Steps 3–4) is only a tie-breaker, used after policy.

WHY this ordering is the whole point. Every earlier protocol you met (Dijkstra, OSPF, RIP) minimizes a distance. BGP flips that: money first, distance second. A long route through a paying customer beats a short route through a provider you pay.

PICTURE. Three routes to prefix P line up. Bars show LOCAL_PREF (tall = preferred). The longest AS_PATH (customer route, 4 hops) has the tallest LOCAL_PREF bar and is crowned the winner — the shortest route loses. That single frame is policy routing.

The one-picture summary

Everything above, compressed: a message flows across ASes gaining path entries (Steps 3–4), a router rejects a route containing its own ASN (Step 5), export is filtered by money relationships (Step 6), and among survivors LOCAL_PREF beats AS_PATH length (Step 7).

Recall Feynman retelling (say it out loud)

The internet is thousands of separate networks that don't trust each other. First idea: shout "I can reach that, it costs 3" — but a number lies when a link dies, so the cost crawls to infinity. Fix: instead of a number, mail the whole list of networks the route crossed. Each network that forwards the route staples its own name to the front of the list. Now a loop is obvious — if I open the letter and see my own name already inside, forwarding it would loop, so I throw it away. That single membership check replaces all the count-to-infinity mess. Then reality bites: networks have contracts. I'll advertise a paying customer's route to everybody (I earn from it) but I'll only hand peer/provider routes to my own customers (I won't pay to carry strangers' traffic). Finally, when several legal routes arrive, I don't pick the shortest — I pick the one my LOCAL_PREF rates highest (the cheapest for me), and only break ties by path length. Money first, distance second. That's BGP.

Recall Quick self-test

Path arriving at AS7 is [3,7,2,50] — accept or reject? ::: Reject, because $7 \in$ the path (loop). Route learned from a peer — may I export it to my provider? ::: No, only to customers. A 2-hop provider route vs a 5-hop customer route — which wins? ::: The 5-hop customer route (higher LOCAL_PREF beats shorter AS_PATH). What does prepending do and to which end? ::: Adds my own ASN to the front (left end) of the AS_PATH.