Probabilistic analysis on fault tolerance of 3-Dimensional mesh networks

Abstract

The probability model is used to analyze the fault tolerance of mesh. To simplify its analysis, it is assumed that the failure probability of each node is independent. A 3-D mesh is partitioned into smaller submeshes, and then the probability with which each submesh satisfies the defined condition is computed. If each submesh satisfies the condition, then the whole mesh is connected. Consequently, the probability that a 3-D mesh is connected is computed assuming each node has a failure probability. Mathematical methods are used to derive a relationship between network node failure probability and network connectivity probability. The calculated results show that the 3-D mesh networks can remain connected with very high probability in practice. It is formally proved that when the network node failure probability is bounded by 0.45%, the 3-D mesh networks of more than three hundred thousand nodes remain connected with probability larger than 99%. The theoretical results show that the method is a powerful technique to calculate the lower bound of the connectivity probability of mesh networks.

Keywords

3-D mesh networks / k-submesh / connectivity / probability analysis