命名數(shù)據(jù)網(wǎng)絡(luò)中基于多級(jí)計(jì)數(shù)Bloom過濾器的名字查找方法研究

侯　睿，吳婷婷

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

?

命名數(shù)據(jù)網(wǎng)絡(luò)中基于多級(jí)計(jì)數(shù)Bloom過濾器的名字查找方法研究

侯睿，吳婷婷*

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

針對(duì)目前NDN中大多數(shù)基于Bloom過濾器的名字查找方法僅考慮速率而忽略沖突概率的局限,提出了一種考慮名字沖突概率并基于多級(jí)計(jì)數(shù)Bloom過濾器的名字查找方法.該方法的實(shí)驗(yàn)結(jié)果表明：相對(duì)于目前廣泛研究的計(jì)數(shù)Bloom過濾器、哈希函數(shù)和d-left計(jì)數(shù)Bloom過濾器，所提方法能有效降低沖突概率.

Bloom過濾器；名字查找；命名數(shù)據(jù)網(wǎng)絡(luò)；最長(zhǎng)匹配前綴

隨著互聯(lián)網(wǎng)信息量的爆炸式增長(zhǎng)，用戶逐漸趨向于關(guān)注信息的內(nèi)容而不是其所處的地理位置.信息中心網(wǎng)絡(luò)(ICN)[1-2]以其通過信息內(nèi)容查找數(shù)據(jù)的方式受到世界各國(guó)研究者的關(guān)注，并被認(rèn)為是下一代計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)的典型代表，命名數(shù)據(jù)網(wǎng)絡(luò)(NDN)[3-4]是ICN的一種有效實(shí)現(xiàn)方式，目前得到廣泛研究.

NDN通過層次化命名方式，將數(shù)據(jù)名字分級(jí)標(biāo)識(shí)，類似于目前的統(tǒng)一資源定位符 (URL) 命名方案[5].針對(duì)NDN網(wǎng)絡(luò)架構(gòu)中固定長(zhǎng)度的前綴查找方法已有很多，文獻(xiàn)[6]中將NDN的名字不作層次化命名，看作扁平化命名，利用名字組件樹進(jìn)行查找.該方案降低了查找樹的深度，相對(duì)地加快了查找速度.但若使用該方法，不利于速度的提升；文獻(xiàn)[7]提出一種平行于NDN架構(gòu)的平行名字查詢(PNL)方案,該方案利用硬件并行加速了查找的過程,同時(shí)保持較低的內(nèi)存冗余和計(jì)算復(fù)雜度，然而該方案的內(nèi)存開銷較大；文獻(xiàn)[8]提出一種名字組件編碼(NCE)方案.此方案采用代碼分配機(jī)制和狀態(tài)轉(zhuǎn)換陣列兩個(gè)核心思想，與名字組件樹方法相比有效加快了其查找速率，但其代碼分配機(jī)制產(chǎn)生的沖突概率較大，且其運(yùn)行平臺(tái)的設(shè)計(jì)成本較大；文獻(xiàn)[9]提出一種名字濾波器方案，通過應(yīng)用兩個(gè)階段的計(jì)數(shù)Bloom過濾器(CBF)有效地將哈希計(jì)算和內(nèi)存訪問的次數(shù)從kN次減少到k次，因此相對(duì)地提高了查找速度.但依舊沒有解決由于哈希函數(shù)的沖突,導(dǎo)致CBF的效率受到?jīng)_突率的影響；此外文獻(xiàn)[10]提出一種新型Bloom過濾器方案d-left哈希函數(shù)的Bloom Filters(DLCBF)，在負(fù)載率的平衡性上進(jìn)行了一定程度的改進(jìn).

以上的研究?jī)H關(guān)注查找速度而忽略了沖突概率，本文提出一種基于多級(jí)計(jì)數(shù)Bloom過濾器(MLCBF)的名字查找方法，有效地降低了查找過程中名字的沖突概率.

1　最長(zhǎng)匹配前綴的查找

