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

(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í)增長(zhǎng)。根據(jù)Cisco的VNI預(yù)測(cè)報(bào)告，2021年全球IP視頻流量將占互聯(lián)網(wǎng)總流量的82%，2022年IP流量達(dá)到4.8 ZiB[1]。急速增長(zhǎng)的網(wǎng)絡(luò)流量對(duì)于傳統(tǒng)網(wǎng)絡(luò)轉(zhuǎn)發(fā)模式和轉(zhuǎn)發(fā)鏈路帶來(lái)了嚴(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)識(shí)進(jìn)行路由，充分體現(xiàn)了信息中心的特征，是最具前景的技術(shù)方案之一。區(qū)別于傳統(tǒng)的TCP/IP網(wǎng)絡(luò)，NDN網(wǎng)絡(luò)直接對(duì)內(nèi)容進(jìn)行唯一命名標(biāo)識(shí)，基于內(nèi)容進(jìn)行尋址傳輸，且網(wǎng)內(nèi)路由節(jié)點(diǎn)具有數(shù)據(jù)緩存能力。內(nèi)容請(qǐng)求者通過(guò)向網(wǎng)內(nèi)發(fā)送帶有標(biāo)識(shí)用戶想要獲取內(nèi)容名稱的興趣包，響應(yīng)者通過(guò)發(fā)送相應(yīng)的數(shù)據(jù)包沿著興趣包路徑響應(yīng)請(qǐ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)問(wèn)題之一[5-6]。

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

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

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

1 DPRP

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

本文拓?fù)淠Ｐ捅硎緸闊o(wú)向圖G=(V,E),集合V={v1,v2，…,vn}表示n個(gè)節(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緩存空間滿需要替換時(shí)，DPRP通過(guò)式(1)計(jì)算vi每個(gè)內(nèi)容塊fi的DPR值(記為DPRi)，即

(1)

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

2 HPCDP

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

(2)

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

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

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

(3)

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

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

圖 1 信息格式Fig.1 Message format

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

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

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

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

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

NDNSim[18]是開源網(wǎng)絡(luò)模擬器NS3中實(shí)現(xiàn)NDN架構(gòu)的一個(gè)模塊。使用NDNSim version 2.8作為仿真工具，通過(guò)對(duì)NDNSim代碼的修改實(shí)現(xiàn)本文的策略,測(cè)試本文策略的性能。網(wǎng)絡(luò)拓?fù)洳捎肦ocketfuel[19]項(xiàng)目測(cè)量到的真實(shí)網(wǎng)絡(luò)拓?fù)銭T(ebone topology)，以最大限度模擬真實(shí)網(wǎng)絡(luò)情況。該拓?fù)浒?63個(gè)節(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個(gè)內(nèi)容源服務(wù)器，每個(gè)內(nèi)容源服務(wù)器存儲(chǔ)4×104個(gè)不同的內(nèi)容，根據(jù)最短路徑路由算法建立轉(zhuǎn)發(fā)表。隨機(jī)選擇12個(gè)節(jié)點(diǎn)為用戶接入節(jié)點(diǎn)，用戶請(qǐng)求速率服從參數(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ì)仿真時(shí)長(zhǎng)為800 s，以消除偶然性誤差，最大限度模擬真實(shí)情況。

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

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

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

(4)

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

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

(5)

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

3.2 結(jié)果分析

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

為了提高命名數(shù)據(jù)網(wǎng)絡(luò)中緩存的命中率并降低請(qǐng)求平均路由跳數(shù)，本文提出了跟隨時(shí)間變化的動(dòng)態(tài)優(yōu)先權(quán)緩存替換策略DPRP。DPR值不僅反映了內(nèi)容塊的歷史價(jià)值,也反映了內(nèi)容塊的未來(lái)價(jià)值。根據(jù)此值進(jìn)行替換后，能將緩存訪問(wèn)率較高的內(nèi)容塊留在緩存中，從而提高了緩存命中率。通過(guò)在數(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)緩存命中率，降低請(qǐ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ā)效率。