（计算机软件与理论专业论文）p2p网络拓扑结构优化与资源定位方法研究.pdf

硕士学位论文 m a s t e r s 。r r l e s l s 中文摘要 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 模型利用了无结 构及结构化p 2 p 网络的优势，尽量避开它们的不足之处。 本文提出的优化算法和模型力求简单，在实际的应用中可以将其作为一个模块 加入到应用程序中发挥其作用。本文所做的研究是以提高p 2 p 网络资源定位效率为 目地的，在为实际应用设计系统时，本文得出的理论上的结论可供开发人员参考。 关键词：p 2 p 网络；拓扑结构；资源定位算法；冗余消息；分域式p 2 p 网络；边界 结点 硕士学住论文 m a s t e r st h e s i s a b s 仃a c t t h ep r o b l e mo fr e s o u r c el o c a t i o ni ss t i l la no p e nq u e s t i o ni nc u r r e n tp 2 pn e t w o r k ； t h ea p p l i c a t i o na b o u tl o c a t i o nm e t h o d ss h o u l db ed e s i g n e df o rs p e c i f i cp e r f o r m a n c ei n s p e c i f i ce n v i r o n m e n t o fc o u r s e ，t h ep e r f o r m a n c ea n a l y s i s o fv a r i o u sp o s i t i o n i n g m e t h o d sh a sv e r yg o o dr e f e r e n c ef o rt h ed e s i g nb e t t e rp o s i t i o n i n gm e t h o di na c t u a l a p p l i c a t i o n t h i sa r t i c l ei sm a i n l ya n a l y s i sa n do p t i m i z a t i o no nt h ep 2 pn e t w o r kr e s o u r c e 1 0 c a t o rm e t h o d s u n s t r u c t u r e dp 2 pn e t w o r kr e s o u r c el o c a t o rs e a r c hi sm a i n l yb a s e do i lt h ef l o o d i n g s e a r c h ，w h i c hw i l le n g e n d e ral o to fr e d u n d a n td a t ap a c k e t s i nt h i sp a p e r , w ep u tf o r w a r d t h ec o n d e n s i n gf o r w a r d l i s ta l g o r i t h m ( c f l ) t or e d u c er e d u n d a n c y t h r o u g ht h e s i m u l a t i o ne x p e r i m e n t sw ef i n dt h a tt h ec f la l g o r i t h mh a sh i g h e rp e r f o r m a n c e c o m p a r e dw i mt h ef l o o d i n ga l g o r i t h m 1 1 1 er e s o u r c el o c a t o ri ns t r u c t u r e dp 2 pn e t w o r k h a st h es u p p o u to fh i f g h e re f f i c i e n tr o u t i n ga l g o r i t h m ；h o w e v e r , s t r u c t u r e dp 2 pn e t w o r k s d on o ts u p p o r tf u z z yq u e r i e s ，t h ea m o u n to fi n q u i r e di n f o r m a t i o nd o e sn o ta c h i e v et h e u s e rr e q u i e m e n t s i no r d e rt op o s i t i o n i n gr e s o u c e se f f i t i e n t l yb u tn o th a v i n gt o om u c h r e d u n d a n c y ，as u b d o m a i nh y b r i dp 2 pm o d e li sp r o p o s e di nt h i sp a p e r w eg i v ead e t a i l e d a n a l y s i sa b o u tt h ed e s i g ni d e ao f t h em o d e l t h a th y b d dp 2 pm o d e lm a k e sf u l lu s eo ft h ea d v a n t a g e so ft h eu n s t r u c t u r e da n d s t r u c t u r e dp 2 pn e t w o r k s ，a sf a ra sp o s s i b l et oa v o i dt h ei n a d e q u a c i e so ft h e i r o nt h e r e a l i z a t i o no ft h em o d e l ，t h e r ei sad e t a i l e di n t r o d u c t i o ni nt h i sp a p e r w ed e s i g no u ra l g o r i t h r nt ob es i m p l e ，a sam o d u l et h a tc a nb ee a s i l ya p p l i e dt o e x i s t i n gp 2 ps y s t e m sf o ri m m e d i a t ei m p a c t t h i sp a p e ri sb a s e do ni m p r o v i n gt h e e f f i c i e n c yo fp 2 pn e t w o r kr e s o u r c el o c a t o r t h et h e o r e t i c a lc o n c l u t i o n so ft h i sp a p e rc a n b ear e f e r e n c ep r o v i d e dt ot h ed e v e l o p e r s k e yw o r d s ：p e e r - t o - p e e r ( p 2 p ) n e t w o r k ；t o p o l o g ys t r u c t u r e ；r e s o u r c e l o c a t i o n a l g o r i t h m ； r e d u n d a n tm e s s a g e ；s u b - d o m a i nh y b r i dp 2 pn e t w o r k 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 羊罅 1 日期：叼年月，矿日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者签名： 茅亿耻 日期：叩年6 月产日 导师签名： 呐：1 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程 中的 规定享受相关权益。圃童诠塞握变蜃进卮! 旦坐生；旦二生i 旦三生蕴鱼! 作者签名： 牛龙耻 日期：q 年，月f 日 尹佃 也产月 卜否 么严 农 饥 签 ： 师期 争日 1 1p 2 p 网络概述 第1 章绪论 p 2 p 网络是分布式系统与计算机网络相结合的产物，是采用对等模式工作的计 算机网络。图li 描绘了随着分布式系统规模的扩展，分布式计算的模式发生的相 应改变。在对等网络中，每个嘲络结点在行为上是自由的，在功能上是平等的，所 有结点自组织成一个整体网络。囡此，它能够极大程度地提高网络效率及资源利用 率，充分利用网络中每个结点的带宽并充分开发每个网络结点的潜力。 系魄= 嘶模 n 和i , a n w a n 月 c l e 闺l1 分布式计算模式与系统规模的关系 横轴：计算机网络在地域分布上的扩展，纵轴：分布式系统在规模上的膨胀 斜箭头：适应于不周需求的分布式计算模式从左到z i 四个框的含义如f m a i n f r a m e ：主机计算，c l a s l o r ：机群计算，g d d ：列格计算p 2 p ：对等计算 世界上第一个应用性对等网络n a p s t e r 出现在1 9 9 9 年，它创造了在半年时问里 拥有5 0 0 0 万用户的网络奇迹，向整个世界展示了p 2 p 优越的性能和巨大的潜力。 在n a p s t e r 之后，涌现出了一系列著名的p 2 p 网络软件：g n u t e l l a ，b i t t o r r e n t ，k a z a a e d o n k e y e m d e ，s k y p e 等i i l 。虽然从1 9 9 9 年到现在只有十年左右时间，但由于p 2 p 网络在工作模式上的优势和对于现代i n t e m e t 应用的适应性，p 2 p 已发展成为计算 机网络的一项重要技术，在学术领域得到了广泛的研究并且取得了一系列可喜的成 果。有研究表明p 2 p 网络在i n t e m e t 中的应用超过了当前流量一半的带宽，被认为 项士学位论文 m a s t e r st h e s l s 是改变i n t e m e t 的新一代网络技术【2 1 1 3 。 1 - 2p 2 p 网络的工作原理及拓扑构建的核心机制 关于p 2 p 网络的分类到目前为止尚未出现公认的，明确的分类方法【4 】【5 1 。本文 从p 2 p 网络设计思想出发，兼顾p 2 p 网络体系结构和出现时间两方面的考虑，将 p 2 p 网络划分成四代： 第一代：集中式p 2 p 网络，它是c s 和p 2 p 两种模式的混合； 第二代：无结构p 2 p 网络，它以分布、松散的结构来组织网络，有些文献中也 常称之为非结构化p 2 p 网络； 第三代：结构化p 2 p 网络，它以准确、严格的结构来组织网络，并能高效地定 位结点的数据； 第四代：混合式p 2 p 网络，它是在非结构化p 2 p 网络和结构化p 2 p 网络的基础 上构建的一种性能良好的p 2 p 网络。 现代计算机网络采用均采用层次化的结构，在应用中表现为一个从高层到低层 的网络通信协议栈。这其中最著名的就是i s o o s i ( 国际标准化组绷开放系统互联) 模型和t c p i p ( 传输控件协议因特网协议) 模型，前者细致、正式，后者更实用。本 文中对于层次化的网络模型均采用t c p i p 模型，如图1 2 所示。 隘涌垂霉：攀獭鬣矽r 攀罗谚移灞 戮翰层0 。( t c e m d p 协议芜，、o ；囊 网络层( i p 协议) ： 网络接入层( 链路协议与物理协议) 图1 2t c p i p 协议栈，p 2 p 工作在应用层 对等计算模式是指上图中四层模型的最高层应用层的工作方式，而下面的 三层通常采用标准的、单一的工作方式，本身并没有集中式与分布式之分，只是为 应用层不同的工作方式提供底层的服务支持。 p 2 p 网络的核心机制，是在应用层建立逻辑上的覆盖网络( o v e r l a yn e t w o r k ) ， 封装下面的三层，让p 2 p 网络的研究者和开发者不必关心下面三层如何工作，而仅 仅去考虑应用层覆盖网络的工作情况，将精力集中于覆盖网络的设计与优化上。虽 然如此，在对p 2 p 网络做基础的研究和设计时，有时还是要考虑到底层的工作情况， 因为应用层建立的覆盖网络与底层实际的物理网络实际的工作情况不可能完全相 2 硕士学位论文 m a s t e r st h e s i s 同，在图1 3 中，覆盖网上的一条逻辑连接a e 对应物理网上的三条物理连接：a c ， c d 和d e 。所以从覆盖网看到的行为与底层物理网络实际的行为通常并不一致。p 2 p 领域的研究者已经对这种不一致性做了大量的工作，尽可能减少两个层次之间的差 异以提高整个网络的效率。简言之，p 2 p 网络工作于应用层，通过良好的设计可以 将网络的底层与覆盖层尽量地融合以提高系统的工作效率6 】【7 1 。 覆盖网 0 层物理网 图1 3p 2 p 覆盖网络和底层物理网络的不一致性 ( 虚线表示逻辑连接，实线表示物理连接) p 2 p 网络在覆盖层上依靠d h t ( d i s t r i b u t e dh a s ht a b l e ，分布式散列表) 来准确、 快速地路由消息和定位数据对象，这是p 2 p 网络的优势【8 】。使用覆盖网络和d h t 机制的p 2 p 网络，为追求性能和效率所付出的代价，是语义模糊查询的困难以及动 态网络环境中错误行为容忍性下降。针对语义模糊查询方面这一问题至今仍然是 p 2 p 领域的一个开放型问题，尤其对结构化p 2 p 网络更为困难；针对动态网络环境 的容错行为，p 2 p 领域的研究者提出的方案各具特色，总体上分两类：即网络周期 性主动更新或是在检测到错误后被动更新。主动更新机制简单但开销很大，被动更 新开销较小但机制复杂。 1 3p 2 p 网络拓扑及资源定位方法的特点 具体地说，p 2 p 网络区别于其它分布式系统的本质特点如下： 1 严格的网络拓扑结构 p 2 p 网络在网络应用层构建了一个有严格拓扑结构的覆盖网，覆盖网拓扑结构 对于一个p 2 p 网络具有基础性的意义，系统的其它许多机制如d h t 、路由、容错 硕士学位论文 m a s t e r st h e s i s 与自适应、自组织等都以覆盖网拓扑结构为基础【9 】【i o l 。具体来说p 2 p 网络通常采用 图1 4 所示的几种拓扑结构m l 。 ( 1 ) 星形结构- - n a p s t e r 、b i t t o r r e n t ( 2 ) 随机图结构- - g n u t e i l a 、f r e e n e t 3 ) 双层结构一k a z a a 、e d o n k e y e m u l e ( 4 ) 带弦环结构- - c h o r d 、k a d e m l i a lb xze c 卜 e ( 5 ) 超立方体结构- - t a p e s t r y 、p a s t r y( 6 ) 多维空问结构一a 悄 图1 4p 2 p 网络通常采用的拓扑结构 2 确定的结点位置和数据对象位置 分布式散列表( d h t ) 是p 2 p 网络的核心设施。如下图1 5 所示，它通常基于一 致性散列函数，提供对于任何一个结点、数据对象在覆盖网中的位置映射。这一点 在结构化p 2 p 网络中尤其重要，因为它保证了能够准确地定位到某个结点或者数据 对象。 具体地说，如果分布式散列表采用一致性散列函数h ( ) ，对于某个网络结点( i p p o r t , - - - ) ，该结点在覆盖网上将有唯一对应的“结点标识 n o d e l d = h ( i p , p o r t , ) ，i p 4 硕士学位论文 m a s t e r st h e s i s 为结点的i p 地址，p o r t 为端口号，表示其它属性：对于某个数据对象( k e y , - ) ， 它在覆盖网上也有唯一的“对象标识 o b j e c t i d = h ( k e y , ) ，k e y 为对象关键码，一 表示其它属性。对于结点而言，n o d e i d 确定了它在覆盖网中的位置；对于数据对象 而言，o b j e c t l d 确定了它的索引信息在覆盖网中存放的位置1 4 1 。 图1 5d h t 在p 2 p 系统中的位置 3 高效的路由 p 2 p 网络通常有适合自己的路由算法，以保证高效的路由。任意两个结点间定 位所需的覆盖网路由跳数典型地为t t l ( j i e 结构化p 2 p 网络) 或l o g n ( 结构化p 2 p 网 络) ，t t l ( t i m e t o 1 i v e ) 为跳数限制，n 为当前网络中的结点总数。由于覆盖网与物 理网的不一致性，实际路由跳数会高于覆盖网路由跳数，但仍可以控制在l o g n 的常数倍范围之内。具体来说，p 2 p 系统的路由方法大致有【l5 】： ( 1 ) 无结构路由结点以洪泛法或者类似的方法发送消息给自己的每个邻 居，邻居收到消息后重复同样的步骤，直到定位成功，通常会有跳数限制1 【l 以控 制路由范围。典型的系统有g n u t e l l a 、f r e e n e t ，路由跳数为o ( t y l ) 。 ( 2 ) 双层路由通常为双层结构的p 2 p 网络所使用，“普通结点直接发消息 给“超级结点”，“超级结点”之间使用无结构路由。典型的系统有k a z a a 、 e d o n k e y e m u l e 等，路由跳数为o ( 1 ) + o ( t t l ) 。 ( 3 ) 数值邻近路由这里的“数值一通常指结点i d 值，路由过程中消息每前 进一步，当前结点都在自己的路由表中选择与目的i d 最邻近的结点作为下一跳结 点。典型的系统有c h o r d 、k a d e m l i a 、s k i p n e t ，路由跳数为o ( 1 0 9 n ) 。 4 容错( f a u l t t o l e r a n t ) 与动态自适应( a d a p t a b i l i t y ) 甲， 硕士学位论文 m a s t e r st h e s i s 容错性一直是p 2 p 领域内的一个难题。虽然严格的拓扑结构和分布式散列表映 射提高了系统的效率和可扩展性，却使得系统对其成员不正常行为的容错性下降 了。研究者提出了各种增强容错性的机制，最典型的如冗余方法和周期性检测b 6 1 。 p 2 p 网络是动态变化的，不断地有新结点的加入、旧结点的离开、新对象的发 布、旧对象的删除。当这些发生以后，p 2 p 网络必须有很好的自适应性，做高效的 调整，以保持网络的拓扑结构、位置映射、负载均衡和路由信息的更新。自适应最 重要的是更新结点的状态。常用的自适应方法有周期性检测、按需检测、捎带确认 等。 5 自由性( f r e e d o m ) 与匿名性( a n o n y m i t y ) p 2 p 网络是一个自由、平等的网络，两个对等结点之间有什么样的行为、做什 么样的事情、提供什么样的信息供他人下载、交换哪些信息等，是由通信双方自由 决定的。另一方面，p 2 p 网络是的用户是匿名的，因为分布式散列表采用安全散列 函数将用户信息、数据对象映射到了一个表面上看起来没有任何意义的数值标识 ( i d e n t i f i e r , i d ) ，这个i d 值唯一地代表了用户和数据对象。由于安全散列函数的单 向性与抗冲突性，不容易从此i d 破解出它所代表的信息，匿名性( a n o n y m i t y ) 正是 基于这个原理实现的。 1 4 本文的主要工作及组织结构 本文的主要工作是根据当前p 2 p 网络的研究现状和不同类型p 2 p 系统的特点， 分析各类p 2 p 系统在拓扑结构、结点定位和数据对象定位、路由效率、负载均衡、 容错与动态自适应等方面表现出来的性能，总结不同系统在上述某一方面或某些方 面表现出的优势与劣势，有针对性地对特定的系统提出改善其性能的方法，并根据 仿真实验，说明本文提出的改进方法的效果。 本文的章节安排如下： 第1 章绪论，介绍p 2 p 的研究现状及研究意义、p 2 p 网络中的重要概念、p 2 p 系统的工作原理及核心机制、p 2 p 系统的特点及评价其优劣的标准，为下文的具体 阐述做好理论上的准备。 第2 章无结构p 2 p 网络拓扑优化与资源定位方法研究，本章介绍了无结构的 p 2 p 系统的工作原理，无结构p 2 p 系统在不同应用中表现出来的性能差异，提出了 改进无结构p 2 p 性能的方法，并根据仿真实验说明本文提出的改进方法的优势所在。 6 硕士学位论文 m a s t e r st h e s i s 第3 章结构化p 2 p 网络拓扑构建与资源定位方法概述，本章介绍了一种经典 的结构化p 2 p 系统c h o r d 环形p 2 p 网络。介绍了在c h o r d 环形p 2 p 网络结点的 加入算法，结点的离开及失效后的自适应算法，结点的路由定位算法及该网络的工 作原理。通过该系统分析了结构化p 2 p 系统的特征和性能上的优劣，为下文利用结 构化p 2 p 系统设计新的模型奠定了基础。 第4 章基于分域混合p 2 p 网络资源定位模型的研究，利用结构化p 2 p 系统以 及无结构的p 2 p 系统的优点，设计出一种混合式的p 2 p 网络模型。域内的结点根据 结构化p 2 p 网络组建方式组织起来，每个域提供一个边界结点，域的边界结点之间 用无结构p 2 p 网络的方式组织在一起。本章中分析了这种模型的具体构建方法，并 说明了该模型的效能。 第5 章结论，该部分对本文提出的无结构p 2 p 网络中的一种资源定位方法效 率作了总结，对本文设计的分域混合p 2 p 资源定位模型的性能作了整体介绍，最后 指出下一步要做的工作。 7 硕士学位论文 m a s t e r st h e s i s 第2 章无结构p 2 p 网络拓扑优化与资源定位方法研究 2 1 无结构p 2 p 网络工作原理 著名的无结构p 2 p 网络有：g n u t e l l a 、k a z a a 、e d o n k e y 和f r e e n e t 。其中，g n u t e l l a 是最简单而又最具代表性的无结构p 2 p 系统。本章将从分析g n u t e l l a 体系的工作原 理入手，分析该系统在应用中的优势和不足之处，从而提出对于无结构系统的改进 方法。 在g n u t e l l a 网中消息可以被广播( b r o a d c a s t ) 也可以被回播( b a c k p r o p a g a t e ，沿广 播的反向路径回传消息) ，g n u t e l l a 协议设计了一些规则以支持广播回播机制：首 先，每条消息具有二个随机产生的称之为消息i d 的全局唯一标识符以互相区分； 其次，每个结点缓存最近路由的消息以支持回播和阻止不必要的重复广播；再次， 每条消息都有一个t r l ( t i m e t o l i v e ，生存时间、跳数限制) ，在覆盖网上每走过一 跳丌l 减1 ，1 v r l 减到o 就不再往前传，从而使得g n u t e l l a 洪泛式的广播不会无度 地消耗网络资源【1 7 】。 g n u t e l l a 协议所设计的消息主要有： ( 1 ) p i n g ，p o n g 消息 p i n g ：当一个新结点加入网络时它广播p i n g 消息宣称它的到来；同时p i n g 消息也可用来探测其它对等结点是否仍然存在。 p o n g ：这是对p i n g 消息的回复。当一个结点收到p i n g 消息时，它首先决 定是否回播p o n g 消息，然后将p i n g 消息广播给它的邻居结点( 如果r 兀l 没有减 至o ) 。 ( 2 ) 查询消息：q u e r y ，q u e r yr e s p o n s e q u e r y ：该消息用来查询所要的文件，它包含用户指定的查询内容和附加信 息。每条q u e r y 消息有唯一的标识符，但发出查询消息的源结点是不可知的。 q u e r yr e s p o n s e ：这是对q u e r y 消息的回复，它包含文件下载的必要信 息以及该结点的n o d e l d 。q u e r yr e s p o n s e 消息沿原q u e r y 消息传过来的路径 回播。 g n u t e l l a 查询方式有两大缺陷：一是由于采用洪泛式路由方法，系统开销很大； 二是受”r l 限制，消息只能到达一定范围，不能覆盖整个网络，即使文件存在，也 不一定能被查询到1 9 1 1 2 0 。 8 g n u t e l l a 网络具有很高的动态性，不断地有新结点加入、旧结点离开。为了保 持覆盖网的一致性和p e e r 信息的及时更新，g n u t e l l a 协议使用p i n g 、p o n g 消息 来帮助p e e r 发现和探测其它结点的存在与否。通过p i n g 、p o n g 消息，c m u t d l a 结点不断更新它们的邻居结点信息，这样使得g n u t e l l a 网络较好的自组织和自适应 性。 c m u t e l l a 协议设计了很多消息以完成不同的功能，p i n g 、p o n g 消息的主要用 途是检测其它结点是否在线以维持网络连接和保持自适应，它们是辅助性的。图2l 显示的是在早期的g n u t d l a 网络中各种消息的大致份额。仅仅p i n g 消息所点份额 就超过了5 0 ，这说明早期c m u t e l l a 的自适应机制是低效的；另一方面用户的 q u e r y 消息只点3 6 左右，这说明整个系统效率不高”i h 6 j 。 暑乒委二寻= 三譬g ；盂： m l n u t 0 图2 1 早期g n u t e l l a 阿络中消息分布( p i n g 消息超过5 0 ) 2 2 无结构p 2 p 网络拓扑优化方法研究 基于上面的分析，采用类似g n u t e l l a 协议的无结构p 2 p 网络在设计、优化时必 须考虑f 面几个问题：针对结点异构性，系统应该有机制针对不同结点的能力采取 不同的措施，让它们扮演不同的角色：针对时延问题，系统应该通过更好的设计来 达到用户的满意度；针对系统过大的负荷问题，应该分析系统负荷过重的原因，从 而找到改进的方法：针对查询效率问题，查询机制的优化、n l 的取值、更合理的 搜索算法等，均是无结构p 2 p 网络要研究的主要课题。本节将着重研究无结构p 2 p 系统的优化问题。 硕士学位论文 m a s t e r st h e s i s 2 2 1 无结构p 2 p 网络中的冗余问题 无结构p 2 p 网络中结点可以自由的加入和退出，这种加入和退出在组建网络的 过程中没有作任何限制，必然导致无结构p 2 p 系统是一种松散耦合型的分布式系统。 由于无结构p 2 p 网络逻辑拓扑的松散性和不可预知性，比较原始的洪泛搜索算法就 成了这种网络中采用的主要搜索算法。洪泛搜索会产生大量的冗余搜索数据包，随 着搜索步的加深，冗余信息会呈指数级增长。大量的冗余信息便成了制约无结构p 2 p 网络各项性能的瓶颈。如网络资源的利用率、信息的查全率、系统的响应时间、网 路上各结点硬件资源的利用率等均会受到不同程度的影响1 1 8 】1 1 9 1 。 为了在p 2 p 网络中有效地进行资源定位，国f q ； l - 学者主要从两个方面来研究 p 2 p 搜索问题：一个是通过改变p 2 p 网络结构达到提高搜索效率的目的，另一个 是优化现有的一些搜索方法【2 0 j 。本文先分析在非结构化p 2 p 网络中冗余数据包产生 的原因进而提出相关优化算法来减少冗余和局部消除冗余搜索数据包( 该方法称之 为精简转发表法) ，然后对本文提出的精简转发表法进行模拟仿真，再通过实验数 据来说明优化的效果。 2 2 2 无结构p 2 p 网络中产生冗余原因分析 本小节分析在非结构化p 2 p 网络中冗余搜索数据包产生的原因，为提出精简转 发表这一优化方法做准备，该方法以减少冗余和局部消除冗余为目的。 图2 23 个结点的环图2 34 个结点的环 图2 4n 0 岭4 ) 个结点的环 图2 5 抽象出的树形结构图2 6 单支环路产生的冗余 搜索过程中之所以会产生冗余数掘包，是因为网络中存在着环路。如图2 2 、 图2 3 、图2 4 所示。图中箭头的起点表示发起搜索或转发搜索的结点，箭头的终点 1 0 弋 硕士学位论文 m a s t e r st h e s i s 表示当前数据要发送到的结点。当发起搜索后，图中实线箭头的终点表示的结点将 收到非冗余的搜索信息，图中虚线箭头的终点表示的结点将收到冗余的搜索信息。 图2 5 表示的是一个树形图，由于树中不存在环路，因此从a 发出的搜索数据 包直接传送至b 、c 、d 结点，不会产生冗余。在图2 6 中，结点c 与结点d 之问 有连接，这样构成了一个环路，在结点c 与d 之间相互转发的搜索包就成了冗余 的数据包。 在图2 7 中，结点c 与d 、结点b 与d 之间均有连接，则在c 与d 、b 与d 之间均会产生冗余数据包。图2 8 为一个全连通图，源结点a 发送搜索包给结点b 、 c 、d ，结点c 与d 、结点b 与d 、结点b 与c 之间转发的搜索包均为冗余数据包。 图2 7 结点度数较大产生的冗余图2 8 在全连通图中会产生很多冗余 由此可以看出，在相同结点个数的情况下，结点的平均度数是影响冗余数据包 产生多少的惟一因素。在最好的情况下，结点之间构成一个连通的树状图，这时搜 索过程中不会产生冗余数据包；最坏的情况是结点之间构成一个全连通图，这样的 网络中存在很多环路，如果不作处理就会产生很多冗余数据包。 接下来分析在动态的p 2 p 网络中即结点个数不确定的情况下冗余数据包产生的 原因。为了使问题简化，在这里用一个较小规模的连通图来代表某一时刻下的p 2 p 收敛网络。 图2 9 是抽象出的一个在某一时刻的收敛的p 2 p 网络的拓扑图。其中的某个结 点向它的邻居结点发起搜索请求，这里设结点i 为发起搜索的结点。图2 1 0 是从结 点i 的角度出发所观察到的整个网络( 注意在非结构化p 2 p 网络中，单一结点只与其 邻居结点和索引其信息的索引结点有联系，没有能力认识整个网络的拓扑结构) 。 图2 1 0 是结点i 视野中的塔状拓扑图。因为结点i 发起搜索请求，所以i 就是 塔状图中的顶点。第二层是结点i 的邻居结点，第三层是结点i 邻居的邻居结点， 依此类推。注意由于结点的加入和退出，该塔状拓扑图是动态变化的。 硕士学位论文 m a s t e r ? st h e s i s 图2 9 抽象出的某时刻p 2 p 收敛网络的拓扑图 图2 1 0 在结点i 视野中的金字塔状拓扑图 对g n u t e l l a 系统进行的一项测试显示：在g n u t e u a 网络中使用泛洪算法搜索 文件时，9 5 的结点都可以在7h o p s 内被搜索到。个别结点的离开或加入不能对 网络造成很大的破坏性1 2 1 1 1 2 2 1 。绝大多数结点都在7 层以内，下层结点的数量一般要 比上层结点的数量多。在上层，向下层转发搜索请求消息的结点数目相对较少，一 个结点只从一个邻居或少数邻居结点处接收到查询请求消息的情况相对较多。这样 一个结点向下层发出的查询请求消息产生的覆盖面积相对较广，冗余的查询请求消 息就相对较少。在下层，随着越来越多的结点收到查询请求消息，一个结点越来越 有可能从同层和上层的多个邻居结点处收到相同的查询请求消息，相对于查询请求 消息的数量，查询请求消息的覆盖面积变小，冗余消息的数量大幅度的增加。 1 2 硕士学位论文 m a s t e r st h e s i s 2 2 3 无结构p 2 p 网络中减少冗余的方法 从上节冗余数据包产生原因的分析中可知减少或消除p 2 p 网络中冗余数据包的 理想方法就是减少p 2 p 网络中的环路，直到完全消除网络中的环路为止。由此可以 设想如果能够建立一棵以发起搜索的结点为根的生成树，那么就可以完全消除网络 中的环路，从而完全消除网络中的冗余数据包。 由于p 2 p 网络的动态性，结点加入和离开的不确定性，各个结点的处理能力以 及所拥有的网络资源的差异性，还有搜索算法的收敛时间问题等，所有这些因素决 定了在p 2 p 网络的当前活动结点之上构造一棵以发起搜索的结点为根的搜索树是不 可能的。但是可以利用结点之间逻辑上的树形结构具有减少或局部消除冗余数据包 这一性质，局部优化常规的洪泛搜索算法，来达到减少和局部消除冗余搜索数据包 这一目的。 在以发起搜索的结点为顶点的塔状拓扑图中，容易知道在上层产生的冗余数据 包较少，但随着塔层数的增加，产生的冗余数据包将呈指数级地增加。如果搜索能 够在上层完成，或者当搜索到某一层后，搜索消息不再以指数形式增加，而是以几 何形式增加，那么就可以大大减少冗余数据包的产生。本文提出的减少冗余方法就 是在洪泛搜索和层次结构的基础上进行的优化。 2 3 无结构p 2 p 网络中的一种高效资源定位算法的实现 为了减少搜索过程中动态产生的冗余数据包，一个简单的方法就是让每个结点 维持r 跳以内邻居结点的信息，建立r 跳距离内的生成树。这样可以保证r 跳以 内的每个结点收到并且只收到一次查询请求消息，不会产生冗余数据包。但是由于 p 2 p 网络中的用户可以随时加入或离开，要想使每个结点维护r 值较大范围内的 结点信息是十分困难的，也是不现实的。很显然，r 值越大越能减少冗余数据包的 产生。当r 值扩展到整个网络范围时，这时就要对网络中所有的结点信息进行维护。 但是维护范围越大，结点之间需要交流及交换的信息就越多，大大增加了结点维护 的开销，过多地消耗了网络资源。同时由于p 2 p 网络的动态特性，结点频繁的加入 或退出，这样每个结点获得的当前网络的局部拓扑结构信息也是不可靠的。可见每 个结点维护r 值较大的局部拓扑信息带来的弊端不利于解决实际问题。 2 3 1 拓扑结构动态变化的处理 通过权衡结点拥有拓扑信息的便利和为获得该信息所付出的维护代价，可以使 硕士学位论文 m a s t e r st h e s i s 每个结点维护r 值相对较小范围内的结点信息。如果r 值较小，则每个结点所需维 护的网络局部拓扑信息较少，能够及时反映网络拓扑的动态变化，减少了由于拓扑 更新不及时造成的网络资源消耗。同时结点维护信息所需的开销也不大。在本文提 出的算法中，让每个结点维护r - 2 跳内的拓扑结构信息，即让每个结点记录它自 己的邻居结点标识，同时该结点还记录自己邻居的邻居结点。本文通过邻居之间相 互发送p i n g 消息的方式来建立每个结点2 跳内的拓扑结构信息。p i n g 消息的格 式如表2 1 所示。它包括发送p i n g 消息的结点的标识以及该结点的邻居结点标识。 表2 1p i n g 消息的格式 结点i 的标识 i 的邻居l 的标识 i 的邻居2 的标识 i 的邻居3 的标识 接下来在每个结点上运行一个简单的构造算法就可以构造出每个结点2 跳内的 拓扑结构信息。本文中用集合n ( i ) 标记结点i 的邻居结点，用集合n ( n ( i ) ) 标记结点 i 邻居的邻居结点，即距结点i 两跳远( 2h o p s ) 的结点集合。算法描述如下： 当结点i 收到某个邻居结点j 发送过来的p i n g 消息时，它作如下更新处理： s t e p l 将结点j 的标识加入代表其邻居结点的集合n ( i ) 中； s t e p 2 将结点j 的邻居结点的标识放入n ( n ( i ) ) ； s t e p 3 在n ( n ( i ) ) 中除去n ( i ) 中包含的元素，即n ( n ( i ) ) = n ( n ( i ) ) - ( n ( n ( i ) ) nn ( i ) ) 。 上述构造算法收敛之后，每个结点2 跳内的拓扑结构构造完毕。由于p 2 p 网络 中经常有结点加入或离开，为了反映拓扑的动态变化，每个网络结点定期发送p i n g 消息给它的邻居。若经过设定的超时值没收到某个邻居的消息，便认为该邻居已经 离开网络。实现时将为每个结点的邻居结点设置一个等待其p i n g 消息到来的超时 计时器。若计时器未超时，采用上述更新算法作更新处理，处理完毕后重置计时器。 若结点i 在定时的时间内未收到某个邻居结点j 发送过来的p i n g 消息，则计时器 超时，说明邻居结点j 离开网络。为了及时反应拓扑结构的变化，处理方法如下： s t e p l 将结点j 的标识从结点i 的邻居结点集合n ( i ) 中删除； s t e p 2 将结点j 的邻居结点集合n ( j ) 中的元素从结点i 邻居的邻居结点集合n ( n ( i ) ) 中删除，即n ( n ( i ) ) = - n ( n ( i ) ) 一( n ( n ( i ) ) nn ( j ) ) 。 如果当前p 2 p 网络中的某个结点在线，那么上述两个算法始终运行在该结点上。 这里是以花费结点较少的处理器资源为代价来获得更新的网络拓扑。 1 4 硕士学位论文 m a s t e r st h e s i s 2 3 2 精减转发表算法( c f l 算法) 的实现 利用2 跳内的拓扑信息，可以消除2 跳内的绝大多数冗余。发起搜索的源结点 首先构建自己的转发表，再把查询消息发送至它的转发表中的结点。转发结点收到 查询请求消息后处理查询请求同时构建自己的转发表。需要构建转发表的结点在构 建转发表的过程中充分利用它所知道的两跳内的拓扑信息，根据预先设计的规则选 择合适的转发结点，在两跳距离内尽量消除冗余信息。这种机制可以制约冗余消息 呈指数级地增长，并将冗余消息限定在合理的范围之内。接下来以图2 1 1 为例，分 析2 跳以内的各种冗余形成的过程，提出消除2 跳以内冗余的算法。 n ( v i ) n ( v j )n ( n ( v 0 ) 图2 1 1 距离v i 结点2 跳以内的网络拓扑图 图2 1 l 是为了说明问题的方便在本文中虚拟的距离结点2 跳以内的网络拓 扑图。在图2 1 1 中集合n m ) ，n o ：j ) ，n ( n ( v i ) ) 中的结点被圈在各自的椭圆圈内。 假设结点是发起查询请求消息的原始结点。如果结点v i 收到了结点的查询 请求消息，并且v i 是v i 的转发表里的结点，那么v ：j 需要处理结点v i 的查询请求 同时结点v i 运行相应的构造算法构造自己的转发表。 与洪泛算法不同，在本文提出的精简转发表算法中，v j 只向集合n 刚) ( n ( v j ) n n ( ) ) 中的结点转发消息，而不是向集合n ( v ：j ) 中的所有结点转发消息，因 此可以避免图2 2 中由三个结点形成的环产生的冗余。图2 1 l 中，发起搜索将向 v j 和v k 发送消息，由于v k n ( v i ) ，v j 不会向v k 转发消息，因此在由v i 、v j 和 硕士学位论文 m a s t e r st h e s i s v k 三个结点构成的环中不会产生冗余。 在图2 1 1 中，假设v i 的转发表中的结点有v j 和v m ，那么和v m 都要向 各自的邻居结点转发从收到的消息。由于v l t e n ( v j ) 且v l e n ( v m ) ，因此v j 和 v m 均可向v l 转发消息，这将可能会生图2 3 中