QoS Path Problems in Communication Networks
Prof. K. Thulasiraman
School of Computer Science, University of Oklahoma.
14-07-05

---

Abstract

Consider a communication network modelled as a directed graph G = (V,E) in which each link is associated with two metrics, cost and delay. The cost (delay) of a directed path is defined as the sum of the costs (delays) of the links in the path. There are two important classes of QoS (Quality of Service) path selection problems. The single source-destination QoS path problem is to determine a minimum cost path from a given source node to a destination node subject to the condition that the delay of the path is at most a prespecified number T. The disjoint QoS Paths problem is to determine a pair of link disjoint paths from a source node to a destination node such the total cost of these path is minimum and the total delay of these paths is at most a prespecifed number. These problems are NP-hard. Therefore, heuristic and approximation algoirthms have been investigated for these problems. In this talk we shall give a broad overview of most of the results in this area emphasizing our own contributions.