The Network · Chapter 11
How do they find each other?

Chapter 10.b mapped a neighbour’s network address to its local link address, the information needed to address a frame on a shared link. But the internet is not a single shared wire that every machine can hear. It is billions of machines joined by many local links. A message from here to anywhere crosses a chain of intermediate machines, each passing it one step closer. This chapter is about how a message finds its way: how each machine knows where to send it next, without carrying the whole route in the packet.

Three ideas do the work. Network addresses identify the destinations; as in the last chapter, letters stand for those addresses, rather than DNS host names. The network is a graph of those machines and the links between them. And routing is the process by which each machine decides, for any destination, which neighbour to forward through.

11.1 The network is a graph

Strip away the wires and what remains is a graph: machines are nodes, and a link between two machines is an edge. Figure 11.2 shows the small network this chapter uses, six machines with addresses A through F, arranged as two triangles joined by two links.

The interactive version needs the in-browser runtime.

A real network weighs its links by speed or cost, and the shortest route is the cheapest one. Ours treats every link as one hop, so the shortest route is simply the one with the fewest links. The principle is the same either way, and the fewest-hops version keeps the search to its simplest correct form.

11.2 Routing tables: shortest paths

Each machine keeps a routing table: for every possible destination, the neighbour to forward a message through. The table is not a full set of routes. It holds only the first step toward each destination, which is all a machine needs, because the next machine holds the next step.

To build the table, a machine searches the graph for the shortest path to every other node. The search is breadth-first: visit the source’s neighbours first, then their neighbours, and so on outward. Because breadth-first search reaches nodes in order of distance, the first time it touches a node it has found a shortest path, and the first step on that path is the table entry.

Every table builder here receives the complete, static graph. Discovering the topology and updating routes after a link changes are outside this model. The forwarding decision will be local even though this table construction sees the whole network.

Example 11-1. Shortest paths by breadth-first search

def _bfs(network: dict, source: str) -> tuple[dict, dict]:
    """Breadth-first search from source.

    Returns two maps: the next hop toward each node (the first step on a shortest
    path) and the distance to each node in hops. Neighbours are visited in sorted
    order, so ties break the same way on every run.
    """
    next_hop = {}
    distance = {source: 0}
    queue = deque([source])
    while queue:
        node = queue.popleft()
        for neighbor in sorted(network[node]):
            if neighbor not in distance:
                distance[neighbor] = distance[node] + 11
                next_hop[neighbor] = neighbor if node == source else next_hop[node]2
                queue.append(neighbor)
    return next_hop, distance

• each newly reached node is one hop farther than the node it was reached from; because the search expands outward in rings, this first distance found is the shortest
• the first hop toward a node is the node itself when it is a direct neighbour of the source, and otherwise the same first hop as the node it was reached from, so the whole shortest path is summarised by one step

The table for a machine is the next-hop half of this search. Asking the search for the distance instead gives the hop count, which the chapter uses to compare a forwarded route’s length with the distance computed by the same breadth-first search. This is a consistency check, not an independent algorithm.

11.3 Forwarding: one hop at a time

With every machine holding a routing table, delivery is simple and local. A packet carries its destination. The machine it sits on looks that destination up in its own table and hands the packet to that neighbour. The next machine does the same. During forwarding, each consults only its next-hop entry. This graph model records the hop; it does not call ARP or transmit a link-layer frame.

Example 11-2. Forwarding a packet hop by hop

def route(network: dict, source: str, dest: str) -> list[str]:
    """Forward a packet from source to dest, hop by hop.

    At each node the packet consults that node's own routing table for the next
    hop; constructing those tables uses the whole graph. Returns the nodes the
    packet passes through, source first and dest last.
    """
    if source not in network or dest not in network:
        raise KeyError("source and destination must be network nodes")
    path = [source]
    node = source
    while node != dest:
        node = routing_table(network, node)[dest]1
        path.append(node)
    return path

• at each node the packet consults that node’s own table for the next hop toward its destination; the packet is never handed a full route, only ever the next single step

Figure 11.3 traces a packet from A to F. At A the table says send to B; at B, send to D; at D, send to F. Three independent local decisions, made during forwarding without negotiation between the machines, and the packet follows a shortest path.

That this works is not obvious. Each machine chooses only its next hop, on its own table, with no route stored in the packet. In this computed table, every choice moves the packet exactly one hop closer to the destination, so the steps cannot loop and cannot wander: they add up to a shortest path. It holds for every pair of machines in the network, not just A and F.

11.4 The network, run

Running ftb.routing prints the network, builds A’s routing table, and forwards a packet from A to F.

network links:
  A connects to B, C
  B connects to A, C, D
  C connects to A, B, E
  D connects to B, E, F
  E connects to C, D, F
  F connects to D, E

routing table at A (destination: next hop):
  B: B
  C: C
  D: B
  E: C
  F: B

a packet from A to F travels: A -> B -> D -> F
that is 3 hops, the shortest possible (3).

The table gives A one next hop per destination. Following them, the packet travels A to B to D to F, three hops, matching the distance returned by the shared breadth-first search. The test suite runs this same check for every pair of machines: in each case the local decisions compose into a valid, shortest route.

A path can still lose or reorder packets; the next chapter makes delivery reliable end to end.

Exercises

• Add a link to the network, and watch a shorter path appear between two machines.
• Ask for a route to a machine that nothing connects to, and see what happens.