基于內(nèi)容中心網(wǎng)的緩存算法研究

黃瑩瑩，楊龍祥

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

1 概 述

隨著網(wǎng)絡(luò)技術(shù)的高速發(fā)展，用戶對(duì)數(shù)據(jù)的需求日益增加，這種趨勢(shì)會(huì)給網(wǎng)絡(luò)帶寬和數(shù)據(jù)存儲(chǔ)空間帶來(lái)極大的壓力，會(huì)導(dǎo)致網(wǎng)絡(luò)擁塞和服務(wù)器過(guò)載等現(xiàn)象。而且日益增加的用戶數(shù)也使IP資源消耗殆盡，用戶不得不在不同的時(shí)段共享同一IP地址，這使得身份認(rèn)證機(jī)制難以實(shí)現(xiàn)，故而引發(fā)了網(wǎng)絡(luò)的安全性問(wèn)題。

并且，傳統(tǒng)的IP通信是由數(shù)據(jù)源主導(dǎo)的用戶之間端到端通信[1]。兩個(gè)端口在傳輸數(shù)據(jù)之前，必須先創(chuàng)建一個(gè)路徑，并維護(hù)該路徑直至數(shù)據(jù)傳輸結(jié)束。如圖1所示，當(dāng)用戶1需要獲取數(shù)據(jù)A時(shí)，首先需要和服務(wù)器建立連接，若服務(wù)器中有滿足要求的數(shù)據(jù)則回傳。當(dāng)用戶2和3也需要獲取數(shù)據(jù)A時(shí)，它們必須重復(fù)執(zhí)行相同的動(dòng)作，并向服務(wù)器發(fā)出請(qǐng)求。這種源主導(dǎo)的端到端通信將導(dǎo)致嚴(yán)重的資源浪費(fèi)。并且，如今高速發(fā)展網(wǎng)絡(luò)更多的是被用來(lái)進(jìn)行數(shù)據(jù)廣播，而不是終端之間的兩兩通信。用戶更在意的是想要獲取的數(shù)據(jù)本身(what)，而不是該數(shù)據(jù)的確切位置(where)。顯然IP網(wǎng)絡(luò)這個(gè)拓?fù)浣Y(jié)構(gòu)無(wú)法實(shí)現(xiàn)性能良好的數(shù)據(jù)分配，這種網(wǎng)絡(luò)模型和用戶需求的不匹配，會(huì)導(dǎo)致用戶體驗(yàn)差、網(wǎng)絡(luò)帶寬損耗、數(shù)據(jù)獲取時(shí)延大等缺陷。

圖1 IP結(jié)構(gòu)的通信過(guò)程

針對(duì)上述問(wèn)題，為了將源主導(dǎo)的端到端通信轉(zhuǎn)變?yōu)榻邮斩酥鲗?dǎo)的信息搜索，提出了未來(lái)網(wǎng)絡(luò)的概念。典型的未來(lái)網(wǎng)絡(luò)緩存方案有面向數(shù)據(jù)的網(wǎng)絡(luò)體系結(jié)構(gòu)(data-oriented network architecture,DONA[2])、內(nèi)容中心網(wǎng)(content-centric network,CCN)、基于發(fā)布和訂閱的互聯(lián)網(wǎng)路由模式(publish-subscribe internet routing paradigm,PSIRP)等，其中內(nèi)容中心網(wǎng)絡(luò)受到業(yè)界的大量關(guān)注，若感興趣，可以參照文獻(xiàn)[3]。

文中主要對(duì)內(nèi)容中心網(wǎng)的緩存算法進(jìn)行了研究，分析了CCN體系結(jié)構(gòu)與傳統(tǒng)IP通信之間的差異，突出內(nèi)容中心網(wǎng)的優(yōu)點(diǎn)。介紹了CCN的最長(zhǎng)前綴匹配查找方法、包結(jié)構(gòu)以及請(qǐng)求轉(zhuǎn)發(fā)機(jī)制。闡述了傳統(tǒng)的緩存決定策略和緩存取代策略，在此基礎(chǔ)上重點(diǎn)研究了幾個(gè)典型的改進(jìn)算法，分析其優(yōu)缺點(diǎn)，并提出了未來(lái)的重點(diǎn)研究方向和相關(guān)工作。

2 CCN工作機(jī)制

