Abstract

A novel design optimization for reliable networking is investigated in Ethernet ring mesh networks with the ITU-T G.8032 Ethernet Ring Protection Recommendation. Designing an Ethernet ring mesh consisting of multiple rings to achieve the maximum network availability is an NP-complete problem. We show that a graph with vertex connectivity equal to or greater than two is a sufficient condition for designing an Ethernet ring mesh. A novel design rule with an efficient heuristic algorithm is proposed to find a design close to an optimal Ethernet ring mesh in terms of maximum network availability. Compared with an optimal network design algorithm with an exponential enumeration search cost, the heuristic algorithm achieves network availability nearly as high as that of an optimal design at a polynomial cost.

© 2012 IEEE

PDF Article

References

  • View by:
  • |
  • |

  1. R. Sanchez, L. Raptis, K. Vaxevanakis, "Ethernet as a carrier grade technology: Developments and innovations," IEEE Comm. Mag. 46, 88-94 (2008).
  2. Ethernet Ring Protection Switching ITU-T Rec. G.8032/Y.1344 (2010).
  3. J.-D. Ryoo, H. Long, Y. Yang, M. Holness, Z. Ahmad, J.-K.K. Rhee, "Ethernet ring protection for carrier ethernet networks," IEEE Comm. Mag. 46, 136-143 (2008).
  4. H. Luss, M. B. Rosenwein, R. T. Wong, "Topological network design for SONET ring architecture," IEEE Trans. Syst., Man, Cybern. 28, 780-790 (1998).
  5. D. Zhou, S. Subramaniam, "Survivability in optical networks," IEEE Netw. 14, 16-23 (2000).
  6. S. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, "Survivable WDM mesh networks," J. Lightw. Technol. 21, (2003).
  7. K. Lee, E. Modiano, "Cross-layer survivability in WDM-based networks," Proc. Infocom (2009).
  8. P. Cho?da, J. Dom?a?, A. Jajszczyk, K. Wajda, "Reliability analysis of resilient packet rings," Proc. SAFECOMP (2006) pp. 289-301.
  9. IEEE 802.17: Resilient Packet Ring (RPR) Access Method & Physical Layer Specifications AUTHOR PLS PROVIDE STANDARDS NUMBER (2004).
  10. J. C. Tournier, T. Werner, "A quantitative evaluation of IEC61850 process bus architectures," Proc. Power and Energy Society General Meeting (2010).
  11. Communication Networks and Systems in Substations IEC 61850International Electrotechnical Commission (2003).
  12. D. Lee, K. Lee, S. Yoo, J.-K. Kevin Rhee Rhee, "Efficient ethernet ring mesh network design," J. of Lightw. Technol. 29, (2011).
  13. C. Arbib, F. Rossi, "An optimization problem arising in the design of multiring systems," Euro. J. Operational Research 124, 63-76 (2000).
  14. Y. Agarwal, "K-partition-based facets of the network design problem," Networks 47, 123-139 (2006).
  15. M. Clouqueur, W. D. Grover, "Availability analysis of span-restorable mesh networks," IEEE JSAC 20, 810-21 (2002).
  16. E. Flandrin, H. Li, A. Marczyk, M. Wózniak, "A generalization of Dirac's theorem on cycles through k vertices in k-connected graphs," Discrete Math. 307, 878-884 (2007).
  17. A. Zamora, "An algorithm for finding the smallest set of smallest rings," J. Chem. Inf. Comput. Sci. 16, 40-43 (1976).
  18. M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of N P-Completeness (Freeman, 1979).
  19. J. D. Horton, "A polynomial-time algorithm to find a shortest cycle basis of a graph," SIAM J. Computing 16, 359-366 (1987).
  20. S. Lee, J. Liu, Y. Chen, "An ear-decomposition based approach for survivable routing in WDM networks," Proc. IEEE AINA (2005).
  21. G. Shen, W. D. Grover, "Exploiting forcer structure to serve uncertain demands and minimize redundancy of $p$-cycle networks," Proc. OptiComm (2003).
  22. S. Verbrugge, D. Colle, P. Demeester, R. Huelsermann, M. Jaeger, "General availability model for multilayer transport networks," Proc. DRCN (2005) pp. 85-92.

2011 (1)

D. Lee, K. Lee, S. Yoo, J.-K. Kevin Rhee Rhee, "Efficient ethernet ring mesh network design," J. of Lightw. Technol. 29, (2011).

2008 (2)

R. Sanchez, L. Raptis, K. Vaxevanakis, "Ethernet as a carrier grade technology: Developments and innovations," IEEE Comm. Mag. 46, 88-94 (2008).

J.-D. Ryoo, H. Long, Y. Yang, M. Holness, Z. Ahmad, J.-K.K. Rhee, "Ethernet ring protection for carrier ethernet networks," IEEE Comm. Mag. 46, 136-143 (2008).

2007 (1)

