本科毕业论文-—基于dht的p2p研究.doc

《本科毕业论文-—基于dht的p2p研究.doc》由会员分享，可在线阅读，更多相关《本科毕业论文-—基于dht的p2p研究.doc（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、硕士学位论文论文题目基于DHT的P2P研究研究生姓名导师姓名专业论文完成时间毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕

2、业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全

3、了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日指导教师评阅书指导教师评价：一、撰写（设计）过程1、学生在论文（设计）过程中的治学态度、工作精神 优 良 中 及格 不及格2、学生掌握专业知识、技能的扎实程度 优 良 中 及格 不及格3、学生综合运用所学知识和专业技能分析和解决问题的能力 优 良 中 及格 不及格4、研究

4、方法的科学性；技术线路的可行性；设计方案的合理性 优 良 中 及格 不及格5、完成毕业论文（设计）期间的出勤情况 优 良 中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）

5、指导教师： （签名） 单位： （盖章）年 月 日评阅教师评阅书评阅教师评价：一、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格二、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）评阅教师： （签名） 单位： （盖章）年 月 日中国科学技术大

6、学硕士学位论文 摘 要教研室（或答辩小组）及教学系意见教研室（或答辩小组）评价：一、答辩过程1、毕业论文（设计）的基本要点和见解的叙述情况 优 良 中 及格 不及格2、对答辩问题的反应、理解、表达情况 优 良 中 及格 不及格3、学生答辩过程中的精神状态 优 良 中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良

7、中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格评定成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）教研室主任（或答辩小组组长）： （签名）年 月 日教学系意见：系主任： （签名）年 月 日摘要随着个人计算机性能的提高和互连网用户的急剧增长，在网络边缘出现了大量的闲散计算和存储资源，而网络带宽的大幅提高也使得开发和利用这些潜在的计算资源成为可能。如何有效利用这些大量的计算资源已成为一个热点问题，P2P研究正是在这种背景下展开的。P2P中文称为对等网络，是指分布式系统中的各个节点是逻辑对等的，与目前互连网上比较流行的C/S计算模型不同的是：P2P计算模型

8、中不再区分服务器和客户端，系统中的各个节点之间可以直接进行数据通信而不需要通过中间的服务器。P2P可以解决传统的C/S模型下服务器带来的性能瓶颈和单一故障点等问题，能够充分利用互联网边缘所蕴含的潜在计算和存储资源。在大规模的P2P系统中，如何高效地查找到指定的数据是一个非常关键的问题。然而第一代的P2P系统都没有很好地解决这个问题。Napster为了查找音乐文件而配置的目录服务器在用户增多时将成为系统的瓶颈和单一故障点。Gnutella所采用的泛洪查询报文的方法在系统规模扩大时会给网络造成较大的负担，因而同样不具有可扩展性。为了解决P2P系统中可扩展的数据检索问题，国际上几个研究小组独立地提出

9、了Chord、CAN、Pastry和Tapestry等基于DHT的结构化P2P系统。DHT在应用层上把所有的P2P节点组织成一个结构化的重叠网络，文件索引分布其中，查询报文将通过这个重叠网络路由。DHT在节点失效、遭受攻击和突发性高负载面前都能表现出很好的健壮性；它具有良好的可扩展性，能以较低系统开销获得较大的系统规模；可以自我配置，不需要手工干预就可以自动把新加入节点合并到系统中；能提供简单灵活的接口，可以为多个应用同时使用。本文在第2章对DHT系统进行了综述。但是目前DHT还面临许多问题，最大的问题之一就是DHT在初始设计时忽略了参与节点在物理网络上的邻近性，导致重叠网络和物理网络脱节，即

10、DHT未能充分利用底层物理网络的拓扑信息，从而造成实际的寻路效率低下。因为路由算法是DHT的核心，所以提高DHT寻路效率是当前基于DHT的P2P研究的重点，具有很重要的意义。本文围绕DHT寻路效率的改善，对如何提取节点在物理网络上的位置信息和如何利用位置信息构造拓扑敏感(topology-aware)的DHT系统进行了深入的研究，提出了具有层次化标识符的DHT、内嵌式DHT和层次化DHT三种利用拓扑信息改进DHT路由性能的方案，本文通过把Chord改造成Chord6、eChord和hChord来分别阐述这几种方案的思路，并通过仿真和分析阐明了这些方案能有效地改善现有DHT寻路效率。本文在第3章

