內(nèi)容中心網(wǎng)絡(luò)中基于差異化緩存通告的混合路由機制

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

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

內(nèi)容中心網(wǎng)絡(luò)中基于差異化緩存通告的混合路由機制

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

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

針對內(nèi)容中心網(wǎng)絡(luò)(CCN)節(jié)點暫態(tài)緩存的高效利用問題，將數(shù)據(jù)場的思想引入到CCN轉(zhuǎn)發(fā)決策中，該文提出一種基于差異化緩存通告的混合路由機制。緩存通告時，依據(jù)內(nèi)容活躍等級和緩存駐留概率，執(zhí)行差異化的內(nèi)容通告和勢能輻射；路由查找時，針對“持久穩(wěn)定”的內(nèi)容源和“動態(tài)可變”的臨時緩存副本，分別構(gòu)建全局導(dǎo)向和局域吸引勢能輻射場，實現(xiàn)興趣包請求的全局路由和局部就近應(yīng)答。仿真結(jié)果表明，該機制減小了內(nèi)容請求時延，提高了緩存命中率，以少量額外的開銷提升了CCN網(wǎng)絡(luò)整體的內(nèi)容分發(fā)性能。

內(nèi)容中心網(wǎng)絡(luò)；數(shù)據(jù)場；緩存策略；內(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ù)演進轉(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ā)展要求。為了適應(yīng)網(wǎng)絡(luò)不斷增長的數(shù)據(jù)內(nèi)容訪問需求，信息中心網(wǎng)絡(luò)(Information-Centric Networking, ICN)[1]作為一種革命式的未來互聯(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è)計的重要模式。其中，內(nèi)容中心網(wǎng)絡(luò)(Content Centric Networking, CCN)[2]作為典型的ICN結(jié)構(gòu)范例，在中間層用命名數(shù)據(jù)取代IP，數(shù)據(jù)傳輸采用“發(fā)布-請求-響應(yīng)”模式，直接以內(nèi)容名字進行路由，成為下一代Internet體系結(jié)構(gòu)的研究熱點。

在CCN設(shè)計中，采用網(wǎng)絡(luò)內(nèi)在普遍緩存(innetwork Caching)的方式，在興趣包(interest packet)沿途轉(zhuǎn)發(fā)路徑(on-path)所有節(jié)點上緩存應(yīng)答內(nèi)容，使得網(wǎng)絡(luò)不僅是一個傳輸體，更是一個內(nèi)容存儲、服務(wù)平臺。在路由轉(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)中進行匹配查詢[3]。應(yīng)答數(shù)據(jù)包(data packet)攜帶請求內(nèi)容，依據(jù)節(jié)點PIT表項記錄，沿相同路徑進行反向傳輸。

對于CCN網(wǎng)絡(luò)，如何在合理的代價開銷下，增大節(jié)點臨時緩存內(nèi)容的可用性，提升緩存資源利用率，是發(fā)揮CCN網(wǎng)絡(luò)內(nèi)容普遍緩存優(yōu)勢的關(guān)鍵。但是，CCN只針對穩(wěn)定持久的內(nèi)容源建立了路由條目，并沒有考慮局域節(jié)點的暫態(tài)緩存內(nèi)容，具體體現(xiàn)在：(1)緩存內(nèi)容的可用性只局限于目標(biāo)存儲節(jié)點，鄰近節(jié)點無法感知局部已有的緩存內(nèi)容[4]；(2)路由查找時，只實現(xiàn)了沿途傳輸路徑上內(nèi)容副本的感知，對于傳輸路徑以外大量的就近緩存資源無法加以利用。

2 問題分析

在CCN中，當(dāng)沿途節(jié)點緩存了應(yīng)答數(shù)據(jù)包攜帶的請求內(nèi)容后，將面臨以下兩個問題：(1)如何設(shè)定臨時緩存內(nèi)容的可用范圍，是只在沿途路徑可用、還是限制在局域范圍、或者向網(wǎng)絡(luò)全局進行通告；(2)后續(xù)如何發(fā)現(xiàn)這些緩存資源，即緩存內(nèi)容的路由查找。在緩存通告時，如果不加限制地將節(jié)點所有內(nèi)容向網(wǎng)絡(luò)全局進行通告，雖然增大了緩存資源的可用范圍，但是會引入大量的額外開銷，而且海量緩存信息的存儲會使已有的可擴展性問題更加突出。同時，由于緩存內(nèi)容的動態(tài)替換更新，緩存信息的一致性難以保持，增大了路由查找的錯誤率；相反，如果只將緩存內(nèi)容的可用性限制在目標(biāo)存儲節(jié)點，雖然不會引入額外的報文通告和計算開銷，卻無法有效利用節(jié)點的緩存內(nèi)容，限制了緩存資源的后續(xù)利用率。

文獻[5]對于節(jié)點緩存利用的必要性和可行性進行了分析，指出在控制平面的路由決策中，必須結(jié)合節(jié)點的暫態(tài)緩存；文獻[6]提出了一種命名數(shù)據(jù)網(wǎng)絡(luò)(Named Data Networking, NDN)的路由緩存策略(Neighbor Cache Explore routing strategy, NCE)，通過發(fā)送探測報文獲取指定鄰居范圍內(nèi)的緩存內(nèi)容，實現(xiàn)局部緩存資源利用；文獻[7]提出了一種基于勢能的目標(biāo)識別路由方法(Cache Aware Target identification, CATT)，將節(jié)點存儲的內(nèi)容副本進行局部范圍通告，實現(xiàn)緩存資源的可用性；文獻[8]為了利用網(wǎng)絡(luò)中可用的內(nèi)容資源，對穩(wěn)定內(nèi)容源建立路由表，采用確定性的路由轉(zhuǎn)發(fā)方式。對于未知的節(jié)點緩存內(nèi)容采用泛洪式的exploration探測方法進行發(fā)現(xiàn)；文獻[9]為了實現(xiàn)緩存資源的可用性，對比了主動通告和被動服務(wù)兩種模式的優(yōu)劣，提出了一種基于流行度的主動通告策略。

以上方案的不足之處主要體現(xiàn)在：(1)不加選擇地將節(jié)點緩存內(nèi)容全部進行通告，不但加劇FIB表項的擴展性問題，通告內(nèi)容的可用性也無法保證；(2)在緩存資源利用時，探測或通告范圍是固定不變的，沒有結(jié)合緩存內(nèi)容的差異化特征來區(qū)分對待；(3)路由查找獨立決策，缺乏對局域緩存資源的考慮。為此，在CCN中提出了一種基于差異化緩存通告的混合路由機制(a Hybrid Routing scheme based on Differentiated Cache Advertisement, HRDCA)。依據(jù)內(nèi)容源“持久穩(wěn)定”和臨時緩存內(nèi)容“動態(tài)可變”的差異化特征，結(jié)合數(shù)據(jù)場[10]的思想，對于穩(wěn)定內(nèi)容源構(gòu)建全局導(dǎo)向的長程勢能場，實現(xiàn)請求興趣包的全局路由；對于動態(tài)的臨時緩存副本建立局域吸引的短程輻射場，對于內(nèi)容請求進行局部吸引，提升緩存內(nèi)容整體利用率。

3 基于差異化通告的混合路由機制

圖1給出了HRDCA的基本工作流程。主要包括：(1)差異化緩存通告；(2)多樣化內(nèi)容存儲；(3)混合式路由查找3個部分。當(dāng)節(jié)點接收到興趣包后，首先查詢CS和PIT表項，當(dāng)沒有對應(yīng)的緩存內(nèi)容和請求條目時，依據(jù)HRDCA的混合路由查找策略進行興趣包轉(zhuǎn)發(fā)。當(dāng)下行數(shù)據(jù)包攜帶應(yīng)答內(nèi)容返回時，執(zhí)行局域的多樣化內(nèi)容存儲策略，減小緩存冗余，增大緩存通告內(nèi)容的有效性。

圖1 HRDCA基本工作流程

3.1 差異化緩存通告

由于網(wǎng)絡(luò)中內(nèi)容數(shù)量巨大，加之緩存內(nèi)容的“動態(tài)揮發(fā)”特性，隨時可能被替換淘汰。如果將節(jié)點所有緩存內(nèi)容向網(wǎng)絡(luò)不加限制地盲目進行洪泛通告，勢必會引入大量的緩存通告和存儲代價開銷，而且通告內(nèi)容的可用性也無法得以保證。特別是對于一些流行程度低的冷門緩存資源，由于其請求頻度很低，在節(jié)點上的駐留時間很短，反而會引入較大的緩存缺失概率，導(dǎo)致興趣包重發(fā)，增大了內(nèi)容請求時延。為此，在局域吸引勢能場建立時，需要對不同緩存內(nèi)容執(zhí)行差異化通告，針對性的選取目標(biāo)通告內(nèi)容，差異化的設(shè)置內(nèi)容輻射范圍，減小局域輻射引入的額外通告和存儲開銷，增大通告內(nèi)容的可用性。

3.1.1 通告內(nèi)容選取 在通告內(nèi)容選擇方面，需要結(jié)合不同緩存內(nèi)容的差異化特性，一方面提升通告內(nèi)容的持久性和可用性，同時盡量減小額外產(chǎn)生的通告開銷。由于內(nèi)容請求的冪律分布特征[11](Zipf或Mandelbrot-Zipf分布)，大部分內(nèi)容請求都集中在少數(shù)流行資源上，即80%的內(nèi)容請求只與20%的內(nèi)容相關(guān)。內(nèi)容的流行程度越大，請求頻率越高，在節(jié)點緩存中的駐留概率越大，對應(yīng)的緩存時間越長。為此，依據(jù)內(nèi)容流行度大小，只選取緩存內(nèi)容中的流行資源進行局域通告，建立局域吸引勢能，增大通告內(nèi)容的可用性。在HRDCA中，依據(jù)內(nèi)容請求的累加概率分布(∑p(i ))函數(shù)，將節(jié)點緩存內(nèi)容劃分為不同活躍等級，執(zhí)行不同的緩存通告決策。第1等級記為“hot”等級，定義為最活躍熱門內(nèi)容，在緩存通告時，其可用性將得到優(yōu)先保證；第3等級為“cold”等級，定義為不活躍的冷門內(nèi)容，不進行局域緩存通告，減小額外通告開銷；其余內(nèi)容劃分為第2“warm”等級，主要為中間活躍內(nèi)容。當(dāng)內(nèi)容總數(shù)N=10000, Zipf指數(shù)α=1.0時，前75項內(nèi)容請求的累加概率就達(dá)到0.5，劃分為“hot”等級；第76項到第1411項內(nèi)容請求的累加概率達(dá)到了0.8，為“warm”等級；其余內(nèi)容(1412-10000)劃分為“cold”等級。而且，隨著Zipf指數(shù)α的增大，第1和第2等級包含的內(nèi)容對象會更加集中，大量的“cold”等級內(nèi)容將不執(zhí)行局域通告，有效減小了緩存通告數(shù)量和額外開銷。

3.1.2 輻射范圍設(shè)置 在輻射范圍設(shè)置方面，結(jié)合內(nèi)容請求分布的局域性特征，將內(nèi)容的通告范圍限制在有限的局域跳數(shù)之內(nèi)，減小內(nèi)容通告產(chǎn)生的報文開銷。在HRDCA中，依據(jù)緩存內(nèi)容所屬的活躍等級，執(zhí)行差異化的區(qū)分通告，對于不同活躍等級的內(nèi)容設(shè)置不同的輻射范圍。緩存內(nèi)容的活躍等級越高，駐留時間越長，對應(yīng)的通告范圍越大。對于第1等級內(nèi)容，取較大的通告范圍，例如3跳；對于第3等級內(nèi)容，不進行通告，輻射范圍為0；對于第2等級內(nèi)容，取較小的通告區(qū)域，例如1跳鄰居范圍。當(dāng)內(nèi)容總數(shù)N=10000, Zipf指數(shù)α=1.0時，HRDCA只對流行程度最大的前75項內(nèi)容進行局域大范圍通告，大量非流行的冷門資源(1412-10000)輻射范圍將設(shè)置為0。圖2給出了緩存內(nèi)容通告報文(Cache Advertisement Packet, CAP)的具體格式。

圖2 緩存內(nèi)容通告報文CAP

其中，報文類型字段表示報文類型，時間戳字段用來記錄報文的發(fā)送時間。CAP可以一次通告多個內(nèi)容副本，并且為不同內(nèi)容設(shè)置不同的通告范圍，每通告一跳，通告范圍減1，直到為0結(jié)束。

3.2 多樣化內(nèi)容緩存

在CCN中，采用的是沿途全部緩存方式，應(yīng)答內(nèi)容在沿途路徑上所有節(jié)點都將進行存儲，致使節(jié)點緩存內(nèi)容趨于同質(zhì)化，導(dǎo)致大量緩存冗余。節(jié)點存儲內(nèi)容的同質(zhì)化，將大大降低差異化緩存通告的必要性，因為相同內(nèi)容的互相冗余通告不會帶來任何收益。為此，為了保證內(nèi)容通告的有效性，減小緩存冗余，增大局域內(nèi)容存儲的多樣性，提出了一種基于動態(tài)緩存概率的局域多樣化內(nèi)容存儲策略。

(1)內(nèi)容請求：內(nèi)容請求者cv發(fā)送興趣包請求，通過興趣包逐跳地上行傳輸，依次記錄并更新傳輸路徑長度l，每當(dāng)興趣包到達(dá)下一跳節(jié)點，傳輸跳數(shù)加1。最終，當(dāng)興趣包到達(dá)內(nèi)容提供者pv后，l記錄的就是沿途節(jié)點的個數(shù)，即傳輸路徑長度。

(2)數(shù)據(jù)應(yīng)答：當(dāng)pv發(fā)送數(shù)據(jù)包進行應(yīng)答時，依據(jù)l首先計算沿途節(jié)點的初始緩存概率：1/pl=。當(dāng)數(shù)據(jù)包到達(dá)第1跳節(jié)點時，首先檢查：(a)該節(jié)點CS是否包含該應(yīng)答內(nèi)容；(b)該節(jié)點是否處于其他鄰居節(jié)點的通告輻射范圍，即存儲了該應(yīng)答內(nèi)容的緩存通告信息。若條件(a)和條件(b)任一項成立，直接進行數(shù)據(jù)包下行轉(zhuǎn)發(fā)，在該節(jié)點不執(zhí)行內(nèi)容存儲。若不成立，將以概率p隨機決定在該節(jié)點是否緩存內(nèi)容。如果緩存，將p重置為0，避免后續(xù)節(jié)點的冗余存儲；否則，p將不斷累加更新：p=p+1/l，以增大后續(xù)節(jié)點的緩存概率。隨著數(shù)據(jù)包逐跳的下行傳輸，節(jié)點的緩存概率將不斷增大。同時，通過判斷條件(a)和條件(b)的成立，避免了應(yīng)答內(nèi)容的冗余重復(fù)緩存，增大了緩存通告的有效性。表1給出了算法的具體流程。

表1 基于動態(tài)緩存概率的局域多樣化內(nèi)容存儲策略

3.3 混合路由查找

圖3給出HRDCA的路由查找過程。當(dāng)節(jié)點接收到內(nèi)容請求后，首先確定在該節(jié)點周圍是否存在局部吸引勢能。如果存在就近緩存內(nèi)容，則依據(jù)最大的局域吸引勢能確定下一跳轉(zhuǎn)發(fā)節(jié)點，實現(xiàn)內(nèi)容請求的就近應(yīng)答。若節(jié)點周圍不存在臨時緩存內(nèi)容的輻射，按照全局導(dǎo)向勢能場執(zhí)行興趣包的下一跳轉(zhuǎn)發(fā)。

3.3.1 全局導(dǎo)向 將內(nèi)容源中存儲的內(nèi)容對象看作是穩(wěn)定的點電荷，由于內(nèi)容源相比臨時緩存內(nèi)容，穩(wěn)定性高，可用性可長久保證。為此，對于穩(wěn)定內(nèi)容源，構(gòu)建全局導(dǎo)向長程勢能場。在前向轉(zhuǎn)發(fā)表FIB中，添加勢能信息選項(Potential Information Field, PIF)，當(dāng)節(jié)點接收到內(nèi)容源通告報文時，在PIF中添加接口對應(yīng)的勢能值大小。由于數(shù)據(jù)源穩(wěn)定性高，F(xiàn)IB中的勢能導(dǎo)向信息無需進行頻繁更新。勢能值的大小可以依據(jù)內(nèi)容通告報文傳輸?shù)穆酚商鴶?shù)來計算，隨著路由跳數(shù)的增加線性衰減。對于內(nèi)容C，在節(jié)點iv處的全局導(dǎo)向勢能值為

