TSDLMRA: an efficient multicast routing algorithm based on Tabu search
As a NP-Complete problem, multicast routing with delay constraint is a research difficulty in routing problem. Tabu Search is artificial intelligence algorithm, which is an extension of local search algorithm and has simple realization and well properties. In this paper, an efficient algorithm based on Tabu Search for Delay-Constrained Low-Cost Multicast Routing is proposed to solve delay-constrained multicast routing problem. This problem is known to be NP-Complete. The proposed heuristic algorithm makes use of the characteristics of flexible memory function and tabu rule in TS algorithm, generates neighborhood structure base on paths-switching operations, and finds multicast tree satisfying constraint. A large number of simulations demonstrate that the algorithm performs excellent performance of cost, rapid convergence and stable performance of delay.
multicast routing tabu search np-complete delay constrained constrained steiner tree