鄭偉平

(華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣東廣州510631)

數(shù)據(jù)緩存是P2P流媒體系統(tǒng)提升性能的重要手段，通過對(duì)等節(jié)點(diǎn)間共享數(shù)據(jù)可顯著地降低流媒體源服務(wù)器的訪問壓力［1］．其中，考慮數(shù)據(jù)供求平衡是數(shù)據(jù)緩存常用的策略;但僅考慮數(shù)量關(guān)系，忽視了數(shù)據(jù)的分布情況．另一方面，鄰近性(proximity)研究的主要驅(qū)動(dòng)力是實(shí)現(xiàn)P2P數(shù)據(jù)的就近分發(fā)，以減少網(wǎng)絡(luò)區(qū)域之間的數(shù)據(jù)流動(dòng)［2］．目前，P2P鄰近性研究集中在拓?fù)湟恢滦陨希?］，試圖通過鄰居的就近選取來實(shí)現(xiàn)數(shù)據(jù)的就近訪問．在文件共享應(yīng)用中，節(jié)點(diǎn)以下載一個(gè)完整文件為目標(biāo)，對(duì)等節(jié)點(diǎn)間互為數(shù)據(jù)源的可能性很高，拓?fù)湟恢滦运惴軌蜉^好地實(shí)現(xiàn)就近訪問．在流媒體分發(fā)中，流媒體文件的容量大、在線播放等特性導(dǎo)致節(jié)點(diǎn)通常只存儲(chǔ)流媒體對(duì)象的部分?jǐn)?shù)據(jù)，僅靠鄰居選擇很難確保就近訪問．節(jié)點(diǎn)的數(shù)據(jù)存儲(chǔ)情況成為影響數(shù)據(jù)就近訪問的另一關(guān)鍵因素．例如，CHENG 等［4］考慮節(jié)點(diǎn)數(shù)據(jù)存放情況，按播放點(diǎn)的距離將鄰居組織成幾個(gè)同心圓，以增加節(jié)點(diǎn)間數(shù)據(jù)共享的可能性．

為此，本文將數(shù)據(jù)緩存和鄰近性研究結(jié)合起來，利用兩者的互補(bǔ)優(yōu)勢(shì)，提出了一種考慮數(shù)據(jù)分布的P2P流媒體數(shù)據(jù)緩存模型．該模型將網(wǎng)絡(luò)系統(tǒng)劃分為多個(gè)區(qū)域，考慮緩存數(shù)據(jù)在網(wǎng)絡(luò)不同區(qū)域的供求分布情況，節(jié)點(diǎn)根據(jù)數(shù)據(jù)的局部供求關(guān)系進(jìn)行緩存替換，優(yōu)先滿足本區(qū)域內(nèi)節(jié)點(diǎn)的數(shù)據(jù)需求，彌補(bǔ)了傳統(tǒng)鄰近性研究的不足，在鄰居選擇算法的配合下，可更好地達(dá)到就近訪問效果．

1 數(shù)據(jù)緩存模型

網(wǎng)絡(luò)運(yùn)營商可依據(jù)管理權(quán)限、地理分布、產(chǎn)權(quán)歸屬等因素，靜態(tài)或動(dòng)態(tài)地將P2P種群節(jié)點(diǎn)(覆蓋網(wǎng))劃分為多個(gè)區(qū)域．本文采用地理位置作為劃分依據(jù)．假設(shè)區(qū)域內(nèi)部網(wǎng)絡(luò)通信的成本遠(yuǎn)低于區(qū)域間的成本，且節(jié)點(diǎn)具備標(biāo)識(shí)自身所屬區(qū)域的能力，假設(shè)對(duì)等節(jié)點(diǎn)可緩存少量數(shù)據(jù)，但其容量較小，帶寬傳輸能力較弱．為了得到數(shù)據(jù)緩存的分布情況，建立了一種數(shù)據(jù)供求平衡的分布式獲取及數(shù)據(jù)替換模型和算法．在存儲(chǔ)容量固定的前提下，基于數(shù)據(jù)供求平衡的緩存替換優(yōu)化模型可表述如下:

目前多數(shù)流媒體系統(tǒng)采用等長度分段，假設(shè)流媒體文件被等長分為J段，bi和ni分別為第i段數(shù)據(jù)的長度和緩存數(shù)量，S為系統(tǒng)的緩存容量上限．t為緩存替換的決策時(shí)刻;Demand(i，t)表示t時(shí)刻本區(qū)域內(nèi)第i段的需求量;Supply(i，t)表示t時(shí)刻第i段在本區(qū)域的現(xiàn)存副本供應(yīng)量．上述問題是NPC問題，一般用啟發(fā)式算法求解．

文獻(xiàn)［5］-［7］基于數(shù)據(jù)供求關(guān)系提出了緩存替換模型，但本模型考慮不同區(qū)域的供求差異，提出了基于局部供求的緩存替換．文獻(xiàn)［6］提出的SD替換算法，需向根節(jié)點(diǎn)查詢數(shù)據(jù)分片的供求統(tǒng)計(jì)數(shù)據(jù)，如果請(qǐng)求與供應(yīng)的比值較高則保留分片，反之將其替換．文獻(xiàn)［7］則使用數(shù)據(jù)供應(yīng)和需求之間的絕對(duì)差值，對(duì)非熱門數(shù)據(jù)段造成了歧視．本模型使用相對(duì)值的形式(見式(2))，這樣更為合理．與文獻(xiàn)［5］相同，文中使用分布式算法統(tǒng)計(jì)數(shù)據(jù)供求情況，無需集中查詢．

2 數(shù)據(jù)供求度量及計(jì)算

定義1 需求模式:在一段時(shí)間［t，t+Δt］內(nèi)流媒體對(duì)象各分段的訪問概率分布稱為此對(duì)象的需求模式，用需求向量PΔtt表示．

一般采用對(duì)象的歷史流行度來衡量未來需求量，記 fi為第 i段的流行度，PΔtt=［f1，f2，…，fJ］．在緩存決策時(shí)，一般使用當(dāng)前時(shí)刻的需求模式，可將簡記為P．Pi為向量P的第i個(gè)分量，表示第i段(1≤i≤J)的訪問需求量．

定義2 供應(yīng)模式:流媒體對(duì)象各分段在系統(tǒng)各節(jié)點(diǎn)上現(xiàn)存副本的分布情況稱為供應(yīng)模式，反映了對(duì)等節(jié)點(diǎn)對(duì)各數(shù)據(jù)段的供應(yīng)能力，用供應(yīng)向量M表示．

令mi為當(dāng)前系統(tǒng)中第i段數(shù)據(jù)的供應(yīng)副本量．記M為向量 M的第i個(gè)分量，表示第i段的歸一化緩存存量，Supply(i，t)=Mi．

定義3 局部供求模式:將統(tǒng)計(jì)范圍限制在某一區(qū)域AN內(nèi)得到的流媒體對(duì)象需求模式和供應(yīng)模式稱為該對(duì)象在區(qū)域AN上的局部供求模式．

定義4 全局供求模式:流媒體系統(tǒng)覆蓋網(wǎng)全體對(duì)等節(jié)點(diǎn)參與統(tǒng)計(jì)得到的流媒體對(duì)象的需求模式和供應(yīng)模式稱為此對(duì)象的全局供求模式．

2．1 分布式一致性算法

分布式一致性算法［8］是一種分布式均值(averaging)計(jì)算方法，文獻(xiàn)［5］首次應(yīng)用此方法來統(tǒng)計(jì)數(shù)據(jù)段供求情況．該算法假設(shè)系統(tǒng)中每個(gè)節(jié)點(diǎn)都維護(hù)有某個(gè)屬性的本地值，通過分布式方法在全局計(jì)算該屬性平均值．每個(gè)節(jié)點(diǎn)i設(shè)置2個(gè)變量:Zi為屬性的本地值，Xi為屬性的均值狀態(tài)變量．均值計(jì)算過程如下［5，8］:(1)每個(gè)節(jié)點(diǎn)隨機(jī)選擇 N 個(gè)鄰居，按某種規(guī)則確定相互之間的“發(fā)送與接收”關(guān)系，并定期交換均值信息;(2)將節(jié)點(diǎn)上的Xi初始化為Zi，Zi是本地對(duì)屬性的觀察，隨本地觀察而改變，Xi值隨著與鄰居的均值信息交換而變化;(3)發(fā)送者i節(jié)點(diǎn)向接收者j發(fā)送STATE消息，將其維護(hù)的Xi告知j;(4)收到Xi后，j將 Xj更新為 Xj+γj(Xi-Xj)，并以REPLY消息將變化量γj(Xi-Xj)告知i;(5)i收到REPLY后將Xi更新為Xi-γj(Xi-Xj)．

