曾宇晶，靳明雙，羅洪斌

(北京交通大學(xué)下一代互聯(lián)網(wǎng)互連設(shè)備國家工程實(shí)驗(yàn)室，北京100044)

?

基于內(nèi)容分塊流行度分級(jí)的信息中心網(wǎng)絡(luò)緩存策略

曾宇晶，靳明雙，羅洪斌

(北京交通大學(xué)下一代互聯(lián)網(wǎng)互連設(shè)備國家工程實(shí)驗(yàn)室，北京100044)

摘要:信息中心網(wǎng)絡(luò)(ICN: Information-Centric Networking)域內(nèi)緩存機(jī)制的研究大多假定單個(gè)內(nèi)容的流行度相同，而忽視了同一內(nèi)容的不同分塊具有不同流行度的特性．本文提出了一種基于內(nèi)容分塊流行度以及緩存節(jié)點(diǎn)位置的分級(jí)緩存策略，通過興趣包和數(shù)據(jù)包攜帶標(biāo)簽的方式實(shí)現(xiàn)隱式緩存協(xié)作．仿真實(shí)驗(yàn)證明相比于其他方案，該方案可以充分利用細(xì)粒度的內(nèi)容分塊流行度這一特性，提高緩存路由器緩存命中率，減小用戶請(qǐng)求內(nèi)容時(shí)延以及網(wǎng)絡(luò)流量，進(jìn)而提升用戶對(duì)實(shí)時(shí)業(yè)務(wù)的服務(wù)體驗(yàn)．

關(guān)鍵詞:內(nèi)容為中心網(wǎng)絡(luò);域內(nèi)緩存;流行度

1　引言

隨著互聯(lián)網(wǎng)的高速發(fā)展，當(dāng)前基于終端間包交換的點(diǎn)到點(diǎn)連接通信的TCP/IP網(wǎng)絡(luò)模型已經(jīng)無法適應(yīng)用戶對(duì)實(shí)時(shí)視頻、流媒體等大流量數(shù)據(jù)業(yè)務(wù)越來越高的需求．為了解決互聯(lián)網(wǎng)在傳輸、處理這些多媒體數(shù)據(jù)時(shí)效率低下，用戶體驗(yàn)差，難以實(shí)現(xiàn)網(wǎng)絡(luò)資源的高效利用等諸多問題，在未來網(wǎng)絡(luò)體系的研究中不斷有新的網(wǎng)絡(luò)架構(gòu)提出．其中ICN［1～3，17～19］(Information-Centric Networking)架構(gòu)脫穎而出，逐漸成為未來網(wǎng)絡(luò)架構(gòu)的研究熱點(diǎn)．

與傳統(tǒng)互聯(lián)網(wǎng)端到端通信模式不同，ICN更強(qiáng)調(diào)以內(nèi)容資源本身為中心．一方面，ICN通過對(duì)內(nèi)容命名實(shí)現(xiàn)對(duì)內(nèi)容的唯一標(biāo)識(shí)，也實(shí)現(xiàn)了內(nèi)容與其存儲(chǔ)位置的分離．另一方面，ICN允許網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)內(nèi)容進(jìn)行緩存，這樣可以使內(nèi)容更接近用戶，用戶無需關(guān)心內(nèi)容存儲(chǔ)的位置，請(qǐng)求的消息將會(huì)被路由到臨近提供該內(nèi)容的節(jié)點(diǎn)并取回內(nèi)容，從而減少服務(wù)器負(fù)載，降低網(wǎng)絡(luò)帶寬消耗以及提升用戶體驗(yàn)．與此同時(shí)，內(nèi)容也可以被分為具有獨(dú)立名字的分塊，進(jìn)而在不同的節(jié)點(diǎn)緩存，同一內(nèi)容的不同分塊也會(huì)由于處于內(nèi)容中的不同位置具有不同的流行度．

域內(nèi)緩存是ICN架構(gòu)中的重要組成部分，有效的部署域內(nèi)緩存協(xié)作以及緩存替換策略對(duì)ICN網(wǎng)絡(luò)的性能具有較大的影響．當(dāng)前網(wǎng)絡(luò)緩存協(xié)作的研究大多基于單個(gè)內(nèi)容的流行度部署緩存，使最流行的內(nèi)容能夠緩存到離用戶最近的緩存節(jié)點(diǎn)中，很少考慮到更細(xì)粒度的內(nèi)容分塊各自的流行度;另一方面，協(xié)作式緩存還存在緩存通告開銷大，緩存信息同步慢導(dǎo)致興趣請(qǐng)求包撲空等情況，從而降低了整個(gè)緩存系統(tǒng)的效率．

為了解決上述網(wǎng)絡(luò)緩存協(xié)作中存在的問題，本文提出了LICA(segment Level-based Implicit CooperationcAche)模型．LICA旨在通過充分考慮內(nèi)容分塊粒度下的流行度，通過隱式協(xié)作的方式提高網(wǎng)絡(luò)緩存效率，同時(shí)減小緩存協(xié)作開銷．本文的主要貢獻(xiàn)如下:

(1)提出了基于內(nèi)容分塊流行度以及緩存節(jié)點(diǎn)位置的分級(jí)模型．(2)通過興趣包和數(shù)據(jù)包攜帶標(biāo)簽的方式實(shí)現(xiàn)隱式協(xié)作．(3)通過大量的仿真實(shí)驗(yàn)，證明了LICA的優(yōu)越性．

