Research Of Fault Diagnosis Strategy On The Exchanged Hypercube Networks

With the rapid development of very large scale processor systems, fault diagnosis of processors has become an important problem for the reliability of the systems. An excellent network model should have a good diagnosibility, so that all the fault processors in the system can be better diagnosed to be repaired or replaced. The hypercube is a good network model whose diagnosibility has caused wide attention. As a variant of hypercube network structure, the Exchanged Hypercube network keeps many good characteristics. According to the studies on the diagnosability of the Exchanged Hypercube networks under different diagnosis strategies, this paper obtained the diagnosabilities of the Exchanged Hypercube networks under different diagnosis strategies. Specific content of this paper is as follows:(1) By studying the topology of exchanged hypercube networks and the definition of the pessimistic one-step diagnosis strategy, this paper obtained the degree of diagnosability of Exchanged Hypercube under pessimistic one-step t1/t1 fault diagnosis strategy. The process of proof for diagnosability is presented here, and a final conclusion is drawn:the degree of diagnosability of the Exchanged Hypercube under pessimistic one-step t1/t1 fault diagnosis strategy is 2s where 1≤s≤t (respectively,2t, where 1≤t≤s) based on the PMC model and that is also 2s where 1≤s≤t (respectively,2t, where 1≤t≤s) based on the MM* model.(2) By introducing the concept of the t1/k -diagnosis strategy, this paper obtained the t1/k -diagnosability of Exchanged Hypercube. By proving the number of vertices adjacent to a set of k nodes is at least k(s+1)-k(k+1)/2+1 for each integer k satisfying 1≤k≤s+2 and 1≤s≤t, this paper demonstrates that the Exchanged Hypercube is t1(s,k)/k-diagnosable when 1≤s≤t and 0≤k≤s+1,where t1(s,k)=(k+1)(s+1)-(k+1)(k+2)/2+1.(3) According to the theory of local diagnosability, this paper proves the local diagnosibility property of the Exchanged Hypercube under the PMC model. We demonstrate that for an Exchanged Hypercube, the local diagnosability of every vertex is equal to its degree, so that the Exchanged Hypercube has the strong local diagnosability property under the PMC model. We prove that even if the fault edges has up to s-1, the Exchanged Hypercube keeps this strong local diagnosability property, when t≥s≥2.