%0 Journal Article
%T Probabilistic Analysis on Fault Tolerance of 3-Dimensional Mesh Networks<br>3-维Mesh网络容错性的概率分析研究
%A WANG Gao-Cai CHEN Jian-Er WANG Guo-Jun CHEN Song-Qiao
%A <br>王高才
%A 陈建二
%A 王国军
%A 陈松乔
%J 计算机科学
%D 2003
%I 
%X 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.
%K 3-dimensional mesh networks
%K k-submesh
%K Connectivity
%K Probabilistic analysis<br>容错性
%K Mesh网络
%K 概率分析
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=C83BF18628E4C4AA&yid=D43C4A19B2EE3C0A&vid=340AC2BF8E7AB4FD&iid=708DD6B15D2464E8&sid=E44E40A2398D4F2A&eid=9C65ADEB5990B252&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=14