李 瑋，張大方，徐 冰

?

面向NDN中名字查找的哈希布魯姆過濾器

李 瑋，張大方，徐 冰

(湖南大學(xué)信息科學(xué)與工程學(xué)院 長沙 410082)

該文設(shè)計了一種面向NDN中名字查找的哈希布魯姆過濾器(HBF)。HBF由位于片內(nèi)存儲器中的個計數(shù)器布魯姆過濾器(CBF)、個計數(shù)器和位于片外存儲器中的個哈希表組成，每個哈希表與1個CBF和1個計數(shù)器關(guān)聯(lián)。為了避免因部分CBF存入名字過多而導(dǎo)致HBF的高誤判率，HBF通過二次哈希選擇算法將NDN路由器中FIB/CS/PIT表項完整信息均勻分散保存于個CBF和個哈希表中，同時也利于數(shù)據(jù)包轉(zhuǎn)發(fā)的并行處理。理論分析和實驗結(jié)果表明在名字查找過程中，HBF利用片內(nèi)存儲器中CBF的定位與過濾作用，大幅度減少片外存儲器的訪問開銷，提高數(shù)據(jù)包轉(zhuǎn)發(fā)速率，有效避免泛洪攻擊。

數(shù)據(jù)包轉(zhuǎn)發(fā)速率; 哈希布魯姆過濾器; 命名數(shù)據(jù)網(wǎng)絡(luò); 名字查找; 二次哈希選擇算法

為了解決TCP/IP體系結(jié)構(gòu)在路由擴(kuò)展性、動態(tài)性、安全性、QoS、可靠性等方面日益突出的問題[1]，人們進(jìn)行了大量研究，并取得了豐碩的研究成果，命名數(shù)據(jù)網(wǎng)絡(luò)(named data networking, NDN)[2-3]就是其中的代表之一。NDN轉(zhuǎn)發(fā)層中需要維護(hù)FIB (forwarding information base)、CS(content store)、PIT (pending interest table)3類信息。

可擴(kuò)展的轉(zhuǎn)發(fā)層是NDN廣泛發(fā)展的關(guān)鍵，而FIB/CS/PIT中快速名字查找又是轉(zhuǎn)發(fā)層的核心問題，特別是FIB與PIT不僅需要遵循最長前綴匹配(longest prefix matching, LPM)的規(guī)則進(jìn)行名字查找，而且需要在大規(guī)模的名字集合中實現(xiàn)快速查找和更新，以滿足路由器的傳輸速率。盡管傳統(tǒng)網(wǎng)絡(luò)體系中面向IP地址的最長前綴匹配算法已經(jīng)非常成熟，但NDN命名特點使得名字查找比IP地址查找更加復(fù)雜；同時沒有上限的名字空間造成路由器中路由表項數(shù)過多，空間急劇膨脹，這給NDN中名字存儲和快速查找?guī)砹司薮蟮奶魬?zhàn)。目前針對NDN的名字查找技術(shù)有4種思路，分別是TCAM、哈希表、多步長字符特里樹(multi-bit character trie)、布魯姆過濾器(bloom filter, BF)。

文獻(xiàn)[2]最早提出使用TCAM實現(xiàn)快速名字查找，但是由于一個名字的長度可能達(dá)到幾百個字節(jié)，導(dǎo)致一個名字被拆分成多段存于TCAM中，因此需要多次TCAM查找，降低了查詢速度，遠(yuǎn)遠(yuǎn)達(dá)不到IP地址查找時的效率[4]。

文獻(xiàn)[3,5]將CS、FIB、PIT分別存放于3個不同哈希表中，文獻(xiàn)[6-7]采用線性鏈?zhǔn)焦１砗?left哈希表等哈希技術(shù)來解決哈希沖突問題，減少查詢時的訪問次數(shù)。盡管哈希表具有(1)的線性查找速度，但由于多個數(shù)據(jù)包達(dá)到時對同一個哈希表進(jìn)行查詢或更新操作，嚴(yán)重降低數(shù)據(jù)包的并發(fā)處理性能。同時由于哈希表占用空間較大，無法將CS/FIB/PIT等信息保存于訪問速度較快但空間受到限制的SRAM中，只能保存于DRAM中，DRAM與SRAM(片內(nèi))訪問延遲比為55:0.45[8]，當(dāng)網(wǎng)絡(luò)中出現(xiàn)大量泛洪攻擊時，攻擊包直接訪問時延較高的DRAM，耗盡路由器內(nèi)存資源，導(dǎo)致網(wǎng)絡(luò)擁塞。

