董利利 ，王 勇 ，董永強(qiáng) ,2，楊 鵬 ,2

（1.東南大學(xué)計算機(jī)科學(xué)與工程學(xué)院 南京 211189；2.東南大學(xué)計算機(jī)網(wǎng)絡(luò)和信息集成教育部重點實驗室 南京211189）

1 引言

以內(nèi)容為中心的命名數(shù)據(jù)網(wǎng)絡(luò)[1]（named data networking，NDN）的重要特征之一，是利用網(wǎng)絡(luò)內(nèi)置緩存機(jī)制提高用戶獲取內(nèi)容資源的效率和網(wǎng)絡(luò)資源的利用率。在NDN中，路由節(jié)點依靠報文中攜帶的內(nèi)容名字轉(zhuǎn)發(fā)數(shù)據(jù)內(nèi)容，同時每個路由節(jié)點都具有緩存本地轉(zhuǎn)發(fā)過的數(shù)據(jù)內(nèi)容的能力，以便后續(xù)相同請求到達(dá)時可利用緩存副本直接響應(yīng)該請求，從而提高響應(yīng)效率。研究設(shè)計高效的緩存管理機(jī)制對提升NDN的整體性能具有重要意義。

傳統(tǒng)的緩存管理策略有LRU（least recently used）、LFU（least frequently used）、FIFO（first in first out）以及 SIZE 替換算法等。其中，LRU[2]將數(shù)據(jù)內(nèi)容最近被訪問的時間點作為判斷依據(jù)，在必要時將緩存內(nèi)容中最近最少訪問的數(shù)據(jù)內(nèi)容替換出緩存；LFU[3]統(tǒng)計緩存內(nèi)容在過去一段時間內(nèi)被訪問的次數(shù)（即訪問頻率），將訪問頻率最低的內(nèi)容替換出去；FIFO[4]緩存管理策略，基于簡單的排隊規(guī)則，根據(jù)緩存內(nèi)容存儲的先后順序依次進(jìn)行緩存替換；SIZE[5]替換算法則將數(shù)據(jù)內(nèi)容的大小作為緩存替換的主要因素，優(yōu)先替換緩存中占用空間較大的數(shù)據(jù)內(nèi)容。參考文獻(xiàn)[6]提出了一種基于內(nèi)容熱度的NDN緩存替換策略。在保留NDN中CS、PIT以及 FIB結(jié)構(gòu)的基礎(chǔ)上新增了一張 CPT（content popularity table），用來保存緩存內(nèi)容的命中率、歷史及當(dāng)前熱度，熱度值按計時周期進(jìn)行加權(quán)平均，在緩存替換過程中選擇熱度最小的內(nèi)容進(jìn)行替換。

以上緩存替換策略都是基于單個節(jié)點的，并沒有將網(wǎng)絡(luò)當(dāng)作一個整體來考慮?？紤]到NDN中每個路由節(jié)點都具有緩存內(nèi)容的能力，為提高網(wǎng)絡(luò)整體的緩存價值，相關(guān)研究提出了節(jié)點間協(xié)作的緩存管理策略。根據(jù)關(guān)注重點、協(xié)作決策點的不同，可將節(jié)點間協(xié)作的緩存管理分為全局協(xié)作、路徑協(xié)作以及鄰域協(xié)作[7]。

全局協(xié)作根據(jù)當(dāng)前的網(wǎng)絡(luò)拓?fù)洹⒐?jié)點間的網(wǎng)絡(luò)距離以及各個節(jié)點的訪問速率等信息，提前規(guī)劃好數(shù)據(jù)內(nèi)容在網(wǎng)絡(luò)中的最佳存儲位置，使得用戶訪問內(nèi)容的“代價”最低。參考文獻(xiàn)[8]提出了一種基于內(nèi)容流行度以及網(wǎng)絡(luò)拓?fù)涞膮f(xié)作緩存策略，主要思路是根據(jù)數(shù)據(jù)報文距離內(nèi)容提供端的跳數(shù)和數(shù)據(jù)的流行度，確定報文的生存期以及報文存儲的位置，但并沒有給出流行度的計算方法以及網(wǎng)絡(luò)拓?fù)鋱D的更新方式。

