面向緩存命中率的命名數據網絡緩存優化策略

高全力，楊 昊,李雪花，趙 輝，金 帥，徐國梁

(1.西安工程大學 計算機科學學院，陜西 西安710048;山東如意毛紡服裝集團股份有限公司，山東 濟寧 272000；3.山東如意恒成產研新材料科技有限公司，山東 濟寧 272000)

0 引 言

隨著互聯網用戶及內容規模的日益增多，網絡內的數據流量呈指數級增長。根據Cisco的VNI預測報告，2021年全球IP視頻流量將占互聯網總流量的82%，2022年IP流量達到4.8 ZiB[1]。急速增長的網絡流量對于傳統網絡轉發模式和轉發鏈路帶來了嚴峻考驗。在此背景下，信息中心網絡(information centric networking，ICN)受到廣泛重視[2]。這種網絡架構通信模式由端到端通信轉向以海量信息獲取為目標的通信。其中，NDN[3]完全以內容名字標識進行路由，充分體現了信息中心的特征，是最具前景的技術方案之一。區別于傳統的TCP/IP網絡，NDN網絡直接對內容進行唯一命名標識，基于內容進行尋址傳輸，且網內路由節點具有數據緩存能力。內容請求者通過向網內發送帶有標識用戶想要獲取內容名稱的興趣包，響應者通過發送相應的數據包沿著興趣包路徑響應請求。響應者可以是數據源服務器，也可以是網絡已緩存該數據的路由節點。因此，合理的內容緩存策略是影響NDN網絡內容分發效率的關鍵因素[4],也是當前的研究熱點問題之一[5-6]。

緩存策略包括數據包經過路由節點時決定是否進行緩存的緩存決定策略，緩存空間滿時應該替換掉哪些內容的緩存替換策略[7]。在緩存決定策略方面，代表性的有LCE(leave copy everywhere)[8]、LCD(leave copy down)[9]、Prob[10]等3種。LCE是NDN中默認的網內緩存策略，它將內容緩存在數據回傳路徑上的所有路由器節點上，提高了內容的分發和檢索速度，但同時也帶來了大量的網內冗余副本，緩存資源利用率較低[11]。LCD策略采用當請求在某節點命中時，返回的數據只在命中節點與靠近客戶端的下游路由器節點緩存，避免了同一內容在路徑所有節點的大量復制，并且只有內容被多次請求時，才會逐步緩存在離客戶端較近的節點上。潛在地考慮了內容訪問次數因素，但并未考慮下游各節點的緩存替換率，可能造成下游節點的替換率過高，導致緩存利用率較低。Prob策略采取每個沿途節點都以概率P緩存內容塊。該方法可以認為是全局沿路緩存的一般化，當P=1時，即退化為LCE策略。在緩存替換策略方面，目前比較有代表性的替換策略有LRU(least recently used)[12]、LFU(least frequently used)[13]等。LRU采取最近最少使用策略。當節點緩存滿而又需要緩存新內容時，該策略會將緩存內最近時間最少使用次數的內容塊刪除，即刪除當前價值最小的內容。LRU只考慮了內容塊訪問時間單一因素，當流行內容塊前期被大量訪問，但最近很短時間內不訪問，就會被替換出去，不能很好地反映內容塊的未來使用價值。LFU利用最不經常使用策略，即刪除當前緩存中命中次數最少的內容塊。LFU策略只將歷史訪問次數這一種因素作為判斷標準，當內容塊前期被大量訪問，而未來不再訪問，根據價值函數值此內容塊不會被替換，從而成為緩存垃圾，浪費了緩存空間。

