命名數(shù)據(jù)網(wǎng)絡(luò)中一種基于節(jié)點(diǎn)分類的數(shù)據(jù)存儲(chǔ)策略

黃　勝　滕明埝　吳　震　許江華　季瑞軍

(重慶郵電大學(xué)光纖通信技術(shù)重點(diǎn)實(shí)驗(yàn)室　重慶　400065)(tmnfighting@163.com)

?

命名數(shù)據(jù)網(wǎng)絡(luò)中一種基于節(jié)點(diǎn)分類的數(shù)據(jù)存儲(chǔ)策略

黃勝滕明埝吳震許江華季瑞軍

(重慶郵電大學(xué)光纖通信技術(shù)重點(diǎn)實(shí)驗(yàn)室重慶400065)(tmnfighting@163.com)

摘要緩存是命名數(shù)據(jù)網(wǎng)絡(luò)(named data networking, NDN)有別于傳統(tǒng)網(wǎng)絡(luò)最突出的特性之一，NDN中默認(rèn)所有節(jié)點(diǎn)都具有緩存所有經(jīng)過(guò)數(shù)據(jù)的功能.這種“處處緩存”策略導(dǎo)致網(wǎng)內(nèi)大量冗余數(shù)據(jù)的產(chǎn)生，使網(wǎng)內(nèi)緩存被嚴(yán)重浪費(fèi).針對(duì)上述問(wèn)題，首次提出了一種基于節(jié)點(diǎn)分類(based on node classification, BNC)的數(shù)據(jù)存儲(chǔ)策略.基于節(jié)點(diǎn)位置的不同，將數(shù)據(jù)返回客戶端所經(jīng)過(guò)的節(jié)點(diǎn)分為“邊緣”類節(jié)點(diǎn)與“核心”類節(jié)點(diǎn).當(dāng)數(shù)據(jù)經(jīng)過(guò)“核心”類節(jié)點(diǎn)時(shí)，通過(guò)權(quán)衡該類節(jié)點(diǎn)的位置與數(shù)據(jù)在不同節(jié)點(diǎn)的流行度分布，將數(shù)據(jù)存儲(chǔ)在對(duì)其他節(jié)點(diǎn)最有利的節(jié)點(diǎn)中；當(dāng)數(shù)據(jù)經(jīng)過(guò)“邊緣”類節(jié)點(diǎn)時(shí)，通過(guò)該數(shù)據(jù)流行度來(lái)選擇最有利于客戶端的位置.仿真結(jié)果表明，提出的策略將有效提高數(shù)據(jù)命中率，減少數(shù)據(jù)請(qǐng)求時(shí)延和距離.

關(guān)鍵詞命名數(shù)據(jù)網(wǎng)絡(luò)；節(jié)點(diǎn)分類數(shù)據(jù)存儲(chǔ)策略；網(wǎng)內(nèi)存儲(chǔ)；冗余數(shù)據(jù)；內(nèi)容中心網(wǎng)絡(luò)

與傳統(tǒng)基于host-to-host的網(wǎng)絡(luò)模型相比，NDN將內(nèi)容作為主體，不再關(guān)心內(nèi)容存儲(chǔ)的位置，而關(guān)心的是內(nèi)容本身是什么[12-16].NDN中每個(gè)節(jié)點(diǎn)都具有內(nèi)容存儲(chǔ)庫(kù)(content storage, CS)，這是其有別于傳統(tǒng)網(wǎng)絡(luò)最大的特點(diǎn).與傳統(tǒng)網(wǎng)絡(luò)相比客戶端所請(qǐng)求的數(shù)據(jù)來(lái)源不僅僅是原始內(nèi)容服務(wù)器(original content servers, OCS)，也可以是網(wǎng)內(nèi)任意緩存有對(duì)應(yīng)數(shù)據(jù)的網(wǎng)內(nèi)節(jié)點(diǎn).因此，將數(shù)據(jù)緩存在什么位置使整個(gè)網(wǎng)絡(luò)的性能最佳已經(jīng)成為了制約NDN發(fā)展的關(guān)鍵因素之一.

在早些時(shí)候Laoutaris 等人提出了LCD(leave copy down)[17-18]與MCD(move copy down)[17-18]以及Prob(copy with probability)[17]三種策略，其中，LCD策略將數(shù)據(jù)僅在命中節(jié)點(diǎn)的下一節(jié)點(diǎn)緩存；MCD策略除將數(shù)據(jù)從命中節(jié)點(diǎn)移向其下一跳節(jié)點(diǎn)以外，還將刪除數(shù)據(jù)在命中節(jié)點(diǎn)中的副本；Prob策略使每個(gè)節(jié)點(diǎn)都以概率p緩存經(jīng)過(guò)的數(shù)據(jù)，其中，0

劉外喜等人[19]提出SC策略，該策略認(rèn)為數(shù)據(jù)傳播應(yīng)分為傳播早期與晚期2個(gè)階段，其中，早期客戶端對(duì)數(shù)據(jù)的需求高于晚期，因此，在這2個(gè)時(shí)期應(yīng)該使用不同的緩存機(jī)制.在數(shù)據(jù)傳播早期由于網(wǎng)內(nèi)節(jié)點(diǎn)對(duì)數(shù)據(jù)的緩存較少，此時(shí)SC策略對(duì)數(shù)據(jù)塊在網(wǎng)絡(luò)中的合理分布有一定的幫助.但是，SC策略忽略了用戶請(qǐng)求數(shù)據(jù)時(shí)具有實(shí)時(shí)性與隨機(jī)性的事實(shí)，因此，將用戶對(duì)數(shù)據(jù)的請(qǐng)求分為2個(gè)時(shí)期的方式不能很好地體現(xiàn)用戶請(qǐng)求數(shù)據(jù)的特性.

Chai等人[20]提出了Betw策略，該策略通過(guò)計(jì)算節(jié)點(diǎn)的介數(shù)來(lái)判斷節(jié)點(diǎn)的重要性(介數(shù)越高的節(jié)點(diǎn)越重要).當(dāng)數(shù)據(jù)返回客戶端的過(guò)程中，只將數(shù)據(jù)緩存在介數(shù)最大的節(jié)點(diǎn)上.這個(gè)機(jī)制簡(jiǎn)單易行，在一定程度上使整個(gè)網(wǎng)絡(luò)性能得到了提升.但是，Betw策略將使介數(shù)較大的節(jié)點(diǎn)十分“擁擠”，這些節(jié)點(diǎn)的負(fù)載將遠(yuǎn)遠(yuǎn)高于其他低介數(shù)節(jié)點(diǎn)，并且，高介數(shù)節(jié)點(diǎn)中的數(shù)據(jù)替換頻繁.這樣即使具有較高流行度的數(shù)據(jù)也很容易被替換，使下一次該數(shù)據(jù)的請(qǐng)求不能被滿足.

Li與Wu等人[21]從降低ISP間流量和用戶平均訪問(wèn)時(shí)延的角度出發(fā)，提出了基于節(jié)點(diǎn)分層與分級(jí)的優(yōu)化策略.該策略依據(jù)數(shù)據(jù)流行度的不同，將數(shù)據(jù)緩存在不同的層、級(jí)上，從而使整個(gè)網(wǎng)絡(luò)的性能最佳，但是本文的拓?fù)浞謱优c分級(jí)思想在除樹(shù)形拓?fù)湟酝獾耐負(fù)渲袑?shí)現(xiàn)較為困難，因此，其擴(kuò)展性有待提高.

Psaras與Chai等人[22]提出了ProbCache策略，該策略依據(jù)請(qǐng)求所經(jīng)過(guò)鏈路的節(jié)點(diǎn)的緩存能力與節(jié)點(diǎn)到客戶端節(jié)點(diǎn)的距離，得到每個(gè)節(jié)點(diǎn)緩存數(shù)據(jù)的概率值，然后以此概率值作為節(jié)點(diǎn)緩存數(shù)據(jù)的依據(jù).該策略在一定程度上減小了網(wǎng)內(nèi)數(shù)據(jù)的冗余度，提高了緩存的利用效率，使整個(gè)網(wǎng)絡(luò)的性能有所提高.但是，ProbCache策略沒(méi)有考慮數(shù)據(jù)的流行度因素，將所有的數(shù)據(jù)都等同看待，從而使流行的數(shù)據(jù)沒(méi)有得到更好的利用.

