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

張 進(jìn),江凌云

（南京郵電大學(xué)，江蘇 南京 210003）

0 引言

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

1 相關(guān)工作

針對(duì)NDN中FIB條目的數(shù)量級(jí)大、層次化名稱的查詢效率低等問(wèn)題，專家和學(xué)者提出了一些名稱查找方案，主要分為3個(gè)方面：基于底層數(shù)據(jù)結(jié)構(gòu)的名稱查找方案、基于FIB表拆分的名稱查找方案、基于查找方式的名稱查找方案。

1.1 基于底層數(shù)據(jù)結(jié)構(gòu)的名稱查找方案

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

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

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

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

FIB表項(xiàng)數(shù)目在實(shí)際規(guī)模中會(huì)非常龐大，給名稱查找?guī)?lái)很大的困難。但是將龐大的表拆分為不同的表，在這幾張表中建立聯(lián)系，會(huì)減少每張表的名稱數(shù)量，從而提升名稱查找的效率，以下的方案就是在這種思想下形成的。

Khelifi等[7]采用了一種“名稱到哈?！本幋a方案。這個(gè)方案將每個(gè)名稱組件分別進(jìn)行哈希計(jì)算，使之成為固定長(zhǎng)度。存儲(chǔ)時(shí)將其切割拆分到兩個(gè)表（hash表、前綴表）中進(jìn)行存儲(chǔ)，兩張表中分別通過(guò)一個(gè)字段相連。然后執(zhí)行啟發(fā)式（類(lèi)似Wu-Manber[8]）的算法查找過(guò)程。將長(zhǎng)度很大的hash值切割分散存儲(chǔ)會(huì)提升名稱的查找速度并具有良好的可擴(kuò)展性。但是，此方案同樣沒(méi)有考慮名稱流行度對(duì)FIB表拆分設(shè)計(jì)的影響。

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

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

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

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

總的來(lái)說(shuō)，以上名稱查找方案對(duì)FIB表的查找速度、內(nèi)存占用都有一定的改進(jìn)，但也存在明顯的不足。例如，文獻(xiàn)[6]在流行度表中存儲(chǔ)的是名稱前綴與前綴樹(shù)中節(jié)點(diǎn)的地址相對(duì)應(yīng)的關(guān)系，還需要進(jìn)一步去前綴樹(shù)中尋找具體的下一跳端口，并且其采取的DT是一個(gè)節(jié)點(diǎn)，只存儲(chǔ)一個(gè)名稱組件，這會(huì)加大DT中的節(jié)點(diǎn)數(shù)量，導(dǎo)致FIB占用的內(nèi)存過(guò)大。文獻(xiàn)[9]專注于FIB表的拆分，沒(méi)有給出具體的底層數(shù)據(jù)結(jié)構(gòu)方案。

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

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

圖1 FIB的構(gòu)成

2.1 計(jì)數(shù)布隆過(guò)濾器（CBF）

布隆過(guò)濾器（Bloom Filter，BF）是一種節(jié)省空間的概率數(shù)據(jù)結(jié)構(gòu)，初始狀態(tài)下每個(gè)位置的值都為0。當(dāng)向BF中插入元素時(shí)，會(huì)將元素用不同的哈希函數(shù)計(jì)算，映射到BF中的不同位置，并將相應(yīng)位的值設(shè)置為1。當(dāng)要在BF中檢索是否存在某個(gè)元素時(shí)，使用與插入元素時(shí)相同的哈希函數(shù)進(jìn)行哈希運(yùn)算，只有所有位的值都為1時(shí)，才能證明此元素位于BF中，否則不存在。

