基于緩存價(jià)值的命名數(shù)據(jù)網(wǎng)絡(luò)緩存優(yōu)化策略

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

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

0 引 言

隨著互聯(lián)網(wǎng)生態(tài)及網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)內(nèi)的流量不斷增長(zhǎng)，根據(jù)思科的VNI預(yù)測(cè)報(bào)告，2022年全球用戶數(shù)據(jù)流量將達(dá)到4.8 ZB[1]。快速增加的網(wǎng)絡(luò)流量及對(duì)網(wǎng)絡(luò)質(zhì)量要求的不斷提高，現(xiàn)存的TCP/IP以鏈接為中心的網(wǎng)絡(luò)架構(gòu)逐漸顯現(xiàn)出一些弊端。建立鏈接的目的是傳輸信息，用戶關(guān)心的是信息本身，而不關(guān)注信息的存儲(chǔ)位置。在此思想及背景之下,信息中心網(wǎng)絡(luò)(Information Centric Networking, ICN)[2-3]得到飛速發(fā)展。信息中心網(wǎng)絡(luò)的思想一經(jīng)提出，便有眾多新型的網(wǎng)絡(luò)架構(gòu)被提出，大量科研機(jī)構(gòu)投入研究，啟動(dòng)了一系列與此相關(guān)的科研項(xiàng)目。DONA[4]項(xiàng)目啟動(dòng)于2006年，項(xiàng)目架構(gòu)設(shè)計(jì)考慮了路由器緩存、命名、命名解析、尋址等問(wèn)題，雖然目前該項(xiàng)目已經(jīng)結(jié)束，但其研究成果為后續(xù)各種項(xiàng)目提供了啟發(fā)。PSIRP[5-6]項(xiàng)目啟動(dòng)于2008年，歷時(shí)2年，倡導(dǎo)以信息為中心的發(fā)布-訂閱網(wǎng)絡(luò)模型作為未來(lái)網(wǎng)絡(luò)架構(gòu)，從而解決當(dāng)前網(wǎng)絡(luò)中由于是否信任信息發(fā)送者而產(chǎn)生的眾多問(wèn)題。NetInf[7]啟動(dòng)于2008年，通過(guò)數(shù)據(jù)類型定義數(shù)據(jù)名字，并給出了多種解析方式。命名數(shù)據(jù)網(wǎng)絡(luò)(Named Data Network, NDN)[8-9]啟動(dòng)于2010年，是目前最有潛力的命名NDN。NDN中路由器具有緩存能力，可以緩存經(jīng)過(guò)的數(shù)據(jù)包，以滿足下次相同的請(qǐng)求。NDN中有2種包類型——興趣包與數(shù)據(jù)包，請(qǐng)求方通過(guò)發(fā)送帶有請(qǐng)求內(nèi)容名的興趣包請(qǐng)求數(shù)據(jù)，內(nèi)容源服務(wù)器或緩存有該數(shù)據(jù)的中間路由器接收到該請(qǐng)求時(shí)，通過(guò)發(fā)送相應(yīng)的數(shù)據(jù)包沿著興趣包傳輸路徑反向傳輸至用戶，由于路由節(jié)點(diǎn)有緩存能力，可以響應(yīng)部分請(qǐng)求，所以將數(shù)據(jù)包合理地緩存到網(wǎng)絡(luò)內(nèi)的路由器節(jié)點(diǎn)，能有效地提高網(wǎng)絡(luò)的分發(fā)效率[10],所以命名數(shù)據(jù)網(wǎng)絡(luò)中緩存策略是當(dāng)前的研究熱點(diǎn)之一[11-12]。