基于編碼技術(shù)和特里樹，文獻(xiàn)[9-10]提出了名字詞元編碼特里樹(name component encoding trie, NCET)或編碼名字前綴特里樹(encode name prefix trie, ENPT)來進(jìn)行名字查找。但NCET或ENPT采用詞元-編碼映射表會增加額外存儲空間、訪問成本和名字詞元分解成本。

為了壓縮名字占用空間，文獻(xiàn)[11-13]提出采用結(jié)構(gòu)簡潔和查詢快速的BF來表示FIB或PIT，分別是DiPIT、UBF、Namefilter。但由于BF假陽性而無法進(jìn)行有效回路檢查；同時由于BF只能記憶元素是否屬于某個集合，無法記憶元素詳細(xì)信息，例如無法保存PIT時間戳等信息，這樣對PIT中的過期表項就無法進(jìn)行有效處理；UBF、DiPIT、Namefilter也未提及FIB、FIT中除了名字字段之外其余字段的存儲設(shè)計方式。

為了有效解決上述問題，本文設(shè)計了一種面向NDN名字查找的哈希布魯姆過濾器(HBF)。HBF由位于片內(nèi)存儲器中的個計數(shù)器布魯姆過濾器(counting bloom filter, CBF)、個計數(shù)器和位于片外存儲器中的個哈希表組成。理論分析和實驗結(jié)果表明HBF利用片內(nèi)存儲器中CBF的定位與過濾作用，大幅度減少片外存儲器的訪問開銷，從而降低HBF的總體訪問成本，提高數(shù)據(jù)包轉(zhuǎn)發(fā)速率，有效避免泛洪攻擊。通過理論和實驗分析了HBF總體訪問成本的影響因素，找出了最優(yōu)參數(shù)設(shè)置，為工業(yè)界推廣應(yīng)用提供了理論設(shè)計依據(jù)。

1 相關(guān)工作

文獻(xiàn)[16]首次提出利用BF加速IP地址查找。文獻(xiàn)[13]據(jù)此提出Namefilter，直接使用名字前綴來代替IP前綴，將第二部分中哈希表換成個BF。由于NDN中名字前綴集合數(shù)目不定，Namefilter中BF個數(shù)就無法確定，這就要求NDN路由器動態(tài)調(diào)整BF的個數(shù)。由于FPGA、ASIC等專用硬件不能支持運行時動態(tài)創(chuàng)建BF，造成該方法無法適用基于FPGA、ASIC的硬件平臺。

文獻(xiàn)[12]提出了基于BF的數(shù)據(jù)結(jié)構(gòu)DiPIT，用于PIT的存儲和快速查詢及更新。DiPIT為NDN路由器中每個端口創(chuàng)建一個BF，用于存儲經(jīng)該端口的數(shù)據(jù)請求包的名字，同時創(chuàng)建一個共享BF，用來降低每個BF假陽性帶來的誤判。DiPIT中采用BF只能表示名字字段，無法表示PIT中每個表項的時間戳、Nonce列表、Face列表等字段。對于一些超過時限的PIT表項，DiPIT采用周期性衰減BF中每個計數(shù)器值的策略，會刪除一些處于正常時限內(nèi)的PIT表項，導(dǎo)致無法轉(zhuǎn)發(fā)部分?jǐn)?shù)據(jù)回復(fù)包。

NDN的實現(xiàn)原型CCNx提出名字前綴哈希表 (name prefix hash table, NPHT)[23]建立FIB和PIT共同的索引。FIB和PIT表項詳細(xì)信息分別存于2個不同的哈希表中。NPHT最大優(yōu)勢是通過前綴之間的關(guān)聯(lián)關(guān)系來提高最長前綴匹配效率。但NPHT存儲了FIB或PIT名字的所有字符，內(nèi)存空間占用較大，而且由于FIB與PIT索引存于同一個哈希表，這勢必成為多個數(shù)據(jù)包并行處理時的訪問瓶頸。

2 哈希布魯姆過濾器

2.1 HBF結(jié)構(gòu)和原理

