Reliable data transfer

A reliable data transfer protocol ensures that data:

is not lost or corrupted
arrives in the same order it was sent

Key parts of a reliable protocol:

acknowledgments (positive and negative)
checksums to detect errors
sequence numbers to track order
timers to handle delays or loss

Building a stop-and-wait reliable data transfer protocol

We develop a "rdt" or "Reliable Data Transfer" protocol step by step, making it more capable each time:

Protocol	Problem	Solution	Notes
rdt1.0 - Perfect channel	Assumes a perfect network channel.	no packet loss or corruption no need to provide any feedback to the sender packets arrive in order data is received as fast as the sender happens to send data, no need to ask him to slow down	No reliability mechanisms needed.
rdt2.0 - Bit errors (ACK/NAK + checksum)	Bits in a packet may be corrupted.	To handle this, the receiver sends feedback to the sender via control messages: `ACK` = packet received correctly `NAK` = packet corrupted, resend Reliable data transfer protocols based on such retransmission are known as ARQ (Automatic Repeat reQuest) protocols. They require 3 capabilities to handle the presence of bit errors: error detection: allow the receiver to detect corrupted packets (e.g. checksum) receiver feedback: receiver tells sender if packet was OK (`ACK`) or bad (`NAK`) retransmission: sender resends packets that were received in error	This is a stop-and-wait protocol: the sender must wait for `ACK`/`NAK` before sending the next packet.
rdt2.1 - Retransmission and sequence number	`ACK`/`NAK` messages can also be corrupted.	This can trigger unnecessary retransmissions, resulting in duplicate packets. Fix to distinguish between a new or duplicate packet: add a sequence number field (1 bit: `0` or `1`) in the packet.	This allows the receiver to distinguish: new packet → has the next sequence number duplicate packet → has the same sequence number as the last correctly received one
rdt2.2 - No NAKs (ACK-only system)	Simplify control messages.	Instead of using both `ACK` and `NAK`, use a `NAK`-free system: the receiver only sends `ACK` for the last correctly received packet duplicate `ACK`s signal an error	If the sender receives repeated `ACK`s for the same packet: it infers the next packet was lost or corrupted and retransmits it
rdt3.0 - Packet loss (timers)	Packets/`ACK`s can be lost entirely and the sender may never hear back from the receiver.	How to detect packet loss? The sender can wait long enough so that it is certain that a packet has been lost: the worst-case maximum delay is difficult to estimate at least as long as a round-trip delay (including buffering at intermediate routers) plus whatever amount of time is needed to process a packet at the receiver thus the approach adopted in practice is to use a countdown timer that makes it likely that the packet is lost, although not guaranteed What to do when packet loss occurs? if a packet is not received within this time, it is retransmitted if a packet experiences a particularly large delay, the sender may retransmit it, though it hasn't been lost, introducing the possibility of duplicate data packets	Sender actions: start the timer when sending a packet retransmit on timeout stop timer when `ACK` arrives

Pipelined reliable data transfer protocols

A stop-and-wait protocol is inefficient because the sender must wait for an acknowledgment after each packet.

Pipelining improves performance by allowing the sender to transmit multiple packets before receiving acknowledgments.

Stop-and-wait protocol and pipelined protocol

Pipelined protocols need more sequence numbers and buffering because multiple packets may be sent before acknowledgments arrive.

There are two main pipelined error-recovery methods:

Go-Back-N (GBN): if a packet is lost or corrupted, the sender retransmits that packet and all subsequent packets
Selective Repeat (SR): only the lost or corrupted packets are retransmitted

Go-Back-N (GBN)

In a GBN protocol, the sender can send up to N packets without waiting for ACKs.

The allowed sequence numbers form a window of size N:

as packets are acknowledged, the window moves forward
N is referred to as the window size
the GBN protocol is referred to as a sliding-window protocol

Example:

Go-Back-N