圖3 混合路由查找過程

其中，vp為內(nèi)容源節(jié)點，QC為初始勢能導(dǎo)向值，dist(vi,vp)為vi與vp的之間的路由跳數(shù)。

3.3.2 局域吸引

(1)吸引勢能計算：由于臨時緩存內(nèi)容的動態(tài)更新特性，隨時可以被替換淘汰，不適于建立全局的導(dǎo)向勢能場。為此，結(jié)合2.1節(jié)提出的差異化緩存通告，對于節(jié)點緩存內(nèi)容建立局部輻射的短程勢能場，并采用具有快速衰減特性的高斯勢函數(shù)[10]來計算局部吸引勢能。在高斯勢函數(shù)中，任一場點x處的勢能值為

(2)轉(zhuǎn)發(fā)接口選擇：對于特定內(nèi)容對象，在局部范圍可能存在多個緩存副本，分布在不同的存儲節(jié)點上，不妨設(shè)為k個，對應(yīng)的緩存節(jié)點集合為。這k個緩存內(nèi)容都將在節(jié)點

vn產(chǎn)生吸引勢能ψ(vn)，記為。當(dāng)vn接收到興趣包后，由于vn同時處于多個緩存內(nèi)容的局域吸引場中，為了提升目標(biāo)緩存內(nèi)容的可用性，增大緩存命中率，選擇駐留概率最大的通告內(nèi)容作為轉(zhuǎn)發(fā)目標(biāo)。vn在ψ(vn)中選擇最大局域吸引勢能對應(yīng)的鄰居接口(neighbor(vn))轉(zhuǎn)發(fā)內(nèi)容請求，確定下一跳路由節(jié)點vnext：

4 仿真及性能分析

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

采用ndnSIM[13]進行仿真與性能分析，該工具對于CCN基本數(shù)據(jù)單元結(jié)構(gòu)和路由轉(zhuǎn)發(fā)流程均已實現(xiàn)，并提供了開放的源碼和運行實例。在GT-ITM下采用Locality模型生成30個路由節(jié)點的平面網(wǎng)絡(luò)拓?fù)洹＞W(wǎng)絡(luò)中內(nèi)容對象總數(shù)N為10000個，大小設(shè)為10 kByte。節(jié)點緩存容量一致，CS均設(shè)為100，鏈路帶寬100 Mbit/s。在網(wǎng)絡(luò)中設(shè)置2個內(nèi)容服務(wù)器，負(fù)責(zé)內(nèi)容對象的存儲和發(fā)布，各服務(wù)器隨機存儲5000個內(nèi)容。其余節(jié)點作為用戶接入節(jié)點，發(fā)布內(nèi)容請求，內(nèi)容請求到達(dá)服從λ=50個/s的泊松過程[13]，請求概率服從Zipf分布[11]，第i個內(nèi)容的請求概率為：。仿真時間設(shè)為200 s,CQ=1，初始節(jié)點緩存狀態(tài)為空，無任何內(nèi)容副本存儲，緩存替換策略為最近最少使用策略(Least Recently Used, LRU)。HRDCA中，依據(jù)內(nèi)容請求的累加概率(∑p(i))來劃分內(nèi)容活躍等級，將累加概率到達(dá)0.5時包含的內(nèi)容對象劃分為第1等級熱門內(nèi)容，0.5～0.8區(qū)間包含的內(nèi)容劃分為第2等級，其余內(nèi)容為第3“cold”等級，各等級內(nèi)容對應(yīng)的輻射范圍設(shè)為(h,w,c)。

4.2 性能分析

將本文提出的HRDCA與文獻[2] CCN，文獻[6] NCE和文獻[7] CATT進行對比分析，性能評價指標(biāo)包括：平均請求時延(Average Request Delay, ARD)，緩存命中率(Cache Hit Ratio, CHR)以及額外開銷對比。

