Connectivity and constructive algorithms of disjoint paths in dragonfly networks

Dragonfly networks have been widely used in the current High Performance Computing (HPC) computers due to lower global network diameter and other advantages of communication performance such as modularity and cost-effectiveness. The original definition of the dragonfly network was very loose on account of its uncertain and diversified global link arrangements. In this paper, we study the logical structure of the dragonfly network which can be treated as a compound graph of complete graphs. Firstly, we give the general definition of the dragonfly network, named DF(n, h, g), and the specific definition of the dragonfly network under the relative global link arrangement, named D(n, h). Then, we prove that the connectivity of D(n, h) is n - 1 + h. In the end, we propose an O(n) algorithm to give the disjoint path between any two distinct vertices in D(n, h) and analyze the maximum length of these disjoint paths which is no more than 7. (C) 2022 Elsevier B.V. All rights reserved.

Automated summary

In this paper, the logical structure of the dragonfly network is studied, and the general and specific definitions of the network are given. The connectivity of the network under specific definition is proven, and an algorithm to find disjoint paths is proposed.