Computer Science ›› 2021, Vol. 48 ›› Issue (6): 253-260.doi: 10.11896/jsjkx.200900203

• Computer Network • Previous Articles     Next Articles

Fault-tolerant Routing Algorithm in BCube Under 2-restricted Connectivity

YI Yi, FAN Jian-xi, WANG Yan, LIU Zhao, DONG Hui   

  1. School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China
  • Received:2020-09-29 Revised:2021-01-25 Online:2021-06-15 Published:2021-06-03
  • About author:YI Yi,born in 1996,postgraduate.Her main research interests include parallel and distributed systems and graph algorithms.(20194227013@stu.suda.edu.cn)
    FAN Jian-xi,born in 1965,Ph.D,Professor,Ph.D supervisor.His main research interests include parallel and distributed systems,computer networks and graph algorithms.
  • Supported by:
    Joint Fund of the National Natural Science Foundation of China(U1905211),National Natural Science Foundation of China(61972272) and Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.

Abstract: BCubeis a data center network with good performance.Compared to traditional tree-shaped data center network,BCube has not only higher fault-tolerance performance but also superior scalability.Currently,the research on BCube can be reduced to logical structure (a special generalized hypercube),in which the switches are regarded as transparent devices.In actual application,with the continuous increase of network scale,vertex failure has become inevitable.Therefore,it is meaningful to study the fault-tolerant routing of the network.At present,there is some research on fault-tolerant routing of BCn,k.However,the fault-tolerant routing of BCn,k under the 2-restricted connectivity has not been studied yet.Before proposing the algorithm,the 2-restricted connectivity of BCn,k is firstly proved which is 3(k+1)(n-1)-2n for k≥3 and n≥3.Then a fault-tolerant routing algorithm with a time complexity of O(κ(BCn,k)3) is proposed where κ(BCn,k)=(k+1)(n-1) denotes the connectivity of BCn,k.The proposed algorithm can find a fault-free path between any two distinct fault-free vertices when the number of faulty vertices is less than 3(k+1)(n-1)-2n and every fault-free vertex has at least two fault-free neighbors.

Key words: 2-restricted connectivity, BCube, Data center networks, Fault-tolerant routing, Time complexity

CLC Number: 

  • TP393
