叢鑫，雙鍇，蘇森，楊放春，孫鑫

（1.北京郵電大學(xué) 網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100876；2.遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島 125105）

1 引言

近年來，視頻點(diǎn)播(VoD, video-on-demand)服務(wù)已經(jīng)成為網(wǎng)絡(luò)上最流行的應(yīng)用之一。傳統(tǒng)的VoD系統(tǒng)使用內(nèi)容分發(fā)網(wǎng)絡(luò)(CDN, content delivery network)將視頻數(shù)據(jù)發(fā)送給節(jié)點(diǎn)，但隨著節(jié)點(diǎn)數(shù)目的增加，基礎(chǔ)設(shè)施的投入是呈線性增長(zhǎng)的。當(dāng)前的VoD系統(tǒng)使用P2P(peer-to-peer)技術(shù)，利用節(jié)點(diǎn)相互交換視頻數(shù)據(jù)，可以使VoD服務(wù)提供商以較小的開銷服務(wù)較大數(shù)量的節(jié)點(diǎn)，但P2P-VoD系統(tǒng)中不可回避的問題是，服務(wù)器帶寬開銷很高但利用率很低。例如文獻(xiàn)[1]指出，VoD服務(wù)提供商每月的開銷中帶寬支出占50%以上。在PPLive中[2]，一天之中超過50%的時(shí)間服務(wù)器帶寬利用率都低于20%，而造成這種現(xiàn)象的原因是一天中各個(gè)時(shí)間段內(nèi)節(jié)點(diǎn)請(qǐng)求視頻的用戶訪問數(shù)量是不均衡的，在21:00點(diǎn)，視頻請(qǐng)求數(shù)量達(dá)到最大，7:00達(dá)到最小。而隨著基于內(nèi)容的云平臺(tái)的應(yīng)用，為上述P2P-VoD架構(gòu)下遇到的問題提供了一種可能的解決方案:在每天的請(qǐng)求高峰時(shí)段，由云平臺(tái)充當(dāng)視頻服務(wù)器分擔(dān)部分負(fù)載，利用云提供商和因特網(wǎng)服務(wù)提供商(ISP, Internet service providers)的價(jià)格差異，降低VoD服務(wù)提供商服務(wù)器帶寬開銷，提高帶寬利用率。

通常情況下，VoD系統(tǒng)中，節(jié)點(diǎn)需要把下載到的視頻數(shù)據(jù)存儲(chǔ)在硬盤或內(nèi)存(稱為緩沖區(qū))中來保證視頻播放的平滑性。這種方法需要節(jié)點(diǎn)設(shè)備有一定大小的緩沖區(qū)，可以在播放點(diǎn)異步的節(jié)點(diǎn)間相互傳播視頻數(shù)據(jù)，但是如何在播放點(diǎn)異步的情況下有效地尋找到能提供所需視頻數(shù)據(jù)的鄰居節(jié)點(diǎn)是一個(gè)需要考慮的問題。文獻(xiàn)[3]提出在大規(guī)模的P2P系統(tǒng)中，可以將視頻數(shù)據(jù)緩存到緩沖區(qū)中而后共享給其他節(jié)點(diǎn)。文獻(xiàn)[4]將具有相似到達(dá)時(shí)間的節(jié)點(diǎn)分成一組，在組內(nèi)進(jìn)行視頻內(nèi)容的交換。文獻(xiàn)[5]允許節(jié)點(diǎn)隨機(jī)加入一個(gè)或多個(gè)多播樹，并且規(guī)定只能從父節(jié)點(diǎn)向子節(jié)點(diǎn)定向的傳輸視頻數(shù)據(jù)。文獻(xiàn)[6]設(shè)計(jì)了一種以下載進(jìn)程和令牌為基礎(chǔ)的節(jié)點(diǎn)數(shù)據(jù)交換過程，但未考慮到使用移動(dòng)設(shè)備的用戶參與系統(tǒng)的情況。另一個(gè)需要考慮的問題是節(jié)點(diǎn)緩沖區(qū)大小對(duì)視頻共享的影響。節(jié)點(diǎn)間只能相互共享存在于緩沖區(qū)內(nèi)的視頻數(shù)據(jù)，當(dāng)節(jié)點(diǎn)緩沖區(qū)足夠大時(shí)，能全部存儲(chǔ)已觀看過的視頻數(shù)據(jù)；反之，只能部分存儲(chǔ)。文獻(xiàn)[7]設(shè)計(jì)一種區(qū)分?jǐn)?shù)據(jù)優(yōu)先級(jí)的算法，節(jié)點(diǎn)下載的數(shù)據(jù)塊按緊急程度分別來源于高優(yōu)先數(shù)據(jù)集和保留數(shù)據(jù)集。文獻(xiàn)[8]應(yīng)用隨機(jī)模型和啟發(fā)式算法進(jìn)行數(shù)據(jù)塊的下載，但未考慮視頻服務(wù)器提供數(shù)據(jù)的因素。文獻(xiàn)[9]從文件片選擇、鄰居節(jié)點(diǎn)選擇和副本管理方面評(píng)估了存在的算法在節(jié)點(diǎn)資源有限和充足情形下的性能，但未涉及基于緩沖區(qū)的算法。

