【作者】 杨波；

【导师】 宋俊德；

【作者基本信息】 北京邮电大学 ， 计算机应用技术， 2010， 硕士

【摘要】 P2P (Peer to Peer)网络模型凭借其低廉的部署费用和丰富的共享资源等优势,迅速地在互联网上流行起来。P2P网络中完全地抛开了服务器的存在,资源分布地存储在整个网络当中,因此资源发现算法毫无疑问地成为了P2P网络的核心。现有的资源发现算法可分为三类：集中目录式P2P中的目录机制、非结构化P2P中的泛洪机制和结构化P2P中的DHT机制。此三类算法都存在着制约P2P网络大规模发展的缺点：目录机制由于没有完全脱离服务器的概念而保留了一部分“客户/服务器”模式的缺点,如服务器瓶颈问题；泛洪机制由于产生大量的冗余流量而造成效率低下问题；DHT机制完全忽略节点的物理位置信息从而造成物理层和逻辑层失配问题,同时由于DHT机制较高的算法复杂度使得使用DHT的P2P网络的可扩展性受到制约。因此本文的研究意义在于提出新的资源查找算法以提高P2P网络的资源发现效率和可扩展性。本文在分析和研究现有的各种P2P资源发现算法的基础上,总结各自的优缺点,并且提出了一种基于混合结构化P2P网络的资源发现算法——Lerd (Location-aware Effective Resource Discovery).该算法的核心思想在于：将网络中的节点按照性能、稳定度等指标划分为超级节点和普通节点两类；并依据物理位置将整个网络划分为若干个区域并且分配相应的区域标识符,每个区域由一个超级节点来管理；普通节点使用物理位置感知方法在加入网络时充分考虑其物理位置信息,从而选择距离自己最近的区域加入,以此解决物理层和逻辑层失配的问题；在节点和资源的标识符中加入区域信息,资源发现的过程中依据该区域信息将资源直接定位到区域,进一步再定位到该区域的某个节点,从而将资源发现算法的复杂度控制在常数级别,即O(1)。在对算法进行验证时使用了NS2仿真软件。首先使用C++语言对算法实现了编码,再将该算法加入到NS2的协议库中,最后针对不同的网络规模做了一系列的仿真验证。本文中以查找路由跳数和查找迟延时间作为度量对仿真结果的分析,并且分别与非结构化P2P和结构化P2P中具有代表性的资源发现算法Flooding和Chord进行对比。经过对比分析,在网络规模不断增大的情况下,Lerd算法的路由跳数和查找迟延时间明显低于Flooding和Chord算法。其中路由跳数为一个位于[4,6]区间的常数,查找迟延呈平缓增长趋势,因此该算法达到了提高资源发现效率和网络可扩展性的目的。更多还原

【Abstract】 P2P (Peer to Peer) network model, with low deployment costs and abundant resources, is more and more popular on the internet. In P2P network, all resources are stored dispersedly in the users’ computers (peers), and shared among peers without the intervention of servers. Thus, the resource discovery algorithm is the core of the P2P network. The existing resource discovery algorithms can be divided into three categories:Directory mechanism in centralized directory-based P2P, Flooding mechanism in unstructured P2P and DHT based mechanism in structured P2P. However, all of them have some shortages which restricted the large-scale development of P2P. Directory mechanism have not laid server aside completely, so it remains some shortages of Client/Server model, such as the bottlenecks of the server. Flooding mechanism is inefficiencies because it generates a lot of redundancy traffic. DHT mechanism does not consider the physical information of the peers during the mapping physical topology to logical topology, so the physical topology and logical topology are mismatched. On the other hand, the resource discovery algorithms are complicated in structural P2P, so its scalability is so limited. The meaning of this paper is to propose a new resource discovery algorithm to improve the efficiency of resource discovery and the scalability of P2P networks.In this paper, by analyzing and studying various existing P2P resource discovery algorithms, the author summarized advantages and disadvantages of these algorithms and then proposes a resource discovery algorithm based on hybrid structured P2P networks-Lerd (Location-aware Effective Resource Discovery). The core idea of the algorithm is that, by considering the performance, stability, and other indicators of peers, all peers are divided into two levels:super peers and normal peers. In accordance with physical location, divide the whole network into several domains and then allocate the corresponding regional identifier to each domain. Each domain is managed by a super peer. When a new peer wants to join the network, it will use the physical location-aware technique to calculate its physical location, and then choose the nearest domain to join. Thus the topology mismatch problem can be resolved. We mix domain information into both of the node and the resource identifier, so that we can use this domain information to locate the resource during the resource discovery. By using this mechanism, we can limit the complex of the resource discover algorithm as a constant, O (1). To verify the algorithm, NS2 (Network Simulator 2) is used. Firstly, code this new algorithm by using C++. Secondly, add it into the protocol library of NS2 and compile NS2. Finally, a series of simulation is taken in different scale of network.In this paper, hops and time delay in resource discovery message routing are used as metric to analyze the simulation result. We compare the result with Flooding and Chord algorithm, which is the typical algorithm of unstructured P2P and structured P2P respectively. The analyze result show that the hops and time delay of Lerd is markedly lower than Flooding and Chord while the scale of network is growing. The hops of the resource discovery are limited as a constant between 4 and 6. The time delay is increasing slowly. As a result, Lerd algorithm achieves the aim of improving the efficiency of resource discovery and network scalability.更多还原