计算机应用研究

作者：钱煜,程宝雷,樊建席,卞庆荣,王懿丰,肖义胜,

单位：苏州大学a.计算机科学与技术学院;b.江苏省计算机信息处理技术重点实验室,江苏苏州215006；

关键词：数据中心网络,顶点独立生成树,复合图,直径,时间复杂度,

基金：国家自然科学基金资助项目(U1905211)；国家自然科学基金资助项目(61572337)；江苏省高等学校自然科学重大项目(18KJA520009)；中国博士后科学基金资助项目(2015M581858)；江苏省博士后科研经费计划项目(1501089B)；苏州大学创新创业本科培养计划资助项目(201910285025Z)；江苏高校优势学科建设工程资助项目；；

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

来源：2021年第7期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2021年第7期