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 language | English (US) |
|---|---|
| Pages | 3711-3715 |
| Number of pages | 5 |
| State | Published - 2003 |
| Event | IEEE Global Telecommunications Conference GLOBECOM'03 - San Francisco, CA, United States Duration: Dec 1 2003 → Dec 5 2003 |
Other
| Other | IEEE Global Telecommunications Conference GLOBECOM'03 |
|---|---|
| Country/Territory | United States |
| City | San Francisco, CA |
| Period | 12/1/03 → 12/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)