Sequence Numbers and the Sliding Window Arithmetic

A reliable byte stream needs to know which bytes arrived. The obvious representation is a set: record every received range, merge overlapping ranges, ask whether a range is covered. That works, and some protocols do it, but it costs memory proportional to the number of disjoint ranges and it makes the common case, a contiguous prefix, no cheaper than the pathological one.

TCP’s answer is to number every byte and let one integer summarise everything the receiver has accepted. The summary is exact only for the prefix, which turns out to be enough, because the sender only ever needs to know how far it may advance.

One counter per byte, not per packet

The sequence number field is 32 bits and counts bytes, not segments. A segment carrying 1,000 bytes of payload consumes 1,000 values of the sequence space. The SYN and FIN flags each consume one value even though they carry no payload, so that their acknowledgement is unambiguous. Pure ACKs consume nothing.

Counting bytes rather than packets is what makes the receiver’s state a single integer. If segments were numbered, a receiver holding bytes 1 through 4,096 would need to know which segments those bytes came from before it could say anything about what is missing. With byte numbering, the receiver publishes RCV.NXT, the next byte it expects, and every byte below that value is known to be in hand.

The sequence space is finite and wraps: after 2³²−1 the counter returns to 0. That is 4 GiB of sequence space, which at the time of the original specification was far more than any plausible window, and the wrap is why every comparison in the protocol is modular rather than ordinary integer comparison.

The five variables that describe a connection

RFC 9293’s connection record lists seven send-side and four receive-side sequence variables. Three on the send side and two on the receive side move as data flows; the remainder are fixed at handshake time, track urgent data, or exist only to police window updates. The sender tracks:

• SND.UNA, the oldest unacknowledged sequence number, which is the left edge of the send window.
• SND.NXT, the next sequence number to send, which is the right edge of what has been transmitted.
• SND.WND, the size of the window advertised by the receiver.

The receiver tracks:

• RCV.NXT, the next byte it expects, which is also the value it puts in the acknowledgement field.
• RCV.WND, the space it currently has available.

Everything else is derived. The bytes in flight are the half-open interval [SND.UNA, SND.NXT), whose length is SND.NXT − SND.UNA. The number of bytes the sender is still permitted to transmit is

usable = SND.WND - (SND.NXT - SND.UNA)

and this expression is the entire flow control mechanism. It is evaluated on every incoming acknowledgement, and it is the reason the protocol needs no message to say “stop”: a window of zero makes the usable value non-positive, and the sender simply has nothing legal to send.

A receiver that shrinks its advertised window below the data already in flight creates a contradiction: bytes that have been sent are now outside the window. RFC 9293 says a receiver SHOULD NOT shrink the window — never moving its right edge leftward — while requiring the sender to tolerate a peer that does. A receiver that wants to reduce buffering must stop advertising growth and wait for the sender to drain, not retract the window.

Modular comparison, and why half the space

The wrap makes SND.UNA ≤ SND.NXT false at the moment the counter rolls over, so the protocol defines a serial-number comparison: a precedes b if (b − a) mod 2³² is less than 2³¹. This is the standard technique for ordering values from a counter with finite width, and its correctness condition is a bound on how far apart the two values can be. If two live sequence numbers differ by more than 2³¹, the comparison returns the wrong answer, and the protocol has no way to detect it. That bound is what fixes the maximum window: the scaling extension in RFC 7323 allows a shift of at most 14, so the largest window it can express is 65,535 × 2¹⁴ bytes, which is just under 2³⁰. The window can therefore never reach half the sequence space, and the comparison stays unambiguous.

In C the comparison is a single subtraction and a sign test, relying on unsigned wraparound:

/* Serial-number comparison: returns -1, 0, or 1 as a precedes, equals, or follows b. */
int seq_cmp(uint32_t a, uint32_t b) {
    int32_t d = (int32_t)(a - b);   /* unsigned subtract, reinterpret as signed */
    return (d > 0) - (d < 0);
}

