Fault-Tolerant Multiprocessor Link and Bus Network Architectures

摘要

This paper presents a general class of regular networks which provide optimal (near-optimal) fault tolerance. The proposed networks compare favorably to other regular networks such as leaf-ringed binary trees and cube networks. In particular, the networks proposed possess certain advantages in that the number of connections per node is neither and arbitrarily fixed number (as in leaf-ringed trees) nor does it grow arbitrarily large with the size of the network (as in cube networks). This point has significant relevance to fault tolerance in that the degree of fault tolerance provided by the network can be varied according to the design specification. Also, the networks admit simple self-routing of messages and that routing is adaptable to faults.