鄭凱月，潘沛生

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

0 引 言

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

內(nèi)容中心網(wǎng)絡(luò)(CCN)是一個以內(nèi)容為中心，將信息對象作為架構(gòu)的網(wǎng)絡(luò)體系。CCN網(wǎng)絡(luò)每一個節(jié)點都有一定的緩存功能，利用網(wǎng)絡(luò)內(nèi)置緩存提高傳輸效率。緩存的研究主要有兩個方面：一是緩存放置策略，二是緩存替換策略。緩存放置策略用于決定某一節(jié)點處是否緩存該內(nèi)容，緩存替換策略用于解決當(dāng)某一節(jié)點緩存已滿的情況下如何實現(xiàn)新到達內(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é)點都緩存，這樣會導(dǎo)致網(wǎng)絡(luò)中緩存節(jié)點空間的浪費和緩存內(nèi)容的冗余。

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

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

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

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

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

1.1 設(shè)計思想

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

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

圖1 緩存決策實例

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

1.2.1 內(nèi)容流行度

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

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

(1)

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

1.2.2 節(jié)點中心度

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

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

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

(2)

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

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

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

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

(3)

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

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

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

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

1.4 算法描述

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

Pseudocode Ι興趣包到達CCN節(jié)點時算法：

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ù)包到達節(jié)點時執(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(新到達內(nèi)容流行度)>Pmax)

CacheVk下(Vk的下一級節(jié)點即靠近用戶端)

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

DeletePmincontent CacheP[n]newcontent inVk

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

RemovePmincontent toVk

CacheP[n]newcontent inVk

2 仿真分析

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

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

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

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

圖3 網(wǎng)絡(luò)拓撲中獲取內(nèi)容平均跳數(shù)

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

圖5 網(wǎng)絡(luò)拓撲中獲取內(nèi)容的平均跳數(shù)

3 結(jié)束語

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

參考文獻：

[1] 崔現(xiàn)東，劉 江，黃 韜，等.基于節(jié)點介數(shù)和替換率的內(nèi)容中心網(wǎng)絡(luò)網(wǎng)內(nèi)緩存策略[J].電子與信息學(xué)報，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é)報，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].計算機學(xué)報，2012,35(6):1077-1093.

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

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

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

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

[10] 曲 樺，王偉萍，趙季紅.內(nèi)容中心網(wǎng)絡(luò)中一種改進型緩存機制[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ù)測的內(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.