基于節(jié)點熱度與緩存替換率的ICN協(xié)作緩存

丁 堯,鄭 烇,郭 晨,王 嵩

(中國科學(xué)技術(shù)大學(xué) 自動化系 未來網(wǎng)絡(luò)實驗室,合肥 230026)

0 概述

根據(jù)Cisco公司的VNI預(yù)測,2015年至2020年期間,全球IP流量將以22%的年均復(fù)合增長率高速增長。其中,大部分流量都由內(nèi)容獲取類應(yīng)用產(chǎn)生。除此之外,各地區(qū)流量會有顯著差異[1]。

信息中心網(wǎng)絡(luò)(Information-Centric Networking,ICN)[2]架構(gòu)的重要特征之一便是利用泛在化、透明化的網(wǎng)內(nèi)緩存來提高內(nèi)容獲取的傳輸效率和網(wǎng)絡(luò)資源利用率[3-5]。而ICN默認緩存策略LCE[6](Leave Copy Everywhere)會產(chǎn)生大量內(nèi)容冗余備份,且節(jié)點緩存替換率較高,無法充分利用緩存資源。在此基礎(chǔ)上,文獻[7]提出了CLFM(Cache Less for More)策略,但沒有考慮到介數(shù)越大的節(jié)點緩存替換率也越高,后續(xù)請求無法利用節(jié)點緩存數(shù)據(jù),而且根據(jù)網(wǎng)絡(luò)拓撲結(jié)構(gòu)計算的節(jié)點介數(shù)固定不變,無法更好地體現(xiàn)流量區(qū)域差異性和時間差異性帶來的影響。

本文提出基于節(jié)點熱度與節(jié)點緩存替換率的ICN協(xié)作緩存策略HotRR,在數(shù)據(jù)包返回路徑上選擇特殊節(jié)點緩存內(nèi)容,利用更少的緩存資源獲取更大的緩存收益。針對節(jié)點在不同區(qū)域和不同時間段內(nèi)網(wǎng)絡(luò)流量的差異性,通過動態(tài)變化的節(jié)點熱度衡量節(jié)點在網(wǎng)絡(luò)拓撲結(jié)構(gòu)中的重要程度,同時考慮節(jié)點的緩存替換率,避免重要的節(jié)點處于高頻率的內(nèi)容替換狀態(tài)。本文考慮上述因素,旨在進一步降低網(wǎng)絡(luò)延遲、網(wǎng)絡(luò)交通流量和服務(wù)器負載,從而改善緩存系統(tǒng)性能,獲得更好的用戶體驗。

1 ICN緩存模型與相關(guān)技術(shù)

1.1 ICN緩存系統(tǒng)模型

緩存命中是指一個請求在內(nèi)容分發(fā)路徑上的某個節(jié)點找到請求內(nèi)容,反之稱為未命中。如果緩存未命中,請求將會遍歷分發(fā)路徑,直到源端的內(nèi)容服務(wù)器。假設(shè)內(nèi)容單元大小相同,當節(jié)點的緩存已滿,緩存替換策略采用LRU。

1.2 相關(guān)技術(shù)

目前有關(guān)ICN緩存的研究主要包括2個方面:1)緩存系統(tǒng)性能優(yōu)化,包括緩存大小規(guī)劃、緩存空間共享機制、緩存決策策略、緩存替換算法、對象可用性、緩存網(wǎng)絡(luò)拓撲優(yōu)化;2)緩存系統(tǒng)建模與分析,包括對象流行度模型、外生請求到達模型、緩存網(wǎng)絡(luò)拓撲模型、請求關(guān)聯(lián)度模型、緩存系統(tǒng)穩(wěn)態(tài)分析[3]。

ICN默認的緩存決策策略LCE[6]在返回路徑的每個節(jié)點緩存數(shù)據(jù),本質(zhì)上沒有協(xié)同緩存,會產(chǎn)生大量內(nèi)容冗余備份,降低系統(tǒng)內(nèi)容的多樣性。

