The Research On Multicast Routing Algorithm Based On Simulated Annealing And Tabu Search

In today's Internet and wide area networks, QoS multicast routing becomes of vital importance. This is due to the fact that Internet is rapidly becoming the main carrier of new multimedia applications and it is expected to play a significant role in the future deployment of these applications. The multimedia applications are characterized by resource intensive, having stringent quality of service (QoS), and involve more than two participants in many cases. Any multicast routing algorithm must satisfy these requirements. The objective of all problems we study is to optimize the utilization of the network resources without violating the QoS requirements of real-time applications.As a NP-Complete problem, delay-constrained multicast routing is a research difficulty in routing problem. In this thesis, a QoS multicast routing algorithm SAQMR based on simulated annealing is proposed for this problem. Simulated annealing is artificial intelligence algorithm, which is an extension of local search algorithm and has simple realization and well properties. A large number of simulations the cost of multicast trees generated by SAQMR is comparable to that of BSMA, which is the best heuristic for delay-constrained multicast routing problem, but the execution time is far less than that of BSMA.Apart from end-to-end delay, delay variation is also an important QoS parameter. Delay and delay variation constrained multicast routing can be reduced to the constrained minimum Steiner tree problem in graphs, which is also NP-Complete. we proposed an efficient algorithm based on Tabu Search is to tackle this problem. The proposed heuristic algorithm makes use of the characteristics of flexible memory function and tabu rule in TS algorithm, and finds multicast tree satisfying both delay and delay variation constraints.Finally, we proposed a Weighted Selection Function-Based Application Layer Multicast Algorithm. Experimental results show that it can reduce the bandwidth consumed by multicast sessions and at the same time achieve low latencies.