在現(xiàn)實(shí)中，計(jì)算機(jī)節(jié)點(diǎn)有較大的緩沖區(qū)，可以存儲(chǔ)全部觀看過的視頻，因此能夠服務(wù)其播放點(diǎn)之前任何有數(shù)據(jù)請(qǐng)求的用戶；同時(shí)也存在手機(jī)、PDA等節(jié)點(diǎn)，其擁有較小的緩沖區(qū)，可以存儲(chǔ)部分觀看過的視頻數(shù)據(jù)，只能服務(wù)其播放點(diǎn)之前部分有數(shù)據(jù)請(qǐng)求的用戶。本文的出發(fā)點(diǎn)在于當(dāng)越來越多的小緩沖區(qū)節(jié)點(diǎn)加入到VoD系統(tǒng)時(shí)，如何設(shè)計(jì)視頻數(shù)據(jù)塊的下載策略才能保證節(jié)點(diǎn)所需數(shù)據(jù)塊的高可用性(即數(shù)據(jù)塊能以較高的概率下載)和提升節(jié)點(diǎn)的下載速率，從而降低VoD提供商的服務(wù)器帶寬開銷。

本文采用基于內(nèi)容的云平臺(tái)和P2P技術(shù)構(gòu)建云輔助的 P2P-VoD架構(gòu)。在此架構(gòu)下設(shè)計(jì)了 NCS(neighbors and chunks selection)算法以輔助節(jié)點(diǎn)有效地共享視頻數(shù)據(jù)。NCS算法包含節(jié)點(diǎn)選擇子算法和塊下載子算法?；诰彌_區(qū)的節(jié)點(diǎn)選擇算法以下載點(diǎn)為基準(zhǔn)使節(jié)點(diǎn)有效地查找到能夠提供視頻數(shù)據(jù)的鄰居節(jié)點(diǎn)，基于緩沖區(qū)的塊下載算法計(jì)算了 2種不同的塊下載策略在此架構(gòu)下所需要的最小緩沖區(qū)值，為視頻塊的下載方法提供理論依據(jù)。本文貢獻(xiàn)如下。

1）詳細(xì)研究小緩沖區(qū)節(jié)點(diǎn)對(duì)P2P-VoD系統(tǒng)的影響，設(shè)計(jì)基于緩沖區(qū)的節(jié)點(diǎn)選擇算法，能夠使節(jié)點(diǎn)以高概率選擇到提供視頻數(shù)據(jù)的鄰居節(jié)點(diǎn)。

2）在云輔助P2P-VoD架構(gòu)下，計(jì)算2種不同的塊下載策略——最少優(yōu)先和貪婪策略所需要的最小緩沖區(qū)的值，并以此為基礎(chǔ)為不同緩沖區(qū)大小的節(jié)點(diǎn)選擇合適的塊下載方案以達(dá)到系統(tǒng)中視頻數(shù)據(jù)塊的高可用性提供理論依據(jù)。

3）建立云輔助P2P-VoD模擬器來評(píng)估NCS算法性能。實(shí)驗(yàn)表明，提出的算法能夠降低服務(wù)器負(fù)載和請(qǐng)求的拒絕率，提升節(jié)點(diǎn)的下載速率。同時(shí)也研究了不同移動(dòng)設(shè)備在系統(tǒng)中占據(jù)的比例不同時(shí)，服務(wù)器負(fù)載的變化情況。結(jié)果表明，隨著小緩沖區(qū)節(jié)點(diǎn)的增加，服務(wù)器負(fù)載的增加程度較低。

2 云輔助P2P-VoD系統(tǒng)架構(gòu)

如圖1所示，云輔助P2P-VoD系統(tǒng)中主要由4個(gè)組成部分，分別是節(jié)點(diǎn)、視頻提供商存儲(chǔ)服務(wù)器和tracker服務(wù)器、云存儲(chǔ)服務(wù)器和云分發(fā)服務(wù)器，各部分功能如下。

圖1 云輔助P2P-VoD系統(tǒng)架構(gòu)

