內容中心網絡中基于內容遷移的協作緩存機制

羅 熹 安 瑩 王建新 劉 耀

?

內容中心網絡中基于內容遷移的協作緩存機制

羅 熹①③安 瑩*②王建新①劉 耀④

①(中南大學信息科學與工程學院 長沙 410083)②(中南大學湘雅醫學院 長沙 410013)③(湖南警察學院信息技術系 長沙 410138)④(湖南商學院計算機與信息工程學院 長沙 410205)

內容中心網絡(CCN)是為了適應未來網絡通信模式的轉變，提供對可擴展和高效內容獲取的原生支持而提出一種新型的網絡體系架構，內容緩存機制是其研究的關鍵問題之一。現有機制在緩存節點的選擇時往往過于集中，緩存負載分布嚴重不均，大大降低了網絡資源利用率以及系統的緩存性能。該文提出一種基于緩存遷移的協作緩存機制，首先在緩存節點選擇時考慮節點的中心性保證內容盡可能緩存在位置更重要的節點。同時，在緩存壓力過大時，通過可用緩存空間大小、緩存替換率以及網絡連接的穩定性等信息選擇合適的鄰居節點進行緩存內容的轉移，充分利用鄰居資源實現負載分擔。仿真結果表明該機制能有效地改善緩存負載在節點上分布的均衡性，提高緩存命中率和緩存資源利用率并降低平均接入代價。

內容中心網絡；協作緩存；負載均衡；內容遷移

1 引言

隨著互聯網技術和應用的不斷發展，網絡需求已經從最初的計算資源共享演變為主機到網絡海量信息的訪問，內容服務逐漸成為網絡服務的主體。為了適應從發送方驅動的端到端通信向接收方驅動的內容獲取方式的轉變，近年來研究者們提出了以內容為中心的新型網絡架構。作為其中的典型代表，內容中心網絡(Content-Centric Networking, CCN)[3]成為了當前下一代網絡架構研究的熱點。為了緩解網絡流量的快速增長對網絡帶寬造成的嚴峻壓力，提高網絡資源的利用率，CCN緩存機制的研究受到了學術界極大的重視。

當前CCN采用LCE(Leave Copy Everywhere)[4]作為默認的緩存策略，然而這種對經過的所有內容都進行緩存的策略容易造成過大的內容冗余，并降低內容的多樣性。隨后，大量學者提出了一系列的選擇性緩存算法，依據一定的條件從網絡中選擇部分節點進行內容緩存，以求降低緩存冗余并達到較高的緩存命中率(即用戶請求由中間節點緩存響應的概率)。如，Cho等人[5]提出了WAVE緩存機制，根據內容的流行度調整每個節點緩存的chunk數目，并由上游節點通過顯式標記向下游節點給出需要緩存的chunk數目建議。文獻[6]提出了內容年齡的概念，通過為位于網絡邊緣且流行度較高的內容設置較長的年齡，驅動流行內容向網絡邊緣的緩存，從而減少網絡流量和內容獲取延遲。基于內容流行度的策略試圖將較流行的內容推向用戶端以提高緩存命中率，然而由于缺乏對節點間聯系的相關特征以及節點重要性的考慮，大大影響了這類策略的執行效果。其他類似的改進算法還包括文獻[7-9]。

考慮到網絡中節點位置的重要性，Chai等人[10]提出一種基于中心性的選擇性緩存決策算法Betw。它將節點介數定義為經過該節點的所有最短路徑的數量占網絡中最短路徑總數的比例，然后利用介數作為衡量標準，在興趣包沿途中選擇重要性更高的節點進行內容緩存，從而在獲得較高緩存命中率的同時減少了內容的轉發跳數。然而，該算法使得內容集中緩存在大介數節點上，而小介數節點的緩存資源則得不到充分利用。這種嚴重的分布不均導致部分節點緩存內容的更替過于頻繁，必然造成緩存命中率的下降，極大地削弱了前期緩存為后續請求提供快速響應的積極作用。不少學者就此提出了一些改進方案，如文獻[11]提出的ProbCache策略，它設計了一種基于加權概率的緩存決策算法，使內容返回路徑中各節點緩存內容的概率反比于節點和請求者之間的距離。由于未考慮內容的流行度，不同內容對象在邊緣節點處存在激烈的競爭，因而算法的性能受到一定的影響。此外，文獻[12]則試圖綜合網絡節點介數和內容替換率來選擇內容的最佳緩存位置。但是從這些策略的實際效果來看，作用都非常有限。

針對上述問題，本文提出了一種基于內容遷移的協同緩存機制(Cooperative Caching Mechanism with Content Migration, CCMCM)。一方面根據節點的中心性，選取位于重要位置的網絡節點進行內容緩存。另一方面，以高中心性節點為緩存中心，將其一跳鄰居范圍劃定為一個緩存區域。在中心節點緩存壓力較大時，合理地選擇部分內容轉移到鄰居節點，利用整個區域的節點資源共同分擔內容的緩存需求。這樣既保證內容盡量緩存在重要節點附近，同時又充分利用了鄰居節點的資源來均衡緩存負載的分布，有效地降低了緩存內容的替換率，提高了緩存命中率和網絡資源的利用率。

2 CCMCM緩存機制

文獻[10]指出節點重要性對于緩存決策具有重要的意義，因此我們采用自我中心網絡(ego network)的介數中心性作為節點重要性的量化指標。然而為了緩解高中心性節點的緩存壓力，提高內容緩存分布的均勻性，我們并非將全部的內容都緩存在高中心性節點上，而是選擇高中心性節點為中心的一跳范圍作為緩存區域，在高中心性節點緩存緊張時把部分內容轉移到區域內的其他節點，充分利用整個區域的緩存能力實現負載分擔，從而降低緩存替換頻率，提高緩存命中的概率。下面詳細描述CCMCM機制的工作原理。

首先，CCMCM機制中的每一個路由節點仍然維護著3個數據結構：前向轉發表(Forwarding Information Base, FIB)、待定請求表(Pending Interest Table, PIT)以及內容存儲器(Content Store, CS)。但是與CCN中的一般情況不同，我們將CS進一步劃分為普通內容存儲區(Common Content Store, CCS)和內容索引存儲區(Content Index Store, CIS)兩部分。CCS占整個節點緩存的絕大部分空間，用來緩存完整的內容分組。而CIS僅存儲內容對象相關緩存位置信息的索引，用來記錄內容的緩存節點及其相應的訪問路徑。

用戶通過發送請求分組來請求所需的內容，每個節點會計算自己的自我中心網絡介數值，同時在請求分組中記錄其傳播路徑上的節點最大介數值。在某個節點發生緩存命中時，命中節點將從請求分組上獲得的介數最大值寫入到內容的數據分組中。在數據分組沿著反向路徑傳回用戶端的過程中，沿途各節點會將自己的介數值與數據分組中記錄的最大值作比較并做出相應的緩存決策。若二者相等表明當前節點即為該路徑上介數中心性最高的節點，則該節點被選為緩存中心節點(Caching Center, CC)，而將其構成的自我中心網絡稱為內容緩存區域(Caching Area, CA)。當CC緩存空間充足時，數據分組直接緩存在其CCS內；若CC緩存占用率超過某個臨界值時，則對本地CCS中的內容進行篩選，從中挑選部分內容轉移到鄰居節點上，同時在其CIS中建立該內容存儲位置的索引信息。我們把這類需要轉移出去的內容稱為轉存內容，將接收并緩存了某個轉存內容的節點稱為該內容的轉存節點，而內容索引存儲區中的索引信息則稱之為轉存內容索引。在轉存內容索引中包含了轉存內容的名稱、轉存節點名稱以及相應的轉發接口等信息。根據內容的名稱，若在CIS中發現與某個請求分組匹配的轉存內容索引條目，則CC可以將該請求分組通過轉存內容索引中記錄的轉發接口發往轉存節點來實現緩存命中。

2.1轉存節點的選擇

為了保證內容對象轉移到其他節點后的可用性，在選擇轉存節點時主要考慮兩方面的因素，其一是節點的緩存狀態，即選擇的轉存節點是否具有足夠的空間緩存轉存內容以及能否提供較長的緩存時間；其二是轉存節點與緩存中心節點網絡連接的穩定性，即二者之間是否能保持較穩定的連接鏈路，以保證利用緩存中心節點記錄的內容位置索引有較大概率實現緩存命中和內容返回。

