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_e, and a delay t_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