2　相關(guān)工作

傳統(tǒng)單純用來轉(zhuǎn)發(fā)和路由的網(wǎng)絡(luò)節(jié)點(diǎn)(如交換機(jī)，路由器)在ICN中被賦予了更多的作用，如對(duì)經(jīng)過的內(nèi)容具有緩存的能力．在傳統(tǒng)WEB緩存［4］以及代理緩存［5］研究的基礎(chǔ)上，越來越多的基于ICN架構(gòu)的域內(nèi)緩存方案［6］被提出，用以提高網(wǎng)絡(luò)緩存的效率進(jìn)而提高整個(gè)網(wǎng)絡(luò)的性能．

當(dāng)前域內(nèi)緩存協(xié)作機(jī)制可以根據(jù)協(xié)作的類型分為顯式協(xié)作以及隱式協(xié)作兩類．顯式協(xié)作通過節(jié)點(diǎn)與一定范圍內(nèi)的鄰居節(jié)點(diǎn)同步各自的緩存信息來實(shí)現(xiàn)緩存的決策以及替換規(guī)則，因而顯示協(xié)作往往伴隨著大量緩存同步信息的通信開銷，如文獻(xiàn)［7］和文獻(xiàn)［8］．隱式協(xié)作則不需要緩存同步開銷就能實(shí)現(xiàn)緩存協(xié)作．文獻(xiàn)［4］提出了LCD的策略，用戶的單次請(qǐng)求將會(huì)使內(nèi)容沿著路徑下移一跳，這樣請(qǐng)求次數(shù)越多的內(nèi)容則會(huì)靠用戶越近．ProbCache［9］，WAVE［10］，CLS［11］等都是采用與LCD相同的路徑緩存的方式來進(jìn)行緩存協(xié)作，只是具體協(xié)作的細(xì)節(jié)有所不同．在文獻(xiàn)［12］中，作者提出了一種基于時(shí)間權(quán)重的緩存協(xié)作方式，通過賦予離用戶近以及請(qǐng)求次數(shù)高的內(nèi)容高的時(shí)間權(quán)重來緩存更長的時(shí)間．CRCache［13］提出了Router Importance(RI)的概念，將最流行的內(nèi)容分塊緩存到RI值最大的路由器上來提高整個(gè)網(wǎng)絡(luò)的緩存效率，但是這樣可能會(huì)造成最流行的內(nèi)容無法緩存到離用戶最近的位置．TLRU［14］對(duì)Least Recently Used(LRU)策略進(jìn)行了修改，對(duì)內(nèi)容大小以及被請(qǐng)求次數(shù)的統(tǒng)計(jì)，提出了基于時(shí)間認(rèn)知的LRU方案，但并沒有在全局網(wǎng)絡(luò)形成很好的協(xié)作因而對(duì)緩存性能的提高有限．IPEC［15］考慮到了同一內(nèi)容的不同分塊具有不同的流行度，并提出了與WAVE類似的路徑緩存協(xié)作方案，但是由于分塊粒度的不夠因而無法充分利用分塊流行度的這一特性．

為了更好的利用細(xì)粒度的內(nèi)容分塊流行度這一特性，我們提出了通過統(tǒng)計(jì)用戶的請(qǐng)求模式來對(duì)內(nèi)容分塊進(jìn)行分級(jí)的ICN域內(nèi)緩存協(xié)作方案．

3　基于內(nèi)容分塊流行度分級(jí)的隱式協(xié)作緩存(LICA)模型

本文提出了一種基于內(nèi)容分塊流行度分級(jí)的隱式協(xié)作緩存Level-based Implicit Cooperation cAche(LICA)模型，具有以下特點(diǎn):

(1)去中心化，即不需要專門的網(wǎng)絡(luò)設(shè)備來收集并統(tǒng)計(jì)網(wǎng)絡(luò)中內(nèi)容的流行度并控制各緩存路由器中內(nèi)容的副本的分布以及替換，只需要由離用戶最近的路由器統(tǒng)計(jì)用戶請(qǐng)求信息即可．

(2)內(nèi)容分塊流行度分級(jí)，即根據(jù)緩存路由器空間大小將不同流行度的內(nèi)容分塊分為不同的等級(jí)，等級(jí)高的內(nèi)容分塊會(huì)被緩存到離用戶近的路由器，提高網(wǎng)絡(luò)緩存效率．

(3)隱式協(xié)作，即緩存路由器之間不需要通過額外的緩存消息進(jìn)行通告，也不需要在本地維護(hù)相應(yīng)的鄰居緩存列表，緩存標(biāo)志僅由原有的請(qǐng)求包與數(shù)據(jù)包攜帶，減少額外通信開銷．

3.1LICA概述

