劉期烈，秦慶偉，夏遠(yuǎn)鵬，李 云

LIU Qilie,QIN Qingwei,XIAYuanpeng,LI Yun

重慶郵電大學(xué) 移動通信重點實驗室，重慶 400065

Chongqing Key Lab of Mobile Communications Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China

1 引言

數(shù)據(jù)命名網(wǎng)絡(luò)是信息中心網(wǎng)的一種典型架構(gòu)，與傳統(tǒng)的IP網(wǎng)絡(luò)架構(gòu)相比，最根本的區(qū)別是不再依賴IP地址，將傳統(tǒng)的以主機為中心的模型轉(zhuǎn)變?yōu)橐詳?shù)據(jù)內(nèi)容為中心的模型[1]。所有的數(shù)據(jù)內(nèi)容被全網(wǎng)統(tǒng)一唯一命名，并且基于內(nèi)容進行定位尋址、轉(zhuǎn)發(fā)路由。路由器具備和數(shù)據(jù)服務(wù)器同樣的存儲轉(zhuǎn)發(fā)功能，用戶除了在原始服務(wù)器請求內(nèi)容外，可以在網(wǎng)內(nèi)路由器節(jié)點的緩存內(nèi)命中內(nèi)容，極大減輕了服務(wù)器端的負(fù)載壓力。

命名數(shù)據(jù)網(wǎng)絡(luò)緩存要解決的主要有三個問題：（1）數(shù)據(jù)返回客戶端，經(jīng)過路由器節(jié)點需要存哪個數(shù)據(jù)；（2）在返回路徑上需要緩存在哪個節(jié)點；（3）當(dāng)確定在某個節(jié)點要緩存返回的數(shù)據(jù)，而該節(jié)點緩存空間飽和時，需要替換掉節(jié)點內(nèi)哪個數(shù)據(jù)[2-4]。由于內(nèi)容中心網(wǎng)對內(nèi)容的請求處理速度必須是線性處理速度，所以在節(jié)點替換內(nèi)容時，任何復(fù)雜度高于O(1)的策略都不能滿足網(wǎng)絡(luò)性能的要求[5]。鑒于此，很多研究工作集中在上文提到的（1）（2）問題上，對于問題（3），目前緩存替換策略仍然采用最近最少使用算法LRU（Least Recently Used）和最近最少頻率算法LFU（Least Frequently Used），也有研究工作采用更為簡單的先進先出FIFO（First In First Out），隨機選擇替換算法RND。

LRU策略是把最近最少使用的內(nèi)容替換掉，LFU策略是把緩存中使用頻率最少的內(nèi)容替換掉，F(xiàn)IFO策略是把緩存中最先存進的內(nèi)容替換掉，以上三種策略都存在只考慮了單一的影響因素[6-8]。由文獻[8]可知LRU策略與FIFO策略不能真實反映內(nèi)容的流行度。LFU按照每個緩存數(shù)據(jù)塊被訪問的頻率的高低進行排序，由于其靜態(tài)特性，即如果某數(shù)據(jù)塊在過去一段時間內(nèi)被大量請求，使該數(shù)據(jù)具有較大的請求頻率，在最近時間該數(shù)據(jù)塊的請求頻率急劇下降，但由于前面的高頻率請求使該數(shù)據(jù)獲得了較大的權(quán)重，因此該數(shù)據(jù)即使當(dāng)前請求頻率很低也不能及時地將其替換，從而長期占用內(nèi)存空間，使當(dāng)前具有高流行度或高請求代價的數(shù)據(jù)不能被緩存。LRU策略維護一個緩存項隊列，隊列中的數(shù)據(jù)塊按照每項的最后被訪問時間排序。當(dāng)緩存空間已滿時，將刪除最后一次被訪問時間距離現(xiàn)在最久的項，在有些情況下可能會出現(xiàn)LRU將一個用戶訪問次數(shù)多的數(shù)據(jù)塊從緩存空間中替換出來，而插入一個用戶訪問次數(shù)低的數(shù)據(jù)塊，引起緩存污染的問題。Wang等基于GreedyDual-Size策略[9]提出一種改進型的Hetero[10]策略，該策略將節(jié)點獲取數(shù)據(jù)塊需要經(jīng)過的跳數(shù)作為花費代價，每次替換時將代價最小的數(shù)據(jù)替換。Chen等[11]根據(jù)NDN的特點，提出LUV-Path策略，該策略將數(shù)據(jù)的權(quán)重設(shè)為本節(jié)點與服務(wù)器源端之間的距離，距離服務(wù)器較遠(yuǎn)的數(shù)據(jù)塊具有相對較大的權(quán)重值，權(quán)重值較小的數(shù)據(jù)更易被節(jié)點剔除。以上策略雖然考慮了數(shù)據(jù)請求的代價，能夠在一定程度上降低用戶請求數(shù)據(jù)時的代價，但這些策略都沒有考慮數(shù)據(jù)的流行度，這些策略不能夠準(zhǔn)確反映數(shù)據(jù)當(dāng)前的流行度情況。