文獻[7]針對LCE問題提出了CLFM策略,其將網(wǎng)絡(luò)抽象成一張圖,由于每個緩存節(jié)點連接的情況各不相同,因此內(nèi)容緩存在不同節(jié)點上能夠發(fā)揮的效用不盡相同。CLFM通過選取圖中介數(shù)較大的節(jié)點,介數(shù)越大意味著被訪問的概率更高,把更多的緩存內(nèi)容放在這些節(jié)點上能夠更大程度發(fā)揮緩存的作用。但CLFM只重視了節(jié)點在拓撲圖中的作用,沒有考慮到緩存內(nèi)容本身發(fā)揮的作用。而且節(jié)點介數(shù)無法更好地體現(xiàn)流量的區(qū)域差異性和時間差異性所帶來的影響。隨著網(wǎng)絡(luò)規(guī)模的增大,往往越重要節(jié)點的請求越多,導(dǎo)致緩存的內(nèi)容更替頻繁,即使流行度很大也很有可能被替換掉,從而后續(xù)請求無法充分利用前期緩存[8]。

ProbCache方法[9]是一種基于概率的緩存方式。在該方法中,內(nèi)容的緩存概率和請求的距離(請求節(jié)點到提供內(nèi)容節(jié)點的度量)成反比。越接近于源節(jié)點,內(nèi)容被緩存下來的幾率就越低。同時緩存容量充足的節(jié)點在接收緩存內(nèi)容時享有比較高的優(yōu)先權(quán),其目的在于讓緩存內(nèi)容存放在接近用戶的節(jié)點上,并且盡量地減少內(nèi)容替換的發(fā)生。但是ProbCache沒有考慮緩存內(nèi)容同質(zhì)化的情況,可能會引起邊緣節(jié)點緩存的競爭。

關(guān)于ICN緩存問題的研究,研究者盡可能地找尋相應(yīng)的協(xié)同緩存機制[10-13]。通過協(xié)同機制的作用,一方面能讓用戶更快地獲取到所需內(nèi)容,另一方面減少網(wǎng)絡(luò)中緩存的同質(zhì)化現(xiàn)象,更大效率地發(fā)揮緩存的作用。

2 HotRR緩存放置策略

2.1 設(shè)計思想

在ICN網(wǎng)絡(luò)結(jié)構(gòu)中,經(jīng)過一個節(jié)點的交通流量越多,則在此節(jié)點緩存內(nèi)容更有可能發(fā)生內(nèi)容請求命中。所以,在數(shù)據(jù)包返回路徑上選擇交通流量最大的節(jié)點緩存數(shù)據(jù)可以降低興趣包的跳數(shù)。但是網(wǎng)絡(luò)交通流量具有動態(tài)性,如果用網(wǎng)絡(luò)拓撲結(jié)構(gòu)中靜態(tài)的節(jié)點介數(shù)來衡量節(jié)點的重要程度,無法體現(xiàn)網(wǎng)絡(luò)流量的區(qū)域差異性和不同時間段的差異性?？赡芡坏貐^(qū)、同一節(jié)點在不同的時間段網(wǎng)絡(luò)流量有很大波動,不同的地區(qū)和節(jié)點在同一時間段的網(wǎng)絡(luò)流量也可能有很大的波動。因此,本文提出基于節(jié)點熱度的ICN緩存策略(簡稱Hot策略),動態(tài)地統(tǒng)計節(jié)點到達的請求數(shù)作為節(jié)點熱度,以衡量節(jié)點的重要程度。在此基礎(chǔ)上,考慮到交通流量越大的節(jié)點經(jīng)過的數(shù)據(jù)包越多,節(jié)點的內(nèi)容替換越頻繁,使流行內(nèi)容在節(jié)點的緩存時間變短,導(dǎo)致網(wǎng)絡(luò)的內(nèi)網(wǎng)緩存命中率下降,延遲增大,本文在綜合考慮節(jié)點熱度和緩存替換率的基礎(chǔ)上,提出HotRR緩存放置策略,周期性地動態(tài)計算節(jié)點熱度和緩存替換率,得到內(nèi)容是否被緩存在節(jié)點的度量指標Score(節(jié)點熱度越高同時節(jié)點緩存替換率越低,節(jié)點的度量值Score越高),在數(shù)據(jù)包返回路徑上選擇Score值最高的節(jié)點緩存內(nèi)容,可以利用更少的緩存資源獲得更多的緩存收益。

