Chinese Journal of Computers   Full Text
Title	Path Reduction for Multi-Constrained Quality-of-Service Routing
Authors	ZHAO You-Jian ZHANG Tie-Lei CUI Yong
Address	(Department of Computer Science and Technology, Tsinghua University, Beijing 100084)
Year	2007
Issue	No.12(2090—2100)
Abstract &   Background	Abstract Multi-constrained quality-of-service routing (QoSR) is regarded as a promising solution to support flexible QoS-oriented services. However, there may exist multiple paths from a source node to a destination node in the context of multi-constrained routing and thus the routing table has to be enlarged accordingly. Since the current routing table size is quite large, especially in the high-speed core networks, path reduction needs to be performed in order to store less paths into the QoS routing table. In this paper the authors try to solve the Optimal Path Reduction Problem (OPR) which aims to reduce the storage space of the QoS routing table as much as possible and at the same time to maximize routing success ratio. To achieve this goal, the authors propose two contribution region based algorithms: the incremental contribution algorithm and its improved version. These two algorithms figure out the path with maximum capacity of contribution region one by one from a large set of multi-constrained paths and finally obtain a small set of selected paths. Extensive simulations show that these two algorithms achieve satisfying performance in terms of the routing success ratio with low time complexity. keywords QoS routing; overlay; multiple constraints; path selection; precomputation background Quality-of-service routing (QoSR) is regarded as a promising solution to support flexible QoS-oriented services. Unlike the traditional routing, QoSR tries to meet multiple constraints. Due to the NP-completeness of the multi-constrained routing, researchers in this field have designed many effective heuristics to find a feasible path or several feasible ones in a given network. This paper steps further and proposes an algorithm to reduce the number of the selected paths to an acceptable level and at the same time to maximize routing success ratio. This work is supported by the National Natural Science Foundation of China (Nos.90604029 and 60403035) and the National Basic Research Program(973 Program) of China (No.2003CB314801). These research programs aim to design and establish a novel network architecture. This architecture should be provided with plenty of attracting features, such as scalability, tolerance of failure, self-configuration, supporting QoS-oriented services, etc. This paper focuses on the problem of QoS control and routing. The work presented in this paper can be used to provide theoretical support for the large-scale deployment of QoS routing in the high-speed core networks.