基于層次劃分的CCN網絡緩存存儲策略

李俊，馮宗明,2，吳海博，智江,2

?

基于層次劃分的CCN網絡緩存存儲策略

李俊1，馮宗明1,2，吳海博1，智江1,2

（1. 中國科學院計算機網絡信息中心，北京 100190；2. 中國科學院大學，北京 100049）

針對如何提高內容中心網絡網內緩存性能的問題，提出一種基于層次劃分的輕量協作的緩存存儲策略。該策略通過Interest分組、Data分組以及路由器本地PIT表三者的協作把內容劃分為多種優先級層級，使不同內容緩存在沿途的不同路由器。實驗證明該策略可以有效地減少訪問跳數，提高平均緩存命中率，降低服務器負載。

內容中心網絡；緩存存儲策略；層次劃分；協作存儲

1 引言

CCN網絡是一種在現有互聯網絡工作模式的基礎上，以內容獲取與分發為主要目標的新興網絡體系結構[1,2]。通過對網絡中內容進行唯一命名，部署網內緩存，并采用名字路由機制，CCN網絡可以快速準確地滿足用戶對內容的需求，同時減少網絡流量、降低傳播延遲以及提高傳輸效率。目前，網內緩存技術已成為CCN體系結構的重要組成部分，對于CCN網絡的性能提升具有重要影響。CCN網絡的緩存存儲、緩存發現等一系列緩存可用性相關的研究得到越來越多人的關注。如何提高緩存利用效率是緩存研究的核心問題。目前，國內外已有一些關于緩存存儲策略的研究[3~12]，然而這些方案都存在不同的局限性，有些方案僅僅利用本地緩存處理機制，沒有利用CCN中Interest-Data這種pull傳輸機制的優勢，有的方案旨在求取全局最優的緩存存儲策略，但是這樣需要大量的額外開銷，并且網絡狀況是動態變化的，需要經常去計算，重復開銷也大，這些方案并不能很好地適應CCN網絡。

在綜合分析CCN網絡特性的基礎上，提出一種基于層次劃分的概率存儲方案。其主要目標是高效利用緩存空間、減少網絡延時以及降低服務器負載。通過對用戶請求的內容進行層次劃分，轉發路徑上的各路由器可以對不同層次的內容進行不同的緩存存儲操作，從而實現高效存儲。層次劃分是動態的，根據不同請求路徑沿途各緩存的容量、路徑跳數產生不同的劃分結果。本方案使熱門的內容可以緩存在路徑上的不同位置，而相對冷門的內容就只能緩存在靠近內容源的位置，這有利于熱門內容的訪問以及緩存空間的利用。實驗結果表明所提的方案在多個方面都取得了性能的提升。

本文的主要貢獻如下。

1) 提出了對內容進行層次劃分的方法，并在實驗中實現這種劃分。

2) 結合層次劃分，提出一種基于層次劃分和概率存儲的CCN網絡緩存存儲策略，同時對路徑之上的緩存冗余進行處理。

3) 實驗評價存儲策略的性能，通過與現有的緩存策略對比，實驗結果表明本文的方案對于網絡性能的提升較為明顯。

2 相關工作

CCN網絡中，請求者向內容源發送Interest分組請求內容，內容源接收到Interest請求分組之后會產生相應的Data數據分組滿足Interest請求。當Interest分組請求的內容在中間節點有緩存備份時，中間節點就會返回本地副本內容（Data數據分組）以滿足此次的Interest請求。這就使在設計高效緩存策略時需要考慮如何設定緩存容量、怎樣去放置內容副本等難題。理想情況下，在進行緩存存儲的時候，總是希望熱度高的內容更靠近用戶，即最熱門的內容緩存的位置距離請求者最近，而相對較冷門的內容由于緩存空間的限制只能相對地遠離請求者緩存，即更靠近內容源。由于熱度高的內容會經常被請求，所有大量的高熱度Interest請求會被就近滿足，從而使網絡訪問延時、訪問跳數以及服務器負載都大大降低。

