內容中心網絡中一種改進型緩存機制

曲 樺,王偉萍,趙季紅,2

(1.西安交通大學電子與信息工程學院,西安710049;2.西安郵電大學通信與信息工程學院,西安710061)

內容中心網絡中一種改進型緩存機制

曲 樺1,王偉萍1,趙季紅1,2

(1.西安交通大學電子與信息工程學院,西安710049;2.西安郵電大學通信與信息工程學院,西安710061)

內容中心網絡(CCN)作為一種主要的未來網絡架構,以命名的內容作為網內的主要元素之一,在網絡研究中受到廣泛關注。針對已有的CCN緩存方案內容副本替換嚴重的問題,提出一種內容熱門度與節點中介中心度約束的緩存機制PopBetw。在基于節點中心度的基礎上,從內容本身的屬性熱門度出發,避免非熱門內容的不必要緩存,降低每個節點的緩存負荷,提高網絡緩存性能。仿真結果表明,通過評估緩存大小和內容熱門度對緩存性能的影響,PopBetw緩存策略可取得比LCE,LCPro和EgoBetw方案更高的緩存命中率和更小的路徑延展度,明顯降低網內緩存替換數量,有效減少網內節點中介中心性較大節點群的緩存替換數,達到整體性能最優化。

內容中心網絡;緩存;內容熱門度;中介中心度;緩存替換;緩存冗余

1 概述

目前因特網大多用于對內容的訪問。盡管當初基于IP的因特網設計是為了達到端到端的通信,但是終端用戶感興趣的僅僅是內容本身而非源端位置。新的信息中心網絡(Information-centric Network, ICN)架構［1］一經提出,便引起了越來越多的研究人員的興趣,例如內容中心網絡(Content-centric Network, CCN)［2-3］。CCN主張重新設計網絡體系結構,從根本上解決高效內容分發面臨的問題。針對用戶關注內容本身而非其所在位置這一特點,內容和位置進行解耦合,并采用內容名對內容進行內容標識和路

由,使用戶可以直接訪問內容本身,不再需要通過位置間接進行訪問。這一特點增強了內容緩存的靈活性,使得內容流量分布更加均勻。

在CCN場景下,所請求內容會依據相應的緩存決策機制［4］被緩存在返回路徑沿途的某些節點中,以便為后續請求服務。緩存的主要作用在于降低用戶訪問時延,特別是減少跨網絡的數據傳輸,使得用戶不必總是從源服務器獲取內容,而是從就近的緩存處獲得服務,同時分布式的緩存起到負載均衡的作用。但是,相對于系統龐大的內容總量,網絡中節點緩存資源是稀缺的。并且內容數目的增長遠大于硬件存儲空間的增長。因此網內緩存決策成為CCN研究中的核心問題之一。

網內緩存決策技術源于Web緩存、CDN和P2P系統,主要包括LCE(Leaving Copies Everywhere)［5］,Rdm (Random Caching Strategy),LCPro(Leaving Copies with Probability)等。LCE機制易于實現但緩存替換頻繁、性能較差,后兩者通過選擇性緩存以減少不必要的內容替換,優于LCE,但隨機性較大,內容緩存點的動態性會產生更多的網絡開銷。文獻［6］基于自我網絡中的中介中心度的概念,提出了ICN場景下一種新穎的緩存方案——EgoBetw,當內容數據包沿原路徑返回時,僅在中介中心度值最大的節點緩存。一個節點若位于大量內容分發路徑之間(在拓撲中起到交通樞紐、關鍵橋梁的作用),則該節點將緩存較多內容,本地緩存將為更多的其他到來的用戶請求提供服務。EgoBetw在一定程度上降低了網內緩存替換率,并且將較熱門的內容逐漸吸引到離用戶較近的緩存節點上,緩存性能明顯得以改善。但是同時導致中介值較大的節點處的緩存替換率較高。網內緩存容量有限,只能滿足用戶的部分請求,即較流行的內容,大部分較不流行的內容請求需到達服務器獲取內容。當這些內容在服務器命中后經過返回路徑上的重要節點(中介中心度較高的節點)緩存后,節點的緩存替換率變高,部分內容副本在緩存內的實際存活時間(節點緩存副本和副本被替換的時間差)變小,導致重要節點的緩存替換率較高、負荷嚴重、效率不高。

