Research On Designing QoS Routing Algorithms For The Internet

There is a continuous demand for the evolution of the Internet from a simple best-effort network towards the one that can provide various levels of quality-of-service (QoS) guarantees to network applications. Researchers in academia have been paying signi cant attention to enabling QoS-based networking in the Internet. Although much work has already been done and several QoS based networking frameworks(e.g.,IntServ, DiffServ, MPLS) are proposed, QoS-based networking is still not in place, mostly due to the lack of efficient and practically deployable solutions, calling for further research.QoS routing(QoSR) is one of building blocks in the architectural framework for QoS-based networks. A key issue in QoSR is designing QoS routing algorithms, namely how to nd feasible paths that satisfy QoS requirements of various network applications based on state information provided by QoSR protocols. The dissertation studies thoroughly the problem of designing QoSR algorithms and gives some efficient proposals.There are three great challenges that QoSR faces, namely Restricted Shortest Path(RSP) problems, Multi-Constraints Path(MCP) problems and Multi-Constraints Optimal Path (MCOP) problems. These three problems are consistent in the meaning of Pareto optimal, which is a fundamental concept in Multi-Objective Optimization problems(MOOP).Concerning that Pareto optimal is a key concept in MOOP, we introduces Pareto optimal relevant concepts into QoSR problems. Based on these concepts, a Pareto optimal based partition framework(POPF) is established, in which QoS metric space is partitioned into three parts, namely feasible, unfeasible and NP-complete areas. We also discuss the Pareto front of two additive constraints QoSR problems and point that the number and distribution of Pareto optimal points are very important to the partition of QoS metric space. We then give a method to generate Pareto optimal points. POPF only not provides a theory basis for applying Paieto optimal relevant concepts in QoSR problems, but also acts as a guide to determining search directions, the termination conditions of the algorithm and even how to generate routing requests to evaluate algorithms.We rst propose two QoSR algorithms that address two additive constraints path selection problems. These two algorithms take fully advantages of Pareto optimal and have lookahead ability. Then, by designing a novel nonlinear path length function, we proposean efficient QoSR algorithm NM_MCP that deals with MCP problems. NM_MCP mainly consists of two phases: precomputation and on-demand computation. Because of the short period of precomputation, NM_MCP suffers less from inaccurate state information while having a fast response at the same time. One the other hand, NM_MCP executes a modi ed version of Dijkstra algorithm at most once on-demand along with the newly de ned nonlinear path length function. Therefore, NM_MCP makes a good tradeoff not only between precomputation and on-demand computation, but also between nonlinear and linear cost-based paths selection algorithms. Using extensive simulations, we demonstrate the high success rate and responsiveness of NM_MCP when compared to the existing QoSR solutions.With few exceptions, most of previous QoS routing solutions have been developed under the assumption that a link-state routing protocol is used to maintain the global network state information at each node, and that this global information is accurate. In practice, however, the network state information might not be accurate due to several reasons.We reconsider the conclusions in POPF and study carefully two additive-constrained path problem, in the presence of inaccurate state information. We formulate this problem as Most-Probable Two-Additive-Constrained Path (MP-TACP) problem. To solve it, we follow a probabilistic approach and propose an algorithm called MP-TACPA. In general, MP-TACPA uses pre- and on-demand computation along with both linear and nonlinear search techniques. In contrast to previous algorithms using similar techniques, MP-TACPA takes into account the inaccuracies along with new bounds and heuristics including look ahead, dominance probability that contribute the low average computation cost. Extensive simulations show that MP-TACPA behaves well in the presence of inaccurate state information. It is very efficient when average computation cost, response speed and success rate of nding a feasible path are taken into consideration.The dissertation studies thoroughly the problems of designing efficient QoSR algorithms. POPF proposed in this dissertation provides theoretical foundation to evaluating and guiding the design of routing algorithms that support QoS. QoSR algorithms provided in this paper help to giving only not higher success rate in nding feasible paths but also shorter response time. The results of our study show that these algorithms can be used in next generation networks in various cases.