CCN路由的緩存機制研究

湯紅　李濤　宋哲

摘? 要：CCN網絡通過待定請求表（Pending Interest Table， PIT）請求源端數據是一個零散的過程，對于首次訪問的所有數據必然會帶來峰值帶寬問題，基于此場景提出一種內容存儲（Content Store， CS）數據模型，包括頻繁度模型、支持度模型、置信度模型和關聯度模型，通過該模型在網絡空閑狀態下提前在對應路由器設備上來預存儲原始數據的關聯數據，從而實現精準化預緩存網絡數據。仿真實驗結果表明，此機制可以實現節省網絡帶寬，有效降低網絡擁塞的目的。

關鍵詞：預緩存；置信度模型；緩存老化；關聯度模型

中圖分類號：TP393? 文獻標識碼：A? 文章編號：2096-4706（2023）12-0078-04

Research on Caching Mechanism of CCN Routing

TANG Hong1， LI Tao2， SONG Zhe3

（1.ZTE Nanjing R&D Center， Nanjing? 210012， China; 2.Purple Mountain Laboratories， Nanjing? 211111， China;

3.Yancheng Branch of China Mobile Communications Corporation， Yancheng? 224399， China）

Abstract： CCN network requests source data through Pending Interest Table is a fragmented process. All data accessed for the first time will inevitably bring peak bandwidth problems. Based on this scenario， a Content Store data model is proposed， including frequency model， support model， confidence model and correlation model， Through this model， the associated data of the original data is pre-stored on the corresponding router device in advance when the network is idle， so as to achieve accurate pre-cache of network data. The simulation experimental results show that this mechanism can achieve the goal of saving network bandwidth and effectively reducing network congestion.

Keywords： precache; confidence model; cache aging; correlation model

0? 引? 言

在CCN中有三個數據結構[1]，分別是待定請求表（Pending Interest Table， PIT）、內容緩存（Content Store， CS）、路由轉發表（Forwarding Information Base， FIB）。CCN請求報文生成PIT表，然后根據FIB進行數據的路由和請求，對于數據的回復會沿途進行CS存儲，保證下次請求的本地化和快速化。網絡通信模型CCN的一大特色就是緩存CS能力，即根據用戶的請求就近進行路由器存儲內容，等下次請求時，可以快速將數據傳輸給用戶，從而節省網絡帶寬[2，3]。對于本地存儲空間未滿，時間長沒有請求的數據，將根據策略選擇性地進行老化刪除[4]，對于本地存儲空間滿了，將根據請求頻次、熱度等方式進行替換。而對于大多數CS未滿的存儲空間如何有效地利用，目前的研究主要是根據熱度排名[5]，將熱度排名高的數據提前存儲到緩存CS中，這在一定程度上可以提高用戶下次命中的概率，但是熱度的概念其實是針對全網所有用戶的加權值，不能準確預測某個用戶或者某個域的數據需求，特別是用戶移動會導致當前網絡內預緩存失效[6]。文獻[7]對目前CS緩存策略進行了分析和概述，提出了基于用戶偏好的緩存差異化策略研究，即考慮用戶對不同內容類型的喜好，并結合內容流行度作為用戶偏好度指標，實現高質量緩存內容的選擇，但是他只考慮了用戶大的方向偏好，比如音樂、美術等，未考慮偏好之間的關聯關系；文獻[8]提出了一種基于業務類型進行差異化分類的數據分發模式，實現了業務的分類數據分發，但是也帶來了CCN體系顛覆和復雜度變更，不利于工程應用的推廣。

在如上研究的基礎上，提出了數據關聯度的緩存機制，即基于用戶在現在的網絡請求中，某個用戶請求數據之間或者某個域內請求數據之間的關聯關系，針對性進行網絡預緩存，避免峰值帶寬浪費。例如用戶請求A數據后，通過關聯關系計算有90%以上的概率下次會請求C數據，即使C數據的熱度很低或者即使C數據不是用戶的偏好數據，按照該網絡模型也會提前下發命令讓請求端路由器發起對C數據的興趣報文請求，然后存儲在本地，實現數據的預測和提前精準化存儲。

1? 預緩存研究

如圖1所示，整個預緩存機制包括SDN控制器設備、CCN路由器設備兩個部分組成，其中控制器設備包括如下功能：

