蔡君,余順爭,劉外喜
(1.廣東技術(shù)師范學(xué)院 電子與信息學(xué)院,廣東 廣州 510665;2.中山大學(xué) 電子與信息工程系,廣東 廣州 510006;3.廣州大學(xué) 電子信息工程系,廣東 廣州 510006)
為了適應(yīng)互聯(lián)網(wǎng)應(yīng)用由發(fā)送者驅(qū)動的端對端通信模式向接收者驅(qū)動的海量內(nèi)容獲取模式的轉(zhuǎn)變,同時增強網(wǎng)絡(luò)對安全性、業(yè)務(wù)質(zhì)量、移動性、可擴展性等方面的支持,研究者們近年來提出了一類以信息為中心的新型網(wǎng)絡(luò)體系架構(gòu),統(tǒng)稱為信息中心網(wǎng)絡(luò)(ICN,information-centric networking),典型的如:DONA[1]、CCN/NDN[2]、PURSUIT[3]、COMET[4]和 GreenICN 項目[5]。在這類ICN網(wǎng)絡(luò)中,為緩解當前網(wǎng)絡(luò)流量的快速增長對網(wǎng)絡(luò)帶寬造成的嚴峻壓力,每個節(jié)點都增加了內(nèi)置緩存功能。雖然緩存機制也是目前互聯(lián)網(wǎng)中用于提高網(wǎng)絡(luò)性能的重要手段之一,緩存理論及相關(guān)技術(shù)也已經(jīng)在Web、CDN和P2P中得到了較為廣泛的應(yīng)用,但目前的緩存策略主要針對某一具體應(yīng)用,并需配置成一個覆蓋網(wǎng)絡(luò)。因此,這些緩存策略與中間節(jié)點共享數(shù)據(jù)時,效率較低。然而,ICN中的緩存是網(wǎng)絡(luò)架構(gòu)內(nèi)在的一部分(每個節(jié)點都具有該功能),與應(yīng)用無關(guān),具有網(wǎng)絡(luò)自適應(yīng)等特性,因而,傳統(tǒng)的面向Web、CDN和P2P緩存算法也就不能直接應(yīng)用于ICN中。近年來,研究者們對ICN中的緩存優(yōu)化方法進行了探索,得出了許多研究成果,主要集中在2個方面:一是判斷內(nèi)容是否被節(jié)點緩存的緩存決策策略[6~14];二是單節(jié)點緩存內(nèi)容的替換策略[15]。
在緩存決策策略方面:ICN原始提案實行的是處處緩存(CEE, cache everything everywhere)策略[6],即所有的內(nèi)容對象被要求緩存于去往目的地途中的所有節(jié)點。這直接降低了緩存系統(tǒng)所能緩存內(nèi)容的多樣性,導(dǎo)致了嚴重的緩存浪費,因為請求被任意中間節(jié)點響應(yīng)后而不會再往上游節(jié)點轉(zhuǎn)發(fā),其上游某些節(jié)點緩存的內(nèi)容可能根本沒有機會響應(yīng)后來的請求而因緩存空間受限被替換。最近,Chai等[7]提出了基于介數(shù)(betweenness),即Betw策略的選擇性緩存機制,只將對象放置于 ICN中興趣分組(interest packet)沿途中介數(shù)最大的節(jié)點,即對象僅緩存于最重要的節(jié)點處。與CEE策略相比,這種策略具有較高的緩存命中率,并且減少了節(jié)點的替換次數(shù),但由于內(nèi)容請求的社團性質(zhì),依然存在局限性,即大部分的內(nèi)容緩存在全網(wǎng)介數(shù)相對大的部分節(jié)點處,導(dǎo)致內(nèi)容對象在空間分布上不合理,網(wǎng)絡(luò)性能亦隨之降低,主要體現(xiàn)在:1) 大部分的網(wǎng)絡(luò)流量與介數(shù)大的節(jié)點相關(guān),從而降低了網(wǎng)絡(luò)的負載容量;2) 高介數(shù)節(jié)點的替換次數(shù)大幅增加,增加了節(jié)點的計算開銷,因而不能滿足ICN節(jié)點線速執(zhí)行的要求;3) 由于網(wǎng)絡(luò)介數(shù)是描述節(jié)點網(wǎng)絡(luò)全局重要度的指標,高介數(shù)的節(jié)點處并不一定是網(wǎng)絡(luò)中大部分用戶最容易訪問的位置。針對以上問題,基于Internet網(wǎng)絡(luò)拓撲結(jié)構(gòu)的社團特性[8]——社團內(nèi)部節(jié)點之間連接相對緊密,社團之間的節(jié)點之間的連接則相對稀疏,所以把內(nèi)容分別緩存于其經(jīng)過的各社團內(nèi)節(jié)點社團重要度最大的節(jié)點處。因為在同一社團中,社團重要度大的節(jié)點不僅越容易被社團內(nèi)的節(jié)點訪問,而且也越容易被社團外的節(jié)點訪問。這樣做不僅能提高網(wǎng)絡(luò)的緩存效率,節(jié)約網(wǎng)絡(luò)的緩存空間,而且能使網(wǎng)絡(luò)內(nèi)容在網(wǎng)絡(luò)空間上的分布變得更加均勻和合理。
在緩存替換策略方面:為保證ICN節(jié)點運行于高速的網(wǎng)絡(luò)環(huán)境,目前在ICN的諸多緩存策略中[8,9,17],采用較多的還是簡單易運行的 LRU(least recently used)或 LFU(least frequently used)。但是,如果在全網(wǎng)中,所有節(jié)點都以內(nèi)容在該節(jié)點處被訪問的頻率大小或被訪問的時間先后為標準,采用相同的替換機制,將直接導(dǎo)致內(nèi)容對象在時間上分布不合理,即在熱門時間里,社團內(nèi)的每個節(jié)點都緩存到相同的對象,這將不利于緩存空間的合理利用。然而,在熱門時間過后,該內(nèi)容對象在各節(jié)點上又幾乎同時消失,若需訪問該內(nèi)容,又會產(chǎn)生比較大的網(wǎng)絡(luò)時延,抑制網(wǎng)絡(luò)的整體性能。為此,本文基于Internet網(wǎng)絡(luò)拓撲結(jié)構(gòu)的社團特性,在每個社團內(nèi),每一個節(jié)點進行內(nèi)容替換時,不僅考慮內(nèi)容在該節(jié)點處被訪問的情況,還考慮到了該節(jié)點在社團中的位置,使同一社團中各節(jié)點采用混合的替換機制,即通過節(jié)點社團重要度確定替換節(jié)點緩存隊列中的內(nèi)容對象位置的概率,如節(jié)點社團重要度大的節(jié)點,在緩存隊列中靠后位置的內(nèi)容對象被替換的概率大;而節(jié)點重要度度小的節(jié)點,在緩存隊列中靠前位置的內(nèi)容對象被替換的概率大,以達到內(nèi)容對象在時間上的合理分布。
本文貢獻如下:1) 基于復(fù)雜網(wǎng)絡(luò)的節(jié)點社團重要度,提出了一種確定ICN緩存位置的決策策略,使內(nèi)容對象在空間上分布更合理;2) 基于復(fù)雜網(wǎng)絡(luò)的節(jié)點社團重要度和內(nèi)容對象在各節(jié)點處的訪問情況,提出了一種ICN節(jié)點混合替換策略,使內(nèi)容對象在時間上分布更合理;3) 在多種實驗條件下對CSNIC策略進行了仿真驗證,結(jié)果表明該策略與CEE+LFU、Betw+LRU和Opportunistic相比,能更好地提升包括緩存命中率、跳數(shù)減少率、內(nèi)容差異性及替換數(shù)量等在內(nèi)的網(wǎng)絡(luò)緩存性能指標,并且CSNIC的通信開銷和計算開銷都較小。
緩存作為ICN的一個關(guān)鍵組件,最近受到了很多研究者的廣泛關(guān)注,而緩存決策策略和緩存替換策略是緩存的2個關(guān)鍵點。緩存決策策略用于確定內(nèi)容對象的緩存位置,在最初的 ICN原始提案中,實行的是CEE (cache everything everywhere)策略,即所有的內(nèi)容對象被要求緩存于去往目的地途中的所有節(jié)點,這種處處緩存的機制已被證明導(dǎo)致了嚴重的緩存浪費[10]。為此,Eum等[11]提出了一種在對象返回沿途節(jié)點中隨機選擇節(jié)點進行緩存的機制,該機制易于實現(xiàn),但未考慮對象的訪問頻率,緩存效率不高,緩存性能的穩(wěn)定性也得不到保證。Psaras等[12]提出了一種基于加權(quán)概率的緩存機制,即對象在返回途中的緩存概率與節(jié)點和請求者的距離成反比,該方法提高了內(nèi)容在距離請求者更近的節(jié)點進行緩存的概率,但也會增加不同對象在邊緣緩存節(jié)點的競爭。最近,Chai等[7]提出了基于介數(shù)(betweenness)的選擇性緩存機制,只將對象放置于 Interest沿途中介數(shù)最大的節(jié)點,即:對象緩存于更重要的節(jié)點上從而實現(xiàn)更高的擊中率,并減少替換次數(shù)。與此類似,He等[13]應(yīng)用另一種網(wǎng)絡(luò)全局節(jié)點重要度的測度方法確定 ICN節(jié)點緩存對象。而實際上,這2種以節(jié)點全局重要度來確定緩存位置的方法并不能使內(nèi)容對象在空間上分布變得更加均勻和合理,并導(dǎo)致了許多額外的問題(如引言中所述)。Hu等[14]提出一種Opportunistic緩存策略,該策略基于內(nèi)容在每個節(jié)點的訪問情況和該內(nèi)容源與節(jié)點之間距離確定內(nèi)容是否被該節(jié)點緩存的概率,由于各節(jié)點相互獨立,因而緩存空間的利用率不高。劉外喜等[15]基于用戶的潛在需求,并結(jié)合帶寬換緩存的思想,利用鏈路的冗余帶寬,將內(nèi)容分流到相鄰節(jié)點緩存,改善緩存效率,但該方法需要一些開銷。在張國強等[9,17]的綜述性論文中,對目前的信息中心網(wǎng)絡(luò)的一些緩存策略進行了詳細的總結(jié)。而本文方法與以上方法的主要區(qū)別在于,本文基于 Internet網(wǎng)絡(luò)的社團特性,從節(jié)點社團重要度(局部重要度)出發(fā),把內(nèi)容緩存于社團內(nèi)和社團外用戶容易訪問的節(jié)點處,使內(nèi)容對象在網(wǎng)絡(luò)上的空間分布相對均勻,同時實現(xiàn)緩存資源的充分利用。
緩存替換算法已在傳統(tǒng)的 Web緩存中得到了廣泛的研究,Podlipnig等對其進行較全面的綜述[18]。在目前ICN緩存策略研究中,普遍采用2種簡單易行的LRU或LFU替換策略。本文同樣采用的是LRU策略,但不同的是,本文是以節(jié)點社團重要度為依據(jù),在同一社團內(nèi),不同重要度的節(jié)點實行概率制的LRU策略,使緩存對象在時間上合理分布。
圖1 基于節(jié)點重要度的決策緩存位置
CSNIC緩存決策機制的原理是:ICN興趣分組在經(jīng)過每個社團時,都會記錄下其所經(jīng)過的每一個社團中節(jié)點重要度最大的節(jié)點,同時在以數(shù)據(jù)分組的形式返程時將內(nèi)容對象緩存于這些節(jié)點上。下面通過一個簡單實例對 CSNIC緩存決策機制進行分析,如圖1所示。如用戶A需從S處獲取一個內(nèi)容,首先用戶A通過圖1實線路徑發(fā)送興趣分組,并記錄該路徑上所經(jīng)過的社團以及各自社團內(nèi)所經(jīng)歷的節(jié)點中節(jié)點社團重要度的最大值。當搜索到內(nèi)容對象緩存(或內(nèi)容服務(wù)器)的位置S后,內(nèi)容對象沿圖1虛線路徑(興趣包的反向路徑)返回。在返回過程中,匹配各社團節(jié)點重要度的值,若與興趣包路徑保存的節(jié)點社團最大值一致,則在該節(jié)點處緩存該內(nèi)容對象,否則,徑自通過該節(jié)點。如圖1所示,數(shù)據(jù)分組在返回過程中經(jīng)過了社團 1、社團 2和社團 3,在所經(jīng)過的每個社團的節(jié)點中,節(jié)點社團重要度最大的節(jié)點分別為v1、v2和v3。因此,將內(nèi)容對象在v1、v2和v3處緩存。而這些節(jié)點正是各自社團內(nèi)用戶容易達到的位置。這樣,社團 1、社團2、社團3內(nèi)的用戶需再次訪問該內(nèi)容時,直接從緩存該內(nèi)容的節(jié)點處獲取即可,與緩存于其他節(jié)點相比,該方法實現(xiàn)了內(nèi)容在網(wǎng)絡(luò)空間上的合理分布,減少了網(wǎng)絡(luò)的延時,提高了網(wǎng)絡(luò)的傳輸效率。
CSNIC替換機制的原理是:以網(wǎng)絡(luò)的社團為一個單位,在同一社團內(nèi)根據(jù)各個節(jié)點的節(jié)點社團重要度和內(nèi)容對象在該節(jié)點處被訪問的時間先后順序,選擇不同的內(nèi)容對象進行替換,即通過節(jié)點社團重要度確定節(jié)點緩存隊列中的內(nèi)容對象被替換的概率,如節(jié)點社團重要度大的節(jié)點,在緩存隊列中流行度低的內(nèi)容對象被替換的概率大;而節(jié)點重要度度小的節(jié)點,在緩存隊列中流行度高的內(nèi)容對象被替換的概率大,以達到內(nèi)容對象在時間上的合理分布。簡而言之,并不是所有節(jié)點都使用相同的替換機制。
若ICN節(jié)點緩存建模為大小為C個對象的隊列,以最近最少使用的時間順序進行排列。假定第i個社團內(nèi)節(jié)點j的節(jié)點社團重要度為Iij,在該社團內(nèi)的平均節(jié)點社團重要度為。當有一內(nèi)容對象在該節(jié)點需緩存時,將按照概率pij(k)替換該節(jié)點緩存隊列的第k個位置的內(nèi)容(k∈ [1 ,C]),pij(k)定義如式(2)所示。
其中,α為歸一化因子,滿足式(3),β為概率調(diào)節(jié)系數(shù)。
下面對CSNIC緩存策略在ICN架構(gòu)中的實現(xiàn)過程進行分析。首先,假定每個節(jié)點的社團重要度I值和每個節(jié)點內(nèi)的每個位置的替換概率是通過離線方式提前計算得到(如通過中心網(wǎng)絡(luò)管理系統(tǒng))。當一個用戶向某一內(nèi)容對象發(fā)起請求興趣分組,在興趣分組中記錄下它所經(jīng)歷的社團以及在每個社團中所經(jīng)歷的節(jié)點中節(jié)點社團重要度的最大值。當興趣分組達到內(nèi)容對象所在的服務(wù)器或者中間路由器時,這些值將被嵌入數(shù)據(jù)分組內(nèi)。在數(shù)據(jù)分組沿興趣分組路徑逆向傳輸過程中,每個社團內(nèi)的路由器匹配自己的I值與數(shù)據(jù)分組的附加值,如果2個值匹配,則該內(nèi)容被緩存。如果在同一社團內(nèi)有多個節(jié)點的I值相同,那么這些節(jié)點都將緩存該對象。在確定內(nèi)容對象需緩存后,再根據(jù)該節(jié)點緩存隊列中各位置的替換概率確定被替換內(nèi)容對象。從以上分析可知,CSNIC緩存決策策略在執(zhí)行過程中的開銷比較小,每個節(jié)點決定是否緩存是相互獨立的,完全是基于節(jié)點所在社團的重要度的值,既不需要與其他節(jié)點交互信息,也無需推斷服務(wù)器的位置和流量模式。CSNIC替換策略也僅與節(jié)點社團重要度和該節(jié)點的緩存隊列相關(guān)。由于在 CSNIC策略中,離線方式預(yù)先計算的I值充分考慮了節(jié)點在網(wǎng)絡(luò)中的位置和與其鄰居的關(guān)系,因而它又是一種協(xié)作式或合作式的緩存策略。在每個社團內(nèi)其轉(zhuǎn)發(fā)請求和內(nèi)容的偽碼如算法1所示。
算法1 (CSNIC緩存策略)
Content request
1) Initialize (Ii-max=0); 在興趣分組中記錄第i個社團中的節(jié)點社團最大值
2) foreach (jfrom 0 toNi); 在社團i中經(jīng)歷Ni個節(jié)點
3) if data in cache
4) then send (data)
5) else
6) GetIij
7) ifIij>Ii-max
8) thenIi-max=Iij
9) Forward request to the next hop towardN
Content data
…
1) recordIi-maxfrom corresponding content request
2) foreach (jfrom 0 toNi)
3) GetIij
4) ifIij==Ii-max
5) then cache (data)
6) forward data packet to the next hop towardNi
ICN引入緩存的主要目的為:1)減輕服務(wù)器負載,因為一次緩存命中,意味著服務(wù)器減少一次用戶請求;2) 降低用戶對內(nèi)容請求的延遲,借助緩存,用戶能快速從鄰近緩存位置獲取所請求內(nèi)容,而不是從服務(wù)器端;3)減少網(wǎng)絡(luò)流量和網(wǎng)絡(luò)堵塞,當緩存命中后,內(nèi)容請求將經(jīng)過更少的跳數(shù)(hops)到達用戶。在達到這些目的的同時,由于ICN緩存線速執(zhí)行的條件,對此提出了以下要求:1)在有限的緩存空間內(nèi)緩存更多的不同種類的內(nèi)容;2)減少替換次數(shù)。
為量化以上ICN緩存的目的和要求,引入緩存命中率(CHR, cache hit ratio)對目的1)進行評估,其定義為:由緩存而不是由服務(wù)器端響應(yīng)用戶請求的概率。定義跳數(shù)減少率(HRR, hop reduction ratio)對目的2)和目的3)進行評估,其定義如式(4)所示。
其中,Hr(t)和hr(t)分別表示在[t-1,t]時間段內(nèi),用戶從服務(wù)器和緩存位置獲取內(nèi)容fr所需要的跳數(shù)。若網(wǎng)絡(luò)中沒有緩存,則Hr(t) =hr(t),此時的HRR恒為1。定義內(nèi)容差異性(CDR, content diversity ratio)對要求1)進行評估,其被定義為緩存中所有內(nèi)容的種類數(shù)量與網(wǎng)絡(luò)中由服務(wù)器所產(chǎn)生的內(nèi)容種類總數(shù)量的比值,CDR值越大,則在相同緩存空間內(nèi)所緩存的內(nèi)容種類數(shù)越多。定義替換數(shù)量(NR,number of replacement)對要求2)進行評估,其定義為一個興趣分組在一個節(jié)點上引起的替換次數(shù),由于在ICN中緩存要求線速執(zhí)行,因此頻繁地替換緩存內(nèi)容并不合適。
ICN緩存模型構(gòu)建方式如下。首先,假定網(wǎng)絡(luò)具有發(fā)布/訂閱的網(wǎng)絡(luò)架構(gòu),即網(wǎng)絡(luò)中的內(nèi)容請求和分發(fā)機制已經(jīng)存在。用圖G=(V,E)表示具有N個節(jié)點、M條邊的無向無權(quán)網(wǎng)絡(luò),其中,V=v1,v2,…,vN表示網(wǎng)絡(luò)中節(jié)點的集合,E=e1,e2,…,eM表示網(wǎng)絡(luò)中邊的集合。F=f1,f2,…,fR表示網(wǎng)絡(luò)中的內(nèi)容的集合,S=s1,s2,…,sp表示網(wǎng)絡(luò)中內(nèi)容服務(wù)器的集合,并且每個內(nèi)容服務(wù)器與一個節(jié)點v∈V相對應(yīng)。內(nèi)容隨機地分布在服務(wù)器S中,并假定每個內(nèi)容對象僅保存于一個服務(wù)器中。
實驗網(wǎng)絡(luò)的拓撲由100個節(jié)點和386條鏈路組成[22],其中描述網(wǎng)絡(luò)的社團特性的模塊度Q=0.794,Q>0.3表明網(wǎng)絡(luò)具有明顯的社團特性[23]。本文采用多個性能參數(shù)將 CSNIC策略與CEE+LFU策略、Betw+LRU策略、Opportunistic策略進行比較,其中包含系統(tǒng)的緩存命中率、跳數(shù)減少率、內(nèi)容差異性和替換數(shù)量變化。下面重點討論節(jié)點緩存空間大小、內(nèi)容數(shù)量、替換概率調(diào)節(jié)系數(shù)(β)和網(wǎng)絡(luò)社團結(jié)構(gòu)對 CSNIC策略的緩存性能的影響。
1) 節(jié)點緩存空間大小的影響
在該實驗過程中,用戶數(shù)量設(shè)置為50 000,Zipf參數(shù)(α)的參數(shù)設(shè)置為 1.2,替換概率調(diào)節(jié)系數(shù)(β)設(shè)置為0.7,節(jié)點緩存空間大小從10 MB至320 MB變化。
圖2為4種緩存策略的緩存命中率隨網(wǎng)絡(luò)節(jié)點緩存空間的變化情況。從圖可以看出,4種緩存策略的緩存命中率都隨網(wǎng)絡(luò)中節(jié)點緩存空間的增大而增大。這是由于節(jié)點緩存空間增大,緩存的內(nèi)容增多,用戶在緩存內(nèi)容的節(jié)點處獲取所需內(nèi)容的概率增大,從而導(dǎo)致緩存命中率增大。但在這個過程中,CSNIC策略的性能一直優(yōu)于其他3種策略。導(dǎo)致這一結(jié)果的主要原因是:CEE+LFU策略實行把所有的內(nèi)容對象緩存于去往目的地途中所有節(jié)點,這樣直接浪費了節(jié)點的緩存空間,網(wǎng)絡(luò)中緩存的內(nèi)容減少導(dǎo)致網(wǎng)絡(luò)的緩存命中率降低;Betw+LRU策略把內(nèi)容緩存到全網(wǎng)介數(shù)最大的節(jié)點,間接地閑置了其他節(jié)點的緩存空間;Opportunistic策略提高了流行度高的內(nèi)容在靠近用戶節(jié)點處的緩存概率,與上 2種策略相比,提高了網(wǎng)絡(luò)緩存的命中率。而CSNIC策略不僅在空間上把內(nèi)容合理地分布在網(wǎng)絡(luò)中不同的社團內(nèi),而且在時間上合理地利用了社團內(nèi)節(jié)點社團重要度較低的節(jié)點的緩存空間,因而更能提高系統(tǒng)的緩存命中率。
圖2 緩存命中率對緩存空間的影響
圖3顯示了跳數(shù)減少率對網(wǎng)絡(luò)節(jié)點緩存空間大小的變化情況,從圖可以看出,4種緩存策略的跳數(shù)減少率都隨網(wǎng)絡(luò)中節(jié)點緩存空間大小的增大而減少,這是由于節(jié)點緩存空間增大,緩存的內(nèi)容增多,用戶獲取所需內(nèi)容的跳數(shù)減少,從而跳數(shù)減少率降低。但在這個過程中,CSNIC策略的性能一直優(yōu)于其他 3種策略。導(dǎo)致這一結(jié)果的主要原因是CSNIC策略把內(nèi)容緩存到社團內(nèi)節(jié)點和社團外節(jié)點相對容易訪問的位置,從而降低了跳數(shù)減少率。
圖3 跳數(shù)減少率對緩存空間的影響
圖4為網(wǎng)絡(luò)內(nèi)容差異率對網(wǎng)絡(luò)節(jié)點緩存空間的變化情況,從圖可以看出,4種緩存策略的內(nèi)容差異率都隨網(wǎng)絡(luò)中節(jié)點緩存空間的增大而增大,這是由于節(jié)點緩存空間增大,緩存的內(nèi)容增多,節(jié)點之間內(nèi)容差異性增大。但在這個過程中,CSNIC策略的性能一直優(yōu)于其他3種策略。雖然Betw+LRU策略在內(nèi)容的傳輸過程中僅緩存介數(shù)最大的節(jié)點,在一定的緩存空間條件下,Betw+LRU策略在網(wǎng)絡(luò)中緩存內(nèi)容的差異性通常被認為最好,但深入的分析發(fā)現(xiàn),由于緩存空間有限,其結(jié)果是介數(shù)大節(jié)點的替換次數(shù)增加,并沒有大幅增加網(wǎng)絡(luò)內(nèi)容的差異性。由于Opportunistic策略在內(nèi)容返回過程不僅考慮了內(nèi)容在節(jié)點處的流行度,而且通過概率機制考慮了內(nèi)容的差異性,因而,Opportunistic策略性能優(yōu)于Betw+LRU策略。而對CSNIC策略,在同一社團中,將不同流行度的內(nèi)容緩存到網(wǎng)絡(luò)不同的節(jié)點處,使在同一社團內(nèi)各節(jié)點緩存內(nèi)容具有明顯的差異性,是內(nèi)容在網(wǎng)絡(luò)中的時間分布趨于合理,相當于均勻分配了內(nèi)容在網(wǎng)絡(luò)中每個社團內(nèi)的分布,直接地提高了緩存內(nèi)容差異率。同時,在現(xiàn)實網(wǎng)絡(luò)中,不同社團具有不同的喜好,這樣相當于在不同社團之間內(nèi)容對象再進行了一次合理分布。因而,在這4種緩存決策策略中,CSNIC策略的內(nèi)容差異率是最佳的。
圖4 內(nèi)容差異率對緩存空間的影響
表 1為替換數(shù)量隨緩存大小變化的結(jié)果:Betw+LRU在 4種機制中的替換數(shù)量最小;CEE+LRU中每一個興趣分組都會引起一次替換,所以為一常數(shù);而 CSNIC策略的替換數(shù)量略微高于Betw+LRU,Opportunistic策略與CSNIC策略非常接近。但Betw+LRU策略的替換主要集中于高介數(shù)的節(jié)點處,在單一節(jié)點頻繁地替換并不滿足ICN架構(gòu)中緩存要求線速執(zhí)行的條件。
表1 替換數(shù)量VS緩存大小
2) 內(nèi)容數(shù)量的影響
在該實驗過程中,節(jié)點緩存空間的大小設(shè)置為20 MB,用戶數(shù)量設(shè)置為50 000,Zipf參數(shù)(α)的參數(shù)設(shè)置為 1.2,替換概率調(diào)節(jié)系數(shù)(β)設(shè)置為0.7,其中內(nèi)容數(shù)量在200至6 400范圍內(nèi)變化。
圖5~圖7分別為緩存命中率、跳數(shù)減少率和內(nèi)容差異率隨網(wǎng)絡(luò)中的內(nèi)容數(shù)量變化的關(guān)系,從圖5~圖7可以看出,4種緩存策略的緩存命中率、跳數(shù)減少率和內(nèi)容差異率的性能都隨網(wǎng)絡(luò)中緩存的內(nèi)容的數(shù)量增大而減弱,這是由于隨著網(wǎng)絡(luò)中內(nèi)容數(shù)量增大,需要緩存內(nèi)容增多,用戶在緩存內(nèi)容節(jié)點處獲取所需內(nèi)容的概率降低,從而導(dǎo)致緩存性能減弱。但在這個減弱的過程中,CSNIC策略的性能一直優(yōu)于其他3種策略。導(dǎo)致這一結(jié)果的主要原因與上述節(jié)點緩存空間大小情況的討論類似,網(wǎng)絡(luò)中內(nèi)容數(shù)量的增加相當于網(wǎng)絡(luò)中節(jié)點緩存空間的減少。
圖5 緩存命中率對內(nèi)容數(shù)量的影響
圖6 跳數(shù)減少率對內(nèi)容數(shù)量的影響
圖7 網(wǎng)絡(luò)內(nèi)容差異率對內(nèi)容數(shù)量的影響
4種緩存策略的替換數(shù)量隨內(nèi)容數(shù)量變化的結(jié)果與緩存空間變化的情況類似:Betw+LRU在4種機制中的替換數(shù)量最??;CEE+LRU中每一個興趣分組都會引起一次替換,為一常數(shù);而 CSNIC和Opportunistic的替換數(shù)量相當,略高于Betw+LRU。
3)Zipf(α)參數(shù)的影響
在該實驗過程中,用戶數(shù)量設(shè)置為50 000,節(jié)點緩存空間的大小設(shè)置為20 MB,替換概率調(diào)節(jié)系數(shù)(β)設(shè)置為 0.7,Zipf參數(shù)(α)的參數(shù)設(shè)置為 0.2至1變化。
現(xiàn)有實證研究顯示網(wǎng)絡(luò)用戶對內(nèi)容的偏好服從Zipf分布[24],Zipf參數(shù)α越大,表示用戶的偏好越集中,并且用戶對不同網(wǎng)絡(luò)應(yīng)用的α值也有差異。因此,下面通過變化α值測試CSNIC策略對不同網(wǎng)絡(luò)應(yīng)用的表現(xiàn)。圖8~圖10分別為緩存命中率、跳數(shù)減少率和內(nèi)容差異率隨Zipf參數(shù)α變化的關(guān)系。從圖8可知,4種策略的緩存命中率都隨參數(shù)α增大而增大,但在這個過程中,CSNIC策略的性能一直優(yōu)于其他3種策略,導(dǎo)致這一結(jié)果的主要原因是4種策略都利用了時間的局域性,但除此此外,CSNIC策略還充分利用空間的局域性。圖9和圖10顯示,跳數(shù)減少率和內(nèi)容差異率隨著參數(shù)α的增大都有減少,但CSNIC策略一直保持較明顯的性能優(yōu)勢。
圖8 緩存命中率對Zipf(α)的影響
圖9 跳數(shù)減少率對Zipf(α)的影響
圖10 網(wǎng)絡(luò)內(nèi)容差異率對Zipf(α)的影響
4) 網(wǎng)絡(luò)社團結(jié)構(gòu)的影響
現(xiàn)有實證研究顯示 Internet網(wǎng)絡(luò)具有明顯的社團特性[16],網(wǎng)絡(luò)特性的量化指標用模塊度Q值表示,Q值越高,表示網(wǎng)絡(luò)的社團特性越明顯,現(xiàn)實網(wǎng)絡(luò)的社團結(jié)構(gòu)在0.3~0.7之間。因CSNIC策略的實現(xiàn)與節(jié)點社團重要度直接相關(guān),而節(jié)點社團重要度與網(wǎng)絡(luò)的社團結(jié)構(gòu)相聯(lián)系。為研究網(wǎng)絡(luò)的社團特性對緩存策略的影響,本文采用了由Yan等提出的SFC模型[25],該模型生成的網(wǎng)絡(luò)不僅全網(wǎng)節(jié)點的度和社團內(nèi)節(jié)點的度都具有無標度特征,而且網(wǎng)絡(luò)社團特性可調(diào),與現(xiàn)實中 Internet網(wǎng)絡(luò)比較接近。選擇合適參數(shù)生成節(jié)點數(shù)為300、模塊度Q從0.3變化到0.7的網(wǎng)絡(luò)。圖11~圖13為實驗結(jié)果,其中橫軸為網(wǎng)絡(luò)模塊度的大小。從圖可知,隨著網(wǎng)絡(luò)模塊度的增加,CSNIC策略的緩存性能(緩存命中率、跳數(shù)減少率和內(nèi)容的差異率)的波動不是很大,而CEE+LRU、Betw+LRU和Opportunistic策略隨著網(wǎng)絡(luò)社團模塊度的增加,緩存性能有所下降,這是由于 CSNIC策略把內(nèi)容緩存到社團內(nèi)節(jié)點容易獲取的位置,而其他3種策略隨著網(wǎng)絡(luò)社團結(jié)構(gòu)的增強,若用戶想獲取的內(nèi)容不在所屬社團內(nèi)的節(jié)點處緩存,將加大獲取的難度。
圖11 緩存命中率對網(wǎng)絡(luò)模塊度(Q)的影響
圖12 跳數(shù)減少率對網(wǎng)絡(luò)模塊度(Q)的影響
圖13 網(wǎng)絡(luò)內(nèi)容差異率對網(wǎng)絡(luò)模塊度(Q)的影響
5) 替換調(diào)節(jié)系數(shù)(β)的影響
在該實驗過程中,用戶數(shù)量設(shè)置為50 000,Zipf參數(shù)(α)的參數(shù)設(shè)置為1.2,節(jié)點緩存空間的大小設(shè)置為10 MB至320 MB變化,替換概率調(diào)節(jié)系數(shù)(β)設(shè)置為0.3至1.5變化。
圖 14為內(nèi)容差異率隨替換概率調(diào)節(jié)系數(shù)(β)和節(jié)點緩存空間的大小變化的曲面圖,從圖可以看出,內(nèi)容差異率的性能隨著β系數(shù)的變化發(fā)生變化。在β=0.7時,內(nèi)容差異率達到最大值,即在同一社團內(nèi),根據(jù)其在社團中的重要度,通過調(diào)節(jié)不同節(jié)點內(nèi)內(nèi)容的替換概率,以達到每個節(jié)點的緩存空間的充分利用。緩存命中率和跳數(shù)減少率的變化趨勢與內(nèi)容差異率的變化趨勢類似,限于篇幅,在文中沒有給出它們的變化曲線。進一步實驗發(fā)現(xiàn),為使內(nèi)容對象在時間的分布上獲取一個好的結(jié)果,替換概率調(diào)節(jié)系數(shù)(β)的取值還與網(wǎng)絡(luò)節(jié)點的緩存空間大小分布有關(guān)。但由于網(wǎng)絡(luò)節(jié)點緩存空間的大小在網(wǎng)絡(luò)設(shè)計規(guī)劃時已經(jīng)固定,替換概率調(diào)節(jié)系數(shù)(β)對于具體的網(wǎng)絡(luò)是固定的,因而在網(wǎng)絡(luò)中易于布局。
圖14 替換概率調(diào)節(jié)系數(shù)(β)和緩存空間對內(nèi)容差異率的影響
6) 策略的開銷分析
下面從計算開銷和通信開銷 2個方面分析CSNIC策略。
計算開銷:CSNIC策略緩存決策策略和替換策略中的節(jié)點社團重要度的如式(3)所示,只需求出表示網(wǎng)絡(luò)節(jié)點連接關(guān)系的鄰接矩陣的所有特征值和特征向量。而現(xiàn)實中的大部分網(wǎng)絡(luò)為稀疏網(wǎng)絡(luò),利用Lanczos算法和QL算法,求稀疏對稱矩陣的所有特征值和特征向量的時間復(fù)雜度為O(nm)[26],其中n和m分別表示網(wǎng)絡(luò)的節(jié)點數(shù)和邊數(shù),其計算復(fù)雜度較低,并且每個節(jié)點的社團重要度都是通過離線方式計算存儲的。在替換過程中概率的計算也是僅為O(k),其中k為每個節(jié)點的緩存空間大小,所以CSNIC策略滿足ICN對每個節(jié)點緩存處理線速的要求。
通信開銷:在興趣分組和 Data分組僅需保存所經(jīng)過的社團內(nèi)節(jié)點社團重要度最大節(jié)點的值, 而每次通信,找到用戶所需內(nèi)容所經(jīng)過的社團數(shù)量一般在2個左右,顯然,CSNIC策略的通信開銷很低。
從上分析可知,CSNIC策略易于實現(xiàn),以較小的開銷獲得很好的性能改善。
如何高效地利用ICN中每個節(jié)點的緩存功能,提高網(wǎng)絡(luò)傳輸性能,成為了ICN架構(gòu)應(yīng)用于實際環(huán)境的關(guān)鍵問題之一。為此,本文提出了一種應(yīng)用Internet網(wǎng)絡(luò)拓撲結(jié)構(gòu)的社團特性,基于每個節(jié)點在其所屬社團的重要度確定內(nèi)容緩存位置和緩存替換的緩存策略。通過在不同網(wǎng)絡(luò)環(huán)境進行仿真實驗,實驗結(jié)果驗證了本文方法的有效性。
由于目前實驗條件的限制,本文僅考慮了網(wǎng)絡(luò)的靜態(tài)拓撲信息的社團特性,為更合理地確定內(nèi)容的緩存位置,Internet網(wǎng)絡(luò)的社團特性也應(yīng)根據(jù)網(wǎng)絡(luò)的實際運行狀態(tài)動態(tài)變化。因此,下一步工作將基于軟件定義網(wǎng)絡(luò)(SDN)的設(shè)計理念,感知網(wǎng)絡(luò)的實時狀態(tài)信息,從 ICN 架構(gòu)的實際流量出發(fā),構(gòu)建加權(quán)有向復(fù)雜網(wǎng)絡(luò)。在 SDN的控制層,根據(jù)節(jié)點的社團特性來確定內(nèi)容的緩存位置。然后通過SDN的數(shù)據(jù)層執(zhí)行這一決策,進一步提高ICN架構(gòu)的緩存性能。
[1] MOHIT C, BYUNG-GON C, ANDREY E,et al.A data-oriented (and beyond) network architecture[A].Proceedings of the 2007 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications[C].2007.181-192.
[2] VAN J, DIANA K, JAMES D.Networking named content[A].CoNEXT '09 Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies[C].2009.1-12.
[3] Conceptual architecture: principles, patterns and sub-components descriptions[EB/OL].http://www.fp7-pursuit.eu/PursuitWeb/, 2011.
[4] WEI K C.Curling: content-ubiquitous resolution and delivery infrastructure for next-generation services[J].IEEE Communications Magazine,2011, 49(3): 112-120.
[5] FP7/NICT GreenICN project[EB/OL].http://www.greenicn.Org.
[6] GHODSI A, SHENKER S, KOPONEN T,et al.Information-centric networking: seeing the forest for the trees[A].HotNets-X Proceedings of the 10th ACM Workshop on Hot Topics in Networks[C].2011.1-6.
[7] CHAI W, HE D, PSARAS I,et al.Cache less for more in information-centric networks(extended version)[J].Computer Communications, 2013, 36(7): 758-770.
[8] 黃韜, 劉江, 霍如等.未來網(wǎng)絡(luò)體系架構(gòu)研究綜述[J].通信學(xué)報,2014, 35(8):184-197.HUANG T,LIU J,HUO R,et al.Survey of research on future network architectures[J].Journal on Communications, 2014, 35(8):184-197.
[9] 張國強, 李楊, 林濤等.信息中心網(wǎng)絡(luò)中的內(nèi)置緩存技術(shù)研究[J].軟件學(xué)報, 2014, 25(1): 154-175.ZHANG G Q,LI Y,LIN T,et al.Survey of in-network caching techniques in information-centric networks[J].Journal of Software, 2014,25(1): 154-175.
[10] GHODSI A, SHENKER S, KOPONEN T,et al.Information-centric networking: seeing the forest for the trees[A].HotNets-X Proceedings of the 10th ACM Workshop on Hot Topics in Networks[C].2011.1-6.
[11] EUM S, NAKAUCHI K, MURATA M,et al.CATT: potential based routing with content caching for ICN[A].Proceedings of the Second Edition of the ICN Workshop on Information-Centric Networking[C].2012.49-54.
[12] SAINO L, PSARAS I, PAVLOU G.Hashing routing scheme for information-centric networking[A].Pro of the 3rd ACM SIGCOMM Workshop on Information-Centric Networking[C].2013.27-32.
[13] HE Y, ZHU Y, SHI J,et al.A cache strategy in content-centric networks based on node's importance[J].Information Technology Journal,2014, 13(3): 588-592.
[14] HU X, GONG J.Opportunistic on-path caching for named data networking[J].IEICE Transactions on Communications, 2014, 97(11):2360-2367.
[15] 劉外喜, 余順爭, 胡曉等.CCN 中選擇性緩存機制的研究[J].計算機學(xué)報, 2014, 37(2): 275-288.LIU W X,YU S Z,HU X,et al.Selective caching in content-centric networking[J].Chinese Journal of Computers, 2014, 37(2): 275-288.
[16] ERIKSEN K A, SIMONSEN I, MASLOV S,et al.Modularity and extreme edges of the Internet [J].Physical Review Letters, 2003,90(14):148701-148704.
[17] ZHANG G Q, LI Y, LIN T.Caching in information centric networking:a survey[J].Computer Networks, 2013, 57(16): 3128-3141.
[18] PODLIPNIG S, B?SZ?RMENYI L.A survey of Web cache replacement strategies[J].ACM Computing Surveys, 2003, 35(4): 374-398.
[19] CHAUHAN S, GIRVAN M, OTT E.Spectral properties of networks with community structure [J].Physical Review, 2009, 80(5): 56114.
[20] WANG Y, DI Z R, FAN Y.Identifying and characterizing nodes important to community structure using the spectrum of the graph[J].PLos ONE, 2011, 6(11): 1-10.
[21] 蔡君, 余順爭.一種有效提高無標度網(wǎng)絡(luò)負載容量的管理策略[J].物理學(xué)報, 2013, 62(5):058901.CAI J, YU S Z.An efficient management strategy for enhancing traffic capacity in scale-free networks[J].Acta Physica Sinica, 2013, 62(5):058901.
[22] CALVERT K I, DOAR M B, ZEGURA E W.Modeling Internet topology[J].Communications Magazine, IEEE, 1997,35(6): 160-163.
[23] NEWMAN M E J, GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E, 2004,69(2): 26113.
[24] BRESLAU L, CAO P, FAN L,et al.Web caching and zipf-like distributions: evidence and implications[A].IEEE INFOCOM[C].1999.126-134.
[25] YAN G, FU Z Q, REN J,et al.Collective synchronization induced by epidemic dynamics on complex networks with communities[J].Physical Review E, 2007, 75(1): 16108.
[26] NEWMAN M.Networks: an Introduction[M].Oxford University Press, Inc, 2010.