基于Chord查找算法的P2P系统研究

发布时间：2018-03-04 14:56

本文选题：Chord　切入点：物理拓扑　出处：《北京交通大学》2014年硕士论文　论文类型：学位论文

【摘要】：Peer-to-Peer：简称P2P)技术的核心思想是所有参与的节点在地位上是平等的,各节点在享受来自其它节点服务的同时也向其它节点提供服务。换而言之该技术并不区分客户机和服务器,各个节点不只是客户机还是服务器,这种模式使互联网中的资源被广泛发掘和利用,已经在各个领域得到了广泛应用。 P2P系统的最大挑战是在没有中心服务器的情况下,高效的查询和资源定位。目前这方面的研究都集中在结构化的路由算法上,其中Chord算法因简单易实施,良好的鲁棒性和扩展性等优点成为国内外研究的热点。本文首先对P2P网络的理论基础进行简要概述,简单分析P2P网络的四种拓扑结构,并介绍了它们的经典模型Napster、Gnutella和KaZaa,然后介绍全分布式结构化拓扑下基于分布式哈希(DHT)技术的四种经典资源查找算法,并着重描述了Chord查找算法。传统Chord查找算法的一个明显的缺点,是没有考虑P2P网络的物理拓扑结构,以致其查找过程的网络延迟较大。除此之外,存储空间的问题也很少被考虑。为弥补这些缺陷,本文的研究工作如下： 1.针对传统Chord物理拓扑和逻辑拓扑不匹配的问题,结合蚂蚁优化算法和双向查找技术的优点,我们提出了一种基于蚂蚁优化算法的双向查找Chord算法。首先,利用蚂蚁优化算法建立Chord环,解决物理拓扑和逻辑拓扑不匹配的问题,在此基础上,使用双向查找方法,进一步加快查找速度。实验结果表明,该算法比传统的Chord算法有更高的查找效率。 2.针对物理拓扑和逻辑拓扑不匹配以及空间复杂度的问题,结合Counting Bloom Filter技术和基于位置查找算法的优点,我们提出一种基于Counting Bloom Filter和物理拓扑的Chord查找算法。首先,Counting Bloom Filter用于数据存储,以减少空间复杂度,然后,用基于物理拓扑的方法,解决物理拓扑和逻辑拓扑不匹配的问题,进一步加快资源定位的速度。实验结果表明,该算法能够进一步节省存储空间并提高查找效率。 3.在路径长度、存储空间、查找跳数方面,将三种方法进行对比,验证两种改进方法各自的优缺点。
[Abstract]:The core idea of Peer-to-Peer (P2P) technology is that all participating nodes are equal in status, each node provides services to other nodes while enjoying services from other nodes. In other words, the technology does not distinguish between client and server. Each node is not only a client or a server, this pattern makes the resources in the Internet widely explored and utilized, and has been widely used in various fields. The biggest challenge of P2P systems is to efficiently query and locate resources without a central server. At present, the research in this area is focused on structured routing algorithms, in which Chord algorithm is simple and easy to implement. Good robustness and expansibility have become the focus of research at home and abroad. First of all, this paper gives a brief overview of the theoretical basis of P2P network, and briefly analyzes the four kinds of topology structure of P2P network. This paper also introduces their classical models, Napstern Gnutella and Kazaa, and then introduces four classical resource lookup algorithms based on distributed hash DHT technology in a fully distributed structured topology. This paper mainly describes the Chord lookup algorithm. One obvious disadvantage of the traditional Chord lookup algorithm is that it does not consider the physical topology of the P2P network, resulting in a large network delay in the lookup process. The problem of storage space is rarely considered. In order to make up for these defects, the research work of this paper is as follows:. 1. Aiming at the mismatch of traditional Chord physical topology and logical topology, combining the advantages of ant optimization algorithm and bidirectional lookup technique, we propose a bidirectional lookup Chord algorithm based on ant optimization algorithm. Ant optimization algorithm is used to establish Chord ring to solve the problem of physical topology and logical topology mismatch. On this basis, bidirectional search method is used to further accelerate the search speed. The experimental results show that, The algorithm is more efficient than the traditional Chord algorithm. 2. Aiming at the problem of physical topology and logical topology mismatch and space complexity, combining the advantages of Counting Bloom Filter technology and location-based search algorithm, We propose a Chord lookup algorithm based on Counting Bloom Filter and physical topology. First, count Bloom Filter is used for data storage to reduce the space complexity. Then, the problem of physical topology and logical topology mismatch is solved by the method based on physical topology. Experimental results show that the proposed algorithm can further save storage space and improve the efficiency of searching. 3. In the aspect of path length, storage space and search hops, the advantages and disadvantages of the two improved methods are verified by comparing the three methods.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.02

【参考文献】