分層P2P點(diǎn)播系統(tǒng)中優(yōu)化的帶寬資源分配策略

陳 卓，馮 鋼，周 江

(1. 重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 重慶 巴南區(qū) 400054; 2. 電子科技大學(xué)通信抗干擾技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室 成都 611731)

近年來(lái)，基于Peer-to-Peer技術(shù)(P2P)的視頻流媒體應(yīng)用已成為最重要和應(yīng)用最廣泛的互聯(lián)網(wǎng)應(yīng)用。用戶節(jié)點(diǎn)從其他節(jié)點(diǎn)處獲取視頻流數(shù)據(jù)的同時(shí)，也利用自己的上行帶寬將所緩存的視頻流數(shù)據(jù)分發(fā)給鄰居節(jié)點(diǎn)。P2P流媒體系統(tǒng)以其良好的可擴(kuò)展性、較低的服務(wù)器帶寬開(kāi)銷等突出優(yōu)勢(shì)，使目前眾多典型的視頻流媒體系統(tǒng)[1-4]均采用了P2P技術(shù)加以實(shí)現(xiàn)。

P2P流媒體系統(tǒng)可分為P2P直播系統(tǒng)和P2P點(diǎn)播系統(tǒng)。在P2P直播系統(tǒng)中，先后進(jìn)入系統(tǒng)的節(jié)點(diǎn)的播放位置基本同步。而在P2P點(diǎn)播系統(tǒng)中，各節(jié)點(diǎn)的播放位置卻存在較大的差異。另外，P2P點(diǎn)播系統(tǒng)為了提高節(jié)點(diǎn)自己的互助，通常需要節(jié)點(diǎn)分配更大的存儲(chǔ)空間(如1 GB[1])將已觀看過(guò)的內(nèi)容進(jìn)行緩存以服務(wù)其他節(jié)點(diǎn)。P2P點(diǎn)播系統(tǒng)雖然吸引了大量用戶，但視頻服務(wù)提供商卻很難從中贏利[5]，其根本原因是服務(wù)提供商需要為大量的服務(wù)器帶寬消耗買單。因此，在保證用戶流暢的視頻播放的同時(shí)，如何有效地降低服務(wù)器的帶寬開(kāi)銷是P2P點(diǎn)播系統(tǒng)亟待研究并解決的問(wèn)題。

另一方面，使用分層視頻編碼技術(shù)能將原始視頻序列壓縮成多個(gè)視頻層，包括基本層和多個(gè)擴(kuò)展層。各層向下依賴，即高層視頻的正確解碼必須依靠其下的各視頻層的數(shù)據(jù)正確獲取。近年來(lái)，學(xué)界已將分層視頻編碼技術(shù)應(yīng)用到P2P流媒體系統(tǒng)中[6-8]，其目的是為了滿足節(jié)點(diǎn)對(duì)不同視頻質(zhì)量的多樣化需求。在這類系統(tǒng)中，節(jié)點(diǎn)能依據(jù)自身帶寬資源或?qū)Σ煌曨l質(zhì)量的需求，有選擇地注冊(cè)在不同的視頻層。注冊(cè)在不同視頻層的節(jié)點(diǎn)所需獲取的視頻流速率也不同，使節(jié)點(diǎn)感受到不同的視頻質(zhì)量。雖然在引入分層視頻編碼后，系統(tǒng)的彈性和自適應(yīng)性得以增強(qiáng)，但同時(shí)也使得分層P2P流媒體系統(tǒng)的優(yōu)化設(shè)計(jì)變得極具挑戰(zhàn)性。特別是當(dāng)鄰居選擇及帶寬分配不合理時(shí)，很容易導(dǎo)致視頻服務(wù)器的帶寬開(kāi)銷嚴(yán)重。本文從鄰居關(guān)系建立及帶寬分配的角度，研究降低基于分層視頻編碼技術(shù)的P2P點(diǎn)播系統(tǒng)(分層P2P點(diǎn)播系統(tǒng))中視頻服務(wù)器帶寬消耗的問(wèn)題。分析了分層P2P點(diǎn)播系統(tǒng)中服務(wù)器開(kāi)銷增加的主要原因，并給出視頻服務(wù)器帶寬開(kāi)銷的數(shù)學(xué)優(yōu)化模型。描述了基于節(jié)點(diǎn)在線時(shí)間相似性的鄰居關(guān)系建立及同層/跨層鄰居選擇帶寬分配策略。對(duì)提出的策略進(jìn)行實(shí)驗(yàn)評(píng)估，并給出相關(guān)結(jié)論。

