【作者】 卢丽；

【导师】 姚家宁；

【作者基本信息】 重庆大学 ， 计算机应用技术， 2007， 硕士

【摘要】 资源搜索问题是P2P网络的核心问题之一,也是P2P网络研究的热点。P2P的资源搜索模型,可分为四种:集中式的资源搜索模型,分布式非结构化的搜索模型,分布式结构化的搜索模型和混合式搜索模型。目前,最受研究者们关注的是基于DHT(分布式哈希表)的分布式结构化搜索模型。DHT路由算法使用分布式哈希函数进行资源搜索,快速、扩展性较好。但DHT方法存在路由性能不高、只支持关键字精确查找,且没有考虑节点的位置信息等问题。典型的DHT模型有Chord、Pastry、CAN、Tapestry和P-Grid等。本文在深入分析了当前P2P系统中常见的搜索模型及对应搜索算法的原理、实现方法、性能特点及优劣势的基础上,针对P2P系统中的资源搜索问题,参考一系列现实及网络世界中呈现的若干规律(如幂规律、Patreo分布规律、Zipf规律及Small World现象及其应用),提出了一种基于DHT模型的启发式算法机制,并给出了此机制中相关公式及其变形,该机制根据前述规律对系统中的一小部分热门数据归纳提取并构造该部分数据的详细附加路由表项,然后置于每个peer节点的索引表中,且这部分数据随着时间增加不断调整。任一对等节点在执行查询时,首先查询索引表,如果没有相关记录项然后再查询本地路由表以转发请求,直至目标数据所在节点被搜索到或者搜索失败查询结束。由于这部分热门数据承担系统中绝大部分的查询要求,所以大部分查询可以在一个逻辑路由跳之内完成对目标数据的查询请求;接下来,在详细分析基于DHT方法的P-Grid、Chord模型的结构定义、系统构造、查询过程的基础上,把上述启发式机制应用于P-Grid、Chord模型中,并给出了改造后的启发式P-Grid(Heuristic P-Grid即HP-Grid)模型、Chord(Heuristic Chord即HChord)模型相应的系统构造、查询、表格维护机制以及算法详细处理过程。论文还在麻省理工学院提供的p2psim平台上对上述机制和改进后的HP-Grid、HChord算法进行了仿真试验。结果表明:上述机制与结构化的DHT搜索模型结合,可以有效缩短资源搜索时的路由长度、降低系统开销,并可以对系统中数据对象的分布起到优化的作用。最后,对全文工作作了总结,并对论文的不足及进一步的工作做出说明。更多还原

【Abstract】 Resources locating is a key issue of P2P network and a research hotspot as well. Based on a network topology, the resources locating models of P2P system are divided into 4 types: Centralized Topology, Decentralized Unstructured Topology, Decentralized Structured Topology and Partially Decentralized Topology. A DHT based Decentralized Structured model, which avoids central managing and broadcast querying, has recently become a focus in the research area. It applies hash function to map the input key of a file to a virtual node, and then sets up a connection with the node through some kind of routing algorithm. The DHT based methods enjoy great advantages of simplicity and extensibility. However, as the keyword space is isolated from the real physical network, the method will disturb the data Locality. As a result, query latency is high while data-downloading speed is low. Typical DHT-based systems include Chord, Pastry, CAN and Tapestry and P-Grid.Based on the careful analysis of principle, realization measures, performance characteristic, advantage and disadvantage of the search models and search algorithms in P2P system, this article takes good consideration of several laws in real world and network (including power-law, Patreo distribution law, Zipf law and Small-World phenomenon and its application etc.) and put forward a newly heuristic DHT mechanism to aim to solving resources locating or searching in P2P system. The relative mathematics formula are also provided and carefully ayalysed. The mechanism picks up several popular data and stores the relative information about those data into an index table in each peer node, and those data can be adjusted by system with the time. It firstly queries in the index table and then turns to the local route table in each peer node and transmit the request to route peer node if not any items were found. Those popular data take on most of the query requests in a given P2P system, hence many requests can be satisfied in a logistic hop. Next, this article uses the mechanism in the P-Grid called HP-Grid and Chord called HChord model both are based on DHT one. The system construction, query, table maintenances and the detailed improved algorithm process are also provided.Further more, this article carried out simulation tests on this mechanism and algorithms in MIT P2Psim simulator, which demonstrate that they can effectively shorten the route hops when processing a query request, lower system load and even can optimize the data distribution in system by combining with DHT model. In the end, there is a complete summary on the work of this paper and a discussion of future work.更多还原