Research On Internet QoS Routing

Following the fast growth of the Internet in recent years, more and more multimedia application carry out in the Internet. Future networks are expected to support various applications, specially multimedia application such as VoIP, VoD. To satisfy different QoS (Quality-of-Service) requirements, some mechanisms need to be employed. But because the Internet nowadays based on IPv4 only provides the best-effort service, and no QoS guarantees provided. QoS guarantee for the next-generation Internet is a challenging problem, and QoS guarantee is also a hot-topic in Internet research. Among QoS guarantee mechanism, QoS routing is one of the key issues. QoS routing has two objectives: (1) find a feasible path for QoS traffic to provide the QoS guarantee; (2) maximizing the utilization of the whole network.In this thesis, we research some problems in QoS routing. The main contributions of this thesis are as follows:(1) To obtain multi-constrained QoS path with minimal cost, a least-cost QoS path selection algorithm-LBPSA(Lagrange Branch-and-Bound Path Selection Algorithm) is presented. This algorithm uses Lagrangian relaxation to obtain the lower bound and the upper bound of the least cost of multi-constrained QoS path. And finds the multi-constrained QoS path with least cost by branch-and-bound method. In solving the Lagrangian multiplier problem, it introduced a new iteration method. Through recursion from destination to source based on branch-and-bound scheme, the least-cost multi-constrained path is obtained. The proposed algorithm has a pseudo polynomial running time. The simulation shows that the algorithm can find the path with high success ratio and low complexity. The success ratio is higher than the H_MCOP that is the main algorithm of MCOP.(2) The second objective of QoS routing is maximizing the utilization of the networks. To QoS traffic, it means that the networks admit more QoS flows that have different QoS requests, including best-effort flows. It is multiple flows coexistence problem. We propose a novel method to this problem- the synthesis metrics routing algorithm (SMRA). SMRA synthesize the QoS delay constrain and the bandwidth request of the QoS flow to form the metrics. Based on the synthesis metrics, SMRA use the shortest path algorithm to search pathfor the QoS flows and best-effort flows. The simulation shows that the networks with SMRA can admit more QoS flows that have different delay request. And the load of the whole networks increase very little.(3) The probing method is a good distributed QoS routing. We propose a new routing algorithm based on probing- MLPRA(Multi-path Limited Probing Routing Algorithm). In MLPRA, we propose two methods- shortest path first probing and saving incomplete path, to search more feasible QoS paths by using limited probing. In the acknowledge procedure, the ack deposit the "pheromone" and get the "pheromone" deposited by the other acks. In simulation, MLPRA can search more feasible paths than DRA, the other probing QoS routing algorithm, and use little probing packets. Through "pheromone'", the congestion probability of MLPRA is little than widest-shortest routing algorithm and shortest-widest routing algorithm.