Ｐ２Ｐ實時點播系統

摘要：在實時點播系統中對異步的服務請求的處理，是通過在Peer節點上緩存目標節目部分段的數據，讓新節點加入時直接從Peer節點獲取數據，可以在很大程度上減少對源服務器帶寬資源的占用。基于單棵組播樹，本文研究如何對Peer節點進行組織，以適應大規模實時點播系統的應用需求。

關鍵詞：P2P；實時點播；流媒體；對等網絡

中圖分類號：TP37文獻標識碼：A文章編號：1009-3044(2008)04-10ppp-0c

P2P Real-time Video on Demand System

LI Jie， LI Yi

(University of Electronic Science and Technology of China， School of Computer and Engineer， Chengdu 610000， China)

Abstract: In real-time video on demand System， in order to process asynchronous service requests， each Peer Node cache part of the whole Media Data. The new rejoining Peer Node gets data from other Peer Node. This method can reduce to a large extent the demand of the source server bandwidth. Multicast tree based on single trees， the paper research how to how to organize Peer nodes， to adapt to large-scale real-time video on demand System application requirements.

Key words: real-time video on demand; Streaming Media; Peer Network

1 引言

由于視頻流服務對帶寬資源的要求高、服務時間長，使得在Internet上提供實時點播極具挑戰性，特別是當某個節目趨向流行時，系統會在短時間內收到大量異步的服務請求，而傳統的在服務器端為每個請求單獨分配一條流的C/S模式無法容納大規模的點播請求，因此，如何在一定的部署代價前提下使系統具有高可擴展性也就成為其核心問題。IP組播以其多路復用的方式能夠減緩服務器和網絡的負載，但眾多原因如實現方面的復雜性，擁塞控制、可靠性管理等方面的不足使基于IP組播的實時點播服務在近期內難以得到廣泛部署應用。

CDN服務通過在Internet上廣泛部署服務節點，把服務內容“推”向網絡的“邊緣”并把客戶請求路由到距客戶最近的服務節點，從而減輕服務器的壓力和對骨干網絡帶寬的消耗，但這種方式不僅成本昂貴，月并沒有從根本上解決系統可擴展性問題，如當網絡中某區域的點播請求數量過大時，部署在該區域的服務節點依然可能成為系統瓶頸。針對實時點播服務，通過在Peer節點上分配一段定長或不定長的數據空間以緩存其所接收到的數據，并為其它請求該數據段的節點提供服務，不但可以滿足實時點播中異步模式的服務請求，還可以減輕服務器的負載。一般來說，在P2P實時點播系統的應用研究中面臨著如下幾個挑戰：(1)節點搜索，主要指當節點加入系統時，如何在組播樹中快速有效地搜索到合適的父節點，從而縮短節點的加入等待時間；(2)系統容錯，P2P模式中的Peer節點不像傳統C/S模式中的服務器那樣具有高可靠性和可用性，在Peer節點上可能隨時發生主動離開或者因軟件硬件故障而引起的失效等行為，從而中斷其子節點的服務，如何讓被中斷的節點能夠快速有效地進行中斷恢復是系統面臨的核心問題；(3)協議開銷，組播樹的建立和維護依賴于控制協議。一般來說，集中式控制協議雖然比較簡單但同時也具有單點失效，且當系統規模較大時單個節點也往往難以承擔整個系統的協議負載；(4)QoS保證，主要指在Peer節點離開或失效時，如何保證節目的播放質量，如完整性、連續性等。

本文提出了一種P2P環境下的實時點播服務體系，它在系統每個Peer節點上分配一段固定長度的FIFO隊列以緩存其最近所接收到的數據，并為其它點播請求該數據段的節點提供服務。該系統具有如下幾個特點：(1)采用分布式的控制協議，通過在每個節點上維護有限個其它節點的狀態信息，使得當節點加入時能夠在短時間內找到合適的父節點，而當節點上發生離開或者失效行為時，子節點能夠通過其所維護的狀態信息快速準確地找到新的父節點；(2)節點的失效或離開一般不涉及到服務器，從而減輕服務器的負載，系統具有良好的可擴展性；(3)服務被中斷的節點在進行中斷恢復時，考慮了節點對目標節目接收的完整性；(4)考慮了節點在網絡帶寬等資源方面所體現出來的異構性。

2 P2P實時點播服務體系及構成

