命名數(shù)據(jù)網(wǎng)絡中的二分緩存方案

張俊敏，金繼歡，侯睿

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

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

NDN 中存在兩種類型的包，興趣包和數(shù)據(jù)包，興趣包中包括內(nèi)容請求者所請求的數(shù)據(jù)內(nèi)容名稱，內(nèi)容發(fā)布者將相應數(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ā)送的請求在路由器中被響應的次數(shù)較少，大多數(shù)請求仍需從較遠的內(nèi)容生產(chǎn)者中獲取響應，從而降低緩存命中率，增大數(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 相關研究

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

文獻［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)容信息熵以及復雜的緩存價值計算會增加額外計算開銷以及存儲開銷.并且通過緩存更新方法提前刪除的只有少量數(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)過的路徑稱為當前路徑.

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

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

BC 方案在原有NDN 包格式基礎上進行了拓展，如圖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）當內(nèi)容生產(chǎn)者接收到興趣包，讀取興趣包的跳數(shù)字段值IH，為將數(shù)據(jù)包緩存在中心路由器中，按照如下公式設置數(shù)據(jù)包緩存標志字段內(nèi)容，其中CT表示緩存標志字段值，TRC表示當前路徑中路由器的數(shù)量，根據(jù)TRC的奇偶性設置CT：

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

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

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

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

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

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

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

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

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

Algorithm 1 Process Incoming Interest/*興趣包處理算法*//*interest是到達節(jié)點的興趣包*//*rdata是命中后響應的數(shù)據(jù)包*/Input： 到達節(jié)點的興趣包interest Output： 響應的數(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ù)據(jù)包緩存標志值ELSE //路徑中路由器數(shù)量為奇數(shù)rdata.setCT （ih/2+2） //設置數(shù)據(jù)包緩存標志值END IF END IF IF Node=Router THEN //節(jié)點為路由器rdata.setCT（ih+1） //設置數(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設置為0將lruData1發(fā)往上游路由器發(fā)送完畢在CS中刪除lruData1 cacheData（data） //緩存數(shù)據(jù)包data.setCT （1） //設置數(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設置為0將lruData2發(fā)往上游路由器發(fā)送完畢在CS中刪除lruData2 cacheData（data） //緩存數(shù)據(jù)包END IF END IF EXIT

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

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

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

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

緩存命中率為數(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)容.

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

圖4～6 為α=0.8 的情況下四種方案的緩存命中率，平均請求時延以及服務器負載的結(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 方案的服務器負載高于CEE，Prob，CPCA三種方案.但隨著運行時間的增加BC 方案中服務器負載逐漸低于其余三種方案并趨于平緩，這說明初始階段由于路由器的緩存空間未被存儲滿，BC方案中大部分請求仍需發(fā)送至內(nèi)容的生產(chǎn)者獲得響應.而隨著運行時間的增加，BC方案中路由器緩存更多熱度高的數(shù)據(jù)內(nèi)容，即使將低熱度數(shù)據(jù)內(nèi)容向上游轉(zhuǎn)發(fā)會帶來服務器負載的增加，但總體上服務器的負載量仍低于其余三種方案.

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

為了驗證不同內(nèi)容流行度集中程度對本文方案的影響，將α設置為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)容.同樣的從平均請求時延以及服務器負載兩個指標的結(jié)果來看，BC方案除了能將熱度最高的數(shù)據(jù)內(nèi)容緩存在鄰接路由器中，還能將熱度較高的數(shù)據(jù)內(nèi)容緩存在靠近內(nèi)容請求者的路由器中.減少了鄰接路由器頻繁進行緩存替換的操作同時通過設置中心路由器分擔了向上轉(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)計的方法將相應熱度的數(shù)據(jù)內(nèi)容更快的緩存在與內(nèi)容請求者相應距離的路由器中.