Automatic Repeat Request (ARQ)

🧭

On this page — click any heading below to jump straight to it. ⬅️ Back to P-II.II. Computer Communications & Networks

---

OSI Layer: Data Link Layer (L2)

Definition

ARQ (Automatic Repeat reQuest) is an error-control method for reliable data transmission that combines error detection (e.g., CRC/checksum) with retransmission of corrupted or lost frames, driven by acknowledgments (ACK) and timeouts — the family of techniques that TCP's own reliability mechanisms are conceptually built from.

Types of ARQ

1. Stop-and-Wait ARQ

• Sender transmits one frame, then stops and waits for an ACK before sending the next.
• If the ACK doesn't arrive before a timer expires (frame lost, or ACK itself lost), the sender retransmits the same frame.
• Advantages: extremely simple to implement, minimal buffering needed (only one frame at a time).
• Disadvantages: very inefficient on high-delay or high-bandwidth links — the sender sits idle for a full round-trip time after every single frame, wasting available bandwidth.

2. Go-Back-N (GBN) ARQ

• Sender may transmit up to N frames (a "window") before needing an acknowledgment — a pipelined/sliding-window scheme.
• Receiver uses cumulative acknowledgment: it only accepts frames in strict order and discards any frame that arrives out of sequence, ACKing only the last correctly-received in-order frame.
• If a frame is lost or corrupted, the sender must retransmit that frame and every subsequent frame already sent in the window — even ones the receiver actually received correctly — because the receiver discarded them for arriving out of order.
• Advantages: simple receiver logic (only needs one buffer slot, no reordering needed).
• Disadvantages: wasteful retransmission on lossy links — a single lost frame forces re-sending the entire remaining window.

3. Selective Repeat (SR) ARQ

• Also uses a sliding window, but the receiver buffers out-of-order frames that arrive correctly instead of discarding them, and individually ACKs each correctly-received frame.
• Only the specific corrupted/lost frame is retransmitted, not the whole window after it.
• Advantages: much more efficient on lossy/high-delay links — minimal wasted retransmission.
• Disadvantages: requires more complex buffering and sequence-number management at the receiver; sender and receiver windows must be sized carefully (window size ≤ half the sequence number space) to avoid ambiguity between old and new frames.

Sliding Window Size Trade-off

A bigger window allows more frames in flight (higher throughput, better link utilisation), but on an error-prone link a bigger window under Go-Back-N also means more wasted retransmission per error — this trade-off is exactly why Selective Repeat exists as a more efficient (but more complex) alternative.

Comparison Table

Numericals

Q1 — Stop-and-Wait efficiency

Transmission time Tt = 1 ms, one-way propagation delay Tp = 5 ms (so a = Tp/Tt = 5).

• Efficiency U = Tt / (Tt + 2Tp) = 1 / (1 + 10) = 1/11 ≈ 9.09%
• Over 90% of the link's capacity sits idle while waiting for each ACK — the core motivation for pipelined (windowed) protocols.

Q2 — Windowed protocol efficiency (GBN/SR) with window size W

Using the same link (a = 5, so 1 + 2a = 11):

• If window W = 4: efficiency = W / (1 + 2a) = 4/11 ≈ 36.4% — better than stop-and-wait, but still not full utilisation.
• If window W = 11 (= 1 + 2a): efficiency = 11/11 = 100% — the window is exactly large enough to keep the link continuously busy while waiting for the first ACK to return; any window larger than this brings no further benefit unless the link's bandwidth-delay product itself grows.

Q3 — Retransmission cost comparison after one lost frame

Window size = 5, frame 2 (of 5 in flight) is lost; frames 3, 4, 5 already arrived correctly at the receiver.

• Go-Back-N: retransmits frames 2, 3, 4, 5 (4 frames) — even though 3, 4, 5 were already received correctly.
• Selective Repeat: retransmits only frame 2 (1 frame) — the receiver had already buffered 3, 4, 5.
• This 4:1 retransmission-cost ratio in this example is exactly why Selective Repeat is preferred on lossy links despite its higher implementation complexity.

CSS Exam Angle

• A near-guaranteed diagram question — draw simple timeline diagrams (sender/receiver arrows over time) for Stop-and-Wait vs Go-Back-N vs Selective Repeat, explicitly marking which frames get retransmitted after a loss.
• The efficiency formula U = Tt/(Tt+2Tp) for stop-and-wait, and its windowed generalisation U = W/(1+2a), is a common numerical component — memorise both.
• State the retransmission-cost trade-off (GBN retransmits the whole window tail; SR retransmits only the lost frame) as the single clearest way to differentiate the two windowed protocols.
• Link this topic explicitly to "Reliable Data Transfer and TCP" — TCP's own retransmission behaviour is conceptually closest to Selective Repeat combined with cumulative-ACK elements from Go-Back-N.

Example

TCP's own retransmission mechanism blends ideas from this family: it uses cumulative ACKs like Go-Back-N, but with selective acknowledgment (SACK) extensions behaving like Selective Repeat, retransmitting only the specific missing segments rather than everything after them — a good link to draw between this topic and TCP's reliability mechanisms.

Likely Questions

1. Compare Stop-and-Wait, Go-Back-N, and Selective Repeat ARQ protocols with diagrams.
2. Calculate the efficiency of a stop-and-wait protocol given transmission time and propagation delay.
3. Why does Go-Back-N retransmit more frames than Selective Repeat after a single lost frame? Illustrate with an example.
4. What window size is needed for a sliding-window protocol to achieve 100% link utilisation?|

📘 CSS Computer Science — Numerical Formula Cheat Sheet

---

1. Data Communication & Networking

Transmission Time

Tt = Message Size (bits) / Data Rate (bps)

• Example: Message = 1,000 bits, Rate = 100 Mbps
• Calculation: Tt = 1,000 / (100 * 10^6) = 10 µs

---

Propagation Delay

Tp = Distance / Propagation Speed

• Example: Distance = 2,000 km, Speed = 2 * 10^8 m/s
• Calculation: Tp = (2 * 10^6) / (2 * 10^8) = 0.01 s = 10 ms

---

Total Delay

Ttotal = Tt + Tp + Tq + Tprocessing

💡 Simplified Form (Ignoring Queueing & Processing):

Ttotal = Tt + Tp

---

Bandwidth-Delay Product (BDP)

BDP = Bandwidth * RTT

• Example: Bandwidth = 100 Mbps, RTT = 20 ms
• Calculation: BDP = (100 * 10^6) * 0.02 = 2,000,000 bits

---

2. Stop-and-Wait ARQ

• Propagation/Transmission Ratio: a = Tp / Tt
• Efficiency / Utilization: η = 1 / (1 + 2a)
• Sender Window (Ws): 1
• Receiver Window (Wr): 1
• Example: If a = 2
  • η = 1 / (1 + 4) = 1/5 = 20%

---

3. Go-Back-N ARQ

For a k-bit sequence number:

• Sequence Numbers: 2^k
• Max Sender Window (Ws): 2^k - 1
• Receiver Window (Wr): 1
• Efficiency (η): min(1, Ws / (1 + 2a))
• Example: k = 3 → Ws = 2^3 - 1 = 7
  • If a = 1: η = 7 / (1 + 2) = 7/3 → 100% (Capped at 100%)

---

4. Selective Repeat ARQ

For a k-bit sequence number:

• Sender & Receiver Window (Ws = Wr): 2^(k - 1)
• Efficiency (η): min(1, Ws / (1 + 2a))
• Example: k = 3 → Ws = Wr = 2^(3 - 1) = 4

---

5. Sliding Window — General

• Frames Outstanding: W
• Full Utilization Requirement: W ≥ 1 + 2a
• Example: If a = 4 → W ≥ 1 + 2(4) → W ≥ 9 frames

---

6. Bit Rate Basics

Bit Rate = Total Bits / Time (seconds)

💡 Key Conversion: 1 Byte = 8 bits

• Example: 10 MB transmitted in 2 seconds
  • 10 MB = 80 Mb
  • Bit Rate = 80 / 2 = 40 Mbps

---

7. Nyquist Bit Rate (Noiseless Channel)

Bit Rate = 2 * B * log2(L)

• B = Bandwidth (Hz)
• L = Number of signal levels
• Example: Bandwidth = 3 kHz, Levels = 4
  • Bit Rate = 2 * 3000 * log2(4) = 6000 * 2 = 12,000 bps

---

8. Shannon Capacity (Noisy Channel)

