Achieving 100% success ratio in finding the delay constrained least cost path

Gang Cheng, Nirwan Ansari

Research output: Contribution to conferencePaperpeer-review

6 Scopus citations

Abstract

In this paper, we introduce an Iterative All Hops k-shortest Paths (IAHKP) algorithm that is capable of iteratively computing all hops k-shortest path (AHKP) from a source to a destination. Based on IAHKP, a high performance algorithm, Dual Iterative All Hops k-shortest Paths (DIAHKP) algorithm, that can achieve 100% success ratio in finding the Delay Constrained Least Cost (DCLC) path with very low average computational complexity is proposed. The underlining concept is that since DIAHKP is a &-shortest-paths-based solution to DCLC, implying that its computational complexity increases with k, we can minimize its computational complexity by adaptively minimizing k, while achiving 100% success ratio in finding the optimal feasible path. Through extensive analysis and simulations, we show that DIAHKP is highly effective and flexible. By setting a very small upper bound to k (k=1,2), DIAHKP still can achieve very satisfactory performance. With only an average computational complexity of twice that of the standard Bellman-Ford algorithm, DIAHKP achieves 100% success ratio in finding the optimal feasible path in the typical 32-node network.

Original languageEnglish (US)
Pages1505-1509
Number of pages5
StatePublished - Dec 1 2004
EventGLOBECOM'04 - IEEE Global Telecommunications Conference - Dallas, TX, United States
Duration: Nov 29 2004Dec 3 2004

Other

OtherGLOBECOM'04 - IEEE Global Telecommunications Conference
Country/TerritoryUnited States
CityDallas, TX
Period11/29/0412/3/04

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Keywords

  • All hops k-shortest paths selection (AHKP)
  • Delay constrained least cost (DCLC)
  • NP-complete

Fingerprint

Dive into the research topics of 'Achieving 100% success ratio in finding the delay constrained least cost path'. Together they form a unique fingerprint.

Cite this