Mesh网络是迄今为止最为重要和最具吸引力的并行计算机系统网络拓扑结构之一。本文提出全新的基于概率模型研究Mesh网络的容错性问题的理论,提出了k-Mesh子网结构的方法,本文基于k-Mesh子网结构研究了二维和三维Mesh网络的容错性,并基于k-Mesh子网结构提出了高效的二维和三维Mesh网络单播和广播容错路由算法,从概率的角度分析了各种算法的有效性。 本文首先在每个结点具有独立的出错概率的情形下研究Mesh网络的容错性,提出基于k-Mesh子网结构的概念:即k-Mesh子网连通性。证明了当网络结点出错概率给定时,随着网络规模的增加,Mesh网络的连通概率将任意地趋向无穷小。因此,对于以Mesh网络为拓扑结构的并行计算机系统的研究者和制造商提出一个实际而重要的课题:当网络连通概率和网络规模给定时,网络结点的出错概率的下界应控制在多大的范围之内。本文严格推导出Mesh网络的连通概率的一个下界。研究结果表明实际规模的以Mesh网络为拓扑结构的并行计算机系统是能容许相当多的出错结点的,因此也是相当可靠的。研究结果也表明了三维Mesh网络有优于其它流行的网络拓扑结构的优势。与规模相当的二维Mesh网络相比,三维Mesh网络在保持较高的连通概率的同时能容许更多的网络结点出错。而与规模相当的超立方体网络相比,三维Mesh网络在保持较高的连通概率的同时享有更低的结点度。 本文基于k-Mesh子网结构提出了基于局部信息的和分布式的二维和三维Mesh网络单播容错路由算法。因为容错路由算法是基于k-Mesh子网结构设计的,所以本文从概率的角度研究了单播容错路由算法的有效性,推导出容错路由算法的成功概率。本文运用严格的数学推理,证明了二维Mesh网络结点出错概率只要控制在1.8%以内,则对于多达250000个结点的二维Mesh网络,路由算法具有99%的概率确保找到正确结点组成的路径。当结点出错概率不大于2.5%时,即使对于规模达到373248个结点的三维Mesh网络,路由算法仍具有99%的成功概率。路由算法的时间复杂性是线性的,模拟结果表明路由算法所构造的路由路径长度非常接近于两结点之间的最优路径长度。