From: Seth Cooper (scooper@cs.washington.edu)
Date: Mon Oct 11 2004 - 00:18:03 PDT
The purpose of this paper is to present a protocol for a "digital
fountain," which is an effective way to perform multicast. A digital
fountain is essentially a server multicasting packets in such a way that
clients can join the limit cast, receive an amount of data equal to the
size of the file they are trying to receive, and then reconstruct the
file, similar to how someone The design of the protocol seeks to be
reliable, efficient, on demand, and tolerant. The paper proposes using
Tornado codes instead of the traditional Reed-Solomon codes the encode
the broadcast data.
The main strength of the proposed protocol is the strength of Tornado
codes over the Reed-Solomon codes: Tornado codes are much faster to
encode and decode. Even though Tornado codes require receiving slightly
more packets than Reed-Solomon, the time lost in packet transmission is
more than made up for by the decrease in decoding time at the receiver.
The paper presents some benchmarks showing that for large files, the
decoding time for a client receiving Reed-Solomon encoded packets can
become prohibitively expensive. One of the reasons for this is that
Tornado codes rely only on exclusive ors, while Reed-Solomon codes
depend on field operations and matrix multiplications to be decoded.
Another strength of the paper is the proposal to use multicast layering
to control congestion. An initial concern about a protocol such as a
digital fountain that would be continuously multicasting would be that
it would consume a lot of bandwidth. But through the use of
"synchronization points" marked periodically in the stream, the paper
claims that the protocol shares bandwidth in a fashion comparable to TCP.
The paper could be improved by comparing various Tornado codes with
other Tornado codes. Most of the comparisons of the paper are between
Tornado codes and Reed-Solomon codes. It would be interesting to see,
within the Family of Tornado codes, what the impact of trading off
decoding inefficiency and decoding time would be.
The paper mentions applying Tornado codes to disperisty routing of data
and to more effectively mirror data. Another interesting application of
the digital fountain approach might be to see how it could be applied to
peer-to-peer networks where different peers could coordinate sending
non-redundant packets to each other.
This archive was generated by hypermail 2.1.6 : Mon Oct 11 2004 - 00:17:54 PDT