1 相關(guān)研究工作

得益于互聯(lián)網(wǎng)用戶對(duì)視頻點(diǎn)播的大量應(yīng)用需求，國(guó)內(nèi)外學(xué)者就基于P2P技術(shù)的點(diǎn)播系統(tǒng)進(jìn)行了一系列的研究工作。文獻(xiàn)[9]建立了數(shù)學(xué)模型，對(duì)單視頻流P2P點(diǎn)播系統(tǒng)中不同的帶寬分配策略進(jìn)行了比較。文獻(xiàn)[10]分析了單視頻流P2P點(diǎn)播系統(tǒng)中存在視頻數(shù)據(jù)的供需不平衡的問(wèn)題，并提出了一種基于隊(duì)列技術(shù)的改進(jìn)策略。另外，文獻(xiàn)[11-13]主要考察在多視頻(多頻道)的場(chǎng)景下優(yōu)化的緩存管理機(jī)制，研究了當(dāng)節(jié)點(diǎn)緩存空間滿后，如何對(duì)緩存內(nèi)容進(jìn)行替換，以達(dá)到降低服務(wù)器帶寬開(kāi)銷的目的。學(xué)界目前對(duì)于采用分層視頻編碼的P2P點(diǎn)播系統(tǒng)的研究工作還相對(duì)較少，文獻(xiàn)[8]研究了分層P2P點(diǎn)播系統(tǒng)中降低起始延遲和保證視頻播放質(zhì)量的問(wèn)題，提出了一種基于zigzag的視頻數(shù)據(jù)段緊迫度評(píng)價(jià)機(jī)制和調(diào)度策略。文獻(xiàn)[14]提出了一種研究分層視頻P2P點(diǎn)播系統(tǒng)的分析模型，能夠預(yù)測(cè)系統(tǒng)在穩(wěn)定狀態(tài)下系統(tǒng)的平均吞吐量、節(jié)點(diǎn)平均播放質(zhì)量等關(guān)鍵系統(tǒng)參數(shù)。文獻(xiàn)[15]研究了在多個(gè)視頻播放階段中節(jié)點(diǎn)的視頻層選擇算法，并通過(guò)大量實(shí)驗(yàn)，評(píng)估了分層視頻P2P點(diǎn)播系統(tǒng)中節(jié)點(diǎn)的起始延遲和視頻質(zhì)量。目前還沒(méi)有從優(yōu)化鄰居選擇和帶寬資源分配的角度討論降低服務(wù)器帶寬開(kāi)銷的研究工作，而這正是本文的研究重點(diǎn)。

2 視頻服務(wù)器的帶寬消耗模型

2.1 研究問(wèn)題描述

雖然在P2P點(diǎn)播系統(tǒng)中，通過(guò)節(jié)點(diǎn)間的互助能夠有效地降低服務(wù)器的帶寬開(kāi)銷[1]，但系統(tǒng)中存在的帶寬資源利用不均衡的問(wèn)題，導(dǎo)致服務(wù)器開(kāi)銷依然較大。特別在基于分層編碼技術(shù)的P2P點(diǎn)播系統(tǒng)中，對(duì)某些視頻數(shù)據(jù)的帶寬資源供需不均衡極容易導(dǎo)致服務(wù)器帶寬開(kāi)銷的增加。

分層P2P點(diǎn)播系統(tǒng)中帶寬資源供需不均衡問(wèn)題主要由兩個(gè)因素所致：1) 某個(gè)節(jié)點(diǎn)p擁有足夠的上行帶寬資源，但卻沒(méi)有緩存其他鄰居節(jié)點(diǎn)所需要的數(shù)據(jù)，使p的帶寬資源無(wú)法有效的利用，而其他鄰居節(jié)點(diǎn)所需的視頻數(shù)據(jù)只能通過(guò)視頻服務(wù)器獲取。特別是當(dāng)考慮用戶連續(xù)點(diǎn)播多個(gè)視頻時(shí)[13]，用戶需要在存儲(chǔ)空間滿時(shí)決策如何對(duì)緩存數(shù)據(jù)進(jìn)行替換。2)某個(gè)節(jié)點(diǎn)p緩存了節(jié)點(diǎn)q所需的數(shù)據(jù)，但由于p的帶寬資源已經(jīng)分配給其他鄰居節(jié)點(diǎn)，導(dǎo)致q無(wú)法獲得服務(wù)。本文重點(diǎn)考察多個(gè)用戶點(diǎn)播同一個(gè)分層視頻節(jié)目，假設(shè)用戶的緩存空間足夠存放一個(gè)完整的分層視頻。主要從上述第二個(gè)因素加以考察，研究新的鄰居關(guān)系建立及帶寬資源分配策略，以降低視頻服務(wù)器的開(kāi)銷。

