一種基于激勵機制的P2P流媒體數據傳輸策略

韓亞峰,董孝珍

（河南科技學院,河南新鄉(xiāng)453003）

隨著P2P技術和流媒體技術的迅速發(fā)展,基于P2P的流媒體直播系統(tǒng)已經成為互聯(lián)網的主要應用之一.為改善傳統(tǒng)的樹狀結構[1]和網狀結構[2]的不足,近幾年來出現了分層的P2P直播系統(tǒng)模型,如Anysee[3]、PPLive[4]和HCPON[5]等系統(tǒng),該模型在流媒體數據傳輸上采用分層異構的方式,提高了系統(tǒng)的服務質量.但由于P2P網絡的復雜性、動態(tài)性以及流媒體數據量大的特點,在節(jié)點負載均衡、節(jié)點之間相互配合等方面還存在著一定的問題,這些問題影響了直播系統(tǒng)的播放質量以及規(guī)模的擴大.P2P流媒體直播系統(tǒng)中的數據傳輸策略正是問題的來源之一,因此對于分層P2P直播系統(tǒng)而言,如何通過合理的數據傳輸策略,在簇內進行有效的數據分發(fā)至關重要.

目前,在P2P流媒體直播系統(tǒng)中主要有推、拉以及推拉結合3種數據傳輸策略.分層結構HCPON[5]簇內采用單一的推傳輸機制,這種機制使得簇內數據分發(fā)較快,但NP節(jié)點資源利用率低,并且由于簇首承擔了全部的數據分發(fā)功能,易引起其負載過重；分層結構PPLive系統(tǒng),簇內采用單一的拉傳輸機制,這種機制雖然抗擾動強,NP節(jié)點資源利用率有所提高,但該機制傳輸時延較大,使得簇內數據分發(fā)較慢.為充分利用推拉的優(yōu)點,最近在網狀結構中又引入了推拉結合[2,6]的策略,如GridMedia[2].現有的數據傳輸策略都不能在簇首負載、數據分發(fā)速率以及資源利用率等關鍵性能參數之間達到很好的平衡,同時缺乏相應的激勵機制,不能充分發(fā)揮P2P網絡的優(yōu)勢.對此,本文以分層直播系統(tǒng)LStream為背景,設計了一種基于激勵機制的推拉相結合的數據傳輸策略,該策略結合網狀結構中推拉結合的思想,并且引入了激勵機制,不但充分利用了網絡資源,而且有效地防止了簇首負載過重,減輕了簇首的壓力.

1 LStream設計方案

分層P2P流媒體直播系統(tǒng)LStream系統(tǒng)在管理層面上采用節(jié)點集中管理方式,整個系統(tǒng)部署一個服務器TrackSrv（TS）管理所有的節(jié)點信息.在數據傳輸上,LStream采用兩層分簇架構,簇間采用應用層組播技術構造轉發(fā)樹,簇內基于數據驅動的思想組成覆蓋網.系統(tǒng)中參與數據分發(fā)的節(jié)點主要包括以下幾類：CS、SP、SNP以及NP.其中,CS為頻道源服務器,實現視頻源的編碼和發(fā)送；SP由系統(tǒng)固定部署的可信且能力較強的節(jié)點組成,完成多頻道數據的傳輸；SNP是由TS動態(tài)選取的節(jié)點,負責一個頻道信息的轉發(fā),且兩者都參與簇間轉發(fā)樹的構造并以簇首的身份實現對簇內NP節(jié)點的管理,簇的形成遵循地域相近頻道相同的NP節(jié)點位于同一簇的原則.

在LStream系統(tǒng)中,SP和SNP形成的上層結構,由于較好的穩(wěn)定性,采用推的數據傳輸策略,實現多頻道的數據轉發(fā)；而在簇內,節(jié)點穩(wěn)定性差,采用推機制顯然不合適,但拉機制又會使得簇內數據分發(fā)較慢.因此,在簇內選擇和設計合適的數據傳輸策略,保證系統(tǒng)的整體性能非常重要.

2 基于激勵機制的數據傳輸策略

