郭 江 王 淼 張玉軍

1(中國科學(xué)院計(jì)算技術(shù)研究所 北京 100190) 2(中國科學(xué)院大學(xué) 北京 100049)

隨著互聯(lián)網(wǎng)規(guī)模和業(yè)務(wù)類型的爆炸式增長，主流應(yīng)用模式從主機(jī)互聯(lián)和計(jì)算資源共享逐步轉(zhuǎn)變?yōu)樾畔@取服務(wù)，例如視頻分發(fā)、文件下載等[1].以TCP/IP為基礎(chǔ)的互聯(lián)網(wǎng)采用以IP地址為中心的端到端通信模式，導(dǎo)致網(wǎng)絡(luò)上存在大量數(shù)據(jù)的重復(fù)傳輸，造成骨干網(wǎng)絡(luò)的流量激增.這種通信模式與互聯(lián)網(wǎng)主流應(yīng)用的不匹配，導(dǎo)致現(xiàn)有互聯(lián)網(wǎng)在擴(kuò)展性、動態(tài)性、安全可控性等方面面臨嚴(yán)峻的挑戰(zhàn)[2].為解決TCP/IP體系結(jié)構(gòu)存在的問題，全新的信息中心網(wǎng)絡(luò)(information-centric networking, ICN)[3]設(shè)計(jì)思想被提出，其中命名數(shù)據(jù)網(wǎng)絡(luò)(named data networking, NDN)[4-5]是最受關(guān)注的ICN方案之一.NDN網(wǎng)絡(luò)以內(nèi)容本身為中心，采用用戶請求驅(qū)動通信模式，依據(jù)內(nèi)容名字進(jìn)行路由與轉(zhuǎn)發(fā)，并提供基于內(nèi)嵌的網(wǎng)絡(luò)化緩存機(jī)制，這種設(shè)計(jì)使得網(wǎng)絡(luò)節(jié)點(diǎn)(例如路由節(jié)點(diǎn))被賦予存儲功能，可直接向用戶提供信息與服務(wù)，實(shí)現(xiàn)用戶對內(nèi)容的高速獲取，有效降低網(wǎng)絡(luò)帶寬的占用，減輕內(nèi)容發(fā)布者的響應(yīng)負(fù)擔(dān)，從而極大緩解網(wǎng)絡(luò)流量爆炸性增長問題.

現(xiàn)有NDN對網(wǎng)絡(luò)化緩存的設(shè)計(jì)相對簡單，只注重緩存基本功能的實(shí)現(xiàn)，缺乏對性能方面的考慮.NDN采用泛在緩存機(jī)制(leave copy everywhere, LCE)[6]，即內(nèi)容發(fā)送至用戶的傳輸路徑上所有路由節(jié)點(diǎn)都無差別地對內(nèi)容進(jìn)行緩存.這種機(jī)制簡單、易于部署，但存在2個(gè)問題，使得緩存性能較低：

1) 冗余緩存，泛在緩存導(dǎo)致內(nèi)容傳輸路徑上各節(jié)點(diǎn)重復(fù)緩存相同內(nèi)容副本，這種逐跳緩存使得網(wǎng)內(nèi)緩存內(nèi)容的同質(zhì)化，特別在緩存容量有限的條件下，降低整個(gè)網(wǎng)絡(luò)的緩存利用率.已有研究表明[7]：在某些場景下，沿路徑的隨機(jī)緩存機(jī)制(即在內(nèi)容發(fā)送的下行路徑上隨機(jī)選擇一個(gè)節(jié)點(diǎn)對內(nèi)容進(jìn)行緩存)甚至都比LCE機(jī)制能獲得更好的性能提升.

2) 內(nèi)容緩存無差別對待，LCE機(jī)制對于所有的內(nèi)容都執(zhí)行相同的緩存決策，缺乏針對內(nèi)容類型的差異化緩存服務(wù)需求考慮，難以提高緩存性能.

為了解決泛在緩存中的冗余緩存等問題，研究者們提出了各種優(yōu)化緩存方法[7-14].現(xiàn)有工作[7-10,12-13]主要從單一因素考慮緩存，難以在網(wǎng)絡(luò)化緩存系統(tǒng)中做出合理的緩存決策，例如網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、熱度內(nèi)容感知、基于概率性選擇.盡管工作[11]結(jié)合網(wǎng)絡(luò)拓?fù)浜蛢?nèi)容熱度2個(gè)方面綜合考慮緩存決策，但忽略內(nèi)容業(yè)務(wù)類型重要影響因素.