針對上述問題,考慮到CCN中固定時間段內不同內容的訪問頻次即熱門度存在差異,本文將內容熱門度與節點中介中心度相結合,提出一種PopBetw緩存機制,在請求內容沿原路徑返回時,由最大節點中介中心度值預判斷出緩存節點后,再由內容本身的熱門度約束進行緩存判決,避免非流行內容的不必要緩存,增大較流行內容的緩存存活時間,實現全網內較佳的緩存性能。

2 PopBetw緩存機制

2.1 設計思想

在多數CCN網絡中緩存判決策略中,每個節點對所有到達內容做相同處理,未考慮不同內容的熱門程度不一這一重要特性。PopBetw緩存機制將內容熱門度與節點中介度相結合,在節點中介度作為緩存約束條件的同時,考慮僅緩存熱門內容,通過緩存更少內容提高網內緩存,減少冗余。

在如圖1所示的拓撲中,t為0時,緩存節點V1至V6的緩存表均為空。當用戶B向服務器S請求內容bi時,S向用戶B返回的內容分發路徑為V1→V3→V5,由于該條路徑上節點V1的中介中心度最大,所以假如內容僅在V1節點處緩存,V3,V5節點不緩存,隨后當A,B,C,D中某幾個用戶請求相同內容時,即可在節點V1命中。但是,網內內容繁多,一旦用戶B請求的內容在緩存未命中,即服務器命中,節點V1均需緩存這些內容,導致節點V1緩存次數增多,有限的緩存容量引起替換次數增多,大量的緩存副本在緩存中的存活時間減小,命中率急劇減少。在上述例子中,當用戶B向服務器S請求內容bi,服務器返回內容時,假如將節點中介中心度和內容熱門度結合作為緩存的約束條件,即預判斷節點V1的中介中心度最大,再次判斷內容bi為熱門內容時,節點V1緩存該內容,反之不緩存。這種方法使得高熱門度的內容副本在節點V1處存在的概率變大,相對冷門內容副本在節點V1處存在的概率變小,從而避免了非流行內容無用的緩存操作,節省了路由器節點的緩存資源,節點V1緩存次數減少,緩存副本在緩存中的存活時間增大,命中率提高。

圖1 緩存決策實例

2.2 內容熱門度

PopBetw緩存策略在保留CCN中CS,FIB和PIT表的基礎上,增加了數據結構:內容熱門度表(Popularity Table,PT),每一個表項由內容bi的內容名和其熱門度值fi組成。如果一個內容越熱門,它的熱門度值越大。

由于內容熱門度值具有隨時間變化的特性,因

此只能根據其過去的流行情況進行估計。PopBetw緩存策略中,將每個節點輸入的請求流分段,每段成為一個統計周期,每個統計周期包括M個請求,在這M個請求周期中記錄統計出各文件的訪問頻次。定義熱門度值是對內容bi在某一統計周期內的請求次數估計值,采取類似文獻［7］的估計方法來計算在第t+1個統計周期內內容bi的熱門度值:

其中,Fbi為上一統計周期內內容bi的訪問頻次;δ為衰減系數。

2.3 節點中介中心度

考慮到實際網絡是動態變化并且全局拓撲信息未必容易獲得,最初的節點中介中心度是一種集中式計算,為實現節點中介中心度的分布式計算,文獻［6］采用自我網絡的中介中心度來近似計算CCN中各節點的中介中心度值。盡管自我網絡的中介中心度僅僅反映節點在自我網絡中的重要性,但是它和真實網絡中該節點的中介中心度存在強的相關性。

設某一自我網絡為圖G,鄰接矩陣為A,1為元素均為1的矩陣,則A2［1-A］i,j表示節點i和節點j之間訪問跳數為2的路徑數,A2［1-A］中所有元素倒數之和即該自我網絡中心節點的中介中心度CB［8］,即也表征了該節點在全網內的重要程度。

2.4 算法描述

PopBetw緩存策略是基于單個興趣包請求的,本節將結合節點收到興趣包、內容包的處理偽代碼對PopBetw緩存策略進行描述。

Pseudo-code I節點收到興趣包偽代碼如下:

若用戶i向服務器j發送內容bi的興趣包,經過的節點依次做出如下處理:

熱門度更新:若計數器count未達到請求周期M,該統計周期內內容bi的訪問頻次Fbi加1;否則,請求數已達到統計周期,根據在本周期內非零的F值對所有內容對應的熱門度值按定義公式更新,即更新內容熱門度表PT。

內容緩存命中判斷:若命中,返回內容,并將服務器命中標志HitInServer清零;否則,服務器命中標志HitInServer仍為1,更新CBmax(判斷本節點中介中心度與興趣包中的CBmax大小,若本節點中介中心度較大,更新CBmax),向下一跳轉發興趣包。