11、详细介绍了我们的研究成果。DHT具有广阔的应用前景，国际上许多著名的研究机构都在开展基于DHT的大规模P2P系统研制工作。围绕这个方向，在实验室CNGI预研项目基于IPv6的P2P弹性重叠网络智能节点的研制中，我们利用自己提出的Chord6，设计了一个IPv6环境下的文件共享系统FSS6。FSS6不仅可以在实践中检验我们提出的DHT改进方案的有效性，而且还可以充分展示IPv6和P2P技术结合的优越性，推动IPv6的普及发展，加速CNGI的顺利演进；同时，FSS6还将给P2P应用探索一个可运营、可管理和可控制的示范模式，进一步推动P2P应用的良性发展，更好地满足用户需求。本文在第4章详细介绍FS

12、S6的设计。本文的主要工作和创新点如下：1. 提出了从IPv6地址前缀中提取节点位置信息的方法。我们注意到IPv6地址分配的层次性，同一自治域内的主机通常具有一定长度的相同的网络前缀，因而DHT系统中的节点可以从自己的IPv6地址前缀中获取位置信息。IPv6以及P2P系统都是下一代网络中重要的发展方向，本文把两者结合在一起是一个重要的尝试。2. 提出了一种构建层次化节点标识符的方案。我们创造性的提出节点标识符可以分段构造，标识符的前缀可以通过哈希同一个域中节点共同的位置信息得到，从而使得物理网络上临近的节点在重叠网络上也互为近邻。作为示例，本文结合IPv6和Chord，构造了一种改进型的DHT

13、系统Chord6，仅仅对Chord协议做了很小的改动就取得了很好的寻路性能改善，并通过仿真验证了这种方案的有效性。我们指出构建层次化节点标识符的思想完全可以应用于其他的DHT系统中，如CAN和Pastry等。3. 提出了一种构造内嵌式DHT的方案，既改进了寻路效率又保持了原有DHT系统的负载平衡性质。本文创新性的提出把节点的位置信息也存储到DHT系统中，新加入的节点可以通过DHT查询到具有相同位置信息的全部节点列表，从而在物理网络上临近的节点之间构造内嵌于全局DHT中的本地DHT。这样，路由可以先在本地DHT中进行，必要时经由全局DHT，从而避免多次跨域路由。该方案具有完全分布式的特点。作为示

14、例，本文利用这种思想对Chord进行了改进，构造了eChord。仿真的结果证明该方案的有效性。4. 提出了构造层次化DHT的方案，按物理网络的远近把节点划分为多个组，使得节点动态加入和退出的影响局限在单个组中；同时也把关键字分层存储以支持部分查询。初步的分析结果证明这种方案具有良好的部分查询性能。5. 利用我们自己提出的Chord6，设计了一个IPv6环境下的文件共享系统FSS6。关键字：P2P，DHT，Chord，查找，寻路，IPv6，拓扑，层次化，文件共享中国科学技术大学硕士学位论文 AbstractAbstractWith the great improvement of PC perf

15、ormance and the fast growth of Internet users, there emerges a vast quantity of computing and storage resources on the Internet edge. P2P (peer-to-peer) technology can be an effective means to harness these resources, which accounts for the fact that P2P applications are becoming more and more popul

16、ar these days. In a P2P system, all peers are identical regarding functionality. Unlike the traditional C/S (client/server) model, there are no dedicated servers and peers can directly communicate with each other for data transmission. P2P can solve the problems of single point failure and performan

17、ce bottle encountered by C/S model. A fundamental problem that confronts a large-scale P2P system is the efficient location of the node that stores the desired date item. However, the first generation of P2P systems did not address the problem well. Napster has a centralized index server where scala

