15. Advanced and Emerging Topics

The preceding chapters described a network as a thing that carries packets between endpoints; this one is about the places where that description stops being sufficient. Distributed systems expose what the network cannot promise, measurement and modelling are how claims about a network are made defensible rather than anecdotal, and the frontier topics are the open questions whose answers will shape what the next decade of infrastructure looks like. The material here is deliberately less settled than what came before, so the emphasis is on the reasoning that survives when the specific technology does not.

<a id="151-distributed-systems-networking"></a>

15.1 Distributed Systems Networking

A distributed system is one in which the network's imperfections become the application's problem: this subchapter covers the failure model that makes distribution hard, what a partition forces you to give up, how nodes locate data without a directory, how information spreads without a coordinator, and what it costs to make a set of machines agree.

Failure Models and Partial Failure

Theory

A program running on one machine has two outcomes: it works, or it crashes and you find out. A program spread across many machines has a third, and it is the one that makes distributed systems hard — the outcome that is unknown. You sent a request, nothing came back, and you cannot determine whether the request was never received, was received and executed but the reply was lost, or is executing right now and will complete after you have given up.

This is partial failure: some components fail while the rest continue, and the survivors cannot reliably tell which. On a single machine, failures are total and shared — if the process dies, every part of it dies together, and there is no possibility of one function believing another is alive when it is not. The network removes that shared fate, and what replaces it is ambiguity.

The ambiguity has a precise form worth memorising: a crashed node, an overloaded node, and a partitioned node are indistinguishable from the outside. Each produces exactly the same observation, which is silence. The analogy is telephoning a colleague who does not answer. The ringing tone is identical whether they stepped out, are in a meeting with the phone face-down, or the handset is broken. You cannot tell from the ringing, and no amount of listening harder helps. You need either a second channel or a decision rule.

A timeout is that decision rule, and it is a guess, not a measurement. Setting a timeout means choosing a point on a trade-off with no optimum: short timeouts detect real crashes quickly but declare healthy-but-slow nodes dead, and a node wrongly declared dead is often worse than a node that is genuinely dead — it is still running, still holding locks, still writing to storage, and now a replacement has been started alongside it. Long timeouts avoid that error and leave the system stalled for the duration of every real failure.

Failure models are the vocabulary for what a component is permitted to do when it fails, ordered from most to least convenient:

Model	The failed node may	Assumption cost
Fail-stop	Halt, and the halt is reliably detectable	Requires a perfect detector — unattainable on a real network
Crash-stop	Halt permanently, silently	Ignores nodes that come back
Crash-recovery	Halt, then restart with stable storage intact	Needs durable state and fencing
Omission	Drop some messages while continuing	Covers congestion and one-way link faults
Timing	Respond arbitrarily late	The realistic asynchronous model
Byzantine	Do anything, including lying consistently	Costs 3f+1 replicas, used where nodes are not all trusted

Most production systems assume crash-recovery with omission and timing faults, which is to say: nodes stop and come back, messages are lost, and nothing is on time. Byzantine tolerance is reserved for cases where the participants are not under one administration, which is why it appears in blockchains and rarely inside a single company's datacentre.

Three consequences follow directly and shape real designs:

Exactly-once delivery is not achievable over a network. If the reply is lost, the sender cannot know whether to retry. The workable construction is at-least-once delivery plus an idempotent operation, which yields an effect that happens once regardless of how many times the message arrives. This is why well-designed APIs take an idempotency key.

Failure detectors are better expressed as suspicion than as a boolean. The phi-accrual approach outputs a continuously increasing suspicion level derived from the distribution of recent heartbeat intervals, letting each consumer choose its own threshold. A cheap action can act at low suspicion, an expensive or destructive one can demand more evidence.

A node declared dead may not be. The node that lost its lease because of a garbage-collection pause will resume mid-write, unaware anything happened. The defence is a fencing token: a monotonically increasing number issued with each lease, which storage checks and rejects if it is lower than the highest already seen. The returning node's writes are refused because its token is stale, and correctness no longer depends on the detector being right.

Examples

The core ambiguity: three different worlds, one identical observation.

  t=0        t=1        t=2        t=3
   |          |          |          |
A  |--req---->X                            node CRASHED before executing
   |          (silence)                    -> safe to retry

B  |--req---->+---exec--->...              node is SLOW, still executing
   |          (silence)                    -> retry DUPLICATES the effect

C  |--req---->+---exec--->+--reply--X      reply LOST in the network
   |          (silence)                    -> retry duplicates; work is done

The client's view in all three cases:   sent a request, heard nothing.
No timeout value distinguishes them. Design for all three at once.

import random, math
random.seed(7)

def healthy_rtt_ms():
    """A HEALTHY node: usually fast, occasionally stalled by GC or a full queue."""
    return random.gauss(40, 9) if random.random() > 0.03 else random.gauss(750, 250)

SAMPLES, HEARTBEAT_S = 20_000, 1.0
rtts = [max(1.0, healthy_rtt_ms()) for _ in range(SAMPLES)]

print(f"{'timeout':>9s} {'wrongly dead':>13s} {'false alarms':>14s} {'crash noticed after':>21s}")
for t in (100, 200, 500, 1000, 2000, 5000):
    fp = sum(1 for r in rtts if r > t) / SAMPLES          # healthy node exceeds timeout
    per_day = fp * (86400 / HEARTBEAT_S)
    print(f"{t:6d} ms {fp*100:12.2f}% {per_day:11.0f}/day {t:18d} ms")

# --- Phi accrual: report a SUSPICION LEVEL, not a boolean ---
mean, sd = 40.0, 9.0
def phi(silent_ms):
    """-log10 P(a healthy node is still silent after `silent_ms`), normal tail."""
    z = (silent_ms - mean) / sd
    p = 0.5 * math.erfc(z / math.sqrt(2))                  # upper-tail probability
    return float('inf') if p <= 0 else -math.log10(p)

print()
for silent in (50, 60, 70, 80, 90, 100):
    print(f"  silent {silent:4d} ms -> phi = {phi(silent):5.2f}"
          f"   {'act' if phi(silent) >= 8 else 'watch'}")

#   timeout  wrongly dead   false alarms   crash noticed after
#    100 ms         2.93%        2532/day                100 ms
#    200 ms         2.92%        2519/day                200 ms
#    500 ms         2.52%        2177/day                500 ms
#   1000 ms         0.40%         346/day               1000 ms
#   2000 ms         0.00%           0/day               2000 ms
#   5000 ms         0.00%           0/day               5000 ms
#
#   silent   50 ms -> phi =  0.88   watch
#   silent   60 ms -> phi =  1.88   watch
#   silent   70 ms -> phi =  3.37   watch
#   silent   80 ms -> phi =  5.36   watch
#   silent   90 ms -> phi =  7.86   watch
#   silent  100 ms -> phi = 10.88   act
#
# The 3% tail of slow-but-healthy responses is the whole problem. A 200 ms
# timeout evicts a healthy node 2500 times a day; a 2 s timeout stops evicting
# healthy nodes and makes every real crash cost two seconds of stall. There is
# no value that is good at both, which is why the choice belongs to the caller.

Key Takeaways

• The defining feature of a distributed system is partial failure: an outcome that is neither success nor failure but unknown.
• Crashed, slow, and partitioned are indistinguishable from outside. Silence carries no information about which one occurred.
• A timeout is a guess trading false eviction of healthy nodes against detection delay, and no value is good at both.
• Assume crash-recovery with omission and timing faults. Reserve Byzantine tolerance for mutually distrusting participants.
• Exactly-once on the wire does not exist. Build at-least-once delivery plus idempotent operations with an idempotency key.
• Prefer graded suspicion (phi-accrual) to a boolean alive/dead, so each caller picks a threshold matching its action's cost.
• A node wrongly declared dead keeps running. Use fencing tokens so correctness does not depend on the detector being correct.

🧪 Practice

1. For each of these, name the weakest failure model that covers it: a server losing power, a link dropping 2% of frames, a node pausing 8 seconds for garbage collection, and a node returning a stale value it knows is stale.
2. Using the table in the example, choose a heartbeat timeout for a cluster where evicting a healthy node triggers a 5-minute data rebalance. Justify the choice in terms of the two error types.
3. Design an idempotent "transfer funds" endpoint that is safe under at-least-once delivery. State exactly what the server stores and for how long.
4. Interview-style: A leader holds a lease, pauses for 30 seconds, and resumes believing it is still leader while a new leader is already serving writes. (Hint: no adjustment to the lease duration removes the risk — the fix is on the resource side, and it involves a number that only increases.)

Consistency and Network Partitions

Theory

Replication exists to survive failures, and the moment data exists in more than one place, the question becomes what a reader is entitled to see. If the network were perfect, replicas would always agree and there would be no question. The network is not perfect, so consistency is a set of promises about what a reader may observe, and each promise has a price measured in round trips and in availability.

A partition is the case where some replicas can still reach each other but not all of them. Note that a partition is not necessarily a severed cable — a node too slow to respond within the timeout is, from the system's point of view, partitioned. This is why partitions cannot be designed away: they are the unavoidable consequence of the previous topic's ambiguity.

CAP, stated precisely. The common phrasing "pick two of consistency, availability, partition tolerance" is misleading, because partition tolerance is not a choice — partitions happen whether you tolerate them or not. The accurate statement is conditional: when a partition occurs, a system must choose between refusing requests (preserving consistency) and answering from an isolated subset (preserving availability, at the cost of possibly stale or divergent data). Outside a partition you can have both, which is why the theorem says nothing at all about a healthy network.

PACELC completes it. If there is a Partition, choose Availability or Consistency; Else, choose Latency or Consistency. The "else" clause is the one that matters most days, because partitions are rare and latency is constant. A linearizable read must confirm it is not stale, which requires contacting a quorum, which costs at least one round trip — and if your quorum spans an ocean, that round trip is a hundred milliseconds you pay on every request.

Consistency models form a ladder, and every step down buys latency or availability with a weaker guarantee:

Model	Promise	Cost
Linearizable	Every read sees the most recent completed write, as if one copy existed	Quorum round trip; unavailable on the minority side of a partition
Sequential	All nodes see operations in the same order, not necessarily real time	Cheaper, but a read can be arbitrarily stale
Causal	Operations that are causally related appear in order everywhere	Available under partition; needs version vectors
Read-your-writes	A client never fails to see its own prior write	Session stickiness or a per-client token
Eventual	Replicas converge if updates stop	Cheapest; readers may see anything in the interim

Quorums make the trade-off arithmetic. With N replicas, writing to W and reading from R, a read is guaranteed to see the newest write only if R + W > N, because that inequality forces the read set and the write set to share at least one replica. If R + W is not greater than N, there exists a read quorum disjoint from the last write quorum, and a stale read is not a bug but a configuration.

The remaining hazard is split brain, where both sides of a partition believe they are authoritative and accept conflicting writes. Majority quorums prevent it by arithmetic: two disjoint majorities of the same set cannot exist. Systems that instead choose availability must plan for convergence, using last-write-wins (which silently discards data), version vectors with application-level merge, or CRDTs, which are data types designed so that concurrent updates merge deterministically and no conflict resolution is needed.

Examples

N = 5
REPLICAS = ["A", "B", "C", "D", "E"]

# --- Part 1: overlap. Does a read quorum have to touch a written replica? ---
def worst_case_read(R, W):
    store = {r: (1, "v1") for r in REPLICAS}
    written = REPLICAS[:W]                       # the write lands here
    for r in written:
        store[r] = (2, "v2")
    unwritten = [r for r in REPLICAS if r not in written]
    quorum = (unwritten + written)[:R]           # adversary reads the stalest R
    return max(store[r] for r in quorum)[1]      # highest version seen wins

print(f"{'R':>2s} {'W':>2s} {'R+W':>4s} {'> N?':>5s}  {'worst-case read':>15s}")
for R, W in [(1, 1), (1, 3), (2, 3), (3, 2), (3, 3), (1, 5), (5, 1)]:
    val = worst_case_read(R, W)
    print(f"{R:2d} {W:2d} {R+W:4d} {'yes' if R+W > N else 'NO':>5s}  {val:>15s}"
          f"{'' if val == 'v2' else '   <- STALE'}")

# --- Part 2: partition. A 3|2 split, majority quorum W = R = 3 ---
print("\npartition {A,B,C} | {D,E}, W = R = 3 (majority)")
for side, members in (("majority {A,B,C}", 3), ("minority {D,E}  ", 2)):
    can = members >= 3
    print(f"  {side}: reachable = {members} -> "
          f"{'writes and reads SUCCEED' if can else 'writes and reads REFUSED (choosing C over A)'}")
print("  relax to W = 1 and both sides accept writes: available, and now divergent (AP)")

#  R  W  R+W  > N?  worst-case read
#  1  1    2    NO               v1   <- STALE
#  1  3    4    NO               v1   <- STALE
#  2  3    5    NO               v1   <- STALE
#  3  2    5    NO               v1   <- STALE
#  3  3    6   yes               v2
#  1  5    6   yes               v2
#  5  1    6   yes               v2
#
# partition {A,B,C} | {D,E}, W = R = 3 (majority)
#   majority {A,B,C}: reachable = 3 -> writes and reads SUCCEED
#   minority {D,E}  : reachable = 2 -> writes and reads REFUSED (choosing C over A)
#   relax to W = 1 and both sides accept writes: available, and now divergent (AP)
#
# Note R=1,W=5 and R=5,W=1 are both consistent and both fragile: the first
# cannot write if ANY replica is down, the second cannot read. R=W=3 is the
# usual choice because it tolerates the loss of any two replicas on both paths.

The choice a partition forces, drawn out:

            +-------------- partition ---------------+
            |                                        |
   [A] [B] [C]   majority, 3 of 5          [D] [E]   minority, 2 of 5
        |                                       |
   CP:  serves reads and writes            refuses everything
        (consistent, but D and E's         (consistent, but their
         clients see an outage)             clients see an outage)

   AP:  serves reads and writes            ALSO serves reads and writes
        (both sides available, and now divergent: two histories to merge
         when the partition heals -- with real user data in both)

   There is no third column. The partition removes the option of having both.

Key Takeaways

