An Optimal and Flexible TCAM Software Simulation Algorithm

This paper presents an optimal and flexible algorithm for matching many search keys against many entries with arbitrary wildcard (i.e., "don\´t care") bits to simulate TCAM lookups in software. The algorithm is also enhanced by using more memory to match search keys containing arbitrary wildcards. To speed up the lookup operation in the functional TCAM model, the algorithm stores intermediary results in a two-dimensional array based on the TCAM entries. It is proved that the algorithm uses the optimal number of bit wise-AND operations in finding the matches. In a theoretical analysis, the proposed algorithm achieves a speedup factor of more than 16 compared to sequential search using reasonable memory footprints, and the best speedup reaches a factor of 27 in our experiments. Finally, the empirical evaluation of the algorithm identifies a sweet spot in the trade-off between space and time which can be practically configurable in simulation.