Q5A · Selective Repeat with three bits

Answer

Selective Repeat (SR) ARQ accepts and buffers valid out-of-order frames inside the receiver window, acknowledges them individually and retransmits only missing/timed-out frames. In this answer ACK i means “frame i received”, unlike the next-expected cumulative ACK convention used for GBN.

Swipe across the diagram to read its labels ↔

Diagram: SR W=4: individual ACKs and buffering. Labels: SR W=4: individual ACKs and buffering | SR W=4: individual ACKs and buffering | Sender | Receiver | Frames 0,1 → accept and deliver | ACK 0 and ACK 1 individually | Frame 2 lost; frame 3 arrives | ACK 3; keep frame 3 in buffer | Timer for frame 2: resend only 2 | ACK 2; deliver 2, then buffered 3 | Sequence space 0…7; equal windows at most 4. | ACK i means that specific frame i was accepted.

1. For m=3 there are eight sequence numbers, 0…7. With equal sender and receiver windows, maximum W=2³⁻¹=4. Both windows begin at 0 and span 0…3.
2. Sender sends 0,1,2,3. Receiver accepts 0 and 1, delivers them and advances its left edge to 2. Frame 2 is lost; frame 3 is stored and ACK 3 is sent.
3. Although 3 is acknowledged, the sender’s base cannot jump over missing 2. A timer for 2 expires; only frame 2 is retransmitted.
4. When 2 arrives, the receiver can deliver 2 and the buffered 3 in order, moving its window forward. Individual ACKs let the sender release the relevant stored copies.
5. Why half the space: with an incorrectly chosen W=5 in an eight-number space, receiving old 0…4 moves the receive window to {5,6,7,0,1}. If ACKs are lost, retransmitted old 0 or 1 could fall in the new window and be mistaken for new data. W=4 prevents these two consecutive windows from overlapping.
6. A repeated old frame can be acknowledged again without delivering it twice. SR needs more receiver storage and per-frame tracking than GBN.

LaTeX: W_s=W_r\le 2^{m-1}