一種基于節點帶寬的自適應數據調度策略在PPVoD系統中的應用研究

黃志艷

(泰山職業技術學院，山東泰安 271000)

隨著互聯網寬帶的普及和發展，網絡音頻和視頻已經成為網絡多媒體主流應用，流媒體的誕生，更是促進了這些應用的規?；仙?。流媒體是一種包含數據采集、壓縮、存儲和傳輸等多項技術的一種網絡應用工具。在傳統應用過程中，流媒體通常采用的系統架構是C/S模式，隨著網絡用戶的快速增加，該模式易受到服務器帶寬、并發進程等服務能力的約束，成為流媒體發展的瓶頸。為了解決該問題，在許多計算機學者的努力下，引入了P2P技術，該技術的目的是使網絡中的用戶分享擁有的資源，以無中介、對等的傳輸方式進行資源交換。

在國外，基于P2P技術的流媒體發展迅速，得到十分廣泛的應用，其在世界著名的各大高校，比如斯坦福大學［1］、中弗羅里達大學［2］、馬里蘭大學［3］、香港大學［4］等擁有 P2P 技術研究機構，微軟研究院［5］專門成立了的P2P技術研究組，經過諸多學者的努力，P2P技術研究成果顯著，已經涌現了SkyPe［6］、Split-stream和PeerCast［7］等諸多經典的系統。在國內，基于P2P的流媒體技術也在高速發展著，已經誕生了PPLive［8］、AnySee［9］，PPStream、QQLive［10］等流媒體點播平臺，截至 2012 年6 月，我國 P2P 市場經濟產值已經高達6.83億元，隨著P2P技術的改進和發展，基于該技術的流媒體應用前景廣闊。

1 PPVoD系統中數據傳輸模式

在采用P2P技術的流媒體系統中，數據傳輸模式主要有三種:推模式、拉模式以及推拉結合的模式。

1.1 推模式

推模式(Push)是指數據的擁有者按照既定路徑把自身擁有的數據向外發布。推模式的實現方式主要是組播樹，其要求節點之間必須存在父子關系。該模式的基本思想是主動將數據文件“推”給需要數據的節點，其實質是假設代理節點具有很大的存儲功能和長時間在線，以便將服務器的功能轉嫁于代理節點，其缺陷是一般與系統的動態性和已勾選互相矛盾，很難實現。

1.2 拉模式

拉模式(Pull)是通過接收節點的主動請求以獲得數據，是指接收節點的驅動模式［11］。在基于P2P技術的Cool Streaming直播系統中，基于數據驅動的方式，在覆蓋網中采用了拉模式獲取節點所缺少的數據片段，交換BM信息是每隔一定周期進行一次，這樣以便確認數據是否可以使用。該策略在系統運行過程中會產生一定的延遲，并且這些延遲將會隨著節點的增多不斷地擴散，因此，基于拉模式的數據傳輸系統會降低系統的實時性。

1.3 推拉結合模式

由于單純的推模式和拉模式具有不可抗拒的缺點，為了彌補他們的缺點，人們將推拉(Push-Pull)傳輸模式的優點進行結合，產生了推拉結合模式。在使用該模式的流媒體系統中，時間被分成連續的時間片，根據每個時間片的相關情況，數據傳輸模式采取推模式或拉模式。當系統進入穩定播放階段時，對上個時間片內服務節點的性能進行評估，依據評估結果向每個服務節點制定自身所需數據，之后，采用推模式進行數據傳輸。但是，在推拉結合的模式中，由于推拉數據的閥值不夠明顯，推的數據可能會被重復下載，導致數據冗余和帶寬資源的浪費。

2 PPVoD系統中數據調度策略

基于P2P技術的流媒體系統建立在Gossip協議基礎上，系統中的所有的合作節點能夠自動有機構成一張網狀拓撲結構，因此，某個應用節點可以從多個合作節點中獲得所需數據，同時，該節點也必須分享其擁有的數據，因此，基于P2P技術的流媒體系統的性能和服務質量受流媒體數據調度的效率的直接影響。在P2P流媒體系統中，數據調度策略主要有三種，分別是最少優先策略、隨機調度策略、最急優先策略［12］。

