分層P2P點播系統中優化的帶寬資源分配策略

陳 卓，馮 鋼，周 江

(1. 重慶理工大學計算機科學與工程學院 重慶 巴南區 400054; 2. 電子科技大學通信抗干擾技術國家級重點實驗室 成都 611731)

近年來，基于Peer-to-Peer技術(P2P)的視頻流媒體應用已成為最重要和應用最廣泛的互聯網應用。用戶節點從其他節點處獲取視頻流數據的同時，也利用自己的上行帶寬將所緩存的視頻流數據分發給鄰居節點。P2P流媒體系統以其良好的可擴展性、較低的服務器帶寬開銷等突出優勢，使目前眾多典型的視頻流媒體系統[1-4]均采用了P2P技術加以實現。

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

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

1 相關研究工作

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

2 視頻服務器的帶寬消耗模型

2.1 研究問題描述

雖然在P2P點播系統中，通過節點間的互助能夠有效地降低服務器的帶寬開銷[1]，但系統中存在的帶寬資源利用不均衡的問題，導致服務器開銷依然較大。特別在基于分層編碼技術的P2P點播系統中，對某些視頻數據的帶寬資源供需不均衡極容易導致服務器帶寬開銷的增加。

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

2.2 分層P2P VoD視頻分發模型

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

圖1 分層視頻內容的組織結構

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

2.3 服務器的帶寬資源開銷優化模型

假設系統中有N個節點正在點播同一個視頻節目。由于這些節點進入系統的時間隨機，使各節點當前正在觀看的視頻區域存在差異，也即表明這N個節點當前可以是正觀看S1～SK不同位置的內容。定義當前N個節點對某一個數據段Si,j總的帶寬資源需求為Di,j，可表示如下：

約束條件1)表示節點p對于視頻數據段Si,j分配的帶寬資源不能為負。約束條件2)表示對節點p所能分配的上行帶寬資源的限制，也即如果節點沒有緩存數據段Si,j，則不能向請求Si,j的節點分配帶寬資源。約束條件3)表示節點所能夠分配的帶寬資源受到其自身最大上行帶寬資源限制。約束條件4)表示分層視頻編碼所具有的解碼依賴關系，也即當節點 p 需要視頻內容Si,j時，視頻數據段Si,1,Si,2,…,Si,j-1也需同時獲取才能實現視頻解碼。

但上述優化問題是一個非線性優化問題，不易求解。因此把上述非線性優化問題轉化為一個等價的線性優化問題。實際上，系統中緩存了數據段Si,j的節點分配給Si,j的帶寬資源總和不應該多于系統中節點對Si,j的帶寬總需求。若在滿足了對數據段Si,j的帶寬資源供需平衡的前提下，緩存Si,j的節點可將多余的帶寬資源分配給其他數據段，而如果沒有緩存其他數據段，則保留多余的帶寬資源。因此，上述非線性優化問題可轉化為線性優化問題：

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

3.1 基于節點在線時間的相似性建立鄰居關系

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

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

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

在3.1節提出的基于節點在線觀看視頻時間相似性的基礎上，本節提出一種分層P2P點播系統中的帶寬資源分配策略。該策略包括同視頻層帶寬資源分配策略和跨視頻層帶寬資源分配策略。

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

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

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

2) 節點q在完成對其所在的視頻層Lv中節點的帶寬資源分配后，剩余帶寬auq≠0。

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

對于系統中的一個節點q，若該節點在線觀看視頻節目的時間為tq，且如果節點q同時收到來自n個鄰居節點的跨視頻層的帶寬資源請求。這時，節點q則成為這n個鄰居節點的跨層視頻服務節點。節點q按照在線觀看視頻的時長將這n個鄰居節點排列為p1, p2,…, pn，也即t1> t2,…, > tn。節點q將按照這n個節點的排列順序分配自己的剩余帶寬資源。該策略的主要目的是對于一個在線觀看視頻時間越長的節點，其緩存的視頻內容越多，能夠為更多的節點提供帶寬資源服務，因此應該優先予以服務。“幫者”的可用帶寬資源分配策略的偽碼如下所示。

4 數值結果與討論

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

本文分200個統計周期分別統計了視頻服務器的實時帶寬資源開銷，也即每隔36 s統計一次。圖2、圖3和圖4分別顯示了普通視頻、冷門視頻和熱門視頻場景下的服務器帶寬資源開銷。文獻[8]中所采用的隨機鄰居建立及帶寬分配策略稱為隨機策略。通過解式(6)的線性優化得到的理論最優值稱為最優化數值結果。

圖2顯示了對于普通視頻場景，在各個統計周期內，本文提出的策略都非常接近于解優化問題后得到的服務器帶寬消耗的理論最小值，這相對于隨機請求策略降低視頻服務器的帶寬消耗非常明顯。

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

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

圖2 普通視頻點播場景中服務器的帶寬資源消耗對比

圖3 普通視頻點播場景中節點的平均帶寬利用率

圖4 冷門視頻中服務器的帶寬資源消耗對比

圖4反映出對于冷門視頻，服務器的帶寬消耗的起伏較嚴重。其主要原因是因為進入冷門視頻頻道的節點速率較低，使停留在冷門視頻中并觀看視頻的節點數量較少，進一步使節點之間的帶寬提供互助行為較弱。同時，由于進入系統的節點的上行帶寬資源存在一定的隨機性，節點間帶寬互助也存在很大的隨機波動，使服務器消耗的帶寬在不同統計周期的存在較大的差異。

5 結 束 語

本文從鄰居選擇及帶寬分配策略的角度，對降低分層P2P點播系統中服務器的帶寬開銷問題進行了系統研究，首先從視頻數據的帶寬供需的角度，建立了最小服務器帶寬開銷的理論優化模型；并提出了一種基于在線觀看視頻時間相似性的鄰居選擇及同視頻層及跨視頻層的及帶寬分配策略。通過仿真實驗表明，本文的策略在各種視頻點播場景中都比已有的策略消耗更小的服務器帶寬。該研究成果有助于改善現有系統的設計。

[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.

編 輯 黃 莘