節(jié)點(diǎn):使用各種設(shè)備在系統(tǒng)中觀看視頻的用戶。它們從視頻提供商存儲(chǔ)服務(wù)器，云分發(fā)服務(wù)器或其他節(jié)點(diǎn)處下載視頻數(shù)據(jù)；同時(shí)也將緩沖區(qū)中的視頻數(shù)據(jù)共享給其他節(jié)點(diǎn)。

視頻提供商存儲(chǔ)服務(wù)器:負(fù)責(zé)存儲(chǔ)視頻源和分發(fā)視頻數(shù)據(jù)。當(dāng)一天之中節(jié)點(diǎn)的請(qǐng)求處于空閑時(shí)段時(shí)，由其獨(dú)立地提供服務(wù)。當(dāng)服務(wù)器負(fù)載很重時(shí)，提前發(fā)送高流行度視頻數(shù)據(jù)到云存儲(chǔ)服務(wù)器中[10]。

視頻提供商tracker服務(wù)器:負(fù)責(zé)記錄節(jié)點(diǎn)到達(dá)的時(shí)間并依據(jù)下載點(diǎn)對(duì)節(jié)點(diǎn)進(jìn)行排序；返回節(jié)點(diǎn)的鄰居列表。

云存儲(chǔ)服務(wù)器:歸屬于云提供商，例如Amazon。它負(fù)責(zé)接收來自視頻提供商存儲(chǔ)服務(wù)器發(fā)送的視頻數(shù)據(jù)并將其轉(zhuǎn)發(fā)到云分發(fā)服務(wù)器上。

云分發(fā)服務(wù)器:例如CloudFront[11]，使用整個(gè)云網(wǎng)絡(luò)服務(wù)器，自動(dòng)將視頻內(nèi)容發(fā)送到離請(qǐng)求節(jié)點(diǎn)最近的位于網(wǎng)絡(luò)邊緣的服務(wù)器上，如圖1所示，節(jié)點(diǎn)c向云服務(wù)器請(qǐng)求數(shù)據(jù)時(shí)，云分發(fā)服務(wù)器先將數(shù)據(jù)調(diào)度到位于云網(wǎng)絡(luò)邊緣距離節(jié)點(diǎn)c較近的服務(wù)器a上，由服務(wù)器a應(yīng)答。

在上述架構(gòu)基礎(chǔ)上，本文考慮如何通過節(jié)點(diǎn)間的有效合作來降低 VoD服務(wù)提供商的服務(wù)器帶寬開銷，同時(shí)直接降低云分發(fā)服務(wù)器的開銷。

3 NCS算法

3.1 節(jié)點(diǎn)緩沖區(qū)模型

對(duì)于云輔助P2P-VoD系統(tǒng)中的節(jié)點(diǎn)，考慮3個(gè)特征:節(jié)點(diǎn)的播放點(diǎn)是異步的；節(jié)點(diǎn)必須提前下載當(dāng)前播放點(diǎn)的數(shù)據(jù)；不同節(jié)點(diǎn)的緩沖區(qū)大小是不同的。為了描述基于緩沖區(qū)的鄰居選擇算法，首先引入一些定義來建模節(jié)點(diǎn)視頻的緩沖區(qū)，如圖2所示。

播放點(diǎn)Pi:節(jié)點(diǎn)i當(dāng)前的播放點(diǎn)，是正在播放視頻塊的序號(hào)。

下載點(diǎn)bi:在播放點(diǎn)Pi之后的第一個(gè)未下載的塊的序號(hào)。

平滑級(jí)ui:在播放點(diǎn)Pi之后還能持續(xù)播放的塊的數(shù)量，等于bi?Pi。標(biāo)識(shí)的是節(jié)點(diǎn)播放平滑性。

平滑播放閾值 δ:平滑播放所必須的塊。平滑播放窗口值為[Pi, Pi+δ]。

緩沖區(qū)大小si:節(jié)點(diǎn)i 的存儲(chǔ)視頻數(shù)據(jù)的存儲(chǔ)區(qū)大小。

圖2中，為了保證播放的平滑性，節(jié)點(diǎn)a正在下載的塊(bi+1)是急需的，而節(jié)點(diǎn)b正在下載的塊在δ之后，對(duì)于節(jié)點(diǎn)b來說，當(dāng)前下載的塊是不急需的。節(jié)點(diǎn)b的貢獻(xiàn)程度應(yīng)該大于節(jié)點(diǎn)a，一方面是因?yàn)槠鋸南到y(tǒng)中獲取了更多的視頻數(shù)據(jù)(節(jié)點(diǎn) b的播放點(diǎn)大于節(jié)點(diǎn)a)，需要更多的回報(bào)系統(tǒng)，另一方面此時(shí)上傳視頻數(shù)據(jù)到其他節(jié)點(diǎn)不會(huì)影響節(jié)點(diǎn)b的播放平滑性。