2.2 分層P2P VoD視頻分發(fā)模型

假設(shè)整個(gè)視頻內(nèi)容分為K個(gè)等長(zhǎng)的視頻區(qū)域(section)，而一個(gè)視頻區(qū)域是由多個(gè)分別屬于不同視頻層的數(shù)據(jù)段(segment)構(gòu)成。若該視頻節(jié)目分解為J個(gè)視頻層，則每個(gè)視頻區(qū)域則包括了J個(gè)數(shù)據(jù)段。如圖1所示，視頻內(nèi)容分解為S1,S2,…,SK個(gè)視頻區(qū)域。對(duì)于其中的任意一個(gè)Si，包括了Si,1,Si,2,…,Si,J一共J個(gè)數(shù)據(jù)段，其中，1≤i≤K。

圖1 分層視頻內(nèi)容的組織結(jié)構(gòu)

假設(shè)點(diǎn)播節(jié)點(diǎn)的存儲(chǔ)空間足夠緩存整個(gè)視頻內(nèi)容。只要一個(gè)節(jié)點(diǎn)p緩存了部分視頻內(nèi)容，就可以利用自己的上行帶寬將緩存內(nèi)容提供給請(qǐng)求節(jié)點(diǎn)。若節(jié)點(diǎn)p注冊(cè)在視頻層Lj(1≤j≤J)，且正觀看到視頻區(qū)域Si。根據(jù)分層視頻編碼的解碼依賴性原理，若節(jié)點(diǎn)p要保證流暢的視頻播放，則需要同時(shí)獲得視頻層L1～Lj的數(shù)據(jù)段Si,1,Si,2,…,Si,j。進(jìn)一步，由于第Lj層的各數(shù)據(jù)段都具有相同的視頻流解碼速率rj，則節(jié)點(diǎn)p需要獲得的視頻流速率為另外，只要某個(gè)節(jié)點(diǎn)q緩存了節(jié)點(diǎn)p所需的視頻內(nèi)容，則節(jié)點(diǎn)q成為節(jié)點(diǎn)p潛在的服務(wù)節(jié)點(diǎn)，特別說(shuō)明不論p，q是否處于相同的視頻層。

2.3 服務(wù)器的帶寬資源開(kāi)銷優(yōu)化模型

假設(shè)系統(tǒng)中有N個(gè)節(jié)點(diǎn)正在點(diǎn)播同一個(gè)視頻節(jié)目。由于這些節(jié)點(diǎn)進(jìn)入系統(tǒng)的時(shí)間隨機(jī)，使各節(jié)點(diǎn)當(dāng)前正在觀看的視頻區(qū)域存在差異，也即表明這N個(gè)節(jié)點(diǎn)當(dāng)前可以是正觀看S1～SK不同位置的內(nèi)容。定義當(dāng)前N個(gè)節(jié)點(diǎn)對(duì)某一個(gè)數(shù)據(jù)段Si,j總的帶寬資源需求為Di,j，可表示如下：

約束條件1)表示節(jié)點(diǎn)p對(duì)于視頻數(shù)據(jù)段Si,j分配的帶寬資源不能為負(fù)。約束條件2)表示對(duì)節(jié)點(diǎn)p所能分配的上行帶寬資源的限制，也即如果節(jié)點(diǎn)沒(méi)有緩存數(shù)據(jù)段Si,j，則不能向請(qǐng)求Si,j的節(jié)點(diǎn)分配帶寬資源。約束條件3)表示節(jié)點(diǎn)所能夠分配的帶寬資源受到其自身最大上行帶寬資源限制。約束條件4)表示分層視頻編碼所具有的解碼依賴關(guān)系，也即當(dāng)節(jié)點(diǎn) p 需要視頻內(nèi)容Si,j時(shí)，視頻數(shù)據(jù)段Si,1,Si,2,…,Si,j-1也需同時(shí)獲取才能實(shí)現(xiàn)視頻解碼。

