Overlay multicast trees of minimal delay

Abstract

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.