命名數(shù)據(jù)網(wǎng)絡(luò)中基于數(shù)據(jù)請求節(jié)點的就近緩存算法

張 浪，韓 敏，鄭 勇，吳婷婷，侯 睿

(中南民族大學(xué) 計算機科學(xué)學(xué)院，武漢 430074)

0 引 言

隨著互聯(lián)網(wǎng)信息量的飛速增長，目前以地址，如IP，為尋址方式的數(shù)據(jù)傳輸和交換方式在移動性、安全性、網(wǎng)絡(luò)地址轉(zhuǎn)換等方面出現(xiàn)一定制約，未來互聯(lián)網(wǎng)的發(fā)展以及用戶的需求必然以信息內(nèi)容為核心而不是其所存在的地址，因此，信息中心網(wǎng)絡(luò)(information-centric networking,ICN)[1-2]以數(shù)據(jù)信息為資源共享的特點，恰好適應(yīng)了未來網(wǎng)絡(luò)的發(fā)展趨勢，目前已得到世界各國研究者的高度關(guān)注。在ICN中，命名數(shù)據(jù)網(wǎng)絡(luò)(named data networking,NDN)[3]以其分布式的信息緩存方式、耦合路由等特點被認為是ICN中最有效的部署方案之一。

在NDN中，數(shù)據(jù)信息分布式存儲或緩存在NDN所有節(jié)點中，數(shù)據(jù)請求節(jié)點(consumer)首先發(fā)出interest包去探尋所需信息，interest包中含有所需數(shù)據(jù)信息的名稱，其每經(jīng)過一個NDN路由器，依次在內(nèi)容存儲數(shù)據(jù)庫(content store,CS)、待定興趣表(pending interest table,PIT)和轉(zhuǎn)發(fā)信息庫(forwarding information base,FIB)中進行數(shù)據(jù)查找、端口登記、數(shù)據(jù)最長匹配查詢并轉(zhuǎn)發(fā)等處理。數(shù)據(jù)發(fā)布節(jié)點(publisher)收到interest包后，將對應(yīng)數(shù)據(jù)信息封裝成data包發(fā)送到NDN網(wǎng)絡(luò)，data包沿interest所經(jīng)歷路徑原路返回至數(shù)據(jù)請求節(jié)點，并在所經(jīng)過的每一個NDN路由器中將此數(shù)據(jù)信息進行緩存。因此，合理優(yōu)化管理NDN路由器中有限的緩存資源，能有效提高NDN網(wǎng)絡(luò)數(shù)據(jù)存儲、轉(zhuǎn)發(fā)和路由性能。

1 研究現(xiàn)狀

目前的IP網(wǎng)絡(luò)數(shù)據(jù)傳輸大多基于C/S模式，數(shù)據(jù)傳輸?shù)闹虚g節(jié)點沒有緩存功能，因此，請求時延和路由跳數(shù)較大，這是目前IP網(wǎng)絡(luò)的弊端。而NDN采用沿途緩存方式(cache everything everywhere,CEE)有效提高了信息搜索和獲取速度，提高了效率，但CEE會出現(xiàn)節(jié)點緩存趨于同質(zhì)化，緩存內(nèi)容可能出現(xiàn)大量重復(fù)從而導(dǎo)致信息冗余等問題；文獻[4]提出只在數(shù)據(jù)信息命中節(jié)點的直接下一跳緩存應(yīng)答數(shù)據(jù)包(leave copy down,LCD)，避免內(nèi)容的重復(fù)緩存，但并沒有考慮數(shù)據(jù)請求節(jié)點的影響，而且被替換出來的data包再次請求時只能轉(zhuǎn)發(fā)到數(shù)據(jù)發(fā)布節(jié)點進行響應(yīng)；文獻[5]提出一種隨機單點緩存方法(randomly copy one,RCOne)，即在沿途路徑隨機選擇單個節(jié)點進行內(nèi)容數(shù)據(jù)緩存，減少了信息冗余；文獻[6]提出一種基于概率的緩存方法Procache(copy with probability)，依據(jù)節(jié)點距離數(shù)據(jù)源距離和路徑的剩余緩存能力，計算節(jié)點對應(yīng)的緩存概率，這是對零緩存和全緩存的一種折中算法，但RCOne和Procache均沒有考慮請求內(nèi)容的流行度問題；文獻[7]提出一種根據(jù)請求內(nèi)容的流行度以及存儲節(jié)點的位置來計算緩存時間的緩存方法，但此流行度是靜態(tài)的；文獻[9]同樣提出一種依據(jù)內(nèi)容流行度以指數(shù)方式逐步增加沿途緩存的方案(WAVE)，但沒有考慮緩存駐留時間，只是對LCD進行了有限改進；文獻[8]提出一種基于節(jié)點介數(shù)的緩存方案，其原理是通過計算網(wǎng)絡(luò)拓撲路徑上介數(shù)最大的節(jié)點(最重要的節(jié)點)來進行數(shù)據(jù)緩存，這會造成了介數(shù)最大節(jié)點負載過重、頻繁替換緩存、其他節(jié)點被閑置等問題。

