刘宗宝，赵 鑫，张 力，李之乾，张 琨

(中国航天科工集团第二研究院 七〇六所，北京 100854)

0 引 言

信息技术的发展推动核心路由器的线速转发率达到40 Gbps以上[1]，路由查找是核心路由器实现高性能线速转发的关键技术。目前路由查找算法主要有软件查找算法和硬件查找算法，基于软件的路由查找方法需要多次内存操作才能完成路由查找，无法满足高速接口线速转发的要求。基于硬件的路由查找算法大多基于TCAM(ternary content addressable memory)[2-4]技术实现，执行速度快，可以在一个时钟周期内完成路由表项的匹配查询，优先级编码器(priority encoder，PE)从多个匹配结果中选择最长前缀匹配(longest prefix match，LPM)作为查找结果，因此TCAM特别适合于高性能路由器，实现快速路由查找和转发。但是，传统TCAM的更新性能较差[5]：路由表是动态变化的并且规模大幅增长，TCAM中路由表项按照前缀长度降序排列，为保证路由表项的优先级，对路由表项的插入、删除等更新操作会造成大量的内存移动[6]，最坏情况下的更新算法复杂度为O(N)(N为TCAM中的路由表项数量)，导致路由查找性能大幅下降，无法满足高性能路由器线速查找转发的要求。

针对TCAM路由表项的更新算法国内外学者进行了大量的研究，提出了许多性能优化的算法，参见文献[7-9]等。PLO-OPT更新算法是对选择移动更新算法的改进，即空闲前缀表项从TCAM的底部移动到了TCAM的中间，因此一次更新操作最多需要L/2次(L是路由前缀的长度)路由表项移动。CAO_OPT更新算法把路由表转化为trie树，只对同一条链路(从根节点到叶子节点)上的规则排序[10]，一次更新操作最多需要D/2次(D是相互重叠的前缀的最大个数)路由表项移动。……