故障超立方体变形网络路由算法的研究

《故障超立方体变形网络路由算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号O1密级UDC硕士学位论文故障超立方体变形网络路由算法的研究学位申请人：刘庆学科专业：应用数学指导教师：刘红美二○一三年五月ADissertationSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofScienceTheStudyonRoutingAlgorithminFaultyHypercubeNetworksVariantsGraduateStudent:LiuQingMajor:MathematicsSupervisor:Prof.LiuHongmeiChinaT

2、hreeGorgesUniversityYichang,443002,P.R.ChinaMay,2013三峡大学硕士学位论文三峡大学学位论文原创性声明本人郑重声明：所呈交的学位论文,是本人在导师的指导下,独立进行研究工作所取得的成果,除文中已经注明引用的内容外,本论文不含任何其它个人或集体已经发表或撰写过的作品成果.对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明,本人完全意识到本声明的法律后果由本人承担.学位论文作者签名：日期：III三峡大学硕士学位论文内容摘要随着并行计算机互联网络规模的不断扩大,互联网络中处理器或处理器链路发生故障的情形是不可避

3、免的.因此,故障网络中的路由问题和连通性以及容错性成为了计算机研究领域的热点.如何设计简单可行的路由算法从而保证网络能继续有效的工作迫在眉睫.本文主要讨论了结点故障条件下超立方体变形网络（折叠超立方体网络和交叉超立方体网络）的局部连通性、拓展局部连通性、在局部连通性和拓展局部连通性下的容错路由算法、结点故障条件下的圈嵌入加强超立方体网络以及增广超立方体网络的边泛圈和边哈密顿性.论文主要分为四章,研究故障超立方体变形网络的容错性、连通性和路由算法.第一章主要介绍图的相关基本概念及其性质,超立方体网络及其变形网络拓扑结构和性质简介；并阐述与网络中路由算法相关的容错性

4、和连通性的研究意义.第二章主要研究了折叠超立方体网络的局部连通性和拓展局部连通性以及基于局部连通性和拓展局部连通性下的高效容错路由算法,得到了以下五个定理和两个高效容错并行路由算法：（1）若n维折叠超立方体网络FQn是局部k维子折叠超立方体连通的,则在FQn中必定存在至少Kmin(DuDvkk(),())条从非故障源结点u到目的结点v的并行路径,k且每一条路径的长度不超过((dUVkk,)3)2.（2）局部k-维子折叠超立方体连通的n-维折叠超立方体FQ中的所有非故障结点n构成一个连通图.（3）局部子折叠超立方体连通的n-维折叠超立方体FQ中的所有非故障

5、结点构成n一个连通图.（4）在一个拓展局部k-维子折叠超立方体连通的n-维折叠超立方体FQ中所有的n非故障结点构成一个连通图.（5）在一个拓展局部子折叠超立方体连通的n-维折叠超立方体FQ中,所有的非故n障结点构成一个连通图.算法1、具有大量故障结点的n-维折叠超立方体FQ中的高效并行路由算法.n算法2、基于拓展局部k维子折叠超立方体连通性下n-维折叠超立方体FQ中n的高效并行路由算法.第三章主要研究了增广超立方体的边泛圈性和边哈密顿性、加强超立方体在结点故障条件下的圈嵌入和交叉超立方体的局部连通性及其以及基于局部连通性下的高效容错路由算法.第四章我们对全文的

6、工作进行了总结和展望,并且提出了一些仍需要进一步研究的问题.IV三峡大学硕士学位论文关键词：超立方体折叠超立方体增广超立方体加强超立方体交叉超立方体边泛圈性哈密顿性并行路由算法容错性局部连通性V三峡大学硕士学位论文AbstractWiththecontinuousincreasinginparallelinterconnectionnetworkssize,processorfaultsandlinkfaultsinnetworksmayhappeninevitably.Inthiscase,theroutingproblemandconnectivityand

7、fault-toleranceinfaultynetworkbecomeahottopicofcomputerresearchfield.Howtodesignasimpleandfeasibleroutingalgorithmtoguaranteethenetworkstillcancontinuetoworkeffectivelyisimminent.Inthispaper,wemaininvestgatelocal-connectivity,extendedlocal-connectivity,fault-tolerantroutingalgorithmb

8、asedonlocal-