Computer Science ›› 2021, Vol. 48 ›› Issue (4): 43-48.doi: 10.11896/jsjkx.201100139

• Computer Science Theory • Previous Articles     Next Articles

Subnetwork Reliability of (n,k)-bubble-sort Networks

FENG Kai, MA Xin-yu   

  1. School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China
  • Received:2020-06-24 Revised:2021-01-10 Online:2021-04-15 Published:2021-04-09
  • 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:
    National Natural Science Foundation of China(61502286).

Abstract: Topological properties of the interconnection network of a parallel computer system play an important role in realizing functions of the system.In order to measure the fault tolerance abilities of subnetworks in the parallel computer system which is built based on the (n,k)-bubble-sort network,the one-to-one relation between (n-m,k-m)-bubble-sort subnetworks of the (n,k)-bubble-sort network and specific strings is constructed,and the reliability of (n-m,k-m)-bubble-sort subnetworks in the (n,k)-bubble-sort network is studied under the node fault model.Assuming that 2≤k≤n-2 and 1≤m≤k-1,the probability that at least one (n-m,k-m)-bubble-sort subnetwork is fault-free in an (n,k)-bubble-sort network under the probabilistic fault condition is firstly given,and the simulation experiments demonstrate the accuracy of the given results.Then the calculation formula of the mean time to failure to maintain the fault-free status of different number of (n-m,k-m)-bubble-sort subnetworks is obtained,and the theoretical results are shown to be in accordance with the simulation results.

Key words: (n, Interconnection network, k)-bubble-sort network, Mean time to failure, Parallel computer system, Probabilistic failure, Subnetwork reliability

CLC Number: 

  • TP393.02
[1]CHANG Y,BHUYAN L N.A combinatorial analysis of subcube reliability in hypercube[J].IEEE Transactions on Compu-ters,1995,44(7):952-956.
[2]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.
[3]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.
[4]KUNG T L,TENG Y H,LIN C K,et al.Combinatorial analysisof the subsystem reliability of the split-star network[J].Information Sciences,2017,415:28-40.
[5]FENG K,JI Z,WEI W.Subnetwork reliability analysis in k-ary n-cubes[J].Discrete Applied Mathematics,2019,267:85-92.
[6]ABRAHAM S,PADMANABHAN K.Reliability of the hypercube[C]//Proceedings of the 1988 International Conference on Parallel Processing.Piscataway:IEEE,1988:90-94.
[7]ZHOU S,LI X,LI J,et al.Reliability assessment of multiprocessor system based on (n,k)-star network[J].IEEE Transactions on Reliability,2017,66(4):1025-1035.
[8]LV M,ZHOU S,SUN X,et al.Reliability evaluation of datacenter network DCell[J].Parallel Processing Letters,2018,28(4):1850015.
[9]FENG K,LI J.Reliability assessment of k-ary n-cube networks[J].Journal of Computer Applications,2019,39(11):3323-3327.
[10]SHAWASH N.Relationships among popular interconnectionnetworks and their common generalization[D].Oakland:Oakland University,2008.
[11]CHENG E,LIPTÁK L,SHERMAN D.Matching preclusion for the (n,k)-bubble-sort graphs[J].International Journal of Computer Mathematics,2010,87(11):2408-2418.
[12]YANG Y X,QIU Y N.Sub-network preclusion in(n,k)-bubble-sort networks[J].Computer Science,2017,44(11):264-267.
[13]ZHAO S,HAO R,WU L.The generalized connectivity of (n,k)-bubble-sort graphs[J].The Computer Journal,2019,62(9):1277-1283.
[14]ZHAO S,HAO R.The fault tolerance of(n,k)-bubble-sort networks[J].Discrete Applied Mathematics,2020,285:204-211.
[15]BONDY J A,MURTY U S R.Graph Theory[M].New York:Springer,2008:1-356.
[16]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, LI Jing. Study on Subnetwork Reliability of k-ary n-cubes [J]. Computer Science, 2020, 47(7): 31-36.
[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] LI A-ni, ZHANG Xiao, ZHAO Xiao-nan, ZHANG Bo-yang and LIU Chun-yi. Cloud Computing System Availability Evaluation for IaaS [J]. Computer Science, 2016, 43(10): 33-39.
[9] SHI Hai-zhong. Some New Cartesian Product Interconnection Networks [J]. Computer Science, 2013, 40(Z6): 265-270.
[10] SHI Hai-zhong. New Model for Interconnection Networks:Multipartite Group-theoretic Model [J]. Computer Science, 2013, 40(9): 21-24.
[11] . One Variety Conjectures of Complete-transposition Network [J]. Computer Science, 2012, 39(Z6): 404-407.
[12] 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.
[13] 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.
[14] LIANG Jia-rong,HUA Ren-jie. Reliability Analysis of star Network with Link Failures [J]. Computer Science, 2010, 37(6): 106-110.
[15] . [J]. Computer Science, 2007, 34(9): 253-255.
Full text



No Suggested Reading articles found!