Research Of Multiple Path Quality-of-Service Routing Algorithms

As the fast growth of Internet and the continues emergence of newly services having real time demand such as Voice over IP, Video Conference, Multimedia long-distance Education and Video Programme, user's demand on Quality of Service (QoS) becomes higher and higher.Routing is the kernel of network. It is also one of the main factors deciding QoS. QoS Routing (QoSR) is the core technique and hotspot in the research of QoS. Traditional routing algorithm can't meet the user's QoS need. At the same time, the shortest path can easily become congested, which leads to the network performance drops dramatically. So some constrained-routing mechanism must be taken to balance network load and improve transfer efficiency. The emergency of QoS routing can solve this problem efficiently. Multiple constrained QoS routing problem is a NP-complete problem. Currently, we search hypo-excellent paths using heuristic algorithm to solve this problem. The imprecision of network link-state information is objective, thus, the research of QoS routing algorithms under imprecise link-state information becomes necessarily. Multi-path routing algorithm can balance network load and have a preferable performance in coping with imprecise network link-state information.The existing algorithms of QoS routing include various heuristic algorithms, neural network-based algorithms, hybrid genetic algorithms, ant-algorithms and so on. These algorithms exist some defects as foliows:(1) the constrain condition of these algorithms is single (2) they dont take the network load balance into consideration (3) they don't consider the coexistence of themselves with traditional shortest-path first algorithm.Aiming at solving these defects, we design and realize multi-path QoS routing algorithm under imprecise link-state information in this paper: Minpath algorithm and KMulpath algorithm. Based on unproved Bellman_Ford algorithm, Minpath algorithm can find the least cost path meeting bandwidtiu delay and hop constrains. Using deepest first search strategy, KMulpath algorithm can find and keep multiple QoS paths meeting QoS constrains in advance. Then, it can select the best and hypo-best path among these multiple QoS paths through path evaluation function and the comparison between bandwidth utilization of these paths. When the best route is invalid, route can be switched to the hypo-best path quickly. As a result, it can decrease reroute spending greatly and solve the problems caused by imprecise link-state information.To validate the efficiency of our algorithms, we create network simulate scenes and go along simulate experiment using these two QoS routing algorithms. By comparison with traditional shortest path first routing algorithm, it can be seen that these two algorithms can balance network load and heighten network resource utilization.Also we primarily probe into the coexistence problem of QoS routing algorithm with traditional shortest path first routing algorithm. In network simulation, our dynamical routing algorithm can adjust routing strategy adaptively according to changes of network stream , choose route dynamically and decide using whether the shortest path or the QoS path, solving the problem of the coexistence of QoS routing algorithm with traditional routing algorithm. The result of simulation experiment indicates that KMulpath algorithm can coexist with traditional shortest-path algorithm excellently and has a preferable network performance.