靜態與動態結合的流媒體緩存替換算法研究

孫 昕，陳德運

（1.哈爾濱醫科大學 基礎醫學院，黑龍江 哈爾濱150081；2.哈爾濱理工大學 計算機科學與技術學院，黑龍江 哈爾濱150080）

0 引 言

人們對流媒體播放質量和傳輸速率等方面要求越來越高，但傳統的C／S模式點播系統的系統規模受到服務器性能和網絡帶寬的限制，為了解決這些瓶頸問題，近年來人們都將目光投向了P2P［1］技術，由于P2P技術可以有效地降低服務器負載，并有效地利用網絡帶寬和節點I／O資源［2］，所以將P2P技術融入流媒體點播系統可以有效解決流媒體數據占用磁盤空間大和傳輸帶寬高等問題［3］。針對于如何提高P2P流媒體QoS（quality of service），本文提出了基于混合P2P的流媒體點播系統中采用靜態與動態結合的緩存方案。

1 系統結構

本文采用文獻 ［4］所提出的P2PProxy的系統結構，它將P2P的原理用于緩存VOD［5］流媒體：請求同一個視頻文件的用戶組成一個組，分別存儲視頻文件的各個部分，當用戶無法從組內獲得數據時，才從VOD服務器獲得數據，這種方法能夠有效緩解服務器的壓力。如圖1所示。

圖1 系統結構

服務器的主要功能是提供所有節目資源［6］，這樣可以避免純分布式P2P模式下的版權問題和非法視頻問題。同時也要維護各組節點列表，記錄節點的登記和退出信息。處理各節點的服務請求，并記錄各節點的緩存信息。

根據普通節點的節目請求，服務器將其分配到所有觀看該節目的節點所組成的組，普通節點先在該組內查找其所請求節目塊，若找到則由組內節點提供服務，否則由服務器提供服務。各節點要邊觀看邊下載部分數據塊［7］，以便能為其他請求節點提供服務，從而減輕服務器壓力［8］，這一點也正是將P2P技術融入VOD系統的優越性的主要體現。

本文采用的文件劃分方法是將待緩存流媒體文件基于時間流劃分成相同大小的數據塊［9］，整個系統以塊為單位對點播內容進行查找、下載、播放等操作。

2 靜態與動態結合的緩存替換算法

本文提出了一種稱為SDCO （static and dynamic combination）的靜態與動態結合的緩存替換算法，該算法由靜態數據更新算法，播放數據替換算法和預取綜合評定因子算法 （CED）3部分組成，其中，CED算法是SDCO的核心。

2.1 普通節點緩存區的劃分

不同于以往的緩存研究，本文將普通節點緩存區分為3個區，分別是固定指派區 （fixed distribute cache，FDC）、當前播放區 （current play cache，CPC）和預取區 （prefetch distribute cache，PDC）。這樣分區的目的在于盡可能地充分利用客戶端緩存空間，提高其緩存命中率。

2.1.1 固定指派區

由于在系統運行過程中會存在流行度很高的過熱數據塊和流行度比較低的冷數據塊，尤其是在系統剛剛運行時，整個P2P結構的節目播放組中還沒有足夠的數據塊備份量，而動態緩存的研究主要集中在流行度高的數據塊來提高VCR操作命中率，這就需要在緩存區中存在靜態緩存部分，即固定指派區來存儲一些固定分配的數據塊，使得冷熱數據塊得以均衡［10］，尤其在系統運行初期能有效緩解服務器負載。在某個緩存節點i中，設3個區的緩存數據塊數量分別為B （i，FDC），B （i，CPC），B （i，PDC），而整個緩存區的總緩存 數量是 B （i，total），其 中的 B （i，FDC）＝αB （i，total），B （i，CPC）＝βB （i，total），B（i，PDC）＝γB （i，total）。α＋β＋γ＝1。

令參數

若某一節點J（第J個到達節點）的值J＜＝C，則由服務器對各個用戶節點分配固定緩存內容；當J＞C時，說明整個節目組中的靜態固定指派區內已經擁有了該節目的所有數據分塊內容，則不再由服務器對該節點進行分配，而是改由在組內節點間緩存的方案，緩存本節點剛剛播放過的數據塊內容［11］，以供其他對等節點使用或本節點前跳VCR操作用。該區相應的算法為靜態數據更新算法。

2.1.2 當前播放區

該分區主要用來緩存本節點播放點前后的若干數據塊。這些緩存數據塊序號是連續的，可以保證本節點在沒有執行VCR操作時播放節目的流暢性，當其服務節點出現問題時可以保證節目的正常播放，留足了緩沖時間。該分區緩存替換策略采用滑動窗口的方式［12］，始終存放的都是在父節點處獲得的播放點前后的數據塊。若有其他節點正在向本節點請求同樣的數據，則可以繼而轉發給其子節點。該區相應的算法為播放數據替換算法。

2.1.3 預取區

這一分區的目的主要是用來提高本節點和其他節點的VCR操作命中率，并兼顧全局數據塊緩存的優化。預取數據要充分考慮其數據塊熱度和數據塊的稀缺度，并受用戶行為因子的影響。其中，數據塊熱度可由單位時間內的數據塊請求量來表示，設數據塊i熱度為Pi，在t1時刻對于數據塊i的請求量為Ri1，在t2時刻對于數據塊i的請求量為Ri2，則Pi＝ （Ri2－Ri1）／ （t2－t1）；數據塊i稀缺度Si為所有數據塊的副本數與數據塊i的副本數的比值，即Si＝CBtotal／CBi；用戶觀看節目時通常都從開頭部分開始［13］，然后才決定是否繼續觀看，所以針對于用戶這樣的共性行為特征，將節目開始部分數據塊的用戶行為因子設置為Us，其余部分設置為Uo，Us＞Uo，數據塊i用戶行為因子Ui＝UoorUs。綜合上述內容，本文提出一個概念為 “數據塊預取綜合評定因子”PS

該區相應的算法為CED替換算法。

2.2 SDCO緩存替換算法

算法1：靜態數據更新算法。

UpdateFDC（待緩存數據塊i）｛

If（J＜＝C）｛服務器直接分配數據塊；｝

Else｛

If（size（i）＜size（FDC的空閑空間））｛

緩存剛剛播過的數據塊i；｝

Else｛

Rep （i）＝find（FDC）；／／用數據塊i來替換固定區中最久未被使用數據塊；｝

｝

算法流程如圖2所示。

算法2：播放數據替換算法

ReplaceCPC（待緩存數據塊i）｛

If（size（i）＜size（CPC的空閑空間））｛

直接緩存數據塊i；｝

Else｛

Rep （i）＝find （CPC）；／／用數據塊i替換播放區中最久未使用的數據塊；｝

圖2 靜態數據更新策略流程

｝

算法流程如圖3所示。

圖3 播放數據置換策略流程

算法3：CED緩存替換算法

ReplacePDC（待緩存數據塊i）｛

If（size（i）＜size （PDC的空閑空間）AND Psi＝MAX （total））｛

直接緩存數據塊i；｝

Else｛

Rep（i）＝find（PS）；／／該函數找出預取區中PS值最小的數據塊進行替換；｝

｝

算法流程如圖4所示。

3 仿真實驗

本文利用模擬實驗，通過在相同數量服務器和對等節點的情況下對等節點分別采用本文提出的SDCO算法和傳統的LRU算法的比較來研究SDCO算法的有效性。使用以下3個性能指標來衡量播放質量：①服務器負載；②啟動延遲：指用戶執行播放或拖動操作，到節目開始正常播放之間的延遲時間。③節點緩存命中率。

圖4 CED緩存置換策略流程

