基于內(nèi)容流行度和節(jié)點(diǎn)中心度匹配的信息中心網(wǎng)絡(luò)緩存策略

芮蘭蘭　　彭　昊　　黃豪球　　邱雪松　　史瑞昌(北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室　北京　100876)

?

基于內(nèi)容流行度和節(jié)點(diǎn)中心度匹配的信息中心網(wǎng)絡(luò)緩存策略

芮蘭蘭彭昊*黃豪球邱雪松史瑞昌
(北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室北京100876)

摘要：在信息中心網(wǎng)絡(luò)(Information-Centric Network，ICN)中，利用網(wǎng)絡(luò)內(nèi)置緩存提高內(nèi)容獲取及傳輸效率是該網(wǎng)絡(luò)構(gòu)架最重要的特性。然而，網(wǎng)絡(luò)內(nèi)置的緩存存在應(yīng)對大量的需要轉(zhuǎn)發(fā)的內(nèi)容時(shí)能力相對弱小，對內(nèi)容放置缺乏均衡分布的問題。該文提出基于內(nèi)容流行度和節(jié)點(diǎn)中心度匹配的緩存策略(Popularity and Centrality Based Caching Scheme，PCBCS)，通過對經(jīng)過的內(nèi)容進(jìn)行選擇性緩存來提高內(nèi)容分發(fā)沿路節(jié)點(diǎn)的緩存空間使用效率，減少緩存冗余。仿真結(jié)果表明，該文提出的算法和全局沿路緩存決策方案，LCD(Leave Copy Down)以及參數(shù)為0.7 及0.3的Prob(copy with Probability)相比較，在服務(wù)器命中率上平均減少30%，在命中緩存內(nèi)容所需的跳數(shù)上平均減少20%，最重要的是，和全局沿路緩存決策方案相比總體緩存替換數(shù)量平均減少了40%。

關(guān)鍵詞：信息中心網(wǎng)絡(luò)；緩存網(wǎng)絡(luò)；緩存決策策略；時(shí)空局部性

1　引言

信息中心網(wǎng)絡(luò)(Information-Centric Network，ICN)是以信息/內(nèi)容為中心的新型網(wǎng)絡(luò)構(gòu)架的統(tǒng)稱，典型的構(gòu)架如DONA(Data-Oriented Network of Information)，CCN(Content-Centric Network)，NetInf(Network of Information)等，這些網(wǎng)絡(luò)構(gòu)架將傳統(tǒng)的主機(jī)中心模型轉(zhuǎn)為更加靈活的數(shù)據(jù)中心模型[1]。區(qū)別于傳統(tǒng)的IP網(wǎng)絡(luò)，ICN網(wǎng)絡(luò)對內(nèi)容進(jìn)行統(tǒng)一標(biāo)識命名，并基于內(nèi)容進(jìn)行定位尋址、路由傳輸，同時(shí)賦予具備緩存能力的網(wǎng)絡(luò)設(shè)備(比如ICN路由器)緩存可尋址內(nèi)容的能力。之后，被命名的內(nèi)容項(xiàng)在從源地址到目的地址的傳輸過程中被ICN路由器唯一識別并被緩存，隨后ICN路由器能夠?qū)⑵滢D(zhuǎn)發(fā)給對這些相同內(nèi)容感興趣并發(fā)起請求的其他用戶。因此，在緩存系統(tǒng)中采用哪種策略在哪些節(jié)點(diǎn)緩存哪些內(nèi)容，即緩存決策策略(cache resolution scheme)的優(yōu)劣很大程度的影響內(nèi)容獲取的效率，是ICN緩存研究的重要方向。對內(nèi)容項(xiàng)的緩存是ICN架構(gòu)的基礎(chǔ)，以至于許多論文中都使用緩存網(wǎng)絡(luò)來指代ICN[2]，可見緩存以及緩存研究對ICN網(wǎng)絡(luò)的重要意義。

在緩存決策策略的研究方向上，文獻(xiàn)[3，4]提出了協(xié)同沿路徑緩存(Cooperative En-Route Web Caching，CERC)為代表的顯式協(xié)同緩存決策策略，CERC策略考慮緩存節(jié)點(diǎn)的狀態(tài)以及內(nèi)容的請求頻率來計(jì)算內(nèi)容緩存的最優(yōu)位置，但是由于需要通過復(fù)雜的信息交互以及計(jì)算才能做出決策，對于要求線性速度執(zhí)行的ICN網(wǎng)絡(luò)過于復(fù)雜，于是LCD(Leave Copy Down)，Prob(copy with Probability)，ProbCache[5]和使用加強(qiáng)計(jì)數(shù)器的機(jī)會(huì)緩存策略等節(jié)點(diǎn)相互交互信息量少，自主性強(qiáng)的隱式協(xié)同緩存決策被提出。以下簡要介紹本文加以對比的及幾種緩存決策策略。

(1)LCD(Leave Copy Down)：當(dāng)緩存命中時(shí)，僅在命中節(jié)點(diǎn)的下游節(jié)點(diǎn)緩存該內(nèi)容，避免了同一內(nèi)容的大量復(fù)制，并且需要多次對某一內(nèi)容的請求才會(huì)將該內(nèi)容復(fù)制到靠近客戶端的地方，潛在地考慮了內(nèi)容的訪問頻率。