與哈希表、樹型存儲及查詢算法、Trie存儲及查詢算法等相比，BF所需要空間與元素自身大小無關(guān)，僅與元素個數(shù)相關(guān)，極大降低了存儲空間。BF只能判斷名字是否存在NDN路由器FIB/CS/PIT表中，而不能返回該名字對應(yīng)的其他字段信息，因此需要用哈希表來存儲組織FIB、PIT或CS表的詳細(xì)信息。由于哈希表較大，無法保存于片內(nèi)存儲器中，只能保存于片外存儲器中，如DRAM?；诖?，本文提出的HBF由個CBF、個計數(shù)器和個哈希表組成，個CBF和個計數(shù)器存儲于片內(nèi)存儲器中，如SRAM；個哈希表存儲于片外存儲器中，如DRAM。其中哈希表中每個Entry由Key和Data兩部分組成，Key代表名字，Data代表該名字對應(yīng)的其他字段信息。HBF結(jié)構(gòu)如圖1所示。

圖1 HBF結(jié)構(gòu)示意圖

為了提高NDN路由轉(zhuǎn)發(fā)并行處理效率，利用3個HBF分別為CS、FIB、PIT建立存儲結(jié)構(gòu)，而不是將CS、FIB、PIT信息存于同一個HBF中。當(dāng)HBF應(yīng)用于CS時，哈希表中每個Entry的Data代表數(shù)據(jù)內(nèi)容(Content)；當(dāng)HBF應(yīng)用于FIB時，哈希表中每個Entry的Data代表FIB的轉(zhuǎn)發(fā)規(guī)則，即Face列表；當(dāng)HBF應(yīng)用于PIT時，哈希表中每個Entry的Data代表請求Face列表、Nonce列表和期限時間戳等字段。

為了解決每個CBF和哈希表中插入名字個數(shù)不均衡的問題，HBF采用二次哈希的方法選擇CBF和哈希表來保存名字及對應(yīng)信息。下面以PIT中的名字插入和查詢?yōu)槔齺碚f明HBF工作原理。

當(dāng)有一個新的數(shù)據(jù)請求包達(dá)到時，CS中未能查詢到請求數(shù)據(jù)內(nèi)容，同時PIT中也未發(fā)現(xiàn)該數(shù)據(jù)請求記錄，因此需要向PIT中插入該條數(shù)據(jù)請求記錄，插入過程分為3步：

1) 利用兩個哈希函數(shù)計算該數(shù)據(jù)請求包中名字字段的哈希值，分別為Hash0和Hash1；

2) 查詢Hash0和Hash1對應(yīng)的兩個計數(shù)器Counter和Counter的值，如果Counter>Counter，則將該名字插入到CBF中，否則插入CBF中；

3) 如果Counter≤Counter，則將該名字及其他信息插入Hashtable中，否則插入Hashtable中。

當(dāng)數(shù)據(jù)回復(fù)包達(dá)到NDN路由器時，需要從PIT中查詢數(shù)據(jù)請求Face列表，查詢過程分為3步：

1) 利用兩個哈希函數(shù)計算該數(shù)據(jù)回復(fù)包中名字的哈希值，分別為Hash0和Hash1；

2) 分別查詢Hash0和Hash1對應(yīng)的CBF和CBF中是否存在該名字，可能出現(xiàn)4種判斷結(jié)果：① CBF判斷存在，CBF判斷不存在；② CBF判斷不存在，CBF判斷存在；③ CBF和CBF判斷都存在；④ CBF和CBF判斷都不存在；

3) 根據(jù)上述4種判斷結(jié)果，對哈希表的查詢操作分別進(jìn)行如下處理：

① CBF判斷存在，CBF判斷不存在。進(jìn)入Hashtable中查詢數(shù)據(jù)回復(fù)包中名字對應(yīng)的其他信息，如果能查詢到該名字，則讀取數(shù)據(jù)請求Face列表進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)；如果未能查詢到該名字，說明CBF產(chǎn)生誤判，不做任何處理；

② CBF判斷不存在，CBF判斷存在。進(jìn)入Hashtable中查詢數(shù)據(jù)回復(fù)包中名字對應(yīng)的其他信息，如果能查詢到該名字，則讀取數(shù)據(jù)請求Face列表進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)；如果未能查詢到該名字，說明CBF產(chǎn)生誤判，不做任何處理；

③ CBF和CBF判斷都存在。進(jìn)入Hashtable中查詢數(shù)據(jù)回復(fù)包中名字對應(yīng)的其他信息，如果能查詢到該名字，則讀取數(shù)據(jù)請求Face列表進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，流程結(jié)束；如果未能查詢到該名字，說明CBF產(chǎn)生誤判，進(jìn)入Hashtable中查詢數(shù)據(jù)回復(fù)包中名字對應(yīng)的其他信息，如果能查詢到該名字，則讀取數(shù)據(jù)請求Face列表進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)；如果未能查詢到該名字，說明CBF產(chǎn)生誤判，不做任何處理；

④ CBF和CBF判斷都不存在。說明該數(shù)據(jù)回復(fù)包不是該NDN路由器請求的，直接丟棄該數(shù)據(jù)包，不做任何處理。特別針對泛洪攻擊，由于CBF的過濾作用，避免直接進(jìn)入位于片外存儲器中的Hashtable或Hashtable查詢，從而有效防止因泛洪攻擊造成的NDN路由器內(nèi)存耗盡和宕機(jī)。

2.2 HBF算法分析

本節(jié)主要對HBF算法空間復(fù)雜度和時間復(fù)雜度的影響因素進(jìn)行理論分析。時間復(fù)雜度主要是指名字查詢過程時對片內(nèi)存儲器中CBF的訪問次數(shù)和片外存儲器中哈希表的訪問次數(shù)，二者均受到CBF誤判率的影響。首先需分析HBF中多個CBF組合在一起后的誤判率。設(shè)定HBF中CBF與哈希表個數(shù)均為，名字最大個數(shù)為，每個CBF和哈希表保存名字的個數(shù)為=/。每個CBF具有個計數(shù)器和個哈希函數(shù)，每個計數(shù)器具有個比特。

1) 誤判率分析(假陽性)

HBF中，每個名字的2個哈希值對應(yīng)的2個CBF同時不出現(xiàn)假陽性時才不會產(chǎn)生誤判現(xiàn)象。根據(jù)文獻(xiàn)[15]，HBF誤判率的計算公式為：

2) 空間復(fù)雜度分析

HBF將CBF和哈希表分別部署在片內(nèi)和片外存儲器中，設(shè)定HBF總占用空間為HBF，CBF占用空間為CBF，哈希表占用空間為HT，F(xiàn)IB/CS/PIT每條記錄為Entry字節(jié)，內(nèi)存占用空間為：

從式(2)看出給定值，CBF只與名字個數(shù)有關(guān)，與名字自身長度無關(guān)，這極大壓縮了名字占用空間，保證片內(nèi)存儲器可容納更多名字個數(shù)。

3) 片內(nèi)存儲器訪問次數(shù)分析

以此類推，片內(nèi)存儲器的平均訪問次數(shù)CBF-2計算公式為：

從式(4)可看出，CBF-2與HBF片內(nèi)存儲器占用空間呈單調(diào)下降關(guān)系，即越大，CBF-2越低。在固定HBF片內(nèi)存儲器占用空間條件下，設(shè)定/=10，片內(nèi)存儲器的平均訪問次數(shù)CBF-2與參數(shù)、相關(guān)。

4) 片外存儲器訪問次數(shù)分析

哈希表(鏈地址)的裝填因子為，對于HBF，同一個名字查找可能要遍歷2個哈希表，需綜合2個哈希表來計算HBF總體平均查找長度(次數(shù))。存儲于HBF中有50%名字在第1個哈希表中查詢到結(jié)果后就退出查詢，不再進(jìn)入第2個哈希表進(jìn)行查詢；50%名字在第1個哈希表查找失敗后再次在第2個哈希表中查詢得到結(jié)果。使用CBF后，進(jìn)入哈希表查找名字個數(shù)為真正存儲于HBF中名字個數(shù)與CBF誤判名字個數(shù)之和，其訪問次數(shù)CBF-HT計算公式為：

未使用CBF過濾時，所有名字查找時都將直接訪問哈希表，其訪問次數(shù)HT計算公式為：

5) 總體訪問成本分析

未采用CBF直接訪問哈希表成本計算公式為：

表1 CostHT與CostHBF理論對比

根據(jù)式(4)、式(5)、式(7)可以看出，在選定片內(nèi)存儲器和片外存儲器后，HBF總體訪問成本CostHBF與/、、、等參數(shù)相關(guān)，相互關(guān)系如下：

