The Study Of Multicast Routing Algorithm And Simulation Based On Delay Constraint

With the development of Internet and Network skill, now, the Network is developing faster than any other time it is.However, as the Network Size and the amount of information extend, the Network has become very crowded, and multicast appears at this time. The multicast is an effective way to support multi-point communications, which can make one or several data sources send data to given multicast groups to save network resources. Therefore, multicast can handle lots of multimedia applications such as interactive games, IP telephone, video on demand, distance education, which need a lot of resources. The core of multicast is the way to solve the multicast routing problem,and for the way to solve the delay constraint multicast routing is very important to the real-time business in the Network,it has caused widespread concern. The main objective of the problem is to establish a multicast tree that can cover all multicast group members and ensure the end to end propagation delay. According to the number of nodes that send data, the multicast routing problem with delay constraint can be divided into two problems:the one-to-many delay constraint multicast routing problem and the many-to-many delay constraint multicast routing problem.This paper not only shows us these two problems, but gives us two algorithms for each problem, and both of them come from the ant colony algorithm. Among the many swarm intelligence algorithms, the ant colony algorithm for its robustness, flexibility, robustness and rich in constructive ideas is highly respected. Besides, for its positive feedback and synergy, the ant colony algorithm can be used in distributed conditions, and its implicit parallelism makes it more suitable for the design of distributed algorithms. Therefore, both of the algorithms in this paper borrow some useful ideas from the ant colony algorithm, and improve it to fit for the problem.The characteristic of the one-to-many delay constraint multicast routing problem is that there is only one node sending data in the whole multicast communication process. The problem often comes down to the constraint Steiner tree with minimum cost, and it can be done by solving the problem of the Steiner tree. Since the problem has been proved to be a NP-Complete problem, it can't be solved within polynomial time. In recent years, there are a large number of excellent algorithms, and it makes people know more and more details about NP-Complete problems. To solve the multicast routing problem better, predecessors have made a lot of centralized algorithms. However, in the real network environment, it's hard to use centralized algorithms.There is a dynamic optimizing distributed multicast routing algorithm in chapter 4. The idea of the algorithm to solve the multicast routing problem comes from the ant colony algorithm. Since an indirect communication can be made between different generations of ants by pheromone that can reflect environmental changes, the algorithm can make changes according to the environmental changes.Simulation experiments done on the network topologies generated by the topology generator show that the algorithm is able to find a delay constrained tree with minimum cost visa evolution of generation of ants.With the development of multimedia technology, there are more and more real-time multicast applications including several source nodes and destination nodes such as interactive games. The multicast routing problem of these applications is the delay constraint many-to-many multicast routing problem. To build one or several trees including all of the source nodes and destination nodes can solve the problem, so that all of the source nodes can use the same tree to send data. This form of multicast tree is named shared tree. The benefit of shared tree is that routers on the tree need to save the information of the multicast members. Therefore, routers on the shared tree save less information than those on the source-rooted tree do and the cost of the shared tree is less than that of the source-rooted tree. To establish a shared tree, there is a key and difficult problem named center selection that we have to solve. Predecessors studying this problem are often limited to single center in the selection. But the shared tree with single center is always poor delay performance, so more and more researchers begin to study the shared tree with multi-centers. There is a delay constraint multicast routing algorithm based on multi-centers in chapter 5, and the focus of the algorithm is the part of center selection. At last, the simulation results show that we can use the shared tree with multi-centers to reduce the multicast data transmission delay without increasing the cost of the tree and the number of centers.