Communication in a hypercube is based
on the binary representation of node IDs. The nodes are numbered
so that two nodes are adjacent if and only if the binary
representations of their IDs differ by one bit. For example,
nodes 0110 and 0100 are immediate neighbors but 0110 and 0101 are
not. An easy way to label nodes is to assign node IDs as the cube
is constructed. When you copy an (**n-1**)-dimensional cube, make
sure the corresponding nodes in the two copies have the same IDs.
Then extend all the IDs by one bit. Append a 0 to the IDs of
nodes in the original cube, and append a 1 to the IDs of nodes in
the copy. As an example the nodes in the 1D and 2D cubes in
Figure 11
are labeled according to this scheme; the labeling of
the 3D and 4D cubes is left for an exercise.

Node IDs are the
basis for a simple algorithm for routing information in a
hypercube. An **n**-dimensional cube will have **n**-bit
node IDs.
Sending a message from node A to node B can be done in **n** cycles,
where on each cycle a node will either hold a message or forward
it along one of its links. On cycle **i** the node that currently
holds the message will compare bit **i** of its own ID with bit **i** of
the destination ID. If the bits match, the node holds the
message. If they don't match, it forwards the message along
dimension **i**, where dimension **i** is the dimension that was added in
the step of the construction
of the cube (i.e. it is the same ``direction'' at all nodes).
As an example, the path from node 2 to
node 7 in a 4D cube is marked with a heavy gray line in
Figure 11.