Sliding window: Go-Back-N and Selective Repeat
Sliding-window flow-control and ARQ protocols (Go-Back-N and Selective Repeat): how window size, sequence-number space and ACKing affect reliability, throughput and ambiguity.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Sliding-window protocols are used by real network and transport-layer engineers to get high throughput over links with non-negligible round-trip time. An engineer picks between Go-Back-N and Selective Repeat depending on error patterns, memory and timer complexity, and the available sequence-number space.
Key ideas
Start with first principles: a reliable data transfer protocol must (1) deliver frames in order and without duplication, (2) cope with loss and corruption, and (3) use the channel efficiently.
- Frame (or packet): a block of user data sent across the channel.
- Sequence number: a small integer attached to each frame to identify its position in the sender's sequence. Sequence numbers wrap modulo k (i.e., they range 0..k-1). Define k as the sequence-number space size.
- Window: the set of sequence numbers that a sender (or receiver) is currently allowed to send (or accept). The size of that set is the window size N. Windowing allows pipelining multiple frames without waiting for an ACK for each.
- ACK (acknowledgement): a control message from the receiver that informs sender which frames have been received. An ACK can be cumulative (acknowledges all frames up to a given sequence) or selective (acknowledges individual frames).
- Timer: used to trigger retransmission on timeout. In Go-Back-N (GBN) typically a single timer is used for the oldest unacked frame; in Selective Repeat (SR) a timer per transmitted-but-not-yet-acked frame is usual.
Assumptions commonly used in analysis (state these in an exam): packets may be lost or corrupted independently, ACKs may be lost/corrupted, channel can reorder frames (or not, depending on model). SR requires receiver buffering of out-of-order frames; GBN discards out-of-order frames at the receiver.
Exact protocol behaviour (what to draw and label for each):
Go-Back-N (GBN): Sender variables: base (sequence number of oldest unacked frame), nextseqnum (smallest unused seq num). Sender may send while nextseqnum < base + N. Receiver accepts only the frame with sequence number equal to its expected value (call it expected); if correct, deliver to upper layer and increment expected, then send cumulative ACK for expected (commonly ACK contains expected). If out of order, receiver discards the frame and re-sends ACK for expected. The receiver window size is 1. On timeout for base, sender retransmits all frames from base to nextseqnum-1.
- Diagram to draw for an exam: timeline showing sender sending frames 0,1,2,... with arrows to receiver; mark when a frame is lost and show retransmission of a block from the base.
Selective Repeat (SR): Sender also has base and nextseqnum and can send up to N outstanding frames. Receiver accepts any frame whose seq number falls inside its receive window (size N) and buffers out-of-order frames; it sends a separate ACK for each correctly received packet. In these SR examples, ACK(x) denotes an acknowledgement for packet with sequence number x (not the next expected). On timeout for a particular packet, the sender retransmits only that packet. Receiver delivers in-order data to upper layer when contiguous sequence numbers from expected are present in buffer.
- Diagram: timeline with out-of-order arrival (e.g., 1 arrives before 0), receiver buffers 1 and sends ACK(1); when 0 arrives, deliver 0 then 1.
Critical constraints to avoid ambiguity and duplicate delivery (exact statements):
- For GBN: the sequence-number space k must satisfy
- k ≥ N + 1. Equivalently, window size N ≤ k − 1. Reason: after N unacked frames transmitter could send a frame whose sequence number equals an earlier unacknowledged frame when wrap-around happens; having k ≥ N+1 prevents ambiguity between old and new frames.
- For SR: the sequence-number space must satisfy
- k ≥ 2N. Equivalently, N ≤ k/2. Reason: the receiver must be able to distinguish a newly transmitted frame from a very late duplicate of an earlier frame that had the same sequence number after wrap-around. With N ≤ k/2 there is no overlap between one sender window and the next expected receiver window after k sequence numbers.
Explain why SR requires more memory and timers: the receiver must buffer up to N out-of-order frames; sender needs separate timers (or a mechanism equivalent) to retransmit individually.
Compare trade-offs: GBN has simpler receiver and one timer but more retransmissions when loss occurs (retransmit all unacked frames after the lost one). SR reduces retransmissions (only lost frames) but needs more buffers and timer complexity.
Formulas
BDP = b * RTT — bandwidth-delay product (bits). b is link bandwidth (bits per second), RTT is round-trip time (seconds). Use to size the window (in bits; convert to bytes if needed).
- b: link bandwidth, units bits/s. RTT: round-trip time, s.
N_packets >= BDP / L — minimum number of packets to fill the pipe. L is packet payload size in bits, N_packets is window size as a packet count.
- L: packet size in bits, units bits.
k >= N + 1 — sequence-number space requirement for Go-Back-N.
- k: sequence-number space size (integer), N: sender window size (packets).
k >= 2N — sequence-number space requirement for Selective Repeat (equivalently N <= k/2).
Throughput = min( b , (N * L) / RTT ) — long-term throughput in bits/s when there are no losses and sender uses window N (simple capacity-limited model). Use this to pick N so that sender keeps the pipe full: choose N so that (N * L) / RTT ≥ b.
- b: link bandwidth (bits/s), L: packet size (bits), RTT: seconds, N: packets.
Note: timers, retransmission intervals and loss rates complicate throughput; above formula assumes no loss and steady-state behaviour.
Worked examples
Example 1 — GBN trace (protocol behaviour):
- Parameters: k = 4 (seq nums 0..3), N = 3 (allowed by k ≥ N + 1). Use ACK semantics: ACK(x) means receiver's next expected seq number is x.
- Start: sender base=0, nextseqnum=0. Sender transmits frames 0,1,2 (nextseqnum becomes 3) since nextseqnum < base+N.
- Receiver expected=0.
- Frame 0 arrives OK → deliver to upper layer, expected=1. Receiver sends ACK(1).
- Frame 1 is lost in channel (never arrives). Receiver does nothing; it may resend last ACK(1) if desired.
- Frame 2 arrives at receiver out-of-order (expected=1) → GBN receiver discards frame 2 and re-sends ACK(1).
- Sender receives ACK(1) (cumulative for 0) — base moves to 1. Because base=1 and nextseqnum=3, still have one outstanding frame (seq 2). Sender can send frame 3 (since nextseqnum < base + N => 3 < 1+3 true). Sender sends frame 3.
- Timer for base (seq 1) expires (no ACK for 1), so sender retransmits frames 1,2,3 (all from base to nextseqnum-1).
- Suppose now frames 1 and 2 arrive and are acked; ACK(3) moves base to 3; then ACKs move to complete.
- Final result: lost frame 1 caused retransmission of frames 1..3 together. This is the characteristic waste in GBN.
Example 2 — SR trace (step-by-step):
- Parameters: k = 8 (0..7), N = 4 (allowed since k ≥ 2N). Sender base=0, nextseqnum=0. Receiver expected=0, receive window covers 0..3.
- Sender sends 0,1,2,3. Receiver gets 0 and 2 (1 lost). On getting 0, deliver up, send ACK(0). On getting 2 (out-of-order but within receive window), buffer it and send ACK(2).
- Sender receives ACK(0) and ACK(2). It clears timers for 0 and 2. On timeout for 1 (timer per packet), retransmit only packet 1.
- Receiver gets 1, now it can deliver 1 and the buffered 2 in order to upper layer and sends ACKs. Sender now advances base appropriately.
- Final result: only lost packet 1 was retransmitted, not the whole block — SR saves bandwidth at the cost of buffers and timers.
Example 3 — numeric window size from link parameters:
- Given: link bandwidth b = 2 Mbps (2·10^6 bits/s), RTT = 50 ms (0.05 s), packet size L = 1500 bytes = 12,000 bits.
- Compute BDP:
BDP = b * RTT = 2e6 * 0.05 = 100000 bits. - Required packets:
N >= BDP / L = 100000 / 12000 ≈ 8.333. So chooseN = 9packets to keep the pipe full. Answer: N = 9 packets.
Common mistakes
- Forgetting receiver buffering needs for SR: claiming SR's receiver just discards out-of-order frames (that describes GBN).
- Forgetting that GBN retransmits a block starting from the lost packet, not just the single lost packet.
- Mixing units in BDP calculation (bits vs bytes). Always convert packet size and bandwidth into the same unit (bits).
- Not carrying units through a numeric calculation.
For your exam
Question types you will see: definitions (define window, ACK types, sequence-number space), short notes (advantages/disadvantages of GBN vs SR), derivations (show why k ≥ 2N for SR), protocol traces (step-by-step sender/receiver windows and timers), and numericals (compute required N from bandwidth and RTT).
What a full-marks answer includes:
- Correct definitions of all bold terms used, and the assumptions stated clearly.
- For constraints, state the exact inequality (k ≥ N+1 or k ≥ 2N) and give a short proof or reasoning to show why ambiguity can occur otherwise.
- For traces, show sender base/nextseqnum and receiver expected/receive-window at each step; show timers and retransmissions clearly.
- For numericals, show all formulas used, substitute values with units, carry units through, and give the final value with units.
Quick check
- What is the receiver action on an out-of-order frame in GBN?
- State the sequence-number-space condition for Selective Repeat.
- Using BDP, how many 1,500-byte packets are needed to fill a 10 Mbps link with RTT = 40 ms?
Answers: 1) Discard the out-of-order frame and re-send cumulative ACK for the next expected frame. 2) k ≥ 2N (equivalently N ≤ k/2). 3) BDP = 10e6 * 0.04 = 400000 bits; packet = 1500·8 = 12000 bits; N ≈ 400000/12000 ≈ 33.333 → choose 34 packets.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?