鄧宇珊，莊一嶸，陳 戈，張 軍

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

1 引言

互聯(lián)網(wǎng)的飛速發(fā)展和普及使得網(wǎng)絡(luò)服務(wù)由主要提供文本和圖像的Web多媒體內(nèi)容逐漸轉(zhuǎn)變?yōu)樘峁┮粢曨l等含有更多豐富信息的多媒體內(nèi)容，同時流媒體技術(shù)也隨之流行起來并應(yīng)用于各式各樣的多媒體服務(wù)中，如視頻點播、直播、視頻會議、遠(yuǎn)程教學(xué)、網(wǎng)絡(luò)視頻等。但是流媒體對象的數(shù)據(jù)量比文本內(nèi)容要大很多，需要大量的存儲空間以及更高要求的網(wǎng)絡(luò)帶寬，由此產(chǎn)生的流媒體傳輸時延會嚴(yán)重影響用戶體驗質(zhì)量。為了減少用戶訪問的響應(yīng)時間，研究者提出采用代理緩存技術(shù)，將用戶需要的內(nèi)容放置在離用戶最近的地方[1～4]。

由于流媒體對象數(shù)據(jù)量巨大，采用全文緩存的方法很難取得理想的緩存效果，而前綴緩存策略[5]雖然可以節(jié)省緩存空間，也可以有效縮短用戶訪問的啟動時延，但隨著用戶訪問時進(jìn)行交互式操作的增多，前綴緩存策略的效果將會變差。為了提高緩存策略的適應(yīng)性，研究者提出了均勻分段[6]和指數(shù)分段[7]等分段策略，其基本思想是將流媒體內(nèi)容沿著播放時間分成若干個片段，并以此作為存儲和置換的基本單元[8]，緩存粒度的減小給緩存算法帶來了更大的靈活性，并且也在一定程度上提高了緩存效率。

基于分段的緩存策略雖然提高了緩存性能，但是精細(xì)的分段粒度也增加了系統(tǒng)需要管理的片段數(shù)量和緩存置換次數(shù)。傳統(tǒng)的均勻分段和指數(shù)分段方法僅按照簡單的函數(shù)關(guān)系來對流媒體進(jìn)行分段，沒有充分地考慮到流媒體自身的一些特性，例如外部流行度和內(nèi)部流行度等，因此其分段效果在很多情況下并不理想。參考文獻(xiàn)[9]的研究表明，如果能針對流媒體的一些特性對其分段策略進(jìn)行優(yōu)化設(shè)計，能有效地提高分段的性能。本文在現(xiàn)有分段緩存研究的基礎(chǔ)上，根據(jù)命中率和存儲的流媒體片段流行度之間的關(guān)系，提出了一種基于最佳分段點估計的流媒體非均勻分段方法，該方法首先統(tǒng)計出進(jìn)行全文緩存時的緩存臨界外部流行度以及每個流媒體對象的內(nèi)部流行度，并對該臨界外部流行度與最佳分段點流行度之商隨存儲占比的變化曲線進(jìn)行擬合，然后對最佳分段點進(jìn)行估計，并將流媒體對象以最佳分段點為分割點分成兩個片段。仿真結(jié)果表明，與其他分段策略相比，本文提出的策略在相同命中率的前提下可以顯著減少總分段數(shù)量，并且在總分段數(shù)相同的前提下可以獲得更好的命中率。

2 流媒體流行度特點

緩存空間是有限的，如何利用有限的空間使緩存的流媒體片段價值最大是分段算法的中心思想，而流行度是衡量流媒體價值的重要指標(biāo)。流行度被廣泛用于描述流媒體的流行程度[10,11]，常常使用流媒體文件被訪問的次數(shù)作為流行度的定義。根據(jù)流行度所描述范圍的不同，進(jìn)一步細(xì)分為外部流行度和內(nèi)部流行度。外部流行度是指流媒體對象之間的流行程度，描述的是流媒體文件的整體流行度大小，而內(nèi)部流行度是流媒體對象不同播放時間片段上的流行程度[12,13]。流媒體對象之間的外部流行度會有明顯的差異，每個流媒體的內(nèi)部流行度也會因用戶的個人喜好產(chǎn)生不均勻的分布。本文以2013年1-5月的中國電信股份有限公司廣東分公司（以下簡稱廣東電信）IPTV系統(tǒng)的點播訪問日志為依據(jù)，分別對以上兩種流行度的特點進(jìn)行了分析，并研究了各個存儲占比情況下的最佳分段點。

2.1 流媒體流行度分布

流媒體的外部流行度常使用Zipf分布或廣延指數(shù)分布進(jìn)行刻畫[14]，用戶的訪問具有很強(qiáng)的傾向性，少數(shù)的熱門影片往往占有大量的用戶請求，也就意味著大多數(shù)的低流行度影片是不會被緩存的，對于這部分影片一視同仁地細(xì)分段顯然會大大增加無謂的分段管理成本。

研究者還發(fā)現(xiàn)，近一半的用戶請求不會播放完整個影片，而是在影片結(jié)尾之前就提前終止請求，因此同一流媒體內(nèi)部不同區(qū)段之間也存在著流行度的差異，用戶常常會通過觀看影片的初始部分，以確定是否有興趣繼續(xù)觀看，于是造成影片的內(nèi)部流行度會隨著播放時間而逐漸遞減[15]。以每分鐘一個區(qū)段計算影片的內(nèi)部流行度，400部影片內(nèi)部流行度與播放時間的關(guān)系如圖1所示，影片起始部分的流行度會有一個快速下降的過程，這是用戶的瀏覽行為造成的，而后流行度以較平穩(wěn)的趨勢逐漸減小。由圖1可以看出，內(nèi)部流行度是非均勻的，也就意味著外部流行度高的流媒體對象也很可能會有內(nèi)部流行度非常低的部分，而且每個影片的內(nèi)部流行度的變化也有所差別，傳統(tǒng)的分段算法，例如均勻分段，往往不依據(jù)或者只單純依據(jù)外部流行度的高低對影片進(jìn)行分段而忽略了每個影片的內(nèi)部流行度變化，具有一定的局限性，不能充分利用流媒體對象的流行度信息。

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

2.2 存儲占比與最佳分段點

不同流媒體對象之間的外部流行度和流媒體對象的內(nèi)部流行度都存在著訪問頻度的差異，由于存儲空間有限，每段流媒體通?？梢苑譃榇鎯Σ糠趾头谴鎯Σ糠帧＜僭O(shè)可以對流媒體進(jìn)行無限精細(xì)度的分段，本文進(jìn)一步分析了在不同存儲占比下，命中率最高時視頻是否被存儲的分界點流行度下限，如圖2所示。由圖2可知，最佳分段點上的流行度下限隨著存儲占比的加大而逐漸變小，這是由于存儲占比越大，緩存空間也越大，可以緩存更多的影片內(nèi)容，從而使得臨界點處的影片分段流行度變得越小。

圖2 最佳分?jǐn)帱c處流行度與存儲占比關(guān)系

根據(jù)以上對流媒體流行度的分析，發(fā)現(xiàn)由于用戶請求有著比較強(qiáng)的傾向性，影片之間以及影片內(nèi)部的流行度分布常常是不均勻的，內(nèi)部流行度有著隨播放時間增加逐漸降低的特點，而流行度又是影響命中率的直接因素，如果能夠直接根據(jù)分段點下限值將影片分成兩段，那么就能從根本上提高命中率，并且減少分段數(shù)量。

3 基于最佳分段點估計的流媒體分段策略

由于高流行度的視頻往往占整個視頻總數(shù)的少部分，且視頻之間的流行度具有較大差異，視頻內(nèi)部的流行度也具有分布不均的特點，因此盡量緩存流行度高的片段是提高命中率和緩存利用率的有效方法。從理論上分析了緩存的流媒體片段流行度與命中率之間的關(guān)系以及將影片分成兩段的分段點下限值的估計方法，并在此基礎(chǔ)上提出了一種基于流媒體對象內(nèi)部分段點估計的新分段策略。

3.1 緩存的片段流行度對命中率的影響

字節(jié)命中率（byte hit ratio,BHR）是指緩存中命中的數(shù)據(jù)量與用戶請求的總數(shù)據(jù)量的比值[16,17]，表示如下：

其中，CBR代表緩存命中的數(shù)據(jù)量，UTD代表請求的總數(shù)據(jù)量。

設(shè)流媒體對象內(nèi)部流行度的計算基本粒度為Rbbyte，即統(tǒng)計流媒體對象分割為Rbbyte片段時的每個片段的流行度。設(shè)Φ={φij|i=1,2,…,N,j=1,2,…,ri}為所有視頻的基本粒度片段的集合，其中，N為緩存視頻總數(shù)，φij為第i個視頻的第j個片段，ri為第i個視頻的片段總數(shù)。當(dāng)存儲空間有限時，只能存儲部分視頻片段，設(shè)Φ′為緩存中的視頻片段集合，則：

