Chapter 16 of 48

ARQ Protocols (Stop-and-Wait, Go-Back-N, Selective Repeat)

In the Error Detection chapter we saw that a receiver can find out that a frame is damaged, and that one way to recover is to simply ask for it again. In the Flow Control chapter we met Stop-and-Wait and Sliding Window. Now we combine these ideas.

ARQ (Automatic Repeat reQuest) is a family of protocols that give reliable delivery over an unreliable link by using acknowledgments, timers and retransmissions. If a frame is lost or damaged, the sender notices and sends it again, automatically.

The three classic ARQ protocols are:

  1. Stop-and-Wait ARQ

  2. Go-Back-N ARQ

  3. Selective Repeat ARQ

They are a favourite topic in exams and interviews, especially questions on efficiency, window size and sequence number bits. We will cover all of them with worked examples.


The Building Blocks of ARQ

Every ARQ protocol is built from the same few pieces.

Building block

Purpose

Error detection

The receiver uses a checksum or CRC to detect damaged frames and silently discards them

ACK (acknowledgment)

The receiver tells the sender "I got it"

NAK (negative acknowledgment)

Optional. The receiver says "this one was bad or missing, please resend"

Timer (timeout)

If no ACK arrives in time, the sender assumes the frame was lost and resends it

Sequence numbers

Numbers on frames so the receiver can spot duplicates and the right order

Windows

How many frames the sender may have unacknowledged, and how many the receiver may accept out of order

Sequence numbers come from a field with a fixed number of bits. With k bits there are 2k numbers, and they wrap around. For example, with k = 3 the numbers go:

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 ...

This wrap-around is the reason window sizes are limited, as we will see.


1. Stop-and-Wait ARQ

The sender sends one frame, starts a timer, and waits. It sends the next frame only after the ACK arrives. If the timer expires first, it resends the same frame.

Sender                         Receiver
  │── Frame 0 ──────────────────→│
  │←───────────────────── ACK 1 ─│   (ACK number = next frame expected)
  │── Frame 1 ──────────────────→│
  │←───────────────────── ACK 0 ─│
  │── Frame 0 ──────────────────→│

Sender window = 1, receiver window = 1, and only two sequence numbers (0 and 1) are needed, so 1 bit is enough.

Case 1: The Frame Is Lost

Sender                         Receiver
  │── Frame 0 ────────X  (lost)
  │   ... timer expires ...
  │── Frame 0 ──────────────────→│  received
  │←───────────────────── ACK 1 ─│

The timer solves this: no ACK came, so the sender resends.

Case 2: The ACK Is Lost

Sender                         Receiver
  │── Frame 0 ──────────────────→│  accepted
  │          X────────── ACK 1 ──│  (ACK lost)
  │   ... timer expires ...
  │── Frame 0 ──────────────────→│  duplicate! discard, but ACK again
  │←───────────────────── ACK 1 ─│

This case is why we need sequence numbers. Without them, the receiver could not tell that the second "Frame 0" is a duplicate and would deliver the same data twice. The receiver discards the duplicate but still sends an ACK, otherwise the sender would keep retransmitting forever.

Case 3: The ACK Is Delayed

If an ACK arrives after the timeout, the sender may have already resent the frame. Numbering the ACKs too lets the sender ignore an old ACK instead of confusing it with the ACK for a newer frame.

Efficiency of Stop-and-Wait

Let Tt be the transmission delay of one frame and Tp the propagation delay (see the Network Delays chapter). Ignoring the ACK's own transmission time and processing, one cycle takes Tt + 2Tp, but the link is busy for only Tt of that.

Efficiency  η = Tt / (Tt + 2 × Tp) = 1 / (1 + 2a)

where  a = Tp / Tt

Throughput = η × link rate

Worked example: Link rate 1 Mbps, frame size 1,000 bits, propagation delay 20 ms.

Tt = 1000 / 10^6 = 1 ms
a  = Tp / Tt = 20 / 1 = 20
η  = 1 / (1 + 2 × 20) = 1 / 41 ≈ 0.0244  →  2.44%
Throughput = 0.0244 × 1 Mbps ≈ 24.4 kbps

The link sits idle about 97.6% of the time. When a is large (long distance, fast link or small frames), Stop-and-Wait wastes almost everything. That is why we need pipelining.


