P2P VOD系統(tǒng)中實(shí)時資源調(diào)度管理的實(shí)現(xiàn)

郎 非，陳麗華，侯成寶

（南京郵電大學(xué) 江蘇省圖像處理與圖像通信重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003）

0 引言

對等網(wǎng)絡(luò)（peer to peer，P2P）技術(shù)作為一種新型的網(wǎng)絡(luò)技術(shù)，改變了互聯(lián)網(wǎng)上以服務(wù)器為中心的傳輸模式，使網(wǎng)絡(luò)上的每一個終端同時具備服務(wù)器和客戶端的功能。當(dāng)前基于P2P網(wǎng)絡(luò)的多媒體服務(wù)得到了廣泛應(yīng)用，并不斷演進(jìn)[1]。目前國內(nèi)外對P2P流媒體的研究及商業(yè)應(yīng)用已經(jīng)獲得了初步成功，但仍面臨諸多問題。其中，如何有效地管理客戶機(jī)緩存中的節(jié)目資源是一個新的課題任務(wù)，同時也是當(dāng)前研究的熱點(diǎn)問題[2]。

本文主要研究如何高效地實(shí)現(xiàn)對P2P網(wǎng)絡(luò)節(jié)點(diǎn)資源的管理，包括針對節(jié)點(diǎn)服務(wù)的動態(tài)特性、媒體流的動態(tài)特性等，對數(shù)據(jù)的播放有較為嚴(yán)格的時限和時序要求限制等，其中核心問題是對節(jié)目源的搜索查找問題。具體來說，在P2P流媒體中，由于請求節(jié)點(diǎn)一般需要從其他節(jié)點(diǎn)獲取流數(shù)據(jù)，因此當(dāng)新節(jié)點(diǎn)請求加入時，根據(jù)其請求，首先在系統(tǒng)中搜索定位能為該節(jié)點(diǎn)提供數(shù)據(jù)服務(wù)的節(jié)點(diǎn)，而當(dāng)提供服務(wù)的節(jié)點(diǎn)離開或失效后也同樣需要在系統(tǒng)中搜索定位新的服務(wù)節(jié)點(diǎn)。該節(jié)點(diǎn)的搜索定位對時間有嚴(yán)格要求，否則會影響終端的用戶體驗(yàn)。所以P2P流媒體系統(tǒng)需要一個高效率的節(jié)點(diǎn)資源管理和定位系統(tǒng)。本文主要研究節(jié)點(diǎn)節(jié)目資源定義、管理和搜索，以及基于Pas?try路由[3]的域間節(jié)目資源管理。

1 P2P資源管理架構(gòu)

P2P的資源架構(gòu)的設(shè)定是資源管理的第一步，是P2P VOD系統(tǒng)實(shí)現(xiàn)所面臨的首要問題[4-6]。本文研究的P2P VOD系統(tǒng)采用二級P2P網(wǎng)絡(luò)管理架構(gòu)，可用于大規(guī)模的電信城域網(wǎng)用戶，如圖1所示。域內(nèi)級（Intra Do?main）由普通客戶端組成P2P域內(nèi)結(jié)構(gòu)，并由調(diào)度中心（Border）負(fù)責(zé)域內(nèi)用戶的集中式管理。域間級（Inter Do?main）由調(diào)度中心組成不同域之間的P2P結(jié)構(gòu)。由于強(qiáng)化了調(diào)度中心的功能作用，二層化分布式的網(wǎng)絡(luò)利于服務(wù)節(jié)點(diǎn)資源的快速定位，避免了泛洪式搜索的盲目性。

2 節(jié)目源資源類型定義

