基于流行度和CDT的NDN名稱查找方案*

張 進,江凌云

（南京郵電大學，江蘇 南京 210003）

0 引言

命名數據網絡（Named Data Networking，NDN）[1-2]不是像TCP/IP基于目的地址轉發數據包，而是基于數據名稱。其中名稱采用類似URL的層次化結構，便于流量多路分解，為數據的使用提供上下文信息。在NDN中，路由轉發過程中轉發信息表（Forwarding Information Base，FIB）的名稱查找同樣支持最長前綴匹配，但與TCP/IP的最長前綴匹配有兩個實質性的區別[3]。首先，NDN名稱是由“/”分割的各個名稱組件組成的，需要將名稱組件看成一個整體進行匹配。而IP地址可以在任何二進制位匹配前綴。其次，IP地址是固定長度的，NDN名稱長度是可變的，沒有明確的上限。這就造成相比傳統的TCP/IP中的路由表條目，NDN中FIB的名稱條目會呈現指數級爆炸性增長。于是，在如此龐大的FIB表中快速、準確地命中興趣包中的名稱條目，減少FIB的占用內存成為一個亟需解決的問題。現有的名稱查找改進方案尚不成熟，例如基于FIB表拆分的名稱查找方案專注于FIB表的拆分，不考慮底層數據結構，基于底層數據結構的一些名稱查找方案采用的底層數據結構還具備改進空間。針對以上缺陷，提出了一種基于流行度和CDT的NDN名稱查找方案。

1 相關工作

針對NDN中FIB條目的數量級大、層次化名稱的查詢效率低等問題，專家和學者提出了一些名稱查找方案，主要分為3個方面：基于底層數據結構的名稱查找方案、基于FIB表拆分的名稱查找方案、基于查找方式的名稱查找方案。

1.1 基于底層數據結構的名稱查找方案

FIB的底層數據結構是一個研究熱點，許多專家和學者致力于研究采用何種數據結構可以在減少FIB內存占用的同時加速NDN的名稱查找速度。所提出的方案采用的數據結構主要包括hash表、前綴樹、布隆過濾器等，具體如下。

Saxena等[4]提出了一種基于可擴展且高效存儲的Patricia trie（前綴樹）的名稱轉發方案，稱為N-FIB。N-FIB將數據名稱存儲在Patricia trie中，同時在存儲的過程中支持FIB聚合，以極大地減小大FIB和高FIB更新成本的影響。Kim等[5]提出了一種將hash表和Patricia trie相結合的名稱查找方案。其中，hash表采用分層表，將層次化名稱的每一級名稱組件進行一次hash運算，并存儲進Patricia trie中，這也就意味著每一級名稱組件都包括一組hash表和Patricia trie。此方案可以有效地容納可變的和無界的內容名稱，加快了查找速度，但會加大內存占用。并且，以上兩種方案沒有將名稱的流行度考慮進底層數據結構的設計當中。

Hao等[6]提出了一種新穎的名稱查找機制（Bloom Filter+Popularity Table+Degraded Trie，BF-PDT），該機制結合了Counting Bloom Filter，Popularity table和Degraded Trie。當需要在FIB中檢索名稱條目時，首先在CBF中進行判斷。如果CBF判斷該條目在FIB中，則繼續在流行度表（Popularity Table，PT）中搜索。PT記錄了一些流行度最高的前綴信息。如果條目的前綴在PT中，則可以大大提高搜索速度。最后，在Degraded Tire（DT）中搜索條目。此方案考慮了名稱流行度的影響，但其在流行度表中存儲的是DT中節點的地址，還需要去DT進一步尋找下一跳信息，不能充分發揮流行度表的作用。同時，DT中一個節點只存儲一個名稱組件，是十分占用內存的。

1.2 基于FIB表拆分的名稱查找方案

FIB表項數目在實際規模中會非常龐大，給名稱查找帶來很大的困難。但是將龐大的表拆分為不同的表，在這幾張表中建立聯系，會減少每張表的名稱數量，從而提升名稱查找的效率，以下的方案就是在這種思想下形成的。

