NDMANET 中基于內容優先級的緩存策略研究

高子軒，鄭 烇，2

（1.中國科學技術大學自動化系未來網絡實驗室，合肥 230026；2.中國科學技術大學先進技術研究院，合肥 230088）

0 概述

隨著移動互聯網的快速發展，現有的網絡體系在可擴展性、移動性和安全性等方面逐漸出現性能瓶頸。為了適應互聯網的需求變化，一種新的網絡體系架構——信息中心網絡（Information Centric Networks，ICN）［1］應運而生，而命名數據網絡（Named Data Networks，NDN）［2］作為ICN 架構的一種具體網絡實現，受到研究人員的廣泛關注。在NDN 中，用戶通過內容名稱去獲取內容，而無需關心內容從何而來，同時，在返回內容的過程中會在沿路根據緩存策略進行緩存。

近年來，考慮到NDN 的優越性能，研究人員開始將NDN 和移動自組織網絡（Mobile Ad hoc Networks，MANET）相結合并進行分析［3-5］。傳統的MANET 基于TCP/IP 協議進行通信，但是由于MANET 中節點移動而引起了網絡拓撲動態變化，導致其難以建立穩定的端到端鏈路，這不僅使得網絡較難實現高效的數據傳輸，同時也阻礙了MANET 的實際應用。由于MANET 中多數通信是“以內容為中心”的信息共享，而不關心數據承載在哪個終端以及某個數據是由哪個終端產生，因此NDN 適用于MANET［6-8］，其比“以主機為中心”的IP 路由協議更有利于數據傳輸。

命名數據無線移動自組織網絡（NDMANET）的研究起步較晚，許多問題亟待解決。其中，緩存策略是NDN 中的一個關鍵技術［9-11］，由于MANET 中節點的移動性、網絡的動態性以及網絡所呈現出的分布式特性，使得現有NDN 中的緩存機制可能不再適用于NDMANET。因此，如何在節點空間資源有限、網絡節點自由移動的MANET 中有效保證數據的可用性，提高更高優先級內容的命中率，加快請求的響應速度，降低數據冗余，是NDMANET 數據緩存機制研究中的關鍵問題。

不同于有線環境下可以擴展較大的緩存容量，無線環境下移動節點的緩存容量大小受限，因此，對緩存替換策略的研究顯得尤為重要。目前，緩存替換策略主要包括先進先出（FIFO）、最近最少使用（LRU）［12］和最少經常使用（LFU）［13］。這些策略多數是從現有網絡中演變而來，通常存在兩點缺陷，一方面，它們沒有考慮內容本身的特性，例如內容優先級、內容的訪問頻率等，另一方面，未考慮MANET應用場景下節點自由移動時重要節點脫離網絡時引發重要內容不可用的問題。因此，上述策略并不適用于NDMANET 這種新型網絡架構。

本文分析NDN 的特性，根據內容本身所傳達的信息，如內容優先級、內容訪問頻率等指標，提出一種基于內容優先級的緩存替換策略PFC。通過向數據包添加新的TLV 字段“priority”，設計決策函數實現緩存內容的替換，以在保證平均緩存命中率的同時提高重要內容的緩存命中率和可用性。

1 相關工作

緩存機制包括緩存放置策略、緩存替換策略和緩存一致性維護策略等。緩存替換策略在緩存已滿而需要緩存新對象時，決定如何替換出緩存中的一些舊對象，從而為新對象騰出空間。在NDMANET中，有限的緩存空間使緩存替換策略更具挑戰性。NDMANET 的緩存研究包括MANET 和NDN 2 個方面。

在MANET 的相關緩存研究中，學者們提出了各種緩存技術。文獻［14］提出一種SQUIRREL 緩存軟件，該軟件可以集成到Internet的節點中，允許區域內的多個節點共享其緩存。文獻［15］提出CachePath、CacheData 和HybridCache 3 種緩存方案，CachePath存儲數據的位置和路徑信息，CacheData 通過存儲數據而非路徑來節省時間，HybridCache 是一種混合方案。上述MANET 緩存策略均基于TCP/IP 網絡，需要存儲與內容對應的IP 地址，因此，并不適用于NDN 網絡。

