（计算机应用技术专业论文）抗抖动的p2p覆盖网的设计与分析.pdf

曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“”) 本人郑重声明：此处所提交的博士口硕士囱论文抗抖动的p 2 p 覆盖 网的设计与分析，是本人在导师指导下，在曲阜师范大学攻读博士口硕 士留学位期间独立进行研究工作所取得的成果。论文中除注明部分外不包含 他人已经发表或撰写的研究成果。对本文的研究工作做出重要贡献的个人和 集体，均已在文中己明确的方式注明。本声明的法律结果将完全由本人承担。 作者签名：际敏 日期：2 0 o 、6 2 - 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“ ) 抗抖动的p 2 p 覆盖网的设计与分析系本人在曲阜师范大学攻读博士口硕 士囹学位期间，在导师指导下完成的博士口硕士日学位论文。本论文的研 究成果归曲阜师范大学所有，本论文的研究内容不得以其他单位的名义发表。 本人完全了解曲阜师范大学关于保存、使用学位论文的规定，同意学校保留 并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人 授权曲阜师范大学，可以采用影印或其他复制手段保存论文，可以公开发表 论文的全部或部分内容。 作者签名：陈敦 新签名：岛嗣 日期：卸f d 、b 、z 日期：山陬6 歹 抗抖动的p 2 p 覆盖网的设计与分析 摘要 网络抖动( c h u r n ) 是指在对等网络中，由参与者的匿名、自由性以及规模大的特点 导致的大量节点频繁自发地加入、离开或失效的现象。抖动是影响对等网络系统性能的一 个重要因素，它可能引起数据丢失、查询失败、多个查询结果不一致、用户时延变大和应 用带宽增加等问题，严重时可能会使得整个网络拓扑被分割成几个不连通的子集，导致网 络性能急剧下降，甚至无法恢复。抖动更是性能优越的结构化对等网络至今没能够被充分 部署应用的主要原因之一。因此在设计对等网协议时需要考虑如何提高系统的抗抖动能 力，在评价对等网协议时需要把该协议构造的对等网是否具有应对网络抖动的能力作为网 络性能的重要评价标准。所以，研究对等网中抖动的特点和规律，寻找应对覆盖网抖动的 策略，对于对等网络的性能的优化具有非常重要的意义。 文中总结了国内外研究者对对等网络中抖动的特点以及应对策略的研究现状，并设计 了具有高抗抖动能力的对等网络模型和算法，包括： ( 1 )利用“冗余机制 、“基于生命周期 的节点选择机制和 角色划分 机制对 c y c l o i d 的设计进行改进，构造了一个基于c y c l o i d 的具有高抗抖动能力的结构 化p 2 p 系统- - - c t - c y e l o i d 。 ( 2 ) 使用“路标集群 的方法开发和利用节点之间的邻近性，修改原g o s s i p 协议， 构造了一个新的拓扑一致的k e l i p s 覆盖网。这种覆盖网通过执行一个扩展的 g o s s i p 周期恢复协议，具有了更高的查询定位效率，更强的负载均衡和抗抖动 能力。 ( 3 )设计了一个可用于构造具有抗抖动能力的p 2 p 覆盖网的负载均衡算法。该算法 基于虚拟服务器，其执行过程便是一个具有负载均衡和高抗抖动功能的结构化 对等网络的构造过程。 关键词：对等网络；抖动；冗余机制；基于生命周期机制；g o s s i p 协议；拓扑 一致性；负载均衡 a b s t r a c t c h 啪i np e e “o p e e r ( p 2 p ) n e t w o r k si st h ep h e n o m e n o n t h a tal a r g en u m b e ro fn o d e sj o i n ， l e a v eo rf a i ls p o n t a n e o u s l ya n df r e q u e n t l y , b e c a u s eo ft h e i rn a t u r eo fa n o n y m o u s ，f r e e ，a n d l a r g e - s c a l e c h u mi ss u c has i g n i f i c a n tp e r f o r m a n c ei n f l u e n t i a l f a c t o ro fp 2 pn e t w o r k st h a t ，i t m a yc a u s ed a t el o s s ，s e a r c hf a i l u r e ，i n c o n s i s t e n c ys e a r c hr e s u l t s ，i n c r e a s ei nu s e r - r e l a t e dl a t e n c y a n db a n d w i d t h ，o re v e np a r t i t i o no ft h eo v e d a yn e t w o r k ，w h i c hw i l l l e a dt os h a r ps y s t e m p e r f o m a n c ed e c r e a s eo re v e nt h a tt h eo v e r l a yc a l ln e v e rr e c o v e r b e s i d e s ，c h u r ni sa l s oo n eo f t h em o s ti m p o r t a n tr e a s o nw h ys t r u c t u r e dp 2 pn e t w o r km o d e l st h a th a v eb e t t e rp e r f o r m a n c e e x p e c t a t i o n st h a nu n s t r u c t u r e do n e sh a v en o tb e e nd e p l o y e db yn o w h e n c e ，w h e t h e ri n d e s i g n i n gan e w p 2 p p r o t o c o lo rw h e na p 2 p p r o t o c o li se v a l u a t e d , t h ea b i l i t yt or e c o v e rf r o m 龇s h o u l db ec o n s i d e r e d t h e r e f o r e ，i ti sv e r ym e a n i n g f u lt os t u d yt h ec h a r a c t e r sa n dn a t u r eo f c h u r ni np 2 po v e r l a yn e t w o r k s ，a n dt r yt o f i n ds c h e m e st om a k ep 2 ps y s t e m sm o r e c h u m - r e s i s t a n t i nt h i sp a p e r , w ef i r s ts u mu pt h es t a t eo fa r to fs t u d yi nn a t u r eo fc h u m i nd e p l o y e dp 2 p n e r k sa n di nc h u m - r e s i l i e n ts t r a t e g i e s ，a n dt h e nb u i l du pt w oc h u m - r e s i l i e n tp 2 p n e t w o r k s a n da na l g o r i t h m ，a sf o l l o w s ： ( 1 1a n o v e is t r u c t u r e dp 2 pn e t w o r ko fh i g hc h u m - r e s i s t a n c e - - - c t - c y c l o i d ，w h i c hi sb a s e d o nc y c l o i d ，i sc o n s t r u c t e db yu s eo f r e d u n d a n c ym e c h a n i s m s ，l i f e s p a n b a s e dn o d e c h o i c e m e c h a n i s m s ，a n dar o l e d i v i s i o ns c h e m e ( 2 ) an e wt o p o l o g y a w a r ek e l i p so v e r l a y n e t w o r ki sc o n s t r u c t e db ye x p l o i t i n ga n du t i l i z i n g t o p o l o g yp r o x i m i t yt h r o u g h “l a n d m a r kc l u s t e r i n g ”，a n db ym o d i f y i n gt h eo r i g i n a lg o s s i p p r o t o c 0 1 t h i sn e t w o r kp e r f o r m sp e r i o d i cr e c o v e r yt h r o u g h ag o s s i pr e c o v e r yp r o t o c o l ， a n dh a sh i g h e re f f i c i e n c ya n ds t r o n g e ra b i l i t yo f c h u r n r e s i l i e n c e ( 3 ) al o a d - b a l a n c i n ga l g o r i t h mw h i c hc a nb eu s e dt o b u i l dc h u r n r e s i l i e n tp 2 po v e r l a y n e t w o r k si sd e s i g n e d t h ea l g o r i t h mi sb a s e do nv i r t u a ls e r v e r , a n ds t r u c t u r e d p 2 p 虢r k sw i t hl o a db a l a n c i n ga n dh i g hc h u m r e s i s t a n tc a p a b i l i t yc a l l b eb u i l ti nt h e p r o c e s so ft h ea l g o r i t h m si m p l e m e n t a t i o n k e y w o r d s ：p e e r - t o p e e r n e t w o r k s ； l i f e s p a n b a s e ds t r a t e g y ；g o s s i pp r o t o c o l ； l i c h u m ；r e d u n d a n c ym e c h a n i s m s ； t o p o l o g y a w a r e n e s s ；l o a db a l a n c i n g 抗抖动的p 2 p 覆盖网的设计与分析 目录 第一章绪论1 1 1 研究背景1 1 2 对等网络中的抖动概述2 1 2 1 抖动的定义2 1 2 2 抖动对覆盖网性能的危害2 1 2 3 抖动大小的衡量标准2 1 3 国内外研究现状3 1 3 1 抖动特点的研究。4 1 3 2 应对抖动策略的研究5 1 4 本文主要工作。9 1 5 论文结构与章节安排9 第二章c t - c y c l o i d ：基于c y c l o i d 的抗抖动的p 2 p 系统1 0 2 1 弓i 言1 0 2 2 相关工作1 0 2 2 1c y c l o i d 1 ( ) 2 2 2 基于生命周期的机制1 0 2 2 3 一个简单的抗抖动机制1 1 2 ：；c t - c y c l o i d 1l 2 3 1c t - c y c l o i d 的系统结构1 1 2 3 2 路由组织方式和路由策略1 2 2 3 3 新节点加入1 2 2 3 4 数据对象插入与查询1 3 2 3 5 节点的离开1 3 2 3 6 节点的失效1 4 2 3 7 网络规模的变化的处理1 6 2 4 仿真实验及分析l6 2 5 总结19 第三章抗抖动的拓扑一致的k e l i p s 系统2 0 3 1 引言2 0 ：；2k e l i p s 2 0 3 2 1 节点软状态2 0 3 - 2 2g o s s i p 协议2 1 3 3 构建和维护有拓扑意识的k e l i p s 。2 2 3 3 1 拓扑构建2 2 抗抖动的p 2 p 覆盖网的设计与分析 3 3 2 覆盖网的完善和维护扩展的g o s s i p 协议2 6 3 3 3 新节点加入2 7 3 4 仿真实验和性能分析。2 7 3 4 1 时间和空间复杂度分析2 8 3 4 2 拓扑一致性和应对抖动能力测试2 8 3 5 总结和将来工作3 1 第四章可用于构造抗抖动p 2 p 系统的负载均衡算法3 2 4 1 弓i 言3 2 4 。2 相关工作3 2 4 3l o g n v s 算法3 4 4 3 1 节点初次加入算法3 4 4 3 2 节点自适应算法3 5 4 3 3 节点再加入算法3 7 4 4 仿真实验和性能分析3 8 4 4 1 算法的简单应用a s e 3 8 4 4 2 对a s e 的仿真实验。3 8 4 5 总结与将来工作4 l 第五章总结与展望。4 2 5 1 总结4 2 5 2 展望4 2 参考文献4 3 在校期间发表的学术论文4 8 致谢4 9 i v 【一 抗抖动的p 2 p 覆盖网的设计与分析 1 1 研究背景 第一章绪论弟一早三百y 匕 随着因特网规模和功能的不断扩大，服务器的负担越来越重，传统的c s 工作模式暴 露出其难以扩展等方面的缺陷。另一方面，个人电脑计算能力得到提高，用户之间资源共 享的需求越来越多。这使得对等计算( p e e r - t o p e e rc o m p u t i n g ) 模式得到了广泛重视、研究 和应用。对等计算模式的核心思想是：所有参与系统的节点处于完全对等的地位，没有客 户机和服务器之分，每个节点本身既是客户机也是服务器，既向别人提供服务，也享受来 自别人的服务j 。 工作在应用层之上，采用对等计算模式工作的覆盖网络被称作对等网络，又n q p 2 p 覆 盖网。p 2 p 覆盖网中的节点都是自由、平等、分布式互联的。它能够开发每个节点的潜力， 充分利用网络带宽，因而可以极大地提高网络效率，并具有高可扩展性。对等网络的发展 经历了混合式对等网，无结构对等网，到目前研究比较多的结构化对等网络【2 1 。结构化对 等网络，利用严格的分布式哈希表结构来组织节点和对象，能为任何一个节点和数据对象 精确地提供其在覆盖网中的位置映射，这使得任何一个节点都能本地计算出任何其他节点 或数据对象在覆盖网中的位置，因而能够精确的定位到任何节点和数据对象而无需盲目地 进行洪泛。所以与无结构对等网络相比，结构化对等网络拥有更高的节点和数据定位效率 以及高可扩展性。 此前对对等网络的研究工作大都集中在对其核心机制的研究上，即研究其最核心、最 基本的构件，包括拓扑结构、路由和定位、以及查询和搜索等。但要使对等网络真正高效 率、高可用、高安全地工作，还需要发现其具有的某些缺陷，然后去克服之。覆盖网中节 点的频繁加入、离开或失效的动态特性( 即网络抖动) 就是对等网络优化需要解决的问题 之一。因为它可能会引起数据丢失、查询失败、多个查询结果不一致、用户时延变大和应 用带宽增加等问题，严重时可能会使得整个网络拓扑被分割成几个不连通的子集，导致网 络性能急剧下降。而且抖动发生之后，为了保证覆盖网继续正常工作，需要花费大量的带 宽和时间对网络进行修复。在抖动率较高的环境下，一些脆弱的对等网络甚至无法被修复。 这些问题更严重制约了结构化对等网络的发展：为满足网络直径的要求，结构化对等网络 事先规定了节点之间的链接关系，所以在节点不断加入、离开、失效存在的情况下难以恢 复。所以即使结构化对等网络( c h o r d 1 ，c a n ”1 ，p a s t r y 1 和k a d e m l i a 1 ) 在查询定位效率， 以及可扩展性上明显优于无结构对等网络，但是它们却不能像无结构对等网络那样容易被 部署应用。目前已被部署应用的对等网络主要是无结构对等网络，如n a p s t e r 7 1 ，g n u t e l l a 引。 f r e e n e t 9 1 ，b i t t o r r e n t l l 0 1 和k a z a a 1 1 1 。因此，研究对等网络中的抖动问题，尤其是构造具有 高抗抖动的能力的p 2 p 覆盖网具有极其重要的意义。 f 一 抗抖动的p 2 p 覆盖网的设计与分析 1 2 对等网络中的抖动概述 1 2 1 抖动的定义 抖动是指在对等网络中，由参与者的匿名、自由性以及规模大的特点导致的大量节点 频繁自发地加入、离开或失效的现象。目前，对它还没有一个统一的定义。w u 等人将抖 动划分为暂时抖动( t e m p o r a r yc h u m ) 和永久抖动( p e r m a n e n tc h u m ) ，并以此作为确定 数据恢复策略的依据【1 2 1 。l i 等人将抖动划分为度抖动( d e g r e ec h u m ) 和连接关系抖动 ( c o n n e c t i o nc h u m ) ，并以此为标准衡量g n u t e l l a 覆盖网的抖动性【1 3 】。l i u 等人【m l 则根据 抖动的剧烈程度将它划分为普通抖动和高抖动，这种划分方法目前被引用的最多。 ( 1 ) 普通抖动：节点一个接一个地串行离开网络，离开前更新路由表。发生的频率不 高，网络有足够的时间来做修复，以保持网络应有的结构和连通性。 ( 2 ) 高抖动：对等网络中有大量的节点频繁并且自发地加入、离开或失效。 在现实世界中高抖动确实存在，比如一些非常热门的电影，可能会在短时间内使得大 量用户加入和离开；某地区突然断电又马上恢复使得大量节点突然离开又重新加入；人为 设计的大量受控恶意节点的突然加入或离开。另外对现实世界p 2 p 网络的研究f ”。1 7 】也证明 了覆盖网中的抖动率是非常高的，现实世界p 2 p 网络中近乎5 0 的节点会在一个小时内离 开网络。 1 2 2 抖动对覆盖网性能的危害 覆盖网中的抖动对系统性能最直接的影响包括：可能引起数据丢失、查询失败、多个 查询结果不一致、用户时延变大和应用带宽增加等问题。除此之外，抖动对覆盖网的影响 还在于在抖动发生之后，需要花费大量的工作来对节点路由表进行修复。这是因为覆盖网 的工作效率主要取决于节点是否有一个合理且高效的路由表，使得该节点能够在o ( 1 0 9 n ) 时间内对数据对象或节点进行定位。抖动严重时可能会使得整个网络拓扑被分割成几个不 连通的子集，导致网络性能急剧下降，甚至直接造成整个系统瘫痪，再也无法修复。对于 有着高效查找定位和高可扩展性等优良性能的结构严密的d h t 覆盖网【l 睨0 j 来讲，这些问 题表现的更加突出。g u m m a d i l 2 l 】研究得出，能否应对抖动是d h t 性能的关键影响因素。 因为在抖动环境下d h t 网络为了维护特定的拓扑结构需要不断地修复路由表，导致维护 代价显著增加，进而严重影响d h t 的网络性能。另外，也正是由于这些原因，结构化p 2 p 覆盖网至今都难以被很好地被实际部署应用。 1 2 3 抖动大小的衡量标准 对覆盖网中的抖动率，大体有以下两类衡量方法。 ( 1 ) 节点寿命( l i f e s p a n ) 和会话时长( s e s s i o n ) ( 如图l 一1 ) 。节点寿命是指节点第一 2 抗抖动的p 2 p 覆盖网的设计与分析 次加入到最终离开的时间。会话时长是指从节点的加入到它随后离开的这段时间的长度 1 2 2 1 。前者较后者更加宏观，忽略了节点突然断线又马上上线等类似情形的干扰；后者则比 较细致，有时候能却更精确描述覆盖网的动态性。所以它们各自适合于不同的环境，但有 时又可以通用。节点的可用性( a v a i l a b i l i t y ) 被定义为节点寿命期内，节点会话时长之和 与节点的寿命之比，即a v a i l a b i l i t y = s e s s i o n t i m e l i f e s p a n 。在图1 1 所示的例子中，节点 的可用性为6 3 6 。 有研究显示节点的存活时间( s e s s i o n ) 中值为数十分钟，节点的寿命( l i f e s p a n ) 中值为 几天，而节点的可用性中值大约为3 0 1 2 引。由此，很多人认为使用l i f e s p a n 来衡量网络抖 动大小的做法是无效的，因而应该选择s e s s i o n 作为抖动大小的衡量标准。据研究，节点 s e s s i o n 长度的分布可能会影响到覆盖网的结构【2 4 】，覆盖网的恢复能力口5 1 ，以及键值设计 参数的选择f 2 6 】。h e 仃e r a 【2 7 】等人通过仿真实验得到c h o r d 和t a p e s t r y 的性能与平均s e s s i o n 值的关系图，并得出s e s s i o n 值与网络性能存在这样的关系：s e s s i o n 值缩短导致平均查找 延时增加、平均带宽消耗增加以及平均查找成功率降低。这些又进一步说明s e s s i o n 是覆 盖网抖动的一个很好的衡量因子。 l i f e s p a n s e s s l o n 。习 黔 “ 4 习 oi 4 f 引 1 1 f - 1 图l - 1l i f e s p a n 和s e s s i o n 的定义 ( 2 ) 半生命周期( h a l f - l i f e ) 。半生命周期是另一个常被使用的抖动衡量因子 2 8 1 。设系 统中初始的节点数目n 。从某一时刻开始计时，如果在时刻t l 系统中节点数目为2 n ，那么 t l 叫做该系统的一个加倍时间；如果在时刻t 2 系统中初始存在的节点还剩下n 2 ，那么t 2 叫做该系统的一个减半时间。该系统的“半生命周期就是所有的t l 和t 2 中较小的那一个。 “半生命周期”是系统状态变化的一个粗略标尺，不能反映节点的加入和离开的细节，但 是在许多环境中，它都是p 2 p 系统变化速率的一个有效的衡量标准【2 9 】。 1 3 国内外研究现状 目前对覆盖网中的抖动的研究工作可以分为以下两类： ( 1 ) 对已经部署的覆盖网中的抖动的特点进行研究。测量其中节点的加入、离开、失 效的规律以供人们找出应对策略；据分析所得到的数据，选取适当的模拟函数，建立抖动 模型，以供人们用来评价所提出的应对策略的有效性。 抗抖动的p 2 p 覆盖网的设计与分析 ( 2 ) 据覆盖网中抖动的特点和产生的原因的分析找出应对抖动的策略，构造具有抗抖 动能力的p 2 p 覆盖网。 1 3 1 抖动特点的研究 要研究大规模的对等网络中抖动的特点，直接获取到每个节点准确加入和离开信息是 不可能的，通常做法是采用被动监视( p a s s i v em o n i t o r i n g ) 或主动探测( a c t i v ep r o b i n g ) 的方法来获得节点会话时长的近似值。被动监视是指在网络的不同位置部署一定数量的监 测点，使用特定的软、硬件设备采集相关的p 2 p 数据流信息【3 0 1 。主动探测则是使用网络爬 虫( c r a w l e r ) 主动加入特定的p 2 p 网络，获取p 2 p 网络特性以及节点的会话行为。主动探测 的优点是探测过程可控性较高，测量结果准确性较好。先后发起探测的时间间隔粒度对测 量准确性有较大的影响，特别是在抖动环境下【l7 1 。 s e n 等人【l6 j 使用被动监视的方法在一个大的i s p 网络的多个路由器上对来自 f a s t t r a c k 、g n u t e l l a 和d i r e c t c o n n e c t 的p 2 p 流量进行监测，然后对得到的数据进行分析， 发现节点的在线时间是长尾的，但不是z i p f 分布。g u m m a d i 3 1 】等人在华盛顿大学的出口 网关上对k a z a a 的负载特点进行研究，发现节点的s e s s i o n 值分布是长尾的( 其中值为2 4 分钟，但是9 0 的节点的s e s s i o n 值为2 8 2 5 分钟) 。这种被动监视的方法往往会低估s e s s i o n 的值，因为一些节点的流量可能不会连续地被在一个观察点获得，而且要正确地区分p 2 p 流存在一定的困难1 3 引。 运用主动探测的方法，c h u 等人田j 对n a p s t e r 和g n u t e u a 进行测量，发现网络中3 1 的节点的会话时长少于1 0 分钟，会话时长服从二次对数( l o g q u a d r a t i c ) 分布。s a r o i u 等人【3 4 1 同样对n a p s t e r 和g n u t e l l a 进行主动探测，得出节点会话时长的累积分布函数，发现这两 种系统的会话时长分布特征非常相似，中值大约为6 0 分钟，绝大多数的会话非常短暂， 会话时长分布有较重的偏斜。b u s t a m a n t e 和q i a o 对g n u t e l l a 的对等体进行主动探测，发现 帕累托( p a r e t o ) 分布能够较好地模拟所得的s e s s i o n 数据【3 5 1 。s t u t z b a c h 和r e j a i e l l 7 1 指出先 前的研究大都没有考虑在抖动研究过程中可能面临的各种会使研究结果失去精确性的困 难( 包括数据丢失、对所选对等体的偏向行为、动态地址等问题) ，因而得出的研究结果 必定是不精确的。他们针对这些困难，提出了相应的应对策略，然后将这些策略应用到对 g n u t e l l a ，b i tt o r r e n t 和k a d 三个p 2 p 应用系统中的抖动的研究中。结果，他们发现s e s s i o n 长度分布不是长尾的，因而也不是帕累托分布，但是可以被威布尔( w e i b u l l ) 分布或对数 正态( 1 0 9 n o r m a l ) 分布很好地模拟。 虽然s t u t z b a c h 和r e j a i e 的研究克服了前述的研究方法的种种障碍，取得了更大的进 步。但是他们对三种对等网络的研究得出的结果并不一定具有普遍适用性，会话时长究竟 服从什么分布到目前为止尚无定论。r h e a 等人 2 2 1 对这些研究结果进行总结，得出学界公 认的关于对等网络中抖动的一般结论：p 2 p 网络中大部分节点的会话时间较为短暂，从1 4 抗抖动的p 2 p 覆盖网的设计与分析 分钟到l 小时不等，p 2 p 文件共享系统具有非常高的抖动率。依据以上研究结果，目前被 广泛采用的抖动的理论模型通常采用指数分布或重尾的p a r e t o 分布盼3 6 - 3 8 1 来模拟会话时 长。另外还有人设计了更为精细的抖动模型，用来模拟网络抖动，评价抖动下系统的稳定 杜【3 9 ，删 _ lo 1 3 2 应对抖动策略的研究 抖动是覆盖网的本质特点，大部分是由用户的自主行为造成的，这是我们无法阻止的； 有一些是恶意用户造成的，这是我们无法预知的：还有一些是设计不当( 如负载不均衡) 引起的节点失效。所以说，减少网络抖动或提高网络的抗抖动性能，其实都是指要采用某 种或某些策略来优化网络设计减少失效的发生，以及减少在节点的频繁加入、离开或失效 时系统进行稳定恢复时需要做的工作。在高抖动环境中如何提高p 2 p 网络尤其是结构化 p 2 p 网络的性能是p 2 p 研究领域的一个开放性的热点问趔4 。并且对此问题的研究已有了 一些成果，下面列举当前已被提出的抗抖动的有效措施。 ( 1 ) 三个影响抖动环境下d h t 覆盖网性能的因素 r h e a 等人研究得出了在抖动环境中影响d h t 工作效率的三个因素，并指出如何在结 构化p 2 p 的设计中从这三个方面进行考虑，选择合适的策略以有效地提高系统在抖动环境 下的生存能力1 2 2 j 。对这三个因素的介绍如下。 使用的恢复策略是被动恢复的还是周期恢复。 被动恢复是指节点仅在发现有邻居失效时才去查找一个替补项的恢复方法。他们证明 了在带宽有限的情况下，被动恢复可能引起使覆盖网超载的正反馈环，从而带来查询延迟 变大，查询不一致等问题。周期恢复是指节点周期地与自己的叶节点相互交换叶节点集， 从而使得节点能够及时发现网络变化，从而及时进行更新。周期恢复一般使用基于g o s s i p 的协议。模拟实验证明：在低抖动环境下，使用被动策略时信息仅在真正有变化发生时才 被发送，因而效率更高，反而是周期恢复策略浪费了带宽；在抖动率适中环境下，周期恢 复策略使用较少的带宽，更少的延迟就能保证网络恢复。 查询信息超时的设置方法。 节点为查询信息设置超时值的方法也会影响抖动下d h t 的性能。如果为查询信息设 置了合适的超时，一个节点将信息发送到一个已经离开网络的节点时，该节点就可以在信 息超时的时候选择其它邻居进行重新尝试。作者证明了超时值的设置是否得当是抖动下查 询延迟以及查询成功率的主要影响因素之一。另外他们描述了两种计算超时值的方法，并 证明了这些方法的有效性。一种方法是基于周期探测时获得的到邻居的平均来回时延信息 来估算超时值的t c p s t y l e 方法。在这种方法中，每个节点记录它的每个邻居的平均来回 时延值a v g ，以及当前观察到的来回延时值v a r ，超时的计算方法为：i 玎o = a v g + 4 k r 【4 2 1 另一种是基于虚拟坐标的估算方法【4 3 1 。在这种方法中，每个节点需要记录到每个邻居实际 抗抖动的p 2 p 覆盖网的设计与分析 的来回延时与使用虚拟坐标方法计算得出的来回时延值v 的误差的平均值a ，那么超时值 i 淝= v + 6 a + 1 5 【州。其中1 5 的时间单位为毫秒，它的存在可以避免在目的节点为当前节点 时进行不必要的转发。实验证明在高抖动环境下，使用前者较为有效，在抖动率适中时两 者有相似的功效。 近似邻居选择的应用 近似邻居选择( p n s ，p r o x i m i t yn e i g h b o rs e l e c t i o n ) 是指在节点有多个候选邻居时， 基于来回延迟的标准选择离自己最近的节点。他们研究得出，首要事情是将路由表填满以 使得系统尽快开始工作，而不是寻找最优项( 最近节点) ，尤其是在有抖动存在的环境下。 所以作者提出应该周期地执行p n s 算法。在高抖动环境下，该策略允许根据网络变化调整 路由表；在抖动率较低的环境下，这种策略允许去弥补暂时的网络异常状况引起的延迟测 量误差。 r h e a 研究得出的影响抖动环境下d h t 的这三个因素，在设计d h t 覆盖网协议的时候 都是首先应该考虑的问题，所以该研究结果对抗抖动的d h t 覆盖网的设计具有非常普遍 和重要的指导意义。 ( 2 ) 基于节点寿命的组织机制 p 2 p 网络性能的发挥要依赖于每个节点有个完整和稳定的邻居，而且节点在邻居维 护上所花费的开销与节点的邻居集的稳定性成正比。所以在高动态的环境中，要使覆盖网 系统保持高效性，应该采取某种机制保证节点邻居的稳定性。 b u s t a m a n t e 等人对g n u t e l l av 0 6 中5 0 万的对等体进行了研究，他们发现对等体的生 存期可以被帕累托分布模拟【4 5 1 ，这意味着对等体期望的剩余生存时间与它的当前“年龄” 成正比。于是他们提出了基于节点寿命的组织策略。即在节点进行邻居选择时，将节点当 前年龄作为对节点稳定性进行推测的依据。 他们通过基于t r a c e s 的模拟实验比较了基于寿命的组织策略和其它策略在分布式无结 构和松散结构网络中的表现。结果发现简单的基于节点寿命的机制与其它机制相比能够减 少4 2 的连接失效率。后来他们又将基于节点寿命的策略应用在应对抖动的松散结构( 超节 点网络) 的对等网络的构造过程q b t 4 5 , 4 6 j 。简单来说基于生命周期的抖动应对机制的思想是： 提高系统对网络中已经生存较长时间的节点的依赖性。如在选择超节点时优先考虑有较长 寿命的节点，在超节点选择其它的超节点进行连接时从候选项中优先考虑“较老的节点。 他们的实验结果证明了单纯使用“基于节点寿命的机制 就可以有效增加系统的稳定性， 而这种机制与包括查询散布、缓存和复制这些增强机制的联合又更大程度地增强了系统的 稳定性。 无结构对等网络与结构化对等网络相比具有很好的自适应能力，因此在抖动环境下， 他们能够进行自我调整，具有较好的抗抖动能力。s t u t z b a c h h ”在高抖动环境下对p 2 p 文件 共享系统进行网络测量的结果以及y a 0 1 3 9 】对无结构对等网络系统的理论分析都显示，在无 结构覆盖网中已存活时间较长的节点其连接度大，保证了高抖动环境下网络的连通性。这 6 抗抖动的p 2 p 覆盖网的设计与分析 点也说明了“提高对网络中有更长已经存活时间的节点依赖性”的方法应该能够用来提高 对等网络的抗抖动性。 综上，可以将“基于节点寿命的机制应用到结构化对等网络的组织设计中来提高结 构化对等网络的性能。 o ) 节点选择过程中加入随机因素 在并行和分布式环境中，简单的随机负载均衡方法能够在花费很小开销的情况下实现 有效的均衡，因而被应用到许多应用系统中。最近又有人提出将随机选择策略应用在对等 网络构建中来提高系统在抖动下的工作效率。理由是随机选择算法具有可扩展性，花费较 少的控制信息和数据结构，更重要的是在动态环境中，它比那些设计严格的选择算法更能 够适应网络变化。 s h e n 和x u 4 8 】在他们的应用于结构化p 2 p 的具有本地意识和抖动恢复能力的负载均衡 算法的设计中就采用了d 路随机探测法。实验证明了在抖动环境下，使用2 路随机探测能 够更快达到负载均衡和系统稳定的目标，这说明随机因素的加入可以提高系统在抖动环境 下的性能。 g o d f r e g 等人研究了如何通过从一个可选节点集合中选择一个合适的子集来减少网络 抖动【4 9 】。他们首先通过实验比较了一系列节点选择策略，发现当节点离开时，简单的平均 随机替换方法拥有更好的性能。基于来回时延的优先表( p r e f e r e n c el i s t ) 策略与随机性策 略相比引起了更多的网络抖动。并且抖动越不规则，随机选择方法与其他方法相比，性能 就越优越。最后作者得出结论：在任何情况下加入一定的随机性对应对网络抖动都是非常 有帮助的。 ( 4 ) 利用冗余策略建立应对抖动的覆盖网模型 传统的冗余策略是指数据对象冗余，即使用复制和缓存来提高文件的可用性，这无疑 可以提高覆盖网应对抖动的能力。这里要介绍的冗余策略主要是指一个逻辑地址对应多个 物理实体的冗余，即将多个物理实体映射到一个i d 号。它实际实现了将数据对象在网络 中复制多份。这种策略与周期维护策略的结合，可以减少节点离开时的系统开销，防止节 点失效造成数据丢失，而且能够提高查询效率。 p a n d u r a n g a n 和j a g a n n a t h a n 5 0 】提出了一个可以将一个静态网络转变为具有高抗抖动 能力的动态对等网络的方法。其过程是让0 0 0 9 n ) 规模的动态覆盖网g 中的节点占据静态 网络h 中的一个顶点( 其中n 为覆盖网g 的估计大小) ，也就是让这些节点拥有相同的i d ， 负责所有被映射到该i d 的数据对象。这样就相当于将同一个数据对象在系统中复制了 0 0 0 9 n ) 份。所以在节点离开时无需做任何工作，从而在大量节点离开时不会引起网络带宽 的急剧增加，在大量节点失效时仍能保证数据的可用性。理论分析证明了使用这一方案构 造的覆盖网不仅具有一般对等网络的所有优点，而且还能应对网络的高抖动性。 k u h n 等设计了一个允许节点在任意时刻加入和离开网络的分布式哈希表系统【5 。该 系统的基本结构是一个超立方体，每一个超立方体顶点包含o ( 1 0 9 n ) 规模的对等体。该系 7 抗抖动的p 2 p 覆盖网的设计与分析 统可以根据网络的变化来动态调整超立方体顶点所包含的对等体数目来保证覆盖网的完 整性，从而使系统具有应对恶意抖动攻击的能力。 ( 5 ) 基于g o s s i p 的维护策略 在这一章的第l 小部分提到了周期恢复策略的合理应用可以有效地提高系统适应网络 抖动的能力。这一部分通过一个例子说明基于g o s s i p 的周期恢复策略可以提高系统应对覆 盖网抖动的能力。 g u p t a 等人应用k e l i p s 5 2 】构造了一个能够有效应对网络抖动的p 2 pw e b 缓存系统【5 3 1 。 k e l i p s 不同于以往的d h t 系统，它通过增加存储需求和固定的背景通信来减少文件查寻开 销，提高在节点失效和网络抖动环境下系统的稳定性。这里的背景开销就是指使用g o s s i p 协议实现动态维护的开销。他们将g o s s i p 信息设计为固定大小、并将这个固定大小在各种 信息间进行合理配给，保证了网络状态变化被节点及时发现并执行更新，从而使得系统在 抖动环境下具有很高的生存能力。 ( 6 ) 通过实现负载均衡来实现应对抖动 实现负载均衡和提高应对抖动的能力是提高对等网络性能的两个主要手段。它们紧密 相关。在实现了并持续具有负载均衡特点的系统中各节点各尽所能地稳定工作，这时往往 使用一般方法( 如周期恢复策略) 就可以使网络从抖动中恢复。相反如果系统负载不均， 使得某些节点负载超出其能力限制而失效离开，网络中的抖动率就会加重，给恢复工作带 来更大困难。 s h e n 和x u 4 8 1 设计了一个可用于构造抗抖动结构化