基于用户行为的流媒体分段缓存算法

李晓楠,朱永宽,张来胜

(1.中原工学院,郑州450007;2.河南职业技术学院;3.郑州市劳动和社会保障数据管理中心,郑州450006)

基于用户行为的流媒体分段缓存算法

李晓楠1,朱永宽2,张来胜3

(1.中原工学院,郑州450007;2.河南职业技术学院;3.郑州市劳动和社会保障数据管理中心,郑州450006)

对网络中流媒体对象的用户访问行为进行了建模分析,根据相对流行度对缓存中的对象进行排序,同时结合指数分段算法,提出了基于相对流行度的流媒体分段缓存算法(RP-S),并使用真实日志记录进行仿真.仿真实验结果表明,与传统流媒体缓存算法相比,该算法具有较高的字节命中率,同时在一定程度上减少了网络延迟.

用户行为;分段缓存;流媒体缓存

随着Internet技术的发展和普遍使用,流媒体技术在互联网上得到了广泛的应用.流媒体对象由于其本身的大容量和传输的持久性,在很大程度上增加了主干网络的负担,在代理服务器上采用缓存分段、替换算法是提升系统性能的关键.

缓存技术最早应用于操作系统,用来提高访问命中率和减少访问延迟,后来被引入到Web环境,通过把用户最近经常访问的文件从源服务器取回到本地代理服务器,从而达到减少延迟的目的.流媒体对象与Web对象相比有着自己的特点,如流媒体文件规模巨大,通常在几百 MB到几 GB之间;交换性强,90%的用户点播会被用户过早地终止等.流媒体对象自身的特点使得传统缓存算法和Web缓存算法不能很好地应用于流媒体缓存.

本文对流媒体用户的访问模式进行了研究,通过对真实网络环境下用户访问行为的建模分析,提出了基于相对流行度的流媒体分段缓存算法RP-S.仿真实验表明,该算法在字节命中率和网络延迟方面有较好的表现.

1 现有算法分析

在当前的流媒体传输系统中,常用的替换算法有FIFO、LRU、LFU、SIZE等[1].其中,FIFO 算法采用先进先出替换策略,易于实现,但效率低;LRU和LFU算法基于用户访问的时间和空间局部性,分别以访问近期性和访问频率作为替换依据,但LFU存在缓存污染问题,LRU存在长环模式问题,导致请求命中率下降和响应延迟增加;SIZE算法则以对象的规模作为主要的替换依据,但该依据不能很好地反映真实的网络环境.总体来说,上述算法简单、容易实现,但存在命中率低、浪费系统空间的问题.

由于流媒体自身的特点,传统的缓存算法和Web缓存算法已经不能很好地适应Internet上的视频点播服务,因此关于流媒体的缓存出现了很多改进的算法.

由于Web访问的时间局部性,文献[2]提出了基于时间间隔的流媒体缓存算法.该算法将数据分片在节点的缓存时间进行等间隔划分,以此构造线性马尔科夫链,然后利用转移概率矩阵预测分片的缓存价值;文献[3]提出了将流媒体对象的头部预先在代理服务器上缓存,以提高用户访问的点击命中率;文献[4]提出一种新的代理缓存分段算法——A dap tive&Lazy算法,该算法的思想是对媒体文件的分段操作尽量晚,然后根据用户访问的平均间隔对媒体对象进行分段.在基于P2P的流媒体网络中,A dap tive&Lazy算法得到了广泛应用 .

2 基于用户行为的流媒体分段缓存算法

2.1 用户行为建模

流媒体技术使视频数据在网络中以无需下载等待的方式进行播放,这种播放方式和“实时播放”的流媒体服务相比具有很多优点,如启动延时短、对系统缓存容量需求低等.但同时流媒体对象也具有自己的特点:①流媒体对象的规模远大于Web对象;②流媒体对象多为静态对象,通常具有一次写多次读的特性;③流媒体对象的前缀具有很高的访问概率,用户往往通过对流媒体最初部分的浏览来决定是否全部观看.

用户访问行为在一定程度上影响着流媒体服务器缓存算法的性能.基于不同的用户访问模式,各缓存算法的性能会表现出差异,因此应该基于最真实的用户访问行为来设计缓存算法.本文以某大学VOD系统(服务器IP为202.196.64.151)3月1日至3月10日和4月10日至4月20日的访问日志为依据,对用户的访问行为进行分析.

定义1 相对流行度(RPi):对服务器中的流媒体对象的流行度进行归一化处理,得到各流媒体对象的相对流行度.表示如下:

其中:Pi为对象i的流行度;C由对流行度的归一化处理所得,C= Pi/∑Pi.

根据流媒体对象被访问的次数与播放时间的关系(如图1所示)可看出:VCR操作下的用户点播满足“二八定律”;Internet环境中用户请求具有高度的时间和空间局部性;用户对流媒体的兴趣往往取决于最开始的部分.

2.2 算法设计

由对用户行为的建模分析可知,流媒体对象的缓存价值受访问次数、平均访问长度以及未来该对象被访问的概率等因素影响.

本算法根据相对流行度的概念预测每个文件的访问概率,同时结合不同用户的网络情况和不同的媒体文件使用分段策略[6],在相对流行度的基础上引入动态分段(RP-S算法),对每个流媒体对象按指数增加方式进行分段.若某个流媒体对象(用户从未访问过)第1次被请求访问,系统将为该对象生成一个日志文件,用来记录该对象某一固定时间内被访问的次数,以及每次用户访问的持续时间.

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

