Back to Search
Start Over
Bidirectional Multi-Constrained Routing Algorithms
- Source :
- IEEE Transactions on Computers. 63:2174-2186
- Publication Year :
- 2014
- Publisher :
- Institute of Electrical and Electronics Engineers (IEEE), 2014.
-
Abstract
- QoS routing plays a critical role in providing QoS support in the Internet. 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. The major contributions in this paper are as follows. First, we propose a $k$ shortest path algorithm using bidirectional search, whose complexity is deduced to be $O(\sqrt{k}\vert V \vert\lg (\vert V \vert) + k\vert E\vert)$ , where $\vert V \vert$ and $\vert E \vert$ represent the number of nodes and links in the network, respectively. Second, we show that bidirectional search can significantly accelerate the convergence of several existing QoS routing algorithms. Third, we propose a novel cost-effective bidirectional multi-constrained routing algorithm, which can greatly alleviate the forwarding state scalability issue by supporting stateless QoS routing in IP networks via IP tunneling or constraints-based alternate routing in MPLS networks via label stacks. It has the fastest known on-line running time $O(\vert V\vert)$ . 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.
- Subjects :
- Routing protocol
Virtual routing and forwarding
Dynamic Source Routing
Computer science
Bidirectional search
Equal-cost multi-path routing
computer.internet_protocol
Enhanced Interior Gateway Routing Protocol
IP forwarding
Multiprotocol Label Switching
Theoretical Computer Science
Convergence (routing)
Destination-Sequenced Distance Vector routing
Static routing
business.industry
ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS
Policy-based routing
Computational Theory and Mathematics
Link-state routing protocol
Private Network-to-Network Interface
Hardware and Architecture
Multipath routing
Shortest path problem
Algorithm design
business
Dijkstra's algorithm
computer
Software
Computer network
Subjects
Details
- ISSN :
- 23263814 and 00189340
- Volume :
- 63
- Database :
- OpenAIRE
- Journal :
- IEEE Transactions on Computers
- Accession number :
- edsair.doi...........1bdf5a7bfdf9c091af09ba9940578b64