下面通過實例說明本文的緩存策略,如圖1所示。在t=0時刻,所有節(jié)點的已緩存空間為空,用戶B向源服務(wù)器請求內(nèi)容f。

圖1 LCE、CLFM與HotRR策略實例

對于LCE策略,路徑上的每個節(jié)點都保留一份內(nèi)容副本?，F(xiàn)在假設(shè)用戶C請求相同的內(nèi)容f,則在節(jié)點v4命中請求內(nèi)容,但是在節(jié)點v1、v2、v5有冗余的內(nèi)容副本。

對于CLFM策略,節(jié)點v2的介數(shù)最大,在v2節(jié)點緩存內(nèi)容f。此后用戶C或者用戶A請求相同的內(nèi)容只需經(jīng)過較少的跳數(shù)就可獲取內(nèi)容,而且不會產(chǎn)生內(nèi)容f的冗余副本。但是由于v2的節(jié)點介數(shù)大,導(dǎo)致緩存替換率較高,流行內(nèi)容可能會被替換掉,后續(xù)請求只能重新到源服務(wù)器獲取內(nèi)容f。

對于HotRR策略,如果用戶B、C請求數(shù)較多,經(jīng)過節(jié)點v4的網(wǎng)絡(luò)交通流量較大,則內(nèi)容f被緩存在節(jié)點v4(同時考慮節(jié)點v4的緩存替換率,如果節(jié)點v4緩存替換率較高,則內(nèi)容f可能被緩存在v2)。如果用戶A請求數(shù)較多,經(jīng)過節(jié)點v2的網(wǎng)絡(luò)交通流量較大,則內(nèi)容f被緩存在節(jié)點v2(同時考慮節(jié)點v2的緩存替換率,如果節(jié)點v2緩存替換率較高,則內(nèi)容f可能被緩存在v4)。所以,HotRR策略會周期性地動態(tài)統(tǒng)計節(jié)點熱度和緩存替換率,根據(jù)網(wǎng)絡(luò)的實時狀況判斷內(nèi)容的放置位置,使得網(wǎng)絡(luò)的平均請求跳數(shù)較低,從而改善用戶體驗。

2.2 算法實現(xiàn)

2.2.1 Hot緩存策略

節(jié)點的度量值Score只與節(jié)點熱度有關(guān)。周期性地動態(tài)統(tǒng)計節(jié)點熱度:

Hot[v,i]=α×Hot[v,i-1]+(1-α)×rNum[v,i]

(1)

其中,Hot[v,i]表示節(jié)點v在周期i內(nèi)的節(jié)點熱度,rNum[v,i]表示節(jié)點v在第i周期內(nèi)到達的請求數(shù),α(0<α<1)表示節(jié)點v的第(i-1)周期的節(jié)點熱度在第i周期的節(jié)點熱度中所占的權(quán)重。

周期性地計算節(jié)點的度量值Score,將其作為在數(shù)據(jù)包到達時內(nèi)容是否被緩存在節(jié)點的依據(jù):

Score[v,i]=Hot[v,i]

(2)

其中,Score[v,i]表示節(jié)點v在周期i內(nèi)的得分。

2.2.2 HotRR緩存策略

綜合考慮節(jié)點熱度和緩存替換率,周期性地動態(tài)統(tǒng)計節(jié)點緩存替換率:

(3)

其中,RR[v,i]表示節(jié)點v在周期i內(nèi)的緩存替換率,β(0<β<1)表示節(jié)點v的第(i-1)周期的緩存替換率在第i周期的緩存替換率中所占的權(quán)重,m[i]表示第i周期內(nèi)被替換內(nèi)容的個數(shù),sv(fk)表示節(jié)點v被替換內(nèi)容fr的大小,C(v)表示節(jié)點v的總緩存容量。

