loading...
Overlay Multicast Trees of Minimal Delay
Hachioji, Tokyo, Japan March 24-March 26
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDCS.2004.128163324th IEEE International Conference on ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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.