On selecting the cost function for source routing

Gang Cheng; Nirwan Ansari

doi:10.1016/j.comcom.2006.06.001

On selecting the cost function for source routing

Gang Cheng
, Nirwan Ansari

Electrical and Computer Engineering

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

2 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	3602-3608
Number of pages	7
Journal	Computer Communications
Volume	29
Issue number	17
DOIs	https://doi.org/10.1016/j.comcom.2006.06.001
State	Published - Nov 8 2006

All Science Journal Classification (ASJC) codes

Computer Networks and Communications

Keywords

Cost function
Multiple additively constrained QoS routing
NP-complete

Access to Document

10.1016/j.comcom.2006.06.001

Cite this

@article{b0758aead6c54b95bd10ff723412b479,

title = "On selecting the cost function for source routing",

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

keywords = "Cost function, 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 = nov,

day = "8",

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

language = "English (US)",

volume = "29",

pages = "3602--3608",

journal = "Computer Communications",

issn = "0140-3664",

publisher = "Elsevier B.V.",

number = "17",

}

TY - JOUR

T1 - On selecting the cost function for source routing

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/11/8

Y1 - 2006/11/8

N2 - 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.

AB - 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.

KW - Cost function

KW - Multiple additively constrained QoS routing

KW - NP-complete

UR - https://www.scopus.com/pages/publications/33750294775

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

U2 - 10.1016/j.comcom.2006.06.001

DO - 10.1016/j.comcom.2006.06.001

M3 - Article

AN - SCOPUS:33750294775

SN - 0140-3664

VL - 29

SP - 3602

EP - 3608

JO - Computer Communications

JF - Computer Communications

IS - 17

ER -

On selecting the cost function for source routing

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this