7 / 13
Отказоустойчивые компьютерные сети, построенные на основе комбинаторных блок-дизайнов
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 6
47
Однако этот способ построения графа BIB-дизайна не приводит к опти-
мальной топологии КСС, удовлетворяющей жестким требованиям по использу-
емым вычислительным ресурсам, малому числу портов процессора, стоимости
связи и др.
2. Рассмотрим новый способ реализации топологии BIB-дизайна. Приме-
ним систему троек Штейнера как наиболее наглядную демонстрацию топологи-
ческих свойств и характеристик КСС, использующих при реализации топологии
блок-дизайны.
Для построения
n
-узловой сети необходимо взять
n
-точечный блок-
дизайн, выбрать подходящее значение для параметра
k
и найти соответствую-
щий BIBD с этим значением.
Процессоры, помеченные
a
,
b
,
c
,
d
, соединяются в графе BIB-дизайна, вся-
кий раз, когда блок вида
(
)
abcd
существует в блок-дизайне. Подобным образом
можно осуществить соединение процессоров по схеме с общей шиной. Логиче-
ски, эти два способа эквивалентны, но их характеристики различны из-за ис-
полнения КСС.
Маршрутизация в блоках осуществляется следующим способом. Маршрут
прохождения сообщений от процессора
a
к процессору
b
является единствен-
ным путем, определяемым блоком, в котором оба эти процессора появляются,
т. е. блок-дизайн гарантирует, что этот маршрут хорошо определен и уникален.
Каждый процессор должен хранить в памяти таблицу
r
путей к процессорам,
с которыми он связан. Поскольку сообщение может быть адресовано любому про-
цессору, таблица маршрутизации должна иметь размер
1
n
для
n
-процессорной
сети.
На рис. 1 показана топология коммуникационной сети, которая реализует
BIB-дизайн с параметрами
7, 7, 3, 3, 1
(полужирными линиями показано
построение блока
3
).
b
Топология представляет собой хордовое кольцо с ва-
лентностью вершин, равной четырем [1, 2, 5, 6].
На рис. 2 показана топология, реализующая BIB-дизайн с параметрами
(9,12, 4, 3,1)
(полужирными линиями показано построение блока
11
).
b
Отказоустойчивые свойства
BIB-дизайна.
Топологические свойства
BIB-дизайна могут быть использованы для обеспечения отказоустойчивости
КСС [1, 2]. Рассмотрим только двухточечное исполнение, хотя описанные мето-
ды применимы и к шинному (магистральному) исполнению сети.
Будем считать, что граф алгоритма
A
выполним в топологическом графе
КСС, если
A
изоморфен некоторому подграфу топологического графа КСС, т. е.
существует однозначное сохраняющее метки и отношения смежности вершин
отображение графа алгоритма
A
в подграф графа КСС.
Удаление из графа КСС любых
s
вершин
1 2
, , ...,
s
x x x
и всех связанных с ни-
ми ребер считается
s
-кратной неисправностью
F
в КСС. Неисправности
F
соот-
ветствует граф
;
F
КСС
КСС является толерантной относительно алгоритма
A
и