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

摘要：

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

关键词：蜻蜓网络、拓扑、完全独立生成树、算法

所属期刊栏目：49

分类号：TP393.0(计算技术、计算机技术)

资助基金：国家自然科学基金;国家自然科学基金;江苏高校优势学科建设工程;江苏省教育厅未来网络科研基金

在线出版日期：2022-11-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：284-292