本文結合LStream系統(tǒng)的特點,在簇內,設計了一種基于激勵機制的推拉相結合的數據傳輸策略ICTMS（An Incentive based Tree-push/Mesh-pull strategy）,該策略充分結合推拉機制的優(yōu)點,并引入激勵機制.以簇為單位,簇首周期選擇上傳能力強的若干節(jié)點,稱這些節(jié)點為簇首的邏輯子節(jié)點,簇首僅對邏輯子節(jié)點采用推機制優(yōu)先進行數據推送,使得這些節(jié)點快速地獲得數據并在簇內快速地分發(fā),而簇內其他節(jié)點均采用拉機制直接或間接地從這些邏輯子節(jié)點獲得數據.

2.1 簇首負載分析

為有效地防止簇首負載過重,減輕簇首的壓力,需要對簇首的資源分配加以分析.在影響簇首負載的諸多因素中,帶寬的均衡分配直接影響系統(tǒng)的播放質量.在LStream系統(tǒng)中,簇首主要負責為子節(jié)點和各個簇的邏輯子節(jié)點分配帶寬,并且ICTMS策略用于簇內,簇首的負載主要與簇首負責的邏輯子節(jié)點總數LC有關,如果簇內邏輯子節(jié)點數過小,簇內播放質量就會很差；另外簇首管理多個簇且資源有限,如果其中一個簇邏輯子節(jié)點過多,勢必影響該簇首管理的其他簇的性能,所以ICTMS策略需要解決的首要問題就是要對LC加以限制.

在LStream系統(tǒng)中,主要負責為子節(jié)點和邏輯子節(jié)點分配上傳帶寬,當簇首負責轉發(fā)數據的子節(jié)點和邏輯子節(jié)點都正常播放時,實際需要的帶寬B1與簇首的子節(jié)點數n、邏輯子節(jié)點總數LC和節(jié)點正常播放時簇首需要為它分配的上傳帶寬b有關,所以對于任意的簇首都有

假設簇首可提供的最大帶寬B2是定值,子節(jié)點數n已知,并且n個子節(jié)點占用的帶寬遠小于B2.基于這種假設,簇首的負載僅與LC有關,當LC過小時,B1遠小于B2,此時簇首帶寬利用率低,簇內數據分發(fā)較慢；當LC過大時,B1遠大于B2,引起簇首負載過重.所以為了有效利用簇首的資源,需要計算恰當的LC值,最佳的條件是

簇首支持的最大邏輯子節(jié)點總數應為

在LStream系統(tǒng)中,為充分利用簇首的帶寬,盡可能地使得簇首管理的所有的簇都能正常播放,簇首在分配邏輯子節(jié)點時,遵循以下原則：先分配小簇,優(yōu)先滿足小簇正常播放的要求；再分配大簇,盡量使這些大簇也能正常播放.基于這種原則,對于任意的簇j,簇首都采用表達式（3）為其分配邏輯子節(jié)點數A（j）.具體思想為：比較簇j正常播放時,至少需要的邏輯子節(jié)點數B（j）和平均邏輯子節(jié)點數C（其中C=MAX（LC）/M,M 表示當前簇首管理的簇數）,如果 j是小簇,令 A（j）=B（j）,否則 A（j）等于未分配的邏輯子節(jié)點數除以未分配邏輯子節(jié)點的簇數.所以簇j實際分配到的邏輯子節(jié)點數A（j）可確定為

2.2 上傳能力度量

在ICTMS中,簇內邏輯子節(jié)點的選取依據的唯一性能參數是上傳能力,如何有效地度量該性能參數,使得這種度量更能充分反映節(jié)點的上傳能力,是該策略需要解決的另一個重要的問題.該策略中NP節(jié)點的上傳能力用單位時間內上傳的有效數據分片數來表示,所謂有效數據分片是指該分片是在播放時刻之前到達的,并且為了準確地表示NP節(jié)點的上傳能力,NP節(jié)點的上傳能力是由鄰居節(jié)點評價,即對于任意一個NP節(jié)點,當前所有的鄰居節(jié)點都為它周期計算一個評價分數SCORE,并發(fā)送給簇首節(jié)點,簇首節(jié)點收集所有鄰居節(jié)點對該節(jié)點的評價分數,周期計算它的上傳能力UC.SCORE的計算公式

