QoS routing in communication networks: Approximation algorithms based on the primal simplex method of Linear Programming

Ying Xiao, Krishnaiyan Thulasiraman, Guoliang Xue

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


Given a directed network with two integer weights, cost and delay, associated with each link, Quality-of-Service (QoS) routing requires the determination of a minimum cost path from one node to another node such that the delay of the path is bounded by a specified integer value. This problem, also known as the Constrained Shortest Path problem (CSP), admits an Integer Linear Programming (ILP) formulation. Due to the integrality constraints, the problem is NP-hard. So, approximation algorithms have been presented in the literature. Among these, the LARAC algorithm, based on the dual of the LP relaxation of the CSP problem, is very efficient. In contrast to most of the currently available approaches, we study this problem from a primal perspective. Several issues relating to efficient implementations of our approach are discussed. We present two algorithms of pseudopolynomial time complexity. One of these allows degenerate pivots and uses an anticycling strategy and the other, called the NBS algorithm, is based on a novel strategy which avoids degenerate pivots. Experimental results comparing the NBS algorithm, the LARAC algorithm, and general purpose LP solvers are presented. In all cases, the NBS algorithm compares favorably with others and beats them on dense networks.

Original languageEnglish (US)
Pages (from-to)815-829
Number of pages15
JournalIEEE Transactions on Computers
Issue number7
StatePublished - Jul 2006


  • Communication networks
  • Constrained shortest path
  • Graph algorithms
  • Linear programming
  • QoS routing
  • Routing protocols
  • Simplex method

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'QoS routing in communication networks: Approximation algorithms based on the primal simplex method of Linear Programming'. Together they form a unique fingerprint.

Cite this