異構(gòu)環(huán)境下P2P直播流媒體調(diào)度算法研究

陳 華，宋建新

(南京郵電大學(xué)通信與信息工程學(xué)院，江蘇 南京 210003)

基于“網(wǎng)”的P2P流媒體技術(shù)憑借其優(yōu)異的可擴(kuò)展性、成本低及易部署的優(yōu)勢(shì)，成為解決大規(guī)模流媒體應(yīng)用最重要的技術(shù)途徑之一［1］。其主要由兩部分組成:覆蓋網(wǎng)絡(luò)創(chuàng)建與維護(hù)，數(shù)據(jù)塊調(diào)度算法。前者指的是創(chuàng)建和維護(hù)覆蓋網(wǎng)絡(luò)拓?fù)涞倪壿?，后者指的是?jié)點(diǎn)和鄰居之間交換數(shù)據(jù)塊的邏輯。數(shù)據(jù)塊調(diào)度算法包含塊選擇算法和節(jié)點(diǎn)選擇算法兩部分。關(guān)于數(shù)據(jù)塊調(diào)度算法的研究，一直受到廣泛關(guān)注。從2005年開(kāi)始，基于無(wú)結(jié)構(gòu)網(wǎng)絡(luò)的數(shù)據(jù)驅(qū)動(dòng)(Data－Driven)、基于“網(wǎng)”(Mesh－based)、基于蜂群算法(Swarmingbased)或者基于“拉”式(Pull－based)的調(diào)度策略(例如Chainsaw［2］，CoolStreaming［3］，PRIME［4］等)被相繼提出。該類(lèi)型的協(xié)議在覆蓋網(wǎng)絡(luò)構(gòu)建方面，采用隨機(jī)選擇鄰居節(jié)點(diǎn)的策略，用以構(gòu)造連接度較高的無(wú)結(jié)構(gòu)網(wǎng)絡(luò)。在流媒體傳輸方面，主要采用類(lèi)似Bit－Torrent等文件共享系統(tǒng)傳輸策略，媒體流被切分成數(shù)據(jù)片段(Segment或者Block)，每一個(gè)節(jié)點(diǎn)周期性地向其鄰居節(jié)點(diǎn)通知它當(dāng)前擁有的數(shù)據(jù)片段。與此同時(shí)，每一個(gè)節(jié)點(diǎn)根據(jù)其鄰居節(jié)點(diǎn)的通知，直接向鄰居節(jié)點(diǎn)周期性地請(qǐng)求它所缺少的數(shù)據(jù)片段。而節(jié)點(diǎn)之間是通過(guò)Buffer Map或者其他類(lèi)似機(jī)制來(lái)相互通知當(dāng)前擁有哪些數(shù)據(jù)片段［5］。Buffer Map中每一位均表示某一個(gè)數(shù)據(jù)片段是否在當(dāng)前緩存區(qū)。雖然核心思想簡(jiǎn)單，但卻有著可擴(kuò)展性強(qiáng)、穩(wěn)健性高、實(shí)現(xiàn)簡(jiǎn)單等優(yōu)點(diǎn)。

以上所提到的文獻(xiàn)是由接收端發(fā)起數(shù)據(jù)塊調(diào)度，同樣也可以由發(fā)送端來(lái)發(fā)起數(shù)據(jù)塊調(diào)度。文獻(xiàn)［6］根據(jù)數(shù)據(jù)塊調(diào)度算法是由發(fā)送端發(fā)起還是由接收端發(fā)起將其分為“推”和“拉”兩大類(lèi)。近期也有大量的文獻(xiàn)對(duì)基于“推”策略的算法進(jìn)行研究，如文獻(xiàn)［7－9］等。基于“推”的策略更適合于上行帶寬受限的系統(tǒng)，因?yàn)槠淇梢愿鶕?jù)自身的上行帶寬來(lái)調(diào)整塊的發(fā)送速率;基于“拉”的策略更適合于下行帶寬受限的系統(tǒng)，因?yàn)閴K的請(qǐng)求速率可以根據(jù)自身下行帶寬來(lái)自適應(yīng)地調(diào)整或者優(yōu)先請(qǐng)求接近播放延時(shí)的塊。若上行帶寬和下行帶寬相同，這兩種策略的效果是一樣的，但是，在現(xiàn)實(shí)的網(wǎng)絡(luò)環(huán)境中更容易出現(xiàn)的是上行帶寬受限的場(chǎng)景，所以，基于“推”的策略更具一般性。

本文提出一種帶寬感知的數(shù)據(jù)塊調(diào)度算法，通過(guò)優(yōu)先選擇高上行帶寬的節(jié)點(diǎn)為目的節(jié)點(diǎn)，以便其盡可能地為其他節(jié)點(diǎn)服務(wù)，從而提高系統(tǒng)的性能。

1 系統(tǒng)模型及相關(guān)標(biāo)識(shí)

