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

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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

1NDN緩存策略常見問題

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

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

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

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

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

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

2BNC數(shù)據(jù)存儲策略運行機制

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

2.1BNC基本思想

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

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

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

2.2BNC策略實現(xiàn)

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

2.2.1 “邊緣”類節(jié)點(Ⅰ類)存儲策略實現(xiàn)

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

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

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

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

2.2.2“核心”類節(jié)點(Ⅱ類)存儲策略實現(xiàn)

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

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

(1)

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

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

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

(2)

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

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

(3)

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

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

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

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

(4)

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

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

(5)

(6)

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

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

(7)

(8)

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

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

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

1) 興趣包處理偽代碼：

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

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

if (節(jié)點v沒有存儲請求對應(yīng)數(shù)據(jù)，并且當(dāng)前節(jié)點到客戶端的距離hop<3)

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

end if

if (節(jié)點v沒有存儲請求對應(yīng)數(shù)據(jù)，并且當(dāng)前節(jié)點到客戶端的距離hop>3)

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

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

end for

for each (fvi,i=0 tom)

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

end for

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

得到請求包中攜帶的上游節(jié)點的Winterest值;

if (Winterest

用Wvq替換請求包中的Winterest值;

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

end if

end if

if (節(jié)點v存儲了請求對應(yīng)數(shù)據(jù)，且節(jié)點v到客戶端的距離hop>3)

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

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

返回數(shù)據(jù)包;

end if

if (節(jié)點v存儲了請求對應(yīng)數(shù)據(jù)，且節(jié)點v到客戶端的距離1

從存儲列表中得到數(shù)據(jù)的位置rate;*rate為從隊頭開始數(shù)據(jù)在隊列中的位置與隊列中的數(shù)據(jù)個數(shù)的比值*

if (rate≤0.7)

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

else

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

end if

返回數(shù)據(jù)包;

end if

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

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

if (hop>3)

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

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

if (W=Wvq)

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

copyNum=copyNum-1;

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

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

end if

end if

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

(copyNum=1 &&hop=3))

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

copyNum=copyNum-1;

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

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

end else if

else

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

end else

3仿真實驗

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

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

3.1性能參數(shù)

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

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

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

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

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

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

(9)

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

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

Table 1　Information of Network Topology

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

3.3ARPA網(wǎng)絡(luò)拓?fù)鋵嶒灲Y(jié)果

3.3.1 緩存大小對策略的影響

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

Fig. 3　The impact of total cache capacity in ARPAnetwork topology on schemes.圖3　ARPA網(wǎng)絡(luò)拓?fù)渲写鎯側(cè)萘繉Σ呗缘挠绊?/p>

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

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

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

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

如圖4(a)所示，當(dāng)Zipf參數(shù)α增加時，請求命中率都相應(yīng)增加，因為隨著Zipf參數(shù)α的增加用戶請求的數(shù)據(jù)類型越來越集中，因此，節(jié)點緩存的數(shù)據(jù)越來越容易滿足客戶端的請求.由圖4(a)可以看出，BNC策略的命中率相對于其他3種策略較高；在Zipf參數(shù)α=0.2時BNC策略與LCE策略相比命中率差值達(dá)到了7%左右，此時，LCE策略命中率卻不到5%，由此可見，BNC策略在Zipf參數(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ù)α不同時對策略的影響

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

3.4隨機網(wǎng)絡(luò)拓?fù)?RT)實驗結(jié)果

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

3.4.1緩存大小對策略的影響

Fig. 5　The impact of total cache capacity in Randomnetwork topology on schemes.圖5　隨機網(wǎng)絡(luò)拓?fù)渲写鎯側(cè)萘繉Σ呗缘挠绊?/p>

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

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

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

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

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

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

4結(jié)束語

為了解決數(shù)據(jù)包返回客戶端過程中的數(shù)據(jù)緩存位置的問題，本文將數(shù)據(jù)返回客戶端所經(jīng)節(jié)點進(jìn)行分類處理，由于不同類型節(jié)點的作用對象不同，本文分別采用不同的緩存方式，提出了一種全新的數(shù)據(jù)存儲策略BNC.該策略大大減少了網(wǎng)內(nèi)節(jié)點的冗余數(shù)據(jù)，同時在滿足當(dāng)前客戶端節(jié)點的同時還滿足了其他客戶端節(jié)點的需求.通過與傳統(tǒng)的LCE策略以及新近提出的Betw,ProbCache策略相比，本文提出的BNC策略在增加請求命中率的同時也減少了用戶的請求時延與跳數(shù)，從而使整個網(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]. 計算機研究與發(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)(謝高崗, 張玉軍, 李振宇, 等. 未來互聯(lián)網(wǎng)體系結(jié)構(gòu)研究綜述[J]. 計算機學(xué)報, 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)(劉外喜, 余順爭, 胡曉, 等. CCN中選擇性緩存機制的研究[J]. 計算機學(xué)報, 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é)點重要性計算公式[J]. 東北大學(xué)學(xué)報, 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

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

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

中圖法分類號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).