int seq_between(uint32_t x, uint32_t lo, uint32_t hi) {
    /* true when x lies in the half-open interval [lo, hi) modulo 2^32 */
    return seq_cmp(lo, x) <= 0 && seq_cmp(x, hi) < 0;
}

Reinterpreting the difference as signed is not portable in the strictest sense: conversion of an out-of-range unsigned value to signed is implementation-defined in C. Every compiler targeting two’s complement hardware produces the intended result, and this is the conventional idiom; a strictly portable version tests the difference against 0x80000000u instead.

The initial sequence number is chosen from a different kind of counter for a different reason. RFC 9293 requires the ISN to come from a 32-bit clock that typically increments at least once every four microseconds and cycles in roughly 4.55 hours, far longer than any maximum segment lifetime. The requirement is not about cryptography. It ensures that two connections over the same address pair do not share sequence numbers within one segment lifetime, so a segment from a closed connection cannot be mistaken for part of a new one. RFC 9293 also recommends adding a keyed pseudorandom function of the four-tuple, so that an off-path attacker cannot predict the value from the clock alone.

What a cumulative acknowledgement can and cannot say

The acknowledgement field carries RCV.NXT, which means “every byte below this number has arrived.” That single statement is cheap and unambiguous, and it is also lossy: when a segment is lost in the middle of a window, the receiver keeps acknowledging the same value, and the sender learns only that something below SND.NXT is missing. It cannot tell which of the outstanding segments was lost, how many were lost, or whether they arrived out of order.

Three mechanisms exist to recover that information, and each is treated separately in this cluster. Selective acknowledgement, described in SACK Blocks and the Retransmission Queue, reports individual received ranges so the sender can retransmit only the holes. The retransmission timer, described in Retransmission Timeout Estimation and Karn’s Algorithm, covers the case where no acknowledgement arrives at all. The receive window, described in Advertised Windows and Zero-Window Probing, handles the case where the acknowledgement arrives but the receiver has no room for more data.

All three build on the same underlying bookkeeping. The sender keeps a queue of transmitted ranges indexed by sequence number, and the acknowledgement either advances the left edge of that queue or, with SACK, marks an interior range as delivered.

Receiver buffering and the cost of a large window

A window is a promise about buffer space. Advertising w bytes commits the receiver to holding w bytes beyond RCV.NXT if the sender fills the window. That commitment is why the receive window is not simply made as large as possible: it is memory that must be allocated per connection, and the number of connections is not bounded by anything the receiver controls.

The classic trade-off is between window size and throughput. A sender cannot have more than one window of data outstanding, so the achievable rate is roughly window / round-trip time. On a path with a 100 ms round trip, a 64 KiB window permits about 5.2 Mbit/s no matter how fast the links are. RFC 7323’s window scaling option exists to lift the 65,535-byte field limit; it carries a shift count of up to 14, so the largest representable window is 65,535 × 2¹⁴ bytes, just under 1 GiB.

Large windows have a second cost that is easy to miss. The sequence space is 4 GiB, so a window of 1 GiB still leaves room for the modular comparison to work, but the sender’s retransmission queue now holds up to 1 GiB of data that must be retained until acknowledged. That memory is on the sender, and it is the reason a server accepting many connections must bound the window per connection rather than letting the client’s advertised scaling drive it upward.

Where the arithmetic meets the application

The window is evaluated per connection, and the sender’s buffer is a separate constraint. A socket write that fills the send buffer blocks the writing thread or returns a short count, because the kernel will not copy more bytes than it can queue, and the queue is bounded by SND.WND and by the socket’s own buffer limit, whichever is smaller. This is why an application writing to a socket with a zero-window peer eventually stops: the send buffer fills, the write blocks, and the block is released only when an acknowledgement opens the window. The mechanisms that keep that stall from becoming permanent, and the ones that keep a stalled sender from wasting the path, are the subject of the rest of the cluster.