基于局部流行度的分布式協(xié)作緩存策略

房曉陽,季新生,劉彩霞,杜福德

(1.國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,鄭州 450002; 2.65054部隊,大連 116000)

0 概述

據(jù)Cisco預(yù)測,全球網(wǎng)絡(luò)流量的年復(fù)合增長率將達(dá)到22%,而到2020年,視頻流量占所有消費類互聯(lián)網(wǎng)流量的比重將超過82%[1],內(nèi)容獲取已經(jīng)成為互聯(lián)網(wǎng)流量的主導(dǎo)因素。日益增長的對高效內(nèi)容分發(fā)的需求促使基于命名數(shù)據(jù)對象(Named Data Objects,NDOs)的未來網(wǎng)絡(luò)架構(gòu)的研究,這些架構(gòu)一般統(tǒng)稱為信息中心網(wǎng)絡(luò)(Information-Centric Network,ICN)[2]。ICN作為一種革命式的新型網(wǎng)絡(luò)架構(gòu),其首要考慮對象是內(nèi)容本身,而不是內(nèi)容所處位置。在ICN中,網(wǎng)絡(luò)節(jié)點具備緩存能力,用戶請求內(nèi)容時,緩存該內(nèi)容的節(jié)點可以響應(yīng)用戶請求。自Information-Centric的概念提出以來,涌現(xiàn)了很多解決方案,其中,以命名數(shù)據(jù)網(wǎng)絡(luò)(Named Data Network,NDN)[3]最為引人注目,其也是現(xiàn)在主流的ICN架構(gòu)研究范例。

NDN為每個內(nèi)容對象分配全局唯一的名字,在中間層用數(shù)據(jù)名取代IP進行路由[4]。當(dāng)NDN路由器接收到興趣包后,如果內(nèi)容存儲器(Content Store,CS)中有對應(yīng)數(shù)據(jù),則發(fā)送數(shù)據(jù)包響應(yīng)請求。若CS中沒有對應(yīng)數(shù)據(jù),則查詢未決請求表(Pending Interest Table,PIT),如果發(fā)現(xiàn)匹配項,則在對應(yīng)項中添加興趣包進來的接口(Face)。如果PIT中沒有匹配項,則依據(jù)轉(zhuǎn)發(fā)信息庫(Forwarding Information Base,FIB)向內(nèi)容源方向轉(zhuǎn)發(fā)請求,并在PIT中創(chuàng)建新條目。

對于NDN網(wǎng)絡(luò),發(fā)揮網(wǎng)內(nèi)(In-Network)緩存優(yōu)勢的關(guān)鍵是在較小的開銷下,提升緩存效能。而NDN中默認(rèn)的緩存方式為處處緩存 (Leave Copy Everywhere,LCE)[5],即當(dāng)對象返回時,沿途的所有節(jié)點都緩存對象,但這種方式容易造成緩存冗余,即相同的對象在多個節(jié)點同時存有副本,影響了緩存系統(tǒng)的多樣性[6]。而且在路由轉(zhuǎn)發(fā)時,無法感知路徑外(off-path)鄰近節(jié)點的緩存內(nèi)容,導(dǎo)致緩存利用率低。這種無協(xié)作的緩存機制導(dǎo)致緩存冗余、頻繁替換、效率不高。

針對上述問題,本文基于內(nèi)容請求的局部特征,依據(jù)轉(zhuǎn)發(fā)路徑緩存收益及鄰居緩存感知,提出一種分布式協(xié)作緩存機制(LPDCC)。在邊緣路由器周期性地統(tǒng)計內(nèi)容請求速率,并將結(jié)果隨興趣包轉(zhuǎn)發(fā),在請求路徑上依據(jù)緩存收益的比較進行緩存決策。

1 研究現(xiàn)狀

針對NDN網(wǎng)絡(luò)LCE緩存方法的不足,為了提升緩存性能,減少冗余,目前研究人員已經(jīng)提出了一些緩存策略,可以劃分為4類,分別是隨機緩存決策、基于拓?fù)涞木彺鏇Q策、基于標(biāo)簽的緩存決策和基于流行度的緩存決策。

隨機緩存決策中,節(jié)點以某一概率決定是否緩存通過的內(nèi)容。文獻(xiàn)[7]提出了Prob方法,節(jié)點按照固定概率p進行內(nèi)容緩存。文獻(xiàn)[8]提出了RCOne方法,在沿途路徑上隨機選擇某一個節(jié)點進行緩存。文獻(xiàn)[9]提出的HPC是一種逐步將內(nèi)容推向消費者的緩存方法。隨機緩存決策能夠一定程度上降低緩存冗余,但是由于是一種隨機性和盲目性的決策,緩存性能的提升有限。

基于拓?fù)涞木彺鏇Q策依據(jù)節(jié)點的拓?fù)湮恢眠M行緩存。文獻(xiàn)[10]為提高邊緣節(jié)點緩存概率,提出了ProbCache方法,通過計算節(jié)點距離和緩存容量進行緩存決策。文獻(xiàn)[11]提出的Betw方法,在轉(zhuǎn)發(fā)路徑上選擇介數(shù)最高的節(jié)點緩存內(nèi)容副本?；谕?fù)涞木彺鏇Q策提高了緩存針對性,但是沒有考慮內(nèi)容請求的分布特征。

基于標(biāo)簽的緩存決策為每個節(jié)點預(yù)先分配一些標(biāo)簽,節(jié)點只緩存滿足標(biāo)簽條件的特定范圍的內(nèi)容。文獻(xiàn)[12]為每個節(jié)點分配一個正整數(shù),內(nèi)容塊的標(biāo)號經(jīng)過模運算后等于節(jié)點存儲的整數(shù),則進行緩存。文獻(xiàn)[13]提出一種基于Hash的協(xié)作緩存機制,采取的方法是先對網(wǎng)絡(luò)進行分簇,而后在每個簇中使用Hash算法進行緩存分配。這種緩存決策使得內(nèi)容只在特定節(jié)點緩存,內(nèi)容請求定向查找的路徑較長,而且需要集中式的網(wǎng)絡(luò)控制。

基于流行度的緩存決策依據(jù)用戶訪問特征,更多地緩存流行內(nèi)容。文獻(xiàn)[14]提出的WAVE機制,當(dāng)內(nèi)容請求次數(shù)增加時,按照指數(shù)速度增加被緩存的內(nèi)容塊數(shù)量。文獻(xiàn)[15]提出的MPC機制,當(dāng)內(nèi)容請求率達(dá)到設(shè)定的門限,就將該內(nèi)容標(biāo)記為流行內(nèi)容,如果節(jié)點中已經(jīng)緩存了該內(nèi)容,則向鄰居節(jié)點發(fā)送建議緩存的消息,鄰居節(jié)點根據(jù)自身狀態(tài)決定是否緩存該流行內(nèi)容,文獻(xiàn)[16]提出了一種PRL緩存策略,網(wǎng)絡(luò)節(jié)點根據(jù)本地內(nèi)容請求的統(tǒng)計信息計算請求率,并結(jié)合跳數(shù)信息和替換率計算緩存收益,在傳輸路徑中選出收益最大節(jié)點作為緩存節(jié)點,上游節(jié)點會記錄緩存節(jié)點信息,并為后續(xù)內(nèi)容請求執(zhí)行重定向,這種方法會導(dǎo)致頻繁的緩存信息同步,顯著增加網(wǎng)絡(luò)負(fù)載。文獻(xiàn)[17]綜合考慮了垂直請求路徑和水平局域范圍2維空間下的內(nèi)容放置和冗余消除,基于最大內(nèi)容活躍因子確定沿途轉(zhuǎn)發(fā)路徑對應(yīng)的最大熱點請求區(qū)域,但是會引入額外的查找時延。

從上述分析可以看出,基于流行度的緩存決策依據(jù)用戶訪問特征提高緩存內(nèi)容的針對性,使得緩存內(nèi)容更好地響應(yīng)后續(xù)請求,得到了更多關(guān)注。但是現(xiàn)有方法無法避免請求聚合特性(即上游路由器接收到的請求是下游路由器請求聚合后的結(jié)果)[18]對內(nèi)容流行度統(tǒng)計的影響,缺乏實時流行度感知,或者以全局流行度代替局部流行度,忽視了內(nèi)容請求的差異性。

2 基于局部流行度的協(xié)作緩存機制

用無向圖G=(V,E)表示任意網(wǎng)絡(luò)拓?fù)?其中,V={v1,v2,…,vn}表示網(wǎng)絡(luò)中的節(jié)點集合,節(jié)點vi的緩存容量為Ci,E表示鏈路集合。內(nèi)容塊對象分別表示為ok,k=1,2,…。ok所在源節(jié)點為Sk。ri,k為節(jié)點vi處,對內(nèi)容塊ok的請求速率。用hi,k表示從節(jié)點vi到Sk的跳數(shù)。詳細(xì)的符號說明參見表1。

