陳 華，宋建新

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 性能評價

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

3.1 場景一

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

圖3 均勻分布場景帶寬提供率對平均塊延時的影響

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

3.2 場景二

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

在該場景下做了兩組實驗:一組是上行帶寬提供率為 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}。實驗結(jié)果如圖4和圖5所示。

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

4 小結(jié)

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

［1］詹曉濤.CDN與P2P相結(jié)合的流媒體系統(tǒng)設(shè)計［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］鄭小樂.對等網(wǎng)絡(luò)流媒體數(shù)據(jù)協(xié)作傳輸研究［D］.合肥:中國科學(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.