但上述優(yōu)化問(wèn)題是一個(gè)非線性優(yōu)化問(wèn)題，不易求解。因此把上述非線性優(yōu)化問(wèn)題轉(zhuǎn)化為一個(gè)等價(jià)的線性優(yōu)化問(wèn)題。實(shí)際上，系統(tǒng)中緩存了數(shù)據(jù)段Si,j的節(jié)點(diǎn)分配給Si,j的帶寬資源總和不應(yīng)該多于系統(tǒng)中節(jié)點(diǎn)對(duì)Si,j的帶寬總需求。若在滿足了對(duì)數(shù)據(jù)段Si,j的帶寬資源供需平衡的前提下，緩存Si,j的節(jié)點(diǎn)可將多余的帶寬資源分配給其他數(shù)據(jù)段，而如果沒(méi)有緩存其他數(shù)據(jù)段，則保留多余的帶寬資源。因此，上述非線性優(yōu)化問(wèn)題可轉(zhuǎn)化為線性優(yōu)化問(wèn)題：

3 基于在線時(shí)間相似性的鄰居選擇及帶寬資源分配策略

3.1 基于節(jié)點(diǎn)在線時(shí)間的相似性建立鄰居關(guān)系

在分層P2P點(diǎn)播系統(tǒng)中，節(jié)點(diǎn)所緩存的視頻數(shù)據(jù)的多寡和節(jié)點(diǎn)在線觀看視頻的時(shí)間密切相關(guān)。也即觀看某個(gè)視頻時(shí)間越久的在線節(jié)點(diǎn)其磁盤空間中緩存的視頻數(shù)據(jù)也越多。這也意味著一個(gè)在線時(shí)間長(zhǎng)度為tp的節(jié)點(diǎn)p，只能從在線時(shí)間長(zhǎng)于tp的在線節(jié)點(diǎn)處獲取所需的視頻數(shù)據(jù)。若P2P點(diǎn)播系統(tǒng)中的管理節(jié)點(diǎn)(Tracker)能夠增加記錄系統(tǒng)中節(jié)點(diǎn)的在線時(shí)間長(zhǎng)度以及所節(jié)點(diǎn)所注冊(cè)的視頻層Lj(1≤j≤J)，則能有效地幫助新進(jìn)入系統(tǒng)的節(jié)點(diǎn)建立合理的鄰居關(guān)系。

若在視頻層Lj一共有kj個(gè)在線節(jié)點(diǎn)正在點(diǎn)播視頻節(jié)目。不失一般性，管理節(jié)點(diǎn)依據(jù)這kj個(gè)節(jié)點(diǎn)的在線時(shí)間長(zhǎng)度將節(jié)點(diǎn)進(jìn)行排序，記為：p1, p2,…, p|kj|，這意味著kj個(gè)節(jié)點(diǎn)的在線時(shí)間滿足t1≥t2≥…≥t|kj|。對(duì)于處于同視頻層的任意兩個(gè)在線節(jié)點(diǎn)pj為pk，若tj≥tk，則稱pj為pk的前驅(qū)節(jié)點(diǎn)。而一個(gè)在時(shí)間點(diǎn)tk進(jìn)入系統(tǒng)的節(jié)點(diǎn)pk首先經(jīng)由管理節(jié)點(diǎn)獲得在線時(shí)間和自己相似的m個(gè)前驅(qū)節(jié)點(diǎn)pk-1,pk-2,…, pk-m的信息。這m個(gè)前驅(qū)節(jié)點(diǎn)采用3.2節(jié)描述的同層帶寬資源分配策略，為節(jié)點(diǎn)pk分配其所需的L1～Lj層視頻流。另外，由于視頻解碼依賴性的因素，使處于視頻層Lj+1,Lj+2,…, LJ的節(jié)點(diǎn)在滿足同層節(jié)點(diǎn)的帶寬資源分配后，若仍有剩余上行帶寬資源，則能夠成為節(jié)點(diǎn)pk的潛在服務(wù)節(jié)點(diǎn)。管理節(jié)點(diǎn)能夠?yàn)楣?jié)點(diǎn)pk提供部分與其在線時(shí)間相似的處于其他視頻層的節(jié)點(diǎn)信息。這也意味著當(dāng)節(jié)點(diǎn)pk在無(wú)法從同視頻層的前驅(qū)節(jié)點(diǎn)獲得足夠視頻流時(shí)，還可以向其他視頻層中緩存了所需視頻數(shù)據(jù)的節(jié)點(diǎn)請(qǐng)求帶寬資源，進(jìn)一步降低分層P2P點(diǎn)播系統(tǒng)中視頻服務(wù)器的帶寬資源開(kāi)銷。