其中，P(φij)為φij的流行度，則命中率為：

假設(shè)視頻的內(nèi)部流行度P(φij)在短暫的時間里是不變的，那 么Σφij∈ΦP(φij)也 是 不 變 的，則Σφij∈Φ′P(φij)越 大，BHR就越大，即緩存中的視頻片段流行度越大，字節(jié)命中率越大。

3.2 最佳分段點的估計模型

本文按視頻的流行度大小排序進(jìn)行緩存，設(shè)所有視頻片段的集合為Φ={φij|i=1,2,…,N,j=1,2,…,Mi}，其中N為視頻總數(shù)，Mi為第i個視頻的片段數(shù)，φij為第i個視頻的第j個片段。緩存空間為C時，被緩存的視頻片段集合依然設(shè)為Φ′，那么不被緩存的片段集合則為Φ′=Φ-Φ′。

若不對視頻進(jìn)行分段，即全文緩存的情況下，所有視頻集合則為Φ={φi|i=1,2,…,N}，則緩存臨界點處的視頻外部流行度Pc滿足：

其中，l(φi)為視頻φi的長度。

對視頻進(jìn)行分段，并逐漸減小分段長度l，當(dāng)l減小到1個單位數(shù)據(jù)量長度時，緩存臨界點處的視頻片段流行度就是最佳的分段點內(nèi)部流行度下限值Po：

其中，l(φij)=1。

由以上分析可知，臨界點處視頻片段流行度隨著分段長度l的減小逐漸向Po靠近，本文以廣東電信IPTV系統(tǒng)2013年12月的實際用戶點播訪問日志對Po和Pc之間的關(guān)系進(jìn)行建模分析。圖3為存儲占比變化時，視頻進(jìn)行全文緩存時的臨界外部流行度與最佳分段點處的內(nèi)部流行度的比值k的變化情況。由圖3可知，k的值隨著存儲占比的增加呈現(xiàn)著逐漸增加的趨勢，并且k與存儲占比的關(guān)系可以使用多項式分布模型進(jìn)行擬合。設(shè)存儲占比表述為c，則：

即：

圖3 k與存儲占比關(guān)系

其中，a1，a2，…,an+1為n階多項式模型參數(shù)，可獲得最佳擬合曲線。

式（8）所表述的模型對不同存儲占比下3階和5階多項式的擬合情況如圖4所示，3階多項式的擬合決定系數(shù)R2=0.963 76，5階多項式的擬合決定系數(shù)R2=0.998 57，兩者的決定系數(shù)都接近1，說明兩種多項式的結(jié)合效果都比較好，從圖4中也可以看出，該模型可以比較好地刻畫k與存儲占比之間的關(guān)系，并且多項式的階數(shù)越高擬合效果越好，也就是說只要獲得視頻完整緩存情況下的臨界流行度就可以估計出最佳的分?jǐn)帱c處內(nèi)部流行度閾值，而完整緩存的視頻不需要進(jìn)行分段，計算復(fù)雜度較小，只要獲得所有視頻的外部流行度信息就可以很容易得到。

3.3 分段策略

利用第3.2節(jié)中分析的估計內(nèi)部分段流行度閾值方法，將每個視頻分成高流行度段和低流行度段兩個片段，可以大大減少視頻總的分段數(shù)目，同時也可以保證比較好的命中率。

圖4 Pc/Po隨存儲占比的變化曲線擬合情況

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

（1）數(shù)據(jù)統(tǒng)計

設(shè)定一個合理的流行度統(tǒng)計周期T，并統(tǒng)計待估計周期T′的前一個周期1T′和前兩個周期T′2內(nèi)的所有視頻的內(nèi)部和外部流行度。

（2）建立內(nèi)部流行度閾值估計模型

·根據(jù)式（5）和式（6），計算得到周期T′2的完整緩存情況下的臨界流行度Pc2和周期1T′的最佳的視頻內(nèi)部分段流行度Po1。

·根據(jù)式（7），對不同存儲占比下的完整緩存的臨界流行度與最佳分段流行度曲線之商k=Pc2/Po1進(jìn)行擬合，得到參數(shù)a1，a2，…，an的值。

（3）內(nèi)部流行度閾值估計

·根據(jù)式（5）計算得到周期1T′在完整緩存情況下的臨界流行度Pc1。

