張 艷，牛朵朵

（1.河南職業(yè)技術(shù)學(xué)院，鄭州450046；2.重慶師范大學(xué) 涉外商貿(mào)學(xué)院，重慶401520）

基于最小代價的流媒體緩存替換算法研究

張 艷1，牛朵朵2

（1.河南職業(yè)技術(shù)學(xué)院，鄭州450046；2.重慶師范大學(xué) 涉外商貿(mào)學(xué)院，重慶401520）

基于對現(xiàn)有流媒體緩存技術(shù)的分析，提出了一種基于最小代價的流媒體緩存替換算法.通過定期統(tǒng)計代理緩存中流媒體前綴片段的流行度，在緩存替換時綜合考慮流媒體對象的訪問熱度和替換的字節(jié)代價，使得緩存替換的代價盡量小，進(jìn)而獲取較大的字節(jié)命中率.仿真實驗結(jié)果表明，最小代價替換算法在提高字節(jié)命中率方面表現(xiàn)較好.

流行度；字節(jié)代價；流媒體；緩存替換算法

隨著互聯(lián)網(wǎng)業(yè)務(wù)的蓬勃發(fā)展及互聯(lián)網(wǎng)用戶數(shù)的持續(xù)增長，流媒體點播服務(wù)也快速膨脹.流媒體對象通常具有文件體積大、服務(wù)持續(xù)時間長的特點，該特點決定了流媒體服務(wù)對帶寬有著較高的要求，從而影響了服務(wù)器的吞吐能力和流媒體服務(wù)的質(zhì)量.因此，采用合理的流媒體緩存算法可以改善代理服務(wù)器流媒體服務(wù)的質(zhì)量.

現(xiàn)有的流媒體緩存算法可分為：①基于分段的方法，如基于共享片段的方法［1］、基于指數(shù)分段的方法［2］；②基于用戶訪問行為的方法，如基于流媒體流行度進(jìn)行預(yù)測緩存［3］；③基于時間間隔的方法，如運用等間隔劃分的方法構(gòu)造馬爾夫鏈從而進(jìn)行緩存［4］；④基于代價的方法，如基于最小代價緩存的方法［5］.相比于傳統(tǒng)緩存，流媒體緩存有其自身特點.本文分析了Internet上流媒體緩存的特點以及流媒體用戶的訪問模式.通過定期統(tǒng)計代理緩存中流媒體前綴片段的流行度，進(jìn)而在分段緩存的基礎(chǔ)上，結(jié)合片段自身的流行度和字節(jié)訪問熱度對流媒體進(jìn)行緩存.仿真實驗驗證了該算法可以獲得較大的字節(jié)命中率.

1 現(xiàn)有流媒體緩存技術(shù)的特點

與傳統(tǒng)緩存相比，現(xiàn)有流媒體緩存有其自身的特點：（1）流媒體對象的文件大小通常比傳統(tǒng)Web對象的文件大幾個數(shù)量級；

（2）流媒體對象多為靜態(tài)的，很少改變，對緩存一致性要求不高；

（3）流媒體用戶通常只根據(jù)文件最初部分來決定是否全部觀看；

（4）流媒體對象在文件大小、播放持續(xù)時間和網(wǎng)絡(luò)帶寬需求等方面具有完全不同于傳統(tǒng)Web對象的特點：① 流媒體文件長度不均勻，從幾兆、幾十兆（如新聞）到幾百兆（如電影、電視劇等）不等；② 用戶對流媒體的訪問具有比Zipf分布更強的偏向性，排名前100的文件的請求占了總訪問請求數(shù)的85%以上；③請求流具有比www資源訪問更強的時間定域性特征，對于前d個對象（d＜＝40）具有更強的訪問熱度.

流行度（popularity）是用于描述流媒體流行程度的一個概念，它反映了流媒體文件在某一時刻被客戶請求的概率.用戶訪問流媒體對象的一般特點是：在開始的一小段時間內(nèi)會有很大一部分用戶停止訪問；隨著時間的延長，停止訪問的用戶會趨于穩(wěn)定.流媒體流行度分布如圖1所示.

2 自適應(yīng)流媒體分段緩存算法

在t時刻，當(dāng)有用戶訪問到達(dá)時，對于流媒體對象的請求，系統(tǒng)會檢查該請求是否在緩存中（若在，則從緩存中讀取前綴片段；若不在，且緩存中有足夠的空間，則將該媒體對象的前綴部分放入緩存中，生成log文件，否則，當(dāng)緩存滿且用戶請求的流媒體對象不在緩存中時，替換發(fā)生）.此時，緩存的狀態(tài)用St表示，大小為M，當(dāng)前用戶請求為Rt，替換出的流媒體對象為Vt，并生成log文件.在log中記錄在△t時間間隔內(nèi)的片段i被訪問的次數(shù)ni以及每次被訪問的字節(jié)數(shù)st.在t＋1時刻，緩存的狀態(tài)為：

