Forward Erasure Correction

Introduction

It consists of an encoder and a decoder. The encoder is fed a stream of data which it breaks up into packets. These packets can then be sent over an unreliable transport mechanism, typically UDP. The decoder can then reconstruct lost packets from redundant packets sent by the encoder.

Like other implementations, the encoder groups n packets of payload together and then adds k redundant packets to it. The receiver can only start to reconstruct any of the lost payload once it has received at least n packets in total.

I wanted everything to be as clean as possible, with no fancy features. Since it's open source, anyone is free to improve things as they see fit. Contributions should start with the to do list at the end of this document.

My intention was that it can be used in those cases where there is no back channel e.g. one-way satellite link. So, if the library has been properly configured, all data will be recovered, even if many megabytes is lost due to external events like thunder storms.

Parameters

1. s the size of each packet, excluding headers. (See 5 below).
2. n the number of packets that are grouped together. This determines latency i.e. the receiver may end up having to wait until the whole group was received before it has enough data to output the first packet. Unless you have latency or memory concerns, you may as well set n to the number of packets you are sending. (See 3 below)
3. k the number of redundant packets sent for each group. k / (n + k) should preferrably be much higher than the the error rate of the transport mechanism on a per packet basis. Note that the k redundant packets are accessed very frequently, so it is advisible that k * s should be less than the amount of physical memory (RAM). Also note that as n gets smaller the chance to loose k of them increases (especially if there are burst losses), so n should be as large as possible. Usually the k * s will equal to the maximum expected amount of data that could be lost.

   Maybe someone will write a function that uses probability models to work out the smallest suitable value of k...

4. w the width of the band in the band matrix. The larger w, the more processing power is needed. Typically 40 is a good default. In the unfortunate case that you loose a packet and all 40 redundant packets in its column, the reconstruction will fail. Fortunely these 41 packets are pseudo randomly distributed amoung the k + n packets so the chance of that happening is not great.
5. g The size of the Galois field is 2^g. The computing time increases linearly with g (unlike other O(1) implementations). Because a field has only 1 element which does not have a multiplication inverse, the probability of not being able to find a spil element when we have k - i rows left to choose from is 2^{-g * (k - i)}. So a good value of g is 2, 3 or 4. s must be a multiple of g * 4.
6. b the number of bits per second that the encoder should limit the output to. This prevents network overload. Setting this to 0, implies that it should send as fast as possible.

Functions

fecEncoder *NewFecEncoder (void *userData,
  size_t (*userSend)(void *buf, size_t size, size_t count, void *userData),
  char **errorMessage,
  int s, int n, int k, int w, int g, int b);

void FecEncode (fecPayload *buf, fecEncoder *f);

void DeleteFecEncoder (fecEncoder *f);

typedef struct fecDecoder;

fecDecoder *NewFecDecoder (void *userData, 
  void (*userReceive)(void *userData, __int64_t position, fecPayload *buf, int len)
);

size_t FecDecode (void *buf, size_t size, size_t count,
  fecDecoder *f);

void FlushFecDecoder (fecDecoder *f);

void DeleteFecDecoder (fecDecoder *f);

To Do list

1. Implement sub channels Currently we send a very large header packet. Because we need it at the receiver, it must be sent with every packets.

   It consumes less bandwidth to implement a sub channel to send the 20 odd bytes of control information : Now the header is e.g. 2 bytes. The first bytes sends would be a simple modulo 2⁸ counter. The second byte would contain 1 byte of control data if the first byte is less than 20, and would be a checksum byte otherwise. This checksum scheme can also use Galois Fields and Gaussian elimination, but it's parameters must chosen so that it will still function under the worst possible error rates.

2. Optimizations
3. Packet checksum Let the library send its own checksums incase the UDP checksum still lets some bad packets get through.
4. Non field rings It is quite possible that there exists some polynomials that are not primative, and the resultant ring is not a field, but most of the ring is invertible, and they can be manipulated for even faster operation. This needs to be investigated.
5. Overflow of i If more than 2 billion packets are send, problem may occur. We need to fi this.

Copyright

Copyright (c) 2002 Nic Roets.  All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:

1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in
   the documentation and/or other materials provided with the
   distribution.

3. All advertising materials mentioning features or use of this
   software must display the following acknowledgment:
   "This product includes software developed by Nic Roets"

4. Redistributions of any form whatsoever must retain the following
   acknowledgment:
   "This product includes software developed by Nic Roets"

THIS SOFTWARE IS PROVIDED BY NIC ROETS `AS IS'' AND ANY
EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL NIC ROETS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
OF THE POSSIBILITY OF SUCH DAMAGE.