基于內容預期價值的內容中心網絡緩存替換策略*

王 珂，江凌云，董 唱

（南京郵電大學 通信與信息工程學院，江蘇 南京 210003）

0 引言

內容中心網絡（Content Centric Network，CCN）的關鍵技術研究主要包括命名、路由、緩存、移動性和安全性等方面[1]。緩存作為內容中心網絡發展的基石，在內容中心網絡中起到十分重要的作用。內容中心網絡中的內容路由器（Content Router，CR）都帶有緩存功能，用戶通過興趣包發出對內容的請求，CR 節點收到請求后首先在本地緩存空間（Content Store，CS）中查找，若查找到所需數據，則可以直接響應請求，回復數據包。相對于從更遠的服務器獲取數據，這種方式可以大大減少獲取內容所需的路由跳數、快速響應用戶請求，降低網絡傳輸流量，提高網絡服務質量。

CCN 中對緩存的研究包含多個方面，其中包括緩存決策策略和緩存替換策略。決策策略決定了內容會在哪些節點存儲，替換策略則在緩存空間不夠時決定了替換哪些舊數據為新數據讓出緩存空間。大量研究表明，緩存策略對CCN 有著巨大影響[2]。良好的緩存策略可以獲得更優的緩存收益，更好地發揮CCN 的優勢。

1 相關工作

隨著內容中心網絡的發展，緩存策略得到了大量研究。相對于緩存決策策略，緩存替換策略的研究相對較少。緩存替換策略的理想最優算法是Belady 算法[3]，其總是逐出未來訪問時間距離現在最遠的內容。但因其需要精準知道未來的請求需求，因而無法實現，只能作為理論參考模型，而用于Web、CDN 的部分緩存替換策略依然用于內容中心網絡。目前，最常見的傳統緩存替換策略有最近最少使用（Least Recent Used，LRU）、最少頻率使用(Least Recent Used，LFU)、先入先出（First In First Out，FIFO）、隨機替換（Random Replacement，RR）以及SIZE 等。LRU[4]是根據內容最近一次訪問的時間，將緩存中和當前時刻時間距離最遠的內容替換出去。這種方式背后的邏輯是越是最近被訪問的數據，將來被訪問的可能性越大。但是，LRU僅僅考慮了時間新近性，沒有考慮內容訪問頻率等，存在非流行數據逐出流行數據的問題。LFU[5]以內容的歷史訪問頻率作為衡量，優先替換出歷史訪問次數最小的內容數據。這種方式過于依賴歷史數據，沒有考慮數據內容的變化趨勢，若某內容在之前的一段時間內被頻繁訪問，而最近一段時間不再流行，那么此內容仍然會長期占據緩存空間，因此LFU 不能很好地適應流行數據內容的變化。FIFO實現簡單，以先進先出的方式替換緩存內容；RR 是在需要替換時隨機從緩存中選取內容進行替換，最大的特點是實現簡單，無需復雜的計算開銷；SIZE 則是以內容大小來替換，當緩存空間不足時優先替換所占空間較大的內容。基于LRU 和LFU 改進的緩存替換有很多如LFRU[6]，其綜合考慮了內容的訪問頻率和訪問時間，較LRU 和LFU 有一定的性能提升。文獻[7]提出了多因素加權替換方法，通過給多個影響緩存的因素分配權重，綜合計算得出需要替換的內容塊。文獻[8]提出了一種基于機器學習的緩存替換方法，通過大量的數據訓練得出內容的流行度，并用高流行度的內容替換低流行度的內容。此種方式所需的空間和計算開銷都很大，無法達到CCN中路由器轉發和緩存要保持線性速度的要求，因此這種方式也不適用于當前的CCN 路由器。

文獻[9]指出，緩存中存在大量內容只被請求一次的問題，即內容被請求后放置在緩存節點，但隨后該內容沒有被請求就被從緩存空間中替換出去，這種短時間內的“一次性數據”嚴重影響緩存的性能。一方面緩存大量的“一次性數據”可能會將流行數據逐出緩存空間，另一方面緩存這些“一次性數據”本身并沒有帶來任何收益，沒有讓緩存發揮出其利用價值，是對緩存資源的巨大浪費。因此，針對這種方式帶來的緩存污染問題，許多策略被提出。為了保護流行數據不被替換出去，文獻[10]提出了SLRU，將緩存空間分為兩個部分。當新數據需要緩存時，首先緩存在第一部分空間中；當緩存在第一部分的內容被請求命中時，該內容移動至第二部分空間緩存。兩部分空間單獨執行LRU策略。這種方式可以達到流行內容不被一次性數據替換出去的目的。文獻[11]提出了cache-after-two-hits。在內容被第一次緩存時，只在該節點存儲內容的名稱；當該節點收到對此內容的第二次請求且內容名稱仍然在該緩存節點時，此內容才會被放入緩存中。此種方式可以過濾掉短時間內一次性訪問的數據，減少I/O 讀寫，同時只緩存相對流行的數據。

2 基于內容預期價值的緩存替換策略

