張俊敏，金繼歡，侯睿

（中南民族大學(xué) 計算機科學(xué)學(xué)院，武漢 430074）

近年來世界各國都在關(guān)注設(shè)計全新的未來互聯(lián)網(wǎng)體系架構(gòu)，其中主流研究方向之一就是信息中心網(wǎng)絡(luò)，而命名數(shù)據(jù)網(wǎng)絡(luò)（Named Data Networking，NDN）［1］作為信息中心網(wǎng)絡(luò)（Information-Centric Network，ICN）［2-3］的經(jīng)典項目具有重要研究意義.

NDN 中存在兩種類型的包，興趣包和數(shù)據(jù)包，興趣包中包括內(nèi)容請求者所請求的數(shù)據(jù)內(nèi)容名稱，內(nèi)容發(fā)布者將相應(yīng)數(shù)據(jù)內(nèi)容封裝成數(shù)據(jù)包并沿興趣包傳輸?shù)穆窂椒聪蚍祷刂羶?nèi)容請求者.NDN 路由器包含3 種數(shù)據(jù)結(jié)構(gòu)，分別是內(nèi)容存儲 （Content Store，CS），待定興趣表（Pending Interest Table，PIT）以及轉(zhuǎn)發(fā)信息庫（Forwarding Information Base，F(xiàn)IB）.其中CS 提供有限的數(shù)據(jù)存儲功能，PIT 記錄Interest包的請求接口信息，F(xiàn)IB 提供數(shù)據(jù)轉(zhuǎn)發(fā)接口的信息.NDN路由器處理傳輸包的過程如圖1所示.

圖1 路由器處理傳輸包的過程Fig.1 The process of router processing transmission packet

NDN 默認的緩存方案為沿途緩存方案Cache Everything Everywhere，CEE）［4］.該方案會將數(shù)據(jù)內(nèi)容緩存在所有經(jīng)過的路由器中從而產(chǎn)生大量冗余副本，降低緩存空間利用率.且由于路由器緩存空間有限，緩存的數(shù)據(jù)內(nèi)容多樣性較差，內(nèi)容請求者發(fā)送的請求在路由器中被響應(yīng)的次數(shù)較少，大多數(shù)請求仍需從較遠的內(nèi)容生產(chǎn)者中獲取響應(yīng)，從而降低緩存命中率，增大數(shù)據(jù)內(nèi)容的請求時延.

為了解決上述問題，本文提出了一種二分緩存方案（Binary Caching，BC）.該方案考慮了區(qū)分數(shù)據(jù)內(nèi)容的熱度以及將高熱度數(shù)據(jù)內(nèi)容緩存在靠近內(nèi)容請求者周圍對緩存性能的提升.將首次被請求的數(shù)據(jù)內(nèi)容緩存在中心路由器中，若該數(shù)據(jù)內(nèi)容再次被請求則緩存在內(nèi)容請求者的鄰接路由器中，若該數(shù)據(jù)內(nèi)容許久未被請求則會被逐漸推向內(nèi)容生產(chǎn)者.從而使得內(nèi)容請求者周圍路由器緩存更多熱度高的數(shù)據(jù)內(nèi)容，有效利用了緩存空間，增加了緩存命中率以及降低了數(shù)據(jù)內(nèi)容的請求時延.

1 相關(guān)研究

數(shù)據(jù)內(nèi)容緩存方案一直是NDN 網(wǎng)絡(luò)研究的重點之一.近年來，許多研究人員都提出相關(guān)緩存方案來有效利用緩存空間，提升緩存性能.

文獻［5］提出基于固定概率將數(shù)據(jù)包進行緩存的方案Prob，該方案實現(xiàn)方法簡單，并且能減少路由器中的冗余數(shù)據(jù)內(nèi)容，提升緩存空間利用率.但是基于概率緩存數(shù)據(jù)內(nèi)容的方法存在較大的不確定性，無法有效區(qū)分不同數(shù)據(jù)內(nèi)容之間的熱度差異.文獻［6］提出了基于節(jié)點介數(shù)與邊緣流行度的方案（Betweenness and Edge Popularity，BEP），該方案通過構(gòu)建邊緣節(jié)點流行度表，將最流行的數(shù)據(jù)內(nèi)容緩存在介數(shù)值最高的核心路由器上，非流行數(shù)據(jù)內(nèi)容緩存在介數(shù)值不高的次要路由器上，增加了緩存空間的利用率.雖然該方案有效區(qū)分了不同數(shù)據(jù)內(nèi)容的流行度差異性，但是介數(shù)值最高的路由器的位置并非最接近內(nèi)容請求者，請求仍需經(jīng)過多個路由器轉(zhuǎn)發(fā)才能命中數(shù)據(jù)內(nèi)容，增大了數(shù)據(jù)內(nèi)容的請求時延.文獻［7］提出基于內(nèi)容流行度的以指數(shù)方式增加沿途經(jīng)過緩存概率的方案WAVE，該方案能將流行度高的內(nèi)容以指數(shù)級別的速度緩存到內(nèi)容請求者四周，減少數(shù)據(jù)內(nèi)容的請求時延，但WAVE 需要在上游路由器中創(chuàng)建數(shù)據(jù)塊標記窗口（Chunk Marking Window，CMW）來記錄數(shù)據(jù)內(nèi)容被請求的次數(shù)，并且CMW 會隨著數(shù)據(jù)內(nèi)容被請求頻率的增加而增大［8］，從而增加額外開銷.文獻［9］提出了基于數(shù)據(jù)請求節(jié)點的就近緩存方案（Consumer-based Proximity Caching Algorithm，CPCA），該方案根據(jù)內(nèi)容熱度變化趨勢將高熱度數(shù)據(jù)內(nèi)容推進在內(nèi)容請求者周圍路由器中，并且延長其在路由器中的緩存時間，提高數(shù)據(jù)內(nèi)容緩存命中率以及減少數(shù)據(jù)內(nèi)容的請求時延.但CPCA 并未將數(shù)據(jù)內(nèi)容進行過濾，使得緩存在靠近內(nèi)容請求者的路由器中的高熱度數(shù)據(jù)內(nèi)容容易被低熱度數(shù)據(jù)內(nèi)容替換.文獻［10］提出了一種基于緩存價值的緩存方案（Leave Cache Value，LCV），該方案通過統(tǒng)計內(nèi)容流行度，興趣源距離，內(nèi)容大小及多樣性3 個指標來建立緩存決策模型，通過層次判別矩陣來確定指標的權(quán)值，并且為了減少CS 已滿時的計算壓力通過緩存更新方法提前刪除CS中緩存價值較低的數(shù)據(jù)內(nèi)容.但建立內(nèi)容流行度表，內(nèi)容大小及多樣性統(tǒng)計表，內(nèi)容信息熵以及復(fù)雜的緩存價值計算會增加額外計算開銷以及存儲開銷.并且通過緩存更新方法提前刪除的只有少量數(shù)據(jù)內(nèi)容，無法有效減小計算壓力.

2 BC方案原理

BC 方案規(guī)定從內(nèi)容生產(chǎn)者到內(nèi)容請求者的傳輸方向為下游方向，相反則為上游方向.將興趣包從內(nèi)容請求者轉(zhuǎn)發(fā)到內(nèi)容生產(chǎn)者時經(jīng)過的路徑稱為當(dāng)前路徑.

若當(dāng)前路徑中路由器數(shù)量為奇數(shù)則將最中心的路由器定義為中心路由器，否則為偶數(shù)時將最中間且靠近內(nèi)容生產(chǎn)者的路由器定義為中心路由器，具體劃分示例如圖2所示.

圖2 中心路由器定義方案Fig.2 Central router definition scheme

BC 方案在原有NDN 包格式基礎(chǔ)上進行了拓展，如圖3 所示，其中數(shù)據(jù)包新增緩存標志字段CachingTag，該字段內(nèi)容用來指示路由器是否進行緩存；興趣包新增興趣包跳數(shù)字段InterestHop，該字段內(nèi)容用來記錄興趣包經(jīng)過跳數(shù).

圖3 拓展包格式Fig.3 Expansion package format

BC 方案主要思想為將熱度高的數(shù)據(jù)內(nèi)容緩存在內(nèi)容請求者周圍，將熱度低的數(shù)據(jù)內(nèi)容緩存在內(nèi)容生產(chǎn)者周圍.并且隨著內(nèi)容熱度的動態(tài)變化將熱度降低的數(shù)據(jù)內(nèi)容逐漸推向內(nèi)容生產(chǎn)者.

其具體實施過程如下所示：

1）當(dāng)內(nèi)容生產(chǎn)者接收到興趣包，讀取興趣包的跳數(shù)字段值IH，為將數(shù)據(jù)包緩存在中心路由器中，按照如下公式設(shè)置數(shù)據(jù)包緩存標志字段內(nèi)容，其中CT表示緩存標志字段值，TRC表示當(dāng)前路徑中路由器的數(shù)量，根據(jù)TRC的奇偶性設(shè)置CT：