Khelifi等[7]采用了一種“名稱到哈希”編碼方案。這個方案將每個名稱組件分別進行哈希計算，使之成為固定長度。存儲時將其切割拆分到兩個表（hash表、前綴表）中進行存儲，兩張表中分別通過一個字段相連。然后執行啟發式（類似Wu-Manber[8]）的算法查找過程。將長度很大的hash值切割分散存儲會提升名稱的查找速度并具有良好的可擴展性。但是，此方案同樣沒有考慮名稱流行度對FIB表拆分設計的影響。

Nguyen等[9]提出了SmartFIB方案，將FIB拆分為主FIB、eFIB，eFIB作為新路由的存儲，主FIB作為高頻路由的存儲。當新路由在本地路由存儲中不存在時，該路由首先進入eFIB，并且如果沒有被興趣包所請求，則可能會在eFIB的特征時間之后從eFIB中移出。主FIB用作高頻路由的存儲。高頻是指流行前綴和具有重復路由請求的路由，可以利用eFIB來決定將哪些路由放入主FIB中。此方案著重考慮了名稱流行度的影響，但其專注于FIB表的拆分，沒有給出具體的底層數據結構方案。

1.3 基于查找方式的名稱查找方案

NDN中默認是使用最長前綴匹配（Longest Prefix Match，LPM）的方式來將興趣包中的名稱與FIB中的名稱條目進行匹配，如/school/library/book在FIB中可匹配/school、/school/library以及/school/library/book。而/school/library/book是最長前綴匹配。為了支持LPM匹配算法，名稱查找從名稱前綴的最長長度開始，并按組件粒度逐漸減小。該過程反復進行，直到找到LPM。但是，這種線性搜索方法不僅性能欠佳，而且安全性也不理想，n個組件的名稱的不匹配興趣包需要進行n次FIB查找。因此，一些專家和學者提出了改進這種查找方式的方案。

Yuan等[10]提出了將二分查找的思想應用到NDN名稱查找的方案。令L和H為二分查找的上下限，而M=[(L+H)/2]為要查找的長度。命中時L=M+1，沒有命中時H=M-1。利用二分查找的思想會使名稱查找的時間復雜度從O(n)下降為Ologn。但是，為了保證二分查找的順利進行，需要在FIB表中添加虛擬條目，這無疑會加大內存的占用。為解決這一問題，Hu等[11]對存入FIB中條目的長度（組件個數）進行了約束（可以為奇數、偶數或其他自定義長度）。對于FIB表中的真實條目，需要確保其所有長度在其范圍內的名稱前綴都插入FIB中。如果不存在相應的真實條目，則將虛擬條目作為填充插入以支持二分查找。此方案可以相對減少虛擬條目的數量以及內存占用，但查找速度相對會變慢。

總的來說，以上名稱查找方案對FIB表的查找速度、內存占用都有一定的改進，但也存在明顯的不足。例如，文獻[6]在流行度表中存儲的是名稱前綴與前綴樹中節點的地址相對應的關系，還需要進一步去前綴樹中尋找具體的下一跳端口，并且其采取的DT是一個節點，只存儲一個名稱組件，這會加大DT中的節點數量，導致FIB占用的內存過大。文獻[9]專注于FIB表的拆分，沒有給出具體的底層數據結構方案。

2 基于流行度和CDT的NDN名稱查找方案

針對上節中討論的現有名稱查找方案存在的一些缺陷，本節提出了一種基于流行度和CDT的NDN名稱查找方案，該方案將FIB劃分為計數布隆過濾器（Counting Bloom Filter，CBF）、流行FIB、CDT、輔助FIB這4個部分，如圖1所示。

圖1 FIB的構成

2.1 計數布隆過濾器（CBF）

布隆過濾器（Bloom Filter，BF）是一種節省空間的概率數據結構，初始狀態下每個位置的值都為0。當向BF中插入元素時，會將元素用不同的哈希函數計算，映射到BF中的不同位置，并將相應位的值設置為1。當要在BF中檢索是否存在某個元素時，使用與插入元素時相同的哈希函數進行哈希運算，只有所有位的值都為1時，才能證明此元素位于BF中，否則不存在。

