In view of their applicability to parallel and distributed computer systems, interconnection networks have been studied intensively by mathematicians, computer scientists, and computer designers. In this paper, we propose an asymptotically optimal method for connecting a set of nodes into a perfect difference network (PDN) with diameter 2, so that any node is reachable from any other node in one or two hops. The PDN interconnection scheme, which is based on the mathematical notion of perfect difference sets, is optimal in the sense that it can accommodate an asymptotically maximal number of nodes with smallest possible node degree under the constraint of the network diameter being 2. We present the network architecture in its basic and bipartite forms and show how the related multidimensional PDNs can be derived. We derive the exact average internode distance and tight upper and lower bounds for the bisection width of a PDN. We conclude that PDNs and their derivatives constitute worthy additions to the repertoire of network designers and may offer additional design points that can be exploited by current and emerging technologies, including wireless and optical interconnects. Performance, algorithmic, and robustness attributes of PDNs are analyzed in a companion paper.

Perfect difference networks (PDNs) that are based on the mathematical notion of perfect difference sets have been shown to comprise an asymptotically optimal method for connecting a number of nodes into a network with diameter 2. Justifications for, and mathematical underpinning of, PDNs appear in a companion paper. In this paper, we compare PDNs and some of their derivatives to interconnection networks with similar cost/performance, including certain generalized hypercubes and their hierarchical variants. Additionally, we discuss point-to-point and collective communication algorithms and derive a general emulation result that relates the performance of PDNs to that of complete networks as ideal benchmarks. We show that PDNs are quite robust, both with regard to node and link failures that can be tolerated and in terms of blandness (not having weak spots). In particular, we prove that the fault diameter of PDNs is no greater than 4. Finally, we study the complexity and scalability aspects of these networks, concluding that PDNs and their derivatives allow the construction of very low diameter networks close to any arbitrary desired size and that, in many respects, PDNs offer optimal performance and fault tolerance relative to their complexity or implementation cost.