探析交叉立方体网络路由算法与图嵌入问题的研究

《探析交叉立方体网络路由算法与图嵌入问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中南大学博士学位论文交叉立方体网络路由算法与图嵌入问题的研究姓名：喻昕申请学位级别：博士专业：计算机应用技术指导教师：吴敏;王国军20071001摘要并行计算机互连网络的拓扑结构～直是国际上的研究热点。人们已提出了多种互连网络拓扑结构，其中超立方体是最流行的互连网络拓扑结构之一而且已被广泛用于商业并行计算机系统。但它并不是各方面拓扑性质最好的互连网络，于是人们开展了对超立方体的一类变型，即交叉立方体及其性质的研究。研究表明，交叉立方体的某些性质优于超立方体，尤其是它的直径几乎是超立方体的一半，因此是一种值得人们研究并推广应用的互连网络拓扑结构。本文

2、对交叉立方体网络的最短路径路由、并行路由、广播路由、无死镆路由、结点不相交路径长度以及交叉立方体环网络的嵌入闻题展开了研究。本文的主要研究工作和贡献如下：(1)针对已有的交叉立方体网络最短路径路由算法只能将部分最短路径作为候选路径进行输出且不具有根据结点的繁忙程度进行选择路径能力的缺点，给如了结点各边可进行最短路径路瘫的充要条件，提出了一种可根据结点的繁忙程度进行择路时间复杂度为D(矿)的完全国适应最短路径路由算法，其中投为交叉立方体网络的维数。算法在进行路由的每一步，都从所有可进行最短路径路由的邻边中选择繁忙程度最低的计算机结点对应的边进行路嘲，

3、因此是将全部最短路径作为候选路径，从面可输出任意一条最短路径。仿真实验结采验证了算法的有效性。(2)对交叉立方体的顶点不相交路径迸行了研究，证明了以下结论：在，z维交叉立方体aG中任意两顶点闻存在露条顶点不相交的路径，并且满足①最短路径的长度=两顶点间的距离，②所有路径中最长路径的长度竖两顶点闻的距离+4。这说明交叉立方体互连网络具有很好的并行通信性能和容错性能。同时提出了一种时间复杂度为阢行2)的以维交叉立方体网络并行路由算法，可输出源结点到睡的结点的三条结点不相交路径岛，A，恐，并且满足①峨产源结点到露的结点的距离，②IP,l-'螺结点到目的结

4、点的距离+3(卢l，2)。(3)在全端12虫洞模型下，利用递归方法将交叉立方体网络分解为互不相交的子交叉立方体网络，提出了栉维交叉立方体网络的广播路由算法，其所需路由步数为O(n／logE(n+l势，在常数乘积因子范豳内是优化的。仿真实验结果验证了算法的有效性。(4)证明了在不使用虚通道的情况下以(眨3)维交叉立方体网络中不存在无死锁的最短路径路由算法，通过将一个物理通道分成三个虚逶道提出了一种时闻复杂度为∞)的无死锁最短路径虫洞路由算法。理论分析和仿真实验结果表明了算法的有效性。(5)交叉立方体网络具有规模难以扩展(不易升级)的性质，而交叉立方体

5、环网络可以有效克服升级困难的缺点。本文证明了交叉立方体环网络仍然保持了交叉立方体网络具有的哈密顿连通性和泛圈性。本文通过对交叉立方体网络的路由算法和图嵌入问题的研究，提出了完全自适应最短路径路由算法、并行路由算法、广播路由算法以及无死锁路由算法，同时证明了交叉立方体环网络仍然保持了交叉立方体网络具有的哈密顿连通性和泛圈性，从而推动了交叉立方体网络的研究与应用。关键词互连网络，交叉立方体网络，路由算法，无死锁路由，图嵌入IIABSTRACTTheresearchoninterconnectionnetworkstopologyofparallelco

6、mputersystemsisahottopicintheworld，andmanynetworktopologieshavebeenproposed．Amongthosetopologies，hypercubeisoneofthemostpopularnetworktopologiesandhasbeenwidelyusedincommercialparallelcomputersystems。Butsometopologicalpropertiesofthehypercubeareinferiortothoseofothernetworksto

7、pologies,SOpeoplebegintoresearchintocrossedcubewhichisavariationofhypercube．Recentresearchesrevealthatsomepropertiesofcrossedcubealesuperiortothoseofhypercube，especiallythediameteroftheformerisapproximatelyhalfthatofthelaaeLTherefore，crossedcubenetworksareworthstudyingandpromo

8、tingtheirapplications．Inthedissertation,wedesignshortestpathr