Reliable and Efficient Multicast in Overlay Networks

As a fundamental model of communication, multicast has long been treated as a network primitive, which leads to IP being viewed as the natural protocol layer for implementing multicast related functionality. However, after more than a decade's efforts from both the research community and industry, IP multicast is still plagued with concerns about its scaling and management limitations. This fact has led to considerable interest in alternative approaches that are implemented at the application layer, using only end-systems. In this new approach, participating hosts organize themselves into an overlay topology for data delivery, and all multicast-related functionality is implemented at the end systems instead of at the routers. This shifting of multicast support from routers to end systems has proven to be able to solve most problems associated with IP multicast, as is evident from the great success of some large-scale media streaming applications running on the current Internet. This thesis addresses two of the major technical challenges presented by overlay multicast: reliability and efficiency. In many application scenali.os, the end systems are non-dedicated machines and are thus dynamic in nature, leading to highly unreliable data delivery in the network. We consider this problem for two representative architectures of overlay multicast: application-specific overlays and Distributed Hash Table (DHT)-based overlays. For the first architecture, we focus on the tree overlay structure and propose a set ofnew algorithms that can significantly improve the reliability of data delivery, and validate it in the context of a media streaming application. For the DHT architecture, we present a stochastic analysis which not only sheds light on node lifetime characteristics in the multicast context, but also lends itself to th~ reliability analysis for general overlay based applications that involve persistent data transfer. The second theme of this thesis concerns the efficiency issues of overlay multicast, particularly those introduced by the 'anarchy' of overlay members. In the absence ofcentralized resource management, end systems are likely to behave in a self-interested way. The lack of motivation to contribute resources, and the potential unfairness of Quality ofService (QoS) among overlay members, therefore may lead to resource shortage which impairs system perfonnance. Taking an economic perspective to this problem, we develop bidding-based incentive and service differentiation mechanisms that can stimulate overlay members to contribute their resources, and that are strategy-proof, in the sense that individuals cannot take advantage of others without QoS penalty. We design mechanisms to stimulate contribution within single overlays as well as across multiple co-existing overlays, and confinn their efficacy through extensive simulations.EThOS - Electronic Theses Online ServiceGBUnited Kingdo