路由器的緩存空間和服務(wù)器相比，空間極小，網(wǎng)絡(luò)內(nèi)節(jié)點隨著客戶端請求次數(shù)的增加和時間推移，節(jié)點緩存空間很快就會出現(xiàn)飽和狀態(tài)，從上游節(jié)點或服務(wù)器返回的數(shù)據(jù)，若要緩存在該節(jié)點將會面臨替換掉誰的問題。如何提高網(wǎng)內(nèi)節(jié)點的緩存空間利用率，減小數(shù)據(jù)的冗余度，將變得非常重要。

基于以上問題，本文提出了一種根據(jù)數(shù)據(jù)請求頻率與最近請求時間間隔來確定數(shù)據(jù)塊流行度的Po-Rep（Popularity-Replacement）緩存替換策略。該策略每次根據(jù)數(shù)據(jù)的最近請求時間差來判斷數(shù)據(jù)的新鮮度，根據(jù)請求頻率來判斷內(nèi)容在本地的熱度，通過以上參量計算出節(jié)點存儲空間CS（Cache Stored）中所有數(shù)據(jù)塊的流行度，數(shù)據(jù)的新鮮度越高同時熱度越高表明流行度越高。Po-Rep策略根據(jù)數(shù)據(jù)此時的流行度情況，有新數(shù)據(jù)到達并進行存儲時，替換掉流行度最低的數(shù)據(jù)，使數(shù)據(jù)的存儲更合理。仿真結(jié)果表明，該替換策略能夠有效提高興趣包在網(wǎng)內(nèi)節(jié)點的命中率并減小用戶請求數(shù)據(jù)的時延與路由跳數(shù)。

2 基于流行度預(yù)測的替換策略Po-Rep

2.1 Po-Rep策略基本思想

在NDN網(wǎng)絡(luò)中，每個節(jié)點都具有緩存空間CS，其功能除了進行路由之外，與服務(wù)器一樣可以滿足客戶端Interest包的請求，但是節(jié)點的CS空間有限，隨著請求次數(shù)的積累，CS很快被存滿，面臨的最大的問題就是后續(xù)的內(nèi)容根據(jù)緩存策略需要存儲在該節(jié)點時，必須進行替換，選擇替換掉CS中相應(yīng)數(shù)據(jù)后，現(xiàn)有的數(shù)據(jù)仍然能夠滿足后續(xù)的用戶請求。只有流行度高的內(nèi)容才能滿足更多用戶的請求，降低服務(wù)器端的負(fù)載壓力，增加用戶在網(wǎng)內(nèi)節(jié)點的命中率，減少用戶的路由跳數(shù)?；趦?nèi)容流行度的替換策略Po-Rep，利用內(nèi)容在節(jié)點中被請求的次數(shù)和被請求的時間間隔，計算出流行度，對內(nèi)容要進行緩存替換時，替換掉價值最低的內(nèi)容。

