Probabilistic analysis on mesh network fault tolerance

Mesh networks are among the most important interconnection network topologies for large multicomputer systems. Mesh networks perform poorly in tolerating faults in the view of worst-case analysis. On the other hand, such worst cases occur very rarely in realistic situations. In this paper, we study the fault tolerance of 2-D and 3-D mesh networks under a more realistic model in which each network node has an independent failure probability. We first observe that if the node failure probability is fixed, then the connectivity probability of these mesh networks can be arbitrarily small when the network size is sufficiently large. Thus, it is practically important for multicomputer system manufacture to determine the upper bound for node failure probability when the probability of network connectivity and the network size are given. We develop a novel technique to formally derive lower bounds on the connectivity probability for 2-D and 3-D mesh networks. Our study shows that these mesh networks of practical size can tolerate a large number of faulty nodes thus are reliable enough for multicomputer systems. For example, it is formally proved that as long as the node failure probability is bounded by 0.5%$0.5\%$, a 3-D mesh network of up to a million nodes remains connected with a probability larger than 99%$99\%$.     

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

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

基于结点出错概率的Mesh网络容错性分析

在并行计算机系统中,Mesh网络是最重要的网络拓扑结构之一。该文研究了基于结点出错概率Mesh网络的连通性,提出了k-Mesh子网连通的概念,运用严格的数学推理,推导出网络结点出错概率和Mesh网络的连通概率之间的关系。研究表明:特定的Mesh网络能保持相当高的连通概率,例如,笔者严格证明了,当网络结点出错概率控制在0.1%以下,则对多达几十万个结点的Mesh网络,网络连通的概率仍可保持在99%以上。     

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

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.     

节点随机出错概率下的Mesh网络容错性分析

容错性是多计算机网络中非常重要的研究主题.本文基于节点随机出错概率研究多计算机网络Mesh的容错性,采用子网划分方法,将网络划分为相互独立且不相交的子网,假设每个节点具有随机出错概率,通过分析子网的连通性,得到整个网络的连通概率.数值和模拟结果表明,网络连通概率随时间的增大而减小,在给定的时间内,网络规模越大,连通概率越低.例如,对于给定的指数分布(λ=3 509×10-6),当时间比较小(4000秒内)的情况下,多达四万节点的Mesh网络几乎总是连通的,连通概率达到99%以上,这也表明以Mesh网络为拓扑的多计算机系统是相当可靠的.     

点对点并行路由算法及容错性概率分析

用概率性分析方法,研究了在结点错误概率性分布的情形下,超立方体网络的点对点并行路由算法,并对算法的容错性概率、路径长度、算法复杂性进行了严格的推导。提出的算法是基于任意给定两个正确结点可以找出n条不相交的路径。分析了算法保证一条或多条路径同时联通的概率达到99.99%时结点的错误概率上界,同时考虑了两点间的海明距离变化,得出了较好的理论结论与计算结果。方法为研究超立方体网络容错性与并行路由算法提供了一种新的途径与新的考虑角度,具有更一般与更接近实际的意义。     

Mesh网络连通性的概率分析

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

基于分块策略的E-3DMesh网络容错性概率分析

对E-3DMesh网络中具有大量失效节点模式进行了研究,提出了基于分块策略的概率分析方法。基于该方法研究了在给定网络连通概率的情况下,E-3DMesh网络对网络节点出错概率p的要求。证明了要使多达上百万个节点的E-3DMesh网络连通概率保持在99%以上,网络节点出错概率必须控制在3.86%以下。新方法能够用于研究其他层次结构的网络和其他网络通信问题。     

自适应路由算法优于确定性路由算法

在研究并行计算机系统的容错时。自适应路由算法是一个极为重要的研究课题．它是在网络结点出错时，算法通过可选择的路径进行路由．在每个结点具有独立的出错概率的模型下，研究Mesh网络上自适应路由算法和确定性路算法的性能．本文提出的技术使得我们能严格地推导出路由算法的成功的概率，从而能分析和比较算法的性能．研究结果表明自适应路由算法具有明显的优势：一方面确定性路算法需要全局错误信息而变得高效性，另一方面自适应路由算法对于结点出错和网络规模具有更好的健壮性而具有更高的成功概率．     

节点随机出错概率下的E-2DMesh网络容错性研究

采用子网和概率模型对E-2DMesh网络在节点随机出错概率下的容错性进行分析,推出不同时间下的不同规模的E-2DMesh网络的连通概率下界,并且运用严密的数学方法推导出网络连通率与其节点出错概率的关系。实验结果表明以E-2DMesh为拓扑结构的并行计算机网络具有相当高的可靠性,通过对比进一步说明了E-2DMesh网络比Mesh网络具有更好的容错性。     

网络容错路由算法概率分析的一种新的方法

该文提出了一种新的概率分析方法来研究在给定结点错误概率的情况下超立方体网络强容错路由算法的容错性的概率。针对文中提出的基于新的局部连通性网络容错模型的高效的强容错路由算法犤1犦,该文首次严格证明了一个具有1024个结点的10维超立方体网络能够容许多达4.7%的错误结点而具有99%的概率确保找到正确结点组成的路径,而如果结点的错误概率不超过0.1%,则所有实际规模的超立方体网络能够具有99.9%的概率确保找到正确结点组成的路径。该算法的时间性能是最优的,且该算法构造的路径的长度不超过源结点和目的结点之间海明距离的两倍加上一个很小的常数。     

在3D-Mesh网络中的两种路由研究

