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

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

王高才[1]2004年在《Mesh网络容错性的概率分析研究》文中研究表明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%的成功概率。路由算法的时间复杂性是线性的,模拟结果表明路由算法所构造的路由路径长度非常接近于两结点之间的最优路径长度。

王高才, 陈建二, 陈松乔, 李陶深[2]2004年在《Mesh网络路由算法容错性的概率分析》文中研究说明该文基于k Mesh子网的概念提出了两个简单的基于局部信息和分布式的Mesh网络容错路由算法 ,并对其容错性进行概率分析 ;在每个结点具有独立的出错概率的假设条件下 ,推导出路由算法成功返回由正确结点组成的路径的概率 .该文运用严格的数学推理 ,证明了Mesh网络结点出错概率只要控制在 1 .87%以内 ,则对于多达几十万个结点的Mesh网络 ,提出的路由算法具有 99%的概率确保找到正确结点组成的路径 .路由算法的时间复杂性是线性的 .模拟结果表明路由算法所构造的路由路径长度非常接近于两结点之间的最优路径长度 .

张祖平[3]2005年在《规则网络容错路由算法及可靠组播的研究》文中研究表明随着交互式多用户应用的增加,如网络视频会议、VOD/AOD、Internet-TV、交互式仿真、远程教学等网络多媒体应用,在Internet上迫切需要高可靠的组播路由服务以确保发送消息队列的可靠性,而现有的基于高层组播实现普遍缺少这种可靠性保证,因此可靠组播成为当前网络技术的研究热点。基于高层的可靠组播技术研究主要涉及到控制拓扑结构的可扩展性、容错性、组播算法、路由长度及组播协议的可靠性、容错性、可维护性与可扩展性等问题。随着Internet上结点数的急剧增加及结点进出网络存在较大的随意性,只有支持大结点数的、具有较好容错性的可靠组播协议才可能有真正的实用价值,因此协议的可扩展性与容错性问题成为研究的焦点。 论文在介绍相关基本概念及国内外相关研究现状的基础上,首先论述了超立方体网络的容错性,提出了多个容错性路由算法,并对算法的容错性、路径长度及对大结点规模的支持等方面进行了深入的分析。针对超立方体容错性好与可靠组播传输对控制拓扑的要求,提出了基于逻辑超立方体的可靠组播传输控制模型,在分析模型相关性能的基础上,提出了新的容错可靠组播协议。本文的具体工作为: (1) 论文在已有的强容错路由算法L2的基础上,提出了改进的路由算法L3及点对点的容错路由算法NL2,采用基于全局联通性的理论分析技术,详细分析了算法NL2的连通性概率等特性,理论分析与实际计算表明算法NL2的路径连通性概率比算法L3要好,而算法L3又比算法L2好得多。提出了点对点并行路由算法HPPA,对算法进行了详细的描述与分析,得出了并行路径条数、路由连通性概率与结点出错概率的公式,并分析了多种情况下的结点错误概率上界。论文还详细分析了算法NL2产生的路由路径的长度期望值,提出了改进的算法NL2N,得出了路由长度的较好上界表达式。 (2) 论文针对可靠组播传输协议采用控制拓扑结构的特点,在已有的前沿研究成果包括在LogCube结构上的HyperCast可靠组播协议和在FullCube结构上的支持可靠组播传输的稳定性检测协议CubeFullDist的基础上,提出新的控制拓扑结构—ComCube,详细论述了ComCube的构造与维护过程,提出了用逻辑联接增强结构联通性的思想,既改善LogCube结构中因部分结点联通度低造成整

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

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

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

王高才, 陈建二, 王国军, 陈松乔[7]2003年在《3-维Mesh网络容错性的概率分析研究》文中认为引言在众多的并行计算机系统的互联网络模型中,Mesh网络是研究者们研究得较早的,并且现在仍然是最为重要的和最有吸引力的网络模型之一。而较为有用的和最为流行的是

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

王高才, 陈建二, 王国军, 陈松乔[9]2003年在《Mesh网络容错广播路由算法的概率分析》文中认为1 引言近年来,许多基于Mesh网络拓扑结构的商用和研究用的大规模并行计算机系统已经问世,如国外的Intel Paragon、Stanford DASH、MIT Alewife、Touchstone DELTA、Symult 2010、MasPar系列,国内的曙光系列。其中结点(处理器、路由器等)间有效的通信是极为重要的,广播(One-to-All或Broadcast)通信操作是极为重要的通信模式之一,也就是一个结点与所有其余所有结点间进行通信,广播通信在大规模