關于緩存存儲的研究主要分為2個方面：路徑之外(off-path)和路徑之上(on-path)緩存存儲策略。

目前現有的off-path緩存存儲策略旨在達到全局最優，需要收集大量的信息，比如請求者位置及請求分布、緩存容量與位置等，這會產生大量的開銷同時并不能保證取得很好效果[7,13]。在文獻[3~6]中提出的幾種緩存存儲策略，都是需要事先收集信息，在此基礎上在進行最優化求解，雖然使用的方法不同但是無一例外都需要大量的額外開銷。同時，網絡環境也會隨時變化，熱門的內容也不是一直熱門，會被新的熱門內容取代，所以在off-path緩存存儲策略下，經常需要重新計算。

相對而言，on-path緩存存儲策略則主要研究怎樣在轉發路徑上緩存特定的內容，即如何在沿途的路由器上緩存內容，以期達到較好性能。文獻[1]中Jacobson等在闡述CCN網絡思想時提出了LCE(leave copy everywhere)的策略，路由器緩存每個經過的內容，當緩存容量被占滿時采用LRU替換策略進行替換。很顯然，LCE策略需要大量的緩存替換操作同時緩存利用率也比較低。文獻[8]中Arianfar等提出一種RAC(random autonomous caching)策略，讓沿途的路由器概率緩存內容，并且路由器緩存的概率是一個常量。RAC并沒有考慮到網內緩存容量、轉發路徑差異等情況，只是比較盲目地進行本地緩存操作。文獻[9]中Psaras等提出ProbCache(probabilistic caching)策略，該策略利用內容轉發路徑上剩余的緩存容量與已取得的路徑收益來計算沿途各路由器緩存該內容的概率。雖然ProbCache利用了路徑的特征，考慮到緩存容量的限制，但是并沒有對網內內容的熱度差異進行考慮。

針對這些問題，提出一種基于層次劃分的緩存存儲策略，充分考慮轉發路徑長度，緩存容量空間與內容熱度分布。

3 層次劃分模型

本節首先介紹如何利用CCN網絡中Interest- Data的傳輸特性去進行內容的層次劃分，之后再介紹路徑上的路由器如何根據層次劃分的結果對經過的內容塊進行緩存操作。

3.1 層次劃分過程

層次劃分過程是利用Interest-Data這種pull傳輸模式完成的。讓Interest請求分組在去往內容源時，沿途記錄請求者到內容源之間的路徑信息，具體包括路徑跳數與沿途各路由器緩存容量，之后對請求者所請求的內容進行優先級層次的劃分。需要用到的參數如下。

CCN網絡中所有的內容都被唯一命名[1],請求者consumer()發出帶有某個內容名字的Interest請求分組請求對應的內容。網內各路由器利用自己的FIB轉發表[14,15]把Interest請求分組轉發給內容源producer()，內容源產生對應的Data數據分組沿Interest請求分組的反向路徑傳遞給請求者。

先利用圖1來說明層次劃分的過程。

圖1所示，請求者發送Interest請求分組向內容源請求相應內容。Interest分組沿途經過1、2、3節點，在Interest分組經過1時會告知節點1其=1，并把1節點的緩存容量1記錄下來。同樣地，Interest分組對后續節點做同樣操作，待其到達內容源時，很容易求得此條路徑上的緩存總容量c。網絡中每個被請求內容的熱度是不一樣的，本文假設網內內容熱度分布服從Zipf分布。如此，各內容都有與之對應的熱度排名，這樣就可以按如下方式把內容劃分成個層次。

不難發現，轉發路徑上路由節點的個數就是劃分的層次數。

3.2 層次劃分必要性

在3.1節中詳細地介紹了層次劃分的方法，下面簡單論證要進行層次劃分的必要性，用以區別不同熱度內容的優先級。

若網內內容滿足Zipf分布，那么某個內容塊被請求的概率為

3.3 緩存存儲策略與去冗余功能

3.3.1 緩存存儲策略

本節在介紹層次劃分方案、層次劃分的必要性之后，詳細闡述利用層次劃分結果對不同優先級的內容進行緩存存儲操作。以圖3為例進行敘述。