上述緩存優(yōu)化方案無法準(zhǔn)確地降低冗余緩存，其根本原因主要有2個(gè):1)現(xiàn)有網(wǎng)絡(luò)化緩存機(jī)制不能識別內(nèi)容的業(yè)務(wù)類型，無法區(qū)分哪些內(nèi)容是否需要緩存服務(wù);2)基于單一信息的策略難以實(shí)現(xiàn)精確緩存，從信息論角度看，信息越少則變量的熵值越大，即不確定性越大.因此，本文綜合考慮網(wǎng)絡(luò)拓?fù)浜蛢?nèi)容類型，提出了一種命名數(shù)據(jù)網(wǎng)絡(luò)中基于內(nèi)容類型的隔跳概率緩存機(jī)制(content type based jumping probability caching mechanism in NDN, CTJP).該機(jī)制允許沿途路由節(jié)點(diǎn)首先執(zhí)行隔跳待定緩存策略，使得內(nèi)容副本存儲在沿途非連續(xù)節(jié)點(diǎn)，有效地減少冗余緩存；然后，執(zhí)行基于內(nèi)容類型的概率緩存策略，即根據(jù)內(nèi)容不同的業(yè)務(wù)特征，將緩存內(nèi)容劃分為4種類型：收到內(nèi)容包的路由節(jié)點(diǎn)根據(jù)內(nèi)容類型和請求聚合度計(jì)算緩存概率；分別提供無緩存、網(wǎng)絡(luò)邊緣緩存、網(wǎng)絡(luò)次邊緣緩存以及網(wǎng)絡(luò)核心緩存；減少冗余緩存；提升用戶獲取內(nèi)容的效率.實(shí)驗(yàn)結(jié)果表明，與典型緩存方案相比，CTJP機(jī)制能夠降低緩存冗余，同時(shí)實(shí)現(xiàn)用戶對內(nèi)容的高效獲取.

1 相關(guān)工作

1.1 NDN背景

NDN網(wǎng)絡(luò)包括用戶(user)、內(nèi)容發(fā)布者(content provider)和路由器(router)3類實(shí)體，其數(shù)據(jù)傳輸主要包括2種類型：興趣包(interest)和數(shù)據(jù)包(data).興趣包是由用戶發(fā)送的數(shù)據(jù)請求包，其中包括請求的內(nèi)容名稱(contentName)等；數(shù)據(jù)包是由發(fā)布者或路由器根據(jù)用戶的請求返回的內(nèi)容，其中包括內(nèi)容名稱(contentName)、內(nèi)容本身(content)等.NDN網(wǎng)絡(luò)中單個(gè)節(jié)點(diǎn)通信流程如圖1所示.每個(gè)實(shí)體包含3種數(shù)據(jù)結(jié)構(gòu)，分別是內(nèi)容存儲(content store, CS)、待定興趣表(pending interest table, PIT)和轉(zhuǎn)發(fā)信息庫(forwarding information base, FIB).CS用于存儲接收到的數(shù)據(jù)包，對于后續(xù)相同的內(nèi)容請求從本地響應(yīng)數(shù)據(jù)包，有利于減少對于發(fā)布者的訪問次數(shù)，提升內(nèi)容分發(fā)的傳輸效率；PIT記錄待轉(zhuǎn)發(fā)興趣包的內(nèi)容名稱以及接入接口，并且匯聚相同的興趣包在一個(gè)表項(xiàng)中；FIB依靠路由協(xié)議生成，記錄興趣包轉(zhuǎn)發(fā)下一跳接口.

Fig. 1 Communication flow of single node in NDN圖1 命名數(shù)據(jù)網(wǎng)絡(luò)單個(gè)節(jié)點(diǎn)通信流程

NDN網(wǎng)絡(luò)用戶獲取內(nèi)容的過程分3個(gè)步驟：

1) 當(dāng)需要內(nèi)容時(shí)，用戶發(fā)送一個(gè)興趣包.路由器收到興趣包后，首先查找CS是否有請求的數(shù)據(jù)，如果有，則從興趣包接入接口返回?cái)?shù)據(jù)包并丟棄興趣包；否則，繼續(xù)查找PIT，查找之前是否轉(zhuǎn)發(fā)來自其他節(jié)點(diǎn)的，并且與該條目的請求內(nèi)容相同的興趣包.如果找到，則將本次興趣包的接入接口添加到對應(yīng)的PIT信息條目中；否則，在PIT中創(chuàng)建興趣包接入接口的信息條目，繼續(xù)查找FIB，進(jìn)行路由尋址.

2) 興趣包到達(dá)發(fā)布者并找到內(nèi)容對象時(shí)，興趣包被丟棄，響應(yīng)的信息以數(shù)據(jù)包的形式原路返回.當(dāng)數(shù)據(jù)包到達(dá)路由器時(shí)，首先查找CS，如果有相同的緩存數(shù)據(jù)，則丟棄數(shù)據(jù)包；若沒有，則與PIT中條目匹配.如果PIT中有匹配條目，則向相應(yīng)的接口轉(zhuǎn)發(fā)數(shù)據(jù)包，緩存數(shù)據(jù)包在CS中，并刪除PIT中的匹配條目；否則丟棄數(shù)據(jù)包.

3) 用戶在接收到數(shù)據(jù)包后進(jìn)行簽名驗(yàn)證，確保內(nèi)容完整性和真實(shí)性.

1.2 內(nèi)容業(yè)務(wù)劃分