圖1 流媒體流行度分布

一個好的分段算法要能夠準(zhǔn)確地反映用戶訪問的媒體對象的特點.分段策略是判斷一個緩存策略好壞的關(guān)鍵之一.對于第一次被請求的媒體對象，根據(jù)log文件中的訪問次數(shù)統(tǒng)計其流行度，以此作為流媒體對象分段的依據(jù).同時，對于不同的流媒體對象，用戶的訪問特點是不同的，所以采用單一的分段算法無法準(zhǔn)確反映其特點.基于流媒體對象大小不等，熱度分布不均衡，對流媒體對象的流行度做如下計算：

其中，R表示在△t時間內(nèi)代理服務(wù)器中的所有請求.用該方法計算出的流行度是在△t時間內(nèi)的一個近似估計.為統(tǒng)計該流媒體的熱度，根據(jù)被訪問的字節(jié)數(shù)統(tǒng)計片段i的字節(jié)流行熱度ci：

其中，S表示該片段的長度.

將流行度和字節(jié)流行熱度統(tǒng)一考慮，得出片段i的替換代價Ci：

為了更準(zhǔn)確地反映用戶的訪問熱度，本文將流媒體對象的片段分為前綴片段和基本片段：前綴片段采用統(tǒng)一長度，按照其替換代價Ci值的大小在緩存中按照由小到大的順序進(jìn)行排序；基本片段采用指數(shù)分段的方法.

（1）前綴片段替換代價統(tǒng)計算法

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

Output：替換代價Ci；

Method：

①對于用戶請求Rt，讀取片段的log文件.若有l(wèi)og文件，轉(zhuǎn)向（2），否則轉(zhuǎn)向（3）；

②計算片段在t時刻的Pi和ci，記錄在log中；

③若用戶請求的文件為新媒體對象，對其進(jìn)行分段，并生成log文件；

④ 對于緩存中的每個片段，計算其替換代價Ci.

（2）最小代價替換算法

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

Output：替換代價序列；

Method：

①根據(jù)每個片段的替換代價，將其在緩存中按照由小到大的順序進(jìn)行排序；

② 當(dāng)緩存滿時，則取隊列首文件進(jìn)行替換.

3 實驗與分析

采用仿真實驗，在緩存算法模擬平臺 MiddleS－im［6］中加入最小代價的分段替換算法，并將該算法與指數(shù)分段算法和流行度預(yù)測算法做比較.

實驗日志為Campus以及由日志生成器 Medisyn生成的日志.它記錄了從2010年8月到2011年3月的流媒體訪問信息.

評價指標(biāo)采用字節(jié)命中率，其表達(dá)式如下：BHR ＝s△t／S△t

其中，s△t和S△t分別表示在△t時間間隔內(nèi)命中的字節(jié)數(shù)和總的請求字節(jié)數(shù).

3種方法所得字節(jié)命中率分布圖如圖2所示.

由圖2可以看出，由于指數(shù)分段算法比較單一，字節(jié)命中率稍低；流行度預(yù)測算法更貼合用戶訪問特點，其字節(jié)命中率要高于單一的指數(shù)分段算法；而最小代價算法由于綜合考慮了分段算法和用戶的訪問行為，在字節(jié)命中率方面表現(xiàn)較好.

4 結(jié) 語

圖2 字節(jié)命中率分布圖

本文針對代理服務(wù)器流媒體緩存進(jìn)行了研究.在分析流媒體緩存算法和流媒體對象特點的基礎(chǔ)上，通過定期統(tǒng)計代理緩存中流媒體前綴片段的流行度，在緩存替換時盡可能地考慮媒體對象的訪問熱度和替換的字節(jié)代價，使得緩存替換的代價盡量小，進(jìn)而獲取較大的字節(jié)命中率，從而達(dá)到改善流媒體服務(wù)質(zhì)量的目的.仿真實驗結(jié)果表明，本算法在緩存字節(jié)命中率方面有較好的表現(xiàn).

［1］ 石磊，程剛運.共享片段自動檢查模型［J］.計算機應(yīng)用，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］ 楊傳棟，余鎮(zhèn)危，王行剛.基于流行度預(yù)測的流媒體代理緩存替換算法［J］.計算機工程，2007，33（7）：99－100.

［4］ 楊靜，李潤知，王宗敏.基于時間問隔的P2P流媒體直播系統(tǒng)緩存算法［J］.計算機工程與設(shè)計，2010，31（1）：90－93.

［5］ 胡玉琦，郝留有，孫爽.基于最小價值的流媒體緩存替換算法［J］.計算機工程與設(shè)計，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－），女，河南新鄉(xiāng)人，碩士.