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

摘要

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