NDN網(wǎng)絡(luò)提供差異化服務(wù)主要體現(xiàn)在請求路由、內(nèi)容轉(zhuǎn)發(fā)、緩存策略等方面[15-24].Kim等人[15]提出了差異化服務(wù)的轉(zhuǎn)發(fā)和緩存機(jī)制，由內(nèi)容發(fā)布者標(biāo)記內(nèi)容屬于哪個(gè)分類并注冊到網(wǎng)絡(luò)，當(dāng)路由節(jié)點(diǎn)收到數(shù)據(jù)包時(shí)，讀取數(shù)據(jù)包的標(biāo)記判斷內(nèi)容屬于哪個(gè)分類，并將內(nèi)容緩存到該分類對應(yīng)的緩存空間中.該模型實(shí)現(xiàn)了差異化服務(wù)的緩存，但每種類型的緩存空間大小是固定的，而且在沿途節(jié)點(diǎn)都緩存數(shù)據(jù)包，容易造成數(shù)據(jù)冗余，浪費(fèi)寶貴的緩存資源.針對視頻流業(yè)務(wù)，Li等人[16]提出了一種沿途協(xié)作緩存算法，節(jié)點(diǎn)記錄內(nèi)容索引與其標(biāo)簽值相等的數(shù)據(jù)單元，避免相同內(nèi)容的重復(fù)冗余緩存.Guo等人[17]設(shè)計(jì)了一種支持實(shí)時(shí)內(nèi)容快速傳輸?shù)臋C(jī)制BoNDN，通過在路由節(jié)點(diǎn)增加訂閱推送表，實(shí)現(xiàn)對實(shí)時(shí)數(shù)據(jù)包轉(zhuǎn)發(fā).該方案對于非實(shí)時(shí)業(yè)務(wù)內(nèi)容采用NDN原有轉(zhuǎn)發(fā)機(jī)制，對于實(shí)時(shí)動態(tài)業(yè)務(wù)內(nèi)容(例如區(qū)塊鏈中的區(qū)塊)采用推送機(jī)制，但缺乏緩存策略的考慮.

1.3 緩存策略

緩存策略是NDN網(wǎng)絡(luò)研究熱點(diǎn)之一，考慮緩存哪些內(nèi)容、緩存位置選擇、緩存內(nèi)容替換等問題中實(shí)現(xiàn)差異化緩存，獲取較高命中率.Laoutaris等人[8]提出了LCD(leave copy down)緩存機(jī)制，內(nèi)容響應(yīng)過程中僅在命中節(jié)點(diǎn)的下一跳節(jié)點(diǎn)存儲內(nèi)容副本，隨著后續(xù)相同的用戶請求不斷達(dá)到，內(nèi)容副本逐步被拉向用戶側(cè).這種隱式協(xié)作緩存方法易于實(shí)現(xiàn)，但是隨著重復(fù)請求增多(例如，請求流行度高的內(nèi)容)，沿傳輸路徑上的各路由節(jié)點(diǎn)都緩存內(nèi)容副本，因此仍存在無效緩存和冗余緩存問題.Psaras等人[9]提出了基于概率緩存方法ProbCache，傳輸路徑上的各路由節(jié)點(diǎn)基于一定的概率決定是否緩存內(nèi)容，從而減少傳輸路徑上的內(nèi)容副本數(shù)量.Sun等人[25]提出了基于路由跳數(shù)的概率緩存方法HPC，引入路由跳數(shù)作為緩存權(quán)重，計(jì)算緩存概率，使得距離用戶側(cè)的緩存可能性越大，從而減少用戶請求的時(shí)延.這2種方法一定程度上減小網(wǎng)內(nèi)緩存冗余，但對于那些共享度低、私有性強(qiáng)的動態(tài)內(nèi)容依舊會進(jìn)行緩存，顯然這類內(nèi)容緩存造成資源浪費(fèi).Chai等人[7]提出了基于節(jié)點(diǎn)中心度的緩存策略Betw，通過統(tǒng)計(jì)路由節(jié)點(diǎn)的中心度值，并以其值作為衡量節(jié)點(diǎn)的重要程度，由匯聚能力更強(qiáng)中心度最高的節(jié)點(diǎn)對內(nèi)容進(jìn)行緩存.這種策略使得內(nèi)容過于集中在中心度高的節(jié)點(diǎn)上，容易導(dǎo)致這類節(jié)點(diǎn)發(fā)生高頻緩存替換操作，不利于整個(gè)網(wǎng)絡(luò)化緩存性能的提升.Cho等人[10]提出了基于熱度的緩存機(jī)制WAVE，用戶對同一內(nèi)容的不同分塊的請求具有連續(xù)性，根據(jù)內(nèi)容熱度決定對該內(nèi)容不同塊的緩存數(shù)量，以便減少非熱度內(nèi)容的緩存.然而這類基于本地視圖的緩存策略因忽略了邊緣節(jié)點(diǎn)對請求熱度的過濾影響[26]而無法準(zhǔn)確感知熱度內(nèi)容，也不能合理規(guī)劃熱度內(nèi)容的緩存位置.另外，Zheng等人[11]提出了基于網(wǎng)絡(luò)拓?fù)浜蛢?nèi)容熱度的緩存策略BEP，通過將熱度較高的內(nèi)容緩存在重要程度較高的節(jié)點(diǎn)，降低緩存替換率，減少冗余緩存，但忽略了內(nèi)容類型對緩存的影響.