LICA方案可以在不同的ICN網(wǎng)絡(luò)架構(gòu)下部署．為了描述方便，我們以ICN網(wǎng)絡(luò)中比較有代表性的CCN (Content Centric Networking)架構(gòu)［1］為例對(duì)LICA方案進(jìn)行描述．在一個(gè)CCN網(wǎng)絡(luò)中，該網(wǎng)絡(luò)由1個(gè)內(nèi)容源服務(wù)器，N個(gè)緩存路由器以及M個(gè)用戶組成．內(nèi)容源服務(wù)器存儲(chǔ)有網(wǎng)絡(luò)中所有的內(nèi)容數(shù)據(jù)，內(nèi)容數(shù)據(jù)可以被分塊．假設(shè)所有分塊大小相同且為單位數(shù)量1，每個(gè)緩存路由器都有相同大小的緩存空間S，即可以同時(shí)緩存內(nèi)容分塊的數(shù)量為S．

根據(jù)傳統(tǒng)CCN網(wǎng)絡(luò)的工作機(jī)制，內(nèi)容數(shù)據(jù)可以被分塊，當(dāng)用戶想要獲取某個(gè)內(nèi)容分塊時(shí)，用戶將向最近的緩存路由器發(fā)送包含該分塊名稱的興趣包．如果該內(nèi)容包含10個(gè)分塊，用戶想要獲取整個(gè)內(nèi)容的數(shù)據(jù)，則需要發(fā)送10個(gè)興趣包．關(guān)于內(nèi)容合適的分塊數(shù)量以及分塊數(shù)量帶來的可擴(kuò)展性問題，不在本文的討論范圍中，但本方案對(duì)粗粒度(單個(gè)內(nèi)容)，細(xì)粒度(分包)都能夠提供較好的支持．如果緩存路由器存儲(chǔ)了該內(nèi)容分塊則會(huì)返回分塊給用戶，沒有則會(huì)轉(zhuǎn)發(fā)到下一跳路由器．如果沿途路由器都沒有緩存該分塊，興趣包將會(huì)被轉(zhuǎn)發(fā)到內(nèi)容源服務(wù)器來滿足服務(wù)請(qǐng)求．內(nèi)容分塊的數(shù)據(jù)包將沿著之前興趣傳輸路徑反向傳給用戶，沿途經(jīng)過的緩存路由器將會(huì)根據(jù)本地緩存策略決定是否緩存該分塊．

與CCN不同，我們修改了興趣包與數(shù)據(jù)包的格式，加入了分塊等級(jí)(如何確定分塊等級(jí)，請(qǐng)見3.3.1節(jié))的字段，通過攜帶和傳遞分塊的等級(jí)來決定分塊是否被緩存路由器緩存．與此同時(shí)，根據(jù)緩存路由器距離用戶的跳數(shù)，我們將緩存路由器分為不同的層級(jí)．另外，為了統(tǒng)計(jì)用戶請(qǐng)求信息，我們還在第一跳緩存路由器加入了用戶請(qǐng)求統(tǒng)計(jì)列表Interest Statistic Table(IST)．IST根據(jù)用戶請(qǐng)求統(tǒng)計(jì)以及緩存路由器緩存空間對(duì)內(nèi)容分塊進(jìn)行分級(jí)，請(qǐng)求頻率高的分塊對(duì)應(yīng)高的分塊等級(jí)．當(dāng)興趣包到達(dá)后，第一跳緩存路由器在查詢IST后填充興趣包分塊等級(jí)的字段．當(dāng)興趣包被沿途某個(gè)緩存路由器或者最終的內(nèi)容源服務(wù)器滿足時(shí)，興趣包中的分塊等級(jí)字段將會(huì)被讀取并寫入到內(nèi)容分塊的數(shù)據(jù)包中，用來決定數(shù)據(jù)包是否被緩存．

3.2LICA工作原理

下面闡述LICA的工作原理．如圖1所示，根據(jù)距離用戶的跳數(shù)，緩存路由器A，B，C被分為層級(jí)1－3．同時(shí)假設(shè)每個(gè)路由器的緩存空間為1，即只能緩存一個(gè)緩存分塊．內(nèi)容C1被分為3個(gè)大小相同的分塊S1，S2，S3．

興趣包中分塊等級(jí)初始值為0．在圖1(a)中，用戶C1發(fā)送興趣包請(qǐng)求內(nèi)容C1的分塊S1．興趣包到達(dá)第一跳緩存路由器A后，A在IST中加入請(qǐng)求的內(nèi)容分塊名稱C1/S1，已請(qǐng)求的次數(shù)1，以及經(jīng)過計(jì)算之后的等級(jí)1并在興趣包中的等級(jí)字段寫入1．由于沿路路由器都沒有緩存該分塊，興趣包將會(huì)被路由到內(nèi)容源服務(wù)器來滿足請(qǐng)求，內(nèi)容源服務(wù)器讀取興趣包中的等級(jí)字段并且將等級(jí)1寫入到內(nèi)容分塊的數(shù)據(jù)包中，沿原路徑返回到用戶．沿途緩存路由器將會(huì)檢查數(shù)據(jù)包中的等級(jí)字段，以判斷是否與自己的層級(jí)數(shù)相等，相等則緩存，不相等則忽略．最終，內(nèi)容分塊C1/S1被層級(jí)1的緩存路由器A緩存．

接下來，如圖1(b)所示．用戶B先后發(fā)出兩個(gè)興趣包分別請(qǐng)求分塊C1/S1與C1/S2．當(dāng)C1/S1的興趣包到達(dá)A后，首先查詢到IST表中對(duì)應(yīng)的字段，添加次數(shù)并重新計(jì)算等級(jí)．然后查詢本地緩存發(fā)現(xiàn)已經(jīng)存取了C1/S1分塊，將等級(jí)賦值到分塊數(shù)據(jù)包后，直接發(fā)送分塊給用戶;當(dāng)C1/S2的興趣包到達(dá)A后，由于每個(gè)緩存路由器只能緩存一個(gè)分塊且C1/S2在IST表中請(qǐng)求的次數(shù)少于C1/S1，因此分塊等級(jí)為2．A在IST中加入請(qǐng)求的內(nèi)容分塊名稱C1/S2，已請(qǐng)求的次數(shù)1，以及經(jīng)過計(jì)算之后的等級(jí)2并在興趣包中的等級(jí)字段寫入2．之后流程與圖1 (a)中相似，最終C1/S2被層級(jí)2的緩存路由器B緩存．

在圖1(c)中，用戶C想要獲取整個(gè)內(nèi)容C1，先后發(fā)送了三個(gè)興趣請(qǐng)求包請(qǐng)求S1，S2，S3．A更新IST表后，S1由A滿足請(qǐng)求直接返回分塊．S2由B滿足請(qǐng)求返回分塊．S3的興趣包從IST表獲得的等級(jí)值為3，因此最終分塊S3被緩存在C處．

在圖1的例子中我們可以看到，分塊所處緩存路由器的層級(jí)與其流行度對(duì)應(yīng)，被請(qǐng)求次數(shù)越多的分塊將會(huì)被緩存到離用戶越近的緩存路由器上．同時(shí)，緩存分塊是否緩存以及緩存的位置直接通過第一跳路由器就能決定，不需要其他復(fù)雜的通信以及協(xié)作，這樣既提高了整個(gè)網(wǎng)絡(luò)的緩存效率也避免了不必要的開銷．

3.3LICA特性詳述

前文中我們對(duì)LICA的工作原理進(jìn)行了描述，接下來我們將詳細(xì)介紹LICA中緩存路由器層級(jí)判斷方法、IST表的更新方法以及緩存更新替換方法．

3．3．1緩存路由器層級(jí)

緩存路由器根據(jù)收到的興趣包中所記錄的跳數(shù)來確定自身的層級(jí)．當(dāng)緩存路由器收到興趣包后，檢查興趣包中跳數(shù)的Hi，并與自身層級(jí)HR做比較，當(dāng)跳數(shù)字段Hi大于自身層級(jí)HR時(shí)，將當(dāng)前層級(jí)HR修改為跳數(shù)Hi所對(duì)應(yīng)的數(shù)值．當(dāng)跳數(shù)字段Hi小于等于自身層級(jí)HR時(shí)，則不需要修改自身層級(jí)HR．在一個(gè)信息中心網(wǎng)絡(luò)域內(nèi)，緩存路由器數(shù)量一定，因而緩存路由器層級(jí)也是不變的，且每個(gè)緩存路由器都有自己確定的層級(jí)．

3．3．2 IST表

IST表只會(huì)在第一跳緩存路由器生成，其他層級(jí)的路由器不會(huì)有IST表，這樣可以有效減少表的存儲(chǔ)開銷以及更新開銷．但是當(dāng)某個(gè)緩存路由器直接連接用戶且同時(shí)位于其他路徑的非第一跳位置時(shí)，該緩存路由器同樣生成IST表．這樣做的目的是確保所有的興趣包都能被分配等級(jí)．IST表格式如圖1所示，包括分塊名字，被請(qǐng)求次數(shù)和等級(jí)．其中分塊名字由分塊所屬內(nèi)容名字與分塊處于內(nèi)容中分塊位置的編號(hào)構(gòu)成，它是唯一的并可以用來區(qū)別其他分塊．

整個(gè)IST表按照被請(qǐng)求次數(shù)項(xiàng)排序．被請(qǐng)求次數(shù)項(xiàng)記錄了一段時(shí)間內(nèi)該分塊被請(qǐng)求的次數(shù)．這里所說的一段時(shí)間可以是一天，一個(gè)星期或者一個(gè)月，根據(jù)總的請(qǐng)求次數(shù)來進(jìn)行調(diào)節(jié)和統(tǒng)計(jì)．同時(shí)，我們也設(shè)置了被請(qǐng)求次數(shù)的最大閾值RT．當(dāng)表中最多次數(shù)項(xiàng)的數(shù)值達(dá)到最大閾值RT后，表中所有項(xiàng)的次數(shù)都會(huì)被減半后向下取整．這樣做的目的有: (1)減少存在歷史數(shù)據(jù)影響將來數(shù)據(jù)的“緩存污染”效用，那些近段時(shí)間內(nèi)被請(qǐng)求的次數(shù)多的內(nèi)容分塊可以在較短的時(shí)間內(nèi)獲得比較高的等級(jí)而不受那些近段時(shí)間內(nèi)被請(qǐng)求次數(shù)少的內(nèi)容分塊的影響; (2)剔除那些被請(qǐng)求次數(shù)為1的內(nèi)容分塊，從而減少整個(gè)IST表的大?。?/p>

IST表中最重要的表項(xiàng)是等級(jí)項(xiàng)，分塊的等級(jí)決定了分塊被緩存的位置．假設(shè)分塊請(qǐng)求次數(shù)項(xiàng)排序數(shù)為RS，則分塊的等級(jí)LS與RS的關(guān)系如下:

其中S為緩存路由器可以容納的分塊數(shù)．由式(1)可以得出，每個(gè)等級(jí)上分塊的數(shù)量即為緩存路由器可以容納的分塊數(shù)量．因此當(dāng)分塊在請(qǐng)求次數(shù)項(xiàng)的排序發(fā)生變化時(shí)，其分塊等級(jí)并不一定會(huì)發(fā)生變化，只有當(dāng)位于等級(jí)邊緣的兩個(gè)分塊發(fā)生排序更迭時(shí)才會(huì)出現(xiàn)分塊等級(jí)的變化，進(jìn)而引發(fā)緩存路由器的緩存更新替換．這樣的策略有效的減少了分塊在沿途緩存路由器的移動(dòng)，也減少了緩存路由器對(duì)分塊重復(fù)存儲(chǔ)的開銷．

3．3．3緩存更新替換

下面介紹當(dāng)分塊等級(jí)發(fā)生變化時(shí)，如何進(jìn)行緩存的更新與替換．

我們依舊采用章節(jié)3．2中的例子來進(jìn)行說明，如圖2 (a)所示．用戶A再次發(fā)送興趣包，請(qǐng)求另一個(gè)內(nèi)容分塊C2/S1．緩存路由器在接收到興趣包后添加一個(gè)C2/S1的條目到IST表中．相同請(qǐng)求次數(shù)的情況下，新添加的條目將具有更高的排序，因此C2/S1的等級(jí)將會(huì)比具有相同請(qǐng)求次數(shù)的C1/S3高．所以當(dāng)內(nèi)容源服務(wù)器將具有等級(jí)3的內(nèi)容分塊C2/S1返回到緩存路由器C時(shí)，C首先將已存取的內(nèi)容分塊C1/S3分塊等級(jí)加1，然后剔除并向上游路由器發(fā)送，進(jìn)而釋放出空間用來緩存C2/S1．由于C的上游是內(nèi)容源服務(wù)器，因此C1/S3將直接被丟棄．此后C2/S1沿路徑到達(dá)用戶A滿足請(qǐng)求．

在圖2(b)中，用戶B再次發(fā)出興趣包請(qǐng)求分塊C2/S1．當(dāng)興趣包到達(dá)A后，A更新IST表，C2/S1的被請(qǐng)求次數(shù)變?yōu)?從而超越分塊C1/S2，兩者的分塊等級(jí)也發(fā)生了互換．當(dāng)興趣包到達(dá)C后，請(qǐng)求將直接由C處的緩存滿足．當(dāng)分塊C2/S1到達(dá)B后，原本緩存在B的C1/S2會(huì)被修改分塊等級(jí)推送到上層路由器C進(jìn)行緩存．然后B緩存分塊C2/S1．

當(dāng)緩存路由器本地緩存有興趣包所請(qǐng)求的分塊，緩存路由器將興趣包中攜帶的分塊等級(jí)與本地緩存分塊等級(jí)進(jìn)行比較: (1)興趣包分塊等級(jí)高于本地緩存分塊等級(jí)，緩存分塊將會(huì)在本地刪除并向下游路由器傳輸滿足請(qǐng)求并緩存; (2)興趣包分塊等級(jí)等于本地緩存分塊等級(jí)，緩存分塊將不會(huì)在本地刪除并向下游路由器傳輸滿足請(qǐng)求; (3)興趣包分塊等級(jí)低于本地緩存分塊等級(jí)，緩存分塊將會(huì)在本地刪除并同時(shí)向下游路由器傳輸滿足請(qǐng)求向上游路由器傳輸進(jìn)行緩存．

同時(shí)緩存路由器采用LRU算法來進(jìn)行緩存替換．當(dāng)某個(gè)緩存路由器緩存空間滿了后，再有新的內(nèi)容分塊到達(dá)需要緩存時(shí)，緩存路由器會(huì)把緩存隊(duì)列中最久沒有被請(qǐng)求的緩存分塊移除，再把其分塊等級(jí)加1后發(fā)送給上游緩存路由器．由于下游的緩存路由器存儲(chǔ)的內(nèi)容分塊比上游存儲(chǔ)的內(nèi)容分塊具有更高的流行度，因此將移除的緩存分塊推送給上游路由器而不是簡單的刪除可以有效的減少再次請(qǐng)求并緩存的過程，同時(shí)也能提高緩存命中率．

這樣單純通過興趣包與內(nèi)容分塊數(shù)據(jù)包中分塊等級(jí)的攜帶，就能實(shí)現(xiàn)緩存分塊按照用戶請(qǐng)求的流行度進(jìn)行分布，節(jié)省了緩存路由器之間緩存信息的通告開銷，也不需要收集全網(wǎng)的內(nèi)容分布信息來進(jìn)行緩存決策，最大化的利用了緩存資源，實(shí)現(xiàn)了緩存路由器之間路由緩存的隱式協(xié)作．

3．3．4 LICA方案定性分析

