Sliding Window Protocol | Computer Networks - Computer Science Engineering (CSE) PDF Download

Introduction

The sliding window is a flow-control and error-control technique used to send multiple frames (or packets) before requiring an acknowledgement. It is widely used where reliable, ordered, and efficient delivery of frames is required. The method is central to data-link layer ARQ (Automatic Repeat reQuest) protocols and is also a core mechanism in the transport layer protocol TCP.

• The sender assigns a sequence number to every frame. Sequence numbers enable the receiver to detect missing, duplicate, or out-of-order frames.
• The technique permits pipelining of frames: the sender may transmit several frames within a permitted window without waiting for individual acknowledgements for each one.
• The primary goals are to improve channel utilisation, provide reliable delivery, and avoid duplication by using sequence numbers and acknowledgements.

Types of Sliding Window Protocol

There are two standard ARQ protocols that use the sliding window concept:

• Go-Back-N ARQ
• Selective Repeat ARQ

Go-Back-N ARQ

Go-Back-N ARQ is an ARQ protocol that uses a sender window of size N and a receiver window of size 1. The sender may transmit up to N frames without receiving an acknowledgement. The receiver only accepts frames in order; if a frame is corrupted or missing, the receiver discards that frame and all subsequent frames until the missing one is correctly received.

• The sender window size is N. For example, in a Go-Back-8 system the sender window size is 8.
• The receiver window size is 1: the receiver only accepts the next expected frame and discards any later frames that arrive out of order.
• When a frame is detected as lost or corrupted, the receiver ignores subsequent frames and the sender must retransmit the lost frame and all frames sent after it (hence "go back" N).
• A timeout for the oldest unacknowledged frame triggers retransmission of that frame and all subsequent outstanding frames in the sender window.
• Acknowledgements are normally cumulative ACKs: an ACK for sequence number k indicates that all frames up to k have been received correctly.

An illustrative transmission example is shown below.

Selective Repeat ARQ

Selective Repeat ARQ improves efficiency in error-prone channels by retransmitting only the frames that are detected as erroneous or lost, rather than retransmitting a block of frames.

• The sender and receiver window sizes are equal (commonly denoted as N) and typically greater than 1.
• The receiver accepts frames that arrive out of order and buffers them until any missing frames with lower sequence numbers are received; it then delivers data to the upper layer in order.
• The receiver sends an individual acknowledgement (ACK) for each correctly received frame; it may also send a negative acknowledgement (NAK) to request retransmission of a specific frame.
• When a NAK for a particular frame is received, the sender retransmits only that frame without going back to resend subsequent frames.
• Selective Repeat requires more receiver buffering and more complex bookkeeping than Go-Back-N, but it saves bandwidth when the error rate is high because fewer frames are retransmitted.

An illustrative selective retransmission example is shown below.

Protocol Operation and Key Concepts

The following concepts are common to sliding window protocols and are important to understand their operation and limits.

• Sequence number space: Sequence numbers are usually taken modulo S, where S = 2^k if k bits are used for sequence numbers. Modulo arithmetic ensures circular numbering of frames.
• Window: A window describes the range of sequence numbers that the sender may transmit (sender window) or the receiver may accept (receiver window).
• ACK and cumulative acknowledgement: In Go-Back-N ACKs are cumulative; in Selective Repeat ACKs are individual and identify each correctly received frame.
• Timeout and retransmission: The sender starts a timer (often per earliest unacknowledged frame in GBN, or per-frame timers in SR) and retransmits when the timer expires.
• Buffering: Selective Repeat requires the receiver to buffer out-of-order frames until missing frames arrive. Go-Back-N discards out-of-order frames, keeping receiver buffer minimal.
• Pipelining: By allowing multiple outstanding frames, sliding window protocols pipeline transmissions and increase link utilisation and throughput compared with stop-and-wait.

Sequence-number Range and Window Constraints

Sequence-number size determines the maximum safe window sizes to avoid ambiguity between new frames and retransmissions. Let S denote the sequence-number space (S = 2^k for k-bit sequence numbers).

