Inventing a protocol

The last chapter ended with a garbled sentence: packets get lost and arrive out of order, so how does a file arrive whole? The network has no answer to that; it is allowed to lose things. The ends will have to answer it, the sender and the receiver, and for that they need an agreement, a protocol. We’ll invent one ourselves, move by move, without peeking at the finished one. Each move will repair what broke on the move before, and the link will keep finding new ways to ruin everything.

The terms of the talks

We need a link that behaves like a network but has knobs we can turn. The sandbox has one: the cs.netsim module. A Link object is a link between a sender and a receiver: link.send(packet) sends a packet, and the list link.arrived shows what reached the other end and in what order. Time on the link is make-believe and counted in round trips: a packet takes half a round trip to go one way, plus a random delay. The link’s parameters are loss, the share of packets lost; dup, the share duplicated; and jitter, the spread of the delay, which lets packets overtake one another. We send a sentence one letter at a time.

The D of AND has vanished, and so have two letters of ORDER; a T came twice, and several letters changed places. Run it again with a different seed: the accidents will be different, the trouble the same. Here are the rules of the game. The link may lose any packet, in either direction, duplicate it, or delay it so that later ones overtake it. It can’t corrupt the contents: we assume that the checksums of the last chapter catch corruption and a damaged packet is thrown away, so corruption turns into loss. We are allowed two things: to write anything we like into the packets, and to agree on what each end does when a packet arrives or fails to.

Move one: numbers

The obvious first step is to number the packets. The number carried by each packet is called a sequence number. The receiver lays the data out by number rather than in order of arrival.

One move, and two troubles out of three are fixed. A duplicate lands in the same place as the original, and overtaking confuses nothing, since the number decides the place. Loss remains, but at least now it shows: the receiver knows that the letters numbered 19, 36 and 38 never came. It can ask for them again. But what if the request itself gets lost? And what if the last packet is lost: how would the receiver know it ever existed? A receiver that stays silent guarantees nothing. Both sides have to talk.

Move two: acks and a timer

Here is the deal: the receiver answers every packet with a receipt, “packet number such-and-such received.” Such an answer is called an acknowledgment, ACK for short, and we’ll call it an ack. Having sent a packet, the sender sets a timer. If the ack arrives, the sender moves on to the next packet. If the timer goes off first, either the packet or the ack was lost, and the packet has to be sent again. The time the sender waits before it decides to resend is called the retransmission timeout. A protocol in which the sender waits for the ack of each packet before sending the next is called, plainly enough, stop-and-wait.

The module’s receiver already knows these rules. With the parameter receiver="ack" it expects packets of the form (number, data), hands the data to the program strictly in order, each piece once, and answers every packet it receives with ("ack", number). The sender collects the answers with link.wait(), which waits for an answer and returns it, or returns None if the timer went off first. Here are two senders. The first, a trusting one, takes any ack that arrives as confirmation of its own packet. The second, a careful one, checks the number.

The trusting sender got three letters through. Delays on this link are sometimes longer than the timer, and acks are sometimes duplicated. The sender resent a packet, and then two acks for it came back: a late one for the original and another for the copy. It accepted the first, moved on to the next packet, and took the second ack, an old one, as confirmation of the new packet. If the new packet was lost meanwhile, the sender will never find out: it believes everything arrived and carries on, while the receiver is stuck at the gap and accepts nothing after it. The careful sender got everything through, and paid for it: 96 sends for 40 letters and more than a hundred round trips.

One bit works only as long as no more than one packet is on the way and packets don’t overtake one another. On our link they do overtake, so our numbers keep counting: 0, 1, 2 and so on. Switch the mechanisms on one at a time and see what each one fixes, and what breaks without it.

You’ll write a stop-and-wait sender of your own in the task “Stop and wait”: in its tests the link loses, duplicates and delays packets in ways that trust won’t survive.

How long to wait

