Characterizing and Visualizing Contours in Regular 3D Mesh Topologies

A systematic approach for realizing three dimensional mesh topologies and the characterization of the union of all shortest paths between a pair of nodes will enable new applications of such topologies in a variety of systems. Current work focuses largely on two dimensional mesh topologies and there have been a few recent reports about the importance of three dimensional topologies to design better systems. This thesis presents (a) embedding functions that yield regular three dimensional mesh topologies, (b) results and observations about the union of all shortest paths between a pair of nodes, and (c) a characterization of when one of the shortest paths gets loaded even when all the available paths are being used uniformly. To enable the use of such topologies in future applications, this thesis also describes a visualization tool and a simulation tool that was designed and implemented.

The embedding functions presented here are all derived from a tessellation of a given volume with the well-known platonic solids, namely tetrahedron, cube, octahedron, and dodecahedron. As in other mesh topologies, each node has a fixed set of neighbors. Because the topologies reported here are all regular, every node has the same number of neighbors; these topologies are represented as Γ_q, where q is the number of neighbors for each node. This thesis presents embedding functions for Γ₄, Γ₆, Γ₈, Γ₁₂. The regularity of these mesh topologies enabled a characterization of the structure of shortest paths.

A contour is the union of all the shortest paths between a pair of nodes. This thesis presents results that characterize the structure of contours in Γ₆ mesh topologies. Observations for the structure of contours in Γ₈ and Γ₁₂ are also presented, without proofs. All these results and observations were validated using the visualization tool. Even when a contour has multiple shortest paths, it is known from prior results in the literature for two dimensional mesh topologies, that when these paths are used in a uniform manner, exactly one of the paths will get loaded. This thesis presents observations that identify the paths in three dimensional mesh topologies that will get loaded. These observations are validated using the simulation tool.

Several interesting problems remain for future investigations. For example, formal characterization of contours in Γ₄, Γ₈ and Γ₁₂. can be explored. Among these, Γ₄ appears to be most challenging. Similarly, formal proofs for loading in three dimensional contours can also be explored. Such results have important applications in emerging technology areas such as multi-core CPUs and cyber-physical systems.