綜上，目前的研究已經(jīng)取得了許多積極的成果，多數(shù)工作是基于網(wǎng)絡(luò)拓?fù)?、?nèi)容熱度等單一因素考慮緩存，以提高緩存利用率，盡管BEP結(jié)合網(wǎng)絡(luò)拓?fù)浜蛢?nèi)容熱度2方面進(jìn)行緩存決策，但這些工作都沒有考慮內(nèi)容類型這一重要影響因素.本文引入內(nèi)容類型因素，并考慮網(wǎng)絡(luò)拓?fù)浜蛢?nèi)容熱度方面，提出了一種命名數(shù)據(jù)網(wǎng)絡(luò)中基于內(nèi)容類型的隔跳概率緩存方法，旨在兼顧效率的同時(shí)解決冗余緩存問題.

2 CTJP機(jī)制

CTJP機(jī)制整體工作流程如圖2所示，其設(shè)計(jì)思想：對接收的數(shù)據(jù)包，網(wǎng)絡(luò)節(jié)點(diǎn)先依據(jù)PendingCache標(biāo)識，判斷是否有必要緩存，若無需緩存，則直接轉(zhuǎn)發(fā)；否則執(zhí)行隔離待定緩存策略，進(jìn)一步查看CotentType標(biāo)識，判斷數(shù)據(jù)包所屬內(nèi)容類型，并提供不同的緩存決策：無緩存、基于網(wǎng)絡(luò)邊緣概率緩存、基于網(wǎng)絡(luò)次邊緣概率緩存和基于網(wǎng)絡(luò)核心概率緩存.首先介紹CTJP機(jī)制支持的內(nèi)容類型以及包格式擴(kuò)展，然后具體說明緩存算法，最后描述數(shù)據(jù)傳輸中緩存的詳細(xì)過程.

Fig. 2 Workflow of CTJP圖2 CTJP機(jī)制整體工作流程

2.1 內(nèi)容類型定義

考慮用戶、內(nèi)容發(fā)布者、中間路由對質(zhì)量服務(wù)QoS的要求，首先對不同業(yè)務(wù)內(nèi)容進(jìn)行類型劃分，以便支持后續(xù)的內(nèi)容緩存策略.根據(jù)業(yè)務(wù)的共享程度、時(shí)延要求、帶寬占用等特征，將緩存內(nèi)容劃分為4類：動態(tài)類、實(shí)時(shí)類、大數(shù)據(jù)類、小數(shù)據(jù)類，類型代碼分別為00，01，10，11，如圖3所示.對于動態(tài)類(類型1)，例如郵件、即時(shí)通信等，該類業(yè)務(wù)內(nèi)容后續(xù)共享程度低[17]，中間路由沒有必要浪費(fèi)寶貴的資源對其緩存；對于實(shí)時(shí)類(類型2)，例如直播視頻、網(wǎng)絡(luò)電視等，該類業(yè)務(wù)后續(xù)共享程度高，此外請求時(shí)延要求嚴(yán)格[16]，將其緩存在網(wǎng)絡(luò)邊緣節(jié)點(diǎn)比在網(wǎng)絡(luò)核心節(jié)點(diǎn)更好地提供低延時(shí)服務(wù)；大數(shù)據(jù)類(類型3)，例如離線視頻、音頻等，該類業(yè)務(wù)包含的內(nèi)容文件容量大，通常被劃分為多個(gè)數(shù)據(jù)單元(內(nèi)容塊)，除了時(shí)延要求低于實(shí)時(shí)類業(yè)務(wù)，但對于帶寬資源要求大，將其緩存在網(wǎng)絡(luò)次邊緣，既避免占用網(wǎng)絡(luò)邊緣稀缺資源，又節(jié)省網(wǎng)絡(luò)帶寬的占用；小數(shù)據(jù)類(類型4)，例如網(wǎng)頁、共享文件等，該類業(yè)務(wù)內(nèi)容文件容量小，對于時(shí)延和帶寬要求比較低[27]，將其緩存在網(wǎng)絡(luò)核心節(jié)點(diǎn)，有利于網(wǎng)絡(luò)緩存負(fù)載平衡.

Fig. 3 Types of content service圖3 內(nèi)容業(yè)務(wù)分類

2.2 包格式擴(kuò)展

為支持?jǐn)?shù)據(jù)傳輸過程中基于內(nèi)容業(yè)務(wù)的緩存策略，在保留NDN原有的基礎(chǔ)上，對興趣包和數(shù)據(jù)包的格式進(jìn)行擴(kuò)展，如圖4所示.興趣包僅增加IntHop字段，用于記錄興趣包轉(zhuǎn)發(fā)的路由跳數(shù).數(shù)據(jù)包增加3個(gè)字段：PendingCache，ContentType，DataHop，其中PendingCache標(biāo)志是否執(zhí)行隔跳待定緩存策略，ContentType標(biāo)識數(shù)據(jù)包內(nèi)容的業(yè)務(wù)類型，DataHop記錄的是數(shù)據(jù)包沿途返回中經(jīng)過路由的跳數(shù).

Fig. 4 Extended packet format圖4 擴(kuò)展后的包格式

Fig. 5 Based on content type probability caching policy圖5 基于內(nèi)容類型的概率緩存策略

2.3 緩存算法

在數(shù)據(jù)包返回給用戶階段，沿途路由節(jié)點(diǎn)根據(jù)緩存算法對該內(nèi)容選擇性緩存.緩存算法分為2個(gè)部分，隔跳待定緩存策略和基于內(nèi)容類型的概率緩存策略.

