Two more steps finish the job: rdt2.2 throws the NAK (negative acknowledgement) negative acknowledgement A message saying that data arrived damaged and must be resent. Used by rdt2.1; removed in rdt2.2; TCP has none, and uses three duplicate ACKs instead. introduced in ch. 3 away as unnecessary, and rdt3.0 adds a timer so the sender can cope with hearing nothing at all.
Words you will meet
- Duplicate ACK — a second acknowledgement of the same packet, which quietly means “the next one never arrived”.
- Countdown timer — a clock the sender starts with each packet, which interrupts it if no reply comes.
- Premature timeout — a timer that fires while the packet is merely slow, not lost.
- Alternating-bit protocol — rdt3.0’s other name, from its sequence numbers flipping 0, 1, 0, 1.
Why this matters
Section 3.4.1 got as far as a channel that damages packets. Real channels also lose them, and loss is a harder signal to act on than damage, because damage announces itself and loss does not.
Everything after this point in the chapter — all of 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 — is built from what these two protocols assemble. The duplicate-ACK trick in rdt2.2 reappears in section 3.5.4 as fast retransmit. The timer reappears in section 3.5.3, where working out how long to set it turns out to be a small science of its own.
| 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.
The same table as section 3.4.1, now finished. Notice that nothing was ever added twice: each mechanism appears once, in the protocol whose channel forced it.
rdt2.2 — the same protocol without NAKs
rdt2.1 is correct. It is also carrying a packet type it does not need.
Here is the observation. We can accomplish the same effect as a NAK by sending an ACK for the last correctly received packet instead. A sender that receives two ACKs for the same packet — duplicate ACKs — knows that the receiver did not correctly receive the packet following the one being acknowledged twice.
In plain words
“I still have packet 0” and “I did not get packet 1” are the same statement, if both sides know packets go in order.
So you do not need a word for the second one. Saying the first one twice will do.
One subtle change makes it work. The receiver must now include the sequence
number of the packet being acknowledged — the ACK,0 or ACK,1 argument to
make_pkt(). And the sender must check that number, which is the 0 or 1
argument to isACK(). Without those, an ACK would be ambiguous and the trick
would be unreadable.
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.
Compare it with the rdt2.1 sender. Same four states, same cycle; the only change is that the sender now checks which packet an ACK is for.
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 NAK is gone. In its place, the receiver re-acknowledges the last packet it did get — which tells the sender the same thing, using a packet type that already existed.
Follow one duplicate ACK through both machines
Put the receiver in Wait for 0 from below and fire corrupted, or the other
number. It sends ACK,1 — an acknowledgement of packet 1, the last one it
successfully took.
Now put the sender in Wait for ACK 0 and fire garbled ACK, or an ACK for the
other packet. It matches isACK(rcvpkt,1), takes the self-loop, and
retransmits.
The receiver never said “that was broken”. It said “I still have packet 1”, and the sender worked out the rest. This is worth remembering: TCP has no NAK either, and section 3.5.4 recovers lost segments from exactly this signal, counting three duplicate acknowledgements before it acts.
rdt3.0 — the channel may lose packets
Now let the underlying channel lose whole packets as well as corrupt bits — not an uncommon event in real networks, the Internet included. Two new questions: how do we detect loss, and what do we do about it?
The second is already answered. Checksums, sequence numbers, ACKs and retransmission — everything rdt2.2 has — handle the consequences. Only detection needs something new.
How long should the sender wait?
Put the burden on the sender. If a data packet or its ACK is lost, no reply is forthcoming; if the sender waits long enough to be sure something was lost, it can simply retransmit.
But how long is long enough? The sender must wait at least a round-trip delay — which may include queuing at intermediate routers — plus the time the receiver needs to process the packet.
Two reasons that is not a workable answer
- In many networks the worst-case delay is very difficult even to estimate, let alone know with certainty.
- Even if you knew it, waiting for it would be a bad idea. The protocol should recover from loss as quickly as it can, and waiting out a worst case before every retransmission is the opposite of that.
So the sender does something less principled and much more practical: it judiciously chooses a time value such that loss is likely, though not guaranteed, to have happened. If no ACK arrives within that time, it retransmits.
Being wrong sometimes is designed in, not an accident. Section 3.5.3 shows how TCP chooses that value from measurements, and it is still only an estimate.
This means a packet with an unusually large delay may be retransmitted even though neither it nor its ACK was ever lost — a premature timeout premature timeout Simple A timer that fires while the packet is merely slow, not actually lost. Precise A timeout that occurs because a packet or its acknowledgement was delayed rather than lost. The sender retransmits anyway, which puts a duplicate into the channel. Sequence numbers already handle the duplicate, so the protocol stays correct; the cost is wasted transmission, which is one of the costs of congestion in §3.6. introduced in ch. 3 — open in glossary . That puts a duplicate into the channel. Happily, rdt2.2 already has enough machinery to handle duplicates, which is precisely why it was safe to add a timer to it.
Retransmission is a panacea
From the sender’s point of view there is no difference between:
- a data packet that was lost,
- an ACK that was lost, and
- a packet or ACK that was merely slow.
In all three cases nothing came back in time. In all three cases the action is the same: retransmit. The sender does not need to diagnose the problem, which is the reason a mechanism this crude works so well.
Implementing this needs a countdown timer countdown timer Simple A clock the sender starts with each packet, which interrupts it if no reply comes in time. Precise The mechanism rdt3.0 adds to cope with loss. The sender must be able to start the timer whenever it sends a packet, respond to the interrupt when it expires, and stop it when an acknowledgement arrives. The interval is chosen so that loss is likely, though not certain, to have happened — waiting for a guaranteed worst case would make recovery far too slow. introduced in ch. 3 — open in glossary that can interrupt the sender after a given amount of time. The sender must be able to
- start the timer each time a packet is sent — first transmission or retransmission,
- respond to the timer interrupt, and
- stop the timer.
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.
Two new self-loops per waiting state. One starts the timer over on a timeout; the other quietly ignores a reply that means nothing. The receiver FSM is left as problem P8 — try drawing it before you look.
In plain words
Look at what actually changed from rdt2.2 to rdt3.0. Every udt_send in a
waiting state is now followed by start_timer, and every successful ACK is
followed by stop_timer. Each waiting state also gains one new self-loop, on
timeout, whose action is “send it again and restart the clock”.
That is the whole of it. One mechanism, added once, and the protocol is finished.
Watching it run
The happy case, and the baseline for the other three. Sequence numbers alternate 0, 1, 0 — which is where the name "alternating-bit protocol" comes from.
Click any arrow to see what that message says and why it is sent.
Four runs of the same protocol. Switch between them, then step through arrow by arrow — the sender’s behaviour is identical in all four, and only the channel differs.
Read this diagram as text
- Sender sends pkt0 to Receiver. Sent from "Wait for call 0 from above". The sender starts its timer and moves to "Wait for ACK 0".
- Receiver sends ACK0 to Sender. The receiver got sequence number 0, which is what it was waiting for. It delivers the data upward and acknowledges packet 0.
- Sender sends pkt1 to Receiver. The ACK was for packet 0 and was not corrupted, so the sender stops its timer, moves on, and the next packet carries sequence number 1.
- Receiver sends ACK1 to Sender.
- Sender sends pkt0 to Receiver. Back to sequence number 0. With one bit there are only two numbers, and stop-and-wait guarantees that is enough.
- Receiver sends ACK0 to Sender.
Lifelines, left to right: Sender (host), Receiver (host).
Scenario d is the one to sit with
In the first three scenarios something goes wrong in the channel. In the fourth, nothing is lost at all — the protocol simply guesses wrong about a slow packet and creates the problem itself.
Follow the consequences. The receiver gets pkt1 twice: it delivers the first and recognises the second as a duplicate, acknowledging without delivering. The sender gets ACK1 twice: it acts on the first and, by the time the second arrives, has moved on to packet 0 and does nothing with it.
Both ends absorb the mistake without any special code for it. That robustness is not luck — it is what the sequence numbers added in rdt2.1 were for, working two protocols later on a problem they were not designed for.
Because packet sequence numbers alternate between 0 and 1, rdt3.0 is sometimes known as the alternating-bit protocol alternating-bit protocol Simple Another name for rdt3.0, because its sequence numbers only ever flip between 0 and 1. Precise Protocol rdt3.0: reliable data transfer over a channel that can both corrupt and lose packets, built from checksums, one-bit sequence numbers, acknowledgements and a countdown timer. The name comes from the sequence numbers alternating 0, 1, 0, 1. introduced in ch. 3 — open in glossary .
We now have a working protocol
The key elements are assembled: checksums, sequence numbers, timers, and acknowledgement packets each play a necessary role.
The book’s summary sentence also lists negative acknowledgements among them. Strictly, rdt3.0 has none — rdt2.2 removed the NAK and rdt3.0 inherits that. NAKs were a necessary step in the argument, and are not part of the finished protocol. Neither is TCP’s.
And yet nobody would use it
rdt3.0 is functionally correct. It is also, in the book’s words, unlikely to make anyone happy — particularly on a fast network.
The reason is the property named back in rdt2.0: it is stop-and-wait. One packet in flight, then a full round trip of silence, then one more. Section 3.4.2 puts real numbers on that, and they are worse than you expect.
Check yourself
Check yourself
0 of 6 answered1.How does rdt2.2 tell the sender that a packet arrived damaged, without using a NAK?
2.What changes had to be made to turn rdt2.1 into rdt2.2?
3.Why can the rdt3.0 sender not simply wait long enough to be certain a packet was lost?
Two separate objections, and the book gives both.
4.predictSwitch the diagram to “premature timeout”. The sender's timer fires while pkt1 is merely slow, not lost. What saves the protocol?
5.From the rdt3.0 sender's point of view, what is the difference between a lost data packet, a lost ACK, and a packet that was merely slow?
6.Why is rdt3.0 called the alternating-bit protocol?
What to remember
- rdt2.2 deletes the NAK. An ACK for the previous packet says the same thing, so a duplicate ACK means “the next one never arrived”.
- rdt3.0 adds one thing: a countdown timer. Everything needed to survive the duplicates it causes was already there.
- To the sender, a lost packet, a lost ACK and a slow packet are indistinguishable. The response to all three is the same: retransmit.