The author can be contacted at the following address:
Abstract: Reliable communication protocols require that all the intended recipients of a message receive the message intact. Automatic Retransmission Request (ARQ) techniques are used in unicast protocols, but they do not scale well to multicast protocols with large groups of receivers, since segment losses tend to become uncorrelated thus greatly reducing the effectiveness of retransmissions. In such cases, Forward Error Correction (FEC) techniques can be used, consisting in the transmission of redundant packets (based on error correcting codes) to allow the receivers to recover from independent packet losses.
Despite the widespread use of error correcting codes in many fields of information processing, and a general consensus on the usefulness of FEC techniques within some of the Internet protocols, very few actual implementations exist of the latter. This probably derives from the different types of applications, and from concerns related to the complexity of implementing such codes in software. To fill this gap, in this paper we provide a very basic description of erasure codes, describe an implementation of a simple but very flexible erasure code to be used in network protocols, and discuss its performance and possible applications. Our code is based on Vandermonde matrices computed over $GF(p^n)$, can be implemented very efficiently on common microprocessors, and is suited to a number of different applications, which are illustrated in the paper. An implementation of the erasure code shown in this paper is available from the author and running in the MB/s speed range when implemented in software on a Pentium133.
Abstract: Forward Error Correction (FEC) is seldom used in computer networks, because of perplexity in doing the necessary encoding/decoding in software. We believe this diffidence to originate from the fact that error control codes (which FEC is usually based upon) are generally designed and presented stressing their ability to correct {\em errors} rather than {\em erasures} (i.e. missing data in known locations). Handling erasures is a much simpler computational problem, and can be approached and solved with much simpler techniques.
This paper has three main objectives. First, to put software FEC in the right perspective by presenting the principle of operation of erasure codes and showing that software FEC is not exceedingly expensive. Second, to provide the research community with a high performance, C implementation of erasure codes capable to run at speeds in excess of 100 Mbit/s. Third, to present a number of applications (some of which have been developed, by the author or other researchers) where software FEC can, despite its overhead, be used to actually improve performance. These application cover slow, wireless networks and fast wired networks, as well as unicast and multicast communication protocols. Our conclusion is that software FEC is feasible and useful in a number of applications, and does not require supercomputing power to be implemented.