Abstract

This paper considers the problem of out-of-band failure localization in all-optical mesh networks using bidirectional monitoring trails (bm-trails), where every possible link set with up to $d$ arbitrary links is considered as a shared risk link group (SRLG). With the SRLG scenario, the bm-trail allocation problem is firstly formulated, which includes the phases of code assignment and bm-trail formation. In the first phase, each SRLG is uniquely coded by assigning each link with a nonadaptive $\bar{d}$-separable combinatorial group testing code. Then, the second phase manipulates a sophisticated yet efficient bm-trail formation process through a novel greedy code-swapping mechanism, such that any SRLG failure can be unambiguously localized by collecting the alarms of the interrupted bm-trails. The algorithm prototype can be found in . Extensive simulation is conducted on hundreds of randomly generated planar topologies to verify the proposed approach in terms of the number of required bm-trails and the computational efficiency. Our approach is compared with previously reported counterparts, by which its merits are further demonstrated.

© 2011 IEEE

PDF Article

References

  • View by:
  • |
  • |

  1. J. Tapolcai, Web page on m-trail/tree design: Simulation environments, examples and technical reports. http://opti.tmit.bme.hu/~tapolcai/mtrail.
  2. I. Tomkos, "Dynamically reconfigurable transparent optical networking based on cross-layer optimization," Proc. Int. Conf. Transparent Opt. Netw. (2007) pp. 327-327.
  3. M. Maeda, "Management and control of transparent optical networks," IEEE J. Sel. Areas Commun. 16, 1008-1023 (1998).
  4. D. Zhou, S. Subramaniam, "Survivability in optical networks," IEEE Netw. 14, 16-23 (2000).
  5. P. Demeester, M. Gryseels, A. Autenrieth, C. Brianza, L. Castagna, G. Signorelli, R. Clemenfe, M. Ravera, A. Jajszczyk, D. Janukowicz, K. Van Doorselaere, Y. Harada, "Resilience in multilayer networks," IEEE Commun. Mag. 37, 70-76 (1999).
  6. C. Mas, I. Tomkos, O. Tonguz, "Failure location algorithm for transparent optical networks," IEEE J. Sel. Areas Commun. 23, 1508-1519 (2005).
  7. H. Zeng, C. Huang, A. Vukovic, "A novel fault detection and localization scheme for mesh all-optical networks based on monitoring-cycles," Photon. Netw. Commun. 11, 277-286 (2006).
  8. H. Zeng, A. Vukovic, "The variant cycle-cover problem in fault detection and localization for mesh all-optical networks," Photon. Netw. Commun. 14, 111-122 (2007).
  9. B. Wu, K. Yeung, P.-H. Ho, "Monitoring cycle design for fast link failure localization in all-optical networks," J. Lightw. Technol. 27, 1392-1401 (2009).
  10. C. Li, R. Ramaswami, I. Center, Y. Heights, "Automatic fault detection, isolation, and recovery in transparent all-optical networks," J. Lightw. Technol. 15, 1784-1793 (1997).
  11. S. Stanic, S. Subramaniam, H. Choi, G. Sahin, H. Choi, "On monitoring transparent optical networks," Proc. Int. Conf. Parallel Process. Workshops (2002) pp. 217-223.
  12. Y. Wen, V. Chan, L. Zheng, "Efficient fault-diagnosis algorithms for all-optical WDM networks with probabilistic link failures," J. Lightw. Technol. 23, 3358-3371 (2005).
  13. C. Assi, Y. Ye, A. Shami, S. Dixit, M. Ali, "A hybrid distributed fault-management protocol for combating single-fiber failures in meshbased DWDM optical networks," Proc. IEEE Global Telecommun. Conf. (GLOBECOM) (2002) pp. 2676-2680.
  14. B. Wu, P.-H. Ho, K. Yeung, "Monitoring trail: On fast link failure localization in WDM mesh networks," J. Lightw. Technol. 27, 4175-4185 (2009).
  15. N. Harvey, M. Patrascu, Y. Wen, S. Yekhanin, V. Chan, "Non-adaptive fault diagnosis for all-optical networks via combinatorial group testing on graphs," Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM) (2007) pp. 697-705.
  16. S. Ahuja, S. Ramasubramanian, M. Krunz, "Single link failure detection in all-optical networks using monitoring cycles and paths," IEEE/ACM Trans. Netw. 17, 1080-1093 (2009).
  17. S. Ahuja, S. Ramasubramanian, M. Krunz, "SRLG failure localization in all-optical networks using monitoring cycles and paths," Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM) (2008) pp. 181-185.
  18. B. Wu, P.-H. Ho, K. Yeung, J. Tapolcai, H. Mouftah, "Optical layer monitoring schemes for fast link failure localization in all-optical networks," IEEE Commun. Surv. Tutorials 114-125 (2011) to appear in.
  19. H. Zeng, C. Huang, A. Vukovic, "A novel fault detection and localization scheme for mesh all-optical networks based on monitoring-cycles," Photon. Commun. Netw. 11, 277-286 (2006).
  20. C. Assi, Y. Ye, A. Shami, S. Dixit, M. Ali, "A hybrid distributed fault-management protocol for combating single-fiber failures in mesh based DWDM optical networks," Proc. IEEE Global Telecommun. Conf. (GLOBECOM) (2002) pp. 2676-2680.
  21. B. Wu, P.-H. Ho, J. Tapolcai, X. Jiang, "A novel framework of fast and unambiguous link failure localization via monitoring trails," Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM) WIP (2010) pp. 1-5.
  22. S. Stanic, S. Subramaniam, G. Sahin, H. Choi, H. A. Choi, "Active monitoring and alarm management for fault localization in transparent all-optical networks," IEEE Trans. Netw. Serv. Manage. 7, 118-131 (2010).
  23. B. Wu, P. H. Ho, J. Tapolcai, P. Babarczi, "Optimal allocation of monitoring trails for fast SRLG failure localization in all-optical networks," IEEE Global Telecommun. Conf. (GLOBECOM) (2010) pp. 1-5.
  24. J. Tapolcai, B. Wu, P.-H. Ho, "On monitoring and failure localization in mesh all-optical networks," Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM) (2009) pp. 1008-1016.
  25. J. W. Suurballe, "Disjoint paths in a network," Networks 4, 125-145 (1974).
  26. D. Eppstein, M. Goodrich, D. Hirschberg, "Improved combinatorial group testing for real-world problem sizes," Proc. Workshop Algorithms Data Struct. (2005) pp. 86-98.
  27. F. K. Hwang, V. T. Sós, "Non-adaptive hypergeometric group testing," Studia Sci. Math. Hungar 22, 257-263 (1987).
  28. D. Du, F. K. Hwang, Combinatorial Group Testing and Its Applications (World Scientific, 2000).
  29. Lemon: A c++ Library for Efficient Modeling and Optimization in Networks http://lemon.cs.elte.hu.
  30. R. Tarjan, "Depth-first search and linear graph algorithms," Conf. Record 1971 IEEE 12th Annu. Symp. Switch. Automata Theory (1971) pp. 114-121.

