基于節(jié)點動態(tài)內(nèi)容流行度的緩存管理策略

張 果,汪斌強(qiáng),張 震,梁超毅

(1.國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,河南鄭州 450002;2.解放軍信息工程大學(xué),河南鄭州450001)

?

基于節(jié)點動態(tài)內(nèi)容流行度的緩存管理策略

張 果1,汪斌強(qiáng)1,張 震1,梁超毅2

(1.國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,河南鄭州 450002;2.解放軍信息工程大學(xué),河南鄭州450001)

針對命名數(shù)據(jù)網(wǎng)絡(luò)中節(jié)點無法感知內(nèi)容流行度變化的缺陷,提出了基于緩存內(nèi)容流行度動態(tài)變化的內(nèi)容管理策略.將緩存分為主緩存(Primary Cache,PC)和副緩存(Secondary Cache,SC),分別用于識別和保護(hù)流行內(nèi)容;采用標(biāo)準(zhǔn)布魯姆過濾器(Standard Bloom Filter,SBF)過濾流行內(nèi)容請求;引入滑動時間窗口算法和HASH表對副緩存內(nèi)容進(jìn)行細(xì)粒度的統(tǒng)計分析,進(jìn)而管理緩存內(nèi)容.仿真顯示,與現(xiàn)有算法相比,該策略以增加少量復(fù)雜度為代價,延長高流行度內(nèi)容的緩存駐留時間,提高了緩存命中率,減輕了服務(wù)器負(fù)載,并具有可擴(kuò)展性,具備單線路40Gbit/s的報文處理能力.

命名數(shù)據(jù)網(wǎng)絡(luò);動態(tài)內(nèi)容流行度;線速;內(nèi)容管理

1 引言

信息中心網(wǎng)絡(luò)(Information-Centric Networking,ICN)[1]以內(nèi)容為網(wǎng)絡(luò)通信的主體,關(guān)注用戶和應(yīng)用通信需求的具體內(nèi)容,是一種新的未來網(wǎng)絡(luò)架構(gòu).命名數(shù)據(jù)網(wǎng)絡(luò)(Named Data Networking,NDN)[2]是一個典型的ICN體系結(jié)構(gòu).內(nèi)容緩存技術(shù)是NDN的研究重點之一.

當(dāng)前,緩存技術(shù)的研究主要集中在緩存決策[3,4]制定,即選取合理的緩存位置和緩存時機(jī).而針對緩存替換算法的研究較少,在節(jié)點內(nèi)多采用基于LRU(Least Recently Used)[5,6]緩存替換算法.文獻(xiàn)[7]指出,LRU算法復(fù)雜度低,可滿足節(jié)點線速處理需求.文獻(xiàn)[8]設(shè)計了LFU(Least Frequently Used)的實現(xiàn)方案,分析了復(fù)雜度,并提出了改進(jìn)方案.文獻(xiàn)[9]討論分析了LRU和MRU(Most Recently Used)在NDN中的具體應(yīng)用和性能.

內(nèi)容流行度是緩存內(nèi)容替換時的重要參考.文獻(xiàn)[10]采用線型拓?fù)浣Y(jié)構(gòu),通過泊松過程建模,提出基于流行度的緩存替換策略,通過減少高流行度內(nèi)容存儲,增加內(nèi)容的多樣性來提高命中率,該算法是在特定網(wǎng)絡(luò)環(huán)境下的研究,適用范圍有限.文獻(xiàn)[11]針對LRU和LFU的不足,提出了RUF(Recently Used Frequency)算法.RUF考慮了流行度的動態(tài)特性,逐包統(tǒng)計信息同時將其存于hash表,但是沒有給出存儲解決方案,實際網(wǎng)絡(luò)環(huán)境中,該方法會導(dǎo)致hash表急劇膨脹而無法有效應(yīng)用.文獻(xiàn)[12]基于靜態(tài)數(shù)據(jù)集研究了youtube的數(shù)據(jù)流行度曲線,采用擬合函數(shù)對該網(wǎng)站視頻內(nèi)容流行度進(jìn)行分析估計,該方法僅能用于仿真實驗,不能在實際中開展應(yīng)用.

文獻(xiàn)[13]指出,在緩存系統(tǒng)中,線速處理是對內(nèi)容索引表項操作的要求,內(nèi)容可以存儲在低速緩存中.因此,基于當(dāng)前硬件存貯介質(zhì)處理速度[14],可考慮設(shè)計滿足線速處理的節(jié)點緩存管理策略提高緩存命中率,從而改善緩存性能.

本文從降低流行內(nèi)容的緩存替換頻度和延長內(nèi)容在節(jié)點駐留時間的角度,設(shè)計基于節(jié)點動態(tài)內(nèi)容流行度的緩存管理(Dynamical Content Popularity for Cache Management,DCPCM)策略.首先將緩存劃分為主緩存(Primary Cache,PC)和副緩存(Secondary Cache,SC),分別用于識別和保護(hù)高流行度內(nèi)容;采用滑動窗口算法,設(shè)計基于標(biāo)準(zhǔn)布魯姆過濾器(Standard Bloom Filter,SBF)和HASH表的線速流行度監(jiān)測機(jī)制.在不影響命中率的前提下,對算法進(jìn)行改進(jìn),并做了理論分析探討.

