Mesh网络连通性的概率分析

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

基于有故障区域的Mesh网络目标结点间的最短路由算法

Mesh网络是较早研究的且现在仍然是最为重要的、最有吸引力的网络模型之一。因其结构、规则简单及良好的可扩展性,易于VLSI(超大规模集成电路)的实现,网格(Mesh)网络不仅成为了许多理论研究的基础模型,而且也是许多大型多处理器并行计算机系统所采用的拓扑结构。给出了两种故障情形下的最短路由算法:1)当Mesh的行数大于等于3且列数大于等于3、出现一个矩形故障区域时,给出了任意两个无故障结点间的最短路由算法,并且计算出了路径长度；2)当Mesh的行数≥3且列数≥3、某个结点及其k跳以内的邻居结点出现故障时,给出了任意两个无故障结点间的最短路由算法,并且计算出了路径长度。     

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

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

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

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

基于3D Mesh结构的一种静态路由算法

3D NoC在同构多核系统中相比2D NoC具有更为优越的性能.本文在研究3D Mesh结构的基础上,对拓扑结构中的平均延时和理想吞吐量进行了理论上的评估,并提出了一种基于3D Mesh的新的静态路由算法,最后运用NS2网络仿真软件对其进行仿真和比较.实验结果显示,新的路由算法可以有效地提高吞吐量,并在大规模数据传输时...     

三维片上网络高维超立方裂变拓扑结构研究

三维片上网络是解决片上网络通讯瓶颈的重要途径,拓扑结构是三维片上网络研究中的关键问题之一。针对高维超立方拓扑结构节点度迅速增加,出现通讯瓶颈的问题,提出一种高维超立方裂变拓扑结构,该拓扑在同等网络规模下具有网络直径短、可扩展性强等优点。以五维超立方裂变拓扑结构为例进行了仿真实验,并与3D Mesh拓扑结构进行了对比分析:当两种拓扑结构在均匀负载状态下达到饱和时,五维超立方裂变拓扑结构的吞吐量比3D Mesh拓扑结构高300%,平均延时比3D Mesh拓扑结构低85.1%,平均跳数比3D Mesh拓扑结构少21.5%;在局部负载下,五维超立方裂变拓扑结构的平均延时比3D Mesh拓扑结构低79.1%,平均跳数比3D Mesh拓扑结构少13.3%。仿真实验表明提出的网络拓扑结构既保留了原有超立方体拓扑结构的优点,又解决了高维超立方体拓扑结构的通讯瓶颈问题。     

无线Mesh网骨干层2-终端可靠性计算策略

无线网络环境下的网络可靠性取决于网络中的多种因素.因此,在计算无线网络的2-终端可靠性时,应该考虑到网络中的各个组成部分对可靠性的影响.文中根据无线Mesh网的结构特性,提出了一种无线Mesh网骨干层的2-终端可靠性计算策略.该策略充分考虑到无线网络环境下节点故障和节点间的无线链路故障对网络的2-终端可靠性的影响,因此能够更加合理地评价实际环境中的无线Mesh网骨干层的2-终端可靠性.仿真实验证明,该策略能够有效提高无线Mesh网性能.     

基于2D Mesh的NoC路由算法设计与仿真

在研究Turn Model模型的基础上,提出一种基于2D Mesh结构的XY-YX路由算法,是一种确定性的无死锁的最短路径路由算法。给出无死锁的证明,通过片上网络（NoC）模拟仿真实验平台NIRGAM,将该算法在一个4×4的2D Mesh网络中进行仿真,并与XY路由算     

基于递推分解的Torus网络可靠性研究

为解决大规模Torus网络可靠度计算中遇到的NP难问题,引入递推分解和组合模型的思想对Torus网络的可靠性进行分析研究.递推分解的算法降低了计算网络可靠度的复杂性,组合模型的方法则降低了网络的结构复杂度.对于大规模的Torus网络,通过采用可靠度上下界逐步逼近的方法,可以得到较高精度的可靠度近似值.实验结果表明,在结点失效概率均小于0.10%时,对多达上千个结点的Torus网络仍超过90%的可靠度,而且提出的方法也适合其它并行体系结构网络的可靠度计算.     

Merkle树遍历机制的改进及应用研究

无线Mesh网络的网络结构导致了无线Mesh网络具有更多的安全隐患.其中数据完整性校验是保障无线Mesh网络通信安全的一个重要方面,而Merkle可信树适用于批量数据验证.研究无线Mesh网络的安全特点,并研究Merkle可信树数字签名技术.研究表明,在Merkle可信树应用中,遍历可信树计算认证路径节点值需要消耗大量的时间.Merkle可信树的遍历算法的效率是影响Merkle可信树数字签名的关键.在研究的基础上,提出了一种改进的Merkle可信树遍历算法,并将改进后的Merkle可信树应用于无线Mesh网络的数据完整性校验机制.     

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

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

On fault tolerance of 3-dimensional mesh networks

In this paper, the concept of k-submesh and k-submesh connectivity fault tolerance model is proposed. And the fault tolerance of 3-D mesh networks is studied under a more realistic model in which each network node has an independent failure probability. It is first observed that if the node failure probability is fixed, then the connectivity probability of 3-D mesh networks can be arbitrarily small when the network size is sufficiently large. Thus, it is practically important for multicomputer system manufacturer to determine the upper bound for node failure probability when the probability of network connectivity and the network size are given. A novel technique is developed to formally derive lower bounds on the connectivity probability for 3-D mesh networks. The study shows that 3-D mesh networks of practical size can tolerate a large number of faulty nodes thus are reliable enough for multicomputer systems. A number of advantages of 3-D mesh networks over other popular network topologies are given.     

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\%$.     

超立方体网络连通性的概率分析

超立方体网络是大型多处理器并行计算机系统中极为重要的拓扑结构.本文使用概率分析的方法研究了在给定结点错误概率的情况下,具有子连通性的超立方体网络容错模型的连通性。理论分析和试验结果表明:在具有大量分布结点错误情况下,超立方体网络是子连通的概率非常高。     

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网络为拓扑的多计算机系统是相当可靠的.     

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

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