其中,節(jié)點j代表節(jié)點i的任意的一個鄰居節(jié)點；SCORE（i,j）代表節(jié)點j對i的上傳能力評價分數；SCORE（i,j,k）表示j從i收到的第k個數據分片的標志,如果該分片在播放時刻之前到達,則該標志為1,否則為0；PNUM代表一個周期內節(jié)點i上傳給節(jié)點j的數據分片總數；NS代表節(jié)點i的鄰居子節(jié)點集合.在一個周期內,節(jié)點i的總體上傳能力UC（i）可確定為

2.3 算法設計

ICTMS策略中,推機制主要用于簇首向邏輯子節(jié)點傳輸數據.對于系統(tǒng)中的任意NP節(jié)點,簇首都為它維護一個上傳能力參數UC,該參數周期更新,然后以簇為單位,簇首依據節(jié)點的上傳能力在簇內周期選擇上傳能力強的若干邏輯子節(jié)點,對邏輯子節(jié)點簇首以推的方式直接推送數據,而簇內其他的節(jié)點,均采用拉的方式從鄰居節(jié)點獲得數據.并且為減小系統(tǒng)的啟動時延,在ICTMS算法中,節(jié)點在剛加入系統(tǒng)時,在采用拉的機制從鄰居節(jié)點獲得數據的同時,簇首也采用推的機制為其發(fā)送最初的幾十秒數據.

算法用到的參數描述,如表1所示.

表1 ICTMS算法相關參數Tab.1 Relative parameters of ICTMS

假設執(zhí)行ICTMS算法的周期為T,設定時器為timer,當定時器timer為T時,對于當前簇首的管理的任意簇j,簇首都依次執(zhí)行ICTMS算法,并且定時器timer清零,重新計時,具體算法：

（1）確定LStream系統(tǒng)中簇的劃分,簇首節(jié)點以及簇內的任意節(jié)點；

（2）如果該節(jié)點為新加入系統(tǒng)的節(jié)點,當前簇首S采用推的機制進行前10 s的數據分發(fā),算法結束；

（3）如果該節(jié)點為非新加入節(jié)點,簇首通過式（5）周期計算任意鄰居節(jié)點對該節(jié)點的評價分數SCORE,再通過式（6）獲得該節(jié)點的總體上傳能力UC；

（4）對于簇內的任意非新加入節(jié)點都執(zhí)行步驟3,計算該節(jié)點的UC；

（5）將簇內節(jié)點按照UC由高到低的順序進行排序；

（6）通過式（3）和式（4）計算當前簇首支持的最大邏輯子節(jié)點總數MAX（LC）,進而得到簇實際分配到的邏輯子節(jié)點數A；

（7）從簇內節(jié)點中選出UC值最大的前A個節(jié)點作為簇首的子節(jié)點,即SNP節(jié)點,簇首通過推的機制先這A個節(jié)點進行數據分發(fā),而簇內的其他節(jié)點,通過拉的機制從任意鄰居節(jié)點獲得數據.

3 實驗驗證

采用D_P2P_SIM作為仿真模擬工具,首先通過修改D_P2P_SIM仿真軟件,構建LStream系統(tǒng)的拓撲結構,模擬在LStream系統(tǒng)的簇內,分別采用ICTMS、推和拉3種數據傳輸策略.實驗中覆蓋網的節(jié)點數目限制在0～3 000之間,播放速率為300～340 Kb/s,每個數據包大小為2 Kb,對于任意的簇首,最多管理5個簇,并且每個簇最多有30個普通節(jié)點.在拉傳輸機制下,緩存映射表BM的交換周期和數據請求周期假設都為1 s,每次請求2個數據包,每個數據包的大小為2 Kb,每個普通節(jié)點最多有5個鄰居節(jié)點.在ICTMS算法中,比例因子N為1/2.

為了評估算法的優(yōu)劣,主要考慮了5個關鍵參數：

參數1：平均占用簇首帶寬是簇首為自身邏輯子節(jié)點提供的上傳帶寬與簇首的實際帶寬的比值,用來衡量簇首的壓力,平均占用簇首帶寬越多,簇首壓力越大.

