Aggregated Multicast Optimization Algorithm Research Based On Ant Colony Algorithm

With the rapid development of the INTERNET, many large scale multi-user applications are emerged, such as video conference, remote education, distributed interactive simulation. The emergence of these applications has brought a sharp bandwidth consumption and network congestion and so on. IP multicast is an important mechanism which can support these applications efficiently.In traditional IP multicast, data for a given group is forwarded through a tree structure covering the members of this group. The on-tree routers must maintain a per-group forwarding state. When there are large numbers of multicast groups in the network, large forwarding tables induce large memory requirements and slow down the address look-up process. Moreover, maintaining multicast trees requires an exchange of control messages causing an important overhead. Hence, the network performance will be tremendously degraded. This issue is referred to as multicast state scalability problem. The state scalability problem has restricted the application of scalable multicast.Aggregated Multicast is a recent approach proposed by the UCLA network laboratory. In this approach, multiple groups share the same aggregated tree within a domain. With multicast tree aggregation, fewer trees are maintained which amounts to reduce both the number of forwarding states in routers and the overhead induced by control messages. The core idea of Aggregated Multicast is to minimize the number of multicast trees without violating a given bandwidth waste threshold, enabling these trees to cover all the groups. The traditional Aggregated Multicast was divided the problem into three sub-problems, namely, candidate tree generation, tree selection and group-to-tree mapping. The tree selection is attributed to minimal set cover problem, which is an NP-complete problem.In this paper, two different algorithms are proposed to solve the forwarding states problem of multicast after achieving extensive and intensive research on the area of traditional aggregated model of multicast:one scheme is Ant Colony Optimization for Aggregated Multicast the other is Clustering for Aggregated Multicast by Ant Colony Optimization.1. Traditional aggregated multicast algorithms are easy to converge to the local optimal solution and could not reach ideal aggregation performance. Aiming at that problem, Ant Colony Optimization for Aggregated Multicast is proposed, which provides appropriate transformation on set-covering problem, and evolves aggregation performance to global optimal solution by using the positive-feedback generated by the self-organized and distributed cooperation of ACO.Simulation results demonstrate that compared to the local optimal solution gained by traditional Greedy Algorithm and approximate optimal solution gained by Lagrange Relaxation, the Ant Colony Optimization for Aggregated Multicast achieves distinct advantage on criteria such as aggregation degree and state reduction ratio.2. When in the condition of large scale network topology or high bandwidth waste bandwidth, the number of expandable links are greatly increased, and the time complexity of traditional aggregated multicast algorithms grows relatively. Clustering for Aggregated Multicast by Ant Colony Optimization is a newly proposed solution, which is based on a new model of constrained clustering, combines aggregated multicast with ant colony optimization, and optimizes clustering performance for aggregated multicast receiving the comprehensive effects of different variables and parameters.Simulation results demonstrate that with large number of expandable links, Clustering for Aggregated Multicast by Ant Colony Optimization has obviously advantage in program execution time compared to traditional algorithm.