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

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

?

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

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

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

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

命名數(shù)據(jù)網(wǎng)絡(luò);動(dòng)態(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]是一個(gè)典型的ICN體系結(jié)構(gòu).內(nèi)容緩存技術(shù)是NDN的研究重點(diǎn)之一.

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

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

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

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

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

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

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

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

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

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

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

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

定義1 節(jié)點(diǎn)內(nèi)容流行度是指內(nèi)容在一個(gè)確定時(shí)長(zhǎng)內(nèi)被請(qǐng)求的頻次.那么對(duì)某一內(nèi)容f流行度表示為:

p(f)=λT

(1)

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

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

2.2.1 滑動(dòng)窗口算法

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

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

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

(2)

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

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

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

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

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

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

3.2 緩存分配分析

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

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

δth=nmy

=Ntotal·p(y)

(3)

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

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

(4)

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

(5)

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

(6)

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

(7)

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

(8)

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

(9)

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

3.3 SBF誤差分析

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

(10)

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

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

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

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

(11)

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

3.4 HASH表約束

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)與性能分析

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

4.1 仿真試驗(yàn)環(huán)境和性能評(píng)價(jià)指標(biāo)

ndnSIM實(shí)現(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的開源平臺(tái)ndnSIM,然后構(gòu)建實(shí)驗(yàn)環(huán)境.

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

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

4.2 性能分析

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

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

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

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

4.2.2 代價(jià)開銷

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

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

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

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

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

4.3 適應(yīng)性討論

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

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

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

表3 滑動(dòng)窗口變化時(shí)的情況(閾值600,SC占比0.2,

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

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

5 結(jié)論

針對(duì)NDN節(jié)點(diǎn)緩存替換策略無法感知長(zhǎng)期流行內(nèi)容的不足,從線速處理的角度出發(fā),設(shè)計(jì)了基于動(dòng)態(tài)內(nèi)容流行度的節(jié)點(diǎn)緩存管理策略.將節(jié)點(diǎn)緩存分為PC和SC兩部分,PC用于識(shí)別流行內(nèi)容,采用SBF過濾流行內(nèi)容和HASH表統(tǒng)計(jì)內(nèi)容流行度變化,基于統(tǒng)計(jì)信息來管理SC內(nèi)的流行內(nèi)容,結(jié)合實(shí)際,對(duì)DCPCM策略改進(jìn)探討,分析了緩存分區(qū)的理論依據(jù).仿真表明,在不影響緩存性能的基礎(chǔ)上實(shí)現(xiàn)了流行內(nèi)容的線速、動(dòng)態(tài)監(jiān)測(cè)分析,為緩存內(nèi)容管理提供了有效的流行度變化信息,延長(zhǎng)高流行度內(nèi)容在緩存節(jié)點(diǎn)內(nèi)的駐留時(shí)間,從而提高緩存命中率,提升緩存網(wǎng)絡(luò)性能.本文的探討局限于CEE策略下的緩存管理方法,設(shè)計(jì)的動(dòng)態(tài)估計(jì)方法有待進(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é)報(bào),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é)手冊(cè)》編委會(huì).現(xiàn)代應(yīng)用數(shù)學(xué)手冊(cè):概率統(tǒng)計(jì)與隨機(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月出生,河南南陽人．國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心博士研究生,主要研究方向?yàn)樾滦途W(wǎng)絡(luò)體系結(jié)構(gòu),內(nèi)容中心網(wǎng)絡(luò)．

E-mail:guozhang-ndsc@163.com

汪斌強(qiáng) 男,1963年2月出生,安徽安慶人．國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心教授、博士生導(dǎo)師,主要研究方向?yàn)閷拵畔⒕W(wǎng)絡(luò),網(wǎng)絡(luò)安全.

E-mail:wbq6301@163.com

張 震 男,1985年出生,博士,講師,研究方向?yàn)槲磥砭W(wǎng)絡(luò)體系架構(gòu)設(shè)計(jì),網(wǎng)絡(luò)測(cè)量.

梁超毅 男,1978年出生,助教,研究方向?yàn)槲磥砭W(wǎng)絡(luò)體系架構(gòu)設(shè)計(jì),內(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é)任編輯：馬蘭英

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

TP393

A

0372-2112 (2016)11-2704-09

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

10.3969/j.issn.0372-2112.2016.11.020