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

References

[1] Sigurd L, Lillevik. The Touchstone 30 Gigaflop DELTA Prototype [A]. IEEE Proceedings of the Sixth Distributed Memory Computing Conference[C]. Portland, Oregon, 1991. 671–677.

[2] LenosjiD, LaudonJ, GharachorlooK, et al.. The Stanford DASH Multiprocessor [J]. IEEE Computer, 1992, 25(3): 63-79

[3] Agarwal A, Bianchini R, Chaiken D, et al. The MIT Alewife machine: Architecture and performance [A]. IEEE/ACM Proceedings of the 22nd Annual International Symposium on Computer Architecture [C]. Ligure, Italy, 1995. 2–13.

[4] Cray T3D System Architecture Overview (HR-04033) [R]. Cray Research Inc, 1994.

[5] Alverson R, Callahan D, Cummings D, et al. The Tera Computer System [A]. Proceedings of the—1990 International Conference on Supercomputing[C]. Amsterdan, 1990.

[6] AllenF, AlmasiG, AndreoniW, et al.. Blue Gene: a vision for protein Science using a petaflop supercomputer [J]. IBM Systems J, 2001, 40: 310-337

[7] BoppanaR V, ChalasaniS. Fault-tolerant wormhole routing algorithms for mesh networks [J]. IEEE Transactions on Computer, 1995, 44(7): 848-864

[8] TsengY C, KpandaD, LaiT H. A trip-based multicasting model in wormhole-routed networks with virtual channels [J]. IEEE Trans Parallel and Distributed Systems, 1996, 7(2): 138-150

[9] AlmohammandB F A, BoseB. Fault-tolerant communication algorithms in toroidal networks [J]. IEEE Trans Parallel and Distributed Systems, 1999, 10(10): 976-983

[10] GaughaP T, DaoB V, YalamanchiliS, et al.. Distributed, deadlock-free routing in faulty, pipelined, direct interconnection networks [J]. IEEE Transactions on Computers, 1996, 45(6): 651-665

[11] ChenC L, ChiuG M. A fault-tolerant routing scheme for meshes with nonconvex faults [J]. IEEE Trans Parallel and Distributed Systems, 2001, 12(5): 467-475