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. 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. 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 -dimensional hypercube has nodes, diameter , and degree . Communication in a hypercube is based on the binary representation of node IDs.