張學圈 張紅躍 熊章學 王紅青 張鵬遠 牛志雷 劉家軍

(1.許繼電氣股份有限公司，河南 許昌 461000;2.華東電力試驗研究院有限公司，上海 200437)

緩存技術(shù)是計算機中所普遍采用的基本技術(shù)之一，并且緩存技術(shù)是P2P流媒體技術(shù)得以應(yīng)用的基礎(chǔ)。P2P流媒體服務(wù)的優(yōu)點在于通過Peer節(jié)點緩存部分數(shù)據(jù)段，以此在P2P網(wǎng)絡(luò)中提供更多片源信息，同時通過Peer節(jié)點貢獻的上載能力，來達到對等節(jié)點間的相互服務(wù)，從而降低服務(wù)器的壓力，提高系統(tǒng)服務(wù)容量。同時通過緩存技術(shù)也可以有效的應(yīng)對P2P網(wǎng)絡(luò)結(jié)構(gòu)的不確定性，節(jié)點頻繁加入、退出網(wǎng)絡(luò)等因素的影響，為流媒體提供穩(wěn)定的服務(wù)。

雖然通過擴大存儲空間可以有效地提供服務(wù)片源，但是P2P流媒體的數(shù)據(jù)緩存還存在以下問題：(1)緩存空間是分布式的，系統(tǒng)的緩存空間分布在加入到系統(tǒng)的不同對等節(jié)點上;(2)基于buffer-forwar方式下，各Peer節(jié)點的存儲空間是有限的;(3)由于Peer節(jié)點的不確定性，必然導(dǎo)致緩存空間的總體容量的不確定，它隨加入到系統(tǒng)中對等節(jié)點的數(shù)量變化而變化;(4)由于各對等節(jié)點間的松耦合特性，系統(tǒng)的緩存空間難以統(tǒng)一管理;(5)系統(tǒng)對同一流媒體內(nèi)容一般均緩存有多個副本，其副本數(shù)量應(yīng)與其流行度相關(guān)。因此如何解決上述問題將直接影響到P2P流媒體服務(wù)的性能和服務(wù)的可靠性。

針對以上幾種情況，需要針對無效的資源進行替換，調(diào)整出更多緩存資源用于緩存稀缺資源。從而從整體達到需求和供給的平衡。減輕服務(wù)器壓力，提升系統(tǒng)服務(wù)性能。通過以上問題分析，本文所述的媒體數(shù)據(jù)段替換策略可以采用GLFU-PVDP算法，即通過PVDP算法獲取全局信息，對本地Peer節(jié)點，結(jié)合全局信息和本地LFU信息做出緩存替換裁決，從而獲取資源的最佳使用。

1 基于全局信息的緩存替換算法

根據(jù)緩存中數(shù)據(jù)的屬性，對緩存的數(shù)據(jù)段進行了如下分類，如圖1所示。

圖1 數(shù)據(jù)段分類

(1)過期數(shù)據(jù)段：緩存的數(shù)據(jù)段，其已經(jīng)經(jīng)過Peer節(jié)點播放。Peer節(jié)點即使刪除該數(shù)據(jù)段也不會造成本Peer節(jié)點播放無法異常。

(2)待播放數(shù)據(jù)段：緩存的數(shù)據(jù)段，但是Peer節(jié)點還沒有播放此部分數(shù)據(jù)段，如果刪除該部分數(shù)據(jù)段會造成Peer節(jié)點播放異常。

(3)正在播放的數(shù)據(jù)段(PPS)：緩存的數(shù)據(jù)段，Peer節(jié)點正在播放此數(shù)據(jù)段，無法刪除該數(shù)據(jù)段。

(4)待下載數(shù)據(jù)段：還沒有進入緩存管理的數(shù)據(jù)段，同時也是Peer節(jié)點沒有播放過的數(shù)據(jù)段，Peer節(jié)點需要從其它Peer節(jié)點或者服務(wù)器下載該部分數(shù)據(jù)段。通常數(shù)據(jù)段編號是當前播放位置PPS的增序。

其中過期數(shù)據(jù)段，待播放數(shù)據(jù)段和正在播放的數(shù)據(jù)段的數(shù)據(jù)段可以向其它Peer節(jié)點提供服務(wù)。而過期數(shù)據(jù)段可以作為緩存替換候選集合。