When should the timer go off? Too early, and the sender sends copies of packets that haven’t had time to arrive yet and clogs the link. Too late, and the link stands idle after every loss. The right time is a little more than the usual round-trip time. But that time differs from one partner to another (across a table, microseconds; across an ocean, a hundred milliseconds), and it changes on the fly as queues grow. So TCP measures it from the acks and keeps two quantities: a smoothed average $\bar R$ and a smoothed deviation $D$. Each new measurement $R$ pulls them a fraction of the way toward itself:

$$D \leftarrow \tfrac{3}{4} D + \tfrac{1}{4}\,|R - \bar R|, \qquad \bar R \leftarrow \tfrac{7}{8}\bar R + \tfrac{1}{8}R, \qquad \text{timeout} = \bar R + 4D.$$

Van Jacobson added the deviation to the formula in 1988; we’ll come to his other fixes in the section on congestion. The earlier standard said to take the average multiplied by a fixed factor between 1.3 and 2, and when delays jumped about, such a timer kept going off too early. And if the timer does go off, the next timeout is doubled: the network may be congested, and hurrying it with resends won’t help.

Move three: don’t wait for every ack

The protocol works, but consider its speed. In one round trip the sender delivers one packet. A round trip from New York to Moscow takes about a hundred milliseconds, and a packet is 1500 bytes. So stop-and-wait delivers 15 kilobytes per second, 120 kilobits, whether or not the link carries a gigabit: the rest of the time the link stands idle while the sender waits for an ack.

The way out is not to wait: let the sender keep several unacknowledged packets on the way at once. How many it may keep is called the window. The sender sends packets as long as there are fewer unacknowledged ones than the window allows; when the ack for the first of them arrives, the window slides forward and one more can go. This is the sliding window. The sender keeps unacknowledged packets until their acks come, in case it has to resend them. The handiest place for them is a ring buffer from Chapter 15: packets go in at one end as they are sent and leave at the other once they are acknowledged.

First, on a link without losses: how does the time to send a thousand packets depend on the window? A packet goes out onto the wire in a hundredth of a round trip, so the link carries a hundred packets per round trip. The timer never goes off here, but it is in the code: after a loss the sender goes back to the first unacknowledged packet and resends everything in the window.

Each doubling of the window halves the time, until the window reaches a hundred. Then the gains stop: the link is already busy to the limit, and extra packets only wait their turn to go out. The number at which this happens is how much data fits “in the wire” in one round trip: the bandwidth multiplied by the round-trip time. It is called the bandwidth-delay product. For a gigabit per second and a hundred milliseconds it is 12.5 megabytes: that much data has to be on the way for the link not to stand idle. A sender with a window can reach that speed; stop-and-wait never can.

A window runs up against the receiver as well as the link. If the receiver can’t keep up (the program at the other end is busy), its buffer overflows, and everything new has to be thrown away. So in every ack the receiver says how much free room it has left, and the sender keeps no more than that on the way. This is flow control. The TCP header gave the window size 16 bits, so the window couldn’t exceed 64 kilobytes. For a gigabit across an ocean that is almost two hundred times too small, so in 1992 came RFC 1323, an extension that lets the window be multiplied by a power of two, up to a gigabyte. Its authors called such a network a “long, fat pipe.” The sandbox has it switched on; we’ll find it there when we question the kernel about a live connection.

With a window, losses cost more. After a loss our sender resends the whole window, though nearly all of it arrived; this scheme is called go-back-N. A tidier scheme exists: the receiver keeps the packets that came out of order in a buffer and reports which pieces are missing, and the sender resends only those. In TCP these are selective acknowledgments, SACK.

What we invented

Numbers, numbered acks, a timer set from measured times, a window, flow control: together, all of this is TCP, the Transmission Control Protocol. It differs from our invention in only a few ways. TCP numbers bytes: the number in a segment is the number of its first byte in the stream. TCP’s acks are cumulative: “I am waiting for byte number such-and-such” means that everything before it has arrived, so losing one ack spoils nothing, since the next one covers it. And the program sees not packets but a continuous stream of bytes, as in a file or a pipe from Chapter 36, only this stream runs between machines.

