基于內(nèi)容預(yù)期價值的內(nèi)容中心網(wǎng)絡(luò)緩存替換策略*

王 珂，江凌云，董 唱

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

0 引言

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

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

1 相關(guān)工作

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

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

2 基于內(nèi)容預(yù)期價值的緩存替換策略

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

2.1 內(nèi)容流行度

內(nèi)容流行度的表示方式有很多種。最早的LFU是利用內(nèi)容被訪問的次數(shù)來表達(dá)流行度。內(nèi)容被訪問的次數(shù)越高，則表示內(nèi)容的流行度越大。但是，這種表示方式?jīng)]有考慮內(nèi)容被訪問的時間性，因此若用來表示內(nèi)容在近期的流行度就未必準(zhǔn)確。除此之外，文獻(xiàn)[12]提出了對內(nèi)容中心網(wǎng)絡(luò)中的幾種流行度表示方式：

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

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

2.2 內(nèi)容預(yù)期訪問時間

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

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

2.3 內(nèi)容預(yù)期價值的定義

根據(jù)2.2 節(jié)，已經(jīng)預(yù)測出數(shù)據(jù)內(nèi)容下一次被請求的時間，則可以計算出內(nèi)容下一次被訪問時間距離現(xiàn)在時刻的時間距離，即：

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

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

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

2.4 算法實現(xiàn)

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

數(shù)據(jù)包轉(zhuǎn)發(fā)到緩存節(jié)點，根據(jù)緩存決策策略。若不對該內(nèi)容進(jìn)行緩存，則直接對數(shù)據(jù)包根據(jù)PIT表轉(zhuǎn)發(fā)；若決定對該內(nèi)容進(jìn)行緩存，則判斷數(shù)據(jù)來源判斷是否需要對該內(nèi)容進(jìn)行過濾。若符合緩存到CS 中的條件時，依據(jù)內(nèi)容預(yù)期價值，將具有最小預(yù)期價值的內(nèi)容替換掉緩存該內(nèi)容，并對該內(nèi)容的4 個標(biāo)簽進(jìn)行初始化。

同時，當(dāng)請求在緩存節(jié)點命中時，緩存節(jié)點對內(nèi)容中的本周期內(nèi)命中次數(shù)加1，并更新加權(quán)平均訪問時間間隔和最近一次訪問時間。

3 仿真與分析

3.1 仿真設(shè)計

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

3.2 性能指標(biāo)

3.2.1 緩存節(jié)點的平均命中率

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

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

3.2.2 平均路由跳數(shù)比

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

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

3.3 結(jié)果分析

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

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

圖1 平均緩存命中率隨Zipf 參數(shù)變化

圖2 平均路由跳數(shù)比隨Zipf 參數(shù)變化

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

中率的增加，內(nèi)容更多地在緩存節(jié)點命中，需要從服務(wù)器獲取內(nèi)容的請求就更少，因此獲取內(nèi)容的平均跳數(shù)也會降低。本文所提方案在平均路由跳數(shù)方面的表現(xiàn)也優(yōu)于其他策略。

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

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

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

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

4 結(jié)語

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