[發明專利]一種基于十字鏈表的P2P流媒體下載方法和系統

有效

• 申請號: 201010117154.0
• 申請日: 2010-03-02
• 公開（公告）號: CN101841557A
• 公開（公告）日: 2010-09-22
• 發明（設計）人: 王雷;李靜遠;林思明;劉悅;程學旗;馮凱;劉祥濤
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: H04L29/08
• 分類號: H04L29/08;H04L29/06;H04N7/24
• 代理公司: 北京律誠同業知識產權代理有限公司 11006
• 代理人: 祁建國;梁揮

1.一種基于十字鏈表的P2P流媒體下載方法，其特征在于，所述方法，包括下列步驟：

步驟100.用戶節點采用十字鏈表數據結構為每個鄰居節點維護一個鄰居節點下載任務隊列，為每個數據分片維護一個數據分片下載任務隊列，并將兩個隊列存儲于用戶節點本身；

步驟200.所述用戶節點在擁有預備下載的數據分片的鄰居節點集合中，選擇所述用戶節點本地所維護的下載任務十字鏈表中相應鄰居節點的下載任務隊列中所有任務的估計完成時間最小的鄰居節點，將該下載任務交給該節點完成所述數據分片的下載任務，同時更新所述鄰居節點下載任務隊列和數據分片下載任務隊列。

2.根據權利要求1所述的基于十字鏈表的P2P流媒體下載方法，其特征在于，所述下載任務通過下載任務三元組記錄，所述下載任務三元組為<P_i，b_j，T_i.j>，其中P_i為資源節點的節點標識，b_j為準備下載的數據分片的標識，T_i.j為該任務的預計完成時刻；

其中T_i.j的計算方法為：Tf(P_i)+block_size/v(P_i)，其中block_size為數據分片的大小，v(P_i)為資源節點P_i到用戶節點的數據傳輸速率。

3.根據權利要求1所述的基于十字鏈表的P2P流媒體下載方法，其特征在于，所述步驟200，包括下列步驟：

步驟210.所述用戶節點在擁有準備下載的數據分片的鄰居節點中，選擇其下載隊列所有任務的估計完成時間最小的鄰居節點安排下載該數據分片的任務；

步驟220.所述用戶節點建立相應數據下載任務三元組記錄所述下載任務；

步驟230.所述用戶節點更新所述下載任務三元組中所述鄰居節點對應的下載任務隊列的所有任務的估計完成時刻；同時更新所述數據分片對應的下載任務隊列的最早完成時刻。

4.根據權利要求2所述的基于十字鏈表的P2P流媒體下載方法，其特征在于，所述方法，還包括下列步驟：

步驟300.所述用戶節點周期性更新所述下載任務三元組中所述鄰居節點對應的下載任務隊列的所有任務的估計完成時刻；同時更新所述預備下載的數據分片對應的下載任務隊列的最早完成時刻，返回步驟200。

5.根據權利要求4所述的基于十字鏈表的P2P流媒體下載方法，其特征在于，所述步驟300，包括下列步驟：

步驟310.所述用戶節點在間隔時間內估計并更新各個所述鄰居節點到所述用戶節點的下載速率；

步驟320.所述用戶節點根據所述估算的下載速率，估算各個所述下載任務三元組的估計下載完成時刻；

步驟330.所述用戶節點更新各個下載任務三元組中所述鄰居節點對應的下載任務隊列的所有任務的估計完成時刻；同時更新各個下載任務三元組中所述數據分片對應的下載任務隊列的最早完成時刻記錄；

步驟340.判斷是否存在待下載的數據分片在預計播放時刻之前無法到達，若是，則根據步驟100至步驟200所述方法重新調度待下載的數據分片的下載任務。

6.根據權利要求1所述的基于十字鏈表的P2P流媒體下載方法，其特征在于，在P2P點播系統中用戶節點在發現用戶進行跳轉操作時，或在P2P直播系統中用戶節點的節目時延較大時，所述方法，還包括下列步驟：

步驟400.根據用戶的跳轉要求，執行點播跳轉操作。

7.根據權利要求2所述的基于十字鏈表的P2P流媒體下載方法，其特征在于，所述步驟400，包括下列步驟：

步驟410.所述用戶節點清空所述下載隊列中的所有下載任務三元組；

步驟420.所述用戶節點向所有已確定的資源節點發送取消下載請求；

步驟430.所述用戶節點從用戶選擇的新時刻，或直播系統給定的新時刻起采用步驟100的方法重新建立十字鏈表數據結構的下載任務隊列。