A Selection Technique For Replicated Multicast Server Using Genetic Algorithm

Multicast server replication is a novel technique for multicast to enhance the performance and scalability. It works in the way that multiple servers providing the same service at different positions deliver information to the different clients groups simultaneously according to the network topology and load. Server selection is the primary issue of multicast server replication, and it leads to different network profit. This problem is composed of two parts. One is clients grouping, which refers to that clients served by the same server belong to the same group; the other is to build a multicast tree for each group. Replicated multicast server selection has been proved to be NP-hard. Due to the complexity, current algorithms are either used in a narrow context or hard to get the satisfactory solution.This paper presents a new approach using genetic algorithm GA-RMSS (Genetic Algorithm based Replicated Multicast Server Selection) to handle replicated multicast server selection. A two-level coding scheme is developed to map the application solution space into the chromosome space. The first level code represents server allocation, and the second level code establishes a multicast tree for each group. A new algorithm DRMT (Dijkstra-based Random Multicast Tree) utilizing Dijkstra algorithm and random disturbance is proposed to create a random multicast tree. DRMT does not need to detect and repair invalid code; hence it facilitates the implementation and accelerates creating process. The multiple multicast trees in different groups are stored in a structure called "routing matrix". Routing matrix provides a convenient means to extract individual multicast tree and express edge-sharing information.An integrated fitness function is designed to indicate optimized object. By various fitness function parameters, it can denote not only single object such as average receiving rate or fairness but also multi-object, therefore it givesflexibility to the algorithm. Elitist model is used in selection operation to remain the best solution. The crossover operation exchanges partial of the first level code at the random cross point. The mutation operation randomly selects a gene in the first level code and changes it into another gene. Both crossover and mutation use DRMT algorithm to rebuild multicast trees for offspring. Crossover and mutation together provide a searching capability that results in improved quality of solution.The extensive simulations in sparse and dense networks clearly demonstrate that the proposed algorithm outperforms the heuristic algorithms (Shortest Path algorithm and Widest Path .algorithm) in the sense of yielding high-quality solutions. In addition, it also shows better performance in providing backup routing and load balance.