由于在NDN中內(nèi)容的流行度僅僅依靠在服務(wù)器端被請求的次數(shù)已經(jīng)不能準(zhǔn)確測定內(nèi)容在整個網(wǎng)絡(luò)內(nèi)的流行度，如何實時準(zhǔn)確預(yù)測出數(shù)據(jù)塊在網(wǎng)絡(luò)內(nèi)的流行度，使每個節(jié)點中緩存的數(shù)據(jù)能夠最大限度地滿足用戶的后續(xù)請求，對于提升NDN的整體性能非常重要。流行度高的內(nèi)容說明在當(dāng)前時間段和未來一段時間都是被用戶大量請求的內(nèi)容，具有被繼續(xù)緩存在節(jié)點CS的潛在價值，而流行度低的內(nèi)容在當(dāng)前階段沒有滿足用戶的大量請求，占用了CS中存儲空間，導(dǎo)致用戶請求需要經(jīng)過更多的跳數(shù)路由到服務(wù)器，當(dāng)CS中流行度低的內(nèi)容被替換掉后，價值更高的數(shù)據(jù)被緩存在離用戶端更近的節(jié)點中，用戶的請求可以更多地在網(wǎng)內(nèi)節(jié)點命中，使網(wǎng)內(nèi)節(jié)點內(nèi)容始終保持價值最大化。

2.2 流行度計算

在整個網(wǎng)絡(luò)中，數(shù)據(jù)內(nèi)容流行度分布仍然符合Zipf分布，即二八分布，20%的內(nèi)容滿足整個網(wǎng)絡(luò)的80%請求量，剩下的80%內(nèi)容滿足用戶20%的請求量[12]。概率為：

其中，p(n)表示排序為n的內(nèi)容出現(xiàn)的頻率，排序按照內(nèi)容出現(xiàn)頻率的高低，從高到低的次序排列。

其中，r(i,s,N)表示在總數(shù)為N個內(nèi)容中排序為i的內(nèi)容被請求的概率，s是冪率系數(shù)，s越大，表示流行度高的內(nèi)容越集中[13]。

而每個路由器節(jié)點的內(nèi)容數(shù)量有限，單個節(jié)點內(nèi)數(shù)據(jù)流行度不再符合數(shù)量級較大的Zipf分布，需要找出更恰當(dāng)?shù)膮⒘縼碛嬎銛?shù)據(jù)在節(jié)點中的流行度，既保證在節(jié)點中的數(shù)據(jù)保持最大價值，又可以保證整個網(wǎng)絡(luò)的性能，提高用戶請求在網(wǎng)內(nèi)路由器節(jié)點的命中率。LRU策略把最近訪問時刻作為數(shù)據(jù)流行度的參考量，距離最近一次被訪問的時間越短，代表下一次被訪問的概率越高，但是對于周期性操作的數(shù)據(jù)，容易出現(xiàn)被替換后再次請求時，已經(jīng)被替換出去的現(xiàn)象；LFU策略把訪問頻率作為流行度參考量，被訪問的次數(shù)越多，代表越多用戶對該數(shù)據(jù)有需求，但是容易出現(xiàn)某個數(shù)據(jù)在某一段時間熱度較高，短時間被請求的次數(shù)很多，長時間未被請求卻仍然保持高頻率值，而其他最近流行度高的內(nèi)容被替換掉，使節(jié)點內(nèi)的數(shù)據(jù)整體價值降低。

請求包在節(jié)點命中，與請求包在服務(wù)器源端命中相比，降低了路由跳數(shù)，節(jié)省了帶寬，綜合考慮節(jié)點內(nèi)容被訪問的次數(shù)，最近訪問的時刻，準(zhǔn)確預(yù)測節(jié)點中內(nèi)容的流行度。用Ti表示節(jié)點中內(nèi)容i所處的當(dāng)前時刻，Ti_recent表示內(nèi)容i最近一次被訪問的時刻，Ti_first表示內(nèi)容i在節(jié)點CS中第一次被訪問的時刻。則此刻距離最近一次被訪問時間間隔為：

Tinterval-max表示所有數(shù)據(jù)中Ti_interval對應(yīng)的最大時間間隔，進行歸一化處理：

而數(shù)據(jù)i平均的訪問間隔可以表示為：

Mi表示在Ti_interval被請求的次數(shù)，Taverage-max表示所有數(shù)據(jù)中Ti_average對應(yīng)的最大值，進行歸一化處理：