假設目標節目以CBR方式編碼和傳輸，其播放時長為T，目標節目的最小存儲和傳輸單元為數據塊，每塊的播放時長為一個單位時間，所有數據塊按播放先后順序從1到T予以編號，每個節點上所分配的FIFO緩存隊列長度為m。另外，為了系統描述的簡單，這里假設節點加入時均從目標節目中第一個數據塊開始申請。首先給出描述系統服務體系所需要的幾個定義：

定義2.1 系統中共享從源服務器S一個頻道所流出數據的Peer節點集合稱為一個簇。

定義2.2 簇中直接從源服務器S獲取數據的節點稱為簇首節點，簇中沒有子節點的節點稱為簇葉節點。

定義2.3 對于系統中的任一節點，如果該節點上還緩存有目標節目的第一個數據塊，則稱該節點為開放節點；而對于系統中的任意簇，如果其中至少還包含一個開放節點，則稱該簇為開放簇，否則為閉合簇。

顯然開放簇能夠接受新節點的加入請求，而閉合簇則不能。圖1給出了系統在時刻22處的一個運行快照示例，示例中每個節點均能緩存3個數據塊。從圖1可以看出，節點p1-p7、p8-p13、p14-pl8分別構成了系統中的三個簇，其簇首節點分別為p1、P8、P14前兩個簇屬于閉合簇，最后一個簇屬于開放簇。

圖1 實時點播系統在時刻22的運行快照

定義2.4 組播樹上沿數據轉發路徑處于服務器S和pi之間的所有節點(不包括S和pi)稱為pi的上游節點，而沿數據轉發路徑處于pi和簇葉節點之間的所有節點(不包括pi)稱為幾的下游節點。

定義2.5 對系統中的任意節點pi和pj，如果幾在當前時刻緩存了數據塊next(pj)，且pi不為pj的父節點，則稱pi為pj的候選父節點。

由于在Peer節點上存在離開或失效等動態行為，而當Peer節點作為服務節點時，這些動態行為將導致其子節點服務的中斷。考慮系統中節點所緩存的數據塊內容一般處于動態更新狀態，且在實時點播應用中節點的服務被中斷后一般要求從被中斷處開始重新獲取數據，因此，現有的容錯機制如直接從祖父節點或父輩節點恢復獲取數據的方式并不能保證節點可以從被中斷處恢復所接收的數據，因而這些機制在此都不具有普遍適用性。這里我們提出一種新的容錯機制，它在每個節點上保留其候選父節點的狀態信息，而當數據服務被中斷時節點能夠基于這些狀態信息快速準確地搜索到新的父節點，從而避免了在整個組播樹中進行搜索，不必在每次中斷恢復過程中訪問源服務器，有效地減輕了源服務器的負載。

3 控制協議

為了維護組播樹的邏輯拓撲以及在組播樹的節點間正確地轉發數據，須在每個節點上維持其父、子節點的有關信息；而為了讓服務被中斷的節點能夠快速進行中斷恢復，須在每節點上維持其候選父節點的有關信息；此外，為支持節點的快速加入和中斷恢復，對于每個簇首節點，還須維護其簇中部分節點的有關信息。

以節點pi為例，對于其父節點，僅需在pi上記錄維護其ip地址、節點狀態這兩類信息；對于其任一子節點，需在pi上記錄維護三類信息：ip地址、節點狀態、子節點當前所請求的數據塊，后者作為下一時刻向該子節點轉發哪個數據塊的依據；對于其簇首節點，僅需要維護其ip地址信息；對于其任一候選父節點，除了記錄其ip地址外，還需維持其和pi之間的“心跳線”，以確認其當前是否仍處在系統中。

3.1 節點加入

節點(設為pi)在加入系統前，首先向服務器S發送一加入系統的請求消息；S在收到該消息后，分兩種情形進行處理：

情形一：如果系統中沒有開放簇，則查看其本身是否還有空閑的數據頻道：如果有則向Pi返回加入成功的消息并指明其父節點為S，pi在收到該信息后直接加入S，并從S分配獲取一新的簇號，置只為空；如果沒有則向幾返回加入失敗的消息，節點加入失敗；

情形二：如果系統中還有開放簇，則向所有開放簇的簇首節點轉發pi申請加入系統消息；簇首節點在收到該消息后，直接向pi返回簇中所有的開放節點；假設pi所收集到的開放節點集合為A，pi根據預先定義的某種父節點選取原則從A中挑選一父節點，若父節點選取成功(設為pj)，pi直接加入pj；若父節點選取失敗，直接申請加入服務器S，其過程類似情形一。對于節點pi和集合A，這里提出三種不同的父節點選取原則：

