基于最佳分段点估计的流媒体非均匀分段方法

邓宇珊，庄一嵘，陈 戈，张 军

（1.华南理工大学电子与信息学院 广州 510640；2.中国电信股份有限公司广州研究院 广州 510630）

1 引言

互联网的飞速发展和普及使得网络服务由主要提供文本和图像的Web多媒体内容逐渐转变为提供音视频等含有更多丰富信息的多媒体内容，同时流媒体技术也随之流行起来并应用于各式各样的多媒体服务中，如视频点播、直播、视频会议、远程教学、网络视频等。但是流媒体对象的数据量比文本内容要大很多，需要大量的存储空间以及更高要求的网络带宽，由此产生的流媒体传输时延会严重影响用户体验质量。为了减少用户访问的响应时间，研究者提出采用代理缓存技术，将用户需要的内容放置在离用户最近的地方[1～4]。

由于流媒体对象数据量巨大，采用全文缓存的方法很难取得理想的缓存效果，而前缀缓存策略[5]虽然可以节省缓存空间，也可以有效缩短用户访问的启动时延，但随着用户访问时进行交互式操作的增多，前缀缓存策略的效果将会变差。为了提高缓存策略的适应性，研究者提出了均匀分段[6]和指数分段[7]等分段策略，其基本思想是将流媒体内容沿着播放时间分成若干个片段，并以此作为存储和置换的基本单元[8]，缓存粒度的减小给缓存算法带来了更大的灵活性，并且也在一定程度上提高了缓存效率。

基于分段的缓存策略虽然提高了缓存性能，但是精细的分段粒度也增加了系统需要管理的片段数量和缓存置换次数。传统的均匀分段和指数分段方法仅按照简单的函数关系来对流媒体进行分段，没有充分地考虑到流媒体自身的一些特性，例如外部流行度和内部流行度等，因此其分段效果在很多情况下并不理想。参考文献[9]的研究表明，如果能针对流媒体的一些特性对其分段策略进行优化设计，能有效地提高分段的性能。本文在现有分段缓存研究的基础上，根据命中率和存储的流媒体片段流行度之间的关系，提出了一种基于最佳分段点估计的流媒体非均匀分段方法，该方法首先统计出进行全文缓存时的缓存临界外部流行度以及每个流媒体对象的内部流行度，并对该临界外部流行度与最佳分段点流行度之商随存储占比的变化曲线进行拟合，然后对最佳分段点进行估计，并将流媒体对象以最佳分段点为分割点分成两个片段。仿真结果表明，与其他分段策略相比，本文提出的策略在相同命中率的前提下可以显著减少总分段数量，并且在总分段数相同的前提下可以获得更好的命中率。

2 流媒体流行度特点

缓存空间是有限的，如何利用有限的空间使缓存的流媒体片段价值最大是分段算法的中心思想，而流行度是衡量流媒体价值的重要指标。流行度被广泛用于描述流媒体的流行程度[10,11]，常常使用流媒体文件被访问的次数作为流行度的定义。根据流行度所描述范围的不同，进一步细分为外部流行度和内部流行度。外部流行度是指流媒体对象之间的流行程度，描述的是流媒体文件的整体流行度大小，而内部流行度是流媒体对象不同播放时间片段上的流行程度[12,13]。流媒体对象之间的外部流行度会有明显的差异，每个流媒体的内部流行度也会因用户的个人喜好产生不均匀的分布。本文以2013年1-5月的中国电信股份有限公司广东分公司（以下简称广东电信）IPTV系统的点播访问日志为依据，分别对以上两种流行度的特点进行了分析，并研究了各个存储占比情况下的最佳分段点。

2.1 流媒体流行度分布

流媒体的外部流行度常使用Zipf分布或广延指数分布进行刻画[14]，用户的访问具有很强的倾向性，少数的热门影片往往占有大量的用户请求，也就意味着大多数的低流行度影片是不会被缓存的，对于这部分影片一视同仁地细分段显然会大大增加无谓的分段管理成本。

研究者还发现，近一半的用户请求不会播放完整个影片，而是在影片结尾之前就提前终止请求，因此同一流媒体内部不同区段之间也存在着流行度的差异，用户常常会通过观看影片的初始部分，以确定是否有兴趣继续观看，于是造成影片的内部流行度会随着播放时间而逐渐递减[15]。以每分钟一个区段计算影片的内部流行度，400部影片内部流行度与播放时间的关系如图1所示，影片起始部分的流行度会有一个快速下降的过程，这是用户的浏览行为造成的，而后流行度以较平稳的趋势逐渐减小。由图1可以看出，内部流行度是非均匀的，也就意味着外部流行度高的流媒体对象也很可能会有内部流行度非常低的部分，而且每个影片的内部流行度的变化也有所差别，传统的分段算法，例如均匀分段，往往不依据或者只单纯依据外部流行度的高低对影片进行分段而忽略了每个影片的内部流行度变化，具有一定的局限性，不能充分利用流媒体对象的流行度信息。

