基于Bloom濾波器的快速路由查找方法

于明，王振安，王東菊

(大連理工大學(xué)信息與通信工程學(xué)院，遼寧大連116024)

互聯(lián)網(wǎng)應(yīng)用的快速發(fā)展給路由器技術(shù)帶來(lái)了極大的挑戰(zhàn)，如何提高路由器的轉(zhuǎn)發(fā)速度已成為下一代網(wǎng)絡(luò)技術(shù)的研究熱點(diǎn)［1］。在影響路由器報(bào)文轉(zhuǎn)發(fā)速度的眾多因素中，路由查找方法的設(shè)計(jì)是極為關(guān)鍵的一個(gè)環(huán)節(jié)［2］。

相對(duì)于傳統(tǒng)的路由查找方法，如基于Trie樹(shù)的路由查找方法、基于HASH的路由查找方法和基于內(nèi)容可尋址存儲(chǔ)器(content addressable memory，CAM)的硬件實(shí)現(xiàn)方法等［3］，基于Bloom濾波器的路由查找方法出現(xiàn)相對(duì)較晚，但其在查找時(shí)間和存儲(chǔ)空間方面的優(yōu)異性能卻引起了研究人員的廣泛關(guān)注。2003年，Sarang.D等首次將Bloom濾波器引入到路由查找中［4］，將不同長(zhǎng)度的IP地址前綴存儲(chǔ)在不同的Bloom濾波器中，待查詢的IP地址并行輸入到所有Bloom濾波器中，并根據(jù)濾波器的查詢結(jié)果探測(cè)相應(yīng)的選路表，以確定報(bào)文轉(zhuǎn)發(fā)的下一跳信息。實(shí)驗(yàn)結(jié)果表明，該方法在查找時(shí)間和存儲(chǔ)空間方面較之傳統(tǒng)的路由查找方法有了較大提升。其不足之處是［5］:1)選路表的探測(cè)次數(shù)與Bloom濾波器的個(gè)數(shù)直接相關(guān)，當(dāng)出現(xiàn)誤稱的濾波器增多時(shí)，無(wú)效探測(cè)次數(shù)會(huì)隨之增多，導(dǎo)致路由查找時(shí)間增長(zhǎng);2)不同長(zhǎng)度的地址前綴對(duì)應(yīng)的選路表大小不均，無(wú)法保證路由查找性能的最優(yōu)化。

為了解決上述問(wèn)題，Haoyu.S等提出了一種基于分布式Bloom濾波器結(jié)構(gòu)的路由查找方法［6］，該方法是將一個(gè)完整的Bloom濾波器分成k個(gè)大小相同的子部分，并將哈希函數(shù)重新分組，每組中哈希函數(shù)的數(shù)量與前綴長(zhǎng)度的數(shù)量相對(duì)應(yīng)。這樣既能減少Bloom濾波器的數(shù)量，又能避免前綴長(zhǎng)度分布不均的問(wèn)題。不過(guò)，該方法結(jié)構(gòu)復(fù)雜，且不同長(zhǎng)度的前綴需要不同的哈希函數(shù)，而要找到大量相互獨(dú)立且性能較好的哈希函數(shù)目前還是很困難的［7］。李鯤鵬等采用前綴擴(kuò)展的方法來(lái)減少Bloom濾波器的個(gè)數(shù)［8］，但前綴擴(kuò)展會(huì)擴(kuò)大選路表，使單次選路表的探測(cè)時(shí)間大幅增加，降低了查找速度。

綜上可見(jiàn)，對(duì)基于Bloom濾波器的路由查找方法而言，提高其查找性能的主要目標(biāo)是減少對(duì)選路表的探測(cè)次數(shù)，而改進(jìn)的主要方向則是減少Bloom濾波器的數(shù)量。基于此，本文提出了一種快速的路由查找方法。

1 基本原理