CCN是以內(nèi)容為中心的未來(lái)網(wǎng)絡(luò)緩存方案，主要完成的工作是用戶請(qǐng)求廣播、數(shù)據(jù)搜索以及數(shù)據(jù)回傳[4]。不同于以往的端到端IP通信，它實(shí)現(xiàn)了將數(shù)據(jù)本身和所在的端口分離，并且無(wú)需維護(hù)端到端之間的通信路徑。它將側(cè)重點(diǎn)放在數(shù)據(jù)本身而無(wú)需知道數(shù)據(jù)的具體位置。在CCN中，將為每個(gè)組塊命名，且每個(gè)組塊的名字都是唯一的，數(shù)據(jù)搜索基于組塊的名字。在組塊名字搜索的過(guò)程中，主要思想是字符串最長(zhǎng)前綴匹配，典型的查找方法有基于TCAM的查找方法、基于字符串查找樹(shù)的查找方法和基于散列技術(shù)的查找方法[5]。CCN另一個(gè)重要特點(diǎn)是，路由器有本地緩存功能。在IP通信中，數(shù)據(jù)包被傳輸?shù)较掠斡脩舳撕?，就?huì)直接被丟棄。而CCN中的路由器會(huì)選擇性緩存一些使用頻率高的數(shù)據(jù)，當(dāng)后續(xù)對(duì)這些數(shù)據(jù)的請(qǐng)求到達(dá)時(shí)，鄰近路由器可以直接回傳給用戶，而不是每次都要從遠(yuǎn)處的服務(wù)器端獲取。這種緩存機(jī)制可有效地減少網(wǎng)絡(luò)擁塞，減少帶寬的使用，提高網(wǎng)絡(luò)吞吐量，降低用戶獲取數(shù)據(jù)的時(shí)延。

2.1 興趣包和數(shù)據(jù)包

在CCN中有兩種包格式，分別為興趣包(interest packet)和數(shù)據(jù)包(data packet)[6]。在興趣包和數(shù)據(jù)包的頭部，都包含一個(gè)名為Content Name的存儲(chǔ)空間，用來(lái)存儲(chǔ)組塊名字。若興趣包中的Content Name是數(shù)據(jù)包中Content Name的前綴，則表明該數(shù)據(jù)包是請(qǐng)求獲取的數(shù)據(jù)[7]。當(dāng)用戶請(qǐng)求獲取某個(gè)數(shù)據(jù)塊時(shí)，會(huì)創(chuàng)建一個(gè)包含該請(qǐng)求組塊名字的興趣包，然后在網(wǎng)絡(luò)中廣播該興趣包。當(dāng)網(wǎng)絡(luò)中的任何路由器接收到該興趣包時(shí)，會(huì)先提取出數(shù)據(jù)名字，由于路由器存在緩存功能，所以它會(huì)先查看自己的本地緩存，再?zèng)Q定是否將興趣包轉(zhuǎn)發(fā)給其他路由器。當(dāng)服務(wù)器或某個(gè)路由器響應(yīng)了該請(qǐng)求，則會(huì)將數(shù)據(jù)以數(shù)據(jù)包的形式回送給用戶。

2.2 轉(zhuǎn)發(fā)機(jī)制

在CCN轉(zhuǎn)發(fā)機(jī)制中主要包含三種數(shù)據(jù)結(jié)構(gòu)，分別是內(nèi)容存儲(chǔ)表(content store，CS)、待定請(qǐng)求表(pending interest table，PIT)和轉(zhuǎn)發(fā)信息表(forwarding information base，F(xiàn)IB)。CS用來(lái)緩存數(shù)據(jù)，從而實(shí)現(xiàn)最大化數(shù)據(jù)共享，減少網(wǎng)絡(luò)擁塞。PIT待定請(qǐng)求表，用來(lái)保存興趣包轉(zhuǎn)發(fā)軌跡。當(dāng)CCN中搜索到滿足要求的數(shù)據(jù)包時(shí)，該數(shù)據(jù)包會(huì)按照PIT中保存的路徑軌跡回傳給請(qǐng)求方。當(dāng)路由器接收到興趣包時(shí)，若該數(shù)據(jù)的請(qǐng)求已被轉(zhuǎn)發(fā)過(guò)，則只需在PIT中添加對(duì)該數(shù)據(jù)的請(qǐng)求端口，當(dāng)數(shù)據(jù)回傳時(shí)，則會(huì)根據(jù)PIT中的請(qǐng)求端口一一回傳該數(shù)據(jù)的副本。FIB轉(zhuǎn)發(fā)信息表，用來(lái)記錄興趣包可以被轉(zhuǎn)發(fā)出去的一系列端口。

