From: Danny Wyatt (danny@cs.washington.edu)
Date: Sun Oct 10 2004 - 23:32:21 PDT
A Digital Fountain Approach to the Reliable Distribution of Bulk Data
John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutsoh Rege
This paper presents a method for using erasure codes to improve the
efficiency of multicast data distribution and evaluates the performance
of one family of codes---Tornado codes---in such a system. They
delineate 2 primary trade-off dimensions on which to evaluate to
performance: encoding/decoding time and decoding inefficiency. They
show that Tornado codes outperform Reed -Solomon codes when measured
only in encoding/decoding time for an entire message. And they show
that, after holding both methods equal on one dimension, Tornado codes
also outperform Reed-Solomon over interleaved blocks in the other
dimension. The intended effect of that experiment is to show that no
matter how the trade-off is managed with R-S codes, Tornado codes will
always outperform them.
I thought this paper did a great job backing up its claims with
empirical results. They defined their variables well and devised
experiments to cover them and beyond---making sure to try "realistic"
simulated data with bursty errors, to vary the size of the file being
distributed, the probability of packet loss, and the number of
receivers. Indeed, if the papers suffers it is from one experiment too
many. The final experiment showing the prototype implementation could
have stood on its own without the addition of layering.
That said, it leads to my final thought. Not knowing what was state of
the art in networking when this paper was written, I can only assume
that they had to address layering lest they be accused of ignoring a
current technique. Similarly, I take it on faith that interleaved block
Reed-Solomon was also the state of the art for bulk distribution. Their
results are convincing to me, but only if they've picked a "worthy
adversary", as it were, for all of their comparisons.
This archive was generated by hypermail 2.1.6 : Sun Oct 10 2004 - 23:33:03 PDT