基于內(nèi)容流行度和節(jié)點(diǎn)重要度的CCN緩存策略

鄭凱月，潘沛生

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，以IP為基礎(chǔ)的TCP/IP網(wǎng)絡(luò)體系架構(gòu)逐漸暴露出諸多問題，比如可擴(kuò)展性較差、安全可控性低、移動(dòng)性支持不足、服務(wù)質(zhì)量難以保證等?；ヂ?lián)網(wǎng)用戶行為也發(fā)生變化，轉(zhuǎn)變?yōu)殛P(guān)注數(shù)據(jù)的內(nèi)容而不是關(guān)注服務(wù)器和主機(jī)IP地址，因此如何更快、更準(zhǔn)確、更高效地獲取數(shù)據(jù)成為下一代網(wǎng)絡(luò)研究的熱點(diǎn)問題。

內(nèi)容中心網(wǎng)絡(luò)(CCN)是一個(gè)以內(nèi)容為中心，將信息對(duì)象作為架構(gòu)的網(wǎng)絡(luò)體系。CCN網(wǎng)絡(luò)每一個(gè)節(jié)點(diǎn)都有一定的緩存功能，利用網(wǎng)絡(luò)內(nèi)置緩存提高傳輸效率。緩存的研究主要有兩個(gè)方面：一是緩存放置策略，二是緩存替換策略。緩存放置策略用于決定某一節(jié)點(diǎn)處是否緩存該內(nèi)容，緩存替換策略用于解決當(dāng)某一節(jié)點(diǎn)緩存已滿的情況下如何實(shí)現(xiàn)新到達(dá)內(nèi)容的緩存問題。傳統(tǒng)的緩存放置策略有：LCE[1](leave copy everywhere)，即Always緩存策略；LCD(leave copy down)；Prob(copy with probability);Betw[2](cache based on betweenness)。

(1)LCE策略要求內(nèi)容在分發(fā)路徑的所有節(jié)點(diǎn)都緩存，這樣會(huì)導(dǎo)致網(wǎng)絡(luò)中緩存節(jié)點(diǎn)空間的浪費(fèi)和緩存內(nèi)容的冗余。

(2)LCD策略要求只在命中節(jié)點(diǎn)下一跳放置緩存，這樣需要多次請(qǐng)求同一內(nèi)容才會(huì)將該內(nèi)容復(fù)制到靠近客戶端的地方，同樣會(huì)產(chǎn)生大量的內(nèi)容冗余備份。

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

(4)Betw策略在請(qǐng)求內(nèi)容返回時(shí)選擇興趣包請(qǐng)求路徑上最重要的節(jié)點(diǎn)進(jìn)行緩存，其他節(jié)點(diǎn)不再緩存。Betw策略在很多不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，在節(jié)點(diǎn)命中率和獲取內(nèi)容的平均跳數(shù)方面都獲得了較好的性能表現(xiàn)。但是，重要節(jié)點(diǎn)的緩存空間有限，節(jié)點(diǎn)越重要，到達(dá)的請(qǐng)求就越多，需要緩存的內(nèi)容就更多，這時(shí)緩存替換策略便會(huì)頻繁啟用[6]。在重要緩存節(jié)點(diǎn)緩存滿了的情況下，緩存替換策略將會(huì)把之前緩存的內(nèi)容剔除掉，即便是新緩存的具有很高流行度的內(nèi)容也會(huì)被快速替換掉，致使后續(xù)請(qǐng)求無法充分利用前期緩存的內(nèi)容。而且重要節(jié)點(diǎn)并不是最靠近用戶的節(jié)點(diǎn)，這樣會(huì)導(dǎo)致最流行的內(nèi)容無法到達(dá)最靠近用戶的節(jié)點(diǎn)，使獲取內(nèi)容的平均跳數(shù)增大，即用戶獲取內(nèi)容的時(shí)延增大[7]。

