Research On QoS Constrained Multicast Routing Algorithm

The development of communication network requires that current network not only provides conventional best effort transfer service, but also some real-time multimedia services with QoS guarantee. It makes QoS multicast routing become one of key technique in network multimedia information transmission. Multicast routing algorithms are used to compute multicast trees that satisfy the needs of QoS. The problem in search of multicast routing with many QoS constraints is a NP-complete problem.A few methods for QoS multicast routing problem were presented such as heuristic algorithm, genetic algorithm (GA), ant algorithm and simulated annealing algorithm etc.. But there are some faults such as lack of local search ability, premature convergence and random walking etc. in their algorithms.Aiming to those shortage, a new genetic simulated annealing algorithm is presented for QoS multicast routing. It combines genetic algorithm and simulated annealing algorithm adequately. Both the advantages in GA and SA can be held in this genetic simulated annealing algorithm. The chromosomes of the multicast tree are represented by tree structure coding to save the time of conversion between encoding space and solution space. Graft spanning tree method is presented and used to make sure that every chromosome in initial population is reasonable multicast tree without loops. Then the crossover operator and simulated annealing mutation operator are designed. The adaptive crossover probability is adopted to improve the evolutionary efficiency.A method for dynamic QoS multicast routing based on routing rebuilding is presented. That includes the method of node deleting and node adding. The process of routing rebuilding is designed. The rebuilding scale is controlled by calculating accumulating damage and adjusting the weight of accumulating damage so that the effect to other multicast members by routing rebuilding can be acceptable and the equilibrium can be reached among optimization, calculating time and complexity.Salama network topology random generation algorithm is researched in this paper. A new algorithm is presented based on k-means clustering. A few simulation experiments have been done based on different network topologies generated by this algorithm randomly. The convergence performance is verified by the routing request success ratio. The comparison of cost performance scale is shown in different network. The simulation results show that this method has better performance and the problem of least-cost QoS multicast routing is solved effectively.