本實驗在 Windows 2000，Pentium D 2.80GHz，1GB內存，100Mb／s網絡帶寬的機器上完成。用NS2仿真器來模擬系統中的服務器和對等節點在系統運行中的行為，仿真器由用戶的請求驅動［14－15］。實驗假定有一臺流媒體服務器，其上存有長20個時長為60分鐘左右的AVI影片文件，文件碼率大致為500Kb／s，200個具有緩存能力的客戶端節點，實驗中忽略各種事件的處理時間，不考慮實際網絡因素的影響 （帶寬、擁塞、連接拓撲等）。假設所有節點參數相同而且節點不會中途離開。具體參數如表1所示。

表1 仿真實驗中參數值

圖5－圖8給出了部分實驗結果。實驗證明SDCO緩存策略在啟動延遲、服務器負載和節點緩存命中率方面優于傳統的LRU算法。

圖5為使用SDCO緩存策略和傳統的LRU算法兩種不同策略時服務器負載的變化情況。由圖中可以看出，在服務器負載方面兩種算法相比，SDCO緩存策略更優于傳統LRU算法，在系統運行初期，由于普通節點固定緩存區里還沒有足夠的供其他節點訪問的資源，所以兩種算法區別不大，但是在當前節目組中服務器連接的普通節點數目大于等于C值時，由于所有數據塊在用戶節點中都可以找到，使用SDCO緩存策略優勢得以體現，服務器負載得到了更加明顯的改善。

圖5 節點個數與服務器負載關系

圖6為使用SDCO緩存策略和傳統的LRU算法兩種不同策略的情況下啟動延遲的變化趨勢。縱坐標為進入系統后節點平均啟動時延延遲時間 （單位：秒），橫坐標為系統對等節點數量 （單位：個）。從圖中可以通過比較看出，使用SDCO緩存策略時啟動延遲能得到較好的改善，尤其是在當前節目組中服務器連接的普通節點數目大于等于C值時，啟動延遲時間得到了更加明顯的改善。

圖6 節點個數與啟動延遲關系

圖7 給出了普通用戶端緩存存儲空間分別為50M、100M、150M、200M、250M、300M 時，采用 SDCO 和LRU兩種不同緩存策略情況下的節點網絡利用率對比圖。由于普通節點緩存空間的加大，將使得普通節點可以存儲更多的數據塊來為整個系統提供服務，從而使更多的數據可以在對等節點處下載而減輕了服務器負載壓力和提高了網絡利用率。從圖7可以看出，隨著普通節點端磁盤緩存空間的不斷增加，網絡利用率也在隨之增大。

節點緩存命中率為節點所請求的數據資源在節點自身緩存區中和對等節點中能成功找到的概率。圖8給出了采用SDCO和LRU兩種不同緩存策略情況下的用戶節點個數與節點緩存命中率對比圖。從圖8可以看出，隨著節點個數的不斷增加，節點緩存命中率也在不斷增大。采用SD－CO緩存策略優勢更加明顯，這主要是因為SDCO策略采用了靜態與動態結合的方式，并且在預取區中運用了CED策略綜合評定各項影響因素，從而提高節點緩存命中率。

4 結束語

本文針對基于混合P2P的流媒體點播系統，提出了靜態與動態相結合的SDCO緩存替換算法，靜態是指所有用戶對等節點都必須留有固定緩存區，在成功加入P2P網絡后為其分配固定的緩存內容；而動態指的是用戶對等節點可以在其余的緩存區中根據相應的緩存替換策略進行緩存或替換有利于播放性能和執行VCR操作的數據內容。該算法可使節目數據塊在同一節目對等節點組中的緩存備份量得到合理均衡的分布，從而滿足用戶的高質量播放需求。最后通過仿真實驗證實了該策略的優勢。如何進一步優化3個分區的分配比例來更好地提高系統性能，是我們需要下一步研究的工作。

