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

详细信息	查看全文 | 推荐本文 |

• 作者：Gaocai Wang^a ; ^{wanggaocai@yahoo.com.cn} ; Guojun Wang^b ; Zhiguang Shan^c
• 关键词：Fault tolerance ; Mesh network ; k-submesh ; Node failure probability ; Connectivity probability
• 刊名：Information Processing Letters
• 出版年：2012
• 期刊代码：61_00200190
• 类别：cp
• 出版时间：31 May, 2012
• 卷：112
• 期：10
• 页码：396-401
• 文件大小：336 K

摘要

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鈥?00 nodes (e.g., ) and require a network connectivity probability , we only need to bound the uniform node failure probability by . On the other hand, for the same size network , the mesh network connectivity probability can maintain even the network runs one million seconds uninterruptedly under exponential distribution node failure probability with failure rate level.