Computer Networking › Section C · The transport layer › Topic C.4

Principles of reliable data transfer

How do you deliver every bit, in order, over a channel that corrupts and loses packets? A handful of mechanisms, checksums, acknowledgements, sequence numbers, timers and windows, solve the problem, and together they are the foundation of TCP.

The problem

An application wants a reliable channel: no bits flipped, nothing lost, everything delivered in the order sent. The channel underneath, such as IP, offers none of this. A reliable data transfer protocol bridges the gap, running at the sender and the receiver and talking only through the unreliable channel. The problem appears at several layers, so it is studied here in general. We build a protocol in stages, adding one mechanism per kind of failure, with data flowing one way and only acknowledgements coming back.

Bit errors: detect, report, resend

Suppose the channel can flip bits but never loses a packet. Three tools fix this. Error detection: each packet carries a checksum, so the receiver can tell when bits have been corrupted. Receiver feedback: the receiver replies with a positive acknowledgement (ACK) for a good packet or a negative acknowledgement (NAK) for a corrupted one. Retransmission: on a NAK, the sender sends the packet again. Protocols built on these ideas are called ARQ, for automatic repeat request. The sender transmits one packet and waits for the reply before sending the next, so the scheme is called stop-and-wait.

Garbled replies need sequence numbers

The ACK or NAK itself can be corrupted. The safe response is for the sender to resend, but then the receiver may get a second copy of a packet it already accepted, with no way to tell a new packet from a repeat. The fix is a sequence number in each packet. For stop-and-wait, a single bit is enough: packets alternate 0, 1, 0, 1, and a repeated number marks a duplicate, which the receiver discards but acknowledges again. NAKs then become unnecessary: the receiver can instead re-acknowledge the last good packet, and a duplicate ACK tells the sender that the following packet did not arrive intact.

Lost packets need timers

Now let the channel lose packets and ACKs too. The sender cannot wait forever, so it starts a countdown timer each time it sends and retransmits if no valid ACK arrives before the timer expires. It cannot tell whether the packet was lost, the ACK was lost, or both were merely slow, but it does not need to: if the original was only delayed, the receiver gets a duplicate and discards it using the sequence number. The timeout should be a little longer than a typical round trip. With checksums, ACKs, one-bit sequence numbers and a timer, this protocol is called the alternating-bit protocol, and it is fully reliable, provided the channel never reorders packets.

Stop-and-wait wastes the link

Correct is not the same as fast. A packet of L bits takes L/R seconds to transmit at rate R. The sender then waits for the ACK, roughly one round-trip time, RTT, later. Ignoring the ACK's own transmission time, the fraction of time the sender is busy, its utilisation, is

U = \frac{L/R}{\mathrm{RTT} + L/R}

On a short link the wait is small. On a fast, long path the sender sits idle almost all the time, whatever the link's rate, because only one packet is ever in flight.

Worked example: stop-and-wait utilisation

A 100 Mbps path has a 40 ms RTT, and packets are 1,250 bytes. 1. Convert to bits: \(L = 1{,}250 \times 8 = 10{,}000\) bits. 2. Transmission time: \(L/R = 10^4 / 10^8 = 0.1\) ms. 3. Utilisation: \(U = 0.1 / 40.1 \approx 0.0025\), so the sender is busy only about 0.25% of the time. 4. Throughput: 10,000 bits every 40.1 ms is about 249 kbps on a 100 Mbps link. 5. Pipelining with N packets in flight multiplies U by N as long as \(N \times 0.1\) ms does not exceed 40.1 ms: N = 100 gives about 25%, and N = 401 fills the link. Check: \(401 \times 0.1 = 40.1\) ms, exactly one RTT plus a transmission time.

Pipelining

