命名數(shù)據(jù)網(wǎng)絡(luò)中基于內(nèi)容請求相關(guān)性的協(xié)作緩存算法

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

?

命名數(shù)據(jù)網(wǎng)絡(luò)中基于內(nèi)容請求相關(guān)性的協(xié)作緩存算法

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

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

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

互聯(lián)網(wǎng)；命名數(shù)據(jù)網(wǎng)絡(luò)(NDN)；協(xié)作緩存；請求相關(guān)性；內(nèi)容路由

1 引言

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

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

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

2 問題分析

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

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

3 基于內(nèi)容請求相關(guān)性的協(xié)作緩存算法

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

3.1 報文交互與參數(shù)定義

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

圖1 (相關(guān))興趣和(相關(guān))數(shù)據(jù)報文格式

圖2 內(nèi)容活躍度CA

3.2 算法執(zhí)行流程

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

3.3 算法運行實例

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

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

圖3 CCARC算法執(zhí)行過程

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

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

CCARC算法的整體流程示于表1，劃分為內(nèi)容請求和數(shù)據(jù)應(yīng)答兩個過程。

4 仿真與性能分析

4.1 仿真環(huán)境與參數(shù)設(shè)置

表1 CCARC算法的整體流程

4.2 性能分析

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

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

圖4 平均請求時延ARD對比

圖5 緩存命中率CHR對比

4.3 適應(yīng)性討論

5 結(jié)束語

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

圖6 平均路由跳數(shù)ARH對比

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

圖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 “l(fā)ess 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] 朱軼，糜正琨，王文鼐. 一種基于內(nèi)容流行度的內(nèi)容中心網(wǎng)絡(luò)緩存概率置換策略[J]. 電子與信息學(xué)報, 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年生，博士生，研究方向為新型網(wǎng)絡(luò)體系結(jié)構(gòu)設(shè)計、內(nèi)容中心網(wǎng)絡(luò).

郭云飛： 男，1963年生，碩士，教授，博士生導(dǎo)師，研究方向為新型網(wǎng)絡(luò)體系結(jié)構(gòu)設(shè)計、移動互聯(lián)網(wǎng).

蘭巨龍： 男，1962年生，博士，教授、博士生導(dǎo)師，研究方向為可重構(gòu)柔性網(wǎng)絡(luò)和高性能路由.

劉彩霞： 女，1974年生，博士，副教授，碩士生導(dǎo)師，研究方向為內(nèi)容中心網(wǎng)絡(luò)、移動互聯(lián)網(wǎng).

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)，國家自然科學(xué)基金(61372121)，和國家863計劃項目(2011AA01A103)資助課題