1）數據收集與挖掘功能，主要是四大模型的計算，即FP-growth（FP）模型[9]、支持度模型、置信度模型、關聯度模型的計算。

2）控制下發模塊，主要完成預緩存PIT下發、緩存老化與更新等功能下發。

3）信息接收模塊，完成信息上報功能接收、緩存老化與替換等功能收集與上報。另外CCN路由器設備主要包括數據的預緩存模塊和信息采集上報兩大模塊。預緩存模塊完成本地CCN路由器的預緩存操作，包括添加和老化刪除操作，信息采集模塊主要完成預緩存關聯數據的采集、老化數據的采集等功能。

基于如上模塊和設備劃分分析可知，預緩存機制主要包括三大功能，分別是信息收集功能、數據收集與挖掘功能、緩存老化與替換功能。其中信息收集功能主要由CCN路由器的信息采集模塊和控制器的信息接收模塊組成，完成CCN數據的收集和上報，由CCN路由器采集數據進入控制器的信息接收模塊；數據收集和挖掘模塊主要由控制器的關聯度模型、置信度模型、支持度模型、FP模型、控制下發模塊、CCN路由的預緩存模塊組成，完成基于上報的信息數據進行數據關聯度的挖掘計算，根據計算結果指導相應的設備完成關聯數據的預緩存；緩存老化和替換功能是數據收集和挖掘功能和信息收集功能的逆向功能，主要由CCN路由器設備元數據刪除觸發上報控制器信息，進而由控制器基于現有的依賴模型完成關聯數據的監控和刪除回收，指導CCN路由器預緩存模塊進行信息的刪除，保證網絡數據信息的一致性。整個預緩存機制通過用戶上送的已有請求的數據進行大數據分析，計算基于各種數據請求的關聯度并建立其模型，該模型作為已有模型，與用戶即時緩存CS數據結合，推算出與緩存CS模型數據相關度高的數據模型，然后在網絡空閑狀態時，在對應路由器設備上發送關聯數據的興趣報文，來預存儲關聯相關數據，從而實現精準化預緩存網絡通信模型CCN數據，避免數據峰值的帶寬占用，有效地降低網絡擁塞，同時對于已經老化刪除的數據同步刪除其關聯數據，并觸發控制器的四大模型的逆向刪除操作。

1.1? 信息收集功能

信息收集模塊位于各個CCN路由器上，傳統CCN路由器在收到數據報文后，首先查找興趣請求表PIT，如果沒有興趣請求表PIT，直接丟棄該數據報文，如果有興趣請求表PIT，按照興趣請求表PIT的入接口轉發數據報文。信息上報模塊在CCN路由器上轉發數據報文后即進行檢查興趣請求表PIT的入接口數量，然后提取內容信息外加興趣請求表PIT的入接口數量來組成數據信息頭上報控制器，內容信息包括內容名稱（URL content資源）、設備信息（設備CPU、內存等資源）、接口信息（目前實際物理接口類型、數量、接口所屬設備信息等）和設備所屬的域信息等。SDN控制器由信息接收模塊完成數據的收發與緩存。

1.2? 數據收集與挖掘功能

如圖2所示的數據收集與挖掘流程，控制器的收發包模塊收到設備上送的數據信息后，需要對信息進行存儲和匯總，首先解析獲取數據信息的子信息，主要包括內容名稱、設備信息、接口信息、域信息和興趣請求表PIT的入接口數量等信息。以數據信息的子信息為基礎開始建立FP-Growth模型[10]，FP-Growth采取分治策略，只需要掃描原始數據2次，便可以將提供頻繁項集的數據庫壓縮到一棵頻繁模式樹（FP-Tree）中，但仍保留項集關聯信息[11]。FP-Tree是一種特殊的前綴樹，由頻繁項頭表和項前綴樹構成，因此FP-Growth算法可以加快整個數據構建和挖掘過程。本設計中即是根據FP-Tree計算出相應的頻繁項的集合，其中，基于接口信息、域信息和全局資源數據這樣的數據信息的子信息為基礎開始建立FP-Growth模型，該模型首先針對每一個子信息構造FP-Tree，然后迭代FP-Tree的構造和投影過程，算出了頻繁項集合。

