A day in the life of a packet

The copy of Toy Story 2 on Galyn Susman’s home computer, the off-site copy of the 3-2-1 rule, git push: everything the last chapter ended with depends on data being able to move from one machine to another. Yet two machines share no memory and no disk. Between them there is only a wire or a radio wave, and often a dozen go-betweens along the way. How do they exchange data? We start with the smallest exchange there is. The program below sends two letters to another program on the same machine, then asks the kernel how many bytes went through the network “loopback,” the internal wire that connects the machine to itself.

The letters arrived, but the numbers don’t add up: we sent two bytes, and thirty went through the loopback. Where did the other twenty-eight come from, and why does the counter call the whole lot one “packet”? Answer these two questions and you know how a network is built. The extra bytes are the clothes data travels in, and a packet is the unit of travel.

The program above talks to the network through a socket, a place to plug into the network. The kernel hands a socket to a program the same way it hands out an open file in Chapter 36: it is a file descriptor too, only the bytes written to it go out to the network. The address 127.0.0.1 means “this machine.” We’ll work with sockets properly in the next chapter; here we follow a single packet. This chapter is its biography: birth, clothes, the road, queues, dangers and arrival. And like any proper biography, it begins with the ancestors.

Prologue: two letters from 1969

Our cell replayed that evening in miniature: the same two letters, only a shorter road, from program to program on one machine. The network’s first word was half a word, and an apt one: “lo,” as in “lo and behold.” But to see why two bytes in 1969 traveled the way they did, in separate envelopes and through go-between machines, we have to go back another ten years and look at the only big network of the time, the telephone network.

Ancestors: a wire for two

When someone made a phone call in 1960, the exchange connected their wire to the other person’s: an operator plugged in a jack, and later relays did the same. For as long as the call lasted, there was an unbroken circuit between the two of them, and it belonged to them alone, even while both were silent. This is circuit switching. For voice it works well: sound flows continuously, without delays or gaps.

For computers it works badly. A person at a terminal types a letter, thinks, reads the answer, and the line stands idle nearly all the time, yet nobody else can use it. And connecting every machine to every other with a wire of its own is hopeless: $n$ machines make $\frac{n(n-1)}{2}$ pairs, the same sum as in Chapter 13. For a thousand machines that is almost half a million wires; for a billion, half a billion billion. What we need is a network where one wire serves many and machines are connected through go-betweens.

The solution looks like the mail. A letter needs no wire running all the way to its addressee: you drop it in a mailbox, a sorting office looks at the address and sends it on, and the next office sends it farther. A computer message is cut into pieces, each gets an address attached, and the network’s nodes hand the pieces from one to the next. Each node waits for a piece down to its last bit, looks at the address and passes it to the neighbor that is closer to the goal. A piece with an address is called a packet, and this way of building a network is packet switching. The wire between two nodes is shared by everyone: while you are silent, other people’s packets travel over it.

You will often read that the internet was built to survive a nuclear war. It wasn’t: Charles Herzfeld, the head of ARPA, objected to that legend in so many words. The ARPANET was made so that researchers at different universities could use one another’s expensive computers without leaving home. But it got its design from Baran and Davies: packets, go-between nodes, and many paths instead of one.

We can check Baran’s calculation ourselves. Here are three networks of 49 nodes each: a star with a center, a grid in which every node has four neighbors, and a grid with diagonals, which gives eight neighbors. We switch off a random share of the nodes and, with the breadth-first search of Chapter 19, find the largest group of survivors that can still reach one another.

The star’s average looks respectable, but its worst trial gives its character away: two percent. When the center goes down, every surviving node is left on its own, however many of them survived. The grid with four neighbors shrugs off the loss of a tenth of its nodes, and at half it falls apart into islands. With eight neighbors, even after a third of the nodes are gone, 99% of the survivors are still in one group. That was Baran’s discovery: a network of unreliable nodes becomes sturdy if it has paths to spare. Now switch nodes off yourself.

A distributed network has its price: a packet’s path is written down nowhere in advance, and every node must decide for itself where to send the packet next. We’ll come to those decisions when the packet sets out on the road; for now it isn’t even dressed.

Clothes: an envelope inside an envelope