圖1為算法消息交換過程．均值數(shù)據(jù)交換時(shí)需保持總量守恒，通過節(jié)點(diǎn)之間的不斷逼近，最終在全網(wǎng)范圍得到屬性均值．γj為節(jié)點(diǎn)步長，可在本地設(shè)定，0＜γj＜1．該算法具有較好的特性:支持時(shí)變(time-varying)屬性的均值計(jì)算，具有較快的收斂速度，且支持節(jié)點(diǎn)的動(dòng)態(tài)加入/退出［8］，應(yīng)用分布式一致性算法作為數(shù)據(jù)供求模式的求解工具．

圖1 分布式一致性消息交換Figure 1 Message exchange of distributed consensus

2．2 需求模式的計(jì)算

流媒體對(duì)象的需求模式由各段流行度確定．LRU-K［9］是常用的流行度預(yù)測(cè)算法，以過去一段時(shí)間對(duì)象請(qǐng)求的到達(dá)率來估計(jì)未來訪問熱度．記N(t)為t時(shí)刻對(duì)象最近被訪問次數(shù)，N(t)只維護(hù)到K次，0≤ N(t)≤K．T(N(t))為前N(t)次的訪問時(shí)間，對(duì)象的訪問到達(dá)率 ω(t)=N(t)/(t-T(N(t)))．LRU-K算法最初面向數(shù)據(jù)庫應(yīng)用，后來被用于文件緩存、流媒體緩存等領(lǐng)域，很多方案直接將ω(t)作為對(duì)象的流行度，用于預(yù)測(cè)訪問趨勢(shì)．流媒體應(yīng)用具有按序播放的特點(diǎn)，即請(qǐng)求前一段數(shù)據(jù)的節(jié)點(diǎn)時(shí)，會(huì)請(qǐng)求下一段數(shù)據(jù)，鄰近數(shù)據(jù)段的流行度之間存在著“弱蘊(yùn)含”關(guān)系．因此，可將其放在流媒體文件分段序列的上下文中考察其流行度．為此，提出“向后加權(quán)LRU-K”算法:先使用LRU-K算法為各分段計(jì)算ω(t)，然后將該段與前一段的ω(t)加權(quán)和作為該段的流行度，即:

假設(shè)流媒體文件分為J段，每個(gè)節(jié)點(diǎn)i上維護(hù)J個(gè)流行度觀察值，構(gòu)成了本地向量為節(jié)點(diǎn)i上第j段的流行度觀察值．節(jié)點(diǎn)i還須設(shè)置均值狀態(tài)向量．在系統(tǒng)收斂時(shí)，由XPi可算出需求模式向量P，即:

