Application of Perfect Difference Sets to the Design of Efficient and Robust Interconnection Networks

摘要

In this paper, we focus on deriving low-diameter networks, beginning with D = 2, the next best value to that of the complete network, and proceeding to somewhat larger (constant) values leading to more economical networks. We show that perfect difference networks (PDNs), which are based on the mathematical notion of perfect difference sets, offer a diameter of 2 in an asymptotically optimal manner. In other words, PDNs allow O(d~2) nodes when nodes are of degree d, or, equivalently, have a node degree that grows as the square-root of the network size. The symmetry and rich connectivity of PDNs lead to balanced communication traffic and good fault tolerance. Multidimensional PDNs offer a tradeoff between cost and performance in the sense that for any constant number q of dimensions, a q-dimensional PDN has diameter D = 2q and node degree that grows as the (2q)th root of n.