圖2 節(jié)點(diǎn)緩沖區(qū)定義

3.2 基于緩沖區(qū)的節(jié)點(diǎn)選擇算法

文獻(xiàn)[6]證明了隨機(jī)節(jié)點(diǎn)選擇算法效率是很低的，同時(shí)也提出了基于緩沖區(qū)的節(jié)點(diǎn)數(shù)據(jù)交換過程，但其未考慮系統(tǒng)中存在小緩沖區(qū)節(jié)點(diǎn)時(shí)的情況。本文提出一種基于下載點(diǎn)的節(jié)點(diǎn)選擇算法，即有相似下載點(diǎn)的節(jié)點(diǎn)為鄰居進(jìn)行視頻數(shù)據(jù)共享，這些節(jié)點(diǎn)形成Overlay網(wǎng)絡(luò)。相似的下載點(diǎn)保證請(qǐng)求的視頻數(shù)據(jù)能夠以較大的概率存在于被請(qǐng)求的節(jié)點(diǎn)緩沖區(qū)中。

云輔助P2P-VoD系統(tǒng)存在tracker服務(wù)器，在tracker服務(wù)器中存儲(chǔ)記錄節(jié)點(diǎn)的列表，可以記錄節(jié)點(diǎn)的到達(dá)、離開時(shí)間及當(dāng)前下載點(diǎn)的位置，為了避免形成Overlay網(wǎng)絡(luò)時(shí)發(fā)生不匹配問題，tracker服務(wù)器依據(jù)已有的方法[12～14]將地理位置較近的節(jié)點(diǎn)放到同一張節(jié)點(diǎn)列表中。當(dāng)新節(jié)點(diǎn)p加入系統(tǒng)時(shí)，它首先連接 tracker服務(wù)器并向其發(fā)送視頻數(shù)據(jù)請(qǐng)求。tracker服務(wù)器返回包含下載點(diǎn)與p相似的一組節(jié)點(diǎn)的列表。p從列表中選擇一組節(jié)點(diǎn)作為鄰居節(jié)點(diǎn)，并與它們建立連接獲得視頻數(shù)據(jù)。需要注意的是:由于每個(gè)節(jié)點(diǎn)存在最大的連接數(shù)目，可能會(huì)拒絕p的連接請(qǐng)求，因此p需要發(fā)送其當(dāng)前下載點(diǎn)和貢獻(xiàn)等級(jí)到它的鄰居節(jié)點(diǎn)。貢獻(xiàn)等級(jí)定義為節(jié)點(diǎn)的上傳能力，即它能給每個(gè)鄰居節(jié)點(diǎn)上傳數(shù)據(jù)的速率，較大的貢獻(xiàn)等級(jí)會(huì)使鄰居節(jié)點(diǎn)獲得較大的下載速率。應(yīng)答節(jié)點(diǎn)收集請(qǐng)求節(jié)點(diǎn)的貢獻(xiàn)等級(jí)，并將其排序，選擇較大的貢獻(xiàn)等級(jí)的節(jié)點(diǎn)來服務(wù)。由于剛加入的節(jié)點(diǎn)沒有貢獻(xiàn)等級(jí)而不能獲得視頻數(shù)據(jù)，為此，每個(gè)節(jié)點(diǎn)需預(yù)留一個(gè)連接隨機(jī)選擇節(jié)點(diǎn)進(jìn)行服務(wù)。本文假設(shè)節(jié)點(diǎn)能夠如實(shí)地傳播它們貢獻(xiàn)等級(jí)到鄰居節(jié)點(diǎn)上，這個(gè)假設(shè)能夠被已經(jīng)廣泛研究的聲譽(yù)激勵(lì)系統(tǒng)所保證，或者部署到已經(jīng)存在的暗網(wǎng)(darknets)中。