(2)Prob(copy with Probability)：每個(gè)沿途節(jié)點(diǎn)都以概率p緩存內(nèi)容項(xiàng)，而以概率1-p不緩存內(nèi)容項(xiàng)，p的值可以依據(jù)緩存情況進(jìn)行調(diào)整。該方法可以認(rèn)為是全局沿路緩存的一般化，當(dāng)p=1時(shí)，即退化為全局沿路緩存。

(3)全局沿路緩存策略：研究者致力于改進(jìn)并加以對比的全局沿路緩存方法是使用在大部分現(xiàn)存ICN提議框架的緩存決策策略，該策略最近被命名為TERC(Transparent En-Route Caching)[2]，是許多ICN結(jié)構(gòu)(如CCN)的默認(rèn)緩存決策策略，該方法中網(wǎng)絡(luò)中的內(nèi)容路由器參與內(nèi)容緩存過程同時(shí)也具有對目標(biāo)中繼下行轉(zhuǎn)發(fā)的功能，但當(dāng)內(nèi)容返回給請求者時(shí)，沿途的所有內(nèi)容路由器都緩存該內(nèi)容，本質(zhì)上沒有協(xié)同機(jī)制。這個(gè)策略引發(fā)了很多爭議，許多論文都指出了該方法的缺點(diǎn)[6-10]，證明其效率低下。因?yàn)門ERC強(qiáng)迫路由器緩存所有經(jīng)過的內(nèi)容，不僅在系統(tǒng)緩存空間有限的情況下，影響內(nèi)容的多樣性；而且會(huì)導(dǎo)致更多的沿路內(nèi)容替換。解決TERC方法的盲目性的弊端，減少重復(fù)緩存，提出更優(yōu)的緩存決策策略是目前ICN研究的一個(gè)重點(diǎn)方向。

ICN網(wǎng)絡(luò)總體緩存空間是有限的，有限的緩存空間最好被用來容納更多的特有數(shù)據(jù)而不是重復(fù)數(shù)據(jù)，一個(gè)內(nèi)容項(xiàng)存在大量副本不是一個(gè)很好的選擇；其次，以全局沿路緩存為代表的全局性緩存會(huì)導(dǎo)致大量的緩存替換，增加緩存節(jié)點(diǎn)的負(fù)載。所以本文致力于對全局沿路緩存決策策略進(jìn)行改進(jìn)，并提出了基于流行度以及中心度的PCBCS(Popularity and Centrality Based Caching Scheme)緩存策略，同時(shí)仿真試驗(yàn)中采用對內(nèi)容請求加入局部性原理后建立的模型，最大程度保證對PCB策略驗(yàn)證的準(zhǔn)確性以及真實(shí)性。

緩存決策的重點(diǎn)是處理兩個(gè)普遍度量即副本數(shù)與更有效的緩存分配的矛盾關(guān)系，權(quán)衡整體系統(tǒng)內(nèi)容獲取效率與網(wǎng)絡(luò)資源利用率。本文在ICN網(wǎng)絡(luò)緩存研究的創(chuàng)新點(diǎn)如下：

(1)提出同時(shí)基于內(nèi)容流行度與節(jié)點(diǎn)中心度的緩存決策策略，解決ICN結(jié)構(gòu)默認(rèn)緩存決策策略盲目性所造成的緩存冗余的問題，提高了緩存系統(tǒng)的內(nèi)容多樣性。

(2)將內(nèi)容與節(jié)點(diǎn)進(jìn)行排名匹配，在整個(gè)系統(tǒng)實(shí)現(xiàn)了更合理的資源分配，提高了緩存系統(tǒng)的整體效用。

(3)分析論證時(shí)考慮緩存網(wǎng)絡(luò)在時(shí)間和空間領(lǐng)域上展現(xiàn)出的強(qiáng)大的關(guān)聯(lián)關(guān)系，加入局部性因素，摒棄僅采用傳統(tǒng)的外生請求到達(dá)模型即獨(dú)立參考模型假設(shè)的方法，而是結(jié)合請求關(guān)聯(lián)性模型進(jìn)行建模分析。

本文第2節(jié)闡述ICN結(jié)構(gòu)的層級式緩存模型并提出PCBCS方法；第3節(jié)對PCBCS方法進(jìn)行實(shí)證性分析，給出性能對比結(jié)果；第4節(jié)為結(jié)束語。

2　PCBCS

本文提出基于內(nèi)容流行度與節(jié)點(diǎn)中心度的緩存決策策略，并對緩存網(wǎng)絡(luò)采用層級式拓?fù)浣Y(jié)構(gòu)進(jìn)行建模。

2.1 層級式緩存模型

建立由層級式緩存節(jié)點(diǎn)組成的樹，如圖1所示。樹的根作為內(nèi)容源，假設(shè)源存儲(chǔ)系統(tǒng)中存儲(chǔ)了所有內(nèi)容項(xiàng)的永久備份。

