基于節點社團重要度的ICN緩存策略

蔡君，余順爭，劉外喜

(1.廣東技術師范學院 電子與信息學院，廣東 廣州 510665；2.中山大學 電子與信息工程系，廣東 廣州 510006；3.廣州大學 電子信息工程系，廣東 廣州 510006)

1 引言

為了適應互聯網應用由發送者驅動的端對端通信模式向接收者驅動的海量內容獲取模式的轉變，同時增強網絡對安全性、業務質量、移動性、可擴展性等方面的支持，研究者們近年來提出了一類以信息為中心的新型網絡體系架構，統稱為信息中心網絡（ICN,information-centric networking），典型的如：DONA[1]、CCN/NDN[2]、PURSUIT[3]、COMET[4]和 GreenICN 項目[5]。在這類ICN網絡中，為緩解當前網絡流量的快速增長對網絡帶寬造成的嚴峻壓力，每個節點都增加了內置緩存功能。雖然緩存機制也是目前互聯網中用于提高網絡性能的重要手段之一，緩存理論及相關技術也已經在Web、CDN和P2P中得到了較為廣泛的應用，但目前的緩存策略主要針對某一具體應用，并需配置成一個覆蓋網絡。因此，這些緩存策略與中間節點共享數據時，效率較低。然而，ICN中的緩存是網絡架構內在的一部分（每個節點都具有該功能），與應用無關，具有網絡自適應等特性，因而，傳統的面向Web、CDN和P2P緩存算法也就不能直接應用于ICN中。近年來，研究者們對ICN中的緩存優化方法進行了探索，得出了許多研究成果，主要集中在2個方面：一是判斷內容是否被節點緩存的緩存決策策略[6～14]；二是單節點緩存內容的替換策略[15]。

在緩存決策策略方面：ICN原始提案實行的是處處緩存(CEE, cache everything everywhere)策略[6]，即所有的內容對象被要求緩存于去往目的地途中的所有節點。這直接降低了緩存系統所能緩存內容的多樣性，導致了嚴重的緩存浪費，因為請求被任意中間節點響應后而不會再往上游節點轉發，其上游某些節點緩存的內容可能根本沒有機會響應后來的請求而因緩存空間受限被替換。最近，Chai等[7]提出了基于介數（betweenness），即Betw策略的選擇性緩存機制，只將對象放置于 ICN中興趣分組(interest packet)沿途中介數最大的節點，即對象僅緩存于最重要的節點處。與CEE策略相比，這種策略具有較高的緩存命中率，并且減少了節點的替換次數，但由于內容請求的社團性質，依然存在局限性，即大部分的內容緩存在全網介數相對大的部分節點處，導致內容對象在空間分布上不合理，網絡性能亦隨之降低，主要體現在：1) 大部分的網絡流量與介數大的節點相關，從而降低了網絡的負載容量；2) 高介數節點的替換次數大幅增加，增加了節點的計算開銷，因而不能滿足ICN節點線速執行的要求；3) 由于網絡介數是描述節點網絡全局重要度的指標，高介數的節點處并不一定是網絡中大部分用戶最容易訪問的位置。針對以上問題，基于Internet網絡拓撲結構的社團特性[8]——社團內部節點之間連接相對緊密，社團之間的節點之間的連接則相對稀疏，所以把內容分別緩存于其經過的各社團內節點社團重要度最大的節點處。因為在同一社團中，社團重要度大的節點不僅越容易被社團內的節點訪問，而且也越容易被社團外的節點訪問。這樣做不僅能提高網絡的緩存效率，節約網絡的緩存空間，而且能使網絡內容在網絡空間上的分布變得更加均勻和合理。

