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: Parallel computer system, Interconnection network, k-ary n-cube, Subnetwork reliability, Probabilistic failure

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] 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.
[2] 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.
[3] YANG Yu-xing and QIU Ya-na. Sub-network Preclusion in (n,k)-bubble-sort Networks [J]. Computer Science, 2017, 44(11): 264-267.
[4] 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.
[5] 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.
[6] SHI Hai-zhong. Some New Cartesian Product Interconnection Networks [J]. Computer Science, 2013, 40(Z6): 265-270.
[7] SHI Hai-zhong. New Model for Interconnection Networks:Multipartite Group-theoretic Model [J]. Computer Science, 2013, 40(9): 21-24.
[8] . One Variety Conjectures of Complete-transposition Network [J]. Computer Science, 2012, 39(Z6): 404-407.
[9] 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.
[10] 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.
[11] LIANG Jia-rong,HUA Ren-jie. Reliability Analysis of star Network with Link Failures [J]. Computer Science, 2010, 37(6): 106-110.
[12] . [J]. Computer Science, 2007, 34(9): 253-255.
[13] 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



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .