Static Networks

In a static network the connectivity between nodes is defined by the presence of physical links, and this makes the choice of network topology heavily dependent on the expected pattern of communication. The topology of static networks can be characterised very simply in terms of geometric dimensionality. Thus, we can define zero, one, two, three and even n-dimensional networks.

0-Dimensional Networks

The 0-dimensional network is just a single node as shown in Figure 1 without any links to other nodes, and is shown here solely for the sake of completeness. It has a null routing function and no communication bandwidth.

1-Dimensional Networks

Chaining together a number of nodes with bi-directional links in a linear array produces, in effect, a bi-directional pipeline. Linking the ends of the pipeline produces a simple two-dimensional ring topology. In a ring structure the throughput, the average path length between any two nodes, and the cost, are all proportional to N.

2-Dimensional Networks

The topological `dual' of the ring is the star network, as shown in Figure 2, and this has similar performance characteristics to a shared bus structure. The number of parallel connections is 1, the maximum distance between nodes is 1 and the cost is proportional to N.

Tree-structured networks have some useful properties, especially when the problems being solved can be decomposed into hierarchies of activity. The most important property is that the distance between any two nodes is always less than 2(log₂(N+1) - 1).

The rectangular mesh network is another two-dimensional network, and is particularly suited to applications with highly localised inter-processor communications. It can be thought of as 2(n + m) inter-linked ring networks (where N = n.m), and can therefore be expressed in terms of shift permutations. The number of possible data movement operations that can take place in parallel is proportional to N; however, the maximum distance between any two nodes is √N.

3-Dimensional Networks

If a network topology cannot be depicted without arcs crossing, then it is of three or more dimensions. Examples of three-dimensional static network topologies (Figure 3) are the 3-cube and 3D mesh, the completely connected network, and some chordal rings.

Variations on the chordal ring can be devised that are equivalent to square mesh networks with shifted wrap-around at the boundaries. This can be verified by a simple pencil and paper exercise, and in fact formed the basis for the ILLIAC IV interconnection network [1]. Such partially connected chordal rings have a maximum distance between any two nodes of √(N - 1).

The 3-cube consists of eight nodes connected in a three-dimensional cube structure, and is actually a particular instance of a more general network topology known as the binary k-cube [2]