基于節點介數和替換率的內容中心網絡網內緩存策略

崔現東 劉 江 黃 韜 陳建亞 劉韻潔

?

基于節點介數和替換率的內容中心網絡網內緩存策略

崔現東*①劉 江①黃 韜①陳建亞②劉韻潔①③

①(北京郵電大學泛網無線通信教育部重點實驗室 北京 100876)②(北京郵電大學北京市網絡體系構建與融合重點實驗室 北京 100876)③(南京(中國)未來網絡產業創新中心 南京 211100)

網內緩存技術是內容中心網絡(CCN)的關鍵技術之一，CCN采用傳統的ALWAYS緩存策略，會造成較大冗余。改進的Betw方案僅考慮了節點介數，容易造成高介數節點緩存更替頻繁，內容可用性下降。為了解決這個問題，該文提出一種綜合使用網絡節點介數和節點緩存內容更替速率作為緩存決策度量的新型網內緩存策略BetwRep，通過權衡節點位置重要性和緩存內容時效性實現回傳內容的最佳放置。最后，基于ndnSIM平臺進行的網絡仿真表明，該文提出的BetwRep緩存策略取得了比Betw方案和ALWAYS方案更低的源端請求負載和更少的平均跳數。

內容中心網絡；網內緩存技術；BetwRep緩存策略；節點介數；緩存替換率

1 引言

基于以上方案存在的問題，本文提出了一種綜合使用網絡節點介數和節點緩存內容更替率作為緩存決策度量的新型網內緩存策略BetwRep。在返回內容判決路徑上哪些節點需要緩存該內容時，既考慮節點的重要性，又要考慮節點緩存內容更替狀況。該策略既有效保證了內容盡量緩存在相對重要的節點上，又能通過節點的內容替換率來調控內容的緩存，使重要節點避免處于高頻率的內容替換狀態而導致系統性能下降。

文章組織結構如下。第2節介紹CCN路徑緩存模型以及相關技術；第3節重點闡述了本文提出的BetwRep緩存判決策略；第4節詳細描述了仿真環境、方案和參數的配置，并對仿真結果進行分析；第5節是結束語。

2 CCN路徑緩存模型和相關技術

2.1 系統模型

2.2 ALWAYS與Betw路徑緩存策略分析

文獻[10]提出的Betw緩存策略，請求命中后將返回內容只緩存在分發路徑最重要的節點上。由于在重要節點上，同一個內容被請求的次數會更多，使得內容在節點被緩存時間變長，這在某種程度上減緩了節點的緩存更替壓力。而節點重要程度以介數作為度量，介數是節點介數中心性的簡稱[12,13]，用來描述節點在網絡中重要性的一個度量，源于復雜網絡領域，其數學定義如下：

然而，網絡中節點緩存大小與系統內容總量相比非常小[14]，因此，重要節點到達的請求和經過的內容量都極為龐大，最流行的內容也會出現很快就被替換的情況，此時大量的興趣包到達重要節點后，無法實現緩存命中，興趣包也只能被轉發到別的節點，直至內容源端。

3 基于節點介數和緩存更替率的BetwRep緩存策略

3.1 BetwRep緩存策略核心思想

CCN網絡中如果一個節點位于多個內容分發路徑上，便會有更多的興趣包和內容包經過，則在該節點上更容易發生內容請求緩存命中。文獻[10]提出的內容緩存算法選擇介數作為度量，將返回內容只緩存在路徑最重要的節點上。由于在重要節點上，同一個內容被請求的次數會更多，使得內容在節點被緩存時間變長，這在某種程度上減緩了節點的緩存更替壓力。

本文目標是設計能取得高收益的網內緩存策略，并驗證系統在不同緩存策略下的網絡緩存性能。Betw緩存策略用來判決請求內容在返回路徑上如何緩存，但由于Betw策略選取緩存節點只考慮節點的重要性，而網絡中節點緩存大小遠小于系統內容總量[14]，大量的請求和內容到達重要節點，導致重要節點內容替換頻繁，使得流行內容在節點中的緩存時間變短，最后致使網內緩存命中率下降。另一個方面，作為網絡層的技術，CCN的節點內容緩存和數據轉發要求達到線性處理速度，如果出現上述情況，節點處理包的壓力將會陡增，給網絡帶來擁塞。