樹結(jié)構(gòu)有L+2層。內(nèi)容訂閱者(content subscriber比如用戶或者內(nèi)容項(xiàng)請求者)在第0層，內(nèi)容源位于L+1層(圖中根節(jié)點(diǎn)與內(nèi)容源相連，路由可達(dá))。中間有L層緩存節(jié)點(diǎn)，其都有緩存能力及路由轉(zhuǎn)發(fā)能力且處于用戶和內(nèi)容源之間，這些節(jié)點(diǎn)的度(即與其相連的鏈路個(gè)數(shù))并不相同，但每個(gè)節(jié)點(diǎn)都有相同的緩存空間大小C。系統(tǒng)中所有內(nèi)容請求都由第0層的用戶節(jié)點(diǎn)發(fā)出，并首先被位于最底層的緩存節(jié)點(diǎn)(即第1層的節(jié)點(diǎn))接收，當(dāng)請求在本層無法得到滿足(即緩存未命中)時(shí)，本層的緩存節(jié)點(diǎn)將請求繼續(xù)轉(zhuǎn)發(fā)給上層的緩存節(jié)點(diǎn)，直至轉(zhuǎn)發(fā)至根節(jié)點(diǎn)，在根節(jié)點(diǎn)命中。請求得到響應(yīng)后，內(nèi)容項(xiàng)數(shù)據(jù)包將會(huì)沿著請求路徑原路返回，并根據(jù)相應(yīng)策略在整個(gè)緩存系統(tǒng)進(jìn)行沿途復(fù)制。模型中，請求只產(chǎn)生于用戶節(jié)點(diǎn)，其他上層的緩存節(jié)點(diǎn)不會(huì)產(chǎn)生請求，它們只會(huì)在緩存未命中時(shí)向上層轉(zhuǎn)發(fā)請求。

圖1　層級式緩存模型拓?fù)鋱D

2.2 外生請求到達(dá)模型

外生請求是指由第0層的用戶節(jié)點(diǎn)發(fā)出的內(nèi)容請求，中間緩存節(jié)點(diǎn)未命中而向上層節(jié)點(diǎn)轉(zhuǎn)發(fā)的請求不屬于外生請求。

首先對內(nèi)容項(xiàng)a在特定節(jié)點(diǎn)是否能夠緩存命中的概率進(jìn)行計(jì)算，即先考慮外生請求到達(dá)模型應(yīng)用在獨(dú)立緩存的情況。表1給出了緩存網(wǎng)絡(luò)建模用到的符號及其含義。

假設(shè)一個(gè)包含總共N個(gè)內(nèi)容項(xiàng)的系統(tǒng)和一個(gè)擁有容量為C的緩存節(jié)點(diǎn)，該節(jié)點(diǎn)采用LRU[11]最近最少使用緩存替代策略，對內(nèi)容項(xiàng)a的請求符合概率q(a)的泊松過程。事實(shí)上q(a)也表示系統(tǒng)中內(nèi)容項(xiàng)a的流行度，即所有對內(nèi)容項(xiàng)a的請求占所有請求的比例。內(nèi)容項(xiàng)a越流行，q(a)的數(shù)值越高。定義緩存大小為C的緩存節(jié)點(diǎn)的時(shí)間參量tc，tc的含義是在IRM假設(shè)下C大小的緩存空間被遵照請求概率q(·)的內(nèi)容項(xiàng)填滿所需花費(fèi)的時(shí)間為

表1　緩存網(wǎng)絡(luò)建模符號及其含義

tc是式(1)唯一的根，求解出tc，那么對內(nèi)容項(xiàng)a請求到達(dá)緩存節(jié)點(diǎn)后未命中的概率為

以上求解對獨(dú)立緩存的未命中率進(jìn)行了高度準(zhǔn)確的建模，避免了誤差聚集造成連鎖反應(yīng)[12]，提高了實(shí)驗(yàn)的準(zhǔn)確性。那么對于由M個(gè)獨(dú)立緩存組成的樹形結(jié)構(gòu)拓?fù)?，樹中任意?jié)點(diǎn)的度即等于該節(jié)點(diǎn)代表的路由器在網(wǎng)絡(luò)中的度，l層r路由器節(jié)點(diǎn)的度表示為，對內(nèi)容項(xiàng)的請求到達(dá)緩存節(jié)點(diǎn)服從獨(dú)立同分布過程。那么對內(nèi)容項(xiàng)a的請求到達(dá)樹形拓?fù)涞趌層的概率能夠被遞歸表示為

其中S(a)表示a的請求經(jīng)過l層到上層被解析后，在數(shù)據(jù)包回到l層時(shí)，l層的路由器節(jié)點(diǎn)是否緩存的函數(shù)，以下會(huì)結(jié)合PCBSC算法給出S(a)的公式。

2.3 基于內(nèi)容流行度與節(jié)點(diǎn)中心度的緩存分配算法

