基于內容流行度和節點重要度的CCN緩存策略

鄭凱月，潘沛生

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

0 引 言

隨著互聯網技術的發展，以IP為基礎的TCP/IP網絡體系架構逐漸暴露出諸多問題，比如可擴展性較差、安全可控性低、移動性支持不足、服務質量難以保證等。互聯網用戶行為也發生變化，轉變為關注數據的內容而不是關注服務器和主機IP地址，因此如何更快、更準確、更高效地獲取數據成為下一代網絡研究的熱點問題。

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

(1)LCE策略要求內容在分發路徑的所有節點都緩存，這樣會導致網絡中緩存節點空間的浪費和緩存內容的冗余。

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

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

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

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

1 基于內容流行度和節點中心度的緩存機制

1.1 設計思想

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

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

圖1 緩存決策實例

1.2 內容流行度和節點中心度的計算

1.2.1 內容流行度

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

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

(1)

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

1.2.2 節點中心度

將節點中心度量化為節點介數，即Betw介數緩存方法提出的節點介數計算方法，節點介數表征節點的重要程度，也就是與該節點相關聯的鏈路條數[12]。

在CCN網絡中，有多個內容分發路徑要經過同一個路徑節點，那么這個節點在網絡中的重要度就比較高，即中心度高。文獻[1]給出了節點介數的定義：

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

(2)

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

在Betw算法中，使用的路由轉發算法是最短路徑算法，所以文中只統計節點間最短路徑的數目。

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

設A是自我中心網絡G的N×N對稱鄰接矩陣：

(3)

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

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

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

表1 內容流行度排名表

1.4 算法描述

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

Pseudocode Ι興趣包到達CCN節點時算法：

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 Π數據包到達節點時執行的緩存策略:

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(新到達內容流行度)>Pmax)

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

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

DeletePmincontent CacheP[n]newcontent inVk

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

RemovePmincontent toVk

CacheP[n]newcontent inVk

2 仿真分析

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

圖2和圖3是在不同CS緩存容量下(CS單位為塊chunk)四種緩存策略的性能圖。圖2是網絡源端命中率，內容源端命中率越低，表示中間節點和邊緣節點發揮作用越大，緩存性能越好。可以看出，四種緩存策略在CS逐漸變大的情況下，都會出現源端命中率逐漸遞減的結果，與其他三種策略相比，corporate策略源端命中率更低，性能更好。圖3是獲取請求內容所需要經過的平均跳數，可見corporate策略性能最好，在CS比較小時由于該策略較其他策略的優越性，會出現快速遞減趨勢，隨后遞減的趨勢趨于穩定。

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

圖2 網絡源端命中率

圖3 網絡拓撲中獲取內容平均跳數

圖4 網絡中緩存內容的命中率

圖5 網絡拓撲中獲取內容的平均跳數

3 結束語

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

參考文獻：

[1] 崔現東，劉 江，黃 韜，等.基于節點介數和替換率的內容中心網絡網內緩存策略[J].電子與信息學報，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] 朱 軼，糜正琨，王文鼐.一種基于內容流行度的內容中心網絡緩存概率置換策略[J].電子與信息學報，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] 林 闖，賈子驍，孟 坤.自適應的未來網絡體系架構[J].計算機學報，2012,35(6):1077-1093.

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

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

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

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

[10] 曲 樺，王偉萍，趙季紅.內容中心網絡中一種改進型緩存機制[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 “less for more” in information-centric networks(extended version)[J].Computer Communications,2013,36(7):758-770.

[13] 董美姣.基于內容流行度預測的內容中心網絡緩存技術研究[D].北京：北京郵電大學，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.