鄧宇珊，陳 戈，張 軍，梁 潔

（1.華南理工大學(xué)電子與信息學(xué)院 廣州 510640；2.中國電信股份有限公司廣東研究院 廣州 510630）

1 引言

隨著互聯(lián)網(wǎng)的日益普及和飛速發(fā)展，人們對多媒體內(nèi)容的需求也有了很大改變?；ヂ?lián)網(wǎng)已經(jīng)由原來的以提供文本和圖像為主的多媒體服務(wù)演變成為提供更豐富信息，如音視頻文件為主的服務(wù)，各種各樣的流媒體服務(wù)也得到了廣泛應(yīng)用，如網(wǎng)絡(luò)視頻、視頻點(diǎn)播、遠(yuǎn)程教學(xué)、視頻會議、IPTV等。但是，隨著流媒體應(yīng)用的普及，相應(yīng)的問題也逐步凸顯出來。流媒體對象巨大的數(shù)據(jù)量對網(wǎng)絡(luò)帶寬的要求比文本內(nèi)容要大很多，同時也增加了流媒體傳輸時延，影響用戶體驗(yàn)質(zhì)量。通過在網(wǎng)絡(luò)邊緣靠近用戶的地方設(shè)置代理緩存服務(wù)器，緩存流行度最高的部分視頻或者視頻片段是目前主流的解決方法。

流媒體對象巨大的數(shù)據(jù)量使得緩存整個媒體文件會快速占用大量的緩存空間，前綴緩存策略[1,2]可以在一定程度上解決這個問題，在大部分用戶都訪問流媒體對象的開始一段時間，前綴緩存策略能夠得到比較好的效果，同時它也可以有效減少用戶訪問的啟動時延，但前綴緩存不適用于互交式的流媒體。基于分段的緩存策略相比前綴緩存策略具有更強(qiáng)的適應(yīng)性，均勻分段[3,4]和指數(shù)分段[5]是最經(jīng)典的分段策略。均勻分段是把流媒體文件分成相同大小的段，分段的粒度越細(xì)，分段緩存的性能越好；指數(shù)分段是把流媒體文件按播放時間分成長度呈指數(shù)增長的段，該策略是基于用戶對流媒體文件前面部分比后面部分更感興趣的假設(shè)，其優(yōu)勢是能夠通過替換大的低流行度段快速獲得大量緩存空間。

均勻分段和指數(shù)分段都沒有結(jié)合流媒體文件自身的流行度信息，分段的基本粒度固定，沒有從減少分段數(shù)量、節(jié)省分段管理成本的角度對流媒體進(jìn)行分段和性能評估。本文在現(xiàn)有分段緩存研究的基礎(chǔ)上，針對流媒體文件的緩存替換規(guī)律，提出了一種基于流行度分類的流媒體分段策略，該算法統(tǒng)計(jì)出流媒體對象的流行度，根據(jù)流行度對流媒體文件進(jìn)行分類，把流媒體文件分成高流行度文件和低流行度文件，對不同類型的流媒體文件采取不同的分段策略，充分利用了流媒體文件的流行度信息，仿真實(shí)驗(yàn)結(jié)果表明，與其他分段策略相比，本文提出的策略在相同命中率的情況下可以減少分段數(shù)量。

2 流媒體外部和內(nèi)部流行度特點(diǎn)分析

流行度是指流媒體對象被訪問的次數(shù)，用來描述流媒體流行程度[6]。緩存算法是通過緩存流行度最高的視頻內(nèi)容，在有限資源情況下獲得最好的用戶體驗(yàn)。而在實(shí)際中，用戶對流媒體對象及其內(nèi)部片段的訪問總存在一定的傾向性，不同流媒體對象和不同片段的流行度不同。因而用戶行為必然會在一定程度上影響緩存算法的性能，在對不同內(nèi)容進(jìn)行分段時就需要結(jié)合以上因素合理選擇分段策略。

對流媒體對象流行度的研究需要從兩個方面展開：不同流媒體對象之間的外部流行度和同一流媒體對象不同區(qū)段之間的內(nèi)部流行度。本文以廣東電信IPTV系統(tǒng)2013年1月到2013年5月的點(diǎn)播訪問日志為依據(jù)，分別研究了流媒體外部流行度與內(nèi)部流行度的特點(diǎn)。

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

本文首先對流媒體的外部流行度分布進(jìn)行了研究。通常認(rèn)為流媒體的外部流行度符合Zipf分布或廣延指數(shù)分布[7]，文中分別用兩種分布模型對實(shí)際的流媒體流行度進(jìn)行擬合，其結(jié)果如圖1所示，橫坐標(biāo)為影片按流行度從大到小排序的序號，縱坐標(biāo)為影片被訪問的互補(bǔ)累計(jì)概率，廣延指數(shù)分布比Zipf分布有更好的擬合效果。從圖1可以看出，大多數(shù)用戶請求集中在少數(shù)的熱門影片上，對于大部分熱度極低且不會被存儲的影片來說，對其進(jìn)行一視同仁的分段會增加不必要的分段管理成本。因此，為了降低全部影片總分段數(shù)，需要對不同流行度的影片使用不同的分段策略。