參數2：平均傳輸時延,是從發(fā)出數據請求到接受到該數據等待的時間,主要用來衡量數據的分發(fā)速率,平均數據時延越小,簇內數據分發(fā)越快.

參數3：節(jié)點上傳帶寬,即單位時間內簇內所有NP節(jié)點上傳的數據包之和,主要用來衡量系統(tǒng)的資源利用率,節(jié)點的上傳帶寬越高,系統(tǒng)的資源利用率就高.

參數4：平均啟動時延,為簇內NP節(jié)點從加入系統(tǒng)時刻到開始播放時刻之間的時間差.

參數5：播放流暢程度,用單位時間內節(jié)點收到的數據包數與節(jié)點連續(xù)播放所需要的數據包數比值來表示.

為避免偶然性,每個實驗都經過多次測試,然后取平均值,實驗結果如表2所示.

表2 3種數據傳輸策略比較Tab.2 Comparison of three data transmission strategies

由表2可知,在相同實驗環(huán)境下,ICTMS策略平均占用簇首的帶寬比推機制減少了將近20%,與拉機制幾乎相等,這說明,ICTMS策略能夠有效的降低簇首的負載,在一定程度上減輕了簇首的壓力,有利于系統(tǒng)的可擴展性.在系統(tǒng)規(guī)模一定,運行時間相同的情況下,ICTMS的平均傳輸時延低于拉機制.因此,相對于拉機制,ICTMS策略簇內數據分發(fā)更快,更滿足直播系統(tǒng)實時性的要求.在運行環(huán)境以及運行時間相同的情況下,三種數據傳輸策略的節(jié)點上傳帶寬和節(jié)點平均啟動時延對比情況表明,ICTMS策略能夠更好地利用節(jié)點的帶寬資源,因此系統(tǒng)資源利用率更高,并且相對于推和拉機制,ICTMS策略下系統(tǒng)的啟動時延更低.隨著節(jié)點數目的增加,三種數據傳輸策略的播放質量都有所下降,但ICTMS數據傳輸策略的下降速度相對于推、拉機制比較平緩.因此與推、拉機制相比,ICTMS數據傳輸策略具有更好的播放質量,更適合大規(guī)模的應用.

4 小結

基于激勵機制的推拉相結合的數據傳輸策略ICTMS,具有以下優(yōu)點：①充分結合推拉的優(yōu)點,減小了系統(tǒng)的數據傳輸時延,從而實現了簇內數據的快速分發(fā)；②引入激勵機制,在簇內起到了激勵作用,從而在一定程度上提高了節(jié)點的資源利用率；③兼顧了簇首節(jié)點的負載問題,將部分數據分發(fā)功能分攤到簇內邏輯子節(jié)點上,并通過對邏輯子節(jié)點數加以限制以及在各個簇中合理的分配邏輯子節(jié)點來防止簇首負擔過重、有效減輕簇首壓力；④相對于推、拉機制,ICTMS減小了系統(tǒng)的啟動時延,進一步提高了系統(tǒng)的整體性能.

[1]Tran D A,Hua K A,Do T.Zigzag：an efficient peer-to-peer scheme for media streaming[C].Proceedings of the IEEE Computer and Communications,INFOCOM,2003：1672-1687.

[2]Xie S S,Li B,Keung GY,et al.Cool-streaming：Design,Theory,and Practice[J].IEEE Transactions,2007,9（8）：1661-1671.

[3]Liao X F,Jin H,Liu YH,et al.AnySee：Peer-to-Peer Live Streaming[C].In：Proc.of INFOCOM'06,2006：1-10.

[4]Long V,Indranil G,Jin L,et al.Mapping the PPLive Network：Studying the Impacts ofMedia Streaming on P2P Overlays[R].UIUC：Tech.Rep,2006.

[5]程普,陳越,黃平川,等.一種分層分簇的P2P流媒體覆蓋網絡模型[J].計算機工程與應用,2007,43（22）：140-142.

[6]Ouali A,Kerherve B,Jaumard B.Toward New Peering Strategies For Push-Pull Based P2P Streaming Systems[C].Ultra Modern Telecommunications&Workshops,2009.ICUMT'09.International Conference on Digital Object Identifier,2009：1-8.