毕业设计（论文）-基于DHT的分布式文件系统研究.doc

《毕业设计（论文）-基于DHT的分布式文件系统研究.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）-基于DHT的分布式文件系统研究.doc（37页珍藏版）》请在三一文库上搜索。

1、 学号： 信阳师范学院华锐学院 本科毕业论文（设计）专 业 计算机科学与技术 年 级 07级 姓 名 论文（设计）题目 基于DHT的分布式文件系统 指导教师 职称 讲师 2011年4月18日目 录摘 要.1第一章 绪论.3 1.1分布式系统的定义.3 1.2目标.5 1.2.1让用户连接到资源.5 1.2.2透明性.5 1.2.3开放性.61.2.4可扩展性.6 1.3分布式文件系统.61.3.1 SUN网络文件系统.61.3.2不同分布式文件系统对比.9第二章P2P技术.10 2.1.1p2p技术的发展.10 2.1.2p2p技术的分类.11 2.1.3p2p的特性.15 2.2 P2P搜索

2、技术.152.2.1非结构化搜索技术.152.2.2基于DHT的搜索技术.162.3Chord.182.3.1 finger表.192.3.2 Chord算法的查找过程.19第三章基于DHT的Chord算法的改进.22 3.1影响搜索算法性能的因素.22 3.2小世界现象对P2P搜索技术的启示.23 3.3 NChord搜索算法.263.3.2节点加入时的策略.283.3.3节点退出时的策略.293.3.4节点失效时的策略.293.3.5 NChord算法原理.293.3.6Nchord搜索算法的步骤.313.3.7Nchord算法特点.32总结.32参考文献.33致谢.33II 标题 基于D

3、HT的分布式文件系统研究学生姓名： 学号：信阳师范学院华锐学院数计系 计算机科学与技术专业 指导教师： 职称：讲师摘 要：随着信息时代的飞速发展，人们日益发现单个计算机的能力很是有限，于是自然而然想到把各个地方的计算机联合起来处理信息，这就是分布式的提出，随即涉及到资源共享的问题，这就是我们研究的分布式文件系统,随着P2P（即Peer-to-Peer）技术的发展，很好的解决了分布式存储与计算方面的问题，它作为一种全新的互联网技术，将传统的以服务器为中心的互联网应用模式提升为以用户为中心的对等模式。P2P在文件交换，对等计算，协同工作，搜索服务等方面都有着重要的应用。P2P文件交换系统的发展也由

4、最初Npaster的完全中心化模型，Gnutella的完全非中心化模型，发展到现在的BitTorrnet、eMul/eeDoknye、KZaza等混合模型。随着近年来DHT(Disrtibuted Hash Table)技术的不断发展，DHT在p2p文件交换系统中扮演着越来越重要的角色，Kdamelai作为覆盖网络被广泛使用到P2P文件交换系统中。P2P网络通常使用DHT作为其路由表，比较典型的算法有Chord、CAN、Kademlia、Tapestry、Pastry等，这些算法不仅可靠性高，容错性强，而且查找的效率非常高，查找算法的复杂度基本上都是O(LogN)，被广泛地应用于各种各样的分布

5、式系统中。本文将比较分析以上各算法的原理和差异，重点分析、研究和改进Chord算法，减少路由跳数和系统开支。关键词：分布式;分布式文件系统;p2p;DHT;ChordAbstract：With the rapid development of information era, People increasingly find a single computer ability is very limited, Naturally they tempted to connect with computers in every region to processing information,th

6、us the distributed proposed,but then comes the resource sharing problem,thats the Distributed File System here what we are talking about,as the development of p2p(peer-to-peer) technology,the problem of distributed storage and computing is well solved,the technology of p2p(peer-to-peer), as a new In

7、ternet technology,promoting the traditional centralized server Internet Application Modle to centralized user Peer to Peer Modle.P2P is important in Data-Exchange,Peer-to-Peer Computing,Coordinated Working,Search Service,etc,In P2P file-sharing systems,it is developing from the beginning centralized

