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

作     者：潘志勇 程宝雷 樊建席 卞庆荣 PAN Zhi-yong;CHENG Bao-lei;FAN Jian-xi;BIAN Qing-rong

作者机构：苏州大学计算机科学与技术学院江苏苏州215006 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2022年第49卷第7期

页      面：287-296页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家自然科学基金(U1905211,62172291,61572337) 江苏省高等学校自然科学重大项目(18KJA520009) 江苏高校优势学科建设工程资助项目。 

主　　题：数据中心网络 独立生成树 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)上的任意一个顶点。