一種基于分段式路由查找的布隆過濾方案*

張 鐿，丁 帥，喬廬峰，陳慶華，劉 熹，鄒仕祥

（中國人民解放軍陸軍工程大學，江蘇 南京 210001）

0 引言

下一代路由器應支持數以千萬計的數據包的線速轉發，并提供快速實時更新，以適應不斷增長的路由表，這使得基于網際互連協議（Internet Protocol，IP）的路由查找任務面臨巨大的挑戰[1]。當前，IP 地址分配廣泛采用無類域間路由（Classless Inter-Domain Routing，CIDR）技術。基于CIDR 提出的最長前綴匹配（Longest Prefix Matching，LPM）算法多采用Trie 樹形數據結構。然而隨著查找深度加大，經典Trie 樹形結構的查找效率會大幅降低，因為這種一次一位的檢索機制在最壞情況下需要進行的次數等于地址長度的存儲訪問。

為了解決上述問題，一系列基于多位Trie（Multibit Trie）的路由查找算法被提出[2-4]。這些算法的基本思想是通過構造步幅不固定的前綴子樹，將路由查找分段式并行進行，檢索位數由一次一位提高到一次多位，以減少存儲訪問次數，實現更高的查找速度。然而，這類方案的缺點在于，需要為每個階段的訪問設置一塊獨立內存且占用大量計算資源，這在某些資源功耗受限的場景下是很難適用的。一般來說，使用共享內存的查找方法可以避免過高的存儲需求，但是查找操作只能順序執行。此類查找方案多采用優先級搜索，當高優先階段無匹配項時，則順序查找次優先級的階段。因此，不必要的查找階段將導致算法整體耗時較長。針對類似的問題，在文獻[5]中，作者利用布隆過濾的方法，在基于Hash 的路由查找方案中進行了設計驗證。

本文提出了一種基于分段式路由查找的布隆過濾方案，面向資源功耗受限的星間網絡，盡可能減少查找次數，提高轉發速率，節省星上計算資源。該方案借鑒地面路由器架構，將布隆過濾器引入到基于多位Trie 的分段式路由查找中，通過減少對外部存儲訪問次數來提高查找性能。該方案在滿足星上資源功耗要求的同時減少了無效查找，提高了查找命中率。此外，本文方案還將布隆過濾器位數組中的每一位與一個計數器相關聯，以支持路由的實時更新。

1 布隆過濾器

布隆過濾器是一種節省空間的數據結構，用于確定集合中是否存在某些元素。它由Bloom 于1970年提出[6]，是目前執行近似成員資格查詢的最流行的架構之一，廣泛用于加速計算和網絡應用，如DNA 測序[7]、緩存[8]和網絡安全[9]等。

布隆過濾器本質上是一個m位數組，用于存儲集合中元素的成員信息并回答成員資格查詢。初始時每個位被設置為“0”，使用k個hash 函數h1(x)，h2(x)，…，hk(x)，在其上插入元素或檢查其中的元素。為了插入元素x，將由h1(x)，h2(x)，…，hk(x)尋址得到的位設置為“1”。與插入相反，為了檢查元素是否存在于集合中，將讀取這些位置上的比特信息，并且當且僅當所有位反饋都為“1”時，才會認為該元素具有一定概率屬于該集合，即成員資格查詢結果返回true。

標準布隆過濾器結構如圖1 所示，在過濾器上插入元素x和y，檢查元素x，y，z的成員資格。

圖1 標準布隆過濾器示例

對于已插入的元素，成員資格查詢結果將始終返回true，即布隆過濾器沒有假陰性。相反，當檢查未插入的元素時，過濾器在絕大多數情況下查詢結果會返回false，但也有一定概率會返回true，即出現了假陽性。對于未存儲在過濾器中的元素，其hash 索引對應的k個位置上因其他元素的插入而被設置為“1”時，就會發生假陽性的情況。檢查時產生這種假陽性誤報的概率可近似認為是pk，其中p是m位數組中一個比特位被設置為“1”的概率，它是插入元素數量的函數。當過濾器中插入n個元素時，p可以具體表示為：