路徑協(xié)作指數(shù)據(jù)內(nèi)容的命中節(jié)點到請求節(jié)點之間的路由節(jié)點，在轉(zhuǎn)發(fā)過程中判斷是否緩存該內(nèi)容的協(xié)作決策方法。參考文獻(xiàn)[9]提出在轉(zhuǎn)發(fā)興趣報文的過程中記錄沿途經(jīng)過的節(jié)點信息（如節(jié)點狀態(tài)、請求頻率等），命中節(jié)點根據(jù)請求報文攜帶的路徑上所有節(jié)點的狀態(tài)信息，利用動態(tài)線性規(guī)劃，計算出最優(yōu)的內(nèi)容緩存位置。這種方法具有中心處理方式的弊端，在決策節(jié)點的計算開銷也不小。參考文獻(xiàn)[10]考慮避免復(fù)雜的決策算法，在轉(zhuǎn)發(fā)內(nèi)容報文的過程中隨機(jī)地選擇一個節(jié)點作為存儲內(nèi)容的路由節(jié)點。這種緩存策略易于實現(xiàn)，但未考慮內(nèi)容的訪問熱度以及節(jié)點的緩存狀況。

鄰域協(xié)作是指在一個節(jié)點的鄰域范圍（經(jīng)過有限跳數(shù)可達(dá)的節(jié)點，也稱鄰居節(jié)點）內(nèi)，顯式地對緩存放置的位置進(jìn)行決策，通過協(xié)調(diào)鄰域范圍內(nèi)節(jié)點之間的緩存內(nèi)容，降低網(wǎng)絡(luò)中數(shù)據(jù)的冗余度，提高整體的緩存利用率。參考文獻(xiàn)[11]提出利用布魯曼濾波器（bloom filter）技術(shù)，根據(jù)節(jié)點設(shè)定的緩存內(nèi)容時間把內(nèi)容目錄廣播給一定區(qū)域內(nèi)的其他節(jié)點，設(shè)定的保存時間越長，廣播的距離越遠(yuǎn)。該方法沒有給出具體的緩存內(nèi)容時間計算方法，也未通過實驗驗證其有效性。參考文獻(xiàn)[12]提出的鄰域協(xié)作緩存管理方法主要針對如何降低節(jié)點之間的冗余度問題，在后臺運行一個降低鄰域范圍內(nèi)緩存冗余的程序，定期清理鄰域范圍內(nèi)的冗余緩存對象。這種方法可以有效地降低數(shù)據(jù)的冗余度，但未考慮數(shù)據(jù)內(nèi)容本身的信息，會導(dǎo)致某些熱門資源在網(wǎng)絡(luò)存儲的副本數(shù)量有限，不能很好地滿足用戶請求。

為充分利用NDN中路由節(jié)點的緩存信息，本文針對現(xiàn)有緩存替換策略的不足，基于鄰域協(xié)作的思想，提出了一種基于蟻群替換算法的鄰居協(xié)作緩存管理（ACNCM）策略。在單節(jié)點的緩存替換中，將自定義的內(nèi)容緩存價值引入具有較高執(zhí)行效率和優(yōu)化求解結(jié)果的蟻群替換算法（ACCR）中，提高單個節(jié)點的緩存價值；在協(xié)作緩存替換中引入?yún)f(xié)作替換參數(shù)，協(xié)調(diào)不同節(jié)點之間的內(nèi)容緩存價值，從而提高NDN整體緩存價值。

2 基于鄰居協(xié)作的NDN緩存管理框架

2.1 鄰居協(xié)作模型與協(xié)議交互機(jī)制

如圖1所示，基于鄰居協(xié)作的NDN緩存管理框架在現(xiàn)有CS、PIT以及FIB結(jié)構(gòu)的基礎(chǔ)上，新添加了鄰居信息結(jié)構(gòu)NIB。NIB的主要功能有：在節(jié)點計算緩存內(nèi)容價值時提供鄰居副本信息，支持緩存替換算法的運行；在節(jié)點執(zhí)行協(xié)作緩存決策過程中提供鄰居節(jié)點信息，作為判斷是否執(zhí)行協(xié)作緩存的一個主要因素；在處理用戶發(fā)起的興趣報文過程中，可以優(yōu)先獲取鄰居節(jié)點中存儲的內(nèi)容，提高響應(yīng)效率。

鄰居信息結(jié)構(gòu)NIB通過鄰居緩存信息表 （NCT）（見表1）和鄰居緩存狀態(tài)表（NST）（見表2）記錄給定鄰居深度范圍內(nèi)的所有鄰居節(jié)點的緩存狀態(tài)信息，其中鄰居深度表

