-------------------------------------------------------------------------------
                                       
                                       
		   B O S T O N   U N I V E R S I T Y
                                       
		      Computer Science Department
                                       
			  C O L L O Q U I U M
                                       
      A Digital Fountain Approach to Reliable Asynchronous Multicast

                              John Byers

                 International Computer Science Institute 
                                  and
                    University of California, Berkeley


                         Wednesday, April 8th
                                       
			        11:00am 
		       (Coffee served at 10:45am)

                                       
			 Seminar Room / MCS 135
                                       

-------------------------------------------------------------------------------



The proliferation of network applications such as software distribution
which must reliably deliver large files to a vast number of autonomous 
clients motivates the design of new multicast and broadcast protocols.  
Among the significant challenges in supporting these applications are 
ensuring reliable delivery across heterogeneous client capabilities, 
minimizing reception time and minimizing feedback from clients to the 
source server.

Our results build on a growing body of work which addresses these challenges 
using ideas from coding theory and information dispersal.  In particular, 
the use of erasure codes enables the source to transmit redundant, encoded
data which can be used at the clients to recover lost message data.  We
prove that the use of codes is a prerequisite for delivering the highest 
performance for these applications.  We then describe an ideal, fully 
scalable protocol for these applications that we call a digital fountain.  
Autonomous clients who subscribe to a digital fountain can efficiently 
reconstruct the source data once they receive any sufficiently large
set of distinct packets.

The limiting factor in implementing such a scheme has been the encoding
and decoding time associated with traditional erasure codes.  The protocol 
we develop closely approximates a digital fountain using a new class of 
erasure codes that are orders of magnitude faster to encode and decode 
than standard erasure codes but have slightly worse decoding guarantees.  
We discuss the design and implementation of an experimental system built 
on top of IP multicast and provide performance measurements that 
demonstrate the effectiveness of our approach. 


Joint work with Michael Luby, Michael Mitzenmacher, and Ashutosh Rege.



Host: Wayne Snyder (snyder@cs.bu.edu)

-------------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
-------------------------------------------------------------------------------