CCN請(qǐng)求轉(zhuǎn)發(fā)過(guò)程主要如下：當(dāng)路由器接收到對(duì)某個(gè)數(shù)據(jù)的興趣包時(shí)，首先會(huì)在興趣包中提取出數(shù)據(jù)名字，利用名字的最長(zhǎng)前綴匹配查找方法，在自己的緩存空間CS中搜索。若數(shù)據(jù)名字匹配成功，則將數(shù)據(jù)以數(shù)據(jù)包的形式回傳給用戶。若未成功，則會(huì)檢查自己的PIT，若PIT中存在對(duì)該數(shù)據(jù)的請(qǐng)求，則可直接更新PIT在其中添加請(qǐng)求端口，并丟棄該興趣包，當(dāng)數(shù)據(jù)包回傳時(shí)會(huì)根據(jù)PIT中的請(qǐng)求端口，每個(gè)都回傳一份副本。若PIT匹配也未成功，則會(huì)檢查FIB，如果存在一個(gè)匹配的FIB出口，則興趣包會(huì)朝著這個(gè)方向傳輸給上游。再否則，匹配失敗丟棄該興趣包。

2.3 緩存機(jī)制

在CCN中，緩存管理機(jī)制對(duì)于改善網(wǎng)絡(luò)系統(tǒng)性能極其重要。緩存管理主要涉及兩個(gè)方面，緩存決定策略和緩存取代策略。緩存決定策略是指，當(dāng)路由器接收到某個(gè)數(shù)據(jù)時(shí)決定是否緩存該數(shù)據(jù)。緩存取代策略是指，由于路由器的緩存空間有限，當(dāng)緩存空間不足時(shí)，路由器決定選擇刪除緩存中的哪個(gè)數(shù)據(jù)，從而存儲(chǔ)新到來(lái)的數(shù)據(jù)。

在緩存決定上，傳統(tǒng)緩存方案有l(wèi)eave copy everywhere (LCE)[8]、leave copy down (LCD)[9]、ProbCache[10]、hop-based probabilistic caching (HPC)[11]等，這些算法簡(jiǎn)單易實(shí)現(xiàn)，但多數(shù)沒(méi)有考慮數(shù)據(jù)流行度，而且路由器間缺乏合作，緩存冗余，緩存空間資源浪費(fèi)。

在緩存取代上，傳統(tǒng)的緩存取代策略有最近最少使用替換算法(least recently used，LRU)[12]、使用頻率最少替換算法(least frequently used，LFU)[13]。國(guó)內(nèi)外研究數(shù)據(jù)表明，數(shù)據(jù)塊流行度的高低，日益成為緩存取代策略需要考慮的重要因素。相繼提出了一系列的基于內(nèi)容流行度的緩存置換策略[14-15]，而傳統(tǒng)的置換策略沒(méi)有將流行度納入研究重點(diǎn)，因此性能欠佳。

3 CCN典型緩存算法

在CCN緩存方案中主要涉及兩個(gè)問(wèn)題，即數(shù)據(jù)緩存位置問(wèn)題和數(shù)據(jù)搜索問(wèn)題。

數(shù)據(jù)緩存位置問(wèn)題主要是指緩存決定策略和緩存取代策略。早期的緩存決定和取代策略，簡(jiǎn)單易實(shí)現(xiàn)，但存在許多問(wèn)題。路由器間缺乏合作，導(dǎo)致同一個(gè)數(shù)據(jù)在多個(gè)相鄰路由器中緩存，緩存冗余浪費(fèi)空間。并且緩存決定和取代時(shí)并沒(méi)有考慮數(shù)據(jù)流行度，導(dǎo)致緩存使用頻率不高的數(shù)據(jù)，影響系統(tǒng)性能。

在數(shù)據(jù)搜索方面，早期的路由轉(zhuǎn)發(fā)只是朝著服務(wù)器的方向轉(zhuǎn)發(fā)，這種搜索方式可能帶來(lái)的問(wèn)題是，所請(qǐng)求的數(shù)據(jù)在相鄰路由器中，卻將請(qǐng)求轉(zhuǎn)發(fā)給了遠(yuǎn)處的服務(wù)器，獲取數(shù)據(jù)的延時(shí)過(guò)大，影響系統(tǒng)性能。

因此，針對(duì)上述問(wèn)題進(jìn)行了改進(jìn)，以下便是一些典型算法思想。

3.1 基于內(nèi)容流行度的路由器間合作緩存策略

由于文件在傳輸過(guò)程中被分成若干個(gè)組塊，終端在請(qǐng)求某個(gè)文件時(shí)，則要對(duì)每個(gè)組塊發(fā)送一個(gè)興趣包。文獻(xiàn)[16]基于該思想，提出一個(gè)上游節(jié)點(diǎn)可以建議下游節(jié)點(diǎn)緩存組塊，并且緩存組塊數(shù)目隨著用戶對(duì)該文件請(qǐng)求次數(shù)的增加而呈指數(shù)式增長(zhǎng)。通過(guò)在組塊中增加緩存建議標(biāo)志，上游路由器在轉(zhuǎn)發(fā)過(guò)程中可以設(shè)置該值來(lái)建議下游是否緩存該組塊，從而實(shí)現(xiàn)各個(gè)路由器間的彼此合作，減少緩存冗余。

假設(shè)用戶第一次請(qǐng)求某文件，原始服務(wù)器回傳該文件，上游第一個(gè)路由器A會(huì)緩存該文件的第一個(gè)組塊。當(dāng)用戶第二次請(qǐng)求該文件時(shí)，路由器A回傳第一個(gè)組塊給用戶，其余組塊仍有服務(wù)器回傳。同時(shí)路由器A會(huì)建議其下游路由器B緩存第一個(gè)組塊，其自身開(kāi)始緩存第二第三個(gè)組塊。以此類推，隨著對(duì)該文件的請(qǐng)求次數(shù)增加，緩存的組塊呈指數(shù)式增長(zhǎng)。

在本算法中，提出了依據(jù)文件的請(qǐng)求頻率來(lái)動(dòng)態(tài)調(diào)整緩存組塊數(shù)目的思想，緩存流行度高的文件，可以有效減少網(wǎng)絡(luò)擁塞，獲得更高的緩存命中率。并且其實(shí)現(xiàn)了上下游路由器之間的緩存合作，能夠有效地避免緩存冗余的問(wèn)題。且研究表明，一個(gè)文件的前面組塊訪問(wèn)頻率會(huì)比后面的高[17]。本算法中將文件的前面組塊緩存在靠近用戶的路由器中，可以有效地減少緩存獲取的時(shí)延，增強(qiáng)用戶體驗(yàn)。

該算法的缺點(diǎn)在于，采用的是LRU緩存取代策略，沒(méi)有依據(jù)組塊的流行度來(lái)提出新的算法，可能會(huì)導(dǎo)致流行度低的文件取代流行度高的文件。

3.2 基于Consistent Hashing的分布式協(xié)作緩存策略

CCN中，緩存和轉(zhuǎn)發(fā)策略極其重要，傳統(tǒng)緩存和轉(zhuǎn)發(fā)策略雖然簡(jiǎn)單，但存在許多缺陷。文獻(xiàn)[18]在此基礎(chǔ)上進(jìn)行改進(jìn)，提出了Consistent Hashing思想及數(shù)據(jù)內(nèi)容流行度預(yù)測(cè)算法，存儲(chǔ)流行度高的數(shù)據(jù)。將路由器分組，各個(gè)組中的路由器彼此合作，實(shí)現(xiàn)數(shù)據(jù)請(qǐng)求有效轉(zhuǎn)發(fā)。

在該算法中，如圖2一個(gè)組中的各個(gè)路由器被分配若干個(gè)鍵值，擁有鍵的多少由該路由器的實(shí)際物理內(nèi)存決定。即路由器的緩存空間越大，被分配的鍵越多。假設(shè)路由器1擁有鍵(2，6，7，12，13)，路由器2擁有鍵(1，5，8，10)，路由器3擁有鍵(0，4，9)，路由器4擁有鍵(3，11)。這些鍵的范圍從0至n，圍成一個(gè)環(huán)。當(dāng)數(shù)據(jù)請(qǐng)求到達(dá)時(shí)，首先使用散列函數(shù)求出興趣包名字的散列值，然后針對(duì)求得的散列值來(lái)尋找對(duì)應(yīng)的路由器。該路由器會(huì)根據(jù)提出的數(shù)據(jù)流行度預(yù)測(cè)公式和動(dòng)態(tài)緩存門限公式，存儲(chǔ)超過(guò)門限值的數(shù)據(jù)。

圖2 基于Consistent Hashing的協(xié)同緩存策略

另外，在本算法中，主要提出了以下兩條公式。式1是數(shù)據(jù)流行度的預(yù)測(cè)算法，該公式由兩部分組成，利用數(shù)據(jù)的歷史和當(dāng)前請(qǐng)求頻率來(lái)預(yù)測(cè)該數(shù)據(jù)的流行度。

(1)

其中，F(xiàn)i為數(shù)據(jù)i的訪問(wèn)頻率；β為權(quán)重參數(shù)。

式2是動(dòng)態(tài)緩存門限公式。

(2)

由于數(shù)據(jù)包請(qǐng)求數(shù)量隨著時(shí)間而變化，因此該公式計(jì)算出的流行度緩存門限能實(shí)現(xiàn)動(dòng)態(tài)調(diào)節(jié)。摒棄傳統(tǒng)采用的靜態(tài)流行度門限，可以更佳有效地緩存使用頻率高的數(shù)據(jù)。并且不同于傳統(tǒng)的路由轉(zhuǎn)發(fā)方式，當(dāng)路由器收到數(shù)據(jù)請(qǐng)求時(shí)，通過(guò)散列環(huán)可以實(shí)現(xiàn)請(qǐng)求的有效轉(zhuǎn)發(fā)，以及每個(gè)組中路由器的彼此協(xié)作，而不是傳統(tǒng)的廣播。

但是，該算法也存在一些缺點(diǎn)。在該算法中，網(wǎng)絡(luò)中的路由器需要被分組，然后構(gòu)成各自的散列環(huán)，在各自的散列環(huán)中，各個(gè)路由器又需要被分配不同的鍵值，可見(jiàn)整個(gè)流程所涉及的計(jì)算比較繁雜。在流行度預(yù)測(cè)公式和動(dòng)態(tài)門限預(yù)測(cè)公式中，各個(gè)路由器需要周期性地計(jì)算通過(guò)它們的數(shù)據(jù)的流行度及各個(gè)時(shí)間段的緩存門限。都需要反復(fù)使用公式來(lái)進(jìn)行數(shù)據(jù)更新，因此涉及的計(jì)算量也較多。綜上所述，由于該算法在公式計(jì)算、路由器分組以及散列環(huán)方面所做的工作比較多，因此復(fù)雜度高，實(shí)現(xiàn)起來(lái)有難度，而且運(yùn)行時(shí)會(huì)占用大量的資源，影響網(wǎng)絡(luò)性能。

3.3 基于緩存容量感知的CCN緩存策略

該算法包含三個(gè)部分：緩存容量估計(jì)、選擇緩存、緩存感知路由選擇[19]。首先，通過(guò)式3估計(jì)每個(gè)路由器的緩存容量值CCV。

(3)

其中，CacheSize是路由器的物理緩存大??；L是路由器的緩存負(fù)荷，即緩存消耗大小，是一段特定時(shí)間里的緩存消耗積累；c是補(bǔ)償系數(shù)。

將最高的緩存容量值CCV記錄在轉(zhuǎn)發(fā)的興趣包中，每經(jīng)過(guò)一個(gè)路由器就更新CCV及當(dāng)前路由器離具有最高CCV的路由器的距離NDV，從而找到那個(gè)具有最高的CCV路由器位置。圖3描述了計(jì)算CCV值的過(guò)程以及如何將CCVhighest插入到轉(zhuǎn)發(fā)的興趣包中。例如節(jié)點(diǎn)1，它的總緩存空間是500，已緩存200，c的默認(rèn)值是1，則節(jié)點(diǎn)1的CCV等于2.5。其他節(jié)點(diǎn)的CCV以此類推計(jì)算。興趣包經(jīng)過(guò)各個(gè)節(jié)點(diǎn)，更新CCVhighest值，并記錄各自的NDV。

圖3 緩存空間估計(jì)示例

在選擇性緩存中，返回路徑上有最大緩存容量CCV的路由器一定要緩存該數(shù)據(jù)，若返回的數(shù)據(jù)流行度比較高，則利用CCV門限值公式，當(dāng)中間路由器的緩存容量CCV大于這個(gè)門限值時(shí)，該路由器選擇緩存數(shù)據(jù)，否則只是轉(zhuǎn)發(fā)數(shù)據(jù)不存儲(chǔ)。

在路由感知方面，路由器一定范圍內(nèi)創(chuàng)建臨時(shí)FIB，來(lái)指示到具有最大CCV的路由器。由于轉(zhuǎn)發(fā)路徑上至少有一個(gè)路由器會(huì)緩存該數(shù)據(jù)，如果路由器接收到該數(shù)據(jù)的請(qǐng)求，而它又沒(méi)有緩存，則可以根據(jù)FIB出口轉(zhuǎn)發(fā)。另外，根據(jù)統(tǒng)計(jì)的數(shù)據(jù)平均駐存時(shí)間為臨時(shí)FIB表建立過(guò)期時(shí)間。

算法中，通過(guò)估計(jì)每個(gè)路由器的緩存容量，將選擇性緩存和路由選擇聯(lián)合起來(lái)，可以提高緩存效率，減少服務(wù)器的負(fù)荷。但是該算法的側(cè)重點(diǎn)在緩存容量估計(jì)上，對(duì)于數(shù)據(jù)的真實(shí)流行度并沒(méi)有提出具體的算法，對(duì)于緩存空間不足的情況也沒(méi)有提出具體的取代策略。

3.4 基于流行度的動(dòng)態(tài)調(diào)整緩存位置的緩存策略

在該算法中，提出了基于組塊流行度來(lái)動(dòng)態(tài)調(diào)整組塊位置信息的思想[20]。每個(gè)組塊中都包含一個(gè)流行度比較標(biāo)志PCF，若上游的路由器想將某個(gè)組塊傳至下游，首先會(huì)比較該組塊的流行度和下游路由器中組塊最小流行度，若大于則將PCF設(shè)置為1，否則為0。當(dāng)PCF=1時(shí)，該上游路由器會(huì)將數(shù)據(jù)包中的緩存建議標(biāo)志CSF設(shè)置為1，以建議下游路由器緩存該組塊。這樣算法就可以保證只會(huì)將流行度高的數(shù)據(jù)緩存在靠近用戶的一端，降低傳輸時(shí)延。同時(shí)，由于傳輸路徑上只有一個(gè)副本，這種合作緩存機(jī)制可以增加緩存多樣性，避免緩存冗余的現(xiàn)象。

當(dāng)緩存空間不足時(shí)，該算法通過(guò)比較組塊的流行度，緩存流行度高的數(shù)據(jù)，并將被替換組塊的CSF設(shè)置為2，發(fā)送給上游路由器建議其緩存。如圖4所示，上游路由器建議下游緩存流行度高的數(shù)據(jù)，下游路由器將替換的數(shù)據(jù)發(fā)送給上游路由器緩存。

圖4 動(dòng)態(tài)調(diào)整緩存位置的工作過(guò)程

并且該算法為每個(gè)組塊都建立了緩存歷史軌跡，類似于Breadcrumbs[21]描述的方法，該軌跡中包含組塊的ID、組塊來(lái)自哪個(gè)路由器以及傳輸至哪個(gè)路由器。當(dāng)發(fā)生數(shù)據(jù)搜索時(shí)，不會(huì)直接將興趣包傳輸給服務(wù)器，而是會(huì)先根據(jù)歷史記錄搜索，以防該數(shù)據(jù)就在附近路由器中。

不同于以前的算法，該算法將緩存的位置信息和數(shù)據(jù)搜索兩者緊密聯(lián)合起來(lái)，并結(jié)合了數(shù)據(jù)流行度，能夠很好地實(shí)現(xiàn)將請(qǐng)求頻率高的數(shù)據(jù)緩存在靠近用戶的邊緣路由器中，減少時(shí)延，改善用戶體驗(yàn)，并且合作緩存減少冗余。其次，該算法是在文獻(xiàn)[22]的基礎(chǔ)上改進(jìn)提出的，由于文獻(xiàn)[22]是在分層的拓?fù)浣Y(jié)構(gòu)中設(shè)計(jì)的，所以應(yīng)用到任意拓?fù)浣Y(jié)構(gòu)的CCN中會(huì)導(dǎo)致震蕩和緩存頻繁替代的現(xiàn)象。而該算法是針對(duì)CCN設(shè)計(jì)的，更加實(shí)用。

3.5 基于動(dòng)態(tài)流行度門限的緩存機(jī)制

研究表示，對(duì)比數(shù)據(jù)請(qǐng)求分布、數(shù)據(jù)類型大小、緩存取代策略等因素，存儲(chǔ)流行度高的數(shù)據(jù)對(duì)網(wǎng)絡(luò)性能的影響更佳深刻。文獻(xiàn)[23]著重研究的就是如何設(shè)置緩存的流行度門限值。

在文獻(xiàn)[24]的算法中，引入了數(shù)據(jù)流行度的思想，為每個(gè)組塊記錄各自的請(qǐng)求次數(shù)。當(dāng)某個(gè)組塊的請(qǐng)求次數(shù)到達(dá)預(yù)先設(shè)置的門限值時(shí)，則被定義為是流行的數(shù)據(jù)，并被路由器緩存。該算法中僅存儲(chǔ)流行的數(shù)據(jù)，在一定程度上可以節(jié)省資源，提高緩存命中率，但是會(huì)導(dǎo)致命中率的收斂速度慢，并且對(duì)于不同大小的緩存空間，其命中率性能不穩(wěn)定。

本算法主要是在文獻(xiàn)[24]基礎(chǔ)上提出的，對(duì)上述提出的問(wèn)題進(jìn)行了改進(jìn)。同樣，也為每個(gè)組塊創(chuàng)建了一個(gè)表，記錄各自的ID、流行度級(jí)別等。當(dāng)數(shù)據(jù)到來(lái)時(shí)，若路由器緩存空間充足，則總會(huì)存儲(chǔ)該數(shù)據(jù)。若緩存空間不足，則會(huì)比較數(shù)據(jù)的請(qǐng)求次數(shù)是否超過(guò)了預(yù)先設(shè)定的流行度門限值，若超過(guò)，則采用LRU緩存替代策略，否則將新到來(lái)數(shù)據(jù)丟棄。對(duì)比于文獻(xiàn)[24]，本算法在緩存空間充足時(shí)無(wú)論新到來(lái)數(shù)據(jù)的流行度多少，都會(huì)存儲(chǔ)該數(shù)據(jù)，當(dāng)緩存空間不足時(shí)，則不流行的數(shù)據(jù)會(huì)被流行度高的數(shù)據(jù)取代。這樣緩存處理方式能夠獲得更高的緩存命中率及更快的收斂速率。

上述的流行度門限都是固定的，但在實(shí)際生活中，一個(gè)數(shù)據(jù)的流行度、興趣包到達(dá)的數(shù)量、文件的實(shí)際大小以及可用的路由器緩存總是隨時(shí)間變化的，因此要設(shè)置動(dòng)態(tài)門限。通過(guò)分析發(fā)現(xiàn)，流行度動(dòng)態(tài)門限與文件大小和興趣包數(shù)量成正比，與緩存空間成反比。綜上所述，提出了公式4：

(4)

其中，ninterest表示興趣包數(shù)量；Fp表示文件大??；Csize表示緩存空間。

通過(guò)對(duì)文獻(xiàn)[24]算法的改進(jìn)及提出動(dòng)態(tài)門限，可以提高緩存命中率、改善網(wǎng)絡(luò)性能。但是，該算法計(jì)算量較大，且要實(shí)時(shí)跟蹤一些參數(shù)，實(shí)現(xiàn)起來(lái)可能有點(diǎn)困難。并且該算法主要探討的是門限值設(shè)定，對(duì)于路由器之間的合作緩存機(jī)制以及路由轉(zhuǎn)發(fā)并沒(méi)有進(jìn)行深入探討。

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

CCN將由信息源主導(dǎo)的網(wǎng)絡(luò)構(gòu)架模式轉(zhuǎn)變?yōu)橛捎脩糁鲗?dǎo)的方式，能夠更好地實(shí)現(xiàn)數(shù)據(jù)搜索轉(zhuǎn)發(fā)。CCN中的緩存功能，對(duì)于更有效地使用帶寬資源、改善用戶體驗(yàn)至關(guān)重要。文中針對(duì)CCN的發(fā)展過(guò)程、網(wǎng)絡(luò)模型以及一些典型的算法策略進(jìn)行了詳細(xì)闡述。

在CCN的設(shè)計(jì)方案中，主要包括緩存決定策略、緩存取代策略和路由轉(zhuǎn)發(fā)協(xié)議。現(xiàn)有設(shè)計(jì)方案中，主要考慮的是數(shù)據(jù)流行度以及路由器間彼此協(xié)作。在此基礎(chǔ)上可以引入其他因素，如數(shù)據(jù)往返時(shí)延、網(wǎng)絡(luò)中能量損耗等。緩存性能的優(yōu)化方法主要分為緩存大小規(guī)劃、緩存空間共享機(jī)制、緩存決策策略、緩存替換算法、緩存對(duì)象可用性這5個(gè)方面[25]。

該課題之后的研究方向主要放在如何提出高效且易實(shí)現(xiàn)的算法方面。在緩存決定方面，制定出簡(jiǎn)單易實(shí)現(xiàn)的數(shù)據(jù)包流行度計(jì)算公式。另一研究重點(diǎn)是如何確定各路由器的數(shù)據(jù)緩存門限，僅緩存流行度值高于門限值的數(shù)據(jù)包，并盡量將其緩存在邊緣路由器上，從而降低用戶獲取數(shù)據(jù)的時(shí)延。在緩存取代方面，主要是研究緩存替代的條件，通過(guò)比較新到來(lái)的數(shù)據(jù)包流行度值與已有緩存中最低流行度值，來(lái)決定是否要進(jìn)行緩存替換。并且制定相應(yīng)的策略，來(lái)處理被替換出的數(shù)據(jù)包和流行度較低的新數(shù)據(jù)。并且各個(gè)路由器協(xié)同工作，從而有效減少緩存冗余，實(shí)現(xiàn)數(shù)據(jù)高效轉(zhuǎn)發(fā)。

參考文獻(xiàn)：

[1] AHLGREN B, DANNEWITZ C, IMBRENDA C,et al. A survey of information-centric networking[J].IEEE Communications Magazine,2012,50(7):26-36.