基于以上方案存在的各種問題，文中提出在內(nèi)容流行度進(jìn)行排名的基礎(chǔ)上考慮節(jié)點(diǎn)的中心度[8]，將流行度量化為請(qǐng)求頻率，比如對(duì)內(nèi)容a的流行度量化為請(qǐng)求頻率q(a)，對(duì)系統(tǒng)中命名的內(nèi)容項(xiàng)都基于全局流行度進(jìn)行排名。節(jié)點(diǎn)的中心度反映節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性[9]，中心度等于路由器節(jié)點(diǎn)的度，即與該路由器相關(guān)聯(lián)的鏈路的條數(shù)。該緩存機(jī)制在請(qǐng)求內(nèi)容沿原路徑返回時(shí)，將內(nèi)容緩存在具有最大節(jié)點(diǎn)中心度的節(jié)點(diǎn)上，緩存滿了后在該節(jié)點(diǎn)內(nèi)生成內(nèi)容流行度排名表，然后將新到達(dá)內(nèi)容的流行度分別與節(jié)點(diǎn)內(nèi)最大最小流行度進(jìn)行比較，然后決定是否在該節(jié)點(diǎn)緩存新來的內(nèi)容。

1 基于內(nèi)容流行度和節(jié)點(diǎn)中心度的緩存機(jī)制

1.1 設(shè)計(jì)思想

該方案主要是針對(duì)Betw方案做出的改進(jìn)。將節(jié)點(diǎn)中心度與內(nèi)容流行度相結(jié)合，在節(jié)點(diǎn)中心度最高的節(jié)點(diǎn)放置緩存內(nèi)容，當(dāng)緩存滿了之后，對(duì)節(jié)點(diǎn)內(nèi)的內(nèi)容進(jìn)行流行度排名，在重要節(jié)點(diǎn)內(nèi)生成一張流行度排名列表popularity precedence table (PPT)，新到達(dá)的內(nèi)容的流行度分別與具有最大、最小流行度的內(nèi)容進(jìn)行比較，將大于最大流行度的內(nèi)容放在此重要節(jié)點(diǎn)的下一級(jí)節(jié)點(diǎn)，將小于最小流行度的內(nèi)容放在此重要節(jié)點(diǎn)的上一級(jí)節(jié)點(diǎn)，將位于最大最小流行度之間的內(nèi)容放在此節(jié)點(diǎn)內(nèi)，剔除掉最小流行度的內(nèi)容。這樣一來，將內(nèi)容實(shí)現(xiàn)了分布式的緩存，減緩了重要節(jié)點(diǎn)的緩存替換率和負(fù)荷，又能讓最流行的內(nèi)容逐漸靠近用戶，減少內(nèi)容冗余。

在圖1所示的拓?fù)鋱D中，t=0時(shí)刻，所有的緩存節(jié)點(diǎn)均為空。當(dāng)用戶A向內(nèi)容中心(SEVER)請(qǐng)求內(nèi)容a時(shí)，SEVER向用戶A返回內(nèi)容a所經(jīng)過的路徑為V1→V2→V4→V5，由于在該路徑上節(jié)點(diǎn)V2的中心度最大，將內(nèi)容a緩存在V2，隨后當(dāng)A、B、C、D中某幾個(gè)用戶請(qǐng)求相同內(nèi)容時(shí)，即可在節(jié)點(diǎn)V2命中。但是網(wǎng)絡(luò)內(nèi)部?jī)?nèi)容繁多，V2節(jié)點(diǎn)緩存容量有限。于是當(dāng)V2節(jié)點(diǎn)緩存滿了之后，需要對(duì)V2節(jié)點(diǎn)內(nèi)的內(nèi)容的流行度等級(jí)進(jìn)行排名。當(dāng)后續(xù)一段時(shí)間內(nèi)新內(nèi)容到達(dá)時(shí)，將新內(nèi)容的流行度等分別與節(jié)點(diǎn)內(nèi)最大最小流行度進(jìn)行比較：若大于最大流行度內(nèi)容，則將新內(nèi)容緩存在V2的下一級(jí)節(jié)點(diǎn)即V3、V4節(jié)點(diǎn)，這樣流行度很大的內(nèi)容將更靠近用戶；若新到達(dá)的內(nèi)容小于最小流行度內(nèi)容，則將新到達(dá)的內(nèi)容緩存在V1節(jié)點(diǎn)；若新到達(dá)內(nèi)容的流行度處于最大流行度與最小流行度之間，則將最小流行度內(nèi)容剔除，替換成新內(nèi)容，再重新對(duì)節(jié)點(diǎn)內(nèi)的內(nèi)容流行度進(jìn)行排名。這種緩存策略，不僅能將近來一段時(shí)間內(nèi)的不再流行的內(nèi)容替換掉、增大緩存中內(nèi)容的存活時(shí)間，又能將近來最流行的內(nèi)容緩存在靠近用戶的網(wǎng)絡(luò)邊緣，減少內(nèi)容冗余。