8、 model Napster and decentralized model Gnutella to the current mixed modle,such as BitTorrent,eMule,Kazza,etc.As the DHT(Distrituted Hash Table) technology develops,it plays a more important role in P2P file-sharing system,Kademlia is used widely in P2P file-sharing system as an overlay network. Dis

9、tributed architecture of the network is commonly used to build P2P networks using DHT algorithm,forinstance,Chord,CAN,Kademlia,Tapestry,Pastry,etc.These algorithms not only possess high reliability and strong fault tolerance,but also have efficient look up.The complexity of search algorithm is basic

10、ally O(LogN),so they are widely used in a variety of distributed storage systems. This paper study and compare the principles and differences of above DHT algorithms,research、analysis and promote the Chord algorithm more in-depth.thus decreasing the jump numbers during the process of searching and t

11、he cost of system.Key words:distributed;distributed file system;p2p;DHT;Chord 第一章 绪 论 计算机系统正在经历一场革命。1945年是现代计算机时代的开始。从那时起一直到1985年，计算机一直是庞大笨重而昂贵的。即便是小型机每台也要上万美元，因而大多数机构都只有很少的几台计算机。而且由于没有把这些计算机连接起来的手段，所以只能单独的使用它们。 然而，从20世纪80年代中期开始，技术领域中两方面的进步开始使这种局面有所改观。第一项进步是高性能处理器的开发。起初这些机器是8位机，但是很快16位、32位乃至64位的cpu纷

12、至沓来，得到了普及。很多使用这些cpu的机器的计算性能都可以与大型机相媲美，而价格却比大型机便宜得多。 近半个世纪以来，在计算机技术改进方面所取得的成果数量之多对于其他工业来说是完全无法想象的。一台计算机的价格从1亿美元下降到了1000美元，而运算速度却从每秒一条指令提升到每秒1千万条指令，性能价格比提升了大约 1012倍。如果汽车的性能价格比在同一时期以同样的速率是提升，那么一辆“劳斯来斯”牌轿车现在只值1美元，而且每消耗1加仑（1加仑=4.5461升）汽油可以行驶10亿英里（1英里=1.6093公里）。（不幸的是如果果真如此，光是说明如何打开车门这件事，就可能在用户手册中占用长达200页得

13、篇幅。） 第二项进步是高速计算机网络的发明。利用局域网技术可以将位于同一建筑物里的数百台计算机连接起来。使用这种连接方式可以在几us内将少量数据从一台机器传输到另一台机器。如果要传输大量的数据，传输数率可以达到101000Mb/s。利用广域网技术可以连接全球范围内数百万台机器，机器间的数据传输速率从64Kb/s到若干Gb/s不等。 现在，由于有以上这些技术可供使用，因此把若干由大量计算机组成的计算机系统彼此通过高速网络相连接，不但是可行的，而且是很容易实现的。这种系统一般称为计算机网络或分布式系统，以突出其与传统的集中式系统（centralized system，也称为单处理器系统，singl

14、e processor system）的差异。传统的集中式系统一般由单个计算机及其外围设备构成，也可以包含一些远程终端。 1.1分布式系统的定义 已经有很多文献给出了分布式系统的定义，但是不同文献给出的定义彼此不尽相同，而且没有一种令人满意。考虑到本文的目标，我们只给出一个粗略的描述： 分布式系统是若干独立计算机的集合，这些计算机对于用户来说就像是单个相关系统。 这个定义包含了两方面的内容。第一方面是关于硬件的：机器本身是独立的，第二个方面是关于软件的：对用户来说他们就像在与单个系统打交道。这两个方面共同阐明了分布式系统的本质，缺一不可。我们先介绍关于软硬件的一些背景材料，与继续探讨分布式系统

