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

Gang Cheng, Nirwan Ansari

Research output: Contribution to journalArticle

3 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 languageEnglish (US)
Pages (from-to)392-401
Number of pages10
JournalComputer Communications
Volume29
Issue number3
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Finding a least hop(s) path subject to multiple additive constraints'. Together they form a unique fingerprint.

  • Cite this