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

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

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

1 引言

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

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

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

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

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

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

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

2 基于鄰居協作的NDN緩存管理框架

2.1 鄰居協作模型與協議交互機制

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

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

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

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

表1 NCT

表2 NST

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

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

（1）NIB 更新報文

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

圖2 NIB更新報文結構

（2）協作緩存報文

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

2.2 ACNCM緩存管理的基本思想

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

（1）單節點的緩存替換機制

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

（2）鄰域協作緩存管理機制

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

3 ACNCM緩存替換與鄰居協作算法

3.1 單節點緩存替換問題建模

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

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

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

3.2 數據內容的緩存價值計算

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

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

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

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

3.3.1 蟻群信息素的計算

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

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

式（3）中考慮到體積大的內容占用的緩存空間也大，當內容沒有被螞蟻最優解選中時，會根據內容的大小增加它的揮發程度。

3.3.2 選擇概率的計算

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

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

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

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

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

（1）當節點收到存儲內容請求時，根據報文內容創建并初始化緩存數據對象。訪問命中次數hitcounti初始化為1，存儲時間記錄為當前時間。

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

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

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

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

（6）如果新到達的數據內容在最優解中，則將新到達內容存入本地緩存，不在最優解中的緩存內容替換出去；否則，不存儲新到來的數據內容。緩存替換執行結束。

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

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

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

節點協作緩存模塊的處理流程如圖4所示。

4 實驗仿真與性能分析

4.1 實驗環境構建

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

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

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

表3 實驗參數

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

圖4 協作緩存流程

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

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

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

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

4.3 協作緩存策略ACNCM的性能分析

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

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

圖7 報文開銷比較

圖8 平均時延比較

5 結束語

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

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

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系統緩存機制.計算機工程,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 李韜,李玉宏.一種基于內容熱度的NDN緩存替換算法.中國科技論文在線,2012

7 張國強,李楊,林濤等.信息中心網絡中的內置緩存技術研究.軟件學報,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中的一種協作緩存機制.軟件學報,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背包問題的快速蟻群算法.計算機技術與發展,2007,17(1):104～106

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