• A partition includes slowness, not just a cut cable. A node that misses the timeout is partitioned by definition.
• CAP is conditional: only during a partition must you choose between refusing requests and serving possibly divergent data.
• PACELC's "else" clause dominates day to day — consistency costs a quorum round trip on every request, partition or not.
• R + W > N is the overlap condition that makes a read see the latest write. Below it, stale reads are configured, not accidental.
• Majority quorums prevent split brain by arithmetic, since two disjoint majorities of one set cannot exist.
• If you choose availability, choose a convergence strategy deliberately: last-write-wins discards data silently, CRDTs merge without conflict.
• Weaker models are not automatically wrong. Causal and read-your-writes cover most user-visible expectations at a fraction of the cost.

🧪 Practice

1. With N = 7, list every (R, W) pair that guarantees overlap and, for each, state how many replica failures the read path and the write path survive.
2. Classify each requirement as needing linearizable, causal, or eventual consistency: a bank balance check before withdrawal, a comment appearing after the post it replies to, a view counter, and a user seeing their own profile edit immediately.
3. A cluster is split 4 | 3 with majority quorums. Describe exactly what each side can do, then describe what changes if it splits 2 | 2 | 3.
4. Interview-style: An engineer proposes running a five-node quorum database across five continents "for availability." (Hint: compute what a single write costs before arguing about availability, and ask which replica must answer before the client hears anything.)

Distributed Hash Tables

Theory

Suppose a million machines collectively store a billion objects, and a client holds a key. Which machine has it? The obvious answer is a directory, but a directory is a single point of failure, a bottleneck, and a thing that must itself be replicated and kept consistent. A distributed hash table answers the question without a directory at all: the key's own hash determines which node is responsible, so every participant can compute the answer independently.

The naive version is node = hash(key) % N, and it works until N changes. Add one node to a cluster of eight and the modulus becomes nine, which changes the answer for almost every key — roughly 89% of the data must move, which for a cache means a near-total miss storm and for a storage system means an unacceptable rebalance. The requirement is that adding or removing a node moves only the keys that node is newly responsible for, about K/N of them.

Consistent hashing achieves this with a simple change of geometry. Map both keys and nodes onto the same circular number space, typically the output range of a hash function treated as a ring. Each key belongs to the first node encountered walking clockwise from the key's position. Adding a node inserts one point on the ring and captures only the arc between it and its predecessor; every other key is untouched. The analogy is a clock face where each node claims the minutes up to the next node: adding a hand steals a slice from exactly one neighbour, rather than renumbering the whole dial.

Consistent hashing alone distributes badly. With eight randomly placed points, arcs vary widely and so does load. The fix is virtual nodes: each physical node claims many ring positions rather than one, so its total arc converges on its fair share by averaging. This also makes heterogeneous capacity easy — give a machine twice the virtual nodes and it takes twice the keys — and it spreads a failed node's load across all survivors rather than dumping it on one successor.

Routing is the second half of the problem. Consistent hashing says who is responsible; in a cluster small enough for every node to know every other node, that is enough, and this is what Dynamo-style systems such as Cassandra do. At Internet scale, full membership is impossible, so each node keeps a partial routing table structured so that every hop at least halves the distance to the target, giving O(log N) hops.

System	Metric	Routing state	Hops	Where seen
Chord	Ring distance	Finger table, O(log N)	O(log N)	Academic, foundational
Kademlia	XOR of node IDs	k-buckets, parallel lookups	O(log N)	BitTorrent DHT, IPFS, Ethereum
Dynamo-style	Ring, full membership	Every node knows all	1	Cassandra, Riak, Voldemort

Kademlia's XOR metric deserves a note because it is elegant and won in practice: distance is symmetric, so a node learns useful routing entries simply from the queries it receives, and lookups can be issued to several candidates in parallel, which hides the slow and dead nodes that dominate an open peer-to-peer network.

The network cost is what a distributed-systems course often skips. Each hop is a real round trip over the Internet. Twenty hops at 80 ms is 1.6 seconds for a single lookup, so implementations use proximity neighbour selection — when several candidates are equally valid by ID, pick the one with the lowest measured latency — and parallelism to avoid waiting on timeouts. Churn is the other practical difficulty: in open networks nodes join and leave constantly, routing tables go stale, and replicas must be re-created faster than they are lost.

Examples

import hashlib, bisect
def h(s):
    return int(hashlib.sha1(s.encode()).hexdigest()[:8], 16)   # 32-bit ring position

class Ring:
    def __init__(self, nodes, vnodes=1):
        self.vnodes, self.ring, self.pos = vnodes, {}, []
        for n in nodes:
            self.add(n)
    def add(self, node):
        for v in range(self.vnodes):
            p = h(f"{node}#{v}")                                # one point per virtual node
            self.ring[p] = node
            bisect.insort(self.pos, p)
    def lookup(self, key):
        i = bisect.bisect(self.pos, h(key)) % len(self.pos)     # walk clockwise
        return self.ring[self.pos[i]]

KEYS = [f"object-{i}" for i in range(100_000)]
NODES = [f"node{i}" for i in range(8)]

mod_before = {k: h(k) % 8 for k in KEYS}
mod_after = {k: h(k) % 9 for k in KEYS}
moved_mod = sum(1 for k in KEYS if mod_before[k] != mod_after[k])

for vn in (1, 64, 256):
    r = Ring(NODES, vnodes=vn)
    before = {k: r.lookup(k) for k in KEYS}
    load = [sum(1 for v in before.values() if v == n) for n in NODES]
    spread = (max(load) - min(load)) / (len(KEYS) / 8) * 100    # imbalance, % of fair share
    r.add("node8")
    moved = sum(1 for k in KEYS if r.lookup(k) != before[k])
    print(f"vnodes={vn:4d}  imbalance max-min = {spread:5.1f}% of fair share   "
          f"keys moved when adding a 9th node = {moved/len(KEYS)*100:4.1f}%")
print(f"modulo hashing (no ring): keys moved = {moved_mod/len(KEYS)*100:.1f}%   "
      f"(ideal is 1/9 = 11.1%)")

# vnodes=   1  imbalance max-min = 313.8% of fair share   keys moved ... =  11.9%
# vnodes=  64  imbalance max-min =  19.7% of fair share   keys moved ... =   8.9%
# vnodes= 256  imbalance max-min =  13.9% of fair share   keys moved ... =  11.5%
# modulo hashing (no ring): keys moved = 88.9%   (ideal is 1/9 = 11.1%)
#
# Two separate wins. The ring moves ~11% of keys where modulo moves 89% -- that
# is the difference between a rebalance and an outage. And ONE point per node is
# not enough: the busiest node holds three times the fair share until virtual
# nodes average the arcs out.

Consistent hashing ring, and what adding a node actually disturbs

        0 / 2^32
            |
     N4 ----+---- N1            key K hashes to *, and belongs to the
      \           /             first node CLOCKWISE from it: N2.
       \    *K   /
        \   |   /               Insert N5 in the arc between N1 and N2:
         \  v  /                  - keys in (N1, N5] move to N5
     N3 ---(N2)---                - every other arc is untouched
                                  - no other node changes at all
       after inserting N5 between N1 and N2:

     N4 ----+---- N1
       \        \                K now resolves to N5. One arc moved.
        \   *K  (N5)             Under modulo hashing, EVERY key would
         \  |   /                have been reassigned instead.
     N3 ---(N2)-

Key Takeaways

• A DHT replaces a directory with arithmetic: the key's hash names its owner, so any node can compute the location.
• Modulo hashing is fatal at scale — one membership change relocates nearly all keys (89% in the example above).
• Consistent hashing moves only about K/N keys per membership change by placing keys and nodes on a shared ring.
• Virtual nodes are not optional. One point per node produced a three-times imbalance; many points per node average it away and enable weighting.
• Routing is separate from placement. Full membership gives one-hop lookups in a datacentre; O(log N) structured routing is for Internet scale.
• Kademlia's XOR metric is symmetric, so nodes learn routes from incoming queries and can probe several candidates in parallel.
• Every routing hop is a real round trip. Latency, not hop count, is the user-visible cost, so prefer nearby candidates and parallelise.

🧪 Practice

1. Compute the fraction of keys that must move when a cluster grows from 10 to 11 nodes, under modulo hashing and under consistent hashing. Explain the difference in one sentence.
2. A ring has nodes at positions 100, 400, 750, and 900 on a 0–999 ring. Give the owner of keys hashing to 50, 399, 751, and 950, then give the owners after a node joins at 500.
3. You must give one machine three times the share of the others. Describe two ways to do it with virtual nodes and state which handles that machine's failure better.
4. Interview-style: A 500-node Kademlia DHT has a median lookup latency of 2.1 seconds with only about 9 hops. (Hint: 9 hops cannot cost 2.1 seconds unless something is being waited on — ask what happens at a hop whose chosen contact has silently left.)

Gossip and Epidemic Protocols

Theory

A thousand nodes need to learn a new piece of membership state. The centralised approach has one node tell everyone, which puts O(N) load on that node and makes it a single point of failure. Flooding has every node forward to every neighbour, which is robust but generates O(N²) messages and melts the network. Gossip takes the middle path: each node, on a fixed interval, picks a small number of peers at random and exchanges state with them. No coordinator, no topology to maintain, no single point of failure, and the message rate per node is constant regardless of cluster size.

The name is the analogy, and it is exact. Information spreads through a population the way a rumour does, and the mathematics are those of an epidemic. In the first round, one node knows. In the second, two. Then four. The infected fraction follows a logistic curve — slow start, explosive middle, long tail as the last few uninfected nodes must be picked by chance — and full coverage arrives in O(log N) rounds. Going from a thousand nodes to a hundred thousand adds only a handful of rounds.

There are three exchange styles, and the differences matter at the tail:

Style	Mechanism	Strength	Weakness
Push	Informed node sends to random peers	Fast while few know	Wasteful at the end: most targets already know
Pull	Node asks random peers for news	Fast at the end	Useless at the start: most peers know nothing
Push-pull	Both directions in one exchange	Best overall, O(log log N) tail	Slightly larger messages

Another axis is what gets exchanged. Rumour mongering spreads a specific new update and stops spreading it once it looks widely known, which is cheap but can miss nodes. Anti-entropy compares complete state between two peers and reconciles differences, which guarantees convergence but is expensive unless the comparison is made cheap — which is what Merkle trees are for. Two replicas exchange a root hash; if it matches, they are identical and nothing more is sent. If not, they descend only into the subtrees that differ, so the cost is proportional to the number of differences, not the size of the data.

The property that makes gossip valuable operationally is that it degrades gracefully. No single message is important. Loss just slows convergence rather than breaking it, a node that restarts catches up automatically on its next exchange, and there is no membership list to maintain or leader to elect. This is why it underpins cluster membership in Cassandra, Consul, Serf, and Redis Cluster, and why SWIM builds failure detection on it: a node probes a random peer directly, and if that fails it asks k other nodes to probe on its behalf before marking the peer suspect. The indirect probe distinguishes "the target is down" from "my path to the target is down," which is precisely the ambiguity from the failure-models topic, attacked with a second channel rather than a longer timeout.

The costs are real and should be stated. Gossip is eventually consistent only, with no bound on when a specific node learns a specific fact. It sends redundant messages — many exchanges tell a node something it already knows. And the aggregate traffic is O(N) per round across the cluster, which is fine for membership-sized state and inappropriate for bulk data.

Examples

import random, math, statistics
random.seed(11)

def gossip(n, fanout=1, mode="push-pull", loss=0.0):
    """One node starts informed; return (rounds to reach all, messages sent)."""
    informed = [False] * n
    informed[0] = True
    rounds = msgs = 0
    while not all(informed) and rounds < 200:
        rounds += 1
        snapshot = informed[:]                      # all exchanges in a round are concurrent
        for i in range(n):
            for _ in range(fanout):
                j = random.randrange(n)
                msgs += 1
                if random.random() < loss:          # the message is simply lost
                    continue
                if mode in ("push", "push-pull") and snapshot[i]:
                    informed[j] = True              # i tells j
                if mode in ("pull", "push-pull") and snapshot[j]:
                    informed[i] = True              # i asks j
    return rounds, msgs

print(f"{'nodes':>7s} {'log2(n)':>8s} {'push':>6s} {'pull':>6s} {'push-pull':>10s} {'msgs/node':>10s}")
for n in (100, 1_000, 10_000, 100_000):
    trials = 5 if n < 50_000 else 2
    res = {m: statistics.mean(gossip(n, 1, m)[0] for _ in range(trials))
           for m in ("push", "pull", "push-pull")}
    _, msgs = gossip(n, 1, "push-pull")
    print(f"{n:7d} {math.log2(n):8.1f} {res['push']:6.1f} {res['pull']:6.1f} "
          f"{res['push-pull']:10.1f} {msgs/n:10.1f}")

print("\n10 000 nodes, push-pull, with packet loss:")
for loss in (0.0, 0.1, 0.3, 0.5):
    r = statistics.mean(gossip(10_000, 1, "push-pull", loss)[0] for _ in range(3))
    print(f"  {loss*100:4.0f}% loss -> {r:4.1f} rounds to full coverage")

#   nodes  log2(n)   push   pull  push-pull  msgs/node
#     100      6.6   12.8   10.0        6.6        7.0
#    1000     10.0   18.0   13.6        9.6        9.0
#   10000     13.3   23.4   17.6       11.4       12.0
#  100000     16.6   28.5   21.0       14.0       15.0
#
# 10 000 nodes, push-pull, with packet loss:
#      0% loss -> 12.0 rounds to full coverage
#     10% loss -> 13.3 rounds to full coverage
#     30% loss -> 16.0 rounds to full coverage
#     50% loss -> 23.7 rounds to full coverage
#
# A THOUSAND-FOLD increase in cluster size costs about 7 extra rounds, and each
# node still sends one message per round. Losing HALF of all messages does not
# break convergence, it roughly doubles the number of rounds -- this tolerance
# is the reason gossip is used for membership rather than a reliable broadcast.

Epidemic spread, push-pull, 1000 nodes (typical run)

  round  informed                                          fraction
    1    #                                                  0.2%
    3    ####                                               0.8%
    5    ###########                                        3.1%
    7    ########################                          12.3%
    8    #####################################             38.4%
    9    ##############################################    78.0%
   10    ################################################  96.1%
   12    ################################################ 100.0%

  Slow start (few carriers), explosive middle (many carriers, few targets
  already informed), long tail (the last stragglers must be picked at random).
  The tail is why push-pull wins: PULL finds the stragglers, PUSH cannot.