與其他隱式協(xié)作方案相比［9～11］，本方案在興趣包與內(nèi)容分塊數(shù)據(jù)包原包的基礎(chǔ)上加入分塊等級(jí)的字段來實(shí)現(xiàn)緩存路由器之間的緩存隱式協(xié)作，因而增加了每個(gè)緩存路由器讀取該字段的開銷以及與本身層級(jí)比較的計(jì)算代價(jià)．但相比于其他顯式協(xié)作方案［7，8］，本方案在實(shí)現(xiàn)緩存協(xié)作的過程中并沒有引入新的數(shù)據(jù)包，只需要讀取一個(gè)字段的數(shù)據(jù)即可以實(shí)現(xiàn)緩存路由器之間的協(xié)作．相比于緩存空間利用率以及緩存效率的提高，這些代價(jià)可以忽略不計(jì)．

另一方面，本方案需要每個(gè)連接用戶的緩存路由器中維護(hù)一個(gè)IST表，并對(duì)收到請(qǐng)求進(jìn)行統(tǒng)計(jì)并劃分等級(jí)，相當(dāng)于維護(hù)一個(gè)LFU表并對(duì)數(shù)量為n的數(shù)據(jù)進(jìn)行查找，添加和刪除，故每次操作的時(shí)間復(fù)雜度為O(n)．但由于緩存節(jié)點(diǎn)層級(jí)有限，且每個(gè)緩存節(jié)點(diǎn)緩存空間有限，緩存節(jié)點(diǎn)可以根據(jù)緩存節(jié)點(diǎn)層級(jí)和緩存空間的大小決定IST表的閾值，當(dāng)表項(xiàng)超過該閾值時(shí)對(duì)表項(xiàng)進(jìn)行清理，進(jìn)而可以減小維護(hù)LST表的復(fù)雜度．同時(shí)，可以通過引入最小堆以及hash表等方法來實(shí)現(xiàn)對(duì)LFU算法的優(yōu)化［20］，進(jìn)而降低LST表的維護(hù)開銷．

4　仿真分析

為了驗(yàn)證本文提出的LICA策略的緩存性能，本文在OMNeT++平臺(tái)上開發(fā)了模擬器對(duì)以上方案進(jìn)行仿真實(shí)現(xiàn)以及性能評(píng)估．主要考慮的性能參數(shù)包括路由器緩存命中率，用戶獲取內(nèi)容跳數(shù)值以及源服務(wù)器流量與系統(tǒng)總流量的比值．

4.1仿真環(huán)境和參數(shù)配置

我們將LICA與WAVE、ProbCache以及CLS方案進(jìn)行了對(duì)比．其中我們假設(shè)WAVE的參數(shù)與［10］中相同且x =2，ProbCache的沿路緩存概率為0.7，CLS的參數(shù)設(shè)置為Hth =2．仿真拓?fù)洳捎门cProbCache以及CLS相同的樹形拓?fù)洌負(fù)渲邪?個(gè)層級(jí)31個(gè)路由器，其中每1000個(gè)用戶與底端16個(gè)葉子節(jié)點(diǎn)的路由器相連，源服務(wù)器與頂端的根節(jié)點(diǎn)的路由器相連，如圖3所示．同時(shí)，我們假設(shè)內(nèi)容數(shù)量為10000個(gè)，每個(gè)內(nèi)容大小相同為10Mbytes，并且平均分為k = 10個(gè)分塊;每個(gè)緩存路由器的緩存空間為1000Mbytes，即可以緩存1000個(gè)緩存分塊．此外，在仿真過程中每個(gè)用戶將會(huì)向連接的路由器發(fā)送10000個(gè)對(duì)內(nèi)容的請(qǐng)求，并且請(qǐng)求的到達(dá)符合泊松分布．用戶對(duì)內(nèi)容的請(qǐng)求分布符合Zipf分布［16］，其中0．5≤α≤1，默認(rèn)情況下α=0．8．

4.2仿真結(jié)果分析

首先我們考慮緩存空間大小對(duì)系統(tǒng)緩存性能的影響．每個(gè)緩存路由器的緩存空間S分別設(shè)置成500 Mbytes、1000 Mbytes、1500 Mbytes和2000Mbytes．如圖4所示，我們考慮不同緩存空間下四種緩存策略的內(nèi)容分塊平均緩存命中率、請(qǐng)求的平均跳數(shù)與源服務(wù)器流量占比的仿真對(duì)比．如圖4(a)所示，隨著路由器緩存空間的變化，LICA比其他三種緩存路由器具有更高的緩存命中率，并且增長速度也比其他的策略要高．LICA的緩存命中率在不同S時(shí)比CLS分別高37.4％，41.4％，33.5％以及33.2％．如圖4(b)所示，LICA在請(qǐng)求平均跳數(shù)這項(xiàng)能比較中也具有更好的性能．其中當(dāng)S = 2000Mbytes時(shí)，LICA的請(qǐng)求評(píng)價(jià)跳數(shù)為1.89，比其他三種緩存策略分別小0.74，1.09以及0.65跳．圖4(c)則展示了源服務(wù)器流量占比受α的影響，源服務(wù)器流量占比表示源服務(wù)器發(fā)送的內(nèi)容流量與全網(wǎng)所有發(fā)送的內(nèi)容流量和的比值，源服務(wù)器流量占比從網(wǎng)絡(luò)流量的角度反映了緩存系統(tǒng)的性能．當(dāng)S = 2000Mbytes時(shí)，LICA的源服務(wù)器流量占比僅為7.8％，說明絕大部分的流量都又緩存路由器提供，大大減小了系統(tǒng)流量開銷．

