面向緩存命中率的命名數(shù)據(jù)網(wǎng)絡(luò)緩存優(yōu)化策略

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

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

0 引 言

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

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

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

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

1 DPRP

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

本文拓?fù)淠Ｐ捅硎緸闊o向圖G=(V,E),集合V={v1,v2，…,vn}表示n個節(jié)點(diǎn),集合E={e1,e2,…,em}表示m條邊，集合Fi={f1,r2…,fk}表示節(jié)點(diǎn)vi中緩存的內(nèi)容，集合S={s1,s2,…,sp}表示內(nèi)容源服務(wù)器的集合。

當(dāng)節(jié)點(diǎn)vi緩存空間滿需要替換時，DPRP通過式(1)計(jì)算vi每個內(nèi)容塊fi的DPR值(記為DPRi)，即

(1)

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

2 HPCDP

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

(2)

式中：k表示節(jié)點(diǎn)vi當(dāng)前時刻的緩存大小。

緩存節(jié)點(diǎn)的DPRVi值SaveNodeDPRV(簡記為SDPRV)滿足

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

(3)

即緩存節(jié)點(diǎn)的平均DRP值為回傳路徑上n個節(jié)點(diǎn)中最大的。

為實(shí)現(xiàn)上述算法，需要在興趣包中添加MaxDPR與SaveNode字段，其中MaxDPR字段用于記錄興趣包經(jīng)過節(jié)點(diǎn)中平均DPR的最大值，SaveNode用于記錄MaxDPR節(jié)點(diǎn)對應(yīng)的節(jié)點(diǎn)ID。在數(shù)據(jù)包中添加SavedNode字段，其值為相應(yīng)的興趣包中SaveNode中的值，用于指示哪個中間節(jié)點(diǎn)應(yīng)當(dāng)緩存此數(shù)據(jù)包。消息格式如圖1所示。

圖 1 信息格式Fig.1 Message format

圖2為節(jié)點(diǎn)接收到數(shù)據(jù)包時HPCDP策略的處理流程，圖3為接收到數(shù)據(jù)包時HPCDP算法的處理流程圖。

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

NDNSim[18]是開源網(wǎng)絡(luò)模擬器NS3中實(shí)現(xiàn)NDN架構(gòu)的一個模塊。使用NDNSim version 2.8作為仿真工具，通過對NDNSim代碼的修改實(shí)現(xiàn)本文的策略,測試本文策略的性能。網(wǎng)絡(luò)拓?fù)洳捎肦ocketfuel[19]項(xiàng)目測量到的真實(shí)網(wǎng)絡(luò)拓?fù)銭T(ebone topology)，以最大限度模擬真實(shí)網(wǎng)絡(luò)情況。該拓?fù)浒?63個節(jié)點(diǎn)，300條鏈路，如圖4所示。

圖 4 實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)銯ig.4 Experimental retwork topology

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

3.1 實(shí)驗(yàn)指標(biāo)

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

平均路由跳數(shù)指的是用戶的請求得到響應(yīng)需要傳輸節(jié)點(diǎn)數(shù)目的平均值。平均跳數(shù)越小，用戶獲取內(nèi)容的平均下載時間越小。令平均路由跳數(shù)為HRA，可表示為

(4)

式中：hi表示請求i在網(wǎng)絡(luò)中經(jīng)過的路由跳數(shù)；Req為請求消息的集合；Q為請求總數(shù)。

緩存命中率指的是路由器緩存響應(yīng)的內(nèi)容請求數(shù)占所有用戶請求數(shù)的比例。緩存命中率越高，越能體現(xiàn)出緩存策略的高效性。令緩存命中率為NCR，可表示為

(5)

式中：請求i在中間路由節(jié)點(diǎn)緩存命中時，hti為1，否則，為0。

3.2 結(jié)果分析

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

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

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

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

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

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

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

4 結(jié)束語

為了提高命名數(shù)據(jù)網(wǎng)絡(luò)中緩存的命中率并降低請求平均路由跳數(shù)，本文提出了跟隨時間變化的動態(tài)優(yōu)先權(quán)緩存替換策略DPRP。DPR值不僅反映了內(nèi)容塊的歷史價值,也反映了內(nèi)容塊的未來價值。根據(jù)此值進(jìn)行替換后，能將緩存訪問率較高的內(nèi)容塊留在緩存中，從而提高了緩存命中率。通過在數(shù)據(jù)傳播路徑上選擇平均DPR值較大的節(jié)點(diǎn)緩存數(shù)據(jù)，可有效調(diào)整節(jié)點(diǎn)緩存內(nèi)容，從而提高節(jié)點(diǎn)的緩存命中率，進(jìn)而降低替換率。仿真實(shí)驗(yàn)表明，本文提出的策略能較好提高全網(wǎng)緩存命中率，降低請求平均路由跳數(shù)。

下一步的研究考慮將緩存決定策略與命名數(shù)據(jù)網(wǎng)絡(luò)的路由機(jī)制結(jié)合，利用更多信息設(shè)計(jì)緩存決定策略，并且考慮根據(jù)數(shù)據(jù)流行度進(jìn)行數(shù)據(jù)預(yù)取，進(jìn)一步提高緩存命中率，提高網(wǎng)絡(luò)分發(fā)效率。