Bloom濾波器是一種高效的數(shù)據(jù)結(jié)構(gòu)，目前已在文本檢索、正則表達(dá)式匹配和網(wǎng)絡(luò)資源共享等領(lǐng)域得到了廣泛應(yīng)用。Bloom濾波器的應(yīng)用涉及到2個(gè)關(guān)鍵結(jié)構(gòu):1)一個(gè)長(zhǎng)為m比特的位向量V，用于存儲(chǔ)集合元素的映射信息;2)k個(gè)相互獨(dú)立的哈希函數(shù)h1，h2，…，hk(1≤i≤k)，用于將集合元素映射到位向量V中。Bloom濾波器的基本應(yīng)用過(guò)程包括集合元素的存儲(chǔ)和元素查詢2個(gè)關(guān)鍵步驟，其執(zhí)行過(guò)程如下。

1)集合元素的存儲(chǔ)。

首先，對(duì)向量V進(jìn)行初始化，將V中各比特位全部置零。然后，計(jì)算集合元素xi的k個(gè)哈希值h1(xi)，h2(xi)，…，hk(xi)。最后，根據(jù)計(jì)算出的哈希值將位向量V中對(duì)應(yīng)的比特位置1，即執(zhí)行操作V［h1(xi)］=V［h2(xi)］=…=V［hk(xi)］=1。若V中的某個(gè)比特位在執(zhí)行映射之前已經(jīng)置1，則該位在執(zhí)行映射時(shí)不做任何變化。圖1給出了利用Bloom濾波器存儲(chǔ)集合元素的原理示意圖。

2)元素的查詢。

對(duì)任一元素y，利用Bloom濾波器查詢其是否屬于集合 V時(shí)，首先要計(jì)算y的哈希值h1(y)，h2(y)，…，hk(y)，然后檢查位向量V中對(duì)應(yīng)比特位是否滿足 V［h1(y)］=V［h2(y)］=…=V［hk(y)］=1。若不滿足，則y必不在集合V中;若全為1，則判斷y屬于集合V。不過(guò)，對(duì)于后一種查詢結(jié)果，有可能出現(xiàn)元素y被誤判為屬于集合X的情況，此時(shí)，稱Bloom濾波器查詢發(fā)生了假陽(yáng)性誤稱［9］，簡(jiǎn)稱誤稱。

各類基于Bloom濾波器的路由查找方法的基本原理是:首先將路由表中所有IP地址的前綴按長(zhǎng)度進(jìn)行分類，每一個(gè)前綴長(zhǎng)度對(duì)應(yīng)設(shè)置一個(gè)Bloom濾波器，用于存儲(chǔ)和查詢?cè)撻L(zhǎng)度下各IP地址的前綴信息，從而形成一個(gè)Bloom濾波器組;然后，將轉(zhuǎn)發(fā)報(bào)文的目的IP地址并行輸入到各Bloom濾波器中進(jìn)行查詢，查詢結(jié)果被存儲(chǔ)到一個(gè)匹配向量中;最后，根據(jù)匹配向量各比特位的取值情況探測(cè)選路表，得到下一跳地址。圖2給出了基于Bloom濾波器進(jìn)行路由查找的原理框圖。

圖1 基于Bloom濾波器的集合元素存儲(chǔ)過(guò)程示意圖Fig.1 Inserting an element to the Bloom filter

圖2 基于Bloom濾波器路由查找的流程框圖Fig.2 The flowchart of IP lookups based on Bloom filter algorithm

2 快速路由查找方法設(shè)計(jì)

2.1 設(shè)計(jì)原理

本文所提出的快速路由查找方法的核心架構(gòu)包括一張根據(jù)路由表信息構(gòu)建的首字節(jié)索引表、一組用于查詢不同長(zhǎng)度前綴的Bloom濾波器以及一組以IP地址前綴為索引的下一跳路由選路表，其設(shè)計(jì)原理如下。

