[發明專利]一種基于調度期限和帶寬感知的數據調度方法

無效

• 申請號: 201010589063.7
• 申請日: 2010-12-15
• 公開（公告）號: CN102035888A
• 公開（公告）日: 2011-04-27
• 發明（設計）人: 胡瑞敏;楊紅云;陳軍;陳鐃;朱永瓊
• 申請（專利權）人: 武漢大學
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 張火春

技術領域

本發明屬于P2P流媒體技術領域，尤其涉及一種數據調度方法。

背景技術

P2P流媒體包括覆蓋網絡拓撲構建和數據調度兩個部分。覆蓋網絡拓撲構建是指尋找鄰居節點從而使一個應用層網絡被組織起來；而數據調度是指在已經構建好的覆蓋網絡之上進行流媒體傳輸，包括決定從哪些鄰居節點得到哪些數據、向哪些鄰居節點轉發哪些數據。基于樹型覆蓋拓撲的有結構P2P流媒體系統因具有確定的調度策略，所以易于獲得最優的分發延遲性能，但是由于對節點動態性的魯棒性差以及很難管理，實際中很少使用。基于網狀(mesh)覆蓋拓撲的無結構P2P流媒體(簡稱為：網狀無結構P2P流媒體)系統由于具有良好的可擴展性和魯棒性使得其更適合于異構、動態的互聯網環境，在實際中被廣泛采用。但是網狀無結構P2P流媒體系統的性能難以預測，且由于節點之間鄰居關系的動態性以及數據分發的實時性，使得數據調度問題成為網狀無結構P2P流媒體領域的一個重要問題，而合理組織數據和調度策略設計成為數據調度的關鍵。

目前，在網狀無結構P2P流媒體中，數據調度策略是采用類似Bittorrent(BT)文件共享軟件的分片機制，源節點將媒體流分成被稱為數據塊(segment、chunk或block)的小片段后在參與流分發會話的對等節點之間進行轉發。數據調度策略就是擁有某數據塊集的節點向哪些鄰居節點發送哪些數據塊所依據的調度策略，因此數據調度策略設計的關鍵是任意兩個節點之間進行數據傳輸的節點/塊選擇算法，即數據調度算法。數據調度方法根據是由發送方還是由接收方做出選擇決定被分為基于推(push)的方法、基于拉(pull)的方法和推拉混合(hybridpull/push)的方法。

基于推的方法主要由發送方根據鄰居節點緩存數據狀態主動選擇數據塊，并向目標節點推送的方法，該方法具有延遲小、控制開銷小的優點，但是由于節點之間缺乏協作，因此可能存在同時有多個節點向同一個鄰居節點發送相同數據的情況，造成數據分發的冗余而浪費了網絡帶寬資源。目前有文獻^[1-2]證明在基于推的數據調度方法中LU(Latest?Useful?Chunk?Scheduling，最近有用塊數據調度)方法是最優的。T.Bonald等人^[1]將LU/RP(最近有用塊/隨機節點)的調度策略用在全連接網狀拓撲結構中，并能夠獲取優異的數據塊分發速率和分發延遲性能。文獻^[2]考慮到上行帶寬能力高的節點在塊分發過程中貢獻更多，提出了利用節點上行帶寬的異構性的最近有用塊/帶寬感知的節點選擇(LU/BA)方法，在全網狀拓撲結構中、節點帶寬異構的情況下LU/BA方法較LU/RP方法能夠獲得80％的塊分發延遲性能的提升。但是上述數據調度方法都是假設覆蓋網絡中節點之間拓撲是全連接的，即節點與覆蓋網絡中其它所有節點都是連接的，并能通過周期性緩存信息交換知道其它所有節點擁有數據塊的信息。而在實際網絡中，特別是在P2P流媒體系統往往具有百萬級用戶的情況下是不可能實現節點間拓撲的全連接的，這將會影響到數據塊在整個系統中的傳輸速度，當播放延遲一定，在節點只與系統中部分節點建立鄰居關系的情況下，LU/BA方法的數據丟包率較高。

文獻1：T.Bonald，L.Massoulie，F.Mathieu，D.Perino，Andrew?Twigg，“Epidemic?Live?Streaming：Optimal?Performance?Trade-Offs”，ACM?Sigmetrics?08，Annapolis，MD，June?2008.

文獻2：A.Couto?da?Silva，E.Leonardi，et?al.，″Chunk?Distribution?inMesh-Based?Large?Scale?P2P?Streaming?Systems：a?Fluid?Approach.″IEEETransactions?on?Parallel?and?Distributed?Systems(99)：1-1.

發明內容

針對上述存在的技術問題，本發明提出一種用于網狀無結構P2P流媒體中的、基于調度期限和帶寬感知的數據調度方法，該方法主要采取由發送方做出選擇的推(push)方法，充分考慮了數據塊播放期限和節點帶寬的異構性，優先向高帶寬節點轉發離播放期限最近的數據塊，降低了數據塊由于超過播放期限而丟棄的概率，提升了網絡資源的利用率。

為達到上述目的，本發明采用如下技術方案：

一種基于調度期限和帶寬感知的數據調度方法，包括以下步驟：