From: Erika Rice (erice@cs.washington.edu)
Date: Sun Oct 10 2004 - 21:02:41 PDT
The paper "A Digital Fountain Approach to Reliable Distribution of Bulk
Data" by John Byers, Michael Luby, Michael Mitzenmacher, and Ashutosh
Rege discusses ways to improve distribution for non-real time broadcast
and multicast data (such as large scale software updates). Broadcast
and multicast cannot use the normal TCP reply/resend mechanism without
the replies potentially overwhelming the server. Furthermore, the
traditional mechanism is not well suited to having clients connect after
the broadcast has begun without causing duplicate data to be sent to
clients which are already connected.
The idealized solution they present is to have the server act as a
"digital fountain". In the digital fountain approach, the server sends
out a looping stream of packets. Receiving any subsets of the packets
from the stream which add up to the message size allows the receiver to
reconstruct the original message. Furthermore, the digital fountain
would provide a reliable, efficient, tolerant, on demand data stream to
clients.
The authors describe a method which uses linear combinations of data to
produce redundancy to approximate this ideal. Their method is an
improvement over previous methods in that the linear combinations form a
sparse matrix that takes less time to encode and decode than the dense
matrix used by previous methods. The downside of this approach is that
the receiver may have to receive more information that the size of the
message to be able to reconstruct the method.
This paper does a good job of presenting convincing arguments as to the
scalability of this method. They also do a through job of showing their
efficiency of their method; for example, they choose to compare their
encoding method against the best implementation of an older encoding
method.
One drawback of this paper was the failure to consider whether or not
their methods could be applied to real time data streams. The authors
make it very clear that their method was not developed with real time
applications in mind, but they do not discuss the possibility of their
method becoming applicable to real time data if it is modified.
The approach presented in this paper seems like a useful addition to the
methods used for improving multicast and broadcast. The authors clearly
recognize the strengths of simplicity and efficiency and, as a result,
accept that the ideal digital fountain is perhaps best realized by
imperfect approximations.
This archive was generated by hypermail 2.1.6 : Sun Oct 10 2004 - 21:02:44 PDT