圖1 緩存決策實(shí)例

1.2 內(nèi)容流行度和節(jié)點(diǎn)中心度的計(jì)算

1.2.1 內(nèi)容流行度

內(nèi)容流行度[10]代表用戶對(duì)內(nèi)容的喜愛程度，通過在興趣包和數(shù)據(jù)包中攜帶流行度值標(biāo)簽的形式實(shí)現(xiàn)內(nèi)容流行度的記錄。當(dāng)前的內(nèi)容流行度與歷史內(nèi)容的流行度和衰減系數(shù)有關(guān)，在過去一段統(tǒng)計(jì)時(shí)間內(nèi)包含M個(gè)請(qǐng)求內(nèi)容，在這一段周期內(nèi)統(tǒng)計(jì)出各個(gè)請(qǐng)求內(nèi)容的訪問頻次[11]。內(nèi)容流行度值是對(duì)內(nèi)容a在請(qǐng)求周期內(nèi)的請(qǐng)求次數(shù)估計(jì)值。式1為在第n個(gè)時(shí)間周期內(nèi)的內(nèi)容a的估計(jì)值。

Pa[n]=α×Pa[n-1]+(1-α)×Fa(n-1)

(1)

其中，Pa[n]表示第n個(gè)周期內(nèi)的內(nèi)容a的流行度；Pa[n-1]表示第n-1個(gè)周期內(nèi)的內(nèi)容a的流行度；α表示衰減系數(shù)；Fa(n-1)表示第n-1個(gè)周期內(nèi)的內(nèi)容a的訪問頻次。

1.2.2 節(jié)點(diǎn)中心度

將節(jié)點(diǎn)中心度量化為節(jié)點(diǎn)介數(shù)，即Betw介數(shù)緩存方法提出的節(jié)點(diǎn)介數(shù)計(jì)算方法，節(jié)點(diǎn)介數(shù)表征節(jié)點(diǎn)的重要程度，也就是與該節(jié)點(diǎn)相關(guān)聯(lián)的鏈路條數(shù)[12]。

在CCN網(wǎng)絡(luò)中，有多個(gè)內(nèi)容分發(fā)路徑要經(jīng)過同一個(gè)路徑節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要度就比較高，即中心度高。文獻(xiàn)[1]給出了節(jié)點(diǎn)介數(shù)的定義：

若G(V,E)[1]是一個(gè)具有n個(gè)節(jié)點(diǎn)的無向圖向量，n個(gè)節(jié)點(diǎn)為V={v1,v2,…,vn}，用CB-SP(v)表示節(jié)點(diǎn)介數(shù)，表達(dá)式為：

(2)

其中，σst表示兩個(gè)頂點(diǎn)s與t之間的最短路徑數(shù)；σst(v)表示經(jīng)過頂點(diǎn)v的最短路徑數(shù)。

在Betw算法中，使用的路由轉(zhuǎn)發(fā)算法是最短路徑算法，所以文中只統(tǒng)計(jì)節(jié)點(diǎn)間最短路徑的數(shù)目。

對(duì)于一些移動(dòng)的網(wǎng)絡(luò)、自組織網(wǎng)絡(luò)等，這些網(wǎng)絡(luò)拓?fù)溆幸欢ú淮_定性，在這些網(wǎng)絡(luò)中很難獲得節(jié)點(diǎn)的信息，因此計(jì)算節(jié)點(diǎn)介數(shù)就很難實(shí)現(xiàn)[13]。文獻(xiàn)[2]提出一種方法：即每個(gè)節(jié)點(diǎn)基于它的自我中心網(wǎng)絡(luò)而非整個(gè)網(wǎng)絡(luò)來計(jì)算其近似介數(shù)，計(jì)算方法如下所示。

設(shè)A是自我中心網(wǎng)絡(luò)G的N×N對(duì)稱鄰接矩陣：

(3)

自我中心網(wǎng)絡(luò)節(jié)點(diǎn)的介數(shù)由矩陣A2[1-A]i,j來確定，1是一個(gè)全1矩陣，A2[1-A]i,j中所有元素倒數(shù)之和即為該自我網(wǎng)絡(luò)中心節(jié)點(diǎn)的中心度[14]。

