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

Construction Algorithm of Completely Independent Spanning Tree in Dragonfly Network

作　　者：卞庆荣 程宝雷[1,2] 樊建席 潘志勇[1,2] BIAN Qing-rong;CHENG Bao-lei;FAN Jian-xi;PAN Zhi-yong(School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China;Jiangsu Provincial Key Laboratory for Computer Information Processing Technology,Soochow University,Suzhou,Jiangsu 215006,China)

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006 [2]苏州大学江苏省计算机信息处理技术重点实验室,江苏苏州215006

出　　处：《计算机科学》2022年第11期284-292,共9页Computer Science

基　　金：国家自然科学基金(62172291,U1905211);江苏高校优势学科建设工程;江苏省教育厅未来网络科研基金(FNSRFP-2021-YB-39)。

摘　　要：蜻蜓网络(Dragonfly network)是由Kim等提出的一种适用于高性能计算系统的拓扑结构。在蜻蜓网络中,网络被组织成两级架构,计算节点与交换机连接,交换机被分为成多个组。在每一组内部的每个交换机之间互相有一条边相连,任意两组之间有一条边相连接。完全独立生成树在信息的可靠传输、信息的并行传输和安全分发以及并行故障服务器诊断算法中具有非常重要的应用。在实际应用中,随着网络规模的不断增大,信息传输的效率以及安全性等要求越来越高。因此,研究网络的完全独立生成树具有重要意义。目前,有许多关于网络中完全独立生成树的研究,但是缺乏蜻蜓网络上的完全独立生成树的研究成果。文中提出了蜻蜓网络全局链路分别以相对链接、绝对链接以及循环链接下的完全独立生成树划分的构造算法,并在此划分的基础上给出了完全独立生成树边集合的构造算法,并对以上算法的正确性进行了证明。最后分析了算法的时间复杂度。Dragonfly network,proposed by Kim et al.,is a topology for high-performance computer systems.In dragonfly network,compute nodes are attached to switches,the switches are organized into groups,and the network is organized as a two-level clique.There is a link between any two nodes in a group,and there is a global link between different groups.Completely independent spanning trees(CISTs)play important roles in reliable information transmission,parallel transmission and safe distribution of information.In practical application,with the continuous increase of network scale,the requirements for information transmission efficiency and security are becoming higher and higher.Therefore,it is meaningful to study the construction of completely independent spanning trees in dragonfly network.At present,there are many results on completely independent spanning trees in networks,but completely independent spanning trees in dragonfly network have not been studied.In this paper,construction algorithm for the global link of dragonfly network is proposed,which is divided into completely independent spanning tree under re-lative link,absolute link and circulant link.Based on this division,a construction algorithm for the edge set of completely independent spanning tree is given,and the correctness of the above algorithms is proved.Finally,the time complexity of these algorithms is analyzed.

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

分 类 号：TP393.0[自动化与计算机技术—计算机应用技术]