基于通告轉移機制的CCN網絡緩存替換策略

王 波 胡軍臺 肖承仟 呂 杰 孫世勇 杜春鋒

1(國網河南省電力公司平頂山供電公司 河南 平頂山 467000)

2(鄭州輕工業大學計算機與通信工程學院 河南 鄭州 450002)

0 引 言

據Cisco VNI Mobile Forecast預測[1]，2021年網絡用戶對于音視頻類信息的獲取流量將會達到全網IP流量的80%以上。用戶需求的不斷變化使得傳統以IP為主的網絡體系架構在諸多方面捉襟見肘，如移動性支持、多徑路由以及網絡性能優化等。因此以信息為核心新一代網絡體系架構應運而生[2-4]，其中CNN以其特有的優勢脫穎而出，被學術界認為是解決傳統網絡缺陷的最佳方案[5]。

網絡內部緩存作為CCN網絡基礎和核心，其目的是使得每個路由節點都具備內容緩存功能，以廉價的存儲代價來換取網絡服務性能的提升[6]，因此緩存性能的優劣將直接影響到網絡整體的性能以及用戶的體驗。CCN網絡節點緩存優化技術是提升網絡性能的關鍵[7]，目前CCN網絡現有的緩存策略在諸多方面存在不足。緩存替換作為緩存策略主要的組成部分，正在受到越來越多學術界人士的關注。為優化網絡緩存算法以及提升整體網絡性能，學術界提出了一些緩存替換算法，如LRU、LFU和FIFO等。在現有的網絡緩存策略下，利用這些緩存替換算法并不能達到預期效果，且大部分現有的替換算法是基于單方面因素考慮，并未實現多節點協作化緩存。同時，它們對替換內容的直接刪除使得節點緩存內容并不能得到有效利用，造成網絡資源的浪費。

本文綜合考慮節點內容的時間、動態流行度以及緩存代價等三方面提出一種基于NTM的緩存替換策略。該策略周期性評測節點中CSV值越大，表明該內容越具有存儲價值，應該在節點中緩存，執行緩存替換時不應該被替換掉，反之，最小的CSV值在緩存替換時應首先考慮被替換掉。同時，考慮到同請求條件下，被替換掉的內容可能在網絡中其他節點處仍然具有較好的存儲價值，故給出一種基于該活動路徑的通告轉移機制，依據節點請求，路由轉發路徑建立一條基于內容的活動路徑，將替換掉的內容沿活動路徑遍歷查找適合緩存的節點，以便再次響應用戶請求。

1 相關工作

網絡內部緩存是CCN網絡區別于傳統網絡的特有優勢。緩存替換是緩存策略的關鍵部分，同時也是學術研究者關注的重點，目前已有的緩存替換策略主要有LRU、LFU以及SIZE 等。LRU的核心思想是發生緩存替換時替換掉最久沒有被訪問的緩存內容，缺點是適應性較差，當緩存節點中內容流行度分布發生變化時，緩存性能下降[8]。LFU的核心思想是如果緩存的內容在過去訪問量很大，那么在以后的訪問頻率也很高，根據緩存內容的歷史訪問頻率來淘汰內容，缺點是自身適應性差，未能充分考慮到內容請求的時變性。原因是LFU僅僅只局限于一段時間內訪問頻率，但是局部時間內訪問頻率最高的內容并不就是一直被命中的內容，即使后期訪問頻率大幅下降，它也會一直留在節點的緩存空間直到更受歡迎的新內容出現。SIZE替換策略[9]的核心思想是依據新的緩存內容進入節點緩存空間時內容塊的大小，優先把大的內容塊淘汰出去，但這種算法沒有設置訪問時間斷點、內容流行度、緩存命中率等因素，可能會使流行度不高的小的對象一直未能被訪問，在節點緩存空間一直占據空間資源，從而降低命中率。

現有緩存替換算法所具有的單一性已經滿足不了多樣化的網絡數據需求。文獻[10]將LRU的最近訪問時間與LFU的請求頻率相結合，提出了一種新的LFRU算法。文獻[11]提出了一種基于內容流行度的動態替換策略，在兼顧用戶的請求頻率和網絡的傳輸開銷的基礎上將緩存價值最小的內容替換掉。以上的緩存替換算法主要是在單節點有限空間的緩存替換，多節點間緩存命中率低。文獻[12]提出了基于Age的多節點合作緩存機制，但是策略僅對內容小的Age敏感，并沒有考慮內容流行度變化。文獻[13]提出一種LUV-Path的策略，該策略依據緩存內容節點距內容源服務器之間的距離作為衡量內容價值的標準，未能充分考慮內容流行度等因素。文獻[14]提出WGDSF緩存替換策略，該策略在一定程度上對GDS算法進行了優化，缺點是增加了算法的復雜度。