2 動態(tài)內(nèi)容流行度監(jiān)測

2.1 節(jié)點緩存內(nèi)容動態(tài)流行度監(jiān)測架構(gòu)

節(jié)點緩存內(nèi)容動態(tài)流行度監(jiān)測架構(gòu)分為動態(tài)監(jiān)測和內(nèi)容緩存兩個部分,如圖1所示.動態(tài)監(jiān)測部分由SBF和HASH表組成;內(nèi)容緩存劃分為PC和SC,PC用于緩存和識別流行內(nèi)容,SC用作存儲已識別的流行內(nèi)容.PC和SC存儲內(nèi)容索引管理均采用雙向鏈表實現(xiàn),PC鏈表內(nèi)采用LRU算法,SC鏈表使用常用的雙向鏈表管理方法.為方便后端運算,興趣包(Interest Packet)或數(shù)據(jù)包(Data Packet)到達(dá)時,先進(jìn)行hash計算,生成內(nèi)容索引,需要指出的是,同一內(nèi)容的興趣包和數(shù)據(jù)包生成的內(nèi)容索引相同.我們分為三個部分來描述整個架構(gòu):內(nèi)容流行度動態(tài)監(jiān)測、PC管理策略和SC管理策略.

內(nèi)容流行度動態(tài)監(jiān)測:當(dāng)興趣包到達(dá)時,先進(jìn)行hash計算,生成內(nèi)容索引,然后查詢SBF,若命中,則表示該內(nèi)容為流行項.然后檢測HASH(為與前文區(qū)分,此處大寫)表是否存在該內(nèi)容項,若存在直接將對應(yīng)的計數(shù)值加1;若不存在,創(chuàng)建對應(yīng)表項,計數(shù)值置為1.若查詢SBF未命中,則丟棄該內(nèi)容索引.

PC管理策略:為方便描述,按照興趣包和數(shù)據(jù)包的處理流程來說明該部分的處理流程.當(dāng)興趣包到達(dá)時,分別在SC和PC中查詢內(nèi)容索引值.若在PC鏈表中匹配命中,則返回數(shù)據(jù),該內(nèi)容索引對應(yīng)的計數(shù)值加1,同時檢查訪問頻次是否到達(dá)閾值,若達(dá)到閾值,在SC鏈表未滿的情況下,將該內(nèi)容索引插入SBF和SC,將PC內(nèi)的內(nèi)容索引刪除;若SC鏈表已滿,該內(nèi)容索引仍留在PC鏈表內(nèi),按LRU規(guī)則移動至PC鏈表頭部.若在SC鏈表中匹配命中,返回數(shù)據(jù)即可.

若興趣包生成的內(nèi)容索引在PC鏈表和SC鏈表中均未命中,興趣包經(jīng)過PIT表和FIB表轉(zhuǎn)發(fā)給下一個節(jié)點.當(dāng)返回數(shù)據(jù)經(jīng)過當(dāng)前節(jié)點時,采用CEE[2](Caching Everything Everywhere)緩存策略,將數(shù)據(jù)存入PC,同時將新生成的內(nèi)容索引存入PC鏈表.當(dāng)PC鏈表未滿時,按LRU算法將內(nèi)容索引存入PC鏈表頭部.若PC鏈表已滿,先執(zhí)行LRU算法將內(nèi)容索引存入PC鏈表頭部,然后刪除PC鏈表尾部的內(nèi)容索引.在刪除PC鏈表尾部內(nèi)容索引時:若尾部內(nèi)容索引對應(yīng)的內(nèi)容流行度達(dá)到閾值且SC鏈表未滿,則將內(nèi)容索引插入SBF的同時,將內(nèi)容索引從PC鏈表移動至SC鏈表;否則直接將尾部內(nèi)容索引刪除.

SC管理策略:分為內(nèi)容索引刪除和內(nèi)容索引插入兩個部分.當(dāng)一個監(jiān)測窗口結(jié)束時,基于HASH表統(tǒng)計的內(nèi)容流行度情況,篩選出內(nèi)容流行度低于閾值的內(nèi)容索引集合,將HASH表中對應(yīng)內(nèi)容索引和SC鏈表內(nèi)對應(yīng)的內(nèi)容索引刪除;若所有內(nèi)容索引對應(yīng)的流行度都高于閾值,則不執(zhí)行刪除操作.內(nèi)容索引插入:PC鏈表內(nèi)的內(nèi)容索引對應(yīng)的計數(shù)達(dá)到閾值且SC鏈表未滿時,將其移入SC鏈表,即SC鏈表的內(nèi)容索引插入.內(nèi)容索引插入過程與PC管理策略中內(nèi)容索引移入SC的步驟相同,因此在本部分不再重述.

