article

On selecting the cost function for source routing

Authors:

Gang Cheng,

Nirwan AnsariAuthors Info & Claims

Computer Communications, Volume 29, Issue 17

Pages 3602 - 3608

https://doi.org/10.1016/j.comcom.2006.06.001

Published: 01 November 2006 Publication History

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.

References

[1]

Cheng, G. and Ansari, N., A theoretical framework for selecting the cost function for source routing. Proceedings of IEEE ICC'03. v1. 631-635.

Google Scholar

[2]

Chen, S. and Nahsted, K., An overview of quality of service routing for next-generation high-speed network: problems and solutions. IEEE Network. v12 ino. 6. 64-79.

Digital Library

Google Scholar

[3]

Shaik, A., Rexford, J. and Shin, K.G., Evaluating the impact of stale link state on quality-of-service routing. IEEE/ACM Transactions on Networking. v9 ino. 2. 162-176.

Digital Library

Google Scholar

[4]

Guerin, R. and Orda, A., QoS based routing in networks with inaccurate information: theory and algorithms. Proceedings of the INFOCOM'97. 75-83.

Digital Library

Google Scholar

[5]

Wang, J., Wang, W., Chen, J. and Chen, S., A randomized QoS routing algorithm on networks with inaccurate link-state information. Proceeding of WCC-ICCT 2000. v2. 1617-1622.

Google Scholar

[6]

Wang, Z. and Crowcroft, J., Quality of Service routing for supporting multimedia applications. IEEE Journal on Selected Areas on Communications. v14 ino. 7. 1228-1234.

Digital Library

Google Scholar

[7]

Korkmaz, T., Krunz, M. and Tragoudas, S., An efficient algorithms for finding a path subject to two additive constraints. Proceedings of the ACM SIGMETRICS'2000. 318-327.

Digital Library

Google Scholar

[8]

Juttner, A., Szyiatovszki, B., Mecs, I. and Rajko, Z., Lagrange relaxation based method for the QoS routing problem. Proceedings of IEEE INFOCOM 2001. v2. 859-868.

Crossref

Google Scholar

[9]

L. Guo, I. Matta, Search space reduction in QoS routing, Proceedings of 19th IEEE International Conference on Distributed Computing Systems, 1999, pp. 142-149.

Digital Library

Google Scholar

[10]

Yuan, X., Heuristic algorithm for multiconstrained quality-of-service routing. IEEE/ACM Transactions on Networking. v10 i2. 244-256.

Digital Library

Google Scholar

[11]

Orda, A. and Sprintson, A., Precomputation schemes for QoS routing. IEEE/ACM Transactions on Networking. 578-591.

Digital Library

Google Scholar

[12]

Korkmaz, T. and Krunz, M., Routing multimedia traffic with QoS guarantees. IEEE Transactions on Multimedia. v5 i3. 429-443.

Digital Library

Google Scholar

[13]

Liu, G. and Ramakrishnan, K.G., A*Prune: an algorithm for finding K shortest paths subject to multiple constraints. Proceedings of IEEE INFOCOM 2001. v2. 743-749.

Google Scholar

Recommendations

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

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 ...
A new cost function for improving Anypath routing performance of VANETs in highways

Instability of wireless networks and high mobility of vehicles make effective and reliable delivery of packets in VANETs a challenging issue. Anypath routing is proposed to tackle this issue in multi hop VANET communications. Link stability and quality ...
Dynamic Routing and Wavelength Assignment Using Cost Based Heuristics in WDM Optical Networks
Abstract
Dynamic routing and wavelength assignment problem in optical networks is a two-step problem that is influenced by the choice of a successful optimal path selection and wavelength assignment. Proper selection techniques reduce the number of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Computer Communications Volume 29, Issue 17

November, 2006

324 pages

ISSN:0140-3664

Issue’s Table of Contents

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 November 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Recommendations

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

A new cost function for improving Anypath routing performance of VANETs in highways

Dynamic Routing and Wavelength Assignment Using Cost Based Heuristics in WDM Optical Networks

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations