摘要
1引言
在众多的并行计算机系统的互联网络模型中,Mesh网络是研究者们研究得较早的,并且现在仍然是最为重要的和最有吸引力的网络模型之一.
Mesh network is very popualr and important topological structure in parallel computing. In this paper, we focus on the fault tolerance of 3-dimensional mesh. We use the probability model to analyze the fault tolerance of mesh. To simplify our analysis, we assume the failure probability of each node is independent. We partition a 3-dimensional mesh into smaller submeshes and compute the probability with which each submesh satisfies the condition we define. If each submesh satisfies the condition, then the whole mesh is connected. We then compute the probability that a 3-dimensional mesh is connected assuming each node has a failure probability p. We use mathematical methods to derive a relationship between network node failure probability and network connectivity probability. Our simulations show that 3-dimensional mesh networks can remain connected with very high probability in practice. For example, the paper formally proves that when the network node failure probability is bounded by 0. 05%, 3-dimensional mesh network of more than two hundred thousand nodes remain connected with probability larger than 99%. Theoretical and experimental results show that our method is powderful technique to calculate the lower bound of the connectivity probability of mesh network.
出处
《计算机科学》
CSCD
北大核心
2003年第11期77-79,96,共4页
Computer Science
基金
国家自然科学基金(90104028)
长江学者奖励计划资助项目
关键词
容错性
MESH网络
概率分析
3-dimensional mesh networks, k-submesh, Connectivity, Probabilistic analysis
