Отказоустойчивые компьютерные сети, построенные на основе комбинаторных блок-дизайнов

Приведен новый класс компьютерных систем и сетей, состоящих из однородных процессоров с локальной памятью и быстродействующей коммуникационной сетью, построенный на основе комбинаторных объектов со специальными свойствами. Анализ и синтез топологии представленного класса сетей, проведен на основе использования уравновешенных неполных блок-дизайнов (блок-схем). Достаточно подробно описан класс компьютерных систем и коммуникационных сетей, которые являются особенно подходящими для практического использования - так называемые тройки Штейнера. Такие компьютерные системы и сети, реализация которых основана на использовании блок-дизайнов, хорошо структурированы, имеют высокую отказоустойчивость, обладают малой средней длиной пути, минимальной стоимостью связи и постепенной деградацией топологии при воздействии на сеть потока отказов. Кроме того, сети имеют свободный параметр, который позволяет согласовать их производительность и стоимость. Топология подобных компьютерных сетей является оптимальной среди циклических систем с точки зрения среднего диаметра, производительности, отказоустойчивости и стоимости. Предложен достаточно простой алгоритм маршрутизации, обеспечивающий отказоустойчивую работу компьютерной коммуникационной сети с циклической топологией.

Литература

[1] Таранников Ю.В. Комбинаторные свойства дискретных структур и приложения к криптологии. М.: МЦНМО, 2011. 152 с.

[2] Андреев А.М., Можаров Г.П., Сюзев В.В. Многопроцессорные вычислительные системы: теоретический анализ, математические модели и применение. М.: Изд-во МГТУ им. Н.Э. Баумана, 2011. 334 с.

[3] Деза М.М., Лоран М. Геометрия разрезов и метрик / пер. с англ. Е. Пантелеевой и П. Сергеева; под ред. В. Гришухина. М.: МЦНМО, 2001. 736 с.

[4] Стенли P. Перечислительная комбинаторика. Т. 2 / пер. с англ. М.: Мир., 2009. 767 с.

[5] Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. СПб.: Лань, 2010. 368 с.

[6] Райгородский A.M. Экстремальные задачи теории графов и анализ данных. М.: РХД, 2009. 64 с.

[7] Звонкин А.К., Ландо С.К. Графы на поверхностях и их приложения. М.: МЦНМО, 2010. 480 с.

[8] Деза М., Гришухин В.П., Штогрин М.И. Изометрические полиэдральные подграфы в гиперкубах и кубических решетках / пер. с англ. Н.А. Шиховой. М.: МЦНМО, 2008. 192 с.

[9] Ландо С.К. Введение в дискретную математику. М.: МЦНМО, 2012. 265 с.

[10] Андреев А.М., Березкин Д.В., Можаров Г.П., Свирин И.С. Математическое моделирование надежности компьютерных систем и сетей // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2012. Спец. вып. "Моделирование и идентификация компьютерных систем и сетей". C. 3-46.

[11] Foss S., Shneer S., Turlikov A. Stability of a Markov-modulated Markov chain, with application to a wireless network governed by two protocols // Stochastic Systems. 2012. Vol. 2. No. 1. Р. 208-231. DOI: 10.1214/11-SSY030

[12] Ziegler Gunter M. Projected products of polygons. Electronic Research Announcements. AMS. 2004. Vol. 10. P. 122-134. DOI: 10.1090/S1079-6762-04-00137-4

[13] Циглер Г.М. Теория многогранников / пер. с англ. под ред. Н.П. Долбилина. М.: МЦНМО, 2014. 568 с.

[14] Алон Н., Спенсер Дж. Вероятностный метод / пер. с англ. М.: БИНОМ, 2007. 320 с.