Sliding Window Protocol at the Data Link Layer

Definition. In a sliding-window protocol both the sender and the receiver keep a window of sequence numbers. The sender may transmit several frames back-to-back without waiting for each individual acknowledgement, but never more than its window size $W_s$; the receiver is prepared to accept up to $W_r$ frames and acknowledges them cumulatively. As ACKs arrive, the window slides over the cyclic sequence-number space, so new frames may be sent while older ones are still being acknowledged. This single mechanism provides both error control and flow control.

With $n$ sequence bits the numbers run $0, 1, \dots, 2^n-1$ and then wrap around.

Working at the sender

1. Keep three counters: base (oldest unacknowledged frame), nextseqnum (next frame to send) and a timer for the oldest frame.
2. If nextseqnum lies inside the window [base, base + W_s - 1], transmit the frame, buffer it, advance nextseqnum; start the timer if it is the first unacknowledged frame.
3. On receiving ACK(n) (cumulative — all frames below n received correctly), advance base past n; slide the window, restart the timer for the new base if the window is not empty, otherwise stop it.
4. On timeout: Go-Back-N retransmits all unacknowledged frames; Selective Repeat retransmits only the missing ones.

Working at the receiver

1. A frame is accepted only if its sequence number equals the number expected; it is then delivered to the network layer and a cumulative ACK is returned.
2. Go-Back-N: out-of-order frames are simply discarded and the last correct ACK is re-sent, so the receiver needs no buffer.
3. Selective Repeat: out-of-order frames are buffered; frames are delivered as soon as the gap is filled, and each frame is ACKed individually.

Flow control

The receiver advertises its window; the sender keeps $W_s \le W_r$, so at most $W_r$ unprocessed frames are outstanding at a slow receiver — it is never overrun.

Bounds and efficiency

• Stop-and-wait is the special case $W_s = 1$ — only one frame outstanding, so the line idles for $1 + 2a$ bit-times per frame.
• $W_s \le 2^n - 1$ for Go-Back-N, and $W_s \le 2^{n-1}$ for Selective Repeat (see the proof of the Go-Back-N bound).
• Throughput: $\displaystyle \eta = \frac{W}{1+2a}$ for $W \le 1+2a$, where $a = T_{prop}/T_{trans}$; for $W > 1+2a$ the channel is saturated and $\eta = 1$.

Timeline (window $W = 4$, Go-Back-N)

  time --->

  Sender                                            Receiver
  -------------------------------------------------------------
  W = [0,1,2,3]
   | --- Frame 0 ---------------------------------> |  expects 0 -> deliver
   | --- Frame 1 ---------------------------------> |  expects 1 -> deliver
   | --- Frame 2 ---------------------------------> |  expects 2 -> deliver
   | --- Frame 3 ---------------------------------> |  expects 3 -> deliver
   |                                                |  (window now full:
   |        channel keeps busy — no waiting!)       |   sender must stop)
   |<------------- cumulative ACK 4 --------------- |
   |  W slides to [4,5,6,7]                        |  expects 4
   | --- Frame 4 ---------------------------------> |
   | --- Frame 5 ----------X  (lost)               |  expects 6, got 5 -> discard
   | --- Frame 6 ---------------------------------> |  (out of order: discard)
   | --- Frame 7 ---------------------------------> |  discard, resend ACK 6
   |
   |  timeout for base = 4 expires                 |
   |  Go-Back-N: retransmit 4, 5, 6, 7 ----------> |  4,5,6,7 accepted -> ACK 8