首先，由于Bloom濾波器在判斷元素是否屬于已知集合時(shí)存在一定的誤稱率，所以，在設(shè)計(jì)路由查找方法時(shí)需要減少對(duì)Bloom濾波器的查詢?，F(xiàn)有的基于Bloom濾波器的路由查找方法都是直接將目的IP地址并行輸入到所有可能的前綴長(zhǎng)度所對(duì)應(yīng)的Bloom濾波器中進(jìn)行查詢，而本文方法則預(yù)先根據(jù)已知的路由表信息設(shè)置了一張首字節(jié)索引表，該表的數(shù)據(jù)結(jié)構(gòu)為{首字節(jié)，前綴長(zhǎng)度1，前綴長(zhǎng)度2，…，前綴長(zhǎng)度n}。在執(zhí)行Bloom濾波器查詢之前，首先提取轉(zhuǎn)發(fā)IP地址的首字節(jié)，并在首字節(jié)索引表中查找是否有對(duì)應(yīng)的表項(xiàng)。若沒(méi)有，則直接將該報(bào)文發(fā)送到默認(rèn)端口;若有，則提取該首字節(jié)對(duì)應(yīng)的所有可能的前綴長(zhǎng)度，并將一個(gè)長(zhǎng)度為32 bit的位向量V1中的相應(yīng)比特位進(jìn)行置位。之后，只需要根據(jù)V1中各比特位的置位情況查詢相關(guān)長(zhǎng)度所對(duì)應(yīng)的Bloom濾波器即可。這一措施的實(shí)施可以有效地減少對(duì)Bloom濾波器的查詢數(shù)量。

其次，本文方法還從Bloom濾波器組的優(yōu)化入手減少Bloom濾波器的數(shù)量。常規(guī)Bloom濾波器組的設(shè)計(jì)方式都是每個(gè)可能的前綴長(zhǎng)度對(duì)應(yīng)一個(gè)Bloom濾波器，因而原則上需要近30個(gè)Bloom濾波器。而由亞太互聯(lián)網(wǎng)絡(luò)信息中心給出的路由表地址分析報(bào)告 (http://bgp.potaroo.net/as2.0/bgp-active.html)中的數(shù)據(jù)可以看出，對(duì)于采用無(wú)類域間路由的IPv4地址而言，長(zhǎng)度小于8 bit、長(zhǎng)度為31 bit和32 bit的前綴是不存在的，絕大多數(shù)的前綴長(zhǎng)度集中在13～24 bit。圖3在亞太互聯(lián)網(wǎng)絡(luò)信息中心報(bào)告的基礎(chǔ)上給出了相關(guān)結(jié)論的圖示結(jié)果，從中可以看出IPv4地址前綴長(zhǎng)度分布的不均勻性。

圖3 IPv4前綴長(zhǎng)度分布Fig.3 Distribution of the prefixes of IPv4 addresses

基于這一特性，本文方法在設(shè)計(jì)中使部分前綴長(zhǎng)度共用一個(gè)Bloom濾波器，從而減少了Bloom濾波器的數(shù)量。具體的實(shí)施方案為:前綴長(zhǎng)度為8～14 bit的前綴信息存儲(chǔ)在1個(gè)Bloom濾波器中;前綴長(zhǎng)度為15～24 bit的前綴信息分別存儲(chǔ)在10個(gè)不同的Bloom濾波器中;前綴長(zhǎng)度為25～30 bit的前綴信息存儲(chǔ)在另外的1個(gè)Bloom濾波器中。所以，本文方法中共采用了12個(gè)Bloom濾波器。這一設(shè)計(jì)方式既可以平衡Bloom濾波器間的負(fù)載，又可以在減少Bloom濾波器個(gè)數(shù)的同時(shí)，不至于使選路表的規(guī)模過(guò)大，從而減小了因縮減Bloom濾波器的個(gè)數(shù)而對(duì)單次選路表探測(cè)時(shí)間的影響。

最后，由于路由表在更新過(guò)程中需要增添或刪除某些地址信息，而標(biāo)準(zhǔn)的Bloom濾波器卻并不支持元素的刪除操作。因此，為了更好地支持路由表的更新，本文借鑒了計(jì)數(shù)型Bloom濾波器的設(shè)計(jì)思想［10］，采用了具有計(jì)數(shù)功能的基本Bloom濾波器，其特征是將基本Bloom濾波器位向量中的比特位各自與1個(gè)計(jì)數(shù)器相關(guān)聯(lián)，若將這些計(jì)數(shù)器記為C(j)，0≤j≤m-1，則這種改進(jìn)型Bloom濾波器的存儲(chǔ)和查詢操作可歸納為:1)添加元素xi:C［h1(xi)］=C［h1(xi)］+1，i=1，2，…，k;2)刪 除 元 素xi:C［h1(xi)］=C［h1(xi)］-1，i=1，2，…，k。

需要指出的是，由于計(jì)數(shù)器需要占用較大的存儲(chǔ)空間，為了減少對(duì)嵌入式內(nèi)存的需求，可采用由獨(dú)立控制器控制的計(jì)數(shù)器，并建議在具體實(shí)現(xiàn)時(shí)將其置于路由器芯片外的存儲(chǔ)器中。

2.2 關(guān)鍵處理過(guò)程

2.2.1 轉(zhuǎn)發(fā)路由的查找過(guò)程

轉(zhuǎn)發(fā)路由的查詢過(guò)程主要依據(jù)首字節(jié)索引表、Bloom濾波器組和選路表完成報(bào)文轉(zhuǎn)發(fā)操作。圖4給出了轉(zhuǎn)發(fā)路由查找過(guò)程的流程框圖。

圖4 轉(zhuǎn)發(fā)路由查找過(guò)程的流程框圖Fig.4 The flowchart of searching operations

首先，提取目的IP地址的首字節(jié)，在首字節(jié)索引表中查找是否有對(duì)應(yīng)的表項(xiàng)，并將查找結(jié)果輸出到匹配向量V1。若V1為零向量，說(shuō)明首字節(jié)索引表中沒(méi)有該IP地址的首字節(jié)所對(duì)應(yīng)的表項(xiàng)，該報(bào)文將被發(fā)往默認(rèn)端口;反之，則根據(jù)V1中各比特位的置位情況查找代表對(duì)應(yīng)長(zhǎng)度前綴的Bloom濾波器。

然后，將對(duì)Bloom濾波器的查找結(jié)果分為匹配(置1)或者不匹配(置0)2種情況，并記錄到匹配向量V2中。

最后，根據(jù)V2的取值情況探測(cè)選路表。若V2為零向量，說(shuō)明Bloom濾波器匹配失敗，即目的IP地址對(duì)應(yīng)的前綴不在選路表中，待轉(zhuǎn)發(fā)報(bào)文被發(fā)送至默認(rèn)端口;若V2不為零向量，說(shuō)明至少有1個(gè)Bloom濾波器匹配成功，可依據(jù)最長(zhǎng)前綴匹配的原則，根據(jù)V2的置位情況從較長(zhǎng)前綴的選路表開(kāi)始探測(cè)。若某次探測(cè)成功，則提取下一跳地址并轉(zhuǎn)發(fā)數(shù)據(jù)包;若全部探測(cè)均以失敗告終，說(shuō)明基于Bloom濾波器的查詢出現(xiàn)誤稱，待轉(zhuǎn)發(fā)報(bào)文被發(fā)送至默認(rèn)端口。

2.2.2 Bloom濾波器存儲(chǔ)信息的更新過(guò)程

為了支持路由表更新，本文方法中采用了一種具有計(jì)數(shù)器的改進(jìn)型Bloom濾波器。圖5給出了本文方法中Bloom濾波器存儲(chǔ)信息更新過(guò)程的流程圖。

圖5 Bloom濾波器存儲(chǔ)信息更新過(guò)程的流程圖Fig.5 The flowchart of element updating operations

當(dāng)需要添加一個(gè)新的前綴信息時(shí)，首先根據(jù)其長(zhǎng)度對(duì)Bloom濾波器相應(yīng)的計(jì)數(shù)器進(jìn)行元素添加操作。若更新后計(jì)數(shù)器的值為1，則必須同時(shí)將Bloom濾波器位向量中相應(yīng)的比特位進(jìn)行置位，否則，不再做任何變化。類似的，當(dāng)需要?jiǎng)h除一個(gè)前綴信息時(shí)，首先對(duì)Bloom濾波器相應(yīng)的計(jì)數(shù)器進(jìn)行元素刪除操作。若更新后計(jì)數(shù)器的值為0，則必須同時(shí)將Bloom濾波器位向量中相應(yīng)的比特位進(jìn)行置零，否則，不再做任何變化。

