基于節(jié)點介數(shù)和替換率的內(nèi)容中心網(wǎng)絡(luò)網(wǎng)內(nèi)緩存策略

崔現(xiàn)東 劉 江 黃 韜 陳建亞 劉韻潔

?

基于節(jié)點介數(shù)和替換率的內(nèi)容中心網(wǎng)絡(luò)網(wǎng)內(nèi)緩存策略

崔現(xiàn)東*①劉 江①黃 韜①陳建亞②劉韻潔①③

①(北京郵電大學(xué)泛網(wǎng)無線通信教育部重點實驗室 北京 100876)②(北京郵電大學(xué)北京市網(wǎng)絡(luò)體系構(gòu)建與融合重點實驗室 北京 100876)③(南京(中國)未來網(wǎng)絡(luò)產(chǎn)業(yè)創(chuàng)新中心 南京 211100)

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

內(nèi)容中心網(wǎng)絡(luò)；網(wǎng)內(nèi)緩存技術(shù)；BetwRep緩存策略；節(jié)點介數(shù)；緩存替換率

1 引言

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

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

2 CCN路徑緩存模型和相關(guān)技術(shù)

2.1 系統(tǒng)模型

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

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

然而，網(wǎng)絡(luò)中節(jié)點緩存大小與系統(tǒng)內(nèi)容總量相比非常小[14]，因此，重要節(jié)點到達的請求和經(jīng)過的內(nèi)容量都極為龐大，最流行的內(nèi)容也會出現(xiàn)很快就被替換的情況，此時大量的興趣包到達重要節(jié)點后，無法實現(xiàn)緩存命中，興趣包也只能被轉(zhuǎn)發(fā)到別的節(jié)點，直至內(nèi)容源端。

3 基于節(jié)點介數(shù)和緩存更替率的BetwRep緩存策略

3.1 BetwRep緩存策略核心思想

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

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

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

3.2 BetwRep緩存策略的實現(xiàn)

4 仿真分析

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

4.1仿真環(huán)境和參數(shù)配置

表1節(jié)點興趣包偽代碼

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 數(shù)據(jù)包處理偽代碼: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

請求轉(zhuǎn)發(fā)方式選擇洪泛模式，節(jié)點緩存替換策略選擇LRU。根據(jù)CCN的通信機制，節(jié)點具有興趣包的聚合特性，返回內(nèi)容沿著組播樹分發(fā)，因此仿真網(wǎng)絡(luò)選擇樹狀拓撲結(jié)構(gòu)，本文選取一個深度為7，總節(jié)點數(shù)為17的隨機樹狀拓撲。

4.2 仿真結(jié)果分析

圖2 網(wǎng)絡(luò)緩存性能與節(jié)點緩存大小關(guān)系圖

圖3 網(wǎng)絡(luò)即時緩存性能圖

5 結(jié)束語

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

[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.

崔現(xiàn)東： 男，1980年生，博士生，研究方向為未來網(wǎng)絡(luò)關(guān)鍵技術(shù)、內(nèi)容中心網(wǎng)絡(luò).

劉 江： 男，1983年生，講師，研究方向為網(wǎng)絡(luò)虛擬化、內(nèi)容中心網(wǎng)絡(luò).

黃 韜： 男，1980年生，副教授，研究方向為路由與交換、內(nèi)容中心網(wǎng)絡(luò).

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

劉韻潔： 男，1943年生，中國工程院院士，博士生導(dǎo)師，主要研究領(lǐng)域為未來網(wǎng)絡(luò)、網(wǎng)絡(luò)融合等.

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)和中央高?；究蒲袠I(yè)務(wù)費專項資金(2013RC0113)資助課題

崔現(xiàn)東 cuixdbupt@gmail.com