（计算机应用技术专业论文）拓扑参数优化的结构化p2p网络研究.pdf

摘要 摘要 近年来，结构化p 2 p 系统以其低跳数的资源定位、路由确定性及平衡负载特性，成为学术界的研究热 点结构化系统都可以看作是由各种静态拓扑扩展而来，因此其基础结构始终面临着拓扑维护及拓扑参数 优化的问题，并最终决定系统运作性能。而静态拓扑在p 2 p 动态环境下的平滑嵌入要面临拓扑维护开销控 制、拓扑虚拟化及优化网络直径等多个难题本文以此为研究对象，定义和完善拓扑参数体系，从拓扑角 度设计新的维护简单、性能优越的结构化p 2 p 系统，并取得了一定的研究进展，主要贡献包括： ( 1 ) 提出了适用于动态p 2 p 环境的概率平衡树的拓扑形式，不遵循层次的完全平衡只遵循层次的概 率均等，使树出现不平衡状态的可能性很小节点位置转变为局部信息，使得新节点加入排除了对全局平 衡信息的需求，在分布式环境下具有很好的可扩展性 ( 2 ) 提出了基于匹配路径和概率平衡树的结构化p 2 p 系统m p p b t r e e 。以概率平衡t r i e 树作为拓扑组织 形式以很高的概率实现常数度数0 ( d ) 下的网络直径下界0 0 0 9 n ) ：通过随机接入方法实现节点加入，避 免了平衡树的高额维护成本：用过载转移方法提供细粒度的负载转移支持。与同类其它p 2 p 系统相比， m p p b t r e e 以相对较低的维护成本和较强的数据负载平衡机制，达到了较高的路由效率和查询灵活性 ( 3 ) 提出了新的常数度数静态拓扑结构h l a l ：h 图，h i n i ：h 图结合d e b r u i j n 图d ( 2 埘和2 维h y p e r e u b e 连接是一个拓扑参数优化、性能优越的静态拓扑结构，在最长路径路由下，具有常数度数、对数直径、 常量拥塞和容错绕路的性质。 ( 4 ) 提出了基于h l 2 d 2 图的常数度数且常量拥塞的d h tp 2 p 系统v i - i l 2 d 2 v h i q d 2 结合d eb r u i j n 链 接和h y p e r 链接进行查询路由，使用h y p e r 链接进行容错路由采用2 步长的倾向性随机游走实现动态维 护时的待分裂域选择保证了全局流量及域面积均衡化v 1 l 2 d 2 也实现了0 ( 由度数下的优化网络直径 o ( i o g t 0 ，与其它常数度数p 2 p 系统相比。v h t a t h 拥有更小的网络直径、更快的新节点定位过程及较强的 容错路由能力 ( 5 ) 提出了p 2 p 拓扑参数抽样统计方法和评价策略。首先提出一种基于信息熵的p 2 p 拓扑参数抽样统 计随机测度方法，定义链接熵以表征节点链接的总体分布，然后针对常数度数网络。以链接熵为抽样测度 基准，提出四种可操作性较强的抽样方案，以v h t a t h 拓扑为实例对象，考察了不同抽样策略对拓扑参数 的抽样性能并作了简要分析 关键词：p 2 p 系统拓扑常数度数抽样统计 a b s t r a c t i nt h ep a s ts e v e r a ly e a r ss t r u c t u r e dp 2 ps y s t e mh a sb e e nr e s e a r c hh o t s p o tf o rh a v i n gf e a t u r e ss u c ha sl o w h o p sl o c a t i n g d e t e r m i n i s t i cr o u t i n ge n di o a db a l a n c e s t r u c t u r e dp 2 ps y s t e m sa f ee x p a n d e df r o mv a r i o u ss t a t i c t o p o l o g i e s ，s ot h e ya l w a y sf a c eu p t ot h e c h a l l e n g e so nt o p o l o g ym a i n t e n a n c ea n dt o p o l o g yp a r a m e t e r o p t i m i z a t i o n t h a td e c i d e su l t i m a t eo p e r a t i o np e r f o r m a n c e b u te m b e d d i n gs t a t i ct o p o l o g i e si n t op 2 pd y n a m i c e n v i r o n m e n tm u s ts o l v es e v e r a lp r o b l e m si n c l u d i n gm a i n t e n a n c ec o s tc o n t r o l ，t o p o l o g ys i m u l a t i o na n dn e t w o r k d i a m e t e ro p t i m i z a t i o n t a k i n gt h e s ea sr e s e a r c ho b j e c lt i l ed i s s e r t a t i o nd e f m e sa n di n t e g r a t e st o p o l o g yp a r a m e t e r f r a m e w o r k , d e s i g n sn e wl o w - c o s t , g o o dp e r f o r m a n c ep 2 ps y s t e m sf r o mt o p o l o g yv i e w t h em a i nc o n t r i b u t i o no f t h ed i s s e r t a t i o ni sa sf o l l o w s ( 1 ) an e wt o p o l o g yc a l l e dp r o b a b i l i t yb a l a n c et r e ei sp r o p o s e df o rd y n a m i cp 2 pe n v i r o r m a e n li td o e s n tk e 印 t oa b s o l u t eb a l a n c e o f l a y e r sb u t p r o b a b i l i t ye q u a l i z a t i o n , a n d t h a tr e s u l t i n t i n yp r o b a b i l i t yo f u n b a l a n c e b e c a u s e n o d el o c a t i o ni n f o r m a t i o nb e c o m e sl o c a lk n o w l e d g e ，g l o b a lb a l a n c ei n f o r m a t i o ni su s e l e s sf o rn o d ej o i n i n g s o u n d e rd i s t r i b u t e de n v i r o n m e n tg o o ds c a l a b i l i t yi so b t a i n e d ( 2 ) ai l e ws t r u c t u r e dp 2 pm o d e lw i t hm a t c hp a t ha n dp r o h a b i l i t yb a l a n c et r e e i sp r o p o s e d b a s e do b p r o b a b i l i t yb a l a n c et r i e ，w i t hh i g hp r o b a b i l i t yi to b t a i n s0 ( 1 0 9 ) d i a m e t e rt h r e s h o l du n d e rd ( 力c o n s t a n td e g r e e h i 曲m a i n t e n a n c ec o s to nb a l a n c ei sa v o i d e db yr a n d o mn o d ea e w e s s i n ga n dd a t ao v e r l o a dt r a n s i ti sg o t t e nf m e g r a n u l a r i t ys u p p o r t c o m p a r e dt oc o n g e n e rp 2 pm o d e l s m p p b t r c eo b t a i n sb e t t e rr o u t i n ge f f i c i e n c ya n dq u e r y f l e x i b i l i t yb yl o w e rm a i n t e n a n c ec o s ta n ds t r o n g e rl o a db a l a n c e ( 3 ) a 咖c o n s t a n t - d e g r e es t a t i ct o p o l o g yc a l l e dh i 4 d 2g r a p hi sp r o p o s e d h k d zg r a p hc o m b i n e sd eb r u i j n g r a p hd ( 2 ，d ) a n d2 - d i m e n s i o nh y p e r c u b el i n k , i sa no p t i m a l - t o p o l o g ya n dh i g h p e r f o r m a n c es t a t i ct o p o l o g y m o d e l u s m gl o n g e s tr o u t i n gp a t h , i th a sp r o p e r t i e si n c l u d i n gc o n s t a n t - d e g r e e ，l o g a r i t h md i a m e t e r , l o wc o n g e s t i o n a n df a u l tt o l e r a n tr o u t i n g ( 4 ) ad h tp 2 pm o d e lv h i a i ) 1b a s e do nh l a l ) 2g r a p hi sb u i l d v h i q d 2e x t e n d sh i z d 2g r a p ht od y n a m i c p 2 pe n v i r o n m e n t , t a k e sq u e r yr o u t i n gb yd eb r u i j nl i n ka n dh y p e r l i n k , t a k e sf a u l tt o l e r a n c er o u t i n gb yh y p e r l i n k , t a k e s2 - s t e pb i a s e dr a n d o mw a l k sw h e ns e l e c t i n gs p l i t t i n gz o n ei nn o d ej o i n i n g , s og l o b a lt r a f ! f i ca n dz o n e - a r e a e q u i l i b r i u mma s s u r e d v h i 以d 2o b t a i n so ( 1 0 9 n ) d i a m e t e ru n d e rd d e g r e e ，c o m p a r e dt oo t h e rp 2 pm o d e l s ，i t h a ss m a l l e rd i a m e t e r ，q u i c k e rn o d el o c a t i o np r o c e s sa n df a u l tt o l e r a n c er o u t i n gc a p a b i l i t y ( 5 ) s a m p l i n gs t a t i s t i cm e t h o do fp 2 pt o p o l o g yp a r a m e t e ra n di t s e v a l u a t i o ns t r a t e g ya 他p r o p o s e d a n e n t r o p y b a s e ds a m p l i n gr a n d o m i z a t i o nm e a s b r em e t h o di si n 仃o d u c e da n dl i n ke n t r o p yi s d e f i n e dt od e s c r i b e l i n k s c o l l e c t i v i t yd i s t r i b u t i o n t h e nt a k i n gl i n ke n t r o p y a ss a m p l i n gr a n d o m i z a t i o nm e a s u r es t a n d a r d ，u n d e r v i - i i n d 2t o p o l o g ye x p e r i m e n ti n s t a n c e ，f o u rr e a s o n a b l es a m p l i n gs c h e m e sa r ei n t r o d u c e da n dt h e i rs a m p l i n g p e r f o r m a n c e sa l er e v i e w e d k e y w o r d s ：p 2 ps y s t e m t o p o l o g yc o t a u t - d e g r e es a m p l i n gs t a t i s t i c - 圈目录 图1 1 图1 2 图2 1 图2 2 图2 3 图2 4 图2 ，5 图2 6 图2 7 图2 8 图2 9 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 1 l 图3 1 2 图3 1 3 图3 1 4 图3 1 5 图4 1 图4 ，2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1 1 图4 1 2 图4 1 3 图4 a 1 图5 1 图5 2 图目录 p 2 p 网络的层次结构2 各种d h t 方法下度数和网络直径问的渐进曲线关系6 p s t r y 节点的路由状态表一1 5 t a p e s t r y 的路由过程一1 6 一个简单的p - g r i d 网络1 6 一个k = 2 的u l y s s e sb u t y e r f l y 。1 7 v i c e r o y 网络节点的b u t e e r f l y 连接关系1 8 d 2 b 的连接关系1 9 c a n 寻路机制1 9 c y c l o i d 节点路由表2 0 f i s s i o n e 的邻居图示例2 l 通过相关性推算转发路由m 2 5 系统的总体结构。2 6 单q k 精确查询算法伪码2 8 单q k 模糊查询算法伪码2 8 井行r a n g eq u e r i e s 2 9 初始n k 为1 0 1l 的节点成为1 0 1 2 ，。3 0 节点加入一3 i 节点离开时的替代行为3 2 新节点优先补充层高的空位n k 3 2 k e y 值的不同分布曲线3 3 精确匹配查询3 5 节点动态维护3 6 平均路由表大小3 6 平均路由表更新开销。3 6 r a n g eq u e r i e s 开销：3 7 h l 2 d 2 圜( n = 2 ) 4 1 h l 2 d 2 图单点( 边) 容错4 5 i l l 2 d 2 图多点( 边) 容错4 5 v h l a d 2 图( n = 7 ) 。4 6 v h l 2 d 2 路由算法4 7 v h i ，2 d 2 节点加入算法4 8 v h l 2 d 2 节点退出算法4 9 节点度的分布。5 l 平均节点度5 1 节点i d 值长度的分布5 2 平均路由长度。5 2 j o i n d e p a r t 消息的平均传递长度，5 2 容错路由成功率v s 失效节点数5 3 d e b r u l ) n 图d ( 2 ，3 x d e g r e e 2 2 ，1 5 1 a m e t e r23 ) 5 5 抽样节点的d e b r u l r n 出边链接熵6 l 抽样节点的h y p e r l i n k 链接墒6 】 v 1 表目录 表目录 表1 1g n u t e l l a 节点在不同消息t 1 l 、不同消息产生速率下的平均负载3 表1 2 不同拓扑、不同资源副本分布下3 种路由方法的性能比较( 1 1 1 f 5 ，k = 3 2 ) 4 表2 1c h o r d 指针表】4 表2 2 各种p 2 p 系统在节点度和网络直径上的性能量级2 1 表3 1 节点2 2 的路由表结构。2 7 表4 1 节点1 0 的路由表- 4 6 表5 1 一个v h l 2 d 2 系统实例中( 5 0 0 0 节点规模) 拓扑参数码位的概率分布一5 8 表5 2 节点标识的各比特位熵6 0 v - 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括 刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：导品签名：城期：导师签名：必期： 第一章绪论 第一章绪论 近十年来，通信技术和计算机技术都取得了惊人的进步从而使计算机系统经历着一场革命i l 肛 。光 纤通信技术的成功研究使网络传输速率达到了吉比级的高度和超低误码率( 盈5 x 1 0 1 ；无线通信技术则从 模拟发展到数字，从窄带发展到宽带，从区域发展到移动再到全球无缝覆盖：交换技术从电路交换发展到 快速分组交换和多协议标记交换( m p l s ) ：同时计算机技术则在计算处理速率、并行处理结构以及面向对象 的软件技术和分布对象计算技术方面获得突破性发展，计算机c p u 处理速度按照摩尔定律不断提升，高 性能计算机体系结构和并行计算结构，使得计算机处理速度已经超越单个c p u 处理速度的限制i l n h ；分布 对象技术使得异构软件系统在网络环境下可以屏蔽自身差异而容易地实现互操作和系统集成。 这两项基础技术的发展推动了网络应用的发展，使得由大量孤立c p u 组成的计算机系统通过高速网 络互连成为现实，其特征开始向开放、集成、高性能和智能化方向转变，时间和地理上的障碍变得越来越 微不足道，电子数据交换成为一种趋势。当前网络应用已经从传输单一的文本数据，发展到传输语音数据 和视频数据，以及集成多种类型数据传输的多媒体网络应用：从传统的点到点交互，发展到单点到多点交 互和多点到多点之间的交互；从传统的集中控制结构发展到分布控制结构再发展到联邦( 多自治域) 的控制 结构；从传统的尽力而为的j 没有任何服务质量保证的传输服务模式，发展到高效，安全简捷、具有服务 质量保证( q o s ) 的高性能网络服务”j ， 然而，随着网络规模的迅速扩展、复杂应用的层出不穷及网络节点间异构现象的普遍传统的c s 应 用结构模式不能满足实际需求。导致大量闲散瓷源的产生。因此研究新的能有效集成产业链上的各种硬软 件资源，动态适应能力强，运营效率高的整合技术已经成为整个产业发展的出路。 1 1p 2 p 网络概述 p 2 p ( p e e r - t o - p e e r ) 是一种和网格服务齐名的新的应用模式。和网格不同的是：网格是一种服务中心的工 作模式，而p 2 p 更强调分布式在这种新的应用模式中，所有的节点具有对等的功能，不存在固定或者永 久的服务器每个节点都可能是某种资源的提供者，同时又可能是其它资源的使用者。由于不存在专门的 服务器现有的基于服务器的搜索引擎技术受到限制，也即p 2 p 网络必须有适应自身特点的资源搜索发现 技术。与传统分布式系统相比，p 2 p 技术具有无可比拟的优势和广阔的应用前景。 在学术界和工业界，p 2 p 技术都已成为研究热点。许多国外大公司如s u n 、i n t e l 、h p 、s o n y 及国内 的华为、联想等都启动了p 2 p 开发计划，从事新型p 2 p 计算底层构架研究；而近两年的s i g c o m m 、 i n f o c o m 等顶级会议及i p t p s 、p 2 p 等专业国际会议也在开设或增加p 2 p 方面的论坛；许多相关的应用 研究项目( 如i r i s t ”、o c e a n s t o r e i “、c f s | s ) 也都在进行或不断深化中 1 1 1 应用的需求 导致业界关注p 2 p 应用的原因在于：制造工艺的提升、硬件成本的降低、用户端的硬件资源大幅度的 提高：因特网的普及、进入网络的用户增多、用户应用计算机的成果积累、用户端的软件和数据资源剧增 等等，如何充分发挥( 或者提高) 这些用户端资源的作用( 或者利用率) 构成了探讨p 2 p 的主要动力。从网络 的角度看，p 2 p 网络是一种基于现有网络( 如因特网) 的覆盖网，网络的每一个节点可以充当服务的提供者 和使用者，可以向网络提供自己的资源或者通过网络使用其它节点提供的资源。用户越多，网络积聚的 资源越多，网络体现的能力越强。换句话说，p 2 p 可被理解为是一种支持网络中闲散资源的管理和共享的 新模式，其目的是通过某种适当的方法将这些大量和闲散的计算、存储、软件和数据资源组织起来，并发 挥其作用，最终使得整个网络成为一台具有超大处理能力、存储能力、丰富应用和数据资源的超级计算机， 使得所有的用户在为网络提供自己的闲置资源的同时，也可从网络中获取取之不尽的服务。 就我国的网络资源利用情况看，应当是不乐观的在国家金字系列工程的促进下。各部门、行业和企 东南大学博士学位论文 业都配置了计算机设施但投资形成的处理、存储和数据资源的利用率均较低。另一方面，为了支持各种 科研和计算任务，仍有不少单位仍在申请新的投资使用p 2 p 技术来减少用户的投资，来适应用户的需求 正是应时之举。 1 1 2p 2 p 网络的特点 非中心化( d e c e n t r a l i z a t i o n ) ：网络中的资源和服务分散在所有节点上，信息的传输和服务的实现都 直接在节点之间进行，可以无需中间环节和服务器的介入。避免了性能瓶颈和单点故障问题，更 好的实现了网络负载均衡。 可扩展性( s c a l a b i t i t y ) ：随着网络规模的扩张不仅服务的需求增加了，系统整体的资源和服务提 供能力也在同步地扩充，其服务性能没有显著下降。理论上其可扩展性几乎可以认为是无限的。 自治性( a u t o n o m y ) ：每个节点具有对所拥有资源及自身行为的完全控制权，它可以选择开放资源 的程度，其加入和离开也是即时而自由的 自组织性( s e l f - o r g a n i z a t i o n ) ：一方面p 2 p 构架具有抗毁性、高容错的优点由于服务是分散于各 个节点的，部分节点或网络遭到破坏对其它部分的影响很小。p 2 p 网络一般在部分节点失效时能 够自动调整整体拓扑，保持其它节点的连通性。另一方面p 2 p 网络甚至还能够根据网络带宽、节 点数、网络负载等变化不断地做自适应式的调整。 覆盖网- 络( o v c r ) a y ) ：p 2 p 网络屏蔽底层通信细节，是构建在现有i n t e m e t 传输网络上的应用层虚拟 网络，其连接关系具有对实际拓扑的非对应性( m i s sm a t c h ) 。 1 1 3 p 2 p 网络的层次结构【6 j 图1 1 显示了p 2 p 网络的纵向层次结构目前p 2 p 的研究主要针对除通信层以外的四层。组管理层包 括资源发现和路由定位等方面的内容，优化消息从一个p e e r 到达另一个p e e r 的路径，本文的研究正是立 足于这个层面上：鲁棒层和分类层涵盖了安全、可靠传输、x m l 语义表达、网络管理等课题，应用层则 考虑工程应用的具体方式，包括特定服务的提供、开发平台的提供等 应用层 分类层 鲁棒层 组管理层 通信层 团圆圈 圈圜圈圈 圈圜圈 圈圈 口 图1 1p 2 p 网络的层次结构 m a g j ”l 、j x t a | 8 l 和n e t m y s e r v i c e s ( 9 t 等包含了四层所有的服务，面向应用提供统一的开发平台。m a 面 是一个能够用于建立安全、跨系统协同应用的p 2 p 基础平台遵循基于w e b 的系列协议标准( 如h 1 1 甲、 w e b d a v 等) ，在网上发布订阅系统应用上有新的价值。j x t a 作为传统c s 结构的替代者，提供了一个 开放的p 2 p 协作平台以支持广泛的分布式计算应用，它在各个层上都实现了核心功能井且提供开发接口 包括从基础构架到高层服务，具有很强的通用性。n e tm ys e r v i c e s 不是专门的p 2 p 平台，但整合了很多 p 2 p 结构和功能，还可以利用下层的很多n e t 服务。 i i 4 实际的应用 p 2 p 网络技术已被广泛应用于各个领域并还在不断扩展中，现有的典型应用包括：( 1 ) 提供文件和其 2 第一章绪论 它内容共享例如n a p s t e r i 、g n u t e l l a i “l 、o h a h a t l ”、k a z a a l ”i 、b i t t o r r e n t t l 4 l 等；( 2 ) 普及p 2 p 对等计算， 即利用网络中的计算单元来共同完成大规模的计算任务，例如s e t l h o m e i ”i 、e n t r o p i a | 1 “、g r i d l l 7 h 1 9 1 等；( 3 ) 广域网存储共享，例如p a s t 凹】、o c e a n s t o r e 、c f s 等；( 4 ) 基于p 2 p 方式的协同处理与服务共享 平台，例如j x t a 、m a g i ，g r o o v e i “j 、n e tm ys e r v i c e 等；( 5 ) 即时通讯交流，例如i c q 、o i c q 、m s n m e s s e n g e r 、j a b b e r 2 2 1 等：( 6 ) p 2 p 视频、语音应用，例如s k y p e l 2 ”、p p l i v e 、p o c o 、p p s t r e a m 等；( 7 ) 信息检 索，例如j x t as e a r c h ”1 、p e e r s e a t c h t 2 ”、p i e r ”i 等。( 8 ) 网络游戏，例如c e n t e r s p a n l 2 7 瞎：( 9 ) 研究和教 育领域的应用，例如e d u c o m m o n s i ”i 、w o r l d w i d e l e x i c o n 2 9 i 项目等；另外还有域名服务d n s 、组播通信、 w e b 缓存共享、分布式搜索引擎等领域。 1 2p 2 p 网络的体系结构 根据组织结构的不同，p 2 p 网络大致可以分为四种结构：集中式( c e n t r a l i z e d ) 、分散式非结构化 ( d e c e n t r a l i z e da n du n s t r u c t u r e d ) 、分散式结构化( d e c e n t r a l i z e db u ts 仇l c t u r e d ) 及混合式( h y b r i d ) 1 2 1 集中式( c e n t r a l i z e d ) 集中式p 2 p 结构不是一种纯粹的p 2 p 网络，它依靠集中目录服务器存储系统所有资源的索引，该服务 器只提供资源注册、资源检索和资源注销功能节点寻路时，通过向服务器提交查询来获得存储实际资源 的主机的i p 地址或u r l 而实际灼资源传输发生在端到端之间，以p 2 p 的方式进行。集中式p 2 p 结构以 n a p s t e r 为代表。首先实现了资源传输和资源检索的分离有效节省了中央服务器的带宽消耗。系统维护简 单且发现效率高，能够实现各种复杂查询( 如模糊查询、多关键字查询等) 。其缺点在于与传统c s 结构类 似，容易造成单点故障、访问热点( h o t s p o t ) 等现象，因此可扩展性较差。 1 2 2 分散式非结构化( d e c e n t r a l i z e da n du n s t r u c t u r e d l 以g n u t e l l a 、f r e e n e t i 圳为代表的分散式非结构化系统采用了随机图的组织方式，节点度数服从 p o w e r - l a w ( 幂律分布) 规律面对网络的动态变化体现了较好的容错能力，同时可以支持复杂查询，具有很 好的实用性g n l l t e i j a 是纯粹的p 2 p 系统，没有索引服务器，它采用基于完全随机图的泛洪( f l o o d i n g ) 发现和 随机游走( r a n d o mw a l k e r ) 机制来建立邻居关系和实现查询请求，并i 盈过t t l ( t i m et ol i v e ) 的减值来控制 查询请求的遍历深度。 表1 1g n u t e l l a 节点在不同消息1 1 乙，不同消息产生速率下的平均负载( 单位k b s ) t t l - - - 2丁n f 3下兀。= 4 r a t e s e a r c hp e e rd i s c s e a r c hp e e rd i s c s e a r c hp e e rd i s e 1 h o u r 0 0 4 o 0 80 6 1 1 1 0 2 1 03 2 0 l m i n u t e2 5 04 8 03 6 8 06 8 2 01 2 7 0 01 9 4 9 0 l s e e o n d1 5 1 0 02 8 8 0 02 2 1 】0 04 0 9 0 4 07 6 1 7 _ 3 0 1 1 6 9 4 5 0 然而随着网络规模的扩大节点数的增多，用于资源定位的泛洪消息量成非线性增长导致低带宽链 路拥塞的频繁发生，同时由于没有确定拓扑结构的支持，搜索深度受限情况下系统不能保证可用资源被发 现的确定性表1 1 p ”显示了含有1 0 0 0 0 节点规模且节点度为指数分布的网络中的节点负载，对t 1 l = 4 。 查找和节点发现消息l m i n u t e 的频度两种消息各自要消耗1 2 7 k b ，s 和1 9 4 9 k b s 的带宽。f r e e n e t 采用广 度优先搜索，增加了基于标识的路由改进方案，对泛洪方向具有一定的指导性，虽然提高了资源发现的效 率依旧不能根本解决路由确定性问题。 。 可扩展性和资源发现确定性是非结构化系统的两个关键问题，目前对此类结构的研究也成为热点，并 且已经提出了很多改进机制主要集中于改进发现算法和复制策略以提高资源发现的准确率和效率： t t l - f l o o d i l l g d 2 1 ：查询消息携带t 1 乙值，1 r l 通常设为7 ，消息每前进一步r r l 值减l ，r r l 为0 时 3 一 东南大学博士学位论文 停止。由此遍历深度和广度得到控制，泛洪消息局限于区域： e x p a n d i n gr i n g 3 2 l ：r r l 值与查询结果直接关联- 具有自适应性。节点首先一个触发小t t l 值的 泛洪消息，若搜索结果不满意则增加t t l 值以继续泛洪搜索，直至达到目标节点对于搜索流行 度( p a p u l 村) 高的资源，该方案能节省带宽消耗； k r d o mw a l k s l 3 2 1 ：节点发出k 路查询消息，每前进一步，消息将只被随机转发到一个邻居上，k 值通常取1 6 6 4 之间。消息也带有t t l 终止机制；表1 2 i s 2 1 显示了t r l - f l o o d i n g ，e x p a n d i n gr i n g 和k - r a n d o mw a l k s 在幂率随机拓扑( p o w e r - l a wr a n d o mg r a p h ) 和o n u t l l a 拓扑中的性能比较，可 以看到，k - r a n d o m w a l k s 显著降低了冗余消息数量和搜索范围，但增大了搜索延迟 f l o o d r i n g k - t a l l d o mw a l k s d i s t r i b u t i o n r e p l i c a t i o n m c t r i c s p l r gg n u t e l l ap l r gc m u t e l l ap l r gc r n u t c l l a h o p s 2 3 7 2 3 93 5 03 4 08 4 7 6 1 l u n i f o r m u n i f o r i l l m s g sp e rn o d e 3 3 34 1 6 21 3 2 50 3 6 9o 0 30 0 4 5 n o d e sv i s i t e d8 9 3 54 5 5 64 8 7 49 3 31 5 81 5 1 h o p s 2 0 7 2 0 32 9 33 0 589 87 9 4 z i p f - l i k c p r o p o r l i o n a lm s g sp e rn o d e 2 8 53 ，5 4 80 9 6 10 4 2 3 0 0 2 9 0 0 5 l n o d e sv i s i t e d7 9 2 34 1 3 73 6 3 l8 1 01 4 51 5 3 r b f s ”：泛洪消息每步选择一部分邻居而非全部； i s m ( i n t e l l i g e n ts e a r c hm e c h a n i s m ) d 3 i ：节点纪录邻居应答历史，将查询转发给最可能相关的邻居， 该方案一定程度的削弱了随机性而增强了路由指导性：a p s ( a d a p t i v ep r o b a b i l i s f i cs e a r c h ) 1 ：结 合i s m 和k - r a n d o m w a l k s ，使邻居选择带有历史指导性，同时不放弃路由随机性，以此增强路由 效率和确定性： l o c a lr o u t i n g i n d i c e s p ”：类似o s p f 路由协议节点通过信息交换确定达到资源的下一跳，但可扩 展性依然较差。 p r o b a b i l i s t i cl o c a t i o n l s 6 1 ：设计a t t e n u a t e db l o o mf i l t e r 压缩表示了不同距离范围内的节点资源，每 个节点维护一个b l o o mf i l t e r 并按时按需更新。从而具有对整体网络资源分布的粗粒度映像，使 泛洪方向带有内容指导性提高了路由准确性。 m o d i f i e dg n u t e l l a t ”1 ：对原有o n u t e l l a 协议作了很多改进，以提升可扩展性和路由效率，这些改 进主要包括：( 1 ) t o p o l o g ya d a p t a t i o n ，选择高能力且度小的节点作为邻居；( 2 ) f l o wc o n t r o l ，节 点根据接收端的t o k e n 发送查询；( 3 ) o n e - h o pr e p l i c a t i o n ：( 4 ) b i a s e dr a n d o mw a l kr 随机游走倾向 选择高能力节点。 e d b f 3 s 1 ：设计了更精致的d e c a yb l o o mf i l t e r 。 h y b r i ds e a r c h ”1 ：对不同拓扑特征的网络给出了不同的搜索策略，结论包括：聚类网络适用f l o o d i n g w i t hd i r e c t i o n 搜索方法节点度相差大的网络适用r a n d o mw a l k sw i t hl o c a lf l o o d i n g 搜索策略。 随着对非结构化p 2 p 系统研究的深入，人们最终发现可扩展性和路由确定性问题与网络拓扑密切相关， 甚至很大程度上取决于网络拓扑的特征。因此非结构化p 2 p 系统研究的关键落实到以下问题：p 2 p 网络拓 扑的实际特征是怎样的? 应该用什么网络图进行描述? 算法参数( 如t i i j 、k - w a l k s f o r w a r dp r o b a b i l i t y f r a c t i o no f n e i 曲b o r s 、d i s t a n c e 等) 设置的拓扑依据是什么? 1 2 3 分散式结构化e c e n t r a l i z e db u ts t r u c t u r e d ) 结构化p 2 p 系统