Refine packet interleaving scheme

[gavv]

Last revised: Oct 2023

Problem

In sender pipeline, we have packet::Interleaver which can shuffle packets inside one FEC block. The idea is that this increases chances of successful packet recovery if some of the packets are lost.

However, quick tests showed that enabling interleaver does not help and sometimes even harms. I didn't look at it in great detail though.

Probably the problem is with the current shuffling algorithm. Or maybe the problem is that the interleaver has some additional latency that is not taken into account on the receiver.

Thus, this requires some research and testing. Here are some questions we need to answer:

• What shuffling algorithm to use? Currently we shuffle all packets inside a block. Probably we should shuffle only repair packets. Probably we should shuffle packets across block boundaries.

• Does the best shuffling algorithm depend on the FEC scheme? Do all FEC schemes need shuffling?

• Are packet bursts harmful? Currently source packets are sent according to their timestamps one by one, but repair packets are sent all at once when they are generated at the end of a block. Probably we should insert some delays, or shuffle repair packets from the previous block with the source packets from the next block.

• What is the latency introduced by interleaver and how should it be taken into account? Probably we need to increase the target queue size on the receiver if interleaver if enabled on sender.

Here is what RFC 6816 (LDPC FEC Scheme) says about packet ordering:

The way the FEC repair packets are transmitted is of high importance.
A good strategy, that works well for any kind of channel loss model,
consists in sending FEC repair packets in random order (rather than
in sequence) while FEC source packets are sent first and in sequence.
Sending all packets in a random order is another possibility, but it
requires that all repair symbols for a source block be produced
first, which adds some extra delay at a sender.

Solution

Do some tests and answer the questions above. Decide what interleaving algorithm we need and adjust packet::Interleaver accordingly. If makes sense, we also can support several interleaving schemes.

Info

About FEC:
https://roc-streaming.org/toolkit/docs/internals/fec.html