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 - http://www.scopus.com/inward/record.url?scp=33750294775&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33750294775&partnerID=8YFLogxK
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 -