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

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

?

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

芮蘭蘭彭昊*黃豪球邱雪松史瑞昌
(北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室北京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)容時能力相對弱小，對內(nèi)容放置缺乏均衡分布的問題。該文提出基于內(nèi)容流行度和節(jié)點中心度匹配的緩存策略(Popularity and Centrality Based Caching Scheme，PCBCS)，通過對經(jīng)過的內(nèi)容進行選擇性緩存來提高內(nèi)容分發(fā)沿路節(jié)點的緩存空間使用效率，減少緩存冗余。仿真結(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ò)；緩存決策策略；時空局部性

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

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

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

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

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

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

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

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

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

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

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

2　PCBCS

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

2.1 層級式緩存模型

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

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

圖1　層級式緩存模型拓撲圖

2.2 外生請求到達模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2　PCBCS算法流程圖

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

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

2.4 局部性原理

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

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

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

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

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

3　仿真測試與分析

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

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

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

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

3.2 實驗結(jié)果分析

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

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

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

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

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

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

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

4　結(jié)束語

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

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

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

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

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

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

參考文獻

[1]張國強，李楊，林濤，等.信息中心網(wǎng)絡(luò)中的內(nèi)置緩存技術(shù)研究[J].軟件學(xué)報，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é)點介數(shù)和替換率的內(nèi)容中心網(wǎng)絡(luò)網(wǎng)內(nèi)緩存策略[J].電子與信息學(xué)報，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ò)中面向隱私保護的協(xié)作緩存策略[J].電子與信息學(xué)報，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é)報，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 年生，博士，副教授，研究方向為網(wǎng)絡(luò)和業(yè)務(wù)質(zhì)量管理、泛在網(wǎng)絡(luò)、大數(shù)據(jù)等.

彭昊：男，1992 年生，碩士生，研究方向為網(wǎng)絡(luò)緩存技術(shù).

黃豪球：男，1985 年生，博士生，研究方向為信息中心網(wǎng)絡(luò).

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

史瑞昌：男，1991 年生，碩士生，研究方向為內(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

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

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

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

DOI:10.11999/JEIT150626

中圖分類號：TP393

文獻標識碼：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)