Sliding Window

From the sender's viewpoint, TCP communication presents a deceptively simple challenge: transmit a stream of bytes as quickly as possible while respecting two constraints—don't overflow the receiver's buffer, and don't overwhelm the network. The send window is the sender's tool for managing the first constraint.

The send window encapsulates everything the sender knows about what it's permitted to transmit. It tracks which bytes have been acknowledged, which are in flight, which are ready to send, and which must wait. It incorporates feedback from the receiver's window advertisements. And it interacts with congestion control to determine actual transmission behavior.

This page examines the send window mechanism in exhaustive detail. We'll explore the data structures that implement it, the algorithms that manage it, and the edge cases that challenge implementations.

TCP, as specified in RFC 793 and subsequent RFCs, defines specific state variables that the sender maintains. Understanding these variables is essential for understanding send window behavior.

The Send Sequence Space:

RFC 793 defines the send sequence space with these critical variables:

Relationships and invariants:

These variables maintain specific relationships that implementations must preserve:

ISS ≤ SND.UNA ≤ SND.NXT ≤ SND.UNA + SND.WND

• SND.UNA is always ≤ SND.NXT (you can't send data you haven't reached yet)
• SND.NXT is always ≤ SND.UNA + SND.WND (you can't send beyond the window)
• As acknowledgments arrive, SND.UNA advances toward SND.NXT
• As data is transmitted, SND.NXT advances toward the window's right edge

Derived quantities:

Several useful quantities derive from these variables:

The send window operates over the send buffer—a region of memory that holds data from the application until TCP has successfully delivered and acknowledged it. Understanding how the send buffer relates to the window is crucial.

Buffer organization:

The send buffer is logically organized into regions that correspond to the send sequence space:

Buffer size vs. window size:

The send buffer size and window size are related but distinct concepts:

• Send buffer size: The total memory allocated for outbound data. Configured by the application or OS. Determines how much data the application can write before write() blocks.

• Send window (SND.WND): The receiver's advertised capacity. Determines how much data TCP can have "in flight" at once.

The send buffer must be at least as large as the send window to allow the window to be fully utilized. If buffer_size < SND.WND, the sender may be artificially limited even when the receiver is willing to accept more.

Best practice:

Send Buffer Size ≥ Expected Maximum SND.WND + Headroom for application writes

Buffer operations:

The send buffer supports three categories of operations:

1. Application writes: Data enters the buffer from the application. If the buffer is full, the write blocks (or returns an error for non-blocking sockets). This adds to the "not yet sent" region.

2. TCP transmission: Data in the "not yet sent" region moves to "sent, unacknowledged" when TCP transmits it. The SND.NXT pointer advances.

3. ACK processing: When acknowledgments arrive, data moves from "sent, unacknowledged" to freed space. The buffer space is recycled for new application writes.

This creates a continuous flow: application in → TCP out → ACK frees → more application in.

Given the send window state, when does TCP actually transmit data? The decision is more nuanced than simply "send if usable window > 0."

The basic transmission condition:

Can transmit if: SND.NXT < SND.UNA + SND.WND
                 AND data exists at SND.NXT in send buffer
                 AND (cwnd constraint also satisfied, but that's congestion control)

Segment sizing:

Once TCP decides to transmit, it must determine how many bytes to send. The segment size considers:

The actual segment size is:

Segment Size = min(MSS, Usable Window, cwnd - bytes_in_flight, Available Data)

Nagle's algorithm interaction:

Nagle's algorithm (RFC 896) adds a timing constraint to improve efficiency:

• If there's unacknowledged data outstanding, hold small segments until:
  • An ACK arrives (freeing window and potentially coalescing data), OR
  • Enough data accumulates to fill a segment, OR
  • A timer expires

This prevents "silly window syndrome" from the sender side. We'll cover this in detail in a later module.

Push (PSH) flag considerations:

When the application calls a "push" operation or TCP reaches the end of currently available data, it sets the PSH flag. This tells the receiver to deliver buffered data to the application immediately rather than waiting.

PSH doesn't affect send window mechanics directly, but it influences when the receiver processes and potentially ACKs data, which indirectly affects window dynamics.

When an ACK arrives, the sender must update its window state. This process is more subtle than it appears.

Validating the ACK:

First, TCP validates that the ACK is acceptable:

Valid ACK if: SND.UNA < ACK ≤ SND.NXT

• ACK > SND.NXT is invalid (acknowledging data we never sent)
• ACK ≤ SND.UNA is a duplicate (acknowledging already-ACKed data)
• ACK in the valid range acknowledges new data

Updating SND.UNA:

For a valid, non-duplicate ACK:

SND.UNA = ACK_Number

This advances the left edge of the window. All bytes from the old SND.UNA to the new SND.UNA - 1 are now considered acknowledged and can be freed from the send buffer.

Updating SND.WND:

The ACK segment also carries a window field. However, TCP must be careful about accepting window updates because segments can arrive out of order. RFC 793 specifies:

Accept new SND.WND if:
  SEG.SEQ > SND.WL1  (segment has newer sequence number)
  OR (SEG.SEQ == SND.WL1 AND SEG.ACK > SND.WL2) (same seq but newer ACK)
  OR (SEG.SEQ == SND.WL1 AND SEG.ACK == SND.WL2 AND SEG.WND > SND.WND)

The SND.WL1 and SND.WL2 variables record the sequence and ACK numbers of the last segment that updated the window. This prevents an old, delayed segment from incorrectly shrinking the window.

Retransmission adds complexity to send window management. When TCP detects loss (via timeout or duplicate ACKs), it must retransmit data that's still in the "sent, unacknowledged" region.

Retransmission doesn't advance SND.NXT:

A critical point: retransmitting data does not advance SND.NXT. The retransmitted bytes occupy the range [SND.UNA, SND.NXT) that has already been sent. Retransmission is re-sending that same range, not sending new data.

Before sending:     SND.UNA = 1000, SND.NXT = 5000 (4000 bytes in flight)
After loss detected: SND.UNA = 1000, SND.NXT = 5000 (unchanged)
After retransmit:    SND.UNA = 1000, SND.NXT = 5000 (still unchanged)

Go-back-N vs. Selective Retransmission:

TCP implementations vary in how they handle retransmission:

SACK and the send window:

With SACK, the sender maintains a more sophisticated view of which bytes have been received:

• The receiver reports SACK blocks: ranges of bytes received out of order
• The sender marks these as "SACKed" (probably delivered)
• On retransmission, the sender only retransmits non-SACKed bytes
• Full cumulative ACK advances SND.UNA and clears SACK information

SACK doesn't change the fundamental window mechanics but dramatically improves retransmission efficiency.

A challenging situation arises when the receiver advertises a window of zero: SND.WND = 0. The sender cannot transmit any data. But how does the sender know when the receiver's buffer has freed up?

The zero window problem:

1. Receiver's buffer fills up → advertises window = 0
2. Sender stops transmitting
3. Receiver processes data, buffer frees up
4. Receiver sends ACK with window > 0
5. This ACK could be lost!
6. Sender waits forever for a window update that will never arrive
7. Receiver waits for data that will never come
8. Deadlock

This is a classic lost-ACK deadlock scenario. TCP solves it with the persist timer and window probes.

The persist timer:

When the sender receives a zero window, it starts a persist timer. When this timer expires, the sender transmits a window probe—a tiny segment (often just 1 byte) designed to elicit an ACK with the current window value.

Window probe characteristics:

• Contains 1 byte of data (the next byte at SND.NXT)
• Sent even though window is 0 (violation of normal rules)
• Forces receiver to respond with current window
• Uses exponential backoff to avoid flooding
• Will not give up (TCP doesn't abandon connections due to zero window)

The probe solves the deadlock:

1. If original window-update ACK was lost, the probe elicits a new one with window > 0
2. If receiver still has no space, probe ACK confirms window = 0, timer restarts
3. Connection eventually makes progress when receiver buffer frees

Implementing the send window correctly requires attention to several subtle issues that can cause bugs or performance problems.

Sequence number wraparound:

TCP sequence numbers are 32-bit unsigned integers. On a fast connection, they wrap around (from 2³²-1 back to 0). All sequence number comparisons must use modular arithmetic:

// WRONG: Simple comparison fails at wraparound
if (seq1 < seq2) { ... }

// RIGHT: Signed comparison handles wraparound
if ((int32_t)(seq1 - seq2) < 0) { ... }

This applies to all window calculations: SND.UNA, SND.NXT, window boundaries, etc.

Buffer management efficiency:

The send buffer is a critical data structure. Efficient implementations:

• Use circular buffers to avoid copying when space is freed
• Maintain per-segment metadata (sequence number, transmit time, retransmit count)
• Support scatter-gather I/O to avoid copying from application buffers
• Pre-allocate space when possible to avoid allocation during transmission

Interaction with the network stack:

The send window is one component of a larger system. It must coordinate with:

• Congestion control: Provides cwnd, which may further limit transmission
• Path MTU discovery: Sets MSS, affecting segment sizes
• Delayed ACKs: Affects when window updates arrive
• Nagle's algorithm: Affects when small segments are sent

We've explored the send window in depth—the sender's mechanism for managing what data it can transmit. Let's consolidate the key concepts:

What's next:

We've examined the sender's perspective. Next, we'll explore the receive window—the receiver's side of the sliding window mechanism. We'll see how the receiver advertises its capacity, manages its buffer, and generates the window values that govern sender behavior.