（计算机应用技术专业论文）非结构化p2p网络文件搜索系统的研究与实现.pdf

摘要 在一个p 2 p 文件共享系统中，终端用户节点( p e e r ) 通过i n t e r n e t 完成文件交 换。一个p 2 p 文件共享系统，需要解决两个方面的问题：文件搜索和文件传送。由 于p 2 p 系统本身的分布式存储特点，使得实现具有扩展性的文件传送机制变得相 对容易。p 2 p 技术的难点也在于如何发现拥有目标文件的对等点，这也就是本文设 法解决的问题。 本文首先介绍了p 2 p 网络技术和p 2 p 网络文件共享系统，重点研究了p 2 p 网 络文件共享系统中的文件搜索。然后在分析现有的p 2 p 网络结构和文件搜索算法 的基础上，研究了前人提出的一种针对非结构化p 2 p 网络f l o o d i n g 算法网络负载 过重的不足的改进算法_ d i 您e a r c h 。该算法首先根据节点当前共享的有效文件 数目确定节点的身份，将节点分为普通节点和超级节点，并将超级节点组成一个 连通的覆盖网络，这样网络中绝大部分节点的查询便可以在覆盖网中进行。在深 入的研究d i f f s e a r c h 算法后，以此算法为核心，对文件搜索系统进行了设计。明确 了文件搜索系统的功能，将系统设置为4 个模块，分别实现启动、终止、搜索和 系统设置。详细设计了各个模块的功能，通过j a v a 语言和j x t a 平台实现了文件 搜索系统各个模块的编码，最终完成了一个以d i f f s e a r c h 算法为核心的文件搜索系 统。并在此系统上进行了测试，用户提供一个查询条件，系统返回一个用户所查 询的文件信息和节点信息，证明了系统的有效性。 关键词：p 2 p ；搜索；非结构化p 2 p ；d i f f s e a r c h ；j x t a 分类号：t p 3 9 3 9 a bs t r a c t i nap 2 pf i l e s h a r i n gs y s t e m ，t h ee n dc l i e n te x c h a n g ef i l e s i nt h ei n t e m e t f i l e s e a r c h i n ga n df i l ed e l i v e r ya r et w oc r u c i a lp r o b l e m sn e e dt ob es o l v e di np 2 ps y s t e m t h en a t u r eo fd i s t r i b u t e ds t o r a g eo fp 2 pm a k e si te a s i e rt oi m p l e m e n tas c a l a b l es y s t e m o ff i l ed e l i v e r y t h ed i f f i c u l t yi sh o wt ol o c a t et h ep e e rw h oh a st h et a r g e tf i l e ，a n di ti s a l s ot h ep r o b l e mt h i st h e s i st os o l v e f i r s t l y , t h i s t h e s i si n t r o d u c e st h et e c h n i q u eo fp 2 pn e t w o r ka n dt h ep 2 p f i l e s h a r i n gs y s t e m ，s t u d i e st h ef i l es e a r c hi np 2 pf i l e s h a r i n gs y s t e m t h e n ，o nt h eb a s i s o fa n a l y z i n gt h ea r c h i t e c t u r eo fp 2 pn e t w o r ka n dt h ef i l es e a r c ha l g o r i t h m ，w es t u d yt h e d i f f s e a r c ha l g o r i t h m ，a l li m p r o v e da l g o r i t h mb a s e do nt h ef l o o d i n go nu n s t r u c t u r e d p 2 pn e t w o r k t h i sa l g o r i t h mi d e n t i f i e st h ep e e r sb a s e do nt h en u m b e ro fe f f e c t i v e s h a r e df i l e s ，s e t t i n gt h e ma sp e e ro ru l t r a p e e r p e e r sc a nf i n dt h ei n f o r m a t i o no f u l t r a p e e r st h r o u g hm e s s a g e so fs e a r c h i n gi nt h en e t w o r k ，a n dc o m p o s ea no v e r l a yw i t h u l t r a p e e r sc o n n e c t e dw i t he a c ho t h e r m o s to fs e a r c h e sc a nb ef i n i s h e di nt h eo v e r l a y t h ed i f f s e a r c ha l g o r i t h mi ss e tt ob et h em a i na l g o r i t h mo ft h ef i l es e a r c hs y s t e mi nt h i s t h e s i s t h e nt h es y s t e mi sd e s i g n e dt of i n i s hf i l es e a r c h b a s e do nf u n c t i o n so ff i l e s e a r c hs y s t e m ，i ti sd i v i d e di n t of o u rm o d e l s ，e a c ho fw h i c hi m p l e m e n t ss t a r t ， t e r m i n a t i o n ，s e a r c h i n ga n ds y s t e ms e t t i n g t h e f u n c t i o no ft w o - r o u n ds e a r c hi s i m p l e m e n t e d i nt h es e a r c hm o d e le l a b o r a t e l y f u r t h e r , c o d i n go ft h es y s t e mi s i m p l e m e n t e dw i t hj a v ao nt h ep l a t f o r mo fj x t ai no r d e rt ob u i l d u pt h es y s t e mt h r o u g h t h ed i f f s e a r c ha l g o r i t h m f i n a l l y , at e s ti se x e c u t e do nt h es y s t e mw h i c hp r o v i d e sa q u e r ya n dm a k e sar e s p o n s et os h o wt h ei n f o r m a t i o no fr e l a t i n gf i l e st op r o v et h e e f f e c t i v eo ft h es y s t e m k e y w o r d s ：p 2 p ；s e a r c h ；u n s t r u c t u r e dp 2 pn e t w o r k ；d i f f s e a r c h ； j x t a c l a s s n o ：t p 3 9 3 9 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字日期：抄口彦年多月多日 导师签名：于职乙 签字日期坩f ) 月毛日苫曲￥v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名! 趣经。寿， 签字日期：文口夕孑年多月多日 5 1 致谢 本论文的工作是在我的导师于双元教授的悉心指导下完成的，于双元教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来 于双元老师对我的关心和指导。 于双元教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向于双元老师表示衷心的谢意。 在实验室工作及撰写论文期间，石磊峰、陈晨、许入文等同学对我论文中的 研究工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。 1 绪论 1 1 研究背景及意义 p 2 p 技术并不是一个新的概念，其实，早在1 9 7 9 年，u s e n e t ( 新闻组) 的 产生，就标志着p 2 p 技术应用的开始。p 2 p 正式进入发展的历史可以追溯到1 9 9 7 年7 月，在一段介绍当时p 2 p 技术的文字中写着：1 9 9 7 年7 月，h o t l i n e c o m m u n i c a t i o n s 公司成立，并且研制了一种可以使其用户从其他用户计算机中直 接下载资料的软件。i l l p 2 p 技术起源于最初的联网通信方式，其中建立在t c p i p 协议之上的通信模 式构成了今日互联网的基础，t c p i p 通讯协议本身没有服务器与客户端的概念。 互联网发展初期，c l i e n t s e r v e r 模式开始大行其道，“内容位于中心 模式较好地 适应了当时由于个人计算机性能差异而需要有专门的服务器，并由于其带宽窄而 不得不退化到被动浏览的状况。 现今随着个人计算机性能的极大提升以及宽带网络的逐步普及，如果不改变 用户与网站间单向主从的关系，网络内容供需仍旧维持着少数供给多数需求的星 型结构，就会大大限制网络内容扩展的能力。p 2 p 技术可重新将网络资源整合与累 积，个人计算机将不再只是网络背后的一具浏览器，而升级为有价值的网络边缘 设备，并成为新的网络资源取向。这将会改变使用者向网站单向索取资源的状况， 使互联网回到“内容位于边缘模式。 从1 9 9 9 年，n a p s t e r l 2 文件共享系统的成功运行，使得p 2 p 技术开始真正的与 实际应用联系起来，也使得到目前为止，对于p 2 p 技术的使用主要集中在文件共 享系统中。随之又有g n u t e l l a t 3 】和k a z a a t 4 】等初级的对等网络应用系统的成功推出， 对等网络受到了人们更加广泛的关注。虽然p 2 p 文件共享系统由此引发了一些版 权问题，但是由于对等网络具有分散控制、自组织、自适应和良好的可扩展性等 优点，使得人们对p 2 p 技术的研究投入越来越多的关注。 在p 2 p 文件共享系统中，为了达到节点间文件共享的目的，必须能实现节点 问的文件上传和下载。但是在下载文件之前，我们首先需要能够搜索到文件。文 件共享系统发展到目前为止，为了达到搜索结果的高效性，已经应运而生了多种 不同的网络结构和针对这些网络结构的搜索算法。本文针对上述背景，分析了一 些传统的p 2 p 搜索算法，在这个基础上找到一种能保证搜索的高效性同时又造成 很小的网络负载的算法，并以这个算法为核心，实现了一个p 2 p 文件搜索系统。 1 2 本文的主要研究内容 本文的主要工作有： 1 p 2 p 技术在文件共享系统中的使用 深入的分析了p 2 p 技术和p 2 p 网络结构，针对p 2 p 文件搜索系统，深入研究 p 2 p 技术的网络结构及其特点，分析针对不同的网络结构提出的资源搜索算法，总 结其优缺点。 2 深入研究非结构化p 2 p 网络搜索技术 对非结构化p 2 p 搜索算法进行深入的研究，综合介绍了非结构化p 2 p 网络 f l o o d i n g 搜索算法的设计原理及对f l o o d i n g 算法的几种改进方法。确定本文主要 的研究对象d i f 俗e a r c h 算法，深入研究d i f t s e a r c h 算法的设计思想及d i f f s e a r c h 算法的核心描述。 3 设计了基于d i f f s e a r c h 算法的文件搜索系统 分析p 2 p 文件搜索系统，确定了文件搜索系统的功能，根据功能不同设计了 该系统的模块，对每个模块进行详细的分析。 4 实现了基于d i f 俗e a r c h 算法的文件搜索系统 研究实现本文中文件搜索系统的p 2 p 网络平台一j x t a ，详细介绍实现系统 的与平台有关的概念、协议等，并使用j a v a 语言在j x t a 平台上实现了以d i f f s e a r c h 算法为核心的文件搜索系统。 5 完成文件搜索系统的测试 按照系统的工作流程对系统的功能进行了测试，测试结果表明该系统可以完 成p 2 p 网络中节点间的文件搜索功能。 1 3 本文的组织结构 本文章节安排如下： 第一章为绪论部分，主要介绍本文的研究背景和本文的主要研究内容。 第二章为相关技术的研究，主要介绍了针对文件搜索相关的p 2 p 技术和p 2 p 开发平台j x t a 。 第三章为文件搜索系统的核心搜索算法介绍，主要针对非结构化p 2 p 网络 d i f f s e a r c h 算法介绍。 第四章为文件搜索系统的设计，主要介绍了系统的设计目标和主要模块。 第五章为系统的实现，详细介绍了各个模块的实现。 第六章为结论，总结了论文的工作和下步工作的展望。 2 2j x t a 平台与p 2 p 技术 在本章中，将对本文涉及的一些相关技术进行介绍。因为本文主要研究p 2 p 文件搜索，所以本文的重点将集中在文件共享系统。首先，2 1 节将介绍本文中用 到的一个现存的p 2 p 网络架构j x t a ，其中又将分几部分详细介绍j x t a 的特 性，协议以及选用j x t a 作为本文p 2 p 搜索系统实现平台的说明。然后，2 2 节将 介绍p 2 p 系统及研究现状：本节又将分为3 个部分，其中2 2 1 将介绍现存的p 2 p 网络结构，并分析每种网络结构的优缺点，2 2 2 将介绍目前p 2 p 网络的应用及研 究现状，以及最后在2 2 3 中介绍一下p 2 p 网络中的文件搜索。 2 1j x t a 的研究 对等网络p 2 p ( p e e r - t o - p e 神是因特网实现下一次飞跃的关键，在p 2 p 网络模式的 研究领域里，j x t a ( j u x t a p o s e ，并行) 【5 1 作为一种全新的p 2 p 网络解决方案己经日益 受到业界的关注。 2 1 1j x t a 体系结构 j x t a 是一个针对点对点( p 2 p ) 计算的合作研究项目，是由s u n 公司发起的 开放源代码( a no p e n s o u r c ep r o j e c t ) 项目。j x t a 是一种平台，使用特定的协议与点 对点网络中的其他j x t a 平台通信。它不是应用程序或创建特定应用程序使用的 库。更进一步说，j x t a 是一组独立于语言和网络的协议，它使得在不断变化的写 作计算设备上开发应用程序和服务成为可能。使用j x t a 可以使p 2 p 环境中的许多 不同应用和服务能够相互协作，且与开发语言( 如c 或者j a v a ) 、操作系统( 如w i n d o w s 或u n i x ) 和网络协议( 立i t c p i p 或蓝牙) 等无关。j x t a 平台提供了基本成分( i d 、广 告、点组、管道等) 和一套默认的核心协议，而且这些协议都易于实现并集成到现 有的系统中。当然，开发者可以开发自己的协议以取代默认的协议。例如，可以 使用新的路由、成员关系或搜索协议来个性化自己的平台。 j x t a 是为了构建p 2 p 网络而制定的一组协议，是为了解决构建p 2 p 网络所碰到 的问题，j x t a 标准协议规范如下： “j x t a 由六个协议组成，这些协议是专为特定的、分布式的、对等的网络计 算而设计的。使用这些协议，p e e r 可以互相合作来建立自我组织、自我管理的对等 组，而不必关心他们在网络中所处的位置( 在网络边缘或者防火墙的后面) ，并且 3 也不需要集中的管理机构。【6 】 因此，j x t a 的核心是六个协议，通过这六个协议来完成p e e r 之间的通信，彼 此之间的资源发布和发现，信息的传递和路由。这六个协议被分成两类：核心协议 和标准服务协议。 核心协议是端点路由协议和点解析协议；标准服务协议包括：点发现协议、点 信息协议、管道绑定协议、集合点协议。 点发现协议( p d p 协议) 点发现协议用于找到任何j x t a 网络中已发布的资源。这些资源都使用广告进 行描述，他们包括：对等点、对等点组、管道和服务。 点信息协议( p i p 协议) 点信息协议用于从已知的对等点那里获得状态信息。该状态信息目前包括了 对等点的上线时间和流量信息。 管道绑定协议( p b p 协议) 简单地说，p b p 将p e e r 组成员的管道操作绑定到实际的传输协议。允许p e e r 之间建立虚拟的通信通道。通过p b p ，一个p e e r 能建立一个或多个连接管道。 点解析协议( p r p 协议) 允许p e e r 送出一个更普通的查询信息，并获得该查询的回应。p e e r 解析协议是 一个基础通信协议，它是按照请求响应格式来进行的。 集合点协议( r v p 协议) r v p 描述了消息如何在点组中各点之间传播。它为p e e r 在组内接收和发送消息 并且控制消息如何传播定义了一个基本的协议。其他协议大量使用此协议提供的 功能来完成消息传播。 端点路由协议( e r p 协议) 此协议为消息发送提供到达目的对等体的路径。这是通过在对等体路由器间 互发查询请求协议消息完成的。对等体路由器在提供最基本的路由功能的同时为 实现高级的路由功能提供了接口。 而且，j x t a 是p 2 p 应用程序开发的运行平台。目前j x t a 首先推出了基于j a v a 的参考实现，提供了支持六个开发协议的j a v a a p i 。 j x t a 虚拟网络( j x t a 虚网) 是一个构建在物理网络之上的虚拟网络。j x t a 虚 网“屏蔽了实际网络中的物理特性。从另一个角度来看，对于用户而言，j x t a 虚网是一个不需要了解实际的物理构成和拓扑的虚拟网络。如图2 1 所示。 4 ， 1 i - 虚拟映射 图2 - 1j x t a 虚网与物理网络映射图 f i g u r e2 - 1m a p p i n gf r o mt h ep h y s i c a ln e t w o r kt oj x t av i r t u a ln e t w o r k j x t a 平台被分成三层。如图2 2 。每一层都是建立在其下层的功能之上，增加 了功能和行为的复杂度。如图2 2 所示，第一层是j x t a 核心层，它包含了服务所需 要的核心功能；第二层是服务层，它提供了访问j x t a 协议的接口：第三层是应用 层，它使用服务来访问j x t a 网络和j x t a 提供的功能，这样的设计和一个标准的操 作系统比较相似，标准的操作系统包括核心操作系统、服务和应用程序。 j x l a a p p l i c a t i o n t a s e r v i c e s j x t a c o f e 图2 - 2j x t a 的层次结构 f i g u r e2 - 2a r c h i t e c t u r eo fj x t a 核心层 核心层提供对于每个p 2 p 解决方案来说都是必须的基本要素。理想上，这一层 的所有元素被所有的p 2 p 解决方案所共享。核心层的元素如下所列： 1 点 2 点组 3 网络传输( 管道、端点、消息) 4 广告 5 实体命名( 标识符) 6 协议( 发现、信息、监听) 7 安全和授权机制 j x t a 提供的六个主要协议被包含在核心层。虽然这些协议以服务来实现，但 是他们被定位在平台层并且被设计成核心服务以区别于其他的服务层的服务。 核心层一就像它的名字所代表的一是j x t a 解决方案的最基本的核心。在 服务层或应用层的一个j x t ap 2 p 解决方案的其他方面都是建立在核心层所提供的 功能之上的。 服务层 服务层所提供的网络服务对每一个p 2 p 应用来说都是希望的但并不是必须的。 这些服务所实现的功能最有可能与几种不同的p 2 p 应用结合起来，如下所列： 1 资源搜索 6 2 文件共享 3 授权 服务层还包含由j x t a 项目组所增加的额外功能。建在j x t a 平台之上的服务提 供被各种各样的p 2 p 应用所要求的特殊功能，并且这些功能能被结合利用以形成一 个完整的p 2 p 应用。 应用层 应用层建立在提供我们所知道的普通p 2 p 应用的服务层功能之上的，例如即时 消息。因为一个应用可能包含仅仅一个服务或者多个服务，所以有时很难决定到 底一个应用包含那些服务。 应用层包含集成的应用程序的实现，服务层和应用层的界限并非严格划分， 对于某一客户的应用可被看成另一客户的服务。整个系统被设计成标准的，以便 开发人员选取服务和应用集来满足他们的需要。 应用层包括了应用j x t a 服务开出发来的完整的p 2 p 应用程序，例如：m y j x t a ， j x t a c a d 等应用程序。 2 1 2j x t a 中的概念 为了本文的进行，有些j x t a 网络的概念是需要熟悉和理解的，它们是从j x t a 协议中提出的一系列的专有名词。 i d ( 标识符l j x t a 使用u u i d ，一个1 2 8 位数，作为一个实体( 如对等体，广告，服务等) 的 标识符。该标识符由系统提供的算法生成，具有极高的唯一性。 j x t a 没有提供一种绝对的方式在整个社区中保证标识符的唯一性。只有在需 一要将标识符以安全的方式捆绑到其他信息，如名称和网络地址时，唯一性才是极 端重要的。在这种情况下，需要在j x t a 基础平台上实现更复杂的命名和捆绑服务。 本文在后面将把对等体的标识符简称为p e e r l d 或i d ，而其他实体的标识符将给 出其全称。 p e e r ( 对等机) p e e r 是一个虚拟的通信点。在一台计算机或者设备上可以有很多个p e e r 。一 个p e e r 并不是一个用户，因为一个用户可以有多个p e e r ，同一个设备上也可以由 多个p e e r 。因为p e e r 不等同于用户，所以需要将用户和p e e r 抽象出来并分离开。 p e e r 与特定的网络服务联系的很紧。在j x t a 的参考实现中，p e e r 可以使用网 络提供的基本服务，例如r e n d e z v o u s ( 集合点服务) 、r o u t e r ( 路由服务) 、g a t e w a y ( 网关服务) 等。这些基本服务又可以提供搜索和通信服务。一般来说，并不是 7 所有的p e e r 都使用这些服务，它们只使用这些服务的一部分。 p e e rg r o u p ( 对等组) 在j x t a 网络中，对等体自组形成对等组。对等组代表一组具有共同兴趣的对 等体，它们之间遵守一系列政策( 包括成员关系，内容共享等) 。 每一个对等组由一个唯一对等组i d 标示。j x t a 技术描述了对等组怎样被创 建，发布和发现，但没有强制规定对等组在何时，何地，以什么原因被创建。用 户，服务开发者和网络管理员可以动态划分对等体的活动范围，并以此匹配相应 的应用需求。 一个对等体可以同时加入多个对等组，而其对等体m 保持不变。 在j x t a 对等组的设计中，包含了以下目的： 为安全内容的共享创建安全域 对等组形成的逻辑区域的边界能够限制非组成员的访问权。对等组并不必然 反映下层物理网络边界，诸如路由器和防火墙形成的边界。 能够划分对等体活动范围 具有共同兴趣的对等体加入相同对等组，使得对等组将网络划分成了抽象的 区域，从而为限制消息传播范围提供了解决方案。 能够建立监控环境 对等组允许对组内的各对等体进行监控( 如流量探测，计费，追踪) 。 在默认情况下，所有对等体都加入一个默认对等组，n e t p e e r g r o u p 。新的对等 组可以在这个默认组下创建。 p i p e ( 管道) 一 在j x t a 规范定义中，对等体之间传输数据、文件、信息、代码和多媒体内容 是通过逻辑管道完成的。一个管道实例，从逻辑上讲，是对等组内的一个资源管 道的使用是通过管道服务完成的。 管道是j x t a 最基本、最重要的特性，它提供了一种很好的方案，使得p e e r 在大多数网络情况下都可以通信，而不用去管防火墙或者其他的障碍。即使你不 知道另外一个p e e r 的位置以及他所使用的协议等信息，通过管道仍然可以与之通 信。 管道作为一种抽象的方法，隐藏了一些细节。在j x t a 的参考实现中，有几 种常用的管道，如单向异步、同步请求应答、成批发送、流传送、双向、单向同 步、单向可靠安全的管道。管道还可以根据连接数目分成点到点类型和传播类型。 管道捆绑的过程是： 1 需要接收消息的对等体发布管道广告。 2 接收消息的对等体执行管道输入端的物理终结点捆绑。 8 3 希望发送消息的对等体发现管道广告。 4 ，发送消息的对等体执行管道输出端的物理终结点捆绑。 这一过程是完全在运行时进行的，意味着j x t a 管道的终结点可以在任何时刻 动态地连接到不同的物理终结点。 a d v e r t i s e m e n t ( 广告) 一个广告就是一个x m l 文档，它用来描述j x t a 的消息、p e e r 、对等组或者 服务等。通过广告在j x t a 网络内的发布，使一个对等体获得关于实体的各种信 息。并根据这些信息，完成诸如建立对等体连接的工作。j x t a 定义了一组基本的 广告，更多子类型广告可以根据需要由这些基本类型生成。 基本的广告的类型有： 对等体广告 关于对等体信息的广告。包含的信息主要有其i d 和其所在的对等组的标示 符。 对等组广告 关于对等组的广告。包含的信息主要有对等组标示符，组内服务的信息。 模块类广告 它描述了某一类模块的特性，包括模块的行为及它支持的编程接口。 模块规范广告 描述某一特定模块的特性，如运行时行为和协议，所有内建核心对等组服务( 如 发现，成员和解析器服务) 都是模块。根据该广告，开发者能实现相互间的功能。 在其中也可能描述如何调用和使用该模块，如怎样定位，装载，启动，通过管道 或者经由代理模块来使用等等。在该广告中可以包含它所依赖的其他模块规范的一 i d 。 模块实现广告 它描述了模块规范的一种实现，通常实现都可以由规范i d 找到。为了能执行 一个模块，模块实现广告提供了获得所有必要数据的手段。 管道广告 管道服务使用它来创建相关联的输入输出管道终端点。 集结点广告 它描述了在对等组内，作为集结点的对等体的信息。通过它，其他对等体可 以发现集结点。 m e s s a g e ( 消息) j x t a 消息是通过管道从个对等体传送到另一个对等体的数据段。消息被定 义为由信封和正文组成的任意大小的段。 9 信封为标准格式，包括：报头、源端点信息( u r i 格式) 、目的地端点信息( u r i 格式) 、消息摘要( 出于安全性目的，可选) 。 消息正文的长度是任意的，包含一个信任状( 出于安全性目的，可选) 及内容的 实现。 2 2p 2 p 系统及研究现状 1 9 9 8 年，美国东北波士顿大学的一年级新生，肖恩范宁为了解决他的室友 的关于如何在网上找到音乐而编写了一个简单程序，这就是n a p s t e r 的雏形。它允 许用户共享本地机器上的m p 3 音乐文件。到了1 9 9 9 年，n a p s t e r 成了人们十分关 注的程序，由于深受用户的欢迎，n a p s t e r 发展迅速，鼎盛时期曾经拥有达到8 0 0 0 万的注册用户。 而与此同时，n a p s t e r 也遭遇到了唱片公司的联合抵制，陷入了众多的版权纠 纷中。在一系列的法律诉讼之后，n a p s t e r 公司在2 0 0 1 年宣布破产。但是，n a p s t e r 的破产并没有意味着p 2 p 技术的消亡，相反，正是n a p s t e r 为p 2 p 技术的蓬勃发展 开创了一个崭新的开始。 n a p s t e r 第一次验证了p 2 p 思想在广域网范围内的可行性，在n a p s t e r 关闭之 后，更多的p 2 p 文件共享系统迅速崛起，成为i n t e m e t 发展的一股巨大浪潮，其中 最著名的是c r n u t e l l a 和k a z a a 。4 2 2 1p 2 p 的网络结构 2 2 1 1 集中式p 2 p 网络 集中式p 2 p 网络形式上有一个中心服务器来负责记录共享信息以及回答对这 些信息的查询。每一个对等实体对他将要共享的信息以及进行的通信负责，根据 需要下载他所需要的其他对等实体上的信息。这种形式具有中心化的特点，但是 又于传统的c l i e n t s e r v e r ( 客户端n 务器) 模式不同。传统的c s 模式将客户需要 的所有资料都存放在服务器上，客户只能被动的从服务器上读取信息，造成了服 务器的巨大消耗。图2 3 为传统的c s 网络结构。 l o 图2 - 3 传统的客户端朋艮务器网络结构 f i g u r e2 - 3t r a d i t i o n a lc l i e n t s e r v e rn e t w o r ka r c h i t e c t u r e 而集中式p 2 p 网络则是将网上提供的资料都分别存放在提供该资料的客户机 上，服务器上只保留索引信息，此外服务器与对等实体以及对等实体之间都具有 交互能力。采用集中式p 2 p 网络结构的软件成为第一代p 2 p ，其代表性的软件为 n a p s t e r 。n a p s t e r 的网络结构如下。 一一 一下载流 图2 _ 4 集中式p 2 p 网络架构( n a p s t e r ) f i g u r e2 - 4c e n t r a l i z e dp 2 pn e t w o r ka r c h i t e c t u r e ( n a p s t e r ) 这种形式有一个中央服务器，为用户提供共享和搜索文件服务。这就要求有 一个连续运转的服务器，服务器必须能够处理大量的用户连接，拥有足够的内存 和磁盘空间来维护和搜索文件列表。而正是这个中央服务器的存在造成了n a p s t e r 被r i a a ( 美国唱片工业协会) 告上法庭，并最终使得n a p s t e r 停止运行。为了解 决由于外界的压力而有可能导致系统停止运行的问题，于是产生了基于分布式的 p 2 p 形式。 2 2 1 2 完全分布式非结构化p 2 p 网络【7 】 完全分布式非结构化p 2 p 网络采用了随机图的组织方式来形成一个松散的网 络，其典型网络结构如图2 - 5 。 图2 5 典型的分布式非结构化p 2 p 网络 f i g u r e2 - 5t y p i c a ld i s t r i b u t e du n s t r u c t u r e dp 2 pn e t w o r k 这种结构对网络的动态变化有较好的容错能力，因此具有较好的可用性。同 时，这种结构支持复杂查询，比如带有规则表达式的多关键字查询、模糊查询等。 完全分布式非结构化拓扑的p 2 p 网络的典型代表是g n u t e l l a 3 1 。 g n u t e l l a 是一个p 2 p 文件共享系统，它和n a p s t e r 最大的区别是c m u t e l l a 完全 不需要中央服务器，它采用了完全随机图的洪泛式搜索和随机转发机制。为了控 制搜索消息的传输，g n u t e l l a 网络采用类似i p 数据包中t t l ( t i m et ol i v e ，生存 时间) 的机制来决定是否继续转发。g n u t e l l a 的查询流成如图2 - 6 所示。 查询流 下载流 图2 - 6c m u t e l l a 的查询流程 f i g u r e2 - 6s e a r c hf l o wo fg n u t e l l an e t w o r k 在完全分布式非结构化拓扑的p 2 p 网络模型中，每个节点都具有相同的功能， 既是客户机又是服务器，因此节点也被称为对等点。这种拓扑的优点是网络配置 1 2 简单，不需要服务器的支持，在网络规模较小的时候具有很高的查询效率。但是， 由于在这种拓扑的网络中多采用洪泛方式查询和定位资源，随着联网节点的增加， 网络规模不断增大，从而给网络中带来了沉重的网络负担。而且由于没有确定的 拓扑，这种形式的网络无法保证查找资源的确定性，即可能会漏过网络中的一些 资源。 由于发现的准确性和可扩展性是完全分布式非结构化网络面临的两个重要问 题，因此，目前对这种结构网络的研究集中在改进发现算法上，本文就是围绕着 这种思想开展的。 2 2 1 3 完全分布式结构化p 2 p 网络 由于非结构化拓扑的p 2 p 网络中随机搜索造成的不可扩展性，人们开始研究 如何构造一个高度结构化的系统。目前，研究的重点在于如何有效的查找信息， 最新的成果就是基于d h t ( d i s t r i b u t e dh a s ht a b l e ，分布式散列表) 的分布式发现 和路由算法。这种算法避免了类似n a p s t e r 的中心服务器，也不像g n u t e l l a 那样基 于广播进行查找，而是通过分布式散列函数将输入的关键字唯一的映射到某个节 点上，然后通过一些特定的路由算法和该节点建立连接。 分布式散列表是由广域范围的大量节点共同维护的巨大散列表。散列表被分 割成不连续的块，每个节点都被分配一个属于自己的散列块，并维护这个散列块。 d h t 的节点既是动态的，也是数量巨大的，因此非中心化和自组织成为两个重要 的设计目标。通过散列函数，节点的i d 还有资源的键值被映射到一个巨大的线性 空间里。 在d h t 技术中，网络节点按照一定的方式分配一个唯一节点标识符( n o d e i d ) ，资源对象通过散列运算产生一个唯一的资源标识符( o b j e c ti d ) ，且该资 源将存储在节点i d 与之相等或者相近的节点上。需要查找该资源时，采用同样的 方法可定位到存储该资源的节点。 d h t 类结构能够自适应节点的动态加入退出，有着良好的可扩展性、健壮性、 节点i d 分配的均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构，d h t 可以提供精确的发现。只要目的节点存在于网络中，d h t 总能发现它，发现的准 确性得到了保证。 d h t 技术最大的问题是d h t 的维护机制较为复杂，尤其是节点频繁加入退出 造成的网络波动( c h u r n ) 会极大地增加d h t 的维护代价。d h t 所面临的另外一 个问题是d h t 仅支持精确关键词匹配查询，无法支持内容语意等复杂查询。 目前已有的分布式结构化拓扑的p 2 p 网络由p a s t r y 、c h o r d 8 】和c a n 等。 2 2 1 4 混合式p 2 p 网络 集中式p 2 p 形式有利于网络资源的快速检索，并且只要服务器能力足够强大 就可以无限扩展，但是其中心化的模式容易遭到直接的攻击，分布式p 2 p 形式解 决了抗攻击问题，但是又缺乏快速搜索和可扩展性。混合p 2 p 形式【1 5 】结合了集中 式和分布式p 2 p 形式的优点，在设计思想和处理能力上都得到进一步优化。混合 式p 2 p 在分布式模式的基础上，将用户节点按能力进行分类，使某些节点担任特 殊的任务。s k y p e 即时通信软件就是用了混合式p 2 p 网络模式。通常的混合式p 2 p 系统结构图和数据流图如图2 7 和图2 8 所示。 图2 7 混合式p 2 p 网络结构 f i g u r e2 - 7h i e r a r c h i c a lp 2 pn e t w o r ks 仇l c t u r e 查询流 下载流 图2 - 8 混合式p 2 p 网络查询流程 f i g u r e2 - 8s e a r c hf l o wo fh i e r a r c h i c a lp 2 pn e t w o r k ( 1 ) 节点( 用户节点) 普通的节点就是用户节点，它不具有任何特殊的功能。 ( 2 ) 搜索节点 搜索节点处理搜索请求，从他们的孩子节点中搜索文件列表，这些节点必须 1 4 有1 2 8 k b i t s 以上的网络连接数度，因此，最好用高性能的处理器。 ( 3 ) 索引节点 连接速度快、内存充足的节点可以作为索引节点。索引节点保存可以利用的 搜索节点信息，搜索状态信息以及尽力维护网络的结构。一个节点可以既是搜索 节点又是索引节点。用户节点可以选择3 个搜索节点作为他的父节点，如果父节 点接受该用户节点作为他的孩子的话，那么该用户节点就可以提交他要共享的列 表给他的副节点。默认的情况下，搜索节点可以最多维护5 0 0 个孩子节点。 在第三代p 2 p 的软件体系结构中，采用了混合p 2 p 形式。这种形式的关键之 一是引入了索引节点，索引节点不会直接连接到有版权的资料，只是搜索和所需 资料相关的地址，至于用户到底连接下载了什么内容和他无关。这种形式的关键 之二是引入搜索节点，搜索节点管理着所属用户的文件列表。用户节点通过索引 节点获得搜索节点信息，之后用户节点就与获得的搜索节点相连，每一次查询都 通过该搜索节点进行。当用户发出搜索请求后，如果和用户节点直接相连的搜索 节点查询结果为1 0 0 个( 这里所说的1 0 0 个搜索结果可以由用户自己来设定) 就 停止，如果不足1 0 0 个，就向相邻的搜索节点发出请求，如果查询结果还不够， 就继续向外快速发散，直到所有的搜索节点都被搜索到。而如果所有的搜索节点 都被访问过，就意味着整个网络上的节点都被搜索到了，其速度要比纯p 2 p 模式 快的多。 2 2 2p 2 p 系统的应用 在i n t e m e t 大行其道的时候，p 2 p 能有此迅猛的发展是有其原因的，通过如表 2 1 的表示，就可以看出相对于i n t e m e t ，p 2 p 在技术上的优势。 因特网最初产生和发展的一个主要动力就是资源共享，也正是文件交换的需 求直接导致了p 2 p 技术的兴起，这是p 2 p 最初也是最成功的应用之一，也正是针 对这类应用的n a p s t e r 使得人们在客户端服务器模式下开始重新认识p 2 p 思想对 人们使用网络习惯的影响。 1 5 表2 1p 2 p 网络和传统网络的一些性能比较【1 】 t a b l e2 1c o m p a r i s o no f t h et r a d i t i o n a ln e t w o r ka n dp 2 pn e t w o r k t l 】 性能比较 p 2 p c s 数据发布 好差 数据接受 由 好 数据互动性好差 数据及时性好差 数据安全性差好 数据更新好差 数据质量 中 好 数据覆盖率和数量差好 数据成本控制好差 数据管理方便性 差好 随着人们对p 2 p 思想的理解和技术的发展，作为一种软件架构，p 2 p 还可以 被开发出种类繁多的应用模式，除了最初的文件交换之外，还出现了一些分布式 存储、深度搜索、分布式计算、个人及时通信和协同工作等新颖应用。另外，随 着s u n 公司将其j x t a 协议扩展到诸如个人数字助理( p d a ) 和移动电话等手持 终端上，并允许人们屏蔽具体的物理平台进行资料共享和文件交换等，p 2 p 技术在 移动通信和智能网领域也开始呈现出较大应用前景。 p 2 p 网络技术主要应用在以下一些方面。【1 】 ( 1 ) 对等计算 通过众多计算机来完成超级计算机的功能，一直是科学家梦寐以求的事情。 采用p 2 p 技术的对等计算，正是把网络中的众多计算机暂时不用的计算能力连接 起来，使用积累的能力执行超级计算机的任务。任何需要大量数据处理的行业都 可从对等计算中获利，如天气预报、动画制作、基因组的研究等，有了对等计算 之后，就不再需要昂贵的超级计算机了。在硅谷，现在有许多公司正在投入对等 计算的开发，并获得了巨大的风险资金。从本质而言，对等计算就是网络上c p u 资源的共享。 ( 2 ) 协同工作 公司机构的日益分