Upper bounds on the connection probability for 2-D meshes and tori

Mesh is an important and popular interconnection network topology for large parallel computer systems. A mesh can be divided into submeshes to obtain the upper bounds on the connection probability for the mesh. Combinatorial techniques are used to get closer upper bounds on the connection probability for 2-D meshes compared with the existing upper bounds we have known. Simulation results of meshes of various sizes show that our upper bounds are close to the exact connection probability. The combinatorial methods and tools used in this paper can be used to study the connection probabilities for other networks.

► We give a method to get upper bounds on the connection probability for meshes/tori.
► A mesh is divided into submeshes to reduce the complexity of the analysis.
► Combinatorial techniques are used, with single-node disconnections mainly concerned.
► Our new upper bounds for meshes are much tighter than the known ones.
► Simulation results show that our upper bounds are close to the exact probabilities.