結(jié)合內(nèi)容流行和主觀偏好的節(jié)點(diǎn)緩存策略

曲大鵬，楊 文，楊 越，程天放，吳思錦，王興偉

1(遼寧大學(xué) 信息學(xué)院，沈陽(yáng) 110036 2(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110819)

1 引 言

由于具有資源共享和提供連通性等特點(diǎn)，互聯(lián)網(wǎng)在人們生活和科研等工作中扮演著越來(lái)越重要的角色.隨著通信技術(shù)的快速發(fā)展和網(wǎng)絡(luò)應(yīng)用的多樣化，互聯(lián)網(wǎng)逐漸從早期以主機(jī)為中心模式發(fā)展為面向內(nèi)容模式[1].例如，絕大多數(shù)數(shù)據(jù)密集型產(chǎn)業(yè)服務(wù)遷移到網(wǎng)絡(luò)，互聯(lián)網(wǎng)成為儲(chǔ)藏?cái)?shù)據(jù)的工具；數(shù)字編碼技術(shù)使得網(wǎng)絡(luò)傳輸?shù)膬?nèi)容由早期文本發(fā)展到圖片、音頻和視頻等多媒體文件.因此，網(wǎng)絡(luò)的主要功能已經(jīng)由點(diǎn)對(duì)點(diǎn)通信變?yōu)榱藘?nèi)容分發(fā)，原本以TCP/IP (Transmission Control Protocol/ Internet Protocol)架構(gòu)為核心的網(wǎng)絡(luò)模型很難適應(yīng)這種變化，許多研究組織提出了發(fā)展內(nèi)容中心網(wǎng)絡(luò)(Information Centric Networking，ICN).通過(guò)在網(wǎng)絡(luò)層命名信息，ICN架構(gòu)內(nèi)置緩存，為終端用戶提供有效的內(nèi)容分發(fā)，已經(jīng)成為未來(lái)互聯(lián)網(wǎng)研究中熱點(diǎn)[2].

當(dāng)前，未來(lái)互聯(lián)網(wǎng)的研究主要有以下幾個(gè)代表性工作.來(lái)自美國(guó)加州大學(xué)洛杉磯分校的Content-Centric Networking (CCN)和其后繼Named Data Networking (NDN)*http://named-data.net/，來(lái)自歐盟的FP7(Seventh Framework Programme for Research)工程的PSIRP (Publish-Subscribe Internet Routing Paradigm)和其后繼PURSUIT(Publish-Subscribe Internet Technology)*http://www.fp7-pursuit.eu/PursuitWeb/，來(lái)自日本的新一代網(wǎng)絡(luò)R&D工程中的GreenICN工程*http://www.greenicn.org/.在上述工作中，NDN不僅保留了TCP/IP架構(gòu)的細(xì)腰模型，而且通過(guò)將命名數(shù)據(jù)放在細(xì)腰重塑了互聯(lián)網(wǎng)架構(gòu)，因此獲得廣泛關(guān)注，也是本文工作的基礎(chǔ)架構(gòu).

NDN通過(guò)Interest包和Data包來(lái)完成內(nèi)容的請(qǐng)求和回應(yīng).具體流程為：源節(jié)點(diǎn)發(fā)出內(nèi)含所需內(nèi)容名的Interest包，其它節(jié)點(diǎn)在收到Interest包后檢查自己的CS(Content Store)，如果有相應(yīng)內(nèi)容，則直接回應(yīng)內(nèi)含具體內(nèi)容的Data包；否則查看PIT(Pending Interest Table)，如果內(nèi)容名在PIT中，說(shuō)明最近剛處理過(guò)相應(yīng)請(qǐng)求，尚未收到結(jié)果，則記錄新Interest包的進(jìn)入接口后丟棄，等收到相應(yīng)Data包后，再向所有相應(yīng)接口進(jìn)行轉(zhuǎn)發(fā)；否則通過(guò)查找FIB(Forwarding Information Based)進(jìn)行最長(zhǎng)前綴匹配來(lái)確定下一跳節(jié)點(diǎn)[3].

