云輔助P2P-VoD系統中一種鄰居選擇算法

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

（1.北京郵電大學 網絡與交換技術國家重點實驗室，北京 100876；2.遼寧工程技術大學 電子與信息工程學院，遼寧 葫蘆島 125105）

1 引言

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

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

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

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

1）詳細研究小緩沖區節點對P2P-VoD系統的影響，設計基于緩沖區的節點選擇算法，能夠使節點以高概率選擇到提供視頻數據的鄰居節點。

2）在云輔助P2P-VoD架構下，計算2種不同的塊下載策略——最少優先和貪婪策略所需要的最小緩沖區的值，并以此為基礎為不同緩沖區大小的節點選擇合適的塊下載方案以達到系統中視頻數據塊的高可用性提供理論依據。

3）建立云輔助P2P-VoD模擬器來評估NCS算法性能。實驗表明，提出的算法能夠降低服務器負載和請求的拒絕率，提升節點的下載速率。同時也研究了不同移動設備在系統中占據的比例不同時，服務器負載的變化情況。結果表明，隨著小緩沖區節點的增加，服務器負載的增加程度較低。

2 云輔助P2P-VoD系統架構

如圖1所示，云輔助P2P-VoD系統中主要由4個組成部分，分別是節點、視頻提供商存儲服務器和tracker服務器、云存儲服務器和云分發服務器，各部分功能如下。

圖1 云輔助P2P-VoD系統架構

節點:使用各種設備在系統中觀看視頻的用戶。它們從視頻提供商存儲服務器，云分發服務器或其他節點處下載視頻數據；同時也將緩沖區中的視頻數據共享給其他節點。

視頻提供商存儲服務器:負責存儲視頻源和分發視頻數據。當一天之中節點的請求處于空閑時段時，由其獨立地提供服務。當服務器負載很重時，提前發送高流行度視頻數據到云存儲服務器中[10]。

視頻提供商tracker服務器:負責記錄節點到達的時間并依據下載點對節點進行排序；返回節點的鄰居列表。

云存儲服務器:歸屬于云提供商，例如Amazon。它負責接收來自視頻提供商存儲服務器發送的視頻數據并將其轉發到云分發服務器上。

云分發服務器:例如CloudFront[11]，使用整個云網絡服務器，自動將視頻內容發送到離請求節點最近的位于網絡邊緣的服務器上，如圖1所示，節點c向云服務器請求數據時，云分發服務器先將數據調度到位于云網絡邊緣距離節點c較近的服務器a上，由服務器a應答。

在上述架構基礎上，本文考慮如何通過節點間的有效合作來降低 VoD服務提供商的服務器帶寬開銷，同時直接降低云分發服務器的開銷。

3 NCS算法

3.1 節點緩沖區模型

對于云輔助P2P-VoD系統中的節點，考慮3個特征:節點的播放點是異步的；節點必須提前下載當前播放點的數據；不同節點的緩沖區大小是不同的。為了描述基于緩沖區的鄰居選擇算法，首先引入一些定義來建模節點視頻的緩沖區，如圖2所示。

播放點Pi:節點i當前的播放點，是正在播放視頻塊的序號。

下載點bi:在播放點Pi之后的第一個未下載的塊的序號。

平滑級ui:在播放點Pi之后還能持續播放的塊的數量，等于bi?Pi。標識的是節點播放平滑性。

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

緩沖區大小si:節點i 的存儲視頻數據的存儲區大小。

圖2中，為了保證播放的平滑性，節點a正在下載的塊(bi+1)是急需的，而節點b正在下載的塊在δ之后，對于節點b來說，當前下載的塊是不急需的。節點b的貢獻程度應該大于節點a，一方面是因為其從系統中獲取了更多的視頻數據(節點 b的播放點大于節點a)，需要更多的回報系統，另一方面此時上傳視頻數據到其他節點不會影響節點b的播放平滑性。

圖2 節點緩沖區定義

3.2 基于緩沖區的節點選擇算法