Our invention lacked one thing: an introduction. Before it transfers data, TCP sets up a connection by exchanging three segments. The client sends SYN (“I want to connect; my numbers start at x”), the server answers SYN-ACK (“agreed; I got your x; my numbers start at y”), and the client confirms with ACK (“I got your y”). This is the three-way handshake. Three segments is the smallest number after which each side knows both that it is heard and that it hears the other. The starting numbers are chosen at random. Otherwise a late segment from an earlier connection between the same ports could wander into the new one and land in someone else’s data, and an attacker could forge segments by guessing the numbers.

Saying goodbye follows rules too: each side sends FIN (“I won’t write any more”) and gets an ack for it. And whoever closed first remembers the closed connection for a while longer, in the TIME_WAIT state, so that stray copies of the last segments have time to die instead of turning up in a new connection with the same port numbers. We’ll soon catch this state in the kernel’s table.

Reliability isn’t always wanted. To a video call, a packet that arrives a second late is already useless: the picture has moved on, and a resend would only hold up the next frames. So TCP has a neighbor, UDP, the protocol of the inner envelope from the last chapter: ports, a length, a checksum, and nothing else. Video calls, online games and DNS run on UDP. In DNS a question and its answer each fit into one packet, and asking again is easier than setting up a connection. And when reliability is needed after all, but of a particular kind, people build it on top of UDP themselves: that is how QUIC works, and a good part of the web travels over it today.

Real TCP in the sandbox

Enough models. The sandbox has no way out to the internet, but the loopback works, and we can run the Linux kernel’s TCP over it, with a server and a client in one program. First, the difference between the two transports: we send three words over UDP and three over TCP.

UDP delivered three datagrams separately, TCP one glued-together string. This is no bug; it is what a stream means. TCP promises to deliver bytes in order, but it doesn’t promise to keep the boundaries between sends. A single recv may return half of what was sent, or three sends at once. If a program needs separate messages, separating them is its own business: with a newline, or a length at the start of each message. Nearly everyone who writes a network program makes this mistake first, and the task “Echo” is built on it.

The server in this cell follows the usual pattern. bind ties the socket to an address and a port, listen announces that it accepts connections, and accept waits for a client and hands out a new socket for each connection. The listening socket goes on listening, and the conversation with each client goes through a socket of its own. Now we spy on the handshake. The segments themselves can’t be caught in the sandbox (that takes privileges we don’t have), but the kernel keeps counters and a table of connections, and we can read them in /proc.

Three segments on the dot: SYN, SYN-ACK and ACK. Both ends of the connection live in one kernel, so the counter sees all three. The table writes port numbers in hexadecimal, and the function turns them into ordinary ones. The server listens on its own port, and the client’s port is random: the kernel picked it from the range for ephemeral ports, which in the sandbox is 32768–60999. After the handshake each side has its own ESTABLISHED line. When the client closes, it waits for the other side’s goodbye (FIN_WAIT2), while the server has learned of the close and waits for its own program to close too (CLOSE_WAIT). Once both have closed, the server forgets the connection at once, but the client keeps it in TIME_WAIT. Linux keeps it there for a minute.

Next, two errors that everyone who works with networks runs into.

Both errors come from the same segment, RST, “reset.” In the first case the server’s kernel answered the SYN: nobody is on this port. That is what “connection refused” looks like: the machine is reachable, but the program isn’t running or listens on another port. In the second case the program at the other end closed its socket without saying goodbye, which happens when it has crashed or been stopped, and the kernel reset the connection: “connection reset by peer.” The third common error, “timed out,” means that nobody answered at all: the packets are lost on the way, the machine is off, or a firewall quietly throws them away. The text of the error tells you where to look: in the program, on the machine or in the network.

Last, a server for many partners. It serves each one in a separate thread from Chapter 39: while one client is silent, the others don’t wait. The threads share no data here, so the races of that chapter can’t happen.

October 1986: everyone is right, and the network stands still

Our protocol is polite to the receiver but gives no thought to the network. And the network is made of shared queues at the routers, the ones we met in the last chapter.