雖然，NDN具有如緩存和內(nèi)置多播等諸多特性，但還需深入研究.例如，緩存特性使得NDN能夠緩存收到的內(nèi)容，從而節(jié)點(diǎn)能夠直接響應(yīng)后繼收到的Interest包，進(jìn)而縮短路徑長(zhǎng)度和提高傳輸效率.但由于節(jié)點(diǎn)的緩存空間有限，目前經(jīng)典的處處緩存(Leave Copy Everywhere，LCE)，即cache everything everywhere，造成嚴(yán)重的緩存冗余和頻繁緩存替換.因此需要設(shè)置一個(gè)合適的緩存策略.

本文設(shè)計(jì)了一種NDN中的節(jié)點(diǎn)緩存策略，每個(gè)節(jié)點(diǎn)通過(guò)自身收發(fā)Interest包情況來(lái)分別計(jì)算主觀視角下的每類內(nèi)容流行和偏好，得到每類內(nèi)容的基本緩存優(yōu)先級(jí)，從而在收到Data包后，結(jié)合內(nèi)容大小評(píng)估來(lái)計(jì)算具體內(nèi)容的緩存優(yōu)先級(jí)，進(jìn)行緩存和執(zhí)行相應(yīng)緩存替換策略.這種更側(cè)重節(jié)點(diǎn)主觀的內(nèi)容流行無(wú)需節(jié)點(diǎn)間頻繁通信開銷，而且兼顧偏好的特性更符合節(jié)點(diǎn)局部視角，從而能夠具有更高的緩存命中率和更低的緩存替換率.

2 相關(guān)工作

緩存策略使得節(jié)點(diǎn)能夠通過(guò)緩存內(nèi)容直接響應(yīng)后繼收到的相同請(qǐng)求，從而提高響應(yīng)效率，受到了相關(guān)研究人員的廣泛關(guān)注[4].由于信息中心網(wǎng)絡(luò)的分布式結(jié)構(gòu)，很難采用集中式管理架構(gòu)模式，節(jié)點(diǎn)往往通過(guò)自身信息判斷是否緩存經(jīng)過(guò)的內(nèi)容，因此，NDN中采用的最經(jīng)典的緩存策略是LCE，即Data包在返回過(guò)程中在經(jīng)過(guò)的每個(gè)節(jié)點(diǎn)處都要緩存，這不僅導(dǎo)致網(wǎng)絡(luò)中出現(xiàn)大量冗余內(nèi)容，而且受節(jié)點(diǎn)緩存空間限制，會(huì)頻繁發(fā)生緩存替換.文獻(xiàn)[5]提出了一種概率緩存策略(Leave Copy Probability，LCProb)，即Data包在返回途中以一定概率緩存.兩種緩存策略雖然簡(jiǎn)單易行，但缺乏對(duì)于內(nèi)容和節(jié)點(diǎn)特性的分析.

