孫 昕，陳德運

（1.哈爾濱醫(yī)科大學(xué) 基礎(chǔ)醫(yī)學(xué)院，黑龍江 哈爾濱150081；2.哈爾濱理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱150080）

0 引 言

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

1 系統(tǒng)結(jié)構(gòu)

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

圖1 系統(tǒng)結(jié)構(gòu)

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

根據(jù)普通節(jié)點的節(jié)目請求，服務(wù)器將其分配到所有觀看該節(jié)目的節(jié)點所組成的組，普通節(jié)點先在該組內(nèi)查找其所請求節(jié)目塊，若找到則由組內(nèi)節(jié)點提供服務(wù)，否則由服務(wù)器提供服務(wù)。各節(jié)點要邊觀看邊下載部分?jǐn)?shù)據(jù)塊［7］，以便能為其他請求節(jié)點提供服務(wù)，從而減輕服務(wù)器壓力［8］，這一點也正是將P2P技術(shù)融入VOD系統(tǒng)的優(yōu)越性的主要體現(xiàn)。

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

2 靜態(tài)與動態(tài)結(jié)合的緩存替換算法

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

2.1 普通節(jié)點緩存區(qū)的劃分

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

2.1.1 固定指派區(qū)

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

令參數(shù)

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

2.1.2 當(dāng)前播放區(qū)

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

2.1.3 預(yù)取區(qū)

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

該區(qū)相應(yīng)的算法為CED替換算法。

2.2 SDCO緩存替換算法

算法1：靜態(tài)數(shù)據(jù)更新算法。

UpdateFDC（待緩存數(shù)據(jù)塊i）｛

If（J＜＝C）｛服務(wù)器直接分配數(shù)據(jù)塊；｝

Else｛

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

緩存剛剛播過的數(shù)據(jù)塊i；｝

Else｛

Rep （i）＝find（FDC）；／／用數(shù)據(jù)塊i來替換固定區(qū)中最久未被使用數(shù)據(jù)塊；｝

｝

算法流程如圖2所示。

算法2：播放數(shù)據(jù)替換算法

ReplaceCPC（待緩存數(shù)據(jù)塊i）｛

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

直接緩存數(shù)據(jù)塊i；｝

Else｛

Rep （i）＝find （CPC）；／／用數(shù)據(jù)塊i替換播放區(qū)中最久未使用的數(shù)據(jù)塊；｝

圖2 靜態(tài)數(shù)據(jù)更新策略流程

｝

算法流程如圖3所示。

圖3 播放數(shù)據(jù)置換策略流程

算法3：CED緩存替換算法

ReplacePDC（待緩存數(shù)據(jù)塊i）｛

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

直接緩存數(shù)據(jù)塊i；｝

Else｛

Rep（i）＝find（PS）；／／該函數(shù)找出預(yù)取區(qū)中PS值最小的數(shù)據(jù)塊進行替換；｝

｝

算法流程如圖4所示。

3 仿真實驗

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

圖4 CED緩存置換策略流程

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

表1 仿真實驗中參數(shù)值

圖5－圖8給出了部分實驗結(jié)果。實驗證明SDCO緩存策略在啟動延遲、服務(wù)器負(fù)載和節(jié)點緩存命中率方面優(yōu)于傳統(tǒng)的LRU算法。

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

圖5 節(jié)點個數(shù)與服務(wù)器負(fù)載關(guān)系

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

圖6 節(jié)點個數(shù)與啟動延遲關(guān)系

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

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

4 結(jié)束語

本文針對基于混合P2P的流媒體點播系統(tǒng)，提出了靜態(tài)與動態(tài)相結(jié)合的SDCO緩存替換算法，靜態(tài)是指所有用戶對等節(jié)點都必須留有固定緩存區(qū)，在成功加入P2P網(wǎng)絡(luò)后為其分配固定的緩存內(nèi)容；而動態(tài)指的是用戶對等節(jié)點可以在其余的緩存區(qū)中根據(jù)相應(yīng)的緩存替換策略進行緩存或替換有利于播放性能和執(zhí)行VCR操作的數(shù)據(jù)內(nèi)容。該算法可使節(jié)目數(shù)據(jù)塊在同一節(jié)目對等節(jié)點組中的緩存?zhèn)浞萘康玫胶侠砭獾姆植?，從而滿足用戶的高質(zhì)量播放需求。最后通過仿真實驗證實了該策略的優(yōu)勢。如何進一步優(yōu)化3個分區(qū)的分配比例來更好地提高系統(tǒng)性能，是我們需要下一步研究的工作。

［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］.計算機工程與設(shè)計，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）.［楊傳棟，余鎮(zhèn)危，王興剛.混合P2P流媒體的緩存替換算法研究 ［J］.計算機應(yīng)用研究，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）.［馬杰.流媒體緩存分散式存儲轉(zhuǎn)換方法 ［J］.計算機工程與設(shè)計，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流媒體點播系統(tǒng)中的緩存管理方案的研究和實現(xiàn) ［J］.計算機應(yīng)用與軟件，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流媒體節(jié)點選擇機制的研究與仿真 ［J］.計算機工程與設(shè)計，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點播系統(tǒng)的客戶端磁盤緩存策略 ［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.