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.
To approach this problem, we observe two facts
B
.
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.
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.
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