The Research Of Degree-Constrained Multicast Routing Algorithm

An information era is coming. Computer network technology has been growing explosively and the multicast technology has become a hot research topic. In order to implement an effective multicast communication, it's extremely essential to determine a multicast routing. Multicast routing algorithm research aims at obtaining a minimum cost multicast tree in a given network. This paper has investigated some multicast routing algorithms in detail. After comparing and analyzing some existing algorithms, this paper proposes two degree-constrained multicast routing algorithms according to the real network. 1. DCMST_on_GRASP Algorithm The algorithm is an iterative method which includes two phases in every iteration, namely, construction of an initial feasible solution phase and the local search phase. Construction of an initial degree-constrained multicast tree includes selecting randomly of a node from the destination set which haven't been in the partial multicast tree and another node from the partial multicast tree, computing their shortest path, adding the path to the partial tree, eliminating the potential free loop and inspecting whether some nodes break degree constraint. These operations have been done until all destination nodes are included in the multicast tree. The local search phase includes constructing firstly a neighbor tree of the initial multicast tree, comparing their cost, and then continually searching the neighborhood of the smaller one. Such procedures are done until it's impossible to gain a much smaller cost tree. Comparing the degree-constrained multicast trees produced in different iteration, the smallest one is the final solution gained by this algorithm. Simulation experiments show that this algorithm is stable and can find the required solution in almost all networks and achieve a better performance ratio. 2. DCMST_on_GA Algorithm A genetic degree-constrained multicast routing algorithm, DCMST_on_GA, is proposed on the basis of adequate research and study of genetic algorithms. The main idea is to establish a degree-constrained minimum spanning tree firstly, and then prune it to a multicast tree. At first, the algorithm must transform the original graph to a dynamic structure table then use a two-dimensional array to represent a multicast tree so that the genetic operation can directly be done on such individual. To guarantee convergence to a global optimal solution with probability one, the algorithm uses a strategy of the retention of the best individual. The coding method of this algorithm is concise, which can resolve the encoding and decoding difficulties of the genetic algorithm for multicast routing problem, and makes the algorithm faster. The experimental results indicate that this algorithm can very quickly find a small cost multicast tree in a small scale network, but when network's size increases, the algorithm need more long time to gain a solution.