Addressing the Limitations of Tree-Based Approaches to High-Bandwidth Streaming Multicast.

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. This dissertation 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. 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 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 of 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 is 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 high 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, since bandwidth decreases monotonically 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, conventional trees challenge the expectation of cooperating systems wherein every peer contributes resources in exchange for using the common service. While simply splitting content among all participants may ensure balanced load distribution in mostly homogeneous environment, this would come at a high cost in terms of performance in heterogeneous dynamic environments. Our thesis is that 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 propose 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, which are alternative leaders that help avoid single-node dependencies and provide alternative paths for data forwarding. We propose to address the bandwidth constraints of conventional trees by importing Leiserson's fat-trees from parallel computing into overlay networks. We posit that overlays composed of performance-centric, balanced trees enable fair resource contributions among peers without impacting overall system performance. We provide 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...