5.3.2 — Routing: How a Packet Crosses the World

Run this and watch it work:

traceroute google.com          # macOS / Linux
tracert google.com             # Windows

You will see something like fifteen lines, each one a machine that touched your packet. Your router. Your ISP's local box. A regional aggregation point. A national backbone router. A peering exchange. Google's edge. Fifteen independent machines, owned by four or five different companies, none of which has any agreement with you.

None of them knew the full route. Each one knew only one thing: which neighbour to hand this packet to next. That is what makes the internet scale, and this page is how that one thing gets decided.

1. What a router actually does to a packet

A router receives a frame, and does five things in order. Being able to list them is worth more than any amount of vocabulary.

1. Strip the frame. The Ethernet header from Chapter 5.2 is discarded entirely. It only ever meant "get to the next box", and the packet has arrived at that box.

2. Look up the destination. Take the destination IP from the packet header and find the longest matching prefix in the routing table (Chapter 5.3.1). That gives an outgoing interface and a next hop — the address of the neighbouring router to hand it to.

3. Decrement the TTL. The TTL (time to live) is an 8-bit counter in the IP header. Every router subtracts one. If it reaches zero, the router discards the packet and sends an ICMP "time exceeded" message back to the source.

This exists because routing tables can temporarily disagree during a change, creating a loop where A sends to B, B sends to C, and C sends back to A. Without TTL that packet circulates forever, and enough of them saturate the link — exactly the broadcast storm problem from Chapter 5.2, which Ethernet has no defence against. TTL is the field Ethernet is missing, and comparing the two is a good way to see why it matters.

Typical starting values are 64 (Linux, macOS) and 128 (Windows), which is itself a mild fingerprint of the sending operating system.

4. Recompute the header checksum. The TTL changed, so the IPv4 header checksum must be recalculated. (IPv6 dropped the header checksum entirely, precisely because doing this at every hop is wasted work when the layers above and below both checksum anyway.)

5. Build a brand-new frame for the next hop, with this router's MAC as the source and the next hop's MAC as the destination — found by ARP (Chapter 5.2) — and transmit.

The sentence that ties Part 5 together: the IP addresses in the packet are untouched from source to destination, while the MAC addresses are replaced at every single hop. The IP header says where it is going; the frame says where it is going next.

2. How traceroute exploits the TTL

Traceroute is a clever abuse of the mechanism just described, and understanding it makes both concepts stick.

Send a packet with TTL = 1. The first router decrements it to 0, discards it, and sends back an ICMP "time exceeded" — which contains that router's own address. You now know hop 1.

Send TTL = 2. The first router decrements to 1 and forwards; the second decrements to 0 and complains. You now know hop 2. Repeat, incrementing, until you get a reply from the destination itself.

There is no "trace" protocol. Traceroute is deliberately triggered error messages, which is why its output is often imperfect: some routers are configured not to send ICMP at all, so you see * * *; some rate-limit it, so timings look worse than reality; and load balancing can send successive probes down different paths, so consecutive hops may not actually be on one route.

A * does not mean the packet was dropped. It means that router declined to send an error message. Traffic through it is usually fine. Misreading that is the most common traceroute mistake.

3. Reading a routing table

ip route            # Linux
netstat -rn         # macOS
route print         # Windows

A laptop's table is tiny:

default via 192.168.1.1 dev wlan0            # (1)
192.168.1.0/24 dev wlan0 proto kernel        # (2)

1. The default route. 0.0.0.0/0 matches everything, so anything not covered by a more specific entry goes to 192.168.1.1. Longest prefix match guarantees this always loses to a real route, which is exactly what makes it a safe catch-all.
2. The directly connected route. Anything on the local subnet needs no router — send it straight out the interface. The kernel adds this automatically when the interface gets an address.

Two entries is enough for a laptop, because a laptop only needs to distinguish "local" from "not local". A backbone router at the internet's core needs something very different: it has no default route at all, and must hold a route for every prefix in existence — around a million of them. That is called a full table, and needing to hold one is a real constraint on router hardware.

4. Two different routing problems

Routing splits into two problems that need different solutions, and conflating them is a common confusion.

Inside one organisation — a company, a university, a cloud provider's own network — one authority controls every router, everyone shares the goal of finding the shortest path, and everyone can be trusted. Protocols here are called IGP (interior gateway protocols).

Between organisations — your ISP and Google's network — nobody is in charge, the goal is not shortest path but cheapest according to a business contract, and nobody fully trusts anyone. This is EGP (exterior), and in practice means exactly one protocol: BGP.