圖1 基于鄰居協(xié)作的NDN緩存管理框架

示該條信息的發(fā)送者距接收者的路由跳數(shù)，初始值為1，在轉(zhuǎn)發(fā)過程中逐跳增加。

表1 NCT

表2 NST

采用ACNCM策略的節(jié)點在接收到興趣報文時，先檢查CS和PIT中是否有相應(yīng)記錄，若有則按NDN標(biāo)準(zhǔn)流程處理；如果都沒有，則檢查NIB以判斷鄰居節(jié)點中是否已有相應(yīng)的數(shù)據(jù)內(nèi)容。如果NIB中有相應(yīng)記錄，則將興趣報文轉(zhuǎn)發(fā)給該鄰居節(jié)點，否則檢查FIB，將興趣報文通過相應(yīng)端口轉(zhuǎn)發(fā)給上游節(jié)點。

為便于路由節(jié)點間進(jìn)行協(xié)同緩存，充分利用新增鄰居緩存結(jié)構(gòu)中的信息，設(shè)計了兩種新的報文：NIB更新報文和協(xié)作緩存報文。

（1）NIB 更新報文

NIB更新報文用于路由節(jié)點向其他節(jié)點通告本地緩存信息，其結(jié)構(gòu)如圖2所示。其中，節(jié)點標(biāo)識是節(jié)點的唯一性身份標(biāo)識；最大轉(zhuǎn)發(fā)跳數(shù)用于限定NIB報文在網(wǎng)絡(luò)中的傳輸范圍；本地緩存是否已滿與平均內(nèi)容緩存價值是判斷是否執(zhí)行協(xié)作緩存的兩個重要指標(biāo)，供報文接收端在執(zhí)行協(xié)作緩存策略時采用；緩存內(nèi)容名字列表記錄本地緩存內(nèi)容的名字，用于告知鄰居節(jié)點本地緩存空間存儲了哪些內(nèi)容，供鄰居節(jié)點執(zhí)行緩存替換算法以及轉(zhuǎn)發(fā)興趣報文時參考。每個路由節(jié)點會根據(jù)給定的協(xié)作鄰居深度以及更新間隔時間定期向外發(fā)出NIB更新報文。當(dāng)路由節(jié)點接收到NIB更新報文時，根據(jù)報文中攜帶的信息更新NST中對應(yīng)的表項；并判斷最大轉(zhuǎn)發(fā)跳數(shù)是否大于1，若是則將最大轉(zhuǎn)發(fā)跳數(shù)減1，并通過當(dāng)前節(jié)點的所有端口轉(zhuǎn)發(fā)，否則丟棄該報文。

圖2 NIB更新報文結(jié)構(gòu)

（2）協(xié)作緩存報文

路由節(jié)點選出需要替換出緩存的數(shù)據(jù)內(nèi)容后，由協(xié)作緩存管理策略決定是否對該內(nèi)容執(zhí)行協(xié)作緩存，如果需要則向選中的鄰居協(xié)作節(jié)點發(fā)送包含該內(nèi)容的報文，稱為協(xié)作緩存報文，其格式如圖3所示，其中協(xié)作節(jié)點標(biāo)識即協(xié)作緩存節(jié)點的身份標(biāo)識，協(xié)作鄰居深度代表節(jié)點選中的協(xié)作鄰居節(jié)點距離本節(jié)點的跳數(shù)，內(nèi)容數(shù)據(jù)即需要協(xié)作存儲的內(nèi)容本身。鄰居節(jié)點收到協(xié)作緩存報文后，會首先根據(jù)內(nèi)容緩存價值判斷是否應(yīng)該存儲收到的內(nèi)容，然后根據(jù)判斷結(jié)果處理報文。如果該處理引發(fā)了協(xié)作鄰居節(jié)點執(zhí)行緩存替換，則不再對替換出的數(shù)據(jù)內(nèi)容繼續(xù)執(zhí)行協(xié)作緩存處理，而是直接刪除新替換出的內(nèi)容，以降低不必要的網(wǎng)絡(luò)開銷。

2.2 ACNCM緩存管理的基本思想

ACNCM緩存管理主要包括兩部分，具體介紹如下。

（1）單節(jié)點的緩存替換機(jī)制

將緩存替換問題建模為0/1背包問題（knapsack problem，KP），在單個節(jié)點內(nèi)需要進(jìn)行緩存替換時，利用基于蟻群優(yōu)化算法的緩存替換機(jī)制選擇需要替換出去的數(shù)據(jù)內(nèi)容。在蟻群算法計算選擇緩存內(nèi)容的概率時綜合考慮以下因素：信息素濃度、數(shù)據(jù)到達(dá)的時間、訪問次數(shù)和數(shù)據(jù)的大小以及鄰居節(jié)點中是否存儲有相同內(nèi)容的副本。

（2）鄰域協(xié)作緩存管理機(jī)制

在協(xié)作緩存管理中引入?yún)f(xié)作替換參數(shù)，對于單個節(jié)點中將要被替換出去的數(shù)據(jù)內(nèi)容，計算出各個鄰居節(jié)點的協(xié)作替換參數(shù)，然后選擇具有最小協(xié)作替換參數(shù)的鄰居節(jié)點作為該數(shù)據(jù)內(nèi)容的存儲節(jié)點。在計算協(xié)作替換參數(shù)時，主要考慮鄰居節(jié)點的平均緩存價值以及訪問時延。

3 ACNCM緩存替換與鄰居協(xié)作算法

3.1 單節(jié)點緩存替換問題建模

給定一個緩存空間有限的網(wǎng)絡(luò)節(jié)點，當(dāng)剩余空間不足以存儲新到來的數(shù)據(jù)時，需要從現(xiàn)有緩存中替換出一些價值相對低的數(shù)據(jù)內(nèi)容，為新到達(dá)的數(shù)據(jù)騰出空間。該問題本質(zhì)上等同于傳統(tǒng)的0/1背包問題，即在給定的約束條件下，求最大可能組合的優(yōu)化問題。這是一類典型的NP完全問題，其一般描述為：給定一個能承受最大重量為W的背包和n個物品，物品i的重量用wi來表示，vi表示物品i的價值，如何選擇總價值盡可能高的物品放入背包中，并且物品的總重量不能超過背包的容量。

基于此認(rèn)識，緩存替換問題可描述為：節(jié)點緩存空間最大容量為S，當(dāng)前存儲了n個數(shù)據(jù)內(nèi)容，數(shù)據(jù)內(nèi)容i的大小記為si，對應(yīng)的內(nèi)容緩存價值記為vi，待存入緩存的新到達(dá)數(shù)據(jù)內(nèi)容的大小為sx。需要找出一種存儲方案，使得在數(shù)據(jù)內(nèi)容總大小不超過最大可用緩存空間S的情況下，緩存空間中保留的數(shù)據(jù)內(nèi)容的緩存價值總和最大。

其形式化描述：設(shè) S>0，00，1≤i≤n，要求解出一個 n 元 0-1 向量{x1,x2,x3,…,xn}，xi∈{0,1}，1≤i≤n，滿足條件∑sixi≤S，且使得∑xivi最大化。其中xi=1表示對應(yīng)的數(shù)據(jù)si保存在緩存中，xi=0則表示對應(yīng)的數(shù)據(jù)被替換出緩存。

3.2 數(shù)據(jù)內(nèi)容的緩存價值計算

數(shù)據(jù)內(nèi)容的緩存價值與背包問題中的物品價值相對應(yīng)，是對節(jié)點緩存空間中存儲的數(shù)據(jù)內(nèi)容的價值估量。由于網(wǎng)絡(luò)中數(shù)據(jù)內(nèi)容請求的隨機(jī)性，無法直接確定數(shù)據(jù)內(nèi)容的緩存價值，只能根據(jù)數(shù)據(jù)內(nèi)容在緩存中以往的效用來判斷內(nèi)容的價值。本文定義內(nèi)容i的緩存價值如式（1）所示。

其中，si表示內(nèi)容i的體積，也即占用的緩存空間，數(shù)據(jù)內(nèi)容的體積越大，其緩存價值越小。t表示當(dāng)前時間，ti表示內(nèi)容被存儲的時間，hitcouti表示內(nèi)容在時間段(t-ti)內(nèi)被訪問的次數(shù)，hitcouti/(t-ti)表示內(nèi)容在該時間段內(nèi)的訪問頻率，它反映數(shù)據(jù)內(nèi)容在過去一段時間的熱度，故緩存價值與其成正比。neibordeepi表示本節(jié)點到存儲內(nèi)容i副本的鄰居節(jié)點的跳數(shù)，如果沒有鄰居節(jié)點存儲該內(nèi)容，則其值為網(wǎng)絡(luò)設(shè)定的最大協(xié)作鄰居深度值加1。鄰居深度越大，從鄰居節(jié)點獲取數(shù)據(jù)內(nèi)容的開銷越大，在本節(jié)點就更有存儲的價值，所以鄰居深度與緩存價值成正比。