圖1 廣延指數(shù)分布與Zipf分布的曲線擬合情況

2.2 流媒體外部流行度對緩存替換的影響

通過對相鄰兩天最熱門視頻的相同視頻比例進(jìn)行分析，發(fā)現(xiàn)最熱門的7 000部視頻（滿足60%的用戶請求）的相鄰兩天相同視頻比例在87%左右，而最熱門的27 000部視頻的相鄰兩天相同視頻比例在92%左右。這種現(xiàn)象說明，大部分用戶對某些視頻表現(xiàn)出很強(qiáng)的傾向性[8]，導(dǎo)致比較熱門和比較冷門的視頻在流行度上有著一定的穩(wěn)定性和持續(xù)性，這些視頻短期內(nèi)不會從緩存中替換出來或者替換進(jìn)緩存，而處于被緩存邊界的視頻將會比較頻繁地進(jìn)行替換。圖2對這種現(xiàn)象進(jìn)行了描述，分析圖2可知，緩存替換集中在某一小段流行度范圍的視頻上，而大部分流行度偏高和流行度偏低的視頻替換很少，并且隨著到峰值處流行度距離的加大，視頻替換次數(shù)越來越少。另外，存儲占所有視頻容量的比例越大，峰值處流行度越小。

圖2 視頻外部熱度與其緩存替換量的關(guān)系

2.3 流媒體內(nèi)部流行度

同一流媒體內(nèi)部各區(qū)段之間也存在訪問頻度的差異，用戶往往會先看視頻的開始部分，進(jìn)而決定是否繼續(xù)看下去，所以從整個視頻來看，其內(nèi)部流行度分布是不均勻的，會隨著播放時間的推移而逐漸遞減[8]。流行度擾動現(xiàn)象[9,10]是指流媒體外部流行度高的對象，其10 min之后的內(nèi)部流行度不一定高。本文通過對實(shí)際用戶數(shù)據(jù)進(jìn)行分析發(fā)現(xiàn)，這種現(xiàn)象只出現(xiàn)在兩個流媒體對象外部流行度差異不大的情況下，而當(dāng)兩個流媒體對象外部流行度差異較大時，則不會發(fā)生流行度擾動現(xiàn)象。影片外部流行度的高低對其內(nèi)部流行度的影響如圖3所示（24 h的數(shù)據(jù)整理所得，其中排名第五的影片最后曲線急速下落是由于到達(dá)了影片末尾），當(dāng)流媒體外部流行度差異超過一定程度時，外部流行度高的流媒體對象，其內(nèi)部流行度也會高于其他外部流行度低的對象。也就是說，在大趨勢下外部流行度高的對象，其整個播放時間上的內(nèi)容都會比較熱。

圖3 不同外部流行度的流媒體對象的內(nèi)部流行度比較

根據(jù)以上分析，發(fā)現(xiàn)流媒體內(nèi)部和外部流行度具有如下幾個特點(diǎn)。

·用戶訪問的傾向性很強(qiáng)，大多數(shù)請求都集中在少數(shù)熱門的視頻上。

·被頻繁替換的視頻集中在一小段流行度范圍內(nèi)，大部分視頻幾乎不會被替換。

·視頻內(nèi)部流行度會隨著播放時間而逐漸降低，并且外部流行度高的視頻，其內(nèi)部流行度也會比較高。

根據(jù)流媒體流行度內(nèi)部與外部流行度的關(guān)系，可以使用外部流行度決定其整個內(nèi)容上的分段大小。從對緩存替換規(guī)律的分析可知，在固定緩存空間大小的情況下，流媒體對象的緩存替換頻繁程度與流行度有關(guān)，如果在緩存替換比較少的流行度區(qū)間，增大視頻的分段粒度，會大大減少總的分段數(shù)，而在緩存替換比較頻繁的流行度區(qū)間內(nèi)，合理減小緩存替換的粒度，可以更加充分合理地利用緩存空間，使用有限的緩存空間資源存儲更多流行度更高的內(nèi)容。

3 基于流媒體外部流行度分類的分段策略

由于流媒體內(nèi)部流行度分布通常是不均勻的，因此對流媒體進(jìn)行分段管理是提高緩存利用率和命中率的一種常用技術(shù)。本文首先從理論上分析了分段對命中率的影響，然后基于流媒體外部和內(nèi)部流行度的特點(diǎn)，提出一種基于流媒體外部流行度分類的分段新策略。

