通信与信息系统专业硕士学位论文：基于DHT的P2P研究(word档，58页，可编辑.doc

硕士学位论文论文题目基于DHT的P2P研究研究生姓名导师姓名教授专业通信与信息系统论文完成时间2005年5月中国科学技术大学硕士学位论文 摘 要摘要随着个人计算机性能的提高和互连网用户的急剧增长，在网络边缘出现了大量的闲散计算和存储资源，而网络带宽的大幅提高也使得开发和利用这些潜在的计算资源成为可能。如何有效利用这些大量的计算资源已成为一个热点问题，P2P研究正是在这种背景下展开的。P2P中文称为对等网络，是指分布式系统中的各个节点是逻辑对等的，与目前互连网上比较流行的C/S计算模型不同的是：P2P计算模型中不再区分服务器和客户端，系统中的各个节点之间可以直接进行数据通信而不需要通过中间的服务器。P2P可以解决传统的C/S模型下服务器带来的性能瓶颈和单一故障点等问题，能够充分利用互联网边缘所蕴含的潜在计算和存储资源。在大规模的P2P系统中，如何高效地查找到指定的数据是一个非常关键的问题。然而第一代的P2P系统都没有很好地解决这个问题。Napster为了查找音乐文件而配置的目录服务器在用户增多时将成为系统的瓶颈和单一故障点。Gnutella所采用的泛洪查询报文的方法在系统规模扩大时会给网络造成较大的负担，因而同样不具有可扩展性。为了解决P2P系统中可扩展的数据检索问题，国际上几个研究小组独立地提出了Chord、CAN、Pastry和Tapestry等基于DHT的结构化P2P系统。DHT在应用层上把所有的P2P节点组织成一个结构化的重叠网络，文件索引分布其中，查询报文将通过这个重叠网络路由。DHT在节点失效、遭受攻击和突发性高负载面前都能表现出很好的健壮性；它具有良好的可扩展性，能以较低系统开销获得较大的系统规模；可以自我配置，不需要手工干预就可以自动把新加入节点合并到系统中；能提供简单灵活的接口，可以为多个应用同时使用。本文在第2章对DHT系统进行了综述。但是目前DHT还面临许多问题，最大的问题之一就是DHT在初始设计时忽略了参与节点在物理网络上的邻近性，导致重叠网络和物理网络脱节，即DHT未能充分利用底层物理网络的拓扑信息，从而造成实际的寻路效率低下。因为路由算法是DHT的核心，所以提高DHT寻路效率是当前基于DHT的P2P研究的重点，具有很重要的意义。本文围绕DHT寻路效率的改善，对如何提取节点在物理网络上的位置信息和如何利用位置信息构造拓扑敏感(topology-aware)的DHT系统进行了深入的研究，提出了具有层次化标识符的DHT、内嵌式DHT和层次化DHT三种利用拓扑信息改进DHT路由性能的方案，本文通过把Chord改造成Chord6、eChord和hChord来分别阐述这几种方案的思路，并通过仿真和分析阐明了这些方案能有效地改善现有DHT寻路效率。本文在第3章详细介绍了我们的研究成果。DHT具有广阔的应用前景，国际上许多著名的研究机构都在开展基于DHT的大规模P2P系统研制工作。围绕这个方向，在实验室CNGI预研项目基于IPv6的P2P弹性重叠网络智能节点的研制中，我们利用自己提出的Chord6，设计了一个IPv6环境下的文件共享系统FSS6。FSS6不仅可以在实践中检验我们提出的DHT改进方案的有效性，而且还可以充分展示IPv6和P2P技术结合的优越性，推动IPv6的普及发展，加速CNGI的顺利演进；同时，FSS6还将给P2P应用探索一个可运营、可管理和可控制的示范模式，进一步推动P2P应用的良性发展，更好地满足用户需求。本文在第4章详细介绍FSS6的设计。本文的主要工作和创新点如下：1. 提出了从IPv6地址前缀中提取节点位置信息的方法。我们注意到IPv6地址分配的层次性，同一自治域内的主机通常具有一定长度的相同的网络前缀，因而DHT系统中的节点可以从自己的IPv6地址前缀中获取位置信息。IPv6以及P2P系统都是下一代网络中重要的发展方向，本文把两者结合在一起是一个重要的尝试。2. 提出了一种构建层次化节点标识符的方案。我们创造性的提出节点标识符可以分段构造，标识符的前缀可以通过哈希同一个域中节点共同的位置信息得到，从而使得物理网络上临近的节点在重叠网络上也互为近邻。作为示例，本文结合IPv6和Chord，构造了一种改进型的DHT系统Chord6，仅仅对Chord协议做了很小的改动就取得了很好的寻路性能改善，并通过仿真验证了这种方案的有效性。我们指出构建层次化节点标识符的思想完全可以应用于其他的DHT系统中，如CAN和Pastry等。3. 提出了一种构造内嵌式DHT的方案，既改进了寻路效率又保持了原有DHT系统的负载平衡性质。本文创新性的提出把节点的位置信息也存储到DHT系统中，新加入的节点可以通过DHT查询到具有相同位置信息的全部节点列表，从而在物理网络上临近的节点之间构造内嵌于全局DHT中的本地DHT。这样，路由可以先在本地DHT中进行，必要时经由全局DHT，从而避免多次跨域路由。该方案具有完全分布式的特点。作为示例，本文利用这种思想对Chord进行了改进，构造了eChord。仿真的结果证明该方案的有效性。4. 提出了构造层次化DHT的方案，按物理网络的远近把节点划分为多个组，使得节点动态加入和退出的影响局限在单个组中；同时也把关键字分层存储以支持部分查询。初步的分析结果证明这种方案具有良好的部分查询性能。5. 利用我们自己提出的Chord6，设计了一个IPv6环境下的文件共享系统FSS6。关键字：P2P，DHT，Chord，查找，寻路，IPv6，拓扑，层次化，文件共享中国科学技术大学硕士学位论文 AbstractAbstractWith the great improvement of PC performance 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 popular 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 performance 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 scalability 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 proposed 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 unexpectedly 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.However, 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 research 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 DHT 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 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 extract 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 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 obtained 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 barely 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 feature 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 same 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 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 in 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 sharing 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 基于目录服务器P2P1.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 分布式网络测量技术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 消息处理4.2 相关的研究4.2.1 CFS4.2.2 PAST4.2.3 OceanStore4.3 本章小结第5章 结束语攻读硕士期间发表的论文致谢缩略语索引参考文献中国科学技术大学硕士学位论文 第1章 序论第1章 序论1.1 P2P研究背景正如摩尔定律所指，“每十八个月处理器性能提高一倍，而价格降低一半”，在个人计算机的计算性能和存储容量得到极大提高的同时，计算机的低廉价格也让其使用越来越广泛。同时，随着近年来计算机通信技术的飞速发展，大量的个人计算机接入Internet，从而导致Internet规模不断扩大，Internet入网的主机数、上网的人数都在飞速增长。图1.1给出的是从1991年到2004年Internet入网主机数的增长曲线【1】。图1.2给出了在线用户数统计【2】。图1.1 1991年到2004年Internet主机数增长曲线【1】(单位：百万)图 1.2Internet全球在线用户数变化趋势【2】另外，接入Internet的设备也变的多样化，不仅有大型机、PC机，而且有越来越多的像手机和PDA这样具有计算能力的手持终端设备。很明显，网络边缘分布着大量的计算和存储资源。但是，在传统的C/S (Client/Server, 客户/服务器)模式下，这些资源没有能够得到很好的开发和利用。因而，如何有效地利用这些计算和存储资源也随之成为研究的热点。P2P（Peer to Peer，对等网络）技术出现的目的就是希望充分利用互联网中所蕴含的潜在计算和存储资源。1.2 什么是P2PP2P中文称为对等网络，是指分布式系统中的各个节点是逻辑对等的，与目前互连网上比较流行的C/S计算模型不同的是：P2P计算模型中不再区别服务器以及客户端，系统中的各个节点之间可以直接进行数据通信而不需要通过中间的服务器。也就是说，对等网络中每个节点的地位是对等的，既可充当服务器为其它节点服务，也可充当客户机消费其它节点提供的服务。如图1.3所示，P2P构建了一种完全分散式的网络结构，不同于C/S的集中模式。 图1.3(a) C/S模式网络 图1.3(b) P2P模式网络P2P大体又可分为两种类型。一种是配置了管理服务器的混和型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 为什么需要P2PP2P技术引起人们的热切关注起源于Napster，Gnutella【5】等P2P文件共享软件的迅速推广。这些应用在满足人们快速交换大容量数据的需求的同时，也使得研究人员意识到P2P技术具有的独特优势，可以利用它来解决传统C/S模式存在的弊端。在传统的C/S方式下，由服务器向众多的客户机提供服务，这样做的潜在前提是：假定服务器拥有强大的处理能力、高速网络接口和大容量的存储空间；与此对应，客户机的处理能力通常被认为比较弱小，基本上只是一个高性能的I/O设备。然而，今天计算机和网络的飞速发展使得上面的假设出现了问题。第一，如1.1节指出，作为客户机的联网主机和用户数目都在飞速增长；同时，网络中要存储和处理的数据也极为惊人，例如Internet上每年产生的网页数据高达21018字节【6】。这两者都服务器提出了巨大的挑战。无论服务器性能多么优越，它的存储容量都是有限的，硬盘读写速度和网络接口都有一定的限制，CPU处理能力也只能满足一定的要求。随着客户机的增多，服务能力和质量必然会下降。因而面对今天数目巨大的用户以及海量信息处理要求，简单的C/S模式已经不能满足需要。也就是说，服务器负载过重，可能会成为瓶颈。第二，作为客户机的个人计算机存储和计算能力大为增加，例如今天的主流PC机配置，CPU主频大都达到12GHZ，内存512M左右，硬盘动辄就是40G或80G，而LAN或宽带网络接口都有10M或100M。用户主机已经不再是一个简单的I/O设备，再加上网络带宽的提高，用户之间完全有能力进行共享和协作。另外，随着社会和网络的发展，人们对数据存储和传输、高性能计算等也有着迫切的需求，用户希望直接交换信息和数据而不必经由特定的服务器中转。然而，C/S模式无法利用客户端的闲置资源，同时也增加了中转服务成本，给用户节点直接通信带来了不便。P2P技术避免了C/S结构带来的单点失效和性能瓶颈等问题，它不依赖或尽可能不依赖中央服务器，使得每个参与节点既能作为服务器，也可成为客户机。P2P技术的核心思想就是将网络应用的重心从中央服务器向网络边缘的终端设备扩散；这些终端设备可以是高性能计算机，可以是PC机，可以是手机，也可以是PDA等等。与C/S模式相比，P2P模式有以下一些主要优点：（1） 信息在用户节点间直接流动，高速、及时、方便，降低了中转服务成本。（2） 资源的高度利用率。在P2P网络上，闲散资源有机会得到利用，所有节点的资源总和构成了整个网络的资源，整个网络可以被用作具有海量存储能力和巨大计算处理能力的超级计算机。（3） 随着节点的增加，C/S模式下服务器的负载会越来越重，将成为系统的瓶颈和单一故障点。也就是说，一旦服务器崩溃，整个网络也随之瘫痪。而在P2P网络中，每个节点都向网络贡献些资源，如存储空间、CPU周期等。所以，对等节点越多，网络的可靠性也就越高。（4） 基于内容的寻址方式处于一个更高的语义层次，因为用户在搜索时只需指定具有实际意义的信息标识而不是物理地址。这将创造一个更加精炼的信息仓库和一个更加统一的资源标识方法。（5） C/S 模式下的互联网是完全依赖于中心点 服务器的。没有服务器，网络就没有任何意义。而P2P 网络中，即使只有一个对等点存在，网络也是活动的，节点可以随意地将自己的信息发布到网络上。P2P模式的出现也使得Internet恢复了初始设计的面貌：Internet本身是跨越全球的一个非集中式结构的系统，但是上世纪九十年代在Internet上建立的许多应用系统都是完全集中式的，从而改变了Internet设计的初衷。网络技术的飞速发展与迅速普及使Internet成为数据通信的重要手段，网络的发展大大超出了网络的提出者以及早期的建立者的构想。网络规模越来越大，连入网络中的设备以及计算单元的数量和种类也越来越多，然而这些设备以及计算单元并没有得到充分的利用，如果能够将这些设备以及计算单元的处理器计算能力、磁盘存储能力以及网络带宽资源等进行充分利用将会有效缓解目前互联网所面临的一些问题。1.4 P2P的应用领域P2P计算技术具有广阔的应用前景，主要应用的领域包括：信息共享、实时通信、网络游戏、金融服务、信息检索、协同工作、普及计算和网络存储等。【7】1.4.1 信息共享信息共享一直是网络技术发展的重要推动力，也是P2P技术中最典型的应用。目前人们主要采用Web技术来实现信息资源共享，在基于Web的方式进行信息资源共享时，Web 服务器被用来对大量用户的访问提供有效的服务，因而也经常成为这类系统的性能瓶颈所在。采用P2P技术来共享信息资源可以更加充分的利用网络中的带宽资源，从而提高了系统数据通信的效率。目前有很多研究项目和应用软件都是针对P2P的文件共享的，包括Freenet【8】、Gnutella、Free Haven【9】、Ohaha【10】、BitTorrent、Kazza【11】、eDonkey【12】等。1.4.2 实时通信实时通信技术是网络中重要的通信技术，成功的实时通信技术吸引了数以万计的在线用户。目前的实时通信技术一般采用一个中心服务器控制用户的认证等基本信息，节点之间直接进行数据通信。ICQ、OICQ、AIM，MSN等是典型的实时通信系统，这些系统也包含好友列表等基本功能。目前流行的Skype是完全采用P2P技术的即时通信工具。Jabber【13】是一个开放源码的实时通信平台。1.4.3 网络游戏宽带网络游戏对于带宽的消耗是比较多的，通过P2P技术，一方面是可以下载游戏场景，另一方面可以省却一些昂贵的游戏服务器。游戏用户之间，可以直接通信，而不需要通过游戏服务器进行转发。1.4.4 金融服务由于P2P的沟通只单纯涉及沟通的双方，不会有第三者知道双方沟通的信息，所以P2P非常适合发展在线金融服务。美国的Billpoint公司已将P2P技术应用于电子商务的付费机制，通过eBay（一个有名的在线拍卖网站）向全球35个国家的使用者提供了这种技术，他们可直接用彼此的信用卡进行交易；1.4.5 信息检索搜索引擎是目前人们在网络中检索信息资源的主要工具，目前的搜索引擎如：Google【14】、天网【15】等都是集中式的搜索引擎，人们在需要搜索信息的时候要向服务器发出指令，由服务器把检索出来的相关目录通过一定的排序法则呈现在用户面前，这就会不可避免的带来一些问题，比如：如果服务器信息更新周期长，将有大量过时的信息产生；如何服务器不加鉴别、只是一味的搜集信息，将带来许多无价值的垃圾信息；受设备条件影响，服务器收集的信息有限；受服务器制约，存在单点失效的问题等。而P2P将以用户为中心，所有的用户都是平等的伙伴。所有人都共享了他们认为最有价值的东西，这将使互联网上信息的价值得到极大的提升。JXTA Search【16】采用P2P的搜索技术来有效的跟踪数据的更新速度、提高访问的有效性以及检索的效率。Pandango【17】搜索引擎也利用了P2P的技术。1.4.6 协同工作协同工作是指多个用户之间利用网络中的协同计算平台互相协同来共同完成计算任务。通过采用P2P计算技术个人和组织可以随时采用各种方式建立在线、非在线的协同应用环境。同工作使得在不同地点的参与者可以在一起工作，因为采用文件直接共享的方式可以保证系统中的每个人所获得的信息总是最新的，同时节省了采用单独服务器时对该服务器存储以及性能的要求。Groove【18】是基于Internet的P2P协同应用软件的典型代表，其用户可以直接进行实时的协同工作。1.4.7 普及计算普及计算技术研究的是如何充分利用网络中各种各样的计算单元来共同完成大规模的计算任务。由于单一计算单元的计算能力总是有限的，因此人们一般采用并行技术、分布式技术将多个计算单元节点联合起来共同完成大规模的计算任务，同时目前网络中的计算机的计算能力一直利用的不是很充分，人们期望能够充分利用网络中的闲散计算能力来完成大规模的计算任务，这样将会使得网络中所蕴含的海量计算能力得到更加充分的利用。P2P计算技术则为普及计算技术的发展提供了新的机遇。SETIhome【19】是UC Berkeley大学启动的普及计算的研究项目，目前大约吸引了一百万台计算机参与研究。GRID【20】是研究普及计算的典型代表。1.4.8 网络存储存储技术一直是人们所关注的一项技术。由于网络规模的扩大，人们对网络的使用也变得十分灵活，人们开始将传统的分布式操作系统、局域存储技术向基于Internet的文件存储系统发展。一些研究项目开始使用基于DHT的P2P技术来组织和存储文件，典型的系统包括：Oceanstore【21】、Farsite【22】等。这些项目的目标都是提供面向全球规模的文件存储服务。1.5 如何实现P2P让对等节点之间进行数据通信，本身不是难点，完全可以通过现有的网络编程技术实现，而如何穿越NAT（Network Address Translater）和防火墙也只是一些技术细节问题。P2P实现的难点在于提供一种对网络中的海量数据进行高效并且可扩展的管理和检索机制。也就是说，如何在庞大的共享数据海洋中有效而快速的查找到感兴趣的文件或服务。依据文件的检索模型和机制，现有的P2P实现可以分为三种类型。它们分别是：基于目录服务器P2P，非结构化P2P，和结构化P2P。1.5.1 基于目录服务器P2P这一类系统中设置目录服务器，用于保存用户节点的地址信息和该节点上共享文件的描述信息，文件本身是分散存贮在各个节点上的，实际的文件传输也是在对等节点之间进行，目录服务器仅仅起到中介作用，为节点提供发布和查询文件索引服务，是文件索引的集散地，即在请求服务节点和提供服务节点之间进行匹配。图1.5 Napster系统结构Napster是该类系统的典型代表，它的工作过程很简单，如图1.5所示：用户连接到Napster服务器，向服务器递交欲查找的音乐信息（如歌曲名）和自己的IP地址；然后由服务器查找其维护的索引信息库，找到后把存有该音乐文件的其他用户节点的IP地址返回给这个用户；用户依据这些IP地址，选择从其中某些用户主机上下载文件。如用户想要共享本机上的某个音乐文件，只需向服务器登记该文件名和自己的IP地址等信息即可。基于目录服务器的P2P系统在查找目录的时候，简单高效，但由于依赖集中式的目录服务器，随着用户节点数目的增加，服务器将遭遇瓶颈问题，而且会成为系统的单一故障点，系统的可扩展性差。Napster也因为存在目录服务器才卷入了法律纠纷，面临被关闭的处境。1.5.2 非结构化P2P鉴于集中式目录服务器不仅可能成为系统的瓶颈，而且还可能引发法律纠纷。以Gnutella（见图1.6）为代表的非结构化P2P系统中，文件索引信息不再由集中式的目录服务器存储和管理，而是分散到网络中，由节点自己保存。该类系统采用分布式的索引查找策略。为了查找网络中的文件，节点要随机地维护网络中的其他一些节点作为邻居，以便通过邻居节点广播查询报文。由于P2P网络中存在大量的数据冗余，因而可以通过限制查询报文的TTL值来使得泛洪仅仅发生在P2P网络的局部。图1.6 Gnutella系统结构非结构化P2P系统中由于不存在目录服务器，所以没有单点瓶颈问题，不存在单一故障点。然而其缺点也是明显的：在网络中广播查询报文加重了网络通信负担，其查询机制在系统规模扩大时不具有可扩展性。另外，由于查询报文被限制在特定的范围内，所以并不能保证一定可以找到网络中存在的目的数据。1.5.3 结构化P2P上面介绍的两类P2P系统都缺乏有效的、可扩展的索引查找机制。为此，近年来许多研究小组在设计可扩展的查找机制方面做了大量的研究工作，提出了Chord【23】、Pastry【24】、CAN【25】和Tapestry【26】等用于构建结构化P2P的分布式哈希表系统（Distributed Hash Table，DHT）。DHT的主要思想是：首先，每条文件索引被表示成一个(K, V)对，K称为关键字，可以是文件名（或文件的其他描述信息）的哈希值，V是实际存储文件的节点的IP地址（或节点的其他描述信息）。所有的文件索引条目(即所有的（K, V）对)组成一张大的文件索引哈希表，只要输入目标文件的K值，就可以从这张表中查出所有存储该文件的节点地址。然后，再将上面的大文件哈希表分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节点上，使得每个节点负责维护其中的一块。这样，节点查询文件时，只要把查询报文路由到相应的节点即可（该节点维护的哈希表分块中含有要查找的(K,V)对）。这里面有个很重要的问题，就是节点要按照一定的规则来分割整体的哈希表，进而也就决定了节点要维护特定的邻居节点，以便路由能顺利进行。这个规则因具体系统的不同而不同，CAN，Chord，Pastry和Tapestry都有自己的规则，也就呈现出不同的特性。本文将在第二章中介绍这几种DHT系统。图1.7 分布式哈希表图1.7给出了一个分布式哈希表的示意图，可以看到每个节点都维护了哈希表的一部分。DHT实际上是把网络中所有的参与节点按特定的规则在应用层重新进行组织，形成了一个结构化的逻辑的重叠网络（Overlay）。这类系统不存在单点瓶颈问题，因为每个节点除了既是客户又是数据服务器外，还提供目录服务器的功能。又因为邻居节点是有目的有规则建立的，所以DHT不需要在网络中泛洪查询报文，而是按照相应的路由规则在系统中转发报文。DHT在节点失效、遭受攻击和突发性高负载面前都能表现出很好的健壮性；它具有良好的可扩展性，能以较低系统开销获得较大的系统规模；可以自我配置，不需要手工干预就可以自动把新加入节点合并到系统中；能提供简单灵活的接口，可以为多个应用同时使用。但是目前DHT还面临许多问题，Sylvia Ratnasamy 等人在总结现有的DHT路由算法的基础之上【27】提出了结构化对等网络面临着十五个主要问题。其中指出提高DHT路由效率是基于DHT的P2P研究的重点，而P2P路由性能直接影响P2P应用的推广。本文将在第三章中介绍作者围绕这个方向所做的工作。1.6 本章小结本章首先介绍了P2P研究的背景，即联网的主机数和用户增加使得网络边缘分布了大量的潜在计算和存储资源，P2P研究正是为了开发利用这些资源。接着讨论了P2P的含义以及P2P研究的必要性，然后本章对P2P的主要应用领域做了概要的介绍。最后，本章指出P2P研究的难点在于设计一种高效可扩展的数据检索机制，并据此将现有的P2P实现分为基于目录服务器P2P、非结构化P2P和结构化P2P三种类型进行介绍，并指出前两种类型的查找机制不具有可扩展性，结构化P2P才是发展的方向和当前研究的热点。中国科学技术大学硕士学位论文 第2章 DHT基本原理第2章 DHT基本原理2.1 引言P2P网络的参与节点可以是来自家庭、学校和公司的计算机或其他计算终端设备，同时在线的用户节点数目常常是成千上万。因而，如何把这些分散在各处的廉价且不可靠的用户节点有效地组织起来，设计一个健壮的可扩展的大规模分布式系统就成为P2P研究中最大的挑战之一。在这个大规模的分布式系统中，如何不引入目录服务器就能高效快速地找到指定的数据则是研究中的核心问题。因此，P2P网络数据检索模型和路由算法的研究具有重要的意义，目前国内外很多研究人员围绕这个问题进行了大量的研究，提出的基于分布式哈希表（DHT）的分布式检索和路由算法因为具有查找可确定性、简单性和分布性等优点，正成为国际上结构化P2P网络研究和应用的热点。例如，自2002年起，美国国家科学基金会（NSF）提供了1200万美元的资金启动了一个为期5年的研究项目IRIS【28】，该项目集中了MIT和UC Berkeley等5所著名高等院校的强大科研力量，为下一代大规模分布式应用研制基于DHT的新型基础设施。哈希表作为一种数据结构，可以在记录的存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字和结构中一个唯一的存储位置相对应。因而在查找时，只要根据这个对应关系就可以找到给定关键字K的存储位置。分布式哈希表，顾名思义就是把哈希表分散到P2P网络的各个节点上，目的是在记录的存储节点和它的关键字之间建立一个确定的对应关系。这里的一条记录就是一个文件索引，抽象成一个(K, V)对。也就是说给定一个K，就可以按照对应关系找到存储有相应(K, V)对的节点。从这个节点上取得文件索引(K, V)对后，再从V中读出真正存储文件的节点IP地址。分布式哈希表在节点失效、遭受攻击和突发性高负载面前都能表现出很好的健壮性；它具有良好的可扩展性，能以较低系统开销获得较大的系统规模；可以自我配置，不需要手工干预就可以自动把新加入节点合并到系统中；能提供简单灵活的接口，可以为多个P2P应用同时使用。本章将介绍Chord、CAN（Content Addressable Network）、Pastry和Tapestry这几种最为典型的分布式哈希表系统的原理。2.2 ChordChord【23】是UC Berkeley和MIT共同提出的一种分布式查找算法，目的是为了能在P2P网络中查找数据。给定一个关键字，Chord可以有效地把该关键字映射到网络中某个节点上。因而在P2P网络中只要给每个数据V都赋予一个关键字K，就可以利用Chord在该关键字映射的节点上存储或提取相应的(K, V)对。Chord的突出特点是算法简单，而且可