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

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

0 概述

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

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

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

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

1 研究現(xiàn)狀

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

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

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

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

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

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

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

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

表1 符號(hào)說明

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

Gain3,k=r3,k×h3,1

(1)

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

2.1 流行度統(tǒng)計(jì)

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

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

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

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

2.2 緩存通告

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

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

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

表2 鄰居緩存信息

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

2.3 路徑緩存決策

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

圖3 興趣包格式

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

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

1.for (對(duì)于每個(gè)興趣包上行請(qǐng)求的沿途節(jié)點(diǎn))

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

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

4. 查詢PIT

5. if存在記錄

6. 在PIT中添加本次請(qǐng)求端口,停止轉(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中查找到被請(qǐng)求內(nèi)容,將該內(nèi)容提供節(jié)點(diǎn)記為g)

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

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

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

20. end if

21.end for

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

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

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

3 仿真與性能分析

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

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

3.2 性能分析

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

1)平均請(qǐng)求延遲

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

(2)

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

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

圖5 平均請(qǐng)求延遲對(duì)比

2)緩存命中率

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

(3)

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

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

圖6 緩存命中率對(duì)比

3)跳數(shù)減少率

(4)

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

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

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

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

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

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

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

(5)

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

(6)

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

(7)

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

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

4 結(jié)束語

為有效利用NDN節(jié)點(diǎn)的緩存空間,提高網(wǎng)絡(luò)服務(wù)性能,本文提出一種基于局部流行度的分布式協(xié)作緩存機(jī)制(LPDCC)。結(jié)合內(nèi)容流行度的局域性,合理評(píng)價(jià)緩存收益,優(yōu)化路徑緩存,通過局部緩存通告,提高節(jié)點(diǎn)緩存利用率。仿真結(jié)果表明,LPDCC能夠獲得較高的緩存命中率,實(shí)現(xiàn)內(nèi)容請(qǐng)求的就近應(yīng)答。下一步工作重點(diǎn)為設(shè)計(jì)面向不同服務(wù)的緩存策略,并將LPDCC擴(kuò)展到移動(dòng)無線網(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] 張國(guó)強(qiáng),李 楊,林 濤,等.信息中心網(wǎng)絡(luò)中的內(nèi)置緩存技術(shù)研究[J].軟件學(xué)報(bào),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] 葛國(guó)棟,郭云飛,劉彩霞等.命名數(shù)據(jù)網(wǎng)絡(luò)中基于局部請(qǐng)求相似性的協(xié)作緩存路由機(jī)制[J].電子與信息學(xué)報(bào),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.