命名數(shù)據(jù)網(wǎng)絡(luò)中基于局部請求相似性的協(xié)作緩存路由機(jī)制

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

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 鄭州 450002)

命名數(shù)據(jù)網(wǎng)絡(luò)中基于局部請求相似性的協(xié)作緩存路由機(jī)制

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

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 鄭州 450002)

該文針對命名數(shù)據(jù)網(wǎng)絡(luò)(Named Data Networking, NDN)應(yīng)答內(nèi)容的高效緩存和利用問題，依據(jù)內(nèi)容請求分布的局域相似特征，提出一種協(xié)作緩存路由機(jī)制。緩存決策時，將垂直請求路徑上的冗余消除和水平局域范圍內(nèi)的內(nèi)容放置進(jìn)行有效結(jié)合。垂直方向上，提出基于最大內(nèi)容活躍因子的路徑緩存策略，確定沿途轉(zhuǎn)發(fā)對應(yīng)的最大熱點請求區(qū)域；水平方向上，采用一致性Hash協(xié)同緩存思想，實現(xiàn)應(yīng)答內(nèi)容的局域定向存儲。路由查找時，將局域節(jié)點緩存引入到路由轉(zhuǎn)發(fā)決策中，依據(jù)內(nèi)容活躍等級動態(tài)執(zhí)行局域緩存查找，增大內(nèi)容請求就近響應(yīng)概率。該機(jī)制減小了內(nèi)容請求時延和緩存冗余，提高了緩存命中率，以少量額外的代價換取了內(nèi)容請求開銷的大幅下降，仿真結(jié)果驗證了其有效性。

互聯(lián)網(wǎng)；命名數(shù)據(jù)網(wǎng)絡(luò)(NDN)；內(nèi)容路由；緩存策略；請求相似性

1 引言

隨著互聯(lián)網(wǎng)技術(shù)與應(yīng)用的飛速發(fā)展，“寬帶化”、“內(nèi)容化”與“個性化”已成為網(wǎng)絡(luò)發(fā)展的主旋律，人們對于數(shù)據(jù)內(nèi)容的需求日益強(qiáng)烈，網(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%的份額[2]，傳統(tǒng)以主機(jī)為中心的網(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)注“在哪”轉(zhuǎn)變?yōu)殛P(guān)注“是什么”，即用戶和應(yīng)用通信的目的和意向，成為未來Internet設(shè)計的重要模式。其中，命名數(shù)據(jù)網(wǎng)絡(luò)(Named Data Networking, NDN)[3]作為典型的ICN體系結(jié)構(gòu)范例，在中間層用命名數(shù)據(jù)取代IP，數(shù)據(jù)傳輸采用“發(fā)布-請求-響應(yīng)”模式，直接以內(nèi)容名字進(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)行反向的逐跳傳輸。但是，由于NDN泛濫式的沿途全部緩存方式(Cache Everything Everywhere, CE2)，應(yīng)答內(nèi)容在沿途轉(zhuǎn)發(fā)路徑上所有節(jié)點都將進(jìn)行存儲，致使節(jié)點緩存內(nèi)容趨于同質(zhì)化，導(dǎo)致大量的緩存冗余。在路由查找中，只針對持久穩(wěn)定的內(nèi)容源建立了路由條目，并沒有考慮局域節(jié)點的暫態(tài)緩存，致使傳輸路徑以外(off-path)大量的就近緩存資源無法加以利用。

文獻(xiàn)[4]對緩存資源利用的必要性和可行性進(jìn)行了分析，指出在控制平面的路由決策中，必須結(jié)合節(jié)點暫態(tài)緩存；文獻(xiàn)[5]對現(xiàn)有緩存方案進(jìn)行了對比分析，指出緩存算法的設(shè)計缺乏對于內(nèi)容請求分布特征的考慮；文獻(xiàn)[6]指出，現(xiàn)有典型的緩存策略，包括隨機(jī)緩存[7]，概率緩存[8]，最大介數(shù)緩存[9]等，在存儲決策時，只設(shè)計了垂直請求路徑上的內(nèi)容放置和冗余消除，缺乏對于局域水平范圍的考慮；文獻(xiàn)[10]提出了一種綜合使用節(jié)點介數(shù)和內(nèi)容更替率的緩存策略，避免重要節(jié)點處于高頻率的內(nèi)容替換狀態(tài)；文獻(xiàn)[7]提出了一種基于勢能的目標(biāo)識別路由方法(CATT)，將節(jié)點緩存內(nèi)容進(jìn)行局部范圍通告，實現(xiàn)緩存資源的可用性；文獻(xiàn)[11]提出了一種基于Hash協(xié)同的域內(nèi)緩存策略，邊緣路由節(jié)點通過Hash運算，確定內(nèi)容的存儲位置和轉(zhuǎn)發(fā)路徑；以上方案存在的不足主要包括：(1)緩存算法的設(shè)計缺乏對于內(nèi)容請求分布特征的考慮；(2)內(nèi)容放置時，只設(shè)計了垂直請求路徑上的冗余消除策略，缺乏與水平局域范圍內(nèi)緩存放置的有效結(jié)合；(3)路由查找缺乏對傳輸路徑以外緩存資源的考慮，無法有效利用局域節(jié)點的緩存內(nèi)容。

為此，結(jié)合內(nèi)容請求的局域分布特征，在NDN中提出了一種協(xié)作緩存路由機(jī)制(Collaborative Caching and Routing Scheme, CCRS)。通過構(gòu)建局域的內(nèi)容請求相似性社區(qū)，在垂直和水平2維空間下，聯(lián)合進(jìn)行冗余消除和緩存策略設(shè)計。路由轉(zhuǎn)發(fā)時，將節(jié)點緩存因素引入到路由決策中，動態(tài)執(zhí)行局域緩存查找，增大緩存命中率和就近響應(yīng)概率。

2 協(xié)作緩存路由機(jī)制(CCRS)

CCRS從內(nèi)容請求的局域相似性特征出發(fā)，首先構(gòu)建了基于內(nèi)容活躍因子的請求相似性社區(qū)(Content Similarity Community, CSC)。進(jìn)而，依據(jù)CSC對內(nèi)容對象的整體需求程度，將應(yīng)答內(nèi)容存儲在沿途轉(zhuǎn)發(fā)路徑活躍度最高的熱點請求CSC內(nèi)，增大緩存內(nèi)容駐留概率；在CSC內(nèi)，采用一致性Hash協(xié)同緩存策略，定向緩存應(yīng)答內(nèi)容，減小相同內(nèi)容的重復(fù)冗余存儲。在內(nèi)容請求時，CCRS不僅可以利用沿途轉(zhuǎn)發(fā)路徑節(jié)點上的緩存內(nèi)容，通過執(zhí)行局域緩存查找，對于所屬CSC內(nèi)的局域緩存資源也可加以利用。

2.1 內(nèi)容請求相似性社區(qū)構(gòu)建

2.1.1 內(nèi)容活躍因子定義 內(nèi)容請求在時間維度上具有動態(tài)可變特征[12]，即內(nèi)容的流行程度在不同的時間段內(nèi)會表現(xiàn)出不同程度的差異性。為了體現(xiàn)內(nèi)容請求的動態(tài)變化特征，減小“冷門”資源的偶然訪問對于請求分布造成的影響，兼顧內(nèi)容對象歷史請求的“熱度”和當(dāng)前時刻的“新穎度”，提出了內(nèi)容活躍因子ρC(t,v)。

定義1 內(nèi)容活躍因子ρC(t,v)。ρC(t,v)是內(nèi)容活躍程度的度量指標(biāo)，用于表征在特定時刻t，緩存節(jié)點v上，內(nèi)容對象C被請求的活躍程度。

以時間間隔T對節(jié)點v上內(nèi)容對象C的訪問次數(shù)進(jìn)行統(tǒng)計，請求速率的統(tǒng)計時間窗口寬度為WKT, k為滑動窗口的寬度，T為統(tǒng)計間隔時間，[nT, t], [(n-1)T, nT],…,[(n-k)T, (n-k+1)T]表示時間間隔序列，Sn, Sn-1,…,Sn-k為T中C的請求次數(shù)，λn,λn-1,…,λn-k為對應(yīng)的請求頻率。對于節(jié)點v，內(nèi)容對象C在時刻t，對應(yīng)的內(nèi)容活躍因子ρC(t,v)為

其中，αi,i=n-1, … ,n-k , 0＜αi＜1，為歷史請求頻率的權(quán)值，表征了前k個時間序列對于當(dāng)前時刻內(nèi)容活躍程度的影響，反映了ρC(t,v)與歷史請求“熱度”的關(guān)聯(lián)關(guān)系。αn表征了ρC(t,v)受當(dāng)前時刻請求頻度的影響程度，反映了內(nèi)容對象訪問的“新穎度”，圖1給出了ρC(t,v)的具體圖示。

2.1.2 內(nèi)容相似性度量 內(nèi)容請求分布在空間上具有很大程度的局域相似性[13]，處于局部區(qū)域的用戶更傾向于關(guān)注和請求相同的內(nèi)容和信息。為此，提出NDN網(wǎng)絡(luò)內(nèi)容請求相似性社區(qū)CSC，用于描述具有相似性內(nèi)容請求的節(jié)點集合。

圖1 內(nèi)容活躍因子ρC(t,v)

定義2 內(nèi)容請求相似性系數(shù)(Similarity Coefficient, SC): SC用于表示節(jié)點間內(nèi)容請求的相似性程度。

以時間間隔T對節(jié)點v上內(nèi)容請求進(jìn)行統(tǒng)計分析，Ct(v)={c1,c2,…,cm}為內(nèi)容請求條目列表，ρt(v)={ρC1(t,v),ρC2(t,v),…,ρCm(t,v )}為對應(yīng)的內(nèi)容活躍因子集合。時刻t，節(jié)點i與j之間的SC為

其中，? i, j, 0≤SC≤1, SC(i,j)=SC(j,i )。Ct(i)∩Ct(j)表示節(jié)點i, j之間內(nèi)容請求的相同部分，Ct(i)∪Ct(j)表示內(nèi)容請求對象的總和，ρC(t,i), ρC(t,j)分別為對應(yīng)的內(nèi)容活躍因子。節(jié)點間請求的內(nèi)容條目越相似，對應(yīng)的內(nèi)容活躍因子越高，相應(yīng)的SC取值越大。

定義3 相似性聚合度θ：用于表征CSC內(nèi)節(jié)點間SC的聚合程度。即：對于CSC內(nèi)任意相鄰節(jié)點i, j，滿足SC(i,j)≥θ。θ取值越大，對應(yīng)CSC的內(nèi)容請求相似性程度越高。

定義4 社區(qū)內(nèi)容活躍度(Community Content Activity, CCA)：用于表示在整個CSC內(nèi)，特定內(nèi)容被請求的頻度。社區(qū)內(nèi)容活躍度CCA為

CCA(c)是特定內(nèi)容c在CSC中所有請求節(jié)點上的局部活躍因子之和，衡量了整個社區(qū)對于該內(nèi)容的整體需求程度，體現(xiàn)了請求內(nèi)容在CSC內(nèi)的全局活躍程度。

2.1.3 局域相似性社區(qū)計算 為了計算和確定CSC結(jié)構(gòu)和對應(yīng)的節(jié)點集合，在NDN中，設(shè)計了CSC相似性通告報文(Similarity Advertisement Packet, SAP)，具體報文格式如圖2所示。其中，Type字段表示報文類型，Nonce字段為隨機(jī)數(shù)，Time Stamp用來記錄報文發(fā)送時間。Node Identifier為緩存節(jié)點標(biāo)識，Ct(v)=(c1,c2,…,cm), ρt(v)={ρC1(t,v),ρC2(t, v),…,(t,v )}分別為內(nèi)容請求條目列表和內(nèi)容活躍因子集合。

圖2 CSC內(nèi)容請求相似性通告報文(SAP)

以θ作為CSC的相似性聚合指標(biāo)，構(gòu)造內(nèi)容請求相似性社區(qū)。節(jié)點向其鄰居節(jié)點發(fā)送SAP報文，依據(jù)SAP消息攜帶的Ct(v)和ρt(v)的大小，計算對應(yīng)SC取值。當(dāng)SC(i,j)≥θ，在節(jié)點間添加相似性屬性連接關(guān)系sij=1，否則sij=0。如果SC(i,j)≥θ，節(jié)點將接收到的SAP報文繼續(xù)下行轉(zhuǎn)發(fā)。否則，直接丟棄，終止報文發(fā)送。最終，節(jié)點將接收到所有具有連續(xù)相似性屬性關(guān)系節(jié)點的SAP報文，確定所屬CSC對應(yīng)的節(jié)點集合Vθ。CSC構(gòu)建算法的具體步驟如下，其中，CGT為局部緩存指引表項，用于確定目標(biāo)緩存節(jié)點的下一跳轉(zhuǎn)發(fā)接口。

(1)計算內(nèi)容請求條目列表Ct(v)={c1,c2,…,cm}和活躍因子集合ρt(v)={ρC1(t,v),ρC2(t,v),…,ρCm(t,v )}；

(2)在SAP報文中添加節(jié)點對應(yīng)的Ct(v)和ρt(v )信息，向其鄰居節(jié)點發(fā)送SAP相似性通告，進(jìn)行內(nèi)容請求信息的局部交互；

(3)當(dāng)鄰居節(jié)點接收到SAP報文后，提取Ct(v)和ρt(v)屬性內(nèi)容，計算節(jié)點間對應(yīng)的SC取值，并記錄節(jié)點標(biāo)識和對應(yīng)的到達(dá)接口，用于建立局部CGT；

(4)依據(jù)θ與SC取值大小關(guān)系，確定相似性屬性連接關(guān)系。當(dāng)SC(i,j)≥θ時，sij=1，否則，sij=0；

(5)若SC≥θ，上游節(jié)點將其接收的SAP報文繼續(xù)向下游節(jié)點轉(zhuǎn)發(fā)通告；

(6)若SC＜θ，上游節(jié)點直接丟棄接收到的SAP報文，終止SAP轉(zhuǎn)發(fā)通告；

(7)節(jié)點依據(jù)接收到的SAP報文，確定所屬CSC的節(jié)點集合Vθ，計算CSC對應(yīng)的CGT；

(8)依據(jù)各節(jié)點局部的Ct(v)和ρt(v)屬性內(nèi)容，確定CSC對應(yīng)的內(nèi)容請求條目列表C(CSC)，計算對應(yīng)的全局內(nèi)容活躍度集合CCA(CSC)。

2.2 基于CSC的緩存策略

