Internet Routing: How Packets Find Their Way

No router sees the whole network

Every router on the Internet must decide, for every possible destination, which neighbour to hand a packet to next — and it must do this with no central authority telling it the answer. Two fundamentally different strategies solve this: distance-vector routing, where routers only ever tell their immediate neighbours "here is my current distance to each destination", and link-state routing, where every router announces its own direct connections to everyone, and each router builds a complete map and computes its own routes from it.

Distance-vector: routing by rumour

A distance-vector router keeps one number per destination — its current best-known cost — and periodically tells each neighbour that whole table. The update rule is the Bellman-Ford relaxation, run continuously and distributed across the network:

for each neighbour n and each destination d:
  candidate = cost(self, n) + n.distance_to(d)
  if candidate < my.distance_to(d):
    my.distance_to(d) = candidate
    my.next_hop(d)    = n

RIP (Routing Information Protocol) is the classic example: the metric is simply hop count, and 16 hops is defined as unreachable, which caps how large a RIP network can be. The protocol's fatal weakness is the count-to-infinity problem: if a router loses its route to a destination, a neighbour that still has a stale route to it can advertise that route right back, and the two routers increment the distance between them one exchange at a time instead of immediately realising the destination is gone. Mitigations like split horizon (never advertise a route back to the neighbour you learned it from) and poison reverse (advertise it back but as infinity) shrink the problem but do not eliminate every case.

Link-state: routing with a full map

A link-state router does the opposite: instead of sharing distances, it floods a small message — a link-state advertisement (LSA) — describing only its own direct links and their costs, to every other router in the area. Once every router has received every LSA, each one independently has an identical picture of the whole topology, and each one runs Dijkstra's shortest-path algorithm on that picture, rooted at itself, to compute its own next hops. OSPF and IS-IS, the two link-state protocols that actually run most of the Internet's interior networks, work exactly this way; OSPF further divides a large network into areas so a router only needs the full map of its own area, keeping the Dijkstra computation and the LSA flood bounded in size.

Cutting a link: convergence compared

The difference between the two shows up most clearly when a link fails. A link-state router adjacent to the break immediately floods a fresh LSA saying "that link is gone", every other router receives it within a few hops of propagation delay, and each recomputes Dijkstra with the corrected map — convergence is fast and, short of the flood itself being lost, does not loop. A distance-vector network instead has to let the count-to-infinity mechanism play out, or rely on triggered updates and poison reverse to shortcut it; even with those safeguards, distance-vector convergence after a failure is generally slower and can transiently create routing loops that link-state, by computing routes from a shared ground truth, avoids by construction.

What actually runs the Internet

Inside a single network (an autonomous system) OSPF or IS-IS — both link-state — is the near-universal choice today; RIP survives mostly in small legacy deployments. Between autonomous systems, the protocol is BGP, which is neither pure distance-vector nor link-state but path-vector: alongside a metric it advertises the entire sequence of autonomous systems a route has traversed, so a router can immediately reject any route whose path already contains itself, sidestepping the count-to-infinity failure mode by making loops directly visible rather than something to be inferred from a slowly changing number.

Frequently asked questions

Try it live

Everything above runs in your browser — open Internet Routing and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.