隨機調度策略是三種策略中較為簡單的，該算法在眾多的服務節點中隨機選擇一個擁有所需數據片段的節點作為服務節點，向其發送數據請求，獲得所需數據。該算法具有復雜度較低，便于維護節點之間的負載均衡的特點，但是，該算法由于過于簡單，其忽略了系統間存在的異構性、節點的帶寬、服務質量等特性，因此，其效率低下。

最少優先策略是一種使用較為廣泛的調度策略，它是以數據片段冗余度優先的策略。最少優先策略的基本思想是記錄擁有該節點缺少數據片段的節點數量，節點數目用冗余度表示，冗余度比較小的節點在請求數據時優先被選擇，冗余度較大的節點實施在請求數據時，可以實行任務分配，優先選擇節點帶寬較高的服務節點相應節點請求，因此，該節點能夠動態的實現良好的負載均衡，提高了帶寬利用率。但是，由于即將播放的數據不能及時獲得系統剛剛發布的冗余度較小的數據，忽略了直播系統的實時性需求，不適于對延遲要求較高的系統。

最急優先策略又被稱為貪婪策略，基于該策略的系統中，缺少數據片段的節點優先選擇距離其最近的服務節點下載數據，這樣就可以充分的播放節點的實時性需求，優先選擇緊迫性較高的數據片段，提高了播放的連續性，有效彌補了最少優先策略的缺點。但是該策略忽視了整個系統，只考慮了單個節點，雖然看似對每個節點都有利，實際上降低了數據塊的共享幾率，不能有效調動每個伙伴節點的數據傳輸能力，從而造成系統整體性能的下降。

3 基于節點帶寬的自適應數據調度策略

3.1 數據緩沖區

在P2P系統中，數據調度是一個NP-Hard問題，因此，尋找一個次優的調度方案，成為人們研究的熱點。本文在保證服務質量的條件下，采用自適應多級反饋隊列，推拉結合，高效利用節點帶寬，緩解媒體服務器的負載，基于功能劃分，數據緩沖區分為Extra Buffer、Pushing Buffer和Pulling Buffer三個部分，如圖1所示。

圖1 數據緩沖區結構Fig.1 Data buffer structure

已播緩沖區(Extra Buffer):該緩沖區存放播放點之前的數據，其基本的功能是杜絕產生無效的數據請求，以便能夠為合作節點提供高效的服務，該緩沖區的大小主要取決于數據傳輸時延和節點間數據調度的周期。

拉緩沖區(Pulling Buffer):該緩沖區存放彈性時間較短的數據。為了保證視頻播放的流暢度，該部分所缺少的數據片段具有較高的優先級，系統采用拉模式從合作節點處獲得。該緩沖區的大小主要取決于拉模式造成的數據時延。

推緩沖區(Pushing Buffer):該緩沖區存放緩沖時間較長的數據。其既可以采用拉模式獲得數據片段，也可以采用推模式獲得數據片段，其大小主要取決于該緩沖區需要滿足的服務能力，同時還取決于直播中節點和數據源的播放點之間的差值。

推拉兩緩沖區的大小與系統性能密切相關，影響節點的帶寬利用率、傳輸延遲和播放流暢度，因此，本文基于P2P自身的動態性特征進行適應性調整，能夠獲得較好的系統性能。

3.2 服務節點集、鄰居節點集和備用節點集

備用節點集、鄰居節點集和服務節點集在基于P2P技術的流媒體系統中需要覆蓋網進行維護的三個節點集合。(1)備用節點集是指選擇部分節點放在一起，其可能轉化為鄰居節點;(2)鄰居節點集是指在系統運行過程中，與本節點播放統一頻道的其他正在播放的節點的集合，鄰居節點在運行過程中可能轉化為合作節點;(3)服務節點集指為缺少數據片段的節點提供視頻服務的節點的集合。

圖2 節點集角色轉換流程Fig.2 Node set role conversion process

