03/01/1995 09:00 AM
Computer Engineering
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 SPH and 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 quality of the solutions produced by both of our algorithms were on the average 25~percent better in comparison to those produced by the pruned spanning-tree approach. In addition, the quality of solution found by our algorithms in almost all cases was within 10% of the best solution found by any of the Steiner heuristics considered, including both centralized or 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.