傳統的緩存替換策略LRU 只考慮了時間新近性，存在非流行數據將流行數據逐出緩存的問題；LFU 只考慮了數據內容的被請求頻率，之前被多次訪問而現在不再流行的數據容易長時間占據緩存空間。因此，提出一種基于內容預期價值的緩存替換策略。內容的未來價值可以從兩個方面體現：一是內容在將來被請求的概率，即內容的流行度；二是內容在將來被請求的時間。內容被請求的概率越大，則緩存內容的價值越高。同樣，內容在將來的預期被請求時間距離當前時刻越近，則緩存內容的價值越高。綜合這兩種因素，得出緩存內容的預期價值，根據內容的預期價值大小對緩存內容進行替換，以獲取更優的緩存收益。

2.1 內容流行度

內容流行度的表示方式有很多種。最早的LFU是利用內容被訪問的次數來表達流行度。內容被訪問的次數越高，則表示內容的流行度越大。但是，這種表示方式沒有考慮內容被訪問的時間性，因此若用來表示內容在近期的流行度就未必準確。除此之外，文獻[12]提出了對內容中心網絡中的幾種流行度表示方式：

式（1）是以單位時間內某一內容的請求頻率與所有內容請求頻率和的比值，式（2）表示單位時間內某一內容的請求頻率與最大請求頻率的比值。通過仿真實驗對比，發現表達式（2）用來表示流行度時的準確性更好，更能提升緩存性能。因此，本文在表達內容流行度時，參考表達式（2）。由于本文是以內容流行度為其中一個因素來制定緩存替換策略，因此只統計緩存中已有內容的流行度，結合EWMA 算法提出預測內容流行度表達式為：

其中，Pi(t-1)表示流行度在前一周期的指數加權移動平均流行度數值；Pi(t)表示流行度在當前周期的指數加權移動平均流行度數值，并以此表示數據未來的內容流行度；Ni(t)表示在當前周期內內容被命中的次數；表示在當前周期內內容被命中次數最多的數值。在對一些時變的數據指標進行預測時，如果僅僅以最新的數值作為其預測值，則由于最新的一次數據具有隨機性、偶然性，以其全權代表未來預測值有失精準。若對所有歷史數據進行統計，給所有歷史數據以平均權重，則又對新近數據更能代表數據變化趨勢這一因素欠缺考慮。使用式（3）預測內容流行度，可以通過調節權重系數α，調節歷史數據和最新數據的比重。

2.2 內容預期訪問時間

若內容的下一次訪問時間和現在時刻越近，則內容就具有更高的保存價值，因此可對內容的訪問時間進行預測。根據內容的歷史訪問記錄統計，可以得出每項內容歷次的訪問時間間隔。考慮到歷史內容訪問時間間隔對預期訪問間隔的影響程度不同，新近訪問間隔更能體現訪問間隔的變化趨勢，因此在預測訪問時間間隔時也可以使用加權移動平均流行算法思想對其進行預測。每次在緩存中命中某數據條目時，對其平均訪問時間間隔的值進行計算更新，公式如下：

Ti表示最新的加權平均訪問時間間隔，Ti-1表示上一次被訪問時計算所得的平均訪問時間間隔，tnow表示現在的時刻，tlast表示內容上次被命中的時刻。命中某內容時，計算其Ti值并更新tlast值。可以用最新的加權平均時間間隔預測該內容下一次被放請求的時刻，以最后一次命中的時間加上最新的加權平均時間間隔，即：

2.3 內容預期價值的定義

根據2.2 節，已經預測出數據內容下一次被請求的時間，則可以計算出內容下一次被訪問時間距離現在時刻的時間距離，即：

對其用式（8）進行歸一化，可以得到其無量綱表示形式，即：

tmax表示在當前緩存節點中所有條目中計算所得tdistance的最大值。由于內容流行度本身就是無量綱指標，因此綜合內容流行度因素和內容預期訪問時間因素，可以定義內容預期價值的計算公式如下：

由式（9）可以看出，內容流行度越高，預期訪問時間間隔和現在時刻距離越小，則內容的預期價值越大。在進行緩存替換時，可以依據內容的預期價值大小，將具有最小內容預期價值的內容逐出緩存空間。

2.4 算法實現

結合上述內容，本小節將介紹對基于內容預期價值的緩存替換策略的算法的完整實現。在CS 中，每個內容條目都有4 個標簽，分別記錄該內容上一周期所得加權平均流行度、本周期內的命中次數、加權平均訪問時間間隔以及最近一次命中的時間。為了收集和保存實現該算法的必要信息，每個數據包新增Flag 字段、加權平均訪問時間間隔T。當數據在服務器命中時，將Flag 置為1；在緩存節點命中時，置為0。增加加權平均訪問時間間隔T的目的是當回傳路徑上的某節點決定緩存該內容時，以此數值初始化該條目對應的加權平均時間間隔。本算法對內容進行預過濾，采用和cache-after-twohits 類似的方式，但只對在服務器命中的數據進行過濾。請求在服務器命中，說明中間經過的緩存節點沒有緩存該內容，那么該內容在此條路徑上相對不是流行數據，因此緩存時只緩存內容名稱，防止一次性內容對緩存的污染。同時，為了避免過度保護的問題，對在緩存節點命中的數據不予過濾。通過該方式達到了對新增平均訪問時間間隔T字段的初始計算賦值，保證該算法的可實施性。由于本文只涉及緩存替換策略，并不討論決定是否緩存該內容的緩存決策算法，因此網絡緩存節點對數據包的處理流程如下：