基于P2P技術的流媒體系統在運行過程中根據數據片段的需要可以動態調整鄰居節點、服務節點和備用節點之間轉換，如圖2所示，轉換過程分為四個步驟:(1)系統初始時，一個節點P加入系統后，此時該節點無法獲得備用節點的緩沖區狀態，因此可以通過覆蓋網中包含的節點信息，收集到近鄰節點并將其存放到備用節點列表中;(2)節點P可以向備用節點請求其擁有的緩沖區狀態，并且節點P和備用節點之間存在同時播放同一頻道，緩沖區重合的現象，那么，節點P可以將該類備用節點轉換為鄰居節點并將其降入鄰居節點集中;(3)節點P會與鄰居節點按照設定周期交換各自的緩沖區狀態，以便高效的進行數據調度;(4)當節點P的鄰居節點由于服務能力過載，無法為節點P提供服務時，其將會被重新納入備用節點集中。

3.3 多層反饋隊列

在本文提出的數據調度策略中，引入了多層反饋隊列機制，該機制可以根據數據片段彈性時間的大小，設置反饋隊列的層次級別，進而估測合作節點服務能力，高效率的進行數據調度。根據合作節點反饋的數據片段的信息，動態更新反饋隊列，本文的多層反饋隊列如圖3所示。

圖3 多層反饋隊列Fig.3 Multi-layer feedback queue

推隊列(Pushing Queue):該隊列存放的數據片段是推緩沖區中所缺少的數據片段，如果這些數據片段存放于其合作節點的緩沖區中，此時可以采用稀有片段優先的選擇策略和拉模式獲取隊列中缺少的數據片段;如果這些數據片段在合作節點緩沖區中不存在，則采用隨機策略和推模式獲取該隊列中缺少的數據片段。

拉隊列(Pulling Queue):該隊列存放拉緩沖區中缺少的數據片段，采用序號優先的數據片段選擇策略以拉模式從合作節點中獲得數據片段;

已發請求隊列(Sent Queue):該隊列存放使用拉模式請求的、但未到達的數據片段。

3.4 數據調度策略分析

基于前面內容所述，本文提出了基于節點帶寬的自適應數據調度策略，經過分析，該策略具有以下三個優勢:

(1)保證對等節點流媒體點播的流暢度。播放點增長到數據片段的序號的時間間隔為數據片度的彈性時間，本文提出的策略可以在每個數據片段的彈性時間內，將所需數據片段放入緩沖區內，彈性時間較低的數據片段采用拉模式，直接從視頻源服務器獲取或者優先從有較強服務能力的合作節點處獲取。

(2)提高帶寬利用率。本文提出的策略能夠準確的評估合作節點服務能力，根據合作節點的處理能力、服務帶寬等服務能力指標自適應調整視頻獲取節點，避免數據片段丟棄率上升，提高了節點帶寬利用率。

(3)拉模式和推模式優勢相連，降低系統延遲。在數據傳輸過程中，拉模式根據接收節點的需求，主動進行數據請求，調度到的數據具有很高的精確度，但產生了附加的延遲;推模式的結果很難預計，但是其延遲較低，因此，將二者的優勢相互結合，在保證播放流暢度前提下，盡量降低系統傳輸延遲。基于節點帶寬的自適應數據調度策略流程如表1所示:

表1 基于節點帶寬的自適應數據調度策略流程Table 1 Based on the node bandwidth adaptive data scheduling strategy process

為了簡化實驗，本文將推隊列和拉隊列中需要調度的數據片段按照傳輸模式分為兩種類型:

(1)在所有合作節點都不存在的數據片段，本文數據調度策略可以采用推模式獲取;

(2)部分已知的合作節點擁有某數據片段，本文數據調度策略使用拉模式獲取;

拉隊列中的數據片段采用序號優先的策略，推隊列中的數據調度策略采用最少優先策略，同時規定，拉隊列中的數據片段的優先級高于推隊列中的數據片段的優先級。

4 實驗及其分析

4.1 實驗環境及評比方法

