基于動態流行度與請求代價的命名數據網絡緩存策略

郭 晨,鄭 烇,丁 堯,王 嵩

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

0 概述

為從根本上解決傳統IP網絡傳輸效率低的問題,一類以信息為中心的新型網絡體系——信息中心網絡(Information-Centric Networking,ICN)被提出[1]。命名數據網絡(Named Data Networking,NDN)[2]是ICN的主流網絡架構之一[3],NDN網絡泛在化的緩存能有效減少用戶的等待時延,節約帶寬資源,減輕服務器負載。NDN網絡緩存策略主要分為2個方面:緩存決策與緩存替換。

為高效地進行緩存替換,有不少經典NDN緩存替換策略被提出:LRU對最近最少使用的緩存內容進行替換;LFU對使用頻率少的內容進行替換[4];Age-based[5]替換策略則對請求代價小的內容進行替換;CCP[6]結合LRU與LFU的特點,實時計算內容的動態流行度,對動態流行度小的內容進行替換。雖然上述策略不同程度地提高了緩存效果,但都是基于單獨因素進行緩存內容的替換,而綜合考慮各方面的替換因素將能有效提升緩存性能。

緩存決策方面,NDN緩存的默認策略采用的是LCE(Leave Copy Everywhere),該算法在內容返回路徑中的每一個節點都會緩存內容,從而產生大量冗余副本,導致網絡緩存資源的利用率降低。針對LCE的缺點,RCOne[7]、Betw[8]、ProbCache[9]、LCD[10]、BetwRep[11]、PopBetw[12]等緩存決策策略相繼被提出。RCOne算法在內容返回路徑中隨機地選擇一個節點緩存內容,這種隨機化的緩存決策易于實現,但并未考慮內容的熱度等信息,對緩存性能的提升有限。Betw算法在內容返回時選擇興趣包請求路徑上最重要的節點緩存,其他節點不再緩存。對于不同網絡拓撲,該策略都取得了較高的網內節點緩存命中率,并減少了內容傳輸的平均跳數。然而在實際網絡中,節點緩存量遠小于內容總量,Betw算法會使重要節點負載過大及緩存替換頻率過快,導致網絡緩存性能降低。

本文綜合考慮緩存內容的動態性、流行度和請求代價,提出動態流行度與請求代價結合的緩存替換算法DPCP。在該算法中,節點單獨計算每個緩存內容的動態流行度與請求代價(Dynamic Popularity and Cost,DPC)加權值,并在緩存替換時選擇動態流行度低、請求代價小的內容。在緩存決策策略方面,為合理選擇節點放置緩存,本文提出結合內容的熱度信息與節點的重要度信息的緩存決策策略DDP。根據緩存內容的DPC值對內容進行分類,并執行區分化的緩存決策策略,將DPC值大的內容放置在重要節點上,DPC值小的內容隨機放置在某一個節點上,從而保證熱點內容盡量緩存在相對重要的節點上,同時又避免重要節點處于高頻率的內容替換狀態,同時充分利用非重要節點的緩存資源,達到提升網絡緩存性能的目的。

1 相關技術

緩存技術作為NDN網絡的關鍵技術之一,是NDN網絡的研究熱點。針對現有緩存策略的優缺點,很多不同的緩存替換策略和緩存決策策略被提出[1]。

現有的NDN緩存替換策略主要有LRU與LFU[4]。LRU(Least Recently Used)主要思想是:當有新內容轉發到節點且節點緩存空間已滿時,將最久未使用的緩存內容替換掉。LRU主要考慮內容的動態性,認為最近轉發的內容很有可能再次被請求。但是如果一個內容每隔一段時間都會被請求一次,LRU算法就會用最近的內容將它替換掉,即使最近的內容很少有人感興趣。LFU(Least Frequently Used)的核心思想是:給每一個緩存內容進行計數,緩存命中時,計數值加1,緩存替換時將計數值最小的內容替換掉。LFU主要考慮內容的流行度,認為歷史流行度高的內容被再次請求的概率大。但是如果請求的內容在動態變化時,LFU算法的性能將下降,原因是:當一個內容過去很流行,即使之后沒有人再請求,它也會一直留在緩存中,直到最近的一些被命中次數更多的內容出現。Age-based[5]緩存替換策略給每個緩存內容設置生存時間(Time-to-Live,TTL),距離源服務器越遠的緩存內容越能減少用戶的請求跳數,TTL就越大,緩存替換時則根據TTL將過期數據替換掉。CCP[6]緩存替換策略結合了LRU與LFU的優勢,周期性地統計內容的命中次數,實時計算內容的動態流行度,根據動態流行度進行緩存替換。Age-based替換策略主要考慮內容的請求代價,忽視了內容的動態流行度;CCP替換策略則與Age-based相反。這些典型緩存替換策略的主要問題是考慮因素比較單一,難以獲得較好的緩存替換效果。

