The extra connectivity, extra conditional diagnosability and t/k-diagnosability of the data center network DCell

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

34 Scopus Citations
View graph of relations


  • Xiaoyan Li
  • Jianxi Fan
  • Cheng-Kuan Lin
  • Baolei Cheng
  • Xiaohua Jia

Related Research Unit(s)


Original languageEnglish
Pages (from-to)16-29
Journal / PublicationTheoretical Computer Science
Online published24 Sep 2018
Publication statusPublished - 25 Apr 2019


Connectivity and diagnosability are two important metrics in evaluating the fault tolerability of a network. The g-extra connectivity and the g-extra conditional diagnosability are both defined under the restraint that every component of the network removing a faulty vertex set has at least + 1 fault-free vertices. The t/k-diagnosability is an outstanding diagnosis strategy, in which the identified faulty vertex set is allowed to contain at most k fault-free vertices. As a well-known model for a large-scale data center network (DCN) with a server-centric structure, the m-dimensional DCell with n-port switches and tm,n servers, Dm,n, has many desirable properties. In this paper, we first investigate the g-extra connectivity of Dm,n for 0 ≤ gn − 1. Based on this, we establish the g-extra conditional diagnosability of Dm,n under the PMC model for 0 ≤ gn − 1. Finally, we evaluate the t/k-diagnosability of Dm,n under the PMC model for 1 ≤ kn − 1.

Research Area(s)

  • Data center networks, DCell, Fault tolerance, g-extra conditional diagnosability, g-extra connectivity, PMC model, t/k-diagnosability