可加速最长前缀匹配的布隆过滤查找方案*

2020-07-19乔庐峰陈庆华

通信技术 2020年7期

王乾，乔庐峰，陈庆华

（陆军工程大学通信工程学院，江苏南京 210001）

0 引言

近年来IPv4 地址逐渐被耗尽，无类域间路由（CIDR）被提出用来缓解地址耗尽的问题，CIDR要求路由器搜索可变长度的地址前缀，以便找到与IP 目的地址相匹配的最长前缀[1]。这种占用大量计算资源的任务（通常称为IP 查找）通常是高性能路由器的性能瓶颈。尽管基于LPM 的算法已取得重大进展，但大多数商用路由器设计人员还是使用三态内容可寻址存储器（TCAM）设备，以与光链路速度保持同步，尽管其尺寸，成本和功耗比高速DDR 存储器更大。使用外部存储器时的查找速度通常被访问片外存储器次数限制。使用共享内存的方案只能顺序执行查找而使用独立内存的方案可以并行查找。一些算法通过流水线掩盖相关的内存访问，每个阶段访问一个独立的内存[2]。但是，这很快成为昂贵的选择。

本文提出了将布隆过滤器用于最长前缀匹配的一种查找方案。布隆过滤器是一种有效的数据结构通常用于有效的精确匹配。然而由于过滤器中使用了哈希算法所以可能会产生误报，误报的概率取决于存储在过滤器中的条目数，过滤器的大小以及用于探查过滤器的哈希函数的数量。我们的方案将一个布隆过滤器与一个唯一的长度相关联，搜索时使用输入IP 对所有布隆过滤器并行执行成员资格查询，此步骤得到匹配前缀长度的向量，其中某些长度可能因为误报产生错误。按照向量中最长匹配到向量中最短匹配的顺序探查与每个前缀长度相对应的哈希表，在找到匹配项或搜索到向量中表示的所有长度时终止[3]。本方案的关键特征在于对于更长的地址长度或转发表中其他唯一的地址前缀长度而言，由每次查找所依赖的内存访问次数决定的性能可以保持恒定。

1 布隆过滤器

布隆过滤器是一种数据结构，用于简洁地表示一组消息。首先使用集合中的每个消息对过滤器进行编程，然后查询以确定特定消息的成员身份。它是由B.H.Bloom 在1970 年提出的[4]，广泛用于Web 缓存，入侵检测和基于内容的路由[5]等不同目的。我们在本小节中解释布隆过滤器的理论。

布隆过滤器本质上是一个长度的位向量（在本文中我们用Vector 表示），用于有效表示一组消息。给定一组带有成员的消息X，将对布隆过滤器进行编程，如下所示。对于每个消息xi，k个哈希函数hi(),…,hk()，将得到k个在1 到m之间的值。这些值中的每一个都寻址向量中的单个位并将其设置为1。请注意，如果其中一个哈希值寻址的是已设置为1的位，则该位不会更改。以下伪代码描述了将消息添加到Bloom 过滤器。

算法1 Old_BFAdd

1）for(i=1 to k)

2）Vector[hi(x)]=1

在过滤器中查询给定消息的集合成员身份类似于编程过程。给定消息，使用与添加时相同的哈希函数计算哈希值。检查与哈希值相对应的位置处比特位是否为1。如果这些位至少有一个0 则该消息没有成员资格。如果发现所有位均为1，则认为该消息具有一定概率属于该集合。如果发现所有位均为1 且不是的成员，则为假阳性。以下伪代码描述了查询过程。

算法2 BFQuery

1）for(i=1 to k)

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

3）return true

假阳性的产生由于以下原因：Vector 中的位可以由任意成员设置，而哈希算法会有冲突的产生，不同的成员通过哈希算法可能映射到Vector 中的同一个位置。因此，即使成员对应的位为1 并不意味着集合中存在该消息，可能是其他消息因为哈希冲突将该位置1。但是，如果有为0 的比特位则该成员必定存在不存在于集合中，因为如果成员存在则对布隆过滤器进行编程时会将所有位都设置为1。

布隆过滤器的误报概率推导过程如下：假设我们使用的哈希函数分布均匀，通过哈希函数将具有m比特向量其中一个比特设置为1 的概率为1/m。则未设置为1 的概率为1-(1/m)，n个成员都没有将该位设置为1 的概率为1-(1/m)n。因为每个成员会使用k个哈希函数将k个位置设置为1 所以该概率变为(1-(1/m))kn。因此该位被设置为1 的概率为(1-(1-(1/m))kn)。如果要判定一个成员存在集合中那么需要将k位设置为1，设该概率为f，则f的表达式如式（1）所示。

当m足够大时f简化为如式（2）所示。

对于给定的m和n，可以改变k的值达到最低的误报概率，当k值如下时误报概率最小：

此时误报概率为式（4）所示。

2 并行可删除布隆过滤器

基础的布隆过滤器将k个哈希函数映射到同一个向量中如图1（a）所示，而使用硬件实现时无法使用数组结构，通常使用RAM 来实现，因此k个函数就需要访问k次RAM，对存储器的多次访问会成为性能瓶颈。为了解决多次访问的问题我们提出了改进的基础方案如图1（b）,此方案使用了2个向量和2 个哈希函数，每个哈希函数对应一个向量，这样过滤的时候可以同时访问两个向量获取两个哈希位对应的值，只需要访问一次内存就能得到过滤结果。在图2 中可以看到随着成员的增加哈希函数的概率呈指数增长，因此当存储一定表项时基础的方案中因为哈希冲突将无法添加成员资格，因此我们提出了改进的基础方案如图1（c）,在该方案中我们用双口RAM 来实现向量，双口RAM 有a,b 口可以同时读取数据。同时使用了四个哈希函数h1,h2,h3 和h4，h1 和h2 分别在两个向量的a 口读取数据，h3 和h4 分别在两个向量b 口读取数据。添加成员资格时当h1 和h2 对应的位置不全为0 可以使用h3 和h4 进行探测，如果h3 和h4 对应位置全为0 则将h3 和h4 对应的位置设置为1。此时添加IP 的伪代码如下：

算法3BFAdd

布隆过滤器的另一个致命缺点是不能删除成员资格[6]。删除成员资格时会将成员对应的哈希位设置为0，如果有其他成员的哈希值也映射到该位置则其他成员的资格也会被删除，查表时会造成丢包这是我们不能接受的。

在我们的方案中产生无法删除成员的原因只有一个，其他成员将待删除成员的剩余为0 的位置全部设置为1 也就是待删除成员h1,h2,h3 和h4 对应的位置全部为1，此时我们无法确定是将h1,h2 对应的位置设置为0 还是将h3,h4 对应的位置设置为0。为解决该问题我们设置了一块FIFO 来存储无法删除的成员，每过一定时钟周期就在FIFO 中读出一个成员重新进行删除，如果无法删除就将该成员重新写入到FIFO 中。如此循环的目的是为了等待产生冲突的其他成员被删除。

以添加15,17 和36 的成员资格为例，表1 中为其对应的哈希值，当添加36 的成员资格时h1 和h2对应的位置都为1，所以将h3 和h4 对应的位置设置为1。添加完成后过滤器为图3（a）。添加完成后删除36 成员资格时四个哈希探针对应的位置都为1 此时将36 写入到FIFO 中，继续删除15 成员资格，删除后如图3（b），如果此时在在FIFO 中读出36 则可删除成功。

图1 布隆过滤器结构

图2 哈希冲突概率

图3 过滤器删除过程

3 系统配置

每次查找所需的内存访问数通常是查找算法的性能瓶颈。随着半导体技术的发展，高端FPGA 的系统频率可以达到300MHz,能够进行大规模并行运算，并且片内有数Mb 的RAM 可以使用。我们的方案基于FPGA 实现搭配外部DDR 每次查找基本只需要一次片外DDR 访问。

以IPv4 为例，查找最长匹配前缀的简单方法是使用哈希表，将每个长度的前缀都分配一个哈希表，表内存储前缀和对应的下一跳信息。进行路由查找时从前缀长度最长的哈希表进行查找，依次查找前缀长度更短的哈希表，当找到匹配的前缀时停止查找返回对应的下一跳信息。为了便于讨论我们假设哈希表内没有冲突，查找哈希表时只需要一次存储器访问。这种方法最坏情况下需要访问32 次片外DDR。但是我们通过使用FPGA 片内的并行布隆过滤器将查找范围缩小到有限的几张哈希表内，因此可以将访问次数降低到几乎单次。

我们的系统配置如图4 所示。我们将相同长度的前缀集中为一个集合，并将该集合存储在布隆过滤器中。我们将布隆过滤器存储在FPGA 的片内RAM 中以便并行操作，每个过滤器对应一个单独的前缀长度。在查询哈希表之前我们先将IP 送到32 个布隆过滤器中进行过滤。注意，布隆过滤会产生假阳性但绝不会产生假阴性，假阳性的后果是我们浪费了内存访问次数，并不会造成错误的最长前缀匹配。如果过滤结果为假阳性，那么对应的哈希表内我们将会匹配失败继续匹配其他哈希表。假阳性是无法避免的我们只能尽力降低过滤器的假阳性概率。

由于我们将布隆过滤器全部存储在FPGA片内，所以我们可以对32 个过滤器同时进行匹配。在我们的实验中需要3 个时钟周期得到匹配结果，

其中读取RAM 就需要花费两个时钟周期。过滤结束后会得到32 比特的匹配向量。我们使用优先级编码器对过滤得到的向量进行优先级编码然后从长到短的查找对应哈希表以找到最长的匹配前缀。以下伪代码描述了对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 表示查询该前缀长度的布隆过滤器的过程。第1-2 行的代码在FPGA 中并行实现。

图4 系统配置

4 性能分析

在第2 节中我们已经得出布隆过滤器的误报概率公式（3），首先说明使用变量的意义，mi为每个过滤器占用的存储资源，ni为每个过滤器中的前缀数量，M为分配给布隆过滤器的存储资源总量，N为系统支持的前缀数量。假设每个布隆过滤器的概率都相等则得到以式（5）：

这说明

因此给定滤波器的误报概率可以表示为：

因此当所有过滤器的误报概率相等时，系统性能就与前缀分布无关，对于IPv4 每次查询的平均哈希探测次数可表示为：

图5 中为不同前缀数量下布隆过滤器占用内存与片外DDR 访问次数的关系，可以看到为过滤器分配2 Mb 内存时对于100000 条前缀，平均探测次数接近1 次。

图5 过滤器大小与访问DDR 次数关系

仿真时我们使用Modelsim 10.6d 和Vivado2018.1，芯片选择xc7vx690ttfg。我们使用实际IPv4 的BGP表来构造转发表。为了说明输入地址对DDR 访问次数的影响，我们从完全随机的IP 地址逐渐过渡到转发表中存在的地址，每次测试使用10 万个IP地址。实验结果表明使用完全随机的地址时布隆过滤器均不会产生误报，随着转发表中存在的地址增多，DDR 访问次数会逐渐上升，当流量中的IP 地址全部来自转发表时达到最大的访问次数。表1 为使用5 个数据库中的流量进行测试时的理论值和实际观测值。可以看到实际观测值与理论值接近，平均误报率几乎为1。使用800MHz 的DDR3 搭配200MHz的FPGA芯片实现时每秒可实现30M次查询。