3.3 基于蟻群算法的單節(jié)點緩存替換機(jī)制

求解0/1背包問題有很多種方法，包括圖論法、動態(tài)規(guī)劃法、分支限界法等精確求解方法以及蟻群算法、遺傳算法、模擬退火算法等啟發(fā)式求解方法。在這些算法中，蟻群算法具有結(jié)果精確度高、計算時間短等優(yōu)點，參考文獻(xiàn)[13]給出了一種求解0/1背包問題的快速蟻群算法（KPACA）。考慮到NDN緩存對象的屬性信息滿足蟻群算法的計算要求，本文借鑒蟻群算法的主要思想，提出一種新的基于蟻群算法的緩存替換機(jī)制（ACCR）。

3.3.1 蟻群信息素的計算

在蟻群算法中，信息素是螞蟻群體選擇和演化過程的一種體現(xiàn)，信息素隨著選擇的螞蟻數(shù)量的增多而增加，同時也會隨著時間的增長而逐漸揮發(fā)。但與求解傳統(tǒng)TSP旅行商問題的蟻群算法不同，在求解0/1背包問題的蟻群算法模型中，信息素積累在螞蟻選過的物品上而不是走過的路徑上。本文參照MMAS算法[14]中信息素的更新方式，在執(zhí)行完一輪選擇后僅對螞蟻找出的最優(yōu)解中包含的數(shù)據(jù)內(nèi)容進(jìn)行信息素的增加修改，其余沒有被最優(yōu)解選中的數(shù)據(jù)內(nèi)容信息素相應(yīng)地減少。蟻群信息素τi(t)的更新如式（2）所示。

其中，ρ∈(0,1)為信息素的揮發(fā)系數(shù)，(1-ρ)表示信息素的殘余因子；Δτi表示在時間段p內(nèi)信息素的增量，初始值為 0。信息素增量 Δτi如式（3）所示。

式（3）中考慮到體積大的內(nèi)容占用的緩存空間也大，當(dāng)內(nèi)容沒有被螞蟻最優(yōu)解選中時，會根據(jù)內(nèi)容的大小增加它的揮發(fā)程度。

3.3.2 選擇概率的計算

在蟻群算法中，每個物品都有它被螞蟻選中的概率，稱為選擇概率，記為。參考KPACA[13]，本文中螞蟻k在一輪執(zhí)行過程中選擇緩存對象i的概率(t)如式（4）所示。

其中，τi(t)為物品i上的蟻群信息素，ηi(t)為啟發(fā)式函數(shù)；α、β為信息素因子和期望啟發(fā)式因子，分別反映螞蟻在選擇內(nèi)容時信息素和緩存內(nèi)容屬性對選擇結(jié)果的影響，α值越大，表示螞蟻更傾向于依賴之前螞蟻的選擇結(jié)果；β值越大，則表示螞蟻獨自判斷選擇的能力越大。pitchedk表示螞蟻已經(jīng)判斷過，不能再選擇的內(nèi)容的集合。

啟發(fā)式函數(shù)ηi(t)表示螞蟻選擇緩存對象i的期望程度，啟發(fā)式函數(shù)根據(jù)數(shù)據(jù)內(nèi)容自身的屬性決定螞蟻對緩存內(nèi)容的選擇概率。在選擇概率中加入啟發(fā)式函數(shù)，一方面可以幫助螞蟻加快選擇出最優(yōu)解的速度，另一方面也是結(jié)合數(shù)據(jù)內(nèi)容的實際使用情況，將緩存內(nèi)容自身的信息作為選擇判斷的重要因素。參考文獻(xiàn)[13]中把啟發(fā)式函數(shù)定義為物品單位體積的價值，認(rèn)為物品單位體積的價值越高，選擇該物品的期望就越高。由于本文在內(nèi)容緩存價值計算中已經(jīng)考慮了內(nèi)容體積大小對緩存價值的影響，所以選擇內(nèi)容緩存價值作為期望啟發(fā)式信息，即ηi(t)=Vali(t)。因此，緩存內(nèi)容價值越大，留在緩存空間的期望就越大；相反，緩存價值低的數(shù)據(jù)內(nèi)容應(yīng)盡早替換出去。

