基于最小代价的流媒体缓存替换算法研究

张 艳，牛朵朵

（1.河南职业技术学院，郑州450046；2.重庆师范大学 涉外商贸学院，重庆401520）

基于最小代价的流媒体缓存替换算法研究

张 艳1，牛朵朵2

（1.河南职业技术学院，郑州450046；2.重庆师范大学 涉外商贸学院，重庆401520）

基于对现有流媒体缓存技术的分析，提出了一种基于最小代价的流媒体缓存替换算法.通过定期统计代理缓存中流媒体前缀片段的流行度，在缓存替换时综合考虑流媒体对象的访问热度和替换的字节代价，使得缓存替换的代价尽量小，进而获取较大的字节命中率.仿真实验结果表明，最小代价替换算法在提高字节命中率方面表现较好.

流行度；字节代价；流媒体；缓存替换算法

随着互联网业务的蓬勃发展及互联网用户数的持续增长，流媒体点播服务也快速膨胀.流媒体对象通常具有文件体积大、服务持续时间长的特点，该特点决定了流媒体服务对带宽有着较高的要求，从而影响了服务器的吞吐能力和流媒体服务的质量.因此，采用合理的流媒体缓存算法可以改善代理服务器流媒体服务的质量.

现有的流媒体缓存算法可分为：①基于分段的方法，如基于共享片段的方法［1］、基于指数分段的方法［2］；②基于用户访问行为的方法，如基于流媒体流行度进行预测缓存［3］；③基于时间间隔的方法，如运用等间隔划分的方法构造马尔夫链从而进行缓存［4］；④基于代价的方法，如基于最小代价缓存的方法［5］.相比于传统缓存，流媒体缓存有其自身特点.本文分析了Internet上流媒体缓存的特点以及流媒体用户的访问模式.通过定期统计代理缓存中流媒体前缀片段的流行度，进而在分段缓存的基础上，结合片段自身的流行度和字节访问热度对流媒体进行缓存.仿真实验验证了该算法可以获得较大的字节命中率.

1 现有流媒体缓存技术的特点

与传统缓存相比，现有流媒体缓存有其自身的特点：（1）流媒体对象的文件大小通常比传统Web对象的文件大几个数量级；

（2）流媒体对象多为静态的，很少改变，对缓存一致性要求不高；

（3）流媒体用户通常只根据文件最初部分来决定是否全部观看；

（4）流媒体对象在文件大小、播放持续时间和网络带宽需求等方面具有完全不同于传统Web对象的特点：① 流媒体文件长度不均匀，从几兆、几十兆（如新闻）到几百兆（如电影、电视剧等）不等；② 用户对流媒体的访问具有比Zipf分布更强的偏向性，排名前100的文件的请求占了总访问请求数的85%以上；③请求流具有比www资源访问更强的时间定域性特征，对于前d个对象（d＜＝40）具有更强的访问热度.

流行度（popularity）是用于描述流媒体流行程度的一个概念，它反映了流媒体文件在某一时刻被客户请求的概率.用户访问流媒体对象的一般特点是：在开始的一小段时间内会有很大一部分用户停止访问；随着时间的延长，停止访问的用户会趋于稳定.流媒体流行度分布如图1所示.

2 自适应流媒体分段缓存算法

在t时刻，当有用户访问到达时，对于流媒体对象的请求，系统会检查该请求是否在缓存中（若在，则从缓存中读取前缀片段；若不在，且缓存中有足够的空间，则将该媒体对象的前缀部分放入缓存中，生成log文件，否则，当缓存满且用户请求的流媒体对象不在缓存中时，替换发生）.此时，缓存的状态用St表示，大小为M，当前用户请求为Rt，替换出的流媒体对象为Vt，并生成log文件.在log中记录在△t时间间隔内的片段i被访问的次数ni以及每次被访问的字节数st.在t＋1时刻，缓存的状态为：

图1 流媒体流行度分布

一个好的分段算法要能够准确地反映用户访问的媒体对象的特点.分段策略是判断一个缓存策略好坏的关键之一.对于第一次被请求的媒体对象，根据log文件中的访问次数统计其流行度，以此作为流媒体对象分段的依据.同时，对于不同的流媒体对象，用户的访问特点是不同的，所以采用单一的分段算法无法准确反映其特点.基于流媒体对象大小不等，热度分布不均衡，对流媒体对象的流行度做如下计算：

