Researches On Subnetwork Reliability Of K-ary N-cubes

The functions of a parallel computer system rely heavily on the interconnection network of the system.Reliability of the interconnection network is used to characterize the ability of the system to maintain some functions in a certain time,which is one of the key indicators to measure the performance of the network.The k-ary n-cube network is one of the famous recursive interconnection networks and several parallel systems have been built based on the k-ary n-cube.The subnetwork reliability of the interconnect network of a system plays an important role in the application.However,the evaluation system of the subnetwork reliability for k-ary n-cube networks has not been established,some problems such as the existence probability of fault-free subnetworks of at least a certain size and the disjoint subnetwork reliability with respect to the mean time to failure remain to study further.In order to enrich this research work,for the k-ary n-cube network with odd k(k?3),the existence probability of fault-free subnetworks and the subnetwork reliability with respect to the mean time to failure are studied in this paper.A lower bound of the existence probability of the fault-free k-ary(n-1)-cube subnetworks in a k-ary n-cube under the probability fault model is derived by clarifying the intersections of k-ary(n-1)-cube subnetworks in a k-ary n-cube,and an approximation of this subnetwork reliability is obtained.The theoretical result is shown to be close to the simulation result.Moreover,an algorithm is designed and implemented for searching fault-free k-ary(n-m)-cube subnetworks in a k-ary n-cube in the presence of node failures,and the experimental results demonstrate the effectiveness of the proposed algorithm.In addition,the reliability of disjoint k-ary(n-1)-cube subnetworks in a k-ary n-cube network under the node fault model and the edge fault model is studied,respectively.Specifically,under the node(edge)fault model,the calculation formula of the mean time to failure to maintain the fault-free status of disjoint k-ary(n-1)-cube subnetworks in a k-ary n-cube network is obtained based on the fixed partition pattern and the flexible partition pattern,respectively.The simulation experiments demonstrate the accuracy of the theoretical results.It is shown that the mean time to failure to maintain the fault-free status of disjoint k-ary(n-1)-cube subnetworks in the k-ary n-cube network under the node(edge)fault model based on the flexible partition pattern is higher than that based on the fixed partition pattern.Research results of this paper can provide a theoretical reference for the algorithm design of the parallel computer system which is built based on the k-ary n-cube network.