Benchmark comparisons of erasure codes


Michael Luby



Hardware-based forward-error correcting (FEC) codes have been in use for years to add reliability, e.g., to protect satellite transmission from errors and losses, to protect CDs against losses due to scratches, to protect modem lines from noisy transmission, and to protect disk arrays from faults (RAID). For the most part, special purpose hardware is built to implement the FEC codes, and in many cases they are Reed-Solomon based. Forward error-correction (FEC) codes for erasure protection have recently been the focus of interest in the networking community to add reliability to packet based communications protocols. For these applications, software-based erasure codes are quite desirable. An important characteristic of erasure codes is how the encoding and decoding times grow with the length of the message to be protected and the amount of protection to be added to the message. Benchmarks for three software-based implementations of erasure codes follows. All of these implementations could probably be optimized to reduce the running times by a small constant factor.

  • Tornado Codes -- These erasure codes were recently developed. More information about these codes is available on this page. The encoding and decoding times for these codes scales linearly with the size of the message. I implemented and ran the benchmarks for the Tornado codes.

  • Cauchy-based Reed-Solomon codes -- More information about these erasure codes is available on this page. These erasure codes are based on traditional Reed-Solomon codes, and are implemented in a way that makes them run reasonably fast using a reasonable amount of memory. The encoding and decoding times for these codes scales quadratically with the size of the message. I implemented and ran the benchmarks for the Cauchy-based codes.

  • Vandermonde-based Reed-Solomon codes -- These erasure codes are also based on traditional Reed-Solomon codes, and are implemented in a way that makes them run reasonably fast. The encoding time scales quadratically with the size of the message, and the decoding time scales more than quadratic. (It is more than quadratic because of the space and time needed to invert the matrix on larger inputs with this implementation -- the decoding time could possibly be reduced to quadratic with a more space efficient implementation). Luigi Rizzo from the University of Pisa implemented these codes, and the benchmarks were run by Christian Riechmann. The source code for these codes can be found here. All of the benchmarks were run with field length 13. This forces the code to perform finite field element operations explicitly instead of using table lookup. Running with table lookup reduces the running times by a factor of 4, e.g., for SIZE=500K Bytes, the encode time is 9.4 seconds (versus 39 seconds reported in the first table) and the decode time is 7.1 seconds (versus the 32 seconds reported in the second table below). However, table lookup can only be used on message sizes up to around 500 Kbytes. This implementation reported a program error on a 4M Bytes message, and thus it could not be benchmarked on the larger message sizes.

    Parameters of the Benchmarks All of the experiments were benchmarked on a SUN 167 MHz Ultrasparc 1 with a 64M Bytes RAM. All runs used packets of length 1K Bytes each. All implementations are written in C.

    Encoding experiment -- A message of length SIZE was encoded by adding redundancy of length SIZE, and thus the total length of the encoding is 2*SIZE.

    Encoding Benchmarks
    Erasure codes
    SIZE Vandermonde Cauchy Tornado
    250K Bytes 9.0 seconds 4.6 seconds 0.06 seconds
    500K Bytes 39 seconds 19 seconds 0.12 seconds
    1M Bytes 150 seconds 93 seconds 0.26 seconds
    2M Bytes 623 seconds 442 seconds 0.53 seconds
    4M Bytes not available 1717 seconds 1.06 seconds
    8M Bytes not available 6994 seconds 2.13 seconds
    16M Bytes not available 30802 seconds 4.33 seconds


    Decoding experiment -- For both the Cauchy-based and the Vandermonde-based codes, a portion SIZE/2 of the original message and SIZE/2 of the redundancy was used to recover the original message of length SIZE. For the Tornado codes, slightly more of each portion was used to recover the original message, i.e., on average 1.05*SIZE/2 of the original message and 1.05*SIZE/2 of the redundancy was used to recover the original message of length SIZE.

    Decoding Benchmarks
    Erasure codes
    SIZE Vandermonde Cauchy Tornado
    250K Bytes 11.0 seconds 2.06 seconds 0.06 seconds
    500K Bytes 32 seconds 8.40 seconds 0.09 seconds
    1M Bytes 161 seconds 40.5 seconds 0.14 seconds
    2M Bytes 1147 seconds 199 seconds 0.19 seconds
    4M Bytes not available 800 seconds 0.40 seconds
    8M Bytes not available 3166 seconds 0.87 seconds
    16M Bytes not available 13269 seconds 1.75 seconds