以上策略利用PC內(nèi)的LRU算法的識別功能,在SC空間允許的情況下,將訪問頻次高的內(nèi)容索引插入SBF,同時將該內(nèi)容索引移動至SC鏈表.當(dāng)興趣包到達(dá)時,能夠利用SBF實現(xiàn)線速過濾,進(jìn)而利用HASH表統(tǒng)計流行度,通過對監(jiān)測窗口內(nèi)緩存內(nèi)容流行度的實時分析,延長流行內(nèi)容在緩存內(nèi)的駐留時間,保護(hù)高流行度內(nèi)容.2.2 流行度監(jiān)測周期

定義1 節(jié)點內(nèi)容流行度是指內(nèi)容在一個確定時長內(nèi)被請求的頻次.那么對某一內(nèi)容f流行度表示為:

p(f)=λT

(1)

其中,T為監(jiān)測時長,λT表示時間T內(nèi)內(nèi)容f被訪問的次數(shù).

T結(jié)束時,根據(jù)統(tǒng)計結(jié)果決定是否刪除SC內(nèi)容.這種算法的優(yōu)勢是實現(xiàn)簡單,統(tǒng)計結(jié)果直觀;缺陷在于割裂了內(nèi)容流行度的連續(xù)性,使統(tǒng)計信息不準(zhǔn)確.監(jiān)測算法要簡單易實現(xiàn),同時兼顧流行度的連續(xù)性,本文引入滑動窗口算法完成流行度統(tǒng)計.

2.2.1 滑動窗口算法

如圖2所示,假定時間窗口WzT由z個時長為T的時隙構(gòu)成,統(tǒng)計每個時隙內(nèi)流行度,同時統(tǒng)計整個窗口內(nèi)容流行度,滑動步長為T.定義如下:

定義2 即時流行度.對定義一稍作改動,內(nèi)容f在第u個時隙Tu內(nèi)的流行度為λu,稱λu為內(nèi)容f在滑動窗口的即時流行度.

定義3 持續(xù)流行度.對于SC內(nèi)某一內(nèi)容f,在滑動窗口WzT內(nèi)的流行度累計值:

(2)

稱為持續(xù)流行度.q表示時間軸上時隙個數(shù),z表示滑動時間窗內(nèi)的時隙個數(shù),時間窗起始時隙Tq-z,終止時隙Tq-1,λq-z是第q-z個時隙(slot)Tq-z內(nèi)的即時流行度.

為便于統(tǒng)計分析,每一個時隙對應(yīng)一個hash表.滑動窗口內(nèi)的z個hash表由一個HASH表管理.一個時隙結(jié)束,根據(jù)流行度排名來更新SC內(nèi)的緩存內(nèi)容.需要指出的是,采用滑動窗口算法后,按照2.1節(jié)中SC管理策略,時隙結(jié)束篩選刪除內(nèi)容時,求出內(nèi)容相對應(yīng)的持續(xù)流行度的z個時隙的平均值與流行度閾值作比較,作為選取刪除內(nèi)容的標(biāo)準(zhǔn).

3 內(nèi)容替換策略分析

3.1 內(nèi)容流行度統(tǒng)計策略分析

在2.1節(jié)算法約定,只要滿足移動內(nèi)容索引條件,就要調(diào)整PC鏈表、SC鏈表和SBF.從算法設(shè)計上說,這種方式使HASH表能夠監(jiān)測滑動時間窗口內(nèi)流行內(nèi)容的流行度變化,為SC管理提供依據(jù).但是會導(dǎo)致使SBF統(tǒng)計的內(nèi)容索引數(shù)量多,誤判概率增大;PC和SC鏈表項頻繁操作,增加系統(tǒng)消耗,影響處理速度.

緩存內(nèi)容動態(tài)流行度監(jiān)測的目的是保護(hù)監(jiān)測時隙內(nèi)流行度有波動的內(nèi)容,進(jìn)而提高緩存命中率.分析發(fā)現(xiàn),按照LRU算法思想,高流行度內(nèi)容因為被訪問頻繁,能夠長期留存在LRU鏈表中,不監(jiān)測該類內(nèi)容,不影響緩存命中率.當(dāng)PC鏈表內(nèi)的內(nèi)容索引更新時,那些因短期內(nèi)未被訪問的流行內(nèi)容索引被替換,才會降低緩存命中率.因此從減輕系統(tǒng)處理壓力的角度考慮,對算法改進(jìn)如下:興趣包到達(dá)且在PC命中內(nèi)容時,PC鏈表僅執(zhí)行LRU算法將內(nèi)容索引移動至PC鏈表頭部,不再檢測其流行度閾值、插入SBF和向SC轉(zhuǎn)移;其它步驟不變.后續(xù)探討均以改進(jìn)算法為基礎(chǔ).

3.2 緩存分配分析

流行度閾值δth和流行內(nèi)容數(shù)目y的關(guān)系

在監(jiān)測時隙T內(nèi),到達(dá)節(jié)點的興趣包總數(shù)為Ntotal時,請求內(nèi)容my的興趣包數(shù)目nmy=Ntotal·p(y),令δth=nmy,則有:

δth=nmy

=Ntotal·p(y)

(3)

PC鏈表長度和流行度閾值δth的關(guān)系

