Mesh网络连通性的概率分析  

Probabilistic Analysis of Connectivity in Mesh Networks

作　　者：王高才[1] 陈建二[1] 王国军[1] 

机构地区：[1]中南大学信息科学与工程学院

出　　处：《小型微型计算机系统》2004年第2期161-165,共5页Journal of Chinese Computer Systems

基　　金：国家杰出青年自然科学基金 (6992 82 0 1)资助;国家自然科学基金 (90 10 40 2 8)资助;长江学者奖励计划资助项目资助

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

关 键 词：MESH网络 k-Mesh子网 连通性 概率分析 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]