本文基于分級覆蓋網(wǎng)絡(luò)組織方式。針對超級節(jié)點，需要周期統(tǒng)計通過超級節(jié)點轉(zhuǎn)發(fā)到服務(wù)器的媒體服務(wù)請求，考慮到文中的優(yōu)先級定義，在對服務(wù)器請求的同時需要進行優(yōu)先級的統(tǒng)計。同時超級節(jié)點之間需要周期交互獲取全局信息。在Peer節(jié)點周期上報和請求數(shù)據(jù)服務(wù)的回應(yīng)中，給出該Peer節(jié)點緩存數(shù)據(jù)的稀缺度評價，用于Peer節(jié)點進行數(shù)據(jù)替換的依據(jù)。考慮到服務(wù)的提供者是優(yōu)選本覆蓋，隨后是其它覆蓋網(wǎng)絡(luò)提供，因而數(shù)據(jù)段的稀缺度評價優(yōu)先考慮本覆蓋的稀缺度，隨后考慮其它覆蓋的稀缺度。具體定義參見公式(1-1)，

式中：

LRi——本覆蓋網(wǎng)絡(luò)內(nèi)數(shù)據(jù)段i的的稀缺度;

ORi——其它覆蓋網(wǎng)絡(luò)同步的稀缺度信息;

β——調(diào)整因子，用于確認稀缺度傾向哪部分信息。

式中：

Rqi——單位時間內(nèi)向服務(wù)器發(fā)起的數(shù)據(jù)段i的訪問頻率;

Rpi——請求數(shù)據(jù)段i的總計優(yōu)先級;

δ——優(yōu)先級調(diào)整因子。

式中：

Oqi——單位時間內(nèi)同步的其它覆蓋網(wǎng)絡(luò)向服務(wù)器發(fā)起的數(shù)據(jù)段i的訪問頻率;

Opi——其它覆蓋網(wǎng)絡(luò)請求數(shù)據(jù)段i的總計優(yōu)先級。

考慮到潮汐效應(yīng)，不同區(qū)域的點播集中程度不同，同時考慮到網(wǎng)絡(luò)代價，超級節(jié)點間的數(shù)據(jù)同步僅按域進行，不進行域間的數(shù)據(jù)同步，對于全局數(shù)據(jù)的有效性也需要考慮，原因如下：根據(jù)潮汐效應(yīng)，針對不同的域可能訪問存在突發(fā)性和集中性，而全局信息如果僅僅通過簡單的加法運算，有可能存在情況是該數(shù)據(jù)段在域1是熱媒體數(shù)據(jù)段，在域2則不一定是熱媒體數(shù)據(jù)段。如果此時將域1的訪問統(tǒng)計也平均到域2，則域2會提供部分額外資源用于服務(wù)數(shù)據(jù)段A，但是本域內(nèi)訪問并不高，而過多地向域1的Peer提供服務(wù)，導(dǎo)致網(wǎng)絡(luò)資源的浪費。

對于數(shù)據(jù)段的替換發(fā)生在以下幾種情況：(1)資源利用率不高的時候，即本地緩存的數(shù)據(jù)段并沒有為其它Peer節(jié)點服務(wù)時，Peer節(jié)點可以替換出沒有參與服務(wù)的數(shù)據(jù)段用于提前下載將要播出的數(shù)據(jù)段。(2)在資源利用率高的情況下，需要Peer節(jié)點根據(jù)待下載數(shù)據(jù)段的deadline來確定是否進行數(shù)據(jù)替換，即每個候選替換數(shù)據(jù)段均有較高時候，就需要根據(jù)待下載數(shù)據(jù)段的此次下載是否會影響到Peer節(jié)點當前服務(wù)情況而定了。

如果Peer節(jié)點判定以上情況發(fā)生時及需要進行數(shù)據(jù)段替換選擇，替換依據(jù)是結(jié)合本地統(tǒng)計信息LFU以及超級節(jié)點反饋的稀缺度評價值進行替換。替換只針對過期數(shù)據(jù)段，替換依據(jù)公式(1-4)：

式中：

fi——緩存數(shù)據(jù)段保留等級;

Dfi——單位時間內(nèi)數(shù)據(jù)段i的訪問頻率;

Ri——從超級節(jié)點同步的數(shù)據(jù)段稀缺度;

θ——稀缺度調(diào)整因子。

2 算法實現(xiàn)

2.1 稀缺度統(tǒng)計

