Sliding Window Protocols

Introduction: The limits of Stop-and-Wait

The Stop-and-Wait protocol sends one frame and waits for an acknowledgment before sending the next. Combined with an integrity check, a timer, and retransmission, it can provide reliable delivery while limiting the number of outstanding frames. Its efficiency falls on links with long propagation delay and high Round-Trip Time (RTT). The communication channel then remains idle for most of the cycle because the sender is waiting for the acknowledgment to return.

A way to reduce this waiting is pipelining: the sender transmits multiple frames before acknowledgments arrive. Data can then occupy the link while earlier frames are propagating, increasing link utilization. The window is chosen with the bandwidth-delay product and buffer capacity in mind. If it is too small, the sender still waits; if it is too large, buffering and sequence-number ambiguity become harder to control. Protocols that implement this rule are known as sliding window protocols. The mechanism appears, with protocol-specific acknowledgment and retransmission rules, in protocols such as TCP and HDLC.

Core mechanics of a sliding window

Typical sliding window protocols use sequence numbers, send and receive windows, and acknowledgments. Together, these elements manage multiple frames that are in transit at the same time. An acknowledgment can be cumulative and confirm a contiguous prefix, or selective and identify individual frames. The choice affects buffering and retransmission. TCP numbers octets rather than frames, while link protocols often number frames. The window mechanism is similar.

1. Sequence Numbers

If multiple frames can be in the network at the same time, the protocol must distinguish them within a connection. It does so by adding a sequence number to each frame header. These numbers are used to:

• Indicate missing frames when a gap appears in the sequence. Integrity checks detect corruption.
• Associate an acknowledgment with a particular frame or range of frames.
• Reorder frames when the protocol buffers frames that arrive out of sequence.
• Detect and discard duplicate frames.

The sequence number field has a finite number of bits, $k$, so values range from 0 to $2^k - 1$ and then wrap around (for example, with $k=3$ the sequence is 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, ...). Modular arithmetic requires a bounded window so that old and new frames cannot be confused after the sequence space wraps. The exact bound depends on the variant because Go-Back-N and Selective Repeat treat out-of-order frames differently. Implementations also need an unambiguous rule for comparing wrapped sequence numbers. A numerical comparison without that rule is insufficient.

The Sender's Perspective: The Transmit Window

The sender maintains a range of sequence numbers known as its send window. The window identifies frames it may send without waiting for earlier acknowledgments. Its size, often denoted by $W_S$, affects how many frames can be in transit at once.

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 window slides when the sender receives an acknowledgment that covers the oldest unacknowledged frame at its lower edge. A cumulative acknowledgment may cover several consecutive frames, so the lower edge then moves by the corresponding number of positions and new sequence numbers become usable. The acknowledgment also releases sender buffers that held copies for possible retransmission.

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. Its size limits how much out-of-order data can be retained and can therefore be tied to available receive-buffer space.

The response to a frame whose sequence number is outside the receive window depends on the protocol: it may be discarded or treated as a duplicate. For a frame whose number is insidethe window, the receiver follows the selected variant's rules. Once a frame completes the contiguous block at the lower edge, the receiver delivers available data to the network layer and slides the window to the next expected number. In Selective Repeat, frames after a gap remain buffered until the missing frame arrives.

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

Go-Back-N is a simpler sliding window variant. The receiver requires sequence order and does not buffer frames that arrive after a gap. It can acknowledge the next expected sequence value, which lets one acknowledgment confirm a contiguous prefix of the stream.

Core principle: In the usual Go-Back-N model, the receive window ($W_R$) has a size of exactly 1. The receiver expects one specific frame, the next in sequence, and does not buffer 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 'k'. If it arrives correctly, the receiver accepts it and sends a cumulative acknowledgment. It then expects frame 'k+1'.
• Error handling: If frame 'k' is lost or another frame arrives, such as 'k+1', the receiver discards the out-of-order frameand resends the acknowledgment identifying 'k' as the next expected frame.
• Retransmission: The sender tracks the oldest unacknowledged frame or uses an equivalent timer. When the timer for 'k' expires, it retransmits frame 'k' and every later frame it had already sent, such as 'k+1' and 'k+2'. This also happens when later frames arrived correctly, because the receiver discarded them as out of order.

GBN: Advantages and Disadvantages

Advantages: The receiver logic is simple because it does not manage a buffer for out-of-order frames. It only needs the sequence number of the next expected frame.

Disadvantages: The protocol loses efficiency on links with high delay or error rates. One lost frame can force many later frames to be retransmitted, reducing bandwidth utilization. With a small window, the sender may also leave the link idle while waiting for an ACK.

Sliding Window Variant 2: Selective Repeat (SR)

Selective Repeat (also known as Selective Reject) limits retransmissions compared with Go-Back-N but requires more state. The receiver can store frames that arrive out of order. It must retain enough information to identify each accepted frame and to prevent a wrapped sequence value from being mistaken for an older copy.

Core principle: In Selective Repeat, the receive window ($W_R$) is greater than 1 and is often equal to the sender's window ($W_S$). The receiver can accept and buffer correctly received frames even when 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 window. When frame 'k' arrives without errors and lies within the receive window, it accepts and stores it, then sends a selective acknowledgmentfor 'k'.
• Error handling:If the timer for a particular frame, such as 'k', expires, the sender can retransmit only that frame. Acknowledgments for later frames, such as 'k+1' and 'k+2', may show that they arrived correctly.
• Retransmission: The sender retransmits only the missing frame, such as frame 'k'. When the receiver gets it, it fills the gap in its buffer. If a contiguous block now starts at the beginning of the window, the receiver delivers it to the network layer and slides the window.

SR: Advantages, disadvantages, and window constraint

Advantages: It usually uses a link more efficiently than GBN, especially with high delay or an elevated error rate. Retransmissions are limited to frames that are actually missing, at the cost of receiver buffering.

Disadvantages: It requires more complex logic on both sides. The sender tracks timers and acknowledgment status for individual frames, while the receiver buffers out-of-order frames and reassembles the data stream.

Window size constraint: In the classic Selective Repeat model, the sum of the sender and receiver windows must not exceed the number of available sequence numbers so that old and new frames remain distinguishable after wraparound ($W_S + W_R \le 2^k$). When both windows are equal, a common choice is half the sequence space: $W_S = W_R = 2^{k-1}$.