表1 符號說明

LPDCC是一種通過比較緩存收益進行決策的機制,主要思想如圖1所示,用戶發(fā)送Interest包,路由節(jié)點依據(jù)FIB進行轉(zhuǎn)發(fā),假設(shè)在節(jié)點v1命中(hit)緩存,然后系統(tǒng)按相反路徑轉(zhuǎn)發(fā)Data包,途中各節(jié)點將距節(jié)點v1的跳數(shù)與本節(jié)點內(nèi)容流行度相乘,得到緩存收益,通過比較緩存收益進行決策。以節(jié)點v3為例,計算內(nèi)容ok的緩存收益,r3,k=3,h3,1=2,那么緩存收益為:

Gain3,k=r3,k×h3,1

(1)

圖1 內(nèi)容請求示意圖

2.1 流行度統(tǒng)計

由于內(nèi)容數(shù)量很多,而且用戶需求會動態(tài)變化,準(zhǔn)確統(tǒng)計內(nèi)容的全局流行度是很困難的,尤其是在大規(guī)模網(wǎng)絡(luò)中。為此,提出一種局部流行度統(tǒng)計方法,每個節(jié)點根據(jù)自己服務(wù)范圍的內(nèi)容請求情況對內(nèi)容流行度進行劃分。由于不同區(qū)域的關(guān)注點不同,局部的流行度信息相比全局流行度,更能準(zhǔn)確刻畫用戶需求。因為本文將周期性統(tǒng)計的內(nèi)容請求速率作為本地的流行度,在本文中將不再區(qū)分這2個名詞,而是在不同語境中采用不同的名詞。

NDN協(xié)議對Interest包的處理過程中包含如下步驟,當(dāng)在節(jié)點CS中沒有發(fā)現(xiàn)匹配的數(shù)據(jù),則查找PIT,如果在PIT中發(fā)現(xiàn)匹配項,那么把Interest包來源端口(Face)加入PIT表并丟棄,也就是請求聚合的Filter effect[19],這會導(dǎo)致內(nèi)容流行度信息與實際情況差距較大,尤其是對于上游節(jié)點,所接收到的是合并后的內(nèi)容請求信息,無法掌握真實的內(nèi)容請求速率。在本文提出的LPDCC中,為了獲得內(nèi)容流行度信息,所有接入路由器周期性地統(tǒng)計每個內(nèi)容對象的請求速率,并將結(jié)果隨興趣包一起轉(zhuǎn)發(fā)。

圖2給出了請求速率的轉(zhuǎn)發(fā)示意圖,路由節(jié)點中需要建立內(nèi)容流行度表(Local Popularity Table,LPT)用于存儲統(tǒng)計結(jié)果。圖2顯示了最近一次請求速率統(tǒng)計結(jié)果,r4,1=3表示在節(jié)點v4對內(nèi)容o1的請求速率為3。這些結(jié)果隨興趣包向上游節(jié)點轉(zhuǎn)發(fā),上游節(jié)點接收后,記錄內(nèi)容ID、來源端口、流行度信息。這樣可以在不增加網(wǎng)絡(luò)負(fù)載的情況下獲取本地內(nèi)容流行度信息。在內(nèi)容流行度表中之所以要區(qū)分端口是因為如果下游節(jié)點發(fā)送的流行度信息變化后,需要在對應(yīng)接口記錄中進行更新。如果在下個統(tǒng)計周期,r4,1=2,那么v2中(內(nèi)容1,端口a)對應(yīng)的流行度為2,v2中內(nèi)容1總的流行度為4。

圖2 請求速率轉(zhuǎn)發(fā)示意圖

2.2 緩存通告

由于內(nèi)容對象數(shù)量多,而且已緩存內(nèi)容有可能會被替換。如果將節(jié)點的緩存內(nèi)容在全網(wǎng)或者較大范圍內(nèi)進行通告,將加劇網(wǎng)絡(luò)負(fù)載。尤其是對于一些緩存收益較低的內(nèi)容,由于緩存的駐留時間(Time To Live,TTL)短,緩存通告的信息容易失效,將導(dǎo)致請求重發(fā),增加延遲。為此,需要選擇相對穩(wěn)定的緩存條目進行通告。

