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

有效

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

技術領域

本發明涉及信息技術領域，特別涉及到由分布式節點組成的內容分發網絡技術 領域中的一種基于訪問頻度變長邏輯分段的數據分發方法。

背景技術

CDN的全稱是Content?Distribution/Delivery?Network，即內容分發網絡。其目的 是通過在現有的Internet中增加一層新的網絡架構，即提供透明服務的中間層，將網 站的內容發布到最接近用戶的網絡邊緣，從而使得用戶能以最快的速度，從最接近 用戶的地方獲得所需的信息，一方面，CDN可以減少延遲，解決Internet網絡擁擠 的狀況；另一方面，還可以有效實現多種寬帶應用，提高響應速度和服務質量，特 別是在流媒體傳輸方面有著其它技術無可比擬的優勢。

在CDN系統中，為了使用戶快速取得數據，一個文件常常被生成多個副本，散 落的放置于網絡中，如何對這些副本進行合理地生成和維護，則是CDN系統的重要 問題。P2P技術由于其自組織、負載均衡等優勢，受到了廣泛的關注，也越來越多的 被應用在CDN的研究中。

結構化P2P網絡又稱為分布式哈希表(簡稱DHT)，每個節點都通過某種哈希 算法得到一個唯一ID值，所有應用實體(如對象，object)，也通過該哈希算法得到 一個與節點ID在同一個數值空間的object?ID值，同樣也有一個唯一的放置節點，該 放置節點就叫做該object的主節點，稱作home?node。對object的查找即對其home node的定位，該過程是通過查詢發起節點的鄰居作為中介而逐跳進行的，直至找到 目標或查找失敗為止。在DHT網絡中，假設哈希值的ID空間為M個bit位的數值， 從左到右，所有匹配大于等于1位數值的ID，稱為在一個等級，即一個level。一個 object如果其level為1，表示平均路由1跳就可以找到該object，因此，需要在1跳 覆蓋之外的所有節點上對該數據進行備份。以Pastry為路由協議為例，object的level 為1則對應了一個楔形的節點區域，表示該區域的所有節點需要對object進行備份， 若網絡中節點總數為N，基數為b，則需要N/b¹個節點進行備份。因此，如何計算每 個object所對應的level值，則是副本放置的關鍵。

文件的流行度是指一個文件受用戶的歡迎程度，以用戶對該文件的訪問頻率來 表示，比如被用戶點播、下載的次數等。在CDN系統中，常常根據每個文件流行度 的不同來計算文件的副本等級數，生成對應副本并放置于網絡中。實際中，大多數 的CDN主要對流媒體等大文件進行分發和存儲，而通過視頻點播等系統的研究發現， 盡管一個文件被點播了多次，但用戶在整個文件時間域上的訪問行為并不是平均分 布的。以電影為例，用戶對文件的開頭和結尾更感興趣，而常常跳過對中間內容的 觀看。同時，長度短的影片和長的影片也具有不同的訪問規律。文件的時域訪問特 征可以通過長時間積累的歷史訪問數據進行擬合得到，許多數值分析的相關方法可 以應用，這里不再贅述。因此，根據流行度信息對大文件整體進行副本生成，并不 符合用戶的實際需求，同時，會導致大量存儲空間被不常被訪問的數據占用。

綜上所述，可知一個文件在時間域上的用戶行為特征，對正確放置數據副本有 著重要意義。

發明內容

為了解決上述問題，本發明的目的在于提供一種基于訪問頻度變長邏輯分段的 數據分發方法。該方法將文件切分成細粒度的單元，基于用戶在文件不同時間段上 訪問頻度的差異，為文件生成變長邏輯分段，針對不同邏輯分段分別進行基于流行 度(即頻度)的多副本放置，使數據在CDN網絡中的副本分布更加符合用戶的實際 訪問習慣。同時，細粒度的文件切片，使得用戶訪問行為的統計更加精準，便于對 用戶訪問頻度特征基于時間變化的更新，并應用于內容分發的副本生成上，使系統 中的數據分布自適應的隨時間進行調整。另外，多級索引的應用，有效降低了數據 副本等級調整時所帶來的通信開銷，提高了系統性能。

為達到上述目的，本發明提供一種基于訪問頻度變長邏輯分段的數據分發方法， 對于分發到網絡中的文件f，分發過程如下：

1)將文件切分為大小相等的小數據塊(Unit?Block，簡稱ub)序列 {ub₁，ub₂，...，ub_n}。