The Reliability Evaluation of Cube Based Interconnection Networks Under Node Failure Model

Nalin Kanta Barpanda, S. Sunani, P. Rath


Under node failure model, a cube may operate in a gracefully degradable manner by supporting parallel algorithms in smaller fault-free cubes. In order to reduce execution slowdown in cube with a given faults, it is essential to identify the maximum healthy sub cubes (maximal incomplete sub cube) in the faulty cube. This paper proposes a new method to identify all the maximal incomplete sub cubes present in a faulty cube taking maximum fault tolerance level i.e. number of faulty nodes is equal to the system dimension. The procedure is a distributed one, as every healthy node next to a failed one performs the same procedure independently and concurrently. Then the reliability expression for the cube is derived. This method is well supported by an efficient algorithm which runs polynomially. The proposed method is found to be simple, general and efficient and thus is applicable to all the cube based topologies.

Index terms:-Cube, Maximal Incomplete sub cube, Discarded region, Reliability.


R.L. Sharma, Network topology optimization-“The Art and Science of network design”, Van Nostrand Reinhold,1990.

F.T. Leighton Introduction to parallel algorithms and architectures, Arrays, Trees, hyper cubes, morgan kaufmann,1992.

Y. Saad and M. H. Schultz, Topological properties of Hypercubes, IEEE Trans. Comput.,vol. 37, no. 7, pp. 86-88, 1988.

S.G.Ziavras-“A versatile family of reduced hypercube interconnections networks”, IEEE trans on parallel and distributed systems .Vol,Nov.1994.

H. P. Katseff, “Incomplete hypercube”, IEEE Trans. On Computers, vol. 37, no. 5, 1988.

N.F.Tzeng, H.L.chen and P.J.chuang,,“Embeddings in incomplete hyper cubes”. In Proc. Int. Conf. Parallel processing, vol-1,pp.335-339,1990.

M.A.Sridhar and C.S Raghavendra, “On finding maximal sub cubes in Residual Hyper cubes”Proc. of IEEE Symp. on Parallel and distributed processing pp 870-873, 1990.

S.Latifi, “Distributed Sub cube identification Algorithmsfor Reliable hypercubes,” Information processing letters, vol.38, pp.315-321, 1991.

H.LChen and N.F Tieng, “Subcube Determination in faulty hyper cube”, IEEE Trans. on computers, vol46, no8, pp 87-89,1997.

J.S.Fu, “Longest fault free paths in hyper cubes with vertex faults”, Inf. Sci. vol. 176, no. 7, pp.759-771, 2006.

J.M.Xu, M.J.Ma, and Z.Z.Du. “Edge–fault tolerant properties of hyper cubes and folded hyper cubes”, Australian J. Combinatorics, vol. 35, no. 1, pp. 7-16, 2006.

W. Wang and X. Chen, “A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges”, J. Information Processing Letters, vol. 107, pp.205–210, 2008.

S. Soh, S. Rai and J.L.Trahan “Improved lower bounds on the reliability of hypercube architectures”,IEEETrans.on parallel and distributed systems, vol.5,no.4,pp 364-378,1994.

F.Boesch,D.Gross and C.Suffel “A coherent model for reliability of multiprocessor networks”, IEEE Trans.on reliability, vol.45,no 4,pp 678-684,1996.

Y. Chen and Z. He “Bounds on the Reliability of distributed systems”,IEEETrans.on reliability, vol.53,no 2,pp 205-215,2004.

پاراگلایدر Full Text: PDF


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

ISSN : 2251-1563