18、bility can be limited by the machine power and the network bandwidth of the central point. Gnutella employs a messaging mechanism that is based on flooding, which can impose heavy burden on networks and thus compromise its scalability. To address the problem, several research groups independently pr

19、oposed DHT (distributed hash table) systems, which include Chord, CAN, Pastry and Tapestry.DHTs reorganize peers into an overlay in the application level, distribute file indexes into the network, and route queries through the overlay. DHTs are robust in the face of failures, attacks and unexpectedl

20、y high loads. They are scalable, achieving large system sizes without incurring undue overhead. They are self-configuring, automatically incorporating new nodes without manual intervention or oversight. They provide a simple and flexible interface and are simultaneously usable by many applications.H

21、owever, DHTs are still faced with many problems, one of which is the fact that most DHTs do not take into account physical network topology in their original design, thus resulting in high routing latency and low efficiency. Therefore, to improve routing performance is an important direction for res

22、earch on DHT-based P2P. While centering on the issue of routing enhancement, the author has conducted an in-depth research on how to extract topology information and how to utilize that information to construct topology-aware DHT systems. In Chapter 3, we propose three solutions, which are called DH

23、T with hierarchical identifiers, embedded DHT and hierarchical DHT. To illustrate our solutions, we build Chord6, eChord and hChord all upon the original Chord system. Analysis and simulation results prove that our solutions can greatly improve routing efficiency in Chord.Currently, a new generation

24、 of applications has been proposed on top of DHTs. In this paper, we also design a wide-area file-sharing system based on Chord6, validating the effectiveness of our research work on DHT routing enhancement. The major contributions of this paper are listed as follows:1. Propose a novel method to ext

25、ract topology information from IPv6 address prefixes. We notice that IPv6 addresses are assigned in a hierarchical way so that nodes with the same prefix are in the same autonomous domain. Therefore peers in a DHT system can learn their location information from their own IPv6 addresses.2. Devise a

26、smart scheme to exploit the IPv6 address hierarchical feature, so as to construct an efficient version of Chord dubbed Chord6. We propose that node identifiers can be divided into several parts and thus be produced separately. For a node identifier divided into two parts, the higher bits can be obta

27、ined by hashing the shared address prefix among all nodes within the same AS, and the lower bits are the hash result of the rest of the IPv6 address. As a result, topologically close peers shall also be adjacent in the overlay. An important advantage of our scheme is that it is very simple and barel

28、y modifies the original Chord. Simulation results have shown that our method can significantly reduce inter-domain traffic that causes the long routing latency.3. Devise a novel scheme to construct embedded DHT, which can not only improve the routing efficiency, but also inherit the load-balancing f

29、eature of the original DHT. First, nodes independently insert their location information into DHT systems as they do with file indexes. Then, a newly joined node can utilize DHT to get a complete list of all nodes that are close to it in the underlying physical networks. Finally, nodes within the sa

30、me domains are organized into many local DHTs which are then embedded into a global DHT comprised of all nodes. Thus, routing can be conducted in local DHTs first, and pass through each other (if necessary) with the aid of the global DHT, which means that inter-domain traffic can be minimized to the

31、 extreme. To illustrate the feasibility and effectiveness of the scheme, we construct eChord upon the original Chord system. Analysis and simulation demonstrate that our scheme is very effective.4. Propose a new kind of hierarchical DHT dubbed hChord, in which topologically close nodes are grouped i

32、n the overlay and keys are stored in a hierarchical way. Analysis show that hChord can isolate the effect of dynamic nodes within small groups for better scalability and stability, and show improved performance with partial queries. 5. Present a prototype design of an IPv6-based wide-area file shari

33、ng system based on Chord6.Keywords：P2P，DHT，Chord，look up, routing，IPv6，topology，hierarchical, file sharing中国科学技术大学硕士学位论文 目录目录摘要IAbstractIII目录V第1章 序论1.1 P2P研究背景1.2 什么是P2P1.3 为什么需要P2P1.4 P2P的应用领域1.4.1 信息共享1.4.2 实时通信1.4.3 网络游戏1.4.4 金融服务1.4.5 信息检索1.4.6 协同工作1.4.7 普及计算1.4.8 网络存储1.5 如何实现P2P1.5.1 基于目录服务器P2P

