《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 其他 > 設(shè)計(jì)應(yīng)用 > 基于云存儲(chǔ)的P2P視頻點(diǎn)播系統(tǒng)數(shù)據(jù)復(fù)制策略
基于云存儲(chǔ)的P2P視頻點(diǎn)播系統(tǒng)數(shù)據(jù)復(fù)制策略
來(lái)源:微型機(jī)與應(yīng)用2013年第20期
王 娟
(江蘇宿遷澤達(dá)職業(yè)技術(shù)學(xué)院,江蘇 宿遷223800)
摘要: 交互性支持對(duì)P2P視頻點(diǎn)播系統(tǒng)具有重要的意義,視頻點(diǎn)播服務(wù)的大規(guī)模普及離不開用戶交互性的支持。討論了如何有效利用對(duì)等節(jié)點(diǎn)的帶寬和存儲(chǔ)資源來(lái)主動(dòng)復(fù)制數(shù)據(jù)塊,提出了一種基于云存儲(chǔ)的數(shù)據(jù)復(fù)制策略CSPR。仿真實(shí)驗(yàn)結(jié)果表明,相比于現(xiàn)有的數(shù)據(jù)復(fù)制策略,CSPR可以顯著提高用戶進(jìn)行隨機(jī)搜索操作時(shí)的響應(yīng)速度,并降低網(wǎng)絡(luò)復(fù)制開銷。
Abstract:
Key words :