2011 (1)

B. Wu, P.-H. Ho, K. Yeung, J. Tapolcai, H. Mouftah, "Optical layer monitoring schemes for fast link failure localization in all-optical networks," IEEE Commun. Surv. Tutorials 114-125 (2011) to appear in.

2010 (1)

S. Stanic, S. Subramaniam, G. Sahin, H. Choi, H. A. Choi, "Active monitoring and alarm management for fault localization in transparent all-optical networks," IEEE Trans. Netw. Serv. Manage. 7, 118-131 (2010).

2009 (3)

B. Wu, P.-H. Ho, K. Yeung, "Monitoring trail: On fast link failure localization in WDM mesh networks," J. Lightw. Technol. 27, 4175-4185 (2009).

S. Ahuja, S. Ramasubramanian, M. Krunz, "Single link failure detection in all-optical networks using monitoring cycles and paths," IEEE/ACM Trans. Netw. 17, 1080-1093 (2009).

B. Wu, K. Yeung, P.-H. Ho, "Monitoring cycle design for fast link failure localization in all-optical networks," J. Lightw. Technol. 27, 1392-1401 (2009).

2007 (1)

H. Zeng, A. Vukovic, "The variant cycle-cover problem in fault detection and localization for mesh all-optical networks," Photon. Netw. Commun. 14, 111-122 (2007).