鑒于上述策略的不足，韓奇辰等基于LCD策略提出了交替路由緩存策略，在內容塊途徑的節點交替地緩存內容塊，但忽略了各個內容塊的價值差異[14]。陳劼博等延伸了LCE策略，提出了一種基于節點介數的數據緩存策略，根據每個節點的介數中心性，將當前流行的內容緩存在較為重要的節點上，但未考慮到內容塊可向下游分發的情況[15]。BERNARDINI等提出的MPC(most popular content)緩存決定策略，路由器緩存流行度超過固定閾值的內容塊，其動態性欠佳[16]。李韜等提出一種基于流行度的緩存策略CCP(cache replacement policy based on content popularity),考慮了流行度因素，但對NDN原本架構修改較大，增加了新的表數據結構[17]。還有部分學者使用靜態的流行度閾值，沒有考慮流行度閾值隨時間的動態變化，對緩存替換策略與決定策略之間的關系考慮亦欠佳。

針對上述問題，本文提出了動態優先權的緩存替換策略(dynamic priority replacement policy，DPRP)，將緩存內容塊的訪問頻率特性、訪問時間特性作為影響緩存價值的因素，隨時間的推移動態計算出內容塊的價值，將價值最小的內容替換，從而提高緩存命中率。緩存決定算法的重點是通過選擇緩存節點的位置，結合緩存替換策略的過濾效應，使整個網絡內都緩存價值較大的內容塊，從而提升整個網絡的分發效率。此外，本文還提出了高優先權緩存決定策略(high priority cache determines policy，HPCDP)：綜合考慮請求路徑上各節點緩存內容的價值以及替換情況，選擇替換率高、緩存內容價值低的節點進行緩存，以此放大緩存替換策略的過濾效應，使網絡中所有節點都盡量緩存價值大的內容塊，進而提高命中率，降低請求平均路由跳數。

1 DPRP

針對傳統的緩存替換策略(LRU,LFU)只考慮單一因素，無法很好地體現緩存內容塊的價值，容易造成緩存利用率低的問題，提出的DPRP算法核心思想為隨著時間的變化，已緩存內容塊的DPR值是隨時間動態變化的，能較好地反映當前節點緩存內容的價值，從而通過替換提升此節點的命中率。 DPR值越大說明此內容塊流行度低，未來被訪問到的概率也不大，緩存替換時將此內容替換。

本文拓撲模型表示為無向圖G=(V,E),集合V={v1,v2，…,vn}表示n個節點,集合E={e1,e2,…,em}表示m條邊，集合Fi={f1,r2…,fk}表示節點vi中緩存的內容，集合S={s1,s2,…,sp}表示內容源服務器的集合。

當節點vi緩存空間滿需要替換時，DPRP通過式(1)計算vi每個內容塊fi的DPR值(記為DPRi)，即

(1)

式中：Ti為內容塊fi最后一次命中的時刻距現在的時間間隔；Hi為該內容塊從放入緩存到現在的命中次數。從DPR值可以看出，當某些內容塊不訪問后，其DPR值會隨著時間增加逐步增大，直到被替換出去。DPRP不僅考慮了內容塊的已命中次數，且動態地考慮了其命中的時間特性；DPR值隨著時間變化，通過DPR值不僅側面反映了內容塊歷史的價值，也反映了內容塊未來的價值。

2 HPCDP

NDN中數據包的傳播路徑是沿著請求此數據包的路徑發送給請求者的，所以要從請求路徑上的節點中選擇合適的節點對內容進行緩存，以滿足后續其他請求。針對傳統的緩存決定策略，例如LCE、LCD、Prob，獨立于緩存替換策略進行緩存決定，容易造成網內緩存冗余度過大，即緩存空間不能緩存盡可能多的不同內容塊，從而造成緩存命中率低、請求平均跳數高的問題，提出了HPCDP。結合上述DPRP過濾效應，網絡內各節點緩存的內容在未來時間內應具有較高的命中率，即DPR平均值應該較小，所以不應該在這些節點進行緩存。若某節點內容的DPR平均值較大，說明此節點替換率較高，即此節點緩存內容塊的命中率不高,所以選擇此節點進行緩存，以期望通過替換此節點緩存內容塊的方式提高此節點的緩存命中率，進而提高此節點緩存利用率。當某一請求被響應，在響應數據回傳的路徑上，選擇的內容塊緩存節點vi應是回傳路徑上所通過的所有節點中DPR平均值最大的那個節點。第i個節點的DPR平均值DPRVi可表示為