最后,周期性地計算節(jié)點的度量值Score:

(4)

其中,Score[v,i]表示節(jié)點v在周期i內(nèi)的得分。

由于衰減因子α、β在0～1之間,通過Score[v,i]的遞歸式可知,較近周期的請求數(shù)和緩存替換率對節(jié)點得分Score影響較大,較遠周期的影響較小,可以更好地體現(xiàn)網(wǎng)絡(luò)動態(tài)性帶來的影響。

HotRR策略的算法步驟如下:在興趣包中添加Score標簽,初始化為0,用來記錄興趣包在請求路徑上所有節(jié)點中最大的節(jié)點度量值,作為數(shù)據(jù)包返回過程中內(nèi)容是否被緩存在節(jié)點的依據(jù)。興趣包每經(jīng)過一個節(jié)點,如果緩存命中,則直接返回數(shù)據(jù);如果緩存未命中,比較興趣包記錄的Score值和節(jié)點的Score值,取其大者作為興趣包的Score值,繼續(xù)往上游轉(zhuǎn)發(fā),直到請求被滿足。當興趣包被滿足時,把興趣包記錄的Score值傳遞給數(shù)據(jù)包的Score字段。在數(shù)據(jù)包返回過程中,如果路徑上節(jié)點的Score值大于等于數(shù)據(jù)包的Score值,則在此節(jié)點緩存內(nèi)容。繼續(xù)往下游轉(zhuǎn)發(fā),直至最初的內(nèi)容請求者。

算法HotRR

初始化:

?v∈V,Hot(v)=0,RR(v)=0,Score(v)=0

α=0.2,β=0.2

T=1 s//周期

//節(jié)點v對收到的興趣包的處理過程

1.++rNum(v)//請求的數(shù)量

2.if(runtime%T == 0)

3. Hot(v)=α*Hot(v)+(1-α)*rNum(v)

4. RR(v)=β*RR(v)+(1-β)*Rep/C

5. //Rep代表m_cs中替換的次數(shù)

6. //C代表m_CS的緩存大小

7. Score(v)=Hot(v)/(e^RR(v))

8.if CacheHit

9. data.setTag(make_shared(*

10. interest.getTag()))

11. return data package

12.else

13. auto scoreTag=interest.getTag()

14. if( *scoreTag< Score(v) )

15. interest.setTag(make_shared(

16. Score(v)))

17. 將此興趣包轉(zhuǎn)發(fā)至下一跳節(jié)點

//節(jié)點v對收到的數(shù)據(jù)包的處理過程

1.if(m_CS is full)

2. ++Rep

3.if 節(jié)點v與Consumer直接相連

4. 將數(shù)據(jù)包轉(zhuǎn)發(fā)至Consumer

5. 請求最終被滿足

6. return

7.else

8. auto scoreTag=data.getTag()

9. if( *scoreTag <= Score(v) )

10. 數(shù)據(jù)將被緩存在 m_CS中

11. 將數(shù)據(jù)包轉(zhuǎn)發(fā)至下一跳節(jié)點

3 實驗與結(jié)果分析

3.1 實驗性能指標

ICN緩存的目標為:1)降低內(nèi)容傳輸延遲;2)降低交通流量,避免擁塞;3)減輕服務(wù)器負載。本文提出平均請求跳數(shù)θ(t)作為目標1)和目標2)的衡量標準,源服務(wù)器命中率φ(t)作為目標3)的衡量標準:

(5)

(6)

其中,hr(t)表示時間段[t-1,t]內(nèi)請求內(nèi)容fr所需的跳數(shù),Q表示時間段[t-1,t]內(nèi)總請求數(shù),wr(t)表示時間段[t-1,t]內(nèi)在源服務(wù)器命中內(nèi)容fr請求的次數(shù)。

平均請求次數(shù)θ(t)越低,說明內(nèi)容傳輸延遲越小、交通流量越少;源服務(wù)器命中率φ(t)越低,說明請求的網(wǎng)內(nèi)命中率越高,源服務(wù)器的負載越小。

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

