CAP7001 · Unit 3: Data link layer
Stop-and-wait, go-back-N and selective repeat ARQ
14 practice questions · in the MTE and ETE syllabus
Key points
- Go-Back-N window 2^m - 1; Selective Repeat window 2^(m-1)
- Go-Back-N resends from the lost frame onward
- Selective Repeat resends only the lost frame
- Windows too large make duplicates look new
ARQ (Automatic Repeat reQuest) retransmits frames that are lost or damaged. With m-bit sequence numbers:
| Protocol | Sender window | Receiver window | On a lost frame |
|---|---|---|---|
| Stop-and-Wait | 1 (numbers 0, 1) | 1 | Resend after timeout |
| Go-Back-N | 2^m - 1 | 1 | Resend that frame and all after it |
| Selective Repeat | 2^(m-1) | 2^(m-1) | Resend only the lost frame |
Go-Back-N uses cumulative ACKs and the receiver discards out-of-order frames. Selective Repeat buffers them. Go-Back-N utilisation is U = N / (1 + 2a).
Worked example: frames 0-9 sent, frames 2 and 6 lost once: Go-Back-N sends 10 + 8 = 18 frames; Selective Repeat sends 10 + 2 = 12. With a = 20 and N = 7, U = 7/41, about 17.1%.
Exam pitfall: a Go-Back-N window of 2^m is wrong: if all ACKs are lost, a resent frame 0 looks like a new frame 0. Selective Repeat above 2^(m-1) has the same overlap problem.
Try two questions
A Go-Back-N link needs a window of 1 + 2 x 12 = 25 frames for continuous transmission, and the sender window is at most 2^m - 1. What is the smallest number of sequence-number bits m that allows this?
- 4 bits
- 6 bits
- 7 bits
- 5 bits
Show the answer
D. With m = 4 the window is at most 15, which is too small, and with m = 5 it is at most 31, which covers 25. Selective Repeat would need m = 6 because its window is 2^(m-1).
Why not A: With 4 bits the largest window is 15, which is below 25.
Why not B: That is the answer for Selective Repeat, whose window is 2^(m-1).
Why not C: That is more bits than needed, since 5 bits already allow a window of 31.
In Go-Back-N ARQ, what is the size of the receiver window?
- N
- 1
- 2^m
- 2^(m-1)
Show the answer
B. The Go-Back-N receiver accepts only the next expected frame, so its window size is 1, and out-of-order frames are discarded.
Why not A: N is the size of the sender window.
Why not C: 2^m is the number of sequence numbers and not a window size.
Why not D: 2^(m-1) is the window size in Selective Repeat.