15、的定义相比，把注意力集中在分布式系统的重要特性上可能更好一些。其重要特性之一是，各种计算机之间的差别以及计算机之间的通信方式的差别对用户是隐藏的。同样，用户也看不到分布式系统的内部组织结构。另一重要特性是，用户和应用程序无论在何时何地都能够以一种一致的统一的方式与分布式系统进行交互。 分布式系统的扩展或者升级应该是相对比较容易的。这一特性是由于下述原因：1、 分布式系统由独立的计算机组成，但同时隐藏了其中单个计算机在系统里所承担任务的细节。2、 即使分布式系统中某些部分可能暂时发生故障，但其整体在通常情况下总是保持可用。3、 用户和应用程序不会察觉到那些部分正在进行替换和维修，以及加入了哪些新

16、的部分来为更多的用户和应用程序提供服务。 为了使种类各异的计算机和网络都呈现为单个的系统，分布式系统常常通过一个“中件层”组织起来，该“软件层”在逻辑上位于由用户和应用程序组成的高层与由操作系统组成的底层之间，如图1.1所示。这样的分布式系统有时又称为中间件（middleware）。图1.1作为中间件组织的分布式系统（请注意，中间件层延伸到了多台机器上）现在我们考察一下分布式系统的几个例子。第一个例子是位于一所大学或者某个公司部门的工作站网络。该系统除了包括每个用户自己的工作站以外，还应该包括机房内的一个处理器池。这些处理器并不分配给特定的用户，而是根据需要进行动态调配，这样的系统可能包含一个

17、单一的文件系统，允许所有的机器通过相同的方法并且使用相同的路径名来访问所有的文件。并且，当用户键入一个命令的时候，系统将寻找执行该命令的最佳位置，也许会在自己的工作站上直接执行该命令，也可能会在别人的一个空闲的工作站上执行，还有可能有机房中某个尚未分配的处理器执行。如果系统整体外观和行为与传统的单处理器分时系统（即多用户系统）相似，那么这个系统就可以看做是分布式系统。第二个例子是某个工作流信息系统，该系统支持对账单的自动的处理。一般情况下，会有来自多个不同部门的人员在不同的地点使用这样的系统。例如，销售部的人员可能遍布在很大的一个区域，甚至全国。可以通过电话网络（或者蜂窝电话）连接到系统的膝上

18、型计算机下达订单。收到的订单由系统自动传送到计划部，接着新的内部调货订单就会送达仓储部，同时有财务部处理账单。该系统自动将订单传送到相关人员手中。用户根本就看不到系统中订单处理的物理流程；对于用户来说，这些订单像是由一个集中式数据库处理的一样。 最后一个例子是万维网。它提供了一种简单、一致并且统一的分布式文档模型。要查看某个文档，用户只须激活一个引用（即链接），文档就会显示在屏幕上。理论上（但目前在实际中并不是这样）并不需要知道该文档来自于哪个服务器，更用不着关心服务器所在的位置。要发布一个文档也很简单：只需要赋予它一个唯一的URL名，让该URL指向包含文档内容的本地文件即可。如果万维网向用户

19、呈现的是一个庞大的集中式文档系统，也可以认为它是一个分布式系统。不幸的是，我们现在还无法做到这一点。例如，用户明白这样一个事实：文档位于不同的地点，并由不同的服务器处理。 1.2 目 标 分布式系统必须能够让用户方便地与资源连接；必须隐藏资源在一个网络分布这样一个事实；必须是开放的；必须是可扩展的。 1.2.1 让用户连接到资源 分布式系统最主要目标是使用户能够方便地访问远程资源，并且以一种受控的方式与其他用户共享这些资源。资源几乎可以是任何东西，其典型例子包括打印机、计算机、存储设备、数据、文件、Web页以及网络，但这些只是资源中的一小部分。有很多理由要求资源共享，一个显而易见的理由是降低经

