QoS routing in communication networks: approximation algorithms based on the primal simplex method of linear programming

摘要

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.