摘  要: 交互性支持對(duì)P2P視頻點(diǎn)播系統(tǒng)具有重要的意義,視頻點(diǎn)播服務(wù)的大規(guī)模普及離不開用戶交互性的支持。討論了如何有效利用對(duì)等節(jié)點(diǎn)的帶寬和存儲(chǔ)資源來(lái)主動(dòng)復(fù)制數(shù)據(jù)塊,提出了一種基于云存儲(chǔ)的數(shù)據(jù)復(fù)制策略CSPR。仿真實(shí)驗(yàn)結(jié)果表明,相比于現(xiàn)有的數(shù)據(jù)復(fù)制策略,CSPR可以顯著提高用戶進(jìn)行隨機(jī)搜索操作時(shí)的響應(yīng)速度,并降低網(wǎng)絡(luò)復(fù)制開銷。
關(guān)鍵詞: 對(duì)等網(wǎng)絡(luò);視頻點(diǎn)播;云計(jì)算;數(shù)據(jù)復(fù)制

    視頻點(diǎn)播VoD(Video on Demand)服務(wù)是指根據(jù)用戶的需要,隨機(jī)選擇視頻內(nèi)容進(jìn)行播放的服務(wù)。在P2P網(wǎng)絡(luò)上構(gòu)建視頻點(diǎn)播系統(tǒng)能有效利用節(jié)點(diǎn)間網(wǎng)絡(luò)帶寬、存儲(chǔ)空間和數(shù)據(jù)資源,系統(tǒng)具有良好的可擴(kuò)展性、數(shù)據(jù)可用性和可靠性。因此,P2P視頻點(diǎn)播系統(tǒng)(P2P VoD)已成為當(dāng)前一個(gè)重要的研究領(lǐng)域。但P2P VoD中每個(gè)節(jié)點(diǎn)隨時(shí)都可能暫時(shí)或永久離開系統(tǒng),這使得構(gòu)建支持交互性的P2P VoD極富挑戰(zhàn)性。系統(tǒng)中的節(jié)點(diǎn)均負(fù)責(zé)存儲(chǔ)數(shù)據(jù),一旦某節(jié)點(diǎn)暫時(shí)離開,存在其上的數(shù)據(jù)就暫時(shí)不可訪問(wèn),而節(jié)點(diǎn)的永久離開更會(huì)造成數(shù)據(jù)的丟失。因而采用有效的辦法來(lái)應(yīng)對(duì)動(dòng)態(tài)的系統(tǒng)環(huán)境,從而滿足用戶的隨機(jī)搜索操作(VCR)則顯得十分必要。
    云計(jì)算是當(dāng)今IT界的熱門技術(shù),借助云計(jì)算,網(wǎng)絡(luò)服務(wù)提供者可以在瞬息之間處理數(shù)以千萬(wàn)計(jì)甚至億計(jì)的信息,實(shí)現(xiàn)與超級(jí)計(jì)算機(jī)同樣強(qiáng)大的效能。當(dāng)云計(jì)算系統(tǒng)運(yùn)算和處理的核心是大量數(shù)據(jù)的存儲(chǔ)和管理時(shí),云計(jì)算系統(tǒng)中就需要配置大量的存儲(chǔ)設(shè)備,此時(shí)云計(jì)算系統(tǒng)就轉(zhuǎn)變成為一個(gè)云存儲(chǔ)系統(tǒng),所以云存儲(chǔ)是一個(gè)以數(shù)據(jù)存儲(chǔ)和管理為核心的云計(jì)算系統(tǒng)。
    在P2P VoD中,資源保存在用戶的機(jī)器上,視頻文件越流行,下載的用戶越多,資源的副本越多,下載效率就越高。但對(duì)于一些過(guò)時(shí)的文件,用戶會(huì)選擇刪除,以免占用過(guò)多的個(gè)人空間。因此,一些冷門文件就不容易通過(guò)對(duì)等節(jié)點(diǎn)間的共享獲得。參考文獻(xiàn)[1]指出用戶訪問(wèn)的集中度符合“二八定律”,即20%的視頻內(nèi)容吸引了80%的用戶訪問(wèn),而其他的80%的用戶訪問(wèn)只吸引了20%的用戶訪問(wèn)量。在基于云存儲(chǔ)的P2P視頻點(diǎn)播系統(tǒng)中,考慮將存儲(chǔ)空間當(dāng)作一片“云”,在無(wú)限量的空間,當(dāng)用戶想從個(gè)人的機(jī)器上刪除一些過(guò)時(shí)但非毫無(wú)價(jià)值的數(shù)據(jù)塊時(shí),可以選擇把資源通過(guò)數(shù)據(jù)復(fù)制的方式放在云上,從而把數(shù)據(jù)塊保存起來(lái)。這樣用戶不僅可以通過(guò)節(jié)點(diǎn)間的共享快速獲得熱門視頻數(shù)據(jù),也可以通過(guò)檢索找到被存儲(chǔ)起來(lái)的冷門視頻數(shù)據(jù),從而可以快速地響應(yīng)用戶的VCR操作。
    本文主要討論在節(jié)點(diǎn)將要離開系統(tǒng)時(shí),根據(jù)視頻數(shù)據(jù)各個(gè)部分的受歡迎程度以及對(duì)等節(jié)點(diǎn)間的網(wǎng)絡(luò)距離,提出了一種基于云存儲(chǔ)的數(shù)據(jù)復(fù)制策略CSPR。仿真實(shí)驗(yàn)結(jié)果表明,相比于現(xiàn)有的基于流行度的數(shù)據(jù)復(fù)制策略PPR,CSPR可以顯著提高用戶執(zhí)行VCR操作的響應(yīng)速度,并有效降低復(fù)制數(shù)據(jù)時(shí)所產(chǎn)生的網(wǎng)絡(luò)開銷。