Back to the thirty bytes. Our two letters lie at the center, and around them are two envelopes, one inside the other. The inner one, eight bytes, was addressed by the part of the kernel in charge of delivery to a particular program. It carries the sender’s port number and the receiver’s port number, and from them the kernel at the other end will know which program gets the letters. The outer one, twenty bytes, was addressed by the part of the kernel in charge of delivery to a particular machine: the sender’s address, the receiver’s address, how many more routers the packet may pass through, and what is inside. We can assemble these thirty bytes ourselves with the struct module, which packs numbers into bytes according to a description of the format.

Thirty on the dot. The format string "!BBHHHBBH4s4s" is an inventory of the fields: B is one byte, H two, 4s four bytes taken as they are, and the exclamation mark at the start asks for network byte order, most significant byte first. This is the same order as in Chapter 28, and all the internet’s protocols agreed on it so that machines that lay out their memory differently could understand one another. That is why the length 30 shows up in the header as 00 1e, and the 7f 00 00 01 at the end is 127.0.0.1, one byte per number. The last line shows how the receiver checks whether the header was damaged on the way. This is a checksum from Chapter 40, one of the simplest: the sum of the header together with the checksum written into it comes out as zero. Flip a single bit and you won’t get zero, and the packet is thrown away.

Each envelope is the result of a separate agreement: the order of the fields, how many bytes each takes, what to do with what arrives. Such an agreement is called a protocol. Our inner envelope is the UDP protocol, and the outer one is IP, the Internet Protocol. Outside the loopback, on a wire or in the air, one more envelope would go around all of this: an Ethernet or Wi-Fi frame with addresses of its own, so the packet could get at least as far as the next device. Protocols are stacked in layers, and each layer solves one problem, relying on the layer below and knowing nothing about the layers above. Such a stack is called a protocol stack. The internet’s has five layers.

• Physical: how a bit becomes a signal, whether a voltage on a copper pair, a flash of light in glass or a radio wave. There are no envelopes here, only signals.
• Link: delivery to a neighbor with whom you share one wire or one stretch of air: Ethernet, Wi-Fi. Its addresses mean something only within one network.
• Network: delivery across the whole world, from machine to machine through a chain of go-betweens: the IP protocol, addresses like 127.0.0.1.
• Transport: delivery to the right program on the machine: UDP or TCP, port numbers.
• Application: what programs say to one another: web pages, mail, our “LO.”

The sender puts data into envelopes from the top down, the receiver opens them from the bottom up, and each layer at the far end reads the header written by its twin at the sender. Go-betweens along the way don’t open everything. A device that connects the computers of one network reads only the link envelope. A router also opens the network envelope to learn the destination address, and as a rule leaves the transport envelope and the data alone. Take a packet from a laptop to a server and watch what changes at each step.

If you have met seven layers in textbooks rather than five, that is the OSI model, which international committees drew up in the late 1970s as a common standard. The internet grew up on a simpler scheme, but the names and numbers of the OSI layers stuck: to network engineers, “layer 3” is the network layer and “layer 7” the application layer.

The first step: sharing the ether

The packet’s very first step takes it to the next device: from a laptop to the home router by radio, or from a computer to a switch by cable. This is the link layer’s job, and the link layer has a history of its own.

When the ether is shared, a question of manners comes up: if two machines start talking at once, their signals mix into noise. Ethernet’s rule is like conversation at a dinner table. Before you speak, listen whether someone else is speaking. If two people started at the same moment anyway, both notice the collision, fall silent and wait a random time. If they collide again, they wait a random time from an interval twice as long, and so on. Randomness separates the speakers, and doubling the interval saves the day when many want to speak. The rule is called CSMA/CD: carrier-sense multiple access with collision detection.

Every network card has an address of its own, set at the factory: the MAC address, 48 bits written as six pairs of hexadecimal digits, for example a4:5e:60:d1:27:0b. An Ethernet frame, the link envelope, begins with the receiver’s address and the sender’s address. Then two bytes say what is inside (08 00 means an IP packet), then comes the data itself, and at the end four bytes of checksum. A frame holds at most 1500 bytes of data, which is where the limit on packet size comes from, the MTU. And at least 46: a shorter frame could be over before it “noticed” a collision, so our “LO,” if it ever left the loopback, would be padded with zeros to the required length.