設(shè)置完畢將其發(fā)往下游路由器.

2）當(dāng)路由器接收到數(shù)據(jù)包，讀取數(shù)據(jù)包的緩存標志字段值CT，并根據(jù)緩存標志值進行對應(yīng)操作：

①CT大于2，表明該數(shù)據(jù)包并未到達指定緩存路由器，路由器將數(shù)據(jù)包CT減去1 后繼續(xù)向下轉(zhuǎn)發(fā).

②CT等于2，表明該數(shù)據(jù)包到達指定緩存路由器，判斷當(dāng)前路由器CS剩余緩存容量能否滿足該數(shù)據(jù)包進行緩存，如能滿足則將該數(shù)據(jù)包緩存，緩存完畢將數(shù)據(jù)包CT設(shè)為1，設(shè)置完畢繼續(xù)向下轉(zhuǎn)發(fā).若無法滿足則通過LRU（Least Recently Used）［11］規(guī)則從CS 中替換出最近最久未使用的數(shù)據(jù)包lruData1，將lruData1的CT設(shè)置為0后發(fā)往上游路由器，而緩存的數(shù)據(jù)包CT設(shè)置為1 后繼續(xù)向下游路由器轉(zhuǎn)發(fā).

③CT等于1，表明該數(shù)據(jù)包已在上游路由器中進行緩存，直接將該數(shù)據(jù)包向下轉(zhuǎn)發(fā).

④CT等于0，表明該數(shù)據(jù)包從下游路由器轉(zhuǎn)發(fā)而來，判斷當(dāng)前路由器CS剩余緩存容量能否滿足該數(shù)據(jù)包進行緩存，如能滿足則將該數(shù)據(jù)包緩存.否則通過LRU 規(guī)則從CS 中替換出最近最久未使用的數(shù)據(jù)包lruData2，將lruData2的CT設(shè)置為0后發(fā)往繼續(xù)向上游路由器轉(zhuǎn)發(fā).

3）當(dāng)數(shù)據(jù)包在路由器中被命中，為將數(shù)據(jù)包緩存在內(nèi)容請求者的鄰接路由器中，讀取對應(yīng)興趣包跳數(shù)字段值IH，并按照如下公式設(shè)置數(shù)據(jù)包緩存標志字段內(nèi)容，其中CT表示緩存標志字段值：

設(shè)置完畢將其發(fā)往下游路由器.

給出內(nèi)容生產(chǎn)者或者路由器使用BC 方案處理興趣包以及數(shù)據(jù)包的偽代碼.

Algorithm 1 Process Incoming Interest/*興趣包處理算法*//*interest是到達節(jié)點的興趣包*//*rdata是命中后響應(yīng)的數(shù)據(jù)包*/Input： 到達節(jié)點的興趣包interest Output： 響應(yīng)的數(shù)據(jù)包rdata ih ← interest.getIH（） //獲取興趣包跳數(shù)IF Node=Producer THEN //節(jié)點為內(nèi)容生產(chǎn)者IF ih%2=0 THEN //路徑中路由器數(shù)量為偶數(shù)rdata.setCT （ih/2+1） //設(shè)置數(shù)據(jù)包緩存標志值ELSE //路徑中路由器數(shù)量為奇數(shù)rdata.setCT （ih/2+2） //設(shè)置數(shù)據(jù)包緩存標志值END IF END IF IF Node=Router THEN //節(jié)點為路由器rdata.setCT（ih+1） //設(shè)置數(shù)據(jù)包緩存標志值END IF EXIT