上述過程的關(guān)鍵是如何維護(hù)相似下載點(diǎn)的節(jié)點(diǎn)列表。tracker服務(wù)器通過節(jié)點(diǎn)的到達(dá)時(shí)間和下載點(diǎn)排序在線節(jié)點(diǎn)。當(dāng)新節(jié)點(diǎn)加入時(shí)，追蹤器記錄其到達(dá)時(shí)間，并將其放置到列表的末尾。在本文中，鄰居列表的范圍為[,γεN εN-](,γ ε是取值從0～1的參數(shù)，N是在線節(jié)點(diǎn)的數(shù)目，能夠被追蹤到服務(wù)器統(tǒng)計(jì)）。需要注意的是不同節(jié)點(diǎn)有不同的下載能力，系統(tǒng)中節(jié)點(diǎn)可能會(huì)比其早到達(dá)的鄰居節(jié)點(diǎn)有更快的下載速率，因此它有更大的下載點(diǎn)，此時(shí)它的下載速率會(huì)下降，這是因?yàn)猷従庸?jié)點(diǎn)緩沖區(qū)內(nèi)缺少當(dāng)前需要的視頻數(shù)據(jù)，因此節(jié)點(diǎn)需要選擇有更大的下載點(diǎn)的節(jié)點(diǎn)作為鄰居。為了適應(yīng)這種情況，tracker服務(wù)器需要知道節(jié)點(diǎn)當(dāng)前的下載點(diǎn)，并且返回節(jié)點(diǎn)新的鄰居列表。節(jié)點(diǎn)需要定期和tracker服務(wù)器取得聯(lián)系并且將其最新的下載點(diǎn)上傳到 tracker服務(wù)器上，tracker服務(wù)器根據(jù)節(jié)點(diǎn)的新下載點(diǎn)更新節(jié)點(diǎn)列表。

3.3 最少優(yōu)先和貪婪的塊下載算法

與P2P文件系統(tǒng)相比，P2P-VoD系統(tǒng)為保證播放的平滑性，每個(gè)數(shù)據(jù)塊必須在指定的時(shí)間內(nèi)被下載到節(jié)點(diǎn)緩沖區(qū)中，因此，以何種策略下載以保證視頻數(shù)據(jù)塊的高可用性是需要解決的問題。有2個(gè)策略可以被考慮——最少優(yōu)先和貪婪策略。最小優(yōu)先是先下載離播放點(diǎn)最遠(yuǎn)的數(shù)據(jù)塊，這種策略在獲得緊急塊時(shí)花費(fèi)的代價(jià)比較大[8]；貪婪策略是下載距離播放點(diǎn)最近的數(shù)據(jù)塊，這種方法不能保證稀少塊的可用性。借鑒文獻(xiàn)[8]的思想和文獻(xiàn)[15]的模型，建立云輔助P2P-VoD系統(tǒng)下的塊下載算法模型。假設(shè)節(jié)點(diǎn)緩沖區(qū)中缺失的塊集合為A。塊下載方案為u，表示節(jié)點(diǎn)以何種策略選擇 A中的數(shù)據(jù)塊。在系統(tǒng)達(dá)到穩(wěn)態(tài)時(shí)，緩沖區(qū)中塊i已經(jīng)被下載的概率為pu(i)，則塊i+1被下載的概率為

從式(1)中可以看出，第i+1塊被下載是通過第i塊下載后右移一塊實(shí)現(xiàn)的，因此其概率是在本次時(shí)間段開始時(shí)第i塊已經(jīng)被下載的概率，加上在本次時(shí)間段結(jié)束時(shí)第i塊被以P2P方式下載的概率或從服務(wù)器處獲得數(shù)據(jù)的概率。pu(i)(1–pu(i))是節(jié)點(diǎn)沒有第i塊但其鄰居節(jié)點(diǎn)有的概率，表明可以從鄰居處下載；(1–pu(i))(1–pu(i))是節(jié)點(diǎn)沒有第 i塊同時(shí)在鄰居節(jié)點(diǎn)處也沒有找到的概率，表明只能從服務(wù)器處下載這個(gè)塊。需要注意的是，在每個(gè)時(shí)間段，服務(wù)器由于其連接數(shù)的限制不能全部應(yīng)答所有的節(jié)點(diǎn)請(qǐng)求，因此參數(shù)Ps表示的是服務(wù)器能夠服務(wù)本次請(qǐng)求的概率。式(2)表示的是緩沖區(qū)第一個(gè)塊能夠被服務(wù)器或者鄰居節(jié)點(diǎn)下載的概率值，|m|是節(jié)點(diǎn)的入度集元素個(gè)數(shù)，R是服務(wù)器等待隊(duì)列的節(jié)點(diǎn)數(shù)目。su(i)是節(jié)點(diǎn)p從鄰居節(jié)點(diǎn)k處請(qǐng)求第i塊時(shí)，p沒有塊i，但k有塊i的概率，su(i)計(jì)算可表示為（）

利用文獻(xiàn)[15]給出的su(i)的定義如下。

1) 最少優(yōu)先(標(biāo)記為r)

2) 貪婪策略(標(biāo)記為g)

其中，b是節(jié)點(diǎn)的平均緩沖區(qū)大小。

