Reliable data transfer: stop-and-wait, Go-Back-N and Selective Repeat

A sender sends packets over a channel that can lose them, corrupt them or delay them; the receiver must deliver the data once and in order. Click on any packet or ACK of the diagram to lose it and watch how each protocol recovers.

Scenario

Protocol

Parameters

Incidents in the channel

Click (or Enter) on a packet or an ACK of the diagram: lost ✕ → bit errors ⚡ → delayed ⏱ → normal. Each incident affects only that transmission; retransmissions go through unless you click on them too.

    Mode

    Practice

    A random protocol with one or two incidents, in prediction mode.

    View

    Space-time diagram · time runs downwards, in units of L/R

    Sender utilization with pipelining · U = N·(L/R) / (RTT + L/R), at most 1

    Events

    Model assumptions
    • Time is measured in units of L/R, the transmission time of a data packet. The propagation delay is the same in both directions, so RTT = 2·(propagation delay). ACKs are small: their transmission time is negligible and they travel in the opposite direction, which does not compete with the data.
    • Sender and receiver only see sequence numbers modulo 2^k (pkt0, pkt1…). dN is the N-th piece of data from the application: it is shown only when sequence numbers repeat, to see which data each packet carries.
    • Stop-and-wait is rdt3.0 (alternating bit): k = 1 and N = 1. The receiver of rdt3.0 and GBN sends, for anything that is not the expected packet, the ACK of the last one received in order; a corrupted ACK or one that acknowledges nothing new is ignored by the sender.
    • GBN: one timer, for the oldest unacknowledged packet; it is restarted with every ACK that moves the window. Cumulative ACKs. Correct if N ≤ 2^k − 1. SR: one timer per packet, individual ACKs and a receiver buffer. Correct if N ≤ 2^k / 2. Kurose and Ross, §3.4.
    • Bit errors are always detected by the checksum (in reality, some multi-bit errors go unnoticed, as seen in GG31). A delayed packet arrives 3·L/R later. If a delay makes a packet overtake another one, the channel reorders: the protocols of §3.4 assume it does not, and they may fail.
    • The timer starts when the packet starts being transmitted. “Adjust” sets it to RTT + L/R + 1: enough for the ACK to arrive in time. With a smaller value there are premature timeouts and needless retransmissions. TCP estimates it from the measured RTT (§3.5.3).

    About this visualization

    A visualization of the principles of reliable data transfer (Kurose and Ross §3.4). A sender sends packets to a receiver over an unreliable channel and the receiver must deliver the data once and in order. The space-time diagram is drawn with time in units of L/R: each packet is a band lasting L/R and each ACK a dashed arrow; on the left, the sender's timers. Three protocols: stop-and-wait (rdt3.0, alternating bit), Go-Back-N (GBN: one timer, cumulative ACKs, the receiver discards out-of-order packets) and Selective Repeat (SR: one timer per packet, individual ACKs and a receiver buffer). Clicking on a packet or an ACK makes it lost, corrupted by bit errors or delayed, and everything is simulated again. Above, the sender and receiver windows at each moment, with base, nextseqnum and the sequence numbers modulo 2^k. Scenarios from the book: the four situations of rdt3.0 (Fig. 3.16), pipelining, the loss of pkt2 in GBN (Fig. 3.22) and in SR (Fig. 3.26), a lost ACK saved by the cumulative ACK, and windows that are too large: N > 2^k − 1 in GBN and N > 2^k/2 in SR (Fig. 3.27), where the receiver delivers a duplicate as new data. It also warns when a delay reorders the channel. It includes a calculator of sender utilization, U = N·(L/R)/(RTT + L/R), with the book's example (1000 B, 1 Gbit/s, 30 ms: U = 0.00027), prediction mode (what the receiver does with each packet and what the sender retransmits on each timeout) and random exercises.

    Concepts: reliable data transfer, rdt3.0, alternating-bit protocol, stop-and-wait, sequence number, ACK, timer, retransmission, pipelining, Go-Back-N (GBN), Selective Repeat (SR), sliding window, cumulative ACK, sender utilization.

    Formulas:

    Network Architecture I, Session 3.2 · Enrique de la Hoz, University of Alcalá · License CC BY-SA 4.0 · Source and catalogue on GitHub · DOI 10.5281/zenodo.23285664