数据中心网络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上的任意一个顶点。     

一类数据中心网络中顶点独立生成树的一种通用构造方法

数据中心网络设计的新趋势是在互连网络的顶点和边上分别部署交换机和双端口服务器,其逻辑图可以抽象为复合图.顶点独立生成树(node-independent spanning trees,NIST)是数据中心网络中的一种重要结构,可用于设计数据中心网络中的可靠通信协议,容错广播和安全消息分发,IP快速重路由等.给定一个复合图G(Kn),首先表明,如果图G的直径为d,则复合图G(Kn)的直径为2d或2d+1.假设n-正则、n-顶点连通的互连网络G中存在以任一顶点为根的n棵NIST,通过提出一种时间复杂度O(N)的高效算法(其中N是顶点数),给出了G(Kn)中一种构造n棵NIST的通用方法.对复合图Qn(Kn)的顶点分析表明,NIST的最大高度仅为其直径加3.另外,基于增广立方体的数据中心网络上的模拟实验也从另一个方面证明了上述结论的正确性.     

蜻蜓网络上完全独立生成树的构造算法

蜻蜓网络(Dragonfly network)是由Kim等提出的一种适用于高性能计算系统的拓扑结构。在蜻蜓网络中,网络被组织成两级架构,计算节点与交换机连接,交换机被分为成多个组。在每一组内部的每个交换机之间互相有一条边相连,任意两组之间有一条边相连接。完全独立生成树在信息的可靠传输、信息的并行传输和安全分发以及并行故障服务器诊断算法中具有非常重要的应用。在实际应用中,随着网络规模的不断增大,信息传输的效率以及安全性等要求越来越高。因此,研究网络的完全独立生成树具有重要意义。目前,有许多关于网络中完全独立生成树的研究,但是缺乏蜻蜓网络上的完全独立生成树的研究成果。文中提出了蜻蜓网络全局链路分别以相对链接、绝对链接以及循环链接下的完全独立生成树划分的构造算法,并在此划分的基础上给出了完全独立生成树边集合的构造算法,并对以上算法的正确性进行了证明。最后分析了算法的时间复杂度。