skip to main content
article

Reliable routings in networks with generalized link failure events

Published: 01 December 2008 Publication History

Abstract

We study routing problems in networks that require guaranteed reliability against multiple correlated link failures. We consider two different routing objectives: The first ensures "local reliability," i.e., the goal is to route so that each connection in the network is as reliable as possible. The second ensures "global reliability," i.e., the goal is to route so that as few as possible connections are affected by any possible failure. We exhibit a trade-off between the two objectives and resolve their complexity and approximability for several classes of networks. Furthermore, we propose approximation algorithms and heuristics. We perform experiments to evaluate the heuristics against optimal solutions that are obtained using an integer linear programming solver. We also investigate up to what degree the routing trade-offs occur in randomly generated instances.

References

[1]
R. Ramaswami and K. N. Sivarajan, Optical Networks: A Practical Perspective, 2nd ed. San Francisco, CA: Morgan Kaufmann, 2002.
[2]
M. Médard, R. A. Barry, S. G. Finn, W. He, and S. Lumetta, "Generalized loop-back recovery in optical mesh networks," IEEE/ACM Trans. Networking, vol. 10, no. 1, pp. 153-164, Feb. 2002.
[3]
Y. Xin and G. N. Rouskas, "A study of path protection in large-scale optical networks," Photonic Network Commun., vol. 7, no. 3, pp. 267-278, 2004.
[4]
H. Choi, S. Subramaniam, and H.-A. Choi, "On double-link failure recovery in WDM optical networks," in Proc. IEEE INFOCOM, 2002, vol. 2, pp. 808-816.
[5]
S. Chaudhuri, G. Hjálmtysson, and J. Yates, "Control of lightpaths in an optical network," IETF Internet Draft, Mar. 2000.
[6]
J. Hu, "Diverse routing in mesh optical networks," IEEE Trans. Commun., vol. 51, no. 3, pp. 489-494, Mar. 2003.
[7]
G. Li, C. Kalmanek, and R. Doverspike, "Fiber span failure protection in mesh optical networks," Opt. Netw. Mag., vol. 3, no. 3, 2002.
[8]
P. Datta and A. K. Somani, "Diverse routing for shared risk resource groups (SRRG) failures in WDM optical networks," in Proc. 1st Int. Conf. Broadband Networks (BROADNETS'04), 2004, pp. 120-129.
[9]
S. Yuan, S. Varma, and J. P. Jue, "Minimum-color path problems for reliability in mesh networks," in Proc. IEEE INFOCOM, 2005.
[10]
C. Papadimitriou, Computational Complexity. Reading, MA: Addison-Wesley, 1994.
[11]
R. D. Carr, S. Doddi, G. Konjevod, and M. Marathe, "On the red-blue set cover problem," in Proc. 11th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA'00), 2000, pp. 345-353.
[12]
H.-C. Wirth, "Multicriteria approximation of network design and network upgrade problems," Ph.D. dissertation, University of Würzburg, Würzburg, Germany, 2001.
[13]
R.-S. Chang and S.-J. Leu, "The minimum labeling spanning trees," Inf. Process. Lett., vol. 63, no. 5, pp. 277-282, 1997.
[14]
S. Krumke and H.-C. Wirth, "On the minimum label spanning tree problem," Inf. Process. Lett., vol. 66, no. 2, pp. 81-85, 1998.
[15]
Y. Wan, G. Chen, and Y. Xu, "A note on the minimum label spanning tree," Inf. Process. Lett., vol. 84, pp. 99-101, 2002.
[16]
D. S. Johnson, "Approximation algorithms for combinatorial problems," J. Comput. Syst. Sci., vol. 9, pp. 256-278, 1974.
[17]
R. Raz and S. Safra, "A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP," in Proc. 29th Annu. ACM Symp. Theory Comput. (STOC '97), 1997, pp. 475-484.
[18]
M. Andrews and L. Zhang, "Hardness of the undirected congestion minimization problem," in Proc. 37th Annu. ACM Symp. Theory Comput. (STOC '05), 2005.
[19]
X. Zhou and T. Nishizeki, "The edge-disjoint paths problem is NP-complete for partial k-trees," in Proc. 9th Annu. Int. Symp. Algorithms Comput. (ISAAC '98), 1998, ser. LNCS 1533, pp. 417-426.
[20]
M. Middendorf and F. Pfeiffer, "On the complexity of the disjoint paths problem," Combinatorica, vol. 13, no. 1, pp. 97-107, 1993.
[21]
M. E. Kramer and J. van Leeuwen, "The complexity of wire routing and finding the minimum area layouts for arbitrary VLSI circuits," in Advances in Computing Research; VLSI Theory, F. P. Preparata, Ed. Greenwich, CT: JAI Press, 1984, vol. 2, pp. 129-146.
[22]
T. Erlebach and D. Vukadinovic, "New results for path problems in generalized stars, complete graphs, and brick wall graphs," in Proc. 13th Int. Symp. Fundamentals Comput. Theory (FCT'01), 2001, ser. LNCS 2138, pp. 483-494.
[23]
T. Nishizeki, J. Vygen, and X. Zhou, "The edge-disjoint paths problem is NP-complete for series-parallel graphs," Discrete Appl. Math., vol. 115, pp. 177-186, 2001.
[24]
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: Freeman, 1979.
[25]
J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts, "On-line routing of virtual circuits with applications to load balancing and machine scheduling," J. ACM, vol. 44, no. 3, pp. 486-504, 1997.
[26]
K. Mehlhorn and S. Näher, LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge, U.K.: Cambridge Univ. Press, 1999.
[27]
"ILOG CPLEX," CPLEX 8.1, 2004 {Online}. Available: http://www. cplex.com/

Cited By

View all
  • (2015)Survivable Cloud Network Mapping for Disaster Recovery SupportIEEE Transactions on Computers10.1109/TC.2014.236054264:8(2353-2366)Online publication date: 1-Aug-2015
  • (2014)Multi-Path Algorithms for minimum-colour path problems with applications to approximating barrier resilienceTheoretical Computer Science10.1016/j.tcs.2014.04.009553:C(74-90)Online publication date: 1-Dec-2014
  • (2010)Characterizing the spread of correlated failures in large wireless networksProceedings of the 29th conference on Information communications10.5555/1833515.1833771(1882-1890)Online publication date: 14-Mar-2010

Index Terms

  1. Reliable routings in networks with generalized link failure events

                          Recommendations

                          Comments

                          Information & Contributors

                          Information

                          Published In

                          cover image IEEE/ACM Transactions on Networking
                          IEEE/ACM Transactions on Networking  Volume 16, Issue 6
                          December 2008
                          248 pages

                          Publisher

                          IEEE Press

                          Publication History

                          Published: 01 December 2008
                          Revised: 24 June 2007
                          Received: 20 February 2006
                          Published in TON Volume 16, Issue 6

                          Author Tags

                          1. algorithms
                          2. network reliability
                          3. routing

                          Qualifiers

                          • Article

                          Contributors

                          Other Metrics

                          Bibliometrics & Citations

                          Bibliometrics

                          Article Metrics

                          • Downloads (Last 12 months)0
                          • Downloads (Last 6 weeks)0
                          Reflects downloads up to 30 Jan 2025

                          Other Metrics

                          Citations

                          Cited By

                          View all
                          • (2015)Survivable Cloud Network Mapping for Disaster Recovery SupportIEEE Transactions on Computers10.1109/TC.2014.236054264:8(2353-2366)Online publication date: 1-Aug-2015
                          • (2014)Multi-Path Algorithms for minimum-colour path problems with applications to approximating barrier resilienceTheoretical Computer Science10.1016/j.tcs.2014.04.009553:C(74-90)Online publication date: 1-Dec-2014
                          • (2010)Characterizing the spread of correlated failures in large wireless networksProceedings of the 29th conference on Information communications10.5555/1833515.1833771(1882-1890)Online publication date: 14-Mar-2010

                          View Options

                          Login options

                          Full Access

                          View options

                          PDF

                          View or Download as a PDF file.

                          PDF

                          eReader

                          View online with eReader.

                          eReader

                          Figures

                          Tables

                          Media

                          Share

                          Share

                          Share this Publication link

                          Share on social media