一种实现TCAM快速增量更新的算法

A New Algorithm to Realize Fast Incremental Updates of TCAMs

三重内容可寻址存储器TCAM(ternarycontent-addressablememory)是执行快速路由查找的常用硬件设备。在TCAM中进行最长前缀匹配操作最糟糕情况可能需要次存储操作,这里提出了一种算法来处理TCAM,结果使增量更新时间在最糟糕情况保持较小。通过对该算法与其他算法的性能分析,证明该算法在前缀长度排序限制条件下较常用算法更优。

One popular hardware device for performing fast routing lookups and packet classification is a ternary content-addressable memory （TCAM）, and the key to realize routing lookup lies in fast incremental updates. But it may take memory shift （write） operations in the worst case on TCAM. This paper proposes one algorithm to manage the TCAM such that incremental update times remain small in the worst case, which is proved better than other normal one.