由于采用了基于緩存收益的決策方式,內(nèi)容的緩存收益越大,在節(jié)點中的駐留概率越大,因此依據(jù)內(nèi)容緩存收益的大小進行局域通告,增加內(nèi)容可用性。按照節(jié)點CS中內(nèi)容的緩存收益將其劃分為3個等級:一是高收益內(nèi)容,在進行通告時,優(yōu)先保證可用性;二是一般收益內(nèi)容;三是低收益內(nèi)容,不進行通告,減小網(wǎng)絡(luò)開銷。對于不同等級的內(nèi)容,通告范圍的設(shè)置也不同。等級越低,TTL越小,可用性較低,應(yīng)設(shè)置比較小的通告范圍?？梢詫⒕彺媸找嬖谇?0%的內(nèi)容定義為第一等級,通告范圍設(shè)為2跳;緩存收益在10%～ 30%的內(nèi)容定義為第二等級,通告范圍為1跳;其余內(nèi)容可用性低,不進行鄰域通告。

節(jié)點收到鄰居節(jié)點的緩存內(nèi)容通告后,建立鄰居緩存信息表(Neighbor Content Table,NCT),如表2所示,其中跳數(shù)是指當(dāng)前節(jié)點與內(nèi)容提供節(jié)點之間的跳數(shù)。

表2 鄰居緩存信息

當(dāng)某項內(nèi)容在NCT中存在多個條目時,則從中選擇跳數(shù)最小的接口進行轉(zhuǎn)發(fā)。由于依據(jù)NCT進行轉(zhuǎn)發(fā)后,可能存在目的節(jié)點內(nèi)容已經(jīng)被替換的可能,在這種情況下,可以將請求通過NCT源節(jié)點進行再次轉(zhuǎn)發(fā)。

2.3 路徑緩存決策

為了比較緩存收益,需要流行度和跳數(shù)信息,而由于節(jié)點內(nèi)容的流行度會由于子節(jié)點的緩存決策而變化,為了不增加請求應(yīng)答的時間,在興趣包轉(zhuǎn)發(fā)過程中收集沿途節(jié)點信息。為此,在興趣包中增加字段用于收集必要信息。增加的請求內(nèi)容流行度字段用于2.1節(jié)闡述的流行度轉(zhuǎn)發(fā)和更新;增加的沿途節(jié)點信息字段包含沿途節(jié)點ID、待替換內(nèi)容ID、待替換內(nèi)容收益、當(dāng)前請求內(nèi)容在沿途節(jié)點的流行度以及節(jié)點與內(nèi)容源之間的跳數(shù)。興趣包的報文格式如圖3所示。

圖3 興趣包格式

在興趣包中添加的字段用灰色表示,分別是請求內(nèi)容流行度和沿途節(jié)點信息,其他字段和NDN中的興趣包相同。沿途節(jié)點接收到興趣包后首先依據(jù)內(nèi)容流行度更新本節(jié)點CS表信息。沿途節(jié)點每轉(zhuǎn)發(fā)一次就添加一項沿途節(jié)點信息,其中待替換內(nèi)容是指節(jié)點CS中緩存收益最小的內(nèi)容,收益是指待替換內(nèi)容的緩存收益,流行度是指當(dāng)前節(jié)點處被請求內(nèi)容的流行度。跳數(shù)的初始值為1,每經(jīng)過一次轉(zhuǎn)發(fā)節(jié)點就加1。興趣包轉(zhuǎn)發(fā)過程見算法1。

算法1興趣包轉(zhuǎn)發(fā)算法(用戶請求內(nèi)容oj)

1.for (對于每個興趣包上行請求的沿途節(jié)點)

2. 依據(jù)興趣包中流行度更新rk,j(當(dāng)前節(jié)點vk處內(nèi)容oj的流行度)

3. if CS中不存在被請求內(nèi)容then

4. 查詢PIT

5. if存在記錄

6. 在PIT中添加本次請求端口,停止轉(zhuǎn)發(fā)

7. else

8. 更新興趣包

9. 查詢NC

10. if存在記錄

11. 依據(jù)NCT轉(zhuǎn)發(fā)

12. else

13. 依據(jù)FIB轉(zhuǎn)發(fā)

14. end if

15. end if

16. else(CS中查找到被請求內(nèi)容,將該內(nèi)容提供節(jié)點記為g)

17. 執(zhí)行緩存決策算法

18. 從請求端口轉(zhuǎn)發(fā)數(shù)據(jù)包