仿真環(huán)境:操作系統(tǒng)Ubuntu14.04 LTS 64 bit;硬件采用Intel?CoreTMi5-4200U CPU @ 1.60 GHz×4,4 GB內(nèi)存;采用基于NS3的NDN仿真器ndnSIM2.2[14]。

實驗參數(shù):總內(nèi)容數(shù)為10 000個,每個內(nèi)容為單一數(shù)據(jù)塊;到達節(jié)點的請求服從泊松分布,λ=100 request/s;內(nèi)容請求服從Zipf-Mandelbrot分布[15];選取不同的節(jié)點緩存容量進行對照實驗,緩存容量指節(jié)點可以緩存的內(nèi)容數(shù)量上限,如緩存容量為100時,該節(jié)點最多可以緩存100個內(nèi)容;仿真時間為300 s。

3.3 實驗數(shù)據(jù)分析

本文以LCE和CLFM策略作為對照實驗,以檢驗Hot策略和HotRR策略的有效性。

3.3.1 隨機樹狀拓撲對實驗的影響

首先,仿真拓撲結(jié)構(gòu)選擇深度為8、節(jié)點數(shù)為50的隨機樹狀拓撲。

當節(jié)點的緩存容量取不同的值,LCE、CLFM、Hot、HotRR策略的平均請求跳數(shù)如圖2所示?？梢钥闯?4種策略的平均請求跳數(shù)均隨著節(jié)點緩存容量的增大而減小,但HotRR策略性能相對而言最優(yōu),Hot策略比CLFM策略性能提升約4%,比LCE策略性能提升約21%。在考慮節(jié)點緩存替換率的基礎(chǔ)上,HotRR策略相對于Hot策略性能提升約5%。

圖2 平均請求跳數(shù)隨節(jié)點緩存容量的變化

源端命中率隨節(jié)點緩存容量的變換趨勢如圖3所示?？梢钥闯鯤otRR策略性能相對而言最優(yōu),相對于ICN默認的LCE緩存策略,Hot策略性能提升較顯著。同時,Hot策略比CLFM性能提升約5%。同理,在考慮節(jié)點緩存替換率的基礎(chǔ)上,HotRR策略相對于Hot策略性能提升約8%。

圖3 源端命中率隨節(jié)點緩存容量的變化

其次,考慮隨機樹狀拓撲結(jié)構(gòu)的規(guī)模對實驗的影響。取節(jié)點緩存容量為400,進行對照實驗。實驗結(jié)果如圖4所示。可以看出,HotRR策略性能相對最優(yōu)。

圖4 平均請求跳數(shù)隨節(jié)點數(shù)量的變化

3.3.2 二叉樹拓撲對實驗的影響

首先,仿真拓撲結(jié)構(gòu)選擇深度為8的二叉樹。當節(jié)點的緩存容量取不同的值,LCE、CLFM、Hot策略、HotRR策略的平均請求跳數(shù)如圖5所示,源端命中率隨節(jié)點緩存容量的變換趨勢如圖6所示?？梢钥闯?HotRR策略性能相對最優(yōu)。

圖5 平均請求跳數(shù)隨節(jié)點緩存容量的變化

圖6 源端命中率隨節(jié)點緩存容量的變化

其次,考慮不同深度的二叉樹對實驗結(jié)果的影響。取節(jié)點緩存容量為400,進行對照實驗。實驗結(jié)果如圖7所示。可以看出,可見HotRR策略性能相對最優(yōu)。

圖7 平均請求跳數(shù)隨二叉樹深度的變化

4 結(jié)束語

