星形图上无死锁受限条件与路由算法

《星形图上无死锁受限条件与路由算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文插图索引图1．1(a)，(b)，(c)分别为2维，3维和4维的星形图s：，s。和s。⋯⋯⋯⋯⋯⋯1图1．23维超立方体互联网络拓扑结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯2图2．1三维星形图S，⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯9图2．2星形图上最小无死锁路径算法模拟⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯14图3．1星形图上单缓冲无死锁路径算法模拟⋯⋯⋯⋯．．．⋯⋯⋯⋯⋯⋯⋯⋯⋯18图4．1星形图上双缓冲无死锁路径算法模拟⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯22图5．1一个有故障的四维超立方体⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯2

2、7III星形图上无死锁受限条件及路由算法附表索引表1．1星形图与超立方体互联网络的拓扑特性比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯2表5．1图5．1部分节点的SV,ESV、SPV、OPM、EOPM数据⋯⋯⋯⋯⋯⋯⋯27表5．2SV、ESV、SPV链路故障的情况下模拟结果(八维)⋯⋯⋯⋯⋯⋯⋯⋯32表5．3SV、ESV、SPV链路故障的情况下模拟结果(十维)⋯⋯⋯⋯⋯⋯⋯⋯32IV湖南大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或

3、撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。I’～，作者签名：疋予日期：2∞s年写月23日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全郝或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、保密口，在——年解密后适用本授权书。2、不保密团。(请在以上相应方框内打

4、“√”)作者签名：乏孚日期：2∞5年5月23日剔磁钰蒸特翘醐删泔珊3日。誉茹露j硕士学位论文第1章绪论本章首先介绍星形图(StarGraph)与超立方体(Hypercube)互联网络的拓扑结构及其构造方式，其次介绍本课题的研究意义，然后分析星形图与超立方体互联网络的拓扑结构及其路由算法的研究现状，接着介绍本课题的主要研究内容和创新点，最后是本文的组织结构。1．1星形图与超立方体互联网络简介1．1．1星形图互联网络简介定义1．1(星形图)：n维星形图S。∥，E)满足：a．点集合V对应所有{1⋯2．．，U)上的置换，即V={P。P：⋯P。l1s

5、P，sn，且当j—k时，P，≠P女)；b．边集合E={(P，q)lP，q∈V，且存在j>1使得P1=qj、q1=P，，而对任意k≠j有Pt=q^}j芏冀22i】l!图1．1(a)．(b)。(c)分别为2维，3维和4维的星形图S2，S3和S41．1．2超立方体互联网络简介定义12(n维超立方体互联网络)：n维超立方体网络Q。(或简称为”一cube)是具有下述性质的一种网络拓扑结构：(1)它由2”个节点和，l·2”1条星形图上无死锁受限条件及路由算法边构成；(2)每一个节点可由一个不相同的n位二进制串bib2⋯b。进行编号；(3)节点编号的规则

6、为，当且仅当G中两个节点的二进制串恰有一位不同时，两个节点是相邻的，即这两个节点之间有一条边相连。图1．2给出的是一个3维超立方体互联网络的拓扑结构图例，图中有23=8个节点和3"23‘1=12条边，图中还标识出了其中各节点的二迸制串编号(分别从000到111)。由图1．2可以看出，3维超立方体互联网络的的直径为3，各节点的连接度为3。图1．23维超立方体互联网络拓扑结构1．1．3星形图与超立方体互联网络的比较星形图与超立方体互联网络作为并行计算机系统中两种最为重要、最具吸g力的拓扑结构，它们在拓扑特性上有着上述众多相似之处但毕竟这两种网络

7、存在着不同。可从下表中不同维数的星形图与超立方体的拓扑特征比较看出，星形图在短直径，低连接度等方面具有更加优秀的表现。表1．1星形图与超立方体互联网络的拓扑特性比较边数连接度直径平均距离容错直径Q712873．58S5120463．7s9Q』2409612613S15040695．9s12Q』826214418919S93628808128．1s15由表1．1可知，星形图互联网络与超立方体互联网络拓扑特性的相似之处在2硕十学位论文于，这两种互联网络均具有正则性、对称性以及可嵌入性等良好性质，且各节点之间均具有多条并行路由，因此这两种互联网络

8、均具有很强的可容错性。其不同之处在于星形图在短直径，低连接度等方面具有更加优秀的表现。1．2课题的研究意义由于星形图和超立方体互联网络在其拓扑性质上有着正则性、对称性、强容错性等