Research Of Multicast Routing Algorithms With QoS Constraint Based On Simulated Annealing

With fast development of network technologies,increase of network bandwidth and processing power makes the network provide more multimedia applications,and also makes the multicast communication that supports "one-to-many" or "many-to-many" become a necessary mode of multimedia services.A fundamental issue in multicast communication is how to determine an efficient multicast routing, and finding simple,effective and robust multicast routing algorithms.This is unsolved problem in network fields.In addition,many distributed multimedia applications have various demands on delay,delay variation,bandwidth and packet loss,which requires current network to transmit real-time multimedia information with these quality-of-service(QoS)constraints.So,as an indispensable component in a QoS-centric network architecture,research on multicast routing algorithms based on IP QoS constraint becomes an important part and hotspot issue of network research fields.This paper researches the structure,typical service model and mechanism of QoS based on network,and introduces the key technology about it;then classifies the multicast routing algorithms with QoS constraints which have been put forward.By analyzing the simulated annealing algorithm and importing the conception of paths-switching,the paper presents a kind of improved simulated annealing algorithm: SAD_DVMA.The simulative result illustrates SAD_DVMA is better than traditional algorithm in solving the least cost multicast routing problem with delay and delay variation constraint.Generally,the main achievements in this paper are as follows:(1)Concentrates on researching multicast routing algorithms with QoS constraints,proposes several simple,effective and practical QoS multicast routing heuristic algorithm to solve some classical multicast routing problems with NP difficulty;(2)Apply the simulated annealing to multicast routing,and propose a multicast routing algorithm(SAD_DVMA)based on simulated annealing to solve delay and delay variation constrained least-cost multicast routing problem.To avoid enlargement of search area and increase of computing time,SAD_DVMA uses "paths-switching" strategy,which constructs neighbor set in the range of feasible solutions according to the relationship between delay and delay variation;(3)Simulations demonstrate that the algorithm has characteristics of feasibility, stability and rapid convergence,and it can effectively construct multicast tree with lower cost according to QoS request,and has better real-time property.