An Improved Ant Colony Optimization Algorithm for Aggregated Multicast

IP multicast often has great scalability problem with the router to keep forwarding state for every multicast tree passing through it. An aggregated multicast technology were proposed by Jun-Hong Cui and others in order to solve this problem, which enables the multicast groups that can be integrated to share one distribution tree so that the multicast state can be reduced efficiently. But this is an NP-Complete problem. In this paper, we propose a new algorithm, combined ant colony optimization with the idea of minimal set cover to overcome this shortcoming. In this new algorithm, every candidate tree is assigned a value of cost. So the solution with smaller cost is selected if there are several best solutions with the same number of multicast trees. As the algorithm limits the value of bandwidth waste rate, which means the increasable number of nodes is limited, the algorithm almost always can be completed in polynomial time. And experiments show that this algorithm can achieve better optimization performance compared with greedy algorithm.