[1]GHEMAWAT S,GOBIOFF H,LEUNG S T.The google filesystem[J].ACM Symposium on Operating System Principles,2003,37(5):29-43.
[2]CHANG F,DEAN J,GHEMAWAT S,et al.Bigtable:A distri-buted storage system for structured data[C]//7th Symposium on Operating Systems Design and Implementation.ACM,2006:6-8.
[3]ISARD M,BUDIU M,YU Y,et al.Dryad:Distributed data-pa-rallel programs from sequential building blocks[J].Operating Systems Review,2007,41(3):59-72.
[4]AZIZI S,HASHEMI N,KHONSARI A.HHS:An efficient network topology for large-scale data centers[J].Journal of Supercomputing,2016,72(3):1-26.
[5]GREENBER A G,HAMILTON J R,JAINT N,et al.VL2:A scalable and flexible data center network[J].ACM SIGCOMM Computer Communication Review,2011,39(4):51-62.
[6]HAMEDAZIMI N,QAZI Z,GUPTA H,et al.FireFly:A reconfigurable wireless data center fabric using free-space optics[J].ACM SIGCOMM Computer Communication Review,2014,44(4):319-330.
[7]ZHANG Z,DENG Y H,MIN G Y,et al.HSDC:A highly scalable data center network architecture for greater incremental scalability[J].IEEE Transactions on Parallel and Distributed Systems,2019,30(5):1105-1119.
[8]GUO C X,WU H T,TAN K,et al.DCell:A scalable and fault-tolerant network structure for data centers[J].ACM SIGCOMM Computer Communication Review,2008,38(4):75-86.
[9]WANG X,FAN J X,LIN C K,et al.BCDC:A high-perfor-mance,server-centric data center network[J].Journal of Compu-ter Science and Technology,2018,33(2):400-416.
[10]GUO C X,LU G H,LI D,et al.BCube:A high performance,server-centric network architecture for modular data centers[J].ACM SIGCOMM Computer Communication Review,2009,39(4):63-74.
[11]PUSHPARAJ J,VEDA B P,SOUMYA J.A link fault tolerant routing algorithm for mesh of tree based network-on-chips[C]//2019 IEEE International Symposium on Smart Electronic Systems.IEEE,2019:181-184.
[12]HANG Y X,XU J F,NAN L M.Congestion-aware adaptive fault-tolerant routing algorithm for network-on-chip[J].Journal of Chinese Mini-Micro Computer Systems,2018,39(2):262-269.
[13]CHAKIB N,MOHAMED S.A new fault tolerant routing algorithm for networks on chip[J].Embedded and Real-Time Communication Systems,2019,10(3):68-85.
[14]THUAN B T,NGOC L B,KANEKO K.A stochastic link-fault-tolerant routing algorithm in folded hypercubes[J].Journal of Supercomputing,2018,74(10):5539-5557.
[15]WANG G J,FAN J X,LV Y L,et al.The constructive algo-rithm of vertex disjoint paths in the generalized hypercube under restricted connectivity[J].Journal of Internet Technology,2019,20(6):1995-2006.
[16]GUO L L,WANG X,LIN C K,et al.A fault-free unicast algorithm in the generalized hypercube with restricted faulty vertices[J].International Journal of Foundations of Computer Science,2017,28(7):915-929.
[17]WANG G J,LIN C K,FAN J X,et al.The fault-tolerant hamiltonicity and hamiltonian connectivity of BCube with various faulty elements[J].Journal of Computer Science and Technology,2020,35(5):1064-1083.
[18]DUH D R,CHEN G H,HSU D F.Combinatorial properties of generalized hypercube graphs[J].Information Processing Letters,1996,57(1):41-45.
[19]TONG M S,LIU C H,FAN T Y.Routing algorithms for shortest paths in faulty generalized hypercubes[J].Chinese Journal of Computers,1998,21(12):1074-1083.
[20]ESFAHANIAN A H,HAKIMI S L.On computing a conditio-nal edge-connectivity of a graph[J].Information Processing Letters,1988,27(4):195-199.
[21]LATIFIFI S,HEGD M V,NARAGHIPOUR M.Conditionalconnectivity measures for large multiprocessor systems[J].IEEE Transactions on Computers,1994,43(2):218-222.
[22]GUO L L.Research on conditional connectivity and fault-tole-rant routing of generalized hypercubes[D].Suzhou:Soochow University,2018.
[23]WEI C C,HSIEH S Y.H-restricted connectivity of locally twisted cubes[J].Discrete Applied Mathematics,2016,615:78-90.
[24]LV M J,CHENG B L,FAN J X,et al.The conditional reliability evaluation of data center network BCDC[J/OL].The Computer Journal,2020,https://doi.org/10.1093/comjnl/bxaa078.
[25]WANG X,FAN J X,ZHOU J Y,et al.The restricted h-connectivity of the data center network DCell[J].Discrete Applied Mathematics,2016,203:144-157.
[1] PAN Zhi-yong, CHENG Bao-lei, FAN Jian-xi, BIAN Qing-rong. Algorithm to Construct Node-independent Spanning Trees in Data Center Network BCDC [J]. Computer Science, 2022, 49(7): 287-296.
[2] ZHANG Deng-ke, WANG Xing-wei, HE Qiang, ZENG Rong-fei, YI bo. State-of-the-art Survey on Reconfigurable Data Center Networks [J]. Computer Science, 2021, 48(3): 246-258.
[3] LIN Cheng-kuan, WANG Ming-cheng, GUO Li-li and DU Man-yi. Shortest Routing Algorithm Based on Target Node in Mesh Network with Faulty Area [J]. Computer Science, 2017, 44(Z6): 252-257.
[4] HUANG Hong and YU Hong-fang. Smooth Energy-saving Algorithm Based on Link-ranking [J]. Computer Science, 2017, 44(6): 68-74.
[5] QIAO Yan, JIAO Jun and RAO Yuan. Traffic Estimation for Data Center Network Based on Traffic Characteristics [J]. Computer Science, 2017, 44(2): 171-175.
[6] FANG Xian-jin, WANG Li, KANG Jia and LIU Jia. On Dendritic Cell Algorithm and its Theoretical Investigation [J]. Computer Science, 2015, 42(2): 131-133.
[7] WANG Shu-xi and LI An-yu. Multi-adjacent-vertexes and Multi-shortest-paths Problem of Dijkstra Algorithm [J]. Computer Science, 2014, 41(6): 217-224.
[8] JIN Yi-ting,WANG Wan-liang,ZHAO Yan-wei and JIANG Yi-bo. Fast Corner Detector Based on Chord-to-Point Distance Accumulation [J]. Computer Science, 2014, 41(4): 306-308.
[9] ZHOU Yi-min and LI Guang-yao. Analysis of Probable Lower Bound of Time Complexity of Some Classical Algorithms Based on Decision Tree and Information Theory [J]. Computer Science, 2013, 40(Z11): 238-241.
[10] YIN Dong,MU De-jun,DAI Guan-zhong. Research on Server Centric Data Center Network Design [J]. Computer Science, 2012, 39(3): 110-112.
[11] WANG Qin,LI Lei,LU Cheng-yong,SUN Fu-ming. Average Computational Time Complexity Optimized Dynamic Particle Swarm Optimization Algorithm [J]. Computer Science, 2010, 37(3): 191-194288.
[12] . [J]. Computer Science, 2008, 35(11): 164-165.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!