面向跳播優化的P2P視頻點播系統

杜磊，金志剛，王曉海

1.天津大學電子信息工程學院，天津 300072

2.中國人民解放軍61660部隊

面向跳播優化的P2P視頻點播系統

杜磊1，金志剛1，王曉海2

1.天津大學電子信息工程學院，天津 300072

2.中國人民解放軍61660部隊

1 引言

隨著網絡帶寬和視頻壓縮技術的快速發展，IPTV被越來越多的人應用。IPTV一般泛指通過IP網絡傳輸音視頻內容并用電視機收看的業務。早期IPTV系統采用客戶機/服務器模式提供業務，這已經成為制約IPTV發展的“瓶頸”，解決方法是體系結構向對等連接（P2P）模式演化[1]。P2P IPTV應用不僅可以像傳統電視一樣向用戶提供視頻直播服務，而且還可以與用戶交互，提供傳統電視很難實現的視頻點播業務。

與直播領域相比，在視頻點播領域，P2P技術的發展速度相對較為緩慢。主要是因為點播當中的高度交互性需求，使得實現的復雜程度較高。正是在這種前提下，各種P2P視頻點播系統應運而生，包括P2Cast[2]，P2VoD[3]，Grid-Cast[4]等系統。這些系統各有各自的優勢，P2VoD系統是其中較為出色的系統。

P2VoD是佛羅里達大學提出來的一個基于樹狀拓撲的P2P視頻點播系統[3]。系統中提出“代”的概念，進行數據分發和失效恢復。不足之處是系統無法順利處理跳播的行為，這是該系統的一大缺陷。

本系統正是基于P2VoD，針對其中的不足，進行優化設計，采用樹網結合的拓撲結構，實現對等體的加入、跳播、離開等行為的處理。

2 P2P視頻點播系統設計

2.1 框架描述

本系統采用樹網結合的拓撲結構，這樣既維護了網絡的中心性，使管理者能夠對整個網絡有全局的把握，另一方面，又增加了對等體之間的聯系，保證當某一個或者某些對等體崩潰時，網絡依然保持連通性，而不需長時間的恢復刪除，保證了網絡的穩定性。

在本系統中，每個對等體中都開辟了一段固定大小的空間作為緩存，實際使用的緩存大小依據不同對等體加入系統的時間不同而不同。將源視頻的內容分塊，順次標號為1，2，3，…，稱為數據塊標號。緩存中，具有相同的最小數據塊標號的對等體稱為一代，所有代的全體對等體組成一個會話。當所有對等體都不保留標號為1的數據塊時，此會話關閉。此時，若再有對等體加入系統，則重啟一個新的會話。

同一會話中，代的標號從1開始遞增。當新的對等體加入系統時，它或者屬于編號最大的代，或者成為新一代的第一個成員。規定第i代中的對等體的父對等體都來自第(i-1)代，其中i＞1。第1代的對等體的父對等體是源服務器。

為了減小特定兩個對等體之間的依賴性，從而增強網絡的穩定性，該系統中，每個對等體選擇多個父對等體。通過對現有系統長時間大量的觀測實驗，得到60%以上的對等體的當前運行時間要超過1 h，隨機選擇兩個對等體，二者中至少存在一個對等體的運行時間大于1 h的概率P2計算結果為：

不考慮網絡抖動，隨著父對等體數目增大，1 h內穩定從父對等體處接收數據的概率也增大；而選擇父對等體的時間增長，網絡的復雜性也增大。為了在二者之間取一個平衡，選擇一個中間值，令父對等體數目為3，維持了網絡的穩定性和拓撲結構的簡易性。同時為了盡可能減小對等體加入網絡后的初始延遲，以及簡化各對等體間的控制信息內容，系統按照最小延遲方法選擇父對等體，即直接在候選隊伍中選擇最靠前的對等體。

同一代中各對等體采用可變緩存機制，這里用緩存中存儲的視頻時間代表緩存大小，后加入代的對等體的緩存要小于先加入的，二者的差應該等于二者加入時間的差。這樣設置的緩存策略保證了不同時間加入系統的對等體，在觀看同一視頻的不同位置時，緩存中的最小數據塊標號仍然相同。

對于網絡中的任一對等體，都需要保存三類信息，包括IP地址和端口號：（1）自己所處的代中全部兄弟對等體的信息；（2）自己的父對等體所處的代中所有對等體的信息；（3）自己的子對等體的信息。對于每個新加入系統或者發生跳播的對等體X，它需要給服務器發送信息＜IPX,GX,TeX＞，其中IPX指X的IP和端口號信息，GX指X加入的代，TeX指X緩存中標號最小數據塊的刪除時間。

2.2 加入算法