Pipelining with Sliding Windows

Instead of waiting after every frame, let the sender have up to N frames "in flight" at once. This is the sliding window from the Flow Control chapter, with a timer and retransmission added.

Already ACKed │  Sent, not ACKed  │ Can send now │ Not allowed yet
  0  1  2     │  3  4  5  6       │  7  8        │  9  10 ...
              └────── sender window (N = 6) ─────┘

If no frames are lost, the sender can transmit N frames in one cycle of Tt + 2Tp:

Efficiency η = N / (1 + 2a)     if N < 1 + 2a
Efficiency η = 1 (100%)         if N ≥ 1 + 2a

So the window needed to keep the link fully busy is N = 1 + 2a. Go-Back-N and Selective Repeat are two different ways of handling errors inside this pipeline.


2. Go-Back-N ARQ

In Go-Back-N (GBN):

  • The sender may have up to N unacknowledged frames.

  • The receiver window is 1: it accepts frames only in order. Any frame that arrives out of order is discarded.

  • ACKs are cumulative: an ACK for frame n means "I have everything up to n". (Some books instead put the number of the next frame expected, n + 1, in the ACK, as we did for Stop-and-Wait above. The idea is the same.)

  • The sender keeps a timer for the oldest unacknowledged frame. On timeout it goes back and resends that frame and every frame after it that was already sent.

Example: Frame 2 Is Lost

Sender sends:   0   1   2   3   4   5
Receiver gets:  0   1   X   3   4   5
                ok  ok      discard (out of order)

Timeout for frame 2 → sender resends 2, 3, 4, 5

Frames 3, 4 and 5 arrived safely, but they are sent again because the receiver threw them away. This wastes bandwidth, especially when errors are frequent or the window is large.

Maximum Window Size in Go-Back-N

With k-bit sequence numbers:

Go-Back-N:  sender window N ≤ 2^k − 1,   receiver window = 1

Why not 2k? Take k = 2 (numbers 0 to 3) and suppose we allowed a window of 4.

1. Sender sends 0, 1, 2, 3. Receiver accepts all four.
   Receiver now expects 0 (the next round of numbers).
2. All four ACKs are lost.
3. Sender times out and resends the OLD frame 0.
4. Receiver is expecting a "0", so it accepts the old frame
   as new data.  → Duplicate delivered. Wrong!

With a window of 3 (sending 0, 1, 2), the receiver would be expecting 3 after accepting them, so a resent old 0 is recognised as a duplicate. Hence N ≤ 2k − 1.


3. Selective Repeat ARQ

Selective Repeat (SR) fixes the waste of Go-Back-N:

  • The receiver also has a window, usually the same size N as the sender. It accepts and buffers out-of-order frames that fall inside its window.

  • Each frame is acknowledged individually.

  • The sender keeps a separate timer for each frame and, on timeout, resends only that frame. A NAK can be used to ask for a missing frame early.

  • The receiver delivers data to the upper layer in order, once the gap is filled.

Example: Frame 2 Is Lost

Sender sends:   0   1   2   3   4   5
Receiver gets:  0   1   X   3   4   5
                ok  ok      buffered, ACKed individually

Timeout for frame 2 → sender resends only 2
Receiver now delivers 2, 3, 4, 5 in order

Maximum Window Size in Selective Repeat

Selective Repeat:  sender window = receiver window ≤ 2^(k−1)

That is, the window can be at most half the sequence number space. Why? Take k = 2 (numbers 0 to 3) and suppose the window were 3.

1. Sender sends 0, 1, 2. Receiver accepts all three and
   moves its window to {3, 0, 1}.
2. All three ACKs are lost.
3. Sender times out and resends the OLD frame 0.
4. "0" is inside the receiver's new window, so it is buffered
   as NEW data.  → Wrong!

With a window of 2 (half of 4), the receiver's new window after accepting 0 and 1 is {2, 3}, which does not overlap the old frames, so the duplicate 0 is correctly rejected. The rule is that the old window and the new window must never overlap.


Seeing the Difference in Code

The following Python program simulates Go-Back-N and Selective Repeat in time slots. Sending one frame takes one slot, an ACK comes back 4 slots after a frame is sent, and an unacknowledged frame times out after 6 slots. We send 8 frames with a window of 4, and the 3rd transmission (frame 2) is lost.