2．2．1 局部需求模式的計(jì)算 為了獲取局部供求模式，節(jié)點(diǎn)只與所屬區(qū)域網(wǎng)絡(luò)內(nèi)的N個(gè)隨機(jī)節(jié)點(diǎn)建立分布式一致性的均值信息交換關(guān)系，假設(shè)系統(tǒng)提供某種識(shí)別節(jié)點(diǎn)所屬區(qū)域的機(jī)制．計(jì)算局部需求模式時(shí)，需對(duì)本地的流行度觀察向量ZPi進(jìn)行處理．由于P2P節(jié)點(diǎn)可為本區(qū)域內(nèi)或區(qū)域外的節(jié)點(diǎn)提供數(shù)據(jù)．為了反映區(qū)域內(nèi)部節(jié)點(diǎn)的真實(shí)數(shù)據(jù)需求，將節(jié)點(diǎn)收到的請(qǐng)求區(qū)分為區(qū)內(nèi)請(qǐng)求與區(qū)外請(qǐng)求．使用LRUK算法計(jì)算各段訪問到達(dá)率ω(t)時(shí)，只統(tǒng)計(jì)區(qū)內(nèi)請(qǐng)求．同時(shí)，將發(fā)向區(qū)外節(jié)點(diǎn)的數(shù)據(jù)請(qǐng)求等效為收到的區(qū)內(nèi)請(qǐng)求，一起累計(jì)到ω(t)上．如圖2所示，a、b、c為同區(qū)域的節(jié)點(diǎn)，d、e節(jié)點(diǎn)在區(qū)域外;箭頭上的數(shù)字表示某一時(shí)間段內(nèi)請(qǐng)求的數(shù)據(jù)段序號(hào)，箭頭表示請(qǐng)求方向，如b節(jié)點(diǎn)向a節(jié)點(diǎn)請(qǐng)求1段和3段．在本實(shí)例中，a節(jié)點(diǎn)在此時(shí)間段內(nèi)將統(tǒng)計(jì)各段的請(qǐng)求到達(dá)次數(shù)，分別為1、2、2、0 次(對(duì)應(yīng)第1-4 段)．

圖2 局部需求模式計(jì)算Figure 2 Computation of regional demand pattern

2．2．2 全局需求模式的計(jì)算 全局需求模式同樣使用LRU-K算法來計(jì)算各段請(qǐng)求到達(dá)率．但與局部模式不同，其分布式一致性鄰居節(jié)點(diǎn)在全系統(tǒng)范圍內(nèi)隨機(jī)選取;且本地流行度觀察向量僅統(tǒng)計(jì)收到的每段數(shù)據(jù)的請(qǐng)求個(gè)數(shù)，不需做特殊處理．

2．3 供應(yīng)模式的計(jì)算

數(shù)據(jù)段的供應(yīng)能力與3個(gè)因素有關(guān):(1)緩存副本的數(shù)量;(2)緩存節(jié)點(diǎn)的上傳帶寬能力;(3)數(shù)據(jù)段的請(qǐng)求響應(yīng)概率．文獻(xiàn)［5］、［6］的研究只考慮了副本數(shù)量．但是，由于節(jié)點(diǎn)帶寬的異構(gòu)性，對(duì)于緩存同個(gè)數(shù)據(jù)段的不同節(jié)點(diǎn)，其上傳帶寬越大，服務(wù)供應(yīng)能力越強(qiáng)．為此需要考慮緩存節(jié)點(diǎn)的帶寬能力．另外，緩存節(jié)點(diǎn)上保存的其它數(shù)據(jù)段的流行度也對(duì)數(shù)據(jù)段的供應(yīng)能力造成影響，即存在各數(shù)據(jù)段對(duì)上傳帶寬的爭用問題．文獻(xiàn)［7］對(duì)此服務(wù)競爭問題進(jìn)行了詳細(xì)的闡述，并給出服務(wù)概率計(jì)算公式，但需要全局信息，計(jì)算難度大．本模型的數(shù)據(jù)供應(yīng)評(píng)估綜合上述3個(gè)因素，并通過分布式一致性算法巧妙地結(jié)合起來．具體如下:

根據(jù)節(jié)點(diǎn)i的緩存情況，Iik=1表示緩存第k段數(shù)據(jù)，Iik=0表示不緩存;當(dāng)節(jié)點(diǎn)沒有整段緩存數(shù)據(jù)時(shí)，Iik=(節(jié)點(diǎn)緩存第k段的數(shù)據(jù)塊數(shù)/數(shù)據(jù)段的總塊數(shù))．BWiup為節(jié)點(diǎn)平均上傳帶寬;P為需求模式向量．Fi為節(jié)點(diǎn)i緩存的數(shù)據(jù)段集合．節(jié)點(diǎn)i維護(hù)1個(gè)本地緩存狀態(tài)向量，通過分布式一致性算法計(jì)算和維護(hù)均值向量由 ZMi定義式可知，本文對(duì)數(shù)據(jù)供應(yīng)量的計(jì)算同時(shí)考慮緩存段數(shù)Iik、節(jié)點(diǎn)上傳帶寬能力BWiup和節(jié)點(diǎn)對(duì)不同請(qǐng)求的服務(wù)概率)，更真實(shí)地反映了系統(tǒng)的數(shù)據(jù)供應(yīng)服務(wù)能力，避免了額外的信息收集機(jī)制和計(jì)算開銷．