19. 停止興趣包轉(zhuǎn)發(fā)

20. end if

21.end for

更新興趣包是指:1)更新被請求內(nèi)容的流行度;2)興趣包沿途節(jié)點信息字段中已有條目的跳數(shù)加1;3)從當(dāng)前節(jié)點CS中選出緩存收益最低的內(nèi)容,標(biāo)記為待替換內(nèi)容,在興趣包中添加其內(nèi)容名、收益,跳數(shù)初始化為1。

圖4為興趣包轉(zhuǎn)發(fā)過程示意圖,用戶請求內(nèi)容oj,在節(jié)點v7處首先更新流行度表,假設(shè)v7沒有緩存該內(nèi)容,且PIT中也沒有對應(yīng)記錄。那么v7從CS中選出緩存收益最低的內(nèi)容,假設(shè)是oq(緩存收益為4),將對應(yīng)信息寫入興趣包,然后繼續(xù)轉(zhuǎn)發(fā)。后續(xù)的轉(zhuǎn)發(fā)處理過程類似,經(jīng)過v7時,將興趣包中v7的跳數(shù)信息加1。這樣,當(dāng)興趣包到達(dá)內(nèi)容提供節(jié)點時,就能夠獲取沿途節(jié)點的待替換內(nèi)容信息,以及各節(jié)點距內(nèi)容提供節(jié)點的跳數(shù)。當(dāng)興趣包到達(dá)內(nèi)容提供節(jié)點后,在該節(jié)點執(zhí)行緩存決策過程,見算法2。然后將決策結(jié)果隨數(shù)據(jù)包轉(zhuǎn)發(fā),沿途節(jié)點接收到數(shù)據(jù)包后依據(jù)相應(yīng)決策結(jié)果決定是否緩存該內(nèi)容,并更新本地流行度。在內(nèi)容提供節(jié)點處的緩存決策算法中,vi表示用戶接入節(jié)點,g表示內(nèi)容提供節(jié)點。

算法2緩存決策算法

1.rj=0

2.for vk∈Path(vi,g)

3. rk,j= rk,j-rj

4. if rk,j×hk,g-Gain>0

5. Caching Decision = TRUE

6. rj= rj+rk,j

7. else

8. Caching Decision = FALSE

9. end if

10.end for

圖4 興趣包轉(zhuǎn)發(fā)過程示意圖

以圖4中的情況為例,在節(jié)點v1處執(zhí)行緩存決策算法,rj初始化為0。首先判斷是否在v7處緩存,由于r7,j=3,h7,g=2,Gainq=4,那么在v7處,內(nèi)容oj的收益比待替換內(nèi)容oq要大,所以在v7緩存內(nèi)容oj。這時,rj更新為3,在判斷v3的緩存決策時,由于v3的子節(jié)點v7將會緩存內(nèi)容oj,后續(xù)在v7處對內(nèi)容oj的請求將由v7應(yīng)答,不會轉(zhuǎn)發(fā)給v3,因此v3處內(nèi)容oj的流行度要減去r7,j(即當(dāng)前rj的值)。因此,r3,j=4,h3,g=1,Gainp=5,經(jīng)過計算決定不在節(jié)點v3處緩存內(nèi)容oj。通過算法2得到緩存結(jié)果后,將該結(jié)果隨數(shù)據(jù)包下發(fā)?？梢钥闯?按照算法2進行緩存決策,當(dāng)子節(jié)點決定緩存當(dāng)前請求內(nèi)容時,可以及時更新父節(jié)點流行度,對緩存收益的評價更加合理,能夠優(yōu)化緩存位置。

3 仿真與性能分析

3.1 仿真環(huán)境與參數(shù)設(shè)置

本文通過ndnSIM進行仿真,這是一種基于NS3的NDN仿真工具,已經(jīng)實現(xiàn)了所有的NDN的基本協(xié)議操作,并且支持用戶自定義緩存和轉(zhuǎn)發(fā)策略。使用NS3提供的GT-ITM生成50個節(jié)點的隨機網(wǎng)絡(luò)拓?fù)?并隨機選擇3個節(jié)點作為內(nèi)容源服務(wù)器,其余節(jié)點作為接入節(jié)點。網(wǎng)絡(luò)中共有10 000個大小相同的內(nèi)容,內(nèi)容大小設(shè)置為相同,每個內(nèi)容劃分為100個內(nèi)容塊,每個內(nèi)容塊的大小設(shè)為10 kB。每個節(jié)點的緩存容量設(shè)為相同,節(jié)點間鏈路帶寬設(shè)置為100 Mb/s。節(jié)點的內(nèi)生請求達(dá)到率符合參數(shù)為λ的泊松過程,內(nèi)容請求概率符合參數(shù)為α的Zipf分布。在初始狀態(tài),節(jié)點緩存為空,沒有存儲任何內(nèi)容副本。