首先我們引入節點緩存替換率的概念，記為Rep()，并將其定義為單位采樣時間內節點緩存中被替換內容的大小與其緩存總容量的比值，以此作為節點緩存狀態的衡量指標。Rep()的計算方法如式(1)所示。

其中，(M)表示節點中被替換的內容M的大小，為單位時間內節點緩存中替換的內容個數，()則是節點的緩存總容量。我們應盡可能將轉存內容遷往內容替換率較低的節點，以避免其被過快地替換。

同時，我們將緩存中心節點與其任意鄰居節點間鏈路連接的穩定性定義為采樣周期內節點間鏈路的連接時間所占的比例，記為Stab()，計算公式為

其中t為鏈路的連接時長，T為采樣時長。我們盡量選擇與緩存中心節點連接穩定性更高的節點進行內容轉移以提高被轉移內容對象的可用性。

當需要進行緩存內容的轉移時，緩存中心節點將分別計算其各個鄰居節點的選擇權重因子，然后從中選擇權重值最大的節點作為內容的轉存節點。

2.2轉存內容的選擇

為了通過恰當的內容遷移實現有效的鄰域協同緩存，緩存中心節點首先檢測并消除當前緩存區域內的冗余內容，然后根據內容的流行度來選擇合適的轉存內容。具體過程描述如下：

(1)節點根據流行度對CCS中緩存的所有內容按升序進行排序；

(2)若緩存中心節點與其鄰居間存在冗余內容且冗余內容流行度低(排在緩存中心節點緩存內容隊列的前50%)，則直接刪除緩存中心節點上的冗余內容副本；反之，刪除鄰居節點上的冗余副本。若鄰居節點間存在冗余，則選擇刪除緩存替換率較高的節點上的冗余副本；

2.3 轉存內容索引的更新與替換

在CCMCM機制中，節點接收到的內容分組可能源自兩種情況，一種是源自內容分發機制產生的正常內容傳輸，由其他節點轉發而來的普通內容分組；另一種則來自緩存決策機制觸發的內容轉移存儲行為。為了區分這兩種不同來源的內容分組，我們在每個內容分組的頭部增加了一個1 bit的轉存標志位Ft。該標志位初值設為0，表示內容為普通內容分組。而該標志位被置為1時，表示該內容分組為轉存分組。當節點緩存不足時，節點對普通內容分組均采用優先舍棄低流行度內容的方式進行替換。然而如果涉及到轉存內容分組，則需考慮其對應的轉存索引信息的更新或替換，我們分以下幾種情況進行處理：

(1)由于轉存節點N的移動或關機，其與緩存中心節點N的連接即將中斷。

此時，N將其緩存中的所有轉存內容向N進行主動通告，若N緩存空間充足，則直接取回轉存內容；否則N比較轉存內容與自身緩存內容的流行度，保留其中流行度較高的內容并刪除對應的轉存內容索引。

(2)由于轉存節點N緩存不足，根據緩存替換算法某個流行度最低的轉存內容M需被替換。

此時，N將向N發送包含M信息的緩存替換通告。若N緩存空間充足，則直接將M取回并將Ft復位，同時移除M對應的轉存內容索引；若N緩存已滿，則根據M的流行度執行相應的替換操作。

(3)緩存中心節點N的CIS空間不足。

此時，N根據流行度替換流行度最低的轉存內容的索引，并通過轉存節點將對應內容的F復位。

3 仿真實驗及性能分析

3.1仿真環境與性能參數

為了證明CCMCM緩存機制在緩存性能上的優勢，我們選擇了處處緩存的LCE策略和基于介數的Betw策略作為CCMCM性能比較的對象，并利用ndnSIM[13]模擬器實現了以上3種策略的性能仿真。仿真實驗中我們利用GT-ITM生成了一個由50個路由節點組成的隨機網絡拓撲。默認情況下，網絡中內容對象總數為2000個，內容大小服從[0.1 MB, 1.9 MB]區間上的均勻分布，轉存內容索引分組的大小均為1 kB。節點緩存初始為空，緩存大小均為10 MB，其中CIS占整個緩存空間大小的1%。用戶請求的到達過程服從=10個/s的泊松分布，用戶的訪問模式服從參數=0.7的Zipf分布。同時，請求分組采用洪泛方式進行轉發，緩存替換策略默認為LRU。在無特殊說明時，各實驗參數均取默認值。本文采用的主要性能評估指標包括：