在一個監(jiān)測時隙T內(nèi),到達(dá)節(jié)點的Ntotal個興趣包中,請求的流行內(nèi)容有y個,內(nèi)容流行度閾值為δth,PC鏈表是長度為L的雙向鏈表,按LRU策略執(zhí)行鏈表節(jié)點操作.假定每隔w個興趣包(與新興趣包相比,該處興趣包是指其請求內(nèi)容已在當(dāng)前節(jié)點緩存),引入一個新的興趣包,新的興趣包的應(yīng)答數(shù)據(jù)到達(dá)節(jié)點時將淘汰PC鏈表尾部的內(nèi)容索引.內(nèi)容my在Zipf分布中流行度排名為y,在監(jiān)測時隙內(nèi)被訪問的次數(shù)為剛好為δth(由流行度閾值δth和流行內(nèi)容數(shù)目y的關(guān)系可知,內(nèi)容my被請求δth次的概率為p(y)),則在連續(xù)w個興趣包中,內(nèi)容my不被請求的概率服從超幾何分布:

(4)

那么內(nèi)容my被轉(zhuǎn)移至SC的概率Pmove(my)為:

(5)

當(dāng)Ntotal遠(yuǎn)大于w時,超幾何分布可用二項分布近似替代[15]:

(6)

由式(5)和式(6)可得:

(7)

持續(xù)流行的內(nèi)容在監(jiān)測時隙內(nèi)到達(dá)速率高,請求持續(xù)時間長.任意閾值大于δth的內(nèi)容項,被移動至SC內(nèi)的概率為Pmove(my),當(dāng)w>L時,內(nèi)容my被移動至SC的最大概率為:

(8)

那么,當(dāng)流行內(nèi)容數(shù)目為y時,被移動至SC的內(nèi)容數(shù)目最多為:

(9)

公式(8)是在閾值和興趣包總數(shù)目一定的情況下,流行內(nèi)容被移動至SC的最大概率,如圖4所示,鏈表長度越大,流行內(nèi)容移動概率越小.但是在實際網(wǎng)絡(luò)環(huán)境中,PC鏈表長度L受空間和硬件處理速度的限制,和實際興趣包數(shù)目相比,L都顯得過小,因此通過劃分緩存的方法延長內(nèi)容在緩存的駐留時間是可行的.公式(9)是參數(shù)確定時,流行內(nèi)容被替換的最大數(shù)量.公式(8)和(9)可作為PC和SC劃分的理論參考.

3.3 SBF誤差分析

文獻(xiàn)[16]給出了SBF的誤判概率的表達(dá)式:

(10)

其中,n為元素個數(shù),m為SBF向量V的長度,k為hash函數(shù)的個數(shù).

圖5給出了hash函數(shù)個數(shù)和SBF誤差的關(guān)系圖,誤判概率隨著hash函數(shù)個數(shù)的增加而增加.圖6是誤判概率和m/n變化關(guān)系圖,可以看出,當(dāng)m/n增大時,誤判概率隨之減小.

令x(k)=k·ln(1-e-kn/m),當(dāng)?x(k)/?k=0時,k0=ln2·m/n,公式(10)有最小值:

fSBF(n,m,k)min=(0.5)k0

(11)

公式(11)給出了使誤判概率達(dá)到最小時,SBF中hash函數(shù)數(shù)目k,SBF長度m和存儲內(nèi)容索引數(shù)目n的關(guān)系.SBF長度和hash函數(shù)個數(shù)確定后,當(dāng)統(tǒng)計的內(nèi)容索引數(shù)目達(dá)到n時,再添加內(nèi)容就會使誤判概率增大,此時需要考慮SBF的擴(kuò)展,可通過增加一個新的同樣大小的SBF來統(tǒng)計新的流行內(nèi)容索引.在實際應(yīng)用當(dāng)中,根據(jù)命名數(shù)據(jù)網(wǎng)絡(luò)內(nèi)容請求分布特征,流行度高的內(nèi)容僅占內(nèi)容總量的少數(shù),所以可以預(yù)先設(shè)定SBF大小,能夠容納一定數(shù)量的流行內(nèi)容索引即可.

3.4 HASH表約束

SBF存儲了滑動窗口內(nèi)的流行內(nèi)容索引,而SBF不具備刪除能力,不再流行的內(nèi)容索引仍會通過SBF進(jìn)入HASH表,導(dǎo)致HASH表膨脹.

解決HASH表膨脹問題有兩個途徑:(1)、PC鏈表將內(nèi)容索引插入SBF時,也將其插入HASH表,若后續(xù)該內(nèi)容流行度降低,則將其索引刪除.當(dāng)SBF過濾出流行度內(nèi)容時,在插入HASH表之前先查找,若HASH表內(nèi)不包含則丟棄,反之則插入HASH表,經(jīng)過雙重過濾可防止HASH表膨脹.缺陷是HASH表本身過大,在實際應(yīng)用中不能在高速緩存中實現(xiàn),而且從PC鏈表插入HASH表,增加了操作復(fù)雜度.(2)、根據(jù)SC大小來設(shè)置HASH表的大小,結(jié)合3.2節(jié)的分析,結(jié)合公式(8)可得到被替換出的流行內(nèi)容所占的比值,然后確定HASH表大小.在一個時隙結(jié)束時,HASH表對內(nèi)容索引進(jìn)行整理,清除干擾項,從而防止HASH表膨脹.本文采用第二個途徑解決HASH表膨脹問題.3.5 動態(tài)流行度處理速度及監(jiān)測靈敏度

