Putting It Back Together

You have two thousand pieces of a photograph and no way to tell what order they go in, whether any are missing, or whether any have arrived twice. The receiving operating system is gluing them together in the order they show up, and the result is a courtyard with a seam through the brickwork and the bottom half sheared into streaks. Everything wrong with that picture comes from one omission, which is that the pieces do not know who they are.

So give every piece a number. Piece zero, piece one, piece two, and so on up to piece two thousand and forty-nine. The number goes in the header, and in particular in the port header from Chapter 7, since this is a matter between the two operating systems and nothing in the middle needs to see it. Two bytes will do. Then let’s see what Mira’s operating system can do that it could not do before.

Take the pieces that arrive out of order first. Piece 1043 arrives before 1042. Instead of gluing it on the end, her operating system reads the number and puts the content where it belongs, at position 1043 in a buffer laid out to hold the whole photograph. When 1042 arrives a moment later it goes into position 1042. The program reading from the socket is only ever handed bytes from the front of that buffer, in sequence, and never learns that anything was out of order. The seam in the brickwork is gone.

Now the piece that arrives twice. Piece 1500 arrives, and then piece 1500 arrives again. Her operating system reads the number, sees that position 1500 is already filled, and throws the second copy away. The shift to the late side is gone. Two of the three failures have been fixed by a number, which is a good return on two bytes of header.

The third failure is different. Piece 1499 arrives, and then 1501. Her operating system now knows something it could not have known before: there is a hole at 1500. It can see the gap. It can refuse to hand the program anything past 1499 until the gap is filled, so the program never sees a sheared photograph; it sees a photograph that is taking a while to finish. But knowing about a hole is not the same as filling it. Piece 1500 is gone, because a router dropped it, and it is not going to arrive however long she waits. The only copy that exists is on your machine, and you have no idea it is needed.

So far in this book every message has gone one way. You send and Mira receives. For loss that is not enough. The only party who can fix a missing piece is the sender, and the only party who knows a piece is missing is the receiver, so the two of them have to talk. The simplest arrangement is that every time Mira’s operating system receives a piece, it sends a tiny message back saying that it got 1499, or whichever piece it was. You keep a list of what she has confirmed, and if you have sent 1500 and never hear that she got 1500, you send it again.

That works, and it is the right idea, but it is chatty, one message back for every message forward. There is a tidier way to say the same thing. Since Mira only ever hands bytes to her program in sequence, what matters is how far the unbroken sequence goes, so instead of confirming each piece she reports one number: she has everything up to and including 1499. That single number summarises her whole state. When 1501 arrives without 1500 she says it again, everything up to 1499, because that is still true. When 1502 arrives she says it a third time. You, the sender, hear “up to 1499” three times in a row while you are busy sending 1502, 1503 and 1504, and the pattern tells you what happened: 1500 did not make it. You send it again, she slots it into place, her next message says everything up to 1504, and the two of you are caught up. The messages she sends back are called acknowledgements, and the summarising kind, which says everything up to here, is a cumulative acknowledgement.

There is something implied in “send it again” that ought to be made plain. You can only send a piece again if you still have it. When your program wrote three megabytes to the socket, your operating system did not push the bytes onto the wire and forget them. It cannot afford to. It has to keep a copy of every piece until Mira has confirmed it, because until she has, any piece might need to go out a second time. So there is a buffer on your side as well, holding pieces that have been sent but not yet acknowledged, and as acknowledgements come in the confirmed pieces are released from it.

That buffer has a size, and the size is a limit. Your program can write to the socket faster than acknowledgements come back, and when it does, the buffer of unacknowledged pieces fills up. What happens then is the subject of Chapter 14. For the moment it is enough that the mechanism you built for loss has given the sender something to hold on to, and things that are held on to take up room.