Wired Ethernet today hardly knows collisions: every computer has its own cable to a switch, which passes a frame only to the port where the receiver sits, and in both directions at once. On the radio ether of Wi-Fi, though (the first IEEE 802.11 standard came out in 1997), collisions remain, and there they are harder to detect: a transmitter is deafened by its own signal and can’t hear anyone else’s. So Wi-Fi tries to avoid collisions instead, waiting for a pause plus a random extra, and acknowledges every frame. If the acknowledgment doesn’t come, the frame is sent again. The air loses a lot, and if Wi-Fi didn’t resend frames on its own, packets would vanish within the first meter.

Crossroads: addresses and routes

That address is the IP address: 32 bits, written as four bytes separated by dots, like the 127.0.0.1 in our envelope. A device that stands at the crossroads of several networks and forwards packets from one to another is called a router. When a packet arrives, the router reads the destination address and decides which of its outputs to send it through. But there are four billion addresses, and no router can remember every one.

What helps the mail helps here too. A mail sorter in Chicago doesn’t need to know every street in Boston: a letter marked “Boston” goes into the Boston bag, and they’ll sort it out there. An IP address is built the same way: the first bits name the network, the next ones a subnet within it, and the last ones the machine itself. A router stores only the beginnings of addresses, prefixes: “everything that starts with 10 goes right.” A prefix is written as an address and a number of bits after a slash: 10.0.0.0/8 is every address whose first 8 bits are the same as those of 10.0.0.0, that is, everything from 10.0.0.0 to 10.255.255.255. A list of such lines, each saying where to send what matches, is a routing table.

Prefixes nest inside one another, and an address often matches several lines. Then the longest matching prefix wins, because it is the most precise. It works like the address on an envelope: “USA” fits, “Boston, MA” fits, but “24 Beacon Street” decides. And the line 0.0.0.0/0, a prefix of zero length that matches any address, means “everything else goes to the provider.” It is called the default route.

The function matches compares only the leading bits: a right shift by $32 - \text{length}$ throws away the tail, which belongs to the machine rather than the network. For /0 the shift is 32, and nothing of any address survives but zero, so the default route matches everything. Our function goes through the whole table, but the routers at the edges of large networks hold more than a million IPv4 prefixes (that is how many the CIDR Report counted in October 2026), and packets arrive by the million every second. Going through the table won’t do. You’ll work out how to search faster in the task “The longest prefix.” One hint is close at hand: the sandbox’s own routing table.

The Linux kernel keeps its routing table in a trie from Chapter 27, only the letters in it are the bits of the address: a branch point 127.0.0.0/8, under it 127.0.0.0/31, and the leaves. Every path from the root spells out a prefix, and the longest matching one is found by walking down the tree: the number of steps depends on the length of the address, not on how many lines the table has. The output also gives away the sandbox’s secret: its table holds only the loopback, 127.0.0.0/8, and not a single route to the outside, not even a default one. So the kernel won’t even accept a packet that wants to go out into the world: Network is unreachable. That is how the course fences your code off from the internet. The addresses 203.0.113.x, by the way, belong to no one: they are set aside for examples in documentation, and so are 198.51.100.x.

Where the tables come from

Nobody types in a million lines by hand. Routers build their tables themselves by talking to their neighbors, and they do it in two ways you already know from Chapter 24. In the first, every router tells everyone whom it is connected to and what each link costs. From these messages each router learns the map of the whole network and computes the shortest paths to all the others itself, with Dijkstra’s algorithm. This is how the OSPF protocol works inside large networks. In the second, a router knows only its neighbors and regularly tells them: “I am so many steps from such-and-such a network.” A neighbor adds one and, if the path through you is shorter, rewrites its own line. This is the Bellman–Ford algorithm, only the edges are relaxed by hundreds of machines, each one on its own. Between the networks of different companies the protocol is BGP, and there contracts count as much as distances: through whose network a provider is willing to carry other people’s packets.

While the tables are being updated, they can disagree: A thinks the path goes through B, and B thinks it goes through A, and a packet starts going around in circles. To keep it from circling forever, the network envelope has a TTL field, “time to live.” Every router decreases it by one; a packet whose TTL reaches zero is thrown away, and its sender gets a short service message of the ICMP protocol: “time exceeded.” In our envelope the TTL was 64, which is what Linux sets by default. The traceroute program, which Van Jacobson wrote in 1987, is built on this: it sends packets with a TTL of 1, 2, 3… and learns which routers the path goes through from the ones that send back “time exceeded.” We’ll meet Jacobson again in the next chapter.

Rush hour: the queue at the output

