Устойчивость работы регулярных и стохастических коммуникационных сетей со свойствами малого мира

Авторы

  • А.П. Демичев
  • В.А. Ильин
  • А.П. Крюков
  • С.П. Поляков

Ключевые слова:

суперкомпьютеры
коммуникационные сети
сети «малого мира»
устойчивость
каскадные отключения

Аннотация

Исследована устойчивость важнейших характеристик стохастических и регулярных (детерминистских) коммуникационных сетей с малым средним расстоянием между узлами (сети «малого мира") при выходе из строя части узлов. В случае стохастических сетей используется алгоритм с оптимальными значениями числа перемычек и параметра распределения их длин, а в качестве регулярных сетей рассмотрена iBT-сеть (Interlaced Bypass Torus Networks), обладающая наилучшими характеристиками в классе сетей, построенных на основе детерминистских алгоритмов. Показано, что в широком диапазоне значений относительного числа вышедших из строя узлов рассмотренные сети являются весьма устойчивыми к выходу узлов из строя, причем iBT-сети ведут себя несколько лучше, чем стохастические сети.

Новые вычислительные технологии

Загрузки

Опубликован

2014-01-29

Выпуск

Том 15 (2014): Выпуск 1.

Раздел

Раздел 1. Вычислительные методы и приложения

Авторы

А.П. Демичев

Московский государственный университет имени М.В. Ломоносова,
НИИ ядерной физики имени Д.В. Скобельцына (НИИЯФ МГУ)
Ленинские горы, 119234, Москва
• старший научный сотрудник

В.А. Ильин

Национальный исследовательский центр «Курчатовский институт»
пл. Академика Курчатова, 1, 123182, Москва
• начальник отделения

А.П. Крюков

Московский государственный университет имени М.В. Ломоносова,
НИИ ядерной физики имени Д.В. Скобельцына (НИИЯФ МГУ)
Ленинские горы, 119234, Москва
• ведущий научный сотрудник

С.П. Поляков

Московский государственный университет имени М.В. Ломоносова,
НИИ ядерной физики имени Д.В. Скобельцына (НИИЯФ МГУ)
Ленинские горы, 119234, Москва
• младший научный сотрудник

Библиографические ссылки

  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.