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

于明，王振安，王東菊

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

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

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

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

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

1 基本原理

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

1)集合元素的存儲。

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

2)元素的查詢。

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

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

圖1 基于Bloom濾波器的集合元素存儲過程示意圖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è)計

2.1 設(shè)計原理

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

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

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

圖3 IPv4前綴長度分布Fig.3 Distribution of the prefixes of IPv4 addresses

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

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

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

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

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

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

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

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

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

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

2.2.2 Bloom濾波器存儲信息的更新過程

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

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

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

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

2.3 性能分析

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

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

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

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

式中:Bl×f表示因濾波器的誤稱而對選路表進(jìn)行的無效探測次數(shù)，1表示成功探測。對于任意前綴長度的IP地址，路由查找過程需探測選路表的平均次數(shù)可表示為

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

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

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

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

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

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

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

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

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

3 實驗驗證

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

本文提出了一種基于Bloom濾波器的快速路由查找方法。該方法采取了2個措施以減少路由查找過程中對選路表的探測次數(shù)。1)建立了一個首字節(jié)索引表，用于減少需要并行查詢的Bloom濾波器的數(shù)量，以降低Bloom濾波器的誤稱率對查詢效率的影響。2)利用IP地址前綴長度分布的不均勻性對Bloom濾波器組的設(shè)置進(jìn)行了優(yōu)化，降低了路由查詢對濾波器總數(shù)的需求。此外，本文方法還將Bloom濾波器位向量中的每一位與一個計數(shù)器相關(guān)聯(lián)，以實現(xiàn)對路由更新的支持。實驗結(jié)果驗證了該方法的有效性及相關(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é)報，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］袁博，汪斌強，王志明.并行多流水綠色路由查找架構(gòu)和算法［J］.西安電子科技大學(xué)學(xué)報，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的高效浮動關(guān)鍵詞匹配算法［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.