韓亞峰,董孝珍

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

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

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

1 LStream設(shè)計方案

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

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

2 基于激勵機制的數(shù)據(jù)傳輸策略

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

2.1 簇首負載分析

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

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

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

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

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

2.2 上傳能力度量

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

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

2.3 算法設(shè)計

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

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

表1 ICTMS算法相關(guān)參數(shù)Tab.1 Relative parameters of ICTMS

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

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

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

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

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

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

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

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

3 實驗驗證

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

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

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

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

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

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

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

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

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

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

4 小結(jié)

基于激勵機制的推拉相結(jié)合的數(shù)據(jù)傳輸策略ICTMS,具有以下優(yōu)點：①充分結(jié)合推拉的優(yōu)點,減小了系統(tǒng)的數(shù)據(jù)傳輸時延,從而實現(xiàn)了簇內(nèi)數(shù)據(jù)的快速分發(fā)；②引入激勵機制,在簇內(nèi)起到了激勵作用,從而在一定程度上提高了節(jié)點的資源利用率；③兼顧了簇首節(jié)點的負載問題,將部分數(shù)據(jù)分發(fā)功能分攤到簇內(nèi)邏輯子節(jié)點上,并通過對邏輯子節(jié)點數(shù)加以限制以及在各個簇中合理的分配邏輯子節(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流媒體覆蓋網(wǎng)絡(luò)模型[J].計算機工程與應(yīng)用,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.