3.3.3 基于蟻群算法的緩存替換機(jī)制

當(dāng)路由節(jié)點的緩存空間不足以存儲新內(nèi)容時，根據(jù)ACCR算法進(jìn)行內(nèi)容替換，使得節(jié)點中緩存的數(shù)據(jù)保持較高的內(nèi)容價值。ACCR過程描述如下。

（1）當(dāng)節(jié)點收到存儲內(nèi)容請求時，根據(jù)報文內(nèi)容創(chuàng)建并初始化緩存數(shù)據(jù)對象。訪問命中次數(shù)hitcounti初始化為1，存儲時間記錄為當(dāng)前時間。

（2）計算剩余緩存空間是否能夠存儲該數(shù)據(jù)內(nèi)容。如果空閑緩存空間能夠容納該內(nèi)容，則直接存儲內(nèi)容，結(jié)束；否則，轉(zhuǎn)步驟（3）。

（3）初始化蟻群替換算法參數(shù)，設(shè)各內(nèi)容對象的信息素τi(t)為一固定值τ0。設(shè)定算法參數(shù)α、β和ρ，設(shè)定時間 t為系統(tǒng)當(dāng)前時間。設(shè)定最大迭代次數(shù)loopmax，模擬螞蟻的個數(shù)ma。初始化每個螞蟻的禁忌表pitchedk和解集resultk。

（4）讓每只螞蟻k根據(jù)式（4）計算出緩存內(nèi)容被選擇的概率(t)，螞蟻k根據(jù)該概率值選擇下一個緩存內(nèi)容i，并將該內(nèi)容加入禁忌表pitchedk中，表示該內(nèi)容已經(jīng)被選擇過。然后試著將該內(nèi)容放入解集resultk中，如果該解集的內(nèi)容總體積小于節(jié)點最大緩存容量S，則把該內(nèi)容并入解集resultk中作為可行解的一部分。循環(huán)上述過程，直到ma只螞蟻都做完了對所有緩存的選擇判斷，并構(gòu)造出各自的解集。

（5）找出本輪循環(huán)結(jié)束后所有螞蟻的解集中緩存價值最大的解集resultmax，如果該解集的總緩存價值大于當(dāng)前最優(yōu)解，則替換當(dāng)前最優(yōu)解。如果迭代次數(shù)小于最大迭代次數(shù)并且不滿足結(jié)束條件，則更新信息素并轉(zhuǎn)至步驟（4）；否則，轉(zhuǎn)至步驟（6）。

（6）如果新到達(dá)的數(shù)據(jù)內(nèi)容在最優(yōu)解中，則將新到達(dá)內(nèi)容存入本地緩存，不在最優(yōu)解中的緩存內(nèi)容替換出去；否則，不存儲新到來的數(shù)據(jù)內(nèi)容。緩存替換執(zhí)行結(jié)束。

3.4 基于蟻群替換算法的鄰居協(xié)作緩存管理策略

緩存替換算法找出需要替換的內(nèi)容之后，啟用協(xié)作緩存機(jī)制查詢鄰居節(jié)點是否存儲了該內(nèi)容的副本，若是，則直接刪除該內(nèi)容不做協(xié)作緩存處理；否則，根據(jù)鄰居節(jié)點的緩存狀態(tài)信息，計算協(xié)作替換參數(shù)，選擇合適的協(xié)作緩存節(jié)點。節(jié)點e的鄰居節(jié)點j的協(xié)作替換參數(shù)計算如下：

其中，delayj為對鄰居節(jié)點j的訪問時延為鄰居節(jié)點j的平均內(nèi)容緩存價值。由于兩個相鄰節(jié)點之間的通信狀況不好，會導(dǎo)致將來從該鄰居節(jié)點獲取緩存數(shù)據(jù)時花費較高的時間成本，所以在選擇緩存協(xié)作節(jié)點時，考慮了鄰居節(jié)點之間的通信時延。此外，由于平均內(nèi)容緩存價值可以反映一個節(jié)點存儲的數(shù)據(jù)內(nèi)容的整體質(zhì)量，因此應(yīng)選擇平均緩存價值較低的鄰居節(jié)點作為協(xié)作節(jié)點，以提高鄰居節(jié)點的整體緩存價值。