［1］YIU WPK，JIN X，CHAN SHG.Vmesh：Distributed segment storage for peer－to－peer interactive video streaming ［J］.IEEE Journal on Selected Areas in Communications，2006，25 （9）：1717－1731.

［2］HU Yuqi，HAO Liuyou，SUN Shuang.Cache replacement algorithms for streaming media based on smallest cache value［J］.Computer Engineering and Design，2011，32 （1）：85－88）［胡玉琦，郝留有，孫爽.基于最小價值的流媒體緩存替換算法 ［J］.計算機工程與設計，2011，32 （1）：85－88.］

［3］LEE G J，CHOI C K，CHOI C Y，et al.P2PProxcy：Peer－topeer proxy caching scheme for VOD service ［C］.Sixth International Conference on Computational Intelligence and Multimedia Applications，2007：272－277.

［4］LIU Xuanjia，HUANG Wei，WU Chuan，et al.InstantLeap：An architecture for fast neighbor discovery in large－scale P2PVoD streaming［J］.Multimedia Systems，2010，16 （3）：183－198.

［5］Coyle C L，Heather V.Social networking：Communication revolution or evolution ［J］.Bell Labs Technical Journal，2008，13 （2）：13－18.

［6］YE Tian，DI Wu，Kam Wing Ng.A novel caching mechanism for peer－to－peer based media－on－demand streaming［J］.Journal of Systems Architecture，2008，54 （2）：55－69.

［7］YANG Chuandong，YU Zhenwei，WANG Xinggang.Cache replacement algorithm for hybrid P2Pmedia streaming ［J］.Application Research of Computers，2006，23 （11）：71－73（in Chinese）.［楊傳棟，余鎮危，王興剛.混合P2P流媒體的緩存替換算法研究 ［J］.計算機應用研究，2006，23 （11）：71－73.］

［8］MA Jie.Distributed storage transform method for streaming media cache［J］.Computer Engineering and Design，2010，31（20）：4393－4395 （in Chinese）.［馬杰.流媒體緩存分散式存儲轉換方法 ［J］.計算機工程與設計，2010，31 （20）：4393－4395.］

［9］TAKANO R，YOSHIZAWA Y.Offloading VoD server organized dynamically distributed cache using P2Pdelivery［C］.Tokyo：International Conference on Information Networking，2008：1－5.

［10］CHEN Qi，WU Jie.Research and implementation of buffer management scheme in a P2Pstreaming media VOD system［J］.Computer Applications and Softwar，2009，26 （2）：94－96（in Chinese）.［陳起，吳杰.P2P流媒體點播系統中的緩存管理方案的研究和實現 ［J］.計算機應用與軟件，2009，26 （2）：94－96.］

［11］Spanos D.Asynchronous distributed averaging on communication networks ［J］.IEEE Trans on Networking，2007，15（3）：512－520.

［12］ZHENG Jie，ZHANG Song，QI Jie.Research and simulation for peer selection strategy on P2Pstreaming ［J］.Computer Engineering and Design，2007，28 （22）：5369－5399 （in Chinese）.［鄭婕，張松，齊潔.P2P流媒體節點選擇機制的研究與仿真 ［J］.計算機工程與設計，2007，28 （22）：5369－5399.］

［13］GAO Wen.Recent advances in peer－to－peer media streaming systems ［J］.China Comminications，2006，5 （13）：52－57.

［14］SUN Mingsong，TANG Liang，ZHOU Hongmin.Client disk caching strategy on P2PVoD system ［J］.Computer Engineering，2008，34 （20）：71－73 （in Chinese）.［孫名松，唐亮，周紅敏.P2P點播系統的客戶端磁盤緩存策略 ［J］.計算機工程，2008，34 （20）：71－73.］

［15］ZHANG M，LUO J G，ZHAO L.A peer－to－peer network for live media streaming using apush－pull approach ［C］.Proceedings of ACM Multimedia，2005：287－290.