1.3 內(nèi)容流行度排名表(PPT)

如表1所示，當(dāng)重要節(jié)點(diǎn)的緩存滿了以后，對(duì)節(jié)點(diǎn)內(nèi)的內(nèi)容流行度進(jìn)行排名，具有最大流行度的內(nèi)容排在最上面，新到達(dá)內(nèi)容的流行度與表內(nèi)的最大最小流行度進(jìn)行比較，之后做出相應(yīng)的判斷。

表1 內(nèi)容流行度排名表

1.4 算法描述

以下內(nèi)容對(duì)提出的corporate緩存策略作偽代碼解釋。

Pseudocode Ι興趣包到達(dá)CCN節(jié)點(diǎn)時(shí)算法：

Initialize

(Pa(1)=Pa(2)=…=Pa(n)=Pa(0)=0,Fa(0)=Fa(1)=Fa(2)=…=0)

For each (Vkfromitoj)

CalculatePa[n]=α×Pa[n-1]+(1-α)×Fa(n-1)

The interest packet carry the popularity labelPa[n]

Ifdata in cache||entry in PIT

The interest deliver the popularity

label to data packet

Then send(data)

Else

Forward request to the next hop towardsj

Pseudocode Π數(shù)據(jù)包到達(dá)節(jié)點(diǎn)時(shí)執(zhí)行的緩存策略:

Calculate Betw(v1,v2,…,vn)

Vk=max{Betw(v1,v2,…,vn)}

For each (Vkfromjtoi)

IfVknot full

Cache data

Else

Ranking the content popularityP[n] inVk

If(P[n]new(新到達(dá)內(nèi)容流行度)>Pmax)

CacheVk下(Vk的下一級(jí)節(jié)點(diǎn)即靠近用戶端)

If(P[n]new(新到達(dá)內(nèi)容流行度)>Pmin)

DeletePmincontent CacheP[n]newcontent inVk

Else if(Pmax>P[n]new(新到達(dá)內(nèi)容流行度)>Pmin)

RemovePmincontent toVk

CacheP[n]newcontent inVk

2 仿真分析

文中將所提方案(corporate)緩存策略與Always、LCD、Betw緩存放置策略進(jìn)行比較，分別結(jié)合LRU緩存替換策略，通過ndnSIM仿真器，實(shí)現(xiàn)CCN仿真模型，得到仿真數(shù)據(jù)，然后將數(shù)據(jù)導(dǎo)入Matlab軟件中進(jìn)行處理，得到仿真結(jié)果圖，最后對(duì)緩存結(jié)果進(jìn)行評(píng)估。

圖2和圖3是在不同CS緩存容量下(CS單位為塊chunk)四種緩存策略的性能圖。圖2是網(wǎng)絡(luò)源端命中率，內(nèi)容源端命中率越低，表示中間節(jié)點(diǎn)和邊緣節(jié)點(diǎn)發(fā)揮作用越大，緩存性能越好。可以看出，四種緩存策略在CS逐漸變大的情況下，都會(huì)出現(xiàn)源端命中率逐漸遞減的結(jié)果，與其他三種策略相比，corporate策略源端命中率更低，性能更好。圖3是獲取請(qǐng)求內(nèi)容所需要經(jīng)過的平均跳數(shù)，可見corporate策略性能最好，在CS比較小時(shí)由于該策略較其他策略的優(yōu)越性，會(huì)出現(xiàn)快速遞減趨勢(shì)，隨后遞減的趨勢(shì)趨于穩(wěn)定。

圖4和圖5是在不同的Zipf分布參數(shù)[8]下比較四種緩存策略的性能?？梢姡琧orporate策略較其他三種緩存策略，無論是在緩存內(nèi)容命中率還是在獲取內(nèi)容需要經(jīng)過的平均跳數(shù)上都有非常明顯的性能提升效果，驗(yàn)證了所提方案的優(yōu)越性。

圖2 網(wǎng)絡(luò)源端命中率

圖3 網(wǎng)絡(luò)拓?fù)渲蝎@取內(nèi)容平均跳數(shù)

圖4 網(wǎng)絡(luò)中緩存內(nèi)容的命中率