Capacity (C) = B * log2(1 + SNR)

SNR (linear) = 10^(SNRdB / 10)

• Example: Bandwidth = 3 kHz, SNR = 30 dB
  • SNR = 10^(30/10) = 1000
  • C = 3000 * log2(1001) ≈ 29.9 kbps

---

9. Signal-to-Noise Ratio (SNR)

• Linear SNR: SNR = Signal Power / Noise Power
• Decibel Scale: SNRdB = 10 * log10(SNR)
• Example: Signal = 100 W, Noise = 1 W
  • SNR = 100 → SNRdB = 10 * log10(100) = 20 dB

---

10. Packet Switching

Number of Packets (N) = ⌈ Message Size (M) / Payload Size (P) ⌉

• Example: Message = 10,000 bytes, Payload = 1,000 bytes
  • N = 10,000 / 1,000 = 10 packets

---

11. Error Detection & Hamming Code

• Even Parity: Total number of 1s must be even.
• Odd Parity: Total number of 1s must be odd.

Hamming Code Condition

2^r ≥ m + r + 1

• m = Data bits
• r = Parity bits
• Example: Data bits m = 4
  • Try r = 3: 2^3 ≥ 4 + 3 + 1 → 8 ≥ 8 (Valid)
  • Total transmitted bits = m + r = 7 bits

---

12. IP Addressing & Subnetting

• IPv4 Address Space: 2^32 (~4.29 Billion)
• Total Hosts per Subnet: 2^h
• Usable Hosts: 2^h - 2 (h = host bits)

Subnet Reference Table

• Number of Subnets: 2^s (s = borrowed bits)

---

13. TCP Concepts

• ACK Number Rule: ACK = Next Byte Expected
• TCP Throughput Approximation: Throughput ≈ Window Size / RTT
• Example: Window = 64 KB (65,536 Bytes), RTT = 100 ms (0.1 s)
  • Throughput = 65,536 / 0.1 = 655,360 B/s ≈ 5.24 Mbps

---

14. Data Structure Complexity

---

15. Sorting Algorithm Complexity

---

16. CPU Performance & Amdahl's Law

CPU Time = (Instruction Count * CPI) / Clock Rate

CPU Cycles = Instruction Count * CPI

• Example: IC = 10^6, CPI = 2, Clock Rate = 1 GHz (10^9 Hz)
  • CPU Time = (10^6 * 2) / 10^9 = 0.002 s = 2 ms

Amdahl's Law (Speedup)

Speedup = 1 / [ (1 - f) + (f / s) ]

• f = fraction improved
• s = speedup of improved part

---

⭐ CSS Must-Memorize Top 15

1. Transmission Time: Tt = Bits / Data Rate
2. Propagation Delay: Tp = Distance / Speed
3. Round Trip Time: RTT ≈ 2 * Tp
4. Stop-and-Wait Efficiency: η = 1 / (1 + 2a)
5. Go-Back-N Window: Ws = 2^k - 1
6. Selective Repeat Window: Ws = Wr = 2^(k - 1)
7. Hamming Code Rule: 2^r ≥ m + r + 1
8. Shannon Capacity: C = B * log2(1 + SNR)
9. Decibel SNR: SNRdB = 10 * log10(SNR)
10. Nyquist Bit Rate: Bit Rate = 2 * B * log2(L)
11. Usable Subnet Hosts: Usable Hosts = 2^h - 2
12. Subnet Count: Subnets = 2^s
13. CPU Time: CPU Time = (IC * CPI) / Clock Rate
14. Amdahl's Law: Speedup = 1 / ((1 - f) + (f / s))
15. Binary Search: Comparisons = O(log2 n)

📜 Past-Paper Questions & Structured Answers

Coverage check: no standalone question on Stop-and-Wait, Go-Back-N or Selective Repeat ARQ was located in the reviewed 2016–2026 descriptive papers or the available 2024–2026 Paper-II MCQ sheets. This is not proof that it has never appeared. Questions labelled “Likely” above are practice, not verified past-paper questions.

Relevant preparation: These are foundations for reliable delivery. Revise acknowledgements, timeouts, sequence numbers and window size, then study the 2021 TCP-window calculation in Reliable Data Transfer and TCP. A TCP bandwidth-delay-product question is not a direct Go-Back-N question.