文獻(xiàn)[13]指出,NDN路由器緩存的處理速度主要取決于存儲介質(zhì)的訪存速度,文獻(xiàn)[14]分析了NDN運行的實際需求和當(dāng)前硬件存儲介質(zhì)處理速度:其中SRAM訪問速度達(dá)到0.45ns,最大容量210M;RLDRAM訪問速度15ns,最大容量2G;DRAM讀取速度為55ns,最大容量為10G.為滿足線速處理需求,將PC、SC鏈表和SBF部署在SRAM中,HASH表部署在RLDRAM中.實際硬件設(shè)計中,興趣包到達(dá)節(jié)點后,PC、SC鏈表和SBF可以實現(xiàn)并行操作,而當(dāng)PC、SC鏈表、SBF和HASH表之間存在交互時,處理時延會增加.

幾個處理流程分別是:(1)興趣包到達(dá)→PC命中→移動至PC鏈表頭部.(2)興趣包到達(dá)→SBF命中→HASH表.(3)興趣包到達(dá)→SC命中.(4)數(shù)據(jù)包到達(dá)→PC表頭部→PC表尾巴判斷超過閾值→寫入SBF和移動至SC(在實際中可并行處理).

由表1知,當(dāng)SBF中hash函數(shù)數(shù)目k=6時,流程(1)需要18.6ns;流程(2)需要15.9ns;流程(3)需要0.9ns;流程(4)需要4.5ns.在40Gbit/s(OC-768)鏈路上,假設(shè)報文平均長度為1000bit,鏈路滿載情況下,大約25ns到達(dá)一個興趣包.本文算法能夠滿足40Gbit/s(OC-768)的鏈路處理需求.

表1 一次操作時間復(fù)雜度

4 仿真實驗與性能分析

因為NDN網(wǎng)絡(luò)并未在實際網(wǎng)絡(luò)中部署,仿真實驗數(shù)據(jù)來源有兩種:基于現(xiàn)有的IP網(wǎng)絡(luò)數(shù)據(jù),通過解析轉(zhuǎn)化,模擬NDN通信;基于ndnSIM[17]仿真平臺,采用Zipf函數(shù)模擬數(shù)據(jù)進(jìn)行仿真.本文仿真基于ndnSIM仿真平臺來驗證算法的有效性和適用性.

4.1 仿真試驗環(huán)境和性能評價指標(biāo)

ndnSIM實現(xiàn)了NDN架構(gòu)中的基本數(shù)據(jù)單元結(jié)構(gòu)和路由轉(zhuǎn)發(fā)流程,并支持路由、轉(zhuǎn)發(fā)和緩存算法的擴(kuò)展.在商用服務(wù)器(2.70 GHz CPU,RAM 2.0GB)上搭建基于NS-3的開源平臺ndnSIM,然后構(gòu)建實驗環(huán)境.

網(wǎng)絡(luò)環(huán)境設(shè)計 用GT-ITM的Locality模型生成包含50個路由節(jié)點的平面網(wǎng)絡(luò)拓?fù)?網(wǎng)絡(luò)中內(nèi)容塊(chunk)總數(shù)為10000個,以1～10000依次排序,內(nèi)容大小設(shè)為10Kbytes.節(jié)點緩存容量一致,CS(Content Store)均設(shè)為10M(根據(jù)實驗需要可再做調(diào)整),可容納1000個內(nèi)容塊,鏈路帶寬10Mbps.在網(wǎng)絡(luò)中部署2個內(nèi)容服務(wù)器,負(fù)責(zé)內(nèi)容對象的存儲和發(fā)布,各服務(wù)器隨機(jī)存儲5000個內(nèi)容塊,并在網(wǎng)絡(luò)邊緣節(jié)點隨機(jī)選取2個節(jié)點與內(nèi)容服務(wù)器直接相連.其余節(jié)點均作為用戶接入節(jié)點.

性能評價指標(biāo) (1)緩存命中率(Cache Hit Ratio,CHR),是網(wǎng)絡(luò)中節(jié)點緩存內(nèi)容響應(yīng)興趣包數(shù)量與總的興趣包的比值;(2)服務(wù)器平均負(fù)載(Average Server Load,ASL),即單位時間內(nèi)到達(dá)服務(wù)器的興趣包數(shù)量.

4.2 性能分析

4.2.1 與現(xiàn)有的替換策略仿真對比