緩存策略包括緩存決定策略與緩存替換策略[13]。傳統(tǒng)的緩存決定策略有LCE(Leave Copy Everywhere)[14]、LCD(Leave Copy Down)[13]、Prob(Copy with Probability)[14]、MCD(Move Copy Down)[13]等。LCE是NDN中默認(rèn)的緩存決定策略，LCE將數(shù)據(jù)包緩存到經(jīng)過(guò)的所有路由器節(jié)點(diǎn)，雖然充分利用了緩存空間，但各個(gè)路由節(jié)點(diǎn)存在大量相同的緩存內(nèi)容塊，冗余度較大。LCD策略采用標(biāo)志位指導(dǎo)緩存，當(dāng)一個(gè)節(jié)點(diǎn)發(fā)生緩存后，設(shè)置標(biāo)志位使其下游節(jié)點(diǎn)不緩存，從而降低了緩存冗余度，當(dāng)同一內(nèi)容被大量請(qǐng)求時(shí)，此內(nèi)容會(huì)逐漸緩存至邊緣節(jié)點(diǎn)，雖然降低了邊緣用戶的請(qǐng)求代價(jià)，但可能造成邊緣節(jié)點(diǎn)的緩存壓力過(guò)大。Prob策略即概率緩存策略，每個(gè)路由器節(jié)點(diǎn)根據(jù)概率可能緩存數(shù)據(jù)包也可能不緩存此數(shù)據(jù)包，當(dāng)P=1時(shí)，即退化為L(zhǎng)CE策略，其隨機(jī)性較大，緩存利用率較低。命名數(shù)據(jù)網(wǎng)絡(luò)中傳統(tǒng)的緩存替換策略主要有LRU[15](Least Recently Used)、LFU[16](Least Frequently Used)、Rand(Random)。LRU即最近最少使用策略，當(dāng)需要緩存替換時(shí)，會(huì)將最近時(shí)間內(nèi)具有最少使用次數(shù)的內(nèi)容塊刪除，只考慮最近時(shí)間內(nèi)訪問(wèn)次數(shù)這一單一因素，不能較好地反映內(nèi)容塊的價(jià)值。LFU即最不經(jīng)常使用策略，即刪除緩存中命中次數(shù)最少的內(nèi)容塊，同樣也不能較好地反映內(nèi)容塊的價(jià)值。Rand策略即隨機(jī)替換策略，當(dāng)需要替換時(shí)隨機(jī)選擇一個(gè)對(duì)象移除，隨機(jī)性較強(qiáng)，性能不穩(wěn)定。

針對(duì)上述問(wèn)題，韓奇辰等人[17]優(yōu)化LCD緩存決定策略提出了交替路由緩存策略，在數(shù)據(jù)包路徑上交替地緩存，提高了緩存利用率，但忽略了各個(gè)內(nèi)容塊的價(jià)值差異。陳劼博等人[18]優(yōu)化了LCE策略，根據(jù)每個(gè)節(jié)點(diǎn)的重要性即介數(shù)中心性，將當(dāng)前網(wǎng)絡(luò)內(nèi)較為流行的內(nèi)容緩存到節(jié)點(diǎn)介數(shù)較大的路由節(jié)點(diǎn)上，但未考慮到可將內(nèi)容塊逐漸下發(fā)至下游節(jié)點(diǎn)。Bernardini等人[19]提出的MPC(Most Popular Content)策略，路由器節(jié)點(diǎn)緩存流行度超過(guò)固定值的內(nèi)容塊，實(shí)時(shí)性較差。朱軼等人[20]提出一種基于流行度的緩存策略，考慮了流行度因素，但使用靜態(tài)的流行度閾值，其動(dòng)態(tài)性考慮欠佳。

針對(duì)上述問(wèn)題，本文提出一種動(dòng)態(tài)緩存價(jià)值的緩存替換策略DCVRP(Dynamic Cache Value Replacement Policy)，緩存價(jià)值度量考慮了請(qǐng)求內(nèi)容大小、請(qǐng)求所花費(fèi)的跳數(shù)以及內(nèi)容塊被訪問(wèn)的時(shí)間特性，且其緩存價(jià)值隨著時(shí)間動(dòng)態(tài)變化，從而在緩存替換時(shí)保留價(jià)值較大內(nèi)容塊，進(jìn)而提高網(wǎng)絡(luò)內(nèi)的緩存命中率。緩存決定策略主要是根據(jù)相應(yīng)規(guī)則決定是否緩存當(dāng)前經(jīng)過(guò)的數(shù)據(jù)包，本文提出一種動(dòng)態(tài)緩存價(jià)值的緩存決定策略DCVDP(Dynamic Cache Value Determines Policy),將興趣包經(jīng)過(guò)的所有節(jié)點(diǎn)的緩存情況作為參考因素，最終合理地選擇數(shù)據(jù)包緩存的節(jié)點(diǎn)。

1 DCVDP緩存決定策略

由于被請(qǐng)求的數(shù)據(jù)包的大小不同，以及請(qǐng)求者距離內(nèi)容服務(wù)器(Content Server, CS)的跳數(shù)不同，所以將被請(qǐng)求數(shù)據(jù)包大小及距離作為考量因素，計(jì)算此被請(qǐng)求內(nèi)容塊的初始價(jià)值。計(jì)算方式如下：

W0=Size·Hops

(1)

其中，Size是被請(qǐng)求數(shù)據(jù)包的大小，單位為MB, Hops為CS與內(nèi)容請(qǐng)求者之間的路由跳數(shù)。當(dāng)所請(qǐng)求的內(nèi)容塊越大，請(qǐng)求跳數(shù)越大，其初始價(jià)值就越大，越具有緩存價(jià)值，緩存所得的收益越大。

中間路由節(jié)點(diǎn)緩存的內(nèi)容塊價(jià)值隨時(shí)間及請(qǐng)求次數(shù)的變化方式如下：

