摘要：在實(shí)時(shí)點(diǎn)播系統(tǒng)中對異步的服務(wù)請求的處理，是通過在Peer節(jié)點(diǎn)上緩存目標(biāo)節(jié)目部分段的數(shù)據(jù)，讓新節(jié)點(diǎn)加入時(shí)直接從Peer節(jié)點(diǎn)獲取數(shù)據(jù)，可以在很大程度上減少對源服務(wù)器帶寬資源的占用。基于單棵組播樹，本文研究如何對Peer節(jié)點(diǎn)進(jìn)行組織，以適應(yīng)大規(guī)模實(shí)時(shí)點(diǎn)播系統(tǒng)的應(yīng)用需求。

關(guān)鍵詞：P2P；實(shí)時(shí)點(diǎn)播；流媒體；對等網(wǎng)絡(luò)

中圖分類號：TP37文獻(xiàn)標(biāo)識碼：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 引言

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

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

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

2 P2P實(shí)時(shí)點(diǎn)播服務(wù)體系及構(gòu)成

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

定義2.1 系統(tǒng)中共享從源服務(wù)器S一個(gè)頻道所流出數(shù)據(jù)的Peer節(jié)點(diǎn)集合稱為一個(gè)簇。

定義2.2 簇中直接從源服務(wù)器S獲取數(shù)據(jù)的節(jié)點(diǎn)稱為簇首節(jié)點(diǎn)，簇中沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為簇葉節(jié)點(diǎn)。

定義2.3 對于系統(tǒng)中的任一節(jié)點(diǎn)，如果該節(jié)點(diǎn)上還緩存有目標(biāo)節(jié)目的第一個(gè)數(shù)據(jù)塊，則稱該節(jié)點(diǎn)為開放節(jié)點(diǎn)；而對于系統(tǒng)中的任意簇，如果其中至少還包含一個(gè)開放節(jié)點(diǎn)，則稱該簇為開放簇，否則為閉合簇。

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

圖1 實(shí)時(shí)點(diǎn)播系統(tǒng)在時(shí)刻22的運(yùn)行快照

定義2.4 組播樹上沿?cái)?shù)據(jù)轉(zhuǎn)發(fā)路徑處于服務(wù)器S和pi之間的所有節(jié)點(diǎn)(不包括S和pi)稱為pi的上游節(jié)點(diǎn)，而沿?cái)?shù)據(jù)轉(zhuǎn)發(fā)路徑處于pi和簇葉節(jié)點(diǎn)之間的所有節(jié)點(diǎn)(不包括pi)稱為幾的下游節(jié)點(diǎn)。

定義2.5 對系統(tǒng)中的任意節(jié)點(diǎn)pi和pj，如果幾在當(dāng)前時(shí)刻緩存了數(shù)據(jù)塊next(pj)，且pi不為pj的父節(jié)點(diǎn)，則稱pi為pj的候選父節(jié)點(diǎn)。

由于在Peer節(jié)點(diǎn)上存在離開或失效等動(dòng)態(tài)行為，而當(dāng)Peer節(jié)點(diǎn)作為服務(wù)節(jié)點(diǎn)時(shí)，這些動(dòng)態(tài)行為將導(dǎo)致其子節(jié)點(diǎn)服務(wù)的中斷?？紤]系統(tǒng)中節(jié)點(diǎn)所緩存的數(shù)據(jù)塊內(nèi)容一般處于動(dòng)態(tài)更新狀態(tài)，且在實(shí)時(shí)點(diǎn)播應(yīng)用中節(jié)點(diǎn)的服務(wù)被中斷后一般要求從被中斷處開始重新獲取數(shù)據(jù)，因此，現(xiàn)有的容錯(cuò)機(jī)制如直接從祖父節(jié)點(diǎn)或父輩節(jié)點(diǎn)恢復(fù)獲取數(shù)據(jù)的方式并不能保證節(jié)點(diǎn)可以從被中斷處恢復(fù)所接收的數(shù)據(jù)，因而這些機(jī)制在此都不具有普遍適用性。這里我們提出一種新的容錯(cuò)機(jī)制，它在每個(gè)節(jié)點(diǎn)上保留其候選父節(jié)點(diǎn)的狀態(tài)信息，而當(dāng)數(shù)據(jù)服務(wù)被中斷時(shí)節(jié)點(diǎn)能夠基于這些狀態(tài)信息快速準(zhǔn)確地搜索到新的父節(jié)點(diǎn)，從而避免了在整個(gè)組播樹中進(jìn)行搜索，不必在每次中斷恢復(fù)過程中訪問源服務(wù)器，有效地減輕了源服務(wù)器的負(fù)載。

3 控制協(xié)議