PCBSC策略中內(nèi)容項(xiàng)并不需要緩存在路由沿路的所有節(jié)點(diǎn)上，而是選擇某個(gè)或者某些最適合緩存該數(shù)據(jù)節(jié)點(diǎn)進(jìn)行緩存，所以路徑上每個(gè)節(jié)點(diǎn)的特性與緩存狀態(tài)都需要加以考慮。這樣路由通路上部分節(jié)點(diǎn)的緩存空間將會(huì)被節(jié)省下來以容納更多的特有數(shù)據(jù)。

如何定量是否“適合”？直觀上考慮，流行度(popularity)高的內(nèi)容，即過去一段時(shí)間的統(tǒng)計(jì)數(shù)據(jù)表明請求分發(fā)次數(shù)多的內(nèi)容，并預(yù)示未來一段時(shí)間同樣流行的內(nèi)容，例如最近很流行的文章或者電影，更應(yīng)該優(yōu)先被選擇緩存在更靠近網(wǎng)絡(luò)中心的位置。網(wǎng)絡(luò)的中心位置區(qū)別于網(wǎng)絡(luò)邊緣，本文對中心位置的量化引入“中心度(centrality)”這個(gè)變量，中心度等于路由器節(jié)點(diǎn)的度，即與該路由器相關(guān)聯(lián)的鏈路的條數(shù)。

所有系統(tǒng)中的命名的內(nèi)容項(xiàng)都基于全局流行度(popularity)進(jìn)行排名，例如對內(nèi)容項(xiàng)a的全局流行度量化為在系統(tǒng)中請求內(nèi)容項(xiàng)a的總體頻率q(a)。同時(shí)路由器節(jié)點(diǎn)也會(huì)根據(jù)節(jié)點(diǎn)的度deg(n)進(jìn)行排名，那么內(nèi)容項(xiàng)a是否能緩存在路由器n中滿足式(5)：

式(5)是目標(biāo)路由器n是否緩存內(nèi)容項(xiàng)a的函數(shù)，其中M為系統(tǒng)中緩存節(jié)點(diǎn)個(gè)數(shù)，N為系統(tǒng)中所有內(nèi)容項(xiàng)個(gè)數(shù)。而是否緩存取決于內(nèi)容項(xiàng)a的流行度排名是否足夠高而有資格緩存在排名為r'(n)的目標(biāo)路由器n中。對于內(nèi)容項(xiàng)a只有其流行度排名所占所有N個(gè)內(nèi)容項(xiàng)排名的百分比r(a)高于目標(biāo)路由器n的度占所有M個(gè)路由器排名的百分比r'(n)，內(nèi)容項(xiàng)a才以概率1緩存在目標(biāo)路由器n中。

圖2為PCBCB算法的算法流程圖。

使用PCBCS算法決定是否對內(nèi)容a進(jìn)行緩存需要O(n)時(shí)間，其中n取決于待緩存節(jié)點(diǎn)中已有內(nèi)容項(xiàng)的個(gè)數(shù)以及待緩存節(jié)點(diǎn)所在的區(qū)域內(nèi)的節(jié)點(diǎn)數(shù)量。線性復(fù)雜度O(n)對于ICN路由器沒有太大壓力，能夠確保內(nèi)容項(xiàng)到達(dá)ICN路由器后，其能夠快速?zèng)Q定是否緩存。而PCBCS算法的空間復(fù)雜度是常數(shù)階O(1)，ICN路由器的內(nèi)置緩存就能夠滿足運(yùn)算要求。

圖2　PCBCS算法流程圖

圖3中呈現(xiàn)了樹結(jié)構(gòu)頂4層的拓?fù)?，假如對?nèi)容項(xiàng)a的請求由源節(jié)點(diǎn)即R1路由器節(jié)點(diǎn)響應(yīng)，這也意味著請求由底層向上層轉(zhuǎn)發(fā)時(shí)中間節(jié)點(diǎn)緩存都未命中。已知內(nèi)容項(xiàng)a的流行度在系統(tǒng)中所有N個(gè)內(nèi)容項(xiàng)的排名換算成百分比為20%。2號節(jié)點(diǎn)度為5，在所有M個(gè)節(jié)點(diǎn)度的排名換算成百分比為10%，而R2路由器節(jié)點(diǎn)度的排名為30%，并且內(nèi)容項(xiàng)的轉(zhuǎn)發(fā)路徑為R1-R2-R4-R6……。且R2路由器、R4路由器節(jié)點(diǎn)有空間緩存該內(nèi)容項(xiàng)。那么根據(jù)PCBCS算法，該內(nèi)容項(xiàng)的流行度并沒有足夠高到有資格緩存在R2路由器節(jié)點(diǎn)中，卻能緩存在R4路由器節(jié)點(diǎn)中。