The unit of "an organisation" is the autonomous system, an AS, identified by a number. AS 15169 is Google, AS 32934 is Meta, AS 3356 is Lumen. There are around 75,000 of them. The internet is best understood not as a network of machines but as a network of about 75,000 autonomous systems that have agreed to carry each other's traffic.

5. Interior routing: OSPF and the shortest path

The dominant interior protocol is OSPF (open shortest path first), and it works in three steps:

Every router learns the entire map. Each router floods a description of its own directly connected links to every other router in the area. After convergence, every router holds an identical copy of the complete network graph.

Every router runs Dijkstra on it. Chapter 4.19.3's algorithm, on that graph, from itself as the source. This is where the algorithm you learned in Part 4 is actually running in production, on hardware, thousands of times a day.

Costs are configurable. Link cost is usually derived from bandwidth — a 10 Gbit/s link costs less than a 1 Gbit/s link — but an operator can set it manually to steer traffic away from an expensive path.

Areas keep it from exploding. Every router holding the whole map is fine for hundreds of routers and impossible for tens of thousands, because both the flooding and the Dijkstra run grow with the graph. So OSPF splits a network into areas, all connected to a backbone area, with only summary information crossing area boundaries. That is the same hierarchy-to-limit-knowledge idea as subnetting itself.

The older alternative, RIP, is essentially distributed Bellman-Ford (Chapter 4.19.3) — each router tells its neighbours its best known distances. It is simpler and it converges slowly, with a failure mode called count to infinity where a router's stale information circulates and distances creep upward one at a time. RIP capped the hop count at 15 to bound the damage, which also capped the size of any network using it. OSPF's give-everyone-the-whole-map approach exists to eliminate that failure, and the trade is more memory and more flooding for much faster, correct convergence.

6. BGP: the protocol that runs on trust

BGP (border gateway protocol) connects the autonomous systems, and it is unlike everything above it.

It is a path-vector protocol. An AS does not advertise a distance. It advertises a path: "to reach 142.250.0.0/15, come to me, and from me it goes through AS 15169." Each AS that passes the advertisement on prepends its own number.

Advertising the whole path solves loop prevention exactly. If an AS sees its own number already in the path, it rejects the advertisement — the route would loop back through itself. No counting, no TTL, just a membership check. This is the direct fix for RIP's count-to-infinity, and it is why path vector was chosen.

Route selection is business policy, not distance. BGP has a long ordered list of tie-breakers, and the ones that actually matter are near the top:

1. Local preference — a number the operator sets manually. Highest wins. This is where "prefer the link we already paid for" is expressed.
2. Shortest AS path — fewest autonomous systems traversed.
3. Various technical tie-breakers, then finally lowest router ID.

Local preference sits above AS path on purpose. A path through three networks the operator peers with for free will be chosen over a two-network path they would have to pay for. The internet routes traffic by contract first and topology second, and that single fact explains a great deal of otherwise baffling routing behaviour — including why traffic between two cities in one country sometimes crosses an ocean.

The money underneath is worth one paragraph, because it explains the shape of the network:

• Transit — a customer pays a larger network to carry its traffic to everywhere.
• Peering — two networks of similar size exchange traffic between their own customers for free, because it benefits both equally.
• A tier 1 network is one that reaches the whole internet through peering alone and pays nobody for transit. There are roughly a dozen.

BGP has essentially no security, and this is not a small problem. An AS can advertise any prefix it likes, and neighbours largely believe it. Two consequences:

Route hijacking. In 2008, Pakistan Telecom advertised a more specific prefix for YouTube in order to block it domestically. The advertisement leaked to its upstream provider and propagated globally, and because longest prefix match prefers the more specific route (Chapter 5.3.1), YouTube went dark worldwide for about two hours. No exploit, no malware — one incorrect announcement that everyone believed.

Route leaks and withdrawals. In 2021, Meta made a configuration change that caused its own routers to withdraw the BGP advertisements for its address ranges. The prefixes vanished from the global routing table, so Facebook, Instagram and WhatsApp did not become slow — they ceased to exist as far as the internet was concerned, for about six hours. It also locked engineers out of the systems they needed to fix it, because those depended on the same infrastructure.

The defences being deployed are RPKI (a cryptographic registry proving which AS is authorised to originate which prefix) and route filtering by upstream providers. Adoption is partial and improving. The honest summary: the routing layer of the internet still runs substantially on the assumption that network operators are competent and honest, and the incidents above are what happens when that assumption briefly fails.

7. What this means for the engineer, not the network operator

You will almost certainly never configure BGP. Four things from this page still matter in ordinary work.

