基于用戶行為的流媒體分段緩存算法

李曉楠,朱永寬,張來勝

(1.中原工學(xué)院,鄭州450007;2.河南職業(yè)技術(shù)學(xué)院;3.鄭州市勞動和社會保障數(shù)據(jù)管理中心,鄭州450006)

基于用戶行為的流媒體分段緩存算法

李曉楠1,朱永寬2,張來勝3

(1.中原工學(xué)院,鄭州450007;2.河南職業(yè)技術(shù)學(xué)院;3.鄭州市勞動和社會保障數(shù)據(jù)管理中心,鄭州450006)

對網(wǎng)絡(luò)中流媒體對象的用戶訪問行為進(jìn)行了建模分析,根據(jù)相對流行度對緩存中的對象進(jìn)行排序,同時結(jié)合指數(shù)分段算法,提出了基于相對流行度的流媒體分段緩存算法(RP-S),并使用真實(shí)日志記錄進(jìn)行仿真.仿真實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)流媒體緩存算法相比,該算法具有較高的字節(jié)命中率,同時在一定程度上減少了網(wǎng)絡(luò)延遲.

用戶行為;分段緩存;流媒體緩存

隨著Internet技術(shù)的發(fā)展和普遍使用,流媒體技術(shù)在互聯(lián)網(wǎng)上得到了廣泛的應(yīng)用.流媒體對象由于其本身的大容量和傳輸?shù)某志眯?在很大程度上增加了主干網(wǎng)絡(luò)的負(fù)擔(dān),在代理服務(wù)器上采用緩存分段、替換算法是提升系統(tǒng)性能的關(guān)鍵.

緩存技術(shù)最早應(yīng)用于操作系統(tǒng),用來提高訪問命中率和減少訪問延遲,后來被引入到Web環(huán)境,通過把用戶最近經(jīng)常訪問的文件從源服務(wù)器取回到本地代理服務(wù)器,從而達(dá)到減少延遲的目的.流媒體對象與Web對象相比有著自己的特點(diǎn),如流媒體文件規(guī)模巨大,通常在幾百 MB到幾 GB之間;交換性強(qiáng),90%的用戶點(diǎn)播會被用戶過早地終止等.流媒體對象自身的特點(diǎn)使得傳統(tǒng)緩存算法和Web緩存算法不能很好地應(yīng)用于流媒體緩存.

本文對流媒體用戶的訪問模式進(jìn)行了研究,通過對真實(shí)網(wǎng)絡(luò)環(huán)境下用戶訪問行為的建模分析,提出了基于相對流行度的流媒體分段緩存算法RP-S.仿真實(shí)驗(yàn)表明,該算法在字節(jié)命中率和網(wǎng)絡(luò)延遲方面有較好的表現(xiàn).

1 現(xiàn)有算法分析

在當(dāng)前的流媒體傳輸系統(tǒng)中,常用的替換算法有FIFO、LRU、LFU、SIZE等[1].其中,FIFO 算法采用先進(jìn)先出替換策略,易于實(shí)現(xiàn),但效率低;LRU和LFU算法基于用戶訪問的時間和空間局部性,分別以訪問近期性和訪問頻率作為替換依據(jù),但LFU存在緩存污染問題,LRU存在長環(huán)模式問題,導(dǎo)致請求命中率下降和響應(yīng)延遲增加;SIZE算法則以對象的規(guī)模作為主要的替換依據(jù),但該依據(jù)不能很好地反映真實(shí)的網(wǎng)絡(luò)環(huán)境.總體來說,上述算法簡單、容易實(shí)現(xiàn),但存在命中率低、浪費(fèi)系統(tǒng)空間的問題.

由于流媒體自身的特點(diǎn),傳統(tǒng)的緩存算法和Web緩存算法已經(jīng)不能很好地適應(yīng)Internet上的視頻點(diǎn)播服務(wù),因此關(guān)于流媒體的緩存出現(xiàn)了很多改進(jìn)的算法.

