Appendix 6 - Network topology design

Summary

A network can be designed using various topologies. Many interconnection networks have been proposed by the research community; some have been prototyped but few have progressed to become commercial products. A network may be static or dynamic. The topologies can be divided into two categories: (i) regular and (ii) irregular. The regular topologies follow a well-defined function to interconnect nodes. The regularity, symmetry, and most often the strong connectivity of the regular network topologies make them suitable for general purpose interconnection structures where the characteristics of the traffic originating from all nodes are identical and destinations are uniformly distributed over the set of nodes. Thus, the link traffic is also uniformly distributed. The irregular topologies are optimized based on the traffic demands. If there is a high traffic flow between two nodes, then they may be connected using a direct link. If a direct link is not feasible, then an alternative is to provide a short path between the two nodes. Such designs are much more involved and need special attention.

We will first discuss regular topologies and then get into the design of irregular topologies. We will also discuss some specific regular topologies, such as a binary cube and its variations, in greater detail.

Regular topologies

There are several regular topologies that have been proposed by various researchers in the literature. The most important among these are complete connected graphs, star, tree, ring, multi-ring, mesh, and hypercube topologies. One of the desirable properties of a structure is to be able to accommodate or embed an arbitrary permutation.