Motivation and Approach
Live streaming media will form a significant fraction of Internet traffic in the near future. YouTube clips, animations and other video applications already account for more than sixty percent of Internet traffic and, at its current acceptance rate, streaming media could quickly surpass television in terms of the size of its client base. Our work is motivated by the vision of delivering high-quality streaming media to a virtually unlimited number of peers over the Internet following a purely cooperative model.
Multicast is an efficient mechanism to support these classes of applications as it decouples the size of the receiver set from the amount of state kept at any single node and potentially avoids redundant communication in the network. The past decade has brought a number of application-level approaches to support mass media distribution. With an application-level approach, end systems configure themselves in an overlay topology for data delivery employing by conventional unicast paths. All multicast-related functionality is implemented at the end systems, instead of at the routers, providing most of the benefit of the network layer approach while avoiding the deployment and scalability issues with IP multicasting. While significant progress toward this vision has been made over these last few years, supporting high-quality, bandwidth-intensive applications in cooperative environments remains a challenge.
For streaming application where timely data delivery is a key requirement, trees are generally considered the preferred overlay structure. Trees have proved to be highly scalable and efficient in terms of physical link stress, overhead, and end-to-end latency. Unfortunately, conventional tree-based multicast are not well matched to the characteristics of our target domain. First, as multicast functionality is pushed to autonomous, unpredictable end systems, significant performance loss can result from their higher degree of transiency when compared to routers and their inherent dependency on interior nodes. Second, when employed for bandwidth-intensive applications, conventional tree structures are likely to be bandwidth constrained as bandwidth monotonically decreases as one ascends from the leaves and high-level paths quickly become the bottleneck under high load. Finally, since a small fraction of interior nodes are solely responsible for data replication and forwarding, while leaf nodes contribute no resources, conventional trees challenge the expectation of cooperating systems where every peer contributes resources in exchange for using the common service. While simply splitting content among all participants can clearly ensure balanced load distribution in mostly homogeneous environment, in heterogeneous dynamic environments this would come at a high cost in terms of performance.
We believe it is feasible to retain the advantages of tree-based overlay structures while addressing its limitations to support high-quality, bandwidth-intensive applications in cooperative environments. We have proposed a number of generic techniques to address the three aforementioned issues: resilience, bandwidth constraints near the root and fair load distribution with high performance.
- We argue for protocols that achieve structural resilience through the introduction of co-leaders, alternative leaders that help avoid single-node dependencies and provide alternative paths for data forwarding. For more details.
- We propose to address the bandwidth constraints of conventional trees by importing Leiserson's fat-trees from parallel computing into overlay networks. For more details.
- We posit that overlays composed of multiple performance-centric balanced trees enable fair resource contributions among peers without impacting overall system performance. For more details.
We have provided working prototypes of our techniques in three reference implementations: Nemo, a structurally resilient overlay, FatNemo, a fat-tree overlay for high-bandwidth multicast, and Magellan, a performance-centric multi-tree overlay that maximizes fair load distribution while meeting stated performance expectations.
People
- Fabián E. Bustamante, Faculty PI
- Stefan Birrer
- Yi Qiao
Collaborators
Publications
- Stefan Birrer and Fabián
E. Bustamante. Resilience in Overlay Multicast
Protocols, In Proc. of the 14th IEEE/ACM
International Symposium on Modeling, Analysis, and Simulation
of Computer and Telecommunication Systems (MASCOTS 2006),
September 2006.
Abstract | PostScript [251K] | PDF Format [78K] - Stefan Birrer and Fabián E. Bustamante. The
Feasibility of DHT-based Streaming Multicast, In
Proc. of the 13th IEEE/ACM International Symposium on
Modeling, Analysis, and Simulation of Computer and
Telecommunication Systems (MASCOTS 2005), September
2005.
Abstract | PostScript [251K] | PDF Format [78K] - Stefan Birrer and Fabián
E. Bustamante. Magellan: Performance-based,
Cooperative Multicast, In Proc. of the Tenth
International Workshop on Web Content Caching and
Distribution, September 2005.
Abstract | PostScript [480K] | PDF Format [139K] - Stefan Birrer, Fabián E. Bustamante, Dong Lu, Peter
Dinda and Yi Qiao. FatNemo: Multi-Source Multicast
Overlay Fat-Tree, Poster in Proc. of the Second
Symposium on Networked Systems Design & Implementation
(NSDI), May 2005.
Abstract | PostScript [107K] | PDF Format [13K] | Poster in PDF Format [1.3MB] - Stefan Birrer and Fabián
E. Bustamante. Nemo- Resilient Peer-to-Peer Multicast
without the Cost. In Proc. of the 12th Annual
Multimedia Computing and Networking Conference (MMCN'05),
January 2005 (Also published as Tech. Report
NWU-CS-04-36).
Abstract | PostScript [260K] | PDF Format [101K] - Stefan Birrer, Dong Lu, Fabián E. Bustamante, Yi
Qiao and Peter Dinda. FatNemo: Building a Resilient
Multi-Source Multicast Fat-Tree, In Proc. of the
Ninth International Workshop on Web Content Caching and
Distribution, October 2004.
Abstract | PostScript [421K] | PDF Format [238K] - Stefan Birrer and Fabián
E. Bustamante. Resilient Peer-to-Peer Multicast from
the Ground Up, In Proc. of the IEEE Network
Computing and Applications - Workshop on Adaptive Grid
Computing, August-September 2004 (Also published as Tech. Report
NWU-CS-03-22).
Abstract | PostScript [2.2M] | PDF Format [229K]
Resources
- The Nixes Tool Set - A set of bash scripts to install, maintain, control and monitor applications on PlanetLab.
- Nemo - Resilient Overlay Multicast - Reference implementation of Nemo for resilient overlay multicast.
- NUPastry - Resilient DHT - Reference implementation of NUPastry, a resilient distributed hash table (DHT).
- NUScribe - Resilient DHT-based multicast - Reference implementation of NUScribe and a work-in-progress version of NUSplitStreaming providing many of the proposed SplitStream features.
Related Projects