在PVDP算法基礎(chǔ)上，超級節(jié)點為每個數(shù)據(jù)段設(shè)置稀缺標志 A，同時設(shè)置屬性 I(Lcount-，Lsumprior，Ocount，Osumprior)，其中Lcount記錄單位時間內(nèi)超級節(jié)點向服務(wù)器轉(zhuǎn)發(fā)的數(shù)據(jù)段i的服務(wù)請求，Lsumprior記錄轉(zhuǎn)發(fā)的請求優(yōu)先級和;Ocount記錄單位時間內(nèi)同步的其它覆蓋網(wǎng)絡(luò)轉(zhuǎn)發(fā)的數(shù)據(jù)段i的服務(wù)請求，Osumprior記錄同步的的請求優(yōu)先級和。超級節(jié)點每接收到其它超級節(jié)點的廣播信息后，累加(Ocount，Osumprior)信息。經(jīng)過單位時間t，超級節(jié)點按照公式(6-2)計算每個數(shù)據(jù)段的稀缺度，并更新數(shù)據(jù)段的稀缺標志A。同時向域內(nèi)其它超級節(jié)點廣播該覆蓋內(nèi)的每個數(shù)據(jù)段的(Lcount，Lsumprior)信息，隨后設(shè)置(Lcount，Lsumprior，Ocount，Osumprior)=(0，0，0，0)。

當超級節(jié)點收到Peer節(jié)點的資源上報Peer節(jié)點能力信息后，根據(jù)算法可知，如 Peer緩存數(shù)據(jù)段(1，2，3，4，5)，其目前可支持上行帶寬剩余為可并行支持1個Peer數(shù)據(jù)的上載，該Peer上報其能力為((1，2，3，4，5)，1)。則超級節(jié)點會將數(shù)據(jù)段(1，2，3，4，5)的稀缺資源標志 A 信息反饋給 Peer節(jié)點((1，A1)，(2，A2)，(3，A2)，(4，A2)，(5，A2))。

2.2 Peer節(jié)點替換無效緩存

當接收到超級節(jié)點的同步信息和緩存數(shù)據(jù)段的稀缺信息后，Peer節(jié)點根據(jù)反饋的信息進行數(shù)據(jù)段服務(wù)的選擇。

(1)首先檢查Peer是否有空閑緩存，如果有則可以直接根據(jù)超級節(jié)點反饋的服務(wù)候選列表進行資源選擇。否則進行iiI

(2)根據(jù)公式4〉對候選替換數(shù)據(jù)段進行排序。

(3)如果存在數(shù)據(jù)段替換fi=0，則數(shù)據(jù)段i被替換。如果不存在數(shù)據(jù)段fi=0則進行iv。

(4)如果該數(shù)據(jù)段的deadline〉ω則表明該數(shù)據(jù)段不是緊急數(shù)據(jù)，在本周期內(nèi)可以不進行下載，因而取消該次數(shù)據(jù)服務(wù)段的請求。算法結(jié)束。否則進行v。

(5)選擇數(shù)據(jù)段替換排序最后的數(shù)據(jù)緩存釋放資源，進行數(shù)據(jù)服務(wù)請求。(6)繼續(xù)選擇一個待下載的數(shù)據(jù)段進行v。具體算法如圖2所示。

圖1 緩存替換算法

3 仿真分析

為了有效地驗證本文提出的算法，我們按照本文提出的模型構(gòu)造系統(tǒng)仿真模型進行評估。本章節(jié)就系統(tǒng)仿真模型進行介紹和結(jié)果分析。

3.1 仿真模型與參數(shù)設(shè)置

仿真模型中我們認為每個peer節(jié)點的請求媒體服務(wù)是獨立的，系統(tǒng)仿真3類Peer的到達，其節(jié)點特性如下：上行和下行帶寬分別為{1000Kbps，256Kbps}，{2000Kbps，512Kbps}，{4000Kbps，1024Kbps}，并且這 3 類節(jié)點按照 0.35，0.4 和 0.25的比率分布，所有Peer節(jié)點分布在3個域中。Peer請求媒體服務(wù)按照Poisson分布，到達概率為λ=10/s;為了對比驗證服務(wù)器的負載，系統(tǒng)中設(shè)置一臺媒體服務(wù)器。系統(tǒng)中總計有100個媒體文件，媒體文件的熱度符合Zipf-like分布，其中θ=0.271。媒體文件播放速率按照128Kbps，時長100分鐘，數(shù)據(jù)按照30S分段，peer與超級節(jié)點的交互周期也是30S，超級節(jié)點間數(shù)據(jù)同步也是30S，數(shù)據(jù)采集按照每5分鐘一次的粒度進行數(shù)據(jù)采集;每個Peer緩存空間為11個原始數(shù)據(jù)段的存儲空間。稀缺度調(diào)整因子θ=0.2，優(yōu)先級調(diào)整因子δ=0.2，本地和外部覆蓋調(diào)整因子β=0.4，即優(yōu)先考慮本覆蓋的資源需求。