(1)緩存命中率：被定義為用戶請求由緩存而非原始內容服務器響應的概率。

(2)緩存負載分布：通過統計節點的累積緩存內容數量(即各節點被選中為緩存節點的次數)來分析各緩存機制對緩存負載分布均衡性的影響。

3.2仿真實驗結果

3.2.1緩存命中率 本小節首先研究采用不同緩存策略時系統緩存命中率隨網絡參數變化的情況。由圖1(a)可見，隨著節點緩存容量的增加，3種機制的緩存命中率都呈現增長的趨勢。這是由于節點緩存空間增加使得內容分組的緩存時間延長，從而提高了緩存命中率。其中，CCMCM充分利用鄰居節點緩存資源進行有效地轉移存儲，緩解了高中心性節點的緩存壓力，從而獲得了三者中最高的緩存命中率。在節點緩存不變時，內容數量的增加使得緩存資源更加稀缺。因此如圖1(b)所示，3種機制的緩存命中率均隨內容數量的增加明顯下降，但CCMCM的緩存命中率始終優于其他二者。圖1(c)反映了Zipf參數不同時各緩存機制的緩存命中率情況。由于Zipf參數越大表明用戶對內容的偏好越集中于高流行度的內容，而3種機制的緩存放置策略以及基于LRU的緩存替換策略均傾向于保證高流行度內容在網絡中的緩存時間。因此，緩存命中率隨著用戶偏好傾向性的增強逐漸增加。其中，CCMCM的緩存命中率相比其他兩種機制依然有著明顯的優勢。

3.2.2緩存負載分布 本小節考察3種緩存決策機制下緩存負載的分布情況。為了突顯出采用不同緩存機制時在網絡節點累積緩存的內容數量上的差異，這里將內容數量增加到10000個，請求到達速率提高到100 個/s，在100 s的仿真時間內對節點的累積緩存內容數量進行統計。由圖2可以看出，采用LCE時各節點上的累積緩存內容數量明顯超過其他兩種機制，這正是該機制導致大量緩存冗余的表現。同時，緩存負載在節點上的分布存在著不均衡的現象。Betw機制下緩存負載分布的不均衡現象更為突出，這是由于Betw總是選擇路徑上介數最大的節點進行內容緩存，因此導致了大量內容集中緩存在高介數節點上。反觀CCMCM機制，通過適時地向周圍的鄰居節點進行緩存內容的轉移，使得緩存負載分布更均衡，提高了節點資源的利用率。

圖1 不同網絡參數對緩存命中率的影響

圖2 3種緩存機制下緩存負載在節點上的分布情況

4 結束語

緩存節點的合理選擇是CCN網內緩存技術研究的關鍵問題。為了實現網絡中節點資源的均衡有效利用，提升系統的緩存性能，本文提出了一種分布式的協同緩存機制——CCMCM。該機制在考慮緩存節點位置重要性的同時，通過適時地向鄰居節點實現合理的緩存內容遷移，來提高緩存負載在節點上分布的均衡性。仿真結果表明CCMCM有效地優化了網絡緩存的整體利用率，并對緩存命中率、平均接入代價等緩存性能指標具有明顯的改進。在后續的工作中，我們將驗證CCMCM在實際網絡環境下的性能并實現算法的優化。同時，還將進一步研究如何將本文的緩存機制擴展到移動網絡環境。

[1] Koponen T, Chawla M, Chun B G,.. A data-oriented (and beyond) network architecture[J]., 2007, 37(4): 181-192.

[2] Ahlgren B, Dannewitz C, Imbrenda C,. A survey of information-centric networking[J]., 2012, 50(7): 26-36.

[3] Jacobson V, Smetters D K, Thornton J D,.. Networking named content[J]., 2012, 55(1): 117-124.

[4] 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, 2004: 445-452.

