3 / 13
Отказоустойчивые компьютерные сети, построенные на основе комбинаторных блок-дизайнов
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 6
43
Последнее требование особенно важно, потому что большое число про-
цессоров вызывает значительный поток отказов в КСС, которые необходимо
парировать (хотя бы частично), чтобы значительно не ухудшить работу
КСС [10, 11].
В некоторых известных топологиях КСС (кольца, деревья, связанные кольца,
кубически связанные циклы, гиперкубы, обобщенные гиперкубы и др. [2−6]) линии
связи (ребра) могли быть инцидентны не более чем двум узлам (процессорам), в то
время как узел мог быть инцидентен любому числу ребер. В сетях с магистральны-
ми связями любой узел (магистраль или шина) может быть инцидентен любому
числу магистралей (узлов). Магистральная сеть, состоящая из
n
узлов и
m
маги-
стралей, может быть описана матрицей инциденций
A
размера
.
n m
Элемент
этой матрицы
ij
a
= 1, если узлу с номером
1,
i
n
инцидентна магистраль с номе-
ром
1, ,
j
m
иначе
0
ij
a
. Из определения матрицы инциденций следует, что ма-
гистральные сети не допускают кратных инциденций (петель) ни по магистралям,
ни по узлам.
Предлагаемые в работе коммуникационные компьютерные сети строятся на
основе блок-дизайнов (этот класс КСС не описан в научных публикациях).
И хотя эти сети более дорогие, чем многие из перечисленных ранее, они имеют
лучшую отказоустойчивость и возможности постепенной деградации тополо-
гии. Эти сети можно реализовать, используя как двухточечную, так и шинную
(магистральную) связи.
Далее будут предложены и исследованы аналитические методы решения
сложной научно-технической оптимизационной задачи по определению мини-
мального количества линий связи среди всех циклических ВС и приведены
примеры синтеза отказоустойчивой циркулянтной сети.
Математическое определение сети на основе блок-дизайнов (
balanced in-
complete block design
(BIBD)).
Уравновешенным неполным блок-дизайном
(также употребляется сокращение BIB-дизайн) называется инцидентная систе-
ма из
n
элементов и
b
подмножеств этих элементов, называемых блоками,
такими, что: (
i
) каждый элемент содержится в
r
блоках, (
ii
) каждый блок со-
держит
k
элементов и (
iii
) каждая пара элементов одновременно содержится в
блоках. Целые числа
, , , ,
n b r k
называются параметрами дизайна [2].
Определенный ранее блок-дизайн с параметрами
, , , ,
n b r k
является част-
ным случаем системы инцидентности, называемой
t
-дизайном. Под
t
-дизайном с
параметрами
, ,
n k
или
- , , -диз
(
а )
йном
t n k l
понимается совокупность
D
под-
множеств (называемых блоками) множества
S
, состоящего из
n
элементов, такая,
что каждое подмножество из
D
содержит
k
элементов, а всякое множество из
t
элементов содержится ровно в
подмножествах из
D
. Это определение для
исключения вырожденных случаев обычно дополняется различными условиями:
S
и
D
не пусты;
n k t
0
[1−3, 5].