1 相關(guān)工作
    VCR功能是對(duì)等點(diǎn)播系統(tǒng)中最重要的功能之一,也是本文研究的主要目標(biāo)。在樹狀P2P VoD系統(tǒng)中,如P2Cast[2]則沒(méi)有考慮VCR操作對(duì)系統(tǒng)性能造成的影響,沒(méi)有針對(duì)VCR操作設(shè)計(jì)新的數(shù)據(jù)存儲(chǔ)策略。當(dāng)用戶進(jìn)行VCR操作時(shí),節(jié)點(diǎn)需要通過(guò)重新加入組播樹。
    在網(wǎng)狀P2P VoD系統(tǒng)中,如VMesh[3]和BulletMedia[4]則是利用DHT技術(shù)支持VCR操作。VMesh通過(guò)本地向下/向上的指針和DHT查詢來(lái)支持交互式操作。在VMesh中,節(jié)點(diǎn)通過(guò)本地存儲(chǔ)的數(shù)據(jù)塊來(lái)為其他節(jié)點(diǎn)提供服務(wù),而不是正在收看的數(shù)據(jù)塊。存儲(chǔ)的數(shù)據(jù)塊在節(jié)點(diǎn)的上線時(shí)間內(nèi)不變。BulletMedia通過(guò)DHT方法讓對(duì)等節(jié)點(diǎn)大公無(wú)私地主動(dòng)查找稀有的數(shù)據(jù)塊并進(jìn)行復(fù)制存儲(chǔ),保證每個(gè)數(shù)據(jù)塊在系統(tǒng)中至少有K個(gè)副本。當(dāng)用戶進(jìn)行VCR操作時(shí),通過(guò)DHT方法查找相應(yīng)的數(shù)據(jù)片段,以減輕用戶進(jìn)行VCR操作時(shí)對(duì)服務(wù)器造成的壓力。
    針對(duì)因節(jié)點(diǎn)離開而導(dǎo)致數(shù)據(jù)丟失的問(wèn)題,參考文獻(xiàn)[5]采用了基于預(yù)測(cè)的帶寬分配策略PBA。該策略的核心思想是讓父節(jié)點(diǎn)給那些具有較高帶寬的子節(jié)點(diǎn)提供較大的上傳帶寬,并且它僅僅讓節(jié)點(diǎn)把數(shù)據(jù)復(fù)制給將來(lái)可能需要的那些節(jié)點(diǎn)。但PBA策略是假定用戶從頭到尾觀看視頻節(jié)目的,并且在觀看過(guò)程中沒(méi)有VCR操作,這是不符合視頻點(diǎn)播系統(tǒng)中的用戶觀看行為的,因此PBA策略不能直接應(yīng)用于P2P VoD系統(tǒng)中。
    研究表明,用戶在視頻點(diǎn)播系統(tǒng)中的行為并非毫無(wú)規(guī)律。參考文獻(xiàn)[6]指出,不同的文件具有不同的流行度,即用戶訪問(wèn)的頻率;大部分的用戶訪問(wèn)都集中于少量熱門節(jié)目上,并且文件的流行度是隨時(shí)間而改變的。
2 基于云存儲(chǔ)的數(shù)據(jù)復(fù)制策略
2.1 云節(jié)點(diǎn)的選擇策略

    為了降低節(jié)點(diǎn)離開對(duì)P2P VoD系統(tǒng)性能的影響,常根據(jù)特定的選擇策略從系統(tǒng)的可用節(jié)點(diǎn)集中選擇部分節(jié)點(diǎn)來(lái)使用[7]。節(jié)點(diǎn)選擇策略可分為隨機(jī)選擇和確定性選擇兩大類,其中隨機(jī)選擇策略是指不考慮節(jié)點(diǎn)的特征隨機(jī)選擇節(jié)點(diǎn);確定性選擇策略是指根據(jù)節(jié)點(diǎn)的某種特征選擇滿足一定標(biāo)準(zhǔn)的節(jié)點(diǎn),如根據(jù)節(jié)點(diǎn)的當(dāng)前在線時(shí)長(zhǎng)、帶寬吞吐能力等選擇節(jié)點(diǎn)[8-9]。
    由于節(jié)點(diǎn)的當(dāng)前在線時(shí)長(zhǎng)對(duì)其余留時(shí)長(zhǎng)有一定的預(yù)見(jiàn)性,因此選擇最長(zhǎng)當(dāng)前在線時(shí)長(zhǎng)的策略用于DHT網(wǎng)絡(luò)中鄰居節(jié)點(diǎn)的選擇[10]和超級(jí)節(jié)點(diǎn)的選擇[11],以及覆蓋層多播樹種雙親節(jié)點(diǎn)的選擇[12]。GODFREY B P等人[7]將不同的選擇策略應(yīng)用于5個(gè)當(dāng)前廣泛使用的對(duì)等網(wǎng)絡(luò)中。實(shí)驗(yàn)結(jié)果表明,與其他選擇策略相比,隨機(jī)選擇策略可以有效降低節(jié)點(diǎn)動(dòng)態(tài)性對(duì)P2P網(wǎng)絡(luò)的影響。這是由于隨機(jī)選擇策略具有簡(jiǎn)單、易實(shí)現(xiàn)等特點(diǎn)。因而隨機(jī)選擇策略被廣泛地應(yīng)用于P2P網(wǎng)絡(luò)中,如P2P文件存儲(chǔ)系統(tǒng)Total Recall[13]等。
    因此,本文采用隨機(jī)選擇策略來(lái)選擇云存儲(chǔ)中的云節(jié)點(diǎn)。