图1 流媒体对象的内部流行度与播放时间的关系

2.2 存储占比与最佳分段点

不同流媒体对象之间的外部流行度和流媒体对象的内部流行度都存在着访问频度的差异，由于存储空间有限，每段流媒体通常可以分为存储部分和非存储部分。假设可以对流媒体进行无限精细度的分段，本文进一步分析了在不同存储占比下，命中率最高时视频是否被存储的分界点流行度下限，如图2所示。由图2可知，最佳分段点上的流行度下限随着存储占比的加大而逐渐变小，这是由于存储占比越大，缓存空间也越大，可以缓存更多的影片内容，从而使得临界点处的影片分段流行度变得越小。

图2 最佳分断点处流行度与存储占比关系

根据以上对流媒体流行度的分析，发现由于用户请求有着比较强的倾向性，影片之间以及影片内部的流行度分布常常是不均匀的，内部流行度有着随播放时间增加逐渐降低的特点，而流行度又是影响命中率的直接因素，如果能够直接根据分段点下限值将影片分成两段，那么就能从根本上提高命中率，并且减少分段数量。

3 基于最佳分段点估计的流媒体分段策略

由于高流行度的视频往往占整个视频总数的少部分，且视频之间的流行度具有较大差异，视频内部的流行度也具有分布不均的特点，因此尽量缓存流行度高的片段是提高命中率和缓存利用率的有效方法。从理论上分析了缓存的流媒体片段流行度与命中率之间的关系以及将影片分成两段的分段点下限值的估计方法，并在此基础上提出了一种基于流媒体对象内部分段点估计的新分段策略。

3.1 缓存的片段流行度对命中率的影响

字节命中率（byte hit ratio,BHR）是指缓存中命中的数据量与用户请求的总数据量的比值[16,17]，表示如下：

其中，CBR代表缓存命中的数据量，UTD代表请求的总数据量。

设流媒体对象内部流行度的计算基本粒度为Rbbyte，即统计流媒体对象分割为Rbbyte片段时的每个片段的流行度。设Φ={φij|i=1,2,…,N,j=1,2,…,ri}为所有视频的基本粒度片段的集合，其中，N为缓存视频总数，φij为第i个视频的第j个片段，ri为第i个视频的片段总数。当存储空间有限时，只能存储部分视频片段，设Φ′为缓存中的视频片段集合，则：

其中，P(φij)为φij的流行度，则命中率为：

假设视频的内部流行度P(φij)在短暂的时间里是不变的，那 么Σφij∈ΦP(φij)也 是 不 变 的，则Σφij∈Φ′P(φij)越 大，BHR就越大，即缓存中的视频片段流行度越大，字节命中率越大。

3.2 最佳分段点的估计模型

本文按视频的流行度大小排序进行缓存，设所有视频片段的集合为Φ={φij|i=1,2,…,N,j=1,2,…,Mi}，其中N为视频总数，Mi为第i个视频的片段数，φij为第i个视频的第j个片段。缓存空间为C时，被缓存的视频片段集合依然设为Φ′，那么不被缓存的片段集合则为Φ′=Φ-Φ′。

若不对视频进行分段，即全文缓存的情况下，所有视频集合则为Φ={φi|i=1,2,…,N}，则缓存临界点处的视频外部流行度Pc满足：

其中，l(φi)为视频φi的长度。

对视频进行分段，并逐渐减小分段长度l，当l减小到1个单位数据量长度时，缓存临界点处的视频片段流行度就是最佳的分段点内部流行度下限值Po：

其中，l(φij)=1。

由以上分析可知，临界点处视频片段流行度随着分段长度l的减小逐渐向Po靠近，本文以广东电信IPTV系统2013年12月的实际用户点播访问日志对Po和Pc之间的关系进行建模分析。图3为存储占比变化时，视频进行全文缓存时的临界外部流行度与最佳分段点处的内部流行度的比值k的变化情况。由图3可知，k的值随着存储占比的增加呈现着逐渐增加的趋势，并且k与存储占比的关系可以使用多项式分布模型进行拟合。设存储占比表述为c，则：

即：

图3 k与存储占比关系

其中，a1，a2，…,an+1为n阶多项式模型参数，可获得最佳拟合曲线。