The mechanism of the collapse becomes clear when you put two facts together. A router with a full queue throws packets away. A sender that gets no ack resends the packet, into the same full queue. Each sender on its own behaves correctly: it doesn’t know its packet was thrown away because of the crush, and it keeps trying to deliver it. Together, though, the senders add load when it ought to be taken away. Queues grow, delays grow, timers go off before the acks arrive, and the network carries copies of packets that would have arrived anyway. Fewer and fewer useful bytes get through, though the wires are fully loaded. This is congestion collapse, and what makes it so dangerous is that it feeds itself.

Jacobson’s cure was to treat loss as a signal. If a packet is lost, most likely a queue somewhere on the path is full, and the sender should slow down. For this the sender gets a second window, the congestion window: how many packets it dares to keep in the network. There are never more packets on the way than the smaller of the two windows allows, the one the receiver granted and the one the network can bear. The sender chooses the congestion window itself, by a simple rule:

• for every round trip without losses, the window grows by one packet;
• for a loss, the window is cut in half.

The rule is called AIMD: add a little, take away a lot. The window creeps up, feeling for how much the network will bear, hits a loss, drops by half and creeps up again. On a graph it makes a sawtooth. And so that a new connection doesn’t spend too long creeping up to the right speed, at the start the window doubles every round trip. Oddly enough, this acceleration was named slow start: slow compared with releasing the receiver’s whole window into the network at once, as senders did before 1988.

The rule “add one, or halve” has a second virtue: besides finding the network’s limit, a flow shares the network with its neighbors. Suppose two flows share a link that carries a hundred packets per round trip, and the first has sped up to seventy by the time the second starts. We compare AIMD with a rule that both adds and takes away a little.

Under AIMD the gap between the flows melts away. They add the same amount, and at each loss the larger one loses more, so every loss halves the difference between them. After a hundred and fifty round trips they share the link almost equally. Under AIAD the increase and the decrease are the same for both, the difference between the windows never changes, and the first flow stays ahead forever by the same 65 packets, on average six times faster than the second. In 1989 Dah-Ming Chiu and Raj Jain proved that among simple rules of this kind only AIMD reaches a fair split and a full link from any starting point.

The last knob in the widget shows a weakness of AIMD: a flow with a long round trip adds less often and gets less. Linux today uses CUBIC by default (since 2006): after a loss its window grows along a cubic curve and quickly returns to its earlier level. In 2016 Google proposed BBR, which steers by measured latency and rate instead of by losses. The principle is the same for all of them, though: the network is shared, and each sender slows down by itself when it is congested. And here is what the sandbox’s kernel knows about a connection of its own.

The algorithm is CUBIC. A round trip over the loopback usually takes ten to twenty microseconds, yet the timer is about 200 milliseconds all the same: Linux won’t set it any shorter, however fast the network, so as not to resend packets for nothing. The congestion window after ten megabytes is somewhere between fifteen and twenty-five segments, but a segment on the loopback is huge, almost 64 kilobytes. The numbers vary a little from run to run. The last two lines are kernel settings: the window scaling of RFC 1323 and selective acknowledgments are both switched on.

The addresses ran out

One part of the header is left: the addresses. An IPv4 address is 32 bits, which makes $2^{32}$ of them in all, a little under 4.3 billion. In 1981, when the IP standard came out, that looked like an inexhaustible supply. There are more than eight billion people on Earth now, and many of them have a phone, a laptop and a TV each.

To see how the internet manages without them, we start with how addresses are divided up. We already know that an address has two parts: the first bits are the network, and the rest are the machine in it. Where the boundary lies is given by the prefix length, /26, or, the old way, by a mask: 32 bits with ones where the network is and zeros where the machine is. The network address is the address with the machine bits set to zero, and the last address, with all of them set to one, is the broadcast address, “everyone on the subnet.” Both are taken, so a subnet has room for two fewer machines than it has addresses. All of it is computed with the bit operations of Chapter 28.