3.2 性能分析

從平均請求延遲、緩存命中率、跳數(shù)減少率和業(yè)務(wù)開銷4個方面,將本文提出的LPDCC與LCE[5]、ProbCache[10]、PRL[16]進行對比分析。

1)平均請求延遲

請求延遲是指從請求內(nèi)容到收到數(shù)據(jù)包之間的時間延遲,網(wǎng)絡(luò)中所有內(nèi)容請求延遲的平均值定義為平均請求延遲ξ(t):

(2)

其中,Q指網(wǎng)絡(luò)中所有內(nèi)容請求,ωr(t)指單次內(nèi)容請求的延遲。

如圖5所示,在節(jié)點緩存容量為200 MB,λ為每移動30個的情況下,Zipf參數(shù)分別為α=1.0和α=1.2時的平均延遲。從系統(tǒng)初始狀態(tài)開始,按照順序進行了200 s的仿真,每隔2 s統(tǒng)計一次平均延遲。由于在初始狀態(tài)下,網(wǎng)絡(luò)節(jié)點中沒有緩存任何內(nèi)容,所有請求都被轉(zhuǎn)發(fā)到內(nèi)容源服務(wù)器,平均延遲較大。隨著系統(tǒng)運行,網(wǎng)絡(luò)節(jié)點緩存內(nèi)容逐漸增加,用戶可以就近獲得所需內(nèi)容,平均延遲變小,隨后達(dá)到穩(wěn)定狀態(tài)。由于LCE采取泛濫式緩存,節(jié)點內(nèi)容頻繁更替,且無法利用路徑外緩存,平均延遲最大。ProbCache沒有考慮內(nèi)容流行度的差異,不能確保高流行度內(nèi)容的緩存駐留概率。對于PRL,由于沒有考慮Filter effect的影響,導(dǎo)致延遲增加。而LPDCC依據(jù)內(nèi)容的緩存收益合理確定緩存節(jié)點,選擇駐留概率高的內(nèi)容進行通告,提升緩存利用率,從而顯著降低平均延遲。

圖5 平均請求延遲對比

2)緩存命中率

緩存命中率ψ(t)定義為用戶請求被節(jié)點緩存應(yīng)答的比率:

(3)

其中,δr(t)為0表示在內(nèi)容源獲得響應(yīng),為1表示在路由節(jié)點命中緩存。緩存命中率越高,用戶就近獲取內(nèi)容的可能性越大,源服務(wù)器和網(wǎng)絡(luò)負(fù)載越小,也就表明系統(tǒng)的緩存性能更好。

圖6給出在節(jié)點緩存容量為200 MB,α=1.2時,請求到達(dá)率分別為λ=20和λ=30情況下的緩存命中率。由于LCE的處處緩存,鏈路上存儲了大量相同的內(nèi)容,緩存多樣性不足,導(dǎo)致緩存命中率很低。ProbCache沒有利用路徑外緩存,也會造成很多內(nèi)容請求被轉(zhuǎn)發(fā)到內(nèi)容源服務(wù)器。PRL采取盲目式的緩存通告,增加了緩存缺少概率。LPDCC通過節(jié)點協(xié)作,保證了節(jié)點間緩存內(nèi)容的差異性,增加了緩存命中率。

圖6 緩存命中率對比

3)跳數(shù)減少率

(4)

圖7給出了跳數(shù)減少率隨α的變化趨勢。當(dāng)α較小時,內(nèi)容流行度不集中,能夠在節(jié)點緩存空間常駐的內(nèi)容少,內(nèi)容替換頻繁,后續(xù)請求較難通過節(jié)點緩存滿足,縮短內(nèi)容獲取路徑的效果不明顯,跳數(shù)減少率低。隨著α的變大,內(nèi)容請求更加集中,熱點內(nèi)容駐留概率大,由于LPDCC能夠充分利用內(nèi)容流行度的局域性特征,性能優(yōu)于其他方案。

圖7 跳數(shù)減少率隨α的變化