因此，假陽性誤報概率f為：

若m足夠大，式（2）可進一步簡化為：

對于給定的過濾器大小m和插入的元素數量n，為使誤報率f達到最小，k的最優值為：

此時誤報率f為：

除了存在假陽性概率，標準布隆過濾器的另一主要缺點在于不支持元素的刪除。由于給定位置的比特指示位可能已被多個元素設置為“1”，移除單一元素時將其清零可能會導致誤報，因此無法刪除元素。

2 可刪除計數式布隆過濾器

一般來說，標準布隆過濾器在所要表達的集合是靜態的情況下，可以達到理想的效果。相反，當所要表達的集合變動頻繁，其不支持刪除的弊端就會顯現出來。通常來說，網絡前綴的修改、插入和刪除，甚至子網可用性配置的更改，都會引起大量的路由更新。對于基于布隆過濾器的路由查找方案而言，如果在路由變動時，不相應地更新布隆過濾器，勢必會造成大量誤報，從而影響查找匹配結果，這在路由查找中是不能接受的。

為了解決上述問題，本文提出將路由查找中使用的標準布隆過濾器擴展為可刪除計數式布隆過濾器（Deletable Counting Bloom Filter，DCBF）。具體而言，將標準布隆過濾器位數組的每一位對應一個計數器以支持刪除操作，計數器僅用于插入和刪除，而不用于查找。圖2 為插入元素A，B，C 的可刪除計數式布隆過濾器示例。

圖2 可刪除計數式布隆過濾器示例

添加成員資格時，需要對位數組及計數器進行修改，過濾器通過算法1 中所示的過程添加新項。

成員資格查詢過程與標準布隆過濾器相同，如算法2 所示。

算法3 描述了計數式布隆過濾器的刪除過程。刪除成員資格時，檢查給定元素hash 索引對應的計數值并減1，當且僅當計數值減為0 時，將對應的位數組值置零。

3 過濾單元的設計與實現

3.1 分段式路由查找算法

常規的分段式路由查找算法在數據結構的設計上，都盡可能避免將流行的前綴長度設為段首來節省存儲，因而原則上沒有固定的分段方法。

以國際協議版本4（Internet Protocol Version 4，IPv4）地址為例，從俄勒岡大學Route Views 項目[10]給出的路由表地址分析報告中可以看出，路由表地址的前綴長度分布在8 到32 之間，并且絕大多數的前綴長度集中在16 至24。圖3 根據報告提供的數據給出了IPv4 前綴長度的分布情況，從中可以看出IPv4 前綴長度分布的不均勻性。

圖3 IPv4 前綴分布情況

基于這種不均勻分布特性，本文設計的路由查找算法將32 位IPv4 地址劃分為4 段。具體分段方案為：第1 階段包含長度為1 到8 的前綴信息；第2 階段包含長度為9 到16 的前綴信息；第3 階段包含長度為17 到24 的前綴信息；第4 階段包含長度為25 到32 的前綴信息。每一階段基于Trie 樹算法生成完整的路由前綴位圖，并配置1 個維護前綴子樹的過濾器，所以在本文方案中共采用了4 個改進型布隆過濾器。

路由的查找過程主要依據布隆過濾器組、位圖信息表和轉發信息表來完成轉發操作。轉發路由查找過程的流程如圖4 所示，查找的具體流程如下文所述。

圖4 轉發路由查找流程

首先，將待匹配的IP 地址分段并行輸入布隆過濾器，執行成員資格查詢操作。若對應于每個階段的布隆過濾器均返回false，說明該地址在路由轉發表中無匹配項，直接以缺省路由進行轉發；反之，則根據過濾單元返回結果進行優先級編碼。

其次，依據最長前綴匹配的原則，檢查最高優先級階段對應的路由前綴位圖，并根據輸入地址遍歷前綴位圖。若當前位圖存在匹配前綴，則輸出該前綴子樹對應的基地址和相應的轉發表尋址信息；若當前位圖匹配失敗，則順序查找前級命中的次優先級階段；若全部階段無位圖匹配，待匹配IP 地址將以默認端口輸出。

