Abstract
In this paper we consider a class of quality of service routing problems that can be formulated as the bounded delay minimum cost path problem. This is an NP-hard problem [2]. So heuristic approaches have been presented in the literature. In a recent work [11] we extensively evaluated the performance of a heuristic called the LHWHM algorithm originally presented in [7]. We have found the LHWHM algorithm (which is based on Dijkstra's minimum cost path algorithm) to be very effective for implementation in a real network environment. In this paper we present a new heuristic which is based on the Bellman-Ford-Moore algorithm for the min-cost path problem. Unlike the LHWHM algorithm this algorithm is also suitable for distributed implementations. We discuss several issues pertaining to an efficient implementation of this algorithm and compare its features with the LHWHM [7] algorithm. We prove that this heuristic produces a feasible path satisfying the delay constraint whenever such a path exists. We conclude with an experimental evaluation of the new heuristic in comparison with the LHWHM algorithm, a recent Lagrangian-Relaxation based heuristic [9] and the approximation algorithm due to Hassin [10] by running them on a large number of graphs. We believe that the LHWHM algorithm and our new BFM based heuristic are serious candidates for implementation in real network environments.
Original language | English (US) |
---|---|
Title of host publication | Proceedings - IEEE International Symposium on Circuits and Systems |
Volume | 3 |
State | Published - 2002 |
Event | 2002 IEEE International Symposium on Circuits and Systems - Phoenix, AZ, United States Duration: May 26 2002 → May 29 2002 |
Other
Other | 2002 IEEE International Symposium on Circuits and Systems |
---|---|
Country/Territory | United States |
City | Phoenix, AZ |
Period | 5/26/02 → 5/29/02 |
ASJC Scopus subject areas
- Electrical and Electronic Engineering
- Electronic, Optical and Magnetic Materials