若內容bi從服務器j或緩存命中的節點到用戶i沿原路徑返回,關于緩存條件decision的判斷,經過的節點依次分如下具體情況做出處理:

(1)若內容bi在服務器命中,即標志HitInServer為1,節點中介中心度CB(vn)等于CBmax,表明該節點為網絡中中介中心性較大的節點,需要考慮內容熱門度,即當該內容的熱門度值大于閾值θ,則緩存該內容。

(2)若內容bi在緩存命中,即標志HitInServer為0,并且節點中介中心度CB(vn)等于CBmax,則緩存該內容。

3 性能評價

3.1仿真環境和性能評價指標

為了驗證PopBetw算法是否能達到預期效果,本文從CCN網內多種內容放置方案中選擇3種代表性策略LCE,LCPro,EgoBetw作為PopBetw性能比較對象,結合LRU緩存替換策略,在NS3網絡仿真器中實現了簡單的CCN仿真模型并對緩存性能進行評估。

由于真實的網絡拓撲是不規則的并且遵循冪律度規則,本文采用文獻［9］中的方法建立一個滿足BA模型的無標度網絡,總節點數為100。節點分為3類:服務器,中間節點和訪問節點(連接用戶終端并且在網內為第一跳的所有節點為訪問節點)［10-11］?？偟膬热菸募礛=1 000個,內容熱門度模型為參數α=0.8的Zipf分布。內容請求由代表終端用戶的66個訪問節點發出,總數為330 0000個(50 000× 66個),每個訪問節點的內容請求到達過程服從λ= 25的泊松過程。盡管CCN支持多徑路由,本文僅從單徑路由的前提下對緩存策略進行性能分析。

本文目標是過濾掉非流行內容,找到相對熱門內容的最優緩存位置達到最大緩存性能,為更加準確地反映CCN性能,本文采取以下測量參數作為性能評價指標。

(1)緩存命中率(CHR):

其中,Q表示請求總數;q表示內容請求在內容路由器處命中個數。緩存命中率是一個典型的測量緩存性能的參數,緩存命中率越高,反映緩存響應用戶請求的概率越高,服務器負載越低,緩存系統的效率越高。

再次，培訓應該以日常工作為重點，不追求花哨和專業難度很大的內容。多關注那些在客戶家經常用到的技術，把它們作為培訓重點。例如，打掃衛生和做飯不掌握，凈關注鮑魚燕窩等高檔食材的制作，就是沒有把握住重點。

(2)路徑延展度(PS)

其中,d為仿真中統計的29個訪問節點發出的請求通過CCN獲取內容的平均實際跳數;|P|為訪問節點發出的請求從源服務器端獲取所需的平均跳數。路徑延展反映了負載水平,在某種程度上,它表示數據內容經過的鏈路數的減少程度［12-13］。

(3)不同節點群的平均緩存替換數和緩存命中數。在通常情況下,網內緩存容量有限,遠遠小于內容的大小,這就勢必會產生大量的替換操作,進而消耗大量的計算資源。而對于一個緩存資源有限的路由器來說,這些消耗顯然將會影響路由器的轉發等其他任務的完成。另一方面,緩存替換發生越頻繁,副本在節點的存活時間越短,副本命中的概率也越小,過高的緩存替換將嚴重影響網內的緩存性能。所以,如何減少CCN中的替換數量,也是一個值得注意的問題。

考慮到本文提出的PopBetw緩存機制涉及到節點的中介中心性,結合以上討論將對3類節點群的平均緩存替換數和緩存命中數進行定量分析:所有具有緩存功能的路由器節點群,具有較大節點中介中心度的節點群和其余普通緩存節點群。

3.2 仿真結果

3.2.1 緩存大小對緩存性能的影響

本節首先研究緩存大小對系統性能的影響。圖2顯示出緩存性能隨緩存大小變化而變化的情況,其中,緩存大小與內容總量之比從1%一直增加到6%。從圖2(a)中可以看到,4種機制的緩存命中率會隨著緩存容量大小的增加而增加,相比LCE, LCPro,EgoBetw機制性能明顯提高,但在這個過程中,PopBetw策略都取得了比較穩定的性能提高,且好于LCE,LCPro,EgoBetw。圖2(b)顯示出路徑延展隨緩存容量的增加而減小的情況。緩存命中率提高,內容請求在內容路由器上獲取到副本的概率增大,所需訪問跳數減少,路徑延展也相應減少。由于PopBetw采用內容熱門度和節點中介中心性約束緩存條件,避免了緩存冗余,使得緩存節點盡量緩存熱門內容。PopBetw的路徑延展自始至終都比LCE, LCPro和EgoBetw要低。