圖1 ALWAYS, Betw和BetwRep緩存策略實例

3.2 BetwRep緩存策略的實現

4 仿真分析

為驗證本文提出的BetwRep緩存策略對于CCN網絡性能的提升，本文通過ndnSIM[15,16]仿真器實現了對Betw, ALWAYS和BetwRep 3種緩存策略的仿真，并對它們的性能進行了定量的比較和分析，仿真結果驗證了BetwRep緩存策略的有效性。

4.1仿真環境和參數配置

表1節點興趣包偽代碼

Pseudocode I 興趣包處理偽代碼:Initialize (serialsB(v)=[0,,0],Re(v)=[0,,0]))Initialize (serials Betw(v)=[0,,0],Repl(v)=[0,,0])for each (vkfrom i to j )If data in cache || entry in PIT Get B(v),Re(v)Calculate Betw(v), Repl(v)Calculate vk= arg max{M(v)}B=B(vk)If data in cachethen send(data)else create () discard interest_packetelse Get B(vk), Re(vk)B(v)k=B(vk),Re(v)k=Re(vk)forward request to the next hop towards jPseudocode II 數據包處理偽代碼:Record Betw from corresponding content requestfor each (vkfrom j to i )Get B(vk), if B== B(vk) &&0==Dthen cache(data)else if !=NULLin face = send(data)elseforward data packet to the next hop toward

請求轉發方式選擇洪泛模式，節點緩存替換策略選擇LRU。根據CCN的通信機制，節點具有興趣包的聚合特性，返回內容沿著組播樹分發，因此仿真網絡選擇樹狀拓撲結構，本文選取一個深度為7，總節點數為17的隨機樹狀拓撲。

4.2 仿真結果分析

圖2 網絡緩存性能與節點緩存大小關系圖

圖3 網絡即時緩存性能圖

5 結束語

為了解決內容中心網絡中返回內容在請求路徑上如何選擇緩存節點的問題，本文將節點的內容緩存替換率和節點介數作為參數構造出一個新的度量，以此提出了一個新的BetwRep緩存策略。該策略避免了ALWAYS策略帶來的大量緩存冗余，同時克服了Betw緩存策略中節點選取只考慮節點的重要性而導致重要節點內容替換頻繁，流行內容在節點中緩存時間變短的缺點。通過對3種方案兩個性能指標平均跳數和內容源端命中率的對比發現，本文提出的BetwRep緩存策略，性能比Betw策略有了5%的提高，相比ALWAYS策略性能提高更加顯著。在后續工作中，我們將在本文基礎上通過引入內容的流行度，設計出基于概率的緩存策略。

[1] Jacobson V, Smetters D K, Thornton J D,.. Networking named content[C]. Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies, Rome, December 1-4, 2009: 1-12.

[2] Yi C, Afanasyev A, Wang L,.. Adaptive forwarding in named data networking[J]., 2012, 42(3): 62-67.

[3] Kideok Cho, Lee Mun-young, Park Kun-woo,.. WAVE: popularity-based and collaborative in-network caching for content-oriented networks[C].IEEE Conference on Computer Communications (INFOCOM WKSHPS), Workshops, Orlando, March 25-30, 2012: 316-321.

[4] Dan A and Towsley D. An approximate analysis of the lru and fifo buffer replacement schemes[C].Proceedings of the 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, Boulder, May 22-25, 1990: 143-152.

[5] Leet Dong-hee, Choit Jong-moo, Kim Jong-hun..On the existence of a spectrum of policies that subsumes the Least Rrecently 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, May 1-4, 1999: 134-143.

[6] Jelenkovic P, Radovanovic A, and Squillante M S. Critical sizing of lru caches with dependent requests[J].y, 2006, 43(4): 1013-1027.

