Fault tolerance of small-world regular and stochastic interconnection networks

Authors

  • A.P. Demichev
  • V.A. Ilyin
  • A.P. Kryukov
  • S.P. Polyakov

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.

New computational technologies

Downloads

Published

2014-01-29

Issue

Vol. 15 (2014): Issue 1.

Section

Section 1. Numerical methods and applications

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.