王 乾，喬廬峰，陳慶華

（陸軍工程大學(xué) 通信工程學(xué)院，江蘇 南京 210001）

0 引言

近年來IPv4 地址逐漸被耗盡，無類域間路由（CIDR）被提出用來緩解地址耗盡的問題，CIDR要求路由器搜索可變長度的地址前綴，以便找到與IP 目的地址相匹配的最長前綴[1]。這種占用大量計(jì)算資源的任務(wù)（通常稱為IP 查找）通常是高性能路由器的性能瓶頸。盡管基于LPM 的算法已取得重大進(jìn)展，但大多數(shù)商用路由器設(shè)計(jì)人員還是使用三態(tài)內(nèi)容可尋址存儲(chǔ)器（TCAM）設(shè)備，以與光鏈路速度保持同步，盡管其尺寸，成本和功耗比高速DDR 存儲(chǔ)器更大。使用外部存儲(chǔ)器時(shí)的查找速度通常被訪問片外存儲(chǔ)器次數(shù)限制。使用共享內(nèi)存的方案只能順序執(zhí)行查找而使用獨(dú)立內(nèi)存的方案可以并行查找。一些算法通過流水線掩蓋相關(guān)的內(nèi)存訪問，每個(gè)階段訪問一個(gè)獨(dú)立的內(nèi)存[2]。但是，這很快成為昂貴的選擇。

