数据中心网络BCDC上的顶点独立生成树构造算法

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

作为云计算技术的基础,数据中心网络的通信性能成为了近年来的研究热点。独立生成树(Independent Spanning Trees,ISTs)作为数据中心网络中常见的基础结构,因其在可靠通信、容错广播以及安全分发方面的应用受到了研究者的广泛关注,在诸多特殊的网络上都取得了显著的成果。但是,学者们对在线图中独立生成树的研究却很少。BCDC是由Wang等于2018年提出的一个新的以服务器为中心的数据中心网络,其逻辑图是交叉立方体的线图且为2n-2正则图。文中给出了BCDC上独立生成树的构造算法,首先利用一种并行算法在交叉立方体中构造出2n-2棵树,然后将这些树按照一定规则连接并通过特定的转换方法将其转变为BCDC中2n-2棵相互独立的树,最后将BCDC中的剩余顶点通过一个时间复杂度为O(N)(其中N表示BCDC的顶点数)的高效算法挂接到树上,从而构造出BCDC上的以顶点[r,N(r,2)]为根的2n-2棵独立生成树,其中顶点r为交叉立方体CQ_(n)上的任意一个顶点。

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 CQ_(n).