命名數據網絡中基于內容請求相關性的協作緩存算法

葛國棟 郭云飛② 劉彩霞 蘭巨龍

?

命名數據網絡中基于內容請求相關性的協作緩存算法

葛國棟*①郭云飛①②劉彩霞①蘭巨龍①

①(國家數字交換系統工程技術研究中心 鄭州 450002)②(解放軍理工大學 南京 210007)

針對命名數據網絡(Named Data Networking, NDN)存儲空間的有效利用和應答內容的高效緩存問題，該文采用“差異化緩存”的方式，提出一種依據內容請求序列相關性的協作緩存算法。在內容請求中，預先發送對于后續相關數據單元的并行預測請求，增大內容請求的就近響應概率；緩存決策時，提出聯合空間存儲位置與緩存駐留時間的2維差異化緩存策略。根據內容活躍度的變化趨勢，空間維度上逐跳推進內容存儲位置，時間維度上動態調整內容緩存時間，以漸進式的方式將真正流行的請求內容推送至網絡邊緣存儲。該算法減小了內容請求時延和緩存冗余，提高了緩存命中率，仿真結果驗證了其有效性。

互聯網；命名數據網絡(NDN)；協作緩存；請求相關性；內容路由

1 引言

隨著互聯網技術與應用的飛速發展，“寬帶化”、“內容化”與“個性化”已經成為網絡發展的主旋律，人們對于數據內容的需求日益強烈，網絡應用的主體逐步向內容請求和信息服務演進轉移[1]。據Cisco VNI Mobile Forecast預測，到2014年互聯網上所有內容相關的流量將占據超過97.5%的份額，傳統以主機為中心的網絡體系結構難以滿足當前網絡信息服務的發展要求。為此，信息中心網絡(Information-Centric Networking, ICN)[1]作為一種革命式(clean-slate)的未來互聯網設計思路，讓數據內容本身成為網絡通信的主體單元，將網絡通信模式從關注“在哪”(地址、服務器)轉變為關注“是什么”，即用戶和應用通信的目的和意向，成為未來Internet設計的重要模式。其中，命名數據網絡(Named Data Networking, NDN)[2]作為典型的ICN網絡體系結構范例，在中間層用命名數據取代IP，數據傳輸采用“發布-請求-響應”模式，直接以內容名字(named data)進行路由，實現點到多點的高效內容分發。

在NDN的設計中，采用網絡內在普遍緩存(in-network caching)的方式，在興趣包(interest packet)沿途轉發路徑(on-path)的所有節點上緩存應答內容。在路由轉發中，當節點收到興趣包，依據內容名字依次在內容存儲器(Content Store, CS)，未決請求表(Pending Interest Table, PIT)和轉發信息庫(Forwarding Information Base, FIB)中進行匹配查詢。應答數據包(data packet)攜帶請求內容，依據節點PIT表項的記錄，沿相同路徑進行反向的逐跳傳輸。

文獻[3]指出，對于NDN網絡，合理的內容放置和緩存決策，是有效發揮網絡性能的關鍵因素。但由于NDN泛濫式的沿途全部緩存方式(Cache Everything Everywhere, CE2)，致使節點緩存內容趨于同質化，導致大量的緩存冗余。而且，在緩存決策時，缺乏對于內容本身差異化特征的考慮，無法實現內容的優化存儲。為此，為了有效發揮內容普遍緩存的優勢，高效緩存算法的設計就成為NDN需要解決的關鍵問題。

2 問題分析