為了維護(hù)組播樹的邏輯拓?fù)湟约霸诮M播樹的節(jié)點(diǎn)間正確地轉(zhuǎn)發(fā)數(shù)據(jù)，須在每個(gè)節(jié)點(diǎn)上維持其父、子節(jié)點(diǎn)的有關(guān)信息；而為了讓服務(wù)被中斷的節(jié)點(diǎn)能夠快速進(jìn)行中斷恢復(fù)，須在每節(jié)點(diǎn)上維持其候選父節(jié)點(diǎn)的有關(guān)信息；此外，為支持節(jié)點(diǎn)的快速加入和中斷恢復(fù)，對于每個(gè)簇首節(jié)點(diǎn)，還須維護(hù)其簇中部分節(jié)點(diǎn)的有關(guān)信息。

以節(jié)點(diǎn)pi為例，對于其父節(jié)點(diǎn)，僅需在pi上記錄維護(hù)其ip地址、節(jié)點(diǎn)狀態(tài)這兩類信息；對于其任一子節(jié)點(diǎn)，需在pi上記錄維護(hù)三類信息：ip地址、節(jié)點(diǎn)狀態(tài)、子節(jié)點(diǎn)當(dāng)前所請求的數(shù)據(jù)塊，后者作為下一時(shí)刻向該子節(jié)點(diǎn)轉(zhuǎn)發(fā)哪個(gè)數(shù)據(jù)塊的依據(jù)；對于其簇首節(jié)點(diǎn)，僅需要維護(hù)其ip地址信息；對于其任一候選父節(jié)點(diǎn)，除了記錄其ip地址外，還需維持其和pi之間的“心跳線”，以確認(rèn)其當(dāng)前是否仍處在系統(tǒng)中。

3.1 節(jié)點(diǎn)加入

節(jié)點(diǎn)(設(shè)為pi)在加入系統(tǒng)前，首先向服務(wù)器S發(fā)送一加入系統(tǒng)的請求消息；S在收到該消息后，分兩種情形進(jìn)行處理：

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

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

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

最小延遲原則：即在A中選擇有充足剩余帶寬容納pi加入，且和pi之間延遲最小的節(jié)點(diǎn)。由于組播樹建立在應(yīng)用層，其拓?fù)浣Y(jié)構(gòu)與物理網(wǎng)絡(luò)的實(shí)際拓?fù)淦毡榇嬖诓灰恢隆Ｗ钚⊙舆t選擇方法能在某種程度上減少這種拓?fù)涞牟灰恢?，同時(shí)也可以減少對骨干網(wǎng)絡(luò)帶寬的消耗；

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

3.2 節(jié)點(diǎn)離開與失效

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

圖2 節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換圖

4 結(jié)束語

在Internet上提供大規(guī)模的實(shí)時(shí)點(diǎn)播服務(wù)是一項(xiàng)極具挑戰(zhàn)性的工作。在P2P網(wǎng)絡(luò)環(huán)境下，本章提出一種基于單棵組播樹的實(shí)時(shí)點(diǎn)播服務(wù)體系，它能夠以較小的服務(wù)器代價(jià)實(shí)現(xiàn)大規(guī)模的實(shí)時(shí)點(diǎn)播應(yīng)用。系統(tǒng)中的每個(gè)Peer節(jié)點(diǎn)均使用定長的FIFO緩存隊(duì)列來保存其最近所接收到的數(shù)據(jù)，以便為后續(xù)到達(dá)的合適節(jié)點(diǎn)提供服務(wù)。對于組播樹的構(gòu)造和維護(hù)，系統(tǒng)使用一種分布式的控制協(xié)議，通過在每個(gè)節(jié)點(diǎn)上維護(hù)有限個(gè)其它節(jié)點(diǎn)的狀態(tài)信息，使得節(jié)點(diǎn)在加入時(shí)能快速準(zhǔn)確地找到父節(jié)點(diǎn)，而當(dāng)節(jié)點(diǎn)上發(fā)生離開或者失效等行為時(shí)，子節(jié)點(diǎn)能夠根據(jù)其所維護(hù)的狀態(tài)信息快速地找到新的父節(jié)點(diǎn)。此外服務(wù)被中斷的節(jié)點(diǎn)在進(jìn)行中斷恢復(fù)時(shí)，考慮了節(jié)點(diǎn)對目標(biāo)節(jié)目接收的完整性。

參考文獻(xiàn)：

[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流媒體關(guān)鍵技術(shù)的研究進(jìn)展[J]. 計(jì)算機(jī)研究與發(fā)展， 2005，(12):2033-2040.

[6]周旭， 盧顯良， 侯孟書， 等. adPD：一種速度自適應(yīng)的動(dòng)態(tài)并行下載技術(shù)[J]. 計(jì)算機(jī)科學(xué)， 2005，(4):168-170，177.

[7]龔海剛， 劉明， 謝立. P2P流媒體傳輸?shù)难芯窟M(jìn)展綜述[J]. 計(jì)算機(jī)科學(xué)， 2004，31(9).

收稿日期：2008-01-15

作者簡介：李杰（1982-），男，在讀碩士研究生，就讀于電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)專業(yè)；李毅，男，博士，電子科技大學(xué)教授；研究方向：OS核心、機(jī)群技術(shù)、對象分布技術(shù)、EDA和軟計(jì)算。