MPLS and Label Switching

The previous lesson built three routing instances on the same device and raised rows kept from 56 to 168. One thing did not change: the decision was taken again at every node. The packet arrived at b, b looked at the destination and read a row from its own table; it arrived at c, c did the same job from scratch. The instance count tripled the row count, but it never changed this repetition.

This lesson’s question is the repetition itself. In a converged network, every decision taken along the path gives the same path; the same result is computed five times at five nodes. Can the decision be taken once and carried on the packet, and when it is, what is gained, and what is paid?

Where the Decision Is Taken

In a network where the decision is taken at every node, the operation is three steps: read the packet’s destination address, do the longest prefix match among the prefixes in the table, and forward to the next hop in the resulting row. All three steps repeat at every node, and the third step’s input is the same every time.

Label switching removes this repetition. The path’s ingress node takes the decision once and attaches the result to the packet as a short label. Intermediate nodes never look at the destination address; they look only at the incoming label, read the outgoing label and next hop from their own label table, swap the label, and forward the packet. The egress node strips the label and delivers the packet to its destination.

Two properties of the label are critical. The label does not name the destination, it names the path: two separate paths to the same destination can have two separate labels. And the label is meaningful per link: there is no connection at all between what the value 17 means on the b–c link and what it means on the c–d link, which is why every node has to swap the label.

# taught transcript, not run

ingress node (b)           intermediate node (c)      egress node (d)
  destination       d        incoming label   17        incoming label    9
  path          b-c-d        outgoing label    9        action    strip and deliver
  action    add label        next hop          d
  label            17        action         swap

c's label table                  c's routing table
  in  out  next hop                destination  next hop
  17    9         d                a            b
  23   41         b                d            d
  44    6         b                e            d

The two tables show the lesson’s trade-off. The routing table keeps a row per destination; the label table keeps a row per path. If the number of paths passing through a node is greater than the number of destinations, the label table is bigger than the routing table.

A label does not have to be a single value. More than one label can be written onto a packet; the labels form a stack, and an intermediate node looks only at the outermost label. This connects directly to the previous lesson: the outer label names the path, the inner label names which routing instance the packet belongs to. Intermediate nodes never know about instances at all; only the egress node strips the outer label, looks at the inner one, and drops the packet into the right instance’s table. Nodes in the middle of a network can thereby carry traffic without knowing how many instances it is split across. The measurement does not count the stack’s depth; what it counts is the lookup the outermost label produces.

Building the Path From the Edge

Once the decision is taken once, that decision no longer has to be the shortest path. The ingress node can choose which path it maps the label to; intermediate nodes never look at the destination anyway, so they never question the choice. This is traffic engineering: the path is chosen not by cost but by administration.

In the setup, the counterpart of this is avoiding the chord. Because the chord short-circuits the two sides of the ring, most shortest paths pass through it and pile up on a single link. If the label paths are built from the shortest paths of the chordless ring, the chord physically keeps standing, but no packet crosses it.

The measurement’s assumptions:

• RT74 — 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.
• RT75 — Two regimes are compared. In the first, every node looks at the destination and takes the decision from its own table; in the second, only the ingress node looks at the destination, intermediate nodes look at the label. The path is derived from the same table in both; the only thing that differs is where the decision is taken.
• RT76 — Lookup count: in the regime where the decision is taken at every node, every hop the packet takes is a full-table lookup. In the regime where the decision is taken at the edge, one full-table lookup is counted per packet, and as many label lookups as the remaining hops.
• RT77 — In the traffic engineering regime, label paths are built from the chordless ring’s shortest paths. The chord physically stays standing; it is just that no label path uses it.
• RT78 — Label-row count: for every one of the fifty-six paths, a row is kept at every node except the path’s last node. The routing table, by contrast, keeps only as many rows per node as there are destinations.
• RT79 — In the last regime, the chord breaks and the label paths are not renewed; the ingress node keeps its old decision, and intermediate nodes cannot fix anything, since they never knew the destination to begin with.
• RT80 — The forty source–destination pairs come from the course’s core generator, each occurrence is a separate packet, the hop limit is 12, and the set’s resolution is 1/40 = 0.025.