針對(duì)上述所存在的問(wèn)題，本文首次將數(shù)據(jù)包返回客戶端所經(jīng)過(guò)的節(jié)點(diǎn)分為不同類型，對(duì)不同類型的節(jié)點(diǎn)按照不同的存儲(chǔ)策略對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)，并考慮了用戶請(qǐng)求數(shù)據(jù)時(shí)的實(shí)時(shí)性，本文所提出的基于節(jié)點(diǎn)分類(based on node classification, BNC)機(jī)制非常簡(jiǎn)單，不需要復(fù)雜的運(yùn)算，而且數(shù)據(jù)包與興趣包所攜帶的附加字段大小比較固定，不會(huì)因?yàn)閿?shù)據(jù)的大小變化而變化，完全符合緩存策略“從簡(jiǎn)”的要求.

1NDN緩存策略常見(jiàn)問(wèn)題

為了充分利用節(jié)點(diǎn)的緩存，設(shè)計(jì)一種高效的數(shù)據(jù)緩存策略便成為了關(guān)鍵.怎樣緩存數(shù)據(jù)(數(shù)據(jù)緩存在什么地方)才能使用戶請(qǐng)求數(shù)據(jù)的時(shí)延更短、跳數(shù)更少、網(wǎng)內(nèi)命中率更高等便成為了一個(gè)高效緩存策略的重要表現(xiàn).而在當(dāng)前的緩存設(shè)計(jì)中主要存在以下需要考慮的問(wèn)題：

1) 近客戶端緩存與中心緩存.為了減少客戶端請(qǐng)求數(shù)據(jù)的時(shí)延與跳數(shù)，盡可能地將數(shù)據(jù)緩存在離客戶端近的節(jié)點(diǎn)上，如果數(shù)據(jù)的流行度較高，即短時(shí)間內(nèi)數(shù)據(jù)的請(qǐng)求量很大，這樣的緩存方式在一定程度上會(huì)減少數(shù)據(jù)請(qǐng)求的時(shí)延.但由于近客戶端節(jié)點(diǎn)的緩存往往所服務(wù)的客戶端節(jié)點(diǎn)很少，甚至有可能只服務(wù)于一個(gè)客戶端節(jié)點(diǎn)，將導(dǎo)致緩存利用率低等問(wèn)題.反之，中心緩存便是將數(shù)據(jù)緩存在網(wǎng)絡(luò)中重要的位置使其為更多的客戶端服務(wù)，顯然，如果緩存在中心位置的數(shù)據(jù)只針對(duì)某一個(gè)客戶端有高流行度，那么，與近客戶端緩存相比將產(chǎn)生更大的請(qǐng)求時(shí)延等問(wèn)題.

2) 無(wú)效緩存.NDN默認(rèn)采用處處緩存(leave copy everywhere, LCE)，即節(jié)點(diǎn)將不加區(qū)分地緩存所有經(jīng)過(guò)的數(shù)據(jù).如圖1所示，節(jié)點(diǎn)p為OCS節(jié)點(diǎn)，當(dāng)客戶端第1次請(qǐng)求數(shù)據(jù)i時(shí)請(qǐng)求將到達(dá)節(jié)點(diǎn)p，如果采用LCE數(shù)據(jù)緩存策略，那么，在數(shù)據(jù)i返回客戶端的所有經(jīng)過(guò)節(jié)點(diǎn)中都要緩存數(shù)據(jù)i.然而，下次請(qǐng)求數(shù)據(jù)i時(shí)在節(jié)點(diǎn)c便可得到相應(yīng)數(shù)據(jù)，這樣其他節(jié)點(diǎn)緩存的數(shù)據(jù)i便成為了“無(wú)效數(shù)據(jù)”，從而浪費(fèi)緩存空間.

Fig. 1　LCE data packet cache scheme.圖1　LCE數(shù)據(jù)緩存策略

3) 非實(shí)時(shí)性.由于客戶端對(duì)數(shù)據(jù)的請(qǐng)求具有實(shí)時(shí)性，即在不同時(shí)間客戶感興趣的數(shù)據(jù)不同.但是，大多數(shù)緩存策略并沒(méi)有將其考慮其中，從而導(dǎo)致過(guò)時(shí)的數(shù)據(jù)長(zhǎng)期占用有限的緩存空間.

針對(duì)以上問(wèn)題，本文提出了BNC策略.該策略將數(shù)據(jù)返回客戶端途徑的節(jié)點(diǎn)分為“邊緣”類節(jié)點(diǎn)與“核心”類節(jié)點(diǎn)(本文后續(xù)部分將“邊緣”類節(jié)點(diǎn)與“核心”類節(jié)點(diǎn)分別用Ⅰ類、Ⅱ類表示).當(dāng)數(shù)據(jù)經(jīng)過(guò)Ⅰ類節(jié)點(diǎn)時(shí)，由于該類節(jié)點(diǎn)主要服務(wù)對(duì)象為與其相近的客戶端，因此數(shù)據(jù)根據(jù)該客戶端的請(qǐng)求流行度對(duì)數(shù)據(jù)進(jìn)行緩存.當(dāng)數(shù)據(jù)經(jīng)過(guò)Ⅱ類節(jié)點(diǎn)時(shí)，為了使緩存數(shù)據(jù)的影響范圍更廣，數(shù)據(jù)的緩存位置將由節(jié)點(diǎn)位置與數(shù)據(jù)在節(jié)點(diǎn)中的流行度分布共同決定，同時(shí)為了滿足實(shí)時(shí)性，本文將2次數(shù)據(jù)請(qǐng)求時(shí)間間隔作為BNC的重要影響因子之一.

2BNC數(shù)據(jù)存儲(chǔ)策略運(yùn)行機(jī)制

在本文提出的系統(tǒng)模型中，我們將整個(gè)網(wǎng)絡(luò)標(biāo)記為G(V,E)，其中V={v1,v2,…,vn}表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合，E={e1,e2,…,em}表示網(wǎng)絡(luò)中所有鏈路的集合.整個(gè)網(wǎng)絡(luò)由內(nèi)容原始節(jié)點(diǎn)與具有NDN特性的路由節(jié)點(diǎn)及客戶端節(jié)點(diǎn)組成.

2.1BNC基本思想

NDN中現(xiàn)有的數(shù)據(jù)緩存策略往往只考慮了某一類節(jié)點(diǎn)的緩存情況，如文獻(xiàn)[13]中所提出的Betw緩存策略只考慮到鏈路上最大介數(shù)節(jié)點(diǎn)的緩存，這樣將其他次要節(jié)點(diǎn)完全否決的思想，將降低整個(gè)網(wǎng)絡(luò)中緩存的利用率.文獻(xiàn)[14]也提出了類似節(jié)點(diǎn)分類的ProbCache緩存策略，但文中的節(jié)點(diǎn)分類方式不具有一般性.結(jié)合上面文章的不足與啟示，本文提出了一種更為合理的BNC緩存策略.

NDN中數(shù)據(jù)包返回客戶端時(shí)往往會(huì)經(jīng)過(guò)多個(gè)中間路由器節(jié)點(diǎn)，當(dāng)一個(gè)網(wǎng)絡(luò)確定時(shí)，其節(jié)點(diǎn)的位置也就確定了.然而，節(jié)點(diǎn)所在的位置不同對(duì)整個(gè)網(wǎng)絡(luò)起到的作用也不一樣.通常情況下節(jié)點(diǎn)越靠近客戶端其作用范圍越小，越靠近中心的節(jié)點(diǎn)其作用范圍越廣.靠近客戶端的節(jié)點(diǎn)由于離客戶端較近，如果能將客戶端請(qǐng)求頻率較高的數(shù)據(jù)存儲(chǔ)在這些節(jié)點(diǎn)中，會(huì)大大減少客戶端請(qǐng)求數(shù)據(jù)的時(shí)延與距離.但由于靠近客戶端的節(jié)點(diǎn)作用的范圍有限，從而會(huì)導(dǎo)致其他節(jié)點(diǎn)不能訪問(wèn)到這些節(jié)點(diǎn)中的數(shù)據(jù)，導(dǎo)致請(qǐng)求的網(wǎng)內(nèi)命中率下降.然而，中心節(jié)點(diǎn)往往能夠影響較多的客戶端節(jié)點(diǎn)，因此，將數(shù)據(jù)緩存在中心節(jié)點(diǎn)處將有效提高請(qǐng)求的網(wǎng)內(nèi)命中率.