在緩存決策方面,NDN的默認緩存決策策略主要是LCE。LCE算法的主要思想是在內容返回過程中使每一個節點都緩存內容。該算法復雜度低、實現簡單,但是會導致網絡中出現大量冗余副本,降低緩存的多樣性。

RCOne[7]緩存決策策略采用隨機化的思想,在內容返回路徑中隨機選取一個節點緩存內容。在如圖1所示的拓撲結構中,當用戶Client A請求內容c1時,源服務器s1提供c1,c1在返回路徑中隨機選擇v1、v2、v3中的某一個節點緩存下來。相比于LCE,RCOne雖然能一定程度上提升網絡緩存多樣性,但其在緩存放置時既沒有考慮內容熱度,也沒有考慮節點信息,對網絡緩存性能的提升有限。

圖1 實例拓撲結構

文獻[8]提出的Betw緩存決策策略,請求命中后將返回內容只緩存在路徑最重要的節點上。由于在重要節點上同一個內容被請求的次數會更多,使得內容在節點上被緩存時間變長,緩存命中率變高,從而提升緩存性能。而節點重要程度是以節點介數作為度量。節點的介數是用來描述節點在網絡中重要性的一個度量,源于復雜網絡領域,其數學定義如下:

(1)

其中,V是網絡拓撲結構所有節點的集合,s、t、v是拓撲結構中不相同的任意3個節點,CB(v)是節點v的節點介數,σs,t是節點s到節點v的所有最短路徑數,σs,t(v)是其中經過節點v的最短路徑數。節點的介數越大,它在網絡中越重要。在圖1所示的拓撲結構中,v2的節點介數最大,3個用戶節點的請求都會經過v2,Betw策略將內容緩存在v2節點可以滿足更多的請求。然而在實際網絡中節點緩存大小與網絡內容總量相比非常小,因此,重要節點到達的請求數量非常大,節點處于高頻率的內容替換狀態下,導致熱點內容也會出現很快就被替換的情況。此時大量興趣包到達重要節點后無法實現緩存命中,興趣包也只能被轉發到別的節點,直至內容源端。在圖1所示的拓撲結構中,Betw策略會把所有的內容都緩存在v2節點,但v2節點的緩存空間大小有限,高頻率的替換狀態下導致網絡緩存性能的降低。此外,v2之外的其他節點均未放置緩存,也造成了緩存資源的浪費。RCOne、Betw這些緩存決策策略的主要問題都在于沒有綜合利用內容和節點的特性。

關于NDN網絡緩存的研究,多為單獨研究緩存替換或者緩存決策。如果將兩者有效結合,利用緩存替換策略計算出的節點緩存內容熱度信息合理地進行緩存決策,將能有效提高緩存命中率,降低請求平均跳數。

2 本文算法

為提高緩存命中率、降低請求平均跳數,本文結合內容的動態性、流行度、請求代價三方面提出DPCP緩存替換算法,周期性地計算緩存表中每個內容的DPC值。DPC值越小,說明內容的動態流行度與請求代價越小,緩存替換時將DPC值小的內容替換出去。根據緩存內容的DPC值,本文將內容分為熱點內容與非熱點內容執行DDP緩存決策算法。DDP算法的核心思想是將熱點內容放置在內容返回路徑中最重要的節點上,非熱點內容隨機放置在某一節點,使熱點內容長時間存儲在重要節點上,以期在互聯網低層ISP的典型拓撲中獲得較好的緩存效果。

2.1 DPCP緩存替換算法

緩存替換算法需要考慮的內容相關因素及主要出發點如下:

1)動態性:適應內容請求的動態變化。

2)流行度:適應內容流行度的變化。

3)請求代價:距離源服務器越遠的緩存內容越能減少用戶的請求跳數。

DPCP算法分周期測量和計算內容的DPC值。內容在第i個計時周期的動態流行度(Dynamic Popularity,DP)為DP(i),則DPC(i)計算公式如下:

DPC(i)=Hopdata×DP(i)

(2)

其中,Hopdata是內容所在節點距離源服務器的跳數。距離源服務器越遠的緩存內容能更大程度地降低經過緩存內容所在節點的用戶請求跳數,從而使DPC值越高。動態流行度DP(i)的計算公式如下:

DP(i)=β×DP(i-1)+(1-β)×N(i)

(3)

