Mesh网络连通性的概率分析

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

Mesh网络容错单播路由算法

基于k Mesh子网连通的概念,提出一个简单的Mesh网络容错单播路由算法.该容错单播路由算法是基于局部信息的,因为路由算法在路由的过程中,只需要知道其相邻结点的信息而无需知道其他结点出错的情况.对于给定的源结点和目的结点,当路由路径扩展到每一个k Mesh子网中时,该子网均可独立地完成算法的操作而无需考虑算法在其他k Mesh子网中的操作状态.所以,路由算法是高度分布式的.容错单播路由算法的时间复杂性是最优的.模拟结果表明,路由算法所构造的路由路径长度非常接近于2个结点之间的最优路径长度.

Mesh网络容错广播路由算法的概率分析

1引言 近年来，许多基于Mesh网络拓扑结构的商用和研究用的大规模并行计算机系统已经问世，如国外的Intel Paragon、Stanford DASH、 MIT Alewife、 Touchstone DELTA、 Symult2010、MasPar系列[5～8]，国内的曙光系列。

基于子网的三维Mesh网络容错广播路由算法

在并行计算机系统中,广播通信是极为重要的通信模式之一。该文基于k-Mesh子网(子立方体)连通的概念提出一个基于局部信息和分布式的三维Mesh网络容错广播路由算法。该算法利用邻结点的状态信息,动态地构建以单个k-Mesh子网为结点的广播树,该广播树能容忍相当多的结点出错。模拟结果表明广播路由算法的广播时间步接近最优的。该算法只要求结点知道它的邻结点的状态,而无需知道整个网络状态信息,也就是说,这些算法是基于局部信息的,因而具有很好的实际意义。

3-维Mesh网络容错性的概率分析研究

1引言 在众多的并行计算机系统的互联网络模型中,Mesh网络是研究者们研究得较早的,并且现在仍然是最为重要的和最有吸引力的网络模型之一.

三维Mesh网络容错路由算法及其概率分析

基于三维Mesh网络中k-Mesh子网连通的概念提出一个简单的基于局部信息和分布式的容错路由算法,并对其容错性进行概率分析.假设每个结点具有独立的出错概率,推导出路由算法成功返回由正确结点组成的路径的概率.结果表明即使三维Mesh网络上非常简单的路由算法也有相当高的成功概率.算法的时间复杂性是线性的,所构造的路由路径长度非常接近两点间的最优路径长度.另外,基于k-Mesh子网容错模型提出的容错路由算法是基于局部信息的和分布式的,因而具有很好的实际意义.

一种基于单播的大规模Mesh网络容错多播路由新算法

本文基于k Mesh子网连通的概念提出一种基于局部信息和分布式的Mesh网络容错多播路由算法。该算法的基本思想是把大规模的Mesh网络分成若干个较小的子网 ,多播消息只在各子网间进行路由 ,并由各子网独立完成操作。该算法的时间复杂性是线性的 ,模拟结果表明多播路由算法的多播时间步接近网络的直径。

Probabilistic analysis on fault tolerance of 3-Dimensional mesh networks

The probability model is used to analyze the fault tolerance of mesh. To simplify its analysis, it is as-sumed that the failure probability of each node is independent. A 3-D mesh is partitioned into smaller submeshes,and then the probability with which each submesh satisfies the defined condition is computed. If each submesh satis-fies the condition, then the whole mesh is connected. Consequently, the probability that a 3-D mesh is connected iscomputed assuming each node has a failure probability. Mathematical methods are used to derive a relationship be-tween network node failure probability and network connectivity probability. The calculated results show that the 3-D mesh networks can remain connected with very high probability in practice. It is formally proved that when thenetwork node failure probability is boutded by 0.45 %, the 3-D mesh networks of more than three hundred thousandnodes remain connected with probability larger than 99 %. The theoretical results show that the method is a power-ful technique to calculate the lower bound of the connectivity probability of mesh networks.

故障三维Mesh网络中的容错路由

该文在k—Mesh子网连通概念的基础上提出了三维Mesh网络中局部k—Mesh子网弱连通的概念，证明了局部k—Mesh子网弱连通的三维Mesh网络存在全局连通性。基于局部k—Mesh子网弱连通的三维Mesh网络提出了单播、广播容错路由算法。这些算法提高了容错能力且是基于局部信息的，因而具有很好的实际意义。