計(jì)數(shù)布隆過(guò)濾器（Counting Bloom Filter，CBF）是對(duì)BF的改進(jìn)，每個(gè)位置的值不再只是0或者1，當(dāng)元素映射到某個(gè)位置時(shí)，會(huì)將元素的值進(jìn)行加1，刪除時(shí)會(huì)將元素的值減1。因此，CBF提升了準(zhǔn)確度并支持了刪除功能。與文獻(xiàn)[6]一樣，這里同樣將FIB中的名稱前綴映射進(jìn)CBF中來(lái)判斷某一名稱前綴是否位于CBF中，從而及時(shí)過(guò)濾掉不存在的名稱前綴，避免在后續(xù)數(shù)據(jù)結(jié)構(gòu)查找中增加時(shí)間成本。只有在CBF中檢測(cè)到此名稱前綴，才進(jìn)行后續(xù)操作。

2.2 流行FIB

流行FIB存儲(chǔ)名稱前綴與下一跳端口的對(duì)應(yīng)關(guān)系，同時(shí)還存在一個(gè)隱藏列：請(qǐng)求頻率。它會(huì)統(tǒng)計(jì)規(guī)定的時(shí)間段內(nèi)此表中的名稱前綴被請(qǐng)求的頻率次數(shù)，根據(jù)閾值來(lái)判定其是否屬于高流行度的名稱前綴，并且當(dāng)上一時(shí)間段統(tǒng)計(jì)完畢進(jìn)行下一時(shí)間段的統(tǒng)計(jì)時(shí)，會(huì)從0開(kāi)始重新計(jì)數(shù)，保證名稱流行度的實(shí)時(shí)性。其底層采用的是hash表，與之前的方案存儲(chǔ)名稱前綴及前綴樹(shù)中節(jié)點(diǎn)地址不同的是本文方案直接在這里存儲(chǔ)名稱前綴與下一跳的關(guān)系。因?yàn)榇吮碇写鎯?chǔ)的已經(jīng)是流行度高的前綴了，應(yīng)該加快其查找命中并轉(zhuǎn)發(fā)的速度，不用在這里考慮優(yōu)化其內(nèi)存占用。因此，本文采用的是效率高的hash表的數(shù)據(jù)結(jié)構(gòu)，如圖2所示。

2.3 Conflict-split Degraded Trie（CDT）

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

前綴樹(shù)（Trie）又稱為單詞查找樹(shù)，是常用于存儲(chǔ)大量的字符串的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，其優(yōu)點(diǎn)是可以利用字符串的公共前綴來(lái)節(jié)約存儲(chǔ)空間。因此，很多學(xué)者將Trie運(yùn)用到了NDN中FIB的底層數(shù)據(jù)結(jié)構(gòu)中，但其運(yùn)用的方案仍有改進(jìn)空間。如文獻(xiàn)[6]采用的Degraded Trie，其特點(diǎn)如下：

（1）除根節(jié)點(diǎn)外的每個(gè)節(jié)點(diǎn)不再僅包含一個(gè)字符，而是包含一個(gè)組件（條目/com/baidu具有com和baidu兩個(gè)組件），這將大大減小樹(shù)的深度。

（2）對(duì)于所有節(jié)點(diǎn)，其子節(jié)點(diǎn)的數(shù)目不再固定，僅添加FIB中存在的節(jié)點(diǎn)，以便對(duì)前綴樹(shù)進(jìn)行裁剪。

此方案已將節(jié)點(diǎn)數(shù)量進(jìn)行了一定程度的削減，但實(shí)際存儲(chǔ)中會(huì)存在大量“單支”（前綴樹(shù)的某一分支只存儲(chǔ)一個(gè)名稱前綴）的情況，如果此名稱前綴很長(zhǎng)，一個(gè)節(jié)點(diǎn)限制只能存儲(chǔ)一個(gè)名稱組件的話也是相當(dāng)耗費(fèi)內(nèi)存占用的。因此本文采用一種Conflict-split Degraded Trie（CDT）的數(shù)據(jù)結(jié)構(gòu)。它遵循這樣的原則，即名稱前綴默認(rèn)存儲(chǔ)在一個(gè)節(jié)點(diǎn)中，只有在出現(xiàn)沖突時(shí)才進(jìn)行拆分，產(chǎn)生沖突的情況有如下兩種：

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