新對等體加入網絡時都需要先與服務器聯系，獲取網絡狀況信息。具體來講，依據控制信息協議，服務器了解當前各個會話的狀態，并且保存有各會話中各代成員的部分信息，如緩存中標號最小數據塊的刪除時間Te。新對等體會根據獲取到的信息和父對等體選擇協議決定加入哪一代以及選哪些對等體作為父對等體。

初始時刻，系統為空，設置最年輕的一代只有服務器，Te設置為無窮大。設新加入系統的對等體為X，加入時間為TjX。

加入步驟描述如下：

情況1所有會話都關閉

步驟1直接連接服務器。若服務器帶寬不足，則新對等體被拒絕；否則轉步驟2。

步驟2創建一個新會話。新對等體成為該會話第一代的第一個成員，從服務器開始下載數據。

情況2至少存在一個未關閉的會話

步驟1選擇一個會話加入。向服務器索取該會話中最年輕一代G1的成員信息。

步驟2與G1中的任一成員聯系，獲取其父對等體的信息。

步驟3如果父代中標號最小數據塊的刪除時間Te1晚于X的加入時間TjX，則跳轉到步驟4；否則跳轉到步驟5。

步驟4X根據選父規則，從父代中選擇3個對等體作父親。之后X成為G1的成員，從父對等體處接受數據。X的實際可用緩存大小根據緩存規則進行設置。

步驟5在G1下形成新的一代。X成為新一代的第一個成員。依據選父規則從G1中選擇父對等體。X實際緩存大小設為最大可用緩存。

2.3 短距離跳播算法

對于用戶來說，視頻點播系統比視頻直播系統增加了更多的能動性，其中最重要的功能之一就是支持跳播。對于一個發生了跳播行為的對等體，它不再屬于當前的代，也無法接受或提供當前的父對等體和子對等體相應的服務。換言之，該對等體近似于一個新加入系統的對等體，唯一的區別是它的起始播放位置不是視頻文件的初始位置，而是它將要跳播到的位置。

設發生跳播行為的對等體為X，跳播到的位置為視頻的TpX位置，發生跳播的時間是T，則設置X的加入時間TjX=T-TpX，將X作為一個加入時間為TjX的對等體。N代表某一代對等體中最小的數據塊標號，X跳播到的數據塊標號為NX。

由于80%的跳播行為都是近距離跳播，所以當發生跳播行為時，首先在本會話內部搜尋合適的對等體來作為父對等體。

向前跳播和向后跳播的示意圖如圖1和圖2所示。

圖1 短距離向前跳播算法示意圖

圖2 短距離向后跳播算法示意圖

算法描述如下：

（1）向前跳播：X遞推地獲取父代G1、G1的子代G2、G2的子代乃至更下一代的信息，直到找到一代Gn，其標號最小數據塊的刪除時間Ten晚于X的加入時間TjX，則X成為Gn的子代的成員。若一直找到當前會話的最后一代仍未找到，則按照長距離跳播算法進行處理。

（2）向后跳播：X遞推地獲取父代G1、G1的父代G2'、G2'的父代乃至更上一代的信息，直到找到一代Gn'，其標號最小數據塊的標號Nn小于X跳播到的數據塊，X成為Gn'的子代的成員。若一直找到當前會話的第一代仍未找到，則按照長距離跳播算法進行處理。

2.4 長距離跳播算法

當發生跳播的對等體無法在其所在的會話中找到合適的新父對等體時，將按照長距離跳播算法處理。仍然設發生跳播的對等體為X，跳播到的數據塊為NX，換算后的加入時間是TjX。

首先連接服務器，索取當前各會話的信息，獲取各會話中最年輕一代的成員的信息，包括當前最小數據塊標號N和標號最小的數據塊的刪除時間Te。

向前跳播和向后跳播的示意圖如圖3和圖4所示。

圖3 長距離向前跳播算法示意圖

圖4 長距離向后跳播算法示意圖

算法描述如下：

（1）向前跳播：按照會話的創建順序，順序向后找到第一個Te＞TjX的會話。若找不到，則直接連接服務器。若找的到，從該會話的最年輕一代開始向上，依次獲取每一代的成員信息。找到第一代不滿足(TjX＜Te&&NX＞N)的代，選取其子代作為X的父代。若所有代都不滿足條件(TjX＜Te&&NX＞N)，則直接連接服務器。

（2）向后跳播：按照會話的創建順序，逆序向前找到第一個Te＜TjX的會話，選擇晚于該會話創建時間的最早會話進行處理。若找不到，選擇最早的會話進行處理。從選中的會話的最年輕一代開始向上，依次獲取每一代的成員信息。找到第一個不滿足(TjX＜Te&&NX＞N)的代，選取其子代作為X的父代。若所有代都不滿足條件(TjX＜Te&&NX＞N)，則直接連接服務器。

