Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1109/INFCOM.2001.916276 | IEEE INFOCOM 2001: THE CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-3, PROCEEDINGS: TWENTY YEARS INTO THE COMMUNICATIONS ODYSSEY |
Keywords | Field | DocType |
quality of service,real time,internet telephony,shortest path problem,shortest path,routing,bandwidth,polynomials,directed graph,qos,directed graphs | Mathematical optimization,Shortest path problem,Computer science,Computer network,Constrained Shortest Path First,Yen's algorithm,Suurballe's algorithm,Shortest Path Faster Algorithm,Longest path problem,Widest path problem,Distributed computing,K shortest path routing | Conference |
ISSN | Citations | PageRank |
0743-166X | 50 | 3.05 |
References | Authors | |
5 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ashish Goel | 1 | 3039 | 244.56 |
| K. G. Ramakrishnan | 2 | 587 | 98.53 |
| Deepak Kataria | 3 | 111 | 9.04 |
| Dimitris Logothetis | 4 | 108 | 9.29 |