Research On Multi-Constrained QoS Routing Algorithm Based On Pareto Optimality

As IP network's general characteristic of independent of high layer applications and low layer carrier networks, the construction of converged network based on IP technology becomes the basic of next generation high speed broadband network recently. Meanwhile, varieties of increasingly rich traffics have different requirements in performance parameters such as bandwidth, delay, delay jitter and packet loss rate, which requires network differentiate traffics, and allocates resources according to users'requirements to provide different Quality of Services (QoS) for traffics.QoS routing problem in QoS research framework, especially multi-constrained QoS routing problem construct of multiple metric constrains becomes a research focus in the industry because it can reflect practical QoS routing selection problem more exactly. The research emphasis of multi-constrained QoS routing problem is resolving a NP complete problem,and an effective solution is to convert it to Multi-Objective Optimization Problem (MOOP).In the searching of Pareto optimality point with Pareto optimality theory, the partition of QoS metric space can be accomplished, and the feasibility of the path can be judged by the routing request information which acquired the feasible solution that meet QoS routing's multi-constrained conditions.A QoS routing algorithm named Linear Pre-compute Non-linear On-line-compute Algorithm (LPNOA) on the basis of searching Pareto optimality point with Dijkstra algorithm is propoed in this paper by analyzing geometrical meaning of linear searching and non-linear searching.The algorithm not only combines linear searching with non-linear searching, but also combines pre-compute with on-line-compute. It selects an optimal searching direction in pre-compute stage, and defines a new non-linear path cost function in on-line-compute stage. LPNOA algorithm is implemented in the simulation platform, and is compared with PODWCA algorithm, which also adopted the partition of QoS metric space based on Pareto optimality, in the algorithm performance such as complexity, respond speed and path searching success rate. It is verified the proportion of remaining NP complete area of LPNOA algorithm with the same complexity is lower than that of PODWCA algorithm 10% to 15%,the respond speed slightly higher, and the success rate is higher than that of PODWCA algorithm up to 0.6%.With the intense and complication of network scale, the acquisition of accurate network information becomes more and more difficult, while inaccurate network state information may lead to network performance's extremely deterioration. A QoS routing algorithm named Pre-compute and On-line-compute Combined QoS Routing Algorithm with Inaccurate Network State Information (POCQRA-INSI) is put forward in the paper. The algorithm adopts ant colony algorithm as a basic searching algorithm, and comprises pre-compute stage and on-line-compute stage, and have different information volume defines in different stage. The simulation verifies the negative effect of inaccuraty of network state information by comparing with LPNOA algorithm's performances in inaccurate network. The path searching success rate of LPNOA algorithm in inaccurate network decreased about 4% than in general network environment, and searching efficiency about 15%,while POCQRA-INSI algorithm almost remains the same as the case in general network environment.Besides,a research on QoS admission control mechanism based on bandwidth broker is also made in the paper. Four admission control algorithms simulation modeling are built, which choose acceptance rate, network utilization and average waiting time as evaluate standard.The paper summarizes the achieved result, and indicates further research direction in QoS routing algorithm in the end.