QoS Routing Algorithms With Inaccurate Network State Information

A major research topic in computer networks is to study how to provide high quality service in the next generation Internet. This thesis concentrates on the study of Quality of Service (QoS) routing algorithms and related technologies with inaccurate network state information, and the analysis on the influence created by the inaccuracy of network state information on the performance of routing algorithms.The thesis starts with an extensive analysis on the current research in network QoS and on the routing policies and algorithms based on IP, describes the reason for state information inaccuracy in network and the research status of routing algorithms with inaccurate network state information, and discusses the problems and models of the routing algorithms.The thesis then studies the emulation modes of routing algorithms with inaccurate network state information, proposes a simulation model based on events for routing algorithms with inaccurate network state information, and develops a routing simulation software R-NS that provides an effective environment for the research of network routing algorithms.Randomized routing algorithms based on improved Dijkstra and Bellman-Fordalgorithms are proposed for the unicast routing model with inaccurate network stateinformation. In these algorithms, we apply randomness at the level of network links andpropose randomized policies based on the probability distribution on network links. Onthe anycast routing model, we propose two routing algorithms with accurate orinaccurate network information, respectively. Our algorithm with accurate networkinformation guarantees finding a path if such a path satisfying the given QoSrequirement exists in network. For the model of QoS routing with general multipleconstraints, we establish a model of the QoS routing problem with multiple constraints,and propose a number of heuristic routing algorithms based on randomization andbreadth first search policies. In order to improve the availability of network resource,we propose two evaluation parameters: the average bandwidth of a request and thebalanced ratio of network load, and apply them to the routing algorithms with accurateor inaccurate network information. We also introduce the characteristic andarchitecture of MANET, and propose a QoS routing algorithm based on predictions.Extensive experimental simulations are performed based on the above proposedalgorithms and the considered routing models. The simulation results show that ouralgorithms effectively get higher request acceptance ratio and more balanced networkload, 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 algorithm designs on network routings that support QoS. The results can be used widely in the next generation Internet.