可見，以上方案在考慮數(shù)據(jù)請求節(jié)點與數(shù)據(jù)發(fā)布節(jié)點的距離、請求內(nèi)容的熱度，以及動態(tài)改變數(shù)據(jù)包的緩存時間等問題上尚存在一定局限。鑒于此，本文提出一種基于數(shù)據(jù)請求節(jié)點的就近緩存算法(consumer-based proximity caching algorithm,CPCA)，該算法依據(jù)數(shù)據(jù)請求節(jié)點的不同，根據(jù)內(nèi)容熱度的變化趨勢，將熱度高的內(nèi)容動態(tài)推進到數(shù)據(jù)請求節(jié)點周邊，并且使熱度高的內(nèi)容能長時間緩存，同時將熱度低的內(nèi)容推到數(shù)據(jù)發(fā)布節(jié)點周邊，有效提高了數(shù)據(jù)信息的首跳命中率，減少了請求時延和平均跳數(shù)。

2 CPCA算法原理

CPCA算法中規(guī)定數(shù)據(jù)從數(shù)據(jù)請求節(jié)點到數(shù)據(jù)發(fā)布節(jié)點的傳輸方向為上游方向，相反則為下游方向，同時本文稱與數(shù)據(jù)請求節(jié)點直連的NDN路由器為請求路由器。根據(jù)算法需要，CPCA改進了NDN網(wǎng)絡(luò)中data包的格式，如圖1所示。

類型(Type)內(nèi)容名字(Contentname)緩存標志位(CI)緩存時間(CT)剩余緩存時間(CRT)簽名信息(Signature)數(shù)據(jù)(Data)

圖1改進的data包格式
Fig.1 Improved data packet format

圖1中，類型(Type)字段表明了該data包的業(yè)務(wù)類型；內(nèi)容名字(content name)字段記錄了該data包所承載的數(shù)據(jù)信息的名稱；緩存標志位(caching index,CI)字段為緩存標志位，初始化為0，當其為1時，指示NDN路由器緩存該data包(實際上緩存的是data包中所承載的數(shù)據(jù)信息，為簡單起見，本文簡述為緩存data包)；緩存時間(caching time ,CT)字段記錄的是該data包的緩存時間，單位為秒；緩存剩余時間(caching remain time,CRT)字段記錄的是該data包的剩余緩存時間，當其為0時，該data包可被替換；簽名信息(Signature)字段記錄的是簽名信息，如發(fā)布者ID等；Data字段為該data包承載的數(shù)據(jù)信息；此外將NDN路由器中CS的剩余存儲空間大小記為(remain caching size,RCS)，data包的大小記為DS(data packet size)。

CPCA的主要思想是①當data包到達相應(yīng)的請求路由器時或其CI字段值為1時，進入該路由器的CS進行緩存；②當請求路由器緩存容量達到上限，新到來的data包替換節(jié)點中已經(jīng)緩存的data包，如果沒有可替換狀態(tài)的data包，則選擇CRT值最小的data包進行替換，如果有可替換的data包，則依據(jù)LRU(least recently used)原則從可替換狀態(tài)的data包中選擇一個data包進行替換，將被替換出來的data包CI置為1，指示上游節(jié)點進行緩存，上游節(jié)點執(zhí)行相同的替換算法，直到data包能夠進入CS進行緩存；③當data包進入CS時，CRT字段的值更新為該data包的當前CRT字段的值加上CT后的值。

