Border Gateway Protocol

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.

# 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

"""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.