圖8給出了跳數(shù)減少率隨節(jié)點緩存容量的變化趨勢。當(dāng)節(jié)點緩存空間很小時,能夠緩存的內(nèi)容很少,大部分內(nèi)容請求需要轉(zhuǎn)發(fā)到內(nèi)容源服務(wù)器,跳數(shù)減少率都比較低。從圖8可以看出,隨著節(jié)點緩存空間的增加,可以在中間節(jié)點上緩存更多內(nèi)容,4種方案的跳數(shù)減少率都在增加。LPDCC與其他3種方案相比,性能提升比較穩(wěn)定。這是因為LPDCC依據(jù)緩存收益,提高緩存可用性,從而能夠更快地相應(yīng)內(nèi)容請求,減少路由跳數(shù)。

圖8 跳數(shù)減少率隨緩存容量的變化

4)業(yè)務(wù)開銷

與LCE相比,ProbCache、PRL和LPDCC為了提高緩存利用率都引入了顯式協(xié)作開銷。主要包含以下幾部分:通告開銷,節(jié)點存儲開銷,內(nèi)容請求開銷。

通告開銷(CA):在構(gòu)建NCT表過程中,選擇相對穩(wěn)定的緩存條目進行通告,引入了緩存狀態(tài)通告開銷。單次緩存通告的開銷為通告報文大小(bit)與傳輸跳數(shù)(hop)的乘積。以fA表示通告頻率,SA1表示首跳通告報文大小,d1為對應(yīng)跳數(shù)。鄰居節(jié)點收到SA1后,將報文中的通告范圍減去1,并刪掉通告范圍為0的條目,獲得下一跳通告報文SA2,d2為對應(yīng)SA2的跳數(shù)。按上述方式類推,到最大通告范圍m跳后,報文中的內(nèi)容清空,通告結(jié)束。

(5)

節(jié)點存儲開銷(CC):由于節(jié)點需要額外存儲流行度表(LPT)和鄰居緩存信息表(NCT),增加了存儲開銷。LPT表需要記錄內(nèi)容名、端口、流行度信息,而NCT表需要記錄內(nèi)容名、端口、跳數(shù)信息。因此,節(jié)點存儲開銷是表中記錄各項信息所占空間的大小(bit)。分別用lc、lf、lp、lh表示內(nèi)容名、端口、流行度、跳數(shù)信息的長度,n1和n2分別表示流行度表和鄰居緩存信息表的存儲數(shù)量。

(6)

內(nèi)容請求開銷(CR):定義為內(nèi)容請求和應(yīng)答過程中產(chǎn)生的開銷,即興趣包和數(shù)據(jù)包的大小(bit)與傳輸距離(hop)的乘積。分別用Si和Sd表示興趣包和數(shù)據(jù)包的大小,dr為第r次請求應(yīng)答的傳輸距離。

(7)

表3為4種緩存機制的開銷對比。統(tǒng)計時間為5 s,λ=30,α=1.2。LCE只是簡單地進行處處緩存,沒有通告開銷和節(jié)點存儲開銷。但是LCE無法利用路徑外緩存,并且路徑緩存的替換率高,內(nèi)容請求開銷最大。ProbCache只需要收集沿途節(jié)點的緩存空間信息,通告開銷和節(jié)點存儲開銷都較小,但和LCE一樣,無法利用路徑外緩存。PRL策略采取了一種盲目的節(jié)點通告方式,通告開銷大,卻不能保證通告的有效性,導(dǎo)致內(nèi)容請求開銷仍然較大。LPDCC 只通告駐留概率大的緩存內(nèi)容,并且利用興趣包轉(zhuǎn)發(fā)過程進行流行度更新,引入了少量通告開銷。由于需要在節(jié)點中維護LPT和NCT表,節(jié)點存儲開銷較大。但從內(nèi)容請求開銷的比較中,可以看出LPDCC能夠增加內(nèi)容請求的就近應(yīng)答率,使得開銷明顯下降。

表3 業(yè)務(wù)開銷對比

4 結(jié)束語

為有效利用NDN節(jié)點的緩存空間,提高網(wǎng)絡(luò)服務(wù)性能,本文提出一種基于局部流行度的分布式協(xié)作緩存機制(LPDCC)。結(jié)合內(nèi)容流行度的局域性,合理評價緩存收益,優(yōu)化路徑緩存,通過局部緩存通告,提高節(jié)點緩存利用率。仿真結(jié)果表明,LPDCC能夠獲得較高的緩存命中率,實現(xiàn)內(nèi)容請求的就近應(yīng)答。下一步工作重點為設(shè)計面向不同服務(wù)的緩存策略,并將LPDCC擴展到移動無線網(wǎng)絡(luò)中。