在研究并行计算机系统容错时,路由算法是一个极为重要的研究课题。主要研究的是自适应路由算法和确定性路由算法在3D-Mesh网络上的性能。在每个结点具有独立的出错概率的模型下,提出的方法使得能够严格地推导出路由算法的成功概率,从而能够对算法进行分析和比较。研究结果表明,自适应路由算法具有明显的优势。一方面,自适应路由算法基于局部信息而变得高效;另一方面,自适应路由算法对于结点出错和网络规模具有更好的健壮性,而使其具有更高的成功概率。     

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

该文基于k-Mesh子网的概念提出了两个简单的基于局部信息和分布式的Mesh网络容错路由算法，并对其容错性进行概率分析；在每个结点具有独立的出错概率的假设条件下，推导出路由算法成功返回由正确结点组成的路径的概率．该文运用严格的数学推理，证明了Mesh网络结点出错概率只要控制在1．87％以内，则对于多达几十万个结点的Mesh网络，提出的路由算法具有99％的概率确保找到正确结点组成的路径．路由算法的时间复杂性是线性的．模拟结果表明路由算法所构造的路由路径长度非常接近于两结点之间的最优路径长度．     

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

One-to-all or broadcast communication is one of the most important communication patterns and occurs in many important applications in parallel computing. This paper proposes a fault tolerant, local-irdormation-based, and distributed broadcast routing algorithm based on the concept of k-submesh-cormectivity in all-port mesh networks.The paper analyzes the fault tolerance of the algorithm in terms of node failure probability. Suppose that every nodehas independent failure probability, and deduce the success probability of the broadcast routing, which successfully routes a message from a source node to all non-faulty nodes in the networks. The paper strictly proves that the broadcast routing algorithm with the success probability of 99％ to route among all non-faulty nodes on mesh networks with forty thousand nodes, in case that the node failure probability is controlled within 0.12％ Simulation results show that the algorithm is practically efficient and effective, and the time steps of the algorithm are very closeto the optimum.     

A simple fault-tolerant adaptive and minimal routing approach in 3-D meshes

In this paper we propose a sufficient codition for minimal routing in 3-dimensional (3-D) meshes with faulty nodes,It is based on an early work of the author on minial routing in 2-dimensional(2-D) meshes,Unlike many traditional models that assume all the nodes know global fault distribution or just adjacent fault information,our approach is based on the concept of limited global fault information,First,we propose a fault model called faulty cube in which all faulty nodes in the system are contained in a set of faulty cubes.Fault information is then distributed to limited number of nodes while it is still sufficeint to support minimal routing.The limited fault information collcted at each node is represented by a vector caaled extended safety level.The extended safety level associated with a node can be used to determine the existence of a minimal path from this node to a given destination .Specifically,we study the existence of minimal paths at a given source node,limited distribution of fault information,minimal routing,and deadlock-free and livelock-free routing.our results show that any minimal routing that is partially adaptive can be applied in our model as long as the dstination node meets a certain conditon.We also propose a dynamic planar-adaptive routing scheme that offers better fault tolerance and adaptivity than the planar-adaptive routing scheme in 3-D meshes.Our approach is the first attempt to address adaptive and minimal routing is 3-D meshes with faulty nodes using limited fault information.     

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

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

Reliable networks with unreliable sensors

Wireless sensor networks (WSNs) deployed in hostile environments suffer from a high rate of node failure. We investigate the effect of such failure rate on network connectivity. We provide a formal analysis that establishes the relationship between node density, network size, failure probability, and network connectivity. We show that large networks can maintain connectivity despite a significantly high probability of node failure. We derive mathematical functions that provide lower bounds on network connectivity in WSNs. We compute these functions for some realistic values of node reliability, area covered by the network, and node density, to show that, for instance, networks with over a million nodes can maintain connectivity with a probability exceeding 95% despite node failure probability exceeding 53%.     

无线传感器网络中连通问题的容错性分析

在确定部署的无线传感器网络中,由于节点本身的脆弱性及应用环境的恶劣性,在部署及研究分析网络时应该考虑到网络节点出错的因素.当网络连通概率和网络规模给定时,网络节点的出错概率应在多大的范围之内;在给定的网络规模和节点出错概率下,网络的覆盖与连通情况如何,这些都是本文分析研究的内容.本文首先定义了一个比较规范的三角形(Triangular)模型,研究了在确定部署情况下,网络节点出错的概率与网络的覆盖概率之间的关系,然后借助"k阶子网"的概念分析了Triangular网络的连通容错性,最后通过模拟试验,对前面通过理论分析计算出的传感器网络连通概率的下界和节点出错概率的上界的可信性进行验证,同时将Triangular拓扑的网络与网格状网络进行比较.     

Proof that pyramid networks are 1-Hamiltonian-connected with high probability

Wu revealed in 2001 that pyramid networks are Hamiltonian-connected. This investigation demonstrates that a pyramid network with one faulty node or one faulty edge is Hamiltonian-connected, excluding some special faulty cases by building a Hamiltonian path between any two distinct nodes in it. Although a pyramid network with one fault is not Hamiltonian-connected, this study indicates that a pyramid network is 1-Hamiltonian-connected with a very high probability.     

基于概率模型的E-2D Mesh网络容错性分析

研究了太比特路由器核心交换网络拓扑的一种新结构-E-2D Mesh.提出一种计算E-2D Mesh网络连通率的新方法.证明了当网络结点失效率控制在0.66%以下时,具有四万多个结点的E-2D Mesh网络可保持不低于99%的连通率,且在同等规模条件下,E-2D Mesh网络结点容错率至少是Mesh网络的11.09倍.研究结果表明,该方法在计算E-2D Mesh网络连通率时显示出较强的生命力且能够用于研究其它层次的网络和其它网络通信问题.