節(jié)點協(xié)作緩存模塊的處理流程如圖4所示。

4 實驗仿真與性能分析

4.1 實驗環(huán)境構(gòu)建

為驗證本文提出的緩存管理策略的可行性和有效性，對ACNCM策略進(jìn)行了模擬實驗。采用C++及MATLAB語言模擬以事件為驅(qū)動的協(xié)作緩存管理系統(tǒng)。

首先模擬實驗過程中的數(shù)據(jù)輸入，依據(jù)現(xiàn)實生活中用戶對互聯(lián)網(wǎng)內(nèi)容資源的訪問特征，實驗中設(shè)定用戶發(fā)起的請求序列符合柏拉圖定律，即80%的請求報文對應(yīng)于20%的內(nèi)容。用戶對內(nèi)容請求的時間間隔服從指數(shù)分布。然后實現(xiàn)ACNCM的邏輯處理部分，這是整個實驗的核心部分，用來模擬緩存替換算法以及基于鄰居協(xié)作的緩存管理過程。

網(wǎng)絡(luò)拓?fù)湟?guī)模根據(jù)GT-ITM拓?fù)渖晒ぞ呱梢粋€節(jié)點數(shù)為10的隨機(jī)網(wǎng)絡(luò)拓?fù)鋱D，其中任意兩個節(jié)點之間存在直達(dá)路徑的概率為0.4。從隨機(jī)生成的拓?fù)鋱D的邊緣節(jié)點中選擇一個節(jié)點作為內(nèi)容提供節(jié)點，選取兩個邊緣節(jié)點作為客戶端節(jié)點。相鄰路由節(jié)點之間的時延設(shè)為20 ms，NIB報文的最大轉(zhuǎn)發(fā)跳數(shù)設(shè)為5。實驗中算法的相關(guān)參數(shù)α、β、ρ的取值分別為0.4、0.3和0.7，協(xié)作鄰居深度設(shè)定為1。模擬實驗的具體參數(shù)配置見表3。

表3 實驗參數(shù)

4.2 緩存替換算法ACCR的性能分析

圖4 協(xié)作緩存流程

首先考察單節(jié)點緩存替換算法ACCR的性能。在相同的實驗環(huán)境下，針對路由節(jié)點的緩存容量為50 MB和80 MB兩種情況，分別進(jìn)行ACCR算法、LRU算法和FIFO算法的實驗，運行結(jié)果如圖5、圖6所示。

圖5 緩存空間為50 MB時的緩存命中率

圖6 緩存空間為80 MB時的緩存命中率

由圖5和圖6可以看出，ACCR的緩存命中率高于LRU算法和FIFO算法。分析其原因，ACCR在執(zhí)行緩存替換時綜合考慮了緩存對象自身的屬性信息，如緩存數(shù)據(jù)的大小、訪問次數(shù)、鄰居副本因素、存儲時間等，同時結(jié)合蟻群信息素的正反饋機(jī)制，使得緩存中保留了那些緩存價值較高的數(shù)據(jù)內(nèi)容。

4.3 協(xié)作緩存策略ACNCM的性能分析

引入鄰居協(xié)作緩存機(jī)制，考察在相同的實驗環(huán)境下，F(xiàn)IFO、LRU、ACCR和ACNCM 4種緩存管理策略的報文開銷和平均時延。報文開銷定義為網(wǎng)絡(luò)報文總數(shù)與用戶得到的響應(yīng)報文的比值。如圖7所示，F(xiàn)IFO緩存管理策略產(chǎn)生的報文開銷最大，LRU緩存管理策略次之；ACCR的效果比LRU好，但是相比于ACNCM性能又相對較差。說明ACNCM能有效降低全網(wǎng)絡(luò)的報文數(shù)量，降低網(wǎng)絡(luò)總開銷。

如圖8所示的實驗結(jié)果表明，ACNCM的平均時延要優(yōu)于其他緩存管理策略，這主要是由于鄰居協(xié)作緩存管理策略充分利用了鄰居節(jié)點的緩存功能。通過協(xié)作存儲內(nèi)容使得鄰居節(jié)點之間作為一個整體，存儲了緩存價值較高的緩存內(nèi)容，更高效地利用了整體的緩存空間。當(dāng)用戶請求到達(dá)時，ACNCM可以更快地響應(yīng)用戶請求，提高用戶對內(nèi)容資源請求的響應(yīng)效率，降低了響應(yīng)時延。

