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

ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 6

УДК 681.322.01

DOI: 10.18698/0236-3933-2016-6-41-53

ОТКАЗОУСТОЙЧИВЫЕ КОМПЬЮТЕРНЫЕ СЕТИ, ПОСТРОЕННЫЕ

НА ОСНОВЕ КОМБИНАТОРНЫХ БЛОК-ДИЗАЙНОВ

Г.П. Можаров

mojarov_g@mail.ru

МГТУ им. Н.Э. Баумана, Москва, Российская Федерация

Аннотация

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

Приведен новый класс компьютерных систем и сетей,

состоящих из однородных процессоров с локальной памя-

тью и быстродействующей коммуникационной сетью,

построенный на основе комбинаторных объектов со спе-

циальными свойствами. Анализ и синтез топологии пред-

ставленного класса сетей, проведен на основе использова-

ния уравновешенных неполных блок-дизайнов (блок-

схем). Достаточно подробно описан класс компьютерных

систем и коммуникационных сетей, которые являются

особенно подходящими для практического использова-

ния — так называемые тройки Штейнера. Такие компью-

терные системы и сети, реализация которых основана на

использовании блок-дизайнов, хорошо структурированы,

имеют высокую отказоустойчивость, обладают малой

средней длиной пути, минимальной стоимостью связи и

постепенной деградацией топологии при воздействии на

сеть потока отказов. Кроме того, сети имеют свободный

параметр, который позволяет согласовать их производи-

тельность и стоимость. Топология подобных компьютер-

ных сетей является оптимальной среди циклических

систем с точки зрения среднего диаметра, производитель-

ности, отказоустойчивости и стоимости. Предложен до-

статочно простой алгоритм маршрутизации, обеспечива-

ющий отказоустойчивую работу компьютерной коммуни-

кационной сети с циклической топологией

Компьютерная система, комму-

никационная сеть, комбинатор-

ные блок-дизайны, отказоустой-

чивость, постепенная деградация,

пропускная способность сети,

алгоритм маршрутизации

Поступила в редакцию 06.04.2016

Введение.

Постоянно растущие требования к производительности, отказо-

устойчивости и надежности компьютерных систем и сетей (КСС), накопление

новых и переосмысление имеющихся идей и методов в комбинаторной матема-

тике приводят к значительным изменениям в теории и практике проектирова-

ния КСС. Эти изменения обусловили необходимость продолжения математиче-

ских исследований в каждом из многочисленных направлений теории КСС и

стимулировали исследователей к поиску новых экстремальных топологий КСС.

В последнее время существенно возрос поток публикаций по решению ши-

рокого спектра алгебраических, комбинаторных и графо-спектральных задач,

возникающих при моделировании, разработке и реализации КСС [1−7]. Интен-

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