在頻繁項集合的基礎上，計算各個頻繁項集合的支持度模型：支持度模型由基于頻繁項的集合的數量占比的計算方式而得，即該頻繁項的集合在相應集合集中的數量占比，集合集為已有的算出來的所有集合。例如，以CCN命名url為基礎建立的{url1、url2}集合共使用10次，整個集合有100條記錄，那么{url1、url2}的支持度就是10/100 = 0.1。

在支持度模型的基礎上，選取具有包含關系的集合全集，計算相應包含關系集合的置信度模型，在一個實施例中，假設相應包含關系集合中的集合一與集合二為包含與被包含的關系，使得所述置信度模型的計算公式為：（集合tmp = 集合1減去集合2） = 集合1的支持度/集合2的支持度×置信度影響因子；其中置信度影響因子默認為1，根據不同場景可以更改置信度因子。全部包含關系的集合與被包含關系的集合的置信度值都可以算出來，然后將所有值加權后取平均值；根據場景不同置信度因子算法：a = l / d×cs，其中l表示場景值，默認l，cs是當前要下發CCN路由器設備剩余存儲空間百分比，剩余越小，置信度a越小，d是域信息，域離的越遠，置信度越小。可見不同場景下置信度因子不同，其受緩沖CS剩余存儲空間、域信息等因子影響。公式中集合tmp是一個臨時的集合，是計算的中間值。下文具體說明置信度模型的計算實例：假設集合1 = {url1，url2，url3}，集合2 = {url1，url2}，那么url3為置信度集合tmp，整個集合有100條記錄，其中集合1共使用了10次，集合1的支持度為10/100 = 0.1，集合2共使用12次，集合2的支持度為：12/100 = 0.12，因此tmp的置信度模型為：集合tmp = url3 = 0.1/0.12 = 0.83，即假如使用集合2的情況下，有83%置信概率會用到集合1，也即用到{url1、url2}情況下，有83%概率會用到url3，按照優先級認為83%概率滿足要求，則控制器可以向集合1所在的CCN路由器設備發送一個PIT指令，指示該路由器發送url3的PIT請求，將url3內容信息提前存儲在集合1所在的CCN路由器設備上。

但是不能所有的tmp都下發PIT請求，這樣會導致大量的資源浪費，因此就需要建立關聯度模型，即基于置信度模型集合數值tmp，選取最終下發設備的最優集合作為關聯度模型，然后在網絡通信模型CCN的路由器上基于所有關聯度模型數值發起相應的興趣報文然后根據數據報文進行CS中的預緩存。本設計中設計了三大關聯度模型，即接口信息tmp關聯度模型、域信息關聯度模型和全局數據關聯度模型，同時選取置信度模型tmp的50%作為下發候選，在下發候選中選取置信度超過60%的tmp作為最終關聯度模型tmp進行下發，指導相應的CCN路由器設備進行數據的提前緩存。

1.3? 緩存老化與更新功能

緩存老換及替換模塊主要是由設備端完成CCN設備緩存CS監控，關聯數據的刪除等功能，然后上報控制器端完成元數據的增刪，觸發增刪數據的重計算，然后下發預緩存數據。根據置信度模型因子的公式可知，在不更改既有的網絡通信模型CCN替換及老化策略的前提下，只有在緩存CS的存儲空間有剩余時才會觸發對關聯度最高的數據進行提前的PIT請求和數據緩存，因此緩存老化及替換模塊主要功能有：

1）緩存CS中數據的刪除需要上報控制器，CCN路由器的預緩存模塊監控CS中數據老化刪除、人為刪除等事件，上報控制器收發模塊從而觸發控制器的關聯度模型的刪除與重新計算，并下發新的關聯度數據。例如url1因為老化觸發刪除，CCN設備感知到該事件后上報控制器模塊，主要包括內容名、內容大小等信息，控制器感知后，即對該集合關聯的url3發起刪除；或者對于url1刪除后，需要計算url3的置信度模型，觸發了重新計算；并且下發相應的與刪除數據關聯的預緩存數據，控制器通過全局控制通道，下發控制報文，對某臺CCN路由器進行單點數據刪除。

