From: Chandrika Jayant (cjayant@cs.washington.edu)
Date: Sun Oct 10 2004 - 21:41:04 PDT
"A Digital Fountain Approach to Reliable Distribution of Data"
Written by Byers, Luby, Mitzenmacher, and Rege
Reviewed by Chandrika Jayant
This paper discusses a way to reliably distribute bulk data
to a large number of autonomous clients. The authors describe an ideal
and fully scalable protocol, the "digital fountain," closely approximate
this ideal protocol using Tornado codes, and provide performance
measurements to show the advantages of this method. The paper is
organized wonderfully by separating the ideal goal from the approximated
one, and the results shown really convince the reader that this protocol
works well. The digital fountain idea is a beautiful and simple concept
which allows for flexibility which seems to be one of the most important
necessities for successfully joining heterogeneous networks. The
comparison of Tornado codes versus Reed Solomon shows a graceful
solution using exclusive-or instead of costly field operations.
Performance results are impressive. The comparison to interleaving is
explained even more thoroughly and convincingly. An actual
implementation and example are provided, for added insight.
I would have liked more of a background on interleaving but
the comparisons to Tornado codes are very impressive. In comparing
Tornado codes with Reed Solomon, for all the trials the same graph was
used and was generated randomly. I was not convinced that the
performance is representative, and the paper even suggests that better
performance might be achieved by testing various random graphs for
performance (couldn't it also be worse?). I would like to see this
backed up by concrete results. Also, the idea of Tornado codes isn't the
authors' idea, this paper just seems to convey its advantages and its
results. A novel idea even in its implementation would have made this a
stronger and more important paper.
I actually wouldn't do much to improve this paper- it is one
of the most solidly organized and backed up papers I have read. However
there are some weak spots (like just picking 1 graph in testing,
skimming over the important issue of the effect of large packet losses,
the Tornado code's problem with stretch factor, and inadequacy for real
time applications that are just mentioned and not discussed in effective
detail).
This paper is relevant today because truly effective
broadcast/multicast goals still haven't been met; this paper provides
explanations of many of the complications that could arise and possible
solutions for some of them. It conveys that there are a bunch of
tradeoffs that must be played with, not just one clear way to approach
matters. Also we see that we might want different approaches to
different applications.
Some future work suggested is looking into the problem of
when receivers change their reception level over time- exploring this
efficiency/ behavior and optimizing it. It would be useful to test a
similar system (as the one used in the paper) with a large number of
users to demonstrate the effectiveness of the paper's approach. It's
also suggested to study the topic in the context of mirrored data and
finding a balance between small and large stretch factors.
This archive was generated by hypermail 2.1.6 : Sun Oct 10 2004 - 21:41:22 PDT