34、1.5.2 非结构化P2P1.5.3 结构化P2P1.6 本章小结第2章 DHT基本原理2.1 引言2.2 Chord2.2.1 Chord的设计2.2.2 Chord的路由2.2.3节点加入和退出2.3 Pastry2.3.1 Pastry的设计2.3.2 Pastry的路由2.3.3 节点加入和退出2.4 CAN2.4.1 CAN的设计2.4.2 CAN的路由2.4.3 节点加入和退出2.5 Tapestry2.5.1 Tapestry的设计2.5.2 Tapestry的路由2.5.3 节点加入和退出2.6 本章小结第3章 利用拓扑信息改进DHT3.1 引言3.2 获取位置信息3.2.1

35、分布式网络测量技术3.2.2 IP地址蕴涵拓扑信息3.3具有层次化标识符的DHT3.3.1 Chord6的设计3.3.2 分析与仿真3.3.3 小结和进一步讨论3.4 内嵌式DHT3.4.1 eChord的设计3.4.2 eChord的路由3.4.3 节点的加入和退出3.4.4 分析与仿真3.4.5 小结和进一步讨论3.5层次化DHT3.5.1 hChord的设计3.5.2性能评估和进一步的讨论3.5.3 结语和未来工作3.6 本章小结第4章 基于DHT的P2P系统设计与实现4.1 FSS64.1.1 设计目标4.1.2 系统结构4.1.3 Chord6实现4.1.4 智能节点设计4.1.5

36、消息处理4.2 相关的研究4.2.1 CFS4.2.2 PAST4.2.3 OceanStore4.3 本章小结第5章 结束语攻读硕士期间发表的论文致谢缩略语索引参考文献中国科学技术大学硕士学位论文 第1章 序论第1章 序论1.1 P2P研究背景正如摩尔定律所指，“每十八个月处理器性能提高一倍，而价格降低一半”，在个人计算机的计算性能和存储容量得到极大提高的同时，计算机的低廉价格也让其使用越来越广泛。同时，随着近年来计算机通信技术的飞速发展，大量的个人计算机接入Internet，从而导致Internet规模不断扩大，Internet入网的主机数、上网的人数都在飞速增长。图1.1给出的是从199

37、1年到2004年Internet入网主机数的增长曲线【1】。图1.2给出了在线用户数统计【2】。图1.1 1991年到2004年Internet主机数增长曲线【1】(单位：百万)图 1.2Internet全球在线用户数变化趋势【2】另外，接入Internet的设备也变的多样化，不仅有大型机、PC机，而且有越来越多的像手机和PDA这样具有计算能力的手持终端设备。很明显，网络边缘分布着大量的计算和存储资源。但是，在传统的C/S (Client/Server, 客户/服务器)模式下，这些资源没有能够得到很好的开发和利用。因而，如何有效地利用这些计算和存储资源也随之成为研究的热点。P2P（Peer t

38、o Peer，对等网络）技术出现的目的就是希望充分利用互联网中所蕴含的潜在计算和存储资源。1.2 什么是P2PP2P中文称为对等网络，是指分布式系统中的各个节点是逻辑对等的，与目前互连网上比较流行的C/S计算模型不同的是：P2P计算模型中不再区别服务器以及客户端，系统中的各个节点之间可以直接进行数据通信而不需要通过中间的服务器。也就是说，对等网络中每个节点的地位是对等的，既可充当服务器为其它节点服务，也可充当客户机消费其它节点提供的服务。如图1.3所示，P2P构建了一种完全分散式的网络结构，不同于C/S的集中模式。 图1.3(a) C/S模式网络 图1.3(b) P2P模式网络P2P大体又可分