3.2 同層/跨層帶寬資源分配策略

在3.1節(jié)提出的基于節(jié)點(diǎn)在線觀看視頻時(shí)間相似性的基礎(chǔ)上，本節(jié)提出一種分層P2P點(diǎn)播系統(tǒng)中的帶寬資源分配策略。該策略包括同視頻層帶寬資源分配策略和跨視頻層帶寬資源分配策略。

1) 同視頻層帶寬資源分配策略。通過(guò)3.1節(jié)鄰居關(guān)系的建立，使得處于視頻層Lj的節(jié)點(diǎn)pk同時(shí)擁有處于同視頻層和其他視頻層的多個(gè)鄰居節(jié)點(diǎn)。由于處于同視頻層的節(jié)點(diǎn)的帶寬資源往往近似，且更容易使節(jié)點(diǎn)pk獲取到所需的視頻層L1～Lj的視頻數(shù)據(jù)。因此節(jié)點(diǎn)pk優(yōu)先向與自己在線時(shí)間相似的同層鄰居節(jié)點(diǎn)(部分前驅(qū)節(jié)點(diǎn))請(qǐng)求帶寬資源。節(jié)點(diǎn)pk先從在線時(shí)間距離tk最近的鄰居節(jié)點(diǎn)pk-1請(qǐng)求帶寬資源，如果pk-1的可用上行帶寬資源無(wú)法滿足，則再依次向其他鄰居節(jié)點(diǎn)pk-2,pk-3,…, pk-m請(qǐng)求帶寬資源，pk,…, pk-m的在線時(shí)間滿足tk≤…≤ tk-m+1≤tk-m。

對(duì)于處于視頻Lj的節(jié)點(diǎn)pk而言，要獲取到自己所需的視頻播放質(zhì)量，則需要同時(shí)獲得L1~Lj各層足夠的視頻流，即r1,r2,…, rj。如果節(jié)點(diǎn)pk在某個(gè)視頻層Li(1≤i≤j)不能通過(guò)同視頻層上的鄰居節(jié)點(diǎn)(部分前驅(qū)節(jié)點(diǎn))獲得足夠的視頻流，則pk需要通過(guò)向能提供Li層視頻流數(shù)據(jù)的異層節(jié)點(diǎn)q請(qǐng)求。本文稱這類跨層的服務(wù)節(jié)點(diǎn)為“幫助者”。節(jié)點(diǎn)pk在Lj層的“幫助者”q應(yīng)具有兩個(gè)條件：

1) q和pk不在同一視頻層，但q必須緩存了pk所需的視頻層Lj的數(shù)據(jù)。由于視頻解碼的依賴關(guān)系，能成為節(jié)點(diǎn)p在視頻層Lj(1≤j≤J)的“幫助者”q所處的視頻層Lv應(yīng)滿足j

2) 節(jié)點(diǎn)q在完成對(duì)其所在的視頻層Lv中節(jié)點(diǎn)的帶寬資源分配后，剩余帶寬auq≠0。

同層/跨層帶寬資源分配策略的偽碼描述如下：

對(duì)于系統(tǒng)中的一個(gè)節(jié)點(diǎn)q，若該節(jié)點(diǎn)在線觀看視頻節(jié)目的時(shí)間為tq，且如果節(jié)點(diǎn)q同時(shí)收到來(lái)自n個(gè)鄰居節(jié)點(diǎn)的跨視頻層的帶寬資源請(qǐng)求。這時(shí)，節(jié)點(diǎn)q則成為這n個(gè)鄰居節(jié)點(diǎn)的跨層視頻服務(wù)節(jié)點(diǎn)。節(jié)點(diǎn)q按照在線觀看視頻的時(shí)長(zhǎng)將這n個(gè)鄰居節(jié)點(diǎn)排列為p1, p2,…, pn，也即t1> t2,…, > tn。節(jié)點(diǎn)q將按照這n個(gè)節(jié)點(diǎn)的排列順序分配自己的剩余帶寬資源。該策略的主要目的是對(duì)于一個(gè)在線觀看視頻時(shí)間越長(zhǎng)的節(jié)點(diǎn)，其緩存的視頻內(nèi)容越多，能夠?yàn)楦嗟墓?jié)點(diǎn)提供帶寬資源服務(wù)，因此應(yīng)該優(yōu)先予以服務(wù)?！皫驼摺钡目捎脦捹Y源分配策略的偽碼如下所示。