為降低緩存冗余，提高內(nèi)容多樣性，顯然需要在緩存節(jié)點(diǎn)間進(jìn)行有效協(xié)同，根據(jù)其復(fù)雜性，可大致分為顯式協(xié)同和隱式協(xié)同[6].前者需要了解內(nèi)容訪問模式和節(jié)點(diǎn)緩存等具體信息，通過(guò)復(fù)雜計(jì)算來(lái)確定節(jié)點(diǎn)緩存策略，可進(jìn)一步分為全局協(xié)同、路徑協(xié)同和鄰域協(xié)同.其中，全局協(xié)同需要對(duì)網(wǎng)絡(luò)整體拓?fù)浣Y(jié)構(gòu)等詳細(xì)信息具有深入了解.例如，文獻(xiàn)[7]定義了度中心性、緊密中心性和介數(shù)中心性，以分別衡量節(jié)點(diǎn)的鄰居個(gè)數(shù)、與其它節(jié)點(diǎn)的緊密程度和控制信息傳輸?shù)哪芰Γ瑥亩M量將內(nèi)容緩存在網(wǎng)絡(luò)拓?fù)涞年P(guān)鍵節(jié)點(diǎn)上；路徑協(xié)同是指在Data包從響應(yīng)節(jié)點(diǎn)到請(qǐng)求節(jié)點(diǎn)的傳輸路徑上的節(jié)點(diǎn)進(jìn)行協(xié)同決策，例如協(xié)同沿路緩存[8]中的Interest包會(huì)沿途收集節(jié)點(diǎn)狀態(tài)和請(qǐng)求頻率等信息，響應(yīng)節(jié)點(diǎn)據(jù)此計(jì)算出優(yōu)化的緩存位置和相應(yīng)的替換對(duì)象，這種方式需要Interest包收集大量信息，不僅造成額外開銷，而且泄露節(jié)點(diǎn)存儲(chǔ)信息，不適合未來(lái)高安全性需求；鄰域協(xié)同是指在節(jié)點(diǎn)的鄰域范圍內(nèi)顯式地進(jìn)行緩存放置協(xié)作.例如，文獻(xiàn)[9]通過(guò)運(yùn)行一個(gè)后臺(tái)程序來(lái)定期地或事件觸發(fā)地清理鄰域范圍內(nèi)的冗余緩存內(nèi)容.顯式協(xié)同方式雖然降低了內(nèi)容在全局、路徑或鄰域范圍內(nèi)的緩存冗余度，有助于提高整體效用，但需要提前知道緩存節(jié)點(diǎn)的狀態(tài)信息和用戶對(duì)內(nèi)容的請(qǐng)求頻率等信息，而且計(jì)算方式比較復(fù)雜，易造成大量額外開銷，更不利于安全性保障.隱式協(xié)同緩存策略是指每個(gè)節(jié)點(diǎn)無(wú)需了解其他節(jié)點(diǎn)的信息或只需要交互很少的信息就能自主決定是否緩存，更適合NDN環(huán)境.前面分析的LCE和LCProb都屬于隱式協(xié)同緩存策略.

近年來(lái)，對(duì)于緩存策略的研究有兩個(gè)方向非常值得注意：內(nèi)容流行度和自私緩存[10].其中，基于內(nèi)容流行度的緩存策略通過(guò)緩存網(wǎng)絡(luò)中流行的內(nèi)容來(lái)降低網(wǎng)絡(luò)流量和減少時(shí)延[11].文獻(xiàn)[12]提出一種基于流行度的協(xié)作緩存策略，利用全局流行信息來(lái)調(diào)整緩存放置策略，以在具有多個(gè)網(wǎng)關(guān)的網(wǎng)絡(luò)服務(wù)供應(yīng)商間和多路徑路由中降低供應(yīng)商間的流量和內(nèi)容訪問時(shí)延.文獻(xiàn)[13]將垂直請(qǐng)求路徑上的冗余消除和水平局域范圍內(nèi)的內(nèi)容放置相結(jié)合，分別提出基于最大內(nèi)容活躍因子的路徑緩存策略和基于一致性Hash協(xié)同緩存的局域定向存儲(chǔ)策略，從而提高緩存命中率.文獻(xiàn)[14]提出了一種基于流行度的鄰居協(xié)作緩存策略，通過(guò)計(jì)算數(shù)據(jù)傳輸代價(jià)，將內(nèi)容緩存在流行度最大節(jié)點(diǎn)或鄰居協(xié)作緩存節(jié)點(diǎn)，并記錄鄰居節(jié)點(diǎn)緩存內(nèi)容，從而降低數(shù)據(jù)傳輸代價(jià)和提高鄰域緩存空間利用率.自私緩存是指隨著認(rèn)知論的不斷發(fā)展，人們不再默認(rèn)網(wǎng)絡(luò)中節(jié)點(diǎn)都是合作的，而是承認(rèn)節(jié)點(diǎn)的自私性，只有當(dāng)對(duì)自身有益時(shí)，節(jié)點(diǎn)才會(huì)與其他節(jié)點(diǎn)協(xié)作.文獻(xiàn)[15]采用組密鑰加密來(lái)控制群組間數(shù)據(jù)獲取，從而解決自私緩存問題.

