Research On Fault Diagnosis Algorithms Of Two Classical Rules Interconnection Networks

Level fault diagnosis is a kind of important fault diagnosis in network system.By analyzing the property of t-fault and t/k-fault diagnosable under MM*fault model,In the term of t-fault diagnosable,we structure a extended star structure in a defined network topology and use the graph theory to analyze and demonstrate the symptoms of a given MM*model,then identify the state of the root node of the extended star structure.In the end,we propose a new system level fault diagnosis called extended star structure algorithm for the multi processor network system with extended star structure and certain diagnosability.The theoretical demonstration and experimental results show that this algorithm can easily,fastly and correctly identify the all faulty node in the multiprocessor network system,whose time complexity of the algorithm is O(N),where N is the number of the all nodes of the network.In the term of t/k-fault diagnosable,we use Breadth First Search to obtain O-subgraph of test,combined the conclusion has been proved,we propose a new t/k-fault diagnosable algorithm under hypercube,whose time complexity of the algorithm is O(2nn2),where n is the number of the all nodes of the network.