恰當(dāng)?shù)馁Y源標(biāo)識定義是實(shí)現(xiàn)資源高效搜索的前提。在P2P VOD系統(tǒng)中，每個節(jié)點(diǎn)接入調(diào)度中心查找為其服務(wù)的源節(jié)點(diǎn)。調(diào)度中心作為整個系統(tǒng)信令核心，負(fù)責(zé)對其BRAS服務(wù)器所管轄的域內(nèi)節(jié)點(diǎn)所擁有的資源信息進(jìn)行管理。當(dāng)域內(nèi)不含有所要查找的資源信息時，調(diào)度中心還要啟動域間查找功能為之服務(wù)。節(jié)點(diǎn)所擁有資源是指節(jié)點(diǎn)緩存中所存儲的節(jié)目媒體數(shù)據(jù)，為了方便調(diào)度中心對節(jié)點(diǎn)資源的查找，對節(jié)點(diǎn)所擁有的資源分成A類和B類。A類資源指節(jié)點(diǎn)緩存中存在“節(jié)目零時刻起始點(diǎn)”的媒體數(shù)據(jù)，而B類資源則不存在“節(jié)目零時刻起始點(diǎn)”的媒體數(shù)據(jù)。A類資源用于一般用戶使用，即用戶對媒體節(jié)目必須從頭看到尾。B類資源主要針對復(fù)雜的操作，如用戶對節(jié)目的拖拉，或因網(wǎng)絡(luò)故障使節(jié)目中斷而再接入等。A類資源是資源默認(rèn)狀態(tài)，無需向調(diào)度中心發(fā)布，而B類資源的信息需要向調(diào)度中心主動發(fā)布。B類資源的設(shè)定豐富了用戶使用功能，是區(qū)別于傳統(tǒng)P2P流媒體應(yīng)用的關(guān)鍵。

在對B類資源定義前，要清楚客戶端節(jié)點(diǎn)如何對媒體數(shù)據(jù)進(jìn)行緩存?？蛻舳斯?jié)點(diǎn)的接收緩存均采用環(huán)形隊列數(shù)據(jù)結(jié)構(gòu)（見圖2）。起始數(shù)據(jù)指針指示節(jié)點(diǎn)緩存中起始接收的數(shù)據(jù)位置（僅用于標(biāo)識A類資源零時刻位置），接收指針指示當(dāng)前新接收的數(shù)據(jù)位置，發(fā)送數(shù)據(jù)指針指示發(fā)給其他節(jié)點(diǎn)的數(shù)據(jù)位置。當(dāng)環(huán)形隊列數(shù)據(jù)未滿，源節(jié)點(diǎn)可為其他節(jié)點(diǎn)提供A類服務(wù)，當(dāng)環(huán)形隊列被數(shù)據(jù)充滿，且零時刻點(diǎn)被覆蓋掉，此時源節(jié)點(diǎn)需要通過Put原語向調(diào)度中心發(fā)布B類資源信息，包括目前緩存起始媒體數(shù)據(jù)時間、緩存的媒體數(shù)據(jù)時間長度及節(jié)點(diǎn)能力大小等。

3 節(jié)點(diǎn)資源的管理

在P2P VOD系統(tǒng)中，除中心服務(wù)器外，每個節(jié)點(diǎn)既是客戶端，同時也是服務(wù)器。每個節(jié)點(diǎn)通過系統(tǒng)獲得多媒體點(diǎn)播服務(wù)，作為服務(wù)器的節(jié)點(diǎn)動態(tài)地緩存接收的媒體數(shù)據(jù)，為其他節(jié)點(diǎn)提供服務(wù)。節(jié)點(diǎn)接收緩存的媒體數(shù)據(jù)是隨著節(jié)目的播放或節(jié)點(diǎn)的點(diǎn)播行為而動態(tài)變化的，調(diào)度中心服務(wù)器的作用就是管理這種資源和準(zhǔn)確定位可用資源。根據(jù)媒體資源定義，調(diào)度中心負(fù)責(zé)分別對A類和B類資源進(jìn)行管理。

3.1 A類資源管理

A類資源調(diào)度比較簡單，調(diào)度中心根據(jù)零時刻起始點(diǎn)點(diǎn)播的需要，專門維護(hù)了一張A類資源信息表（如圖3所示）。該表按照節(jié)目ID從小到大的順序向下一級鏈接為多張A類資源節(jié)點(diǎn)子表。子表中記錄著具有A類資源的節(jié)點(diǎn)ID。當(dāng)一個節(jié)點(diǎn)點(diǎn)播請求時，根據(jù)節(jié)點(diǎn)請求的節(jié)目ID能夠快速定位到其A類資源子表，提供相應(yīng)的節(jié)目ID。任一節(jié)點(diǎn)對A類資源信息的保存都有時效性，會受節(jié)目緩沖時間的限制。

3.2 B類資源管理

緩存中不論接收的是哪類資源，其節(jié)目內(nèi)容都是在變化的，但對于A類資源，其起始點(diǎn)位置（零時刻）始終存在，而對于B類資源，節(jié)目源數(shù)據(jù)起始時間不斷變化，調(diào)度中心發(fā)布的節(jié)點(diǎn)緩存相關(guān)信息是間歇性的（相隔一段時間發(fā)布一次），由此存在數(shù)據(jù)不一致性，這為節(jié)點(diǎn)上的B類資源管理帶來了難度。本文通過設(shè)置B類資源參考點(diǎn)的值來唯一標(biāo)識節(jié)點(diǎn)緩存變化的數(shù)據(jù)信息。

