Distributed algorithms for multicast path setup in data networks
F. Bauer, Anujan Varma · IEEE/ACM Transactions on Networking · 1996
Establishing a multicast tree in a point-to-point network of switch nodes, such as a wide-area asynchronous transfer mode (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 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 that 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% better in comparison to that of the pruned spanning-tree approach. In addition, the competitiveness of our algorithms was, in almost all cases, within 10% 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.
Cited by 129 works. doi:10.1109/90.490746
Authors
References
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Routing of multipoint connections
- On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem
- 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
- How bad is naive multicast routing?