算法中用到的参数如下:

M:缓存大小;

Di:数据分段;

Li:对象 i的日志文件;

Ni:对象 i的访问次数;

Ti:对象i被访问的持续时间;

Pi:流媒体对象的流行度;

RPi:流媒体对象的相对流行度.

当流媒体对象段Di从服务器到达客户端进行缓存时,执行如下算法:

(1)如果 Di是第1次被访问,则转向(2),否则转向(3);

(2)为 Di创建日志文件Li,并记录访问次数和时间等信息;

(3)计算 RPi并记录在Li中;

(4)如果 Di的剩余部分已全部分片,则转向(5),否则转向(6);

(5)对Di进行指数分段;

(6)如果缓存未满,将Di放入缓存,否则转向(7);

(7)如果缓存满,则根据 RPi执行替换,依次选择RPi最小的分段进行替换;

(8)将Di的分段放入缓存.

为了减少系统的启动延时,还为每个流媒体对象保留一小段前缀分段.这样能够保证当用户首次访问该对象的时候,系统能够立即为其服务,从而减少启动延时.

2.3 性能分析

仿真实验以指数分段缓存算法和流行度缓存算法作为对比参照.在指数分段算法中,将缓存总量的10%留作存放媒体对象的前缀,缓存片段递增指数为2,前缀长度400 kB,即第 i个片段的长度 P(i)=2i-1×c,其中c为前缀长度400 kB.实验日志采用真实日志(某大学VOD系统3月1日至4月30日的访问日志).

由于代理缓存中字节命中率大说明更多的用户请求数据由代理缓存来提供,字节命中率可以有效反映代理缓存减少的骨干网络流量,因此选取字节命中率作为评价指标.

定义2 字节命中率(B HR):代理缓存中命中的字节数与请求的字节数的比.表示如下:

其中:Ri表示代理缓存中命中的字节数;∑Si表示请求的总字节数.

仿真实验结果如图2所示.与指数分段算法和基于流行度的缓存算法相比,RP-S算法在字节命中率方面具有较好的表现.正是由于RP-S算法在替换时考虑了用户的访问频率和访问持续时间等因素,并对对象的流行度进行了归一化处理,而且针对流媒体前缀部分访问概率高的特征使用了指数分段的方法进行分段缓存,才使得缓存的总命中率最大,从而在一定程度上减少了网络中的访问延迟.

3 结 语

图2 字节命中率比较

本文在对网络中流媒体对象的用户访问模式进行建模分析的基础上,提出了基于用户行为的流媒体分段缓存算法,利用相对流行度对代理缓存中的流媒体对象进行排序替换.这样一方面通过对流行度的归一化处理,使得替换依据更加合理;另一方面也充分考虑了用户访问模式,更贴近Web真实环境.同时考虑到流媒体前缀部分具有较高的访问概率,算法使用指数分段的方法对流媒体对象进行分段缓存.仿真实验结果表明,RS-P算法相比较指数分段算法和基于流行度的缓存算法具有较高的字节命中率,并且在一定程度上减少了网络用户的等待时间.

[1] Sasabe M,Wakamiya N,M urata M,et al.Scalable and Con-tinuous Media Streaming on Peer to Peer Netwo rks[C]//.Proceedings of the 3rd International Conference on Peer-to-Peer Computing.Linköping,Sweden:IEEE Computer Society,2003:92-99.

[2] 杨静,李润知,王宗敏.基于时间间隔的 P2P流媒体直播系统缓存算法[J].计算机工程与设计,2010,3(1):91-93.

[3] HU X-B,Di Paolo E.An Efficient Genetic A lgorithm w ith Unifo rm Crossover for Air Traffic Control[J].Computers&Operations Research,2009,36(1):245-259.

[4] L IU Jiang-chuan,XU Jian-liang.Proxy Caching for Media Streaming over the Internet[J].IEEE Communications Magazine,2004,42(8):88-94.

[5] 孙名松,唐亮,周红敏.P2P点播系统的客户端磁盘缓存策略[J].计算机工程,2008,34(20):71-73.

[6] WU Kun-lung,Philip S Y,Wolf J L.Segment-based Proxy Caching of M ultimedia Stream s[C]//.Proceedingsof the 10th International Conference on Wo rld Wide Web.New York,USA:ACM Press,2001,7(54):1229-1241.

Segmentation Caching Algorithm of Stream ing Media Based on User Accessing

L IXiao-nan1,ZHU Yong-kuan2,ZHANG Lai-sheng3
(1.Zhongyuan University of Technology,Zhengzhou 450007;2.Henan Polytechnic;3.Labo r and Social Security Data M anagement Center of Zhengzhou,Zhengzhou 450046,China)

Analysis of Internet user accessing of streaming media are p resented in this paper at first.Stream ing media object show s larger size,static content and high accessing p robability on Prefix Segment and that is different from Web object.Relative Popularity(RP)is emp loyed in this paper based on the user accessing of stream ing media,and objects are o rdered by Relative Popularity in the cache.Integrating w ith the existing exponential segment,an algorithm based on Relative Popularity(RP)named RP-S is emp loyed.Experimental result show s that algorithm p resented in thispaper has a higher byte hit ratio compared w ith the departed caching algorithm of streaming media,and also reduces the occupied bandw idth and user latency.

user accessing;segmentation caching;stream ing media caching

TP312

A DO I:10.3969/j.issn.1671-6906.2010.04.016

1671-6906(2010)04-0062-03

2010-07-18

李晓楠(1983-),女,河南南阳人,硕士.