The Component Diagnosability of Hypercubes with Large-Scale Faulty Nodes

2020/11/26 by Shurong Zhang, Dongyue Liang, Lin Chen +3 · 4 citations
Computer Science · Engineering · #Interconnection Networks and Systems #Software-Defined Networks and 5G #Advanced Optical Network Technologies

paper · doi:10.1093/comjnl/bxaa155

Abstract

Abstract The diagnosability is one of the most important measures of the reliability of networks. Consider the setting where there are large-scale failures that disconnect the network and result in many components. Then, the diagnosability is closely related to the number of components. In this paper, we define and study the \boldsymbolg-component diagnosability of network \boldsymbolG, which is denoted by \boldsymbolct_g(G) and has not been addressed before. \boldsymbolct_g(G) is the maximum number of nodes in the faulty node set \boldsymbolF of \boldsymbolG such that \boldsymbolG-F has at least \boldsymbolg components and diagnosis model can identify all nodes in \boldsymbolF. Under PMC and MM^* diagnosis models, we show that, in the hypercube \boldsymbolQ_n (n≥ 7), \boldsymbolct_g+1(Q_n)=-(1/2)g²+(n-3/2)g+n when \boldsymbolg≤ n-1. Moreover, we determine the \boldsymbol(n+1)-component diagnosability \boldsymbolct_n+1(Q_n)=n²/2+n/2-2 for \boldsymboln≥ 7.

Citations

• Diagnosability Evaluation of the Data Center Network DCell

Cited by

• The cyclic diagnosability of Cayley graphs generated by transposition triangle-free unicyclic graphs under the PMC and MM* models
• The Cyclic Diagnosability Of Hypercubes Under The PMC Model And The MM* Model
• Component Fault Diagnosis and Fault Tolerance of Alternating Group Graphs
• Relationship Between Component Connectivity And Component Diagnosability Of Some Regular Networks

Related

• Hybrid Fault diagnosis capability analysis of Hypercubes under the PMC model and MM* model
• The Cyclic Diagnosability Of Hypercubes Under The PMC Model And The MM* Model
• The h-edge tolerable diagnosability of balanced hypercubes
• The Conditional Diagnosability with g-Good-Neighbor of Exchanged Hypercubes
• Relationship Between Component Connectivity And Component Diagnosability Of Some Regular Networks