9 / 13
Отказоустойчивые компьютерные сети, построенные на основе комбинаторных блок-дизайнов
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 6
49
При многократных отказах линий связи этот алгоритм маршрутизации
продолжает обеспечивать постепенную деградацию КСС. Так, например, при
многократных отказах в линиях связи, если процессор–получатель сообщения
также содержит отказавшую линию связи, процессор–отправитель передает со-
общение в произвольно выбранном порядке одному из соседних исправных
процессоров. По мере накопления числа отказов этот алгоритм маршрутизации
будет использовать лишь работоспособную связную часть топологии КСС.
Отказы процессора можно классифицировать следующим образом.
Если отказ происходит непосредственно в процессоре и выполнение ко-
манд разделено на вычислительную и коммуникационную части, то КСС может
продолжать функционировать. Подобный режим работы возможен для шинно-
го (магистрального) исполнения, когда потеря процессора ни в коем случае не
влияет на возможность шины продолжить передавать сообщения для других
процессоров, связанных с отказавшим.
Другой тип отказа, при котором невозможна любая передача сообщения
посредством коммуникационной сети через отказавший процессор, может быть
рассмотрен как отказ в каждом из
r
путей, проходящих через отказавший про-
цессор, и в этом случае необходимо руководствоваться алгоритмом маршрути-
зации, описанным в пункте 1.
Таким образом, топология КСС, реализованная на базе BIBD, имеет свой-
ства высокой отказоустойчивости и постепенной деградации, поскольку она
может оставаться работоспособной при условии, что рабочая часть сети связа-
на. Эта топология адаптируется к новой ситуации и противостоит отказам, вы-
полняя при этом свою целевую функцию за счет соответствующего изменения
структуры и поведения КСС даже при повреждениях ее частей. Топологию
BIBD желательно применять в ситуациях, когда поток отказов редкий, но регу-
лярный (например, в больших мультипроцессорных системах — отказы явля-
ются равномерно распределенными [2, 10, 11, 14]). Кроме того, эта топология
может применяться в ситуациях, когда ожидается значительная интенсивность
потока отказов, но при этом важным является, чтобы КСС использовала все
возможности топологии по связности, независимо от того, какая рабочая часть
сети остается исправной.
Дополнительные свойства BIB-дизайна.
При проектировании КСС ис-
пользование топологии на основе блок-дизайна позволяет получить бóльшую
гибкость для заданного числа процессоров
n
за счет выбора параметра
k
. Это
обеспечивает достижение оптимального соотношения между стоимостью и
производительностью.
Отметим, что число связей, требуемых для каждого процессора, не может
превысить
2 ,
r
так как каждый элемент, появляющийся в блоках
r
, может быть
смежным одному или двум процессорам в каждом блоке. Из уравнений (1) мо-
гут быть выражены параметры
r
и
b
как функции параметров
n
и
k
: