羅　熹，安　瑩，牛碧諾

(1.中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙　410083；2.中南大學(xué) 信息安全與大數(shù)據(jù)研究院，湖南 長沙　410083；3.湖南警察學(xué)院 信息技術(shù)系，湖南 長沙　410138；4.武漢大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢　430072)

?

內(nèi)容中心網(wǎng)絡(luò)中一種基于內(nèi)容擴(kuò)散的主動(dòng)緩存機(jī)制*

羅熹1,3，安瑩2?，牛碧諾4

(1.中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙410083；2.中南大學(xué) 信息安全與大數(shù)據(jù)研究院，湖南 長沙410083；3.湖南警察學(xué)院 信息技術(shù)系，湖南 長沙410138；4.武漢大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢430072)

借鑒分子擴(kuò)散的思想，提出一種基于內(nèi)容擴(kuò)散的主動(dòng)緩存機(jī)制(Content Diffusion Based Proactive Caching, CDBPC).該機(jī)制引入緩存內(nèi)容濃度的概念來描述不同內(nèi)容在不同區(qū)域內(nèi)的需求程度，然后根據(jù)節(jié)點(diǎn)間的緩存內(nèi)容濃度關(guān)系來驅(qū)動(dòng)內(nèi)容副本在網(wǎng)絡(luò)中的主動(dòng)推進(jìn)和遷移，并結(jié)合內(nèi)容的流行度等因素實(shí)現(xiàn)了緩存內(nèi)容的概率性放置，從而達(dá)到內(nèi)容緩存的快速部署和推進(jìn)，提高為用戶提供就近響應(yīng)概率的目的.仿真結(jié)果表明，該機(jī)制能有效地降低系統(tǒng)的平均接入代價(jià)并提高緩存命中率.

內(nèi)容中心網(wǎng)絡(luò)；擴(kuò)散原理；主動(dòng)緩存；內(nèi)容流行度

近年來，隨著P2P應(yīng)用、發(fā)布訂閱系統(tǒng)、普適計(jì)算以及海量流媒體等新型應(yīng)用的不斷發(fā)展，信息獲取已經(jīng)成為了當(dāng)前網(wǎng)絡(luò)服務(wù)的主體，傳統(tǒng)的以主機(jī)為中心的通信模式逐漸演變?yōu)橐孕畔橹行牡男履Ｊ?網(wǎng)絡(luò)通信方式的變化使得網(wǎng)絡(luò)設(shè)計(jì)者們必須對(duì)當(dāng)前的Internet體系架構(gòu)做出重大調(diào)整，從而導(dǎo)致了以內(nèi)容中心網(wǎng)絡(luò)(Content-Centric Networking，CCN)[1]為代表的一系列新型網(wǎng)絡(luò)的涌現(xiàn).在CCN中，內(nèi)容位置的重要性被逐漸弱化，網(wǎng)絡(luò)通過對(duì)內(nèi)容進(jìn)行統(tǒng)一命名，來實(shí)現(xiàn)基于內(nèi)容名稱的定位、路由和傳輸.同時(shí)，CCN要求每個(gè)具有存儲(chǔ)能力的節(jié)點(diǎn)都能緩存經(jīng)過的內(nèi)容，從而為其他用戶對(duì)同一內(nèi)容的后續(xù)請(qǐng)求提供快速的響應(yīng).換而言之，CCN將透明化、泛在化的網(wǎng)絡(luò)內(nèi)置緩存作為其網(wǎng)絡(luò)體系結(jié)構(gòu)中固有的一部分，以此加快內(nèi)容的分發(fā)速度并提高網(wǎng)絡(luò)資源的利用率.因此，CCN中的內(nèi)置緩存機(jī)制也就成為了目前該領(lǐng)域的研究熱點(diǎn)，其中一個(gè)重要的問題是如何選擇內(nèi)容的緩存位置，并且研究者們已經(jīng)就此開展了大量的研究工作.Psaras等人[2]提出了一種基于加權(quán)概率的緩存機(jī)制ProbCache，結(jié)合節(jié)點(diǎn)與請(qǐng)求者的距離和路徑的剩余緩存空間來計(jì)算內(nèi)容返回路徑上各沿途節(jié)點(diǎn)緩存內(nèi)容對(duì)象的概率，該概率與節(jié)點(diǎn)和內(nèi)容請(qǐng)求者間的距離成反比，而與節(jié)點(diǎn)的可用資源成正比.該機(jī)制通過將內(nèi)容以更高的概率緩存于距離請(qǐng)求者更近的節(jié)點(diǎn),來保證內(nèi)容副本快速地趨向網(wǎng)絡(luò)邊緣，從而提升系統(tǒng)的緩存性能.文獻(xiàn)[3-4]采用了相似的基本思想，通過為流行度高的內(nèi)容設(shè)置較長的緩存時(shí)間，保證流行內(nèi)容的緩存命中，并加快內(nèi)容獲取的響應(yīng)速度.文獻(xiàn)[5]采用了差異化緩存的方式，提出了一種結(jié)合空間存儲(chǔ)位置和緩存駐留時(shí)間的二維差異化緩存策略.該策略將一定時(shí)間間隔內(nèi)內(nèi)容被請(qǐng)求的次數(shù)定義為該內(nèi)容的活躍度，然后根據(jù)內(nèi)容活躍度的變化趨勢來決定下行節(jié)點(diǎn)是否對(duì)內(nèi)容進(jìn)行緩存，在空間維度上實(shí)現(xiàn)內(nèi)容緩存位置的逐跳推進(jìn).同時(shí)，通過賦予活躍度高的內(nèi)容更長的緩存時(shí)間，進(jìn)一步確保流行內(nèi)容盡可能地緩存在靠近用戶的網(wǎng)絡(luò)邊緣位置.劉外喜等人[6]提出了把內(nèi)容的放置、發(fā)現(xiàn)、替換統(tǒng)一起來考慮的APDR機(jī)制，實(shí)現(xiàn)內(nèi)容的有序緩存.APDR的主要思想是：Interest報(bào)文除了攜帶對(duì)內(nèi)容的請(qǐng)求，還收集沿途各節(jié)點(diǎn)對(duì)該內(nèi)容的潛在需求、空閑緩存等信息，使得Interest的匯聚點(diǎn)和目的地節(jié)點(diǎn)，可以據(jù)此計(jì)算出一個(gè)緩存方案，并把該方案附加在Data報(bào)文之上，通知返程途中的某些節(jié)點(diǎn)緩存該內(nèi)容并設(shè)置指定的緩存時(shí)間.文獻(xiàn)[7]根據(jù)用戶的潛在需求和內(nèi)容的流行規(guī)律，提出了一種選擇性緩存機(jī)制SC.作者認(rèn)為由于下游節(jié)點(diǎn)緩存的存在，節(jié)點(diǎn)上收到過某個(gè)內(nèi)容的請(qǐng)求并作出響應(yīng)的端口在未來一段時(shí)間內(nèi)不會(huì)再次收到對(duì)該內(nèi)容的請(qǐng)求.因此，對(duì)于某個(gè)內(nèi)容而言，節(jié)點(diǎn)上未請(qǐng)求過該內(nèi)容的端口數(shù)量越少，其對(duì)該內(nèi)容的潛在需求就越低，那么節(jié)點(diǎn)緩存該內(nèi)容的必要性也越小.在此基礎(chǔ)上，該機(jī)制通過結(jié)合鏈路利用率以及節(jié)點(diǎn)的可用緩存空間等因素計(jì)算內(nèi)容的緩存概率來實(shí)現(xiàn)內(nèi)容的選擇性緩存，以提升系統(tǒng)的緩存效率.Kyi等人[8]提出了一種基于一致性哈希算法的協(xié)作緩存決策機(jī)制，該機(jī)制將AS內(nèi)的路由節(jié)點(diǎn)分成不同的組，通過組內(nèi)路由節(jié)點(diǎn)間對(duì)內(nèi)容緩存和請(qǐng)求轉(zhuǎn)發(fā)的協(xié)同操作來提高緩存性能和資源利用率.在緩存決策時(shí)，各個(gè)路由節(jié)點(diǎn)主要考慮內(nèi)容的流行度并利用一致性哈希避免內(nèi)容的重復(fù)緩存.

CCN中內(nèi)容緩存的重要目的之一是逐步地使內(nèi)容副本接近請(qǐng)求用戶，從而縮短內(nèi)容的獲取延遲.然而，對(duì)于整個(gè)網(wǎng)絡(luò)范圍而言，內(nèi)容對(duì)象向網(wǎng)絡(luò)邊緣的復(fù)制往往是一個(gè)較為緩慢的過程[9].其主要原因是，現(xiàn)有的CCN緩存機(jī)制中，內(nèi)容的緩存決策大多和內(nèi)容的分發(fā)過程一樣均由用戶的興趣(Interest)驅(qū)動(dòng)，并采用路徑內(nèi)(on-path)緩存策略直接從Interest的反向路徑上的中間節(jié)點(diǎn)中選擇內(nèi)容緩存位置.這導(dǎo)致了兩方面的主要缺陷，其一，內(nèi)容的攜帶者(原始內(nèi)容服務(wù)器或中間緩存節(jié)點(diǎn))只有在收到相應(yīng)的Interest并在其緩存中發(fā)生命中后才會(huì)在響應(yīng)內(nèi)容的返回過程中觸發(fā)內(nèi)容緩存位置的決策，缺乏對(duì)內(nèi)容副本進(jìn)行主動(dòng)推進(jìn)的能力.這種過于被動(dòng)的方式顯然會(huì)延緩內(nèi)容緩存在網(wǎng)絡(luò)內(nèi)的部署速度，很大程度上它將受到Interest轉(zhuǎn)發(fā)策略的影響.其二，內(nèi)容緩存位置的選擇往往局限在原始內(nèi)容服務(wù)器與請(qǐng)求用戶節(jié)點(diǎn)的直接路徑上，未充分地考慮路徑外的節(jié)點(diǎn)狀態(tài)及用戶需求.文獻(xiàn)[10]指出路徑外(off-path)緩存策略在能耗等緩存性能上比路徑內(nèi)(on-path)緩存策略具有更大的優(yōu)勢.更重要的是，如果能根據(jù)節(jié)點(diǎn)未來的潛在需求，預(yù)先將內(nèi)容復(fù)制到當(dāng)前路徑以外的其他網(wǎng)絡(luò)區(qū)域，將能更進(jìn)一步地加快內(nèi)容查詢和獲取的速度，大大提升緩存系統(tǒng)的綜合性能.

針對(duì)上述問題，本文提出一種基于擴(kuò)散理論的主動(dòng)緩存機(jī)制.該機(jī)制不僅能根據(jù)收到的用戶請(qǐng)求沿著反向路徑選擇緩存內(nèi)容的放置位置，同時(shí)還通過借鑒分子動(dòng)理論中的擴(kuò)散原理，根據(jù)節(jié)點(diǎn)分布密度以及與內(nèi)容提供者和請(qǐng)求者間的距離來定義網(wǎng)絡(luò)中不同區(qū)域的緩存內(nèi)容濃度，然后將內(nèi)容副本由高濃度區(qū)域主動(dòng)擴(kuò)散到低濃度區(qū)域，實(shí)現(xiàn)內(nèi)容緩存節(jié)點(diǎn)的快速部署以及緩存位置的動(dòng)態(tài)調(diào)整，從而有效提高系統(tǒng)的緩存性能.根據(jù)現(xiàn)有的相關(guān)研究工作，部分學(xué)者也試圖通過引入物理場的概念來優(yōu)化CCN中的緩存決策問題.如文獻(xiàn)[11]中提出了一種基于勢能的目標(biāo)識(shí)別路由方法(Cache Aware Target iden Tification, CATT)，該方法引入勢場(potential field)的概念，將節(jié)點(diǎn)存儲(chǔ)的內(nèi)容副本沿勢能由高到低的方向進(jìn)行局部范圍通告，從而提高緩存資源的可用性.文獻(xiàn)[12]指出CCN中能夠響應(yīng)內(nèi)容請(qǐng)求的節(jié)點(diǎn)可以分為持久穩(wěn)定的原始內(nèi)容服務(wù)器和動(dòng)態(tài)可變的臨時(shí)緩存節(jié)點(diǎn)兩類，考慮到它們的差異化特征并結(jié)合數(shù)據(jù)場的思想，分別為其構(gòu)建全局導(dǎo)向和局部吸引的勢能輻射場，在路由查找過程中引導(dǎo)內(nèi)容請(qǐng)求的轉(zhuǎn)發(fā)，實(shí)現(xiàn)緩存內(nèi)容整體利用率的提升.文獻(xiàn)[13]則通過建立一個(gè)基于內(nèi)容的拓?fù)鋭輬?，用于擴(kuò)散網(wǎng)絡(luò)緩存副本的內(nèi)容通告，使網(wǎng)絡(luò)后續(xù)產(chǎn)生的用戶請(qǐng)求可以充分利用不在路徑上的內(nèi)容副本來選擇最佳的內(nèi)容響應(yīng)位置.然而這些方法均從優(yōu)化內(nèi)容副本通告或用戶請(qǐng)求轉(zhuǎn)發(fā)的角度來改進(jìn)內(nèi)容的緩存性能和網(wǎng)絡(luò)通信服務(wù)質(zhì)量.與之不同的是，我們提出的方法是通過構(gòu)建內(nèi)容在網(wǎng)絡(luò)中的區(qū)域緩存濃度，利用內(nèi)容副本在不同濃度區(qū)域間的擴(kuò)散實(shí)現(xiàn)內(nèi)容緩存的主動(dòng)放置和動(dòng)態(tài)遷移，從而增加為潛在用戶請(qǐng)求提供就近響應(yīng)的可能.這種內(nèi)容副本的主動(dòng)推進(jìn)方式將大大地縮短內(nèi)容查找和響應(yīng)的延遲并提高內(nèi)容的緩存命中概率.

1　分子擴(kuò)散的引入

擴(kuò)散現(xiàn)象是指物質(zhì)分子從高濃度區(qū)域向低濃度區(qū)域轉(zhuǎn)移直到均勻分布的現(xiàn)象.根據(jù)分子動(dòng)理論，分子擴(kuò)散的本質(zhì)是由于分子熱運(yùn)動(dòng)而產(chǎn)生的質(zhì)量遷移現(xiàn)象.從微觀上說，它實(shí)際上是大量物質(zhì)分子做無規(guī)則熱運(yùn)動(dòng)時(shí)，分子之間發(fā)生相互碰撞的結(jié)果.由于不同空間區(qū)域的分子密度分布不均勻，分子發(fā)生碰撞的情況也不同.這種碰撞迫使密度大的區(qū)域的分子向密度小的區(qū)域轉(zhuǎn)移，最后達(dá)到均勻的密度分布.

擴(kuò)散定律描述了分子擴(kuò)散導(dǎo)致的傳質(zhì)過程，這一定律由德國物理學(xué)家菲克( A.Fick)于1855年在實(shí)驗(yàn)的基礎(chǔ)上提出的，故又稱為菲克(Fick)定律.Fick定律指出，在穩(wěn)態(tài)擴(kuò)散過程中，擴(kuò)散通量J與濃度梯度成正比，即

(1)

式中：D為擴(kuò)散系數(shù)，是描述擴(kuò)散速度的重要物理量，它表示單位濃度梯度條件下，單位時(shí)間單位截面上通過的物質(zhì)流量；φ為濃度；x代表位置；負(fù)號(hào)表示物質(zhì)沿著濃度降低的方向擴(kuò)散.式(1)的意思是，如果某個(gè)事物的空間分布是不均勻的，就會(huì)造成流動(dòng)，而引起的物質(zhì)流正比于該事物的梯度.其中，梯度是物質(zhì)流動(dòng)的驅(qū)動(dòng)力.

受到上述分子擴(kuò)散思想的啟發(fā)，我們將內(nèi)容對(duì)象看作溶質(zhì)，將用戶對(duì)該內(nèi)容對(duì)象的需求視為溶劑，那么整個(gè)網(wǎng)絡(luò)系統(tǒng)則為內(nèi)容對(duì)象與用戶需求混合而成的溶液.由于內(nèi)容副本以及用戶需求分布的不均勻性和動(dòng)態(tài)性，因此該溶液不同區(qū)域的濃度也存在差異，內(nèi)容原始服務(wù)器或緩存節(jié)點(diǎn)附近濃度較高，而內(nèi)容請(qǐng)求節(jié)點(diǎn)附近濃度較低.對(duì)于內(nèi)容的緩存決策而言，直覺上內(nèi)容副本應(yīng)盡量趨近用戶需求較大的區(qū)域以提供快速高效的緩存和通信服務(wù).于是，緩存內(nèi)容的放置決策可以看作溶質(zhì)分子(內(nèi)容副本)在溶液中由高濃度區(qū)域向低濃度區(qū)域轉(zhuǎn)移的擴(kuò)散過程.

2　CDBPC緩存機(jī)制

2.1內(nèi)容擴(kuò)散模型

假設(shè)網(wǎng)絡(luò)中存在內(nèi)容集合C={ci|i=1,2,…,k}，C中的元素ci按其流行度級(jí)別編號(hào)，其被訪問的概率為pi，對(duì)任意1≤i

pi=Ω/iα.

(2)

將具有不同流行度的內(nèi)容比作不同種類的溶質(zhì)，每類內(nèi)容的一個(gè)副本即為該類溶質(zhì)的一個(gè)分子.那么某類內(nèi)容ci的緩存放置過程可以視為溶質(zhì)ci的分子在溶劑中的擴(kuò)散過程.類比擴(kuò)散原理中的相關(guān)概念，我們重新定義了擴(kuò)散系數(shù)、緩存內(nèi)容濃度和緩存概率3個(gè)概念，表述如下.

定義1擴(kuò)散系數(shù)D.物質(zhì)的分子擴(kuò)散系數(shù)表示它的擴(kuò)散能力，是物質(zhì)的物理性質(zhì)之一.根據(jù)菲克定律，擴(kuò)散系數(shù)是沿?cái)U(kuò)散方向，在單位時(shí)間每單位濃度梯度的條件下，垂直通過單位面積所擴(kuò)散某物質(zhì)的流量.在內(nèi)容緩存過程中，內(nèi)容的流行度反映了用戶對(duì)其需求程度的高低.高流行度的內(nèi)容需要更多的緩存副本來滿足用戶更高的需求量.即內(nèi)容的流行度越高，相應(yīng)地它應(yīng)具有更強(qiáng)的擴(kuò)散能力，從而保證其緩存副本能夠更快更密集地分布到網(wǎng)絡(luò)中.因此，本文用流行度來表示內(nèi)容ci的擴(kuò)散系數(shù)，即

Di=pi=Ω/iα.

(3)

(4)

2.2CDBPC工作原理

CDBPC機(jī)制的基本思想是克服現(xiàn)有緩存機(jī)制中緩存決策過程完全依賴用戶Interest驅(qū)動(dòng)的被動(dòng)性，通過借鑒分子擴(kuò)散的原理以一種更主動(dòng)的方式實(shí)現(xiàn)內(nèi)容副本向用戶端的快速推進(jìn).同時(shí)在內(nèi)容副本的推進(jìn)過程中綜合緩存內(nèi)容濃度和內(nèi)容流行度實(shí)現(xiàn)概率性的緩存放置，從而加快對(duì)后續(xù)用戶請(qǐng)求的響應(yīng)速度，提高系統(tǒng)的整體緩存性能.CDBPC主要包括兩個(gè)部分：內(nèi)容副本的推進(jìn)以及內(nèi)容的緩存決策.在內(nèi)容副本的推進(jìn)過程中，我們?cè)O(shè)計(jì)了被動(dòng)響應(yīng)和主動(dòng)擴(kuò)散2種基本的推進(jìn)模式.其中，被動(dòng)響應(yīng)模式發(fā)生在節(jié)點(diǎn)返回被請(qǐng)求的數(shù)據(jù)的響應(yīng)過程中.即，僅當(dāng)收到相應(yīng)的用戶請(qǐng)求并在緩存中發(fā)生命中時(shí)，作為數(shù)據(jù)應(yīng)答，節(jié)點(diǎn)才會(huì)將內(nèi)容副本沿著請(qǐng)求的反向傳輸路徑返回請(qǐng)求用戶.主動(dòng)擴(kuò)散模式的觸發(fā)則與內(nèi)容是否在該節(jié)點(diǎn)發(fā)生緩存命中無關(guān)，而是每隔一定的時(shí)間(本文稱之為擴(kuò)散周期Td)，節(jié)點(diǎn)便通過計(jì)算并比較自身與鄰居節(jié)點(diǎn)的緩存內(nèi)容濃度，主動(dòng)將內(nèi)容副本沿著緩存內(nèi)容濃度下降最快的路徑方向逐跳地進(jìn)行擴(kuò)散.在內(nèi)容副本的主動(dòng)擴(kuò)散或被動(dòng)響應(yīng)路徑上，中間節(jié)點(diǎn)再以一定的概率來選擇內(nèi)容的緩存位置.CDBPC機(jī)制的工作流程描述如下.

1)每個(gè)節(jié)點(diǎn)包含一個(gè)計(jì)時(shí)器T，在網(wǎng)絡(luò)初始化時(shí)，T被清零并開始計(jì)時(shí).若任意節(jié)點(diǎn)N的緩存內(nèi)容集合C非空(即節(jié)點(diǎn)至少緩存了一個(gè)內(nèi)容)，則N依據(jù)內(nèi)容的流行度以一定的概率從中挑選出一個(gè)內(nèi)容ci作為待處理對(duì)象.

3)每經(jīng)過一個(gè)擴(kuò)散周期Td，節(jié)點(diǎn)N將重復(fù)步驟1)- 2)決定是否執(zhí)行內(nèi)容的主動(dòng)擴(kuò)散.

4)當(dāng)N收到某個(gè)內(nèi)容副本cj，則N根據(jù)概率性緩存決策策略以一定的概率緩存該內(nèi)容副本，同時(shí)檢查其待定轉(zhuǎn)發(fā)表PIT.

5)若在PIT中發(fā)現(xiàn)與cj匹配的用戶請(qǐng)求，則N采用被動(dòng)響應(yīng)模式，根據(jù)PIT中記錄的請(qǐng)求來源端口將cj返回請(qǐng)求用戶節(jié)點(diǎn).否則以cj作為待處理對(duì)象，執(zhí)行步驟2)決定是否進(jìn)行內(nèi)容的主動(dòng)擴(kuò)散.

6)若cj未被節(jié)點(diǎn)N緩存，同時(shí)也未觸發(fā)相應(yīng)的主動(dòng)擴(kuò)散或被動(dòng)響應(yīng)，則N直接丟棄cj.

這里，我們的主要目的是利用內(nèi)容的主動(dòng)擴(kuò)散驅(qū)動(dòng)內(nèi)容副本向用戶端的預(yù)先推進(jìn)和部署，來減小用戶進(jìn)行內(nèi)容查找以及獲取的延時(shí).下面將具體介紹CDBPC機(jī)制的主要實(shí)現(xiàn)細(xì)節(jié).

2.2.1緩存內(nèi)容濃度的計(jì)算

2.2.2內(nèi)容的主動(dòng)擴(kuò)散

在CDBPC中，被動(dòng)響應(yīng)模式相對(duì)比較簡單，它由發(fā)生緩存命中的Interest包觸發(fā)，內(nèi)容副本按照預(yù)先確定的Interest包的反向路徑推進(jìn).而在主動(dòng)擴(kuò)散模式中，內(nèi)容副本的擴(kuò)散源自相鄰節(jié)點(diǎn)間的緩存內(nèi)容濃度差，按濃度由高到低的方向進(jìn)行移動(dòng).與被動(dòng)響應(yīng)模式中推進(jìn)的內(nèi)容對(duì)象以及推進(jìn)的路徑均由相應(yīng)的Interest確定不同，主動(dòng)擴(kuò)散模式需解決以下2個(gè)問題：①節(jié)點(diǎn)緩存中可能存在多個(gè)不同的內(nèi)容對(duì)象，對(duì)所有的緩存內(nèi)容均進(jìn)行擴(kuò)散容易造成過大的通信和存儲(chǔ)開銷.因此必須對(duì)進(jìn)行擴(kuò)散的內(nèi)容對(duì)象進(jìn)行合理的選擇；②沿著節(jié)點(diǎn)的所有輸出路徑進(jìn)行全方位的擴(kuò)散也必然產(chǎn)生大量的冗余內(nèi)容副本，導(dǎo)致網(wǎng)絡(luò)資源的過度消耗.因此，節(jié)點(diǎn)還必須合理地選擇內(nèi)容副本的推進(jìn)方向以實(shí)現(xiàn)內(nèi)容的選擇性擴(kuò)散.下面針對(duì)上述問題給出具體的解決策略.

(5)

2)擴(kuò)散方向的選擇.為了控制內(nèi)容擴(kuò)散的傳輸開銷，CDBPC中節(jié)點(diǎn)通過比較自己與各鄰居間的緩存內(nèi)容濃度，每次僅選擇向濃度下降最快的鄰居節(jié)點(diǎn)方向進(jìn)行擴(kuò)散.以節(jié)點(diǎn)S為例，假設(shè)其鄰居節(jié)點(diǎn)集合為Neighbor={N1,N2,…,Nn}，選中的擴(kuò)散內(nèi)容對(duì)象為ci，那么節(jié)點(diǎn)S與任意鄰居節(jié)點(diǎn)Nj間的緩存內(nèi)容濃度差可以表示為：

(6)

2.2.3概率性內(nèi)容緩存

CDBPC機(jī)制中，內(nèi)容副本推進(jìn)路徑上的節(jié)點(diǎn)將以一定的概率對(duì)內(nèi)容副本進(jìn)行緩存.在確定不同節(jié)點(diǎn)對(duì)內(nèi)容副本的緩存概率時(shí)，我們主要考慮兩方面的因素.首先，從內(nèi)容本身的角度來看，內(nèi)容的流行度越高，其被用戶請(qǐng)求的概率也就越大.因此，節(jié)點(diǎn)應(yīng)該以更高的概率來緩存流行度高的內(nèi)容.另一方面，從節(jié)點(diǎn)的角度來看，將內(nèi)容緩存在距離請(qǐng)求用戶節(jié)點(diǎn)越近的位置，將能獲得更快的響應(yīng)速度以及更高的緩存命中率.因此，內(nèi)容副本推進(jìn)路徑上各節(jié)點(diǎn)的緩存概率應(yīng)該沿著內(nèi)容副本的推進(jìn)方向逐跳遞增，而緩存概率增加的比例則應(yīng)與內(nèi)容推進(jìn)方向上緩存內(nèi)容濃度下降的速度成正比.

(7)

需要說明的是，若Nk成為了內(nèi)容ci的新的緩存節(jié)點(diǎn)，那么，將以Nk作為新的起始節(jié)點(diǎn)，而原路徑中Nk之后的子路徑即為ci新的推進(jìn)路徑，然后利用公式(7)重新計(jì)算新路徑上各節(jié)點(diǎn)對(duì)ci的緩存概率并執(zhí)行概率性緩存決策.

3　性能仿真及評(píng)價(jià)

本文采用ndnSIM[15]對(duì)算法進(jìn)行了仿真和性能分析.仿真實(shí)驗(yàn)中我們利用GT-ITM下的Locality模型構(gòu)建了一個(gè)由2個(gè)內(nèi)容服務(wù)器和50個(gè)路由節(jié)點(diǎn)組成的平面隨機(jī)網(wǎng)絡(luò)拓?fù)?其中，內(nèi)容服務(wù)器位于網(wǎng)絡(luò)的邊緣，并從邊緣節(jié)點(diǎn)中隨機(jī)選擇2個(gè)節(jié)點(diǎn)與之相連.2個(gè)內(nèi)容服務(wù)器各自不重復(fù)地隨機(jī)存儲(chǔ)占網(wǎng)絡(luò)內(nèi)容對(duì)象總數(shù)一半的內(nèi)容.同時(shí)，假設(shè)用戶請(qǐng)求的到達(dá)過程服從λ=50的泊松分布，用戶的訪問模式服從參數(shù)為α的Zipf分布.各路由節(jié)點(diǎn)緩存容量相同，且初始狀態(tài)下節(jié)點(diǎn)緩存為空.請(qǐng)求分組采用洪泛方式進(jìn)行轉(zhuǎn)發(fā)，默認(rèn)緩存替換策略為LRU，其他的主要實(shí)驗(yàn)參數(shù)如表1所示.

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

為了對(duì)算法性能進(jìn)行評(píng)價(jià)，我們選擇了緩存命中率和平均接入代價(jià)作為主要的性能指標(biāo).

1)緩存命中率.緩存命中率是評(píng)價(jià)緩存性能的重要指標(biāo)之一，它被定義為用戶請(qǐng)求由緩存而非原始內(nèi)容服務(wù)器響應(yīng)的概率.緩存內(nèi)容的命中率越高，對(duì)應(yīng)的原始內(nèi)容服務(wù)器響應(yīng)率和負(fù)載就越小，系統(tǒng)的效率就越高.

2)平均接入代價(jià).平均接入代價(jià)被定義為用戶請(qǐng)求找到匹配的內(nèi)容對(duì)象所需的平均跳數(shù)，它反映了用戶請(qǐng)求得到響應(yīng)，用戶完成內(nèi)容獲取的速度.平均接入代價(jià)越小，內(nèi)容獲取速度越快，緩存系統(tǒng)效率越高.

3.1CDBPC參數(shù)選擇

CDBPC包含兩個(gè)主要的算法參數(shù)：擴(kuò)散濃度差閾值θth和擴(kuò)散周期Td，本小節(jié)將通過仿真實(shí)驗(yàn)來選擇合理的參數(shù)值.

3.1.1擴(kuò)散濃度差閾值θth

緩存內(nèi)容濃度與擴(kuò)散濃度差閾值θth的大小關(guān)系是CDBPC機(jī)制中內(nèi)容副本主動(dòng)擴(kuò)散的觸發(fā)條件.較小的θth值意味著節(jié)點(diǎn)對(duì)內(nèi)容副本進(jìn)行主動(dòng)擴(kuò)散的概率越大，內(nèi)容副本在網(wǎng)絡(luò)中擴(kuò)散的范圍也相對(duì)更大，從而加速副本在網(wǎng)絡(luò)中的推進(jìn)和分布.但是擴(kuò)散主動(dòng)性的增加也會(huì)帶來更大的開銷.θth值過小可能造成內(nèi)容副本過度擴(kuò)散并緩存，節(jié)點(diǎn)緩存的過快消耗必然引發(fā)大量的緩存替換操作，反而導(dǎo)致緩存命中率下降并影響了CDBPC機(jī)制加快內(nèi)容響應(yīng)速度的效果.反之，θth值越大，推進(jìn)內(nèi)容副本的主動(dòng)性越低，擴(kuò)散范圍也越小，CDBPC機(jī)制對(duì)緩存性能的積極作用逐漸減小并退化為被動(dòng)響應(yīng)模式.圖1(a)和(b)分別反映了θth對(duì)緩存命中率和平均接入代價(jià)的影響.由圖1可見，θth值在0.02附近時(shí)CDBPC獲得了相對(duì)較高的緩存命中率和較小的平均接入代價(jià).而當(dāng)θth值向兩側(cè)變化時(shí)，則其性能均出現(xiàn)了不同程度的下滑.當(dāng)θth大于0.02之后，CDBPC的主動(dòng)擴(kuò)散作用隨著θth值的增長不斷減少，但最終其性能仍能與采用被動(dòng)響應(yīng)模式時(shí)接近.然而隨著θth值從0.02繼續(xù)不斷減小，緩存命中率出現(xiàn)急劇下降，同時(shí)平均接入代價(jià)也迅速增加.這正是因?yàn)檫^于激進(jìn)的副本擴(kuò)散加劇了節(jié)點(diǎn)的緩存消耗，進(jìn)而引發(fā)頻繁的緩存替換，大大縮短了內(nèi)容副本在節(jié)點(diǎn)上的緩存服務(wù)時(shí)間，因此最終降低了CDBPC的緩存性能.根據(jù)仿真實(shí)驗(yàn)結(jié)果及上面的分析，本文中將CDBPC的擴(kuò)散濃度差閾值設(shè)為0.02.

θth/10-3

θth/10-3

3.1.2擴(kuò)散周期Td

CDBPC機(jī)制中，內(nèi)容副本的攜帶節(jié)點(diǎn)根據(jù)與鄰居的緩存內(nèi)容濃度差周期性地執(zhí)行主動(dòng)擴(kuò)散過程，擴(kuò)散周期Td是影響CDBPC機(jī)制性能的重要因素之一.為了合理地選擇擴(kuò)散周期Td的長度，我們?cè)O(shè)置擴(kuò)散濃度差閾值θth=0.02，其他實(shí)驗(yàn)參數(shù)均采用默認(rèn)值，然后通過仿真實(shí)驗(yàn)觀察Td取不同值時(shí)CDBPC機(jī)制緩存性能的變化情況，如圖2所示.當(dāng)Td值設(shè)置較小時(shí)，將使得節(jié)點(diǎn)頻繁地進(jìn)行緩存內(nèi)容濃度的計(jì)算和比較并可能造成內(nèi)容副本的過度擴(kuò)散.這極大地增加了CDBPC機(jī)制的網(wǎng)絡(luò)開銷并導(dǎo)致頻繁的緩存替換，從而降低了其整體的緩存性能.由圖2(a)可見，Td=10 ms時(shí)的緩存命中率僅為29.1%，在Td值增加到100 ms的過程中，CDBPC的緩存命中率逐步提高到了32%.但是，隨著Td值的繼續(xù)增大，緩存命中率隨后則發(fā)生明顯的下降，在Td=300 ms時(shí)緩存命中率跌至27.9%.這主要是因?yàn)門d值繼續(xù)增大時(shí)，節(jié)點(diǎn)主動(dòng)擴(kuò)散的頻率進(jìn)一步降低，減慢了內(nèi)容副本在網(wǎng)絡(luò)中的推進(jìn)和緩存部署速度，主動(dòng)擴(kuò)散的積極作用也因此被極大地削弱.出于同樣的原因，圖2(b)中，CDBPC的平均接入代價(jià)則出現(xiàn)了先減后增的變化趨勢，同樣也是在Td=100 ms附近發(fā)生轉(zhuǎn)折并達(dá)到最佳值.因此，綜合圖2的仿真結(jié)果，本文中擴(kuò)散周期Td的長度被設(shè)為100 ms.

Td/ms

Td/ms

3.2性能評(píng)估

仿真過程中，我們將CDBPC與在用戶請(qǐng)求的被動(dòng)響應(yīng)路徑上選擇最大介數(shù)節(jié)點(diǎn)進(jìn)行緩存的Betw[16]和利用勢場主動(dòng)進(jìn)行局部內(nèi)容通告的CATT進(jìn)行比較.其中，CATT的內(nèi)容通告范圍設(shè)置為2跳.在緩存大小、內(nèi)容數(shù)量和Zipf參數(shù)α等網(wǎng)絡(luò)參數(shù)變化的情況下，分別對(duì)上述3種緩存機(jī)制的緩存命中率以及平均接入代價(jià)進(jìn)行了定量分析和比較.

3.2.1緩存大小的影響

圖3為節(jié)點(diǎn)緩存對(duì)緩存性能影響的仿真結(jié)果圖.由圖3(a)可以看到，隨著節(jié)點(diǎn)緩存空間的增大，內(nèi)容分組在緩存中的駐留時(shí)間延長，因此3種機(jī)制的緩存命中率均逐漸提高.其中，由于CDBPC向用戶端對(duì)內(nèi)容分組實(shí)施主動(dòng)擴(kuò)散，同時(shí)在此過程中根據(jù)緩存內(nèi)容濃度和內(nèi)容流行度采用了逐跳遞增的概率緩存，將內(nèi)容的緩存副本快速有效地分布到請(qǐng)求用戶節(jié)點(diǎn)附近，從而獲得了3種機(jī)制中最高緩存命中率.而Betw中內(nèi)容副本的推進(jìn)完全依賴節(jié)點(diǎn)對(duì)用戶請(qǐng)求的應(yīng)答，且單純地依據(jù)節(jié)點(diǎn)的介數(shù)中心性來實(shí)現(xiàn)緩存節(jié)點(diǎn)的選擇，使得介數(shù)較高的節(jié)點(diǎn)由于緩存壓力過大而導(dǎo)致緩存替換頻繁，因此獲得的緩存命中率最低.CATT利用勢場實(shí)現(xiàn)了緩存內(nèi)容的主動(dòng)通告，有效地將用戶請(qǐng)求導(dǎo)向匹配的內(nèi)容緩存副本，一定程度上提高了系統(tǒng)的緩存命中率，因此在圖中CATT的緩存命中率略高于Betw.

同樣，隨著節(jié)點(diǎn)緩存的增加，中間節(jié)點(diǎn)對(duì)內(nèi)容的緩存能力增強(qiáng)，每個(gè)內(nèi)容分組能獲得更長時(shí)間的緩存服務(wù).這意味著用戶有更大的可能從距離較近的中間緩存節(jié)點(diǎn)實(shí)現(xiàn)快速的內(nèi)容獲取.因此，圖3(b)中各機(jī)制的平均接入代價(jià)均隨著節(jié)點(diǎn)緩存的增加而逐漸降低.其中，得益于CDBPC對(duì)內(nèi)容副本的主動(dòng)擴(kuò)散，加快了緩存副本向用戶邊緣的推進(jìn)，因此，CDBPC獲得了3種機(jī)制中最小平均接入代價(jià).以節(jié)點(diǎn)緩存為50 MB時(shí)的情況為例，Betw和CATT的平均接入代價(jià)達(dá)到了4.55跳和4.22跳，而CDBPC僅為4.02跳，與前兩者相比，分別減少了近11.6%和4.7%.

3.2.2內(nèi)容數(shù)量的影響

內(nèi)容數(shù)量對(duì)3種緩存機(jī)制影響的實(shí)驗(yàn)結(jié)果如圖4所示.由于在節(jié)點(diǎn)緩存大小固定的情況下，內(nèi)容數(shù)量的增加意味著可用緩存資源的相對(duì)緊張.因此，內(nèi)容數(shù)量對(duì)緩存性能的影響實(shí)際上也是節(jié)點(diǎn)緩存大小與緩存性能之間關(guān)系的另一種體現(xiàn).

從圖4(a)中結(jié)果可以看到，隨著內(nèi)容數(shù)量的增多，節(jié)點(diǎn)緩存資源越發(fā)緊缺，3種機(jī)制的緩存命中率均出現(xiàn)進(jìn)了明顯下降的趨勢.但是，CDBPC始終保持了3種機(jī)制中最高的緩存命中率.在內(nèi)容數(shù)量增至10 000個(gè)時(shí)，CDBPC仍獲得了21.6%的緩存命中率，優(yōu)于CATT的19.5%和Betw的15.7%.而由圖4(b)可知，3種緩存機(jī)制的平均接入代價(jià)則隨著內(nèi)容數(shù)量的增加逐漸增大.其中，CDBPC的平均接入代價(jià)明顯低于其他2種緩存機(jī)制.同樣以10 000個(gè)內(nèi)容時(shí)的情況為例，CDBPC的平均接入代價(jià)僅為4.57跳，相比Betw和CATT分別減少了約10.9%和5%.這與3.2.1節(jié)中關(guān)于緩存大小對(duì)2種緩存性能指標(biāo)的影響的分析結(jié)果是一致的.

緩存大小/MB

緩存大小/MB

3.2.3Zipf參數(shù)α的影響

用戶對(duì)內(nèi)容的訪問具有一定的偏好性，用戶偏好對(duì)不同機(jī)制的緩存命中率的影響如圖5所示.Zipf參數(shù)α越大，意味著用戶的偏好越發(fā)地向流行度高的內(nèi)容集中.由于3種緩存機(jī)制均采用了優(yōu)先保證高流行度內(nèi)容緩存時(shí)間的相關(guān)策略(如，基于LRU的緩存替換策略)，因此，由圖5(a)可見，它們的緩存命中率隨著α值的增大均呈現(xiàn)上升的趨勢.同時(shí)，還得益于在內(nèi)容推進(jìn)以及緩存決策中對(duì)內(nèi)容流行度的考慮，CDBPC在采用不同的α值時(shí)均獲得了明顯高于其他2種緩存機(jī)制的緩存命中性能.在平均接入代價(jià)方面，從圖5(b)中的結(jié)果可以發(fā)現(xiàn)，用戶偏好性的增強(qiáng)導(dǎo)致了平均接入代價(jià)的下降.而CDBPC對(duì)內(nèi)容副本更為主動(dòng)的推進(jìn)方式，使得用戶可以更快地實(shí)現(xiàn)內(nèi)容獲取，從而獲得了3種機(jī)制中相對(duì)最低的平均接入代價(jià).

內(nèi)容數(shù)量/個(gè)

內(nèi)容數(shù)量/個(gè)

Zipf參數(shù)α

Zipf參數(shù)α

4　結(jié)　論

為了加快內(nèi)容緩存副本在內(nèi)容中心網(wǎng)絡(luò)中的推進(jìn)，進(jìn)一步提高其為潛在用戶請(qǐng)求提供就近響應(yīng)的可能性，本文提出緩存內(nèi)容濃度的概念，并借鑒分子的擴(kuò)散原理設(shè)計(jì)了一種基于內(nèi)容擴(kuò)散的主動(dòng)緩存機(jī)制CDBPC.該機(jī)制利用節(jié)點(diǎn)間的緩存內(nèi)容濃度關(guān)系來驅(qū)動(dòng)內(nèi)容副本在網(wǎng)絡(luò)中的主動(dòng)推進(jìn)和遷移，并結(jié)合內(nèi)容的流行度等因素實(shí)現(xiàn)了內(nèi)容的概率性緩存決策.仿真實(shí)驗(yàn)結(jié)果表明該機(jī)制能有效地提高系統(tǒng)的整體緩存性能.在今后的工作中，我們將對(duì)CDBPC在實(shí)際網(wǎng)絡(luò)環(huán)境下的性能進(jìn)行驗(yàn)證，同時(shí)進(jìn)一步研究如何將其擴(kuò)展到移動(dòng)網(wǎng)絡(luò)以及其他復(fù)雜的網(wǎng)絡(luò)環(huán)境.

[1]JACOBSON V,SMETTERS D K,THORNTON J D,etal. Networkingnamed content[J].Communications of the ACM, 2012, 55(1):117-124.

[2]PSARAS I,CHAI W K,PAVLOU G.Probabilistic in-networkcaching for information-centric networks[C]// Proceedings of the Second Edition of the ICN Workshop on Information-centric Networking. New York: ACM, 2012: 55-60.

[3]MING Z,XU M,WANG D.Age-based cooperative caching in information-centric network[C]// Proceedings of the 23rd International Conference on Computer Communication and Networks (ICCCN). Washington DC: IEEE Computer Society,2014:1-8.

[4]QIAN H,MUQING W,DONGYANG W,etal.Lifetime-based greedy caching approach for content-centric networking[C]// Proceedings of the 21st International Conference on Telecommunications (ICT). Washington DC: IEEE Computer Society,2014:426-430.

[5]葛國棟,郭云飛,劉彩霞,等.命名數(shù)據(jù)網(wǎng)絡(luò)中基于內(nèi)容請(qǐng)求相關(guān)性的協(xié)作緩存算法[J].電子與信息學(xué)報(bào),2014,36(12):2795-2801.

GE Guo-dong,GUO Yun-fei,LIU Cai-xia,etal.Collaborative caching algorithm based on request correlation in named data networking[J].Journal of Electronics & Information Technology,2014,36(12):2795-2801.(In Chinese)

[6]劉外喜,余順爭,蔡君,等.ICN中的一種協(xié)作緩存機(jī)制[J].軟件學(xué)報(bào),2013,24(8):1947-1962.

LIU Wai-xi,YU Shun-zheng,CAI Jun,etal.Scheme for cooperative caching in ICN[J].Journal of Software, 2013, 24(8):1947-1962.(In Chinese)

[7]劉外喜,余順爭,胡曉,等.CCN中選擇性緩存機(jī)制的研究[J]. 計(jì)算機(jī)學(xué)報(bào),2014,37(2):275-288.

LIU Wai-xi,YU Shun-zheng,HU Xiao,etal.Selective caching in content-centric networking[J].Chinese Journal of Computers,2014,37(2):275-288.(In Chinese)

[8]KYI T,SAEED U,CHOONG S H.Consistent hashing based cooperative caching and forwarding in content centric network[C]//Proceedings of the 16th Asia-Pacific Network Operations and Management Symposium (APNOMS). Washington DC: IEEE Computer Society,2014:1-4.

[9]張國強(qiáng),李楊,林濤,等.信息中心網(wǎng)絡(luò)中的內(nèi)置緩存技術(shù)研究[J].軟件學(xué)報(bào),2014,25(1):154-175.

ZHANG Guo-qiang,LI Yang,LIN Tao,etal.Survey of in-network caching techniques in information-centric networks[J].Journal of Software,2014,25(1):154-175.(In Chinese)

[10]DRAXLER M,KARL H.Efficiency of on-path and off-path caching strategies in information centric networks[C]// Proceedings of 2012 IEEE International Conference on Green Computing and Communications (GreenCom). Washington DC:IEEE Computer Society,2012:581-587.

[11]EUM S,NAKAUCHI K,MURATA M,etal.CATT: potential based routing with content caching for ICN[J]. IEEE Communications Magazine,2012,50(12):60-67.

[12]葛國棟,郭云飛,劉彩霞,等.內(nèi)容中心網(wǎng)絡(luò)中基于差異化緩存通告的混合路由機(jī)制[J].電子與信息學(xué)報(bào),2015, 37(3):700-707.

GE Guo-dong,GUO Yun-fei,LIU Cai-xia,etal.A hybrid routing scheme based on differentiated cache advertisement in content centric networking[J].Journal of Electronics & Information Technology,2015,37(3):700-707.(In Chinese)

[13]陳璐,湯紅波,鄭林浩.內(nèi)容中心網(wǎng)絡(luò)基于拓?fù)鋭莸恼?qǐng)求者移動(dòng)性支持機(jī)制[J].計(jì)算機(jī)工程與設(shè)計(jì),2014,35(8): 2685-2690.

CHEN Lu,TANG Hong-bo,ZHENG Lin-hao.Consumer mobility scheme in content centric networks based on topological potential[J].Computer Engineering and Design,2014,35(8): 2685-2690.(In Chinese)

[14]KIM Y,YEOM I.Performance analysis of in-network caching for content-centric networking[J].Computer Networks,2013,57(13):2465-2482.

[15]MASTORAKIS S,AFANASYEV A,MOISEENKO I,etal.ndnSIM 2.0: a new version of the NDN simulator for NS-3[R]. Los Angeles:University of California,2015.

[16]CHAI W K，HE D， PSARAS I，etal.Cache “Less for more” in information-centric networks[J].Computer Communications, 2013,36(7):758-770.

Content Diffusion Based Proactive Caching in Content-centric Networks

LUO Xi1,3, AN Ying2?,NIU Bi-nuo4

(1. School of Information Science and Engineering, Central South Univ, Changsha, Hunan410083, China; 2. Institute of Information Security & Big Data, Central South Univ, Changsha, Hunan410083, China;3. Department of Information Technology, Hunan Police Academy, Changsha, Hunan410138, China;4.Computer School, Wuhan Univ, Wuhan,Hubei430072,China)

This paper borrowed the idea of molecular diffusion and proposed a proactive caching scheme based on content diffusion. In this mechanism, the conception of content concentration was introduced to analyze user demands for different contents in different network regions. In order to achieve fast content placement and increase the probability of providing responses to user requests by the nearer caching nodes, the content replicas were proactively pushed forward or migrated according to the content concentration difference between nodes. Furthermore, by synthetically considering the content popularity, a probabilistic content placement method was also implemented. The simulation results have shown that this scheme can effectively decrease the average access cost and improve the cache hit ratio.

Content-centric Networking(CCN);diffusion theory;proactive caching;content popularity

1674-2974(2016)08-0142-09

2015-06-23

國家自然科學(xué)基金資助項(xiàng)目(61402541)，National Natural Science Foundation of China(61402541);網(wǎng)絡(luò)犯罪偵查湖南省普通高等學(xué)校重點(diǎn)實(shí)驗(yàn)室開放研究基金資助項(xiàng)目(2016WLFZZC009)；網(wǎng)絡(luò)偵查技術(shù)湖南省普通重點(diǎn)實(shí)驗(yàn)室開放研究基金資助項(xiàng)目(2016WLZC009)

羅熹(1980-)，女，湖南長沙人，中南大學(xué)博士研究生，湖南警察學(xué)院講師 ?通訊聯(lián)系人，E-mail:anying@csu.edu.cn

TP393

A