On multicast path finding algorithms

1 January 1991

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 1274-1283 vol.3
https://doi.org/10.1109/infcom.1991.147651

Abstract

Three multicast path-finding algorithms for networks with directed links are designed and implemented: an optimal algorithm based on the dynamic programming technique, a heuristic algorithm with the assumption that all vertices have the multicast capability, and a heuristic algorithm for networks where some vertices do not have the multicast capability. Computation results show that the heuristic algorithms can find multicast paths whose costs are close to optimal and can operate with reasonable response time for large networks. Applications of these path-finding algorithms to set up multipoint connections for broadband multimedia multiparty services are discussed.

Keywords

This publication has 12 references indexed in Scilit:

Multicast routing in datagram internetworks and extended LANs
ACM Transactions on Computer Systems, 1990
Multicast connection-oriented packet switching networks
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1990
A second‐generation BISDN prototype
International Journal of Communication Systems, 1988
Routing of multipoint connections
IEEE Journal on Selected Areas in Communications, 1988
Steiner problem in networks: A survey
Networks, 1987
On finding steiner vertices
Networks, 1986
Reducibility among Combinatorial Problems
Published by Springer Nature ,1972
The steiner problem in graphs
Networks, 1971
A note on two problems in connexion with graphs
Numerische Mathematik, 1959
On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem
Proceedings of the American Mathematical Society, 1956

Cited by 52 articles