科研之友
微信
新浪微博
Facebook
分享链接
摘要
作为云计算技术的基础，数据中心网络的通信性能成为了近年来的研究热点。独立生成树(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为交叉立方体CQn上的任意一个顶点。
- 单位
