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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

7 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)189-203
Journal / PublicationTheoretical Computer Science
Online published17 Dec 2019
Publication statusPublished - 24 Feb 2020


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 Dm,n, we prove that: 1) the g-ECD of Dm,n under the MM model is (g+1)m+n−1 with n≥4, m≥3, and [Formula presented]; 2) Dm,n is [(k+1)(m−1)+n]/k-diagnosable under the MM model with n≥2, m≥2, and 0kn−1. Furthermore, for N-server DCN, we propose the first t/k-diagnosis algorithm on Dm,n under the MM model, namely t/k-Dm,n-DIAG with (NlogN) time complexity. Comparing with the traditional t-diagnosable algorithm by Ziwich and Duarte (2016) [11], on Dm,n, the t/k-Dm,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 (N(logN)3). These results provide a quantitative analysis for the reliability and availability evaluation of a large-scale DCN.

Research Area(s)

  • Data center networks, g-ECD, MM⁎ model, Reliability, t/k-diagnosis algorithm