垂直方向上，依據(jù)CSC對內(nèi)容的整體需求程度，將請求內(nèi)容存儲在沿途轉(zhuǎn)發(fā)路徑活躍度(CCA)最高的熱點請求CSC內(nèi)，使內(nèi)容請求盡可能在本地CSC內(nèi)得到就近應(yīng)答；水平方向上，在CSC內(nèi)，采用一致性Hash協(xié)同的緩存思想，定向緩存應(yīng)答內(nèi)容，增大CSC局域緩存資源的多樣性。

2.2.1 路徑緩存策略 路徑緩存策略需要確定應(yīng)答內(nèi)容存儲的目標(biāo)CSC社區(qū)，減小垂直方向上內(nèi)容的重復(fù)冗余存儲。在興趣包和數(shù)據(jù)包中添加CCA字段，用于記錄和匹配興趣包沿途CSC對應(yīng)的活度信息。

(1)內(nèi)容請求過程：內(nèi)容請求者vc發(fā)送內(nèi)容請求，節(jié)點接收到興趣包后，如果CS已經(jīng)緩存了該內(nèi)容，則直接進(jìn)行響應(yīng)。若CS和PIT中沒有對應(yīng)的請求內(nèi)容和接口信息，則判斷是否要執(zhí)行CSC局域緩存查找(依據(jù)2.3.1節(jié))。若條件成立，在CSC內(nèi)執(zhí)行局域緩存查找。否則，在興趣包中添加CSC對應(yīng)的內(nèi)容活躍度CCA(c)，依據(jù)FIB表項信息進(jìn)行下一跳路由轉(zhuǎn)發(fā)。通過興趣包逐跳的上行傳輸，依次記錄和添加沿途CSC對應(yīng)的CCA(c)。每當(dāng)興趣包轉(zhuǎn)發(fā)到下一個CSC時，所屬節(jié)點將相鄰CSC對應(yīng)的CCA(c)取值大小進(jìn)行比較，將CCA(c)更新為已有社區(qū)中的最大值。最終，當(dāng)興趣包到達(dá)內(nèi)容提供者vp后，CCA(c)記錄的就是內(nèi)容c沿途最大熱點請求區(qū)域?qū)?yīng)的內(nèi)容活躍度maxCCA(c)。

(2)數(shù)據(jù)應(yīng)答過程：當(dāng)vp發(fā)送數(shù)據(jù)包進(jìn)行反向應(yīng)答時，將上行興趣包中攜帶的maxCCA(c)添加到數(shù)據(jù)包的CCA(c)選項中，并依次比對反向傳輸路徑節(jié)點對應(yīng)的活躍度信息，匹配目標(biāo)CSC。進(jìn)而，在該CSC內(nèi)執(zhí)行局域緩存操作，將內(nèi)容c存儲在對應(yīng)的CSC目標(biāo)節(jié)點上，實現(xiàn)請求內(nèi)容的熱點區(qū)域緩存。

2.2.2 Hash協(xié)同緩存策略 當(dāng)數(shù)據(jù)包到達(dá)目標(biāo)CSC后，同時執(zhí)行以下兩種操作：(1)正常的數(shù)據(jù)轉(zhuǎn)發(fā)。節(jié)點依據(jù)PIT表項，向請求者發(fā)送應(yīng)答內(nèi)容；(2)局域定向緩存。節(jié)點執(zhí)行一致性Hash運算，計算該內(nèi)容的目標(biāo)緩存節(jié)點nc：

其中，輸入為內(nèi)容對象名字，目標(biāo)空間為所屬CSC的節(jié)點集合Vθ，輸出為nc。在數(shù)據(jù)包中添加nc的節(jié)點標(biāo)識，構(gòu)造緩存數(shù)據(jù)報文(Caching Data Packet, CDP)，其格式與數(shù)據(jù)包消息類似，只是將CCA字段替換為目標(biāo)緩存節(jié)點標(biāo)識。然后，節(jié)點依據(jù)緩存指引表項CGT，確定下一跳轉(zhuǎn)發(fā)接口，將CDP報文發(fā)送到nc。nc接收到CDP報文后，提取數(shù)據(jù)內(nèi)容并在CS中進(jìn)行存儲。在CSC中，對于同一請求內(nèi)容，只存儲在目標(biāo)緩存節(jié)點上，避免相同內(nèi)容的重復(fù)冗余存儲，增大CSC緩存內(nèi)容的多樣性。

2.3 緩存查找和路由轉(zhuǎn)發(fā)

2.3.1 局域緩存查找 當(dāng)CS和PIT表項中沒有對應(yīng)的請求內(nèi)容和接口信息時，節(jié)點需要確定是否執(zhí)行CSC內(nèi)的局域緩存查找。如果對于沿途傳輸?shù)乃蠧SC都執(zhí)行局域的緩存資源查找操作，將會引入多個額外的查找時延。對于CSC來說，CCA描述了CSC對于請求內(nèi)容的整體需求程度。對于特定的請求內(nèi)容，如果該內(nèi)容不處于對應(yīng)的內(nèi)容請求條目列表中，說明CSC對于該內(nèi)容請求的頻度很小，需求程度很低。那么，依據(jù)路徑緩存策略，此內(nèi)容在該CSC內(nèi)存儲的概率將很小，如果執(zhí)行緩存查找，將存在很大程度的內(nèi)容缺失。為此，定義局域緩存查找區(qū)間CQ(CSC)，節(jié)點只對CSC對應(yīng)的流行資源進(jìn)行局域緩存查找，減小額外引入的查找時延。為前m項流行內(nèi)容，m取值由式(5)確定：

