李 瑋，張大方，徐 冰

?

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

李 瑋，張大方，徐 冰

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

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

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

為了解決TCP/IP體系結(jié)構(gòu)在路由擴(kuò)展性、動(dòng)態(tài)性、安全性、QoS、可靠性等方面日益突出的問(wèn)題[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ā)層的核心問(wèn)題，特別是FIB與PIT不僅需要遵循最長(zhǎng)前綴匹配(longest prefix matching, LPM)的規(guī)則進(jìn)行名字查找，而且需要在大規(guī)模的名字集合中實(shí)現(xiàn)快速查找和更新，以滿足路由器的傳輸速率。盡管傳統(tǒng)網(wǎng)絡(luò)體系中面向IP地址的最長(zhǎng)前綴匹配算法已經(jīng)非常成熟，但NDN命名特點(diǎn)使得名字查找比IP地址查找更加復(fù)雜；同時(shí)沒有上限的名字空間造成路由器中路由表項(xiàng)數(shù)過(guò)多，空間急劇膨脹，這給NDN中名字存儲(chǔ)和快速查找?guī)?lái)了巨大的挑戰(zhàn)。目前針對(duì)NDN的名字查找技術(shù)有4種思路，分別是TCAM、哈希表、多步長(zhǎng)字符特里樹(multi-bit character trie)、布魯姆過(guò)濾器(bloom filter, BF)。

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

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

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

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

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

1 相關(guān)工作

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

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

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

2 哈希布魯姆過(guò)濾器

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 HBF算法分析

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

1) 誤判率分析(假陽(yáng)性)

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

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

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

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

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

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

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

4) 片外存儲(chǔ)器訪問(wèn)次數(shù)分析

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

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

5) 總體訪問(wèn)成本分析

未采用CBF直接訪問(wèn)哈希表成本計(jì)算公式為：

表1 CostHT與CostHBF理論對(duì)比

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

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

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

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

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

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

3 實(shí)驗(yàn)評(píng)估

3.1 實(shí)驗(yàn)方案及數(shù)據(jù)

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

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

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

3.2 實(shí)驗(yàn)結(jié)果分析

1) HBF實(shí)際總體訪問(wèn)成本對(duì)比分析

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

表2 CostHT與CostHBF實(shí)際結(jié)果對(duì)比

2) HBF與-left HTPIT訪問(wèn)次數(shù)及成本對(duì)比

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

[1] 謝高崗, 張玉軍, 劉韻潔, 等. 未來(lái)互聯(lián)網(wǎng)體系結(jié)構(gòu)研究綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 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

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

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