需要指出的是，在完成Bloom濾波器的更新操作后，還要更新相應(yīng)的選路表和首字節(jié)索引表，以確保路由查找的準(zhǔn)確性。

2.3 性能分析

時(shí)間復(fù)雜度是目前衡量基于Bloom濾波器的路由查找方法性能的主要指標(biāo)，影響時(shí)間復(fù)雜度的因素有2個(gè):選路表的大小和探測(cè)選路表的次數(shù)。在其他條件一定的情況下，選路表越小，單次探測(cè)時(shí)間就越短;探測(cè)次數(shù)越少，查找時(shí)間就越短。但是，對(duì)于同一地址集合而言，在基于Bloom濾波器的各種查找方法中，每一前綴長(zhǎng)度所對(duì)應(yīng)的選路表的大小都是相同的，因此，不同查找方法的時(shí)間復(fù)雜度主要由選路表的探測(cè)次數(shù)決定。

文獻(xiàn)［4］指出，假設(shè)單個(gè)Bloom濾波器的位向量大小為mi，存儲(chǔ)條目的總數(shù)為ni，則單個(gè)濾波器的最小誤稱率fi與該濾波器的哈希函數(shù)數(shù)量ki之間的關(guān)系式為［4］

在實(shí)際應(yīng)用中，濾波器組中各濾波器一般都設(shè)置為具有相同的位向量大小和哈希函數(shù)，但卻可能具有不同的存儲(chǔ)條目數(shù)，因此，各濾波器的誤稱率未必都會(huì)取得最優(yōu)值。前文指出，本文方法依據(jù)IP地址前綴分布的不均勻性對(duì)濾波器的數(shù)量進(jìn)行了優(yōu)化，減小了各濾波器間存儲(chǔ)條目的不均衡性，從而保證了各濾波器具有相近的誤稱率。為了便于分析，本文方法中假設(shè)各濾波器具有相同的誤稱率f。

由方法的設(shè)計(jì)原理可以看出，選路表的探測(cè)次數(shù)與匹配向量V1和V2密切相關(guān)。假設(shè)需要對(duì)一個(gè)前綴長(zhǎng)度為l的IP地址進(jìn)行轉(zhuǎn)發(fā)，設(shè):1)由V1決定應(yīng)查詢的Bloom濾波器個(gè)數(shù)為B;2)進(jìn)行選路表探測(cè)前需檢查匹配向量V2中前綴長(zhǎng)度大于l的濾波器的個(gè)數(shù)為Bl。則為了匹配前綴長(zhǎng)度為l的IP地址，路由查找過(guò)程中需探測(cè)選路表的平均次數(shù)El可表示為

式中:Bl×f表示因?yàn)V波器的誤稱而對(duì)選路表進(jìn)行的無(wú)效探測(cè)次數(shù)，1表示成功探測(cè)。對(duì)于任意前綴長(zhǎng)度的IP地址，路由查找過(guò)程需探測(cè)選路表的平均次數(shù)可表示為

在所有濾波器均出現(xiàn)誤稱的最壞情形下，執(zhí)行路由查找所需的選路表最大探測(cè)次數(shù)Emax為

基于上述分析，可以從以下3個(gè)方面來(lái)說(shuō)明本文方法與D.Sarang［4］、S.Haoyu 等［6］提出的同類方法相比所具有的的性能優(yōu)勢(shì):

1)同類方法中Bloom濾波器的平均數(shù)量均在20～30個(gè);本文方法則根據(jù)IP地址前綴長(zhǎng)度的不均勻分布特性使部分長(zhǎng)度的前綴共用一個(gè)濾波器，將濾波器的總數(shù)B縮減為12個(gè)，當(dāng)Bl服從［0，12］間的均勻分布時(shí)，路由查找過(guò)程需探測(cè)選路表的平均次數(shù)可表示

最壞情形下選路表的最大探測(cè)次數(shù)Emax為

2)同類方法在進(jìn)行地址查詢時(shí)，都是直接將目的IP地址并行輸入到所有Bloom濾波器中，查詢計(jì)算量大且平均誤稱率高;本文方法在執(zhí)行濾波器查詢之前首先將待查地址通過(guò)首字節(jié)索引表進(jìn)行預(yù)過(guò)濾，以減少需要查詢的濾波器的個(gè)數(shù)，從而有助于降低查詢的誤稱率。