本文分析ICN默認的LCE緩存放置策略,針對其存在的問題,使用更能反映網(wǎng)絡(luò)動態(tài)性和節(jié)點重要性的節(jié)點熱度代替CLFM策略中的節(jié)點介數(shù),并結(jié)合節(jié)點緩存替換率提出HotRR緩存放置策略。該策略解決了LCE策略造成的緩存冗余問題,同時更有效地將內(nèi)容緩存在重要節(jié)點上,并可避免重要節(jié)點內(nèi)容被替換頻繁。仿真實驗表明,在平均請求跳數(shù)和服務(wù)器源端命中率方面,HotRR的性能皆優(yōu)于LCE和CLFM策略。下一步將在本文研究基礎(chǔ)上,結(jié)合緩存放置策略和路由機制,利用鄰域緩存信息設(shè)計性能更優(yōu)的緩存策略。

[1] Cisco Systems,Inc..Cisco Visual Networking Index:Forecast and Methodology:2015～2020[EB/OL].(2016-06-01).http://www.cisco.com/c/en/us/solutions/collate ral/service-provider/visual-networking-index-vni/complete- white-paper-c11-481360.html.

[2] BENGT A,DANNEWITZ C,IMBRENDA C,et al.A Survey of Information-Centric Networking[J].IEEE Communications Magazine,2012,50(7):26-36.

[3] 張國強,李 楊,林 濤,等.信息中心網(wǎng)絡(luò)中的內(nèi)置緩存技術(shù)研究[J].軟件學(xué)報,2014,25(1):154-175.

[4] RAN Jianhua,LV Na,ZHANG Ding,et al.On Performance of Cache Policies in Named Data Networking[C]//Proceedings of International Conference on Advanced Computer Science and Electronics Information.[S.l.]:Atlantis Press,2013:668-671.

[5] CHAO Fang,YU F R,TAO Huang,et al.A Survey of Energy-efficient Caching in Information-Centric Net-working[J].IEEE Communications Magazine,2014,52(11):122-129.

[6] JACOBSON V,SMETTERS D K,THORNTON J D,et al.Networking Named Content[C]//Proceedings of the 5th International Conference on Emerging Networking Experi-ments and Technologies.New York,USA:ACM Press,2009:1-12.

[7] CHAI W,HE D,IOANNIS P,et al.Cache “Less for More” in Information-Centric Networks[J].Computer Communications,2013,36(7):758-770.

[8] 崔現(xiàn)東,劉 江,黃 韜,等.基于節(jié)點介數(shù)和替換率的內(nèi)容中心網(wǎng)絡(luò)網(wǎng)內(nèi)緩存策略[J].電子與信息學(xué)報,2014,36(1):1-7.

[9] PSARAS I,CHAI W K,PAVLOU G.Probabilistic In-network Caching for Information-Centric Networks[C]//Proceedings of the 2nd Edition of the ICN Workshop on Information-Centric Networking.New York,USA:ACM Press,2012:55-60

[10] 曲 樺,王偉萍,趙季紅.內(nèi)容中心網(wǎng)絡(luò)中一種改進型緩存機制[J].計算機工程,2015,41(3):41-46.

[11] LI Jun,WU Hao,LIU Bin,et al.Effective Caching Schemes for Minimizing Inter-ISP Traffic in Named Data Network-ing[C]//Proceedings of IEEE International Conference on Parallel and Distributed Systems.Washington D.C.,USA:IEEE Press,2012:580-587.

[12] 劉外喜,余順爭,蔡 君,等.ICN 中的一種協(xié)作緩存機制[J].軟件學(xué)報,2013,24(8):1947-1962.

[13] MING Zhongxing,XU Mingwei,WANG Dan.Age-based Cooperative Caching in Information-Centric Networks[C]//Proceedings of IEEE INFOCOM’12.Washington D.C.,USA:IEEE Press,2012:268-273.

[14] MASTORAKIS S,AFANASYEV A,MOISEENKO I,et al.ndnSIM 2.0:A New Version of the NDN Simulator for NS-3:NDN-0028[R].Los Angeles,USA:Los Angeles University of California,Los Angeles,2015.

[15] BRESLAU L,CAO Pei,FAN Li,et al.Web Caching and Zipf-like Distributions:Evidence and Implica-tions[C]//Proceedings of the 18th Annual Joint Con-ference of the IEEE Computer and Communications Societies.Washington D.C.,USA:IEEE Press,1999:126-134.