文獻[4]提出了一種隨機單點緩存策略(RCOne)，在沿途路徑上隨機選擇單個節點進行內容存儲，減小緩存冗余。但該方案沒有考慮不同請求內容流行程度的差異性；文獻[5]提出只在緩存命中節點的直接下一跳存儲應答內容(LCD)，避免內容的重復緩存；文獻[6]提出了基于節點介數的緩存方案(betw)，通過在沿途傳輸路徑介數最大的節點上緩存內容，以提高后續利用率。但該方案將導致少數重要節點上的緩存頻繁替換；文獻[7]設計了基于概率的緩存方式(probabilistic cache)，依據節點距離數據源的距離和路徑的剩余存儲能力，計算節點對應的緩存概率；文獻[8]提出了緩存年齡的思想(age)，依據內容流行等級和存儲節點的位置來計算緩存年齡。但是該算法中假設內容流行度是已知的靜態參量，無法體現內容請求的動態變化特性，而且該參數難以預先獲取；文獻[9]提出了一種基于內容流行等級的協作緩存策略(WAVE)，依據內容的請求次數，以指數增長方式逐步增加沿途緩存的數據個數。但是該方案并沒有考慮內容請求序列的相關性，而且只實現了空間存儲位置上的差異化緩存；文獻[10]對現有緩存方案進行了對比分析，指出緩存算法的設計缺乏對于內容請求分布特征的考慮，并給出下一步的研究方向。

以上方案存在的不足之處主要體現在：(1)在差異化緩存設計時，對于不同內容的存儲位置和緩存駐留時間缺乏綜合考慮和有效結合；(2)緩存決策沒有結合內容請求序列的分布特征。緩存算法設計時，多數基于獨立請求模式(Independent Reference Model, IRM)進行研究[10]，內容請求概率由流行度分布函數預先給定，無法體現請求分布的動態變化和相關性特征[10, 11]。針對上述不足，在NDN中本文提出了一種基于內容請求相關性的協作緩存算法(Collaborative Caching Algorithm based on Request Correlation, CCARC)。CCARC根據內容請求序列間的相關性特征，主動發送對于關聯數據單元的并行預測請求；在緩存決策時，從差異化緩存思想出發，根據內容活躍度的變化趨勢，逐步推進內容存儲位置，以漸進式的方式將流行資源推送至網絡邊緣節點存儲。

3 基于內容請求相關性的協作緩存算法

CCARC屬于一種隱式的輕量級協作緩存算法，節點以分布式的方式獨立地執行緩存決策，不會引入額外的交互報文的發送與通告，也避免了中心化決策實體的引入。同時，內容的流行程度根據實際請求次數來動態確定，不依賴預先的參數假設。CCARC主要思想包括兩個方面：(1)基于內容請求相關性的并行預測請求；(2)緩存位置和駐留時間的2維差異化存儲。

3.1 報文交互與參數定義

為了區分基于相關性預測發起的請求和應答數據，分別設計了相關興趣包(Correlated Interest packet, CIP)和相關數據包(Correlated Data Packet, CDP)報文，其具體格式與NDN中的興趣包和數據包相同，只是CIP和CDP用于標識節點基于請求相關性而發出的交互報文，用于執行下一相關數據單元(chunk)的預測請求。在數據包和CDP報文中，添加緩存指示(Cache Indication, CI)和內容活躍度(Content Activity, CA)字段。其中，CI用于緩存節點指示下游節點執行應答內容的存儲，CA表示該內容對應的流行程度，用于存儲位置和緩存時間(Caching Time, CT)的計算，圖1給出了具體報文格式。

圖1 (相關)興趣和(相關)數據報文格式

圖2 內容活躍度CA

3.2 算法執行流程

3.2.1緩存存儲決策 節點依據接收到的報文格式和內容活躍度CA的變化趨勢，動態地確定內容存儲位置，計算、更新緩存時間。具體執行以下3種策略：

3.3 算法運行實例

圖3給出了CCARC算法具體執行實例。假設內容包括7個chunk(1~7)，存儲于內容源服務器(Original Content Server, OCS)。終端用戶1~4為內容請求者，A, B, C, D均為內容路由器(Content Router, C-Router)，實線方框表示正常的數據緩存單元，虛線方框代表臨時存儲的數據單元。

(1)1發送對前5項數據塊(1~5)的請求(圖3(a))：由于沿途路徑不存在對應的緩存資源，興趣包請求需要路由至OCS進行響應。當OCS接收到內容請求后，發送數據包進行應答，并將緩存指示標志CI位置為1，指示下游路由器緩存該應答內容；當C-Router A接收到數據包后，查看CI標志和CA字段，計算緩存存儲時間CT，將內容在其CS中進行存儲，并重置CI為0，繼續向下轉發應答數據包。當B, C和D接收到數據包后，由于CI標志位為0，直接進行報文轉發，無需進行數據緩存；