Measurement

"""Label switching: is the decision taken at every node, or once at the edge."""
SEED = 20260810
NODES = "abcdefgh"
LINKS = [("a", "b"), ("b", "c"), ("c", "d"), ("d", "e"), ("e", "f"),
         ("f", "g"), ("g", "h"), ("h", "a"), ("b", "f")]
BROKEN = [b for b in LINKS if b != ("b", "f")]
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 trace(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, edge):
    """edge=False: full-table lookup at every node. edge=True: once, at the edge."""
    tally = {"reached": 0, "loop": 0, "black hole": 0}
    hops = full = label = chord = 0
    for x, y in pairs():
        fate, path = trace(x, y, t, links)
        h = len(path) - 1
        tally[fate] += 1
        hops += h
        full += 1 if edge else h
        label += max(h - 1, 0) if edge else 0
        chord += sum(1 for i in range(h)
                      if tuple(sorted((path[i], path[i + 1]))) == ("b", "f"))
    return tally, hops, full, label, chord


FULL, ENG = oracle(LINKS), oracle(BROKEN)
REGIME = (("decision at every node", FULL, LINKS, False),
          ("decision at the edge", FULL, LINKS, True),
          ("edge decision, traffic engineering", ENG, LINKS, True),
          ("chord broke, label stale", FULL, BROKEN, True),
          ("chord broke, decision at every node", FULL, BROKEN, False))
print(f"{'regime':<36s} {'reached':>7s} {'loop':>6s} {'black hole':>11s} "
      f"{'hops':>5s} {'full lookups':>12s} {'label lookups':>14s} {'chord':>6s}")
for name, t, links, edge in REGIME:
    s, a, full, label, chord = measure(t, links, edge)
    print(f"{name:<36s} {s['reached']:7d} {s['loop']:6d} {s['black hole']:11d} "
          f"{a:5d} {full:12d} {label:14d} {chord:6d}")

print()
print(f"{'table':<28s} {'total rows':>11s} {'busiest node':>13s}")
print(f"{'routing (per destination)':<28s} {len(FULL):11d} "
      f"{max(sum(1 for u, h in FULL if u == x) for x in NODES):13d}")
for name, t in (("label, shortest path", FULL), ("label, engineered path", ENG)):
    rows = {u: 0 for u in NODES}
    for u in NODES:
        for h in NODES:
            if u == h:
                continue
            for v in trace(u, h, t, LINKS)[1][:-1]:
                rows[v] += 1
    print(f"{name:<28s} {sum(rows.values()):11d} {max(rows.values()):13d}")

regime                               reached   loop  black hole  hops full lookups  label lookups  chord
decision at every node                    40      0           0    83           83              0     14
decision at the edge                      40      0           0    83           40             43     14
edge decision, traffic engineering        40      0           0    99           40             59      0
chord broke, label stale                  26      0          14    61           40             26      0
chord broke, decision at every node       26      0          14    61           61              0      0

table                         total rows  busiest node
routing (per destination)             56             7
label, shortest path                 110            23
label, engineered path               128            18

The Lookup Moved, the Count Did Not

The first two rows run the same path in two separate ways. Forty packets take 83 hops in both, all forty arrive, and the chord’s load is 14 packets in both. The path is identical, and this is deliberate: what is compared is not the path, it is where the decision is taken.

What changes is the distribution of lookups. The regime that decides at every node does 83 full-table lookups. The regime that decides at the edge does 40 full-table lookups and 43 label lookups. Total lookup count is 83 in both; the label does not reduce the lookup count.

The gain is in the lookup’s kind. A full-table lookup requires reading the destination address, searching for the longest match among prefixes, and walking a seven-row table. A label lookup is the direct lookup of a single value; there is no ordering, no prefix, no length comparison.

The second and more important gain is in the course’s axis of measurement. In the regime that decides at every node, k separate tables give the decision along the path, and these tables have to agree. In the regime that decides at the edge, a single table determines the path; the tables at intermediate nodes carry not the path but only the label’s counterpart. The course’s third claim said a loop is a disagreement between at least two tables; the label brings the number of tables that have to agree down to one.

