[發明專利]一種基于訪問頻度變長邏輯分段的數據分發方法

有效

• 申請號: 200910085125.8
• 申請日: 2009-06-02
• 公開（公告）號: CN101645888A
• 公開（公告）日: 2010-02-10
• 發明（設計）人: 王勁林;尤佳莉;王玲芳;李廷屹;鄧浩江
• 申請（專利權）人: 中國科學院聲學研究所
• 主分類號: H04L29/06
• 分類號: H04L29/06;H04L29/08;H04L12/56;H04L1/00
• 代理公司: 北京法思騰知識產權代理有限公司
• 代理人: 楊小蓉

1.一種基于訪問頻度變長邏輯分段的數據分發方法，對于分發到網絡中的文件 f，分發過程如下：

1)將文件f切分為大小相等的小數據塊ub序列{ub₁，ub₂，...，ub_n}；

2)根據文件f的初始用戶訪問概率分布函數g(x)，計算得到每一個ub_i的訪問概 率積分，整個序列的概率為{q₁，q₂，...，q_n}；

3)通過合并算法，將ub序列進行合并，生成數據片段序列 {seg₁，seg₂，...，seg_k}，并為每個數據片段seg計算流行度和副本等級，其中，副 本等級計算方法如下：

假設D(l)是計算副本數目的函數，其只跟副本等級和總節點數相關，則目標方 程為：

F′(L,Λ)=argmin{Σm=1MΣk=1kmsucm,kD(lm,k)+λ(Σm=1MΣk=1kmcm,kqm,klm,k-A)}]]>

其中，L為副本等級，k_m為第m個文件的數據片段數目；c_m，k為第m個文件中 第k個數據片段seg中所包含的小數據塊ub數目；l_m，k為第m個文件中第k個數據 片段seg所對應的副本等級數，通過數值分析中的線性規劃算法估計該l_m，k的值；q_m，k為第m個文件中第k個數據片段seg對應的用戶訪問概率，A為預設的平均延遲；

4)根據所述步驟3)中的計算結果，得到所有數據片段seg的副本等級數，同 時對應了所有小數據塊ub的副本等級，然后對文件的所有小數據塊ub根據其等級 在CDN網絡中進行放置，

在放置時，假設ub的副本等級為L，首先計算小數據塊ub的ID號，根據分布 式哈希表DHT路由算法找到當前ub的主節點；然后將小數據塊ub以及對應副本等 級相關信息下載到主節點；再通過主節點的路由表找到與主節點的ID匹配L位的所 有節點，將ub復制到這些節點上；

5)為每個數據片段seg生成其一級索引項，其信息包括：每個小數據塊ub的大 小、數據片段seg中小數據塊ub的起始和結尾序號、數據片段seg中所有小數據塊 ub的ID列表以及更新時間，并根據數據片段seg的副本等級將一級索引項分布在 CDN網絡中；

6)通過整個文件的流行度信息，計算整個文件若不進行切分時對應的副本等級 l_all；

7)對每個文件生成二級索引項列表，包括：數據片段seg的ID列表、數據片 段seg的開始和結尾ub序號以及每個小數據塊ub大小，以文件名的哈希值作為鍵值， 并通過整個文件的副本等級l_all對二級索引項進行放置，放置方法與所述步驟4)中 的方法相同；

8)文件放置完成后，以根據實際應用而選擇的時間T為周期觀測用戶對文件不 同小數據塊ub上訪問頻度的變化，重新計算數據片段seg邏輯分塊中的小數據塊ub 數目和首尾序號、訪問流行度以及副本等級，并根據新的副本等級調整小數據塊ub 的副本數目，同時更新文件的一級和二級索引項。