本文提出了將布隆過濾器用于最長前綴匹配的一種查找方案。布隆過濾器是一種有效的數(shù)據(jù)結(jié)構(gòu)通常用于有效的精確匹配。然而由于過濾器中使用了哈希算法所以可能會(huì)產(chǎn)生誤報(bào)，誤報(bào)的概率取決于存儲(chǔ)在過濾器中的條目數(shù)，過濾器的大小以及用于探查過濾器的哈希函數(shù)的數(shù)量。我們的方案將一個(gè)布隆過濾器與一個(gè)唯一的長度相關(guān)聯(lián)，搜索時(shí)使用輸入IP 對(duì)所有布隆過濾器并行執(zhí)行成員資格查詢，此步驟得到匹配前綴長度的向量，其中某些長度可能因?yàn)檎`報(bào)產(chǎn)生錯(cuò)誤。按照向量中最長匹配到向量中最短匹配的順序探查與每個(gè)前綴長度相對(duì)應(yīng)的哈希表，在找到匹配項(xiàng)或搜索到向量中表示的所有長度時(shí)終止[3]。本方案的關(guān)鍵特征在于對(duì)于更長的地址長度或轉(zhuǎn)發(fā)表中其他唯一的地址前綴長度而言，由每次查找所依賴的內(nèi)存訪問次數(shù)決定的性能可以保持恒定。

1 布隆過濾器

布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu)，用于簡潔地表示一組消息。首先使用集合中的每個(gè)消息對(duì)過濾器進(jìn)行編程，然后查詢以確定特定消息的成員身份。它是由B.H.Bloom 在1970 年提出的[4]，廣泛用于Web 緩存，入侵檢測和基于內(nèi)容的路由[5]等不同目的。我們?cè)诒拘」?jié)中解釋布隆過濾器的理論。

布隆過濾器本質(zhì)上是一個(gè)長度的位向量（在本文中我們用Vector 表示），用于有效表示一組消息。給定一組帶有成員的消息X，將對(duì)布隆過濾器進(jìn)行編程，如下所示。對(duì)于每個(gè)消息xi，k個(gè)哈希函數(shù)hi(),…,hk()，將得到k個(gè)在1 到m之間的值。這些值中的每一個(gè)都尋址向量中的單個(gè)位并將其設(shè)置為1。請(qǐng)注意，如果其中一個(gè)哈希值尋址的是已設(shè)置為1的位，則該位不會(huì)更改。以下偽代碼描述了將消息添加到Bloom 過濾器。

算法1 Old_BFAdd

1）for(i=1 to k)

2）Vector[hi(x)]=1

在過濾器中查詢給定消息的集合成員身份類似于編程過程。給定消息，使用與添加時(shí)相同的哈希函數(shù)計(jì)算哈希值。檢查與哈希值相對(duì)應(yīng)的位置處比特位是否為1。如果這些位至少有一個(gè)0 則該消息沒有成員資格。如果發(fā)現(xiàn)所有位均為1，則認(rèn)為該消息具有一定概率屬于該集合。如果發(fā)現(xiàn)所有位均為1 且不是的成員，則為假陽性。以下偽代碼描述了查詢過程。

算法2 BFQuery

1）for(i=1 to k)

2）if (Vector[hi(x)]=0)return false

3）return true

假陽性的產(chǎn)生由于以下原因：Vector 中的位可以由任意成員設(shè)置，而哈希算法會(huì)有沖突的產(chǎn)生，不同的成員通過哈希算法可能映射到Vector 中的同一個(gè)位置。因此，即使成員對(duì)應(yīng)的位為1 并不意味著集合中存在該消息，可能是其他消息因?yàn)楣_突將該位置1。但是，如果有為0 的比特位則該成員必定存在不存在于集合中，因?yàn)槿绻蓡T存在則對(duì)布隆過濾器進(jìn)行編程時(shí)會(huì)將所有位都設(shè)置為1。

布隆過濾器的誤報(bào)概率推導(dǎo)過程如下：假設(shè)我們使用的哈希函數(shù)分布均勻，通過哈希函數(shù)將具有m比特向量其中一個(gè)比特設(shè)置為1 的概率為1/m。則未設(shè)置為1 的概率為1-(1/m)，n個(gè)成員都沒有將該位設(shè)置為1 的概率為1-(1/m)n。因?yàn)槊總€(gè)成員會(huì)使用k個(gè)哈希函數(shù)將k個(gè)位置設(shè)置為1 所以該概率變?yōu)?1-(1/m))kn。因此該位被設(shè)置為1 的概率為(1-(1-(1/m))kn)。如果要判定一個(gè)成員存在集合中那么需要將k位設(shè)置為1，設(shè)該概率為f，則f的表達(dá)式如式（1）所示。

當(dāng)m足夠大時(shí)f簡化為如式（2）所示。

對(duì)于給定的m和n，可以改變k的值達(dá)到最低的誤報(bào)概率，當(dāng)k值如下時(shí)誤報(bào)概率最?。?/p>

此時(shí)誤報(bào)概率為式（4）所示。

2 并行可刪除布隆過濾器

基礎(chǔ)的布隆過濾器將k個(gè)哈希函數(shù)映射到同一個(gè)向量中如圖1（a）所示，而使用硬件實(shí)現(xiàn)時(shí)無法使用數(shù)組結(jié)構(gòu)，通常使用RAM 來實(shí)現(xiàn)，因此k個(gè)函數(shù)就需要訪問k次RAM，對(duì)存儲(chǔ)器的多次訪問會(huì)成為性能瓶頸。為了解決多次訪問的問題我們提出了改進(jìn)的基礎(chǔ)方案如圖1（b）,此方案使用了2個(gè)向量和2 個(gè)哈希函數(shù)，每個(gè)哈希函數(shù)對(duì)應(yīng)一個(gè)向量，這樣過濾的時(shí)候可以同時(shí)訪問兩個(gè)向量獲取兩個(gè)哈希位對(duì)應(yīng)的值，只需要訪問一次內(nèi)存就能得到過濾結(jié)果。在圖2 中可以看到隨著成員的增加哈希函數(shù)的概率呈指數(shù)增長，因此當(dāng)存儲(chǔ)一定表項(xiàng)時(shí)基礎(chǔ)的方案中因?yàn)楣_突將無法添加成員資格，因此我們提出了改進(jìn)的基礎(chǔ)方案如圖1（c）,在該方案中我們用雙口RAM 來實(shí)現(xiàn)向量，雙口RAM 有a,b 口可以同時(shí)讀取數(shù)據(jù)。同時(shí)使用了四個(gè)哈希函數(shù)h1,h2,h3 和h4，h1 和h2 分別在兩個(gè)向量的a 口讀取數(shù)據(jù)，h3 和h4 分別在兩個(gè)向量b 口讀取數(shù)據(jù)。添加成員資格時(shí)當(dāng)h1 和h2 對(duì)應(yīng)的位置不全為0 可以使用h3 和h4 進(jìn)行探測，如果h3 和h4 對(duì)應(yīng)位置全為0 則將h3 和h4 對(duì)應(yīng)的位置設(shè)置為1。此時(shí)添加IP 的偽代碼如下：

算法3BFAdd

布隆過濾器的另一個(gè)致命缺點(diǎn)是不能刪除成員資格[6]。刪除成員資格時(shí)會(huì)將成員對(duì)應(yīng)的哈希位設(shè)置為0，如果有其他成員的哈希值也映射到該位置則其他成員的資格也會(huì)被刪除，查表時(shí)會(huì)造成丟包這是我們不能接受的。

在我們的方案中產(chǎn)生無法刪除成員的原因只有一個(gè)，其他成員將待刪除成員的剩余為0 的位置全部設(shè)置為1 也就是待刪除成員h1,h2,h3 和h4 對(duì)應(yīng)的位置全部為1，此時(shí)我們無法確定是將h1,h2 對(duì)應(yīng)的位置設(shè)置為0 還是將h3,h4 對(duì)應(yīng)的位置設(shè)置為0。為解決該問題我們?cè)O(shè)置了一塊FIFO 來存儲(chǔ)無法刪除的成員，每過一定時(shí)鐘周期就在FIFO 中讀出一個(gè)成員重新進(jìn)行刪除，如果無法刪除就將該成員重新寫入到FIFO 中。如此循環(huán)的目的是為了等待產(chǎn)生沖突的其他成員被刪除。

以添加15,17 和36 的成員資格為例，表1 中為其對(duì)應(yīng)的哈希值，當(dāng)添加36 的成員資格時(shí)h1 和h2對(duì)應(yīng)的位置都為1，所以將h3 和h4 對(duì)應(yīng)的位置設(shè)置為1。添加完成后過濾器為圖3（a）。添加完成后刪除36 成員資格時(shí)四個(gè)哈希探針對(duì)應(yīng)的位置都為1 此時(shí)將36 寫入到FIFO 中，繼續(xù)刪除15 成員資格，刪除后如圖3（b），如果此時(shí)在在FIFO 中讀出36 則可刪除成功。

圖1 布隆過濾器結(jié)構(gòu)

圖2 哈希沖突概率

圖3 過濾器刪除過程

3 系統(tǒng)配置

每次查找所需的內(nèi)存訪問數(shù)通常是查找算法的性能瓶頸。隨著半導(dǎo)體技術(shù)的發(fā)展，高端FPGA 的系統(tǒng)頻率可以達(dá)到300MHz,能夠進(jìn)行大規(guī)模并行運(yùn)算，并且片內(nèi)有數(shù)Mb 的RAM 可以使用。我們的方案基于FPGA 實(shí)現(xiàn)搭配外部DDR 每次查找基本只需要一次片外DDR 訪問。

以IPv4 為例，查找最長匹配前綴的簡單方法是使用哈希表，將每個(gè)長度的前綴都分配一個(gè)哈希表，表內(nèi)存儲(chǔ)前綴和對(duì)應(yīng)的下一跳信息。進(jìn)行路由查找時(shí)從前綴長度最長的哈希表進(jìn)行查找，依次查找前綴長度更短的哈希表，當(dāng)找到匹配的前綴時(shí)停止查找返回對(duì)應(yīng)的下一跳信息。為了便于討論我們假設(shè)哈希表內(nèi)沒有沖突，查找哈希表時(shí)只需要一次存儲(chǔ)器訪問。這種方法最壞情況下需要訪問32 次片外DDR。但是我們通過使用FPGA 片內(nèi)的并行布隆過濾器將查找范圍縮小到有限的幾張哈希表內(nèi)，因此可以將訪問次數(shù)降低到幾乎單次。

我們的系統(tǒng)配置如圖4 所示。我們將相同長度的前綴集中為一個(gè)集合，并將該集合存儲(chǔ)在布隆過濾器中。我們將布隆過濾器存儲(chǔ)在FPGA 的片內(nèi)RAM 中以便并行操作，每個(gè)過濾器對(duì)應(yīng)一個(gè)單獨(dú)的前綴長度。在查詢哈希表之前我們先將IP 送到32 個(gè)布隆過濾器中進(jìn)行過濾。注意，布隆過濾會(huì)產(chǎn)生假陽性但絕不會(huì)產(chǎn)生假陰性，假陽性的后果是我們浪費(fèi)了內(nèi)存訪問次數(shù)，并不會(huì)造成錯(cuò)誤的最長前綴匹配。如果過濾結(jié)果為假陽性，那么對(duì)應(yīng)的哈希表內(nèi)我們將會(huì)匹配失敗繼續(xù)匹配其他哈希表。假陽性是無法避免的我們只能盡力降低過濾器的假陽性概率。

由于我們將布隆過濾器全部存儲(chǔ)在FPGA片內(nèi)，所以我們可以對(duì)32 個(gè)過濾器同時(shí)進(jìn)行匹配。在我們的實(shí)驗(yàn)中需要3 個(gè)時(shí)鐘周期得到匹配結(jié)果，

其中讀取RAM 就需要花費(fèi)兩個(gè)時(shí)鐘周期。過濾結(jié)束后會(huì)得到32 比特的匹配向量。我們使用優(yōu)先級(jí)編碼器對(duì)過濾得到的向量進(jìn)行優(yōu)先級(jí)編碼然后從長到短的查找對(duì)應(yīng)哈希表以找到最長的匹配前綴。以下偽代碼描述了對(duì)IP 地址I 的查找過程。

算法4 LOOKUP(I)

1）for (j=32 to 1)

2）MatchVector[j]=BFQueryj(Ij)

3）for(j=32 to 1)

4）if(MatchVector[j]==1)

5）{prefix,NextHop}=HashTableLookupj(Ij)

6）if(prefix=Ij)return{prefix,NextHop}

7）return {NULL,DefaultHop}

在上面的偽代碼中Ij表示I 的高j 比特，BFQuery 表示查詢?cè)撉熬Y長度的布隆過濾器的過程。第1-2 行的代碼在FPGA 中并行實(shí)現(xiàn)。

圖4 系統(tǒng)配置

4 性能分析

在第2 節(jié)中我們已經(jīng)得出布隆過濾器的誤報(bào)概率公式（3），首先說明使用變量的意義，mi為每個(gè)過濾器占用的存儲(chǔ)資源，ni為每個(gè)過濾器中的前綴數(shù)量，M為分配給布隆過濾器的存儲(chǔ)資源總量，N為系統(tǒng)支持的前綴數(shù)量。假設(shè)每個(gè)布隆過濾器的概率都相等則得到以式（5）：

這說明

因此給定濾波器的誤報(bào)概率可以表示為：

因此當(dāng)所有過濾器的誤報(bào)概率相等時(shí)，系統(tǒng)性能就與前綴分布無關(guān)，對(duì)于IPv4 每次查詢的平均哈希探測次數(shù)可表示為：

圖5 中為不同前綴數(shù)量下布隆過濾器占用內(nèi)存與片外DDR 訪問次數(shù)的關(guān)系，可以看到為過濾器分配2 Mb 內(nèi)存時(shí)對(duì)于100000 條前綴，平均探測次數(shù)接近1 次。

圖5 過濾器大小與訪問DDR 次數(shù)關(guān)系

仿真時(shí)我們使用Modelsim 10.6d 和Vivado2018.1，芯片選擇xc7vx690ttfg。我們使用實(shí)際IPv4 的BGP表來構(gòu)造轉(zhuǎn)發(fā)表。為了說明輸入地址對(duì)DDR 訪問次數(shù)的影響，我們從完全隨機(jī)的IP 地址逐漸過渡到轉(zhuǎn)發(fā)表中存在的地址，每次測試使用10 萬個(gè)IP地址。實(shí)驗(yàn)結(jié)果表明使用完全隨機(jī)的地址時(shí)布隆過濾器均不會(huì)產(chǎn)生誤報(bào)，隨著轉(zhuǎn)發(fā)表中存在的地址增多，DDR 訪問次數(shù)會(huì)逐漸上升，當(dāng)流量中的IP 地址全部來自轉(zhuǎn)發(fā)表時(shí)達(dá)到最大的訪問次數(shù)。表1 為使用5 個(gè)數(shù)據(jù)庫中的流量進(jìn)行測試時(shí)的理論值和實(shí)際觀測值?？梢钥吹綄?shí)際觀測值與理論值接近，平均誤報(bào)率幾乎為1。使用800MHz 的DDR3 搭配200MHz的FPGA芯片實(shí)現(xiàn)時(shí)每秒可實(shí)現(xiàn)30M次查詢。

表1 M=2Mb 6 個(gè)IPv4BGP 表的平均哈希探測次數(shù)

5 結(jié)語

我們通過使用布隆過濾算法將查找范圍精確定位到少量哈希表內(nèi)，降低了LPM 算法的平均訪問存儲(chǔ)器次數(shù)。為了進(jìn)一步優(yōu)化性能，我們將布隆過濾器改為雙向量的結(jié)構(gòu)使其適合硬件實(shí)現(xiàn)可以并行過濾降低了查找延遲提高了端口吞吐率。性能分析和仿真實(shí)驗(yàn)表明，該方案平均訪問片外存儲(chǔ)器次數(shù)小于兩次，幾乎接近一次。

使用200MHz 的FPGA 芯片搭配頻率為800MHz 的DDR3 實(shí)現(xiàn)可提供每秒30M 次的查詢。盡管仍低于TCAM 但是TCAM 的每位存儲(chǔ)的功耗比DDR 高10 倍，并且隨著半導(dǎo)體技術(shù)的發(fā)展DDR 和FPGA 的頻率會(huì)逐漸提升，該方案可以移植到性能更高的平臺(tái)以達(dá)到更快的查找速度。