Multi-constrained optimal path selection

T. Korkmaz, M. Krunz

Research output: Contribution to journalConference articlepeer-review

379 Scopus citations


Providing quality-of-service (QoS) guarantees in packet networks gives rise to several challenging issues. One of them is how to determine a feasible path that satisfies a set of constraints while maintaining high utilization of network resources. The latter objective implies the need to impose an additional optimality requirement on the feasibility problem. This can be done through a primary cost function (e.g., administrative weight, hop-count) according to which the selected feasible path is optimal. In general, multi-constrained path selection, with or without optimization, is an NP-complete problem that cannot be exactly solved in polynomial time. Heuristics and approximation algorithms with polynomial-and pseudo-polynomial-time complexities are often used to deal with this problem. However, existing solutions suffer either from excessive computational complexities that cannot be used for online network operation or from low performance. Moreover, they only deal with special cases of the problem (e.g., two constraints without optimization, one constraint with optimization, etc.). For the feasibility problem under multiple constraints, some researchers have recently proposed a nonlinear cost function whose minimization provides a continuous spectrum of solutions ranging from a generalized linear approximation (GLA) to an asymptotically exact solution. In this paper, we propose an efficient heuristic algorithm for the most general form of the problem. We first formalize the theoretical properties of the above nonlinear cost function. We then introduce our heuristic algorithm (H_MCOP), which attempts to minimize both the nonlinear cost function (for the feasibility part) and the primary cost function (for the optimality part). We prove that H_MCOP guarantees at least the performance of GLA and often improves upon it. H_MCOP has the same order of complexity as Dijkstra's algorithm. Using extensive simulations on random graphs with correlated and uncorrelated link weights, we show that under the same level of computational complexity, H_MCOP outperforms its (less general) contenders in its success rate in finding feasible paths and in the cost of such paths.

Original languageEnglish (US)
Pages (from-to)834-843
Number of pages10
JournalProceedings - IEEE INFOCOM
StatePublished - 2001
Event20th Annual Joint Conference of the IEEE Computer and Communications Societies - Anchorage, AK, United States
Duration: Apr 24 2001Apr 26 2001


  • Multiple constraints
  • Path selection
  • QoS routing
  • Scalable routing
  • k-shortest paths

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Multi-constrained optimal path selection'. Together they form a unique fingerprint.

Cite this