Research On Network Anycast Routing Algorithm Based On Genetic Algorithm

A major research topic in computer network is to study how to provide high quality service in the next generation Internet. This thesis concentrates on the study of the any-cast routing algorithm based on genetic algorithm.On the base of the abundant understanding and analysis of the basic concept of network any-cast routing and the technology research precondition , The thesis discusses the problems and models of the any-cast routing algorithms and studies how to induct the genetic algorithm into any-cast routing algorithm.In the thesis, the key technical problems utilizing genetic algorithm and random method to design any- cast routing algorithms are explored. We designed and realized the any-cast routing algorithm based on genetic algorithm. Resolved the problems concerned in the algorithms, such as the code model, the original genus selection, the fitness function, the crossover strategy, the mutation regulation, and the algorithm's convergence, avoidance of dead loop etc. Aim at different network scales we propose two any-cast routing algorithms. The first one aim at small-scale networks, which adopts genetic algorithm and general search, it based on any-cast routing, first, create all the anthology routines; then, acquire the general best resolution through evolution. The second one aim at large-scale networks, which is a localized anycast routing algorithm after some advancement is made, the node doesn't need store the network topology. The next node extends its evolution genes and anthology routines based on the exchange of information. Both the creation of anthology routines and the evolution work at the same time, thus we acquire the best resolution at less time and save a lot memory.In order to verify the validity of our algorithms, we proposed a network simulation model for any-cast routing algorithms with incomplete network state information. We structure the topology of network, the capability of every link,produce the source/destination group nodes concerned in services. Extensive experimental simulations are performed based on the proposed algorithms and the considered network simulation model. The simulation results show that our algorithms effectively get high search ratio and more balanced network load, and improve the availability of network resource.In conclusion, the research in this thesis provides theoretical foundation for optimizing network resource and improving quality of services, and offers scientific reference for algorithms designs on network any-cast routings that support QoS. The results can be used widely in the next generation Internet.