2.5 錯誤恢復

設對等體X發現某一個父對等體崩潰（跳播離開、退出或上行帶寬不足）。

錯誤恢復步驟描述如下：

步驟1X從父對等體所在的代信息中，依據選父規則，選取一個新的對等體作為父親。若建立連接成功則恢復成功。否則繼續嘗試父代的其他對等體直到成功。都失敗后轉步驟2。

步驟2若此時X仍有不少于一個父對等體，則X維持當前的父子狀態。每隔一段時間，跳轉回步驟1嘗試新的連接。若父對等體數小于一個，轉步驟3。

步驟3X當前播放位置為TpX，根據當前時間T，設置X的加入時間TjX=T-TpX。按照跳播算法，重新選擇X的父對等體。

3 仿真與評價

利用仿真手段，使用GT-ITM拓撲產生器來生成基本的網絡拓撲結構[5]，從初始時延、服務器負載、跳播延遲等方面，對系統性能進行了評價。通過與P2VoD系統性能的比較，給出了本系統的性能評價。

3.1 仿真環境

使用GT-ITM拓撲產生器創建一個傳輸域-子域模型。整個網絡包含3個傳輸域，每個傳輸域內有5個傳輸結點。每個傳輸結點與6個子域相連，每個子域有12個結點。網絡中的總結點數為3×5+3×5×6×12=1 095。在這組實驗中，可以認為每個子域都代表一個局域網。對等體可以位于任意一個子域的任意一個結點上。數據源服務器位于傳輸域的一個結點上。

傳輸域結點間帶寬、傳輸域和子域結點間帶寬、子域結點間帶寬，以及電影資源碼率和資源時長的設置見表1。

客戶到達滿足泊松分布，并且被隨機分派到子域的一個結點上。每次仿真時間都是2 h。到達系統的客戶數=到達率×仿真運行時間，用到達系統的客戶數表示網絡負載。

表1 網絡環境與資源參數設置

3.2 初始時延

初始時延表示從一個對等體準備加入網絡，到對等體開始播放資源內容之間的時間間隔。初始時延越小，用戶體驗越好。因為視頻資源播放前漫長的等待是用戶最討厭的事情之一。

為了簡化過程，仿真簡單地統計對等體加入網絡時需要連接其他對等體的次數，連接次數少相當于有較小的初始時延。圖5給出了隨著用戶規模的增大，新加入網絡的對等體平均需要連接其他對等體的次數。

圖5 初始加入時的平均連接次數

從圖中可以看出，在系統中，當網絡中用戶規模較小的時候，由于符合要求的父對等體較少，而且能連接到每個父對等體的孩子數量有限，所以連接次數增加較快，并達到一個峰值。隨著用戶規模增加，符合要求的父對等體也增加，平均連接次數逐漸回落。當用戶數量達到一定規模之后，平均連接次數基本穩定下來，并且維持在一個優秀的水平上。通過和P2VoD系統比較可以看出，本文系統的初始時延更加穩定，用戶體驗更好。

3.3 服務器負載

隨著加入網絡的客戶數量增大，服務器負載也會增大。好的系統可以盡量減小服務器的壓力，通過使現有的對等體盡可能多地為新用戶提供數據，來達到減小服務器壓力的效果。

為了簡化實驗，本仿真通過統計不同客戶規模時，直接連接服務器的用戶數來直觀反應服務器負載。

從圖6可以看出，在本系統中，隨著用戶規模的增大，服務器的負載緩慢增加，當用戶規模達到一定程度時，本系統的服務器壓力比P2VoD稍大。這是由于與P2VoD相比，本系統采用樹網結合的拓撲結構，整個網絡結構更加扁平。這也是引起平均查找次數減少，服務器負載增大的主要原因。為了減小服務器的壓力，可以考慮部署分布式的多服務器。

圖6 服務器負載

3.4 跳播延遲

本系統與P2VoD相比最大的差別就是支持用戶的跳播行為。當用戶離開當前播放位置，轉到另一播放位置繼續觀看視頻時，對等體需要逐代去尋找適合自己新的播放位置的代。過長的延遲是用戶所不能接受的，故需對延遲性能進行仿真評價。

圖7給出了在不同的用戶規模下，用戶跳播到距離當前播放位置分別為1 min、5 min、10 min和30 min情況下的平均連接結點的次數，用以間接反映跳播延遲。

圖7 跳播延遲

從圖中可以看出，跳播到的位置與當前播放位置距離越長，需要連接其他結點的次數就越多，直接導致等待時間越長。如果跳播距離不超過10 min，連接次數都在10次以內，基本規模在初始加入連接次數的一半以下，用戶基本可以接受。

