Construction Algorithm of Completely Independent Spanning Tree in Dragonfly Network

Abstract

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.

Keywords

• dragonfly network|topology|completely independent spanning tree|algorithm