Reliable delivery is built out of nothing over four protocols, one mechanism at a time — and every mechanism is added only when the channel forces it.
Words you will meet
- Reliable channel — an imaginary pipe in which nothing is lost, damaged or reordered.
- Finite state machine — a drawing of a protocol as a few states with labelled arrows between them.
- ARQ — Automatic Repeat reQuest: fixing errors by asking for the data again.
- ACK / NAK — the receiver saying “that arrived correctly” or “that arrived damaged”.
- Stop-and-wait — a sender that will not touch new data until the last packet is settled.
- Sequence number — a number in each packet so the receiver can tell a copy from something new.
Why this matters
If you had to name the ten most important problems in networking, this would be a candidate to lead the list. How do two machines communicate reliably over something that damages and loses what they send?
It is not only a transport-layer question. The same problem appears at the link layer and in applications, and it is solved the same way each time. Everything TCP (Transmission Control Protocol) Transmission Control Protocol The Internet transport protocol that delivers data reliably and in order, with flow control and congestion control. introduced in ch. 1 does in section 3.5 is one of the mechanisms built here.
The method matters as much as the result. Each protocol makes the channel a little worse and adds exactly one thing to cope. Nothing appears before it is forced to.
| What the channel may now do | What broke | What we added | |
|---|---|---|---|
Cells marked ⓘ have an explanation — click to read it. Sortable columns have a ↕ in the heading.
Each protocol answers exactly one new thing the channel is allowed to do. Nothing is added before the channel forces it.
The framework
The service given to the layer above is a reliable channel reliable channel Simple An imaginary pipe in which nothing is lost, nothing is damaged and nothing arrives out of order. Precise The service abstraction a reliable data transfer protocol provides to the layer above: no transferred bit is corrupted or lost, and all bits are delivered in the order they were sent. It is exactly the service TCP offers Internet applications. The difficulty is that the layer *below* the protocol is usually not reliable. introduced in ch. 3 — open in glossary : no bit is corrupted or lost, and everything arrives in the order it was sent. That is precisely the service TCP offers its applications.
The difficulty is that the layer below is unreliable. Four procedure names carry everything in this section:
Two assumptions hold throughout, and both matter:
- The channel does not reorder packets. They may be corrupted, and later they may be lost, but what arrives arrives in the order it was sent.
- Data flows one way only. Control packets still travel both ways — that is unavoidable — but the data itself goes from sender to receiver. Two-way data is no harder in principle and considerably more tedious to draw.
The section says “packet” rather than “segment” throughout, because the theory applies to computer networks in general and not only to the Internet’s transport layer.
rdt1.0 — a perfectly reliable channel
Start with the easy case: the channel below is completely reliable.
How to read a finite state machine
A finite state machine finite-state machine Simple A drawing of a protocol as a few states with labelled arrows between them. Precise An FSM: a description of a protocol as a set of states joined by transitions. Each arrow is labelled with the event that causes it above a horizontal rule, and the actions taken below the rule. The symbol Λ means "no event" above the rule, or "no action" below it. A dashed arrow marks the initial state. Sender and receiver always have separate FSMs. introduced in ch. 3 — open in glossary shows a protocol as states joined by arrows. On each arrow:
- the event that causes the transition is written above a horizontal rule;
- the actions taken are written below it;
- Λ means “no event” above the rule, or “no action” below it;
- the dashed arrow marks the state the protocol starts in.
The sender and the receiver always have separate machines. That is not a drawing convention — they are separate programs on separate computers, and neither can see the other’s state.
One state, one transition. Read the label the way the book does: the event above the rule, the actions below it.
The mirror image, and just as trivial. With a perfect channel the receiver never has anything to report, so no packet ever travels back.
There is no difference here between a unit of data and a packet, and all packets flow from sender to receiver. The receiver never sends anything back, because with a perfect channel there is nothing it could usefully say. We also assume the receiver can consume data as fast as the sender produces it, so there is no need to ask the sender to slow down. Section 3.5.5 removes that assumption and calls the fix flow control.
rdt2.0 — the channel may flip bits
A more realistic channel corrupts bits, which happens in the physical parts of a network as a packet is transmitted, propagates, or sits in a buffer. Packets still all arrive; some of them arrive wrong.
The message taker says "OK" when a sentence has been heard, understood and written down. That is a positive acknowledgement, and it is the simplest possible feedback.
The book’s own analogy, and the three ways out of the trouble it runs into. Only the third one survives.
Read all steps as text
- 1 — "OK" after every sentence — The message taker says "OK" when a sentence has been heard, understood and written down. That is a positive acknowledgement, and it is the simplest possible feedback.
- 2 — "Please repeat that" when it was garbled — If the sentence arrives garbled, the message taker asks for it again. That is a negative acknowledgement. Protocols built on this pattern are called ARQ — Automatic Repeat reQuest.
- 3 — But what if the reply is garbled? — Now the trouble. You could not make out whether they said "OK" or "Please repeat that". You do not know whether that sentence was written down or not. Neither answer is safe.
- 4 — Fix one: ask "What did you say?" — Introduce a new kind of message. But what if THAT is garbled? The other person, unable to tell a garbled question from garbled dictation, would ask "What did you say?" back — and that could be garbled too. This does not terminate.
- 5 — Fix two: enough redundancy to repair, not just detect — Add enough checksum bits that the sender can not only detect an error in the reply but correct it. This genuinely works for a channel that corrupts packets but never loses them. It is also expensive, and chapter 6 shows how expensive.
- 6 — Fix three: just say it again — On a garbled reply, simply resend the sentence. Cheap, simple, and it introduces one new problem: the other person may now write the same sentence down twice. Solving THAT is what rdt2.1 is about, and the solution — numbering the sentences — is the one almost every real protocol uses, TCP included.
Formally, three capabilities are needed:
- Error detection. The receiver must be able to tell that bits have changed. This is what section 3.3.2’s checksum does, and its bits go in the packet.
- Receiver feedback. The sender and receiver may be thousands of kilometres apart, so the only way the sender learns the receiver’s view of the world is if the receiver says so. A positive acknowledgement positive acknowledgement Simple A short message from the receiver meaning "that arrived correctly". Precise An ACK: a control packet sent from receiver to sender to say that a packet was received correctly. In principle it need only be one bit long. In TCP it is not a separate packet type but a field in an ordinary segment header. introduced in ch. 3 — open in glossary (ACK) and a negative acknowledgement negative acknowledgement Simple A short message from the receiver meaning "that arrived damaged — send it again". Precise A NAK: a control packet sent from receiver to sender to say that a packet was received in error and must be repeated. Protocol rdt2.1 uses NAKs; rdt2.2 removes them by having the receiver acknowledge the last correctly received packet instead, so that two ACKs for the same packet carry the same meaning. TCP has no NAK, and gets the same effect from three duplicate acknowledgements. introduced in ch. 3 — open in glossary (NAK) are enough — in principle one bit each.
- Retransmission. A packet received in error is sent again.
Protocols built this way are called ARQ protocols automatic repeat request Simple A family of protocols that fix errors by asking the sender to send it again. Precise ARQ protocols: reliable data transfer protocols based on retransmission. Three capabilities are needed to cope with bit errors — error detection, so the receiver can tell something is wrong; receiver feedback, so the sender learns what the receiver saw; and retransmission of anything received in error. introduced in ch. 3 — open in glossary — Automatic Repeat reQuest.
Outlined buttons are the events this state can actually handle. Try the others too — what cannot happen is as much of the protocol as what can.
Now drive it. Notice which button stops being available the moment a packet goes out — that is stop-and-wait, and it is a property of the state machine, not of any one line of code.
This is where “stop-and-wait” comes from
Try firing rdt_send(data) while the sender is waiting for an ACK. Nothing
happens, and the widget explains why.
In the wait-for-ACK-or-NAK state the rdt_send() event cannot occur. It
becomes possible again only when an ACK arrives and the sender leaves that state.
So the sender never sends a new piece of data until it is certain the receiver
has correctly received the current one.
Protocols with that property are called stop-and-wait protocols stop-and-wait protocol Simple A sender that refuses to send anything new until the last thing has been acknowledged. Precise A protocol in which the sender, having sent one packet, will not accept more data from the layer above until it has received an acknowledgement. rdt2.0 through rdt3.0 are all stop-and-wait. It is simple and correct, and its performance is terrible on any link with a round-trip time much larger than the time to transmit one packet. introduced in ch. 3 — open in glossary . It is a perfectly reasonable design and, as section 3.4.2 will show with real numbers, it is also catastrophically slow.
Outlined buttons are the events this state can actually handle. Try the others too — what cannot happen is as much of the protocol as what can.
Still one state. Every arriving packet gets a reply, and which reply depends only on whether the checksum agrees.
The fatal flaw
rdt2.0 may look as if it works. It does not.
We never accounted for the ACK or NAK itself being corrupted.
Click any arrow to see what that message says and why it is sent.
The data got through perfectly. It is the reply that was damaged — and rdt2.0 has no move here.
Read this diagram as text
- Sender sends pkt (data, checksum) to Receiver. Sent from the "Wait for call from above" state. The sender now moves to "Wait for ACK or NAK" and will accept no new data until this is settled.
- Receiver sends ACK — but corrupted in flight to Sender. The receiver got the data intact and delivered it. It sent a positive acknowledgement. The acknowledgement was damaged on the way back, and rdt2.0 puts no checksum on ACKs and NAKs — so at minimum we would need to add one just to notice.
Lifelines, left to right: Sender (host), Receiver (host).
At minimum we would need checksum bits on the ACK and NAK packets just to notice. The harder question is what to do next, because if the feedback is garbled the sender has no way of knowing whether the receiver got the data.
The three ways out are in the walkthrough above. The first does not terminate. The second works but is expensive. The third — just resend — is cheap, and is what almost every real protocol does, TCP included. It introduces exactly one new problem.
In plain words
If you resend whenever you are unsure, you will sometimes send something twice.
The receiver now holds a packet and cannot tell whether it is new data or a copy of what it already has. Deliver it, and the application above sees the same data twice. Discard it, and you may have thrown away something genuinely new.
The receiver cannot decide, because nothing in the packet tells it which one this is. So put something in the packet that does.
rdt2.1 — number the packets
Add a field to the data packet and have the sender put a sequence number sequence number Simple A number written into each packet so the receiver can tell one from the next. Precise A field added to a data packet so the receiver can decide whether an arriving packet is new or a retransmission of one it already has. For a stop-and-wait protocol one bit is enough, since the receiver only needs to distinguish the current packet from the previous one. With a k-bit field the range is 0 to 2ᵏ−1 and all arithmetic is modulo 2ᵏ. TCP’s field is 32 bits and counts bytes, not packets. introduced in ch. 3 — open in glossary in it. The receiver then only has to check that number to know whether the packet is a retransmission.
For stop-and-wait, one bit is enough. At most one packet is outstanding at a time, so the receiver’s only question is whether this is the packet it just took or the next one. The number moving “forward” in modulo-2 arithmetic means a new packet; the same number again means a duplicate duplicate packet Simple A second copy of something the receiver already has. Precise A packet the receiver has already accepted, arriving again because the sender retransmitted after a corrupted acknowledgement or a timeout that fired too early. Sequence numbers exist so that a receiver can recognise and discard duplicates instead of delivering the same data to the application twice. introduced in ch. 3 — open in glossary .
And because we are still assuming the channel does not lose packets, ACKs and NAKs need not say which packet they refer to. The sender knows any reply — garbled or not — was produced by its most recent transmission.
Outlined buttons are the events this state can actually handle. Try the others too — what cannot happen is as much of the protocol as what can.
Twice the states, and the bottom half is the mirror of the top half with 0 and 1 exchanged. Fire your way round the cycle, then try a corrupted reply and watch the sender resend without moving.
The sender FSM has twice as many states, because the state must now record whether the packet being sent should carry sequence number 0 or 1. The bottom half is the mirror image of the top half; the only differences are in the handling of the sequence number.
Outlined buttons are the events this state can actually handle. Try the others too — what cannot happen is as much of the protocol as what can.
The interesting button is the third one. A clean packet carrying the sequence number the receiver is NOT waiting for is a duplicate — acknowledge it, but do not deliver it twice.
The case worth driving by hand
Put the receiver in “Wait for 0 from below” and fire clean packet, the other number.
The receiver sends an ACK and does not deliver the data. Both halves matter:
- It does not deliver, because a packet carrying sequence number 1 when 0 was expected is a retransmission of data already handed to the application.
- It does acknowledge, because the sender is clearly still waiting for a reply — that is why it resent — and silence would leave it retransmitting forever.
Note what this means: the receiver sends a positive acknowledgement for a packet it is throwing away. An ACK in rdt2.1 does not mean “I delivered this”. It means “stop sending me this”.
Check yourself
Check yourself
0 of 6 answered1.predictIn the rdt2.0 sender, you are in “Wait for ACK or NAK” and you fire rdt_send(data). What happens?
Look at which buttons are outlined in that state.
2.What is the fatal flaw in rdt2.0?
3.The sender resends the data packet whenever it gets a garbled ACK or NAK. What new problem does that create?
4.Why is a one-bit sequence number enough for rdt2.1?
5.predictDrive the rdt2.1 receiver: it is in “Wait for 0 from below” and a packet arrives, uncorrupted, carrying sequence number 1. What does it do?
6.Why is the “What did you say?” approach — a new packet type asking the receiver to repeat its reply — a bad fix for a corrupted ACK?
What to remember
- rdt2.0 copes with bit errors using three things together: a checksum, ACK and NAK feedback, and retransmission. That combination is called ARQ.
- rdt2.0’s fatal flaw is that the feedback itself can be corrupted. Of the three ways out, only “just resend” is both correct and cheap.
- Resending creates duplicates, and the receiver cannot recognise one without help. The help is a sequence number, and one bit is enough for stop-and-wait, because only one packet is ever outstanding.