2）新的緩存CS中數據的添加也需要上報控制器，與1相同，該模塊感知到CS中新數據的添加后上報控制器后，控制器基于新數據計算其內容關聯度模型，選取與新數據的關聯度模型置信度較高的預緩存數據下發控制命令，觸發網絡通信模型CCN的路由器發送興趣報文來預緩存數據，例如某臺CCN設備有新的數據url4的內容緩存到了設備上，控制器感知后，計算針對url4的置信度模型、關聯度模型，然后選取關聯度最高的作為url資源的url5，然后向設備發送控制報文，設備收到控制報文后，發起針對url5的PIT興趣報文，來預緩存url5數據。

2? 仿真實驗

基于如上CCN模型，建立1 000個CCN網絡數據URL資源集合，分別是url1～url1 000，按照集合組合隨機原則建立url集合10 000個，然后對比方案如下：CCN路由器首次分別獲取url1，url2，…，url1 000所需要的時間，選取50個url為一組，計算獲取數據的平均時間；然后采用本文所用方案后獲取url組所對應數據的時間。

如圖3所示即為采用本方案前后的對比圖，由圖中可見采用本方案后在前30個大樣本周期內效率優化明顯，隨著采樣樣本的增加，觸發與樣本相關的url提前預存儲，使得請求數據的效率得到較大提升。后續隨著傳統CCN網絡存儲能力的提現，優化后與優化前效率相當。

3? 結? 論

綜上所述，本文在研究了目前CCN各種緩存技術的基礎上，結合理論實踐，提出了CCN路由的預緩存技術，對預緩存技術涉及的信息收集模塊、收據收集與挖掘模塊、緩存老化與更新模塊進行了詳細的介紹與研究，通過信息上報模塊進行CCN路由器信息的收集與上報，通過數據收集與挖掘模塊進行大數據關聯度計算，并對于關聯度較高的模型結合CS存儲情況提前發起預緩存，通過緩存老化與替換模塊完成關聯數據的回收。實驗仿真結果表明，預緩存技術不但保留了CCN網絡結構的經濟性、便捷性、易擴展性的特點，而且還具有可以有效地節省網絡峰值帶寬的巨大價值。將其應用到現有的CCN網絡系統中，不僅可有效保證數據傳輸的及時性和可靠性，而且還能大幅度提升網絡寬帶利率。

參考文獻：

[1] AHLGREN B，DANNEWITZ C，IMBRENDA C，et al. A survey of information-centric networking [J].IEEE Communications Magazine，2012，50（7）：26-36.

[2] CHOI J，HAN J，CHO E，et al. A Survey on content-oriented networking for efficient content delivery [J].IEEE Communications Magazine，2011，49（3）：121-127.

[3] JACOBSON V，SMETTERS D K，THORNTON J D，et al. Networking named content [J].Communications of the ACM，2012，55（101）：117-124.

[4] 劉外喜，余順爭，胡曉，等.CCN中選擇性緩存機制的研究 [J].計算機學報，2014，37（2）：275-288.

[5] 唐紅，韓健，段潔，等.基于內容流行度的移動CCN緩存策略研究 [J].重慶郵電大學學報：自然科學版，2018，30（1）：119-126.

[6] 霍如，劉江，鄂新華，等.一種融合CCN的移動網絡內容預緩存方法：CN201811233306.6 [P].2019-01-18.

[7] 李朋明.面向用戶的內容中心網絡緩存策略研究 [D].重慶：重慶郵電大學，2019.

[8] 葛國棟，郭云飛，劉彩霞，等.CCN中基于業務類型的多樣化內容分發機制 [J].電子學報，2016，44（5）：1124-1131.

[9] 羅曉霞，陳君.一種FP-growth的改進算法 [J].西安科技大學學報，2009，29（4）：491-494+504.

[10] 于紅，王秀坤，孟軍.用有序FP-tree挖掘最大頻繁項集 [J].控制與決策，2007（5）：520-524.

[11] 顏躍進，李舟軍，陳火旺.基于FP-Tree有效挖掘最大頻繁項集 [J].軟件學報，2005（2）：215-222.

作者簡介：湯紅（1985－），女，漢族，江蘇宿遷人，中級職稱，碩士，研究方向：CCN網絡、設備驅動網絡；李濤（1983－），男，漢族，江蘇連云港人，高級職稱，碩士，主要研究方向：CCN網絡、未來網絡；宋哲（1984—），男，漢族，江蘇鹽城人，中級職稱，碩士，研究方向：CCN網絡。