Evaluating Robustness of Subnetworks for the Split-Star Network

The robustness of subnetworks for the interconnection network of a computer system is an important consideration for the system performance. It can be measured by the extent to which subnetworks can stay fault-free when faults are present in the system. In this paper, we evaluate the subnetwork robustness for the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>-dimensional split-star network <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$S_{n}^{2}$</tex-math></inline-formula>. Let <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$S_{n-m}^{2}, 1 \leq m \leq n-3$</tex-math></inline-formula> , be a subnetwork of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$S_{n}^{2}$</tex-math></inline-formula>, and let <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</i> be the node reliability, the probability that a single node remains fault-free. We determine two values that reflect how robust <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$S_{n-m}^{2}$</tex-math></inline-formula> subnetworks are, from two perspectives. We first establish the upper/lower bounds for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal{F}_{m} (S_{n}^{2})$</tex-math></inline-formula>, the minimum number of faulty nodes to make all <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$S_{n-m}^{2}$</tex-math></inline-formula> subnetworks faulty. Then, we determine the subnetwork reliability, denoted by <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal{R}_{m} (S_{n}^{2}, p)$</tex-math></inline-formula>, which is the probability that at least one fault-free <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$S_{n-m}^{2}$</tex-math></inline-formula> subnetwork exists in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$S_{n}^{2}$</tex-math></inline-formula>, given the node reliability <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</i>. The upper/lower bounds and an approximation expression for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal{R}_{m} (S_{n}^{2}, p)$</tex-math></inline-formula> are obtained. We also propose a simulation method to estimate <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal{R}_{m} (S_{n}^{2}, p)$</tex-math></inline-formula>. The experimental results show that a) when <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</i> is relatively low, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal{R}_{m} (S_{n}^{2}, p)$</tex-math></inline-formula> can be approximated by the mean value of its upper and lower bounds, or the estimation value by the approximation expression; b) when <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</i> is high, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal{R}_{m} (S_{n}^{2}, p)$</tex-math></inline-formula> can be more accurately estimated by our simulation method.