4 數(shù)值結(jié)果與討論

本文采用Matlab實(shí)現(xiàn)了一個(gè)動(dòng)態(tài)仿真平臺(tái)模擬分層P2P點(diǎn)播系統(tǒng)。實(shí)驗(yàn)中的節(jié)點(diǎn)規(guī)模為5 000，視頻長(zhǎng)度為60 m in，且整個(gè)視頻內(nèi)容切分為100個(gè)等長(zhǎng)的視頻區(qū)域(Section)，即每一個(gè)視頻區(qū)域的播放時(shí)間為36 s。源視頻分解為3個(gè)視頻層L1, L2和L3。且r1=300 kb/s，r2=200 kb/s，r3=100 kb/s，這也表示節(jié)點(diǎn)注冊(cè)到視頻層L1, L2和L3分別需要至少R1=300 kb/s, R2=500 kb/s和R3=600 kb/s的下行帶寬資源。定義節(jié)點(diǎn)的下行帶寬分布于區(qū)間[R1, R2], [R2, R3]和[R3, 1.5R3]的比例為1:1:1。在同一帶寬區(qū)間內(nèi)，節(jié)點(diǎn)的下行帶寬服從均勻分布。類似于文獻(xiàn)[1, 8]，節(jié)點(diǎn)組織成一個(gè)“網(wǎng)狀”結(jié)構(gòu)的重疊網(wǎng)絡(luò)。每個(gè)節(jié)點(diǎn)的鄰居個(gè)數(shù)設(shè)置為8～10個(gè)[1]。為了充分評(píng)估算法的性能，本文比較了在普通視頻、冷門視頻和熱門視頻3種視頻點(diǎn)播場(chǎng)景下各種策略的性能，分別以參數(shù)為λ0=30，10，60的泊松流表示節(jié)點(diǎn)進(jìn)入普通視頻，冷門視頻和熱門視頻的速率。根據(jù)文獻(xiàn)[1]對(duì)實(shí)際系統(tǒng)PPLive的測(cè)量，節(jié)點(diǎn)觀看視頻片段的時(shí)間(在線時(shí)間)服從近似的指數(shù)分布，因此分別設(shè)置參數(shù)μ=50，20，80的指數(shù)分布模擬節(jié)點(diǎn)觀看普通視頻，冷門視頻和熱門視頻的時(shí)間長(zhǎng)度分布。另外需要說(shuō)明的是，為求解式(6)的優(yōu)化問(wèn)題，需在不同的統(tǒng)計(jì)點(diǎn)動(dòng)態(tài)記錄系統(tǒng)當(dāng)前的以及節(jié)點(diǎn)的帶寬資源總需求和總供應(yīng)。而當(dāng)系統(tǒng)中的在線節(jié)點(diǎn)規(guī)模較大時(shí)需求解大規(guī)模的線性優(yōu)化，如在仿真系統(tǒng)的100個(gè)統(tǒng)計(jì)周期以后，每統(tǒng)計(jì)一次理論最優(yōu)解，需解一個(gè)3′105～6′105個(gè)變量的大規(guī)模線性優(yōu)化。

本文分200個(gè)統(tǒng)計(jì)周期分別統(tǒng)計(jì)了視頻服務(wù)器的實(shí)時(shí)帶寬資源開(kāi)銷，也即每隔36 s統(tǒng)計(jì)一次。圖2、圖3和圖4分別顯示了普通視頻、冷門視頻和熱門視頻場(chǎng)景下的服務(wù)器帶寬資源開(kāi)銷。文獻(xiàn)[8]中所采用的隨機(jī)鄰居建立及帶寬分配策略稱為隨機(jī)策略。通過(guò)解式(6)的線性優(yōu)化得到的理論最優(yōu)值稱為最優(yōu)化數(shù)值結(jié)果。

圖2顯示了對(duì)于普通視頻場(chǎng)景，在各個(gè)統(tǒng)計(jì)周期內(nèi)，本文提出的策略都非常接近于解優(yōu)化問(wèn)題后得到的服務(wù)器帶寬消耗的理論最小值，這相對(duì)于隨機(jī)請(qǐng)求策略降低視頻服務(wù)器的帶寬消耗非常明顯。

