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

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

0 引 言

隨著互聯(lián)網(wǎng)生態(tài)及網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)內(nèi)的流量不斷增長，根據(jù)思科的VNI預(yù)測報告，2022年全球用戶數(shù)據(jù)流量將達到4.8 ZB[1]?？焖僭黾拥木W(wǎng)絡(luò)流量及對網(wǎng)絡(luò)質(zhì)量要求的不斷提高，現(xiàn)存的TCP/IP以鏈接為中心的網(wǎng)絡(luò)架構(gòu)逐漸顯現(xiàn)出一些弊端。建立鏈接的目的是傳輸信息，用戶關(guān)心的是信息本身，而不關(guān)注信息的存儲位置。在此思想及背景之下,信息中心網(wǎng)絡(luò)(Information Centric Networking, ICN)[2-3]得到飛速發(fā)展。信息中心網(wǎng)絡(luò)的思想一經(jīng)提出，便有眾多新型的網(wǎng)絡(luò)架構(gòu)被提出，大量科研機構(gòu)投入研究，啟動了一系列與此相關(guān)的科研項目。DONA[4]項目啟動于2006年，項目架構(gòu)設(shè)計考慮了路由器緩存、命名、命名解析、尋址等問題，雖然目前該項目已經(jīng)結(jié)束，但其研究成果為后續(xù)各種項目提供了啟發(fā)。PSIRP[5-6]項目啟動于2008年，歷時2年，倡導(dǎo)以信息為中心的發(fā)布-訂閱網(wǎng)絡(luò)模型作為未來網(wǎng)絡(luò)架構(gòu)，從而解決當(dāng)前網(wǎng)絡(luò)中由于是否信任信息發(fā)送者而產(chǎn)生的眾多問題。NetInf[7]啟動于2008年，通過數(shù)據(jù)類型定義數(shù)據(jù)名字，并給出了多種解析方式。命名數(shù)據(jù)網(wǎng)絡(luò)(Named Data Network, NDN)[8-9]啟動于2010年，是目前最有潛力的命名NDN。NDN中路由器具有緩存能力，可以緩存經(jīng)過的數(shù)據(jù)包，以滿足下次相同的請求。NDN中有2種包類型——興趣包與數(shù)據(jù)包，請求方通過發(fā)送帶有請求內(nèi)容名的興趣包請求數(shù)據(jù)，內(nèi)容源服務(wù)器或緩存有該數(shù)據(jù)的中間路由器接收到該請求時，通過發(fā)送相應(yīng)的數(shù)據(jù)包沿著興趣包傳輸路徑反向傳輸至用戶，由于路由節(jié)點有緩存能力，可以響應(yīng)部分請求，所以將數(shù)據(jù)包合理地緩存到網(wǎng)絡(luò)內(nèi)的路由器節(jié)點，能有效地提高網(wǎng)絡(luò)的分發(fā)效率[10],所以命名數(shù)據(jù)網(wǎng)絡(luò)中緩存策略是當(dāng)前的研究熱點之一[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中默認的緩存決定策略，LCE將數(shù)據(jù)包緩存到經(jīng)過的所有路由器節(jié)點，雖然充分利用了緩存空間，但各個路由節(jié)點存在大量相同的緩存內(nèi)容塊，冗余度較大。LCD策略采用標志位指導(dǎo)緩存，當(dāng)一個節(jié)點發(fā)生緩存后，設(shè)置標志位使其下游節(jié)點不緩存，從而降低了緩存冗余度，當(dāng)同一內(nèi)容被大量請求時，此內(nèi)容會逐漸緩存至邊緣節(jié)點，雖然降低了邊緣用戶的請求代價，但可能造成邊緣節(jié)點的緩存壓力過大。Prob策略即概率緩存策略，每個路由器節(jié)點根據(jù)概率可能緩存數(shù)據(jù)包也可能不緩存此數(shù)據(jù)包，當(dāng)P=1時，即退化為LCE策略，其隨機性較大，緩存利用率較低。命名數(shù)據(jù)網(wǎng)絡(luò)中傳統(tǒng)的緩存替換策略主要有LRU[15](Least Recently Used)、LFU[16](Least Frequently Used)、Rand(Random)。LRU即最近最少使用策略，當(dāng)需要緩存替換時，會將最近時間內(nèi)具有最少使用次數(shù)的內(nèi)容塊刪除，只考慮最近時間內(nèi)訪問次數(shù)這一單一因素，不能較好地反映內(nèi)容塊的價值。LFU即最不經(jīng)常使用策略，即刪除緩存中命中次數(shù)最少的內(nèi)容塊，同樣也不能較好地反映內(nèi)容塊的價值。Rand策略即隨機替換策略，當(dāng)需要替換時隨機選擇一個對象移除，隨機性較強，性能不穩(wěn)定。

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

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

1 DCVDP緩存決定策略

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

W0=Size·Hops

(1)

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

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

W=1/(W0·T/C)

(2)

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

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

(3)

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

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

表1 消息格式

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

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

2 DCVRP緩存替換策略

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

3 實驗結(jié)果與分析

仿真實驗使用NDNSim2.8[21-23]，通過編寫腳本及修改代碼，測試本文所提策略性能。網(wǎng)絡(luò)拓撲采用Rocketfuel[24]項目提供的真實環(huán)境網(wǎng)絡(luò)拓撲，此拓撲包含163個路由器、300條鏈路，如圖3所示。其中圓點表示路由器，連線表示路由器之間的鏈接。網(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個內(nèi)容源服務(wù)器，每個內(nèi)容源服務(wù)器存儲40000個不同的內(nèi)容。隨機選擇12個節(jié)點為請求節(jié)點，用戶請求速率服從參數(shù)λ=100 req/s的泊松分布[27]。網(wǎng)絡(luò)中節(jié)點緩存C與內(nèi)容總量之比控制在0.025%～0.3%之間，符合緩存容量遠小于網(wǎng)絡(luò)中內(nèi)容總數(shù)的實際情況。統(tǒng)計時長為400 s，以消除偶然造成的誤差，最大限度模擬真實情況。

3.1 實驗指標

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

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

(4)

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

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

(5)

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

3.2 結(jié)果分析

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

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

4 結(jié)束語

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

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