圖2給出了CPCA算法的流程圖。

圖2 CPCA算法流程圖Fig.2 Algorithm flow chart of CPCA

同時給出CPCA算法和緩存過程偽代碼，如下所示。

Algorithm1CPCA

1 if 該節(jié)點是數(shù)據(jù)發(fā)布節(jié)點then

2 刪除該data包

3 else if 該節(jié)點是對應(yīng)請求節(jié)點或者該data包緩存標志位為1 then

4 緩存該data包

5 else

6 將該data包轉(zhuǎn)發(fā)至下游節(jié)點

7 end if

Algorithm2Caching

1 symbol←true

2 while symbol is true do

3 if DS<=RCS then

4 把該data包插入到節(jié)點的CS中

5 CRT←CRT+CT

6 更新該data包的剩余緩存時間

7 symbol←false

8 else

9 if 沒有可替換狀態(tài)的data包then

10 選擇一個剩余緩存時間最小的data包

11 else

12 用LRU原則從CS中選擇一個data包

13 CI←1

14 將該data包向上游節(jié)點轉(zhuǎn)發(fā)

15 symbol←true

16 end if

17 end if

18 end while

3 仿真與性能分析

為了驗證CPCA算法的有效性，本文利用Matlab配合C++代碼進行了模擬仿真實驗。首先基于改進的Salama[10]算法用Matlab隨機生成一個具有50個節(jié)點的NDN網(wǎng)絡(luò)拓撲，如圖3所示。不失一般性，本文假設(shè)該NDN網(wǎng)絡(luò)中的數(shù)據(jù)信息有1 000個，每個信息內(nèi)容大小設(shè)為1 MByte， NDN中間路由器緩存容量皆設(shè)為50 MByte，鏈路帶寬為100 Mbit/s，在網(wǎng)絡(luò)中設(shè)置了一個數(shù)據(jù)發(fā)布節(jié)點負責內(nèi)容的存儲和發(fā)布，在網(wǎng)絡(luò)邊緣設(shè)置有8個數(shù)據(jù)請求節(jié)點發(fā)出interest請求。Interest包的到達服從參數(shù)λ為10的泊松過程，請求概率服從Zipf分布[11]，仿真時間設(shè)為100 s，采樣周期為1 s，仿真開始時所有NDN中間路由器無緩存，緩存替換采用LRU規(guī)則。

圖3 實驗拓撲圖Fig.3 Experimental topology

將CPCA算法與目前NDN中采用的緩存方法、Procache和WAVE進行對比分析，評價指標采用緩存命中率(cache hit ratio，CHR)[12]、平均路由跳數(shù)(average route hop，ARH)[13]和平均請求時延(average request delay，ARD)[14]。CHR表示NDN網(wǎng)絡(luò)中interest包在中間路由器被成功響應(yīng)的概率；ARD表示節(jié)點發(fā)送interest包到接收到對應(yīng)的data包所產(chǎn)生的平均時延；ARH表示成功獲得響應(yīng)的interest包所傳輸?shù)钠骄嚯x，以路由跳數(shù)計算。設(shè)所有數(shù)據(jù)請求節(jié)點發(fā)出的interest包數(shù)量總和為m，數(shù)據(jù)發(fā)布節(jié)點響應(yīng)數(shù)據(jù)包的總數(shù)為n，一個采樣周期內(nèi)共發(fā)出了j個interest請求，其中，第i個interest包得到響應(yīng)的路由跳數(shù)為Xi，響應(yīng)時延為Ti。3種評價指標計算公式如下

CHR=1-n/m

(1)

(2)

(3)

