[發明專利]一種面向內容中心網絡中基于預測的最優化緩存放置方法

有效

• 申請號: 201410382200.8
• 申請日: 2014-08-06
• 公開（公告）號: CN104166630B
• 公開（公告）日: 2017-06-20
• 發明（設計）人: 張國印;邢志靜;武俊鵬;董玉增;劉青;唐濱;李曉光
• 申請（專利權）人: 哈爾濱工程大學
• 主分類號: G06F12/0813
• 分類號: G06F12/0813
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于網絡技術領域，具體涉及一種可用于內容中心網絡中數據緩存的面向內容中心網絡中基于預測的最優化緩存放置方法。

背景技術

隨著Internet的迅速發展，互聯網在很多方面暴露出問題，如可擴展性方面的問題、動態性方面的問題以及網絡安全性問題等等。針對當前互聯網出現的一系列問題，國內外研究者已經提出很多的解決方案，包括P2P和CDN等。2009年，施樂公司帕洛阿托研究中心的Van Jacobson提出內容中心網絡(Content Centric Network，簡稱CCN)。

CCN中每個節點都設有緩存空間，采用“經過即緩存”策略來緩存數據。CCN節點自身具備的緩存特性雖然有一定的優勢，但是這種對內容不加區分地緩存特性容易產生無效緩存，帶來不必要開銷，造成有限的緩存空間內大量內容冗余，大大降低緩存空間的利用率，從而降低網絡的緩存性能。

本發明將緩存放置問題轉化為一個最優化問題，對影響緩存性能的幾個因素包括對象被訪問頻率、距離、對象大小等進行綜合考慮，構建了一種最大化收益緩存放置模型，稱為Max-Benefit模型。同時，為了使模型中對象被訪問頻率能夠更好地反映對象的熱度情況，本發明在Max-Benefit模型中引入了預測機制，用對象被訪問頻率的預測值代替實際值，更準確地表示對象被訪問的頻率趨勢，提出基于預測的最大化收益的緩存放置模型(Prediction based Max-Benefit，簡稱PB-Max-Benefit)。

此外，相比于其他求解最優化模型的算法，如最小斯坦納樹算法、貪婪算法、動態規劃法等，本發明中使用的遺傳算法運算過程簡單而且并行搜索問題的解。

發明內容

本發明的目的在于提供一種解決內容中心網絡中因對內容不加區分進行緩存而產生無效緩存，帶來不必要開銷，造成有限的緩存空間內大量數據冗余，大大降低緩存空間的利用率的一種面向內容中心網絡中基于預測的最優化緩存放置方法。

本發明的目的是這樣實現的：

(1)將緩存放置方案編碼為二進制符號串，1代表緩存對象，0代表不緩存對象，隨機產生初始種群；

(2)計算每種緩存放置方案的收益值，找出最大收益值存入數組max；

(3)基于個體適應度劃分的選擇運算；

(4)基于個體相關性的交叉運算；

(5)基于基因塊的變異運算；

(6)產生新的種群，即新的緩存放置方案；

(7)判斷數組max是否趨于穩定，如果穩定，得到最大收益緩存放置；否則重新執行步驟(2)。

步驟(1)中，對于每一種緩存放置方案都對應一種0、1編碼串。

步驟(2)包括：

計算最大化緩存收益Max-Benefit步驟，其中，為新對象o_i到達節點v_i，緩存新對象o_i給節點v_i帶來的收益：

其中，x_i∈{0，1}，

X＝{x₁，x₂，...x_n}，x₁，x₂，...，x_n對應的是節點v₁，v₂，...，v_n的值，對于對象o，x_i＝0表示節點v_i上不對o進行緩存，x_i＝1表示節點v_i上緩存對象o；

對象o，將o緩存在節點v_i上，所有經過v_i對o的請求可以直接從節點v_i得到對象o，由節點v_i緩存對象o而節省的訪問開銷稱為緩存對象o獲得的緩存收益，每個相關節點v_j獲得的收益為：

其中，表示任意相關節點v_j上觀察到的對對象o的訪問頻率，表示節點v_i上緩存對象o時，以v_i為新的最近源節點的節點v_j請求o節省的跳數，size(o)表示對象o的大小，w表示傳輸單位大小對象的開銷；