Research On Multicast Routing Algorithm Using Ant Colony Optimization

With the high popularity of Internet and rapid development of multimedia communication technology, especially with the construction, research and pre-commercialization of next generation Internet (NGI), a variety of multimedia services, such as IPTV, video-on-demand (VoD), media streaming and distance learning, have greatly expanded and produced as many times as already existed huge network traffic. It is estimated by Cisco that the Internet traffic will double every two years between 2007 and 2012. This poses a serious challenge to the healthy development of Internet. Optimizing network bandwidth can satisfy the demand of ever increasing data traffic. IP multicast, designed to be suitable for one to many (or many to many) data transmission service, is one of the most efficient network bandwidth optimization approaches. IP multicast is a novel network architecture first proposed by Steve Deering, with which the source can send only one copy of the data to a group of receivers with multiplexing. In contrast to unicast, IP multicast can significantly reduce the network overload and lower the burden of the data source; therefore, it is one of the best solutions to multimedia group communication.Multicast and multicast routing always are two hot research topics in both academia and industry. In particular, in order to meet the QoS requirements of multimedia group communication, how to seek a simple, effective, and robust multiple QoS constrained multicast routing algorithm is a problem that researchers in network and communication areas are always endeavoring to work on but never get it solved. In December 2008, the project of pre-commercialization of China next generation Internet (CNGI) is launched, and in January 2010, the integration of telecommunication networks, cable TV networks and the Internet, is put on the agenda in the executive meeting of state council. All these will have a positive influence on the deployment and application of multimedia group communication services such as IPTV, video conferencing and distance learning, and will also boost the development of these multimedia applications. As a result, IP multicast and QoS have become two urgent requirements for the forthcoming next generation multimedia services. Therefore, it is both of theoretical significance and realistic sense to research on multicast routing problems with new intelligent computational algorithms.The multi-constrained multicast routing algorithm is mathematically considered as a constrained Steiner tree problem, which is proven to be NP-Complete and can not get solved in polynomial time. Many research institutions and communities domestic and abroad have thoroughly studied this problem and proposed many approximation algorithms, such as BSMA, DMVA and SPH-R. However, these algorithms are so complicated that they have high computational complexity, and even worse, they can not guarantee the finding of the global optimal solutions in real-world networks. With the rise of intelligent computational algorithms, researchers have resorted intelligent computational algorithms, such as genetic algorithm, immune algorithm, to solve the constrained multicast routing algorithm. However, these algorithms usually do not converge at a satisfactory rate, and they do not converge to the global optimal solution in many situations.The ant colony algorithm is a new simulated evolutionary algorithm which was firstly introduced by Italian researcher Marco Dorigo in his doctoral thesis and was successfully applied to solve the traveling salesman problem (TSP). The ant colony algorithm solves the optimization problem by using the collaboration between the individuals in the population, so that it will be able to overcome the difficulties that traditional methods can not, or be hard to, solve the optimization problems. Its basic methodology is that the ant chooses a path in proportion to the path's pheromone intensity when it is searching the food. As a result, for a path, the more ants select the path, the stronger the path's pheromone intensity will be, and in turn, the stronger path's pheromone intensity will attract more ants to select this path, thus a positive feedback mechanism is formed by which the ant can find the shortest path. In short, in contrast to other intelligent computational methods, the ant colony algorithm has many distinguished merits such as positive feedback, distributed computing and constructive greedy heuristic searching; therefore, the ant colony algorithm has been extensively used to solve the network routing optimization problem.With the increasing demand for multicast and network QoS by the distributed multimedia applications, it has become a hot research topic in current network and communication area that applies the ant colony algorithm to solve bandwidth, delay, packet loss rate and minimum cost constrained multicast routing problem.In this paper, we are engaged in proposing several novel multi-constrained multicast routing algorithms with ant colony optimization as our mathematical tool, including degree constrained multicast routing algorithm and multiple QoS constrained multicast routing algorithm. The main contributions of the thesis can be summarized as below:1) To solve the degree constrained multicast routing problem, we propose a novel tree based ant colony algorithm called NAH by utilizing its positive feedback mechanisms. The NAH algorithm first selects a link with a certain probability and adds it to the multicast subtree, and then it checks the degree constraint of the selected node. If the degree of the node is greater than the threshold, the ant will never select the links connected to that node again. Computer simulations show that compared with existed AH algorithm, the NAH algorithm can find the optimal solution within a shorter period; moreover, it can significantly reduce the spatial complexity. In particular, the space complexity of NAH algorithm is o(M x N), while that of AH algorithm is o(M×N×n).2) Combining cross entropy algorithm with ant colony algorithm, we design a new ant colony algorithm to solve multiple QoS constrained multicast routing problem. In the new algorithm, the multiple QoS constrained multicast routing problem is transformed into the mathematical model that can be solved by the cross entropy algorithm. After that, the procedures are presented how to apply cross entropy based ant colony algorithm to solve multiple QoS constrained multicast routing problem with the notion of ant agent. By combining ant colony algorithm with mathematically self-contained cross entropy algorithm, the quality of optimal solution is greatly improved because the randomness mechanism in the cross entropy algorithm guarantees the solution scale as well as the search scope for the solution. In addition, the new algorithm has advantages in computing speed and scalability over standard ant colony algorithm.3) As the ant colony algorithm converges with a slow speed in its initial phase, we propose a geographical awareness based ant colony algorithm which introduces geographical information into the standard ant colony algorithm. The ants in the new algorithm can make better path selection with the help of the incorporated geographical information. Then we present the notion of "orientation factor" by utilizing the concept of geographical awareness. Based on the notion of orientation factor, we propose an improved multiple QoS constrained multicast routing ant colony algorithm named MACA. The MACA algorithm builds the multicast tree using the receiver-driven approach, and it adds orientation factor into the path selection probability function which can make the ants move faster to the source by getting rid of the blindness in early path selection. Experimental results show that the MACA algorithm make great improvements in both convergence speed and computing time.