在NDN 的相關緩存研究中，多數使用LRU、FIFO、LFU 和Random 策略作為緩存替換策略。為了提高NDN 的性能，研究人員也為其設計了很多緩存算法。文獻［11］提供了有關信息中心網絡中緩存機制的調查結果，其分析不同的參數（如緩存時間、內容本身、內容相關性以及緩存中的生存期）對ICN緩存性能的影響。文獻［16］提出一種ICN 的緩存替換策略，其將內容的流行度視為替換指標，此外，還考慮網絡中的全局流行度。但是，該策略不適用于NDMANET，一方面，對于NDMANET 而言，全局內容流行度并不現實，而且還會對CS 管理造成更多的負擔；另一方面，該策略會延長緩存檢索時間。文獻［17］提出一種基于流行度的細粒度緩存替換策略FGPC，但是，FGPC 僅使用請求頻率來決定內容的替換。文獻［18］提出一種基于層次流行度的緩存替換策略，其將內容流行度分為5 個層次，每個數據包都屬于一個流行度級別，當緩存已滿時，將替換緩存中流行度最低的數據包。但是，該策略也導致一個問題，一些重要內容不一定是流行內容，僅通過流行度去決定緩存替換，對于一些特定內容將不合適。文獻［19］提出一種通用緩存替換策略，節點可以通過各項指標，包括請求頻率、節點距離、節點可達性等，綜合決定替換內容，但是，該策略中的內容度量系統CMS 的權重系數是根據節點和網絡中心的距離來確定的，對于MANET 這種去中心化的網絡而言顯然不合理。文獻［20］將節點的位置加入到緩存替換決策中，但是，其決策函數考慮的因素較多，計算復雜度較高，從而提高了替換時的計算代價與響應時間。

從已有文獻可以看出，MANET 緩存研究是基于IP 網絡的，不適用于NDMANET 網絡，針對NDN 的緩存替換策略也不適合NDMANET，原因是它們沒有考慮節點的移動性、網絡的去中心化等NDMANET 的特性。此外，多數緩存策略并未考慮內容本身的優先級。因此，本文從內容的優先級出發，同時兼顧內容的請求頻率，提出一種緩存替換策略PFC。

一扇窗子立刻打開，拿著槍的黑臉孔的人竟跳進來，踏了金枝的左腿一下。那個黑人向棚頂望了望，他熟悉地爬向棚頂去，王婆也跟著走來，她多日不見金枝而沒說一句話，宛如她什么也看不見似的。一直爬上棚頂去。金枝和母親什么也不曉得，只是爬上去。直到黃昏惡消息仍沒傳來，他們和爬蟲樣才從棚頂爬下。王婆說：“哈爾濱一定比鄉下好，你再去就在那里不要回來，村子里日本子越來越惡，他們捉大肚女人，破開肚子去破‘紅槍會’（義勇軍的一種），活顯顯的小孩從肚皮流出來。為這事，李青山把兩個日本子的腦袋割下掛到樹上。“

2 基于內容優先級的緩存替換策略

有效的緩存替換策略可以提高緩存命中率，從而提升內容分發性能。但是，現有研究一方面未考慮NDMANET 不同于傳統NDN 網絡的3 個特點：1）分布式控制，沒有中心節點；2）節點的自由移動導致網絡拓撲變化以及某些節點可能會“掉線”的情況；3）節點的資源有限。另一方面，現有緩存策略僅考慮內容的流行度而忽略了內容本身的優先級，這會導致重要內容的可用性降低，一旦重要節點離開網絡，可能出現請求無響應的情況。

2.1 NDN 緩存機制

NDN 的通信模型由消費者驅動，消費者發送興趣包（Interest Packet）請求相應的數據包（Data Packet）。節點在收到興趣包后，其內容緩存CS（Content Store）中如果有匹配的內容，則會返回數據包；否則，節點先查詢未決興趣表PIT，查看是否有記錄，若無記錄，興趣包將根據轉發信息表FIB 在網絡中進一步轉發。在接收到數據包后，節點首先檢查相關請求是否在PIT 中，如果對該數據的請求仍然沒有得到響應，則將數據進一步轉發到網絡中的下游，否則將丟棄該數據。同時，節點根據適當的緩存決策方案將數據存儲在CS 中，如果CS 達到其最大容量，則根據緩存替換策略進行內容替換。NDN 的通信流程如圖1 所示。

