Fault tolerance analysis of mesh networks with uniform versus nonuniform node failure probability

Mesh networks have been applied to build large scale multicomputer systems and Network-on-Chips (NoCs). Mesh networks perform poorly in tolerating faults in the view of worst-case analysis, so it is practically important for multicomputer systems and NoCs manufactures to determine the lower bound for the mesh network connectivity probability when the node failure probability and the network size are given. In this paper, we study the topic based on k-submesh model under two fault models: Each node has uniform or nonuniform failure probability. We develop a novel technique to formally derive lower bound on the connectivity probability for mesh networks. Our study shows that mesh networks of practical size can tolerate a large number of faulty nodes and maintain higher connectivity probability, thus are reliable and trustworthy enough for multicomputer systems and NoCs. For example, suppose we are building a mesh network of 40 000 nodes (e.g., M-200x200) and require a network connectivity probability 99%, we only need to bound the uniform node failure probability by 0.25%. On the other hand, for the same size network M-200 x 200, the mesh network connectivity probability can maintain 95.88% even the network runs one million seconds uninterruptedly under exponential distribution node failure probability with failure rate 10(-9) level. (C) 2012 Elsevier B.V. All rights reserved.