一种改进的LPM路由查找算法

针对高性能路由器中性能强大的硬件查找器件三态内容寻址存储器(ternary content-addressable memory,TCAM)价格昂贵与TCAM芯片支持的表项优先级数量不足的问题,提出了一种改进的最长前缀匹配(longest prefix match,LPM)算法。首先,使用改进的表项分配策略将相同匹配度的表项分别放置在不同优先级的存储表项中,以避免路由查找错误的发生。然后,选择不同的链路添加路由条目,根据实际情况确定TCAM中条目的搬移策略,进行路由条目搬移。最后,根据不同的场景,进行路由条目的删除操作。实验结果表明,所提方法在不影响路由查找结果的基础上,提高了芯片的空间利用率,解决了网络处理器查找命中错误的问题,充分发挥了芯片的效能,取得了较好的实用效果。