文獻[6]證明了隨機節點選擇算法效率是很低的，同時也提出了基于緩沖區的節點數據交換過程，但其未考慮系統中存在小緩沖區節點時的情況。本文提出一種基于下載點的節點選擇算法，即有相似下載點的節點為鄰居進行視頻數據共享，這些節點形成Overlay網絡。相似的下載點保證請求的視頻數據能夠以較大的概率存在于被請求的節點緩沖區中。

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

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

3.3 最少優先和貪婪的塊下載算法

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

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

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

1) 最少優先(標記為r)

2) 貪婪策略(標記為g)

其中，b是節點的平均緩沖區大小。

尋求的目標是輔助節點根據自己的緩沖區大小來選擇合適的塊下載方案以達到盡快獲得需要的視頻數據的目的。通過式(1)和式(2)，建立差分方程如下:

節點在ui＜ δ時向服務器請求數據，由于有云分發服務器的存在，因此可以假設同一時間段內所有節點的請求都能夠得到滿足，因此 Ps=1。同理，1/R的值也為 1。通過對上述數學模型的分析和計算，可以得出2個塊下載策略所需要的最小緩沖區大小值。

結論1 最少優先方案需要的最小緩沖區為:i=（1-pr（i））-1+ c。

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

結論2 貪婪策略需要的最小緩沖區大小為: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)是增函數且pg(0)=1/R，替換su(i)為1?pu(b)。從式(6)和式(7)可得，貪婪策略的差分方程為

解這個方程得到

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

圖3 最少優先和貪婪策略最小緩沖區大小

4 模擬實驗和性能分析

4.1 實驗模擬初始化

本文實驗環境如下，Myeclipse 8.5平臺，雙核CPU和 4GB內存的服務器。模擬實驗是建立在PeerSim引擎基礎之上，這是為了保證盡可能地接近真實世界的情況。實驗的參數設置如表1所示。

節點到達符合參數為1/4的泊松分布。每個節點最大有15個鄰居節點。節點每2min發送最新的下載點到 tracker服務器，實驗運行的結果數據每2min統計一次。

表1 模擬實驗參數設置

4.2 模擬實驗結果

1) 運行時服務器帶寬開銷

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

圖4 與BPB比較的服務器帶寬開銷

圖5 不同參數ε下的服務器帶寬開銷

2) 節點請求的拒絕率

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

3) 節點的平均下載速率

節點下載速率是一個關鍵的評價指標。為了保證播放的平滑性，下載速率應該大于視頻播放速率 r。如果小于視頻播放率，缺少的速率就會從服務器處下載，這會增加服務器的帶寬開銷。圖8顯示NCS算法相比于BPB提升了5.23%的節點下載速率，這是由于NCS算法能夠從低連接數的節點處獲得視頻數據，同時，在降低了請求拒絕率的情況下，節點能夠較快地獲得視頻數據。圖 9顯示，在不同的參數ε下，平均下載速率提升了大約2.47%。

圖6 節點請求拒絕數

圖7 不同參數ε下節點請求拒絕數

圖8 節點的平均下載速率

圖9 不同參數ε下的節點評價下載速率

圖10 在不同小緩沖區，節點數目對服務器的帶寬開銷

4) 不同小緩沖區節點數目對服務器帶寬開銷影響

最后測試的是，當擁有小緩沖區的節點數目不同時，服務器帶寬開銷情況。圖 10顯示當網絡中小緩沖區節點數目占總節點數的10%、20%、30%、40%時服務器帶寬開銷變化情況。隨著小緩沖區節點數目的增加，服務器帶寬開銷僅有少量的增加。以網絡中小緩沖區節點占總節點數的10%為基準，當這個數值是 20%時，服務器帶寬開銷增加了4.78%、30%時增加了5.02%、40%時增加了5.14%。這表明隨著小緩沖區節點數目的增加，服務器帶寬開銷增加程度小于 6%，這是由于節點能夠從其他節點處獲得足夠的下載速率來保證平滑播放從而減少了對服務器的請求。

5 結束語

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

下一步工作是設計一個基于稅收機制的分布式算法來激勵高能力節點盡可能多地貢獻自己資源，輔助低能力節點獲得充足的下載速率從而實現平滑播放，最終達到降低VoD供應商服務器帶寬開銷的目的。

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