A Novel Measurement for Network Reliability

Abstract

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 <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> be a network, <inline-formula><tex-math notation="LaTeX">$C\subset V(G)$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$G[C]$</tex-math></inline-formula> be a <i>connected subgraph</i> . Then <inline-formula><tex-math notation="LaTeX">$C$</tex-math></inline-formula> is called an <i><inline-formula><tex-math notation="LaTeX">$h$</tex-math><alternatives><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>h</mml:mi></mml:math><inline-graphic xlink:href="lin-ieq5-3023120.gif" xmlns:xlink="http://www.w3.org/1999/xlink"/></alternatives></inline-formula>-faulty-block</i> of <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> if <inline-formula><tex-math notation="LaTeX">$G-C$</tex-math></inline-formula> is disconnected, and every component of <inline-formula><tex-math notation="LaTeX">$G-C$</tex-math></inline-formula> has at least <inline-formula><tex-math notation="LaTeX">$h+1$</tex-math></inline-formula> nodes. The minimum cardinality over all <inline-formula><tex-math notation="LaTeX">$h$</tex-math></inline-formula> -faulty-blocks of <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> is called <i><inline-formula><tex-math notation="LaTeX">$h$</tex-math><alternatives><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>h</mml:mi></mml:math><inline-graphic xlink:href="lin-ieq12-3023120.gif" xmlns:xlink="http://www.w3.org/1999/xlink"/></alternatives></inline-formula>-faulty-block connectivity</i> of <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> , denoted by <inline-formula><tex-math notation="LaTeX">${FB}\kappa _h(G)$</tex-math></inline-formula> . In this article, we determine <inline-formula><tex-math notation="LaTeX">${FB}\kappa _h(Q_n)$</tex-math></inline-formula> for <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> -dimensional hypercube <inline-formula><tex-math notation="LaTeX">$Q_n$</tex-math></inline-formula> ( <inline-formula><tex-math notation="LaTeX">$n\geq 4$</tex-math></inline-formula> ), a classic interconnection network. We establish that <inline-formula><tex-math notation="LaTeX">${FB}\kappa _h(Q_n)=(h+2)n-3h-1$</tex-math></inline-formula> for <inline-formula><tex-math notation="LaTeX">$0\leq h\leq 1$</tex-math></inline-formula> , and <inline-formula><tex-math notation="LaTeX">${FB}\kappa _h(Q_n)=(h+2)n-4h+1$</tex-math></inline-formula> for <inline-formula><tex-math notation="LaTeX">$2\leq h\leq n-2$</tex-math></inline-formula> , respectively. Larger <inline-formula><tex-math notation="LaTeX">$h$</tex-math></inline-formula> -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 <inline-formula><tex-math notation="LaTeX">$h$</tex-math></inline-formula> -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 <inline-formula><tex-math notation="LaTeX">$h$</tex-math></inline-formula> increases, the <inline-formula><tex-math notation="LaTeX">$h$</tex-math></inline-formula> -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.

Topics & Concepts