Distributed Algorithms for Multicast Path
in Data Networks
August 16, 1995
Computer Engineering Department
University of California
Santa Cruz, CA 95064
Establishing a multicast tree in a point-to-point network of switch nodes, such as a wide-area ATM network, can be modeled as the NP-complete Steiner problem in networks. In this paper, we introduce and evaluate two distributed algorithms for finding multicast trees in point-to-point data networks. These algorithms are based on the centralized Steiner heuristics, the shortest path heuristic (SPH) and the Kruskalbased shortest path heuristic (K-SPH), and have the advantage that only the multicast members and nodes in the neighborhood of the multicast tree need to participate in the execution of the algorithm. We compare our algorithms by simulation against a baseline algorithm, the pruned minimum spanning-tree heuristic, which is the basis of many previously published algorithms for finding multicast trees. Our results show that the competitiveness (the ratio of the sum of the heuristic tree's edge weights to that of the best solution found) of both of our algorithms was on the average 25 percent better in comparison to those produced by the pruned spanning-tree approach. In addition, the competitiveness of our algorithms was, in almost all cases, within 10 percent of the best solution found by any of the Steiner heuristics considered, including both centralized and distributed algorithms. Limiting the execution of the algorithm to a subset of the nodes in the network results in an increase in convergence time over the pruned spanning-tree approach, but this overhead can be reduced by careful implementation.
Keywords: Multicasting, Steiner problem in networks, Distributed algorithms.
This research is supported by the Advanced Research Projects Agency (ARPA) under Contract No. F19628-93-C- 0175 and by the NSF Young Investigator Award No. MIP-9257103. This paper was presented in part at GLOBECOM '95, Singapore, November 1995.