论文部分内容阅读
近年来,基于分布式对等(Peer-to-Peer)系统在互联网上广泛的流行起来,成为了当前占据Internet主要流量之一。基于分布式散列表(Distributed Hash Table,DHT)的结构化P2P系统是P2P领域研究的热点之一。P2P系统中的一个核心问题:如何高效地定位到所需要的资源,即路由算法问题。目前大多数已有的分布式结构化P2P系统的覆盖网络的拓扑集中在如何尽量降低查询路径的长度和路由表大小。本文主要围绕着如何让P2P系统高效的定位资源展开研究工作。本文的研究内容是对等覆盖网络拓扑的设计和分析,并且针对该对等网络的拓扑设计路由算法及其上的组播算法。
本文创新性的利用Cayley图的方法来设计P2P覆盖网络的拓扑。本文首先使用群论的数学方法设计了一种新的Cayley图г模型。Cayley图г的顶点的度可以达到O(logN),直径可以达到(logN)/(loglogN),并且聚集系数为(C2r-1+C2k-1)/C2r+k-2.Cayley图г的聚集系数可以达到小世界特征。Cayley图г拥有的这些优秀特性非常适合做P2P覆盖网络的静态拓扑。本文在Cayley图г的基础上设计了一个全新的分布式结构化P2P系统协议E3C。E3C继承了Cayley图г具有的较小的路由表和较短的查询路径长度和较大的聚集系数的优秀特性。模拟仿真实验表明E3C是一个拥有能够达到理论下界的路由表大小和路由长度,具有较大的聚集系数和较好的鲁棒性的新颖的P2P系统。
本文创新性的解决了E3C上的组播,通过E3C上的路由算法设计了E3C上的组播树的构造算法。定义了加入组播树的规则,使得结点能够快速加入组播树,有利于提高组播树性能。通过实验证明组播树的深度能够达到O(logN),该组播树具有较高的性能和可扩展性。