BGP — path vector, AS, policy routing: Exercises

Notation refresher (so nothing is unearned)

Definition The symbols and terms we reuse below

AS = Autonomous System = one independently-run network, identified by a number (ASN). We write $A S_{5}$ or just "AS5".
Prefix = a block of IP addresses, e.g. 200.0.0.0/24. The route "how to reach this block" is what BGP advertises.
AS_PATH = an ordered list like $[X, Y, Z]$ . Read right-to-left: the prefix originates in $Z$ , was handed to $Y$ , then to $X$ . The leftmost AS is the most recent one to touch the route.
prepend = stick your own ASN on the front (left) of the list before passing it on.
eBGP (external BGP) = the BGP session that runs between routers in two different ASes. When a route crosses an eBGP link into a new AS, that AS prepends its ASN. An "eBGP hop" = one such AS-to-AS step.
iBGP (internal BGP) = BGP that runs between routers inside the same AS, to carry externally-learned routes across that AS. Crossing iBGP does not add to the AS_PATH (you're still in the same AS).

Definition The route attributes BGP compares (define each before use)

When one AS has several candidate routes to the same prefix, each route carries these numbers/flags. BGP uses them, in a fixed order, to pick one:

LOCAL_PREF = a number the AS attaches internally to a route; higher = more preferred. It is the AS's own policy knob (usually set by relationship: customer > peer > provider). It is the first thing BGP compares.
AS_PATH length = how many AS hops long the path is (count the entries). Fewer = shorter.
MED (Multi-Exit Discriminator) = a hint number a neighboring AS attaches when it connects to you over multiple links, saying "please enter me through this link (lower MED)." Lower is preferred. It is only meaningful — and by default only compared — between routes that came from the same neighboring AS.
eBGP over iBGP = prefer a route learned directly from another AS (eBGP) over the same route relayed internally (iBGP), because the eBGP one is "closer to the source."
IGP cost to egress = the internal distance (measured by the AS's intra-domain protocol like OSPF) from this router to the egress — the border router where traffic actually leaves the AS. Lower = the exit is nearer. Preferring the lowest is hot-potato routing (get traffic off your network fast).
Router-ID = a unique number identifying each router; used last as a purely deterministic tie-break so the choice is repeatable. Lower wins.

Formula Gao–Rexford export rules (full table)

"Export" = advertise a route to a neighbor. An AS exports a route depending on who it learned the route from and who it would send it to:

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

The one rule to remember: a customer-learned route goes to everyone; a peer- or provider-learned route goes only to customers. Why: you happily tell paying customers about every route (you earn money carrying their traffic), but you refuse to spend money carrying traffic between two parties who don't pay you.

We will lean on one picture for the geometry of "valley-free" paths — introduced when we first need it.

Level 1 — Recognition

L1.1 Read an AS_PATH

Recall Solution

What we do: apply the right-to-left reading rule.

(a) The origin is the rightmost entry → AS56.
(b) The most recent forwarder is the leftmost entry → AS12.
(c) AS hop count = number of entries in the list = 3.

Why: each AS prepends itself as it forwards, so the list grows leftward and the origin stays pinned on the right.

L1.2 Loop test

Recall Solution

Rule: accept $⟺ X \in / P$ . Here $X = A S_{34}$ and the path is $P = [56, 34, 90]$ . Since $34 \in P$ , AS34 rejects it — accepting would create a loop (the route already went through AS34 once).

Level 2 — Application

L2.1 Prepend chain

Recall Solution

Step by step (each eBGP hop prepends the receiving AS):

AS90 originates: $[90]$
AS34 receives, prepends 34: $[34, 90]$
AS12 receives, prepends 12: $[12, 34, 90]$
AS7 receives, prepends 7: $[7, 12, 34, 90]$

AS hop count = 4. Read right-to-left, this says: originates in AS90 → AS34 → AS12 → AS7. ✔

L2.2 Two routes, tie-break by path length

Recall Solution

What we do: since LOCAL_PREF (step 1) ties, we fall to step 2 — shortest AS_PATH.

$∣ R_{a} ∣ = 3$ , $∣ R_{b} ∣ = 2$ .
Fewer AS hops wins → R_b (2 hops) is chosen.

Why this step matters: AS_PATH length is a tie-breaker, used only because policy (LOCAL_PREF) didn't already decide. Here it did the job because policy was a tie. (MED — the lower-is-better neighbor hint defined above — was equal, so it did not intervene either.)

Level 3 — Analysis

L3.1 Policy beats distance

Recall Solution

Step 1 — LOCAL_PREF (highest wins):

R1 (provider) → 100
R2 (peer) → 200
R3 (customer) → 300

R3 has the highest LOCAL_PREF (300). Decision made at step 1 — R3 wins. We never even reach step 2.

Why: sending traffic toward a customer means the customer pays AS100 for transit, so it's the most profitable exit. AS100 prefers it even though R3 is the longest path (4 hops vs 2). This is policy routing in one line: money first, distance second. ✔

L3.2 Valley-free check

Recall Solution

First, the shape of a valley-free path. In the figure, each circle is an AS and its height shows its tier: customers sit low, providers sit high. Follow the route left-to-right: it climbs UP on customer→provider hops (green labels), may take at most one PEER hop across the top (coral label), then descends DOWN on provider→customer hops (lavender labels). The red arrow marks the one thing that is forbidden — going up again after you have already gone down, which digs a "valley."

Figure — BGP — path vector, AS, policy routing

What "valley-free" means (from the picture): you may go up (customer→provider) zero or more times, then take at most one peer hop, then go down (provider→customer) zero or more times. Never up again after you've gone down. A "down then up" is a valley — it means some AS in the dip is giving free transit to two parties who don't pay it, which no AS does.

Now classify the given sequence:

customer→provider = UP ✅
provider→customer = DOWN (we have now started descending)
customer→provider = UP again ❌ — this is up after down = a valley.

Verdict: NOT valley-free. The illegal step is the third hop: after the route already went downhill in step 2, step 3 goes back uphill, forming a valley. The AS at the bottom of that valley (the customer in step 2 = provider in step 3) would have to carry traffic between two networks that don't pay it — Gao–Rexford export rules (see the table above) forbid advertising the route that way, so this path can't exist. ✔

Level 4 — Synthesis

L4.1 Combine export policy + loop test + selection

Recall Solution

(a) Propagation (each eBGP hop prepends):

AS70 originates: $[70]$
AS400 (customer of AS100) receives from its customer AS70, prepends: $[400, 70]$
AS100 receives from its customer AS400, prepends: $[100, 400, 70]$

So AS100 holds [100, 400, 70].

(b) Export to provider AS200? The route was learned from a customer (AS400). Gao–Rexford table (row "learned from Customer"): a customer-learned route may be exported to everyone — customers, peers, and providers. So yes, AS100 may advertise $[100, 400, 70]$ up to AS200. It becomes $[200, 100, 400, 70]$ at AS200 after AS200 prepends.

Why AS100 is happy to do this: the route reaches AS100's own customers (AS400, AS70), and advertising it upward lets the whole internet reach those paying customers — more traffic to customers = more money.

(c) AS200 advertises back toward AS100: the path arriving at AS100 would be $[200, 100, 400, 70]$ . AS100 runs the loop test: is $100 \in [200, 100, 400, 70]$ ? Yes. → AS100 rejects it. The AS_PATH is its own proof of non-loopiness; no global map needed. ✔

L4.2 Design a LOCAL_PREF scheme

Recall Solution

(Here $LP$ is just shorthand for LOCAL_PREF, the policy number defined above — higher wins.)

Requirement: customer > peer > provider in preference, and this must dominate path length. Since LOCAL_PREF is step 1 and AS_PATH is step 2, any assignment with $LP_{customer} > LP_{peer} > LP_{provider}$ achieves this — path length can never override it.

A valid choice: customer = 300, peer = 200, provider = 100.

Proof for the extreme case:

9-hop customer route: $LP = 300$ .
1-hop provider route: $LP = 100$ .
Step 1 compares LOCAL_PREF first: $300 > 100$ → customer route wins immediately. BGP never reaches step 2, so the 9-vs-1 hop difference is irrelevant. ✔

Why it works: the decision process is strictly lexicographic (dictionary order) — it fully resolves at the first step where values differ. Since LOCAL_PREF differs here, nothing below it matters.

Level 5 — Mastery

L5.1 Full six-step selection with realistic data

Worked example Problem

AS500 has four routes to P = 150.0.0.0/16. Attributes (all defined in the refresher):

Route	Neighbor type	LOCAL_PREF	AS_PATH len	MED	from-AS	eBGP?	IGP cost to egress	Router-ID
W	provider	100	2	30	AS10	yes	5	1
X	peer	200	5	10	AS20	yes	8	2
Y	peer	200	5	10	AS20	yes	3	3
Z	customer	200	4	50	AS30	yes	2	4

Walk the full BGP decision process and name the winner.

Recall Solution

Apply the six steps in order; drop losers at each step.

Step 1 — Highest LOCAL_PREF. Values: W=100, X=200, Y=200, Z=200. W (100) is lowest → eliminate W. Survivors: X, Y, Z (all 200).

Step 2 — Shortest AS_PATH. Lengths: X=5, Y=5, Z=4. Z=4 is strictly shortest → eliminate X and Y, leaving Z.

Only one route survives step 2 → Z is the best path.

Sanity note on the trap: X and Y (peers, LP 200, 5 hops) had equal LOCAL_PREF to Z, so step 1 did not eliminate them. It was step 2 (shortest AS_PATH) that decided, because Z's path (4) is shorter than X/Y's (5). MED, eBGP/iBGP, IGP cost, and Router-ID were never consulted — the process halted at step 2.

Winner: Z. ✔

L5.2 When do the lower steps actually run?

Recall Solution

Now X and Y are tied through step 2. Continue down the ladder:

Step 3 — Lowest MED. MED is compared here only because both routes came from the same neighbor AS (AS20) — that is the condition for MED to be comparable. Both MED = 10 → tie.

Step 4 — eBGP over iBGP: both are learned over eBGP (directly from another AS) → tie.

Step 5 — Lowest IGP cost to egress (hot-potato): X's internal cost to its exit = 8, Y's = 3. Y is lower → Y wins.

This is hot-potato routing: among otherwise-equal exits, dump the traffic out the nearest egress (cheapest internal cost) to get it off your network fast. Winner: Y. ✔

(Step 6, lowest Router-ID, would only trigger if IGP costs also tied.)

Consolidation

Recall One-line summary of the decision ladder

Q: In what order does BGP break ties? ::: 1 LOCAL_PREF (policy/money), 2 shortest AS_PATH, 3 lowest MED (same-neighbor only), 4 eBGP over iBGP, 5 lowest IGP cost (hot-potato), 6 lowest Router-ID.

Recall The single most-tested fact

Q: Why can a longer AS_PATH win? ::: Because LOCAL_PREF (step 1) outranks AS_PATH length (step 2); a customer route (high LOCAL_PREF, earns money) beats a shorter provider route (low LOCAL_PREF).

See also: Distance Vector and Count-to-Infinity (why path vector exists), Autonomous Systems and ASN allocation, IP addressing and CIDR prefixes, Internet topology — Tier-1, transit, peering, OSPF and link-state routing (the intra-domain contrast).