Heuristic algorithms for multiconstrained quality-of-service routing

Xin YuanIEEE/ACM 2002 · DOI

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.
BibTeX
@inproceedings{yuan2002heuristic,
  author = {Xin Yuan},
  title = {{Heuristic algorithms for multiconstrained quality-of-service routing}},
  booktitle = {IEEE/ACM},
  year = {2002},
  doi = {10.1109/90.993305},
}

Loading related content...

Figure