The Josephus cube: A novel interconnection network

We present a novel interconnection topology, the Josephus Cube, which suppo rts a simple routing strategy that is minimal, deadlock- and livelock-free. The topology can optimally embed linear arrays (LAs), rings, and complete binary trees of arbitrary size, as well as 2(p) x q meshes. It is also a su pergraph of the n-cube and several of its variants and supports a degree of fault tolerance. Finally, the topology can systematically interconnect an arbitrary number of nodes and its scalability, diameter and communications performance compare favourably with those of the n-cube and its variants. ( C) 2000 Elsevier Science B.V. All rights reserved.