(2)

式中：k表示節點vi當前時刻的緩存大小。

緩存節點的DPRVi值SaveNodeDPRV(簡記為SDPRV)滿足

SDPRV=max(DPRV1,DPRV2,…,DPRVn)

(3)

即緩存節點的平均DRP值為回傳路徑上n個節點中最大的。

為實現上述算法，需要在興趣包中添加MaxDPR與SaveNode字段，其中MaxDPR字段用于記錄興趣包經過節點中平均DPR的最大值，SaveNode用于記錄MaxDPR節點對應的節點ID。在數據包中添加SavedNode字段，其值為相應的興趣包中SaveNode中的值，用于指示哪個中間節點應當緩存此數據包。消息格式如圖1所示。

圖 1 信息格式Fig.1 Message format

圖2為節點接收到數據包時HPCDP策略的處理流程，圖3為接收到數據包時HPCDP算法的處理流程圖。

圖 2 接收到數據包時算法處理流程Fig.2 Algorithm processing flow chart as data packet received

圖 3 接收到興趣包時算法處理流程Fig.3 Algorithm processing flow chart as interest packet received

從流程圖2、3可以看出：當數據請求在內容源服務器滿足時，數據會緩存在請求路徑的某一個節點上；當數據請求在中間節點的緩存命中時，若此下游節點的平均DPR值較大，則數據會在此節點的更靠近用戶的下游節點緩存，當前節點緩存的數據包會刪除。從而降低了緩存冗余率，提高緩存命中率，降低請求平均跳數。

3 實驗結果與分析

NDNSim[18]是開源網絡模擬器NS3中實現NDN架構的一個模塊。使用NDNSim version 2.8作為仿真工具，通過對NDNSim代碼的修改實現本文的策略,測試本文策略的性能。網絡拓撲采用Rocketfuel[19]項目測量到的真實網絡拓撲ET(ebone topology)，以最大限度模擬真實網絡情況。該拓撲包含163個節點，300條鏈路，如圖4所示。

圖 4 實驗網絡拓撲Fig.4 Experimental retwork topology

圖4中圓點表示節點，邊表示節點之間的鏈路。網絡中內容總塊數N為2.4×105種不同的內容，大小均為50 kiB；內容流行度服從Zipf[20]分布，Zipf參數范圍為0.7～1.5,鏈路帶寬為1 Gibit/s。網絡中有4個內容源服務器，每個內容源服務器存儲4×104個不同的內容，根據最短路徑路由算法建立轉發表。隨機選擇12個節點為用戶接入節點，用戶請求速率服從參數λ=100 次/s的泊松分布。網絡中節點緩存C與內容總量N之比控制在0.300%～0.025%之間，符合緩存容量遠小于網絡中內容總數的實際情況。統計仿真時長為800 s，以消除偶然性誤差，最大限度模擬真實情況。

3.1 實驗指標

為了檢驗本文提出的緩存替換策略DPRP的性能，設定緩存決定策略全部采用LCE，對比LCE+LRU、LCE+FIFO、LCE+DPRP等策略的仿真結果。為了檢驗本文提出的緩存決定策略HPCDP的性能，設定緩存替換策略全部采用LRU,對比LCE+LRU、HPCDP+LRU、Prob+LRU的仿真結果。其中Prob策略的P設置為1時，Prob策略退化為LCE策略，即在內容經過的所有節點都緩存該內容；當P過小時，則緩存利用率較低，所以P取0.5，以增強仿真對比性。為了綜合檢驗本文提出的DPRP策略與HPCDP策略的性能，對比HPCDP+DPRP、Prob+LRU、LCE+LRU、LCE+RAND等策略的仿真結果。其中性能指標主要采用平均路由跳數及緩存命中率。

