TY - JOUR
T1 - Finding a least hop(s) path subject to multiple additive constraints
AU - Cheng, Gang
AU - Ansari, Nirwan
N1 - Funding Information:
This work has been supported in part by the National Science Foundation under Grant 0435250, and the New Jersey Commission on Science and Technology via the New Jersey Center for Wireless Networking and Internet Security.
PY - 2006/2/1
Y1 - 2006/2/1
N2 - In this paper, for the purpose of saving network resources, we first introduce and investigate a new problem referred to as the least hop(s) multiple additively constrained path (LHMACP) selection, which is NP-complete. Then, we propose the k-shortest paths Extended Bellman-Ford (k-EB) algorithm, which is capable of computing All Hops k-shortest Paths (AHKP) between a source and a destination. Through extensive analysis and simulations, we show that the heuristic algorithm, based on k-EB, is highly effective in finding a least hop path subject to multiple additive constraints with very low computational complexity; it achieves near 100% success ratio in finding a feasible path while minimizing its average hop count.
AB - In this paper, for the purpose of saving network resources, we first introduce and investigate a new problem referred to as the least hop(s) multiple additively constrained path (LHMACP) selection, which is NP-complete. Then, we propose the k-shortest paths Extended Bellman-Ford (k-EB) algorithm, which is capable of computing All Hops k-shortest Paths (AHKP) between a source and a destination. Through extensive analysis and simulations, we show that the heuristic algorithm, based on k-EB, is highly effective in finding a least hop path subject to multiple additive constraints with very low computational complexity; it achieves near 100% success ratio in finding a feasible path while minimizing its average hop count.
KW - Cost function
KW - Least hop(s)
KW - Multiple additively constrained QoS routing
KW - NP-complete
UR - http://www.scopus.com/inward/record.url?scp=31144436484&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=31144436484&partnerID=8YFLogxK
U2 - 10.1016/j.comcom.2005.05.009
DO - 10.1016/j.comcom.2005.05.009
M3 - Article
AN - SCOPUS:31144436484
SN - 0140-3664
VL - 29
SP - 392
EP - 401
JO - Computer Communications
JF - Computer Communications
IS - 3
ER -