Max-min overlay multicast: Allocation and tree construction

Yi Cui, Yuan Xue, Klara Nahrstedt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Although initially proposed as the deployable alternative to IP multicast, overlay multicast actually offers us great flexibilities oa QoS-aware resource allocation for network applications. For example, in overlay multicast streaming, (1) the streaming rate of each client can be diversified to better accommodate network heterogeneity, through various end-to-ead streaming adaptation techniques; and (2) one can freely organize the overlay session by rearranging the multicast tree, for the purpose of better resource utilization and fairness among all clients. The goal of this paper, is to find the max-min rate allocation in overlay multicast, which is pareto-optimal in terms of network resource utilization, and max-min fair. We approach this goal in two steps. First, we present a distributed algorithm, which is able to return the max-min rate allocation for any given overlay multicast tree. Second, we study the problem of finding the optimal tree, whose max-min rate allocation is optimal among all trees. After proving its NP-hardness, we propose a heuristic algorithm of overlay multicast tree construction. A variation of the heuristic is also designed to handle the dynamic client join/departure. Both of them have approximation bound of 1/2 to the optimal value. Experimental results show that they achieve high average throughput, almost saturate link utilization, and consistent nun-favorability.

Original languageEnglish (US)
Title of host publication2004 Twelfth IEEE International Workshop on Quality of Service, IWQoS 2004
Pages221-231
Number of pages11
StatePublished - Sep 29 2004
Event2004 Twelfth IEEE International Workshop on Quality of Service, IWQoS 2004 - Montreal, Ont., Canada
Duration: Jun 7 2004Jun 9 2004

Publication series

Name2004 Twelfth IEEE International Workshop on Quality of Service, IWQoS 2004

Other

Other2004 Twelfth IEEE International Workshop on Quality of Service, IWQoS 2004
CountryCanada
CityMontreal, Ont.
Period6/7/046/9/04

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Max-min overlay multicast: Allocation and tree construction'. Together they form a unique fingerprint.

  • Cite this

    Cui, Y., Xue, Y., & Nahrstedt, K. (2004). Max-min overlay multicast: Allocation and tree construction. In 2004 Twelfth IEEE International Workshop on Quality of Service, IWQoS 2004 (pp. 221-231). (2004 Twelfth IEEE International Workshop on Quality of Service, IWQoS 2004).