Research And Application Of Ant Colong Algorithm In Aggregated Multicast Optimization

With the development of Internet, IPV6 and epc system network have expanded network nodes to all the comers of our life and the communication among many different nodes in the network could not get away from the support of multicast technology.In the traditional multicast, a multicast tree is established for every multicast group to distribute data packets. At the same time a multicast address is assigned to this established multicast tree. Every on-tree router needs to maintain the multicast forwarding stated. When there are a large amount of concurrent multicast groups in the network the corresponding multicast trees will increase. These multicast trees not only degrade the inquiry speed of multicast address, but also consume a lot of memories and CPU resources to maintain huge quantity of multicast state forwarding tables. Multicast groups change dynamically in the network and the multicast tree will renew when the group members join and leave. Therefore it is a big cost thing for the control and management of multicast trees. All the bad effects come from the multicast state scalability problem; it degrades the performance of the network and becomes an important bottle neck for the wide deployment of multicast application.Aggregated multicast is proposed by the network libratory of UCLA University in order to tackle multicast state scalability problem. Several multicast groups which have similar shaped original multicast tree share a single large multicast tree in aggregated multicast. It could reduce the number of multicast trees significantly in the network, decrease the amount of the forwarded multicast states, decline the consuming of resource and cut down the cost when maintain and manage the trees. The key idea of aggregated multicast is to establish the least aggregated multicast trees which could cover all multicast groups within the constraint of the given bandwidth wasted threshold. In the existed aggregated multicast optimization algorithms there are Greedy algorithm and Genetic algorithm, both of which have done great devotion to the development of aggregated multicast theory.This thesis proposes a kind of ant colony algorithm based on disturbance factor to reduce the number of multicast trees in the basis of the research on the existed aggregated multicast optimization algorithm. In order to speed up the convergence of ant colony algorithm the parallel computing model of ant colony algorithm is also proposed.1. The ant colony algorithm based on disturbance factor is the improvement of ant colony algorithm. In this algorithm every time one cycle is completed not only the pheromone in the optimal aggregated tree set is renewed but the pheromone in the random suboptimal aggregated tree set is also renewed. The introduction of disturbance factor (random suboptimal solution) could add the diversity of the solutions and prevent from falling into the morass of local optimal solutions prematurely.The simulation experiment shows ant colony algorithm surpasses Greedy algorithm in the performance. The heuristic information is too simple and the search solution space is narrow in the Greedy algorithm. However, it uses pheromone to mark the optimal solution in the ant colony algorithm and it takes more time to try, so it will get a better solution naturally.2. In order to improve the shortcoming of serial ant colony algorithm which have a slow convergence speed while solving the problem it is reformed to a parallel computing model. The key idea is to assign the task which could be executed concurrently to multi nodes in average. Through the cooperative computing between control nodes and slave nodes a satisfactory result is got at last.The simulation experiment shows that with the growing number of multicast groups, the cost of calculation time will become longer gradually. But parallel computing reduces much time of serial algorithm and parallel efficiency will go up too, the effect of parallel computing is obvious in a large scale aggregated multicast optimization.