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

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

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

0 引 言

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

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

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

1 相關工作

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

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

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

2 基于通告轉移的CCN網(wǎng)絡緩存替換策略

2.1 活動路徑建立

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

圖1 活動路徑模型

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

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

2.2.1動態(tài)內容流行度

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

(1)

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

2.2.2緩存代價

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

(2)

(3)

式中：β>>1。

2.2.3內容存儲價值

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

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

(4)

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

2.2.4通告機制

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

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

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

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

(5)

CSVi,h=CSV(i)-CSVmin

(6)

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

表1 替換內容通告范圍

2.3 算法描述

為實現(xiàn)NTM的CCN網(wǎng)絡緩存替換策略，算法1給出請求過程、數(shù)據(jù)包處理以及替換算法的描述。

算法1興趣包處理算法

Input:興趣請求包

if(CS中命中緩存)

Ni_hit++，Ni_hit

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

更新內容的請求時間

準備沿逆路徑轉發(fā)

else

if (PIT中存在條目)

丟棄興趣包同時更新PIT表

else

PIT中添加興趣包條目

查找FIB轉發(fā)興趣分組

end

算法2數(shù)據(jù)包處理算法

Input:命中緩存內容

讀取興趣包的跳數(shù)減1后賦值給數(shù)據(jù)包

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

沿著逆路徑返回數(shù)據(jù)包，且查找適合緩存的節(jié)點

if(CS空間充足)

存儲內容數(shù)據(jù)，初始化內容命中數(shù)和請求數(shù)，更新Hopi值

else

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

刪除相應的FIB條目

end

算法3替換算法

Input:替換內容

依據(jù)CSV值計算并查找通告范圍

沿著建立的活動路徑通告

if(CSVi,h≤CSVper)

直接刪除，

else if((m-1)CSVper

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

else if(nCSVper≤CSVi,h)

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

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

end

3 仿真實驗

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

表2 參數(shù)設置

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

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

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

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

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

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

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

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

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

4 結 語

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