Routing — Networking · the runtime

You never said which way

Your laptop has a Wi-Fi interface, maybe an Ethernet port, a loopback device, and after lesson 12 a virtual one. Each has its own address. When you call sendto with destination 93.184.216.34, you did not say "use Wi-Fi" or "hand this to the router at 192.168.1.1". Yet the packet left through Wi-Fi, addressed at the Ethernet layer to the router, and it got there.

The kernel made two decisions from the destination IP alone: which interface to write the frame on, and which machine should receive the frame — the next hop. It made them by looking the address up in the routing table. Every machine that forwards IP packets, from your laptop to a backbone router, does this same lookup for every packet.

The table

sh

$ ip route
default via 192.168.1.1 dev wlan0 proto dhcp metric 600
100.64.0.0/10 dev tun0 scope link
127.0.0.0/8 dev lo scope host
192.168.1.0/24 dev wlan0 proto kernel scope link src 192.168.1.7
          

Each row is a route: a destination prefix, the interface to send on, and optionally a gateway. 192.168.1.0/24 dev wlan0 says: anything whose first 24 bits match 192.168.1 is on the Wi-Fi network directly — send the frame straight to it. default via 192.168.1.1 is the row for everything else: hand the packet to the router at 192.168.1.1 and let it worry. On macOS and BSD, netstat -rn shows the same table in a different layout.

The match is a bitwise AND

A prefix like /24 is a mask: 24 one-bits followed by 8 zero-bits, 0xFFFFFF00. A destination matches a route when ANDing it with the route's mask produces the route's network address. That is the whole test, and it is one instruction:

c

struct route {
    uint32_t net;        // 192.168.1.0  → 0xC0A80100 (host order here)
    uint32_t mask;       // /24          → 0xFFFFFF00
    uint32_t gateway;    // 0 = deliver directly on the link
    int      ifindex;    // which interface
};

static int matches(const struct route *r, uint32_t dst) {
    return (dst & r->mask) == r->net;
}

// 192.168.1.42 & 0xFFFFFF00 = 192.168.1.0  → matches 192.168.1.0/24
//  93.184.216.34 & 0xFFFFFF00 = 93.184.216.0 → does not
// anything & 0x00000000 = 0.0.0.0           → always matches 0.0.0.0/0
          

Notice the last line. The default route is 0.0.0.0/0: a zero-bit mask. AND anything with zero and you get zero, which equals the network 0.0.0.0. The default route is not special-cased anywhere. It is just a route that matches every address because it has nothing to check.

Longest prefix wins

That raises a problem. 192.168.1.42 matches 192.168.1.0/24 and the default route. Which one? The rule is longest-prefix match: among the routes that match, pick the one with the most mask bits. /24 beats /0. /10 beats /0. A more specific route is a more specific claim about where that address lives, and specific knowledge overrides general.

c

const struct route *lookup(const struct route *tbl, int n, uint32_t dst) {
    const struct route *best = NULL;
    for (int i = 0; i < n; i++) {
        if (!matches(&tbl[i], dst)) continue;
        // a longer mask has more one-bits → numerically larger
        if (!best || tbl[i].mask > best->mask) best = &tbl[i];
    }
    return best;    // NULL → "Network is unreachable" (ENETUNREACH)
}
          

Step through the visualization. Three destinations go through the same four-row table. For each, every row's mask is ANDed with the destination; rows that fail go gray, rows that match turn green, and the longest match wins. Watch the third destination — it never leaves the machine on a real wire.

routing table — longest-prefix match

Click next to start the walkthrough.

💡

The kernel does not loop over rows like the code above. Linux keeps routes in a trie keyed by address bits, so the lookup walks down the prefix instead of scanning. Same answer, O(32) instead of O(rows). The linear version is the right mental model; the trie is the right implementation.

Local or remote: what the gateway column means

The winning route answers two questions. The interface is where the frame goes out. The gateway, if present, is who the frame is addressed to at the Ethernet layer. When the route has no gateway (scope link), the destination is on your own network: the frame carries the destination's own MAC address. When the route has a gateway, the frame carries the router's MAC address, while the IP header inside still says the real destination. The router receives the frame, looks at the IP header, does its own table lookup, and forwards.

How does the kernel learn a MAC address from an IP address? It asks. ARP broadcasts "who has 192.168.1.1?" on the link and the owner replies with its MAC; the answer is cached (see ip neigh). That is a lower-layer detail; what matters here is that the routing decision picks which IP to ask about.

⚠️

"Network is unreachable" is a routing miss, not a cable problem. sendto fails with ENETUNREACH when no route matches the destination. Usually the default route is missing — DHCP failed, or a VPN removed it. Run ip route before you blame the network.

TTL: the loop guard

Every router that forwards your packet decrements the IP header's TTL field by one. When it hits zero the router drops the packet and sends back an ICMP "time exceeded" message. Without this, two routers with inconsistent tables could bounce a packet between them forever. traceroute exploits the mechanism on purpose: it sends packets with TTL 1, 2, 3, … and each hop that drops one reveals its address in the ICMP reply. The output of traceroute is the list of routing decisions made along the way, one table lookup per line.

A route can point at something that is not a wire

Look at the second row of the table again: 100.64.0.0/10 dev tun0. tun0 is not a network card. It is a virtual interface whose other end is a file descriptor inside a user-space program. The kernel does not know or care. A packet for 100.64.0.2 matches that row (longer than /0), so the kernel "transmits" it on tun0 — which means a read in some process returns the packet's bytes. That process can do anything it likes with them, including encrypting them and sending them out the real Wi-Fi interface as UDP.

This is the entire mechanism a VPN uses to capture traffic: not interception, not packet filters. One line in the routing table, added like this:

sh

$ sudo ip route add 100.64.0.0/10 dev tun0     # send this prefix to the virtual interface
$ ip route get 100.64.0.2                       # ask the kernel what it would do
100.64.0.2 dev tun0 src 100.64.0.1 uid 1000

$ ip route get 93.184.216.34
93.184.216.34 via 192.168.1.1 dev wlan0 src 192.168.1.7 uid 1000
          

✅

Use ip route get ADDR to see the decision before sending a byte. It runs the exact same lookup the kernel will run for your packet and prints the winning route, interface, gateway, and source address. When a packet goes somewhere surprising, this tells you why in one command.

Lesson 12 opens that tun0 file descriptor and reads the packets the routing table delivers to it. Before that, there is a harder question: when the packet does leave your machine toward 192.168.1.1, why does the rest of the internet see a completely different source address? That is NAT, next.

one-line takeaway

Routing is a table lookup: AND the destination with each route's mask, keep the rows that equal their network, and the longest prefix decides the interface and next hop — even when that interface is a file descriptor.