① CostHBF與/是單調(diào)減的關(guān)系，即CostHBF隨著/增加而減小，但會增加CBF的占用空間；

② CostHBF與是單調(diào)增的關(guān)系，即CostHBF隨著減小而減小，路由器運行時間越長，會越??；

③ CostHBF與是單調(diào)增的關(guān)系，即CostHBF隨著減小而減小，但會增加哈希表的占用空間；

④ CostHBF與既有單調(diào)增的關(guān)系，也有單調(diào)減的關(guān)系，<0時，CostHBF與是單調(diào)減的關(guān)系，>0時，CostHBF與是單調(diào)增的關(guān)系。

通過上述關(guān)系分析，在固定占用空間的情況下，是決定CostHBF大小的關(guān)鍵參數(shù)，特別是0的選擇，這給工業(yè)界的推廣應(yīng)用提供了理論依據(jù)。

3 實驗評估

3.1 實驗方案及數(shù)據(jù)

實驗主要目標(biāo)是驗證理論分析正確性，找出最優(yōu)參數(shù)設(shè)置，優(yōu)化HBF總體訪問成本，降低訪問開銷，提高NDN數(shù)據(jù)包轉(zhuǎn)發(fā)速率。同時將HBF的訪問訪問成本與-left HTPIT對比分析。

實驗數(shù)據(jù)有兩個途徑。1) 從Blacklist[19]下載學(xué)術(shù)界廣泛使用的域名和URL集合，從URL解析出域名后并重新生成名字集；2) 利用文獻(xiàn)[20]開發(fā)的NDN數(shù)據(jù)生成工具NDNBench，以Blacklist下載的URL集合為種子，隨機(jī)生成多組名字集合。

實驗數(shù)據(jù)以Blacklist子目錄Port中URL集為種子，利用NDNBench生成50組查詢名字集，每個查詢集包括1 000 000個名字，然后分別抽取查詢集中0.1%、1%、10%的元素構(gòu)成插入名字集(即=0.001，=0.01，=0.1)。查詢集或插入集中名字對應(yīng)的其他字段信息隨機(jī)生成。

3.2 實驗結(jié)果分析

1) HBF實際總體訪問成本對比分析

根據(jù)上述實驗，計算HBF和直接訪問哈希表實際總體訪問成本(以1 000個名字為統(tǒng)計單位)，CostHT與CostHBF實際結(jié)果對比如表2所示。=0.1時，CostHBF約為CostHT的8.2%；隨著降低，CBF總體訪問成本降低更加明顯，=0.001時，CostHBF約為CostHT的2.1%。

表2 CostHT與CostHBF實際結(jié)果對比

2) HBF與-left HTPIT訪問次數(shù)及成本對比

-left HTPIT中參數(shù)(哈希表個數(shù))越大時，數(shù)據(jù)包的并發(fā)處理對哈希表的訪問效率就越高，但名字查找時需要遍歷個哈希表，片外存儲器的訪問次數(shù)就會大幅度上升。

HBF片內(nèi)存儲器和片外存儲器的訪問次數(shù)與其參數(shù)(CBF與哈希表的個數(shù))無關(guān)，當(dāng)取值越大時，數(shù)據(jù)包的并發(fā)處理時對哈希表的訪問效率就越高。HBF以犧牲片內(nèi)存儲器空間為代價，通過片內(nèi)存儲器中的CBF減少對片外存儲器中哈希表的無效訪問次數(shù)。根據(jù)文獻(xiàn)[15]可知，當(dāng)≥，CBF的誤判率(假陽性)CBF接近1，全部元素會被誤判，導(dǎo)致CBF失效，因此會有/>。一般最小值取2，因此當(dāng)/=3時，HBF占用最小的片內(nèi)存儲存儲器空間，此時代價最低，即每個名字消耗12 bits(1.5 byte)。

將具有最低片內(nèi)存儲空間的HBF與具有最低哈希表個數(shù)的-left HTPIT進(jìn)行對分析，如表3所示。

表3 HBF與d-left HTPIT訪問次數(shù)及訪問成本對比

從表3可以看出，HBF在占用最小片內(nèi)存儲空間情況下，其片外存儲器訪問次數(shù)和總體訪問成本約為-left HTPIT的25%。

