基于節點熱度與緩存替換率的ICN協作緩存

丁 堯,鄭 烇,郭 晨,王 嵩

(中國科學技術大學 自動化系 未來網絡實驗室,合肥 230026)

0 概述

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

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

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

1 ICN緩存模型與相關技術

1.1 ICN緩存系統模型

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

1.2 相關技術

目前有關ICN緩存的研究主要包括2個方面:1)緩存系統性能優化,包括緩存大小規劃、緩存空間共享機制、緩存決策策略、緩存替換算法、對象可用性、緩存網絡拓撲優化;2)緩存系統建模與分析,包括對象流行度模型、外生請求到達模型、緩存網絡拓撲模型、請求關聯度模型、緩存系統穩態分析[3]。

ICN默認的緩存決策策略LCE[6]在返回路徑的每個節點緩存數據,本質上沒有協同緩存,會產生大量內容冗余備份,降低系統內容的多樣性。

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

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

關于ICN緩存問題的研究,研究者盡可能地找尋相應的協同緩存機制[10-13]。通過協同機制的作用,一方面能讓用戶更快地獲取到所需內容,另一方面減少網絡中緩存的同質化現象,更大效率地發揮緩存的作用。

2 HotRR緩存放置策略

2.1 設計思想

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

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

圖1 LCE、CLFM與HotRR策略實例

對于LCE策略,路徑上的每個節點都保留一份內容副本。現在假設用戶C請求相同的內容f,則在節點v4命中請求內容,但是在節點v1、v2、v5有冗余的內容副本。

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

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

2.2 算法實現

2.2.1 Hot緩存策略

節點的度量值Score只與節點熱度有關。周期性地動態統計節點熱度:

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

(1)

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

周期性地計算節點的度量值Score,將其作為在數據包到達時內容是否被緩存在節點的依據:

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

(2)

其中,Score[v,i]表示節點v在周期i內的得分。

2.2.2 HotRR緩存策略

綜合考慮節點熱度和緩存替換率,周期性地動態統計節點緩存替換率:

(3)

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

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

(4)

其中,Score[v,i]表示節點v在周期i內的得分。

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

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

算法HotRR

初始化:

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

α=0.2,β=0.2

T=1 s//周期

//節點v對收到的興趣包的處理過程

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

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中替換的次數

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. 將此興趣包轉發至下一跳節點

//節點v對收到的數據包的處理過程

1.if(m_CS is full)

2. ++Rep

3.if 節點v與Consumer直接相連

4. 將數據包轉發至Consumer

5. 請求最終被滿足

6. return

7.else

8. auto scoreTag=data.getTag()

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

10. 數據將被緩存在 m_CS中

11. 將數據包轉發至下一跳節點

3 實驗與結果分析

3.1 實驗性能指標

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

(5)

(6)

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

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

3.2 仿真環境及參數設置

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

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

3.3 實驗數據分析

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

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

首先,仿真拓撲結構選擇深度為8、節點數為50的隨機樹狀拓撲。

當節點的緩存容量取不同的值,LCE、CLFM、Hot、HotRR策略的平均請求跳數如圖2所示。可以看出,4種策略的平均請求跳數均隨著節點緩存容量的增大而減小,但HotRR策略性能相對而言最優,Hot策略比CLFM策略性能提升約4%,比LCE策略性能提升約21%。在考慮節點緩存替換率的基礎上,HotRR策略相對于Hot策略性能提升約5%。

圖2 平均請求跳數隨節點緩存容量的變化

源端命中率隨節點緩存容量的變換趨勢如圖3所示。可以看出HotRR策略性能相對而言最優,相對于ICN默認的LCE緩存策略,Hot策略性能提升較顯著。同時,Hot策略比CLFM性能提升約5%。同理,在考慮節點緩存替換率的基礎上,HotRR策略相對于Hot策略性能提升約8%。

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

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

圖4 平均請求跳數隨節點數量的變化

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

首先,仿真拓撲結構選擇深度為8的二叉樹。當節點的緩存容量取不同的值,LCE、CLFM、Hot策略、HotRR策略的平均請求跳數如圖5所示,源端命中率隨節點緩存容量的變換趨勢如圖6所示。可以看出,HotRR策略性能相對最優。

圖5 平均請求跳數隨節點緩存容量的變化

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

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

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

4 結束語

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

[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] 張國強,李 楊,林 濤,等.信息中心網絡中的內置緩存技術研究[J].軟件學報,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] 崔現東,劉 江,黃 韜,等.基于節點介數和替換率的內容中心網絡網內緩存策略[J].電子與信息學報,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] 曲 樺,王偉萍,趙季紅.內容中心網絡中一種改進型緩存機制[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 中的一種協作緩存機制[J].軟件學報,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.