[2] 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.

[3] 夏春梅,徐明偉.信息中心網(wǎng)絡(luò)研究綜述[J].計(jì)算機(jī)科學(xué)與探索,2013,7(6):481-493.

[4] FANG Chao,YU F R,HUANG Tao,et al.A survey of energy-efficient caching in information-centric networking[J].IEEE Communications Magazine,2014,52(11):122-129.

[5] 劉 斌,汪 漪.內(nèi)容中心網(wǎng)絡(luò)中名字查找技術(shù)的研究[J].電信科學(xué),2014,30(9):10-17.

[6] JACOBSON V,SMETTERS D K,THORNTON J D,et al.Networking named content[J].Communications of the ACM,2012,55(1):117-124.

[7] 閔二龍,陳 震,許宏峰,等.內(nèi)容中心網(wǎng)絡(luò)CCN研究進(jìn)展探析[J].信息網(wǎng)絡(luò)安全,2012(2):6-10.

[8] JIANG Anxiao,BRUCK J.Optimal content placement for en-route web caching[C]//Proceedings of the second IEEE international symposium on network computing and applications.[s.l.]:IEEE,2003:9-16.

[9] LAOUTARIS N,SYNTILA S,STAVRAKAKIS I.Meta algorithms for hierarchical Web caches[C]//IEEE international conference on performance,computing,and communications.Phoenix,AZ,USA:IEEE,2004:445-452.

[10] PSARAS I,WEI K C,PAVLOU G.Probabilistic in-network caching for information-centric networks[C]//Proceedings of the second edition of the ICN workshop on information-centric networking.Helsinki,Finland:ACM,2012:55-60.

[11] WANG Yu,XU Mingwei,FENG Zhen.Hop-based probabilistic caching for information-centric networks[C]//IEEE global communications conference.Atlanta,GA,USA:IEEE,2013:2102-2107.

[12] MEGIDDO N,MODHA D S.Outperforming LRU with an adaptive replacement cache algorithm[J].Computer,2004,37(4):58-65.

[13] PETEV P G,WINTERGERST M.Least frequently used eviction implementation:U.S.,US7552284[P].2009-06-23.

[14] 朱 軼,糜正琨,王文鼐.一種基于內(nèi)容流行度的內(nèi)容中心網(wǎng)絡(luò)緩存概率置換策略[J].電子與信息學(xué)報(bào),2013,35(6):1305-1310.

[15] 段 煉,楊龍祥,任美翠.內(nèi)容中心網(wǎng)絡(luò)及其緩存策略研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2017,27(3):75-80.

[16] CHO K,LEE M,PARK K,et al.WAVE:popularity-based and collaborative in-network caching for content-oriented networks[C]//Computer communications workshops.Orlando,FL,USA:IEEE,2012:316-321.

[17] LIM S H,KO Y B,JUNG G H,et al.Inter-chunk popularity-based edge-first caching in content-centric networking[J].IEEE Communications Letters,2014,18(8):1331-1334.

[18] THAR K,OO T Z,PHAM C,et al.Efficient forwarding and popularity based caching for content centric network[C]//International conference on information networking.Cambodia,Cambodia:IEEE,2015:330-335.

[19] LEE S W,KIM D,KO Y B,et al.Cache capacity-aware CCN:selective caching and cache-aware routing[C]//Global communications conference.Atlanta,GA,USA:IEEE,2014:2114-2119.

[20] XU Yuemei,MA Shuai,LI Yang,et al.P-CLS:a popularity-driven caching location and searching scheme in content centric networking[C]//Computing and communications conference.Nanjing,China:IEEE,2016:1-8.

[21] ROSENSWEIG E J,KUROSE J.Breadcrumbs:efficient,best-effort content location in cache networks[C]//International conference on computer communications.[s.l.]:IEEE,2009:2631-2635.

[22] LI Yang,LIN Tao,TANG Hui,et al.A chunk caching location and searching scheme in content centric networking[C]//IEEE international conference on communications.Ottawa,ON,Canada:IEEE,2012:2655-2659.

[23] ONG M D,CHEN Min,TALEB T,et al.FGPC:fine-grained popularity-based caching design for content centric networking[C]//Proceedings of the 17th ACM international conference on modeling,analysis and simulation of wireless and mobile systems.Montreal,QC,Canada:ACM,2014:295-302.

[24] BERNARDINI C,SILVERSTON T,FESTOR O.MPC:popularity-based caching strategy for content centric networks[C]//IEEE international conference on communications.[s.l.]:IEEE,2013:3619-3623.

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