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
|