由于Web訪問的時間局部性,文獻(xiàn)[2]提出了基于時間間隔的流媒體緩存算法.該算法將數(shù)據(jù)分片在節(jié)點(diǎn)的緩存時間進(jìn)行等間隔劃分,以此構(gòu)造線性馬爾科夫鏈,然后利用轉(zhuǎn)移概率矩陣預(yù)測分片的緩存價值;文獻(xiàn)[3]提出了將流媒體對象的頭部預(yù)先在代理服務(wù)器上緩存,以提高用戶訪問的點(diǎn)擊命中率;文獻(xiàn)[4]提出一種新的代理緩存分段算法——A dap tive&Lazy算法,該算法的思想是對媒體文件的分段操作盡量晚,然后根據(jù)用戶訪問的平均間隔對媒體對象進(jìn)行分段.在基于P2P的流媒體網(wǎng)絡(luò)中,A dap tive&Lazy算法得到了廣泛應(yīng)用 .

2 基于用戶行為的流媒體分段緩存算法

2.1 用戶行為建模

流媒體技術(shù)使視頻數(shù)據(jù)在網(wǎng)絡(luò)中以無需下載等待的方式進(jìn)行播放,這種播放方式和“實(shí)時播放”的流媒體服務(wù)相比具有很多優(yōu)點(diǎn),如啟動延時短、對系統(tǒng)緩存容量需求低等.但同時流媒體對象也具有自己的特點(diǎn):①流媒體對象的規(guī)模遠(yuǎn)大于Web對象;②流媒體對象多為靜態(tài)對象,通常具有一次寫多次讀的特性;③流媒體對象的前綴具有很高的訪問概率,用戶往往通過對流媒體最初部分的瀏覽來決定是否全部觀看.

用戶訪問行為在一定程度上影響著流媒體服務(wù)器緩存算法的性能.基于不同的用戶訪問模式,各緩存算法的性能會表現(xiàn)出差異,因此應(yīng)該基于最真實(shí)的用戶訪問行為來設(shè)計(jì)緩存算法.本文以某大學(xué)VOD系統(tǒng)(服務(wù)器IP為202.196.64.151)3月1日至3月10日和4月10日至4月20日的訪問日志為依據(jù),對用戶的訪問行為進(jìn)行分析.

定義1 相對流行度(RPi):對服務(wù)器中的流媒體對象的流行度進(jìn)行歸一化處理,得到各流媒體對象的相對流行度.表示如下:

其中:Pi為對象i的流行度;C由對流行度的歸一化處理所得,C= Pi/∑Pi.

根據(jù)流媒體對象被訪問的次數(shù)與播放時間的關(guān)系(如圖1所示)可看出:VCR操作下的用戶點(diǎn)播滿足“二八定律”;Internet環(huán)境中用戶請求具有高度的時間和空間局部性;用戶對流媒體的興趣往往取決于最開始的部分.

2.2 算法設(shè)計(jì)

由對用戶行為的建模分析可知,流媒體對象的緩存價值受訪問次數(shù)、平均訪問長度以及未來該對象被訪問的概率等因素影響.

本算法根據(jù)相對流行度的概念預(yù)測每個文件的訪問概率,同時結(jié)合不同用戶的網(wǎng)絡(luò)情況和不同的媒體文件使用分段策略[6],在相對流行度的基礎(chǔ)上引入動態(tài)分段(RP-S算法),對每個流媒體對象按指數(shù)增加方式進(jìn)行分段.若某個流媒體對象(用戶從未訪問過)第1次被請求訪問,系統(tǒng)將為該對象生成一個日志文件,用來記錄該對象某一固定時間內(nèi)被訪問的次數(shù),以及每次用戶訪問的持續(xù)時間.

圖1 流媒體對象的相對流行度與播放時間的關(guān)系

算法中用到的參數(shù)如下:

M:緩存大小;

Di:數(shù)據(jù)分段;

Li:對象 i的日志文件;

Ni:對象 i的訪問次數(shù);

Ti:對象i被訪問的持續(xù)時間;

Pi:流媒體對象的流行度;

RPi:流媒體對象的相對流行度.

