Research On Multi-constraint Quality Of Service Routing Algorithm

In research of quality-of-service routing, the network model based on multi-constraints problem can present the actual quality-of-service routing more accurately. The problem of multi-constraints path selection, which is an NP-complete problem, is determined a feasible path that satisfies a set of constraints. In order to improve the performance of multi-constraints quality-of-service routing, we might meet the problems that how to assemble parameter, how to update the information of network, and how to bring quality-of-service routing into "best-effort" frequently.Based on above consideration, we propose an efficient heuristic algorithm, which take a nonlinear function as cost function, for the most general form of the quality-of-service routing problem in this thesis. First, the thesis introduces the concept of quality-of-service and quality-of-service routing, and recommends the characteristic and the other related knowledge of quality-of-service routing. There also introduce some multi-constraints quality-of-service routing algorithm in present situation both in domestic and abroad. Afterward, the thesis analyzes one of the representative multi-constraints quality-of-service routing algorithm — HMCOP algorithm, classifies the enhanced algorithm of HMCOP algorithm into three species: enhanced on cost function, on node information, and on basic algorithm. And then the thesis points out an important theorem that HMCOP algorithm is based on is not always true. Also, the thesis makes a proof in theory firstly, In this part, there introduces a kind of enhanced heuristic algorithm, which hold the HMCOP algorithm's low complexity, and compares with HMCOP algorithm, illuminates the performance. Moreover, this thesis proposes a novelty efficient heuristic algorithm named M_MCOP algorithm, which takes a nonlinear function as cost function also, and combines bidirectional search with blocking, holds low complexity and high success ratio, for the most general form of the quality-of-service routing problem. At the end of the thesis, it makes the performance evaluation of M_MCOP algorithm. Finally, the development of quality-of-service routing algorithm theory and research in the future is forecasted.