1998 | John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege
A digital fountain is a scalable protocol for reliably distributing bulk data to a large number of autonomous clients. It allows any number of heterogeneous clients to acquire data with optimal efficiency, without requiring feedback channels for reliable delivery, even in high loss environments. The paper introduces Tornado codes, a new class of erasure codes that are significantly faster than standard Reed-Solomon codes for large block sizes. Tornado codes enable efficient decoding with slightly more than k packets, leading to a much better approximation of a digital fountain than Reed-Solomon codes. The paper compares Tornado codes with interleaved codes and shows that Tornado codes have lower decoding inefficiency and faster decoding times. The paper also describes an experimental system based on Tornado codes for reliable bulk data distribution using IP multicast. The system demonstrates the feasibility of the approach and shows that it is interoperable with layered multicast techniques. The paper concludes with additional research directions for the digital fountain approach.A digital fountain is a scalable protocol for reliably distributing bulk data to a large number of autonomous clients. It allows any number of heterogeneous clients to acquire data with optimal efficiency, without requiring feedback channels for reliable delivery, even in high loss environments. The paper introduces Tornado codes, a new class of erasure codes that are significantly faster than standard Reed-Solomon codes for large block sizes. Tornado codes enable efficient decoding with slightly more than k packets, leading to a much better approximation of a digital fountain than Reed-Solomon codes. The paper compares Tornado codes with interleaved codes and shows that Tornado codes have lower decoding inefficiency and faster decoding times. The paper also describes an experimental system based on Tornado codes for reliable bulk data distribution using IP multicast. The system demonstrates the feasibility of the approach and shows that it is interoperable with layered multicast techniques. The paper concludes with additional research directions for the digital fountain approach.