Efficient and Fault-tolerant Application-level Multicast
on Structured P2P Overlays

The demand for streaming multimedia applications is growing at an incredible rate. Such applications are distinguished by a single writer (or small number of writers) simultaneously feeding information to a large number of readers.  Current trends indicate a need to scale to thousands or millions of receivers.  To say that such applications stress the capabilities of wide-area networks is an understatement. When millions of receiving nodes are involved, unicast is completely impractical because of its redundant use of link bandwidth; to best utilize network resources, receivers must be arranged in efficient communication trees.  This in turn requires the efficient coordination of a large number of individual components, leading to a concomitant need for resilience to node and link failures.

Given barriers to wide-spread deployment of IP multicast, researchers have turned to application-level solutions. The major challenge is to build an efficient network of unicast connections and to construct data distribution trees on top of this overlay structure.  Currently, there are no designs for application-level multicast protocols that scale to thousands of members, incur both minimal delay and bandwidth penalties, and handle faults in both links and routing nodes.

We propose Bayeux, an efficient, source-specific, explicit-join, application-level multicast system that has these properties. One of the novel aspects of Bayeux is that it combines randomness for load balancing with locality for efficient use of network bandwidth.  Bayeux utilizes a prefix-based routing scheme that it inherits from  Tapestry.  In addition to the base multicast architecture, Bayeux leverages the Tapestry infrastructure to provide simple load-balancing across replicated root nodes, as well as reduced bandwidth consumption, by clustering receivers by identifier.


Bayeux: An Architecture for Scalable and Fault-tolerant Wide-Area Data Dissemination
Shelley Q. Zhuang, Ben Y. Zhao, Anthony D. Joseph, Randy H. Katz, John Kubiatowicz
The 11th International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV)
Port Jefferson, New York, 2001
[Abstract, PDF (110KB), ps.gz (102KB)]


Bayeux: An Architecture for Scalable and Fault-tolerant Wide-Area Data Dissemination
Presented at NOSSDAV 2001, Port Jefferson, New York, 2001.


Ben Y. Zhao, February 24, 2003