Abstract
This paper presents the Full-Cube, a versatile cube network built by merging the Cube and Complementary-Cube (Co-Cube) networks. Compared to the Hypercube, the Full-Cube has double the number of links while maintaining the same number of nodes. Some of the properties of a 2
n
-node Full-Cube are: an [
n
2
] diameter,
O(
n2
n
) link cost, considerably more redundant paths connecting any two nodes than the Hypercube leading to a higher tolerance of link faults, and a significantly larger number of partitions into subcubes. Furthermore, for practical hypercube sizes, the average internode distance of the cube, which directly affects the message communication time, is shown to be reduced by approximately 20–35% in the Full-Cube. Like the Hypercube, the Full-Cube offers extendability and a fixed node complexity, and simple distributed one-to-one and multicast routing algorithms. We discuss the properties of the Full-Cube and present distributed routing algorithms for one-to-one and multicast communication.