On selecting the cost function for source routing

Gang Cheng, Nirwan Ansari

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


Many proposed source routing algorithms tackle the Multiple Additively Constrained Path (MACP) selection, an NP-complete problem, by transforming it into the shortest path selection problem, which is P-complete, with an integrated cost function that maps the multi-constraints of each link into a single cost. However, how to select an appropriate cost function is an important issue that has rarely been addressed in literature. In this paper, we provide a theoretical framework for picking a cost function that can improve the performance of source routing in terms of complexity, convergence, and probability of finding a feasible path.

Original languageEnglish (US)
Pages (from-to)3602-3608
Number of pages7
JournalComputer Communications
Issue number17
StatePublished - Nov 8 2006

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications


  • Cost function
  • Multiple additively constrained QoS routing
  • NP-complete


Dive into the research topics of 'On selecting the cost function for source routing'. Together they form a unique fingerprint.

Cite this