When a node is not connected to every other
node, messages may have to go through intervening nodes to reach
their final destination. The * diameter* of a network is the longest
path between any two nodes. Again the ring and fully connected
network show two extremes. A ring of **n** nodes has diameter
, but a
fully connected network has a fixed diameter (1) no matter how
many nodes there are.

Figure 11: Hypercubes.

The diameter of a ring grows as more nodes
are added, but the diameter of a fully connected network remains
the same. On the other hand, a ring can expand indefinitely
without changing the degree, but each time a new node is added to
a fully connected network a link has to be added to each existing
node. * Scalability* refers to the increase in the complexity of
communication as more nodes are added. In a highly scalable
topology more nodes can be added without severely increasing the
amount of logic required to implement the topology and without
increasing the diameter.

A scalable topology that has been used
in several parallel processors is the hypercube, shown in
Figure 11.
A line connecting two nodes defines a 1-dimensional ``cube.'' A
square with four nodes is a 2-dimensional cube, and a 3D cube has
eight nodes. This pattern reveals a rule for constructing
an **n**-dimensional cube: begin with an (**n-1**)-dimensional
cube, make an
identical copy, and add links from each node in the original to
the corresponding node in the copy. Doubling the number of nodes
in a hypercube increases the degree by only 1 link per node, and
likewise increases the diameter by only 1 path. It is left as an
exercise to prove that an **n**-dimensional hypercube has
nodes,
diameter **n**, and degree **n**.