（计算机系统结构专业论文）非结构化p2p网络节点负载均衡机制研究.pdf

r e s e a r c ho nt h en o d el o a db a l a n c ec o n t r o l m e c h a n i s mi nu n s t r u c t ur e dp 2 pn e t w o r k s 彳砌e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t f o rt h em s d e g r e e 锄c o m p u t e rs c i e n c e b y c h e nl i l o n g p o s t g r a d u a t ep r o g r a m d e p a r t m e n to fc o m p u t e r s c i e n c e c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r ：l i uy u h u a a c a d e m i ct i t l e ：p r o f e s s o r s l g n a t u r e a p p r o v e d m a y , 2 0 1 1 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者张陟晦7 日期：2 卢t l 月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者娩修协 日期：2 矽t f * 占月日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程 ，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程 中的 规定享受相关权益。回童途塞理交卮澄卮! 旦坐生；旦二生；旦三生筮查1 8 - - j , 签名：壶? 日期：弘f ，年 日 穆丫可 a 厂d 冽降 名 弘 獬 沙 师期 争日 硕士学位论文 m a s t e r st h e s i s 中文摘要 在非结构化p 2 p 网络中，节点由于受到内部能力差异、搭便车行为和高扰动 ( h i g hc h u m ) 特性的影响，负载度呈现出严重的失衡，对网络的健壮性和可用性形 成了严重的影响，同时也造成了网络资源的巨大浪费。因此，如何遏制网络节点负 载度失衡是一个迫切需要解决的问题。本文在当前国内外研究的基础上，首先将造 成网络节点负载度失衡的因素定性为两类：节点内部因素( 即节点内部能力差异) 与节点外部因素( 即搭便车行为与h i g hc h u m ) ，然后提出相应的解决机制，依次 为： 针对网络节点间的能力差异，本文提出了一种基于虚节点的均衡控制算法，算 法中允许节点通过“划分 和“整合”操作，让重载节点的剩余负载能向相邻节点 转移。通过大量的模拟实验显示，基于虚节点的均衡算法使得网络中节点负载更加 紧凑，网络负载方差得到较大幅度的下降，重载节点数也保持相对平稳； 网络h i g hc h u m 特性会引起网络分割问题，经过大量的路由查询与转发操作 后，网络分割点承载着巨大的负载压力，最终演变成网络“热点( 或集散节点) ， 进而使得网络中的普通节点与“热 点存在巨大的负载差异。基于此，考虑到非结 构化p 2 p 网络的路由特性，本文提出了如何检测与避免集散节点的相关机制。最后 通过模拟实验显示，在相同的m 下，p 2 p 网络经过一次避免算法后，网络中的集 散节点数得到了大幅度地减少； 最后，针对综合因素( 同时包含内外因素) 下的节点负载失衡问题，本文提出 了一种基于节点负载度与逻辑链路迁移的控制算法，首先在每个节点所拥有的文件 中，为流行度较高的文件建立二叉树备份节点表，然后根据备份节点表选择负载转 移节点。最后的仿真模拟显示，在无c h u m 以及不同c h u r nr a t e 的情况下，该算法在 均衡节点负载方面都具有明显优势。 关键词：p 2 p 网络；负载均衡；虚节点；网络分割；高扰动 a b s t r a c t i nu n s t r u c t u r e dp e e r - t o p e e rn e t w o r k ，w i t ht h ei n f l u e n c eo fi n t e r n a la b i l i t yd i f f e r e n c e b e t w e e nn o d e s ，f r e e r i d i n gb e h a v i o ra n dh i g hc h u mi np e e r - t o p e e rn e t w o r k ，s e r i o u sl o a d u n b a l a n c eb e t w e e nn o d e sh a se x t e n d e de n o r m o u si n f l u e n c eo v e rr o b u s t n e s sa n du s a b i l i t y o fn e t w o r k a n da l s oc a u s e sg r e a tr e s o u r c ew a s t e t h e r e f o r e ，h o wt oc o n t r o ln o d el o a d u n b a l a n c ei sa nu r g e n tp r o b l e mt os o l v e i nt h i st h e s i s ，o nt h eb a s i so fc u r r e n tr e s e a r c ha t h o m ea n da b r o a d f i r s t l yf a c t o r si nc a u s i n gn o d el o a du n b a l a n c ea r ec h a r a c t e r i z e di n t o t w ot y p e s ：n o d ei n t e r n a lf a c t o r ( t h a ti si n t e r n a la b i l i t yd i f f e r e n c eb e t w e e nn o d e s ) a n dn o d e e x t e r n a lf a c t o r ( t h a ti n c l u d e sf r e e r i d i n gb e h a v i o ra n dh i g hc h u m ) ，t h e nc o r r e s p o n d i n g a l g o r i t h mm e c h a n i s mi sp r o p o s e d ，t h e r ea r e ： a b o u tn o d ea b i l i t yd i f f e r e n c eb e t w e e nn o d e si nt h en e t w o r k ，t h et h e s i sp r o p o s e sa b a l a n c ec o n t r o la l g o r i t h mb a s e do nv i s u a l n o d e ，i nt h ea l g o r i t h m ，n o d ec a nc h o o s ed i v i d e o rm e r g e ro p e r a t i o n ，r e m n a n tl o a di nh e a v yl o a dn o d e sc a ns h i f tt o w a r d st h e i rn e i g h b o r n o d e s l o t so fs i m u l a t e de x p e r i m e n t ss h o w , t h ev i r t u a l n o d ea l g o r i t h mm a k en o d e1 0 a d m o r et i g h t e rf r o md i f f e r e n tn o d e s ，t h en e t w o r kl o a dv a r i a n c ed r o p ss h a r p l y , a n dt h e n u m b e ro fh e a v y 1 0 a dn o d ek e e p sr e l a t i v e l ys t e a d y h i g hc h u mi nn e t w o r kc a np r o d u c et h ep r o b l e mo fn e t w o r kp a r t i t i o n ，e s p e c i a l l ya f t e r l o t so fr o u t eq u e r ya n df o r w a r do p e r a t i o n s 。p a r t i t i o nn o d ei nn e t w o r kw i l lw i t h s t a n d i m m e n s el o a dp r e s s u r ea n dd e v e l o p si n t o “h o t n o d e ( o rh u b ) ，t h e nr e s u l t si nb i g d i f f e r e n c ei nl o a db e t w e e nc o m m o nn o d e sa n dh o tn o d e s b a s e do ni t c o n s i d e r i n gr o u t e c h a r a c t e r i s t i ci n p e e r - t o - p e e rn e t w o r k ，t h et h e s i sp r o p o s e sc o r r e s p o n d i n gm e c h a n i s m a b o u th o wt od e t e c ta n da v o i dh u b s t h es i m u l a t e de x p e r i m e n t ss h o w , i nt h es a m e 玎【， a f t e re x e c u t i n gt h ea v o i d a n c ea l g o r i t h mo n c e ，t h en u m b e ro fh u b si nt h ep e e r - t o p e e r n e t w o r ki sd e c r e a s i n gs h a r p l y i nt h ee n d ，f o rt h ep u r p o s eo fs o l v i n gt h en o d el o a du n b a l a n c ei nc o m p o s i t e f a c t o r s ( i n c l u d i n gi n t e r n a la n de x t e r n a lf a c t o r s ) ，t h et h e s i sp r o p o s e sac o n t r o la l g o r i t h m w h i c hi sb a s e do nn o d el o a da n dl o g i c a l1 i n km i g r a t i o n f i r s t e a c hn o d em u s tc r e a t e b i n a r yb a c k u pn o d et a b l e sf o rs h a r e dh i g hp o p u l a r i t yf i l e s ，t h e na c c o r d i n gt oi t ，c h o o s e s t h ep r o p e rl o a ds h i f tn o d e s t h es i m u l a t i o ne x p e r i m e n ts h o w s w h e nt h e r ea r en oc h u m o ri nd i f f e r e n tc h u mr a t e t h ea l g o r i t h ma l s oh a so b v i o u sa d v a n t a g e s k e yw o r d s ：p 2 pn e t w o r k ；l o a db a l a n c e ；v i r t u a ln o d e ；n e t w o r kp a r t i t i o n ；h i g hc h u m u 硕士学位论文 m a s t e r st t l e s i s 目录 中文摘要i a b s t r a c t i i 第l 章绪论1 1 1p 2 p 网络简介l 1 2p 2 p 网络中节点负载均衡问题2 1 3国内外研究现状3 1 4本文的主要内容及组织安排8 第2 章基于节点内部因素的p 2 p 网络负载均衡研究。1 0 2 1内部因素对网络节点负载分布影响1 0 2 2基于内部因素的负载均衡机制研究1 1 2 2 1节点差异下负载均衡模型。11 2 2 2基于虚节点的负载均衡算法机制的设计与实现1 2 2 3仿真与性能评估1 3 2 3 1仿真环境与参数说明1 3 2 3 2 性能指标1 4 2 3 3实验结果1 4 2 4本章小结。1 7 第3 章基于节点外部因素的p 2 p 网络负载均衡研究1 8 3 1外部因素对网络节点负载分布影响1 8 3 2基于外部因素的节点负载均衡机制研究1 9 3 2 1集散节点的概念1 9 3 2 2集散节点的检查2 1 3 2 3集散节点避免机制的实现一2 2 3 3仿真与性能评估2 4 3 3 1仿真环境与参数说明2 4 3 3 2性能指标2 4 3 3 3实验结果2 5 硕士学位论文 m a s t e r st h e s i s 3 4本章小结2 7 第4 章基于节点综合因素的p 2 p 网络负载均衡算法研究2 8 4 1综合因素下负载均衡控制模型2 8 4 2基于节点负载与逻辑链路迁移的均衡控制算法2 9 4 2 1文件流行度与二叉树备份节点表2 9 4 2 2 逻辑链路迁移算法3 0 4 2 3算法分析3l 4 3仿真与性能评估3 1 4 3 1仿真环境与参数说明一3 l 4 3 2性能指标3 2 4 3 3 实验结果3 3 4 4本章小结3 7 第5 章总结与展望。3 8 参考文献4 0 在校期间所参与项目和发表的论文4 4 j 变谢4 5 硕士学位论文 m a s t e r st h e s i s 1 1p 2 p 网络简介 第1 章绪论 在传统的互联网应用模式c s ( c l i e n t s e r v e r ) 下，随着网络中个人计算机数量 的剧增，极易引起单点失效，对系统的可靠性造成严重影响；同时，网络边缘节点 却存在大量的空闲资源，造成了网络负载的分布不均以及资源的浪费，基于此，一 种新型的应用模式即p 2 p 模式应运而成。 目前对p 2 p 比较权威的定义是，“p 2 p 是一种能够充分利用那些分布在i n t e m e t 边缘的存储、计算、信息和人力资源的应用模式，因为访问这些分布式资源是在不 稳定连接状态和动态i p 地址的情况下进行的，p 2 p 节点必须异于d n s 系统寻址并 有相当或者完全的自治性。 【l 】对比c s ，p 2 p 网络中的节点充当客户机和服务器 双重角色，允许任何节点间进行对等互联，中间不需要经过服务器，这样一方面能 够充分发掘网络中节点潜力，提高了网络系统的吞吐量，另一方面，p 2 p 网络具有 极高的可扩展性，因为随着网络规模的扩大，整个p 2 p 网络不需要额外添加网络设 备，这些优点是传统的模式所不具备的。综上所述，p 2 p 网络大致在以下几个方面 的特征： ( 1 ) 对等性( p e e r ) 网络节点充当客户机和服务器双重角色，所体现出的功能 和职能均是对等的； ( 2 ) 自治性( a u t o n o m y ) 网络中节点在处理内部与外部事务时具有很高的自 治度，几乎不受外部影响。 ( 3 ) 扰动- i 生( c h u m ) 基于网络的高自治性，网络节点能够随意加入或离开 p 2 p 系统，造成与节点相关的服务甚至整个系统的规模和结构均会受到影响。 ( 4 ) 规模大( h i g hs c a l e ) p 2 p 系统形成的规模是巨大的，特别是针对一些热 门应用，如p 2 p 直播或点播业务的平均在线用户数达到百万级。 ( 5 ) 无集中控错l j ( c e n t r e 1 e s s ) 有别于传统的c s 模式，p 2 p 网络基本上是一 种彻底的分布式系统，系统的功能只能是依靠网络节点间的协作才能完成。 根据p 2 p 的发展历程以及拓扑关系可以将p 2 p 系统进行划分，如图1 1 。非结 构化p 2 p 系统又包括集中式和完全分布式，代表是n a p s t e r 拉】和g n u t e l l a t 引，其中 n a p s t e r 可看成是p 2 p 应用的鼻祖，它包含一个集中式的目录服务器。目录服务器 硕士学位论文 m a s t e r st i i e s i s 存放着网络节点的地址信息和所要共享的数据信息，通过对来自于节点的请求作出 查找响应并返回最适合的节点，待请求节点与目的节点间建立t c p 连接后，文件传 输就可以在它们之间直接进行，因此，n a p s t e r 首先将文件查询与文件传输进行分离， 这样不仅提高了系统的吞吐量，同时缓解了单点失效的问题。g n u t e l l a 则采用了完 全分布式策略，因此它几乎不存在单点失效问题，可扩展性好，但是在定位效率方 面不如前者。为了兼有完全分布式非结构化网络的高扩展性以及目录服务机制的查 询效率，结构化p 2 p 系统出现了，它能将系统中每个资源定位在确定的节点上，并 提供资源i d 与资源所在节点位置的映射关系，这样保证了每个资源的精确查找在 有限步内完成。目前，大部分结构化p 2 p 系统都是基于分布式h a s h 表，如c h o r d l 4 j 、 t a p e s t r y 5 1 、p a s t r y l 6 】等。 图l - 1p 2 p 系统分类示意图 本文主要以非结构化p 2 p 网络为研究对象，从节点差异、搭便车行为以及h i 曲 c h u m 特性三个方面研究网络节点负载均衡问题。 1 2p 2 p 网络中节点负载均衡问题 在非结构p 2 p 网络中，各节点主要是通过文件的共享连接来承载网络负载的， 倘若网络中每个节点在网络中的状态均能保持稳定，且能主动参与文件贡献，积极 地接收并处理来自于其他节点的文件查询请求，同时网络中文件资源在地理位置上 均匀分布( 某个文件资源在整个网络中存在多个副本) ，这样网络中各节点的负载 分布会十分均衡，同时网络系统的吞吐量、稳定性以及可靠性也会达到最佳性能。 然而，在实际网络中，一切并非如此，网络中存在严重的不均衡性，其原因可以从 节点的内部和外部因素两个方面进行说明： ( 1 ) 内部因素：节点差异是影响网络节点负载失衡最重要的内部因素。节点的 能力，如处理能力、存储能力、带宽等均存在，节点所共享的文件在数量，特别是 2 硕士学位论文 m a s t e r st h e s i s 文件流行度方面存在着数量级的差异，这样势必会影响到网络用户的查询行为，已 有研究发现，p 2 p 系统中的查询分布特征类似于h 1 v r p 请求分布，均服从于z i p f 分 布定律【7 1 ，因此对于那些拥有流行度极高文件( 或“热门”文件) 而自身能力反而 偏低的节点将承受着巨大的负载压力，它类似于传统应用模式下的s e r v e r 节点，最 终可能会导致失效。 ( 2 ) 外部因素：高扰动( h i g hc h u r n ) 和搭便车行为是造成节点失衡的两大外 部因素【8 】。首先，基于节点的高自治性，p 2 p 网络呈现一个高动态状态，节点可以 自主地选择加入和离开网络，如果过多的承载热点文件的关键节点离开网络，将会 对文件查询的成功率、网络可靠性和可扩展性均将产生不良影响。另外，网络中存 在大量自私行为节点( 或“搭便车 节剧9 】【1 0 】) ，它们没有共享文件或者共享极少， 或者是共享一些极为冷门的文件，它们的加入只是想从p 2 p 网络中掘取由其他节点 提供的服务，而不乐意为网络做贡献。这样，会导致节点负载出现严重的两极化， 对网络健壮性、可用性方面都将造成负面影响。 从上面的分析中可以看到，影响节点负载是来自于多方面的，既有节点自身在 能力方面的差异，也有来自于节点自私行为和高动态环境下产生的外部因素，因此， 在考虑平衡节点间负载差异时，一定要综合这三方面的因素加以解决。 1 3 国内外研究现状 针对p 2 p 网络中节点负载失衡问题，主要的解决方法是分别从节点内部和外 部因素出发对节点负载失衡加以抑制，达到系统整体均衡的目的。概括起来如下： ( 1 ) 节点差异 基于节点之间差异来解决节点失衡问题的方法主要有：依据可用能力或者随机 调度的负载均衡算法。若想依据节点可用能力将查询请求分配给可用处理能力最大 的节点，首先如何探测到节点具有这种处理能力，这在无中心和高动态化的p 2 p 网 络中是很难办到的。b e v e r l y 1 l 】等人提出了在p 2 p 网络中选出一些处理能力强的节点 作为超级节点，并负责探测节点处理能力并代理其他节点的路由请求，但这种方法 容易在超级节点上形成负载过度集中。另外，m i t z e n m a c h e r l l 2 1 等人依据所设定的阈 值将服务器分为轻载服务器和重载服务器，并将任务分配给轻载服务器，但这种方 法比较适合于局域性的分布式系统，对广域式p 2 p 网络的效果有限。对于针对随机 调度的负载均衡算法，f o n l u p tc 【1 3 】等人通过随机选出若干节点并同时发出状态查询 请求，然后再在这些备选节点间集中进行任务分配。在文献 1 2 】中，通过排队模型 硕士学位论文 m a s t e r st h e s i s 对随机采样的稳定性进行了分析，最后发现当采样的规模在大于2 时算法是收敛的， 但是基于随机调度算法在一定程度上存在盲目性，并不能使那些严重负载节点的负 载压力及时得到缓解。 ( 2 ) h i g hc h u m h i g hc h u m 对p 2 p 网络的连通性( 即p 2 p 网络中任意两个节点间的通路情况) 和文件查找性能( 主要表现在平均查找距离和查找成功率) 均产生了重大影响。目 前国内外主要是在p 2 p 网络的不同层中采取相应的方法去减低c h u m 对网络的不良 影响，如在数据层采取增加数据冗余的方法，在路由层则是采取路由维护策略，而 在节点层采用灵活的节点选择方法等。 1 ) 数据冗余策略 数据冗余是一种为了防止因h i g hc h u m 而导致数据丢失采取的补救措施，目前 已经成功运用于一些p 2 p 数据存储系统中，如c f s 14 1 、o c e a n s t o r e t l 5 1 等，因为存储 系统中均需要对节点进行认证管理，因此系统中的节点相对比较稳定，也较容易部 署，但是如果是在高动态的文件共享系统中，数据冗余策略的部署就显得极为困难， 同时必须考虑到，系统中文件的可用性依赖于文件的流行度，流行度高的文件可能 在网络中有多个副本，而流行度低的文件却仅仅为少数几个节点所拥有。田敬【1 6 j 等人提出了采用副本和纠删码两种冗余方法，其中将系统中小文件和访问频繁的文 件冗余在多个节点中，纠删码方法则是将存储的数据划分成m 个部分，再通过编码 方法生成n 个部分( n m ) ，使用其中任意的，p 所) 个部分，通过解码算法就能还原 数据。c o h e ne t l7 】等人为非结构化p 2 p 文件系统建立线性规划模型，其中： 目标函数：e s s 。( ，) = m i n k - - - 2 q 2 p7 7 _ - 约束条件：尺= r t 和q j = l j =j = 模型假设每个节点的容量并且文件被分发的到各个节点的概率均是相等的， e s s 即平均查找距离，作为c h u m 衡量指标，m 为网络中不同文件的个数，：为文 件i 的副本数，r 为系统可存储的文件总徼，为每个节点的存储容量，q i 则为文件 i 被查询的概率。求解后得到，当，；= r 虿芝虿时， 最小平均查找距离可以达到 。 21,-v 【善g fj 细，不过很难通过实际部署去达到理论最佳值，另外还探讨了利用该模型 去进行均匀复制与按比例复制下平均查找距离数量的对比，发现在两种复制策略下 具有同样的e s s ，即，杉。 ，p 2 ) 路由维护策略 4 在结构化p 2 p 网络中，人们习惯采用路由维护策略去减低c h u m 对网络的影响， 而非结构化p 2 p 网络却很少遇到有这方面的问题，因为二者在路由技术上存在巨大 差异，前者采用d h t l l 8 】去找到资源所在的位置，而后者则通常采用f l o o d i n g 1 9 】去 进行路由查找。针对d h t 网络路由的优化主要集中在对路由器的大小和路由表的 更新。其中，路由器的大小对平均查找距离会产生巨大影响。l ij 2 0 1 等人提出节点 应该根据d h t 网络运行情况动态调整路由器的大小，在运行良好的情况下，可适 当增大路由表的大小，而在运行状态较差的情况下则将路由表大小减少至o ( 1 0 9 ，) ( 其中n 是节点数目) 。路由器更新的时长与内容对查找时延影响是挺大的，在d h t 协议的具体设计过程中，c h o r d 则采取了周期性检查邻居节点的有效性以及更新路 由器表中无用的节点，而k a d e m l i a 则是采取触发方式更新节点路由器中的内容， 即当发现自身邻居节点不可达时立即更新其所对应的信息，r h e as | 2 1 1 等人在 b a m b o o 协议上实验得出，周期更新在带宽消耗与查找延时性能指标方面要优于触 发式更新。 3 ) 节点选择策略 类似于在节点差异因素下某些文献中所采取的方法，常将节点选择策略分成两 类：随机性选择和确定性选择，其中随机性选择就是在不考虑任何节点特征的前提 下选取节点子集，而确定性选择则是按照节点的某些特征来对节点进行选择，如根 据节点当前的在线时长、邻近节点的地理位置等。由于节点当前在线时长对未来的 剩余时长有一定的预见性，因此通常选取当前在线时长策略用于对d h t 网络中邻 近节点2 2 1 、超级节点【2 3 】的选取。 ( 3 ) 搭便车行为 节点“搭便车行为【2 4 1 降低了p 2 p 网络系统的性能，增加了系统的脆弱性，若 任由搭便车现象发展将可能会导致p 2 p 应用系统的崩溃。自从2 0 0 0 年由a d a r 等人 发现p 2 p 网络中存在搭便车行为以来，研究者提出了一系列的搭便车行为抑制机制， 大体上可分为基于节点行为的激励机制、基于博弈论的方法、采用社会网络或经济 模型的控制策略三类。 1 ) 激励机制 激励机制例【2 6 】【2 7 1 是最早用于抑制节点搭便车行为的方法，不同激励机制之间的 主要差异在于所选取的效用函数、测量点选择等方面。图1 2 给出了利用激励机制 来限制节点搭便车行为的一般流程： 硕士学位论文 m a s t e r st h e s i s s t e p1 提出一个效用函数； s t e p2 每个节点周期性地或者触发式地计算节点的效用值； s t e p3 节点发起数据查询或者下载业务； s t e p4 若某时刻节点的效应函数值偏高，则允许下载服务，下载完成后转向 s t e p 6 ： s t e p5若节点效用函数值偏低，则拒绝下载服务，转向s t e p7 ； s t e p6 节点重新计算自身效应函数值； s t e p7 系统等待事件触发，有服务请求则转s t e p3 ；若节点为其他节点提 供服务，则跳步转向s t e o6 图1 2 激励机制算法一般流程 至于测量点位置的选择问题，目前存在两种方法：( 1 ) 节点自身做自我测量， 评价节点在网络中的贡献；( 2 ) 每个节点对邻居节点进行测量和监督，各节点的贡 献值大小的计算由邻居节点来计算。其中第一种方法在实际中较容易实现，且计算 开销小，然而不排除网络内少量恶意节点虚报自己提供的信息服务次数而获得较高 的效用函数值，而后者却能很好地抑制这种现象。基于上面这两种方法，可将激励 机制划分成基于节点自身测量的激励机制和分布式测量机制两类。在基于节点自身 测量的机制中，r a m a s w a m yl 【2 8 】等人提出了一个较完备的基于节点效应函数值的概 念，内容主要涉及以下自变量：节点共享文件的数量、节点已下载的文件数量、节 点己上传的文件数量、节点已上传的文件大小以及节点已下载的文件大小等，并提 出了3 个有代表行的效用函数： u ( 霉，7 ) = o r v 1 i s t ( 只，乃i 式( 1 1 ) 中左端表示在t 时刻，节点i 的效用函数值。右端的u l i s t ( p , ，r ) 则表 示在t 时刻，节点i 所提供的共享文件数，其中口为一个调节常量系数。从( 1 1 ) 式可以看出，节点所享用的服务质量则与它所共享的文件数量成正比。 u ( 只，t ) = f 1 s i z e ( f ) ( 1 - 2 ) v 弓e l m ( p s 。r ) 式( 1 2 ) 则是从所共享的文件大小角度来计算节点效用函数值，因此式子先将 节点所共享的所有文件大小求和。口则是一个规范化系数，对比这两个式子发现， 式子( 1 1 ) 有利于共享多个小文件的节点将会收到好的服务质量，而式( 1 - 2 ) 则 有利于共享大文件的节点。但是从式( 1 1 ) ( 1 2 ) 可以看到，式子仅仅强调了所共 享文件的数量和大小，却没有很好地反映节点所共享的文件被其他节点的使用情 况，因此这样很难避免网络中的搭便车行为。 6 硕士学位论文 m a s t e r st h e s i s u ( 只，7 ) = r ( k + d c o u n t ( f j ，r ) ) z i z e ( f j ) - s i z e ( f , ) ( 1 - 3 ) v e n 盯( b ，7 ) v 巧6 d l 盯( b r ) 式( 1 - 3 ) 则不仅考虑到节点所共享文件的大小，同时还考虑到了其所共享文件 在网络中的流行程度，其中y ( k + d c o u n t ( f j ，7 1 ) ) s i z e ( g ) 表示节点i 在t 时刻的 奖励值，里面包括节点为其他节点提供下载的数据文件大小之和，坼。扁n 妣p 【q ) 表示节点i 在时刻t 的惩罚值，并且惩罚值的大小与节点已下载数据量大小成正比。 但在式( 1 - 3 ) 较合理地反映出节点效用值的同时，也难免会增加计算复杂度，由此 也可以看到在设计效用函数的过程中，合理性与计算复杂度是一对很难调和的矛 盾。另外还要注意网络系统的用户数量，因为对于一个对等网络运营者来说，用户 数量才是他们盈利的根本，因此，在设计效用函数时不能对搭便车行为节点实施过 于严厉的措施，或者在设计效用函数时，为搭便车节点的某个特征实施奖励，即免 费赠品，例如根据节点的在线时间长赋予相应的服务等级权利，免费赠品的实现比 较简单，只需将节点的在线时间作为一个自变量加入到原效用函数中。 文献【2 9 】【3 0 】认为不应该仅仅根据节点的绝对贡献值来评价节点所做的贡献，还 应考虑到节点所在的网络带宽情况，于是将节点的效用函数值表示为节点服务贡献 值与节点所能提供的最大带宽之比，这样对那些虽然在物理上贡献能力较低，却尽 力做了巨大贡献的节点比较公平。 在分布式测量机制下，文献【3 1 】提出一种严厉的搭便车行为激励机制，首先每 个节点负责观察其邻居节点的发送、转发数据报行为，再根据形成的日志记录计算 效用函数值来判断搭便车者，最后采取强制手段驱使节点为系统提供服务，否则将 其从系统中剔除。文中还提出了节点曰志记录的生成方法，即p 2 p 网络中的每个节 点只需对通过自身转发的报文做记录就可以了，如当节点收到每个报文时，要记录 下这个报文是来自于哪个节点，并转向哪个节点，然后定期统计与之相邻节点是问 系统做贡献的报文数量多还是从系统中得到的服务多，最后根据这个统计记录将搭 便车节点分成三类：( 1 ) 发出查询响应报文次数较少的节点，这种节点属于那种提供 共享文件资源较少或者提供了一些流行度极低的节点；( 2 ) 从其他节点所获得的资 源数量远大于它向其它节点所提供服务的报文数；( 3 ) 转发信令较少的节点，这类 节点几乎不承担网络路由维护义务。 2 ) 博弈论方法 博弈论是分析社会群体、经济活动中个体或者群体选择最优行为的有效数学工 具，对等网络中节点的行为可看成是长期博弈的过程，节点可以在为系统做贡献、 贪婪索取服务等多种行为中找到有利于节点最大化利益的策略选择。文献【3 2 】借助 7 硕士学位论文 m a s t e r st h e s i s 博弈论工具对节点行为进行了分析，文中假设节点在任一时间段内都会发出服务请 求，并且每个节点的行为集合仅包括提供服务和不提供服务两种，每个节点的偏好 期望值主要与收益u 和服务成本c 相关，并且节点i 在任一时刻t 的支付函数计算 与节点信誉度息息相关，信誉度的计算方法如下式子： 碍= 碍一i ( 1 一o r ) + o ) o t ，0 口1 ，t 2 ( 1 4 ) 式中若在t 时刻节点提供服务，则缈为l ，否则为0 ，口是一个o 1 之间的非负 实数。另外还规定民为0 ，r 为6 0 。最后在混合式策略下计算得到节点选择服务的 概率p 为： p 一 墨= ! 竺! ! 二竺! ( 1 5 ) - c + 2 r l u ( i - a ) + u a 3 ) 社会网络和经济模型 p 2 p 网络中节点搭便车行为可看成是节点用户社会心理的一种延伸。k r i s h n a nr 等人在文献【3 3 通过社会网络模型对p 2 p 网络中的节点行为进行建模分析，认为搭 便车现象也是提高网络资源利用效率的一种有效方式，只要网络中的搭便车现象不 是太严重，就不应该进行抑制。文献 3 4 】中运用市场机制模型对搭便车节点行为进 行分析，该文认为采用分布式抑制机制是个趋势，并集中讨论了采用市场机制来处 理搭便车行为的实现方法，最后提出了一种基于代理的资源管理框架和策略。文献 【3 5 】中提出了一种基于市场竞争机制下的抑制模型，并基于节点若不为其它节点提 供转发服务，也就不会向别的节点提供路由服务的假设，提出了有关转发报文的服 务费用，若节点向其它节点提供了转发服务，就可以获得一定的经济补偿，反之， 若节点从其它节点获得了信息服务，则会需要支出掉部分经济补偿，这样才能迫使 网络节点积极向其它节点提供信息服务。 1 4 本文的主要内容及组织安排 因为节点内外因素的存在，网络中节点负载出现了严重失衡，本文致力于如何 在节点内外因素的基础上解决网络中节点负载失衡问题，以保证p 2 p 网络系统的可 用性、扩展性和健壮性。 分别对应于节点的内外因素，本文提出了对应的基于虚节点的负载均衡控制算 法以及基于网络内部拓扑的控制算法，即集中于网络中集散节点的检测和消除；最 后提出了一种综合因素下节点负载控制算法。 8 硕士学位论文 m a s t e r s 丁h e s i s 本文首先分析了如今p 2 p 网络中基于节点自身差异性、h i g hc h u m 以及搭便车 行为分别对p 2 p 网络造成的影响，然后总结了国内外相关的研究现状，最后基于节 点自身差异性提出了虚节点控制算法，基于节点外部因素下的网络拓扑节点调整控 制算法，基于节点综合因素下的控制机制。 本文的章节安排如下： 第1 章绪论。主要介绍了p 2 p 网络的定义、特点以及相关应用领域，然后分 析了影响了节点负载失衡的内外因素并总结了国内外相关的研究现状； 第2 章p 2 p 网络节点内部因素下负载均衡机制研究，主要详细阐述了节点内部 因素即节点差异性给p 2 p 网络系统在节点负载方面的负面影响，并提出了一种基于 虚节点的负载均衡控制算法； 第3 章p 2 p 网络节点外部因素下负载均衡机制研究，本章主要分析了在搭便车 行为和h i g hc h u r n 两个外部因素下对节点负载失衡造成的影响，对于h i g hc h u m 因造成网络分割点而造成的失衡问题，本章提出了描述分割点集散节点的定 义，以及如何响应的如何检测和避免集散节点的算法。 第4 章p 2 p 网络节点综合因素下负载均衡机制研究，本章主要提出了一种基于 拓扑控制的负载均衡控制算法，主要包括如何为集散节点建立二叉备份节点表以及 逻辑链路迁移算法的设计等工作。 第5 章结论。本章对前面有关平衡p 2 p 网络节点负载算法思想进行总结，并 提出以后需要进一步研究的内容。 9 硕士学位论文 m a s t e r st h e s i s 第2 章基于节点内部因素的p 2 p 网络负载均衡研究 2 1 内部因素对网络节点负载分布影响 节点差异是影响网络节点负载失衡最重要的内部因素，它主要体现在节点能力 值、地理位置和兴趣上。对于节点能力，经常出现节点处理能力弱的节点却承担着 较大的负载问题，从而形成网络热点，使得p 2 p 系统部分退化成c s 结构，对p 2 p 网络的可用性和可靠性造成了不利影响。 在大部分p 2 p 网络路由算法中，节点或者资源的路由查找通常是由节点间组成 的覆盖网决定的，而不是物理网络，而p 2 p 网络路由效率却是由端间的时延所决定 的，由于节点在地理上是分布的，因此可能在查找资源时出现在覆盖网络上的最优 路由与实际最优性能不一致，这是p 2 p 逻辑覆盖网络与物理网络不一致造成的( 如 图2 1 ，图2 2 ) 。 图2 1c h o r d 路由的逻辑覆盖网络图2 2 物理网络 至于节点兴趣上的差异性，主要跟节点所共享的资源的流行度相关，也就是说， 对于不同流行度的资源，节点所表现出的兴趣也是截然不同的，它对节点负载的影 响将会在第三章中介绍，本章主要介绍节点负载在节点能力差异下的均衡算法机 制。 另外，节点能力值的度量因素也是多样的，文献 3 6 y l j 举出了6 个可能体现节 点异构性的因素：节点本地查询能力、节点维持稳定性的能力、节点维持连通性的 能力、节点的存储能力以及节点处理信息的能力，文献 3 7 贝j j 从c p u 计算能力、主 存