圖5 網(wǎng)絡(luò)拓?fù)渲蝎@取內(nèi)容的平均跳數(shù)

3 結(jié)束語

為了解決之前在CCN網(wǎng)絡(luò)中已存在的各種緩存策略的問題，將緩存滿了的中心節(jié)點(diǎn)中的內(nèi)容流行度進(jìn)行排名比較，然后將新來內(nèi)容的流行度分別與最大、最小流行度進(jìn)行比較，最后做出相應(yīng)判決,將內(nèi)容緩存在最合適的節(jié)點(diǎn)。該方案既解決了Betw緩存策略重要節(jié)點(diǎn)緩存替換頻繁的問題，又使流行內(nèi)容更加靠近用戶；不但可以減少內(nèi)容的冗余，各處節(jié)點(diǎn)也能充分利用，內(nèi)容流行度越高越靠近用戶，從而大大提高了緩存性能。下一步將深入研究?jī)?nèi)容流行度的排名和預(yù)測(cè)[13]，從而制定更為合理的緩存策略，以更好地提升緩存性能。

參考文獻(xiàn)：

[1] 崔現(xiàn)東，劉 江，黃 韜，等.基于節(jié)點(diǎn)介數(shù)和替換率的內(nèi)容中心網(wǎng)絡(luò)網(wǎng)內(nèi)緩存策略[J].電子與信息學(xué)報(bào)，2014,36(1)：1-7.

[2] LI Yang,LIN Tao,TANG Hui,et al.A chunk caching location and searching scheme in content centric networking[C]//IEEE international conference on communications.Ottawa,ON,Canada:IEEE,2012:2655-2659.

[3] 朱 軼，糜正琨，王文鼐.一種基于內(nèi)容流行度的內(nèi)容中心網(wǎng)絡(luò)緩存概率置換策略[J].電子與信息學(xué)報(bào)，2013,35(6)：1305-1310.

[4] TARNOI S,SUKSOMBOON K,KUMWILAISAK W,et al.Performance of probabilistic caching and cache replacement policies for content-centric networks[C]//39th annual IEEE conference on local computer network.[s.l.]:IEEE,2014.

[5] 林 闖，賈子驍，孟 坤.自適應(yīng)的未來網(wǎng)絡(luò)體系架構(gòu)[J].計(jì)算機(jī)學(xué)報(bào)，2012,35(6):1077-1093.

[6] 王國(guó)卿，黃 韜，劉 江,等.一種基于逗留時(shí)間的新型內(nèi)容中心網(wǎng)絡(luò)緩存策略[J].計(jì)算機(jī)學(xué)報(bào)，2015，38(3):472-482.

[7] 芮蘭蘭，彭 昊，黃豪球,等.基于內(nèi)容流行度和節(jié)點(diǎn)中心度匹配的信息中心網(wǎng)絡(luò)緩存策略[J].電子與信息學(xué)報(bào)，2016,38(2)：325-331.

[8] 曾宇晶，靳明雙，羅洪斌.基于內(nèi)容分塊流行度分級(jí)的信息中心網(wǎng)絡(luò)緩存策略[J].電子學(xué)報(bào)，2016,44(2):358-364.

[9] 徐昌彪，王 華.CCN中基于內(nèi)容流行度和節(jié)點(diǎn)重要度的緩存設(shè)計(jì)[J].電子應(yīng)用技術(shù)，2017，43(3)：100-103.

[10] 曲 樺，王偉萍，趙季紅.內(nèi)容中心網(wǎng)絡(luò)中一種改進(jìn)型緩存機(jī)制[J].計(jì)算機(jī)工程，2015,41(3):41-46.

[11] CUI Yufei,ZHAO Min,WU Muqing.A centralized control caching strategy based on popularity and betweenness centrality in CCN[C]//IEEE conference on international symposium on wireless communication systems.Poznan,Poland:IEEE,2016:286-291.

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

[13] 董美姣.基于內(nèi)容流行度預(yù)測(cè)的內(nèi)容中心網(wǎng)絡(luò)緩存技術(shù)研究[D].北京：北京郵電大學(xué)，2015.

[14] GUAN Jianfeng,HE Yunhang,WEI Quan,et al.A classification-based wisdom caching scheme for content centric networking[C]//IEEE conference on computer communications workshops.San Francisco,CA,USA:IEEE,2016.