摘 要：本文研究了流媒体传输领域的相关技术，并对其进行总结分类。对服务器流调度技术、代理缓存技术、节目替换算法等进行了详细介绍。
关键词：流媒体传输 服务器流调度 代理缓存机制
近年来互联网上基于视频、音频的流媒体应用呈飞速发展的趋势。流媒体有着广阔的市场前景[1]。然而流媒体应用不同于Web上普通的文本、图片的浏览，有其独特的一面。由于视频文件巨大，持续时间长，且要求具有实时性，所以传送视频时需要很大的带宽。
阻碍流媒体发展的因素主要是带宽问题，包括服务器磁盘带宽和网络带宽，二者中相对较小者决定了系统服务用户的数目。流媒体传输技术面临如此多的挑战，从而吸引许多学者在这方面进行研究，并取得了一定的成果。本文针对这些技术进行了总结。
对流媒体传输技术的研究主要涉及：(1)服务器流调度技术。(2)代理缓存技术。(3)节目替换算法的研究。另外还有一些技术，它们采用分布式的系统结构，把视频服务器尽量推到离用户较近的网络末梢以节约主干网络带宽。
1 服务器流调度技术
在统计分析过程中，人们发现节目点播情况服从Zipf(齐夫)法则，即对N部电影按访问概率从大到小进行排序为M1，M2，……Mn，第i部电影的访问概率pi=P{X=Mi}(i=1，2，……n)满足：
针对VOD的统计表明，大量用户的点播往往集中在少数热门节目上。当大量用户点播相同节目时，可以把用户的请求合并，通过组播通道传输媒体流，节约视频服务器磁盘I/O带宽和网络带宽。这种思想正是流媒体调度技术的基础[3]。
流媒体调度算法分为两类：(1)静态调度算法是指服务器主动把节目在一系列组播通道中播放媒体流。(2)动态调度算法是指用户点播驱动，服务器根据调度算法来为用户调度媒体流。
1.1 静态调度算法
流媒体静态调度算法主要包括阶段广播算法、周期性广播算法、金字塔(Pyramid)、Permutation Pyramid算法、摩天大楼(skyscraper)算法、磁盘尽力保留广播(GDB)算法等。
在阶段广播和周期性广播算法中，服务器在规定间隔后开始发送节目媒体流，它的延时取决于请求在间隔内的到达点。其问题在于虽然提高了服务器带宽利用率，但是它强迫用户端增加延时。
分段广播系统包括金字塔和摩天大楼算法等。这些系统不是在一个流中广播一个节目，而是把节目分段，在每个流中广播一个段。分段广播与阶段广播相比可以降低客户端延时，但客户端更复杂，不能作到零延时，只适用于高点播率的节目。
GDB（Greedy Disk-conserving Broadcast）是基于周期性的广播技术。这个策略中，节目对象分为段，每个段周期性在特定通道中广播。这些段经过精心选择，保证客户在观看节目时能加入合适的通道以取得每个段的数据，并确保节目能连续回放。周期性广播策略中关键的问题是设计一个合适的节目分段公式，以保证客户端节目的连续回放。
1.2 动态调度算法
流媒体动态调度算法包括FCFS算法、Batching算法、Adaptive Piggybacking算法、Stream Tapping[4]、补丁算法(Patching)、受控组播算法、Catching and Selective Catching、BandWidth Skimming、分片融合、层次型组播流聚合等。
(1)最简单的动态调度算法是FCFS算法，该算法按照用户请求“先来先服务”的原则，可以实现简单的TvoD系统，算法简单实用，可以支持VCR功能，但是资源消耗过大。
(2)在Batching 算法中，当几个用户在相近的时间内点播同一部节目时，服务器把他们的请求聚合在一起，绑定到一个组播流中。Batching 算法可以有效地利用系统资源。但是它增大了用户的启动延时，且该算法不能支持用户VCR功能。
(3)Adaptive Piggybacking算法中，节目的播放速度调节为原来的正负5%以使两个流能聚合成一个流。一旦两个流到达节目的同一个点，其中一个流即被释放，用户切换到现存的流中。缺点是两个流要经过长时间才能聚合，需要服务器有足够高的性能来改变节目播放速度。
(4)Stream Tapping算法中，利用客户缓冲区使客户加入服务器现存的流中，以便从多个流中取得数据。使用这种方法可以节约服务器带宽资源，降低客户延时，但是它要求客户有足够的接收带宽来同时接收多个流。与Batching相比它能获得较小的启动延迟。
(5)补丁算法的基础是Batching算法，它利用组播媒体流服务多个用户。用户可以利用本地缓冲同时从多个组播流中取得数据，用户没有启动延时。同时系统可以尽可能地合并用户请求来提高系统的效率。补丁算法明显优于其他动态调度算法，但是它受客户缓冲区的限制，补丁流的大小不能大于缓冲区长度。
(6)受控组播技术与补丁算法相似，允许两个点播同一节目的客户共享同一通道。与补丁算法的区别是：它不会为了提高共享而延迟先到客户的点播请求，而是通过允许后来的客户共享先到的客户的组播流，从而满足客户要求。然而受控组播技术并不是在任何可能的时候都允许客户加入正在进行的组播会话。使用一个域值来控制何时开辟一个新的组播会话。优化的域值可以最小化服务器的通道数目。受控组播在低点播率时提供较好的性能。然而，对热播节目性能下降，特别在文件巨大时，它的服务器带宽与节目长度和点播率的平方根成正比。
(7)分片融合是一个在补丁基础上支持VCR功能的算法。当用户执行交互功能时，它将从组播通道中退出，系统重新为它分配单播通道来进行服务，直到它能和现有的组播流聚合。
(8)Catching技术比较适合热播节目。该技术的高效性体现在它智能地结合了服务器和客户端的发送功能。在此技术中，一个视频节目在一些通道中循环组播。想要观看该节目的用户可以立即加入合适的组播通道，无须等待下一个广播周期。同时客户向服务器发送请求来取得错过节目的开始部分的数据（前缀）。前缀通过单播通道发送，客户可以马上观看。另一方面，从组播通道取得的数据暂时缓存在客户端，直到回放结束。这样通过客户端和服务器的模式Catching策略可以最小化启动延迟。为了能适合各种节目的点播分布，一种叫做Selective Catching的策略，结合了Catching和受控组播技术(Controlled Multicast)。受控组播技术采用客户端的模式，比较适合冷门节目。Selective Catching能适用于各种系统负载和各种流行度的节目。Catching是一种基于参数的策略，它的通道需求为点播率和文件大小的对数。这种策略的主要缺点是需要预先知道点播率参数，在点播率变化时需要调整参数。
2 代理缓存技术
代理技术的研究主要包括：缓存策略、代理缓存结合服务器调度技术、分段分布式代理的研究。
2.1 缓存策略
视频代理的缓存策略多种多样，主要包括全部缓存、部分缓存(Prefix，Suffix or Selective)、滑动窗口技术和分层编码视频的缓存策略等。
(1)全部缓存策略：缓存整个流行度高的节目数据，这种方法效率不高，特别是在代理缓存空间有限时尤为突出，缓存需要频繁的换入换出，缓存一个巨大的节目代价是昂贵的，所以很难提高点播的命中率，同时也很难降低代理-服务器之间的网络流量。正在进行的流不能被删除，这会使缓存替换算法替换掉本来不应该被替换的节目，进而偏离优化点。
(2)部分缓存策略：可以降低用户点播的启动延时，也可以利用缓存的前缀来做一些提前平滑及丢包重传的处理。但是由于大量后缀数据要从服务器取得，所以不能从本质上降低代理到中心服务器之间的网络流量和服务器的负担。该方法的侧重点是解决服务延时，服务器负载巨大和网络带宽的问题，缓存空间需要非常巨大。
(3)滑动窗口策略：没有用户点播请求时，代理服务器不缓存任何数据。当第一个用户请求到达时，代理服务器向中心服务器请求数据，代理服务器预测将来可能还有请求，缓存w分钟的数据，数据的生命期就是窗口的大小。所以从第一个请求开始，w分钟内到达的请求都可以用这个窗口的数据来服务，这个窗口之外的请求将要再次启动网络传输。该策略在节目点播人数较多时可以节约一定的网络传输，缺点是数据的生命期固定，它没有充分利用代理的缓存资源，不能从根本上节约网络带宽，并且很难实现VCR等功能，同样存在热播问题。
(4)分层编码视频的缓存策略：针对分层编码的流媒体来决定应该缓存哪一个节目的哪一层，才能最小化传输代价。主要的挑战是根据客户所拥有的不同可用带宽进行质量调整后，用不同质量的缓存流来响应。该策略中的预取算法和适合分层编码的细粒度的缓存替换算法，能根据节目的流行度对缓存状态进行调整。模拟结果显示缓存的流质量与流行度成正比，质量之间的变化与流行度成反比。它的目的主要是来调节网络而不是为了最小化网络带宽利用[6]。
2.2 代理缓存结合服务器调度
典型的缓存前缀有许多优点，例如：掩盖代理与服务器之间的延时抖动、启动延时、减少网络传输，可以实现在线平滑。中心服务器使用组播和广播技术可以降低服务器负载和网络传输。
一种闭环(点播驱动)控制的方法被称为Multicast with Caching(MCache)[7]。MCache的中心思想是利用Batching、Patching和代理前缀缓存技术。Batching补丁的请求是本策略的独特特点。使用区域的缓存服务器来缓存前缀以降低启动延迟。MCache的特点在于组播开始后的请求仍旧可以聚合起来，通过组播补丁来达到没有启动延迟。MCache高效地使用代理组播补丁来提供TRUE VOD服务，它的性能可达到一些著名的开环控制方法，在高点播率时，使用较少的带宽。另外使用组播和缓存技术，克服了一些策略要预先知道客户点播率和需要客户端存储空间的缺点。
另一种结合服务器调度和代理前缀缓存或部分缓存的策略是在给定缓存容量时，最小化主干网络上的传输量。它不但存在一个选择前缀集合的优化算法，而且可以动态缓存补丁数据和RC（从头至尾发送节目的通道）的数据。
结合代理前缀缓存和视频后缀数据服务器周期广播的调度策略。该策略的思想是不同代理可以根据用户和节目流行情况采用合适的前缀传输策略。另一种方案是结合部分缓存和Batch Pathing 的策略。它不仅缓存前缀，而且可以有选择地缓存Pathing数据，甚至RC的数据，进而可以进一步降低服务器的负载和代理到中心服务器的网络传输。
2.3 分段分布式代理
以往对代理技术的研究主要是结合代理缓存和服务器调度。最近分段分布式代理技术是一个研究方向。
MiddleMan[8]是由局域网联结起来的协同工作的代理服务器集合。MiddleMan由两部分组成：代理服务器和协调器(Coordinators)。典型的配置包括一台协调器和多台代理服务器，它们通过LAN互联。协调器跟踪代理服务器上保存的内容，做出缓存替换决定。MiddleMan存储系统中把视频文件平均分成大小相等的文件块，把它们在所有代理之间分布，使视频看起来是由一系列顺序的文件块组成。这样可以极大地降低系统结构的复杂度，也能提供很好的负载均衡，同样也简化了节目替换算法，并且也使设计更科学的节目替换算法成为可能。MiddleMan需要考虑的一个技术难题是从不同的代理服务器上取文件块并把它们合并成一个连续的流。
MiddleMan提供和评估了基于分断存储大媒体流的代理管理方法。代理服务器接收到的媒体流块数据按可变大小的段组织，缓存接纳控制和替换策略为每个段添加不同的缓存值。这些缓存策略对开始段给予特别的考虑。把缓存空间分为两部分，一部分用来缓存前缀，一部分用来缓存后缀。前缀只能替换原来缓存的前缀，后缀只能替换原来的后缀。结果表明：(1)基于分段缓存不但可以提高命中率(降低全部的网络传输)，而且可以降低请求的开始延时；(2)基于分段缓存在缓存空间有限以及热播节目变化频繁、媒体文件巨大以及用户经常只观看节目开始部分时具有特别的优势。
一些视频服务器提供了VCR功能，但它需要经历很大的延时和大量的处理。另外用户也不知道视频的大致内容以及感兴趣部分的精确位置，同时也浪费了网络资源。结合交互式视频发送和缓存系统并使用视频分析和抽象技术设计了一个视频代理系统，可给用户提供一个良好的观看环境。视频分析包括Shot Boundary Detection和Key-frame Selection。当用户点播一个节目时，系统首先显示一系列关键画面，用户可以选择从关键画面开始播放。视频数据分段存储在多个代理上来进行负载均衡，同时也允许实现细粒度的替换策略。前缀缓存是只缓存每个视频段的前缀，所以预取也能减低延时。
3 节目替换算法
传统的替换算法主要应用于大小相等的对象、传统的内存以及Web应用的替换算法不适用于流媒体领域。最经典的替换算法包括LRU(Latest Recently Used)、LFU（Latest Frequently Used）等。LRU算法不能区别经常和不经常使用的对象。LFU缓存策略缓存当前具有高使用频率的节目或片段[9]。
目前提出的RBC算法在缓存接纳和替换时考虑了文件大小和所需的发送带宽因素。Pooled RBC策略进一步提高了RBC算法的性能。它提供一个带宽POOL，当一个点播请求到达时，从带宽POOL中为该用户分配流。发送完毕要收回已经分配的带宽归还给带宽POOL。如果点播请求不能分配足够的带宽，则POOL RBC把请求转交给原始服务器，而不是简单地替换实体来释放带宽。实验结果表明，在大多数情况下这个策略明显比RBC容易实现。而Hybrid LFU/Interval Caching策略的性能比Pooled RBC和LFU都优越。LFU/IC是一个结合LFU和Interval Caching的技术。Interval Caching算法主要研究在内存中缓存部分节目流。在这个策略中，如果点播同一个节目的请求相距足够近，发送给第一个用户的流将保存在内存中直到给第二个用户发送完毕。更一般的数据缓存在内存中直到满足几个相近的点播请求。通过结合磁盘缓存和内存缓存两种技术，明显提高了LFU的性能。
LRU算法不能区别经常和不经常使用的对象。LRU-K算法仔细检查使用对象最近K次被引用的信息。本文使用考虑最近2次引用信息的算法叫作LRU-2，更一般的是LRU-K算法。典型的LRU算法相当于这里的LRU-1算法。LRU-K包含内在的“老化”含义，考虑了对象的最近K次引用，然而LRU算法不能很好地处理不断演化的引用模式。LRU-K算法有以下显著的特点：①能很好地区分不同级别引用对象的集合。②可以通过自调节来适应不同的引用模式。③产生很少的管理负担。通过2Q算法可对LRU-K进行改进。它引进两个管理队列来简化LRU-K的管理负担。在大多数情况下，2Q算法性能比LRU高5%～10%，性能与LRU-K相近。2Q的复杂度为O(1)，LRU-K的复杂度为O(logn)。但是LRU-K（包括2Q）没有统一考虑近期性和频率。所以在K较大时LRU-K算法很难适应不断演化的工作模式。
LRU和LFU分别是考虑近期性和使用频率的两个极端。LRFU(Least Recently/Frequently Used)策略统一考虑频率和近期性，在两者之间进行折中。LRFU算法中为每个块分配一个CRF(Combined Recency and Frequency)，这个CRF值代表该对象将来被点播的可能。过去的每次引用对该值的贡献由一个权值函数F(x)来衡量。F(x)是一个单调降函数，x代表当前时刻。
Segmented LRU是基于频率对基本LRU进行扩展，它是为页缓存设计的，页的大小均相等。Segmented LRU基于这样的观察：在很短一段时间内使用两次的对象比只使用一次的对象流行度高。在Segmented LRU中缓存空间分为两部分：可能段和保护段。新对象（使用一次）首先进入可能段，使用两次以上的段进入保护段。当整个缓存空间满时，可能段中的最近最少使用的对象将被替换掉。保护段空间有限，当它满时，从中溢出的段重新缓存在可能段中。因为保护段中的对象在被驱逐时要走相对长的路，所以流行的和使用次数多的对象能在缓存中保存较长的时间。
The Size-Adjusted LRU把缓存的所有对象按cost-to-size（1/(Si*ΔTit）)排序，这里Si是对象I的大小，ΔTit是自从上次使用以来经历的时间。它只是贪婪地把cost-to-size最小的对象删除。实际应用中对象按Si*ΔTit重新排序，具有较大索引的对象在替换时逐一被清除掉。
更进一步，为了避免计算所有对象的cost-to-size值，一个近似的算法叫做Pyramidal Selection Scheme(PSS)，对象按log2(size)分为有限的组，同一个组中对象大小相似。每个组中使用LRU机制。
4 小 结
本文归纳总结了当前流媒体传输领域的一些流行的技术，并对它们进行分类。目前看来，各种技术都只能解决部分问题，并且都有自己的缺陷。因此目前还没有完善的流媒体传输解决方案。我们期待将来随着计算机和通信技术及流媒体领域各种相关技术（视频压缩、传输协议等）的发展，会出现更好的流媒体解决方案，使流媒体得到更广泛的应用。
参考文献
1 吴国勇，丘学刚，万燕仔.网络视频：流媒体技术与应用.北京：北京邮电大学出版社，2001
2 段渭军，张永斌，王福豹.分布式视频点播系统的设计与实现.世界电信网络，2002；10(4)：36
3 钟玉琢，向哲，沈洪.流媒体和视频服务器.北京：清华大学出版社，2003
4 Carter S W，Long D D E.Improving bandwidth efficiency of video-on-demand servers.Computer Networks and ISDN Systems，1999；31(1)：99
5 Rejaie R，Handley M，Yu H et al.Proxy caching mechanism for multimedia playback streams in the internet.In：Proceedings of the 4th International Web Caching Workshop，San Diego，CA.，March 1999
6 Rejaie R，Handley M，Yu H et al.Proxy caching mechanism for multimedia playback streams in the internet.In：Proceedings of the 4th International Web Caching Workshop，San Diego，CA.，March 1999
7 Ramesh S，Rhee I，Guo K.Multicast with Cache (Mcache)：An Adaptive Zero Delay Video-on-Demand Service.In：Proc.of IEEE Infocorn′01，Apr 2001
8 Acharya S，Smith B.MiddleMan:A Video Caching Proxy Server.In：proc.IEEE NOSSDAV，2000
9 Tewari R，Vin H，Dan A et al.Resource-Based Caching for Web Servers.In：Proceedings of SPIE/ACM Conference on Multimedia Computing，January 1998