另外，可以看到在第100個(gè)統(tǒng)計(jì)周期(等于整個(gè)視頻文件的時(shí)長(zhǎng))以前，視頻服務(wù)器的帶寬資源消耗逐步上升的過(guò)程；但到了100個(gè)統(tǒng)計(jì)周期以后，視頻服務(wù)器的帶寬開(kāi)銷呈現(xiàn)出平穩(wěn)的特性。其中，理論最小的服務(wù)器帶寬資源開(kāi)銷平均值為86.3 Mb/s，采用本文提出的策略所需平均服務(wù)器帶寬資源為92.8 Mb/s，而采用隨機(jī)策略時(shí)，服務(wù)器所需的平均帶寬資源開(kāi)銷則為126.4 Mb/s。在前100個(gè)統(tǒng)計(jì)周期內(nèi)系統(tǒng)中，節(jié)點(diǎn)數(shù)量穩(wěn)步增加，從而使服務(wù)器的帶寬消耗也穩(wěn)步增加。進(jìn)一步分析發(fā)現(xiàn)其主要原因是這段時(shí)間只有節(jié)點(diǎn)異常退出系統(tǒng)的情況，而使節(jié)點(diǎn)進(jìn)入系統(tǒng)的速率是大于節(jié)點(diǎn)離開(kāi)系統(tǒng)的速率，導(dǎo)致了節(jié)點(diǎn)數(shù)量穩(wěn)步增加。而在100個(gè)統(tǒng)計(jì)周期后，系統(tǒng)中節(jié)點(diǎn)的退出包括異常退出和觀看完整個(gè)視頻退出兩種情況，使節(jié)點(diǎn)進(jìn)入系統(tǒng)的速率基本等于節(jié)點(diǎn)退出系統(tǒng)的速率，進(jìn)而使整個(gè)系統(tǒng)中的節(jié)點(diǎn)總數(shù)趨于動(dòng)態(tài)穩(wěn)定。因此導(dǎo)致服務(wù)器的帶寬資源消耗也趨于穩(wěn)定。

圖3顯示了在普通視頻點(diǎn)播場(chǎng)景中節(jié)點(diǎn)的上行帶寬利用率，可以看到在第12個(gè)統(tǒng)計(jì)周期以后，采用本文的策略使節(jié)點(diǎn)的上行帶寬利用率均在90%以上，并最終在95%上下浮動(dòng)。相比之下，采用隨機(jī)策略的上行帶寬利用率在83%上下浮動(dòng)。由于節(jié)點(diǎn)按照從相距自己進(jìn)入頻道時(shí)間最接近的同層/異層的在線節(jié)點(diǎn)中選取鄰居節(jié)點(diǎn)，有效地避免了部分請(qǐng)求節(jié)點(diǎn)所需帶寬資源無(wú)法得到服務(wù)，而部分節(jié)點(diǎn)的上行帶寬資源卻沒(méi)有充分利用的問(wèn)題。該圖也進(jìn)一步表明了本文的策略能夠有效地提高節(jié)點(diǎn)之間的互助，從而實(shí)現(xiàn)降低服務(wù)器帶寬資源開(kāi)銷的問(wèn)題。

圖2 普通視頻點(diǎn)播場(chǎng)景中服務(wù)器的帶寬資源消耗對(duì)比

圖3 普通視頻點(diǎn)播場(chǎng)景中節(jié)點(diǎn)的平均帶寬利用率

圖4 冷門視頻中服務(wù)器的帶寬資源消耗對(duì)比

圖4反映出對(duì)于冷門視頻，服務(wù)器的帶寬消耗的起伏較嚴(yán)重。其主要原因是因?yàn)檫M(jìn)入冷門視頻頻道的節(jié)點(diǎn)速率較低，使停留在冷門視頻中并觀看視頻的節(jié)點(diǎn)數(shù)量較少，進(jìn)一步使節(jié)點(diǎn)之間的帶寬提供互助行為較弱。同時(shí)，由于進(jìn)入系統(tǒng)的節(jié)點(diǎn)的上行帶寬資源存在一定的隨機(jī)性，節(jié)點(diǎn)間帶寬互助也存在很大的隨機(jī)波動(dòng)，使服務(wù)器消耗的帶寬在不同統(tǒng)計(jì)周期的存在較大的差異。

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