尋求的目標(biāo)是輔助節(jié)點(diǎn)根據(jù)自己的緩沖區(qū)大小來選擇合適的塊下載方案以達(dá)到盡快獲得需要的視頻數(shù)據(jù)的目的。通過式(1)和式(2)，建立差分方程如下:

節(jié)點(diǎn)在ui＜ δ時(shí)向服務(wù)器請(qǐng)求數(shù)據(jù)，由于有云分發(fā)服務(wù)器的存在，因此可以假設(shè)同一時(shí)間段內(nèi)所有節(jié)點(diǎn)的請(qǐng)求都能夠得到滿足，因此 Ps=1。同理，1/R的值也為 1。通過對(duì)上述數(shù)學(xué)模型的分析和計(jì)算，可以得出2個(gè)塊下載策略所需要的最小緩沖區(qū)大小值。

結(jié)論1 最少優(yōu)先方案需要的最小緩沖區(qū)為:i=（1-pr（i））-1+ c。

證明 從式(4)、式(6)和式(7)得到，最少優(yōu)先的差分方程為:d pr（i）di= pr（i）（1-pr（i ））2+ (1 -pr(i))3ps，解此差分方程得到di = d pr( i)/(pr(i)-1)2，從而得到

結(jié)論2 貪婪策略需要的最小緩沖區(qū)大小為:i=（1-pg（b））-1ln （pg（i-1）+c 。

證明 從式(5)得出

sg（i）=1- 1 R-pg（b）+pg（i+1）≥ 1-pg（b ）這是由于pg(i)是增函數(shù)且pg(0)=1/R，替換su(i)為1?pu(b)。從式(6)和式(7)可得，貪婪策略的差分方程為

解這個(gè)方程得到

文獻(xiàn)[15]觀察到緩沖區(qū)的靠前位置的數(shù)據(jù)使用最少優(yōu)先策略可以獲得較高的pu(i)，即能保證塊的高可用性。如圖3所示，以pu(i)= 0.94為例，當(dāng) 119×5＜bi–pi＜252×5(每塊的大小為 5 KB)時(shí)，2種塊下載策略中，選擇最少優(yōu)先會(huì)使塊i+1更容易被下載到。

圖3 最少優(yōu)先和貪婪策略最小緩沖區(qū)大小

4 模擬實(shí)驗(yàn)和性能分析

4.1 實(shí)驗(yàn)?zāi)M初始化

本文實(shí)驗(yàn)環(huán)境如下，Myeclipse 8.5平臺(tái)，雙核CPU和 4GB內(nèi)存的服務(wù)器。模擬實(shí)驗(yàn)是建立在PeerSim引擎基礎(chǔ)之上，這是為了保證盡可能地接近真實(shí)世界的情況。實(shí)驗(yàn)的參數(shù)設(shè)置如表1所示。

節(jié)點(diǎn)到達(dá)符合參數(shù)為1/4的泊松分布。每個(gè)節(jié)點(diǎn)最大有15個(gè)鄰居節(jié)點(diǎn)。節(jié)點(diǎn)每2min發(fā)送最新的下載點(diǎn)到 tracker服務(wù)器，實(shí)驗(yàn)運(yùn)行的結(jié)果數(shù)據(jù)每2min統(tǒng)計(jì)一次。

表1 模擬實(shí)驗(yàn)參數(shù)設(shè)置

4.2 模擬實(shí)驗(yàn)結(jié)果

1) 運(yùn)行時(shí)服務(wù)器帶寬開銷

如圖4所示，開始時(shí)在系統(tǒng)中沒有節(jié)點(diǎn)，因此由服務(wù)器應(yīng)答請(qǐng)求。隨著時(shí)間的增長(zhǎng)，一些節(jié)點(diǎn)加入到系統(tǒng)中，此時(shí)新加入節(jié)點(diǎn)能從早加入的節(jié)點(diǎn)處獲得數(shù)據(jù)，使服務(wù)器的帶寬開銷降低。在第5個(gè)時(shí)刻，一批新節(jié)點(diǎn)由于節(jié)點(diǎn)最大連接數(shù)的限制，部分節(jié)點(diǎn)沒有足夠的鄰居節(jié)點(diǎn)，服務(wù)器參與數(shù)據(jù)上傳而造成服務(wù)器負(fù)載的加重。可以看出隨著節(jié)點(diǎn)的加入服務(wù)器帶寬開銷逐步降低最后達(dá)到穩(wěn)定。通過計(jì)算，相比于BPB[6]服務(wù)器帶寬開銷降低大約6.16%。圖5顯示在不同參數(shù)0.2ε=和0.4ε=時(shí)的服務(wù)器帶寬開銷情況。隨著服務(wù)器返回的鄰居列表中節(jié)點(diǎn)數(shù)目的增加，大緩沖區(qū)節(jié)點(diǎn)被選中作為鄰居節(jié)點(diǎn)的概率加大，此時(shí)節(jié)點(diǎn)在沒有服務(wù)器參與的情況下也可以獲得足夠的下載速率來保持視頻平滑播放。需要注意的是:當(dāng)ε增大時(shí)，返回的鄰居列表也會(huì)增大，會(huì)導(dǎo)致額外的服務(wù)器帶寬開銷。設(shè)置γ的原因是:如果節(jié)點(diǎn)a和節(jié)點(diǎn)b下載點(diǎn)相近，下載點(diǎn)靠后的節(jié)點(diǎn)a達(dá)到最大連接數(shù)的概率較低，同時(shí)塊下載方案使 a可能擁有節(jié)點(diǎn)b所需要的視頻數(shù)據(jù)，可以根據(jù)不同的在線節(jié)點(diǎn)數(shù)目來選擇γ，這里取γ=0.1。當(dāng)參數(shù)ε從0.2～0.4時(shí)，服務(wù)器帶寬開銷降低了4.93%。

