【作者】 梁活民；

【导师】 肖文俊；

【作者基本信息】 华南理工大学 ， 计算机应用技术， 2012， 博士

【摘要】 基于应用层的覆盖网络技术正迅速兴起并得到广泛的应用。结构化P2P覆盖网络凭借其去中心化、扩展性好、容错性高等优点，日益在互联网信息共享方面显示出巨大潜力。而拓扑构造和资源定位是结构化P2P覆盖网络研究两个核心问题，直接影响了结构化P2P覆盖网络的可用性和系统效率。结构化P2P覆盖网络的拓扑性质决定了其拓扑维护的代价以及节点间路由寻址的性能。常数度结构化P2P覆盖网络在保证了高效路由的同时具备稳定性强、控制信息少、网络负载小等优点，而利用小世界网络理论构造的覆盖网络较小的平均路径长度和较大的聚类系数等优点有利于提高网络的路由效率，这两点对近年来的覆盖网络拓扑研究都产生了一定的影响。结合这些因素构造具有优良特性的结构化网络拓扑是结构化P2P覆盖网络构造的重要研究方向。分布式哈希表技术使结构化P2P覆盖网络能准确定位具有精确标识符的资源，但对于不具备精确标识符的资源却非常困难。在结构化P2P覆盖网络没有目录服务器、各个节点没有全局索引的前提下，为资源定位提供更强大的查询手段是结构化P2P覆盖网络能否得到广泛应用的重要因素。论文以上述两个核心问题为主线，主要开展了以下几方面的研究工作：1.具有小世界网络特性的常数度结构化P2P覆盖网络拓扑构造。基于群论中的半直积方法和具有小世界网络特性的凯莱图模型，提出了一种新型的常数度结构化覆盖网络CayDHT。CayDHT继承了凯莱图的点可迁特性，具有简单高效的路由算法，而常数度特性使得构造大规模的对等网络称为可能。理论分析和实验表明，CayDHT具有O (l)大小的常数路由表、 O (log N)大小的网络直径和优良的容错能力，并具有小世界网络的特性。2.结构化P2P覆盖网络的多关键字搜索研究。一般来说，在结构化P2P覆盖网络中通过多关键字来定位资源需要分布式倒排索引等额外机制。水平切分和垂直切分是分布式倒排索引的两种主要存储方式，本文讨论和分析了结构化P2P覆盖网络在这两种模式下实现多关键字超集搜索的关键问题，并基于CayDHT对这两种模式进行了详细的理论分析和实验对比。3. CayDHT的复杂搜索(盲目搜索)研究。和其他结构化P2P覆盖网络一样，基于分布式哈希表的CayDHT对于不限定搜索形式的复杂搜索缺乏支持，引入传统非结构化覆盖网络的基于广播/洪泛的盲目搜索方法是必要的。本文通过分析CayDHT拓扑的性质，结合凯莱图的点可迁特性，提出了一种基于虚拟搜索树的复杂搜索算法(VTCS)，无需额外维护树结构，具有良好的负载平衡特性，可以在O(logN)的时间复杂度内完成无冗余消息的搜索分发。4.结构化P2P覆盖网络的分区复杂搜索研究。基于复杂搜索和盲目搜索的资源定位都依赖于初始化TTL参数来控制搜索的范围和减少冗余消息，而很多研究显示这种控制方法还存在比较大的缺陷。本文通过借鉴了超节点混合对等网络的优点，使用图控制集理论及网络资源布局理论，基于CayDHT提出了一种分区盲目搜索模型，该模型在搜索时只需要通过小部分搜索分发节点进行TTL参数较小的洪泛式搜索。理论分析和实验表明这种方法可以较好的控制搜索范围，并且可以保证搜索的完全性。更多还原

【Abstract】 Overlay network technology based on application-layer is rapidly emerging and has beenwidely used in the Internet. Structured Peer-to-Peer overlay networks demonstrate many goodfeatures such as decentralization, scalability and fault tolerance, hence it indeed has a greatpotential to become a major technology for sharing information. Topology construction andthe resource locating are two important research fields of structured overlay network, whichdirectly affect the usability and efficiency of network.1. Topological properties determine the costs of topology maintenance and the routingperformance between nodes. Constant degree structure P2P overlay network provides notonly efficient routing but strong stability, less control message and network overhead, besides,low average distance and high clustering coefficient are two main attractive properties ofSmall-world network for overlay network which implies a small latency lookup andpreferable routing efficiency. These two factors have already had a significant impact uponresearch of overlay network topology. Combining these factors to construct a structurednetwork topology with good properties is an important research direction in P2P networktopology construction.2. By utilizing distributed hash tables, structured peer-to-peer network can provide exact-match search and locate the resource effectively. However, it is difficult to locate a resourcethat does not own an exact identifier when facing diversified search styles and complexqueries. Therefore, on the premise of lacking directory server and global index an efficientnovel distributed retrieval model that support complex queries is the key issue whether thestructure overlay network can be widely used.The thesis focuses on these two problems, and makes the main research subjects andcontributions as follows:1. Construction of constant degree structure P2P overlay network topology with small-world features. Based on the semidirect products of finite group and Cayley graph with small-world features, a new constant degree P2P overlay network CayDHT is proposed. CayDHTinherits the vertex-transitive property of Cayley graph, its simple routing scheme and constantrout table make it possible to construct large scale network. The simulations and experimentsshowed that this model provides O(1) routing table, O(logN) query path, good robustness andsmallworld properties.2. Multi-keyword search of Structured P2P overlay network. Generally speaking, instructured P2P network to locate a resource by multi-keywords requires additional mechanism such as distributed inverted index. Horizontal partition and vertical partition are two principalpattern of distributed inverted index. We discuss and analyses the key problem of multi-keyword superset search under these two patterns, and we also evaluate exhaustively thesetwo patterns by simulation and theoretical analysis under CayDHT.3. Complex/blind search of CayDHT. Like other structured P2P overlay networks,CayDHT does not provide any methods for complex/blind search too, so introducing flexibleblind search of traditional unstructured P2P network is necessary. By analyzing the topologyproperty of CayDHT, an efficient blind search scheme named Virtual Tree based ComplexSearch of CayDHT (VTCS) is proposed. The algorithm guarantees that query messages canvisit every node within O(logN) hops while does not need to maintain extra data structure, andwhat’s more, the algorithm shows good load-balancing.4. Complex/blind search base on partition. Typically, the blind search depends on theTTL parameter to control the scope of the search and reduce the redundant messages.However, many studies have shown the TTL mechanism has some defects. By introducingthe advantage of super-peer based P2P network, with the help of dominating sets of graphtheory and solution to resource placement of network, we propose a novel search algorithmbased on partitioning the whole network. The algorithm can guarantees the completeness ofsearch result while only need to search the subzone with small TTL parameter. Theoreticalanalysis and simulation show that the method can control the search scope more effectively.更多还原