Computer Science ›› 2020, Vol. 47 ›› Issue (7): 31-36.doi: 10.11896/jsjkx.190700170

• Computer Science Theory • Previous Articles     Next Articles

Study on Subnetwork Reliability of k-ary n-cubes

FENG Kai, LI Jing   

  1. School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China
  • Received:2019-07-25 Online:2020-07-15 Published:2020-07-16
  • About author:FENG Kai,born in 1987,Ph.D,associate professor,master supervisor,is a member of China Computer Federation.His main research interests include fault-tolerance of interconnection network,graph theory and its applications.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61502286) and Applied Basic Research Project of Shanxi Province (201701D221099)

Abstract: The k-ary n-cube is one of the most attractive interconnection network topologies for parallel computing systems.In order to accurately measure the fault tolerance on subnetworks in a k-ary n-cube,the k-ary (n-1)-cube reliability in a k-ary n-cube under the probabilistic fault model is studied.When k is an odd integer and k≥3,a lower bound on the k-ary (n-1)-cube reliability in a k-ary n-cube under the probability fault model is derived by clarifying the intersections of k-ary (n-1)-cube subnetworks in a k-ary n-cube,and an approximate k-ary (n-1)-cube reliability result is obtained.The approximation result is shown to be close to the simulation result,and these two results are getting overlapped as the node reliability decreases.Moreover,an algorithm is given for searching fault-free k-ary (n-1)-cubes in a k-ary n-cube in the presence of node failures,and the experimental results demonstrate the effectiveness of the proposed algorithm.

Key words: k-ary n-cube, Interconnection network, Parallel computer system, Probabilistic failure, Subnetwork reliability

CLC Number: 

  • TP393.02
[1]CHANG Y,BHUYAN L.A combinatorial analysis of subcubereliability in hypercube[J].IEEE Transactions on Computers,1995,44(7):952-956.
[2]WU X,LATIFI S.Substar reliability analysis in star networks[J].Information Sciences,2008,178:2337-2348.
[3]LIN L,XU L,ZHOU S,et al.The reliability of subgraphs in the arrangement graph[J].IEEE Transactions on Reliability,2015,64(2):807-818.
[4]LI X,ZHOU S,XU X,et al.The reliability analysis based on subsystems of (n,k)-star graph[J].IEEE Transactions on Reliability,2016,65(4):1700-1709.
[5]MAO W,NICOL D M.On k-ary n-cubes:theory and applica-tions[J].Discrete Applied Mathematics,2003,129(1):171-193.
[6]ANDERSON E,BROOKS J,GRASSL C,et al.Performance of the CRAY T3E Multiprocessor[C]//Proceedings of the 1997 ACM/IEEE Conference on Supercomputing.New York:ACM Press,1997:1-17.
[7]ADIGA N R,BLUMRICH M A,CHEN D,et al.Blue Gene/L torus interconnection network[J].IBM Journal of Research and Development,2005,49(2/3):265-276.
[8]CHEN X-B.Paired 2-disjoint path covers of faulty k-ary n-cubes[J].Theoretical Computer Science,2016,609:494-499.
[9]FENG K,JI Z,WEI W.Subnetwork reliability analysis in k-ary n-cubes[J].Discrete Applied Mathematics,2019,267:85-92.
[10]LV Y,FAN J,HSU D F,et al.Structure connectivity and substructure connectivity of k-ary n-cube networks[J].Information Sciences,2018,433/434:115-124.
[11]LIU A,WANG S,YUAN J,et al.The h-extra connectivity of k-ary n-cubes[J].Theoretical Computer Science,2019,784:21-45.
[12]WANG S,ZHANG G,FENG K.Fault tolerance in k-ary n-cube networks[J].Theoretical Computer Science,2012,460:34-41.
[13]YANG Y,LI J,WANG S.Embedding various cycles with prescribed paths into k-ary n-cubes[J].Discrete Applied Mathematics,2017,220:161-169.
[14]BONDY J A,MURTY U S R.Graph Theory[M].New York:Springer,2008:1-450.
[15]SANE S.Combinatorial Techniques[M].New Delhi:Hindustan Book Agency,2016:57-79.
[1] XU Jia-qing, HU Xiao-yue, TANG Fu-qiao, WANG Qiang, HE Jie. Detecting Blocking Failure in High Performance Interconnection Networks Based on Random Forest [J]. Computer Science, 2021, 48(6): 246-252.
[2] FENG Kai, MA Xin-yu. Subnetwork Reliability of (n,k)-bubble-sort Networks [J]. Computer Science, 2021, 48(4): 43-48.
[3] SHI Teng and SHI Hai-zhong. Model of Cartesian Product of Modulo p Residual Class Addition Group for Interconnection Networks [J]. Computer Science, 2020, 47(6A): 299-304.
[4] LIN Cheng-kuan, ZHAO Yuan, FAN Jian-xi and CHENG Bao-lei. Research on Completely Independent Spanning Trees Based on Degree of Vertices [J]. Computer Science, 2017, 44(6): 94-96.
[5] YANG Yu-xing and QIU Ya-na. Sub-network Preclusion in (n,k)-bubble-sort Networks [J]. Computer Science, 2017, 44(11): 264-267.
[6] SHI Hai-zhong, CHANG Li-ting, ZHAO Yuan, ZHANG Xin and WANG Hai-feng. Hamiltonian Decomposition of 2r-regular Graph Connected Cycles Networks [J]. Computer Science, 2016, 43(Z11): 304-307.
[7] XU Xi-rong, HUANG Ya-zhen, ZHANG Si-jia and DONG Xue-zhi. Feedback Numbers of Generalized Kautz Digraphs GK(3,n) [J]. Computer Science, 2016, 43(5): 13-21.
[8] SHI Hai-zhong. Some New Cartesian Product Interconnection Networks [J]. Computer Science, 2013, 40(Z6): 265-270.
[9] SHI Hai-zhong. New Model for Interconnection Networks:Multipartite Group-theoretic Model [J]. Computer Science, 2013, 40(9): 21-24.
[10] . One Variety Conjectures of Complete-transposition Network [J]. Computer Science, 2012, 39(Z6): 404-407.
[11] LI Yong,FAN Jian-xi,WANG Xi,ZHOU Wu-jun. LHL-cube Interconnection Networks and their Properties [J]. Computer Science, 2010, 37(8): 83-87.
[12] XING Chang-ming,LIU Fang-ai,YANG Lin. Practical Interconnection Network RPC(k) and its Routing Algorithms [J]. Computer Science, 2010, 37(6): 131-135.
[13] LIANG Jia-rong,HUA Ren-jie. Reliability Analysis of star Network with Link Failures [J]. Computer Science, 2010, 37(6): 106-110.
[14] . [J]. Computer Science, 2007, 34(9): 253-255.
[15] LI Tao, CHEN Yu-Ming ,ZHAO Jing-Long, NI Chang-Shun ,YANG Yu-Lu(Department of Computer Science and Technology, Nankai University, Tianjin 300071). [J]. Computer Science, 2005, 32(10): 20-22.
Full text



No Suggested Reading articles found!