From: Ethan Phelps-Goodman (ethanpg@cs.washington.edu)
Date: Sat Oct 09 2004 - 15:43:35 PDT
A Digital Fountain Approach to Reliable Distribution of Bulk Data
Byers et al.
This paper considers the problem of multicasting data to a large number of recievers without incurring the huge cost of retransmissions to individual recievers. There has been a large body of work on this subject, most using Reed-Solomon base erasure codes. The main contribution of this paper is to demonstrate an improved system using Tornado codes (introduced by the authors in an earlier STOC paper.) Reed-Solomon codes were inadequite primarily becuase their encoding and decoding time grows quickly with the data size. This forced broadcasts to be broken up into blocks which were encoded separately. Missing a block required either retransmission or waiting for packets from that block to be rebroadcast at a latter time. The authors present an idealized system called a digital fountain, in which a constant stream of packets is broadcast in which any k distinct packets is enough to recover a source message of length k.
Reed-Solomon erasure codes encode a source of length k into a system of linear equations over a finite field, such that any k encoded blocks are enough to solve for all variables. Tornado codes use a sparse system of equations over GF(2). This allows Tornado codes to be decoded very quickly, but introduces some size overhead since k equations will not in general fix all k variables. The authors give performance data for the bare encoding algorithms, and for muliticast systems built with these algorithms. For comparable size efficiencies, Tornado codes are one to two orders of magnitude faster to decode. With the parameters of the Reed-Solomon codes adjusted to give the same speed as Tornado codes, the Tornado codes add about 50% to the size of the data the must be recieved.
The paper concludes with an implementation of Tornado codes over IP Multicast. The design of the system is well thought out, but doesn't introduce any new ideas. The paper does a good job of describing a new system and gives strong evidence that it outperforms existing solutions. The real intellectual work however was in the earlier work on the mathematics of Tornado codes and on the design of multicast systems.
Ethan Phelps-Goodman
This archive was generated by hypermail 2.1.6 : Sat Oct 09 2004 - 15:43:41 PDT