GA-Based Algorithm For QoS Based Multicast Routing

As a result of the emergence of many kinds of high-speed communication systems and increasing demand of distributed multimedia applications, efficient and effective support of quality of service (QoS) has become more and more essential. Many service models and mechanisms have been put forward by IETF to meeting QoS requirement, multicast service is a key one of them and is becoming a key requirement of computer network supporting multimedia application.Multicasting consists of concurrently sending the same information from a source to a subset of all possible destinations in a computer network. Multicast utilizes a tree delivery structure, on which data packets are duplicated only at fork nodes and are forwarded only once over each link. This approach makes multicast resource-efficient in delivering data to a group of member simultaneously and can scale well to support very large multicast group. This dissertation focuses on the algorithms to construct low cost multicast routing tree with QoS requirements.This dissertation analyses the principle of multicast and multicast routing technology. Generally multicast routing algorithms use heuristic technology, but the simulation result has shown that most of the proposed heuristic algorithm either work too slowly or cannot compute delay-constrained multicast trees with low costs.For this reason, methods based on genetic computation may be of great help. In this dissertation, we study the bandwidth, delay, delay jitter, and packet loss constrained least-cost multicast routing problem, and propose a new heuristic genetic algorithm. The algorithm has the following characteristics:The preprocessing, by which we can greatly simplifies the QoS multicast routing problem, optimizes the performance of the genetic algorithm and decreases the search space;The tree structure coding method, by which we can use any data structure of the tree to describe the chromosome structure, and omits the coding and decoding process;The heuristic crossover technique, it, in which QoS metrics are considered, can speeds up the algorithm convergence and delivers the good characteristics to the offspring.The instructional mutation operation. By which we can improve the performanceof the genetic algorithm because it is effective to convert the algorithm from a local optimal point into good state.Finally we conduct simulation studies to evaluate our algorithms and strategies and compare with other similar or related approaches, and we see improved or comparable performance in most cases.