連接的次數與網絡中用戶的規模數沒有直接的單調關系。用戶規模很小（100以內）的時候，連接次數簡單遞增。但是當用戶規模大幅增大之后，跳播需要的平均連接次數十分穩定。這是因為，用戶規模很小的時候，所有用戶幾乎都在一個會話中，處于不同的代，跳播后逐層尋找新的父對等體，導致連接次數單調遞增。隨著用戶規模的增大，網絡中會話數增多，網絡變得扁平，查找次數就基本穩定下來了。

4 結束語

本文在P2VoD算法的基礎上進行了一系列的改變和優化，設計了新的系統，實現對等體的加入、跳播、離開等行為的處理。新的系統以樹網結合的拓撲結構，實現了對點播用戶跳播行為的支持，并減小了系統抖動。

通過使用GT-ITM拓撲產生器生成基本的網絡拓撲結構，從初始時延、服務器負載、跳播延遲等多個方面，對系統性能進行評價。仿真結果顯示，在相同的網絡負載下，當用戶規模達到一定程度時，服務器壓力會比P2VoD系統的服務器壓力略大，但是對等體初始加入網絡時的延遲要小20%，同時系統比P2VoD更加穩定，并且實現了對跳播功能的支持，平均跳播時延約為初始時延的50%。

綜上，本系統很好地實現了快速加入，用戶異步請求的有效處理，快速的錯誤恢復，尤其是實現了跳播支持，顯示出比P2VoD更加優秀的性能。在當前的高帶寬網絡中，本系統能夠為終端用戶提供包括立體電視在內的眾多類型的視頻點播服務，因此適合推廣到大規模的IPTV VoD覆蓋網絡之中。

[1]侯自強.P2P IPTV技術進展[J].中興通訊技術，2006，12（3）：10-13.

[2]Guo Y，Suh K，Kurose J，et al.P2Cast：peer to peer patching scheme for VoD service[C]//Proc of the 12th International Conference on World Wide Web，2003：301-309.

[3]Do T，Hua K，Tantaoui M.P2VoD：providing fault tolerant video-on-demand streaming in peer-to-peer environment[C]// Proc of the IEEE ICC 2004，2004：1467-1472.

[4]Cheng B，Stein L，Jin H，et al.GridCast：improving peer sharing for P2P VoD[J].ACM Transactions on Multimedia Computing，Communications and Applications，2008，4（4）：1-31.

[5]Zegura E，Calvert K，Bhattacharjee S.How to model an internetwork[C]//Proc of IEEE INFOCOM，1996：594-602.

[6]齊衛寧，王勁林.基于P2VoD的視頻點播系統[J].計算機工程與應用，2008，44（10）：20-22.

DU Lei1,JIN Zhigang1,WANG Xiaohai2

1.School of Electronic and Information Engineering,Tianjin University,Tianjin 300072,China
2.Unit 61660 of PLA,China

A new video on demand system is designed.It is based on P2VoD algorithm,and it makes changes and optimization for the inadequacies of P2VoD.New system combines tree topology and mesh topology,realizes actions of peers such as joining, skipping,and leaving,especially makes a special optimization for skipping behavior of users and reduces the delay jitter of the system.After the simulation,results show that with the same network load,the initial delay of peers is 20%smaller than P2VoD, while the system is more stable than P2VoD and realizes the skipping function,and the average skipping delay is about 50%of the initial delay.

video on demand system;network;Peer-to-Peer（P2P）;skipping

基于P2VoD算法，針對其不足之處進行改變和優化，設計了新的系統。新的系統以樹網結合的拓撲結構，實現對等體的加入、跳播、離開等行為的處理，尤其是對點播用戶跳播行為的支持進行了特別的優化，減小了系統的延遲抖動。經過仿真，結果表明在相同的網絡負載下，對等體初始加入網絡時的延遲比P2VoD要小20%，同時系統比P2VoD更加穩定，并且實現了對跳播功能的支持，平均跳播時延約為初始時延的50%。

視頻點播系統；網絡；對等連接（P2P）；跳播

A

TP393

10.3778/j.issn.1002-8331.1203-0404

DU Lei,JIN Zhigang,WANG Xiaohai.Skipping optimization for P2P video on demand system.Computer Engineering and Applications,2013,49（24）：65-69.

國家高技術研究發展計劃（863）（No.2009AA01A336）；中興通訊產學研合作項目資助。

杜磊（1988—），男，碩士研究生，主要研究領域為計算機網絡；金志剛，男，博士，教授，博士生導師；王曉海，高級工程師。E-mail：zgjin@tju.edu.cn

2012-03-19

2012-06-18

1002-8331（2013）24-0065-05