圖1 NDN 通信流程Fig.1 NDN communication procedure

2.2 內容的可用性與優先級

在NDMANET 中，內容的可用性指在網絡中一部分節點出現故障后，網絡整體是否還能響應消費者的請求。在一些實際的NDMANET 應用場景，如軍事活動、救援行動中，由于環境的復雜性，可能經常發生節點脫離網絡的情況。如果該節點緩存了重要內容，可能會導致重要內容不可用。因此，對于NDMANET 而言，節點可用性的重要程度不低于命中率、響應延時等指標。

常用的保證可用性的方法是在多處保留內容副本，對于NDN 架構而言，其每個節點所帶有的緩存能力可以很好地解決該問題，但是，這些是建立在緩存容量足夠大的情況下。在移動場景中，大緩存意味著低移動性，為保證節點的移動性，高可用性需要與緩存替換策略相結合。因為難以提高所有內容的可用性，所以本文的目標是提高重要內容的可用性。根據節點內容對可用性的不同需求，本文對內容優先級進行劃分，即一個內容很重要，在網絡中需要很高的可用性，則其優先級相應很高。

在本文模型中，通過對數據包添加新的TLV 字段“priority”來區分內容的優先級，priority 值越大，內容優先級就越高。

2.3 緩存替換策略

緩存替換決策函數所含的參數如下：

2）節點的請求頻率。本文期望在引入內容優先級后對全局平均命中率并不會產生太大影響，因為NDN 緩存的本質就是為后續請求提供內容副本從而提高網絡性能，包括請求的響應時間、吞吐量和網絡負載等，如果僅考慮優先級，則會對全局性能造成影響，一些較為流行的內容可能因為沒有被標記為重要內容而被替換，因此，本文引入節點的請求頻率，請求頻率度量內容在當前節點的CS 中被請求的次數，在某種程度上可以反映一個內容是否流行，如果是流行內容，其請求頻率會相對較大。

3）內容大小。考慮到移動自組織網絡節點緩存容量的限制，本文將內容大小也作為一個衡量指標。

根據以上分析，對于每一個到達CS 的內容k而言，都需要計算一個如式（1）所示的函數：

其中，P(k)表示內容k的優先級，F(k)表示內容k在當前CS 中的請求頻率，S(k)表示內容k的大小，cf是F(k)的標準化系數，cs是S(k)的標準化系數。

從式（1）可以看出，R(k)隨著F(k)線性增長，即當有很多節點對同一個內容k發起請求時，R(k)可能會變得很大，但是如果在接下來一段時間內沒有節點請求內容k，k也會一直被緩存在CS 中，因為沒有較大的R(j)來替換它。為了解決這一問題，本文在替換策略中考慮內容的生成周期，每次新內容到達后CS 會檢測緩存中是否有內容過期，如果有，則刪除該內容，以騰出緩存空間。

基于內容優先級的緩存替換策略PFC 的偽代碼如算法1 所示，其步驟為：當一個內容k到達CS 時，先檢查該內容是否已經在緩存中，如果已經在緩存中，則更新R(k)的值；否則，檢測緩存空間是否已滿，若緩存未滿，則緩存該內容，如果緩存已滿，則計算R(k)值，并與CS 其他內容的R值進行比較，淘汰R值最小的內容，最后，清空過期的內容。

算法1基于內容優先級的緩存替換策略PFC

3 實驗結果與分析

本文選取比較常用的緩存策略LRU 和FIFO 作為對照組，通過模擬仿真來分析基于內容優先級的緩存替換策略的緩存性能。

3.1 實驗環境

使用ndnSIM 仿真平臺進行實驗，網狀拓撲共包含50 個節點，每個節點既是內容生產者（Producer）也是內容消費者（Consumer），實驗參數設置如表1 所示。不同生產者產生的內容有不同的優先級標記，為了方便分析，本文將內容分為重要內容和普通內容2 種，其中，10%是重要內容，其余是普通內容，所有的內容流行度服從Zipf-mandelbrot 分布，消費者節點對內容的請求服從泊松分布，請求速率為10 req/s。此外，為了模擬移動網絡的情景，在仿真進行到5 min 時，通過改變節點的通斷關系來改變網絡拓撲。