2．3．1 局部供應(yīng)模式的計(jì)算 局部供應(yīng)模式的計(jì)算較簡單:節(jié)點(diǎn)與區(qū)域內(nèi)部節(jié)點(diǎn)建立拓?fù)潢P(guān)系后，根據(jù)本地的數(shù)據(jù)段緩存和帶寬能力等情況設(shè)置和更新本地向量ZMi，并定期和鄰居交換均值信息，在系統(tǒng)收斂時(shí)，可用XMi計(jì)算供應(yīng)模式:

2．3．2 全局供應(yīng)模式的計(jì)算 全局供應(yīng)模式的計(jì)算過程基本與局部供應(yīng)模式一致，區(qū)別在于其分布式一致性算法鄰居在全系統(tǒng)范圍內(nèi)隨機(jī)選?。?/p>

3 基于局部供求平衡的數(shù)據(jù)緩存管理

全局供求模式與局部供求模式存在差異性．當(dāng)應(yīng)用到個(gè)體區(qū)域時(shí)，全局模式不能準(zhǔn)確代表該區(qū)域的供求關(guān)系．而局部模式是在感知數(shù)據(jù)存放位置的基礎(chǔ)上統(tǒng)計(jì)的供求關(guān)系．故此，為了實(shí)現(xiàn)就近訪問，本節(jié)提出了基于局部供求模式的緩存替換算法，在節(jié)點(diǎn)播放完數(shù)據(jù)塊b后，若本地有存儲(chǔ)空間則直接緩存，否則調(diào)用替換過程DoReplace，其偽代碼如下:記錄本地已緩存的數(shù)據(jù)段id到集合S中

int m=Arg MiniSφ(i，t);∥求 φ 值最小的數(shù)據(jù)段id

int n=get_Segment_id(b);∥求數(shù)據(jù)塊b所在數(shù)據(jù)段的id

if(n=m)不緩存數(shù)據(jù)塊b;

else從本地第m段中隨機(jī)選擇一塊將其替換為b;

更新本地緩存狀態(tài)ZM;∥為下輪的分布式一致性數(shù)據(jù)交換做準(zhǔn)備

}

4 結(jié)果與評(píng)價(jià)

使用NS2仿真的方法驗(yàn)證算法有效性．系統(tǒng)使用GT-ITM生成920個(gè)節(jié)點(diǎn)(1個(gè)transit域+3個(gè)stub域)，0-19號(hào)節(jié)點(diǎn)為核心交換節(jié)點(diǎn)，20-919號(hào)為普通節(jié)點(diǎn)．設(shè)置A、B、C 3個(gè)區(qū)域，分別在20-319號(hào)、320-619號(hào)以及620-919號(hào)節(jié)點(diǎn)中隨機(jī)選取，各區(qū)節(jié)點(diǎn)分別處于同個(gè)stub域里．各區(qū)節(jié)點(diǎn)的帶寬配置分3 類:(1)上行 512 Kbps、下行 1 Mbps，占 60%;(2)上行1 Mbps、下行1 Mbps，占30%;(3)上行2 Mbps、下行2 Mbps，占10%．系統(tǒng)模擬了1個(gè)流媒體服務(wù)器，上傳帶寬為50 Mbps，在緊急窗口內(nèi)的數(shù)據(jù)才能向流媒體服務(wù)器請(qǐng)求．模擬的流媒體文件長度為30 min，320 Kbps比特率，按每6 s等長分段，每1 s數(shù)據(jù)封裝為40個(gè)包．普通節(jié)點(diǎn)可緩存20段數(shù)據(jù)．采用位置感知的鄰居選擇算法，80%的鄰居在區(qū)域內(nèi)選擇，其余鄰居從區(qū)域外挑選．向后加權(quán)LRU-K算法中，K=8，α=0．8．分布式一致算法中，節(jié)點(diǎn)連接度為4，步長γ為0．2，為了控制消息傳輸成本，算法每隔1 s才與鄰居交換均值信息．實(shí)驗(yàn)分別從A、B、C 3區(qū)隨機(jī)選取50、100、150和200個(gè)節(jié)點(diǎn)，在這4種規(guī)模下，各種方案運(yùn)行10次，取性能平均值作比較．為了評(píng)價(jià)提出的基于局部供求平衡的數(shù)據(jù)替換策略(POP_LOCAL)，實(shí)驗(yàn)還實(shí)現(xiàn)了以下3種緩存策略:隨機(jī)替換策略(Random)、按序替換策略(Sequence)及基于全局供求平衡的替換策略(POP_GLOBAL)．

