In this paper

we study the NP-hard delay-constrained least-cost routing problem.We propose a new framework to solve the problem and provide simple and efficient source routing heuristics from the model

through which one can always find a delay-constrained path if such a path exists.Computation complexity of our heuristics is

O(|V|

2

) and on-line complexity is

O(|V|)

.Simulation results show that our heuristics achieve good cost performance.Finally

we extend the model to routing problem under multiple QoS constraints.