圖7 報文開銷比較

圖8 平均時延比較

5 結(jié)束語

針對NDN緩存利用效率問題，本文根據(jù)數(shù)據(jù)內(nèi)容自身的屬性信息以及鄰居節(jié)點的存儲狀態(tài)信息，提出一種基于鄰居協(xié)作的緩存管理（ACNCM）策略。本文的主要工作包括：定義了緩存數(shù)據(jù)的內(nèi)容價值屬性，結(jié)合鄰居節(jié)點的緩存信息，為節(jié)點緩存替換決策提供重要參考；將緩存替換問題建模為0/1背包問題，利用蟻群優(yōu)化算法，結(jié)合蟻群信息素和緩存內(nèi)容自身的屬性信息，對節(jié)點的緩存空間進(jìn)行替換管理；采用鄰域協(xié)作思想，依據(jù)內(nèi)容緩存價值和鄰居緩存信息，選擇合適的鄰居節(jié)點作為協(xié)作緩存節(jié)點，提升鄰居節(jié)點間整體緩存利用率。

實驗結(jié)果表明，ACNCM機(jī)制在緩存的命中率、用戶請求的響應(yīng)時延以及網(wǎng)絡(luò)整體開銷等方面，相比現(xiàn)有緩存管理方法都有不同程度的優(yōu)化。進(jìn)一步的研究工作包括探討與協(xié)作替換參數(shù)相關(guān)的鄰居屬性，優(yōu)化NIB更新報文，實現(xiàn)更準(zhǔn)確的節(jié)點間協(xié)作開銷估算。此外，增加更多同類算法的對比也是未來要完成的工作之一。

1 Zhang L,Estrin D,Burke J,et al.Named Data Networking(NDN)Project.Technical Report NDN-0001,Xerox Palo Alto Research Center-PARC,2010

2 Willick D L,Eager D L,Bunt R B.Disk cache replacement policies for network fileservers.Proceedings of the Distributed Computing Systems,California,USA,1993:2～11

3 張震波,楊鶴標(biāo),馬振華.基于LRU算法的Web系統(tǒng)緩存機(jī)制.計算機(jī)工程,2006,32(19):68～70

4 Chrobak M,Noga J.LRU is better than FIFO.Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms,San Francisco,California,USA,1998:78～81

5 Abrams M,Standridge C R,Abdulla G,et al.Removal policies in network caches for world-wide web documents.Proceedings of the ACM SIGCOMM,Stanford,CA,USA,1996:293～305

6 李韜,李玉宏.一種基于內(nèi)容熱度的NDN緩存替換算法.中國科技論文在線,2012

7 張國強(qiáng),李楊,林濤等.信息中心網(wǎng)絡(luò)中的內(nèi)置緩存技術(shù)研究.軟件學(xué)報,2014,25(1):154～175

8 Ming Z,Xu M,Wang D.Age-based cooperative caching in information-centric networks. Proceedings of the IEEE INFOCOM WKSHPS,Orlando,FL,USA,2012:268～273

9 劉外喜,余順爭,蔡君等.ICN中的一種協(xié)作緩存機(jī)制.軟件學(xué)報,2013,24(8):1947～1962

10 Eum S,Nakauchi K,Murata M,et al.CATT:potential based routing with content caching for ICN.Proceedings of the Second Edition of the ICN Workshop on Information-Centric Networking,Istanbul,Turkey,2012:49～54

11 Wang Y,Lee K,Venkataraman B,et al.Advertising cached contents in the control plane: necessity and feasibility.Proceedings of the IEEE INFOCOM WKSHPS,Orlando,FL,USA,2012:286～291

12 Wang J M,Zhang J,Bensaou B.Intra-AS cooperative caching for content-centric networks.Proceedings of the 3rd ACM SIGCOMM Workshop on Information-Centric Networking,Santa Barbara,CA,2013:61～66

13 王會瑩,賈瑞玉,章義剛等.一種求解0/1背包問題的快速蟻群算法.計算機(jī)技術(shù)與發(fā)展,2007,17(1):104～106

14 Stutzle T,Holger H H.Max-min ant system.Future Generation Computer System,2000,16(8):889～914