Finding a least hop(s) path subject to multiple additive constraints

Gang Cheng; Nirwan Ansari

doi:10.1016/j.comcom.2005.05.009

Finding a least hop(s) path subject to multiple additive constraints

Gang Cheng
, Nirwan Ansari

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	392-401
Number of pages	10
Journal	Computer Communications
Volume	29
Issue number	3
DOIs	https://doi.org/10.1016/j.comcom.2005.05.009
State	Published - Feb 1 2006

All Science Journal Classification (ASJC) codes

Computer Networks and Communications

Keywords

Cost function
Least hop(s)
Multiple additively constrained QoS routing
NP-complete

Access to Document

10.1016/j.comcom.2005.05.009

Cite this

@article{4da7a47d09e749599e0d62b50df0849b,

title = "Finding a least hop(s) path subject to multiple additive constraints",

abstract = "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.",

keywords = "Cost function, Least hop(s), Multiple additively constrained QoS routing, NP-complete",

author = "Gang Cheng and Nirwan Ansari",

note = "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. ",

year = "2006",

month = feb,

day = "1",

doi = "10.1016/j.comcom.2005.05.009",

language = "English (US)",

volume = "29",

pages = "392--401",

journal = "Computer Communications",

issn = "0140-3664",

publisher = "Elsevier B.V.",

number = "3",

}

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 - https://www.scopus.com/pages/publications/31144436484

UR - https://www.scopus.com/pages/publications/31144436484#tab=citedBy

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 -

Finding a least hop(s) path subject to multiple additive constraints

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this