Routing Instances

The previous lesson applied policy inside a single table. Every node had one table, every destination had a single row in that table, and policy changed which next hop that row pointed to. The Border Gateway Protocol rewrote the table, but it did not change how many tables there were.

This lesson’s question is: what happens when the same device keeps more than one table? Then a destination address does not correspond to a single decision but to as many decisions as there are tables — and the decisions know nothing of each other. What is measured is this divergence.

One Device, More Than One Table

A routing instance is an independent routing table kept inside a single device. It has three parts: a link set that says which of the device’s links it may use, a table computed from that link set, and a port mapping that determines which instance an incoming packet falls into.

The third part is the point in the lesson most often overlooked. Which instance a packet falls into is not read from its address. The address is the same in both instances; what makes the distinction is which port the packet came in on. The device first picks the instance, then does the longest prefix match in that instance’s table. The two steps are separate, and the second knows nothing of the first.

# taught transcript, not run

node b's routing instances

instance      port      destination   next hop
management    1 2       e             f
management    1 2       f             f
measurement   3 4       e             c
measurement   3 4       f             a
guest         5         e             f
guest         5         f             f

an incoming packet falling into an instance
  port 1 -> management instance -> next hop for destination e is f
  port 3 -> measurement instance -> next hop for destination e is c
  the destination address is the same in both and never enters the choice

The reasoning for splitting is scope. Measurement traffic does not need to use the same path as management traffic; it may be desired that guest traffic never go out on some links at all. Doing this with an address plan means writing a separate filter at every node; doing it with instances means narrowing the link set and letting the table compute itself accordingly.

Same Address, Two Decisions

The setup builds three instances. management uses all of the device’s links. measurement does not use the chord (b–f) — that link is not mapped to this instance. guest does not use the d–e link. All three instances use the same eight nodes, the same destinations, and the same longest prefix match rule; the only place they differ is the link set.

The result shows up at node b. For destination e, the management instance points to f, the measurement instance to c. Same device, same destination, two separate next hops. Both decisions are correct; both are the shortest path within their own link set. What is wrong is using one in place of the other.

The measurement’s assumptions:

• RT68 — The topology is the same throughout the course: eight nodes, the a–b–c–d–e–f–g–h–a ring, and the b–f chord that cuts the ring.
• RT69 — Three routing instances are built, and they differ only in their link sets: management all nine links, measurement eight links without the chord, guest eight links without the d–e link. The instance names are fictional.
• RT70 — Every instance’s table is computed from its own link set with the same rule as the oracle: the first hop of the shortest path to every destination. The oracle is not changed.
• RT71 — A packet does not leave the instance it enters. A packet forwarded in one instance sees, along its entire path, only that instance’s links and only that instance’s tables.
• RT72 — 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.
• RT73 — Collapsing to a single table means using management‘s table within the others’ link sets; the link sets do not merge in the collapse, because a link not being mapped to an instance is an administrative decision, not a physical one.

Measurement

"""Routing instances: same address, same device, two separate decisions."""
SEED = 20260810
NODES = "abcdefgh"
LINKS = [("a", "b"), ("b", "c"), ("c", "d"), ("d", "e"), ("e", "f"),
         ("f", "g"), ("g", "h"), ("h", "a"), ("b", "f")]
INSTANCE = {"management": LINKS,
            "measurement": [b for b in LINKS if b != ("b", "f")],
            "guest": [b for b in LINKS if b != ("d", "e")]}
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 oracle(links):
    """The first hop of the shortest path for every node to every destination."""
    kom, t = neighbors(links), {}
    for source in NODES:
        prev, frontier, seen = {}, [source], {source}
        while frontier:
            nxt = []
            for u in frontier:
                for v in sorted(kom[u]):
                    if v not in seen:
                        seen.add(v)
                        prev[v] = u
                        nxt.append(v)
            frontier = nxt
        for dest in NODES:
            if dest == source or dest not in prev:
                continue
            step = dest
            while prev[step] != source:
                step = prev[step]
            t[(source, dest)] = step
    return t


def forward(source, dest, t, links):
    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, links):
    tally, hops = {"reached": 0, "loop": 0, "black hole": 0}, 0
    for x, y in pairs():
        fate, path = forward(x, y, t, links)
        tally[fate] += 1
        hops += len(path) - 1
    return tally, hops