圖7是在節(jié)點緩存空間與內(nèi)容塊數(shù)量之比(cache size/catalog size)不同時,四種策略的緩存命中率變化情況.當(dāng)二者比值為10%時,DCPCM策略的緩存命中率優(yōu)于其它三種策略.隨著比值的增大,DCPCM、LRU、MRU和LFU四種策略的緩存命中率之間的差別越來越小,這是因為隨著緩存空間的增大,能夠留存在LRU、MRU和LFU緩存中的內(nèi)容塊越來越多,從而提高了緩存命中率,此時DCPCM策略延長緩存內(nèi)容駐留時間的優(yōu)勢變得越來越小.而在實際網(wǎng)絡(luò)中,內(nèi)容索引項的處理速度受硬件高速處理緩存(SRAM)速度和空間的限制,緩存空間也受硬件存儲介質(zhì)的約束.文獻(xiàn)[14]指出可提供的存儲空間大小為10G,文獻(xiàn)[13]指出,緩存空間和內(nèi)容條目的比值一般為10-5,實際應(yīng)用中,節(jié)點要以線速處理大量的興趣包和數(shù)據(jù)包,緩存空間與內(nèi)容塊數(shù)量的比值更小,在這種情況下,DCPCM策略的應(yīng)用優(yōu)勢比較明顯.

圖8是節(jié)點緩存空間與內(nèi)容塊數(shù)量之比變化時,服務(wù)器平均負(fù)載變化情況,當(dāng)二者比值為10%時,DCPCM優(yōu)于LRU、MRU和LFU.隨著比值的增大,服務(wù)器平均負(fù)載變化情況趨于相同.這是因為緩存空間不斷增大,三種算法緩存的流行內(nèi)容幾乎相同,使得到達(dá)服務(wù)器的興趣包數(shù)目趨同,因此三種算法的效果相差不大.而在實際網(wǎng)絡(luò)中,在緩存空間受限的條件下,DCPCM能夠有效延長流行內(nèi)容在緩存內(nèi)的駐留時間,進(jìn)而減輕服務(wù)器負(fù)載.

圖9是內(nèi)容流行度突變時緩存命中率的變化情況.當(dāng)流行內(nèi)容突然發(fā)生變化時,DCPCM策略能夠快速做出反應(yīng),使新流行內(nèi)容替換緩存內(nèi)容,從而保證緩存命中率.這是因為在同樣大小的緩存情況下,DCPCM策略由于緩存內(nèi)分區(qū),按照預(yù)設(shè)的流行度閾值,能夠快速跟蹤流行度變化情況,同時將內(nèi)容移至副緩存保護(hù)起來,從而快速提升緩存命中率,在本文實驗中反應(yīng)時間為3s.而LRU和MRU由于缺乏保護(hù)機(jī)制,對內(nèi)容流行度的變化反應(yīng)較為緩慢.LFU算法缺乏對流行度較高的內(nèi)容的管理,過時的流行內(nèi)容無法從緩存內(nèi)清除,因而對內(nèi)容流行度的短暫變化幾乎不敏感.

4.2.2 代價開銷

(1)空間復(fù)雜度

空間復(fù)雜度用存儲所占的比特數(shù)來衡量,與LRU、MRU、LFU相比,DCPCM增加了SBF和HASH表,從而增加了空間消耗.

在仿真實驗中,10000個內(nèi)容塊中流行項為1000個,節(jié)點緩存可存儲1000個內(nèi)容塊.那么SBF存儲內(nèi)容索引最多為1000個,當(dāng)m/n=20,k=6時,誤判概率為3×10-4,能夠滿足統(tǒng)計需求,此時SBF消耗的空間為20000bit.當(dāng)SC占比為0.2時,SC可存儲200個內(nèi)容塊.HASH表項的大小與SC大小有關(guān),因此考慮內(nèi)容在滑動窗口內(nèi)變化情況,將內(nèi)容表項大小設(shè)置為SC的2倍,即400個內(nèi)容項.若一條hash值及其對應(yīng)統(tǒng)計值占64bit,那么HASH表大小為25600bit,足夠存儲相應(yīng)數(shù)量的內(nèi)容塊及其流行度.與LRU、MRU和LFU相比,DCPCM增加了45600bit約5.55M空間消耗.

(2)時間復(fù)雜度

3.4節(jié)分析了內(nèi)容流行度算法操作流程,DCPCM最長的操作時間為18.6ns.LRU,MRU的操作復(fù)雜度為O(2),若在SRAM上實現(xiàn)雙向鏈表,完成操作需要0.9ns.由文獻(xiàn)[8]的改進(jìn)算法可使LFU時間復(fù)雜度為O(1),即0.45ns.

4.3 適應(yīng)性討論

圖10是SC占比不同時,節(jié)點緩存空間與內(nèi)容塊數(shù)量比變化時緩存命中率的變化情況.二者比值為2%時,SC占比越大,緩存命中率就越高.在這種情況下,SC占比越大,受保護(hù)的內(nèi)容就越多,圖10中所示當(dāng)SC占比為0.3時,緩存命中率明顯增大.過度增加SC占比,使得LRU鏈表長度L變短,由公式(8)可知,這種情況下使得PC鏈表內(nèi)替換率增大,增加SC的管理消耗.當(dāng)緩存和內(nèi)容總條目比值逐漸增大時,SC占比變化對平均緩存命中率影響越來越小.這是因為隨著緩存空間的增大,緩存內(nèi)容數(shù)量增加,從而提高了緩存命中率.在實際網(wǎng)絡(luò)環(huán)境中,因為緩存空間和SC管理開銷的限制,需要選擇合理的SC占比才能有效改善緩存系統(tǒng)性能.

