Research Article
The primal simplex approach to the QoS routing problem
@INPROCEEDINGS{10.1109/QSHINE.2004.51, author={ Ying Xiao and K. Thulasiraman and Guoliang Xue }, title={The primal simplex approach to the QoS routing problem}, proceedings={1st International ICST Conference on Quality of Service in Heterogeneous Wired/Wireless Networks}, publisher={IEEE}, proceedings_a={QSHINE}, year={2004}, month={12}, keywords={}, doi={10.1109/QSHINE.2004.51} }- Ying Xiao
K. Thulasiraman
Guoliang Xue
Year: 2004
The primal simplex approach to the QoS routing problem
QSHINE
IEEE
DOI: 10.1109/QSHINE.2004.51
Abstract
Quality-of-service (QoS) routing problem requires the determination of a minimum cost path from a source node s to a destination node t in a data network such that the delay of the path is bounded by Δ (> 0). This problem also known as the constrained shortest path (CSP) problem is NP-hard. So, heuristics and approximation algorithms have been presented in the literature. Among the heuristics, the LARAC algorithm, based on the dual of the LP relaxation or the Lagrangian relaxation of the CSP problem is very efficient. In this paper we study the primal simplex approach to the LP relaxation of the CSP problem and present an approximation algorithm to this problem. Several issues relating to efficient implementations of our approach are discussed. Experimental results comparing the performance of the new algorithm with that of the LARAC algorithm are presented.