A router takes in packets from several inputs and sends each one out through a single output. What if an output that carries a hundred megabits per second is asked for a hundred and twenty right now? The surplus has to wait somewhere. Every output has a buffer, a queue from Chapter 15, usually built on a ring buffer, and packets wait in it while the output is busy. If the queue is full, there is no room for a new packet, and the router throws it away without telling anyone.

Leonard Kleinrock, in whose lab Kline would later type “LO,” studied how queues grow. His dissertation, defended at MIT in 1963, was called Message Delay in Communication Nets with Storage, and it was built on queueing theory. Its main conclusion can be checked by experiment. Suppose sending one packet out of the output takes one unit of time, and packets arrive at random, $\rho$ per unit on average: $\rho$ is the output’s load, between zero and one. How long does a packet wait in the queue on average?

While the output is half loaded, a packet waits on average half a sending time, hardly noticeable. At 80% it waits two units, at 90% four and a half, at 95% about nine. The wait grows not in proportion to the load but like $\frac{1}{1-\rho}$: the last few percent of load cost more than all the others put together. The formula in the last column is a special case of the Pollaczek–Khinchine formula, for a queue that customers join at random and that serves each of them in the same time. At 99% the experiment parts company with the formula: the queue swings so slowly that even two hundred thousand packets are too few for the average to settle. You have seen the same law in traffic: a road loaded to 70% moves, and at 95% it stands still, though there are only a third more cars on it.

When the load is above a hundred percent, no buffer will save you: the queue grows until it is full, and from then on the router throws the surplus away. A large buffer only pushes that moment back and turns the queue into a long wait: a packet that stands two hundredth in line waits two hundred sending times. The danger was described as early as 1985, but it drew wide attention in 2010–2011, when it turned out that many home routers and modems keep huge buffers, and while a large file downloads, the delay on such a network climbs to seconds. Jim Gettys, who tracked it down, called the phenomenon bufferbloat. If your video call starts to lag as soon as someone at home downloads a game, that’s bufferbloat.

A death and a double

Here our packet’s biography may come to an end. It reached an output where the queue was full, and the router threw it away. Packets die in other ways too: interference garbles bits on the air and the checksum check rejects the frame, a router reboots, a TTL reaches zero. And almost always silently. An IP network guarantees nothing: it tries to deliver, but a packet may vanish, arrive twice, or overtake one sent earlier if that one took another path or got stuck in a queue. Delivery like this is called best-effort delivery.

One could make the network itself reliable, with every router checking and resending. Against this there is an argument that Jerome Saltzer, David Reed and David Clark set out in 1981 and called the end-to-end principle. Only the parties at the ends can guarantee delivery from start to finish, because a packet can also be lost after the last router, or in the receiver’s own memory. So the ends will have to check and ask again anyway, and if they must, the network in the middle is better left simple and fast. There are exceptions where checking on the spot is much cheaper: Wi-Fi resends frames itself because the air loses too much. But the last word always belongs to the ends.

That is how our packet acquires a double. The sender gets no answer, decides the packet was lost and sends a copy. How it knows when the time has come, how long to wait, and what to do if the original turns up after the copy after all: TCP was invented to answer these questions, and they take up the whole next chapter.

Time on the road

Suppose our packet was lucky. How long is it on the road? First we measure the shortest path there is, to the machine itself. The sandbox has no ping utility, but we can write one: ping sends an ICMP service message, an “echo request,” and the kernel at the other end answers with an “echo reply” carrying the same data.

A few microseconds there and back, and nearly all of it is the kernel at work: system calls, copying bytes, switching between sender and receiver. There is no distance here. On a network between cities, physics joins in. Light in optical fiber travels about a third slower than in a vacuum, at roughly 200,000 kilometers per second, and no amount of money will make a signal go faster.

That is a lower bound, as the crow flies. Cables don’t run in straight lines, and distance is only one of the terms. A packet’s time on the road adds up from four parts:

• propagation: the distance divided by the speed of the signal, and there is no getting around it;
• transmission: the size of the packet divided by the speed of the link; 1500 bytes on a link of 100 megabits per second go out onto the wire in 0.12 milliseconds;
• queueing: how long the packet stood in buffers, anywhere from zero to seconds;
• processing: how long a router thought about where to send it, usually microseconds.