PCBCS方法的性能指標(biāo)體現(xiàn)在平均反應(yīng)時(shí)延，平均緩存替換次數(shù)，以及內(nèi)容服務(wù)器命中率上。其中對內(nèi)容項(xiàng)a請求的反應(yīng)時(shí)延D(a)定義為用戶從發(fā)出對a的請求到請求在系統(tǒng)中得到響應(yīng)(無論是中間路由器節(jié)點(diǎn)緩存命中還是源節(jié)點(diǎn)服務(wù)器命中)所需的時(shí)間。反應(yīng)時(shí)延表示為請求從發(fā)出到得到響應(yīng)所經(jīng)歷的跳數(shù)。平均緩存替換次數(shù)是指單位時(shí)間單位路由器節(jié)點(diǎn)發(fā)生的緩存替換的次數(shù)。將平均緩存替換次數(shù)加入評估PCBCS方法的性能指標(biāo)中是因?yàn)槠骄彺嫣鎿Q次數(shù)的多少直接影響路由器節(jié)點(diǎn)的負(fù)載。

2.4 局部性原理

圖3　樹形結(jié)構(gòu)示意圖

上一節(jié)為PCBCS方法建立的樹形拓?fù)湓谀M用戶請求時(shí)采用了IRM獨(dú)立參考模型，IRM模型廣泛應(yīng)用于在對存儲(chǔ)系統(tǒng)的分析上，在ICN網(wǎng)絡(luò)建模中被大量使用，這些研究均假設(shè)請求遵從獨(dú)立參考模型?？梢娝c現(xiàn)存的緩存模型有著緊密的聯(lián)系，IRM模型是緩存模型的基礎(chǔ)[2]。IRM模型下對內(nèi)容項(xiàng)的請求是獨(dú)立隨機(jī)變量，即各個(gè)請求之間沒有關(guān)聯(lián)性，但本文注意到對一個(gè)目標(biāo)的請求很大可能會(huì)觸發(fā)未來一段時(shí)間的一系列在附近地理位置的相同請求。也就是對內(nèi)容項(xiàng)的請求在空間和時(shí)間上存在局部性。所以本文在分析PCBCS方法的性能時(shí)，在傳統(tǒng)的IRM模型的基礎(chǔ)上，利用簇點(diǎn)過程理論得到通用的方法來綜合內(nèi)容請求的分布特性，以此將局部性原理加入分析模擬中。本文的目的并不是為了比較IRM模型與加入了局部性后新模型的優(yōu)劣，而是為了證明局部性原理對ICN緩存網(wǎng)絡(luò)性能的影響，最重要的是為PCBCS策略搭建最接近真實(shí)的模擬環(huán)境。

局部性原理下，從小范圍看對內(nèi)容項(xiàng)的請求在時(shí)間和空間維度上局部成簇，本文基于此引入局部性因子(locality)[13]來量化簇的度，范圍從0～1，局部性因子為0即退化為IRM模型。

使用簇點(diǎn)過程(cluster point processes)理論[14]來模擬請求的時(shí)空局部性。通過一個(gè)請求生成簇心，設(shè)置α為內(nèi)容項(xiàng)流行度Zipf分布的參數(shù)，根據(jù)該請求內(nèi)容的全局流行度圍繞該中心生成相應(yīng)的后代子集，由此對更加流行內(nèi)容項(xiàng)的請求能夠在更廣的范圍和更長的時(shí)間延續(xù)，相反，不流行的內(nèi)容項(xiàng)只會(huì)在特定的某一小范圍區(qū)域，特定的很短的時(shí)段被連續(xù)請求。這樣能夠確保全局目標(biāo)流行度遵循開始指定的Zipf分布。同時(shí)本文在模擬時(shí)設(shè)置合適的N和α的值，使其足夠大來保證流行度分布排名靠后的內(nèi)容項(xiàng)也有合理的機(jī)會(huì)被請求。

簇心分散在整個(gè)用戶節(jié)點(diǎn)間，對于每一個(gè)簇心，后代請求在其周圍分布，總體形成具有局部性的分布式請求。

3　仿真測試與分析

3.1 仿真設(shè)置與仿真方法

為了評估本文提出的PCBCS方法的性能，我們在ndnSIM[15]上做了大量基于離散事件驅(qū)動(dòng)的模擬，ndnSIM是實(shí)現(xiàn)命名數(shù)據(jù)網(wǎng)絡(luò)(Named Data Networking，NDN)的一個(gè)NS-3的模塊，通過對ndnSIM中各個(gè)緩存節(jié)點(diǎn)的緩存決策方法進(jìn)行配置，其中有默認(rèn)緩存策略的配置以及對PCBCS方法的自定義編程，能夠很直觀地呈現(xiàn)各種策略性能情況，方便對比分析。

拓?fù)浯罱ú捎脴湫谓Y(jié)構(gòu)，區(qū)別于傳統(tǒng)的對ICN結(jié)構(gòu)性能分析所用的完全K叉樹結(jié)構(gòu)。本文拓?fù)渲袠浣Y(jié)構(gòu)中每個(gè)節(jié)點(diǎn)擁有的子樹個(gè)數(shù)并不固定為K，而定義為deg(·)函數(shù)，依此決定該緩存節(jié)點(diǎn)的度，引申為中心度的度量。實(shí)驗(yàn)中樹的深度為6，其中內(nèi)容請求者位于最底層的第0層，內(nèi)容源為與頂層第5層。中間4層l1～l4層為具有緩存能力的路由器節(jié)點(diǎn)，節(jié)點(diǎn)總數(shù)為M=200，并配置它們的緩存替代策略為LRU策略。