suppose the sender has a window size of 4:
- the sender sends packets 0–3
- the receiver successfully gets packets 0 and 1, and now expects packet 2
- after receiving ACKs for 0 and 1, the sender's window advances and it sends packets 4 and 5
- packet 2 is lost
at the receiver:
- packets 3, 4, and 5 arrive after the missing packet 2
- because GBN requires in-order delivery, these packets are discarded
- the receiver does not store out-of-order packets because they will be retransmitted anyway
at the sender:
- the ACK for packet 2 never arrives, so a timeout occurs
- the sender goes back to packet 2 and retransmits all packets from 2 to 5

This behavior gives Go-Back-N its name: the sender goes back to the missing packet and resends all following packets.

GBN can suffer from performance problems when both the window size and the bandwidth-delay product (BDP) are large:

BDP is the maximum amount of data that can be "in flight" on the network at one time:
- BDP (bits) = bandwidth (bits/second) × RTT (seconds)
- you can think of a network link like a pipe:
  - pipe length = RTT (round-trip delay)
  - pipe diameter = bandwidth (link capacity)
  - therefore, bandwidth × RTT = pipe volume (the amount of data the network can hold)
when the BDP is large, many packets may be in transit simultaneously
in GBN, a single packet error can cause a retransmission of a large number of packets, many unnecessarily
this can potentially fill the pipeline with redundant traffic and reducing efficiency

Selective repeat (SR)

In a SR protocol:

the sender retransmits only packets that are lost or corrupted instead of resending everything
the receiver accepts packets out of order and buffers them until missing ones arrive
a window of size N limits the number of unacknowledged packets in transit
unlike GBN, the sender may already have ACKs for some packets in the window

Selective repeat

Event	Sender	Receiver
Packet received	if the packet is within the sender window: send it otherwise, buffer it	if the packet is within the receiver window: send `ACK` buffer it if the sequence number = `rcv_base`, deliver it and any consecutive buffered packets to the upper layer slide the receiver window forward by the number of packets sent to the upper layer if the packet was already received: re-send `ACK` (reacknowledge instead of ignoring the packet) this prevents the sender window from getting stuck if a previous `ACK` was lost if the packet is outside both ranges: ignore it
Timeout	each packet has its own timer to detect lost ones if a timer expires, only that packet is retransmitted	—
`ACK` received	mark the packet as received (if it's in the window) if the sequence number = `send_base`, slide the window forward if new space opens, send any buffered packets	—

Sender and receiver windows are not always aligned.

This can create the SR receiver dilemma. With large windows, the receiver may not know whether a packet is a new packet or a retransmission:

suppose:
- sequence numbers are limited to 0, 1, 2, 3
- window size is 3
steps:
1. sender sends packets 0, 1, 2
2. receiver gets them and sends ACKs
3. receiver window moves to expect 3, 0, 1
4. however, ACKs are lost, so sender retransmits 0, 1, 2
5. receiver receives packet 0 again
the receiver cannot tell whether this 0 is:
- a retransmission of the old packet 0
- a new transmission of a new packet 0 after sequence numbers wrapped around

To avoid this ambiguity:

the window size must be at most half of the sequence number space for SR protocols
if sequence space = 4 → max window size = 2

Selective repeat receiver dilemma

Summary

Mechanisms for reliable data transfer:

Name	Mechanism
Checksum	detects bit errors in a packet
Timer/timeout	triggers retransmission of lost packets or missing `ACK`s can cause duplicates due to: premature timeout (packet delayed but not lost) lost `ACK`s
Sequential numbering of packets	gaps allow the receiver to detect missing packets duplicate sequence numbers allow the receiver to detect duplicates
Acknowledgment	confirms correct receipt of a packet carries sequence number can be individual or cumulative
Negative acknowledgment	indicates a packet was not received correctly carries sequence number
Window, pipelining	limits number of unacknowledged packets in transit window size may be set on: receiver buffer capacity level of congestion in the network or both

Published on 03/08/2026

Previous UDP All ⏎ Next TCP

Keyboard shortcut	Description
`←`	Previous item
`→`	Next item
`⇧` + `←`	Previous page
`⇧` + `→`	Next page
`f`	Show/hide furigana