Sliding Window Protocol

The problem: waiting wastes time

Data is sent in frames, and the receiver confirms each with an acknowledgement (ACK). If a frame or ACK is lost, the sender retransmits after a timeout. This idea is called ARQ (Automatic Repeat reQuest).

The simplest version, Stop-and-Wait, sends one frame and waits for its ACK before sending the next. On a long link (say India → USA, ~200 ms round trip) the line sits idle most of the time.

The sliding window idea

Let the sender have up to N unacknowledged frames in flight at once. The window is the range of sequence numbers it may send:

[ acked | acked | sent | sent | sent | sent | not yet | not yet ]
                 └──────── window (N = 4) ───────┘

When the oldest frame in the window is acknowledged, the window slides forward and a new frame may be sent. In the 3D model, the translucent box on the sender’s row is the window.

Go-Back-N (GBN)

• Sender keeps up to N frames in flight.
• Receiver accepts frames only in order; anything out of order is discarded.
• ACKs are cumulative: “ACK k” means everything before k arrived.
• On timeout, the sender goes back and resends the oldest unacknowledged frame and all frames after it.

Simple receiver, but one loss causes many good frames to be resent.

Selective Repeat (SR)

• Receiver buffers out-of-order frames and acknowledges each frame individually.
• On timeout, the sender resends only the missing frame.
• More efficient on lossy links, but the receiver needs buffer space, and the window can be at most half the sequence-number space (to avoid confusing old and new frames).

Comparison

Efficiency

With frame transmission time Tf and propagation delay Tp, let a = Tp / Tf. The link utilisation of Stop-and-Wait is

U = 1 / (1 + 2a)

A window of size N ≥ 1 + 2a keeps the link fully busy (U ≈ 1). That’s why TCP uses a sliding window (with a variable size) on top of IP.

Code (Go-Back-N sender, simplified)

def go_back_n(frames, N, lost=None):
    lost = set(lost or {2})                                       # frames lost the first time
    base, next_seq, log = 0, 0, []
    while base < len(frames):
        while next_seq < base + N and next_seq < len(frames):    # fill the window
            log.append(f"send {next_seq}" + (" (lost)" if next_seq in lost else ""))
            next_seq += 1
        # receiver accepts only in-order frames
        expected = base
        while expected < next_seq and expected not in lost:
            expected += 1
        if expected == base:                                      # nothing new arrived → timeout
            log.append(f"timeout → resend {base}..{next_seq - 1}")
            lost.discard(base)
            next_seq = base
        else:
            log.append(f"ACK {expected}")
            base = expected
    return log

for line in go_back_n(list(range(8)), 4):
    print(line)

Common mistakes

• Thinking Go-Back-N resends all frames — only from the lost one onwards.
• Forgetting that ACKs can be lost too (a later cumulative ACK still covers earlier frames in GBN).
• Making the Selective Repeat window bigger than half the sequence space.