A QoS Multicast Routing Based On Genetic Algorithm

With the rapid development in the broadband IP technology, there are more and more multimedia application in the Internet, such as video meeting. On the one hand, these new services require the support of multicast communication to reduce the traffic in the network. On the other hand, there must be a QoS (Quality of Service) guaranteed mechanism for these real-time services.The QoS multicast routing is searching the paths for transmission packets to all members in a multicast group with QoS constrained. It is very important for QoS multicast routing in broadband IP network so that an efficient QoS multicast routing algorithm is the key for development the broadband services. Unfortunately, the problem of finding multicast routing with QoS constrained is a NP-complete problem. So we can not solve the problem with the classical Shortest Path First algorithms such as Bellman-Ford and Dijstra. Thus, most previous researchers have focused on developing heuristic algorithms to solve the problem. However, these heuristic algorithms have high computation complexity so they are not fit in practicality.In this paper, we presented a QoS multicast routing algorithm based on Genetic Algorithm to solve the problem. Genetic algorithm is a new algorithm to solve an optimization problem. Based on natural selection, it executes three same and simple genetic operators: selection, crossover and mutation. Under the leading of fitness value, it makes an efficient searching in complex spaces until acquiring the best result. There are three genetic operators : selection, crossover and mutation.Selection and crossover complete a majority of searching, and mutation improves the ability of approaching the best result.In this Algorithm, we represent the chromosomes of the multicast tree by tree structure coding. In the design of crossover, we first merge two parent trees to a graph, and then create a multicast tree from the graph. Based on the method, the algorithm have a good performance of crossover. Our simulation results show that the proposed algorithm is able to find the result with fast speed.In the end of this paper, we analyzed the performance of the algorithm and considered the genetic algorithm as a good prospect in soluting the QoS multicast routing problem.