# Time-slot simulation of Go-Back-N and Selective Repeat.
# Sending one frame takes 1 time slot. An ACK reaches the sender
# RTT slots after the frame was sent. A frame that has not been
# ACKed TIMEOUT slots after it was sent is retransmitted.

TOTAL, WINDOW, RTT, TIMEOUT = 8, 4, 4, 6
LOST = {3}   # the 3rd transmission is lost on the way

def simulate(protocol):
    acked = [False] * TOTAL     # what the sender knows
    sent_at = [None] * TOTAL    # when each frame was last sent
    pending_acks = []           # (arrival_time, ack_number)
    expected = 0                # GBN receiver: next in-order frame
    buffered = set()            # SR receiver: frames received
    base = nxt = tx = t = 0
    log = []
    while base < TOTAL:
        # 1. deliver ACKs that have arrived by time t
        for arrival, ack in [a for a in pending_acks if a[0] <= t]:
            pending_acks.remove((arrival, ack))
            if protocol == "GBN":            # cumulative ACK
                for f in range(ack + 1):
                    acked[f] = True
            else:                            # individual ACK
                acked[ack] = True
        while base < TOTAL and acked[base]:
            base += 1
        if base >= TOTAL:
            break
        # 2. choose what to send in this slot
        frame = None
        if protocol == "GBN":
            if sent_at[base] is not None and t - sent_at[base] >= TIMEOUT:
                log.append(f"t={t}: timeout for {base}, go back")
                nxt = base                   # resend everything from base
        else:
            for f in range(base, min(base + WINDOW, TOTAL)):
                if (not acked[f] and sent_at[f] is not None
                        and t - sent_at[f] >= TIMEOUT):
                    log.append(f"t={t}: timeout for {f}")
                    frame = f                # resend only this frame
                    break
        if frame is None and nxt < min(base + WINDOW, TOTAL):
            frame = nxt
            nxt += 1
        # 3. transmit it and let the receiver react
        if frame is not None:
            tx += 1
            sent_at[frame] = t
            if tx in LOST:
                log.append(f"t={t}: send {frame}  (LOST)")
            else:
                log.append(f"t={t}: send {frame}")
                if protocol == "GBN":
                    if frame == expected:
                        expected += 1        # accept in order
                    # out-of-order frames are discarded
                    if expected > 0:
                        pending_acks.append((t + RTT, expected - 1))
                else:
                    buffered.add(frame)      # accept and buffer
                    pending_acks.append((t + RTT, frame))
        t += 1
    log.append(f"done: {tx} transmissions, finished at t={t}")
    return log

for protocol in ("GBN", "SR"):
    print(f"--- {protocol} ---")
    print("\n".join(simulate(protocol)))

Output:

--- GBN ---
t=0: send 0
t=1: send 1
t=2: send 2  (LOST)
t=3: send 3
t=4: send 4
t=5: send 5
t=8: timeout for 2, go back
t=8: send 2
t=9: send 3
t=10: send 4
t=11: send 5
t=12: send 6
t=13: send 7
done: 12 transmissions, finished at t=17
--- SR ---
t=0: send 0
t=1: send 1
t=2: send 2  (LOST)
t=3: send 3
t=4: send 4
t=5: send 5
t=8: timeout for 2
t=8: send 2
t=12: send 6
t=13: send 7
done: 9 transmissions, finished at t=17

Notice the key points:

  • Both protocols keep sending frames 3, 4 and 5 after the loss, because the window still allows it. That is pipelining.

  • On timeout, Go-Back-N resends 2, 3, 4 and 5, while Selective Repeat resends only 2.

  • With a single loss both finish at the same time here, because both must wait for frame 2. But GBN used 12 transmissions and SR only 9. On a busy or error-prone link, those wasted transmissions slow everything down.


Comparison of the Three ARQ Protocols

Feature

Stop-and-Wait

Go-Back-N

Selective Repeat

Sender window

1

N ≤ 2k − 1

N ≤ 2k−1

Receiver window

1

1

Same as sender (N)

Minimum sequence numbers

2

N + 1

2N

Out-of-order frames

Not applicable

Discarded