由于節(jié)點(diǎn)空間受限，因此當(dāng)緩存空間已滿，但節(jié)點(diǎn)又需緩存新內(nèi)容時(shí)，需要設(shè)計(jì)緩存替換算法.其中，最近最少使用(Least Recently Used，LRU)和最不經(jīng)常使用(Least Frequently Used，LFU)是應(yīng)用最廣的兩種替換算法，前者替換最近一段時(shí)間內(nèi)最長(zhǎng)時(shí)間沒有使用的內(nèi)容，后者替換最近一段時(shí)間內(nèi)使用次數(shù)最少的內(nèi)容.為盡量減少替換次數(shù)和重要內(nèi)容不會(huì)輕易被替換出去，研究者們往往聚焦于內(nèi)容流行度和優(yōu)先級(jí).例如，文獻(xiàn)[16]在CS中加入一個(gè)內(nèi)容流行表以存儲(chǔ)緩存命中率和內(nèi)容流行度等信息，使得節(jié)點(diǎn)能夠周期性地計(jì)算內(nèi)容流行度，從而替換出流行度最低的內(nèi)容，但該策略需要消耗大量資源去維護(hù)內(nèi)容流行表.文獻(xiàn)[17]通過(guò)特定的名字前綴來(lái)識(shí)別全域范圍內(nèi)的優(yōu)先級(jí)，進(jìn)而實(shí)現(xiàn)高效內(nèi)容分發(fā).文獻(xiàn)[18]周期性計(jì)算CS緩存表中緩存內(nèi)容的動(dòng)態(tài)流行度與請(qǐng)求代價(jià)的加權(quán)值，一方面基于該值進(jìn)行緩存替換，另一方面根據(jù)該值進(jìn)行內(nèi)容分類，執(zhí)行區(qū)分化緩存策略.

從上述分析可以看出，由于能直接反映內(nèi)容未來(lái)一段時(shí)間內(nèi)被緩存的概率，因此內(nèi)容流行性受到了廣泛關(guān)注，但一方面現(xiàn)有方法，如文獻(xiàn)[12-14]往往試圖著眼全局因此導(dǎo)致開銷增加和計(jì)算復(fù)雜，而且全局流行并不意味著局部一定流行；另一方面，考慮節(jié)點(diǎn)主觀偏好能夠促進(jìn)節(jié)點(diǎn)合作，一定程度上解決節(jié)點(diǎn)自私問題.因此，本文通過(guò)節(jié)點(diǎn)自己收發(fā)Interest包情況從節(jié)點(diǎn)局部視角考慮內(nèi)容流行和主觀偏好從而判斷每類內(nèi)容的基本緩存優(yōu)先級(jí)，不僅計(jì)算簡(jiǎn)單，無(wú)需額外開銷，而且更能體現(xiàn)內(nèi)容在節(jié)點(diǎn)的未來(lái)緩存概率，又適度解決了節(jié)點(diǎn)自私問題.最后，在每類內(nèi)容的基本緩存優(yōu)先級(jí)上加入內(nèi)容大小的評(píng)估從而得到每個(gè)具體內(nèi)容的存儲(chǔ)優(yōu)先級(jí)，以作為緩存和替換的依據(jù).

3 緩存策略

3.1 基本思想