接下來我們考慮Zipf分布參數(shù)α對(duì)系統(tǒng)緩存性能的影響．圖5是LICA與WAVE、ProbCache以及CLS四種緩存策略在Zipf分布參數(shù)α變化情況下，內(nèi)容分塊平均緩存命中率、請(qǐng)求的平均跳數(shù)與源服務(wù)器流量占比的仿真對(duì)比．如圖5(a)所示，當(dāng)0.5≤α≤1，通過統(tǒng)計(jì)拓?fù)渲兴新酚善鞯木彺婷新?，?jì)算整個(gè)系統(tǒng)的內(nèi)容分塊平均緩存命中率．在α變化的過程中，LICA始終比其他三種緩存策略具有更高的緩存命中率，其中當(dāng)α=0.8時(shí)，LICA的緩存命中率比WAVE、ProbCache以及CLS分別提高了28.8％、82.1％和41.4％．如圖5 (b)所示，LICA在請(qǐng)求平均跳數(shù)這項(xiàng)性能中也展示了很大的優(yōu)勢(shì)．當(dāng)α= 0.8時(shí)，LICA的請(qǐng)求平均跳數(shù)比其他三種策略分別提高了0.55、1.21和0.71跳．通過LICA的方案，用戶可以從更近的緩存路由器獲得內(nèi)容，從而減少了用戶等待時(shí)延，提高了用戶體驗(yàn)．圖5(c)則展示了源服務(wù)器流量占比受α的影響，相比與其他三個(gè)緩存策略，當(dāng)α變化時(shí)LICA有更小的源服務(wù)器流量占比．當(dāng)α=0.8時(shí)，LICA的源服務(wù)器流量占比分別為WAVE、ProbCache和CLS的75.5％、53.6％和71.9％．

綜上所述，本文提出的LICA緩存策略在內(nèi)容分塊平均緩存命中率、請(qǐng)求的平均跳數(shù)與源服務(wù)器流量占比這三種緩存性能參數(shù)中都比其他三種緩存策略有更好的緩存性能．

5　結(jié)束語

本文針對(duì)現(xiàn)有ICN網(wǎng)絡(luò)域內(nèi)緩存策略沒有充分考慮到內(nèi)容分塊請(qǐng)求流行度的問題，提出了一種基于內(nèi)容分塊流行度分級(jí)的緩存策略．仿真測(cè)試結(jié)果表明:該方案可以利用細(xì)粒度的內(nèi)容分塊流行度這一特性，提高緩存路由器緩存命中率，減小用戶請(qǐng)求內(nèi)容時(shí)延進(jìn)而提升用戶對(duì)實(shí)時(shí)業(yè)務(wù)的服務(wù)體驗(yàn)，又可減小整個(gè)系統(tǒng)的流量．下一步工作將研究大規(guī)模系統(tǒng)下集中控制緩存策略的方案設(shè)計(jì)．

參考文獻(xiàn)

［1］Zhang L X，Estrin D，Burke J，et al．Named Data Networking (NDN) project［R］．California: PARC，2010．

［2］Koponen T，Chawla M，Chun B．G，et al．A data-oriented (and beyond) network architecture［J］．SIGCOMM Comput Commun Rev，2007，37(4) : 181－192．

［3］Lagutin D，Visala D，Tarkoma S．Publish/subscribe for internet: Psirp perspective［R］．Towards the Future Internet Emerging Trends from European Research，2010 (4) : 75 －84．

［4］Laoutaris N，Syntila S，Stavrakakis I．Meta algorithms for hierarchical web caches［A］．Proceedings of 2004 IEEE International Conference on Performance，Computing，and Communications［C］．Phoenix，2004．445－452．

［5］Chae Y，Guo K，Buddhikot M M，et al．Silo，rainbow，and caching token: Schemes for scalable，fault tolerant stream caching［J］．Selected Areas in Communications，IEEE Journal on，2002，20(7) : 1328－1344．

［6］Zhang G，Li Y，Lin T．Caching in information centric networking: a survey［J］．Computer Networks，2013，57(16) :3128－3141．

［7］Long Y，F(xiàn)an L，Yan Z．Off-path and on-path collaborative caching in named data network［A］．Proceedings of AsiaFI ［C］．Kyoto，2012．1－8．

［8］Vassilakis V G，Al-Naday M F，Reed M J，et al．A cache-aware routing scheme for information-centric networks［A］．Proceedings of 2014 9th International Symposium on Communication Systems，Networks＆Digital Signal Processing (CSNDSP)［C］．Manchester，2014: 721－726．

［9］Psaras I，Chai，Wei Koong，Pavlou G．Probabilistic in-network caching for information-centric networks［A］．Proceedings of the Second Edition of the ICN Workshop on Information-centric Networking［C］．Helsinki，2012．55 －60．

［10］Cho K，Lee M，Park K，et al．Wave: Popularity-based and collaborative in-network caching for content-oriented networks［A］．Proceedings of 2012 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)［C］．Orlando，2012．316－321．

［11］Li Yang，Lin Tao，Tang Hui，et al．A chunk caching location and searching scheme in content centric networking ［A］．Proceeding of 2012 IEEE International Conference on Communications (ICC)［C］．Ottawa，2012．2655 －2659．

