基于流行度分类的流媒体分段策略

邓宇珊，陈 戈，张 军，梁 洁

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

1 引言

随着互联网的日益普及和飞速发展，人们对多媒体内容的需求也有了很大改变。互联网已经由原来的以提供文本和图像为主的多媒体服务演变成为提供更丰富信息，如音视频文件为主的服务，各种各样的流媒体服务也得到了广泛应用，如网络视频、视频点播、远程教学、视频会议、IPTV等。但是，随着流媒体应用的普及，相应的问题也逐步凸显出来。流媒体对象巨大的数据量对网络带宽的要求比文本内容要大很多，同时也增加了流媒体传输时延，影响用户体验质量。通过在网络边缘靠近用户的地方设置代理缓存服务器，缓存流行度最高的部分视频或者视频片段是目前主流的解决方法。

流媒体对象巨大的数据量使得缓存整个媒体文件会快速占用大量的缓存空间，前缀缓存策略[1,2]可以在一定程度上解决这个问题，在大部分用户都访问流媒体对象的开始一段时间，前缀缓存策略能够得到比较好的效果，同时它也可以有效减少用户访问的启动时延，但前缀缓存不适用于互交式的流媒体。基于分段的缓存策略相比前缀缓存策略具有更强的适应性，均匀分段[3,4]和指数分段[5]是最经典的分段策略。均匀分段是把流媒体文件分成相同大小的段，分段的粒度越细，分段缓存的性能越好；指数分段是把流媒体文件按播放时间分成长度呈指数增长的段，该策略是基于用户对流媒体文件前面部分比后面部分更感兴趣的假设，其优势是能够通过替换大的低流行度段快速获得大量缓存空间。

均匀分段和指数分段都没有结合流媒体文件自身的流行度信息，分段的基本粒度固定，没有从减少分段数量、节省分段管理成本的角度对流媒体进行分段和性能评估。本文在现有分段缓存研究的基础上，针对流媒体文件的缓存替换规律，提出了一种基于流行度分类的流媒体分段策略，该算法统计出流媒体对象的流行度，根据流行度对流媒体文件进行分类，把流媒体文件分成高流行度文件和低流行度文件，对不同类型的流媒体文件采取不同的分段策略，充分利用了流媒体文件的流行度信息，仿真实验结果表明，与其他分段策略相比，本文提出的策略在相同命中率的情况下可以减少分段数量。

2 流媒体外部和内部流行度特点分析

流行度是指流媒体对象被访问的次数，用来描述流媒体流行程度[6]。缓存算法是通过缓存流行度最高的视频内容，在有限资源情况下获得最好的用户体验。而在实际中，用户对流媒体对象及其内部片段的访问总存在一定的倾向性，不同流媒体对象和不同片段的流行度不同。因而用户行为必然会在一定程度上影响缓存算法的性能，在对不同内容进行分段时就需要结合以上因素合理选择分段策略。

对流媒体对象流行度的研究需要从两个方面展开：不同流媒体对象之间的外部流行度和同一流媒体对象不同区段之间的内部流行度。本文以广东电信IPTV系统2013年1月到2013年5月的点播访问日志为依据，分别研究了流媒体外部流行度与内部流行度的特点。

2.1 流媒体外部流行度的分布

本文首先对流媒体的外部流行度分布进行了研究。通常认为流媒体的外部流行度符合Zipf分布或广延指数分布[7]，文中分别用两种分布模型对实际的流媒体流行度进行拟合，其结果如图1所示，横坐标为影片按流行度从大到小排序的序号，纵坐标为影片被访问的互补累计概率，广延指数分布比Zipf分布有更好的拟合效果。从图1可以看出，大多数用户请求集中在少数的热门影片上，对于大部分热度极低且不会被存储的影片来说，对其进行一视同仁的分段会增加不必要的分段管理成本。因此，为了降低全部影片总分段数，需要对不同流行度的影片使用不同的分段策略。