由于節(jié)目是嚴(yán)格按照時間順序勻速播放，接收B類資源緩存中的節(jié)目起始指針也隨節(jié)目播放相應(yīng)變化。因此調(diào)度中心可通過記錄節(jié)點(diǎn)加入時間（請求節(jié)目得到響應(yīng)的時間）和媒體流傳輸速率來計算緩存中某時刻節(jié)點(diǎn)所存儲數(shù)據(jù)的節(jié)目時間區(qū)間，當(dāng)一個節(jié)點(diǎn)正好請求該時間區(qū)間的內(nèi)容時，該節(jié)點(diǎn)將為其提供服務(wù)。在服務(wù)節(jié)點(diǎn)和被服務(wù)節(jié)點(diǎn)正常觀看節(jié)目，且沒有任何前進(jìn)、倒退等操作時，服務(wù)節(jié)點(diǎn)緩存的數(shù)據(jù)將一直能滿足被服務(wù)節(jié)點(diǎn)的需要。

1）組定位

為了進(jìn)一步滿足B類資源快速搜索定位的要求，將節(jié)點(diǎn)的B類資源按照發(fā)布的緩存起始數(shù)據(jù)時間進(jìn)行分組管理。當(dāng)某個節(jié)點(diǎn)請求點(diǎn)播服務(wù)時，調(diào)度中心首先將節(jié)點(diǎn)的查詢請求快速定位到某個組，再在該組內(nèi)查找節(jié)點(diǎn)的B類資源信息，定位可以提供指定節(jié)目服務(wù)的源節(jié)點(diǎn)。預(yù)先進(jìn)行組定位，目的就是先將用戶快速定位到一個大致的區(qū)域內(nèi)，從而減少搜索范圍，避免在全網(wǎng)搜索，降低系統(tǒng)開銷。具體過程如下：

（1）將長度為L的媒體節(jié)目以一定的時間粒度τ等分為ψ份（L=τψ），τ稱為一個時間區(qū)域。每個節(jié)目定義一個指針，即資源參考點(diǎn)RP，初始值為0，每經(jīng)過一個τ時間，RP值加1。在節(jié)目的分組管理中，每一個組對應(yīng)著節(jié)目的一個播放時間區(qū)間，該時間區(qū)間長度設(shè)為τ。

（2）以某一節(jié)目管理為例，調(diào)度中心從第1個節(jié)點(diǎn)開始點(diǎn)播該節(jié)目算起，經(jīng)過τ時間，其間從節(jié)目源起始點(diǎn)開始點(diǎn)播的用戶都被歸為一組，其組號為RP的當(dāng)前值。換種角度看，當(dāng)點(diǎn)播時，通過當(dāng)時的RP值來直接找到組號（RP與組號同值），即分組與搜索點(diǎn)播可一并完成。

（3）如果用戶沒有從媒體源起始點(diǎn)點(diǎn)播，采用如下式子來計算該用戶應(yīng)該加入的組號

式中：O為用戶點(diǎn)播節(jié)目的時間點(diǎn)。查找點(diǎn)播過程，亦可通過上式帶入O，計算Group-ID。上述算法可簡單描述為：一個組內(nèi)節(jié)目緩存的數(shù)據(jù)內(nèi)容時刻在變，但是Group-ID是固定值，無法反應(yīng)緩存中數(shù)據(jù)的變化，由此設(shè)置隨時間發(fā)生變化的指針RP，那么Group-ID值與當(dāng)前RP的差值即可作為表示節(jié)目內(nèi)容時間變化的量度。

2）組內(nèi)定位

針對一個時間區(qū)間的Group-ID，雖然其區(qū)間內(nèi)的數(shù)據(jù)的起始與終止時間是不斷變化的，但是由于Group-ID是固定值，這為資源管理帶來了方便。然而這種搜索查找的精度只能達(dá)到τ。進(jìn)一步考慮，組內(nèi)節(jié)點(diǎn)數(shù)據(jù)的起始時間也在時刻變化，通過一定的Hash運(yùn)算計算出節(jié)點(diǎn)緩存起始數(shù)據(jù)時間的相對固定值，該值不隨緩存起始數(shù)據(jù)時間的變化而變化。

