--- title: 'MPLS and Label Switching' source: 'https://academia.sh/en/courses/switching-and-routing/mpls-and-label-switching' course: 'Switching and Routing' language: en updated: '2026-08-17T18:07:20+00:00' license: 'CC BY-SA 4.0' --- # MPLS and Label Switching When the decision is taken again at every node, forty packets produce 83 full-table lookups; when the decision is taken once at the edge and carried by a label, the count drops to 40 full lookups and 43 label lookups, a label-built path brings the chord's load down from 14 packets to 0, and rows kept climb from 56 to 110. 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. ```text # 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 ```python """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.