計數布隆過濾器（Counting Bloom Filter，CBF）是對BF的改進，每個位置的值不再只是0或者1，當元素映射到某個位置時，會將元素的值進行加1，刪除時會將元素的值減1。因此，CBF提升了準確度并支持了刪除功能。與文獻[6]一樣，這里同樣將FIB中的名稱前綴映射進CBF中來判斷某一名稱前綴是否位于CBF中，從而及時過濾掉不存在的名稱前綴，避免在后續數據結構查找中增加時間成本。只有在CBF中檢測到此名稱前綴，才進行后續操作。

2.2 流行FIB

流行FIB存儲名稱前綴與下一跳端口的對應關系，同時還存在一個隱藏列：請求頻率。它會統計規定的時間段內此表中的名稱前綴被請求的頻率次數，根據閾值來判定其是否屬于高流行度的名稱前綴，并且當上一時間段統計完畢進行下一時間段的統計時，會從0開始重新計數，保證名稱流行度的實時性。其底層采用的是hash表，與之前的方案存儲名稱前綴及前綴樹中節點地址不同的是本文方案直接在這里存儲名稱前綴與下一跳的關系。因為此表中存儲的已經是流行度高的前綴了，應該加快其查找命中并轉發的速度，不用在這里考慮優化其內存占用。因此，本文采用的是效率高的hash表的數據結構，如圖2所示。

2.3 Conflict-split Degraded Trie（CDT）

除流行FIB中存儲的名稱前綴外都要存儲在Conflict-split Degraded Trie（CDT）中。

前綴樹（Trie）又稱為單詞查找樹，是常用于存儲大量的字符串的樹形數據結構，其優點是可以利用字符串的公共前綴來節約存儲空間。因此，很多學者將Trie運用到了NDN中FIB的底層數據結構中，但其運用的方案仍有改進空間。如文獻[6]采用的Degraded Trie，其特點如下：

（1）除根節點外的每個節點不再僅包含一個字符，而是包含一個組件（條目/com/baidu具有com和baidu兩個組件），這將大大減小樹的深度。

（2）對于所有節點，其子節點的數目不再固定，僅添加FIB中存在的節點，以便對前綴樹進行裁剪。

此方案已將節點數量進行了一定程度的削減，但實際存儲中會存在大量“單支”（前綴樹的某一分支只存儲一個名稱前綴）的情況，如果此名稱前綴很長，一個節點限制只能存儲一個名稱組件的話也是相當耗費內存占用的。因此本文采用一種Conflict-split Degraded Trie（CDT）的數據結構。它遵循這樣的原則，即名稱前綴默認存儲在一個節點中，只有在出現沖突時才進行拆分，產生沖突的情況有如下兩種：

（1）CDT中名稱組件存在沖突的情況。

首先向一個空的CDT中插入一個名稱前綴/com/google/movie/comedy,如圖3中左圖所示，此時CDT中除根節點外只存在一個節點。當插入另一個名稱前綴/com/google/movie/drama時，名稱中的前3個組件（com、google、movie）不存在沖突，依舊存儲在一個節點當中，而最后一個組件drama與CDT中已存在的名稱/com/google/movie/comedy中的最后一個組件comedy產生沖突，則進行拆分，將comedy從原節點拆分出來存放在一個新節點中，drama組件也新建一個節點進行存儲，如圖3中右圖所示。

（2）CDT中公共前綴與原名稱前綴存在沖突的情況。

仍使用僅存儲了一個名稱前綴/com/google/movie/comedy的CDT。當插入此名稱的公共前綴/com/google/movie時，需要將原來的節點拆分，將/com/google/movie存儲在一個節點，將名稱組件comedy新建一個節點進行存儲，如圖4所示。這是因為原來的節點存放的是/com/google/movie/comedy的下一跳，而插入其公共前綴/com/google/movie，會存在新的下一跳，為了使得興趣包能夠被準確地轉發到對應名稱的下一跳，將其拆分進行存儲來保證正確性。

