Research On QoS Routing Problems On Networks

The delivery of large scale digitized audio-visual information over local or wide area networks is now becoming realistic. For traditional IP network, the currently deployed routing scheme is focused on constructing end-to-end connectivity which usually supports only one type of datagram service. The emerging high speed multimedia applications have different performance requirements such as bandwidth, delay, delay jitter, and loss rate etc. The notion of Quality-of-Service (QoS) has been proposed to describe the quality defined performance contract between the service provider and the user applications. The QoS requirement of a connection is given as a set of constraints, which can be link constraints, path constraints, or tree constraints. QoS routing is one such mechanism with two goals: selecting feasible paths or trees that meet QoS constraints and making efficient utilization of the network resources. So the QoS routing problem can be attributed to the construction of path or tree which satisfies the end-to-end QoS constraints at the same time optimizes some special cost function.The traditional QoS routing problem researches assume that the network information is precise, while in practical situation the growing network size makes it increasingly difficult to gather up-to-date state information in a dynamic environment and so the full knowledge on network parameters is typically unavailable. This paper divides the QoS routing problem into two major classes. One is the QoS routing with the accurate network information while the other is with the uncertain network information. One model of uncertainty assumes a probability distribution for each link parameter that represents the probability that the link can meet QoS demands. The routing problem is to establish a connection that satisfies some QoS requirements with a maximal probability. The other model of uncertainty assumes the link parameter is fuzzy number. Based on the extend principle of fuzzy mathematics and the notion of order reliability which describes the credibility of order relation between two fuzzy numbers. The routing problem is then to establish a connection that satisfies some QoS requirements with a maximal reliability.Another QoS routing problem is related to the notion of QoS partition. If the QoS parameters are additive and some or all the nodes of a path have QoS requirements, one must find a QoS-aware path and QoS allocation in this path which satisfies QoS requirements of both the end-to-end path and these nodes. The optimal solution must be chosen from all combinations of route and demand allocation, namely it is a combined routing and resource allocation optimization problem. Under the uncertain network environment, the notion of QoS partition can be explained as the probabilityor credibility of local links satisfying the QoS value allocated by end-to-end QoS requirement. At the same time, the means of definition on the optimal QoS partition will be different due to the probability model and the fuzzy mathematical model. We study the QoS routing or partition schemes with fuzzy model and probability model respectively.The further investigation of QoS routing problem introduces the concept of network fault tolerance. The disjoint paths are very important for fast restoration from network failure. Networks also require disjoint paths to distribute flows to avoid network congestion and optimize network throughput. Lost rate, network robustness and load balancing etc, are all aspects of Quality of Service (QoS) routing. QoS-aware link-disjoint paths are a pair of link-disjoint paths between the source and the destination which satisfy the multiple QoS constraints. The Optimal solution needs finding a pair of QoS-aware link-disjoint paths and optimizing the costs.In this dissertation, we mainly address the following problems: (1) the key issue of the QoS routing problem, including Multi-constraint Path (MCP), Multi-constraint Tree (MCT) and the related problems;(2)the link disjoint or node disjoint paths pair with QoS constraints; (3) the routing problems with uncertain network information, such as Most Probable Path(MP), Path Optimal Partition(POP), Most Optimal Partition Path(MOPP) for the probability model and Most Optimal Reliability Path(MORP), Path Optimal Partition(POP) etc.Chapter 1 introduces the concept of QoS routing, we overview the background of QoS routing problem, describe the major research direction and introduce the related important work done before and recently in this field. Then we propose the problem we will study on this paper.Chapter 2 discusses the key QoS routing problem MCP and the related problems such as Multi-constraint Optimal Path(MCOP), Bi-constraint Path(BCP), Restricted Shortest Path(RSP). BCP or RSP is the basic one among all these questions. In this chapter, first we overview the important algorithms about BCP and MCP. We divide these algorithms into four classes: polynomial approximate, linear search, dynamic programming and heuristic algorithms. Then, we make mathematical analysis on the linear search algorithm for the BCP and MCP. We determine the bound of the search factor and the value of the best search factor. Based on this analysis, we propose new approximate algorithms on BCP and RSP and make performance analysis on them. We also propose a novel heuristic approximate algorithm for BCP.Chapter 3 discusses multicast QoS routing problem. We present a survey in multicast QoS routing algorithms and classify them according to their objective functions and link constraints. The key question about multicast QoS routing is...