4．1 播放流暢度

圖3是節(jié)點(diǎn)規(guī)模為600節(jié)點(diǎn)時(shí)4種緩存方案的播放流暢度累計(jì)分布函數(shù)(CDF)．播放流暢度定義為能及時(shí)下載(未超過播放時(shí)限)的數(shù)據(jù)塊數(shù)占下載總塊數(shù)的比率．Sequence替換方式最差，Random次之;基于供求關(guān)系的緩存機(jī)制播放流暢度均超過90%，其播放質(zhì)量均優(yōu)于Random和Sequence機(jī)制．其中，POP_GLOBAL策略下，有90%的節(jié)點(diǎn)播放流暢度介于93% ～97%之間;而POP_LOCAL策略大大提高了用戶播放質(zhì)量，所有用戶的播放流暢度在97%以上．因此，在節(jié)點(diǎn)規(guī)模較大的情況下，POP_LOCAL策略在播放質(zhì)量方面優(yōu)于POP_GLOBAL策略．即:局部供求模式的緩存替換策略比全局供求模式的更合理．

圖3 不同方案下的播放流暢度Figure 3 Playback smooth index of different schemes

4．2 服務(wù)器負(fù)載

使用流媒體服務(wù)器的訪問峰值做為衡量服務(wù)器負(fù)載的指標(biāo)．在4種節(jié)點(diǎn)規(guī)模下，Random策略和Sequence策略的性能最差，Sequence策略的服務(wù)負(fù)載比Random的大．在小節(jié)點(diǎn)規(guī)模(150個(gè))情況下，各種策略的服務(wù)負(fù)載相差不大:Sequence策略最差為 8．02 Mbps，POP_GLOBAL 最好為 6．9 Mbps．小節(jié)點(diǎn)規(guī)模情況下同區(qū)域內(nèi)的節(jié)點(diǎn)無法提供節(jié)點(diǎn)播放所需的數(shù)據(jù)，需從其它區(qū)域下載數(shù)據(jù)，從系統(tǒng)全局出發(fā)替換數(shù)據(jù)可獲得更好的性能，因此POP_GLOBAL的性能最優(yōu)．隨著節(jié)點(diǎn)規(guī)模增大，POP_LOCAL策略的優(yōu)勢(shì)越來越明顯．600個(gè)節(jié)點(diǎn)時(shí)，POP_LOCAL的服務(wù)負(fù)載為12．43 Mbps，比 POP_GLOBAL的負(fù)載小1．17 Mbps．

4．3 數(shù)據(jù)自供應(yīng)能力

定義“數(shù)據(jù)自供應(yīng)指數(shù)”如下:數(shù)據(jù)自供應(yīng)指數(shù)=系統(tǒng)中從同區(qū)域下載的數(shù)據(jù)總塊數(shù)/系統(tǒng)中由對(duì)等交換得到(非流媒體源服務(wù)器提供)的數(shù)據(jù)總塊數(shù)．指數(shù)值越大，系統(tǒng)數(shù)據(jù)自供應(yīng)能力越強(qiáng)，區(qū)域間數(shù)據(jù)流動(dòng)量越少，網(wǎng)絡(luò)傳輸成本越低．

