An effective candidate list strategy for Tabu Search based QoS multicast routing

Multicast routing with quality-of-service constraints is one of the most important problems in computer networks as constrained Steiner tree problem. It is a well-known NP-complete problem, which has various real-time multimedia applications in high-speed networks. In this paper, we propose algorithms to solve the bandwidth-delay-constrained least-cost multicast routing problem based on Tabu search. The main feature of proposed TS-based algorithms is use of an effective candidate list strategy. By the use of this strategy not only search speed but also solution quality will be improved. We evaluate the performance and efficiency of the proposed algorithms on a variety of random generated networks. Evaluation results indicate that the proposed algorithms overcome the other existing short-term memory version of TS-based algorithms and heuristics.