Heuristic algorithms for multiconstrained quality-of-service routing
Author:
- 7 August 2002
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 10 (2) , 244-256
Abstract
Multiconstrained quality-of-service (QoS) routing deals with finding routes that satisfy multiple independent QoS constraints. This problem is NP-hard. Two heuristics, the limited granularity heuristic and the limited path heuristic, are investigated. Both heuristics extend the Bellman-Ford shortest path algorithm and solve general k-constrained QoS routing problems. Analytical and simulation studies are conducted to compare the time/space requirements of the heuristics and the effectiveness of the heuristics in finding paths that satisfy the QoS constraints. The major results of this paper are the following. For an N-nodes and E-edges network with k (a small constant) independent QoS constraints, the limited granularity heuristic must maintain a table of size O(|N|/sup k-1/) in each node to be effective, which results in a time complexity of O(|N|/sup k/|E|), while the limited path heuristic can achieve very high performance by maintaining O(|N|/sup 2/lg(|N|)) entries in each node. These results indicate that the limited path heuristic is relatively insensitive to the number of constraints and is superior to the limited granularity heuristic in solving k-constrained QoS routing problems when k>3.Keywords
This publication has 7 references indexed in Scilit:
- A distributed algorithm for delay-constrained unicast routing2002
- An efficient algorithm for finding a path subject to two additive constraintsACM SIGMETRICS Performance Evaluation Review, 2000
- An efficient algorithm for finding a path subject to two additive constraints2000
- Routing with end-to-end QoS guarantees in broadband networksIEEE/ACM Transactions on Networking, 1999
- An overview of quality of service routing for next-generation high-speed networks: problems and solutionsIEEE Network, 1998
- Quality-of-Service Routing for Traffic with Performance Guarantees1997
- Algorithms for finding paths with multiple constraintsNetworks, 1984