Forward Error Correction

[mcelrath]

Forward Error Correction is a mechanism by which extra data is sent over the wire which allows the receiver to reconstruct any missing data due to packet loss, without a round trip.

QUIC is a low-latency UDP protocol which will retry for missed packets.

The QUIC standards group experimented with FEC as early as 2016 but it was removed from the spec in 2017 because it showed poor improvement for the use cases under consideration (mostly streaming video). Here is a review from a Google employee focusing on Youtube, search, and browser metrics, and a discussion. This is focused on the XOR method.

The focus on streaming in evaluations of this technology has hindered its adoption, as it's just not that awesome in a streaming context. Braidpool's use case where latency is paramount does not have a lot of overlap with the evaluations done on FEC so far and FEC is probably a lot more valuable for Braidpool than other use cases.

FEC methods:

1. XOR: can recover exactly one lost packet (aka parity block)
2. Reed-Soloman: can recover k out of n packets. k must be decided ahead of time and cannot be adaptive. Used in RAID arrays among other things.
3. Tornado Code: a faster version of Reed-Soloman with the same characteristics
4. Fountain Code: limitless number of additional packets can be generated for recovery. Uses Langrange interpolation over a polynomial (simple explanation/demo)
5. Raptor Code: successor to Fountain codes, linear time encoding and decoding (rust), adaptive recovery.

A Braidpool use case would use either Fountain Codes or Raptor Codes, or some other mechanism that is adaptive -- peers will measure their packet loss rate and communicate to each other how much extra data to send. Data should be encoded in packets matching the network's MTU (1500 bytes - overhead) and assumed to be lost all-or-none. Peers should send slightly more data than the expected packet loss rate, at minimum one extra packet and a maximum set by a statistical analysis of the number of expected lost packets given the average packet loss.

There continues to be work on adding FEC to QUIC 2024 proposal, 2025 proposal. The 2024 proposal was not adopted by QUIC and does not specify the FEC scheme, any of the above could be used. The 2025 proposal only mentions XOR and Reed-Soloman.

[mcelrath]

https://link.springer.com/article/10.1007/s11227-024-06346-9