其中，R表示在△t时间内代理服务器中的所有请求.用该方法计算出的流行度是在△t时间内的一个近似估计.为统计该流媒体的热度，根据被访问的字节数统计片段i的字节流行热度ci：

其中，S表示该片段的长度.

将流行度和字节流行热度统一考虑，得出片段i的替换代价Ci：

为了更准确地反映用户的访问热度，本文将流媒体对象的片段分为前缀片段和基本片段：前缀片段采用统一长度，按照其替换代价Ci值的大小在缓存中按照由小到大的顺序进行排序；基本片段采用指数分段的方法.

（1）前缀片段替换代价统计算法

Input：用户请求序列Rt，t＝｛1，2，3，…｝；

Output：替换代价Ci；

Method：

①对于用户请求Rt，读取片段的log文件.若有log文件，转向（2），否则转向（3）；

②计算片段在t时刻的Pi和ci，记录在log中；

③若用户请求的文件为新媒体对象，对其进行分段，并生成log文件；

④ 对于缓存中的每个片段，计算其替换代价Ci.

（2）最小代价替换算法

Input：用户请求序列Rt，t＝｛1，2，3，…｝；

Output：替换代价序列；

Method：

①根据每个片段的替换代价，将其在缓存中按照由小到大的顺序进行排序；

② 当缓存满时，则取队列首文件进行替换.

3 实验与分析

采用仿真实验，在缓存算法模拟平台 MiddleS－im［6］中加入最小代价的分段替换算法，并将该算法与指数分段算法和流行度预测算法做比较.

实验日志为Campus以及由日志生成器 Medisyn生成的日志.它记录了从2010年8月到2011年3月的流媒体访问信息.

评价指标采用字节命中率，其表达式如下：BHR ＝s△t／S△t

其中，s△t和S△t分别表示在△t时间间隔内命中的字节数和总的请求字节数.

3种方法所得字节命中率分布图如图2所示.

由图2可以看出，由于指数分段算法比较单一，字节命中率稍低；流行度预测算法更贴合用户访问特点，其字节命中率要高于单一的指数分段算法；而最小代价算法由于综合考虑了分段算法和用户的访问行为，在字节命中率方面表现较好.

4 结 语

图2 字节命中率分布图

本文针对代理服务器流媒体缓存进行了研究.在分析流媒体缓存算法和流媒体对象特点的基础上，通过定期统计代理缓存中流媒体前缀片段的流行度，在缓存替换时尽可能地考虑媒体对象的访问热度和替换的字节代价，使得缓存替换的代价尽量小，进而获取较大的字节命中率，从而达到改善流媒体服务质量的目的.仿真实验结果表明，本算法在缓存字节命中率方面有较好的表现.

［1］ 石磊，程刚运.共享片段自动检查模型［J］.计算机应用，2009，29（5）：1197－2000.

［2］ Wu Kun－Lung，Philip S Y，Wolf J L.Segment－based Proxy Caching of Multimedia Streams［C］／／Proc.of the 10th International Conference on World Wide Web.New York，USA：ACM Press，2001.

［3］ 杨传栋，余镇危，王行刚.基于流行度预测的流媒体代理缓存替换算法［J］.计算机工程，2007，33（7）：99－100.

［4］ 杨静，李润知，王宗敏.基于时间问隔的P2P流媒体直播系统缓存算法［J］.计算机工程与设计，2010，31（1）：90－93.

［5］ 胡玉琦，郝留有，孙爽.基于最小价值的流媒体缓存替换算法［J］.计算机工程与设计，2011，32（1）：85－88.

［6］ Acharya S，Smith B C.MiddleMan：A Video Caching Proxy Server［EB／OL］.［2012－04－15］.http：／／www.nossdav.org／2000／papers／16.pdf.

Research of Caching Replacement Algorithm of Streaming Media Based on Minimize Cost

ZHANG Yan1，NIU Duo－duo2
（1.Henan Vocational Technical College，Zhengzhou 450046；2.Chongqing Normal University Foreign Trade and Business College，Chongqing 401520，China）

Based on the analysis of existing streaming media technology，user accessing is considered to make total cost minimize for cache，accessing popularity and cost of replacement are employed in this paper through timely statistics.Experimental result shows that this algorithm has a higher byte hit ratio.

popularity；byte cost；streaming media；caching replacement algorithm

TP393

A

10.3969／j.issn.1671－6906.2012.05.017

1671－6906（2012）05－0073－03

2012－04－18

张 艳（1982－），女，河南新乡人，硕士.