移动网络中基于两级缓存的流媒体调度算法.doc

第11期廖建新等：移动网络中基于两级缓存的流媒体调度算法57移动网络中基于两级缓存的流媒体调度算法廖建新, 杨波, 朱晓民, 王纯(北京邮电大学 网络与交换技术国家重点实验室，北京 100876)摘 要：提出一种适用于移动通信网的两级缓存流媒体系统结构2CMSA(two-level cache mobile streaming architecture)，它突破了移动流媒体系统中终端缓存空间小、无线接入网带宽窄的局限；针对2CMSA结构设计了基于两级缓存的移动流媒体调度算法2CMSS(two-level cache based mobile streaming scheduling algorithm)，建立数学模型分析了其性能；仿真实验证明，与原有的移动流媒体系统相比，使用2CMSS调度算法能够有效地节省网络传输开销，降低用户启动时延。关键词：移动通信网；流媒体系统；两级缓存；调度算法中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2007)11-0051-08Two-level cache based streaming mediascheduling algorithm for mobile networkLIAO Jian-xin, YANG Bo, ZHU Xiao-min, WANG Chun(State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications, Beijing 100876, China)Abstract: A novel caching system architecture for mobile streaming was proposed, which was named 2CMSA (two-level cache mobile streaming architecture). In this system, limitations for mobile streaming system such as small memory size in mobile terminal and low bandwidth in wireless access network were avoided. According to the 2CMSA, a scheduling algorithm of 2CMSS (two-level cache based mobile streaming scheduling) was designed; mathematical models were also achieved to analyze the performance of this scheduling algorithm. Simulation experiment proves that, comparing to the original mobile streaming system, by using the new two-level cache architecture and cache based scheduling algorithm, the network transmission cost and the client startup delay of the mobile streaming services can be decreased effectively.Key words: mobile communication network; streaming media system; two-level cache; scheduling algorithm1 引言收稿日期：2006-07-15；修回日期：2007-09-28基金项目：国家杰出青年科学基金资助项目（60525110）；新世纪优秀人才支持计划基金资助项目（NCET-04-0111）；高等学校博士学科点专项科研基金资助项目（20030013006）；电子信息产业发展基金重点项目（下一代网络核心业务平台）Foundation Items: The National Science Fund for Distinguished Young Scholars (60525110); The Program for New Century Excellent Talents in University (NCET-04-0111); The Specialized Research Fund for the Doctoral Porgram of Higher Education (20030013006); Development Fund Key Project for Electronic and Information Industry (Core Service Platform for Next Generation Network)流媒体技术是宽带IP网络和多媒体技术共同发展的产物，它以流的形式进行数字内容传输，支持边下载边观看的播放方式，减少了节目启动的等待时间，且不需要大量的缓存空间，减少了对接收端的资源要求，使得在移动终端上使用流媒体业务成为可能。随着移动通信技术和移动数据业务的发展，移动流媒体业务已引起了广泛关注，对移动流媒体技术进行研究具有重要的应用价值1。根据流媒体的特性，Lim等提出了一种最小效用值优先缓存算法SCU2，以特定时间段内缓存提供的数据量与已缓存内容占用空间大小的比值构成效用函数，以等长片段为单位进行缓存替换。Chen提出了一种滞后分段和主动预取的替换算法3，有效提高了缓存命中率并避免了节目播放期间产生的停顿。Wang提出了一种优化的缓存分配算法4，并利用代理缓存提出了几种调度算法：SBatch、UPatch和MPatch。上述算法在Internet流媒体环境中表现出较好的性能，但并不适用于移动网络中的流媒体应用，因为这些算法或者需要较大的终端缓存能力，或者要求传输网络支持多播，或者要求链路有足够的带宽，或者存在较长的操作时延。为此，作者根据GPRS网络的特点提出了一种移动流媒体缓存体系结构5，并对该体系结构中的关键问题(如：缓存算法、性能与可靠性、终端适配等)进行了深入研究。本文在此基础上，提出了一种移动网络的两级缓存流媒体系统结构2CMSA(two-level cache mobile streaming architecture)，针对该结构设计了一种基于两级缓存的移动流媒体调度算法2CMSS(two-level cache based mobile streaming scheduling algorithm)，并分析了其性能。本文组织结构如下：第2节设计了一种WCDMA移动网络中的两级缓存流媒体系统结构2CMSA；第3节根据该结构的特点，提出了一种基于两级缓存的移动流媒体调度算法2CMSS，并建立了数学模型对其性能进行分析；第4节使用仿真实验验证了两级缓存结构和调度算法的有效性；第5节是本文的结束语。2 移动网络的两级缓存流媒体系统结构目前，中国移动已经在多个省展开了基于GPRS网络的流媒体实验业务，如手机电视、视频点播等。受网络体系结构和技术的制约，这些业务存在一些性能瓶颈，如：操作时延较大、无线接入网带宽消耗大、流媒体业务对其他业务造成较大冲击等。文献5提出的流媒体缓存结构在一定程度上缩短了用户操作的响应时延，降低了流媒体内容服务器的负载。但鉴于GPRS网络的技术现状，在其上开展流媒体业务受到网络带宽和传输成本等多方面的限制。3G移动网络为用户提供了更高的接入带宽，是规模化开展流媒体业务的基础；权威机构预测流媒体业务将是3G网络上的主导业务，是流媒体业务发展的动力。本文以3GPP的WCDMA R5网络6,7为例讨论。为了将基于Internet的流媒体调度和缓存算法应用到移动网络上，需要解决如下问题：1)流媒体传输网络对IP多播或者应用层多播的支持：诸如Batching9、Patching10、Merging11等算法，都是利用多播技术来节省网络带宽和提高服务器处理能力；2)调度算法需要终端具有同时接收和缓存2个视频流的能力，比如：在Patching算法中，用户需要同时接收常规流(regular stream)和补丁流(patch stream)，在播放补丁流期间，终端对常规流进行缓存；而无线接口的带宽较小，终端的缓存和处理能力有限，无法同时接收并缓存两路数据。针对WCDMA网络结构6，提出一种适用于移动通信网络的两级缓存流媒体系统结构2CMSA，如图1所示。中心缓存代理(CCP, central cache proxy)位于移动网与公用数据网(PDN, public data network)的边缘，与(GGSN, gateway GPRS support node)和PDN通过Gi接口交互；作为第一级缓存，CCP缓存来自外部数据网络上的流媒体内容服务器(SCS, streaming content server)上的热门节目片断，以降低流媒体内容服务器的处理开销，减少GGSN与PDN之间的带宽消耗，并有效缩短数据传输时延；此外，CCP还具备流调度功能，用于实施有效的流调度算法。用户边界缓存代理(UECP, user edge cache proxy)位于无线网络子系统中，通过Iub接口与Node B和RNC(radio network controller)交互；作为第二级缓存，UECP上的缓存空间按功能分为2个区域：前缀缓存区(prefix buffer)用于缓存热门节目的前缀部分，以保证大多数用户点播请求能得到迅速响应；交换缓存区(swap buffer)是为每个在线用户分配的动态缓存空间，作为调度算法的接收端，代替终端MS(mobile station)接收和缓存一个节目的多个并行流以配合调度算法的实施。同时，UECP将接收到的视频流以稳定的单速率向MS提供，并与终端进行QoS交互，保证终端流畅地播放视频节目。IP直连链路是一个基于IP协议的数据通信网络，连接系统中所有的UECP和CCP，支持资源保留协议RSVP(resource reservation protocol)，可支持IP多播；通过IP直连链路，视频流直接在IP网络上传送，避免了GTP(GPRS tunneling protocol)封装和拆封带来的时延及处理开销，旁路了GSN和RNC实体，减轻了报文转发引起的处理负担和时延，避免了视频点播业务对核心网承载的其他业务的冲击。为了描述方便，根据时间顺序将编号为i的节目分成前缀(prefix)、中缀(infix)、后缀(suffix)3个片段，其播放时间长度分别为vi、ui和si，(vi 0, ui 0, si 0)；设节目i的总长度为Li，则有Li=vi+ui+si。UECP的功能包括：1)保存节目的前缀(播放时间为vi)，以便缩短移动终端的请求响应时延；2)实现调度算法的客户端功能，充当接收端的缓存区，以便调度算法的有效实施；3)与CCP结合进行流分发，实现了应用层多播功能；4)与终端进行QoS协商，向终端提供有质量保证的单速率播放流。CCP的功能包括：1)缓存节目的中缀(播放时间为ui)；2)实现调度算法的服务器端功能；3)对于未命中的请求，从流服务器获得节目内容，转发给UECP。按照缓存分配和替换算法灵活调整各片断的长度大小，例如：vi 0且ui = 0表示在UECP上缓存了节目i的前缀，但在CCP上没有缓存相应中缀的情况。图1 WCDMA网络中的两级缓存流媒体系统结构部署本文提出的两级缓存流媒体系统，包括如下几个方面的投资：硬件包括CCP代理服务器、UECP代理服务器以及UECP与CCP之间的IP直连链路；软件主要是UECP和CCP上的流媒体调度和缓存系统的开发。在一个移动网络中配置一台高性能的CCP服务器，每个无线网络子系统中设置一台UECP服务器，IP直连链路可以使用有安全及QoS保障的城域网，在硬件和通信技术高速发展的今天，该部分硬件投资很小。软件方面，由于采用了移动网络的通用接口和协议，软件开发和维护成本也很低。因此，2CMSA结构具有现实可行性。基于WCDMA的两级缓存流媒体系统结构2CMSA具有如下特点：1)使用应用层多播规避了核心网络不支持IP多播对流媒体调度算法的限制；2)通过UECP上的动态用户缓存区，避免了无线网络数据带宽和终端缓存不足对调度算法的影响；3)两级缓存体系的引入，不需对WCDMA网络的设备、接口以及流媒体传输和控制协议做扩充，透明于核心网络；4)实施成本低，具有较强的可行性。3 基于两级缓存的移动流媒体调度算法设流媒体VOD(video on demand)系统中共有N个视频节目，其中第i (00，ui=0，Li=vi+si)，使用3.2节代理辅助的批量调度算法(PAB, proxy aided batching schedule)；3)对于在UECP上缓存了节目前缀，且在CCP中缓存了中缀的情况(即vi0，ui0，Li=vi+ ui+si)，采用3.3节代理辅助的补丁调度算法(PAP, proxy aided patching schedule)。设3种情况发生的概率分别为PDLA、PPAB和PPAP，则有PDLA+PPAB+PPAP=1，用户对节目i的点播在单位时间内消耗的网络代价T2CMSS(i)由式(2)给出(2)3.1 直连链路辅助的调度算法(DLA, direct link aided schedule)对于UECP未缓存节目前缀，CCP也没有缓存中缀的情况(即vi=ui=0，Li= si)，采用直连链路辅助的调度算法DLA。DLA的基本思想与ORG系统相同，为每个用户请求分配一个单独的视频流；所不同的是：在UECP和CCP之间使用IP直连链路旁路媒体流，借助直连链路的高性能和低代价来降低传输成本。使用DLA调度算法时，单位时间内对节目i的点播所需的网络开销TDLA(i)表示为(3)3.2 代理辅助的批量调度算法(PAB, proxy aided batching schedule)对于在UECP上缓存了节目前缀，但CCP中没有缓存中缀的情况(即vi0，ui=0，Li=visi)，采用代理辅助的批量调度算法PAB。PAB的基本思想是：借助UECP上缓存的节目前缀的播放时间间隔，将在指定时间区间到达的对同一个节目的一批请求集中起来，使用单个后缀流为其提供服务。如图2所示，PAB的流程如下：假设对节目i的第一个用户请求t0在0时刻到达，UECP向其播放节目的前缀部分vi，并通知CCP准备播放节目i的剩余部分。由于CCP上没有存储节目i的内容，它将向位于PDN网络上的视频内容服务器SCS请求节目的后缀部分si，以保证终端播放节目的连续性。同时CCP尽量推迟节目后缀部分的发送时间，以便将后续到达的请求合并起来，用同一个后缀流批量提供服务。在时间(0, vi区间的某个时刻t1，终端对视频节目i的点播请求到达UECP，UECP经Node B向终端发送前缀部分vi(即图2中的S11流)；CCP根据前缀长度和CCP与存放节目内容的SCS服务器之间的往返时延(RTT，round trip time)决定从服务器上获取后缀的时刻，以保证vi时刻开始向UECP发送后缀部分si(即图2中的S12流)。图2 两级缓存移动流媒体系统的PAB调度方案第一个请求在0时刻到达，则在前缀播放时间vi内，到达的用户请求数量为1vi.i。因此，使用PAB算法单位时间内节目i消耗的网络开销TPAB(i)表示为(4)在PAB算法中，随着在线用户数量的增多，Swap Buffer占用大量的缓存空间，为了节省UECP的缓存空间，在保证节目连续播放的前提下，应尽量少缓存节目的前缀。因此节目i的前缀长度vi，取决于UECP从视频内容服务器SCS上获取视频流的最大往返时延RTT。如图2所示，在MS播放流S11期间，从CCP上到达的视频流S12开始部分（即位于时间区间(vi, vi+ t1)的视频段B）将缓存在UECP为该终端开辟的Swap Buffer区中。在(0, vi)时间段内，用户以强度为i的Poisson序列到达，根据Poisson分布的性质，各用户的到达时间相互独立，且服从U(0, t1)分布。所以，在每个调度周期，节目i所需的UECP Swap Buffer空间大小的数学期望MPAB(i)由式(5)给出(5)与传统的批量调度算法Batching相比较，代理辅助的批量调度算法PAB具有明显的优势：1)降低了流媒体服务的用户启动时延，时延仅体现在终端到UECP的无线链路上；2)为终端提供了一种QoS保障机制：UECP和终端之间可以使用RTCP协议交互，反馈无线链路和终端的状态信息，动态调整流的质量和传输速率，提高了用户的流媒体服务质量。3.3 代理辅助的补丁调度算法(PAP,proxy aided patching schedule)对于在UECP上缓存了节目前缀，且在CCP中缓存了中缀的情况(即vi0，ui0，Li=vi+ui+si)，采用代理辅助的补丁调度算法PAP。PAP的基本思想是：CCP上缓存的节目的中缀ui，使得在特定时间区间到达的对同一个节目请求使用相同的常规流，并为每个请求发送单独的补丁流，在有效节省网络传输负荷的前提下，实现终端的连续播放。如图3所示，PAP的流程如下：假设对节目i的第一个用户请求t0在0时刻到达，UECP向其播放节目的前缀部分vi，并通知CCP准备发布节目i的剩余部分。由于CCP上缓存了节目的中缀部分ui，从vi时刻开始，CCP将通过IP直连链路向UECP发送节目的中缀ui，并准备向视频内容服务SCS请求节目的后缀部分si，CCP根据前缀和中缀长度以及CCP与存放节目内容的内容服务器之间的往返时延RTT决定从服务器上获取后缀的时刻，以保证终端视频流的连续性。同时CCP尽量推迟节目后缀流的发送时间，将后续到达的请求合并起来，用同一个常规流提供服务。在时间(0, vi)区间到达的请求，采用PAB算法调度；位于 (vi, vi+ui)时间区间内到达的用户请求，通过UECP和CCP配合的PAP算法获得视频服务，超出vi+ui时刻到达的用户请求将触发新的PAP调度周期。对于在时间区间(vi, vi+ui)的某个时刻t2到达的请求，UECP经Node B向终端发送前缀部分vi(即图3中的S21流)，同时UECP从另一个通道接收正在发布的常规流(即图3中的S22流)并将其缓存在为该终端分配的缓存区Swap Buffer中，从vi+t2时刻开始，CCP向UECP发送S21流和S22流的补丁部分(即图3中的S23流)，从而保证终端的连续播放。图3 两级缓存移动流媒体系统的PAP调度方案使用PAP算法，单位时间内用户对节目i的点播所需网络开销TPAP(i)如(6)使TPAP(i)值最小的ui值称为补丁门限，记做gi，在特定网络环境下的一个特定节目，gi取决于节目长度Li、前缀长度vi和用户请求强度i三因素，其中Li、i不受调度算法控制，因此gi是前缀vi的函数，显然uigi 。如图3所示，在S21和S23播放期间从CCP上到达的视频流S22开始部分（即位于时间区间(t2, 2t2的视频段B）将缓存在UECP为该终端开辟的Swap Buffer区中。PAP算法所需的Swap Buffer空间大小的数学期望MPAP(i)由式(7)表示(7)从上面的分析可以看出，PAP是一种使用UECP的缓存空间换取网络带宽节省的方法，和传统的补丁算法Patching相比，它具有如下特点： 1)借助UECP上的前缀缓存功能，加长了补丁周期，进一步节省了流媒体传输开销； 2)借助UECP上的Swap Buffer缓存功能，通过应用层多播的方式将媒体流复制到各终端，规避了3GPP R6之前版本中WCDMA核心网不支持IP多播的局限。3.4 2CMSA中缓存替换算法的选择在2CMSA结构中，UECP和CCP是2个独立的缓存代理服务器，根据各自的功能特点，我们为其选择相应的缓存替换算法。UECP的主要作用是减少用户端播放时延，降低用户因等待超时而退出的概率，它缓存节目的前缀部分，前缀长度vi的大小取决于从UECP到存储节目i的视频内容服务器之间的往返时延RTT；因此，在UECP上采用LFU(least frequently used)算法，以提高缓存替换算法的性能。CCP的主要作用是与UECP结合实现视频调度算法，减少GGSN到SCS之间的网络流量，降低视频内容服务器SCS的负载，CCP要尽可能多地缓存热门节目的片断；因此，在CCP上采用最小效用值优先缓存算法(SCU，smallest caching utility)2，缓存效用值综合考虑了节目的流行度和已缓存部分的长度2个因素。4 性能评价4.1 模拟环境与评价指标为了验证本文提出的移动网络的两级缓存流媒体系统结构2CMSA的有效性和基于两级缓存的移动流媒体调度算法2CMSS的性能，设计了一个事件驱动型流媒体仿真平台，通过一组事件模拟客户端的点播行为，触发缓存系统中各代理服务器的缓存替换和流调度动作，记录各链路和服务器上的流量数据。仿真中使用如图1所示的网络拓扑结构。将100个CBR(constant bit rate)的视频节目存储在视频内容服务器SCS上，节目编码速率为128kbit/s的统计特征服从Zipf(100, )分布8；节目的时间长度服从U(90, 120)min的均匀分布；节目前缀长度统一取5min(即)。客户点播请求的到达率服从次/s的Poisson分布。定义CGTP=CIP、CPDN=CIP，称为链路代价比。由于在WCDMA的核心网上数据是通过GTP协议传输的，GSN设备要对报文进行封装和解封装，其传输开销必然高于IP直连链路，即1。设在UECP上缓存了前缀的节目数量占节目总数的比例用表示，称为前缀缓存比。在不影响本文结论的前提下，做如下假定以简化仿真环境： 1)不考虑IP直连链路上的报文传输时延和带宽限制； 2)不考虑缓存代理UECP和CCP的磁盘及网络带宽限制，假定网络和磁盘输入输出带宽足够大； 3)用户对节目的点播，都从节目的头部开始。为了评价第3节提出的调度算法2CMSS的性能，将其与不使用缓存的WCDMA常规视频流媒体系统ORG作对比。选取如下指标：启动时延率(client startup delay rate) ，记作RCSD；网络代价节省率(network cost saving rate)，记作RNCS。启动时延率RCSD是未能直接从缓存代理上获取节目前缀用户请求次数与用户总的请求次数的比率。网络代价节省率RNCS是指与不使用缓存的ORG方式相比较，2CMSS节省的网络代价的比率，定义如式(8)所示。无论采用何种调度算法，对相同的访问模式，从UECP到移动终端MS的无线链路上的带宽和代价消耗总是相同的，因此，在计算时不考虑无线接入网部分的传输代价CRNS。(8)4.2 仿真结果选取不同的参数进行仿真实验，每组实验进行3次仿真，每次仿真进行6个仿真小时，对仿真结果进行统计分析。图4描述了不同参数下网络代价节省率RNCS与前缀缓存比例的关系。图4(a)对比了用户到达图4 网络代价节省率RNCS与前缀缓存比的关系率对RNCS的影响程度：随着用户到达率的增加，网络代价的节省率呈上升趋势。当0.5时增加的趋势变缓，这是由于随着用户到达率的增加，PAP算法中补丁部分开销的上升幅度增大导致的。图4(b)给出了用户点播分布的倾斜度的变化对RNCS的影响，随着的增大，用户对节目的点播趋于分散，因此命中缓存的概率变小，固定大小的缓存对网路代价的贡献减少。图4(c)给出了不同的链路代价比下对网络代价节省率的影响：使用本文提出的调度机制，即使在核心网的链路代价CGTP小于两级缓存结构中IP直连链路CIP的情况下，仍然能够大量节省网络传输代价，比如：在前缀缓存比 = 20%时，节省率达到35%以上；随着链路代价比的增加，对网络代价的节省程度更明显：前缀缓存率 = 20%、 = 2.0时，网络代价节省率RNCS达到65%。图5给出了用户启动时延率RCSD与前缀缓存比例的关系，从图5(a)可以看出，用户到达率对用户启动时延率的影响并不明显，因此，基于两级缓存的移动流媒体调度算法具有较广的适用范围，在不同强度的用户请求模式，都能较好地降低用户启动时延，当前缀缓存比例为30%时，65%以上的用户请求无需等待可立即从UECP获得服务。图5(b)给出了用户点播分布的倾斜度的变化对RCSD的影响，随着的增大，用户对节目的点播趋于分散，缓存命中的概率变小，用户时延率相应增大。文献8使用统计数据说明VOD的用户点播行为具有明显的集中特性(服从=0.271的Zipf分布，大量用户请求集中在少数节目上)，因此，本文的两级缓存结构能较好地适应流媒体业务的特征。图5 用户启动时延率RCSD与前缀缓存比的关系综观上述的仿真实验和分析结果，本文提出的移动流媒体的两级代理结构2CMSA和相应的调度算法2CMSS对网络资源的节省、用户服务质量的提高等方面都具有明显优势。根据实际网络的代价状况、用户点播行为特征和节目属性，配置合适UECP和CCP缓存空间，能有效提升移动流媒体系统的性能。5 结束语本文提出的两级缓存的移动流媒体系统结构2CMSA具有如下特点： 1)采用标准接口和标准协议，无需对原有移动网络设备做修改扩充，具有良好的兼容性；2)通过两级代理间的IP直连链路旁路了流媒体业务流量，减小了视频业务对移动核心网络的冲击；3)软、硬件成本低，部署代价小； 4)使用缓存辅助的调度算法2CMSS有效降低了网络传输代价和用户启动时延。因此，两级缓存的流媒体结构对移动流媒体应用系统具有一定的实用价值。后续工作中，将进一步扩充和优化2CMSA结构，主要包括：多UECP环境下IP直连链路上IP多播技术的支持及性能分析、UECP上用户Swap Buffer的分配和共享机制、两级缓存替换算法等问题。本文的贡献在于：1) 提出了一种适用于移动网络中流媒体业务的两级缓存代理结构2CMSA，解决了移动网络和终端对现有流媒体调度算法的限制，消除了流媒体业务对核心网的冲击；2) 针对该结构设计了一种优化的流媒体调度算法2CMSS，有效地降低了流媒体传输代价和用户启动时延。参考文献：1ELSEN I, HARTUNG F, HORN U, et al. Streaming technology in 3G mobile communication systemsJ. IEEE Computer, 2001,34(9): 46-52.2LIM E, PARK S, HONG H, et al. A proxy caching scheme for continuous media streams on the InternetA.15th International Conference on Information NetworkingC. 2001. 720-725.3CHE N S, WANG H, ZHANG X,et al. Segment-based proxy caching for Internet streaming media deliveryJ. IEEE Multimedia, 2005,12(3): 59-67.4WANG B, SEN S, ADLER M, et al. Optimal proxy cache allocation for efficient streaming media distributionJ. IEEE Tran