式（8）所表述的模型对不同存储占比下3阶和5阶多项式的拟合情况如图4所示，3阶多项式的拟合决定系数R2=0.963 76，5阶多项式的拟合决定系数R2=0.998 57，两者的决定系数都接近1，说明两种多项式的结合效果都比较好，从图4中也可以看出，该模型可以比较好地刻画k与存储占比之间的关系，并且多项式的阶数越高拟合效果越好，也就是说只要获得视频完整缓存情况下的临界流行度就可以估计出最佳的分断点处内部流行度阈值，而完整缓存的视频不需要进行分段，计算复杂度较小，只要获得所有视频的外部流行度信息就可以很容易得到。

3.3 分段策略

利用第3.2节中分析的估计内部分段流行度阈值方法，将每个视频分成高流行度段和低流行度段两个片段，可以大大减少视频总的分段数目，同时也可以保证比较好的命中率。

图4 Pc/Po随存储占比的变化曲线拟合情况

本文提出的分段策略分为5个步骤，具体过程如下。

（1）数据统计

设定一个合理的流行度统计周期T，并统计待估计周期T′的前一个周期1T′和前两个周期T′2内的所有视频的内部和外部流行度。

（2）建立内部流行度阈值估计模型

·根据式（5）和式（6），计算得到周期T′2的完整缓存情况下的临界流行度Pc2和周期1T′的最佳的视频内部分段流行度Po1。

·根据式（7），对不同存储占比下的完整缓存的临界流行度与最佳分段流行度曲线之商k=Pc2/Po1进行拟合，得到参数a1，a2，…，an的值。

（3）内部流行度阈值估计

·根据式（5）计算得到周期1T′在完整缓存情况下的临界流行度Pc1。

（4）分段

根据估计的分段流行度Po，对周期T′内的所有视频分成两个片段：内部流行度高于Po的内容部分为一个片段，低于Po的部分为另一个片段。

（5）重新分段

由于视频的流行度会随着时间的推移而不断变化，每个周期对已有旧视频进行检测，如果视频现有的分段点阈值与最佳分段点阈值相差达到一定程度则对该视频进行重新分段。

本文的分段策略依据流行度对命中率的重要性，并对最佳的内部分段点进行估计，充分利用了视频的外部和内部流行度信息，一方面直接针对命中率进行了提高，另一方面也大大减少了总的分段数量。

4 实验结果

本文的实验数据采用广东电信IPTV系统2013年12月流行度前400的电影类视频真实点播访问日志，共有8 000条记录。采用字节命中率和总分段数对分段策略进行性能评估，其中总分段数对系统管理的复杂度有直接影响，而字节命中率可以有效地比较各个分段策略所消耗的网络流量。仿真实验采用2013年12月1-15日的数据对2013年12月下半月的视频最佳分段点进行估计，并对比了采用3阶多项式估计最佳分段点时，本文的分段策略与均匀分段策略相同总分段数下的命中率大小以及相同命中率下的总分段数大小。

4.1 相同总分段数情况下的字节命中率比较

图5为相同总分段数情况下，不同分段策略的字节命中率比较结果。本文的分段策略命中率基本上达到了最佳分段点分段时的命中率，并与均匀分段策略相比明显呈现出更好的命中率，这是由于最佳分段点估计分段策略充分利用了实际内部和外部流行度特征，并对分段点处内部流行度进行了良好的估计，不仅提高了字节命中率，还可以减少用户访问时延并节省了网络流量以及缓存空间资源。

图5 不同分段策略的字节命中率比较

4.2 相同命中率情况下的总分段数比较

表2为相同命中率情况下，不同分段策略的总分段数大小比较结果。在各个存储占比大小下，本文的分段策略的总分段数都远远低于均匀分段策略，这是由于本文的分段策略根据最佳分段点估计值对视频进行分段，每个视频最多分为2段，在保证命中率的同时也可以获得分段数的减少，从而节省了系统的分段管理成本。

表2 最佳分段点估计分段策略的总分段数相对于均匀分段的减少量比较

5 结束语

本文对流媒体的内部和外部流行度进行了分析，并基于流行度对命中率的重要性，提出了基于最佳分段点估计的流媒体非均匀分段策略。通过对流行度建模分析，利用流媒体的外部流行度对最佳分段点的内部流行度进行估计，将视频最多分成两段，达到了减少总分段数目的目的，同时由于增强了流媒体对象对流行度的适应性，也获得了较好的命中率。实验结果表明，对比于传统的均匀分段策略，本文分段策略可以在相同总分段数的情况下提高字节命中率，节约缓存资源以及网络带宽，也可以在相同命中率情况下大大减少总分段数，降低系统分段管理成本。本文所提方法的局限性在于估计最佳分段点时假设内部和外部流行度在一定时间内保持不变，然而实际中无论外部还是内部流行度都是动态变化的，因此在估计最佳分段点时考虑流行度变化的特点将有望能进一步提高本文方法的性能。

