An Algorithm for Computing RTP Sequence Number Ranges

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[0]
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