Latency is set by geography and route, not by bandwidth. Light in fibre travels about 200,000 km/s, so London to Sydney is roughly 17,000 km, giving about 85 ms one way and 170 ms round trip at the theoretical minimum. Real routes are longer and add switching delay, so 250–300 ms is normal. No amount of money buys a faster round trip on that path — which is exactly why Chapter 10.14.3's CDNs exist, and why "add a bigger server" never fixes a latency complaint from another continent.

An incident may not be yours. When a service is unreachable from one region and fine from another, a routing problem between two networks you do not control is a real possibility. traceroute, mtr and looking-glass servers are how you demonstrate that rather than assert it.

BGP anycast is how global services work. Advertise the same prefix from many locations, and every router sends traffic to the nearest one by its own metrics. This is how public DNS resolvers like 1.1.1.1 and 8.8.8.8 answer from a nearby city wherever you are, and how CDNs steer users to a nearby edge. Chapter 10.14.3 covers it as a design tool; here you can see the mechanism, which is simply that longest prefix match plus multiple origins gives you geographic distribution for free.

Cloud networking is this, virtualised. A cloud provider's route table is the same concept with a management interface on it. When Chapter 5.10 sets up a route table sending 0.0.0.0/0 to a NAT gateway and 10.0.0.0/16 to a local route, that is exactly the two-line laptop table from section 3, with the provider's software playing the part of the kernel.

What the interviewer will push on

"What happens to a packet at each router?" Five steps: strip the frame, longest-prefix lookup, decrement TTL, recompute the checksum, build a new frame. The tell is mentioning that the MAC addresses change and the IP addresses do not.

"How does traceroute work?" Incrementing TTL to provoke ICMP time-exceeded messages from each hop in turn. Then the follow-up: a * means that router declined to send ICMP, not that traffic is being dropped.

"Why does the internet need both OSPF and BGP?" Different problems. Inside one organisation everyone shares a goal and can be trusted, so shortest-path with full knowledge works. Between organisations the goal is contractual cost, nobody is in charge, and nobody fully trusts anyone — so you advertise paths and apply policy.

"Why does BGP advertise the whole AS path?" Loop prevention by membership check: an AS that sees its own number rejects the route. That is the exact fix for RIP's count-to-infinity.

"Explain a BGP hijack." Advertise a more specific prefix than the legitimate owner; longest prefix match makes every router prefer it. Give the 2008 YouTube incident, and name RPKI as the deployed defence.

"Why is latency from London to Sydney about 250 ms and why can you not fix it?" Speed of light in fibre over 17,000 km plus routing overhead. It is a physical bound, which is why CDNs and regional deployment are the only real answers. This is asked in system-design interviews far more than in networking ones.

One thing to volunteer: say that BGP prefers local preference over AS path length, so the internet routes by contract before topology. It explains routing behaviour that otherwise looks irrational and shows you understand the network as an economic system, not just a technical one.

Recall

• A router does five things: strip the frame, longest-prefix lookup, decrement TTL, recompute the checksum, build a new frame. IP addresses survive every hop; MAC addresses are replaced at every hop.
• TTL exists to kill routing loops — it is the field Ethernet lacks, which is why a layer-2 loop causes a broadcast storm and a layer-3 loop does not.
• traceroute provokes ICMP time-exceeded by incrementing TTL; a * means that router declined to reply, not that traffic is dropped.
• Inside one organisation, OSPF floods the full map and runs Dijkstra on it; RIP's distributed Bellman-Ford converges slowly and can count to infinity.
• Between organisations, BGP is a path-vector protocol: advertising the whole AS path prevents loops by a membership check, and local preference outranks AS path length, so the internet routes by contract before topology.
• BGP has almost no authentication: a more specific advertisement hijacks traffic (YouTube, 2008), and withdrawn advertisements erase a company from the internet (Meta, 2021). RPKI is the partial fix.
• Latency is bounded by the speed of light in fibre (~200,000 km/s), which is why CDNs and regional deployment are the only cures for cross-continent round trips.

Self-test: Which addresses change at each hop and which do not? · Why does an IP loop stop but an Ethernet loop does not? · What does * * * in traceroute actually mean? · Why does BGP advertise a whole path instead of a distance? · Why can a three-AS path be preferred over a two-AS path? · Compute the theoretical minimum round trip for 17,000 km of fibre.

Next: 5.3.3 explains how a machine with a 192.168.x.x address — an address that is guaranteed not to be routable — nevertheless reaches the whole internet, what that trick cost, and why a cloud provider now puts a price tag on an IPv4 address.