圖3中中間路由節點數為3，根據3.1節所述方法，Interest分組到達內容源之后，已走過的跳數為即為4，因此內容會被分為3個層次。讓最熱門的內容即的內容，擁有最高的優先級可以在沿途所有的路由節點概率緩存，而最冷門的內容即的內容僅能在最靠近內容源的路由節點概率緩存，這樣就會形成圖3中的內容緩存情況。前面提到Interest分組沿途會把已經走過的節點數告知當前節點，由此路由器就可以知道自身存儲哪些內容。例如的值為3，其可以緩存所有的內容。的值為2，其可以緩存第1層和第2層內容。的值為1，從而其僅可以緩存第1層的內容。可以發現的值越小，可以緩存的內容越少，而這些少量的內容正是網內熱門的內容。

一般而言，Interest分組到達內容源走過的跳數為，因而把內容分為個層次。沿途的節點根據Interest經過時留下的值可以判斷自身可緩存哪些層次的內容，具體如下。

利用層次劃分方法，為不同熱度的內容區別不同優先級，結合Interest分組的協作，讓路由器可以識別內容的優先級，讓高優先級的內容可以緩存在更靠近請求者的位置，達到了緩存存儲策略的初衷，有效地提高了緩存效益。

3.3.2 去冗余功能

從圖3發現，由于第1層次的內容是高優先級，按照上述概率緩存的方式有可能使節點1、2、3同時對同一個高熱度內容進行了緩存操作。這樣就造成內容副本的冗余，是對緩存空間的浪費。為了避免大量的冗余，應當降低內容副本在靠近內容源的節點3或2緩存的概率。因此，中間節點在緩存內容時依概率緩存，設定此概率為。乘積的前部分表示如果內容熱度排名越高，則被緩存的概率越大，后半部分表示如果Data數據分組從源端走過的距離越小，則內容到達的當前位置越靠近內容源，被緩存的概率越小。這樣就可以降低熱門內容在靠近內容源被緩存的概率，從而避免了過多的冗余。對于第2熱度層次的內容，緩存的概率為，因為第2層次的內容并不能被緩存在1，同理第3層次的內容緩存概率為。

3.3.3 算法描述

前文詳細地對基于層次劃分的CCN網絡緩存策略進行了描述，現在對整個緩存策略的實現進行介紹。圖4中給出了整個算法的實現過程。Interest分組沿途記錄各節點的緩存容量并告知各節點值，Data分組沿著Interest反向路徑回來時攜帶自身所屬的內容層次，路由器接收到Data數據分組之后，會查看自己的值，通過對比決定是否對當前的Data數據分組進行緩存存儲操作。

請求者 1) 設定初始值為0；2) 發出Interest請求分組攜帶 內容源 1) 獲取Interest請求分組當前的值，對內容進行層次劃分得到；2) 產生Data分組攜帶對應的 中間節點 1) IF Interest 請求分組到達；2) 獲取的值，記錄在PIT條目中；3) Interest分組的值加1并轉發請求分組；4) ElSE IF Data請求分組到達5) 獲取其層次信息并查看對應PIT條目中的；6) 對比PIT中記錄的值與當前的內容層次7) IF 8) 概率緩存Data數據分組

3.4 緩存存儲策略的輕量級協作

從上述的介紹可以看出本文提出的緩存存儲策略是一種輕量級協作的策略。首先通過Interest請求分組記錄沿途的跳數信息與緩存信息，并讓路由器的PIT表記錄Interest請求分組走過的路徑跳數，最后Interest請求分組到達內容源之后，把記錄的總跳數以及沿途緩存總容量告知給內容源。內容源產生對應的Data數據分組并賦予其優先級，Data數據分組經過路由器時與本地PIT表進行優先級匹配以決定后續是否進行相應的緩存存儲操作。通過Interest請求分組，路由器本地PIT表以及Data數據分組三者的輕量級協作，便可以完成整個緩存存儲策略，并不需要引入復雜的功能與大量的計算開銷。