考慮一個(gè)基于塊的系統(tǒng)，在系統(tǒng)只有一個(gè)源節(jié)點(diǎn)，源節(jié)點(diǎn)產(chǎn)生一定速率的數(shù)據(jù)流，并將其切割成固定大小的數(shù)據(jù)塊，見(jiàn)圖1。

用P表示節(jié)點(diǎn)集合，N為節(jié)點(diǎn)總數(shù)(不含源節(jié)點(diǎn))，Bp表示節(jié)點(diǎn)p∈P的上行帶寬，Bs表示源節(jié)點(diǎn)上行帶寬。C(p)表示節(jié)點(diǎn)p接收到的塊集合，N(c，p)表示仍缺少塊c的鄰居節(jié)點(diǎn)集合。覆蓋網(wǎng)絡(luò)由無(wú)向圖G(V，E)表示，其中，當(dāng)且僅當(dāng)p∈P和q∈P是鄰居關(guān)系時(shí)，(p，q)∈E。數(shù)據(jù)塊大小為L(zhǎng)(單位bit)，源速率為l，塊傳輸過(guò)程由節(jié)點(diǎn)塊數(shù)據(jù)調(diào)度算法完成，且每個(gè)節(jié)點(diǎn)每次只發(fā)送一個(gè)塊給其鄰居節(jié)點(diǎn)。

圖1 系統(tǒng)模型示意圖

2 基于帶寬感知的數(shù)據(jù)塊調(diào)度算法

數(shù)據(jù)塊調(diào)度算法由兩部分組成:塊選擇算法和節(jié)點(diǎn)選擇算法。本文提出的算法LU/WP中塊選擇算法采用最近有用塊優(yōu)先(LU)，節(jié)點(diǎn)選擇算法是以正比于鄰居點(diǎn)的上行帶寬的概率來(lái)選擇目的節(jié)點(diǎn)。

具體描述為，發(fā)送節(jié)點(diǎn)p從其收到的數(shù)據(jù)塊集合C(p)中選擇滿足條件N(c，p)的最近數(shù)據(jù)塊c作為待發(fā)送的目標(biāo)塊。具體的目的節(jié)點(diǎn)選擇算法為，缺少數(shù)據(jù)塊c的鄰居節(jié)點(diǎn)以概率pq被選擇為目的節(jié)點(diǎn)，其中

式中:N(c，p)為不含數(shù)據(jù)塊 c的鄰居節(jié)點(diǎn)集合，ωq=f(Bq)=Bq。算法的偽代碼可參考:

為了更清楚地解釋所提算法，下面將結(jié)合圖2來(lái)說(shuō)明算法LU/WP完成一次調(diào)度的過(guò)程。假設(shè)調(diào)度過(guò)程由節(jié)點(diǎn)A發(fā)起，D1，D2，D3，D4，…為其鄰居節(jié)點(diǎn)，并且各節(jié)點(diǎn)擁有的塊如圖2所示。

以圖2為初始狀態(tài)的LU/WP算法的具體調(diào)度過(guò)程為:

1)選擇最近有效數(shù)據(jù)塊5作為待發(fā)送的塊，然后判斷是否有鄰居節(jié)點(diǎn)缺少塊5，經(jīng)分析發(fā)現(xiàn)D1，D2，D4節(jié)點(diǎn)缺少數(shù)據(jù)塊5，D1，D2，D4成為候選目的節(jié)點(diǎn)。

2)根據(jù)D1，D2，D4的上行帶寬，分別賦予其權(quán)值

圖2 某一時(shí)刻節(jié)點(diǎn)A及其鄰居節(jié)點(diǎn)所擁有的塊集合示意圖

4)發(fā)送數(shù)據(jù)塊給目的節(jié)點(diǎn)。

3 性能評(píng)價(jià)

本文利用一個(gè)專(zhuān)門(mén)開(kāi)發(fā)用于P2P流媒體系統(tǒng)研究的仿真平臺(tái)P2PTV－sim來(lái)驗(yàn)證算法的性能。將基于帶寬感知的算法與傳統(tǒng)的LU/RP(最近有用塊優(yōu)先/隨機(jī)節(jié)點(diǎn)選擇)算法進(jìn)行比較。通過(guò)對(duì)P2PTV－sim源文件中的Config.txt文件對(duì)實(shí)驗(yàn)場(chǎng)景進(jìn)行了設(shè)置。節(jié)點(diǎn)數(shù)(不含源節(jié)點(diǎn))Np=5000 ，傳輸?shù)臄?shù)據(jù)塊數(shù)Mc=300，塊長(zhǎng)度L=100 kbit，數(shù)據(jù)源速率l=1 Mbit/s，服務(wù)器上行帶寬Bs=10 Mbit/s，回放延時(shí)PlayoutDelay=5 s，節(jié)點(diǎn)出度outdegree=20。

3.1 場(chǎng)景一

