On multicast path finding algorithms

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.