几类新型互连网络拓扑结构与并行算法及其构造方法在P2P网络中的应用

摘要

在并行分布式系统中，互连网络拓扑结构决定性能。至今为止，已经提出了相当多的互连网络拓扑结构。自从S.B.Akers与B.Krishnamurthy倡导把Cayley图作为对称互连网络模型之后，网络设计者和图论学者利用各种技巧提出并研究了一系列互连网络模型，如超立方体网络、Torus网络、蝴蝶网络、De Brujn和Kautz网络等。研究者们一般侧重于针对某种具体的网络结构进行研究，并且大多数是采用直观的方法。由于互连网络表示符号的不同，经常会出现相同的网络结构被重复地提出的问题，因此就有必要采用一种新的研究方法来统一处理互连网络拓扑结构问题。
　　 本文的研究重点在于首先利用代数图论的方法分析一些现行网络拓扑结构的构造共性及构造本质，总结出一种对于互连网络拓扑结构的统一研究方法；然后使用这种研究方法，提出了几类新型的互连网络拓扑结构，并研究其拓扑性质、路由算法、通信算法以及一些典型的并行算法等；最后把这种代数图论的研究方法应用于复杂网络和P2P（Peer to Peer）网络，构造出了一种新的具有小世界特性的P2P覆盖网络。
　　 本文的主要研究内容和创新点包括以下几个方面：
　　 1、使用代数图论方法对现行著名的互连网络拓扑结构进行分析，归纳出了构造互连网络拓扑结构的一套理论的、系统化的研究方法，如Cayley图方法、群直积和半直积方法。这种研究方法对于研究互连网络的构造本质和提出新型的互连网络拓扑结构具有现实的意义。
　　 2、通过采用代数图论中Cayley图的方法对OTIS（Optical Transpose Interconnection System）网络的分析发现，该网络模型是陪集图，缺乏对称性。为了弥补其对称性的不足，作者导师提出了一类Biswapped网络结构。本文则介绍了如何采用代数图论方法从OTIS网络模型中构造出Biswapped网络的过程，并研究了其拓扑性质及容错性能，然后以Biswapped网络为基础，开发了基于该网络结构的一系列并行算法包括基本通信算法、并行矩阵乘算法和并行排序算法等。这些算法在Biswapped网络中实现简单，且具有较低的时间复杂度。
　　 3、为了吸取超立方体网络和Kautz网络的优点，剔除其缺点，使用代数图论中直积的方法，提出了一类新型的积网络--Hyper-Kautz网络，并研究其相关的拓扑性质（包括直径、度和Hamilton圈等），然后基于Hyper-Kautz网络提出了最优广播算法、路由算法等一些基本的并行算法，同时分析了Hyper-Kautz网络的容错性能和平均内点距离。Hyper-Kautz网络具有路由简单和容错性强等诸多优点。
　　 4、使用代数图论中半直积和Cayley图方法来研究复杂网络和P2P网络，通过推广CCC（Cube-Connected Cycles）图，得到了一类符合小世界特性的Cayley图--GCCC（Generalized Cube-Connected Cycles）图，并把GCCC图作为P2P网络的静态拓扑，提出了一类新的具有小世界特征的P2P覆盖网络。相对于随机图的静态拓扑，这类覆盖网络具有对称性好、聚集系数大和平均距离小等许多优势。同时还在该覆盖网络的基础上构造了一种基于Cayley图的语义对等网络结构。

目录

文摘

英文文摘

声明

第一章 绪论

1.1 研究背景及意义

1.2 本文的主要研究内容

1.3 本文的组织结构

第二章 分布式互连网络中的代数图论方法研究

2.1 引言

2.2 互连网络结构与通信算法的Cayley图研究方法

2.2.1 Cayley图的定义

2.2.2 互连网络结构的Cayley图研究方法

2.2.3 Cayley图方法对于研究路由算法的优势

2.3 互连网络结构的群直积、半直积研究方法

2.3.1 群直积的定义

2.3.2 群半直积的定义

2.3.3 群直积、半直积方法对互连网络结构设计的优势

2.4 本章小结

第三章 Biswapped网络拓扑结构及其并行算法

3.1 引言

3.2 BSN拓扑结构

3.2.1 OTIS网络结构的定义

3.2.2 BSN结构的定义

3.2.3 BSN结构的拓扑性质

3.2.3 BSN的路由算法

3.2.4 BSN的Hamilton圈

3.3 BSN的容错性分析

3.3.1 BSN的网络连通度

3.3.2 BSN的容错直径

3.3.3 BSN的诊断性

3.4 BSN的基本通信操作算法

3.4.1 BSN的广播算法

3.4.2 BSN的并行前缀和算法

3.4.3 BSN的并行数据和算法

3.5 BSN的并行排序算法

3.5.1 映射策略

3.5.2 并行排序算法

3.5.3 时间复杂度分析

3.6 BSN的并行矩阵乘算法

3.6.1 矩阵映射策略

3.6.2 并行矩阵乘算法

3.6.3 算法时间复杂度分析

3.6.4 模拟实验与分析

3.7 本章小结

第四章 Hyper-Katuz网络拓扑结构及其并行算法

4.1 引言

4.2 预备知识

4.3 Hyper-Kautz网络的拓扑结构

4.4 Hyper-Kautz网络的最优路由算法和广播算法

4.4.1 最优路由算法

4.4.2 最优广播算法

4.5 Hyper-Kautz网络的容错性与点不相交路径

4.6 Hyper-Kautz网络的Hamilton圈和平均内点距离

4.6.1 Hamilton圈

4.6.2 平均内点距离

4.7 Hyper-Kautz网络与其它积网络的比较

4.8 本章小结

第五章 Cayley图方法在结构化P2P覆盖网络的应用

5.1 引言

5.2 覆盖网络与其静态图的关系

5.3 结构化P2P覆盖网络的Cayley图构造本质分析

5.3.1 Chord

5.3.2 CAN

5.3.3 Ulysses

5.4 几种结构化P2P覆盖网络拓扑性质比较

5.5 小世界网络

5.5.1 小世界网络的概念

5.5.2 基于Cayley图的小世界网络模型

5.6 一种新颖的具有小世界特征的结构化P2P覆盖网络

5.6.1 CCC图与推广CCC图的定义

5.6.2 GCNET

5.6.3 性能评估

5.7 语义对等网络Semantic GCNET

5.7.1 语义对等网络

5.7.2 Semantic GCNET的构建

5.7.3 Semantic GCNET资源搜索

5.7.4 实验分析

5.8 本章小结

总结与展望

参考文献

攻读博士学位期间取得的研究成果

致谢