[7] Lee Breslau, Pei Cao, Li Fan.. Web caching and Zipf-like distributions: evidence and implications[C]. Proceedings of INFOCOM’99, Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies, NewYork, March 21-25, 1999: 126-134.

[8] Laoutaris N, Syntila S, and Stavrakakis I. Meta algorithms for hierarchical web caches[C]. Proceedings of the IEEE International Performance Computing and Communications Conference (IEEE IPCCC), Phoenix, April 15-17, 2004:445-452.

[9] Chai Wei-koong, He Di-liang, Ioannis P,Cache “Less for More” in information-centric networks[C]. Proceedings of the 11th International IFIP TC 6 Conference on Networking, Prague, May 21-25, 2012: 27-40.

[10] Chai Wei-koong, He Di-liang, Ioannis P,Cache “Less for More” in information-centric networks (extended version)[J]., 2013, 36(7): 758-770.

[11] Ghodsi A, Koponen T, Raghavan B,Information- centric networking: seeing the forest for the trees[C]. Proceedings of the 10th ACM Workshop on Hot Topics in Networks, Cambridge, Massachusetts, November 14-15, 2011: 1-6.

[12] Goh K, Oh E, Kahng B,.. Betweenness centrality correlation in social networks[J]., 2003, 67(1): 1-4.

[13] Izquierdo L R and Hanneman R A. Introduction to the formal analysis of social networks using mathematics[OL]. http://www.luis.izquierdo.name, 2006.

[14] Rossi D and Rossini G. Caching performance of content centric networks under multi-path routing (and more)[R]. Technical Report, Telecom ParisTech, 2011.

[15] Afanasyev A, Moiseenko I, and Zhang L. ndnSIM: NDN simulator for NS-3[R]. Technical Report, NDN-0005, NDN Project (July 2012).

[16] University of California, Los Angeles. NS-3 based Named Data Networking (NDN) simulator[OL]. http://ndnsim. net/, 2012.

[17] Tsinghua University, P. R. China. ndn-consumer-zipf- mandelbrot[OL]. http://ndnsim.net/doxygen/ ndn- consumer-zipf-mandelbrot_8cc_source.html, 2012.

崔現東： 男，1980年生，博士生，研究方向為未來網絡關鍵技術、內容中心網絡.

劉 江： 男，1983年生，講師，研究方向為網絡虛擬化、內容中心網絡.

黃 韜： 男，1980年生，副教授，研究方向為路由與交換、內容中心網絡.

陳建亞： 男，1951年生，教授，研究方向為下一代網絡、路由與交換.

劉韻潔： 男，1943年生，中國工程院院士，博士生導師，主要研究領域為未來網絡、網絡融合等.

A Novel In-network Caching Scheme Based on Betweenness and Replacement Rate in Content Centric Networking

Cui Xian-dong①Liu Jiang①Huang Tao①Chen Jian-ya②Liu Yun-jie①③

①(,,,100876,)②(,,100876,)③(,211100,)

In-network caching is one of the key aspects of Content Centric Networking (CCN), which is widely concerned recently. However, the ALWAYS caching scheme (caching everywhere on the delivery path) in CCN produces a great of redundancy, while the Betw scheme leads to that the node has the more frequent replacement with the larger betweenness centrality, which will decrease the availability of the content. In this paper, a novel in-network caching scheme named BetwRep is proposed based on a metric including the betweenness centrality and the replacement rate of one node to address the problem-where to cache along the delivery path. Simulation experiment based on ndnSIM demonstrates that the BetwRep caching scheme achieves the lower loading in the source server and less average hops than that of Betw scheme and ALWAYS scheme.

Content Centric Networking (CCN); In-network caching; BetwRep caching scheme; Betweenness centrality; Replacement rate

TP393

A

1009-5896(2014)01-0001-07

10.3724/SP.J.1146.2013.00503

2013-04-16收到，2013-07-29改回

國家973計劃項目(2012CB315801, 2011CB302901)和中央高校基本科研業務費專項資金(2013RC0113)資助課題

崔現東 cuixdbupt@gmail.com