Bounds on Reliability of Parallel Computer Interconnection Systems

Authors: Ranjan Kumar Dash, Chita Ranjan Tripathy

Abstract:

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

Keywords: Parallel computer network, reliability, probabilisticgraph, interconnection networks.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1059998

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)