From: Charles Reis (creis@u.washington.edu)
Date: Mon Oct 11 2004 - 00:45:51 PDT
A Digital Fountain Approach to Reliable Distribution of Bulk Data
Byers, et al., 1998
Unlike the previous two classic papers reviewed, here the authors take a more traditional research approach, selecting a narrowly defined problem and improving upon existing solutions, guided by an idealized solution and theoretical analysis. The paper focuses on reliable delivery of bulk data over unreliable and possibly one-way links, such that senders can multicast or broadcast encoded data repeatedly, and clients can come and go, only needing to receive any subset of sufficient size to reconstruct the data. Noting the ideal metaphor of a digital fountain, the authors improve upon Reed-Solomon codes with Tornado codes, which require far less processing for encoding and decoding.
Despite the notable benefits in decoding inefficiency and decoding times shown in both simulation and experiment, it appears that many parameters remain to be explored, such as the stretch factor or choice of random graph for encoding. More importantly, the scope of the work seems narrowed by the fact that most of the encoded data must be received before any useful decoding can begin, preventing its use for any streaming media solutions. Nonetheless, it is surprising not to see more visible implementations of digital fountain techniques for bulk data like software updates; perhaps the failure of IP multicast to catch on is one limiting factor. Future work likely involved further improvements to the encodings, while the work might also be relevant for newer P2P multicast services.
This archive was generated by hypermail 2.1.6 : Mon Oct 11 2004 - 00:45:53 PDT