20、济成本。例如，让若干用户共享一台打印机比为每一位用户购买并维护一台打印机要划算的多。基于同样的原因，共享超级计算机和高性能存储系统这样昂贵资源也是很有意义的。 1.2.2 透明性 如果一个分布式系统能够在用户和应用程序面前呈现为单个计算机系统，这样的分布式系统就称为透明的。 1分布式系统的透明性 透明性的概念可以运用到分布式系统中的各个方面，如图1.2所示。 透明性说明访问隐藏数据表示形式的不同以及资源访问方式的不同位置隐藏资源所在位置迁移隐藏资源是否移动到另一个位置重定位隐藏资源是否在使用过程中移动到另一个位置复制隐藏是否资源进行复制并发隐藏资源是否由若干相互竞争的用户共享故障隐藏资源的故障

21、和恢复持久性隐藏资源（软件）位于内存中还是硬盘中图1.2 分布式系统中不同形式的透明性（ISO 1995） 访问透明性指对不同数据表示形式以及资源访问方式的隐藏。例如，要将一个整型数从基于Intel处理器的工作站传输到一台Sun SPARC机器上，我们必须考虑到Intel处理器传输数据字节的顺序是little endian格式（先传输数据的高位字节），而SPARC处理器却使用big endian（先传输数据的低位字节）。在数据表示形式上还会存在其他的差别。例如，分布式系统中的多个计算机系统可能运行的是不同的操作系统，这些操作系统的文件命名方式不同。文件命名方式的差异以及由此引发的文件操作方式的

22、差异都应该对用户和应用程序隐藏起来。2透明度 虽然对于任何分布式系统来说，实现分布透明性通常是可取的，但是在某些情况下，把所有分布情况都对用户屏蔽得严严实实并不见得有好处。这样的一个例子是，如果您订阅了一份电子报刊，并且要求它在每天本地时间早上7点之前就寄到邮箱里，而您现在呆在地球另一端的不同时区，您就会发现“早报”不在是早上寄到的。 另外，还必须在高度的透明性和系统性能之间进行权衡，得出折衷方案。例如，许多Internet应用程序会不断尝试连接到某台服务器，多次失败后才最终放弃。这种在用户转向另一台服务器之前竭力隐藏服务器短暂故障的企图会导致整个系统变慢。在这种情况下，最好还是让用户早一些放

23、弃，或者至少允许用户取消这种连接的尝试。 在设计并实现分布式系统时，把实现分布的透明性作为目标是正确的，但是应该将它和其他方面的问题（比如性能）结合起来考虑。1.2.3 开放性 开放的分布式系统的另一个重要目标是，它必须是灵活的，要能够方便的把由不同开发人员开发的不同组件组合成整个系统。同时，还必须能够方便地添加新组件、替换现有的组件，而不会对那些无须改动的组件造成影响。换句话说，开放的分布式系统应该是可扩充的。例如，在灵活的系统中，要添加可运行于另一个操作系统上的部件应该是比较容易的，即使要更换整个文件系统也不应该太对困难。但根据我们从日常实践中得到的经验，要实现灵活性是比较困难的。1.2.

24、4可扩展性 通过互联网，世界范围的互联正在变得像给世界任何地方的人寄张明信片一样平常。考虑到这种情况，分布式系统开发者都将可扩展性作为最重要的实际目标之一。 系统的可扩展性至少可以通过三个方面来度量（Neuman 1994）。首先，系统要能在规模上扩展，也就是说可以方便地把更多的用户和资源加入到系统中去。其次，如果系统中的用户和资源可以相隔极为遥远，这种系统就称为地域上可扩展的系统。最后，系统在管理上是可扩展的，也就是说，即使该分布式系统跨越多个独立的管理机构，仍然可以方便地对其进行管理。不幸的是，在以上这三个方面或其中某一两个方面可扩展的系统常常在扩展之后表现出性能的下降。1.3 分布式文件

25、系统 鉴于共享数据是分布式系统的基础，分布式文件系统是构成许多分布式应用程序的基础就不足为奇了。分布式文件系统允许多个进程在长时期内以一种安全、可靠的方式共享数据。所以，它们已被用作分布式系统和分布式应用程序的基础层。在本节中，我们把分布式文件系统看作通用分布式系统的模型。 我们将详细讨论两个不同的分布式文件系统。第一个实例是SUN NFS(net work file system,网络文件系统)，它已经得到了广泛应用，现在正逐渐向基于Internet的大规模文件系统的方向发展。NFS的大多数实现基于其版本3规范。 另一个完全不同的分布式文件系统是Coda。Coda源于AFS（Andrew文件