將HBF的片內(nèi)存儲空間提高到/=10(每個名字消耗40 bits)后，再與-left HTPIT(=2)對比分析，其實驗結(jié)果如圖2、圖3所示。

圖2 片外存儲器訪問次數(shù)比較(r=0.001)

圖2可看出=2時，HBF片外存儲器訪問次數(shù)約為-left HTPIT的3.3%；=7時，HBF片外存儲器訪問次數(shù)約為-left HTPIT的1%。

圖3 總體訪問成本比較(r=0.001)

圖3可看出同-left HTPIT相比，盡管HBF增加了片內(nèi)存儲器的訪問次數(shù)，但總體訪問成本還是顯著降低，=2時，約為-left HTPIT的5%；=5時，約為-left HTPIT的2.5%。

4 結(jié)束語

本文提出了一種名為哈希布魯姆過濾器的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)查詢算法，該結(jié)構(gòu)通過CBF的定位與過濾作用，避免查找時對個哈希表的遍歷操作，大幅度減少對片外存儲器的訪問開銷，降低名字查找的總體訪問成本，提高名字查找速率，有效避免泛洪攻擊。本文對HBF總體訪問成本CostHBF與/、、、等參數(shù)關(guān)系進(jìn)行了系統(tǒng)理論分析和實驗驗證，為工業(yè)界應(yīng)用提供了設(shè)計依據(jù)。

同時通過與類似研究成果-left HTPIT對比，HBF在NDN名字查找過程的內(nèi)存訪問次數(shù)(片外存儲器)和總體訪問成本大幅度降低，在其占用最少片內(nèi)存儲器空間情況下(每個名字消耗12 bits)，片外存儲器訪問次數(shù)和總體訪問成本約為-left HTPIT的25%；當(dāng)其占用空間提高到每個名字消耗40 bits時，片外存儲器訪問次數(shù)約為-left HTPIT的1% (HBF中=7)。而這樣的比較結(jié)果還是在-left HTPIT中哈希表個數(shù)設(shè)為最小值時取得的，此時-left HTPIT中哈希表會成為數(shù)據(jù)包并發(fā)處理時資源訪問的瓶頸。為了解決此問題則需要提高哈希表個數(shù)，那么HBF在總體訪問成本的優(yōu)勢就會更加突出。

[1] 謝高崗, 張玉軍, 劉韻潔, 等. 未來互聯(lián)網(wǎng)體系結(jié)構(gòu)研究綜述[J]. 計算機(jī)學(xué)報, 2012, 35(6): 1109-1119.

XIE Gao-gang, ZHANG Yu-jun, LIU Yun-jie, et al. A survey on future internet architecture[J]. Chinese Journal of Computers, 2012, 35(6): 1109-1119.

[2] ZHANG L, ESTRIN D, JACOBSON V, et al. Named data networking (ndn) project. in Technical Report, NDN-0001, 2010[ EB/OL]. [2010-10-31]. http://www.named-data.net/.

[3] JACOBSON V, SMETTERS D K, THORNTON J D, et al. Networking named content[C]//Proceedings of International Conference on Emerging Networking Experiments and Technologies. Rome, Italy: IEEE, 2009: 1-12.

[4] 汪漪. 內(nèi)容中心網(wǎng)絡(luò)路由查找關(guān)鍵技術(shù)研究[D]. 北京: 清華大學(xué), 2013.

WANG Yi. Research on name lookup in named data networking[D]. Beijing: Tsinghua University, 2013.

[5] YUAN H, SONG T, CROWLEY P. Scalable NDN forwarding: Concepts, issues and principles[C]//Proceedings of International Conference on Computer Communication Networks. Munich, Germany: IEEE, 2012: 1-9.

[6] MATTEO V, DIEGO P, LEONARDO L .On the design and implementation of a wire-speed pending interest table[C]//Proceedings of IEEE International Workshop on Emerging Design Choices in Name-Oriented Networking. Turin, Italy: IEEE, 2013: 1-6.

[7] YUAN Hao-wei, CROWLEY P. Scalable pending interest table design: from principles to practice[C]//Proceedings of IEEE International Conference on Computer Communications. Toronto, Canada: IEEE, 2014: 2049-2057.

