Protocols use sequence numbers to maintain message order. The transmitter typically increments them either once per message or by the length of the message. The receiver uses them to reorder messages and detect gaps due to inferred loss.
Sequence numbers are represented within those messages (e.g., in the headers) as values of a finite, unsigned number space. This space is typically represented in a fixed-length bit string, whose values range from 0..(2N
The use of finite representations has repercussions on the use of these values at both the transmitter and receiver. Without additional constraints, when the number space "wraps around", it would be impossible for the receiver to distinguish between the uses of the same value.
As a consequence, additional constraints are required. Transmitters are typically required to limit reuse until they can assume that receivers would successfully differentiate the two uses of the same value. The receiver always interprets values it sees based on the assumption that successive values never differ by just under half the number space. A receiver cannot detect an error in that sequence, but it will incorrectly interpret numbers if reordering violates this constraint.
The constraint requires that "forward" values advance the values by less than half the sequence number space, ensuring that receivers never experience a series of values that violate that rule.
We define a sequence space as follows:
An unsigned integer within the range of 0..(2N)-1, i.e., for N bits.
An operation that increments values in that space by K, where K < 2(N-1), i.e., less than half the range. This operation is used exclusively by the transmitter.
An operation that compares two values in that space to determine their order, e.g., where X < Y implies that X comes before Y.
We assume that both sides begin with the same initial value, which can be anywhere in the space. That value is either assumed (e.g., 0) before the protocol begins or coordinated before other messages are exchanged (as with TCP Initial Sequence Numbers (ISNs) [RFC 0793
]). It is assumed that the receiver always receives values that are always within (2N
)-1, but the successive received values never jump forward or backward by more than 2(N-1)
-1, i.e., just under half the range.
No other operations are supported. The transmitter is not permitted to "backup", such that values are always used in "increment" order. The receiver cannot experience loss or gaps larger than 2(N-1)
-1, which is typically enforced either by assumption or by explicit endpoint coordination.
An SNE is a separate number space that can be combined with the sequence number to create a larger number space that need not wrap around during a connection.
On the transmit side, SNE is trivially accomplished by incrementing a local counter once each time the sequence number increment "wraps" around or by keeping a larger local sequence number whose least-significant part is the message sequence number and most-significant part can be considered the SNE. The transmitter typically does not need to maintain an SNE except when used in local computations, such as for Message Authentication Codes (MACs) in TCP-AO [RFC 5925
The goal of this document is to demonstrate that SNE can be accomplished on the receiver side without transmitting additional information in messages. It defines the stateful function compute_sne() as follows:
SNE = compute_sne(seqno)
The compute_sne() function accepts the sequence number seen in a received message and computes the corresponding SNE. The function includes persistent local state that tracks the largest currently received SNE and seqno combination. The concatenation of SNE and seqno emulates the equivalent larger sequence number space that can avoid wrap around.
Note that the function defined here is capable of receiving any series of seqno values and computing their correct corresponding SNE, as long as the series never "jumps" more than half the number space "backward" from the largest value seen "forward".