本文從鄰居選擇及帶寬分配策略的角度，對(duì)降低分層P2P點(diǎn)播系統(tǒng)中服務(wù)器的帶寬開(kāi)銷問(wèn)題進(jìn)行了系統(tǒng)研究，首先從視頻數(shù)據(jù)的帶寬供需的角度，建立了最小服務(wù)器帶寬開(kāi)銷的理論優(yōu)化模型；并提出了一種基于在線觀看視頻時(shí)間相似性的鄰居選擇及同視頻層及跨視頻層的及帶寬分配策略。通過(guò)仿真實(shí)驗(yàn)表明，本文的策略在各種視頻點(diǎn)播場(chǎng)景中都比已有的策略消耗更小的服務(wù)器帶寬。該研究成果有助于改善現(xiàn)有系統(tǒng)的設(shè)計(jì)。

[1] HUANG Yan, FU Zhen-jia, CHIU Dah-ming. Challenges,design and analysis of a large scale P2P-VoD system[C]//Proceedings of the ACM SIGCOMM. Seattle, USA:ACM, 2008: 375-388.

[2] LIU Zi-mu, WU Chuan, LI Bao-chun, et al. UUSee:large-scale operational on-demand stream ing w ith random network coding[C]//Proceedings of the IEEE INFOCOM.San Diego, USA: IEEE, 2010: 1-9.

[3] XIE Su-su, LI Bo, KEUNG G Y, et al. The coolstreaming:Design, theory and practice[J]. IEEE Transactions on Multimedia, Special Issue on Content Storage and Delivery in Peer-to-Peer Network, 2007, 9(8): 1661-167.

[4] GILL P, ARLITT M, LI Zong-peng, et al. YouTube traffic characterization: a view from the edge[C]//Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement. San Diego, USA: ACM, 2007:15-28.

[5] HUANG Cheng, LI Jin, KEITH R. Can Internet video-on-demand be profitable[C]//Proceedings of ACM SIGCOMM. Kyoto: ACM, 2007:133-144.

[6] XIAO Xin, SHI Yuan-chun, GAO Yuan, et al. LayerP2P: a new data scheduling approach for layered stream ing in heterogeneous networks[C]//Proceedings of IEEE INFOCOM. Rio de Janeiro: IEEE, 2009: 603-611.

[7] M IESHOKRAIE S, HEFEED A M. Live peer-to-peer stream ing w ith scalable video coding and network coding[C]//ACM Multimedia Systems. Scottsdale, USA:ACM, 2010: 123-132.

[8] DING Yan, LIU Jiang-chuan, WANG Dan, et al.Peer-to-peer video-on-demand with scalable video coding[J].Elsevier Computer Communications, Special Issue on Multimedia Networking and Security in Convergent Networks, 2009, 33(14): 1589-1597.

[9] PARVEZ N, W ILLIAMSON C, MAHANTI A, et al.Analysis of bittorrent-like protocols for on-demand stored media streaming[C]//Proceedings of ACM SIGMETRICS.Annapolis: ACM, 2008: 301-312.

[10] YANG Yan, CHOW A, GOLUBCHIK L, et al. Improving QoS in BitTorrent-like VoD systems[C]//Proceedings of IEEE INFOCOM. San Diego: IEEE, 2010: 1-9.

[11] ZHOU Yi-peng, FU Zhen-jia, CHIU D M. Divisionof-labor between server and P2P for streaming VoD[C]//Proceedings of IEEE IWQoS. Coimbra: IEEE,2012: 1-9.

[12] ZHOU Y P, FU T Z J, CHIU D M. A unifying model and analysis of P2P VoD replication and scheduling[C]//Proceedings of IEEE INFOCOM. Shanghai: IEEE, 2012:1530-1538.

[13] ZHOU Yi-peng, FU Zhen-jia, CHIU D M. Server-assisted adaptive video replication for P2P VoD[J]. Elsevier Journal of Signal Processing: Image Communication, Advances in 2D/3D Video Stream ing Over P2P Networks, 2012, 27(4):484-495.

[14] MOKHTARIAN K, HEFEEDA M. Analysis of peer-assisted video-on-demand systems w ith scalable video streams[C]//Proceedings of ACM Multimedia Systems.Scottsdale, USA: ACM, 2010:133-143.

[15] ABBOUD O, ZINNER T, PUSSEP K, et al. On the impact of quality adaptation in svc-based P2P video-on-demand systems[C]//Proceedings of ACM Multimedia Systems.San Jose: ACM, 2011: 223-232.

編 輯 黃 莘