3.1 分段對命中率的影響

設(shè)Φ={φi|i∈[1,N]}為所有視頻的集合，其中，N為總的視頻數(shù)，φi為第i個視頻。當(dāng)存儲空間為L時，按熱度優(yōu)先原則存于緩存中的視頻集合為Φ′，不被存儲的視頻集合為=Φ-Φ′,則Φ′中的視頻φi滿足：

其中，h（φj）為φj的被訪問概率，l(φj)為φj的存儲空間大小，此時命中率為：

將任意兩個視頻φj∈Φ′和φk∈Φ′分為m段，假設(shè)φjm和φkm分別表示φj和φk的第m個分段，如果h(φjm)

由于視頻內(nèi)部流行度不均勻，經(jīng)常會出現(xiàn)h(φjm)

3.2 分段策略

視頻的流行度具有一定的持續(xù)性，并且緩存替換集中在某一段流行度范圍的少數(shù)視頻上，大多數(shù)視頻很少被替換，而傳統(tǒng)的分段策略并沒有針對緩存替換規(guī)律進(jìn)行分段。本文依據(jù)視頻流行度，以替換頻繁的地方為界對視頻進(jìn)行分類，把視頻分成高流行度視頻和低流行度視頻，替換頻繁的部分視頻分段粒度減小，而其他視頻分段粒度加大，能保證在總分段數(shù)目一定的情況下提高命中率。

本文提出的分段策略分為5個步驟，具體過程如下。

（1）流行度分類

把視頻按照外部流行度分為高流行度視頻或者低流行度視頻，設(shè)分界處的流行度為P，視頻m的流行度為Pm，若Pm>P，則標(biāo)記該視頻為高流行度視頻；若Pm

（2）分段長度計(jì)算

對不同流行度高低類型的視頻做不同的分段處理，使得對于高流行度視頻來說，外部流行度越高，視頻分段粒度越大；而對于低流行度視頻來說，外部流行度越小，分段粒度越大。視頻的起始段定義為視頻的第一個分段，則高流行度視頻m的起始段長度Lm正比于其外部流行度Pm，低流行度視頻n的起始段長度Ln反比于其外部流行度Pn。則視頻起始分段長度為：

其中，ah，al為常數(shù)參數(shù)。

（3）ah，al的計(jì)算

流行度為P的分界處的視頻起始段長度為L，假設(shè)高流行度分類視頻臨界處的視頻起始段長度Lsh和低流行度分類視頻臨界處的視頻起始段長度Lsl相等，且等于L，由式（4）和式（5）可得：

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

ah，al計(jì)算出來后，可以根據(jù)式（4）和式（5）計(jì)算所有視頻的起始段長度。

（4）視頻內(nèi)部的分段方法

[11]經(jīng)過研究指出，指數(shù)分段不適合對所有的視頻進(jìn)行管理，并且在系統(tǒng)中媒體數(shù)量非常多的情況下，緩存準(zhǔn)入和緩存替換的粒度太大，會造成系統(tǒng)抖動，影響系統(tǒng)穩(wěn)定性。而使用線性分段則減緩了分段長度的增長速度，也能夠比較迅速地將熱門視頻進(jìn)行緩存。本文采用參考文獻(xiàn)[11]提出的線性分段方法對每個視頻進(jìn)行分段，設(shè)視頻內(nèi)部段編號為i（起始段編號為1），其起始段長度為Li，則該視頻第i段的長度為Li×i。

（5）視頻的重新分段

視頻的流行度會隨時間變化，時間越長流行度變化越大，因此需要根據(jù)視頻流行度的持續(xù)性特征設(shè)定一個重新分片周期T，全部視頻在一個周期后根據(jù)其當(dāng)前流行度進(jìn)行重新分片，重新分片的時間點(diǎn)可以設(shè)定在用戶點(diǎn)播低谷時段，避免增加網(wǎng)絡(luò)負(fù)擔(dān)。

本文的分段策略在已有分段策略的基礎(chǔ)上增加了對視頻流行度的分類，給定L和P可以計(jì)算出所有視頻的起始流行度，在視頻內(nèi)部仍然更加重視時間靠前的部分內(nèi)容，對每個視頻都使用分段長度增長較緩的線性分段策略，在充分利用了外部流行度特征的同時，也保證了對視頻開頭部分內(nèi)容的重視。

4 實(shí)驗(yàn)結(jié)果分析

