A randomized algorithm for finding a path subject to multiple QoS requirements

T. Korkmaz, M. Krunz

Research output: Contribution to journalArticlepeer-review

70 Scopus citations

Abstract

An important aspect of quality-of-service (QoS) provisioning in integrated networks is the ability to find a feasible route that satisfies a set of end-to-end QoS requirements (or constraints) while efficiently using network resources. In general, finding a path subject to multiple additive constraints (e.g., delay, delay-jitter) is an NP-complete problem. We propose an efficient randomized heuristic algorithm to this problem. Although the algorithm is presented as a centralized one, the idea behind it can also be implemented in a distributed manner. Our algorithm initially computes the cost of the best path from each node to a given destination with respect to individual link weights and their linear combination. In this initialization step, Reverse-Dijkstra's algorithm is used K + 1 times per path request, where K is the number of additive constraints. The algorithm then randomly traverses the graph, discovering nodes from which there is a good chance of reaching the final destination. This randomized search is a modification of the breadth-first search (BFS). Using extensive simulations, we show that the proposed algorithm provides better performance than existing algorithms under the same order of computational complexity.

Original languageEnglish (US)
Pages (from-to)251-268
Number of pages18
JournalComputer Networks
Volume36
Issue number2-3
DOIs
StatePublished - Jul 2001

Keywords

  • Multi-constrained path selection
  • QoS-based routing
  • Scalable routing

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'A randomized algorithm for finding a path subject to multiple QoS requirements'. Together they form a unique fingerprint.

Cite this