Routing: From a Destination IP to a Next Hop

IP delivery is hop by hop. No machine knows the whole path to a destination; each one knows only where to hand the packet next. A host, a home router, an ISP core router and a data-centre switch all run the same procedure: take the destination IP out of the header, look it up in a routing table, and get back two things — the interface to send on and the next hop, the neighbour’s IP on that interface (or "deliver directly").

The distinction between directly connected and via a gateway is the whole trick of IP. If the destination is on a network attached to one of my interfaces, I resolve its link-layer address with ARP and Neighbor Discovery: From an IP to a Local MAC and put the frame on the wire myself. If it is not, I do not try to reach it; I hand the packet to a router that is on my network, with the router’s MAC address in the frame but the *final* destination’s IP still in the IP header. The IP header does not change at each hop (apart from the TTL decrement); the frame around it is rebuilt every hop — see Encapsulation: Data, Segment, Packet, Frame and Switches vs Routers.

A default route is the entry that matches everything: 0.0.0.0/0 for IPv4, ::/0 for IPv6. A laptop typically has one default route (the home router) and one or two connected networks; a core router may have no default at all, because it is expected to know a specific route for every reachable prefix.

A routing table is a list of prefixes, each written as a network address and a length: 10.0.0.0/8, 10.10.0.0/16, 0.0.0.0/0. A destination "matches" a prefix when its first *length* bits equal the prefix’s. Because prefixes nest, one destination frequently matches several entries — 10.10.42.7 matches all three above. The rule that resolves this is longest-prefix match (LPM): the entry with the most matching bits wins, because it is the most specific statement anyone made about that address.

The default route has length 0, so it matches every address and loses to everything else. That is exactly what you want: it is the route of last resort. Metric (also called cost, distance or priority depending on the vendor) breaks ties only between entries with the *same* prefix — two default routes, say, one via Wi-Fi with metric 600 and one via Ethernet with metric 100. Metric never overrides prefix length; a more specific route with a terrible metric still wins over a less specific one with a great metric.

The Routing Table and Longest-Prefix Match walks through a concrete lookup bit by bit, and explains why LPM — rather than, say, "first match" or "lowest metric" — is what makes the internet’s routing tables compressible.

Routing is not something only routers do. Every host with an IP stack has a routing table and consults it for every outgoing packet; it is usually just very short. On Linux, ip route prints the main table, and ip route get <addr> shows the exact decision the kernel would make for one destination — the single most useful command when a packet is leaving through the wrong interface.

Read the transcript below top to bottom. The default via line is the gateway route. The proto kernel scope link lines were added automatically when an interface got an address: "this /24 is directly reachable on wlan0, and use src 192.168.1.42 as the source address". The metric 600 on the Wi-Fi routes is NetworkManager’s way of preferring wired over wireless when both are up. The VPN client added a /32 for its own server via the physical gateway (so the tunnel’s own packets do not get routed into the tunnel) and then a pair of /1 routes that together cover the whole address space and — being longer than /0 — beat the default route without deleting it.

The entries above were static or kernel-generated: put there by DHCP, by an administrator, or by an interface coming up. A static table is fine for a host with one way out, and for small networks with no redundancy. It is useless the moment there are two paths and one of them fails, because nothing updates it.

Dynamic routing means routers run a protocol that exchanges reachability information and recomputes the table when the topology changes. Inside one organisation the common choices are link-state protocols — OSPF and IS-IS — in which every router learns the full graph of links and costs and runs a shortest-path computation locally. Older or smaller networks use distance-vector protocols like RIP, where each router only learns its neighbours’ distance estimates. Between organisations, the entire internet uses one protocol, BGP, which is a *path-vector* protocol driven by policy more than by distance; Internet Routing: Autonomous Systems and BGP covers it.

The property to care about is convergence time: the interval between a link failing and every affected router agreeing on the new table. During that interval packets loop, black-hole, or take detours. OSPF converges in under a second on a well-tuned network; global BGP can take minutes. Both are why "the site was unreachable for 90 seconds and then fixed itself" is a routing story far more often than a server story.

Two things you already know from DSA are the literal machinery here. Longest-prefix match over binary strings is a trie problem. The routing table is a binary trie keyed on address bits; a lookup walks from the root following the destination’s bits and remembers the last node that carried a route — that node is the longest matching prefix. Linux’s IPv4 forwarding table is a compressed variant of exactly this structure (an LC-trie, visible at /proc/net/fib_trie); hardware routers use TCAM, which The Routing Table and Longest-Prefix Match explains. A hash table cannot do this job: hashing needs an exact key, and a prefix lookup is an inexact one.

Topology is a graph, and choosing routes is shortest path. OSPF’s SPF computation is Dijkstra over a weighted graph of routers and links. Distance-vector protocols are distributed Bellman–Ford: each node relaxes its estimates from what its neighbours report, and the "count to infinity" problem is what happens when Bellman–Ford runs without a global view. When you implement Dijkstra's Algorithm on a weighted graph, you are re-deriving an interior gateway protocol.