張學(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信息做出緩存替換裁決,從而獲取資源的最佳使用。
根據(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)整因子。
在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))。
當(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 緩存替換算法
為了有效地驗(yàn)證本文提出的算法,我們按照本文提出的模型構(gòu)造系統(tǒng)仿真模型進(jìn)行評估。本章節(jié)就系統(tǒng)仿真模型進(jìn)行介紹和結(jié)果分析。
仿真模型中我們認(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)先考慮本覆蓋的資源需求。
仿真試驗(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ù)器壓力
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.