Title :
Achieving 100% success ratio in finding the delay constrained least cost path
Author :
Cheng, Gang ; Ansari, Nirwan
Author_Institution :
Dept. of Electr. & Comput. Eng., New Jersey Inst. of Technol., Newark, NJ, USA
fDate :
29 Nov.-3 Dec. 2004
Abstract :
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, is proposed. It can achieve 100% success ratio in finding the delay constrained least cost (DCLC) path with very low average computational complexity. The underlying concept is that since DIAHKP is a k-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 achieving 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.
Keywords :
computational complexity; iterative methods; minimisation; quality of service; telecommunication network routing; Bellman-Ford algorithm; QoS routing; computational complexity; delay constrained least cost path; dual iterative all hops k-shortest paths algorithm; optimal feasible path; success ratio; Analytical models; Bandwidth; Computational complexity; Computational modeling; Computer networks; Cost function; Delay; Iterative algorithms; Routing; Upper bound;
Conference_Titel :
Global Telecommunications Conference, 2004. GLOBECOM '04. IEEE
Print_ISBN :
0-7803-8794-5
DOI :
10.1109/GLOCOM.2004.1378234