（计算机软件与理论专业论文）基于superpeer结构的p2p数据库模式匹配研究.pdf

一 、s，：t 原创性声明和关于论文使用授权的说明 原创性声明 3 6 8y 17 9 1 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 芏蕴 日期： ! ! ! ：笸金 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：丝导师签名：龇 - j _，j 伪 卜 馐 目录 摘要i a b s t r a c t u i 第1 章绪论1 1 1 研究意义1 1 2 研究现状及相关研究3 1 2 1p 2 p 系统及相关研究3 1 2 2 数据库系统及特点：5 1 2 3p 2 p 并1 1 数据库系统的结合p d m s 一6 1 2 4 模式匹配技术及应用7 1 3 本文的工作1 0 1 4 本文的组织结构l o 第2 章基于s u p e r - p e e r 拓扑结构研究及设计1 2 2 1p 2 p 系统拓扑结构1 2 2 1 1 中心化拓扑结构1 3 2 1 2p u r e p e e r 结构1 5 2 1 3s u p e r - p e e r 结构1 7 2 2s u p e r - p e e r 拓扑结构分析及设计原则18 2 2 1 应用背景及结构分析1 8 2 2 2s u p e r - p e e r 结构设计原则2 2 2 3 本文的拓扑构造方法2 2 2 3 1 域和主题概念2 3 2 3 2 普通节点的加入2 4 2 3 3 超级节点的构成2 6 2 3 4 系统结构2 8 2 4 小结3 3 第3 章s u p e r p e e r 结构中的模式匹配技术3 4 山东大学硕十学位论文 3 1 问题引入3 4 3 2 模式匹配技术在p d m s 中的作用3 5 3 3 提出基于实例的匹配方法3 7 3 3 1 匹配模型3 7 3 3 2 属性重要性排序3 8 3 3 3 构造属性分类器4 2 3 3 4 构造最小距离目标函数4 5 3 4 匹配实验4 6 3 5 小结4 7 第4 章结束语与展望4 8 4 1 总结4 8 4 2 展望4 9 参考文献5 0 致谢5 5 攻读学位期间发表的学术论文目录5 6 攻读学位期间参与的科研项目5 7 靠1 _l-1，-l1l 山东大学硕士学位论文 t a b l eo fc o n te n t s a b s t r a c ti nc h i n e s e i a b s t r a c ti ne n g l i s h r i c h a p t e r1i n t r o d u c t i o n 1 1 1r e s e a r c hs i g n i f i c a n c e 1 1 2c u r r e n tr e l a t i v er e s e a r c h 3 1 2 1p 2 p s y s t e m 3 1 2 2d a t a b a s es y s t e ma n dc h a r a c t e r i s t i c 5 1 2 3i n t e g r a t ep 2 pa n dd a t a b a s es y s e t m ：p d m s 6 1 2 4s c h e a mm a t c h i n gm e t h o da n da p p l i c a t i o n 7 1 3t h ew o r ko f t h ep a p e r 1 0 1 4t h es t r u c t u r e 1 0 c h a p t e r2s u p e r - p e e rb a s e dt o p o l o g ys t r u c t u r er e s e a r c ha n dd e s i g n 1 2 2 1p 2 ps y s t e mt o p o l o g ys t r u c t u r e 1 2 2 1 1c e n t r a l i z e ds t r u c t u r e 1 3 2 1 2p u r e p e e rs t r u c t u r e 15 2 1 3s u p e r - p e e rs t r u c t u r e 1 7 2 2s u p e r - p e e rt o p o l o g ya n a l y s i sa n dd e s i g np r i n c i p l e 18 2 2 1a p p l i c a t i o nb a c k g r o u n da n ds t r u c t u r ea n a l y s i s 1 8 2 2 2s u p e r p e e rd e s i g np r i n c i p l e 2 2 2 3p r o p o s e dn e w t o p o l o g yc o n s t r u c t i o nm e t h o d 2 2 2 3 1c o n c e p to f d o m a i na n dt h e m e 2 3 2 3 2j o i nn o r m a lp e e r s 2 4 2 3 3c o n s t i t u t i o no f s u p e r - p e e r 2 6 2 3 4o u rp r o p o s e ds y s t e ms t r u c t u r e 2 8 2 4s u m m a r y 3 3 c h a p t e r3a p p l y i n gs c h e m am a t c h i n gi no u rs t r u c t u r e 3 4 t li 东大学硕士学位论文 3 1b a c k g r o u n di n t r o d u c t i o n 3 4 3 2t h er o l eo fs c h e m am a t c h i n gi np d m s 3 5 3 3p r o p o s e di n s t a n c eb a s e dm a t c h i n gm e t h o d 3 7 3 3 1f r a m e w o r ko fs c h e m a m a t c h i n gm e t h o d 3 7 3 3 2r a n k i n gs c h e m aa t t r i b u t e sb yi m p o r t a n c e 3 8 3 3 3c l a s s i f y i n ga t t r i b u t e s 4 2 3 3 4c o n s t r u c t i o nt h ec r i t e r i o nf u n c t i o n 4 5 3 4e x p e r i m e n tr e s u l t s 4 6 3 5s u m m a r y 4 7 c h a p t e r4c o n c l u s i o n 4 8 4 1s u m m a r i z e 4 8 4 2p r o s p e c t ，4 9 r e f e r e n c e 5 0 a c k n o w l e d g e 5 5 t h et h e s i sp u b l i s h e df o r t h em a s t e r sd e g r e e ：。5 6 t h ep r o j e c t sp a r t i c i p a t e df o rt h em a s t e rm a s t e r sd e g r e e ，5 7 “、， 山东大学硕士学位论文 摘要 模式匹配技术在当今已经成为众多领域的研究热点，如：数据集成，数据仓 库，数据挖掘。其作用是为异构数据源提供两个或多个模式间的元素( 属性) 间 对应关系，关键是如何寻找两个元素间的语义对应关系。模式可以具有不同的结 构、定义、命名方式，所以要寻找对应关系通常需要从多方位发掘匹配，采用多 匹配器相结合的方式，如：结构匹配器，实例匹配器，基于约束匹配等。而且对 于不同的领域匹配器的构造通常也有差异，另外目前仍没有一种模式匹配技术是 全自动化的，或多或少需要人工干预。通常来说，采用何种匹配器以及匹配器采 用何种技术来实现需要根据应用背景来考虑。所以模式匹配过程较为复杂，但是 如果能较大程度的减轻人工劳动强度提高生产效率，也是非常有价值的。 本文以对等网络( p e e r t o p e e r ) 的数据共享为应用背景来考虑模式匹配的 作用及实现。p 2 p 是一种不同于传统网络的新型结构，其特点是：网络中的任何 一个节点都是关系平等的，节点既可以提供资源也可以请求资源，也可以随时键 入网络或退出网络。p 2 p 系统的结构众多，不同的拓扑结构使节点具有不同的服 务方式。本文通过详细的研究和分析，选取了以s u p e r p e e r 结构为基础作为研究 对象。本文的重点研究内容分两部分：1 ) 构造一种新的基于s u p e r p e e r 的拓扑 结构，研究模式匹配对其作用。2 ) 根据上述结构，提出一种基于实例的模式匹 配方法。 对于问题1 ) ，本文提出了一种基于域主题划分的二重超级节点结构。不同 于常规的模式匹配技术，p 2 p 环境下的模式匹配具有其特殊性：1 ) p 2 p 环境必须 具有可扩展性( s c a l a b l e ) ，节点可以随时加入、离开网络。如何考虑在这种动 态环境下新加入的节点或退出节点与网络中其它节点的模式关系。2 ) 在数据共 享背景下以节点的信息查询为例，什么样的s u p e r p e e r 结构才具有最佳的查询效 率，也就是超级节点和普通节点的结构关系。这些问题在文中都有详细的研究。 对于问题2 ) ，首先详细分析了模式匹配对于p 2 p 的数据共享的作用，这也是 本文重点研究内容。其实，目前的大多数相关研究中都使用了模式匹配技术，但 是其重点都是研究如何改进查询路由或查询算法，而没有注重模式匹配这一点。 本文通过假设模型提出：如果模式中的元素具有语义对应关系，那么这两个元素 山东大学硕士学位论文 具有相同的重要性。通过r f 多决策树算法并d r b f 分类器对提取属性特征，寻找属 性在模式中的位置，进而构建最小距离函数判别属性是否具有对应关系。该思想 非常适合于p 2 p 环境下，因为它具有以下特点：1 ) 通过多决策树方式产生精确的 匹配器。2 ) 可以处理大数据量和数据的可变性。3 ) 域元数据表适应对于新加入 的节点或者退出的节点所导致的数据变化。 最后，在文中通过u c i 数据集实验证明了该方法的匹配效果。 关键词：p 2 p 系统；s u p e r - p e e r 结构；模式匹配；可扩展性：语义对应 i i f ， t j。，j一 山东大学硕士学位论文 a b s tr a c t n o w a d a y s ，s c h e m am a t c h i n gi sa l r e a d yb e i n gah o tt o p i ci nm a n yf i e l d s s u c ha s d a t ai n t e g r a t i o n ，d a t aw a r e h o u s ea n dd a t am i n i n g i tw a su s e dm a i n l yt op r o v i d e c o r r e s p o n d i n gr e l a t i o n s h i p sb e t w e e na t t r i b u t e so fh e t e r o g e n e o u ss c h e m a s ，t ow h i c h t h ek e yp r o b l e mi sh o wt of i n dt h es e m a n t i cc o r r e s p o n d i n gb e t w e e na t t r i b u t e s a l w a y s ， s c h e m aw i t hd i f f e r e n ts t r u c t u r e ，d e f i n i t i o n ，n a m i n gc o n v e n t i o n s s o ，i no r d e rt of i n d t h ec o r r e s p o n d i n gr e l a t i o n s h i pw eh a v et oc o m b i n ev a r i o u ss c h e m am a r c h e r s ，f o r e x a m p l e ，s t r u c t u r em a t c h e r , i n s t a n c em a t c h e r , r e s t r i c t i o n - b a s e dm a t c h e rw h a t sm o r e ， t h ec o n s t r u c t i o no fs c h e m am a r c h e rm a yd i f f e r e n t 、 ，i t hd i f f e r e n ta p p l i c a t i o nd o m a i n c u r r e n t l yn o n eo fe x i s tt h e o r yo rs y s t e mi st o t a l l ya u t o m a t i c ，w h i c hn e e d sm a n u a l i n t e r v e n t i o nm o r eo rl e s s b e f o r ew ec o n s t r u c tas c h e m am a t c h e rw es h o u l dc o n s i d e r t h ea p p l i c a t i o nb a c k g r o u n dc o m p r e h e n s i v e l y t h o u g ht h ep r o c e s so fi m p l e m e n t a t i o n m a t c h i n gc a p a b i l i t yi sc o m p l e x ，i t ss t i l lo fh i g hv a l u a b l ew i t hg r e a t l yd e c e a s i n gh a n d l a b o ra n di n c r e a s i n gt h ee f f i c i e n c y i nt h i sp a p e rw ef o c u so nt h ef u n c t i o n a l i t ya n di m p l e m e n t a t i o no fs c h e m a m a t c h i n gm e t h o dw i t ht h ee n v i r o n m e n to fd a t as h a r i n gu n d e rp e e r - t o p e e rs y s t e m o t h e rt h a nt r a d i t i o n a ln e t w o r k ，p 2 pc h a r a c t e f i s t i z e ：e v e r yp e e ri np 2 pi se q u a li n f u n c t i o n , w h i c hc a i lp r o v i d er e s o u r c et oo t h e r sa l s oc a l ls e n dr e q u e s tt oo t h e r s ，b e s i d e t h a ta n yp e e rc a na d di n t oo rl e a v et h en e t w o r kf r e e l y p 2 ps y s t e mh a sn o to n l yo n e s t r u c t u r e ，d i f f e r e n tt o p o l o g ys t r u c t u r es u i t sf o rd i f f e r e n ta p p l i c a t i o n h e r e ，w ep r e f e r t h es u p e r - p e e ra st h eb a s es t r u c t u r ea f t e rc o n s i d e r i n go u ra p p l i c a t i o nc o m p r e h e n s i v e l y i nt h i sp a p e r , w em a i n l yf o c u so nt h et w op a r t s ：1 ) c o n s t r u c tan e ws u p e r - p e e rb a s e d p 2 pt o p o l o g y , a n dt h e nw ed oad e e p g o i n gr e s e a r c ho nt h ef u n c t i o no fs c h e m a m a t c h i n g 2 ) a c c o r d i n gt ot h en e ws t r u c t u r ew ep r o p o s e d ，w ei m p l e m e n t a n i n s t a n c e b a s e ds c h e m a m e t h o dw h i c hs u i tf o ro u re n v i r o n m e n tw e l l w i t hr e g a r dt ot h ef i r s tp a r t ，w ep r o p o s ean e wt o p o l o g ye m p l o yd o m a i nt h e m d i v i d e d 、 ，i t hd o u b l es u p e rp e e r sp 2 ps t r u c t u r e w h a td i f f e r e n t 、肮t ht h ec o m m o n i i i l l 东大学硕士学位论文 s c h e m am a t c h i n gm e t h o d ，t h es c h e m am a t c h i n gi np 2 pw i t hi t s d i s t i n c t i v e n e s s ：f i r s t l y , a n yp 2 ps y s t e mi sc h a r a c t e r i s t i c 谢t hs c a l a b l e ，w h i c hm e a n sp e e r sc a nj o i nt h e n e t w o r ko rd i s c o n n e c ta tr a n d o m s o ，h o wt od e a l 谢1t h es c h e m ar e l a t i o n s h i po ft h e n e wa d d e do rl e a v e dn o d e si ns u c had y n a m i ce n v i r o n m e n ti sn e e dt ob ec o n s i d e r e d s e c o n d l y ，t a k et h ei n f o r m a t i o nq u e r yf o re x a m p l e ；w h a tt y p eo fs t r u c t u r ec a ng e ta n o p t i m a le f f i c i e n c y i no t h e rw o r d s ，h o wt oo r g a n i z et h es t r u c t u r er e l a t i o nb e t w e e nt h e s u p e rn o d ea n dn o r m a ln o d ec a nw eg e tab e t t e rq u e r ye f f e c t a l lt h e s ep r o b l e m sa r e g e td e t a i l e di no u rp a p e r f o rt h es e c o n dp a r t ，w ef i r s t l yd om u c hr e s e a r c ho nt h ef u n c t i o no fs c h e m a m a t c h i n gt oo u rp 2 pn e t w o r k ，w h i c hi so n eo ft h em o s ti m p o r t a n ti s s u e si no u rp a p e r i nf a c t ，m o s to ft h ec u r r e n tr e l a t i v er e s e a r c ha l le m p l o y e dt h es c h e m am a t c h i n g t e c h n o l o g y , b u tn e a r l ya l lo ft h e mp a ya t t e n t i o nt oh o w t oi m p r o v et h eq u e r yr o u t ea n d q u e r ya l g o r i t h m i nt h i sp a p e r , b yp u t t i n gf o r w a r dah y p o t h e s i sm o d e l ：t h et w o a t t r i b u t e sh a sr e l a t i v ei m p o r t a n c ei nt w os c h e m a s ，i f 缸l e yh a v ec o r r e s p o n d i n g s e m a n t i cr e l a t i o n s h i p h e r e ，w ea p p l yt h er fn e u r a ln e t w o r ka sm u l t id e c i s i o nt r e e a n dr b fa l g o r i t h ma sc l a s s i f i e rt oe x t r a c tf e a t u r e ，i no r d e rt of i n dt h eu n i q u ea t t r i b u t e p o s i t i o n a tl a s tw ec o n s t r u c tam i n i m u me u c l i d e a nd i s t a n c ef u n c t i o nt od i s c r i m i n a t e t h e b e s tc o r r e s p o n d i n gp a i r s o u rm e t h o di sm u c hf i tt oo u rb a c k g r o u n d ：1 ) m u l t i - d e c i s i o nt r e ec a np r o d u c ea c c u r a t em a t c h e r 2 ) t h ep e e r si nt h ew h o l es y s t e m c a nd e a l 谢t hag r e a tn u m b e ro fd a t aa n di t sv a r i a b i l i t y 3 、d o m a i nm e t a d a t at a b l es u i t f o rn e wa d d e do rl e a v e dp e e r s i nt h ee n d ，o u ra p p r o a c hi sv a l i d a t e db yu c id a t a s e t sa n dt h er e s u l t ss h o wg o o d a c c u r a c y k e y w o r d s ：p 2 ps y s t e m ：s u p e r p o e rs t r u c t u r e ：s c h e m am a t c h in g ：s e aia bie ： s e m a n tic c o r r e s p o n d in g ： 0 1 一 山东大学硕士学位论文 1 1 研究意义 第1 章绪论 网络的出现加速了信息的共享和数据交换，而现代社会中信息量的爆炸式增 长也给数据的存储、查询等带来了新的问题和要求。网络在其5 0 多年发展历程中 先后经历了a r p a n e t 网络、n s f n e t 网络、直到i n t e r n e t 的诞生。网络结构和模式 也在经历着不断的演变，从原始的c s 、b s 到分布式网络，现代网格等，其中 对等网络( p 2 p ) 的出现是一个里程碑式的突破。p 2 p 彻底改变了原始的网络形态， 在p 2 p 网络中所有的节点都是平等的，任何一个节点既可以向网络中其它节点发 出服务请求，同时也可以充当服务对象为其它节点提供服务；网络中节点的数量 越多，请求服务效率也越高。 从1 9 9 5 年n a p s t e r 第一次出现标志着p 2 p 系统的正式使用，到现在g n u t e l l a 、 a v a k i 、p o p u l a rp o w e r 、j x t a 等成熟p 2 p 技术的确立，标志着p 2 p 时代的来临。所 经历的不同的发展阶段，充分说明其对环境、性能等越来越高的要求。p 2 p 技术 特点主要体现在如下几个方面： 1 ) 非中心化( d e c e n t r a l i z a t i o n ) ：p 2 p 网络的一个最大特点就是没有中央 服务器，也就是说网络中的资源是分散各个结点上。这样，对数据的请求和传输 都直接在结点之间进行，无需中间环节和服务器的介入，避免了可能的瓶颈。这 一特点也带来了其在可扩展性、健壮性等方面的优势。 2 ) 可扩展性：p 2 p 网络的另一个特点是允许节点灵活的加入和退出网络，随 着节点数量的增多，不仅对服务的需求增加了，而且系统整体的资源和服务能力 也在同步扩充。这种需求平衡性使得p 2 p 结构在理论上其可扩展性是无限的。 3 ) 健壮性：p 2 p 架构不依赖中心节点，所以在个别结点失效时能够自动调整 整体连接，保持其它结点的连通性。p 2 p 网络是以自组织的方式建立起来的，一 个良好的系统能够根据结点个数、负载情况做出必要调整，有利于提高整体性能。 4 ) 性价比高：p 2 p 架构的网络可以有效地利用网络中散布的大量结点，将计 算任务或数据分布到空闲结点上以提供更高的计算和存储能力，达到高性能计算 和海量存储的目的。 山东大学硕十学位论文 5 ) 隐私保护：p 2 p 网络中信息的传输省去了中间环节，相比传统的中继转发 方法，大大提高了匿名通讯的灵活性和可靠性，为用户提供更好的隐私保护。 6 ) 负载均衡：p 2 p 网络环境下由于每个节点既是服务器又是客户机，同时 因为资源分布在多个节点，更好的实现了整个网络的负载均衡。 尽管p 2 p 有上述诸多优点，它也无法解决所有的应用问题。从第一代集中式 目录结构开始的n a p s t e r 系统，它采用了数据查询和数据下载分开的方式，高效 的为用户提供分布式资源。但也会出现系统瓶颈和扩展性差的问题，这是由其拓 扑结构决定的。第二代的纯对等结构的g n u t e l l a n 町乜铂系统，它在文件共享方面有 良好的性能；但是它具有查询效率低、网络易阻塞的特点。第三代以k a z a a 乜们为 代表的超级节点结构( s u p e r p e e r ) 的p 2 p 系统，吸取了之前系统的优点。不仅 具有良好的扩展性同时也由于它具有结构特征，所以在结构特征的基础上提出很 多改进算法，使查询性能得到很大提升。但是，单纯的改进查询算法或者路由模 式并不能从根本上解决问题，在之前的两个阶段中都是因为系统的拓扑结构限制 的技术的使用。所以，本文希望从拓扑结构方面提升数据共享方面的性能。 由于p 2 p 系统节点数据源的异构性，对于数据共享来说，要在p 2 p 网络中找到 目标资源有两个重要的条件：1 ) 目标节点如何理解查询请求语句中的关键字信 息( i t e m ) 。2 ) 如何保证发出请求的节点高效的寻找到目标节点。这两个问题 本文研究的出发点，也是本文的意义所在。 对于问题1 ) ，也就是当前所说的查询重构问题。在文乜6 们中有相关研究表 明，其实现的关键在于模式匹配技术。如果一个模式中没有目标信息，那么我们 就不需要去进一步搜寻这个节点了。如果有目标信息，我们还需要有理解原始 i t e m 的能力。也就是说把原始查询语句转化为本地模式能够理解的新语句。虽然 目前很少有在p 2 p 系统中研究模式匹配，但是绝大多数都是用到了模式匹配，只 是关注点都放在了查询性能上，本文将p 2 p 中的模式匹配技术做详细的研究。对 于问题2 ) ，也就是如何构建系统拓扑结构的问题，它会影响系统的查询方式， 而且需要根据应用背景综合考虑。 所以，对s u p e r - p e e r 拓扑结构的研究和模式匹配技术是两个相互关联的过 程，本文将深入研究这两个部分。并在最后给出y u c i “踟实验分析，证明了文中 方法的有效性。 2 l | 一 r， 山东大学硕士学位论文 1 2 研究现状及相关研究 1 2 1p 2 p 系统及相关研究 p 2 p 系统的定义b 蜘是：允许一组计算机用户通过网络能直接访问其他用户的 计算机资源，而不需要通过中心服务器，这样通过计算机互联来达到文件、数据 共享的网络称为p 2 p 。p 2 p 系统具有：可扩展性，非中心化，负载均衡的特点。这 里需要强调的是p 2 p 中的计算机在数据请求时是采用直接( d i r e c t l y ) 访问的方 式，这是有和传统c s ，b s 网络结构的最大区别。其次，p 2 p 系统以其良好的扩 展性著称，在传统结构中新的网络用户需要将自身的信息写入到服务器端，这样 当有请求到达时，才可以通过查找服务器的存储信息来返回用户请求。而p 2 p 网 络则不同，任何节点( p e e r ) 可以随时的加入或者离开网络，也不用像任何其它 节点注册。 当然，在第一代集中式目录机构中仍然需要一个充当服务器的节点来存储其 它节点的信息，达到索引的目的。其代表性的是n a p s t e r ，它也是最早出现的p 2 p 系统之一。n a p s t e r 实质上并非是纯粹的p 2 p 系统，它通过一个中央服务器保存所 有用户上传的音乐文件索引和存放位置的信息。当某个用户需要某个音乐文件 时，首先连接到n a p s t e r 服务器，在服务器进行检索，并由服务器返回存有该文 件的用户信息；再由请求者直接连到文件的所有者传输文件。n a p s t e r 首先实现 了文件查询与文件传输的分离，有效地节省了中央服务器的带宽消耗，减少了系 统的文件传输延时。这种方式最大的隐患在中央服务器上，如果该服务器失效， 整个系统都会瘫痪；当用户数量增加到1 0 5 或者更高时，n a p s t e r 的系统性能会大 大下降。 在第二代纯对等p u r e - p e e r 结构中，所有的节点在功能和结构上都是对等的， 每一个节点既可以为其它节点提供服务，也可以向其它节点发出服务请求。但是 由于这种拓扑结构导致其在信息查询的时候主要采用洪泛的方法，所以性能较 低。比如，当前有个一个节点a 需要请求服务，那么它会向所有与它直接相邻的 节点a 1 ，a 2 a n 发送消息，并且同时计算一个t t l ( t i m et ol i v e ) 值。如果它 的邻节点没有返回结果，那么它会把a 的请求转发给与其相连的节点b 1 ，b 2 b m ，同时将当前的t t l 值减l ，采用这种洪泛方式不断将请求在网络中广播，收到 3 山东大学硕十学位论文 消息的节点继续转发a 的请求。直到有节点返回结果，或者所有收到a 节点请求消 息的节点t t l 值都为0 时，表明没有返回结果请求失败。这样的服务请求方式效率 较低，容易造成网络阻塞。随后有改进算法只随即选择一部分节点进行请求转发， 这样虽然提高的效率，但是查询结果并不全面覆盖面不如之前的方法。所以，这 种拓扑结构有其固有的缺陷。 g n u t e l l a 是典型的p u r e p e e r 结构，确切的说是一个p 2 p 文件共享系统。它和 n a p s t e r 最大的区别在于没有索引服务器，它采用了基于完全随机图的洪泛发现 ( 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 a 网络中，存在比 较严重的分区，断链现象。也就是说，一个查询访问只能在网络的很小一部分进 行，因此网络的可扩展性不好。 而第三代s u p e r p e e r 拓扑结构的系统以其性能优势备受关注。在s u p e r - p e e r 结构中，有两种不同的节点。一种是普通节点( n o r m a ln o d e ) ，它存储了数据 信息。另一种是超级节点( s u p e rn o d e ) ，它不存储基本数据信息，而存储与之 相连的普通节点信息。若干个普通节点和一个超级节点链接，形成一个主次结构， 被称为“簇”。超级节点之间再通过相互自由链接的方式构成整个p 2 p 网络。当 有普通节点接受到查询请求时，它只向簇内的超级节点发出信息请求，然后超级 节点再查询簇内各节点。如果能够找到目标信息，则可以快速返回结果。如果找 不到信息则需要将请求信息像p u r e p e e r 一样的方式进行转发，所不同的是。超 级点之间构成一个高速转发层，每次转发后都是先在各簇内进行查询，查询不到 结果才会继续转发。这样效率明显l 匕p u r e - p e e r 有较大提升。 第三代p 2 p 中最著名的是k a z a a 。有统计称使用k a z a a 软件进行文件传输消耗 了互联网4 0 9 6 的带宽。之所以它如此的成功，是因为它结合了n a p s t e r 和g n u t e l l a 共同的优点。从结构上来说，它使用了g n u t e l l a 的全分布式的结构，这样可以是 系统更好的扩展，因为它无需中央索引服务器存储文件名，它自动的把性能好的 机器作为超级节点，并存储着离它最近的叶子节点的文件信息，这些超级节点， 再连通起来形成一个o v e r l a yn e t w o r k 。 由于超级节点的索引功能，使搜索效率 4 览 一 j 1 l 1 i 山东大学硕士学位论文 大大提高。 所以，为了能快速的处理簇内的信息请求，超级节点应该选取稳定的，性能 较强的节点，以避免它成为瓶颈。当簇内的普通节点数量为0 时，s u p e r -