Back to the blog

# An Algorithm for Computing RTP Sequence Number Ranges

September 29th, 2021

RTP packets have a sequence number associated with each packet to indicate the order in which the packets should be arranged. When they are sent over the network, they can often come out-of-order despite being sent in the correct order. On the receiver, some feedback mechanisms require sending information back to the sender to indicate which packets have been received. This requires computing the "range" of the sequence number seen over a time window.

Unfortunately, this algorithm is not trivial because the sequence number is only 16-bits of information, therefore it will often wrap around. For example, it is easy to see that if the sequence numbers received are `[10, 11, 12, 14]`, the range is `[10, 14]`, however when the sequence numbers are `[65534, 65535, 0, 1, 2]`, it is a little less trivial to find the correct range `[65534, 2]`, especially when the packets arrive out of order.

In other words, we seek an algorithm that is able to compute the range of a bounded set of numbers in quotient space.

## Outline

To approach this problem, we observe two facts

1. The sequence number range is bounded, typically as a constrant of the feedback mechanism. Feedback mechanisms typically do not permit sequence number ranges to exceed, eg 16384, in length. Define this bound as `B`.
2. Given a bound `B`, we wish to find the first sequence number `seq_0` such that `seq_i < seq_0 + B` for all sequence numbers. Note that addition here is under modulo arithmetic.

Given the second observation, let us define `delta_i = seq_i - seq_0` under non-modular arithmetic. That is, `delta_i` can be negative.

Our algorithm observes that the start of the range is `seq_0 + min(delta_i)` and the end of the range is `seq_0 + max(delta_i)` with this addition performed in modular arithmetic.

## Implementation

The implementation given the above outline is fairly straightforward. The main trick is in the conversion into a larger unsigned integer space. The algorithm is implemented in Go as follows:

``` minDelta := 0 maxDelta := 0 seq0 := seqs for _, seq := range seqs { delta := int(seq-seq0) if seq-seq0 >= B { delta -= (1<<16) if delta < minDelta { minDelta = delta } } else { if delta > maxDelta { maxDelta = delta } } } return seq0 + uint16(minDelta), seq0 + uint16(maxDelta) ```

If unfamiliar, `int32()` converts a `uint16` into a signed at-least-32-bits integer.

## Rationale

Observe that `seq_i = (seq_0 + delta_i) % (2^16)`. We also know that `min(delta_i) <= delta_i <= max(delta_i)`. Therefore it must be true that `seq_i` falls within the range `[seq_0 - min(delta_i), seq_0 + max(delta_i)]`.

Interestingly, the choice of `seq_0` here is largely arbitrary. However, it is important that the choice of pivot lies within the sequence range for this algorithm to work. Therefore, an arbitrary sequence number is a natural choice.

This algorithm is used at Muxable to implement sender-side congestion control over RTP flows. Check out the source code to learn more.

Comment on this post on Twitter