首先向一個(gè)空的CDT中插入一個(gè)名稱前綴/com/google/movie/comedy,如圖3中左圖所示，此時(shí)CDT中除根節(jié)點(diǎn)外只存在一個(gè)節(jié)點(diǎn)。當(dāng)插入另一個(gè)名稱前綴/com/google/movie/drama時(shí)，名稱中的前3個(gè)組件（com、google、movie）不存在沖突，依舊存儲(chǔ)在一個(gè)節(jié)點(diǎn)當(dāng)中，而最后一個(gè)組件drama與CDT中已存在的名稱/com/google/movie/comedy中的最后一個(gè)組件comedy產(chǎn)生沖突，則進(jìn)行拆分，將comedy從原節(jié)點(diǎn)拆分出來(lái)存放在一個(gè)新節(jié)點(diǎn)中，drama組件也新建一個(gè)節(jié)點(diǎn)進(jìn)行存儲(chǔ)，如圖3中右圖所示。

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

仍使用僅存儲(chǔ)了一個(gè)名稱前綴/com/google/movie/comedy的CDT。當(dāng)插入此名稱的公共前綴/com/google/movie時(shí)，需要將原來(lái)的節(jié)點(diǎn)拆分，將/com/google/movie存儲(chǔ)在一個(gè)節(jié)點(diǎn)，將名稱組件comedy新建一個(gè)節(jié)點(diǎn)進(jìn)行存儲(chǔ)，如圖4所示。這是因?yàn)樵瓉?lái)的節(jié)點(diǎn)存放的是/com/google/movie/comedy的下一跳，而插入其公共前綴/com/google/movie，會(huì)存在新的下一跳，為了使得興趣包能夠被準(zhǔn)確地轉(zhuǎn)發(fā)到對(duì)應(yīng)名稱的下一跳，將其拆分進(jìn)行存儲(chǔ)來(lái)保證正確性。

當(dāng)存儲(chǔ)圖1中FIB除流行FIB外的名稱條目時(shí)，如圖5所示。

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

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

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

2.4 輔助FIB

輔助FIB用于輔助流行FIB、CDT。其存儲(chǔ)的是名稱前綴與CDT中的地址對(duì)應(yīng)的關(guān)系。這里的名稱前綴是除流行FIB中存儲(chǔ)的名稱前綴外的流行度較高的前綴，同時(shí)也包括一些公共的名稱前綴。與流行FIB類(lèi)似，它也具備一個(gè)隱藏列——請(qǐng)求頻率。它會(huì)在規(guī)定的時(shí)間段后與流行FIB進(jìn)行流行前綴的更新替換，來(lái)保證流行FIB中存儲(chǔ)的一直是高流行度的名稱前綴。它也會(huì)用來(lái)輔助在前綴樹(shù)中快速定位到一些名稱前綴的位置，可以是具體的名稱前綴，也可以是一些公共名稱前綴，如圖6所示。

圖6 輔助FIB及其底層數(shù)據(jù)結(jié)構(gòu)、CDT

/com/google/scholar就是一個(gè)具體的名稱前綴，可以通過(guò)在輔助FIB中檢索定位到其在CDT中的地址快速找到存儲(chǔ)下一跳的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)。而在實(shí)際網(wǎng)絡(luò)中往往也會(huì)出現(xiàn)一些公共名稱前綴出現(xiàn)的概率較高，而具體的前綴出現(xiàn)的概率反而不高，例如輔助FIB中的/cn/google/movie，當(dāng)想要檢索/cn/google/movie/comedy時(shí)，可以先在輔助FIB中定位到/cn/google/movie在前綴樹(shù)中的地址，找到此節(jié)點(diǎn)后再向其子節(jié)點(diǎn)進(jìn)行遍歷從而找到具體的節(jié)點(diǎn)獲取到下一跳進(jìn)行轉(zhuǎn)發(fā)。

