（计算机应用技术专业论文）基于p2p流媒体点播系统的磁盘缓存策略研究.pdf

哈尔滨理工大学工学硕士学位论文 基于p 2 p 流媒体点播系统的磁盘缓存策略研究 摘要 近年来，随着宽带网的高速发展，流媒体内容的服务日益受到宽带用户的 青睐，其中基于p 2 p 网络的流媒体技术成为当前研究的热点。而流媒体数据对网 络的巨大带宽消耗，使得运营商的网络资源越来越紧张，服务质量也越来越差。 而p 2 p 技术采用完全分布式结构，这种技术弱化了服务器的作用，甚至取消服务 器，网络中的节点既可以获取其他节点的资源或服务，同时又是资源或服务的 提供者。 本文针对大规模p 2 p 流媒体点播中的一项关键技术一盘缓存进行了深 入的研究。本文主要完成以下工作： 首先，针对提高用户观看质量的需求与降低骨干网带宽消耗的矛盾，在p 2 p 文件共享多源协同流调度思想的启发下，提出了一种基于经济模型的分布式缓 存策略，策略通过采用分布式一致性算法计算视频分段的流行度，并根据分段 内容流行度高低对缓存分段进行缓存置换，实验结果表明，这种算法有效降低 了服务器的负载，显著降低了启动延时，比传统的分段缓存方法有更好的性能。 其次，在衡量被请求的数据分段的存储位置与结点对之间的通信频率的基 础上，研究并设计了与缓存策略相关的缓存副本分布策略和缓存副本概率一致 性策略，详细介绍了设计思想和策略特点。 最后，针对目前仿真软件不能有效模拟点播行为，在分析了传统的仿真器 的基础上，设计并开发了适用于本策略的仿真器，详细说明了各模块的作用， 并对所需参数的设置进行了说明。通过用其对传统缓存策略和本文策略对比， 说明其有效性。 关键词p 2 p 流媒体；分布式缓存；内容流行度；点播 啥尔滨理工大学工学硕士学位论文 暑暑鲁暑量置詈葛詈詈盲e 詈暑暑暑詈詈詈= = 詈詈暑篇皇暑= 詈暑= = 詈皇詈詈詈詈詈= 詈皇暑詈皇= = 暑皇詈詈詈詈詈詈詈詈= 暑皇暑暑詈詈置量蟹詈昌= 皇= = 詈詈詈詈昔置置墨, m ! r e s e a r c ho nd i s kc a c h i n gs t r a t e g yb a s e do nap 2 p s t r e a m i n g m e d i av o d s y s t e m a b s t r a c t i nr e c e n ty e a r s ，晰t ht h er a p i dd e v e l o p m e n to fb r o a d b a n dn e t w o r k , s t r e a m i n g m e d i ac o n t e n ts e r v i c e sa r ei n c r e a s i n g l yw e l c o m e db yb r o a d b a n dc u s t o m e r s p 2 p n e t 、) v o r ks t r e a m i n gm e d i at e c h n o l o g yh a sb e c o m et h ef o c u so fc u r r e n tr e s e a r c h m s t r 鬏m f i n gm e d i ad a t ac o n 霸n 骼h u g en e t w o r kb a n d w i d t h , w h i c hc a u s t 络m o l o s h o r t a g eo ft h eo p e r a t o r sn e t w o r k 豫渊，a n dw o r s eq u a l i t yo fs e r v i c e a n dp 2 p t e c h n o l o g yu s c sf u l l yd i s t r i b u t e da r c h i t e c t u r e , w h i c hw e a k e n sa n do v e nc a n c e l st h e f u n c t i o no ft h es f i l v e l , n e t w o r kn o d e sc a na c c e s st h er e s o u l ( ：i g so fo t h e rn o d e s0 1 s e r v i c e , a tt h es a r n et i m e , t h e y 趣a l s o 删d i nt h i sp a p e r , w ed i dad e e pr e s e a r c h0 1 1t h ek e yt e c h n o l o g yo ft h el a r g e - s c a l e p 2 ps t r e 2 a n i n gm e d i av o ds y s t e m , w h i c hi st h ed i s kc a c h e t h em a i nw o r ki sa s f o l l o w i n g ： f i r s t l y , i nv i e wo fc o n t r a d i c t i o nb e t w e e ni m p r o v i n gq u a l i t yt om e e tt h eu s e i w a t c ha n dr e d u c i n gt h eb a c k b o n eb a n d w i d t hc o n s m n p t i o n , a n di n s p i r e db yp 2 p f i l e - s h a r i n gi nm u l t i - s o u r c ec o l l a b o r a t i o nf l o ws c h e d u l i n gt h o u g h t , t h i sp a p e r p 磁鼬ac a c h i n gs t r a t e g yb a s e do no c o n o m y m o d e lf o rd i s t r i b u t e ds t r e a m i n gm e d i a i tu $ o sd i s t r i b u t e dc o n s i s t e n c ya l g o r i t h mc o m p u t e st h ep r e v a l e n c eo f v i d e os e g m e n t s ， a n di na c c o r d a n c ew i t ht h ec o n t e n t so ft h el e v e lo fp o p u l a r i t y , w h i c hg i v e st h e c o r r e s p o n d i n g c a c h er e p l a c e m e n ts t r a t e g y e x p e r i m e n t a lr e s u l t ss h o wt h a tt h e a l g o r i t h mc a ne f f e c t i v e l yr e d u c et h el o a do ft h es 廿v e r ，a n ds i g n i f i c a n t l yr e d u c et h e s t a r t u pd e l a y , a n dh a sb e t t e rp e r f o r m a n c et h a nt h et r a d i t i o n a ls e g m e n t e d - c a c h e m e t h o d s e c o n d l y , e x , n s i d e r i n gb o t hd a t as t o r a g el o c a t i o na n dt h ed i s t a n c eb e t w e e n r e q u e s t e ra n dr e s p o n d e r , t h i sp a p e rr e 蝴c h a n dd e s i g nt h es t r a t e g i e sa s s o c i a t e dw i t h t h ec a c h et h ec a c h e dc o p yo fac o p yo ft h ed i s t r i b u t i o ns t r a t e g ya n dt h ep r o b a b i l i t yo f c a c h ec o h e r e n c es t r a t e g y , i n t r o d u c e dt h ec h a r a c t e r i s t i c so fd e s i g nt h o u g h ta n d i i 哈尔滨理工大学工学硕士学位论文 s t r a t e g yi nd e t a i l f i n a l l y , a c c o r d i n gt ot h es i t u a t i o nt h a tt h ec u r r e n ts i m u l a t i o ns o r w a r ec a nn o t e f f e c t i v e l ys i m u l a t et h ev i d e oo n - d e m a n db e h a v i o r , t h i sp a p e rd e s i g n sa n dd e v e l o p sa t h es i m u l a t o rs u i t a b l ef o rt h es t r a t e g yo nt h eb a s i so fa n a l y z i n gt r a d i t i o n a ls i m u l a t o r , a n de x p l a i n st h er o l eo fe a c hm o d u l ei nd e t a i la n da l s om a k e sa r te x p l a n a t i o no f s e t t i n gu po fr l u i r o dp a r a m e t e r t h i sp a p e ri l l u s t r a t e si t se f f e c t i v e n e s sb yc o m p a r i n g t r a d i t i o n a ls t r a t e g yo f c a c h i n ga n ds t r a t e g yo f t h i sp a p e r p e e r - t o - p e e rm e d i as t r e a m i n g , d i s t r i b u t e dc a c h e , c o n t e n tp o p u l a r i t y , v i d e oo nd e m a n d 一i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文 ，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期 间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包 含他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体， 均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：冲咖。秽日期：弘即年弓月加日 l 哈尔滨理工大学硕士学位论文使用授权书 基于p 2 p 流媒体点播系统的磁盘缓存策略研究 系本人在哈尔滨理工大 学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归 哈尔滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完 全了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有 关部门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大 学可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分 内容。 本学位论文属于 保密0 ，在年解密后适用授权书。 不保密彰 导师签名 沈 珈 月 月 )r、弓 年 年 卅砷 期 期 日 日 哈尔滨理工大学工学硕士学位论文 第1 章绪论 1 1论文的研究背景及意义 随着宽带网络的普及和个性化在网络时代的突出，网络流媒体近来已获得 极大发展。流媒体以其丰富的内容和特有的交互性，给人们的工作、生活和娱 乐带来了深刻的变化。最近几年来，p p l i v e 、p p s 仃e a m 、u u s c e 这样的网络电 视软件空前流行，引发了人们对流媒体技术的极大关注。 传统的p 2 p 流媒体应用多是基于c s 架构，其流媒体服务器实体可以是一 个服务器或者一组服务器和代理。随着上网人数的不断增加，网络带宽的瓶颈 和可扩展性差的特征就日益显现出来，表现为在播放的时候经常卡住，不断地 缓冲等等，严重地影响了多媒体内容的观看效果。为了解决系统的可扩展性问 题，许多研究都提出了相应的解决办法。应用层组播技术把服务器作为第一层 源节点，由其子节点作为第二层的源节点，向其它节点服务，从而降低了服务 器的带宽压力。应用层组播的缺点是，由于节点的加入退出，使树结构保持稳 定需要付出很大代价。用户的加入是随机的，所以控制拓扑与网络的物理拓扑 无关，需要交换大量信息来保证控制拓扑的稳定。c d n ( c o n t e n td e l i v e r yn e t w o r k ) n 1 基本思想是在网络边缘放置数据服务器，存储访问频率较高的热门资源，称为 边缘服务器。当用户请求时，数据就近从边缘服务器获取，不需要经过骨干网 络，从而降低了骨干网络的压力，同时提高了响应时间因为可以提前把资源 下载到边缘服务器，所以对于静态资源十分有效，很多大型网站使用c d n 技术 作为内容分发的手段。对于点播系统，由于影片的静态特性，可以发挥c d n 的 优势，这种方法代价比较昂贵，需事先建立庞大的c d n 网络。 随着p 2 p ( p e e r - t o - p e e r 口1 ) 的兴起，近几年，基于p 2 p 技术的流媒体业务发展 迅速。在p 2 p 网络中，所有的节点是对等的( 称为对等点) ，各节点具有相同的 责任与能力并协同完成任务，这种技术的一大特点在于加入的节点越多，节点 间为系统贡献的资源也越多，整个系统的服务能力也就越强，从而有效地减轻 了服务器的负载，极大地提高了系统的可扩展性。将p 2 p 引入流媒体服务，将 打破传统的c s 结构，有效地减轻服务器负载并可以很好的支持大规模流媒体 应用。根据研究和咨询公司i r e s e a r c h 2 0 0 7 公布的最新数据显示，2 0 0 7 年p 2 p 流媒体用户规模达到6 5 0 0 万，而到2 0 1 0 年时，这一用户规模将达到1 5 8 0 0 万 哈尔滨理工大学工学硕士学位论文 人。在市场需求的驱动下，p p l i v e 、p p s t r e a m 、q q l i v e 、u u s e e 等一批直播软 件便在这种条件下应运而生，并且在短短几年内得到了飞速的发展。 令人遗憾的是，如同电视点播的出现落后于电视直播一样，至今还未出现 一款成功的p 2 p 网络视频点播产品。究其原委，相比流媒体直播，用户的高度 交互性和数据的网络存储和缓存是挡在点播系统迈向成功的拦路虎。点播系统 就是应此需求而产生的。视频点播技术( v o d ) ，它是一种根据观众的要求播放 节目的系统，随时提供交互式视频服务，主要用于实现多用户对网络多媒体文 件的共享播放。 i n t e m e t 技术、网络和业务的发展从各方面改变了人们的学习、工作和生活 方式，给人们带来了巨大的便利，i n t e m e t 已经成为人们生活中不可缺少的一部 分，而p 2 p 的流媒体正是i n t e m e t 上非常成功一个重要应用。 通过p 2 p 流媒体点播系统，使“大家的电视一变成了“我的电视一，把“你 播我看 的方式变成了“我选我看 的方式，使得用户真正感受想看什么节目 片段就看什么节目片段的便利。 就像电视逐步取代传统的广播一样，随着网络技术的发展和宽带网的普及， 流媒体点播取代电视的时代即将到来，这是一个颠覆性的技术，流媒体点播将 形成一个极具前景的应用。 1 2 p 2 p 流媒体技术的研究现状 自从世纪9 0 年代末p 2 p 流媒体技术被提出以来，由于其流媒体服务的优越 性，基于它的各种应用得到了极大的关注。目前在视频直播、视频点播、视频 会议、i n t e r n e t 网络电视等方面已经取得了初步的良好应用。目前，互联网上最 火爆的p 2 p 流媒体技术应用是p 2 p 视频直播、点播系统。 1 9 9 8 年，美国学者在i e e em u l t i m e d i a 杂志上发表了第一篇关于利用p 2 p 技术 来实现大规模流媒体点播和直播系统的论文w e b c a s t 。w e b c a s t 的想法虽然很简单 ( 仅仅利用一棵二叉组播树在用户之间进行实时多媒体数据的传输和共享) ，但 其高度可扩展性和可行性给工业界和学术届的研究带来了极大的冲击。至此， p 2 p 流媒体技术的发展进入研究的萌芽期。 随着宽带网络接入技术的普及，普通个人电脑的计算能力和存贮能力不断增 强，众多研究机构都对基于p 2 p 的流媒体传输进行了研究，提出或开发了许多p 2 p 流媒体直播系统，如：美国斯坦福大学在早期提出t s p r e a d l t 体系嘲，该体系将 p e e r 组织成单一的组播树，利用p e e r 的资源转发媒体流。马塞诸塞大学则设计实 哈尔滨理工大学工学硕士学位论文 现了d i r e e t s t r e a m ，一个基于目录的视频直播系统，目录中维护了服务器的影 片信息索引以及组播树中所有p e e r 的信息，新的p e e r 加入时查找目录，若存在提 供其请求服务的组播树则加入相应的组播树，否则由服务器处取得服务并创建 新的组播树。微软研究院在继c o o p n e t 跚之后又设计t s p l i t s t r e a m 畸1 流媒体系统， 该系统以减小组播树内部节点的负载为目标，建立多棵组播树，每棵组播树的 内部节点是其它组播树的叶子节点，完整的媒体流被分割为均等的数据流在各 棵组播树上传送，这样将传统的单组播树中内部节点的转发负载分散到所有参 与组播的节点中。加州u cd a v i s 大学提出一种应用b i t t o r r e n t 协议的流媒体系统 b a s s 盯1 ，他在减少流媒体缓冲时间上作了很大贡献。 近年来，国内的p 2 p 流媒体的业务已经进入了一个快速发展期，每天都会有 新兴的p 2 p 厂家出现。比如：华中科技大学集群与网格计算实验室的n n y s 嘲 是p 2 p 直播系统之后推出的一款p 2 p 点播系统，它采用了一对多的服务模式，支 持部分n a t 和防火墙的穿越，提高了视频直播系统的可扩展性；同时，它利用 就近播放原则、分域调度的思想，使用l a n d m a r k 路标算法直接建树的方式构建 应用层上的组播树，克服了e s m 等一对多模式系统由联接图的构造和维护带来 的负载影响。p 2 v o d 悖1 是一款全新的p 2 p 流媒体播放软件，它具有延时小，全自 动穿透内网，支持内网间互联的的特性。p p s ( p p s t r e a m ) 2 0 0 7 年1 1 月8 日推出了 p 2 p 点播解决方案，p p s 流媒体服务器拥有p e e r r a n k 等多项专利技术，处于全球 领先地位，继承了h e l i x ，w i n d o w sm e d i as e r v e r 等传统非p 2 p 流媒体服务器的优 点，同时又支持服务器同步、c d n 、p 2 p 加速、分布式存储和远程管理等多种专 为高并发、海量用户设计的独有技术。能够轻松实现百兆带宽几万人同时在线。 虽然，这些系统和协议在实用过程中存在一些缺陷，但是原型系统的实用以及 基础协议研究工作的开展为p 2 p 直播技术进入商业领域运作打下了坚实的理论 基础。与此同时，p 2 p 技术在文件共享领域和数据存储领域也得到了广泛的应用， 这些应用为p 2 pm u l t i m e d i as t r e a m i n gs e r v i c e 的下一步发展提供了丰富的经验。 对于p 2 p 流媒体点播系统，缓存策略的好坏是基于p 2 p 流媒体点播系统能 否提供连续播放和交互的关键。因为点播系统是异步系统，请求者可能是新加 入系统的节点，也可能是一个需要暂停、快进、快退或拖动到新视频点的当前 节点。由于网络i o 的不稳定性及用户行为的随意性，使得可能产生如下问题： 在某一时刻视频信息的读取和播放速率不匹配，进而导致视频信息播放不稳定， 或者当用户执行v c r 操作时，引起缓存命中失效，造成长时间缓冲等待，将大 大增加启动和播放时延。为此需要采用一种高效率地存储策略及缓存策略来解 决这一问题。 哈尔滨理工大学工学硕士学位论文 1 3 论文的研究内容 本文在比较目前流行的流媒体缓存策略基础上。查阅大量文献，对p 2 p 点 播系统中的关键技术一媒体存储和缓存策略进行了深入的分析和研究，主要做 了如下几方面的工作： 1 通过查阅国内外各种p 2 p 流媒体技术的相关文献，深入研究了几种流 媒体系统理论，包括流媒体相关技术、点播系统分类、视频点播系统技术难点 及磁盘缓存策略等。 2 通过分析同一影片不同分段的分布规律，提出客户端采用了影片分段存 储的方式，研究了通用缓存理论及p 2 p 点播系统中典型缓存策略的应用。 3 深入研究了p 2 p 流媒体磁盘缓存策略，并提出了一种基于经济模型的流 媒体缓存策略。 4 针对这种缓存策略给出相应的替换算法，并设计了与缓存策略相应的副 本分布策略和副本概率一致性策略。 5 对分布式缓存策略进行了仿真测试，证明其有效性。 1 4论文组织结构及内容安排 第1 章主要介绍论文的研究背景和意义，给出本课题研究的重点及方向。 第2 章主要回顾了流媒体点播系统相关理论综述。重点介绍了流媒体相关 技术、点播系统分类和实现点播系统的技术难点。 第3 章详细描述了论文中通用磁盘缓存策略设计过程中要考虑的要素，并 结合典型缓存策略说明了目前存在的不足。 第4 章提出一种新的基于经济模型的分布式流媒体缓存策略，详细阐述了 模型设计并给出了相应的缓存替换算法。 第5 章对本系统和磁盘缓存策略进行了仿真实验，并对实验结果进行了分析 与评价。 哈尔滨理工大学工学硕士学位论文 第2 章流媒体点播系统相关理论综述 2 1流媒体相关技术 2 1 1概念 流媒体是一种可以使音频、视频和其它多媒体文件能在i n t e r n e t i n t r a n e t 上 以实时的、无需下载等待就可以进行播放的技术。简单的说，它就是把连续的 影像和声音信息经过压缩分成一个个的压缩包存储于服务器上，让用户可以一 边下载一边观看，而不需要等整个压缩文件下载到自己的机器后就可以收看。 为了消除网络连接速率的抖动，一般先在使用者端的电脑上创造一个缓冲区， 在播放前预先下载一小段，播放程序取用这一小段缓冲区内的数据进行播放。 在播放的同时，多媒体文件的剩余部分在后台继续下载填充到缓冲区。流媒体 技术并不是单一的技术，它是整合了很多网络技术之后产生的技术，它涉及到 流媒体数据的采集、压缩、存储、传输等多项技术。 2 1 2流媒体传输控制协议 流媒体数据在网络上传输需要合适的传输协议。流媒体在i n t e m e t 上传输涉 及的网络传输协议包括i n t e m e t 本身的多媒体传输协议，以及一些实时流式传输 协议等。i e t f ( i n t e m e t 工程任务组) 是i n t e r n e t 规划与发展的主要标准化组织， 已经设计出几种支持流媒体传输的协议。r t p ( r e a l t i m et r a n s p o r tp r o t o c 0 1 ) 主要 针对多媒体数据流的实时传输，实时传输控制协议r t c p ( r e a l - t i m et r a n s p o r t c o n t r o lp r o t o c 0 1 ) 是设计和r t p 一起使用的进行流量控制和拥塞控制的服务控制 协议，r t s p ( r e a lt i m es t r e a m i n gp r o t o c 0 1 ) 用于定义一对多的应用程序如何有效 地通过p 网络传送多媒体数据。 2 2p 2 p 在流媒体中的应用 对等网络( p e e r - t o - p e e r , p 2 p ) 是目前非常热门的应用，近几年，国内外的知名 学府和研发机构对p 2 p 进行了广泛的研究。它通过在不同计算机用户之间、不 经过中继设备直接交换数据或服务。这种网络通信方式打破了传统的 哈尔滨理工大学工学硕士学位论文 c 摁( c l i e 州s e r v 砷模式。在p 2 p 网络中，每个节点的地位都是相同的，可以作为 服务的使用者，同时也作为服务的提供者。p 2 ps t r o m n i n g ( p e e rt op e e rs t r e a m i n g m e d i a ) 即“点对点的流媒体技术。p 2 ps t r e a m i n g 是指以网络为传输介质，在对 等网络中以流媒体方式传输视频、音频等数据的技术。从技术角度来看，p 2 p 流媒体是流媒体技术和p 2 p 技术的结合。 p 2 p 流媒体技术在近几年中取得了飞速的发展，目前，p 2 p 视频直播和视频 点播( v i d e oo nd 既n a n d , v o d ) 是p 2 p 流媒体应用的两种表现形式。 2 2 1直播系统与点播系统 p 2 p 直播系统是利用p 2 p 基本原理来建立播放网络，它的特点是用户只能 被动收看，也就是说，系统播放什么，用户就观看什么。在直播系统中直接的 内容需要实时地从直接数据源获取，而且各个节点的播放进度相差不大，在同 一时刻，每个直播频道有成千上万的用户，因此，实时性要求很高的直播系统 来说，最重要的关键在于怎样选择带宽稳定、物理相近的节点来提供稳定服务。 不同于直播系统，p 2 p 点播系统中由于同一时间内观看同一影片的节点比较少， 并且即使在观看同一影片，由于加入时间的随机性，使得播放进度相差很大， 从而可以相互共享数据的节点数量很少，所以点播系统中的重点是怎样增加和 利用网络中已存在的数据。本文通过利用对等节点的分布式缓存解决了网络中 节点数量较少这一问题。 2 3点播系统的分类 2 3 1a s 结构 最早的视频点播系统通常采用c s 架构，这种架构的系统的结构及组成一 般可以分为三个部分：服务端系统，网络系统，客户端系统。 1 服务端系统视频服务器主要由存储系统和建立在其上的各种控制器管 理系统组成，其目标是实现压缩媒体数据的存储，以及按请求进行媒体信息的 检索和传输。视频服务器与传统的数据服务器在很多方面有显著不同，需要解 决许多问题，以求能够支持新功能，例如：媒体数据检索、信息流的实时传输 以及信息的加密和解密工作。对于交互式的v o d 系统来说，服务端系统还需要 完成诸如用户实时请求处理、允许控制服务等功能。 2 网络系统网络系统包含主干网络和本地网络系统两部分，是影响连续 哈尔滨理工大学工学硕士学位论文 媒体网络服务系统性能的关键部件。由于媒体服务系统的网络部分投资巨大， 所以在设计时不仅要考虑当前的媒体应用需要，而且还要考虑将来发展的需要 和兼容性。 3 客户端系统在客户终端主要解决硬件问题及处理与之相关的各种软件 技术问题。例如，为了满足用户的多媒体交互需求，客户系统的界面必须加以 改造。此外，在进行连续媒体演播时，媒体流的缓冲管理、音频和视频数据的 同步、网络中断与演播中断的协调等问题都要进行考虑。 传统d s 架构工作流程如图2 1 所示： 对等节点 图2 1 传统c s 模型 f i g 2 - ic l i e n t s e r v e rm o d e l 2 3 2纯分布式p 2 p 结构 对等节点 图2 - 2 纯p 2 p 模型 f i g 2 - 2p u r ep e e rt op e e rm o d e l 哈尔滨理工大学工学硕士学位论文 纯分布式p 2 p 模式完全取消了集中的中央服务器，每个用户随机接入网络， 并与自己相邻的一组节点端到端的连接，从而构成一个逻辑覆盖网络，节点之 间通过互相交换消息，得到系统局部的信息，其最大特点是，加入系统节点越 多，整个系统的容量也增大。另外，因为使用这种架构的点播系统不存在服务 器，每个对等节点地位是平等的，所以在纯p 2 p 系统中不存在单点瓶颈。但是， 随着系统中客户端数量的增加也意味着用户更慢的数据传输和更长的查找时 延。这种结构如图2 2 所示。 2 3 3混合结构 混合式模型p 2 p 拓扑结构是p 2 p 思想与c s 思想结合的产物。混合式p 2 p 拓扑结构没有集中的固定的服务器，而是引入了“超级节点 。超级节点是功能 介于服务器与普通节点之间的一类节点，它们单体性能较强，这跟服务器相似， 同时他们随机分散在p 2 p 网络中，并无确定位置，这和普通节点相似。节点的 元信息通过中心服务器维护，而具体内容则分散到各个节点上。这种模型既可 以利用c s 架构的优势，方便地对系统进行管理；也可以通过p 2 p 技术，把对 服务器压力最大的资源分散到各个节点上。 这种架构如图2 3 所示： 对等节点 对等节点 图2 - 3 混合p 2 p 模型 f i g 2 - 3h y b r i dp e e rt op e e rm o d e l 2 3 4c d n 与p 2 p 的混合点播系统 基于c d n 点播系统的优点是可以提前把影片推送到边缘服务器，节点可以 就近从服务器获取数据；p 2 p 系统的优点是利用节点的服务能力，降低服务器 哈尔滨理工大学工学硕士学位论文 的压力。把这两种技术相结合，提出了基于c d n 和p 2 p 技术的混合点播系统。 在这种模式中，每个节点在硬盘开辟存储空间，把用户观看过的数据有选 择的保存下来，利用这些静态数据提供服务，大大减轻了媒体服务器的压力。 这种架构如图2 - 4 所示i 对世节点对世节点对世节点对世节点 图2 _ 4 c d n 与p 2 p 的混合模型 f i g 2 - 4c d n a n dp e e rt op e e rh y b r i dm o d a l 2 4 视频点播系统技术难点 2 4 1 流媒体数据存储和内容分发 1 流媒体数据存储数据存储是视频点播实现的关键技术之一，在点播系 统中数据存储的设计主要从存储空间和读取速度两方面考虑。现行的数据存储 方式按数据存储的体系结构的不同可以分为三种：集中式、分布式和分段协作 存储n 0 1 ： ( 1 ) 集中式存储方式。也称为完全共享存储方式，它是典型的集群式结构视 频点播系统采用的数据存储方式。这种方式的每个视频服务器节点可以通过网 络直接访问所有的数据而不需要经过其它节点。这种方式最大的优势在于视频， 服务任务调度和迁移可以很容易实现，从而实现节点间的负载平衡；可以将节 点从数据存储管理的负担中解脱出来，实现数据处理和数据存储的分离，同时 对节点间的内部通信带宽可以不需要占用。 哈尔滨理工大学工学硕士学位论文 ( 2 ) 分布式存储方式。分布式存储有两种方式：一是分段协作存储方式，采 用条纹化技术将视频数据分布到每台视频服务器，此时所有服务器都参与服务； 二是完整存储方式，将数据完整独立地存储在某台视频服务器上，但一个节目 有可能同时保存在几台视频服务器，只是这些视频服务器上同一个节目的数据 互相不会影响。完整分布式存储方式根据节目在所有服务器的拷贝数量分为三 类：完全复制、垂直分割和完全自治。 ( 3 ) 分段协作存储方式。分段协作存储方式是一种非常好的存储方式，有多 种服务策略是将视频文件分成若干段进行服务的。对这种方式而言，存在两个 方面的问题。分段协作方式可以实现节目数据的低冗余甚至零冗余，而且使用 一定的服务策略可以实现服务器的负载均衡。这种方式也存在一些缺点：由于 节目分片存储在各个服务器中，如果任何_ 个服务器不能工作，将影响整个系 统。随着服务器和数据量的增多，系统发生故障的可能性很大；要想实现节目 数据的分段存储和管理需要有新的文件系统的支持，且这种方式下的服务策略 非常复杂，实现这些的工作量非常大。 2 流媒体数据分发在p 2 p 流媒体系统中，通常媒体流被分成多个数据段。 随着播放进度的前移，请求节点的邻居节点可能不能提供其需要的媒体数据段， 这是因为可提供服务的p e e r ：宵点的服务能力有限，不同p r 节点的服务能力具有 差异性，p e e r 节点还可随时退出系统，从而造成其他部分节点流传输的中断。 这会导致请求节点播放暂停，影响用户的播放体验。另外，p 2 p 流媒体技术本身 具有其特殊性，如有媒体数据的传输持续时间长，带宽资源占用高，以及接收 媒体数据时有较为严格的时限和顺序要求等。所以在内容分发研究过程中面临 非常严峻的挑战。为了高效的进行数据分发，人们提出了各种办法： ( 1 ) i p 组播技术，它实现了i n t e r n e t 上高效的一对多通信，提高了系统的可扩 展性。但由于p 组播也存在种种限制，并没有取得预期的成功。一方面，因特 网中的网络极少开放口组播业务，至今还没有大范围内的因特网组播业务；另 一方面，基于i p 组播的上层应用也屈指可数，相对于w w w 等新的体系结构，口 组播的发展非常缓慢。 ( 2 ) 应用层组播技术。由于i n t e r a c t 对网络层组播的支持不理想，人们把组播 的思想扩展到应用层，提出了应用层组播的概念。应用层组播的基本思想是屏 蔽底层网络的拓扑细节，将组成员节点直接自组织成一个逻辑覆盖网络，并在 应用层提供组播路由协议来构建和维护该网络，为数据传输提供高效、可靠服 务。由于对网络本身改变很少，应用层组播具有很好的灵活性。 ( 3 ) 内容分发网络( c d n ，c o n t e n td e l i v e r y n e t w o r k s ) ，媒体服务器将存储访问 哙尔滨理工大学工学硕士学位论文 频率较高的热门资源以推( p u s h ) 的方式存放在边缘服务器或c d n 服务器上，当客 户请求媒体服务器时，可从边缘服务器或c d n 服务器获得服务，而不必消耗服 务器的资源。因为可以提前把资源下载到边缘服务器，所以对于静态资源十分 有效，很多大型网站使用c d n 技术作为内容分发的手段。但这种方案只是部分 地解决了可扩展性问题，因为此时代理缓存或c d n 服务器很有可能成为系统瓶 颈。 ( 4 ) p 2 p ( p r - t o p e e r ) 技术。p 2 p 是一种网络模型，即对等网络，可以简单地 定义为通过直接交换共享计算机资源或服务，对等计算机兼有客户机和服务器 的功能。相对于传统的c s ( c l i e n t s e r v e r ) 模式，p 2 p 技术的出现是对服务器负载 的极大解放。在这种网络中所有的节点是对等的( 称为对等点) ，各节点具有相 同的责任与能力并协同完成任务。对等点之间通过直接互连实现信息资源、处 理器资源、存储资源甚至高速缓存资源等的全面共享，无需依赖集中式服务器 支持，消除信息孤岛和资源孤岛。p 2 p 技术在文件下载系统中得到了广泛应用， 如b t 、e m u l e 、m a z e n 2 1 等。 2 4 2 流媒体数据缓存 在p 2 p 流媒体分发系统中，每个p e e r 节点会将收到的媒体数据段在本地缓 存以供其邻居节点获取。对直播系统来讲，p e e r 节点的播放时序通常由视频源 的播出时序决定。虽然在某一时刻节点收到的视频数据相对视频源己有一定的 延迟，但在后续播放过程中与相邻的p e e r 节点播放时序相近，从而缓存的分片 内容重合度高，缓存处理相对较为简单。而对于点播系统，针对某一视频文件 初始的播放时序由每个节点加入系统时确定。在p e e r 节点加入系统时间点离散 的情况下，系统要存储的数据量是相当庞大的，在进行视频点播系统的设计时， 不仅系统的结构设计、服务策略的选择非常重要，系统数据的缓存策略同样是 非常重要的，数据的布局不仅会影响系统的服务性能，同时与服务策略也是紧 密相关的。各个节点更趋向于播放不同时间点上的视频内容，造成节点之间缓 存的数据段重合度低。如果系统中媒体数据缓存机制性能低下，节点将难以从 系统中其它p e e r 节点下载得到相应数据，而且会频繁地向服务器发起数据请求， 从而加重服务器的负载压力。因此，需要研究高效的媒体数据段缓存机制，通 过增加p e e r 节点自身的缓存服务能力，降低服务器的负载压力。 缓存策略就是确定媒体对象如何缓存于节点中，使得每个节点都可以高效 的访问任何媒体对象。这里“高效往往用一些指标来描述，如访问延时和访 哈尔滨理工大学工学硕士学位论文 问可靠性。但这些优化目标往往互相冲突，如果将网络看成一个整体，并在整 个网络上应用一种缓存策略很难满足相互冲突的各种需求，例如访问延时和访 问可靠性就彼此冲突。于是人们将对等网层次化，不同的层次有不同的需求起 主导作用，并据此需求设计相应的缓存算法。对网络中的节点分层是p 2 p 系统 地节点有效分组的一种思想，n 3 1 将思想整个对等网划分为两层：由若干相邻的 节点构成组；由所有组构成整个对等网。并分别设计了用于组内和组间的缓存 策略。具体的说，将彼此访问时延小于某一阈值的节点划为一个组，这样组内 媒体分发的关键就是提高访问的可靠性，相应的组内缓存策略就是优化这个指 标；而组间媒体分发的关键就是减少访问时延，相应的组间缓存策略就以这个 指标为优化目标。 2 4 3v c r 操作的实现 支持v c r n 4 1 操作已经成为流媒体服务中不可分割的一部分。然而，v c r 操 作具有以下两种特性：第一，用户进行的v c r 操作不同；第二，对于同一数据 流，v c r 操作起始的位置不同。这些特性增加了实现v c r 操作的难度。现有流 媒体服务器中的常见缓存算法没有能够考虑这些特性，仅仅通过单纯的补丁流 提供服务，造成的结果是在服务器负载和主干网带宽消耗方面均不能够达到令 人满意的效果。本文的分布式缓存策略有效的解决了点播系统中的v c r 操作。 2 5本章小结 本章首先介绍了流媒体相关技术的概念，然后详细介绍了点播系统的分类。 最后分析实现点播系统的技术难点，本章所介绍各个部分为以后本文将要阐述 的分布式缓存策略及其调度算法奠定了理论基础。 哈尔滨理工大学工学硕士学位论文 第3 章p 2 p 流媒体点播中缓存策略研究 3 1缓存策略要考虑的因素 缓存技术是计算机中普遍采用的基本技术之一，在p 2 p 网络中，缓存技术 的主要思想表现为：当发生资源请求时，首先到本地缓存中进行查询，如果命 中，则返回结果直接响应；否则，用户的请求将仍然通过路由机制导航到存储 所需求对象的目的节点上。然而，在海量的存储对象中间，访问频率却并不是 完全一致的。换言之，这些对象并不是等概率被访问的。研究表明，各个对象 的访问分布基本上遵循z i p f 定律n 钉，即大多数的访问集中在少数热点对象，而 大多数对象只得到很少的访问量。这从另一个角度阐述了对象访问具有局部性 的特点。系统重复查询会产生大量相同的数据传输，从而导致p 2 p 网络带宽资 源大量浪费。除了增强各对等点性能、提高网络带宽以外，采用缓存机制无疑 是解决这一问题的有效途径。近年来，作为分布式存储系统重要技术之一的缓 存技术也已被逐渐应用于基于p 2 p 网络的流媒体系统中，以解决信息传输中的 瓶颈问题，均衡网络负载，降低带宽开销，从而提升系统性能。 缓存策略的组成部分主要有缓存置换策略、缓存副本分布策略。此外缓存 副本一致性维护也是缓存策略的主要考虑内容之一。另外，由于点播系统中节 目分散，上线时间随机，即使两个节点在看同一个影片，由于播放进度相差很 大，也很难互相提供数据，形成p 2 p 网络，所以缓存时客户端缓存空间的大小和 缓存数据段的在线人数都会对缓存产生一定的影响，缓存策略是以上各个部分 的有机整合。在一个可行性高的缓存策略中，以上各个部分都需要加以认真思 考与设计。 3 1 1缓存置换策略分析 由于客户端节点存储空间是有限的，需要在有限的空间里尽可能存储价值 相对较大的，因此必须考虑适时地将一些副本文件替换掉以便为新的副本留出 空间。当缓存空间达到最大容量时，缓存置换算法便开始选择某些缓存副本， 将其置换出缓存空间之外。而当缓存空间出现剩余，可以存储新的缓存副本时， 这一置换过程便停止运行。 在p 2 p 流媒体点播系统中，影片采用分段技术，每个影片分成固定大小的 哈尔滨理工大学工学硕士学位论文 若干段( s e g m e n t ) 。根据影片的热度的不同分布，同一文件内部的热度也是很不 均衡的。一个段的价值高低，体现在其能为其它节点提供服务的概率大小，概 率大，则价值高，提高了p 2 p 的利用率，随之降低了服务器的压力。尽可能提 高节点的服务能力，从而减少服务器的压力是p 2 p 系统的一贯目标。因此，通 常会用价值高的段代替价值低的段，决定被替换副本的算法就是替换算法。目 前的替换算法有很多，典型的有以下几种： l r u ( l e a s tr e c e n t l yu s e d ，最近最少使用) 算法n 帕。它将缓存中最近最少被访 问的副本换出。主要考虑访问的近期性：当缓存的剩余可用空间不足时，缓冲 区尽可能的先保留使用者最常使用的数据，换句话说就是优先清除“较不常使 用的数据 ，并释放其空间。l r u 在是w e b 缓存系统中应用最为广泛。缺点是 没有考虑文档大小的影响，如果被换入的文档很大，就要换出多个小的副本， 这样会降低请求命中率。 l f u ( l e a s tf r