當存儲圖1中FIB除流行FIB外的名稱條目時，如圖5所示。

圖4 CDT中公共前綴與原名稱前綴存在沖突的情況

圖5 除流行FIB外的名稱條目在DT及CDT的存儲

圖5中/com/google、/cn/google以及/action/movie就是之前所說的“單支”的情況，如果按照Degraded Trie的存儲方式存儲，將像左圖一樣各需要兩個節點。如果按照本文方案，例如com與google之間是沒有沖突的，則會存儲到1個節點，如圖5右圖所示。這樣前綴樹的節點數量有所減少，樹的深度也有所降低，會大大減少內存占用。并且名稱前綴的數量越大，優化效果越明顯。

2.4 輔助FIB

輔助FIB用于輔助流行FIB、CDT。其存儲的是名稱前綴與CDT中的地址對應的關系。這里的名稱前綴是除流行FIB中存儲的名稱前綴外的流行度較高的前綴，同時也包括一些公共的名稱前綴。與流行FIB類似，它也具備一個隱藏列——請求頻率。它會在規定的時間段后與流行FIB進行流行前綴的更新替換，來保證流行FIB中存儲的一直是高流行度的名稱前綴。它也會用來輔助在前綴樹中快速定位到一些名稱前綴的位置，可以是具體的名稱前綴，也可以是一些公共名稱前綴，如圖6所示。

圖6 輔助FIB及其底層數據結構、CDT

/com/google/scholar就是一個具體的名稱前綴，可以通過在輔助FIB中檢索定位到其在CDT中的地址快速找到存儲下一跳的節點進行轉發。而在實際網絡中往往也會出現一些公共名稱前綴出現的概率較高，而具體的前綴出現的概率反而不高，例如輔助FIB中的/cn/google/movie，當想要檢索/cn/google/movie/comedy時，可以先在輔助FIB中定位到/cn/google/movie在前綴樹中的地址，找到此節點后再向其子節點進行遍歷從而找到具體的節點獲取到下一跳進行轉發。

當然，輔助FIB還有一個功能就是與流行FIB進行實時的更新替換，它們會在規定的時間段內統計其包括的名稱前綴的請求頻率，每一個時間段都重新從0開始計數。設置一個閾值，高于閾值的進入流行FIB中，并在輔助FIB、CDT中進行刪除。低于閾值的插入到輔助FIB以及CDT中。如圖7所示，假設經過了規定的時間段統計的請求頻率發生了變化，流行FIB中的/com/popular/4請求頻率由1 002變為956，輔助FIB中的/com/google/scholar的請求頻率由866變為1 044。假設閾值為1 000，則在流行FIB中刪除/com/popular/4，將其添加到輔助FIB及CDT中。在輔助FIB中刪除/com/google/scholar，將其添加進流行FIB中，從而保證了流行FIB中的名稱前綴的高流行度。

3 名稱查找方案的處理過程

本節將對提出的名稱查找方案具體的處理過程進行詳述，主要包括名稱查找、名稱插入、名稱刪除3部分。

3.1 名稱查找

如圖8所示，當要在FIB中查找某一名稱前綴對應的下一跳端口時，主要包含以下幾個步驟：

圖7 輔助FIB與流行FIB的更新替換過程

（1）首先在CBF中檢索，如果CBF中不存在此名稱前綴，則直接丟棄掉請求該名稱前綴的興趣包，否則在流行FIB中檢索。

（2）如果在流行FIB中查到了對應的名稱條目，則直接通過下一跳端口轉發，沒有的話則檢索輔助FIB。

（3）如果輔助FIB檢索到此名稱前綴，則根據其定位的CDT中的節點地址快速定位到對應的節點獲取到下一跳。

（4）如果輔助FIB檢索到此名稱前綴的公共前綴，則根據其定位的CDT中的公共前綴的節點地址快速定位到對應的節點，并繼續向其子分支節點進行遍歷，從而獲取到下一跳。

（5）如果輔助FIB中也不存在，則從CDT的根節點開始向下遍歷，直到找到對應的節點獲取到下一跳。