當(dāng)然，輔助FIB還有一個(gè)功能就是與流行FIB進(jìn)行實(shí)時(shí)的更新替換，它們會(huì)在規(guī)定的時(shí)間段內(nèi)統(tǒng)計(jì)其包括的名稱前綴的請(qǐng)求頻率，每一個(gè)時(shí)間段都重新從0開(kāi)始計(jì)數(shù)。設(shè)置一個(gè)閾值，高于閾值的進(jìn)入流行FIB中，并在輔助FIB、CDT中進(jìn)行刪除。低于閾值的插入到輔助FIB以及CDT中。如圖7所示，假設(shè)經(jīng)過(guò)了規(guī)定的時(shí)間段統(tǒng)計(jì)的請(qǐng)求頻率發(fā)生了變化，流行FIB中的/com/popular/4請(qǐng)求頻率由1 002變?yōu)?56，輔助FIB中的/com/google/scholar的請(qǐng)求頻率由866變?yōu)? 044。假設(shè)閾值為1 000，則在流行FIB中刪除/com/popular/4，將其添加到輔助FIB及CDT中。在輔助FIB中刪除/com/google/scholar，將其添加進(jìn)流行FIB中，從而保證了流行FIB中的名稱前綴的高流行度。

3 名稱查找方案的處理過(guò)程

本節(jié)將對(duì)提出的名稱查找方案具體的處理過(guò)程進(jìn)行詳述，主要包括名稱查找、名稱插入、名稱刪除3部分。

3.1 名稱查找

如圖8所示，當(dāng)要在FIB中查找某一名稱前綴對(duì)應(yīng)的下一跳端口時(shí)，主要包含以下幾個(gè)步驟：

圖7 輔助FIB與流行FIB的更新替換過(guò)程

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

（2）如果在流行FIB中查到了對(duì)應(yīng)的名稱條目，則直接通過(guò)下一跳端口轉(zhuǎn)發(fā)，沒(méi)有的話則檢索輔助FIB。

（3）如果輔助FIB檢索到此名稱前綴，則根據(jù)其定位的CDT中的節(jié)點(diǎn)地址快速定位到對(duì)應(yīng)的節(jié)點(diǎn)獲取到下一跳。

（4）如果輔助FIB檢索到此名稱前綴的公共前綴，則根據(jù)其定位的CDT中的公共前綴的節(jié)點(diǎn)地址快速定位到對(duì)應(yīng)的節(jié)點(diǎn)，并繼續(xù)向其子分支節(jié)點(diǎn)進(jìn)行遍歷，從而獲取到下一跳。

（5）如果輔助FIB中也不存在，則從CDT的根節(jié)點(diǎn)開(kāi)始向下遍歷，直到找到對(duì)應(yīng)的節(jié)點(diǎn)獲取到下一跳。

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

圖8 名稱查找過(guò)程

3.2 名稱插入

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

（1）由于需要根據(jù)其請(qǐng)求頻率進(jìn)行插入，因此首先要獲取到要插入的名稱前綴的請(qǐng)求頻率。

（2）將此名稱前綴進(jìn)行哈希運(yùn)算映射進(jìn)CBF中。

（3）當(dāng)其請(qǐng)求頻率高于流行FIB中的最低請(qǐng)求頻率時(shí)，則插入流行FIB中。

（4）如果低于流行FIB的最低請(qǐng)求頻率，但高于輔助FIB中的最低請(qǐng)求頻率時(shí)，則首先添加進(jìn)CDT中，再在輔助FIB中保留其與節(jié)點(diǎn)地址的關(guān)系。

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

3.3 名稱刪除

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

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

（2）如果要?jiǎng)h除的名稱前綴在流行FIB中，則直接在流行FIB中刪除此名稱前綴和其下一跳的關(guān)系條目即可。

（3）如果在輔助FIB中，則首先根據(jù)輔助FIB定位到的節(jié)點(diǎn)地址在CDT中刪除對(duì)應(yīng)的節(jié)點(diǎn)，再在輔助FIB中刪除掉對(duì)應(yīng)的名稱前綴與CDT中節(jié)點(diǎn)地址的關(guān)系條目。

