Path Reduction for Multi-Constrained Quality-of-Service Routing

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.