上行帶寬均勻分布于［0，Bmax］，平均帶寬為=Bmax/2 。考慮上行帶寬提供率 r={1.0，1.2，1.4，1.6，1.8，2.0}的情況，r的不同代表著系統(tǒng)的負(fù)載不同。實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 均勻分布場(chǎng)景帶寬提供率對(duì)平均塊延時(shí)的影響

觀察圖3可以看出，隨著帶寬提供率的增大，LU/RP和LU/WP算法的平均塊傳輸延時(shí)都在下降，但是LU/WP算法的平均塊傳輸延時(shí)明顯小于LU/RP算法，說(shuō)明LU/WP算法的性能更優(yōu)。

3.2 場(chǎng)景二

異構(gòu)環(huán)境中，節(jié)點(diǎn)被分為3類(lèi)，即

在該場(chǎng)景下做了兩組實(shí)驗(yàn):一組是上行帶寬提供率為 r=1 ，異構(gòu)度 h={0，0.2，0.4，0.6，0.8，1};另一組是上行帶寬提供率為 r=1.4 ，異構(gòu)度h={0，0.2，0.4，0.6，0.8，1}。實(shí)驗(yàn)結(jié)果如圖4和圖5所示。

觀察圖4和圖5可以發(fā)現(xiàn)，無(wú)論是在帶寬提供率為1還是1.4的情況下，LU/RP算法的平均塊傳輸延時(shí)都呈增大趨勢(shì)，而LU/WP算法的平均塊傳輸延時(shí)呈下降趨勢(shì)。這是由于，隨著異構(gòu)度的增大，高上行帶寬和低上行帶寬節(jié)點(diǎn)都將增加，隨機(jī)選擇算法，優(yōu)先選擇到低上行帶寬的可能性也在增加，所以性能急劇下降。相反，LU/WP算法則總是優(yōu)先選擇高上行帶寬的節(jié)點(diǎn)，隨著高上行帶寬節(jié)點(diǎn)增加時(shí)，其性能顯著提升。可以看出，通過(guò)優(yōu)先選擇高上行帶寬節(jié)點(diǎn)可以改善系統(tǒng)的性能。

4 小結(jié)

本文對(duì)P2P直播流媒體系統(tǒng)中關(guān)鍵組成部分之一的數(shù)據(jù)塊調(diào)度算法進(jìn)行了研究。提出一種基于帶寬感知的數(shù)據(jù)塊調(diào)度算法，即讓發(fā)送節(jié)點(diǎn)優(yōu)先選擇高上行帶寬的節(jié)點(diǎn)作為目的節(jié)點(diǎn)。通過(guò)仿真發(fā)現(xiàn)，基于帶寬感知的數(shù)據(jù)調(diào)度算法的平均塊傳輸延時(shí)更小。平均塊傳輸延時(shí)是P2P流媒體系統(tǒng)最重要的性能指標(biāo)，故在設(shè)計(jì)數(shù)據(jù)塊調(diào)度算法時(shí)充分利用網(wǎng)絡(luò)環(huán)境的異構(gòu)性能可有效地提高系統(tǒng)的性能。

［1］詹曉濤.CDN與P2P相結(jié)合的流媒體系統(tǒng)設(shè)計(jì)［J］.電視技術(shù)，2009，33(6):67－70.

［2］PAI V，KUMAR K，TAMILMANI K，et al.Chainsaw:eliminating trees from overlay multicast［C］//Proc.IPTPS.［S.l.］:Springer，2005:127－140.

［3］ZHANG Xinyan，LIU Jiangchuan，LI Bo，et al.CoolStreaming/DONet:a data－driven overlay network for efficient live media streaming［EB/OL］.［2011－07 －01］. http://www.cs.sfu.ca/～ jcliu/Papers/CoolStreaming.pdf.

［4］MAGHAREI N，REJAIE R.Prime:peer－to－peer receiver－driven meshbased streaming［J］.IEEE/ACM Transactions on Networking，2009，17(4):1052－1065.

［5］鄭小樂(lè).對(duì)等網(wǎng)絡(luò)流媒體數(shù)據(jù)協(xié)作傳輸研究［D］.合肥:中國(guó)科學(xué)技術(shù)大學(xué)，2009.

［6］BONALD T，MASSOULI L，MATHIEU F，et al.Epidemic live streaming:optimal performance trade－offs［EB/OL］.［2011－07－01］.http://www.cs.ox.ac.uk/people/andy.twigg/papers/sigmetrics08.pdf.

［7］SANGHAVI S，HAJEK B，MASSOULIE L.Gossiping with multiple messages［J］.IEEE Transactions on Information Theory，2007，53(12):4640－4654.

［8］MASSOULIE L，TWIGG A，GKANTSIDIS C，et al.Randomized decentralized broadcasting algorithms［C］//Proc.INFOCOM 2007.［S.l.］:IEEE Press，2007:1073－1081.

［9］ABENI L，KIRALY C，LO C R.On the optimal scheduling of streaming applications in unstructured meshes［C］//Proc.8th International IFIPTC 6 Networking Conference.Berlin:Springer－Verlag，2009:117－130.