Efficient Heuristic Algorithms for Finding Multi-constrained Paths

Quality of service routing, namely, finding multi-constrained paths is a real problem arising in multimedia applications, which has been proven to be NP-complete. The paper presents three polynomial-time scalable algorithms for finding a path subject to two additive constraints: one to be randomized algorithm and two to be limited path heuristic algorithms. To our best knowledge, so far, the best heuristic algorithm among the existing algorithms is Korkmaz's algorithm. However, from our simulations, our algorithms may achieve better performance than Korkmaz's algorithm.