2.2 云節(jié)點(diǎn)的組織方式
    基于P2P的系統(tǒng)中兩節(jié)點(diǎn)間網(wǎng)絡(luò)距離的測(cè)算可通過(guò)計(jì)算系統(tǒng)中數(shù)據(jù)傳輸時(shí)延、網(wǎng)絡(luò)最小帶寬和數(shù)據(jù)傳輸所經(jīng)路由跳數(shù)等方法獲得。對(duì)于P2P視頻點(diǎn)播系統(tǒng)中數(shù)據(jù)塊的可用性和可靠性來(lái)說(shuō),數(shù)據(jù)傳輸時(shí)延是一個(gè)很重要的因素,而數(shù)據(jù)傳輸時(shí)延最主要的影響因子是傳輸兩節(jié)點(diǎn)間的可用帶寬。
    P2P覆蓋網(wǎng)技術(shù)從最初以Napster為代表的有著中央目錄服務(wù)器的對(duì)等網(wǎng)絡(luò)結(jié)構(gòu),到后來(lái)以Gnutella為代表的完全分布式的對(duì)等網(wǎng)絡(luò)和提供匿名發(fā)布和獲取文檔的Freenet,再到以CAN、Chord、Pastry和Tapestry等為代表的基于分布式哈希表的結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò),對(duì)等網(wǎng)絡(luò)的發(fā)展大致經(jīng)歷了3個(gè)階段,每個(gè)階段都采用了不同的資源定位和路由模型。根據(jù)拓?fù)浣Y(jié)構(gòu)關(guān)系可以將P2P系統(tǒng)分為4類:集中式P2P系統(tǒng)、完全分布式P2P系統(tǒng)、混合式P2P系統(tǒng)和結(jié)構(gòu)化P2P系統(tǒng)。
    本文將P2P視頻點(diǎn)播系統(tǒng)中網(wǎng)絡(luò)距離相近的節(jié)點(diǎn)劃分到同一云中,以實(shí)現(xiàn)對(duì)節(jié)點(diǎn)的分組和有效管理,采用參考文獻(xiàn)[14]中的節(jié)點(diǎn)分組算法來(lái)對(duì)云節(jié)點(diǎn)進(jìn)行組織。該算法的核心思想是依次從初始化網(wǎng)絡(luò)中隨機(jī)選取一個(gè)節(jié)點(diǎn),以該節(jié)點(diǎn)為圓心,預(yù)測(cè)網(wǎng)絡(luò)距離為半徑,其內(nèi)的所有節(jié)點(diǎn)都劃入一個(gè)分組,再將獲得分組的節(jié)點(diǎn)從初始網(wǎng)絡(luò)中移除。以此方法循環(huán)劃分,可將初始網(wǎng)絡(luò)中大部分節(jié)點(diǎn)劃入分組。
    另外,本文采用參考文獻(xiàn)[15]中的方法對(duì)分布式數(shù)據(jù)塊的流行度進(jìn)行估計(jì)。
2.3 基于云存儲(chǔ)的數(shù)據(jù)復(fù)制算法
    基于云存儲(chǔ)的數(shù)據(jù)復(fù)制策略包括以下4個(gè)步驟:(1)根據(jù)隨機(jī)選擇策略選擇云節(jié)點(diǎn);(2)按照網(wǎng)絡(luò)距離分組算法組織這些數(shù)據(jù)復(fù)制的目標(biāo)云節(jié)點(diǎn);(3)根據(jù)分布式平均算法估計(jì)出每個(gè)數(shù)據(jù)塊的流行度,并按從高到低的順序排序,按照用戶存儲(chǔ)空間的大小確定數(shù)據(jù)塊集合S;(4)把S以外的數(shù)據(jù)塊推向云節(jié)點(diǎn)中進(jìn)行存儲(chǔ)。該算法可用偽代碼表示如下:
