Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (7): 287-296.doi: 10.11896/jsjkx.210500170

• Computer Network • Previous Articles     Next Articles

Algorithm to Construct Node-independent Spanning Trees in Data Center Network BCDC

PAN Zhi-yong, CHENG Bao-lei, FAN Jian-xi, BIAN Qing-rong   

  1. School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China
  • Received:2021-05-25 Revised:2021-09-15 Online:2022-07-15 Published:2022-07-12
  • About author:PAN Zhi-yong,born in 1998,postgra-duate.His main research interests include parallel and distributed systems and graph algorithms.
    CHENG Bao-lei,born in 1979,associate professor.His main research interests include parallel and distributed systems,algorithms,interconnection architectures and software testing.
  • Supported by:
    National Natural Science Foundation of China(U1905211,62172291,61572337),Natural Science Foundation of Jiangsu Higher Education Institutions of China(18KJA520009) and Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.

PDF (PC)

388

Abstract: As the foundation of cloud computing technology,the communication performance of data center networks has become a research hotspot in recent years.And as an important infrastructure of data center networks,independent spanning trees(ISTs) attract much attention of researchers because of their application in reliable communication,fault-tolerant broadcasting and secure message distribution,and remarkable results have been obtained on some special networks.But only a few results are reported on the line graphs.A new server-centric network called BCDC was proposed in 2018.Its logic graph is the line graph of crossed cube and is (2n－2)-regular.In this paper,an algorithm is proposed to construct the independent spanning trees on BCDC.Firstly,2n－2 trees are constructed by a parallel algorithm on crossed cube.Then,connect these trees by a special rule,and transfer these trees into 2n－2 independent trees on BCDC through a way of transformation.Finally,the rest nodes of BCDC are connected to these trees by an algorithm which is proposed with time complexity O(N),where N is the number of nodes on BCDC.As a result,we will obtain 2n－2 ISTs rooted at node [ r,N(r,2)] on BCDC,where r is an arbitrary node in n dimensional crossed cube CQn.

Key words: BCDC, Crossed cube, Data center networks, Independent spanning trees, Line graph

CLC Number: 

  • TP311.12
[1]ZUO P,SHU Y A.Dynamic Multi-Path Load Balancing Method Based on Feedforward Neural Network in DCN[J].Computer Engineering,2021,47(9):113-119.
[2]ZHOU X,LU D X,HUO J H,et al.Performance analysis ofdata center optical interconnection based on single-side band modulation technologies [J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2020,32(5):707-718.
[3]LI D,WU J.On data center network architectures for interconnecting dual-port servers [J].IEEE Trans on Computers,2015,64(11):3210-3222.
[4]WANG X,FAN J X,LIN C K,et al.A high-performance,server-centric data center network [J].Journal of Computer Science and Technology,2018,33(2):38-44.
[5]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.
[6]ITAI A,RODEH M.The multi-tree approach to reliability in distributed networks [J].Information and Computation,1988,79:43-59.
[7]ZEHAVI A,ITAI A.Three tree-paths [J].Journal of GraphTheory,1989,13(2):175-188.
[8]HUCK A.Independent trees in planar graphs [J].Graphs and Combinatorics,1999,15(1):29-77.
[9]OBOKATA K,IWASAKI Y,BAO F,et al.Independent span-ning trees of product graphs and their construction [J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences,1996,E79-A(11):1894-1903.
[10]KIM J S,LEE H O,CHENG E,et al.Independent spanningtrees on even networks [J].Information Sciences,2011,181(13):2892-2905.
[11]KIM J S,LEE H O,CHENG E,et al.Optimal independentspanning trees on odd graphs [J].Journal of Supercomputing,2011,56(2):212-225.
[12]CHENG B L,FAN J X,JIA X H,et al.Independent spanning trees in crossed cubes [J].Information Sciences,2013,233(1):276-289.
[13]WANG Y,FAN J X,ZHOU G,et al.Independent spanningtrees on twisted cubes [J].Journal of Parallel and Distributed Computing,2012,72(1):58-69.
[14]CHENG B L,FAN J X,JIA X H.Dimensional-permutation-based independent span- ning trees in bijective connection networks [J].IEEE Transactions on Parallel and Distributed Systems,2015,26(1):45-53.
[15]LI H,HE W H,YANG W H,et al.A note on edge-disjointHamilton cycles in line graphs [J].Graphs and Combinatorics,2016,32:741-744.
[16]HASUNUMA T.Structural properties of subdivided-line graphs [J].Journal of Discrete Algorithms,2015,31:69-86.
[17]HARVEY D J,WOOD D R.Treewidth of the line graph of a complete graph [J].Journal of Graph Theory,2015,79(1):48-54.
[18]TIAN T,XIONG L M.Traceability on 2-connected line graphs [J].Applied Mathematics and Computation,2018,321:1339-1351.
[19]BONOMO F, DURÁN G, SAFE M D,et al.Clique-perfectness of complements of line graphs [J].Electronic Notes in Discrete Mathematics,2011,37:327-332.
[20]CHENG B L,FAN J X,JIA X H,et al.Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes [J].Journal of Parallel and Distributed Computing,2013,73(5):641-652.
[21]YU X,WU,WANG G J.A Parallel Routing Algorithm forCrossed Cube Networks[J].Computer Engineering,2007,33(3):12-14.
[22]EFE K.The crossed cube architecture for parallel computation [J].IEEE Transactions on Parallel and Distributed Systems,1992,3(5):513-524.
[23]EFE K.A variation on the hypercube with lower diameter [J].IEEE Transactions on Computers,1991,40(11):1312-1316.
[24]CHARTRAND G,STEWART M J.The connectivity of line-graphs [J].Mathematische Annalen,1969,182(3):170-174.
[25]CHENG B L,FAN J X,LI X Y,et al.Towards the Independent Spanning Trees in the Line Graphs of Interconnection Networks[C]//International Conference on Algorithms & Architectures for Parallel Processing.Cham,:Springer,2018:342-354.
[1] YI Yi, FAN Jian-xi, WANG Yan, LIU Zhao, DONG Hui. Fault-tolerant Routing Algorithm in BCube Under 2-restricted Connectivity [J]. Computer Science, 2021, 48(6): 253-260.
[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] SHI Hai-zhong and SHI Yue. M-layers Binary Graph Model for Interconnection Networks [J]. Computer Science, 2017, 44(Z11): 308-311.
[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] 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] YIN Dong,MU De-jun,DAI Guan-zhong. Research on Server Centric Data Center Network Design [J]. Computer Science, 2012, 39(3): 110-112.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.