In the last line the standard ipaddress module computes the same thing: in a working program, use it, and use the bits to understand what it does. The prefix length can be anything. Before 1993 addresses were handed out in only three sizes, classes A, B and C, of 16 million, 65 thousand and 256 addresses, and a company that needed two thousand addresses had to be given 65 thousand. Classless addressing, CIDR, with prefixes of any length, slowed both the drain on addresses and the growth of routing tables. Play with the mask yourself.

One address for the whole apartment

Look up the address of your home computer: it almost certainly starts with 192.168 or with 10. These are private addresses: in 1996 the standard RFC 1918 set aside three ranges, 10.0.0.0/8, 172.16.0.0/12 and 192.168.0.0/16, for internal networks. Anyone may use them at home, and millions of apartments have a 192.168.1.23 of their own. On the internet such addresses mean nothing.

And yet the packet of the last chapter got from such an address to a server, and the answer found its way back. That was the work of NAT, network address translation. When the home router lets a packet out, it replaces the private sender address with its own single public address, and the sender’s port with a free number of its own, and writes the pair into a table: “my port 61022 is 192.168.1.23, port 50000.” The answer comes to port 61022; the router finds the line, swaps the address back and passes the packet to the laptop. This is the swap you saw when you followed the packet in the last chapter. NAT was proposed in 1994 as a stopgap until something better came along, and it ended up everywhere.

NAT has a consequence you may have run into. You can’t connect from outside to a computer on a home network: a packet that reaches the router without a matching line in the table has nowhere to go. So for a home server people “forward a port” on the router by hand, and video calls and games resort to clever workarounds. Often the provider, too, hides thousands of subscribers behind one address of its own, so packets pass through NAT twice.

Only longer addresses can cure the shortage. In IPv6 an address takes 128 bits: $2^{128} \approx 3.4 \cdot 10^{38}$, or $8 \cdot 10^{28}$ addresses for every IPv4 address. They are written as eight groups of hexadecimal digits separated by colons, and long runs of zeros are abbreviated: the loopback, our 127.0.0.1, is ::1 in IPv6. It works in the sandbox too.

The move to IPv6 is slow because the old ways still work: NAT, private addresses, a secondary market where IPv4 addresses are bought, sold and rented out. But it is happening. According to Google’s statistics, on Saturday, March 28, 2026, the share of its users who arrive over IPv6 passed one half for the first time. So far this happens only on weekends; on weekdays the share stays around 46–47%. IPv6, it seems, is more common at home than on office networks.

Tasks

Three tasks, one for each floor of the chapter: a protocol over a model link, a server on the kernel’s TCP, and an address plan for an office.

Write send_file(chunks, link), a stop-and-wait sender. chunks is a list of the file’s pieces (any values at all), and link is a Link from the cs.netsim module with the receiver receiver="ack". That receiver accepts packets (number, piece) numbered 0, 1, 2…, hands the pieces to the program in order and once each, and answers every packet it receives with ("ack", number). A packet that comes before its turn it throws away, repeating the ack for the last piece it accepted. link.send(packet) sends a packet, and link.wait() returns the next answer, or None if the timer went off first. In the tests the link loses packets and acks, duplicates them and delays them, so an ack may arrive after the timer has gone off. The receiver must assemble the original list without distortion, and the sender must send nothing extra: on a link without losses, exactly one send per piece.

First the timer: if wait() returned None, the packet or its ack was lost, and the packet has to be sent again. Repeat until the ack comes.

Now the ack’s number. Compare the answer with ("ack", seq): a late ack for the previous piece is no reason to move on to the next one. Nor is it a reason to send the packet again: that ack came late, and yours may already be on its way. Wait for the next answer.

Three outcomes of waiting, three branches: your own ack, silence, someone else’s ack. Someone else’s ack can’t be taken for yours (that is how the trusting sender of the chapter breaks), and it can’t be taken for silence either. If you answer every late ack with a resend, the resends produce new acks, those come late in turn and produce new resends: a small congestion collapse on a single connection. The receiver needs the numbers so as not to take a repeat for a new piece, and that is why no comparison of contents will help in the test with identical pieces in a row.