本文采用實驗環境是PeerSim模擬器。在該模擬器中，本文對P2P流媒體系統進行仿真，網絡節點的動態特性實現方法是按照18%的比例增減覆蓋網中合作節點數量，實驗過程中保持覆蓋網的擁有最多1200個合作節點即可，同時，本文將覆蓋網劃分為16個AS，流媒體直播的流速率1Mbps，其最小位速率256Kbps。

本文評比算法優劣的標準采用源端時延。因為節點數目對源端時延的具有重要的影響。源端時延是指用戶執行點播操作，數據從源端傳輸到客戶端，視頻正常播放之時的客戶需要等待的時間。由于數據片段的時延和丟失取決于數據調度算法，因此數據調度算法大大的影響流媒體的服務質量考核的一個重要指標——時延，節點的源端時延是考核數據調度算法的重要指標。

4.2 實驗結果分析

為了比較自適應數據調度算法的效果，實驗過程中，本文選擇兩個經典的數據調度算法Coolstreaming、Tree。其研究結果如圖4所示。

圖4 節點數目對源端時延造成的影響Fig.4 The number of nodes on the impact of source end delay

由圖4可知，隨著節點數目的增多，Coolstreaming和Tree算法導致系統時延大大增加，嚴重的阻礙了流媒體的擴展性。由于播放初始時，客戶端需要從源服務器獲得數據，初始啟動時，數據調度時延幾乎是相等的，但是，隨著動態調整覆蓋網中的節點數量，節點逐漸增加，因此，節點可以從其他鄰居節點獲得所缺少的數據片段，此時，自適應算法就可以使用多層反饋隊列動態調整數據調度，充分的考慮節點服務性能，降低流媒體系統的源端時延，直至趨于平緩，實驗結果表明，基于節點帶寬自適應數據調度算法能夠降低系統的源端時延，優于Coolstreaming和Tree算法。

5 未來工作總結

本文詳細的分析了現有數據調度策略，提出了基于節點帶寬的自適應數據調度策略，實驗表明該策略有效的降低了數據傳輸時延。該策略研究過程過中，發現未來工作的重點是尋找維護多層反饋隊列和備用節點集的方法，以便更好的降低系統消耗。

［1］ Deshpande H，Hrishikesh and Bawa，Garcia Molina H.streaming live media over a P2P network［R］.In Work at CS – Stanford 2002

［2］ Tran D，Hua K，D.T.Zigzag.an efficient P2P scheme for media streaming［J］.Proc.of IEEE INFOCOM'03，2003，4-6

［3］ Suman Banerjee，Bobby Bhattacharjee，Christopher Kommareddy，etal.Scalable application layer multicast［J］，Proc.Of SIGCOMM'02，2002:205-220.

［4］ Lee，J.Y.B.，Leung，R.W.T.Study of a Server-less Architecture for VoD Applications［J］.Proc IEEE ICME，2002，8:233-236

［5］ N.Venkata Padmanabhan，Helen J.Wang，Philip A.Chou，etal.distributing streaming media content using cooperative networking［J］.Proc.Of ACM/IEEE NOSSDAV.2002，5:12-14

［6］ Deshpande H，Hrishikesh and Bawa，Garcia Molina H.Streaming Live Media over Peers［R］.Stanford University，2001

［7］ Salman A.Baset，Henning Schulzrinne.An analysis of the Skype P2P internet telephony protocol［J］.In Proc.of IEEE INFOCOM 2006，4

［8］ PPLive［DB］.2005，http://www.pplive.com

［9］ Xiaofei Liao，Hai Jin，Yunhao Liu，etal.Scalable Live Streaming Service Based Inter-Overlay Optimization［J］.IEEE Transactions on Parallel and Distribute Systems，2007，18(12):1663-1674

［10］ QQlive［DB］.2009，http://live.qq.com

［11］ Bo Liu，Yansheng Lu，Yi Cui，etal.A measurement study on AS-aware P2P streaming strategies［C］.Proc.of 3rd ICCN.China.2008:564568.

［12］ X.Hei，Y.Liu，and K.W.Ross.IPTV over P2P streaming networks:the mesh-pull approach［J］.IEEE Communications Magazine，2008:8692.