article

On the complexity of and algorithms for finding the shortest path with a disjoint counterpart

Authors:

Xin HeAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 14, Issue 1

Pages 147 - 158

https://doi.org/10.1109/TNET.2005.863451

Published: 01 February 2006 Publication History

Abstract

Finding a disjoint path pair is an important component in survivable networks. Since the traffic is carried on the active (working) path most of the time, it is useful to find a disjoint path pair such that the length of the shorter path (to be used as the active path) is minimized. In this paper, we first address such a Min-Min problem. We prove that this problem is NP-complete in either single link cost (e.g., dedicated backup bandwidth) or dual link cost (e.g., shared backup bandwidth) networks. In addition, it is NP-hard to obtain a K-approximation to the optimal solution for any K > 1. Our proof is extended to another open question regarding the computational complexity of a restricted version of the Min-Sum problem in an undirected network with ordered dual cost links (called the MSOD problem). To solve the Min-Min problem efficiently, we introduce a novel concept called conflicting link set which provides insights into the so-called trap problem, and develop a divide-and-conquer strategy. The result is an effective heuristic for the Min-Min problem called COnflicting Link Exclusion (COLE), which can outperform other approaches in terms of both the optimality and running time. We also apply COLE to the MSOD problem to efficiently provide shared path protection and conduct comprehensive performance evaluation as well as comparison of various schemes for shared path protection. We show that COLE not only processes connection requests much faster than existing integer linear programming (ILP)-based approaches but also achieves a good balance among the active path length, bandwidth efficiency, and recovery time.

References

[1]

{1} E. Bouillet, J. F. Labourdette, R. Ramamurthy, and S. Chaudhuri, "Lightpath re-optimization in mesh optical networks," presented at the 7th Eur. Conf. Netw. Opt. Commun., Darmstadt, Germany, Jun. 2002.

[2]

{2} Y. Liu, D. Tipper, and P. Siripongwutikorn, "Approximating optimal spare capacity allocation by successive survivable routing," in Proc. IEEE INFOCOM, 2001, pp. 699-708.

[3]

{3} M. Sridharan, A. K. Somani, and M. Salapaka, "Approaches for capacity and revenue optimization in survivable WDM network," J. High Speed Netw., vol. 10, no. 2, pp. 109-125, Aug. 2001.

[4]

{4} J. Suurballe and R. Tarjan, "A quick method for finding shortest pairs of disjoint paths," Networks, vol. 14, pp. 325-336, 1984.

[5]

{5} J. W. Suurballe, "Disjoint paths in a network," Networks, vol. 4, pp. 125-145, 1974.

[6]

{6} D. A. Dunn, W. D. Grover, and M. H. MacGregor, "Comparison of k-shortest paths and maximum flow routing for network facility restoration," IEEE J. Select. Areas Commun., vol. 2, no. 1, pp. 88-99, Jan. 1994.

[7]

{7} Y. Liu, "Spare capacity allocation method, analysis and algorithms," Ph.D. dissertation, Sch. Inf. Sci., Univ. Pittsburgh, Pittsburgh, PA, 2001.

[8]

