（计算机软件与理论专业论文）基于指数分段的流媒体代理缓存算法研究.pdf

基于指数分段的流媒体代理缓存算法研究 摘要 随着网络和多媒体技术的发展，流媒体应用越来越流行。然而现有的互联网 络缺乏对实时通信的良好支持，影响了流媒体的传输性能。同时，流媒体传输对 系统i 0 和网络带宽的高要求，使得服务器和网络带宽成为系统的瓶颈。流媒体 代理缓存技术通过缓存热门节目的部分或全部数据，为就近的客户端请求提供服 务，可以有效的解决上述问题。因此，针对流媒体应用的特点，研究高效的代理 缓存策略，以提高缓存命中率、减小客户端启动延迟、降低服务器负载和网络资 源消耗，是流媒体代理缓存技术的重要研究内容。 本文针对影响流媒体缓存性能和传输资源消耗的主要因素，以代理缓存策略 为主要研究内容。缓存替换算法直接影响缓存系统的效率，如何替换缓存的对象 以便用户直接从缓存中访问是缓存替换算法研究的主要内容。现有缓存替换算法 主要以媒体访问次数和访问频率来计算缓存效能值，并未考虑对象未来被访问的 概率，对效能值评价不够精确和效能值的计算也局限于整个媒体对象而没有精确 到段。针对这些问题，本文提出了基于l r v 的缓存替换算法。该算法以指数分段 为基础，细化了对于缓存空间的调度粒度，效能值的计算细化到段，充分考虑了 媒体部分有效性、段未来被访问的概率、段的访问频率、段已缓存长度对缓存效 能值的影响和段平均访问长度，因而提高了缓存性能。 模拟实验结果表明：本文的流媒体代理缓存算法在提高缓存字节命中率、降 低客户端启动延迟率等方面具有较好的性能，有利于提高流媒体的传输效率和播 放质量。 关键词：流媒体；l r v , 代理缓存；缓存替换算法； i i a bs t r a c t a st h ed e v e l o p m e n to ft h ei n t e r n e ta n dm u l t i m e d i a t e c h n o l o g y ，t h ea p p l i c a t i o no f s t r e a m i n gm e d i ai sb e c o m i n gm o r ea n dm o r ep o p u l a r h o w e v e r ，t h ec u r r e n ti n t e r n e t l a c k ss u p p o r tf o rr e a l t i m ec o m m u n i c a t i o n ，w h i c hi n f l u e n c i n gt h ep e r f o r m a n c eo f m e d i at r a n s m i s s i o n f u r t h e r m o r e ，d u et ot h e h i g hd e m a n d so fs t r e a m i n gm e d i a t r a n s m i s s i o no ns y s t e mi oa n d n e t w o r k b a n d w i d t h ，t h es e r v e ra n dn e t w o r kb a n d w i d t h t u r ni n t ot h eb o t t l e n e c ko ft h ew h o l e s y s t e m w h i l es u c hp r o b l e m sc a nb ee f f e c t i v e l y s o l v e db yt h ep r o x yc a c h i n gt e c h n o l o g y ，w h i c hc a c h e sp a r to ra l lo ft h ed a t ao fh o t p r o g r a m ss oa st oo f f e rs e r v i c e st ot h eu s e r sn e a r b y t h e r e f o r e ，b a s e do nt h em a i n f e a t u r e so ft h ea p p l i c a t i o no fs t r e a m i n gm e d i a ，s t u d i e so ne f f i c i e n tp r o x yc a c h i n g s t r a t e g yt oi n c r e a s ec a c h i n gh i tr a t e ，d e c r e a s et h ec l i e n ts t a r t u pl a t e n c ya n dr e d u c e s e r v e ro v e r l o a d sa n dn e t w o r kr e s o u r c ec o n s u m p t i o na r eo fg r e a ts i g n i f i c a n c et ot h e r e s e a r c ho fp r o x yc a c h i n gt e c h n o l o g yo f s t r e a m i n gm e d i a b a s e do nt h em a i nf a c t o r si n f l u e n c i n gt h es t r e a m i n gm e d i ac a c h i n g p e r f o r m a n c e a n dt r a n s m i s s i o nr e s o u r c e c o n s u m p t i o n ，t h i sp a p e rd i s c u s s e st h ep r o x ys t r a t e g y c a c h er e p l a c e m e n ta l g o r i t h m sd i r e c t l ya f f e c tt h ee f f i c i e n c yo f t h ep r o x yc a c h es y s t e m ， a n dt h em a i nr e s e a r c ho nc a c h er e p l a c e m e n ta l g o r i t h m si sh o w t or e p l a c ec a c h eo b je c t s ot h a tu s e r sc a na c c e s sm e d i ao b je c t d i r e c t l yf r o mt h ec a c h e e x i s t i n gc a c h e r e p l a c e m e n ta l g o r i t h m sh a v et h ep r o b l e mo fi n a c c u r a t ee v a l u a t i o no ft h ec a c h i n g u t i l i t yb e c a u s et h e i rs t a n d a r d sa r ea c c e s st i m e sa n df r e q u e n c yo ft h em e d i a ，a d d i t i o n l y t h e yd o n 。tc o n s i d e rt h ep r o b a b i l i t yo fa c c e s so b je c t si nt h ef u t u r e ，a n dt h ee v a l u a t i o n o fc a c h eu t i l i t yi sn o ta c c u r a t e ，a n dt h ec a l c u l a t i o no fc a c h eu t i l i t yi sc o n s t r a i n e dt o t h ew h o l em e d i ao b je c tb u tn o ta c c u r a t e l yt ot h es e g m e n t t os o l v et h e s ep r o l e m s t h e p a p e rp r e s e n t st h ec a c h er e p l a c e m e n ta l g o r i t h mb a s e do nl r v t h i sa l g o r i t h mb u i l d s t h eb a s eo ne x p o n e n t i a ls e g m e n t a t i o n ，r e f i n e st h es c h e d u l i n gg r a n u l a r i t yo fc a c h e s p a c e ，a n dt h ec a l c u l a t i o no fc a c h eu t i l i t yi sb a s e do ns e g m e n t s ，t h em e d i ap a r t i a l v a l i d i t y ，t h ep r o b a b i l i t yo fa c c e s st os e g m e n ti nt h ef u t u r e ，s e g m e n ta c c e s sf r e q u e n c y ， s e g m e n ta v e r a g ea c c e s sl e n g t ha n dt h ei n f l u e n c eo fc a c h e ds e g m e n ts i z et oc a c h e u t i l i t ya r ea l lc o n s i d e r e di nt h i sa l g o r i t h m ，w h i c he n h a n c e st h ec a c h ep e r f o r m a n c e t h er e s u l t so fs i m u l a t i o ne x p e r i m e n t ss h o wt h a tt h es t r e a m i n gm e d i a p r o x yc a c h e a l g o r i t h mp r e s e n t e di nt h i sp a p e rh a sb e t t e rp e r f o r m a n c eo ni n c r e a s i n gc a c h e h i tr a t e a n dr e d u c i n gc l i e n ts t a r t u pl a t e n c yr a t e ，t h e r e f o r e ，t h es t r e a m i n gm e d i a p r o x yc a c h e i i i 基于指数分段的流媒体代理缓存算法研究 a l g o r i t h mp r e s e n t e di nt h i sp a p e rh e l p st oi m p r o v et h et r a n s m i s s i o ne f f i c i e n c ya n d m e d i aq u a l i t yp e r c e i v e db yt h ee n du s e r k e yw o r d s ：s t r e a m i n gm e d i a ；l e a s t r e l a t i v e v a l u e ；p r o x y c a c h e ；c a c h e r e p l a c e m e n ta l g o r i t h m i v 硕士学位论文 插图索引 图1 1m i d d l e m a n 体系结构3 图1 2c a c h i n g 代理结构一4 图2 1 流媒体系统基本组成部分。1 l 图2 2 流媒体系统结构。l l 图2 3v o d 系统结构2 0 图2 4 代理服务器流媒体缓存系统模型2 l 图3 1 指数分段方式。2 7 图3 2 算法流程图一3l 图4 1o m n e t + + 中的简单模块和复合模块。3 3 图4 2z i p f 分布曲线。3 6 图4 3 算法承载平台38 图4 4 启动延迟率的比较。3 9 图4 5 命中率的比较。4 0 图4 6 平均缓存对象数的比较4 0 v i i 基于指数分段的流媒体代理缓存算法研究 置曩暑曩皇_ 目鼍詈暑穹詈皇皇詈皇鼍詈暑鼍詈詈皇暑皇鲁皇詈皇墨暑葛昌喜寡暑詈皇昌皇i l l 。i 一 插表索引 表4 1 系统参数及其缺省值3 8 v i i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名：际铥。跸 日期：西多年月石日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 l 、保密e l ，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名：酥钦群 翩戳。嗡 日期：支形$ 年石月台日 e t 期：a 棚年月户日 硕士学位论文 1 1 引言 第1 章绪论 二十一世纪己经进入了数字化的信息时代，随着i n t e r n e t 技术的发展和普遍 应用，网络电视、远程教育、视频会议、宽带电视广播、移动和无线多媒体服务 蓬勃发展起来，视频、声音、图像、动画等多媒体信息已成为人们生活的一部分； 流媒体的需要速度正以指数级增长着，它的实时性、高速性、宽带性使i n t e r n e t 的 网络设施常常不能满足流媒体的需求；网络资源和流媒体的广泛应用之间的矛盾 日益严重，节约网络资源保证流媒体应用成为挑战性的研究课题。 流媒体与传统静态媒体相比有三个显著的特点： ( 1 ) 流媒体内容数据量较大； ( 2 ) 延时敏感度高； ( 3 ) 交互性很强， 这就使现有网络面临巨大的考验。 目前应对该问题的常见方法就是部署边缘代理服务器，通过代理服务器处理 本地客户的请求，缓存并转发来自源服务器的数据。虽然代理服务器在处理静态 的基于文本的媒体内容方面取得了成功，但是在应对流媒体内容的时候却往往碰 到困难。因为传输流媒体数据需要占用较多的网络带宽资源，而且持续时间较长， 从而导致源服务器及网络只能支持数量有限的并发流，所以仅仅是部署边缘代理 服务器还远远不能支持网络中流媒体内容的平滑传输。目前的一个主要解决方案 就是求之于大规模的内容分发网络( c d n ) ，c d n 凭借其高带宽网络和大容量的 存储能力可以平滑传输流媒体内容，但是c d n 成本过高。目前的研究主要集中 于改善代理服务器的缓存算法来保证流媒体服务的质量，因此缓存管理算法和策 略成为流媒体传输领域的热点 1 2 研究背景及意义 i n t e r n e t 的飞速发展使其成为了社会基础信息的强大载体。随着网络信息资源 的逐渐丰富，网络上的文本、网页和图片等静态信息己经不能充分满足人们的需 要。取而代之的是由音频、视频以及数据资源综合形成的新的多媒体信息。这些 多媒体包含了丰富内容，但文件占用存储空间非常大，下载这些媒体文件需要数 分钟甚至数小时。为了解决多媒体资源传输问题，流媒体技术应运而生。流媒体 是指i n t e r n e t 中使用流式传输技术传输的连续时基媒体，它并不需要下载整个媒 基于指数分段的流媒体代理缓存算法研究 体文件，只要获得其部分内容即可开始播放【l 】。浏览网络多媒体文件的途径存在 两种：流媒体访问和h t t p 访问。在h t t p 访问方式中，所有内容全部下载完之后用 户才能观看。在流媒体访问方式中，用户可以边接收媒体数据边观看媒体内容。 相比h t t p 访问方式，使用流媒体访问方式的用户不需要经历长时间的下载等待， 也不需要提供存储网络多媒体文件的空间流媒体技术的发展和逐步成熟，使得在 i n t e r n e t 上开展了各种流媒体应用，如v o d ( v i d e oo nd e m a n d ) 、i p t v ( i n t e r n e t p r o t o c o lt e l e v i s i o n ) 、远程教育和视频会议等，而且这些应用已经越来越流行。 流媒体传输具有实时性、高速性、高宽带性的特点。然而，由于现有的网络 主要是为传输非实时数据而建立的，延迟、抖动和包丢失等问题普遍存在，网络 传输质量常常不能满足流媒体应用的需求，影响了流媒体传输的性能，造成用户 可感知质量的降低。而且目前网络带宽的增长速度跟不上流媒体应用的增长速度， 网络资源的紧张和流媒体的广泛应用之间的矛盾日益严重，如何在i n t e r n e t 中有 效地传输流媒体成为了近年来网络应用的研究热点。为了提供较高的流媒体服务 质量，必须解决以下三个问题心1 ： ( 1 ) 大量用户访问会造成流媒体服务器过载； ( 2 ) 网络拥塞造成的播放质量下降； ( 3 ) 网络传输距离和经过不同网络路径造成的用户启动延迟。在以往的解决 办法中，互联网服务提供商多利用镜像服务器提高系统的服务能力。但镜像服务 器并不考虑用户的访问行为( 如访问频率和媒体的流行性) ，多次复制非热门数 据浪费了服务器系统的存储资源。 流媒体代理缓存技术能有效解决上述问题。它通过在骨干网络的边缘靠近用 户的代理服务器上部署代理缓存系统，来缓存热门节目的部分或全部数据，为后 续的用户请求提供服务，其重要作用表现在阻3 ： ( 1 ) 代理缓存承担了一部分访问负载，有效降低了对流媒体服务器的访问负 载，减少了服务器的带宽资源消耗，使服务器可以为更多用户提供服务； ( 2 ) 代理缓存位于i n t e r n e t 边缘，一般设置在离终端用户很近的位置，利用缓 存数据服务用户，可节约从服务器到代理缓存之间的主干网络资源： ( 3 ) 利用代理缓存内容直接服务用户，可降低用户的启动延迟； ( 4 ) 代理缓存可以有效地提高流媒体服务器的鲁棒性。 因此，流媒体代理缓存是解决目前网络带宽资源不足与流媒体应用对网络带 宽高需求之间的矛盾，降低用户的播放启动延迟，提高播放质量的重要技术。研 究流媒体代理缓存技术，对于推动流媒体应用具有重要意义。 1 3 国内外研究现状 基于代理服务器的缓存技术主要分为以下七个研究方向： 2 硕士学位论文 ( 1 ) 流媒体缓存系统结构：研究代理服务器如何按层次、部署和混合组织等 问题。 ( 2 ) 缓存策略：研究如何缓存、在哪里缓存，缓存什么等问题。 ( 3 ) 替换算法：替换算法与缓存策略有很大关系，由于w e b 缓存技术是在计 算机三层结构、分布式系统缓存的基础上发展起来的，替换算法的研究是根据 w e b 缓存对象的内在属性异同研究出新的算法。 ( 4 ) 流调度技术：在代理服务器根据客户的请求对媒体流进行统一调度，达 到节约网络带宽资源。 ( 5 ) 预取技术：研究代理服务器什么时候从w e b 服务器或其它的代理服务服 务器预取什么，以便降低将来的访问延迟。 ( 6 ) 缓存一致性：研究代理服务器缓存的数据如何与源服务器数据保持一致 的问题。 ( 7 ) 动态数据缓存：研究代理服务器如何缓存经常变化的动态数据( 如天气预 报、财经信息、从数据库检索的信息等) 问题。 由于流媒体的固有属性，主要研究前五个方向。 1 3 1 流媒体缓存系统结构的研究 流媒体缓存系统结构方面的研究主要集中在做为缓存的代理服务器应该如何 组织，包括缓存系统结构是采用什么样的层次、分布式或混合结构等问题。a c h a r y a ， s m i t h 等提出了一种合作缓存c a h i n g 视频服务器m i d d l e m a n 结构h 1 。 该结构将一组代理服务器连接成一个l a n ，通过合作缓存视频文件， m i d d l e m a n 可以聚合成一个很大的缓存空间，而参与这种结构的每一个p r o x y 只 有很少的负荷。文中用一个5 0 0 客户的校园网形成一个m i d d l e m a n 集群作为例子： 每台机在分配1 0 0 m 的存储空间做为缓存存储器，整个系统就可以获得5 0 g 的 c a c h e 容量。m i d d l e m a n 结构如图1 2 所示共享。协调器( c o o r d i n a t o r ) 保持记录了 每个代理服务器缓存的视频文件。当用户请求某个v i d e o 对象时，协调器就根据 保持的记录将请求重定向到某个代理服务器或者源服务器。 m a c h i n e2 图1 1m i d d l e m a n 体系结构4 3 基于指数分段的流媒体代理缓存算法研究 t r a n ，h u a 等提出了将一种称为c a c h i n g 代理的服务器分布在网络中，构成一 个虚拟骨干( v i r t u a lb a c k b o n e ) 网络的方案哺1 。这个骨干网可以是i s p 的网络，也 可以是视频分布网络。不同于传统的代理服务器的是：代理服务器缓存扮演了一 个虚拟路由器巧妙地缓存经过它的数据。其结构如图1 3 所示。 在该系统结构中，c a c h i n g 代理分为三种，分别是内部代理( i a g e n t s ) 、外部 代理( x - a g e n t s ) 和根代理( r a g e n t ) ，每个内部代理服务于一个子网中的用户；外 部代理位于核心骨干网中，而根代理位于服务器端。客户端将对媒体对象的请求 提交给它的内部代理，如果缓存命中，就由该内部代理提供服务，否则，请求就 会被转发给外部代理，如果未命中则把请求转发给根代理，仍旧没命中的话则最 终把请求转发给源服务器。 图1 2c a c h i n g 代理结构哺1 1 3 2 缓存策略的研究 由于流媒体的固有属性，同缓存传统的w e b 对象相比，对流媒体对象进行缓 存遇到了新的挑战。该方向主要研究如何对流媒体对象进行缓存，包括对流媒体 对象进行分段、分层和部分缓存策略问题，还包括如何将缓存数据进行质量调整 和转码( t r a n s c o d i n g ) 以满足异质( h e t e r o g e n e o u s ) 用户等问题。 r e j a i e 等为分层编码( l a y e r e d - e n c o d e d ) 的视频，结合拥塞控制( c o n g e s t i o n c o n t r 0 1 ) 哺1 机制，提出了一种基于代理服务器的缓存策略。分层编码将压缩的视频 流分割成一个基础层，包含最基本的质量信息；多个增强层，用来改善流媒体播 放质量，其缓存策略的基本思想是根据流媒体的流行性来增加或减少缓存在代理 服务器上的流媒体的层数，媒体越流行，缓存的层数也越多，媒体的播放质量也 越好，当用户点播一个流媒体对象时，没有被缓存的层将从流服务器上获得，文 献 7 】研究了哪个媒体对象和媒体对象的哪一层应该被缓存的优化算法。 s e n ，r e x f o r d 提出了一种前缀( p r e f i x ) 缓存策略哺1 ，该策略在代理服务器中 c a c h i n g 媒体剪辑的前面一定集合的帧( 前缀) ，并在媒体对象从p r o x y 传输到用户 4 硕士学位论文 时使用w o r k a h e a d 平滑技术旧j 们。即在p r o x y 上存储流媒体的初始帧，一旦接收 到用户对该媒体的请求，p r o x y 就用缓存的前缀数据提供给用户初始化，同时向 流服务器请求其余的帧。前缀部分应该足够大，以便隐藏掉来回旅程( r o u n d t r i p ) 的延迟和吸收用户播放器与代理服务器间的通信抖动。比较大的前缀可以减少请 求媒体其余部分的时间，但减少了代理服务器上缓存流媒体前缀的数量该策略的 不足之处就是不适用于交互式的流媒体，当用户进行了一个交互操作( 如快进) ， 将会经历一个比较大的等待延迟。 t e w a r i ，w i n 等提出为c b r ( c o n s t a n tb i tr a t e ) 编码的v i d e o 对象提出了一种 基于资源r b c ( r e s o u r c eb a s e dc a c h i n g ) 机制1 ，该策略根据缓存中的资源( 存储 空间和带宽) 确定哪个对象应该部分或完全缓存，并提出了考虑对象大小和c b r 带宽的缓存替换策略。 l i m ，p a r k 等提出了根据媒体的流行性，在代理服务器上缓存流媒体的一部分 或整个媒体的策略n 引，该策略在代理服务器上缓存某个媒体的长度与用户对它的 访问次数成正比，并提出了缓存效益和成本等概念。对于媒体对象的分段策略， w uk 等n 3 1 提出了指数分段缓存，指数分段缓存。一个媒体文件o 被分成多个大 小相等的块b ( b l o c k ) ，块b 是用来进行传送的最小单元。越靠近前面，段落所包 含的块就越少。段落o 含有块o ，段落l 含有块l ，段落2 含有块2 和段落i 包含的块的个数是2 卜1 ( f 1 ) 。它的动机是能够通过释放掉大的缓存段落来快速的 适应访问趋势的变化。文献【1 4 】根据媒体特性，提出了一种具有q o s 调整的混合 媒体( 文本、图像、音频和视频等) 代理服务器缓存方案，并将源服务器与代理服 务器之间，代理服务器与客户之间变化的带宽作为缓存策略的重要参数。 1 3 3 流调度技术的研究 为了节约网络带宽资源，研究者已提出了一些高效的流调度技术，目前相关 的算法有成批算法、补丁算法和成批补丁算法等。在成批算法n5 1 6 1 中，代理在收 到用户的点播请求后，并不立刻进行处理，而是适当延迟对用户请求的响应，将 在这个延迟时间段中到达代理的客户点播请求集中起来，统一协调处理。把这个 延迟时间段称为批量化窗口。成批处理的目的在于充分利用多播的优势，即一个 多播服务的客户越多，节约的网络带宽就越多( 相对于单播方式而言) 。 补丁算法n7 1 8 1 是在成批算法的基础上，第一个客户请求到来后代理立即把从 服务器申请来的数据通过组播发送到客户端，后来的客户则直接加入该组播组， 同时记录下所缺少的部分并向服务器发送请求补丁数据，得到数据后再启动补丁 通道以单播方式发送补丁数据给此客户端。在补丁调度算法中，用于传输整个流 媒体对象的通道称为常规通道( r e g u l a rc h a n n e l ) ，用于传输补丁部分( 由于客户请 求晚到而错过的部分) 的通道称为补丁通道( p a t c hc h a n n e l ) ，相应地，在常规通道 基于指数分段的流媒体代理缓存算法研究 中传输的数据流叫做常规组播流，在补丁通道中传输的数据流叫补丁流。在成批 处理和补丁算法的基础上，最优批处理补丁( o p t i m i z e db a t c hp a t c h i n g ) n 钔方案结合 了二者的优点，导出了最优补丁窗口与媒体对象长度及访问强度之间的关系，认 为当客户请求到达时刻超出该窗口范围后，服务器应该启动一个新的常规组播流 为其提供服务。该方法能够更有效地节省网络带宽，避免开辟较多的补丁流通道， 充分利用了组播的优势，能够降低服务器网络带宽的消耗。但是在实践中，它依 赖于一个完全具有网络层组播能力的网络，在广域网中组播的部署还存在一定的 困难，而在局域网内组播的部署则比较容易实现。 1 3 4 替换算法的研究 当作为缓存的代理服务器的存储空间不够缓存一个流媒体的部分或全部时， 就要替换( r e p l a c e m e n t ) 缓存中已过时的媒体，以便释放出空间缓存新的媒体对象。 w e b 缓存替换算法是从传统的操作系统虚拟存储管理和数据库缓冲管理缓存算法 的基础上扩展的，目前已对w e b 缓存替换算法进行了比较深入的研究。而流媒体 缓存替换算法根据流媒体的特性，在w e b 缓存替换算法的基础上扩展的。由于 流媒体的固有特性和流媒体系统的专用性，对通用流媒体缓存替换算法的研究还 不多见。文献【2 0 】分析了视频流分段的动态缓存。文献 2 1 提出了改善接收质量 q o r ( q u a l i t yo f r e c e p t i o n ) 的缓存策略，通过引进一个灵活的成本函数允许接收端 来影响代理服务器的缓存替换策略。 1 3 5 预取技术的研究 预取是通过预先获取对象保存在缓存中，以便期待它们能在未来被请求的技 术。关键点就是确定预取的收益率强胡。在传统的w e b 缓存应用比较广泛，在流 媒体系统无线通信系统中和媒体播放器的缓冲区中有所应用。由于同传统w e b 的r e q u e s t r e s p o n s e 特性相比，流媒体有较长的持续时间，流媒体对象要比传统 的w e b 对象大几个数量级，预取技术在流媒体c a c h i n g 系统中应用还比较少， 其意义也和传统w e b 缓存中的预取有所不同。在流媒体缓存中，预取的概念是 代理服务器在将部分数据传送给客户端的同时，向服务器端请求其余的数据。文 献 2 3 在缓存命中的情况下为高带宽连接用户预取请求媒体流的增强层，但媒体 流只限于层次编码。文献【8 】在将缓存的前缀数据提供给用户初始化的同时，向流 服务器请求预取其余的帧。 1 3 6 流媒体代理缓存国内研究现状 国内目前对流媒体缓存技术的研究比较多，从发表文章的时间上看，可以说 国内对流媒体缓存技术的研究最近两年比较热门。文献【2 4 】针对流行度随时间变 化的特性，利用回归分析技术给出了一种流媒体文件的流行度预测算法，并在增 6 硕士学位论文 加少量存储空间及计算时间消耗的情况下，将该预测算法应用于流媒体代理缓存 服务器的缓存替换算法之中。文献 2 5 】结合代理缓存和补丁算法的优点，设计与 实现了一种基于补丁算法的流媒体代理缓存，但是算法前提代理服务器是为局域 网用户服务的，因而有一定的局限性。文献【2 6 提出了一种基于最大缓冲时间的 p 2 p 流媒体分发缓存算法，算法考虑了无线网络传输时延、流媒体中断的位置及 用户提供的计算资源。文献【2 7 】提出一种流媒体缓存替换算法一基于平均传输成 本的最小缓存效用算法，并提出一组评价缓存替换算法有效性的性能指标：平均 传输成本、中心服务器消耗的带宽和算法的计算开销。文献 2 8 1 贝0 总结了代理服 务器缓存国外所展开的研究，虽然其内容主要针对的是c d n ( c o n t e n td i s t r i b u t i o n n e t w o r k ) ，但是c d n 中边缘服务器与流媒体代理服务器有很多共同之处，因而具 有很高的参考价值。 1 4 本论文的主要研究工作和组织结构 1 4 1 主要研究工作 随着流媒体应用程序在i n t e r n e t 上的广泛应用，预计最近一、二年，连续媒 体将超过源服务器上可用数据的7 0 。数字视频的高带宽和实时性要求， 必将 使互连网的负载急剧增加。单播目前仍是i n t e r n e t 上的一种主要的流媒体播放方 式，而基于包交换的i n t e r n e t 不是为实时、不问断的流媒体传输而设计的，访问 流媒体的用户必须忍受高启动延迟( s t a r t u pl a t e n c y ) 和不可预知的播放质量。因 此，要在i n t e r n e t 实现规模化的流媒体应用系统，必须走出点到点、服务器到客 户这种流媒体传输模式，流媒体缓存( c a c h i n g ) 就是这种解决方案的一个重要研 究方向。 w e b 缓存在提高访问i n t e r n e t 的性能方面获得了相当大的成功，由于流媒体 对象具有与w e b 对象( 文本、图像) 不同的内在属性，目前己有的代理服务器缓 存系统还不能有效地应用于缓存像音频、视频这样的流媒体对象。因此，本研究 提出用代理服务器缓存来解决流媒体在大用户群环境下所面i 临的问题，从用户访 问特性、媒体流行性、缓存策略等方面对流媒体代理服务器缓存算法进行了深入 的研究。 本文针对影响流媒体缓存性能和传输资源消耗的主要因素，以代理缓存策略 为主要研究内容，研究缓存替换算法和调度算法，论文主要工作如下： ( 1 ) 阐述了和流媒体流媒体技术的概念和应用，详细介绍了流媒体代理缓存 技术国内外现状，并对该领域的多个研究方向进行了简单的介绍和总结。 ( 2 ) 针对现有缓存替换算法主要以媒体访问次数和访问频率来计算缓存效用 值，对效能值计算不够精确和其计算也局限限于整个媒体对象而没有精确到段的 7 基于指数分段的流媒体代理缓存算法研究 问题，提出了基于l r v 的缓存替换算法。该算法充分考虑了媒体部分有效性、段 未来被访问的概率、访问频率、己缓存大小对缓存效用值的影响和平均访问长度。 ( 3 ) 对媒体对象的前缀和后缀分开管理，段的缓存和替换都在相应的高效 l r v 栈中进行管理，而不是使用简单的f i f o 栈。针对前缀段和后缀段的不同特性， 也采用不同的效能函数。 ( 4 ) 在o m n e t + + 模拟平台上，设计了基于事件驱动的模拟实验，针对流媒体 缓存系统三个重要的性能评价指标分别与指数分段，前缀算法进行了比较，并对 实验结果做了详细的分析。 1 4 2 论文的组织结构 本论文分为5 章，其中： 第l 章：叙述了本文的研究背景及意义，介绍了流媒体代理缓存的主要应用 领域和研究现状，并对本论文的主要研究工作和论文组织结构进行了说明。 第2 章：介绍了流媒体代理服务器系统，重点阐述了流媒体系统的结构，分 析了流媒体应用与带宽的关系、流媒体代理缓存与w e b 代理缓存的区别等。最后 提出基于l a n 的流媒体代理服务器模型。 第3 章：首先分析了缓存策略的主要目标和研究内容，指出缓存替换算法和 调度算法在提高缓存命中率、降低客户端启动延迟、减小媒体传输对服务器和网 络带宽资源的消耗等方面具有重要的影响。然后以前缀结合指数增长分段方式为 基础，提出了基于l r v 的缓存替换算法，并对算法进行了分析和阐述。 第4 章：介绍了实验所使用的仿真平台。然后列出了流媒体缓存系统三个重 要的性能评价指标和实验中我们所采用的系统参数。最后在命中率、客户端启动 延迟率和平均对象个数等方面，对实验结果进行了比较和分析。 第5 章：对全文的研究做出总结并对未来的工作进行了展望。 8 硕士学位论文 第2 章流媒体代理服务器系统概述 2 1 流媒体与流媒体技术 2 1 1 流媒体 流媒体是指在网络中使用流式传输技术的连续时基媒体，如音频、视频、动 画或其它多媒体文件。在i n t e r n e t 产生的相当长的一段时间里，网上的连续媒 体应用一直局限于媒体文件的下载模式，这些文件通常都是很大的，这不仅需 要用户耐心地等待，而且要占用很大的磁盘空间。而流媒体是直接从网上播放 的，真正做到了边传送边播放。归纳起来，流媒体具有以下特征： ( 1 ) 能用来传播诸如足球比赛、音乐会之类的直播内容。 ( 2 ) 能提供对比较长的媒体的随机访问，流媒体服务器就像带遥控的v c d 机一样，可以提供如快进、快退和暂停等v c r 功能，这是“流”模式和“逐步前 进”模式的非常大的区别。 ( 3 ) 不占用用户的磁盘空间，用户无需获得一个完整流媒体文件的拷贝， 这也是“流”模式和“下载”模式的最大区别。 ( 4 ) 只使用它实际需要的网络带宽，如果流媒体内容超过了连接速度，流 媒体可以通过调整它们的质量来适应连接的速度，这意味着数据包可能丢失， 播放的效果会受影响。 ( 5 ) 需要附加的流媒体协议支持，如r t s p 等。 2 1 2 流媒体技术 所谓流媒体技术是实时数据传输技术和流媒体编码技术的总称。流媒体技 术覆盖网络技术和多媒体技术的两个方面，是计算、压缩、存储设备、网络带 宽几方面的技术进步产物。通过流媒体技术访问网络多媒体文件的行为被称之 为流媒体访问。支持流媒体访问的网络多媒体文件称之为流媒体对象。流媒体 技术可分为视频压缩、应用层q o s 控制、分发服务、流媒体服务器、媒体同步 技术以和流媒体协议6 个部分： ( 1 ) 视频压缩：为了提高效率，在传输之前原始视频信息需要进行压缩处 理。压缩格式存在可扩展( s c a l a b l ev i d e o ) 和不可扩展( n o n s c a l a b l ev i d e o ) 两大 类。其中，可扩展压缩格式中一个多媒体文件能具有多个码率的解码方式，主 要应对观看用户的网络状况差异，不可扩展的压缩格式中一个多媒体文件只能 按照一种码率来解码，具有更高的压缩比率。 9 基于指数分段的流媒体代理缓存算法研究 ( 2 ) 应用层q o s 控制：在实际应用中，不同用户的播放能力或网络条件存 在着差异。应用层q o s 控制是应对这种差异的传输技术。应用层q o s 主要包 括拥塞控制和错误控制两个方面，拥塞控制是用来避免数据包丢失和延迟对播 放质量的影响。错误控制是在数据包丢失时尽力恢复数据以保证播放质量的技 术。 ( 3 ) 连续媒体的分发服务：流媒体访问是用户访问网络多媒体文件的行为， 网络的传输能力是影响流媒体访问质量的关键因素。访问延迟和丢包率是网络 传输的固有属性，也是降低流媒体访问质量的主要原因。连续媒体的分发服务 是用来降低流媒体传输访问延迟和丢包率的重要技术。 ( 4 ) 流媒体服务器：流媒体服务器是提供流媒体服务的主体。保证实时数 据的传输响应访问操作是流媒体服务器服务的两个工作。通常由传输器、工作 系统和存储系统三部分组成。 ( 5 ) 媒体同步技术：媒体同步是正确展现多媒体内容的关键技术。在媒体 同步的机制下，客户端的应用可以按照原始采集的情况将多个流媒体完整的流 呈现出来。 ( 6 ) 流媒体协议：流媒体协议是实时数据的传输规范，包含网络寻址、传 输以及会话控制等描述。根据功能可被分为网络协议( i p ) 、传输协议( u d p ，t c p ) 、 会话控制协议( r t s p ) = 类。 2 2 流媒体系统结构 2 2 1 流媒体系统基本组成部分 流媒体系统的基本组成部分如图2 1 所示，一个基本的流媒体系统有三个 基本组成部分即播放器，流媒体服务器和编码器。 流媒体服务器用于存放流媒体内容，根据用户的请求将流媒体内容传给用 户。在处理客户请求方面，流媒体服务器和w e b 服务器相似。与w e b 服务器 不同的是，在媒体的播放过程中，流媒体服务器需要维持与用户的双向连接， 还需要提供如数字版权管理权限d r m ( d i g i t a lr i g h t sm a n a g e m e n t ) 、广告插入 和其它服务器流的映射或分流等。 编码器将原始音频或视频文件转换为能够进行流传输的格式。 1 0 硕士学位论文 流媒体播放器 图2 1 流媒体系统基本组成部分 2 2 2 流媒体系统的体系结构 图2 2 说明了一种通用视频流结构，在图中，用视频和音频压缩( c o m p r e s s i o n ) 算法将捕捉到的原始视频数据和音频数据预先压缩存储在流服务器的存储设备 中，一旦客户请求到来，流服务器根据网络状态和q o s 要求，先从存储设备中 检索压缩的视频音频数据，再选择应用层( a p p l i c a t i o n l a y e r ) q o s 控制模块调节视 频和音频的位流，调节以后，传输层协议将压缩的位流打包，并将视频和音频包 送到i n t e r n e t 上。由于网络拥塞，包在i n t e r n e t 内可能丢失或经历过多的延迟。为 了改善视频和音频的传输质量，连续媒体分布服务( c o n t i n u o u sm e d i ad i s t r i b u t i o n s e r v i c e s ) 部署在i n t e r n e t 。对于那些成功传送到接收端的包，它首先穿过传输层， 然后被应用层处理，最后交由视频或者音频解码器解码。为了获得视频和音频间 的同步，需要媒体同步机制( m e d i as y n c h r o n i z a t i o nm e c h a n i m s ) 乜9 3 们。 r a wa u d i o 八 c l i e n t m e d i as y n c h r o n i z a t i o nm e c h a n i m s 。上。 i t r a n s p o r t 咖l 。u d d c l i d c r c o d e r d e c o s 衙鸱蓐 i n t c m e t ( i d e v i c e p r o t o c o i s队 c o n t i n u o u s ? 。 c o m p r e s s i o n 、t ic o m p r e s s e di + m e d i a t v i d