4.2.1 平均請求時延 平均請求時延ARD：節(jié)點發(fā)送請求興趣包到接收到應(yīng)答數(shù)據(jù)包之間的平均延遲。圖4分別給出了α=1.0, h=2,w=1,c=0和α=1.2, h=3,w=2,c=0時，各方案的ARD對比，采樣時間間隔T和緩存內(nèi)容通告間隔AT設(shè)為2 s, NCE的探測范圍Scope和CATT內(nèi)容通告范圍m設(shè)為2跳。仿真初始階段，由于網(wǎng)絡(luò)所有節(jié)點存儲狀態(tài)為空，發(fā)送的興趣包請求都需要轉(zhuǎn)發(fā)至內(nèi)容服務(wù)器進行響應(yīng)，ARD較大。隨著內(nèi)容的不斷存儲，緩存內(nèi)容的響應(yīng)概率逐漸增加，ARD隨之減小。

在CCN中，內(nèi)容請求只能利用沿途路徑上的緩存資源，對于沿途路徑以外的局域緩存內(nèi)容無法加以利用，ARD明顯大于其他方案；對于NCE和CATT，在緩存資源探測和內(nèi)容通告決策時，缺乏對于緩存內(nèi)容差異化特征的考慮，無法保證通告內(nèi)容的可用性，增大了緩存內(nèi)容缺失概率，缺失內(nèi)容需要重新進行路由轉(zhuǎn)發(fā)，導(dǎo)致ARD增大；對于HRDCA，依據(jù)緩存內(nèi)容的活躍度和駐留概率來選取目標(biāo)通告內(nèi)容、設(shè)定內(nèi)容輻射范圍，實現(xiàn)緩存內(nèi)容的差異化通告和輻射，提升了局域緩存資源的可用性，使興趣包請求盡可能在局部實現(xiàn)就近應(yīng)答，ARD最小。

4.2.2 緩存命中率 緩存命中率CHR：網(wǎng)絡(luò)中節(jié)點緩存內(nèi)容響應(yīng)興趣包請求的概率。圖5分別給出了α=1.0,h=2,w=1,c=0和α=1.2, h=3,w=2, c=0時，整個仿真時間T=200 s內(nèi)，各方案的CHR對比。由于CCN和NCE采用的是沿途全部緩存方式，應(yīng)答內(nèi)容的重復(fù)冗余存儲將導(dǎo)致緩存內(nèi)容的頻繁替換，降低了緩存駐留概率和利用率。對于NCE和CATT，不加選擇地盲目式內(nèi)容通告，無法保證通告內(nèi)容的有效性。特別是對于大量非流行通告資源，由于駐留時間過短，加劇了緩存查找缺失概率；HRDCA按照內(nèi)容的活躍等級，選取通告目標(biāo)內(nèi)容，確定輻射范圍，有效地保證了通告內(nèi)容的有效性，CHR分別達(dá)到了0.421和0.502。

4.2.3 代價開銷對比 相比CCN, NCE, CATT和HRDCA，為了實現(xiàn)局域緩存資源的利用，都不同程度地引入了額外代價開銷，主要包括緩存通告開銷，節(jié)點存儲開銷，下面對HRDCA開銷進行定量分析。

(1)緩存通告開銷(AC)：在局域吸引勢能場構(gòu)建時，緩存內(nèi)容通告引入的開銷，定義為緩存通告報文CAP與其傳輸距離的乘積，大小取決于CAP報文長度、通告頻率和路由傳輸跳數(shù)，代價單位取數(shù)據(jù)大小(bit)與傳輸跳數(shù)(hop)的乘積。單位時間內(nèi)緩存通告開銷AC為

圖4 平均請求時延ARD對比

圖5 緩存命中率CHR對比

其中，CAPf為CAP通告頻率，max表示緩存內(nèi)容的最大輻射范圍。表示首跳緩存通告消息長度，d1為通告跳數(shù)。當(dāng)鄰居節(jié)點接收到后，將通告范圍(Scope)減1，并刪除通告范圍為0的內(nèi)容信息，得到第2跳緩存通告消息的長度, d2為對應(yīng)的路由跳數(shù)。依次類推，直到CAP中通告范圍全部為0結(jié)束。