• For Go-Back-N, the maximum sender window size is S - 1. This prevents the sender from sending a new frame that could be confused with an old, unacknowledged one.
• For Selective Repeat, the sender and receiver window size must satisfy N ≤ S/2 (commonly N ≤ 2^(k-1)). This ensures that sequence numbers of outstanding frames and newly transmitted frames do not overlap and cause confusion at the receiver.

Worked Examples (Operational Walkthroughs)

Go-Back-N example (stepwise)

1. The sender has frames with sequence numbers 0,1,2,3,4 and a sender window of size 3 (may send frames 0,1,2 without waiting).
2. The sender transmits frames 0,1,2 in succession.
3. The receiver correctly receives 0 and sends cumulative ACK 0 (or ACK for next expected 1); it receives 1 and sends ACK 1. If frame 2 is lost, the receiver will not accept 3 when it arrives and will not advance its ACK beyond 1.
4. The sender's timer for frame 2 eventually expires; the sender retransmits frame 2 and all subsequent frames that were sent (if any). The sender "goes back" to retransmit outstanding frames starting at the lost one.
5. After receiver gets frame 2, normal cumulative ACKs resume and the sender moves its window forward.

Selective Repeat example (stepwise)

1. The sender and receiver have window size 4 and frames 0..7 as the sequence space (mod 8).
2. The sender transmits frames 0,1,2,3. Suppose frame 1 is corrupted in transit while 2 and 3 arrive correctly.
3. The receiver accepts 0, buffers 2 and 3 as they arrived out of order, and sends ACKs for 0, 2 and 3; it may also send a NAK for 1 to prompt immediate retransmission.
4. The sender retransmits only frame 1 (either upon receiving a NAK or when its timer for frame 1 expires).
5. When the receiver receives frame 1, it delivers the buffered frames 0,1,2,3 in order to the upper layer and discards buffer entries for those frames.

Comparison: Go-Back-N vs Selective Repeat

Key operational differences between the two protocols are:

• Retransmission policy: Go-Back-N retransmits the lost frame and all subsequent frames in the sender window; Selective Repeat retransmits only the damaged or lost frames.
• Receiver buffering: Go-Back-N requires minimal buffering because out-of-order frames are discarded; Selective Repeat requires buffering of out-of-order frames until missing frames arrive.
• Acknowledgements: Go-Back-N typically uses cumulative ACKs; Selective Repeat uses individual ACKs (and may use NAKs).
• Efficiency: Selective Repeat is more bandwidth-efficient when error rates are moderate to high because fewer frames are retransmitted; Go-Back-N is simpler but wastes bandwidth on retransmissions.
• Complexity: Go-Back-N is simpler to implement; Selective Repeat is more complex due to per-frame timers, buffering and bookkeeping.
• Window-size constraint: For correct operation, Go-Back-N's window must be ≤ S - 1; Selective Repeat's window must be ≤ S/2 (where S = 2^k).

Advantages and Disadvantages

• Advantages of sliding window techniques: higher link utilisation through pipelining, better throughput than stop-and-wait, ability to tolerate propagation delays.
• Disadvantages: increased complexity compared to stop-and-wait, need for timer management and buffering, potential for wasted bandwidth in simpler protocols like Go-Back-N when errors are frequent.

Applications and Practical Notes

• TCP (Transmission Control Protocol) uses a sliding-window mechanism for flow control and reliable delivery. TCP uses cumulative acknowledgements and also supports selective acknowledgement via the SACK option for efficiency on lossy links.
• Sliding-window protocols are used in data-link layer standards, wireless protocols, and other reliable transport schemes where ordered and reliable delivery is necessary.
• Choice between Go-Back-N and Selective Repeat depends on link error characteristics, implementation complexity, and available buffering.

Conclusion

The sliding window protocols-Go-Back-N and Selective Repeat-provide mechanisms for reliable, ordered, and efficient frame transmission by allowing multiple outstanding frames, using sequence numbers and acknowledgements, and managing retransmissions. Go-Back-N is simpler and uses cumulative ACKs with a receiver window of 1, while Selective Repeat is more efficient on noisy channels at the cost of receiver buffering and per-frame management. Understanding the sequence-number space and window-size constraints is essential for correct protocol design and implementation.