通過(guò)上述分析，本文提出的BNC策略將數(shù)據(jù)包返回客戶端所經(jīng)過(guò)的節(jié)點(diǎn)分為Ⅰ類節(jié)點(diǎn)與Ⅱ類節(jié)點(diǎn)2類，其中Ⅰ類節(jié)點(diǎn)為“邊緣”節(jié)點(diǎn)，Ⅱ類節(jié)點(diǎn)為“核心”節(jié)點(diǎn).Ⅰ類節(jié)點(diǎn)主要為對(duì)應(yīng)客戶端提供高效的數(shù)據(jù)傳輸(迅速地滿足客戶端請(qǐng)求)功能；Ⅱ類節(jié)點(diǎn)則是為了更廣地服務(wù)其他客戶端的請(qǐng)求.可以看出2類的節(jié)點(diǎn)作用大不相同，因此，對(duì)這2類節(jié)點(diǎn)應(yīng)當(dāng)采用不同的緩存策略.其中，Ⅰ類節(jié)點(diǎn)主要依據(jù)客戶端節(jié)點(diǎn)對(duì)數(shù)據(jù)請(qǐng)求的流行度分布來(lái)緩存數(shù)據(jù)；Ⅱ類節(jié)點(diǎn)則主要依據(jù)節(jié)點(diǎn)位置以及數(shù)據(jù)在不同節(jié)點(diǎn)的流行度不同來(lái)緩存數(shù)據(jù).從而在滿足當(dāng)前請(qǐng)求數(shù)據(jù)的客戶端的同時(shí)也滿足其他客戶端潛在的需求，并且，為了避免網(wǎng)內(nèi)產(chǎn)生不必要的冗余數(shù)據(jù)，每次數(shù)據(jù)請(qǐng)求過(guò)程中，數(shù)據(jù)在每個(gè)類型的節(jié)點(diǎn)中只被緩存一次.結(jié)果表明，BNC策略將減少用戶請(qǐng)求數(shù)據(jù)的時(shí)延與距離，并提高請(qǐng)求的網(wǎng)內(nèi)命中率.

2.2BNC策略實(shí)現(xiàn)

由于BNC策略將數(shù)據(jù)包返回時(shí)經(jīng)過(guò)的節(jié)點(diǎn)分為2種不同的類型，并且2個(gè)類型的節(jié)點(diǎn)有不同的數(shù)據(jù)緩存方式.因此，本節(jié)將分為2個(gè)小節(jié)分別對(duì)Ⅰ類節(jié)點(diǎn)、Ⅱ類節(jié)點(diǎn)緩存方式進(jìn)行描述.

2.2.1 “邊緣”類節(jié)點(diǎn)(Ⅰ類)存儲(chǔ)策略實(shí)現(xiàn)

設(shè)數(shù)據(jù)返回客戶端所經(jīng)過(guò)的路由器節(jié)點(diǎn)總數(shù)為n，本文將靠近客戶端的l跳節(jié)點(diǎn)設(shè)置為Ⅰ類節(jié)點(diǎn)，而其余n-l個(gè)節(jié)點(diǎn)屬于Ⅱ類節(jié)點(diǎn).文中的l參數(shù)值主要由客戶端到服務(wù)器端的平均距離決定，本文中的仿真用到了2種拓?fù)漕愋?，?種拓?fù)浣Y(jié)構(gòu)相對(duì)于第1種而言更為復(fù)雜，但是由于第2種拓?fù)湓黾恿丝蛻舳斯?jié)點(diǎn)與服務(wù)器端節(jié)點(diǎn)的個(gè)數(shù)，這樣一來(lái)便使客戶端節(jié)點(diǎn)到服務(wù)器端節(jié)點(diǎn)的平均距離十分接近，并且通過(guò)實(shí)驗(yàn)證明，在本實(shí)驗(yàn)中當(dāng)l=3時(shí)仿真性能最好(請(qǐng)求平均命中率最高)，因此，本文中的l=3.如圖2所示，V1={v1,v2,v3}表示Ⅰ類節(jié)點(diǎn)，V2={v4,v5,…,vn}表示Ⅱ類節(jié)點(diǎn).在本節(jié)我們只討論Ⅰ類節(jié)點(diǎn)對(duì)數(shù)據(jù)緩存的實(shí)現(xiàn).

Fig. 2　The node classification.圖2　節(jié)點(diǎn)分類

對(duì)Ⅰ類節(jié)點(diǎn)而言，越靠近客戶端越重要.因此，當(dāng)數(shù)據(jù)由Ⅱ類節(jié)點(diǎn)返回時(shí)，該數(shù)據(jù)將被緩存在節(jié)點(diǎn)v3.因?yàn)?，已?個(gè)Ⅰ類節(jié)點(diǎn)，如果數(shù)據(jù)請(qǐng)求流行度較高，那么，應(yīng)該被緩存于Ⅰ類節(jié)點(diǎn)中，而不會(huì)到Ⅰ類以外的節(jié)點(diǎn)請(qǐng)求數(shù)據(jù).因此，當(dāng)數(shù)據(jù)從Ⅱ類節(jié)點(diǎn)返回時(shí)將其看作是當(dāng)前非流行數(shù)據(jù).雖說(shuō)將此類數(shù)據(jù)定義為非流行數(shù)據(jù)，但由于其是最近被請(qǐng)求的數(shù)據(jù)，并不知道在接下來(lái)的時(shí)間是否流行，所以不能將其拋棄.由上述分析，此時(shí)，將該類非流行數(shù)據(jù)緩存在離客戶端最遠(yuǎn)的Ⅰ類節(jié)點(diǎn)(即節(jié)點(diǎn)v3)中，而該數(shù)據(jù)經(jīng)過(guò)其他Ⅰ類節(jié)點(diǎn)時(shí)將不再存儲(chǔ).