{8} P. Laborczi et al., "Solving asymmetrically weighted optimal or near-optimal disjoint path-pair for the survivable optical networks," presented at the 3rd Int. Workshop On Design Of Reliable Communication Networks (DRCN'01), Budapest, Hungary, Oct. 2001.

[9]

{9} C. Li, S. T. McCormick, and D. Simchi-Levi, "Finding disjoint paths with different path costs: Complexity and algorithms," Networks, vol. 22, pp. 653-667, 1992.

[10]

{10} C. Li, S. T. McCormick, and D. Simchi-Levi, "The complexity of finding two disjoint paths with min-max objective function," Discrete Appl. Math., vol. 26, no. 1, pp. 105-115, Jan. 1990.

[11]

{11} A. Sen, B. Shen, S. Bandyopadhyay, and J. Capone, "Survivability of lightwave networks path lengths in WDM protection scheme," J. High Speed Netw., vol. 10, no. 4, pp. 303-315, 2001.

[12]

{12} R. Bhandari, Survivable Networks: Algorithms for Diverse Routing. Norwell, MA: Kluwer, 1999.

[13]

{13} M. Kodialam and T. V. Lakshman, "Dynamic routing of bandwidth guaranteed tunnels with restoration," in Proc. IEEE INFOCOM, 2000, pp. 902-911.

[14]

{14} C. Qiao and D. Xu, "Distributed partial information management (DPIM) schemes for survivable networks-part I," in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 302-311.

[15]

{15} D. Xu, C. Qiao, and Y. Xiong, "An ultra-fast shared path protection scheme-distributed partial information management, part II," in Proc. IEEE ICNP, Paris, France, Nov. 2002, pp. 344-353.

[16]

{16} G. Li et al., "Efficient distributed path selection for shared restoration connections," in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 140-149.

[17]

{17} Y. Liu and D. Tipper, "Successive survivable routing for node failures," in Proc. IEEE GLOBECOM, 2001, pp. 2093-2097.

[18]

{18} J. Yen, "Finding the K shortest loopless paths in a network," Manag. Sci., vol. 17, no. 11, pp. 712-716, 1971.

[19]

{19} R. Bhandari, "Optimal diverse routing in telecommunications fiber networks," in Proc. IEEE INFOCOM, 1994, pp. 1498-1508.

[20]

{20} G. Li, B. Doverspike, and C. Kalmanek, "Fiber span failure protection in mesh optical networks," Opt. Netw. Mag., vol. 3, no. 3, pp. 21-31, May/Jun. 2002.

[21]

{21} J. Hu, "Diverse routing in optical mesh networks," IEEE Trans. Commun., vol. 51, no. 3, pp. 489-494, Mar. 2003.

[22]

{22} S. Even, A. Itai, and A. Shamir, "On the complexity of timetable and multicommodity problems," SIAM J. Comput., vol. 5, pp. 691-703, 1976.

[23]

{23} T. Corman, C. Leiserson, and R. Rivest, Introduction to Algorithms . Cambridge, MA: MIT Press, 1990.

[24]

{24} L. R. Ford and D. R. Fulkerson, Flows in Networks. Princeton, NJ: Princeton Univ. Press, 1962.

[25]

{25} S. Baroni, P. Bayvel, and R. J. Gibbens. (1998) On the number of wavelength in arbitrarily-connected wavelength-routed optical networks. Statistical Lab. Research Rep. 1998-7. Univ. Cambridge, Cambridge, U.K. {Online}. Available: http://www.statslab.cam.ac.uk/reports/1998/1998-7.pdf

[26]

{26} Y. Xiong, D. Xu, and C. Qiao, "Achieving fast and bandwidth efficient shared-path protection," J. Lightw. Technol., vol. 21, no. 2, pp. 365-371, Feb. 2003.

[27]

{27} E. Bouillet, J.-F. Labourdette, R. Ramamurthy, and S. Chaudhuri, "Enhanced algorithm cost model to control tradeoffs in provisioning shared mesh restored lightpaths," in Proc. Optical Fiber Commun. Conf., Mar. 2002, pp. 544-546.

Cited By

Guo LLi P(2021)On the complexity of and algorithms for detecting -length negative cost cyclesJournal of Combinatorial Optimization10.1007/s10878-018-00371-042:3(396-408)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s10878-018-00371-0
Yallouz JRottenstreich OBabarczi PMendelson AOrda A(2018)Minimum-Weight Link-Disjoint Node-“Somewhat Disjoint” PathsIEEE/ACM Transactions on Networking10.1109/TNET.2018.282391226:3(1110-1122)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2823912
Deng YGuo LHuang P(2018)Exact Algorithms for Finding Partial Edge-Disjoint PathsComputing and Combinatorics10.1007/978-3-319-94776-1_2(14-25)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1007/978-3-319-94776-1_2
Show More Cited By

Index Terms

On the complexity of and algorithms for finding the shortest path with a disjoint counterpart

Recommendations

Finding non-dominated bicriteria shortest pairs of disjoint simple paths

In this paper we introduce a method to compute non-dominated bicriteria shortest pairs, each including two disjoint simple paths. The method is based on an algorithm for ranking pairs of disjoint simple paths by non-decreasing order of cost, that is an ...
Paired many-to-many disjoint path covers in faulty hypercubes

A paired many-to-many k-disjoint path cover (k-DPC for short) of a graph is a set of k disjoint paths joining k distinct source-sink pairs that cover all the vertices of the graph. Extending the notion of DPC, we define a paired many-to-many bipartite k-...
k-Fewest Turn and Shortest Path Algorithm based on Stroke Graph
IWCTS '23: Proceedings of the 16th ACM SIGSPATIAL International Workshop on Computational Transportation Science

This paper proposes the k-fewest turn and shortest path (k-FTSP) algorithm to solve the problem of route search in web mapping systems. Conventional shortest path search has a problem in that the generated shortest path may include many right and/or left ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 14, Issue 1

February 2006

231 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 February 2006

Published in TON Volume 14, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
650
Total Downloads

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

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Guo LLi P(2021)On the complexity of and algorithms for detecting -length negative cost cyclesJournal of Combinatorial Optimization10.1007/s10878-018-00371-042:3(396-408)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s10878-018-00371-0
Yallouz JRottenstreich OBabarczi PMendelson AOrda A(2018)Minimum-Weight Link-Disjoint Node-“Somewhat Disjoint” PathsIEEE/ACM Transactions on Networking10.1109/TNET.2018.282391226:3(1110-1122)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2823912
Deng YGuo LHuang P(2018)Exact Algorithms for Finding Partial Edge-Disjoint PathsComputing and Combinatorics10.1007/978-3-319-94776-1_2(14-25)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1007/978-3-319-94776-1_2
Yallouz JOrda A(2017)Tunable QoS-Aware Network SurvivabilityIEEE/ACM Transactions on Networking10.1109/TNET.2016.260634225:1(139-149)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TNET.2016.2606342
Guo LLi P(2017)On the Complexity of Detecting k-Length Negative Cost CyclesCombinatorial Optimization and Applications10.1007/978-3-319-71150-8_21(240-250)Online publication date: 16-Dec-2017
https://dl.acm.org/doi/10.1007/978-3-319-71150-8_21
Guo L(2016)Efficient approximation algorithms for computing k disjoint constrained shortest pathsJournal of Combinatorial Optimization10.1007/s10878-015-9934-232:1(144-158)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s10878-015-9934-2
Guo LShen HLiao K(2015)Improved approximation algorithms for computing $$k$$k disjoint paths subject to two constraintsJournal of Combinatorial Optimization10.1007/s10878-013-9693-x29:1(153-164)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1007/s10878-013-9693-x
Xu MHou MWang DYang J(2013)An efficient critical protection scheme for intra-domain routing using link characteristicsComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2012.09.00657:1(117-133)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1016/j.comnet.2012.09.006
Omran MSack JZarrabi-Zadeh H(2013)Finding paths with minimum shared edgesJournal of Combinatorial Optimization10.1007/s10878-012-9462-226:4(709-722)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1007/s10878-012-9462-2
Summa BTierny JPascucci V(2012)Panorama weavingACM Transactions on Graphics10.1145/2185520.218557931:4(1-11)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1145/2185520.2185579
Show More Cited By

View Options

Login options

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

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents