Milestone: 39 - FEC

Add Forward Error Correction (FEC) to Librecast.

Why FEC?

IP Multicast is based on UDP, which is inherently unreliable. Packets may arrive out of order, or not at all. TCP provides unicast with a reliable messaging layer on top of this unreliable, connectionless medium.

Unicast, however, is one-to-one only. Multicast could, in theory, use all of the same reliability options (ACKs etc.) as TCP, at the cost of not being scalable any more.

Fortunately there are other ways to achieve similar reliability. RFC3208 describes Pragmatic General Multicast (PGM) based on NAKs (negative acknowledgements). This, too, has scaling issues.

Forward Error Correction (FEC) offers us another approach.

What is FEC?

Thanks to parity checking in the network stack, we don't generally need to worry about errors within packets. Every packet has a checksum, and if that doesn't match, the packet is dropped before it reaches us. Our encryption provides further checking of data received. We need only concern ourselves with erasures. ie. dropped packets.

FEC encodes the data in such a way that we can recover any lost packets, provided a certain minimum number of packets have been received.

Error correction has applications outside of multicast (and networking in general). Reed-Solomon erasure codes are what enable CDs to play even when scratched. ECC/FEC are used in bar codes to allow scanning of damaged codes. It is used in RAID modes like RAID6 to recover from the loss of a disk in an array. Erasure codes have been used with USENET posts to allow files to be recovered when posted in parts into a newsgroup and some of those parts get lost.

RaptorQ

RaptorQ (RFC6330) is a method of implementing a class of systematic erasure codes called fountain codes.

The data we want to send is split into blocks, and then pre-encoded into a set of intermediate symbols. From these intermediate symbols we can generate both our original source symbols, and also additional repair symbols.

Provided the recipient receives at least a minimum value K' of these symbols (any unique combination of source and repair) the intermediate symbols can be reconstituted, and the original data recovered.

RaptorQ is what is called a systematic encoding, because the set of symbols we send includes our original data as plain text. Provided all source symbols are received, the original data has been transmitted with no decoding overhead. It is only in the case where we need to supplement the source symbols with repair symbols that we must perform the decoding process.

LCRQ

lcrq is the Librecast RaptorQ FEC library. lcrq provides a C library implementation of RFC6330.

It was coded from the ground up and has zero external dependencies.

It has been tested and runs on Linux (Gentoo, Ubuntu, Debian), FreeBSD and NetBSD. We compiled and ran it on one of the original Raspberry PI Zeros from 2011 (Running Rasbian 7) and all the lcrq and librecast tests pass. We even compiled it on a VAX, and an (emulated) IBM s390.

Librecast Integration

Support for LCRQ is integrated into the Librecast library. Enabling FEC with RaptorQ is a matter of turning on this encoding with lc_channel_coding_set(3).

Getting Started

"Sounds great! Where do I get me some FEC?"

You have two options:

use liblcrq directly in your own code
enable FEC with liblibrecast

From Source

First, download lcrq from Codeberg.

Then install it as per the instructions in the README.md.

`make test` and `make speedtest` provide a simple way to verify the code is working as expected.

There are man pages for all of the API, and example programs can be found in examples/. `man 7 lcrq` is a good place to start.

Debian Experimental

Alternatively, on Debian you can install the library from Debian Experimental with `apt install liblcrq`. To get the development package use `apt install liblcrq-dev`. lcrq is available for all supported Debian architectures (and quite a few others).

Using FEC with Librecast

To use FEC with Librecast, download and install the latest liblibrecast release. FEC support was added in the 0.5.0 release.

To enable FEC for a Librecast Channel, turn on the RaptorQ encoding with: lc_channel_coding_set(3)

Tests 0039 and 0040 exercise the RaptorQ encoding. The first test (0039) sends some data, simulating a dropped packet, and recovers this with FEC. Test 0040 does the same, but with symmetric encryption also enabled. Encodings can be combined in the Librecast API, and we will be adding support for several more, including compression and other encryption modes

Future Directions

There are a handful of existing libraries that provide RaptorQ support. We could have used one of those, so why develop our own?

FEC is fundamental to multicast in the same way SYN/ACK is to TCP. The two technologies combine beautifully. It is important that we have a strong understanding of and full control over this part of the stack, so we can ensure that we do things in a multicast way. FEC isn't just something you turn on and forget (although Librecast tries to make it that simple). In the same way that the more you know about data, the better you can compress it, the more you know about your data flows the more effective the use of FEC will be. Things like block sizes make a huge difference to encoding speed, and multicast's ability to split data flows over multiple channels let us do things that simply aren't possible in unicast.

This will be an ongoing area of research for the project. We are looking with interest at BATS codes (BATched Sparse codes - like RaptorQ, but batched encoding).