當(dāng)請(qǐng)求被Ⅰ類節(jié)點(diǎn)(v1,v2,v3)滿足，將對(duì)應(yīng)數(shù)據(jù)返回客戶端時(shí)需另作處理.假設(shè)請(qǐng)求被節(jié)點(diǎn)v3(或v1、或v2)滿足，說(shuō)明該數(shù)據(jù)相對(duì)流行.但也需注意到一個(gè)問(wèn)題，如果數(shù)據(jù)位于命中節(jié)點(diǎn)CS緩存隊(duì)列的前面，意味著此數(shù)據(jù)即將被替換(本文使用LRU數(shù)據(jù)替換策略，該策略替換數(shù)據(jù)時(shí)由最前面的數(shù)據(jù)開(kāi)始)，那么，將此數(shù)據(jù)定義為次非流行數(shù)據(jù).此時(shí)該數(shù)據(jù)不會(huì)被返回客戶端時(shí)經(jīng)過(guò)的其他節(jié)點(diǎn)緩存，但由于該數(shù)據(jù)剛被訪問(wèn)，它將被放在節(jié)點(diǎn)v3的CS隊(duì)列末尾(設(shè)隊(duì)列大小為m).本文將Ⅰ類節(jié)點(diǎn)CS隊(duì)列中后0.3m個(gè)數(shù)據(jù)定義為流行數(shù)據(jù)，前0.7m個(gè)數(shù)據(jù)定義為次非流行數(shù)據(jù).如果當(dāng)請(qǐng)求被Ⅰ類節(jié)點(diǎn)滿足的同時(shí)該數(shù)據(jù)又是其CS緩存隊(duì)列后0.3m個(gè)數(shù)據(jù)之一，這充分說(shuō)明該數(shù)據(jù)在短時(shí)間內(nèi)被連續(xù)請(qǐng)求，則該數(shù)據(jù)在此時(shí)為流行數(shù)據(jù).因此，將該數(shù)據(jù)在其命中節(jié)點(diǎn)的下一跳節(jié)點(diǎn)緩存(即如果請(qǐng)求被v3滿足，且該數(shù)據(jù)是節(jié)點(diǎn)v3中CS隊(duì)列后0.3m個(gè)數(shù)據(jù)之一，那么，該數(shù)據(jù)在返回客戶端時(shí)被緩存在節(jié)點(diǎn)v2上，v1并不緩存.當(dāng)然，節(jié)點(diǎn)v2與此相同.如果請(qǐng)求在節(jié)點(diǎn)v1中被滿足，那么，只能將數(shù)據(jù)緩存在節(jié)點(diǎn)v1的CS隊(duì)列的末尾).在這種情況下，數(shù)據(jù)被命中節(jié)點(diǎn)的下一跳節(jié)點(diǎn)緩存以后是否刪除命中節(jié)點(diǎn)中的副本便成為了需要仔細(xì)考慮的地方.此時(shí)，當(dāng)數(shù)據(jù)命中節(jié)點(diǎn)的接入接口大于等于3時(shí)該數(shù)據(jù)將不被刪除，因?yàn)?，這時(shí)如果將數(shù)據(jù)刪除，其他客戶端節(jié)點(diǎn)相應(yīng)請(qǐng)求到達(dá)該節(jié)點(diǎn)請(qǐng)求數(shù)據(jù)時(shí)將不會(huì)命中，這樣使網(wǎng)內(nèi)命中率下降的同時(shí)也會(huì)增加其他客戶端請(qǐng)求數(shù)據(jù)的時(shí)延.但如果數(shù)據(jù)命中節(jié)點(diǎn)的接入接口小于等于2，那么，數(shù)據(jù)將被在命中節(jié)點(diǎn)刪除，因?yàn)?，此時(shí)命中節(jié)點(diǎn)中的相應(yīng)數(shù)據(jù)將使冗余數(shù)據(jù)浪費(fèi)緩存空間.

2.2.2“核心”類節(jié)點(diǎn)(Ⅱ類)存儲(chǔ)策略實(shí)現(xiàn)

與Ⅰ類節(jié)點(diǎn)的存儲(chǔ)策略相比，Ⅱ類節(jié)點(diǎn)的存儲(chǔ)策略相對(duì)而言更加復(fù)雜.為了更好地理解Ⅱ類節(jié)點(diǎn)的存儲(chǔ)策略，下面首先給出節(jié)點(diǎn)親密度與介數(shù)的定義.

定義1. 節(jié)點(diǎn)親密度.節(jié)點(diǎn)親密度被定義為該節(jié)點(diǎn)到達(dá)其他節(jié)點(diǎn)距離之和的倒數(shù).因此，節(jié)點(diǎn)vi的親密度為

(1)

其中，eij表示節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間的最短路徑長(zhǎng)度.

節(jié)點(diǎn)親密度可以很好地表達(dá)節(jié)點(diǎn)到達(dá)網(wǎng)絡(luò)中其他節(jié)點(diǎn)的難易程度，能夠很好地反映本節(jié)點(diǎn)對(duì)其他節(jié)點(diǎn)的作用能力.

定義2. 介數(shù).節(jié)點(diǎn)介數(shù)定義為網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)最短路徑經(jīng)過(guò)本節(jié)點(diǎn)的路徑數(shù)占所有最短路徑數(shù)的比例，則節(jié)點(diǎn)vi的介數(shù)為

(2)

其中，σst表示頂點(diǎn)vs到頂點(diǎn)vt所有最短路徑數(shù);σst(i)表示σst中經(jīng)過(guò)節(jié)點(diǎn)vi的最短路徑數(shù);n(n-1)2用來(lái)對(duì)無(wú)向圖中節(jié)點(diǎn)介數(shù)歸一化處理，即此時(shí)B(i)∈[0,1].

Ⅱ類節(jié)點(diǎn)相對(duì)于Ⅰ類節(jié)點(diǎn)而言更靠近網(wǎng)絡(luò)中心位置，因此，其距離數(shù)據(jù)請(qǐng)求客戶端而言較遠(yuǎn)，如果將其與Ⅰ類節(jié)點(diǎn)“一視同仁”，那么，將浪費(fèi)這些節(jié)點(diǎn)的位置優(yōu)勢(shì).由于這些節(jié)點(diǎn)位于網(wǎng)絡(luò)的中心位置，其將作用于更多的客戶端節(jié)點(diǎn)，因此，數(shù)據(jù)經(jīng)過(guò)Ⅱ類節(jié)點(diǎn)時(shí)應(yīng)該被存儲(chǔ)在最重要節(jié)點(diǎn)上.但所有Ⅱ類節(jié)點(diǎn)的重要性并不是一樣的，本文采用文獻(xiàn)[23]中所提供的節(jié)點(diǎn)重要性度量公式，對(duì)節(jié)點(diǎn)重要性進(jìn)行計(jì)算，其表達(dá)式為

(3)

其中,B(i)為節(jié)點(diǎn)vi的介數(shù)，C(j)表示節(jié)點(diǎn)vj的親密度，節(jié)點(diǎn)vj將自身的緊密度1C(j)貢獻(xiàn)給其相鄰節(jié)點(diǎn)，而非相鄰的節(jié)點(diǎn)則貢獻(xiàn)度為0.

H值不僅僅通過(guò)節(jié)點(diǎn)的介數(shù)值考慮了節(jié)點(diǎn)的位置，而且還將節(jié)點(diǎn)與其他節(jié)點(diǎn)的連接難易程度考慮其中，通過(guò)實(shí)驗(yàn)驗(yàn)證，該值更能全面地描述網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性.

當(dāng)數(shù)據(jù)經(jīng)過(guò)Ⅱ類節(jié)點(diǎn)時(shí)，如果將數(shù)據(jù)存儲(chǔ)在H值最大的節(jié)點(diǎn)中，可以使該數(shù)據(jù)為更多的客戶端節(jié)點(diǎn)請(qǐng)求服務(wù).但是，一旦當(dāng)網(wǎng)絡(luò)確定時(shí)，網(wǎng)絡(luò)中節(jié)點(diǎn)的位置便固定了，其H值也將會(huì)被固定，因此，H值大的節(jié)點(diǎn)將產(chǎn)生很大的負(fù)載，而H值相對(duì)較小的節(jié)點(diǎn)卻顯得空閑.這樣一來(lái)將會(huì)導(dǎo)致H值大的節(jié)點(diǎn)中的數(shù)據(jù)頻繁地被替換，致使請(qǐng)求的網(wǎng)內(nèi)命中率大大降低，而其他Ⅱ類節(jié)點(diǎn)的資源得不到利用.

針對(duì)以上問(wèn)題，本文給出了較好的解決方法.由于每個(gè)客戶端節(jié)點(diǎn)對(duì)數(shù)據(jù)的“喜好”往往不同，并且客戶端對(duì)數(shù)據(jù)的請(qǐng)求具有實(shí)時(shí)性，因此，不同客戶端對(duì)數(shù)據(jù)請(qǐng)求往往不同以及同一客戶端在不同時(shí)刻對(duì)數(shù)據(jù)請(qǐng)求也不相同，這樣將會(huì)使同一數(shù)據(jù)在不同網(wǎng)內(nèi)節(jié)點(diǎn)(主要考慮Ⅱ類節(jié)點(diǎn))表現(xiàn)出不同的流行度.本文針對(duì)具體數(shù)據(jù)實(shí)時(shí)地判斷數(shù)據(jù)所經(jīng)過(guò)的節(jié)點(diǎn)哪一個(gè)對(duì)當(dāng)前數(shù)據(jù)的需求較大，并將該需求與節(jié)點(diǎn)的H值相結(jié)合，從而使數(shù)據(jù)能夠動(dòng)態(tài)地存儲(chǔ)在不同的節(jié)點(diǎn)上，而并非某一H值較大節(jié)點(diǎn).由于數(shù)據(jù)的請(qǐng)求頻率能夠很好地度量一個(gè)數(shù)據(jù)的流行度，本文將數(shù)據(jù)的請(qǐng)求頻率看作節(jié)點(diǎn)對(duì)此數(shù)據(jù)的需求.因此，給出節(jié)點(diǎn)vi關(guān)于數(shù)據(jù)q的需求Diq為

(4)

其中，fiq表示節(jié)點(diǎn)vi中數(shù)據(jù)q的請(qǐng)求頻率，并設(shè)節(jié)點(diǎn)vi的大小為m(即能夠存儲(chǔ)m個(gè)數(shù)據(jù)塊).

式(4)雖然能夠很好地表示出具體數(shù)據(jù)在某一節(jié)點(diǎn)的需求，但很明顯式 (4)不具備實(shí)時(shí)性.如果某一數(shù)據(jù)在一段時(shí)間內(nèi)得到了大量的請(qǐng)求，但是在其后的很長(zhǎng)一段時(shí)間內(nèi)都沒(méi)有請(qǐng)求該數(shù)據(jù)，但由于前一段時(shí)間的高頻率請(qǐng)求導(dǎo)致其有較大的D值，從而不能實(shí)時(shí)地反映出數(shù)據(jù)當(dāng)時(shí)的情況.因此，為了減少該問(wèn)題帶來(lái)的影響，現(xiàn)給出式(5)表示節(jié)點(diǎn)vi對(duì)數(shù)據(jù)q需求的實(shí)時(shí)表達(dá)式.

(5)

(6)

其中，tgap表示q數(shù)據(jù)2次請(qǐng)求的時(shí)間間隔,tcurrent表示本次請(qǐng)求到達(dá)節(jié)點(diǎn)的時(shí)刻，told表示該請(qǐng)求上次到達(dá)該節(jié)點(diǎn)的請(qǐng)求時(shí)刻.

由式(3)與式(5)可得節(jié)點(diǎn)vi對(duì)數(shù)據(jù)q的重要性的實(shí)時(shí)度量為

(7)

(8)

當(dāng)請(qǐng)求包經(jīng)過(guò)某一Ⅱ類節(jié)點(diǎn)時(shí)，將得此節(jié)點(diǎn)針對(duì)當(dāng)前數(shù)據(jù)的W值，然后將該值添加到請(qǐng)求包中，當(dāng)請(qǐng)求包到達(dá)下一節(jié)點(diǎn)時(shí)得到當(dāng)前數(shù)據(jù)在此節(jié)點(diǎn)的W值，并將其與請(qǐng)求包中的W值進(jìn)行比較，將較大者加入到請(qǐng)求包中，以此類推.當(dāng)數(shù)據(jù)包返回時(shí)根據(jù)請(qǐng)求包傳給它的W值找到對(duì)應(yīng)的節(jié)點(diǎn)，將數(shù)據(jù)緩存在該節(jié)點(diǎn)(即式(8)中的vkq)中即可.

2.2節(jié)完整地描述了BNC策略在Ⅰ類節(jié)點(diǎn)與Ⅱ類節(jié)點(diǎn)的緩存機(jī)制的實(shí)現(xiàn).當(dāng)請(qǐng)求在Ⅰ類節(jié)點(diǎn)就被滿足時(shí)(即請(qǐng)求包跳數(shù)小于3時(shí)被滿足)，這時(shí)數(shù)據(jù)在返回客戶端的過(guò)程中只需要按照數(shù)據(jù)在Ⅰ類節(jié)點(diǎn)中的存儲(chǔ)策略緩存數(shù)據(jù).反之，數(shù)據(jù)包返回的過(guò)程中，將經(jīng)過(guò)Ⅰ類節(jié)點(diǎn)與Ⅱ類節(jié)點(diǎn)這2類節(jié)點(diǎn)，此時(shí)，數(shù)據(jù)將在經(jīng)過(guò)的這2類節(jié)點(diǎn)中分別存儲(chǔ)1次，其具體緩存策略嚴(yán)格按照Ⅰ類節(jié)點(diǎn)與Ⅱ類節(jié)點(diǎn)的存儲(chǔ)策略執(zhí)行.為了更清晰地說(shuō)明BNC緩存策略的實(shí)現(xiàn)過(guò)程，偽代碼1給出了整個(gè)BNC策略實(shí)現(xiàn)的偽代碼.為了將Ⅰ類節(jié)點(diǎn)與Ⅱ類節(jié)點(diǎn)作為一個(gè)整體處理，偽代碼不以節(jié)點(diǎn)類型的形式給出，而是分興趣包與數(shù)據(jù)包2部分給出.

偽代碼1. BNC策略實(shí)現(xiàn)偽代碼.

1) 興趣包處理偽代碼：

耳石癥是一種當(dāng)頭部快速移動(dòng)時(shí)出現(xiàn)眩暈和位置性眼震的眩暈癥,發(fā)病率隨年齡增長(zhǎng),且女性發(fā)病率高于男性,嚴(yán)重影響患者生活質(zhì)量。關(guān)于耳石癥的發(fā)病機(jī)理,目前主流觀點(diǎn)認(rèn)為是由于耳石變形脫落(可能由重大外力撞擊或衰老導(dǎo)致)移動(dòng)到其它平衡器官造成眩暈。臨床上常采用手法復(fù)位來(lái)使耳石復(fù)位進(jìn)行治療,Epley手法復(fù)位和Barbecue翻滾手法復(fù)位是當(dāng)前臨床上較為常見(jiàn)的用于治療耳石癥的復(fù)位手法,Epley手法復(fù)位通過(guò)移動(dòng)患者頭部,在重力的作用下使耳石復(fù)位,Barbecue翻滾手法復(fù)位是根據(jù)耳石假說(shuō)和前庭結(jié)構(gòu)解剖學(xué)關(guān)系來(lái)移動(dòng)患者頭部使耳石復(fù)位。

假設(shè)當(dāng)前節(jié)點(diǎn)為v，用戶請(qǐng)求的數(shù)據(jù)為q;

if (節(jié)點(diǎn)v沒(méi)有存儲(chǔ)請(qǐng)求對(duì)應(yīng)數(shù)據(jù)，并且當(dāng)前節(jié)點(diǎn)到客戶端的距離hop<3)

轉(zhuǎn)發(fā)請(qǐng)求到下一節(jié)點(diǎn);

end if

if (節(jié)點(diǎn)v沒(méi)有存儲(chǔ)請(qǐng)求對(duì)應(yīng)數(shù)據(jù)，并且當(dāng)前節(jié)點(diǎn)到客戶端的距離hop>3)

得到節(jié)點(diǎn)v的id;

for each (i=0 ton)*n為節(jié)點(diǎn)個(gè)數(shù)*

end for

for each (fvi,i=0 tom)

得到數(shù)據(jù)q在節(jié)點(diǎn)v的Mvq(ttag);

end for

得到Wvq=H(v)×Mvq(ttag);

得到請(qǐng)求包中攜帶的上游節(jié)點(diǎn)的Winterest值;

if (Winterest

用Wvq替換請(qǐng)求包中的Winterest值;

轉(zhuǎn)發(fā)請(qǐng)求到下一跳節(jié)點(diǎn);

end if

end if

if (節(jié)點(diǎn)v存儲(chǔ)了請(qǐng)求對(duì)應(yīng)數(shù)據(jù)，且節(jié)點(diǎn)v到客戶端的距離hop>3)

添加Winterest到數(shù)據(jù)包;

添加緩存次數(shù)copyNum=2到數(shù)據(jù)包;

返回?cái)?shù)據(jù)包;

end if

if (節(jié)點(diǎn)v存儲(chǔ)了請(qǐng)求對(duì)應(yīng)數(shù)據(jù)，且節(jié)點(diǎn)v到客戶端的距離1

從存儲(chǔ)列表中得到數(shù)據(jù)的位置rate;*rate為從隊(duì)頭開(kāi)始數(shù)據(jù)在隊(duì)列中的位置與隊(duì)列中的數(shù)據(jù)個(gè)數(shù)的比值*

if (rate≤0.7)

添加copyNum=0到數(shù)據(jù)包中;

else

添加copyNum=1到數(shù)據(jù)包中;

end if

返回?cái)?shù)據(jù)包;

end if

2) 數(shù)據(jù)包處理偽代碼

從數(shù)據(jù)包中獲得本節(jié)點(diǎn)到客戶端的距離hop與緩存次數(shù)copyNum;

if (hop>3)

得到本節(jié)點(diǎn)的Wvq;

得到數(shù)據(jù)包中攜帶的W值;

if (W=Wvq)

將數(shù)據(jù)緩存到節(jié)點(diǎn)的CS中;

copyNum=copyNum-1;

添加copyNum到數(shù)據(jù)包中;

轉(zhuǎn)發(fā)數(shù)據(jù)包到下一節(jié)點(diǎn);

end if

end if

else if ((hop<3 &©Num=1)‖

(copyNum=1 &&hop=3))

緩存數(shù)據(jù)到節(jié)點(diǎn)的CS中;

copyNum=copyNum-1;

添加copyNum到數(shù)據(jù)包中;

轉(zhuǎn)發(fā)數(shù)據(jù)包到下一節(jié)點(diǎn);

end else if

else

轉(zhuǎn)發(fā)數(shù)據(jù)包到下一節(jié)點(diǎn);

end else

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

本文研究的是在NDN中怎樣放置數(shù)據(jù)(數(shù)據(jù)存儲(chǔ)在哪些節(jié)點(diǎn)上)，而不涉及節(jié)點(diǎn)中數(shù)據(jù)的替換策略.LRU是一個(gè)被普遍使用的數(shù)據(jù)替換策略，因此，在實(shí)驗(yàn)中所有的數(shù)據(jù)替換策略都使用LRU策略.為了更好地體現(xiàn)出BNC策略的優(yōu)越性，本文將NDN中傳統(tǒng)的處處緩存策略(LCE)作為對(duì)比算法之一.另外選取2種新近提出的數(shù)據(jù)緩存策略Betw與ProbCache作為對(duì)比算法.其中，Betw是一種基于介數(shù)的緩存機(jī)制；ProbCache是一種基于鏈路節(jié)點(diǎn)緩存能力與節(jié)點(diǎn)所在位置的概率存儲(chǔ)機(jī)制.

本文為了更全面地衡量BNC策略性能的優(yōu)越性，將參考多個(gè)參數(shù)對(duì)BNC與LCE,Betw,Prob-Cache數(shù)據(jù)存儲(chǔ)策略進(jìn)行對(duì)比.其中包括請(qǐng)求網(wǎng)內(nèi)平均命中率β、平均請(qǐng)求跳數(shù)γ、平均命中時(shí)延δ.同時(shí)還分別針對(duì)緩存相對(duì)大小(relative cache size)與Zipf參數(shù)(Zipf parameter α)[24]分別進(jìn)行分析.

3.1性能參數(shù)

NDN與傳統(tǒng)網(wǎng)絡(luò)架構(gòu)有所不同，由于NDN中每個(gè)節(jié)點(diǎn)都具有緩存數(shù)據(jù)的功能，因此，請(qǐng)求很有可能在中間節(jié)點(diǎn)就被滿足而無(wú)需到達(dá)OCS節(jié)點(diǎn)，這樣不僅可以減少用戶請(qǐng)求數(shù)據(jù)的時(shí)延與命中跳數(shù)，還能使OCS節(jié)點(diǎn)的負(fù)載減小.因此，在度量NDN性能的參數(shù)上也與傳統(tǒng)網(wǎng)絡(luò)有所區(qū)別.為了更好地理解實(shí)驗(yàn)結(jié)果，現(xiàn)將本文用到的性能指標(biāo)定義給出如下：

1) 請(qǐng)求網(wǎng)內(nèi)平均命中率β.請(qǐng)求網(wǎng)內(nèi)命中率能夠很好地衡量對(duì)NDN網(wǎng)內(nèi)節(jié)點(diǎn)緩存的利用效率.β值越高說(shuō)明請(qǐng)求的網(wǎng)內(nèi)命中率也就越高，緩存的利用效率也就越高.

2) 平均請(qǐng)求跳數(shù)γ.平均請(qǐng)求跳數(shù)用于衡量數(shù)據(jù)請(qǐng)求的平均距離(請(qǐng)求數(shù)據(jù)所經(jīng)過(guò)的節(jié)點(diǎn)數(shù))，一個(gè)好的替換策略應(yīng)該使請(qǐng)求在較近的范圍內(nèi)被滿足.因此，γ值越小說(shuō)明數(shù)據(jù)被滿足的平均距離越小，請(qǐng)求的效率越高.

3) 平均命中時(shí)延δ.這應(yīng)該是最直接表示客戶端滿意度的參數(shù)，如果在沒(méi)有其他條件影響的情況下，跳數(shù)越小時(shí)延應(yīng)該越小，但時(shí)延往往受帶寬以及服務(wù)器位置的影響.δ值越小表示用戶獲取數(shù)據(jù)的平均時(shí)間越短，這樣客戶度的滿意度越高.

3.2仿真環(huán)境與參數(shù)配置

本實(shí)驗(yàn)是在Ubuntu操作系統(tǒng)上基于NS3的ndnSIM[25]仿真平臺(tái)進(jìn)行仿真實(shí)驗(yàn).每個(gè)節(jié)點(diǎn)的容量大小相等為Ci，每個(gè)內(nèi)容的大小為Sm(本文每個(gè)內(nèi)容大小相等為1 024 KB)，每個(gè)節(jié)點(diǎn)緩存的內(nèi)容滿足關(guān)系：

(9)

在實(shí)驗(yàn)中分別取網(wǎng)內(nèi)節(jié)點(diǎn)CS的總?cè)萘繛閿?shù)據(jù)總?cè)萘康?0%～50%進(jìn)行實(shí)驗(yàn).為了考慮請(qǐng)求熱度變化對(duì)BNC的影響，本實(shí)驗(yàn)取Zipf參數(shù)α在0.2～1.0的變化范圍進(jìn)行實(shí)驗(yàn).

為了更好地驗(yàn)證本文提出的BNC策略的可擴(kuò)展性，本文分別在ARPA(advanced research project agency)網(wǎng)與隨機(jī)網(wǎng)絡(luò)拓?fù)?random topology, RT)上進(jìn)行實(shí)驗(yàn).其中，隨機(jī)拓?fù)渫ㄟ^(guò)BRITE拓?fù)渖善魃桑?種拓?fù)涞木唧w信息如表1所示:

Table 1　Information of Network Topology

客戶端請(qǐng)求到達(dá)服從泊松分布，其中，ARPA網(wǎng)中λ為每秒50個(gè)，在隨機(jī)拓?fù)渲笑藶槊棵?00個(gè).下面分別在2種網(wǎng)絡(luò)拓?fù)渲羞M(jìn)行實(shí)驗(yàn)，并對(duì)上述給出的相應(yīng)指標(biāo)進(jìn)行統(tǒng)計(jì)分析.

3.3ARPA網(wǎng)絡(luò)拓?fù)鋵?shí)驗(yàn)結(jié)果

3.3.1 緩存大小對(duì)策略的影響

一般情況下，網(wǎng)絡(luò)中節(jié)點(diǎn)的緩存大小將遠(yuǎn)遠(yuǎn)小于內(nèi)容的數(shù)量.本文為了考慮隨著網(wǎng)內(nèi)節(jié)點(diǎn)緩存大小的變化對(duì)BNC策略的影響，分別取節(jié)點(diǎn)總?cè)萘繛閿?shù)據(jù)總量的10%～50%之間的9個(gè)位置作為實(shí)驗(yàn)點(diǎn)，從而觀察BNC隨著網(wǎng)內(nèi)緩存總?cè)萘康淖兓瘜?duì)其性能的影響.

Fig. 3　The impact of total cache capacity in ARPAnetwork topology on schemes.圖3　ARPA網(wǎng)絡(luò)拓?fù)渲写鎯?chǔ)總?cè)萘繉?duì)策略的影響

如圖3(a)所示，隨著網(wǎng)內(nèi)緩存總?cè)萘康脑黾樱?種策略的命中率都有顯著的提高.因?yàn)?，?dāng)網(wǎng)內(nèi)緩存總?cè)萘吭黾訒r(shí)，將有更多的數(shù)據(jù)被緩存在網(wǎng)內(nèi)節(jié)點(diǎn)，因此，更多的請(qǐng)求被滿足，從而使其命中率增加.相對(duì)于其他3種緩存策略而言，本文提出的BNC策略有更高的命中率.BNC策略最大命中率要比傳統(tǒng)LCE策略最大命中率高9%左右.與新近提出的Betw策略與ProbCache策略相比,BNC命中率也明顯較高.

高的命中率不一定與較低的命中跳數(shù)和時(shí)延相關(guān).例如一個(gè)請(qǐng)求在2個(gè)不同節(jié)點(diǎn)請(qǐng)求到相應(yīng)數(shù)據(jù)所需要的跳數(shù)往往是不一樣的；但跳數(shù)的遠(yuǎn)近與時(shí)延的大小往往相關(guān)聯(lián).然而，時(shí)延也受到帶寬等的影響，如圖3(b)與圖3(c)所示.無(wú)論是在請(qǐng)求時(shí)延還是請(qǐng)求跳數(shù)上BNC策略都明顯優(yōu)于其他3種策略，BNC策略與LCE策略相比平均跳數(shù)最大相差2跳左右，時(shí)延相差達(dá)到了0.0175 s左右.BNC策略與Betw,ProbCache策略相比在時(shí)延與跳數(shù)性能上也有明顯優(yōu)勢(shì).

3.3.2 Zipf參數(shù)α對(duì)策略的影響

由于用戶請(qǐng)求服從Zipf分布已經(jīng)成為了大家的共識(shí)，當(dāng)Zipf參數(shù)α越大時(shí)，表示用戶請(qǐng)求的數(shù)據(jù)越集中.即隨著Zipf參數(shù)α的增大，具有高請(qǐng)求頻率的數(shù)據(jù)種類將減少.在本實(shí)驗(yàn)中，為了研究用戶請(qǐng)求熱度變化對(duì)緩存策略的影響，分別對(duì)Zipf參數(shù)α在0.2～1.0的取值范圍的情況進(jìn)行實(shí)驗(yàn).

如圖4(a)所示，當(dāng)Zipf參數(shù)α增加時(shí)，請(qǐng)求命中率都相應(yīng)增加，因?yàn)殡S著Zipf參數(shù)α的增加用戶請(qǐng)求的數(shù)據(jù)類型越來(lái)越集中，因此，節(jié)點(diǎn)緩存的數(shù)據(jù)越來(lái)越容易滿足客戶端的請(qǐng)求.由圖4(a)可以看出，BNC策略的命中率相對(duì)于其他3種策略較高；在Zipf參數(shù)α=0.2時(shí)BNC策略與LCE策略相比命中率差值達(dá)到了7%左右，此時(shí)，LCE策略命中率卻不到5%，由此可見(jiàn)，BNC策略在Zipf參數(shù)α較小時(shí)性能遠(yuǎn)遠(yuǎn)好于傳統(tǒng)LCE策略；隨著Zipf參數(shù)α的增大，3種策略之間的差值在逐漸減小，但是BNC策略也明顯優(yōu)于其他3種策略.

Fig. 4　The impact of different Zipf parameter α inARPA network topology on schemes.圖4　ARPA網(wǎng)絡(luò)拓?fù)渲衂ipf參數(shù)α不同時(shí)對(duì)策略的影響

如圖4(b)與圖4(c)所示，隨著Zipf參數(shù)α的增加，用戶數(shù)據(jù)請(qǐng)求時(shí)延與跳數(shù)都隨之減小.由圖4可以看出，BNC策略下用戶請(qǐng)求數(shù)據(jù)的平均時(shí)延與跳數(shù)遠(yuǎn)遠(yuǎn)小于Betw,ProbCache,LCE策略.Zipf參數(shù)α=0.2時(shí)BNC策略與LCE策略相比時(shí)延差值達(dá)到0.02 s左右，此時(shí)，請(qǐng)求跳數(shù)差值達(dá)到1.1跳左右；在整個(gè)取值區(qū)間內(nèi)，BNC策略在請(qǐng)求時(shí)延與跳數(shù)性能上優(yōu)于其他3種策略.

3.4隨機(jī)網(wǎng)絡(luò)拓?fù)?RT)實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本文提出的策略的可擴(kuò)展性，因此，提供了在隨機(jī)拓?fù)渲械姆抡娼Y(jié)果，從仿真結(jié)果來(lái)看，本文提出的BNC策略性能明顯優(yōu)于其他3種對(duì)比策略.

3.4.1緩存大小對(duì)策略的影響

Fig. 5　The impact of total cache capacity in Randomnetwork topology on schemes.圖5　隨機(jī)網(wǎng)絡(luò)拓?fù)渲写鎯?chǔ)總?cè)萘繉?duì)策略的影響

由圖5(a)可以看出，在隨機(jī)拓?fù)渲须S著緩存的增加，4種策略的命中率都大大提高；但是，本文提出的BNC策略性能明顯優(yōu)于其他3種策略，當(dāng)緩存容量為總?cè)萘康?0%時(shí)，BNC策略的命中率可以達(dá)到30%以上.但由于隨機(jī)拓?fù)涔?jié)點(diǎn)的差異性巨大，因此，從圖5(a)可以看出Betw策略的性能不佳.

在圖5(b)與圖5(c)可以看出，本文提出的BNC策略在平均請(qǐng)求時(shí)延與平均請(qǐng)求跳數(shù)上性能優(yōu)于Betw,ProbCache,LCE策略.

3.4.2Zipf參數(shù)α對(duì)策略的影響

Fig. 6　The impact of Zipf parameter α in Randomnetwork topology on schemes.圖6　隨機(jī)網(wǎng)絡(luò)拓?fù)渲衂ipf參數(shù)α對(duì)策略的影響

由圖6可以看出，BNC策略在平均請(qǐng)求命中率、時(shí)延、跳數(shù)等性能上明顯優(yōu)于Betw,ProbCache,LCE三種策略.在圖6(a)中，Zipf參數(shù)α增加時(shí)，4種策略的請(qǐng)求命中率都相應(yīng)增加；但是，本文所提出的策略命中率遠(yuǎn)高于其他3種策略.本文提出的命中率與對(duì)比算法的命中率最大差值可達(dá)到15個(gè)百分點(diǎn).

在圖6(b)與圖6(c)可以看出，BNC策略在用戶體驗(yàn)上也明顯優(yōu)于其他3種對(duì)比策略；其用戶請(qǐng)求時(shí)延與數(shù)據(jù)傳輸跳數(shù)都較其他3種策略小，這樣將提高用戶體驗(yàn).

4結(jié)束語(yǔ)

為了解決數(shù)據(jù)包返回客戶端過(guò)程中的數(shù)據(jù)緩存位置的問(wèn)題，本文將數(shù)據(jù)返回客戶端所經(jīng)節(jié)點(diǎn)進(jìn)行分類處理，由于不同類型節(jié)點(diǎn)的作用對(duì)象不同，本文分別采用不同的緩存方式，提出了一種全新的數(shù)據(jù)存儲(chǔ)策略BNC.該策略大大減少了網(wǎng)內(nèi)節(jié)點(diǎn)的冗余數(shù)據(jù)，同時(shí)在滿足當(dāng)前客戶端節(jié)點(diǎn)的同時(shí)還滿足了其他客戶端節(jié)點(diǎn)的需求.通過(guò)與傳統(tǒng)的LCE策略以及新近提出的Betw,ProbCache策略相比，本文提出的BNC策略在增加請(qǐng)求命中率的同時(shí)也減少了用戶的請(qǐng)求時(shí)延與跳數(shù)，從而使整個(gè)網(wǎng)絡(luò)的性能得到提升.

參考文獻(xiàn)

[1]Feldmann A. Internet clean-slate design: What and why?[J]. ACM SIGCOMM Computer Communication Review, 2007, 37(3): 59-64