3.2 仿真結(jié)果分析

仿真試驗中我們分別從控制信息規(guī)模，服務(wù)延遲，VCR的影響，服務(wù)器負載方面仿真和分析，結(jié)果如下。

3.2.1 控制開銷

針對控制信息我們按照5分鐘的采集粒度進行統(tǒng)計，控制信息包括peer向超級節(jié)點上報的信息、后續(xù)對數(shù)據(jù)提供者的檢索信息以及服務(wù)器間，服務(wù)器與超級節(jié)點間的同步信息和不同覆蓋網(wǎng)絡(luò)間的廣播信息?？紤]到本文是按照30S的周期進行數(shù)據(jù)的同步，檢索等服務(wù)請求，同時控制信息的開銷是與節(jié)點規(guī)模相關(guān)，因此我們將統(tǒng)計結(jié)果折算為每30S每Peer的開銷。圖3給出了在不同節(jié)點規(guī)模情況下本算法在系統(tǒng)正常狀態(tài)下以及支持VCR操作情況下的統(tǒng)計結(jié)果，可以看出本算法較PVDP算法增加了系統(tǒng)開銷，但是平均到每個節(jié)點的控制面數(shù)據(jù)開銷較PVDP算法而言增加并不明顯，但節(jié)點平均開銷并不大。

圖2 控制開銷

3.2.2 服務(wù)延遲

針對緩存數(shù)據(jù)替換的有效性，我們通過Peer節(jié)點檢索服務(wù)數(shù)據(jù)節(jié)點的命中次數(shù)進行評測，即需要幾個hop才可以最終確定服務(wù)提供者。理想情況下Peer節(jié)點緩存了較多的熱點數(shù)據(jù)段，則應(yīng)當有較高的檢索命中率，即通過幾個小的hop交互即可確定服務(wù)提供者。同時針對VCR測試，考慮到用戶的行為通常是將播放位置調(diào)整到熱點數(shù)據(jù)段，即熱點數(shù)據(jù)段的點播較為集中，也是VCR動作的目的調(diào)整位置。因而在對系統(tǒng)對VCR支持情況的測試中不同于第3章的方針測試方式，隨機調(diào)整用戶的播放位置，而是設(shè)置幾個熱點數(shù)據(jù)段位置，隨機選擇Peer節(jié)點觸發(fā)VCR操作，而VCR動作調(diào)整的目標位置隨機地落在某個設(shè)定的熱點數(shù)據(jù)段位置。為了測試的簡單，針對每個媒體數(shù)據(jù)文件我們設(shè)置3個熱點播放位置，數(shù)據(jù)段10，數(shù)據(jù)段50和數(shù)據(jù)段90的位置。根據(jù)以上設(shè)置，我們對GFLU-PVDP算法和PVDP算法，以及P2VoD算法進行了仿真比較。從圖4和圖5中可以看出由于本文對熱點數(shù)據(jù)段進行了針對性緩存，在Peer節(jié)點存儲多的副本，從而有效地提高了熱點數(shù)據(jù)檢索的成功率，降低了VCR帶來的服務(wù)延遲。

3.2.3 基于優(yōu)先級的接入控制和服務(wù)器壓力

針對服務(wù)器負載的仿真試驗結(jié)果如圖6所示?？梢钥闯鯣FLU-PVDP算法中服務(wù)器的負載遠低于PVDP算法，其原因在于GFLU-LCSS算法中根據(jù)超級節(jié)點間的廣播信息，針對服務(wù)器服務(wù)的資源(文中認為的稀缺資源)進行了針對性的緩存，有效地減輕了服務(wù)器的壓力。同時在GFLU-PVDP算法中結(jié)合待下載數(shù)據(jù)段i的deadline限制了Peer節(jié)點的提前下載量，并且保證了在Peer節(jié)點間提供了更多的服務(wù)候選資源，從而在相同系統(tǒng)規(guī)模的情況下，通過GFLU-PVDP緩存替換算法有效地減輕服務(wù)器負載，同時系統(tǒng)可以獲得更大的服務(wù)能力。

