Quality of service routing: heuristics and approximation schemes with a comparative evaluation

• Main Authors: Ravindran, R., Thulasiraman, K., Das, A., Kaiyuan Huang, Gang Luo, Guoliang Xue
• Format: Conference Proceeding
• Language: English
• Subjects: Algorithm design and analysis; Approximation algorithms; Costs; Delay; Explosives; Lagrangian functions; NP-hard problem; Quality of service; Relaxation methods; Routing protocols
• DOI: 10.1109/ISCAS.2002.1010339

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. So heuristic approaches have been presented in the literature. Recently we extensively evaluated the performance of a heuristic called the LHWHM algorithm originally presented by Gang Luo et al. (1999). 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 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 and the approximation algorithm due to Hassin (1992) 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.