表2是在SC占比、節(jié)點緩存空間與內(nèi)容塊數(shù)目比和滑動時間窗一定的條件下,流行度閾值變化對緩存命中率和服務(wù)器平均負(fù)載的影響.當(dāng)閾值過大時,進(jìn)入SC的內(nèi)容就較少,SC不能被充分利用,導(dǎo)致緩存命中率降低,服務(wù)器平均負(fù)載增加.流行度閾值較小時,SC內(nèi)容頻繁替換,導(dǎo)致緩存命中率降低和服務(wù)器平均負(fù)載升高.

表2 流行度閾值變化時的情況(滑動窗口8s,SC占比0.2,

緩存空間與內(nèi)容塊數(shù)目比10%)

流行度閾值(item)2004006008001000緩存命中率(%)42.743.550.147.646.5服務(wù)器平均負(fù)載(pkt/sec)389.3385.2382.9391.6398.6

表3是在SC占比、節(jié)點緩存空間與內(nèi)容塊數(shù)目比和流行內(nèi)容閾值一定的情況下,滑動窗口大小變化對緩存命中率和服務(wù)器平均負(fù)載的影響.窗口過大時,流行度累計值過大,使得對流行度的變化變得不夠敏感,導(dǎo)致不能及時將“老化”內(nèi)容從SC內(nèi)剔除,從而影響了緩存命中率和服務(wù)器平均負(fù)載.窗口過小時,流行內(nèi)容的流行度區(qū)分度不高,使得內(nèi)容頻繁替換,導(dǎo)致緩存命中率降低.當(dāng)滑動窗為2s時,緩存內(nèi)容替換過于頻繁,緩存命中率降低,而頻繁的替換使得仿真時間內(nèi)的緩存內(nèi)容多樣化,因而出現(xiàn)了緩存命中率降低,服務(wù)器平均負(fù)載降低的情況.

表3 滑動窗口變化時的情況(閾值600,SC占比0.2,

緩存空間與內(nèi)容塊數(shù)目比10%)

滑動窗口(sec)2481632緩存命中率(%)44.246.750.147.348.1服務(wù)器平均負(fù)載(pkt/sec)379.7384.1382.9387.4394.3

5 結(jié)論

針對NDN節(jié)點緩存替換策略無法感知長期流行內(nèi)容的不足,從線速處理的角度出發(fā),設(shè)計了基于動態(tài)內(nèi)容流行度的節(jié)點緩存管理策略.將節(jié)點緩存分為PC和SC兩部分,PC用于識別流行內(nèi)容,采用SBF過濾流行內(nèi)容和HASH表統(tǒng)計內(nèi)容流行度變化,基于統(tǒng)計信息來管理SC內(nèi)的流行內(nèi)容,結(jié)合實際,對DCPCM策略改進(jìn)探討,分析了緩存分區(qū)的理論依據(jù).仿真表明,在不影響緩存性能的基礎(chǔ)上實現(xiàn)了流行內(nèi)容的線速、動態(tài)監(jiān)測分析,為緩存內(nèi)容管理提供了有效的流行度變化信息,延長高流行度內(nèi)容在緩存節(jié)點內(nèi)的駐留時間,從而提高緩存命中率,提升緩存網(wǎng)絡(luò)性能.本文的探討局限于CEE策略下的緩存管理方法,設(shè)計的動態(tài)估計方法有待進(jìn)一步優(yōu)化.在后續(xù)研究中,考慮將緩存決策和緩存替換結(jié)合,來改進(jìn)緩存系統(tǒng)的性能.

[1]Ahlgren B,Dannewitz C,Imbrenda C,et al..A survey of information-centric networking[J].IEEE Communication Magazine,2012,50(7):26-36.

[2]V Jacobson,D K Smetters,J D Thornton,M F Plass,N H Briggs,R L Braynard.Networking named content[A].Proceedings of the 5th international conference on Emerging networking experiments and technologies[C].NY,USA:2009.1-12.

[3]Wang J M,Zhang J,Bensaou B.Intra-AS cooperative caching for content-centric networks[A].Proceedings of the ACM SIGCOMM Workshop on Information-Centric Networking[C].Hong Kong,China:2013.61-66.

[4]Saino L,Psaras I,Pavlou G.Hash-routing schemes for information centric networking[A].Proceedings of the ACM SIGCOMM Workshop on Information-Centric Networking[C].Hong Kong,China:2013.27-32.

[5]S Podlipnig,L Boszormenyi.A survey of web cache replacement strategies[J].Acm Computing Surveys,2003,35(4):374-398.

[6]Jelenkovi′c P R,Radovanovi′c A.Least-recently-used caching with dependent requests[J].Theoretical Computer Science,2002,326(326):293-327.

[7]G Zhang,Y Li,T Lin.Caching in information centric networking:A survey[J].Computer Networks,2013,57(16):3128-3141.