調(diào)度中心記錄節(jié)點(diǎn)緩存內(nèi)容（組內(nèi)）的起始時間T、節(jié)點(diǎn)緩存深度（節(jié)目時長Lmemsize）以及當(dāng)前調(diào)度中心系統(tǒng)時間（Tsystime1）。

新用戶請求點(diǎn)播X時間的內(nèi)容，此時調(diào)度中心的系統(tǒng)時間Tsystime2，檢查

式中：Td為緩存起始數(shù)據(jù)時間。上式同樣適用于節(jié)點(diǎn)請求點(diǎn)播節(jié)目時，計算點(diǎn)播時間點(diǎn)的相對值（查詢參考點(diǎn)），此時，Td為點(diǎn)播時間點(diǎn)的值。

在調(diào)度中心中，每組節(jié)點(diǎn)的B類資源信息表中記錄了節(jié)點(diǎn)的B類資源參考點(diǎn)、節(jié)點(diǎn)接收緩存大小及節(jié)點(diǎn)ID共3項(xiàng)。前兩項(xiàng)是調(diào)度中心對B類資源信息搜索查找服務(wù)源的關(guān)鍵值。當(dāng)節(jié)點(diǎn)請求點(diǎn)播節(jié)目時，調(diào)度中心通過將節(jié)點(diǎn)點(diǎn)播時間點(diǎn)的相對值（查詢參考點(diǎn)）與B類資源信息表中各節(jié)點(diǎn)的B類資源參考點(diǎn)及緩存大小進(jìn)行比較，得到可以提供服務(wù)的源節(jié)點(diǎn)。將上述對B類資源的定義與操作歸納為三級管理：第一級為節(jié)目號，第二級為組號，第三級為具體的B類資源信息（參考點(diǎn)和接收緩存尺度），如圖4所示。

4 基于Pastry路由的域間資源管理

當(dāng)域內(nèi)節(jié)目源信息不能滿足節(jié)點(diǎn)的服務(wù)要求，調(diào)度中心會啟動域間內(nèi)容發(fā)現(xiàn)功能為其服務(wù)。域間內(nèi)容發(fā)現(xiàn)方法在調(diào)度中心之間完成內(nèi)容發(fā)現(xiàn)，從而使調(diào)度中心可獲取其他域的節(jié)點(diǎn)媒體信息。域間資源的管理主要涉及節(jié)目源信息的發(fā)布與查找。本文的P2P VOD系統(tǒng)結(jié)構(gòu)分兩個層次，每個Border為其所管轄域內(nèi)所有客戶端提供服務(wù)（見圖1）。當(dāng)Border要進(jìn)行域間查找時，先要與網(wǎng)絡(luò)中其他的Border進(jìn)行通信，查詢可提供服務(wù)的源。Border間路由通信通過Pastry路由算法來實(shí)現(xiàn)（見圖5）。

4.1 采用單一服務(wù)源多域的發(fā)布策略

為了搜索查找節(jié)目源時得到更快速的響應(yīng)，尤其在域數(shù)量相當(dāng)多時，采用單一服務(wù)源多域的發(fā)布策略。客戶端在該策略下，并非將節(jié)目信息向所有域發(fā)布，而是將節(jié)目信息發(fā)布到所有滿足節(jié)目時間區(qū)間的域，這需要對網(wǎng)絡(luò)中的調(diào)度中心按節(jié)目時間分配ID值。域間內(nèi)容發(fā)現(xiàn)分為3個步驟：1）Pastry網(wǎng)絡(luò)鄰近域節(jié)點(diǎn)查；2）節(jié)點(diǎn)對鄰近域節(jié)點(diǎn)資源發(fā)布；3）鄰近域節(jié)點(diǎn)依照Pastry路由機(jī)制向網(wǎng)絡(luò)中所有滿足節(jié)目時間區(qū)間的域進(jìn)行發(fā)布。在點(diǎn)播流的過程中，節(jié)點(diǎn)的緩存中的流片斷是動態(tài)變化的，當(dāng)節(jié)點(diǎn)的緩存滿時，節(jié)點(diǎn)（客戶端）會向外發(fā)布其服務(wù)能力（B類資源），表明其可以作為服務(wù)者。

4.2 基于節(jié)目源區(qū)間的查找

