Research On Algorithms For Aggregated Multicast

Recently, with the expansion of the Internet stream media and video-on-demand, the IP multicast technology has developped rapidly. IP multicast is a mechanism which can supports multi-point communication efficiently. It 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 IP multicast resource-efficient in delivering data to a group of members simultaneously and scalable in supporting very large multicast groups. So IP multicast is the important basis of high-bandwidth and shared Internet applications,such as stream media and video conference.However, a multicast distribution tree requires all the tree nodes to maintain per-group forwarding state,so when there are large numbers of multicast groups in the network, IP multicast suffers from many problems: The number of forwarding states obviously increases with the growth of the number of groups. The increasing growth of the forwarding states requires the growth of memory of the router. Meanwhile, since the forwarding of each group takes time to search address,the cost of CPU will augment and the forwarding process will slow down. Therefore, when there are a large number of simultaneous multicast sessions, the state information and control information will be too great to deal with on time. The state scalability problem has restricted the application of scalable multicast.To solve the problem of scalability, a novel approach called aggregated multicast has been proposed,which is based on the feature of actual networks. Its main idea is to broaden the demands of saving bandwidth, and to enable many multicast groups to share a multicast distributing tree.The tree nodes maintain only the state of the tree, instead of every group. In this way, the number of forwarding states decreases accordingly and the performance of network is improved. The key of aggregated multicast is how to find trees with minimal number, enabling these trees to cover all the groups. Aggregated Multicast can actually be attributed to minimal set cover problem, which is an NP-complete problem. The conventional way to solve aggregated multicast problem is Greedy Algorithm. Greedy algorithm is a local optimal algorithm having its limitation. The aggregated effect of this algorithm is not ideal.To solve the problem of how to select aggregated multicast trees,this paper presents Lagrange Relaxation Algorithm,Genetic Algorithm and Immune Algorithm.The basic idea of Lagrange Relaxation Algorithm is to combine the constraint conditions that make the problem hard into objective function, which is kept linear to facilitate the solution. It can dynamically adjust Lagrange multiplier, making it possible for the solution that is found to be close to global optimal solution.Genetic Algorithm is a kind of intelligent search algorithm which is premised on the evolutionary ideas of natural selection and "survival of the fitness". Individuals which are more successful in adapting to their environment will have a better chance of surviving and reproducing, whilst individuals which are less fit will be eliminated. By this way,the best individual will come into being.Genetic Algorithm is an effective global optimal searching algorithm.Immune Algorithm is a kind of intelligent search algorithm that uses biology immune system for reference.It can induct the evolution of specy with prior knowledge.In this way,it can get hypo- global optimal solution from a huge research space by creating antigen of different antigen.The results of simulation under the same network topology and multicast groups indicate that these three algorithms are better than the conventional greedy algorithm in improving aggregation degree and reducing multicast forward states.