命名數據網中基于流行度的網內緩存替換策略

劉期烈，秦慶偉，夏遠鵬，李 云

LIU Qilie,QIN Qingwei,XIAYuanpeng,LI Yun

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

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

1 引言

數據命名網絡是信息中心網的一種典型架構，與傳統的IP網絡架構相比，最根本的區別是不再依賴IP地址，將傳統的以主機為中心的模型轉變為以數據內容為中心的模型[1]。所有的數據內容被全網統一唯一命名，并且基于內容進行定位尋址、轉發路由。路由器具備和數據服務器同樣的存儲轉發功能，用戶除了在原始服務器請求內容外，可以在網內路由器節點的緩存內命中內容，極大減輕了服務器端的負載壓力。

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

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

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

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

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

2.1 Po-Rep策略基本思想

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

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

2.2 流行度計算

在整個網絡中，數據內容流行度分布仍然符合Zipf分布，即二八分布，20%的內容滿足整個網絡的80%請求量，剩下的80%內容滿足用戶20%的請求量[12]。概率為：

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

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

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

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

Tinterval-max表示所有數據中Ti_interval對應的最大時間間隔，進行歸一化處理：

而數據i平均的訪問間隔可以表示為：

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

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

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

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

步驟1數據到達節點，且根據緩存策略確定要緩存在該節點，檢測節點的CS是否已滿，若滿則轉步驟3。

步驟2直接緩存返回的數據。

圖1 流程圖

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

步驟5數據存進節點后，對其Ti、Ti_recent、Ti_first、Mi分別進行初始化。

3 仿真

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

3.1 仿真環境和參數配置

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

3.2 仿真結果分析

主要考慮的關鍵指標為：節點存儲空間劃分的比例；請求平均跳數haverage(t)；內容源端命中率γ(t)（或網內節點命中率1-γ(t)），其中

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

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

圖2 網內節點的命中率隨節點容量變化

圖3 平均跳數隨節點容量變化

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

圖2 網內節點的命中率隨節點容量變化

圖5 平均跳數隨s變化

4 結束語

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

圖1(a)示出了四模交叉諧振器的幾何結構,其關于A-A′平面是對稱的,因此可以應用奇偶模方法進行分析。對于奇模激勵,其等效電路如圖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，Feng 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]蔡君，趙慧民，魏文國，等.一種信息中心網絡內置緩存空間大小的設計策略[J].中山大學學報：自然科學版，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，Fan 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]葛國棟，郭云飛，劉彩霞，等.命名數據網絡中基于局部請求相似性的協作緩存路由機制[J].電子與信息學報，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，Festor O.A comparison of caching strategies for content centric networking[C]//IEEE Global Communications Conference，2015：1-6.