A modified implementation of bounded shortest multicast algorithm for constrained multicast routing

Constrained minimum Steiner tree (CMST) problem is a key issue in multicast routing with quality of service (QoS) support. Many heuristics have been developed to solve this NP-complete problem. The bounded shortest multicast algorithm (BSMA) has been proved to be able to find solutions of very low cost with reasonable computation time. As such, it is still being widely used as a benchmark to evaluate newly proposed algorithms. In this paper, we proposed a new algorithm to construct the initial feasible solution for the BSMA algorithm. Simulations demonstrate that the modified implementation of BSMA based on this algorithm runs much faster and can find solutions with even lower costs than the best implementation of BSMA.