图1 广延指数分布与Zipf分布的曲线拟合情况

2.2 流媒体外部流行度对缓存替换的影响

通过对相邻两天最热门视频的相同视频比例进行分析，发现最热门的7 000部视频（满足60%的用户请求）的相邻两天相同视频比例在87%左右，而最热门的27 000部视频的相邻两天相同视频比例在92%左右。这种现象说明，大部分用户对某些视频表现出很强的倾向性[8]，导致比较热门和比较冷门的视频在流行度上有着一定的稳定性和持续性，这些视频短期内不会从缓存中替换出来或者替换进缓存，而处于被缓存边界的视频将会比较频繁地进行替换。图2对这种现象进行了描述，分析图2可知，缓存替换集中在某一小段流行度范围的视频上，而大部分流行度偏高和流行度偏低的视频替换很少，并且随着到峰值处流行度距离的加大，视频替换次数越来越少。另外，存储占所有视频容量的比例越大，峰值处流行度越小。

图2 视频外部热度与其缓存替换量的关系

2.3 流媒体内部流行度

同一流媒体内部各区段之间也存在访问频度的差异，用户往往会先看视频的开始部分，进而决定是否继续看下去，所以从整个视频来看，其内部流行度分布是不均匀的，会随着播放时间的推移而逐渐递减[8]。流行度扰动现象[9,10]是指流媒体外部流行度高的对象，其10 min之后的内部流行度不一定高。本文通过对实际用户数据进行分析发现，这种现象只出现在两个流媒体对象外部流行度差异不大的情况下，而当两个流媒体对象外部流行度差异较大时，则不会发生流行度扰动现象。影片外部流行度的高低对其内部流行度的影响如图3所示（24 h的数据整理所得，其中排名第五的影片最后曲线急速下落是由于到达了影片末尾），当流媒体外部流行度差异超过一定程度时，外部流行度高的流媒体对象，其内部流行度也会高于其他外部流行度低的对象。也就是说，在大趋势下外部流行度高的对象，其整个播放时间上的内容都会比较热。

图3 不同外部流行度的流媒体对象的内部流行度比较

根据以上分析，发现流媒体内部和外部流行度具有如下几个特点。

·用户访问的倾向性很强，大多数请求都集中在少数热门的视频上。

·被频繁替换的视频集中在一小段流行度范围内，大部分视频几乎不会被替换。

·视频内部流行度会随着播放时间而逐渐降低，并且外部流行度高的视频，其内部流行度也会比较高。

根据流媒体流行度内部与外部流行度的关系，可以使用外部流行度决定其整个内容上的分段大小。从对缓存替换规律的分析可知，在固定缓存空间大小的情况下，流媒体对象的缓存替换频繁程度与流行度有关，如果在缓存替换比较少的流行度区间，增大视频的分段粒度，会大大减少总的分段数，而在缓存替换比较频繁的流行度区间内，合理减小缓存替换的粒度，可以更加充分合理地利用缓存空间，使用有限的缓存空间资源存储更多流行度更高的内容。

3 基于流媒体外部流行度分类的分段策略

由于流媒体内部流行度分布通常是不均匀的，因此对流媒体进行分段管理是提高缓存利用率和命中率的一种常用技术。本文首先从理论上分析了分段对命中率的影响，然后基于流媒体外部和内部流行度的特点，提出一种基于流媒体外部流行度分类的分段新策略。

3.1 分段对命中率的影响

设Φ={φi|i∈[1,N]}为所有视频的集合，其中，N为总的视频数，φi为第i个视频。当存储空间为L时，按热度优先原则存于缓存中的视频集合为Φ′，不被存储的视频集合为=Φ-Φ′,则Φ′中的视频φi满足：

其中，h（φj）为φj的被访问概率，l(φj)为φj的存储空间大小，此时命中率为：

将任意两个视频φj∈Φ′和φk∈Φ′分为m段，假设φjm和φkm分别表示φj和φk的第m个分段，如果h(φjm)

