基于p2p协作的代理缓存流媒体调度算法研究

《基于p2p协作的代理缓存流媒体调度算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

中国海洋大学硕士学位论文基于P2P协作的代理缓存流媒体调度算法研究姓名：魏青磊申请学位级别：硕士专业：计算机软件与理论指导教师：唐瑞春20090601 基于P2P协作的代理缓存流媒体调度算法研究摘要随着计算机硬件水平与宽带网络的迅速发展，多媒体服务越来越受到人们的欢迎。由于流媒体技术能够有效的实现直播与交互式点播，成为近来研究的热点。网络结构与调度算法关系到流媒体系统的服务质量，成为流媒体技术的研究重点。在流媒体网络模式中，传统c／s模式结构相对简单容易管理，但整个系统的服务能力受中央媒体服务与主干网络影响较大，不能很好的适应数据传输量大持续时间长的流媒体服务。于是人们提出P2P网络模式，网络中对等节点之间互为服务器与客户端，实现数据共享，但网络环境复杂对等节点难于管理。将经常被访问的数据缓存到离客户端相对较近的代理服务器上，通过代理服务直接为客户端提供服务，并且为增大缓存空间，将多个代理服务器组成簇，是一个有效提高服务质量减少用户时延的方法。由于缓存空间有限，代理服务器必须有选择性的缓存媒体文件。如何准确的选择需要缓存的数据并把这些数据分配到不同代理服务器，使得系统能够服务更多用户，提供更好的服务质量，是缓存算法面临的主要问题。为解决上述网络模式问题，本文采用具有中心流媒体服务器，且代理服务器能够进行P2P协作的混合网络。能够有效避免c／s模式下过分依赖中心流媒体服务器的情况，及纯P2P网络环境下节点之间难于管理，易造成网络抖动的情况。在缓存数据的选择上，本文引入以数据量为基础的媒体文件流行度Popularity和缓存效率CE，按照流行度高的数据占用较大存储空间的原则，利用媒体文件的存储效率为每个前缀分配相应的存储空间。在数据传输时，连接中心媒体服务器的主干网络需要传输一些必要的数据，增强客户端交互性或是避免网络抖动，保证客户端正常播放。在不影响客户端播放质量的情况下，应该尽量利用边缘网络传输数据减少主干网络压力。本文将为主干网络与边缘网络赋予不同权重，引入c(f，．，，p：)表示媒体文件，在代理服务器．，缓存P：的数据量时所需的传输成本，并按传输成本将前缀降序排列，代理服务器升序排列。将前缀依次分配到代理服务器上，使得整个网络中传输成本最小。 本文提出的基于P2P协作的代理缓存流媒体调度算法PCSPC(Proxy-CachingSchedulerbasedonP2PCooperation)，选取合适的网络模式，综合考虑缓存空间利用率与传输成本，．使代理缓存尽量存储价值较高的前缀部分，提高了客户端请求命中率，特别是在存储空间受限的情况下，该算法优点突出。在传输数据时，本算法使得普通数据倾向于在代理服务器与客户端之间的边缘网络上传输，保证主干网络传输必要的控制信息与紧急信息。特别是在用户请求频繁时，主干网络压力上升缓慢，能够服务较多用户。在文章最后通过仿真结果，与其他类似算法相比，证明其有效性。关键词：流媒体；P2P协作；代理缓存；存储效率；传输成本； ResearchonProxy—eachingScheduIerbasedonP2PCooperationAbstractWiththerapiddevelopmentofcomputerhardwareandWideBand，multimediaservicebecomemoreandmorepopular．Asstreaming—mediatechnologyprovideconditionstoreal—timevideoandVOD(videoondemand)，manyexpertsarefocusedonit．Networkstructureandscheduleralgorithmsarcresearchpoint，fortheyCallaffecttheefficientofstreaming-mediasystem’SQoS(Qualityofservice)．Inthenetworkstructureofstreaming·media，thetraditionalC／Smodeisrelativelysimpleandmanagedeasily，however，thecapacityofsystemisimpactedseriouslybycentermediaserverandbackbonenetworkanddonotadapttostreaming—mediaservice、析thheavydataandlongtime．Tochangethiscondition，P2PnetworkmodeWasraised，peersarebothserverandclientforeachother．Thatmakesdatasharedamongthem，howeverpeersmanageddifficultly。Theregularlyaccesseddataiscachedintheproxyserverwhichisrelativeclosetoclient．Proxyserverservesdirectlytoclient．OrganizinganumberofserversaSaclustertoincreasecachespaceisanefficientwaytoreducetheservicedelayandincreaseQoS。Asthelimitofcachespace，proxyservershavetocachethemostvaluabledata．ItistheimportproblemofcachingalgorithmthatchoosingthemostvaluabledataexactlyandassigningtodifferentproxyserversmakethesystemservemoreclientsandprovidebetterQoS．Forresolvingaboveproblemsofnetworkmode，thispaperusesthehybridnetworkmode、)l，ithcentermediaserverandproxyserverswhichconnecteachotherbyP2Pcooperation．ThisCanavoidtheconditionthatsystemdependsoncentermediaserverexcessivelyinC／SmodeandtheconditionthatpeersaremanageddifficultlyinpureP2Pnetworkmode．Whenchoosingofdata,thispaperintroducesthemediafilepopularityandcachingefficiencybasedondatastatistics．Accordingtotheprinciplethatmorepopulardataareassignedmorecache，allocatecorrespondingcachetoeverymediafile’Sprefixbyitspopularity．Whensendingthedataonnetworks，thebackbonehastosendsome necessarydatatoincreasealternationwithclientsandavoidnetworkjitterandguaranteetheQoS．WithoutinfluenceQos，thesystemshouldsenddatausingtheedgenetworktoreducethepressureofbackbone。Thispapergivesthebackboneandedgenetworksdifferentrights，introducesc(i，-『，p：)denotingthetransmissioncostwhenmedia‘fileihasp：dataontheproxyserverj．Prefixsequenceandproxysequencearesortedinascendinganddescendingorderrespectivelybytransmissioncost．Andthenassigningprefixtoproxyserversmakesthetransmissioncostasleastaspossible．ThepaperproposesProxy—CachingSchedulerbasedonP2PCooperation(PCSPC)，whichchoosesanappropriatenetworksmodeandconsidersbothcachingefficiencyandtransmissioncost．Thisalgorithmincreaseshitratio，especiallyintheconditionthatcacheislimitedusingthewaythatproxyserverscachethemostvaluableprefix．Itmakesdatatobesentonedgenetworksinsteadofbackboneforensuringthetransmissionofcontrolinformationandurgencyinformationonbackbone．Especiallywhenlotsofclientrequest，thepressureofbackbonewillincreaseslowly,thisletsystemservemoreclients．Inthelastsectionofthepaper,simulationresultsshowtheeffectivenessofthestrategy．Keywords：Streamingmedia：P2Pcooperation：proxy—caching；cachingefficiency：transmiSSioncost 独创声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过囊勺研究成果，也不包含未获得(洼!垫遗直基丝益要挂剔直盟笪：奎拦豆窒2或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息研究所将本学位论文收录到《中国学位论文全文数据库》，并通过网络向社会公众提供信息服务。(保密的学位论文在解密后适用本授权书)学位论文储躲棚撕签字日期∥7年p导师签字：签字日期： 基于P2P协作的代理缓存流媒体调度算法研究1绪论1．1．1选题背景流媒体(StreamingMedia)是指在Internet中采用流式传输技术(指将大文件分成有序列的小文件)的多媒体。用户在点播流媒体文件，等待片刻，就能观看媒体文件，而不需要下载整个文件，流式媒体文件允许边下载边播放。流媒体技术的原理就是按照时间顺序将媒体文件分成不同的片段，然后将这些规模很小的文件发送给客户端，在客户端将这些规模小的媒体文件按时间顺序重新组织起来，并将音频包与视频包同步，形成在客户端连续播放的视频流。随了流媒体技术的发展，视频直播与视频点播(VOD)逐渐被人们熟悉，而且应用广泛，例如在新闻点播，远程教育，数字图书馆，电子商务采购等文化，商业，娱乐，通信领域。在流媒体迅速发展的背后，不但为各个应用领域带来了极大的方便，同时成为电信运营商的一大主流增值业务，带给他们巨大的利润空间。但是，流媒体技术远远没有成熟，无论是理论上还是技术上都面临很多问题，比如，寻找最稳定的网络连接，最多的媒体资源，最快的传输速率，最短的网络延迟，最优值的服务效果等。所以流媒体技术还有着巨大的研究空间与研究价值。1．1．2流媒体技术中的网络模式传统的流媒体系统是基于C／s(Client／Server)模式的，主要由服务器和客户机组成，其中服务器可以是一台也可以是多台组成，客户机的数量则由服务器的服务能力决定。在该模式下，客户机之间基本上是独立的，如果有相同的请求，服务器必须通过网络向不同的客户机发送相同的数据。在该模式下系统能够同时服务的客户机数量就成为系统容量或是系统服务能力，该模式下的服务能力主要由服务器的处理能力和服务器端的网络带宽决定，在有的系统中服务器的内存大小，吞吐能力也是决定因素之一。在该模式下，服务器端的可用带宽有限，传输的流媒体文件则需要消耗大量的带宽，且占用时间长。单纯的提高服务器的处理能力增加服务器的存储空间，系统的服务能力也不能得到有效的提高。在带宽的限制下，系统仅能同时服务几百左右的客户端，在小型的应用中尚可，但是不具 基于P2P协作的代理缓存流媒体调度算法研究备大型应用的经济规模。另外，由于因特网的特性，在传输数据量大持续时间长的流媒体文件的过程中，肯定会出现例如，延迟，抖动，丢包，网络阻塞等问题，使得服务质量(QoS)不能得到保证。该系统中最为关键的问题还是带宽消耗问题，服务器向每一个客户发送请求的数据，而且是单独发送没有复用，这将迅速的挤占带宽资源导致系统服务能力不高。在新兴的P2P网络模式中人们往往考虑巨大的因特网中分布着许多计算机空闲资源，P2P技术的原理就是采用分布式算法将这些空闲资源利用起来为因特网上的用户提供各种服务。网络的每一个节点(peer)既可以作为客户接受其它节点的服务，也可以作为服务器向其它节点提供服务[1]。在P2P结构中节点之间基本上都是平等的，削弱了服务器在网络中的中心的特殊地位，所以与传统的客户端服务器模式相比，有一些独特的优势。1．1．3传输成本概述传输成本是衡量不同网络通路中传输一个单元数据(数据可大可小，与传输的数据类型有关)所需花费的指标。传输成本这个指标尤其在传统的C／S结构中，或是在含有中心服务器的混合型P2P网络模式中很重要。这是因为在连接中心服务器的主干网络中传输一单元数据要比在边缘网络中即对等节点之间或是代理服务器与客户端节点之间的线路上成本权重要大。因为主干网络负责传输较为重要的或是较为紧急的数据，以达到保证系统稳定的目的。一旦主干网络出现拥塞，将影响整个系统的服务性能。而边缘网络主要负责常规的请求数据，一般涉及的客户端较少，对整个网络影响较小。这就鼓励流媒体系统设计者尽量的利用边缘网络来传送数据，将主干网络留给最需要的数据，这样既可以保证整个系统的服务质量也能提升系统的服务能力。1．1．4流媒体缓存技术概述代理服务器缓存技术(ProxyCaching)也称代理缓存技术，最初应用在Web内容的分发上。将那些经常被客户访问的WebP勺容(尤其是相对较大文件，例如动画、图片等)，存储到服务器与客户端之间的代理服务器上，有效地节省了主网络上的带宽，大大减少了用户时延[2][3]。同样的原理可以应用到流媒体传输2 基于F2P协作的代理缓存流媒体调度算法研究中，正因为流媒体传输持续时间长，需要较大的传输带宽，采用代理缓存之后能够有效的降低主干网络带宽压力和服务时延。缓存技术的基本原理就是将用户请求率高的内容复制到代理服务器的内存中，并通过一定的更新算法，使得硬盘中的数据与内存中的数据一致。这样客户的请求基本上都能在内存中找到，而不需要去服务器硬盘中去找。这样能够有效的减少服务器节点的资源，另外由于内存和硬盘的吞吐速度不～样，系统延迟能有效的改善。．多媒体缓存虽然也是将常用的数据缓存起来，但是和Web资源的缓存有相当大的不同。因为媒体文件比普通的Web文件大很多，而且传输时间也长很多。在有限的缓存空间下，Web文件可以很容易的被全部缓存，但媒体文件只能缓存少数甚至一个都不能完全缓存。在这种情况下存储命中率极低，缓存变得完全没有意义，而且替换也会变得很困难。总之Web缓存技术不能应用到媒体文件的缓存策略中，为了能够将缓存技术应用到流媒体传输中必须要做到以下几点：1．客户端的服务延迟能够得到有效的改善。2．客户只能够感觉到服务延迟的降低和服务质量的提升，而不能将客户端操作复杂化即客户端感觉不到缓存系统。3．缓存技术能够不断的评价自己缓存的数据，不断的改变缓存中的数据，使得有限的存储空间的利用率达到最大。而且在代理缓存失效的情况下，有备用的解决方法，保证客户端的正常播放。4．缓存技术应该尽量避免将服务压力集中到网络中的某个节点上，过度的依赖一个或是特定的几个节点的话，会造成系统瓶颈和不安全因素增加。5．缓存技术应该能够有一定的网络容错能力不能造成网络的不稳定。1．2课题的主要意义本论文的研究是在国家科技支撑计划项目《数字家庭软件技术集成开发与示范》(2007BAH07800)支持下展开的，数字媒体作为其中主要的研究内容，将结合当前P2P网络的主要研究成果和流媒体业务的重要应用背景。因此，论文选题具有较高的前瞻性和较好的应用前景。首先，随着多媒体应用的不断丰富，流媒体技术随着以视频点播、视频会议、3 基于P2P协作的代理缓存流媒体调度算法研究远程教育、远程医疗、手机电视等典型应用得到迅速推广和普及，流媒体数据传输流量已成为当今包括移动网络在内业务流量的主要组成部分。显然，流媒体和非流媒体应用有着明显的不同，主要体现在以下几个方面，一是要求稳定高速的传输带宽，二是较短的启动延时和较少的传输抖动，三是对异构系统环境要有更好的屏蔽。因此，流媒体应用系统对网络的通信能力和流媒体技术本身都提出了更高的要求并面临更新的挑战。其次，流媒体内容分发是网络应用技术的重要研究内容，但目前仍然没有令人满意的解决方案。那么，如何充分利用网络上的资源将是提高流媒体服务性能从而保证用户观看质量的关键所在。第三，如何充分利用网络上的资源从而有效地缓解其所面临的资源瓶颈。P2P技术正是解决这一问题的主要候选方案。P2P是一种分布式系统，各节点间通过信息资源、存储器资源等的共享可协同完成任务。P2P技术为服务共享、信息交流等都提供了更加灵活高效的工作模式。综上所述，流媒体赋予了宽带应用更多的娱乐性和交互性，更加丰富了网络的内容表现形式，作为一种新兴媒体具有强大的吸引力。而基于P2P的流媒体系统，不仅充分利用客户节点的上传能力减轻了服务器的负担，而且无需额外架设网络基础设施，更不需要组播等的支持，为解决流媒体内容分法提供了一个崭新的发展空间。同时，该研究方向更为解决大规模流媒体应用中的可扩展性问题提供了可行的方案，因此，也是近期国内外学术界关注的一个焦点。本文综合考虑传输成本与缓存空间的利用率，尽量用边缘网络传输代替主干网络传输，不断评价媒体文件的缓存效率，提高代理服务器缓存的媒体文件价值，对P2P流媒体技术展开研究，旨在提高流媒体的服务质量，进一步降低资源的消耗，提高网络的传输效率，从而保证用户的观看质量。1．3问题的提出1．3．1当前研究面临的问题在流媒体广泛应用的今天，流媒体技术远远没有达到人们希望的那样。当人们发现P2P模式能够很好的提升流媒体技术的服务能力，于是研发在P2P环境下4 基于P2P协作的代理缓存流媒体调度算法研究的流媒体技术成为重点，然而任何的模式都有自己的缺点和优点。我们应该更为全面的分析一下传统的客户端服务器模式下面临的问题和P2P模式下遇到的困难，才能得到更好的应用效果。1．媒体服务器处理能力的限制：在传统的客户端服务器模式下，中心媒体服务器负责处理来自客户端的请求，同时向客户端发送他们需要的数据。当请求过多时，中心服务器就会成为系统中最为繁忙和关键的节点，这样服务器的任何瓶颈都会成为流媒体服务系统的限制。例如媒体服务器的处理能力，硬盘的吞吐能力，存储空间的大小或是网络带宽的大小。2．骨干网络带宽的限制：中心服务器连接都是带宽较大传输线路，通常采用光纤。但是所有的数据都是中心媒体服务器通过该条线路传送。这样大大增加了骨干网络的传输压力，造成较大的传输时延，增加网络拥塞的几率。3．缓存空间的约束：代理缓存服务器的缓存空间一般是有限的，无法完全将所有的被访问的媒体对象全部复制下来，代理缓存算法的目的就是如何在有限的缓存空间下，合理的选择缓存内容，尽可能的达到减轻服务器负载和网络带宽消耗的目的[3]。在P2P流媒体系统中，每个对等节点都会从邻居节点那里接收自己需要的数据，同时将这些数据存储起来，以提供给需要这些数据的其他邻居节点。在通常的VoD系统中，由于每个对等节点之间访问的数据无关，同时节点之间加入系统的时间也是随机的，在这种情况下不同媒体之间共享数据的可能性很低，因为存储在每个节点内的数据重合度太低。节点缓存自己已经播放的数据意义不大，而且一旦找到节点上存储有自己需要的数据，加之节点的不确定性。节点更倾向于去服务器节点请求数据，从而增加了服务器的压力，失去了P2P模式的优点，也给普通节点的缓存空间增加了压力。4．P2P节点动态性限制：P2P模式下节点的加入与离开都是随机行的，这就是节点的动态性，这是P2P结构的优点也是该结构的缺点，优点在于当客户请求增加时，系统的处理能力也相应的增加了。但是受个人操作的影响太大，P2P模式下的系统处理能力始终处在不确定的状态中。对等节点基本上都是通过本地网络与因特网相连，所以P2P网络的性能在很大程度受制于本地网络环境。一旦本地网络出现问题，相当于节点退出系统，必然会影响其他节点的服务质量。由于5 基于F2P协作的代理缓存流媒体调度算法研究对等节点的随意性太大，在设计P2P模式下流媒体系统时就必须考虑到这些问题，能够迅速找出弥补方法，保证其他节点的正常播放。这是P2P模式下流媒体设计的一个难点。5．因特网复杂的拓扑结构限制：P2P网络技术是在现有的因特网上发展起来的，由于因特网本身就是由不同拓扑结构的网络组成的异构网络。上层覆盖网络拓扑与底层的通信拓扑不匹配。使得逻辑上相邻的节点和物理上的相邻的节点不匹配，造成定位效率低。在选择相邻节点时如果不是物理上相邻的节点，就会造成网络压力，传输时延较大，势必会造成用户OoS的降低。底层网络是已经客观形成的环境，必须寻找更为有效地逻辑覆盖网络，这也是P2P模式下流媒体系统的研究重点之一。6．定位搜索特定数据端的限N-特别是在P2P模式下的流媒体系统中，媒体文件被分成规模相对较小的数据段。节点自己有一个缓存窗口，将播放的数据缓存下来，但是不可能缓存所有播放的数据，随着播放时间前行，缓存窗口中的数据不断的被替换成刚刚播放过的数据。如果时间不匹配，邻居节点很难从这个节点获得数据，这样会导致邻居节点没有可用数据而不得不暂停或是向服务器请求数据。如果再使用“快进"“快退"“拖动”等操作，流媒体的数据段不是按照顺序播放而是跳动到需要的数据段上。并且能够迅速查找到哪个节点上存储有这个特定时序的数据段，这是也是P2P模式下流媒体系统的难点之一。7．服务质量的限制：流媒体传输文件规模大，持续时间长。要保证服务质量的稳定就必须改进所有流媒体系统的参与者。客户端需要优化存储空间，数据分发协议、编码容错等。在服务器方采用批处理等优化方法。但是基于P2P模式下保证服务质量，涉及到更多的方面。如何保证节点的服务质量，尽量使得P2P技术透明化，同样是P2P模式下流媒体系统研究的重点之一。1．3．2本文主要的研究内容一个大规模的视频点播系统节目繁多，而且每个视频节目数据量巨大，显然在这种情况下将所有节目复制到各个视频服务器的内存中的方式几乎是不可行的。缓存管理策略对视频服务器重要资源进行管理，它的选择对视频点播系统的性能和用户体验有很重要的影响。同时又要考虑到流媒体系统的稳定性与系统的6 基于P2P协作的代理缓存流媒体调度算法研究服务能力，于是我们借鉴了两种流媒体构架模式，充分利用两种模式的优点。1．我们将系统设计成为具有中心流媒体服务器节点的，同时代理服务器之间为互相协作的P2P节点的混合网络。代理服务器可以处理客户端节点的请求，同时缓存部分必要数据，以提高系统的稳定性和服务能力。2．代理缓存技术，本为主要研究代理服务器的缓存问题，由于代理服务器上缓存的容量有限，要保证代理服务器能够充分的发挥其作用，必须要缓存那些最有价值的流媒体文件，使得代理服务器中缓存的媒体文件都有最优的利用价值，这就转化成如何将代理服务器存储空间更为科学的分配问题。这是一个典型的背包问题，同时也是一个NP问题，于是本文中我们把寻找最优解转化成为寻找次优解，即用一个相似的但容易实现的解决办法来替换繁琐的最优解决办法。在本文中我们提出一种基于P2P协作的代理缓存调度算法。同时权衡了存储空间和传输成本。3．流媒体文件的受访特性及影响代理缓存分配的关键因素——流行度。媒体文件的受访特性与web文件或其他文件的受访特性不同，在一段时间内特定的某一些媒体文件的访问频率是有一定的规律性的也呈现出一定的周期性。这对于缓存空间的分配有着重要的影响，根据媒体文件的流行度，将不同存储空间分配给不同的媒体文件，实现空间利用率最大化。本文分析了媒体文件的受访特性，同时有讨论了几种流行度的定义方法，并分析了各自的优缺点。4．由于客户端在播放视频文件时，是由不同的代理服务和主代理服务器共同提供的不同阶段的媒体流，同时每个媒体流的开始的时间片都是随机生成的，于是将来自不同源的媒体流组成一个完整流畅的媒体流也是本文研究的一个内容。1．4论文的结构本文的组织结构如下，第一章主要介绍P2P流媒体系统的相关背景，相关的研究工作，面临的问题与挑战以及本文的主要研究内容；第二章介绍流媒体及其关键技术，其中包括两种流媒体应用中的网络模式，主要流媒体原理及传输技术及缓存技术；第三章主要介绍流媒体文件的访问特性，并详细介绍了重要指标一一流行度。第四章介绍了基于P2P协作的代理缓存流媒体调度算法的具体实现；第五章介绍了主要的仿真工具，并详细分析了算法比较结果。7 基于P2P协作的代理缓存流媒体调度算法研究2流媒体及其关键技术2．1P2P及相关技术P2P(Peer—to—Peer)成为等连接或是对等网络，P2P技术主要指由硬件形成连接后的信息控制技术，最初起源于联网通信方式。能够增强网络的文件交换级分布式计算等能力。为了便于介绍P2P技术及特点，本节将在给出传统的客户／服务器模式的基础上引入P2P技术，并给出了两者的对比分析。2．1．1C／s模式图2-1传统C／S网络模式C／S模式即客户端／服务器模式是当前主要使用的网络模式，如图2—1所示服务器是网络服务的中心，绝大多数的计算处理发生在服务器上，客户端负责发送请求和执行处理结果。由于万维网的发展使得C／S模式迅速发展，客户端的浏览器很容易显示通过HTl'P协议传送过来的HTML数据。目前比较流行的网络应用如万维网，邮件系统，文件传输，远程登入等都是c／s模式。我们可以归纳为客户端通过相应协议，与负责处理的服务器连接，只要发送请求就能获得需要的结果[4]。这种模式结构简单而且需要客户端解决的事情并不多。维护主要在服务器端进行，用户可以完全透明升级。这是该模式的优点，但缺点也很突出：1．为了满足大量的客户端请求，规模必须很庞大。为了提高服务器的处理8 基于P2P协作的代理缓存流媒体调度算法研究能力，复杂的计算机集群也是常用的解决方案。例如某著名搜索引擎，它是由一万多台高性能计算机组成的计算机集群[5]为用户提供服务。2．随着计算机硬件的发展个人计算机已经有了较高处理能力和较大存储空间，在c／s模式下对客户端的硬件要求很低，这样无疑是对网络资源的一种闲置。3．服务器是整个网络中最关键和最脆弱的。服务器的状态很大程度上就是整个系统的状态，服务器不工作，客户端得不到服务[4]。为了克服以上几个缺点，以下是常用的解决方案。1．将多台服务器组成服务器集群，解决ClS模式下服务器处理能力的瓶颈，在网络方面，努力提高传输带宽，例如用传输能力更高的光纤。服务器集群是将多个异构或是同构的计算机进行协同工作，完成处理工作。这种方案能够提高一部分的服务能力，但是没有解决最为关键的网络问题，与提高的服务能力相比，成本高昂。而且服务器群实现起来复杂度高，实现困难。2．为了提高服务器能力的批处理技术(Batching)，补丁技术(Patching)，为了解决网络瓶颈的周期广播技术，流合并流搭载(Piggybacking)技术。在一定的范围内能够有效的解决带宽服务器服务能力的限制，减少用户的服务时延，提高QoS。但是c／s模式下的问题仍然存在。3．组播技术，能够实现在网络中高效的一对多的通信，提高了系统的扩展能力，但是IP组播存在太多的限制例如难以实现拥塞控制和可靠性，特别是在点播系统中组播技术的应用就更为困难。所以组播技术也没有广泛的应用。4．在服务器与客户端之间部署代理缓存服务器(ProxyCachingServer)或是增加内容分发网络(ContentDeliveryNetworks)，客户端在请求媒体文件时，客户从代理服务器或是分发网络中获得服务，只有代理服务器不能满足客户端时，才向中心媒体服务器发送请求。代理服务器分担了一部分处理能力和网络压力，能够提高一部分服务能力。但是该方法成本较高，代理服务之间是否协作也是研究的难点之一。9 基于P2P协作的代理缓存流媒体调度算法研究2．1．2P2P网络模式客户端客尸靖图2—2．P2P网络模式P2P网络模式与c／s明显不同，该模式通过覆盖网络实现节点之间的互联，使得节点之间互为服务器与客户端[7]。各个节点之间在理论上是平等的，且能够互联的。这样c／s结构中过分依赖中心服务器的问题就会得到解决。如图2-2所示，网络中的节点无需经过服务器或是中间节点就能实现直接互联。这样的网络结构大大实现了网络负载平衡，从图2-2中可以看出P2P网络是一种分布式网络体系结构，网络中的节点无需经过中间方，就可以直接互相访问。在P2P网络中所有节点既是服务和内容的提供者，同时也是服务和内容的使用者。P2P技术可以利用网络中的空闲带宽，把提供服务的负担分散到网络中的各个对等节点上，既消除了因为单点故障而造成的服务中断，也减缓了网络拥挤状况[8]。一般认为P2P网络有如下基本特征：1．非中心化：非中心化是P2P模式最主要的特点之一，但是并不意味着所有的节点都是平等的完全没有中心。主要可以分为纯P2P结构和混合的P2P两类。在纯P2P结构中，每个节点都是平等的，在这种结构中没有服务器(或特定的中心节点)负责管理，各个节点自行通信与协作。在混合的P2P结构中，把P2P结构与传统的C／S相结合，保留了服务器功能。指定一个专门的节点(通常都是超级节点)负责其他节点之间的通信，协同等任务。这种节点和节点之间相互通信大多10 基于P2P协作的代理缓存流媒体调度算法研究数情况下并不需要服务器或是其他中间环节。P2Pj[E中心化使得网络的可扩展性，健壮性得到了巨大的提高，这个特点使得以前传统模式下的网络带宽和服务器处理能力等限制条件不在重要。2．网络的可扩展性：在客户端服务器模式下，不管如何优化服务器的处理能力减少带宽压力，受模式特点限制这两点总是会成为服务能力的瓶颈。单靠提高设备的计算能力和改用高带宽的传输线路，这不是科学的解决途径也不现实。在对等网络中，由于没有中心服务节点，而且各个节点之间的功能也和传统模式不同，越是有节点加入，服务能力也相应增加了。如果各个节点之间的协调算法比较合适，还是能够完成所有客户端的请求。在这种纯对等网络中，不存在网络带宽和处理能力的限制，在理论上来说这种扩充是没有限制的。在混合网络中，虽然存在服务器，但是大部分的通信是对等节点之间完成的，服务器的存在只是增加了系统的稳定性，当节点之间不能相互提供数据的情况下，可以向服务器请求，这种情况基本上不会对服务器造成太大的压力，所以也能够给大量的客户端提供服务。3．性价比高：较高的性能与相对较低的投资是P2P近年来发展迅速的主要因素。由于个人计算机的迅速发展，个人计算机已经拥有较大的存储能力和计算能力，网络带宽也在迅速增加，这些客观因素使得P2P的应用更加有价值，利用这些网络中的个人计算机可以真正实现高性能计算和海量存储的目的。由于客户端总是在得到信息的同时贡献自己的数据与计算能力，成本相比于维护昂贵的中心服务器来说要底很多。这是P2P网络模式的经济优点。4．网络负载均衡：在对等网络环境下，节点充当两个角色即客户端与服务器，自己得到数据的时候同时提供数据。在传统模式下，处理数据与提供数据都是服务器的工作，而客户端则仅仅负责发送求情和接收数据。网络中的数据严重不平衡，在对等网络环境中信息会平等的存储到各个对等节点中，更能都实现资源的平衡。5．网络健壮性：网络健壮性是评价一个网络好坏的重要指标。在异构性强且充满不稳定的网络中，影响传输质量的因素很多而且总在变动。尤其是在存在中心节点的客户端服务器模式，一旦中心节点压力过大瘫痪或是被恶意攻击，所有的客户都会受到影响。但是在P2P结构中这种危险很小，具有耐攻击和高容错的 基于P2P协作的代理缓存流媒体调度算法研究特点。一些优秀的模型，还能够动态的检测网络和节点情况，自适应的调整，保证服务质量的平滑过渡。部分节点的失效并不会对全部节点产生致命的影响，因此节点可以在未经通知的情况下加入或是离开服务组，大大增强了网络的健壮性。c／s模式下的互联网是完全依赖于中心点——服务器的，没有服务器，网络就没有任何意义。而P2P网络中，即使只有一个对等点存在，网络也是活动的，节点所有者可以随意地将自己的信息发布到网络上。但相比传统的C／S模式，P2P不易于管理，而对C／s网络，只需在中心点进行管理。随之而来的是P2P网络中数据的安全性难于保证。因此，在安全策略、备份策略等方面，P2P的实现要复杂一些。由于对等点可以随意地加入或退出网络，会造成网络带宽和信息存在的不稳定。2．1．3P2P的网络拓扑结构发展P2P网络模式的拓扑结构即网络组织形式，主要经历了三种典型的结构，以下对这三种结构详细分析：1．集中P2P网络拓扑结构以Napster[9]为典型代表，它基本上是由传统的c／s模式加入P2P思想形成的。该结构包括中心服务器和具有交互能力的对等节点组成。不同于以往的结构，客户端可以和服务器交互也可以和其他节点交互，但前提是必须去中心服务器上获取索引信息。中心服务器不再像传统模式下存储所有的信息，在集中拓扑结构中它只负责维护索引信息，供客户端节点查询所需的数据在什么位置。这样中心服务器处理的事务大大减少，由于只向客户节点传输查询消息，连接中心服务器的主干网压力也减轻不少。但是中心服务器依然没有摆脱传统c／s模式下的缺点，就是过分依赖中心节点，一旦中心节点瘫痪，整个网络将会完全崩溃。每一次节点之间交换信息，总会经过中心节点，缺乏有效的强制共享机制，资源可用性不好。在小规模的网络中，中心节点维护的索引信息表并不会过分复杂，但是当网络规模达到一定的程度，数据交换变的频繁起来，维护索引信息的成本将会大大增加，使得中心服务器的瓶颈问题再次出现。2．纯粹的P2P网络拓扑结构‘6nutell其中的代表，该结构中所有的节点互为客户端与服务器。节点之间 基于P2P协作的代理缓存流媒体调度算法研究互相平等，不存在中心服务器。通过逻辑覆盖网中相邻接点，可以遍历整个P2P网络。这种网络模式的优点显而易见，由于不依赖中心服务器，整个网络负载比较均衡，不会因为一个节点的失效，瘫痪整个网络。但是缺点就是为了寻找符合条件的伙伴节点，需要遍历一个范围很大的网络，遍历算法与定位算法会产生很大的数据量，网络带来压力容易造成网络拥塞，影响其他节点之间的通信。对等节点管理困难，容易遭受恶意进攻。3．混合P2P拓扑结构Fasttrack，GuntellaO．6，KAZaa都是其中的典型。在集中式结构和纯粹P2P结构的基础上提出，既不会过分依赖于某一个点，造成网络负责不均衡，也不会因为各个节点都是平等的而造成网中充斥着遍历信息与定位信息。其基本思想是在纯粹P2P结构的基础上，引入功能不同的节点，负责索引与搜索。类似将集中式结构中，中心服务器的功能分配各多个功能节点去完成。索引节点处理搜索请求，返回请求所需的媒体资源列表，索引节点负责保存可以利用的节点信息，并维护这些节点的状态信息。普通节点通过这些功能节点获取信息，而不需要自己遍历网络定位节点。混合的P2P网络模式比大多数其他网络稳定，而且效率较高。是流媒体系统比较常用网络拓扑结构。2．1．4P2P流媒体技术P2P流媒体系统中，当一个节点接收到另一个节点的请求，发送方的服务质量控制层会根据网络状况和质量需要调整发送参数，然后将数据打包，通过P2P网络技术进行分发，接收方受到数据之后，接收方质量控制层对接收到数据进行调整，然后解码按照数据包的时序调整顺序，将视频与音频同步，然后播放。在有的系统中，为了给另外的节点提供数据，还将替换自己缓存窗口中的数据。一般P2P流媒体传输过程包括以下几个步骤。1．媒体文件压缩技术：原始媒体文件规模较大，存在很大冗余信息。规模较大的文件存储、传输困难。将冗余的信息去掉之后，既可以提高存储空间的利用率，也能够以较为经济的方式传输。所以，多媒体技术首先就县罂减少数据冗余，提高数据压缩率。2．媒体服务质量控制：在复杂的因特网中传输规模较大的媒体文件，面临着 基于P2P协作的代理缓存流媒体调度算法研究各种各样的挑战。所以用户在不同时间有着不同的服务质量要求。服务质量控制主要有媒体文件传输的实时性和数据包出现丢失时如何进行容错处理。保证数据的实时性就是要防止网络抖动和预防丢包和服务延时。例如在网络出现拥塞的情况下及时告知发送方减少数据发送率，只发送必要数据(如果数据分层的话)。容错处理就是当数据包确实丢失的情况下，尽量保持服务质量。例如可以利用预测帧，保持播放流畅。3．媒体组播技术：这里组播技术主要是在应用层，通过应用层独立进行，将数据包复制，并利用应用层路由技术发送数据包。解决了网络层对组播技术的障碍。4．普通对等节点的流媒体服务器技术：在混合的P2P网络模式下，对等节点也充当多媒体服务器的角色。利用对等节点完成传统流媒体服务器的功能，例如能够对应用层和传输层进行控制，很好的处理点播请求，根据网络情况调节发送速率，存储部分媒体文件。这种技术在任何网络模式下都是必要的。有的对等节点为了完成直播功能，例如实时监控，还需要在模拟信号与数字信号之间转换。同时具备网络处理功能。5．流媒体传输协议：网络传输协议是流媒体技术发展的基础，包括因特网的基本媒体传输协议及一些实时传输协议。例如实时传输协议，实时传输控制协议。还有专门符合P2P网络模式下的流媒体协议。只有适合环境的协议才能发挥出流媒体技术的优势。P2P技术在流媒体直播中比较简单，因为直播中交互数据少控制协议比较容易实现。但是在交互频繁的点播请求中，为了实现VCR功能，流媒体控制协议复杂程度较高。导致P2P技术在流媒体点播业务中发展缓慢，但视频点播技术是流媒体技术中的主要应用。P2P模式下，对等节点相互共享数据，媒体文件的版权问题变得难以管理。6．媒体同步技术：流媒体主要传输的就是影音信号，但是影像数据和声音数据是各自独立的，但是在播放的时候却是相互联系的。如何在因特网中传输影音信号，并在接收端同步播出是流媒体技术的关键之一。特别是在复杂的P2P网络中，如果同步出现问题，对服务质量影响巨大。这涉及影音数据的按序列发送与接收端如何重新排序以消除网络抖动对数据的影响。每个节点都贡献自己的一部分存储空间。当媒体文件由中心媒体服务器提供14 基于P2P协作的代理缓存流媒体调度算法研究之后，节点之间就可以相互请求和应答，从而减轻媒体服务器的压力并增加了存储空间。文献[10]建立了一种盖然缓存模型，该模型克服了P2P网络异构性和服务客户节点稀少等弊端；文献[11]提出了P2VoD的多播树技术，用来解决点播服务中P2P网络异构性和服务节点失败等问题；文献[12]提出一种混合P2P流媒体点播模型TTVOD，提高了数据冗余度和分发特性。由于媒体文件播放传输时间长，在播放或传输时间内很难保证有足够的资源支持媒体文件正常播放或传输。因为系统内的节点加入和离开都是随机的同时没有任何通知，会引起较大的网络抖动。而流媒体传输对网络的抖动又是极为敏感的，这也是P2P发展过程中的一个主要障碍。2．2流媒体技术一I圜 基于P2P协作的代理缓存流媒体调度算法研究2．2．1流媒体技术原理媒体文件规模巨大不适合网络传输，为了符合流式传输，需要必要的预处理。一是降低质量，为的是减少数据量，既可以减轻网络压力也能减少服务节点的处理数据。二是压缩数据，去除冗余数据。流式传输将规模较大的媒体文件以一个个小数据包的形式异步传输给接收方。流式传输需要接收方缓存数据，便于将数据包按照时间顺序排序。因为传输时间长，各个数据包选择路径不同，到达时间也不尽相同。同时为了防止网络抖动，缓存一部分数据是必要的，这样能够争取一定的时间，让系统针对网络抖动启动补救方法。在P2P网络模式下这一点更有意义，可以为其他节点提供缓存数据。图2—4流式传输的基本原理图如图2-4所示，流式传输需要选择合适的网络协议。HTTP协议是万维网的基础，HTTP协议是应用层协议需要下层TCP协议作为保障。TCP连接是可靠连接，连接双方必须传输过多的控制信息以保证数据的可靠性。但不适合传输流媒体数据，因为数据量巨大，采用尽最大能力的UDP协议最为合适，利用TCP来传输控制信息。在图中客户端利用Web浏览器登入到服务端的Web服务器，Web服务器为用户提供媒体文件的信息，并接收请求。媒体服务器接到请求之后，直接通过RTSP等媒体传输协议将数据发送给接收方。RTP主要针对媒体文件数据流的实时传输，RTSP主要针对一对多的传输流媒体数据，RTCP协议主要提供控制信息。16 基于P2P协作的代理缓存流媒体调度算法研究2．2．2流媒体播送技术为了改进流媒体系统的服务能力，在网络传输中利用流合并技术，带宽复用技术，改进传输协议，在服务器端增加批处理能力，在服务器与客户端之间加入代理服务器。各种方法都是为了满足人们更高的要求，为了能够更好达到这个目的数据的传送方式也需要改进。1．单播技术(Unicast)单播技术指服务器与客户端之间点对点连接[14]这是网络通信中普遍的通信方式。在流媒体传输过程中客户端与媒体服务器之间是一个单独的互联通路。是一一对应的关系，一个发送方一个接收方，发送的数据只能经由通道被这个接收方接收到。理论上数据不能共享线路不能复用。单播技术如下图2-5所示。图2-5单播示意图仅仅利用单播技术往往出现在早期的c／s结构中。以媒体服务器为网络中心，用户分别向服务器发送请求，服务器为每个客户端单独发送数据。这种情况能够保证媒体服务质量，受网络抖动影响小。随着系统规模的增加，为骨干网络和服务器处理能力带来巨大的压力。由于硬件设备和还带宽条件的不断提高，单播还是有自己的用武之地。在网络边缘，代理服务器与客户端之间，或是内容提供节点与接收节点之间的单播应用依然广泛。17 基于P2P协作的代理缓存流媒体调度算法研究2．多播技术(Multicast)多播也就是组播，组播的基本思想就是向特定的一组用户进行广播，一个发送方和一组接收方，组外成员不能获取数据除非加入该组[15]。组播不是一种新技术，在IP网络中已经能共实现，只是没有多少应用机会，随着流媒体技术的发展IP组播再次得到重视。组播技术可以使得媒体服务器批处理成为可能。图2-6多播示意图如图2-6所示，中心流媒体服务器可以只发送一个数据流就能同时服务多个客户端，而且媒体服务器不需要知道到底有多少客户端。这是因为以前由媒体服务器负责为每一个客户端请求发送数据，现在由路由器复制数据包并转发出去，路由器向其他子网路由器发送一个数据流，子网路由器再进行复制转发。这时客户端请求数据时，只需要告知子网路由器加入该组接收数据即可。组播在理论上可以利用一台媒体服务器为数万台客户端提供服务，而且可以保证服务质量。路由器只在最末端复制和转发数据，这样大大减少了网络中传输的数据，使得网络压力减少，网络阻塞的发成概率下降。服务器不需要处理每一个请求，也减少了服务器压力。这些都有利于提高流媒体系统的服务质量。组播技术的限制是必须有多播路由器支持，如果网络中多播路由器的数量较少，很多用户将得不到服务。组播技术在小范围内的局域网应用广泛，在复杂的异构广域网中，不能保证每个路由器都支持多播，应用起来难度较大。同时广播是一种服务器端推服务，互动较少，客户端基本上都是被动接收数据，在直播流域应用广泛，但是点播要求客户端与服务器端交互而且每个客户端需求的数据也不相同，客户端不能共享数据，所以在点播中组播技术还有一定限制。18 基于P2P协作的代理缓存流媒体调度算法研究3．点播技术(on-demand)点播是指媒体服务器提供的一种“拉"服务。客户端主动请求服务，建立服务器与客户端单播通道，客户端发送VCR功能请求。点播是单播的另一种形式，对带宽要求较高，但是服务质量较好，‘交互性高。4．广播技术(Broadcast)广播与点播相反，是一种服务器“推"模式的服务。客户端被动接收数据，客户端不能向服务器发送VCR功能请求。与组播的一对多不一样，组播只是向加入多播组的客户端发送数据，广播则是向所有网内用户发送数据。在某种意义上，广播是一个将全网视为一组的组播技术，在流媒体点播中应用不多，因为不管用户是否需要，服务器都将发送数据，造成网络中充斥这垃圾信息，给网络造成压力，导致网络阻塞影响真正需要数据的客户。而且交互性不好，但是在范围较小的局域网中可以应用到电话会议中，但这时的广播就退化成为网络组播。2．3缓存技术2．3．1缓存简介日⑧缓存图2—7代理缓存的应用环境如图2-7所示，代理服务器部署在媒体服务器和客户之间。代理服务器的引入主要源于互联网中的热点现象，所谓热点现象就是在一定时期内，人们关注的内容具有集中的特性。代理服务器存在的意义就在于存储热点信息。利用较少的存储空间应对比较高的访问频率，代理服务器的缓存功能具有减少主干网带宽的要求，减少服务器负载，减少启动延迟，提高系统服务能力。通常代理服务器只存储媒体文件中的一部分，用来减少需要缓存的数据量，从而提高代理服务器缓一器一一务一／L乡一服一带划一理一甲一 基于P2P协作的代理缓存流媒体调度算法研究存媒体文件的数量。文献[16]提出只缓存媒体文件中每个块的前缀部分从而减少用户时延增强交互性：文献[17]提出将比较流行的媒体文件的前几块作为前缀进行缓存，用来减少用户时延；杨戈等n羽研究了当在代理服务器上缓存的数据与其流行的程度成正比时，可节约缓存空间，减少补丁通道的数据量；廖建新等n钔提出了基于流行度与网络代价的缓存策略。以上几个调度策略都是基于单个代理服务器，由于单个代理服务器缓存空间有限，缓存技术始终存在着存储空间瓶颈。2．3．2实现架构媒体般务器RTP敷据包图2—8流媒体代理服务器示意图图2—8所示，为代理服务器构架模型，其中包括请求管理模块，缓存对象管理模块，缓存磁盘与RTP协议模块[203。其中请求管理模块负责客户端与服务器端的控制信息通信。缓存对象管理主要负责缓存什么数据，什么时候更新。RTP协议模块主要负责流式传输，以下将对各个模块有一个详细的介绍：1．RTP协议模块：由于媒体文件采用流式传输，用户播放数据的同时请求后续数据，并下载到缓存中。如果后续数据不能及时的到达客户端，服务质量受到很大影响，但是后续数据不能及时的到达有很多方面的原因，其中最主要的原因就是网络抖动和异步传输中丢包。还有就是在客户端不能将接收到的数据组成流畅的数据流。为了解决这些问题，IETF(网络工程服务组)提出RTP／RTCP[21][22](流媒体实时传输协议／流媒体传输控制协议)，其中RTP加入更多支持实时传输的信息，包括标示数据来源，每个数据包的序列号，时间戳，以及标示数据的负荷类型。而RTCP负责传递控制信息，为传送的数据提供服务质量反馈。20 基于P2P协作的代理缓存流媒体调度算法研究2．缓存对象管理模块：该模块是代理服务器的关键模块，也是代理服务器存在的意义，很多研究算法在此展开[23][24][25】。代理服务器就是存储受访频率较高的热点数据，并为客户端提供服务。前文讲到代理服务器与客户端之间的传输成本权重较低，而在主干网络上传输成本权重较高。用权重低的方式去替换权重高的方式，能够增加系统的服务能力。代理服务不会缓存整个媒体服务器中的数据，只能存储部分，但是如果代理服务器上存储的数据命中率不高，客户不得不去中心服务器请求，则代理与客户之间传输成本较低的优势不能得到发挥。为了提高命中率，缓存对象管理模块必须时刻评价存放在缓存空间中的数据，最大化的利用存储空间。缓存管理模块的主要任务有，评价数据是否应该放入缓存空间，决定某个文件在缓存中的空间[26]，合理利用网络带宽[27]，统计媒体文件受访特征执行对应的替换算法等。3．请求管理模块：主要运行RTSP协议，这主要是为客户提供与媒体服务器之间的VCR功能通信。RTSP协议还具有，可扩展行，易解析，安全，独立传输，支持多服务器等特性。在此协议上客户可以向服务器发送“快进～播放”“快退"等一系列交互式操作。请求管理模块就是解析这些请求并根据不同情况负责转发。转发RTSP请求情况发生在用户请求代理服务器无法满足的情况下，代理服务器负责将请求交给中心服务器。4存储空间：代理服务器最终将数据存储到本地存储空间中。空间中的数据基本分为两种一种是媒体文件数据(基本上是多个媒体文件的一部分，通常是前缀，或是后缀的前缀等一些热点数据)，另一种就是支持缓存管理模块算法的记录信息。例如每个文件对应的流行度，存储空间大小，请求频率等。2．3．3缓存技术的评价方法及指标缓存技术最早应用在Web请求中，能够有效的降低服务延时，提高服务数量。其中设计缓存替换算法或是数据选择算法等。如何评价一个代理缓存算法，变得很重要。在Web时代，代表算法有记录驱动的仿真算法。记录是指Web日志数据，这是反映数据流量特征的主要依据，在日志中记录了特定时间间隔内媒体文件被访问而产生的HTTP协议的请求信息。现在很多记录数据在网络上都能找得到：与Web日志数据类似，在流媒体技术中，流媒体日志的数据主要记录客户端21 基于P2P协作的代理缓存流媒体调度算法研究启动的实时传输协议请求，但是真实的请求记录却比较难获取[28]。为了弥补数据不足的缺陷，研究人员发现，除了直接分析日志获取数据之外，可以借助分析受访特征，对流媒体访问建模分析[29]。建模之后，人们可以通过某个指标来评价缓存算法的好坏。以下是几种常用的指标：1．请求命中率(RequestHitRatio)：以一个文件为单位，代理服务器上缓存的数据命中客户端请求的数量与客户端总请求数量的比。该指标反映了缓存算法确定流行文件的能力。通常评估关于Web的算法。2．字节命中率(BytesHitRatio)：以字节为单位，代理服务器上缓存的数据命中客户端请求的数量与客户端总请求数量的比。该指标比请求命中率类似，但更为准确，但应用范围不同。字节命中率是衡量缓存算法对网络负载改善情况。字节命中率与对骨干网络需求成反比。命中率愈小负载改善越小，反之改善情况越好。3．空间利用率：这个指标表示代理缓存是否被有效利用，换句话说就是缓存空间所存储的数据是不是必要的数据。代理缓存空间存在的目的只是为了存储热点信息，增加缓存空间势必提高系统成本，所以不必存储所有中心服务器上的文件，如果存储得当，在有限的空间内一样能够服务更多的客户。4．延迟请求比(DelayedResponseRatio)：在代理技术中，存储的是热点信息而不是所有数据，所以肯定会有客户端请求代理服务器落空的情况。落空之后，客户端不得不去向中心服务器请求，或是代理服务器转发客户请求，造成延时增加。延迟请求比就是未命中的客户端请求数与所有客户端请求数的比。该指标经常用来衡量缓存算法对服务质量改善的情况。该指标大表示该算法对服务质量改善不明显。延时请求比越小，说明平均时延小[30][31]。5．加权命中率(WeightedHitRatio)：同请求命中率一样也是衡量确定文件流行度能力的大小，但更准确。它是指所有从缓存中请求得到的媒体文件长度与所有请求数据量程度的比。在文献[32]中用该指标衡量缓存算法。6．质量命中率(QualityHitRatio)：该指标与加权命中率或请求命中率类似，只是适用范围有所不同。主要用来评价分层编码的流媒体缓存技术中，有时候也称用户体验难易度指标。它是指缓存能够满足客户端请求的媒体片段质量与所有请求需要的媒体片段质量的比。在文献[33]中使用分层缓存技术，质量命中 基于P2P协作的代理缓存流媒体调度算法研究率就是很重要的评价指标。7．平均缓存对象数(AverageNumberofcachedVideoobject)：该指标指的是，代理缓存空间中包含媒体文件的平均数量。这个指标经常用来评价部分缓存算法(例如代理服务器只缓存媒体文件的前缀或是后缀的前缀等)，平均数量多大，说明空间中包含的媒体文件个数多，但媒体数量多与服务质量之间还是有区别的。平均数量过大说明算法没有很好的把握到热点信息。平均数过小说明算法倾向于存储热点信息，不能兼顾其他媒体文件。2．3．4主要缓存算法分析：缓存技术中，应用环境基本上都是基于两点假设，一是主干网络传输成本较高，尽量节省主干网络带宽。二是代理服务器与客户端之间带宽比较充裕。这种情况基本上出现在同构网络中，近年来接入网技术的发展使得代理服务器与客户端之间的连接变得复杂。代理缓存不但需要考虑媒体文件的存储效率，流行度还要考虑分层的服务质量问题。于是基于环境不同分为同构网络下的流媒体缓存算法和异构网络下的缓存算法。1．同构网络下的流媒体缓存算法在同构网络中缓存算法关注的重点不是网络问题，而是存储内容。因为在同构网络规模较小而且客户端情况相近，接入网络不复杂且传输比较有保障(一般都是规模相对较小的局域网)。根据缓存数据选取的不同，基本上可以分为三大类。基于间隔的缓存策略，基于片段的缓存策略和选择缓存策略(1)基于间隔的缓存(Intervalbasedcaching)间隔缓存算法(IntervalCaching)：最初是在文献[34]中提出的。其基本思路是，当两个客户端请求同一个媒体文件时，缓存算法启动并将，这个媒体文件介于这两个客户端请求间隔内的数据保存到缓存窗口中。缓存窗口中的数据根据时间的前进逐步的由新的数据替换。这样后到客户端在代理服务器上就能获取自己所需的数据。这种算法在理想的情况下，即两个客户端请求间隔非常的小，代理服务器只需要存储很小的一部分数据就能保证第二个客户端正常播放。代理服务在很短的时间内存储间隔数据并将数据发送给第二个客户端，紧接着更换滑动窗口中的数据，数据吞吐量大，开始部署在代理缓存的内存中。该算法今年来 基于P2P协作的代理缓存流媒体调度算法研究有了更多改进版本。基于资源的缓存算法(ResourcebasedCaching)，在文献[35]中改进了时间间隔缓存算法，一是将算法部署到了代理服务器的磁盘中，二是提出了一个辅助方法，首先根据媒体文件和网络情况，启发式的决定一个存储单元的大小，这个存储单元表示一个滑动的间隔或是一系列的间隔的组合。由于有了磁盘空间大大增加了缓存的能力，所以存储单元可以增大到一个完整的媒体文件。这样及时两个客户端请求之间间隔比较大，第二个客户端依然能够从代理服务器上获取数据。这种算法基本上适用于客户端频繁访问并且访问数据大致类似的情况，也就是说必须有较高的时域邻近性。代理服务器缓存很少一部分数据就能够服务后续客户端。但是一般情况下的多媒体受访规律都不会是这样，算法的效率收请求间隔影响很大，特别是客户端访问过于离散且两个请求之间相距太远。最极端的情况就是将整个文件全部缓存下来，这样就失去了代理缓存的意义。比较合适的算法是将关键内容缓存下来，代替没有选择性的间隔缓存。(2)基于分段的缓存(SegmentbasedCaching)分段缓存的主要思想就是将媒体文件按照播放时间分成一个个的片段，在缓存算法中以分成的数据段为操作基本单元。因为缓存颗粒清晰灵活度高，分段缓存算法是比较流行的解决方案。如何决定段大小和段替换算法是研究的重点。前缀缓存最早在文献[36]提出，前缀只是一个模糊的概念指的是从媒体文件开头部分到媒体文件的某个位置。与前缀对应的就是后缀，再有细分还可以分为后缀的前缀，和后缀的后缀。在一般情况前缀都是事先存储在代理服务器上的，当客户端请求数据时，代理服务器就把前缀部分发送给客户端，并转发请求给中心服务器，去请求后缀部分的内容。在改进算法中，代理服务器可以一边转发从中心服务器得到的后缀部分存储到本次空间中，当有后续客户请求同样的数据，代理服务器就可以服务这些节点，而不需要再次请求中心服务器。这样可以有效的降低启动时延，减少中心服务器的压力。但是其中的难点在于如何确定前缀部分的大小。在文献[37]表明，前缀缓存在网络客观限制下，达到启动延时最小是一个背包问题。实现起来很困难，但是可以通过其他方法来来获得次优解。．指数分段及类似缓存算法简介：在大多数分段缓存算法中，不只是将媒体文 基于F2P协作的代理缓存流媒体调度算法研究件分成前缀和后缀部分，而是将媒体文件分成等长或是变长的多个数据段。多数流行的划分算法是将媒体文件分成变长的数据段。指数分段算法将媒体文件按照指数增长的规律分成若干个小的数据段。首先规定一个基础单元块，后面的块按照指数规律增长。例如第i段是由Z以个块组成。这个规律并不是无限持续下去，当第rl段大于某个特定的值时，段的增长将停止，或是按照等分原则划分或是将后边所有的数据都划分成一块数据。这是因为按照流媒体受访特性，文件开头的部分总是被频繁访问，而后面的数据则不太经常访问。代理服务器首先存储开始的几个数据段，花费较少的存储空间，就能够很好的满足客户需求。如果该媒体文件被频繁访问，就开始依次存储后面较大的数据段，等到请求热度下降之后，代理缓存可以放弃这些大的数据段，迅速回收空间缓存其他媒体文件，提高了系统的灵活性。由于该算法在降低服务延时，提高服务质量方面比较突出，所以出现了很多改进算法，主要是体现在不同的段划分规律上。例如摩天大楼算法，其中数据段不是按照基础块指数增长，而是持续的几个数据段都保持一个大小，紧接着后续的几个块再增大并保持一样⋯⋯，同样也存在着一个最大数据段的限制。还有就是该算法，如果将基础数据块划分很大，也就是前几个数据段规模较大，由于前几个数据段总是容易被访问到，这样明显就能减少用户的启动时延，但是需要的代理服务器存储空间就会变大。启动延迟与代理服务器存储空间是算法两端的限制条件，很多算法在两者之间寻找最优方法或是容易实现的次优解。由于将媒体文件分段缓存，可以提供给客户单预览功能。在文献E38]中，客户端可以请求这些分段缓存在代理服务器上的媒体文件，其中可以浏览的数据段称之为关键片段。客户端可以根据这个交互功能迅速找到自己观看的媒体文件。(3)基于选择缓存(SelectiveCaching)与分段缓存不同，代理服务器不是从头开始缓存数据，而是按照不同情况，选择缓存不同数据。例如缓存算法受缓存空间条件约束，算法针对网络有无服务质量保证，提出两种帧选取算法一可靠网络选择缓存和尽量传输网络缓存。当网络可靠时，尽量让网络上传输的数据少，在网络不可靠的时候就要多发帧数，以保证接收端能够接收到足够多的数据保持服务质量，文献r39]提出一类算法，不依赖于时间轴，而是选择缓存数据轴上速率较高的数据。这种选择方法很适合 基于P2P协作的代理缓存流媒体调度算法研究变比特率的流传输中。2．异构网络下的流媒体缓存算法由于接入网络的发展，网络异构性成为流媒体技术需要解决的问题。在这种网络环境下，客户端环境相差很大，对视频质量的要求也不尽相同。为应对不同的网络带宽，数据发送方按照客户端请求和带宽情况，需要自适应的改变传输速率。异构环境下的媒体技术大致可以分为，结合可扩展编码的缓存技术即分层编码和结合编码转换的缓存技术。(1)结合扩展编码的缓存技术该技术也成为划分层次编码技术，利用分层次的比特流结构对媒体文件压缩。层次结构主要有：基本层与增强层。基本层为了维持客户端的正常播放，它可以独立解码。增强层用于提高服务质量，并且存在多个增强层。网络环境好的客户端可以获取多个增强层来提高服务质量。在异构网络中，代理服务器为减少启动延迟，需要确定缓存内容尽量缓存流行度较高的媒体文件。为了保证不同网络情况下的客户端的服务质量，代理服务器也需要确定缓存质量。该技术最大的挑战就是设法满足以上这两个限定条件。(2)结合编码转换的缓存技术编码转化技术发展还不成熟，其基本思想是：通过码率转换，分辨率转换和语法间转换等，满足不同带宽，不同客户端，和不同的网络环境。该方法应用范围广且适应性较好，但何时进行编码转换依然存在不少问题。 基于P2P协作的代理缓存流媒体调度算法研究3流媒体内容受访特征分析与流行度流媒体内容的受访特征与流行度，是流媒体代理缓存技术中重要的决定指标。流媒体文件访问会在某些周期，某些文件上表现出规律性。分析这些特性有助准确把握热点信息，提高缓存技术的准确性，减少用户时延提高服务质量。3．1用户对媒体访问的行为的研究从上个世纪九十年代，流媒体专家发现分析客户端访问特性有助于提高代理缓存技术的服务效果。最有代表性的Zipf-like分布模型，描述了客户端请求偏好的规律。这样就可以指导缓存算法中代理服务器倾向于存储那些受偏好的文件，做到减少成本提高效率。Zipf规律最初体在词的收索，规律如下：R×F—C(3-i)其中F表示在检索中某个词出现的频率，然后将这些词按照F降序排列，尺表示这个词的在队列中序号。以上两个数的积即值C总是在一个中心值附近徘徊。在媒体文件受访特征研究中，我们同样按照Zipf规律，假定一组数据。并且将这些媒体文件按受访次数降序排列。总请求次数为Ⅳ，f为某个媒体文件在序列中的位置，m表示该文件被访问的次数。流行度我们可以定义为：p(f)一万t?／(3-2)上式中数据i是我们比较容易得到的数据，在众多的方法中都试图找出p(i)与i的关系。文献[40]和文献[41]分别从不同的实验数据中分析发现pO)与i在对数坐标系下基本上成一条直线分布，因此推断数据项被访问次数与数据序号有下列关系：109‰(i)-c—logi(3—3)进而推出： 基于P2P协作的代理缓存流媒体调度算法研究10c删；当盟．翌竺仔4，i∑‰(f)’令了堡一；Q则∑‰(f)pG)。旱(3—5)l其中，‰(f)代表第f个数据项被请求的次数，万为数据项的个数，c和Q都是常数。上式说明媒体文件受访特性也遵循Zipf规律。在后续研究中又将规律演化为：p(i)--昙(3-6)其中a的变化范围为0．4珈．9。其中指数a代表了请求集中度，当a大的时候表明人们只关注几个媒体文件，a比较小的时候，客户端访问的媒体文件相对较多，热点信息不明显。由于接近Zipf规律，这个规律就成为“Zipf-like"规律。在这个规律中就体现出20／80原则，也是媒体文件访问中普遍的规律，即80％的用户倾向于访问20％的热点文件。而其他80％的文件则只有2096的受访概率。按照这个规律，代理缓存算法就会将重点放到热点文件中。用户访问规律为代理缓存使用有限的缓存空间即可较明显地改善用户服务质量和网络带宽消耗提供了理论基础，流媒体缓存算法设计时的重要依据和评价方法。在上述的讨论中，Web访问符合Zipf规律，媒体文件访问符合Zipf—like规律，但是媒体访问负责的多，Zipf-like只体现出来在一定时间内，多数用户请求少量的热点信息的规律，但是在实际缓存过程中，缓存算法必须适应不同的网络环境，客户端不同质量要求。仅仅利用该规律将热点信息缓存到代理服务器上去，是远远不够的。Zipf-like规律是一个基本规律，指导我们在设计算法时，对待媒体文件可以有重点有区分。还有其他比较值得注意的媒体访问特性。如下：1．流媒体文件长度并不等于其播放时间，但是二者经过对数变换，比较好的符合了正态分布。也就是说不考虑媒体文件编码效率等问题，媒体长度大小意味着播放时间大小。 基子F2P协作的代理缓存流媒体调度算法研究2．媒体文件受访特性集中度比Zip更为明显即越靠前越频繁，访问频率越是靠前的媒体文件，所占总的请求数越多。例如排名前百位的媒体文件接收近85％的客户请求。3．媒体文件受访比Web内容受访更具有时间特性。在队列中比较靠前位置的媒体文件具有明显的时间相关性，排位比较靠后的媒体文件表现并不明显。最高流行度文件之间，时间相关性最强。4．媒体文件的受访特性表现出明显的以天为单位的周期性。每天都会出现基本规律的波峰与波谷。在一星期中，也表现出一定的周期性。媒体文件被访问的次数，与人们的活动规律有关。3．2媒体受访特性与流行度的关系为了调整媒体的缓存质量，目前的自适应媒体对象普遍使用分层编码方法，但由于编码层数受到各种制约而数量有限，故难以达到细粒度的速率自适应调整。于是人们提出了使用基于MPEG-4编码的FGS媒体对象来增加速率调整的粒度。为了调整媒体的缓存部分，人们往往将整个媒体对象从时间上分为若干部分，许多研究表明用户对媒体对象的访问往往具有提前结束访问的性质，关于提前结束访问的性质，下一节有详细介绍。基于此种现象使用了基于前缀的缓存算法，即将一个媒体对象分成两个部分：一个长度一定的前缀和长度不定的后缀，并根据用户提前结束访问的概率分别调整这两部分的缓存质量来优化代理服务器的性能。但是此算法中前缀长度及提前结束概率需要预先确定，并且无法跟随具体情况的变化而自适应调整。这些要求在实际环境下很难满足。为了解决这个问题，我们将媒体对象分成若干片段，并借助于每个媒体对象片段的流行度信息来得到最终的缓存策略。随着对媒体对象片段的流行度的研究，人们发现该流行度是服从一定规律分布的。媒体文件的流行度与媒体文件的受访特性有着明显的联系，我们可以利用媒体文件的受访特性来预测媒体文件的流行度，受访特性与流行度相互结合才能得到媒体缓存的最佳结果。关于流行度的研究，下一节有详细介绍。所以我们通过记录用户对媒体对象的某些片断的访问信息，并根据内部流行度的分布规律计算每个片段的流行度信息，然后将缓存 基于F2P协作的代理缓存流媒体调度算法研究问题划归为一个受约束的优化问题，并通过动态规划算法决定缓存哪些片断以及缓存怎样的质量。3．3现有流行度分析的不足在流媒体系统中，人们很早就发现，媒体文件受访特性与Web内容受访特性不同，所以大部分算法集中在如何反映媒体文件的受访特性上。例如，引入文件生命范围，时域邻近性，进程特性等指标。媒体流行度的讨论却基本上停留在定性分析上，缺少定量分析的数学模型，和更为科学的流行度定义。1．媒体流行度的定性分析文献[42]通过近200天对mMOD系统样本分析，发现媒体文件在请求之后，并不是所有的客户会从始至终的观看该影片，有45％的请求没有持续到文件播放结束，其中多数客户是通过预览媒体文件的开始部分，决定是否完成观看。预览的文件开头部分仅仅占到整个文件的5％左右。在分段缓存技术中，媒体文件的开始部分被频繁的访问到，在同一文件位置比较靠后的分段则流行度相对较低。根据此规律，很多算法都是将比较靠前位置的数据段优先缓存或逆序置换把握媒体文件的高流行度数据段。研究人员只是就该规律做统计数据的描述，没有给出模型定量分析。2．已有的定量分析模型将定性分析中发现的规律，利用不同的数学分布进行建模分析，并引入了切断点的概念。流行度在断点两边是不同的，在断点前面流行度利用指数分布模型确定，后面利用平均分布模型确定。但是该模型存在一个重要的问题，即由于采用两个不同的分布模型，断点的选择很关键，而且每个媒体文件的断点不同，使得该模型应用困难。以上流行度的获取，基本上都是通过分析实际数据来获得。但分析数据需要很长时间积累，且不易获得。有研究者直接对媒体文件的流行度建立假设模型，在有的方法中，利用已有指标(数据段序号或是整个媒体文件的流行度)来推算某个数据段的流行度。但是缺少实际数据的证明，目前很难得到普遍认同。 基于P2P协作的代理缓存流媒体调度算法研究3．4媒体流行度3．4．1内容流行度为了确定媒体文件的不同部分的流行度，一种较常用的方法是将媒体文件按照一个小的时间间隔分成若干段(通常按照现在媒体播放器的控制精度，将分段的基本单位定1秒)。假设媒体文件f其长度为￡，在时间间隔△，I，2内，有Ⅳ个对媒体文件f的请求，避免影片长度不同的影响，毛来代表第j『次请求对影片f访问的情况，则访问向量足，定义如下：焉@，={三第，个薯霎甚黑军墨苒豁c3—7)其中七