本文的實(shí)驗(yàn)數(shù)據(jù)來自廣東電信IPTV系統(tǒng)2013年12月的電影類視頻真實(shí)點(diǎn)播訪問日志，包括3 226個視頻，共有100 000條記錄。分段策略的性能評價指標(biāo)采用了總分段數(shù)和字節(jié)命中率，字節(jié)命中率是緩存中命中字節(jié)數(shù)與總請求字節(jié)數(shù)的比值，可以有效地反映使用分段策略所節(jié)省的網(wǎng)絡(luò)流量，而分段數(shù)的減少可以節(jié)省系統(tǒng)管理成本。本文仿真實(shí)驗(yàn)比較了在相同命中率的情況下，本文分段策略與均勻分段策略的總分段數(shù)大小以及在相同總分段數(shù)的情況下，它們的字節(jié)命中率大小。

4.1 最佳P值的選取

相同總分段數(shù)的情況下，分界流行度對流行度分類分段方法的命中率影響如圖4所示。以L=10 min、存儲占所有視頻比例為10%的情況為例，可以看出分界流行度P在[15 000,25 000]范圍內(nèi)，流行度分類分段策略效果比較好，并且對流行度分類分段策略的命中率影響不大，流行度分類分段策略與均勻分段策略命中率的差也比較穩(wěn)定。表1為存儲占所有視頻比例為10%的情況下，不同的L值對最佳分界流行度P的影響?？梢钥闯鲈诓煌腖下，最佳分界流行度P值有一些波動，但是波動范圍不大，且在20 000左右，因此可以設(shè)定P=20 000，使用相同方法可以為其他不同存儲占所有視頻比例的情況設(shè)定一個理想的分界流行度值。

圖4 分界流行度對兩種分段方法命中率的比較

表1 存儲占所有視頻比例為10%時，不同L下的最佳分界流行度P

4.2 字節(jié)命中率

圖5為L=10 min時，不同分段方法的字節(jié)命中率，實(shí)驗(yàn)結(jié)果是在最佳分界流行度下的記錄。從圖5可以看出，本文的分段策略相比均勻分段策略具有更好的字節(jié)命中率，這是由于流行度分類分段策略充分考慮了實(shí)際緩存替換規(guī)律和流媒體對象的流行度特征，才使得字節(jié)命中率獲得較好效果，從而在一定程度上節(jié)省了緩存空間資源和網(wǎng)絡(luò)流量，但是由于只有少部分視頻緩存替換頻繁，本算法對于總的命中率提高不顯著。

圖5 相同總分段數(shù)情況下不同分段方法字節(jié)命中率比較

4.3 總分段數(shù)

圖6 為L=15 min，分界流行度P為最佳分界流行度，字節(jié)命中率相同的情況下，對兩種分段方法的總分段數(shù)的比較。從圖6中可以看出，在各個緩存空間大小下，本文分段策略都能獲得比均勻分段策略更少的總分段數(shù)，從而可以節(jié)省系統(tǒng)的分段管理資源。

圖6 相同命中率情況下不同分段方法的總分段數(shù)比較

5 結(jié)束語

本文在主流分段策略基礎(chǔ)上，對流媒體的流行度特征進(jìn)行分析，提出了基于流行度分類的流媒體分段策略。利用緩存替換的規(guī)律，對流媒體對象進(jìn)行分類，針對不同流行度采用不同的分段策略，由于增強(qiáng)了對流媒體對象自身流行度的適應(yīng)性，達(dá)到了減少分段數(shù)目的目的，獲得了較好的字節(jié)命中率。實(shí)驗(yàn)結(jié)果表明，該分段策略相比于傳統(tǒng)的均勻分段策略，在相同命中率的情況下，可以減少總的分段數(shù)，節(jié)省系統(tǒng)分段管理成本，同時在相同總分段數(shù)的情況下，字節(jié)命中率有所提高，可以節(jié)省網(wǎng)絡(luò)帶寬和緩存空間資源。

參考文獻(xiàn)

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 張艷,朱朵朵.基于最小代價的流媒體緩存替換算法研究.中原工學(xué)院學(xué)報(bào),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 周鈾,吳剛,李俊.視頻點(diǎn)播中用戶交互式請求數(shù)分布的建模與分析.小型微型計(jì)算機(jī)系統(tǒng),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 林光國,戴瓊海,丁嶸.基于用戶行為統(tǒng)計(jì)的流媒體集群負(fù)載均衡算法.清華大學(xué)學(xué)報(bào)(自然科學(xué)版),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 余江,楊宗凱,杜旭等.基于兩點(diǎn)流行度的流媒體緩存算法.華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),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 楊菲菲,陳志云,曾秋梅.一種基于流行度和分段適應(yīng)性的流媒體緩存算法.計(jì)算機(jī)應(yīng)用與軟件,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 夏琰.基于實(shí)際用戶行為分析的緩存研究（碩士學(xué)位論文）.中國科學(xué)技術(shù)大學(xué),2011 Xia D.Research of caching replacement based on real user behavior(master dissertation).University of Science and Technology of China,2011