2006 (2)

H. Zeng, C. Huang, A. Vukovic, "A novel fault detection and localization scheme for mesh all-optical networks based on monitoring-cycles," Photon. Netw. Commun. 11, 277-286 (2006).

H. Zeng, C. Huang, A. Vukovic, "A novel fault detection and localization scheme for mesh all-optical networks based on monitoring-cycles," Photon. Commun. Netw. 11, 277-286 (2006).

2005 (2)

Y. Wen, V. Chan, L. Zheng, "Efficient fault-diagnosis algorithms for all-optical WDM networks with probabilistic link failures," J. Lightw. Technol. 23, 3358-3371 (2005).

C. Mas, I. Tomkos, O. Tonguz, "Failure location algorithm for transparent optical networks," IEEE J. Sel. Areas Commun. 23, 1508-1519 (2005).

2000 (1)

D. Zhou, S. Subramaniam, "Survivability in optical networks," IEEE Netw. 14, 16-23 (2000).

1999 (1)

P. Demeester, M. Gryseels, A. Autenrieth, C. Brianza, L. Castagna, G. Signorelli, R. Clemenfe, M. Ravera, A. Jajszczyk, D. Janukowicz, K. Van Doorselaere, Y. Harada, "Resilience in multilayer networks," IEEE Commun. Mag. 37, 70-76 (1999).

1998 (1)

M. Maeda, "Management and control of transparent optical networks," IEEE J. Sel. Areas Commun. 16, 1008-1023 (1998).

1997 (1)

C. Li, R. Ramaswami, I. Center, Y. Heights, "Automatic fault detection, isolation, and recovery in transparent all-optical networks," J. Lightw. Technol. 15, 1784-1793 (1997).

1987 (1)

F. K. Hwang, V. T. Sós, "Non-adaptive hypergeometric group testing," Studia Sci. Math. Hungar 22, 257-263 (1987).

1974 (1)

J. W. Suurballe, "Disjoint paths in a network," Networks 4, 125-145 (1974).

IEEE Commun. Mag. (1)

P. Demeester, M. Gryseels, A. Autenrieth, C. Brianza, L. Castagna, G. Signorelli, R. Clemenfe, M. Ravera, A. Jajszczyk, D. Janukowicz, K. Van Doorselaere, Y. Harada, "Resilience in multilayer networks," IEEE Commun. Mag. 37, 70-76 (1999).

IEEE Commun. Surv. Tutorials (1)

B. Wu, P.-H. Ho, K. Yeung, J. Tapolcai, H. Mouftah, "Optical layer monitoring schemes for fast link failure localization in all-optical networks," IEEE Commun. Surv. Tutorials 114-125 (2011) to appear in.

IEEE J. Sel. Areas Commun. (1)

C. Mas, I. Tomkos, O. Tonguz, "Failure location algorithm for transparent optical networks," IEEE J. Sel. Areas Commun. 23, 1508-1519 (2005).

IEEE J. Sel. Areas Commun. (1)

M. Maeda, "Management and control of transparent optical networks," IEEE J. Sel. Areas Commun. 16, 1008-1023 (1998).

IEEE Netw. (1)

D. Zhou, S. Subramaniam, "Survivability in optical networks," IEEE Netw. 14, 16-23 (2000).

IEEE Trans. Netw. Serv. Manage. (1)

S. Stanic, S. Subramaniam, G. Sahin, H. Choi, H. A. Choi, "Active monitoring and alarm management for fault localization in transparent all-optical networks," IEEE Trans. Netw. Serv. Manage. 7, 118-131 (2010).

IEEE/ACM Trans. Netw. (1)

S. Ahuja, S. Ramasubramanian, M. Krunz, "Single link failure detection in all-optical networks using monitoring cycles and paths," IEEE/ACM Trans. Netw. 17, 1080-1093 (2009).

J. Lightw. Technol. (1)

Y. Wen, V. Chan, L. Zheng, "Efficient fault-diagnosis algorithms for all-optical WDM networks with probabilistic link failures," J. Lightw. Technol. 23, 3358-3371 (2005).

J. Lightw. Technol. (3)

B. Wu, K. Yeung, P.-H. Ho, "Monitoring cycle design for fast link failure localization in all-optical networks," J. Lightw. Technol. 27, 1392-1401 (2009).

