A New Heuristics for Finding the Delay Constrained Least Cost Path

Gang Cheng, Nirwan Ansari

Research output: Contribution to conferencePaperpeer-review

5 Scopus citations

Abstract

In this paper, we investigate the problem of finding the Delay Constrained Least Cost path (DCLC) in a network, which is NT-complete and has been extensively studied. Many proposed algorithms tackle this problem by transforming it into the shortest path selection problem or the k-shortest paths selection problem, which are P-complete, with an integrated weight function that maps the delay and cost each link into a single weight. However, they suffer from either high computational complexity or low success ratio in finding the optimal paths (the least cost path satisfying a given delay constraint). Based on the Extended Bellman-Ford (EB) algorithm, we propose a high performance algorithm, Dual Extended Bellman-Ford (DEB) algorithm, which achieves a high success ratio in finding the least cost path subject to a delay constraint with low computational complexity. Extensive simulations show that DEB outperforms its contender on all the worst-case computational complexity, average cost of the solutions, and the success ratio in finding the delay constrained least cost path.

Original languageEnglish (US)
Pages3711-3715
Number of pages5
StatePublished - Dec 1 2003
EventIEEE Global Telecommunications Conference GLOBECOM'03 - San Francisco, CA, United States
Duration: Dec 1 2003Dec 5 2003

Other

OtherIEEE Global Telecommunications Conference GLOBECOM'03
CountryUnited States
CitySan Francisco, CA
Period12/1/0312/5/03

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering
  • Global and Planetary Change

Keywords

  • Delay Constrained Least Cost Path
  • Extended Bellman-Ford algorithm
  • LAgrange Relaxation based Aggregated Cost (LARAC)

Fingerprint Dive into the research topics of 'A New Heuristics for Finding the Delay Constrained Least Cost Path'. Together they form a unique fingerprint.

Cite this