ARQ Protocols: Stop-and-Wait, Go-Back-N & Selective Repeat
Automatic Repeat reQuest (ARQ) is an error-control mechanism for reliable data delivery at the Data Link layer. When the receiver detects an error (via CRC) or a frame is lost, it requests retransmission.
---
1. Data Link Layer Framing
Before discussing ARQ, understand how frames are delimited:
| Method | How It Works | Example |
|---|---|---|
| Character count | First field in header gives frame length | Simple but fragile if header corrupted |
| Flag bytes | Special byte 01111110 marks start/end; stuffing prevents false flags | HDLC |
| Bit stuffing | Sender inserts a 0 after five consecutive 1s; receiver removes it | HDLC, PPP |
| Byte stuffing | Special escape byte inserted before any flag byte in data | PPP, SLIP |
---
2. Stop-and-Wait ARQ
The simplest ARQ protocol.
How It Works
- Sender transmits one frame and starts a retransmission timer
- Sender waits for an ACK (acknowledgement) from the receiver
- If ACK received before timeout → send next frame
- If timeout before ACK → retransmit the same frame
- If receiver gets NAK (negative acknowledgement) → retransmit immediately
Efficiency Analysis
For a link with propagation delay Tp and transmission time Tt:
- Bandwidth-delay product =
Tt / (Tt + 2 × Tp)=1 / (1 + 2a)wherea = Tp / Tt
Example: Satellite link, Tt = 1 ms, Tp = 270 ms (round trip = 540 ms)
a = 270 / 1 = 270- Efficiency ≈ 1 / (1 + 2×270) ≈ 0.18% — catastrophically inefficient!
Solution: Use sliding window protocols (Go-Back-N or Selective Repeat) to keep multiple frames "in flight."
Stop-and-Wait Characteristics
| Feature | Detail |
|---|---|
| Sequence numbers needed | 1 bit (0 and 1) — alternates |
| Sender window size | 1 |
| Receiver window size | 1 |
| Efficiency | Very low on high-latency links |
| Implementation | Simple |
Exam Tip: Stop-and-Wait requires only 1-bit sequence numbers (alternating bit protocol). Efficiency = 1 / (1 + 2a). For low bandwidth-delay product links it's acceptable; for high-latency links like satellite, it wastes 99%+ of bandwidth.
---
3. Sliding Window Protocol
Sliding window allows the sender to have multiple frames outstanding (unacknowledged) simultaneously — the "window" of frames in flight.
Window Size Concepts
- Sender window (Ws): Maximum frames sender can have unacknowledged
- Receiver window (Wr): Maximum frames receiver will accept out of order
- Sequence number space: Must be large enough for both windows
---
4. Go-Back-N (GBN) ARQ
How It Works
- Sender transmits frames continuously within its window
- Receiver accepts frames in order only
- If frame N is in error/lost:
- Receiver discards frame N and all subsequent frames
- Sends NAK N (or stops sending ACKs)
- Sender goes back and retransmits frame N and all subsequent frames
GBN Window Sizes
- Sequence number bits: n
- Sender window:
Ws = 2^n − 1 - Receiver window:
Wr = 1(accepts only in-order frames) - Example: n=3 bits → Ws = 7, sequence numbers 0–7
Efficiency
- With window size W and bandwidth-delay parameter a:
- If
W ≥ 2a + 1: Efficiency = 1 (100%) - If
W < 2a + 1: Efficiency =W / (2a + 1)
GBN Characteristics
| Feature | Detail |
|---|---|
| Sequence numbers | n bits → 2^n − 1 max sender window |
| Retransmission on error | Frame N + all subsequent frames (wasteful) |
| Buffer at receiver | Not needed (in-order only) |
| Efficiency | Moderate — wasted on error recovery |
| Complexity | Moderate |
---
5. Selective Repeat (SR) ARQ
How It Works
- Sender transmits frames within its window (same as GBN)
- Receiver accepts frames out of order and buffers them
- If frame N is in error/lost:
- Receiver sends NAK N / SREJ (Selective Reject)
- Sender retransmits only frame N — not subsequent frames
- Once frame N arrives correctly, receiver delivers buffered frames in order
SR Window Sizes
- Sequence number bits: n
- Sender window:
Ws = 2^(n−1) - Receiver window:
Wr = 2^(n−1) - Example: n=3 → Ws = Wr = 4, sequence numbers 0–7
- Why smaller window than GBN? To ensure receiver can always distinguish old frames from new frames correctly
SR Characteristics
| Feature | Detail |
|---|---|
| Sequence numbers | n bits → max window = 2^(n−1) |
| Retransmission on error | Frame N only |
| Buffer at receiver | Required (buffers out-of-order frames) |
| Efficiency | Highest — only retransmits what's necessary |
| Complexity | Highest |
---
6. ARQ Protocol Comparison Table
| Feature | Stop-and-Wait | Go-Back-N | Selective Repeat |
|---|---|---|---|
| Sender window | 1 | 2^n − 1 | 2^(n−1) |
| Receiver window | 1 | 1 | 2^(n−1) |
| Retransmit on error | 1 frame | Frame N + all after | Frame N only |
| Receiver buffer | 1 | 1 | Large buffer needed |
| Sequence bits | 1 bit | n bits | n bits |
| Efficiency | Very low | Moderate | High |
| Complexity | Simplest | Moderate | Most complex |
| Best for | Low BDP links | General use | High BDP, noisy links |
Exam Tip: Sender window sizes: Stop-and-Wait = 1, GBN =2^n − 1, SR =2^(n-1). The SR window is half the GBN window — crucial distinction. SR is more efficient because it only retransmits erroneous frames, not all subsequent frames.
---
Study Deep: ARQ in Modern Networks
- TCP uses a form of Selective Repeat: TCP's selective acknowledgement (SACK) option allows the receiver to report non-contiguous received data, so the sender only retransmits missing segments — exactly like Selective Repeat.
- Wi-Fi uses ARQ at Layer 2: 802.11 (Wi-Fi) uses its own ARQ at the MAC layer — every frame must be acknowledged, with automatic retransmission on loss.
- Why Go-Back-N is rarely used in practice: The wasted bandwidth from retransmitting non-erroneous frames makes it uncompetitive with Selective Repeat on any link where errors are non-trivial. GBN is mainly taught for academic comparison.
- HDLC (High-level Data Link Control): The standard Data Link layer protocol that implements sliding window ARQ. PPP (Point-to-Point Protocol) over phone lines also uses HDLC framing.