（4）如果輔助FIB中沒(méi)有，則直接從根節(jié)點(diǎn)遍歷，直到找到對(duì)應(yīng)的名稱前綴節(jié)點(diǎn)并刪除。

圖9 名稱插入過(guò)程

圖10 名稱刪除過(guò)程

4 實(shí)驗(yàn)和結(jié)果

在本節(jié)中，將對(duì)本文所提出的NDN名稱查找方案進(jìn)行仿真實(shí)驗(yàn)，使用Java語(yǔ)言在Windows系統(tǒng)下進(jìn)行仿真驗(yàn)證。

4.1 實(shí)驗(yàn)設(shè)置

由于需要驗(yàn)證本文方案相比文獻(xiàn)[6]提出的方案在NDN名稱查找上的優(yōu)勢(shì)，因此直接使用Java語(yǔ)言在Windows平臺(tái)上對(duì)其底層采取的數(shù)據(jù)結(jié)構(gòu)進(jìn)行模擬驗(yàn)證，Windows平臺(tái)配置如表1所示。數(shù)據(jù)集來(lái)自文獻(xiàn)[12]提出的NameGen，它是一個(gè)生成NDN/CCN名稱數(shù)據(jù)集的程序。本文用其生成了創(chuàng)建時(shí)間統(tǒng)計(jì)數(shù)據(jù)集、查找時(shí)間統(tǒng)計(jì)數(shù)據(jù)集、內(nèi)存占用統(tǒng)計(jì)數(shù)據(jù)集。

表1 仿真平臺(tái)配置

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

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

圖11 基于流行度和CDT方案的實(shí)驗(yàn)數(shù)據(jù)結(jié)構(gòu)

圖12 BF-PDT方案實(shí)驗(yàn)數(shù)據(jù)結(jié)構(gòu)

4.2 實(shí)驗(yàn)指標(biāo)

（1）創(chuàng)建時(shí)間：將2～100 000的數(shù)據(jù)集分別存儲(chǔ)進(jìn)4種方案的數(shù)據(jù)結(jié)構(gòu)所花費(fèi)的時(shí)間。同樣數(shù)量的數(shù)據(jù)集存儲(chǔ)進(jìn)不同的數(shù)據(jù)結(jié)構(gòu)中存儲(chǔ)的時(shí)間越少，證明數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)效率越高。

（2）查找時(shí)間：分別在已經(jīng)存儲(chǔ)了2～100 000數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)中查找對(duì)應(yīng)數(shù)據(jù)集數(shù)量的名稱前綴所花費(fèi)的時(shí)間。查找時(shí)間花費(fèi)得越少，證明名稱查找方案的處理過(guò)程越合理，數(shù)據(jù)結(jié)構(gòu)的查找效率越高。這是NDN名稱查找方案中比較重要的一個(gè)實(shí)驗(yàn)指標(biāo)。

（3）內(nèi)存占用：將10～100 000的數(shù)據(jù)集分別存儲(chǔ)進(jìn)四種方案的數(shù)據(jù)結(jié)構(gòu)所占用的內(nèi)存。同樣數(shù)量的數(shù)據(jù)集存儲(chǔ)進(jìn)不同的數(shù)據(jù)結(jié)構(gòu)中占用的內(nèi)存越少，證明數(shù)據(jù)結(jié)構(gòu)的內(nèi)存設(shè)計(jì)越優(yōu)。

4.3 實(shí)驗(yàn)結(jié)果

4.3.1 創(chuàng)建時(shí)間

