Heuristic algorithms for multiconstrained quality-of-service routing
Multiconstrained quality-of-service (QoS) routing deals with finding routes that satisfy multiple independent QOS constraints. This problem is NP-hard. In this paper, 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\(k-1)) in each node to be effective, which results in a time complexity of O(\N\(k)\E\), while the limited path heuristic can achieve very high performance by maintaining O(\N\(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.
routing quality of service