Bidirectional Multi-Constrained Routing Algorithms

Abstract
Most existing QoS routing algorithms employ the strategy of unidirectional search in route selection. Bidirectional search has been recognized as an effective strategy for fast route acquisition in identifying the shortest path connecting a pair of nodes. However, its efficiency has not been well established in the context of route selection subject to multiple additive constraints, which is in general NP-Complete. In this paper, we study how to employ bidirectional search to support efficient QoS routing subject to multiple additive constraints. First, we propose a k shortest path algorithm, which employs bidirectional search, with a complexity of Ο(sqrt(k)|V|lg|V|+k|E|), where |V| and |E| represent the number of nodes and links in the network, respectively. Second, our study shows that bidirectional search can significantly accelerate the convergence of existing QoS routing algorithms. Third, we propose a cost-effective stateless bidirectional multi-constrained routing algorithm, which can greatly alleviate the forwarding state scalability issue for supporting QoS routing in IP networks. It has the fastest known on-line running time O(|V|). Theoretical and simulation results are given to demonstrate the high performance of our proposed algorithm in identifying QoS-satisfied paths and also in efficient resource utilization as compared with existing algorithms.

Comments are closed.