Distributing the Load

The third row measures traffic engineering. When the label paths avoid the chord, all forty of the forty packets still arrive, but total hops climb from 83 to 99, and the number of packets crossing the chord drops from 14 to 0.

The trade-off is plain: sixteen extra hops, against removing a fourteen-packet pileup on a single link. Cost cannot make this decision, because the only thing cost knows is path length; it does not know the chord’s capacity, its price, or what other traffic shares it. In the previous lesson, policy lengthening the path was not a flaw; it is not here either, and the reasoning is the same: the shortest path is not a goal, it is a default.

The Table’s Cost

The bottom table gives the bill for moving the decision to the edge. Routing tables keep fifty-six node–destination rows, and no node has more than 7 rows. Label tables keep 110 rows for the same fifty-six paths, and 23 rows pile up at the busiest node.

The pattern reads in two rows of the table. Routing state grows with the number of destinations; label state grows with the number of paths, and the number of paths grows much faster than the number of destinations. The decision moved to the edge, but the decision’s state spread across the middle.

Engineered paths split this bill in an interesting way: total rows climb from 110 to 128, but the busiest node’s row count drops from 23 to 18. The chord piled up every path crossing it at two nodes; avoiding the chord lengthens the paths and grows the count, while distributing both the load and the state. This is where avoiding a link balances not just traffic but table load too.

A Decision Taken at the Edge Is Renewed at the Edge

The last row measures the break. When the chord breaks and the label paths are not renewed, 26 of the forty packets arrive, 14 fall into a black hole, and total hops drop to 61. Full-table lookups stay at 40, label lookups drop to 26 — a dying packet also stops spending lookups.

The fifth row measures the same break in the regime that decides at every node, and the fate counts come out identical: 26 reached, 14 black hole, 61 hops. This is not surprising, because both regimes use the same stale table and the same broken link set. The only column that differs is the lookup column: when the old decision is retaken at every node, 61 full lookups; when it is taken once at the edge, 40 full lookups and 26 label lookups.

Even though the fates are the same, the repair is not. In a network that decides at every node, the tables correct themselves over a few convergence rounds, and the correction starts near the break. On a label path, intermediate nodes have nothing they can correct: they do not know the destination, they only know the label’s counterpart. The repair has to happen at the ingress, and the ingress can be the node farthest from the break.

The course’s axis of measurement reverses here. Concentrating the decision in a single place spreads that place’s disagreement over the entire path. The label brings the number of tables that have to agree down to one; in return, that single table going stale becomes the packet’s sole cause of failure.

Summary

• In label switching, the decision is taken once, at the ingress node, and written onto the packet as a label; intermediate nodes never look at the destination, they swap the label. The label names not the destination but the path, and it is meaningful per link.
• Lookup count does not change: the same path produces 83 full-table lookups in the regime that decides at every node, and 40 full lookups and 43 label lookups in the regime that decides at the edge. What changes is the kind of lookup and the number of tables that determine the path.
• A label path does not have to be the shortest: paths that avoid the chord raise hops from 83 to 99 and bring packets crossing the chord down from 14 to 0.
• Rows kept climb from 56 to 110; routing state grows with the number of destinations, label state with the number of paths. Engineered paths raise the total to 128 while bringing the busiest node’s row count down from 23 to 18.
• When the chord breaks and the label path is not renewed, 14 packets fall into a black hole. In the same break, the regime that decides at every node also delivers 26 and loses 14; the only things that differ are the lookup distribution (61 full lookups against 40 full and 26 label) and where the repair starts — since an intermediate node does not know the destination, the repair has to happen at the ingress.

Next Step

The label moved the decision to the edge, but the path still ran over the network’s own links: a labeled packet going from b to c genuinely used the b–c link. But what if the link between two nodes were not a physical link, but a logical one built over another network? The next lesson measures a logical topology built with tunnels: in such a network, the table is kept in two layers at once, the two layers converge separately, and a packet’s fate depends on both of them agreeing.