Computing Delay Constrained Paths from One Source to Single/All Destinations

Abstract — Delay-constrained least cost (DCLC) path problem is a typical delay sensitive quality of service (QoS) routing prob-lem. In this paper, we provide an explicit expression of the time complexity of a previously proposed heuristic NR DCLC when delay and cost are integers. The expression indicates it com-pares favorably with other heuristics. We further describe a heuristic NR DCLC 1toN to compute the DCLC paths from one source to all destinations satisfying the delay constraint. Simula-tions demonstrate that NR DCLC 1toN can always find delay con-strained paths with lower costs than the delay scaling algorithm (DSA), which is so far the best heuristic for such problem. Even though NR DCLC 1toN needs higher execution time than DSA in some cases, it runs much faster than DSA in many other cases such as when the delay constraint has to be strictly guaranteed or when the delay and cost are distributed on large intervals. I