Efficient QoS routing

We consider the problem of routing in a network where quality of service constraints are placed on network traffic. We provide two optimal algorithms that are based on determining the discontinuities of functions related to the optimization at hand. The proposed algorithms have pseudopolynomial worst case running time and for a wide variety of tested networks they have fairly satisfactory running times. They perform significantly better than the algorithm based on the direct application of the dynamic programming equations and can also be used in conjunction with known polynomial-time approximation algorithms to provide good average case behavior, in addition to guaranteeing polymonial worst-case running time. (C) 2003 Elsevier B.V. All rights reserved.