圖3 CCARC算法執行過程

(2)2發送對前3項數據內容(1~3)的請求(圖3(b1))：在首次請求中，由于1~5在路由器A處已經進行了緩存，節點A直接發送1~3對應的數據包進行應答，將CI置為1，指示下行路由器B緩存該應答內容。1~3將推送至節點B處進行存儲；假設在該次請求中(圖3(b2)),3對應的內容活躍度CA降低，那么對應的數據包中CI將設置為0，緩存位置將不會向下(節點B)推進，直接在節點A處依據當前CA重新計算緩存時間CT；

(3)3發送對前4項數據塊(1~4)的請求(圖3(c))：由于沿途緩存資源的存在，1~3對應的興趣包將在B處得到響應，并在C處依次進行緩存。當節點B進行3的應答時，同時發送CIP報文，執行對于數據塊4的相關性預測請求。當上游節點A接收到CIP后，發送CDP進行應答。當節點B接收到4的CDP應答報文后，提取內容并進行臨時存儲(虛線方框)。當C-Router B接收到用戶發送的4請求興趣包后，該內容將被節點正式緩存(實線方框)，并依據CA重新計算緩存時間CT。當5在節點B進行臨時緩存后，由于用戶沒有發起對于該內容的請求，該內容短時間內將會被替換淘汰。

CCARC算法的整體流程示于表1，劃分為內容請求和數據應答兩個過程。

4 仿真與性能分析

4.1 仿真環境與參數設置

表1 CCARC算法的整體流程

4.2 性能分析

將CCARC與文獻[2] NDN，文獻[4]RCOne和文獻[9] WAVE進行對比分析，評價指標包括：平均請求時延(Average Request Delay, ARD)，緩存命中率(Cache Hit Ratio, CHR)，平均路由跳數(Average Route Hop, ARH)。

由于NDN的CE2泛濫式緩存方式，節點的同質化緩存將會導致高頻率的內容替換更新，降低了沿途緩存資源的響應率，對應的ARD最大；RCOne在沿途路徑上以固定概率隨機選擇單個節點進行內容存儲，但該方案沒有考慮不同請求內容流行程度的差異性，固定的緩存概率無法實現內容的優化存儲；WAVE依據內容的請求次數，以指數增長方式不斷增加傳輸路徑緩存數據個數。但是該方案并沒有考慮內容請求分布的相關性特征。相比其他方案，CCARC對于不同請求內容，執行差異化緩存。依據內容活躍度的變化趨勢，計算內容存儲位置，動態調整內容緩存時間，增大了流行資源駐留概率和命中率。同時，依據內容請求序列的強相關性，主動發送對于關聯內容的預測請求，有效減小內容請求時延(約37%)。

圖4 平均請求時延ARD對比

圖5 緩存命中率CHR對比

4.3 適應性討論

5 結束語

內容的普遍緩存是NDN網絡的核心特征，而合理的內容放置和緩存策略是其性能有效發揮的保證。本文針對現有緩存算法的不足，結合內容請求分布的相關性特征，從差異化緩存的思想出發，在NDN中提出了一種依據內容請求序列相關性的協作緩存算法。在內容請求過程中，節點主動發送對于下一個相關數據單元的預測請求，增大后續內容請求的就近應答；在緩存決策時，逐跳推進內容存儲位置，動態調整緩存駐留時間，實現不同內容的差異化存儲。后續研究工作包括：(1)如何將CCARC緩存算法擴展到多數據源和多路徑模式下；(2)在不同網絡和仿真參數條件下對于CCARC性能進一步分析驗證。

圖6 平均路由跳數ARH對比

圖7 平均請求時延ARD隨Zipf指數的變化趨勢

圖8 平均請求時延ARD隨NoC的變化趨勢

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

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

[3] Chiocchetti R, Perino D, Carofiglio G,.. INFORM: a dynamic Interest Forwarding Mechanism for Information Centric Networking[C]. ACM SIGCOMM Workshop on Information-Centric Networking, Hong Kong, China, 2013: 9-14.