(2)節(jié)點存儲開銷(CC)：在HRDCA中，相比CCN方案，在建立局域吸引勢能場時，當(dāng)節(jié)點接收到CAP報文后，需要記錄相應(yīng)的內(nèi)容名字，到達(dá)接口信息，以及每個接口對應(yīng)的吸引勢能值大小，引入了額外的存儲代價。其大小取決于存儲的內(nèi)容名字、接口信息和勢能值的長度和數(shù)量，代價單位為bit。

其中，Ln, Lf和Lp分別表示內(nèi)容名字、接口信息和吸引勢能值的長度，l,m,n分別為對應(yīng)的存儲數(shù)量。

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

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

表2給出了α=1.0, NCE的探測范圍和CATT內(nèi)容通告范圍m取值為2跳時，各方案的代價開銷對比。在CCN中沒有相應(yīng)的局域緩存內(nèi)容發(fā)現(xiàn)機制，所以不會引入額外的緩存通告開銷AC和節(jié)點存儲開銷CC。但是，在內(nèi)容請求時，由于無法利用沿途傳輸路徑以外的就近緩存內(nèi)容，對應(yīng)的內(nèi)容請求開銷RC最大。在HRDCA中，采用差異化的緩存內(nèi)容選擇和通告，相比NCE和CATT盲目式的全部通告方式，有效減小了額外引入的通告開銷AC和節(jié)點存儲開銷CC，增大了通告內(nèi)容的有效性。HRDCA通過少量額外AC,CC的付出，增大了內(nèi)容請求的就近響應(yīng)率，換取了RC的大幅下降。

表3給出在α=1.2, NCE的探測范圍和CATT內(nèi)容通告范圍m為3跳時，各方案的額外開銷對比。隨著α的增大，內(nèi)容請求更加集中在少數(shù)的流行資源上，流行內(nèi)容的有效集中使HRDCA引入的額外開銷AC和CC大幅減小。但是，對于NCE和CATT，隨著通告范圍的增大，引入了更多AC和節(jié)CC。

4.3 適應(yīng)性討論

圖6給出了ARD隨Zipf指數(shù)α的變化趨勢。當(dāng)α取值較小時，內(nèi)容請求分布不能有效集中，在α取值為0.2和0.4時，最大流行內(nèi)容的請求概率僅為0.0005和0.0024，多樣化的內(nèi)容請求和存儲將導(dǎo)致有限存儲空間高頻率的替換更新，增大了ARD。隨著α的增大，內(nèi)容請求的集中性和局域性不斷加強，流行資源在緩存中的駐留概率和響應(yīng)率明顯增大，請求時延逐步減小。特別是當(dāng)α取值位于0.8到1.2區(qū)間時，內(nèi)容請求的集中性顯著增大，累加概率為0.8包含的內(nèi)容數(shù)量從3894項減小到189項，ARD大幅下降。但是，隨著α的取值的進一步增大(α＞1.2)，流行資源對應(yīng)的內(nèi)容分布已無顯著變化，ARD下降趨勢逐漸減緩。

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

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

圖7給出了在α=1.0時，各方案ARD隨節(jié)點緩存容量的變化趨勢。隨著節(jié)點緩存容量(CS)的不斷增加，更多的請求內(nèi)容可以被存儲在中間節(jié)點上，提高了緩存命中率CHR，各方案對應(yīng)的ARD不斷減小。當(dāng)節(jié)點緩存空間較小時，HRDCA采用動態(tài)緩存概率的多樣化存儲策略，有限減小了垂直請求路徑上緩存冗余，增大了緩存空間利用率。在局域吸引勢能場建立時，依據(jù)內(nèi)容活躍等級和緩存駐留概率，執(zhí)行差異化的內(nèi)容通告和勢能計算，提升了通告內(nèi)容的可用性，減小了額外引入的節(jié)點存儲開銷。HRDCA充分發(fā)揮和利用了節(jié)點有限的緩存空間，對應(yīng)ARD最小，對于緩存容量的變化具有良好的適應(yīng)性。