[5] Cho K, Lee M, Park K,.. WAVE: popularity-based and collaborative in-network caching for contentoriented networks[C]. Proceedings of the IEEE INFOCOM Workshop onNOMEN, Orlando, FL, 2012: 316-321.

[6] Ming Z, Xu M, and Wang D. Age-based cooperative caching in information-centric network[C]. Proceedings of the 23rd International Conference on Computer Communication and Networks (ICCCN), Shanghai, 2014: 1-8.

[7] 葛國棟, 郭云飛, 劉彩霞, 等. 命名數據網絡中基于內容請求相關性的協作緩存算法[J]. 電子與信息學報, 2014, 36(12): 2795-2801.

Ge Guo-dong, Guo Yun-fei, Liu Cai-xia,.. Collaborative caching algorithm based on request correlation in named data networking[J].&, 2014, 36(12): 2795-2801.

[8] Wang L, Bayhan S, and Kangasharju J. Optimal chunking and partial caching in information-centric networks[J]., 2015, 61: 48-57.

[9] Qian H, Muqing W, Dongyang W,. Lifetime-based greedy caching approach for content-centric networking[C]. Proceedings of the 21st International Conference on Telecommunications (ICT), Lisbon,Portugal, 2014: 426-430.

[10] Chai W K, He D, Psaras I,.. Cache “less for more” in information-centric networks (extended version)[J]., 2013, 36(7): 758-770.

[11] Psaras I, Chai W K, and Pavlou G. Probabilistic in-network caching for information-centric networks[C]. Proceedings of the Second Edition of the ICN Workshop on Information- centric Networking, Helsinki, Finland, 2012: 55-60.

[12] 崔現東, 劉江, 黃韜, 等. 基于節點介數和替換率的內容中心網絡網內緩存策略[J]. 電子與信息學報, 2014, 36(1): 1-7.

Cui Xian-dong, Liu Jiang, Huang Tao,.. A novel in-network caching scheme based on betweenness and replacement rate in content centric networking[J].&, 2014, 36(1): 1-7.

[13] NS-3 based Named Data Networking (NDN) Simulator[OL]. http://ndnsim.net, 2013.6.

Cooperative Caching Mechanism with Content Migration in Content-centric Networking

Luo Xi①③An Ying②Wang Jian-xin①Liu Yao④

①(,,410083,)②(,,410013,)③(,,410138,)④(,,410205,)

Content-Centric Networking (CCN) is a new Internet architecture with native support for scalable and efficient content acquisition, which is proposed to accommodate the changes in future communication mode. Content caching is one of the key issues in CCN. In some existing work, the choice of caching nodes is over-focused on few special nodes, which results in an uneven distribution of cached contents. It greatly decreases the utilization of network resources and impairs the overall caching performance. In this paper, a Cooperative Caching Mechanism with Content Migration (CCMCM) is proposed. In this scheme, the centrality of node is considered in the selection of caching nodes to ensure that contents can be cached in the more important nodes as much as possible. When the cached contents are extensive, the caching node can transfer some contents to the appropriate neighbor according to the cache space available, the cache replacement rate and the connection stability between nodes. The aim is to fully utilize the resource of neighbor nodes and achieve effective load distribution. Simulation results show that the proposed scheme improves the load balance among caching nodes, increases the resource utilization and achieves high cache hit rate with low average access cost.

Content-Centric Networking (CCN); Cooperative caching; Load balance; Content migration

TP393

A

1009-5896(2015)11-2790-05

10.11999/JEIT150399

2015-04-08；改回日期：2015-07-08；

2015-08-27

安瑩 anying@csu.edu.cn

國家自然科學基金(61402541, 61103204)

The National Natural Science Foundation of China (61402541, 61103204)

羅 熹： 女，1980年生，博士生，研究方向為新型網絡體系結構設計、內容中心網絡.

安 瑩： 男，1980年生，講師，在站博士后，研究方向為新型網絡體系結構設計、內容中心網絡、延遲容忍網絡等.

王建新： 男，1969年生，教授，博士生導師，研究方向為網絡優化理論、參數計算理論、生物信息學等.

劉 耀： 男，1976年生，講師，博士，研究方向為延遲容忍網絡、社會網絡等.