最快匹配原則：即在A中選擇第一個有充足剩余帶寬容納pi加入的節點。這種選擇方式不必在A中查詢比較每一個節點，從而可以讓pi快速加入系統；

最小延遲原則：即在A中選擇有充足剩余帶寬容納pi加入，且和pi之間延遲最小的節點。由于組播樹建立在應用層，其拓撲結構與物理網絡的實際拓撲普遍存在不一致。最小延遲選擇方法能在某種程度上減少這種拓撲的不一致，同時也可以減少對骨干網絡帶寬的消耗；

最小高度原則：即在A中選擇有充足剩余帶寬容納pi加入，且其在組播樹中高度最小的節點。由于組播樹上中間節點的離開或失效行為將直接影響后續子節點對數據的接收。最小高度原則通過選擇高度最小的節點作為父節點，能夠減小整個組播樹的高度，從而減少節點離開或失效對其它節點的影響，提高節目在節點上的平均播放質量。

3.2 節點離開與失效

節點的離開或失效都將引起子節點服務的中斷，而為了恢復節點被中斷的服務，必須解決兩個問題：一是離開或失效節點的檢測，二是重新加入時父節點的搜索選擇。如果節點為主動離開，則在離開前向其所有的子節點發送LEAVE消息，子節點在收到LEAVE消息后表明其服務將被中斷，則由Normal狀態轉入Disconnected狀態。如果節點為失效，由于其在離開系統前無法通知其子節點，因此約定如果節點在規定時間內沒有收到任何從其父節點轉發而來的數據，則向其父節點發送TEST消息：如果在預定時間內能從其父節點收到WAIT消息反饋，節點轉入Suspended狀態，否則繼續向其父節點發送TEST消息；如果連發三次TEST消息后都不能從其父節點收到WAIT消息反饋，表明其父節點己經失效，子節點轉入Disconnected狀態；節點一旦從其子節點收到TEST消息，查看本身所處狀態，如果為Disconnected或Suspended，則向其反饋WAIT消息，否則向其父節點發送TEST消息，并依此類推。圖2給出了節點狀態轉換圖以及相應的轉換條件。為了減少節點失效或離開給系統帶來的額外開銷，規定只有狀態為Disconnected的節點才能發起重新加入請求。

圖2 節點狀態轉換圖

4 結束語

在Internet上提供大規模的實時點播服務是一項極具挑戰性的工作。在P2P網絡環境下，本章提出一種基于單棵組播樹的實時點播服務體系，它能夠以較小的服務器代價實現大規模的實時點播應用。系統中的每個Peer節點均使用定長的FIFO緩存隊列來保存其最近所接收到的數據，以便為后續到達的合適節點提供服務。對于組播樹的構造和維護，系統使用一種分布式的控制協議，通過在每個節點上維護有限個其它節點的狀態信息，使得節點在加入時能快速準確地找到父節點，而當節點上發生離開或者失效等行為時，子節點能夠根據其所維護的狀態信息快速地找到新的父節點。此外服務被中斷的節點在進行中斷恢復時，考慮了節點對目標節目接收的完整性。

參考文獻：

[1]C.Diot，B.N.Levine，B.Lyles，H.Kassem and D.Balensiefen.Deploymet issues for the IP multicast service and architecture. IEEE Network magazines Special issue on Multicasting，2000，14(l):78-88.

[2]S.Gadde，J.Chase and M.Rabinovich. Web caching and content distribution: a view from the interior. In Proceedings of 5th International Web Caching and Content Delivery Workshop. Lisbon， Portugal: Elsevier Science.

[3]http://ww.akamai.com， Alkamai Website.

[4]http://www.napster.com， Napster Website.

[5]龔海剛， 劉明， 毛鶯池， 等. P2P流媒體關鍵技術的研究進展[J]. 計算機研究與發展， 2005，(12):2033-2040.

[6]周旭， 盧顯良， 侯孟書， 等. adPD：一種速度自適應的動態并行下載技術[J]. 計算機科學， 2005，(4):168-170，177.

[7]龔海剛， 劉明， 謝立. P2P流媒體傳輸的研究進展綜述[J]. 計算機科學， 2004，31(9).

收稿日期：2008-01-15

作者簡介：李杰（1982-），男，在讀碩士研究生，就讀于電子科技大學計算機科學與工程學院計算機系統結構專業；李毅，男，博士，電子科技大學教授；研究方向：OS核心、機群技術、對象分布技術、EDA和軟計算。