對于CCN網絡的緩存替換策略的研究，多為單方面的研究，均未能充分考慮多方面因素，如：考慮到了內容時間，但卻未能考慮到內容流行度；考慮到了內容流行度但卻未能考慮緩存代價因素等。以上替換策略雖然在一定程度上對緩存優化以及網絡性能有所提升，但卻未能達到最佳效果。

2 基于通告轉移的CCN網絡緩存替換策略

2.1 活動路徑建立

CCN網絡在以內容為基礎建立通信鏈路的過程中，我們稱對該內容請求建立的通信鏈路為活動路徑，其具有網絡拓撲的全網性、用戶的泛在性以及興趣請求的多樣性，該活動路徑具有如下特點：(1) 匹配內容，指活動路徑的建立依賴于請求內容所存在；(2) 唯一性，指雖然針對同一內容建立的活動路徑可能有多條，但基于請求用戶到緩存節點或內容源服務器之間建立的活動路徑有且僅有一條；(3) 全網特性，指活動路徑的建立是基于整個網絡的。活動路徑模型如圖1所示。

圖1 活動路徑模型

可以看出，A-C-G-I-K、A-D-H-I-K以及E-F-I-K等都是網絡中的活動路徑，雖然最終請求到達相同的緩存節點，但它們是不同的路徑，且都是唯一的。

2.2 基于活動路徑的通告轉移

2.2.1動態內容流行度

CCN網絡中內容對于用戶需求狀況的一個重要指標即是內容流行度。相對于內容源中的穩態型緩存內容，網絡節點中的緩存內容屬于動態型，具有時變特性。若緩存中的部分內容在當前周期內被多用戶請求，內容流行度很高，但是過了該時期，內容幾乎不被用戶訪問，訪問量極少，內容流行度將會急速下降。因此若要得到準確的內容流行度的變化，避免因不同時間段流行度不同而造成當前時段內容流行度的誤判，需要我們結合不同時間段的流行度比重來準確預測。本文為每個節點加一個用戶請求包計數器來記錄節點收到興趣請求數量，同時為節點中數據包加一個計數器來記錄數據內容被命中次數。依據前后時間周期來計算當前時間周期中的動態內容流行度，公式如下：

(1)

式中：DCPi(T-1)代表上一時間周期中的節點中該內容的流行度；ε為衰減因子，取值范圍為0<ε<1；Ni(T)代表節點緩存內容周期內命中率；Ni_hit表示節點內容i在統計周期內命中次數；Nall表示該緩存節點在統計時間段內收到的請求次數的總和。

2.2.2緩存代價

CCN網絡中用戶請求到內容緩存在節點的過程中消耗的網絡資源，稱為緩存代價。我們將緩存代價分為傳輸代價和存儲代價。傳輸代價指節點中緩存內容從源服務器到達緩存節點所消耗的資源，有傳輸經過跳數和每跳代價決定，假設每跳的傳輸代價固定不變，跳數越大，傳輸代價越高。存儲代價指將到達節點的內容存儲到緩存空間中所需代價。緩存代價公式如下：

(2)

(3)

式中：β>>1。

2.2.3內容存儲價值

在此，我們將CSV設定為域內網絡中節點內容的存儲屬性，CSV值的高低也直接影響著內容對整個網絡用戶的作用大小以及是否適合緩存在網內節點中。為避免由于節點中緩存內容歷史請求命中率大但近段時間未被訪問而造成的緩存污染問題，本文依據LRU算法思想，引入內容緩存時間差[15]。其原理是在節點緩存內容中添加一個記錄最新時刻的字段，用t表示當前內容被請求時間，t0表示前一時刻內容被請求時間，則節點中該內容兩次被訪問的時間差為：Tinter=t-t0。

綜合考慮時間、內容流行度以及緩存代價等三方面因素，同時結合GDSF算法思想，本文給出了內容存儲價值函數，公式如下：

(4)

由式(4)可以看出，時間間隔越短，則內容在短時間內被請求次數越多，內容流行度越大，此時CSV(i)值也越大。時間間隔越大，則內容流行度值越小，此時應著重考慮內容緩存代價，節點緩存內容距源服務器距離越遠，即Hopi值越大，則緩存代價越高，因此CSV(i)值也越大。綜上，該內容存儲價值的值可以很好地表征內容的存儲屬性，在節點空間不足需發生緩存替換時，可以依據該CSV值進行替換內容的選擇，優先替換掉內容存儲價值較低的緩存內容。

2.2.4通告機制

當通過以上方法得到CSV后，如果在域內網絡節點空間不足需要發生緩存替換時缺少了相應的通告機制將被替換掉的內容在限定范圍內進行通告，那么基于轉移通告機制的CCN緩存替換策略將無異于普通的緩存替換策略。即發生緩存替換時直接將替換掉的內容進行刪除，而不能將該內容通過轉移到其他的節點進行緩存，當網絡用戶再次請求該內容時，依然會耗費網絡資源再次從其他節點或者源服務器中獲取。因此我們設計一種針對由于緩存空間不足而被替換掉內容的通告轉移機制，替換掉的內容可以沿著依賴內容而存在的活動路徑進行轉移，遍歷查找適合存儲的其他節點，以便其他節點或同一節點再次請求。遍歷完活動路徑，如果有適合緩存的節點，則對其進行緩存，反之直接刪除。

依賴用戶請求-響應而建立的活動路徑，中間節點本身不存在該內容緩存，隨著不同用戶請求建立的活動路徑交叉不同，使得中間節點也會存在針對該內容的緩存。由以上分析可知，活動路徑節點中依據CSV值大小，在緩存替換時，首先替換掉其值較小的緩存內容，替換內容沿著活動路徑從緩存節點向網絡中發出通告，尋找適合存儲的其他節點，若找不到則將該內容刪除。在這里涉及兩個方面：(1) 選擇合適的存儲節點，利用替換內容的CSV值沿活動路徑匹配查找，滿足條件則進行存儲，反之遍歷結束，直接刪除；(2) 通告范圍限制，通告范圍的大小影響著效率的快慢以及內容的可再用性，同時應當受到網絡限制，此部分將在下面詳細闡述。

內容通告范圍限定需要根據不同網絡、不同環境進行，若無節制地向全網進行通告，會占用大量的網絡資源，增大網絡開銷，同時替換掉或最終刪除掉內容后依然需要刪除原有的路徑中FIB條目，否則會占用一部分網絡帶寬。在此，我們以活動路徑上路由跳數n來定義通告的范圍，需要滿足以下條件[16]：(1) 通告范圍不能超出域內網絡；(2) 最大程度的減少網絡資源消耗；(3)n的選擇小于請求者到緩存節點之間的跳數。

跳數的設定需要考慮活動路徑的大小以及節點中CSV值范圍的大小，公式如下：

(5)

CSVi,h=CSV(i)-CSVmin

(6)

式中：CSVmax、CSVmin分別表示緩存節點中的內容存儲價值的最大值和最小值；CSV(i)表示節點中被替換內容的內容緩存價值。表1所示為替換內容通告范圍。

表1 替換內容通告范圍

2.3 算法描述

為實現NTM的CCN網絡緩存替換策略，算法1給出請求過程、數據包處理以及替換算法的描述。

算法1興趣包處理算法

Input:興趣請求包

if(CS中命中緩存)

Ni_hit++，Ni_hit

內部審計要依賴于完善的內部控制，沒有完善的內部控制做支撐，內部審計工作將成為無源之水、無本之木。內部控制的完善，首先就是要測試村鎮銀行的內部控制，村鎮銀行的內部控制越健全、越有效，內部審計在符合性測試后，需要的實質性測試程序就越少；反之，內部控制不健全或者失效，就要通過大量的實質性測試程序來保障審計結論的可靠性。村鎮銀行由于機構小，人員少，管理層的重視程度有重大差異。不重視或管理不善的村鎮銀行內部控制機制不健全，或者雖然設計了內部控制制度，但內部控制實施無效。這種情況下，內部審計工作就要付出高成本。

更新內容的請求時間

準備沿逆路徑轉發

else

if (PIT中存在條目)

丟棄興趣包同時更新PIT表

else

PIT中添加興趣包條目

查找FIB轉發興趣分組

end

算法2數據包處理算法

