（计算机软件与理论专业论文）基于p2p协作的代理缓存流媒体调度算法研究.pdf

基于p 2 p 协作的代理缓存流媒体调度算法研究 摘要 随着计算机硬件水平与宽带网络的迅速发展，多媒体服务越来越受到人们的 欢迎。由于流媒体技术能够有效的实现直播与交互式点播，成为近来研究的热点。 网络结构与调度算法关系到流媒体系统的服务质量，成为流媒体技术的研究重 点。 在流媒体网络模式中，传统c s 模式结构相对简单容易管理，但整个系统的 服务能力受中央媒体服务与主干网络影响较大，不能很好的适应数据传输量大持 续时间长的流媒体服务。于是人们提出p 2 p 网络模式，网络中对等节点之间互为 服务器与客户端，实现数据共享，但网络环境复杂对等节点难于管理。 将经常被访问的数据缓存到离客户端相对较近的代理服务器上，通过代理服 务直接为客户端提供服务，并且为增大缓存空间，将多个代理服务器组成簇，是 一个有效提高服务质量减少用户时延的方法。由于缓存空间有限，代理服务器必 须有选择性的缓存媒体文件。如何准确的选择需要缓存的数据并把这些数据分配 到不同代理服务器，使得系统能够服务更多用户，提供更好的服务质量，是缓存 算法面临的主要问题。 为解决上述网络模式问题，本文采用具有中心流媒体服务器，且代理服务器 能够进行p 2 p 协作的混合网络。能够有效避免c s 模式下过分依赖中心流媒体服 务器的情况，及纯p 2 p 网络环境下节点之间难于管理，易造成网络抖动的情况。 在缓存数据的选择上，本文引入以数据量为基础的媒体文件流行度 p o p u l a r i t y 和缓存效率c e ，按照流行度高的数据占用较大存储空间的原则，利 用媒体文件的存储效率为每个前缀分配相应的存储空间。在数据传输时，连接中 心媒体服务器的主干网络需要传输一些必要的数据，增强客户端交互性或是避免 网络抖动，保证客户端正常播放。在不影响客户端播放质量的情况下，应该尽量 利用边缘网络传输数据减少主干网络压力。本文将为主干网络与边缘网络赋予不 同权重，引入c ( f ，p ：) 表示媒体文件，在代理服务器，缓存p ：的数据量时所需的 传输成本，并按传输成本将前缀降序排列，代理服务器升序排列。将前缀依次分 配到代理服务器上，使得整个网络中传输成本最小。 本文提出的基于p 2 p 协作的代理缓存流媒体调度算法p c s p c ( p r o x y - c a c h i n g s c h e d u l e rb a s e do np 2 pc o o p e r a t i o n ) ，选取合适的网络模式，综合考虑缓存 空间利用率与传输成本，使代理缓存尽量存储价值较高的前缀部分，提高了客户 端请求命中率，特别是在存储空间受限的情况下，该算法优点突出。在传输数据 时，本算法使得普通数据倾向于在代理服务器与客户端之间的边缘网络上传输， 保证主干网络传输必要的控制信息与紧急信息。特别是在用户请求频繁时，主干 网络压力上升缓慢，能够服务较多用户。在文章最后通过仿真结果，与其他类似 算法相比，证明其有效性。 关键词：流媒体；p 2 p 协作；代理缓存；存储效率；传输成本； r e s e a r c ho np r o x y e a c hin gs c h e d uie rb a s e do np 2 p c o o p e r a t io n a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rh a r d w a r ea n dw i d eb a n d ，m u l t i m e d i a s e r v i c eb e c o m em o r ea n dm o r ep o p u l a r a ss t r e a m i n g m e d i at e c h n o l o g yp r o v i d e c o n d i t i o n st or e a l t i m ev i d e oa n dv o d ( v i d e oo nd e m a n d ) ，m a n ye x p e r t sa r ef o c u s e d o ni t n e t w o r ks t r u c t u r ea n ds c h e d u l e ra l g o r i t h m sa r cr e s e a r c hp o i n t ，f o rt h e yc a l l a f f e c tt h ee f f i c i e n to fs t r e a m i n g - m e d i as y s t e m sq o s ( q u a l i t yo fs e r v i c e ) i nt h en e t w o r ks t r u c t u r eo fs t r e a m i n g m e d i a ，t h et r a d i t i o n a lc sm o d ei sr e l a t i v e l y s i m p l ea n dm a n a g e de a s i l y ，h o w e v e r ，t h ec a p a c i t yo fs y s t e mi si m p a c t e ds e r i o u s l yb y c e n t e rm e d i as e r v e ra n db a c k b o n en e t w o r ka n dd on o ta d a p tt os t r e a m i n g m e d i a s e r v i c e 、析t hh e a v yd a t aa n dl o n gt i m e t oc h a n g et h i sc o n d i t i o n ，p 2 pn e t w o r km o d e w a sr a i s e d ，p e e r sa r eb o t hs e r v e ra n dc l i e n tf o re a c ho t h e r t h a tm a k e sd a t as h a r e d a m o n gt h e m ，h o w e v e rp e e r sm a n a g e dd i f f i c u l t l y 。 t h er e g u l a r l ya c c e s s e dd a t ai sc a c h e di nt h ep r o x ys e r v e rw h i c hi sr e l a t i v ec l o s et o c l i e n t p r o x ys e r v e rs e r v e sd i r e c t l yt oc l i e n t o r g a n i z i n gan u m b e ro fs e r v e r sa sa c l u s t e rt oi n c r e a s ec a c h es p a c e i sa ne f f i c i e n tw a yt or e d u c et h es e r v i c ed e l a ya n d i n c r e a s eq o s 。a st h el i m i to fc a c h es p a c e ，p r o x ys e r v e r sh a v et oc a c h et h em o s t v a l u a b l ed a t a i ti st h ei m p o r tp r o b l e mo fc a c h i n ga l g o r i t h mt h a tc h o o s i n gt h em o s t v a l u a b l ed a t ae x a c t l ya n da s s i g n i n gt od i f f e r e n tp r o x ys e r v e r sm a k et h es y s t e ms e r v e m o r ec l i e n t sa n dp r o v i d eb e t t e rq o s f o rr e s o l v i n ga b o v ep r o b l e m so fn e t w o r km o d e ，t h i sp a p e ru s e st h eh y b r i dn e t w o r k m o d e 、) l ，i t hc e n t e rm e d i as e r v e ra n dp r o x ys e r v e r sw h i c hc o n n e c te a c ho t h e rb yp 2 p c o o p e r a t i o n t h i sc a na v o i dt h ec o n d i t i o nt h a ts y s t e md e p e n d so nc e n t e rm e d i as e r v e r e x c e s s i v e l yi nc sm o d ea n dt h ec o n d i t i o nt h a tp e e r sa r em a n a g e dd i f f i c u l t l yi np u r e p 2 pn e t w o r km o d e w h e nc h o o s i n go fd a t a , t h i sp a p e ri n t r o d u c e st h em e d i af i l ep o p u l a r i t ya n dc a c h i n g e f f i c i e n c yb a s e do nd a t as t a t i s t i c s a c c o r d i n gt ot h ep r i n c i p l et h a tm o r ep o p u l a rd a t a a r ea s s i g n e dm o r ec a c h e ，a l l o c a t ec o r r e s p o n d i n gc a c h et oe v e r ym e d i af i l e sp r e f i xb y i t sp o p u l a r i t y w h e ns e n d i n gt h ed a t ao nn e t w o r k s ，t h eb a c k b o n eh a st os e n ds o m e n e c e s s a r yd a t at oi n c r e a s ea l t e r n a t i o nw i t hc l i e n t sa n da v o i dn e t w o r kj i t t e r a n d g u a r a n t e et h eq o s w i t h o u ti n f l u e n c eq o s ，t h es y s t e ms h o u l ds e n dd a t au s i n gt h e e d g en e t w o r kt or e d u c et h ep r e s s u r eo fb a c k b o n e 。t h i sp a p e rg i v e st h eb a c k b o n ea n d e d g en e t w o r k sd i f f e r e n tr i g h t s ，i n t r o d u c e sc ( i ，- ，p ：) d e n o t i n gt h et r a n s m i s s i o nc o s t w h e nm e d i a f i l eih a sp ：d a t ao nt h ep r o x ys e r v e rj p r e f i xs e q u e n c ea n dp r o x y s e q u e n c ea r es o r t e di na s c e n d i n ga n dd e s c e n d i n go r d e rr e s p e c t i v e l yb yt r a n s m i s s i o n c o s t a n dt h e na s s i g n i n gp r e f i xt op r o x ys e r v e r sm a k e st h et r a n s m i s s i o nc o s ta sl e a s t a sp o s s i b l e t h ep a p e rp r o p o s e sp r o x y c a c h i n gs c h e d u l e rb a s e do np 2 pc o o p e r a t i o n ( p c s p c ) ， w h i c hc h o o s e sa na p p r o p r i a t en e t w o r k sm o d ea n dc o n s i d e r sb o t hc a c h i n ge f f i c i e n c y a n dt r a n s m i s s i o nc o s t t h i sa l g o r i t h mi n c r e a s e sh i tr a t i o ，e s p e c i a l l yi nt h ec o n d i t i o n t h a tc a c h ei sl i m i t e du s i n gt h ew a yt h a tp r o x ys e r v e r sc a c h et h em o s tv a l u a b l ep r e f i x i tm a k e sd a t at ob es e n to ne d g en e t w o r k si n s t e a do fb a c k b o n ef o re n s u r i n gt h e t r a n s m i s s i o no fc o n t r o li n f o r m a t i o na n du r g e n c yi n f o r m a t i o no nb a c k b o n e e s p e c i a l l y w h e nl o t so fc l i e n tr e q u e s t ，t h ep r e s s u r eo fb a c k b o n ew i l li n c r e a s es l o w l y , t h i sl e t s y s t e ms e r v em o r ec l i e n t s i nt h el a s ts e c t i o no f t h ep a p e r , s i m u l a t i o nr e s u l t ss h o wt h e e f f e c t i v e n e s so ft h es t r a t e g y k e y w o r d s ：s t r e a m i n gm e d i a ：p 2 pc o o p e r a t i o n ：p r o x y c a c h i n g ；c a c h i n g e f f i c i e n c y ：t r a n s m is si o nc o s t 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过囊勺研究成果，也不包含未获得 ( 洼! 垫遗直基丝益要挂剔直盟笪：奎拦豆窒2 或其他教育机构的学位或证书使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 学位论文作者签名 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公 众提供信息服务。( 保密的学位论文在解密后适用本授权书) 学位论文储躲棚撕 签字日期7 年p 导师签字： 签字日期： 基于p 2 p 协作的代理缓存流媒体调度算法研究 1 绪论 1 1 1 选题背景 流媒体( s t r e a m i n gm e d i a ) 是指在i n t e r n e t 中采用流式传输技术( 指将大文 件分成有序列的小文件) 的多媒体。用户在点播流媒体文件，等待片刻，就能观 看媒体文件，而不需要下载整个文件，流式媒体文件允许边下载边播放。流媒体 技术的原理就是按照时间顺序将媒体文件分成不同的片段，然后将这些规模很小 的文件发送给客户端，在客户端将这些规模小的媒体文件按时间顺序重新组织起 来，并将音频包与视频包同步，形成在客户端连续播放的视频流。 随了流媒体技术的发展，视频直播与视频点播( v o d ) 逐渐被人们熟悉，而 且应用广泛，例如在新闻点播，远程教育，数字图书馆，电子商务采购等文化， 商业，娱乐，通信领域。在流媒体迅速发展的背后，不但为各个应用领域带来了 极大的方便，同时成为电信运营商的一大主流增值业务，带给他们巨大的利润空 间。但是，流媒体技术远远没有成熟，无论是理论上还是技术上都面临很多问题， 比如，寻找最稳定的网络连接，最多的媒体资源，最快的传输速率，最短的网络 延迟，最优值的服务效果等。所以流媒体技术还有着巨大的研究空间与研究价值。 1 1 2 流媒体技术中的网络模式 传统的流媒体系统是基于c s ( c l i e n t s e r v e r ) 模式的，主要由服务器和客 户机组成，其中服务器可以是一台也可以是多台组成，客户机的数量则由服务器 的服务能力决定。在该模式下，客户机之间基本上是独立的，如果有相同的请求， 服务器必须通过网络向不同的客户机发送相同的数据。在该模式下系统能够同时 服务的客户机数量就成为系统容量或是系统服务能力，该模式下的服务能力主要 由服务器的处理能力和服务器端的网络带宽决定，在有的系统中服务器的内存大 小，吞吐能力也是决定因素之一。在该模式下，服务器端的可用带宽有限，传输 的流媒体文件则需要消耗大量的带宽，且占用时间长。单纯的提高服务器的处理 能力增加服务器的存储空间，系统的服务能力也不能得到有效的提高。在带宽的 限制下，系统仅能同时服务几百左右的客户端，在小型的应用中尚可，但是不具 基于p 2 p 协作的代理缓存流媒体调度算法研究 备大型应用的经济规模。另外，由于因特网的特性，在传输数据量大持续时间长 的流媒体文件的过程中，肯定会出现例如，延迟，抖动，丢包，网络阻塞等问题， 使得服务质量( q o s ) 不能得到保证。该系统中最为关键的问题还是带宽消耗问 题，服务器向每一个客户发送请求的数据，而且是单独发送没有复用，这将迅速 的挤占带宽资源导致系统服务能力不高。 在新兴的p 2 p 网络模式中人们往往考虑巨大的因特网中分布着许多计算机空 闲资源，p 2 p 技术的原理就是采用分布式算法将这些空闲资源利用起来为因特网 上的用户提供各种服务。网络的每一个节点( p e e r ) 既可以作为客户接受其它节点 的服务，也可以作为服务器向其它节点提供服务 1 。在p 2 p 结构中节点之间基本 上都是平等的，削弱了服务器在网络中的中心的特殊地位，所以与传统的客户端 服务器模式相比，有一些独特的优势。 1 1 3 传输成本概述 传输成本是衡量不同网络通路中传输一个单元数据( 数据可大可小，与传输 的数据类型有关) 所需花费的指标。传输成本这个指标尤其在传统的c s 结构中， 或是在含有中心服务器的混合型p 2 p 网络模式中很重要。这是因为在连接中心服 务器的主干网络中传输一单元数据要比在边缘网络中即对等节点之间或是代理 服务器与客户端节点之间的线路上成本权重要大。因为主干网络负责传输较为重 要的或是较为紧急的数据，以达到保证系统稳定的目的。一旦主干网络出现拥塞， 将影响整个系统的服务性能。而边缘网络主要负责常规的请求数据，一般涉及的 客户端较少，对整个网络影响较小。这就鼓励流媒体系统设计者尽量的利用边缘 网络来传送数据，将主干网络留给最需要的数据，这样既可以保证整个系统的服 务质量也能提升系统的服务能力。 1 1 4 流媒体缓存技术概述 代理服务器缓存技术( p r o x yc a c h i n g ) 也称代理缓存技术，最初应用在w e b 内容的分发上。将那些经常被客户访问的w e b p 勺容( 尤其是相对较大文件，例如 动画、图片等) ，存储到服务器与客户端之间的代理服务器上，有效地节省了主 网络上的带宽，大大减少了用户时延 2 3 。同样的原理可以应用到流媒体传输 2 基于f 2 p 协作的代理缓存流媒体调度算法研究 中，正因为流媒体传输持续时间长，需要较大的传输带宽，采用代理缓存之后能 够有效的降低主干网络带宽压力和服务时延。 缓存技术的基本原理就是将用户请求率高的内容复制到代理服务器的内存 中，并通过一定的更新算法，使得硬盘中的数据与内存中的数据一致。这样客户 的请求基本上都能在内存中找到，而不需要去服务器硬盘中去找。这样能够有效 的减少服务器节点的资源，另外由于内存和硬盘的吞吐速度不样，系统延迟能 有效的改善。 多媒体缓存虽然也是将常用的数据缓存起来，但是和w e b 资源的缓存有相当 大的不同。因为媒体文件比普通的w e b 文件大很多，而且传输时间也长很多。在 有限的缓存空间下，w e b 文件可以很容易的被全部缓存，但媒体文件只能缓存少 数甚至一个都不能完全缓存。在这种情况下存储命中率极低，缓存变得完全没有 意义，而且替换也会变得很困难。总之w e b 缓存技术不能应用到媒体文件的缓存 策略中，为了能够将缓存技术应用到流媒体传输中必须要做到以下几点： 1 客户端的服务延迟能够得到有效的改善。 2 客户只能够感觉到服务延迟的降低和服务质量的提升，而不能将客户端操 作复杂化即客户端感觉不到缓存系统。 3 缓存技术能够不断的评价自己缓存的数据，不断的改变缓存中的数据，使 得有限的存储空间的利用率达到最大。而且在代理缓存失效的情况下，有备用的 解决方法，保证客户端的正常播放。 4 缓存技术应该尽量避免将服务压力集中到网络中的某个节点上，过度的依 赖一个或是特定的几个节点的话，会造成系统瓶颈和不安全因素增加。 5 缓存技术应该能够有一定的网络容错能力不能造成网络的不稳定。 1 2 课题的主要意义 本论文的研究是在国家科技支撑计划项目数字家庭软件技术集成开发与示 范( 2 0 0 7 b a h 0 7 8 0 0 ) 支持下展开的，数字媒体作为其中主要的研究内容，将结 合当前p 2 p 网络的主要研究成果和流媒体业务的重要应用背景。因此，论文选题 具有较高的前瞻性和较好的应用前景。 首先，随着多媒体应用的不断丰富，流媒体技术随着以视频点播、视频会议、 3 基于p 2 p 协作的代理缓存流媒体调度算法研究 远程教育、远程医疗、手机电视等典型应用得到迅速推广和普及，流媒体数据传 输流量已成为当今包括移动网络在内业务流量的主要组成部分。显然，流媒体和 非流媒体应用有着明显的不同，主要体现在以下几个方面，一是要求稳定高速的 传输带宽，二是较短的启动延时和较少的传输抖动，三是对异构系统环境要有更 好的屏蔽。因此，流媒体应用系统对网络的通信能力和流媒体技术本身都提出了 更高的要求并面临更新的挑战。 其次，流媒体内容分发是网络应用技术的重要研究内容，但目前仍然没有令 人满意的解决方案。那么，如何充分利用网络上的资源将是提高流媒体服务性能 从而保证用户观看质量的关键所在。 第三，如何充分利用网络上的资源从而有效地缓解其所面临的资源瓶颈。p 2 p 技术正是解决这一问题的主要候选方案。p 2 p 是一种分布式系统，各节点间通过 信息资源、存储器资源等的共享可协同完成任务。p 2 p 技术为服务共享、信息交 流等都提供了更加灵活高效的工作模式。 综上所述，流媒体赋予了宽带应用更多的娱乐性和交互性，更加丰富了网络 的内容表现形式，作为一种新兴媒体具有强大的吸引力。而基于p 2 p 的流媒体系 统，不仅充分利用客户节点的上传能力减轻了服务器的负担，而且无需额外架设 网络基础设施，更不需要组播等的支持，为解决流媒体内容分法提供了一个崭新 的发展空间。同时，该研究方向更为解决大规模流媒体应用中的可扩展性问题提 供了可行的方案，因此，也是近期国内外学术界关注的一个焦点。 本文综合考虑传输成本与缓存空间的利用率，尽量用边缘网络传输代替主干 网络传输，不断评价媒体文件的缓存效率，提高代理服务器缓存的媒体文件价值， 对p 2 p 流媒体技术展开研究，旨在提高流媒体的服务质量，进一步降低资源的消 耗，提高网络的传输效率，从而保证用户的观看质量。 1 3 问题的提出 1 3 1 当前研究面临的问题 在流媒体广泛应用的今天，流媒体技术远远没有达到人们希望的那样。当人 们发现p 2 p 模式能够很好的提升流媒体技术的服务能力，于是研发在p 2 p 环境下 4 基于p 2 p 协作的代理缓存流媒体调度算法研究 的流媒体技术成为重点，然而任何的模式都有自己的缺点和优点。我们应该更为 全面的分析一下传统的客户端服务器模式下面临的问题和p 2 p 模式下遇到的困 难，才能得到更好的应用效果。 1 媒体服务器处理能力的限制：在传统的客户端服务器模式下，中心媒体 服务器负责处理来自客户端的请求，同时向客户端发送他们需要的数据。当请求 过多时，中心服务器就会成为系统中最为繁忙和关键的节点，这样服务器的任何 瓶颈都会成为流媒体服务系统的限制。例如媒体服务器的处理能力，硬盘的吞吐 能力，存储空间的大小或是网络带宽的大小。 2 骨干网络带宽的限制：中心服务器连接都是带宽较大传输线路，通常采 用光纤。但是所有的数据都是中心媒体服务器通过该条线路传送。这样大大增加 了骨干网络的传输压力，造成较大的传输时延，增加网络拥塞的几率。 3 缓存空间的约束： 代理缓存服务器的缓存空间一般是有限的，无法完全将所有的被访问的媒体 对象全部复制下来，代理缓存算法的目的就是如何在有限的缓存空间下，合理的 选择缓存内容，尽可能的达到减轻服务器负载和网络带宽消耗的目的 3 。 在p 2 p 流媒体系统中，每个对等节点都会从邻居节点那里接收自己需要的数 据，同时将这些数据存储起来，以提供给需要这些数据的其他邻居节点。在通常 的v o d 系统中，由于每个对等节点之间访问的数据无关，同时节点之间加入系统 的时间也是随机的，在这种情况下不同媒体之间共享数据的可能性很低，因为存 储在每个节点内的数据重合度太低。节点缓存自己已经播放的数据意义不大，而 且一旦找到节点上存储有自己需要的数据，加之节点的不确定性。节点更倾向于 去服务器节点请求数据，从而增加了服务器的压力，失去了p 2 p 模式的优点，也 给普通节点的缓存空间增加了压力。 4 p 2 p 节点动态性限制：p 2 p 模式下节点的加入与离开都是随机行的，这就 是节点的动态性，这是p 2 p 结构的优点也是该结构的缺点，优点在于当客户请求 增加时，系统的处理能力也相应的增加了。但是受个人操作的影响太大，p 2 p 模 式下的系统处理能力始终处在不确定的状态中。对等节点基本上都是通过本地网 络与因特网相连，所以p 2 p 网络的性能在很大程度受制于本地网络环境。一旦本 地网络出现问题，相当于节点退出系统，必然会影响其他节点的服务质量。由于 5 基于f 2 p 协作的代理缓存流媒体调度算法研究 对等节点的随意性太大，在设计p 2 p 模式下流媒体系统时就必须考虑到这些问 题，能够迅速找出弥补方法，保证其他节点的正常播放。这是p 2 p 模式下流媒体 设计的一个难点。 5 因特网复杂的拓扑结构限制：p 2 p 网络技术是在现有的因特网上发展起 来的，由于因特网本身就是由不同拓扑结构的网络组成的异构网络。上层覆盖网 络拓扑与底层的通信拓扑不匹配。使得逻辑上相邻的节点和物理上的相邻的节点 不匹配，造成定位效率低。在选择相邻节点时如果不是物理上相邻的节点，就会 造成网络压力，传输时延较大，势必会造成用户o o s 的降低。底层网络是已经客 观形成的环境，必须寻找更为有效地逻辑覆盖网络，这也是p 2 p 模式下流媒体系 统的研究重点之一。 6 定位搜索特定数据端的限n - 特别是在p 2 p 模式下的流媒体系统中，媒 体文件被分成规模相对较小的数据段。节点自己有一个缓存窗口，将播放的数据 缓存下来，但是不可能缓存所有播放的数据，随着播放时间前行，缓存窗口中的 数据不断的被替换成刚刚播放过的数据。如果时间不匹配，邻居节点很难从这个 节点获得数据，这样会导致邻居节点没有可用数据而不得不暂停或是向服务器请 求数据。如果再使用“快进 “快退 “拖动”等操作，流媒体的数据段不是按照 顺序播放而是跳动到需要的数据段上。并且能够迅速查找到哪个节点上存储有这 个特定时序的数据段，这是也是p 2 p 模式下流媒体系统的难点之一。 7 服务质量的限制：流媒体传输文件规模大，持续时间长。要保证服务质 量的稳定就必须改进所有流媒体系统的参与者。客户端需要优化存储空间，数据 分发协议、编码容错等。在服务器方采用批处理等优化方法。但是基于p 2 p 模式 下保证服务质量，涉及到更多的方面。如何保证节点的服务质量，尽量使得p 2 p 技术透明化，同样是p 2 p 模式下流媒体系统研究的重点之一。 1 3 2 本文主要的研究内容 一个大规模的视频点播系统节目繁多，而且每个视频节目数据量巨大，显然 在这种情况下将所有节目复制到各个视频服务器的内存中的方式几乎是不可行 的。缓存管理策略对视频服务器重要资源进行管理，它的选择对视频点播系统的 性能和用户体验有很重要的影响。同时又要考虑到流媒体系统的稳定性与系统的 6 基于p 2 p 协作的代理缓存流媒体调度算法研究 服务能力，于是我们借鉴了两种流媒体构架模式，充分利用两种模式的优点。 1 我们将系统设计成为具有中心流媒体服务器节点的，同时代理服务器之间 为互相协作的p 2 p 节点的混合网络。代理服务器可以处理客户端节点的请求，同 时缓存部分必要数据，以提高系统的稳定性和服务能力。 2 代理缓存技术，本为主要研究代理服务器的缓存问题，由于代理服务器上 缓存的容量有限，要保证代理服务器能够充分的发挥其作用，必须要缓存那些最 有价值的流媒体文件，使得代理服务器中缓存的媒体文件都有最优的利用价值， 这就转化成如何将代理服务器存储空间更为科学的分配问题。这是一个典型的背 包问题，同时也是一个n p 问题，于是本文中我们把寻找最优解转化成为寻找次 优解，即用一个相似的但容易实现的解决办法来替换繁琐的最优解决办法。在本 文中我们提出一种基于p 2 p 协作的代理缓存调度算法。同时权衡了存储空间和传 输成本。 3 流媒体文件的受访特性及影响代理缓存分配的关键因素流行度。媒体 文件的受访特性与w e b 文件或其他文件的受访特性不同，在一段时间内特定的某 一些媒体文件的访问频率是有一定的规律性的也呈现出一定的周期性。这对于缓 存空间的分配有着重要的影响，根据媒体文件的流行度，将不同存储空间分配给 不同的媒体文件，实现空间利用率最大化。本文分析了媒体文件的受访特性，同 时有讨论了几种流行度的定义方法，并分析了各自的优缺点。 4 由于客户端在播放视频文件时，是由不同的代理服务和主代理服务器共同 提供的不同阶段的媒体流，同时每个媒体流的开始的时间片都是随机生成的，于 是将来自不同源的媒体流组成一个完整流畅的媒体流也是本文研究的一个内容。 1 4 论文的结构 本文的组织结构如下，第一章主要介绍p 2 p 流媒体系统的相关背景，相关的 研究工作，面临的问题与挑战以及本文的主要研究内容；第二章介绍流媒体及其 关键技术，其中包括两种流媒体应用中的网络模式，主要流媒体原理及传输技术 及缓存技术；第三章主要介绍流媒体文件的访问特性，并详细介绍了重要指标一 一流行度。第四章介绍了基于p 2 p 协作的代理缓存流媒体调度算法的具体实现； 第五章介绍了主要的仿真工具，并详细分析了算法比较结果。 7 基于p 2 p 协作的代理缓存流媒体调度算法研究 2 流媒体及其关键技术 2 1p 2 p 及相关技术 p 2 p ( p e e r t o p e e r ) 成为等连接或是对等网络，p 2 p 技术主要指由硬件形 成连接后的信息控制技术，最初起源于联网通信方式。能够增强网络的文件交换 级分布式计算等能力。为了便于介绍p 2 p 技术及特点，本节将在给出传统的客户 服务器模式的基础上引入p 2 p 技术，并给出了两者的对比分析。 2 1 1c s 模式 图2 - 1 传统c s 网络模式 c s 模式即客户端服务器模式是当前主要使用的网络模式，如图2 1 所示 服务器是网络服务的中心，绝大多数的计算处理发生在服务器上，客户端负责发 送请求和执行处理结果。由于万维网的发展使得c s 模式迅速发展，客户端的浏 览器很容易显示通过h t l p 协议传送过来的h t m l 数据。目前比较流行的网络应用 如万维网，邮件系统，文件传输，远程登入等都是c s 模式。我们可以归纳为客 户端通过相应协议，与负责处理的服务器连接，只要发送请求就能获得需要的结 果 4 。 这种模式结构简单而且需要客户端解决的事情并不多。维护主要在服务器端 进行，用户可以完全透明升级。这是该模式的优点，但缺点也很突出： 1 为了满足大量的客户端请求，规模必须很庞大。为了提高服务器的处理 8 基于p 2 p 协作的代理缓存流媒体调度算法研究 能力，复杂的计算机集群也是常用的解决方案。例如某著名搜索引擎，它是由一 万多台高性能计算机组成的计算机集群 5 为用户提供服务。 2 随着计算机硬件的发展个人计算机已经有了较高处理能力和较大存储空 间，在c s 模式下对客户端的硬件要求很低，这样无疑是对网络资源的一种闲置。 3 服务器是整个网络中最关键和最脆弱的。服务器的状态很大程度上就是 整个系统的状态，服务器不工作，客户端得不到服务 4 。 为了克服以上几个缺点，以下是常用的解决方案。 1 将多台服务器组成服务器集群，解决c l s 模式下服务器处理能力的瓶颈， 在网络方面，努力提高传输带宽，例如用传输能力更高的光纤。服务器集群是将 多个异构或是同构的计算机进行协同工作，完成处理工作。这种方案能够提高一 部分的服务能力，但是没有解决最为关键的网络问题，与提高的服务能力相比， 成本高昂。而且服务器群实现起来复杂度高，实现困难。 2 为了提高服务器能力的批处理技术( b a t c h i n g ) ，补丁技术( p a t c h i n g ) ，为 了解决网络瓶颈的周期广播技术，流合并流搭载( p i g g y b a c k i n g ) 技术。在一定的 范围内能够有效的解决带宽服务器服务能力的限制，减少用户的服务时延，提高 q o s 。但是c s 模式下的问题仍然存在。 3 组播技术，能够实现在网络中高效的一对多的通信，提高了系统的扩展能 力，但是i p 组播存在太多的限制例如难以实现拥塞控制和可靠性，特别是在点播 系统中组播技术的应用就更为困难。所以组播技术也没有广泛的应用。 4 在服务器与客户端之间部署代理缓存服务器( p r o x yc a c h i n gs e r v e r ) 或是 增加内容分发网络( c o n t e n td e l i v e r yn e t w o r k s ) ，客户端在请求媒体文件时， 客户从代理服务器或是分发网络中获得服务，只有代理服务器不能满足客户端 时，才向中心媒体服务器发送请求。代理服务器分担了一部分处理能力和网络压 力，能够提高一部分服务能力。但是该方法成本较高，代理服务之间是否协作也 是研究的难点之一。 9 基于p 2 p 协作的代理缓存流媒体调度算法研究 2 1 2p 2 p 网络模式 客户端 客尸靖 图2 2 p 2 p 网络模式 p 2 p 网络模式与c s 明显不同，该模式通过覆盖网络实现节点之间的互联， 使得节点之间互为服务器与客户端 7 。各个节点之间在理论上是平等的，且能 够互联的。这样c s 结构中过分依赖中心服务器的问题就会得到解决。如图2 - 2 所示，网络中的节点无需经过服务器或是中间节点就能实现直接互联。这样的网 络结构大大实现了网络负载平衡， 从图2 - 2 中可以看出p 2 p 网络是一种分布式网络体系结构，网络中的节点无 需经过中间方，就可以直接互相访问。在p 2 p 网络中所有节点既是服务和内容的 提供者，同时也是服务和内容的使用者。 p 2 p 技术可以利用网络中的空闲带宽，把提供服务的负担分散到网络中的各 个对等节点上，既消除了因为单点故障而造成的服务中断，也减缓了网络拥挤状 况 8 。一般认为p 2 p 网络有如下基本特征： 1 非中心化：非中心化是p 2 p 模式最主要的特点之一，但是并不意味着所有 的节点都是平等的完全没有中心。主要可以分为纯p 2 p 结构和混合的p 2 p 两类。在 纯p 2 p 结构中，每个节点都是平等的，在这种结构中没有服务器( 或特定的中心 节点) 负责管理，各个节点自行通信与协作。在混合的p 2 p 结构中，把p 2 p 结构与 传统的c s 相结合，保留了服务器功能。指定一个专门的节点( 通常都是超级节 点) 负责其他节点之间的通信，协同等任务。这种节点和节点之间相互通信大多 1 0 基于p 2 p 协作的代理缓存流媒体调度算法研究 数情况下并不需要服务器或是其他中间环节。p 2 p j e 中心化使得网络的可扩展性， 健壮性得到了巨大的提高，这个特点使得以前传统模式下的网络带宽和服务器处 理能力等限制条件不在重要。 2 网络的可扩展性：在客户端服务器模式下，不管如何优化服务器的处理能 力减少带宽压力，受模式特点限制这两点总是会成为服务能力的瓶颈。单靠提高 设备的计算能力和改用高带宽的传输线路，这不是科学的解决途径也不现实。在 对等网络中，由于没有中心服务节点，而且各个节点之间的功能也和传统模式不 同，越是有节点加入，服务能力也相应增加了。如果各个节点之间的协调算法比 较合适，还是能够完成所有客户端的请求。在这种纯对等网络中，不存在网络带 宽和处理能力的限制，在理论上来说这种扩充是没有限制的。在混合网络中，虽 然存在服务器，但是大部分的通信是对等节点之间完成的，服务器的存在只是增 加了系统的稳定性，当节点之间不能相互提供数据的情况下，可以向服务器请求， 这种情况基本上不会对服务器造成太大的压力，所以也能够给大量的客户端提供 服务。 3 性价比高：较高的性能与相对较低的投资是p 2 p 近年来发展迅速的主要因 素。由于个人计算机的迅速发展，个人计算机已经拥有较大的存储能力和计算能 力，网络带宽也在迅速增加，这些客观因素使得p 2 p 的应用更加有价值，利用这 些网络中的个人计算机可以真正实现高性能计算和海量存储的目的。由于客户端 总是在得到信息的同时贡献自己的数据与计算能力，成本相比于维护昂贵的中心 服务器来说要底很多。这是p 2 p 网络模式的经济优点。 4 网络负载均衡：在对等网络环境下，节点充当两个角色即客户端与服务器， 自己得到数据的时候同时提供数据。在传统模式下，处理数据与提供数据都是服 务器的工作，而客户端则仅仅负责发送求情和接收数据。网络中的数据严重不平 衡，在对等网络环境中信息会平等的存储到各个对等节点中，更能都实现资源的 平衡。 5 网络健壮性：网络健壮性是评价一个网络好坏的重要指标。在异构性强且 充满不稳定的网络中，影响传输质量的因素很多而且总在变动。尤其是在存在中 心节点的客户端服务器模式，一旦中心节点压力过大瘫痪或是被恶意攻击，所有 的客户都会受到影响。但是在p 2 p 结构中这种危险很小，具有耐攻击和高容错的 基于p 2 p 协作的代理缓存流媒体调度算法研究 特点。一些优秀的模型，还能够动态的检测网络和节点情况，自适应的调整，保 证服务质量的平滑过渡。部分节点的失效并不会对全部节点产生致命的影响，因 此节点可以在未经通知的情况下加入或是离开服务组，大大增强了网络的健壮 性。 c s 模式下的互联网是完全依赖于中心点服务器的，没有服务器，网络就 没有任何意义。而p 2 p 网络中，即使只有一个对等点存在，网络也是活动的，节点所 有者可以随意地将自己的信息发布到网络上。但相比传统的c s 模式，p 2 p 不易于 管理，而对c s 网络，只需在中心点进行管理。随之而来的是p 2 p 网络中数据的安 全性难于保证。因此，在安全策略、备份策略等方面，p 2 p 的实现要复杂一些。由 于对等点可以随意地加入或退出网络，会造成网络带宽和信息存在的不稳定。 2 1 3p 2 p 的网络拓扑结构发展 p 2 p 网络模式的拓扑结构即网络组织形式，主要经历了三种典型的结构，以 下对这三种结构详细分析： 1 集中p 2 p 网络拓扑结构 以n a p s t e r 9 为典型代表，它基本上是由传统的c s 模式加入p 2 p 思想形 成的。该结构包括中心服务器和具有交互能力的对等节点组成。不同于以往的结 构，客户端可以和服务器交互也可以和其他节点交互，但前提是必须去中心服务 器上获取索引信息。中心服务器不再像传统模式下存储所有的信息，在集中拓扑 结构中它只负责维护索引信息，供客户端节点查询所需的数据在什么位置。这样 中心服务器处理的事务大大减少，由于只向客户节点传输查询消息，连接中心服 务器的主干网压力也减轻不少。但是中心服务器依然没有摆脱传统c s 模式下的 缺点，就是过分依赖中心节点，一