最后，根據位圖尋址信息查找路由轉發表，提取下一跳地址并輸出。整個查找架構如圖5 所示。

圖5 引入布隆過濾器的分段式路由查找架構

3.2 過濾單元的參數設計

在上一小節中，本文提出為分段式路由查找的每一階段配置一個本地計數式布隆過濾器，來維護該級別生成的子樹。對于過濾單元而言，計數器的內存分配如何做到合理且適用是至關重要的。根據第2 節的描述，已經計算得到了布隆過濾器誤報率的相關公式，現在在此基礎上展開如下推導。

首先，計數器i被增加j次的概率為：

式中：ci為計數器i的計數值；n為插入元素數量；k為hash 函數數目；m為計數器個數，即對應原先位數組的大小。

因此，計數器的值大于或等于j的概率可以限定為：

依據Stirling 公式，則可進一步得到：

最后，根據hash 函數數目的最優值公式（4），假設k小于kopt，就可以得到如下結論：

在實際運用中，對于hash 函數數目k，通常選擇一個低于最優值的整數值來減少計算開銷；對于最大計數值j，取4，8，16 等對應計數位數的整數值代入式（9）得到以下示例值：

具體而言，如果為每個計數器分配3 位，則當計數值達到8 時就會溢出，其概率如式（11）所示，此時溢出概率很小；同理，如果每個計數器允許分配4 位，則實際值溢出（即計數值達到16）的概率如式（12）所示，這個數值已經足夠小，能夠滿足絕大部分應用需求。

綜上所述，并結合路由前綴的不均勻分布特性，過濾單元的具體參數設置如表1 所示，其中前綴子樹的相關數據基于路由表地址分析報告[10]給出。

表1 過濾單元參數設置

4 仿真分析

本文使用Vivado2019.2 和Modelsim10.6d 軟件對過濾單元進行設計實現與仿真測試，FPGA 芯片選擇Xilinx 的Virtex-7 xc7vx690tffg。圖6、圖7 和圖8 給出了過濾單元關鍵算法的仿真波形。

添加前綴子樹的成員資格時，過濾單元對子樹索引的讀取和相應計數器操作的過程如圖6 所示。其中1 處上半部分表示完成對第1 階段子樹索引128.0.0.0（32’h8000000）尋址的位數組值的寫入，下半部分對應其計數值的變化。圖6 中其余2、3、4 處同理。

圖6 DCBF 插入算法仿真結果

在完成對4 個階段子樹索引128.0.0.0、128.128.0.0、128.128.128.0 和128.128.128.128 的添加之后，對4 組IP 地址128.0.0.0、128.128.0.0、128.128.128.0 和128.128.128.128 進行測試，結果分別如圖7 中5、6、7、8 處所示。以匹配第1 階段和第2 階段子樹索引的IP 地址128.128.0.0（32’h80800000）為例，其過濾結果為0011，即輸出的4 位結果由高到低與命中的4 個階段一一對應。

圖7 DCBF 查詢算法仿真結果1

過濾單元收到刪除請求后讀取待刪除的子樹索引，刪除第1 階段子樹索引128.0.0.0 和第3 階段子樹索引128.128.128.0 的成員資格，如圖8 中9 和10 處所示。索引刪除完成之后，重復上述4 組IP地址的資格查詢操作，結果分別如圖9 中11、12、13、14 處所示。

圖8 DCBF 刪除算法仿真結果

圖9 DCBF 查詢算法仿真結果2

5 結語

本文針對資源功耗受限的衛星網絡應用場景，給出了一種能夠在較少資源消耗下提高分段式路由查找速率的解決方案。該方案通過布隆過濾算法來縮小查找階段范圍，減少路由查找過程中外部存儲的訪問次數。同時，將標準布隆過濾器擴展為可刪除計數式布隆過濾器，用于支持路由的實時更新。理論分析和仿真結果都表明，該方案具有有效性。