C. Li, R. Ramaswami, I. Center, Y. Heights, "Automatic fault detection, isolation, and recovery in transparent all-optical networks," J. Lightw. Technol. 15, 1784-1793 (1997).

B. Wu, P.-H. Ho, K. Yeung, "Monitoring trail: On fast link failure localization in WDM mesh networks," J. Lightw. Technol. 27, 4175-4185 (2009).

Networks (1)

J. W. Suurballe, "Disjoint paths in a network," Networks 4, 125-145 (1974).

Photon. Commun. Netw. (1)

H. Zeng, C. Huang, A. Vukovic, "A novel fault detection and localization scheme for mesh all-optical networks based on monitoring-cycles," Photon. Commun. Netw. 11, 277-286 (2006).

Photon. Netw. Commun. (2)

H. Zeng, C. Huang, A. Vukovic, "A novel fault detection and localization scheme for mesh all-optical networks based on monitoring-cycles," Photon. Netw. Commun. 11, 277-286 (2006).

H. Zeng, A. Vukovic, "The variant cycle-cover problem in fault detection and localization for mesh all-optical networks," Photon. Netw. Commun. 14, 111-122 (2007).

Studia Sci. Math. Hungar (1)

F. K. Hwang, V. T. Sós, "Non-adaptive hypergeometric group testing," Studia Sci. Math. Hungar 22, 257-263 (1987).

Other (14)

D. Du, F. K. Hwang, Combinatorial Group Testing and Its Applications (World Scientific, 2000).

Lemon: A c++ Library for Efficient Modeling and Optimization in Networks http://lemon.cs.elte.hu.

R. Tarjan, "Depth-first search and linear graph algorithms," Conf. Record 1971 IEEE 12th Annu. Symp. Switch. Automata Theory (1971) pp. 114-121.

C. Assi, Y. Ye, A. Shami, S. Dixit, M. Ali, "A hybrid distributed fault-management protocol for combating single-fiber failures in mesh based DWDM optical networks," Proc. IEEE Global Telecommun. Conf. (GLOBECOM) (2002) pp. 2676-2680.

B. Wu, P.-H. Ho, J. Tapolcai, X. Jiang, "A novel framework of fast and unambiguous link failure localization via monitoring trails," Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM) WIP (2010) pp. 1-5.

D. Eppstein, M. Goodrich, D. Hirschberg, "Improved combinatorial group testing for real-world problem sizes," Proc. Workshop Algorithms Data Struct. (2005) pp. 86-98.

B. Wu, P. H. Ho, J. Tapolcai, P. Babarczi, "Optimal allocation of monitoring trails for fast SRLG failure localization in all-optical networks," IEEE Global Telecommun. Conf. (GLOBECOM) (2010) pp. 1-5.

J. Tapolcai, B. Wu, P.-H. Ho, "On monitoring and failure localization in mesh all-optical networks," Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM) (2009) pp. 1008-1016.

J. Tapolcai, Web page on m-trail/tree design: Simulation environments, examples and technical reports. http://opti.tmit.bme.hu/~tapolcai/mtrail.

I. Tomkos, "Dynamically reconfigurable transparent optical networking based on cross-layer optimization," Proc. Int. Conf. Transparent Opt. Netw. (2007) pp. 327-327.

N. Harvey, M. Patrascu, Y. Wen, S. Yekhanin, V. Chan, "Non-adaptive fault diagnosis for all-optical networks via combinatorial group testing on graphs," Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM) (2007) pp. 697-705.

S. Ahuja, S. Ramasubramanian, M. Krunz, "SRLG failure localization in all-optical networks using monitoring cycles and paths," Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM) (2008) pp. 181-185.

S. Stanic, S. Subramaniam, H. Choi, G. Sahin, H. Choi, "On monitoring transparent optical networks," Proc. Int. Conf. Parallel Process. Workshops (2002) pp. 217-223.

C. Assi, Y. Ye, A. Shami, S. Dixit, M. Ali, "A hybrid distributed fault-management protocol for combating single-fiber failures in meshbased DWDM optical networks," Proc. IEEE Global Telecommun. Conf. (GLOBECOM) (2002) pp. 2676-2680.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.