2 D Meshes and 2 D Toroids

2-D meshes are one of the easiest topologies to visualize – nodes are connected in a “grid” fashion (see Figure). The simple layout also allows many problems to map easily to the structure of this network.

2-D meshes have unequal node degree. The node degree in the corners is 2, around the edges is 3, and in the center is 4. Also, traffic distribution is unequal among nodes. Nodes in the center of the mesh will carry the majority of traffic (leading to possible bottlenecks), and nodes around the edges will carry mostly their own traffic and little of others.

For reliability, 2-D meshes, in the general case, offer many redundant paths between nodes and can probably withstand a fair number of random failures. However, in the worst case, two link failures can isolate a corner node, as could two node failures.

2-D toroids improve on the design of the 2-D mesh by connecting left-edge nodes to right-edge nodes and top-edge nodes to bottom-edge nodes (geometrically, imagine a cylinder where the top is bent around and connected back to the bottom – this is a torus). The benefit to this modification is that each node now has a fixed degree of 4, and reliability and performance improves substantially.

2-D toroids can withstand a high number of general (random) link and/or node failures. In the worst case, four link failures or four node failures could cause the isolation of a valid working node. There are an abundant number of loops and alternate paths in the network to keep this topology connected.

Regarding performance, the addition of links between opposing edges significantly reduces the overall network diameter and average path length. The additional links also distribute the traffic evenly among all nodes, removing the bottlenecks that were present in the center of the 2-D mesh topology. However, the topology could use a few additional links (or rewired links) that jump a few nodes to help improve average path length.

• Advantages (2-D Mesh): Simple layout and easy to construct. Problems map well to this topology. Many redundant paths exist between most nodes.

• Disadvantages (2-D Mesh): Bottlenecks may exist in the center of the network. Corner, edge, and center nodes all have different degree. Bad worst-case failure rate. One of the easier topologies to bisect.

• Advantages (2-D Toroid): Reliable topology with reasonable performance. Fixed node degree of 4 for all nodes.

• Disadvantages (2-D Toroid): Link placement is not quite as efficient as some other topologies with the same number of links, and thus average path length and diameter are higher than other topologies with the same link count.