表1 實驗環境的參數設置Table 1 Parameters setting of experimental environment

3.2 結果分析

緩存命中率是到達緩存節點時命中的請求數與到達緩存節點的請求總數之比。圖2 所示為不同緩存替換策略下緩存命中率與緩存大小的關系，從圖2可以看出，隨著緩存容量的增加，各策略的內容命中率都提高，原因是緩存容量增加，可以緩存的內容副本數也隨之增加，導致內容的命中率提高。

圖2 平均緩存命中率隨緩存容量的變化情況Fig.2 The change of average cache hit rate with cache capacity

圖3 所示為重要內容命中率隨緩存容量的變化情況，從圖3 可以看出，各策略的重要內容命中率也隨緩存容量的增大而提升，且本文內容優先級緩存策略對于重要內容的緩存命中率有顯著提高，特別是在緩存容量較小時，緩存命中率較其他2 種策略而言提升幅度更大。這是因為緩存大小有限時，內容優先級緩存策略優先保留內容優先級較高的內容，即淘汰相對不重要的內容。隨著緩存容量的增加，可以緩存更多的內容副本，內容優先級緩存策略對于重要內容的緩存命中率仍然高于其他緩存替換策略。

圖3 重要內容緩存命中率隨緩存容量的變化情況Fig.3 The change of important content cache hit rate with cache capacity

圖4 所示為重要內容緩存占比隨緩存容量的變化情況，從圖4 可以看出，在緩存容量較小時，重要內容在緩存中占比最高，此時緩存的都是較為重要且請求較多的內容，隨著緩存容量的增加，重要內容緩存占比開始減小。圖4 中開始階段本文策略的重要內容緩存占比達到1 是因為緩存較小，而重要內容的數量大于緩存容量，因此本文策略將重要內容全部緩存從而替換不重要的內容。其他策略的重要內容緩存占比基本保持不變，即它們并不區分重要內容與普通內容。

圖4 重要內容緩存占比隨緩存容量的變化情況Fig.4 The change of important content cache proportion with cache capacity

圖5 所示為平均響應跳數隨緩存容量的變化情況，從圖5 可以看出，緩存可以降低請求的平均響應跳數，隨著緩存容量的增加，響應跳數減少，內容請求者可以更快地獲取內容，原因是隨著用戶的不斷請求，其感興趣的內容被緩存在離用戶近的節點，響應跳數隨之降低。

圖5 平均響應跳數隨緩存容量的變化情況Fig.5 The change of average response hops with cache capacity

為了驗證本文緩存策略PFC 在提高內容可用性方面的性能，設計一個簡單的包含10 個節點的小型拓撲，網絡中有2 個節點產生重要內容，在仿真進行到3 min 時分別不斷開、斷開1 個和2 個重要節點與網絡的連接，然后計算10 s 后的內容命中率，以反映重要內容的可用性。實驗結果如圖6 所示，其中，100%-topo 表示2 個節點都不斷開，50%-topo 表示1 個節點斷開，0%-topo 表示2 個節點均斷開。從圖6可以看出，在沒有節點斷開時，3 種緩存策略的命中率相差不多，隨著重要節點的斷開，命中率下降，這是因為內容生產者節點斷開連接后，用戶需要去向其他潛在內容擁有者請求，原有路由可能請求不到內容，造成命中率下降。但是，本文策略命中率下降幅度比較緩慢，這是因為該策略優先緩存重要內容，在整個網絡中重要內容副本更多，所以更容易命中。

圖6 緩存命中率隨拓撲結構的變化情況Fig.6 The change of cache hit rate with topology

4 結束語

本文提出一種基于內容優先級的緩存替換策略。根據節點內容對可用性的不同需求劃分內容優先級，將優先級作為緩存替換的參考因子進行緩存替換決策。實驗結果表明，該策略能夠提高NDMANET 網絡的緩存命中率，縮短響應時間，提升網絡的抗毀性。本文的內容優先級劃分方式較簡單，今后將通過更精確的方法，如根據生產者節點之間的博弈以及一些經濟指標來決定緩存內容的優先級，從而使本文策略更具可靠性。