其中,β是衰減因子,0<β<1,表示上一個周期的DP值在當前周期所占的比例,N(i)表示內容在第i周期被命中的次數,每個節點單獨計算CS表中緩存內容的命中次數。結合式(2)、式(3),得出的DPC值遞推計算公式如下:

DPC(i)=Hopdata×DP(i)=Hopdata×

(1-β)×(N(i)+β×N(i-1)+…)

(4)

距離當前周期越遠的周期,內容的被命中次數在當前DPC值中占的比例越小,說明分周期計算緩存內容DPC值的思想能適應內容請求的動態變化。

為了實現DPCP緩存替換策略,本文在NDN網絡原有CS、PIT、FIB表的基礎上,增加一個DPC表。

以一個簡單實例說明DPCP策略的緩存替換過程。假設β=0.4,已知緩存內容的歷史動態流行度His_DP、當前周期命中次數Cache_Hit_Num、距離源服務器跳數Hopdata,可以計算出緩存內容的當前動態流行度Cur_DP、動態流行度與DPC值,如表1所示。

表1 DPC表

在緩存替換時,將DPC值最小的緩存內容替換出去。雖然反映內容/content/1.mpg流行度的DP值是最大的,但是由于它離源服務器的距離太近,不能很好地降低該內容的請求代價,導致其DPC值最小,因此最早地被替換。

2.2 DDP緩存決策算法

NDN網絡中用戶請求到的內容是由源服務器節點或者請求路由路徑中某個節點的CS表提供[13]。為結合內容的熱度信息與節點的重要度信息合理地進行緩存放置,本文將內容分為熱點內容與非熱點內容。由于源服務器提供的內容在請求路由路徑中沒有緩存副本,說明這個內容在路徑中所有節點上的熱度都不高,因此被劃分為非熱點內容。由節點CS緩存表提供的內容,根據DPC值進行劃分。內容分類具體如下:

1)熱點內容:節點CS表中DPC值位于前40%的內容。

2)非熱點內容:源服務器提供的內容,節點CS表中DPC值位于后60%的內容。

興趣包請求如果被某一個節點CS表中DPC值位于前40%的內容滿足,那么返回的內容是熱點內容;如果被源服務器或者某一個節點CS表中DPC值位于后60%的內容滿足,則返回的內容是非熱點內容。根據內容的分類,本文提出了區分化的緩存決策策略(DDP)。具體設計思想如下:

1)熱點內容采用基于節點介數的Betw策略,緩存在內容返回路徑中節點介數最大的節點上,以滿足更多的請求。

2)非熱點內容采用隨機化的RCOne策略,隨機緩存在內容返回路徑中的某一個節點上,以降低節點介數大的節點的緩存替換頻率,同時也充分利用其他節點的緩存資源。

DDP緩存決策算法的偽代碼如下:

算法DDP

初始化(CB=0,hop=0,Bool hot=false)

興趣包到達節點v:

get(hop,hot);

hop++;

if data in cache

hot=DPC.isHoted(data);//look up the DPC table

hop=random(0,hop);//RCOne

send(data);

else if node v is server and provide data

hot=false;

hop=random(0,hop);

send(data);

else

get(CB);

if CB(v)>CB

CB=CB(v)

end if

forward interest to the next hop

end if

數據包到達節點v:

get(CB,hop,hot);

hop--;

if hot==true

if CB(v)==CB

cache(data);

end if

else

if hop==0

cache(data);

end if

end if

forward data to the next hop;

興趣包在請求的過程中,需要記錄路由路徑中所有節點的最大節點介數CB與跳數hop。興趣包請求被滿足時,判斷內容是否為熱點內容并生成一個1～hop的隨機數。熱點內容在內容返回的路徑中,將路徑中每個節點v的節點介數CB(v)與最大節點介數CB進行比較,2個值相同則將內容緩存在這個節點v上。非熱點內容每轉發1跳,隨機數減1,當隨機數減為0時,將內容緩存在這個節點上。

3 實驗與結果分析

3.1 實驗環境與參數配置

3.2 結果分析

圖2是在6種緩存策略下節點的緩存容量不同時用戶請求在全網的緩存命中率。這個命中率是在節點緩存確定后,一次實驗中被網內節點緩存命中的請求占所有用戶請求的比例。當緩存決策策略都采用LCE時,DPCP-LCE的全網緩存命中率與CCP-LCE不相上下,相比于LFU-LCE提升了22.9%。這是因為DPCP、CCP緩存替換策略能兼顧內容請求的動態性與歷史內容的流行度,根據內容的動態流行度進行緩存替換。當緩存替換策略都采用DPCP緩存替換策略時,DPCP-DDP的全網緩存命中率高于DPCP-LCE、DPCP-Betw策略,相比于DPCP-Betw策略提升了9.2%。對比結果表明,DPCP-DDP緩存策略的全網緩存命中率明顯高于其他5種策略。