T = {name: oracle(links) for name, links in INSTANCE.items()}
print(f"{'instance':<12s} {'links':>5s} {'rows':>5s} {'reached':>7s} {'loop':>6s} "
      f"{'black hole':>11s} {'hops':>5s}")
for name, links in INSTANCE.items():
    s, a = measure(T[name], links)
    print(f"{name:<12s} {len(links):5d} {len(T[name]):5d} {s['reached']:7d} "
          f"{s['loop']:6d} {s['black hole']:11d} {a:5d}")

print()
print(f"{'comparison':<27s} {'diverging rows':>14s} {'packets diverging first hop':>28s}")
for x, y in (("management", "measurement"), ("management", "guest"), ("measurement", "guest")):
    rows = sum(1 for k in T[x] if T[x][k] != T[y][k])
    packets = sum(1 for c in pairs() if T[x][c] != T[y][c])
    print(f"{x + ' - ' + y:<27s} {rows:14d} {packets:28d}")

print()
print("node b's routing rows")
print(f"{'dest':>4s} {'management':>10s} {'measurement':>11s} {'guest':>6s}   state")
for h in NODES:
    if h == "b":
        continue
    v = [T[name][("b", h)] for name in INSTANCE]
    print(f"{h:>4s} {v[0]:>10s} {v[1]:>11s} {v[2]:>6s}   "
          f"{'diverges' if len(set(v)) > 1 else 'same'}")

print()
for n in (1, 2, 3):
    chosen = list(INSTANCE)[:n]
    diverging = sum(1 for k in T["management"]
                     if len({T[name][k] for name in chosen}) > 1)
    print(f"{n} instance(s): rows kept {n * 56}, rows where at least two "
          f"instances diverge {diverging}")

print()
print("collapsing to a single table (the management table wins)")
for name in ("measurement", "guest"):
    s, a = measure(T["management"], INSTANCE[name])
    print(f"  in the {name} link set: reached {s['reached']}, loop {s['loop']}, "
          f"black hole {s['black hole']}, hops {a}")

instance     links  rows reached   loop  black hole  hops
management       9    56      40      0           0    83
measurement      8    56      40      0           0    99
guest            8    56      40      0           0    91

comparison                  diverging rows  packets diverging first hop
management - measurement                11                           12
management - guest                       7                            6
measurement - guest                     18                           18

node b's routing rows
dest management measurement  guest   state
   a          a           a      a   same
   c          c           c      c   same
   d          c           c      c   same
   e          f           c      f   diverges
   f          f           a      f   diverges
   g          f           a      f   diverges
   h          a           a      a   same

1 instance(s): rows kept 56, rows where at least two instances diverge 0
2 instance(s): rows kept 112, rows where at least two instances diverge 11
3 instance(s): rows kept 168, rows where at least two instances diverge 18

collapsing to a single table (the management table wins)
  in the measurement link set: reached 26, loop 0, black hole 14, hops 61
  in the guest link set: reached 32, loop 0, black hole 8, hops 72

The Measure of Divergence

The top table places the three instances side by side. In all three, all forty of the forty packets arrive, loop is 0, black hole is 0. The only thing that differs is hops: management 83, guest 91, measurement 99. Removing the chord is more expensive than removing the d–e link, because the chord is the link that short-circuits the two sides of the ring.

The second table counts the divergence at the row and packet level. management and measurement diverge in 11 of the 56 rows, and this divergence changes the first hop for 12 of the measured forty packets. Between management and guest, the numbers are 7 and 6. The biggest divergence is between the two narrowed instances: measurement and guest diverge in 18 rows and 18 packets — neither uses the link the other uses.

The third table gives node b’s seven rows. Four are the same across all three instances: for destinations a, c, d, and h, the decision is independent of the link set. Three diverge. For destination e, management and guest say f while measurement says c; for destination f, measurement says a, meaning it routes the packet around the other side of the ring.

There is one more consequence of the divergence. When a link breaks, convergence starts only in the instances that use that link. If the chord breaks, management’s table has to turn into a new table — the one measurement’s instance already has; the difference between the two has been measured, and it is 11 rows. In the same break, the measurement instance changes zero rows, because that link was never in its set to begin with. The same device spends a convergence round in one instance while spending none at all in another, at the same moment; splitting separates the scope of the fault before it separates the table.