E. Flandrin, H. Li, A. Marczyk, M. Wózniak, "A generalization of Dirac's theorem on cycles through k vertices in k-connected graphs," Discrete Math. 307, 878-884 (2007).

2006 (1)

Y. Agarwal, "K-partition-based facets of the network design problem," Networks 47, 123-139 (2006).

2003 (1)

S. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, "Survivable WDM mesh networks," J. Lightw. Technol. 21, (2003).

2002 (1)

M. Clouqueur, W. D. Grover, "Availability analysis of span-restorable mesh networks," IEEE JSAC 20, 810-21 (2002).

2000 (2)

C. Arbib, F. Rossi, "An optimization problem arising in the design of multiring systems," Euro. J. Operational Research 124, 63-76 (2000).

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

1998 (1)

H. Luss, M. B. Rosenwein, R. T. Wong, "Topological network design for SONET ring architecture," IEEE Trans. Syst., Man, Cybern. 28, 780-790 (1998).

1987 (1)

J. D. Horton, "A polynomial-time algorithm to find a shortest cycle basis of a graph," SIAM J. Computing 16, 359-366 (1987).

1976 (1)

A. Zamora, "An algorithm for finding the smallest set of smallest rings," J. Chem. Inf. Comput. Sci. 16, 40-43 (1976).

Discrete Math. (1)

E. Flandrin, H. Li, A. Marczyk, M. Wózniak, "A generalization of Dirac's theorem on cycles through k vertices in k-connected graphs," Discrete Math. 307, 878-884 (2007).

Euro. J. Operational Research (1)

C. Arbib, F. Rossi, "An optimization problem arising in the design of multiring systems," Euro. J. Operational Research 124, 63-76 (2000).

IEEE Comm. Mag. (2)

R. Sanchez, L. Raptis, K. Vaxevanakis, "Ethernet as a carrier grade technology: Developments and innovations," IEEE Comm. Mag. 46, 88-94 (2008).

J.-D. Ryoo, H. Long, Y. Yang, M. Holness, Z. Ahmad, J.-K.K. Rhee, "Ethernet ring protection for carrier ethernet networks," IEEE Comm. Mag. 46, 136-143 (2008).

IEEE JSAC (1)

M. Clouqueur, W. D. Grover, "Availability analysis of span-restorable mesh networks," IEEE JSAC 20, 810-21 (2002).

IEEE Netw. (1)

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

IEEE Trans. Syst., Man, Cybern. (1)

H. Luss, M. B. Rosenwein, R. T. Wong, "Topological network design for SONET ring architecture," IEEE Trans. Syst., Man, Cybern. 28, 780-790 (1998).

J. Chem. Inf. Comput. Sci. (1)

A. Zamora, "An algorithm for finding the smallest set of smallest rings," J. Chem. Inf. Comput. Sci. 16, 40-43 (1976).

J. Lightw. Technol. (1)

S. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, "Survivable WDM mesh networks," J. Lightw. Technol. 21, (2003).

J. of Lightw. Technol. (1)

D. Lee, K. Lee, S. Yoo, J.-K. Kevin Rhee Rhee, "Efficient ethernet ring mesh network design," J. of Lightw. Technol. 29, (2011).

Networks (1)

Y. Agarwal, "K-partition-based facets of the network design problem," Networks 47, 123-139 (2006).

SIAM J. Computing (1)

J. D. Horton, "A polynomial-time algorithm to find a shortest cycle basis of a graph," SIAM J. Computing 16, 359-366 (1987).

Other (10)

S. Lee, J. Liu, Y. Chen, "An ear-decomposition based approach for survivable routing in WDM networks," Proc. IEEE AINA (2005).

G. Shen, W. D. Grover, "Exploiting forcer structure to serve uncertain demands and minimize redundancy of $p$-cycle networks," Proc. OptiComm (2003).

S. Verbrugge, D. Colle, P. Demeester, R. Huelsermann, M. Jaeger, "General availability model for multilayer transport networks," Proc. DRCN (2005) pp. 85-92.

K. Lee, E. Modiano, "Cross-layer survivability in WDM-based networks," Proc. Infocom (2009).

P. Cho?da, J. Dom?a?, A. Jajszczyk, K. Wajda, "Reliability analysis of resilient packet rings," Proc. SAFECOMP (2006) pp. 289-301.

IEEE 802.17: Resilient Packet Ring (RPR) Access Method & Physical Layer Specifications AUTHOR PLS PROVIDE STANDARDS NUMBER (2004).

J. C. Tournier, T. Werner, "A quantitative evaluation of IEC61850 process bus architectures," Proc. Power and Energy Society General Meeting (2010).

Communication Networks and Systems in Substations IEC 61850International Electrotechnical Commission (2003).

Ethernet Ring Protection Switching ITU-T Rec. G.8032/Y.1344 (2010).

M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of N P-Completeness (Freeman, 1979).

Cited By

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

Alert me when this article is cited.