（4）分段

根據(jù)估計的分段流行度Po，對周期T′內(nèi)的所有視頻分成兩個片段：內(nèi)部流行度高于Po的內(nèi)容部分為一個片段，低于Po的部分為另一個片段。

（5）重新分段

由于視頻的流行度會隨著時間的推移而不斷變化，每個周期對已有舊視頻進(jìn)行檢測，如果視頻現(xiàn)有的分段點閾值與最佳分段點閾值相差達(dá)到一定程度則對該視頻進(jìn)行重新分段。

本文的分段策略依據(jù)流行度對命中率的重要性，并對最佳的內(nèi)部分段點進(jìn)行估計，充分利用了視頻的外部和內(nèi)部流行度信息，一方面直接針對命中率進(jìn)行了提高，另一方面也大大減少了總的分段數(shù)量。

4 實驗結(jié)果

本文的實驗數(shù)據(jù)采用廣東電信IPTV系統(tǒng)2013年12月流行度前400的電影類視頻真實點播訪問日志，共有8 000條記錄。采用字節(jié)命中率和總分段數(shù)對分段策略進(jìn)行性能評估，其中總分段數(shù)對系統(tǒng)管理的復(fù)雜度有直接影響，而字節(jié)命中率可以有效地比較各個分段策略所消耗的網(wǎng)絡(luò)流量。仿真實驗采用2013年12月1-15日的數(shù)據(jù)對2013年12月下半月的視頻最佳分段點進(jìn)行估計，并對比了采用3階多項式估計最佳分段點時，本文的分段策略與均勻分段策略相同總分段數(shù)下的命中率大小以及相同命中率下的總分段數(shù)大小。

4.1 相同總分段數(shù)情況下的字節(jié)命中率比較

圖5為相同總分段數(shù)情況下，不同分段策略的字節(jié)命中率比較結(jié)果。本文的分段策略命中率基本上達(dá)到了最佳分段點分段時的命中率，并與均勻分段策略相比明顯呈現(xiàn)出更好的命中率，這是由于最佳分段點估計分段策略充分利用了實際內(nèi)部和外部流行度特征，并對分段點處內(nèi)部流行度進(jìn)行了良好的估計，不僅提高了字節(jié)命中率，還可以減少用戶訪問時延并節(jié)省了網(wǎng)絡(luò)流量以及緩存空間資源。

圖5 不同分段策略的字節(jié)命中率比較

4.2 相同命中率情況下的總分段數(shù)比較

表2為相同命中率情況下，不同分段策略的總分段數(shù)大小比較結(jié)果。在各個存儲占比大小下，本文的分段策略的總分段數(shù)都遠(yuǎn)遠(yuǎn)低于均勻分段策略，這是由于本文的分段策略根據(jù)最佳分段點估計值對視頻進(jìn)行分段，每個視頻最多分為2段，在保證命中率的同時也可以獲得分段數(shù)的減少，從而節(jié)省了系統(tǒng)的分段管理成本。

表2 最佳分段點估計分段策略的總分段數(shù)相對于均勻分段的減少量比較

5 結(jié)束語

本文對流媒體的內(nèi)部和外部流行度進(jìn)行了分析，并基于流行度對命中率的重要性，提出了基于最佳分段點估計的流媒體非均勻分段策略。通過對流行度建模分析，利用流媒體的外部流行度對最佳分段點的內(nèi)部流行度進(jìn)行估計，將視頻最多分成兩段，達(dá)到了減少總分段數(shù)目的目的，同時由于增強(qiáng)了流媒體對象對流行度的適應(yīng)性，也獲得了較好的命中率。實驗結(jié)果表明，對比于傳統(tǒng)的均勻分段策略，本文分段策略可以在相同總分段數(shù)的情況下提高字節(jié)命中率，節(jié)約緩存資源以及網(wǎng)絡(luò)帶寬，也可以在相同命中率情況下大大減少總分段數(shù)，降低系統(tǒng)分段管理成本。本文所提方法的局限性在于估計最佳分段點時假設(shè)內(nèi)部和外部流行度在一定時間內(nèi)保持不變，然而實際中無論外部還是內(nèi)部流行度都是動態(tài)變化的，因此在估計最佳分段點時考慮流行度變化的特點將有望能進(jìn)一步提高本文方法的性能。

