Bounds on Reliability of Parallel Computer Interconnection Systems

The evaluation of residual reliability of large sized parallel computer interconnection systems is not practicable with the existing methods. Under such conditions, one must go for approximation techniques which provide the upper bound and lower bound on this reliability. In this context, a new approximation method for providing bounds on residual reliability is proposed here. The proposed method is well supported by two algorithms for simulation purpose. The bounds on residual reliability of three different categories of interconnection topologies are efficiently found by using the proposed method

Authors:

• Ranjan Kumar Dash
• Chita Ranjan Tripathy

Keywords:

• Parallel computer network
• reliability
• probabilisticgraph
• interconnection networks.

References:

[1] J. S. Provan, Bounds on the reliability of networks, IEEE Trans. Reliab.,
R-35, 260-268, 1986. 2
[2] K. S. Trivedi, Probability and Statistics with reliability, Queuing and
Computer Science Applications, Prentice Hall of India Pvt. Ltd., New
Delhi, 1992. 3
[3] C.R. Tripathy, R. N. Mahapatra and R. B. Misra, Reliability analysis of
hypercube multicomputers, Microelectronics and Reliability, An International
Journal, vol. 37, no.6, pp. 885-891, 1997. 4
[4] Y. G. Chen and M. C. Yuang, A cut-based method for terminal-pair
reliability, IEEE Trans. Reliability, vol. 45, no. 3, pp. 413-416, 1996.
5
[5] S. Soh and S. Rai, Experimental results on preprocessing of path/cut terms
in sum of disjoint products techniques, IEEE Transactions Reliability, vol.
42, no. 1, pp. 24-33, 1993. 6
[6] M. Al-Ghanim, A heuristic technique for generating minimal path and
cut sets of a general network, Computers and Industrial Engineering, vol.
36, pp. 45-55, 1999. 7
[7] Y. Lin, Using minimal cuts to evaluate the system reliability of a
sto-chastic-flow network with failures at nodes and arcs, Reliability
Engineering and System Safety, vol. 75, no. 3, pp. 41-46, 2002/3. 8
[8] S. K. Chaturvedi and K. B. Misra, An efficient multi-variable inversion
algorithm for reliability evaluation of complex systems using path sets,
International Journal of reliability, Quality and Safety Engineering, vol.
9, no. 3, pp. 237-259, 2002. 9
[9] H. Gud and X. Yang, Automatic creation of Markov models for reliability
assessment of safety instrumented systems, Reliability Engineering and
System Safety vol. 93, no. 6,pp. 829-837, 2008. 10
[10] R. K. Dash, N. K. Barpanda and C. R. Tripathy, Prediction of Reliability
of Multistage Interconnection Networks by Multi-decomposition
method, International Journal of Information Technology and Knowledge
Management, vol.1, no.2, pp. 439-448. 11
[11] A.Ramanathan and C. J. Colbourn, Bounds on all terminal reliability in
arc- parking, Arc Combinatorial, 23A, 91-94, 1987. 12
[12] C. J. Colbourn, The Combinatorics of Network Reliability, Oxford
University Press, Oxford, 1987. 13
[13] S. Soh , S. Rai , J. L. Trahan, Improved Lower Bounds on the
Reliability of Hypercube Architectures, IEEE Transactions on Parallel
and Distributed Systems, v.5 n.4, p.364-378, April 1994 14
[14] Y. Chen and Z. He, Bounds on the reliability of distributed systems with
unreliable nodes and links, IEEE Tans. Reliab., vol. 53, no.2, pp.205-215,
2004. 15
[15] J. Fang1, C. Huang, K. Lin, C. Liao and S. Feng The bi-panconnectivity
of the hypercube, International Conference on Networking, Architecture,
and Storage (NAS 2007), 2007, pp. 15-20. 16
[16] Z. Xue and S. Liu, An optimal result on fault-tolerant cycle-embedding
in alternating group graphs, Information Processing Letters, vol. 109, no.
21-22, pp. 1197-1201, 2009. 17
[17] N. Imani, H. Azad and S.G. Akl, Perfect load balancing on the star
interconnection network, The Journal of Supercomputing, vol. 41 , no. 3,
pp. 269-286, 2007. 18
[18] R.K. Dash and C. R. Tripathy, Comparative Analysis on Residual
Reliability of Hypercube and Torus Topologies under Link Failure model,
International Journal of Computing and Information Sciences (in press)