Mesh Muddling Madness¹

The theory of six degrees of separation is the idea that any living person is only six introductions away. In other words, the graph with nodes being people and edges being their friendships has a very low maximum-shortest-path-length (or diameter) compared to the number of nodes. Networks such as these are known as 'small-world networks' and this article explores what properties a super-computer wired up in this manner might have.

Making Small-World Networks

Watts and Strogatz proposed an algorithm for generating random small-world networks. The algorithm starts with a ring network of $n$ nodes where each successive node is connected to it's $k$ nearest neighbours. In the example below, we have a ring network with $n=12$ nodes and $k=2$.

To turn this network into a small-world network, a small percentage of the edges are randomly re-wired². In the example below, edges are rewired with a probability $p=0.2$.

The modified graph now exhibits various small-world properties, notably a reduced average path-length.

Making Small-World Super-Computers

For certain computing tasks reducing the average path-length in the network may be desirable as it would potentially reduce the latency between arbitrary pairs of nodes in the system. Super-computer interconnection systems tend not to use ring networks but instead a $k$-ary $n$-cube topologies which are a generalisation of the ring network³. Extending the Watts Strogatz model to this general case is trivial: simply start with a $k$-ary $n$-cube and then randomly rewire some of the edges.

The network above is a 2D torus (a 6-ary 2-cube), in this network the average path length (in terms of hops) is $\frac{nk}{4}$. This is because a packet travels (on average, for uniform random traffic) $\frac{1}{4}$ of the way around each of the $n$, $k$-node-long dimensions. In this case, that means the average path length is $\frac{2 \times 6}{4} = 3$.

If the network shown above has been rewired with $p=0.1$ and has an average path length of 2.77 hops. With the same number of wires it can be seen that the average minimum hop count has reduced. As the amount of rewiring increases returns diminish. This is plotted bellow for 10-runs of the above algorithm on 6-ary 2-cubes. The error bars show the standard deviation.

With larger networks the effect becomes more significant. Below shows the results for a 40-ary 2-cube⁴. Here the average path length drops by almost 50% when just 1% of edges are rewired.

Practical Wiring

Unfortunately, adding wires at random like we have done in the previous examples could be problematic for real-world systems. It isn't practical to have wires above a certain length and when laid out naively as shown above you can see that long wires crossing the whole system appear.

Folding Long Wires

In order to keep wire-lengths manageable, the whole network should be folded in half. For example, this ring network:

Can be folded in half to yield this arrangement containing no wires which cross the whole system:

Or, drawn flattened:

This process can be generalised to minimise the maximum wire-length required for 2-cubes as well:

Keeping Randomly-Created Wires Short

Of course, things start to get interesting when we start rewiring the edges as long wires can start to reappear. For example, here is the same network with rewiring of edges with $p=0.1$:

As you can see there are several long wires including one that crosses nearly the longest jump in the system (bottom left to nearly-top right).

In an attempt to combat this problem we can change the rewiring algorithm to only create new links whose links are relatively short.

The rewiring above constrains the maximum wire to be 3 units long (where a unit is the spacing between each node in a given dimension). We still see that the maximum path length still drops, this time to 2.73, but now there are no long wires.

To test the effects of limiting wire lengths when re-wiring, a parameter sweep was carried out for a 40-ary 2-cube both with and without folding:

For very short wire length limits, folding provides improved average path-lengths, presumably because it is better-able to insert links to nodes topologically far away using only short wires. This is due to the fact that each folding moves the furthest nodes much closer at the expense of slightly increasing the wire length between topologically close nodes.

The other interesting effect visible in the graph is that allowing wires longer than about 25 units has no significant effect on the average path length. I hypothesise that there is some small benefit hidden by noise) which eventually disappears when wires reach 40 units long. This is due to the fact that wires of a maximum length of 40 allow packets to jump beyond the length of the maximum shortest-path possible in the system which would never be useful: a wire which travels the equivalent distance of $h$ hops can be completed in $h \mod \frac{kn}{2}$ hops.

Remaining Work

Much work remains to be done in this analysis. In particular:

• A formula which calculates the expected average path length in the case of rewiring and wire-length limited rewiring.
• An analysis of the use of edge-adding variation on the Watts Strogatz model
• An analysis of how this effects the bisection-bandwidth of the network
• An analysis of routing challenges