skip to main content
article

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

Published: 01 August 2009 Publication History

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]
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network flows: Theory, Algorithm, and Applications. Englewood Cliffs, NJ: Prentice Hall, 1993.
[2]
J. A. Bondy and U. S. R. Murthy, Graph Theory With Applications. New York: American Elsevier Pub., 1976.
[3]
T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms . Englewood Cliffs, NJ: Prentice Hall, 1998.
[4]
CPLEX. {Online}. Available: http://www.cplex.com.
[5]
Z. Galil and G. F. Italiano, "Maintaining the 3-edge-connected components of a graph on-line," SIAM J. Comput., vol. 22, no. 1, pp. 11-28, 1993.
[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]
V. Raghavan and A. Tripathi, "Sequential diagnosability is Co-NP complete," IEEE Trans. Comput., vol. 40, pp. 584-595, May 1991.
[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]
H. Zeng, C. Huang, and A. Vukovic, "Monitoring cycles for fault detection in meshed all-optical networks," in Proc. Int. Conf. Parallel Processing Workshop (ICPP), Aug. 2004, vol. 1, pp. 434-439.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 17, Issue 4
August 2009
337 pages

Publisher

IEEE Press

Publication History

Published: 01 August 2009
Revised: 13 October 2007
Received: 16 February 2007
Published in TON Volume 17, Issue 4

Author Tags

  1. all-optical networks
  2. fault localization

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)1
Reflects downloads up to 07 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Low-cost crossed probing path planning for network failure localizationWorld Wide Web10.1007/s11280-023-01206-726:6(3891-3914)Online publication date: 1-Nov-2023
  • (2022)Intelligent failure localization and maintenance of network based on reliabilityThe Journal of Supercomputing10.1007/s11227-022-04653-779:1(389-418)Online publication date: 11-Jul-2022
  • (2020)A Machine Learning-Based Framework to Estimate the Lifetime of Network Line CardsNOMS 2020 - 2020 IEEE/IFIP Network Operations and Management Symposium10.1109/NOMS47738.2020.9110455(1-5)Online publication date: 20-Apr-2020
  • (2017)Taming both predictable and unpredictable link failures for network tomographyProceedings of the ACM Turing 50th Celebration Conference - China10.1145/3063955.3063990(1-10)Online publication date: 12-May-2017
  • (2017)Novel Survivable Logical Topology Routing by Logical Protecting Spanning Trees in IP-Over-WDM NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2016.263936225:3(1673-1685)Online publication date: 1-Jun-2017
  • (2017)JMAWRPhotonic Network Communications10.1007/s11107-017-0692-134:2(181-192)Online publication date: 1-Oct-2017
  • (2017)Unambiguous switching link group failure localization in all-optical networksNetworks10.1002/net.2177970:4(327-341)Online publication date: 1-Dec-2017
  • (2016)Discrete Path Selection and Entropy Based Sensor Node Failure Detection in Wireless Sensor NetworksCybernetics and Information Technologies10.1515/cait-2016-003916:3(137-153)Online publication date: 1-Sep-2016
  • (2015)Link Scanner: Faulty Link Detection for Wireless Sensor NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2015.242135314:8(4428-4438)Online publication date: 10-Aug-2015
  • (2015)Sherlock Is Around: Detecting Network Failures with Local Evidence FusionIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2014.232075026:5(1430-1440)Online publication date: 7-Apr-2015
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media