在P2P點(diǎn)播流媒體系統(tǒng)中，搜索能提供流服務(wù)的源的問題，復(fù)雜性主要在于每個節(jié)點(diǎn)的緩沖區(qū)中的流片斷是動態(tài)變化的。實(shí)際上，點(diǎn)播點(diǎn)間隔很近的節(jié)點(diǎn)，先播放的節(jié)點(diǎn)能從其本地的緩沖區(qū)中提供流給后播放的節(jié)點(diǎn)服務(wù)。采用資源相對值計算及查找服務(wù)原理（與B類資源參考點(diǎn)計算方法類似）和基于Pastry的實(shí)現(xiàn)策略。其中客戶端向其所在的Border發(fā)送查詢請求，Border在域內(nèi)不能滿足需求時，進(jìn)行域間查找。

5 測試結(jié)果

5.1 域內(nèi)延時測試

測試環(huán)境為100 Mbit/s以太網(wǎng)，1個調(diào)度中心服務(wù)器，1個媒體服務(wù)器，40個客戶終端PC?？蛻舳斯?jié)點(diǎn)通過原語與調(diào)度中心進(jìn)行信令通信，表1與表2分別為操作原語和高級操作（VCR）原語的平均延時。

表1 域內(nèi)P2P原語響應(yīng)延時 ms

表2 VCR操作原語的響應(yīng)延時 s

5.2 域間延時測試

實(shí)驗(yàn)環(huán)境是以太網(wǎng)連接的40臺配置相同的PC，用于模擬40個域間網(wǎng)絡(luò)節(jié)點(diǎn)（Border），其域間Pastry網(wǎng)絡(luò)平均路由跳數(shù)的測試結(jié)果為1.56。

6 小結(jié)

針對當(dāng)前電信網(wǎng)絡(luò)對P2P VOD系統(tǒng)中媒體資源的發(fā)布查找等功能進(jìn)行設(shè)計與實(shí)現(xiàn)。主要圍繞3個方面：1）系統(tǒng)中所有客戶端上的資源采用二級架構(gòu)管理——域內(nèi)和域間，具體來說，域內(nèi)所有客戶端的資源的調(diào)度由該域內(nèi)的調(diào)度中心負(fù)責(zé)，而不同域之間的資源調(diào)度，由各個調(diào)度中心通過P2P分布網(wǎng)絡(luò)機(jī)制來進(jìn)行資源調(diào)度管理；2）為了對媒體資源進(jìn)行準(zhǔn)確快速定位，調(diào)度中心按照客戶對點(diǎn)播節(jié)目不同時間點(diǎn)的需要，對節(jié)點(diǎn)發(fā)布的媒體資源信息分類管理；3）根據(jù)客戶端緩存數(shù)據(jù)的變化特性，提出資源值參考點(diǎn)的計算方法，使得域內(nèi)、域間資源采用統(tǒng)一相對值形式表示，在此基礎(chǔ)上進(jìn)行高效率域內(nèi)快速搜索和域間Pastry路由。同時在網(wǎng)絡(luò)資源發(fā)布時，也基于此方法將客戶機(jī)緩存的數(shù)據(jù)進(jìn)行區(qū)間劃分，使其能同時在多域發(fā)布，達(dá)到平衡整個網(wǎng)絡(luò)負(fù)載的目的。實(shí)驗(yàn)結(jié)果表明，資源管理方法能夠滿足P2P VOD系統(tǒng)用戶點(diǎn)播延時需求。

[1]LIU Ran，YIN Hao，HUI Wen.PMSAI：A novel peer-to-peer multimedia streaming architecture over IMS[C]//Proc.IEEE 16th International Conference on Parallel and Distributed Systems.[S.l.]：IEEE Press，2010：724-729.

[2]陳俊，杜旭，程文青，等.對等網(wǎng)絡(luò)點(diǎn)播系統(tǒng)中一種分布式索引結(jié)構(gòu)[J].華中科技大學(xué)學(xué)報：自然科學(xué)版，2011，39（3）：66-70.

[3]ROWSTRON A，DRUSCHEL P.Pastry：scalable，distributed object location and routing for large-scale peer to peer systems[M].Berlin Heidelberg：Springer-Verlag，2001.

[4]沈時軍，李三立.一種適用于VoD/P2P的存儲調(diào)度策略[J].小型微型計算機(jī)系統(tǒng)，2011，32（2）：203-207.

[5]劉志忠，王懷民.一種雙層P2P結(jié)構(gòu)的語義服務(wù)發(fā)現(xiàn)模型[J].軟件學(xué)報，2007，18（8）：1922-1932.

[6]朱曉輝，陳蘇蓉.基于流媒體的小型分布式視頻點(diǎn)播系統(tǒng)研究[J].微電子學(xué)與計算機(jī)，2010，27（10）：69-78.