for(1≤m≤t)    compute(pm);//計(jì)算數(shù)據(jù)塊的流行度
if(delete(M))
{
for(1≤m≤t)
{
NodeGet(n,i);    //從當(dāng)前在線的節(jié)點(diǎn)中隨機(jī)選取
節(jié)點(diǎn)i作為數(shù)據(jù)復(fù)制目標(biāo)云節(jié)點(diǎn)
SegmentChoose(P,M,m); //選取流行度高且副本數(shù)
低的數(shù)據(jù)塊m
Replication(m,i);   //將數(shù)據(jù)塊m復(fù)制給節(jié)點(diǎn)i
}
}
代碼中,n表示在線的節(jié)點(diǎn)數(shù);i為選擇的目標(biāo)數(shù)據(jù)復(fù)制云節(jié)點(diǎn);m表示選擇的數(shù)據(jù)塊;t表示將要?jiǎng)h除數(shù)據(jù)塊的個(gè)數(shù);T表示整個(gè)數(shù)據(jù)塊的集合;S為各個(gè)節(jié)點(diǎn)的性能值的集合,其中s1≥s2≥…≥sn;M表示節(jié)點(diǎn)將要?jiǎng)h除的數(shù)據(jù)塊的集合,M=T-S;P表示各個(gè)數(shù)據(jù)塊的流行度集合,其中s1≥s2≥…≥st。
3 仿真實(shí)驗(yàn)
3.1 關(guān)鍵性能指標(biāo)

    選擇了如下兩個(gè)重要參數(shù)作為P2P視頻點(diǎn)播系統(tǒng)中數(shù)據(jù)復(fù)制算法性能的關(guān)鍵指標(biāo),也是仿真實(shí)驗(yàn)的測(cè)量對(duì)象。
    (1)響應(yīng)用戶VCR操作時(shí)延:數(shù)據(jù)復(fù)制的目標(biāo)之一是快速響應(yīng)用戶進(jìn)行VCR操作的時(shí)延,以改進(jìn)用戶的播放體驗(yàn)。該指標(biāo)指從用戶進(jìn)行VCR操作開始到獲得所想要的數(shù)據(jù)塊為止所需要的時(shí)間,響應(yīng)用戶VCR操作時(shí)延的減少表示數(shù)據(jù)復(fù)制算法的性能的提高。
    (2)網(wǎng)絡(luò)開銷:由復(fù)制的數(shù)據(jù)塊總量來(lái)表示,主要衡量數(shù)據(jù)復(fù)制導(dǎo)致的系統(tǒng)資源的額外消耗,例如,增加的對(duì)等節(jié)點(diǎn)之間網(wǎng)絡(luò)通信流量。
3.2 實(shí)驗(yàn)與結(jié)果
    仿真實(shí)驗(yàn)對(duì)本文提出的基于云存儲(chǔ)的P2P視頻點(diǎn)播系統(tǒng)數(shù)據(jù)復(fù)制策略CSPR與現(xiàn)有的數(shù)據(jù)復(fù)制策略的關(guān)鍵性能指標(biāo)進(jìn)行對(duì)比?;诹餍卸鹊臄?shù)據(jù)復(fù)制策略(PPR)在進(jìn)行數(shù)據(jù)復(fù)制時(shí)僅考慮每個(gè)數(shù)據(jù)塊的流行度,而并未考慮節(jié)點(diǎn)間的網(wǎng)絡(luò)距離。

 


    本文在對(duì)P2P對(duì)等點(diǎn)播系統(tǒng)用戶動(dòng)態(tài)性分析的基礎(chǔ)上,提出了一種基于云存儲(chǔ)的數(shù)據(jù)復(fù)制策略CSPR。仿真實(shí)驗(yàn)結(jié)果表明,相比單純基于數(shù)據(jù)流行度的數(shù)據(jù)復(fù)制機(jī)制,本文提出的數(shù)據(jù)復(fù)制機(jī)制可較快地響應(yīng)用戶VCR操作,同時(shí)降低了網(wǎng)絡(luò)開銷。在后續(xù)的工作中,將考慮對(duì)P2P視頻點(diǎn)播系統(tǒng)的移動(dòng)用戶行為特征進(jìn)行分析,將之應(yīng)用于數(shù)據(jù)復(fù)制策略中,來(lái)更好地滿足移動(dòng)用戶觀看視頻文件時(shí)的交互式操作,從而改善用戶的播放體驗(yàn)。