26、系统），AFS是一个在设计是就考虑到可扩展性的大规模系统。Coda与许多其他文件系统的区别在于它在面对网络分区时支持连续操作。特别是那些故意时常断开网络连接的移动用户（比如，使用膝上型计算机的人们）会从中获益。 我们也将简要讲述其他三个系统。Plan9是一个将所有资源都视为文件的分布式系统。从这种意义上来说，它可以被视为一个基于文件的分布式系统。我们将讲述的另一个系统是xFS，其与众不同之处在于它没有服务器，而是让客户实现文件系统。最后，我们会介绍SFS，该系统强调可扩展的安全性。1.3.1 SUN网络文件系统 我们以SUN微系统的网络文件系统（network file system），即通常

27、所说的NFS，开始讨论分布式文件系统。NFS最初是Sun为在它的基于UNIX的工作站上的使用而开发的，但是NFS已在许多其他系统中实现。NFS的基本思想是每台文件服务器提供它的本地文件系统的标准化视图。也就是说，它不关心如何实现本地文件系统，每台NFS服务器支持相同的模型。这个模型带有一个通信协议，该协议允许客户访问存储在一台服务器上的文件。这种方法允许大量异构进程共享一个公共的文件系统，其中的进程可能运行于不同的操作系统和机器上。1NFS概述 与其说NFS是一个真正的文件系统，不如说它是共同为客户提供分布式文件系统模型的协议的集合。NFS协议是以不同的实现之间应该易于进行互操作为目的而设计的

28、。因此，NFS可以运行于大量异构计算机之上。2.NFS体系结构NFS底层的模型是远程文件服务的模型。这个模型为客户提供对远程服务器所管理的文件系统的透明访问。但是，客户通常不知道文件的实际位置，相反，NFS为客户提供访问此文件系统的接口，此接口类似于传统本地文件系统所提供的接口。也就是说，客户仅被提供包含多种文件操作的接口，而服务器负责实现这些操作。因此，这一模型也被称为远程访问模型（remote access model），如图1.3.1（a）所示图1.3.1（a）客户服务器文件位于服务器上来自客户的访问远程文件的请求3.当客户程序被执行后，文件返回服务器 旧文件新文件客户服务器1.文件移动

29、到客户2.在客户上执行访问 1.3.1（b）上载/下载模型与之相对照，在上载、下载模型（upload/download model）中，客户从服务器下载文件后，在本地访问该文件，如图1.3.1（b）所示。客户完成对文件的访问后，再将该文件上载回服务器，以便其他客户使用该文件。当客户下载一个完整的文件，修改该文件，然后将其放回服务器时，可以使用Internet的FTP服务。尽管NFS基于UNIX的版本占主流地位，但是NFS已开发了多种版本以用于许多不同的操作系统。实际上，对所有现代UNIX系统而言，NFS通常按照图1.3.1（c）所示的层次体系结构实现。 图1.3.1（c）3.文件系统模型 NF

30、S版本四支持硬链接和符号链接。文件具有文件名，但是访问它们是通过一种类似UNIX的文件句柄（file handle）实现的，为访问一个文件，客户必须现在命名服务器中搜索该文件的文件名，然后获得该文件关联的文件句柄。另外，每个文件有许多属性，这些属性是可以查询和修改的。下表列出了NFS支持的通用文件操作。操作描述create创建一个非常规文件link创建一个文件的硬链接rename更改文件名remove从文件系统删除一个文件open打开一个文件close关闭一个文件lookup根据文件名搜索文件readdir读取一个目录下的项目readlink读取符号链接所存储的路径名getattr获得文件的属

