Introduction: Overcoming the "Wait" in Stop-and-Wait

In our discussion of flow control, we explored the Stop-and-Wait protocol. It is perfectly reliable: the sender sends a single frame and waits for an acknowledgment before sending the next. This simple rule completely prevents the sender from overwhelming the receiver. However, its efficiency is abysmal, especially on long-distance links with high Round-Trip Time (RTT). The communication channel spends most of its time idle while the sender is waiting for an ACK to travel back. It's like having a conversation where you must wait for a "yes, I understood" after every single sentence, polite, but painfully slow.

The obvious solution to this inefficiency is pipelining: allowing the sender to transmit multiple frames before being required to stop and wait for an acknowledgment. This allows the communication channel, or the "pipe," to be filled with data, dramatically increasing its utilization and throughput. The family of protocols that implement this pipelining strategy is known as Sliding Window Protocols. They are the cornerstone of reliable, high-performance data transfer in modern networks, used by protocols like TCP and HDLC.

Core Mechanics of a Sliding Window

All sliding window protocols share a common set of fundamental concepts that enable them to manage multiple "in-flight" frames simultaneously.

1. Sequence Numbers

If multiple frames can be in the network at the same time, we need a way to uniquely identify each one. This is achieved by adding a sequence number to the header of each frame. These numbers are used to:

• Identify which frames have been lost or corrupted during transmission.
• Acknowledge the receipt of specific frames.
• Reorder frames that may arrive at the destination out of sequence.
• Detect and discard duplicate frames.

The sequence number field has a finite number of bits, $k$, meaning the numbers range from 0 to $2^k - 1$ and then wrap around (e.g., for $k=3$, the sequence is 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, ...). This modular arithmetic is sufficient as long as the number of frames in flight is smaller than the total number of available sequence numbers.

The Sender's Perspective: The Transmit Window

The sender maintains a range of sequence numbers known as its send window. This window represents the set of frames that it is permitted to send. The size of this window, often denoted by $W_S$, is a critical parameter.

The sequence number space from the sender's perspective is divided into four regions:

1. Frames Sent and Acknowledged: These frames have completed their journey successfully. They are behind the window.
2. Frames Sent but Not Yet Acknowledged: These are the "in-flight" frames currently transiting the network. They occupy the sender's window. The sender must buffer these frames in its memory in case they need to be retransmitted.
3. Usable Frames Not Yet Sent: These frames have sequence numbers that fall within the allowed window but haven't been transmitted yet. The sender can send these as soon as it's ready.
4. Frames Beyond the Window: These frames cannot be sent until the window "slides" forward.

The "sliding" action occurs when the sender receives an acknowledgment for the oldest unacknowledged frame (the one at the low end of the window). This confirmation allows the sender to move the lower boundary of its window forward, thus bringing new "usable" sequence numbers into the window and allowing more frames to be transmitted.

The Receiver's Perspective: The Receive Window

The receiver also maintains a receive window of size $W_R$. This window defines the range of sequence numbers for frames that it is currently prepared to accept.

Any frame that arrives with a sequence number outside of the receiver's window is discarded. For frames arriving with a sequence number inside the window, the receiver's behavior depends on the specific sliding window protocol being used. When the receiver accepts a frame at the lower boundary of its window, it passes the data up to the network layer and "slides" its window forward to the next expected sequence number.

Sliding Window Variant 1: Go-Back-N (GBN)

Go-Back-N is the simpler, but more punitive, of the two main sliding window protocols. It's built on a principle that demands perfect order from the receiver.

Core Principle: The receiver has a window size ($W_R$) of exactly 1. This means it is only looking for one specific frame at a time: the next one in the sequence. It has no mechanism for buffering frames that arrive out of order.

The GBN Process and Error Recovery

• Sender Behavior: The sender can transmit up to $N$ frames (its window size) without waiting for an acknowledgment.
• Receiver Behavior: The receiver expects frame with sequence number 'k'. If frame 'k' arrives correctly, it is accepted, and the receiver sends back a cumulative acknowledgment for 'k'. It then updates its expectation to frame 'k+1'.
• Error Handling (The "Go Back" Part): If frame 'k' is lost, or if any frame other than 'k' arrives (e.g., 'k+1', 'k+2'), the receiver takes a harsh action: it discards the incorrect frame and resends the acknowledgment for the last frame it received correctly ('k-1').
• Retransmission: The sender has a timer for each unacknowledged frame. Eventually, its timer for the lost frame 'k' will expire. At this point, the sender "goes back" to sequence number 'k' and retransmits frame 'k' and every subsequent frame it had already sent (i.e., 'k+1', 'k+2', etc.). This happens even if frames 'k+1' and 'k+2' were originally received correctly, the receiver had already discarded them because they arrived out of order.

GBN: Advantages and Disadvantages

Advantages: The receiver logic is extremely simple, as it doesn't need to manage complex buffers for out-of-order frames. It only needs to store one variable: the sequence number of the next expected frame.

Disadvantages: It is highly inefficient, especially on links with long delays and high error rates. A single lost frame can cause a large number of subsequent, perfectly good frames to be retransmitted, wasting significant bandwidth.

Sliding Window Variant 2: Selective Repeat (SR)

Selective Repeat (also known as Selective Reject) is the more intelligent and efficient, but also more complex, sliding window protocol. It was designed to fix the bandwidth-wasting behavior of Go-Back-N.

Core Principle: The receiver has a window size ($W_R$) that is greater than 1 (often equal to the sender's window size, $W_S$). It can accept and buffer correctly received frames, even if they arrive out of order.

The SR Process and Error Recovery

• Sender Behavior: Same as GBN, the sender can transmit up to $N$ frames without waiting for an acknowledgment.
• Receiver Behavior: The receiver maintains a buffer for its entire window. When a frame with sequence number 'k' arrives error-free and 'k' is within its receive window, it accepts it, stores it in its buffer, and sends back a selective acknowledgment for frame 'k'.
• Error Handling (The "Selective" Part): If the sender's timer for a specific frame (e.g., frame 'k') expires, it knows that only that particular frame was lost (because it may have received SACKs for later frames like 'k+1' and 'k+2').
• Retransmission: The sender retransmits only the single frame that was lost (frame 'k'). When the receiver receives the retransmitted frame 'k', it fills the gap in its buffer. If it now has a contiguous block of frames starting from the beginning of its window, it can deliver this block to the network layer and slide its window forward.

SR: Advantages, Disadvantages, and a Key Constraint

Advantages: Dramatically more efficient than GBN, especially on high-latency, high-error-rate links ("long fat networks"). It minimizes unnecessary retransmissions, leading to much higher throughput.

Disadvantages: Requires much more complex logic on both sides. The sender needs to manage timers and acknowledgment status for each individual frame. The receiver needs a more complex buffering system to manage out-of-order frames and reassemble the data stream correctly.

Window Size Constraint: To avoid ambiguity between old and new windows after the sequence numbers wrap around, the sum of the sender and receiver window sizes must be no larger than the total number of available sequence numbers ($W_S + W_R \le 2^k$). A common, safe implementation is to set the window sizes for both sender and receiver to be half the sequence number space: $W_S = W_R = 2^{k-1}$.