在緩存替換策略方面：為保證ICN節點運行于高速的網絡環境，目前在ICN的諸多緩存策略中[8,9,17]，采用較多的還是簡單易運行的 LRU(least recently used)或 LFU(least frequently used)。但是，如果在全網中，所有節點都以內容在該節點處被訪問的頻率大小或被訪問的時間先后為標準，采用相同的替換機制，將直接導致內容對象在時間上分布不合理，即在熱門時間里，社團內的每個節點都緩存到相同的對象，這將不利于緩存空間的合理利用。然而，在熱門時間過后，該內容對象在各節點上又幾乎同時消失，若需訪問該內容，又會產生比較大的網絡時延，抑制網絡的整體性能。為此，本文基于Internet網絡拓撲結構的社團特性，在每個社團內，每一個節點進行內容替換時，不僅考慮內容在該節點處被訪問的情況，還考慮到了該節點在社團中的位置，使同一社團中各節點采用混合的替換機制，即通過節點社團重要度確定替換節點緩存隊列中的內容對象位置的概率，如節點社團重要度大的節點，在緩存隊列中靠后位置的內容對象被替換的概率大；而節點重要度度小的節點，在緩存隊列中靠前位置的內容對象被替換的概率大，以達到內容對象在時間上的合理分布。

本文貢獻如下：1) 基于復雜網絡的節點社團重要度，提出了一種確定ICN緩存位置的決策策略，使內容對象在空間上分布更合理；2) 基于復雜網絡的節點社團重要度和內容對象在各節點處的訪問情況，提出了一種ICN節點混合替換策略，使內容對象在時間上分布更合理；3) 在多種實驗條件下對CSNIC策略進行了仿真驗證，結果表明該策略與CEE+LFU、Betw+LRU和Opportunistic相比，能更好地提升包括緩存命中率、跳數減少率、內容差異性及替換數量等在內的網絡緩存性能指標，并且CSNIC的通信開銷和計算開銷都較小。

2 相關工作

緩存作為ICN的一個關鍵組件，最近受到了很多研究者的廣泛關注，而緩存決策策略和緩存替換策略是緩存的2個關鍵點。緩存決策策略用于確定內容對象的緩存位置，在最初的 ICN原始提案中，實行的是CEE (cache everything everywhere)策略，即所有的內容對象被要求緩存于去往目的地途中的所有節點，這種處處緩存的機制已被證明導致了嚴重的緩存浪費[10]。為此，Eum等[11]提出了一種在對象返回沿途節點中隨機選擇節點進行緩存的機制，該機制易于實現，但未考慮對象的訪問頻率，緩存效率不高，緩存性能的穩定性也得不到保證。Psaras等[12]提出了一種基于加權概率的緩存機制，即對象在返回途中的緩存概率與節點和請求者的距離成反比，該方法提高了內容在距離請求者更近的節點進行緩存的概率，但也會增加不同對象在邊緣緩存節點的競爭。最近，Chai等[7]提出了基于介數（betweenness）的選擇性緩存機制，只將對象放置于 Interest沿途中介數最大的節點，即：對象緩存于更重要的節點上從而實現更高的擊中率，并減少替換次數。與此類似，He等[13]應用另一種網絡全局節點重要度的測度方法確定 ICN節點緩存對象。而實際上，這2種以節點全局重要度來確定緩存位置的方法并不能使內容對象在空間上分布變得更加均勻和合理，并導致了許多額外的問題（如引言中所述）。Hu等[14]提出一種Opportunistic緩存策略，該策略基于內容在每個節點的訪問情況和該內容源與節點之間距離確定內容是否被該節點緩存的概率，由于各節點相互獨立，因而緩存空間的利用率不高。劉外喜等[15]基于用戶的潛在需求，并結合帶寬換緩存的思想，利用鏈路的冗余帶寬，將內容分流到相鄰節點緩存，改善緩存效率，但該方法需要一些開銷。在張國強等[9,17]的綜述性論文中，對目前的信息中心網絡的一些緩存策略進行了詳細的總結。而本文方法與以上方法的主要區別在于，本文基于 Internet網絡的社團特性，從節點社團重要度（局部重要度）出發，把內容緩存于社團內和社團外用戶容易訪問的節點處，使內容對象在網絡上的空間分布相對均勻，同時實現緩存資源的充分利用。