Algorithm 2 Process Incoming Data/*數(shù)據(jù)包處理算法*//*data是到達節(jié)點的數(shù)據(jù)包*/Input： 到達節(jié)點的數(shù)據(jù)包data Output： 轉(zhuǎn)發(fā)或緩存數(shù)據(jù)包data ct ← data.getCT（） //獲取數(shù)據(jù)包緩存標志值IF ct＞2 THEN data.setCT （ct-1） //數(shù)據(jù)包緩存標志值減去1 sendData（data） //向下游發(fā)送數(shù)據(jù)包END IF IF ct=2 THEN IF CS能滿足緩存 THEN cacheData（data） //緩存數(shù)據(jù)包ELSE通過LRU規(guī)則取出lruData1將lruData1的CT設(shè)置為0將lruData1發(fā)往上游路由器發(fā)送完畢在CS中刪除lruData1 cacheData（data） //緩存數(shù)據(jù)包data.setCT （1） //設(shè)置數(shù)據(jù)包緩存標志值sendData（data） //向下游發(fā)送數(shù)據(jù)包END IF END IF IF ct=1 THEN sendData（data） //向下游發(fā)送數(shù)據(jù)包END IF IF ct=0 THEN IF CS能滿足緩存THEN cacheData（data） //緩存數(shù)據(jù)包ELSE通過LRU規(guī)則取出lruData2將lruData2的CT設(shè)置為0將lruData2發(fā)往上游路由器發(fā)送完畢在CS中刪除lruData2 cacheData（data） //緩存數(shù)據(jù)包END IF END IF EXIT

3 實驗結(jié)果與分析

本次實驗使用的是ndnSIM［12］仿真平臺，選取CEE，Prob，CPCA 緩存方案同BC 進行比較，其中Prob緩存概率設(shè)置為0.5.實驗拓撲參照AS-6461，該拓撲由176 個節(jié)點組成.在網(wǎng)絡(luò)拓撲中心設(shè)置1 個內(nèi)容生產(chǎn)者，在邊緣隨機設(shè)置20 個內(nèi)容請求者.每個內(nèi)容請求者發(fā)送興趣包的過程都符合泊松分布，設(shè)置數(shù)據(jù)內(nèi)容類型總量為5000，生成的請求數(shù)據(jù)內(nèi)容符合Zipf-Mandelbrot分布［13］，其中Zipf參數(shù)α決定數(shù)據(jù)內(nèi)容請求集中程度，α越大表示內(nèi)容請求越集中，仿真時間設(shè)置為100 s，緩存替換規(guī)則使用LRU.為接近現(xiàn)實網(wǎng)絡(luò)中數(shù)據(jù)緩存節(jié)點容量遠小于數(shù)據(jù)內(nèi)容類型總量的情況，將每個路由器節(jié)點緩存容量設(shè)置為50 KB，使得節(jié)點緩存容量與數(shù)據(jù)內(nèi)容類型總量比例為0.01.具體各項模擬參數(shù)如表1所示

表1 實驗參數(shù)Tab.1 Experimental parameters

為了驗證本方案的優(yōu)劣，本文選取緩存命中率［14］，平均請求時延［15］以及服務(wù)器負載三個指標來進行評判.

緩存命中率為數(shù)據(jù)包在路由器中被命中的數(shù)量與所有內(nèi)容請求者發(fā)送的數(shù)據(jù)內(nèi)容請求總量的比值，緩存命中率越高說明路由器緩存的數(shù)據(jù)內(nèi)容種類更多，緩存空間利用率越高.

平均請求時延為內(nèi)容請求者在發(fā)送興趣包后等待數(shù)據(jù)包返回的平均時間，該指標反映了數(shù)據(jù)內(nèi)容緩存位置的好壞，平均請求時延越小，說明離內(nèi)容請求者越近的路由器能緩存越多熱度高的數(shù)據(jù)內(nèi)容.

服務(wù)器負載為內(nèi)容生產(chǎn)者在單位時間內(nèi)接收到請求并響應(yīng)的數(shù)據(jù)包的數(shù)量，服務(wù)器負載越大表明內(nèi)容生產(chǎn)者接收到的請求越多.同時服務(wù)器負載過高會導(dǎo)致處理請求能力過差，增加內(nèi)容請求時延.

圖4～6 為α=0.8 的情況下四種方案的緩存命中率，平均請求時延以及服務(wù)器負載的結(jié)果對比圖.

圖4 4種方案緩存命中率對比結(jié)果Fig.4 Comparison results of cache hit rate for four schemes

從圖4 中可以看出到，BC 方案的緩存命中率均高于其余三種方案，這是因為NDN 默認的CEE方案會使得路徑中所有路由器緩存相同的數(shù)據(jù)內(nèi)容，降低緩存空間的利用率.而Prob 方案通過概率進行數(shù)據(jù)內(nèi)容的緩存，不同路由器仍有概率緩存相同數(shù)據(jù)內(nèi)容.CPCA 方案雖然減少了數(shù)據(jù)內(nèi)容的冗余，但未對數(shù)據(jù)內(nèi)容的熱度進行過濾，使得路由器緩存更多熱度低的數(shù)據(jù)內(nèi)容.而BC 方案則在減少數(shù)據(jù)內(nèi)容冗余的同時過濾掉低熱度數(shù)據(jù)內(nèi)容使得路徑中路由器能緩存更多熱度高的數(shù)據(jù)內(nèi)容，更大的提升緩存命中率.