1 张玉洁,何明,孟祥武.基于用户需求的内容分发点对点网络系统研究.软件学报，2014,25(1)：98～117 Zhang Y J,He M,Meng X W.Research on CDN-P2P system over user requirements.Journal of Software,2014,25(1)：98～117

2 Theodorou M,Paterakis M.Efficient cache management policiesfor streaming proxies supporting complete and partial video playback.Proceedings of the 5th International Conference on Next Generation Networks and Services(NGNS 2014),Casablanca,Morocco,2014:270～277

3 何智聪，谷光昭，王新等.基于可重构路由器上缓存的流媒体协作分发策略.通信学报，2012,33(6)：82～90 He Z C,Gu G Z,Wang X,et al.Novel cooperative caching strategies for video streaming distribution based on reconfiguration routers.Journal on Communications,2012,33(6):82～90

4 王蒙蒙.基于异构网络的交互式流媒体缓存替换算法.信息通信，2013(6):71～72 Wang M M.Cache replacement algorithm based on heterogeneous network of interactive streaming media file.Information and Communications,2013(6):71～72

5 Sen S,Rexford J,Towsley D.Proxy prefix caching for multimedia streams.Proceedings of IEEE Conference On Computer Communications,New York,USA,1999:1310～1319

6 Chen S Q,Shen B,Wee S,et al.Adaptive and lazy segmentation based proxy caching for streaming media delivery.Proceedings of the 13th International Workshop on Network and Operating Systems Support for Digital Audio and Video,Monterey,USA,2003:22～31

7 Wu K L,Yu P S,Wolf J L.Segment-based proxy caching of multimedia streams.Proceedings of the 10th International Conference on World Wide Web,Hong Kong,China,2001:36～44

8 余江，杨宗凯，杜旭等.基于两点流行度的流媒体缓存算法.华中科技大学学报（自然科学版），2006，34（10）:15～17 Yu J,Yang Z K,Du X,et al.Two-point popularity-based caching algorithm for streaming media.Journal of Huazhong University of Science and Technology(Nature Science),2006,34(10):15～17

9 邓宇珊，梁洁，张军等.基于流行度分类的流媒体分段策略.电信科学,2015,31(1)：152～157 Deng Y S,Liang J,Zhang J,et al.Segmentation strategy of streaming media based on popularity classifying.Telecommunications Science,2015,31(1):152～157

10 杨传栋，余镇危，王行刚等.基于流行度预测的流媒体代理缓存替换算法.计算机工程,2007,33(7):99～100,129 Yang C D,Yu Z W,Wang X G,et al.Proxy cache replacement algorithm based on popularity prediction of streaming media file.Computer Engineering,2007,33(7):99～100,129

11 张艳，牛朵朵.基于最小代价的流媒体缓存替换算法研究.中原工学院学报，2012，23(5)：73～75 Zhang Y,Niu D D.Research of caching replacement algorithm of streaming media based on minimize cost.Journal of Zhongyuan Institute of Technology,2012,23(5):73～75

12 Yu J,Chun T C,Yang Z K,et al.A proxy caching algorithm based on user access preference in streaming media.Microelectronics & Computer,2006,23(11):19～22,25

13 刘宜宁，赵正德，全卫新等.基于媒体流行度和前缀缓存的缓存替换算法.中国图像图形学报,2007,12(10):1753～1756 Liu Y N,Zhao Z D,Quan W X,et al.Proxy cache replacement algorithm based on popularity and prefix caching.Journal of Image and Graphics,2007,12(10):1753～1756

14 周轴.视频点播系统访问行为研究：测量、分析与建模(博士学位论文).合肥：中国科学技术大学，2009 Zhou Z.Research on the access behavior of video on demand system:measurement,analysis and modeling(doctor dissertation).Hefei:University of Science and Technology of China,2009

15 余江.流媒体代理缓存算法研究(博士学位论文).武汉：华中科技大学,2006 Yu J.Research on proxy caching algorithms for streaming media(doctor dissertation).Wuhan:Huazhong University of Science and Technology,2006

16 李晓楠，朱永宽，张来胜.基于用户行为的流媒体分段缓存算法.中原工学院学报，2010,21(4)：62～64,69 Li X N,Zhu Y K,Zhang L S.Segmentation caching algorithm of streaming media based on user accessing.Journal of Zhongyuan Institute of Technology,2010,21(4):62～64,69

17 刘磊,熊小鹏.最小驻留价值缓存替换算法.计算机应用,2013,33(4):1018～1022 Liu L,Xiong X P.Least cache value replacement algorithm.Journal of Computer Applications,2013,33(4):1018～1022