圖4給出了4種方案CHR指標對比，從圖4中可以看到，在運用CPCA的NDN中，數(shù)據(jù)請求節(jié)點的首跳命中率和緩存命中率皆高于其余3種方案。主要原因在于傳統(tǒng)NDN采用沿途緩存方法(cache everything everywhere，CEE)，該方法是將原路返回的data包全部緩存在其經(jīng)過的每一個NDN路由器上，因此，造成了大量的緩存冗余，且路由器中的緩存替換操作頻繁，增加了其處理開銷；Procache根據(jù)路由器節(jié)點與用戶節(jié)點間的距離來計算節(jié)點的緩存概率，越靠近用戶的節(jié)點其緩存概率就越高，因此，用戶周圍節(jié)點緩存替換頻繁，而網(wǎng)絡(luò)核心處節(jié)點的緩存空間利用不高；WAVE根據(jù)信息內(nèi)容的請求頻率以指數(shù)增長的方式增加沿途緩存信息內(nèi)容的個數(shù)，但其指數(shù)式的增長方式使得用戶周圍節(jié)點頻繁替換緩存內(nèi)容，且節(jié)點間的交互報文也增加了網(wǎng)絡(luò)負載。CPCA優(yōu)先考慮在數(shù)據(jù)請求節(jié)點進行緩存，增大了首跳命中率和內(nèi)容請求的就近響應(yīng)率；通過動態(tài)設(shè)置data包的緩存時間，使熱度越高的信息內(nèi)容緩存時間越長，且被替換的data包沒有被直接刪除，而是向上一跳緩存，增大了緩存命中率，減小了數(shù)據(jù)發(fā)布節(jié)點的負載。

圖4 4種方案的CHR比較Fig.4 CHR comparison of the four schemes

圖5給出了4種方案的ARD指標對比，從圖5中可以看到，在運行4種緩存算法的NDN網(wǎng)絡(luò)中，ARD指標曲線走勢皆逐漸減小，并趨于平緩，這是因為開始階段是數(shù)據(jù)信息在NDN路由器中緩存積累的階段，待一段時間后，NDN路由器中的數(shù)據(jù)信息量達到一定規(guī)模，便趨于穩(wěn)定。同時可以看到，CPCA在整個過程中的ARD指標比其余3種方案皆具有優(yōu)勢，證明CPCA能夠有效縮短interest包的搜索時間，提高數(shù)據(jù)信息對象的命中率。

圖6給出了4種方案的ARH指標對比，從圖6中可以看到，和圖5相似，4種算法運行的NDN網(wǎng)絡(luò)中，ARH指標皆逐漸降低，最后趨于平緩。主要原因在于NDN路由器的緩存逐漸趨于飽和，獲取信息的路由跳數(shù)便有所減少。同樣可以看到，CPCA算法在整個路由過程中，所經(jīng)歷的路由平均跳數(shù)較其余3種方案皆有明顯的減少，主要取決于CPCA能夠根據(jù)數(shù)據(jù)信息的請求頻率，把熱度較高的數(shù)據(jù)信息盡可能緩存于數(shù)據(jù)請求節(jié)點附近，且為了減小緩存冗余，相同數(shù)據(jù)信息不重復(fù)緩存，這樣就在很大程度上減少數(shù)據(jù)請求的路由跳數(shù)。

圖5 4種方案的ARD比較Fig.5 ARD comparison of the four schemes

圖6 4種方案的ARH比較Fig.6 ARH comparison of the four schemes

圖7給出了在NDN路由器配備100 M，150 M和200 M等不同容量緩存情況下，CPCA的ARH指標性能。從圖7中看到，ARH隨著緩存容量的增加而有所減少，證明緩存的增加能夠有效增大interest包請求的命中率，減少平均路由跳數(shù)。

4 結(jié) 論