由于视频内部流行度不均匀，经常会出现h(φjm)

3.2 分段策略

视频的流行度具有一定的持续性，并且缓存替换集中在某一段流行度范围的少数视频上，大多数视频很少被替换，而传统的分段策略并没有针对缓存替换规律进行分段。本文依据视频流行度，以替换频繁的地方为界对视频进行分类，把视频分成高流行度视频和低流行度视频，替换频繁的部分视频分段粒度减小，而其他视频分段粒度加大，能保证在总分段数目一定的情况下提高命中率。

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

（1）流行度分类

把视频按照外部流行度分为高流行度视频或者低流行度视频，设分界处的流行度为P，视频m的流行度为Pm，若Pm>P，则标记该视频为高流行度视频；若Pm

（2）分段长度计算

对不同流行度高低类型的视频做不同的分段处理，使得对于高流行度视频来说，外部流行度越高，视频分段粒度越大；而对于低流行度视频来说，外部流行度越小，分段粒度越大。视频的起始段定义为视频的第一个分段，则高流行度视频m的起始段长度Lm正比于其外部流行度Pm，低流行度视频n的起始段长度Ln反比于其外部流行度Pn。则视频起始分段长度为：

其中，ah，al为常数参数。

（3）ah，al的计算

流行度为P的分界处的视频起始段长度为L，假设高流行度分类视频临界处的视频起始段长度Lsh和低流行度分类视频临界处的视频起始段长度Lsl相等，且等于L，由式（4）和式（5）可得：

由式（6）和式（7）可得：

ah，al计算出来后，可以根据式（4）和式（5）计算所有视频的起始段长度。

（4）视频内部的分段方法

[11]经过研究指出，指数分段不适合对所有的视频进行管理，并且在系统中媒体数量非常多的情况下，缓存准入和缓存替换的粒度太大，会造成系统抖动，影响系统稳定性。而使用线性分段则减缓了分段长度的增长速度，也能够比较迅速地将热门视频进行缓存。本文采用参考文献[11]提出的线性分段方法对每个视频进行分段，设视频内部段编号为i（起始段编号为1），其起始段长度为Li，则该视频第i段的长度为Li×i。

（5）视频的重新分段

视频的流行度会随时间变化，时间越长流行度变化越大，因此需要根据视频流行度的持续性特征设定一个重新分片周期T，全部视频在一个周期后根据其当前流行度进行重新分片，重新分片的时间点可以设定在用户点播低谷时段，避免增加网络负担。

本文的分段策略在已有分段策略的基础上增加了对视频流行度的分类，给定L和P可以计算出所有视频的起始流行度，在视频内部仍然更加重视时间靠前的部分内容，对每个视频都使用分段长度增长较缓的线性分段策略，在充分利用了外部流行度特征的同时，也保证了对视频开头部分内容的重视。

4 实验结果分析

本文的实验数据来自广东电信IPTV系统2013年12月的电影类视频真实点播访问日志，包括3 226个视频，共有100 000条记录。分段策略的性能评价指标采用了总分段数和字节命中率，字节命中率是缓存中命中字节数与总请求字节数的比值，可以有效地反映使用分段策略所节省的网络流量，而分段数的减少可以节省系统管理成本。本文仿真实验比较了在相同命中率的情况下，本文分段策略与均匀分段策略的总分段数大小以及在相同总分段数的情况下，它们的字节命中率大小。

4.1 最佳P值的选取

相同总分段数的情况下，分界流行度对流行度分类分段方法的命中率影响如图4所示。以L=10 min、存储占所有视频比例为10%的情况为例，可以看出分界流行度P在[15 000,25 000]范围内，流行度分类分段策略效果比较好，并且对流行度分类分段策略的命中率影响不大，流行度分类分段策略与均匀分段策略命中率的差也比较稳定。表1为存储占所有视频比例为10%的情况下，不同的L值对最佳分界流行度P的影响。可以看出在不同的L下，最佳分界流行度P值有一些波动，但是波动范围不大，且在20 000左右，因此可以设定P=20 000，使用相同方法可以为其他不同存储占所有视频比例的情况设定一个理想的分界流行度值。

