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

数据中心网络设计的新趋势是在互连网络的顶点和边上分别部署交换机和双端口服务器,其逻辑图可以抽象为复合图。顶点独立生成树(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。另外,基于增广立方体的数据中心网络上的模拟实验也从另一个方面证明了上述结论的正确性。