參考文獻(xiàn)
[1] Yu Hongliang,Zheng Dongdong,ZHAO B Y,et al.Understanding user behavior in large-scale video-on-demand systems[C].In Proceedings of ACM,Eurosys,2006.
[2] GUO Y,SUH K,KUROSE J,et al.P2Cast:peer-to-peer  patching scheme for VoD service[C].In Proceedings of the 12th International World Wide Web Conference,Budapest,2003:301-309.
[3] YIU K,JIN X,CHAN G.VMesh:distributed segment storage  for peer-to-peer interactive video streaming[J].IEEE Journal on Selected Areas in Communications(JSAC),2007,25(9):1717-1731.
[4] NEVENA V,PRIYA G,NIKOLA K,et al.Enabling DVD-like features in P2P video-on-demand systems[C].In  Proceedings of the SIGCOMM Peer-to-Peer Streaming and  IP-TV Workshop,Kyoto,2007:329-334.
[5] CHENA Z J,XUE K P,HONG P L,et al.Differentiated  bandwidth allocation for reducing server load in P2P VoD[C]. In Proceedings of the 8th International Conference on Grid    and Cooperative Computing,Lanzhou,2009:31-36.
[6] Luo Jianguang,Tang Yun,Zhang Meng,et al.Characterizing  user behavior model to evaluate hard cache in peer-to-peer based video-on-demand service[C].In Proc.MMM,Kyoto,2005:125-134.
[7] GODFREY B P,SHENKER S,STOICA I.Minimizing churn  in distributed sytems[C].In Proc.of the ACM SIGCOMM  2006,New York:ACM Press,2006:147-158.
[8] 張宇翔,楊冬,張宏科.P2P網(wǎng)絡(luò)中Churn問(wèn)題研究[J].軟件學(xué)報(bào),2009,20(5):1362-1367.
[9] RHEA S,GEELS D,ROSCOE T,et al.Handling churn in  a DHT[C].In Proc.of  the USENIX Annual Technical Conference.Boston:USENIX Association Press,2004:127-140.
[10] LEDLIE J,SHNEIDMAN J,AMIS M,et al.Reliability  and capacity-based selection in distributed hash tables[R]. Technical Report,Harvard University Computer Science,2003:1-14.
[11] GARCES E L,BIERSACK E W,ROSS K W,et al. Hierarchical peer-to-peer systems[C].In Proc. of the ACM/IFIP Int’l Conf. on Parallel and Distributed Computing (Euro-Par).Berlin:Springer-Verlag,2003:1230-1239.
[12] SPRIPANIDKULCHAI K,GANJAM A,MAGGS B,et al. The feasibility of supporting large-scale live streaming applications with dynamic application end-points[C].In Proc.of the ACM SIGCOMM.New York:ACM Press,2004:107-120.
[13] BHAGWAN R,TATI K,CHENG Y,et al.Total recall:system support for automated availability management[C].In Proc.of the 1st ACM/Usenix Symp.on Networked Systems Design and Implementation(NSDI 2004).San Francisco:USENI Press,2004:337-350.
[14] 楊磊,黃浩,李仁發(fā),等,一種基于分組管理的混合式P2P存儲(chǔ)系統(tǒng)[J].計(jì)算機(jī)科學(xué),2010,37(1):64-67.
[15] MEHYAR M,SPANOS D,PONGSAJAPAN J,et al.Asynchronous distributed averaging on communication networks[J]. IEEE/ACM Transactions on Networking,2007,15(3):512-520.
[16] The Network Simulator-ns-2[EB/OL].[2013-05-25].http: //www.isi.edu/nsnam/ns.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。