仿真中生成內(nèi)容項(xiàng)總數(shù)N=100000個(gè)具有相同大小的數(shù)據(jù)項(xiàng)，這些內(nèi)容項(xiàng)的流行度，即整個(gè)系統(tǒng)中對內(nèi)容項(xiàng)的請求概率服從參數(shù)為1的Zipf分布，對應(yīng)單個(gè)節(jié)點(diǎn)請求的泊松分布的參數(shù)也與其流行度成正比。

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

本文將PCBCS方法與ICN網(wǎng)絡(luò)大量采用的全局沿路緩存策略以及LCD策略、Prob策略進(jìn)行性能對比，其中Prob方法中每個(gè)沿途節(jié)點(diǎn)都以概率p緩存對象，而以概率1-p不緩存對象，p的值可以依據(jù)緩存情況進(jìn)行調(diào)整，當(dāng)p=1時(shí)，即退化為全局沿路緩存策略，對此本文選定p為0.3～0.7兩種策略，p(0.3)和p(0.7)。

(1)IRM模型下不同策略一次請求的平均響應(yīng)跳數(shù)：圖4呈現(xiàn)了IRM模型中不同策略下應(yīng)答每個(gè)請求所耗費(fèi)的的平均跳數(shù)，可以觀察到PCBCS方法較其他4種方法在平均跳數(shù)指標(biāo)的性能上有較大的改進(jìn)，平均跳數(shù)在本文的拓?fù)渲形ㄒ坏陀?跳，而全局沿路緩存策略平均需要接近4跳才能得到響應(yīng)。此時(shí)的模擬并未考慮局部性因素，即此時(shí)的局部性因子為0。之后會(huì)將局部性因子加入模擬，數(shù)值范圍從0～1，即請求由完全獨(dú)立隨機(jī)過程到完全局部化。

(2)不同策略下服務(wù)器命中率與局部性的關(guān)系：

圖5展示了5種不同緩存決策策略情況下服務(wù)器命中率隨著局部性因子數(shù)值改變而變化的情況。從圖中可以看出PCBCS方法相比全局沿路緩存策略在服務(wù)器命中率上有很大程度的降低，這意味著PCBCS方法中對內(nèi)容項(xiàng)的請求將以更大概率由中間路由器緩存命中，從而無需繼續(xù)轉(zhuǎn)發(fā)至頂層的內(nèi)容源根節(jié)點(diǎn)，這樣能夠減少這部分請求的響應(yīng)時(shí)延。同時(shí)觀察任意一種策略，可以從圖像中得出服務(wù)器命中率同時(shí)與請求的局部性有很大聯(lián)系，這也印證了之前提到的局部性理論對于ICN網(wǎng)絡(luò)緩存的重要性，以及將局部性理論加入網(wǎng)絡(luò)緩存模型的必要性。對于內(nèi)容請求，更強(qiáng)的局部性能更大程度的減少服務(wù)器命中率。

(3)不同策略下平均相應(yīng)跳數(shù)與局部性的關(guān)系：

對于響應(yīng)時(shí)延來說，服務(wù)器命中上PCBCS減少的那部分在取得響應(yīng)所經(jīng)過的跳數(shù)上自然能得到減少，因?yàn)樵诒疚牡膶?shí)驗(yàn)環(huán)境下對內(nèi)容項(xiàng)的請求得到響應(yīng)最多經(jīng)歷5跳，即內(nèi)容源根節(jié)點(diǎn)響應(yīng)請求，所以采用PCBCS方法減少的服務(wù)器命中數(shù)對應(yīng)的請求將小于5跳得到響應(yīng)，減小了響應(yīng)時(shí)延。具體性能的提升在圖6中呈現(xiàn)，圖中PCBCS方法比其它4種方法在在響應(yīng)時(shí)延上都有很大的性能提升。同時(shí)可以觀察到局部性在模擬中對時(shí)延影響很大。而全局沿路緩存策略在時(shí)延上的表現(xiàn)依舊低效。

(4)不同策略下的總體緩存替換次數(shù)：緩存替換發(fā)生在新的內(nèi)容需要被緩存在空間已滿的緩存節(jié)點(diǎn)的情況下，而替換是耗時(shí)的，會(huì)消耗緩存節(jié)點(diǎn)的計(jì)算資源，增加節(jié)點(diǎn)的負(fù)荷。所以不考慮替換所間接導(dǎo)致的其它參數(shù)性能提升的情況，單純的替換是降低整體性能的操作，要加以限制。同時(shí)不是所有的替換后續(xù)都能有益于性能提升，事實(shí)上，在內(nèi)容流行度遵從Zipf分布的情況下，流行度排名在末尾的內(nèi)容被請求的可能性很小，但是在全局沿路緩存策略下，這些不流行的內(nèi)容一旦被請求，那么會(huì)導(dǎo)致從響應(yīng)者到請求者沿路所有路由器節(jié)點(diǎn)的緩存替換，然而在未來的一段時(shí)間這些內(nèi)容項(xiàng)接著被請求的概率很低，它們卻占用了本應(yīng)屬于流行內(nèi)容項(xiàng)的空間，降低了系統(tǒng)整體性能。從圖7中能夠看出，PCBCS方法比全局沿路緩存策略方法在緩存替換總數(shù)上有了大幅度的減少。這一點(diǎn)不難從PCBCS方法的特性得出。因?yàn)镻CBCS是選擇性緩存策略，路由器節(jié)點(diǎn)對經(jīng)過的內(nèi)容項(xiàng)的緩存是有選擇的，并非必須緩存。其次，性能呈現(xiàn)圖中，PCBCS方法下內(nèi)容請求能夠以更小的跳數(shù)得到響應(yīng)，更進(jìn)一步減小了緩存替換數(shù)目。

