loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
24th IEEE International Conference on Distributed Computing Systems (ICDCS'04)
Overlay Multicast Trees of Minimal Delay
Hachioji, Tokyo, Japan
March 24-March 26
ISBN: 0-7695-2086-3
Anton Riabov, Columbia University
Zhen Liu, IBM T.J. Watson Research Center
Li Zhang, IBM T.J. Watson Research Center
Overlay multicast (or application-level multicast) has become an increasingly popular alternative to IP-supported multicast. End nodes participating in overlay multicast can form a directed tree rooted at the source using existing unicast links. For each receiving node there is always only one incoming link. Very often, nodes can support no more than a fixed number of outgoing links due to bandwidth constraints. In this paper, we describe an algorithm for constructing a multicast tree with the objective of minimizing the maximum communication delay (i.e. the longest path in the tree), while satisfying degree constraints at nodes. We show that the algorithm is a constant-factor approximation algorithm. We further prove that the algorithm is asymptotically optimal if the communicating nodes can be mapped into Euclidean space such that the nodes are uniformly distributed in a convex region. We evaluate the performance of the algorithm using randomly generated configurations of up to 5,000,000 nodes.
Citation:
Anton Riabov, Zhen Liu, Li Zhang, "Overlay Multicast Trees of Minimal Delay," icdcs, pp.654-661, 24th IEEE International Conference on Distributed Computing Systems (ICDCS'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.