1 張玉潔,何明,孟祥武.基于用戶需求的內(nèi)容分發(fā)點對點網(wǎng)絡(luò)系統(tǒng)研究.軟件學(xué)報，2014,25(1)：98～117 Zhang Y J,He M,Meng X W.Research on CDN-P2P system over user requirements.Journal of Software,2014,25(1)：98～117

2 Theodorou M,Paterakis M.Efficient cache management policiesfor streaming proxies supporting complete and partial video playback.Proceedings of the 5th International Conference on Next Generation Networks and Services(NGNS 2014),Casablanca,Morocco,2014:270～277

3 何智聰，谷光昭，王新等.基于可重構(gòu)路由器上緩存的流媒體協(xié)作分發(fā)策略.通信學(xué)報，2012,33(6)：82～90 He Z C,Gu G Z,Wang X,et al.Novel cooperative caching strategies for video streaming distribution based on reconfiguration routers.Journal on Communications,2012,33(6):82～90

4 王蒙蒙.基于異構(gòu)網(wǎng)絡(luò)的交互式流媒體緩存替換算法.信息通信，2013(6):71～72 Wang M M.Cache replacement algorithm based on heterogeneous network of interactive streaming media file.Information and Communications,2013(6):71～72

5 Sen S,Rexford J,Towsley D.Proxy prefix caching for multimedia streams.Proceedings of IEEE Conference On Computer Communications,New York,USA,1999:1310～1319

6 Chen S 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,USA,2003:22～31

7 Wu K L,Yu P S,Wolf J L.Segment-based proxy caching of multimedia streams.Proceedings of the 10th International Conference on World Wide Web,Hong Kong,China,2001:36～44

8 余江，楊宗凱，杜旭等.基于兩點流行度的流媒體緩存算法.華中科技大學(xué)學(xué)報（自然科學(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),2006,34(10):15～17

9 鄧宇珊，梁潔，張軍等.基于流行度分類的流媒體分段策略.電信科學(xué),2015,31(1)：152～157 Deng Y S,Liang J,Zhang J,et al.Segmentation strategy of streaming media based on popularity classifying.Telecommunications Science,2015,31(1):152～157

10 楊傳棟，余鎮(zhèn)危，王行剛等.基于流行度預(yù)測的流媒體代理緩存替換算法.計算機(jī)工程,2007,33(7):99～100,129 Yang C D,Yu Z W,Wang X G,et al.Proxy cache replacement algorithm based on popularity prediction of streaming media file.Computer Engineering,2007,33(7):99～100,129

11 張艷，牛朵朵.基于最小代價的流媒體緩存替換算法研究.中原工學(xué)院學(xué)報，2012，23(5)：73～75 Zhang Y,Niu D D.Research of caching replacement algorithm of streaming media based on minimize cost.Journal of Zhongyuan Institute of Technology,2012,23(5):73～75

12 Yu J,Chun T C,Yang Z K,et al.A proxy caching algorithm based on user access preference in streaming media.Microelectronics & Computer,2006,23(11):19～22,25

13 劉宜寧，趙正德，全衛(wèi)新等.基于媒體流行度和前綴緩存的緩存替換算法.中國圖像圖形學(xué)報,2007,12(10):1753～1756 Liu Y N,Zhao Z D,Quan W X,et al.Proxy cache replacement algorithm based on popularity and prefix caching.Journal of Image and Graphics,2007,12(10):1753～1756

14 周軸.視頻點播系統(tǒng)訪問行為研究：測量、分析與建模(博士學(xué)位論文).合肥：中國科學(xué)技術(shù)大學(xué)，2009 Zhou Z.Research on the access behavior of video on demand system:measurement,analysis and modeling(doctor dissertation).Hefei:University of Science and Technology of China,2009

15 余江.流媒體代理緩存算法研究(博士學(xué)位論文).武漢：華中科技大學(xué),2006 Yu J.Research on proxy caching algorithms for streaming media(doctor dissertation).Wuhan:Huazhong University of Science and Technology,2006

16 李曉楠，朱永寬，張來勝.基于用戶行為的流媒體分段緩存算法.中原工學(xué)院學(xué)報，2010,21(4)：62～64,69 Li X N,Zhu Y K,Zhang L S.Segmentation caching algorithm of streaming media based on user accessing.Journal of Zhongyuan Institute of Technology,2010,21(4):62～64,69

17 劉磊,熊小鵬.最小駐留價值緩存替換算法.計算機(jī)應(yīng)用,2013,33(4):1018～1022 Liu L,Xiong X P.Least cache value replacement algorithm.Journal of Computer Applications,2013,33(4):1018～1022