緩存替換算法已在傳統的 Web緩存中得到了廣泛的研究，Podlipnig等對其進行較全面的綜述[18]。在目前ICN緩存策略研究中，普遍采用2種簡單易行的LRU或LFU替換策略。本文同樣采用的是LRU策略，但不同的是，本文是以節點社團重要度為依據，在同一社團內，不同重要度的節點實行概率制的LRU策略，使緩存對象在時間上合理分布。

3 CSNIC緩存策略

3.1 節點社團重要度定義

3.2 CSNIC緩存決策機制

圖1 基于節點重要度的決策緩存位置

CSNIC緩存決策機制的原理是：ICN興趣分組在經過每個社團時，都會記錄下其所經過的每一個社團中節點重要度最大的節點，同時在以數據分組的形式返程時將內容對象緩存于這些節點上。下面通過一個簡單實例對 CSNIC緩存決策機制進行分析，如圖1所示。如用戶A需從S處獲取一個內容，首先用戶A通過圖1實線路徑發送興趣分組，并記錄該路徑上所經過的社團以及各自社團內所經歷的節點中節點社團重要度的最大值。當搜索到內容對象緩存(或內容服務器)的位置S后，內容對象沿圖1虛線路徑（興趣包的反向路徑）返回。在返回過程中，匹配各社團節點重要度的值，若與興趣包路徑保存的節點社團最大值一致，則在該節點處緩存該內容對象，否則，徑自通過該節點。如圖1所示，數據分組在返回過程中經過了社團 1、社團 2和社團 3，在所經過的每個社團的節點中，節點社團重要度最大的節點分別為v1、v2和v3。因此，將內容對象在v1、v2和v3處緩存。而這些節點正是各自社團內用戶容易達到的位置。這樣，社團 1、社團2、社團3內的用戶需再次訪問該內容時，直接從緩存該內容的節點處獲取即可，與緩存于其他節點相比，該方法實現了內容在網絡空間上的合理分布，減少了網絡的延時，提高了網絡的傳輸效率。

3.3 CSNIC替換機制

CSNIC替換機制的原理是：以網絡的社團為一個單位，在同一社團內根據各個節點的節點社團重要度和內容對象在該節點處被訪問的時間先后順序，選擇不同的內容對象進行替換，即通過節點社團重要度確定節點緩存隊列中的內容對象被替換的概率，如節點社團重要度大的節點，在緩存隊列中流行度低的內容對象被替換的概率大；而節點重要度度小的節點，在緩存隊列中流行度高的內容對象被替換的概率大，以達到內容對象在時間上的合理分布。簡而言之，并不是所有節點都使用相同的替換機制。

若ICN節點緩存建模為大小為C個對象的隊列，以最近最少使用的時間順序進行排列。假定第i個社團內節點j的節點社團重要度為Iij，在該社團內的平均節點社團重要度為。當有一內容對象在該節點需緩存時，將按照概率pij(k)替換該節點緩存隊列的第k個位置的內容(k∈ [1 ,C])，pij(k)定義如式(2)所示。

其中，α為歸一化因子，滿足式(3)，β為概率調節系數。

3.4 CSNIC運行機制

下面對CSNIC緩存策略在ICN架構中的實現過程進行分析。首先，假定每個節點的社團重要度I值和每個節點內的每個位置的替換概率是通過離線方式提前計算得到（如通過中心網絡管理系統）。當一個用戶向某一內容對象發起請求興趣分組，在興趣分組中記錄下它所經歷的社團以及在每個社團中所經歷的節點中節點社團重要度的最大值。當興趣分組達到內容對象所在的服務器或者中間路由器時，這些值將被嵌入數據分組內。在數據分組沿興趣分組路徑逆向傳輸過程中，每個社團內的路由器匹配自己的I值與數據分組的附加值，如果2個值匹配，則該內容被緩存。如果在同一社團內有多個節點的I值相同，那么這些節點都將緩存該對象。在確定內容對象需緩存后，再根據該節點緩存隊列中各位置的替換概率確定被替換內容對象。從以上分析可知，CSNIC緩存決策策略在執行過程中的開銷比較小，每個節點決定是否緩存是相互獨立的，完全是基于節點所在社團的重要度的值，既不需要與其他節點交互信息，也無需推斷服務器的位置和流量模式。CSNIC替換策略也僅與節點社團重要度和該節點的緩存隊列相關。由于在 CSNIC策略中，離線方式預先計算的I值充分考慮了節點在網絡中的位置和與其鄰居的關系，因而它又是一種協作式或合作式的緩存策略。在每個社團內其轉發請求和內容的偽碼如算法1所示。

