TY - JOUR
T1 - The reliability analysis based on subsystems of (n,k)-star graph
AU - Li, Xiaowang
AU - Zhou, Shuming
AU - Xu, Xiang
AU - Lin, Limei
AU - Wang, Dajin
N1 - Publisher Copyright:
© 1963-2012 IEEE.
PY - 2016/12
Y1 - 2016/12
N2 - As the cardinality of multiprocessor systems grows, the probability of arising malfunctioning or failing processors in the system is bound to increase. It is then of both practical and theoretical importance to know the reliability of the system as a whole. One metric for a system's overall reliability is the measurement of the collective effect of its subsystems becoming faulty. However, a challenge of this approach is that the subsystems often interact with each other in a complex manner, making the analysis difficult. Wu and Latifi (Int. Sci., vol. 178, pp. 2337-2348, Oct. 2008) proposed two schemes to evaluate the system reliability of the Star graph network under a probabilistic fault model. The first scheme computes the combinatorial probability of subgraphs to obtain an upper-bound on the reliability by considering the intersection of no more than three subgraphs. The second scheme computes an approximate combinatorial probability by completely neglecting the intersection among subgraphs. Recently, Lin et al. have applied this approach to investigate the reliability of the multiprocessor system based on the arrangement graph (IEEE Trans. Rel., vol. 62, no. 2, pp. 807-818, Jun. 2015). In this paper, we extend the above approach by computing both upper- and lower-bounds and considering the difference of the two, to establish the reliability of the (n, k) -Star graph, another extensively studied interconnection network for multiprocessor systems. More specifically, we compute a lower-bound and an upper-bound on the reliability by taking into account the intersection of no more than four or three subgraphs, respectively. The empirical study shows that the upper- and lower-bounds are both very close to the approximate results. Especially, the lower the single-node reliability goes, the closer the approximate reliability is to both lower- and upper-bounds.
AB - As the cardinality of multiprocessor systems grows, the probability of arising malfunctioning or failing processors in the system is bound to increase. It is then of both practical and theoretical importance to know the reliability of the system as a whole. One metric for a system's overall reliability is the measurement of the collective effect of its subsystems becoming faulty. However, a challenge of this approach is that the subsystems often interact with each other in a complex manner, making the analysis difficult. Wu and Latifi (Int. Sci., vol. 178, pp. 2337-2348, Oct. 2008) proposed two schemes to evaluate the system reliability of the Star graph network under a probabilistic fault model. The first scheme computes the combinatorial probability of subgraphs to obtain an upper-bound on the reliability by considering the intersection of no more than three subgraphs. The second scheme computes an approximate combinatorial probability by completely neglecting the intersection among subgraphs. Recently, Lin et al. have applied this approach to investigate the reliability of the multiprocessor system based on the arrangement graph (IEEE Trans. Rel., vol. 62, no. 2, pp. 807-818, Jun. 2015). In this paper, we extend the above approach by computing both upper- and lower-bounds and considering the difference of the two, to establish the reliability of the (n, k) -Star graph, another extensively studied interconnection network for multiprocessor systems. More specifically, we compute a lower-bound and an upper-bound on the reliability by taking into account the intersection of no more than four or three subgraphs, respectively. The empirical study shows that the upper- and lower-bounds are both very close to the approximate results. Especially, the lower the single-node reliability goes, the closer the approximate reliability is to both lower- and upper-bounds.
KW - (n,k)-Star graph
KW - approximate approach
KW - probabilistic fault model
KW - reliability
KW - reliability of subgraphs
UR - http://www.scopus.com/inward/record.url?scp=84978976111&partnerID=8YFLogxK
U2 - 10.1109/TR.2016.2570544
DO - 10.1109/TR.2016.2570544
M3 - Article
AN - SCOPUS:84978976111
SN - 0018-9529
VL - 65
SP - 1700
EP - 1709
JO - IEEE Transactions on Reliability
JF - IEEE Transactions on Reliability
IS - 4
M1 - 7505605
ER -