圖2 全網緩存命中率隨節點緩存容量的變化

圖3是在6種不同策略下請求的平均跳數隨節點緩存容量大小的變化。平均跳數是一次實驗中所有的用戶請求被轉發的平均跳數。與圖3的全網緩存命中率結果不同,在緩存決策策略采用LCE的情況下,DPCP-LCE的平均跳數比CCP-LCE低8.9%,更低于LRU-LCE、LFU-LCE。與CCP緩存替換策略相比,DPCP緩存替換策略能兼顧動態流行度與請求代價,更有效地降低請求的平均跳數。當緩存替換策略都采用DPCP替換策略時,DPCP-DDP策略的平均跳數比DPCP-Betw策略低7.1%,更低于DPCP-LCE。對比結果表明,DPCP-DDP緩存策略的請求平均跳數是6種緩存策略中最低的。

圖3 平均跳數隨節點緩存容量的變化

4 結束語

合理利用緩存資源是NDN網絡高效傳輸數據的關鍵。為實現高效的緩存替換,本文提出結合動態流行度與請求代價的DPCP緩存替換策略。該策略能將動態流行度小、請求代價小的內容替換出去,達到提高全網緩存命中率、降低請求平均跳數的目的。同時,針對如何合理放置緩存副本的問題,進一步提出DDP緩存決策算法。首先對內容進行分類,然后對熱點內容與非熱點內容采用不同的決策算法,既保證了熱點內容盡量緩存在相對重要節點上,又能避免重要節點處于高頻率的內容替換狀態,同時也充分利用非重要節點的緩存資源,提高了網絡緩存的多樣性。實驗結果表明,將兩者結合的DPCP-DDP緩存策略能有效提高NDN緩存的整體性能。

現有的NDN緩存策略一般只考慮內容流行度,較少考慮不同區域或不同時間段內的內容請求特性。為此,下一步將設計鄰域協作緩存策略,以提高全網緩存性能。

[1] 張國強,李 楊,林 濤,等.信息中心網絡中的內置緩存技術研究[J].軟件學報,2014,25(1):154-175.

[2] ZHANG L,ESTRIN D,BURKE J,et al.Named Data Networking (NDN) Project:NDN-0001[R].Palo Alto,USA:Xerox Palo Alto Research Center,2010.

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

[4] PODLIPNIG S,B?SZ?RMENYI L.A Survey of Web Cache Replacement Strategies[J].ACM Computing Surveys,2003,35(4):374-398.

[5] MING Z,XU M,WANG D.Age-based Cooperative Caching in Information-Centric Networking[C]//Proceedings of International Conference on Computer Communication and Networks.Washington D.C.,USA:IEEE Press,2014:1-8.

[6] RAN J,LU N,ZHANG D,et al.On Performance of Cache Policies in Named Data Networking[C]//Proceedings of International Conference on Advanced Computer Science and Electronics Information.Washington D.C.,USA:IEEE Press,2013:668-671.

[7] EUM S,NAKAUCHI K,MURATA M,et al.CATT:Potential Based Routing with Content Caching for ICN[C]//Proceedings of the 2nd ICN Workshop on Information-Centric Networking.New York,USA:ACM Press,2012:49-54.

[8] CHAI W K,HE D,PSARAS I,et al.Cache “Less for More” in Information-Centric Networks[C]//Proceedings of Inter-national Conference on Research in Networking.Berlin,Germany:Springer,2012:27-40.

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

[10] LAOUTARIS N,CHE H,STAVRAKAKIS I.The LCD Interconnection of LRU Caches and Its Analysis[J].Performance Evaluation,2006,63(7):609-634.

[11] 崔現東,劉 江,黃 韜,等.基于節點介數和替換率的內容中心網絡網內緩存策略[J].電子與信息學報,2014,36(1):1-7.

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

[13] YI C,AFANASYEV A,WANG L,et al.Adaptive Forwarding in Named Data Networking[J].ACM SIGCOMM Computer Communication Review,2012,42(3):62-67.

[14] AFANASYEV A,MOISEENKO I,ZHANG L.ndnSIM:NDNSimulator for NS-3[D].Los Angeles,USA:University of California,Los Angeles,2012.

[15] MASTORAKIS S,AFANASYEV A,MOISEENKO I,et al.ndnSIM 2.0:A New Version of the NDN Simulator for NS-3:NDN-0028[R].Palo Alto,USA:Xerox Palo Alto Research Center,2015.