Reliability analysis of data center networks based on precise and imprecise diagnosis strategies

Fault tolerance and reliability are the crucial issues for data center networks (DCNs). Both the g-extra conditional diagnosis (g-ECD) precise strategy and the t/k-diagnosis imprecise strategy play essential role in the reliability of networks. For the data center network based on DCell structure D_m,n, we prove that: 1) the g-ECD of D_m,n under the MM^⁎ model is (g+1)m+n−1 with n≥4, m≥3, and [Formula presented]; 2) D_m,n is [(k+1)(m−1)+n]/k-diagnosable under the MM^⁎ model with n≥2, m≥2, and 0≤k≤n−1. Furthermore, for N-server DCN, we propose the first t/k-diagnosis algorithm on D_m,n under the MM^⁎ model, namely t/k-D_m,n-DIAG with O (NlogN) time complexity. Comparing with the traditional t-diagnosable algorithm by Ziwich and Duarte (2016) [11], on D_m,n, the t/k-D_m,n-DIAG can identify the number of faulty vertices is almost k times larger than the t-diagnosable algorithm, where the time complexity of t-diagnosable algorithm is about O (N(logN)³). These results provide a quantitative analysis for the reliability and availability evaluation of a large-scale DCN.