（计算机系统结构专业论文）p2p存储系统中资源搜索机制的研究.pdf

摘要 摘要 在过去的几年中，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 系统，按结构分为结 构化对等网络和非结构化对等网络，阐述了结构化对等网络和非结构化对等网络 的典型资源搜索机制。与结构化对等网络相比，非结构化对等网络中的资源搜索 机制不需要维护分布式哈希表，减少了系统繁重的计算开销，具有较广泛的可用 性和可扩展性。 其次，针对当前结构化p 2 p 文件存储系统存在仅支持单关键字的精确匹配， 而缺乏支持内容查询的局限性，提出一种名为c t i c h o r d 的p 2 p 文件共享机制。 利用c h o r d 高效定位优势，引入层次分类方法，将分类树作为模型的中心数据结 构，形成新型p 2 p 框架。用户信息发布、获取和更新不再基于关键字而是依赖 于类别属性，实现了对模糊搜索的支持。 最后，针对p 2 p 系统中由节点匿名性所带来的恶意欺诈服务问题，提出了 基于信誉感知的资源发现算法，基于路由索引算法( r o u t i n gi n d i c e s ( r i s ) ) ，融入信 誉的概念，有效的抑制了p 2 p 网络中恶意节点的欺诈行为，降低了系统的消息 负载，保证了节点获得服务的可靠性和安全性。 模拟试验表明，本文提出的资源搜索机制可以有效减少p 2 p 系统中的搜索 成本，降低资源定位延迟，并且在保证安全性的情况下提供基于内容的有效查询。 关键词：对等网络，资源搜索机制，分类树，层次分类，信誉 a b s t r a c t a b s t r ac t t h ep a s ts e v e r a ly e a r sw i t n e s st h er a p i dd e v e l o p m e n to fp 2 ps y s t e m s e f f i c i e n t r e s o u r c es e a r c hs c h e m eb e c o m e st h e k e yt e c h n o l o g y o fp 2 ps y s t e m s t h e c h a r a c t e r i s t i c so fd y n a m i c sa n da n o n y m i t yo fp 2 pc a n te n s u r et h a ta l lt h ep e e r sw i l l p r o v i d eh o n e s ts e r v i c e sa n dr e l i a b l er e s o u r c e s a tt h es a m et i m e ，a l t h o u g hs t r u c t u r e d p 2 ps y s t e m sh a v eg o o ds c a l a b i l i t y ，t h em a i ni s s u ee x i s t si nt h e mi st h a tt h e ya le s t r i c t e dt oe x a c tm a t c ha n dd o n ts u p p o r tc o n t e n tb a s e dq u e r y a l lt h e s ep r o b l e m s p r o h i b i tt h er a p i dd e v e l o p m e n to fp 2 ps y s t e m s h o wt or e d u c es e a r c h i n gc o s ta n d d e c r e a s et h el a t e n c yo fl o c a t i n gr e s o u r c e sa n dh o wt oc o n s t r u c tas a f ee f f i c i e n tp 2 p s y s t e mt h a ts u p p o r t sc o n t e n tb a s e dq u e r yb e c o m e sa ni m p o r t a n ts u b j e c to ft h ep 2 p s y s t e mr e s e a r c hf i e l d t os o l v et h ea b o v et w op r o b l e m s ，t h i st h e s i sf o c u s e so nt h e f o l l o w i n gr e s e a r c h e s f i r s t l y ，t h ef e a t u r e so fp 2 pn e t w o r k sa r ei n t r o d u c e d t h e r ea r et w oc l a s s e so f p 2 pn e t w o r k ：s t r u c t u r e da n du n s t r u c t u r e d t h i st h e s i si n t r o d u c e st h ec l a s s i c a lr e s o u r c e s e a r c hm e c h a n i s mo ft h e s et w ok i n d so fp 2 p c o m p a r e dw i t hs t r u c t u r ep 2 pn e t w o r k ， t h er e s o u r c es e a r c hm e c h a n i s mi nu n s t r u c t u r e dp 2 pn e t w o r kd o e s n tn e e dt om a i n t a i n t h ed i s t r i b u t e dh a s ht a b l e s ( d h t ) t h u s ，t h ec a l c u l a t i o nl o a do ft h es y s t e mi s r e d u c e da n dt h es y s t e mh a sg o o du s a b i l i t ya n ds c a l a b i l i t y t os o l v et h ep r o b l e mo fe x i s t i n gd h t b a s e df i l es t o r a g es y s t e m sb e i n gr e s t r i c t e d t oe x a c tm a t c ha n dl a c k i n gs e m a n t i c b a s e dq u e r y ，ad h t b a s e df i l es t o r a g es y s t e m n a m e dc t i c h o r di sp r o p o s e di nt h i st h e s i s u s i n ge f f i c i e n t l yp o s i t i o n i n gm e t h o d ， c t i - c h o r de m p l o y st h ec a t e g o r yt r e e ，w h i c hi st h ek e r n e ls t r u c t u r ea sw e l la st h e i n n o v a t i o no fc t i - c h o r d ，t os o l v et h e p r o b l e mo f t h ed i s o r d e ri n f o r m a t i o n m a n a g e m e n ti np 2 pn e t w o r ka n df o r m sa n o v e li n f o r m a t i o nn e t w o r kf r a m e w o r k t h e d i s t r i b u t i o n ，a c q u i s i t i o na n du p d a t eo fi n f o r m a t i o na r en o tb a s e do nk e yb u tp r o p e r t y ， w h i c hc a ns u p p o r tf u z z ys e a r c h f i n a l l y ，t ot h ep r o b l e mo fh o s t i l es e r v i c eb r o u g h tb yn o d ea n o n y m i t yi np 2 p a b s t r a c t s y s t e m ，t h i st h e s i sp r o p o s e sar e p u t a t i o na w a r er e s o u r c ef i n d i n ga l g o r i t h m t h i s a l g o r i t h mi sb a s e do nr o u t i n gi n d i c e s ( r s ) a l g o r i t h ma n da d o p t st h ec o n c e p t i o no f r e p u t a t i o nt oe f f i c i e n t l yr e s t r a i nt h ed e c e i v i n gb e h a v i o ro fh o s t i l en o d e si np 2 ps y s t e m a n dr e d u c et h em e s s a g e sl o a di nt h es y s t e m ，w h i c hc a ne n s u r et h er e l i a b i l i t ya n d s a f e t yo f t h es e r v i c e s s i m u l a t i o nr e s u l t ss h o wt h a tt h er e s o u r c es e a r c hs c h e m e sp r e s e n t e di nt h i st h e s i s n o to n l yr e d u c et h es e a r c h i n gc o s ta n dd e c r e a s et h el a t e n c yt ol o c a t er e s o u r c e si np 2 p s y s t e me f f e c t i v e l y ，b u ta l s op r o v i d ec o n t e n t b a s e dq u e r ya n de n s u r et h es a f e t yo ft h e w h o l e s y s t e m k e y w o r d s ：p e e r - t o p e e rn e t w o r k ，r e s o u r c es e a r c hm e c h a n i s m ，c a t e g o r yt r e e ， h i e r a r c h i c a lc l a s s i f i c a t i o n ，t r u s t 4 图表目录 图表目录 图1 1 论文结构图6 图2 1p 2 p 分类结构图1 l 表2 1p 2 p 类型性能的比较1 1 图2 2f l o o d i n g 算法1 2 表2 2g n u t e l l a0 4 协议的消息类型1 3 图2 3c h o r d 结构图18 表2 3c h o r d 节点指针表中各项的含义1 9 图2 4c h o r d 的数据组织2 0 图3 1c t i c h o r d 路由查找示例。3 0 图3 2 搜索平均跳转次数3 2 图3 3 搜索平均跳转次数3 2 图3 4 搜索平均跳转次数3 3 图4 1 信任的分类3 7 图4 2p 2 p 系统多路径推荐图3 9 图4 3 扩展的p 2 p 结构图3 9 图4 - 4 扩展p 2 p 系统节点数据结构图4 0 图4 5 算法流程图4l 图4 6r a r d a 的伪代码4 2 图4 7 r a r d a 的伪代码4 2 图4 8 信任节点比率关系图4 4 图4 - 9 欺诈节点与成功下载文件的比率关系图4 5 图4 1 0 资源搜索成功率4 5 图4 1 l 系统消息负载比较4 6 论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰 写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明 确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按 有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅，可以将学位论文编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：缒 巧年厂月刁日 第一章绪论 第一章绪论 互联网系统的计算模式正在发生从客户机服务器( c l i e n v s e r v e r ) 模式到对等 网络( p e e r t o p e e r ，简称p 2 p ) 模式的转变( 郑纬民e ta 1 2 0 0 4 ) 。对等网络的核心 思想是所有参与系统的节点( 指互联网上的某个计算机) 处于完全对等的地位，没 有客户机和服务器之分，也可以说每个节点既是客户机，也是服务器；既向别人 提供服务，也享受来自别人的服务。在p 2 p 系统中，资源是分布在各个对等节点 上的，而不是保存在集中的服务器上，因此如何有效地管理p 2 p 系统中的资源并 对其进行快速定位成为p 2 p 系统的关键技术。规模的增长对p 2 p 系统中资源的定 位不断提出更高的要求。资源搜索机制成为影响p 2 p 系统继续发展的重要因素。 研究p 2 p 系统中资源搜索机制的关键技术，提高p 2 p 的资源定位性能，成为一个 重要的研究课题。 1 1 研究背景 1 1 1 对等网络的基本概念和特征 在过去的几年中，随着计算机网络和通信技术的飞速发展，以i n t e r n e t 为典 型代表的开放网络得到飞速发展与普及，网络迅速融入了人们的社会生活。具体 表现在网络中用户与机构数量迅速扩大，目前接入互联网的个人计算机数量已经 上亿，并且其所承载的业务及应用不断扩展，导致网络应用模式、资源共享方式、 运行方式以及安全管理发生了根本性的变化。网络环境也从早期相对静态的、面 向特定组织和用户群体的封闭网络，转变为可公共访问的、面向大量动态用户的 开放网络。开放网络具备以下的几个特征： ( 1 ) 地理上广域分布。开放网络环境中已无地理位置上的限制和约束，目前 i n t e r n e t 是开放网络的典型代表，亦是目前构建开放网络最重要的基础平台。 ( 2 ) 开放性。在开放网络环境中整个网络不再是静态的、面向特定组织和用户 群体的封闭网络，而是可公共访问的、面向大量动态用户的开放网络。 ( 3 ) 节点资源共享是自愿的。 ( 4 ) 动态性和自组织性。由于节点可以自主地决定自身的行为与状态，可以随 第一章绪论 时加入某一网络，随时提供新的资源共享服务，亦可以随时终止资源共享服务， 甚至可以随时退出该网络，因此开放网络具有高度动态性和自组织性的特点。 ( 5 ) 节点之间对等自治。一般而言，开放网络中的节点间关系是对等的，一个 节点既可能是网络服务的提供者，亦可能是网络服务的访问者，无中心权威节点， 参与者间的依赖度下降。在开放网络环境中，为提高系统的可扩展性和解决单点 失败问题，除少数系统外具有中心认证服务器外，绝大多数的开放系统都无控制 中心，也无可信的第三方c a ( c e r t i f i c a t i o n a u t h o r i t y ) 。 ( 6 ) 安全信息的不完全性与不确定性，以陌生参与者为主体的事务模式导致在 多数情形下不可能获得完整的安全相关信息，而网络的开放性和节点的动态性、 自组织性则导致许多影响系统安全的因素变得不确定。 1 1 2 对等网络的应用 在需求的推动下，p 2 p 系统在文件共享、科学计算与协作、数据存储、数据 搜索等多个领域得到了广泛的应用和研究，从而开辟了互联网应用的新时代。 ( 1 ) 文件共享 按照传统的文件共享模式，每个需要共享文件的计算机必须先把文件上载到 集中的服务器上，而需要获取文件的计算机必须到服务器上下载所需的文件，这 样才能实现个人计算机之间的文件共享。传统的方式不仅浪费了大量的服务器资 源，而且存在单点失效的问题。利用p 2 p 系统进行数据文件共享，可以让个人计 算机用户之间不通过中心服务器而直接共享各种文件，用户直接到共享文件的计 算机上去下载文件，这样不仅节约了资源，还提高了鲁棒性。 第一个p 2 p 文件共享系统是1 9 9 9 年f a n n 开发的n a p s t e r ( n a p s t e r1 9 9 9 ) ，它 在发布不久便拥有了几百万用户，取得了极大的成功。此后，l i m e w i r e ( l i m e w i r e 2 0 0 0 ) ，m o r e p h e u s ( m o r p h e u s2 0 0 2 ) ，e d o n k e y ( e d o n k e y2 0 0 2 ) ，i m e s h ( i m e s h2 0 0 2 ) 、 k a z a a ( k a z a a2 0 0 2 ) 、b i t t o r r e n t ( b i t t o r r e n t2 0 0 1 ) 等p 2 p 文件共享系统不断涌现。 用户数量的持续增长和应用的迫切需求使得文件共享成为当前p 2 p 系统中最主 流的应用。 基于p 2 p 的分布式w e b 缓存共享系统也得到了广泛的研究( i y e rse ta 1 2 0 0 2 ， 凌波e ta 1 2 0 0 5 ) ，利用p 2 p 技术，局域网内所有个人计算机能够共享本地缓存， 中心代理服务器就无需缓存w e b 页面信息，而且所有的查询也无需通过中心的 2 第一章绪论 代理服务器发送到远程的服务器。这样不仅能节省费用，还能缩短请求的响应时 间。 一 一 ( 2 ) 科学计算与协作 在现代科学研究中，高能物理、大气、天文、生物信息和石油地质等许多重 大科学领域正面临着巨大的挑战。这些领域的数据计算和存储要用p e t a 数量级来 衡量。使用超级计算机存储和分析数据，不仅价格昂贵，还难以满足需求。同时 单凭少数几个研究人员和几台计算机的传统科学研究方式已无法满足科研需求， 需要全球各地的科研人员协作来完成。 p 2 p 系统可以联接上百万台或更大规模的个人计算机，有效地利用处于网络 边缘的空闲计算资源进行协同计算，完成超级计算机的工作。1 9 9 9 年开始的 s e t i h o m e ( s o c i e t yt p1 9 9 9 ) 项目致力于搜寻外太空生命，到现在已经得到 5 ，0 0 0 ，0 0 0 以上用户的支持。2 0 0 0 年斯坦福大学开发的f o l d i n g h o m e ( u n i v e r s i t ys 2 0 0 0 ) 项目致力于研究蛋白质折叠、误折、聚合及由此引起的相关疾病，到目前 已经吸引了4 0 0 ，0 0 0 个用户加入。2 0 0 3 年o l s o n 实验室主持的研究艾滋病的项目 f i g h t a i d s h o m e ( l a bo2 0 0 3 ) 也吸引到了9 , 0 2 0 个用户。 英特尔公司研制的p 2 p 分布式中间件n e t b a t c h ( i n t e l n e t b a t c h1 9 9 0 ) 使工程师 能够在本地和全球的英特尔环境中寻找可用的计算能力，使计算机能够提高吞吐 量、缩短运行时间并运行更复杂的工作，从而降低开发成本。企业级协同工作的 p 2 p 平台g r o o v e ( n e t w o r k sg2 0 0 2 ) 允许用户直接通信，为企业或是商务的应用提 供支持。同时为了方便科学家之间的协作以及对大量研究数据的处理，p 2 p 科学 协作系统的研究工作也已经开始( i a m n i t c h ia e ta 1 2 0 0 2 ，i a m n i t c h ia 2 0 0 3 ) 。 ( 3 ) 数据存储 当今社会处于一个信息爆炸的时代，需要大量的存储空间来存储消息。p 2 p 技术允许数据分散存放在多个p 2 p 节点上，而不是存放于专用服务器。这样不仅 可以减轻服务器负担，节省大量开支，还可以提高数据存储的可靠性和传输的速 度。 伯克利大学开发的分布式海量存储系统o c e a n s t o r e ( k u b i a t o w i c zje ta 1 2 0 0 2 ) 采用t a p e s t r y ( z h a ob e ta 1 2 0 0 1 ) 技术，提供了全球范围内的一致性数据存储。m i t 研究的c f s 项目采用c h o r d ( s t o i c aie ta 1 2 0 0 3 ) 技术，提供了一致性的分布协同 第一章绪论 文件存储。r i c e 大学和微软公司联合研究的p a s t 项目采用p a s t r y ( r o w s t r o n ae t a 1 2 0 0 1 ) 技术，提供了大规模的、可扩展的、协同的分布文件存储服务。 s u n 公司实验室和斯坦福大学图书馆联合研发的l o c k s s ( u n i v e r s i t yse ta 1 2 0 0 2 ) 项目是一个用于电子数字出版物的高度安全的系统。现在包括美国国会图 书馆在内的4 9 家图书馆正在采用l o c k s s 软件。 ( 4 ) 数据搜索 传统的搜索引擎采用集中式的体系结构，通过网络爬行器收集信息，在设计 方面存在局限性，表现为数据不能动态跟踪、难以访问数据库和动态w e b 页的 信息、单点失效、可扩展性差以及资源浪费等。基于p 2 p 的分布式搜索引擎可以 克服这些缺点。首先，它通过对动态页面的访问使搜索范围更深更准确：其次， 它采用的分布式结构避免了单点失效；最后，它可以充分利用网络边缘空闲资源， 不必专门建立强大的服务器系统，从而节省资源。 2 0 0 1 年s u n 公司开发的p 2 p 分布式搜索引擎j x t a s e a r c h ( w a t e r h o u s es2 0 0 1 ) 可以基于某个元数据集合进行分布式搜索。m i l l e r 提出的p 2 p 分布式搜索引擎 h y p e r b e e ( s o c i e t yt p1 9 9 9 ) 为网页建立数据库，利用互联网上数量庞大的个人计 算机的运算能力，将每台个人计算机作为小型的搜索引擎搜索每个网站的信息。 s u e l 讨论了p 2 p 分布式搜索引擎的基本设计原则，并设计了一个原型系统 o d i s s e a ( s u e lt e ta 1 2 0 0 3 ) 。 ( 5 ) 实时通讯 基于p 2 p 的通讯又可以分为两种，即时消息和实时游戏。即时消息( i n s t a n t m e s s a g i n g ，简称i m ) 在当今全球已经变得相当普遍。国外的i c q 、y a h o om e s s a g e r 、 m s nm e s s e n g e r 以及国内的o o 等都已经吸引了大量用户使用。然后，目前i m 软件还是基于c s 模型设计的，用户的帐户、好友列表都保存在s e r v e r 上，甚至 用户有时发出的消息也需要s e r v e r 帮助转发。s e r v e r l e s s 型的i m 基本不需要 s e r v e r 的支持，只要人们以某种形式形成p 2 p 网络互联，就可以相互之间识别并 通讯，中间过程无需s e r v e r 的帮助，比如s k y p e ( s k y p e2 0 0 8 ) 。 网络游戏的发展速度同样惊人。然而与即时通讯应用相似，基于c s 模型的 连线对战同样需要性能强劲的游戏服务器支持。p 2 p 技术允许任何p e e r 可以单独 建立区域性的p 2 p 网络，可以让i n t e m e t 上的任何人随时加入到其中，共同游戏 4 第一章绪论 娱乐。 1 2 问题的提出 资源搜索机制是对等网络中的关键技术。所谓的资源搜索机制主要是为了发 现资源的结构和状态信息，给出期望资源的一个具体的描述，发现一系列和资源 描述相匹配的资源。对等网络的开放、动态、异质、广域、匿名、节点对等自治 等特性保证了系统具有较好的可扩展性。但同时，对等网络中每个节点自治、匿 名、自组织等特性使得每个节点的目标是最大化自身的网络效用( n e t w o r k u t i l i t y ) ( j e f f r e ys h n e i d m a ne ta 1 2 0 0 3 ) ，存在着搭便车的现象( f r e e - r i d i n g ) ( a d a re e ta 1 2 0 0 0 ) 。即某些节点只索取资源，而不愿意或者很少共享资源。资源的搜索 请求需要在更多的节点之间转发才能到达愿意共享资源的节点，增加了资源搜索 的延迟；某些情况下响应资源请求的节点还可能存在欺诈或恶意行为，如伪造文 件、随意中止服务、提供虚假数据、节点的恶意退出等，从而使得搜索机制获得 的提供服务节点的质量无法保证。 因此，针对对等网络中存在的问题，建立信任模型，在搜索机制中融入信任， 建立一种对等网络环境下高效的基于信任的资源搜索机制，增加网络的可用性， 安全性和鲁棒性，减少网络的通信负载成为对等网络中研究的重要方向。 另外，目前大多数p 2 p 系统只支持基于关键字的搜索，用户不能根据文件的 内容进行搜索，不能进行个性化的共享信息定制。虽然现有许多成型的p 2 p 系统 应用，但如何在大规模分布式的p 2 p 系统中构建灵活、可扩展的信息检索机制仍 是当前亟待研究的问题。 1 3 论文工作 为了设计高效、安全的基于内容的资源搜索机制，本文深入总结了前人在相 关领域的研究成果，分别对p 2 p 系统信息检索领域的两部分技术展开研究，主要 研究工作如下： 1 全面深入的综述p 2 p 系统中资源搜索机制的相关技术。总结了相关研究工 作中存在的主要问题，分析了未来研究工作发展的趋势。 2 针对当前结构化p 2 p 文件存储系统存在仅支持单关键字的精确匹配，而缺 5 第一章绪论 乏支持内容查询的局限性，基于一种改进型的c h o r d 协议( y ud a n e ta 1 2 0 0 5 ) 并结 合文本分类技术，提出一种新的p 2 p 文件共享机制，用户信息发布、获取和更新 不再基于关键字而是依赖于类别属性，实现了对模糊搜索的支持。由于分类树具 有良好的可重构性，用户可以部分下载自己所感兴趣的子树，组装成自己的个人 分类树，进行个性化的共享信息定制。 3 针对p 2 p 系统中由节点匿名性所带来的恶意欺诈服务，提出了基于信誉感 知的资源发现算法。基于路由索弓l ( r o u t i n gi n d i e e s ( r i s ) ) 算法，融入信誉的概念， 有效地抑制了p 2 p 网络中恶意节点的欺诈行为，降低了系统的消息负载，保证了 节点获得服务的可靠性和安全性。 本文的研究工作得到了国家自然科学基金项目基于计算市场模型的网 络资源管理研究( 编号：6 0 2 7 3 0 4 1 ) 和网格计算环境中信任感知的资源交易模 型( 编号；6 0 6 7 3 1 7 2 ) ，以及国家8 6 3 项目合肥网格节点的建设及若干典型 网格应用的研制( 编号：2 0 0 2 a a l 0 4 5 6 0 ) 的支持。 1 4 论文结构 论文共分五章，章节的基本关系如图1 1 所示。 第一章绪论 上 第二章对等网络中基于内容的资源管搜索机制相关研究 第三章 第四章 基于分类树的 p 2 p 环境中基于信 p 2 p 文件共享机 任感知的资源搜索 制机制 图1 1 论文结构图 6 第一章绪论 第一章，绪论。首先介绍所从事研究工作的背景和意义，然后分析p 2 p 系统 中资源搜索机制面临的一些问题，最后介绍本文的主要工作和组织结构。 第二章，p 2 p 系统中资源搜索机制的相关研究。分析了p 2 p 的构建与物理相 关的重要性，回顾了p 2 p 系统中资源定位机制的各种研究技术，从而明确本文的 研究工作。 第三章，基于分类树的p 2 p 文件共享机制。基于一种改进型的c h o r d 路由模 型，将层次分类技术应用到p 2 p 结构中，设计了一种名为c t i c h o r d 的p 2 p 文件 共享机制，并给出了性能分析和实验结果。 第四章，基于信誉感知的资源发现算法。基于r i s 算法，融入信誉的概念， 提出基于信誉感知的资源发现算法，有效地抑制了p 2 p 网络中恶意节点的欺诈行 为，降低了系统的消息负载，保证了节点获得服务的可靠性和安全性。 第五章，结束语。对本文工作的总结，以及对下一步工作的展望。 1 5 本章小结 本章首先介绍了对等网络的定义、特征、和应用，阐述了对等网络技术的发 展以及研究意义。然后提出了对等网络中基于内容资源搜索机制研究的重要性， 分析了对等网络发展面临的挑战。最后给出了本文的研究内容和论文结构。 7 第二章对等网络中资源搜索机制的研究 第二章对等网络中资源搜索机制的研究 p 2 p 是开放网络的典型代表。由于p 2 p 系统规模和应用的不断扩大，则对于 资源搜索机制的相关研究成为p 2 p 系统研究的热点。本章将对目前p 2 p 系统中 典型的资源搜索机制进行归纳总结并分析其中存在的问题。 2 1 引言 随着社会和网络的发展，人们对数据存储和传输、高性能计算等有着迫 切的需求；而这些应用满足了人们快速交换大容量数据的需求。p 2 p 不依赖或 尽可能不依赖中央服务器，避免了c s ( c l i e n t s e r v e r ) 结构带来的单点失效、 性能瓶颈和网络拥塞等问题。每个p e e r 既能作为服务器，也可成为客户机。 p 2 p 技术的核心思想就是将网络应用的核心从中央服务器向网络边缘的终端 设备扩散；这些终端设备可以是高性能计算机，可以是p c 机，可以是手机， 也可以是p d a 等等。 传统的p 2 p 资源搜索机制分为非结构化和结构化，其中全分布式非结构 化p 2 p 系统采用资源定位机制洪泛算法，并且实现了模糊查询。虽然实现简 单，但不适应大规模p 2 p 的特点i 既给网络带宽带来严重的影响，也降低了 资源搜索的性能；全分布式结构化p 2 p 系统具有较好的可扩展性和鲁棒性， 并且提供了有效的节点加入和离开策略。但是结构化p 2 p 系统的最大问题是 仅限于精确关键字的匹配查询，而不支持基于内容的复杂查询。研究人员围 绕具有p 2 p 系统特征的资源搜索机制展开了大量研究。有的研究针对全分布 式非结构化p 2 p 系统的搜索机制进行优化，有的研究如何基于全分布式结构 化p 2 p 系统实现基于内容的查询。本章将综述这些相关工作。 2 2p 2 p 系统的分类和特征 p 2 p 系统中的每个p e e r 既是客户机，又是服务器，还是路由器，因此p 2 p 系统中的节点称为对等机( s e r v e n t ，s e r v e r + c l i e n t 的组合) 。p 2 p 的各个p e e r 不依赖于特定的集中式机制，各个p e e r 因为互相协作而共存；而且，各个节 9 第二苹对等网络中资源搜索机制的研究 点可以直接交互并可能随时离开和随时加入对等网络。p 2 p 技术的特点体现在 以下几个方面： 非中心化( d e c e n t r a l i z a t i o n ) ：网络中的资源和服务分散在所有结点上， 信息的传输和服务的实现都直接在结点之间进行，可以无需中间环节和服务 器的介入，避免了可能的瓶颈。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 s 结构服务器计算能力、存储能力的要求，同时因为资源分布在多 个节点，更好的实现了整个网络的负载均衡。 目前已有的p 2 p 系统种类繁多，可以从不同的角度对其进行分类。本文 根据其网络拓扑结构以及拓扑集中化程度来进行分类。 对等网络按拓扑结构的不同可分为结构化对等网络和非结构化对等网 络，按照集中程度可以分为集中式的和分布式的。结构化对等网络的网络拓 1 0 第二章对等网络中资源搜索机制的研究 曼曼曼曼曼鼍皇! 曼曼詈曼曼皇皇曼皇曼曼i i 一曼i 曼曼皇皇曼曼曼曼曼兽曼璺皇皇曼皇曼蔓曼曼曼曼曼皇曼量曼曼曼皇曼曼曼曼曼皇皇暑舅皇蔓笪 扑结构是固定的，每个资源精确放置在确定的节点上，提供了资源标识i d 到 资源存储位置间的映射关系，从而保证有效的路由，确保在有限的步数内搜 索到资源。c h o r d 、t a p e s t r y 、p a s t r y 和c a n ( r a t n a s a m yse ta 1 2 0 01 ) 都属于结 构化对等网络。 非结构化p 2 p 系统中没有提供资源标识i d 到资源所在位置的映射关系， 因而不能在确定的跳数内搜索到资源，数据放置与对等网络拓扑无关，如 n a p s t e r 、g n u t e l l a 、f r e e n e t 、k a z a a 等。非结构化的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 1 所示。 图2 - 1p 2 p 分类结构图 对于不同类型p 2 p 系统的可靠性、可扩展性、可维护性以及算法分析的比 较如表2 1 所示。一 表2 - 1p 2 p 类型性能的比较 集中式分布式非结构化拓扑分布式结构化拓扑 可扩展性差差好 可靠性差好好 可维护性最好最好好 发现算法效率最高 由 高 第二章对等网络中资源搜索机制的研究 2 3 非结构化对等网络的资源搜索算法 传统的资源定位机制是基于洪泛算法的。采用洪泛算法传播消息无需节点保 存其他节点的信息，实现最为简单，洪泛资源定位机制在p 2 p 系统应用的初期得 到广泛应用。g n u t e l l a 是实现洪泛资源定位机制的一种典型协议，它在p 2 p 文件 共享系统中得到广泛应用。本节将以g n u t e l l a 为例分析传统的洪泛资源定位机 制。 2 3 1 传统洪泛资源定位机制的基本搜索技术 传统的资源搜索机制采用的是简单洪泛( f l o o d i n g ) 算法。洪泛算法首先从 源节点传播查询消息到其所有邻居结点，然后再传播到邻居节点的邻居节点，直 到达到预先确定的跳数为止。其洪泛算法流程图如图2 2 所示。从节点a 出发查找 文件描述符c h a r a c t e r ，a 首先分布向自己的邻居节点b 、c 广播查询请求，节点b 、 c 又分别向它们的邻居节点c 、d 、e 广播转发的查询消息，依此类推，一旦某个 节点查找到关键字为c h a r a c t e r 的数据，它就按原路径返回结果。如达到算法预先 确定的跳数，则算法终止。这种f l o o d i n g 的资源搜索方法只适应于以发起者为中 心的某个特点半径范围内，当超出这个范围时就无法继续查询。f l o o d i n g 资源搜 索算法是一种完全分布式的，它能有效地避免单点失败问题。在p 2 p 系统中通过 四个步骤在节点之间的进行通信，为发送查询消息，定位资源，请求消息，响应 消息。 l _ 查询消息- - 2+ 定位资源 3 t 请求消息4 响应消息 图2 2f l o o d i n g 算法 简单的洪泛搜索机制在p 2 p 系统的应用初期得到了广泛的使用。g n u t e l l a 是 一个p 2 p 文件共享系统，它是一个纯粹的p 2 p 系统，没有集中的索引服务器， 1 2 第二章对等网络中资源搜索机制的研究 采用了随机图的组织方式，节点度数服从“p o w e r l a w ( f a l o u t s o s me ta 1 1 9 9 9 ) 规则，j ，= x 口，面对网络的动态变化体现了较好的容错性，使系统具有较好的可 用性。g n u t e l l a 采用了基于完全随机图的洪泛( f l o o d i n g ) 发现机制和随机转发 ( r a n d o mw a l k e r ) 机制。为了控制查询消息的传输，通过t t l ( t i m et ol i v e ) 的减值来实现。本文将以g n u t e l l a0 4 为例来详细的分析传统的洪泛搜索机制。 表2 - 2 给出了g n u t e u a0 4 协议定义的消息类型，其中p i n g 和p o n g 是构建 类消息，用于网络的构建；q u e r y 和q u e r y h i t 是搜索类消息，用于资源搜索。各 个消息的功能如表2 2 所示。 表2 2g n u t e l l a0 4 协议的消息类型 消息指令 说明 p i n g 指令用于发现网络上的其他节点。个节点收到一个p i n g 的描述符表示希 望回应一个或多个p o n g 描述符。 p o n g 指令用于响应p i n g 消息。包括一个被连接的g n u t e l l a 节点的地址和它能提 供的数据共享信息。 q u e r y 指令重要的分布式网络检索机制。个节点收到一个q u e r y 描述符后，如 果在自己的数据集中发现一个匹配的数据将回应一个q u e r y h i t 。 q u e r y h i t 指令用于回应q u e r y 消息。提供足够的信息来获取匹配q u e r y 请求的数据。 p u s h 指令一个用于允许防火墙中的节点向网络提供共享数据文件的机制。 在g n u t e l l a 系统中，当用户需要搜索某个文件的时，向其所有邻居节点发送 包含请求文件描述符的请求消息q u e r y 。当用户接收到q u e r y 消息时，先将请求 文件的描述符与本节点的文件共享索引进行匹配，匹配成功发送包含响应消息 q u e r y h i t 。但无论匹配成功与否，则只要1 v r l 不等于0 ，则q u e r y 消息继续转发， 直到t t l = 0 ，则整个搜索结束。 资源搜索过程中，采用洪泛算法可以快速的传播消息