W=1/(W0·T/C)

(2)

其中，T表示當(dāng)前時(shí)刻與該內(nèi)容塊最后一次被請(qǐng)求時(shí)刻相減的時(shí)間差，C表示CS中此內(nèi)容塊的緩存命中次數(shù)。從表達(dá)式可以看到隨著T增大，即內(nèi)容塊當(dāng)前時(shí)刻與最后一次訪問(wèn)時(shí)刻的時(shí)間差越來(lái)越大，T/C的值將越來(lái)越大，其緩存價(jià)值將越來(lái)越小。

為了充分利用網(wǎng)內(nèi)各路由節(jié)點(diǎn)的緩存空間，若數(shù)據(jù)包傳輸路徑上存在緩存空間，則直接緩存該內(nèi)容；若各個(gè)節(jié)點(diǎn)緩存空間都滿，則緩存在平均緩存內(nèi)容價(jià)值最小的路由節(jié)點(diǎn)上。各節(jié)點(diǎn)平均緩存內(nèi)容價(jià)值計(jì)算方式如下：

(3)

其中，nj為節(jié)點(diǎn)j緩存內(nèi)容的總塊數(shù)。

為了實(shí)現(xiàn)上述算法，需要在興趣包中添加Node字段、MinValue字段及Hops字段，數(shù)據(jù)包中添加Node字段。其中數(shù)據(jù)包與興趣包中的Node字段用于標(biāo)識(shí)緩存數(shù)據(jù)包的路由節(jié)點(diǎn)ID；興趣包中的MinValue字段用于記錄請(qǐng)求路徑上節(jié)點(diǎn)的最小平均緩存內(nèi)容價(jià)值；Hops字段用于記錄跳數(shù)，興趣包每經(jīng)過(guò)一個(gè)路由器，Hops字段數(shù)值加1。消息格式如表1所示。

表1 消息格式

當(dāng)中間路由節(jié)點(diǎn)接收到興趣包時(shí)處理流程如圖1所示。

如圖1所示，當(dāng)興趣包在CS命中時(shí)，節(jié)點(diǎn)將興趣包中的Node字段，寫(xiě)入數(shù)據(jù)包的Node字段以指示其下游緩存此數(shù)據(jù)包的節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)接收到數(shù)據(jù)包時(shí)處理流程如圖2所示。

2 DCVRP緩存替換策略

針對(duì)命名數(shù)據(jù)網(wǎng)絡(luò)中LRU、LFU等緩存替換策略存在的無(wú)法較準(zhǔn)確地在緩存滿的情況下將價(jià)值小的內(nèi)容替換出去，保留價(jià)值大的內(nèi)容塊，造成的緩存利用率低的問(wèn)題，本文提出DCVRP緩存替換算法，緩存價(jià)值越大說(shuō)明此內(nèi)容塊流行度越大，即價(jià)值越大，未來(lái)被訪問(wèn)到的概率越大。其基本思想是，隨著時(shí)間的流逝，路由器CS中所緩存的內(nèi)容塊的價(jià)值是隨時(shí)間流逝動(dòng)態(tài)變化的，所以能比較準(zhǔn)確地反映當(dāng)前時(shí)間內(nèi)容的價(jià)值，實(shí)時(shí)性較好。具體規(guī)則為當(dāng)節(jié)點(diǎn)有要緩存的數(shù)據(jù)包但是緩存已滿時(shí)，通過(guò)式(2)計(jì)算各內(nèi)容塊的緩存價(jià)值，然后將價(jià)值最小的緩存內(nèi)容替換出去。從式(2)可以看出，內(nèi)容塊的緩存價(jià)值綜合考慮了訪問(wèn)的次數(shù)、訪問(wèn)時(shí)間特性及訪問(wèn)者與請(qǐng)求者之間的路由跳數(shù)。

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

仿真實(shí)驗(yàn)使用NDNSim2.8[21-23]，通過(guò)編寫(xiě)腳本及修改代碼，測(cè)試本文所提策略性能。網(wǎng)絡(luò)拓?fù)洳捎肦ocketfuel[24]項(xiàng)目提供的真實(shí)環(huán)境網(wǎng)絡(luò)拓?fù)?，此拓?fù)浒?63個(gè)路由器、300條鏈路，如圖3所示。其中圓點(diǎn)表示路由器，連線表示路由器之間的鏈接。網(wǎng)絡(luò)中內(nèi)容總塊數(shù)n=160000，流行度服從Zipf[25-26]分布，Zipf參數(shù)設(shè)置為0.7～1.5。鏈路帶寬為1 Gbit/s，網(wǎng)絡(luò)中有4個(gè)內(nèi)容源服務(wù)器，每個(gè)內(nèi)容源服務(wù)器存儲(chǔ)40000個(gè)不同的內(nèi)容。隨機(jī)選擇12個(gè)節(jié)點(diǎn)為請(qǐng)求節(jié)點(diǎn)，用戶請(qǐng)求速率服從參數(shù)λ=100 req/s的泊松分布[27]。網(wǎng)絡(luò)中節(jié)點(diǎn)緩存C與內(nèi)容總量之比控制在0.025%～0.3%之間，符合緩存容量遠(yuǎn)小于網(wǎng)絡(luò)中內(nèi)容總數(shù)的實(shí)際情況。統(tǒng)計(jì)時(shí)長(zhǎng)為400 s，以消除偶然造成的誤差，最大限度模擬真實(shí)情況。

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