[4] Eum S, Nakauchi K, Murata M,.. CATT: potential based routing with content caching for ICN[C]. ACM SIGCOMM Workshop on Information-Centric Networking, Helsinki, Finland, 2012: 49-54.

[5] Laoutaris N, Syntila S, and Stavrakakis I. Meta algorithms for hierarchical web caches[C]. IEEE International Conference on Performance, Computing, and Commu- nications, Phoenix, USA, 2004: 445-452.

[6] Chai W K, He D, Psaras I,.. Cache “less for more” in information-centric networks[C]. Proceedings of IFIP 6 Networking Conference, Prague, Czech, 2012: 27-40.

[7] Psaras I, Chai W K, and Pavlou G. Probabilistic in-network caching for information-centric networks[C]. ACM SIGCOMM Workshop on Information-Centric Networking, Helsinki, Finland, 2012: 55-60.

[8] Ming Z X, Xu M W, and Wang D. Age-Based cooperative caching in information-centric networks[C]. IEEE INFOCOM, Orlando, USA, 2012: 268-273.

[9] Cho K, Lee M, Park K,.. WAVE: popularity-based and collaborative in-network caching for content-oriented Networks[C], IEEE INFOCOM Workshop on Emerging Design Choices in Name-Oriented Networking, Orlando, USA, 2012: 316-321.

[10] Zhang G Q, Li Y, and Lin T. Caching in information centric networking: a survey[J]., 2013, 57(16), 3128-3141.

[11] 朱軼，糜正琨，王文鼐. 一種基于內容流行度的內容中心網絡緩存概率置換策略[J]. 電子與信息學報, 2013, 35(6): 1305-1310.

Zhu Yi, Mi Zheng-kun, and Wang Wen-nai. A cache probability replacement policy based on content popularity in content centric networks[J].&, 2013, 35(6): 1305-1310.

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

[13] Chiocchetti R, Rossi D, Rossini G,.. Exploit the known or explore the unknown? Hamlet-like doubts in ICN[C]. ACM SIGCOMM Workshop on Information-Centric Networking, Helsinki, Finland, 2012: 7-12.

[14] Guo S, Xie H Y, and Shi G. Collaborative forwarding and caching in content centric networks[C]. Proceedings of IFIP Networking, Prague, Czech Republic, 2012: 41-55.

葛國棟： 男，1985年生，博士生，研究方向為新型網絡體系結構設計、內容中心網絡.

郭云飛： 男，1963年生，碩士，教授，博士生導師，研究方向為新型網絡體系結構設計、移動互聯網.

蘭巨龍： 男，1962年生，博士，教授、博士生導師，研究方向為可重構柔性網絡和高性能路由.

劉彩霞： 女，1974年生，博士，副教授，碩士生導師，研究方向為內容中心網絡、移動互聯網.

Collaborative Caching Algorithm Based on Request Correlation in Named Data Networking

Ge Guo-dong①Guo Yun-fei①②Liu Cai-xia①Lan Ju-long①

①(&&,450002,)②(’,210007,)

How to efficiently utilize the finite storage space and cache content chunks in the content store poses challenges to the caching policy in Named Data Networking (NDN). Using the differentiated caching strategy, a collaborative caching algorithm is proposed based on the request correlation. In the scheme, the subsequent correlated content chunks are requested in advance to increase the hit ratio for content requesting. When making the caching decision, a two-dimensional differentiated caching policy combining the caching location and cache-resident time is proposed. According to the change of content activity, the caching location is pushed downstream hop by hop in the spatial dimension in order to spread popular contents to the network edge in a gradual manner, and the cache-resident time is adjusted dynamically in the time dimension. The simulation results show that the proposed algorithm can efficiently decrease the request latency, reduce the cache redundancy, and achieve higher cache hit ratio than other caching strategies.

Internet; Named Date Networking (NDN); Collaborative caching; Request correlation; Content-based routing

TP393

A

1009-5896(2014)12-2795-07

10.3724/SP.J.1146.2014.00114

葛國棟 ggd@mail.ndsc.com.cn

2014-01-20收到，2014-04-24改回

國家973計劃基金(2012CB315901)，國家自然科學基金(61372121)，和國家863計劃項目(2011AA01A103)資助課題