（6）如果CDT中也尋找不到此名稱前綴，則丟棄掉請求該名稱前綴的興趣包。

圖8 名稱查找過程

3.2 名稱插入

如圖9所示，要向FIB中插入名稱前綴，主要包含以下幾個步驟：

（1）由于需要根據其請求頻率進行插入，因此首先要獲取到要插入的名稱前綴的請求頻率。

（2）將此名稱前綴進行哈希運算映射進CBF中。

（3）當其請求頻率高于流行FIB中的最低請求頻率時，則插入流行FIB中。

（4）如果低于流行FIB的最低請求頻率，但高于輔助FIB中的最低請求頻率時，則首先添加進CDT中，再在輔助FIB中保留其與節點地址的關系。

（5）如果請求頻率低于輔助FIB的最低請求頻率，則只在CDT中添加。

3.3 名稱刪除

如圖10所示，要在FIB中刪除名稱前綴，主要包含以下幾個步驟：

（1）首先在CBF中刪除掉此名稱前綴的映射結果。

（2）如果要刪除的名稱前綴在流行FIB中，則直接在流行FIB中刪除此名稱前綴和其下一跳的關系條目即可。

（3）如果在輔助FIB中，則首先根據輔助FIB定位到的節點地址在CDT中刪除對應的節點，再在輔助FIB中刪除掉對應的名稱前綴與CDT中節點地址的關系條目。

（4）如果輔助FIB中沒有，則直接從根節點遍歷，直到找到對應的名稱前綴節點并刪除。

圖9 名稱插入過程

圖10 名稱刪除過程

4 實驗和結果

在本節中，將對本文所提出的NDN名稱查找方案進行仿真實驗，使用Java語言在Windows系統下進行仿真驗證。

4.1 實驗設置

由于需要驗證本文方案相比文獻[6]提出的方案在NDN名稱查找上的優勢，因此直接使用Java語言在Windows平臺上對其底層采取的數據結構進行模擬驗證，Windows平臺配置如表1所示。數據集來自文獻[12]提出的NameGen，它是一個生成NDN/CCN名稱數據集的程序。本文用其生成了創建時間統計數據集、查找時間統計數據集、內存占用統計數據集。

表1 仿真平臺配置

如圖11所示，在本文名稱查找方案中采用四個數據結構：CBF、流行hash表（流行FIB，存儲名稱前綴與下一跳的關系）、輔助hash表（輔助FIB，存儲名稱前綴與CDT中地址的關系）、CDT（一個節點不是只能存儲一個組件，如果不存在沖突，則可以存儲多個名稱組件）。本文在模擬文獻[6]中的BF-PDT方案采用三個數據結構：CBF、流行hash表（與本文方案中的流行hash表不同，這里存儲流行名稱前綴與DT中地址的關系）、DT（一個節點只存儲一個名稱組件），如圖12所示。

同時，為了驗證BF-PDT方案中流行度表以及本文方案中流行FIB、輔助FIB的作用，本文在實驗時增加了2個對比方案：BF-DT（只有CBF和DT）以及BF-CDT（只有CBF和CDT）。

圖11 基于流行度和CDT方案的實驗數據結構

圖12 BF-PDT方案實驗數據結構

4.2 實驗指標

（1）創建時間：將2～100 000的數據集分別存儲進4種方案的數據結構所花費的時間。同樣數量的數據集存儲進不同的數據結構中存儲的時間越少，證明數據結構的存儲效率越高。

（2）查找時間：分別在已經存儲了2～100 000數據的數據結構中查找對應數據集數量的名稱前綴所花費的時間。查找時間花費得越少，證明名稱查找方案的處理過程越合理，數據結構的查找效率越高。這是NDN名稱查找方案中比較重要的一個實驗指標。

（3）內存占用：將10～100 000的數據集分別存儲進四種方案的數據結構所占用的內存。同樣數量的數據集存儲進不同的數據結構中占用的內存越少，證明數據結構的內存設計越優。

4.3 實驗結果

4.3.1 創建時間

