張學(xué)圈 張紅躍 熊章學(xué) 王紅青 張鵬遠(yuǎn) 牛志雷 劉家軍

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

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

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

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

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

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

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

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

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

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

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

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

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

式中：

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

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

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

式中：

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

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

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

式中：

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

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

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

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

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

式中：

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

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

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

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

2 算法實(shí)現(xiàn)

2.1 稀缺度統(tǒng)計(jì)

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

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

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

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

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

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

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

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

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

圖1 緩存替換算法

3 仿真分析

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

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

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

3.2 仿真結(jié)果分析

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

3.2.1 控制開銷

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

圖2 控制開銷

3.2.2 服務(wù)延遲

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

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

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

圖5 服務(wù)器壓力

4 結(jié)論

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

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

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

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

[4]雷迎春，程實(shí)，吳產(chǎn)樂等。應(yīng)用網(wǎng)絡(luò)編碼的P2P內(nèi)容分發(fā)[J].計(jì)算機(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)中的負(fù)載均衡問題的研究[J].計(jì)算機(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ù)旦大學(xué)博士學(xué)位論文，2008.

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

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

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

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