Key Takeaways

• Gossip reaches every node in O(log N) rounds with a constant per-node message rate, so cluster size barely affects convergence time.
• Push-pull beats both pure modes: push spreads fast early, pull collects the stragglers that push reaches only by luck.
• Gossip is robust by construction. Fifty percent message loss roughly doubled convergence time rather than causing failure.
• Anti-entropy guarantees convergence, rumour mongering is cheaper. Merkle trees make anti-entropy affordable by exchanging hashes before data.
• SWIM's indirect probe distinguishes a failed node from a failed path by asking other nodes to check, instead of lengthening a timeout.
• The guarantee is eventual only — there is no bound on when a given node learns a given fact, so never gossip anything that needs a deadline.
• Traffic totals O(N) per round across the cluster. Suitable for membership and metadata, not for bulk data.

🧪 Practice

1. With a gossip interval of 1 second and push-pull, estimate the time to full membership convergence for 300 nodes and for 30,000. Explain why the answers are so close.
2. Explain, in terms of who already knows the news, why pull is nearly useless in round one and best in the final rounds.
3. Two replicas hold a million keys and differ in three of them. Describe the Merkle tree exchange and estimate how many hashes cross the wire.
4. Interview-style: A cluster using gossip membership reports nodes as flapping between alive and suspect during a period of high CPU load. (Hint: ask what the detector is actually measuring on a loaded node, and what SWIM's indirect probe would establish that a longer timeout would not.)

Consensus over Unreliable Networks

Theory

Consensus is the problem of getting a set of nodes to agree on one value despite failures, and it is the foundation beneath leader election, distributed locks, configuration management, and any replicated log. If you can agree on a sequence of values you can replicate a state machine, and if you can replicate a state machine you can build anything.

The bad news arrives first. The FLP impossibility result proves that in an asynchronous system — one with no bound on message delay — no deterministic algorithm can guarantee consensus if even a single node may crash. The intuition is the ambiguity from the first topic: a node that has not responded may be dead or merely slow, and any algorithm that decides without it risks being wrong, while any algorithm that waits may wait forever.

Practical systems escape FLP by weakening the model rather than defeating the proof. The standard escape is partial synchrony: assume the network is asynchronous in general but eventually behaves well for long enough to make progress. Under that assumption, safety is preserved always and liveness is preserved eventually — the system will never produce two conflicting decisions, but during a bad network period it may simply stop deciding. This split is the right mental model for Raft and Paxos: they never lie, they may stall.

Raft is the version worth understanding in detail because it was designed to be understood. It has three pieces:

Leader election. Time is divided into numbered terms, each with at most one leader. A follower that hears nothing from a leader for a randomised election timeout becomes a candidate, increments the term, and requests votes. A node grants at most one vote per term, so at most one candidate can collect a majority. The randomisation is what prevents repeated split votes.

Log replication. Clients send commands to the leader, which appends to its log and replicates to followers. An entry is committed once a majority has stored it, at which point it is safe to apply, because any future leader must have been elected by a majority, and any two majorities intersect, so the new leader's log necessarily contains that entry.

Term numbers as fencing. Every message carries its term. A message from an older term is rejected, and a node seeing a higher term immediately steps down. This is exactly the fencing-token idea from the failure-models topic, and it is what makes an old leader returning from a pause harmless rather than catastrophic.

The network determines the cost. A client write costs roughly one round trip from the client to the leader, plus one round trip from the leader to the nearest majority of replicas. The critical quantity is not the average RTT to all replicas but the RTT to the majority-th closest replica, because the leader waits for that one and not for the rest. This single fact governs replica placement: a slow distant replica adds fault tolerance without adding latency, while spreading replicas evenly across the globe makes every write pay an intercontinental round trip.

Byzantine consensus, where nodes may lie rather than merely fail, requires 3f+1 replicas to tolerate f faults and O(n²) messages per decision in protocols like PBFT. That cost is justified only when participants are mutually distrusting, which is why it appears in blockchain systems and almost never inside one organisation's infrastructure.

Examples

RTT = {  # measured round-trip times between regions, in ms
    ("us-east", "us-west"): 60,  ("us-east", "eu-west"): 75,  ("us-east", "ap-south"): 210,
    ("us-east", "sa-east"): 115, ("us-west", "eu-west"): 140, ("us-west", "ap-south"): 230,
    ("us-west", "sa-east"): 175, ("eu-west", "ap-south"): 120, ("eu-west", "sa-east"): 180,
    ("ap-south", "sa-east"): 300,
}
def rtt(a, b):
    return 0.5 if a == b else RTT.get((a, b)) or RTT[(b, a)]   # 0.5 ms inside a region

def commit_ms(replicas, leader):
    """Leader commits once a MAJORITY has acked, itself included."""
    need = len(replicas) // 2                       # acks required from OTHER replicas
    peers = sorted(rtt(leader, r) for r in replicas)[1:]       # drop the leader itself
    return peers[need - 1]                          # wait for the need-th fastest ack

PLACEMENTS = {
    "3 in one region":        ["us-east"] * 3,
    "3 across one continent": ["us-east", "us-west", "sa-east"],
    "5 spread globally":      ["us-east", "us-west", "eu-west", "ap-south", "sa-east"],
    "3 near + 2 far":         ["us-east", "us-east", "us-west", "ap-south", "eu-west"],
}
for name, rs in PLACEMENTS.items():
    best = min((commit_ms(rs, l), l) for l in set(rs))
    worst = max((commit_ms(rs, l), l) for l in set(rs))
    tolerated = len(rs) - (len(rs) // 2 + 1)
    print(f"{name:24s} n={len(rs)}  tolerates {tolerated} failure(s)   "
          f"best leader {best[1]:9s} {best[0]:6.1f} ms   worst {worst[0]:6.1f} ms")

# 3 in one region          n=3  tolerates 1 failure(s)   best leader us-east    0.5 ms  worst   0.5 ms
# 3 across one continent   n=3  tolerates 1 failure(s)   best leader us-east   60.0 ms  worst 115.0 ms
# 5 spread globally        n=5  tolerates 2 failure(s)   best leader us-east   75.0 ms  worst 210.0 ms
# 3 near + 2 far           n=5  tolerates 2 failure(s)   best leader us-east   60.0 ms  worst 210.0 ms
#
# Three lessons. (1) Replicas in ONE region commit in microseconds and die with
# the region. (2) WHICH node is leader changes commit latency by 3x on the same
# cluster -- leader placement is a latency decision, not an implementation
# detail. (3) The distant replicas in "3 near + 2 far" add fault tolerance
# WITHOUT adding latency, because the leader never waits for them.

Raft: an old leader returns after a pause and is harmlessly rejected

  term 5   L1 --------X (pause: GC, or a partition)
                       .
  term 6            [election] F2 and F3 elect L2 with a majority (2 of 3)
                       .
  term 6   L2 --append(term=6, idx=8)--> F2, F3      committed: majority stored it
                       .
  term 5   L1 wakes and sends append(term=5, idx=8)  <- stale term number
           F2, F3 reply: "current term is 6"         <- rejected, not applied
           L1 sees term 6 > 5 and steps down immediately

  No timing assumption was needed for safety. The term number alone made the
  returning leader's writes impossible to accept. Liveness paused during the
  election; correctness never did.

Key Takeaways

• FLP rules out deterministic consensus in a fully asynchronous system with one crash fault. Real systems assume partial synchrony instead.
• The resulting guarantee is always safe, eventually live: Raft and Paxos will stall under a bad network but will not produce conflicting decisions.
• Raft is three parts: leader election by randomised timeout, log replication committed by majority, and term numbers that fence stale leaders.
• Majority intersection is the whole argument: any two majorities share a node, so a new leader necessarily holds every committed entry.
• Commit latency is the round trip to the majority-th closest replica, not the average. Distant extra replicas can be free.
• Leader placement is a latency decision. The same five-node cluster committed in 60 ms or 210 ms depending only on which node led.
• Byzantine tolerance costs 3f+1 replicas and O(n²) messages. Use it only when the participants do not trust one another.

🧪 Practice

1. For Raft clusters of 3, 5, and 7 nodes, give the majority size, the failures tolerated, and state why an even cluster size adds no fault tolerance over the odd size below it.
2. Using the RTT table in the example, compute the commit latency of a 5-node cluster placed at us-east, us-east, us-west, eu-west, sa-east, with us-east leading. Compare it to the globally spread case.
3. Explain why Raft randomises the election timeout, and predict what happens if every node uses exactly 150 ms.
4. Interview-style: A three-node Raft cluster is up and healthy, but every write takes over a second and the leader changes every few minutes. (Hint: elections that keep firing on a healthy cluster point at one timer compared against one measured quantity — work out what the heartbeat interval must be relative to the network.)

<a id="152-network-measurement-and-modeling"></a>

15.2 Network Measurement and Modeling

Every claim about a network is a claim about a measurement, and measurements have methods, biases, and error bars: this subchapter covers the two families of measurement and what each can honestly support, how the Internet's structure is inferred and why the resulting maps are wrong in specific ways, the queueing mathematics that explains delay under load, the tools for experimenting without a production network, and why real traffic refuses to behave like the textbook model.

Active vs Passive Measurement

Theory

There are exactly two ways to learn something about a network. You can inject traffic and watch what happens to it, or you can observe traffic that was going to be there anyway. Every tool is one or the other, and the distinction determines what its output can honestly support.

Active measurement sends probes: ping, traceroute, iperf, OWAMP for one-way delay, or a synthetic HTTP transaction. Its strengths are control and coverage. You choose the source, destination, timing, packet size, and protocol, and you can measure a path that currently carries no traffic at all — which is the only way to know a backup path works before you need it. Its weakness is that it measures the fate of the probe, not the experience of the user. An ICMP echo is handled differently from a TCP flow: routers rate-limit and deprioritise control-plane traffic, middleboxes treat it specially, and load balancers hash it onto one path out of many. A probe that succeeds proves that a probe succeeded.

Passive measurement observes existing traffic: interface counters by SNMP or streaming telemetry, flow records by NetFlow or IPFIX, sampled packet headers by sFlow, or full capture at a tap or mirror port. Its strengths are that it reflects what users actually experienced, adds no load to the network, and sees things no probe would think to test. Its weaknesses are the mirror image: it can only observe where traffic exists and where you have a collection point, its data volume is large, and it carries privacy and regulatory weight because the records describe real people's activity.

Property	Active	Passive
What it measures	Behaviour of injected probes	Behaviour of real user traffic
Idle paths	Measurable	Invisible
Load added	Yes, and it can perturb the result	None
Represents user experience	Only by proxy	Directly
Data volume	Small and controlled	Large, usually sampled
Privacy exposure	Minimal	Significant
Typical tools	ping, traceroute, iperf, OWAMP, synthetic checks	SNMP, NetFlow/IPFIX, sFlow, port mirrors

Three pitfalls are worth internalising, because each produces confident wrong answers.

Sampling error is not intuitive. sFlow at 1-in-1000 gives excellent aggregate totals and near-useless per-flow detail for small flows, because the relative error of a sampled estimate scales as one over the square root of the number of samples captured. A flow that produced two samples supports no numerical claim at all, yet it will appear in the interface with a precise-looking byte count.

The probe rate changes the answer. Probing more often measures the path more thoroughly and perturbs it more, and at high rates active measurement becomes a load test. There is also a subtler bias: a periodic probe can synchronise with a periodic event and either always hit it or always miss it, so probe intervals are usually randomised.

One-way delay needs clock synchronisation that most networks do not have. Round-trip time requires only one clock and is therefore easy. Splitting it into forward and reverse components requires two clocks agreeing to better than the difference you are trying to measure, which NTP at a few milliseconds cannot support for a sub-millisecond path. That is what PTP and GPS-disciplined clocks are for.

The practical answer is that the two families are complementary and the strongest evidence uses both: passive measurement to notice that something changed and to quantify who was affected, active measurement to isolate where it changed by probing the segments in between.

Examples

import math
# sFlow-style 1-in-N sampling: what can the estimate actually support?
def rel_error(true_packets, N):
    """Relative standard error of an unbiased 1-in-N estimator (binomial)."""
    p = 1.0 / N
    expected_samples = true_packets * p
    if expected_samples == 0:
        return float('inf'), 0.0
    return math.sqrt((1 - p) / (true_packets * p)), expected_samples

print(f"{'flow size':>12s} " + " ".join(f"{'1-in-'+str(n):>12s}" for n in (100, 1000, 10000)))
for size in (100, 1_000, 10_000, 100_000, 1_000_000):
    cells = []
    for N in (100, 1_000, 10_000):
        err, exp = rel_error(size, N)
        cells.append("no samples" if exp < 1 else f"+/-{err*196:5.0f}%")  # 95% CI = 1.96 sigma
    print(f"{size:10d} pk " + " ".join(f"{c:>12s}" for c in cells))

#    flow size     1-in-100    1-in-1000   1-in-10000
#        100 pk    +/-  195%   no samples   no samples
#       1000 pk    +/-   62%    +/-  196%   no samples
#      10000 pk    +/-   20%    +/-   62%    +/-  196%
#     100000 pk    +/-    6%    +/-   20%    +/-   62%
#    1000000 pk    +/-    2%    +/-    6%    +/-   20%
#
# Read the diagonal: at 1-in-1000, a 10 000-packet flow is known to +/-62%. The
# collector will still print "14.2 MB" to three significant figures. Aggregate
# totals across millions of packets are accurate; PER-FLOW claims about small
# flows are not, and "top talkers" lists inherit this error silently.

Choosing the method from the question being asked

  "Is the backup circuit working?"          -> ACTIVE (no traffic to observe)
  "Why is checkout slow for EU users?"      -> PASSIVE first (who, how much,
                                                when), then ACTIVE to isolate
  "What is this link's capacity?"           -> ACTIVE (iperf; a load test)
  "What is this link's peak utilisation?"   -> PASSIVE (counters; never a probe)
  "Did the change break anything?"          -> PASSIVE (real traffic, real users)
  "Is one-way delay asymmetric?"            -> ACTIVE + synchronised clocks
                                                (NTP is not good enough)

Key Takeaways

• Active measurement injects probes and can test idle paths; passive measurement observes real traffic and reflects actual user experience.
• An active probe proves what happened to the probe. ICMP is rate-limited and deprioritised, so it is a weak proxy for application traffic.
• Passive measurement sees only where traffic and collectors both exist, and its records carry real privacy weight.
• Sampled per-flow numbers are far less precise than they look. Error scales as one over the square root of samples captured, not of flow size.
• Aggregate totals from sampling are trustworthy; small-flow detail is not. Treat top-talker lists from sparse sampling with suspicion.
• Randomise probe intervals so periodic probing cannot lock onto a periodic event, and keep probe rates below the level that perturbs the path.
• One-way delay requires synchronised clocks. Without PTP or GPS, report round-trip time and say so.

🧪 Practice

1. Classify each as active or passive and name one thing it cannot show: ping, an SNMP interface counter, iperf3, IPFIX flow records, and a synthetic login check.
2. At 1-in-2000 sampling, how many packets must a flow send before its estimated volume is accurate to within roughly 20% at 95% confidence?
3. A dashboard shows 0% loss from ping while users report failures. Give three mechanisms that produce this, and one measurement for each that would confirm it.
4. Interview-style: A team raises probe frequency from every 60 seconds to every second and the measured latency rises. (Hint: the probes are now a traffic class of their own — consider both what they do to the queue and what the router does to them.)

Internet Topology Discovery

Theory

Nobody has a map of the Internet. There is no registry of which router connects to which, no authority that could produce one, and no participant with an incentive to publish their own. Every map that exists was inferred from measurements, and understanding the inference is the only way to know what the map is wrong about.

Topology exists at several levels, and conflating them is the most common error:

Level	What a node is	Discovered by	Main difficulty
IP interface	One address on one router	traceroute	Routers have many addresses
Router	One physical device	Alias resolution	Merging aliases is unreliable
PoP	A facility in a city	Geolocation plus latency	Geolocation of infrastructure is poor
AS	One routing domain	BGP tables from collectors	Peering invisible to collectors

Traceroute is the workhorse and it lies in specific, learnable ways. It infers a path by sending probes with increasing TTL and reading the source address of each ICMP Time Exceeded reply. The first problem is that the reply's source address is whichever interface the router chose, usually the one facing the probe, so the addresses you collect belong to interfaces, not routers. Turning interfaces into routers is alias resolution, done by probing addresses and looking for a shared IP-ID counter or a common source address in replies, and it is a heuristic that fails on modern routers with per-interface counters.

The second problem is more damaging. Load balancing creates links that do not exist. Classic traceroute varies the destination port per probe so it can match replies to probes. Varying the port changes the five-tuple, which changes the ECMP hash, which means consecutive TTLs may be answered by routers on different parallel paths. The tool then prints them as consecutive hops, and the inferred adjacency between them is fiction. Paris traceroute fixes this by holding the flow-identifying fields constant and varying something else, such as the ICMP checksum, so all probes follow one path.

Further distortions to know about: MPLS tunnels can hide interior hops entirely, so two routers appear adjacent when several sit between them; anonymous hops appear where a router is configured not to send Time Exceeded, leaving a gap; and third-party addresses appear when a router replies from an interface not on the measured path, placing a node in the wrong part of the graph.

At the AS level the data source changes from probes to routing: public collectors such as RouteViews and RIPE RIS peer with many networks and archive their BGP tables. This gives an excellent view of the paths used to reach the collectors' peers, and a systematically poor view of everything else. Peering links that are never announced towards a collector are invisible, and because most peering is at the edge between regional networks, AS-level maps consistently understate connectivity there while representing the transit core well. Measurement platforms like CAIDA's Ark and RIPE Atlas improve this by distributing thousands of vantage points, but no distribution of probes fully removes the bias, because the probes still sit where volunteers and infrastructure are.

The honest conclusion is that an Internet topology map is a hypothesis with error bars, not a record. Used to reason about general structure, it is valuable. Used to claim a specific link exists, it needs corroboration.

Examples

import zlib
# Two equal-cost paths. A router hashes the 5-tuple to pick one, per FLOW.
PATHS = {0: ["R1", "A1", "A2", "A3", "R5"],      # the "upper" ECMP path
         1: ["R1", "B1", "B2", "B3", "R5"]}      # the "lower" ECMP path
def ecmp(flow_id):
    return zlib.crc32(str(flow_id).encode()) % 2  # stand-in for the router's hash

def trace(vary_flow_per_probe):
    hops = []
    for ttl in range(1, 6):
        # Classic traceroute increments the destination PORT for each probe,
        # which changes the 5-tuple, which re-rolls the ECMP decision.
        flow = ttl if vary_flow_per_probe else 33434
        hops.append(PATHS[ecmp(flow)][ttl - 1])
    return hops

classic, paris = trace(True), trace(False)
print("classic traceroute :", " -> ".join(classic))
print("Paris traceroute   :", " -> ".join(paris))
real = set(zip(PATHS[0], PATHS[0][1:])) | set(zip(PATHS[1], PATHS[1][1:]))
inferred = set(zip(classic, classic[1:]))
print("\nlinks the classic trace implies that DO NOT EXIST:")
for a, b in sorted(inferred - real):
    print(f"  {a} -> {b}")
print(f"false-link rate: {len(inferred - real)}/{len(inferred)} of the inferred adjacencies")

# classic traceroute : R1 -> B1 -> B2 -> A3 -> R5
# Paris traceroute   : R1 -> B1 -> B2 -> B3 -> R5
#
# links the classic trace implies that DO NOT EXIST:
#   B2 -> A3
# false-link rate: 1/4 of the inferred adjacencies
#
# The printed path looks perfectly ordinary. Nothing in the output marks the
# fabricated adjacency, and at Internet scale these accumulate into maps with
# links no cable ever carried.

Why one router shows up as several nodes (the alias problem)

            .-- 10.0.1.1 --.              A single physical router R has three
   probe -->|   ROUTER R   |--> onward    interfaces. Which address answers a
            '-- 10.0.2.1 --'              Time Exceeded depends on which one
                10.0.3.1                  the probe arrived through.

   trace from X:  ... -> 10.0.1.1 -> ...      three traces, three "routers",
   trace from Y:  ... -> 10.0.2.1 -> ...      one actual device. Without alias
   trace from Z:  ... -> 10.0.3.1 -> ...      resolution the graph has 3 nodes
                                              and inflated path diversity.

Key Takeaways

• There is no authoritative map. Every Internet topology is inferred, so its errors are properties of the method used.
• Keep the levels distinct: interface, router, PoP, and AS are four different graphs, and merging them silently produces nonsense.
• Traceroute reports interface addresses, not routers. Alias resolution merges them and is a heuristic that often fails.
• Classic traceroute fabricates links under ECMP by changing the flow identifier per probe. Use Paris traceroute, which holds it fixed.
• MPLS hides hops, anonymous routers leave gaps, and third-party replies misplace nodes. Each distorts the graph in a different direction.
• AS-level maps from BGP collectors represent the transit core well and understate edge peering, because unannounced links are unobservable.
• Treat a discovered link as a hypothesis needing corroboration, especially when the conclusion depends on that single link.

🧪 Practice

1. Run traceroute and traceroute -n to the same destination three times. Note which hops vary and give the two most likely explanations for any variation.
2. A trace shows * * * at hop 7 but hops 8 through 12 respond normally. List three causes and state what each implies about the path.
3. Explain why AS-level maps built from RouteViews systematically miss regional peering links, and describe a measurement that could find some of them.
4. Interview-style: A topology tool reports that your datacentre has 340 distinct routers; the inventory says 46. (Hint: the tool is counting something other than devices — ask what a router puts in the source address of a Time Exceeded message.)

Queuing Theory Basics and Little's Law

Theory

Everyone knows a congested link is slow. Queueing theory explains how slow, and the answer is the single most counter-intuitive number in network engineering: delay does not rise gradually with load, it rises hyperbolically, and almost all of the rise happens in the last stretch before saturation.

The setup is a queue with a server. Work arrives at average rate lambda, the server completes work at average rate mu, and utilisation rho = lambda / mu is the fraction of time the server is busy. For a network link, the server is the transmitter and the service time is fixed by physics: a 1500-byte packet on a 1 Gb/s link takes 12 microseconds to clock out, no matter what.

Little's Law is the first result and the most useful, because it assumes essentially nothing. For any stable system:

L = lambda * W        items in the system = arrival rate * time each spends in it

No distribution assumptions, no independence assumptions, no requirement that the queue be FIFO. It holds for a router buffer, a connection pool, a support ticket queue, and a factory. Its value in practice is that it lets you infer the quantity you cannot measure from the two you can. If a service handles 2000 requests per second with 40 ms average latency, it has 80 requests in flight on average, so a connection pool of 20 is guaranteed to be a bottleneck and no amount of tuning elsewhere will fix it.

The M/M/1 queue adds assumptions — Poisson arrivals, exponential service times, one server — and yields the delay formula. Mean time waiting in the queue is rho / (mu - lambda), and the important feature of that expression is the denominator: as lambda approaches mu, the denominator approaches zero and the delay approaches infinity. The analogy is a supermarket checkout. At 50% utilisation the cashier is idle half the time and you walk straight up. At 95% the cashier is almost never idle, so every fluctuation in arrival timing has nowhere to be absorbed, and queues form and take a long time to drain.

Two refinements matter for networks. Determinism helps: with fixed-size packets and a fixed service rate, an M/D/1 queue has exactly half the waiting time of M/M/1 at the same utilisation, which is part of why fixed-size cells were attractive historically. And burstiness hurts: real traffic is burstier than Poisson, so M/M/1 is an optimistic bound, not a pessimistic one, which is the subject of the self-similarity topic below.

This is where the conventional 70–80% utilisation target comes from. It is not a safety margin invented by cautious engineers; it is the point beyond which the curve turns upward steeply enough that small forecasting errors produce large latency errors.

Finally, queueing theory explains bufferbloat. A queue's job is to absorb bursts, but a queue that is too large stops dropping packets and instead stores them, converting a signal that congestion control understands — loss — into delay that it does not. TCP fills the buffer, and every flow sharing it inherits the resulting latency. The correct buffer is large enough to absorb genuine bursts and small enough that a standing queue cannot form, which is what active queue management schemes such as CoDel and FQ-CoDel enforce by watching how long packets have been waiting rather than how many there are.

Examples

# A 1 Gb/s link, 1500-byte packets: service time is fixed by physics.
LINK_BPS, PKT_BITS = 1_000_000_000, 1500 * 8
service_us = PKT_BITS / LINK_BPS * 1e6            # 12 us to clock one packet out
mu = 1e6 / service_us                             # packets per second the link can serve

print(f"service time = {service_us:.0f} us/packet, mu = {mu:,.0f} pps\n")
print(f"{'load':>6s} {'M/M/1 wait':>12s} {'M/D/1 wait':>12s} {'queue (L)':>10s} {'vs 10%':>8s}")
base = None
for rho in (0.10, 0.50, 0.70, 0.80, 0.90, 0.95, 0.99, 0.999):
    lam = rho * mu
    w_mm1 = rho / (mu - lam) * 1e6                # mean time WAITING in queue, us
    w_md1 = w_mm1 / 2                             # deterministic service halves it
    L = lam * (w_mm1 / 1e6)                       # Little's Law: packets in queue
    base = base or w_mm1
    print(f"{rho*100:5.1f}% {w_mm1:9.1f} us {w_md1:9.1f} us {L:10.1f} {w_mm1/base:7.0f}x")

# --- Little's Law the other way round: sizing a connection pool ---
print("\nLittle's Law, L = lambda * W, applied to a connection pool:")
for tps, ms in ((2_000, 25), (2_000, 40), (5_000, 25), (5_000, 120)):
    print(f"  {tps:5d} req/s x {ms:3d} ms = {tps * ms / 1000:5.0f} connections in flight")

# service time = 12 us/packet, mu = 83,333 pps
#
#   load   M/M/1 wait   M/D/1 wait  queue (L)   vs 10%
#  10.0%       1.3 us       0.7 us        0.0       1x
#  50.0%      12.0 us       6.0 us        0.5       9x
#  70.0%      28.0 us      14.0 us        1.6      21x
#  80.0%      48.0 us      24.0 us        3.2      36x
#  90.0%     108.0 us      54.0 us        8.1      81x
#  95.0%     228.0 us     114.0 us       18.0     171x
#  99.0%    1188.0 us     594.0 us       98.0     891x
#  99.9%   11988.0 us    5994.0 us      998.0    8991x
#
# Read the last column. Going from 10% to 80% load costs 36x the queueing delay;
# going from 80% to 99% costs another 25x on top. The link is "not full" in both
# cases. This is why the trigger for adding capacity is 70-80%, not 100%.
#
# Little's Law, L = lambda * W, applied to a connection pool:
#    2000 req/s x  25 ms =    50 connections in flight
#    2000 req/s x  40 ms =    80 connections in flight
#    5000 req/s x  25 ms =   125 connections in flight
#    5000 req/s x 120 ms =   600 connections in flight

Delay against utilisation: the shape worth memorising

  delay
    ^                                                     |
    |                                                    |
    |                                                   /
    |                                                  /
    |                                              __/
    |                                         ____/
    |                          ______________/
    |______________________----
    +----+----+----+----+----+----+----+----+----+----+--> utilisation
     0   10   20   30   40   50   60   70   80   90  100%
                                        ^
                                        |
                        act here, where the curve turns.
                        Waiting for 100% means the link has
                        been unusable for a long time first.

Key Takeaways

• Little's Law (L = lambda x W) holds universally and lets you compute items in flight from throughput and latency, for queues, pools, and people.
• Delay under load is hyperbolic, not linear. The denominator mu - lambda approaching zero is the whole story.
• The measured jump from 10% to 80% load was 36 times the queueing delay, and 80% to 99% cost another 25 times on top.
• Determinism halves queueing delay (M/D/1 versus M/M/1); burstier-than-Poisson traffic makes it worse, so M/M/1 is an optimistic bound.
• The 70–80% capacity trigger is derived from the curve's shape, not from caution.
• Utilisation and delay must be read together. A link at 95% is "not full" and already slow.
• Bufferbloat is a queueing pathology: oversized buffers convert loss, which congestion control understands, into delay, which it does not. Use AQM.

🧪 Practice

1. A service sustains 800 requests per second at 120 ms average latency. Compute the average number of requests in flight and state the minimum viable thread pool size.
2. Using the M/M/1 formula, compute the ratio of queueing delay at 90% utilisation to that at 60% on the same link.
3. A 10 Gb/s interface has a 100 ms buffer. Compute how many 1500-byte packets that is, and explain what a single greedy TCP flow does to every other flow sharing it.
4. Interview-style: A link averages 45% utilisation over five-minute samples, and users report severe latency several times an hour. (Hint: the average and the queue respond to different timescales — ask what the utilisation looks like at 10 ms granularity and what happens to the mean when you smooth over five minutes.)

Network Simulation and Emulation Tools

Theory

You cannot test a routing change on the production network, you cannot buy forty routers to reproduce a customer's topology, and you cannot wait for a real congestion event to study one. The alternatives fall into three families, and choosing wrongly wastes weeks.

Simulation models the network in software with a virtual clock. There is no real traffic and no real protocol stack; there are events on a timeline and models of how components behave. ns-3 and OMNeT++ are the standard tools. The strengths are decisive for research: perfect repeatability (the same seed gives the same result exactly), arbitrary scale (a hundred thousand nodes if you have memory), and the ability to run faster or slower than real time while observing any variable. The weakness is equally decisive: you are studying a model. If the model of TCP differs from the TCP in Linux 6.x, results about TCP behaviour may not transfer.

Emulation runs real software over an artificially impaired or virtualised network. Mininet creates real Linux network namespaces connected by virtual links; Containerlab does the same with containerised vendor network operating systems; GNS3 and EVE-NG run real router images; tc netem applies delay, loss, and reordering to any interface. Here the protocol stacks are genuine, so a bug in a real implementation will appear. The costs are that everything runs in real time, results vary between runs, and fidelity is bounded by the host: a laptop cannot faithfully emulate 40 Gb/s, and above a few gigabits the measurements reflect the host's scheduler rather than the network being modelled.

Testbeds use real hardware, either a shared facility or a lab of the actual devices. Fidelity is total, because it is the real thing. Scale, cost, and availability are the constraints, and reconfiguration is slow.

Family	Stack	Time	Repeatable	Scale	Best for
Simulation	Modelled	Virtual	Exactly	Very large	Protocol research, parameter sweeps
Emulation	Real	Real	Approximately	Moderate	Config validation, application behaviour
Testbed	Real	Real	Approximately	Small, costly	Final validation, hardware-specific effects

Two rules cover most mistakes. Validate the model of the thing you are studying. If the question is about a congestion control algorithm, the simulated TCP must match the real one, and the honest approach is to reproduce a known measurement before trusting a novel one. And know which layer your tool is faithful to: netem reproduces delay and loss convincingly but does not reproduce a router's queueing discipline, buffer sizing, or the way a real ECMP hash distributes flows.

For everyday network engineering, emulation is the workhorse. Reproducing a customer's WAN characteristics locally with netem takes one command and turns "it is slow for the Sydney office" into something that can be debugged at your desk.

Examples

# --- Emulate a WAN path on a local interface with tc netem ---
# 80 ms mean delay, +/-10 ms jitter, correlated 25% (successive delays are related)
sudo tc qdisc add dev eth0 root netem delay 80ms 10ms 25%

# Add realistic impairment: 0.1% loss, 0.05% corruption, 0.2% reordering
sudo tc qdisc change dev eth0 root netem \
     delay 80ms 10ms 25% loss 0.1% corrupt 0.05% reorder 0.2% 50%

# Shape to a fixed rate with a bounded queue -- this is what creates CONGESTION.
# netem delay alone models propagation; it does not model a full buffer.
sudo tc qdisc change dev eth0 root netem rate 10mbit limit 1000

sudo tc -s qdisc show dev eth0      # verify: packets, drops, requeues
sudo tc qdisc del dev eth0 root     # always remove it; this rule outlives your shell

#!/usr/bin/env python3
"""Mininet: a real Linux TCP stack over a lossy, high-latency virtual link."""
from mininet.net import Mininet
from mininet.link import TCLink          # TCLink exposes bw/delay/loss per link
from mininet.topo import Topo

class WanTopo(Topo):
    def build(self):
        h1, h2 = self.addHost('h1'), self.addHost('h2')
        s1 = self.addSwitch('s1')
        self.addLink(h1, s1, cls=TCLink, bw=100, delay='1ms')        # LAN side
        self.addLink(h2, s1, cls=TCLink, bw=10, delay='90ms',
                     loss=0.5, max_queue_size=100)                   # WAN side

net = Mininet(topo=WanTopo(), link=TCLink)
net.start()
h1, h2 = net.get('h1'), net.get('h2')
print(h1.cmd('ping -c 4 %s' % h2.IP()))          # confirms the 180 ms RTT
h2.cmd('iperf3 -s -D')                            # real iperf3, real kernel TCP
print(h1.cmd('iperf3 -c %s -t 20 -C cubic' % h2.IP()))
print(h1.cmd('iperf3 -c %s -t 20 -C bbr' % h2.IP()))   # compare on the SAME path
net.stop()
# The comparison is the point: two real congestion control implementations,
# one reproducible path, measured by the tool you would use in production.

Key Takeaways

• Simulation models the network; emulation runs real software over an impaired one; a testbed is the real thing. Pick by which fidelity you need.
• Simulation gives exact repeatability and unlimited scale, at the cost of studying a model rather than an implementation.
• Emulation gives genuine protocol stacks, bounded by the host's capacity. Do not trust multi-gigabit results from a laptop.
• Validate the model of what you are studying by reproducing a known measurement before trusting a new one.
• netem models propagation, not congestion. Add a rate limit and a queue limit before drawing conclusions about buffers or loss.
• tc rules persist beyond your shell session. Remove them explicitly, and never test this on a remote box without a scheduled rollback.
• For day-to-day engineering, emulation reproduces a remote site's conditions locally and turns a vague report into a debuggable case.

🧪 Practice

1. Write the tc netem command for a satellite path: 600 ms RTT, 20 ms jitter, 1% loss. State which side of the interface it applies to and how to remove it.
2. Choose a tool family for each: comparing CUBIC and BBR at 300 nodes, validating a BGP policy across 6 routers, and measuring a specific switch's buffer behaviour. Justify each choice.
3. Using netem, reproduce a path with 200 ms RTT and 0.5% loss, then measure single-stream TCP throughput. Compare it to the bandwidth-delay product prediction.
4. Interview-style: A simulation shows a new congestion control algorithm achieving 40% higher throughput; in production it is slightly worse. (Hint: ask what the simulated competing traffic looked like, and whether the algorithm was ever sharing a bottleneck with flows that behave differently from itself.)

Traffic Characterization and Self-Similarity

Theory

For decades, network traffic was modelled as a Poisson process, borrowed from telephony where it worked well. The Poisson model makes a strong and convenient prediction: aggregate enough independent sources and the traffic smooths out. Variability should fall as one over the square root of the aggregation timescale, so a link busy at millisecond granularity should look nearly constant over ten seconds.

In 1993 a careful measurement study of Ethernet traffic at Bellcore found that it does not. Plot real traffic at 10 ms, 1 s, 10 s, and 100 s resolution and the graphs look statistically similar at every scale — the bursts do not average away, they merely change units. This property is called self-similarity, and the associated long-range dependence means that activity now is correlated with activity a long time ago, unlike a Poisson process where each instant is independent.

The degree is summarised by the Hurst parameter H. At H = 0.5 the process has no memory and behaves as the classical model predicts. As H rises towards 1, bursts persist across timescales and aggregation stops helping. Measured network traffic typically lands between 0.7 and 0.9.

Why it happens is more interesting than the statistic. The cause is heavy-tailed session sizes. Most transfers are tiny and a few are enormous, and the distribution of file sizes follows a power law with infinite variance rather than a distribution with a well-behaved mean spread. Model each user as an ON/OFF source whose ON and OFF durations are drawn from such a distribution, aggregate many of them, and the result is provably self-similar. The long transfers create correlation that spans minutes, so no amount of aggregation washes them out. The analogy is a motorway: individual cars average out, but a single broken-down lorry creates a disturbance that persists long after it is removed, and if breakdown durations are heavy-tailed, the road never looks smooth at any timescale.

The engineering consequences are concrete and mostly unwelcome.

Buffers overflow far more often than Poisson analysis predicts, because sustained bursts arrive rather than independent arrivals. Queue length distributions decay sub-exponentially, so the tail is much fatter, and doubling buffer size reduces loss far less than the classical model suggests. Since buffers buy less, bandwidth headroom is the effective remedy, which links directly to the 70–80% trigger from the queueing topic.

It also means averages are the wrong summary. A link averaging 45% can spend meaningful time saturated, and reporting means hides exactly the behaviour that causes user-visible pain. Capacity work should use peaks and high percentiles, and the retention decision about what to keep in long-term monitoring data should preserve them.

The same heavy tail appears in flow sizes, where it is described as mice and elephants: the overwhelming majority of flows are small and the minority of large flows carry most of the bytes. This has direct operational consequences, since per-flow hashing distributes flow counts evenly but not bytes, so a link bundle can be badly imbalanced while every hash bucket holds the same number of flows.

Examples

import random, math, statistics
random.seed(3)
BINS = 100_000                                   # 10 ms bins -> ~17 minutes of traffic

# --- Model A: Poisson arrivals, the classical assumption ---
poisson = [sum(1 for _ in range(20) if random.random() < 0.5) for _ in range(BINS)]

# --- Model B: 800 ON/OFF sources with heavy-tailed (Pareto) durations ---
def pareto(alpha, xm=1.0):
    return xm / (random.random() ** (1.0 / alpha))   # infinite variance for alpha < 2
selfsim = [0.0] * BINS
for _ in range(800):
    t, on = 0, random.random() < 0.5
    while t < BINS:
        dur = int(pareto(1.2))
        for b in range(t, min(t + dur, BINS)):
            if on:
                selfsim[b] += 1                      # this source is transmitting
        t += max(dur, 1)
        on = not on                                  # alternate ON and OFF

def cv_at_scale(series, m):
    """Coefficient of variation after aggregating m bins into one."""
    agg = [sum(series[i:i+m]) / m for i in range(0, len(series) - m + 1, m)]
    return statistics.pstdev(agg) / statistics.mean(agg)

print(f"{'timescale':>11s} {'Poisson CV':>11s} {'smoothed':>9s} "
      f"{'self-similar CV':>16s} {'smoothed':>9s}")
c0p, c0s = cv_at_scale(poisson, 1), cv_at_scale(selfsim, 1)
for m, label in ((1, "10 ms"), (10, "100 ms"), (100, "1 s"), (1000, "10 s"), (10000, "100 s")):
    cp, cs = cv_at_scale(poisson, m), cv_at_scale(selfsim, m)
    print(f"{label:>11s} {cp:11.4f} {c0p/cp:8.0f}x {cs:16.4f} {c0s/cs:8.1f}x")
# Estimate H from the slope of log(CV) against log(m):  CV ~ m^(H-1)
slope = (math.log(cv_at_scale(selfsim, 10000)) - math.log(c0s)) / math.log(10000)
print(f"\nestimated Hurst parameter H = {1 + slope:.2f}   (0.5 = no memory, ->1 = strong)")

#   timescale  Poisson CV  smoothed  self-similar CV  smoothed
#       10 ms      0.2236        1x           0.0353      1.0x
#      100 ms      0.0708        3x           0.0277      1.3x
#         1 s      0.0243        9x           0.0225      1.6x
#        10 s      0.0074       30x           0.0166      2.1x
#       100 s      0.0019      116x           0.0090      3.9x
#
# estimated Hurst parameter H = 0.85   (0.5 = no memory, ->1 = strong)
#
# Compare the two "smoothed" columns, which is where the whole argument lives.
# Aggregating 10 000-fold smooths the Poisson series by 116x -- exactly the
# square-root law. The same aggregation smooths the heavy-tailed series by less
# than 4x. Burstiness that does NOT average away is what breaks buffer sizing
# derived from Poisson assumptions.

The same traffic at four resolutions (self-similar: the shape repeats)

  10 ms  |#  ##_#   #### _##  #_#  ####   _#  ###|   bursty
   1 s   |#  ##_#   #### _##  #_#  ####   _#  ###|   still bursty
  10 s   |#  ##_#   #### _##  #_#  ####   _#  ###|   still bursty
 100 s   |#  ##_#   #### _##  #_#  ####   _#  ###|   still bursty

  Poisson traffic, for contrast:

  10 ms  |#_##__#_#__##_#__#_##__#_#__##__#_#_##_|   bursty
   1 s   |######################################_|   smoothing
  10 s   |#######################################|   flat
 100 s   |#######################################|   flat

Key Takeaways

• Real traffic is self-similar: burstiness persists across timescales instead of averaging away as the Poisson model predicts.
• The Hurst parameter summarises it. H = 0.5 means no memory; measured traffic is typically 0.7 to 0.9, and the example measured 0.85.
• The cause is heavy-tailed transfer sizes. Many ON/OFF sources with power-law durations aggregate into long-range dependence.
• Aggregating 10,000-fold smoothed Poisson traffic 116 times over and heavy-tailed traffic less than 4 times.
• Buffers help less than classical analysis suggests, because queue-length tails decay sub-exponentially. Headroom beats buffering.
• Report peaks and percentiles, not means. A 45% average link can still saturate, and the mean is built to hide that.
• Mice and elephants: most flows are small, most bytes are in a few large ones, so equal flow counts per hash bucket does not mean equal load.

🧪 Practice

1. Using one hour of interface counters at 10-second resolution, compute the coefficient of variation at 10 s, 1 min, and 10 min. State whether the decay matches the square-root law.
2. Explain why a link averaging 45% over five minutes can drop packets, and name the two graphs you would produce to prove it to a sceptical colleague.
3. Two 10 Gb/s links in a bundle carry 4000 flows each, yet one is at 82% and the other at 31%. Explain the mechanism and give two remedies.
4. Interview-style: A buffer is doubled to cut packet loss; loss falls by only a few percent while latency rises noticeably. (Hint: two separate effects are in play — how the queue-length tail decays under bursty traffic, and what a larger buffer does to packets that are not dropped.)

<a id="153-frontier-directions"></a>

15.3 Frontier Directions

The remaining topics are unsettled: some are research directions that may never deploy, some are already shipping and changing assumptions you rely on, and one is not technical at all but determines what the others are permitted to do. This subchapter covers naming content instead of hosts, networking where no end-to-end path exists, orbital infrastructure, the cryptographic migration already under way, machine learning in operations, and the governance that decides the rules.

Information-Centric Networking

Theory

IP addresses name locations. Almost every use of the Internet is about content. When you request a news article you do not care which machine serves it, yet the protocol forces you to name one, then forces the network to deliver your packets to that specific machine even if an identical copy sits on the router one hop away.

The workarounds for this mismatch are enormous and familiar: content delivery networks, DNS-based request steering, HTTP caching, anycast, and application-layer replication all exist to reintroduce location independence on top of a protocol that removed it. Information-Centric Networking asks what the architecture would look like if content were named natively.

In Named Data Networking, the best developed design, packets carry names rather than addresses. A consumer sends an Interest for a name such as /bbc/news/2026-09-24, and the network forwards it towards any source that can satisfy it. The Data packet returns along the reverse path, and every router along the way may cache it. Each router keeps three structures:

• Content Store: a cache of Data packets. A hit answers the Interest immediately.
• Pending Interest Table: records Interests already forwarded. A second Interest for the same name is aggregated, not forwarded, and one returning Data satisfies all waiters.
• Forwarding Information Base: maps name prefixes to next hops, using longest-prefix match on name components exactly as IP does on address bits.

Three properties follow without extra machinery. Caching is native rather than an overlay. Multicast is automatic, because Interest aggregation means simultaneous requesters are served by a single upstream fetch. And security attaches to the data, not the channel: every Data packet is signed by its producer, so a consumer can verify authenticity regardless of who handed it over. That is a genuinely different trust model from TLS, which authenticates the connection and then trusts whatever arrives on it.

The unsolved problems are serious. Routing on names does not obviously scale: IP's routing table is bounded by an address space with aggregatable structure, while content names are unbounded and arbitrary. Per-Interest state in the Pending Interest Table means routers hold state proportional to in-flight requests, which is a denial-of-service target and the opposite of IP's stateless forwarding. Caching leaks privacy, since response time reveals what neighbours have requested. And signature verification at line rate is expensive.

The pragmatic objection is the strongest one. CDNs already deliver most of ICN's benefits over unmodified IP, incrementally and profitably, and no operator can deploy ICN partially and gain anything. Its most likely influence is therefore indirect: the ideas about data-centric security and in-network caching reappear inside other designs, even if Interest packets never cross a backbone.

Examples

class NDNRouter:
    def __init__(self, name, fib):
        self.name = name
        self.fib = fib          # name prefix -> next-hop router
        self.cs = {}            # Content Store: cached Data, keyed by full name
        self.pit = {}           # Pending Interest Table: name -> list of requesters
        self.upstream_sent = 0

    def interest(self, name, requester, net):
        if name in self.cs:                              # 1. Content Store hit
            print(f"  {self.name}: CS hit for {name} -> answer {requester} directly")
            return self.cs[name]
        if name in self.pit:                             # 2. already pending: AGGREGATE
            self.pit[name].append(requester)
            print(f"  {self.name}: PIT hit for {name}, {requester} added, nothing sent upstream")
            return None
        self.pit[name] = [requester]                     # 3. forward using the FIB
        nh = next(h for p, h in self.fib.items() if name.startswith(p))
        self.upstream_sent += 1
        print(f"  {self.name}: forwarding {name} upstream to {nh}")
        data = net[nh].interest(name, self.name, net)
        if data:
            self.cs[name] = data                         # cache on the way back
            for r in self.pit.pop(name):
                print(f"  {self.name}: returning {name} to {r}")
        return data

class Producer(NDNRouter):
    def interest(self, name, requester, net):
        print(f"  {self.name}: PRODUCER signs and returns {name}")
        return f"<data {name}, signed by {self.name}>"

net = {"R1": NDNRouter("R1", {"/bbc/news": "R2"}),
       "R2": NDNRouter("R2", {"/bbc/news": "P"}),
       "P":  Producer("P", {})}

print("consumer A asks for /bbc/news/2026-09-24:")
net["R1"].interest("/bbc/news/2026-09-24", "A", net)
print("\nconsumer B, behind the same R1, asks for the SAME name:")
net["R1"].interest("/bbc/news/2026-09-24", "B", net)
print(f"\nupstream requests made by R1: {net['R1'].upstream_sent} for 2 consumers")

# consumer A asks for /bbc/news/2026-09-24:
#   R1: forwarding /bbc/news/2026-09-24 upstream to R2
#   R2: forwarding /bbc/news/2026-09-24 upstream to P
#   P: PRODUCER signs and returns /bbc/news/2026-09-24
#   R2: returning /bbc/news/2026-09-24 to R1
#   R1: returning /bbc/news/2026-09-24 to A
#
# consumer B, behind the same R1, asks for the SAME name:
#   R1: CS hit for /bbc/news/2026-09-24 -> answer B directly
#
# upstream requests made by R1: 1 for 2 consumers
#
# B's request never left R1, and nothing had to be configured to make that
# happen -- no CDN, no cache-control header, no DNS steering. The signature on
# the Data is what lets B trust a copy that came from a router, not a server.

IP versus NDN for the same request

  IP:   client --GET /article--> [CDN edge] --> [origin]
        The client must first resolve a NAME to an ADDRESS, then the network
        must deliver to THAT address. The copy on the router next door is
        unreachable because it is not the address you asked for.

  NDN:  client --Interest /bbc/news/2026-09-24--> R1 --> R2 --> producer
                <----------------- Data (signed) ---------------+
        R1 and R2 both cache it. The NEXT consumer behind R1 is served from R1.
        Trust comes from the producer's signature on the Data, so it does not
        matter that R1, not the producer, handed it over.

Key Takeaways

• IP names locations; users want content. CDNs, DNS steering, and caching all exist to paper over that mismatch.
• NDN forwards Interests by name and returns signed Data along the reverse path, with every router free to cache.
• The Pending Interest Table aggregates duplicate requests, which makes multicast a side effect rather than a feature.
• Security binds to the data, not the channel. A signed Data packet is trustworthy no matter who delivered it.
• The scaling problem is real: content names are unbounded and non-aggregatable, unlike IP prefixes.
• Per-Interest router state reverses IP's stateless forwarding and creates a denial-of-service surface.
• The strongest objection is economic. CDNs already capture most of the benefit incrementally, and ICN offers no partial-deployment gain.

🧪 Practice

1. List three things a CDN does today that NDN would provide natively, and two things a CDN provides that NDN does not address at all.
2. Explain how the Pending Interest Table turns 10,000 simultaneous requests for one live video segment into a single upstream fetch, and where the state lives.
3. Describe a privacy attack that exploits in-network caching, and suggest one mitigation along with what it costs.
4. Interview-style: If data-centric security is better than channel security, why did TLS win? (Hint: consider content that is generated per request and cannot be signed in advance, and ask what caching means for content that is unique to one user.)

Delay-Tolerant Networking

Theory

Every protocol described so far assumes something so basic it is rarely stated: that a contemporaneous end-to-end path exists. TCP's handshake requires the other end to be reachable now. Congestion control adjusts based on feedback that arrives within a round trip. Routing computes a path over links that are currently up.

Remove that assumption and the entire stack fails. A probe orbiting Mars has no path to Earth for hours at a time because a planet is in the way. A sensor in a remote valley has connectivity when a vehicle drives past. A village has a satellite uplink for two hours a day. In each case links exist, but never simultaneously along the whole route.

Delay- and Disruption-Tolerant Networking replaces end-to-end assumptions with store-carry-forward. A node accepts a message, stores it durably, carries it until a next hop becomes available, and then forwards it. The unit is not a packet but a bundle: a self-contained message with enough metadata to be routed and delivered independently, standardised as Bundle Protocol version 7 in RFC 9171.

Four design differences follow directly:

Storage is a routing resource. In IP, a router that cannot forward immediately drops the packet. In DTN, it stores it, possibly for hours, so persistent storage capacity determines how much disruption the network can absorb.

Custody transfer replaces end-to-end retransmission. Retransmitting from the original sender across a 40-minute round trip is unacceptable, so a node can accept custody, taking responsibility for onward delivery and allowing the previous hop to free its copy.

Names are bound late. A destination is an endpoint identifier resolved as the bundle travels, because resolving it at the source assumes a directory that may be many hours away.

Routing uses schedules, not discovery. Orbital mechanics are deterministic, so contacts between nodes are known in advance from ephemerides. Contact Graph Routing computes forwarding decisions over a time-varying graph of scheduled contacts, choosing paths that will exist rather than paths that do.

Beneath the bundle layer, convergence layers adapt to each link type. For deep space the Licklider Transmission Protocol handles long-delay retransmission, since TCP's timers are meaningless when a round trip is 40 minutes. Note also what must be discarded: chatty handshakes, window-based flow control driven by acknowledgements, and interactive negotiation of any kind. A DTN application sends a complete, self-describing request and waits, in the manner of postal mail rather than conversation.

Terrestrial uses exist too — disaster response where infrastructure is destroyed, military tactical networks, rural connectivity via scheduled vehicle transport, and wildlife sensors that offload when animals pass a base station. Anywhere that intermittent contact is normal rather than exceptional, the same architecture applies.

Examples

C_KM_S = 299_792.458
LINKS = {                       # one-way distance in km
    "London -> New York (fibre)": 5_570 * 1.47,      # 1.47 = refractive index of glass
    "Earth -> Moon":            384_400,
    "Earth -> Mars (closest)":  54_600_000,
    "Earth -> Mars (farthest)": 401_000_000,
    "Earth -> Voyager 1":       24_500_000_000,
}
MSS, PAYLOAD = 1448, 1_000_000_000               # 1 GB to transfer
def slow_start_rounds(payload):
    sent, cwnd, rounds = 0, 10, 0                # RFC 6928 initial window of 10 segments
    while sent < payload:
        sent += cwnd * MSS
        cwnd *= 2                                # one doubling per RTT
        rounds += 1
    return rounds

print(f"{'link':28s} {'one-way':>12s} {'RTT':>12s} {'TCP+TLS setup':>15s} {'1 GB ramp-up':>14s}")
for name, km in LINKS.items():
    owl = km / C_KM_S
    rtt = 2 * owl
    setup = 2.5 * rtt                            # ~1.5 RTT TCP + 1 RTT TLS 1.3
    ramp = slow_start_rounds(PAYLOAD) * rtt
    def fmt(s):
        if s < 1:    return f"{s*1000:8.0f} ms"
        if s < 3600: return f"{s:8.1f} s"
        return f"{s/3600:8.1f} h"
    print(f"{name:28s} {fmt(owl):>12s} {fmt(rtt):>12s} {fmt(setup):>15s} {fmt(ramp):>14s}")
print(f"\n(slow start alone needs {slow_start_rounds(PAYLOAD)} round trips for 1 GB)")

# link                              one-way          RTT   TCP+TLS setup   1 GB ramp-up
# London -> New York (fibre)          27 ms        55 ms          137 ms         929 ms
# Earth -> Moon                       1.3 s        2.6 s           6.4 s         43.6 s
# Earth -> Mars (closest)           182.1 s      364.3 s         910.6 s          1.7 h
# Earth -> Mars (farthest)         1337.6 s     2675.2 s           1.9 h         12.6 h
# Earth -> Voyager 1                 22.7 h       45.4 h         113.5 h        771.8 h
#
# (slow start alone needs 17 round trips for 1 GB)
#
# At Mars, the TCP+TLS handshake costs 15 MINUTES before one byte of payload
# moves, and slow start spends 1.7 hours ramping. Neither is a tuning problem:
# both are protocols asking a question and waiting for an answer, across a gap
# where every question costs six minutes. DTN removes the questions.

Contact Graph Routing: forward over contacts that WILL exist

  time ->   0h    2h    4h    6h    8h   10h   12h
  Mars rover  [==A==]              [==A==]              contact with orbiter
  Orbiter           [=====B=====]        [=====B=====]  contact with Earth DSN
  Earth DSN                  |                 |

  A bundle generated at t=1h:
    t=1h  rover -> orbiter        (contact A is open now)
    t=2h  orbiter STORES it       (no contact with Earth yet; this is normal)
    t=3h  orbiter -> Earth        (contact B opens; forward)

  There was never an end-to-end path. IP routing would have found no route and
  dropped the packet at t=1h. CGR planned across time instead of across space.

Key Takeaways

• DTN drops the assumption that an end-to-end path exists at one moment, which is what every conventional protocol depends on.
• The mechanism is store-carry-forward over self-contained bundles (Bundle Protocol v7, RFC 9171), not packets.
• Storage is a routing resource. A node that cannot forward stores rather than drops, so capacity bounds tolerable disruption.
• Custody transfer moves retransmission responsibility hop by hop, because end-to-end retransmission over a 40-minute round trip is unusable.
• Contact Graph Routing plans over time, using predictable orbital schedules instead of discovering currently-live links.
• Handshakes and acknowledgement-driven flow control must go. At Mars, TCP and TLS setup alone costs about 15 minutes before any payload moves.
• The same architecture serves terrestrial intermittent connectivity: disaster zones, tactical networks, rural relays, and wildlife sensors.

🧪 Practice

1. Compute the one-way light time to a spacecraft 1.2 billion km away, and state how many TCP round trips would fit into a 24-hour period.
2. Explain why custody transfer is essential in DTN and describe what a custodian must do if the next hop never becomes available.
3. Given contact windows Earth–Relay 00:00–02:00 and Relay–Rover 03:00–04:00, give the earliest delivery time for a bundle created at 01:30 and name the resource it consumes meanwhile.
4. Interview-style: Why can DTN not simply be TCP with much larger timeout values? (Hint: enumerate every point in a TCP connection at which one side must wait for the other before it may proceed, and ask which of them a timer can remove.)

Satellite Constellations and LEO Networks

Theory

Satellite Internet has a long reputation for being slow, and the reputation was earned by geostationary orbit. A GEO satellite sits 35,786 km above the equator, which is what makes it appear motionless and lets a dish point at it permanently. That distance costs roughly 120 ms each way, so a round trip through the satellite is about 480 ms before any processing. No protocol tuning removes it, because it is the speed of light over a fixed distance.

Low Earth Orbit changes the arithmetic by changing the distance. At 550 km, the round trip to the satellite and back is about 7 ms. That is the difference between satellite links being unusable for interactive work and being ordinary.

The price is that a LEO satellite does not stay put. At 550 km it orbits in about 95 minutes, moving at roughly 7.6 km/s, so it is visible from a given point on the ground for only a few minutes. Continuous service therefore requires thousands of satellites and a handover every few minutes, and each handover is a path change: the route shifts, the round-trip time steps, and packets can be lost or reordered.

There is a second, less obvious advantage. Light travels through optical fibre at roughly two-thirds of its vacuum speed, because glass has a refractive index near 1.47. It also travels a longer route, since cables follow coastlines, rights of way, and existing ducts rather than great circles. A constellation with inter-satellite laser links routes through vacuum along something much closer to the direct path, so for long distances LEO can beat terrestrial fibre on latency — which is why the financial-trading interest in these networks is not a marketing story.

The networking consequences are genuinely new problems:

Routing is a continuously changing graph that is nonetheless predictable. Every satellite's position is known in advance from orbital mechanics, so routes can be precomputed on a schedule rather than converged reactively. This resembles the contact graph routing of the previous topic, applied at seconds rather than hours.

Congestion control is confused by handovers. The round-trip time varies in a sawtooth as a satellite recedes and a new one is acquired, and the handover itself can cause loss. Loss-based algorithms such as CUBIC interpret that as congestion and reduce the window when nothing was congested. Algorithms that model the path, such as BBR, cope better, but rapidly varying minimum RTT is difficult for any of them.

Ground segment and weather remain. Ka and Ku band links suffer rain fade, gateway capacity limits throughput regardless of the space segment, and terminal cost and power draw are real constraints.

Non-technical constraints are becoming binding. Spectrum coordination, orbital debris, collision avoidance between constellations, and the effect of large constellations on ground-based astronomy are all now subjects of regulation, and they will shape what is deployable as much as engineering does.

Examples

import math
C, RE, MU = 299_792.458, 6_371.0, 398_600.4418   # km/s, Earth radius km, GM km^3/s^2
FIBRE_C = C / 1.47                                # light in glass: ~204,000 km/s

print(f"{'orbit':>8s} {'alt km':>8s} {'RTT bent-pipe':>15s} {'period':>9s} {'pass @25deg':>12s}")
for name, alt in (("LEO", 550), ("LEO", 1200), ("MEO", 8000), ("GEO", 35786)):
    r = RE + alt
    rtt = 4 * alt / C * 1000                      # up+down, there and back, straight overhead
    period = 2 * math.pi * r / math.sqrt(MU / r) / 60          # orbital period, minutes
    theta = math.degrees(math.acos(RE / r * math.cos(math.radians(25)))) - 25
    pass_min = 2 * theta / 360 * period           # how long one satellite stays usable
    per = "stationary" if alt > 35000 else f"{period:6.1f} min"
    pas = "always up" if alt > 35000 else f"{pass_min:6.1f} min"
    print(f"{name:>8s} {alt:8d} {rtt:12.1f} ms {per:>9s} {pas:>12s}")

# --- Long-haul: vacuum beats glass, and the route is shorter too ---
GREAT_CIRCLE = 16_983                             # London to Sydney, km
print(f"\nLondon -> Sydney, {GREAT_CIRCLE} km great circle:")
fibre_km = GREAT_CIRCLE * 1.4                     # real cables are not great circles
print(f"  terrestrial fibre : {fibre_km:7.0f} km of glass -> "
      f"{fibre_km / FIBRE_C * 2 * 1000:6.1f} ms RTT")
isl_km = GREAT_CIRCLE + 2 * 550                   # up, across by laser, back down
print(f"  LEO laser mesh    : {isl_km:7.0f} km of vacuum -> "
      f"{isl_km / C * 2 * 1000:6.1f} ms RTT")
print(f"  GEO bent pipe     : {4 * 35786:7.0f} km of vacuum -> "
      f"{4 * 35786 / C * 1000:6.1f} ms RTT")

#    orbit   alt km   RTT bent-pipe    period  pass @25deg
#      LEO      550          7.3 ms   95.5 min      4.5 min
#      LEO     1200         16.0 ms  109.3 min      9.3 min
#      MEO     8000        106.7 ms  285.8 min     65.6 min
#      GEO    35786        477.5 ms stationary    always up
#
# London -> Sydney, 16983 km great circle:
#   terrestrial fibre :   23776 km of glass ->  233.2 ms RTT
#   LEO laser mesh    :   18083 km of vacuum ->  120.6 ms RTT
#   GEO bent pipe     :  143144 km of vacuum ->  477.5 ms RTT
#
# Two facts in one table. GEO is 65x the LEO round trip, which is the whole
# reason LEO constellations were built. And a LEO mesh beats fibre to Sydney by
# roughly 2x, because glass is slow AND cables do not go in straight lines --
# but the price is a satellite that leaves the sky every 4.5 minutes.

Why a LEO ground terminal never stops handing over

  sky over one terminal, 550 km shell:

   t=0     SAT-A overhead, RTT 7 ms
   t=2m    SAT-A at 40 deg,  RTT 11 ms       RTT RISES as the satellite recedes
   t=4m    SAT-A at 25 deg,  RTT 16 ms       (the sawtooth, climbing)
   t=4.5m  HANDOVER --> SAT-B overhead, RTT 7 ms      (sawtooth resets)

   RTT |    /|    /|    /|    /|        CUBIC sees each handover's loss as
       |   / |   / |   / |   / |        congestion and cuts its window.
       |  /  |  /  |  /  |  /  |        Nothing was congested; a satellite
       | /   | /   | /   | /   |        simply went over the horizon.
       +----------------------------> time
         ^     ^     ^     ^
         handovers, every ~4 minutes, forever

Key Takeaways

• GEO's latency is geometric, about 480 ms round trip from 35,786 km, and no protocol change reduces it.
• LEO at 550 km cuts that to roughly 7 ms, which is what makes satellite links viable for interactive traffic.
• The cost is motion: a satellite is usable for only a few minutes, so continuous coverage needs thousands of them and constant handover.
• Vacuum beats glass. With laser inter-satellite links, a LEO mesh reached Sydney in about half the fibre round trip.
• Constellation topology changes constantly but predictably, so routing can be precomputed from orbital mechanics rather than converged.
• Handovers break loss-based congestion control, which reads handover loss and RTT steps as congestion that never happened.
• Ground segment, weather, spectrum, debris, and astronomy are binding constraints, not footnotes.

🧪 Practice

1. Compute the minimum round-trip time for a bent-pipe link at 340 km and at 1,200 km, and state which applications become viable at each.
2. Explain why a LEO constellation needs inter-satellite links to beat fibre on a London-to-Singapore path, rather than simply relaying via ground stations.
3. A terminal hands over every four minutes and each handover loses three packets. Estimate the effect on a long CUBIC flow, and name a congestion control that copes better and why.
4. Interview-style: A LEO link measures 25 ms RTT and 500 Mb/s in iperf, yet video calls stutter noticeably. (Hint: mean latency is not the metric a real-time codec cares about — ask what the RTT graph looks like across a handover boundary.)

Post-Quantum Cryptography in Transit

Theory

Almost all key exchange on the Internet today rests on a single mathematical assumption: that certain problems, factoring large integers and computing discrete logarithms, are hard. Shor's algorithm shows they are not hard for a sufficiently large quantum computer. No such machine exists publicly today, which makes this sound like a future problem. It is not, for one reason.

Harvest now, decrypt later. An adversary who records encrypted traffic today and stores it can decrypt it whenever a capable quantum computer arrives. Anything whose confidentiality must outlast the machine's arrival is already exposed, and the capture has already happened or not, regardless of what you do later. Medical records, state secrets, legal material, and long-lived credentials all fall into this category. That is why deployment is happening now rather than when the threat materialises.

The damage is not uniform across cryptography, and the distinction matters:

Primitive	Quantum impact	Response
RSA, Diffie-Hellman, ECDH, ECDSA	Broken by Shor's algorithm	Replace entirely
AES-128	Effective strength halved by Grover	Move to AES-256
SHA-256	Preimage strength halved	Move to SHA-384 or SHA-512

So symmetric cryptography survives with larger parameters, and public-key cryptography must be replaced. NIST standardised the replacements in 2024: ML-KEM (FIPS 203, from Kyber) for key encapsulation, ML-DSA (FIPS 204, from Dilithium) and SLH-DSA (FIPS 205, from SPHINCS+) for signatures.

Deployment uses hybrids, deliberately. The new algorithms are young, and a lattice-based scheme could turn out to have a classical weakness nobody has found yet. So TLS 1.3 deployments use a hybrid key exchange such as X25519MLKEM768, which combines the classical and post-quantum shared secrets so that breaking the session requires breaking both. This is already the default in major browsers and CDNs, so a meaningful fraction of web traffic is post-quantum protected today.

The interesting part for a networking course is that this is a packet-size problem. An X25519 key share is 32 bytes; an ML-KEM-768 encapsulation key is 1,184. That pushes the ClientHello past the point where it fits in one packet, so the first flight of the handshake becomes multiple segments. Consequences follow: middleboxes that mishandle a split ClientHello break connections in ways that look like random failures, QUIC's anti-amplification limit restricts what a server may send before validating the client's address, and the first flight interacts with the initial congestion window.

Signatures are the harder half, and migration order reflects that. A certificate chain must carry a public key and a signature per certificate plus a handshake signature, and with ML-DSA-65 that turns a one-packet server flight into eleven packets, which exceeds a standard ten-packet initial window and costs an extra round trip. Key exchange is being migrated first because it addresses harvest-now-decrypt-later, while signature migration can wait until a quantum computer is closer, since forging a signature retroactively does not help an attacker.

The durable lesson is crypto agility: build systems where algorithms can be changed without redesign, because this migration will not be the last one.

Examples

import math
MTU_PAYLOAD = 1400                    # bytes of TLS record that fit in one packet
ALGS = {  # name: (public key / encapsulation key, ciphertext or signature)
    "X25519 (ECDH)":        (32, 32),
    "ML-KEM-768":           (1184, 1088),
    "X25519MLKEM768 hybrid":(1216, 1120),
    "ECDSA P-256":          (64, 72),
    "RSA-2048":             (256, 256),
    "ML-DSA-65":            (1952, 3309),
    "SLH-DSA-128s":         (32, 7856),
}
print(f"{'algorithm':24s} {'public key':>11s} {'ct or sig':>11s} {'vs X25519/ECDSA':>16s}")
for n, (pk, ct) in ALGS.items():
    kem = "KEM" in n or "ECDH" in n or "hybrid" in n
    ratio = (pk + ct) / (64 if kem else 136)      # compare like with like
    print(f"{n:24s} {pk:8d} B {ct:8d} B {ratio:15.0f}x")

# --- What that does to the TLS 1.3 handshake on the wire ---
def flight(label, bytes_):
    pkts = math.ceil(bytes_ / MTU_PAYLOAD)
    note = "" if pkts <= 10 else "  EXCEEDS a 10-packet initcwnd: extra round trip"
    print(f"  {label:34s} {bytes_:6d} B -> {pkts:2d} packet(s){note}")

print("\nClientHello (first flight, client -> server):")
flight("classical, X25519 only", 300 + 64)
flight("hybrid X25519MLKEM768", 300 + 1216)
print("\nServer flight (ServerHello + certificate chain + CertificateVerify):")
flight("ECDSA chain, 2 certs", 2 * (64 + 72 + 400) + 72 + 200)
flight("RSA-2048 chain, 2 certs", 2 * (256 + 256 + 400) + 256 + 200)
flight("ML-DSA-65 chain, 2 certs", 2 * (1952 + 3309 + 400) + 3309 + 200)

# algorithm                 public key   ct or sig  vs X25519/ECDSA
# X25519 (ECDH)                  32 B       32 B               1x
# ML-KEM-768                   1184 B     1088 B              36x
# X25519MLKEM768 hybrid        1216 B     1120 B              36x
# ECDSA P-256                    64 B       72 B               1x
# RSA-2048                      256 B      256 B               4x
# ML-DSA-65                    1952 B     3309 B              39x
# SLH-DSA-128s                   32 B     7856 B              58x
#
# ClientHello (first flight, client -> server):
#   classical, X25519 only                364 B ->  1 packet(s)
#   hybrid X25519MLKEM768                1516 B ->  2 packet(s)
#
# Server flight (ServerHello + certificate chain + CertificateVerify):
#   ECDSA chain, 2 certs                 1344 B ->  1 packet(s)
#   RSA-2048 chain, 2 certs              2280 B ->  2 packet(s)
#   ML-DSA-65 chain, 2 certs            14831 B -> 11 packet(s)  EXCEEDS ...
#
# The KEM migration costs one extra packet in the first flight -- annoying, and
# survivable. The SIGNATURE migration turns a one-packet server flight into
# eleven, which is why key exchange went first and certificates did not.

# Check whether a real connection negotiated a post-quantum group.
openssl s_client -connect cloudflare.com:443 -groups X25519MLKEM768 </dev/null 2>&1 \
  | grep -E 'Negotiated TLS1.3 group|Protocol|Cipher'
# Negotiated TLS1.3 group: X25519MLKEM768      <- hybrid: classical AND ML-KEM

# What the client OFFERS is visible in the ClientHello size; capture the first flight:
sudo tcpdump -i any -n -s0 'tcp port 443 and tcp[tcpflags] & tcp-push != 0' -c 2 -A

# SSH has shipped a hybrid KEX by default for some time:
ssh -Q kex | grep -Ei 'sntrup|mlkem'
# sntrup761x25519-sha512@openssh.com            <- hybrid, on by default

Key Takeaways

• Harvest now, decrypt later makes this urgent today: traffic captured now is decryptable later, so long-lived secrets are already at risk.
• Shor breaks RSA, DH, ECDH, and ECDSA. Grover only halves symmetric strength, so AES-256 and SHA-384 remain adequate.
• The standards are ML-KEM (FIPS 203) for key exchange and ML-DSA / SLH-DSA (FIPS 204/205) for signatures.
• Hybrids are deliberate, not transitional caution: an attacker must break both the classical and the post-quantum half.
• Post-quantum key exchange is already the default in major browsers and CDNs, so real traffic is protected now.
• The networking impact is packet size. The hybrid ClientHello no longer fits in one packet, exposing middlebox and amplification-limit bugs.
• Signatures are the harder migration, turning a one-packet server flight into eleven, which is why key exchange is going first.
• Design for crypto agility. Algorithms must be replaceable without redesigning the system.

🧪 Practice

1. For each, state whether it needs post-quantum protection now and why: a session cookie valid 24 hours, a decade of archived medical records, a TLS server certificate expiring in 90 days.
2. Compute how many 1,400-byte packets a certificate chain of three ML-DSA-87 certificates would need, and state the effect on a 10-packet initial congestion window.
3. Run the openssl s_client command above against three sites you use and record which negotiated a hybrid group.
4. Interview-style: Why deploy hybrid key exchange rather than pure ML-KEM, given that ML-KEM is the NIST standard? (Hint: consider what happens if a classical attack on lattices is published in three years, and what the hybrid construction requires an attacker to do.)

AI-Driven Network Operations

Theory

A modern network emits more telemetry than anyone can read. Streaming telemetry from a few thousand devices produces millions of time series, and the classical response — a static threshold per metric — fails in two directions at once. Thresholds set tightly produce alerts nobody reads, and thresholds set loosely miss the incident. Worse, a fixed threshold cannot express "normal for a Tuesday at 09:00 and alarming at 03:00 on Sunday."

This is a pattern-recognition problem on large volumes of data, which is why machine learning is being applied to it. The useful framing is to separate where it genuinely helps from where it is being oversold.

Where it works well:

• Anomaly detection on multivariate time series, learning normal behaviour including seasonality instead of encoding a threshold by hand.
• Alert correlation, collapsing a storm of two hundred symptom alerts into one probable cause, which addresses the real failure of monitoring systems.
• Forecasting, extending the capacity planning of the previous chapter to many series at once with seasonality handled automatically.
• Traffic classification from flow features such as packet sizes and timing, which still works when payloads are encrypted.
• Failure prediction from slowly degrading signals: optical power drift, rising correctable error counts, fan speed trends.

Where it disappoints, and the reasons are structural rather than fixable by a better model:

The base rate destroys precision. This is the dominant practical problem and it is arithmetic, not opinion. Evaluate five thousand metrics every five minutes and you make over a million decisions a day. Even a false-positive rate of one in ten thousand produces roughly 150 alerts a day against a handful of real incidents, so precision collapses and operators disable the system. A detector's advertised accuracy says almost nothing without the event rate it will run against.

Labels are scarce. Supervised learning needs labelled incidents, and a well-run network produces few. The ones it does produce are inconsistently recorded, which is exactly the argument for the structured incident write-ups from the previous chapter.

Distribution shift is constant. Networks change every week, and a model trained on last quarter's topology is describing a network that no longer exists. Retraining cadence is a permanent operational cost, not a setup step.

Explainability is a gate, not a preference. A change advisory board will not approve an action whose justification is "the model scored it 0.87," and an operator cannot verify a recommendation they cannot inspect.

Feedback loops change the data. Once a model's outputs drive actions, its future training data reflects those actions, and it can learn to prefer what it already did.

Intent-based networking is the adjacent idea: declare the desired outcome, let a system compile it into configuration, and continuously verify that reality matches. The valuable part is the verification, and notably the strongest verification techniques are formal, not learned — tools that prove reachability properties across a whole configuration give guarantees no model can.

The sound approach to closed-loop automation is to bound the blast radius: let automation act freely on reversible, small-scope changes, require human approval for anything destructive or wide, and make every automated action logged and revertible.

Examples

SERIES, WINDOWS_PER_DAY = 5_000, 288          # 5000 metrics, one 5-minute window each
EVALS = SERIES * WINDOWS_PER_DAY              # 1.44M decisions per day
RECALL = 0.95                                 # the model catches 95% of real anomalies

print(f"{EVALS:,} model decisions per day\n")
print(f"{'real events/day':>16s} {'false-positive rate':>20s} {'alerts/day':>11s} "
      f"{'true':>6s} {'precision':>10s}")
for real in (5, 50):
    for fpr in (0.05, 0.01, 0.001, 0.0001, 0.00001):
        tp = real * RECALL
        fp = (EVALS - real) * fpr                 # every NON-event is a chance to be wrong
        precision = tp / (tp + fp) if tp + fp else 0
        print(f"{real:16d} {fpr*100:19.3f}% {tp+fp:11,.0f} {tp:6.1f} {precision*100:9.2f}%")
    print()
print("To reach 90% precision at 5 real events/day the detector needs a")
print(f"false-positive rate below {5*RECALL/9/EVALS*100:.6f}% -- roughly 1 in {EVALS*9/(5*RECALL):,.0f}.")

# 1,440,000 model decisions per day
#
#  real events/day  false-positive rate  alerts/day   true  precision
#                5               5.000%      72,004    4.8      0.01%
#                5               1.000%      14,405    4.8      0.03%
#                5               0.100%       1,445    4.8      0.33%
#                5               0.010%         149    4.8      3.19%
#                5               0.001%          19    4.8     24.80%
#
#               50               5.000%      72,045   47.5      0.07%
#               50               1.000%      14,447   47.5      0.33%
#               50               0.100%       1,487   47.5      3.19%
#               50               0.010%         191   47.5     24.80%
#               50               0.001%          62   47.5     76.74%
#
# To reach 90% precision at 5 real events/day the detector needs a
# false-positive rate below 0.000037% -- roughly 1 in 2,728,421.
#
# A "99% accurate" detector means a 1% false-positive rate, which is row two:
# 14,405 alerts a day, of which 5 are real. The model is not bad; the BASE RATE
# is brutal. This is why aggregation, correlation and suppression matter more
# than detector accuracy, and why per-metric alerting does not scale.

Where to put automation, by blast radius

  reversible  ^
   & narrow   |  [ AUTOMATE FREELY ]        [ AUTOMATE WITH GUARDRAILS ]
              |  restart a process           shift traffic off a link
              |  clear a stale entry         scale a pool up
              |
              |  [ AUTOMATE WITH REVIEW ]   [ HUMAN DECIDES, ALWAYS ]
   permanent  |  re-home a customer          withdraw a BGP prefix
    & wide    |  push a policy change        reload a core device
              +---------------------------------------------------->
                narrow scope                             wide scope

  The axis that matters is not model confidence. It is what happens if the
  model is wrong, and whether the action can be undone without a human.

Key Takeaways

• ML earns its place in anomaly detection, alert correlation, forecasting, encrypted-traffic classification, and failure prediction.
• The base rate is the dominant constraint. At 1.44M decisions a day, a 1% false-positive rate buys 14,405 alerts to find 5 real events.
• Judge a detector by precision at your event rate, never by advertised accuracy.
• Labelled incidents are scarce, which is a direct argument for disciplined, structured incident records.
• Distribution shift is permanent. Every network change ages the model, so retraining is an ongoing cost.
• Explainability is a gate. An unexplainable recommendation will not be approved and cannot be verified by the person on call.
• Intent-based networking's value is verification, and the strongest verification is formal rather than learned.
• Scope automation by blast radius and reversibility, not by model confidence, and log and bound every automated action.

🧪 Practice

1. A detector claims 99.9% accuracy. Running against 800 metrics at one-minute resolution with two real incidents a day, compute the daily alert count and the precision.
2. Classify each as well suited or poorly suited to ML and justify it: predicting optical transceiver failure, choosing which BGP prefix to withdraw during an attack, and grouping 200 alerts into incidents.
3. Describe the retraining and validation process for a production anomaly detector, including how you would detect that the model has gone stale.
4. Interview-style: An automated remediation system fixes a fault, then causes a larger outage an hour later. (Hint: consider what the remediation changed about the inputs the system was reading afterwards, and whether anything bounded how many times it could act.)

Network Neutrality and Internet Governance

Theory

This topic is in a technical guide for a technical reason: the protocols you can deploy, the traffic you may treat differently, and the addresses and names you may use are all determined by rules made outside engineering. An engineer who does not know where those rules come from cannot predict which designs will be permitted.

Network neutrality is the principle that a network should not discriminate among traffic based on its source, destination, application, or sender's willingness to pay. The technical fact underneath the debate is that networks absolutely can discriminate. Deep packet inspection, TLS Server Name Indication, IP address reputation, DSCP marking, per-application shaping, and throttling by flow signature are all standard capabilities. The question was never whether it is possible but whether it is permitted.

The debate turns on distinctions that are easy to blur:

Practice	Description	Typically considered
Reasonable network management	Shaping during genuine congestion, application-agnostic	Acceptable
Paid prioritisation	A content provider pays for preferential treatment	The core dispute
Zero-rating	Some traffic exempt from a data cap	Contested; distorts competition without blocking
Blocking or throttling a competitor	Degrading a rival's service	Almost universally opposed
Interconnection disputes	Congested peering points between networks	Often mislabelled as a neutrality issue

That last row deserves emphasis because it is the most common confusion. Several famous "throttling" incidents were congestion at a peering interconnect, not last-mile discrimination. The user experience is identical, the mechanism is entirely different, and the policy remedies are different too.

Encryption has changed the terrain. TLS 1.3 encrypts most of the handshake, Encrypted Client Hello conceals the server name, QUIC moves transport metadata inside the encrypted envelope, and encrypted DNS removes another observation point. Each of these removes a signal that discrimination depended on. Protocol design has become a policy instrument, which is why debates in standards bodies about what metadata remains visible are contested by parties well outside engineering.

Governance is the other half, and it is not one body but several, each with a distinct scope and a distinct legitimacy model:

Body	Scope	How it decides
IETF	Internet protocols (RFCs)	Open participation, rough consensus, running code
IANA / ICANN	Names and number coordination, root zone	Multi-stakeholder, contract-based
RIRs (RIPE, ARIN, APNIC, LACNIC, AFRINIC)	Address allocation per region	Community policy, bottom-up
IEEE	Physical and link layer standards	Members, formal balloting
W3C	Web platform standards	Members plus community groups
ITU	Telecommunications treaties	States vote; an alternative model

The structural tension worth understanding is between multi-stakeholder governance, where anyone who shows up can participate and legitimacy comes from open process, and multilateral governance, where states negotiate and legitimacy comes from sovereignty. The Internet's technical layer grew up under the first model, and pressure towards the second is persistent.

Fragmentation is the concrete risk. National filtering, data localisation requirements, divergent regulation, and independent name or routing infrastructure all push towards a "splinternet" in which reachability depends on jurisdiction. RPKI is the clearest example of where governance meets protocol: securing BGP means someone must be authoritative about who may announce which prefix, and that authority is simultaneously a security improvement and a control point, since a route origin authorisation can be revoked. The engineering and the politics are not separable here, and pretending otherwise leads to designs that get rejected for reasons the designer never considered.

Examples

Where the rules for one HTTPS request come from

  Browser --------------------------------------------------> Server
     |          |          |           |          |
     |          |          |           |          +-- IETF: TLS 1.3, QUIC, HTTP/3
     |          |          |           +------------- IANA: port 443 registration
     |          |          +------------------------- RIR: the server's IP block
     |          +------------------------------------ ICANN: the domain's TLD
     +----------------------------------------------- IEEE: Wi-Fi / Ethernet below

  And, invisibly on top of all of it:
     national regulator -- may this ISP throttle this flow? may it block it?
     RPKI authority ----- may this AS announce this prefix at all?

  Every one of these can change what a correct implementation is allowed to do.

# Governance made concrete: who is permitted to originate this prefix?
whois -h whois.bgpmon.net " --roa 13335 1.1.1.0/24"
# 0 - Valid
#   ROA Details
#   Origin ASN: AS13335
#   Not valid Before: ...
# The answer exists because an RIR issued a cryptographic authorisation.
# A network operator enforcing RPKI is enforcing a POLICY decision made
# by an address registry, in the data plane, at every route announcement.

# What a neutrality rule would govern, expressed as configuration:
#   class-map match-any STREAMING
#     match protocol rtp                  <- application-aware classification
#   policy-map WAN-OUT
#     class STREAMING
#       bandwidth percent 40              <- this is "reasonable management"
#     class COMPETITOR-VIDEO              <- and THIS is the thing rules forbid
#       police cir 1000000                   (same mechanism, different intent)

Key Takeaways

• Governance decides what your protocols are allowed to do, so it is an engineering constraint, not a separate subject.
• Networks can discriminate by application, source, and destination. Neutrality is about what is permitted, never about what is technically possible.
• Distinguish reasonable congestion management from paid prioritisation, and both from interconnection disputes, which look identical to users.
• Encryption removes the signals discrimination relied on. TLS 1.3, ECH, QUIC, and encrypted DNS make protocol design a policy lever.
• Governance is distributed by scope: IETF for protocols, ICANN and IANA for names and numbers, RIRs for addresses, IEEE for links, ITU for treaties.
• The structural tension is multi-stakeholder against multilateral legitimacy, and it is unresolved.
• RPKI is where governance enters the data plane: it improves routing security and creates an authority that can revoke an announcement.
• Fragmentation is the practical risk — filtering, localisation, and divergent regulation making reachability depend on jurisdiction.

🧪 Practice

1. Classify each and justify it: an ISP shaping all video during evening peak, exempting its own streaming service from a data cap, and blocking a rival's voice application.
2. Name the body that would decide each: a new TCP option, a new generic top-level domain, an IPv6 allocation to an ISP, and a new Wi-Fi standard.
3. Explain how Encrypted Client Hello changes what an ISP can do about a specific website, and what observation remains available to it.
4. Interview-style: Does RPKI centralise control of the Internet's routing? (Hint: identify who issues the authorisations and what revoking one would do, then weigh that against what BGP's trust model is without it.)