Now comes the hard part. Suppose all the pieces after 1499 are lost, because a router’s queue overflowed for a solid stretch. Mira gets 1499 and then nothing. She acknowledges up to 1499 once, and then has nothing further to acknowledge, so she goes quiet. You are sitting with pieces 1500 onward in your buffer, hearing silence. Or suppose the pieces got through perfectly well but the acknowledgement was lost on the way back. Mira has everything, she said so, and the saying did not arrive. From your side it is the same silence.

Silence means resend, and the question is after how long. Wait too little and you resend pieces that were merely slow. They arrive twice, and Mira’s operating system discards the duplicates, so nothing breaks, but you have filled a path that was already struggling with copies of things it had already carried, and it struggles more. Wait too long and a single lost piece stalls the whole photograph for the length of your patience, while Mira’s program sits at 1499 and waits.

There is no number that is right. A wait that is sensible across a courtyard is absurd across an ocean, where the round trip alone is a hundred times longer. The same path is fast at three in the morning and slow at eight in the evening. Any fixed value is wrong most of the time. So you do not fix it. You measure it. Every time you send a piece and get its acknowledgement back, you learn how long a round trip currently takes, and you keep a running estimate. You set the wait to somewhat more than that estimate, enough more to allow for an acknowledgement that is a little slow rather than lost, and you keep updating it, because the path changes under you.

This is the retransmission timer, and the estimate it is built on is the round-trip time. Neither one is a constant. Both are guesses that improve. It is the first time in this book that you have had to answer the question of how long to wait before deciding that something has failed, and you have not really answered it. You have built a way to keep guessing. The question is going to come back at every layer, and it will never have a clean answer. You will ask it about a machine that has gone silent, about a request to a server that has not replied, about a lock that has not been released. Each time the honest answer will be the one you found here: measure, estimate, add a margin, and accept that you will sometimes be wrong in both directions.

Go back to the second kind of silence, where the pieces arrived and the acknowledgement did not. Your timer runs out and you resend 1500 through 1510, and Mira already has them. Her operating system discards the copies, because of the numbering, and the photograph is fine. But look at what has happened structurally. The mechanism you built to fix loss has produced duplicates. Chapter 10 warned you that it would, and it has, on the very first lost acknowledgement. Your fix for one failure is a generator of another, and the only reason it is harmless is that you happened to build the defence against duplicates first.

This deserves to be stated as a principle, because it governs a great deal of Part III. Anything that resends on silence will sometimes resend something that arrived, and so the receiver must be able to receive a thing twice and behave as if it had received it once. Here, at the bottom of the tower, that is easy. The pieces have numbers, so a repeat is obvious and discarding it is safe. Higher up it will not be easy. When the thing being sent is “post this message” or “charge this card”, and the acknowledgement is lost, and the sender resends, the receiver had better be able to tell that it is a repeat, or Mira gets two messages and you are charged twice. You will spend Chapter 20 on that. The shape of the problem is this one, and you have now seen it in its simplest form.

Let’s step back and look at what you have built, because it is the most important idea in Part I. The path between you and Mira loses pieces, reorders them, and occasionally duplicates them. It makes no promise otherwise and never will. On top of that path, with nothing but numbers, acknowledgements, a buffer and a timer, you have built something that delivers every byte, once, in order. Reliability, then, is not a property of the wire but an agreement between the two ends. Nothing in the middle became more dependable. The two operating systems agreed on a way to notice every failure and repair it, and the program above them sees a stream that never fails. The whole internet rests on this arrangement: an unreliable core, and reliability manufactured at the edges by mutual agreement.

The photograph arrives intact. Every one of two thousand and fifty pieces is placed, gaps are noticed and filled, repeats are discarded, and the program on Mira’s side reads three megabytes off the socket without ever knowing how much went wrong underneath. You have built all of this on one assumption you have not examined, which is that both sides agree on where the numbering starts. You started at zero because it was obvious. In the next chapter that turns out to be a mistake, and fixing it is what turns a stream of numbered pieces into something you would recognise as a connection.