4 性能評價

4.1 實驗環境與性能指標

4.1.1 實驗環境

實驗在ndnSIM平臺[16]上進行仿真。ndnSIM平臺基于NS-3[17]，將CCN網絡的功能設計成一個獨立的協議棧，用戶可以方便地配置到節點之上，實現CCN網絡功能部署。為了驗證本緩存方案的性能，本文方案記為HDBC，將HDBC與現有的其他緩存方案進行了性能對比。在本文中呈現與3個方案的對比結果——LCE[1]、RAC[8]、ProbCache[9]。為了保證公平性，對于所有的緩存方案，都采用LRU替換策略。

實驗采用圖5所示的5層完全二叉樹的拓撲結構，指定樹的根節點為內容源，而所有的葉子節點都是請求者。同時指定請求內容服從Zipf分布。在實驗中，通過對以下2個參數值的改變來觀察性能變化趨勢。

4.1.2 性能指標

本文將用以下3個性能指標去衡量緩存策略的優劣。

1) 跳數降低率，可以反映出緩存方案節省的帶寬，其值如下

2) 緩存平均命中率，反映出緩存內容的利用效率，同時也反映出緩存替換操作的多少，其值為

3) 負載降低率，反映緩存的部署對內容源負載降低效果，其值為

4.2 實驗結果與分析

5 結束語

內容中心網絡是一種以內容為中心的新興網絡體系結構，其突出特點之一就是通過網內緩存技術，快速地響應用戶對網絡中內容的請求，同時減少服務器負載、冗余流量。在緩存內容時，總是希望熱度更高的內容在靠近用戶處緩存，使最熱門的內容緩存在離請求者最近的地方，這樣接下來對熱門內容的訪問收益會大幅提高，而較冷門的內容由于緩存空間有限只能遠離請求者緩存，即更靠近內容源。因而本文提出了一種基于層次劃分的CCN網絡緩存存儲策略，把網內內容劃分為不同優先級，讓轉發路徑上的路由器去存儲不同優先級的內容，盡可能地保證更熱門的內容緩存在距離請求者更近的位置，同時對路徑之上的緩存冗余進行了處理。通過實驗與現有的on-path緩存方案的對比，表明本文所闡述的方案各項性能指標較其他方案都有大幅度的提高。接下來需要繼續開展的工作是把方案應用到真實網絡環境，可以進一步利用中國科技網的海云創新實驗環境[18]進行實驗。

[1] ACOBSON V, SMETTERS D K, THORNTON J D, et al. Networking named content[C]//The 5th International Conference on Emerging Networking Experiments and Technologies. ACM, c2009: 1-12.

[2] AHLGREN B, et al. A survey of information-centric networking[J]. Communications Magazine,2012, 50 (7) :26-36.

[3] WANG Y G, et al. Advertising cached contents in the control plane: necessity and feasibility[C]//Computer Communications Workshops (INFOCOM WKSHPS), 2012 IEEE Conference on. c2012: 286-291.

[4] SANG S, BI J, WU J P. Collaborative caching based on hash-routing for information-centric networking[J]. ACM Sigcomm Computer Communication Review, 2013, 43(4): 535-536.

[5] SAIL. NetInf Content Delivery and Operations[R]. SAIL Project, SAIL Project Deliverable D-3.2, 2011.

[6] SOURLAS V, FLEGKAS P, PASCHOS G S, et al. Storage planning and replica assignment in content-centric publish/subscribe networks[J]. Computer Networks, 2011, 55(18): 4021-4032.

[7] REN J, QI W, et al. MAGIC: a distributed max-gain in-network caching strategy in information-centric networks[C]//Computer Communications Workshops (INFOCOM WKSHPS), 2014 IEEE Conference on. c2014: 470-475.

[8] ARIANFAR S, NIKANDER P, OTT J. On content-centric router design and implications[C]//Proc of ReARCH Workshop. New York, NY, USA, c2010: 1-6.

[9] PSARAS I, CHAI W K, PAVLOU G. Probabilistic in-network caching for information-centric networks[C]//Proc of ICN Workshop on Information Centric Networking. New York, NY, USA, c2012: 55-60.

