CCN路由的緩存機制研究

湯紅　李濤　宋哲

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

關(guān)鍵詞：預(yù)緩存；置信度模型；緩存老化；關(guān)聯(lián)度模型

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

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

1? 預(yù)緩存研究

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

1）數(shù)據(jù)收集與挖掘功能，主要是四大模型的計算，即FP-growth（FP）模型[9]、支持度模型、置信度模型、關(guān)聯(lián)度模型的計算。

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

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

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

1.1? 信息收集功能

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

1.2? 數(shù)據(jù)收集與挖掘功能

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

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

在支持度模型的基礎(chǔ)上，選取具有包含關(guān)系的集合全集，計算相應(yīng)包含關(guān)系集合的置信度模型，在一個實施例中，假設(shè)相應(yīng)包含關(guān)系集合中的集合一與集合二為包含與被包含的關(guān)系，使得所述置信度模型的計算公式為：（集合tmp = 集合1減去集合2） = 集合1的支持度/集合2的支持度×置信度影響因子；其中置信度影響因子默認為1，根據(jù)不同場景可以更改置信度因子。全部包含關(guān)系的集合與被包含關(guān)系的集合的置信度值都可以算出來，然后將所有值加權(quán)后取平均值；根據(jù)場景不同置信度因子算法：a = l / d×cs，其中l(wèi)表示場景值，默認l，cs是當(dāng)前要下發(fā)CCN路由器設(shè)備剩余存儲空間百分比，剩余越小，置信度a越小，d是域信息，域離的越遠，置信度越小?？梢姴煌瑘鼍跋轮眯哦纫蜃硬煌?，其受緩沖CS剩余存儲空間、域信息等因子影響。公式中集合tmp是一個臨時的集合，是計算的中間值。下文具體說明置信度模型的計算實例：假設(shè)集合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，按照優(yōu)先級認為83%概率滿足要求，則控制器可以向集合1所在的CCN路由器設(shè)備發(fā)送一個PIT指令，指示該路由器發(fā)送url3的PIT請求，將url3內(nèi)容信息提前存儲在集合1所在的CCN路由器設(shè)備上。

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

1.3? 緩存老化與更新功能

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

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

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

2? 仿真實驗

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

如圖3所示即為采用本方案前后的對比圖，由圖中可見采用本方案后在前30個大樣本周期內(nèi)效率優(yōu)化明顯，隨著采樣樣本的增加，觸發(fā)與樣本相關(guān)的url提前預(yù)存儲，使得請求數(shù)據(jù)的效率得到較大提升。后續(xù)隨著傳統(tǒng)CCN網(wǎng)絡(luò)存儲能力的提現(xiàn)，優(yōu)化后與優(yōu)化前效率相當(dāng)。

3? 結(jié)? 論

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

參考文獻：

[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].計算機學(xué)報，2014，37（2）：275-288.

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

[6] 霍如，劉江，鄂新華，等.一種融合CCN的移動網(wǎng)絡(luò)內(nèi)容預(yù)緩存方法：CN201811233306.6 [P].2019-01-18.

[7] 李朋明.面向用戶的內(nèi)容中心網(wǎng)絡(luò)緩存策略研究 [D].重慶：重慶郵電大學(xué)，2019.

[8] 葛國棟，郭云飛，劉彩霞，等.CCN中基于業(yè)務(wù)類型的多樣化內(nèi)容分發(fā)機制 [J].電子學(xué)報，2016，44（5）：1124-1131.

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

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

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

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