Families of communication architectures for data centers and parallel processing derived by switching network dilation

Network dilation is a way of o ering system families, at a range of sizes and computational powers, which share an underlying communication architecture and routing algorithm. We consider indirect networks that connect processing nodes via intermediate switch nodes. In the simplest such indirect networks, there is a switching network of some regular topology, where each switch is connected to d other switches and to exactly one processing node. A variant, which we adopt here because it is more robust in the sense of not losing any processing capability to single-switch failures, is the use of 2-port processing nodes that connect to two neighboring switches. This alternate architecture also has the advantage of increasing the number of processing nodes from n to (d=2)n with a factorof- 2 increase in internode distances. A k-dilated version of the latter architecture replaces each processing node with a path network (linear array) of length k, thus growing the network size to k(d=2)n and also further increasing internode distances. In this paper, we study topological and performance attributes of such dilated network architectures, proving general theorems about worst-case and average internode distances and deriving the routing algorithm from that of the underlying switch network.