2.3.1 隔跳待定緩存策略

本文將數(shù)據(jù)存儲在非連續(xù)的傳輸節(jié)點(diǎn)上，從空間上減少冗余緩存.隨著隔跳跨度的增加，盡管緩存的冗余將逐漸減小，但是其他用戶請求響應(yīng)的時(shí)間也將增大.具體選擇相隔多少跳數(shù)進(jìn)行緩存數(shù)據(jù)比較合理，還需進(jìn)行建模分析.在此，我們通過路由節(jié)點(diǎn)對數(shù)據(jù)包進(jìn)行隔一跳待定緩存，既有效地減半冗余緩存，提高網(wǎng)絡(luò)化緩存內(nèi)容的多樣性，節(jié)省對數(shù)據(jù)包緩存所需的操作開銷，又避免用戶請求響應(yīng)時(shí)間的增大.具體地，沿途路由節(jié)點(diǎn)對到達(dá)的數(shù)據(jù)包進(jìn)行逐一檢查，若數(shù)據(jù)包的擴(kuò)展字段PendingCache值標(biāo)記為1，則待定緩存到本地，并對PendingCache值取反操作，即標(biāo)記為0；否則不進(jìn)行緩存，并對PendingCache值取反操作，即標(biāo)記為1.

2.3.2 基于內(nèi)容類型的概率緩存策略

為了進(jìn)一步減少冗余緩存，基于內(nèi)容類型概率緩存策略提供差異化的網(wǎng)絡(luò)緩存服務(wù).根據(jù)第2節(jié)中提出的4種內(nèi)容類型，分別提供無緩存、網(wǎng)絡(luò)邊緣緩存、網(wǎng)絡(luò)次邊緣緩存，網(wǎng)絡(luò)核心緩存.針對動態(tài)類內(nèi)容，沿途路由節(jié)點(diǎn)不進(jìn)行任何緩存操作，從而節(jié)省大量不必要的緩存空間和時(shí)間；針對實(shí)時(shí)類內(nèi)容，沿途路由節(jié)點(diǎn)采用基于網(wǎng)絡(luò)邊緣概率緩存方法，如圖5(a)所示，即從內(nèi)容發(fā)布者到用戶傳輸路徑中，中間路由節(jié)點(diǎn)以遞增概率緩存數(shù)據(jù)包，使得類型2內(nèi)容大概率緩存在網(wǎng)絡(luò)邊緣，以滿足用戶低時(shí)延的服務(wù)要求；針對大數(shù)據(jù)類內(nèi)容，沿途路由節(jié)點(diǎn)執(zhí)行基于遞增遞減概率緩存方法，如圖5(b)所示，即中間路由節(jié)點(diǎn)先以遞增概率再以遞減概率緩存數(shù)據(jù)包，使得類型3內(nèi)容大概率緩存在網(wǎng)絡(luò)次邊緣，以節(jié)省帶寬；針對小數(shù)據(jù)類內(nèi)容，沿途路由節(jié)點(diǎn)采用基于網(wǎng)絡(luò)核心概率緩存方法，如圖5(c)所示，即中間路由節(jié)點(diǎn)以遞減概率緩存數(shù)據(jù)包，使得類型4內(nèi)容大概率緩存在網(wǎng)絡(luò)核心，避免在網(wǎng)絡(luò)邊緣匯聚過多而造成高頻緩存替換操作.

緩存策略具體過程如算法1所示，當(dāng)用戶發(fā)送興趣包時(shí)，通過興趣包的上行逐跳傳輸，依次更新傳輸路徑跳數(shù)IntHop，即每當(dāng)興趣包抵達(dá)下一個(gè)節(jié)點(diǎn)，傳輸跳數(shù)加1；興趣包到達(dá)內(nèi)容發(fā)布者，記錄的就是沿途傳輸路徑節(jié)點(diǎn)的數(shù)目.當(dāng)數(shù)據(jù)包沿回路傳輸時(shí)，沿途節(jié)點(diǎn)先判斷數(shù)據(jù)包內(nèi)容類型，按照4種方式計(jì)算緩存概率：

1) 若ContentType=00，則不進(jìn)行緩存并對數(shù)據(jù)包進(jìn)行直接轉(zhuǎn)發(fā).

2) 若ContentType=01，則依據(jù)PIT表的接口列表統(tǒng)計(jì)對應(yīng)名字的接口數(shù)量，即請求聚合度β，反映同一時(shí)間段內(nèi)用戶請求內(nèi)容的熱度；計(jì)算TotalHop(IntHop與DataHop之和)，其表示請求用戶與內(nèi)容發(fā)布者的距離；計(jì)算DataHop和TotalHop相關(guān)比值，其反映數(shù)據(jù)包距離請求側(cè)的遠(yuǎn)近；按照式(1)計(jì)算沿途節(jié)點(diǎn)的緩存概率為

1≤DataHop≤TotalHop.

(1)

3) 若ContentType為10，則依據(jù)PIT表的請求聚合度β和TotalHop，計(jì)算沿途節(jié)點(diǎn)的緩存概率為

(2)

4) 若ContentType為11，則依據(jù)PIT表的請求聚合度β和TotalHop，計(jì)算沿途節(jié)點(diǎn)的緩存概率為

