TCAMimic: A TCAM Software Simulation

TCAM is a fast ternary associative cache memory, which is common in today’s routers, mainly in order to perform high rate packet-classification. Recently we are witnessing many works that use this powerful memory type to solve other hard problems that require high-speed solutions for example, pattern matching, regular expression matching, and heavy hitters analysis. While TCAM is a very powerful off-the-shelf new type of memory, currently it still requires hardware specialties to use it. Thus the research works are evaluated and analyzed using synthetic model only.
We show that understanding the detailed design of TCAM is important in order to understand the limitations and power of TCAM, as many works ignore the fact that while TCAM has a high throughput, it also has, by design, a high latency. Thus, many of the previously-proposed works which assumed closed-loop lookups (namely, where the input of a TCAM lookup depends on the result of a previous TCAM lookup) cannot be efficiently implemented as is and require a modification to their algorithm.
We present TCAMimic, a TCAM simulator that addresses the need of an easy-to-use software simulator of TCAM hardware. Using the TCAMimic simulator, we run intra-flow interleaving, where queries from different parts of the same flow are interleaved, and show that this significantly reduces the latency with only a marginal reduction in the throughput.