[1] Cisco. Visual networking index:forecast and methodology,2015-2020[EB/OL].[2016-08-11].http://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/complete-white-paper-c11-481360.pdf.

[2] TROSSEN D,SARELA M,SOLLINS K.Arguments for an information-centric internetworking architecture[J].ACM SIGCOMM Computer Communications Review,2010,40(2):26-33.

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

[4] IOANNOU A,WEBER S.A survey of caching policies and forwarding mechanisms in information-centric networking[J].IEEE Communications Surveys & Tutorials,2016,18(4):2847-2886.

[5] WANG Wei,SUN Yi,GUO Yang,et al.CRCache:exploiting the correlation between content popularity and network topology information for ICN caching[C]//Proceedings of IEEE International Conference on Communications.Washington D.C.,USA:IEEE Press,2014:3191-3196.

[6] 張國強,李 楊,林 濤,等.信息中心網(wǎng)絡(luò)中的內(nèi)置緩存技術(shù)研究[J].軟件學(xué)報,2014,25(1):154-175.

[7] LAOUTARIS N,SYNTILA S,STAVRAKAKIS I.Meta algorithms for hierarchical web caches[C]//Proceedings of Performance,Computing,and Communica-tions.USA:IEEE Press,2004:445-452.

[8] EUM S,NAKAUCHI K,MURATA M,et al.CATT:potential based routing with content caching for ICN[C]//Proceedings of ACM Proceedings of the ICN Workshop on Information-centric Networking.New York,USA:ACM Press,2012:49-54.

[9] WANG Yu,XU Mingwei,FENG Zhen.Hop-based pro-babilistic caching for information-centric networks[C]//Proceedings of IEEE Global Communications Conference.Washington D.C.,USA:IEEE Press,2013:2102-2107.

[10] PSARAS I,CHAI W K,PAVLOU G.Probabilistic in-network caching for information-centric networks[C]//Proceedings of the ICN Workshop on Information-centric Networking.New York,USA:ACM Press,2012:55-60.

[11] CHAI W K,HE Diliang,PSARAS I,et al.Cache “l(fā)ess for more” in information-centric networks[J].Computer Communications,2013,36(7):758-770.

[12] LI Zhe,SIMON G.Time-shifted TV in content centric networks:the case for cooperative in-network caching[C]//Proceedings of ICC’11.Washington D.C.,USA:IEEE Press,2011:1-6.

[13] SOURLAS V,PSARAS I,SAINO L,et al.Efficient hash-routing and domain clustering techniques for information-centric networks[J].Computer Networks,2016,103:67-83.

[14] CHO K,LEE M,PARK K,et al.Wave:popularity-based and collaborative in-network caching for content-oriented networks[C]//Proceedings of IEEE Computer Com-munications Workshops.Washington D.C.,USA:IEEE Press,2012:316-321.

[15] BERNARDINI C,SILVERSTON T,FESTOR O.MPC:IEEE Popularity-based caching strategy for content centric networks[C]//Proceedings of IEEE International Conference on Communications.Washington D.C.,USA:IEEE Press,2013:3619-3623.

[16] HU Xiaoyan,GONG Jian,CHENG Guang,et al.Enhancing in-network caching by coupling cache placement,replacement and location[C]//Proceedings of IEEE International Conference on Communications.Washington D.C.,USA:IEEE Press,2015:5672-5678.

[17] 葛國棟,郭云飛,劉彩霞等.命名數(shù)據(jù)網(wǎng)絡(luò)中基于局部請求相似性的協(xié)作緩存路由機制[J].電子與信息學(xué)報,2015,37(2):435-442.

[18] JIA Zixiao,ZHANG Peng,HUANG Jiwei,et al.Modeling hierarchical caches in content-centric networks[C]//Proceedings of IEEE International Conference on Computer Communications and Networks.Washington D.C.,USA:IEEE Press,2013:1-7.

[19] FENG Bohao,ZHOU Huachun,ZHANG Hongke,et al.A popularity-based cache consistency mechanism for information-centric networking[C]//Proceedings of Global Communications Conference.Washington D.C.,USA:IEEE Press,2016:1-6.