From: Karthik Gopalratnam (karthikg@cs.washington.edu)
Date: Mon Oct 11 2004 - 01:14:13 PDT
Digital Fountain - Byers et. al.
This paper introduces the concept of the "Digital Fountain" which is a
protocol for efficiently multicasting data to several users, based on
Tornado coding.
The principal idea of a digital fountain is to use some form of erasure
coding mechanism to split up a data item into 'k' chunks, and encoding these
'pieces' into 'n' packets with possible redundancy such that a receiver
receiving any 'k' packets can reconstruct the original data. The original
solution to this coding problem involved Reed-Solomon codes, which suffered
from the drawback that encoding and decoding were both expensive operations,
especially as the amount of redundancy or 'stretch' in the code increased.
Since networks with any appreciable degree of packet loss would require a
significant stretch of the codes, Reed-Solomon codes would possibly be
infeasible in practice. The authors propose a digial fountain multicast
scheme based on a different type of erasure code - the Tornado Code,
introduced by one of the authors in an earlier STOC-97 paper. The advantage
of Tornado codes is that they are much faster for encoding and decoding
since they take advantage of optimized operations on sparse matrices. The
tradeoff however lies in the fact that a greater number of packets have to
be transmitted to achieve reliable decoding. The authors however make a
theoretical average-case analysis and show experimental evidence for the
fact that the gains in coding time outweigh the loss in coding efficiency.
It appears that the protocol itself is merely a tweak to already
existing protocols to account for Tornado codes, and therefore, the real
importance of this paper is questionable given that Tornado codes already
appeared in an earlier paper. Also, to place the work in perspective today,
this scheme would have to be evaluated for a much larger average file size
and number of receivers than was foreseen in the paper.
This archive was generated by hypermail 2.1.6 : Mon Oct 11 2004 - 01:14:14 PDT