Fault Diagnosis And Reliability Researchof Several Interconnection Networks

With the wide application of multiprocessor systems,the scale of the system is increasing,it is inevitable that some processors of the system will fail.Therefore,reliability and fault diagnosis capability analysis play an important role in the design and maintenance of multiprocessor systems.Interconnection networks are topological structures of multiprocessor systems.They are key to the performance of multiprocessor systems.To choose an appropriate interconnection network,the properties of interconnection networks have to be explored.Connectivity and diagnosability are usually used to assess the reliability and fault diagnosis abilities of interconnection networks.In order to better study the performance of interconnection networks,some new parameters have been proposed,such as restricted connectivity,super connectivity,extra connectivity,pessimistic diagnosability and t/k-diagnosability.Star graphs and Split-Star networks have been extensively studied because of their excellent properties such as small diameter,symmetry,separability and high fault tolerance.Firstly,the reliability analysis of the star graph S_n is studied in this article.We determine the minimum vertex-boundary of the star graph S_n and introduce a vertex set F satisfying a necessary condition,that is S_n-F has a large component and all the remaining components at most have h-1 vertices.Furthermore,the h-extra connectivity of the star graphs is proved that Kh(S_n)=(h?1)n-4h+2(3?h?4).The research result improves the fault-tolerant ability of the star graphs theoretically.Next,we discuss the fault diagnosis ability of Split-Star network in the article.The pessimistic diagnosability of the n-dimension Split-Star network is determined under the PMC model,that is tp(S_nk)= 4n-9.The results show that the pessimistic diagnosability is twice as much as its traditional t-diagnosability,which significantly improves the fault diagnosability of Split-Star networks.Finally,the relationship between the h-extra connectivity and the t1/k-diagnosability of k-ary n-cube Q_n~k is studied in this paper.And we determine the h-extra connectivity of k-ary n-cube Q_n~k is equal to its t/k-diagnosability under the PMC model.Similarly,for BC networks:Kh(X_n)= t(n,h)and t(n,h)=(k+1)n-1/2(k+1)(k + 2)+ where k?4,1?h?n-4.The results show that the t/k-diagnosability of some interconnection networks is obtained by its h-extra connectivity.