當(dāng)流媒體對象段Di從服務(wù)器到達(dá)客戶端進(jìn)行緩存時,執(zhí)行如下算法:

(1)如果 Di是第1次被訪問,則轉(zhuǎn)向(2),否則轉(zhuǎn)向(3);

(2)為 Di創(chuàng)建日志文件Li,并記錄訪問次數(shù)和時間等信息;

(3)計(jì)算 RPi并記錄在Li中;

(4)如果 Di的剩余部分已全部分片,則轉(zhuǎn)向(5),否則轉(zhuǎn)向(6);

(5)對Di進(jìn)行指數(shù)分段;

(6)如果緩存未滿,將Di放入緩存,否則轉(zhuǎn)向(7);

(7)如果緩存滿,則根據(jù) RPi執(zhí)行替換,依次選擇RPi最小的分段進(jìn)行替換;

(8)將Di的分段放入緩存.

為了減少系統(tǒng)的啟動延時,還為每個流媒體對象保留一小段前綴分段.這樣能夠保證當(dāng)用戶首次訪問該對象的時候,系統(tǒng)能夠立即為其服務(wù),從而減少啟動延時.

2.3 性能分析

仿真實(shí)驗(yàn)以指數(shù)分段緩存算法和流行度緩存算法作為對比參照.在指數(shù)分段算法中,將緩存總量的10%留作存放媒體對象的前綴,緩存片段遞增指數(shù)為2,前綴長度400 kB,即第 i個片段的長度 P(i)=2i-1×c,其中c為前綴長度400 kB.實(shí)驗(yàn)日志采用真實(shí)日志(某大學(xué)VOD系統(tǒng)3月1日至4月30日的訪問日志).

由于代理緩存中字節(jié)命中率大說明更多的用戶請求數(shù)據(jù)由代理緩存來提供,字節(jié)命中率可以有效反映代理緩存減少的骨干網(wǎng)絡(luò)流量,因此選取字節(jié)命中率作為評價指標(biāo).

定義2 字節(jié)命中率(B HR):代理緩存中命中的字節(jié)數(shù)與請求的字節(jié)數(shù)的比.表示如下:

其中:Ri表示代理緩存中命中的字節(jié)數(shù);∑Si表示請求的總字節(jié)數(shù).

仿真實(shí)驗(yàn)結(jié)果如圖2所示.與指數(shù)分段算法和基于流行度的緩存算法相比,RP-S算法在字節(jié)命中率方面具有較好的表現(xiàn).正是由于RP-S算法在替換時考慮了用戶的訪問頻率和訪問持續(xù)時間等因素,并對對象的流行度進(jìn)行了歸一化處理,而且針對流媒體前綴部分訪問概率高的特征使用了指數(shù)分段的方法進(jìn)行分段緩存,才使得緩存的總命中率最大,從而在一定程度上減少了網(wǎng)絡(luò)中的訪問延遲.

3 結(jié) 語

圖2 字節(jié)命中率比較

本文在對網(wǎng)絡(luò)中流媒體對象的用戶訪問模式進(jìn)行建模分析的基礎(chǔ)上,提出了基于用戶行為的流媒體分段緩存算法,利用相對流行度對代理緩存中的流媒體對象進(jìn)行排序替換.這樣一方面通過對流行度的歸一化處理,使得替換依據(jù)更加合理;另一方面也充分考慮了用戶訪問模式,更貼近Web真實(shí)環(huán)境.同時考慮到流媒體前綴部分具有較高的訪問概率,算法使用指數(shù)分段的方法對流媒體對象進(jìn)行分段緩存.仿真實(shí)驗(yàn)結(jié)果表明,RS-P算法相比較指數(shù)分段算法和基于流行度的緩存算法具有較高的字節(jié)命中率,并且在一定程度上減少了網(wǎng)絡(luò)用戶的等待時間.

[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流媒體直播系統(tǒng)緩存算法[J].計(jì)算機(jī)工程與設(shè)計(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點(diǎn)播系統(tǒng)的客戶端磁盤緩存策略[J].計(jì)算機(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-),女,河南南陽人,碩士.