NDN中是以最長(zhǎng)匹配前綴原則實(shí)現(xiàn)名字匹配，如請(qǐng)求包的名字為K/X/Y/Z，此時(shí)路由表中包含K/X/Y/Z和K/X/Y，那么按照最長(zhǎng)匹配前綴原則與K/X/Y/Z匹配.在本文中，名字前綴根據(jù)其長(zhǎng)度分別映射進(jìn)不同長(zhǎng)度的Bloom過濾器中，通過查詢Bloom過濾器，名字的最長(zhǎng)匹配前綴被確定.這個(gè)階段采用的是One Memory Access Bloom Filters[11]使得一次查詢中內(nèi)存訪問的次數(shù)從k次(k是每個(gè)Bloom過濾器中hash函數(shù)的個(gè)數(shù))減到1次，其主要思想是把k個(gè)hash函數(shù)的結(jié)果映射為一段字符串，提高了基于散列的字符串性能，加快了Bloom過濾器在第一階段的操作.第一階段Bloom過濾器的映射流程結(jié)構(gòu)如圖1所示.

圖1　One Memory Access Bloom Filters映射流程圖Fig.1　The mapping flow chart of One Memory Access Bloom Filters

當(dāng)請(qǐng)求包需要被查詢的名字為/wuhan/scuec/2015/.../時(shí)，依次將各層次的名字按照長(zhǎng)度映射進(jìn)Bloom過濾器中，此方案會(huì)先從最長(zhǎng)長(zhǎng)度的過濾器中查找，若沒找到，則向相鄰且長(zhǎng)度較小的過濾器中查找,直到找到輸出最長(zhǎng)匹配前綴為止.

2　多級(jí)計(jì)數(shù)Bloom過濾器

MLCBF是采用哈希函數(shù)映射并且結(jié)合信息指紋來(lái)構(gòu)建計(jì)數(shù)型Bloom過濾器的方法,如圖2所示.該方案將存儲(chǔ)區(qū)分為d層(本文為了論述方便,按照d=4來(lái)劃分存儲(chǔ)區(qū)),每層記作LV1,LV2,LV3,LV4，每塊又依賴遞減率R分為不同數(shù)量但相同容量的塊.本文將每層中各個(gè)塊看作桶(bucket),從上到下記作BN1,BN2，…,BNn桶內(nèi)存儲(chǔ)H個(gè)元素.每個(gè)桶由標(biāo)簽、信息指紋、計(jì)數(shù)器和下一跳端口組成.每層桶的數(shù)量由固定的遞減率R(R<1)決定.設(shè)R0=1+R+R2+…+Rd-1，那么LV1桶的數(shù)量BN1=[n/(HR0)],第LVi桶的數(shù)量為BNi=[BNi-1R](i≥2) .例如,如圖2所示將存儲(chǔ)區(qū)劃分為4個(gè)層次,每層按照遞減率R=0.5劃分為若干個(gè)桶,每桶深度為8，即能存儲(chǔ)8個(gè)信息指紋.當(dāng)插入元素key時(shí),由 d個(gè)獨(dú)立的哈希函數(shù)計(jì)算元素key的哈希值，然后映射進(jìn)各個(gè)塊中的桶地址,分別記作 h1(e),h2(e),…,hd(e).然后將key插入到 BE1(h1(e)),BE2(h2(e)),…,BEd(hd(e))中負(fù)載最輕的那個(gè)桶中.如果存在多個(gè)負(fù)載最輕的桶,則選擇最上面層次的桶.遵循上述方法,可使得各個(gè)層上各個(gè)桶的負(fù)載率較為平均,所以該方案適用于大規(guī)模數(shù)據(jù)的存儲(chǔ)和查詢，除此之外也支持網(wǎng)址黑名單白名單功能.文獻(xiàn)[5]中的實(shí)驗(yàn)表明，與一般的哈希表查詢相比該方案獲得90.9%的內(nèi)存節(jié)省,且有效地提高了查找速率.以下為進(jìn)行插入和查詢?cè)貢r(shí)的算法.

Algorithm 1 Pseudo-code for insertion and search in MLCBF

FunctionMLCBF-INSERT(key)

ifMLCBF-SEARCH(key) then

fori←1 toDdo

pos←LVi[hi(key) modBNi]

forj←1 toHdo

ifBEpos.LB[j]=0 then

BEpos[j].fingerprint ←hf(key)

BEpos[j].CC←BEpos[j].CC+1

BEpos.LB[j]←1

return 1

return 0

FunctionMLCBF-SEARCH(key)

fori←1 toDdo

pos←LVi[hi(key)] modBNi

ifBEpos.LB≠0 then

forj←1 toHdo

ifBEpos.LB[J]=1 then

ifBEpos[J].fingerprint ≠hf(key) then

j←j+1

else return 1

elsej←j+1

return 0

圖2　MLCBF框架舉例(R=0.5)Fig.2　An example of MLCBF construction (R=0.5)

3　MLCBF沖突率

目前的哈希函數(shù)Bloom過濾器得到的哈希值分作兩個(gè)部分，高位部分用作隨機(jī)地址，低位部分留作信息指紋.但是這樣的哈希過程沖突率較高，且不能進(jìn)行插入刪除等操作，即無(wú)法處理變動(dòng)的集合，并且此時(shí)各個(gè)bucket的負(fù)載并不均衡.目前所提出的DLCBF與MLCBF主要區(qū)別在于它每一層桶的個(gè)數(shù)是相等的，而MLCBF是依賴固定的遞減率R來(lái)分配每一層桶的個(gè)數(shù)，那么在插入元素時(shí)，MLCBF的負(fù)載均衡率較高于DLCBF，所以在沖突率方面也是略小于DLCBF.

建立一個(gè)元素集合S={x1,x2,…,xn}， mn為計(jì)數(shù)器個(gè)數(shù)，N為所有元素個(gè)數(shù)，令η=mn/N (全局負(fù)載指數(shù))，F(xiàn)為元素多樣性即當(dāng)F越大時(shí)，元素重復(fù)率就越小.當(dāng)查找元素x,y時(shí)，其中x?S,y∈S，但存在hf(x)=hf(y)，此時(shí)便產(chǎn)生了沖突現(xiàn)象，由此造成錯(cuò)誤的定位是不能接受的.所以，盡管提高了查找速度，越高的d，H依舊會(huì)造成一定程度的沖突現(xiàn)象.對(duì)于MLCBF，其沖突率不會(huì)超過dH2-F，那么MLCBF的沖突率EP1可以表示為：

(1)

其中αj/η可以理解為該層的負(fù)載率(Load):

(2)

對(duì)于DLCBF:

(3)

當(dāng)lf≥8時(shí)，(3)式可近似為：

(4)

(5)

(6)

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

以公式(1)和公式(4)為依據(jù)，F(xiàn)(元素多樣性)為自變量進(jìn)行沖突率分析實(shí)驗(yàn).實(shí)驗(yàn)對(duì)目前廣泛研究的CBF、DLCBF和BloomHash與本文所提出的MLCBF方案沖突率進(jìn)行比較.當(dāng)η=1,2時(shí)，全局負(fù)載過高，計(jì)數(shù)器幾乎滿載，桶易溢出，實(shí)驗(yàn)數(shù)據(jù)不可靠，所以本次實(shí)驗(yàn)值考慮η=3,4,5,6四種情況,實(shí)驗(yàn)結(jié)果如圖3.

如圖3所示，當(dāng)η=5,6時(shí)，BloomHash、CBF的沖突率和MLCBF、DLCBF的沖突率差距較大，所以此時(shí)只比較后者兩種Bloom過濾器，由于CBF和BloomHash沖突概率不隨F變化，當(dāng)F增大時(shí)，MLCBF沖突率優(yōu)勢(shì)趨于明顯，當(dāng)F=14,15時(shí)MLCBF的沖突概率幾乎為0，DLCBF和MLCBF沖突概率平均減小率如表1所示.

表1DLCBF和MLCBF沖突概率平均減小率

Tab.1The average conflict probability decrease rate of DLCBF and MLCBF

方案沖突概率平均減小率/%η=3η=4η=5η=6DLCBF53.3771.1374.1892.32MLCBF78.6890.9895.5298.09

由表1可見，隨著F的增大，MLCBF沖突概率平均減小率大于DLCBF，說(shuō)明當(dāng)元素多樣性增大時(shí)，MLCBF能更有效地降低名字的沖突率.當(dāng)F>15時(shí)，元素基本都各不相同，重復(fù)概率低，沖突率無(wú)限趨于0，所以實(shí)驗(yàn)只考慮F≤15的沖突率情況.如圖3(d)所示， 當(dāng)η≥6時(shí)，兩種方案的沖突率都無(wú)限趨近于0且重合，所以η>6后的情況此時(shí)不用再討論.

5　結(jié)語(yǔ)