Input:命中緩存內容

讀取興趣包的跳數減1后賦值給數據包

及時更新內容存儲價值CSV值

沿著逆路徑返回數據包，且查找適合緩存的節點

if(CS空間充足)

存儲內容數據，初始化內容命中數和請求數，更新Hopi值

else

查找并替換CSV值最小的內容

刪除相應的FIB條目

end

算法3替換算法

Input:替換內容

依據CSV值計算并查找通告范圍

沿著建立的活動路徑通告

if(CSVi,h≤CSVper)

直接刪除，

else if((m-1)CSVper

遍歷活動路徑m跳，找到合適節點則存儲，否則直接刪除

else if(nCSVper≤CSVi,h)

遍歷活動路徑n跳，找到合適節點則存儲，否則直接刪除

刪除原內容對應路徑中的FIB條目

end

3 仿真實驗

為驗證本文所提CCN網絡替換策略對網絡性能的優化，本文采用如下設置進行仿真實驗。實驗采用BRITE Topolgy Builider[17]隨機生成含有50個節點的網絡，其中用戶節點15個，內容源服務器節點5個。假設默認網絡中包含7 000個文件，文件數變化為2 000～12 000，且單個文件大小一致。每個節點緩存空間大小相同，用戶請求頻率符合泊松分布，且λ=100次/s，內容數據的流行度服從Zipf分布[18]，傳輸速率1 Mbit/s，實驗仿真150 s，統計周期時間更新為5 s。參數設置如表2所示。

表2 參數設置

為方便統計和分析，我們以FIFO、LRU和LFU三種緩存替換策略與本文提出的NTM進行對比分析。

緩存容量對平均緩存命中率和平均路由跳數比的影響如圖2、圖3所示。

圖2 緩存容量對平均緩存命中率影響

圖3 緩存容量對平均路由跳數比的影響

由圖2可知，隨著域內網絡節點緩存容量的提高，幾種替換算法的平均緩存命中率都有不同程度的提升，其中NTM替換策略提高較為明顯。這是因為仿真實驗中采用的替換策略，首先利用綜合因子緩存存儲價值來對CSV較小的值替換，同時利用通告轉移機制將其存儲在其他節點。這種機制優化了系統緩存，同時也提高節點的緩存命中率。由圖3可知，隨著緩存容量的提高幾種替換策略平均路由跳數比都有下降。但NTM相對下降最為明顯，因為NTM替換策略考慮到了緩存代價，距離源服務器較遠的節點緩存內容不易被替換。同時也考慮到了內容流行度，隨著時間的積累，也可提高緩存多樣性。

Zipf參數α變化對平均緩存命中率和平均路由跳數比的影響如圖4、圖5所示。

圖4 Zipf參數α變化對平均緩存命中率影響

圖5 Zipf參數α變化對平均路由跳數比影響

由圖4可知，起始參數α值較小，內容流行度高低并不明顯，大多數的內容只能從源服務器中獲取，因此幾種緩存替換策略的平均緩存命中率很低。隨著α值的增大，內容請求越來越集中，節點中緩存的內容也更加具有存儲價值，因此網絡中節點的緩存命中率也相應增加，其中NTM替換策略的緩存命中率提高較為顯著。由圖5可知，隨著α值越來越大，平均路由跳數比值也在下降。NTM替換策略充分利用內容流行度因子，隨著α的增加，內容流行度增大，網絡中緩存內容呈現局部性特點，多條緩存路徑中將會緩存大量的高內容流行度的內容，進而降低用戶的平均請求跳數。相比于其他幾種替換策略，隨著參數α的增大，本文提出的NTM緩存策略對用戶獲得請求內容的平均請求跳數比降低最為明顯。

4 結 語

本文提出一種基于通告轉移的CCN網絡緩存替換策略，建立請求者到緩存節點的活動路徑。節點緩存空間不足時，將替換掉的內容沿著活動路徑進行遍歷尋找適合的存儲節點，便于其他或者同一請求者再次請求內容。仿真實驗表明，本文提出的NTM緩存替換策略在提高網絡緩存平均命中率和降低用戶獲取內容平均跳數方面具有很好的優勢。本文的研究重點在于替換策略后期，通過對有價值的內容充分利用，提高緩存命中率和減少請求跳數。下一步工作將結合節點和內容的各種影響因子，降低網絡請求時延，進一步優化緩存性能。