The observation here is another form of the course’s axis of measurement. Throughout the course, what happens to a packet was counted when the tables fell into disagreement; here, the tables disagree, and this is not a fault. The divergence is the design itself. The fault begins where the divergence is removed.

The Cost of Instance Count

The fourth table gives the row count. Eight nodes and seven destinations come to 56 rows per instance; two instances, 112; three instances, 168. The row count grows linearly with instance count.

The diverging-row count does not grow at the same rate. 0 at one instance, 11 at two, 18 at three. The third instance adds 56 more rows to the table but raises the divergence by only seven rows. Read the other way: 38 of the 56 rows (56 minus 18) are the same across all three instances, and 114 of the 168 rows are copies of the same decision written three times.

This is the cost. The split is made for the 18 rows whose decision genuinely diverges; the remaining rows are the split’s overhead. This overhead does not grow with the node count, it grows with destination count times instance count, and both factors are design decisions.

Overlapping Addresses and Shared Rows

In the setup, what separates the instances is the link set. In working networks, the real reason is the address itself: two instances can carry the same block of addresses, and that block can go to two separate places. On a single-table device this is impossible, because longest prefix match gives a single result, and the same prefix cannot be written into two rows. Instances remove this constraint, because the match is made after the instance is chosen. The setup’s node names do not overlap; if they did, the measurement would not change, since instance selection never looks at the address at all.

A second consequence of this is that a row can be deliberately shared between two instances. If there is a common service meant to be reached from every instance, that service’s row is copied into the second instance, and the divergence shrinks by one row. The final measurement gives this operation’s limit: if the copied row does not verify that the next hop is a neighbor in that instance, every copied row is a black-hole row.

Segmentation’s counterpart at the link layer was established in this course’s network devices topic: a VLAN splits the broadcast domain and separates frames by tag. The distinction can be written in a single sentence: a VLAN determines who enters the same broadcast domain, a routing instance determines which table gets read. One separates the domain a frame circulates in, the other separates the row a packet looks at. When the two are used together, a port is mapped both to a VLAN and to a routing instance; if either mapping is missing, the packet falls into either the wrong domain or the wrong table.

Collapsing to a Single Table

The final measurement tries to escape the overhead: if a single table were kept instead of three, what would management‘s table do within the others’ link sets?

In the measurement link set, 26 packets arrive, 14 fall into a black hole, for a total of 61 hops. The reason is written in node b’s row: the collapsed table points to f for destination f, but f is not b‘s neighbor in this instance. The next hop exists in the table but not in the neighborhood — this is exactly the course’s definition of a black hole. In the guest link set, the numbers are 32 and 8. Hops dropping from 83 to 61 is not an improvement here either: a dying packet stops spending hops, and a low hop count becomes the sign of loss.

This is the answer to why splitting separates the link set along with the table. Sharing the table while keeping the link set separate produces, at every node, rows that say a next hop exists but cannot be reached. The table shrinks, the packet dies.

Summary

• A routing instance is three parts: a link set, a table computed from it, and a port mapping that drops an incoming packet into the instance. Which instance a packet falls into is not read from its address.
• On the same device, the same destination goes to two separate decisions: for destination e, node b points to f in the management instance and to c in the measurement instance; both are the shortest path within their own link set.
• All three instances deliver all forty of the forty packets, and total hops are 83, 99, and 91 respectively; the divergence is 11 rows and 12 packets between management and measurement, and 18 rows and 18 packets between measurement and guest.
• Rows kept grow linearly with instance count (56, 112, 168), but diverging rows do not grow the same way (0, 11, 18); 114 of the 168 rows are copies of the same decision.
• When the instances are collapsed into a single table, 14 packets fall into a black hole in the measurement link set: the next hop exists in the table but is not a neighbor in that instance.

Next Step

In all three instances, the decision was taken again at every node. The packet arrived at b, b looked at its table; it arrived at c, c looked at its table. Raising the instance count to three tripled the rows kept but did not change the lookup count at all: exactly as many lookups happened as the forty packets took hops. The next lesson measures this repetition. Does the decision have to be taken again at every node along the path, or can it be taken once and carried on the packet, and when it is carried, what trade-off arises between lookup count and row count?