由于當(dāng)前互聯(lián)網(wǎng)的局限性，命名數(shù)據(jù)網(wǎng)絡(luò)成為了符合新興通訊需求的全新網(wǎng)絡(luò)架構(gòu)，是未來(lái)網(wǎng)絡(luò)架構(gòu)研究方案之一.本文利用MLCBF實(shí)現(xiàn)多層次化計(jì)數(shù)存儲(chǔ)名字，較便捷地插入和刪除元素.實(shí)驗(yàn)結(jié)果表明，相比其余三種方案，當(dāng)元素多樣性增長(zhǎng)時(shí)MLCBF因其多層次的優(yōu)勢(shì)使得各層次負(fù)載率趨于平衡，且能有效地降低名字的沖突概率.

(a) η=3　　　　　　　　　　 　 　　　　　　　　(b) η=4

(c) η=5　　　　　　　　　　 　 　　　　　　　　(d) η=6圖3　取不同值時(shí)四種方案的沖突率Fig.3　False positive rate of four paradigm

[1] 吳超,張堯?qū)W, 周悅芝, 等. 信息中心網(wǎng)絡(luò)發(fā)展研究綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(3): 455-471.

[2] 黃韜，劉江，霍如，等. 未來(lái)網(wǎng)絡(luò)體系架構(gòu)研究綜述[J].通信學(xué)報(bào)，2014，35(8)：184-197.

[3]Zhang L X,Estrin D,Burke J,et al.Named data networking(ndn). Project[R].California: PARC,2010．

[4]林嘯.以內(nèi)容為中心的新一代互聯(lián)網(wǎng)體系架構(gòu)研究[J].電信科學(xué),2010,5: 1-7．

[5]Feng Y H, Huang N F, Chen C H. An efficient caching mechanism for network-based URL filtering by multi-level counting bloom filters[C]//IEEE. International Conference on Communications (ICC).Kyoto: IEEE, 2011: 1-6.

[6]Park C, Hwang S. Fast URL lookup using URL prefix hash tree[EB/OL]. (2008-05-11).http://dbpia.co.kr/.

[7]Wang Y, Dai H, Jiang J, et al. Parallel name lookup for named data networking[C]//IEEE. Global Telecommunications Conference (GLOBECOM 2011).Houston: IEEE, 2011: 1-5.

[8]Wang Y, He K, Dai H, et al. Scalable name lookup in NDN using effective name component encoding[C]//IEEE. The 32nd IEEE International Conference on Distributed Computing Systems (ICDCS).Macau: IEEE, 2012: 688-697.

[9]Wang Y, Pan T, Mi Z, et al. NameFilter: Achieving fast name lookup with low memory cost via applying two-stage bloom filters[C]//IEEE. The 32nd IEEE International Conference on Computer Communications (INFOCOM).Turin: IEEE, 2013: 95-99.

[10]Bonomi F, Mitzenmacher M, Panigrahy R, et al. An improved construction for counting bloom filter[M]. Berlin: Springer, 2006: 684-69.

[11]Qiao Y, Li T, Chen S. One memory access bloom filters and their generalization[C]// IEEE. Berlin The 30nd IEEE International Conference on Computer Communications (INFOCOM). Shanghai: IEEE, 2011:1745-1753.

Named Lookup Based on Multi-Level Counting Bloom Filters for Named Data Network

HouRui,WuTingting

(College of Computer Science,South-Central University for Nationalities,Wuhan 430074,China)

In view of the present most of NDN name lookup method based on Bloom filter, only consider the rate and ignore the limitations of the conflict probability, proposes a consider name conflict probability and name lookup method based on Multi-level Counting Bloom Filters. The experiment results show that relative to the extensive research of Counting Bloom Filters, hash function and d - left Counting Bloom Filters, the proposed method can effectively reduce the collision probability.

Bloom filters;named lookup; named data networking; the longest prefix matching

2016-04-12*通訊作者吳婷婷，研究方向: 光網(wǎng)絡(luò)技術(shù)，E-mail: wtt_617@yeah.net

侯睿( 1977-) ，男，教授，博士，研究方向: 光網(wǎng)絡(luò)交換技術(shù)研究，E-mail: hourui@mail.scuec.edu.cn

武漢市科技計(jì)劃資助項(xiàng)目(2015010101010008，2013010501010125)，湖北省普通高等學(xué)?！皯?zhàn)略性新興(支柱)產(chǎn)業(yè)人才培養(yǎng)計(jì)劃”資助項(xiàng)目

TP393

A

1672-4321(2016)03-0107-04