其中，δ(0≤δ≤1)為累積活躍閾值，表示前m項內(nèi)容請求的累加概率。例如，當(dāng)δ=0.8時，即表示對于前m項內(nèi)容的請求概率占據(jù)了全部內(nèi)容請求的80%。當(dāng)內(nèi)容對象總數(shù)為2000, Zipf指數(shù)α取值1.0和1.2時，累加請求概率為0.8包含的內(nèi)容對象，即m取值分別為390項和99項。

2.3.2 動態(tài)路由轉(zhuǎn)發(fā) 當(dāng)節(jié)點接收到興趣包后，首先查找CS中是否已存儲了該請求內(nèi)容c，若匹配成功，直接發(fā)送數(shù)據(jù)包進(jìn)行響應(yīng)。否則，查找PIT表項，若已包含該內(nèi)容的請求條目，直接添加到達(dá)接口信息；否則，在PIT中增加該內(nèi)容對應(yīng)的請求條目，然后查看請求內(nèi)容是否位于局域緩存查找區(qū)間CQ(CSC): (1)如果c∈CQ(CSC)，執(zhí)行一致性Hash運算，確定目標(biāo)緩存節(jié)點nc，依據(jù)CSC的緩存指引表項，進(jìn)行局域緩存資源查找。若nc含有該請求內(nèi)容，則直接命中，進(jìn)行局部應(yīng)答。否則，依據(jù)FIB表項，進(jìn)行內(nèi)容請求的前向轉(zhuǎn)發(fā)；(2)如果c?CQ(CSC)，無需執(zhí)行局域緩存查找，直接依據(jù)FIB表項，進(jìn)行內(nèi)容請求的下一跳轉(zhuǎn)發(fā)。表1給出了CCRS的整體流程，包括內(nèi)容請求和數(shù)據(jù)應(yīng)答兩個部分。

表1 基于局域請求相似性的協(xié)作緩存路由機(jī)制

3 仿真與性能分析

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

采用ndnSIM[14]進(jìn)行仿真與性能分析，該工具對于NDN的基本數(shù)據(jù)單元結(jié)構(gòu)和路由轉(zhuǎn)發(fā)流程均已實現(xiàn)，并提供了開放源碼和運行實例。在GT-ITM下采用Locality模型生成50個路由節(jié)點的平面隨機(jī)網(wǎng)絡(luò)拓?fù)?。網(wǎng)絡(luò)中內(nèi)容對象總數(shù)N為10000個，大小設(shè)為10 kByte。節(jié)點緩存容量一致，CS設(shè)為100，鏈路帶寬100 Mbps。在網(wǎng)絡(luò)中設(shè)置2個內(nèi)容服務(wù)器，負(fù)責(zé)內(nèi)容對象的存儲和發(fā)布，各服務(wù)器隨機(jī)存儲5000個內(nèi)容，并在網(wǎng)絡(luò)邊緣節(jié)點中隨機(jī)選取2個節(jié)點與內(nèi)容服務(wù)器直接相連。其余節(jié)點均作為用戶接入節(jié)點，發(fā)布內(nèi)容請求，內(nèi)容請求到達(dá)服從λ=50個/s的泊松過程[9]，請求概率服從Zipf分布[8]，第i個內(nèi)容的請求概率為：。依據(jù)文獻(xiàn)[15]的構(gòu)造方法模擬內(nèi)容請求分布的局域相似特征，首先依據(jù)節(jié)點度的大小，構(gòu)造不同中心節(jié)點內(nèi)容請求的差異化分布，其余節(jié)點的請求分布依據(jù)路由跳數(shù)與就近的中心節(jié)點保持一致，并依據(jù)與中心節(jié)點的距離進(jìn)行局部的差異化調(diào)整。仿真時間設(shè)為200 s，統(tǒng)計間隔δ=0.8，初始節(jié)點緩存狀態(tài)為空，緩存替換策略采用最近最少使用策略LRU。

3.2 性能分析

將CCRS與NDN[3], Betw[9]和Hash-Mu[11]進(jìn)行對比分析，性能評價指標(biāo)包括：平均請求時延(Average Request Delay, ARD)，緩存命中率(Cache Hit Ratio, CHR)，局部響應(yīng)率(Local Response Ratio, LRR)和額外開銷對比。