圖2 緩存大小對緩存性能的影響

下面研究不同緩存機制下緩存替換數和緩存命中數之間的關系。圖3是節點緩存大小和內容總量之比取定后,LCE,LCPro,EgoBetw和PopBetw 4種緩存策略下3種不同緩存節點群的平均緩存替換數和命中數的比較。類似文獻［6］,設節點緩存大小和內容總量之比為0.1,節點群1～節點群3分別表示具有緩存功能的所有節點,具有較大節點中介中心度的節點群和其余普通緩存節點群。

如圖3所示,對于節點群1,LCE機制下的平均

緩存替換數最大且平均緩存命中數最小,故綜合性能最差,而PopBetw機制下的平均緩存替換數最小而緩存命中數最高,綜合性能明顯提高;對于節點群2,4種緩存機制下的緩存替換數量差異較大, LCE和LCPro機制在緩存命中數方面優于EgoBetw,而PopBetw策略下的節點群2的替換數遠比另外3種少,并且命中數達最高;對于節點群3,節點中介中心性較小,4種策略下的緩存替換次數均較小,與節點群2不同的是,EgoBetw性能遠勝過LCE和LCPro機制,同時EgoBetw以低替換率達到了最好的命中效果。與節點群3相比,節點群2往往處在網內的樞紐位置,每個節點收到來自下游節點聚合的內容請求數量較多,大量的內容緩存在這些節點的概率增大,圖中顯示節點群2的替換次數遠遠高于節點群3。

圖3顯示了PopBetw緩存方案通過判斷內容的流行度過濾掉相對較冷門的內容,有效地減少了網內節點中介中心性較大的節點群的緩存替換數,改善了節點群2的緩存水平,達到了整體性能最優化的目的。

圖3 不同緩存節點群的緩存命中數和平均緩存替換數

3.2.2 內容熱門度對緩存性能的影響

由于用戶對內容的興趣隨時間會發生變化從而影響內容熱門度,本節進一步研究變化的內容熱門度對緩存性能的影響。

首先考慮內容的熱門度有范圍這一情況,即一些內容在某些節點屬于熱門類,在另外一些節點處為非熱門內容。仿真中所有訪問節點分為3類,分別產生3類不同內容請求(體現用戶對內容的不同程度的喜好),當緩存大小與內容總量之比為1%時統計4種緩存機制的緩存性能并與內容請求為一類的情況下的結果對比,如表1所示。相對于內容請求為一類的情況,4種緩存機制達到的緩存性能稍差,但是與其他3種方案對比,PopBetw緩存方案依然有明顯的性能改善。

表1 內容請求不同分類情況下的緩存性能對比

然后分析當內容熱門度在變化速率不同時4種緩存機制的性能變化,假設緩存大小與內容總量之比為3%。如圖4所示,橫軸表示在一個時間周期里變化的熱門內容數與內容總數的比值。圖4表明隨著變化的內容熱門度,LCE和LCPro30%性能所受影響不大,EgoBetw和PopBetw性能稍微變差。實驗顯示當內容熱門度變化越緩和,EgoBetw性能越易達到最優。

圖4 熱門內容變化率對緩存性能的影響

4 結束語

為了使CCN的全網緩存發揮潛在的優勢,本文將內容本身的屬性——流行度和節點中介中心性相結合,提出并實現了一種新的內容緩存策略

PopBetw。該策略通過節點中介中心性大小判定選擇較優目標緩存位置,通過內容熱門度緩存熱門內容,避免非熱門內容的不必要緩存,有效利用緩存資源,避免了大量緩存冗余。仿真結果表明,考慮到緩存大小和內容熱門度變化的因素,PopBetw在緩存性能(包括緩存命中率、路徑延展度)方面優于EgoBetw,相比LCE,LCPro策略性能提高更顯著;另外相比較LCE,LCPro,EgoBetw 3種策略,PopBetw有效地減少了網內節點中介中心性較大的節點群的緩存替換數,達到了整體性能最優化。下一步將對內容熱門度對算法的影響進行更深入的研究。

［1]Koponen T,Chawla M,Chun B G,et al.A Data-oriented (and Beyond)Network Architecture［J］.ACM SIGCOMM Computer Communication Review,2007,37(4):181-192.