[8] WEI You, BERTRAND M, PATRICK T, et al. Realistic storage of pending requests in content-centric network routers[C]//Proceedings of the 1st IEEE International Conference on Communications in China: Communications QoS and Reliability. Beijing, China: IEEE, 2012: 121-125.

[9] WANG Yi, HE Ke-qiang, LIU Bin, et al. Scalable name lookup in NDN using effective name component encoding[C]//Proceedings of International Conference on Distributed Computing Systems. Macau, China:IEEE, 2012: 688-696.

[10] DAI H, LIU B, CHEN Y, et al. On pending interest table in named data networking[C]//Proceedings of ACM/IEEE Architectures for Networking and Communications Systems. Austin, Texas, USA: IEEE, 2012: 211-222.

[11] LI Z, BI J, WANG S. Compression of pending interest table with bloom filter in content centric network[C]// Proceedings of ACM International Conference on Future Internet Technologies. Seoul, Korea: ACM, 2012: 47.

[12] WEI You, BERTRAND M, PATRICK T, et al. DiPIT: a distributed bloom-filter based PIT table for CCN Nodes[C]//Proceedings of IEEE International Conference on Computer Communications and Networks. Munich, Germany: IEEE, 2012: 1-7

[13] WANG Yi, PAN Tian, LIU Bin, et al. NameFilter: Achieving fast name lookup with low memory cost via applying two-stage Bloom filters[C]//Proceedings of IEEE International Conference on Computer Communications, Mini-conference. Turin, Italy: IEEE, 2013: 95-99.

[14] BlOOM B. Space/time trade-offs in hash coding with a llowable errors[J]. Communications of the ACM, 1970, 13(7): 422-426.

[15] BRODER A, MITZENMACHER M. Network applications of bloom filters: a survey[J]. Internt Mathematics, 2005, 1(4): 485-509.

[16] SARANG D, PRAVEEN K, DAVID E T. Longest prefix matching using bloom filters[C]//Proceedings of ACM International Conference on the Applications, Technologies, Architectures, and Protocols for Computer Communication. Karlsruhe, Germany: ACM, 2006: 201-212.

[17] 嚴(yán)蔚敏, 吳偉明. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京: 清華大學(xué)出版社, 2011.

YAN Wei-min, WU Wei-ming. Data structure[M]. Beijing: Tsinghua University Press, 2011.

[18] PERINO M D, VARVELLO. A reality check for content contric networking[C]//ACM SIGCOMM Workshop on Information-Centric Networking. Toronto, Canada: ACM, 2011: 44-49.

[19] URLBLACKLIST. Blacklist data set[EB/OL]. [2014-09- 23]. http://www.urlblacklist. com/.

[20] ZHANG Ting, WANG Yi, LIU Bin, et al. NDNBench: a benchmark for named data networking lookup[C]// Proceedings of IEEE Global Communications Conference, incorporating the Global Internet Symposium. Atlanta, GA, USA: IEEE, 2013: 2152-2157.

編 輯 蔣 曉

Hash Bloom Filters for Name Lookup in Named Data Networking

LI Wei, ZHANG Da-fang, and XU Bing

(College of Computer Science and Electronics Engineering, Hunan University Changsha 410082)

To provide quick name lookup technique, the paper designs a Hash bloom filter (HBF). The HBF consists of g on-chip counter bloom filters (CBFs),on-chip counters andoff-chip Hash tables. Each Hash table is associated with a CBF and a counter. To reduce the false positive rate introduced by unbalanced name insertion in to CBFs, we propose two-Hash-choice algorithm which evenly disperses the FIB/CS/PIT entries intoHash tables and CBFs. Moreover, HBF has a good feature of parallel processing of data packet forwarding because HBF adopts multiple Hash tables and CBFs. Theoretical and simulated results demonstrate that HBF can achieve very efficient name lookup by well utilizing the on-chip memory through localization and filtering function of CBF. Therefore, the proposed HBF improves data packet forwarding rate and effectively avoids flooding attacks.

data packet forwarding rate; Hash bloom filter; named data networking; name lookup; two-Hash-choice algorithm

TP393

A

10.3969/j.issn.1001-0548.2017.05.016

2016-01-05；

2016-07-08

國家973項目(2012CB315805)；國家自然科學(xué)基金(61173167, 61472130)

李瑋(1972-)，男，博士，主要從事可信系統(tǒng)與網(wǎng)絡(luò)、大數(shù)據(jù)處理等方面的研究.