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

董利利 ，王 勇 ，董永強 ,2，楊 鵬 ,2

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

1 引言

以內(nèi)容為中心的命名數(shù)據(jù)網(wǎng)絡[1]（named data networking，NDN）的重要特征之一，是利用網(wǎng)絡內(nèi)置緩存機制提高用戶獲取內(nèi)容資源的效率和網(wǎng)絡資源的利用率。在NDN中，路由節(jié)點依靠報文中攜帶的內(nèi)容名字轉發(fā)數(shù)據(jù)內(nèi)容，同時每個路由節(jié)點都具有緩存本地轉發(fā)過的數(shù)據(jù)內(nèi)容的能力，以便后續(xù)相同請求到達時可利用緩存副本直接響應該請求，從而提高響應效率。研究設計高效的緩存管理機制對提升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)容存儲的先后順序依次進行緩存替換；SIZE[5]替換算法則將數(shù)據(jù)內(nèi)容的大小作為緩存替換的主要因素，優(yōu)先替換緩存中占用空間較大的數(shù)據(jù)內(nèi)容。參考文獻[6]提出了一種基于內(nèi)容熱度的NDN緩存替換策略。在保留NDN中CS、PIT以及 FIB結構的基礎上新增了一張 CPT（content popularity table），用來保存緩存內(nèi)容的命中率、歷史及當前熱度，熱度值按計時周期進行加權平均，在緩存替換過程中選擇熱度最小的內(nèi)容進行替換。

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

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

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

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

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

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

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

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

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

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

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

表1 NCT

表2 NST

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

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

（1）NIB 更新報文

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

圖2 NIB更新報文結構

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

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

2.2 ACNCM緩存管理的基本思想

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

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

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

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

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

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

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

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

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

其中，si表示內(nèi)容i的體積，也即占用的緩存空間，數(shù)據(jù)內(nèi)容的體積越大，其緩存價值越小。t表示當前時間，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)絡設定的最大協(xié)作鄰居深度值加1。鄰居深度越大，從鄰居節(jié)點獲取數(shù)據(jù)內(nèi)容的開銷越大，在本節(jié)點就更有存儲的價值，所以鄰居深度與緩存價值成正比。

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

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

3.3.1 蟻群信息素的計算

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

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

式（3）中考慮到體積大的內(nèi)容占用的緩存空間也大，當內(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)容屬性對選擇結果的影響，α值越大，表示螞蟻更傾向于依賴之前螞蟻的選擇結果；β值越大，則表示螞蟻獨自判斷選擇的能力越大。pitchedk表示螞蟻已經(jīng)判斷過，不能再選擇的內(nèi)容的集合。

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

3.3.3 基于蟻群算法的緩存替換機制

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

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

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

（3）初始化蟻群替換算法參數(shù)，設各內(nèi)容對象的信息素τi(t)為一固定值τ0。設定算法參數(shù)α、β和ρ，設定時間 t為系統(tǒng)當前時間。設定最大迭代次數(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只螞蟻都做完了對所有緩存的選擇判斷，并構造出各自的解集。

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

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

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

緩存替換算法找出需要替換的內(nèi)容之后，啟用協(xié)作緩存機制查詢鄰居節(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é)點之間的通信狀況不好，會導致將來從該鄰居節(jié)點獲取緩存數(shù)據(jù)時花費較高的時間成本，所以在選擇緩存協(xié)作節(jié)點時，考慮了鄰居節(jié)點之間的通信時延。此外，由于平均內(nèi)容緩存價值可以反映一個節(jié)點存儲的數(shù)據(jù)內(nèi)容的整體質量，因此應選擇平均緩存價值較低的鄰居節(jié)點作為協(xié)作節(jié)點，以提高鄰居節(jié)點的整體緩存價值。

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

4 實驗仿真與性能分析

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

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

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

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

表3 實驗參數(shù)

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

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

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

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

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

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

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

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

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

圖7 報文開銷比較

圖8 平均時延比較

5 結束語

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

實驗結果表明，ACNCM機制在緩存的命中率、用戶請求的響應時延以及網(wǎng)絡整體開銷等方面，相比現(xiàn)有緩存管理方法都有不同程度的優(yōu)化。進一步的研究工作包括探討與協(xié)作替換參數(shù)相關的鄰居屬性，優(yōu)化NIB更新報文，實現(xià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 張震波,楊鶴標,馬振華.基于LRU算法的Web系統(tǒng)緩存機制.計算機工程,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 張國強,李楊,林濤等.信息中心網(wǎng)絡中的內(nèi)置緩存技術研究.軟件學報,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é)作緩存機制.軟件學報,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背包問題的快速蟻群算法.計算機技術與發(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