[10] MING Z X, XU M W, WANG D. Age-based cooperative caching in information-centric networks[C]//Computer Communications Workshops (INFOCOM WKSHPS), 2012 IEEE Conference on. c2012: 268-273.

[11] CHAI W K, HE D, PSARAS I, et al. Cache less for more in information-centric networks[C]//Networking 2012, Ser Lecture Notes in Computer Science. c2012: 27–40.

[12] EUM S,et al. CATT: potential based routing with content caching for ICN[C]//The Second Edition of the ICN Workshop on Information-centric Networking. c2012.

[13] WANG Y, LEE K, VENKATARAMAN B, et al. Advertising cached contents in the control plane: Necessity and feasibility[C]//Proc. of IEEE INFOCOM WKSHPS. c2012: 286-291.

[14] HOQUE A K M, AMIN S O, ALYYAN A, et al. Nlsr: named-data link state routing protocol[C]//The 3rd ACM SIGCOMM Workshop on Information-centric Networking. ACM, c2013: 15-20.

[15] WANG L, HOQUE A K M, YI C, et al. OSPFN: An OSPF Based Routing Protocol for Named Data Networking[R].University of Memphis and University of Arizona, 2012.

[16] ALEXANDER A, MOISEENKO I, ZHANG L X. ndnSIM: NDN simulator for NS-3 Named Data Networking (NDN) Project[R]. 2012.

[17] HENDERSON T R, et al. ns-3 project goals[C]//The 2006 Workshop on ns-2: the IP Network Simulator. ACM, c2006.

[18] SCIE project [EB/OL]. http://scie.ac.cn/view/scie.jsp.

Hierarchical division-based cache storage strategy in content-centric networking

LI Jun1, FENG Zong-ming1, 2, WU Hai-bo1, ZHI Jiang1, 2

(1. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China; 2. University of Chinese Academy of Sciences, Beijing 100049, China)

For the issue of improving the performance of in-network cache in content-centric networking, a hierarchical division-based lightweight collaboration cache storage strategy was proposed. According to the strategy, content was grouped into different hierarchies by the cooperation of Interest package, Data package and the local PIT of routers, so that the contents could be cached in different nodes along the delivery path. The performance of the scheme was evaluated by comparing with the well-known schemes through simulation. Experimental results indicate that the scheme has good performance in reducing access hops, increasing the average cache hit ratio and reducing the server load.

content-centric network, cache strategy, hierarchical division, collaborative caching

TP393

A

10.11959/j.issn.1000-436x.2016005

2015-01-10；

2015-04-30

中國科學院計算機網絡信息中心“135”規劃重點培育方向專項基金資助項目（No.CNIC_PY_1401）；國家重點基礎研究發展計劃（“973”計劃）基金資助項目（No.2012CB315803）；中國科學院知識創新工程青年人才領域基金資助項目（No.CNIC_QN_1303, No.CNIC_QN_1508）；中國科學院計算機網絡信息中心主任基金資助項目（No.CNIC_ZR_201204）

Five Top Priorities of“One-Three-Five”Strategic Planning, CNIC (No.CNIC_PY-1401), The National Basic Research Program of China (973 Program) (No.2012CB315803), Knowledge Innovation Program, CAS (No.CNIC_QN_1303, No.CNIC_QN_1508); Director Fund, CNIC (No.CNIC_ZR_201204)

李俊（1968-），男，安徽桐城人，博士，中國科學院計算機網絡信息中心研究員、博士生導師，主要研究方向為下一代互聯網、網絡安全等。

馮宗明（1989-），男，安徽馬鞍山人，中國科學院大學碩士生，主要研究方向為下一代互聯網關鍵技術。

吳海博（1981-），男，山東泰安人，博士，中國科學院計算機網絡信息中心助理研究員，主要研究方向為下一代互聯網緩存技術。

智江（1983-），男，山西太原人，中國科學院大學博士生，主要研究方向為下一代互聯網關鍵技術。