算法1 （CSNIC緩存策略）

Content request

1) Initialize (Ii-max=0)； 在興趣分組中記錄第i個社團中的節點社團最大值

2) foreach (jfrom 0 toNi)； 在社團i中經歷Ni個節點

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

4 仿真實驗與分析

4.1 評價指標

ICN引入緩存的主要目的為：1)減輕服務器負載，因為一次緩存命中，意味著服務器減少一次用戶請求；2) 降低用戶對內容請求的延遲，借助緩存，用戶能快速從鄰近緩存位置獲取所請求內容，而不是從服務器端；3)減少網絡流量和網絡堵塞，當緩存命中后，內容請求將經過更少的跳數(hops)到達用戶。在達到這些目的的同時，由于ICN緩存線速執行的條件，對此提出了以下要求：1)在有限的緩存空間內緩存更多的不同種類的內容；2)減少替換次數。

為量化以上ICN緩存的目的和要求，引入緩存命中率(CHR, cache hit ratio)對目的1)進行評估，其定義為：由緩存而不是由服務器端響應用戶請求的概率。定義跳數減少率(HRR, hop reduction ratio)對目的2)和目的3)進行評估，其定義如式(4)所示。

其中，Hr(t)和hr(t)分別表示在[t-1，t]時間段內，用戶從服務器和緩存位置獲取內容fr所需要的跳數。若網絡中沒有緩存，則Hr(t) =hr(t)，此時的HRR恒為1。定義內容差異性(CDR, content diversity ratio)對要求1)進行評估，其被定義為緩存中所有內容的種類數量與網絡中由服務器所產生的內容種類總數量的比值，CDR值越大，則在相同緩存空間內所緩存的內容種類數越多。定義替換數量(NR,number of replacement)對要求2)進行評估，其定義為一個興趣分組在一個節點上引起的替換次數，由于在ICN中緩存要求線速執行，因此頻繁地替換緩存內容并不合適。

4.2 ICN緩存模型

ICN緩存模型構建方式如下。首先，假定網絡具有發布/訂閱的網絡架構，即網絡中的內容請求和分發機制已經存在。用圖G=(V,E)表示具有N個節點、M條邊的無向無權網絡，其中，V=v1,v2,…,vN表示網絡中節點的集合，E=e1,e2,…,eM表示網絡中邊的集合。F=f1,f2,…,fR表示網絡中的內容的集合，S=s1,s2,…,sp表示網絡中內容服務器的集合，并且每個內容服務器與一個節點v∈V相對應。內容隨機地分布在服務器S中，并假定每個內容對象僅保存于一個服務器中。

4.3 實驗結果

實驗網絡的拓撲由100個節點和386條鏈路組成[22]，其中描述網絡的社團特性的模塊度Q=0.794，Q＞0.3表明網絡具有明顯的社團特性[23]。本文采用多個性能參數將 CSNIC策略與CEE+LFU策略、Betw+LRU策略、Opportunistic策略進行比較，其中包含系統的緩存命中率、跳數減少率、內容差異性和替換數量變化。下面重點討論節點緩存空間大小、內容數量、替換概率調節系數(β)和網絡社團結構對 CSNIC策略的緩存性能的影響。

1) 節點緩存空間大小的影響

