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

于明，王振安，王東菊

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

互聯網應用的快速發展給路由器技術帶來了極大的挑戰，如何提高路由器的轉發速度已成為下一代網絡技術的研究熱點［1］。在影響路由器報文轉發速度的眾多因素中，路由查找方法的設計是極為關鍵的一個環節［2］。

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

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

綜上可見，對基于Bloom濾波器的路由查找方法而言，提高其查找性能的主要目標是減少對選路表的探測次數，而改進的主要方向則是減少Bloom濾波器的數量。基于此，本文提出了一種快速的路由查找方法。

1 基本原理

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

1)集合元素的存儲。

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

2)元素的查詢。

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

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

圖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 快速路由查找方法設計

2.1 設計原理

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

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

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

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

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

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

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

2.2 關鍵處理過程

2.2.1 轉發路由的查找過程

轉發路由的查詢過程主要依據首字節索引表、Bloom濾波器組和選路表完成報文轉發操作。圖4給出了轉發路由查找過程的流程框圖。

圖4 轉發路由查找過程的流程框圖Fig.4 The flowchart of searching operations

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

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

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

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

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

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

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

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

2.3 性能分析

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

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

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

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

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

在所有濾波器均出現誤稱的最壞情形下，執行路由查找所需的選路表最大探測次數Emax為

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

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

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

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

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

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

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

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

3 實驗驗證

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

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

因此選擇在軟件實現中設置12個哈希函數。

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

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

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

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

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

根據表2可以得到如下結論:

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

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

4 結束語

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

［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］.通信學報，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］袁博，汪斌強，王志明.并行多流水綠色路由查找架構和算法［J］.西安電子科技大學學報，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的高效浮動關鍵詞匹配算法［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.