15 · Go-Back-N & Selective Repeat ★
Slides 3-25 → 3-42 · HW3 P5, P6, P7 · Sample midterm P4, 1d · the most likely exam problem
Primer: the 5 rdt ideas you need first
- ACK = the receiver tells the sender "got packet n OK".
- Sequence number on every packet, so the receiver can spot a duplicate (a retransmitted packet it already has).
- Timer: if no ACK arrives in time, the sender assumes loss and retransmits.
- Stop-and-wait: send one packet, wait for its ACK, then send the next. Seq #s 0 and 1 are enough (the "alternating-bit protocol"). Correct, but very slow.
- Pipelining: let many packets be "in flight" (sent but not yet ACKed). Needs a bigger range of seq #s and buffering. Two versions: Go-Back-N and Selective Repeat.
With a k-bit seq # field there are 2k seq #s: 0 to 2k − 1, and then they wrap around to 0. (k = 2 → 0, 1, 2, 3, 0, 1, …)
Window (size N or W) = the range of seq #s the sender may have in flight at once.
Go-Back-N (GBN)
| Sender | Receiver |
|---|---|
| Window of up to N consecutive sent-but-unACKed packets | Only accepts packets in order. Remembers just rcv_base (the next seq # it expects) |
| Cumulative ACK: ACK(n) means "everything up to and including n arrived". On ACK(n), slide the window to start at n+1 | Always ACKs the highest in-order seq # received so far. This can create duplicate ACKs |
| One timer, for the oldest unACKed packet | Out-of-order packet: discard it (or buffer; that's an implementation choice) and re-ACK the highest in-order seq # |
| Timeout(n): resend packet n and every higher packet in the window ("go back N") |
GBN in action (slide 3-36, N = 4, pkt2 lost)
| Sender | Receiver |
|---|---|
| send pkt0, 1, 2, 3 (pkt2 is lost) | rcv pkt0 → ack0 · rcv pkt1 → ack1 |
| rcv ack0 → send pkt4 · rcv ack1 → send pkt5 | rcv pkt3 → out of order, discard, re-send ack1 |
| ignore duplicate ack1s | rcv pkt4 → discard, ack1 · rcv pkt5 → discard, ack1 |
| pkt2 timeout → resend 2, 3, 4, 5 | rcv 2, 3, 4, 5 in order → deliver each, ack2, ack3, ack4, ack5 |
Packets 3, 4, 5 arrived fine the first time but get sent again. That's the waste GBN accepts in exchange for a simple receiver.
Selective Repeat (SR)
| Sender | Receiver |
|---|---|
| Window of N consecutive seq #s | Individually ACKs every correctly received packet, even out of order |
| A timer for each unACKed packet | Buffers out-of-order packets, then delivers them in order once the gap is filled |
| Timeout(n): resend only packet n | Has its own window of N seq #s |
| ACK(n): mark n as received. If n was the smallest unACKed, slide the base to the next unACKed seq # |
SR receiver rules (3-39)
- Packet n in [rcv_base, rcv_base + N − 1] → send ACK(n). Out of order → buffer. In order → deliver it plus any buffered in-order packets, and advance the window.
- Packet n in [rcv_base − N, rcv_base − 1] (an old one) → ACK(n) again, even though it was already received. (The sender may have lost the first ACK.)
- Otherwise → ignore.
SR in action (slide 3-40, N = 4, pkt2 lost)
| Sender | Receiver |
|---|---|
| send pkt0, 1, 2, 3 (pkt2 is lost) | rcv pkt0 → ack0 · rcv pkt1 → ack1 |
| rcv ack0 → send pkt4 · rcv ack1 → send pkt5 | rcv pkt3 → buffer, ack3 |
| record that ack3 arrived (and ack4, ack5) | rcv pkt4 → buffer, ack4 · rcv pkt5 → buffer, ack5 |
| pkt2 timeout → resend only pkt2 (not 3, 4, 5) | rcv pkt2 → deliver 2, 3, 4, 5, ack2 |
Q (slide): what happens when ack2 arrives? 3, 4, 5 are already ACKed, so the window base jumps to 6, and the sender can send pkts 6, 7, 8, 9.
GBN vs SR
| Go-Back-N | Selective Repeat | |
|---|---|---|
| ACKs | Cumulative | Individual |
| Timers | One (oldest unACKed) | One per packet |
| On timeout | Resend that packet and all after it | Resend only that packet |
| Out-of-order packets | Discarded | Buffered |
| Receiver window | Size 1 (only rcv_base) | Size N |
| Max window, k-bit seq # | 2k − 1 | 2k−1 (= half of 2k) |
Max window size: the core idea
• GBN: sender's window (W seq #s) + the 1 seq # the receiver expects next must all differ → W + 1 ≤ 2k → W ≤ 2k − 1.
• SR: sender's old window (W) + receiver's new window (W) must not overlap → 2W ≤ 2k → W ≤ 2k−1.
Sample midterm P4 (likely on the exam)
Q: GBN with k bits of sequence number. What's the maximum window size? Explain using an example with k = 2. Without a concrete example, you will not get any points.
Answer: max W = 2k − 1. With k = 2, seq #s are 0, 1, 2, 3, so max W = 3.
W = 4 fails
| Step | Sender | Receiver |
|---|---|---|
| 1 | Sends pkts 0, 1, 2, 3 | |
| 2 | Receives all 4 in order, delivers them, sends ACK0–ACK3. Now expects seq 0 (the new 5th packet, after wraparound) | |
| 3 | All 4 ACKs are lost | |
| 4 | Times out, resends the old pkts 0, 1, 2, 3 | |
| 5 | Gets old pkt 0. It's expecting seq 0, so it accepts the old packet as new data. ✗ Error: duplicate delivered |
W = 3 works
| Step | Sender | Receiver |
|---|---|---|
| 1 | Sends pkts 0, 1, 2 | |
| 2 | Receives all 3, delivers, sends ACK0–ACK2. Now expects seq 3 | |
| 3 | All 3 ACKs are lost | |
| 4 | Times out, resends old pkts 0, 1, 2 | |
| 5 | Gets pkt 0, but expects 3. Out of order → discard, re-ACK 2. ✓ Correct |
With W = 3, the expected seq # (3) is never in the set the sender could resend ({0, 1, 2}), so old and new packets can't be confused.
HW3 P7: GBN, 3 bits, show W = 8 fails
Seq #s are 0–7. Same story as above:
- Sender sends pkts 0–7.
- Receiver gets all 8, delivers them, ACKs 0–7, and now expects the new pkt 0.
- All ACKs are lost.
- Sender times out and resends the old pkts 0–7.
- Receiver expects seq 0, so it accepts the old pkt 0 as new data. Error.
Max W = 23 − 1 = 7.
SR dilemma (slides 3-41, 3-42)
Seq #s 0, 1, 2, 3 (k = 2), window size 3. Two scenarios that look identical to the receiver:
| (a) No problem | (b) Oops! |
|---|---|
| Sender sends 0, 1, 2. All ACKs arrive. Sender sends 3 (lost), then the new 0. | Sender sends 0, 1, 2. Receiver gets them and ACKs, but all ACKs are lost. Sender times out and retransmits the old 0. |
| Receiver's window is now {3, 0, 1}. It accepts the new 0 (buffers it). ✓ | Receiver's window is {3, 0, 1}. It accepts the old 0 as new data. ✗ |
The receiver can't see the sender's side, so it can't tell (a) from (b). Fix: W ≤ 2k−1 = 2. With W = 2, after receiving 0 and 1 the receiver's window is {2, 3}. An old 0 falls in [rcv_base − N, rcv_base − 1], so it just gets re-ACKed, not accepted.
Sample midterm 1d
Q: Under what condition is Selective Repeat the same as Stop-and-Wait?
HW3 P6: true or false
| Statement | Answer | |
|---|---|---|
| a | With SR, the sender can get an ACK for a packet outside its current window | True. The sender times out early and retransmits packets the receiver already got. The receiver ACKs both copies. After the first ACKs arrive, the window slides forward, so the second ACKs land outside it |
| b | Same, with GBN | True. Same scenario |
| c | Alternating-bit = SR with sender and receiver window 1 | True |
| d | Alternating-bit = GBN with sender and receiver window 1 | True |
HW3 P5: where can the GBN window be?
Q: GBN, sender window 4, seq range 1024. At time t the receiver expects seq k. The medium doesn't reorder.
(a) Possible sender windows
The receiver expects k, so it has received and ACKed everything through k − 1. The sender sent k − 1, so k − 1 was in its window → base ≥ k − 4. And the sender can't be past k, since k hasn't been ACKed.
- None of the last 4 ACKs (k−4 … k−1) have arrived yet → window [k−4, k−1]
- Some arrived → [k−3, k], [k−2, k+1], [k−1, k+2]
- All arrived → [k, k+3]
So base is anywhere from k − 4 to k: 5 possible windows.
(b) Possible ACK values in flight
k − 5 to k − 1. The receiver has ACKed up to k − 1 and nothing higher. If the base is k − 4, the sender must already have received ACK k − 5 (that's what moved the base there), and the receiver never sends anything lower than that again. Since the medium doesn't reorder, the ACKs still in flight range from k − 5 to k − 1.