Component Reliability of a Class of Regular Networks and Its Applications

摘要

With the continuous attention to the parallel computing system, the reliability of the system, which is mainly measured by two parameters, connectivity and diagnosability, needs to be constantly studied and improved. At present, the component connectivities of some networks have been extensively studied, while the component diagnosabilities of these networks have rarely involved in. In this article, some networks with common characteristics are summarized as a class of regular networks. The definition of this kind of networks is given, and its reliability based on component failures is determined. To be specific, we prove that C kappa(m+)(1)(G) = m(k - 1) - ((m)(2)) + 1 for 1 <= m <= k - ct(m+1) (G) = (m+1)k - ((m)(2)) - 2 m for 1 <= m <= k-2 under the PMC model, where c kappa(m+1) (G) and ct(m+1)(G) represent the (m + 1)-component connectivity and the (m + 1)-component diagnosability of such networks G, respectively. Based on this, we design a low time complexity component diagnosis algorithm for this kind of networks. As applications, the above two component reliability parameters of many famous networks are explored. Furthermore, the proposed diagnosis algorithm is simulated on these networks, and the results show that the algorithm has high diagnosis accuracy for Various networks.

关键词