基于TCAM技术的高速路由查找方案

An Approach to High-speed Routing Lookup Based on TCAM

基于TCAM技术提出一个高速路由查找方案。该方案可以达到每秒钟100M次的查找速度,满足OC48和OC192接口的线速转发要求。方案使用了索引表和映射表的二级结构存储路由的下一跳信息,大大减小了存储空间,同时对IPv6具有很好的扩展性。对TCAM的路由更新问题进行了讨论,提出一个最坏情况下O(W 2)的更新算法(W为前缀长度集合的数目),有效地提高了TCAM的更新性能。

This paper proposes an approach of highspeed routing lookup based on TCAM. The approach can get a lookup speed of 100M times per second and satisfy the sending speed required by the OC48 and OC192 interfaces. By using two layer structure of the index table and the map table to storage the next hop information of the routers, it reduces the storage spaces greatly and makes a good generalization to IPv6. The paper also discusses the problem of routing update of TCAM. An updating algorithm is proposed, which has a time complexity of O(W/2) in the worst case(where W indicates the number of prefix length sets) and improves the updating ability of TCAM effectively.