[8]Ketan Shah,Anirban Mitra,Dhruv Matani.An O(1) algorithm for implementing the LFU cache eviction scheme[R/OL].http://dhruvbird.com/lfu.pdf.2010-08-16.

[9]K Katsaros,G Xylomenos,G C Polyzos.MultiCache:An overlay architecture for information-centric networking[J].Computer Networks,2011,55(4):936-947.

[10]朱軼,糜正琨,王文鼐.一種基于內(nèi)容流行度的內(nèi)容中心網(wǎng)絡(luò)緩存概率置換策略[J].電子與信息學(xué)報,2013,35(6):1305-1310.

Zhu Yi,Mi Zheng-Kun,Wang Wen-Nai.A cache probability replacement policy based on content popularity in content centric networks[J].Journal of Electronics and Information Technology,2013,35(6):1305-1310.(in Chinese)

[11]S J Kang,S W Lee,Y B Ko,A recent popularity based dynamic cache management for content centric networking[A].Proceedings of the International Conference on Ubiquitous & Future Networks[C].Phuket,Thailand:2012.219-224.

[12]S Traverso,M Ahmed,M Garetto,P Giaccone,E Leonardi,S Niccolini.Temporal locality in today's content caching:why it matters and how to model It[J].Acm Sigcomm Computer Communication Review,2013,43(5):5-12.

[13]G Rossini,D Rossi.Caching performance of content centric networks under multi-path routing (and more)[R/OL].http://perso.telecom-paristech.fr/～drossi/paper/rossi11ccn-techrep1.pdf.2015-04-15.

[14]D Perino and M Varvello.A reality check for content centric networking[A].Proceedings of the ACM SIGCOMM workshop on Information-centric networking[C].NY,USA:2011.44-49.

[15]《現(xiàn)代應(yīng)用數(shù)學(xué)手冊》編委會.現(xiàn)代應(yīng)用數(shù)學(xué)手冊:概率統(tǒng)計與隨機(jī)過程卷[M].北京:清華大學(xué)出版社,1999.74-75.

[16]A Broder,M Mitzenmacher.Network applications of bloom filters:A survey[J].Internet Mathematics,2003,1(4):485-509.

[17]S Mastorakis,A Afanasyev,I Moiseenko,L Zhang.NdnSIM 2.0:A new version of the NDN simulator for NS-3[R/OL].http://named-data.net/techreports.html.2015-01-27.

[18]Guo S,Xie H Y,Shi G.Collaborative forwarding and caching in content centric networks[A].Proceedings of the IFIP Networking[C].Prague,Czech Republic,2012.41-55.

張 果(通信作者) 男,1985年8月出生,河南南陽人．國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心博士研究生,主要研究方向為新型網(wǎng)絡(luò)體系結(jié)構(gòu),內(nèi)容中心網(wǎng)絡(luò)．

E-mail:guozhang-ndsc@163.com

汪斌強(qiáng) 男,1963年2月出生,安徽安慶人．國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心教授、博士生導(dǎo)師,主要研究方向為寬帶信息網(wǎng)絡(luò),網(wǎng)絡(luò)安全.

E-mail:wbq6301@163.com

張 震 男,1985年出生,博士,講師,研究方向為未來網(wǎng)絡(luò)體系架構(gòu)設(shè)計,網(wǎng)絡(luò)測量.

梁超毅 男,1978年出生,助教,研究方向為未來網(wǎng)絡(luò)體系架構(gòu)設(shè)計,內(nèi)容中心網(wǎng)絡(luò).

A Strategy Based on Dynamical Content Popularity for Cache Management

ZHANG Guo1,WANG Bin-qiang1,ZHANG Zhen1,LIANG Chao-yi2

(1.NationalDigitalSwitchingSystemEngineering&TechnologicalR&DCenter,Zhengzhou,Henan450002,China; 2.PLAInformationEngineeringUniversity,Zhengzhou,Henan450001,China)

To overcome the drawback that nodes in Named Data Networking are insensitive to the change of the content popularity,a dynamic content popularity based cache management strategy is proposed.The strategy divides the cache into primary and secondary one.The former is used to identify popular content and the latter is used to protect it.Standard Bloom Filter is adopted by the strategy to filter popular content requests.The strategy also introduces sliding window and hash table to analyze the content of secondary cache in fine granularity and manage the cache content.Simulation results show that,compared with traditional strategies,our algorithm prolongs the cache residence time of high popularity content,increases cache hit ratio and reduces server loads.Our algorithm is also scalable and has the ability to process packets at 40Gbit/s.

named data networking;dynamical content popularity;line speed;content management

2015-04-16；

2016-01-07；責(zé)任編輯：馬蘭英

國家自然科學(xué)基金創(chuàng)新研究群體項目(No.61521003)；國家973重點基礎(chǔ)研究發(fā)展計劃(No.2012CB315901，No.2013CB329104)；國家自然科學(xué)基金(No.61372121，No.61309019，No.61309020，No.61572519)；國家863高技術(shù)研究發(fā)展計劃(No.2015AA016102，No.2013AA013505)

TP393

A

0372-2112 (2016)11-2704-09

??學(xué)報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.11.020