Research On Multi-Constrained QoS Routing Algorithms

Internet is important in many fields and areas. It penetrates into and has important effects to human's study, work, teaching, national defence and living. Among the applications of Internet, an important one is the multimedia application, or the realtime business in the network. This includes IP phone, video meeting, online movie, etc. A common character of them is their requirement for quality, or the problem of quality of service, shortened as QoS.People have presented various protocols and frameworks for QoS. QoS routing is an important and efficient method to solve QoS. The purpose of QoS routing is to find a way from the source node to the destination node, which meets the requirements of QoS metrics such as bandwidth, delay, delay jitter, etc. This dissertation aims at the QoS routing problems.Chapter one surveys the studies of QoS and QoS routing.Chapter two presents three algorithms for multi-constrained path problems, or shortened as MCP. This method translates all kinds of metrics into only one kind, i.e., concave metric. We call this algorithm as additive-to-concave, or shortened as ATC. As to MCP, the dealing method with concave metrics is very simple. Any way is a QoS satisfying way from the topology in which all the dissatisfying links are just truncated by the concave requirement. This method has better performance than the methods which use mixed metric to solve the MCP. The second algorithm improves from the ATC. It uses the algorithm breadth-first-search, or BFS. We call this algorithm as ATC_BFS. ATC_BFS is more complicated than ATC, but has better performance. The third algorithm presented in this chapter uses BFS in a backward way and forward way, i.e., BFS is resorted both from the source node to the destination node and from the destination node to the source node.Chapter three presents an algorithm for the MCOP problem. We call this method as ATC_MCOP. The MCOP considers optimal requirement besides the other QoS multi-constraints. ATC_MCOP first gets three paths; and chooses a minimal path as the target path by the way of the optimal requirement from the three paths. The basic idea of this algorithm is that when deals with the MCOP: the first step is to consider multi-constraints, then the second step is to consider the optimal requirement.Chapter four presents a pervasive QoS routing algorithm. A pervasive algorithm has many characters. The algorithm should be pervasive and expansible, i.e., it can deal with different kinds of situations. The algorithm should have good performance compared with other algorithms. The algorithm should be robust; i.e. it can go on well when faulse happens in the network. The algorithm should be load-balanced, i.e., it can go well with heavy load traffic environment. The algorithm should be deadlock-free; and the algorithm can bring profitability for the service providers.Availability is a special QoS metric, and of which the counterpart is unavailability. Chapter five presents an analytical computation method for the unavailability in SBPP (shared backup path protection). Existing computation methods for the unavailability get the upper and lower limits for the unavailability. Their computation steps are complicated. We first get analytical computation equations for the state probabilities; and then compute the unavailability for the SBPP based on these analytical state probabilities.Chapter six probes into the MCP and MCOP problems with availability as a QoS metric. Availability is a special QoS metric. Its computation method is special. When the availability of a path does not satisfy the requirement, people may find backup paths to satisfy the availability requirement. The idea of backup paths is special to availability compared with other QoS metrics. People has studied QoS problems based on availability, but has not studied multi-constrained QoS routing with availability as its metric. In this chapter, we point out that the MCP and MCOP problems with availability as QoS metrics can be solved by resorting to special strategies. By the way, once the MCP and MCOP problems meet availability, the problems turn out to be more complicated.Chapter seven expatiates upon the simulation and computation environments. The algorithms in this dissertation are simulated with OPNET in different topologies and different traffic loads.The last chapter is for the conclusions.