3)同類方法中不同濾波器所存儲(chǔ)的前綴條目的數(shù)量具有不均衡性，因而濾波器間的誤稱率差別較大，整個(gè)濾波器組的平均誤稱率fs較高;而本文方法則通過(guò)對(duì)濾波器數(shù)量的優(yōu)化減小了各濾波器存儲(chǔ)條目的不均衡性，使各濾波器具有相近的誤稱率，降低了整個(gè)濾波器組的平均誤稱率f。

表1對(duì)比了本文方法較之同類方法在性能方面的改善情況。

表1 本文方法與同類方法的性能比較Table 1 Performence comparisons between the proposed method and other similar methods

需要說(shuō)明的是，本文方法中首字節(jié)索引表的引入必然會(huì)增加系統(tǒng)實(shí)現(xiàn)的復(fù)雜度，但索引查詢過(guò)程僅涉及簡(jiǎn)單的二進(jìn)制“與”操作和判斷操作，實(shí)現(xiàn)并不困難。不過(guò)，當(dāng)被查詢地址的首字節(jié)對(duì)應(yīng)的前綴索引數(shù)量較多時(shí)，首字節(jié)索引方式較之并行查詢的優(yōu)勢(shì)會(huì)縮小。另外，對(duì)于前綴長(zhǎng)度為8～14 bit及25～30 bit的地址查詢而言，濾波器數(shù)量的減少會(huì)使其對(duì)應(yīng)的路由表規(guī)模有所增大，單次探測(cè)時(shí)間會(huì)有所增加，當(dāng)這類地址的數(shù)量較多時(shí)(實(shí)際應(yīng)用中這種情況出現(xiàn)的概率很低，見(jiàn)圖3)，查詢性能可能會(huì)低于同類方法。

3 實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證本文方法的有效性及相關(guān)性能分析的正確性，本文在Eclipse開(kāi)發(fā)平臺(tái)上用Java編寫(xiě)了本文方法的測(cè)試代碼，并采用由中國(guó)網(wǎng)通、中國(guó)電信和中國(guó)聯(lián)通等公司提供的2011年的路由數(shù)據(jù)進(jìn)行了驗(yàn)證，該路由數(shù)據(jù)集中共有250 000條不同前綴長(zhǎng)度的轉(zhuǎn)發(fā)路由。此外，軟件中為Bloom濾波器組分配的用于位向量的內(nèi)存大小為4 Mbit。根據(jù)前述性能分析的結(jié)果，實(shí)驗(yàn)前首先對(duì)相關(guān)指標(biāo)進(jìn)行了理論計(jì)算，計(jì)算結(jié)果如下:

1)為了使各濾波器的誤稱率接近最優(yōu)值，根據(jù)式(1)和式(2)計(jì)算出哈希函數(shù)數(shù)量的估值為

因此選擇在軟件實(shí)現(xiàn)中設(shè)置12個(gè)哈希函數(shù)。

2)根據(jù)式(2)估算出各濾波器最低誤稱率的理論值為

3)根據(jù)式(5)計(jì)算出路由查找過(guò)程中需探測(cè)選路表的平均次數(shù)≈ 1.001 9。

4)根據(jù)式(6)計(jì)算出最壞情形下執(zhí)行路由查找所需的選路表最大探測(cè)次數(shù)Emax=1.003 8。

實(shí)驗(yàn)中對(duì)數(shù)據(jù)集里每一條IP地址都進(jìn)行了查詢測(cè)試，并在輸出結(jié)果中記錄了相關(guān)的Bl值和對(duì)應(yīng)的選路表平均探測(cè)次數(shù)El，然后將相同Bl下對(duì)應(yīng)的El進(jìn)行了算術(shù)平均處理，作為對(duì)應(yīng)于Bl的平均探測(cè)次數(shù)值，相關(guān)結(jié)果如表2所示。