A pipelined protocol lets the sender transmit many packets before the first ACK returns. That brings three requirements. The sequence-number range must grow, since every packet in flight needs a distinct number. The sender must keep copies of every unacknowledged packet in case it has to resend. And the receiver may need buffers for packets that arrive out of order. The two classic designs, Go-Back-N and selective repeat, differ in how they handle losses. Both limit the sender to a window of at most N unacknowledged packets, a sliding window that moves forward as ACKs arrive.

Go-Back-N

In Go-Back-N (GBN), the receiver keeps it simple. It accepts only the packet it expects next. Anything arriving out of order is discarded, and the receiver re-sends an ACK for the last packet it accepted in order. ACKs are cumulative: ACK n means every packet up to and including n has arrived. The sender runs one timer, for its oldest unacknowledged packet. When that timer expires, it resends that packet and every later one already sent: it goes back N. The receiver needs no buffer for out-of-order packets, but one loss can trigger many retransmissions.

Worked example: a Go-Back-N trace

A GBN sender has window N = 4 and packets 0 to 5 to send; packet 2 is lost. 1. It sends 0, 1, 2 and 3. 2. The receiver accepts 0 and 1 and ACKs each. 3. Packet 3 arrives out of order, so it is discarded and ACK 1 is repeated. 4. ACKs 0 and 1 slide the window to 2 to 5, so the sender sends 4 and 5; both are discarded, each producing another ACK 1. 5. The timer for packet 2 expires, and the sender resends 2, 3, 4 and 5, which now arrive in order. Check: 10 transmissions delivered 6 packets; packets 3, 4 and 5 crossed the network twice although they arrived intact the first time.

Selective repeat

Selective repeat (SR) retransmits only the packets that were actually lost. The receiver acknowledges each correctly received packet individually, even out of order, and buffers out-of-order packets until the gaps fill; then it delivers the whole run in order. The sender keeps a separate timer for each unacknowledged packet. Replaying the trace above, the receiver ACKs and buffers 3, 4 and 5, the timer for 2 expires, only 2 is resent, and on its arrival 2, 3, 4 and 5 are delivered together: 7 transmissions instead of 10. One rule is essential: the window must be no more than half the sequence-number space, or the receiver can mistake a retransmitted old packet for a new one. With 3-bit numbers, 0 to 7, the window can be at most 4.

Common mistakes to avoid

First, thinking a timeout proves the packet was lost; the ACK may have been lost or both may be late. Second, forgetting that duplicates are the price of retransmission, so sequence numbers are required. Third, believing a faster link fixes stop-and-wait; the RTT still dominates. Fourth, mixing up the receivers: GBN discards out-of-order packets, SR buffers them. Fifth, reading a GBN ACK as acknowledging one packet; it is cumulative. Sixth, making an SR window larger than half the sequence space.

Key takeaways

Reliable transfer over an unreliable channel uses checksums to detect errors, ACKs as feedback, retransmission, sequence numbers to spot duplicates and timers to recover losses. The alternating-bit protocol is reliable but stop-and-wait, with utilisation (L/R)/(RTT + L/R), tiny on fast long paths. Pipelining keeps up to N packets in flight. Go-Back-N uses cumulative ACKs, one timer and resends everything from the lost packet on. Selective repeat ACKs and buffers individually, resends only lost packets, and needs a window of at most half the sequence space.

Flashcards

Flashcard

Reliable channel

No corruption, no loss, delivery in order

The service the protocol must provide.

Test your understanding

Question 1 of 5

A stop-and-wait sender uses 8,000-bit packets on a 1 Gbps path with a 20 ms RTT. About what is its utilisation?

Question 2 of 5

Why does a stop-and-wait protocol need sequence numbers once the sender retransmits after a garbled ACK?

Question 3 of 5

A Go-Back-N receiver has accepted packets 0 to 4 in order and then receives packet 6. What does it do?

Question 4 of 5

A selective repeat protocol uses sequence numbers 0 to 15. What is the largest safe window size?

Question 5 of 5

With window 4, packets 0 to 3 are sent and only packet 1 is lost; its timer then expires. Which packets are resent?

← Previous topicNext topic →