在該實驗過程中，用戶數量設置為50 000，Zipf參數(α)的參數設置為 1.2，替換概率調節系數(β)設置為0.7，節點緩存空間大小從10 MB至320 MB變化。

圖2為4種緩存策略的緩存命中率隨網絡節點緩存空間的變化情況。從圖可以看出，4種緩存策略的緩存命中率都隨網絡中節點緩存空間的增大而增大。這是由于節點緩存空間增大，緩存的內容增多，用戶在緩存內容的節點處獲取所需內容的概率增大，從而導致緩存命中率增大。但在這個過程中，CSNIC策略的性能一直優于其他3種策略。導致這一結果的主要原因是：CEE+LFU策略實行把所有的內容對象緩存于去往目的地途中所有節點，這樣直接浪費了節點的緩存空間，網絡中緩存的內容減少導致網絡的緩存命中率降低；Betw+LRU策略把內容緩存到全網介數最大的節點，間接地閑置了其他節點的緩存空間；Opportunistic策略提高了流行度高的內容在靠近用戶節點處的緩存概率，與上 2種策略相比，提高了網絡緩存的命中率。而CSNIC策略不僅在空間上把內容合理地分布在網絡中不同的社團內，而且在時間上合理地利用了社團內節點社團重要度較低的節點的緩存空間，因而更能提高系統的緩存命中率。

圖2 緩存命中率對緩存空間的影響

圖3顯示了跳數減少率對網絡節點緩存空間大小的變化情況，從圖可以看出，4種緩存策略的跳數減少率都隨網絡中節點緩存空間大小的增大而減少，這是由于節點緩存空間增大，緩存的內容增多，用戶獲取所需內容的跳數減少，從而跳數減少率降低。但在這個過程中，CSNIC策略的性能一直優于其他 3種策略。導致這一結果的主要原因是CSNIC策略把內容緩存到社團內節點和社團外節點相對容易訪問的位置，從而降低了跳數減少率。

圖3 跳數減少率對緩存空間的影響

圖4為網絡內容差異率對網絡節點緩存空間的變化情況，從圖可以看出，4種緩存策略的內容差異率都隨網絡中節點緩存空間的增大而增大，這是由于節點緩存空間增大，緩存的內容增多，節點之間內容差異性增大。但在這個過程中，CSNIC策略的性能一直優于其他3種策略。雖然Betw+LRU策略在內容的傳輸過程中僅緩存介數最大的節點，在一定的緩存空間條件下，Betw+LRU策略在網絡中緩存內容的差異性通常被認為最好，但深入的分析發現，由于緩存空間有限，其結果是介數大節點的替換次數增加，并沒有大幅增加網絡內容的差異性。由于Opportunistic策略在內容返回過程不僅考慮了內容在節點處的流行度，而且通過概率機制考慮了內容的差異性，因而，Opportunistic策略性能優于Betw+LRU策略。而對CSNIC策略，在同一社團中，將不同流行度的內容緩存到網絡不同的節點處，使在同一社團內各節點緩存內容具有明顯的差異性，是內容在網絡中的時間分布趨于合理，相當于均勻分配了內容在網絡中每個社團內的分布，直接地提高了緩存內容差異率。同時，在現實網絡中，不同社團具有不同的喜好，這樣相當于在不同社團之間內容對象再進行了一次合理分布。因而，在這4種緩存決策策略中，CSNIC策略的內容差異率是最佳的。

圖4 內容差異率對緩存空間的影響

表 1為替換數量隨緩存大小變化的結果：Betw+LRU在 4種機制中的替換數量最小；CEE+LRU中每一個興趣分組都會引起一次替換，所以為一常數；而 CSNIC策略的替換數量略微高于Betw+LRU，Opportunistic策略與CSNIC策略非常接近。但Betw+LRU策略的替換主要集中于高介數的節點處，在單一節點頻繁地替換并不滿足ICN架構中緩存要求線速執行的條件。

表1 替換數量VS緩存大小