圖13顯示了本文提出的基于流行度和CDT的名稱查找方案與BF-PDT方案、BF-DT方案以及BFCDT方案分別將2～100 000的數(shù)據(jù)集存入所花費(fèi)的時(shí)間的變化曲線。可以看出，4種方案的創(chuàng)建時(shí)間隨著FIB中名稱數(shù)量的增長(zhǎng)處于上升趨勢(shì)。從本文方案與BF-PDT方案、BF-DT方案與BF-CDT方案的對(duì)比情況來(lái)看，方案中采用CDT的比采用DT的花費(fèi)的時(shí)間更少，這是因?yàn)镃DT中一個(gè)節(jié)點(diǎn)不一定只存儲(chǔ)一個(gè)名稱組件，而DT中一個(gè)節(jié)點(diǎn)只能存儲(chǔ)一個(gè)名稱組件。節(jié)點(diǎn)數(shù)、深度有所下降，名稱前綴存入數(shù)據(jù)結(jié)構(gòu)花費(fèi)的時(shí)間會(huì)減少。從本文方案與BF-CDT方案、BF-PDT方案與BF-DT方案的對(duì)比情況來(lái)看，采用流行度表的方案所花費(fèi)的時(shí)間更少，這是因?yàn)閔ash表中用到的哈希運(yùn)算是很快速的，相比前綴樹(shù)中進(jìn)行遍歷來(lái)創(chuàng)建節(jié)點(diǎn)時(shí)間花費(fèi)是更少的。

4.3.2 查找時(shí)間

圖14顯示了本文提出的名稱查找方案與其他3種方案分別在存入2～100 000的數(shù)據(jù)集的數(shù)據(jù)結(jié)構(gòu)中查找對(duì)應(yīng)數(shù)據(jù)集數(shù)量的名稱前綴所花費(fèi)時(shí)間的變化曲線。與創(chuàng)建時(shí)間類(lèi)似，4種方案的查找時(shí)間呈現(xiàn)上升趨勢(shì)。從本文方案與BF-PDT方案的對(duì)比情況來(lái)看，本文方案查找時(shí)間更少，這是因?yàn)楸疚姆桨钢苯訉⒘餍械拿Q前綴和其下一跳的對(duì)應(yīng)關(guān)系存入到了流行度表而不是像BF-PDT里那樣流行度表存儲(chǔ)名稱前綴和DT中節(jié)點(diǎn)地址的對(duì)應(yīng)關(guān)系，仍需要進(jìn)一步去DT中尋找下一跳，因此流行的名稱前綴會(huì)更快地命中FIB中的名稱條目。從BF-DT與BFCDT方案的對(duì)比情況來(lái)看，BF-CDT的查找時(shí)間更少，這是因?yàn)镃DT的節(jié)點(diǎn)數(shù)目和樹(shù)的深度低于DT，自然在樹(shù)中進(jìn)行遍歷尋找下一跳信息也會(huì)更快。從本文方案與BF-CDT方案、BF-PDT方案與BF-DT方案的對(duì)比情況來(lái)看，流行度表對(duì)于查找時(shí)間的優(yōu)化效果是很明顯的，可見(jiàn)在FIB底層數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)中考慮名稱流行度的影響是可以提升查找性能的。

圖13 創(chuàng)建時(shí)間隨FIB中名稱數(shù)量的變化曲線

圖14 查找時(shí)間隨FIB中名稱數(shù)量的變化曲線

4.3.3 內(nèi)存占用

圖15顯示了四種方案分別在存入10～100 000的數(shù)據(jù)集的數(shù)據(jù)結(jié)構(gòu)所占用內(nèi)存的變化柱狀圖。從本文方案與BF-PDT方案的對(duì)比情況來(lái)看，本文方案的內(nèi)存占用也是更少的，同樣是因?yàn)椴捎肅DT會(huì)比DT節(jié)點(diǎn)數(shù)目更少，節(jié)點(diǎn)數(shù)更少也就會(huì)導(dǎo)致樹(shù)的內(nèi)存占用更少。而從BF-PDT方案與BF-DT方案、本文方案與BF-CDT方案的對(duì)比情況來(lái)看，本文方案與BF-PDT方案相比不存在流行度表的方案內(nèi)存占用會(huì)稍多一些，這是因?yàn)閔ash表需要對(duì)每個(gè)前綴開(kāi)辟空間存儲(chǔ)，而前綴樹(shù)會(huì)對(duì)前綴的公共部分進(jìn)行聚合存儲(chǔ)，內(nèi)存占用會(huì)相對(duì)更少一些。

5 結(jié)語(yǔ)

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