表1給出不同緩存方案的數(shù)據(jù)自供應(yīng)能力比較情況．從趨勢(shì)來看，任一種緩存策略的數(shù)據(jù)自供應(yīng)能力都隨節(jié)點(diǎn)規(guī)模的增大而增強(qiáng)．因?yàn)?，區(qū)域節(jié)點(diǎn)數(shù)量增多，則在內(nèi)部找到合適數(shù)據(jù)源的概率增大，數(shù)據(jù)流動(dòng)性減弱．從策略比較來看，Sequence策略的數(shù)據(jù)自供應(yīng)能力最差;Random次之;而POP_LOCAL能夠顯著提高系統(tǒng)數(shù)據(jù)自供應(yīng)能力，多數(shù)情況下性能優(yōu)于POP_GLOBAL(節(jié)點(diǎn)規(guī)模為150個(gè)時(shí)例外)．在600個(gè)節(jié)點(diǎn)的規(guī)模下，POP_LOCAL的數(shù)據(jù)供應(yīng)指數(shù)高達(dá)0．32，比POP_GLOBAL高出6%．可見，在適當(dāng)?shù)泥従舆x擇算法的配合下，在局部維持?jǐn)?shù)據(jù)供求平衡，可將數(shù)據(jù)分發(fā)過程更多地控制在網(wǎng)絡(luò)局部．

表1 不同方案下的數(shù)據(jù)供應(yīng)指數(shù)Table 1 Self sufficiency ratio of different s chemes

5 結(jié)語

在P2P流媒體分發(fā)中，單純使用拓?fù)湟恢滦运惴o法保證數(shù)據(jù)就近訪問．而基于數(shù)據(jù)供求關(guān)系的傳統(tǒng)緩存替換算法僅考慮數(shù)據(jù)供求數(shù)量關(guān)系，忽視了數(shù)據(jù)分布位置因素．為此，本文提出了基于局部數(shù)據(jù)供求平衡的緩存模型，利用分布式一致性算法作為數(shù)據(jù)供求統(tǒng)計(jì)工具，給出了該模型的分布式求解方案．仿真實(shí)驗(yàn)表明，基于局部供求平衡的緩存策略能有效提升播放質(zhì)量，降低不同區(qū)域間的數(shù)據(jù)流量．在節(jié)點(diǎn)規(guī)模較大的情況下，該策略的性能優(yōu)于基于全局供求平衡的替換策略．研究如何降低分布式統(tǒng)計(jì)供求模式的網(wǎng)絡(luò)開銷，以及不同的區(qū)域規(guī)模對(duì)緩存性能的影響將作為后續(xù)的研究重點(diǎn)．

［1］SHEN Z J，LUO J，ROGER Z，etal．Peer-to-peermedia streaming:Insights and new developments［J］．P IEEE，2011，99(12):2087-2088．

［2］KARAGIANNIS T，RODRIGUEZ P，PAPAGIANNAKI K．Should internet service providers fear peer assisted content distribution［C］∥ACM Internet Measurement Conference，New Orleans，LA，2005．

［3］FIORESE A，SIMOESP，BOAVIDA F．Peer selection in P2P service overlays using geographical location criteria［C］∥12th International Conference on Computational Science and Its Applications，Salvador de Bahia，Brazil，2012:234-248．

［4］CHENG B，JIN H，LIAO X F．RINDY:A ring based overlay network for peer to peer on demand streaming［C］∥Proceedings of Ubiquitous Intelligence and Computing，Wuhan，2006:1048-1058．

［5］YIUW P K，JIN X，CHAN SH G．VMesh:Distributed segment storage for peer-to-peer interactive video streaming［J］．IEEE JSel Area Comm，2007，25(9):1717-1731．

［6］陳剛，張偉文，吳國新．P2P流媒體Cache的置換算法［J］．計(jì)算機(jī)研究與發(fā)展，2007，44(11):1857-1865．

［7］WU J H，LI B C．Keep Cache replacement simple in Peer-Assisted VoD systems［C］∥P IEEE Infocom 2009 Mini-Conference，Rio de Janeiro，Brazil，2009．

［8］MEHYAR M，SPANOSD，PONGSAJAPAN J，et al．A-synchronous distributed averaging on communication networks［J］．IEEE/ACM Transactions on Networking，2007，15(3):512-520．

［9］O'NEIL E J，O'NEIL P E，WEIKUM G．The LRU-K page replacement algorithm for database disk buffering［C］∥ACM SIGMOD．Washington D．C．，1993:297-306．