4　結(jié)束語

網(wǎng)絡(luò)內(nèi)置緩存是ICN網(wǎng)絡(luò)最重要的特性，緩存決策策略的優(yōu)劣直接影響ICN網(wǎng)絡(luò)內(nèi)置緩存的性能。默認(rèn)的緩存決策策略會(huì)導(dǎo)致大量的數(shù)據(jù)冗余，并且反應(yīng)時(shí)延大，緩存替換次數(shù)多。本文提出基于內(nèi)容流行度和節(jié)點(diǎn)中心度匹配的選擇性緩存決策策略，即PCBCS方法，提高內(nèi)容分發(fā)沿路節(jié)點(diǎn)的緩存空間使用效率，減少緩存冗余，此外，在分析論證時(shí)考慮緩存網(wǎng)絡(luò)在時(shí)間和空間領(lǐng)域上展現(xiàn)出的強(qiáng)大的關(guān)聯(lián)關(guān)系，加入局部性因素，摒棄僅采用傳統(tǒng)的外生請求到達(dá)模型即IRM假設(shè)，而是結(jié)合請求關(guān)聯(lián)性模型進(jìn)行建模分析。最后通過仿真結(jié)果表明，PCBCS方法較傳統(tǒng)沿路緩存策略，LCD策略以及Prob策略，在服務(wù)器命中率，反應(yīng)時(shí)延以及替換次數(shù)的性能指標(biāo)上有較大程度的提升。

接下來的工作我們將進(jìn)一步優(yōu)化內(nèi)容流行度以及節(jié)點(diǎn)中心度的分級機(jī)制，并將我們的策略運(yùn)行在不同的實(shí)際拓?fù)渲?，逐步調(diào)優(yōu)以達(dá)到最佳性能。

圖4　IRM模型下不同策略平均響應(yīng)跳數(shù)

圖5　不同策略下服務(wù)器命中率與局部性的關(guān)系

圖6　不同策略下平均響應(yīng)跳數(shù)與局部性的關(guān)系

圖7　緩存系統(tǒng)總體緩存替換次數(shù)

參考文獻(xiàn)

[1]張國強(qiáng)，李楊，林濤，等.信息中心網(wǎng)絡(luò)中的內(nèi)置緩存技術(shù)研究[J].軟件學(xué)報(bào)，2014，25(1):154-175.doi:10.13328/j.cnki.jos.004494.ZHANG Guo-qiang，LI Yang，LIN Tao，et al.Survey of in-network caching techniques in information-centric networks[J].Journal of Software，2014，25(1):154-175.doi:10.13328/j.cnki.jos.004494.

[2]KUROSE J.Information-centric networking:The evolutionfrom circuits to packets to content[J].Computer Networks，2014，66:112-120.

[3]TANG X and CHANSON S T.Coordinated en-route Web caching[J].IEEE Transactions on Computers，2002，51(6):595-607.

[4]WANG S，BI J，and WU J.Collaborative caching based on hash-routing for information-centric networking[C].Proceedings of the 2013 ACM SIGCOMM，Hong Kong，2013:535-536.

[5]PAVIOU G，PSARAS I，and WEI K C.Probabilistic in-network caching for information-centric networks[C].Proceedings of ACM SIGCOMM ICN Workshop，Helsinki，2012:55-60.

[6]崔現(xiàn)東，劉江，黃韜，等.基于節(jié)點(diǎn)介數(shù)和替換率的內(nèi)容中心網(wǎng)絡(luò)網(wǎng)內(nèi)緩存策略[J].電子與信息學(xué)報(bào)，2014，36(1):1-7.doi:10.3724/SP.J.1146.2013.00503.CUI Xiandong，LIU Jiang，HUANG Tao，et al.A novel in-network caching scheme based on betweenness and replacement rate in content centric networking[J].Journal of Electronics ＆ Information Technology，2014，36(1):1-7.doi:10.3724/SP.J.1146.2013.00503.

[7]HU Q，WU M，WANG D，et al.Lifetime-based greedy caching approach for content-centric networking[C].21st International Conference on Telecommunications，Lisbon，2014:426-430.