In the mountains an echo sends words back reversed, at least in this task. Write serve(server): the function receives a listening TCP socket and serves the clients who connect to it, forever. A client sends lines of text in UTF-8, each ending with a newline, \n. To each line it receives, the server answers with the same line reversed, also ending with \n: to "hello\n", it answers "olleh\n". Clients connect at the same time, and while one of them is silent, the others must not wait. The tests run serve in a separate thread and connect to it with ordinary sockets over the loopback.

The starter makes three mistakes. It reverses whatever recv returned, and that may be half a line or three lines at once, \n included. Collect the bytes you receive in a buffer and cut whole lines off it at each \n.

The second mistake: decode() on a piece that ended in the middle of a letter. In UTF-8 “ï” and “é” are two bytes each, and a piece can split them apart. Split the bytes into lines and decode whole lines: in UTF-8 the byte \n never occurs inside a multibyte letter, as you may remember from Chapter 28.

The third: handle(conn) runs in the same thread as accept, so while it serves the first client, the second waits. Run handle in a separate thread, as in the cell echo.py.

A buffer and splitting at a delimiter are what every network protocol does with a stream: HTTP in the next chapter reads its headers the same way, up to an empty line. Python can do it for you: conn.makefile("r", encoding="utf-8") turns a socket into a file, and lines are read from it with an ordinary for line in f, with the same buffer inside. A thread per client is the simplest way to serve many at once; when clients number in the tens of thousands, servers switch to a single thread with an event loop, as in asyncio from Chapter 37.

An office has been given a block of addresses, for example "10.0.0.0/24", and it has to be carved into a subnet for each department. Write plan(block, sizes): sizes says how many machines each department has, and the answer is a list of subnets in the same order, a string like "10.0.0.128/26" for each department, or None if the departments don’t fit into the block. The rules are these. In a subnet of $2^k$ addresses, the machines get $2^k - 2$: the first address is the network address and the last is the broadcast address; the smallest subnet has four addresses. Each department gets the smallest subnet that fits it. Hand out subnets from the start of the block, one after another, from the largest departments to the smallest, and departments of equal size in the order of the list. For example, plan("10.0.0.0/24", [50, 20, 100, 2]) is ["10.0.0.128/26", "10.0.0.192/27", "10.0.0.0/25", "10.0.0.224/30"].

The starter forgets the two reserved addresses: a department of 64 machines won’t fit into a /26, which has room for 62. And it never checks whether everything fit into the block: the end of the block is its start plus $2^{32 - \text{length}}$.

Why from the largest to the smallest? A subnet of $2^k$ addresses must start at an address divisible by $2^k$, or it can’t be written as a prefix. If you hand them out in list order, a subnet of 128 that comes after a subnet of 4 would start at address 4, and that isn’t allowed. Going from the largest to the smallest, each next piece starts at a multiple of its own size by itself.

Sort the department numbers: sorted(range(len(sizes)), key=lambda i: -sizes[i]). Sorting in Python is stable, so departments of equal size stay in list order. Put the answers into a list of the right length by those numbers.

This is the greedy algorithm of Chapter 23, and here it is exact: the sizes are powers of two, so handing them out from the largest to the smallest leaves no holes, and the alignment takes care of itself. If everything fits in any arrangement at all, it fits in this one. Network engineers call such a plan VLSM, variable-length subnet masking, and draw one up for every new site. The ipaddress module can do the same piece by piece: ip_network("10.0.0.0/24").subnets(new_prefix=26) cuts a network into /26 subnets.

What next

Now any two programs can exchange bytes reliably, as long as they know each other’s address and port. But you never type an address like 198.51.100.10 and port 443 into a browser. You type a name.

The sandbox knows the port number from the file /etc/services, but it can’t turn the name into an address: Temporary failure in name resolution. It has been cut off from the internet, and with it from the service that answers the question “what is the address of legost.in?” Who answers it for you? You type legost.in and press Enter. What happens before this page appears: which packets go out, in what order, and how many milliseconds does each step take? That is the subject of the next chapter, and the page we’ll be looking at is the one you are reading now.