Gaussian Networks For Scalable Distributed Systems
Wynne Hsu · The Computer Journal · 1996
The interconnection topology of a network plays a key role in determining the performance and cost of routing messages in the system. Presently, there are many known results about individual network topologies and their applications. However, relatively few results exist about the relations among these topologies; for instance, it is rather difficult to relate quantitatively the cost of interconnection with the routing efficiency. As such, the theory is incomplete for assisting a designer to choose a suitable topology for a required routing performance under a given cost of interconnection. Here, by extending the popular hypercube, a family of parameterized network topologies called Gaussian Cubes (GCs) is presented. By varying the parameter that controls the interconnection density, the routing performance of a GC can be scaled according to the traffic loads without changing the routing algorithm. It is demonstrated that these new networks can approximate the concurrent offered by hypercubes while lowering the cost of interconnection; common communication primitives such as Unicast, Multicast and Broadcast can all be supported efficiently on GCs. Therefore, the new network topologies can be applied to distributed systems with scalable messaging performance. Because GCs are also subgraphs of the conventional hypercubes, our results may also be useful to fault-tolerant computing based on hypercubes.