Single-link failure detection in all-optical networks using monitoring cycles and paths

ABSTRACT

In this paper, we consider the problem of fault localization in all-optical networks. We introduce the concept of monitoring cycles (MCs) and monitoring paths (MPs) for unique identification of single-link failures. MCs and MPs are required to pass through one or more monitoring locations. They are constructed such that any single-link failure results in the failure of a unique combination of MCs and MPs that pass through the monitoring location(s). For a network with only one monitoring location, we prove that three-edge connectivity is a necessary and sufficient condition for constructing MCs that uniquely identify any single-link failure in the network. For this case, we formulate the problem of constructing MCs as an integer linear program (ILP). We also develop heuristic approaches for constructing MCs in the presence of one or more monitoring locations. For an arbitrary network (not necessarily three-edge connected), we describe a fault localization technique that uses both MPs and MCs and that employs multiple monitoring locations. We also provide a linear-time algorithm to compute the minimum number of required monitoring locations. Through extensive simulations, we demonstrate the effectiveness of the proposed monitoring technique.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 3: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 4: CPLEX. [Online]. Available: http://www.cplex.com.
• 5: Zvi Galil , Giuseppe F. Italiano, Maintaining the 3-edge-connected components of a graph on-line, SIAM Journal on Computing, v.22 n.1, p.11-28, Feb. 1993 [doi>10.1137/0222002]
• 6: Y. Hamazumi, M. Koga, K. Kawai, H. Ichino, and K. Sato, "Optical path fault management in layered networks," in Proc. IEEE Globecom, Nov. 1998, vol. 4, pp. 2309-2314.
• 7: N. Harvey, M. Patrascu, Y. Wen, S. Yekhanin, and V. W. S. Chan, "Non-adaptive fault diagnosis for all-optical networks via combinatorial group testing on graphs," in Proc. IEEE INFOCOM, May 2007.
• 8: J. Hopcraft and R. E. Tarjan, "Dividing a graph into triconnected components," SIAM J. Comput., vol. 2, no. 3, pp. 135-158, 1973.
• 9: S. Maclane, "A structural characterization of planar combinatorial graphs," DUKE Math J., vol. 3, no. 3, pp. 460-472, 1937.
• 10: Vijay Raghavan , Anand Tripathi, Sequential Diagnosability is Co-NP Complete, IEEE Transactions on Computers, v.40 n.5, p.584-595, May 1991 [doi>10.1109/12.88482]
• 11: B. M. Waxman, "Routing of multipoint connections," IEEE J. Sel. Areas Commun., vol. 69, pp. 1617-1622, Dec. 1988.
• 12: Y. Wen, V. W. S. Chan, and L. Zheng, "Efficient fault diagnosis algorithms for all-optical WDM networks with probabilistic link failures," J. Lightw. Technol., vol. 23, no. 10, pp. 3358-3371, Oct. 2005.
• 13: Hongqing Zeng , Changcheng Huang , Alex Vukovic, Monitoring Cycles for Fault Detection in Meshed All-Optical Networks, Proceedings of the 2004 International Conference on Parallel Processing Workshops, p.434-439, August 15-18, 2004 [doi>10.1109/ICPPW.2004.59]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM)
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming; Integer programming
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Performance

Keywords:
all-optical networks, fault localization