Research On Optimization Model And Algorithm For Aggregated Multicast

With the rapid development of Internet, there are more and more distributed applications involving group communications in a network. As a main technology to support group communication, the traditional IP (Internet Protocol) multicast scheme requires a network to set up and maintain a delivery tree for a multicast group (or even for a source of a multicast group), and each on-tree router needs to maintain a multicast forwarding state for this multicast group (or per source of this group). The number of forwarding states in a router increases as there are more concurrent multicast groups in a network, and this increase is translated into more memory usage in a router and more look-up time when forwarding a multicast packet. At the same time, forwarding states of a multicast group are set up and maintained through exchanging control messages periodically among routers, and more multicast groups are translated into more usage of network bandwidth. The increase of both forwarding states and control messages slows down the forwarding process and degrades the performance of a whole network. This is referred to as the state scalability problem. Particularly, when QoS (Quality of Service) service is considered, this state scalability problem is exacerbated, because not only more memory is required for the QoS parameters, but several multicast trees might be established for one multicast group due to different QoS requirements of different group members. So, the large scale deployment of the traditional IP multicast technology faces the challenge of state scalability problem.The Internet is a hierarchical network, where multiple user networks are connected to a region network, and multiple region networks are connected by a backbone network. Data from multiple user networks are transferred through a backbone network, and multicast forwarding states are maintained in the backbone network for multicast groups which pass through it. So the state scalability problem is more exacerbated in a backbone network. Research on the state scalability problem, especially research on the state scalability problem in a backbone network, has important scientific and practical meaning. The aggregated multicast (AM), proposed in recent years, is a promising technology to resolve the state scalability problem which targets on a backbone network. The AM technology forces multiple groups to share one multicast tree (aggregated tree) to reduce the number of multicast trees. By this way the number of both multicast forwarding states and control messages are reduced simultaneously. In this kind of systems, a shared aggregated tree must cover all the multicast groups which transfer data using it, and the tree is larger than these groups generally, so this wastes extra bandwidth. The AM technology is a tradeoff between reduction of multicast trees and extra bandwidth waste. This is a multiple objective optimization problem, and has two optimization directions: given the threshold of bandwidth waste rate, minimize the number of aggregated trees (which is called the aggregated tree optimization problem, or the aggregated multicast problem constrained by bandwidth waste rate); given the number of aggregated trees, minimize the bandwidth waste rate (which is called the bandwidth optimization problem, or the aggregated multicast problem constrained by the number of aggregated trees).Searching for optimal solutions for these two problems has an important role in deployment of the AM technology, and these two problems are both NPC problems. Designing some efficient algorithms for them and improving the optimization performance of the algorithms are the main focuses of this dissert.Firstly, the aggregated tree optimization problem (ATOP) is described and defined based on the minimum grouping model. The minimum grouping problem is a class of some concrete problems such as the bin packing problem, the graph coloring problem, and the minimum clique cover problem. When some heuristic algorithms are used to solve these problems, these algorithms always gain some local optimal solutions, which cannot satisfy with the practical requirements. For gaining more optimal solutions, some meta-heuristic algorithms are proposed in recent years, and the ant colony optimization (ACO) algorithm gains more challenging solutions when solving the minimum grouping problems. So some efficient ACO algorithms were designed to solve the ATOP problem. A hierarchical method was used in designing ACO algorithms:firstly the minimum grouping characteristics of the ATOP were analyzed, especially there are always multiple optimal solutions in an iteration process. To accumulate effective acknowledges for guiding the later iteration processes, the principals of designing fitness functions between two multicast groups were proposed, and some new multiple layer pheromone update rules were proposed based on them. At the same time, some new terminal conditions were proposed according to the randomized essence of ACO algorithms. Secondly based on these proposed principals, the bin packing model and the minimum clique cover model were used to analyze the aggregation condition of ATOP. Corresponding heuristic information were proposed based on these two models, and the concrete definitions of fitness function and pheromone update rules were proposed respectively. The bin packing model and the minimum clique cover model describe the ATOP from different viewpoints, and reflect its different characteristics. Simulation results show that the designing principals of fitness function and corresponding multiple layer pheromone update rules can improve the optimization performance of ACO algorithms of ATOP significantly. Compared with existing heuristic algorithms, the proposed algorithms have more optimization performance, and are more suitable to the scenarios which have larger bandwidth waste rate or larger network scale because candidate trees are not needed to be pre-computed.Secondly, the bandwidth optimization problem (BOP) was defined based on the grouping model, and an ACO algorithm was proposed based on multicast tree similarity. Through analyzing the characteristics of BOP, the BOP was divided into two stages, the initial tree selection stage and the tree aggregation stage. Based on the definition of similarity between multicast trees (groups) and the asymmetric characteristic of similarity, the heuristic information of the initial tree selection stage and the tree aggregation stage were proposed according to the combination of similarity and similarity rank. At the same time, two different forms of pheromone (itself and its inverse) and similarity (itself and its inverse) were used in different stages. New pheromone update rules were designed according to the essence of BOP. Simulation results show that the proposed ACO algorithm has higher optimization performance than heuristic algorithms, and compared with general ACO algorithms the proposed algorithm improves the convergence time of the algorithm, which implies the effectiveness of the proposed heuristic information.Finally, some future works such as designing dynamic algorithms and designing algorithms with QoS constraints for the aggregated multicast, are discussed.