QoS Routing under Multiple Additive Constraints: A Generalization of the LARAC Algorithm

Ying Xiao, Krishnaiyan Thulasiraman, Guoliang Xue, Mamta Yadav

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


Consider a directed graph G(V; E), where V is the set of nodes and E is the set of links in G. Each link (u; v) is associated with a set of k C 1 additive nonnegative integer weights Cuv D (cuv;w1 uv;w2 uv; : : : ;wk uv). Here, cuv is called the cost of link (u; v) and wi uv is called the ith delay of (u; v). Given any two distinguish nodes s and t, the QoS routing (QSR) problem QSR(k) is to determine a minimum cost s-t path such that the ith delay on the path is atmost a specied bound. This problem is NP-complete. The LARAC algorithm based on a relaxation of the problem is a very efficient approximation algorithm for QSR(1). In this paper, we present a generalization of the LARAC algorithm called GEN-LARAC. A detailed convergence analysis of GEN-LARAC with simulation results is given. Simulation results provide an evidence of the excellent performance of GEN-LARAC.We also give a strongly polynomial time approximation algorithm for the QSR(1) problem.

Original languageEnglish (US)
Article number7103034
Pages (from-to)242-251
Number of pages10
JournalIEEE Transactions on Emerging Topics in Computing
Issue number2
StatePublished - Apr 1 2016


  • Combinatorial optimization
  • Lagrangian relaxation,
  • QoS routing
  • algorithms

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications


Dive into the research topics of 'QoS Routing under Multiple Additive Constraints: A Generalization of the LARAC Algorithm'. Together they form a unique fingerprint.

Cite this