（电路与系统专业论文）通信网中p2p流媒体节点分配策略研究.pdf

； 。 南京邮电大学 硕士学位论文摘要 学科、专业：工学电路与系统 研究方向：玉线通值丕统生的篮曼处堡撞苤 作者：孙卫军 指导教师：周井泉教授 1 1 1 1 1 1 1 111 1 1 1 1 1 1i iiil llii i1 1 1 1 1 1 1 1 0 1y 17 5 4 9 6 0 题目：通信网中p 2 p 流媒体节点分配策略研究 英文题目：t h en o d ea l l o c a t i o ns t r a t e g yr e s e a r c ho fp 2 pm e d i a s t r e a m i n g i nc o m m u n i c a t i o nn e t w o r k 主题词：p 2 p 流媒体节点分配策略结构化博弈理论 激励机制 k e y w o r d s ：p 2 p m e d i as t r e a m i n gn o d ea l l o c a t i o ns t r a t e g y s t r u c t u r e dg a m et h e o r yi n c e n t i v e s 南京邮电大学硕士研究生学位论文 摘要 摘要 p 2 p 流媒体系统在过去几年用户群急速膨胀、应用面不断拓宽。典型的p 2 p 流媒体系 统有s k y p c 、p p l i v e 、p p s t r e a m 等，其中无论网络音频、网络视频领域均存在数十家公司 激烈竞争，这种激烈竞争的局面不仅促进了工业界的技术进步，也为学术界的研究工作提 供了价值保证。目前，中国内地网民观看网络视频的几种主要方式中，通过p 2 p 流媒体软 件下载的比率接近三分之一，由此可见，p 2 p 流媒体是一个拥有巨大用户群的领域，也是 一个充满研究潜力与意义的领域。 节点分配策略是p 2 p 流媒体的核心技术与研究热点。根据优化目标的不同，节点分配 策略可以分为3 类子问题，分别是面向系统健壮性与网络负载均衡性，面向流服务质量和 面向网络拓扑聚集，其中面向流服务质量的节点分配策略为主要研究方向。 本文主要研究结构化的p 2 p 流媒体节点分配策略，对于结构化的p 2 p 流媒体协议进行 分类并且分析在选择父节点与子节点时的异同。另外通过仿真比较各种现存的p 2 p 流媒体 协议的节点分配算法的优劣，着重比较它们在提高流媒体服务质量方面所做的贡献。对于 一种基于博弈理论的p 2 p 流媒体的c _ r d m e 节点分配算法提出改进措施，与现存的几种较先 进的p 2 p 流媒体协议相比，改进后的算法能够很好地提高p 2 p 流媒体的服务质量。 关键词：p 2 p 流媒体节点分配策略结构化博弈理论激励机制 1 1， 7 嶂 j i ； d o w n l o a dr a t i oi sc l o s et oo n e - t h i r d i tc a nb es e e nt h a tp 2 pm e d i as t r e a m i n gi sn o to n l ya na r e a 诚t hh u g eu s e r s ，b u ta l s oaf u l lp o t e n t i a la n ds i g n i f i c a n c ea r e af o rr e s e a r c h n o d ea l l o c a t i o ns t r a t e g yi st h ec o l eo fp 2 pm e d i as t r e a m i n gt e c h n o l o g ya n dt h ef o c u so f r e s e a r c h a c c o r d i n gt ot h ed i f f e r e n to p t i m i z a t i o no b j e c t i v e s ，n o d ea l l o c a t i o ns t r a t e g yc a nb e d i v i d e di n t ot h r e ec a t e g o r i e ss u b - p r o b l e m s , n a m e l y , s y s t e mr o b u s to r i e n t e d , n e t w o r kl o a d b a l a n c e , f l o ws e r v i q u a l i t yo r i e n t e da n dn e t w o r kt o p o l o g ya g g r e g a t i o no r i e n t e d , i nw h i c ht h e n o d ef o rt h ef l o wo fs e l v i c , eq u a l 耐a l l o c a t i o ns t r a t e g yi st h em a i nr e s e a r c hd i r e c t i o n t h i sp a p e rs t u d i e s t h es t r u c t u r e dp 2 pm e d i as t r e a m i n gn o d ea l l o c a t i o ns t r a t e g y t h e s t r u c t u r e dp 2 pm e d i as t r e a m i n gp r o t o c o l si sc l a s s i f i e da n da n a l y z e di ns e l e c t i n gt h ep a r e n tn o d e s a n dc h i l dn o d e sf o rt h es i m i l a r i t i e sa n dd i f f e r e n c e s t h r o u g ht h es i m u l a t i o nw ec o m p a r et h ep r o s a n do o n so fe x i s t i n gp 2 pm e d i as t r e a m i n gn o d ea l l o c a t i o na l g o r i t h m , w i t hs p e c i a le m p h a s i s0 1 1 c o m p a r i s o no f t h e i rs t r e a m i n gm e d i as e r v i c e si ni m p r o v i n gt h eq u a l i t yo fc o n t r i b u t i o n s b a s e do n g a m et h e o r yf o rp 2 pm e d i as t r e a m i n g , a ni m p r o v e dg a m en o d ea l l o c a t i o na l g o r i t h mi s p r o p o s e d c o m p a r e dw i t h s e v e r a la d v a n c e dp 2 pm e d i as t r e a m i n gp r o t o c o l s ，t h ei m p r o v e d a l g o r i t h mc a n b eag o o dp 2 pm e d i as t r e a m i n gi ni m p r o v i n gt h eq 谳埘o fs e r v i c e m e d i as t r e a m i n g n o d ea l l o c a t i o ns t r a t e g ys t r u c t u r e d g a m e t h e o r y i n c e n t i v e s i i ，+： ， 一 。 南京邮电大学硕士研究生学位论文目录 目录 摘要i a b s t r a c t 目录i 第一章绪论1 1 1 课题的提出l 1 2 国内外研究现状：2 1 3 论文的主要工作和组织结构4 第二章p 2 p 流媒体技术6 2 1p 2 p 流媒体的系统模型6 2 2f 2 p 流媒体系统的分类。8 2 3 现存结构化的p 2 p 流媒体协议 2 3 1 单播树1 2 2 3 2 多播树1 4 2 3 3 非循环有向图( d a g ) l5 2 4 现存非结构化的p 2 p 流媒体协议1 5 2 4 1 完全非结构化1 6 2 4 2 混合非结构化的p 2 p 流媒体系统1 6 2 5 现存p 2 p 流媒体的激励机制1 7 2 6 博弈理论数学化的冲突分析方法1 9 2 6 1 不合作博弈游戏1 9 2 6 2 合作的博弈过程。2 0 2 7 本章小结2 1 第三章基于服务质量的p 2 p 流媒体节点分配策略。2 2 3 1 概览。2 2 3 2 现存节点分配策略的分析2 3 3 2 1 以提高系统的健壮性为目标。2 3 3 2 2 以优化网络拓扑聚集为目标2 3 i i i y ， f 南京邮电大学硕士研究生学位论文目录 3 2 3 以提高流媒体服务质量为目的2 4 3 3 面向p 2 p 流媒体服务质量的节点分配策略2 4 3 4 非循环有向图( d a g ) 协议系统d a g s t e r 2 6 3 4 1d a g s t e r 的节点分配策略行使规则2 6 3 4 2 算法“2 7 3 4 3 性能分析。2 9 3 5 基于博弈理论的节点分配策略g a m e 2 9 3 5 1c r d m e 协议的博弈理论模型。2 9 3 5 2 一个专属值函数3 3 3 5 3g a m e 的节点分配策略3 3 3 5 4c _ r d i n e 节点分配策略的性能分析3 5 3 6 面向流媒体服务质量的节点分配策略性能仿真3 6 3 6 1 仿真软件简介3 6 3 6 2p 2 p 流媒体协议的参数设置。3 9 3 6 3 反复比率的比较4 0 3 6 4 节点出口带宽作用的仿真4 3 3 7 本章小结4 6 第四章博弈理论的节点分配策略改进与仿真4 7 4 1g a m e 算法分析与改进4 7 4 2 仿真的环境变量设置4 8 4 3 仿真结果比较4 9 4 3 1 数据传输率的比较分析4 9 4 3 2 系统健壮性比较分析5 0 4 3 3 数据延时性能比较分析5 l 4 4 本章小结5 1 第五章总结与展望5 2 5 1 本文工作总结5 2 5 2 今后的研究方向5 3 至i 谢5 4 参考文献。5 5 攻读硕士研究生期间发表论文j 6 0 圣 v 4 南京邮电大学硕士研究生学位论文 第一章绪论 1 1 课题的提出 第一章绪论 p 2 p ( p e e r - t o - p e e r ) h 口对等网络在不到1 0 年的时间里迅速发展成为互联网最具有影响力 的应用。p 2 p 网络软件应用领域包括文件共享、网络音频、网络视频、协同计算、虚拟社 区等等。p 2 p 网络技术已经渗透到绝大多数i n t e m e t 应用领域中来，并且p 2 p 网络技术在其中 很多领域占据支配性的地位。而今，p 2 p 网络流量已占据当前i n t e m e t 超过一半的带宽资源， 成为名副其实的“改变i n t e m e t 的新一代网络技术”。 p 2 p 出现于1 9 9 9 年的世界上第一个应用性p 2 p 网络n a p s t e r 。在n a p s t e r 之_ 后，是一系列广 泛流行的p 2 p 网络软件：b t 、电驴电骡、s k y p e 等等。p 2 p 应用的成功，使得学术界于2 0 0 1 年开始关注和重视p 2 p 网络的研究，代表性的事件是关于c h o r d 、c a n 两大p 2 p 覆盖网模型 的两篇论文发表于国际网络通信领域顶尖会议s i c 记o m m o l 上。自此，全世界的网络、通 信、系统会议或期刊上都开始发表p 2 p 相关的论文，而p 2 p 网络的研究者逐年递增，p 2 p 网 络成为学术界不可忽视的重要研究领域。 流媒体是把连续的影像和声音信息经过特殊的压缩方式分成一个个压缩包，从流媒体 服务器向用户计算机连续、实时地传送。让用户一边下载一边观看、收听，而不需要等整 个压缩文件下载到自己的机器后才可以观看。该技术首先在用户端的计算机上创造一个缓 冲区，预先下载多媒体文件的部分数据作为缓冲，播放程序读取缓冲区内的数据进行播放。 在播放的同时，用户计算机在后台继续下载多媒体文件的剩余部分填充缓冲区。这样，当 网络出现抖动o i r e r ) ，实际连线速度小于播放消耗数据速度时，可以避免播放的中断，也 使得播放质量得以维持。所以流媒体最显著的特征是“边下载、边播放”。而流媒体数据 的传输方式也分为早期的c s 模式以及p 2 p 模式。 近年来以p 2 p 技术为核心的流媒体系统得到了广泛的应用。诸如网络电视、视频点播、 视频会议、远程教学、远程医疗等已经为越来越多的人所接受和熟悉。据调查，p 2 p 流量 占互联网流量的5 0 - 7 0 ，音视频文件的比例高达6 0 以上。在一个典型的p 2 p 流媒体的 应用协议中，一个媒体服务器可以服务于数以万计的用户，如此强大的服务能力源自于服 务器把媒体流数据分发给它的整个用户群体，而这些用户相应地把他们的媒体数据与其他 的用户以p 2 p 的方式进行分享。 南京邮电大学硕士研究生学位论文第一章绪论 对于p 2 p 流媒体系统而言，所谓的节点是指参与系统的终端。节点分配策略是指p 2 p 系统中当一个节点加入系统时，系统中已经存在一组具有该节点所需内容的其他节点，系 统将根据某种选择策略选择部分节点作为该节点的伙伴节点，该节点进一步与这些邻居节 点建立连接，获取数据，这种选择方式就是节点分配策略。节点分配策略是p 2 p 系统的核 心部分，这是节点的动态性决定的。正是这种动态性使得无法预先采用某种动态的方法来 处理这种问题，这与传统的依赖于固定服务器或路由器的节点分配方法差别很大，所以面 临更大的挑战性。 1 2 国内外研究现状 早期节点分配策略是作为整个系统的一个部分进行研究，不同的p 2 p 协议都有节点分 配策略的描述算法，目的是为了满足或改进系统性能。而随着p 2 p 技术的发展，节点分配 策略作为系统核心部分的重要性越来越凸现出来，因此一些科研人员把这一部分专门作为 一个专题进行研究。通过对已有的p 2 p 流媒体协议进行分析，根据节点分配策略可将其划 分为下面三种类别。 ( 1 ) 以提高系统的健壮性为目标 这种方法在该领域的早期研究中很常见，其中以随机选择策略的循环策略为主要代 表，循环策略拥有协议简单的特点，可以很好地保证系统的健壮性。随机选择策略即是从 邻居节点的可选节点中建立一个列表，列表头的节点为目标节点，一旦被选中则移动到列 表的尾部。早期的研究中，s p r e a d i t 和p e e r e a s t 1 】系统都尝试了这两种办法。这类方法的优 点是协议简单，能够保持系统的健壮性和网络负载均衡性，缺点是无法提供流媒体实时性 的保证，并且对流媒体最重要的指标即流媒体服务质量的整体改进不明显。 ( 2 ) 以优化网络拓扑聚集为目标 这类方法着眼于整体的p 2 p 系统，对于整体的p 2 p 流媒体系统，选择收看同一个节目的 用户节点构成了一个应用层上的覆盖网络，选择什么样的节点分配策略即会决定这个覆盖 网络的构造方式和数据分发路由，这便会对骨干网的流量和底层网络的利用率形成影响。 比如，同一国家的节点收看同一个节目，如果他们不能互相发现，那便可能选择国外的节 点进行数据请求，这样做既造成了网络资源的极大浪费，同时又不能得到很好的流服务质 量，如图1 1 ( a ) 。因此p 2 p 系统需要改进自身，以缓解与i s p ) j 艮务商之间的矛盾冲突，作为 p 2 p 系统的核心模块，节点分配策略对系统的改进具有决定性影响。改进后的网络拓扑结 构如图1 1 ( b ) 所示，可以看到改进后的节点优先选择本区域的节点构建网络而不是跨区域 2 南京邮电大学硕士研究生学位论文 第一章绪论 寻找邻居节点。 ( a ) 改进前的拓扑 ( b ) 改进后的拓扑 图1 1p 2 p 流媒体系统的拓扑结构 国内的研究进展中，以华中科技大学的a n y s e e 和中科院研究所的b i g m e d i a 为代表的流 媒体系统，在面向网络拓扑聚集方面拥有很好的表现。其中华中科技大学a n y s e e 视频直播 系统使用“路标 系统，通过对“路标 识别尽量返回给请求节点地理位置较近的接收节 点，从而保证距离近的节点间能够相互形成稳定的拓扑聚集。 中科院计算所的b i g m e d i a 直播系统也是基于网状结构的p 2 p 流媒体系统，通过采用运 营商一地区相结合的二维向量与m 映射的方法，当节点加入系统并发出数据请求时，尽量返 回与请求节点同一区域的节点，从而有效减少跨越骨干网的p 2 p 流量。 ， - - _ - - _ _ _ _ _ - - - _ _ _ _ _ _ _ _ _ - - _ - _ _ _ _ _ - _ _ - ，一 南京邮电大学硕士研究生学位论文第一章绪论 网络拓扑时按照本地优先选择节点，这类方法能增强节点的网络拓扑聚集性，减少穿 越骨干网的流量，提高网络利用率。缺点是缺乏自适应于网络环境动态变化的能力，对于 节点间带宽分布不均衡问题考虑的还很不够。 ( 3 ) 以提高流媒体服务质量为目的 以提高流媒体服务质量为目标是目前p 2 p 流媒体系统采用的主要办法，这类方法能够 考虑到候选节点的性能差异，所选的性能参数主要有带宽、延迟、丢失率等网络参数，以 及自定义参数，通过候选节点和请求节点之间的性能关系选择最佳节点。对于每个节点， 通过获得邻居节点集合，与邻居节点交换数据得到媒体流。邻居节点的能力和它们之间连 接链路的性能，极大程度地影响了节点获取流服务的质量。这类方法的优点是能充分考虑 网络中节点的异构性和动态性，选择能力强的节点，因此能极大地提高节点的流服务质量。 在流媒体系统中，流服务质量是评价系统性能的最重要的参数。好的流媒体系统应该 以提高系统的流服务质量为基础，并同时尽量提高系统的健壮性、网络负载均衡性。在已 存在的节点分配策略中，有随机选择策略，最小延时策略和带宽优先判定策略。而这三种 方法中，由于带宽优先策略对流媒体服务质量的贡献最大，因此带宽优先判定策略成为现 有系统的主要选择，如o v e r t 鲫p ，c o o l s t r e a m i n 9 0 1 ，d a g l 6 1 ，g a m e l 5 1 等系统都在实际使用 中采用了带宽优先判定策略。 1 3 论文的主要工作和组织结构 本文在对p 2 p 流媒体系统进行了深入的研究的基础上，主要完成了以下工作： 1 、对各种p 2 p 流媒体协议分类成结构化模型的单播树、多播树、非循环有向图( d a g ) 、 博弈理论( g a m e ) 结构以及非结构化模型的完全结构化、混合结构化结构。并且分析各种协 议在选择父节点与子节点时的异同点。 2 、比较各种现存的p 2 p 流媒体协议的节点分配算法的优劣，特别着重比较它们在提 高流媒体服务质量方面所做的贡献，主要评价指标为数据传输比率、系统健壮性、平均包 延时等。通过比较发现早期的单播树节点分配策略如o v e r c a s t ，p r o m i s e 具有结构简单，系 统开销小的优点，但是流媒体数据传输率较低，系统健壮性很弱，很容易受到系统动态性 影响，在流媒体服务质量方面没有保障。而d a g s t e r 和g a m e 策略基于较复杂的单向图结 构，能够更好地考虑到节点带宽异构性的影响，而g a m e 协议的数据传输率较d a g s t e r 高， 因此有着更高的流媒体服务质量，但是其系统健壮性要劣于d a g s t e r 。 3 、对基于博弈理论的g a m e 节点分配算法提出改进措施，主要在节点分配过程中，对 4 南京邮电大学硕士研究生学位论文第一章绪论 请求加入系统的节点带宽进行最小带宽贡献约束，本文提出的改进的g a m e 协议是在原有 算法的基础上，对请求加入系统的节点进行最小带宽阈值判定，旦节点出口带宽贡献量 小于某个阈值，就将它剔除出系统，以便维护整个系统的流媒体表现性能。改进后的系统 将与现存的几种较先进的p 2 p 流媒体协议进行比较，通过仿真结果可以看出改进的g a l l i c 协议在系统健壮性，数据传输比率方面与原c _ r d m c 协议相比拥有着较好的性能表现，总体 上还是提高了系统的流媒体服务质量，能够很好地保障p 2 p 流媒体系统的性能。 4 、在算法仿真方面，采用一种以o v e r s i m 为核心的复合仿真平台。简单介绍了o v e r s i m 复合仿真平台的功能、结构和使用。重点通过o v e r s i m 进行仿真实验，对各种p 2 p 流媒体 系统的节点分配策略进行比较。文章最后指出了改进后的算法研究中存在的不足，和下一 步的研究方向。 论文的结构安排如下： 第一章主要介绍p 2 p 流媒体节点分配策略课题的提出，课题的国内外研究现状和研 究意义。 第二章介绍了p 2 p 流媒体系统的概念和体系结构，在这一章主要介绍了本文的一些 背景知识，列举了现存p 2 p 流媒体协议，把现存的p 2 p 流媒体协议分为两个类别：结构化 和非结构化。并且描述了一些具有代表性的结构化和非结构化p 2 p 流媒体协议，以及现存 p 2 p 流媒体中的激励机制和p 2 p 流媒体研究中所需要的博弈理论的一些基本知识，从而为 改进一种基于博弈理论的p 2 p 流媒体协议g a m e 协议做好理论铺垫。 第三章对基于服务质量的p 2 p 流媒体节点分配策略进行比较仿真，着重比较结构化 和非结构化p 2 p 流媒体中单播树、d a g 、非结构化和g a m e 协议在系统健壮性、平均包延 时等几项评价流媒体服务质量的指标上的表现。 第四章对基于博弈理论的p 2 p 流媒体协议g a m e 协议的节点分配策略进行分析，总 结其优缺点。在此基础上提出一种改进的g a m e 协议，主要是增加了阈值判断系统以应对 过分限制自身带宽的节点对系统性能表现的不良影响。改进的g a m e 协议在系统健壮性、 数据传输比率方面与原g a m e 协议相比拥有着较好的性能表现，总体上还是提高了系统的 流媒体服务质量。 第五章对全文的工作进行总结，分析并指出算法存在的不足和进一步研究的方向。 5 南京邮电大学硕士研究生学位论文 第二章p 2 p 流媒体技术 第二章p 2 p 流媒体技术 这一章主要提供了论文研究课题的背景知识。首先给出了现存p 2 p 流媒体的系统模型， 讨论了对现有p 2 p 流媒体协议的分类。另外分别描述了具有代表性的结构化和非结构化的 p 2 p 流媒体协议，以及现存的p 2 p 流媒体协议的带宽优先激励机制。最后，简要介绍一下 在p 2 p 流媒体节点分配的合作机制和不合作机制中用到的博弈理论。 肇f i 4 p 4 )节j 氛3 ( p 3 ) 图2 - 1p 2 p 流媒体的系统模型 2 1p 2 p 流媒体的系统模型 p 2 p 流媒体的运作过程如下：首先一个媒体供应商会把媒体信息存储在媒体服务器中 以便于服务与大量的用户。而媒体服务器所能服务的用户的数量是有限的，这是由于它的 出1 ：3 带宽是有限的，这便不能满足某些客户的需求。而p 2 p 流媒体的出现很好地解决了这 个问题，而且其花费的代价也是很小的，但是效果确实很明显，因为它可以把大量的媒体 内容分发给一些用户，而这些用户继而也成为了提供媒体信息的节点，然后再传递给其他 用户，图2 1 描述了p 2 p 流媒体的系统模型。这里面有三个重要的实体：媒体内容，服务 器和节点。可以把他们的功能描述如下： 1 ) 媒体内容包含了音频和视频信息的融合，这些可以由服务器分发给所有的节点。媒 体内容以恒定的比特率格式进行编码，假定为，k b p s 。而为了有效地分发数据，服务器可 6 南京邮电大学硕士研究生学位论文 第二章p 2 p 流媒体技术 以把媒体内容分割成相同大小的数据包。这也就意味着每一个媒体包携带了相同量的信 息。这样每一个节点编拥有了各自的重放缓冲区来存放缓冲的数据。在等待新的媒体数据 的时候，节点便可以先播放缓冲区中的数据，其播放的比特率为，k b p s 。可以想到p 2 p 流 媒体的性能表现将取决于是否能在缓冲区的数据播放完毕后接受到新的媒体数据并进行 播放。 2 ) 一个服务器节点为所有的节点提供媒体内容。也许有的时候服务器不止一个，但现 在只讨论拥有一个服务器的情况。服务器在不超过其出口带宽的情况器把数据分发出去， 而根据当今的媒体需求，可以认定需要媒体数据的用户节点是非常庞大的以至于单靠服务 器本身来为所有节点提供服务几乎是不可能的事情，但是可以考虑服务器为一少部分节点 提供服务的情况。也就是说，最有限的资源是服务器的出口带宽，并且在提供媒体数据的 同时，服务器还要处理其他的数据，比如相应节点的请求，处理节点的行为等等，从这一 点来看，服务器所能服务的节点数量就更有限了。 3 ) 一个用户节点当然只关心的是能从服务器取得怎样的媒体数据，先前假定的服务器 的媒体流比特率是，k b p s ，那么这里也要假定用户节点的入口带宽要高于，k b p s 。这也就 是说，入口带宽不会成为p 2 p 流媒体性能表现的瓶颈。在这里面，每一个节点都可以自主 控制其出口带宽，也就是说他们可以自行决定为p 2 p 流媒体系统提供多少贡献，一个极有 可能出现的情况是用户节点接受的带宽肯定会大于他们想要贡献的带宽。 正是由于用户节点数量的庞大，服务器根本不可能为所有的节点直接提供服务，因为 它的带宽资源是有限的。那么如前所述，服务器可以把它的媒体数据先发送给一部分节点， 这些节点称为直接节点，而直接节点下一步便可以把媒体数据分发给其他的节点，然后， 流媒体的数据以这种方式继续传递下去。最后，所有的节点都将得到由服务器提供的原始 数据流。注意到大部分现存的p 2 p 流媒体协议目标都是非交互式的方法，即避免信息的循 环传递，这样相当程度的延时可以认定为数据在媒体网络中的缓存与传递的时间。既然如 此，那么保证服务质- m ( q o s ) 的重点便是要确保有效的带宽资源为所有的节点来传递一个合 理的媒体流。特别低，每一个节点都应该可以接受到保持在有效的媒体比特率的数据。 由图2 2 可以看至u p 2 p 流媒体的工作原理。服务器节点，用睐表示，把媒体数据分发给 两个节点，p 2 和p 5 ，p 2 和p 5 都是直接节点。s 的出口带宽被完全的利用了起来，让这两个 直接节点为其他节点来提供服务，如图2 3 所示，p 2 把媒体数据分发给p 1 和p 3 ，而p 5 把媒 体数据分发给p 4 和p 6 。如果还有没有服务到的节点，这个服务步骤将会继续进行下去。这 样的话，节点便可以以一个合理的过程来形成网络布局来传递p 2 p 流媒体数据。实际上， 已经有很多不同的协议提出来去形成这个服务网络，将会在下一节来进行介绍。 7 南京邮电大学硕士研究生学位论文 1 第二章p 2 p 流媒体技术 节点4 ( p 4 ) 节点3 没有博弈者可以通过从其选择的机制中来提高自身的盈利时，就 认为达到了纳什均衡。但是同时要满足下面的条件： o ) - u t ( i ，墨，) 墨，f ( 2 - 1 ) 注意到博弈者知道其他选手的效用函数， 点都独立地选择能够最大化自身效用的机制。 1 9 但是他们之间并没有合作，也就是说每个节 总体来讲，一个博弈过程可能有任何纳什均 南京邮电大学硕士研究生学位论文 。 第二章p 2 p 流媒体技术 衡的值，也就是从0 到无穷大a 为了把某个特定的方法建模成不合作的博弈过程，应该首 先设计一个能够导出不止一个的纳什均衡的效用函数，用下面的例子来说明： 考虑到有两个犯人被单独进行审问，他们彼此不能相互通信，同时也不能否认和承认 对他们的指控，这叫做囚徒的选择，是一种典型的二人不合作博弈。博弈者是这两个犯人， 彳和占。每个博弈者可选择的博弈空间包含两个：否认和承认。用表2 2 来表示博弈情况， 其中o ，力表示彳的输出为z 而曰的输出为y 。 表2 1 犯人博弈选择的输出矩阵 b 选择“否认”b 选择“供认” 彳选择“否认” p ，6 )( 西口) 彳选择“供认” ( 口力( c j c ) 注意到a ，b ，c 和d 是一些常量并且驴6 殄d 。显然地，最优的输出结果是两个犯人 都选择否认指控，这将导致结果( 6 ，。但是这个输出结果是不稳定的，因为每个犯人都 可以选择供i a ( a b ) 来提高自身的输出如果一个犯人选择忏悔那么另一个犯人也会选择忏 悔因为c d 。因此，两个犯人都会选择忏悔，从而达到唯一的纳什均衡状态。 2 6 2 合作的博弈过程 一个合作的博弈过程包含了一系列的博弈者，定义为：= 1 ，啦。但是它们不像不 合作博弈过程那样独立行动而是形成不同的聚类。既然有万个博弈者，那么也就有矽个可 能的聚类。每一个聚类都包含一系列的博弈者，有c ，这些聚类与一个值相关，这些 值是由一个特征函数1 ，来决定的。换句话说，聚类的值c 是由v ( o 来定义的。通过协定， 可以假定空集的值为零即v ( 囝) = 0 。注意到v 矧只代表了c 中的博弈者形成的效用值。既 然这个值函数是非递减函数，那么v o v ) n 是代表有所有的博弈者形成的最大的效用值。而 对满足下列条件的效用函数将给予更多关注： k c , u c , u - ) v ( q ) ( 2 2 ) 解决办法包含两个方面，第一部分是聚类的形成。第二部分是为聚类分配值v f j 回。特 别地，为博弈者f 分配的值定义为m 。博弈者被认为是自私的但是也是理性的实体。每个 博弈者的目的都是最大化自身的值。同样，问题就在于怎样分配v 以使得相关的博弈者 不会离开聚类。一个较为流行的解决概念是“核心 。当满足下面两个条件时，分配方案 南京邮电大学硕士研究生学位论文 、 第二章p 2 p 流媒体技术 就可以认为是处于游戏的核心：。+ 坼= ，( c ) 。 ( 2 3 ) v i 毫- c 1 j ：f 1 ，( c 7 ) v c 7c _c(2-4) v i e c ： 第一个条件保证了聚类的值能够分配给所有的博弈者，这也是为了稳定性的需要。第 二个条件意味着博弈者不能通过加入其它聚类来提高自己的值，也就是说，博弈者最好的 选择就是在原聚类中与其他节点合作。因此，节点不会单独或成群地离开聚类，从而保证 聚类的稳定性。可以用下面的例子来看一下具体是怎样实现的： 考虑到在这个方案中有三个施工者和一个工程，这个工程不能单独地有某个施工者来 完成。如果三个施工者都参与到工程中来他们将创造一个单位的收入。如果只有两个人参 与进来，这个收入减少到口。可以把这个方案比喻成一个合作的博弈过程，每个施工者都 相当于一个博弈者。基于以上的描述，这个特征值函数描述如下： 旧= 1 f i c l = ( 2 - 5 ) 定义分配给i 的收入记为，这里面f = 1 ，2 , 3 。如果有三个博弈者形成一个聚类，那 么便希望知道它们之间是怎样分配收入的。首先，要求h + 吃+ 屹= l ，其次对于任意的f ， j 要满足条件+ 匕 t z 如果口2 3 ，博弈者就能得到一个定值，这样这个聚类就是稳 定的。 2 7 本章小结 在这一章主要介绍了本文的一些背景知识。第2 2 节列举了现存p 2 p 流媒体协议，这 也是第三、四两章研究的基础。在2 3 节，本文把现存的p 2 p 流媒体协议分为两个类别： 结构化和非结构化。在2 4 和2 5 节描述了一些具有代表性的结构化和非结构化p 2 p 流媒 体协议。在2 6 节介绍了现存p 2 p 流媒体中的激励机制，在2 7 节介绍了博弈理论的一些 基本知识，从而为改进一种基于博弈理论的p 2 p 流媒体协议g a m e 协议做好理论铺垫。 2 1 南京邮 第三章基于服务质量的p 2 p 流媒体节点分配策略 3 1 概览 随着互联网成为日常生活的一个核心组成部分，人们越来越多地依赖它来获取或交换 信息。最近几年一个常见的趋势便是流媒体在网络上的应用，特别是p 2 p 流媒体数据的应 用，成为流媒体应用较新的手段。在一个典型的p 2 p 流媒体的应用协议中，一个媒体服务 器可以服务于数以万计的用户，如此强大的服务能力源自于服务器把媒体流数据分发给它 的整个用户群体，而这些用户相应地把他们的媒体数据与其他的用户以p 2 p 的方式进行分 享。 p 2 p 流媒体系统中的节点分配策略是指节点加入系统时，从具有所需内容的其他节点 集合中挑选邻居节点所采取的决定策略。p 2 p 流媒体系统结构图如图3 - l 所示。节点分配 策略是p 2 p 系统的核心部分，这是节点的动态性决定的。正是这种动态性使得无法预先采 用某种动态的方法来处理这种问题，这与传统的依赖于固定服务器或路由器的节点分配方 法差别很大，所以面临更大的挑战性。 在流媒体系统中，流服务质量是评价系统性能的最重要的参数。好的流媒体系统应该 以提高系统的流服务质量为基础，并同时尽量提高系统的健壮性、网络负载均衡性。在已 存在的节点分配策略中，有随机选择策略，最小延时策略和带宽优先判定策略。而这三种 方法中，由于带宽优先策略对流媒体服务质量的贡献最大，因此带宽优先判定策略成为现 有系统的主要选择，如o v e r c a s t e ，c o o l s t r c a m i n g 3 ，d a g 7 ，o a m e 5 等系统都在实际 使用中采用了带宽优先判定策略。 图3 - 1p 2 p 流媒体系统结构图 南京邮电大学硕士研究生学位论文 第三章基于服务质量的p 2 p 流媒体节点分配策略 3 2 现存节点分配策略的分析 早期节点分配策略是作为整个系统的一个部分进行研究，不同的p 2 p 协议都有节点分 配策略的描述算法，目的是为了满足或改进系统性能。而随着p 2 p 技术的发展，节点分配 策略作为系统核心部分的重要性越来越凸现出来，因此一些科研人员把这一部分专门作为 一个专题进行研究。通过对已有的p 2 p 流媒体协议进行分析，根据节点分配策略可将其划 分为下面三种类别。 3 2 1 以提高系统的健壮性为目标 这种方法在该领域的早期研究中很常见，其中以随机选择策略的r o u n d r o b i n 循环策 略为主要代表，r o u n d r o b i n 拥有协议简单的特点，很适合于保证系统的健壮性。随机选 择策略即是从邻居节点的可选节点中建立一个列表，列表头的节点为目标节点，一旦被选 中则移动到列表的尾部。r o u n d - r o b i n 循环策略如图3 - 2 所示。早期的研究中，s p r e a d i t 和 p e e r e a s t t l 】系统都尝试了这两种办法这类方法的优点是协议简单，能够保持系统的健壮性 和网络负载均衡性，缺点是无法提供流媒体实时性的保证，并且对流媒体最重要的指标即 流媒体服务质量的整体改进不明显。 图3 - 2r o u n d - r o b i n 节点分配策略 3 2 2 以优化网络拓扑聚集为目标 这类方法着眼于整体的p 2 p 系统，对于整体的p 2 p 流媒体系统，选择收看同一个节目 南京邮电大学硕士研究生学位论文第三章基于服务质量的l 2 p 流媒体节点分配策略 的用户节点构成了一个应用层上的覆盖网络，选择什么样的节点分配策略即会决定这个覆 盖网络的构造方式和数据分发路由，这便会对骨干网的流量和底层网络的利用率形成影 响。比如，同一国家的节点收看同一个节目，如果他们不能互相发现，那便可能选择国外 的节点进行数据请求，这样做既造成了网络资源的极大浪费，同时又不能得到很好的流服 务质量。i s p 0 n t e m e ts e r v i c ep r o v i d e r ) 调查报告指出p 2 p 系统中7 0 0 , - - - 9 0 是穿越骨干网的 传输，导致它们对p 2 p 的网络流量加以限制，因此p 2 p 系统需要改进自身，以缓解与i s p 服务商之间的矛盾冲突，作为p 2 p 系统的核心模块，节点分配策略对系统的改进具有决定 性影响。国内的研究进展中，以华中科技大学的a n y s e e e i o 】和中科院研究所的b i g m e d i a 为 代表的流媒体系统，在面向网络拓扑聚集方面拥有不俗的表现。其中华中科技大学a n y s e e 视频直播系统使用l a n d m a r k 值作为调度路径上的“路标 ，通过对l a n d m a r k 的识别尽量 返回给请求节点地理位置较近的接收节点，从而保证距离近的节点间能够相互形成稳定的 拓扑聚集。 中科院计算所的b i g m e d i a 直播系统也是基于网状结构的p 2 p 流媒体系统，通过采用 运营商地区相结合的二维向量与口映射的方法，当节点加入系统并发出数据请求时，尽 量返回与请求节点同一区域的节点，从而有效减少跨越骨干网的p 2 p 流量。 3 2 3 以提高流媒体服务质量为目的 以提高流媒体服务质量为目标是目前p 2 p 流媒体系统采用的主要办法，这类方法能够 考虑到候选节点的性能差异，所选的性能参数主要有带宽、延迟、丢失率等网络参数，以 及自定义参数，通过候选节点和请求节点之间的性能关系选择最佳节点，该类方法将在下 一节详细阐述。 3 3 面向p 2 p 流媒体服务质量的节点分配策略 p 2 p 流媒体服务质量是评价系统好坏的重要标准，好的系统应该以提高流媒体服务质 量为基础，同时也要考虑到网络健壮性，负载均衡性和网络资源的利用率等指标。视频流 的应用层q o s ( q u a l i t yo f s e r v i c e ) 参数可通过用户的实际感官，对图像分辨率、图像锐化、 视频流传输的连续性等进行评价，但是在系统中难以自组织的统计和获取。因此，采用网 络端到端q o s 参数来评价系统的流服务质量，计算在有限时间内，节点实