數據包轉發到緩存節點，根據緩存決策策略。若不對該內容進行緩存，則直接對數據包根據PIT表轉發；若決定對該內容進行緩存，則判斷數據來源判斷是否需要對該內容進行過濾。若符合緩存到CS 中的條件時，依據內容預期價值，將具有最小預期價值的內容替換掉緩存該內容，并對該內容的4 個標簽進行初始化。

同時，當請求在緩存節點命中時，緩存節點對內容中的本周期內命中次數加1，并更新加權平均訪問時間間隔和最近一次訪問時間。

3 仿真與分析

3.1 仿真設計

本文對所提方法進行了驗證，通過ndnsim 平臺進行仿真。設置內容服務器有10 000 個內容塊，各個內容塊大小相同，消費者請求速率為100 r/s，齊普夫參數在0.7～1.3，默認為1.0。每個緩存節點的大小以內容塊衡量，在100～1 000 之間默認大小為500。仿真時間為100 s，設內容流行度統計周期為5 s，α、β取值都為0.6。緩存決策策略使用默認的LCE，轉發策略使用默認的最短路徑優先，鏈路延遲設為10 ms。

3.2 性能指標

3.2.1 緩存節點的平均命中率

平均緩存命中率（Average Cache Hit Ratio，ACHR）表示用戶發出的總請求次數與請求在緩存節點命中次數的比值，即：

其中Hi代表節點i的緩存命中率，N代表總的緩存節點數。ACHR越大，緩存策略性能越好。

3.2.2 平均路由跳數比

平均路由跳數比（Average Access Hop Ratio，AAHR）表示用戶每個請求平均需要的路由跳數，用公式表達為：

其中di表示從用戶到達服務器或緩存節點的跳數，Di表示每一次請求都從服務器獲取數據所需的跳數，M代表總的請求次數。AAHR越小，流量開銷越小，緩存策略的效果越好。

3.3 結果分析

3.3.1 Zipf 參數對緩存命中率和路由跳數比的影響

圖1 和圖2 展示了在Zipf 參數變化的情況下，FIFO、LRU、LFU 以及本文提出方法的平均緩存命中率和路由跳數比。由圖1 可以看出，隨著齊普夫參數的增加，所有緩存替換策略下的平均緩存命中都在不斷提高。這是因為Zipf 參數的增加表示內容請求的局部性越來越高，更多的請求集中在更少的內容上，因此緩存的命中率會不斷提高。

圖1 平均緩存命中率隨Zipf 參數變化

圖2 平均路由跳數比隨Zipf 參數變化

從圖1 可以看出，本文所提方案要好于幾種經典的緩存替換方案，這是因為所提方案會緩存更加流行且預期訪問距離當前時刻更近的數據內容。由圖2 可以看出，隨著Zipf 參數的增大，所有緩存替換策略下請求獲取內容的平均跳數在下降。因為命

中率的增加，內容更多地在緩存節點命中，需要從服務器獲取內容的請求就更少，因此獲取內容的平均跳數也會降低。本文所提方案在平均路由跳數方面的表現也優于其他策略。

3.3.2 緩存大小對緩存命中率和路由跳數比的影響

圖3 和圖4 展示了在緩存空間大小變化的情況下各項指標的變化情況。圖3 展示了隨著緩存空間的增大，緩存命中率不斷提高。更大的緩存空間可以緩存更多的內容，提高緩存中內容數據的多樣性，因此緩存的命中率也在不斷提高。從圖3 也可以看出，緩存命中率并沒有隨著緩存空間的增大線性增長，而是呈現出“對數”式增長的趨勢，說明單純不斷增加緩存空間對提升命中率的作用將是有限的。在緩存空間大小變化時，本文所提方案也優于其他緩存替換方法。圖4 展示了隨著緩存大小的增加，獲取內容所需的平均路由跳數在不斷下降，所提方法在平均路由跳數方面也表現更好。

圖3 平均緩存命中率隨緩存空間大小變化

圖4 平均路由跳數比隨緩存空間大小變化

4 結語

緩存在內容中心網絡中起到不可或缺的作用，合理高效地使用有限的緩存空間并提高緩存所帶來的收益是緩存策略的根本目的。本文從內容在未來被請求的概率越大、被請求的時間距離當前時刻越近則內容的保留價值就越大這一思想出發，提出了考慮內容流行度和預期時間至當前時刻時間距離的緩存替換策略。仿真結果表明，該方案可以提升緩存命中率，降低獲取內容的平均跳數。下一步將在本文的基礎上，結合不同的緩存決策策略進行研究。