為了檢驗(yàn)本文提出的緩存策略的性能，對(duì)比DCVDP+DCVRP、Prob+LRU、LCE+LRU、LCE+RAND的仿真結(jié)果。指標(biāo)采用平均路由跳數(shù)(Average number of Route Hops, ARH)及緩存命中率(Cache Hit Ratio, CHR)。

平均路由跳數(shù)是指興趣包被路由節(jié)點(diǎn)或內(nèi)容源服務(wù)器滿足的平均跳數(shù)，平均路由跳數(shù)越小，則說(shuō)明響應(yīng)越快。計(jì)算方法如下：

(4)

其中，hi表示請(qǐng)求數(shù)據(jù)包經(jīng)過(guò)的路由跳數(shù)，Req為請(qǐng)求消息的集合，Q為網(wǎng)絡(luò)內(nèi)請(qǐng)求總數(shù)。

緩存命中率是指興趣包在路由器節(jié)點(diǎn)被滿足的數(shù)量占請(qǐng)求總數(shù)的比例，緩存命中率越高，意味著緩存策略效果越好。計(jì)算方法如下：

(5)

其中，Q表示請(qǐng)求總數(shù)，Req為請(qǐng)求消息的集合，hiti表示請(qǐng)求i是否在中間路由節(jié)點(diǎn)緩存命中。

3.2 結(jié)果分析

圖4為Zipf參數(shù)對(duì)平均請(qǐng)求跳數(shù)影響的仿真結(jié)果，橫軸為Zipf分布參數(shù)，縱軸為平均路由跳數(shù)。從實(shí)驗(yàn)結(jié)果可以看出，各緩存策略下，Zipf參數(shù)越大，平均請(qǐng)求跳數(shù)越小，對(duì)比于傳統(tǒng)的緩存策略Prob+LRU、LCE+LRU、LCE+RAND，本文提出的策略有更小的平均請(qǐng)求跳數(shù)，說(shuō)明了其可用性及有效性。

圖5為Zipf分布參數(shù)對(duì)緩存命中率影響的仿真結(jié)果，橫軸為Zipf分布參數(shù)，縱軸為緩存命中率。從仿真結(jié)果可以看出隨著Zipf分布參數(shù)的增大，4種策略的緩存命中率不斷增加，但本文提出的策略具有最優(yōu)的性能，當(dāng)Zipf分布參數(shù)為1.5時(shí)，本文提出策略的緩存命中率高達(dá)85%。對(duì)比LCE+LRU、LCE+RAND、Prob+LRU這3種策略，本文提出的DCVDP+DCVRP策略命中率最高，相對(duì)其他策略平均提高了6%，這說(shuō)明本文提出的策略相比傳統(tǒng)的緩存策略有更高的緩存命中率。

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

為了更有效地利用命名數(shù)據(jù)網(wǎng)絡(luò)中路由節(jié)點(diǎn)的緩存空間，本文提出了基于緩存價(jià)值的緩存決定策略DCVDP，將內(nèi)容塊大小與請(qǐng)求跳數(shù)作為考量因素，且內(nèi)容塊價(jià)值隨時(shí)間動(dòng)態(tài)變化，從而更實(shí)時(shí)地反映內(nèi)容塊的價(jià)值?；诖颂岢隽薉CVRP緩存替換策略，當(dāng)需要替換時(shí)將當(dāng)前路由節(jié)點(diǎn)中價(jià)值最小的內(nèi)容替換出去，從而提升整個(gè)網(wǎng)絡(luò)內(nèi)緩存的利用率。經(jīng)過(guò)大量仿真實(shí)驗(yàn)，結(jié)果表明本文提出的策略相比于傳統(tǒng)的策略能更好地提升緩存命中率及降低平均請(qǐng)求跳數(shù)。

下一步將考慮更多反映內(nèi)容塊價(jià)值的因素，更加準(zhǔn)確地反映內(nèi)容塊的緩存價(jià)值，從而進(jìn)一步提升整個(gè)網(wǎng)絡(luò)的分發(fā)效率。