［12］Ming Zhong-xing，Xu Ming-wei; Wang Dan．Age-based cooperative caching in Information-Centric Networks ［A］．Proceedings of 2012 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS ) ［C］．Orlando，2012．268－273．

［13］Wang Wei，Sun Yi，Guo Yang，et al．CRCache: Exploiting the correlation between content popularity and network topology information for ICN caching［A］．Proceeding of 2014 IEEE International Conference on Communications (ICC)［C］．Sydney，2014．3191－3196．

［14］Bilal M，Kang S G．Time Aware Least Recent Used (TLRU) cache management policy in ICN［A］．Proceeding of 2014 16th International Conference on Advanced Communication Technology (ICACT)［C］．PyeongChang Korea，2014．528－532．

［15］Lim Sung-Hwa，Ko Young-Bae，Jung Gue-Hwan，et al．Inter-Chunk Popularity-Based Edge-First Caching in Content-Centric Networking［J］．IEEE Communications Letters，2014，18(8) : 1331－1334．

［16］Breslau L，Cao P，F(xiàn)an L，et al．Web caching and zipf-like distributions: evidence and implications［A］．Proceedings of INFOCOM'99［C］．New York，1999．126－134．

［17］Xylomenos G，Ververidis C，Siris V，et al．A Survey of Information-Centric Networking Research［J］．IEEE Communications Surveys and Turorials，2014，16 (2) : 1024 －1049．

［18］Ahlgren B，Dannewitz C，Imbrenda C，et al．A Survey of Information-Centric Networking［J］．IEEE Communications Magazine，2012，50(7) : 26－36．

［19］Luo H，Chen Z，Cui J，et al．CoLoR: an information-centric Internet architecture for innovations［J］．IEEE Network Magazine，2014，28(3) : 4－10．

［20］Ketan S，Mitra A，Matani D．An O(1) algorithm for implementing the LFU cache eviction scheme［OL］．http: / / dhruvbird．com /lfu．pdf，2010．

曾宇晶男，1987年8月出生，湖南邵東人，博士研究生，2009年在北京交通大學(xué)獲得工學(xué)學(xué)士學(xué)位，并于同年開始攻讀工學(xué)博士學(xué)位．主要從事下一代互聯(lián)網(wǎng)、智慧協(xié)同網(wǎng)絡(luò)、信息中心網(wǎng)絡(luò)的路由與緩存策略研究．

E-mail: 09111043@ bjtu．edu．cn

靳明雙女，1990年9月出生，黑龍江省哈爾濱人，博士研究生，2013年在北京交通大學(xué)獲得工學(xué)學(xué)士學(xué)位，并于同年碩博連讀攻讀工學(xué)博士學(xué)位．主要從事下一代互聯(lián)網(wǎng)、智慧協(xié)同網(wǎng)絡(luò)、軟件定義網(wǎng)絡(luò)方面的研究．

E-mail: 13120082@ bjtu．edu．cn

羅洪斌男，1977年1月出生，重慶忠縣人，北京交通大學(xué)教授、博士生導(dǎo)師，現(xiàn)任北京交通大學(xué)下一代互聯(lián)網(wǎng)互連設(shè)備國家工程實(shí)驗(yàn)室副主任、中國通信學(xué)會(huì)第四屆青年工作委員會(huì)委員、北京通信學(xué)會(huì)第八屆理事會(huì)理事，入選教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃．目前主要從事未來互聯(lián)網(wǎng)體系架構(gòu)、理論與關(guān)鍵技術(shù)的研究，正主持多項(xiàng)國家973、863、國家自然科學(xué)基金項(xiàng)目．近年來在IEEE/ACM Transactions on Networking，IEEE Journal on Selected Areas in Communications，IEEE Network等本領(lǐng)域高水平期刊與國際會(huì)議發(fā)表論文50余篇．

E-mail: hbluo@ bjtu．edu．cn

LICA: A Segment-Popularity Based Caching Scheme in ICN

ZENG Yu-jing，JIN Ming-shuang，LUO Hong-bin
(National Engineering Lab for Next Generation Internet Interconnection Devices，Beijing Jiaotong University，Beijing 100044，China)

Abstract:In-network caching schemes in information-centric networking (ICN) often consider the popularity granularity in the content level，which ignores the character that different parts of a content may have different popularity．This paper proposes a segment Level-based Implicit Cooperation cAche (LICA) scheme．LICA assigns a cache router a level based on its location and archives implicit cooperation with tags in interest and data packets．We compare LICA with other caching schemes and the simulation results show that LICA has higher average hit ratio，lower average hop count of content retrieval，and reduces the network traffic than other schemes，which will improve the experience of users in real-time streaming media service．

Key words:information centric networking; in-network caching; segment popularity

作者簡介

基金項(xiàng)目:國家973重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(No．2013CB329100) ;國家自然科學(xué)基金重點(diǎn)項(xiàng)目(No．61271200，No．61422101，No．61232017)

收稿日期:2015-03-18;修回日期: 2015-08-19;責(zé)任編輯:郭游

DOI:電子學(xué)報(bào)URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．017

中圖分類號(hào):TN915

文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):0372-2112 (2016) 02-0358-07