基于通告轉(zhuǎn)移機(jī)制的CCN網(wǎng)絡(luò)緩存替換策略

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

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

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

0 引 言

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

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

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

1 相關(guān)工作

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

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

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

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

2.1 活動路徑建立

CCN網(wǎng)絡(luò)在以內(nèi)容為基礎(chǔ)建立通信鏈路的過程中，我們稱對該內(nèi)容請求建立的通信鏈路為活動路徑，其具有網(wǎng)絡(luò)拓?fù)涞娜W(wǎng)性、用戶的泛在性以及興趣請求的多樣性，該活動路徑具有如下特點：(1) 匹配內(nèi)容，指活動路徑的建立依賴于請求內(nèi)容所存在；(2) 唯一性，指雖然針對同一內(nèi)容建立的活動路徑可能有多條，但基于請求用戶到緩存節(jié)點或內(nèi)容源服務(wù)器之間建立的活動路徑有且僅有一條；(3) 全網(wǎng)特性，指活動路徑的建立是基于整個網(wǎng)絡(luò)的?；顒勇窂侥Ｐ腿鐖D1所示。

圖1 活動路徑模型

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

2.2 基于活動路徑的通告轉(zhuǎn)移

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

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

(1)

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

2.2.2緩存代價

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

(2)

(3)

式中：β>>1。

2.2.3內(nèi)容存儲價值

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

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

(4)

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

2.2.4通告機(jī)制

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

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

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

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

(5)

CSVi,h=CSV(i)-CSVmin

(6)

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

表1 替換內(nèi)容通告范圍

2.3 算法描述

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

算法1興趣包處理算法

Input:興趣請求包

if(CS中命中緩存)

Ni_hit++，Ni_hit

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

更新內(nèi)容的請求時間

準(zhǔn)備沿逆路徑轉(zhuǎn)發(fā)

else

if (PIT中存在條目)

丟棄興趣包同時更新PIT表

else

PIT中添加興趣包條目

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

end

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

Input:命中緩存內(nèi)容

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

及時更新內(nèi)容存儲價值CSV值

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

if(CS空間充足)

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

else

查找并替換CSV值最小的內(nèi)容

刪除相應(yīng)的FIB條目

end

算法3替換算法

Input:替換內(nèi)容

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

沿著建立的活動路徑通告

if(CSVi,h≤CSVper)

直接刪除，

else if((m-1)CSVper

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

else if(nCSVper≤CSVi,h)

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

刪除原內(nèi)容對應(yīng)路徑中的FIB條目

end

3 仿真實驗

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

表2 參數(shù)設(shè)置

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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