Constrained shortest paths for QoS routing and path protection in communication networks.

Abstract

The CSDP (k) problem requires the selection of a set of k > 1 link-disjoint paths with minimum total cost and with total delay bounded by a given upper bound. This problem arises in the context of provisioning paths in a network that could be used to provide resilience to link failures. Again we studied the LP relaxation of the ILP formulation of the problem from the primal perspective and proposed an approximation algorithm.

We have studied certain combinatorial optimization problems that arise in the context of two important problems in computer communication networks: end-to-end Quality of Service (QoS) and fault tolerance. These problems can be modeled as constrained shortest path(s) selection problems on networks with each of their links associated with additive weights representing the cost, delay etc.

The problems considered above assume that the network status is known and accurate. However, in real networks, this assumption is not realistic. So we considered the QoS route selection problem under inaccurate state information. Here the goal is to find a path with the highest probability that satisfies a given delay upper bound. We proposed a pseudo-polynomial time approximation algorithm, a fully polynomial time approximation scheme, and a strongly polynomial time heuristic for this problem.

Finally we studied the constrained shortest path problem with multiple additive constraints. Using the LARAC algorithm as a building block and combining ideas from mathematical programming, we proposed a new approximation algorithm.

First we studied the QoS single route selection problem, i.e., the constrained shortest path (CSP) problem. The goal of the CSP problem is to identify a minimum cost route which incurs a delay less than a specified bound. It can be formulated as an integer linear programming (ILP) problem which is computationally intractable. The LARAC algorithm reported in the literature is based on the dual of the linear programming relaxation of the ILP formulation and gives an approximate solution. We proposed two new approximation algorithms solving the dual problem. Next, we studied the CSP problem using the primal simplex method and exploiting certain structural properties of networks. This led to a novel approximation algorithm.