3.2.1 平均請求時延 平均請求時延ARD：節(jié)點發(fā)送請求興趣包到接收到應(yīng)答數(shù)據(jù)包之間的平均延遲。圖3給出了α=1.2, θ=0.7時，4種方案的ARD對比，采樣間隔T=2 s。仿真初始階段，由于網(wǎng)絡(luò)中所有節(jié)點存儲狀態(tài)為空，發(fā)送的興趣包請求都需要轉(zhuǎn)發(fā)至內(nèi)容源服務(wù)器進(jìn)行響應(yīng)，ARD較大。但隨著請求內(nèi)容的不斷存儲，緩存內(nèi)容的響應(yīng)概率逐漸增加，ARD隨之減小。

NDN采用泛濫式的CE2存儲方式，將會引起高頻率的緩存替換更新，導(dǎo)致內(nèi)容缺失概率增大，對應(yīng)的ARD最大；Betw通過在介數(shù)最大的重要節(jié)點上緩存內(nèi)容，提高內(nèi)容副本的后續(xù)利用率，但該方案僅僅考慮了垂直請求路徑上的緩存放置，且對于傳輸路徑以外的局部緩存資源無法進(jìn)行感知利用；Hash-Mu雖然消除了域內(nèi)相同內(nèi)容的冗余緩存，但是基于Hash計算目標(biāo)緩存節(jié)點，無法實現(xiàn)應(yīng)答內(nèi)容的優(yōu)化存儲；CCRS在應(yīng)答內(nèi)容存儲時，綜合考慮垂直和水平方向上的冗余消除，將CSC整體需求程度最大的活躍內(nèi)容定向存儲在對應(yīng)的目標(biāo)緩存節(jié)點上。內(nèi)容請求時，實現(xiàn)了沿途所屬CSC內(nèi)就近緩存資源的有效利用，減小了內(nèi)容請求時延，ARD是各方案中最小的。

3.2.2 緩存命中率 緩存命中率CHR：網(wǎng)絡(luò)中節(jié)點緩存內(nèi)容響應(yīng)興趣包請求的概率。圖4給出了α=1.2, θ=0.7和α=1.5, θ=0.8時，各方案的CHR對比。隨著α取值增加，內(nèi)容請求的集中性和局域性不斷加強(qiáng)，流行緩存資源的駐留概率和命中率不斷增大，各方案對應(yīng)的CHR都得到了相應(yīng)的提高。對于NDN和Betw，在應(yīng)答內(nèi)容存儲時，沒有考慮不同請求內(nèi)容流行等級的差異性，而且對于沿途附近存在的內(nèi)容副本無法加以利用，CHR明顯小于CCRS方案。對于Hash-Mu，域內(nèi)所有節(jié)點整體協(xié)作，實現(xiàn)應(yīng)答內(nèi)容的協(xié)同緩存，雖然無法實現(xiàn)內(nèi)容的優(yōu)化存儲，但提升了域內(nèi)緩存內(nèi)容的命中率；在CCRS中，將節(jié)點有限的存儲空間用于緩存CSC整體需求程度最高的活躍請求內(nèi)容，增大了緩存內(nèi)容的駐留概率和利用率。同時，通過局域緩存查找，充分利用了沿途所屬CSC內(nèi)的局部緩存資源，CHR分別達(dá)到了0.481和0.622。

3.2.3 局部響應(yīng)率 局部響應(yīng)率LRR：內(nèi)容請求在首跳發(fā)送節(jié)點和第1跳轉(zhuǎn)發(fā)節(jié)點上響應(yīng)的概率。LRR反映了內(nèi)容請求在局部范圍內(nèi)的就近響應(yīng)率。圖5給出了在α=1.2, θ=0.7時，各方案的LRR對比。CCRS將應(yīng)答內(nèi)容存儲在沿途請求活躍程度最大的熱點CSC中，增加了緩存內(nèi)容在本地的駐留概率和命中率，首跳節(jié)點緩存命中率達(dá)到了0.210。當(dāng)首跳節(jié)點緩存缺失時，通過執(zhí)行所屬CSC緩存資源的局域查找，一跳轉(zhuǎn)發(fā)節(jié)點的緩存命中率為0.161，明顯大于其他方案，LRR達(dá)到了0.371，是4種方案中最大的。對于Hash-Mu，雖然其增大了域內(nèi)緩存內(nèi)容命中率CHR，但是由于其隨機(jī)化的選擇內(nèi)容存儲位置，對于LRR提升并不明顯，只達(dá)到0.102和0.096。

3.2.4 代價開銷對比 相比NDN, Betw和Hash-Mu, CCRS為了實現(xiàn)應(yīng)答內(nèi)容的合理放置和有效利用，引入了額外的開銷來換取內(nèi)容請求性能的提升。其中，額外開銷主要包括：相似性通告和節(jié)點存儲開銷，下面進(jìn)行定量分析。

(1)相似性通告開銷(CA)：在CSC建立時，相似性通告報文(SAP)交互引入的開銷，定義為SAP與其傳輸距離(路由跳數(shù))的乘積，大小取決于報文長度、通告頻率和路由傳輸跳數(shù)，代價單位取bit·hop。單位時間內(nèi)相似性通告開銷CA為

圖3 平均請求時延ARD對比

圖4 緩存命中率CHR對比圖