1≤DataHop≤TotalHop.

(3)

算法1.路由節(jié)點(diǎn)緩存算法.

/*興趣包處理*/

/*Interest(n)是請求名字為n的興趣包*/

IFIsCache(n) THEN

GenerateData(n)；

CachePending置0；

根據(jù)PIT表轉(zhuǎn)發(fā)數(shù)據(jù)包；

ELSE

IFIsPIT(n) THEN

AddPITInterface(n)；

ELSE

AddPITEntry(n)；

IntHop++；

根據(jù)FIB表轉(zhuǎn)發(fā)興趣包；

END IF

END IF

EXIT

/*數(shù)據(jù)包處理*/

/*Data(n)是對應(yīng)名字為n的數(shù)據(jù)包*/

1) /*隔跳待定緩存策略*/

IFPendingCache=1 THEN

PendingCache置0；

Goto 2)；

ELSE

PendingCache置1；

Goto 3)；

END IF

EXIT

2) /*基于內(nèi)容類型的概率緩存策略*/

IFContentType=00 THEN

Goto 3)；

ELSE

統(tǒng)計(jì)PIT(n)請求聚合度β；

TotalHop=DataHop+IntHop；

獲取DataHop；

END IF

IFContentType=01 THEN

計(jì)算概率P1并賦值到變量P；

ELSE IFContentType=10 THEN

計(jì)算概率P2并賦值到變量P；

ELSE

計(jì)算概率P3并賦值到變量P；

END IF

END IF

IFP>概率門限值P0THEN

存儲數(shù)據(jù)包到CS；

END IF

3)DataHop++；

根據(jù)PIT表轉(zhuǎn)發(fā)數(shù)據(jù)包；

EXIT

2.4 包轉(zhuǎn)發(fā)和緩存過程

命名數(shù)據(jù)網(wǎng)絡(luò)中基于內(nèi)容類型的包轉(zhuǎn)發(fā)和緩存流程，如圖6、圖7所示：

Fig. 6 The process of interest forward圖6 興趣包轉(zhuǎn)發(fā)流程圖

Fig. 7 The process of data forward圖7 數(shù)據(jù)包轉(zhuǎn)發(fā)流程圖

步驟1. 用戶發(fā)送請求興趣包(interest)，路由節(jié)點(diǎn)接收到興趣包后查找CS表，若找到對應(yīng)名字的緩存內(nèi)容，則返回?cái)?shù)據(jù)包(data)；否則執(zhí)行步驟2.

步驟2. 查找PIT，若PIT中存在對應(yīng)內(nèi)容名字的記錄，按照路由節(jié)點(diǎn)原有的處理流程將進(jìn)入端口號，端口數(shù)和跳數(shù)記錄在對應(yīng)的PIT表項(xiàng)上；否則執(zhí)行步驟3.

步驟3. 按照路由節(jié)點(diǎn)原有的處理流程增加一條新PIT表項(xiàng)，即將興趣包的名字、進(jìn)入端口號、端口數(shù)和跳數(shù)記錄在PIT上.

步驟4. 對興趣包的跳數(shù)標(biāo)志位(IntHop)增加1，并將興趣包依照FIB中記錄向內(nèi)容發(fā)布者轉(zhuǎn)發(fā)，至此路由器完成了對這個(gè)興趣包的處理.在處理其他興趣包的同時(shí)，等待這個(gè)興趣包所請求的數(shù)據(jù)包返回.

當(dāng)數(shù)據(jù)包返回時(shí)，執(zhí)行4個(gè)步驟：

步驟1. 路由節(jié)點(diǎn)接收到內(nèi)容發(fā)布者發(fā)來的數(shù)據(jù)包，首先查看數(shù)據(jù)包PendingCache字段值決定當(dāng)前數(shù)據(jù)包是否需要緩存，若PendingCache字段值為0，則執(zhí)行步驟4；否則，PendingCache置1，并判斷數(shù)據(jù)包的內(nèi)容類型，然后執(zhí)行步驟2.

步驟2. 根據(jù)數(shù)據(jù)包的跳數(shù)DataHop和傳輸路徑總跳數(shù)TotalHop(即IntHop與DataHop之和)，計(jì)算緩存概率：若數(shù)據(jù)包內(nèi)容類型字段為00，則執(zhí)行步驟4；若數(shù)據(jù)包內(nèi)容類型字段為01，則采用基于網(wǎng)絡(luò)邊緣緩存策略計(jì)算緩存概率；若數(shù)據(jù)包內(nèi)容類型字段為10，則采用基于網(wǎng)絡(luò)次邊緣緩存策略計(jì)算緩存概率；若數(shù)據(jù)包內(nèi)容類型字段為11，則采用基于網(wǎng)絡(luò)核心緩存策略計(jì)算緩存概率.執(zhí)行步驟3.

步驟3. 根據(jù)概率計(jì)算結(jié)果決定緩存數(shù)據(jù)包，若計(jì)算得出的概率值P大于預(yù)先設(shè)置的門限概率值[13]，則緩存數(shù)據(jù)包；否則不進(jìn)行任何操作.執(zhí)行步驟4.

步驟4. 對數(shù)據(jù)包的DataHop增加1，按照路由器默認(rèn)流程將數(shù)據(jù)包依照PIT記錄的端口進(jìn)行轉(zhuǎn)發(fā).

