Distributed algorithms for multicast path setup in data networks
F. Bauer, Anujan Varma · Globecom · 2002
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 two centralized Steiner heuristics, the shortest path heuristic (SPH) and the Kruskal-based 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, our algorithm's competitiveness in almost all cases was within 10 percent of the best solution found by any of the Steiner heuristics considered, including both centralized and distributed algorithms.
Cited by 16 works. doi:10.1109/glocom.1995.502627
Authors
References
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- An approximate solution for the Steiner problem in graphs
- Another adaptive distributed shortest path algorithm
- Steiner problem in networks: A survey
- Steiner problem in networks: a survey
- Routing to Multiple Destinations in Computer Networks
- Steiner tree problems
- Steiner's problem in graphs: heuristic methods
- Degree-constrained multicasting in point-to-point networks
- Path-distance heuristics for the Steiner problem in undirected networks