Mesh网络连通性的概率分析

Mesh网络是大型多处理器并行计算机系统中极为重要的拓扑结构．本文提出了一种计算Mesh网络连通概率的新方法，该方法在给定网络规模和结点出错概率时，计算出Mesh网络连通概率的一个下界，或者对于要求的Mesh网络连通概率，该方法能计算出对结点出错概率的要求．例如，本文运用严格数学推导证明了当网络结点出错概率控制在0．12％以下，则多达四万个结点的Mesh网络仍可保持高达99％的连通概率．理论计算和实验结果表明，该方法在计算Mesh网络连通概率下界时是一种强有力的技术．

Probabilistic Analysis of Connectivity in Mesh Networks

Mesh networks are a kind of very important network topologies in massively multiprocessor parallel systems. The paper proposes a novel approach for calculating the probabilistic connectivity of mesh networks, which uses thorough mathematical methods to derive the relationship between the node failure probability and the probabilistic connectivity in the networks. The results show that practical mesh networks can remain connected with very high probability. For example, the paper formally proves that when the networks' node failure probability is bounded by 0.12%, the mesh networks with forty thousand nodes remain connected with probability larger than 99%. Theoretical and experimental results show that our method is a powerful technique for calculating the lower bound of the probabilistic connectivity in mesh networks.