In the section “If a cycle were a second” of Chapter 34, a packet across the ocean and back traveled for sixteen years. That figure came from the first term, propagation. But when an ad promises “500 megabit internet,” it is talking about something else: how much data the link lets through per second. That is bandwidth. It doesn’t make a packet any faster, but it lets more packets travel at once. A ten-lane highway doesn’t make the drive from New York to Boston any shorter; it lets more cars through. Latency is when the first bit arrives; bandwidth is how quickly the rest follow. Link speed is measured in bits and files in bytes: 500 megabits per second is 62.5 megabytes.

Latency and bandwidth are linked in one more way, and it explains why a network cuts data into small packets. A node passes a packet on only after it has received the whole of it. If a megabyte goes through five nodes in one piece, each node waits until the entire megabyte has reached it. Packets, though, move like a pipeline: while the second node passes on the first packet, the first node is already passing on the second.

In one piece, a megabyte takes twelve seconds to cross fifteen links; in packets, 0.82. Each extra link adds the time of one packet, not the time of the whole message. This is the same laundry pipeline as in the processor of Chapter 35. The formula in packets is simplified: it leaves out propagation, the headers, and the fact that the last packet is usually shorter. The exact count is in the task “How long a file takes.”

The pigeon versus the link

If bandwidth and latency are different things, they can have different champions. This was put to the test in South Africa.

These figures give an estimate of the line: 4% of 4 gigabytes in 7617 seconds is less than 200 kilobits per second. The pigeon “transmitted” 32 billion bits in the same time: 4.2 megabits per second, twenty-five times faster. But try sending a single ping by pigeon. The pigeon’s latency is an hour; the line’s is a fraction of a second. Andrew Tanenbaum, the author of a classic textbook on networks, put it this way: “Never underestimate the bandwidth of a station wagon full of tapes hurtling down the highway.” Find out for yourself where the boundary lies: choose the amount of data, the distance and the link.

The pigeon is only half a joke. When customers have hundreds of terabytes to move, cloud companies accept their data on disks shipped by truck or by mail: over a link, volumes like that would take months. For a conversation, a game or a ping, though, latency decides, and there any wire beats any bird.

Arrival

The last router handed the packet to the network where the receiver lives, the link layer carried it to the network card, and the kernel checked the IP header’s checksum and found its own address there. The packet is home. But dozens of programs run on the machine, and each is waiting for something of its own. Who gets the two letters? Now the transport envelope is opened, and one number in it decides: the port. A program that expects data asks the kernel for a port number in advance (that is what bind did in the very first cell), and the kernel gives it everything that arrives for that number. The machine’s address is like the address of a building, and the port like an apartment number.

Two packets came to one address and went their separate ways, to different programs, by their port numbers. The last packet came to a place where nobody was waiting. The kernel didn’t drop it in silence: it sent back an ICMP service message, “port unreachable,” and the sender’s kernel turned that into the error Connection refused. The port numbers you see in the output were picked by the kernel from the free ones, because the program asked for port 0. Well-known services have fixed numbers: a web server waits on 80 (and on 443 for secure connections), a mail server on 25.

In one day our two letters were born in a program, got a transport envelope with port numbers, a network envelope with addresses and a TTL, and a link envelope with the addresses of network cards. At every step the link envelope was swapped for a new one and the TTL went down by one; the letters stood in queues, risked death when a buffer overflowed, and at last reached the program that was waiting for them. Millions of such lives are lived every second, and no node in the network sees the whole picture: nobody is in charge, and each node only hands a packet on to a neighbor that is closer to the goal. This is the first piece of the answer to the course’s sixth big question, how billions of computers work together when none of them is in charge. The other pieces come in the next three chapters.

Tasks

Three tasks, one for each of the three crafts of the network layer: find a route, work out the time, cut up and put back together. Each has a large input with a time limit.

What next

Our packet was lucky. Now let the program send not two bytes but a one-megabyte file cut into seven hundred packets, and let the network behave the way it is allowed to: a full queue throws one packet away, three pairs take different routes and arrive in reverse order, and one router sends a packet twice.

That is what the text looks like if you glue together everything that arrived. Packets get lost and arrive out of order. How does a file arrive whole? The network won’t answer: it is allowed to lose things. The ends will have to answer, the sender and the receiver, and for that they need to agree on rules for talking through an unreliable go-between. You can invent such an agreement yourself, step by step, and discover at the end that you have invented TCP. That is what we do in the next chapter.