图4 分界流行度对两种分段方法命中率的比较

表1 存储占所有视频比例为10%时，不同L下的最佳分界流行度P

4.2 字节命中率

图5为L=10 min时，不同分段方法的字节命中率，实验结果是在最佳分界流行度下的记录。从图5可以看出，本文的分段策略相比均匀分段策略具有更好的字节命中率，这是由于流行度分类分段策略充分考虑了实际缓存替换规律和流媒体对象的流行度特征，才使得字节命中率获得较好效果，从而在一定程度上节省了缓存空间资源和网络流量，但是由于只有少部分视频缓存替换频繁，本算法对于总的命中率提高不显著。

图5 相同总分段数情况下不同分段方法字节命中率比较

4.3 总分段数

图6 为L=15 min，分界流行度P为最佳分界流行度，字节命中率相同的情况下，对两种分段方法的总分段数的比较。从图6中可以看出，在各个缓存空间大小下，本文分段策略都能获得比均匀分段策略更少的总分段数，从而可以节省系统的分段管理资源。

图6 相同命中率情况下不同分段方法的总分段数比较

5 结束语

本文在主流分段策略基础上，对流媒体的流行度特征进行分析，提出了基于流行度分类的流媒体分段策略。利用缓存替换的规律，对流媒体对象进行分类，针对不同流行度采用不同的分段策略，由于增强了对流媒体对象自身流行度的适应性，达到了减少分段数目的目的，获得了较好的字节命中率。实验结果表明，该分段策略相比于传统的均匀分段策略，在相同命中率的情况下，可以减少总的分段数，节省系统分段管理成本，同时在相同总分段数的情况下，字节命中率有所提高，可以节省网络带宽和缓存空间资源。

参考文献

1 Sen S,Rexford J,Towsley D.Proxy prefix caching for multimedia streams.Proceedings of IEEE INFOCOM,New York,NY,USA,1999:1310～1319

2 Qu W Y,Li K Q,Kitsuregawa M,et al.An optimal solution for caching multimedia objects in transcoding proxies.Computer Communications,2007,30(8):1802～1810

3 Rejaie R,Handley M,Yu H B,et al.Proxy caching mechanism for multimedia playback streams in the Internet.Proceedings of the 4th International WWW Caching Workshop,San Diego,USA,1999:1～11

4 ChenS 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,New York,NY,USA,2003:22～31

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

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

7 周铀,吴刚,李俊.视频点播中用户交互式请求数分布的建模与分析.小型微型计算机系统,2010,31(7):1426～1432 Zhou Y,Wu G,Li J.Modeling and analyzing the distribution of number of user interactive in video-on-demand.Journal of Chinese Computer Systems,2010,31(7):1426～1432

8 林光国,戴琼海,丁嵘.基于用户行为统计的流媒体集群负载均衡算法.清华大学学报(自然科学版),2005,45(4):525～528 Lin G G,Dai Q H,Ding R.User behavior-based load balancing algorithm for distributed streaming systems.Journal of Tsinghua University(Science and Technology),2005,45(4):525～528

9 余江,杨宗凯,杜旭等.基于两点流行度的流媒体缓存算法.华中科技大学学报(自然科学版),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 Edition),2006,34(10):15～17

10 杨菲菲,陈志云,曾秋梅.一种基于流行度和分段适应性的流媒体缓存算法.计算机应用与软件,2010,27(7):227～229 Yang F F,Chen Z Y,Zeng Q M.A popularity-based and segment adaptability-based caching algorithm for streaming media.Computer Applications and Software,2010,27(7):227～229

11 夏琰.基于实际用户行为分析的缓存研究（硕士学位论文）.中国科学技术大学,2011 Xia D.Research of caching replacement based on real user behavior(master dissertation).University of Science and Technology of China,2011