我們首先應(yīng)用NDN的層次命名機(jī)制來(lái)表示內(nèi)容和內(nèi)容類型，con_k_l表示內(nèi)容，CCon_k表示內(nèi)容類型，con_k_l∈CCon_k；其次應(yīng)用內(nèi)容流行來(lái)反映網(wǎng)絡(luò)中內(nèi)容被需求情況，為降低節(jié)點(diǎn)周期交流造成的開銷，我們統(tǒng)計(jì)節(jié)點(diǎn)收到的Interest包以計(jì)算每類內(nèi)容的被請(qǐng)求比例來(lái)反映其局部視角下的流行性；再次應(yīng)用節(jié)點(diǎn)偏好來(lái)反映自身對(duì)不同內(nèi)容類型的喜愛程度，我們統(tǒng)計(jì)節(jié)點(diǎn)發(fā)送的Interest包(節(jié)點(diǎn)相連的終端主機(jī)發(fā)送的內(nèi)容請(qǐng)求)以計(jì)算每類內(nèi)容的請(qǐng)求比例來(lái)反映其偏好；然后將內(nèi)容流行和節(jié)點(diǎn)偏好結(jié)合起來(lái)表征不同類型內(nèi)容在節(jié)點(diǎn)處的緩存基本優(yōu)先級(jí)，使得不僅能夠通過(guò)緩存流行內(nèi)容來(lái)提高節(jié)點(diǎn)緩存效率，而且能夠通過(guò)滿足偏好來(lái)促進(jìn)節(jié)點(diǎn)合作；最后結(jié)合內(nèi)容大小評(píng)估來(lái)計(jì)算具體內(nèi)容在節(jié)點(diǎn)處的緩存優(yōu)先級(jí)，從而使得當(dāng)收到Data包時(shí)能夠準(zhǔn)確判斷節(jié)點(diǎn)是否緩存以及如何替換.

3.2 參數(shù)定義

3.2.1 內(nèi)容流行

為方便計(jì)算，我們應(yīng)用節(jié)點(diǎn)收到的來(lái)自其它節(jié)點(diǎn)的對(duì)某一類內(nèi)容的Interest包數(shù)量與其收到的所有Interest包數(shù)量的比值來(lái)表征流行度，如公式(1)所示：

(1)

3.2.2 節(jié)點(diǎn)偏好

我們應(yīng)用節(jié)點(diǎn)發(fā)出的對(duì)某一類內(nèi)容的Interest包數(shù)量與其發(fā)出的所有Interest包數(shù)量的比值來(lái)表征其偏好度，如公式(2)所示：

(2)

3.2.3 緩存基本優(yōu)先級(jí)

通過(guò)上述分析，我們?cè)O(shè)定緩存基本優(yōu)先級(jí)由內(nèi)容流行和節(jié)點(diǎn)偏好共同決定，如公式(3)所示：

caprCCon_k(vi)=wpo×poCCon_k(vi)+wpr×prCCon_k(vi)

(3)

其中，caprCCon_k(vi)表示CCon_k類型內(nèi)容在節(jié)點(diǎn)vi處的緩存基本優(yōu)先級(jí)，wpo和wpr分別表示內(nèi)容流行和節(jié)點(diǎn)偏好的權(quán)重，且0<=wpo，wpr<=1，wpo+wpr=1.顯然該類內(nèi)容在網(wǎng)絡(luò)中越流行，節(jié)點(diǎn)對(duì)其越偏好，則該類內(nèi)容在節(jié)點(diǎn)處越應(yīng)該被緩存.

3.2.4 內(nèi)容大小評(píng)估

我們應(yīng)用內(nèi)容大小表征其在緩存中占據(jù)的空間.為降低內(nèi)容大小對(duì)于緩存的影響和保證大內(nèi)容也有一定的存儲(chǔ)機(jī)會(huì)，我們引入如公式(4)所示的評(píng)價(jià)函數(shù)來(lái)計(jì)算具體內(nèi)容大小評(píng)價(jià)值.

cscon_k_l(vi)=

(4)

其中，cscon_k_l(vi)表示節(jié)點(diǎn)vi對(duì)內(nèi)容con_k_l大小size(con_k_l)的評(píng)價(jià)值，csL和csH是內(nèi)容大小的最低和最高閾值，可根據(jù)節(jié)點(diǎn)緩存空間自行設(shè)定，hcs是一個(gè)很小的正小數(shù)，表示當(dāng)節(jié)點(diǎn)大小超過(guò)閾值上限時(shí)的評(píng)價(jià)值.

3.2.5 緩存優(yōu)先級(jí)

我們?cè)诰彺婊緝?yōu)先級(jí)和內(nèi)容大小評(píng)估基礎(chǔ)上設(shè)計(jì)緩存優(yōu)先級(jí)以反映具體內(nèi)容con_k_l在節(jié)點(diǎn)vi處存儲(chǔ)的優(yōu)先級(jí)別，如公式(5)所示：

caprcon_k_l(vi)=caprCCon_k(vi)×cscon_k_l(vi)

