（计算机软件与理论专业论文）无结构对等网络激励机制研究.pdf

摘要 当今因特网应用中出现了越来越多的基于对等网络协议开发的应用软件，其网络结 构一般分为结构化和无结构化两大类，其中无结构对等网络因其本身具有自治性、无组 织、去中心化等特点而倍受关注。本文的研究对象是无结构对等网络系统中广泛存在的 搭便车问题。在充分研究近年来国内外已有的多种激励机制模型后，我们发现现有的 p 2 p ( p e e r - t o p e e r ) 应用软件的运营模式与已经提出的众多策略下的激励机制之间存在 不一致性。激励机制主要关注的是如何通过奖励协作节点、抑制搭便车节点来维护整个 网络系统的公平公正性，而p 2 p 网络运营商的主要收入是来自在网络社区内广告的投放 量，因此为了吸引更多的用户加入p 2 p 网络并长时间留在网络社区中，运营商往往对搭 便车节点采取了忽视和容忍的态度。 针对上述问题，本文借鉴了分布式测量和博弈论中的纳什均衡理论，提出d a m r ( d i s t r i b u t e da l g o r i t h ma n t i - f r e e d d c rb a s e do nm e s s a g er o u t i n g ) 算法，该算法分布式地 检测和抑制搭便车节点。在此算法的基础上，考虑节点自身的网络负载，设计了一个基 于d a m r 策略的激励机制。为了更好地分析本文提出的激励机制的特点、性能、对p 2 p 网络系统的影响及其是否符合p 2 p 网络运营商的商业期望，通过数学化建模的方法，提 出一个无结构p 2 p 网络系统激励机制的数学评估模型，并利用该模型分析论证了基于 d a m r 策略的激励机制能够使p 2 p 网络系统处于一种良性的均衡状态。最后通过扩展 c m u t d l a s i m 软件，将该激励机制添加到以n s 2 为平台的仿真系统中，通过实验和数据 分析，验证了基于d a m r 策略的激励机制的正确性和有效性。利用该激励机制，在符 合p 2 p 网络运营商利益的前提下，可以提高网络的利用率，促进p e e r 节点参与协作和 享用服务，使p 2 p 网络社区更具有吸引力。本文的研究对促进p 2 p 网络系统的良性发展 具有一定的启示意义。 关键词：对等网络，无结构，激励机制，数学模型 a b s t r a c t m o r ea n dm o r ea p p l i c a t i o n sb a s e do np e e r - t o - p e e rp r o t o c o ls p r i n gu po nt h ei n t e r n e t ， m e i rn e t w o r ks t r u c t u r e sa r et w om a i nc a t e g o r i e s ：s t r u c t u r a ln e t w o r k sa n du n s t r u c t u r e d n e t w o r k s ，p e o p l ep u tm o r ea t t e n t i o nt ot h eu n s t r u c t u r e dp e e r - t o p e e r ( p 2 p ) n e t w o r k sb e c a u s e t h e ya r ea u t o n o m o u s ，u n s t r u c t u r e da n dd e c e n t r a l i z e d t h er e s e a r c ho b j e c to ft h ep a p e ri st h e f r e e - r i d i n gp r o b l e mw h i c hw i d e l ye x i s t si nt h eu n s t r u c t u r e dp 2 pn e t w o r k s o nt h eb a s i so f s t u d yo nt h ec l a s s i c a li n c e n t i v em e c h a n i s m sp r o p o s e di nr e c e n ty e a r s ，w ef i n dt h a tt h e r ei sa c o n f l i c tb e t w e e nt h eo p e r a t i n gm o d eo nw h i c hm o s tp 2 p a p p l i c a t i o n sa r ec u r r e n t l yr u n n i n g a n dt h ea i mo ft h e p r o p o s e di n c e n t i v em e c h a n i s m s t h ep r o p o s e di n c e n t i v em e c h a n i s m sf o c u s m a i n l yo nh o w t or e w a r dc o o p e r a t i v en o d e sp u n i s ht h ef r e er i d e r ss oa st om a k et h ee n t i r e n e t w o r kb e j u s t i c ea n de q u i t a b l e h o w e v e r , m a i ni n c o m eo fp 2 pn e t w o r ko p e r a t o rc o m e sf r o m a d v e r t i s e m e n t si nt h en e t w o r kc o m m u n i t y , s oi no r d e rt oa t t r a c tm o r eu s e r st oj o i nt h en e t w o r k a n ds t a yi nn e t w o r kf o ral o n gt i m e , o p e r a t o r st e n dt ot a k et h ea t t i t u d eo fn e g l e c t i n ga n d t o l e r a n c et of r e e - r i d e r s a i m i n ga tt h ep r o b l e m ，t h r o u g hd r a w i n go nt h ed i s t r i b u t e dm e a s u r e m e n ta n dt h en a s h e q u i l i b r i u mi ng a m et h e o r y , ad a m r ( d i s t r i b u t e da l g o r i t h ma n t i - f r e e - r i d e rb a s e do nm e s s a g e r o u t i n g ) a l g o r i t h mi sp r o p o s e di nt h ep a p e r 。t h i sa l g o r i t h md e t e c t sa n dd i s c o u r a g et h e f r e e - r i d e r sd i s t r i b u t i v e l y 。o nt h eb a s i so ft h ed a m r a l g o r i t h m ，a ni n c e n t i v em e c h a n i s mi s d e s i g r e db yt a k i n g t h en o d e sn e t w o r kl o a di n t oa c c o u n t i no r d e rt o a n a l y z et h e c h a r a c t e r i s t i c sa n dp e r f o r m a n c eo ft h ei n c e n t i v em e c h a n i s mp r o p o s e di nt h i sp a p e rb e t t e r , a n d t oa n a l y z et h ei n f l u e n c eo ft h ei n c e n t i v em e c h a n i s mt op 2 pn e t w o r ka n do p e r a t o r s ，a l l e v a l u a t i o nm o d e li sp r o p o s e d m a k i n gu s eo ft h i sm a t h e m a t i c a lm o d e l ，w ee v a l u a t et h e d a m ri n c e n t i v em e c h a n i s ma n dd r a wt h ec o n c l u s i o nt h a tt h ei n c e n t i v em e c h a n i s mc a nm a k e p 2 p n e t w o r ，ks y s t e m t or e a c ha n dk e e pa p o s i t i v ee q u i l i b r i u m a tt h ee n do f t h ep a p e r , t h r o u g h t h ee x p a n s i o no fo n u t e l l a s i ms o f t w a r et oa d dt h ei n c e n t i v em e c h a n i s mt on s 2 ，ap l a t f o r m f o rs i m u l a t i o ni sb u i l tu p t h r o u g hm a k i n gm a n yt i m e so fs i m u l a t i o ne x p e r i m e n t s ，as e r i e so f d a t aa r eg o t b ya n a l y s i so ft h ed a t a , t h ec o r r e c t n e s sa n de f f e c t i v e n e s so ft h ed a m r - b a s c d i n c e n t i v em e c h a n i s ma r ev e r i f i e d s ot h ec o n c l u s i o ni st h a tt h ed a m r - b a s e di n c e n t i v e m e c h a n i s mc a nm a k em o r ee f f i c i e n tu s eo fn e t w o r k , p r o m o t et h en o d e si np 2 pn e t w o r kt o c o l l a b o r a t ea n de n j o ys e r v i c o s ， m a k ep 2 pn e t w o r k sm o r ea t t r a c t i v ei na c c o r d a n c ew i t ht h e i n t e r e s t so fp 2 pn e t w o r ko p e r a t o r s t h er e s e a r c hi nt h ep a p e rm a yh a v es o m ei n s p i r a t i o nt o t h es o u n dd e v e l o p m e n to fp 2 pn e t w o r k s k e yw o r d s ：p 2 p ，u n s t r u c t u r e d ，i n c e n t i v em e c h a n i s m , m a t h e m a t i c a lm o d e l 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被查 阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 同时授权中国科学技术信息研究所等机构将本学位论文收录到中国学位论文 全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：袒指导教师签名： 砷年6 月夕e l 侧 r y lj jl 冲年月7 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包 含其他人已经发表或撰写过的研究成果，也不包含为获得西北大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 年月 日 西北大学硕士学位论文 第一章绪论 本章首先介绍了论文的研究背景和研究现状，然后重点阐明了论文研究的主要目的 和内容，最后介绍了本文的各章节安排。 1 1 课题研究背景 对等网络( p e e r - t o p e e rn e t w o r k ，简称p 2 p 网络) 是分布式系统和计算机网络相结 合的产物。这是一种网络结构的新思想，整个网络结构中不存在中心节点( 或者中心服 务器) ，每一个节点( p e e r ) 大都同时具有服务消费者、服务提供者和信息通讯等三个 方面的功能。这种新的互联网通信模式在网络的应用层上，打破了传统网络的“客户端 朋艮务器 ( c l i e n t s e r v e r ，c s ) 模式和“浏览器i l l 务器( b r o w s e r s e r v e r ，b s ) 模式， 让网络中的所有成员享有“自由、平等、互联”的功能，不再有客户端、服务器端之分， 任何两个网络节点之间都能提供和享用诸如共享文件、传递消息、协同计算等服纠1 】【2 】。 在对等网络中，每个网络节点在行为上是自由的；在功能上是平等的；在连接上是互联 的。节点分布式地自组织成一个整体网络，所以它能够在很大程度上提高网络效率，充 分利用网络带宽，开发每个网络节点自身的潜能。因此p 2 p 网络系统赢得了产业界的广 泛认可和应用。与此同时，p 2 p 网络系统在产业界应用过程中所突显出的相关问题也在 学术界引起了高度的关注。 p 2 p 网络中节点间自由通信、平等交流和分布式互联的特点，使得p 2 p 网络技术 及其应用得到了迅猛的发展，尤其是在文件共享、流媒体直播点播等方面涌现了一批 知名的应用软件和大规模的用户群体及社区。目前，p 2 p 流量已经占到了主干网流量 的6 0 左右。p 2 p 系统依赖参与节点的协作共享资源，绝大多数p 2 p 协议在设计之初 都假定参与节点是协作性的( c o o p e r a t i v e ) 【3 】【4 】。然而，很多研究者观察发现，在已经 实际应用的p 2 p 系统中，节点间存在着严重的搭便车现象( r i c e - r i d i n g ) 。对等网络研 究者对搭便车行为目前尚缺乏形式化定义，但大家普遍认为，从对等网络的角度看， 搭便车就是p 2 p 系统中存在节点用户享用p 2 p 网络资源( 通过搜索、下载或是享用服 务等) 但不做出相应的贡献或是做出的贡献量远远小于其所享用的服务量。也就是说 一个搭便车者( r i c e r i d e r ) 是p 2 p 网络中使用p 2 p 网络服务但对该网络做出的贡献低 于可以接收程度的那些节点用户。在k a z a a 和g n u t e l l a 等知名p 2 p 文件共享系统中 都充斥着大量的搭便车者。就共享文件数目而言，g n u t e l l a 网络中高达2 5 的用户从 第一章绪论 不共享任何文件，7 的用户所共享的文件数超过了其余9 3 的用户所共享文件数目的 总和，并且在网络中，5 0 的查询响应是从1 的节点返回的 5 】。 p 2 p 网络中搭便车现象会引起整个系统性能的下降，对p 2 p 网络系统的应用和发展 具有致命的威胁。文酬8 】中的数据表明，如果p 2 p 网络系统中没有f r e e r i d e r ，系统的局 部命中率将比现在提高一倍，大量f r e e r i d e r 节点用户的存在，将导致系统中很少一部分 的节点长期来服务系统中其他绝大多数的节点，容易出现个别服务节点因负载过重而最 终导致宕机；另外，绝大多数的服务请求由某一小部分节点来满足，容易出现因个别“热 点”离线而导致网络分裂，这对p 2 p 网络的扩展性不利【9 】；最终也会导致p 2 p 网络蜕变 为原来的c s 模式，不能发挥p 2 p 网络的优势【1 0 1 】，如p 2 p 网络的高度容错性、鲁棒 性等会明显降低；p 2 p 网络中查询结果的质量也会降低9 】 1 2 1 ：p 2 p 网络中大量的f r e e - r i d e r 查询信息容易造成网络拥塞，导致正常节点不能得到很好的服务；资源和服务集中在少 数热心节点身上，导致整个p 2 p 网络中新的资源和服务更新较慢，降低了网络对节点吸 引程度，容易丧失已有的节点用户，同样限制了网络的规模；在某些应用领域，如基于 p 2 p 的流媒体直播点播系统中，由于每一个节点用户都依赖其它节点用户的本地视频段 缓存和上传带宽，如果其它节点用户多为搭便车者，则该节点用户的视频播放效果将会 出现如停顿、马赛克等影响用户体验的不良现纠1 3 】。所以p 2 p 网络系统中的搭便车行为 必须要得到有效的抑制，否则对等网络以及基于对等网络的应用软件的生命周期、资源 丰富性、鲁棒性等都将受到严重的威胁。 1 2 国内外研究现状 显然搭便车现象与p 2 p 通讯模式设计之初的愿望严重冲突节点用户问的合作 ( c o o p e r a t i o n ) 对于p 2 p 网络系统的正常运作是至关重要的，但是，系统中每一个相对 独立的节点用户，它们各自的兴趣和利益，在很多时候是不同的，有时候甚至是相互冲 突的。a d a r 和h u b e r m a n 是最早指出在g n u t e l l a 网络中存在严重的触r i d i n g 现象【5 1 ， 继a d a r 和h u b e r m a n 在2 0 0 3 年的工作之后，仍然有很多学者在研究p 2 p 网络中的f r e e t i d i n g 现象6 】【7 】【1 4 】【l 卯。 一直以来，对等网络领域的研究者们对此问题进行了广泛和深入的研究，提出了一 些应对搭便车的激励机制模型和方法。激励机制的引入就是为了促使抱有各自不同利益 的节点，志愿将自身的资源贡献给系统，充分利用节点自我利好的动机达到系统总体效 用的最大化。针对p 2 p 网络系统中的搭便车问题，研究人员提出了多种激励方案。目前 2 西北大学硕士学位论文 激励机制的研究主要分为两大类：一类是基于货币支付( m o n e t a r yp a y m e n t ) 的市场经 济激励机制模型【1 6 】【1 刀【1 引，一类是基于差异化服务( d i f f e r e n t i a ls e r v i c e ) 的模型【1 9 】【2 0 】【2 l 】。 在基于货币支付( m o n e t t l yp a y m e n t ) 的市场经济激励机制模型中，其基本的思想 是将p 2 p 网络系统中节点所得到的服务货币化，也就是要提出一种合理有效的激励机 制，将节点提供的服务和享受的服务以虚拟货币的形式来度量。p g o l l e 1 6 】在p 2 p 网络 系统内引入了一个监视系统节点间交易的可信运营商，它通过1 ) 让下载资源的节点向 运营商支付一定的费用；2 ) 与提供资源的节点从运营商处获得一定的报酬相结合的办 法来解节点的搭便车问题；郑纬刚1 7 】等提出的m a z e 系统通过采用“积分值”奖励的办 法来鼓励节点提供共享资源。在m a z e 中系统为那些愿意提供共享文件的用户增加积分， 使得它们享有较高的下载带宽和较短的等待时间；而对那些具有自私行为的用户则以减 少积分、降低服务质量作为惩罚；k r i tw o n g r u j i r a 1 8 1 等将p 2 p 网络视为一个虚拟的市场， p 2 p 网络中的节点为自己转发的报文标价，通过利用市场的价格机制来激励节点参与协 作和共享，从而抑制搭便车行为。尽管这些基于货币支付的市场经济激励机制可以将现 有成熟的经济学模型加以利用，提供公正公平的激励方法，抑制搭便车行为的发生，但 是，在实际的工程实践上，却是不容易实现的。因为这种机制大都需要一个中心服务器 或是可信的第三方来支持，并且对于节点附加的货币化功能，在计算量和公平性上两者 也有矛盾之处。例如，论文【1 6 】需要一个类似n a p s t c r 注册服务器那样的中心服务器支持， 在一定程度上违背了p 2 p 的设计原理，容易产生单点失效的问题；m 讹e 【1 7 】中为了有效 的管理积分，系统采用用户管理服务器对用户积分进行严格地记帐和管理，但集中式的 管理也使它成为系统性能瓶颈，在实际应用的过程中，因无法登录用户服务器而导致 m a z e 整个网络瘫痪的现象时有发生；论文【1 8 】提出的结合节点信誉的报文竟价机制理论 上具有较好的效果，但是也不难发现，其节点信誉的计算和管理的开销都比较大，给参 与其中的节点附加的负载较重。 考虑到对等网络，特别是无结构对等网络( 如g n u t e l l a 3 1 、k a z a a 【4 等) 的特性， 如自治性( a u t o n o m o u s ) 、无组织( u n s t r u c t u r e d ) 、去中心化( d e c e n t r a l i z e d ) ，以及无结 构对等网络中参与节点的特性，如策略性( s t r a t e g i c ) 、自私性( s e l f - i n t e r e s t e d ) ，本论文 认为，基于差异化服务( d i f f e r e n t i a ls e r v i c e ) 的模型是一个应对搭便车现象的更为合理 的研究方向。斯坦福大学的k a l n v a r 等【1 9 】研究人员提出了基于分布式的信誉系统来形成 激励机制，其基本思想是，网络中每个节点根据本地信息( 交易信息或是信任关系) ， 计算出它对其它节点的本地信誉值，进而会得到初始信任矩阵c ，然后通过一定的算 3 第一章绪论 法扩大节点的信任范围，最终形成该节点的全局信誉值。根据这种方式，搭便车节点在 系统中积累的信誉值就会低于正常参与协作的节点的信誉值，以每个节点的全局信誉值 作为考核节点参与系统活动行为的标尺，从而起到了解决f r e e - r i d i n g 的作用。但是 e i g e n t r u s t 1 9 】算法有一个非常重要的前提，就是p d o nt r u s t 节点必须存在，即系统中前期 必须存在一定数量值得信赖的节点，而且每个节点在计算全局信誉值c 。时都需要进行多 次矩阵迭代运算，节点所附加的运算开销大；b i t t o r r e n t 协议中采用的t i t - f o r - t a t 策略是 典型的基于差异化服务的激励机制，它是以合作开局，此后就采取以其人之道还治其人 之身的策略2 0 1 【2 2 1 ；设计一个合理的效用函数，将节点的贡献和消费考虑其中，以此来决 定或是影响节点在网络中的收益，也是差异化服务激励机制的重要研究热点【9 】【2 3 】；差异 化服务的另一个研究方向是基于惩罚( p u n i s h m e n t - b a s e d ) 的激励机制【2 4 】，根据节点是 否按照对等网络协议来转发、响应其它节点的查询消息而进行一定程度的服务限制。 另外，利用市场经济理论( 如博弈论、纳什均衡等) 解决p 2 p 网络中的搭便车问 题已经成为p 2 p 网络激励机制研究的一个重要方向【2 5 】【2 6 1 ，通过将节点用户、节点行为、 节点收益分别看作是博弈论中的参与者( p l a y e r s ) 、策略集( s t r a t e g ys e t ) 、支付函数 ( p a y o f f sf u n c t i o n ) 等三要素，借鉴人们在分析社会群体活动和经济活动中寻求个体和 群体最优选择的纳什均衡，来对搭便车行为进行抑制，激励节点参与协作和贡献。 1 3 研究的动机和内容 继a d a r 和h u b c r m a n 在2 0 0 3 年的工作之后，有很多研究学者相继提出了应对p 2 p 网络中的f r e er i d i n g 现象的激励机制，但其中在真实p 2 p 网络系统中应用的却很少。很 多已有的激励机制在工程实现上并不复杂【2 3 】【2 4 】，但为何p 2 p 网络运营商却迟迟不在实 际的p 2 p 网络应用系统中采用抑制搭便车行为的激励机制? 本文认为现有的绝大多数 激励机制和p 2 p 网络运营商的运营模式之间存在以下矛盾： ( 1 ) ：度量节点贡献量和消费量的效用函数在设计上存在一个天然的冲突：复杂度 与合理性之间的冲突，即，简单的效用函数，对节点的额外负载低，但是合理性较弱； 而合理性较强的效用函数复杂度较高，很多往往只适用于理论推导，不具有实践推广性 【9 】因此就导致了如果采用计算量小的简单效用函数，效果不明显，而采用复杂的效用 函数，对单个节点的负载过高，如果一个应用软件对系统资源要求过高，在推广方面就 有一定的难度，目前p 2 p 网络运营商主要还是依靠在大规模的p 2 p 社区投放广告来支持 运营。 4 西北大学硕士学位论文 ( 2 ) ：在激励机制中，如果惩罚措施较为严格，就会使搭便车节点的行为受到较大 的限制，所享受的服务有限，往往就会导致搭便车节点用户退出网络，从而使该p 2 p 系 统的在线用户数量降低，而用户数量的降低，又会导致系统中资源的丰富性降低，每个 节点搜索资源的饱和度容易到达，进而在线的节点用户继续离开系统的可能性增大，最 终导致整个系统的衰竭。 ( 3 ) ：些激励机制往往需要系统中的每一个节点对整个系统的其它节点的信息有 所了解1 9 】【2 5 】【2 6 】，而在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 网络中节点用户的异质性和当前现有的p 2 p 网络的商业运营模式， 提出一种轻量级基于消息路由的应对f r e e - r i d e r 的分布式算法，即d a m r ( d i s t r i b u t e d a l g o r i t h ma n t i f l e e r i d e rb a s e do nm e s s a g er o u t i n g ) ，在此算法的基础之上，结合网络中 节点自身的负载情况，设计了一种新的抑制搭便车行为的激励机制，在对无结构对等网 络g n u t e l l a 协议进行小幅度修改后便可应用其之上。 1 4 论文结构和章节安排 本论文一共分为六章。 第一章绪论。主要介绍了本论文的研究背景，国内外现有的相关研究中的成果在实 际应用中所面临的矛盾和问题，以及本论文的主要工作，并简单介绍了论文的组织结构。 第二章是p 2 p 激励模型的研究。通过概述p 2 p 技术引出p 2 p 网络中存在的搭便车 问题，重点分析了p 2 p 网络中存在的f r e e - r i d i n g 行为对p 2 p 系统的危害，最后针对目前 已有的经典激励模型进行了研究分析和比较，并指出它们与目前现有的p 2 p 系统运营商 的实际需求之间的冲突之处，最后描述了对等网络激励机制近年来的研究热点。 第三章提出一种轻量级基于消息路由的应对搭便车行为的分布式算法，即d a m r 5 第一章绪论 ( d i s t r i b u t e da l g o r i t h ma n t i f i v e - r i d e rb a s e do nm e s s a g er o u t i n g ) ，在此算法的基础之上， 结合p 2 p 网络中节点自身的负载情况，设计了一种新的抑制搭便车行为的激励机制，并 对d a m r 算法所需的空间、时间和网络通信开销进行了分析，指出该算法的时间、空 间以及通信开销均很小，如果考虑到因抑制搭便车节点而惩罚性丢弃的数据包，那么该 算法其实就不会对现有网络系统的负载有所冲击。 第四章提出一种针对差异化服务激励机制具有通用性的数学模型来分析和评估这 一类激励机制。首先是数学模型的提出和建立，然后应用该数学模型对基于差异化服务 的两种激励机制，分别是b i t t o r r c n t 软件中的t i t - f o r - t a t 策略和本文的激励机制，进行 分析、评估以及合理性和正确性的数学验证，最后指出在应用d a m r 算法的激励机制 后，p 2 p 网络系统中将会存在着良性的均衡状态，而t i t f o r - t a t 策略则不存在。 第五章对现有的一个无结构对等网络仿真平台g n u t e l l a s i m 进行了扩展，搭建了一 个用于验证无结构对等网络采取激励机制后的系统性能的仿真实验平台，在此平台上对 第三章中提出的以d a m r 算法为基础的激励机制进行了仿真实验，通过对实验数据的 分析处理，验证了前面两章的分析结论，即本文的激励机制充分保证了p 2 p 网络的利用 效率，提高了p 2 p 网络系统中包括自私节点用户在内的所有类型节点用户的个体收益， 也提高了整个网络的系统总收益，增强了网络社区对节点用户的吸引力，进而维护了 p 2 p 网络运营商的利益，同时也努力营造出了一个公平公正的网络环境。 第六章结论与展望。总结全文的工作并指出无结构p 2 p 网络激励机制未来可能的 研究方向。 6 西北大学硕士学位论文 第二章对等网络激励机制的研究 2 1p 2 p 网络概述 因特网是当今全球最大的计算机网络，随着它在应用上的广泛普及，在规模上的 不断扩大，在功能上的不断推陈出新，端用户系统资源的不断丰富，以及网络带宽的 不断增大，传统客户服务器( c l i e n t s e r v e r ) 模式下服务器负载的增长远远超出了硬 件水平的增长速度，服务器端的性能瓶颈以及单点失效等问题不仅限制了端系统资源 的充分利用，更严重制约了现代因特网的高速发展。当传统的客户i l l 务器 ( c l i e n t s e r v e r ) 模式不再能够适应现代因特网的发展需求时，人们又重新审视分布式 系统。对等( p 2 p ) 网络是分布式系统与计算机网络相结合的产物，是采用对等模式 工作的计算机网络，网络中的每个成员都具有自由、平等、互联的功能，不再区分客 户端和服务器端，即每一个节点用户都兼具客户端和服务器端的功能，这种方式使得 网络的工作模式从集中式走向分布式，网络应用的核心从服务器转向网络中的每一个 结点。图2 1 反映出客户服务器模式到p 2 p 模式的转变。 图2 - l 从客户，服务器模式到p 2 p 模式的转变 ( 实线表示物理连接，虚线表示逻辑连接) p 2 p 网络在协同工作、分布式信息共享、大规模并行计算等方面显示出独特的优 势，从而使人们在网络上的信息交流被提升到了一个更高更新的层次，使人们以更主 动更深刻的方式参与到网络活动中去。我们需要p 2 p 网络，是因为它很好地适应了不 断膨胀的因特网的网络规模和动态的网络环境，图2 2 反映了分布式计算模式与系统 规模的关系。 7 第二章对等网络激励机制的研究 1 0 6 系 统 1 0 0 0 规 模1 0 0 1 0 单机l a nw a ni n t e m e t 地域分布 图2 2 分布式计算模式与系统规模的关系 p 2 p 网络的优点归纳有如下几点：( 1 ) 提高了网络的工作效率；( 2 ) 充分利用 了网络带宽；( 3 ) 开发了每一个网络节点的潜力；( 4 ) 具有较高的可扩展性；( 5 ) 具有良好的容错性。 2 1 1p 2 1 网络的分类 对于已经应用或正处于理论研究阶段的各种p 2 p 网络，到目前尚未出现公认的、 明确的分类方法，本文参考【l 】，将p 2 p 系统分为三类： ( 1 ) 混合式( h y b r i d ) p 2 p 网络。它是c l i e n t s e r v e r 和p 2 p 两类模式的混合，反 映出了网络工作模式从c l i e n t s e r v e r 到p 2 p 的过渡，网络的拓扑一般都是星型拓扑结 构，其中服务器仍然是整个网络的核心，网络的自组织、自适应性基本上都还是要依 靠服务器的监控和管理，节点用户之间的协作是建立在服务器的监控和管理基础之 上，典型代表是n a p s t e r l 2 8 】和b i t t o 玎煳t 【2 2 1 。图2 3 是混合式p 2 p 系统的示意图。 西北大学硕士学位论文 p e e r 图2 - 3 混合式p 2 p 系统示意图 图2 4 无结构p 2 p 系统的示意图 ( 2 ) 无结构( u n s t r u c t u r e d ) p 2 p 网络。其以分布、松散的结构来组织网络，即 网络中已经完全没有服务器角色的存在，网络的拓扑没有固定、严格的拓扑结构，而 是一个随机生成的、松散组织的普通图，理论上可以是任意形状。严格来讲，无结构 9 第二章对等网络激励机制的研究 p 2 p 网络是真正意义上的对等网络，它充分体现了自由、平等、互联的p 2 p 精神，具 有以下优点( a ) 网络拓扑结构简单，开发和实现难度小； ( b ) 鲁棒性高；( c ) 可扩 展性强：( d ) 自适应好；( e ) 安全性和匿名性高等特点。典型的代表是g n u t e l l a 3 1 。 图2 _ 4 是无结构p 2 p 系统的示意图。本文的研究重点就是无结构对等网络中的激励机 制，基于的无结构对等网络协议就是c m u t e l l a 协议。 ( 3 ) 有结构( s t r u c t u r e d ) p 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 ) 来将节点、数据对象等信息映射到网络中。典型代表 是c h o r d 3 1 】。图2 5 是有结构p 2 p 系统的示意图。 l e e r 3 图2 5 有结构p 2 p 系统的示意图 本论文所重点讨论的内容是在无结构p 2 p 网络中普遍存在的搭便车现象以及应 对这种现象的激励机制，主要以g n u t e u a 网络作为讨论对象。 2 1 2p 2 p 系统的应用 n a p s t c r 2 s 是全球第一个p 2 p 网络应用系统，它的出现给计算机网络技术领域带 来了重要变革，是对传统的非对称c l i e n t s e r v e r 通信模式的重大冲击。从n a p s t e r 开 1 0 西北大学硕士学位论文 始，利用网络边缘的终端结点进行计算、存储和通信的p 2 p 模式逐步取代了传统的客 户j 3 及务器模式，成为当前因特网应用的主要模式之一。一些基于p 2 p 技术的文件共享 系统，如g n u t c l l a ，e d o n k e y e m u l e ，b i t t o r r e n t 等，在全球范围内的在线用户数量曾 一度达到数百万之多。 近年来，p 2 p 应用软件更是层出不穷，除了在早期的文件共享、分布式计算应用 领域，p 2 p 在实时通信、流媒体、搜索引擎等领域也有显著的发展，涌现出了像n a p s t e r ， g n u t e l l a ，k a z a a ，b i t t o r r e n t ，e d o n k e y ，s k y p e ，p p s 仃e a m ，p p l i v e ，u u s c c 等一大批 知名软件，p 2 p 网络成为新的研究和发展热点。表2 1 列出了p 2 p 技术的相关应用实 例。 第二章对等网络激励机制的研究 表2 - li 2 p 技术应用 应用领域应用描述典型应用实例 最早便是文件共享引发了p 2 p 技术的产生与开发热 n a p s t e r ， 潮，p 2 p 技术使任意两台相连接的计算机之间共享文 文件共享 b i t t o r r e n t ， 档、多媒体和其它文件成为可能。采用p 2 p 技术， ( f i l es h a r i n g )e d o n k e y e m u l e ， 计算机之间可以进行直接交互，而不需要使用任何 m a z e ，e a s y m u l e 一台中央服务器。 将巨大的整体计算任务分解开来交给许多台计算机 分布式计算 g p u ， 分别执行，然后再将它们计算的结果进行归纳整合， ( d i s t r i b u t e d s e t i h o m e ， 从而开发了每个网络结点的潜力，利用了它们空闲 c o m p u t i n g ) d i s t r i b u t e d n e t 的c p u 计算能力。 利用p 2 p 技术可以减少对服务器的依赖，提高点对 实时通信( i m )q q ，s k y p e 点通信的可扩展性。 流媒体直播点播流媒体应用方面可以将流媒体文件进行实时分发数 p e e r c a s t ， ( s t r e a m i n g o n 据，且具有较大的可扩展性，极大的降低了服务器h n y s e ，p p l i v e ， v o d ) 的带宽负载。 p p s 垃e a m ，u u s e e 利用p 2 p 技术使用户能够无需通过w 曲s e 疆 v c r 就能 p 2 p 搜索引擎 够进行深度搜索文档，也可以不受消息文档格式和 i n f r a s e r c h ， ( p 2 1 , s e a r c h 宿主设备的限制，相对于传统目录式搜索引擎只能 p a n d a n g o e n g i n e )搜索到2 0 3 0 的网络资源，它理论上将包括网络 上所有开放的信息资源。 p 2 p 的分布式数据存取系统本身就包含了文件共享 的功能，但其目的与文件共享不同，它是以数据的 分布式数据存取可用性、持久性、安全性为目标，并且通常致力于 c f s ， ( d i s t r i b u t e dd a t a广阔的领域和海量的数据。分布式数据存取系统采 o c 魈n s t o m ， a c c e s s ) 用的数据存取方法因不同的用户要求也不同，但为 g r a n a r y 了确保数据的可用性和持久性，往往采用分片、复 制、缓存等方法。 1 2 西北大学硕士学位论文 2 2 搭便车问题与激励机制 2 2 1 搭便车问题的引出 在p 2 p 网络发展的早期，传统的p 2 p 协议( 如g n u t e l l a ) 总是假定网络中的节点 用户都是积极协作的( c o o p e r a t i v e ) 【3 】【4 】，因此就并没有提供差异化的服务策略，也没 有激励节点参与网络活动的概念。而p 2 p 网络较之传统的分布式系统，最大的特点就 是网络节点的自主性，也就是说，单个节点都是策略性的( s t r a t e g i c ) ，而不是协作性 的( c o o p e r a t i v e ) ，它们各自的兴趣和利益，在很多时候是不同的，有时候甚至是相 互冲突的。因此，更多的时候，节点用户可以在不参与贡献、不积极协作的前提下， 也能获得与正常协作节点用户相同的甚至是优于它们的服务，这就是搭便车行为，它 对p 2 p 网络的危害是十分致命的：( 1 ) 打破了p 2 p 所倡导的“平等 精神；( 2 ) 增 加了p 2 p 网络崩溃的风险；( 3 ) 降低了p 2 p 网络的生命周期；( 4 ) 制约了p 2 p 网络 的可扩展性。 很多研究者在对p 2 p 网络的测量中发现，在实际应用的p 2 p 系统中，少数热心 节点和多数搭便车节点并存，节点间存在着严重的搭便车现象( f i v e - r i d i n g ) 。据h u g h e s 等人的测试通过表2 2 中的数据对比可见，g n u t e l l a 的搭便车节点用户占网络总节点 数的比例，已经由2 0 0 0 年的6 6 上升到8 5 1 6 1 。国内学者对m a z e 的观察测量也表 明，在m a z e 中有近8 0 的节点用户表现得更像一个客户端，这些节点的下载数据量 占到了总量的5 1 ，而提供的上载数据量却只有总量的7 5 v i 。 表2 - 2g n u t e l l a 中搭便车行为测量结果 特别是近年来流行的p 2 p 流媒体系统呈现出比传统的p 2 p 文件共享系统更多的