Qos-based Multicast Routing Algorithm

Multicasting is a means of group communications. It is the most widely-used communication pattern in computer network .It requires information from a source to several destinations at the same time. As the core technique of high-speed network, routing has many research fields, for example, routing protocols, routing policy and routing algorithms etc. In this dissertation, we will concentrate on routing algorithms based on multicast tree which satisfy Quality of Service (QoS) requirement.There are two algorithms in this dissertation: Low-cost Short Path Tree and Hybrid Simulated annealing algorithm (SA) and Genetic Algorithm (GA).First, the dissertation mainly studies how to reduce the total cost of multicast tree. Based on some existing algorithms, through improving the search procedure, a new algorithm called ASLSPT(Low-cost short path tree based on All-paths Shared)for lower cost Short Path Tree is presented, which has better performance and lower complexity than Destination-Driven Short Path Tree (DDSP) algorithm. According to the basic idea of sharing of as many destination nodes as possible, the new algorithm adopts a new idea called full-paths shared to reduce the cost of the multicast tree. And it sets a collection to record adjacency nodes joined to the multicast tree.Intelligence techniques have recently become among the state of the art techniques in the domain of artificial intelligence design. Because of giving the high potential in dealing with large structural and complex systems, the intelligence algorithm such as neural networks, genetic algorithm, and ant colony optimization, have attracted much interest. The appropriate integrations of these algorithms will make them very powerful and efficient. For this reason, this dissertation focuses on the QoS routing problem by using these intelligent techniques. The concrete content is Hybrid Simulated annealing algorithm (SA) and Genetic Algorithm (GA) Approach. In GA, the preprocessing is used to simplify the QoS multicast routing problem, we adopt the improved DFS and represent the chromosomes of the multicast tree by tree structure coding. In the design of crossover, we use the ASLSPT to create a child multicast tree.This dissertation designs a kind of effective network simulation environment referred to the Salama model, which used to confirm performance of the algorithms. After the simulation experiment and contrast, it proves that the ASLSPT algorithm and the GSAA algorithm are both efficient algorithms which the performance has a certain increase. They are both correct and effective multicast routing algorithms.