圖5 服務(wù)器壓力

4 結(jié)論

GLFU-PVDP緩存替換算法，該算法中的超級節(jié)點不僅需要同步可用資源信息，還要負責周期統(tǒng)計本覆蓋的的稀缺資源，并通過覆蓋超級節(jié)點間的周期廣播獲取全局稀缺資源信息，各Peer節(jié)點在此信息基礎(chǔ)上結(jié)合本地緩存數(shù)據(jù)服務(wù)頻率進行數(shù)據(jù)段緩存的替換，來提高緩存數(shù)據(jù)的命中率，從而做到Peer節(jié)點的數(shù)據(jù)段替換，既兼顧全局稀缺資源的統(tǒng)計信息，又兼顧Peer節(jié)點服務(wù)資源服務(wù)的有效性，提升了系統(tǒng)的服務(wù)能力。通過仿真實驗表明本文算法可以提高系統(tǒng)緩存的命中率，提升Peer節(jié)點集的服務(wù)能力，降低媒體服務(wù)器的負載壓力。解決目前P2P網(wǎng)絡(luò)結(jié)構(gòu)存在的主要問題，為媒體流的傳輸、應(yīng)用提供切實可行的全局信息的替換算法。

[1]CNNIC.2009年中國網(wǎng)民網(wǎng)絡(luò)視頻應(yīng)用研究報告[R/OL]. Apr， 8， 2010. http：//research. cnnic. cn/html/1270691299d2051.html.

[2]中投顧問.2010-2015年中國網(wǎng)絡(luò)視頻行業(yè)投資分析及前景預(yù)測報告[R].Feb，2010.

[3]李之棠.P2P原理與技術(shù)[R].華中科技大學計算機學院.Jun，4，2007.

[4]雷迎春，程實，吳產(chǎn)樂等。應(yīng)用網(wǎng)絡(luò)編碼的P2P內(nèi)容分發(fā)[J].計算機研究與發(fā)展，2009，46(1)：108-119.

[5]ChiFeng Kao，ChungNan Lee.Aggregate Profit-Based Caching Replacement Algorithms for Streaming Media Transcoding Proxy Systems[J].Multimedia，2007，9(2)：221-230.

[6]徐群，祝永志.集群系統(tǒng)中的負載均衡問題的研究[J].計算機技術(shù)與發(fā)展，2009，8.

[7]羅杰文.Peer to Peer(P2P)綜述[R/OL].Nov，3，2005.http：//docs.huihoo.com/p2p/1/index.html.

[8]Jun Wang，Johan Pouwelse，Jenneke Fokker.Personalization on a peer-to-peer television system[J].Multimedia Tools and Applications，2008，36(1)：89-113.

[9]HsiangFu Yu，HungChang Yang，ChuYi Chien.A Limited Client Capability Broadcasting Scheme for VoD Applications[C].ICN 2008：192-196.

[10]Tsai HsienMing，Ding JenWen，Cheng ShuChen.Providing continuous VCR function with interpolated active buffer management for near VoD system on ubiquitous multimedia environment[C].The 1st IEEE International Conference on Ubi-Media Computing and Workshops，2008：231-236.

[11]吳杰.P2P流媒體內(nèi)容分發(fā)與服務(wù)關(guān)鍵技術(shù)研究[D].復(fù)旦大學博士學位論文，2008.

[12]馮健.P2P點播流媒體服務(wù)質(zhì)量研究[D].國防科技大學博士學位論文，2008.

[13]張明龍，馮博琴，王雪平.并發(fā)多媒體服務(wù)系統(tǒng)超載模型分析[J].西安交通大學學報，2006，40(2)：161-164.

[14]楊杰.基于P2P的流媒體代理緩存系統(tǒng)[J].電腦與信息技術(shù)，2009，17(2)：60-65.

[15]胡懋智，徐恪，夏樹濤等.TOW：一種新的P2P實時流媒體緩存替換算法[J].小型微型計算機系統(tǒng)，2009，30(8)：1484-1489.