Buffered

ACK type

One per frame

Cumulative

Individual (NAK optional)

On a loss, resends

That frame

That frame and all after it

Only that frame

Timers

One

One (oldest frame)

One per frame

Efficiency (no errors)

1 / (1 + 2a)

min(1, N / (1 + 2a))

min(1, N / (1 + 2a))

Complexity

Simplest

Moderate

Most complex (buffers, reordering)

Best for

Short links, small a

Low error rates

High error rates or large windows


Worked Exam Problems

Problem 1: Window Sizes for k = 3

A protocol uses 3-bit sequence numbers (0 to 7). What is the maximum sender window?

Stop-and-Wait    : 1
Go-Back-N        : 2^3 − 1 = 7
Selective Repeat : 2^(3−1) = 4   (sender and receiver window each 4)

Problem 2: Window Needed for 100% Efficiency

Frame transmission time Tt = 1 ms, propagation delay Tp = 20 ms. How large must the window be, and how many sequence number bits are needed?

a = Tp / Tt = 20
Window for 100% efficiency: N = 1 + 2a = 41 frames

Go-Back-N:  2^k − 1 ≥ 41  →  2^k ≥ 42   →  k = 6 bits (window up to 63)
Selective Repeat: 2^(k−1) ≥ 41 → 2^k ≥ 82 → k = 7 bits (window up to 64)

In general, the minimum number of bits is ⌈log2(N + 1)⌉ for Go-Back-N and ⌈log2(2N)⌉ for Selective Repeat.

Problem 3: Efficiency With a Limited Window

Same link as Problem 2, but the protocol is Go-Back-N with 3-bit sequence numbers.

Maximum window N = 2^3 − 1 = 7
η = N / (1 + 2a) = 7 / 41 ≈ 0.1707  →  17.07%

Compare that with Stop-and-Wait on the same link: 1/41 ≈ 2.44%. A window of 7 gives exactly 7 times the efficiency, as long as N is still less than 1 + 2a.


Where Are These Used?

  • Stop-and-Wait style acknowledgments are used where links are short, for example Wi-Fi acknowledges each unicast frame quickly at the link layer (modern Wi-Fi also has Block ACK for groups of frames).

  • Data link protocols such as HDLC define Go-Back-N and Selective Repeat style operation.

  • TCP (covered later in this tutorial) uses ideas from both: its ACK numbers are cumulative like Go-Back-N, but receivers usually keep out-of-order data, and the SACK option lets the receiver report exactly which blocks it has, much like Selective Repeat.


Common Mistakes

  • Using 2k as the Go-Back-N window. The maximum is 2k − 1.

  • Using 2k − 1 for Selective Repeat. The maximum is 2k−1, half the sequence space.

  • Forgetting the 2 in 1 + 2a. The sender waits for the frame to reach the receiver and for the ACK to come back.

  • Mixing up a. a = Tp / Tt, propagation over transmission, not the other way round.

  • Thinking Go-Back-N resends the whole window from the start. It resends from the lost (oldest unacknowledged) frame onwards, not frames that were already acknowledged.

  • Saying the receiver ignores a duplicate frame completely. It discards the data but must still send an ACK.


Interview Tips

  • Be ready to draw the lost ACK scenario for Stop-and-Wait and explain why it needs sequence numbers.

  • Explain the window limits with the "old frame looks new" argument rather than just quoting formulas.

  • If asked "Which is better, GBN or SR?", answer with the trade-off: SR saves bandwidth on lossy links but needs receiver buffers, per-frame timers and more complex logic.

  • Connect it to real life: "TCP's reliability is built on these same ideas: sequence numbers, ACKs, timeouts and a sliding window."

Conclusion

ARQ protocols make an unreliable link reliable using acknowledgments, timeouts, sequence numbers and retransmission.

Stop-and-Wait sends one frame at a time and is simple but inefficient when a = Tp/Tt is large: η = 1/(1 + 2a). Go-Back-N pipelines up to 2k − 1 frames but resends everything after a loss. Selective Repeat resends only the lost frames, at the cost of buffering, with a window of at most 2k−1.

The easiest way to remember it is:

Stop-and-Wait → one at a time. Go-Back-N → go back and resend the rest. Selective Repeat → resend only what was lost.