內(nèi)容i的流行度P(i)可以表示為：

Ti_interval越小，說明數(shù)據(jù)距離最近一次被訪問的時間間隔越短，新鮮度較高，被訪問的概率越大；Ti_average越小，說明數(shù)據(jù)在很短時間內(nèi)被訪問的次數(shù)越多，表示該數(shù)據(jù)處于高熱度時期，被更多的用戶需求。P(i)越大，表示內(nèi)容i新鮮度越高的同時，熱度也較高，可以很好地滿足后續(xù)用戶的請求。

替換策略的步驟如圖1中流程圖所示。

步驟1數(shù)據(jù)到達節(jié)點，且根據(jù)緩存策略確定要緩存在該節(jié)點，檢測節(jié)點的CS是否已滿，若滿則轉(zhuǎn)步驟3。

步驟2直接緩存返回的數(shù)據(jù)。

圖1 流程圖

步驟3節(jié)點根據(jù)每個數(shù)據(jù)的Ti、Ti_recent、Ti_first、Mi計算出CS中每個數(shù)據(jù)的P(i)，進行比較得出P(i)最低的對應(yīng)數(shù)據(jù)，進行刪除。

步驟5數(shù)據(jù)存進節(jié)點后，對其Ti、Ti_recent、Ti_first、Mi分別進行初始化。

3 仿真

為驗證本文提出的Po-Rep緩存替換策略對于NDN網(wǎng)絡(luò)性能的提升，通過ndnSIM[14]仿真平臺實現(xiàn)了對LRU、LFU、Po-Rep三種替換策略的仿真，并對其各自的性能進行了對比和分析，仿真結(jié)果驗證了Po-Rep替換策略的有效性。

3.1 仿真環(huán)境和參數(shù)配置

本實驗硬件環(huán)境為Intel?Core?i3-4170CPU@3.70 GHz，8GB內(nèi)存。操作系統(tǒng)是Ubuntu 12.04。仿真環(huán)境ndnSIM是基于NS-3的仿真模塊，該模塊可以實現(xiàn)NDN的基本功能的仿真模擬，并且可以修改代碼更換緩存和路由策略，仿真結(jié)果的數(shù)據(jù)導(dǎo)入Matlab軟件進行處理。主要參數(shù)設(shè)置如下：數(shù)據(jù)塊chunk總數(shù)N=5 000，所有的數(shù)據(jù)內(nèi)容設(shè)為一個chunk大小，網(wǎng)絡(luò)中整體內(nèi)容請求服從Zipf分布，冪率指數(shù)s=0.8；節(jié)點請求到達服從泊松分布，λ=10個/s；為對比性能指標(biāo)隨節(jié)點容量變化，仿真時每個節(jié)點緩存容量取10，15，20，…，60個chunk。請求轉(zhuǎn)發(fā)方式選擇洪泛方式，命中數(shù)據(jù)在返回路徑上采用的緩存決策策略為LCE（Leave Copy Everywhere）[15]；由于考慮到NDN網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)層次性不再明顯，仿真時采用隨機分布的50個節(jié)點和1個服務(wù)器源端。

3.2 仿真結(jié)果分析

主要考慮的關(guān)鍵指標(biāo)為：節(jié)點存儲空間劃分的比例；請求平均跳數(shù)haverage(t)；內(nèi)容源端命中率γ(t)（或網(wǎng)內(nèi)節(jié)點命中率1-γ(t)），其中

hr(t)表示興趣包r到命中節(jié)點經(jīng)過的跳數(shù)，R是在t時間內(nèi)總請求數(shù)。hitr(t)表示請求r在內(nèi)容源端命中，若命中取1，其他取0。

