（计算机软件与理论专业论文）基于服务区分的p2p流媒体激励方案研究.pdf

南开大学学位论文使用授权书 i y l l l l l l l18i1 1 1 1 4 i i i1 i l l 9 l1 1 i i i 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位 获得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范同内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论 文( 包括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位 论文，并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可 以将公开的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目 录检索、文摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开 大学向教育部指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息 研究所和中国学术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相 应学位论文数据库，通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论 文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开火学学习期间创作完成的作品，并已通过论文答 辩；提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 丞驰 2 0 1 0 年5 月2 8 日 南开大学研究生学位论文作者信息 论文题目基于服务区分的p 2 p 流媒体激励方案研究 姓名张驰学号2 1 2 0 0 7 0 2 9 6答辩日期2 0 1 0 年5 月2 8 日 论文类别博士口学历硕士硕士专业学位口高校教师口同等学力硕士口 院系所信息技术科学学院 专业 计算机软件与理论 联系电话 13 8 21 6 7 9 0 3 5e m a i l z h a n g c h i 0 2 2 7 g m a i l t o m 通信地址( 邮编) ：天津市卫国道翠阜新村翠荫里2 号楼5 门3 0 3 备注：无是否批准为非公开论文 否 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行研究工作所 取得的研究成果。除文中已经注明引用的内容外，本学位论文的研究成果不包 含任何他人创作的、己公开发表或者没有公开发表的作品的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均己在文中以明确方式标明。本 学位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 毖驰： 2 0 1 0 年5 月2 8 日 非公开学位论文标注说明 根据南开大学有关规定，非公开学位论文须经指导教师同意、作者本人申 请和相关部门批准方能标注。未经批准的均为公开学位论文，公开学位论文本 说明为空白。 论文题目 申请密级 口限制( q 年)口秘密( s 1 0 年)口机密( 翌0 年) 保密期限 2 0 年月日至2 0年月 日 审批表编号批准日期 2 0 年月日 限制2 年( 最长2 年，可少于2 年) 秘密1 0 年( 最长5 年，可少于5 年) 机密2 0 年( 最长1 0 年，可少于1 0 年) 中文摘要 摘要 近年来，互联网中流媒体的应用愈发广泛，并且已经成为推动宽带应用的 主要动力。流媒体的播放耗费了大量的网络资源，并且对网络的带宽要求较高。 传统的基于服务器和c d n 网络的流媒体系统由于带宽的限制，其应用局限于 极少数带宽富有的发布者上。而基于p 2 p 的流媒体系统可以打破i n t e m e t 传统 c s 模式固有的局限，降低服务器的压力，将流媒体的服务压力从单一的服务 器端分散到p 2 p 网络中去，大大提高了流媒体服务应用的广泛性。 然而，f r e e r i d i n g ( 搭便车) 问题一直困扰着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 i n g 节点和新加 入的节点由于其贡献值较低，从而在系统中的相对等级较低，在接受服务的时 候，其服务节点的选择受到限制，从而有效的抑制了f r e e r i d i n g 行为在系统中 的发生。 关键词：无结构p 2 p ，流媒体，搭便车，等级划分，服务区分 a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，m e d i as t r e a m i n gi sm o r ea n dm o r ew i d e l yu s e di nt h ei n t e r n e t a n db e c o m i n gt h em a i n l yd r i v i n gf o r c ef o rf u t u r eb r o a d b a n d h o w e v e r , i tn o to n l y c o n s u m e sh u g er e s o u r c eo ft h ei n t e r n e tb u ta l s or e q u i r e sg o o db a n d w i d t h t r a d i t i o n a lm e d i as t r e a m i n gs y s t e mb a s e do nc so fc d nm e c h a n i s mr e q u i r e s o v e rh i g hb a n d w i d t hw h i c hl i m i t st h eu s eo fm e d i as t r e a m i n gc a no n l yb ed e p l o y e d o nf e wp u b l i s h e r sw i t hh u g es t o r a g es p a c ea n db a n d w i d t h b u tt h em e d i as t r e a m i n g b a s e do np 2 ps y s t e mc a ne s c a p et h el i m i to ft h et r a d i t i o n a lc sm o d e l t h r o u g ht h e p 2 ps y s t e m ，w ec a nd i s p e r s et h el o a d i n go ft h es e r v e rt ot h ec l i e n ti nt h ei n t e m e t t h ed e p l o y m e n to ft h em e d i as t r e a m i n gb e c o m e sp o p u l a rb ym a k i n gu s eo ft h ep 2 e h o w e v e r ，t h ed e v e l o p m e n to ft h ep 2 pm e d i as t r e a m i n gi su n s m o o t hb e c a u s eo f t h ef r e e r i d i n g f r e e r i d i n gm e a n sm o r ea n dm o r en o d e sd on o ts h a r eb u to n l yg e t a n do n l yaf e wn o d e si nt h es y s t e mw a n tt oc o n t r i b u t e w j t l lt h ed e v e l o p m e n to ft h e p 2 p , t h eh a r mo ff r e e r i d i n gb e c o m e sm o r ea n dm o r es e v e r e p 2 pm e d i as y s t e m r e q u i r e sh i g hb a n d w i d t ht o f u l f i l lt h en e e do fr e a l - t i m i n g t h em i n o r i t ya l t r u i s t i c n o d e sc a n n o tt a k eo nt h el o a d i n go ft h ee n t i r es y s t e m s o ，w en e e da ne f f e c t i v e i n c e n t i v em e c h a n i s mt og u a r dt h eq u a l i t yo ft h es e r v i c e i nt h i sp a p e r ，w ep r o p o s eas e r v i c ed i f f e r e n t i a t e dp e e rs e l e c t i o nm e c h a n i s mf o r p e e r - t o - p e e rm e d i as t r e a m i n gs y s t e m sb a s e do nt h er a n k - - o r d e rt o u r n a m e n t st h e o r y t h em e c h a n i s mp r o v i d e sf l e x i b i l i t ya n dc h o i c ei np e e rs e l e c t i o nt ot h ec o n t r i b u t o r so f t h es y s t e m r e s u l t i n gi nh i g hq u a l i t ys t r e a m i n gs e s s i o n s f r e e - r i d i n g sa r eg i v e n l i m i t e do p t i o n si np e e rs e l e c t i o n ，i fa n y , a n dh e n c er e c e i v el o wq u a l i t ys t r e a m i n g t h u s ，t h r o u g ht h eu s eo ft h em e c h a n i s m ，w ee f f e c t i v e l yd e p r e s st h ef r e e - r i d i n g k e yw o r d s ：u n s t r u c t u r e dp 2 pn e t w o r k s ，m e d i as t r e a m i n g ，f r e e r i d i n g ，r a n k o r d e r , s e r v i c ed i f f e r e n t i a t e d i i 目录 目录 第一章引言1 第一节研究背景1 第二节相关研究现状2 第三节本文研究内容3 第四节论文结构4 第二章p 2 p 网络与f r e e - r i d i n g 问题5 第一节p 2 p 网络概述j ：5 2 1 1p 2 p 网络产生背景与基本原理5 2 1 2 p 2 p 网络的结构分类7 第二节p 2 p 流媒体概述10 2 2 ip 2 p 流媒体技术简介1 0 2 2 2p 2 p 流媒体的特点。11 第三节p 2 p 网络中f r e e r i d i n g 行为的影响及其分析1 2 2 3 1 f r e e - r i d i n g 问题1 2 2 3 2 f r e e r i d i n g 问题对p 2 p 网络的影响1 3 2 3 3 f r e e r i d i n g 问题的建模分析1 4 第三章p 2 p 系统中激励模型概述1 7 第一节什么是激励机制1 7 第二节p 2 p 网络中的激励机制1 8 3 2 1 p 2 p 中主要激励措施1 8 3 2 2 几种典型的激励机制一1 9 i i i 目录 3 2 3p 2 p 流媒体激励机制的特殊性2 3 第四章r c b d i f f s e r v 激励方案设计2 5 第一节p 2 p 流媒体系统的特殊性分析。2 5 第二节r c b d i f f s e r v 激励方案基本思想与理论依据。2 7 4 2 1r c b d i f f s e r v 激励方案基本思想2 7 4 2 2r c b d i f f s e r v 激励方案的理论依据2 8 第三节r c b d i f f s e r v 方案设计流程与模型一2 9 4 3 1r c b d i f i s e r v 的设计流程2 9 4 3 2 r c b d i f f s e r v 方案的设计模型3 0 第四节r c b d i f f s e r v 方案的实现细节3 2 4 4 1 服务质量( q u a l i t y ) 一3 2 4 4 2 贡献值的计算。3 2 4 4 3 贡献值的存储3 4 4 4 4 贡献值获取依据3 5 4 4 5 贡献值的衰减。3 6 4 4 6 节点等级计算。3 7 4 4 7 质量函数。3 8 第五章仿真实验及性能分析4 0 第一节模拟环境4 0 5 1 1 模拟平台4 0 5 1 2 模拟环境参数设置4 2 第二节仿真实现4 4 5 2 1t r a c k e r 服务器的仿真实现4 4 5 2 2 视频服务器的仿真实现4 5 i v 5 2 2 第三节 5 3 1 5 3 2 5 3 3 5 3 4 5 3 5 5 3 6 第四节本章小结6 l 第六章总结与展望6 3 第一节总结6 3 第二节今后工作的展望。6 4 参考文献6 5 致谢6 9 附录7 0 附录a ：图索引7 0 附录b ：表索引。71 个人简历、在学期间发表的学术论文与研究成果7 2 v 第一章引言 第一章引言 第一节研究背景 近年来，对等网络的研究在文件共享、应用层组播方面得到了广泛关注， p 2 p 技术得以快速发展。在p 2 p 方式下，每个对等实体( p e e r ) 既是服务的提 供者，又是服务的享用者。p e e r 为系统提供有限的计算或存储资源，p e e r 之间 协作为其它p e e r 提供服务，将服务器的负载分散到p e e r 中，从而有效地减轻了 服务器的负载和网络带宽占用，极大提高了系统的可扩展性，具有潜在的应用 前景。 由于p 2 p 模式可以在大规模网络应用中有效提高系统的可扩展性，基于p 2 p 方式的流媒体传输的研究也逐步引起了人们的重视，许多流媒体协议已经被提 出。然而，为了获得较好的性能，大部分都假设是在一个有足够上载能力支持 下载的环境中，节点充分相互协作，共享拥有的资源，如磁盘空间、上行带宽 等。然而在现实环境中情况远非如此：在p 2 p 系统中，f r e e r i d i n g ( 搭便车) 行为盛行，大多数的用户不愿共享自己的资源，却向网络索取大量的资源，只 有少数无私的用户贡献资源并成为服务的提供者，响应其他用户的请求；另外， 一些非对称网络连接( 例如a d s l ) 上行带宽和下行带宽的数据传输能力存在 差异，下行带宽数据传输能力往往大于上行带宽。这些都会导致系统对于下行 带宽的需求大于可用的上行带宽，造成系统的资源瓶颈。 此外，通过对p r o m i s e 的研究【1 1 表明节点协作度低于某个阈值，即使在负 载不重的情况下系统性能也很差；研究还表明当协作度低，无私者同时给多个 流会话提供上载时，提供者和远端接收者的流质量都会下降，仅仅依靠少量的 无私者提供服务是不可行的。因此，需要建立一种合理的激励机制，鼓励节点 提供尽可能多的上行带宽，提高协作度，最大化地共享资源。 传统的激励方案，如t i t f o r t a t 、基于微支付和基于信誉的机制在文件共享 系统中是比较有效的。但是在流媒体系统中，由于有延迟和带宽的限制，这些 机制不能很好地运行。因此，提出合理的适用于p 2 p 流媒体系统的激励方案， 有效的减少p 2 p 流媒体系统中f r e e r i d i n g 节点的数量，使节点自觉的共享出自 身的资源为 第二节相关研究现状 为了解决p 2 p 网络中广泛存在的f r e e r i d i n g 问题，促进节点共享资源，最 终增强系统的整体效用。于是学者们借鉴社会、经济上的术语，提出“激励机 制”这一名词，并把它应用于p 2 p 网络研究中。那么怎样在p 2 p 网络中建立激 励机制，采用什么样的激励模型和算法，成为众多研究者进行研究的目标。 f r e e r i d i n g 现象最早是在研究g n u t e l l a 2 】时发现的。e a d a r 等人指出，g n u t e l l a 系统中存在着大量的f r e e r i d i n g 现象，导致该系统缺乏节点进行合作的机制， 最终成为g n u t e l l a 系统发展的瓶颈【3 j 。 目前激励机制的研究主要分为两大类：一类是基于微支付和虚拟货币机制 4 1 ( m i c r o c u r r e n c y ) 的模型，类是基于服务质量( q o s ) 。金钱支付类的激励 措施的主要思想是为p 2 p 网络引入虚拟货币的概念，用虚拟货币对p 2 p 网络中 的资源或服务明码标价，用户如果需要下载资源或使用服务的话，就需要缴纳 其价格对应的虚拟货币量；而用户如果提供资源下载或服务的话，则可以获得 一定比例的虚拟货币。虚拟货币与现实中的货币以一定的比例相对应。在满足 某种条件下，用户可以将虚拟货币兑换成现实中的货币。用户也可以使用现实 中的货币去购买虚拟货币，以购买需要的资源或服务。由于用户兑换或购买时 使用的货币量往往比较小，常规的网络支付成本高且非常不便，因此采用此类 激励措施的激励机制往往同时引入微支付机制来进行货币的支付和虚拟货币的 购买。由于这种激励方案采用了虚拟货币，需要建立专门的财务机制来跟踪交 易情况，而且还引入了微支付机制，使得其在实际应用中比较复杂，因此不是 很实用。 区分服务的思想是为不同级别的节点提供不同的服务。对于那些级别高的 用户，在下载资源时提供更好的服务，比如更大的带宽，更好的节点选择能力， 如果需要等待的话则排在等待队列的前方。对于那些低级别的用户，则刚好相 反。只有当优先级高的用户得到较好的服务之后才能够享受服务，而且服务质 量不如高级别用户。 p 2 p 流媒体系统不同于传统的p 2 p 文件共享系统。p 2 p 流媒体系统不仅仅 要求文件的可用性，由于p 2 p 流媒体系统实时点播的应用，它往往需要更高的 2 第一章引言 服务质量，而这就要求需要从各方面综合考虑，包括流媒体源节点的链路容量， 可用性，传输速率和从源节点到接受节点传输网络的带宽可用性，丢包率等多 方面的因素。此外，实验表明，通常情况下流媒体文件传周期中比传统的p 2 p 文件共享需要更多的s u p p l i e r s 。因此，流媒体文件传输过程中，节点之间的合 作更为频繁，这样就需要更为有效的激励方案，从而起到使贡献多的节点获得 更好的服务，而对f r e e r i d i n g 这种自私节点起到有效的抑制作用。 而目前国内外对于p 2 p 激励方案的研究还相对集中在p 2 p 文件共享系统 中，如b t f 5 1 ，e m u l e 【6 j 等文件共享系统。而相对于传统p 2 p 文件共享系统而言， p 2 p 流媒体系统中激励方案的研究少之又少，大部分的研究还集中在系统的调 度策略与整体的系统构架方面【7 】【8 】 9 1 1 0 】。虽然如此，传统的p 2 p 文件共享系统 的激励方案的策略在一定程度上仍然适用于p 2 p 流媒体系统【1 1 】【1 2 】【1 3 】【1 4 】。 第三节本文研究内容 本文首先介绍了p 2 p 系统中存在的f r e e r i d i n g 现象对系统资源的利用以及 系统整体性能所带来的危害。然后对p 2 p 流媒体系统现有的一系列f r e e r i d i n g 现象带来的问题进行了分析和总结，并且指出了无激励机制的p 2 p 流媒体系统 的不足，如系统的服务质量不高，网络带宽浪费，节点请求次数过多等一系列 问题。 为了解决p 2 p 流媒体系统中f r e e r i d i n g 以及其所带来的服务质量问题，本 文提出了一种基于相对贡献值的服务区分激励方案( r c b d i f f s e r v ) 。在该方案 中，我们通过节点的贡献值来划分节点的等级，拥有不同等级的节点在进行节 点选择的时候拥有不同的节点选择范围，进而使等级高的节点获得服务时可以 选择更多的节点为其服务，从而提高该节点所获得的服务质量，并且局限了 f r e e r i d i n g 节点的选择范围，使其获得较低的服务质量。节点可以根据其贡献 值和等级预测其可以获得的服务，并且可以根据其预估的能够获得的服务质量 来选择拒绝或者接受来自其它节点的请求，从而有效的对节点起到了激励作用。 本文通过在p 2 p s t r m s i m 提供的p 2 p 流媒体系统平台上进行算法的模拟，并 通过模拟环境下的仿真实验，测试该方案对p 2 p 流媒体系统性能的影响。最后 分析结果并得出结论。 文的 以及 析。 点行 统的 第一节p 2 p 网络概述 2 1 1p 2 p 网络产生背景与基本原理 早期的互联网，主要的模式是由服务器提供各类应用，而一般的网络用户 的客户机终端使用这些应用，即所谓的客户服务器模式。然而，随着互联网 的迅速普及，网络用户量呈几何级数增长，这既为计算机技术带来了新的机遇， 同时也带来了挑战。一方面各种网络应用的并发用户数量变化极大，高峰时 的用户数量和低谷时的用户数量可以相差一个甚至多个数量级。如果满足高峰 时的要求，则需要大量的服务器投资，而且在低谷时服务器资源空置，造成了 极大的浪费：如果不满足高峰时的要求，则会极大地降低用户的体验。这使得 服务提供者进退两难另一方面，尽管服务器也在快速发展，却依然满足不了 高速增长的用户需求。而相比之下，用户的计算机终端经过多年的发展，已经 有了长足的进步。于是p 2 p 技术应运而生：通过利用用户计算机的空闲能力， 部分缓解服务器的压力，甚至取代服务器提供服务。事实上，从2 0 世纪9 0 年 代中叶起，个人计算机的计算能力就开始超过用户的需求了。i n t e l 的一项研究 表明，普通组织的桌面计算机的计算能力总和是其中央服务器和高端计算机的 2 5 倍【1 5 】。 p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源 ( 处理能力、存储能力、网络连接能力、打印机等) ，这些共享资源需要由网络 提供服务和内容，能被其它对等节点( p e e r ) 直接访问而无需经过中间实体 【1 6 】【1 7 】【1 引。在此网络中的参与者既是资源( 服务和内容) 提供者( s e r v e r ) ，又是 资源( 服务和内容) 获取者( c l i e m ) 。传统的c s 结构模式与p 2 p 结构模式的 对比【憎j 如图2 1 与2 2 所示： 第二章p 2 p 网络与搭便车问题 图2 1 传统的c s 结构模式 创建信息 图2 2p 2 p 分布式结构模式 由图2 2 可以看出，p 2 p 网络中的资源和服务分散在所有节点上【2 川，信息的 传输和服务的实现都直接在节点之间进行，可以无需中间环节和服务器的介入， 避免了由于网络规模增加而可能的瓶颈。p 2 p 的非中心化的基本特点为其带来 了可扩展性、健壮性等方面的优势【2 。在p 2 p 网络中，随着用户的加入，不仅 服务的需求增加了，系统整体的资源和服务能力也在同步地扩充，始终能较容 易地满足用户的需要。整个体系是全分布的，不存在瓶颈。理论上其可扩展性 几乎可以认为是无限的。此外，p 2 p 结构天生具有抗攻击性高、高容错的优点 6 第二苹p 2 p 网络与搭便车问题 【勿。由于服务是分散在各个节点之间进行的，部分节点或网络遭到破坏对其它 部分的影响很小。p 2 p 网络一般在部分节点失效时能够自动调整整体拓扑，保 持其它节点的连通性。p 2 p 网络通常都是以自组织的方式建立起来的，并允许 节点自由地加入和离开。p 2 p 网络还能够根据网络带宽、节点数、负载等变化 不断地做自适应式的调整。由于每个节点既是服务器又是客户机，减少了对传 统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布在多个节点， 更好的实现了整个网络的负载均衡。 总之，与传统的分布式系统相比，p 2 p 技术具有无可比拟的优势。同时， p 2 p 技术具有广阔的应用前景。i n t e m e t 上各种p 2 p 应用软件层出不穷，用户数 量急剧增加。并且p 2 p 计算技术正不断应用到军事领域，商业领域，政府信息， 通讯等领域。 2 1 2p 2 p 网络的结构分类 依照节点信息的存储方式，查询方式，以及拓扑关系，p 2 p 网络大致可以 分为4 类：集中式p 2 p 网络，非结构化的p 2 p 网络，结构化的p 2 p 网络，融合 了结构化与非结构化特点的混合式p 2 p t 乃j 。 集中式p 2 p 结构是最早出现的p 2 p 应用模式，因为仍然具有中心化的特点 也被称为非纯粹的p 2 p 结构。集中式p 2 p 网络结构如图2 3 所示。在集中式p 2 p 结构中所有资料并非存储在服务器上，而是存贮在各个节点中。查询节点根据 网络流量和延迟等信息选择合适的节点建立直接连接，而不必经过中央服务器 进行。著名的m p 3 共享软件n a p s t e r 2 4 采用的就是这种模式。 7 图2 3 集中式p 2 p 网络结构 非结构化的p 2 p 系统采用了随机图的组织方式，形成丁一个松散的网络。 其结构如图2 4 所示。非结构化系统的优点在于实现结构简单，无须中央服务 器，节点之间完全平等，网络的层次是单一的，网络的动态变化有较好的容错 能力，而且节点之间无需维护拓扑信息，因此具有较好的可用性它解决了网络 结构中心化的问题，扩展性和容错性较好。典型的应用有g n u t e l l a 、f r e e n e t l 2 5 j 但网络中的搜索算法以泛洪的方式进行，控制信息的泛滥消耗了大量带宽并很 快造成网络拥塞甚至网络的不稳定。同时，局部性能较差的节点可能会导致网 络被分片，从而导致整个网络的可用性较差，另外这类系统更容易受到垃圾信 息，甚至是病毒的恶意攻击。 图2 4 非结构化p 2 p 网络 8 第二章p 2 p 网络与搭便车问题 结构化p 2 p 模式是一种采用纯分布式哈希的消息传递机制和根据关键字进 行查找的定位服务，目前的主流方法是采用分布式( d h t ) 技术【2 6 ，这也是目 前扩展性最好的p 2 p 路由方式之一，c h o r d 2 7 1 、c a n t 2 8 】和p a s t r y 2 9 1 是这类拓扑 的代表。由于d h t 各节点并不需要维护整个网络的信息，只在节点中存储其 临近的后继节点信息，因此较少的路由信息就可以有效地实现到达目标节点， 同时又取消了泛洪算法。该模型有效地减少了节点信息的发送数量，从而增强 了p 2 p 网络的扩展性。同时，出于冗余度以及延时的考虑，大部分d h t 总是 在节点的虚拟标识与关键字最接近的节点上复制备份冗余信息，这样也避免了 单一节点失效的问题。结构化p 2 p 网络形成了一种逻辑上的拓扑结构。但结构 化p 2 p 网络模型并不适合大规模的i n t e m e t 部署。同时基于d h t 的拓扑维护和 修复算法也比非结构化模型等无结构的系统要复杂得多。目前大量实际应用还 大都是基于无结构的拓扑和泛洪广播机制。 混合式p 2 p 结构在纯p 2 p 分布式模型基础上引入了超级节点的概念，综合 了集中式p 2 p 快速查找和纯p 2 p 去中心化的优势。典型的案例如k a z o a 【3 ， g r o k s t e r 3 ， m e s h 3 2 1 该模型将节点按能力不同( 计算能力、内存大小、连接带 宽、网络滞留时间等) 区分为普通节点和搜索节点两类( 也有的进一步分为三 类节点，其思想本质相同) 。其中搜索节点与其临近的若干普通节点之间构成一 个自治的簇，簇内采用基于集中目录式的p 2 p 模式，而整个p 2 p 网络中各个不 同的簇之间再通过纯p 2 p 的模式将搜索节点相连起来。混合式p 2 p 网络结构 模型如图2 5 所示。总的来说，基于超级节点的混合式p 2 p 网络结构比以往有 较大程度的改进。然而，由于超级节点本身的脆弱性也可能导致其簇内的节点 处于孤立状态，因此这种局部索引的方法仍然存在一定的局限性。 9 第二章p 2 p 网络与搭便车问题 图2 5 混合式p 2 p 网络结构模型 第二节p 2 p 流媒体概述 2 - 2 1p 2 p 流媒体技术简介 p 2 p 实时流媒体技术是p 2 p 技术与流媒体技术【3 3 】【3 4 j 的结合，其核心思想就是 把p 2 p 技术应用于实时流媒体数据的分发中去，把网络层的组播功能转移到应用 层实现，充分有效地利用各个节点的资源。 在基于p 2 p 的流媒体技术中【3 5 】，每个流媒体用户是p 2 p 网络中的一个节点， 用户可以根据其他节点的设备能力和网络状态与一个或几个用户建立连接柬分 享数据，这种连接能减轻服务器的负担和提高每个用户的视频质量。p 2 p 技术在 流媒体应用中特别适用于一些热门事件，即使是大量的用户同时访问流媒体服 务器，也不会使服务器因负载过重而瘫痪。p 2 p 流媒体技术主要优势在于降低对 服务器处理能力和服务器上传带宽的要求，节约了主干网络传输带宽。 目前比较流行的p 2 p 流媒体直播技术，采用无结构的数据驱动( d a t a 。d r i v e n ) 的调度策略1 3 引。该协议在覆盖网络构建方面，采用随机选择邻居节点的策略， 用以构造连接度较高的无结构网络。在流媒体传输方面，主要采用类似b i t t o r r e n t 1 0 第二章p 2 p 网络与搭便车问题 等文件共享系统的传输策略，如a n y s e e l 3 7 】。将完整的一段流媒体被切分成多个 数据片段，每一个节点周期性的向他的邻居节点通知其所拥有的数据片段，与 此同时，每一个节点根据其邻居节点的通知，直接显示的向其邻居节点请求它 所缺少的数据片段。节点问是通过b u f f e r - m a p 或者类似的机制来相互通知所拥有 的数据片段。目前网络中部署的绝大多数p 2 p 网络流媒体直播系统都是基于该算 法实现的。( ! t l l p p l i v e 3 8 】，q q l i v e 3 9 】等) 该算法核心思想简单，易于实现，而且 拥有很强的可扩展性和健壮性。该协议的缺点就是控制开销过大，延迟较高。 2 2 2p 2 p 流媒体的特点 与p 2 p 文件共享相比，在p 2 p 流媒体内容分发研究过程中所面临的挑战也更为 严峻，这是因为可提供服务的p e e r 节点的服务能力有限、不同p e e r 节点的服务能 力具有差异性，此p f p e e r 节点还可随时退出系统，从而造成其它部分节点流传输 的中断；而流媒体本身又具有其特殊性，如带宽资源占用高、服务持续时间长、 对数据的播放有较为严格的时限和顺序要求等。 虽然p 2 p 流媒体技术得到了长足的发展，但是仍然有许多待解决的挑战性难 题，主要有以下几点： 1 ) 节点动态性管理 p 2 p 系统中节点的行为是不可预测的，每个节点可以随时加入系统请求服务， 也会随时终止服务，甚至在没有预先通知下退出系统。极端情况下，大量节点 在短时间内加入或者退出网络。节点的高度动态性对整个系统的服务质量带来 了挑战。 2 1 节点异构性 网络中节点的能力是异构的，它们的上下行带宽，可提供的存储空间和计算 能力是不同的。高质量视频流媒体需要足够的带宽支持，由于节点带宽的异构 性，一些节点可用带宽低于视频速率的要求。进一步提高流媒体视频速率，满 足高带宽节点对视频质量需求，帮助低带宽节点获取满意的服务质量是流媒体 系统需要研究的一个关键问题。 3 1q o s j 艮务质量保证 现行的各种视频压缩标准产生的视频流码率都比较高，如m p e g 1 的码率为 1 - 5 m b p s ，m p e g 2 的码率为2 i o m b p s ，m p e g 一4 的码率约为数十m b p s 至r 数百 第二苹p 2 p 网络与搭便下问题 m b p s ，在p 2 p 流媒体系统运行时超过或低于此码率都会导致解码时的缓冲区上溢 或下溢，影响播放效果，因此在流数据的分发过程中必须保证数据传输的实时 性。此外数据包在网络传输过程中发生的丢包、延迟等现象都可能会影响接收 方的q o s 服务质量【4 0 1 。由于p e e r 节点之间的网络带宽资源有限，数据包在p e e r 节 点之间传输时也同样具有丢包、延迟等特征，此夕 - p e e r 还可能随时离开或失效， 上述这些因素将导致p 2 p 网络环境下的q o s 服务质量问题更加突出。因此在p 2 p 网络环境下如何对p e e r 节点的服务质量提供保障己成为p 2 p 流媒体分发技术研究 中的核心问题。 4 ) 激励机制及其它 在p 2 p 网络环境中需要参与服务的p e e r 节点尽量贡献自己的资源，以提高网 络上的资源利用率，快速增长系统服务能力，从而提高系统中节点的整体服务 质量水平。但在实际应用中许多用户更倾向于以f r e e r i d i n g 的形式参与系统，即 只愿意从其它节点获取服务而不愿意贡献出其本身的空闲资源为其它节点提供 服务，这一点也在实际系统中得到了论证：a d a r 等人通过对著名p 2 p 文件共享系 统g n u t e l l a 的运行活动进行了2 4 d , 时的跟踪记录，发现系统中7 0 的用户节点根 本没有共享出本身的资源，其中1 的用户节点承担了系统4 7 的下载负载，而 2 5 的用户节点承担了系统9 9 的下载负载。p 2 p 网络环境中节点这种 f r e e r i d i n g 行为并不能够充分利用i n t e m e t 上的空闲资源，也不利于充分发挥p 2 p 模式的优势。因此如何建立一套有效的激励机制，使得节点在行使消费者角色 的同时，主动承担为其它节点提供服务的职责，也是p 2 p 流媒体内容分发中一项 值得研究的课题，这也是论文中所要解决的问题。此外，如何验证流媒体数据 内容的正确性与合法性、如何有效地检测并抵御恶意节点所实施的攻击或欺骗 等行为，也是p 2 p 流媒体内容分发技术研究中逐步需要解决的问题。 第三节p 2 p 网络中f r e e - r idin g 行为的影响及其分析 2 3 1 f r e e r i d i n g 问题 f r e e r i d i n g ( 搭便车) 问题是指节点只消费其他节点贡献的资源，而不共 享自己的资源。以g n u t e l l ap 2 p 文件共享系统为例，7 0 的节点是只下载不上 传，系统内5 0 的请求来自于前l 的节点，通过对e d o n k e y 的监测也表明在 1 2 第二章p 2 p 网络与搭便车问题 e d o n k e y 文件共享网络中，大约有8 0 的节点是f r e e r i d i n g 节点。 f r e e r i d i n g 行为不但使p 2 p 网络服务规模从理论上的o ( n 2 ) 下降到趋于 o 【4 1 1 ，严重的制约了p 2 p 的优势，还会引起“公共物品的悲剧”( t h et r a g e d y o f t h ec o m m o n s ) 问题。所谓“公共物品的悲剧”是指网络资源作为一种非排 它的公共资源，被大多数p 2 p 节点无节制地使用 4 2 1 。据统计，p 2 p 数据流量占 因特网总流量达6 0 ，并且在用户总数没有显著增长的情况下，p 2 p 数据流量 仍然在快速持续增长。事实上，p 2 p 网络理性用户的根本目的是最大化自己效 用，而并不考虑网络的整体效用。另一方面，此现象与f r e e r i d i n g 行为相结合， 造成提供共享资源的节点处出现网络拥塞，影响网络服务质量1 4 引。 一个缺乏合作的p 2 p 网络中，f r e e r i d i n g 现象非常普遍，很多节点之下载 资源或索取服务，从来不提供资源或服务。更有甚者，有的节点提供假的资源 或服务，这种现象在e m u l e 网络中也屡见不鲜。有些节点故意限制或提供虚假 的网络状况报告，以达到少提供或不提供资源或服务的目的。 f r e e r i d i n g 等一系列问题的出现，究其根本原因是目前p 2 p 网络中信任的 缺失。因此，我们需要提供某种信任机制，激励节点提供安全可靠的服务，发 挥p 2 p 架构的网络规模优势。 2 3 2 f r e e r i d i n g 问题对p 2 p 网络的影响 f r e e r i d i n g 现象给p 2 p 网络带来的诸多不良影响。具体表现在如下几个方 方面： 1 1 当对等网中的在线节点很多时，f r e e r i d i n g 节点的增多，使那些热心 节点( 积极共享资源的节点，非f r e e r i d i n g 节点) 所承担的资源查询和下载等 任务就会越来越重，热心节点的负载就会增加，严重时可能会导致热心节点主 动退出该网络。在无结构的p 2 p 网络中热心节点有可能是其关键的路由节点， 所以当热心节点故障或者退出网络时，可能会导致网络的连通性发生变化。 2 1 过多节点的f r e e r i d i n g 行为会导致p 2 p 网络的生命周期缩短。用户节 点加入到p 2 p 网络是为了从系统中获取自己需要的资源。节点通过对p 2 p 网络 的查询，来收集其本身所需要的资源。如果节点收集到的资源数量与p 2 p 网络 中所共享的资源总数相同，则该节点就会从这个对等网中退出。如果系统中的 大部分资源都是由其热心节点提供的，那么当对等网中可以用来下载的资源越 第二章p 2 p 网络与搭便车问题 来越少时，那些热心节点也会迅速退出该网络的，最终导致系统资源匮乏。 3 1 随着热心节点的退出，系统中的f r e e r i d i