（计算机应用技术专业论文）基于chord协议的p2p网络模型及其搜索技术研究.pdf

基于c h o r d 协议的p 2 p 网络模型及其搜索技术研究 摘要 p 2 p ( p e e r - m p e e r ) 技术被视为2 l 世纪计算机技术的热点技术之 一，随着网络技术的飞速发展和个人计算机性能的增强，互联网的计 算模式正经历着从c s 模式向p 2 p 模式的转变。高效的资源搜索机制 是p 2 p 技术的研究重点，本文概述了p 2 p 的基本概念、体系结构以及 主要的应用领域，总结了目前主要的p 2 p 搜索算法，详细分析了非结 构化p 2 p 网络和结构化p 2 p 网络搜索算法的研究现状，并指出了各自 的优缺点。 结构化p 2 p 网络是第三代p 2 p 网络，其采用的分布式哈希表搜索 算法具有较高的查询效率，适合大规模的p 2 p 网络并且可扩展性很好， 是目前的研究热点。但是以c h o r d 为代表的结构化p 2 p 网络在构建覆 盖网络的时候没有考虑节点的实际物理地址，导致覆盖网络和底层网 络差异很大，即c h o r d 网络存在的绕路问题。本文通过对c h o r d 网络 的深入剖析，提出一个额的基于c h o r d 协议的p 2 p 网络模型。新模型 将网络中的节点按照实际物理地址的邻近性划分为不同的群组，每个 群组是一个c h o r d 环，群组之间互连构成分布式的p 2 p 网络。新模型 通过引入群首节点的概念充分考虑了节点性能的差异，同时为了增大 群组内部完成查找的概率，减少跨群组搜索的次数，提出了群首节点 的复制技术，使得新模型不但继承了c h o r d 在可扩展性和鲁棒性等方 面的优点，而且降低了网络流量，减少了路由定位开销，提高了搜索 效率。 基于新模型在拓扑结构和数据分布等方面的特点，我们提出新模 型下的二阶混合搜索算法。此算法分为群组内部查找和群组之间查找 二阶混合执行，查找以群组为基本单位，根据群组内外不同的拓扑结 构分别采用不同的搜索算法，在群组内部采用d h t 算法，在群组之间 采用非结构化p 2 p 网络普遍采用的泛洪请求搜索算法的改进算法一一 随机游走搜索算法。本算法结合了d h t 算法和随机游走算法的优点， 实验结果表明，新模型下的算法比c h o r d 网络的d h t 算法更有效。 关键词：p 2 pc h o r d 搜索算法群组分布式哈希表泛洪 随机游走 i i r e s e a r c ho nc h o r dp r o t o c o lb a s e dp e e r - t o - p e e rn e t w o r k m o d e la n ds e a r c hln gt e c h n o l o g y a b s t r a c t p 2 p ( p e e r - t o - p e e nt e c h n o l o g yh a sb e e ns e e da so n eo ft h em o s tp o p u l a r c o m p u t e rt e c h n o l o g yi nt w e n t y - o n ec e n t u r y w i t h t h en e t w o r kt e c h n o l o g y a d v a n c e sa n dp o w e ro fp c se n h a n c e s ，t h ec o m p u t i n gp a t t e r no fi n t e r n e ti s t r a n s f o r m i n gf r o mc i st op 2 p h i 曲e f f i c i e n c yr 鹤o u r c es e a r c hm e c h a n i s mi st h e r e s e a r c hk e y s t o n eo f t h ep 2 p t e c h n o l o g y t h ep a p e rr e v i e w sp 2 p sb a s i cc o n c e p t i o n n e t w o r ka r c h i t e c t u r ea n dt h ep h m a r ya p p f i c a t i o nd o m a i n t h ep r i m a r ys e a r c h i n g a l g o r i t h m sa tp r e s e n ta r cs u m m a r i z e d t h es e a r c h i n ga l g o r i t h m so fu n s t r u c t u r e d p 2 pn e t w o r k sa n ds t r u c t u r e dp a pn e t w o r k sa r ea n a l y z e da n dp m n t e do u tt h e i r a d v a n t a g e sa n dd i s a d v a n t a g e s s t r u c t u r e dp 2 pn e t w o r ki st h et h i r dg e n e r a t i o np 2 pn e t w o r k sa n di t sd h t s e a r c ha l g o r i t h mh a st h eh i i g h e rs e a r c he f f i c i e n c yw h i c hi ss u i t a b l et ol a r g e - s c a l e p 2 pn e t w o r k sa n di t se x p a n s i b i l i t yi sv e r yg o o d i ti st h es t u d yh o t s p o ta tp r e s e n t b u ts t r u c t u r e dp 2 pn e t w o r k sc h o r dh a v en o tc o n s i d e rt h ea c t u a lp h y s i c sa d d r e s s w h e nc o n s t r u c t i n gn e t w o r k sw h i c hl e a dt ot h ed i f f e r e n c eb e t w e e n c o v e r i n g n e t w o r ka n db o t t o ma c t u a ln e t w o r ki sv e r yb i g i ti st h ed e t o u r i n gp r o b l e mo f c h o r dn e t w o r k i nt h i sp a p e ran e w p 2 pn e t w o r km o d e lb a s e do hc h o r d p r o t o c o l h a sb e e np r o p o s e db yt h ed e e pa n a l y z e do fc h o r dn e t w o r k t h en e wm o d e l s e p a r a t e dt h en o d e si nt h en e t w o r k si n t od i f f e r e n tc l u s t e r sa c c o r d i n gt ot h e i ra c t u a l p h y s i c sa d d r e s sv i c i n i t y e v e r yc l u s t e ri sac h o r dn e t w o r k c l u s t e r si n t e r c o n n e c t e d c o m p o s e dt h ed i s t r i b u t ep 2 pn e t w o r k t h eh e wm o d dh a sc o n s i d e r e dt h e d i f f e r e n c eo fn o d e sc a p a b i l i t yb yl e a d i n gi n t ot h ec o n c e p to fc i n s t e rh e a d e rn o d e a n di no r d e rt oe n h a n c et h ep r o b a b i l i t yo fs e a r c hi n s i d eo fac l u s t e ra n dd e c r e a s e t h en u m b e ro ft i m e ss e a r c ha c r o s sc l u s t e r , t h er e p l i c at e c h n o l o g yo fc l u s t e rh e a d e r 1 1 1 n o d eh a sb e e np r o p o s e d t h e r e f o r et h e e wm o d e ln o to n l yi n h e r i t e dt h ea d v a n t a g e o fc h o r dn e t w o r k , b ma l s or e d u c e dt h ev o l u m eo fn e t w o r kt r a l 畸c , d e c r e a s e dt h e r o u t el o c a t i o ne x p e n s e ，e n h a n c e dt h es e a r c he f f i c i e n e y o w i n gt ot h en e wm o d e lc h a r a c t e r i s t i ci nt h er e s p e c to ft o p o l o g i c a ls t r u c t u r e a n dd a t ad i s t r i b u t i o n ，at w o - s t a g eh y b r i ds e a r c ha l g o r i t h mh a sb e e np r o p o s e d 。 t h i sa l g o r i t h mi n c l u d ec l u s t e ri n s i d es e a r c ha n dc l u s t e r ss e a r c ht w o - s t a g eh y b r i d i m p l e m e n t s e a r c h i n gb a s e do nc l u s t e ra n dr e s p e c t i v e l ya d o p td i f f e r e n ts e a r c h a l g o r i t h ma c c o r d i n gt od i f f e r e n tt o p o l o g i c a ls t r u c t u r e i n s i d et h ec l u s t e rw ea d o p t d h ts e a r c ha l g o r i t h m a n db e t w e e nt h ec l u s t e r sw ea d o p tt h er a n d o mw a l ks e a r c h a l g o r i t h mw h i c hi st h ei m p r o v e ds e a r c ha l g o r i t h mo ft h ef l o o d i n ga l g o r i t h m t h i s a l g o r i t h mc o m b i n e dt h ea d v a n t a g eo ft h ed h ts e a r c ha l g o r i t h ma n dr a n d o mw a l k s e a r c ha l g o r i t h m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mu n d e rn e w m o d e li sb e t t e rt h a nd h ts e a r c ha l g o r i t h m k e yw o r d s ：p e e r - t o p e e r ：c h o r d ：s e a r c h i n ga l g o r i t h m ；c l u s t e r ；d h t ： f l o o d i n g ：r a n d o mw a l k 广西大学学位论文原创性声明和使用授权说明 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成 果和相关知识产权属广西大学所有，本人保证不以其它单位为第一署名单位发表 或使用本论文的研究内容。除已注明部分外，论文中不包含其他人已经发表过的 研究成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提 供过重要帮助的个人和集体，均己在论文中明确说明并致谢。 论文作者签名：二套红灸御7 年多月弓同 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的i i 提下，学校可以公御论文的部分或全部内容。 请选择发布时间： 酿口时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：j 鸯；凌导师签名：霭弛睦劾刁年f 月乡同 广两大学硕士学位论文 基丁二c h o r d 协议的p 2 p 网络模型及其搜索技术研究 1 1 论文的选题背景 第一章引言 随着社会信息化进程的不断推进，网络技术的飞速发展以及计算机技术在日 常生活中的广泛应用和迅速普及，使得网络规模不断扩大，信息的种类、数量呈 爆炸式增长，用户数量与日俱增，如何在如此庞大的i n t e r n e t 上找到所需要的信 息已经成为广大用户日益关注的问题。搜索技术的诞生为人们在互联网上寻找有 价值的信息提供了一个新的思路，当时i n t e r n e t 中内容发布的主要方式是 c l i e n t s e r v e r 模式和b r o w s e r s s e r v e r 模式，数据集中在位于网络中心的中央服 务器上，客户机位于网络的边缘，用户必须通过服务器获得所需资源，信息的发 布是在中央服务器的协调下完成的。在这种模式下，客户端主机只能处于被动接 受服务器提供服务的状态，而不具有主动提供服务的能力，网络的数据处理能力 将受到中央服务器的性能以及客户机和服务器之间带宽性能的限制，当大量用户 同时访问某一应用服务器时，网络带宽大量占用，应用服务器负载过重，网络带 宽和应用服务器的性能问题将成为网络传输能力的瓶颈。虽然近年来网络带宽成 倍增长，应用服务器的性能不断提高，但i n t e r n e t 中内容发布的基本方式并没有 发生根本的变化，仍然依赖于中央服务器，致使热门网站不堪重负，而冷门网站 的空闲链路带宽却被白白的浪费，传统的c s 模式不能满足和支持目前大规模的 网络应用，由此p 2 p 技术产生了。 p 2 p 技术不同于传统的c s 和b s 模式，不再依赖中央服务器的支持，真正的 消除了中间商，使得网络中的节点以一种对等的方式共享存储空间、处理器计算 能力、网络带宽等资源，网络中的每个节点都处于平等的地位，既充当服务器向 其他节点提供服务，又充当客户机接受其他节点提供的服务，使得人们可以通过 互联网直接进行交互“1 。p 2 p 技术引导网络计算模式从集中式向分布式偏移，也就 是网络应用的核心从中央服务器向网络边缘的终端设备扩散：服务器到服务器、服 务器到p c 机、p c 机到p c 机，p c 机到w a p 手机所有网络节点上的设备都可以 建立p 2 p 对话”1 ，p 2 p 恢复了互联网的本质特征，重返“非中心化”，把权利交还 给用户。这样的对等模式一方面可以使节点之间直接进行交互，不再需要中央服 广西大学硕士学位论文 基于c h o r d 协议的p 2 p 网络模型及其搜索技术研究 务器的中转，使交流更直接，更迅速，效率更高；另一方面节点之f b 】的交互不再 依赖网络中特定的服务器，从而解决了因服务器性能引起的系统瓶颈问题，也避 免了因中央服务器的失效而导致的整个系统瘫痪，增强了系统的可扩展性，提高 了系统的可靠性。 从1 9 9 9 年起，共享音乐m p 3 的n a p s t e r 。1 软件在网络中空前盛行，引发了人 们对p 2 p 这种新的应用模式的极大关注，p 2 p 技术在互联网上引起了一场风暴。 尽管n a p s t e r 风靡一时，但其p 2 p 应用模式的运用为后来的p 2 p 发展奠定了坚实 的基础。近年来，继n a p s t e r 之后，随着g n u t e l l a e 5 j 、f r e e n e t 蜘等p 2 p 系统的巨 大成功，p 2 p 逐渐成为研究和应用的热点，受到学术界和工业界的广泛关注。p 2 p 技 术可以有效的均衡负载，充分的利用i n t e r n e t 边缘闲置的资源，包括计算、存储 和带宽等，具有良好的自组织能力和可扩展性，为未来i n t e r n e t 的多元化网络结 构提供了可持续发展的开放性平台，财富( f o r t u n e ) 杂志将p 2 p 列为影响i n t e r n e t 未来的四项科技之一”1 。随着p 2 p 技术的不断发展，使之在文件共享、大规模并行 计算、分布式数据存储、搜索引擎、通信和协作等诸多应用领域都有广泛的应用。 1 2 问题的提出及研究意义 网络规模越来越大，连入网络中的设备以及计算单元的数量和种类也越来越 多，然而位子网络边缘的这些设备以及计算单元并没有得到充分的利用，而是构 成了网络边缘的闲置资源，如果能够将这些设备以及计算单元的处理器的计算能 力、磁盘存储能力、网络带宽等资源进行充分利用将会有效缓解目前互联网所面 临的一些问题”1 。p 2 p 技术工作的基本原理就是充分利用这些网络边缘的闲置资源， 为解决目前互联网所面临的问题提供了一个新的技术，所以迅速成为目前研究的 重点。在p 2 p 的诸多应用领域中，文件共享是一个重要的应用，p 2 p 产生的本质目 的就是为了大规模的资源共享，而要想在信息量如此庞大的i n t e r n e t 上实现资源 共享，首要的前提就是快速、有效的找到并且定位资源即资源搜索技术，资源搜 索问题已经成为p 2 p 技术领域的热点问题，所以本课题把研究的重点定位到资源 搜索这个方向上。 p 2 p 网络按照其拓扑结构可分为非结构化p 2 p 网络和结构化p 2 p 网络， g n u t e l l a 是一个典型的非结构化p 2 p 网络，是纯粹的p 2 p 系统代表，它取消了中 2 广西大学硕士学位论文基于c h o r d 协议的p 2 p 网络模型及其搜索技术研究 央服务器，彻底实现了节点间的对等交互，由于其快速的发展，所以目前的许多 p 2 p 应用都是基于其建立的，但是以g n u t e l l a 为代表的非结构化p 2 p 网络存在以 下一些不足： 1 文档的存放位置与节点之间没有固定的关系。 在非结构化p 2 p 网络中，每个节点保存的是自己要共享的文档，文档放置于 何处对于其他节点来说是未知的，文档的存放位置与其文档的内容、节点的物理 地址没有任何关系。所以当查找某一文档的时候，节点只能把查询消息在网络中 盲目的扩散，而不能通过匹配要查询文档的内容和节点地址之间的关系进行快速 查找。而在结构化p 2 p 网络中，文档的存放位置是固定的，文档和节点之间存在 着函数映射关系，可以通过文档内容快速找到该文档所在的节点，提高搜索效率。 2 网络中产生大量的冗余信息，带宽占用严重。 由于在非结构化p 2 p 网络中，节点没有对文档的精确定位，只能通过查询消 息在网络中盲目扩散的方式查找信息，所以当某一节点发出查询请求时，很多节 点会重复收到查询请求，而且整个查询过程会覆盖整个网络或者很大的一个搜索 空间，导致网络中产生大量的冗余信息，带宽占用严重。据统计，p 2 p 软件占 i n t e r n e t 上运行带宽的4 0 一7 0 ，p 2 p 大量吞噬带宽，被称为i n t e r n e t 网络 带宽的杀手“。 3 网络的可扩展性不好。 随着网络规模的不断扩大，非结构化p 2 p 网络的不足表现的越来越严重，网 络流量随着查询节点个数的增加呈指数级增长，其中包含了许多不必要的重复包 流量，大量占用带宽，使得查询速度缓慢。由于网络规模较大和节点之间性能的 差异，可能造成在查询过程中一部分性能低的节点处于失效状态，导致网络的查 询成功率降低，网络的可用性、可扩展性不好。相反，在结构化p 2 p 网络中，节 点可以快速定位到所需文档的具体位置，免除了查询消息在网络中的盲目扩散， 节省了带宽，增强了网络的可靠性和可扩展性。 基于以上的论述，本课题选定结构化p 2 p 网络作为研究对象，c h o r d “”是一典 型的结构化网络代表，所以本文将在仔细分析c h o r d 网络的基础上，提出改进措 施，旨在提高p 2 p 网络的查询效率。 p 2 p 技术被视为2 1 世纪计算机技术的热点技术之一，目前国际上很多知名的 广西大学硕士学位论文基于c h o r d 协议的p 2 p 网络模型及其搜索技术研究 大公司和研究机构都参与到p 2 p 的研究中并取得了显著的成果，它的研究对我国 计算机网络技术和其他相关研究领域的发展具有重要的战略意义，我们追踪世界 热点技术，开展这一课题的研究具有一定的理论价值和实际价值，并且具有广泛 的应用前景。 1 3 本文工作 本文主要研究了以下内容： 1 概述p 2 p 的基本概念、体系结构以及主要的应用领域，总结目前主要的p 2 p 搜索算法，分析非结构化p 2 p 网络和结构化p 2 p 网络搜索算法的实现方式和研究 现状，并指出各自的优缺点，旨在提出一个资源搜索的有效方案。 2 通过对c h o r d 网络的深入剖析，提出了一个新的基于c h o r d 协议的p 2 p 网 络模型，新模型不但继承了c h o r d 在可扩展性和鲁棒性等方面的优点，同时考虑 了节点的实际物理地址和节点性能的差异，降低了网络流量，减小了路由时间开 销。 3 基于新模型在拓扑结构和数据分布等方面的特点，提出二阶混合搜索算 法，该算法结合了d h t 算法和泛洪算法的优点，实验结果表明，新模型下的算法 比c h o r d 网络的d h t 算法更有效。 1 4 本文组织 全文共分六章。 第一章，引言。主要介绍论文的选题背景，问题的提出以及研究意义，在此 基础上介绍了本论文的研究内容和论文的组织结构。 第二章，p 2 p 技术概述。本章作为全文的技术背景理论介绍，阐述了p 2 p 的基 本概念、产生、发展及其特点，详细分析了p 2 p 的体系结构，最后对p 2 p 的主要 应用领域进行论述。 第三章，p 2 p 搜索算法。总结了目前主要的p 2 p 搜索算法，在此基础上对非结 构化p 2 p 网络和结构化p 2 p 网络采用的搜索算法进行了分类论述，并指出各自的 优缺点。 第四章，基于c h o r d 协议的p 2 p 网络模型c c n m 。本章是全文的核心部分， 4 广西大学硕士学位论文基于c h o r d 协议的p 2 p 网络模型及其搜索技术研究 在详细剖析c h o r d 模型的基础上提出一个新的p 2 p 网络模型，并对该模型进行了 详细的分析论述。 第五章，c c n m 模型中的资源搜索算法。本章是在前面一章提出的模型的基 础上，提出二阶混合搜索算法，并进行模拟实现，性能分析。 第六章，总结与展望。对本论文所作的工作做了概括性的总结，并展望了今 后需要进一步完善和发展的地方。 广西大学硕士学位论文基于c h o r d 协议的p 2 p 网络模犁及其搜索技术研究 第二章p 2 p 技术概述 2 1p 2 p 的概念、产生及特点 2 1 1p 2 p 的基本概念 p 2 p 即p e e r - t o - p e e r ，称为对等计算或对等网络，是模仿人类社会 p e r s o n t o p e r s o n 的交流方式，也可以理解为伙伴对伙伴的意思。它是近几年兴 起的网络技术研究领域中的一个热点，改变了人们使用网络的方式。与c s 模式 不同的是，p 2 p 不存在专门的中央服务器，计算节点在功能上是对等的，既充当客 户机，享用其他节点提供的服务；又充当服务器，为其他节点提供服务，允许计 算节点之间的直接交流和协作，所以称为s e r v e n t “”模式，s e r v e n t 一词是由c h i e n t 和s e r v e r 构成的，代表既有客户机的功能，又能充当服务器的角色。 p 2 p 技术真正消除了中间商，不再依赖服务器，使得用户可以通过互联网直 接进行交互，而不必像以前那样登陆到服务器去浏览并且下载信息。p 2 p 恢复了互 联网的本质特征，重返“非中心化”，真| 下把权利交还给用户。目前尚没有对p 2 p 的统一定义，下面介绍几个著名的p 2 p 概念： p 2 p 是一种网络，并且网络中的每一个工作站都具有同等的能力和责任“”。 p 2 p 是利用i n t e r n e t 边缘的存储、c p u 计算周期、内容及人力等资源的一 组应用程序n ”。 i b m 为p 2 p 下了如下定义：p 2 p 系统由若干互联协作的计算机构成，且至 少具有如下特性之一：系统依存于边缘化( 非中央式服务器) 设备的主动协作，每 个成员直接从其他成员而不是从服务器的参与中受益；系统中的成员同时扮演服 务器与客户端的角色；系统应用的用户能够意识到彼此地存在，构成一个虚拟的 或实际的群体“”。 2 1 2p 2 p 的产生及发展 i n t e r a c t 的发展本身就是一个“螺旋式上升，波浪式前进”的过程，p 2 p 技术 并不是一个近几年诞生的全新的技术，它实际是互联网的本质属性之一。早在1 9 6 9 6 广两大学硕十学位论文基于c h o r d 协议的p 2 p 网络模犁及其搜索技术研究 年i n t e m e t 的前身a r p a n e t 刚出现的时候，网络的应用模式就是p 2 p ，计算机对等 相连共享网络资源，i n t e m e t 的很多应用或协议都是以对等方式工作的，i n t e r n e t 最基本的协议t c p i p 并没有客户机服务器的概念，所有的设备都是通讯平等的一 端。从1 9 9 5 年开始，i n t e m e t 进入了大爆炸时期，大量的p c 机接入i n t e r n e t ，成千 上万的人利用i n t e r n e t 来发送电子邮件、游览网页和网上购物，这些现象影响了网 络架构的发展，也直接影响了p 2 p 应用程序的发展。为了便于管理控制，很多应 用逐步演变成层次式和c s 模式，此时p 2 p 平等工作的本质受到了威胁。 直到1 9 9 9 年，1 8 岁的肖恩范宁建立的共享音乐m p 3 的软件n a p s t e r 的流行 才使得p 2 p 重新受到关注。n a p s t e r 软件提供歌迷共享m p 3 的服务“”，它与原有的 下载音乐的软件的不同之处在于n a p s t e r 的服务器上保存的是歌曲的索引，所有的 歌曲都保存在用户自己的硬盘上，所有使用n a p s t e r 软件的用户可以通过服务器索 引查询到需要的m p 3 文件后，直接连接拥有此文件的用户下载，而不是去服务器 上下载。n a p s t e r 的优势使得它在短短的时间就吸引了5 0 0 0 万用户，由于被控告侵 犯版权，n a p s t e r 网站被迫关闭。 继n a p s t e r 之后，2 0 0 0 年一个名为g n u t e l l a 的软件诞生了，该软件和n a p s t e r 有着类似的功能，它彻底取消了中央服务器，真正实现了用户之日j 的对等交互， 是真正意义的p 2 p ，出现后立即受到广泛的关注，g n u t e l l a 的出现标志着纯粹p 2 p 模式的诞生。 从此之后，p 2 p 技术快速发展，s e t i h o m e l l 7 1 是p 2 p 应用的一个著名例子， 它是由美国加州大学伯克利分校开展的寻找外星智慧生命的项目。这个项目通过 利用和i n t e m e t 相连的数目庞大的个人电脑的空闲c p u 能力来分析世界上最大的 射电望远镜获得的数据，以帮助搜集外太空信息、探索外太空智慧生命。 s e t i h o m e 通过把任务分割成很多独立的单元分布到个入计算机上运算，运算结 束后返回结果，再开始新的计算。从s e t i h o m e 项目正式启动以来，已经有5 0 0 万志愿者参加了这个项目，总计算数相当于使用超级计算机工作5 0 年【l s 】，这个项 目以p 2 p 的工作原理充分利用了分散在世界各地的计算机能力，增强了数据处理 能力，减小了开销。 7 广两大学硕士学位论文基于c h o r d 协议的p 2 p 网络模犁及其搜索技术研究 2 1 3 n p 计算模式和c s 模式的比较 当前流行的网络模式是传统的c s 模式，在此模式中，客户机位于网络的边 缘，每个客户机都连接到服务器上，接受服务器提供的资源，如图2 - 1 所示。而 在p 2 p 模式中，所有的机器都处于平等的地位，既是客户机，又是服务器，彼此 互连组成网络，如图2 2 所示。表2 一l 比较了两种模式的优缺点。 图2 - 1c s 模式 f i 9 2 - 1c s ( c l i e n t - s e r v e r ) m o d e l 8 广西大学硕十学位论文基丁c h o r d 协议的p 2 p 网络模犁及其搜索技术研究 图2 - 2p 2 p 模式 f j 9 2 - 2p e e r - t o - p e e rm o d e l 表2 - 1p 2 p 模式与c s 模式的比较 t a b l e 2 1t h ec o m p a r eo f p 2 pm o d e la n dc sm o d e l p 2 p 模式c s 模式 数据发布好差 数据接收差好 数掘互动性好差 数据安全性 差 好 容错性好差 数据传输速度好差 数据更新好差 数据成本控制 好差 数据管理性 差 好 可扩展性好差 9 r 阳大学硕士学位论文墓丁- c h o r d 协议的p 2 p 网络模犁及其搜索技术研究 2 2p 2 p 的体系结构 p 2 p 网络是构建于现存的底层物理网络基础之上的网络，所以又称为p 2 p 覆 盖网络。p 2 p 网络通常有按照服务器的集成度和按照p 2 p 覆盖网络的拓扑结构两种 划分标准，按照服务器的集成度即网络中是否存在中央服务器的标准，可将p 2 p 网络划分为集中式p 2 p 网络、完全分布式p 2 p 网络和混合式p 2 p 网络；按照覆盖 网络的拓扑结构可划分为非结构化p 2 p 网络和结构化p 2 p 网络。 2 2 1 按照服务器的集成度划分 ( 1 ) 集中式p 2 p 网络。该网络存在一个中央目录服务器，目录服务器负责 管理和维护网络中所有节点的目录信息。它不像传统的c s 模式那样把所有节点 的信息都保存在中央目录服务器上，它的服务器只存储每个节点的索引信息，而 节点的所有具体信息都保存在节点本身。集中式p 2 p 网络的典型代表是n a p s t e r 。 如图2 - 3 所示。 ( 2 ) 完全分布式p 2 p 网络。该网络和集中式p 2 p 网络相比的主要区别就是 不存在中央目录服务器，网络中所有节点在功能上是对等的，既是客户机，又是 服务器，节点通过与其邻居节点之间的连接组成整个网络，不再需要中央服务器 的协调。完全分布式p 2 p 网络的典型代表是g n u t e l l a 。如图2 - 4 所示。 图2 - 3 集中式p 2 p 网络 f i 9 2 3 c e n t r a l i z e dp 2 pn e t w o r k o 图2 - 4 完全分布式p 2 p 网络 f i 9 2 - 4d e c e n t r a l i z e dp 2 pn e t w o r k 广西大学硕士学位论文基于c h o r d 协议的p 2 p 网络模型及其搜索技术研究 ( 3 ) 混合式p 2 p 网络。该网络融合了以上两种网络的优点而形成。在混合 式p 2 p 网络中，选择网络中那些具有较高带宽、较大内存和较强的c p u 处理能力 的节点作为“超级节点”( s u p e r - p e e r ) ，超级节点可以存储其周围一部分节点的 数据信息，作为这些节点的中央服务器，那么这部分网络就相当于集中式p 2 p 网 络，而且这些超级节点再以完全分布式的方式互相连接构成一个p 2 p 网络，称为 混合式p 2 p 网络。混合式p 2 p 网络中超级节点的选择是动态的，它们同普通节点 一样可以随时离开网络，一旦网络发现某个超级节点不再工作，就会采用某种选 择机制重新选择一个高性能的节点担任超级节点。混合式p 2 p 网络的典型代表是 k a z a a “”和m o r p h e u s 。如图2 - 5 所示。 图2 - 5 混合式p 2 p 网络 f i 9 2 5h y b r i dp 2 pn e t w o l | 【 2 2 2 按照覆盖网络的拓扑结构划分 ( 1 ) 非结构化p 2 p 网络。该网络中的节点随机地连接在一起，节点之间的 连接是不规则的，无需遵循特定的原则，所以非结构化p 2 p 网络的优点是具有很 强的动态性，节点可以随时加入和离丌网络。但是在这种网络中文档的存放位置 和节点之间没有明确的定位关系，每个节点保存的是自身共享的文档，文档放置 广i i i 大学硕七学位论文基于c h o r d 协议的p 2 p 网络模璎及其搜索技术研究 于何处对于其他节点来说是未知的，所以非结构化p 2 p 网络的缺点是要经过很大 范围的搜索才能查询到理想的文档。其基本结构如图2 - 6 所示。 图2 - 6 非结构化p 2 p 网络 f i 9 2 - 6 u n s t r u c t u r e dp 2 pn e t w o r k ( 2 ) 结构化p 2 p 网络。该网络中的节点之间连接成规则的拓扑结构，节点 的加入和退出需要遵循一定的原则。在结构化p 2 p 网络中，文档存放的位置是固 定的，文档和节点之间存在着函数映射关系，节点存储的文档不一定是其自身共 享的或者是感兴趣的，而是通过一定函数关系映射的，这种映射关系使得查询能 够很快的定位到要查询的文档，所以结构化p 2 p 网络具有很好的可扩展性的优点。 其基本结构如图2 - 7 所示。 图2 7 结构化p 2 p 网络 f i 9 2 7 s t r u c t u r e dp 2 pn e t w o r k 广西人学硕七学位论文基于c h o r d 协议的p 2 p 网络模型及其搜索技术研究 2 3p 2 p 主要应用 p 2 p 技术具有广泛的发展前景，目前主要有以下几个方面的应用： ( 1 ) 信息资源共享 信息资源共享是p 2 p 技术产生的主要目的和根本动力，p 2 p 技术的出现改变 了传统共享信息的方式，无需再通过w e b 服务器，用户可以直接从任意一台计算 机上下载信息，实现了资源的全面共享，避免了w e b 服务器的瓶颈问题。采用p 2 p 的方式共享信息资源，可以充分的利用网络带宽，提高共享效率，目前流行的p 2 p 文件共享系统有g n u t e l l a 、f a s t t r a c k l 2 1 捌、f r e e n e t l 2 a 】、k a z a a 、b i t t o r r e n t l 2 4 1 等。 ( 2 ) 对等计算 对等计算是p 2 p 技术的一个重要应用，目的是共享网络上数目庞大的计算机 暂时不用的c p i j 资源，将这些资源积累起来，用以完成以往需要超级计算机来完 成的任务。在对等计算中，任务被分割成许多独立的单元，分配给网络中的计算 机进行独立计算，计算结束后返回结果，领取新的任务再开始新的计算。任何需 要处理大量数据的行业都可以通过对等计算大大降低计算成本，如天气预报、动 画制作、基因组的研究等。s e t i h o m e 就是对等计算中的著名例子。 ( 3 ) 搜索引擎 搜索引擎是目前人们在网络中检索信息资源的主要工具，目前的搜索引擎如 g o o g l e 和b a i d u 等都是集中式的搜索引擎，这种搜索模式是由一个机群在互联网 上盲目读取信息，然后按照某种算法根据关键字将信息保存在一个海量数据库内， 当用户提交搜索请求的时候，实际上是在海量数据库内部进行搜索。这种搜索机 制虽然能尽快获得搜索结果，但是不能保证搜索范围的深度和结果的时效性。运 用p 2 p 技术开发的搜索工具使用户深度搜索文档成为可能，为互联网的信息搜索 提供了一个新的思路。p 2 p 网络模式中节点之间的动态而又对等的互联关系使得搜 索可以在对等点之间直接地、实时地进行，无需依赖w e b 服务器，既可以保证搜 索的实时性，又可以达到很好的搜索效果。 ( 4 ) 实时通信 实时通信是目前互联网上最流行、使用最广泛的应用，它为用户之间的实时 交流提供了虚拟平台，目前著名的实时通信系统包括m s n ，i c q ，o i c q 等，尽管目 前的实时通信技术都存在中央服务器，但中央服务器仅用来控制用户的身份认证 广西人学硕十学位论文基于c h o r d 协议的p 2 p 网络模型及其搜索技术研究 等基本信息，并帮助完成节点之间的初始连接工作，而节点之间直接进行数据通 信。 ( 5 ) 协同工作 协同工作是指多个用户之问利用网络中的协同计算平台来共同完成某项任 务，共享信息资源等”。目前企业机构的日益分散、企业和客户之自j 工作方式及 环境的变化促进了p 2 p 技术在协同工作方面的发展。p 2 p 技术可以使i n t e r n e t 上 任意两台计算机建立实时的连接，建立一个安全的共享虚拟空间，进行同步及非 同步的协同工作。p 2 p 技术帮助企业和客户之间建立了一种安全的网上联系方式， 提高了彼此之间的合作效率和生产的发展，使人们方便快捷的在互联网上进行实 时信息交流。 除了上面介绍的几种主要应用外，随着研究的深入，p 2 p 技术将快速发展， 在更多的领域具有广泛的应用。 2 4 本章小结 本章介绍了p 2 p 的基本概念、产生和发展，并将其与传统的c s 模式进行比 较，分别按照服务器的集成度和p 2 p 覆盖网络的拓扑结构两种划分标准分析了p 2 p 网络的体系结构，最后对p 2 p 的主要应用领域进行了论述，作为后续章节的理论 基础。 1 4 广西大学硕士学位论文基于c h o r d 协议的p 2 p 网络模璎及其搜索技术研究 第三章p 2 p 搜索算法 3 1 主要的p 2 p 搜索算法 目前的p 2 p 搜索算法主要有集中目录式搜索算法、泛洪搜索算法和分布式哈 希表搜索算法三类。 3 1 1 集中目录式搜索算法 集中目录式搜索算法主要适用于集中式p 2 p 网络，网络中所有节点共享的文 档目录被存储在一个中央目录服务器上，新加入的节点将其要共享的文档目录上 传到中央目录服务器上，并由服务器对这些目录信息进行索引。查询时节点向目 录服务器发起搜索请求，由目录服务器检索其存储的文档索引目录后返回匹配文 档的节点地址给发起节点，然后文档的传输就在两个节点之间直接进行，不再需 要通过中央目录服务器。 集中目录式搜索算法的查询思想简单，具有较高的查询效率，可以提供快速 准确的搜索服务，但是存在的最大明显缺点就是中央目录服务器的系统瓶颈问题 和可扩展性较差。 3 1 2 泛洪请求搜索算法 在泛洪请求搜索算法( f l o o d i n g ) 中，发起节点向其所有的邻居节点广播查 询请求，邻居节点再向自己的邻居节点广播，这个过程不断地进行下去直到消息 生存时间t t l ( t i m e t o l i v e ) 值为0 ，搜索过程结束。t t l 是指消息在网络中能 够继续传播的次数，是为了限制搜索范围而给消息设置的一个初值，消息每经过 一个节点，t t l 值减1 。 泛洪请求搜索算法的优点是搜索实现方式简单，但是在泛洪搜索算法中，由 于节点没有对文档的精确定位，所以要想搜索到查询结果，要经过整个网络或者 是一个很大的搜索范围，这样便导致网络中产生大量的冗余查询消息。尤其当网 络规模比较大，节点之b j 的连通度比较高的时候，网络中的冗余搜索消息将随着 节点数目的增加而呈指数级增长。 】5 广西人学硕七学位论文基于c h o r d 协议的p 2 p 网络模璎及其搜索技术研究 例如在图3 一l 中，仅有5 个节点的全连通图，若节点a 以泛洪的方式查找某 一消息，则a 将查询消息发送给其邻居节点b 、c 、d 、e ，节点b 接到消息后再发 送给c ，d 、e ，节点c 发送给b 、d 、e ，节点d 发送给b 、c 、e ，节点e 将消息发 送给b 、c 、d ，这仅仅是节点b 、c 、d 、e 接收到节点a 发送的查询消息后的第一 次泛洪。从上面的消息传输路径我们可以看出，在第一次泛洪中，节点a 给其邻 居节点发送消息后，图中的其他4 个节点都已经收到了消息，而节点b 、c 、d 、e 再次发送的1 2 条消息都是冗余消息，冗余消息占第一次泛洪消息总量的3 4 。大 量的冗