--- title: 'Switching and Routing' source: 'https://academia.sh/en/courses/switching-and-routing' language: en updated: '2026-08-17T04:39:16+00:00' license: 'CC BY-SA 4.0' lessons: 17 outcomes: - 'Explains switch and router behavior through their tables' - 'Chooses between static and dynamic routing on a measured criterion' - 'Compares layered network topologies' --- # Switching and Routing The decision of a switch and of a router is read from a local table; the table is a copy of a shared truth, and the course counts what happens to a packet during the time the copies disagree. ## Network Devices The effect of the repeater, hub, and switch on collision and broadcast domains, the MAC address table's learning and forwarding decision, segmentation with VLANs, loop prevention, and link aggregation. ### Repeater, Hub, and Switch Source: https://academia.sh/en/courses/switching-and-routing/repeater-hub-and-switch Three device classes are measured on the same forty frames: the repeater and the hub set up a single collision domain and produce 280 deliveries and 34 collisions, a table-less switch zeroes the collisions but keeps 240 unnecessary copies, and a switch with a table brings deliveries down to 40. The previous course counted what an intermediary can read **from a message**. There, the decision was made by looking at what was written in the message: the method field said something, the status code said something, and the intermediary ran purely by reading these. When the message closed, the intermediary went blind. A switch's decision is not made this way. The device receiving the frame passes it to an output by looking at **its own table**; the destination address written in the frame is only the question asked of the table, not the answer itself. The answer is in the device's memory. And what is in that memory is a **copy** of a shared reality — the copy can go stale, can be incomplete, can contradict its neighbor's. This is the course's one subject. This lesson's question comes before that: how do a decision-making device and a non-deciding device diverge on the same traffic? #### Where the Decision Is Read From What is measured throughout the course is a single mechanism. There is a **table**; the table maps a destination to an output. The device takes the incoming frame or packet, looks up its destination in the table, and passes it to the output it finds. The table itself is not the device's invention: it derives from the network's real shape, but it is kept as a **local copy** of that reality. To measure whether the copy agrees with reality, the reality has to be written down separately. Throughout the course, this is called the **oracle**: because we build the topology ourselves, where every destination is is known. The oracle is not information in a device's hands; it is the ruler in the measurement's hands. When the copy does not agree with reality, one of three things happens to the packet, and the course uses these three names to the end. **Reached:** the packet arrived at its destination. **Loop:** the packet crossed the same link a second time, or burned through the hop limit; it did not die, it is circling. **Black hole:** the output is not in the table, or is no longer a real output; the packet ended there. The only fate measured in this lesson is **reached**, because a single device's table cannot set up a loop by itself. A loop is a disagreement between at least two tables, and two tables show up in this topic's later lessons. #### Three Device Classes Three device classes standing on the same local network read the decision from three separate places. A **repeater** reads from nowhere. It joins two segments and refreshes the signal coming from one side, pushing it out the other. It does not decode the frame, does not look at an address, keeps no table. What it does is undo the signal's weakening; it buys distance, not decision. A **hub** is a repeater with many ports. It pushes the signal coming in on one port out to all the remaining ports. The port count is greater than two, but the decision mechanism is the same: nonexistent. A **switch** reads the decision from a table. The table maps a hardware address to a port; if the frame's destination address is in the table, the frame goes out only that port. How it fills the table — writing an incoming frame's source address together with the port it arrived on, and **flooding** a frame whose destination is unknown — was established in the Ethernet and MAC Addresses lesson of the Network Models and Protocols course and is not repeated here. Here the table is taken as given; what is measured is what the table's **existence** buys. The distinction is a layer distinction. The repeater and the hub work at the signal level: what they carry is a bit stream, not a frame. The switch works at the link layer: it recognizes the frame as a unit, reads its address fields, and makes a decision. Which layer a device stands at says not how fast it is, but **what it can look at**. #### Forwarding Modes A switch's decision is made at one point in time, and the choice of that point gives rise to two modes. In **store-and-forward** mode, the switch takes in the whole frame, verifies the check sequence, and only then passes it to a port. A corrupted frame never gets placed on an output; its cost is a wait proportional to the frame's length. In **cut-through** mode, the switch picks the output the moment it reads the destination address and passes the remaining bytes through as they stream in. The wait is only as long as the address field, independent of the frame's length. Its cost is this: the check sequence is at the end of the frame, meaning it has not yet been seen when the decision is made. A corrupted frame gets forwarded too, and only the receiver finds the error. The choice is not a right-versus-wrong choice, but a trade-off that depends on what is being counted: latency on one side, wasted transmission on the other. This lesson's measurement is independent of the mode and the same in both, because what is counted is not **when** the decision is made but whether it is made at all. #### Two Domains Two scopes are distinguished, and this distinction is the first measure that separates the three devices from each other. A **collision domain** is the set of devices whose signals can clash if transmission happens at the same time. The repeater and the hub set up a single shared medium: eight stations are in a single collision domain. Every port of the switch is a separate collision domain; a transmission on one port does not clash with a transmission on another. A **broadcast domain** is the set of devices a broadcast frame reaches. None of the three devices splits the broadcast domain. Nor does the switch: a frame whose destination is a group address goes out every port. The mechanism that splits the broadcast domain is the subject of this topic's later lessons. #### Full-Duplex Ports and Buffers Every port of the switch being a separate collision domain means collision **can** happen in that domain. If a port has a single station on it and the port runs full-duplex, sending and receiving travel on separate paths, and two transmissions that would clash never arise at all. The switch's zeroing of collisions comes from this structure: the collision domain was not shrunk, it was **emptied out.** This has a cost, and the queue column in the measurement counts it. Two transmissions cannot happen at the same time on a shared medium; they can on a switch, because the input ports are independent of each other. When two inputs want the same output, the switch has to hold one of them, and where it holds it is a **buffer.** If the buffer fills, the frame is dropped — the site of the loss has moved from the medium to the device. The same reasoning works when port speeds are not equal too. A frame coming in on a fast port and going out on a slow one waits out the difference in the buffer. On a shared medium, such a difference was undefined: everyone spoke at the same speed, because everyone was on the same wire. The measurement's setup is this: eight stations are connected to a single device through eight ports. Forty frames are sent; every frame has a source, a destination, and a time slot. The device's table is read as in the transcript below. ```text # taught transcript, not run MAC address table (switch) address port a 1 b 2 ... h 8 trace of one frame source a, destination e hub -> 2,3,4,5,6,7,8 (seven copies, six unnecessary) switch -> 5 (one copy) when destination is not in the table switch -> 2,3,4,5,6,7,8 (flooding; same as hub) ``` #### The Measurement's Assumptions - **ND1** — Eight stations are connected to a single device through eight ports, and every station is on exactly one port. The oracle is known because we built this layout ourselves: the measurement knows which address is on which port, the device may not. - **ND2** — Forty frames are generated. Source and destination are drawn from one generator, the time slot from a separate generator; each generator is called with a single modulus. A draw where source and destination are the same is discarded. - **ND3** — The number of time slots is twenty. Forty frames spread over twenty slots means a loaded medium; what is measured is not the absolute collision count, but what the same load becomes across the three devices. - **ND4** — On a shared medium, if a slot has more than one sender, every frame in that slot is counted as **collided**. There is no collision on separate ports; every extra frame in the same slot wanting the same output port is written to the **queue**. - **ND5** — Four regimes are compared: repeater, hub, a switch with an empty table, and a switch with a full table. The switch with an empty table is a setup that does not learn; its purpose is to separate the gain of port isolation from the gain of the table. - **ND6** — The load axis is built with the slot count: the same forty frames are fit into forty, twenty, and ten slots. When the slot count changes, the draws are redone from scratch, so the load rows are not subsets of each other; what is compared is not the same frame sequence, but the same density rule. - **ND7** — The set's resolution is forty frames; the smallest measurable difference is $1/40 = 0{,}025$. A difference smaller than this cannot be defended with this set. #### The Measurement ```python """Three device classes on the same traffic: domain counts and delivered frames. Source and destination are drawn from one generator, the time slot from a separate generator; each generator is called with a single modulus. """ SEED = 20260810 STATIONS = ["a", "b", "c", "d", "e", "f", "g", "h"] SLOTS = 20 def generator(seed): d = seed % 2147483646 + 1 def r(n): nonlocal d d = (d * 48271) % 2147483647 return d % n return r def frames(count=40, slots=SLOTS): r, z, result = generator(SEED), generator(SEED + 1), [] while len(result) < count: x, y = STATIONS[r(8)], STATIONS[r(8)] if x != y: result.append({"source": x, "destination": y, "slot": z(slots)}) return result def oracle(): """Reality: which station stands on which port.""" return {a: i + 1 for i, a in enumerate(STATIONS)} def measure(C, table, shared_medium): location, filled, sent = oracle(), {}, {} delivered = unnecessary = collided = 0 for c in C: filled[c["slot"]] = filled.get(c["slot"], 0) + 1 for c in C: port = table.get(c["destination"]) outputs = ([port] if port is not None else [p for p in location.values() if p != location[c["source"]]]) delivered += len(outputs) unnecessary += sum(1 for p in outputs if p != location[c["destination"]]) if shared_medium: collided += 1 if filled[c["slot"]] > 1 else 0 else: for p in outputs: sent[(c["slot"], p)] = sent.get((c["slot"], p), 0) + 1 queue = sum(n - 1 for n in sent.values() if n > 1) return delivered, unnecessary, collided, queue C, FULL = frames(), oracle() print(f"frames {len(C)} | stations {len(STATIONS)} | time slots {SLOTS}") print() print(f"{'device':<20s} {'ports':>5s} {'collision':>9s} {'broadcast':>9s} " f"{'delivered':>9s} {'unnecessary':>11s} {'collided':>8s} {'queue':>6s}") for name, ports, table, shared in (("repeater", 2, {}, True), ("hub", 8, {}, True), ("switch, no table", 8, {}, False), ("switch, full table", 8, FULL, False)): d, u, co, q = measure(C, table, shared) print(f"{name:<20s} {ports:5d} {1 if shared else ports:9d} {1:9d} " f"{d:9d} {u:11d} {co:8d} {q:6d}") print() print(f"{'slots':>5s} {'hub collided':>12s} {'no-table queue':>14s} " f"{'full-table queue':>17s}") for d in (40, 20, 10): Cd = frames(40, d) _, _, co, _ = measure(Cd, {}, True) _, _, _, q0 = measure(Cd, {}, False) _, _, _, q1 = measure(Cd, FULL, False) print(f"{d:5d} {co:12d} {q0:14d} {q1:17d}") ``` ``` frames 40 | stations 8 | time slots 20 device ports collision broadcast delivered unnecessary collided queue repeater 2 1 1 280 240 34 0 hub 8 1 1 280 240 34 0 switch, no table 8 8 1 280 240 0 151 switch, full table 8 8 1 40 0 0 6 slots hub collided no-table queue full-table queue 40 27 102 3 20 34 151 6 10 38 202 10 ``` #### Two Separate Gains The first two rows are **identical to each other**, and this is not a shortcoming but the lesson's first finding. The repeater has two ports, the hub has eight; the domain counts they produce, the copy counts they deliver, and the collided-frame counts all come out the same. Adding ports buys no decision. Because neither reads the decision from anywhere, they are the same device. The third row measures port isolation alone. The switch with an empty table still floods: **280** deliveries, **240** unnecessary copies — the same as the hub's. The only thing that changes is collision: it drops from **34** to **0**. Because the ports are separate collision domains, two transmissions no longer corrupt each other. Transmissions that are not corrupted do not vanish, they go into the **queue**: **151** extra copies wanting to go out the same port in the same slot wait in line. Collision did not disappear, it **turned into queuing.** The fourth row adds the table's gain. Delivered drops from **280** to **40**, unnecessary copies from **240** to **0**: every one of the forty frames goes out exactly one port. The queue also drops from **151** to **6**, because now only the frames that genuinely need to go there want a given port. The distinction is this: **port isolation removes collision, the table removes unnecessary copies.** They are two separate mechanisms, and they are measured separately. A table-less switch is better than a hub in wiring, and no different from it in workload. The differences counted are within the measurement's band. In a set of forty frames, the smallest measurable difference is $1/40 = 0{,}025$; the differences here are not at the level of one frame but tens of frames. The **34**-frame drop in collision is **0.850** of the set, and the **240**-unit drop in unnecessary copies is six copies per frame. A difference at this scale does not depend on the fiction's detail. #### When Load Rises The table below sends the same forty frames at three separate densities: light load when spread over forty slots, heavy when packed into ten. On the shared medium, collided frames climb from **27** to **34**, then to **38**. The rise slows because there is a known ceiling: all forty of the forty frames can collide, and there is nothing past that. This is the shared medium's behavior under load — degradation is measured **by frames lost**, and it saturates. On the switch, the same load shows up as a queue. On the switch with a table, the queue climbs to **3**, **6**, **10** entries; on the table-less switch, to **102**, **151**, **202**. Two observations follow. First, on a switch, load produces not **loss** but **waiting**: the frame does not disappear, it waits its turn. Second, flooding raises the queue roughly twentyfold — because every frame wants not one port but seven. The table's gain grows as load rises: the gap is **99** entries under light load, **192** under heavy load. One more warning is read from the table above. The broadcast domain column is **1** in all four rows. No matter how well the switch decides with its table, it has to give a frame whose destination is a group address to every port — because that frame's destination never lands on a single port in the table. In an eight-station domain, a single broadcast frame produces seven deliveries; as the domain grows, this number grows with it. #### Summary - In this course, the decision is not read from what is written in the message; it is read from the device's **table**, and the table is a local copy of a shared reality. - A packet has three fates — **reached**, **loop**, **black hole**; a single device's table cannot set up a loop by itself, a loop is a disagreement between at least two tables. - The repeater and the hub are the same device: on forty frames, both give **1** collision domain, **280** deliveries, **240** unnecessary copies, and **34** collided frames. - Port isolation brings collision down from **34** to **0** but does not touch unnecessary copies; collision does not disappear, it turns into **151** queue entries. The table brings delivered down from **280** to **40**, unnecessary copies from **240** to **0**, the queue from **151** to **6**. - As load rises, collision on the shared medium saturates toward forty with **27**, **34**, **38**; the same load on the switch becomes **3**, **6**, **10** queue entries — waiting, not loss. - None of the three devices splits the broadcast domain; the broadcast domain count stays **1** across all four regimes. #### Next Step In this measurement, the switch's table was taken as given: all eight of the eight addresses were mapped to the right port. In reality, a table does not start that way and does not stay that way. When a switch powers on, its table is empty; if a station goes quiet, its entry gets deleted after a while; if a station moves to another port, its entry stays wrong for a while. The next lesson measures the table's **age**: how many frames an unlearned and an aged entry make get flooded, and which domain that flooding grows. ### MAC Address Tables Source: https://academia.sh/en/courses/switching-and-routing/mac-address-tables A table's age is a two-way trade-off: on forty frames, an entry with unlimited lifetime gives 110 deliveries and 3 black holes, a two-frame lifetime zeroes the black holes but raises deliveries to 278. The previous lesson took the switch's table as given: all eight of the eight addresses were mapped to the right port, and the table therefore sent all forty of the forty frames out a single port. Under that assumption, the table brought delivered down from 280 to 40. A real table does not start that way and does not stay that way. When a switch powers on, its table is empty; entries fill in through observation; a silent station never gets an entry written; and a written entry does not stay correct forever, since the station can move to another port. This lesson's question is not what the table does, but **how long it lives.** #### Three Separate Shortfalls A table falls short in three separate ways, and the three do not cost the same. **Unlearned entry.** The address is not in the table. The switch does not know where the destination is and passes the frame to every port but the one it arrived on. The frame **reaches** its destination; the cost is only unnecessary copies. The learning mechanism itself — writing the source address together with its arrival port, and **flooding** a frame whose destination is unknown — was established in the Ethernet and MAC Addresses lesson of the Network Models and Protocols course and is not repeated here. **Aged entry.** The address was in the table, but the time since the entry was placed exceeded the entry's lifetime, and the entry was deleted. The result is the same as an unlearned entry: flooding, a frame that reaches its destination, unnecessary copies. The reason it is counted separately is that it comes from a different source — one arises from never having been learned, the other from having been **forgotten.** **Stale entry.** The address is in the table, the entry is fresh, and it is **wrong.** The station has moved to another port, and the table still points at the old one. The switch does not flood here; it confidently sends the frame out the wrong port. The frame finds no one there and falls into a **black hole.** Of the three shortfalls, only this third one kills the frame. The distinction comes down to this: flooding is **expensive but correct**, a stale entry is **cheap and wrong.** An entry's lifetime is a choice between the two. #### Which Domain Flooding Does Its Work In A flooded frame goes out every port even though its destination is a single station. The two scopes from the previous lesson diverge here. Flooding does not grow the **collision domain**: the ports are still isolated from each other, and the copies going out do not clash with each other. Flooding uses up the **broadcast domain**: the copies go exactly where a broadcast frame would go. The result is this: **an unlearned destination temporarily turns a single frame into a broadcast frame.** The larger the broadcast domain, the larger flooding's cost, and this cost is multiplied by the number of frames flooded. A station that never speaks makes this cost permanent. In the measurement, station `h` never sends a frame; because its source address never appears in any frame, it never gets written to the table. Every frame going to it is flooded to the end of the measurement. The table's row count is therefore not eight but seven. #### The Table Looks at the Address, Not the Port The table's orientation looks backward at first glance: the switch has eight ports, but the table counts not ports but **addresses.** A port need not hold exactly one station. If another switch is connected to it, the addresses of every station behind it map to that same port; a virtualized host can likewise show more than one address from a single port. This has two consequences. First, the table's row count grows not with the port count but with the **number of addresses seen**; the seven rows in the measurement come from eight stations, not nine ports. Second, the same address cannot appear on two ports at once: a new observation updates the entry rather than duplicating it. An address moving back and forth between two ports is not the table contradicting itself, it is the network producing contradictory observations — its source is the subject of a later lesson in this topic. The table's capacity is also finite. When the number of entries exceeds capacity, an entry is dropped to make room, and frames going to the dropped entry's address are flooded. This gives the same result as shortening the lifetime; the difference is that the choice is made by occupancy, not by the administrator. ```text # taught transcript, not run MAC address table (instant 12) address port instant written a 1 13 b 2 9 c 3 11 <- this entry goes stale at instant 12 d 4 8 e 5 10 f 6 12 g 7 5 (no row for h: never transmitted) at instant 12: station c moves from port 3 to port 9. instant 15, destination c -> table says port 3 -> no one there -> black hole if the entry ages out -> flooding -> every port -> reaches if c transmits again -> entry becomes port 9 -> reaches ``` #### The Measurement's Assumptions - **ND8** — Eight stations are connected to a switch with nine ports; the ninth port is empty and is the target of the move. The oracle is known because we built the layout ourselves, and it says which address is on which port at every instant. - **ND9** — Forty frames are drawn from a single generator with a single modulus. Draws where the source equals the destination, or where the source is the silent station, are discarded; the silent station therefore never sends anything. - **ND10** — The unit of time is the frame: an entry's age is the number of frames elapsed since it was placed. In the regime where the lifetime is `None`, the entry is never deleted. - **ND11** — The table learns only from the source address, and every frame first learns, then forwards. This order matches the real mechanism and affects the measurement: a station's own transmission refreshes its own entry. - **ND12** — In the move regime, a station switches to the empty port on frame 12 and announces this to no one. The table corrects itself only two ways: the entry ages out, or the station transmits again. - **ND13** — The fate names are the same as in the shared definition. A frame that leaves a copy on the destination's real port is counted **reached**; one that does not is counted a **black hole.** In this single-switch setup, a **loop** cannot form. - **ND14** — The set's resolution is forty frames; the smallest measurable difference is $1/40 = 0{,}025$. #### The Measurement ```python """MAC address table age: cost of unlearned and aged entries. The learning mechanism was established in the Network Models course; what is measured here is how long an entry lives. """ SEED = 20260810 STATIONS = ["a", "b", "c", "d", "e", "f", "g", "h"] PORTS = 9 SILENT = "h" MOVED, MOVE_TIME = "c", 12 def generator(seed): d = seed % 2147483646 + 1 def r(n): nonlocal d d = (d * 48271) % 2147483647 return d % n return r def frames(count=40): r, result = generator(SEED), [] while len(result) < count: x, y = STATIONS[r(8)], STATIONS[r(8)] if x != y and x != SILENT: result.append({"instant": len(result), "source": x, "destination": y}) return result def oracle(instant, move): """Reality: at the move instant, one station switches to the empty port.""" location = {a: i + 1 for i, a in enumerate(STATIONS)} if move and instant >= MOVE_TIME: location[MOVED] = PORTS return location def measure(C, age, move): table, fate = {}, {"reached": 0, "black hole": 0} flood = {"unlearned": 0, "aged": 0} delivered = unnecessary = 0 for c in C: location = oracle(c["instant"], move) table[c["source"]] = (location[c["source"]], c["instant"]) entry = table.get(c["destination"]) fresh = entry is not None and (age is None or c["instant"] - entry[1] < age) if fresh: outputs = [entry[0]] else: flood["aged" if entry else "unlearned"] += 1 outputs = [p for p in range(1, PORTS + 1) if p != location[c["source"]]] delivered += len(outputs) unnecessary += sum(1 for p in outputs if p != location[c["destination"]]) fate["reached" if location[c["destination"]] in outputs else "black hole"] += 1 return flood, fate, delivered, unnecessary, len(table) C = frames() print(f"frames {len(C)} | ports {PORTS} | silent station {SILENT}, frame as " f"destination {sum(1 for c in C if c['destination'] == SILENT)} | " f"flooding ceiling {len(C) * (PORTS - 1)}") HEADER = (f"{'age':>5s} {'unlearned':>12s} {'aged':>9s} {'reached':>6s} " f"{'black hole':>10s} {'delivered':>6s} {'unnecessary':>8s} {'rows':>5s}") for move in (False, True): print() print("with move" if move else "no move") print(HEADER) for age in (None, 20, 10, 5, 2): f, k, d, u, n = measure(C, age, move) print(f"{str(age):>5s} {f['unlearned']:12d} {f['aged']:9d} " f"{k['reached']:6d} {k['black hole']:10d} {d:6d} {u:8d} {n:5d}") ``` ``` frames 40 | ports 9 | silent station h, frame as destination 4 | flooding ceiling 320 no move age unlearned aged reached black hole delivered unnecessary rows None 10 0 40 0 110 70 7 20 10 0 40 0 110 70 7 10 10 6 40 0 152 112 7 5 10 14 40 0 208 168 7 2 10 24 40 0 278 238 7 with move age unlearned aged reached black hole delivered unnecessary rows None 10 0 37 3 110 73 7 20 10 0 37 3 110 73 7 10 10 6 38 2 152 114 7 5 10 14 39 1 208 169 7 2 10 24 40 0 278 238 7 ``` #### The Unlearned Entry's Unchanging Share In both tables, the `unlearned` column is **10**, and no lifetime value changes it. This number has two parts: the initial encounters from the table starting empty, and the **4** frames going to the silent station. The first part is paid once, the second throughout the measurement. The result matters: **extending an entry's lifetime does not reduce unlearned entries.** Lifetime only decides how long an entry survives; it does not produce an entry that was never written. The only way to bring a silent station into the table is to make it speak. Because the table is fed only by observation, an endpoint that produces none at all sits entirely outside its field of view, and every frame going there pays the cost of this blindness. The regime that leaves lifetime unlimited delivers **110**; if everything could be flooded, the ceiling is **320**. So even working correctly, the table produces **less than a third** of the ceiling's deliveries — the rest is already saved. As lifetime shrinks, this saving erodes: at a **10**-frame lifetime, delivered is **152**; at **5**, **208**; at **2**, **278**. In the last row, the switch has climbed to **0.869** of the ceiling; the table is nearly void, and the device has stopped being one that makes decisions. #### Two Sides of Lifetime The lower table reads the same lifetime series together with a move, and the direction reverses. In the regime that leaves lifetime unlimited, **3** frames fall into a black hole. All three are sent after the move, before the moved station speaks again; the table is confident and wrong over that stretch. A **20**-frame lifetime gives the same result, because no entry reaches that age before the measurement ends: a lifetime longer than the measurement window is indistinguishable from an unlimited one. At a **10**-frame lifetime, black holes drop to **2**; at **5**, to **1**; at **2**, to **0**. What performs the correction is not an announcement — no one reports the move. It is **forgetting:** the moment the entry is deleted, the switch again admits it does not know, floods, and the flooded frame reaches its destination because it visits the new port too. The cost sits on the same rows. Bringing black holes down from **3** to **0** raises delivered from **110** to **278**: saving one frame costs an average of fifty-six extra copies. Three frames in a set of forty is **0.075** and three times the resolution, so it is a measurable difference; but the copies paid to zero out the loss exceed half the flooding ceiling. The pattern is this: **an entry's lifetime is a choice between how long it stays wrong and the cost of not knowing.** A long lifetime makes the table cheap and prolongs the error; a short lifetime shortens the error and voids the table. No lifetime zeroes out both at once, because the only way for the switch to learn of a move is a new observation, and the time until that observation arrives cannot be measured. #### Lifetime Is Not Chosen Alone The measurement had a single lifetime because it had a single table. On a real path, two separate caches for the same destination stand side by side: the switch's MAC address table, and the address-resolution cache on the sending host. The second was established in the ARP lesson of the Network Models and Protocols course and is not repeated here; what matters here is only that the two lifetimes are chosen **relative to each other.** When the two are not equal, an asymmetry arises. If the sending host keeps holding the destination's hardware address while the switch's entry has been deleted, the host keeps sending without querying, and the switch floods every frame. If the destination station is only ever a responder — it never speaks on its own — its entry never gets rewritten, and flooding becomes permanent. The silent station's persistent share of **10** in the measurement is a small instance of this. The rule is this: if the switch entry's lifetime is chosen shorter than the upper-layer address cache's lifetime, flooding is not a malfunction but the **ordinary result of the design.** Chosen the other way around, the stale entry's lifetime lengthens and the black-hole window widens. The measurement's two tables show these two directions separately; the choice lies between them. #### Tables Do Not Know Each Other The measurement was run with a single switch, which makes the result more optimistic than it is. When two switches stand side by side, there are two tables, and **there is no synchronization between them.** Each switch sees only frames passing through its own ports; it writes what it sees and does not know what it does not see. An entry one switch has just refreshed can already be stale in the other. This is not a flaw in the table but its definition: a table is a **local copy** of a shared reality. There is no announcement that keeps the copy current; the only thing that keeps it current is seeing the same traffic. Two switches that do not see the same traffic can point to different ports for the same address. In the single-switch setup, this cost was not visible, because the only fate measured was the **black hole**: a frame going out the wrong port died there. With two tables, a third fate opens up. If one switch sends the frame forward and the other sends it back, the frame does not die; it goes back and forth between the two devices. **A loop is not something a single table can produce** — it is a disagreement between at least two tables, and it will be counted for the first time in a later lesson in this topic. #### Summary - A table falls short in three separate ways: **unlearned** and **aged** entries lead to flooding, a **stale** entry leads to a black hole; the first two are expensive but correct, the third is cheap and wrong. - Flooding does not use up the collision domain, it uses up the **broadcast domain**: a flooded frame does the work of a broadcast frame even though it is bound for a single destination. - The unlearned-entry count stays **10** across every lifetime value; **4** of it goes to the station that never speaks, and the table therefore stays at **7** rows, not eight. - As lifetime shortens, delivered grows **110**, **152**, **208**, **278**; the last value is **0.869** of the flooding ceiling of **320** and leaves the table nearly void. - In the move regime, black holes drop **3**, **3**, **2**, **1**, **0**; what performs the correction is not an announcement, it is the entry being forgotten. #### Next Step In this measurement, flooding always went to the same place: all nine ports. The reason was that the eight stations were in a single broadcast domain — in the previous lesson's measurement too, the broadcast-domain count was one in every regime. But flooding's cost is multiplied directly by the size of this domain. The next lesson measures splitting the domain: when more than one broadcast domain is defined on the same physical switch, how many copies does flooding come down to, how many rows does the table grow to, and where does the black hole that segmentation itself produces come from. ### VLANs Source: https://academia.sh/en/courses/switching-and-routing/vlans Segmentation splits the broadcast domain but not the table row: on forty frames, flooding delivered drops from 280 to 51 and to 8, row count stays at 16, and the cost is a black hole of between 23 and 32. The previous lesson counted flooding's cost and showed where that cost comes from: a flooded frame goes to the entire broadcast domain, so its cost is multiplied directly by that domain's size. In an eight-station domain, a single flood costs eight copies; the same flood in an eighty-station domain costs eighty. The way out this suggests is shrinking the domain. But the known way to shrink a domain is to physically separate the network: separate switches, separate cables, separate locations. This lesson's question is: can more than one broadcast domain be defined on the same physical switch, without changing the cabling, and if so, **what is gained, what is paid?** #### The ID Is Assigned to the Port A **VLAN** is a switch dividing its ports into numbered sets. Each port is assigned an **ID**; the switch passes a frame arriving on one port only to ports carrying the same ID. Flooding obeys the same rule: a frame with an unknown destination is flooded not to every port, but only to the ports of its own ID. That is the entire mechanism, and it changes nothing in the frame. The station is unaware the ID exists; the frame it sends is an ordinary frame. The ID lives in the switch's configuration, not in the frame. When a port's ID is changed, the station on it has been moved to another broadcast domain, and it does not notice. The direct consequence is that the broadcast-domain count is no longer tied to cabling. A single eight-port switch can carry four broadcast domains; eight separate switches can carry a single one. The domain's boundary is not physical, it is **declarative.** #### The Trunk Link On a single switch, the ID is not written into the frame, because it does not need to be: which ID a frame belongs to is known from the port it arrived on. When two switches sit side by side, this information is lost. Which ID the frames sharing the single cable between them belong to is undetermined for the other switch. The fix is to write the ID into the frame. On a **trunk link**, the frame passes carrying a four-byte tag inserted between the source address and the type field. | Field | Width | Carries | |---|---|---| | Tag protocol identifier | 16 bits | A fixed value marking the frame as tagged | | Priority | 3 bits | The frame's processing priority | | Drop-eligible indicator | 1 bit | A notice that it can be dropped first under congestion | | ID | 12 bits | The VLAN's number | The ID field is 12 bits; because the smallest and largest values are reserved, the number of usable IDs is 4094. The tag exists only on the trunk link: it is stripped off as the frame goes out to a station, because the station is unaware of the tag. ```text # taught transcript, not run untagged frame (station <-> switch) destination | source | type | payload | check tagged frame (switch <-> switch) destination | source | TAG | type | payload | check ^ 4 bytes: id-mark + priority + drop-eligible + id port configuration (switch 1) port 1 untagged, id 1 port 2 untagged, id 1 port 3 untagged, id 2 port 4 untagged, id 2 port 5 TAGGED, ids carried: 1, 2 ``` Which IDs a trunk link carries is a separate decision. If an ID has no members on the other switch, carrying it buys nothing; when it is not carried, no frame belonging to that ID crosses over, and the switch on the other side never sees that ID's addresses. The measurement counts this decision's cost separately. Assigning an ID to a port is not the only method. In port-based assignment, the decision is tied to the cable: whatever the port is, that is the ID, no matter which station gets plugged in. In address-based assignment, the switch looks at an incoming frame's source address and reads the ID from a mapping table; if the station moves, its ID moves with it. The second buys portability, and charges in return a second table the switch has to keep, plus keeping that table current. The measurement uses port-based assignment, because what is counted is not the method of assignment but segmentation itself. #### The Native VLAN and Disagreement Between the Two Ends What to do when an untagged frame appears on a tagged link is decided separately. Every trunk link has a **native VLAN**: an untagged incoming frame is counted as belonging to that ID, and a frame leaving that ID is sent untagged. The domain is recognized not by carrying an ID, but by not carrying one. This opens a configuration surface that belongs to the course's axis. What the native VLAN is gets written **separately** at the two ends of the link, and there is no synchronization between them. If the two ends write the same number, there is no problem. If they write different numbers, a frame leaving one end untagged is counted into a different domain at the other end: the frame **crosses from one broadcast domain to another with no device making that decision.** There is no sign of malfunction — the link is up, counters are clean, frames are not dropped. The only visible thing is that two domains meant to be separate are sharing some frames. **Narrowing** takes three steps. First, the native VLAN is written to the same value at both ends, and that value is treated as a reviewed part of the configuration. Second, the native VLAN is pulled to a number assigned to no station; if that domain has no members, there is no traffic for the mismatch to carry either. Third, the ID list a trunk link carries is written in its narrowest form: IDs with members on both sides are carried, the rest are not. The measurement's third regime is the extreme case of this narrow configuration. #### The Measurement's Assumptions - **ND15** — There are two switches, four stations connected to each, and a single trunk link stands between them. The oracle is known because we built the layout ourselves. - **ND16** — Forty frames are drawn from a single generator with a single modulus; draws where the source equals the destination are discarded. The same frame sequence is used across all four segmentations. - **ND17** — Four regimes are compared: unsegmented; two domains, both **spanning** the two switches; two domains, each **local** to a single switch; four domains, all spanning. - **ND18** — The delivered column counts the **flooding** regime: as if the destination were not in the table, the frame is given to every station in its own domain. The goal is to isolate segmentation's effect on flooding; the table's own gain was measured in the previous lesson. - **ND19** — The trunk link carries an ID that has members on both sides; it does not carry an ID without members. This is the narrowest form of the configuration. - **ND20** — A table row is an `(id, address)` pair, and a switch writes only a source it has **seen.** Whether the other switch sees a given source depends on the trunk link carrying that ID. - **ND21** — A frame whose source and destination are in separate IDs is counted a **black hole**: the switch floods it within its own domain, and since the destination is not in that domain, no copy reaches it. The set's resolution is forty frames, the smallest measurable difference is $1/40 = 0{,}025$. #### The Measurement ```python """Segmentation's effect on the broadcast domain, table row, and trunk link.""" SEED = 20260810 STATIONS = ["a", "b", "c", "d", "e", "f", "g", "h"] SWITCH = {"a": 1, "b": 1, "c": 1, "d": 1, "e": 2, "f": 2, "g": 2, "h": 2} SEGMENTATION = { "unsegmented": {a: 1 for a in STATIONS}, "two domains, spanning": {"a": 1, "b": 1, "c": 2, "d": 2, "e": 1, "f": 1, "g": 2, "h": 2}, "two domains, local": {"a": 1, "b": 1, "c": 1, "d": 1, "e": 2, "f": 2, "g": 2, "h": 2}, "four domains, spanning": {"a": 1, "b": 2, "c": 3, "d": 4, "e": 1, "f": 2, "g": 3, "h": 4}, } def generator(seed): d = seed % 2147483646 + 1 def r(n): nonlocal d d = (d * 48271) % 2147483647 return d % n return r def frames(count=40): r, result = generator(SEED), [] while len(result) < count: x, y = STATIONS[r(8)], STATIONS[r(8)] if x != y: result.append({"source": x, "destination": y}) return result def carried_ids(id_map): """The trunk link carries an ID that has members on both sides.""" return {k for k in set(id_map.values()) if {SWITCH[s] for s in STATIONS if id_map[s] == k} == {1, 2}} def measure(C, id_map): carried = carried_ids(id_map) rows = {1: set(), 2: set()} fate = {"reached": 0, "black hole": 0} delivered = unnecessary = trunked = 0 for c in C: k, x, y = id_map[c["source"]], c["source"], c["destination"] rows[SWITCH[x]].add((k, x)) if k in carried: rows[3 - SWITCH[x]].add((k, x)) if id_map[y] != k: fate["black hole"] += 1 continue outputs = [s for s in STATIONS if id_map[s] == k and s != x] delivered += len(outputs) unnecessary += sum(1 for s in outputs if s != y) trunked += 1 if SWITCH[y] != SWITCH[x] else 0 fate["reached"] += 1 return fate, delivered, unnecessary, trunked, len(rows[1]) + len(rows[2]) C = frames() print(f"frames {len(C)} | stations {len(STATIONS)} | switches 2") print() print(f"{'segmentation':<23s} {'domains':>7s} {'reached':>7s} {'black hole':>10s} " f"{'delivered':>9s} {'unnecessary':>11s} {'trunked':>7s} {'rows':>5s}") for name, id_map in SEGMENTATION.items(): fate, d, u, t, r = measure(C, id_map) print(f"{name:<23s} {len(set(id_map.values())):7d} {fate['reached']:7d} " f"{fate['black hole']:10d} {d:9d} {u:11d} {t:7d} {r:5d}") ``` ``` frames 40 | stations 8 | switches 2 segmentation domains reached black hole delivered unnecessary trunked rows unsegmented 1 40 0 280 240 29 16 two domains, spanning 2 17 23 51 34 14 16 two domains, local 2 11 29 33 22 0 8 four domains, spanning 4 8 32 8 0 8 16 ``` #### The Domain Splits, the Row Does Not The delivered column keeps segmentation's promise. Flooding forty frames on the unsegmented network produces **280** deliveries; split into two domains it drops to **51**, into four domains to **8**. Doubling the domain count drops the cost to roughly a quarter, because both the number of frames flooded and the number of stations each flood reaches shrink together. In the four-domain regime, unnecessary copies drop to **0**, and the reason is interesting. Every domain in that regime has two stations; the frame a station floods within its own domain goes to the domain's only other station — exactly the destination. **Once a domain shrinks to two stations, flooding and learned forwarding are the same thing.** The table buys no gain there; segmentation has done the table's job. The rows column, however, does not keep the promise. In three of the four regimes, the row count is **16**: even though segmentation splits the broadcast domain, it does not split the table row. The reason is direct — the table separates addresses by ID, but does not **destroy** them. Eight addresses split into four domains are still eight addresses; every switch still sees all eight, because the trunk link carries every ID and every source address crosses over. The two two-domain regimes giving different results comes from the same distinction. The domain count is two in both, but reached frames are **17** in one, **11** in the other. The difference comes not from segmentation's coarseness but from its **placement**: when domains span the two switches, a domain's members are four stations; when domains stay local to a single switch, it is also four, but this time who talks to whom is tied to the cable. Same domain count, same member count, different result. What actually splits the row is not segmentation but **what the trunk link carries.** In the third regime, every domain stays local to a single switch; the trunk link has no shared ID left to carry, and each switch learns only its own four addresses. Rows drop from **16** to **8**. This is not a result of segmentation alone, but of **segmentation together with placement.** #### The Black Hole Segmentation Produces The gain's cost sits in the black-hole column, and what is paid is not small. On the unsegmented network, all forty of the forty frames reach their destination. Split into two domains, **23** frames fall into a black hole; in local segmentation, **29**; in four domains, **32**. In a set of forty, this last value is **0.800**: segmentation has stopped more than three-quarters of the traffic. This is not a malfunction, it is the definition itself. Splitting the broadcast domain means those domains cannot send frames to each other; the silence gained and the access lost are two faces of the same thing. The measurement writes this under a fate name because the frame genuinely dies: the switch floods it within its own domain, and since the destination is not in that domain, no copy reaches it and no one reports an error. Where the distinction has shifted deserves attention. In the previous lesson, a black hole was a **misjudgment** — the table was stale, the device went out the wrong port. Here, a black hole is a **decision**: the table is correct, the ID is correct, the device has done exactly what was asked of it. The same name is written for two separate reasons, and what separates them is whether the table is right. This second kind of black hole also decides where the domain's boundary falls. A broadcast domain is the largest set within which address resolution can walk: a station can only ask about an address in its own domain, because its question travels by a broadcast frame, and that frame does not leave the domain. This is why the boundary of the broadcast domain and the boundary of the address block land in the same place; the subnet arithmetic established in the Network Models and Protocols course is not repeated here, but segmentation requires a separate block for every new domain. In a set of forty frames, **32** black holes is **0.800** and thirty-two times the resolution; at this scale, the claim rests on the definition of segmentation, not on the fiction's detail. The trunked column gives a third reading. On the unsegmented network, **29** frames use the cable between the two switches; split into two domains it drops to **14**, in local segmentation to **0**. Local segmentation empties the cable entirely — but the cable it empties is at the same time the reason **29** frames die. A link going unused does not show that it is unnecessary. #### Summary - A VLAN assigns an ID to a port; the station does not see the ID, and no field is added to its frame. The broadcast domain's boundary stops being physical and becomes declarative. - A trunk link writes the ID into the frame with a four-byte field; a 12-bit ID field gives 4094 usable values, and the tag is dropped as the frame goes out to a station. - Segmentation brings flooding delivered down from **280** to **51** and **8**; once a domain shrinks to two stations, unnecessary copies become **0** and flooding turns into the same thing as learned forwarding. - The table row stays at **16** in three of the regimes: segmentation separates addresses, it does not destroy them. What brings the row down to **8** is not segmentation, but the trunk link never carrying that ID at all. - The cost is the black hole: **0**, **23**, **29**, **32**. This black hole is not a misjudgment but a decision — the table is correct and the device has done what was asked. #### Next Step In this measurement, there was a single cable between the two switches, and every flooded frame crossed it once and was done. If a second cable is run between the two switches, the situation changes: a flooded frame goes out the first cable and comes back on the second, and once it comes back, it gets flooded again, this time going out the first cable. There is no domain to stop the frame — the link-layer frame carries no hop count. The next lesson measures this consequence of redundant links and the decision made by the protocol that prevents it: which link gets blocked, and what happens to a packet's fate during the round before the block is recomputed. ### Spanning Tree Protocol Source: https://academia.sh/en/courses/switching-and-routing/spanning-tree-protocol In an unblocked ring, a single broadcast frame produces 142 copies by round twelve and does not stop; on the tree it ends at 7 copies. When the tree is rebuilt with stale tables, 20 packets fall into a black hole; when only two switches have refreshed their tables, 10 packets enter a loop. The previous lesson placed a single cable between two switches, and every flooded frame crossed it once and was done. When redundancy is wanted, a second cable is run; the two switches connect through two separate paths, and if one breaks, the other stays up. This is the oldest and most natural request in network design. The request produces a malfunction when it meets flooding. A flooded frame crosses over on the first cable, the far switch floods it to every port but the one it arrived on — the second cable is among them — and the frame returns to the first switch. When it returns, the first switch floods it again. This lesson's question is how this return is stopped, and what the stopping decision does to a packet's fate. #### The Frame Carries No Counter To see why the above return does not end on its own, it is enough to look at the frame. An Ethernet frame has a destination address, a source address, a type field, a payload, and a check sequence. **There is no field that counts how many devices it has passed through.** The network-layer packet has such a field, and it was established in the Network Models and Protocols course; the link-layer frame has none. The result is not two-fold but three-fold. First, a circulating frame never dies by **aging.** Second, every switch on the ring **duplicates** the frame each round: one incoming copy spawns several outgoing copies. Third, because the same source address is seen from different ports, every switch's MAC address table gets rewritten round after round — the table is not stale in the sense measured in the previous lesson, it is **unstable.** This trio is the first instance of why a loop is more expensive than a black hole. In a black hole, the packet dies and the matter ends; here, the packet does not die, it multiplies and consumes the network's own carrying capacity by itself. Someone looking from outside sees this as congestion. #### The Protocol's Decision The solution is to turn a topology that is physically a ring into a logical **tree.** A tree has no cycle; without a cycle there is no return either. This requires **blocking** some links: the link stays up, the cable is plugged in, but no data frame passes over it. **Spanning tree protocol** lets the switches build this tree among themselves. The decision has three steps. The switches first elect a **root**: every switch has an identifier, and the smallest identifier becomes root. Then every switch marks its cheapest port toward the root as its **root port.** Finally, on every link, the end that connects that link to the root more cheaply is counted **designated**; the other end is **blocked.** How the tree itself is built is not this lesson's subject. The concept of a spanning tree and its greedy construction were established in the Minimum Spanning Tree lesson of the Algorithms course and are not rederived here. What is measured here is the **protocol's decision** and what that decision does to packets. ```text # taught transcript, not run topology: a-b-c-d-e-f-g-h-a ring + b-f chord (8 nodes, 9 links) root: a port roles (for root a) b: root port -> a | designated -> c, f h: root port -> a | designated -> g c: root port -> b | designated -> d f: root port -> b | designated -> e d: root port -> c | d-e BLOCKED g: root port -> h | f-g BLOCKED protocol message (switch to switch, not data) root identifier | cost to root | sender identifier | port ``` In root election, a small identifier is not a measure of capability; it is only an ordering rule that gets every switch to the same result. The tree gets built no matter where the root is, but the tree's **shape** depends on the root, and so does the length of the paths. #### The Measurement's Assumptions - **ND22** — The topology is the shared definition's topology: eight switches, a ring of seven links (`a–b–c–d–e–f–g–h–a`), and the `b–f` chord cutting the ring; nine links in total. The oracle is known because we built the topology ourselves, and it is the first step of the shortest path to every destination for every node. - **ND23** — The root is `a`, and the tree is built by walking breadth-first from the root: every switch keeps its port nearest the root, and the remaining links are blocked. The minimum spanning tree algorithm is not run here; the tree's **result** is used. - **ND24** — In the flooding measurement, a broadcast frame leaves the root; every node copies the frame to every link but the one it arrived on. There is no mechanism to stop it, because the frame carries no hop count. The measurement is cut off by a round limit; being cut off does not mean the frame has stopped. - **ND25** — Forty source–destination pairs are drawn from a single generator with a single modulus; a draw where the source equals the destination is discarded. The same forty pairs are used in every regime. - **ND26** — The link that breaks is the `b–f` chord. Because the chord short-circuits the two arms of the ring, most of the tree passes through it; when it breaks, a large number of switches have to change their decision. - **ND27** — Five regimes are compared: tree built, no break; link broken but neither the tree nor the table has been renewed; tree renewed but the tables are stale; tree renewed and only two switches have refreshed their table; tree renewed and every table cleared. - **ND28** — The hop limit is 12. A packet that burns through the limit, or crosses the same link a second time, is counted a **loop**; a packet whose next node is not in the table or is no longer a neighbor is counted a **black hole.** - **ND29** — The set's resolution is forty packets; the smallest measurable difference is $1/40 = 0{,}025$. #### The Measurement ```python """Spanning tree protocol's decision: the blocked link and the packet's fate. The tree is built by walking breadth-first from the root; the minimum spanning tree algorithm was established in the Algorithms course and is not rederived here. """ SEED = 20260810 NODES = ["a", "b", "c", "d", "e", "f", "g", "h"] LINKS = [("a", "b"), ("b", "c"), ("c", "d"), ("d", "e"), ("e", "f"), ("f", "g"), ("g", "h"), ("h", "a"), ("b", "f")] BROKEN, ROOT, HOP_LIMIT = ("b", "f"), "a", 12 def generator(seed): d = seed % 2147483646 + 1 def r(n): nonlocal d d = (d * 48271) % 2147483647 return d % n return r def neighbors(links): n = {u: set() for u in NODES} for x, y in links: n[x].add(y) n[y].add(x) return n def oracle(links): """First step of the shortest path to every destination, for every node.""" n, table = neighbors(links), {} for source in NODES: previous, frontier, seen = {}, [source], {source} while frontier: next_frontier = [] for u in frontier: for v in sorted(n[u]): if v not in seen: seen.add(v) previous[v] = u next_frontier.append(v) frontier = next_frontier for destination in NODES: if destination == source or destination not in previous: continue step = destination while previous[step] != source: step = previous[step] table[(source, destination)] = step return table def tree(links, root=ROOT): """The port nearest the root is kept, the remaining link is blocked.""" n, seen, frontier, kept = neighbors(links), {root}, [root], [] while frontier: next_frontier = [] for u in frontier: for v in sorted(n[u]): if v not in seen: seen.add(v) kept.append(tuple(sorted((u, v)))) next_frontier.append(v) frontier = next_frontier return kept def forward(source, destination, tables, links): n, u, crossed, hop = neighbors(links), source, [], 0 while u != destination: if hop >= HOP_LIMIT: return "loop", hop next_node = tables.get((u, destination)) if next_node is None or next_node not in n[u]: return "black hole", hop if (u, next_node) in crossed: return "loop", hop crossed.append((u, next_node)) u, hop = next_node, hop + 1 return "reached", hop 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 measure(tables, links): tally, hops = {"reached": 0, "loop": 0, "black hole": 0}, 0 for x, y in pairs(): fate, h = forward(x, y, tables, links) tally[fate] += 1 hops += h return tally, hops def partial(old, new, updated): """Only one set has heard of the new tree; the rest keep the old one.""" return {(u, h): (new if u in updated else old)[(u, h)] for (u, h) in old if (u, h) in new} def flood(links, source, round_limit): """Broadcast frame: every node copies to every link but the one it arrived on.""" n, wave, copies = neighbors(links), [(source, None)], 0 for _ in range(round_limit): next_wave = [] for u, arrived_from in wave: for v in sorted(n[u]): if v != arrived_from: copies += 1 next_wave.append((v, u)) wave = next_wave if not wave: break return copies, len(wave) BROKEN_LINKS = [b for b in LINKS if b != BROKEN] OLD, NEW = tree(LINKS), tree(BROKEN_LINKS) OLD_BROKEN = [b for b in OLD if b != BROKEN] print(f"links {len(LINKS)} | tree links {len(OLD)} | old tree blocks " f"{[b for b in LINKS if tuple(sorted(b)) not in OLD]}") print(f"broken link {BROKEN} | new tree blocks " f"{[b for b in BROKEN_LINKS if tuple(sorted(b)) not in NEW]}") print() print(f"{'round':>5s} {'ring copies':>11s} {'in flight':>9s} {'tree copies':>11s} " f"{'in flight':>9s}") for rnd in (1, 2, 4, 6, 8, 10, 12): c1, f1 = flood(LINKS, ROOT, rnd) c2, f2 = flood(OLD, ROOT, rnd) print(f"{rnd:5d} {c1:11d} {f1:9d} {c2:11d} {f2:9d}") print() print(f"{'regime':<34s} {'reached':>7s} {'loop':>6s} {'black hole':>11s} " f"{'hops':>5s}") for name, tab, links in ( ("tree built, no break", oracle(OLD), OLD), ("link broken, tree and table stale", oracle(OLD), OLD_BROKEN), ("tree new, tables stale", oracle(OLD), NEW), ("tree new, table on two switches", partial(oracle(OLD), oracle(NEW), {"b", "f"}), NEW), ("tree new, tables clean", oracle(NEW), NEW)): tally, h = measure(tab, links) print(f"{name:<34s} {tally['reached']:7d} {tally['loop']:6d} " f"{tally['black hole']:11d} {h:5d}") ``` ``` links 9 | tree links 7 | old tree blocks [('d', 'e'), ('f', 'g')] broken link ('b', 'f') | new tree blocks [('e', 'f')] round ring copies in flight tree copies in flight 1 2 2 2 2 2 5 3 5 3 4 14 5 7 0 6 27 7 7 0 8 50 13 7 0 10 85 19 7 0 12 142 33 7 0 regime reached loop black hole hops tree built, no break 40 0 0 106 link broken, tree and table stale 21 0 19 70 tree new, tables stale 20 0 20 64 tree new, table on two switches 25 10 5 100 tree new, tables clean 40 0 0 129 ``` #### What Blocking Buys The table above gives the protocol's reason for existing. On the nine-link ring, a single broadcast frame produces **14** copies by round four, **50** by round eight, **142** by round twelve, with **33** copies still in flight at that point. The count keeps growing; it stops because the measurement's round limit ends, not because the frame stops. A single frame fills an eight-switch network all by itself. On the tree, the same frame ends at **7** copies by round four, with nothing left in flight. The number seven is the tree's link count, and it is not a coincidence: on a tree, every link is crossed exactly once, moving away from the root. **Flooding is finite on a tree and infinite on a cycle**, and the difference amounts to nothing more than two blocked links. The cost sits in the same place. Two of the nine links carry no data; the cables are plugged in, the ports are up, but no frame passes over them. The cable run for redundancy waits idle until the need for redundancy arises. #### Until the Block Lifts The lower table reads the time from the moment the chord breaks to the new tree settling in in five steps. **While the tree is built**, all forty of the forty packets reach their destination, spending **106** hops. This is also an indicator of blocking's cost: the same forty pairs would take shorter paths if every link were open. Blocking lengthens paths but loses no packet. **When the link breaks and no one hears about it**, reached drops to **21**, and **19** packets fall into a black hole. Hops drop to **70** — fewer hops does not mean less work, it means **early death.** A packet falling into a black hole stops making progress; the hops it does not spend are a loss, not a gain. **When the tree is rebuilt but the tables stay stale**, the situation is a bit worse: reached is **20**, black hole is **20**. The protocol has fixed the topology, but the MAC address tables still point at the old tree's ports. The new tree has opened one link and blocked another; as long as the tables point at the closed port, a packet is sent somewhere that is no longer a neighbor, and it ends there. This is the reason the protocol does not settle for rebuilding just the tree: when a topology change is announced, the tables' **lifetime is also shortened**, so that stale entries drop quickly. **When only two switches have refreshed the table**, the table produces a third fate for the first time: **25** reach, **5** fall into a black hole, and **10** packets enter a **loop.** Hops climb from **64** to **100**. While the two switches point at the new port, their neighbors point at the old one, so the packet goes forward and comes back, circling until it burns through the hop limit. From here, the shared definition's second claim can be read: **partial information produces a more expensive malfunction than no information at all.** When no one heard, the packet died right away; when two switches heard, black holes dropped from **20** to **5**, but **10** packets started circling instead of dying, and hops climbed from **64** to **100**. The count of lost packets fell, the work spent rose, and the malfunction became **invisible** — a circling packet looks not like an error but like congestion. A third claim is read from the same row, and it is structural. **No single switch can put a packet into a loop by itself.** A loop needs **at least two tables**, one sending the packet forward and the other sending it back; in the first three regimes, every table pointed at the same tree, so no loop arose even though they were wrong. A loop is born not from a table being wrong, but from **tables disagreeing.** **When every table is cleared**, all forty of the forty packets reach again, and hops climb to **129.** Paths have lengthened because the chord is gone; but **no packet is lost.** This is the definition of convergence: expensive but correct. #### Summary - The link-layer frame carries no hop count; on a topology with a cycle, a flooded frame does not die by aging, it multiplies every round and leaves the tables unstable. - Spanning tree protocol elects a root, keeps every switch's port toward the root, and blocks the remaining links; a single broadcast frame on the ring climbs to **142** copies by round twelve, while on the tree it ends at **7**. - Blocking's cost is idle cable and longer paths: on the tree, forty packets reach in **106** hops; on the new tree after the break, in **129** — but all forty reach. - When no one hears of the break, **19** packets fall into a black hole; when the tree is rebuilt but tables stay stale, **20** do; hops dropping to **70** and **64** is early death, not a gain. - When only two switches refresh the table, black holes drop to **5** but **10** packets enter a loop and hops climb to **100**: partial information produces a more expensive malfunction than no information. - A loop is not something a single table can produce; it is a disagreement between at least two tables. #### Next Step The spanning tree's answer to redundancy is one-directional: the second link exists, but it waits. In the measurement, two links were blocked, and their carrying capacity went unused until the moment of the break. A question follows from this: can two links be used at the same time? The cycle ban seems to forbid it, because two links mean two paths, and two paths bring a flooded frame back. The next lesson measures the mechanism that goes around this ban: an aggregation that counts several links as a **single logical link**, why the distribution decision does not split a given flow, and how many flows get moved when a port drops. ### Link Aggregation Source: https://academia.sh/en/courses/switching-and-routing/link-aggregation Per-flow distribution splits no flow and breaks no order but spreads port load between 0 and 19; per-frame distribution equalizes load and splits 7 of 8 flows. When a port drops, modulus remapping moves 7 of 8 flows, in-place remapping only 3. The previous lesson measured the first answer given to redundancy: an extra link is run, the protocol blocks it, and the blocked link waits until the moment of the break. In the measurement, two of the nine links carried no data at all. They have capacity, their cable is plugged in, and they sit idle. A natural question follows: can two links not be used at the same time? The cycle ban seems to forbid this — two links mean two paths, two paths bring a flooded frame back, and a loop is born. This lesson's question is how the ban is gotten around, and what new decision that requires. #### A Single Logical Link **Link aggregation** is presenting several physical ports between two switches as a single logical link. Spanning tree protocol sees the topology through these logical links: four ports are not four links, they are **one link.** The consequence is direct. In the previous lesson's measurement, the cycle came from two separate links between two switches; because aggregation reduces those two links to one, the tree sees no cycle and blocks neither. It is not a mechanism that violates the ban; it is a mechanism that **removes the cycle the ban is about.** Flooding fits the same picture. A broadcast frame is handed to the logical link and goes out only **one** port; the far switch receives it as a single copy. Aggregation's most important rule appears here: a frame coming in is never sent back out another port of the same aggregation. Without this rule, aggregation would reproduce within itself the multiplication the previous lesson measured. Both ends have to know that the aggregation is set up. If the ports are aggregated on one end and counted separately on the other, one side sees a single link where the other sees several, and the tree's blocking decision comes out different at the two ends. This is why aggregation is set up by **agreement** through a control message between the two ends; a port that cannot reach agreement is left out of the aggregation and kept as a separate link. #### The Distribution Decision Looks at the Flow Every frame handed to an aggregated link needs a decision: which port does it go out? The simplest answer is round-robin, and it is also the answer that balances load best. But there is a problem. The ports are not on the same cable. Each has its own queue, its own length, its own instantaneous occupancy; the delay difference between two ports is not zero. If two frames of the same flow are sent out two separate ports, the second can arrive before the first. The link layer cannot fix this. As seen in the previous lesson, the Ethernet frame carries no hop count; **it carries no sequence number either.** The receiving switch cannot tell, of the two frames it has, which was sent first, and it cannot reorder them. Keeping order intact is left to the sending side's decision. The cost of out-of-order delivery is paid at an upper layer. The mechanism established in the TCP lesson of the Network Models and Protocols course reorders segments that arrive out of order, but it does so by holding a buffer and, in some cases, by making unnecessary retransmissions; an application that never expects reordering counts the data as corrupted. This is why the common rule is: **the distribution decision looks at the flow, not the frame.** Every frame of the same flow goes out the same port. What counts as a flow is a choice. A hash that looks only at the pair of hardware addresses counts all the traffic between two switches as a single flow and voids the aggregation; a hash that adds port numbers to the address pair makes the flow finer-grained and improves the balance. The measurement uses the coarsest form, because what is measured is not the hash's fineness but what the decision **looks at.** ```text # taught transcript, not run aggregation configuration (switch 1 <-> switch 2) logical link: t1 port 0 agreed port 1 agreed port 2 agreed port 3 agreed what the tree sees: a SINGLE link distribution decision per flow : port = hash(source, destination) mod port_count per frame: port = sequence_no mod port_count rule: a frame coming in from an aggregation is never sent back out another port of the same aggregation. ``` #### The Measurement's Assumptions - **ND30** — There is a single aggregation with four ports. Eight flows are drawn from the shared topology's node names with a single generator and a single modulus; each of the forty frames is assigned to one of these eight flows with a separate generator. The oracle's flow–frame mapping is known because we built it ourselves. - **ND31** — The flow hash is the sum of the character values of the names defining the flow, and the port number is this hash's remainder with respect to the port count. The hash's fineness is not the measurement's subject. - **ND32** — Port delays are not equal, and are 1, 2, 1, 3 units respectively. Every port processes one frame per unit of time; a frame's arrival instant is found by adding the delay to the port's free-up instant. - **ND33** — A frame is counted **out of order** if it arrives after a frame of the same flow sent **after** it. Ordering cannot be fixed at the link layer, because the frame carries no sequence number. - **ND34** — Two distribution schemes are compared: per-flow and per-frame. The same forty frames are used for both. - **ND35** — In the break regime, port number 1 drops. Remapping is tried with two rules: **modulus**, which recomputes every flow because the port count has shrunk; **in-place**, which moves only the flows on the dropped port and leaves the rest untouched. - **ND36** — The break happens on frame 20, and the distribution mapping is updated five frames later. In this window, frames written to the dropped port are counted a **black hole**: the port does not exist, the frame does not arrive anywhere, and no one reports it. - **ND37** — The set's resolution is forty frames and eight flows; the smallest measurable difference is $1/40 = 0{,}025$ in the frame set, $1/8 = 0{,}125$ in the flow set. #### The Measurement ```python """Link aggregation: distribution splits no flow, the dropped port moves flows.""" SEED = 20260810 NODES = ["a", "b", "c", "d", "e", "f", "g", "h"] PORTS, DELAY = 4, (1, 2, 1, 3) DROPPED, BREAK_FRAME, WINDOW = 1, 20, 5 def generator(seed): d = seed % 2147483646 + 1 def r(n): nonlocal d d = (d * 48271) % 2147483647 return d % n return r def flows(count=8): r, result = generator(SEED), [] while len(result) < count: x, y = NODES[r(8)], NODES[r(8)] if x != y and (x, y) not in result: result.append((x, y)) return result def frames(F, count=40): r = generator(SEED + 1) return [{"no": i, "flow": F[r(8)]} for i in range(count)] def flow_hash(flow): return sum(ord(c) for c in flow[0] + flow[1]) def port(c, scheme, ports): n = len(ports) return ports[flow_hash(c["flow"]) % n if scheme == "flow" else c["no"] % n] def arrival(C): """Every port processes one frame per unit time; delays are not equal.""" free = {} for c in C: start = max(c["no"], free.get(c["port"], 0)) free[c["port"]] = start + 1 c["arrival"] = start + 1 + DELAY[c["port"]] return C def out_of_order(C): last, count = {}, 0 for c in sorted(C, key=lambda c: (c["arrival"], c["no"])): if c["flow"] in last and last[c["flow"]] > c["no"]: count += 1 last[c["flow"]] = max(last.get(c["flow"], -1), c["no"]) return count F, ALL = flows(), list(range(PORTS)) print(f"flows {len(F)} | frames 40 | ports {PORTS} | dropped port {DROPPED}") print() print(f"{'scheme':<8s} {'port load':>18s} {'min':>5s} {'max':>6s} " f"{'flows split':>12s} {'unordered':>10s}") for scheme in ("flow", "frame"): C = frames(F) for c in C: c["port"] = port(c, scheme, ALL) arrival(C) load = [sum(1 for c in C if c["port"] == p) for p in ALL] split = sum(1 for f in F if len({c["port"] for c in C if c["flow"] == f}) > 1) print(f"{scheme:<8s} {str(load):>18s} {min(load):5d} {max(load):6d} " f"{split:12d} {out_of_order(C):10d}") print() REMAINING = [p for p in ALL if p != DROPPED] C = frames(F) old = {f: port({"flow": f, "no": 0}, "flow", ALL) for f in F} modulus = {f: port({"flow": f, "no": 0}, "flow", REMAINING) for f in F} in_place = {f: (REMAINING[flow_hash(f) % len(REMAINING)] if old[f] == DROPPED else old[f]) for f in F} lost = sum(1 for c in C if BREAK_FRAME <= c["no"] < BREAK_FRAME + WINDOW and old[c["flow"]] == DROPPED) print(f"flows on dropped port {sum(1 for f in F if old[f] == DROPPED)} | " f"frames lost in the {WINDOW}-frame window {lost}") print() print(f"{'remapping':<16s} {'flows moved':>12s} {'stayed in place':>16s} " f"{'new load':>14s}") for name, new in (("modulus", modulus), ("in-place", in_place)): moved = sum(1 for f in F if new[f] != old[f]) load = [sum(1 for c in C if new[c["flow"]] == p) for p in REMAINING] print(f"{name:<16s} {moved:12d} {len(F) - moved:16d} {str(load):>14s}") ``` ``` flows 8 | frames 40 | ports 4 | dropped port 1 scheme port load min max flows split unordered flow [0, 19, 5, 16] 0 19 0 0 frame [10, 10, 10, 10] 10 10 7 2 flows on dropped port 3 | frames lost in the 5-frame window 2 remapping flows moved stayed in place new load modulus 7 1 [26, 14, 0] in-place 3 5 [13, 11, 16] ``` #### Between Order and Balance The table above puts the two distribution schemes side by side, and each gains one thing and loses another. **Per-flow** distribution keeps its promise exactly: flows split, **0**; frames arriving out of order, **0**. None of the eight flows spreads across two ports, so even though port delays are not equal, order is never broken. Preserving order needs no extra mechanism — the decision already preserves it. Its cost sits in the load column, and it is not small: the ports carry **0**, **19**, **5**, and **16** frames respectively. In a four-port aggregation, one port is never used, and another pulls **19** of the forty frames on its own. The capacity aggregation promises is not a fourfold multiplication, but a distribution that depends on where the flows' hash values happen to land. **Per-frame** distribution equalizes load exactly: **10** frames per port. In return, **7** of the eight flows get split — the eighth is not split because its frames already happen to land on a single port. Splitting costs **2** out-of-order frames. This number is **0.050** in a set of forty frames and twice the resolution; it is within the measurement band but small, because the largest difference between port delays is two units. That this number would grow as the delay difference grows is read from the fiction, not from the measurement. The pattern is this: **the finer the distribution decision, the better the balance and the more fragile the order.** No single rule gives both, because what preserves order is not splitting the flow, and what builds balance is splitting it. #### Whose Capacity Is It Reading the load column has a practical consequence, and it closes off the most common misconception about aggregation. A four-port aggregation's total capacity is the sum of the four ports, but **a single flow's capacity is one port.** A flow cannot be split, because it is not split; whichever port its hash value lands it on, that port's capacity is the most data that flow can carry. The measurement shows this directly: the port carrying **19** frames is, on its own, the ceiling for those flows, and the idle port adds nothing to them. Aggregation grows a link that has **many flows**; it does not grow a link that has **one large flow.** If the traffic between two switches consists of a single backup transfer, running four ports gives the same result as running one. The second side of this is redundancy. The same mechanism, with the same cables, buys two separate things: capacity when there are many flows, staying up when a port drops. Which one dominates depends on the flow count, and this is something measurable. Nor is it required that every port carry traffic at the same time. In an **active–standby** arrangement, one port carries all the traffic, and the others take over only when it drops. This removes the distribution decision entirely: no flow gets split, no frame arrives out of order, no balance problem exists. In return, the standby ports' capacity is never used — the same situation as the previous lesson's blocked link, this time by aggregation's decision, not the tree's. #### When a Port Drops The lower section looks at aggregation's real reason for existing. When a port drops, the logical link stays up; spanning tree does not see this as a topology change and does not recompute. The rounds measured in the previous lesson are not spent here at all. Rounds not spent do not mean a free failover. The dropped port carries **3** flows, and in the five-frame window before the distribution mapping is updated, **2** frames fall into a black hole. The port does not exist, the frame arrives nowhere, no one reports an error. This number grows linearly as the window lengthens. The real difference shows up in the remapping rule. The **modulus** rule drops the port count from four to three and recomputes every hash, moving **7** of the eight flows. Yet only **3** flows **need** to move; the remaining four sat on healthy ports and changed place for no reason at all. Every flow that changes place means a new port in the matching table on the other side, and that table has to wait to be refreshed. The **in-place** rule moves only the **3** flows on the dropped port, leaving five where they were. And the result is not just less work but a better distribution too: the modulus rule splits load into **26**, **14**, **0**, while the in-place rule gives **13**, **11**, **16**. Recomputing every flow did not improve the balance, it broke it — because hash values fall into a new pattern once taken modulo a different port count, and there is no guarantee that new pattern will be balanced. In a set of eight flows, the difference between **7** and **3** is **0.500** and four times the flow set's resolution of **0.125**. The result lands on a general rule: **a source dropping should not change mappings that do not depend on it.** When it does, the price paid is relocating flows that have nothing to do with the failure at all. #### Summary - Link aggregation turns several ports into a **single logical link**; because spanning tree sees no cycle, it blocks no port, and aggregation's own rule bans sending an incoming frame back out the same aggregation. - The frame carries no sequence number; the receiver cannot reorder, so the obligation to preserve order falls on the distribution decision. - Per-flow distribution splits **0** flows and produces **0** out-of-order frames, but spreads load as **0**, **19**, **5**, **16**; per-frame distribution equalizes load to **10**, splits **7** flows, and produces **2** out-of-order frames. - When a port drops, the tree does not recompute, but **2** frames fall into a black hole in the five-frame window before the mapping updates. - Modulus remapping moves **7** flows instead of the **3** that need to move, and makes the load **26**, **14**, **0**; in-place remapping moves **3** flows and gives **13**, **11**, **16**. #### Next Step Every decision measured across this topic's five lessons shared a single common assumption: the source and destination were **within the same local network.** The switch looked for the destination in its own table because the destination was expected to be behind one of its own ports; flooding served a purpose because a flooded frame had a chance of reaching the destination; segmentation produced black holes because the destination was in another domain and no path to it had been defined. In every case, the destination was either directly a neighbor, or not there at all. The next topic lifts this assumption. If the destination is on another network, that destination's address will never be found in the device's table — because the destination is not behind any port at all. What does the decision look at then, and in which table does what it looks at reside? ## Routing From longest prefix match to the routing table, from the criterion for choosing between static and dynamic routing to the convergence of the distance vector and link state families, from policy-based routing to table splitting, label switching, and overlay networks. ### Routing Decision Source: https://academia.sh/en/courses/switching-and-routing/routing-decision The routing decision is made by looking not at what the message says but at the device's own table; when the same table is read with two different rules, it diverges on 12 of the 256 addresses, and because the table is a copy of a shared reality, at the moment of the break 26 of the 40 packets reach their destination and 14 fall into a black hole. Every decision covered so far was made **within the same local network**. A switch looked up the frame's destination in its own address table; when it found an entry, it sent the frame straight out that port, and when it did not, it flooded. The destination was in every case a **direct neighbor**: inside the same broadcast domain, one hop away. If the destination is on another network, this setup does not work. It is not a direct neighbor, it has no port entry in the table, and flooding is not an option — a network of networks cannot be flooded. The decision now has to answer not "which port" but **"whom do I hand it to"**. This lesson's question is where that answer is read from. #### What the Decision Looks At The decision a router makes is called the **routing decision**, and it has exactly one output: the **next hop**. The packet's destination address is the input, one of the neighboring nodes is the output. The router does not know the entire path to the destination, and it does not need to; it knows only **one hop** and hands the packet there. The rest of the path is the next node's problem. The decision is not made by looking at the packet itself. The packet carries its destination address and nothing else; it does not say which neighbor gets closer to that destination. What says that is the device's own **routing table**, held in memory. The table is a set of rows that maps destination-address prefixes to next hops: ```text # taught transcript, not run routing table — rows in the order they were written prefix length next hop 1010 4 north 10110 5 west 101011 6 east (empty) 0 central 10101100 8 local 10100 5 south ``` This transcript is not a specification but a reading of a device's memory; it has not been run and no numeric claim follows from it. The only thing to notice is the **order** of the rows: they were added over time and are not sorted by length. The last row carries a longer prefix than the first. The empty-prefix row is special: its length is zero and it matches every address. This row is the **default route**, and it covers whatever the table leaves out. Because of it, the table never has to enumerate every address in the world. #### Longest Prefix Match In the table above, an address can match more than one row. An address beginning with `10101100` fits four of the five rows. Which one wins? The rule is called **longest prefix match**: among the matching rows, the one with the longest prefix is chosen. The reasoning is the amount of information. A longer prefix covers a narrower set of addresses, and is therefore a **more precise** statement about that set. A shorter prefix lumps a wide set together with a coarse approximation. When two statements conflict, the precise one wins. The real point here is this: **the rule is not written inside the table.** The table carries only the rows; the rule that decides which row wins lives in the device's specification. A device that reads the same set of rows with a different rule makes a different decision. The most common wrong rule is to scan the rows in the order they were written and take the **first match**. #### The Table Is a Copy In the Linux Network Administration and Troubleshooting course, the routing table was read as **a single machine's configuration**: a file, a command's output, a reality belonging to that machine. Here, the table is not a configuration but **a copy of a shared reality** — the network's topology is one, but every device keeps its own copy of it and reads its decision from that copy. As long as the copies agree, this distinction is invisible. It becomes visible the moment the topology changes and the copies have not yet been updated. The state in which every copy matches reality is called **convergence**; what is measured throughout the course is not convergence itself but **the time spent not converged**. During that time, a packet has three possible fates. **Reached**: it arrived at its destination. **Black hole**: a node's table pointed to a neighbor that no longer exists, and the packet died there. **Loop**: the tables sent the packet back and forth to each other, and it circled until it burned through the hop limit. The measured network has eight nodes. Seven links form a ring, and the eighth is a chord that cuts across the ring. Because the chord short-circuits the two sides of the ring, most tables route through it; when it breaks, a large number of rows are forced to change their decision. Reality itself — the **oracle** — is known because we built the topology ourselves: it is the first hop of the shortest path from each node to every destination. The measurement's assumptions: - **RT1** — The network has eight nodes and nine links; seven links form the ring, and the ninth is the chord that cuts across it. The oracle is known because we built the topology ourselves. - **RT2** — The oracle is the first hop of the shortest path from each node to every destination, and it is not changed during the measurement. Reality is always the shortest path. - **RT3** — The measured break is only the loss of the chord: one link drops, there is no node loss, and the network does not partition. After the break, every destination still has a path. - **RT4** — Forty source–destination pairs are generated from a fixed seed. The same pair can come up more than once, and the measurement counts each recurrence as a separate packet. - **RT5** — The hop limit is 12; a packet that burns through it is counted as a loop. In an eight-node network, the longest loop-free path is seven hops, well below the limit. - **RT6** — In the prefix measurement, the address is eight bits wide and the **entire** space is scanned; no sample is chosen. Table rows stay in the order they were written. - **RT7** — The set's resolution is the measurement band's floor: in a set of forty packets, the smallest measurable difference is **1/40 = 0.025**; in the address space, **1/256**. #### Same Table, Two Rules First the rule itself is measured. The six-row table above is read with two different rules, and the entire eight-bit address space is scanned. ```python """Longest prefix match: same table, two reading rules. Rows stay in the order they were written, not sorted by length; the entire eight-bit address space is scanned, no example is picked. """ TABLE = [("1010", "north"), ("10110", "west"), ("101011", "east"), ("", "central"), ("10101100", "local"), ("10100", "south")] NODES = ("north", "south", "east", "west", "central", "local") ADDRESSES = [format(a, "08b") for a in range(256)] def longest_prefix(address): chosen = None for prefix, node in TABLE: if address.startswith(prefix) and (chosen is None or len(prefix) > len(chosen[0])): chosen = (prefix, node) return chosen def first_match(address): for prefix, node in TABLE: if address.startswith(prefix): return (prefix, node) return None diverging = [a for a in ADDRESSES if longest_prefix(a)[1] != first_match(a)[1]] print(f"table rows {len(TABLE)} | address space {len(ADDRESSES)} | " f"addresses where the two rules diverge {len(diverging)}") print() print(f"{'next hop':>18s} {'longest prefix':>14s} {'first match':>12s}") for node in NODES: print(f"{node:>18s} {sum(longest_prefix(a)[1] == node for a in ADDRESSES):14d}" f" {sum(first_match(a)[1] == node for a in ADDRESSES):12d}") print() for a in (diverging[0], diverging[8], diverging[11]): u, i = longest_prefix(a), first_match(a) print(f" {a} -> longest prefix {u[1]} ({u[0]}), first match {i[1]} ({i[0]})") ``` ``` table rows 6 | address space 256 | addresses where the two rules diverge 12 next hop longest prefix first match north 4 16 south 8 0 east 3 0 west 8 8 central 232 232 local 1 0 10100000 -> longest prefix south (10100), first match north (1010) 10101100 -> longest prefix local (10101100), first match north (1010) 10101111 -> longest prefix east (101011), first match north (1010) ``` The two rules diverge on **12** of the 256 addresses. The divergence runs one way: a device reading by row order sends **16** addresses to `north`, one reading by longest prefix sends **4**. Of the twelve addresses in between, eight should have gone to `south`, three to `east`, one to `local`. The `central` column is **232** in both: the default route remains the last resort in both rules, because for addresses that match no longer prefix, it is the only match. The **8** in the `west` column is also the same in both, and this is not a coincidence: the prefix `10110` overlaps with no shorter prefix, and no other row in the table contains it. **Divergence is born only from nested prefixes.** If the table had no nesting, the two rules would give the same decision, and the rule would not need to be written into the specification at all. #### Before and After the Break Now the rule is held fixed and the **table** changes. Three generations are placed side by side: tables converged with no break, tables that are still stale at the moment of the break, and tables converged again after the break. The same forty packets are run through all three between the same pairs. ```python """The table is a copy: same rule, three table generations. Eight nodes, a chord that cuts the ring; the measured break is that chord's loss. """ SEED = 20260810 NODES = ["a", "b", "c", "d", "e", "f", "g", "h"] 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 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 from each node to each destination.""" k, table = neighbors(links), {} for source in NODES: prev, frontier, seen = {}, [source], {source} while frontier: nxt = [] for u in frontier: for v in sorted(k[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] table[(source, dest)] = step return table def forward(source, dest, tables, links): """Runs the packet through the tables; returns its fate, hop count, and where it died.""" k, u, crossed, hop = neighbors(links), source, [], 0 while u != dest: if hop >= HOP_LIMIT: return "loop", hop, u nxt = tables.get((u, dest)) if nxt is None or nxt not in k[u]: return "black hole", hop, u if (u, nxt) in crossed: return "loop", hop, u crossed.append((u, nxt)) u, hop = nxt, hop + 1 return "reached", hop, None def pairs(count=40, seed=SEED): 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 measure(tables, links, count=40): tally, hops = {"reached": 0, "loop": 0, "black hole": 0}, 0 for x, y in pairs(count): fate, h, _ = forward(x, y, tables, links) tally[fate] += 1 hops += h return tally, hops old, new = oracle(LINKS), oracle(BROKEN) print(f"nodes {len(NODES)} | links {len(LINKS)} | table rows {len(old)} | " f"measured pairs {len(pairs())} | hop limit {HOP_LIMIT}") print() print(f"{'table generation':<27s} {'reached':>7s} {'loop':>6s} {'black hole':>11s} {'hops':>5s}") for name, tab, links in (("converged, no break", old, LINKS), ("at break, tables stale", old, BROKEN), ("after break, converged", new, BROKEN)): s, h = measure(tab, links) print(f"{name:<27s} {s['reached']:7d} {s['loop']:6d} {s['black hole']:11d} {h:5d}") print() changed = sum(1 for key in old if old[key] != new[key]) print(f"rows whose decision must change after the break: {changed}/{len(old)}") died = {} for x, y in pairs(): fate, _, node = forward(x, y, old, BROKEN) if fate != "reached": died[node] = died.get(node, 0) + 1 print("node where the packet died:", dict(sorted(died.items()))) ``` ``` nodes 8 | links 9 | table rows 56 | measured pairs 40 | hop limit 12 table generation reached loop black hole hops converged, no break 40 0 0 83 at break, tables stale 26 0 14 61 after break, converged 40 0 0 99 rows whose decision must change after the break: 11/56 node where the packet died: {'b': 6, 'f': 8} ``` #### Reading the Break The three rows say three separate things. **In the converged network, all forty of the forty packets reach their destination**, in a total of 83 hops. This is the state where the tables agree with reality, and it is the measurement's baseline. The bottom row gives the same result after the break: again **40/40**, but with **99** hops. Once the chord is gone, paths get longer; that is the sixteen-hop difference. What the network loses is not connectivity but shortness — **no packet is lost**. The middle row is the time in between. While the tables still point at the chord, **26 packets reach their destination and 14 fall into a black hole.** That fourteen is a measurable share: **0.350** of the set of forty packets, fourteen times the band's floor. The total hop count dropping to **61** here looks like an improvement at first glance, and that is exactly why it needs attention. Hops went down because a third of the packets **did not continue on their way**: a packet that falls into a black hole dies immediately and does not spend its remaining hops. **A low hop count here is not a success, it is the signature of a loss.** The last two rows say where the fault is. The number of rows whose decision must change after the break is **11**; the table carries fifty-six rows, so the large majority of rows stay correct. And yet fourteen packets die. The reason is that **every** dying packet dies at one of two nodes: six at **b**, eight at **f**. These are the two ends of the broken chord. What follows from this is the course's axis. A packet's fate **does not depend on the correctness of the table at the node it leaves from.** The source node's row can be correct; the packet, along the way, passes through a node whose table is wrong and dies there. Along the chain of decisions, it is the **oldest copy** that determines the outcome. #### Summary - The routing decision's input is the packet's destination address, its output is the next hop; the router knows not the whole path but only one hop. - The decision is made by looking not at what the message says but at the device's **own table**; the rule that determines the decision lives in the specification, not the table. - Longest prefix match chooses the narrowest set among the matching rows; a rule that reads by row order gives a different decision on **12** of the 256 addresses in the same table, and the divergence is born only from nested prefixes. - The table is not a configuration but a copy of a shared reality; in a converged network, all forty of the forty packets reach their destination, in **83** hops before the break and **99** after. - At the moment of the break, with stale tables, **26** packets reach their destination and **14** fall into a black hole; the drop in hops to **61** is not a gain, it is dying packets not spending hops. - Only **11** of the fifty-six rows are wrong, but all fourteen dying packets die at the two ends of the broken link: what determines the fate is not the source's copy but the **oldest** copy along the path. #### Next Step In this measurement, the tables were built by hand twice: once from the reality before the break, once from the reality after it. Nobody made the transition in between — the second-generation table was handed to the measurement already made. In a real network, someone has to make that transition, and there are two options: an administrator writes the table, or the devices tell each other. The next lesson puts these two options side by side and asks: when does a hand-written table learn about a break, and what does the black-hole count do over time? ### Static and Dynamic Routing Source: https://academia.sh/en/courses/switching-and-routing/static-and-dynamic-routing The static table never hears about the break, and the black-hole count stays at 14 across six rounds; in the dynamic regime where the news spreads, the loss ends in two rounds, but when only two nodes hear the news, the black hole drops to zero while 6 packets enter a loop and hops climb from 61 to 94. The previous measurement had two table generations, and the second was handed over ready-made: the reality after the break was computed, written into the tables, and the packets run through as is. Nobody made the transition in between. In a real network, someone has to make that transition, and there are only two ways to do it: either an administrator writes the rows by hand — **static routing** — or the devices tell each other the state of their links and build their own tables — **dynamic routing**. This lesson's question is not which one is better, but: when a break happens, **how many rounds** does it take to reach the correct table, and if it is never reached, what does the loss do over time? #### Writing and Telling In static routing, the table is a configuration text. The administrator writes, for every node, the next hop for every destination; the device reads these rows and never questions them. There is no mechanism that checks whether a row is correct, because the device has no second source to compare it against. ```text # taught transcript, not run rows hand-written for node b destination next hop a a c c d c e f f f g f h a ``` In the eight-node network, seven rows are written for every node, and the `e`, `f`, `g` rows route through the chord. When the chord breaks, this text does not change — the device keeps reading whatever is written in the file. In dynamic routing, the table is not a configuration but **the output of an agreement**. Devices notify their neighbors at regular intervals, produce their own rows from the incoming notifications, and tell their neighbors when a link drops. What the administrator writes is not the rows, but which links the protocol speaks on. The two regimes' costs fall in different places. In the static regime, the cost is **at write time**: in an eight-node network, every node has seven destinations, for a total of fifty-six rows. If the node count is $n$, the row count grows as $n(n-1)$ — eight hundred seventy rows at thirty nodes. In the dynamic regime, the cost is **at run time**: devices send notifications, process incoming notifications, and the tables stay wrong for a while during convergence. Part of the write cost can be shortened with the default route from the previous lesson. A node can pile every destination but one neighbor into a single empty-prefix row, dropping hand-written rows from seven to two. The measurement does not use this shortcut, because what is measured is not writing effort but **the correctness of the decision**: the default route reduces the row count, it does not change the ability to hear about a break. A shortened table that still points at the broken link sends the packet there just the same. #### The Static Table's Blind Spot A static table **never** learns that a link has broken. This is not a delay, it is an absence: no channel is defined for the news to travel through. A device can see its own link go down, but not one two hops away, and if its row points at that link, it keeps sending the packet there. The consequence in the measurement is this: in the static regime, the black-hole count is **not a function of time**. However many packets die in the first round, that many die in the hundredth round too. The loss does not stop, it **accumulates**. Stopping it requires an event from outside the measurement: an administrator noticing the fault and rewriting the rows. In the dynamic regime, on the other hand, the news has a channel. The two ends of the broken link see it directly, tell their neighbors, and those neighbors tell their own neighbors. The news spreads through the network like a wave, advancing one neighborhood hop every round. The measurement below models exactly this wave. The measurement's assumptions: - **RT8** — The network, the oracle, and the forty pairs are the same as in the previous lesson: eight nodes, nine links, the chord that cuts the ring. The measured break is again the loss of that chord. - **RT9** — In the static regime, the table never changes during the measurement. The administrator noticing the fault and intervening is outside the measurement; what is measured is the time until that intervention. - **RT10** — In the dynamic regime, the news starts from the two ends of the broken link and advances one neighborhood hop every round. A node that hears the news makes its table **correct**; a node that has not heard keeps its old table as is. - **RT11** — A round is a node receiving notifications from its neighbors and updating its table. A round is not a unit of clock time; its real-world counterpart is the protocol's notification interval, and it varies in seconds. - **RT12** — The same forty pairs are run again every round, and the measurement keeps no memory between rounds; every round is measured independently, with that round's tables. - **RT13** — The hop limit is 12; a packet that burns through it is counted as a loop. - **RT14** — The set's resolution is **1/40 = 0.025** over forty packets; no difference smaller than this is claimed. #### Measurement ```python """Static and dynamic: a table that never hears the break vs. one that does. In the static regime the table never changes. In the dynamic regime the news starts from the two ends of the broken link and advances one neighborhood hop every round. """ SEED = 20260810 NODES = ["a", "b", "c", "d", "e", "f", "g", "h"] 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 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): k, table = neighbors(links), {} for source in NODES: prev, frontier, seen = {}, [source], {source} while frontier: nxt = [] for u in frontier: for v in sorted(k[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] table[(source, dest)] = step return table def forward(source, dest, tables, links): k, u, crossed, hop = neighbors(links), source, [], 0 while u != dest: if hop >= HOP_LIMIT: return "loop", hop nxt = tables.get((u, dest)) if nxt is None or nxt not in k[u]: return "black hole", hop if (u, nxt) in crossed: return "loop", hop crossed.append((u, nxt)) u, hop = nxt, hop + 1 return "reached", hop def pairs(count=40, seed=SEED): 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 measure(tables, links, count=40): tally, hops = {"reached": 0, "loop": 0, "black hole": 0}, 0 for x, y in pairs(count): fate, h = forward(x, y, tables, links) tally[fate] += 1 hops += h return tally, hops def partial(old, new, informed): """Only the informed set has updated after the break; the rest carry their old table.""" return {(u, h): (new if u in informed else old)[(u, h)] for (u, h) in old} def informed_by(rnd, links=BROKEN, source=("b", "f")): """The news starts from the ends of the broken link, advancing one neighborhood hop per round.""" if rnd <= 0: return set() k, group, edge = neighbors(links), set(source), set(source) for _ in range(rnd - 1): edge = {v for u in edge for v in k[u]} - group group |= edge return group old, new = oracle(LINKS), oracle(BROKEN) changed = [(u, h) for (u, h) in old if old[(u, h)] != new[(u, h)]] print(f"table rows {len(old)} | rows to fix by hand after the break " f"{len(changed)} | nodes touched {len({u for u, _ in changed})}") print() print(f"{'round':>5s} {'informed':>8s} | {'static: reached':>16s} {'loop':>5s} {'blk hole':>8s}" f" {'hops':>4s} | {'dynamic: reached':>16s} {'loop':>5s} {'blk hole':>8s} {'hops':>4s}") static_loss = dynamic_loss = 0 for rnd in range(6): s, sh = measure(old, BROKEN) group = informed_by(rnd) d, dh = measure(partial(old, new, group), BROKEN) static_loss += s["loop"] + s["black hole"] dynamic_loss += d["loop"] + d["black hole"] print(f"{rnd:5d} {len(group):8d} | {s['reached']:16d} {s['loop']:5d} " f"{s['black hole']:8d} {sh:4d} | {d['reached']:16d} {d['loop']:5d} " f"{d['black hole']:8d} {dh:4d}") print(f"packets that miss their destination over six rounds: static {static_loss}, " f"dynamic {dynamic_loss}") print() print(f"{'informed set':<26s} {'reached':>7s} {'loop':>6s} {'black hole':>11s} " f"{'hops':>5s} {'died with correct table':>24s}") for name, group in (("nobody", set()), ("only b and f", {"b", "f"}), ("b, f, and their neighbors", informed_by(2)), ("everybody but d", set(NODES) - {"d"}), ("everybody", set(NODES))): tab = partial(old, new, group) s, h = measure(tab, BROKEN) correct_died = sum(1 for x, y in pairs() if forward(x, y, tab, BROKEN)[0] != "reached" and x in group) print(f"{name:<26s} {s['reached']:7d} {s['loop']:6d} {s['black hole']:11d} " f"{h:5d} {correct_died:24d}") ``` ``` table rows 56 | rows to fix by hand after the break 11 | nodes touched 6 round informed | static: reached loop blk hole hops | dynamic: reached loop blk hole hops 0 0 | 26 0 14 61 | 26 0 14 61 1 2 | 26 0 14 61 | 34 6 0 94 2 6 | 26 0 14 61 | 40 0 0 99 3 8 | 26 0 14 61 | 40 0 0 99 4 8 | 26 0 14 61 | 40 0 0 99 5 8 | 26 0 14 61 | 40 0 0 99 packets that miss their destination over six rounds: static 84, dynamic 20 informed set reached loop black hole hops died with correct table nobody 26 0 14 61 0 only b and f 34 6 0 94 1 b, f, and their neighbors 40 0 0 99 0 everybody but d 40 0 0 99 0 everybody 40 0 0 99 0 ``` #### The Flat Line and the Falling Line The static column is the same across all six rounds: **26 reached, 14 black hole, 61 hops.** This constancy is the measurement's most important finding. The loss does not shrink because there is no event to shrink it; the table did not hear about the break, and there is no channel for it to hear through. The packets that miss their destination over six rounds reach **84**, and this number keeps growing linearly with rounds. The dynamic column closes in two rounds: reached climbs to **40** in the second round and stays there. Total loss over six rounds is **20**. Same break, same topology, same forty packets — the only difference is whether the news has a channel. The manual-correction cost sits in the top row. **11** of the fifty-six rows become wrong, spread across **6** separate nodes. Even if the administrator learns that a link has broken, what needs fixing is not a single row: six devices have to be touched, and on each, which rows need to change has to be recomputed. In an eight-node network, this is one session's work; in a thirty-node network, it is something else. #### The Cost of Partial Information The bottom table looks **inside** the dynamic regime, and something unexpected is there. When nobody has heard, **14 packets fall into a black hole**, spending a total of **61** hops. When **only b and f** have heard about the break, the black hole drops to **zero** — an improvement at first glance, but the reached count is not 40, it is **34**: the remaining **6 packets enter a loop**, and total hops climb from **61** to **94**. This row pays off the course's second claim: **partial information produces a fault more expensive than no information at all.** The reason is in the nature of the fates. A packet that falls into a black hole **dies immediately**: it arrives at a node, finds a neighbor with no counterpart, and is dropped. The resource it spends is the hops it took up to that point. A packet that enters a loop, however, does not die; it **circles the network until it burns through the hop limit**, consuming link and processing capacity every round. The measurement says this in hop counts. The number of lost packets drops from 14 to 6 — more than half — while **hops spent climb from 61 to 94**. Few packets, many hops. The fault's appearance changes too: a black hole looks like a loss and is relatively easy to find; a loop **looks like congestion**, because the links are full and packets are flowing — it is just that none of them arrive. The rightmost column says why this is unavoidable. In the `only b and f` row there is **1** packet that leaves a node **whose table is correct** and dies anyway. That node has heard about the break, its row matches reality, its decision is flawless — and it still loses the packet, because the neighbor it hands the packet to has not heard. A structural conclusion follows: **no single device can put a packet into a loop by itself.** The situation where two tables send a packet back and forth to each other is called a **routing loop**; the measurement's short fate name for it is **loop**. The correctness of a device's decision does not depend on its own table but on **its neighbor's**. The last two rows show something else. When **everybody but d** has heard, the result is **40/40** — even though one node has still not heard. The reason is that none of the measured forty pairs pass through `d`'s changed rows. Partial information does not always produce a fault; the fault is born **only when the missing information falls on the packet's path**. #### Choosing by the Criterion The choice between the two regimes rests on a criterion readable from this measurement, and the criterion is not "which one is more advanced". Static routing is the right choice **when the path to the destination is unique**. In a stub network with a single exit, there is no alternative path; even if a dynamic protocol ran there, it would have no second path to discover, and nothing to do at the moment of a break. In a place like this, a protocol's notification traffic and state-keeping are an unreturned cost. Dynamic routing pays off **when there is more than one path**. The ring in the measurement is exactly this: when the chord breaks, every destination still has a path, and the dynamic regime finds it in two rounds. The reason the static regime cannot find it is not the absence of a path, but the absence of a mechanism that looks for one. A mix of the two is also an option, and a common one: static rows for stub networks, a dynamic protocol for the core. The criterion is the same in both cases — when a link breaks, **how many rounds** it takes to reach the correct table, and how many packets miss their destination during those rounds. This criterion is defined for the static regime too, but its counterpart is not in the protocol, it is in a person. A static network's convergence time is the time between the fault being noticed and the rows being rewritten; the measurement left this outside with **RT9**, because this duration cannot be read from the protocol: it has no upper bound like a notification interval, and it depends on how long the fault takes to be seen. The flat line in the measurement represents exactly this uncertainty — that line does not fall on its own. #### Summary - The administrator writes the static table, and its cost is at write time; the row count grows as $n(n-1)$ and is fifty-six rows at eight nodes. - The static table never hears about the break: the black-hole count stays at **14** across all six of the six rounds, and total loss over six rounds reaches **84** packets, versus **20** in the dynamic regime. - A manual correction is not a one-row job; **11** of the fifty-six rows become wrong across **6** separate nodes. - When only two nodes hear about the break, the black hole drops to **0**, but **6 packets enter a loop** and hops climb from **61** to **94**: partial information produces a fault that is more expensive and harder to see than no information at all. - Even **1** packet leaving a node with a correct table dies; no single device can put a packet into a loop by itself, a loop is a disagreement between at least two tables. - The choice criterion is the number of paths: a static row is enough in a single-path stub network; in a network with more than one path, the rounds the dynamic protocol finds pay off. #### Next Step In this measurement, the **carrying** of the news was not modeled: the informed set was given from outside, and every informed node arrived at the correct table instantly, as if it held the whole reality the moment the link broke. In reality, what a node hears from its neighbor is not the entire topology — the plainest protocol family hears exactly one thing from a neighbor: **how many hops away the neighbor is from every destination.** The next lesson measures how this single number spreads, how many rounds it takes to reach the correct table, and what fault this plainness brings. ### Distance Vector Protocols Source: https://academia.sh/en/courses/switching-and-routing/distance-vector-protocols A neighbor is heard from only as a sequence of distances; from a cold start, the correct table is reached in four rounds, and reached packets per round go 0, 9, 20, 32, 40. The one trade-off needed to learn bad news gives rise to counting to infinity: when a destination becomes unreachable, all sixty of the sixty packets in a twelve-round window enter a loop. The previous measurement did not model the news being carried: the informed set was given from outside, and an informed node arrived at the correct table instantly. In reality, what a node hears from its neighbor is not the entire topology; nobody sends its neighbor a map saying "the network is connected like this." The plainest protocol family hears exactly one thing from a neighbor: **how many hops away the neighbor is from every destination.** This family is called the **distance vector** family, and this lesson's question is whether this single number is enough to build the correct table. #### The One Thing Heard From a Neighbor A node sends its neighbors a list: a **metric** for every destination. Here, the metric is the hop count. The list does not say who the neighbor's neighbor is, which path is taken, or how the network is connected — it says only the distance. ```text # taught transcript, not run node c's notification to its neighbors destination metric a 3 b 1 d 1 e 2 f 2 g 3 h 4 ``` The node receiving the notification takes two steps. It **adds one** to every incoming metric — the cost of reaching the neighbor is one hop. Then it compares this to the metric in its own table and takes the **smaller one**; when it does, it writes that neighbor's name into the next-hop field. The information constraint here is the family's definition. `b`, receiving `c`'s notification, learns that `a` is reached in three hops; it does not learn **which nodes** are passed through to get there. This makes the computation cheap: the notification received is not the topology, it is the neighbor's **already-chewed** decision. The node does not do its own computation, it adds one to its neighbor's computation. #### What Convergence Means Here What is measured throughout the course is **convergence**, and this same term was also used in the Introduction to System Design course. There, what converged was **copies of a data value**: copies of the same record read differently for a while, eventually arrive at the same value, and what is observed is **the value read**. Here, what converges is not data but the **routing table**, and what is observed is not the value read but the **packet's fate**. The term is the same, the sense is different; the two are not to be confused. #### The Rule That Accepts Only Improvement The rule's first form is the plainest: **a node changes its table only when it hears of a shorter path.** If the incoming metric is larger than what it already holds, it discards the notification. This rule is intuitive and guarantees one thing for certain — the table never gets worse. The measurement's first part traces this rule from a **cold start**: no node holds anything, everybody knows only its own neighbors, and the tables fill up round by round. The measurement's assumptions: - **RT15** — The network, the oracle, and the forty pairs are the same as in the previous lessons. In the first and third parts, the broken link is again the chord that cuts the ring. - **RT16** — In the first part, the start is **cold**: every node's distance to itself is zero, to everyone else it is 99, and there is no table row at all. What is measured is the round-by-round build-up from scratch. - **RT17** — A round is every node receiving notifications from its neighbors and updating its table once; notifications are taken as simultaneous. A round has no counterpart in seconds. - **RT18** — The metric is the hop count, and every link's cost is one. The metric's ceiling is **16**, and an entry that reaches this ceiling is counted as **unreachable**; the ceiling is infinity's finite stand-in. - **RT19** — The break measured in the second part is different: both links into node `d` drop at once, and `d` is cut off from the network. The remaining seven nodes stay connected to each other. The start in this part is not cold; it is the table converged to the pre-break reality. - **RT20** — The hold-down window is six rounds and opens only when an entry becomes **unreachable**; for that window, no notification is accepted for that entry. - **RT21** — The set's resolution is **1/40 = 0.025** over forty packets. The second part's window is twelve rounds at five packets per round; the set there is sixty packets. #### Measurement ```python """Distance vector: only a single number is heard from a neighbor. Part 1 - cold start; a node accepts only a BETTER path. Part 2 - bad news is accepted too; counting to infinity and two restrictions. """ SEED = 20260810 NODES = ["a", "b", "c", "d", "e", "f", "g", "h"] 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")] ISOLATED = [b for b in LINKS if b not in (("c", "d"), ("d", "e"))] HOP_LIMIT, INFINITY, WINDOW = 12, 16, 12 def generator(seed): d = seed % 2147483646 + 1 def r(n): nonlocal d d = (d * 48271) % 2147483647 return d % n return r 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): k, table = neighbors(links), {} for source in NODES: prev, frontier, seen = {}, [source], {source} while frontier: nxt = [] for u in frontier: for v in sorted(k[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] table[(source, dest)] = step return table def forward(source, dest, tables, links): k, u, crossed, hop = neighbors(links), source, [], 0 while u != dest: if hop >= HOP_LIMIT: return "loop", hop nxt = tables.get((u, dest)) if nxt is None or nxt not in k[u]: return "black hole", hop if (u, nxt) in crossed: return "loop", hop crossed.append((u, nxt)) u, hop = nxt, hop + 1 return "reached", hop def pairs(count=40, seed=SEED): 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 measure(tables, links, count=40): tally = {"reached": 0, "loop": 0, "black hole": 0} for x, y in pairs(count): tally[forward(x, y, tables, links)[0]] += 1 return tally def only_improve(links, rounds): """A neighbor's distance vector is heard; only a shorter path is accepted.""" k = neighbors(links) dist = {(u, h): (0 if u == h else 99) for u in NODES for h in NODES} first = {} for _ in range(rounds): new_dist, new_first = dict(dist), dict(first) for u in NODES: for v in sorted(k[u]): for h in NODES: if dist[(v, h)] + 1 < new_dist[(u, h)]: new_dist[(u, h)] = dist[(v, h)] + 1 new_first[(u, h)] = v dist, first = new_dist, new_first return dist, first def recompute(links, rounds, start, split_horizon=False, hold_down=0): """Every round, the table is rebuilt from neighbor notifications; bad news is accepted too.""" k, trace = neighbors(links), [] dist, first = dict(start[0]), dict(start[1]) frozen = {key: 0 for key in dist} for _ in range(rounds): new_dist, new_first = dict(dist), dict(first) for u in NODES: for h in NODES: if u == h or frozen[(u, h)] > 0: continue best, pick = (1, h) if h in k[u] else (INFINITY, None) for v in sorted(k[u]): if split_horizon and first.get((v, h)) == u: continue cost = min(dist[(v, h)] + 1, INFINITY) if cost < best: best, pick = cost, v if best >= INFINITY > dist[(u, h)]: frozen[(u, h)] = hold_down new_dist[(u, h)], new_first[(u, h)] = best, pick for key in frozen: frozen[key] = max(0, frozen[key] - 1) dist, first = new_dist, new_first trace.append((dict(dist), dict(first))) return trace correct = oracle(BROKEN) print("Part 1 -- cold start, only a shorter path is accepted") print(f"{'round':>5s} {'reached':>7s} {'loop':>6s} {'black hole':>11s} {'rows matching oracle':>21s}") for rnd in range(6): first = only_improve(BROKEN, rnd)[1] s = measure(first, BROKEN) same = sum(1 for key in correct if first.get(key) == correct[key]) print(f"{rnd:5d} {s['reached']:7d} {s['loop']:6d} {s['black hole']:11d}" f" {same:18d}/{len(correct)}") start = only_improve(LINKS, 8) d_targeted = [(x, y) for x, y in pairs() if y == "d"] print() print(f"Part 2 -- d isolated, {WINDOW}-round window, {len(d_targeted)} packets per round") print(f"{'restriction':<28s} {'ceiling round':>13s} {'loop':>6s} {'black hole':>11s} " f"{'hops':>5s} {'peak metric':>11s}") for label, sh, hd in (("none", False, 0), ("hold-down", False, 6), ("split horizon", True, 0), ("split horizon + hold-down", True, 6)): loop = black = hops = peak = 0 ceiling = None for i, (dist, first) in enumerate(recompute(ISOLATED, WINDOW, start, sh, hd), 1): for x, y in d_targeted: fate, h = forward(x, y, first, ISOLATED) loop += fate == "loop" black += fate == "black hole" hops += h peak = max(peak, max(dist[(u, "d")] for u in NODES if u != "d")) if ceiling is None and all(dist[(u, "d")] >= INFINITY for u in NODES if u != "d"): ceiling = i print(f"{label:<28s} {ceiling if ceiling else '>' + str(WINDOW):>13} {loop:6d} " f"{black:11d} {hops:5d} {peak:11d}") print() print("Part 3 -- chord broke, every destination stays reachable") print(f"{'restriction':<28s} {'convergence round':>18s}") for label, sh, hd in (("none", False, 0), ("hold-down", False, 6), ("split horizon", True, 0), ("split horizon + hold-down", True, 6)): reached_round = None for i, (dist, first) in enumerate(recompute(BROKEN, 20, start, sh, hd), 1): if all(first.get(key) == correct[key] for key in correct): reached_round = i break print(f"{label:<28s} {reached_round if reached_round else '>20':>18}") ``` ``` Part 1 -- cold start, only a shorter path is accepted round reached loop black hole rows matching oracle 0 0 0 40 0/56 1 9 0 31 16/56 2 20 0 20 32/56 3 32 0 8 48/56 4 40 0 0 56/56 5 40 0 0 56/56 Part 2 -- d isolated, 12-round window, 5 packets per round restriction ceiling round loop black hole hops peak metric none >12 60 0 202 13 hold-down >12 60 0 202 13 split horizon >12 5 55 59 16 split horizon + hold-down 6 5 55 41 16 Part 3 -- chord broke, every destination stays reachable restriction convergence round none 2 hold-down 2 split horizon 3 split horizon + hold-down 7 ``` #### Four Rounds The first part gives the family's basic number. From cold start, the correct table is reached in **four rounds**, and reached packets per round go **0, 9, 20, 32, 40**. In round zero, no packet arrives: because the table is empty, every packet dies at the first node — forty black holes. Distance vector starts the network **knowing nothing at all**; it has not even written who its neighbor is into the table. In the following rounds, the number of rows matching the oracle advances as **16, 32, 48, 56**: exactly sixteen rows correct themselves every round. The regularity is not a coincidence, it is the nature of the notification. In one round, information advances exactly one neighborhood hop; in the first round, one-hop destinations are written correctly, in the second, two-hop destinations. Whatever the network's diameter is, that is the convergence round. It is also meaningful that the reached-packet count does not grow as fast as the row count: for a packet to arrive, **every** row along its path has to be correct. Even when thirty-two rows are correct, eight packets still die, because those eight have a not-yet-filled row somewhere on their path. #### Learning Bad News The first part's rule cannot do one thing: it **cannot learn bad news.** A node that accepts only a shorter path can never hear that a path has gotten longer or has vanished — because by definition, that news arrives with a larger metric, and the rule discards it. This is why real protocols make a trade-off: **a notification from the neighbor chosen as the next hop is accepted even when it is bad news.** The trade-off is mandatory; without it, the blindness of the static regime from the previous lesson comes back. Counting to infinity is born exactly from this trade-off. When a destination becomes unreachable, nodes hear each other's old metric, add one, and write it; their neighbor hears theirs in turn, adds one, and writes it. The metric grows **one by one** round after round, and no node understands that the destination is really gone until it reaches the ceiling. This behavior is called **counting to infinity**. #### Counting to Infinity and Two Restrictions The second part measures this behavior. When node `d` is cut off from the network, under the unrestricted rule the peak metric only climbs to **13** in twelve rounds — it does not even reach the ceiling of 16. In that window, **all sixty of the sixty** `d`-targeted packets enter a loop, and **202** hops are spent. The black-hole count is **0**: no packet dies, all of them circle. The reading built in the previous lesson shows up here in its purest form — **the fault is not a lost packet, it is saturated links.** The first restriction is called **split horizon**, and it is a single rule: a node **does not advertise a path to a destination back to the neighbor that is that path's first hop**. The reasoning is plain — that neighbor is already routing through it; selling its own path back to it is not information, it is an echo. The measurement confirms the gain: loop drops from **60** to **5**, hops from **202** to **59**. Black hole climbs to **55**, meaning most packets now die immediately instead of circling. This is not a loss. In both fates the packet fails to reach its destination, but one dies **in one hop**, the other spends **twelve hops** of network resources; the drop in the hops column measures this. Split horizon still is not enough. The `ceiling round` column says it is still not complete at twelve rounds: it cuts two-node loops, but not the **longer** loops the ring forms. A node reaches the ceiling, then hears an old metric from a neighbor that has not reached it yet and drops back down. The second restriction is this **hold-down**: when an entry becomes unreachable, the node freezes that entry for a window and accepts no notification for that destination during it. Over the window, the neighbors' stale metrics filter out. Its effect in the measurement is clean: the round the ceiling is reached is **6**, and hops drop from **59** to **41**. But hold-down **by itself** does nothing — the second row is identical to the unrestricted row: 60 loop, 202 hops. The reason is that hold-down opens only when an entry becomes **unreachable**, and under the unrestricted rule no entry ever reaches the ceiling, so the window never opens. There is no restriction whose trigger never fires. The third part gives the cost. In an ordinary break where destinations stay reachable, the unrestricted rule converges in **2 rounds**, split horizon in **3**, and the two together in **7**. Hold-down hurts twice here: split horizon temporarily shows an entry as unreachable, and hold-down mistakes this temporary state for true and freezes it for six rounds. **Every restriction that speeds up bad news slows down good news.** #### Summary - In the distance vector family, a node hears from its neighbor only a sequence of metrics; it does not learn the topology, it learns its neighbor's already-made decision and adds one to it. - From cold start, the correct table is reached in **four rounds**; reached packets per round are **0, 9, 20, 32, 40**, correct rows are **0, 16, 32, 48, 56** — every round advances one neighborhood hop. - A rule that accepts only a shorter path cannot learn bad news; the trade-off made to learn it gives rise to counting to infinity. - When a destination becomes unreachable, under the unrestricted rule, all sixty of the sixty packets in a twelve-round window enter a loop, **202** hops are spent, and the metric does not even reach the ceiling. - Split horizon brings loop down to **5** and hops to **59**; when hold-down is added, the ceiling is reached in round **6** and hops drop to **41**, but hold-down by itself does nothing because its trigger never fires. - The restrictions' cost is paid in an ordinary break: the convergence round climbs from **2** to **3**, and to **7** when both are combined. #### Next Step All these flaws have a single source: a node hears its neighbor's **decision**, not what its neighbor **sees**. Because the metric is compressed into a single number, which path that number summarizes is lost; the node cannot tell whether its own name appears inside that path, and the restrictions try to patch this ignorance from the outside. The next lesson reverses the trade-off: if neighbors send each other not a decision but **raw link information**, and every node computes the shortest path itself, how many rounds does it take to converge? ### Link State Protocols Source: https://academia.sh/en/courses/switching-and-routing/link-state-protocols A neighbor is sent not a decision but raw link information; every node builds its own link-state database and computes the shortest path itself. The correct table is reached in three rounds, and it is ahead of distance vector in every round: 9, 20, 32, 40 against 0, 9, 20, 32. All of the previous lesson's flaws came from a single place: a node heard its neighbor's **decision**, not what its neighbor **saw**. A number in the distance vector had been produced by adding one to a number the neighbor itself had heard from its own neighbor; which path that number passed through was lost during the compression. The **link state** family reverses the trade-off. What is sent to a neighbor is not a decision but **a raw fact**: "this link exists, and its metric is this." As the fact travels, it is not changed, not summarized, nothing is added to it. Every node accumulates the facts that reach it and computes the shortest path **itself**. This lesson's question is how many rounds this exchange saves, and where the gain comes from. #### What Is Sent to a Neighbor In distance vector, a node sent an eight-row sequence of metrics: one number per destination. In link state, what is sent is much smaller — a node advertises only **its own links**. ```text # taught transcript, not run node c's advertisement advertiser c neighbor b metric 1 neighbor d metric 1 the database accumulated in node c's hands, two rounds later a–b b–c c–d d–e e–f f–g g–h h–a ``` The difference is not in the notification's size, it is in **who is speaking for whom**. In distance vector, `c` said that `h` was reached in four hops — this was `c`'s own decision, and it contained something about `h` that `c` did not actually know. In link state, `c` advertises only the two links it sees itself; it says nothing about `h`, because it sees nothing about `h`. #### Flooding and the Link-State Database The advertisement does not stop at the neighbor. The receiving node passes it on to its own neighbors **as is**; this is the counterpart here of the **flooding** mechanism built in the Network Models and Protocols course. While passing it on, it does not change the advertisement, does not add to its metric, does not write its own name. As it spreads through the network, the advertisement stays **the same advertisement**. Every node accumulates the incoming advertisements. What accumulates is called the **link-state database**, and in the end it is nothing more than the network's list of links. Once the database is complete, the node holds the topology itself in its hands — in the form nobody has summarized, nobody has chewed. What comes after this is a graph computation. Taking itself as the source, the node finds the shortest path to every destination and writes the path's **first hop** into its table. This computation itself was established in the Graph Algorithms course of the Algorithms curriculum and is not re-derived here; what matters here is **where** the computation is done. In distance vector, the computation was distributed, and every node built on top of its neighbor's computation. Here the computation is **local**: every node independently derives the same result from the same input. This has a direct consequence. A wrong table can no longer come from a wrong computation — the computation is the same everywhere. A wrong table comes only from **incomplete input**: the database has not filled up yet. The measurement counts this incompleteness. #### The Database's Cost This mechanism is not free, and its cost is collected in two places. The first is size. In distance vector, what a node holds is as many rows as there are destinations; in link state, what it holds is **the entire network**. In the measured network, this means eight links, but as the link count grows, every node's memory and the computation it does on every change grow with it. This is why large networks split the topology into regions and keep each region's database within itself: the computation's input is shrunk. The second is freshness. Because an advertisement is carried without being changed, an **old** advertisement circulating in the network can get mixed up with a new one, and a node can mistake a past link for a current one. This is why every advertisement carries a **sequence number** and an **age**; when a node sees two advertisements from the same advertiser, it keeps the one with the larger number and drops the one whose age has run out. These two fields are the one mechanism that resolves the copies' disagreement inside the protocol itself. The measurement's assumptions: - **RT22** — The network, the oracle, and the forty pairs are the same as in the previous lessons; the measured break is again the loss of the chord that cuts the ring, and both families are measured in the same topology. - **RT23** — In the link state family, a node's starting information is **its own links**. This information is not heard from a neighbor, it is directly observed; the device at the link's end sees its own interface. - **RT24** — A round is every node passing on the set of links it holds to all its neighbors and adding the incoming ones to its own set. The advertisement is **not changed** while being carried. - **RT25** — A node computes the shortest path from the set of links it holds with the **same procedure** as the oracle. The procedure is the same at every node; the only thing that comes out different is the input. A table that comes from incomplete input is wrong, not the procedure. - **RT26** — The distance vector side is the previous lesson's cold-start rule: a node hears its neighbor's metric sequence and takes only the shorter path. - **RT27** — In the carried-entries count, distance vector sends every neighbor its eight-destination sequence, link state sends the set of links it knows. The model floods **every round**; real protocols do not flood unless something changes, so the count is meaningful only for the convergence window. - **RT28** — The set's resolution is **1/40 = 0.025** over forty packets. #### Measurement ```python """Link state: a neighbor is sent raw link facts, not a decision. Part 1 - both families' packet fate, round by round, side by side. Part 2 - correct rows, known links, and entries carried up to that round. """ SEED = 20260810 NODES = ["a", "b", "c", "d", "e", "f", "g", "h"] 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 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): k, table = neighbors(links), {} for source in NODES: prev, frontier, seen = {}, [source], {source} while frontier: nxt = [] for u in frontier: for v in sorted(k[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] table[(source, dest)] = step return table def forward(source, dest, tables, links): k, u, crossed, hop = neighbors(links), source, [], 0 while u != dest: if hop >= HOP_LIMIT: return "loop", hop nxt = tables.get((u, dest)) if nxt is None or nxt not in k[u]: return "black hole", hop if (u, nxt) in crossed: return "loop", hop crossed.append((u, nxt)) u, hop = nxt, hop + 1 return "reached", hop def pairs(count=40, seed=SEED): 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 measure(tables, links, count=40): tally = {"reached": 0, "loop": 0, "black hole": 0} for x, y in pairs(count): tally[forward(x, y, tables, links)[0]] += 1 return tally def distance_vector(links, rounds): """A summarized metric is heard from a neighbor; only a shorter path is taken.""" k = neighbors(links) dist = {(u, h): (0 if u == h else 99) for u in NODES for h in NODES} first = {} for _ in range(rounds): new_dist, new_first = dict(dist), dict(first) for u in NODES: for v in sorted(k[u]): for h in NODES: if dist[(v, h)] + 1 < new_dist[(u, h)]: new_dist[(u, h)] = dist[(v, h)] + 1 new_first[(u, h)] = v dist, first = new_dist, new_first return first def link_state(links, rounds): """Raw link facts are carried unchanged; the node computes them itself.""" k = neighbors(links) known = {u: {(u, v) for v in k[u]} for u in NODES} carried = 0 for _ in range(rounds): carried += sum(len(known[u]) * len(k[u]) for u in NODES) new = {u: set(known[u]) for u in NODES} for u in NODES: for v in k[u]: new[u] |= known[v] known = new tables = {} for u in NODES: local = oracle([tuple(sorted(b)) for b in known[u]]) for (x, h), step in local.items(): if x == u: tables[(u, h)] = step return tables, known, carried correct = oracle(BROKEN) k_broken = neighbors(BROKEN) dv_round_entries = sum(len(NODES) * len(k_broken[u]) for u in NODES) print(f"nodes {len(NODES)} | links after break {len(BROKEN)} | table rows " f"{len(correct)} | measured packets {len(pairs())}") print() print(f"{'round':>3s} | {'distance vector: reached':>25s} {'loop':>6s} {'blk hole':>8s}" f" | {'link state: reached':>25s} {'loop':>6s} {'blk hole':>8s}") for rnd in range(6): dv = measure(distance_vector(BROKEN, rnd), BROKEN) ls = measure(link_state(BROKEN, rnd)[0], BROKEN) print(f"{rnd:3d} | {dv['reached']:25d} {dv['loop']:6d} {dv['black hole']:8d}" f" | {ls['reached']:25d} {ls['loop']:6d} {ls['black hole']:8d}") print() print(f"{'round':>3s} {'DV correct rows':>15s} {'LS correct rows':>15s} " f"{'LS known links':>15s} {'LS carried':>11s} {'DV carried':>11s}") for rnd in range(6): dv = distance_vector(BROKEN, rnd) ls, known, carried = link_state(BROKEN, rnd) links_known = {len({tuple(sorted(b)) for b in known[u]}) for u in NODES} print(f"{rnd:3d} {sum(1 for a in correct if dv.get(a) == correct[a]):12d}/56" f" {sum(1 for a in correct if ls.get(a) == correct[a]):12d}/56" f" {min(links_known):8d}/{len(BROKEN):<5d} {carried:11d} {dv_round_entries * rnd:11d}") ``` ``` nodes 8 | links after break 8 | table rows 56 | measured packets 40 round | distance vector: reached loop blk hole | link state: reached loop blk hole 0 | 0 0 40 | 9 0 31 1 | 9 0 31 | 20 0 20 2 | 20 0 20 | 32 0 8 3 | 32 0 8 | 40 0 0 4 | 40 0 0 | 40 0 0 5 | 40 0 0 | 40 0 0 round DV correct rows LS correct rows LS known links LS carried DV carried 0 0/56 16/56 2/8 0 0 1 16/56 32/56 4/8 32 128 2 32/56 48/56 6/8 128 256 3 48/56 56/56 8/8 288 384 4 56/56 56/56 8/8 512 512 5 56/56 56/56 8/8 768 640 ``` #### Ahead in Every Round The top table places the two families side by side in the same break, with the same forty packets. Link state reaches the correct table in **three rounds**, distance vector in **four**. And the difference is not only at the finish line: link state is ahead **every round**. In round zero, **9** against **0**; in round one, **20** against **9**; in round two, **32** against **20**. Round zero is the row that says the most. No advertisement has been sent yet, and link state still **delivers 9 packets**. The reason is assumption RT23: a node's own links are not heard from a neighbor, they are seen directly. The device at the link's end knows that link exists without a protocol. In distance vector, even this piece of information waits for a round's notification, because there, what gets written into the table is a metric that has been **heard**. The loop column is **0** from start to finish in both families. This is not a coincidence, it is the result of the cold start: both rules accept only a shorter path, and no table row points at a wrong neighbor — it points at **nothing** yet. A wrong direction first has to have some direction written; an empty row produces a black hole, not a loop. #### Where the Difference Is The bottom table looks for the source of the gain, and at first glance it does not give the expected answer. The correct-rows columns advance by **exactly sixteen rows per round** in both families: distance vector 0, 16, 32, 48, 56; link state 16, 32, 48, 56. **The rate of increase is the same.** Both families advance one neighborhood hop per round, because in both, information crosses one link per round. Link state does not spread faster, and distance vector does not spread slower. The only difference between the two sequences is their **starting point**. Link state's sequence is distance vector's sequence **shifted by one round**. The round gained is not gained speed, it is a gained **head start**. The carried-entries columns also say the opposite of what is expected. By its own convergence round (the third), link state has carried **288** entries; by its own convergence round (the fourth), distance vector has carried **384**. So the family that converges earlier has carried **less** information. The known-links column confirms this: the largest load a link-state node carries is **eight links**, and it stops there, because the entire network is eight links. Distance vector, on the other hand, resends its eight-destination sequence to every neighbor every round, and this load never shrinks. The fourth reading follows from this: **the difference is not in the amount of information, it is in how far the information is carried unread.** In distance vector, the number a node knows about `h` has come by being recomputed at every node in between, starting from `h`; at every stop, an addition was made and everything before that stop was erased. In link state, `h`'s links arrive in the form they left `h`'s mouth; the nodes in between are carriers, not interpreters. Information that is not interpreted is the same information regardless of the distance it is carried. The fifth round's row also calls for honesty. There, the entries link state has carried climb to **768**, overtaking distance vector. This is the consequence of the model constraint written in RT27: the measurement floods every round. Real protocols do not flood once converged unless something changes; the count is therefore read only for the convergence window. #### Where the Two Families Both Arrive Despite all these differences, the two families arrive at the same place. After the fourth round, both columns give **56/56** correct rows and **40/40** reached packets. The tables are not just equally correct, they are **identical to each other**: both are the oracle's table. The reason is structural. Both families search for the same thing — the **shortest path**. Distance vector finds it by summing its neighbors' metrics, link state finds it by building the topology and computing it itself; but the criterion being searched for is single. A search with a single criterion has a single result, and this is why the place where the two families part ways is not the result, it is the time it takes to arrive at it and the packet's fate during that time. #### Summary - In the link state family, a neighbor is sent not a decision but raw link information; the advertisement is not changed while being carried, and every node computes the shortest path itself. - A wrong table cannot come from a wrong computation, because the computation is the same at every node; a wrong table comes only from **incomplete input**. - The correct table is reached in **three rounds**, and it is ahead of distance vector every round: reached packets are **9, 20, 32, 40** against **0, 9, 20, 32**. The 9 packets in round zero come from a node knowing its own links without a protocol. - The correct-row increase is **sixteen per round** in both families; link state's sequence is distance vector's sequence **shifted by one round**. What is gained is not speed, it is a head start. - At the convergence round, entries carried are **288** for link state, **384** for distance vector: the earlier-converging family carries less information. The difference is not in the amount of information, it is in how far the information is carried **without being interpreted**. - Both families reach **56/56** correct rows and **40/40** reached packets after the fourth round; the tables are identical to each other, because both search for the same criterion. #### Next Step The last part's finding is this: both families were searching for the **shortest path**, and both eventually arrived at **the same table**. Because the criterion was single, the result was single too; the entire difference between them was packed into the rounds it took to reach that result. This means the criterion itself was never questioned — shortness was taken as good without being examined. But a path is not judged by its length alone: whose network it passes through, whose link it fills, and what it costs whom are also qualities of the path. The next lesson asks: what if the shortest path is **not wanted** — what does the table get built on then, and is a longer path a flaw? ### Border Gateway Protocol Source: https://academia.sh/en/courses/switching-and-routing/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. ### Routing Instances Source: https://academia.sh/en/courses/switching-and-routing/routing-instances When a single device keeps more than one routing table, the same destination goes to two separate next hops: three instances carry the same forty packets in 83, 99, and 91 hops, 18 of the 56 rows diverge, and when the instances are collapsed into a single table, 14 packets fall into a black hole. 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. ```text # 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 ```python """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? ### MPLS and Label Switching Source: https://academia.sh/en/courses/switching-and-routing/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. ### Overlay Networks Source: https://academia.sh/en/courses/switching-and-routing/overlay-networks A logical topology built with tunnels keeps its own table and never sees the table beneath it: when the underlay breaks, not a single row of the overlay's table changes, but the underlay's hops climb from 188 to 211; when the underlay's tables go stale, 21 packets die even though the overlay's table is correct; and the overlay tables' partial information puts 12 packets into a loop with not a single wrong decision in the underlay. The previous lesson 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. The label named the path, and the path it named was physical. This lesson's question is: what would happen if the link between two nodes were not a physical link but a logical one, **built over another network**? Then there would not be one table but **two tables**, the two would converge separately, and the packet's fate would be tied to **both** of them agreeing. This is the most extreme form of the course's axis of measurement. #### Overlay and Underlay An **overlay network** is a logical topology built with tunnels. A link in the overlay does not mean there is a direct cable between two nodes; it means those two nodes **count each other as neighbors**. The real set of links the overlay stands on is called the **underlay**. (`Subnet` on its own is reserved for the concept that divides an address block; the concept here is named the **underlay**, and the two are not to be confused.) The Containers course built container networks' overlay; that procedure is not repeated here. Here, the overlay is measured as a **logical topology**: it has its own table, its own neighborhood, its own convergence, and its own hop counter. ```text # taught transcript, not run overlay link path in the underlay meaning a-c a-b-c a and c are neighbors in the overlay a-e a-b-f-e a and e are neighbors in the overlay c-f c-b-f c and f are neighbors in the overlay tunneled packet outer header source a dest c <- only the underlay reads this inner header source a dest g <- only the overlay reads this payload ... node a's two tables overlay table underlay table dest next hop dest next hop g e c b d d e b ``` The two tables on the right are the whole lesson. Node `a`'s overlay points to `e` for destination `g`; `e` is a neighbor in the overlay but three hops away in the underlay. As the packet leaves `a`, it goes to `b` according to the underlay table, and the overlay never sees this at all. The two tables are inside the same device, and **neither reads the other**. This has a direct consequence: **one overlay hop is several hops in the underlay.** The two layers' counters are separate, and they have to be counted separately. The measurement's assumptions: - **RT81** — The underlay 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. - **RT82** — The overlay is built from nine tunnels, and **none** of the tunnels is the same as an underlay link; every tunnel corresponds to a path of between two and four hops in the underlay. - **RT83** — The two layers' tables are computed separately and do not see each other. The rule is the same in both: the **first hop of the shortest path** to every destination. The oracle is not changed. - **RT84** — Every layer has its own hop counter, and the limit for both is 12. Underlay hops spent inside one overlay hop are **not added** to the overlay counter. - **RT85** — An overlay hop is counted as taken only if the tunnel was delivered in the underlay; if the tunnel cannot be delivered, the packet's fate is the tunnel's fate. - **RT86** — In the last two regimes, the overlay link that drops is the `a–c` tunnel. In the fourth, only `a` and `c` hear about the drop; the other seven nodes keep their old overlay table. - **RT87** — In the last two regimes, the underlay's table is **the oracle itself**: there is not a single wrong decision in the underlay, and not a single tunnel is undeliverable. - **RT88** — The forty source–destination pairs come from the course's core generator, each occurrence is a separate packet, and the set's resolution is `1/40 = 0.025`. #### Measurement ```python """Overlay network: when the overlay's table and the underlay's table disagree.""" 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")] OVERLAY = [("a", "c"), ("a", "d"), ("a", "e"), ("b", "d"), ("b", "g"), ("c", "f"), ("d", "h"), ("e", "g"), ("f", "h")] 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): """Runs a single layer; returns the fate and the hops it took.""" kom, u, crossed, hop = neighbors(links), source, [], 0 while u != dest: if hop >= HOP_LIMIT: return "loop", hop s = t.get((u, dest)) if s is None or s not in kom[u]: return "black hole", hop if (u, s) in crossed: return "loop", hop crossed.append((u, s)) u, hop = s, hop + 1 return "reached", hop def overlay_forward(source, dest, over, over_links, under, under_links): """Every overlay hop is a tunnel, and it is also run in the underlay.""" kom, u, crossed, over_hop, under_hop = neighbors(over_links), source, [], 0, 0 while u != dest: if over_hop >= HOP_LIMIT: return "overlay loop", over_hop, under_hop s = over.get((u, dest)) if s is None or s not in kom[u]: return "overlay black hole", over_hop, under_hop if (u, s) in crossed: return "overlay loop", over_hop, under_hop fate, a = forward(u, s, under, under_links) under_hop += a if fate != "reached": return "tunnel " + fate, over_hop, under_hop crossed.append((u, s)) u, over_hop = s, over_hop + 1 return "reached", over_hop, under_hop def partial(old, new, informed): """Only the informed set has heard that the overlay link came down.""" return {(u, h): (new if u in informed else old)[(u, h)] for (u, h) in old if (u, h) in new} def measure(over, over_links, under, under_links): tally = {"reached": 0, "overlay loop": 0, "overlay black hole": 0, "tunnel black hole": 0, "tunnel loop": 0} oa = ua = 0 for x, y in pairs(): fate, o_, a_ = overlay_forward(x, y, over, over_links, under, under_links) tally[fate] += 1 oa += o_ ua += a_ return tally, oa, ua UP, DOWN, DOWN_NEW = oracle(OVERLAY), oracle(LINKS), oracle(BROKEN) MISSING = [b for b in OVERLAY if b != ("a", "c")] UP_MISSING = oracle(MISSING) REGIME = (("both layers converged", UP, OVERLAY, DOWN, LINKS), ("underlay broke, converged", UP, OVERLAY, DOWN_NEW, BROKEN), ("underlay broke, table stale", UP, OVERLAY, DOWN, BROKEN), ("tunnel dropped, two ends heard", partial(UP, UP_MISSING, {"a", "c"}), MISSING, DOWN, LINKS), ("tunnel dropped, everybody heard", UP_MISSING, MISSING, DOWN, LINKS), ("both layers stale", partial(UP, UP_MISSING, {"a", "c"}), MISSING, DOWN, BROKEN)) RESULT = [(name, measure(over, ol, under, ul)) for name, over, ol, under, ul in REGIME] print(f"{'regime':<32s} {'reached':>7s} {'overlay loop':>16s} " f"{'tunnel black hole':>18s}") for name, (s, oa, ua) in RESULT: print(f"{name:<32s} {s['reached']:7d} {s['overlay loop']:16d} " f"{s['tunnel black hole']:18d}") print() print(f"{'regime':<32s} {'overlay hops':>14s} {'underlay hops':>20s}") for name, (s, oa, ua) in RESULT: print(f"{name:<32s} {oa:14d} {ua:20d}") print() print("a tunnel's length in the underlay") print(f"{'tunnel':>6s} {'converged':>11s} {'after break':>14s} {'with old table':>15s}") for x, y in OVERLAY: _, a0 = forward(x, y, DOWN, LINKS) k1, a1 = forward(x, y, DOWN_NEW, BROKEN) k2, a2 = forward(x, y, DOWN, BROKEN) print(f"{x + '-' + y:>6s} {a0:11d} {a1:14d} " f"{('black hole' if k2 != 'reached' else str(a2)):>15s}") ``` ``` regime reached overlay loop tunnel black hole both layers converged 40 0 0 underlay broke, converged 40 0 0 underlay broke, table stale 19 0 21 tunnel dropped, two ends heard 28 12 0 tunnel dropped, everybody heard 40 0 0 both layers stale 17 3 20 regime overlay hops underlay hops both layers converged 74 188 underlay broke, converged 74 211 underlay broke, table stale 40 124 tunnel dropped, two ends heard 77 205 tunnel dropped, everybody heard 97 264 both layers stale 41 134 a tunnel's length in the underlay tunnel converged after break with old table a-c 2 2 2 a-d 3 3 3 a-e 3 4 black hole b-d 2 2 2 b-g 2 3 black hole c-f 2 3 black hole d-h 4 4 4 e-g 2 2 2 f-h 2 2 2 ``` #### The Overlay Never Sees the Break The first two regimes measure the chord breaking. All forty of the forty packets arrive in both regimes, and **overlay hops are 74 in both**. **Not a single row** of the overlay's table changed; as far as the overlay is concerned, nothing happened. Underlay hops climb from **188 to 211**. The third table says where the twenty-three extra hops come from: the `a-e` tunnel goes from three hops to four, the `b-g` and `c-f` tunnels go from two hops each to three each. These were the tunnels using the chord; once the chord was gone, the underlay built them from the other side of the ring. This is the overlay's most advertised feature, and the measurement confirms it: **as long as the underlay repairs itself, the overlay never sees the break at all.** But the measurement gives the cost too. An observer watching the overlay **cannot see** the twenty-three extra hops, because nothing has changed in its own counter. The layer hides the fault, and hides the cost along with it. #### Correct Table, Dead Packet The third regime measures the same break with the underlay **not yet converged**. The overlay's table still has not changed, and it is still correct; only **19** of the forty packets arrive, and **21** fall into a tunnel black hole. The third table's last column names three tunnels: `a-e`, `b-g`, and `c-f` cannot be delivered with the old underlay table. The overlay still counts these three links as standing and sends packets to them. This is the first form of two-layer disagreement: **the table above is flawless, and the packet still dies.** A check that looks only at the overlay's own metrics reports no fault at all — the overlay's neighborhoods are complete, its paths are valid, its hop count is even lower than expected (**40**, because a dying packet stops spending hops). The fault is a layer below, and the layer above cannot see it. #### Underlay Flawless, Overlay in a Loop The fourth regime turns the disagreement around. In this regime, the underlay's table is the oracle itself: **there is not a single wrong decision in the underlay**, and all nine of the nine tunnels are deliverable. The only thing that changes is in the overlay — the `a-c` tunnel has dropped, and only `a` and `c` have heard about it. The result: **28** of the forty packets arrive, **12** enter an **overlay loop**. Black hole is **zero**. The fifth regime measures the same tunnel drop when everybody has heard about it: **40 arrive**, overlay hops climb to 97, underlay hops to 264. The course's second claim gets paid off again here, one layer up. **Partial information produces a fault more expensive than total ignorance:** when everybody has heard, forty packets arrive; when only the two ends have heard, twelve packets circle in the network. And the third claim gets paid off a second time too: not a single one of the twelve packets was put into a loop by a single table. The loop is **a disagreement between two overlay tables** — `a` knows the tunnel has dropped, `d` does not, and sends the packet back. The sharpest point is this: **the underlay cannot see this loop.** What the underlay sees is tunnel deliveries, each valid on its own. The tunnel from `a` to `d` was delivered, the tunnel from `d` to `a` was delivered too; both are correct. The loop is visible only to an eye that puts the two deliveries **side by side**, and the underlay has no such eye. #### Both Layers at Once The sixth regime stacks the two disagreements on top of each other: the `a-c` tunnel has dropped and only the two ends have heard, and **at the same time** the chord has broken and the underlay's tables have gone stale. **17** of the forty packets arrive — fewer than either the underlay fault alone (**19**) or the overlay fault alone (**28**). The real observation is in how the fates are distributed. Overlay loop drops from **12** to **3**, tunnel black hole from **21** to **20**. Most of the packets that would have entered a loop instead fall into a tunnel black hole and die at the very first turn: **the fault below hides the fault above.** An eye watching the overlay sees the loop count drop and might mistake it for an improvement. The hop counts point the same way — overlay from **77** to **41**, underlay from **205** to **134**. The network's worst state is the state in which every counter looks the calmest. #### Two Counters, Two Diagnoses The counters' separateness separates the diagnosis too. In the regime that enters a loop, the overlay spends **77 hops**, the underlay **205 hops**: every hop in the overlay is worth more than two and a half hops in the underlay on average, and a loop in the overlay layer grows by this factor in the underlay. Two observers see two separate things. The counter watching the overlay sees the loop **as a loop**: packets are circling, the hop limit is burning through. The counter watching the underlay sees only **a rise in load**: there are more packets on the links than expected, and no delivery is failing. The course's shared finding that "a loop looks like congestion" is, in a two-layer network, a finding that changes depending on **which layer it is viewed from**. This is not a reason not to use overlays; it is a reason overlays cannot be used without watching both layers at once. In a single-layer network, the table and the link set stand in the same place, and a fault shows up in both at once. In **three** of the six overlay regimes measured, a packet dies, and each of the three has a different symptom: one only a black hole, one only a loop, one both at once. #### Summary - An overlay network is a logical topology built with tunnels; an overlay link declares a neighborhood, not a cable. The real set of links beneath it is called the **underlay**, and even though the two layers' tables sit on the same device, neither reads the other. - When the underlay repairs itself, the overlay **never sees** the break at all: overlay hops stay at **74**, underlay hops climb from **188 to 211**. The layer hides the fault, and hides the cost along with it. - If the overlay works with its correct table before the underlay converges, **21 packets** fall into a tunnel black hole; the `a-e`, `b-g`, and `c-f` tunnels that used the chord cannot be delivered. The table above is flawless, and the packet still dies. - With not a single wrong decision in the underlay, the overlay tables' partial information puts **12 packets into a loop**; when everybody has heard, all forty of the forty packets arrive. The loop is **a disagreement between two overlay tables**, and the underlay cannot see it. - 77 hops in the overlay are 205 hops in the underlay; the counter watching the overlay sees a loop, the counter watching the underlay sees only a rise in load. - When both layers go stale at once, reached packets drop to **17**, but loop drops to **3**: the black hole below hides the loop above, and the worst state looks the calmest in the counters. #### Next Step Up to this point, the topology was **given** in every measurement. Eight nodes, nine links, and a chord cutting the ring were laid down from the start; what was measured was always the response given to it — which table converges in how many rounds, how much a given policy lengthens the path, which layer sees the break. The topology itself was never questioned. But the topology is a choice too: which node connects to which, how many backup paths are left, how many nodes' tables a break will change are all decided when the network is laid out. The next topic measures this choice and shows that the choice directly touches the convergence round. ## Topology Design Layered enterprise designs, spine-leaf for east-west traffic, gateway redundancy and failover, and an address and naming plan that scales as the network grows. ### Layered Design Source: https://academia.sh/en/courses/switching-and-routing/layered-design The number of layers determines hop count and convergence rounds together: on the same nine access switches, a flat chain spends 121 hops, a two-layer design 80, and a three-layer design 138, and the link-state family converges in 7, 1, and 3 rounds respectively. Up to this point, the topology was **given**. Eight nodes, nine links, a chord cutting across the ring — these were fixed by the setup, and what was measured was the response to the topology: which family converges in how many rounds, what fate partial information produces, how an overlay's table conflicts with the one beneath it. The topology itself is also a choice. The choice determines convergence rounds, hop count, and how many rows a failure changes, all together. This lesson's question is: when the same access switches are wired into three separate arrangements, how does what the packet pays change? #### The Decision Each Layer Carries **Layered design** separates devices by role and gives each role a single decision to make. The **access layer** is where hosts connect. Its decision is local: does the frame go to one of this switch's ports, or upward? The **distribution layer** aggregates an entire building, floor, or segment; its decision sits at the block's boundary, and everything leaving the block passes through it. The **core layer** only connects blocks to one another; no host attaches to it, and its decision is the narrowest of the three. In a two-layer arrangement, distribution and core merge into the same device; this merger is called a **collapsed core** arrangement. A layerless arrangement, by contrast, is not a choice but the absence of one: each new switch plugs into the previous one, and the network grows as a chain. Three arrangements are built for the measurement. All three have **nine access switches**, and hosts connect only to them; the only thing that changes is the arrangement among them. ```text # taught transcript, not run flat chain — 1 layer access: e1 - e2 - e3 - e4 - e5 - e6 - e7 - e8 - e9 collapsed core — 2 layers core: c1 - c2 access: e1..e9, each to both c1 and c2 three-layer — 3 layers core: c1 - c2 distribution: d1 d2 | d3 d4 | d5 d6, each to both c1 and c2 access: e1 e2 e3 -> d1 d2 e4 e5 e6 -> d3 d4 e7 e8 e9 -> d5 d6 ``` #### What the Layer Promises and Does Not The rationale for layered design is often summarized as "faster," and that summary is wrong. Adding a layer **lengthens** the path: each new layer means two more devices that every inter-block packet must cross. What layering does promise is something else: a change inside one block stays inside that block. The promise is not in the **hop count**, it is in the **table and how a failure propagates**. The measurement counts both sides of the promise. The assumptions the measurement rests on: - **TD1** — All three designs share the same nine access switches, and the forty packets are generated only among these nine. What is compared is not host count but the arrangement among them. - **TD2** — The oracle is known because we build the topology ourselves, and it is the first hop of the shortest path to every destination for every node. Where paths tie in length, the order of node names decides. - **TD3** — Every link costs one; what is measured is **hops**, not bandwidth. - **TD4** — The convergence counter runs from a **cold start**: at round zero, each node knows only its own links. In the distance vector family, a round is learning a neighbor's distance array; in the link-state family, it is learning the links a neighbor knows. - **TD5** — The link that is cut is not chosen by hand: the **busiest link** carrying the shortest paths of the forty packets is found by counting. The same criterion is applied in all three designs. - **TD6** — The hop limit is 12; a packet that burns through this limit is counted as a loop. - **TD7** — A table row is a single record a node holds for one destination; row count in all three designs grows together with node count. - **TD8** — In a set of forty packets, the smallest measurable difference is 1/40 = 0.025; no smaller difference is claimed. #### The Measurement ```python """Layered design: the effect of layer count on hops and convergence rounds. Part 1 - three converged designs: hops, table rows, longest path. Part 2 - convergence rounds from a cold start. Part 3 - the packet's fate when the busiest link fails, and reconvergence. """ SEED = 20260810 HOP_LIMIT = 12 ACCESS = [f"e{i}" for i in range(1, 10)] BLOCK = {"d1": ACCESS[0:3], "d2": ACCESS[0:3], "d3": ACCESS[3:6], "d4": ACCESS[3:6], "d5": ACCESS[6:9], "d6": ACCESS[6:9]} DESIGN = { "flat chain": (ACCESS, [(f"e{i}", f"e{i + 1}") for i in range(1, 9)]), "two-layer": (ACCESS + ["c1", "c2"], [(e, c) for e in ACCESS for c in ("c1", "c2")] + [("c1", "c2")]), "three-layer": (ACCESS + sorted(BLOCK) + ["c1", "c2"], [(e, d) for d, es in BLOCK.items() for e in es] + [(d, c) for d in sorted(BLOCK) for c in ("c1", "c2")] + [("c1", "c2")]), } def make_rng(seed): state = seed % 2147483646 + 1 def rand(n): nonlocal state state = (state * 48271) % 2147483647 return state % n return rand def neighbors(nodes, 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(nodes, links): """First hop of the shortest path to every destination, for every node.""" k, table = neighbors(nodes, links), {} for source in nodes: prev, front, seen = {}, [source], {source} while front: new = [] for u in front: for v in sorted(k[u]): if v not in seen: seen.add(v) prev[v] = u new.append(v) front = new for dest in nodes: if dest == source or dest not in prev: continue step = dest while prev[step] != source: step = prev[step] table[(source, dest)] = step return table def forward(source, dest, tables, nodes, links): k, u, crossed, hops = neighbors(nodes, links), source, [], 0 while u != dest: if hops >= HOP_LIMIT: return "loop", hops nxt = tables.get((u, dest)) if nxt is None or nxt not in k[u]: return "black hole", hops if (u, nxt) in crossed: return "loop", hops crossed.append((u, nxt)) u, hops = nxt, hops + 1 return "reached", hops def pairs(count=40, seed=SEED): rand, out = make_rng(seed), [] while len(out) < count: x, y = ACCESS[rand(9)], ACCESS[rand(9)] if x != y: out.append((x, y)) return out def measure(tables, nodes, links): counts, hops, longest = {"reached": 0, "loop": 0, "black hole": 0}, 0, 0 for x, y in pairs(): fate, a = forward(x, y, tables, nodes, links) counts[fate] += 1 hops += a if fate == "reached": longest = max(longest, a) return counts, hops, longest def distance_vector(nodes, links, rounds): """Each round a node learns only its neighbor's distance array.""" k = neighbors(nodes, links) dist = {(u, h): (0 if u == h else 99) for u in nodes for h in nodes} first = {} for _ in range(rounds): new_dist, new_first = dict(dist), dict(first) for u in nodes: for v in sorted(k[u]): for h in nodes: if dist[(v, h)] + 1 < new_dist[(u, h)]: new_dist[(u, h)] = dist[(v, h)] + 1 new_first[(u, h)] = v dist, first = new_dist, new_first return first def link_state(nodes, links, rounds): """Over rounds the topology is carried; a node with the full topology computes correctly.""" k = neighbors(nodes, links) known = {u: {tuple(sorted((u, v))) for v in k[u]} for u in nodes} for _ in range(rounds): new = {u: set(known[u]) for u in nodes} for u in nodes: for v in k[u]: new[u] |= known[v] known = new tables = {} for u in nodes: seen = sorted({x for b in known[u] for x in b}) for (x, h), step in oracle(seen, sorted(known[u])).items(): if x == u: tables[(u, h)] = step return tables def busiest_link(nodes, links): t, count = oracle(nodes, links), {} for x, y in pairs(): u = x while u != y: v = t[(u, y)] count[tuple(sorted((u, v)))] = count.get(tuple(sorted((u, v))), 0) + 1 u = v return max(count, key=count.get) print(f"{'design':<14s} {'layers':>6s} {'nodes':>5s} {'links':>5s} " f"{'table rows':>10s} {'reached':>7s} {'hops':>5s} {'longest':>7s}") for i, (name, (D, B)) in enumerate(DESIGN.items()): t = oracle(D, B) s, a, u = measure(t, D, B) print(f"{name:<14s} {i + 1:6d} {len(D):5d} {len(B):5d} {len(t):10d} " f"{s['reached']:7d} {a:5d} {u:7d}") print() print(f"{'round':>5s}" + "".join(f"{name:>17s}" for name in DESIGN)) print(f"{'':>5s}" + f"{'dv ls':>17s}" * 3) for rnd in range(0, 9): row = f"{rnd:5d}" for name, (D, B) in DESIGN.items(): dv = measure(distance_vector(D, B, rnd), D, B)[0]["reached"] ls = measure(link_state(D, B, rnd), D, B)[0]["reached"] row += f"{dv:12d}{ls:5d}" print(row) print() print(f"{'design':<14s} {'cut':>9s} {'at failure':>18s} " f"{'converged':>18s} {'dv/ls rounds':>12s} {'rows changed':>13s}") print(f"{'':<14s} {'':>9s} {'reached black hole':>18s} {'reached black hole':>18s}") for name, (D, B) in DESIGN.items(): cut = busiest_link(D, B) remaining = [b for b in B if tuple(sorted(b)) != cut] old, new = oracle(D, B), oracle(D, remaining) s0 = measure(old, D, remaining)[0] s1 = measure(new, D, remaining)[0] round_ls = next(t for t in range(12) if measure(link_state(D, remaining, t), D, remaining)[0] == s1) round_dv = next(t for t in range(12) if measure(distance_vector(D, remaining, t), D, remaining)[0] == s1) changed = sum(1 for a in old if a in new and old[a] != new[a]) print(f"{name:<14s} {cut[0] + '-' + cut[1]:>9s} {s0['reached']:11d}" f"{s0['black hole']:7d} {s1['reached']:11d}{s1['black hole']:7d} " f"{f'{round_dv}/{round_ls}':>12s} {f'{changed}/{len(old)}':>13s}") ``` ``` design layers nodes links table rows reached hops longest flat chain 1 9 8 72 40 121 8 two-layer 2 11 19 110 40 80 2 three-layer 3 17 31 272 40 138 4 round flat chain two-layer three-layer dv ls dv ls dv ls 0 0 13 0 0 0 0 1 13 22 0 40 0 11 2 22 26 40 40 11 11 3 26 29 40 40 11 40 4 29 34 40 40 40 40 5 34 37 40 40 40 40 6 37 38 40 40 40 40 7 38 40 40 40 40 40 8 40 40 40 40 40 40 design cut at failure converged dv/ls rounds rows changed reached black hole reached black hole flat chain e5-e6 19 21 19 21 3/2 0/72 two-layer c1-e7 26 14 40 0 2/1 18/110 three-layer c1-d3 20 20 40 0 4/3 24/272 ``` #### Hop Count Does Not Grow With Layers The top table directly shows what the layer does not promise. The **two-layer** design carries the forty packets in **80** hops, and the longest path is **2**: every packet goes up and comes back down, and that is all. The **three-layer** design spends **138** hops on the same forty packets, and the longest path climbs to **4**. The third layer adds **58 hops** on top of the two-layer design. What is surprising is the top row: the **flat chain finishes in 121 hops** and spends **fewer** hops than the three-layer design. The reason is in the distribution: in a chain, a packet between neighboring switches arrives in a single hop, and thirteen of the forty packets do exactly that. The chain's longest path is **8** hops, twice the three-layer design's worst case; what keeps the total hop count low is not the worst case but the cheap nearby neighbors. The rule that follows is this: **layer count does not improve hop count.** The two-layer design's 80 is a lower bound, because there are already at least two hops between any two access switches. A third layer can only make this number grow. #### Convergence Rounds Shrink With Layers The middle table follows the same three designs from a cold start, and here the ranking reverses. In the **flat chain**, the link-state family delivers all forty of the forty packets by **round 7**, the distance vector family by **round 8**. Information crawls neighbor to neighbor along the chain: for e1 to learn about e9, the news has to cross eight links. In the **two-layer** design, the link-state family finishes at **round 1** — an access switch's neighbor is the core, and the core knows everyone, so a single round is enough to carry the whole topology. The **three-layer** design converges at **round 3**: the news has to travel from access to distribution, from distribution to core, and back down again. The round-zero row deserves its own reading. In the flat chain, the link-state family delivers **13** packets at the very first instant, because those thirteen packets' destinations are already neighbors and a node knows its own links from the start. In the two-layer and three-layer designs, the same cell is **0**: in a layered design, no access switch is another one's neighbor. This is the first cost of layering — at round zero, no packet arrives. The one-round gap between the two families persists across all three designs: the link-state family finishes **one round ahead** of the distance vector family in every design. #### What the Failure Costs The bottom table cuts the busiest link, and the response of the three designs is entirely different from one another. In the **flat chain**, the link cut is `e5-e6`, and the outcome is permanent: **21 packets fall into a black hole**, and the count stays at **21** even after the tables converge. There is no alternate path in a chain; the failure splits the network into two pieces, and computing a correct table does nothing. The changed-row count of **0/72** says exactly this: there is no new path to compute. This is where the chain's cheap hop count ends. In the **two-layer** design, the link cut is `c1-e7`. At the moment of failure, with the old tables, **26 packets reach, 14 fall into a black hole**; once the tables converge, this returns to **40/40** and the total hop count is again **80** — nothing is lost, because e7 has a second path through c2. The link-state family repairs this in **1 round**. The cost is that **18 of 110 rows** change. In the **three-layer** design, the link cut is `c1-d3`; at the moment of failure, **20 reach, 20 fall into a black hole**, convergence takes **3 rounds**, and the result is again **40/40**. The real difference is in the rightmost column: the changed rows are **24 of 272**, that is **9 percent**. In the two-layer design, the same ratio is **18 of 110**, that is **16 percent**. This is what the third layer buys: a failure moves **fewer rows** in a table that holds more rows, because the change stops at the block boundary. The trade-off is therefore explicit. Adding a layer adds hops, convergence rounds, and table rows; the one thing it gives in return is that **the change stays narrow**. At nine access switches, this trade-off does not justify a third layer; it does when the core has ninety-nine neighbors instead of nine. #### Summary - Layered design separates devices by role: access aggregates hosts, distribution aggregates a block, and core only connects blocks; in a two-layer design, the last two roles merge into the same device. - On the same nine access switches, a flat chain spends **121** hops, a two-layer design **80**, and a three-layer design **138**; adding a layer does **not improve** hop count. - Convergence rounds work in the opposite direction: the link-state family converges in **7** rounds in the chain, **1** in the two-layer design, and **3** in the three-layer design, and in every design it is one round ahead of the distance vector family. - In a layered design, no packet arrives at round zero; in the chain, **13** packets arrive, because their destinations are already neighbors. - When the busiest link fails, the chain **permanently** loses **21 packets**; the two-layer and three-layer designs return to **40/40**, but the changed-row ratios are **18/110** and **24/272** respectively — what the third layer buys is a change that stays narrow. #### Next Step All three designs shared an implicit assumption: a packet climbs up from access, turns somewhere, and comes back down. The forty packets' source and destination were both at access switches, but the arrangement was built around climbing up. In the three-layer design, the cost of this showed — every inter-block packet spent four hops, while intra-block ones spent two. The hop count between the same two endpoints depended on which block they fell into. The next lesson takes up the case where most traffic flows **sideways** rather than up: in an arrangement where every leaf connects to every spine, the hop count between two leaves stays constant, and what this constancy costs in table rows is counted separately. ### Spine–Leaf Design Source: https://academia.sh/en/courses/switching-and-routing/spine-leaf-design In a design where every leaf connects to every spine, the leaf-to-leaf hop count stays constant at 2, independent of spine count, leaf pair, and break; the cost of that constancy is table rows, and with four spines the single-path row count climbs from 90 to 156 and the multi-path row count from 90 to 468. The previous lesson measured three designs on the same nine access switches and left an inconsistency in the three-layer design: the hop count between the same two endpoints depended on which block they fell into. A packet inside a block spent two hops, a packet between blocks spent four. The layered design's implicit assumption was that most traffic flows upward — leaving the host and crossing out of the network, north-south traffic. When that assumption holds, the four inter-block hops are rarely paid. The assumption does not always hold. If what a host talks to is not outside the network but another host on the same network, traffic flows sideways rather than upward. This lesson's question is: when most traffic runs leaf to leaf, which design makes the hop count independent of where the endpoints sit, and what does that cost? #### East-West Traffic Traffic between two endpoints on the network that never leaves the network is called **east-west traffic**. Its counterpart is **north-south traffic**: flow that leaves the host, crosses the core, and exits the network. Layered design is built for north-south traffic. A block's distribution pair collects all of the block's traffic and hands it to the core; the core carries it outward. In this design, east-west traffic is handled as an exception: every packet between two blocks climbs to its own distribution pair, rises to the core, descends to the other distribution pair, and reaches the leaf from there. The previous lesson's measurement counted this as four hops. The problem is not the hop count alone. When an intra-block packet spends two hops and an inter-block packet spends four, the cost between two endpoints depends on where they plug in. Moving a host to a different leaf changes its latency without changing who it talks to. #### Spine and Leaf **Spine–leaf** design removes this dependency structurally. There are two kinds of device. The **leaf** is the switch hosts connect to. The **spine** only connects leaves, and no host attaches to it. There is a single rule: **every leaf connects to every spine, spines do not connect to each other, and leaves do not connect to each other.** This rule has a direct consequence: every path from one leaf to another is exactly **two** hops — leaf, spine, leaf. No path of any other length exists, because no other link exists. ```text # taught transcript, not run spine–leaf, 3 spines spine: o1 o2 o3 leaf: y1 y2 y3 y4 y5 y6 y7 y8 y9 rule: every y connects to every o (9 x 3 = 27 links) no o-o link, no y-y link paths for y3 -> y8: y3-o1-y8 y3-o2-y8 y3-o3-y8 all 2 hops, all equal cost ``` Because all three paths are equal in length, the leaf must choose one. The choice is made by the **equal-cost multipath** rule: the leaf keeps every equal-cost next hop toward a destination in its table and picks one for each flow. Every packet of the same flow gets the same choice. The rule that a flow is never split was established in the Link Aggregation lesson; there, the choice was among the legs of a link bundle, and here the same rule operates over a path. The assumptions the measurement rests on: - **TD9** — The nine leaves (`y1`-`y9`) are the previous lesson's nine access switches; the forty pairs are generated only among these. What is measured is therefore entirely east-west traffic. - **TD10** — Spine count is tried at 1, 2, 3, and 4; leaf count is fixed in every trial. As a comparison row, the previous lesson's three-layer design is rebuilt with the same nine leaves. - **TD11** — The oracle gives all of the first hops of the shortest path for every destination; equal-cost paths are not reduced to one. - **TD12** — Flow selection is made by the remainder of the flow number divided by the number of equal-cost candidates. In a real deployment, the choice is made by hashing header fields; what matters for the measurement is that the choice is constant per flow and spread evenly across the paths. - **TD13** — Every link costs one; what is measured is hops. - **TD14** — The "single-path row" count counts one record per destination, the "multi-path row" count counts a separate record for each equal-cost next hop. The two are two accountings of the same table. - **TD15** — The break is applied the same way in every design: a leaf's link to the first spine is cut (`y7-o1`). In the three-layer design, the counterpart is the same leaf's distribution link (`d5-y7`). - **TD16** — In a set of forty packets, the smallest measurable difference is 1/40 = 0.025; the hop limit is 12. #### The Measurement ```python """Spine-leaf design: the constancy of the leaf-to-leaf hop and its cost in table rows. Part 1 - hops, links, and table rows as spine count changes. Part 2 - the moment of failure and the converged state when a leaf-spine link breaks. """ SEED = 20260810 HOP_LIMIT = 12 LEAF = [f"y{i}" for i in range(1, 10)] BLOCK = {"d1": LEAF[0:3], "d2": LEAF[0:3], "d3": LEAF[3:6], "d4": LEAF[3:6], "d5": LEAF[6:9], "d6": LEAF[6:9]} THREE_LAYER = (LEAF + sorted(BLOCK) + ["c1", "c2"], [(y, d) for d, ys in BLOCK.items() for y in ys] + [(d, c) for d in sorted(BLOCK) for c in ("c1", "c2")] + [("c1", "c2")]) def make_rng(seed): state = seed % 2147483646 + 1 def rand(n): nonlocal state state = (state * 48271) % 2147483647 return state % n return rand def neighbors(nodes, links): k = {u: set() for u in nodes} for x, y in links: k[x].add(y) k[y].add(x) return k def distances(nodes, links): k, dist = neighbors(nodes, links), {} for source in nodes: seen, front, d = {source}, [source], 0 dist[(source, source)] = 0 while front: d, new = d + 1, [] for u in front: for v in sorted(k[u]): if v not in seen: seen.add(v) dist[(source, v)] = d new.append(v) front = new return dist def oracle(nodes, links): """All (equal-cost) first hops of the shortest path, for every destination.""" k, dist, table = neighbors(nodes, links), distances(nodes, links), {} for u in nodes: for h in nodes: if u == h or (u, h) not in dist: continue table[(u, h)] = [v for v in sorted(k[u]) if dist.get((v, h), 99) == dist[(u, h)] - 1] return table def forward(flow, source, dest, tables, nodes, links): """One of the equal-cost paths is chosen by the flow number.""" k, u, crossed, hops = neighbors(nodes, links), source, [], 0 while u != dest: if hops >= HOP_LIMIT: return "loop", hops candidates = [v for v in tables.get((u, dest), []) if v in k[u]] if not candidates: return "black hole", hops nxt = candidates[flow % len(candidates)] if (u, nxt) in crossed: return "loop", hops crossed.append((u, nxt)) u, hops = nxt, hops + 1 return "reached", hops def pairs(count=40, seed=SEED): rand, out = make_rng(seed), [] while len(out) < count: x, y = LEAF[rand(9)], LEAF[rand(9)] if x != y: out.append((x, y)) return out def measure(tables, nodes, links): counts, hops, lengths = {"reached": 0, "loop": 0, "black hole": 0}, 0, [] for i, (x, y) in enumerate(pairs()): fate, a = forward(i, x, y, tables, nodes, links) counts[fate] += 1 hops += a if fate == "reached": lengths.append(a) return counts, hops, (min(lengths), max(lengths)) if lengths else (0, 0) def max_load(tables, nodes, links): """How many of the forty flows use each link; the busiest link's count.""" k, count = neighbors(nodes, links), {} for i, (x, y) in enumerate(pairs()): u, hops = x, 0 while u != y and hops < HOP_LIMIT: candidates = [v for v in tables.get((u, y), []) if v in k[u]] if not candidates: break v = candidates[i % len(candidates)] link = tuple(sorted((u, v))) count[link] = count.get(link, 0) + 1 u, hops = v, hops + 1 return max(count.values()) def spine_leaf(spines): s = [f"o{i}" for i in range(1, spines + 1)] return LEAF + s, [(y, sp) for y in LEAF for sp in s] DESIGN = {f"spine–leaf, {s} spine{'s' if s != 1 else ''}": spine_leaf(s) for s in (1, 2, 3, 4)} DESIGN["three-layer (lesson 01)"] = THREE_LAYER print(f"{'design':<26s} {'nodes':>5s} {'links':>5s} {'reached':>7s} {'hops':>5s} " f"{'range':>6s} {'busiest link':>12s} {'single-path':>11s} {'multi-path':>10s}") for name, (D, B) in DESIGN.items(): t = oracle(D, B) s, a, (mn, mx) = measure(t, D, B) print(f"{name:<26s} {len(D):5d} {len(B):5d} {s['reached']:7d} {a:5d} " f"{f'{mn}–{mx}':>6s} {max_load(t, D, B):12d} {len(t):11d} " f"{sum(len(v) for v in t.values()):10d}") print() print(f"{'design':<26s} {'cut':>7s} {'at failure':>18s} {'converged':>18s} " f"{'hops':>5s}") print(f"{'':<26s} {'':>7s} {'reached black hole':>18s} {'reached black hole':>18s}") for name, (D, B) in DESIGN.items(): cut = ("y7", "o1") if "spine" in name else ("d5", "y7") remaining = [b for b in B if tuple(sorted(b)) != tuple(sorted(cut))] old, new = oracle(D, B), oracle(D, remaining) s0 = measure(old, D, remaining)[0] s1, a1, _ = measure(new, D, remaining) print(f"{name:<26s} {cut[0] + '–' + cut[1]:>7s} {s0['reached']:11d}" f"{s0['black hole']:7d} {s1['reached']:11d}{s1['black hole']:7d} {a1:5d}") ``` ``` design nodes links reached hops range busiest link single-path multi-path spine–leaf, 1 spine 10 9 40 80 2–2 14 90 90 spine–leaf, 2 spines 11 18 40 80 2–2 9 110 198 spine–leaf, 3 spines 12 27 40 80 2–2 6 132 324 spine–leaf, 4 spines 13 36 40 80 2–2 5 156 468 three-layer (lesson 01) 17 31 40 138 2–4 11 272 500 design cut at failure converged hops reached black hole reached black hole spine–leaf, 1 spine y7–o1 26 14 26 14 52 spine–leaf, 2 spines y7–o1 38 2 40 0 80 spine–leaf, 3 spines y7–o1 38 2 40 0 80 spine–leaf, 4 spines y7–o1 39 1 40 0 80 three-layer (lesson 01) d5–y7 38 2 40 0 138 ``` #### The Hop Is Constant The `range` column reads **2–2** in all four spine–leaf rows: the shortest and the longest of the forty packets are both two hops. Total hops are **80** in all four designs, and this never changes with spine count. This constancy holds in three separate dimensions, and all three can be read from the table. **Independent of the leaf pair:** the forty pairs were generated among nine leaves, and none of them found a path longer than two hops. **Independent of spine count:** going from one spine to four, link count rose from nine to thirty-six, and the hop count stayed the same. **Independent of the break:** in the bottom table, after `y7–o1` is cut, the converged hop total is again **80**. The comparison row shows the difference. The three-layer design carries the same forty packets in **138** hops, with a range of **2–4**. The entire 58-hop gap comes from inter-block traffic climbing to the core. For east-west traffic, the layered design is not only slower, it is **unpredictable**: its cost is determined by which block the endpoints fall into. The source of this constancy is not an optimization but an absence. Because spines do not connect to each other and leaves do not connect to each other, a three-hop path cannot be constructed. The design does not select the short path; it does not let the long one exist. #### The Cost of Constancy Is Table Rows The two right-hand columns show the cost, and the two must be read separately. **The single-path row count** counts one record per destination: **90** with one spine, **110** with two, **132** with three, **156** with four. The increase comes from adding nodes: every new spine is itself a destination, and it adds one row to everyone's table. **The multi-path row count** is the real cost. A leaf must keep every equal-cost next hop toward a destination; with two spines, every remote destination has two records, with four spines, four. The count climbs from **90** to **468** — as spine count quadruples, rows grow **5.2 times**. And the hop count never changes. The rule is this: **in a spine–leaf design, scale is paid in rows, not hops.** In layered design, growth lengthens the hop count and caps the table at the block boundary; in spine–leaf, growth never changes the hop count and widens every leaf's table. The two designs charge the same resource to two different accounts. The comparison row favors spine–leaf here: the three-layer design holds **272** single-path and **500** multi-path rows, the two-spine design **110** and **198**. The three-layer design's excess comes from the intermediate layer's own nodes — six distribution and two core devices, all present in each other's tables. #### What Spine Count Changes If the hop count never changes, why build more than two spines? The answer is in the `busiest link` column. The link most loaded by the forty flows carries **14** flows with one spine; **9** with two, **6** with three, **5** with four. Adding a spine does not reduce latency, it reduces **density** — flows spread across parallel paths. The second answer is in the bottom table. **A single-spine design is not a design:** when `y7–o1` is cut, **14** packets fall into a black hole, and after the tables converge, **14** remain, because `y7` has no other path. From two spines onward, the same break leaves **0** black holes after convergence; the **2** packets remaining at the moment of failure are the flows that had chosen `o1` at that instant. With four spines, this number drops to **1**: the fraction of flows using the cut link shrinks with spine count. A caveat is necessary. The measurement counts every link's cost as one and never accounts for bandwidth. In a real deployment, a leaf's total downward-facing capacity can exceed its total upward-facing capacity; in that case, the `busiest link` column does not show flow count but where flows fail to fit. This lesson does not do that accounting; it only counts how many links a flow spreads across. #### Summary - East-west traffic is traffic that stays inside the network; layered design is built for north-south traffic and forces east-west packets to climb to the core. - In a spine–leaf design, every leaf connects to every spine, and spines and leaves do not connect among themselves; every leaf-to-leaf path is therefore **2** hops. - The constancy holds in three dimensions — independent of leaf pair, spine count, and break — for a total of **80** hops; the three-layer design gives **138** hops and a **2–4** range for the same forty packets. - The cost is table rows: going from one spine to four, the single-path row count climbs from **90** to **156**, and the multi-path row count from **90** to **468**. - Adding a spine reduces density, not hops — the busiest link drops from **14** flows to **5**; in a single-spine design, a break permanently loses **14** packets, while from two spines onward the loss converges to **0**. #### Next Step In a spine–leaf design, redundancy is structural: no single device owns a path, and the loss of a spine only changes how flows are distributed. But a host attached to a leaf sends its outbound packet not to a path but to an address — the default gateway's address. That address sits on a single device at any moment, and when that device fails, redundancy stops being structural and turns into a **failover**: the address's owner must change, and everyone must hear about the change. The next lesson counts the packet's fate during the failover window, and measures a second time that partial information produces a loop. ### Redundancy and Failover Source: https://academia.sh/en/courses/switching-and-routing/redundancy-and-failover The failover window in gateway redundancy is measured: when the upstream link breaks and nobody has heard, all forty flows fall into a black hole one hop later; when the gateway fails over, the black hole clears but the peer link carries forty crossings; when two gateways each believe themselves active, all forty flows enter a loop and the peer link carries eighty crossings. In a spine–leaf design, redundancy was structural: no device was the sole owner of a path, and the loss of a spine only changed how flows were distributed. On the host side, this is not the case. A host sends its outbound packet not to a path but to an address — the default gateway's address. The address is singular, and at any moment it sits on exactly one device. This singularity takes redundancy out of the structural category. When the device fails, a second device must take over the address, and everyone must hear about the takeover. This lesson's question is what happens to the packet during that short interval while the hearing is still in progress. #### The Virtual Address and Two Roles **Gateway redundancy** puts two devices behind a single address. This address is called the **virtual address**; hosts know it as their default gateway and are unaware that two devices exist. One of the devices is **active**, the other is **standby**. The active one answers for the virtual address and forwards packets upward; the standby one listens silently. When the active device's periodic advertisements stop arriving, the standby waits for a period and then takes over the address. ```text # taught transcript, not run gateway pair virtual address single address, hosts' default gateway g1 priority 110 active -> answers the virtual address, forwards upward g2 priority 100 standby -> listens silently, waits for advertisements peer link g1 - g2, carries advertisements and state timing advertisement interval active side advertises once per interval dead timer standby takes over if no advertisement heard in this time failover instant standby begins answering for the virtual address leaf table (for remote networks) destination next hop u1 u2 u3 the gateway believed to currently hold the virtual address ``` Service-level failover patterns — health checks, retries, the circuit breaker — were established in the Resilience and Reliability course and are not repeated here. There, what failed over was a service instance, and what was measured was the request's fate; here, what fails over is the **gateway**, and what is measured is the packet's fate. #### What the Window Is Failover is not instantaneous. The time it takes for the dead timer to expire, for the standby to announce the address, and for switches along the path to relearn where the address is — the sum of these is called the **failover window**. During the window, devices disagree about where the virtual address is. Inside the window there are two separate questions. First: **who answers for the virtual address?** Second: **can the answering device forward the packet?** The measurement counts exactly this distinction: a gateway whose upstream link has broken keeps collecting packets for as long as it holds the address. The assumptions the measurement rests on: - **TD17** — Nine leaves (`y1`-`y9`) connect to a gateway pair (`g1`, `g2`); the pair connects to a core (`c`), and the core connects to three remote networks (`u1`, `u2`, `u3`). The forty flows have a leaf as their source and a remote network as their destination; the traffic measured is entirely north-south. - **TD18** — The failure measured is the breaking of the `g1-c` upstream link. `g1` is healthy, remains connected to the leaves, and can continue to hold the virtual address. - **TD19** — Every leaf holds a belief: whether the virtual address is on `g1` or `g2`. A leaf that has heard says `g2`; one that has not says `g1`. - **TD20** — Every gateway also holds a belief. A gateway that believes itself active forwards the packet upward; one that believes its peer active hands the packet to its peer over the peer link. - **TD21** — The oracle is known because we built the setup ourselves: after `g1-c` breaks, the only path to the remote networks is through `g2`. - **TD22** — The regimes differ only in belief; the topology does not change except for the presence of the `g1-c` link. So the difference measured is a difference in information, not in structure. - **TD23** — The "peer link" column counts how many times the forty flows cross the `g1-g2` link in total. This link is sized for control traffic; it carrying user traffic is a symptom. - **TD24** — A packet is counted as a loop when it crosses the same link a second time or burns through the hop limit (12); a packet whose next hop is no longer a neighbor is counted as a black hole. - **TD25** — The hops column counts only the hops spent; a packet that falls into a black hole has spent the hops up to where it died. - **TD26** — In a set of forty flows, the smallest measurable difference is 1/40 = 0.025. #### The Measurement ```python """Gateway redundancy: the packet's fate during the failover window. Part 1 - regimes: converged, window, upstream-link tracking, split-brain. Part 2 - the change in fate as the number of leaves that have heard grows. """ SEED = 20260810 HOP_LIMIT = 12 LEAF = [f"y{i}" for i in range(1, 10)] REMOTE = ["u1", "u2", "u3"] NODES = LEAF + ["g1", "g2", "c"] + REMOTE LINKS = ([(y, g) for y in LEAF for g in ("g1", "g2")] + [("g1", "g2"), ("g1", "c"), ("g2", "c")] + [("c", u) for u in REMOTE]) BROKEN = [b for b in LINKS if b != ("g1", "c")] def make_rng(seed): state = seed % 2147483646 + 1 def rand(n): nonlocal state state = (state * 48271) % 2147483647 return state % n return rand 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 build_tables(leaf_belief, g1_belief, g2_belief): """The next hop each node holds for the remote networks.""" t = {} for y in LEAF: for u in REMOTE: t[(y, u)] = leaf_belief[y] for g, peer, belief in (("g1", "g2", g1_belief), ("g2", "g1", g2_belief)): for u in REMOTE: t[(g, u)] = "c" if belief == g else peer for u in REMOTE: t[("c", u)] = u return t def forward(source, dest, tab, links): k, u, crossed, hops = neighbors(links), source, [], 0 while u != dest: if hops >= HOP_LIMIT: return "loop", hops nxt = tab.get((u, dest)) if nxt is None or nxt not in k[u]: return "black hole", hops if (u, nxt) in crossed: return "loop", hops crossed.append((u, nxt)) u, hops = nxt, hops + 1 return "reached", hops def pairs(count=40, seed=SEED): rand, out = make_rng(seed), [] while len(out) < count: out.append((LEAF[rand(9)], REMOTE[rand(3)])) return out def peer_crossings(tab, links): """How many of the forty flows cross the g1-g2 peer link.""" k, count = neighbors(links), 0 for x, y in pairs(): u, crossed, hops = x, [], 0 while u != y and hops < HOP_LIMIT: v = tab.get((u, y)) if v is None or v not in k[u] or (u, v) in crossed: break if {u, v} == {"g1", "g2"}: count += 1 crossed.append((u, v)) u, hops = v, hops + 1 return count def measure(tab, links): counts, hops = {"reached": 0, "loop": 0, "black hole": 0}, 0 for x, y in pairs(): fate, a = forward(x, y, tab, links) counts[fate] += 1 hops += a return counts, hops def belief(heard): return {y: ("g2" if y in heard else "g1") for y in LEAF} ALL, NONE = set(LEAF), set() REGIME = [ ("converged, g1 active", LINKS, belief(NONE), "g1", "g1"), ("upstream link broke, nobody heard", BROKEN, belief(NONE), "g1", "g1"), ("g1 failed over, no leaves heard", BROKEN, belief(NONE), "g2", "g2"), ("g1 failed over, four leaves heard", BROKEN, belief(set(LEAF[:4])), "g2", "g2"), ("g1 failed over, all heard", BROKEN, belief(ALL), "g2", "g2"), ("both think themselves active", LINKS, belief(set(LEAF[:5])), "g1", "g2"), ("both think the peer active", LINKS, belief(set(LEAF[:5])), "g2", "g1"), ] print(f"{'regime':<35s} {'reached':>7s} {'loop':>6s} {'black hole':>10s} " f"{'hops':>5s} {'peer link':>9s}") for name, links, lb, a1, a2 in REGIME: tab = build_tables(lb, a1, a2) s, a = measure(tab, links) print(f"{name:<35s} {s['reached']:7d} {s['loop']:6d} {s['black hole']:10d} " f"{a:5d} {peer_crossings(tab, links):9d}") print() print(f"{'leaves heard':>12s} {'g1 did not fail over':>32s} {'g1 failed over':>32s}") print(f"{'':>12s} {'reached black hole hops peer':>32s}" f" {'reached black hole hops peer':>32s}") for n in range(0, 10): lb, columns = belief(set(LEAF[:n])), [] for g1b in ("g1", "g2"): tab = build_tables(lb, g1b, "g2") s, a = measure(tab, BROKEN) columns.append(f"{s['reached']:9d}{s['black hole']:11d}{a:5d}" f"{peer_crossings(tab, BROKEN):5d}") print(f"{n:12d} {columns[0]} {columns[1]}") print() print(f"nodes {len(NODES)}, links {len(LINKS)}, flows 40, " f"hop limit {HOP_LIMIT}") ``` ``` regime reached loop black hole hops peer link converged, g1 active 40 0 0 120 0 upstream link broke, nobody heard 0 0 40 40 0 g1 failed over, no leaves heard 40 0 0 160 40 g1 failed over, four leaves heard 40 0 0 146 26 g1 failed over, all heard 40 0 0 120 0 both think themselves active 40 0 0 120 0 both think the peer active 0 40 0 120 80 leaves heard g1 did not fail over g1 failed over reached black hole hops peer reached black hole hops peer 0 0 40 40 0 40 0 160 40 1 4 36 48 0 40 0 156 36 2 7 33 54 0 40 0 153 33 3 9 31 58 0 40 0 151 31 4 14 26 68 0 40 0 146 26 5 18 22 76 0 40 0 142 22 6 24 16 88 0 40 0 136 16 7 29 11 98 0 40 0 131 11 8 34 6 108 0 40 0 126 6 9 40 0 120 0 40 0 120 0 nodes 15, links 24, flows 40, hop limit 12 ``` #### Answering Is Not Forwarding The second row is the lesson's most important number. When `g1-c` breaks and nobody has heard, all forty of the forty flows fall into a **black hole**. The hops spent are **40** — one hop per flow. The packet leaves the leaf, arrives at the gateway holding the virtual address, and dies there. This is the shape of the failure: the device is up, its ports work, the virtual address answers, and the host finds its default gateway reachable. Only the packet never goes up. **Who owns the virtual address and who can forward the packet are separate questions**, and the host can only ask the first one. #### Failing Over Turns the Black Hole into the Peer Link The third row closes the failure: when `g1` notices its upstream link has broken and fails over, all forty of the forty flows reach, and the black hole drops to **0**. The leaves still have not heard anything; `g1` takes their packet and hands it to its peer. The cost shows up in two columns at once. Hops rise from **120** to **160** — one extra hop per flow. And the peer link column rises from **0** to **40**: the link set up for control traffic carries all of the user traffic. The bottom table shows how this cost dissolves. As the number of leaves that have heard climbs from zero to nine, the reached count in the `g1 failed over` column stays fixed at **40**; what changes is hops falling from **160** to **120**, and peer-link crossings falling from **40** to **0**. The failover window does not lose packets; it routes them over the peer link, and as the window closes, that load lifts. The left column shows the same window without failover: as the number of leaves that have heard rises, reached flows climb linearly from **0** to **40**, and black holes fall from **40** to **0**. Even with eight leaves already having heard, **6** flows still go to the dead gateway. #### Partial Information Produces a Loop Again The last row pays off the course's second claim for a second time. When `g1` and `g2` each believe the other active, all forty of the forty flows enter a **loop**: black holes are **0**, reached is **0**. This situation is not contrived. As `g1` was going down, it received the information "my peer is now active"; `g2`, when `g1` came back, received the information "my peer has the higher priority." **Each heard something true, but at a different moment.** What is wrong is what the two say **together**. Two numbers must be compared. In the regime with no information at all (nobody heard), forty packets fall into a black hole, **40** hops are spent, and the peer link carries **0** crossings: the failure is cheap and unmistakable. In the regime with partial information, forty packets enter a loop, **120** hops are spent, and the peer link carries **80** crossings — two crossings per flow. **The loop is three times as expensive as the black hole, and it does not look like a black hole — it looks like congestion:** the administrator does not see an idle link, but a full peer link. The third claim also reads here. The leaves behind the forty flows that entered the loop were split into two groups; five sent to `g1`, four to `g2`. Which group a flow belonged to made no difference — all forty entered the loop. The leaf's table was correct, and its packet still died. **No single device can put a packet into a loop by itself; a loop is the joint product of the pair.** The sixth row carries a warning. When both believe themselves active — that is, when the virtual address answers from two devices at once — the fate table looks spotless: **40 reached, 0 loop, 0 black hole, 120 hops.** This measurement cannot see the split-brain, because the packets genuinely arrive. Where it becomes visible is in a different table: when the same address is heard from two ports, the MAC address table oscillates between two records. That table is the subject of the MAC Address Tables lesson and is not repeated here. #### The Counted Surfaces and Their Narrowing This section writes how the failures **look** and how they are **narrowed**; it does not give a procedure. The attack side belongs to the **Wireless Networks and Network Security** course. **First surface — the length of the window.** In the measurement, without failover, even with eight leaves already having heard, **6** flows still die. **Narrowing:** shortening the advertisement interval and the dead timer narrows the window; its cost is that a transient glitch can trigger an unnecessary failover. A second narrowing is precomputing the backup path: the table is not computed at the moment of failover, it is kept ready. **Second surface — a gateway that answers but cannot forward.** In the measurement, **40** black holes and one hop per flow. **Narrowing: upstream link tracking** — the gateway's priority is tied to its upstream link's state; when the link drops, priority drops and the peer takes over. The measurement gives the full gain of this narrowing: black holes fall from **40** to **0**, at the cost of the peer link carrying **40** crossings. **Third surface — two gateways each believing the other active.** In the measurement, **40** loops and **80** crossings on the peer link. **Narrowing:** ranking priorities strictly and unequally, and turning off **preemption** — if the returning device does not reclaim the address, a two-sided standoff never forms. The hop limit also terminates the loop, but the limit is a ceiling, not a fix: its cost stands in the measurement at **120** hops. **Fourth surface — the peer link being singular.** The peer link carries both the advertisements and, during failover, all of the user traffic; in the measurement, this load is **40** crossings. When the link breaks, the two devices cannot see each other, and a split-brain is born. **Narrowing:** making the peer link itself redundant and confirming the peer's health over a second path — one link's silence is not treated as proof of death. **Fifth surface — advertisements accepted without verification.** A failover advertisement is a claim; without something to verify the claim, which device takes over the gateway is left to whoever announces it. **Narrowing:** tying advertisements to authentication and accepting them only on the ports where the gateway pair actually sits. #### Summary - Gateway redundancy puts two devices behind a single virtual address; the host knows the address, not the devices, and can only ask "is the address answering?" - When the upstream link breaks and nobody has heard, all forty of the forty flows fall into a black hole one hop later: **answering is not forwarding.** - When the gateway fails over, black holes fall to **0**, but hops rise from **120** to **160** and peer-link crossings from **0** to **40**; both recede as the number of leaves that have heard grows. - When two gateways each believe the other active, all forty flows enter a loop: **120** hops and **80** crossings on the peer link — three times the no-information regime, and it looks like congestion. - With leaves split between sending to one gateway and the other, all forty still entered the loop; a loop is the pair's joint product, and when both believe themselves active, the measurement sees nothing wrong. #### Next Step The three lessons so far measured topology as a graph: nodes, links, hops, rounds. Table row count appeared as a column in every measurement, and every time it came out of the topology — **272** in the three-layer design, **468** in the four-spine design. But there is a second thing that determines row count, and it has nothing to do with topology: how destinations are **named**. On the same topology, a plan that distributes addresses by a scheme and a plan that distributes them by creation order fill the same table with a different number of rows. The next lesson counts that difference and closes the course. ### Address and Naming Plan Source: https://academia.sh/en/courses/switching-and-routing/address-and-naming-plan On the same topology, a summarizable plan holds the table at 73 rows as the subnet count climbs from nine to thirty-six, while a plan distributed by creation order climbs from 90 rows to 335 on the same path; a single moved network leaves a summary announcing an address it no longer owns, and two packets fall into a black hole. The previous three lessons measured topology as a graph, and table row count appeared as a column in every measurement: **272** in the three-layer design, **468** in the four-spine design. Every time, what determined the row count was the topology. There is a second thing that determines row count, and it has nothing to do with topology: how destinations are **named**. On the same devices, with the same links, with the same number of subnets, two different address plans fill the same table with wildly different row counts. This lesson's question is what the plan does to the table. #### The Plan's One Condition A routing table can summarize neighboring addresses in a single row. This is called **route summarization**, and it has a single condition: every address in the summarized range must be reachable through the **same next hop**. The range must be aligned, and no address heading in another direction may fall inside it. The netmask, alignment, and block-stride arithmetic were established in the Subnetting and Variable-Length Subnetting lessons and are not repeated here. What is measured is not the arithmetic itself, but its effect on **table rows**. A plan either satisfies this condition or it does not. A plan that satisfies it divides the address space the same way the topology is divided: an aligned range for each block, an aligned sub-range for each leaf within that range, and growth room in both. A plan that does not satisfy it hands out addresses from a single pool in creation order. ```text # taught transcript, not run aligned plan — 64-slot space, four blocks, three in use block 0 slots 0-15 y1: 0-3 y2: 4-7 y3: 8-11 12-15 growth room block 1 slots 16-31 block 2 slots 32-47 block 3 48-63 reserved c1's table: 0-15 -> d1 16-31 -> d3 32-47 -> d5 creation-order plan — single pool, creation order slot 0 -> y1 slot 1 -> y2 slot 2 -> y3 slot 3 -> y4 ... two consecutive slots fall into separate blocks; no summarizable range forms ``` The assumptions the measurement rests on: - **TD27** — The topology is the first lesson's three-layer design: nine leaves, three blocks, six distribution and two core nodes. The topology is the same in both plans; the only thing that changes is the plan. - **TD28** — The address space is 64 slots, and a slot represents one subnet. In the aligned plan, each block gets 16 slots and each leaf gets 4; `k` slots are used per leaf, and the rest is growth room. - **TD29** — Row count is counted as the fewest aligned prefixes that cover a node's table. An empty slot may fall inside a prefix; a slot heading in another direction may not. - **TD30** — The oracle is known because we built the topology ourselves, and it is, for every node, the first hop of the shortest path to every leaf. The packet is run with longest-prefix match. - **TD31** — The count of name zones is the fewest ranges countable without changing block when names are laid out in the plan's order. Name resolution itself is the subject of The Domain Name System lesson and is not repeated here. - **TD32** — In a set of forty packets, the smallest measurable difference is 1/40 = 0.025. #### The Measurement ```python """Address and naming plan: the plan's effect on table row count. Part 1 - aligned plan vs. creation-order plan, 1-4 subnets per leaf. Part 2 - a summary announcing an address it no longer owns. """ SEED = 20260810 SLOT = 64 LEAF = [f"y{i}" for i in range(1, 10)] BLOCK = {0: LEAF[0:3], 1: LEAF[3:6], 2: LEAF[6:9]} DISTRIBUTION = {"d1": 0, "d2": 0, "d3": 1, "d4": 1, "d5": 2, "d6": 2} NODES = LEAF + sorted(DISTRIBUTION) + ["c1", "c2"] LINKS = ([(y, d) for d, b in DISTRIBUTION.items() for y in BLOCK[b]] + [(d, c) for d in sorted(DISTRIBUTION) for c in ("c1", "c2")] + [("c1", "c2")]) def make_rng(seed): state = seed % 2147483646 + 1 def rand(n): nonlocal state state = (state * 48271) % 2147483647 return state % n return rand def neighbors(): k = {u: set() for u in NODES} for x, y in LINKS: k[x].add(y) k[y].add(x) return k def oracle(): """The first hop of the shortest path to every destination, for every node.""" k, table = neighbors(), {} for source in NODES: prev, front = {}, [source] while front: new = [] for u in front: for v in sorted(k[u]): if v != source and v not in prev: prev[v] = u new.append(v) front = new for h in prev: step = h while prev[step] != source: step = prev[step] table[(source, h)] = step return table def aligned(k): """Each block gets 16 slots, each leaf 4; k of them are filled, the rest is growth room.""" return {16 * b + 4 * j + i: y for b, leaves in BLOCK.items() for j, y in enumerate(leaves) for i in range(k)} def creation_order(k): """Subnets are handed out from a single pool, in creation order.""" return {n: LEAF[n % 9] for n in range(9 * k)} def prefixes(u, plan, start=0, size=SLOT): """The fewest aligned prefixes that cover u's table.""" inside = {("local" if y == u else ORACLE[(u, y)]) for slot, y in plan.items() if start <= slot < start + size} if len(inside) < 2: return [(start, size, inside.pop())] if inside else [] return (prefixes(u, plan, start, size // 2) + prefixes(u, plan, start + size // 2, size // 2)) def forward(source, slot, prefix, neigh, truth): """Runs with longest-prefix match; arrival is checked against actual ownership.""" u, hops = source, 0 while hops < 12: candidates = [p for p in prefix[u] if p[0] <= slot < p[0] + p[1]] if not candidates: return "black hole" v = min(candidates, key=lambda p: p[1])[2] if v == "local": return "reached" if truth.get(slot) == u else "black hole" if v not in neigh[u]: return "black hole" u, hops = v, hops + 1 return "loop" def pairs(count=40, seed=SEED): rand, out = make_rng(seed), [] while len(out) < count: x, y = LEAF[rand(9)], LEAF[rand(9)] if x != y: out.append((x, y)) return out def zones(plan): """The fewest regions countable in the name sequence without changing block.""" prev, count = None, 0 for _, y in sorted(plan.items()): b = next(i for i, ys in BLOCK.items() if y in ys) if b != prev: count, prev = count + 1, b return count def measure(plan, dest=None, truth=None): """Rows come from the plan, destinations from the address plan, arrival from ground truth.""" dest, truth = dest or plan, truth or plan neigh = neighbors() prefix = {u: prefixes(u, plan) for u in NODES} first, counts = {}, {"reached": 0, "loop": 0, "black hole": 0} for slot, y in sorted(dest.items()): first.setdefault(y, slot) for x, y in pairs(): counts[forward(x, first[y], prefix, neigh, truth)] += 1 return sum(len(p) for p in prefix.values()), len(prefix["c1"]), counts ORACLE = oracle() print(f"{'plan':<16s} {'per leaf':>8s} {'subnets':>7s} " f"{'total rows':>10s} {'c1':>3s} {'name zones':>10s} {'reached':>7s}") for name, build in (("aligned", aligned), ("creation order", creation_order)): for k in (1, 2, 3, 4): plan = build(k) rows, c1, s = measure(plan) print(f"{name:<16s} {k:8d} {len(plan):7d} {rows:10d} {c1:3d} " f"{zones(plan):10d} {s['reached']:7d}") print() home = aligned(4) moved = {slot: ("y1" if y == "y9" else y) for slot, y in home.items()} print(f"{'state':<32s} {'total rows':>10s} {'c1':>3s} {'reached':>7s} " f"{'black hole':>10s}") for name, plan, truth in (("plan in place", home, None), ("moved, summary not updated", home, moved), ("moved, separate row added", moved, moved)): rows, c1, s = measure(plan, home, truth) print(f"{name:<32s} {rows:10d} {c1:3d} {s['reached']:7d} " f"{s['black hole']:10d}") ``` ``` plan per leaf subnets total rows c1 name zones reached aligned 1 9 73 3 3 40 aligned 2 18 73 3 3 40 aligned 3 27 73 3 3 40 aligned 4 36 73 3 3 40 creation order 1 9 90 6 3 40 creation order 2 18 171 12 6 40 creation order 3 27 249 17 9 40 creation order 4 36 335 24 12 40 state total rows c1 reached black hole plan in place 73 3 40 0 moved, summary not updated 73 3 38 2 moved, separate row added 76 4 40 0 ``` #### Row Count Can Be Independent of Subnet Count The first four rows of the top table are the whole lesson. In the aligned plan, as subnet count climbs from **9** to **36**, total table rows stay at **73**. A network that quadruples in size adds not a single row to its table. The core's table holds at **3** rows: one prefix per block. The bottom four rows show the same topology with addresses distributed by creation order. Total rows climb **90, 171, 249, 335** — linear with subnet count. At thirty-six subnets, the gap is **73** against **335**, a factor of **4.6**. The core's table holds **24** rows instead of **3**. The source of the gap is a single condition. In the aligned plan, every address in a block is reachable through the same next hop, so a single prefix covers all of them. In the creation-order plan, two consecutive addresses fall into separate blocks; no coverable range remains, and the table drops to one row per address. The `name zones` column repeats the same accounting for names. In the aligned plan, when names are laid out in the plan's order, **3** ranges result — one zone per block. In names laid out by creation order, the count grows **3, 6, 9, 12**. A naming plan is not a separate design; it is the same question as the address plan, and it is measured with the same arithmetic. One thing does not change: the `reached` column reads **40** in all eight rows. The plan does not lose packets, it only grows the table. The plan's cost is not in latency, it is in **the state carried.** #### The Address the Summary Does Not Own The bottom table measures the summary's single weak point. If the networks attached to `y9` are moved to a different leaf and their addresses stay the same, the tables do not change at all — total rows are still **73**, the core still **3**. But **2** of the forty packets fall into a black hole. The reason is this: the core's `32-47 -> d5` row now announces an address it no longer owns. A summary says that every address it covers lies in that direction; the moved network does not lie in that direction. The summary is not wrong, it is **over-broad** — and a truth that over-covers is a falsehood. The fix is in the last row. If a separate, narrower row is added for the moved network, all forty of the forty packets reach; the cost is rows climbing from **73** to **76** in total, and from **3** to **4** at the core. Three rows look small, but the rule is plain: **every exception is a row, and exceptions accumulate.** The plan is the only thing protecting the table from growth; the way to keep protecting it is to renumber the moved network. #### Summary - Route summarization has a single condition: every address in the summarized range must be reachable through the same next hop; a plan either satisfies this condition or it does not. - In the aligned plan, as subnet count climbs from **9** to **36**, total rows stay at **73** and the core's table stays at **3**. - In the plan distributed by creation order, the same topology holds **90, 171, 249, 335** rows; at thirty-six subnets the gap is a factor of **4.6**. - A naming plan is not a separate design: the name zone count stays at **3** in the aligned plan, and climbs from **3** to **12** for names laid out by creation order. - A single moved network leaves the summary announcing an address it no longer owns, and **2** packets fall into a black hole; adding a separate row fixes it but raises the row count from **73** to **76**. #### Course Wrap-Up The course opened with a single question: if the decision is read not from what is written in the packet but from the device's own table, and that table is a copy of a shared truth, what happens to the packet for as long as the copies disagree? Seventeen lessons asked this question with seventeen separate disagreements, and every one counted the same three fates. | lesson | disagreement measured | reached | loop or black hole | |---|---|---|---| | Repeater, Hub, and Switch | the absence of any table | 40 frames, 280 deliveries | none; 240 unnecessary copies, 34 collisions | | MAC Address Tables | the entry's age | 110 deliveries, 278 once lifetime is shortened | 3 black holes, 0 once lifetime is shortened | | VLANs | the segment's boundary against the table's scope | flooding delivery 280, 51, 8 | black holes 0, 23, 29, 32 | | Spanning Tree Protocol | the tree was renewed, tables are stale | 40/40 on the tree, 106 and 129 hops | 19 and 20 black holes; 10 loops once two switches refresh | | Link Aggregation | leg mapping against the leg's state | 8 flows distributed without splitting | 2 black holes in a five-frame window | | Routing Decision | the copy's age and the reading rule | converged 40/40, 83 and 99 hops | 14 black holes at the moment of the break | | Static and Dynamic Routing | the static table never hears about the break | 40 in two rounds under dynamic | 14 black holes under static, fixed for six rounds; 6 loops once two nodes hear | | Distance Vector Protocols | the age of the neighbor's decision | 0, 9, 20, 32, 40 — four rounds | sixty of sixty packets loop at an unreachable destination; split horizon brings it down to 5 | | Link State Protocols | the database's missing entry | 9, 20, 32, 40 — three rounds | no loop; a wrong table comes only from the missing entry | | Border Gateway Protocol | policy against the shortest path | 40/40 under the transit ban, 92 hops | 14 black holes once the advertisement closes; 7 packets outside the contract in the leak | | Routing Instances | the same destination's two decisions across two instances | 40/40 across three instances, 83, 99, 91 hops | 14 black holes once reduced to a single table | | MPLS and Label Switching | the label path against the underlying link's state | 40 full-view and 43 label-view hops | 14 black holes when the chord breaks and the path is not renewed | | Overlay Networks | the overlay's table against the underlay's table | 40/40 with both layers converged, overlay 74 hops | 21 tunnel black holes while the underlay is stale; 12 overlay loops once the tunnel drops and both ends hear | | Layered Design | cold start and the busiest link breaking | 40/40 across three designs; 121, 80, 138 hops | 21 permanent black holes in the flat chain | | Spine–Leaf Design | the loss of a leaf-spine link | 40/40, 80 hops, every path 2 hops | 14 permanent black holes with a single spine, 0 from two onward | | Redundancy and Failover | who holds the virtual address | 40/40 with failover | 40 black holes when nobody has heard; 40 loops when both believe the peer active | | Address and Naming Plan | what the summary covers against what it owns | 40/40 with 73 rows | 2 black holes in the moved network | The table repeats three things over and over. **Partial information produces a more expensive failure than no information:** a break nobody hears about gives a black hole, and the failure is unmistakable; a break a few nodes hear about gives a loop, and it looks like congestion. **No single device can put a packet into a loop by itself:** a loop is a disagreement between at least two tables, and a packet leaving a node whose own table is correct can still die. And **convergence is not a speed, it is a round count:** how many rounds it takes depends on how far the information has to travel. All of these measurements shared one silent assumption. A link either exists or it does not; a neighbor either hears or it does not; a frame either gets forwarded or it does not. If a cable exists between two devices, what that cable carries reaches the other side — throughout the course, the opposite was never considered, except in the case of a break. The next course lifts this assumption: on a wireless link, whether a transmitted frame arrives is not a certainty but a **probability**, the medium is shared, and who is listening is unknown. Everything the wired link took as given will be asked again there.