圖5 局部響應(yīng)率LRR對比

其中，fSAP為SAP通告頻率，SSAP為報文長度，d1為首跳鄰居通告跳數(shù)。當(dāng)鄰居節(jié)點接收到SAP后，計算SC取值，如果SC≥θ，節(jié)點將SAP繼續(xù)進(jìn)行轉(zhuǎn)發(fā)通告，d2為第2跳路由傳輸跳數(shù)。否則，直接丟棄，終止報文發(fā)送。

(2)節(jié)點存儲開銷(CC)：在CCRS中，節(jié)點需要記錄內(nèi)容請求條目列表Ct(v)和對應(yīng)的內(nèi)容活躍因子集合ρt(v)。當(dāng)節(jié)點交互SAP報文后，需要存儲局域緩存指引表項CGT和對應(yīng)的緩存查找區(qū)間CQ(CSC)。額外CC大小取決于所存儲的內(nèi)容名字、接口和活躍因子的數(shù)量和長度，代價單位為bit。

其中，Lc, Lρ, Lf和Li分別為內(nèi)容名字、活躍因子、接口和節(jié)點標(biāo)識的長度，l, m, n為對應(yīng)的存儲數(shù)量。

(3)內(nèi)容請求開銷(CR)：定義為內(nèi)容請求過程中，興趣包(interest packet)和數(shù)據(jù)包(data packet)分別與其傳輸距離的乘積之和，大小主要取決于內(nèi)容請求過程傳輸?shù)穆酚商鴶?shù)，代價單位取bit·hop。

其中，SInt, SDat分別表示內(nèi)容請求和數(shù)據(jù)應(yīng)答報文長度，d為對應(yīng)的路由傳輸跳數(shù)。

表2給出了α=1.2，各方案的代價開銷對比。其中，CCRS的SAP通告間隔設(shè)為2 s。在NDN和Betw中，沒有相應(yīng)的局域緩存內(nèi)容發(fā)現(xiàn)機(jī)制，不會產(chǎn)生額外的報文通告開銷CA和存儲開銷CC。但是，在內(nèi)容請求時，由于無法利用局域就近的緩存資源，對應(yīng)的CR最大。Hash-Mu提升了域內(nèi)節(jié)點緩存內(nèi)容的命中率，但是，基于Hash隨機(jī)計算存儲位置的方式，無法實現(xiàn)應(yīng)答內(nèi)容的優(yōu)化存儲；在CCRS中，將局域緩存因素引入到路由決策中，動態(tài)執(zhí)行局域緩存查找和應(yīng)答內(nèi)容定向存儲，相比其他方案，雖然引入了額外的CA和CC，但有效地減小了內(nèi)容請求開銷CR。CCRS通過小量額外CA, CC的付出，增大了內(nèi)容請求的局部響應(yīng)率LRR，換取了CR的大幅下降。表3給出在α=1.5，各方案代價開銷對比。

表2 代價開銷對比(α=1.2)

表3 代價開銷對比(α=1.5)

3.3 適應(yīng)性討論

圖6分別給出了在相似性聚合度θ取值為0.6, 0.7和0.8下，ARD隨Zipf指數(shù)α的變化趨勢。當(dāng)α取值較小時，內(nèi)容請求不能有效集中，在α取值為0.2和0.4時，最大流行內(nèi)容對應(yīng)的請求概率僅為0.0005和0.0024，節(jié)點間內(nèi)容請求相似性較低，無法形成局域的CSC社區(qū)。隨著α取值增大，內(nèi)容請求的集中性和局域性不斷加強(qiáng)，在聚合度θ=0.6時，首先形成CSC社區(qū)，內(nèi)容請求局域響應(yīng)概率增大，ARD顯著下降。但是，隨著α進(jìn)一步增大，少數(shù)流行資源包含的內(nèi)容對象已無顯著變化，加之CSC的局域性，ARD下降趨勢逐漸減緩。在不同的θ取值下，CCRS可以有效降低ARD, θ取值越大，CSC內(nèi)容請求相似性程度越高，對應(yīng)的ARD越小。

圖7給出了在α=1.2, θ=0.7時，ARD隨節(jié)點緩存容量變化的趨勢。隨著節(jié)點緩存容量的不斷增加，更多的請求內(nèi)容可以被存儲在中間節(jié)點上，提高了緩存命中率CHR，各方案對應(yīng)的ARD不斷減小。當(dāng)節(jié)點緩存空間較小時，CCRS依據(jù)CSC內(nèi)容請求的流行等級，將節(jié)點有限的存儲空間用于緩存CSC整體需求程度最高的活躍請求內(nèi)容，減小相同內(nèi)容副本的重復(fù)存儲。CCRS可以有效利用節(jié)點有限的緩存空間，對于緩存容量的變化具有良好的適應(yīng)性。

4 結(jié)束語

