Fault tolerance of small-world regular and stochastic interconnection networks

Authors

Keywords:

supercomputers, interconnection networks, small-world networks, fault tolerance, cascading failures

Abstract

The fault tolerance of the most important properties of stochastic and regular (deterministic) small-world interconnection networks are studied. In the case of stochastic networks, the algorithm with the best values of the number of shortcuts and the parameter of their length distribution is used. As a regular networks, the Interlaced Bypass Torus Networks (iBT-networks), which possess the best characteristics in the class of networks constructed by deterministic algorithms, are considered. It is shown that, in the broad range of values of the faulty node rate, the considered networks possess the high fault tolerance and the iBT-networks are slightly better than the stochastic ones.

Author Biographies

A.P. Demichev

Lomonosov Moscow State University,
Skobeltsyn Institute of Nuclear Physics (SINP MSU)
• Senior Researcher

V.A. Ilyin

National Research Center «Kurchatov Institute»
• Head of Department

A.P. Kryukov

Lomonosov Moscow State University,
Skobeltsyn Institute of Nuclear Physics (SINP MSU)
• Leading Researcher

S.P. Polyakov

Lomonosov Moscow State University,
Skobeltsyn Institute of Nuclear Physics (SINP MSU)
• Junior Researcher

References

  1. Shalf J., Dosanjh S., Morrison J. Exascale computing technology challenges // Lecture Notes in Computer Science. Vol. 6449. Heidelberg: Springer, 2011. 1-25.
  2. Горбунов В., Елизаров Г., Эйсымонт Л. Экзафлопсные суперкомпьютеры: достижения и перспективы // Открытые системы. 2013. № 7. 10-14
  3. Deng Y., Zhang P. Perspectives on exascale computing // J. New Computing Architectures and Applications. 2010. 1. 8-22.
  4. Alvin K., Barett B., Brightwell R., et al. On the path to exascale // Int. J. of Distributed Systems and Technologies. 2010. 1, N 2. 1-22.
  5. Dally W.J., Towles B.P. Principles and practices of interconnection networks. Amsterdam: Elsevier, 2003.
  6. Kleinrock L. Communication nets: stochastic message flow and design. New York: McGraw-Hill, 1964.
  7. Barthelemy M. Spatial networks // Phys. Reports. 2011. 499. 1-101.
  8. Zhu Z.-Y., Mao B.-H., Hao H.-M., Gao J.-Z., Yang J.-J. Regular small-world network // Chin. Phys. Lett. 2009. 26. 110502-1-110502-3.
  9. Boettcher S., Goncalves B., Azaret J. Geometry and dynamics for hierarchical regular networks // J. of Physics. 2008. A41. 335003-1-335003-25.
  10. Boettcher S., Goncalves B., Guclu H. Hierarchical regular small-world networks // J. of Physics. 2008. A41. 252001-1-252001-7.
  11. Монахова Э.А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011. 3, № 13. 92-115.
  12. Comellas F., Ozona J., Peters J.G. Deterministic small-world communication networks // Information Processing Letters. 2000. 76. 83-90.
  13. Comellas F., Mitjana M., Peters J.G. Broadcasting in small-world communication networks // Proc. 9th Int. Coll. on Structural Information and Communication Complexity. Waterloo: Carleton Scientific, 2002. 73-85.
  14. Демичев А.П., Ильин В.А., Крюков А.П., Поляков С.П. Сравнительный анализ алгоритмов построения больших коммуникационных сетей со свойствами «малого мира» // Вестн. Уфимского гос. авиационного техн. ун-та. 2013. 17, № 5. 167-175.
  15. Inoguchi Y., Horiguchi S. Shifted recursive torus interconnection for high performance computing // Proc. on the High-Performance Computing on the Information Superhighway. New York: IEEE Press, 1997. 61-66.
  16. Yang Y., Funahashi A., Akiya J., Nishi H., Amano H., Sueyoshi T. Recursive diagonal torus: an interconnection network for massively parallel computers // IEEE Trans. on Parallel and Distributed Systems. 2001. 12, N 7. 701-715.
  17. Zhang P., Powell R., Deng Y. Interlacing bypass rings to torus networks for more efficient networks // IEEE Trans. on Parallel and Distributed Systems. 2011. 22, N 2. 287-295.
  18. Zhang P., Deng Y. An analysis of the topological properties of the interlaced Bypass Torus (iBT) networks // Appl. Math. Lett. 2012. 25. 2147-2155.
  19. Powell R. Analysis of supercomputers and development of a novel network. PhD Thesis. Stony Brook: Stony Brook University. 2010.
  20. Moukarzel C.F., de Menezes M.A. Shortest paths on systems with power-law distributed long-range connections // Phys. Rev. E. 2002. 65. 056709-1-056709-9.
  21. Sen P., Chakrabarti B. Small-world phenomena and the statistics of linear polymer // J. of Physics A. 2001. 34. 7749-7755.
  22. Petermann T., De Los Rios P. Physical realizability of small-world networks // Phys. Rev. E. 2006. 73. 026114-1-026114-4.
  23. Watts D.J., Strogatz D.H. Collective dynamics of small-world networks // Nature. 1998. 393. 440-442.
  24. Albert R., Barabasi A.-L. Statistical mechanics of complex networks // Rev. Mod. Phys. 2002. 74. 47-97.
  25. Kleinberg J.M. Navigation in the small world // Nature. 2000. 406. 845.
  26. Ciciani B., Colajanni M., Paolucci C. Performance evaluation of deterministic wormhole routing in k-ary n-cubes // Parallel Comput. 1998. 24. 2053-2075.
  27. Sarbazi-Azad H., Khonsari A., Ould-Khaoua M. Analysis of k-ary n-cubes with dimension-ordered routing // Future Generation Computer Systems. 2003. 19. 493-502.
  28. Alzeidi N., Ould-Khaoua M., Khonsari A. A new modelling approach of wormhole-switched networks with finite buffers // Int. J. of Parallel, Emergent and Distributed Systems. 2008. 23, N 1. 45-57.
  29. Xu J. Topological structure and analysis of interconnection networks. Dordrecht: Klüwer, 2001.
  30. Motter A.E., Lai Y.-C. Cascade-based attacks on complex networks // Phys. Rev. 2002. E66. 065102-1-065102-4.
  31. Dobson I., Carreras B., Newman D. Complex systems analysis of series of blackouts: cascading failure, critical points, and self-organization // Chaos. 2007. 17. 026103-1-026103-13.
New computational technologies

Downloads

Published

29-01-2014

How to Cite

Демичев А., Ильин В., Крюков А., Поляков С. Fault Tolerance of Small-World Regular and Stochastic Interconnection Networks // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2014. 15. 36-48

Issue

Vol. 15 (2014): Issue 1.

Section

Section 1. Numerical methods and applications