Research On T/T-diagnos Ability And T/K-diagnosability Of Augmented Cube Networks

With the rapid development of multi-processor computers and the expansion of processors,which will cause faults inevitably.In a multi-processor system,the process of identifying the fault is called fault diagnosis.The fault diagnosis mode of network system is divided into two kinds:circuit level diagnosis and system level diagnosis.In the circuit level diagnosis,the processor must be tested under the experimental environment,which will increase the complexity of the diagnosis process and reduce the efficiency in the practical application.Therefore,system level diagnosis becomes the mainstream in solving the problem of large-scale processor fault diagnosis.In the research of fault diagnosis,two diagnostic models are commonly used:PMC model and MM*model.In regular network topology,hypercube network(Qn represent n-dimensional hypercube network)has many advantages,such as good recursion,symmetry,fault tolerance and so on,therefore,it is often used by scholars.However,the diameter of hypercube network is positively correlated with its dimension,and the connection complexity of its network topology is positively correlated with the network size too,so the scalability is unoptimistic.For lots of variations on the basis of the hypercube topology structure,Choudum and Sunitha came up the augmented network(AQn represents n-dimensional augmented cube networks)not only has the good performance of hypercube,but also has a number of good properties that was not possessed by hypercube,such as its network diameter is only half of Qn,and it has good network embedded feature which is not possessed by other classes cube network structure.Based on the good topology of augmented cube network,this paper presents the fault diagnosis degree of augmented cube network under t/t-diagnosable and t/k-diagnosable strategies.First,by combining the topological properties of the augmented cube networks,which proved that AQn is(4n-8)/(4n-8)-diagnosable,namely,the t/t-diagnosable degree of the augmented cube networks is about twice as large as that of the t-diagnosable degree.In addition,some important properties of augmented cube networks that have not been studied before are proposed.By studying the properties of private neighbor nodes in augmented cube networks,which proved that AQn is t/k-diagnosable,and its diagnosability is t = 2(k+1)n-3(k+1)(k+2)/2+1,k?4n/9-13/9,and n>5.