5 結(jié)束語

為了實現(xiàn)節(jié)點臨時緩存資源的有效利用，結(jié)合數(shù)據(jù)場的思想，在CCN中提出了一種基于差異化緩存通告的混合路由機制。針對“持久穩(wěn)定”的內(nèi)容源和“動態(tài)可變”的臨時緩存副本，分別構(gòu)建了全局導(dǎo)向和局域吸引勢能輻射場，實現(xiàn)內(nèi)容請求的全局路由和局部就近應(yīng)答。HRDCA增大了緩存內(nèi)容命中率，以少量額外開銷換取了內(nèi)容請求性能的顯著提升，仿真結(jié)果和對比分析顯示了其有效性。后續(xù)研究工作包括：(1)將HRDCA擴展到移動ICN環(huán)境中，解決請求者和數(shù)據(jù)源的移動性問題；(2)在不同網(wǎng)絡(luò)和仿真參數(shù)條件下對于HRDCA性能和開銷進行分析驗證。

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

圖7 平均請求時延ARD隨緩存容量的變化趨勢

[1] Trossen D, Sarela M, and Sollins K. Arguments for an information-centric internetworking architecture[J]. ACM SIGCOMM Computer Communications Review, 2010, 40(2): 26-33.

[2] Jacobson V, Smetters D K, Thronton J D, et al.. Networking named content[C]. Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies, Rome, Italy, 2009: 1-12.

[3] 崔現(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.

[4] Chiocchetti R, Perino D, Carofiglio G, et al.. INFORM: a dynamic interest forwarding mechanism for information centric networking[C]. Proceedings of the ACM SIGCOMM Workshop on Information-Centric Networking, Hong Kong,China, 2013: 9-14.

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

[6] 葉潤生, 徐明偉. 命名數(shù)據(jù)網(wǎng)絡(luò)中的鄰居緩存路由策略[J]. 計算機科學(xué)與探索, 2012, 6(7): 593-601.

Ye Run-sheng and Xu Ming-wei. Neighbor cache explore routing strategy in NDN[J]. Journal of Frontiers of Computer Science and Technology, 2012, 6(7): 593-601.

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

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

[9] Dai H C, Lu J Y, Wang Y, et al.. A two-layer intra-domain routing scheme for named data networking[C]. Proceedings of the IEEE Globe Telecommunications Conference, Anaheim, USA, 2012: 2815-2820.

[10] 淦文燕, 赫南, 李德毅, 等. 一種基于拓?fù)鋭莸木W(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法[J]. 軟件學(xué)報, 2009, 20(8): 2241-2254.

Gan Wen-yan, He Nan, Li De-yi, et al.. Community discovery method in networks based on topological potential[J]. Journal of Software, 2009, 20(8): 2241-2254.

[11] Kim Y and Yeom I. Performance analysis of in-network caching for content-centric networking[J]. Computer Networks, 2013, 57(13): 2465-2482.

[12] Psaras I, Clegg R G, Landa R, et al.. Modelling and evaluation of CCN-caching trees[C]. Proceedings of IFIP TC 6 Networking Conference, Valencia, Spain, 2011: 78-91.

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

葛國棟： 男，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ò)和高性能路由.

A Hybrid Routing Scheme Based on Differentiated Cache Advertisement in Content Centric Networking

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

How to efficiently utilize the temporary cached replicas poses challenges to the retrieval process of Content Centric Networking (CCN). Inspired by the idea of data fields, a hybrid routing scheme based on differentiated cache advertisement is proposed. In the scheme, depending on the content popularity and resident probability, the differentiated advertisement strategy is performed to choose the advertised content and calculate the attracting potential. When a retrieve is requested, in order to realize global routing and local response to the content request, the globally oriented potential field and locally attracting potential field are constructed for the stable original content source and volatile cached copies, respectively. The simulation results show that the scheme can decrease the request latency, increase the cache hit ratio, while improving the overall performance of content delivery with a small amount of additional overhead.

Content Centric Networking (CCN); Data field; Caching strategy; Content-based routing

TP393

A

1009-5896(2015)03-0700-08

10.11999/JEIT140527

2014-04-22收到，2014-06-13改回

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

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