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

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.

Keywords

• data center networks|independent spanning trees|bcdc|crossed cube|line graph