(5)

3.3 緩存策略

3.3.1 緩存優(yōu)先級(jí)更新

為及時(shí)更新反映節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的局部視角，我們?cè)O(shè)定定期更新機(jī)制，在每個(gè)更新周期(update_circle)結(jié)束，節(jié)點(diǎn)更新其保存的每類內(nèi)容的流行度和偏好度，以及緩存基本優(yōu)先級(jí)，如公式(6)所示，以保證緩存策略的正確執(zhí)行.

(6)

3.3.2 緩存策略

節(jié)點(diǎn)在運(yùn)行前分配好緩存區(qū)域，因此當(dāng)收到Data包，并且自身不是發(fā)出相應(yīng)Interest包節(jié)點(diǎn)時(shí)，需要執(zhí)行緩存策略，即首先判斷該內(nèi)容的緩存優(yōu)先級(jí)是否超過(guò)閾值，如果沒有超過(guò)閾值，則放棄存儲(chǔ)；如果超過(guò)且緩存有足夠空間，則直接存儲(chǔ)；否則，執(zhí)行緩存替換策略，即根據(jù)公式(5)計(jì)算得到的緩存優(yōu)先級(jí)，按從小到大順序在緩存內(nèi)搜索低于新到內(nèi)容緩存優(yōu)先級(jí)的那些內(nèi)容，直到找到的內(nèi)容大小總和超過(guò)新內(nèi)容，將它們清除以存放新內(nèi)容，如果找不到則意味著需要將某些緩存優(yōu)先級(jí)更高的內(nèi)容替換出去才能放入新內(nèi)容，代價(jià)太高，放棄存儲(chǔ).顯然，在需要執(zhí)行緩存替換策略時(shí)，本算法需要在一定范圍內(nèi)按優(yōu)先級(jí)從小到大順序依次累加，直到能為新到內(nèi)容準(zhǔn)備出足夠空間.考慮到內(nèi)容緩存優(yōu)先級(jí)和大小實(shí)際情況，在絕大多數(shù)情況下，該算法涉及的內(nèi)容規(guī)模較小，效率較高.詳細(xì)過(guò)程如算法1所示，其中輸入是收到的Data包和緩存CS，輸出是新緩存CS*.

算法1.caching strategy

Input：CS，Data;

Output：CS*

1：Calculatecaprcon_k_l(vi)of Data packets;

2：if(caprcon_k_l(vi)≥caprth)then

3：if(there is enough space in CS)then

4：Cache contentcon_k_l;

5：else

6：forthe cached contents from small to large order of prioritythen

7：ifthe priority of the current content is smaller thancaprcon_k_l(vi)then

8：ifthe sum of the size of all contents is larger than size(con_k_l)then

9：Replace these contents with contentcon_k_l;

10：Break;

11：endif

12：else

13：Break;

14：endif

15：endfor

16：endif

