（计算机应用技术专业论文）开放网络中基于信任的资源搜索机制研究.pdf

中国科学技术大学硕士学位论文 摘要 摘要 随着计算机网络和通信技术的飞速发展，网络环境已经从早期相对静态的、面向特定组 织和用户群体的封闭网络，转变为可公共访问的、面向大量动态用户的开放网络。开放网络 在促进了网络实体间的相互协作与资源共享的同时，由于其开放、动态、异质、实体对等自 治、资源共享自愿等特性，使得网络中节点最大化自身的网络效用，即某些节点只索取资源， 而不愿意或者很少共享资源。并且，某些情况下响应资源请求的节点可能存在欺诈或恶意行 为，如伪造文件、随意中止服务、提供虚假数据、节点的恶意退出等，导致响应资源请求节 点提供的服务质量无法保证。因此，如何在开放网络环境中建立并维护信任关系以提高整个 网络的可用性，保证整个网络的良性发展己成为开放网络研究领域的主要课题之一；在开放 网络中如何高效的定位这些资源中的可信资源也成为一个热点问题。本文基于以上的两个问 题进行了以下几个方面的研究。 本文首先归纳总结了开放网络的典型代表g r i d 和p 2 p 的主要特征。针对p 2 p 系统，按 结构分为结构化对等网络和非结构化对等网络，阐述了结构化对等网络和非结构化对等网络 的典型资源搜索机制。与结构化对等网络相比，非结构化对等网络中的资源搜索机制不需要 维护分布式哈希表，减少了系统繁重的计算开销，具有较广泛的可用性和可扩展性。本文的 资源搜索机制的研究都是基于非结构化对等网络。 其次，针对目前p 2 p 网络中存在的同谋、诋毁，虚假服务等安全问题，提出了基于矢 量空间的信任模型。通过矢量空间模型的推荐可信度来防止节点之间的同谋和诋毁，通过“时 间敏感因子”来提高信任模型检测节点行为的敏感性。最后对此模型进行了仿真验证，理论 分析和实验表明，可以有效抑制同谋诋毁攻击行为，具有较好的可用性。 然后，针对非结构化对等网络资源搜索机制存在的问题，将信任融入资源搜索机制，提 出了基于信任感知的资源搜索机制，确保资源请求节点得到可靠的资源和服务，提高整个系 统的q o s 。实验表明，该机制有效的抑制了对等网络中恶意节点的欺诈行为，减少了整个系 统的网络开销。 接着，对g r i d 和p 2 p 的混合计算环境进行了分析。在混合计算环境中，p 2 p 节点的自 组织性和匿名性不能保证所有节点都能提供诚实的服务，一些节点可能存在恶意欺诈行为。 因此，我们基于信任对经验和最好邻居搜索算法进行了改进，提出了混合计算环境下基于信 任的资源搜索机制，确保混合计算环境节点提供较好的服务保证。 最后，本文引入兴趣的概念，基于兴趣和信任构建超级节点叠加网络拓扑结构，并在此 基础上提出g n u t e l l a 环境下基于兴趣聚类和信任感知的资源搜索机制。仿真证明，该机制有 效的保证了系统的q o s 并降低了消息的网络负载。 关键词：开放网络，网格，对等网络，信任模型，资源搜索机制，兴趣聚类，超级节点 中国科学技术大学硕士学位论文摘要 a b s t r a c t w i l l ld e v e l o p m e n to ft h e c o m p u t e rn e t w o r ka n dc o m m u n i c a t i o nt e c h n o l o g y , n e t w o r k e n v i r o n m e n th a sb e e nc h a n g e df r o mac l o s en e t w o r kb e i n gc o m p a r a t i v e l ys t a t i ca n df a c e dw i t h s p e c i a lo r g a n i z a t i o n so rn s e rg r o u p st oa no p e no n et h a tc a nb ep u b l i c l ya c c e s s e da n df a c e dw i t h m a n yd y n a m i cu s e r s o p e nn e t w o r kn o to n l yi m p r o v e sc o l l a b o r a t i o na n dr e s o u r c es h a r i n ga m o n g e n f t i e si nn e t w o r k ，b u ta l s oh a st h ef e a t u r e so fo p e n n e s s ，d y n a m i c s ，h e t e r o g e n e i 吼a u t o n o m y , e q u a l i t ya n dv o l u n t a r i e sf o rr e s o u r c es h a r i n g t h e r e f o r e ，t h ep e e r si nt h en e t w o r kt r yt om a x i m i z e t h e i ro w nn e t w o r ku t i l i t y , w h i c hm e a n st h a ts o m ep e e r sa l w a y sa b u s eo t h e r s r e s o u r c e sb u ts e l d o m c o n t r i b u t et h e i ro w nr e s o u r c e s o no c c a s i o n ，c h e a ta n db a l e f u lb e h a v i o rm a y b ee x i s ta m o n gs o m e p e e r sr e s p o n d i n gr e s o u r c er e q u e s t ，s u c ha sp r o v i d i n gc o u n t e r f e i tf i l e sa n dd e c e i t f u ld a t a ，l e a v i n g b a l e f u l l ya n ds t o p p i n gs e r v i c ew h i c hl e a dt h er e s u l t st h a tt h eq u a l i t yo fs e r v i c e sp r o v i d e db y r e s p o n d i n gp e e r sc a n tb eg u a r a n t e e d t h e r e f o r e ，h o wt oe s t a b l i s ha n dm a i n t a i nt r u s ti nt h eo p e n n e t w o r k st op r o m o t et h ew h o l en e t w o r k sa v a i l a b i l i t ya n da s s u r ei t sb e n i g nd e v e l o p m e n tc o m e st o af u n d a m e n t a lp r o j e c tf o rt h eo p e nn e t w o r kr e s e a r c h e r s ，t h u s ，i ti sah o tq u e s t i o nt oe f f i c i e n t l y l o c a t et h er e l i a b l er e s o u r c e si ns u c ha no p e nn e t w o r k 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 s f o c u s e so nt h ef 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 ft w o t y p i c a lo p e nn e t w o r k s ，g r i da n dp 2 p , a r ei n t r o d u c e d t h e r ea r e t w oc l a s s e so fp 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 s 血ec l a s s i c a l r e s o u r c es 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 ec 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 e r 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 dm a i n t a i nt h ed i s t r i b u t e d h 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 f t h es y s t e mi sr e d u c e da n dt h es y s t e mh a sg o o d u s a b i l i t ya n ds c a l a b i l i t y i nt h i st h e s i s ，a l lr e s e a r c h e so nr e s o u r c es e a r c hm e c h a n i s m sa r eb a s e do n u n s t r u c t u r e dp 2 pn e t w o r k s e c o n d l y , a i m e da tc o l l u s i o n , b a d - m o u t h i n ga n dd e c e p t i o ns e r v i c ee x i s t i n gi nc u r r e n tp 2 p n e t w o r k ，ad i s t r i b u t e dt r u s tm o d e lb a s e do nv e c t o rs p a c ei sp r o p o s e d t h ei m p r o v e dt r u s tm o d e l u s e s t i m e s e n s i t i v ef a c t o r t oi m p r o v et h es e n s i t i v e n e s so fd e t e c t i n gp e e r s b e h a v i o r s ，a n d r e c o m m e n d a t i o nt r u s tb a s e do nv e c t o rs p a c em o d e lt oa v o i dc o l l u s i o na n db a d - m o u t h i n ga m o n g p e e r s t h e o r e t i ca n a l y s i sa n ds i m u l a t i o ns h o wt h a tt h i sm o d e li se f f e c t i v ea n dr e s t r a i nt h eb e h a v i o r o f c o l l u s i o na n d b a d - m o u t h i n ge f f e c t i v e l y t h i r d l y , t ot h ep r o b l e me x i s t i n gi nr e s o u r c es e a r c hm e c h a n i s mo fu n s t r u c t u r e dp 2 p , h e u r i s t i c r e s o u r c ed i s c o v e r ya l g o r i t h mb a s e do nt r u s t - a w a r ei sp r e s e n t e db yi n t e g r a t i n gar o b u s ta n df l e x i l e t r u s tm e c h a n i s mi n t oc u r r e n ts e a r c hm e c h a n i s mt oe n s u r et h a tr e s o u r c ed e m a n d e rc a no b t a 曲 r e l i a b l er e s o u r c ea n ds e r v i c e t h i sn e wr e s o u r c ed i s c o v e r ya l g o r i t h mc a ne f f e c t i v e l yr e s t r a i nt h e 2 i m p o s t u r ea n dp s e u d os e r v i c eo fp 2 pn e t w o r k ，i m p r o v et h er e l i a b i l i t ya n ds e c u r i t ya n dd e c r e a s e n e t w o r kl o a d ， a f t e rt h a t ，t h em a l i c i o u sb e h a v i o r si ng r i da n dp 2 pc o m p o u n de n v i r o n m e n ta r ea n a l y z e d f o r t h ea u t o n o m y a n d a n o n 蛳t y f e a t u r e s o f p 2 pe v i r o r l r r 蝎n t ，s e l f i s h p e e r s m a y p r o v i d e f a k es e r v i c e s s o m ep e e r se v e nt a k ed e c e i t f u lb e h a v i o r c o n s e q u e n t l y , t h et r u s tf a c t o ri se n g a g e di n t ot h e s e a r c h i n gm e c h a n i s mb a s e do ne x p e r i e n c e a n db e s t n e i g h b o r , a n dan e wr e s o u r c es e a r c h m e c h a n i s mb a s e do nt r u s ti sb r o u g h tf o r w a r d t h i ss e a r c hm e c h a n i s mc a l le f f e c t i v e l yi m p r o v et h e r e l i a b i l i t ya n ds e c u r i t yo f t h eg r i da n dp 2 pc o m p o u n de n v i r o n m e n t ， f i n a l l y ，w ei n t r o d u c el h ec o n c e p to fi n t e r e s t ，a n dc o n s t r u c ta ni n t e r e s ta n d t r u s tb a s e do v e r l a y n e t w o r kw i t hs u p e rn o d e a c c o r d i n g l y a t li n t e r e s t - c l u s t e r i n gb a s e da n dt r u s t - a w a r eh e u r i s t i c r e s o u r c ed i s c o v e r ym e c h a n i s mi sp r o p o s e di ng n u t e l l a a n a l y s i sa n ds i m u l a t i o n ss h o wt h a tt h i s r e s o u r c ed i s c o v e r ym e c h a n i s mc a ni m p r o v et h eq u a l i t yo fs e r v i c eo ft h es y s t e m ，a n dr e d u c et h e o v e r h e a do f s e a r c hm e s s a g e s k e y w o r d s ：o p e nn e t w o r k ，g r i d ，p e e r - t o 。p e e rn e t w o r k ，t r u s tm o d e l ，r e s o u r c e s e a r c h m e c h a n i s m ，i n t e r e s tc l u s t e r ，s u p e rn o d e 3 中国科学技术大学硕士学位论文图表目录 图表目录 图1 - 1 论文组织结构图9 图2 1p 2 p 分类结构图。1 2 表2 1p 2 p 类型性能的比较1 2 图2 2f l o o d i n g 算法1 5 表2 - 2g r m t e l l a0 4 协议的消息类型1 5 表2 3p 2 p 与网格各项性能比较1 8 图3 - 1 信任的分类2 l 表3 - 1 三种类型恶意节点的行为特征2 9 表3 2 模拟场景3 0 图3 - 2 模型对同谋诋毁攻击的抵御能力。3 0 表3 - 3 三种类型节点特征3 1 图3 - 3 三种类型恶意节点的行为特征3 l 图4 1p 2 p 系统多路径推荐图，3 3 图4 _ 2 扩展的p 2 p 结构图3 4 图4 - 3 扩展p 2 p 系统节点数据结构图3 4 图4 - 4 算法流程图3 5 图4 5r a r d a 的伪代码3 6 图4 6r a r d a 的伪代码3 6 图4 7 模拟拓扑结构图3 7 图4 - 8 信任节点比率关系图3 8 图4 - 9 欺诈节点与成功下载文件的比率关系图3 8 图4 1 0 资源搜索成功率3 9 图4 1 1 系统消息负载比较3 9 图5 1g r i d 和p 2 p 的混合计算环境4 2 图5 - 2 混合计算环境中基于信任的模型4 4 表5 1 信任等级表一4 4 图5 3 域间信任模型4 4 表5 - 2 经验信息表4 5 图5 - 4 基于信任的资源搜索流程图4 5 图5 5 自由搜索和基于信任搜索的信任节点比较图4 9 图5 - 6 自由搜索和基于信任搜索的不信任节点比较图4 9 图5 7 自由搜索和选择信任度最大值下载对比实验图4 9 图6 - 1 传统的超级节点叠加网络的拓扑结构5 2 图6 2 冗余盼超级节点叠加网络的拓扑结构5 2 图6 - 3 超级节点选取伪代码算法5 4 图6 - 4 扩展p 2 p 系统结构图5 5 表6 1 兴趣关联表5 5 图6 5 资源搜索流程图5 6 图6 - 6 资源搜索流程伪代码5 8 图6 7 资源搜索命中率5 9 图6 - 8 网络规模与请求转发节点数目关系5 9 图6 9 信任节点比例6 0 6 中国科学技术大学硕士学位论文 绪论 1 1研究背景 第一章绪论 1 1 1 开放网络的基本概念和特征 在过去的几年中，随着计算机网络和通信技术的飞速发展，以l u t e m e t 为典型代表的开 放网络得到飞速发展与普及，网络迅速融入了人们的社会生活。具体表现在网络中用户与机 构数量迅速扩大，目前接入互联网的个人计算机数量已经上亿，并且其所承载的业务及应用 不断扩展，导致网络应用模式、资源共享方式、运行方式以及安全管理发生了根本性的变化。 网络环境也从早期相对静态的、面向特定组织和用户群体的封闭网络，转变为可公共访问的、 面向大量动态用户的开放网络。开放网络具备以下的几个特征： ( 1 ) 地理上广域分布。开放网络环境中已无地理位置上的限制和约束，目前i n t e m 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 开放网络的应用领域 目前，开放网络的应用领域主要包括电子商务( e c o m m e r c e ，实例有e b a y 1 a n d o n s a l e 2 ) ；分布式计算( d i s t r i b u t e d c o m p u t i n g ，实例有p 2 p 【3 】计算和g i u d 4 计算) ：文件 共享p 2 p 系统( f i l es h a r i n g p 2 ps y s t e m 5 ，实例有l i m e w i r e 、e d o n k e y 、b i t t o r r e n 下载) ： 信息过滤( i n f o r m a t i o n f i l t e r i n g 6 ，实例有z y l a b 开发的z y f i l l e r ) 等。 7 1 1 3p 2 p 系统和网格系统 p 2 p 系统和网格系统是开放网络的两个典型代表。 网格的定义到目前为止仍没有一个明确统一的表述。对网格和网格计算理论做出巨大 贡献的i a nf o s t e r 等人认为网格是“在缺乏中央控制、全局信息和严格信任关系的情况下能 够协同使用地理分布的资源” 7 1 1 8 。网格的出现是由于人们需要解决一些超大规模应用问 题，而这些超大规模应用所需计算能力已不可能在单一的高性能计算机或单一的计算机机群 上获得。这就需要将地理分布、系统异构、性能各异的各种高性能计算机、计算机机群、大 型服务器、贵重科研设备、大型通信设备、可视化系统等，通过高速互连网络连接并集成起 来，形成对用户相对透明的、虚拟的、高性能计算环境，即网格系统，以此来协同解决大型 应用的计算问题。 p 2 p 是p e e r _ t o - p e e r 的简称，也称为对等网络。它是一种i n t e m e t 应用，可以充分的利用 大量自治的参与者的资源。参与者共享他们所拥有的一部分硬件资源( 处理能力、存储能力、 网络连接能力、打印机等) 和软件资源，这些共享资源需要由网络提供服务和内容，能被其 他对等节点( p e e 0 直接访问而无需经过中间实体。在此网络中的参与者既是资源( 服务和内 容) 提供者( s e r v e r ) ，又是资源( 服务和内容) 获取者( c l i e n t ) 。 1 2 问题的提出 资源搜索机制是开放网络中的关键技术。所谓的资源搜索机制主要是为了发现资源的结 构和状态信息，给出期望资源的一个具体的描述，发现一系列和资源描述相匹配的资源。开 放网络的开放、动态、异质、广域、匿名、节点对等自治等特性保证了系统具有较好的可扩 展性。但同时，开放网络中每个节点自治、匿名、自组织等特性使得每个节点的目标是最大 化自身的网络效用( n e t w o r ku t i l i t y ) 9 ，存在着搭便车的现象( f r e e - r i d i n g ) 1 0 。即某些节 点只索取资源，而不愿意或者很少共享资源。资源的搜索请求需要在更多的节点之间转发才 能到达愿意共享资源的节点，增加了资源搜索的延迟；某些情况下响应资源请求的节点还可 能存在欺诈或恶意行为，如伪造文件、随意中止服务、提供虚假数据、节点的恶意退出等， 从而使得搜索机制获得的提供服务节点的质量无法保证。 因此，针对开放网络中存在的问题，建立信任模型，在搜索机制中融入信任，建立一种 开放网络环境下高效的基于信任的资源搜索机制，增加网络的可用性，安全性和鲁棒性，减 少网络的通信负载成为开放网络中研究的重要方向。 1 3本文的主要工作和贡献 针对1 2 节中存在的问题，本文主要做了如下几个方面的工作和贡献： 提出一种信任模型，解决由于开放网络中节点自治、匿名性所导致的协同欺骗，提 供虚假服务的问题。 中国科学技术太学硕士学位论文 绪论 在全面深入的研究目前非结构化p 2 p 系统中资源搜索机制的相关技术基础上，提出 了一种基于信任感知的资源搜索机制，这种资源搜索机制可以有效减少资源搜索延 迟，降低系统中的消息负载，抵抗欺诈节点的恶意虚假服务。 在网格和p 2 p 的混合计算环境下，基于信任对经验和最好邻居搜索机制进行了改 进，提出了一种网格和p 2 p 的混合计算环境下基于信任的资源搜索机制。这种资源 搜索机制尽量避免恶意节点的欺诈行为和虚假服务，有效提高资源搜索的可靠性和 安全性，保证系统的安全性。 在非结构化对等网络g n u t e l l a 系统下，提出了基于兴趣和信任构造超级节点叠加网 络拓扑结构的方法和依据兴趣聚类和信任的资源搜索的机制，降低了消息的网络负 载，提高系统的安全性和可靠性。 1 4论文结构 本文共分为七章，文章结构如图1 - 1 所示。 第一章绪论 第二章对等网络的研究及其与网格的融合 第三章p 2 p 环境中基于矢量空间的信任模型 第四章p 2 p 环境 中基于信任感知 的资源搜索机制 第五章g r i d 和p 2 p 混台环境中基于信 任的资源搜索机制 第七章总结和展望 第六章g n u t e l l a 中基 于兴趣聚类和信任感 知的资源搜索机制 图1 1 论文组织结构图 第一章绪论 首先介绍所从事研究工作的背景和意义，然后分析p 2 p 系统中资源搜索机制面临的一 些问题，最后介绍本文的主要工作和组织结构。 第二章对等网络的研究现状及其与网格的融合 首先介绍了有关p 2 p 的研究现状以及对等网络的分类。然后简单介绍了结构化对等网 络中具有代表性的几种资源搜索机制。接着重点介绍了非结构化p 2 p 系统中的资源搜索机 制洪泛( f l o o d i n g a l g o r i t h m ) ，b f s 和d f s 。最后简单介绍网格和p 2 p 技术的互相融合。 第三章p 2 p 环境中基于矢量空间的一种信任模型 首先介绍了信任的一些基本概念以及目前存在的问题，然后提出了一种基于矢量空间 9 中国科学技术大学硕士学位论文 绪论 信任模型，对于诋毁和共谋提出解决方案。 第四章p 2 p 环境中基于信任感知的资源搜索机制 介绍了目前非结构化p 2 p 中的资源搜索机制d i r e c t e d - b f s 所存在的问题，提出了一种 基于信任感知的资源搜索机制，在定程度上避免了系统中欺诈和恶意行为引起的虚假服务 问题，较好的保证了响应节点提供的服务质量，减少了网络中的消息负载。 第五章g r i d 和p 2 p 混合环境中基于信任的资源搜索机制 本节介绍了g r i d 和p 2 p 混合环境下存在的安全问题，介绍了g r i d 环境下基于经验和最 好邻居的资源搜索机制。本节对经验和最好邻居的请求一转发机制进行改进，融入信任因素， 提出经验+ 最好邻居+ 信任的资源搜索机制。 第六章g n u t e l l a 下基于兴趣聚类和信任感知的资源搜索机制 首先基于兴趣和信任进行超级节点叠加网络拓扑结构的构建，然后在超级节点网络拓 扑结构基础上提出基于兴趣聚类和信任感知的资源搜索机制。 第七章结束语 总结了本文的研究成果，展望未来需要解决的问题。 1 0 第二章对等网络的研究及其与网格的融合 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 等等。 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 因为互相协作而共存：而且，各个节点可以直接交互并可能随时离开和随时加入对等 网络。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 n 络环境下由于每个节点既是服务器又是客户机，减少了对传统c s 结 构服务器计算能力、存储能力的要求，同时因为资源分布在多个节点，更好的实现了整 个网络的负载均衡。 目前已有的p 2 p 系统种类繁多，可以从不同的角度对其进行分类。本文根据其网络拓扑 结构以及拓扑集中化程度来进行分类。 对等网络按拓扑结构的不同可分为结构化对等网络和非结构化对等网络，按照集中程度 可以分为集中式的和分布式的。结构化对等网络的网络拓扑结构是固定的，每个资源精确放 置在确定的节点上，提供了资源标识i d 到资源存储位置间的映射关系，从而保证有效的路 由，确保在有限的步数内搜索到资源。c h o r d 1 1 、t a p e s t r y 1 2 】、p a s t r y 1 3 d c a n 1 4 都属 于结构化对等网络。而非结构化p 2 p 系统中没有提供资源标识i d 到资源所在位置的映射关 系，因而不能在确定的跳数内搜索到资源，数据放置与对等网络拓扑无关，如n a p s t e r 1 5 、 g n u t e l l a 1 6 、f r e e n e t 1 7 、k a z a a b 8 1 等。非结构化的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 类型性能的比较 集中式分布式非结构化拓扑分布式结构化拓扑 可扩展性 差差好 可靠性差好好 可维护性最好 最好好 发现算法效率最高中高 1 2 中国科学技术大学硕士学位论文对等网络的研究厦其与网格融台 2 3p 2 p 系统中现有的资源搜索算法 2 3 1 结构化对等网络的资源搜索算法 结构化对等网络采用分布式哈希表d h t ( d i s t r i b u t e dh a s ht a b l e ) 进行资源搜索，具有 查找效率高和查找确定性等优点。d h t 类结构能够自适应结点的动态加入退出，有着良好 的可扩展性、鲁棒性、结点分配均匀性和自组织能力。结构化网络采用了确定性的网络 拓扑结构，d h t 可以提供精确的发现。只要目的结点存在于网络中，d h t 总能发现它，发 现的准确性得到了保证。资源搜索算法是结构化对等网络的核心对等网络算法的可扩展性 和容错性直接影响到对等网络系统的性能，因此对等网络资源搜索算法的研究具有重要的意 义。本小节介绍了目前几种有影响的结构化对等网络搜索算法。 2 3 1 1c a n 算法 c a n 1 4 是a t & t 的a c i r i 部门开展的研究项目。c a n ( c o n t e n ta d d r e s s a b l en e t w o r k s l 模型采用多维的标识符空间来实现分布式散列算法。c a n 将所有结点映射到一个n 维的笛 卡尔空间中，并为每个结点尽可能均匀的分配一块区域。c a n 采用的散列函数通过对 ( k e y ，v a l u e ) 对中的k e y 进行散列运算，得到笛卡尔空间中的一个点，并将( k e y , v a l u e ) 对存储在 拥有该点所在区域的结点内。c a n 采用的路由算法相当直接和简单，知道目标点的坐标后， 就将请求传给当前结点四邻中坐标最接近目标点的结点。c a n 是一个具有良好可扩展性的 系统，给定n 个结点，系统维数为d ，则路由路径长度为o ( n l d ) ，每结点维护的路由表信 息和网络规模无关为o ( d ) 。 2 3 1 2c h o r d 算法 c h o r d 算法 1 1 是m i t 提出的一种分布式查找算法。该算法中每个节点和文件都映射 到1 6 0 位的标识，该标识通过对文件名或节点i p 哈希得到，节点和文件i d 在一维空间上构 成一个环，文件关键字存贮在文件i d 的后继节点上。为减少搜索开销，c h o r d 在每个节点 建立一个f i n g e r 表( 路由表) ，用于指向环中距该节点分别2 丹0 ，2 千2 m 的节点。因此 c h o r d 可以保证在o ( 1 0 9 d 的复杂上界内确定性地搜索对象( 索引) ，其中为对等网络系 统的节点数。c h o r d 的邻居表为l o g 项，即拓扑维护开销为o ( 1 0 9 ) 。 与现有的工作相比，c h o r d 算法具有简单性、可验证性和可扩展性等优点。c h o r d 算法 的路由跳数和网络直径优于c a n 算法，节点加入过程和维护开销优于t a p e s t r y 算法和p a s t r y 算法。 2 3 1 3 t a p e s t r y 算法 t a p e s t r y 1 2 是用于覆盖网络的搜索机制，它可以对消息进行位置无关的路由，把消息 传递到最近的存放所要求的对象拷贝的结点。t a p e s t r y 的路由机制完全是基于软状态的并且 易于修复。t a p e s t r y 具有自我管理、容错和灵活平衡负载等特点。该算法是目前广域环境中 中国科学技术大学硕士学位论文对等网络的研究及其与网格融合 非集中式搜索的最有影响路由算法之一。每个t a p e s t r y 节点只需维护l o g n 大小的路由表信 息，路由最多在1 0 刚的路由跳数内完成。 t a p e s t r y 算法针对p r r 算法进行了改进和扩充，该算法具有可扩展、自适应和鲁棒性 等特点，能够在高负载和动态网络、节点差错时有效地进行路由查询和搜索资源。尽管 t a p e s t r y 算法与p r r 算法相类似，但是该算法增加一些新的特点：利用了状态信息、提供 自我管理功能、强壮性、可扩展性、动态自适应性，在出现节点、网络失败和高负载时实现 平滑降低系统睦能，不需要任意节点来维护全局信息等。 2 3 1 4 p a s t r y 算法 p a s t r y 【1 3 】是m i c r o s o f t 和r i c e 大学共同发起的对等网络匿名存储系统中的搜索和路由算 法，该算法与t a p e s t r y 有许多相似之处：使用匹配前缀或者后缀地址的路由方法、插入和删 除算法有类似的代价。p a s t r y 与t a p e s t r y 的区别在于：第一，p a s t r y 中对象复制无需由所有 者来控制，在对象的出版发布过程中，复制对象被放到与对象编号最接近的多个节点上。 第二，t a p e s t r y 在服务器和根节点之间的路由过程中放置对象指针信息；而在p a s t r y 中客户 端通过对象编号直接路由到保存对象复制饩附近，这样在实际网络中多个复制对象存在于实 际物理网络的不同节点上，在多个节点存储复制对象带来了存储开销、安全性、保密性和一 致性等问题。最后，p a s t r y 路由算法不能充分利用本地性提高路由效率。 2 3 2 非结构化对等网络的资源搜索算法 2 3 1 节中结构化p 2 p 系统中资源搜索算法面临的最大问题是d h t 的维护机制较为复 杂，尤其是结点频繁加入退出造成的网络波动会极大增加d h t 的维护代价，造成了系统繁 重的计算开销。下边我们要介绍的非结