--- title: 'Border Gateway Protocol' source: 'https://academia.sh/en/courses/switching-and-routing/border-gateway-protocol' course: 'Switching and Routing' language: en updated: '2026-08-17T18:07:19+00:00' license: 'CC BY-SA 4.0' --- # Border Gateway Protocol At an autonomous system border, the decision looks not at the shortest path but at policy: a transit ban still delivers all forty of the forty packets but raises total hops from 83 to 92; when a border advertisement is withdrawn, 14 packets fall into a black hole; and a single node's route leak brings hops back down to 83 while routing 7 packets off the contracted path. The previous two lessons placed two routing families side by side. Distance vector learned its neighbor's distance sequence, link state carried the topology itself; their rounds differed, but both searched for the same thing and eventually arrived at **the same table**: the first hop of the **shortest path** to every destination. This lesson's question starts exactly here. What if the shortest path is **not wanted**? A network is not obligated to carry its neighbor's traffic; when it does, that has a cost and a contract. The Border Gateway Protocol's measure is therefore not the shortest path but the **permitted path**, and the permitted path is most often longer. ## A Border Is a Decision Boundary The autonomous system concept was established in the **How the Internet Works** course; its definition is not repeated here. What matters here is this distinction: **inside** an autonomous system, the table is built on a **metric** — hop count, link cost, latency. **Beyond** the border, **contract** takes the metric's place. What crosses the border is not a distance but an **advertisement**. The advertisement says three things: which destination is reached, which autonomous systems are passed through to reach it, and who the **next hop** is. A neighbor can accept this advertisement, modify it, or drop it. If it accepts, it writes a row into its own table; if it drops it, it never learns a path to that destination at all. And **nothing verifies** the advertisement. The Application Layer Protocols course said this about what is written in a message; at the border, the same gap applies to the advertisement. Whatever a neighbor advertises, the table writes it. The advertisement carrying the **path** does two jobs at once. The first is policy: the receiving side accepts or drops the advertisement by looking at the path's intermediate position; this is what this lesson measures. The second is loop detection, and it is directly related to the course's third claim. Throughout the course, a loop has been counted as **a disagreement between at least two tables**; no device could put a packet into a loop by itself, because no device could look past its own table. At the border, this changes: because the advertisement carries the path itself, an autonomous system can see **its own name** in an incoming advertisement's path. The moment it sees it, it drops the advertisement. This is the place where a loop can be detected by looking at a single table, and it has no counterpart inside — the distance vector family's counting-to-infinity flaw is born exactly from the absence of this information. ## Setup: Three Autonomous Systems The course's eight-node network is split into three autonomous systems. The split does not change the physical links; it only determines which link is a **border link**. ```text # taught transcript, not run autonomous system nodes internal links border links north a b c d a-b b-c c-d d-e (middle), b-f (middle), h-a (south) middle e f e-f d-e (north), b-f (north), f-g (south) south g h g-h f-g (middle), h-a (north) south -> north advertisement north -> south advertisement destination g destination c path south path north next hop h next hop a middle -> north advertisement (learned from south, not passed on under the transit ban) destination g path middle south next hop f ``` The third advertisement is the lesson's core. The middle autonomous system knows a path to south and can advertise it to north. If it does, it takes on **carrying** the traffic between north and south. If it will not carry it, it does not pass on the advertisement, and north never learns that path. ## The Permitted Path A path's autonomous-system sequence is the node sequence translated into autonomous systems, with repetitions compressed. The sequence for path `g-f-b-c` is `south middle north`, for path `g-h-a-b-c` it is `south north`. **The rule is a single line:** when an autonomous system declares it will not carry transit, every path in whose sequence it sits in an **intermediate position** is eliminated. The autonomous system at the start and at the end does not count as intermediate — carrying your own traffic is not transit. The result shows up in the packet going from `g` to `c`. The shortest path is `g-f-b-c`, three hops, and it passes through middle. If middle does not carry transit, this path is eliminated; the shortest remaining **permitted** path is `g-h-a-b-c`, four hops. **The path got one hop longer, and the packet still arrived.** This is what is measured. The measurement's assumptions: - **RT61** — Eight nodes, nine links: seven form the `a–b–c–d–e–f–g–h–a` ring, the eighth is the `b–f` chord that cuts the ring. The topology is the same throughout the course. - **RT62** — Nodes are split into three autonomous systems: north `a b c d`, middle `e f`, south `g h`. The autonomous systems are referred to by fictional names, not numbers. - **RT63** — Policy consists of a single rule: the **transit ban**. The source's and destination's own autonomous system does not count as an intermediate position. - **RT64** — The oracle does not change; reality is always the first hop of the **shortest path**. The policy table is a separate table, and what is measured is the difference between the two. - **RT65** — The forty source–destination pairs come from the course's core generator. The same pair can come up more than once, and each occurrence is a **separate packet**. The hop limit is 12. - **RT66** — The leak is **a single node** not honoring the ban: `f` passes on the advertisement despite the middle autonomous system's promise not to carry transit. The other middle node, `e`, keeps the promise. - **RT67** — In the set of forty packets, the smallest measurable difference is `1/40 = 0.025`; no difference smaller than this is claimed. ## Measurement ```python """Policy-based routing: not the shortest path, the permitted path.""" SEED = 20260810 NODES = "abcdefgh" LINKS = [("a", "b"), ("b", "c"), ("c", "d"), ("d", "e"), ("e", "f"), ("f", "g"), ("g", "h"), ("h", "a"), ("b", "f")] AS_OF = {"a": "north", "b": "north", "c": "north", "d": "north", "e": "middle", "f": "middle", "g": "south", "h": "south"} HOP_LIMIT = 12 def generator(seed): d = seed % 2147483646 + 1 def r(n): nonlocal d d = (d * 48271) % 2147483647 return d % n return r def pairs(count=40): r, result = generator(SEED), [] while len(result) < count: x, y = NODES[r(8)], NODES[r(8)] if x != y: result.append((x, y)) return result def neighbors(links): k = {u: set() for u in NODES} for x, y in links: k[x].add(y) k[y].add(x) return k def table(no_transit=(), closed=(), leaking=()): """The first hop of the shortest PERMITTED path for every node to every destination.""" kom, t = neighbors(LINKS), {} for u in NODES: for h in NODES: if u == h: continue banned = {v for v in NODES if AS_OF[v] in no_transit and AS_OF[v] not in (AS_OF[u], AS_OF[h]) and v not in leaking} prev, frontier, seen = {}, [u], {u} while frontier: nxt = [] for x in frontier: for v in sorted(kom[x]): if tuple(sorted((x, v))) in closed or v in seen: continue if v in banned and v != h: continue seen.add(v) prev[v] = x nxt.append(v) frontier = nxt if h not in prev: continue step = h while prev[step] != u: step = prev[step] t[(u, h)] = step return t def forward(source, dest, t): kom, u, path, crossed = neighbors(LINKS), source, [source], [] while u != dest: if len(path) > HOP_LIMIT: return "loop", path s = t.get((u, dest)) if s is None or s not in kom[u]: return "black hole", path if (u, s) in crossed: return "loop", path crossed.append((u, s)) u = s path.append(u) return "reached", path def measure(t, no_transit): tally, hops, off_contract = {"reached": 0, "loop": 0, "black hole": 0}, 0, 0 for x, y in pairs(): fate, path = forward(x, y, t) tally[fate] += 1 hops += len(path) - 1 if {AS_OF[v] for v in path[1:-1]} & (set(no_transit) - {AS_OF[x], AS_OF[y]}): off_contract += 1 return tally, hops, off_contract REGIME = (("no policy", (), (), ()), ("middle bans transit", ("middle",), (), ()), ("middle bans transit, border closed", ("middle",), (("a", "h"),), ()), ("middle bans transit, f leaks", ("middle",), (), ("f",))) print(f"{'regime':<34s} {'rows':>5s} {'reached':>7s} {'loop':>6s} " f"{'black hole':>11s} {'hops':>5s} {'off contract':>13s}") for name, nt, cl, lk in REGIME: t = table(nt, cl, lk) s, h, o = measure(t, nt) print(f"{name:<34s} {len(t):5d} {s['reached']:7d} {s['loop']:6d} " f"{s['black hole']:11d} {h:5d} {o:13d}") base, narrow, leaked = table(), table(("middle",)), table(("middle",), (), ("f",)) print() print(f"of the 56 rows, " f"{sum(1 for k in base if base[k] != narrow.get(k))} diverge from policy, " f"{sum(1 for k in base if base[k] != leaked.get(k))} from the leak") print(f"{'pair':>7s} {'packets':>7s} {'no policy':>12s} {'policy':>11s}" f" {'leaking':>10s}") for x, y in sorted(set(pairs())): y0, y1, y2 = (''.join(forward(x, y, t)[1]) for t in (base, narrow, leaked)) if y0 == y1 == y2: continue n = sum(1 for c in pairs() if c == (x, y)) print(f"{x+'->'+y:>7s} {n:7d} {y0:>12s} {y1:>11s} {y2:>10s}") ``` ``` regime rows reached loop black hole hops off contract no policy 56 40 0 0 83 0 middle bans transit 56 40 0 0 92 0 middle bans transit, border closed 40 26 0 14 48 0 middle bans transit, f leaks 56 40 0 0 83 7 of the 56 rows, 5 diverge from policy, 1 from the leak pair packets no policy policy leaking b->g 2 bfg bahg bfg g->b 1 gfb ghab gfb g->c 2 gfbc ghabc gfbc g->d 2 gfed ghabcd gfed ``` ## A Longer Path Is Not a Flaw The second row is the lesson's main measure. When the transit ban takes effect, the table is still **56 rows**, all forty of the forty packets **still arrive**, loop is **0**, black hole is **0**. The only thing that changes is total hops: **from 83 to 92**, nine hops. The bottom table shows where the nine hops come from. Only **5** of the fifty-six rows diverge, and among the measured forty packets, this divergence touches **four pairs**, **seven packets** in total. Path `g->d` climbs from three hops to five, `g->c` from three to four, `b->g` and `g->b` from two to three. The other thirty-three packets never see the policy at all, because their paths did not pass through the middle in an intermediate position to begin with. This lesson has to be read together with the course's axis of measurement. What sets the axis is the **packet's fate**: reached, loop, black hole. Policy changed none of these three numbers. In a set of forty packets, the smallest measurable difference is `0.025`, and the fate difference here is exactly **zero**. Hops are the measure of the cost, not of the fate. The converse of this is also true: **the shortest path is not a goal.** The path through the chord was two hops shorter, but the two ends of that chord belonged to two separate autonomous systems, and carrying the traffic in between had a cost. The nine hops are the price of not paying that cost. ## When Policy Is Set Too Narrow The third row sharpens the distinction. In this regime, the transit ban still stands, and in addition, the `h–a` border link between north and south is not advertised — the two neighbors advertise no destination to each other. The table drops from **56 rows to 40**. For the sixteen missing rows, **there is no permitted path**: every path from north to south either passes through the middle (banned) or goes through `h–a` (not advertised). In the measurement, this shows up as **14 black holes**; only **26** of the forty packets arrive. The hop count dropping from 92 to **48** is not an improvement. A dying packet stops spending hops; a low hop count here is exactly the sign of **loss**. The same number saying two different things in two regimes is also the answer to why looking at a single counter is not enough. The distinction is this: **a policy that lengthens the path is not a flaw; a policy that makes a destination unreachable is a flaw.** Both are written in the same language, both have correct syntax, both take effect without error. Only measurement shows the difference. ## Route Leaks and Restrictions The fourth row measures a configuration fault. A **route leak** is an autonomous system passing on to another neighbor an advertisement it learned from one neighbor, when its contract says it should not. Here, node `f` does not honor the middle autonomous system's transit ban; `e` does. The one breaking the ban is **a single node**. The result looks surprisingly clean: **56 rows, 40 reached, 0 loop, 0 black hole.** Total hops drop from **92 to 83**. Only **1** of the fifty-six rows diverges from the no-policy table — meaning the leak brings the table back to its **no-policy state**, short by just one row. And **7 packets** pass through the middle in an intermediate position: the bottom table's right column gives these paths, `bfg`, `gfb`, `gfbc`, `gfed`. This is not an attack, it is a **configuration fault**: the rule is written, the syntax is correct, the session is up, no alarm goes off. The attack side is the subject of the **Network Security** course and is not carried here. Here are the counted surfaces and the restriction that closes each one. **First surface — traffic carried off contract.** Seven packets pass through an autonomous system that declared it would not carry them. **Restriction:** passing an advertisement learned from one neighbor on to another neighbor is limited by a per-neighbor **prefix filter**; a prefix not in the filter is not advertised. A second restriction is a per-neighbor **cap on advertisement count** — a leak most often arrives as a sudden spike in advertisement count, and the session shuts itself down automatically when the cap is exceeded. **Second surface — a leak that looks like an improvement.** Hops dropped from 92 to 83, no packet is lost, the table row count stayed at 56. A counter watching latency reports **improvement**. **Restriction:** what is tracked should not be hops but the **autonomous-system sequence**; path `g->c`'s sequence comes out as `south middle north` where `south north` was expected. This difference shows up in the table, not in the counter. **Third surface — the advertisement is not verified.** The advertisement says "this destination is reached through me," and nothing verifies it. **Restriction:** a **signed registry** that pairs a prefix's owner with the autonomous system authorized to advertise it, and a filter that checks the advertisement against this registry. A second restriction is **rejecting advertisements that carry your own autonomous system in their path** — an advertisement that comes back is a sign of a loop. **Fourth surface — policy set too narrow.** The third regime's 14 black holes are a configuration fault, and the opposite of a leak. **Restriction:** before a policy change is put into effect, **counting the number of permitted paths** for every destination; if any destination's count drops to zero, the change is not rolled out. ## Summary - At an autonomous system border, the decision shifts from metric to policy; what crosses the border is not a distance but an **advertisement**, and nothing verifies the advertisement. - A path is eliminated when an autonomous system that does not carry transit sits in an **intermediate position** in its autonomous-system sequence; the source's and destination's own autonomous system does not count as intermediate. - The transit ban still delivers all forty of the forty packets and raises total hops from **83 to 92**; **5** of the 56 rows diverge, and the divergence touches **four pairs** and **seven packets**. **A longer path is not a flaw.** - When the border advertisement is withdrawn, the table drops to **40 rows** and **14 packets** fall into a black hole; hops dropping to 48 is a sign of loss, not improvement. - A single node's route leak brings the table back to its no-policy state, **short by one row**: hops drop to 83, **7 packets** travel off the contracted path, and no counter reports it. ## Next Step In this lesson, policy was applied **inside a single table**: every node had one table, and one destination had a single row in it. Policy changed which next hop that row pointed to. But what if the same device had **more than one table**? The next lesson measures the same address going to two separate decisions on the same device: when the table is split into instances, which packet falls into which table, what happens when separate tables share the same links, and how the instance count grows the row count kept.