Research Of System-Level Fault Diagnosis On Regular Interconnection Networks

Interconnection networks provide an effective mechanism for data exchange between processors in multicomputers systems. The performance of a system heavily depends on the reliability of its underlying interconnection network. With the ever increasing size of a system, it becomes much likely that there exist faulty components within the system. In order to maintain high reliability and high availability of a system, it is crucial to identify faulty units in the system. The system-level fault diagnosis is an effective approach to locating faulty processors in a multicomputers system, where a syndrome is formed by allowing processors to conduct tests on neighboring processors, then the faulty processors are identified by analyzing the syndrome.This thesis is devoted to the study of system-level diagnosis of interconnection networks.First, we review the principle and state-of-the-art of system-level fault diagnosis, and explain some classical fault diagnosis models and fault diagnosis strategies. Then, we list some typical interconnection networks (crossed cubes, 0-M?bius cubes, 1-M?bius cubes and locally twisted cubes) .Pessimistic diagnosis strategy can enhance the self-diagnosing capability of a system at the expense of a small number of fault-free nodes being mistakenly identified as faulty. By exploring the relationship between a largest connected component of the 0-test subgraph of a locally twisted cube and the distribution of the faulty nodes, the fault diagnosis of an n-dimensional locally twisted cube can be reduced to those of two constituent (n– 1)-dimensional locally twisted cube. On this basis, a fast pessimistic diagnosis algorithm is proposed. Given that there are no more than 2n– 2 faulty nodes, the algorithm can identify all the faulty nodes at the cost of at most one fault-free node being incorrectly diagnosed as faulty. The presented algorithm costs O(Nlog2N), where N is the total number of the nodes in the system. In contrast, the best known algorithm takes O(N2.5) time to achieve the same goal.Sequential diagnosis is a more practical approach to fault diagnosis of multicomputer networks then one-step diagnosis. The BC graphs (bijective connection graphs) are a large class of interconnection topologies. We describe a generalized sequential diagnosis algorithm for BC graphs under the PMC model. It is shown that BC graphs of n dimensions are ?(NloglogN /logN)-diagnosable, where N = 2n is the number of nodes of a BC graph.