圖4 與BPB比較的服務(wù)器帶寬開銷

圖5 不同參數(shù)ε下的服務(wù)器帶寬開銷

2) 節(jié)點(diǎn)請(qǐng)求的拒絕率

為了研究節(jié)點(diǎn)請(qǐng)求拒絕情況，模擬實(shí)驗(yàn)監(jiān)視了每個(gè)節(jié)點(diǎn)如何發(fā)送下載請(qǐng)求和應(yīng)答來自其他節(jié)點(diǎn)請(qǐng)求的行為，并且記錄了請(qǐng)求被拒絕的數(shù)目。圖 6顯示NCS算法的拒絕次數(shù)下降了27.74%，導(dǎo)致這種現(xiàn)象的原因是:NCS使相似下載點(diǎn)的節(jié)點(diǎn)所需要的視頻數(shù)據(jù)即使在鄰居節(jié)點(diǎn)的緩沖區(qū)較小時(shí)也有較大的概率存在于鄰居節(jié)點(diǎn)的緩沖區(qū)中。圖7顯示，由于鄰居列表中的候選節(jié)點(diǎn)數(shù)目的增大，拒絕數(shù)明顯降低。

3) 節(jié)點(diǎn)的平均下載速率

節(jié)點(diǎn)下載速率是一個(gè)關(guān)鍵的評(píng)價(jià)指標(biāo)。為了保證播放的平滑性，下載速率應(yīng)該大于視頻播放速率 r。如果小于視頻播放率，缺少的速率就會(huì)從服務(wù)器處下載，這會(huì)增加服務(wù)器的帶寬開銷。圖8顯示NCS算法相比于BPB提升了5.23%的節(jié)點(diǎn)下載速率，這是由于NCS算法能夠從低連接數(shù)的節(jié)點(diǎn)處獲得視頻數(shù)據(jù)，同時(shí)，在降低了請(qǐng)求拒絕率的情況下，節(jié)點(diǎn)能夠較快地獲得視頻數(shù)據(jù)。圖 9顯示，在不同的參數(shù)ε下，平均下載速率提升了大約2.47%。

圖6 節(jié)點(diǎn)請(qǐng)求拒絕數(shù)

圖7 不同參數(shù)ε下節(jié)點(diǎn)請(qǐng)求拒絕數(shù)

圖8 節(jié)點(diǎn)的平均下載速率

圖9 不同參數(shù)ε下的節(jié)點(diǎn)評(píng)價(jià)下載速率

圖10 在不同小緩沖區(qū)，節(jié)點(diǎn)數(shù)目對(duì)服務(wù)器的帶寬開銷

4) 不同小緩沖區(qū)節(jié)點(diǎn)數(shù)目對(duì)服務(wù)器帶寬開銷影響

最后測(cè)試的是，當(dāng)擁有小緩沖區(qū)的節(jié)點(diǎn)數(shù)目不同時(shí)，服務(wù)器帶寬開銷情況。圖 10顯示當(dāng)網(wǎng)絡(luò)中小緩沖區(qū)節(jié)點(diǎn)數(shù)目占總節(jié)點(diǎn)數(shù)的10%、20%、30%、40%時(shí)服務(wù)器帶寬開銷變化情況。隨著小緩沖區(qū)節(jié)點(diǎn)數(shù)目的增加，服務(wù)器帶寬開銷僅有少量的增加。以網(wǎng)絡(luò)中小緩沖區(qū)節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)的10%為基準(zhǔn)，當(dāng)這個(gè)數(shù)值是 20%時(shí)，服務(wù)器帶寬開銷增加了4.78%、30%時(shí)增加了5.02%、40%時(shí)增加了5.14%。這表明隨著小緩沖區(qū)節(jié)點(diǎn)數(shù)目的增加，服務(wù)器帶寬開銷增加程度小于 6%，這是由于節(jié)點(diǎn)能夠從其他節(jié)點(diǎn)處獲得足夠的下載速率來保證平滑播放從而減少了對(duì)服務(wù)器的請(qǐng)求。

