命名數據網絡中的二分緩存方案

張俊敏，金繼歡，侯睿

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

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

NDN 中存在兩種類型的包，興趣包和數據包，興趣包中包括內容請求者所請求的數據內容名稱，內容發布者將相應數據內容封裝成數據包并沿興趣包傳輸的路徑反向返回至內容請求者.NDN 路由器包含3 種數據結構，分別是內容存儲 （Content Store，CS），待定興趣表（Pending Interest Table，PIT）以及轉發信息庫（Forwarding Information Base，FIB）.其中CS 提供有限的數據存儲功能，PIT 記錄Interest包的請求接口信息，FIB 提供數據轉發接口的信息.NDN路由器處理傳輸包的過程如圖1所示.

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

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

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

1 相關研究

數據內容緩存方案一直是NDN 網絡研究的重點之一.近年來，許多研究人員都提出相關緩存方案來有效利用緩存空間，提升緩存性能.

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

2 BC方案原理

BC 方案規定從內容生產者到內容請求者的傳輸方向為下游方向，相反則為上游方向.將興趣包從內容請求者轉發到內容生產者時經過的路徑稱為當前路徑.

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

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

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

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

BC 方案主要思想為將熱度高的數據內容緩存在內容請求者周圍，將熱度低的數據內容緩存在內容生產者周圍.并且隨著內容熱度的動態變化將熱度降低的數據內容逐漸推向內容生產者.

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

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

設置完畢將其發往下游路由器.

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

①CT大于2，表明該數據包并未到達指定緩存路由器，路由器將數據包CT減去1 后繼續向下轉發.

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

③CT等于1，表明該數據包已在上游路由器中進行緩存，直接將該數據包向下轉發.

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

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

設置完畢將其發往下游路由器.

給出內容生產者或者路由器使用BC 方案處理興趣包以及數據包的偽代碼.

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

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

3 實驗結果與分析

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

表1 實驗參數Tab.1 Experimental parameters

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

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

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

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

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

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

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

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

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

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

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

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

圖7 數據內容請求集中程度對評價指標的影響Fig.7 Impact of data content request concentration on evaluation indicators

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

4 結束語

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