平均路由跳數指的是用戶的請求得到響應需要傳輸節點數目的平均值。平均跳數越小，用戶獲取內容的平均下載時間越小。令平均路由跳數為HRA，可表示為

(4)

式中：hi表示請求i在網絡中經過的路由跳數；Req為請求消息的集合；Q為請求總數。

緩存命中率指的是路由器緩存響應的內容請求數占所有用戶請求數的比例。緩存命中率越高，越能體現出緩存策略的高效性。令緩存命中率為NCR，可表示為

(5)

式中：請求i在中間路由節點緩存命中時，hti為1，否則，為0。

3.2 結果分析

圖5為Zipf參數對緩存命中率的影響。從圖5可以看出:隨著Zipf參數的增加，6種策略的命中率不斷增加，但HPCDP+DPRP策略具有最優的性能; 當Zipf參數為1.5時，本文提出策略的緩存命中率高達92%。當緩存替換策略采用DPRP時，對比LCE+LRU、LCE+FIFO、LCE+DPRP等3種策略，LCE+DPRP策略緩存命中率最高，比LCE+LRU、LCE+FIFO分別平均提高了11.7%、15.6%；當緩存決定策略采用HPCDP時，對比LCE+LRU、HPCDP+LRU、Prob+LRU等3種策略，HPCDP+LRU策略命中率最高，相對LCE+LRU、Prob+LRU分別平均提高了6.5%、5.2%。說明本文提出的緩存替換策略DPRP與緩存決定策略HPCDP都能較好的提高緩存命中率。

圖 5 齊夫分布參數對緩存命中率的影響Fig.5 The effect of Zipf distribution parameters on cache hit rate

圖6為Zipf參數對請求平均路由跳數的影響。從圖6可以看出：隨著Zipf參數的增大各策略的平均路由跳數不斷減小，但HPCDP+DPRP策略具有最小的平均跳數。當緩存替換策略采用DPRP時，對比LCE+LRU、LCE+FIFO、LCE+DPRP等3種策略，LCE+DPRP策略的平均路由跳數最小，相對LCE+LRU、LCE+FIFO分別平均降低了7.9%、16.8%；當緩存決定策略采用HPCDP時，對比LCE+LRU、HPCDP+LRU、Prob+LRU等3種策略，HPCDP+LRU策略的平均路由跳數最小。說明本文提出的緩存替換策略DPRP與緩存決定策略HPCDP都能較好的降低平均路由跳數。

圖 6 齊夫分布參數對平均路由跳數的影響Fig.6 The effect of Ziff distribution parameters on average routing hops

圖7、8是Zipf參數為1的情況下，節點緩存容量對緩存命中率以及平均路由跳數的影響，其中緩存容量即節點可緩存的內容塊的數量。從圖7、8可以看出：在節點緩存容量較小的情況下，本文提出的策略相較于其他有更好的優勢。說明在符合網絡中緩存容量遠小于內容總量的約束條件下，本文提出的策略依然有較好的性能。

圖 7 緩存容量對緩存命中率的影響Fig.7 The effect of cache capacity on cache hit rate

圖 8 緩存容量對平均路由跳數的影響Fig.8 The effectof buffer capacity on average routing hops

4 結束語

為了提高命名數據網絡中緩存的命中率并降低請求平均路由跳數，本文提出了跟隨時間變化的動態優先權緩存替換策略DPRP。DPR值不僅反映了內容塊的歷史價值,也反映了內容塊的未來價值。根據此值進行替換后，能將緩存訪問率較高的內容塊留在緩存中，從而提高了緩存命中率。通過在數據傳播路徑上選擇平均DPR值較大的節點緩存數據，可有效調整節點緩存內容，從而提高節點的緩存命中率，進而降低替換率。仿真實驗表明，本文提出的策略能較好提高全網緩存命中率，降低請求平均路由跳數。

下一步的研究考慮將緩存決定策略與命名數據網絡的路由機制結合，利用更多信息設計緩存決定策略，并且考慮根據數據流行度進行數據預取，進一步提高緩存命中率，提高網絡分發效率。