內(nèi)容的普遍緩存是NDN的核心特征，而合理的內(nèi)容放置和緩存查找是其性能有效發(fā)揮的保證。本文依據(jù)內(nèi)容請求的局域分布特征，在NDN中提出了一種協(xié)作緩存路由機(jī)制。CCRS綜合考慮了垂直請求路徑和水平局域范圍2維空間下的內(nèi)容放置和冗余消除，基于最大內(nèi)容活躍因子確定沿途轉(zhuǎn)發(fā)路徑對應(yīng)的最大熱點請求區(qū)域，采用一致性Hash協(xié)同緩存思想，實現(xiàn)應(yīng)答內(nèi)容CSC內(nèi)的局域定向緩存，仿真結(jié)果和對比分析顯示其有效性。后續(xù)研究工作包括：(1)如何將CCRS擴(kuò)展到移動ICN環(huán)境中，設(shè)計相應(yīng)的內(nèi)容存儲和查找機(jī)制；(2)在不同網(wǎng)絡(luò)和仿真參數(shù)條件下，對于CCRS性能和開銷進(jìn)行進(jìn)一步分析驗證。

圖6 ARD隨Zipf指數(shù)α的變化趨勢

圖7 ARD隨緩存容量的變化趨勢

[1] Xylomenos G, Ververidis C, Siris V, et al.. A survey of information-centric networking research[J]. IEEE Communications Surveys & Tutorials, 2014, 16(2): 1024-1049.

[2] Cisco. Cisco Visual Networking Index (VNI): forecast and methodology, 2011-2016[OL]. http://www.cisco.com, 2012.

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

[4] Wang Y G, Lee K, Venkataraman B, et al.. Advertising cached contents in the control plane: necessity and feasibility[C]. IEEE Conference on Computer Communications Workshops, Orlando, USA, 2012: 286-291.

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

[6] Wang J M, Zhang J, and Bensaou B. Intra-AS cooperative caching for content-centric networks[C]. ACM SIGCOMM Workshop on Information-Centric Networking, Hong Kong, China, 2013: 61-66.

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

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

[9] Chai W K, He D, Psaras I, et al.. Cache “l(fā)ess for more” ininformation-centric networks[C]. Proceedings of IFIP Networking, Prague, Czech, 2012: 27-40.

[10] 崔現(xiàn)東, 劉江, 黃韜, 等. 基于節(jié)點介數(shù)和替換率的內(nèi)容中心網(wǎng)絡(luò)網(wǎng)內(nèi)緩存策略[J]. 電子與信息學(xué)報, 2014, 36(1): 1-7. Cui Xian-dong, Liu Jiang, Huang Tao, et al.. A novel in-network caching scheme based on betweenness and replacement rate in content centric networking[J]. Journal of Electronics & Information Technology, 2014, 36(1): 1-7.

[11] Saino L, Psaras I, and Pavlou G. Hash-routing schemes for information centric networking[C]. ACM SIGCOMM Workshop on Information-Centric Networking, Hong Kong, China, 2013: 27-32.

[12] Wang J M and Bensaou B. Progressive Caching in CCN[C]. IEEE GLOBECOM, Anaheim, USA, 2012: 2727-2732.

[13] 劉外喜, 余順爭, 蔡君, 等. ICN 中的一種協(xié)作緩存機(jī)制[J].軟件學(xué)報, 2013, 24(8): 1947-1962. Liu Wai-xi, Yu Shun-zheng, Cai Jun, et al.. Scheme for cooperative caching in ICN[J]. Journal of Software, 2013, 24(8): 1947-1962.

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

[15] Zhang Y, Zhao J, Cao G H, et al.. On interest locality in content-based routing for large-scale MANETs[C]. IEEE 6th International Conference on Mobile Ad hoc and Sensor system, Macau, China, 2009: 178-187.

葛國棟： 男，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).

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

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

Collaborative Caching and Routing Scheme Based on Local Request Similarity in Named Data Networking

Ge Guo-dong Guo Yun-fei Liu Cai-xia Lan Ju-long
(National Digital Switching System Engineering & Technological R &D Center, Zhengzhou 450002, China)

How to efficiently cache and take advantage of largely distributed copies poses challenges to the retrieval process of Named Data Networking (NDN). On the basis of similarity in local request, a collaborative caching and routing scheme is proposed. In the scheme, redundancy elimination in vertical requesting path and collaborative cache in horizontal local scope are effectively combined on the caching decision-making. In the vertical direction, the similar community which has the highest active value along the content delivery path is calculated based on the path caching strategy. In the horizontal direction, consistent Hash-caching is implemented to fulfill the oriented cache for the requested data in the vicinity. When a retrieve is requested, the proposed scheme dynamically performs the local lookup according to the content popularity by introduction of the local cache factor into the routing process. The simulation results show that the scheme can decrease the request latency, reduce the cache redundancy, and achieve higher cache hit ratio by comparison with existing methods.

Internet; Named Date Networking (NDN); Content-based routing; Caching strategy; Request similarity

TP393

A

1009-5896(2015)02-0435-08

10.11999/JEIT140246

2014-02-26收到，2014-05-30改回

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

*通信作者：葛國棟 ggd@mail.ndsc.com.cn