圖13顯示了本文提出的基于流行度和CDT的名稱查找方案與BF-PDT方案、BF-DT方案以及BFCDT方案分別將2～100 000的數據集存入所花費的時間的變化曲線。可以看出，4種方案的創建時間隨著FIB中名稱數量的增長處于上升趨勢。從本文方案與BF-PDT方案、BF-DT方案與BF-CDT方案的對比情況來看，方案中采用CDT的比采用DT的花費的時間更少，這是因為CDT中一個節點不一定只存儲一個名稱組件，而DT中一個節點只能存儲一個名稱組件。節點數、深度有所下降，名稱前綴存入數據結構花費的時間會減少。從本文方案與BF-CDT方案、BF-PDT方案與BF-DT方案的對比情況來看，采用流行度表的方案所花費的時間更少，這是因為hash表中用到的哈希運算是很快速的，相比前綴樹中進行遍歷來創建節點時間花費是更少的。

4.3.2 查找時間

圖14顯示了本文提出的名稱查找方案與其他3種方案分別在存入2～100 000的數據集的數據結構中查找對應數據集數量的名稱前綴所花費時間的變化曲線。與創建時間類似，4種方案的查找時間呈現上升趨勢。從本文方案與BF-PDT方案的對比情況來看，本文方案查找時間更少，這是因為本文方案直接將流行的名稱前綴和其下一跳的對應關系存入到了流行度表而不是像BF-PDT里那樣流行度表存儲名稱前綴和DT中節點地址的對應關系，仍需要進一步去DT中尋找下一跳，因此流行的名稱前綴會更快地命中FIB中的名稱條目。從BF-DT與BFCDT方案的對比情況來看，BF-CDT的查找時間更少，這是因為CDT的節點數目和樹的深度低于DT，自然在樹中進行遍歷尋找下一跳信息也會更快。從本文方案與BF-CDT方案、BF-PDT方案與BF-DT方案的對比情況來看，流行度表對于查找時間的優化效果是很明顯的，可見在FIB底層數據結構的設計中考慮名稱流行度的影響是可以提升查找性能的。

圖13 創建時間隨FIB中名稱數量的變化曲線

圖14 查找時間隨FIB中名稱數量的變化曲線

4.3.3 內存占用

圖15顯示了四種方案分別在存入10～100 000的數據集的數據結構所占用內存的變化柱狀圖。從本文方案與BF-PDT方案的對比情況來看，本文方案的內存占用也是更少的，同樣是因為采用CDT會比DT節點數目更少，節點數更少也就會導致樹的內存占用更少。而從BF-PDT方案與BF-DT方案、本文方案與BF-CDT方案的對比情況來看，本文方案與BF-PDT方案相比不存在流行度表的方案內存占用會稍多一些，這是因為hash表需要對每個前綴開辟空間存儲，而前綴樹會對前綴的公共部分進行聚合存儲，內存占用會相對更少一些。

5 結語

命名數據網絡中的FIB的存儲和名稱查找是一個亟需解決的問題。本文從基于FIB表拆分的名稱查找方案以及基于底層數據結構的名稱查找方案的基礎上，針對它們的缺點，提出了基于流行度和CDT的NDN名稱查找方案。該方案將FIB劃分為CBF、流行FIB、CDT以及輔助FIB。CBF用于快速篩選掉不在FIB中的名稱前綴。流行FIB底層采用hash表，存儲流行名稱前綴與下一跳端口的對應關系，用于高流行度的名稱前綴的快速轉發。所有除了流行FIB中存儲的名稱前綴都要存儲到CDT中。CDT通過一個節點不一定只存儲一個名稱組件且只有在產生沖突時拆分的機制減少了樹的深度以及節點的數目。輔助FIB用于輔助流行FIB、CDT，底層采用hash表，存儲CDT中存儲的名稱前綴中的流行名稱前綴（包括一些公共前綴）與CDT中節點地址對應的關系，便于其快速定位到CDT的節點。輔助FIB、流行FIB根據流行度的變化進行實時更新、替換。最后通過實驗表明，該方案在創建時間、查找時間、內存占用指標上存在優化效果，證明該方案進一步提升了NDN中FIB的存儲和名稱查找性能。