31、性值setattr设置文件的一个或多个属性值read 读取文件中的数据write向文件写入数据1.3.2不同分布式文件系统对比该表总结了5种不同分布式文件系统的各个要点： 要点NFSCodaPlan9xFSSPF设计目标访问透明性高可用性统一性无服务器系统可扩展的安全性访问模型远程上载/下载远程基于日志远程通信RPCRPC特殊方法活动消息RPC客户进程瘦/胖胖瘦胖中等服务器组无有无有无装入粒度目录文件系统文件系统文件系统目录名称空间每个客户全局每个进程全局全局文件ID范围文件服务器全局服务器全局文件系统共享语义会话事务处理UNIXUNIXN/S缓存单元文件文件文件块N/S高速缓存一致性回写式回

32、写式直写式回写式回写式复制最低限度ROWA无带区划分无容错可靠的通信复制与缓存可靠的通信带区划分可靠地通信恢复基于客户重新合成N/S 检查点和记录日志N/S安全通道现存的机制重新合成N/S检查点和记录日志自证明访问控制许多操作目录操作基于UNIX基于UNIX基于NFS注：N/S表示无特殊规定第二章P2P技术2.1 P2P技术2.1.1 P2P的背景与发展 对等网络p2p（peer to peer），维基百科是这样定义的：P2P技术是一种网络新技术，依赖网络中参与者的计算能力和带宽，而不是把依赖都聚集在较少的几台服务器上。在P2P网络环境中，成千上万台彼此连接的计算机都处于平等的地位，整个网络一

33、般来说不会依赖于专门的中央服务器。网络中的每一台计算机既能充当网络服务的请求者，又能对其他计算机的请求做出响应，提供资源或其他服务。 P2p技术的发展可以追溯到上世纪九十年代，由一个叫肖恩的大一学生编写的叫Napster的程序，这个程序能搜索音乐文件并提供检索功能。随着互联网的发展，尤其是上世纪90年代后期，计算机硬件的性能有了突飞猛进的发展，而且网络带宽等基础设施也大幅的改善，人们开始感到有必要而且能够直接控制、修改和共享资源。随后开始把服务器软件也放在单独的PC上，而且在PC与PC之间直接进行通信，这就导致了P2P技术的复兴。P2P技术主要指由硬件形成网络连接后的信息控制技术，是应用层上的

34、一种逻辑网络，主要的代表就是在基于P2P网络协议的各种客户端软件。由上文可知，P2P网络是属于叠加在底层通信网络基础之上的逻辑网络，是应用层的程序，也是一个分布式、具有互操作性的自组织系统。P2P网络面临的最大的挑战之一就是如何在没有集中式服务器的模式下维护网络拓扑结构，以及实现资源检索等服务。在P2P网络中，如何对资源进行准确的定位是最重要的问题。现阶段P2P搜索技术的研究可以从两个方面来进行，第一个方面是从P2P搜索算法入手来进行研究，第二个方面是从P2P的体系架构入手进行研究。P2P搜索算法包括：Chord算法，Pastry算法，Tapestry算法，CAN算法和Kademlia算法等等

35、。P2P体系架构方面包括：集中式系统，分布式系统，混合式系统。2.1.2p2p技术的分类拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系，节点之间的拓扑结构一直是确定系统类型的重要依据。P2P系统主要采用非集中式的拓扑结构，根据结构关系可以将P2P系统细分为叫种结构的拓扑形式：中心化拓扑网络、全分布式非结构化拓扑网络、全分布式结构化拓扑网络以及半分布式拓扑网络。1. 中心化拓扑网络中心化拓扑网络最大的优点是维护简单，发现效率高。由于资源的发现依赖中心 化的目录系统，发现算法灵活、高效并能够实现复杂查询。最大的问题与传统c/s结构类似，容易造成单点故障，访问的“热点”现象和法律等相

