TY - JOUR
T1 - A Novel Measurement for Network Reliability
AU - Lin, Limei
AU - Huang, Yanze
AU - Wang, Dajin
AU - Hsieh, Sun Yuan
AU - Xu, Li
N1 - Funding Information:
The authors declare that there is no conflict of interest regarding the publication of this article. This work was supported in part by the National Natural Science Foundation of China under Grant 61702100, Grant U1905211, Grant 61771140, Grant 61773415 and in part by Fok Ying Tung Education Foundation under Grant 171061.
Publisher Copyright:
© 1968-2012 IEEE.
PY - 2021/10/1
Y1 - 2021/10/1
N2 - The attackers in a network may have a tendency of targeting on a group of clustered nodes, and they hope to avoid the existence of significant large communication groups in the remaining network, such as botnet attack, DDoS attack, and Local Area Network Denial attack. Current various kinds of connectivity do not well reflect the fault tolerance of a network under these attacks. This observation inspires a new measure for network reliability to resist the block attack by taking into account of the dispersity of the remaining nodes. Let GG be a network, C\subset V(G)C⊂V(G) and G[C]G[C] be a connected subgraph. Then CC is called an hh-faulty-block of GG if G-CG-C is disconnected, and every component of G-CG-C has at least h+1h+1 nodes. The minimum cardinality over all hh-faulty-blocks of GG is called hh-faulty-block connectivity of GG, denoted by {FB}\kappa _h(G)FBκh(G). In this article, we determine {FB}\kappa _h(Q_n)FBκh(Qn) for nn-dimensional hypercube Q_nQn (n\geq 4n≥4), a classic interconnection network. We establish that {FB}\kappa _h(Q_n)=(h+2)n-3h-1FBκh(Qn)=(h+2)n-3h-1 for 0\leq h\leq 10≤h≤1, and {FB}\kappa _h(Q_n)=(h+2)n-4h+1FBκh(Qn)=(h+2)n-4h+1 for 2\leq h\leq n-22≤h≤n-2, respectively. Larger hh-faulty-block connectivity implies that an attacker will have to stage an attack to a bigger block of connected nodes, so that each remaining components will not be too small, which will in turn limit the size of large components. In other words, there will not be great disparity in sizes between any two remaining components, and hence there will less likely be a significantly large remaining communication group. The larger the hh-faulty-block, the more difficult for an attacker to achieve that goal. As a consequence, the resistance of the network against the attacker will increase. Our experiments also show that as hh increases, the hh-faulty-block gets larger, and the size disparity between any two remaining components decreases. In turn, as expected, the size of the largest remaining communication group becomes smaller.
AB - The attackers in a network may have a tendency of targeting on a group of clustered nodes, and they hope to avoid the existence of significant large communication groups in the remaining network, such as botnet attack, DDoS attack, and Local Area Network Denial attack. Current various kinds of connectivity do not well reflect the fault tolerance of a network under these attacks. This observation inspires a new measure for network reliability to resist the block attack by taking into account of the dispersity of the remaining nodes. Let GG be a network, C\subset V(G)C⊂V(G) and G[C]G[C] be a connected subgraph. Then CC is called an hh-faulty-block of GG if G-CG-C is disconnected, and every component of G-CG-C has at least h+1h+1 nodes. The minimum cardinality over all hh-faulty-blocks of GG is called hh-faulty-block connectivity of GG, denoted by {FB}\kappa _h(G)FBκh(G). In this article, we determine {FB}\kappa _h(Q_n)FBκh(Qn) for nn-dimensional hypercube Q_nQn (n\geq 4n≥4), a classic interconnection network. We establish that {FB}\kappa _h(Q_n)=(h+2)n-3h-1FBκh(Qn)=(h+2)n-3h-1 for 0\leq h\leq 10≤h≤1, and {FB}\kappa _h(Q_n)=(h+2)n-4h+1FBκh(Qn)=(h+2)n-4h+1 for 2\leq h\leq n-22≤h≤n-2, respectively. Larger hh-faulty-block connectivity implies that an attacker will have to stage an attack to a bigger block of connected nodes, so that each remaining components will not be too small, which will in turn limit the size of large components. In other words, there will not be great disparity in sizes between any two remaining components, and hence there will less likely be a significantly large remaining communication group. The larger the hh-faulty-block, the more difficult for an attacker to achieve that goal. As a consequence, the resistance of the network against the attacker will increase. Our experiments also show that as hh increases, the hh-faulty-block gets larger, and the size disparity between any two remaining components decreases. In turn, as expected, the size of the largest remaining communication group becomes smaller.
UR - http://www.scopus.com/inward/record.url?scp=85091683203&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85091683203&partnerID=8YFLogxK
U2 - 10.1109/TC.2020.3023120
DO - 10.1109/TC.2020.3023120
M3 - Article
AN - SCOPUS:85091683203
VL - 70
SP - 1719
EP - 1731
JO - IEEE Transactions on Computers
JF - IEEE Transactions on Computers
SN - 0018-9340
IS - 10
M1 - 9194366
ER -