Efficient computation of delay-sensitive routes from one source to all destinations

In this paper we describe an efficient algorithm for the constrained shortest path problem which is defined as follows. Given a directed graph with two weights on each link e, a cost l/sub e/, and a delay t/sub e/, find the cheapest path from a source to all destinations such that the delay of each path is no more than a given threshold. The constrained shortest path problem arises in quality-of-service-sensitive routing in data networks and is of particular importance in real time services. The problem formulation and the algorithmic framework presented are quite general; they apply to IP, ATM, and optical networks. Unlike previous algorithms, our algorithm generates paths from one source to all destinations. Our algorithm is strongly polynomial, and is asymptotically faster than earlier algorithms. We corroborate our analysis by a preliminary simulation study.

I. Introduction

The basic problem in QoS-sensitive routing for emerging services such as VoIP (Voice over IP), video, interactive multimedia etc. is to find the cheapest route from a source to a destination (or destinations) that satisfies one or more QoS criteria. The most important QoS criteria are end-to-end bandwidth requirement and end-to-end delay threshold. This basic problem is important for IP networks as well as optical networking.