17：endif`

在算法1中，line 1表示計(jì)算收到的Data包中的內(nèi)容的緩存優(yōu)先級(jí)；lines 3-4表示如果節(jié)點(diǎn)緩存足夠，則直接緩存；lines 6-15表示按緩存優(yōu)先級(jí)從小到大的順序搜索內(nèi)容，如果在優(yōu)先級(jí)小于新內(nèi)容的內(nèi)容中找到的內(nèi)容大小總和高于新內(nèi)容，則執(zhí)行緩存替換，否則放棄本次緩存.本算法最壞情況下的時(shí)間復(fù)雜度為O(N)，其中N表示節(jié)點(diǎn)內(nèi)已存儲(chǔ)內(nèi)容數(shù)量，而在普通情況下的時(shí)間復(fù)雜度為常數(shù)O(K)，即節(jié)點(diǎn)只需將緩存優(yōu)先級(jí)最小的幾個(gè)內(nèi)容替換出去即可緩存新到內(nèi)容.

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

我們應(yīng)用linux 4.10.8-1下的gcc 6.3.1來(lái)模擬實(shí)現(xiàn)本文提出的結(jié)合內(nèi)容流行和節(jié)點(diǎn)偏好的緩存機(jī)制(Cache strategy based on Content Popularity and Node Preference，CCPNP).拓?fù)浣Y(jié)構(gòu)分別為中國(guó)的CERNET2(20節(jié)點(diǎn)，22條邊)、美國(guó)的ITC Deltacom(97節(jié)點(diǎn)，121條邊)、歐洲的GTS CE(130節(jié)點(diǎn)，166條邊)和OTEGlobe(61節(jié)點(diǎn)，69條邊)4，具體如圖1所示.為便于分析，我們?cè)O(shè)定26種Interest包類型，并遵循zipf分布，同時(shí)引入“單位時(shí)間”的概念，每個(gè)節(jié)點(diǎn)在每個(gè)單位時(shí)間內(nèi)發(fā)送1個(gè)Interest包.

圖1 網(wǎng)絡(luò)拓?fù)鋱D

評(píng)價(jià)參數(shù)分別為緩存命中率(Cache Hit Rate)、緩存替換率(Cache Replacement Rate)和平均請(qǐng)求距離(Average Request Distance).其中，緩存命中率是指節(jié)點(diǎn)從緩存中獲取到內(nèi)容的次數(shù)占獲取內(nèi)容總次數(shù)的百分比；緩存替換率是指緩存時(shí)發(fā)生替換的次數(shù)占緩存次數(shù)的百分比；平均請(qǐng)求距離是指從發(fā)出Interest包的節(jié)點(diǎn)到返回Data包的節(jié)點(diǎn)的平均距離(以跳數(shù)為單位).

實(shí)驗(yàn)中相關(guān)參數(shù)分別設(shè)置為：α=0.75，wpo=0.5，wpr=0.5，update_circle=20單位時(shí)間.

表1 仿真實(shí)驗(yàn)參數(shù)設(shè)置

4.2 實(shí)驗(yàn)結(jié)果及分析

在圖2中，我們比較CCPNP和LCE、LCProb在四個(gè)不同拓?fù)湎碌木彺婷新剩瑱M坐標(biāo)為每個(gè)節(jié)點(diǎn)平均發(fā)送的Interest包總數(shù)，縱坐標(biāo)為不同緩存策略的緩存命中率.顯然，隨著節(jié)點(diǎn)發(fā)出的Interest包數(shù)量的增加，網(wǎng)絡(luò)中返回的Data包數(shù)量也相應(yīng)增加，因此三種不同策略的緩存命中率都呈增加趨勢(shì).

圖2 緩存命中率比較

其中，由于考慮了內(nèi)容流行和節(jié)點(diǎn)偏好，CCPNP的命中率顯然遠(yuǎn)高于采取處處緩存方式的LCE和采取概率處處緩存的LCProb.由于采取概率緩存的方式，LCProb的命中率略高于完全緩存的LCE.

4http://www.topoloty-zoo.org/dataset.html

值得注意的是，由于CERNET2中只有20個(gè)節(jié)點(diǎn)，低于OTEGlobe的61個(gè)節(jié)點(diǎn)，更低于ITC Deltacom的97個(gè)節(jié)點(diǎn)和GTS CE的130個(gè)節(jié)點(diǎn)，使得在每個(gè)節(jié)點(diǎn)發(fā)出的Interest包數(shù)量相等的情況下，相應(yīng)Data包從回應(yīng)節(jié)點(diǎn)到請(qǐng)求節(jié)點(diǎn)的路徑經(jīng)過(guò)的節(jié)點(diǎn)數(shù)量較少，被緩存的數(shù)量相應(yīng)較小，所以CCPNP、LCE和LCProb的緩存命中率按從小到大的順序依次為CERNET2、OTE Globe、ITC Deltacom和GTS CE.過(guò)低的節(jié)點(diǎn)數(shù)量也使得在Interest包數(shù)量比較少的時(shí)候，LCE在CERNET2中取得了比LCProb略好的緩存命中率.

圖3 緩存替換率比較

圖3顯示的是四種不同拓?fù)湎氯N策略的緩存替換率，可以看出，CCPNP的性能遠(yuǎn)遠(yuǎn)低于LCE和LCProb，原因是首先CCPNP在執(zhí)行緩存策略時(shí)考慮了內(nèi)容流行性和節(jié)點(diǎn)偏好性，從而盡量存儲(chǔ)那些在未來(lái)更容易被請(qǐng)求的內(nèi)容和更被自己喜歡的內(nèi)容，可以以更大概率直接響應(yīng)未來(lái)收到的Interest包，避免潛在的緩存替換操作；其次，CCPNP在執(zhí)行緩存策略前有一個(gè)閾值判斷過(guò)程，這使得一些優(yōu)先級(jí)極低的內(nèi)容不會(huì)被緩存，進(jìn)一步降低了未來(lái)發(fā)生替換的概率；最后，CCPNP考慮內(nèi)容大小，合理降低了一些占據(jù)空間過(guò)大的內(nèi)容被緩存的概率，綜上，CCPNP在每個(gè)拓?fù)渖隙既〉昧朔浅５偷木彺嫣鎿Q率.

圖4 平均請(qǐng)求距離比較

為進(jìn)一步展現(xiàn)緩存策略對(duì)于網(wǎng)絡(luò)性能的影響，特別是對(duì)于網(wǎng)絡(luò)流量的影響，我們?cè)谒姆N不同拓?fù)湎卤容^了三種緩存策略的平均請(qǐng)求距離，如圖4所示，CCPNP的性能低于LCE和LCProb，這是因?yàn)镃CPNP能更好地協(xié)調(diào)內(nèi)容的緩存位置和節(jié)點(diǎn)的緩存內(nèi)容，更有效地利用節(jié)點(diǎn)的緩存空間.為更好地進(jìn)行比較，我們還加入了無(wú)緩存機(jī)制Non-Cache，可以看出當(dāng)節(jié)點(diǎn)沒有緩存機(jī)制時(shí)，平均請(qǐng)求距離值最大，因?yàn)楣?jié)點(diǎn)只能從原持有節(jié)點(diǎn)處獲取請(qǐng)求內(nèi)容.雖然，LCE和LCProb的緩存機(jī)制效率較低，但畢竟能夠在內(nèi)容持有節(jié)點(diǎn)到請(qǐng)求節(jié)點(diǎn)的路徑上進(jìn)行相應(yīng)緩存操作，因此較Non-Cache機(jī)制降低了平均請(qǐng)求距離.

5 總 結(jié)

針對(duì)現(xiàn)有NDN緩存機(jī)制存在嚴(yán)重緩存冗余，基于全局流行度的緩存機(jī)制需要大量協(xié)助開銷，以及節(jié)點(diǎn)自私等問題，本文為NDN設(shè)計(jì)了一個(gè)節(jié)點(diǎn)主觀視角下結(jié)合內(nèi)容流行和自身偏好的緩存策略，通過(guò)對(duì)內(nèi)容類型的流行度和節(jié)點(diǎn)偏好來(lái)表征不同內(nèi)容類型在節(jié)點(diǎn)處的緩存基本優(yōu)先級(jí)，進(jìn)一步結(jié)合內(nèi)容大小評(píng)估來(lái)表征具體內(nèi)容在節(jié)點(diǎn)處的緩存優(yōu)先級(jí).實(shí)驗(yàn)結(jié)果表明該緩存策略比主流的LCE和LCProb具有更高的緩存命中率、更低的緩存替換率和更短的請(qǐng)求距離.

在未來(lái)工作中，我們一方面將引入其它協(xié)同方法以通過(guò)節(jié)點(diǎn)間的交互來(lái)強(qiáng)化節(jié)點(diǎn)對(duì)于全局內(nèi)容流行的深入挖掘，并對(duì)取得性能和協(xié)同交互所需代價(jià)之間進(jìn)行深入權(quán)衡分析；另一方面在節(jié)點(diǎn)偏好研究基礎(chǔ)上，通過(guò)引入信任模型來(lái)解決存在自私節(jié)點(diǎn)的NDN網(wǎng)絡(luò)環(huán)境中節(jié)點(diǎn)合作緩存問題.