39、为两种类型。一种是配置了管理服务器的混和型P2P，如图1.4(a)所示。这里的服务器并不提供传统的数据服务，它主要是对节点间的通信进行控制和管理，节点在服务器的帮助下相互之间进行数据通信。目前流行的P2P软件如Napster【3】和BitTorrent【4】等基本上都属于混和型P2P。混合型P2P易于导入用户认证、安全、和计费功能，但是由于管理服务器的存在，仍然面临着单点故障和扩展性问题。另一种则是不引入任何服务器的完全对等的纯P2P结构，如图1.4(b)所示。纯P2P完全是自组织的，节点之间直接进行数据交换。 图1.4 (a) 混和型P2P架构 图1.4 (b) 纯P2P架构1.3 为什么需

40、要P2PP2P技术引起人们的热切关注起源于Napster，Gnutella【5】等P2P文件共享软件的迅速推广。这些应用在满足人们快速交换大容量数据的需求的同时，也使得研究人员意识到P2P技术具有的独特优势，可以利用它来解决传统C/S模式存在的弊端。在传统的C/S方式下，由服务器向众多的客户机提供服务，这样做的潜在前提是：假定服务器拥有强大的处理能力、高速网络接口和大容量的存储空间；与此对应，客户机的处理能力通常被认为比较弱小，基本上只是一个高性能的I/O设备。然而，今天计算机和网络的飞速发展使得上面的假设出现了问题。第一，如1.1节指出，作为客户机的联网主机和用户数目都在飞速增长；同时，网络

41、中要存储和处理的数据也极为惊人，例如Internet上每年产生的网页数据高达21018字节【6】。这两者都服务器提出了巨大的挑战。无论服务器性能多么优越，它的存储容量都是有限的，硬盘读写速度和网络接口都有一定的限制，CPU处理能力也只能满足一定的要求。随着客户机的增多，服务能力和质量必然会下降。因而面对今天数目巨大的用户以及海量信息处理要求，简单的C/S模式已经不能满足需要。也就是说，服务器负载过重，可能会成为瓶颈。第二，作为客户机的个人计算机存储和计算能力大为增加，例如今天的主流PC机配置，CPU主频大都达到12GHZ，内存512M左右，硬盘动辄就是40G或80G，而LAN或宽带网络接口都有

42、10M或100M。用户主机已经不再是一个简单的I/O设备，再加上网络带宽的提高，用户之间完全有能力进行共享和协作。另外，随着社会和网络的发展，人们对数据存储和传输、高性能计算等也有着迫切的需求，用户希望直接交换信息和数据而不必经由特定的服务器中转。然而，C/S模式无法利用客户端的闲置资源，同时也增加了中转服务成本，给用户节点直接通信带来了不便。P2P技术避免了C/S结构带来的单点失效和性能瓶颈等问题，它不依赖或尽可能不依赖中央服务器，使得每个参与节点既能作为服务器，也可成为客户机。P2P技术的核心思想就是将网络应用的重心从中央服务器向网络边缘的终端设备扩散；这些终端设备可以是高性能计算机，可以

43、是PC机，可以是手机，也可以是PDA等等。与C/S模式相比，P2P模式有以下一些主要优点：（1） 信息在用户节点间直接流动，高速、及时、方便，降低了中转服务成本。（2） 资源的高度利用率。在P2P网络上，闲散资源有机会得到利用，所有节点的资源总和构成了整个网络的资源，整个网络可以被用作具有海量存储能力和巨大计算处理能力的超级计算机。（3） 随着节点的增加，C/S模式下服务器的负载会越来越重，将成为系统的瓶颈和单一故障点。也就是说，一旦服务器崩溃，整个网络也随之瘫痪。而在P2P网络中，每个节点都向网络贡献些资源，如存储空间、CPU周期等。所以，对等节点越多，网络的可靠性也就越高。（4） 基于内容的寻址方式处于一个更高的语义层次，因为用户在搜索时只需指定具有实际意义的信息标识而不是物理地址。这将创造一个更加精炼的信息仓库和一个更加统一的资源标识方法。（5） C/S 模式下的互联网是完全依赖于中心点 服务器的。没有服务器，网络就没有任何意义。而P2P 网络中，即使只有一个对等点存在