圖2顯示了用戶請求在網(wǎng)內(nèi)節(jié)點的命中率，可以看到Po-Rep策略和LRU、LFU策略相比在網(wǎng)內(nèi)節(jié)點命中率要高。這是因為LRU策略和LFU策略中，流行度較高的周期性操作數(shù)據(jù)被過早替換掉，在節(jié)點存儲時間過久，但在過去時間段被請求頻率很高，現(xiàn)在時間段流行度較低的數(shù)據(jù)不能被替換出去，導(dǎo)致節(jié)點中數(shù)據(jù)利用率偏低，用戶端請求在網(wǎng)內(nèi)撲空率較高，隨著節(jié)點空間的增加，整個網(wǎng)絡(luò)內(nèi)的數(shù)據(jù)增加，在網(wǎng)內(nèi)節(jié)點的命中率增加。而Po-Rep策略記錄并計算出節(jié)點內(nèi)每個數(shù)據(jù)的流行度，流行度高的內(nèi)容被長時間保存在節(jié)點CS中，流行度低的內(nèi)容很快被替換出去，保證用戶請求可以快速在網(wǎng)內(nèi)節(jié)點命中。通過對內(nèi)容的區(qū)別緩存，大大提高了在網(wǎng)內(nèi)節(jié)點的命中率。圖3顯示了用戶發(fā)出的請求包經(jīng)過的平均跳數(shù)隨節(jié)點容量變化，通過對圖3的分析可知，請求在網(wǎng)內(nèi)節(jié)點命中率相比其他策略，Po-Rep策略在網(wǎng)內(nèi)命中率更高，路由到網(wǎng)內(nèi)節(jié)點要比路由到源端服務(wù)器跳數(shù)更少，對節(jié)點存儲容量分配得越大，整個網(wǎng)內(nèi)節(jié)點的存儲空間相應(yīng)增加，可以有更多的請求在網(wǎng)內(nèi)節(jié)點命中，跳數(shù)進一步減少。

圖2 網(wǎng)內(nèi)節(jié)點的命中率隨節(jié)點容量變化

圖3 平均跳數(shù)隨節(jié)點容量變化

圖4是設(shè)定每個節(jié)點的CS大小為30 chunk，顯示了興趣包在網(wǎng)內(nèi)節(jié)點的命中率隨著zipf指數(shù)s的變化情況，在s較小的點，由于流行度高的內(nèi)容分布比較廣泛，流行度高的內(nèi)容和流行度低的內(nèi)容區(qū)別不夠明顯，所以在網(wǎng)內(nèi)節(jié)點的緩存內(nèi)容基本上是包括了所有分布區(qū)域的數(shù)據(jù)。LRU和LFU，在本來就對內(nèi)容沒有流行度準(zhǔn)確預(yù)測的情況下，單個節(jié)點的空間利用率和整個網(wǎng)絡(luò)網(wǎng)內(nèi)節(jié)點的冗余度得不到改善，大量的請求仍然依賴源端服務(wù)器。隨著s的增大，流行度高的內(nèi)容分布范圍集中，導(dǎo)致大量的請求集中在少量流行度高的內(nèi)容上，所以在網(wǎng)內(nèi)節(jié)點命中率逐步增加，對服務(wù)器的依賴只存在于對流行度低的內(nèi)容請求時。而本文提出的Po-Rep策略在s較小時，仍然有一定優(yōu)勢。而隨著s增大，優(yōu)勢愈加明顯。同樣在圖5中，由對圖4的分析可知隨著s的增大，在網(wǎng)內(nèi)節(jié)點命中率更高，這樣平均跳數(shù)逐漸降低。

圖2 網(wǎng)內(nèi)節(jié)點的命中率隨節(jié)點容量變化

圖5 平均跳數(shù)隨s變化

4 結(jié)束語

為了提高命名數(shù)據(jù)網(wǎng)絡(luò)中網(wǎng)內(nèi)節(jié)點存儲空間的利用率，本文通過對內(nèi)容的流行度預(yù)測后，根據(jù)流行度的不同對內(nèi)容進行差異化緩存，提出了基于流行度預(yù)測的Po-Rep策略。通過仿真證明，在降低網(wǎng)內(nèi)數(shù)據(jù)冗余度的同時，又增加了在網(wǎng)內(nèi)節(jié)點的命中率，平均跳數(shù)也有顯著降低。但是由于沒有對緩存決策策略LCE進行改進，導(dǎo)致用戶請求在網(wǎng)內(nèi)節(jié)點中的命中率整體偏低，在后續(xù)工作中，將會在本文基礎(chǔ)上，利用流行度預(yù)測，對當(dāng)興趣包命中的內(nèi)容確定是否在返回路徑節(jié)點緩存，緩存在哪個節(jié)點的問題進行研究，對現(xiàn)存的緩存放置策略中出現(xiàn)的高冗余度性問題提出改進方案，進一步提高整個網(wǎng)內(nèi)節(jié)點緩存空間的利用率。

