Joint Architecture Standard Overview Profile

# Complete and Incomplete Hypercubes

Domain(s)
Space
System(s)
Satellite
Profile(s)
CH, COMM, EXP, PS, RP, SMAC

An overall good performer, hypercubes are very reliable and offer good performance. Complete hypercubes have fixed size of 2^d (i.e., 4, 8, 16, 32, 64, etc, nodes) but an extension to this structure (incomplete hypercubes) allows for arbitrary size.

Hypercubes are constructed by beginning with two interconnected nodes (a 1-D hypercube) (see Figure). If more nodes are required, the structure is duplicated and interconnected by adding links between the original and the duplicated nodes.

Node degree grows quickly, making node complexity an issue for larger networks. Link count also exceeds other topologies for similar node counts.

Hypercubes offer excellent connectivity, especially at large node counts. This topology also has a high probability of withstanding random link/node failures.

Incomplete hypercubes relax the requirements of complete hypercubes to allow for structures that resemble hypercubes without the strict node count constraint. They generally perform about as well as complete hypercubes.

Reliability in incomplete hypercubes, however, is somewhat unpredictable. Incomplete hypercubes slightly larger than 2^d will introduce points of failure and decrease reliability, while hypercubes slightly smaller than 2^d will perform almost as reliably as a complete hypercube of size 2^d.

As an example, look at the figure below for an incomplete hypercube of N=9; if the link between nodes 1 and 9 were to fail, or if node 1 were to itself fail, then node 9 would be isolated from the rest of the network. Thus, the failure of one node causes two nodes to “fail” (or, the failure of a single link would additionally cause one node to “fail”). However, for networks closer in size to 2^d (such as the above case where N=7), the reliability of the hypercube is closer to that of a hypercube with d=3 (N=8).