[2]Cheriton D R, Gritter M. TRIAD: A scalable deployable NAT-based Internet architecture[R]. Palo Alto, CA: Stanford University, 2000

[3]Koponen T, Chawla M, Chun B G, et al. A data-oriented (and beyond) network architecture[J]. ACM SIGCOMM Computer Communication Review, 2007, 37(4): 181-192

[4]Han D, Anand A, Dogar F, et al. XIA: Efficient support for evolvable inter-networking[C] //Proc of the 9th USENIX Conf on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2012: 23-23

[5]The FP7 4WARD Project[OL]. European Commission: FP7, 2008 [2014-10-10]. http://www.4ward-project.eu

[6]Scalable and Adaptive Internet Solutions (SAIL)[OL]. European Commission: FP7, 2010 [2014-10-10]. http://www.sail-project.eu

[7]Content mediator architecture for content-aware networks (COMET)[OL]. Madrid: EU ICT, 2010 [2014-10-10].http://www.comet-project.org

[8]Jacobson V, Smetters D K, Thornton J D, et al. Networking named content[C] //Proc of the 5th ACM Int Conf on Emerging Networking Experiments and Technologies (CoNEXT’09). New York: ACM, 2009: 1-12

[9]Fayazbakhsh S K, Lin Y, Tootoonchian A. Less pain, most of the gain: Incrementally deployable ICN[J]. ACM SIGCOMM Computer Communication Review, 2013, 43(3): 147-158

[10]Wang Yonggong, Li Zhenyu, Tyson Gareth, et al. Optimal cache allocation for content centric networking[C] //Proc of the 21st IEEE Int Conf on Network Protocols (ICNP 2013). Piscataway, NJ: IEEE, 2013: 1-10

[11]Wang Jingyuan, Li Chao, Xiong Zhang, et al. Survey of data centric smart city[J]. Journal of Computer Research and Development, 2014, 51(2): 239-259 (in Chinese)(王靜遠(yuǎn), 李超, 熊璋, 等. 以數(shù)據(jù)為中心的智慧城市研究綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(2): 239-259)

[12]Ghodsi A, Shenker S, Koponen T, et al. Information centric networking: Seeing the forest for the trees[C] //Proc of the 10th ACM Workshop on Hot Topics in Networks (HotNets-X). New York: ACM, 2011: 1-12

[13]Jacobson V, Smetters D K, Thornton J D, et al. Networking named content[J]. Communications of the ACM, 2012, 55(1): 117-124

[14]Xie Gaogang, Zhang Yujun, Li Zhenyu, et al. A survey on future Internet architecture[J]. Chinese Journal of Computers, 2012, 35(6): 1109-1119 (in Chinese)(謝高崗, 張玉軍, 李振宇, 等. 未來(lái)互聯(lián)網(wǎng)體系結(jié)構(gòu)研究綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(6): 1109-1119)

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

[16]Xylomenos G, Ververidis C, Siris V, et al. A survey of information-centric networking research[J]. IEEE Com-munications Surveys & Tutorials, 2013, 16(2): 1024-1049

[17]Laoutaris N, Syntila S, Stavrakakis I. Meta algorithms for hierarchical Web caches[C] //Proc of the 23rd IEEE Int Performance, Computing, and Communications Conf. Piscataway, NJ: IEEE, 2004: 445-452

[18]Laoutaris N, Che H, Stavrakakis I. The LCD interconnection of LRU caches and its analysis[J]. Performance Evaluation, 2006, 63(7): 609-634

[19]Liu Waixi, Yu Shunzheng, Hu Xiao, et al. Selective caching in content centric networking[J]. Chinese Journal of Computers, 2014, 37(2): 275-288 (in Chinese)(劉外喜, 余順爭(zhēng), 胡曉, 等. CCN中選擇性緩存機(jī)制的研究[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(2): 275-288)

[20]Chai Weikoong, He Diliang, Ioannis P, et al. Cache “Less for More” in information centric networks[C] //Proc of the 11th Int IFIP TC6 Networking Conf (NETWORKING 2012). Berlin: Springer, 2012: 27-40

[21]Li J, Wu H, Liu B, et al. Popularity-driven coordinated caching in named data networking[C] //Proc of the 8th ACM/IEEE Symp on Architectures for Networking and Communications Systems. New York: ACM, 2012: 15-26

[22]Psaras I, Chai W K, Pavlou G. Probabilistic in-network caching for information centric networks[C] //Proc of the 2nd ACM SIGCOMM Information-Centric Networking Workshop (ICN 2012). New York: ACM, 2012: 55-60

[23]Zhang Xiaojuan, Wang Xufeng. Evaluation formula for communication network node importance[J]. Journal of Northeastern University, 2014, 35(5): 663-666 (in Chinese)(張小娟, 王旭峰. 一種通信網(wǎng)絡(luò)節(jié)點(diǎn)重要性計(jì)算公式[J]. 東北大學(xué)學(xué)報(bào), 2014, 35(5): 663-666)

[24]Breslau I, Cao P, Fan I, et al. Web caching and Zipf-like distributions: Evidence and implications[C] //Proc of the 18th Annual Joint Conf of the IEEE Computer and Communications Societies: The Future is Now (INFOCOM’99). Piscataway, NJ: IEEE,1999: 126-134

[25]Afanasyev A, Moiseenko I, Zhang L. ndnSIM: NDN simulator for NS-3, NDN-0005[R]. Los Angeles, CA: University of California, Los Angeles, 2012

Huang Sheng, born in 1974. Received his MS degree from Huazhong University of Science & Technology and his PhD degree from Chongqing University in 2003 and 2008, respectively. Member of China Computer Federation. His main research interests include optical communication system, channel coding and named data networking.

Teng Mingnian, born in 1991. Master candidate. Received his bachelor’s degree from Qiqihar University in 2013. His current research interests include data packet caching in named data networking.

Wu Zhen, born in 1990. Master candidate. Received his bachelor’s degree from Hunan First Normal University in 2013. His current research interests include named data networking.

Xu Jianghua, born in 1990. Master candidate. Received his bachelor’s degree from Taiyuan University of Science and Technology in 2013. His current research interests include IP lookup and name lookup in CCN.

Ji Ruijun, born in 1990. Master candidate. Received his bachelor’s degree from Chongqing University of Posts and Telecommunications in 2013. His current research interests include LT code.

A Data Caching Scheme Based on Node Classification in Named Data Networking

Huang Sheng, Teng Mingnian, Wu Zhen, Xu Jianghua, and Ji Ruijun

(KeyLaboratoryofOpticalFiberCommunicationTechnology,ChongqingUniversityofPostsandTelecommunications,Chongqing400065)

AbstractCompared with the traditional Internet, in-networking caching is one of the most distinguishable features in named data networking (NDN). In NDN, a node caches every passing data packet as a default model. The caching scheme generates a large number of redundant data in in-networking. As a consequence, the networking cache resource is wasted seriously. To solve the problem, a caching scheme based on node classification (BNC) is proposed firstly in this paper. Based on different node positions, the nodes that data packet passes through are divided into two types: “edge” type and “core” type. When data packet passes through the “core” type nodes, by considering location and data popularity distribution at different nodes, it is cached in a node which is beneficial to other nodes. When the data packet passes through the “edge” nodes, a node is selected through data popularity to be beneficial to the client. The simulation results show that the proposed scheme can efficiently improve the in-network hit ratio and reduce the delay and hops of getting the data packet.

Key wordsnamed data networking (NDN); node classification caching scheme; in-network caching; redundant data; content centric networking

收稿日期：2014-10-13；修回日期：2015-03-26

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61371096,61275077);國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2012CB315803);重慶市自然科學(xué)基金項(xiàng)目(cstc2013jcyjA40052);重慶市教委科學(xué)技術(shù)研究項(xiàng)目(KJ130515)

通信作者：滕明埝(tengmingnianzbb@163.com)

中圖法分類號(hào)TP393

This work was supported by the National Natural Science Foundation of China (61371096,61275077), the National Basic Research Program of China (973 Program) (2012CB315803), the Natural Science Foundation of Chongqing (cstc2013jcyjA40052), and the Scientific and Technological Research Program of Chongqing Municipal Education Commission (KJ130515).