3 實(shí)驗(yàn)評估

為了驗(yàn)證本文所提方案在緩存方面的性能優(yōu)勢，我們在基于NS-3[28]的網(wǎng)絡(luò)仿真平臺NDNSim[29-30]上對CTJP機(jī)制進(jìn)行模擬實(shí)現(xiàn)，選取了LCE，ProbCache，Betw，HPC典型的緩存策略作為參照對象，并從以下方面進(jìn)行性能比較，包括平均請求時(shí)延、緩存命中率以及額外開銷.

3.1 仿真環(huán)境設(shè)置

所有仿真作業(yè)在本地計(jì)算機(jī)上執(zhí)行，其運(yùn)行環(huán)境如下：CPU Intel Core i7，主頻3.4 GHz，內(nèi)存16 GB，硬盤1 TB，操作系統(tǒng)內(nèi)核Ubuntu 14.04(64 b)，NDNSim版本1.0.實(shí)驗(yàn)拓?fù)涫菂⒄誂S-3967真實(shí)且復(fù)雜的網(wǎng)絡(luò)拓?fù)洌溌穾?、鏈路時(shí)延、路由度量等參數(shù)都是基于Rocketfuel的追蹤結(jié)果[31-32].該拓?fù)溆?79個(gè)節(jié)點(diǎn)組成，其中255個(gè)路由器，20個(gè)用戶，4個(gè)源服務(wù)器，負(fù)責(zé)4種業(yè)務(wù)內(nèi)容的產(chǎn)生.

為了模擬不同的業(yè)務(wù)請求，分別設(shè)置動態(tài)類、實(shí)時(shí)類、大數(shù)據(jù)類、小數(shù)據(jù)類對應(yīng)的內(nèi)容前綴名為“blockchain.com”“skype.com”“youtube.com”“google.com”，后綴為隨機(jī)數(shù).假設(shè)用戶請求內(nèi)容流行度服從參數(shù)α=0.8[33]的Zipf分布，每個(gè)內(nèi)容大小為1 024 B，內(nèi)容個(gè)數(shù)為200，內(nèi)容序號以1～200排序.每個(gè)路由器具有相同的緩存空間，可容納內(nèi)容數(shù)量500，緩存初始時(shí)不存儲任何內(nèi)容，采用NDN默認(rèn)的緩存替換算法，即最近最少使用策略LRU.表1列出了各項(xiàng)模擬參數(shù)，仿真運(yùn)行時(shí)長600 s， Interest包請求產(chǎn)生的平均速率服從參數(shù)10個(gè)/s的泊松分布.為了方便比較，ProbCache機(jī)制中每個(gè)路由器以0.2的概率緩存內(nèi)容.

Table 1 Simulation Parameters Setting

3.2 性能評價(jià)指標(biāo)

針對路由器、用戶、服務(wù)器，實(shí)驗(yàn)引入3個(gè)指標(biāo)評估緩存的性能，即平均請求時(shí)延、緩存命中率和額外開銷.平均請求時(shí)延是從用戶發(fā)出請求興趣包到獲得數(shù)據(jù)包的平均等待時(shí)間，單位為ms，該值用來衡量用戶體驗(yàn)好壞.緩存命中率是指在路由器命中的興趣包數(shù)目與興趣包總數(shù)的比值，能反映網(wǎng)絡(luò)化緩存(路由器)為源服務(wù)器分擔(dān)的壓力.額外開銷在整個(gè)通信過程中可細(xì)分為控制開銷和傳輸開銷2部分，用于比較各種機(jī)制帶來的開銷情況.

3.3 實(shí)驗(yàn)結(jié)果分析

3.3.1 平均請求時(shí)延

我們通過平均請求時(shí)延分析CTJP機(jī)制的傳輸效率.圖8顯示了CTJP機(jī)制與對比方案的用戶請求時(shí)延，采樣時(shí)間周期2 s.對于動態(tài)類型內(nèi)容，如圖8(a)所示，CTJP機(jī)制略小于LCE，請求動態(tài)類型內(nèi)容的興趣包需要轉(zhuǎn)發(fā)至內(nèi)容發(fā)布者才能得到響應(yīng)，而CTJP機(jī)制對動態(tài)類型內(nèi)容不進(jìn)行存儲操作，同時(shí)節(jié)省緩存空間.對于實(shí)時(shí)類型內(nèi)容，如圖8(b)所示，CTJP機(jī)制明顯小于HPC，由于CTJP機(jī)制采用網(wǎng)絡(luò)邊緣概率緩存，使得實(shí)時(shí)類型內(nèi)容大概率分布在網(wǎng)絡(luò)邊緣側(cè)，同時(shí)避免相同內(nèi)容的重復(fù)冗余存儲，增大就近響應(yīng)率和緩存利用率.對于大數(shù)據(jù)內(nèi)容，如圖8(c)所示，CTJP機(jī)制采用網(wǎng)絡(luò)次邊緣概率緩存，使得大數(shù)據(jù)類型內(nèi)容大概率分布在網(wǎng)絡(luò)次邊緣，并減少相同內(nèi)容的重復(fù)冗余存儲.對于小數(shù)據(jù)內(nèi)容，如圖8(d)所示，CTJP機(jī)制與LCE持平，但波動起伏較小，由于CTJP機(jī)制采用網(wǎng)絡(luò)核心概率緩存，使得小數(shù)據(jù)類型內(nèi)容大概率分布在網(wǎng)絡(luò)核心，同時(shí)避免占用網(wǎng)絡(luò)邊緣稀缺資源而引發(fā)高頻的替換.

