命名數據網絡中基于局部請求相似性的協作緩存路由機制

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

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

命名數據網絡中基于局部請求相似性的協作緩存路由機制

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

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

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

互聯網；命名數據網絡(NDN)；內容路由；緩存策略；請求相似性

1 引言

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

在NDN的設計中，采用網絡內在普遍緩存(in-network caching)的方式，在興趣包(interest packet)沿途轉發路徑(on-path)的所有節點上緩存應答內容。在路由轉發中，當節點收到興趣包，依據內容名字依次在內容存儲器(Content Store，CS)，未決請求表(Pending Interest Table, PIT)和轉發信息庫(Forwarding Information Base, FIB)中進行匹配查詢。應答數據包(data packet)攜帶請求內容，依據節點PIT表項記錄，沿相同路徑進行反向的逐跳傳輸。但是，由于NDN泛濫式的沿途全部緩存方式(Cache Everything Everywhere, CE2)，應答內容在沿途轉發路徑上所有節點都將進行存儲，致使節點緩存內容趨于同質化，導致大量的緩存冗余。在路由查找中，只針對持久穩定的內容源建立了路由條目，并沒有考慮局域節點的暫態緩存，致使傳輸路徑以外(off-path)大量的就近緩存資源無法加以利用。

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

為此，結合內容請求的局域分布特征，在NDN中提出了一種協作緩存路由機制(Collaborative Caching and Routing Scheme, CCRS)。通過構建局域的內容請求相似性社區，在垂直和水平2維空間下，聯合進行冗余消除和緩存策略設計。路由轉發時，將節點緩存因素引入到路由決策中，動態執行局域緩存查找，增大緩存命中率和就近響應概率。

2 協作緩存路由機制(CCRS)

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

2.1 內容請求相似性社區構建

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

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

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

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

2.1.2 內容相似性度量 內容請求分布在空間上具有很大程度的局域相似性[13]，處于局部區域的用戶更傾向于關注和請求相同的內容和信息。為此，提出NDN網絡內容請求相似性社區CSC，用于描述具有相似性內容請求的節點集合。

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

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

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

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

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

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

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

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

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

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

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

(2)在SAP報文中添加節點對應的Ct(v)和ρt(v )信息，向其鄰居節點發送SAP相似性通告，進行內容請求信息的局部交互；

(3)當鄰居節點接收到SAP報文后，提取Ct(v)和ρt(v)屬性內容，計算節點間對應的SC取值，并記錄節點標識和對應的到達接口，用于建立局部CGT；

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

(5)若SC≥θ，上游節點將其接收的SAP報文繼續向下游節點轉發通告；

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

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

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

2.2 基于CSC的緩存策略

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

2.2.1 路徑緩存策略 路徑緩存策略需要確定應答內容存儲的目標CSC社區，減小垂直方向上內容的重復冗余存儲。在興趣包和數據包中添加CCA字段，用于記錄和匹配興趣包沿途CSC對應的活度信息。

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

(2)數據應答過程：當vp發送數據包進行反向應答時，將上行興趣包中攜帶的maxCCA(c)添加到數據包的CCA(c)選項中，并依次比對反向傳輸路徑節點對應的活躍度信息，匹配目標CSC。進而，在該CSC內執行局域緩存操作，將內容c存儲在對應的CSC目標節點上，實現請求內容的熱點區域緩存。

2.2.2 Hash協同緩存策略 當數據包到達目標CSC后，同時執行以下兩種操作：(1)正常的數據轉發。節點依據PIT表項，向請求者發送應答內容；(2)局域定向緩存。節點執行一致性Hash運算，計算該內容的目標緩存節點nc：

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

2.3 緩存查找和路由轉發

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

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

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

表1 基于局域請求相似性的協作緩存路由機制

3 仿真與性能分析

3.1 仿真環境與參數設置

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

3.2 性能分析

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

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

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

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

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

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

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

圖3 平均請求時延ARD對比

圖4 緩存命中率CHR對比圖

圖5 局部響應率LRR對比

其中，fSAP為SAP通告頻率，SSAP為報文長度，d1為首跳鄰居通告跳數。當鄰居節點接收到SAP后，計算SC取值，如果SC≥θ，節點將SAP繼續進行轉發通告，d2為第2跳路由傳輸跳數。否則，直接丟棄，終止報文發送。

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

其中，Lc, Lρ, Lf和Li分別為內容名字、活躍因子、接口和節點標識的長度，l, m, n為對應的存儲數量。

(3)內容請求開銷(CR)：定義為內容請求過程中，興趣包(interest packet)和數據包(data packet)分別與其傳輸距離的乘積之和，大小主要取決于內容請求過程傳輸的路由跳數，代價單位取bit·hop。

其中，SInt, SDat分別表示內容請求和數據應答報文長度，d為對應的路由傳輸跳數。

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

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

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

3.3 適應性討論

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

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

4 結束語

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

圖6 ARD隨Zipf指數α的變化趨勢

圖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 “less for more” ininformation-centric networks[C]. Proceedings of IFIP Networking, Prague, Czech, 2012: 27-40.

[10] 崔現東, 劉江, 黃韜, 等. 基于節點介數和替換率的內容中心網絡網內緩存策略[J]. 電子與信息學報, 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 中的一種協作緩存機制[J].軟件學報, 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年生，博士生，研究方向為新型網絡體系結構設計、內容中心網絡.

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

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

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

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

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