從圖5 中我們可以看出，CPCA 和BC 兩種方案的平均請求時延逐漸降低并且趨于平緩，同時BC相比CPCA 能取得更好的平均請求時延，這是因為隨著路由器中數(shù)據(jù)內(nèi)容逐漸飽和，CPCA 會使得靠近內(nèi)容請求者的路由器中一些緩存的高熱度的數(shù)據(jù)內(nèi)容被低熱度數(shù)據(jù)內(nèi)容替換掉，而被替換的高熱度數(shù)據(jù)內(nèi)容仍需從較遠的內(nèi)容生產(chǎn)者重新請求，從而增加請求時延.而BC 方案則不允許低熱度數(shù)據(jù)內(nèi)容緩存在內(nèi)容請求者周圍，因此相較于CPCA 方案能獲得更低的平均請求時延.

圖5 4種方案平均請求時延對比結(jié)果Fig.5 Comparison results of average request delay for four schemes

從圖6中我們可以看出，在運行初始階段BC 方案的服務(wù)器負載高于CEE，Prob，CPCA三種方案.但隨著運行時間的增加BC 方案中服務(wù)器負載逐漸低于其余三種方案并趨于平緩，這說明初始階段由于路由器的緩存空間未被存儲滿，BC方案中大部分請求仍需發(fā)送至內(nèi)容的生產(chǎn)者獲得響應(yīng).而隨著運行時間的增加，BC方案中路由器緩存更多熱度高的數(shù)據(jù)內(nèi)容，即使將低熱度數(shù)據(jù)內(nèi)容向上游轉(zhuǎn)發(fā)會帶來服務(wù)器負載的增加，但總體上服務(wù)器的負載量仍低于其余三種方案.

圖6 4種方案服務(wù)器負載對比結(jié)果Fig.6 Comparison results of server load for four schemes

為了驗證不同內(nèi)容流行度集中程度對本文方案的影響，將α設(shè)置為0.5—1.4 進行實驗，得到的三個指標結(jié)果如圖7所示.

圖7 數(shù)據(jù)內(nèi)容請求集中程度對評價指標的影響Fig.7 Impact of data content request concentration on evaluation indicators

從圖7中可以看出隨著數(shù)據(jù)內(nèi)容的請求集中程度越高，BC方案的緩存命中率仍然穩(wěn)定高于其余三種方案，這是因為BC 方案將數(shù)據(jù)內(nèi)容首次緩存在中心路由器中，并且隨著數(shù)據(jù)內(nèi)容的積累，中心路由器將熱度高的數(shù)據(jù)內(nèi)容繼續(xù)推向內(nèi)容請求者，而將熱度低的數(shù)據(jù)內(nèi)容逐漸推向內(nèi)容生產(chǎn)者，更快的過濾掉請求次數(shù)少的數(shù)據(jù)內(nèi)容，使路由器能緩存更多種類數(shù)據(jù)內(nèi)容的同時減少冗余的數(shù)據(jù)內(nèi)容.同樣的從平均請求時延以及服務(wù)器負載兩個指標的結(jié)果來看，BC方案除了能將熱度最高的數(shù)據(jù)內(nèi)容緩存在鄰接路由器中，還能將熱度較高的數(shù)據(jù)內(nèi)容緩存在靠近內(nèi)容請求者的路由器中.減少了鄰接路由器頻繁進行緩存替換的操作同時通過設(shè)置中心路由器分擔(dān)了向上轉(zhuǎn)發(fā)數(shù)據(jù)包造成的負載.

4 結(jié)束語

本文針對現(xiàn)有緩存算法的局限，提出一種二分緩存方案，過濾低熱度數(shù)據(jù)內(nèi)容，增加緩存的數(shù)據(jù)內(nèi)容的多樣性，減少數(shù)據(jù)冗余，降低平均請求時延.但本文提出的方案在數(shù)據(jù)內(nèi)容熱度過濾方面仍有提升空間，下一步將結(jié)合路由器緩存容量與周期性數(shù)據(jù)內(nèi)容熱度統(tǒng)計的方法將相應(yīng)熱度的數(shù)據(jù)內(nèi)容更快的緩存在與內(nèi)容請求者相應(yīng)距離的路由器中.