Raptor/RaptorQ FEC scheme

[gavv]

Intro

It would be interesting to try Raptor/RaptorQ FEC codes. It is claimed that they perform better than Reed-Solomon.

Our docs:

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

RFCs:

• RFC 6681
• RFC 6682

Known Raptor/RaptorQ implementations:

• libRaptorQ (C++)
• orq (C++)
• OpenRQ (Java)
• raptorq (Rust)

Implementation

We should try libRaptorQ.

The plan is:

• Add target_libraptorq to roc_fec.

• Add libRaptorQ dependency to build system (add --enable-libraptorq to SConstruct which enables libRaptorQ dependency and enables target_libraptorq; add libraptorq to 3rdparty.py; see #246 for details on adding a new dependency).

• Add fec::RaptorEncoder and fec::RaptorDecoder, implementing fec::IBlockEncoder and fec::IBlockDecoder using libRaptorQ (they should be placed into target_libraptorq).

• Add raptor fec scheme to packet::FECScheme.

• Register RaptorEncoder and RaptorDecoder in fec::CodecMap.

• Currently both fec::Reader and fec::Writer expect that source and repair packets will have FECFRAME header (packet::FEC). This is true for Reed-Solomon and LDPC FEC-schemes, but not for Raptor scheme; Raptor uses bare RTP packets for both source and repair packets. We should improve fec::Reader and fec::Writer so that they will support two modes:

  • Source packets have RTP and FECFRAME headers. Repair packets have only FECFRAME header. Block number and number in block are deduced from FECFRAME headers. This is how it works currently.

  • Source and repair packets both have RTP header and don't have FECFRAME header. Block number and number in block are deduced from RTP headers. This is what we need for raptor.

  What mode to use should be defined by the FEC scheme. We should also add unit tests for the new mode.

• Allow to enable Raptor via command-line tools and C API. It should be enabled by using corresponding FEC scheme. Since it does not introduce its own headers, no new protocols should be added. RTP should be used for both source and repair packets.

• Enable Raptor scheme in roc_fec, roc_pipeline, and roc_lib tests (if it's enabled at compile-time).

Steps

This could be split into three pull requests:

1. Add libRaptorQ dependency. Add raptor encoder and decoder. Enable them in codec-level roc_fec tests.

2. Add support for bare-RTP source & repair packets in fec::Reader and fec::Writer (without FECFRAME header). Add corresponding unit tests.

3. Register raptor FEC scheme. Add it to command-line tools and C API. Add it to reader-writer-level roc_fec tests and roc_pipeline & roc_lib tests.

[drdpov]

Hi @gavv. Is this issue still open? Can I work with it? What should i start with?

[gavv]

Hi! Yes, this is still relevant and you're welcome.

I'd recommend to start from reading this page from our documentation and then RFC 6363, RFC 6681, and RFC 6682.

Then I suggest to look at OpenRQ and orq. IIRC, OpenRQ is quite complete, but it's written in Java. I don't know whether orq is complete. So you'll need to do some research. If we can just use orq, it would be great! If it's far from complete, we'll have either to send patches or to grow our own implementation, likely using OpenRQ and orq as a reference.

We already have generic FECFRAME code and tests. We support two FEC schemes (LDPC and Reed-Solomon). In command-line tools FEC scheme is auto-detected from port protocols (e.g. rs8m protocol corresponds to Reed-Solomon scheme). See manual pages for info on how to try different schemes. You can play with them and see how they behave on different block sizes and packet loss ratios. This post may be helpful.

In this task we should add raptor-specific payload format and encoder/decoder. ~For payload format, look at the roc_fec/headers.h, used in fec::Parser and fec::Composer.~ For codecs, look at fec::OFEncoder and fec::OFDecoder (LDPC and Reed-Solomon encoder & decoder implemented using OpenFEC). Then we should integrate the new scheme into pipeline and add corresponding FEC scheme. Finally, it would be interesting to compare Raptor with existing schemes in terms of latency and service quality.

[gavv]

Oh, and there are also:

• https://github.com/LucaFulchir/libRaptorQ
• https://github.com/cberner/raptorq

[gavv]

I've took a look at those libraries and I think libRaptorQ looks very promising and we should try it first (its C++98 or C API).

I've also updated the issue and added a more detailed plan. And I've removed the part about fec::Parser/fec::Composer - we actually don't need a new parser & composer for Raptor because it doesn't introduce new headers, only a new RTP payload.

@ffisherr What do you think? Are you working on this / have plans to work on this?

[drdpov]

Hey @gavv, agree with you, example in libRaptorQ seems very easy, i believe, i can do the first pull request in couple days.

[gavv]

Great!

[drdpov]

Hey, i have some troubles while adding libRaptorQ to SConstruct file. Here it is: /usr/local/include/RaptorQ/v1/caches.hpp:24:10: fatal error: vector: No such file or directory

include

How can i solve that? I saw in coding guidelines: "We don’t use STL (the algorithms-and-containers part of the C++ standard library)." Anyway, it is used in libraptoq.

[gavv]

We don't use STL, but we don't disable it in any way. So the error is unrelated. It's OK if libraptorq uses STL, we just wont be able to enable raptor on some restricted platforms.

[gavv]

You can push your changes to a branch on your fork and I'll take a look at it.

[drdpov]

Done.

[gavv]

Have you tried to remove extern "C" when including libraptorq headers?

[drdpov]

In "rq_encoder.h" #include <RaptorQ/RaptorQ_v1.hpp>? Yes, still doesn't work..

[gavv]

Well, I can't reproduce the error with <vector>, probably we have different compiler versions. But I got lots of other errors on your branch:

• compiler is complaining on extern C; it should not be used for C++ headers;
• roc is built with -std=c++98, and the included headers require at least C++11, which causes a lot of compilation errors.

One option would be to modify our build system to use c++11/c++17 for raptor codecs, but I'd like to avoid mixing different C++ standards for different translation units, it can lead to various linking problems.

Can we just use libraptorq pure C API instead?

BTW, for extensive discussions/debugging/etc I recommend to use our mailing list.

[gavv]

@ffisherr Do you still have plans on this?

[gavv]

Unassigning this so that someone else could pick it up. @ffisherr feel free to ping me if you decide to come back.

If somebody will pick this up, please take a look at these discussion at the mailing list:

https://www.freelists.org/post/roc/libRaptorQ https://www.freelists.org/post/roc/roc-Re-libRaptorQ

[gavv]

The task is old but still relevant. We should check what is current status of libRaptorQ.