From: Michael J Cafarella (mjc@cs.washington.edu)
Date: Sun Oct 10 2004 - 19:58:24 PDT
A Digital Fountain Approach to Reliable Distribution of Bulk Data
By Byers, Luby, Mitzenmacher, Rege
Review by Michael Cafarella
CSE561
October 11, 2004
Main result:
The authors describe the "digital fountain" model of data distribution,
in which a receiver can decode a message using any k of n packets. They
give a technique that implements a digital fountain with very small
encoding and decoding overhead. They also show how it can be used in
a real protocol, though I thought this section was not really necessary.
Strengths of paper:
The use of Tornado codes for digital fountains, along with detailed
analysis, is clearly the meat of the paper. The authors do a good
job of describing why it's an important problem, as well as how
Tornado codes actually work. I appreciate the effort to include
protocol-level work, but it feels beside the point.
Limitations, other problems:
Tornado codes are suitable for traditional file transfer, not
lossy media transfers. It would be possible to use the techniques
here for streaming applications, if the encoder chunked the outgoing
stream.
The recipient needs to make multiple passes over the received data.
Indeed, it needs to somehow quickly check whether the arrival
of a packet enables it to decode previously-received packets. This
might involve keeping all received packets in-memory until the
entire set can be decoded, which is obviously unsuitable for very
large files. Alternatively, to-be-decoded packets can be stored
on disk, but a recipient would need a fast disk-based decoding
method, which isn't obvious.
Possible improvements:
I'd like to see more data on the decoder, and how it might be
implemented. Especially for very large files, it seems difficult
to do properly.
Modern relevance, future work:
Since this paper was published in '98, I'm unaware of any
systems that use this approach. I'd imagine this is because the
only really lossy channels we deal with nowadays are wireless
ones. Except for satellite, there's not much need for bulk
wireless data transfer. I could imagine this gets a lot of
use by satellite broadcasters, but I don't know.
This archive was generated by hypermail 2.1.6 : Sun Oct 10 2004 - 19:58:24 PDT