王国军[10]2002年在《具有大量错误结点的超立方体网络容错模型和容错路由算法研究》文中指出超立方体网络是迄今为止最为重要和最具吸引力的网络拓扑结构之一。本文提出了两种全新的基于子立方体结构的超立方体网络中的局部连通性网络容错模型,基于局部连通性网络容错模型设计了高效的单播、广播和并行容错路由算法,提出了一种全新的、有效的和强有力的基于子立方体结构的超立方体网络容错模型和容错路由算法的概率分析方法和技术。 本文提出了两种基于子立方体结构的局部连通性网络容错模型:即局部K维子立方体连通性和局部子立方体连通性。证明了在结点错误比例任意接近50.0%时,局部连通的超立方体网络是全局连通的,即超立方体网络的局部连通性隐含了整个网络的全局连通性。所要求的局部连通性条件可以用基于局部管理的分布式方式进行检测和维护。 本文基于局部连通性网络容错模型设计了高效的单播、广播和并行容错路由算法。所设计的容错路由算法都是基于局部信息的,因而具有很好的实际意义。特别地,对于单播容错路由算法,不管所给定的超立方体网络是否满足局部连通性条件,算法都能适用:在满足要求的条件时,算法将成功地构造一条路由路径;在不满足要求的条件时,如果算法不能成功地构造一条路径,则算法将正确地报告出给定的超立方体网络不满足要求的条件。 本文还对局部连通性网络容错模型和网络容错路由算法进行了概率分析研究。大量的实验与经验表明超立方体网络具有很强的容错性。但是,当前国内外已经提出的超立方体网络容错模型只能表示一些极端的不大可能的情形,也就是说这些容错模型明显低估了超立方体网络的容错能力。本文使用概率分析的方法研究在给定结点错误概率的情况下,推导出局部连通性网络容错模型的容错性和网络容错路由算法的容错性概率。本文首次严格证明了一个具有1024个结点的10维超立方体网络能够容许多达10.0%的错误结点而具有99.0%的概率确保正确结点的连通性,而如果结点的错误概率不超过0.1%,则所有实际规模的超立方体网络能够具有99.9%的概率确保正确结点的连通性。这是当前国内外对超立方体网络进行概率分析的最好结果。该方法在确定网络容错模型和网络容错路由算法的容错性概率的下界时具有普遍意义。该方法也能够用于研究其它层次结构的网络和其它的网络通信问题。

参考文献:

[1]. Mesh网络容错性的概率分析研究[D]. 王高才. 中南大学. 2004

[2]. Mesh网络路由算法容错性的概率分析[J]. 王高才, 陈建二, 陈松乔, 李陶深. 计算机学报. 2004

[3]. 规则网络容错路由算法及可靠组播的研究[D]. 张祖平. 中南大学. 2005

[4]. 节点随机出错概率下的Mesh网络容错性分析[J]. 王晶, 王高才, 黄亿海. 小型微型计算机系统. 2010

[5]. 基于结点出错概率的Mesh网络容错性分析[J]. 刘先锋, 王高才, 陈建二, 陈松乔. 计算机工程与应用. 2004

[6]. 叁维Mesh网络容错路由算法及其概率分析[J]. 王高才, 李陶深, 陈建二. 小型微型计算机系统. 2005

[7]. 3-维Mesh网络容错性的概率分析研究[J]. 王高才, 陈建二, 王国军, 陈松乔. 计算机科学. 2003

[8]. 基于概率模型的E-2D Mesh网络容错性分析[J]. 肖杰, 梁家荣, 黄亿海. 小型微型计算机系统. 2009

[9]. Mesh网络容错广播路由算法的概率分析[J]. 王高才, 陈建二, 王国军, 陈松乔. 计算机科学. 2003

[10]. 具有大量错误结点的超立方体网络容错模型和容错路由算法研究[D]. 王国军. 中南大学. 2002

标签:;  ;  ;  ;  ;  ;  ;  ;  ;  

Mesh网络容错性的概率分析研究
下载Doc文档

猜你喜欢