The standard step-by-step development of reliable data transfer used in top-down networking courses (Kurose and Ross, section 3.4). The utilization figures were computed in code before publishing.
Read each version as an answer to a question: what can go wrong now, and which tool fixes it? If you can say the problem and the fix for each step, you understand the topic. The finite-state diagrams in your slides are the same ideas drawn as boxes and arrows.
Some course slide decks cover only the opening of this topic: why reliability is hard, and the four interface calls. Others go on to the full rdt2.0 to rdt3.0 sequence and pipelined protocols. This guide covers the principles through rdt3.0 and the stop-and-wait utilization argument, and names pipelining without its details. If your course skipped part of it, your exam most likely will too, but the ideas here are what make TCP make sense.
The picture: reading a phone number over a bad line#
You are reading a phone number to a friend over a crackly phone line. How do you make sure they get it right?
- They repeat it back, or say “got it”. If they say “sorry, what?”, you say it again.
- If their “got it” is garbled, you are not sure, so you say the number again. Now they need to know whether that is the same number again or a new one.
- If you hear nothing at all, you wait a moment, then say it again.
That is the whole topic. The rest is giving each of those habits a proper name.
Vocabulary, before anything uses it#
| Term | What it means |
|---|---|
| Reliable channel | A channel where no bits are flipped, nothing is lost, and everything arrives in order. |
| Unreliable channel | What the network layer really provides: bits can be corrupted and packets can be lost. |
| ACK | Acknowledgment: the receiver telling the sender “I got that packet correctly”. |
| NAK | Negative acknowledgment: “that packet arrived damaged, send it again”. |
| Retransmission | Sending a packet again. |
| Sequence number | A number on each packet so the receiver can tell a new packet from a repeat. |
| Duplicate | A second copy of a packet the receiver already has. |
| Timer (timeout) | A countdown at the sender. If no ACK arrives before it runs out, the sender retransmits. |
| Stop-and-wait | Send one packet, then wait for its ACK before sending the next. |
| ARQ | Automatic Repeat reQuest: the family of protocols that fix errors by retransmitting. |
The four calls: where rdt sits#
A reliable data transfer protocol, rdt, sits between the application above and the unreliable channel below. It has four named calls, and exams do ask for them:
| Call | Where | Meaning |
|---|---|---|
| rdt_send() | Sender side, called from above | The application hands data to rdt to be delivered. |
| udt_send() | Sender side, called by rdt | rdt pushes a packet into the unreliable channel. |
| rdt_rcv() | Receiver side, called from below | A packet has arrived from the channel. |
| deliver_data() | Receiver side, called by rdt | rdt hands correct data up to the application. |
The goal: whatever goes into rdt_send() at one end comes out of deliver_data() at the other, correct, complete and in order, even though udt_send() is unreliable. How hard that is depends entirely on what the channel can do wrong.
rdt is reliable, udt is unreliable. The application only ever sees the rdt calls.
Building it up, one problem at a time#
rdt1.0: a perfect channel
If the channel never damages or loses anything, the sender just sends and the receiver just delivers. Nothing else is needed. This version exists only as a starting point.
rdt2.0: the channel can flip bits
Problem: some bits may arrive flipped. Fix: three tools.
- Error detection: a checksum, so the receiver can tell a packet is damaged.
- Receiver feedback: ACK for a good packet, NAK for a damaged one.
- Retransmission: on a NAK, the sender sends the packet again.
The sender waits for the ACK or NAK before sending anything new, so rdt2.0 is a stop-and-wait protocol.
rdt2.1: the ACK or NAK itself can be damaged
Problem: rdt2.0 has a fatal flaw. If the ACK or NAK is corrupted, the sender cannot tell which it was. Resending is the safe choice, but then the receiver might get the same packet twice and deliver it twice. Fix: a sequence number on every packet. For stop-and-wait, one bit is enough: packets alternate 0, 1, 0, 1. A receiver expecting 1 that gets a 0 knows it is a duplicate, throws it away, and ACKs again.
rdt2.2: drop the NAK
The same job can be done with ACKs only. Instead of a NAK, the receiver re-sends the ACK for the last good packet, with that packet's sequence number. A sender that gets a duplicate ACK for the previous packet knows the current one did not get through. Remember this trick: TCP uses it.
rdt3.0: the channel can also lose packets
Problem: now packets, or ACKs, can vanish completely. Waiting for a reply that never comes would wait forever. Fix: a countdown timer. After sending, the sender starts the timer. If the ACK has not arrived when the timer runs out, it retransmits.
What if the packet was only delayed, not lost? Then the retransmission creates a duplicate, and the sequence numbers from rdt2.1 already handle that. Because the sequence number flips between 0 and 1, rdt3.0 is also called the alternating-bit protocol.
| Version | New problem | New tool |
|---|---|---|
| rdt1.0 | Nothing goes wrong | Nothing needed |
| rdt2.0 | Bits get flipped | Checksum, ACK/NAK, retransmit |
| rdt2.1 | The ACK/NAK itself gets flipped | Sequence numbers (0 and 1) to spot duplicates |
| rdt2.2 | Same as 2.1, without NAKs | Duplicate ACK for the last good packet |
| rdt3.0 | Packets get lost | Countdown timer, then retransmit |
Checksums detect damage. Timers detect loss. A lost packet has no checksum to fail, because nothing arrives. That is why the timer was needed as a separate tool.
Worked example: why stop-and-wait wastes the link#
rdt3.0 works, but it is slow. The sender puts one packet on the link and then sits idle for a whole round trip, waiting for the ACK. The share of time the sender is actually busy sending is its utilization:
Usender = (L / R) / (RTT + L / R)
A 1 Gbps link joins two hosts with a round-trip time of 20 ms. Packets are 12,000 bits (1,500 bytes). What is the sender's utilization under stop-and-wait, and what throughput does that give?
Step 1: Time to put one packet on the link.
L / R = 12,000 / 1,000,000,000 = 0.000012 s = 0.012 ms
Step 2: Utilization.
U = 0.012 / (20 + 0.012) ≈ 0.0006
The sender is busy only about 0.06% of the time.
Step 3: Throughput. One packet is delivered per RTT + L/R.
12,000 bits / 0.020012 s ≈ 600 kbps
A 1 Gbps link, delivering about 600 kbps. The protocol, not the link, is the bottleneck.
The fix is pipelining: let the sender have several packets “in flight” before it needs an ACK. With 3 packets in flight, utilization triples. Pipelining needs a larger range of sequence numbers, and buffering at the sender (and, for Selective Repeat, at the receiver too). The two classic pipelined designs are called Go-Back-N and Selective Repeat, and TCP borrows ideas from both.
Checksums catch damaged bits, ACKs tell the sender what arrived, sequence numbers let the receiver spot duplicates, and timers catch loss; stop-and-wait is correct but leaves the link idle for almost a whole round trip.
Practice#
For each version, say the problem before you say the fix. That order is what exams reward.
- Name the four rdt interface calls and say which side each is on.
- What three tools does rdt2.0 add, and what problem do they solve?
- What is the fatal flaw in rdt2.0, and how does rdt2.1 fix it?
- Why is one bit enough for the sequence number in a stop-and-wait protocol?
- How does rdt2.2 signal a damaged packet without using a NAK?
- What new problem does rdt3.0 handle, and with what tool?
- In rdt3.0 the timer expires, but the original packet was only delayed. What happens at the receiver, and why is it safe?
- A 100 Mbps link, 10,000-bit packets, RTT 10 ms. What is the stop-and-wait utilization?
- What is pipelining, and why does it help?
Solutions#
Find the first line where your working split from the solution, and redo the problem from that line. Do not just read the answer and nod.
- rdt_send() and udt_send() at the sender; rdt_rcv() and deliver_data() at the receiver. rdt_send is called by the application above; udt_send pushes into the unreliable channel; rdt_rcv is called when a packet arrives; deliver_data hands data up.
- Checksum, ACK/NAK feedback, retransmission; bit errors. The checksum detects damage, the receiver reports ACK or NAK, and the sender retransmits on a NAK.
- Damaged ACK/NAK; sequence numbers. If the ACK or NAK is corrupted, the sender does not know what happened. Resending could produce a duplicate. rdt2.1 numbers each packet so the receiver can detect and discard duplicates.
- Only two packets are ever in question. In stop-and-wait, the receiver only needs to tell whether an arriving packet is the one it just got again or the next new one. Two values, 0 and 1, distinguish those two cases.
- A duplicate ACK. The receiver re-sends the ACK for the last correctly received packet, including its sequence number. The sender reads a duplicate ACK for the previous packet as “the current one failed” and retransmits.
- Packet loss; a countdown timer. If no ACK arrives before the timer expires, the sender retransmits.
- The receiver gets a duplicate and discards it. Its sequence number shows it is a repeat, so the receiver throws it away and sends the ACK again. Nothing is delivered twice.
- About 0.0099, roughly 1%. L/R = 10,000 / 100,000,000 = 0.0001 s = 0.1 ms. U = 0.1 / (10 + 0.1) ≈ 0.0099.
- Several packets in flight. The sender may send several packets before receiving an ACK, instead of one. The link is kept busy during the round trip, so utilization rises by roughly the number of packets in flight.
Test-readiness checklist#
- ☐ I can name the four rdt calls and say which side and direction each is.
- ☐ I can list the problem and the fix for rdt1.0, 2.0, 2.1, 2.2 and 3.0.
- ☐ I can explain why sequence numbers were needed and why 0 and 1 are enough for stop-and-wait.
- ☐ I can explain how a duplicate ACK can replace a NAK.
- ☐ I can explain why a timer is needed and why a premature timeout is harmless.
- ☐ I can compute stop-and-wait utilization and throughput.
- ☐ I can explain in one sentence why pipelining helps.
Name the problem first, then the tool. “Sequence numbers” alone is half an answer; “sequence numbers, because a garbled ACK makes the sender resend and the receiver must recognize the duplicate” is a full one.
Frequently asked questions#
What is the difference between rdt2.0, rdt2.1, rdt2.2 and rdt3.0?
rdt2.0 handles bit errors with a checksum, ACK/NAK and retransmission. rdt2.1 adds sequence numbers because the ACK/NAK can itself be corrupted. rdt2.2 does the same without NAKs, using duplicate ACKs. rdt3.0 adds a countdown timer because packets can also be lost.
Why does reliable data transfer need sequence numbers?
Because the sender may retransmit a packet the receiver already received correctly, for example when an ACK is corrupted or delayed. The sequence number lets the receiver recognize the duplicate and discard it instead of delivering it twice.
Why is rdt3.0 called the alternating-bit protocol?
Because its packets carry a one-bit sequence number that alternates between 0 and 1, which is all a stop-and-wait protocol needs to tell a new packet from a retransmitted one.
How do you calculate stop-and-wait utilization?
Utilization = (L/R) / (RTT + L/R), where L/R is the time to transmit one packet. For a fast link with a long RTT the result is tiny, because the sender is idle for almost the whole round trip.
What are the four rdt interface calls?
rdt_send() is called by the application at the sender, udt_send() sends a packet into the unreliable channel, rdt_rcv() is called when a packet arrives at the receiver, and deliver_data() passes data up to the receiving application.
Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written.
Test yourself on this topic
The free networking practice app has 19 questions on this topic and 500 across the whole course, each with an explanation for every answer. Offline, no ads, no account.
Practise this topic →