Nemo -- Resilient Streaming Overlay Multicast

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

Collaborators

Publications

Resources

  • The Nixes Tool Set - A set of bash scripts to install, maintain, control and monitor applications on PlanetLab.
  • Nemo Maven documentation pages
  • We ask that you create an account on our website to access the software. Once you have created an account and logged in, download links will appear at the bottom of this page. Any paper that uses this software must refer to the publication above and you must send us a copy of the paper upon publication.

Related Projects