International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 10, No. 10, 8 Oct. 2018
Cover page and Table of Contents: PDF (size: 615KB)
Reliability Evaluation and Analysis of Interconnection Network using Edge-disjoint Minimal Path Method
Full Text (PDF, 615KB), PP.11-17
Views: 0 Downloads: 0
Author(s)
Index Terms
Minimal path-set, probabilistic graph, network reliability, Interconnection Network
Abstract
The work carried out in this paper first generates all edge-disjoint minimal paths between every pair of nodes of the interconnection network. Then the merging of the edge disjoint minimal paths from each source nodes to the rest of nodes occurs only if such merging of minimal paths does not result into cycle. Thus, the merging operation ensures connectivity of all nodes of interconnection network without any cycle which is equivalent to the generation of spanning trees. In this manner, a number of spanning tree rooted on each source node are generated and ranked according to their generation. The network reliability is then evaluated from these spanning trees by applying sum of disjoint product techniques on these trees. A mathematical model followed by an algorithm is proposed in this paper. The proposed method is well illustrated by taking a suitable example network. The simulated results obtained from the proposed method are validated against existing method. The validation results show a tolerable level discrepancy in estimating the network reliability of some benchmark networks while using a very less number of spanning trees in leu of all possible spanning tress. The network reliability of some important interconnection networks viz. Hypercube, crossed cube, folded hypercube, mesh and torus are evaluated and analyzed. The network reliability of fully connected network with size varying from 3 to 10 are evaluated and analysed.
Cite This Paper
Ranjan Kumar Dash, Deepak Kumar Panda, "Reliability Evaluation and Analysis of Interconnection Network using Edge-disjoint Minimal Path Method", International Journal of Computer Network and Information Security(IJCNIS), Vol.10, No.10, pp.11-17, 2018. DOI:10.5815/ijcnis.2018.10.02
Reference
[1]K. B. Mishra, New Trends in System Reliability Evaluation, The Netherlands: Elsevier Science Publishers B.V., 1993.
[2]C R Tripathy, R K Dash, A New Fault-tolerant Interconnection Topology for ParallelSystems, Journal of The Institution of Engineers, (India), Computer Division, vol. 89, pp 83, 2008.
[3]M. Wilson, “An improved minimizing algorithm for sum of disjoint products,” IEEE Trans. Reliability, vol. 39, no. 1, pp. 42–45, Apr. 1990.
[4]S. Soh and S. Rai, “Experimental results on pre-processing of path/cut terms in sum of disjoint products technique,” IEEE Trans. Reliability, vol. 42, no. 1, pp. 24–33, Mar. 1993.
[5]A. Gebre and J. E. Ramirez-Marquez, “Element substitution algorithm for general two-terminal network reliability analysis,” IIE Trans.Operation Engineering, vol. 39, pp. 265–275, 2007.
[6]M. Rebaiaia, D. Ait-Kadi, A. Merlano “A Practical Algorithm for Network Reliability Evaluation Based on the Factoring Theorem – A Case Study of a Generic Radiocommunication System”, Journal of Quality Vol. 16, No. 5, pp. 323, 2009.
[7]M. Yeh, S. Lu, and S. Kuo, “OBDD-based evaluation of k-terminal network reliability,” IEEE Trans. Reliability, vol. 51, no. 4, pp. 443–451, 2002.
[8]G. Hardy, C. Lucet, and N. Limnios, “k-terminal network reliability measures with binary decision diagram,” IEEE Trans. Reliability, vol. 56, no. 3, pp. 506–515, 2007.
[9]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.
[10]W. Yeh, “A simple Heuristic Algorithm for Generating All Minimal Paths,” IEEE Trans. Reliability. vol. 56, no. 3, pp. 488-494, 2007.
[11]Alexandru O. Balan and Lorenzo Traldi “Preprocessing MinPaths for Sum of Disjoint Products” IEEE Transactions on Reliability, vol. 52, no. 3, pp 289-295, 2003.
[12]S. Y. Kuo, F. Yeh, and H. Y. Lin, “Efficient and Exact Reliability Evaluation for Networks with Imperfect Vertices” IEEE Transactions on Reliability, vol. 56, no. 2, 2007.
[13]J.Park, “All-Terminal Reliability Analysis of WirelessNetworks of Redundant Radio Modules”, IEEE Internet of Things Journal, vol. 3, no. 2, pp-219, 2016.
[14]L. Wei and L. Jie, “An improved cut-based recursive decomposition algorithm forreliability analysis of networks”, Earthquake Engineering and Engineering Vibration vol. 11, no.1, 2012.
[15]R. Mishra, S. K. Chaturvedi “A Cutsets-Based Unified Framework to Evaluate Network Reliability Measures”, IEEE Transactions on Reliability, Vol. 58, No. 4, 2009.
[16]T. E. TZoreff, “The disjoint shortest paths problem”, Discrete Applied Mathematics, vol. 85, pp. 113- 138, 1998.
[17]D. Wang, A Low-Cost Fault-Tolerant Structurefor the Hypercube, The Journal of Supercomputing, 20, 203–216, 2001.