優(yōu)化的內(nèi)容緩存能有效提高NDN的數(shù)據(jù)信息搜索效率，發(fā)揮NDN網(wǎng)絡(luò)的優(yōu)勢。本文針對現(xiàn)有緩存算法的局限，考慮到了首跳命中的重要性以及內(nèi)容熱度對緩存的影響，提出了基于數(shù)據(jù)請求節(jié)點的就近緩存算法。該算法重點在數(shù)據(jù)請求節(jié)點的上一跳NDN路由器中進行緩存，且把內(nèi)容熱度低的數(shù)據(jù)不斷推送到內(nèi)容源服務(wù)器數(shù)據(jù)發(fā)布節(jié)點周圍，把熱度高的數(shù)據(jù)拉到請求節(jié)點周圍，仿真結(jié)果顯示，所提算法有效提高NDN緩存命中率，降低數(shù)據(jù)獲取時延。本文提出的方法在用戶請求差異度較大時有良好的性能，但在用戶請求差異度不大時，相鄰節(jié)點間可能會存在一定的數(shù)據(jù)信息重復(fù)緩存，在今后的研究中將考慮相鄰節(jié)點間的協(xié)作來進行緩存優(yōu)化，進一步提升該算法的性能。

圖7 不同緩存容量大小情況下的ARHFig.7 ARH in different cache capacity sizes

[1] ZHANG M,LUO H,ZHANG H.A survey of caching mechanisms in information-centric networking[J].IEEE Communications Surveys & Tutorials,2015,17(3):1473-1499.

[2] XYLOMENOS G, VERVERIDIS C N, SIRIS V A, et al. A survey of information-centric networking research[J]. IEEE Communications Surveys & Tutorials, 2014, 16(2): 1024-1049.

[3] ZHANG L, AFANASYEV A, BURKE J, et al. Named data networking[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(3): 66-73.

[4] BERNARDINI C, SILVERSTON T, FESTOR O. A comparison of caching strategies for content centric networking[C]// 2015 IEEE Global Communications Conference(GLOBECOM).San Diego,CA:IEEE,2015:1-6.

[5] EUM S, NAKAUCHI K, MURATA M, et al. CATT: potential based routing with content caching for ICN[C]// Proceedings of the second edition of the ICN workshop on Information-centric networking(ICN’12). New York, NY, USA: ACM, 2012: 49-54.

[6] PSARAS I, CHAI W K, AND PAVLOU G. Probabilistic in-network caching for information-centric networks[C]// Proceedings of the second edition of the ICN workshop on Information-centric networking(ICN’2). New York, NY, USA: ACM, 60.

[7] MING Z X, XU M W, AND WANG D. Age-Based cooperative caching in information-centric networks[C]// Computer Communications Workshops. Orlando, FL: IEEE, 2012: 1-8.

[8] CHAI W K, HE D, PSARAS I, et al.. Cache “l(fā)ess for more” in information-centric networks[C]// International Conference on Research in Networking. Berlin, Heidelberg: Springer, 2012: 27-40.

[9] CHO K, LEE M, PARK K, et al.. WAVE: popularity-based and collaborative in-network caching for content-oriented Networks[C]// 2012 Proceedings IEEE INFOCOM Workshops. Orlando, FL: IEEE, 2012: 316-321.

[10] SALAMA H F,REEVES D S,VINIOTIS Y. Evaluation of multicast routing algorithms for real-time communication on high-speed networks[J]. IEEE Journal on Selected Areas in Communications,1997,15(3):332-345.

[11] BACHER F, RAINER B, HELLWAGNER H. Towards controller-aided multimedia dissemination in named data networking[C]// 2015 IEEE International Conference on Multimedia & Expo Workshops(ICMEW). Turin: IEEE, 2015: 1-6.

[12] AOKI M, SHIGEYASU T. Effective content management technique based on cooperation cache among neighboring routers in content-centric networking[C]// 2017 31st International Conference on Advanced Information Networking and Applications Workshops(WAINA). Taipei: IEEE, 2017: 335-340.

[13] ZHANG Z, MA H, LIU L. Cache-aware named-data forwarding in internet of things[C]// 2015 IEEE Global Communications Conference (GLOBECOM). San Diego, CA: IEEE, 2015: 1-6.

[14] KIM D, KO Y B. On-demand anchor-based mobility support method for named data networking[C]// 2017 19th International Conference on Advanced Communication Technology(ICACT).Bongpyeong,South Korea:IEEE,2017:19-23.

(編輯：劉 勇)