5 結(jié)束語(yǔ)

本文首先引入了云輔助的P2P-VoD系統(tǒng)架構(gòu)，并詳細(xì)闡述了不同緩沖區(qū)大小的節(jié)點(diǎn)在播放點(diǎn)異步時(shí)如何相互獲取視頻數(shù)據(jù)的節(jié)點(diǎn)選擇算法，通過減少對(duì)VoD服務(wù)提供商服務(wù)器的請(qǐng)求從而降低其帶寬開銷。其次，分析了2種不同的塊下載策略，為節(jié)點(diǎn)選擇哪些塊進(jìn)行優(yōu)先下載提供了依據(jù)，從而保證需要下載的塊都是高可用的。最后，模擬實(shí)驗(yàn)從服務(wù)器帶寬開銷、請(qǐng)求拒絕率和下載速率方面進(jìn)行了分析和比較，實(shí)驗(yàn)證明NCS算法可以取得比較好的效果。

下一步工作是設(shè)計(jì)一個(gè)基于稅收機(jī)制的分布式算法來激勵(lì)高能力節(jié)點(diǎn)盡可能多地貢獻(xiàn)自己資源，輔助低能力節(jié)點(diǎn)獲得充足的下載速率從而實(shí)現(xiàn)平滑播放，最終達(dá)到降低VoD供應(yīng)商服務(wù)器帶寬開銷的目的。

[1]YEUNG M K H, YU-KWONG K.On game theoretic peer selection for resilient peer-to-peer media streaming[J].Transactionss on Parallel and Distributed Systems, 2009, 20:1512-1525.

[2]PPLive[EB/OL].http://www.pptv.com/.

[3]YAN H, TOM Z J F, DAH-MING C, et al.Challenges, design and analysis of a large-scale P2P-VoD system[A].ACM SIGCOMM[C].2008.375-388.

[4]SHARMA A, BESTAVRORS A, MATTA I.dPAM:a distributed perfecting protocol for scalable asynchronous multicast in P2P systems[A].IEEE International Conference on Network Protocols (ICNP)[C].2005.1139-1150.

[5]LUPU E, SLOMAN M, DULAY N, et al.PONDER:performance aware P2P video on demand service[A].GLOBECOM[C].2007.225-230.

[6]CHAO L, ZHENGHUA F, YONG L.iPASS:incentivized peer-assisted system for asynchronous streaming[A].INFOCOM[C].2009.2741-2745.

[7]VLAVIANOS A, ILIOFOTOU M, FALOUTSOS M.Bitos:enhancing bittorrent for supporting streaming applications[A].IEEE Global Internet Symposium[C].2006.1-6.

[8]YIPENG Z, DAHMING C, LUI J C S.A simple model for analyzing P2P streaming protocols[A].IEEE International Conference on Network Protocols (ICNP)[C].2007.226-235.

[9]ZHEN M, KE X, YIFENG Z.Exploring the policy selection of P2P VoD system-a simulation based research[A].International Workshop on Quality of Service (IWQoS)[C].2012.1-4.

[10]HAITAO L, LILI Z, JIANGCHUAN L, et al.Cost-effective partial migration of VoD services to content clouds[A].IEEE International Conference on Cloud Computing[C].2011.203-210.

[11]Amazon[EB/OL].http://aws.amazon.com/cloudfront/.

[12]XIAO L, YUNHAO L, LIONEL M N.Improving unstructured peer-to-peer systems by adaptive connection establishment[J].IEEE Transactions on Computers, 2005, 54(9):1091-1103.

[13]YUNHAO L, XIAO L, ABDOL-HOSSEIN E, et al.Approaching optimal peer-to-peer overlays[A].13th Annual Meeting of IEEE MASCOTS[C].2005.407-414.

[14]YUNHAO L, XIAO L, XIAO L, et al.Location awareness in unstructured peer-to-peer systems[J].IEEE Transactions on Parallel and Distributed Systems, 2005, 16(2):163-174.

[15]LUI B Q Z J, DAH-MING C.Exploring the optimal chunk selection policy for data-driven P2P streaming systems[A].IEEE 9th International Conference on Peer-to-Peer Computing[C].2009.271-280.