圖1(a)示出了四模交叉諧振器的幾何結(jié)構(gòu),其關(guān)于A-A′平面是對稱的,因此可以應(yīng)用奇偶模方法進行分析。對于奇模激勵,其等效電路如圖1(b)所示。

參考文獻：

[1]Zhang L，Afanasyey A，Burke J，et al.Named data networking[J].ACM Sigcomm ComputerCommunication Review，2014，44（3）：66-73.

[2]Cheng Yunho，Cheng Yuanho，Chien Chaotseng.A case study of cache performance in ICN—various combinations of transmission behavior and cache replacement mechanism[C]//2015 17th International Conference on Advanced Communication Technology（ICACT），Seoul，July 1-3，2015：323-328.

[3]Li Jun，F(xiàn)eng Zongming，Wu Haibo，et al.Hierarchical division-based cache storage strategy in content-centric networking[J].Journal on Communications，2016，37（1）：35-41.

[4]蔡君，趙慧民，魏文國，等.一種信息中心網(wǎng)絡(luò)內(nèi)置緩存空間大小的設(shè)計策略[J].中山大學(xué)學(xué)報：自然科學(xué)版，2015，54（6）：72-76.

[5]Cui Xiandong，Liu Jiang，Huang Tao，et al.A novel in-network caching scheme based on betweenness and replacement rate in content centric networking[J].Journal of Electronics&Information Technology，2014，36（1）：1-7.

[6]Psaras I，Clegg R G，Landa R，et al.Modeling and evaluation of CCN-caching trees[C]//Proceedings of the 10th International IFIP TC 6 Conference on Networking.Berlin：Springer，2011：78-91.

[7]Carofiglio G，Gallo M，Muscariello L，et al.Modeling data transfer in content-centric networking[C]//Proceedings of the 23rd InternationalTeletraffic Congress.Piscataway：IEEE，2011：111-118.

[8]CarofiglioG，GalloM，MuscarielloL.Bandwidthand storage sharing performance in information centric networking[C]//Proceedings of the 2011 ACM SIGCOMM Conference.New York：ACM，2011：1-6.

[9]Cao P，Irani S.Cost-aware WWW proxy caching algorithms[C]//Proceedings of the USENIX Symposium on Internet Technologies and Systems.Berkeley：USENIX Association，1997：193-206.

[10]Wang J M，Bensaou B.Improving content-centric networks performance with progressive，diversity-load driven caching[C]//Proceedings of the 2012 1st IEEE International Conference on Communications in China.Piscataway：IEEE，2012：85-90.

[11]Chen X，F(xiàn)an Q，Yin H.Caching in information-centric networking：From a content delivery path perspective[C]//Proceedings of the 2013 9th International Conference on Innovations in Information Technology.Piscataway：IEEE，2013：48-53.

[12]Jiang Qiqi，Tan Chuanhoo，Phang Cheewei.Understanding Chinese online users and their visits to websites：Application of Zipf’s law[J].International Journal of Information Management，2013，33（5）：752-763.

[13]葛國棟，郭云飛，劉彩霞，等.命名數(shù)據(jù)網(wǎng)絡(luò)中基于局部請求相似性的協(xié)作緩存路由機制[J].電子與信息學(xué)報，2015，37（2）：435-442.

[14]Alexander A，Ilya M，Zhang Lixia.ndnSIM：NDN simulator for NS-3，Technical Report NDN-005[R].NDN，May 2012.

[15]Bernardini C，Silverston T，F(xiàn)estor O.A comparison of caching strategies for content centric networking[C]//IEEE Global Communications Conference，2015：1-6.