（计算机应用技术专业论文）基于文件流行度的无结构p2p搜索机制研究.pdf

摘要 摘要 近年来以g n u t e l l a 和k a z a a 为代表的无结构p 2 p 文件共享系统已经成为当 前i n t e m e t 中最重要的应用之一。现有p 2 p 文件共享系统采用的洪泛搜索机制会 产生大量的冗余查询消息；同时由于没有对不同流行度的文件进行区别对待， 使得针对流行文件的查询常常获得过多的结果，间接地造成了网络资源的浪费， 而针对稀缺文件的查询却难以获得满意的结果。针对上述两个问题，本文在基 于闲谈的文件流行度判定方法基础上，提出了一种基于l o g l o g 算法的判定方法， 并把该判定方法分别与e x p a n d i n gr i n g 和预算搜索机制相结合，产生了两种基 于文件流行度的资源搜索机制。 这两种搜索机制都能根据文件的流行度动态地调整搜索范围，使得针对流 行文件的查询返回满足需要、但不至于过多的结果，而针对稀缺文件的查询返 回尽可能多的结果。基于文件流行度的e x p a n d i n gr i n g 机制通过调整t t l 值控 制查询范围，由于查询范围随t t l 呈指数增长，因此该机制控制查询范围的精 确性不太高；而预算机制通过预算值控制的查询覆盖范围是可以连续变化的， 因此基于文件流行度的预算机制可以根据文件流行度调整预算值从而更精确地 控制查询的覆盖范围。 本文在模拟环境下对文件流行度判定方法和这两种搜索机制进行了测试。 实验结果表明，本文的文件流行度判定方法估算出的流行度比基于闲谈的判定 方法更接近真实流行度。在取得相同查询满意度的情况下，基于文件流行度的 e x p a n d i n gr i n g 比c m u t e l l a 洪泛节约了3 7 6 的带宽，而基于文件流行度的预算 机制比c m u t e l l a 洪泛节约了5 4 4 的带宽；此外，这两种搜索机制的查询响应时 间都接近于g n u t e l l a 洪泛机制。 关键词：无结构p 2 p ，洪泛，e x p a n d i n gr i n g ，l o g l o gc o u n t i n g 算法，预算 a b s t r a c t i nr e c e n ty e a r s ，u n s t r u c t u r e dp 2 pf i l e - s h a r i n gs y s t e m ss u c ha u sg n u t e l l aa n d k a z a ah a v eb e c o m et h em o s ti m p o r t a n ta p p l i c a t i o n si ni n t e r n e t h o w e v e r , t h e f l o o d i n gs e a r c h m e c h a n i s mw h i c hi s w i d e l yu s e di n t h e s ef i l e s h a r i n gs y s t e m s g e n e r a t e sal o to fr e d u n d a n tq u e r ym e s s a g e s f u r t h e r m o r e ，b e c a u s ei tu s e st h es a m e s e a r c h i n gs t r a t e g yf o rt h ei t e m sw i md i f f e r e n tp o p u l a r i t y , q u e r i e sf o rp o p u l a ri t e m s g e tf a rm o r er e s u l t st h a nn e e d e d ，c a u s i n gal a r g ea m o u n to fn e t w o r kt r a f f i c o nt h e o t h e rh a n d ，q u e r i e sf o rr a r ei t e m sc a n n o tr e t r i e v ed e s i r e dn u m b e ro fr e s u l t s t od e a l 、7 l ，i t l lt h e s ep r o b l e m s ，w ep r o p o s ea l o g l o gc o u n t i n ga l g o r i t h m - b a s e di t e mp o p u l a r i t y e v a l u a t i n gm e t h o di n t h el i g h to fag o s s i p - b a s e dp o p u l a r i t ye v a l u a t i n gm e t h o d m o r e o v e r , w eg a i nt w op o p u l a r i t ) r b 鹪o ds e a r c h i n gm e c h a n i s m sb yc o m b i n i n gt h i s m e t h o dw i t he x p a n d i n gr i n ga n db u d g e ts e a r c h i n gm e c h a n i s m sr e s p e c t i v e l y t h e s et w os e a r c h i n gm e c h a n i s m sc a na d j u s tt h es e a r c h i n gs c o p ea c c o r d i n gt ot h e p o p u l a r i t yo ft h eq u e r i e di t e m s ，s ot h a tq u e r i e sf o rp o p u l a ri t e m sw i l lg e te n o u g h ，b u t n o tt o om a n yr e s u l t s ，w h i l eq u e r i e sf o rr a r ei t e m sw i l lg e t 嬲m a n yr e s u l t s 硒p o s s i b l e p o p u l a r i t y - b a s e de x p a n d i n gr i n gs e a r c h i n gm e c h a n i s mc o n t r o l st h es e a r c h i n gs c o p e b ya d j u s t i n gt t l b e c a u s et h es e a r c h i n gs c o p eg r o w se x p o n e n t i a l l yw i t ht t l ，t h i s m e c h a n i s mc a n n o tc o n t r o lt h es e a r c h i n gs c o p ea c c u r a t e l y o nt h eo t h e rh a n d ，t h e s e a r c h i n gs c o p eo ft h eb u d g e ts e a r c h i n gm e c h a n i s mc a nb ec h a n g e dc o n t i n u o u s l yb y a d j u s t i n gt h eb u d g 吒s op o p u l a r i t y - b a s e db u d g e ts e a r c h i n gm e c h a n i s mc a nc o n t r o l t h es e a r c h i n gs c o p em o r e a c c u r a t e l yb ya d j u s t i n gt h eb u d g e ta c c o r d i n gt ot h e p o p u l a r i t yo f t h eq u e r i e di t e m s e x t e n s i v es i m u l a t i o ne x p e r i m e n t sh a v eb e e nd o n et oe x a m i n et h ep e r f o r m a n c e o ft h ei t e mp o p u l a r i t ye v a l u a t i n gm e t h o da n dt h et w os e a r c h i n gm e c h a n i s m s t h e s i m u l a t i o nr e s u l t ss h o wt h a tt h ei t e mp o p u l a r i t ye v a l u a t e db y0 1 1 1 m e t h o di sc l o s e rt o t h er e a l p o p u l a r i t yt h a nt h a to ft h eg o s s i p - b a s e dp o p u l a r i t ye v a l u a t i n gm e t h o d c o m p a r e d t o f l o o d i n g s e a r c h m e c h a n i s m ，p o p u l a r i t y - b a s e de x p a n d i n g 黜n g s e a r c h i n gm e c h a n i s mr e d u c e sm e a nq u e r yb a n d w i d t hu s a g eb y3 7 6 ，w h i l e a b s t r a c t p o p u l a r i t y - b a s e db u d g e ts e a r c h i n gm e c h a n i s mr e d u c e sm e a nq u e r yb a n d w i d t hu s a g e b y5 4 4 a tt h es a m et i m e ，t h er e s p o n s et i m eo ft h et w os e a r c h i n gm e c h a n i s m si s a l m o s tt h es a m ea st h a to ft h ef l o o d i n gs e a r c h i n gm e c h a n i s m k e yw o r d s ：u n s t r u c t u r e dp 2 pn e t w o r k s ，f l o o d i n g , e x p a n d i n gr i n g , l o g l o g c o u n t i n ga l g o r i t h m ，b u d g e t i l l 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：刘乾 p o g 年5 只玛e t 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 。 学位论文作者签名：刘靴 卫。奄孑 年j 月j - 3 日 第一章引言 第一章引言 第一节课题背景 对等网络( p e e r - t o p e e r ，p 2 p ) 是建立在i n t e m e t 上的覆盖网( o v e r l a y n e t w o r k ) ，不同于传统的客户服务器( c l i c n t s e r v e r ，c s ) 模式，它改变了集 中存储和处理资源的方法。顾名思义，对等网络中每个节点的地位都是对等的， 每个节点既充当服务器，为其它节点提供服务，同时也充当客户机，享用其它 节点提供的服务。这种分散的自治式网络模式使得人们不再依赖于某一台服务 器、某一条网络链路，而是依赖于众多的网络节点。 事实上，对等网络并非新技术，而是旧有技术的新应用模式。自i n t e m e t 诞 生之日起，对等计算的思想就已经存在。i n t e r n e t 上最基本的t c p i p 协议也是对 等的，在t c p i p 协议中，并没有客户端和服务器的概念，在通讯过程中，所有 的设备都是平等的。但是限于当时个人计算机的性能，建立在t c p i p 之上的软 件大多采用了c s 模式。上个世纪9 0 年代后期，随着网络服务的增长，服务器 端越来越不堪重负，而客户端空闲的链路带宽被白白浪费，再加上个人计算机 的性能在速度和处理能力方面有了突飞猛进的发展，人们开始意识到可以把服 务器软件放在个人计算机上，而且可以在个人计算机间初始化全双工的信息流， 这就导致了对等网络技术的复兴。 对等网络最为人们所熟知的应用在于文件共享，例如著名的n a p s t e t 【l 】就是 利用对等网络提供相互共享音乐文件的一种服务，并取得了巨大的成功。对等 网络的应用并不局限于文件的共享，目前p 2 p 技术主要有以下几个发展方向： 1 ) 文件共享服务 文件共享服务是目前i n t e r n e t 上最主要、最为成功的p 2 p 应用。用户利用基 于p 2 p 的网络协议，直接从含有所需文件的对等节点下载文件，从而摆脱了对 特定服务器的依赖。应用实例包括n a p s t e r ，g n u t e l l a 2 1 和k a z a a e 3 1 等。 2 ) 网络存储 随着网络规模的扩大，人们开始将传统的局域存储技术向基于互联网的数 据存储系统发展。一些研究项目开始采用p 2 p 技术来组织和存储数据，这些项 第一章引言 目的目标都是提供面向全球的数据存储服务。应用实例包括o c e a n s t o r e 4 、p a s t 5 】 和c f s 6 等。 3 ) 对等计算 对等计算是分布式计算的思想在广域网上的延伸，目的是把网络中的众多 计算机暂时不用的计算资源连接起来，充分利用这些资源执行以往需要超级计 算机来完成的任务，从而减少对价格昂贵的高性能计算机的需求。在对等计算 中，大型的计算任务被分解成很多个小的分片，分别分配给网络中的节点独立 执行。许多需要大量数据处理的行业都可以从对等计算中获利，如基因组的研 究、天气预报、动画制作等。这种应用的实例包括s e t i h o m e z l t 【ix e n o s e r v e r s i s 世 乎o 4 ) 协同工作 对等网络的自主连接特征和直接交互模式使其非常适合在分布式环境下构 建用户级协同应用。对等网络可以让一个工作小组建立和管理同步及非同步的 协同合作。利用对等网络技术，可以增进成员间的合作效率，减少在多个项目 间再评估和协调的时间，每个成员都可以访问最新的数据、分享彼此的资源。 例如协同办公软件g r o o v e 9 】就是基于p 2 p 来实现协作。 5 ) 即时通讯 即时通信技术是网络中重要的通信技术。在基于p 2 p 技术的通信中，交流 双方的通信完全是节点之间直接进行数据通信，不依赖服务器的性能和带宽。 尽管目前的即时通讯技术一般都带有中心服务器，但中, c a i 艮务器仅仅是用来控 制用户的认证信息等基本信息，帮助完成节点之间的初始连接工作。这种应用 实例很多，包括m s n 1 0 1 、i c q t l l l 、s k y p e t l 2 】等。 除了上面介绍的对等网络常见的应用之外，随着对等网络技术的逐渐成熟， 还出现一些正在发展的、新的应用。例如，用网络上不同地点的多个节点来检 测、监测和鉴别恶意行为；用散布在i n t e r n e t 上的计算机来创建一个精确和实时 的网络交通图；通过对等网络改变i n t e r n e t 现有层次化的d n s 结构，建立分布 式的基于对等网络的域名服务系统；利用对等网络技术，建立分布式的电子邮 件系统，在邮件发送者和接受者之间建立直接的链接，不必通过邮件服务器； 利用对等网络技术进行负载均衡等。 有关对等网络的研究方兴未艾，国际上许多知名的大公司和一流的研究机 构及大学纷纷加入到对等网络的研究行列中，并取得了一批显著的成果。在工 2 第一章引言 业界，重要的软硬件生产商，如m i c r o s o f t 、s u nm i c r o s y s t e m s 等公司都致力于 推出基于对等计算的分布式平台。例如，m i c r o s o f t 的f a r s i t e 1 3 】，s u n m i c r o s y s t e m s 的j x t a 1 4 平台等。在学术界，来自计算机网络、数据库、计算理 论等多个领域的学者纷纷投入到p 2 p 系统的拓扑、协议、路由算法、底层支持 平台和上层应用系统等各个方面的研究中。自2 0 0 1 年起，a c ms i g c o m m 1 5 】、 i e e ei n f o c o m 1 6 等计算机领域的重要学术会议上先后开始发表了关于对等计 算的学术论文；从2 0 0 2 年开始，出现了大量的以对等计算为主题的学术会议， 著名的包括i n t e r n a t i o n a lw o r k s h o po np e e r - t o p e e rs y s t e m ( i p t p s ) 【1 7 】、i e e e i n t e r n a t i o n a lc o n f e r e n c eo np e e r - t o p e e rc o m p u t i n g t l 8 j 等。这些充分表明了工业界 和学术界对于对等网络技术的重视和其发展的潜力。 第二节本文研究内容及研究意义 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 ) 机制进行资源搜索【r 礓1 8 】。这种机制具有节点覆盖率高、 查询成功率高、命中结果数目多、健壮性好、响应时间快等优点，但是，洪泛 有个很严重的问题，就是会产生大量的冗余消息。此外，洪泛搜索机制没有对 不同流行度的文件区别对待，从而导致针对流行文件的查询，系统能够以较短 的响应时间搜索到大量的结果，但结果可能远远超出需求，间接地造成大量网 络资源的浪费；而针对稀缺文件的查询，系统在经过较长的响应时间后，可能 仍难以搜索到足够多的结果，甚至搜索不到结果而造成查询的失败。 本文研究的重点是如何判定文件的流行度以及如何根据文件的流行度动态 调整查找的覆盖范围，从而减少网络带宽消耗，提高p 2 p 文件共享网络的可扩 展性。本文中，文件的流行度是指该文件的副本数与系统中节点数目的比值， 文件的副本数越多，则该文件的流行度越大。由于文件的副本数不会超过，因 此流行度的范围是o 1 。 3 第一章引言 本文第四章在基于闲谈的文件流行度判定方法基础上，提出了一种基于 l o g l o g 算法的文件流行度判定方法，并通过模拟实验验证了新判定方法的有效 性。实验结果表明，改进的文件流行度判定方法估算出的流行度比原有判定方 法更接近真实流行度，原有判定方法判定结果的平均相对偏差为0 7 3 5 ，而改进 的判定方法判定结果的平均相对偏差为0 3 6 4 。 本文第五章将文件流行度判定分别与e x p a n d i n gr i n g 和预算搜索机制相结 合，产生了两种基于文件流行度的、自适应的、适用于类g n u t e u a 无结构p 2 p 网络的资源搜索机制。这两种搜索机制都能根据文件流行度动态调整搜索范围， 使得针对流行文件的查询返回满足需要、但不至于太多的结果，而针对稀缺文 件的查询返回尽可能多的结果，这样既能减少查询开销，又能得到满意的结果。 基于文件流行度的e x p a n d i n gr i n g 搜索机制在e x p a n d i n gr i n g 的基础上，通过 调整初始t t l 值更加准确地控制查询的覆盖范围，但由于覆盖范围随t t l 呈指 数增长，因此该方法控制查询范围的精确性不太高。而预算机制查询的覆盖范 围是可以连续变化的，因此基于文件流行度的预算机制可以根据文件流行度调 整预算值从而更精确地控制查询的范围。实验结果表明，在取得相同查询满意 度的情况下，基于文件流行度的e x p a n d i n gr i n g 比c m u t e l l a 洪泛节约了3 7 6 的 带宽，而基于文件流行度的预算机制比g n u t e l l a 洪泛节约了5 4 4 的带宽。 第三节论文结构 本文共分为六个部分，具体结构如下： 第一章介绍本文的课题背景、研究内容及研究意义。 第二章介绍p 2 p 的基本概念、特点和p 2 p 文件共享系统按照拓扑结构的分 类，并分析各种拓扑结构的优缺点以及选择无结构而不是结构化p 2 p 的原因。 第三章介绍g n u t e l l a 网络协议和g n u t e l l a 系统的特性，并介绍当前p 2 p 采 用的洪泛搜索机制以及一些改进的搜索机制。 第四章阐述基于l o g l o g 算法的文件流行度判定方法，并通过仿真验证了该 判定方法的有效性。 第五章提出两种基于文件流行度搜索机制，并通过仿真检验了这两种搜索 机制的性能。 第六章对论文进行了简要的总结，并提出了今后的研究方向。 4 第二章p 2 p 网络概述 第二章p 2 p 网络概述 第一节p 2 p 的概念 p 2 p 网络，也称为对等网络。在p 2 p 网络中，每个节点( p e e r ，如i n t e m e t 中的个人计算机) 都拥有对等的功能与责任，即每个节点既充当服务器向其它 的节点提供数据或服务，又作为客户机享用其它节点提供的数据或服务。 目前，p 2 p 技术还处于不断发展阶段，因而尚未给出一个精确的定义。一种 常见的p 2 p 的定义是：p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的 一部分硬件资源( 处理能力、存储能力、网络连接能力、打印机等) ，这些共享 资源需要由网络来提供服务和内容，能被其它对等节点直接访问而无需经过中 间实体。在此网络中的参与者既是资源提供者，又是资源获取者。一些著名研 究机构和研究人员还给出了对等网络的其它一些定义： i b m 给出的定义为：p 2 p 系统是由若干互联协作的计算机构成，且至少具 有如下特征之一：系统依存于边缘化( 非中央式服务器) 设备的主动协作，每 个成员直接从其他成员而不是从服务器的参与中受益；系统成员同时扮演服务 器与客户机两种角色；系统成员能够意识到彼此的存在，并构成一个虚拟或实 际的群体l l 引。 c l a ys h i r k e y 给出的定义为：p 2 p 是利用i n t e r n e t 边缘各种可用资源( 如存储 空间、计算能力、媒体内容等) 的一类应用。因为访问这些分散化的资源意味 着在一个连通性不稳定和d 地址不可预测的环境中进行，所以p 2 p 节点必须能 够独立于d n s 系统运行且高度自治 2 0 】。 p 2 p 工作组给出的定义为：p 2 p 通过在系统之间直接交换来共享计算机资源 和服务，这些资源和服务包括信息交换、高速缓存、处理能力和存储空间【2 1 1 。 m i k em i l e r 给出的定义为：p 2 p 是一个网络体系，其中每个计算机具有相同 的能力和责任。m i k em i l e r 定义了五个关键特性：网络提供节点间实时的数据传 输和消息传递；节点既是客户机，又是服务器；网络的内容是由分散的节点提 供；节点具有网络控制权和自治权；网络允许节点随时加入和退出、可以没有 永久的口地址 2 2 1 。 5 第二章p 2 p 网络概述 总之，p 2 p 是一个用于资源共享的网络节点群体，每个节点向群体提供资源 同时作为回报从群体中获取所需资源。网络中每个节点自治又彼此依赖，所谓 自治是指每个节点独立决定自己的行为而不受其它节点的控制，所谓依赖是指 每个节点需要相互协作获得信息资源和计算资源。 第二节p 2 p 的特点 p 2 p 模式和目前流行的c s 模式有着本质上的区别。在c s 模式中，当用户 间要进行信息资源的传输活动时，首先要构建一个有一定资源的服务器，然后 在其它地方( 大多数为在个人计算机上) 创建信息并“发布 到服务器上。这 些信息在服务器上等待请求。接收到请求之后，服务器将信息传递给请求者。 整个过程需要三步，a p 仓, j 建信息一发布信息一查看信息。图2 1 是一个典型的 c s 模式的体系结构。 图2 1c s 模式的体系结构 c s 模式具有以下特点【2 3 1 。 1 ) 采用集中计算方式，存在客户端和服务器之分。信息和数据都保存在服 务器端，每台服务器所能提供的信息数量受到自身存储空间的限制。客户端基 本上只是一个高性能的i o 设备，上面大量的资源和服务被闲置。 2 ) 服务器及网络的带宽决定了整个网络的性能，任意时刻它所能支持的客 户端访问数量受到自身处理能力以及网络吞吐能力的限制。随着客户端的增加， 服务器的负载就越来越重，成为系统的瓶颈。 3 ) 一旦中央服务器崩溃，整个网络也随之瘫痪。 4 ) 信息的分布与生存期十分稳定。通常，发布的信息将会在服务器上稳定 的保存较长的一段时间，并且该服务器也不间断地运行在网络上。 6 第二章p 2 p 网络概述 5 ) 存储与管理比较集中，服务器根据适当的算法和规则管理本地信息，应 答客户端的访问请求。 同样是进行信息资源的传输，在p 2 p 模式下则有很大不同。处于对等地位 的节点可以直接向存储信息的对等节点发送请求。而接收到请求的节点可以直 接将需要的信息发送给对方。整个过程只需两步，即创建信息一查看信息。图 2 2 是一个典型的p 2 p 模式的体系结构。p 2 p 模式具有以下特础2 4 2 5 】。 1 ) 节点对等性：每个节点具有相同的地位，既可以请求服务也可以提供服 务，同时扮演c s 模式中的服务器和客户端两个角色。这是和传统的c s 模式 最大的差别。 2 ) 非中心化：网络中的资源和服务分散在所有节点上，信息的传输和服务 的实现都直接在节点之间进行，可以无需中间环节和服务器的介入，避免了可 能的瓶颈。非中心化的特点给p 2 p 带来了在可扩展性、健壮性等方面的优势。 3 ) 可扩展性：p 2 p 网络的规模随着加入节点的数量的增长而增长，新节点 的加入会给系统增加新的资源。整个体系是全分布的，不存在瓶颈。从理论上 讲，p 2 p 网络的可扩展性几乎是无限的，可以达到现有的i n t e r n e t 规模。 图2 2p 2 p 模式的体系结构 4 ) 节点的自治性：p 2 p 网络中的节点具有高度的自治性，它们的行为不受 任何第三方的限制。系统中的任意一个节点主要关注本地的事务；可以独立自 主地决定哪些本地资源可以被共享以及共享权限等；并且当节点离开p 2 p 系统 时仍然是一个功能完备的计算机系统。 5 ) 节点的异构性和动态性：p 2 p 系统中各个节点的c p u 处理能力、存储 能力、带宽以及他们在系统中的滞留时间均有很大的不同。系统中的任意一个 节点可以随时加入网络，也可以随时离开网络。 7 第二章p 2 p 网络概述 6 ) 健壮性：p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在 各个节点之间进行的，部分节点或网络遭到破坏对其它部分的影响很小。p 2 p 网 络一般在部分节点失效时能够自动调整整体拓扑，保持其它节点的连通性。 7 ) 负载均衡：每个节点既是服务器又是客户机，减少了对传统c s 模式服 务器计算能力、存储能力的要求，同时因为资源分布在多个节点，所以可以更 好地实现整个网络的负载均衡。 ， 8 ) 高性价比：性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术 的发展，个人计算机的计算和存储能力以及网络带宽等性能依照摩尔定律高速 增长。p 2 p 架构可以有效地利用互联网中散布的大量普通节点，将计算任务或存 储资料分布到所有节点上。通过利用网络中的大量空闲资源，可以用更低的成 本提供更高的计算和存储能力。 9 ) 缺乏集中管理：p 2 p 系统是彻底的分布式系统，每一个节点都可以随意 的发布信息，缺乏集中管理，因此信息的获取比较困难。此外，缺乏集中管理 还造成系统整体信息的缺失：每个节点都通过有限的局部信息做出决定。这样 造成的后果是系统不能以全局最优的策略完成某个特定任务。 1o ) 隐私保护：在p 2 p 网络中，由于信息的传输分散在各节点之间进行而无 需经过某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大减小。在p 2 p 中，所有参与者都可以提供中继转发的功能，因而大大提高了匿名通讯的灵活 性和可靠性，能够为用户提供更好的隐私保护。 第三节p 2 p 文件共享系统的分类 现有p 2 p 文件共享系统根据网络拓扑结构可以分为集中式、分布式无结构 和分布式结构化系统。本节将对这三种类型的p 2 p 文件共享系统进行介绍。 2 3 - 1 集中式p 2 p 文件共享系统 集中式p 2 p 文件共享系统存在一个或多个中央目录服务器，服务器里面并 不存储用户的数据，而是存储资源的索引信息。当用户共享资源时，需将资源 的信息向中央服务器进行资源注册，中央服务器保存着系统中所有资源的标识 符和地址列表。当用户查找资源时，首先通过资源标识符向中央服务器查询， 8 第二章p 2 p 网络概述 服务器返回该资源的地址，用户通过该地址定位到所需资源。当定位到资源的 存储位置后，资源的下载在节点之间直接进行，与中央服务器无关。这是第一 代p 2 p 网络采用的结构模式，经典的案例就是著名的m p 3 共享软件n a p s t e r 。图 2 3 是集中式体系结构图。 图2 3 集中式体系结构图 集中式p 2 p 系统最大的优点是维护简单、资源查找效率高。由于资源的查 询依赖中央目录服务器，因此搜索算法灵活高效并能够实现复杂查询。该结构 最大的问题与传统c s 模式类似，容易造成单点故障、访问的“热点 现象和 法律等相关问题，主要表现为： 1 ) 中央服务器的瘫痪容易导致整个网络的崩溃，可靠性和安全性较低； 2 ) 随着网络规模的扩大，对中央服务器进行维护和更新的费用将急剧增 加； 3 ) 中央服务器的存在引起共享资源在版权问题上的纠纷，并因此被攻击为 非纯粹意义上的p 2 p 网络模型。 对小型网络而言，集中目录式模型在管理和控制方面占一定优势，但该模 型并不适合大型网络应用。 2 3 2 分布式无结构p 2 p 文件共享系统 分布式无结构模型也称为纯p 2 p 资源搜索模型，它可分为全分布式无结构 模型和半分布式无结构模型，它们之所以被称作无结构p 2 p 就是因为文件随机 9 第二章p 2 p 网络概述 地分布在节点中，文件和网络拓扑之间没有联系。 图2 4 全分布式无结构p 2 p 模型 在全分布式无结构p 2 p 网络中，所有的节点都既是服务器，又是客户端， 它们在网络中有着同等的地位和作用。全分布式无结构p 2 p 采用了随机图的组 织，取消了集中的中央服务器，每个用户随机接入网络，并与自己相邻的一组 邻居节点通过端到端连接构成一个逻辑覆盖的网络。资源分布在各个对等节点 上，资源查询都是通过洪泛的方式在相邻节点之间传递。全分布式无结构p 2 p 文件共享系统最具有代表性的是c m u t e l l a 。全分布式无结构模型如图2 4 所示。 全分布无结构网络解决了网络结构中心化的问题，具有较好的扩展性和容 错性。全分布无结构网络的另一优势在于能支持模糊匹配、文本匹配和范围匹 配等复杂的文件查询方式，从而为用户带来更多可选择的匹配结果。无结构型 p 2 p 网络的主要缺点是其可扩展性较差。随着节点的不断增多，网络规模不断扩 大，这种通过洪泛定位资源的方法将造成网络流量急剧增加，从而导致网络中 部分低带宽节点因网络资源过载而失效。 半分布式无结构模型吸取了集中式结构和全分布式无结构拓扑的优点，选 择性能较高( 处理器能力、存储、带宽、在线时间等方面性能) 的节点作为超 级节点，所有的超级节点连接成一个覆盖网络，而普通节点( 或称为叶子节点) 则连接到一个或多个超级节点上，各个超级节点存储了系统中与其连接的叶子 节点的信息索引。洪泛查询消息仅在超级节点之间转发，超级节点将查询结果 转发给提交该查询请求的叶子节点。采用这种结构的最典型的案例就是k a z a a ， 最新的g n u t e l l av 0 6 版本也采用了超级节点的技术【2 6 1 。典型的半分布式无结构 1 0 第二章p 2 p 网络概述 模型如图2 5 所示。 图2 5 半分布式无结构p 2 p 模型 由于超级节点的索引功能，搜索效率和系统的可扩展性都得以大大提高。 半分布式无结构系统具有两个明显的优势： 1 ) 与完全分布式系统相比，查找时间明显缩短，并且不存在单点故障问题。 如果一个或多个超级节点失效，连接到它们的节点可以与其它超级节点建立联 系，网络仍然可以正常运转。 2 ) 可以充分利用p 2 p 网络中节点的差异。在完全分布式对等网络中，无论 节点的能力大小，所有节点以均等的机会分担负载，这样使得能力较小的节点 负载过重。而在半分布式的系统中，性能较高的超级节点承担了绝大部分网络 负载，普通节点的负载相对较小，这样能更好地达到负载均衡。 半分布式无结构系统的缺点是对超级节点依赖性大，易于受到攻击，容错 性也受到影响。 2 3 3 分布式结构化p 2 p 文件共享系统 c h o r d 2 7 1 、c a n 2 8 】、p a s t r y 2 9 】和t a p e s t r y 3 0 】是结构化p 2 p 系统的代表，它们 建立在分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 之上。这种方法利用哈希 函数为搜索空间建立索引，将信息按照一定的规律组织，进而抽象出高效的查 询算法完成准确查询定位。因为每个节点都保存一张拥有其它少数节点索引信 息的路由表，所以这种查询算法也被称为分布路由算法。 第二章p 2 p 网络概述 系统中的节点构成一个覆盖网，每个查询操作都是通过这个覆盖网寻找目 标节点。结构化p 2 p 系统的性能就取决于其所采用的路由协议的效率。虽然各 种结构化p 2 p 系统的路由协议都不相同，但它们都具有一个共同的特点，就是 每个节点在覆盖网中拥有的邻居数目为o ( 1 0 9 ，完成每一次路由所需步数都会 在o ( 】0 9 n ) 内，其中n 为系统总节点数。 这些路由协议都是根据接收到的标识( 一般是一定长度的数字串) ，把信息 路由到相应的节点。每个节点也具有一个标识符( d ) ，而且这个标示符通常是 和它对应文件的标识相同( 当一个节点对应一个区间内的文件标识时，节点标 识符一定位于这个区间之内，一般是区间的中点) 。同时，每个节点都维护一张 路由表，记录其它一些节点的信息。当一个节点收到一个查询时，如果它发现 所查询的标识不在自己关联的区间内，那么该节点将会把该查询发送给其路由 表中它认为最靠近目标的邻居节点。各种路由协议中，对“最靠近目标 的定 义不尽相同，但是通常都是根据节点标识符和目标标识进行定义。c h o r d 采用 d h t 技术把p 2 p 节点在逻辑上组成一个环形结构；c a n 则将p 2 p 节点在逻辑上 组成一个t o r u s 结构；t a p e s t r y 和p a s t r y 的工作原理非常接近，节点在逻辑上组 成一个超立方体结构。 结构化p 2 p 系统最大的问题是d h t 的维护机制较为复杂，尤其是节点频繁 加入退出造成的网络波动会极大增加d h t 的维护代价。d h t 面临的另外一个问 题是d h t 仅支持精确关键词匹配查询，无法支持内容、语义等复杂查询。 第四节选择无结构p 2 p 的原因 目前p 2 p 文件共享系统的研究主要集中在分布式无结构和分布式结构化系 统上。尽管基于d h t 的结构化p 2 p 系统文件查找效率上优于无结构p 2 p 系统， 但也存在以下一些弱点使得d h t 系统至今没有得到广泛应用，而在这些方面无 结构p 2 p 优于d h t 系统。 1 ) p 2 p 节点出入网络频繁。一份研究报告【3 l 】指出，在g n u t e l l a 和n a p s t e r 网络中，节点的平均在线时间是6 0 分钟。也就是说，对于一个有1 0 0 万个节点 的大型p 2 p 网络，每分钟会有超过1 6 0 0 0 个节点加入或者退出网络。对于g n u t e l l a 等无结构网络来说，节点的进出对网络不会产生影响。相反，节点的进出对于 d h t 有着显著的开销。为了保证路由的效率和正确性，在每次失败后大多数d h t 1 2 第二章p 2 p 网络概述 需要o ( 崦n ) 步的纠正操作。最糟糕的情况，由于一个节点不能预先通知它的邻 居节点并发送相关的状态信息，在d h t 中就需要较多的时间和工作来找出错误 并且重新替换丢失的数据或是指针。如果节点出入过于频繁，这些纠正操作引 起的开销就会成为严重的问题，低带宽的连接节点就会被淹没。 2 ) d h t 很难支持模糊查询。基于d h t 的p 2 p 系统采用相容散列函数根据 精确关键词进行对象的定位与发现。散列函数总是试图保证生成的散列值均匀 随机分布，结果两个内容相似度很高但不完全相同的对象被生成了完全不同的 散列值，存放到了完全随机的两个节点上。因此，d h t 可以提供精确匹配查询， 但是支持语义是非常困难的。虽然研究者们做了大量的工作以帮助d h t 系统能 够处理更为复杂的查询，但始终无法像无结构p 2 p 系统一样方便地进行处理模 糊查询。 3 ) 用户存储空间的占用。在d h t 系统中，每当有外来数据的存储要求时， 就必须把这些数据存储到某一台主机，这台主机可能对该数据并不感兴趣。在 当前p 2 p 系统中，没有有效的激励机制使得节点愿意存储与自己不相关的数据 资源。相反，在无结构p 2 p 网络中，用户不会有过多的负担，他们只存储自己 需要的资源，不需要贡献自己的硬盘空间存储与其无关的信息。 基于以上三点原因，结构化的p 2 p 文件共享系统始终没能得到广泛应用。 事实上，目前已投入实际应用的p 2 p 文件共享服务大都是基于无结构p 2 p 网络 的，不少学者也指出无结构p 2 p 网络更适合于文件共享系统。有鉴于此，本文 选择无结构p 2 p 文件共享系统作为研究的重点，以便研究内容具有一定的应用 价值。本文提出的两种改进搜索机制都可以运用在类似g n u t e l l a 的完全分布式无 结构p 2 p 网络中，也可以运用在k a z a a 系统中由超级节点组成的上层覆盖网络 中( 因为k a z a a 中超级节点组成的覆盖网络可以看作是一个类似g n u t e u a 的完 全分布式网络) 。 第五节本章小结 本章详细介绍了p 2 p 的基本概念和特点，阐述了集中式、分布式无结构和 分布式结构化p 2 p 文件共享系统的优缺点，最后分析了选择无结构而不是结构 化p 2 p 的原因。 1 3 第三章g n u t e l l a 网络的文件搜索机制与系统特性 第三章g n u t e l la 网络的文件搜索机制与系统特性 本文的研究工作将以c m u t c l l a 网络为依托，因此有必要对g n u t c l l a 网络作深 入的了解。本章首先介绍g n u t c l l a 网络协议、g n u t c l l a 采用的洪泛搜索机制，然 后阐述c m u t e l l a 系统在拓扑结构、节点动态性、资源分布和查询分布等方面的特 性，最后介绍当前学术界提出的几种对洪泛搜索机制的改进方法。 第一节g n u t e l l a 协议和搜索机制 3 1 1g n u t e l l a 协议的定义 c m u t c l l a 协议是工作在t c p i p 协议之上的应用层协议。在最新版本的 g n u t c l l av 0 6 版本 2 6 】中定义了五种在对等节点之间通信的消息类型。这些消息 类型如表3 1 所示。 表3 1c m u t e l l a 协议的消息类型 消息类型说明 p i n g p o n g 呻 ( 查询消息) q u c r y h i t ( 应答消息) 用于在网络中主动发现其它节点。一个收到p i n g 消息的节点 会向发送方响应一个或多个p o n g 消息。 用于对