Minimum Cost Paths Subject to Minimum Vulnerability for Reliable Communications

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Bing Yang Articles by Mei Yang Articles by Jianping Wang Articles by S.Q. Zheng

8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05)

Las Vegas, Nevada, USA

December 07-December 09

ISBN: 0-7695-2509-1

	ASCII Text	x
	Bing Yang, Mei Yang, Jianping Wang, S.Q. Zheng, "Minimum Cost Paths Subject to Minimum Vulnerability for Reliable Communications," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 334-339, 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05), 2005.

	BibTex	x
	@article{ 10.1109/ISPAN.2005.60, author = {Bing Yang and Mei Yang and Jianping Wang and S.Q. Zheng}, title = {Minimum Cost Paths Subject to Minimum Vulnerability for Reliable Communications}, journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on}, volume = {0}, year = {2005}, issn = {1087-4089}, pages = {334-339}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.2005.60}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel Architectures, Algorithms, and Networks, International Symposium on TI - Minimum Cost Paths Subject to Minimum Vulnerability for Reliable Communications SN - 1087-4089 SP334 EP339 A1 - Bing Yang, A1 - Mei Yang, A1 - Jianping Wang, A1 - S.Q. Zheng, PY - 2005 KW - Networks KW - graph KW - algorithm KW - protection KW - reliability KW - survivability KW - disjoint paths KW - shortest path KW - complexity KW - network flow KW - minimum cost network flow. VL - 0 JA - Parallel Architectures, Algorithms, and Networks, International Symposium on ER -

Bing Yang, Cisco Systems, Richardson, TX

Mei Yang, UNLV

Jianping Wang, Georgia Southern University, Statesboro, GA

S.Q. Zheng, University of Texas at Dallas, Richardson, TX

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2005.60

In real networks, disjoint paths are needed for providing protection against single link/node failure. When disjoint paths cannot be found, an alternative solution is to find paths with the minimum shared links/nodes. In the literature, there is little work addressing this problem. In this paper, defining vulnerability as the number of times a link/node is shared among different paths, we consider the problems of finding k paths with minimum edge/node vulnerability. We study three problems and propose polynomial algorithms to solve these problems. The work presented in this paper can be directly applied to a number of network applications such as reliable unicast/multicast communications, reliable client-server communications, protection for the dual-homing architecture, etc.

Index Terms:

Networks, graph, algorithm, protection, reliability,survivability, disjoint paths, shortest path, complexity, network flow, minimum cost network flow.

Citation:

Bing Yang, Mei Yang, Jianping Wang, S.Q. Zheng, "Minimum Cost Paths Subject to Minimum Vulnerability for Reliable Communications," ispan, pp.334-339, 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05), 2005

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.