用于网络设备的高效最长前缀匹配技术

摘要

在网络设备的搜索引擎处获得与分组相关联的网络地址。该搜索引擎包括表示路由表中相应长度的前缀的多个布隆过滤器。相应的布隆过滤器被应用于网络地址的相应前缀以确定在路由表中针对其可能存在匹配的一个或者多个前缀的集合。以最长前缀作为开始并且以前缀长度的降序继续，使用前缀集合中的前缀对存储器执行若干访问，直至在路由表中找到匹配条目，并且获取用于分组的路由信息。如果所执行的存储器访问的数量超过了阈值，该路由表被调适以减少针对与该网络地址相关联的后续分组所要执行的存储器访问的数量。

说明书

相关申请的交叉引用

本公开要求于2013年2月27日提交的美国临时专利申请号61/770,100以及2013年7月26日提交的美国临时专利申请号61/859,053、题目同为“LongestPrefixMatch”的权益，其公开内容因此通过引用以其整体明确地并入本文。

技术领域

本公开总体上涉及诸如交换机、路由器和边缘设备之类的网络设备，尤其涉及用于这样的设备中的最长前缀(prefix)匹配操作的系统和方法。

背景技术

本文所提供的背景技术描述是为了总体上呈现本公开的背景。就该背景技术部分中所描述的工作的范围以及描述中在提交时并不以其它方式构成现有技术的方面而言，本发明人的工作既非明确也非隐含地被承认为相对本公开的现有技术。

诸如网络交换机、桥接器、路由器等的网络设备通常执行最长前缀匹配查找以便对遍历网络设备的分组(packet)进行路由。一般来讲，路由表将网络地址与关联于该网络地址的分组应当从网络设备被发送至那里的下一跳相关联。最长前缀匹配查找涉及基于与分组相关联的网络地址搜索路由表以找出与该地址中最大数量的开头位(bit)相匹配的路由条目(entry)。一些网络设备使用基于三元内容可寻址存储器(TCAM)技术的路由表。在基于TCAM的路由表中，该路由表的所有条目都能够基于地址进行并行搜索以找出针对该地址具有最长前缀匹配的条目。因此，TCAM设备允许相对快速地执行最长前缀匹配搜索。然而，TCAM设备通常在尺寸、成本和功耗方面是昂贵的。

作为TCAM实施方式的一种替换形式，一些网络设备使用诸如静态随机访问存储器(SRAM)设备或者动态随机访问存储器(DRAM)设备的随机访问存储器设备来存储路由表，并且采用诸如基于特里(trie)的算法之类的搜索算法在路由表中执行最长前缀匹配搜索。然而，基于RAM的路由表与大小相当的基于TCAM的路由表相比通常需要更多的存储器空间以及更高的存储器带宽。而且，通常被用来搜索这样的基于RAM的路由表的搜索算法相对缓慢，并且并非必然以许多网络设备所支持的高线路速度进行操作。此外，这样的基于RAM的路由表和搜索算法无法良好扩展以轻易地应对长度有所增加的网络地址。

发明内容

在实施例中，一种用于在存储用于转发网络设备中的分组的路由表的存储器中执行最长前缀匹配查找操作的方法，包括在该网络设备的搜索引擎处获得与分组相关联的网络地址。该搜索引擎包括多个布隆过滤器(Bloomfilter)，其中该布隆过滤器中的至少一些布隆过滤器中的每一个布隆过滤器表示该路由表中的一定长度的前缀。该方法还包括由该网络设备的搜索引擎将该多个布隆过滤器中的相应布隆过滤器应用于该网络地址的相应前缀以确定在该路由表中针对其可能存在匹配的该网络地址的一个或者多个前缀的集合。该方法还包括由该搜索引擎使用该前缀集合中的前缀对该存储器执行若干访问，以该前缀集合中的最长前缀作为开始并且以该前缀集合中的前缀长度的降序继续，直至在该路由表中找到具有匹配前缀的条目。该方法进一步包括从该路由表中的该条目获取用于该分组的路由信息。该方法还进一步包括由该搜索引擎确定所执行的存储器访问的数量超过阈值，并且响应于确定所执行的存储器访问的数量超过阈值，对该路由表进行调适以减少要针对与该网络地址相关联的后续分组所执行的存储器访问的数量。

在其它实施例中，该方法进一步包括以下一个或者多个特征的任意组合。

该多个布隆过滤器中的第一布隆过滤器表示该路由表中第一长度的前缀。

该第一布隆过滤器包括表示该路由表中第一长度的第一前缀子集的第一布隆过滤器块；和表示该路由表中第一长度的第二前缀子集的第二布隆过滤器块。

该第一前缀子集并不与该第二前缀子集重叠。

向前缀应用第一布隆过滤器包括基于前缀计算散列值，使用该散列值的第一部分选择第一布隆过滤器块或者第二布隆过滤器块，使用该散列值的第二部分选择第一布隆过滤器块和第二布隆过滤器块中所选择的一个过滤器块中的位置；并且基于该位置确定该路由表中是否可能存在匹配。

调适(adapt)该路由表包括将新条目插入到该路由表中，其中该新条目包括(i)地址的前缀，其中该前缀比与该路由表中所找到的条目相关联的匹配前缀更长，和(ii)从该路由表中所找到的条目获取到的路由信息。

调适该路由表在该网络设备的数据面中执行。

在另一个实施例中，一种装置包括用于存储路由表的存储器，该路由表用于转发网络设备中的分组。该装置还包括搜索引擎，该搜索引擎包括被配置为表示该路由表中特定长度的相应前缀集合的多个布隆过滤器。该搜索引擎被配置为获得与分组相关联的网络地址并且将该多个布隆过滤器中的相应布隆过滤器应用于该网络地址的相应前缀以确定在该路由表中针对其可能存在匹配的该网络地址的一个或者多个前缀的集合。该搜索引擎还被配置为使用该前缀集合中的前缀对该存储器执行若干访问，以该前缀集合中的最长前缀作为开始并且以该前缀集合中的前缀长度的降序继续，直至在该路由表中找到具有匹配前缀的条目。该搜索引擎进一步被配置为从该路由表中的该匹配条目获取用于该分组的路由信息。该搜索引擎还被配置为确定所执行的存储器访问的数量超过阈值，并且响应于确定所执行的存储器访问的数量超过阈值，对该存储器中的该路由表进行调适以减少要针对与该网络地址相关联的后续分组所执行的存储器访问的数量。

在其它实施例中，该装置进一步包括以下一个或者多个特征的任意组合。

该多个布隆过滤器中的第一布隆过滤器被配置为表示该路由表中第一长度的前缀。

该第一布隆过滤器包括表示该路由表中第一长度的第一前缀子集的第一布隆过滤器块；以及表示该路由表中第一长度的第二前缀子集的第二布隆过滤器块。

该第一前缀子集并不与该第二前缀子集重叠。

该搜索引擎进一步包括散列函数引擎，其被配置为基于该第一长度的前缀计算散列值。

该搜索引擎进一步被配置为使用该散列值的第一部分选择第一布隆过滤器块或者第二布隆过滤器块；并且使用该散列值的第二部分选择第一布隆过滤器块和第二布隆过滤器块中所选择的一个过滤器块中的位置；并且基于该位置确定该路由表中是否可能存在匹配。

该搜索引擎被配置为至少通过将新条目插入到路由表中来调适该路由表，该新条目是(i)与地址的前缀相关联，其中该前缀比在该存储器中所找到的最长前缀匹配更长，和(ii)包括从该路由表所获取到的路由信息。

调适该路由表在该网络设备的数据面中执行。

在又一个实施例中，一种方法包括在网络设备的搜索引擎配置布隆过滤器，该布隆过滤器具有至少一个布隆过滤器块以表示路由表中一定长度的前缀集合。该方法还包括使用该网络设备的搜索引擎动态调节该布隆过滤器的大小。动态调节该布隆过滤器的大小包括基于与该布隆过滤器相关联的一个或者多个因素确定以下各项之一：(i)该布隆过滤器的大小应当被增大，或者(ii)该布隆过滤器的大小应当被减小；并且响应于确定特定布隆过滤器的大小应当被增大，向该布隆过滤器增加一个或者多个附加布隆过滤器块；以及响应于确定特定布隆过滤器的大小应当被减小，从该布隆过滤器去除一个或者多个布隆过滤器块。

在其它实施例中，该方法进一步包括以下一个或者多个特征的任意组合。

向该布隆过滤器增加一个或者多个附加的布隆过滤器块包括在并不中断该布隆过滤器的操作的情况下增加该一个或者多个附加的布隆过滤器块。

基于与该布隆过滤器相关联的一个或者多个因素确定以下各项之一：(i)该布隆过滤器的大小应当被增大，或者(ii)该布隆过滤器的大小应当被减小，包括针对该布隆过滤器确定错误肯定概率(falsepositiveprobability)；并且在该错误肯定概率超过第一阈值时确定该布隆过滤器的大小应当被增大；并且在该错误肯定概率低于第二阈值时确定该布隆过滤器的大小应当被减小。

该布隆过滤器包括第一布隆过滤器块，并且其中向该布隆过滤器增加一个或者多个附加的布隆过滤器块包括向该布隆过滤器增加第二布隆过滤器块；并且将该第一布隆过滤器块配置为表示该路由表中由该布隆过滤器所表示的前缀集合的第一子集，并且将该第二布隆过滤器块配置为表示该路由表中由该布隆过滤器所表示的前缀集合的第二子集。

将该第一布隆过滤器块配置为表示该路由表中由该布隆过滤器所表示的前缀集合的第一子集，并且将该第二布隆过滤器块配置为表示该路由表中由该布隆过滤器所表示的前缀集合中前缀的第二子集包括将该第一布隆过滤器块的内容复制至该第二布隆过滤器块，针对该前缀集合中的每个前缀计算相应散列值，该散列值具有第一部分和第二部分，使用针对前缀所计算的散列值的第一部分来确定该前缀属于该前缀集合的第一子集还是该前缀集合的第二子集，并且如果确定该前缀属于第一子集，则将该第二布隆过滤器块中的位置设置为指示该前缀并不属于第二子集的数值，其中该位置由该散列值的第二部分所指示；并且如果确定该前缀属于第二子集，则将该第一布隆过滤器块中的位置设置为指示该前缀并不属于第一子集的数值，其中该位置由该散列值的第二部分所指示。

该布隆过滤器包括表示该布隆过滤器所表示的前缀集合的第一子集的第一布隆过滤器块以及表示该布隆过滤器所表示的前缀的第二子集的第二布隆过滤器块。

从该特定布隆过滤器去除一个或者多个布隆过滤器块包括基于该第一布隆过滤器块的内容和该第二布隆过滤器块的内容执行逻辑OR运算，基于该逻辑OR运算配置该第一布隆过滤器块；并且去除该第二布隆过滤器块。

在路由表中以压缩形式存储该前缀集合中的前缀，并且其中针对每个前缀计算相应散列值包括基于根据该压缩形式所压缩的相对应前缀计算相应数值。

在又一个实施例中，一种装置包括用于存储路由表的存储器，该路由表用于转发网络设备中的分组。该装置还包括搜索引擎，该搜索引擎包括被配置为表示该路由表中相应长度的相应前缀集合的多个布隆过滤器，其包括具有被配置为表示该特定布隆过滤器所表示的前缀集合的布隆过滤器块的至少一个第一布隆过滤器。该搜索引擎还包括动态布隆过滤器控制器，其被配置为基于与该第一布隆过滤器相关联的一个或者多个因素确定以下各项之一：(i)该第一布隆过滤器的大小应当被增大，或者(ii)该第一布隆过滤器的大小应当被减小；并且响应于确定该第一布隆过滤器的大小应当被增大，向该第一布隆过滤器增加一个或者多个附加的布隆过滤器块；并且响应于确定该第一布隆过滤器的大小应当被减小，从该第一布隆过滤器去除一个或者多个布隆过滤器块。

在其它实施例中，该装置包括以下一个或者多个特征的任意组合。

该动态布隆过滤器被配置为在并不中断该布隆过滤器的操作的情况下向该布隆过滤器增加一个或者多个附加的布隆过滤器块。

该动态布隆过滤器控制器进一步被配置为针对该第一布隆过滤器确定错误肯定概率，并且在该错误肯定概率超过第一阈值时确定该第一布隆过滤器的大小应当被增大，并且在该错误肯定概率低于第二阈值时确定该第一布隆过滤器的大小应当被减小。

该第一布隆过滤器包括第一布隆过滤器块，并且其中该动态布隆过滤器控制器被配置为响应于确定该布隆过滤器的大小应当被增大而向该第一布隆过滤器增加第二布隆过滤器块，将该第一布隆过滤器块配置为表示该路由表中由该第一布隆过滤器所表示的前缀集合的第一子集，并且将该第二布隆过滤器块配置为表示该路由表中由该第一布隆过滤器所表示的前缀集合的第二子集。

动态布隆过滤器控制器进一步被配置为将第一布隆过滤器块的内容复制到第二布隆过滤器块，针对该前缀集合中的每个前缀获得相应散列值，该散列值具有第一部分和第二部分，使用针对前缀所计算的散列值的第一部分来确定该前缀属于该前缀集合的第一子集还是该前缀集合的第二子集，并且如果确定该前缀属于第一子集，则将该第二布隆过滤器块中的位置设置为指示该前缀并不属于第二子集的数值，其中该位置由该散列值的第二部分所指示；并且如果确定该前缀属于第二子集，则将该第一布隆过滤器块中的位置设置为指示该前缀并不属于第一子集的数值，其中该位置由该散列值的第二部分所指示。

该第一布隆过滤器包括表示由该布隆过滤器所表示的前缀集合的第一子集的第一布隆过滤器块以及表示由该布隆过滤器所表示的前缀的第二子集的第二布隆过滤器块。

该动态布隆过滤器控制器被配置为响应于确定该第一布隆过滤器的大小应当被减小而获得基于该第一布隆过滤器块的内容和第二布隆过滤器块的内容所执行的逻辑OR操作的结果，基于该逻辑OR操作配置该第一布隆过滤器块；并且去除该第二布隆过滤器块。

该存储器被配置为以压缩形式存储该前缀集合中的前缀。

每个前缀的相应散列值基于根据该压缩形式所压缩的相对应前缀进行计算。

附图说明

图1是根据一个实施例的被配置为采用本公开的最长前缀匹配技术的示例网络设备的简化框图；

图2是根据一个实施例的被用作图1的网络设备的布隆过滤器系统的示例布隆过滤器系统的框图；

图3是根据另一个实施例的被用作图1的网络设备的布隆过滤器系统的示例布隆过滤器系统的框图；

图4A-4C是描绘根据一个实施例的用于增大布隆过滤器的大小的过程400的示图；

图5是根据一个实施例的利用自适应(adaptive)模式以响应于检测到路由表中所执行的低效查找而对路由表进行调适的系统的示图；

图6A-6D是根据一些实施例的在路由表中使用的示例压缩条目的示图；

图7是根据一个实施例的用于在存储用于转发网络设备中的分组的路由表的存储器中执行最长前缀匹配查找操作的示例方法的流程图；

图8是根据一个实施例的用于对布隆过滤器的大小进行动态调节的示例方法的流程图。

具体实施方式

图1是根据一个实施例的被配置为采用本公开的最长前缀匹配技术的示例网络设备100的简化框图。网络设备100通常是连接两个或者更多计算机系统、网络分段、子网等的计算机联网设备。例如，网络设备100在一个实施例中是路由器。然而，注意到，网络设备100并非必然被局限于特定协议层或者特定联网技术(例如，以太网)。例如，在其它实施例中，网络设备100是桥、交换机、VPN集线器等。

网络设备100包括分组处理器(或者其它适当网络处理器)102，并且网络处理器102进而包括耦合至处理引擎106的分组处理元件(PPE)或者分组处理节点(PPN)104。虽然，在图1中为了简明仅图示了一个PPE104并且仅图示了一个处理引擎106，但是在一些实施例中，网络处理器102包括其它适当数量(例如，2、3、4、5等)的PPE104和/或者处理引擎106。在这样的实施例中，PPE104和处理引擎106以任意适当的并行或者管道布置形式进行布置。例如，在一个实施例中，在并行处理布置形式中，PPE104是分组处理器102中所包括的被配置为对网络设备100所接收的相应分组并行执行处理操作的多个PPE之一。根据一个实施例，处理引擎106是分组处理元件104之外并且专用于针对分组处理元件104所处理的分组执行某些—例如计算密集的—处理操作的多个专用处理引擎之一。例如，在一个实施例中，多个PPE104被配置为使用存储在非暂态存储器(未示出)中的计算机可读指令对分组进行处理，并且处理引擎106使用一个或者多个应用特定集成电路(ASIC)或者其它硬件部件来实施。在一些实施例中所使用的若干示例并行分组处理布置在于2013年11月27日提交的美国专利申请号14/092,521中有所描述，其通过引用全文结合于此。在一些实施例中所使用的若干示例并行分组处理布置在于2013年12月20日提交的美国专利申请号14/137,571中有所描述，其通过引用全文结合于此。

作为另一个示例，在串行分组处理架构中，根据一个实施例，PPE104是以串行的管道布置形式进行布置的多个PPE之一，其中每个PPE104被配置为对分组执行一种或者多种分组处理操作并且将该分组送至下一个PPE以便对该分组进行进一步处理。例如，在一些这样的实施例中，PPE104被配置为基于与分组相关联的分组情境(context)对该分组进行串行处理，并且有选择地采用处理引擎106以便对分组执行某些动作。作为另一个示例，PPE104和处理引擎106使用ASIC或者其它硬件部件来实施，并且以任意适当的串行或者并行布置形式进行配置以对分组执行某些处理操作。

网络设备100还包括耦合至网络处理器102的多个网络端口112，并且每个网络端口112经由相应通信链路耦合至通信网络和/或者通信网络内的另一个适当网络设备。一般来讲，分组处理器102被配置为对经由入口(ingress)端口112所接收的分组进行处理，确定要经由其传送分组的相应出口(egress)端口112，并且使得分组经由所确定的出口端口112进行传送。在一些实施例中，分组处理器102对与分组相关联的分组描述符而不是分组本身进行处理。在一个实施例中，分组描述符包括来自分组的一些信息，诸如分组的一些或者全部报头信息，和/或者包括由网络设备100针对分组所生成的信息。在一些实施例中，分组描述符也包括其它信息，诸如该分组在与网络设备100相关联的存储器中存储在何处的指示符。为了便于解释，术语“分组”在这里被用来指代分组自身或者与分组相关联的分组描述符。另外，如这里所使用的，术语“分组处理元件(PPE)”和术语“分组处理节点(PPN)”被互换使用以指代被配置为对网络设备100所接收的分组执行分组处理操作的处理单元。

在一个实施例中，处理引擎106是被配置为基于与分组相关联的地址而针对分组执行最长前缀匹配查找的搜索引擎。外部引擎106在本文中有时候被称为“LPM引擎”。外部引擎106耦合至路由表或者数据库108。在一个实施例中，路由表108存储网络地址与关联于该网络地址的分组应当从网络设备被传送至哪里的下一跳之间的关联。在至少一些实施例中，路由表108存储附加的信息，诸如用来将分组传送至下一跳的网络设备100的接口(例如，端口112)。搜索引擎106被配置为从分组的报头获得诸如IP地址(例如，32位的IPv4地址或者128位的IPv6地址)的地址，并且基于该地址在路由表108中执行查找以在路由表108中找出具有该地址的最长匹配前缀的条目。根据一个实施例，如果在路由表108中找到了匹配条目，则搜索引擎106从路由表108中的该匹配条目获取路由信息并且将该路由信息提供至PPE104。在一个实施例中，PPE104使用该路由信息作出关于该分组的转发决策，诸如确定该分组应当被转发至哪个端口112以便对该分组进行传输。

在一个实施例中，路由表108被存储在处理引擎106之外的存储器中。在另一个实施例中，路由表108被存储在处理引擎106内部的存储器中。在一个实施例中，例如，路由表108被存储在随机访问存储器中，诸如动态随机访问存储器(DRAM)或者静态随机访问存储器(SRAM)。在各个实施例中，路由表108以任意适当方式进行构造，并且路由表108中的查找使用任意适当搜索技术来执行。在一些实施例中所使用的用于执行查找以便在路由表108中执行查找的一些示例技术在于2013年1月9日提交的美国专利申请号13/737,608中有所描述，其通过引用全文结合于此。

在一个实施例中，搜索引擎106包括动态布隆过滤器系统110、布隆过滤器控制器114和自适应模式控制器116。动态布隆过滤器系统110包括布隆过滤器118的集合。在一个实施例中，至少一些布隆过滤器118中的每一个过滤器与路由表108中的特定前缀长度相关联。在一个实施例中，所有或者基本上所有的布隆过滤器118与路由表108中特定长度的前缀相关联。在另一个实施例中，一些但并非全部布隆过滤器118与路由表108中特定长度的前缀相关联，并且如以下将更为详细描述的，在至少一些实施例中，其余布隆过滤器118则是可用于对布隆过滤器118的大小进行动态调节的布隆过滤器块。在一个实施例中，与特定前缀长度相关联的布隆过滤器118被配置为接收特定长度的前缀并且提供(i)该前缀在路由表108中可能具有匹配还是(ii)该前缀在路由表108中肯定没有匹配的指示。为此，在一个实施例中，布隆过滤器118被“编程”为表示存储在路由表108中的特定长度的前缀的集合。当搜索引擎106接收到地址时，搜索引擎106使用该地址的相应前缀对布隆过滤器118执行并行查询，并且针对该地址的相应前缀获得相应的肯定或者否定指示。在一个实施例中，前缀的否定指示表示该前缀在路由表108中肯定没有匹配。另一方面，在一个实施例中，前缀的肯定指示表示该前缀在路由表108中可能但并非肯定具有匹配。也就是说，在该实施例中，前缀的肯定指示在一些情况下可能是错误肯定指示，并且在一些实施例和情形中，搜索引擎106对路由表108执行一个或者多个存储器访问以消除从布隆过滤器系统200所获得的这样的错误肯定指示。

在一个实施例中，搜索引擎106通过使用被指示为可能在路由表108中具有匹配的前缀访问路由表108而在路由表108中执行查找。在一个实施例中，查找操作以被指示为可能在路由表108中具有匹配的最长前缀作为开始，并且在必要情况下，以被指示为可能在路由表108中具有匹配的相继更短的前缀继续进行，直至(i)在路由表108中找到匹配或者(ii)所有被指示为可能具有匹配的前缀都被排除并且没有在路由表108中找到匹配。根据一个实施例，在各个实施例和/或者情形中，布隆过滤器系统110一般针对大多数或者基本上所有的地址产生相对少量的错误肯定指示，由此确保最多有相对少量的存储器访问需要基于该地址在查找操作期间由搜索引擎106执行，并且与并不采用布隆过滤器的搜索引擎实施方式(诸如基于特里的算法搜索实施方式)相比减少搜索引擎106通过执行查找操作而引入的延时。然而，在至少一些实施例中，针对一些地址，布隆过滤器系统110产生相对大量的错误肯定指示，在一些实施例和情形中，这可能致使搜索引擎106在查找操作期间基于这样的地址执行大量存储器访问，可能导致搜索引擎106与并不采用布隆过滤器的搜索引擎实施方式(诸如基于特里的算法搜索实施方式)相比引入更高延时。

一般来讲，布隆过滤器的错误肯定概率与布隆过滤器的填充水平(filllevel)正向相关，并且与过滤器大小反向相关。布隆过滤器的填充水平一般取决于与路由表108中所存储的布隆过滤器相关联的长度的前缀的数量。在至少一些实施例和情形中，由于各种长度的前缀在路由表108中的非均匀分布，一些布隆过滤器118在路由表108中表示比其它布隆过滤器更大的前缀集合。在一个实施例中，搜索引擎106的布隆过滤器控制器114对布隆过滤器118的大小进行动态调节以保持相应布隆过滤器118的适当低的错误肯定概率，同时有效地利用诸如存储器资源之类的可供布隆过滤器系统110所使用的资源。例如，根据一个实施例，布隆过滤器控制器114监视布隆过滤器118以确定特定布隆过滤器118何时例如由于布隆过滤器118所表示的集合中的前缀数量的增加而应当被扩展，或者相反地，特定布隆过滤器118的大小何时例如由于布隆过滤器118所表示的前缀集合中的前缀数量的减少而应当被减小。例如，在一个实施例中，控制器114例如基于针对布隆过滤器118或者针对布隆过滤器118的集合所收集的统计而存储或者确定i)用于确定布隆过滤器118的大小应当被增加的第一错误肯定概率阈值水平以及ii)用于确定布隆过滤器118的大小应当被减小的第二错误肯定概率阈值水平。在一个实施例中，控制器114在与特定布隆过滤器118相关联的错误肯定概率超过第一阈值水平时确定该特定布隆过滤器118的大小应当被增大，并且在与特定布隆过滤器118相关联的错误肯定概率低于第二阈值水平时确定该特定布隆过滤器118的大小应当被减小。

在一个实施例中，控制器114随后相应地进行动作以增大或者相反地进行动作以减小特定布隆过滤器118的大小。在至少一些实施例和情形中，增大布隆过滤器118的大小降低了该布隆过滤器118的错误肯定概率。在至少一些情形中，降低错误肯定概率减少了搜索引擎106在针对地址的查找操作期间对路由表108所执行的访问的数量。在至少一些实施例和/或者情形中，由于在查找操作期间所需要执行的存储器访问更少，所以由搜索引擎106执行的搜索操作所引入的延时也有所减少。另一方面，在至少一些实施例和情形中，减小布隆过滤器118的大小允许系统110的存储器资源有效地被利用。

在一些实施例中，即使在布隆过滤器118的大小被动态调节以总体上针对布隆过滤器118保持适当低的错误肯定概率时，提供给布隆过滤器系统110的一些地址也导致了从布隆过滤器系统110所获得的相对大量的错误肯定指示。在一些实施例和/或者情形中，针对这样的地址的查找涉及到对路由表108可能大量的存储器访问。在一个实施例中，搜索引擎106的自适应模式控制器116被配置为检测路由表108中针对其的查找需要对路由表108进行大量访问并且导致在路由表108中找到匹配的这样的地址。在一个实施例中，响应于检测到这样的地址，该自适应模式控制器进行操作以对路由表108进行调适以减少针对后续基于该地址所执行的查找而对路由表108所要执行的存储器访问的数量。例如，当自适应模式控制器116检测到需要大量(例如，超过预定阈值)存储器访问的地址时，自适应模式控制器116向PPE104提供反馈126，其向PPE104指示基于该网络地址对路由表108执行了大量的访问。在一个实施例中，PPE104随后向搜索引擎106发送指令128，其指示搜索引擎106对路由表108进行调适以减少搜索引擎106在基于相同网络地址的后续查找期间将需要执行的访问数量。以下关于图5对实施根据实施例和说明性情形的自适应模式的示例系统进行更为详细地描述。

继续参考图1，在一个实施例中，耦合至路由表108和搜索引擎106的路由更新单元120被配置为诸如在与前缀相关联的新路由被网络设备100所学习时通过将新的条目插入到路由表108中而更新路由表108，或者相反地，例如在条目在某个时间段内并没有被访问时通过从路由表108删除该条目而更新路由表108。在一个实施例中，当更新单元120将与前缀相关联的新条目插入到路由表108中时，更新单元120将该前缀提供至搜索引擎106。搜索引擎106更新布隆过滤器系统110以指示该前缀存在于路由表108中。特别地，与该前缀的前缀长度相关联的布隆过滤器118被更新以在利用该前缀进行查询时提供肯定指示。此外，路由更新单元120对计数布隆过滤器122中的相对应计数器进行递增。相反地，当从路由表108删除条目时，更新单元120对计数布隆过滤器122中相对应的计数器124进行递减。维护对应于布隆过滤器118的计数器124允许路由更新单元120随后在布隆过滤器118的位置所表示的所有条目都已经从路由表108被删除时对相对应的布隆过滤器118进行更新。

在一些实施例中，网络设备100包括处理器132，其执行包括在处理器132之中或者与之耦合的存储器设备136中所存储的机器可读指令。在一些实施例中，处理器132包括中央处理器(CPU)。在一些实施例中，处理器132耦合至搜索引擎106和路由表108。在各个实施例中，处理器132执行与以下的一个或者多个相关联的功能，i)更新路由表108，ii)动态调节布隆过滤器118的大小，和iii)基于来自自适应模式控制器114的反馈调适路由表108。在一个实施例中，更新单元120的一部分由处理器132所实施。在一个实施例中，整个更新单元由处理器132所实施。在一些实施例中，处理器132并不执行与路由表108的更新相关联的任何功能。

图2是根据一个实施例的随图1的网络设备100所采用的示例布隆过滤器系统200的框图。出于说明的目的，参考图1的网络设备100对示例的布隆过滤器系统200进行讨论。然而，在其它实施例中，布隆过滤器系统200在不同于图1的示例网络设备100的适当网络设备中被采用。类似地，在一些实施例中，图1的网络设备100采用布隆过滤器系统200以外的布隆过滤器系统。

布隆过滤器系统200包括多个布隆过滤器202，每个布隆过滤器202与路由表108中所存储的特定长度的前缀集合相关联。在图2的示例实施例中，系统200包括33个布隆过滤器202，每个布隆过滤器202与32位的IPv4地址的相应前缀相关联。在其它实施例中，布隆过滤器系统200包括其它适当数量(例如，小于32的适当数量或者大于32的适当数量)的布隆过滤器202。例如，在其中系统200被配置为随129位的IPv6地址进行操作的实施例中，系统200包括129个布隆过滤器202或者小于129的适当数量的布隆过滤器202，例如，在一些实施例中，当并非128位地址的所有可能前缀都被网络设备100所支持时(例如，仅128位地址中的64位被用作地址的前缀)。可替换地，布隆过滤器系统200包括数量超过网络设备100所支持的前缀长度的数量的布隆过滤器，例如，在一些实施例中，用于布隆过滤器系统200在网络设备100的操作期间的动态扩展。

在一个实施例中，布隆过滤器系统200包括多个布隆过滤器块204。在一个实施例中，每个布隆过滤器块204是分离的随机访问存储器(RAM)设备，或者是RAM设备的相应部分。在一个实施例中，每个布隆过滤器202包括一个或者多个布隆过滤器块204。在图2所示的示例实施例和情形中，布隆过滤器202a包括单个布隆过滤器块204a，布隆过滤器202b包括两个布隆过滤器块204b和204c，并且布隆过滤器202c包括单个布隆过滤器块202d。在一个实施例中，布隆过滤器202中的布隆过滤器块204的数量决定了布隆过滤器202的大小。因此，例如，在一个实施例中，包括两个布隆过滤器块204的布隆过滤器202是包括一个布隆过滤器块204的布隆过滤器202的两倍长。类似地，在一个实施例中，包括四个布隆过滤器块204的布隆过滤器202是包括两个布隆过滤器块204的布隆过滤器202的两倍长，并且是包括一个布隆过滤器块204的布隆过滤器202的四倍长。在一个实施例中，布隆过滤器202中的布隆过滤器块204的数量一般决定了布隆过滤器202的大小。在一个实施例中，布隆过滤器202中的布隆过滤器块204的数量在布隆过滤器系统200的操作期间进行动态调节。例如，在一个实施例中，布隆过滤器202的大小被增大以降低布隆过滤器202的错误肯定概率。相反地，在一个实施例中，例如在布隆过滤器202所表示的前缀集合有所减小时减小布隆过滤器202的大小以使得与布隆过滤器202相关联的一个或者多个布隆过滤器块204能够随其它布隆过滤器202使用。

在一个实施例中，在布隆过滤器系统200的操作期间，动态布隆过滤器控制器114(图1)被配置为对布隆过滤器202中的布隆过滤器块204的数量进行动态调节，并且相应地对布隆过滤器202的大小进行动态调节。例如，在一个实施例中，在布隆过滤器系统200的操作期间，动态布隆过滤器控制器114检测到特定布隆过滤器202应当被扩展，以例如保持布隆过滤器202适当低的错误肯定率。如将要在下文中更为详细描述的，在一个实施例中，控制器114随后进行操作以通过向布隆过滤器202增加一个或者多个附加布隆过滤器块204并且对布隆过滤器202进行重新编程而使得布隆过滤器202中所包括的每个布隆过滤器块204表示由布隆过滤器202所表示的前缀集合的更小子集来对布隆过滤器202的大小进行扩展。相反地，在一个实施例中，动态布隆过滤器控制器114检测到某个布隆过滤器202对于路由表108中所存储的相对应长度的前缀的数量而言过大。在这种情况下，如将要在下文中更为详细描述的，在一个实施例中，控制器114进行操作以通过去除一个或者多个布隆过滤器块204，并且根据布隆过滤器202所表示的前缀集合对其余布隆过滤器块204进行重新编程来减少布隆过滤器202的数量。

布隆过滤器系统200包括耦合至多个布隆过滤器块204的多个散列函数引擎206。在一个实施例中，散列函数引擎206被配置为接收网络地址的相应前缀208并且针对该网络地址的前缀208生成相应散列值。例如，在一个实施例中，搜索引擎106包括地址解析单元(未示出)，其接收地址并且对该地址进行操控以生成地址的各种长度的前缀。在一些实施例中，该地址解析单元还对所生成的地址的前缀进行操控，以例如适当压缩该前缀从而对应于路由表108中所存储的压缩前缀。在一个实施例中，每个(未压缩或者被压缩的)前缀随后被提供至相对应的散列函数引擎206。可替换地，在另一个实施例中，每个散列函数引擎206接收该地址，生成该地址的相应前缀，并且在必要情况下对该地址进行操控(例如，压缩)，并且基于该地址的(未压缩或者被压缩的)前缀生成相应散列值210。

仍然参考图2，在一个实施例中，散列值20被用来访问相应布隆过滤器202。在一个实施例中，散列值210中的一个或者多个位被用来从布隆过滤器202中所包括的多个布隆过滤器块204中选择布隆过滤器块204，并且散列值210的一个或者多个最低有效位被用来指示所选择的布隆过滤器块204中的位置。在图2的实施例中，散列值210的五个最高有效位(MSB)被用来选择布隆过滤器块204。在一个实施例中，如果布隆过滤器202仅包括一个布隆过滤器块204，则这一个布隆过滤器块204无论这五个最高有效位的数值如何都被选择。另一方面，在一个实施例中，如果布隆过滤器202包括多个布隆过滤器块204，则MSB的相应数值被指定给该多个布隆过滤器块204中的每一个。例如，在一个实施例中，如果布隆过滤器包括两个布隆过滤器块204，则散列值210的五个最高有效位的数值“XXXX0”选择第一布隆过滤器块204而数值“XXXX1”则选择第二布隆过滤器块204，其中X表示“不关注”位。在一个实施例中，这五个最高有效位最右侧的位被用来在布隆过滤器202的两个布隆过滤器块204中进行选择，这五个最高有效位最右侧的两位被用来在布隆过滤器202的四个布隆过滤器块204中进行选择，这五个最高有效位最右侧的三位被用来在布隆过滤器202的八个布隆过滤器块204中进行选择，等等。在图2的示例实施例中，基于前缀“Address/x”所生成的散列值201的数值“XXXX0”选择布隆过滤器202b的布隆过滤器块204b，并且基于前缀“Address/x”所生成的散列值201的数值“XXXX1”选择布隆过滤器202b的布隆过滤器块204c。在其中使用五个位在布隆过滤器202的多个布隆过滤器块204中进行选择的实施例中，系统200能够在最多32个布隆过滤器块204中进行选择。在其它实施例中，使用散列值210中其它适当数量的位和/或者其它适当的位位置(bitlocation)在布隆过滤器202的多个布隆过滤器204中进行选择。

在一些实施例中，多个散列函数引擎206与布隆过滤器块204相关联并且被用来访问布隆过滤器块204。多个散列函数引擎206接收前缀并且基于所接收到的前缀计算相应散列值。在一个实施例中，搜索引擎106根据使用多个散列值访问单个布隆过滤器块204的适当方案来访问布隆过滤器块。一般来讲，使用单个散列函数所访问的布隆过滤器与使用多个散列函数进行访问的相同布隆过滤器的错误肯定概率相比具有更大的错误肯定概率。然而，使用多个散列值访问单个布隆过滤器通常要求使用更高带宽的存储器来存储布隆过滤器。在一个实施例中，布隆过滤器中所包括的多个布隆过滤器块通常与该布隆过滤器中所包括的布隆过滤器块的数量成比例地增大存储器带宽。由于每个布隆过滤器块使用相应散列值进行访问，所以在至少一些实施例中，具有多个布隆过滤器块的布隆过滤器与存储在单个存储器中的相同大小的布隆过滤器相比具有较低的错误肯定概率。因此，在至少一些实施例中，将布隆过滤器202划分为多个布隆过滤器块204通常降低了布隆过滤器202的错误肯定概率。

在任意情况下，布隆过滤器204的输出被提供至决议模块212，其选择每个布隆过滤器202的相应输出并且生成指示哪个或者哪些前缀206可能在路由表108中具有匹配的位矢量214。例如，位矢量214包括对应于被用来查询布隆过滤器202的每个前缀长度的位。在一个实施例中，对应于特定布隆过滤器202的位被设置为逻辑1以指示该布隆过滤器202针对提供至该布隆过滤器202的前缀206返回了肯定指示，或者并且被设置为逻辑0以指示该布隆过滤器202针对提供给该布隆过滤器202的前缀206返回了否定指示，或者反之亦然。搜索引擎106利用位矢量214确定哪个或者哪些前缀206应当被用来在查找操作中访问路由表206以在路由表108中找出最长前缀匹配。例如，以最长的一个前缀作为开始，并且在必要情况下以前缀长度的降序所继续，搜索引擎106使用被位矢量214指示为可能在路由表108中具有匹配的索引来访问路由表。该查找操作在路由表108中找到匹配索引时或者在位矢量214所指示为可能具有匹配的所有前缀都被用来访问路由表108并且没有在路由表108中找到匹配时完成。在一个实施例中，如果该查找操作在路由表108中找到匹配，则搜索引擎106从路由表108中的匹配条目获取路由并且将该路由信息提供至PPE104。

暂时转向图3，该图是根据另一个实施例的被用作图1的网络设备100的布隆过滤器系统110的示例布隆过滤器300的框图。布隆过滤器系统300类似于图2的布隆过滤器系统200，区别在于与图2的布隆过滤器系统200中的每个布隆过滤器块204的分离散列函数引擎206相比，布隆过滤器系统300针对每一个布隆过滤器202仅包括一个散列引擎306。在一个实施例中，散列函数引擎306接收地址或者接收地址的相应前缀，并且基于该地址的相应前缀生成相应散列值310。散列引擎306的输出被耦合至布隆过滤器接口单元304，布隆过滤器接口单元304将散列值310的LSB数值指向适当的布隆过滤器块302。例如，在一个实施例中，接口单元304基于与布隆过滤器块204相关联的前缀长度和/或者基于散列值310的MSB选择布隆过滤器块204。在其它实施例中，布隆过滤器系统300包括其它适当数量的散列函数引擎306。一般来讲，布隆过滤器系统300包括N个散列函数引擎306和X个布隆过滤器202，其中N和X在一个实施例中是正整数。在该实施例中，接口单元304将N个散列函数306连接至X个布隆过滤器202。

图4A-4C是描绘根据一个实施例的用于增大布隆过滤器的大小的示例过程400的不同阶段的示图。在一个实施例中，过程400随图1的网络设备100使用。例如，参考图1，在一个实施例中，过程400至少部分由BF控制器114所执行。继续参考图1，在一些实施例中，过程400至少部分由分组处理元件104和/或者路由更新单元120执行。为了便于解释，以下结合图1的网络设备100对过程400进行描述。

首先参考图4A，布隆过滤器402包括耦合至散列函数引擎406a的单个布隆过滤器块404a。布隆过滤器块404a被配置为表示路由表108中长度为x的前缀的集合。在一个实施例中，布隆过滤器404a的所有位都被设置为诸如逻辑0的缺省值。当长度为x的前缀被插入路由表108之中时，该前缀被提供至散列函数引擎406a。散列函数引擎406a接收该前缀并且基于该前缀计算散列值410。散列值410包括一个或者多个最高有效位412的集合以及一个或者多个最低有效位414的集合。在一个实施例中，最高有效位412选择布隆过滤器404a的布隆过滤器块404。由于布隆过滤器402仅包括一个布隆过滤器块404a，所以布隆过滤器块404a无论最高有效位412的数值如何都被选择。最低有效位414指示所选择的布隆过滤器块404a中的位置。在一个实施例中，布隆过滤器块404a中被指示的位置被设置为某个逻辑数值(例如，逻辑1)以指示前缀408在路由表108中所存储的长度为x的前缀集合中的成员资格。在一个实施例中，随着更多前缀被插入到路由表108，布隆过滤器块404a的填充水平(即，被设置为逻辑1的位的数量)有所增加。一般来讲，布隆过滤器402的错误肯定概率直接与布隆过滤器402所表示的前缀的数量成比例，并且与布隆过滤器402中的位总数成反比。因此，对于布隆过滤器块404a中给定数量的位而言，随着布隆过滤器块404a所表示的前缀的数量增加，布隆过滤器402的错误肯定概率也有所增加。

在图4B中，控制器114已经检测到布隆过滤器块404a的大小不足以表示当前存储在路由表108中的长度为x的前缀的集合。例如，在一个实施例中，控制器114基于布隆过滤器402中的位的数量以及布隆过滤器402所表示的长度为x的前缀的数量，或者布隆过滤器402中被设置为逻辑1的位的数量来计算布隆过滤器402的错误肯定概率。控制器114将所计算的错误肯定概率与预定阈值进行比较，并且在所计算的错误肯定概率超过该预定阈值时检测到布隆过滤器402的大小应当被增大。在另一个实施例中，控制器114(或者另一个设备)例如基于布隆过滤器402的操作或者基于布隆过滤器集合的操作而收集错误概率统计，并且利用所收集到的统计来确定布隆过滤器402的大小应当被增大。

在一个实施例中，响应于检测到布隆过滤器块404a的大小不足，控制器114将附加的块404b增加至布隆过滤器402。将附加的布隆过滤器404b增加至布隆过滤器402使得布隆过滤器402中的位的数量有所增加，因此针对路由表108中所存储的长度为x的相同前缀集合减小布隆过滤器402的错误肯定概率。控制器114随后将布隆过滤器块404a的内容复制到布隆过滤器块404b。控制器114随后将最高有效位412的第一个数值指定给第一布隆过滤器块404a并且将最高有效位412的第二个数值指定给第二布隆过滤器块404b，并且使能布隆过滤器块404b。在至少一个实施例中，由于布隆过滤器块404a的内容在使用相应数值选择布隆过滤器块404a、404b中特定的一个之前被复制到布隆过滤器块404b，所以包括布隆过滤器402的过滤器系统的操作在布隆过滤器402的扩展处理期间无需被中断。换言之，由于在过程400的该阶段，布隆过滤器块404a和布隆过滤器块404b表示路由表108中长度为x的前缀的集合，所以选择块404a或者404b将产生特定前缀是否可能存储在路由表108中的指示。因此，针对给定前缀，布隆过滤器402无论针对该前缀所生成的散列值410的MSB位412的数值如何，并且因此无论基于该前缀的散列值选择了块404a和404b中的哪一个，都将提供该前缀在路由表108中是否具有匹配的相同指示。

在一个实施例中，控制器114随后对布隆过滤器块404a、404b进行重新配置以表示布隆过滤器402所表示的前缀集合中相应的无重叠子集。作为将布隆过滤器块404a的内容复制到布隆过滤器块404b，将相应选择数值指定给布隆过滤器块404a、404b，使能布隆过滤器块404b，并且随后重新配置布隆过滤器块404a、404b的一种替换形式，在另一个实施例中，控制器114在向布隆过滤器块404a、404b指定相应选择数值并且使能布隆过滤器块404b之前对布隆过滤器块404b进行配置以表示布隆过滤器402所表示的前缀集合的子集。随后，在一个实施例中，在使能布隆过滤器块404b之后，控制器114重新配置布隆过滤器块404a以表示并未由布隆过滤器块404b所表示的前缀的子集。类似于以上所描述的实施方式，在该实施例中，包括布隆过滤器402的布隆过滤器系统的操作在布隆过滤器402的扩展处理期间无需被中断。在一个实施例中，为了重新配置布隆过滤器块404a和404b，控制器114一般将布隆过滤器块404a和404b中分别对应于布隆过滤器块404a、404b所表示的前缀子集的位的位置设置为逻辑1，并且将布隆过滤器块404a、404b中的其余位的位置设置为逻辑0，或者反之亦然。参考图4c对根据一个实施例的重新配置布隆过滤器块404a、404b的示例过程进行更为详细地描述。

现在参考图4c，布隆过滤器块404a和404b被重新配置为使得块404a和404b中的每一个表示路由表108中所存储的长度为x的前缀的集合中的子集。特别地，在一个实施例中，布隆过滤器块404a被重新编程为表示被散列为MSB412的数值“XXXX0”的长度为x的前缀的子集，并且布隆过滤器块404a被重新编程为表示被散列为MSB412的数值“XXXX1”的长度的前缀的子集。在一个实施例中，对布隆过滤器块404a、404b重新编程涉及到针对路由表108中所存储的长度为x的前缀的集合重新计算散列值。在一个实施例中，路由更新单元120在重新配置布隆过滤器块404a、404b时进行辅助。例如，路由表更新单元120针对路由表108中所存储的长度为x的前缀重新计算散列值，并且基于重新计算的散列值重新配置布隆过滤器块404a、404b。在另一个实施例中，更新单元120针对路由表108中所存储的长度为x的前缀的相应集合保持相应的计数布隆过滤器。在该实施例中，该更新单元无需针对前缀集合重新计算散列值。相反，更新单元108基于更新单元120所保持的计数布隆过滤器的相应集合重新配置布隆过滤器块404a、404b。

为了重新配置布隆过滤器块404a、404b，在一个实施例中，更新单元120根据路由表108中所存储的长度为z的前缀的散列值，将布隆过滤器块404a、404b中对应于布隆过滤器块404a、404b中的另外一个所表示的前缀集合的位置的位设置为逻辑0。特别地，针对被散列为MSB412的数值“XXXX0”的前缀子集，布隆过滤器块404b中相对应的位的位置被重置为逻辑0。类似地，针对被散列为MSB412的数值“XXXX1”的前缀子集，布隆过滤器块404a中相对应的位的位置被重置为逻辑0。在一个实施例中，在所产生的布隆过滤器402中，被设置为1的位与布隆过滤器402中的位总数的比率有所减小，因此，布隆过滤器402的错误肯定概率有所下降。

在一个实施例中，为了减小布隆过滤器的大小，诸如路由更新单元120的主机设备执行OR运算以将布隆过滤器中的多个布隆过滤器块的内容进行合并，并且基于针对布隆过滤器的多个块所执行的OR运算的结果对该布隆过滤器的布隆过滤器块之一进行重新配置。作为结果，单个布隆过滤器块被配置为表示布隆过滤器的多个布隆过滤器块之前所表示的长度为x的前缀的集合。因此，例如，仍然参考图4c，在示例情形中，控制器114检测到布隆过滤器402的大小应当有所减小。例如，在一个实施例中，控制器114在针对布隆过滤器402所计算或者统计确定的布隆过滤器402的错误肯定概率低于预定阈值时检测到布隆过滤器402的大小应当有所减小。控制器114随后向路由更新单元120指示布隆过滤器402的大小应当有所减小。路由更新单元120对布隆过滤器块404a、404b的相对应的位执行OR运算。该OR运算的结果被用来重新配置块404a，并且随后从布隆过滤器402移除块404b。例如，在一个实施例中，控制器114去除块404b和长度为x的前缀的集合之间的关联，并且将MSB412的数值XXXXX指定给块404a。在一个实施例中，现在块404b能够被添加至布隆过滤器集合111中的另一个布隆过滤器。

图5是根据一个实施例的响应于检测到路由表中所执行的低效查找利用自适应模式对路由表进行调适的系统500的示图，上述低效查找诸如与针对路由表的相对大量的存储器访问相关联的查找。在一个实施例中，系统500随图1的网络设备100一起被利用。如图5所示，系统500包括耦合至路由表508的搜索引擎506。搜索引擎506包括布隆过滤器系统510和自适应控制器511。参考图1和图5，在一个实施例中，搜索引擎506对应于搜索引擎106并且路由表510对应于路由表108。继续参考图1和图5，在一个实施例中，布隆过滤器系统510对应于布隆过滤器系统110，并且自适应控制器511对应于自适应控制器116。

在图5的示例情形中，搜索引擎506从分组处理器元件(例如，从图1的分组处理元件104)获得网络地址502。网络地址502例如是IPv4地址。网络地址502在图5中使用四元带点表示形式被图示为地址1.2.3.4。搜索引擎506将地址502提供至布隆过滤器系统510。响应于接收到地址502，布隆过滤器510返回可能在路由表508中具有匹配的地址502的前缀512的集合。特别地，在图5所示的示例情形中，前缀512的集合包括前缀1.2.3.0/28、1.2.3.0/24、1.2.0.0/16和1.0.0.0/8。

如以上所讨论的，在一些实施例中，从布隆过滤器所获得的指示特定前缀可能在路由表中具有匹配的肯定指示可能是错误肯定指示。因此，搜索引擎506可能需要对路由表508执行多个存储器访问以便找出路由表508中的匹配或者确定路由表508中并不存在匹配。搜索引擎506使用前缀512的集合中的最长前缀1.2.3.0/28对路由表508执行第一存储器访问516。第一存储器访问516并未找到前缀1.2.3.0/28的匹配。搜索引擎506随后使用前缀512的集合中的下一个最长前缀1.2.3.0/24执行第二存储器访问518。第二存储器访问518并未在路由表508中找到前缀1.2.3.0/24的匹配。类似地，使用第三最长前缀1.2.0.0/16所执行的第三存储器访问520并未在路由表508中找到前缀1.2.0.0/16的匹配。搜索引擎506随后使用前缀512的集合中的第四最长前缀1.0.0.0/8执行第四存储器访问522。第四存储器访问522在路由表508中找到了前缀1.0.0.0/8的匹配条目523。在一个实施例中，搜索引擎506从匹配条目523得出路由信息524(例如，下一跳指示符)，并且将路由信息524提供至提供地址502的分组处理元件，诸如分组处理元件104。

继续参考图5，在一个实施例中，自适应控制器511对搜索引擎506为了找到地址502的匹配条目523而执行的存储器访问的数量进行评估。例如，自适应控制器511将存储器访问的数量与预定阈值进行比较。在一个实施例中，控制器511用来评估在搜索引擎506在查找操作期间所执行的存储器访问的数量的预定阈值是可配置的。如果搜索引擎506所执行的存储器访问的数量超过该预定阈值，则控制器511生成指示搜索引擎506超过了存储器访问预算的反馈。作为示例，在一个实施例中，该预定阈值被设置为两次存储器访问。由于搜索引擎506为了针对地址502所执行的查找执行了四次存储器访问，所以控制器511生成指示存储器访问预算在针对地址502的查找操作期间被超过的反馈530。在一个实施例中，搜索引擎506将反馈530提供至主机设备。例如，参考图1，在一个实施例中，搜索引擎506将反馈530提供至分组处理元件104和/或者更新单元130。响应于接收到反馈530，主机设备生成指令532，其指示搜索引擎506对地址502调适路由表508。例如，指令532指示搜索引擎506将路由信息524与在路由表508中针对其找到匹配的比前缀1.0.0.0/8更长的地址502的前缀之间的关联添加至路由表508。响应于接收到指令532，搜索引擎506将新的条目534插入到路由表508之中。在一个实施例中，新条目534包括(i)比针对其在路由表508中找到匹配的前缀1.0.0.0/8更长的地址502的前缀，和(ii)基于前缀1.0.0.0/8而从路由表508所获取到的路由信息534。

在至少一些实施例和/或者情形中，地址502的较长前缀与针对地址502所获得的路由信息524之间的关联确保了基于地址502的后续查找操作将执行较少的存储器访问，上述后续查找操作诸如用于对与地址502相关联的后续分组进行处理。在各种实施例和/或者情形中，被插入到路由表508之中的地址502的特定更长前缀通常可以是地址502的比前缀1.0.0.0/8更长的任意适当前缀。在图5的实施例中，从前缀512的集合选择了前缀1.2.3.0/24。作为结果，在至少一些实施例和/或者情形中，查找与地址1.2.3.4相关联的后续分组将仅需要对路由表508的两次存储器访问。在另一个实施例中，使用地址502的另一个适当前缀，诸如来自前缀512的集合的另一个前缀或者并未包括在前缀512的集合中的另一个前缀。例如，在一个实施例中，使用完整地址502(即，前缀1.2.3.4/32)。由于布隆过滤器系统510随后将提供地址502的最长可能(32位)前缀的肯定指示，所以在一个实施例中，使用完整的地址502确保了针对由搜索引擎506基于地址502所执行的后续查找将仅需要一次存储器访问。在其它实施例中，选择其它适当前缀。在一些实施例和/或者情形中，如果使用并非处于前缀512的集合中的前缀，则布隆过滤器系统510基于该前缀进行更新以确保布隆过滤器系统510将在针对地址502的后续查询中返回肯定指示。

在一个实施例中，使用以上所描述的自适应模式技术，在运行时间期间并且在网络设备100的数据面中(例如，使用硬件/固件部件)，新的关联被插入到路由表508中。作为结果，在该实施例中，该自适应模式确保了这些关联能够相对快地被用于处理与所检测到的地址相关联的后续分组，因此在至少一些实施例中，由于最初基于所检测到的地址所执行的大量查找而确保了相对小或者可忽略的性能损失。

在一些实施例中，系统500被配置为响应于接收到调适路由表508的指令而在随后删除被插入到路由表508中的新关联。例如，系统500被配置为使用老化方案来删除被插入到路由表508中的这样的新关联，根据上述老化方案，条目在自从该条目被插入起已经过去某个时间量时被删除，或者条目在某个时间段内并未对其进行访问的情况下被删除。

图6A-6D是在一些实施例中在路由表中所使用的示例压缩条目格式的示图。压缩路由表中的条目允许使用较少的存储器来存储该路由表和/或者允许更多信息(例如，更多条目)被存储在路由表中。在一些实施例和/或者情形中，图6A-6D的压缩条目格式在图1的路由表108或者图5的路由表508中使用。

首先参考图6A，条目格式600包括第一前缀字段602、第二前缀字段604和第三前缀字段606，以及路由信息(例如，下一跳)字段608。在一个实施例中，字段602-606被用来存储压缩形式的前缀，并且字段608则存储与前缀相关联的路由信息。在一个实施例中，第一前缀字段602存储前缀的长度X的指示，例如通过存储若干逻辑1，它们对应于与该前缀相对应的地址中的“不关注”位的数量，第二前缀字段604存储单个零位，并且第三前缀字段466存储实际前缀。仅作为说明性示例，在一个实施例中，为了存储32位地址的前缀2.3.4.0/24，字段602存储“11111111”以指示32位地址的前缀长度(24位)，字段604存储单个零位“0”，并且字段606存储实际的24位前缀2.3.4.0/24。

现在参考图6B，条目格式620包括多项式相除商数字段622和路由信息(例如，下一跳)字段624。多项式相除商数字段622存储基于地址的前缀而存储散列函数多项式相除运算的商数。条目格式620在一些其中多项式相除被用作散列函数以访问路由表的实施例中使用。在一个实施例中，不同于存储完整的前缀，条目格式620存储使用该散列函数基于前缀所生成的商数。在一个实施例中，条目620使用基于该前缀而使用散列函数所生成的余数进行访问，并且条目620中所存储的商数从条目620进行获取。在一个实施例中，使用从条目620所获取的商数来计算前缀。例如，在一个实施例中，通过将从条目620所获取的商数乘以散列函数所使用的多项式，并且向相乘的结果加上被用来访问条目620的余数来计算前缀。在一个实施例中，如果所计算的前缀与地址的前缀相匹配，则确定条目620是该地址的前缀的匹配，并且从字段624所得出的路由信息被用来路由与该地址相关联的分组。

现在参考图6C，例如，条目格式630在单个条目中包括前缀X以及前缀X直到某个水平的子前缀的路由信息，诸如紧跟地址中的前缀X的地址的四个附加位。在一些实施例中，条目格式630被用于对应于路由表的密集分布部分的条目。例如，在一个实施例中，条目格式630被用于与IPv4路由表中的20-24位前缀相关联的条目。条目格式630包括存储长度为X的前缀的第一字段632，以及被用来存储与第一字段432中所存储的前缀和第一字段632中所存储的前缀的子集合相关联的路由信息的多个第二字段634。在图6C的示例实施例中，条目630包括16个字段634以存储与共享前缀的前X位的前缀相关联的路由信息并且具有随后四个位的不同组合。当基于地址的长度为X的前缀而在字段632中找到匹配时，基于地址中紧跟长度为X的前缀的四个位而选择包含地址的路由信息(例如，下一跳)的适当字段634。因此，例如，在一个示例实施例中，跟在地址中长度为X的前缀之后的位数值0000选择字段634-1中的路由信息，跟在地址中长度为X的前缀之后的位数值0001选择字段634-2中的路由信息，等等。在一个实施例中，如果字段632中的前缀的特定子前缀的路由信息并不存在于路由表中，则相对应的字段634包括字段632中长度为X的前缀的缺省路由信息(例如，缺省的下一跳)。注意到，在一个实施例中，对于根据格式630进行格式化的路由表条目，需要单个布隆过滤器用于路由表条目中所包括的所有前缀。因此，在至少一些实施例中，与利用非压缩路由表条目的实施例相比使用了较少的布隆过滤器。例如，在示例实施例中，使用仅对应于以4递增的前缀长度(0，4，8，12等)的布隆过滤器。

现在参考图6D，在至少一些实施例中，条目640包含多个网络地址前缀的路由信息。条目格式640允许多个前缀被存储在路由表的单个条目(例如，单个存储器行)中，以便例如有效利用路由表的存储器空间。在一些实施例中，条目格式640被用于对应于路由表的稀疏分布部分的条目。条目640包括被用于存储地址前缀的第一多个字段642，以及被用于存储与前缀相关联的路由信息的第二多个字段644。在一个实施例中，字段642存储连续更长长度的前缀，其中更长前缀与更短前缀分享前面的位。例如，存储在字段642-1中的长度为X1的前缀是条目640中所存储的前缀集合中的最短前缀。在一个实施例中，存储在字段642-2中的长度为X2的前缀关于字段642-1中所存储的长度为X1的前缀为更长的前缀，并且与字段642-1中所存储的长度为X1的前缀分享前面的位。在一个实施例中，基于存储在字段642-1中的地址的最短前缀找到了地址的匹配，并且基于将其余前缀与地址的相对应前缀进行比较而选择地址的适当路由信息。

在一些实施例中，路由表(例如，图1的路由表108或者图5的路由表508)包括根据以上所描述的格式600、610、630和640中的多个的任意组合进行格式化的条目。在一些实施例中，定义了用于访问路由表的若干模式。在各个实施例中，该不同模式包括缺省模式、密集分布部分模式、稀疏分布部分模式、IPv4地址模式和IPv6地址模式等中的一种或者多种。例如，在示例实施例中，路由表包括对应于路由表中的密集分布地址范围并且根据格式630进行格式化的第一条目集合，以及对应于路由表中的稀疏分布地址范围并且根据格式640进行格式化的第二条目集合。因此，在一个实施例中，路由表根据地址对应于密集分布地址范围还是稀疏分布地址范围而基于格式630或者格式640进行访问。另外，继续相同的示例路由表，在一个实施例中，该路由表利用格式600或者格式610作为缺省条目格式。

图7是根据一个实施例的用于在存储用于转发网络设备中的分组的路由表的存储器中执行最长前缀匹配查找操作的示例方法700的流程图。在一个实施例中，方法700由图1的交换设备100所实施。例如，在一个实施例中，方法700至少部分由图1的自适应搜索引擎106或者图5的搜索引擎506所实施。在其它实施例中，方法700由交换设备100的其它适当部件或者另一个适当网络设备所实施。

在框702，获得与分组相关联的网络地址。在一个实施例中，该网络地址是从该分组的报头所提取的地址。例如，在一个实施例中，获得32位的IPv4地址。作为另一个示例，在另一个实施例中，获得128位的IPv6地址。在框704，相应布隆过滤器被应用于在框702所获得的地址的相应前缀。在一个实施例中，还基于在框702应用相应的布隆过滤器，在框704识别被该布隆过滤器指示为可能在路由表中具有匹配的一个或者多个前缀的集合。

在框706，基于在框702所识别的前缀集合针对路由表执行若干(一次或者多次)存储器访问。框706处的存储器访问以该前缀集合中的最长的一个前缀开始使用在框704所识别的前缀集合中的一个或者多个前缀来执行，如果针对该最长的一个前缀并未在路由表中找到匹配，则以前缀长度的降序继续进行直至在路由表中找到了具有匹配前缀的条目。

在框708，从在框706找到的具有匹配前缀的条目获取路由信息。在710，确定在框706所执行的存储器访问的数量超过了存储器访问的某个阈值最大数量。在框712，响应于检测到在框706所执行的存储器访问的数量超过该阈值，对路由表进行调适以减少针对与相同网络相关联的后续分组的存储器访问数量。例如，在一个实施例中，将新的条目插入到路由表中以对路由表进行调适。在一个实施例中，该新的条目将地址的较长前缀与使用在框704针对其找到匹配条目的地址的较短前缀从路由表所获取的路由信息进行关联。

图8是根据一个实施例的用于对布隆过滤器的大小进行动态调节的示例方法800的流程图，该布隆过滤器表示路由表中动态变化的前缀集合。在一个实施例中，方法800由图1的交换设备100所实施。例如，在一个实施例中，方法800至少部分由图1的自适应搜索引擎106或者图5的搜索引擎506所实施。在其它实施例中，方法800至少部分由交换设备100的其它适当部件或者另一个适当网络设备所实施。

在框802，具有至少一个布隆过滤器块的布隆过滤器被配置为表示路由表中一定长度的前缀的集合。在框804，确定以下各项之一：(i)布隆过滤器的大小应当被增大，或者(ii)该布隆过滤器的大小应当被减小。框804的确定基于与布隆过滤器相关联的因素之一来进行。例如，在各个实施例中，该确定基于布隆过滤器的填充水平、针对布隆过滤器所计算的错误肯定概率、从布隆过滤器统计确定的错误肯定概率、与布隆过滤器相关联的另一个适当因素等中的一个或者多个来进行。当确定布隆过滤器的大小应当被增大，在框806，另外的一个或者多个布隆过滤器块被添加至布隆过滤器。另一方面，当确定布隆过滤器的大小应当减小，在框808，一个或者多个布隆过滤器块从布隆过滤器被去除。

以上所描述的各个模块、操作和技术中的至少一些可以利用硬件、执行固件指令的处理器、执行软件指令的处理器或者其任意组合来实施。当利用执行软件或者固件指令的处理器来实施时，该软件或者固件指令可以存储在任意适当的计算机可读介质或者媒体中，诸如存储在磁盘、光盘、RAM或者ROM或者闪存等中。该软件或者固件指令可以包括机器可读指令，当被处理器所执行时，该指令使得处理器执行各种动作。

当以硬件实施时，该硬件可以包括一个或者多个离散部件、集成电路、应用特定集成电路(ASIC)、可编程逻辑设备(PLD)等。

虽然已经参考特定示例对本发明进行了描述，但是其意在仅是说明性的而并非对本发明进行限制，可以在不背离本发明的范围的情况下对所公开的实施例进行改变、添加和/或者删除。