［2]閔二龍,陳 震,許宏峰,等.內容中心網絡CCN研究進展探析［J］.信息網絡安全,2012,(2):6-10.

［3]Jacobson V,Smetters D K,Thornton J D,et al.Networking Named Content［C］//Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies.New York,USA:ACM Press,2009:1-12.

［4]Cho K,Lee M,Park K,et al.WAVE:Popularity-based andCollaborativeIn-networkCachingforContentoriented Networks［C］//Proceedings of 2012 IEEE Conference on Computer Communications Workshops.Washington D.C.,USA:IEEE Press,2012:316-321.

［5]Laoutaris N,Syntila S,Stavrakakis I.Meta Algorithms for Hierarchical Web Caches［C］//Proceedings of IEEE International Conference on Performance,Computing,and Communications.Washington D.C.,USA:IEEE Press, 2004:445-452.

［6]Chai W K,He D,Psaras I,et al.Cache“Less for More”in Information-centric Networks［C］//Proceedings of the 11thInternationalIFIPTC6Conferenceon Networking.Berlin,Germany:Springer,2012:27-40.

［7]Zhang Y,Zhao J,Cao G.Roadcast:A Popularity Aware ContentSharingSchemeinVANETs［J］.ACM SIGMOBILE Mobile Computing and Communications Review,2010,13(4):1-14.

［8]Everett M,Borgatti S P.Ego Network Betweenness［J］.Social Networks,2005,27(1):31-38.

［9]Barabasi A L,AlbertR.EmergenceofScalingin Random Networks［J］.Science,1999,286(5439): 509-512.

［10]Wang J M,Bensaou B.ProgressiveCaching in CCN［C］// Proceedings of 2012 IEEE Global Communications Conference.Washington D.C.,USA:IEEE,2012:2727-2732.

［11]Wang J M,Zhang J,Bensaou B.Intra-AS Cooperative Caching for Content-centric Networks［C］//Proceedings of the 3rd ACM SIGCOMM Workshop on Information-centric Networking.New York,USA:ACM Press,2013:61-66.

［12]Rossi D,Rossini G.CachingPerformance of Content Centric Networks Under Multi-path Routing(and More)［Z］.2011.

［13]Rossi D,Rossini G.On sizing CCNContent Stores by Exploiting Topological Information［C］//Proceedings of INFOCOM Workshops.Washington D.C.,USA:IEEE Press,2012:280-285.

編輯 金胡考

An Improved Caching Mechanism for Content-centric Network

QU Hua1,WANG Weiping1,ZHAO Jihong1,2
(1.School of Electronic and Information Engineering,Xi’an Jiaotong University,Xi’an 710049,China;
2.School of Communication and Information Engineering,Xi’an University of Posts and Telecommunications,Xi’an 710061,China)

Content-centric Network(CCN)based on named data which is one of the vital elements in network,as a main architecture for the future Internet,attracts considerable attention from the research community recent years.A new caching scheme called PopBetw based on content popularity and node’s betweenness is proposed to solve the problem of heavy replacement of content copies brought by existing cache policies in CCN:combining content popularity which is one of content attributes with node’s betweenness avoids caching unpopular contents,reduces caching load in each node and improves in-network caching performance.Simulation experiment demonstrates that the proposed PopBetw caching strategy achieves larger cache hit rate and lower path stretch than that of LCE scheme,LCPro and EgoBetw scheme by evaluating the impact of cache size and content popularity on the caching performance,it also shows that PopBetw apparently lower the number of in-network cache replacement especially in nodes with relatively large value of betweenness to achieve better overall performance.

Content-centric Network(CCN);caching;content popularity;betweenness;cache replacement;cache redundancy

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

英文引用格式:Qu Hua,Wang Weiping,Zhao Jihong.An Improved Caching Mechanism for Content-centric Network［J］.Computer Eng-ineering,2015,41(3):41-46.

1000-3428(2015)03-0041-06

:A

:TP393

10.3969/j.issn.1000-3428.2015.03.008

國家自然科學基金資助項目(61371087);國家科技重大專項基金資助項目“新一代寬帶無線移動通信網”(2013ZX03002010-003);國家“863”計劃基金資助項目(2014AA01A706)。

曲 樺(1961-),男,教授、博士生導師,主研方向:移動互聯網;王偉萍,碩士研究生;趙季紅,教授。

2014-03-06

:2014-05-22E-mail:wwpwalker@163.com