命名數(shù)據(jù)網(wǎng)絡(luò)中基于內(nèi)容類型的隔跳概率緩存機制

郭 江 王 淼 張玉軍

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

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

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

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

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

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

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

1 相關(guān)工作

1.1 NDN背景

NDN網(wǎng)絡(luò)包括用戶(user)、內(nèi)容發(fā)布者(content provider)和路由器(router)3類實體，其數(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ò)中單個節(jié)點通信流程如圖1所示.每個實體包含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)容請求從本地響應數(shù)據(jù)包，有利于減少對于發(fā)布者的訪問次數(shù)，提升內(nèi)容分發(fā)的傳輸效率；PIT記錄待轉(zhuǎn)發(fā)興趣包的內(nèi)容名稱以及接入接口，并且匯聚相同的興趣包在一個表項中；FIB依靠路由協(xié)議生成，記錄興趣包轉(zhuǎn)發(fā)下一跳接口.

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

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

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

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

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

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

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

1.3 緩存策略

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

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

2 CTJP機制

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

Fig. 2 Workflow of CTJP圖2 CTJP機制整體工作流程

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

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

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

2.2 包格式擴展

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

Fig. 4 Extended packet format圖4 擴展后的包格式

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

2.3 緩存算法

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

2.3.1 隔跳待定緩存策略

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

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

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

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

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

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

1≤DataHop≤TotalHop.

(1)

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

(2)

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

1≤DataHop≤TotalHop.

(3)

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

/*興趣包處理*/

/*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)是對應名字為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)計PIT(n)請求聚合度β；

TotalHop=DataHop+IntHop；

獲取DataHop；

END IF

IFContentType=01 THEN

計算概率P1并賦值到變量P；

ELSE IFContentType=10 THEN

計算概率P2并賦值到變量P；

ELSE

計算概率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é)點接收到興趣包后查找CS表，若找到對應名字的緩存內(nèi)容，則返回數(shù)據(jù)包(data)；否則執(zhí)行步驟2.

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

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

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

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

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

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

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

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

3 實驗評估

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

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

所有仿真作業(yè)在本地計算機上執(zhí)行，其運行環(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.實驗拓撲是參照AS-3967真實且復雜的網(wǎng)絡(luò)拓撲，鏈路帶寬、鏈路時延、路由度量等參數(shù)都是基于Rocketfuel的追蹤結(jié)果[31-32].該拓撲由279個節(jié)點組成，其中255個路由器，20個用戶，4個源服務器，負責4種業(yè)務內(nèi)容的產(chǎn)生.

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

Table 1 Simulation Parameters Setting

3.2 性能評價指標

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

3.3 實驗結(jié)果分析

3.3.1 平均請求時延

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

3.3.2 緩存命中率

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

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

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

3.3.3 額外開銷

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

4 相關(guān)討論

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

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

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

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

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

5 總結(jié)與展望

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