Reliable routings in networks with generalized link failure events

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: Rajiv Ramaswami , Kumar N. Sivarajan, Optical networks: a practical perspective, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 2: Muriel Médard , Richard A. Barry , Steven G. Finn , Wenbo He , Steven S. Lumetta, Generalized loop-back recovery in optical mesh networks, IEEE/ACM Transactions on Networking (TON), v.10 n.1, p.153-164, February 2002 [doi>10.1109/90.986592]
• 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: Pallab Datta , Arun K. Somani, Diverse Routing for Shared Risk Resource Groups (SRRG) Failures in WDM Optical Networks, Proceedings of the First International Conference on Broadband Networks, p.120-129, October 25-29, 2004 [doi>10.1109/BROADNETS.2004.34]
• 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: Robert D. Carr , Srinivas Doddi , Goran Konjevod , Madhav Marathe, On the red-blue set cover problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.345-353, January 09-11, 2000, San Francisco, California, United States
• 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: Ruay-Shiung Chang , Shing-Jiuan Leu, The minimum labeling spanning trees, Information Processing Letters, v.63 n.5, p.277-282, Sept. 15, 1997 [doi>10.1016/S0020-0190(97)00127-0]
• 14: Sven O. Krumke , Hans-Christoph Wirth, On the minimum label spanning tree problem, Information Processing Letters, v.66 n.2, p.81-85, April 1998 [doi>10.1016/S0020-0190(98)00034-9]
• 15: Yingyu Wan , Guoliang Chert , Yinlong Xu, A note on the minimum label spanning tree, Information Processing Letters, v.84 n.2, p.99-101, 31 October 2002 [doi>10.1016/S0020-0190(02)00230-2]
• 16: D. S. Johnson, "Approximation algorithms for combinatorial problems," J. Comput. Syst. Sci., vol. 9, pp. 256-278, 1974.
• 17: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 18: Matthew Andrews , Lisa Zhang, Hardness of the undirected congestion minimization problem, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060633]
• 19: Xiao Zhou , Takao Nishizeki, The Edge-Disjoint Paths Problem is NP-Complete for Partial k-Trees, Proceedings of the 9th International Symposium on Algorithms and Computation, p.417-426, December 14-16, 1998
• 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: Thomas Erlebach , Danica Vukadinovic, New Results for Path Problems in Generalized Stars, Complete Graphs, and Brick Wall Graphs, Proceedings of the 13th International Symposium on Fundamentals of Computation Theory, p.483-494, August 22-24, 2001
• 23: Takao Nishizeki , Jens Vygen , Xiao Zhou, The edge-disjoint path problem is NP-complete for series-parallel graphs, Discrete Applied Mathematics, v.115 n.1-3, p.177-186, November 15, 2001 [doi>10.1016/S0166-218X(01)00223-2]
• 24: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 25: James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997 [doi>10.1145/258128.258201]
• 26: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 27: "ILOG CPLEX," CPLEX 8.1, 2004 [Online]. Available: http://www. cplex.com/

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
      G.1.6 Optimization
          Subjects: Integer programming; Linear programming

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Reliability, Theory

Keywords:
algorithms, network reliability, routing