36、关问题，这是第一代p2p网络采用的结构模式，经典案例就是著名的MP3共享软件Napster。 在Napster模型中，一群高性能的中央服务器保存着网络中所有活动对等计算机共享资源的目录信息。当需要查询某个文件时，对等机会向一台中央服务器发出文件查询请求。中央服务器进行相应的检索和查询后，会返回符合查询要求的对等机地址信息列表。查询发起对等机接收到应答后，会根据网络流量和延迟等信息进行选择和合适的对等机建立连接，并开始文件传输。Napster的工作原理如图2.1.2（1）所示。 图2.1.2（1）Napster网络的拓扑结构采用Napster结构的中心化拓扑网络结构也存在一些问题，主要表现为：

37、(1) 中央服务器的瘫痪容易导致整个网络的崩馈，可靠性和安全性较低； (2)随着网络规模的扩大，对中央索引服务器进行维护和更新的费用将急剧增加，所需成本过高；（3）中央服务器的存在引起共享资源在版权问题上的纠纷，并因此被攻击为非纯粹意义上的P2P网络模型。综合上述优缺点，对小型网络而言，中心化网络模型在管理和控制方面占一定优势。但鉴于其存在的种种缺陷，该模型并不适合大型的网络应用。2.全分布式非结构化的P2P网络 全分布式非结构化刚络采用了随机图的组织方式，结点度数服从Powerlaw”规律，从而能够较快发现目的结点，而对网络的动态变化体现了较好的容错能力，因此具有较好的可用性，同时可以支持复

38、杂查询，如带有规则表达式的多关键词查询，模糊查询等，采用这种拓扑结构最典型的案例便是Gnutella，如图2.1.2（2）所示。 图2.1.2（2）Gnutella网络的拓扑结构Gnutella是一个P2P文件共享系统，它和Napster最大的区别在于Gnutella是纯粹的P2P系统，不存在集中式的目录服务器，并且文件的发布和网络拓扑松散相关。 Gnutella网络具有以下特点： (1) 不存在中央服务器，完全依赖于网络中的交互式个人成员而独立存在；(2)在浚网络模型中，每一个联网计算机在功能上都是对等的，既是客户机同时又是服务器，所以被称为对等机。 发现的准确性和可扩展性是非结构化网络面临

39、的两个重要问题。目前对此类结构的研究主要集中于改进发现算法和复制策略以提高发现的准确率和性能。3全分布式结构化的P2P网络 在这类网络中，不存在中心化的目录服务器，因此属于全分布式的P2P网络。这种类型的网络结构，采用分布式散列表(Distributed Hash Table，简称DHT)的全分布式结构化拓扑网络。分布式散列表实际上是一个由广域范围大量结点共同维护的巨大散列表。散列表被分割成不连续的块，每个结点被分配给一个属于自己的散列块，并成为这个散列块的管理者。 DHT结构能够自适应结点的动态加入与退出，有着良好的可扩展性、鲁棒性、结点ID分配的均匀性和自组织能力。最经典的案例是Tapes

40、try、Chord、CAN和Pastry。这里主要介绍一下具有代表性的chord网络模型，如图2.1.2(3)。该网络模型诞生于美国的麻省理工学院，它的目标是提供适合于P2P环境的分布式资源发现服务，它通过使用DHT技术使得发现指定对象只需要维护O(109N)长度的路由表。在DHT技术中，网络节点按照一定的方式分配一个唯一节点标识符(Node，ID)，资源对象通过散列运算产生一个唯一的资源标识符(Obiect，ID)，且该资源将存储在节点ID与之相等或者相近的节点上。需要查找该资源时，采用同样的方法可定位到存储该资源的结点。因此，Chord的主要贡献是提出了一个分布式查找协议，该协议可将指定的关键字(Key)映射到对应的节点(Node)。 图2.1.2（3）Chord网络的拓扑结构DHT结构最大的问题是DHT的维护机制较为复杂，尤其是结点频繁加入退出造成的网络波动会极大增加DHT的维护代价。DHT所面临的另外一个问题是DHT仅支持精确关键词匹配查询，无法支持内容、语义等复杂查询。4半