異構環境下P2P直播流媒體調度算法研究

陳 華，宋建新

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

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

以上所提到的文獻是由接收端發起數據塊調度，同樣也可以由發送端來發起數據塊調度。文獻［6］根據數據塊調度算法是由發送端發起還是由接收端發起將其分為“推”和“拉”兩大類。近期也有大量的文獻對基于“推”策略的算法進行研究，如文獻［7－9］等。基于“推”的策略更適合于上行帶寬受限的系統，因為其可以根據自身的上行帶寬來調整塊的發送速率;基于“拉”的策略更適合于下行帶寬受限的系統，因為塊的請求速率可以根據自身下行帶寬來自適應地調整或者優先請求接近播放延時的塊。若上行帶寬和下行帶寬相同，這兩種策略的效果是一樣的，但是，在現實的網絡環境中更容易出現的是上行帶寬受限的場景，所以，基于“推”的策略更具一般性。

本文提出一種帶寬感知的數據塊調度算法，通過優先選擇高上行帶寬的節點為目的節點，以便其盡可能地為其他節點服務，從而提高系統的性能。

1 系統模型及相關標識

考慮一個基于塊的系統，在系統只有一個源節點，源節點產生一定速率的數據流，并將其切割成固定大小的數據塊，見圖1。

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

圖1 系統模型示意圖

2 基于帶寬感知的數據塊調度算法

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

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

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

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

以圖2為初始狀態的LU/WP算法的具體調度過程為:

1)選擇最近有效數據塊5作為待發送的塊，然后判斷是否有鄰居節點缺少塊5，經分析發現D1，D2，D4節點缺少數據塊5，D1，D2，D4成為候選目的節點。

2)根據D1，D2，D4的上行帶寬，分別賦予其權值

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

4)發送數據塊給目的節點。

3 性能評價

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

3.1 場景一

上行帶寬均勻分布于［0，Bmax］，平均帶寬為=Bmax/2 。考慮上行帶寬提供率 r={1.0，1.2，1.4，1.6，1.8，2.0}的情況，r的不同代表著系統的負載不同。實驗結果如圖3所示。

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

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

3.2 場景二

異構環境中，節點被分為3類，即

在該場景下做了兩組實驗:一組是上行帶寬提供率為 r=1 ，異構度 h={0，0.2，0.4，0.6，0.8，1};另一組是上行帶寬提供率為 r=1.4 ，異構度h={0，0.2，0.4，0.6，0.8，1}。實驗結果如圖4和圖5所示。

觀察圖4和圖5可以發現，無論是在帶寬提供率為1還是1.4的情況下，LU/RP算法的平均塊傳輸延時都呈增大趨勢，而LU/WP算法的平均塊傳輸延時呈下降趨勢。這是由于，隨著異構度的增大，高上行帶寬和低上行帶寬節點都將增加，隨機選擇算法，優先選擇到低上行帶寬的可能性也在增加，所以性能急劇下降。相反，LU/WP算法則總是優先選擇高上行帶寬的節點，隨著高上行帶寬節點增加時，其性能顯著提升。可以看出，通過優先選擇高上行帶寬節點可以改善系統的性能。

4 小結

本文對P2P直播流媒體系統中關鍵組成部分之一的數據塊調度算法進行了研究。提出一種基于帶寬感知的數據塊調度算法，即讓發送節點優先選擇高上行帶寬的節點作為目的節點。通過仿真發現，基于帶寬感知的數據調度算法的平均塊傳輸延時更小。平均塊傳輸延時是P2P流媒體系統最重要的性能指標，故在設計數據塊調度算法時充分利用網絡環境的異構性能可有效地提高系統的性能。

［1］詹曉濤.CDN與P2P相結合的流媒體系統設計［J］.電視技術，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］鄭小樂.對等網絡流媒體數據協作傳輸研究［D］.合肥:中國科學技術大學，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.