2) 內容數量的影響

在該實驗過程中，節點緩存空間的大小設置為20 MB，用戶數量設置為50 000，Zipf參數(α)的參數設置為 1.2，替換概率調節系數(β)設置為0.7，其中內容數量在200至6 400范圍內變化。

圖5～圖7分別為緩存命中率、跳數減少率和內容差異率隨網絡中的內容數量變化的關系，從圖5～圖7可以看出，4種緩存策略的緩存命中率、跳數減少率和內容差異率的性能都隨網絡中緩存的內容的數量增大而減弱，這是由于隨著網絡中內容數量增大，需要緩存內容增多，用戶在緩存內容節點處獲取所需內容的概率降低，從而導致緩存性能減弱。但在這個減弱的過程中，CSNIC策略的性能一直優于其他3種策略。導致這一結果的主要原因與上述節點緩存空間大小情況的討論類似，網絡中內容數量的增加相當于網絡中節點緩存空間的減少。

圖5 緩存命中率對內容數量的影響

圖6 跳數減少率對內容數量的影響

圖7 網絡內容差異率對內容數量的影響

4種緩存策略的替換數量隨內容數量變化的結果與緩存空間變化的情況類似：Betw+LRU在4種機制中的替換數量最小；CEE+LRU中每一個興趣分組都會引起一次替換，為一常數；而 CSNIC和Opportunistic的替換數量相當，略高于Betw+LRU。

3)Zipf(α)參數的影響

在該實驗過程中，用戶數量設置為50 000，節點緩存空間的大小設置為20 MB，替換概率調節系數(β)設置為 0.7，Zipf參數(α)的參數設置為 0.2至1變化。

現有實證研究顯示網絡用戶對內容的偏好服從Zipf分布[24]，Zipf參數α越大，表示用戶的偏好越集中，并且用戶對不同網絡應用的α值也有差異。因此，下面通過變化α值測試CSNIC策略對不同網絡應用的表現。圖8～圖10分別為緩存命中率、跳數減少率和內容差異率隨Zipf參數α變化的關系。從圖8可知，4種策略的緩存命中率都隨參數α增大而增大，但在這個過程中，CSNIC策略的性能一直優于其他3種策略，導致這一結果的主要原因是4種策略都利用了時間的局域性，但除此此外，CSNIC策略還充分利用空間的局域性。圖9和圖10顯示，跳數減少率和內容差異率隨著參數α的增大都有減少，但CSNIC策略一直保持較明顯的性能優勢。

圖8 緩存命中率對Zipf(α)的影響

圖9 跳數減少率對Zipf(α)的影響

圖10 網絡內容差異率對Zipf(α)的影響

4) 網絡社團結構的影響

現有實證研究顯示 Internet網絡具有明顯的社團特性[16]，網絡特性的量化指標用模塊度Q值表示，Q值越高，表示網絡的社團特性越明顯，現實網絡的社團結構在0.3～0.7之間。因CSNIC策略的實現與節點社團重要度直接相關，而節點社團重要度與網絡的社團結構相聯系。為研究網絡的社團特性對緩存策略的影響，本文采用了由Yan等提出的SFC模型[25]，該模型生成的網絡不僅全網節點的度和社團內節點的度都具有無標度特征，而且網絡社團特性可調，與現實中 Internet網絡比較接近。選擇合適參數生成節點數為300、模塊度Q從0.3變化到0.7的網絡。圖11～圖13為實驗結果，其中橫軸為網絡模塊度的大小。從圖可知，隨著網絡模塊度的增加，CSNIC策略的緩存性能(緩存命中率、跳數減少率和內容的差異率)的波動不是很大，而CEE+LRU、Betw+LRU和Opportunistic策略隨著網絡社團模塊度的增加，緩存性能有所下降，這是由于 CSNIC策略把內容緩存到社團內節點容易獲取的位置，而其他3種策略隨著網絡社團結構的增強，若用戶想獲取的內容不在所屬社團內的節點處緩存，將加大獲取的難度。