3.3.2 緩存命中率

圖9顯示CTJP機(jī)制中某條傳輸路徑節(jié)點(diǎn)的緩存命中率情況，其統(tǒng)計(jì)時(shí)間為500 s.在實(shí)時(shí)類、大數(shù)據(jù)類、小數(shù)據(jù)類的緩存決策中，分別采用網(wǎng)絡(luò)邊緣遞增概率緩存、網(wǎng)絡(luò)次邊緣遞增遞減概率緩存、網(wǎng)絡(luò)核心遞減概率緩存.針對不同內(nèi)容特征，用戶與內(nèi)容存儲位置的距離有所不同，為提升整個(gè)緩存系統(tǒng)的整體利用率.圖10給出了各個(gè)方案的平均緩存命中率的對比，CTJP機(jī)制的命中率為31.1%，明顯高于其他方案.

Fig. 9 The cache hit rate of on-path node圖9 沿途路徑節(jié)點(diǎn)的緩存命中率

Fig. 10 The average cache hit rate圖10 平均緩存命中率

3.3.3 額外開銷

CTJP機(jī)制為了提供內(nèi)容差異化的緩存服務(wù)，在NDN原始的興趣包和數(shù)據(jù)包中增大了額外的控制字段IntHop(8 b)，PendingCache(1 b)，ContentType(2 b)，DataHop(8 b)，以匹配不同的內(nèi)容緩存服務(wù).控制開銷定義為控制字段與傳輸跳數(shù)的乘積.假設(shè)一次傳輸跳數(shù)為n，則帶來的額外開銷是O(3n)字節(jié)的存儲開銷.內(nèi)容傳輸開銷為興趣包請求過程中，請求包和數(shù)據(jù)包分別與其傳輸距離的乘積之和.假設(shè)一次完整的的請求響應(yīng)，經(jīng)過傳輸跳數(shù)n到達(dá)內(nèi)容發(fā)布者，所需的傳輸開銷為O(n+2n).因此，在最壞情況下，CTJP機(jī)制所需的控制開銷，傳輸開銷與傳輸跳數(shù)相關(guān)，而且成線性相關(guān)，開銷較小.

4 相關(guān)討論

CTJP機(jī)制不僅適用于NDN網(wǎng)絡(luò)環(huán)境，還適用于所有基于網(wǎng)絡(luò)化緩存的未來網(wǎng)絡(luò)架構(gòu)，但是需要服務(wù)提供商(內(nèi)容發(fā)布者)支持對內(nèi)容業(yè)務(wù)進(jìn)行分類.

CTJP機(jī)制根據(jù)業(yè)務(wù)特征劃分內(nèi)容種類，并結(jié)合非連續(xù)緩存策略，對待不同內(nèi)容實(shí)行差異化緩存，從而達(dá)到降低數(shù)據(jù)冗余，提高緩存命中率，減少用戶請求時(shí)延.其優(yōu)勢具體體現(xiàn)在3個(gè)方面：

1) 在動態(tài)類方面，采用無緩存策略，避免動態(tài)類型內(nèi)容無效占用緩存空間，降低數(shù)據(jù)冗余.

2) 在實(shí)時(shí)類方面，結(jié)合路由跳數(shù)和請求熱度設(shè)計(jì)網(wǎng)絡(luò)邊緣概率緩存，使得用戶就近訪問實(shí)時(shí)內(nèi)容，減少用戶請求時(shí)延.與HPC機(jī)制相比，CTJP機(jī)制還引入請求熱度因素，對于熱度較高的請求，更有可能緩存在網(wǎng)絡(luò)邊緣，減少用戶請求時(shí)延.

3) 在大數(shù)據(jù)類和小數(shù)據(jù)類方面，考慮到該內(nèi)容對時(shí)延要求不高，設(shè)計(jì)網(wǎng)絡(luò)次邊緣和網(wǎng)絡(luò)核心概率緩存策略，避免占用網(wǎng)絡(luò)邊緣稀缺資源而引發(fā)高頻的替換，盡管實(shí)驗(yàn)結(jié)果顯示CTJP機(jī)制在這些內(nèi)容請求響應(yīng)時(shí)延表現(xiàn)不是最好，但不影響總體命中率.

5 總結(jié)與展望

本文提出基于內(nèi)容類型的隔跳概率緩存方法，采用隔跳待定緩存策略，減少數(shù)據(jù)緩存冗余；定義內(nèi)容類型，并針對不同內(nèi)容提供差異化緩存服務(wù)，進(jìn)一步降低冗余，同時(shí)提高用戶獲取內(nèi)容的效率，實(shí)驗(yàn)結(jié)果表明該方案的有效性.后續(xù)研究主要完善CTJP機(jī)制設(shè)計(jì)思想，在實(shí)際平臺上實(shí)現(xiàn)方案.