表2 選路表平均探測(cè)次數(shù)的實(shí)驗(yàn)結(jié)果Table 2 Experimental results of the averaged number of times to probe the HASH tables for each IP lookup

根據(jù)表2可以得到如下結(jié)論:

1)對(duì)表1中測(cè)得的13個(gè)El值做算術(shù)平均，得到，該結(jié)果與理論計(jì)算結(jié)果相符。

3)實(shí)驗(yàn)結(jié)果中El的最大值為1.003 788 605，而根據(jù)式(6)得出的最壞情形下執(zhí)行路由查找所需的選路表最大探測(cè)次數(shù)Emax=1.003 8，從而驗(yàn)證了式(6)的正確性。

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

本文提出了一種基于Bloom濾波器的快速路由查找方法。該方法采取了2個(gè)措施以減少路由查找過(guò)程中對(duì)選路表的探測(cè)次數(shù)。1)建立了一個(gè)首字節(jié)索引表，用于減少需要并行查詢的Bloom濾波器的數(shù)量，以降低Bloom濾波器的誤稱率對(duì)查詢效率的影響。2)利用IP地址前綴長(zhǎng)度分布的不均勻性對(duì)Bloom濾波器組的設(shè)置進(jìn)行了優(yōu)化，降低了路由查詢對(duì)濾波器總數(shù)的需求。此外，本文方法還將Bloom濾波器位向量中的每一位與一個(gè)計(jì)數(shù)器相關(guān)聯(lián)，以實(shí)現(xiàn)對(duì)路由更新的支持。實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法的有效性及相關(guān)性能分析的正確性。

［1］NIU Yun，WU Liji，ZHANG Xiangmin.An IPsec accelerator design for a 10Gbps in-line security network processor［J］.Journal of Computers(Finland)，2013，8(2):319-325.

［2］胥小波，鄭康鋒，李丹，等.基于并行BP神經(jīng)網(wǎng)絡(luò)的路由查找算法［J］.通信學(xué)報(bào)，2012，33(2):61-68.XU Xiaobo，ZHENG Kangfeng，LI Dan，et al.Routing lookup algorithm based on parallel BP neural network ［J］.Journal of Communications，2012，33(2):61-68.

［3］袁博，汪斌強(qiáng)，王志明.并行多流水綠色路由查找架構(gòu)和算法［J］.西安電子科技大學(xué)學(xué)報(bào)，2012，39(2):145-152.YUAN Bo，WANG Binqiang，WANG Zhiming.Green IP lookup architecture and algorithm based on the parallel multi-pipeline［J］.Journal of Xidian University，2012，39(2):145-152.

［4］SARANG D，PRAVEEN K，TAYLOR D E.Longest prefix matching using bloom filters［J］.IEEE/ACM Transactions on Networking，2006，14(2):397-409.

［5］LIM Hyesook，LIM Kyuhee，LEE Nara，et al.On adding Bloom filters to longest prefix matching algorithms［J］.IEEE Transactions on Computers，2014，63(2):411-423.

［6］SONG Haoyu，KODIALAM M，HAO Fang，et al.Building scalable virtual routers with trie braiding［C］ //Proceedings of IEEE INFOCOM 2010.San Diego，USA，2010:14-19.

［7］LUO Layong，XIE Gaogang，XIE Yingke，et al.A hybrid hardware architecture for high speed IP lookups and fast route updates［J］.IEEE/ACM Transactions on Networking，2014，22(3):957-969.

［8］李鯤鵬，蘭巨龍.基于TCAM的高效浮動(dòng)關(guān)鍵詞匹配算法［J］.計(jì)算機(jī)工程，2012，38(4):269-274.LI Kunpeng，LAN Julong.Efficient unfixed keywords matching algorithm based on TCAM［J］.Computer Engineering，2012，38(4):269-274.

［9］GUO Deke，LIU Yunhao，LI Xiangyang，et al.False negative problem of counting Bloom filter［J］.IEEE Transactions on Knowledge and Data Engineering，2010，22(5):651-664.

［10］ROTHENBERG C E，MACAPUNA C A B，VERDI F L，et al.The deletable Bloom filter:a new member of the Bloom family［J］.IEEE Communications Letters，2010，14(6):557-559.