（计算机系统结构专业论文）对等网络内容搜索及索引缓存研究.pdf

! 堡型兰堡旦坐堡苎：壁羔塑竺查查矍窒墨窒! ! 堡童竺塞 摘要 近年来，对等网络闩益成为i n t e 丌l e t 一个重要应用。对等网络将i n t e r n e t 边缘节点的 资源收集起来，提供强大的计算与存储能力。无结构对等网络由于查询的灵活性和对动 态环境的适应性，得到大力部署，成为对等网络的主流。但无结构对等网络存在网络性 能低下等困难，这使搜索算法直是无结构对等网络的研究重点。 本论文研究无结构对等网络的内容搜索算法和分布式索引缓存算法，主要研究内容 和创新成果如下： i ) 提出了一个基于查询代理的自适应无结构对等网络盲搜索算法( q 从，q u e r ya g e n t a l g o r i t h m ) 。盲搜索算法的主要目标是控制查询规模，降低冗余开销，但现有算法缺少 对网络状况的感知能力，难以自适应地根据查询及网络情况调整查询规模。 q a a 通过查询代理不断发战子查询来完成查询工作，其核心思想是通过子查询探测 刚络状况，再利用这些信息指导后续子查询规模，从而有效降低冗余开销，其规则是： 禹查询成功越近，查询规模越小。利用这种探测过程，q 从避免了现有算法的参数优 化难题。 本论文将q a a 与现有盲搜索算法进行了对比实验，结果表明，对u n i - u n i 模式及 z i p f - s q r t 模式，q a a 即使在高查询满足率条件下，也实现了有效冗余开销控制，其结果 冗余事分别为1 1 和1 4 ，足几个实验算法中最低的，并且两个模式下的结果冗余率提高 也是最低的，这说明q a a 有更好的网络适应性。 2 ) 提出t - 个基于缓存生命期( t t l ) 的分布式索引缓存模型。分布式索引缓存方法的基 本思想足以较低代价扩大网络中信息数量，以此提高网络搜索性能，因此索引缓存密度 在影响对等网络的搜索性能上占据核心地位，但目前对此的研究工作还很少见报道。 本论文分析了查询到达对缓存索引扩散的驱动作用以及缓存生命期超时对缓存索引 的消灭作用，发现网络索引缓存密度在这两个因素影响下可以维持一定的稳定状态，这 意味蕾，可以通过一些简单的参数来模型网络搜索性能。 鉴于上述发现本论文研究了两个具代表性的基本节点发现算法g n u t e l l a 算法与 随机浸游算法，其分别具有最短和最长的缓存路径。我们研究了这两个算法的索引缓存 密度如何受查淘到达速率以及缓存生命期时长的影响，发现在g n u t e l l a 算法下，查询到 达速率及缓存生命期时长对缓存密度表现出明显的线性关系，而在随机漫游算法下，表 中国辩7 - 鲩博t 擘忙论文：对等叫硌内容墟j # 屉蠡；1 暖打埘究 论文进一步研究了查询到达速率及缓存生命朗两个冈袭妇何影响嘲络的搜索什能 发现在g n u t e l a 算法下，平均查询开销和返两个因奈仃线性天系，厨在随机漫游算法下， 这是一个对数关系。 3 ) 研究了目前分布式索引缓存方法存在的问题，包括网络动态性所导致的索引缓存失 效问题以及多对一映射所导致的负载均衡问题。 在动态网络环境下，由于索引与共享内容相分离，当共亭内容变化时，会使相关索 引信息失效。目前算法中使用的缓存生命期机制没能保证索引信息的有效性，分析发现， 失效索引信息会在对等网络中扩敬，对查询造成干扰。我们提出通过检测索引信息有效 性来阻止无效索引信息扩散，并进一步提出了检测重生方法，该方法执行了对命中条 目缓存生命期的重设操作：研究结果表明。使用检测方法会引起对等网络绥存密度最多 4 4 的降低，但可以将无效缓存索引降低4 7 倍。 索引缓存方法扩大了网络中索引信息数量，但不影响相应的共亨内容，这种多对一 映射的不均匀会使得负载均衡问题发生，影响网络服务能力。我们提出共享内容天联方 法( s c a a s h a r e dc o n t e n t a s s o c i a t e d a l g o r i t h m ) 来缓解这一问题。s c a a 关联共享内容， 分担内容请求，以此来缓解负载均衡问题。我们研究了s c a a 在不同负载压力下的效果， 发现在中等负载下，s c a a 最多可以提高服务满足率3 0 。 关键词：对等网络，盲搜索算法。分布式索引缓存，缓存有效性，负载均衡 q i 拍抖7 硫薄t 彳 论文：对等列络内容搜点及嘉 ：缓存研究 a b s t r a c t p e e r t o p e e r ( p 2 p ) n e t w o r kh a sb e c o m ea ni m p o r t a n ta p p l i c a t i o ni ni n t e r a c t p 2 pn e t w o r k c o l l e c t st h er e s o u r c eo nt h en o d e sa tt h ee d g eo fi n t e m e tt op r o v i d es t r o n gc o m p u t i n gp o w e r a n ds t o r a g ec a p a b i l i t y b e c a u s eo fi t sf l e x i b i l i t yo nq u e r yp a t t e r na n da d a p t a b i l i t yt od y n a m i c e n v i r o n m e n t ，u n s t r u c t u r e dp 2 pn e t w o r ki sw i d e l yd e p l o y e da n db e c o m et h em a i n s t r e a mo f t h e c u 盯e n tp 2 pn e t w o r k s h o w e v e r , u n s t r u c t u r e dp 2 pn e t w o r k ss u f f e rf r o mp o o rp e r f o r m a n c e ， t h e r e f o r ei m p r o v i n gs e a r c h i n ga l g o r i t h mi so n ei m p o r t a n tm a j o rr e s e a r c ha r e af o ru n s t r u c t u r e d p 2 pn e t w o r k t h i sd i s s e r t a t i o ns t u d i e st h ec o n t e n t s e a r c h i n ga l g o r i t h m a n dt h ed i s t r i b u t e d i n d e x c a c h i n ga l g o r i t h m t h em a i nc o n t r i b u t i o n sa r ea sf o l l o w s ： 1 ) aq u e r y a g e n t - b a s e da d a p t i v eb l i n ds e a r c h i n ga l g o r i t h mf o ru n s t r u c t u r e dp 2 pn e t w o r k ( q a a ，q u e r ya g e n ta l g o r i t h m ) i sp r o p o s e d t h eo b j e c t i v eo f b l i n ds e a r c h i n ga l g o r i t h mi st o c o n t r o lt h eq u e r ys c a l ea n dr e d u c et h er e d u n d a n c yc o s t h o w e v e rt h ep r e s e n ta l g o r i t h m sa r e s h o r to ft h en e t w o r ki n f o r m a t i o nd e t e c t i n gc a p a b i l i t ya n dd i f f i c u l tt or e g u l a t et h eq u e r ys c a l e a d a p t i v e l y q a a f u l f i l l st h eq u e r yw o r kb yt h es u b q u e r i e ss e n tb yq u e r ya g e n t i t sb a s i ci d e ai st o u s et h en e t w o r ka n dq u e r yi n f o r m a t i o nd e t e c t e db yt h ep r e v i o u ss u b q u e r i e st od e t e r m i n et h e s c a l eo ft h es u b s e q u e n ts u b - q u e r i e sa n dt h u sr e d u c er e d u n d a n c yc o s te f f e c t i v e l y i t sr u l ei st h e s m a l l e rg a pt os u c c e s sq u e r y , t h es m a l l e rq u e r ys c a l e u s i n gt h ed e t e c t i n gs c h e m e ，q a a a v o i d st h et r o u b l e s o m ep a r a m e t e ro p t i m i z a t i o ni s s u eo ft h ep r e s e n ta l g o r i t h m s e x p e r i m e n t st oc o m p a r eb e t w e e nq h ha n dt h ep r e s e n tb l i n ds e a r c h i n ga l g o r i t h m si nt h e t h e s i sr e s e a r c hf o u n dt h a tf o ru n i f o r md i s t r i b u t i o na n dz i p fd i s t r i b u t i o nn e t w o r k s ，q a ac a n r e a l i z er e d u n d a n c yc o s tc o n t r o lu n d e rq u e r yc o n t e n t sh i g h l ys a t i s f i e dc o n d i t i o n ，a n dt h er e s u l t r e d u n d a n c yr a t i oi sa b o u t1 ia n d1 4r e s p e c t i v e l y f u r t h e r m o r e ，f r o mu n i f o r md i s t r i b u t i o nt o z i p fd i s t r i b u t i o n ，t h ei n c r e a s eo fq a a i nr e s u l tr e d u n d a n c yr a t i oi st h el o w e s lw h i c h i m p l i e s q a a ss t r o n g e rf l e x i b i l i t yt h a nt h ep r e s e n tb l i n ds e a r c h i n ga l g o r i t h m s 2 ) at t l - b a s e dd i s t r i b u t e di n d e x c a c h i n gm o d e li sp r o p o s e d t h eb a s i ci d e ao fd i s t r i b u t e d i n d e x c a c h i n gi st oe n l a r g et h ei n d i c e si nt h ep 2 pn e t w o r ki nr e l a t i v el o w e rc o s t t h ei n d i c e s d e n s i t yi sak e yp a r a m e t e r , w h i c ha f f e c t st h es e a r c h i n gp e r f o r m a n c eo fp 2 pn e t w o r k s i l i ! 堕! ! 兰竺堡三! 竺堡壅：墅! 坚竺塑查望墨墨墨：! ! 堡垒竺塞 h o w e v e r , f e ww o r ko ni n d i c e sd e n s i t yh a v eb e e nf o u n ds of a ri nt h el i t e r a t u r e t h et h e s i sr e s e a r c ha n a l y s e dt h ed r i v i n ge f f e c t so fc a c h e di n d i c e sd i f f u s i n gw i t hq u e r y a r r i v a l sa n dt h ec a c h e di n d i c e sd e s t r o y i n ge f f e c t sw i t hc a c h et t lt l m e o u t sh a v eb e e n a n a l y z e d t h ew o r kf o u n dt h a tc a c h i n gi n d i c e sd e n s i t yc a nm a i n t a i nac e r t a i ns t a b l el e v e l t h i si m p l i e st h a tt h es e a r c h i n gp e r f o r m a n c eo fp 2 pn e t w o r k sc a nb em o d e l e d b ys o m es i m p l e p a r a m e t e r s t w ot y p i c a lb a s i cn o d e f i n d a l g o r i t h m s g n u t e l l aa l g o r i t h ma n dr a n d o m w a l k e r a l g o r i t h mw e r es t u d i e d t h et w oh a v et h es h o r t e s ta n dl o n g e s tc a c h i n gp a t hr e s p e c t i v e l y , h o w t h eq u e r ya r r i v a ls p e e da n dc a c h e 竹la f f e c tt h ei n d i c e sd e n s i t yi nt h e s et w oa l g o r i t h m sw e r e i n v e s t i g a t e d ，a n ds o m ei n t e r e s t i n gr e s u l t sw e r eo b t a i n e d f o rg n u t e l l aa l g o r i t h m ，al i n e a r r e l a t i o ne x i s t sb e t w e e nt h ei n d i c e sd e n s i t ya n dt h e s et w of a c t o r s ，a n df o rr a n d o m w a l k e r a l g o r i t h map o w e r - l a we x i s t s h o wt h e q u e r ya r r i v a ls p e e da n dc a c h e 订la f f e c ts e a r c h i n gp e r f o r m a n c eo fp 2 p n e t w o r k sw a sf u r t h e ri n v e s t i g a t e d t h er e s u l t ss h o w s ，f o rg n u t e l l aa l g o r i t h m ，al i n e a rr e l a t i o n e x i s t sb e t w e e nt h em e a nq u e r yc o s ta n dt h e s et w of a c t o r s ，a n df o rr a n d o m w a l k e ra l g o r i t h ma l o g a r i t h mr e l a t i o ne x i s t s 3 ) t h ed r a w b a c k so f p r e s e n td i s t r i b u t e di n d e xc a c h i n gm e t h o dh a v eb e e ns t u d i e d ，i n c l u d i n g t h ei n v a l i di n d i c e sp r o b l e mc a u s e db yd y n a m i cn e t w o r ka n dt h el o a di m b a l a n c ec a u s e db y m u l t i - t o o n ei n d e xm a p p i n g i nd y n a m i cn e t w o r k ，b e c a u s eo ft h es e p a r a t i n go fi n d e xa n dc o n t e n t ，t h ec h a n g m go ft h e s h a r e dc o n t e n tw i l lc a u s et h er e l e v a n ti n d i c e st ob e c o m ei n v a l i d t h ec a c h i n g1 t lm e c h a n i s m u s e db yt h ep r e s e n ta l g o r i t h m sc a n n o tg u a r a n t e et h ee f f e c t i v e n e s so fi n d e x o u ra n a l y s i s f o u n dt h a tt h ei n v a l i di n d i c e sc a l ld i f f u s ei np 2 pn e t w o r k ，w h i c hd i s t u r b st h es u b s e q u e n t q u e r i e s b a s e do nt h i sf i n d i n g ，c h e c k i n gt h ee f f e c t i v e n e s so fi n d e xt op r e v e n tt h ed i f f u s i n go f t h ei n v a l i di n d i c e si sp r o p o s e d , a n dac h e c k r e g e n e r a t i o nm e t h o di sa l s op r o p o s e d ，w h i c h e x e c u t e st h er e s e ti n s t r u c t i o no f t h eh i ti n d e xi nt h ec a c h e i t l e x p e r i m e n tr e s u l t ss h o wt h a t o u rp r o p o s e dm e t h o d sc a nd e c r e a s et h ei n v a l i di n d i c e sb y4 - 7t i m e s 。b u ti n d i c e sd e n s i t y r e d u c e sn om o r et h a n4 4 i n d e xc a c h i n gm e t h o de n l a r g e st h ei n d i c e si np 2 pn e t w o r k sa n dd o e sn o ta f f e c tt h es h a r e d c o n t e n t s ，b u tt h en o n u n i f o r mm u l t i t o - o n em a p p i n gc a nc a u s et h el o a di m b a l a n c e ，w h i c h d e t e r i o r a t e sn e t w o r ks e r v i c ep e r f o r m a n c e s h a r e dc o n t e n ta s s o c i a t e da l g o r i t h m ( s c a a ) i s ：! ：塑! ! ! 坚! ! 兰! ：! 堡茎：翌兰竖竺塑查竺墨墨墨! ! 堡堡竺塑 p r o p o s e dt oa l l e v i a t et h ei s s u e s c a aa s s o c i a t e ss h a r e dc o n t e n t sa n ds h a r e st h ec o n t e n t r e q u e s t st oa l l e v i a t et h el o a di m b a l a n c e t h ee f f e c t i v e n e s so fs c a au n d e rv a r i a b l en e t w o r k l o a di sf u r t h e ri n v e s t i g a t e d s c a ac a n i m p r o v et h es e r v i c es a t i s f a c t o r yr a t i oa b o u t3 0 u n d e r m o d e r a t en e t w o r kl o a d k e yw o r d s ：p e e r t o - p e e rn e t w o r k ，b l i n ds e a r c h i n ga l g o r i t h m ，d i s t r i b u t e di n d e xc a c h i n g ， c a c h i n ge f f e c t i v e n e s s ，l o a db a l a n c e v 表目录 农i ig n u t e l l a 网络可达用户数 表2 i 结构对等网络性能 表2 2 c s 模式及对等网络的比较 。3 1 3 表2 3g n u t e l l a 消息描述符 农51 索引缓存表 表5 2 扩展的索引缓存表 x i 1 8 7 7 目录 图目录 倒2 ic s 模式与对等模式1 0 图2 3 中心式对等网络图1 1 圈2 4 无结构对等网络1 2 图2 5 对等网络应用模型二1 4 h2 6j x t a 结构1 5 幽2 7g n u t e l l a 消息处理过程1 9 h28r i n g 算7 圭睡眠查询般活2 0 | ! i2 9k - r a n d o m - w a l k e r 查询过程( k - 3 ，p = 3 ) 2 1 图2 1 0 逆向路径缓存2 2 圈2 1 1g n u t e l l a 网络查询流行性分布t k s o “2 2 陶2 1 2g n u t e l l 列络查询消息的生命期分布【6 ”1 2 3 图2 1 3 多层对等网络的洪泛2 4 i | 3i 结果冗余率随对象流行度的分布3 l j 茎| 32u n i u n i 模式下的查询开销3 8 图3 31 1 1 1 1 u n i 模式下的结果冗余率3 8 | 墨l3 4z l p f - s q r t 授式下的查询开销。3 9 幽3 5z i p f - s q r t 校式下的结果冗余率3 9 图36 邻属节点度对满足车的影响4 1 图3 7 邻居节点度对结果冗余率的影响4 1 圈3 8 系统框架示意图4 4 闲3 9 查询代理算法处理流程4 8 图4l 缓存密度髓时f h j 的发展趋势5 7 图4 2g n u t e l l a 算法下的索引缓存密度6 l l 苎| 4 3 随机漫步芽法。f 的索引缓存密度6 3 图44g n u t e l l a 的矗询成功车6 5 幽4 5g n u t e l l a 算法下的奇询开销，6 6 图4 6 随机晨游算法下的查询成功率6 7 图4 7 随机缦步算7 去下的甲均查询开销6 9 图4 8 绥存密度的影响7 0 削5 1 奇询硝且处王l i l 流柠图8 l 罔5 2 验汀处即流榉阁8 3 幽5 4 缓存密皮。t t l = 3 0 0 。8 5 罔5 5 关联转发j ：急图8 8 圈56 二次天联币恿图8 9 同5 7 肢务7 苘足车9 2 图5 8 转绶开销。9 2 x 1 1 1 声明 我声明本论文足我本人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，本论 文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的 兑明并表示了 谢意。 作者签名： 关言 论文版权使用授权书 目期：2 0 0 6 3 2 9 本人授权中国科学院计算技术研究所可以保留并向国家有关部 门或机构送交本论文的复印件和电子文档，允许本论文被查阅和借 阅，可以将本论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) 作者躲关雪聊潞篆心隰2 晰。2 9 第一章引言 近年来，对等网络日益成为一个热门的话题。对等网络的快速发展得益于微芯片技 术的的快速发展，个人计算机的日益普及以及网络技术的迅猛发展通过将分布在 i n t e m e t 边缘的众多节点联系起来，集合它们的计算能力以及存储空问等资源，对等网 络口r 以以极低的代价形成巨大的服务能力。也正因为如此，对等网络得到了快速地增长。 目前，已有数鼋众多的对等网络得到部署，包括n a p s t e r ，g n u t e l l a ，s e t i ，f r e e n e t 以及 g r o o v e 网络等应用，分布在包括文件共享，分布式计算，信息交流与协作等多个领域。 在对等网络中，所有节点处于对等地位，每个节点都可以既足服务提供者，同时也 可以是服务请求者，而整个对等网络的服务能力则由网路中的节点所提供的共享资源来 决定。显然，对等网络的中节点越多，节点提供的荩享资源越大，则对等网络的服务能 力也越强。向网络的中的节点所能得到的共亭资源也越多。这样，就形成了一个自我催 化的循环过程。最早的无结构对等网络g n u t e l l a 网络在短短的六个月内从最初的一千个 节点迅速地增长到了近五万个节点，由此形成了巨大的服务能力。 随者网络的进一步普及，将会有更多的计算机加入对等网络，扩大其规模。另外， 随着无线网络等技术的进一步发展，以后的对等网络中将出现大黾的电子产品，例如 p d a ，多功能的移动电话等。这些电子产品的加入将使对等网络的性质更复杂化，并进 一步扩大对等网络的规模。 网络规模的扩大和节点的多样性将使得对等网络的性质变得更复杂，如何有效地查 找其一 的共享资源变得更加困难，从而要求更有效的资源搜索算法。 1 1 无结构对等网络及其搜索算法 在对等网络中，无结构对等网络具有查询方式灭活，可适应高度动态的i n t e m e t 环 境等优点。基本上。无结构对等网络对其中的节点没有任何束缚，节点可以随意地加入 或退出对等网络。显然，这种随意性使得无结构对等网络对环境有高度适应性，并免除 了对等网络的管理困难。 另外，无结构对等网络对苁享内容的放置也不做任何规定。结构时等网络通过分布 ，哈希衰( d h t ) 严密控剐苁亨内容的放置，这为以后查找莛亭内容提供了方便，可以实 现o ( 1 0 9 n ) 的搜索开销。但是结构对等网络这种做法需要维护结构，并且难以实现部分 中画科翠院蹲上学似论丈：对等州嚣内容棺蠢及豪b f 缵靠研究 匹配查询。无结构对等网络不对共事内容的放置做f e 何规定免除了结掏维护以及锊珲 开销，提高了网络的适应性，并且可以实现关键字查询等灵活的查询方式。 无结构对等网络的内容查询只能依靠邻居转交的方式进行。每个节点在加入刘等网 络的时候通过一些手段获取它的邻居节点，节点根据自己的能力及意愿维护相应数塌的 邻居节点，在邻居节点下线的时候还可以再次获取邻居节点来补充。当意图发起一次查 询时，节点生成查询消息，其上肓查询内容的匹配串等相关信息，节点根据所采用的具 体算法，自行决定将查询消息转交给其邻居中的所有或部分节点。类似地，当收到查淘 消息的时候，节点根据所采用的具体算法自行决定将查询消息转交给其邻居中的所有 或部分节点，或者在匹配其上的共享内容时返回查询命中消息。 无结构对等网络通过松散化节点间的相互联系来换取对动态环境的适应以及灵洒 的查询方式，这实际上是在网络的搜索性能与网络的灵活性和适应性之间的一种折衷。 由于缺少结构的辅助，无结构对等网络的搜索性能一直比较低，这使得无结构对等网络 的内容搜索算法一直是重要的研究内容。 提高对等网络的搜索性能包括提高查询成功率以及降低查询开销。这两个方由i 足相 关的，查询成功率提高了可以降低重复发起的查询，从而降低、p 均查询开销，同样，比 较两个搜索算法的开销时应该在相近的查询成功率下比较。而无结构对等网络的查询开 销主要包括两个方面：一个是传递查询消息所耗费的网络开销；另一个是节点收到查询 消息时，进行共享内容匹配检查时所耗费的c p u 计算时日】。 目前的无结构对等网络内容搜索算法可以分为三类：盲搜索算法，也就是节点发现 算法：信息搜索算法：索引缓存算法。这三个方面的算法各自的侧重点不同。盲搜索饽 法基本上只利用极少的网络信息来进行查询工作，主要的努力方向是降低查诲的) c 余歼 销。意即在查询被满足时尽快地停止查询。盲搜索算法是无结构对等网络搜索饽法的摹 础，基本上，信息搜索算法以及索引缓存方法都建立在盲搜索算法之上。信息搜索7 法 的主要努力方向是提高查询的精确性，通过在节点间维护一些信息，以此知逝盘咖的方 向，使其偏向更有可能找到共亨内容的符点。索引缓存方法将查询的结果缓行f 求以 备后续查询使用。索引缓存方法主要足利用相同的查询会被圣复提交的特性，以比较低 的代价朱扩大网络中索引信息拥有告的数量。从而大幅度降低查询的开销。 1 2 已有盲搜索算法的不足 目前有多种无结构对等网络的盲搜索算法，这包括原始的g n u t e l l l a 算法 g n u t e l l a 】 m o d i f i e d b f sg 法 k g 0 2 i ，i t e r a t i v e d e e 妒n i n g y g 0 2 】e x p a n d i n g r i n g l c 0 2 算7 去 以及k - r a n d o m w a l k e r l c 0 2 算法等。 第一审：引言 g n u t e l l a 网络采用洪泛方式分发查询消息，完全依靠消息生命期来控制查询的规模， 这种方法使得每次查询的规模随消息生命期以指数增长。在 j r 0 1 l t 辛讨论了g n u t e l l a 网 络中一次查询的规模( 可达用户数) 随网络邻居节点度n 及消息生命期t 的变化，如下表 所示： 表1 1g n u t e u a 网络可达用户数 仁， 扛2降j t - - 4弘，t = 6t = 7 n = 22 4 681 0 1 21 4 n = 3392 l4 59 31 8 93 8 1 n = 441 65 21 6 04 8 4 l ，4 5 64 ，3 7 2 肛552 51 0 54 2 5 l ，7 0 56 ，8 2 52 7 ，3 0 5 n = 663 61 8 69 3 6 4 ，6 8 62 3 ，4 3 61 1 7 ，1 8 6 n = 7 7 4 93 0 1l ，8 1 31 0 。8 8 56 5 ，3 1 73 9 1 ，9 0 9 n = 886 44 5 63 ，2 0 02 2 ，4 0 81 5 6 ，8 6 4l ，0 9 8 ，0 5 6 当网络邻居节点度n 或查询生命期t 较高时，g n u t e l l a 网络中一次查询的可达用户 数迅速提高到难以接受的程度。g n u t e l l a 算法没有提供满足截止机制，在查询已经得到 满足的情况下，各查询分枝会继续进行，导致大的冗余开销。 i t e r a t i v e d e e p e n i n g e x p a n d i n g r i n g 算法相比于g n u t e l l a 算法实现了一定的查 询满足截止能力。i t e r a t i v e d e e p e n i n g e x p a n d i n g r i n g 一个“睡眠一激发”机制来逐 步增大查询消息的生命期，在查询没有得到满足时增加查询消息生命期，得到满足的时 候则停止激发，但是i t e r a t i v e d e e p e n i n g e x p a n d i n g r i n g 算法没有能力感知网络状 况，魁以控制每次激发的查询规模。 k - r a n d o m - w a l k e r 算法实现了较好的查询规模开销控制，可以控制每轮的查询规模 ；超过( k - i ) 却。这里的k 为漫游消息并发数，p 为漫游消息返回检查周期。 k - r a n d o m w a l k e r 算法的缺点在于难以在每次查询选择适当的k 以及p 的值，并且存在 一定的查询消息重复问题。 一个好的旨搜索算法应该尽量避免要求对查询对象在对等网络中的相关信息有预先 的了解，因为这是无结构肘等网络中单个节点难以做到的，这些发出查询的节点基本不 町能预先获得这些信息，同样，也不应要求对对等网络的状况等信息有实时的了解，因 为在高度动态的无结构对等网络中，实时收集并发布相关的统计信息极为困难。搜索算 法廊该有能力在矗瑚过程中收集相关信息，再根据查询对象以及网络状况的不同，自适 府地控制每轮查询的规模。 0 持 珩 皤 瑚；呈删一一一 中国科 院博上。7 - 论文；对等叫络内容撞赢及禾i 缓律研究 1 3 目前索引缓存研究的不足 目前一些分布式索引缓存算法被提出来以改善无结构刘等刚络的搜索忖能，包括 s r i p a n i d k u l c h a i 提出的简单u i c 方法 k s 0 1 ，m a r k a t o s 对u 1 c 方7 上的改新e m 0 2 】，以及 w a n g 等提出的d i c a s 方法 w x 0 4 等。这些算法利用无结构列等网络的查询特性通 过扩大网络中索引信息的数量来有效地降低查询开销。 分布式索引缓存方法是一个比较新的课题。在无结构对等网络中，分布式索引缓存 方法基本的思想是以较低的代价扩大网络中的索引信息数鼍来提高网络的搜索忖能，但 是，目前的研究对影响对等网络中的索引信息数量的因素，以及这些因豪足如何通过影 响网络的索引信息数量来影响网络的搜索性能还缺少了解。在对等网络中，索引信息的 扩散是通过查询来驱动的，成功的查询结果被缓存下来，使得索引信息可以在网络扩散 开来，另外，目前的索引缓存算法使用缓存生命期机制来对抗网络动态性和节约存储空 间，这种过期机制使得网络中的索引信息消失。目前这方面的研究还没能从整个系统的 角度来研究这两个因素的在索引信息扩散过程中的作用，对查询到达速事以及缓存生命 期时长如何影响网络的索引信息密度缺少定量的研究，对这些因素如何进一步影响网络 的搜索性能还不了解。 同时，目前对无结构对等网络索引缓存算法的研究对索引缓存方法所引起的问题也 没有足够重视。事实上，由f 索引与共享内容相分离，于是会带来两个问题：1 ) 索引信 息无效；2 ) 索引信息虽然有效，但是节点不能提供服务。 第一个问题是由于对等网络的动态性所引起。无结构刈等网络是一个高度动态的网 络，节点可以频繁地进出网络，并随意地增删自己的共享内容，基本上不受任何约束。 当对等网络中的索引信息指向的内容出现了变化，就会使得相应的索引信息失效，成为 一个错误的索引信息，例如，提供共享内容的节点下线，或者共享内容被删除，部可以 使得指向这些其享内容的索引信息失效。在使用索引缓存的对等叫络中失效的索引信 息会误导对等网络的内容查询，使得查询者误以为已经找到所需的内容，这种错误实际 上浪费了查询开销。降低了对等网络的搜索性能。 目前的索引缓存方法或者使用缓存生命期机制来对抗网络动态性带来的失效风险， 或者没能关注这个问题。缓存生命期机制要求对每个索引缓存计鲜其，上俞期，一旦，上命 期超时则不再使用，但是，缓存生命其机制并不检查索引f f l 恩的仃散性，x tf 那些，上余 期不超时但已经失效的索引信息没有辨别力，这使得丈效索引信息会在对臂嘲络，l ，自 敞。而这些扩散出去的失效索引信息会在网络中长期存在，误旨对等刚络的直询，降低 其搜索性能。 4 第一葶：引言 第二个问题实际足索引缓存引起的对等网络负载均衡问题。无结构对等网络的负载 均衡包括内容直询的负载均衡和内容共事的负载均衡两个方面。利用索引缓存方法可以 提高删络的搜索性能，但是会带来内容共享上的负载均衡问题。在使用索引缓存方法对 等州络中，节点对内容的查询很大程度上依赖网络中缓存的索引信息。索引缓存方法的 思想足以较低的代价扩大对等网络中索引信息拥有者的数量，以此提高搜索效率，降低 搜索丌销，但是索引缓存不会影响对等网络中实际的共享内容的数量。对等网络中指向 菜一共孛内容的索引越多，则该共事内容越容易被发现，这样，节点收到的内容共享请 求也越多。过多的内容共享请求将使得节点应接不暇，并使得其中部分请求节点得不到 内容尖亭服务。 目前的研究只注意到索引缓存方法所带来的好处，对其所带来的问题还不够重视。 对等网络的根本目的是资源共享，从查询开销的效率上来说，虽然用户找到了共享内容 的位琶，但是如果内容共享节点不能