[8]葛國棟，郭云飛，劉彩霞.內(nèi)容中心網(wǎng)絡(luò)中面向隱私保護(hù)的協(xié)作緩存策略[J].電子與信息學(xué)報(bào)，2015，37(5):1220-1226.doi.10.11999/JEIT140874.GE Guodong，GUO Yunfei，LIU Caixia，et al.A collaborative caching strategy for privacy protection in content centric networking[J].Journal of Electronics ＆ Information Technology，2015，37(5):1220-1226.doi:10.11999/ JEIT140874.

[9]朱軼，糜正琨，王文鼐等.一種基于內(nèi)容流行度的內(nèi)容中心網(wǎng)絡(luò)緩存概率置換策略[J].電子與信息學(xué)報(bào)，2013，35(6):1305-1310.doi:10.3724/SP.J.1146.2012.01143.ZHU Yi，MI Zhengkun，WANGg Wennai，et al.A cache probability replacement policy based on content popularity in content centric networks[J].Journal of Electronics ＆Information Technology，2013，35(6):1305-1310.doi.10.3724/SP.J1146.2012.01143.

[10]MING Z X，XU M W，and WANG D.Age-based cooperative caching in information-centric networks[C].IEEE INFOCOM Workshop on Emerging Design Choices in Name-oriented Networking，Orlando，USA，2012:268-273.

[11]LEET D.On the existence of a spectrum of policies that subsumes the Least Recently Used(LRU)and Least Frequently Used(LFU)policies[C].Proceedings of the 1999 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems，Atlanta，1999:134-143.

[12]CHE H，TUNG Y，and WANG Z.Hierarchical Web caching systems:Modeling，design and experimental results[J].IEEE Selected Areas in Communications，2012，20(7):1305-1314.

[13]TRAVERSO S，AHMED M，GATETTO M，et al.Temporal locality in today's content caching:Why it matters and how to model it[J].ACM SIGCOMM Computer Communications Review，2013，43(5):5-12.

[14]KARYPIS G，HAN E H，and KUMAR V.CHAMELEON:Hierarchical clustering algorithm using dynamic modeling[J].IEEE Computer，1999，32(8):68-75.

[15]AFANASYEV A，MOISEENKO I，and ZHANG L.“ndnSIM:NDN Simulator for NS-3”[R].University of California Technical Report，2012.

芮蘭蘭：女，1979 年生，博士，副教授，研究方向?yàn)榫W(wǎng)絡(luò)和業(yè)務(wù)質(zhì)量管理、泛在網(wǎng)絡(luò)、大數(shù)據(jù)等.

彭昊：男，1992 年生，碩士生，研究方向?yàn)榫W(wǎng)絡(luò)緩存技術(shù).

黃豪球：男，1985 年生，博士生，研究方向?yàn)樾畔⒅行木W(wǎng)絡(luò).

邱雪松：男，1973 年生，教授，博士生導(dǎo)師，研究方向?yàn)榫W(wǎng)絡(luò)管理和通信軟件等.

史瑞昌：男，1991 年生，碩士生，研究方向?yàn)閮?nèi)容中心網(wǎng)絡(luò).

Popularity and Centrality Based Selective Caching Scheme for Information-centric Networks

RUI LanlanPENG HaoHUANG HaoqiuQIU XuesongSHI Ruichang
(State Key Laboratory of Networking and Switching Technology，Beijing University of Posts and Telecommunications，Beijing 100876，China)

Abstract:Information-Centric Network(ICN)architectures seek to provide the necessary foundations for a more cost-efficient content acquirement and content distribution using universal in-network caching，also universal in-network caching is a key design principle of many such architectures.Given that caching capacity of ICN is relatively small in comparison to the amount of forwarded content，a key aspect is balanced distribution of content among the available caches.The in-network caching resolution scheme is proposed in this paper，based on content popularity and node’s centrality，called PCBCS.It reduces caching redundancy and in turn，make more efficient utilization of available cache resources along a delivery path through selective caching of content passing.The proposed algorithm is compared with universal on-path caching and Leave Copy Down(LCD)，also Prob(copy with probability)scheme with parameter of 0.7 and 0.3.The results show reduction of up to 30% in server hits，and up to 20% in the number of hops required to hit cached contents，but，most importantly，reduction of cache replacements up to 40% in comparison to universal caching.

Key words:Information-Centric Network(ICN); Caching network; Caching resolution strategy; Spatiotemporal locality of reference

基金項(xiàng)目：國家自然科學(xué)基金(61302078，61372108)，國家863計(jì)劃(2011AA01A102)，國家科技重大專項(xiàng)(2011ZX03005-004-02)，北京高等學(xué)校青年英才計(jì)劃項(xiàng)目(YETP0476)

*通信作者：彭昊heypardon@bupt.edu.cn

收稿日期：2015-05-27；改回日期：2015-11-09；網(wǎng)絡(luò)出版：2015-12-18

DOI:10.11999/JEIT150626

中圖分類號：TP393

文獻(xiàn)標(biāo)識碼：A

文章編號：1009-5896(2016)02-0325-07

Foundation Items:The National Natural Science Foundation of China(61302078，61372108)，The National 863 Program of China(2011AA01A102)，The National S＆T Major Project(2011ZX 03005-004-02)，Beijing Higher Education Young Elite Teacher Project(YETP0476)