圖11 緩存命中率對網絡模塊度（Q）的影響

圖12 跳數減少率對網絡模塊度（Q）的影響

圖13 網絡內容差異率對網絡模塊度（Q）的影響

5) 替換調節系數(β)的影響

在該實驗過程中，用戶數量設置為50 000，Zipf參數(α)的參數設置為1.2，節點緩存空間的大小設置為10 MB至320 MB變化，替換概率調節系數(β)設置為0.3至1.5變化。

圖 14為內容差異率隨替換概率調節系數(β)和節點緩存空間的大小變化的曲面圖，從圖可以看出，內容差異率的性能隨著β系數的變化發生變化。在β=0.7時，內容差異率達到最大值，即在同一社團內，根據其在社團中的重要度，通過調節不同節點內內容的替換概率，以達到每個節點的緩存空間的充分利用。緩存命中率和跳數減少率的變化趨勢與內容差異率的變化趨勢類似，限于篇幅，在文中沒有給出它們的變化曲線。進一步實驗發現，為使內容對象在時間的分布上獲取一個好的結果，替換概率調節系數(β)的取值還與網絡節點的緩存空間大小分布有關。但由于網絡節點緩存空間的大小在網絡設計規劃時已經固定，替換概率調節系數(β)對于具體的網絡是固定的，因而在網絡中易于布局。

圖14 替換概率調節系數(β)和緩存空間對內容差異率的影響

6) 策略的開銷分析

下面從計算開銷和通信開銷 2個方面分析CSNIC策略。

計算開銷：CSNIC策略緩存決策策略和替換策略中的節點社團重要度的如式(3)所示，只需求出表示網絡節點連接關系的鄰接矩陣的所有特征值和特征向量。而現實中的大部分網絡為稀疏網絡，利用Lanczos算法和QL算法，求稀疏對稱矩陣的所有特征值和特征向量的時間復雜度為O(nm)[26]，其中n和m分別表示網絡的節點數和邊數，其計算復雜度較低，并且每個節點的社團重要度都是通過離線方式計算存儲的。在替換過程中概率的計算也是僅為O(k)，其中k為每個節點的緩存空間大小，所以CSNIC策略滿足ICN對每個節點緩存處理線速的要求。

通信開銷：在興趣分組和 Data分組僅需保存所經過的社團內節點社團重要度最大節點的值， 而每次通信，找到用戶所需內容所經過的社團數量一般在2個左右，顯然，CSNIC策略的通信開銷很低。

從上分析可知，CSNIC策略易于實現，以較小的開銷獲得很好的性能改善。

5 結束語

如何高效地利用ICN中每個節點的緩存功能，提高網絡傳輸性能，成為了ICN架構應用于實際環境的關鍵問題之一。為此，本文提出了一種應用Internet網絡拓撲結構的社團特性，基于每個節點在其所屬社團的重要度確定內容緩存位置和緩存替換的緩存策略。通過在不同網絡環境進行仿真實驗，實驗結果驗證了本文方法的有效性。

由于目前實驗條件的限制，本文僅考慮了網絡的靜態拓撲信息的社團特性，為更合理地確定內容的緩存位置，Internet網絡的社團特性也應根據網絡的實際運行狀態動態變化。因此，下一步工作將基于軟件定義網絡(SDN)的設計理念，感知網絡的實時狀態信息，從 ICN 架構的實際流量出發，構建加權有向復雜網絡。在 SDN的控制層，根據節點的社團特性來確定內容的緩存位置。然后通過SDN的數據層執行這一決策，進一步提高ICN架構的緩存性能。

[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] 黃韜, 劉江, 霍如等.未來網絡體系架構研究綜述[J].通信學報,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] 張國強, 李楊, 林濤等.信息中心網絡中的內置緩存技術研究[J].軟件學報, 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].計算機學報, 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] 蔡君, 余順爭.一種有效提高無標度網絡負載容量的管理策略[J].物理學報, 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.